多路径QoS路由算法研究
摘要
随着Internet的迅猛增长及具有实时要求的新兴业务(如VoIP，视频会议、多媒体远程教学、视频点播等)不断出现，用户对网络服务质量(QoS，Qualityof Service)的要求越来越高。
路由问题处于网络的核心地位，也是决定网络传输质量的主要因素之一。QoS路由(QoSR，QoS Routing)是QoS研究中的核心技术和热点问题。传统路由算法满足不了用户的QoS要求，而且在最短路径上容易产生拥塞。因此，需要采取一定的约束路由机制来平衡网络负载，提高传输效率。QoS路由的出现就能够有效地解决这些问题。多约束条件下的QoS路由问题是一个NP-完全问题，一般采用启发式算法寻找其次优解。网络链路状态信息的非精确性是客观存在的，因而研究非精确网络状态信息下的QoS路由算法十分必要。多路径路由算法在克服网络状态信息非精确性方面具有较好的性能，并能有效平衡网络负载。
现有的QoS路由算法有各种启发式算法、神经网络算法、遗传算法和蚂蚁算法等。这些算法往往存在约束条件单一，没有考虑网络负载平衡，也没有考虑与传统最短路径优先路由算法的共存问题等缺陷。
基于现有方法存在的局限性，本文研究了非精确网络状态信息下的多路径QoS路由算法，在改进原有算法的基础上，提出并实现了2种QoS路由算法：Minpath算法和KMulpath算法。Minpath算法基于改进的Bellman_Ford算法，通过剪裁策略减少了算法的搜索空间，寻找出满足带宽、时延和跳数约束的最小代价路由。KMulpath算法采用深度优先搜索策略，计算并预存K条满足带宽、时延和跳数约束的QoS路径。通过路径评价函数和对路径带宽利用率的比较，找出最优和次优路径。在最优路由失效时迅速转到备用的次优路由上去，极大地减少了重路由开销，能有效解决由于链路状态信息的非精确而引起的问题。
为了验证算法的有效性，用ns-2建立网络仿真场景，采用这两种QoS路由算法进行仿真试验。通过与传统算法性能的比较，可以看出这两种算法能平衡网络负载，提高网络资源利用率，具有较好的性能。
对QoS路由算法与传统最短路径路由算法的共存问题进行了初步探讨。在仿真中根据网络流量的变化自适应调整路由策略，动态选择是采用原来的最短路径路由还是QoS路由，从而解决了与传统路由算法的共存问题。实验结果表明KMulpath算法能与传统算法良好共存，同时提高了网络性能。
As the fast growth of Internet and the continues emergence of newly services having real time demand such as Voice over IP, Video Conference, Multimedia long-distance Education and Video Programme, user's demand on Quality of Service (QoS) becomes higher and higher.
Routing is the kernel of network. It is also one of the main factors deciding QoS. QoS Routing (QoSR) is the core technique and hotspot in the research of QoS. Traditional routing algorithm can't meet the user's QoS need. At the same time, the shortest path can easily become congested, which leads to the network performance drops dramatically. So some constrained-routing mechanism must be taken to balance network load and improve transfer efficiency. The emergency of QoS routing can solve this problem efficiently. Multiple constrained QoS routing problem is a NP-complete problem. Currently, we search hypo-excellent paths using heuristic algorithm to solve this problem. The imprecision of network link-state information is objective, thus, the research of QoS routing algorithms under imprecise link-state information becomes necessarily. Multi-path routing algorithm can balance network load and have a preferable performance in coping with imprecise network link-state information.
The existing algorithms of QoS routing include various heuristic algorithms, neural network-based algorithms, hybrid genetic algorithms, ant-algorithms and so on. These algorithms exist some defects as foliows:(1) the constrain condition of these algorithms is single (2) they dont take the network load balance into consideration (3) they don't consider the coexistence of themselves with traditional shortest-path first algorithm.
Aiming at solving these defects, we design and realize multi-path QoS routing algorithm under imprecise link-state information in this paper: Minpath algorithm and KMulpath algorithm. Based on unproved Bellman_Ford algorithm, Minpath algorithm can find the least cost path meeting bandwidtiu delay and hop constrains. Using deepest first search strategy, KMulpath algorithm can find and keep multiple QoS paths meeting QoS constrains in advance. Then, it can select the best and hypo-best path among these multiple QoS paths through path evaluation function and the comparison between bandwidth utilization of these paths. When the best route is invalid, route can be switched to the hypo-best path quickly. As a result, it can decrease reroute spending greatly and solve the problems caused by imprecise link-state information.
To validate the efficiency of our algorithms, we create network simulate scenes and go along simulate experiment using these two QoS routing algorithms. By comparison with traditional shortest path first routing algorithm, it can be seen that these two algorithms can balance network load and heighten network resource utilization.
Also we primarily probe into the coexistence problem of QoS routing algorithm with traditional shortest path first routing algorithm. In network simulation, our dynamical routing algorithm can adjust routing strategy adaptively according to changes of network stream , choose route dynamically and decide using whether the shortest path or the QoS path, solving the problem of the coexistence of QoS routing algorithm with traditional routing algorithm. The result of simulation experiment indicates that KMulpath algorithm can coexist with traditional shortest-path algorithm excellently and has a preferable network performance.
路由问题处于网络的核心地位，也是决定网络传输质量的主要因素之一。QoS路由(QoSR，QoS Routing)是QoS研究中的核心技术和热点问题。传统路由算法满足不了用户的QoS要求，而且在最短路径上容易产生拥塞。因此，需要采取一定的约束路由机制来平衡网络负载，提高传输效率。QoS路由的出现就能够有效地解决这些问题。多约束条件下的QoS路由问题是一个NP-完全问题，一般采用启发式算法寻找其次优解。网络链路状态信息的非精确性是客观存在的，因而研究非精确网络状态信息下的QoS路由算法十分必要。多路径路由算法在克服网络状态信息非精确性方面具有较好的性能，并能有效平衡网络负载。
现有的QoS路由算法有各种启发式算法、神经网络算法、遗传算法和蚂蚁算法等。这些算法往往存在约束条件单一，没有考虑网络负载平衡，也没有考虑与传统最短路径优先路由算法的共存问题等缺陷。
基于现有方法存在的局限性，本文研究了非精确网络状态信息下的多路径QoS路由算法，在改进原有算法的基础上，提出并实现了2种QoS路由算法：Minpath算法和KMulpath算法。Minpath算法基于改进的Bellman_Ford算法，通过剪裁策略减少了算法的搜索空间，寻找出满足带宽、时延和跳数约束的最小代价路由。KMulpath算法采用深度优先搜索策略，计算并预存K条满足带宽、时延和跳数约束的QoS路径。通过路径评价函数和对路径带宽利用率的比较，找出最优和次优路径。在最优路由失效时迅速转到备用的次优路由上去，极大地减少了重路由开销，能有效解决由于链路状态信息的非精确而引起的问题。
为了验证算法的有效性，用ns-2建立网络仿真场景，采用这两种QoS路由算法进行仿真试验。通过与传统算法性能的比较，可以看出这两种算法能平衡网络负载，提高网络资源利用率，具有较好的性能。
对QoS路由算法与传统最短路径路由算法的共存问题进行了初步探讨。在仿真中根据网络流量的变化自适应调整路由策略，动态选择是采用原来的最短路径路由还是QoS路由，从而解决了与传统路由算法的共存问题。实验结果表明KMulpath算法能与传统算法良好共存，同时提高了网络性能。
As the fast growth of Internet and the continues emergence of newly services having real time demand such as Voice over IP, Video Conference, Multimedia long-distance Education and Video Programme, user's demand on Quality of Service (QoS) becomes higher and higher.
Routing is the kernel of network. It is also one of the main factors deciding QoS. QoS Routing (QoSR) is the core technique and hotspot in the research of QoS. Traditional routing algorithm can't meet the user's QoS need. At the same time, the shortest path can easily become congested, which leads to the network performance drops dramatically. So some constrained-routing mechanism must be taken to balance network load and improve transfer efficiency. The emergency of QoS routing can solve this problem efficiently. Multiple constrained QoS routing problem is a NP-complete problem. Currently, we search hypo-excellent paths using heuristic algorithm to solve this problem. The imprecision of network link-state information is objective, thus, the research of QoS routing algorithms under imprecise link-state information becomes necessarily. Multi-path routing algorithm can balance network load and have a preferable performance in coping with imprecise network link-state information.
The existing algorithms of QoS routing include various heuristic algorithms, neural network-based algorithms, hybrid genetic algorithms, ant-algorithms and so on. These algorithms exist some defects as foliows:(1) the constrain condition of these algorithms is single (2) they dont take the network load balance into consideration (3) they don't consider the coexistence of themselves with traditional shortest-path first algorithm.
Aiming at solving these defects, we design and realize multi-path QoS routing algorithm under imprecise link-state information in this paper: Minpath algorithm and KMulpath algorithm. Based on unproved Bellman_Ford algorithm, Minpath algorithm can find the least cost path meeting bandwidtiu delay and hop constrains. Using deepest first search strategy, KMulpath algorithm can find and keep multiple QoS paths meeting QoS constrains in advance. Then, it can select the best and hypo-best path among these multiple QoS paths through path evaluation function and the comparison between bandwidth utilization of these paths. When the best route is invalid, route can be switched to the hypo-best path quickly. As a result, it can decrease reroute spending greatly and solve the problems caused by imprecise link-state information.
To validate the efficiency of our algorithms, we create network simulate scenes and go along simulate experiment using these two QoS routing algorithms. By comparison with traditional shortest path first routing algorithm, it can be seen that these two algorithms can balance network load and heighten network resource utilization.
Also we primarily probe into the coexistence problem of QoS routing algorithm with traditional shortest path first routing algorithm. In network simulation, our dynamical routing algorithm can adjust routing strategy adaptively according to changes of network stream , choose route dynamically and decide using whether the shortest path or the QoS path, solving the problem of the coexistence of QoS routing algorithm with traditional routing algorithm. The result of simulation experiment indicates that KMulpath algorithm can coexist with traditional shortest-path algorithm excellently and has a preferable network performance.
引文
[1] R.Rajkumar, C.Lee, J.Lehoczky, D. Siewiorek. A resource allocation model for QoS management. The 18th IEEE Real-Time Systems Symposium, 1997. pp: 298-307.
[2] R.L.Cruz. Quality of Service Guarantees in Virtual Circuit Switched Networks. IEEE Journal on Selected Areas in Communications, 1995.13(6): 1048-1056.
[3] R.Braden, D.Clark, S.Shenker. Integrated Services in the Interaet Architecture: an Overview. Internet RFC 1633, June 1994.
[4] S.Blake, et al. An Architecture for Differentiated Services. RFC 2475, Dec 1998.
[5] E.Rosen, A.Viswanathan, R.Callon. Multi-protocol Label switching Architecture. Internet draft, draft-ietf-mpls-arch-01.txt, Mar 1998.
[6] D.Awduche, et al. Requirements for Traffic Engineering over MPLS. Internet draft, draft-ietf-mpls-traffic-eng.00.txt, Oct 1998.
[7] Crawley E, Nair R, Rajagopalan B, Sandick H. RFC 2386 A Framework for QoS-based Routing in the Internet. IETF, August 1998.
[8] Xipeng Xiao and Lionel M. Ni. Internet QoS: A Big Picture. IEEE Network. 1999, 17(2): 8-18.
[9] Y.Bernet, R.Yavatkar, P.Ford, F.Baker, et al. Interoperation of RSVP/Int-Serv and Diff-Serv Networks. Work in Progress, February 1999.
[10] Z.Wang and J.Crowcroft. QoS Routing for Supporting Resource Reservation. IEEE Journal on Selected Areas in Communications, 1996.14(7): 1228-1234.
[11] Qingming Ma and Peter Steenkiste. Quality-of-Service Routing with Performance Guarantees. Proceedings of the 4th International IFTP Workshop on Quality-of-Service, May 1997. pp. 115-126.
[12] C.Pornavalai, G.Chakraborty, N.Shiratori. QoS Based Routing Algorithm in Integrated Service Packet Networks. Journal of High Speed Networks, 1998, 7(2): 99-112.
[13] H.F.Salama, D.S.Reeves, Y.Viniotis. A Distributed Algorithm for Delay-Constrained Unicast Routing. IEEE/ACM Transactions on Networking (TON), 2000.8(2): 239-250.
[14] Dean H.Lorenz and Ariel Orda. Optimal Partition of QOS Requirements on Unicast Paths and Multicast trees. In IEEE INFOCOM'99, March 1999.pp.246-253.
[15] J. Westcott, J. Jubin. A Distributed Routing Design for a Broadcast Environment. Conference Record of IEEE Military Communications Conference, Boston, MA, October 1982, pp. 152-160.
[16] D.Xuan, W.Jia, W.Zhao. Integrated Routing Algorithms for Anycast Messages. Proc.International Conference on Parallel Processing, 1998, pp. 122-130.
[17] 马任璐，程时端．宽带IP网络的QoS路由：框架和问题．高技术通讯，2000．18(5)：99-103．
[18] Z.Wang, J.Crowcroft. QoS Routing for Supporting Resource Reservation. IEEE Journal on Selected Areas in Communications, 1996, 14(7): 1228-1234.
[19] S.Wi, Y. Choi. A Delay Constrained Distributed Multicast Routing Algorithlm. 12th International Conference on Computer Conununication, ICCC' 95, 1995, pp. 833-838.
[20] F.Kamoun, L.Kleinrock. Hierarchical Routing for Large Networks. Computer Networks. 1977, 1 (3): 155—174.
[21] S. Chen and K. Nahrstedt. Distributed Quality-of-Service Routing in High-Speed Networks Based on Selective Probing. LCN'98, 1998, pp. 80-89.
[22] K.G. Shin and C.-C. Chou. A Distributed Route-Selection Scheme for Establishing Real-Time Channel. Sixth IFIP Int'1 Conf. On High performance Networking Conf (HPN'95), Sep. 1995, pp. 319-329.
[23] Zhang Zhi-Li. End-To-End support for Statistical Quality-of-Service Guarantees in Multimedia Networks, Ph.D. thesis. Feb.1997, University of Massachusetts at Amherst. Amherst, MA. 56-60.
[24] A.Shaikh. Efficient Dynamic Routing in Wide-Area Networks, Ph.D.thesis. May 1999, University, of Michigan. 16-21.
[25] Anees Shaikh, Jennifer Rexford, Kang Shin. Dynamics of Quality-of-Service Routing with Ifiaccurate Link-State Information. Technical report CSE-TR-350-97, Dept.of Electrical-Engineering and Computer Science, the University of Michigan, Nov. 1997.
[26] Roch A.Guerin, Ariel Orda. QoS Routing in Neworks with Inaccurate Information: Theory and Algorithms. IEEE/ACM Transactions on Networking. 1999. 7(3): 350-364.
[27] Huitema C．陶文星译．因特网路由技术．1998．1，第一版，北京：清华大学出版社：55-60．
[28] 严蔚敏，吴伟民编著．数据结构(C语言版)．1996，第一版，北京：清华大学出版：210-215．
[29] Z. Wang, J. Crowcroft. QoS Routing for Supporting Resource Reservation. IEEE Journal on Selected Areas in Communications, September 1996. 14(7): 1228-1234.
[30] Q. Ma, P. Steenkiste. Quality-of-Service Routing with Performance Guarantees. 4th International IFIP Workshop on Quality of Service, May 1997. pp. 115-126.
[31] R. Guerin, A. Orda. QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms. IEEE/ACM Transactions on Networking, 1999, 7(3): 350-364.
[32] S.Chen, K.Nahrstedt. On finding multi-constrained paths. Proceedings of the IEEE International Conference on Communications(ICC'98). Atlanta: IEEE Communication Society, 1998, pp. 874-879.
[33] L.Guo and I.Matta. Search Space Reduction in QoS Routing. Computer Networks: The International Journal of Computer and Telecommunications Networking, 2003, 41(1): 73-88.
[34] F.Xiang, L.Junzhou, W.Jieyi, G.Guanqun. QoS Routing Based on Genetic algorithm. Computer communications, 1999.Vol.22:1394-1399.
[35] H.F. Salama, D. S. Reeves, Y. Viniotis. A Distributed Algorithm for Delay-Constrained Unicast Routing. IEEE/ACM Transactions on Networking (TON), 2000, 8(2): 239-250.
[36] Q. Sun, H. Langendoffer. A New Distributed Routing Algorithm with End-to-End Delay Guarantee. Proceedings of the IFIP Fifth International Workshop on Quality of Service, Columbia University, New York. May 1997.
[37] I. Cidon, R. Rom, Y. Shavitt. Multi-path Routing Combined with Resource Reservation. IEEE INFOCOM'97, Kobe, Japan. April 1997, pp. 92-100.
[38] K.G. Shin, C. -C. Chou. A Distributed Route Selection Scheme for Establishing Real-Time Channel. Sixth IFIP Int'1 Conf on High Performance Networking Conf. (HPN'95), Sep. 1995, pp. 319-329.
[39] ATM Forum. Private Network-Network Interface (PNNI) v1.0 specifications. May 1996.
[40] A.Orda. Routing with End-to-End QoS Guarantees in Broadband applications. INIFOCOM'98, March 1998, 1(2): 27-34.
[41] E. I. Chong, S. Maddila, S.Morley. On finding Single-Source Single-Destination k-Shortest Paths. In proc. International Conference on Computing and Information (ICCI'95), Ontario, Canada, July 1995, pp. 40-47.
[42] D.D. Kandlur, K. G. Shin, D. Ferrari. Real-time Communication in Multi-hop Networks, Proc. 11th Int'1 Conf. Dist. Comp. Syst, 1991, pp. 300-307.
[43] Dean H.Lorenz, A.Orda. QoS Routing in Networks with Uncertain Parameters. IEEE/ACM Transactions on Networking, 1998.6(6): 768-778.
[44] A.Shajkh. J.Rexford. K.Shin. Evaluating the Overheads of Source-Directed Quality-of-Service Routing. IEEE International Conference on Network
Protocols (ICNP'98), Austin, TX, October 1998. pp. 42-51.
[45] J.Rexford, A.Shaikh. Performance Evaluation of Quality-of-Service Routing with Inaccurate Link-State Information. Proc.OPENSIG Fall'97 Workshop, Columbia University, October 1997.
[46] Qingrning Ma, Peter Steenkiste. On Path Selection for Traffic with Bandwidth Guarantees. In the Proceedings of IEEE International Conference on Network Protocols, Atlanta, Georgia,. October 1997. pp. 153-179.
[47] Srihari Nelalmditi, Rose P.Tsang, Zhi-Li Zhang, Quality. -of-Service Routing without Global Information Exchange, In Proc. IFTP International Workshop on Quality-of-Service (IWQoS'99), London, UK. June 1999, pp. 129-131.
[48] Xin Yuan, Wei Zheng. A Comparative Study of Quality of Service Routing Schemes That Tolerate Imprecise State Information. Florida State University, Technical Report TR-010704, http://websrv.cs.fsu.edu/research/reports. 2002.
[49] Yanxia Jia, Ioanis Nikoladis, Pawel Oburzynski. Multiple Path QoS Routing. IEEE International Conference on Communications. Burbank, California, 2001, pp. 2583-2587.
[50] I.Cidon, R.Rom, Y.Shawitt. Analysis of Multi-path Routing. IEEE Transaction on Networking, 1999, 7: 885-896.
[51] Y.Jia, Y.Nikolaidis, P. Gburzynsld. Multiple Path Routing in Networks with Inaccurate Link State Infonnation. IEEE International Conference on Communications(ICC'2001), Helslnki, Finland, June 2001.
[52] 张保贤，刘越，陈长嘉．QoS路由的多路径算法．电子学报，2000．28(7)：120-122．
[53] 崔勇，吴建平，徐恪，徐明伟．互联网络服务质量路由算法研究综述．软件学报．2002，13(4)：10-21．
[54] 王建新，陈松乔，陈建二，王伟平．基于QoS的随机源选路由算法研究．小型微型计算机系统，2001，22(8)：917-920．
[55] 冯径，顾冠群．基于不确定参数的QoS路由研究．计算机研究与发展，2002，39(5)：533-539．
[56] 石坚，赵硕生．基于非精确状态的动态组播QoS路由算法．华中科技大学学报，2001．29(6)：22-24．
[57] Zhu Huiling, Ma Zhengxin, Wang Yongqian, Cao Zhigang. Improving QoS routing with multi-path scheme under inaccurate link state information. The International Conference on Fundamentals of Electronics, Communications and Computer Sciences. Tokyo, Japan, 2002. pp. 67-82.
[58] G.Apostolopoulos, R.Guerin, S.Kamat, S.Tripathi. Improving QoS Routing Performance Under Inaccurate Link State Information. Proceedings of the 16th International Teletraffic Congress, Edinburgh. UK. June 7-11. 1999. pp.
1351-1362.
[59] S.Chen, K.Nahrstedt. An Overview of Quality-of-Service Routing for the Next Generation High-Speed Networks: Problems and Solutions. IEEE Networks, Nov/Dec 1998.12(6): 64-79.
[60] P.E. Boyer, D. P. Trachier. A reservation principle with applications to the ATM traffic control. Computer Networks and ISDN Systems. 1992, 24(4): 321-334.
[61] Y. Shavitt. Burst Control in high-Speed Network. PHD thesis. Technion-Israel Institute of Technology, Electrical Engineering Dept., Technion City, Haifa 32000, Israel, June 1996.
[62] J.S. Turner. Managing bandwidth in ATM networks with burtsy traffic. IEEE Network, September 1992, 6(5): 50-58.
[63] R.Widyono. The Design and Evaluation of Routing Algorithms for Real-time Channels. Technical Report ICSI TR-94-024, International Computer Science Institute, UC Berkeley, June 1994.
[64] X.Yuan. On the extended Bellman-Ford algorithm to solve two—constrained quality of service muting problems. Proceedings of the Eighth International Conference on Computer Communications and Networks(IC3N'99). Boston, Massachusetts:IEEE Communication Society, 1999, pp. 304-10.
[65] X.Yuan, X.Liu. Heuristic algorithms for multi-constrained quality of service routing. Proceedings of the IEEE INFOCOM'01. Piscataway, NJ: IEEE Communication Society, 2001, pp. 844 -853.
[66] 刘千里，汪泽焱，倪明放．一种基于多条件约束的QoS路由选择优化算法[J]．计算机研究与发展，2001，38(3)：275-278．
[67] 汪泽焱．一种基于多目标优化的Q O S路由交互式算法[J]．国防科技大学学报．2002．24(4)：37-41．
[68] The Network Simulator- ns-2. http://www.isi.edu/nsnam/ns/, 2001-06-04.
[2] R.L.Cruz. Quality of Service Guarantees in Virtual Circuit Switched Networks. IEEE Journal on Selected Areas in Communications, 1995.13(6): 1048-1056.
[3] R.Braden, D.Clark, S.Shenker. Integrated Services in the Interaet Architecture: an Overview. Internet RFC 1633, June 1994.
[4] S.Blake, et al. An Architecture for Differentiated Services. RFC 2475, Dec 1998.
[5] E.Rosen, A.Viswanathan, R.Callon. Multi-protocol Label switching Architecture. Internet draft, draft-ietf-mpls-arch-01.txt, Mar 1998.
[6] D.Awduche, et al. Requirements for Traffic Engineering over MPLS. Internet draft, draft-ietf-mpls-traffic-eng.00.txt, Oct 1998.
[7] Crawley E, Nair R, Rajagopalan B, Sandick H. RFC 2386 A Framework for QoS-based Routing in the Internet. IETF, August 1998.
[8] Xipeng Xiao and Lionel M. Ni. Internet QoS: A Big Picture. IEEE Network. 1999, 17(2): 8-18.
[9] Y.Bernet, R.Yavatkar, P.Ford, F.Baker, et al. Interoperation of RSVP/Int-Serv and Diff-Serv Networks.
[10] Z.Wang and J.Crowcroft. QoS Routing for Supporting Resource Reservation. IEEE Journal on Selected Areas in Communications, 1996.14(7): 1228-1234.
[11] Qingming Ma and Peter Steenkiste. Quality-of-Service Routing with Performance Guarantees. Proceedings of the 4th International IFTP Workshop on Quality-of-Service, May 1997. pp. 115-126.
[12] C.Pornavalai, G.Chakraborty, N.Shiratori. QoS Based Routing Algorithm in Integrated Service Packet Networks. Journal of High Speed Networks, 1998, 7(2): 99-112.
[13] H.F.Salama, D.S.Reeves, Y.Viniotis. A Distributed Algorithm for Delay-Constrained Unicast Routing. IEEE/ACM Transactions on Networking (TON), 2000.8(2): 239-250.
[14] Dean H.Lorenz and Ariel Orda. Optimal Partition of QOS Requirements on Unicast Paths and Multicast trees. In IEEE INFOCOM'99, March 1999.pp.246-253.
[15] J. Westcott, J. Jubin. A Distributed Routing Design for a Broadcast Environment. Conference Record of IEEE Military Communications Conference, Boston, MA, October 1982, pp. 152-160.
[16] D.Xuan, W.Jia, W.Zhao. Integrated Routing Algorithms for Anycast Messages. Proc.International Conference on Parallel Processing, 1998, pp. 122-130.
[17] 马任璐，程时端．宽带IP网络的QoS路由：框架和问题．高技术通讯，2000．18(5)：99-103．
[18] Z.Wang, J.Crowcroft. QoS Routing for Supporting Resource Reservation. IEEE Journal on Selected Areas in Communications, 1996, 14(7): 1228-1234.
[19] S.Wi, Y. Choi. A Delay Constrained Distributed Multicast Routing Algorithlm. 12th International Conference on Computer Conununication, ICCC' 95, 1995, pp. 833-838.
[20] F.Kamoun, L.Kleinrock. Hierarchical Routing for Large Networks. Computer Networks. 1977, 1 (3): 155—174.
[21] S. Chen and K. Nahrstedt. Distributed Quality-of-Service Routing in High-Speed Networks Based on Selective Probing. LCN'98, 1998, pp. 80-89.
[22] K.G. Shin and C.-C. Chou. A Distributed Route-Selection Scheme for Establishing Real-Time Channel. Sixth IFIP Int'1 Conf. On High performance Networking Conf (HPN'95), Sep. 1995, pp. 319-329.
[23] Zhang Zhi-Li. End-To-End support for Statistical Quality-of-Service Guarantees in Multimedia Networks, Ph.D. thesis. Feb.1997, University of Massachusetts at Amherst. Amherst, MA. 56-60.
[24] A.Shaikh. Efficient Dynamic Routing in Wide-Area Networks, Ph.D.thesis. May 1999, University, of Michigan. 16-21.
[25] Anees Shaikh, Jennifer Rexford, Kang Shin. Dynamics of Quality-of-Service Routing with Ifiaccurate Link-State Information. Technical report CSE-TR-350-97, Dept.of Electrical-Engineering and Computer Science, the University of Michigan, Nov. 1997.
[26] Roch A.Guerin, Ariel Orda. QoS Routing in Neworks with Inaccurate Information: Theory and Algorithms. IEEE/ACM Transactions on Networking. 1999. 7(3): 350-364.
[27] Huitema C．陶文星译．因特网路由技术．1998．1，第一版，北京：清华大学出版社：55-60．
[28] 严蔚敏，吴伟民编著．数据结构(C语言版)．1996，第一版，北京：清华大学出版：210-215．
[29] Z. Wang, J. Crowcroft. QoS Routing for Supporting Resource Reservation. IEEE Journal on Selected Areas in Communications, September 1996. 14(7): 1228-1234.
[30] Q. Ma, P. Steenkiste. Quality-of-Service Routing with Performance Guarantees. 4th International IFIP Workshop on Quality of Service, May 1997. pp. 115-126.
[31] R. Guerin, A. Orda. QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms. IEEE/ACM Transactions on Networking, 1999, 7(3): 350-364.
[32] S.Chen, K.Nahrstedt. On finding multi-constrained paths. Proceedings of the IEEE International Conference on Communications(ICC'98). Atlanta: IEEE Communication Society, 1998, pp. 874-879.
[33] L.Guo and I.Matta. Search Space Reduction in QoS Routing. Computer Networks: The International Journal of Computer and Telecommunications Networking, 2003, 41(1): 73-88.
[34] F.Xiang, L.Junzhou, W.Jieyi, G.Guanqun. QoS Routing Based on Genetic algorithm. Computer communications, 1999.Vol.22:1394-1399.
[35] H.F. Salama, D. S. Reeves, Y. Viniotis. A Distributed Algorithm for Delay-Constrained Unicast Routing. IEEE/ACM Transactions on Networking (TON), 2000, 8(2): 239-250.
[36] Q. Sun, H. Langendoffer. A New Distributed Routing Algorithm with End-to-End Delay Guarantee. Proceedings of the IFIP Fifth International Workshop on Quality of Service, Columbia University, New York. May 1997.
[37] I. Cidon, R. Rom, Y. Shavitt. Multi-path Routing Combined with Resource Reservation. IEEE INFOCOM'97, Kobe, Japan. April 1997, pp. 92-100.
[38] K.G. Shin, C. -C. Chou. A Distributed Route Selection Scheme for Establishing Real-Time Channel. Sixth IFIP Int'1 Conf on High Performance Networking Conf. (HPN'95), Sep. 1995, pp. 319-329.
[39] ATM Forum. Private Network-Network Interface (PNNI) v1.0 specifications. May 1996.
[40] A.Orda. Routing with End-to-End QoS Guarantees in Broadband applications. INIFOCOM'98, March 1998, 1(2): 27-34.
[41] E. I. Chong, S. Maddila, S.Morley. On finding Single-Source Single-Destination k-Shortest Paths. In proc. International Conference on Computing and Information (ICCI'95), Ontario, Canada, July 1995, pp. 40-47.
[42] D.D. Kandlur, K. G. Shin, D. Ferrari. Real-time Communication in Multi-hop Networks, Proc. 11th Int'1 Conf. Dist. Comp. Syst, 1991, pp. 300-307.
[43] Dean H.Lorenz, A.Orda. QoS Routing in Networks with Uncertain Parameters. IEEE/ACM Transactions on Networking, 1998.6(6): 768-778.
[44] A.Shajkh. J.Rexford. K.Shin. Evaluating the Overheads of Source-Directed Quality-of-Service Routing. IEEE International Conference on Network
Protocols (ICNP'98), Austin, TX, October 1998. pp. 42-51.
[45] J.Rexford, A.Shaikh. Performance Evaluation of Quality-of-Service Routing with Inaccurate Link-State Information. Proc.OPENSIG Fall'97 Workshop, Columbia University, October 1997.
[46] Qingrning Ma, Peter Steenkiste. On Path Selection for Traffic with Bandwidth Guarantees. In the Proceedings of IEEE International Conference on Network Protocols, Atlanta, Georgia,. October 1997. pp. 153-179.
[47] Srihari Nelalmditi, Rose P.Tsang, Zhi-Li Zhang, Quality. -of-Service Routing without Global Information Exchange, In Proc. IFTP International Workshop on Quality-of-Service (IWQoS'99), London, UK. June 1999, pp. 129-131.
[48] Xin Yuan, Wei Zheng. A Comparative Study of Quality of Service Routing Schemes That Tolerate Imprecise State Information. Florida State University, Technical Report TR-010704, http://websrv.cs.fsu.edu/research/reports. 2002.
[49] Yanxia Jia, Ioanis Nikoladis, Pawel Oburzynski. Multiple Path QoS Routing. IEEE International Conference on Communications. Burbank, California, 2001, pp. 2583-2587.
[50] I.Cidon, R.Rom, Y.Shawitt. Analysis of Multi-path Routing. IEEE Transaction on Networking, 1999, 7: 885-896.
[51] Y.Jia, Y.Nikolaidis, P. Gburzynsld. Multiple Path Routing in Networks with Inaccurate Link State Infonnation. IEEE International Conference on Communications(ICC'2001), Helslnki, Finland, June 2001.
[52] 张保贤，刘越，陈长嘉．QoS路由的多路径算法．电子学报，2000．28(7)：120-122．
[53] 崔勇，吴建平，徐恪，徐明伟．互联网络服务质量路由算法研究综述．软件学报．2002，13(4)：10-21．
[54] 王建新，陈松乔，陈建二，王伟平．基于QoS的随机源选路由算法研究．小型微型计算机系统，2001，22(8)：917-920．
[55] 冯径，顾冠群．基于不确定参数的QoS路由研究．计算机研究与发展，2002，39(5)：533-539．
[56] 石坚，赵硕生．基于非精确状态的动态组播QoS路由算法．华中科技大学学报，2001．29(6)：22-24．
[57] Zhu Huiling, Ma Zhengxin, Wang Yongqian, Cao Zhigang. Improving QoS routing with multi-path scheme under inaccurate link state information. The International Conference on Fundamentals of Electronics, Communications and Computer Sciences. Tokyo, Japan, 2002. pp. 67-82.
[58] G.Apostolopoulos, R.Guerin, S.Kamat, S.Tripathi. Improving QoS Routing Performance Under Inaccurate Link State Information. Proceedings of the 16th International Teletraffic Congress, Edinburgh. UK. June 7-11. 1999. pp.
1351-1362.
[59] S.Chen, K.Nahrstedt. An Overview of Quality-of-Service Routing for the Next Generation High-Speed Networks: Problems and Solutions. IEEE Networks, Nov/Dec 1998.12(6): 64-79.
[60] P.E. Boyer, D. P. Trachier. A reservation principle with applications to the ATM traffic control. Computer Networks and ISDN Systems. 1992, 24(4): 321-334.
[61] Y. Shavitt. Burst Control in high-Speed Network. PHD thesis. Technion-Israel Institute of Technology, Electrical Engineering Dept., Technion City, Haifa 32000, Israel, June 1996.
[62] J.S. Turner. Managing bandwidth in ATM networks with burtsy traffic. IEEE Network, September 1992, 6(5): 50-58.
[63] R.Widyono. The Design and Evaluation of Routing Algorithms for Real-time Channels. Technical Report ICSI TR-94-024, International Computer Science Institute, UC Berkeley, June 1994.
[64] X.Yuan. On the extended Bellman-Ford algorithm to solve two—constrained quality of service muting problems. Proceedings of the Eighth International Conference on Computer Communications and Networks(IC3N'99). Boston, Massachusetts:IEEE Communication Society, 1999, pp. 304-10.
[65] X.Yuan, X.Liu. Heuristic algorithms for multi-constrained quality of service routing. Proceedings of the IEEE INFOCOM'01. Piscataway, NJ: IEEE Communication Society, 2001, pp. 844 -853.
[66] 刘千里，汪泽焱，倪明放．一种基于多条件约束的QoS路由选择优化算法[J]．计算机研究与发展，2001，38(3)：275-278．
[67] 汪泽焱．一种基于多目标优化的Q O S路由交互式算法[J]．国防科技大学学报．2002．24(4)：37-41．
[68] The Network Simulator- ns-2. http://www.isi.edu/nsnam/ns/, 2001-06-04.