Internet QoS路由研究
摘要
随着计算机技术和通信技术的飞速发展，Internet以其便捷、价廉的优势，吸引着越来越多的用户和新业务加入其中，目前网络承载的业务包括数据、语音、视频等多种业务，为实现多种业务共存，多种应用共存，服务质量(QoS)控制机制是必需的。Internet已逐步由单一的数据传输网向多媒体综合传输网演进。但目前Internet中的传输模式“尽力而为”(Best-Effort)服务，无法满足多媒体应用和各种用户对网络传输质量的要求。因此，以提高网络资源利用效率、为用户提供高质量服务作为目标的QoS(Quality of Service)研究是当前Internet领域的热点之一。因为路由直接关系到网络的性能，所以搜索满足约束并优化网络资源利用的QoS路由是全网和局部网络的QoS控制的核心问题之一。本文重点研究了目前QoS路由研究中的几个热点难点问题，具有重要的理论意义和使用价值。本文的主要工作如下：
(1)本文研究了QoS路由的一个重要问题---多约束最优路径问题(Multi-constrained Optimal Path，MCOP)。多约束最优路径问题，又称多约束最小代价路径问题，是QoS路由中一个很重要的问题，它涉及网络使用的计费，用户的付费，网络的优化等。本文提出了新的多约束最优路径选择算法---LBPSA(Lagrange Branch-and-Bound Path Selection Algorithm)，LBPSA利用拉格朗日松弛搜索出多约束最小代价路径的上界和下界，然后使用分枝界定反向搜索，得到多约束最小代价路径的成功率更高，而且复杂度相对较低。为提高搜索的成功率，本文提出了一种新的拉格朗日乘子在网络结构中的迭代方法，并利用拉格朗日乘子迭代的结果和属性确定了多约束最小代价QoS路径的边界，提出了反向分枝界定搜索方法以得到多约束最小代价QoS路径。实验结果表明LBPSA在搜索多约束最小代价路径的成功率比目前公认性能较好的H_MCOP算法更有效，而且算法复杂度也较低。
(2)本文研究了目前QoS路由的一个难点问题----多业务流共存的问题。本文从路由的角度提出了一种新的算法——综合度量路由算法，该算法在保证QoS流的延迟、带宽要求和“尽力而为”流的带宽要求同时，合理选择路由，利用资源，在相同条件下，比现有的最短路径路由算法能容纳更多的QoS流，而且不会消耗过多的网络带宽资源。
(3)在现有的基于探测法的分布式QoS路由算法的基础上，本文充分利用了探测法分布式的特点，借鉴蚂蚁路由算法的思想提出了一个基于探测法的QoS路由算法
一MLP以(Multi一p毗Limited Prob访g助uting Algorithm)。在MLpRA中，本文提出最
短路径优先探测的方法减少探测包的发送，同时提出“待完成路径”的思想搜索出更多
的可行路径。在返回包返回的过程中提出在中间节点保留路径选择“痕迹”的方法，同
时也记录其他请求留下的“痕迹”，通过分析比较选择最优路径，减少拥塞和流量溢出。
Following the fast growth of the Internet in recent years, more and more multimedia application carry out in the Internet. Future networks are expected to support various applications, specially multimedia application such as VoIP, VoD. To satisfy different QoS (Quality-of-Service) requirements, some mechanisms need to be employed. But because the Internet nowadays based on IPv4 only provides the best-effort service, and no QoS guarantees provided. QoS guarantee for the next-generation Internet is a challenging problem, and QoS guarantee is also a hot-topic in Internet research. Among QoS guarantee mechanism, QoS routing is one of the key issues. QoS routing has two objectives: (1) find a feasible path for QoS traffic to provide the QoS guarantee; (2) maximizing the utilization of the whole network.
In this thesis, we research some problems in QoS routing. The main contributions of this thesis are as follows:
(1) To obtain multi-constrained QoS path with minimal cost, a least-cost QoS path selection algorithm-LBPSA(Lagrange Branch-and-Bound Path Selection Algorithm) is presented. This algorithm uses Lagrangian relaxation to obtain the lower bound and the upper bound of the least cost of multi-constrained QoS path. And finds the multi-constrained QoS path with least cost by branch-and-bound method. In solving the Lagrangian multiplier problem, it introduced a new iteration method. Through recursion from destination to source based on branch-and-bound scheme, the least-cost multi-constrained path is obtained. The proposed algorithm has a pseudo polynomial running time. The simulation shows that the algorithm can find the path with high success ratio and low complexity. The success ratio is higher than the H_MCOP that is the main algorithm of MCOP.
(2) The second objective of QoS routing is maximizing the utilization of the networks. To QoS traffic, it means that the networks admit more QoS flows that have different QoS requests, including best-effort flows. It is multiple flows coexistence problem. We propose a novel method to this problem- the synthesis metrics routing algorithm (SMRA). SMRA synthesize the QoS delay constrain and the bandwidth request of the QoS flow to form the metrics. Based on the synthesis metrics, SMRA use the shortest path algorithm to search path
for the QoS flows and best-effort flows. The simulation shows that the networks with SMRA can admit more QoS flows that have different delay request. And the load of the whole networks increase very little.
(3) The probing method is a good distributed QoS routing. We propose a new routing algorithm based on probing- MLPRA(Multi-path Limited Probing Routing Algorithm). In MLPRA, we propose two methods- shortest path first probing and saving incomplete path, to search more feasible QoS paths by using limited probing. In the acknowledge procedure, the ack deposit the "pheromone" and get the "pheromone" deposited by the other acks. In simulation, MLPRA can search more feasible paths than DRA, the other probing QoS routing algorithm, and use little probing packets. Through "pheromone'", the congestion probability of MLPRA is little than widest-shortest routing algorithm and shortest-widest routing algorithm.
(1)本文研究了QoS路由的一个重要问题---多约束最优路径问题(Multi-constrained Optimal Path，MCOP)。多约束最优路径问题，又称多约束最小代价路径问题，是QoS路由中一个很重要的问题，它涉及网络使用的计费，用户的付费，网络的优化等。本文提出了新的多约束最优路径选择算法---LBPSA(Lagrange Branch-and-Bound Path Selection Algorithm)，LBPSA利用拉格朗日松弛搜索出多约束最小代价路径的上界和下界，然后使用分枝界定反向搜索，得到多约束最小代价路径的成功率更高，而且复杂度相对较低。为提高搜索的成功率，本文提出了一种新的拉格朗日乘子在网络结构中的迭代方法，并利用拉格朗日乘子迭代的结果和属性确定了多约束最小代价QoS路径的边界，提出了反向分枝界定搜索方法以得到多约束最小代价QoS路径。实验结果表明LBPSA在搜索多约束最小代价路径的成功率比目前公认性能较好的H_MCOP算法更有效，而且算法复杂度也较低。
(2)本文研究了目前QoS路由的一个难点问题----多业务流共存的问题。本文从路由的角度提出了一种新的算法——综合度量路由算法，该算法在保证QoS流的延迟、带宽要求和“尽力而为”流的带宽要求同时，合理选择路由，利用资源，在相同条件下，比现有的最短路径路由算法能容纳更多的QoS流，而且不会消耗过多的网络带宽资源。
(3)在现有的基于探测法的分布式QoS路由算法的基础上，本文充分利用了探测法分布式的特点，借鉴蚂蚁路由算法的思想提出了一个基于探测法的QoS路由算法
一MLP以(Multi一p毗Limited Prob访g助uting Algorithm)。在MLpRA中，本文提出最
短路径优先探测的方法减少探测包的发送，同时提出“待完成路径”的思想搜索出更多
的可行路径。在返回包返回的过程中提出在中间节点保留路径选择“痕迹”的方法，同
时也记录其他请求留下的“痕迹”，通过分析比较选择最优路径，减少拥塞和流量溢出。
Following the fast growth of the Internet in recent years, more and more multimedia application carry out in the Internet. Future networks are expected to support various applications, specially multimedia application such as VoIP, VoD. To satisfy different QoS (Quality-of-Service) requirements, some mechanisms need to be employed. But because the Internet nowadays based on IPv4 only provides the best-effort service, and no QoS guarantees provided. QoS guarantee for the next-generation Internet is a challenging problem, and QoS guarantee is also a hot-topic in Internet research. Among QoS guarantee mechanism, QoS routing is one of the key issues. QoS routing has two objectives: (1) find a feasible path for QoS traffic to provide the QoS guarantee; (2) maximizing the utilization of the whole network.
In this thesis, we research some problems in QoS routing. The main contributions of this thesis are as follows:
(1) To obtain multi-constrained QoS path with minimal cost, a least-cost QoS path selection algorithm-LBPSA(Lagrange Branch-and-Bound Path Selection Algorithm) is presented. This algorithm uses Lagrangian relaxation to obtain the lower bound and the upper bound of the least cost of multi-constrained QoS path. And finds the multi-constrained QoS path with least cost by branch-and-bound method. In solving the Lagrangian multiplier problem, it introduced a new iteration method. Through recursion from destination to source based on branch-and-bound scheme, the least-cost multi-constrained path is obtained. The proposed algorithm has a pseudo polynomial running time. The simulation shows that the algorithm can find the path with high success ratio and low complexity. The success ratio is higher than the H_MCOP that is the main algorithm of MCOP.
(2) The second objective of QoS routing is maximizing the utilization of the networks. To QoS traffic, it means that the networks admit more QoS flows that have different QoS requests, including best-effort flows. It is multiple flows coexistence problem. We propose a novel method to this problem- the synthesis metrics routing algorithm (SMRA). SMRA synthesize the QoS delay constrain and the bandwidth request of the QoS flow to form the metrics. Based on the synthesis metrics, SMRA use the shortest path algorithm to search path
for the QoS flows and best-effort flows. The simulation shows that the networks with SMRA can admit more QoS flows that have different delay request. And the load of the whole networks increase very little.
(3) The probing method is a good distributed QoS routing. We propose a new routing algorithm based on probing- MLPRA(Multi-path Limited Probing Routing Algorithm). In MLPRA, we propose two methods- shortest path first probing and saving incomplete path, to search more feasible QoS paths by using limited probing. In the acknowledge procedure, the ack deposit the "pheromone" and get the "pheromone" deposited by the other acks. In simulation, MLPRA can search more feasible paths than DRA, the other probing QoS routing algorithm, and use little probing packets. Through "pheromone'", the congestion probability of MLPRA is little than widest-shortest routing algorithm and shortest-widest routing algorithm.
引文
[1]K. Egevang, P. Francis. The IP Network Address Translator (NAT). RFC 1631, 1994.
[2]R. Bradert, D. Clark, and S. Shenker. Integrated services in the Interact Architecture: An overview. Rfc 1633, 1994
[3]S. Blake et al. An architecture for differentiated services. RFC 2475, 1998.
[4]J.Y Le Boudec and P. Thiran. Network Calculus. Springer Verlag Lecture Notes in Computer Science volume 2050.
[5]A.K.Parekh and R.G.Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single node case. IEEE/ACM Transactions on Networking. June,1993 Vol. 2, No 3, pp: 344-357.
[6]A.K.Parekh and R.G.Gallager. A generalized processor sharing approach to flow control in integrated services networks: The multiple node case. IEEE/ACM Transaction on Networking. Apr,1994 vol. 2, No 2, pp: 137-150.
[7]Floyd S, Jacobson V. Random early detection gateways for congestion avoidance. IEEE/ACM Transaction on Networking. 1998, vol. 1 No.4, pp:397-413
[8]E.Rosen, A. Viswanathan and R. Callon. Multiprotocol Label Switching Architecture. RFC 3031, Jan. 2001
[9]P.E.Boyer, M.J.Servel. The spacer-controller: An efficient upc/npc for ATM networks. In Proceedings of International Switching Symposium, 1992.
[10]H.Zhang. Service disciplines for guaranteed performance service in packet switching networks. Proceeding of the IEEE, Oct. 1995, vol.83, No. 10, pp: 1374-1396.
[11]Braden, B., Clark, D., Crowcroft, J, et al. Recommendations on Queue Management and Congestion Avoidance in the Interact. RFC 2309, 1994.
[12]Z.Wang. Interact QoS: Architecture and Mechanisms for Quality of Service. Morgan Kaufmann, 2001.
[13]ISO, "Quality of Service Framework", ISO/lEC JTC1/SC21/WG1 N9680,International Standards Organisation, UK, 1995.
[14]ISO, "QoS-Methods and Mechanism", ISO/IEC JTC1/SC21/WG1 N9310,International
Standards Organisation, UK, 1995.
[15]S.Shenker, C.Partridge, and R.Guerin. Specification of Guaranteed quality of service. RFC 2212, 1997.
[16]Wright Gray R., W. Richard Steven. TCP/IP Illustrated, Volume Ⅰ : The protocol, Jan 1995, Addison Wesley.
[17]J.Wroclawski. Specification of the Controlled-Load Network Element Service.. RFC 2211, 1997.
[18]R. Braden, L.Zhang, S. Berson et al. Resource ReSerVation Protocol(RSVP)-Version 1 Functional Specification, RFC 2205,1997.9
[19]Zhang. L, Deering. S, Estrin D, et al. RSVP: A New Resource ReSerVation Protocol, IEEE Network Magzine, September 1993, vol.7, No.5, pp: 116-127.
[20]Z.Wang and J.Crowcroft. QoS Routing for Supporting Resource Reservation, IEEE JSAC, September 1996, vol. 14,No.7, pp: 1228-1234,
[21]Moy J. OSPF Version 2. RFC 2328, April 1998.
[22]G.Malkin. RIP Version 2. RFC 2453, 1998.
[23]Crawley. E, Nair. R, Rajagopalan. B et al. A framework for QoS-based routing in the Internet. RFC 2386, 1998.
[24]Yuan X. On the extended Bellman-Ford algorithm to solve two-constrained quality of service routing problems. In: Park E, ed. Proceedings of the 8th International Conference on Computer Communications and Networks (IC3N'99). Boston, MA: IEEE Communication Society, 1999. pp:304-310.
[25]Yuan x, Liu X. Heuristic algorithms for multi-constrained quality-of-service routing. In : Sengupta B, ed. Proceedings of the IEEE INFOCOM 2001. Piscataway, NJ: IEEE Communication Society, 2001. pp:844-853.
[26]Chen S, Nahrstedt K. On finding multi-constrained paths. In : Goldston R, ed. Proceedings of the IEEE International Conference on Communications(ICC' 98). Atlanta: IEEE Communication Society, 1998. pp:874-879
[27]J. Bennett, H. Zhang. Hierarchical Packet Fair Queueing Algorithms. IEEE/ACM Transactions on Networking, Oct 1997, vol.5, No.5, pp:675-689.
[28]Demers, S. Keshav, S. Shenker. Analysis and Simulation of A Fair Queueing Algorithm.
Transactions on Networking, Oct 1997, vol.5, No.5, pp:675-689.
[28]Demers, S. Keshav, S. Shenker. Analysis and Simulation of A Fair Queueing Algorithm. In Proceedings ofACM SIGCOMM, 1989, vol 19. No. 4
[29]S. Golestani, A Self-Clocked Fair Queueing Scheme for Broadband Applications. In Proceedings of IEEE INFOCOM, June 1994, pp:636-646.
[30]Q. Ma, P. Steenkiste. Quality-of-Service Routing with Performance Guarantees. In Proceedings of 4th International IFIP Workshop on Quality of Service , May 1997, pp: 115-126.
[31]H. De Neve and P. Van Mieghem. TAMCRA: A Tunable Accuracy Multiple Constraints Routing Algorithm, Computer Communications,2000, vol. 23, pp. 667-679.
[32]H. De Neve and P. Van Mieghem, A multiple quality of service routing algorithm for PNNI, IEEE ATM Workshop, Fairfax, May 26-29, 1998, pp. 324-328.
[33]T. Korkmaz, M. Krunz, Multi-Constrained Optimal Path Selection. In Proceedings of IEEE INFOCOM, 2001, pp:834-843.
[34]Cidon I, Rom R, Shavitt Y. Multi-Path routing combined with resource reservation. In : Hasegawa T. ed. Proceedings of the IEEE INFOCOM'97. Kobe: IEEE Communication Society, 1997. pp:92-100.
[35]Norden. Improving Network Performance Using QoS Routing and Deferred Reservations. Doctoral Dissertation, Washington University Computer Science Department. 8/2002.
[36]Shin K G. Chou C. A distributed route-selection scheme for establishing real-time channel. In : Puigjaner R ed. Proceedings of IFIP the 6th International Conference on High Performance Networking. Palma: Chapman & Hall, 1995. pp:319-329.
[37]Chen S, Nahrstedt K . Distributed quality-of-service routing in high-speed networks based on selective probing. In: Nolley E, ed. Proceedings of LCN'98, Boston, MA: IEEE Communication Society, 1998, pp:80-89.
[38]Chen S, Nahrstedt K .Distributed QoS routing with imprecise state information. In: Pressley A ed. Proceedings of the 7th International Conference on Computer Communications and Networks (IC3N'98) IEEE Communication Society, 1998. pp:614-621.
[39]Z. Wang, J. Crowcroft. QoS routing for Supporting Multimedia Applications. IEEE Journal on Selected Areas in Communications, vol. 14, NO.7, September 1996, pp: 1228-1234.
[40]Claudio Casetti, Renato Lo Cigno. A New Class of QoS Routing Strategies Based on Network Graph Reduction. Computer Networks, 2003, vol. 41, No. 4, pp: 475-487.
[41]G.Liu and K.G.Ramakrishnan. A*Prune: An Algorithn for Finding k Shortest Paths Subject to Multiple Constraints. Proceeding of INFOCOM 2001,Anchorage, Ak, Apr. 2001, IEEE, pp:743-749.
[42]R. Guerin and A. Orda. QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms. IEEE/ACM Transactions on Networking, 1999, vol.7, No.3, pp:350-364.
[43]D. Lorenz, H.Orda. Efficient QoS partition and routing of unicast and multicast. In: Steenkiste. P. ed. Proceedings of International Workshop on Quality of Service. Pittsburgh: IEEE Communications Society. 2000. pp:75-83.
[44]G. Apostolopoulos, R. Guerin, S. Kamat, S. Tripathi. Quality of Service based routing: A performance perspective. Proceedings of ACM SIGCOMM. Vancouver, Canada: ACM, 1998, pp: 17-28.
[45]Funda Ergun, Rakesh Sinha, Lisa Zhang. QoS Routing with Performance-Dependent Costs. In Proceedings of IEEE INFOCOM. March 1999, pp: 137-146.
[46]Raz D, Shavitt Y. Optimal partition of QoS requirements with discrete cost function. In : Sidi M ed. Proceedings of the IEEE INFOCOM 2000. IEEE Communication Society, 2000, pp:613-622.
[47]徐恪，吴建平．高等计算机网络—体系结构、协议机制、算法设计与路由器技术．机械工业出版社，2003．
[48]H.F.Salama, D.S.Reeves,and Y.Viniotis.A Distributed Algorithm for Delay-Constrained Unicast Routing. Proceeding of INFOCOM, Japan, April 1997,pp: 239 - 250
[49]Q. Sun and H. Langendorfer. A New Distributed Routing Algorithm with End-to-End Delay Guarantee.2nd, Workshop, Protocols Multimedia Systems, Oct,1995, pp:452-458.
[50]Z. Wang and J. Crowcrofl. QoS Routing for Supporting Resource Reservation. JSAC, vol.14(7), September 1996, pp.1228-1234.
[52]F. Kuipers, P.V.Mieghem, T. Korkmaz, M. Krunz. An Overview of Constraint-Based Path Selection Algorithms for QoS Routing. IEEE Communications Magazine, 2002 Dec. vol. 40, No.12, pp:50-55.
[53]Shigang Chen, Klara Nahrstedt. An overview of quality-of-service routing for the next generation high-speed networks: problems and solutions. IEEE Network Magazine, 1998, vol. 12, No.6, pp: 64-79.
[54]M.R.Garey and D.S.Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, 1979.
[55]D.H. Lorenz and A.Orda. QoS routing in networks with uncertain parameters. IEEE/ACM Transactions on Networking, vol.6, No.6, December 1998, pp:768-778.
[56]R. Hassin. Approximation Schemes for the Restricted Shortest Path Problem. Mathematics of Operations Research archive Volume 17, Issue 1 (February 1992). Pages: 36-42.
[57]Juttner. A. Szviatovski, Mecs, B.I. et al. Lagrange relaxation based method for the QoS routing problem. Proceedings of the IEEE INFOCOM 2001. IEEE Communication Society, 2001. pp:859-868.
[58]L.Guo and I. Matta. Search Space Reduction in QoS Routing. Proc. 19th IEEE International Conference on Distributed Computing Systems May 31-June 04, 1999 Austin, Texas. pp: 142-149.
[59]P. Van Mieghem, H. De Neve and F.A. Kuipers, Hop-by-hop quality of service routing, Computer Networks, October 2001, vol. 37, no. 3-4, pp. 407-423.
[60]J.M.Jaffe. Algorithms for Finding Paths with Multiple Constraints. IEEE Networks, vol. 14, 1984, pp. 95-116.
[61]F.A. Kuipers and P. Van Mieghem.The Impact of Correlated Link Weights on QoS Routing. Proceeding of IEEE INFOCOM 2003, San Francisco, USA, March 30 -April 3, 2003.
[62]P. Van Mieghem and F. A. Kuipers .Concepts of Exact QoS Routing Algorithms. to appear in IEEE/ACM Transaction on Networking
[63]Pragyansmita Paul and SV Raghavan. Survey of QoS routing. Proceedings of the 15th international conference on Computer communication. Maharashtra, India. 2002,
[63]Pragyansmita Paul and SV Raghavan. Survey of QoS routing. Proceedings of the 15th international conference on Computer communication. Maharashtra, India. 2002, pp: 50 - 75.
[64]R J Sinavasankar, S Ramamz et al. Some studies on the impact of dynarnic traffic in a QoS-based dynamic routing environment. ICC'2000. New Orleans, USA: ICC, 2000, pp:959-963.
[65]Ying Xu and Roch Guerin. Individual QoS versus Aggregate QoS: A Loss Performance Study. Proceeding of INFOCOM, 2002, vol.3, pp:1170-1179.
[66]Stephen L. Spitler and Daniel C. Lee. Integrating Effective-Bandwidth-Based QoS Routing and Best Effort Routing. Proceedings of IEEE INFOCOM, San Francisco, CA, April 2003
[67]Shigang Chen. Coexistence QoS and best-effort flows-routing and schedule. In Proceedings of 10th IEEE Tyrrhenian International Workshop on Digital Communications: Multimedia Communications, Ischia, Italy, September 1998. pp.33-36.
[68]QingmingMa, Peter Steenkiste. Supporting Dynamic InterClass Resource Sharing: A MultiClass QoS Routing Algorithm. In Proceeding of IEEE INFOCOM, 1999, pp:649-660.
[69]Guerin R, Orda A. Networks with advance reservations: the routing perspective. In : Sidi M ed. Proceedings of the IEEE INFOCOM 2000. IEEE Communication Society, 2000, pp: 118-127.
[70]S Siachalou, L Georgiadis. Efficient QoS Routing. Proceeding of INFOCOM 2003, San Francisco, MA: IEEE Communication Society, 2003, pp:938～947.
[71]K. Ahuja, L. Magnanti. Network Flows: Theory, Algorithms, and Applications[B]. Prentice Hall, Upper Saddle River, New Jersey, 1993.
[72]Thomas H, Cormen Charles E, Leiserson Ronald L, et al. Introduction to Algorithms. MIT Press, 2001.
[73]H. Lorenz and Ariel Orda. Optimal Partition of QoS Requirements on Unieast Paths and Multicast Trees. In Proceedings of IEEE INFOCOM, March 1999. pp: 246--253
[74]Ellen W. Zegura, Ken Calvert and S. Bhattacharjee. How to Model an Internetwork. Proceedings of IEEE Infocom '96, San Francisco, CA.
[75]Ken Calvert, Matt Doar and Ellen W. Zegura. Modeling lnternet Topology. IEEE Communications Magazine, June 1997.
[76]Ellen W. Zegura, Kenneth Calvert and M. Jeff Donahoo. A Quantitative Comparison of Graph-based Models for Interact Topology. IEEE/ACM Transactions on Networking ,, 1997, Volume 5, Issue 6,pp: 770- 783.
[77]Anindya Basu, Alvin Lin, Sharad Ramanathan. Routing Using Potentials:A Dynamic Traffic-Aware Routing Algorithm. Proceedings ofACM SIGCOMM 2003, Karlsruhe, Germany, August 2003, pp:37-48.
[78]T Ibaraki, N Katoh. Resource Allocation Problem: The Foundations of Computing. Cambridge, MA: MIT Press, 1988.
[79]D. Bertsekas, R. Gallager, Data Networks, PrenticeHall, 2nd ed., 1992.
[80]Shigang Chen. Routing Support for Providing Guaranteed End-To-End Quality-Of-Service. PhD thesis. University of Illinois Computer Science Department. 1999
[81]Kihong Park, Walter Willinger. Self-similar network traffic and performance evaluation. Published by wiley Inter-science.2001
[82]Leonard Kleinrock. Queueing Systems. Wiley-Interscience Publication. Canada, 1975.
[83]B. Fortz and M. Thorup.Intemet Traffic Engineering by optimizing OSPF weights. In Proceeding of 19th IEEE INFOCOM, 2000, pp. 519-528.
[84]Jacobson, V. Congestion avoidance and control. ACM Computer Communication Review, 1988, vol.18, No.4, pp:314～329.
[85]D. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, Belmont, MA, 1995
[86]R. Bellman. On a routing problem. Quartely of Applied Mathematics, 16(1):87-90, 1958.
[87]E.W.Dijkstra. A note on two problems in connection with graphs. Numerical Mathematics, 1959, pp: 269-271.
[88]L. K. Fleischer. Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York, NY, October 1999, pp: 24-31.
[89]N. Garg and J. Konemann. Faster and Simpler Algorithms for Multicommodity
Flow and Other Fractional Packing Problems. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, November 1998, pp: 300-309.
[90]J. Behrems and J. Garcia-Luna-Aceves. Distributed, Scalable routing based on link-state vectors. SIGCOMM, August 1994, pp: 136-147.
[91]Qingming Ma. Peter Steenkiste. On Path Selection for Traffic with Bandwidth Guarantees. Proceedings of IEEE International Conference on Network Protocols,1997, Atlanta, GA, pp: 191-202.
[92]M.Dorigo and L.M.Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, vol. 1, No. 1, 1997,pp:53-66.
[93]G.Di Caro and M.Dorigo. Ant colonies for adaptive routing in packet-switched communication networks. In Springer-Verlag, editor, PPSN V-Fifth International Conference on Parallel Problem Solving From Nature, 1998, pp:673-682.
[94]Goss.S, Aron.S, Deneubourg.J. Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 1976, pp:579-581.
[95]The Network Simulator—ns-2. http://www.isi.edu/nsnam/ns/.
[2]R. Bradert, D. Clark, and S. Shenker. Integrated services in the Interact Architecture: An overview. Rfc 1633, 1994
[3]S. Blake et al. An architecture for differentiated services. RFC 2475, 1998.
[4]J.Y Le Boudec and P. Thiran. Network Calculus. Springer Verlag Lecture Notes in Computer Science volume 2050.
[5]A.K.Parekh and R.G.Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single node case. IEEE/ACM Transactions on Networking. June,1993 Vol. 2, No 3, pp: 344-357.
[6]A.K.Parekh and R.G.Gallager. A generalized processor sharing approach to flow control in integrated services networks: The multiple node case. IEEE/ACM Transaction on Networking. Apr,1994 vol. 2, No 2, pp: 137-150.
[7]Floyd S, Jacobson V. Random early detection gateways for congestion avoidance. IEEE/ACM Transaction on Networking. 1998, vol. 1 No.4, pp:397-413
[8]E.Rosen, A. Viswanathan and R. Callon. Multiprotocol Label Switching Architecture. RFC 3031, Jan. 2001
[9]P.E.Boyer, M.J.Servel. The spacer-controller: An efficient upc/npc for ATM networks. In Proceedings of International Switching Symposium, 1992.
[10]H.Zhang. Service disciplines for guaranteed performance service in packet switching networks. Proceeding of the IEEE, Oct. 1995, vol.83, No. 10, pp: 1374-1396.
[11]Braden, B., Clark, D., Crowcroft, J, et al. Recommendations on Queue Management and Congestion Avoidance in the Interact. RFC 2309, 1994.
[12]Z.Wang. Interact QoS: Architecture and Mechanisms for Quality of Service. Morgan Kaufmann, 2001.
[13]ISO, "Quality of Service Framework", ISO/lEC JTC1/SC21/WG1 N9680,International Standards Organisation, UK, 1995.
[14]ISO, "QoS-Methods and Mechanism", ISO/IEC JTC1/SC21/WG1 N9310,International
Standards Organisation, UK, 1995.
[15]S.Shenker, C.Partridge, and R.Guerin. Specification of Guaranteed quality of service. RFC 2212, 1997.
[16]Wright Gray R., W. Richard Steven. TCP/IP Illustrated, Volume Ⅰ : The protocol, Jan 1995, Addison Wesley.
[17]J.Wroclawski. Specification of the Controlled-Load Network Element Service.. RFC 2211, 1997.
[18]R. Braden, L.Zhang, S. Berson et al. Resource ReSerVation Protocol(RSVP)-Version 1 Functional Specification, RFC 2205,1997.9
[19]Zhang. L, Deering. S, Estrin D, et al. RSVP: A New Resource ReSerVation Protocol, IEEE Network Magzine, September 1993, vol.7, No.5, pp: 116-127.
[20]Z.Wang and J.Crowcroft. QoS Routing for Supporting Resource Reservation, IEEE JSAC, September 1996, vol. 14,No.7, pp: 1228-1234,
[21]Moy J. OSPF Version 2. RFC 2328, April 1998.
[22]G.Malkin. RIP Version 2. RFC 2453, 1998.
[23]Crawley. E, Nair. R, Rajagopalan. B et al. A framework for QoS-based routing in the Internet. RFC 2386, 1998.
[24]Yuan X. On the extended Bellman-Ford algorithm to solve two-constrained quality of service routing problems. In: Park E, ed. Proceedings of the 8th International Conference on Computer Communications and Networks (IC3N'99). Boston, MA: IEEE Communication Society, 1999. pp:304-310.
[25]Yuan x, Liu X. Heuristic algorithms for multi-constrained quality-of-service routing. In : Sengupta B, ed. Proceedings of the IEEE INFOCOM 2001. Piscataway, NJ: IEEE Communication Society, 2001. pp:844-853.
[26]Chen S, Nahrstedt K. On finding multi-constrained paths. In : Goldston R, ed. Proceedings of the IEEE International Conference on Communications(ICC' 98). Atlanta: IEEE Communication Society, 1998. pp:874-879
[27]J. Bennett, H. Zhang. Hierarchical Packet Fair Queueing Algorithms. IEEE/ACM Transactions on Networking, Oct 1997, vol.5, No.5, pp:675-689.
[28]Demers, S. Keshav, S. Shenker. Analysis and Simulation of A Fair Queueing Algorithm.
Transactions on Networking, Oct 1997, vol.5, No.5, pp:675-689.
[28]Demers, S. Keshav, S. Shenker. Analysis and Simulation of A Fair Queueing Algorithm. In Proceedings ofACM SIGCOMM, 1989, vol 19. No. 4
[29]S. Golestani, A Self-Clocked Fair Queueing Scheme for Broadband Applications. In Proceedings of IEEE INFOCOM, June 1994, pp:636-646.
[30]Q. Ma, P. Steenkiste. Quality-of-Service Routing with Performance Guarantees. In Proceedings of 4th International IFIP Workshop on Quality of Service , May 1997, pp: 115-126.
[31]H. De Neve and P. Van Mieghem. TAMCRA: A Tunable Accuracy Multiple Constraints Routing Algorithm, Computer Communications,2000, vol. 23, pp. 667-679.
[32]H. De Neve and P. Van Mieghem, A multiple quality of service routing algorithm for PNNI, IEEE ATM Workshop, Fairfax, May 26-29, 1998, pp. 324-328.
[33]T. Korkmaz, M. Krunz, Multi-Constrained Optimal Path Selection. In Proceedings of IEEE INFOCOM, 2001, pp:834-843.
[34]Cidon I, Rom R, Shavitt Y. Multi-Path routing combined with resource reservation. In : Hasegawa T. ed. Proceedings of the IEEE INFOCOM'97. Kobe: IEEE Communication Society, 1997. pp:92-100.
[35]Norden. Improving Network Performance Using QoS Routing and Deferred Reservations. Doctoral Dissertation, Washington University Computer Science Department. 8/2002.
[36]Shin K G. Chou C. A distributed route-selection scheme for establishing real-time channel. In : Puigjaner R ed. Proceedings of IFIP the 6th International Conference on High Performance Networking. Palma: Chapman & Hall, 1995. pp:319-329.
[37]Chen S, Nahrstedt K . Distributed quality-of-service routing in high-speed networks based on selective probing. In: Nolley E, ed. Proceedings of LCN'98, Boston, MA: IEEE Communication Society, 1998, pp:80-89.
[38]Chen S, Nahrstedt K .Distributed QoS routing with imprecise state information. In: Pressley A ed. Proceedings of the 7th International Conference on Computer Communications and Networks (IC3N'98) IEEE Communication Society, 1998. pp:614-621.
[39]Z. Wang, J. Crowcroft. QoS routing for Supporting Multimedia Applications. IEEE Journal on Selected Areas in Communications, vol. 14, NO.7, September 1996, pp: 1228-1234.
[40]Claudio Casetti, Renato Lo Cigno. A New Class of QoS Routing Strategies Based on Network Graph Reduction. Computer Networks, 2003, vol. 41, No. 4, pp: 475-487.
[41]G.Liu and K.G.Ramakrishnan. A*Prune: An Algorithn for Finding k Shortest Paths Subject to Multiple Constraints. Proceeding of INFOCOM 2001,Anchorage, Ak, Apr. 2001, IEEE, pp:743-749.
[42]R. Guerin and A. Orda. QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms. IEEE/ACM Transactions on Networking, 1999, vol.7, No.3, pp:350-364.
[43]D. Lorenz, H.Orda. Efficient QoS partition and routing of unicast and multicast. In: Steenkiste. P. ed. Proceedings of International Workshop on Quality of Service. Pittsburgh: IEEE Communications Society. 2000. pp:75-83.
[44]G. Apostolopoulos, R. Guerin, S. Kamat, S. Tripathi. Quality of Service based routing: A performance perspective. Proceedings of ACM SIGCOMM. Vancouver, Canada: ACM, 1998, pp: 17-28.
[45]Funda Ergun, Rakesh Sinha, Lisa Zhang. QoS Routing with Performance-Dependent Costs. In Proceedings of IEEE INFOCOM. March 1999, pp: 137-146.
[46]Raz D, Shavitt Y. Optimal partition of QoS requirements with discrete cost function. In : Sidi M ed. Proceedings of the IEEE INFOCOM 2000. IEEE Communication Society, 2000, pp:613-622.
[47]徐恪，吴建平．高等计算机网络—体系结构、协议机制、算法设计与路由器技术．机械工业出版社，2003．
[48]H.F.Salama, D.S.Reeves,and Y.Viniotis.A Distributed Algorithm for Delay-Constrained Unicast Routing. Proceeding of INFOCOM, Japan, April 1997,pp: 239 - 250
[49]Q. Sun and H. Langendorfer. A New Distributed Routing Algorithm with End-to-End Delay Guarantee.2nd, Workshop, Protocols Multimedia Systems, Oct,1995, pp:452-458.
[50]Z. Wang and J. Crowcrofl. QoS Routing for Supporting Resource Reservation. JSAC, vol.14(7), September 1996, pp.1228-1234.
[52]F. Kuipers, P.V.Mieghem, T. Korkmaz, M. Krunz. An Overview of Constraint-Based Path Selection Algorithms for QoS Routing. IEEE Communications Magazine, 2002 Dec. vol. 40, No.12, pp:50-55.
[53]Shigang Chen, Klara Nahrstedt. An overview of quality-of-service routing for the next generation high-speed networks: problems and solutions. IEEE Network Magazine, 1998, vol. 12, No.6, pp: 64-79.
[54]M.R.Garey and D.S.Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, 1979.
[55]D.H. Lorenz and A.Orda. QoS routing in networks with uncertain parameters. IEEE/ACM Transactions on Networking, vol.6, No.6, December 1998, pp:768-778.
[56]R. Hassin. Approximation Schemes for the Restricted Shortest Path Problem. Mathematics of Operations Research archive Volume 17, Issue 1 (February 1992). Pages: 36-42.
[57]Juttner. A. Szviatovski, Mecs, B.I. et al. Lagrange relaxation based method for the QoS routing problem. Proceedings of the IEEE INFOCOM 2001. IEEE Communication Society, 2001. pp:859-868.
[58]L.Guo and I. Matta. Search Space Reduction in QoS Routing. Proc. 19th IEEE International Conference on Distributed Computing Systems May 31-June 04, 1999 Austin, Texas. pp: 142-149.
[59]P. Van Mieghem, H. De Neve and F.A. Kuipers, Hop-by-hop quality of service routing, Computer Networks, October 2001, vol. 37, no. 3-4, pp. 407-423.
[60]J.M.Jaffe. Algorithms for Finding Paths with Multiple Constraints. IEEE Networks, vol. 14, 1984, pp. 95-116.
[61]F.A. Kuipers and P. Van Mieghem.The Impact of Correlated Link Weights on QoS Routing. Proceeding of IEEE INFOCOM 2003, San Francisco, USA, March 30 -April 3, 2003.
[62]P. Van Mieghem and F. A. Kuipers .Concepts of Exact QoS Routing Algorithms. to appear in IEEE/ACM Transaction on Networking
[63]Pragyansmita Paul and SV Raghavan. Survey of QoS routing. Proceedings of the 15th international conference on Computer communication. Maharashtra, India. 2002,
[63]Pragyansmita Paul and SV Raghavan. Survey of QoS routing. Proceedings of the 15th international conference on Computer communication. Maharashtra, India. 2002, pp: 50 - 75.
[64]R J Sinavasankar, S Ramamz et al. Some studies on the impact of dynarnic traffic in a QoS-based dynamic routing environment. ICC'2000. New Orleans, USA: ICC, 2000, pp:959-963.
[65]Ying Xu and Roch Guerin. Individual QoS versus Aggregate QoS: A Loss Performance Study. Proceeding of INFOCOM, 2002, vol.3, pp:1170-1179.
[66]Stephen L. Spitler and Daniel C. Lee. Integrating Effective-Bandwidth-Based QoS Routing and Best Effort Routing. Proceedings of IEEE INFOCOM, San Francisco, CA, April 2003
[67]Shigang Chen. Coexistence QoS and best-effort flows-routing and schedule. In Proceedings of 10th IEEE Tyrrhenian International Workshop on Digital Communications: Multimedia Communications, Ischia, Italy, September 1998. pp.33-36.
[68]QingmingMa, Peter Steenkiste. Supporting Dynamic InterClass Resource Sharing: A MultiClass QoS Routing Algorithm. In Proceeding of IEEE INFOCOM, 1999, pp:649-660.
[69]Guerin R, Orda A. Networks with advance reservations: the routing perspective. In : Sidi M ed. Proceedings of the IEEE INFOCOM 2000. IEEE Communication Society, 2000, pp: 118-127.
[70]S Siachalou, L Georgiadis. Efficient QoS Routing. Proceeding of INFOCOM 2003, San Francisco, MA: IEEE Communication Society, 2003, pp:938～947.
[71]K. Ahuja, L. Magnanti. Network Flows: Theory, Algorithms, and Applications[B]. Prentice Hall, Upper Saddle River, New Jersey, 1993.
[72]Thomas H, Cormen Charles E, Leiserson Ronald L, et al. Introduction to Algorithms. MIT Press, 2001.
[73]H. Lorenz and Ariel Orda. Optimal Partition of QoS Requirements on Unieast Paths and Multicast Trees. In Proceedings of IEEE INFOCOM, March 1999. pp: 246--253
[74]Ellen W. Zegura, Ken Calvert and S. Bhattacharjee. How to Model an Internetwork. Proceedings of IEEE Infocom '96, San Francisco, CA.
[75]Ken Calvert, Matt Doar and Ellen W. Zegura. Modeling lnternet Topology. IEEE Communications Magazine, June 1997.
[76]Ellen W. Zegura, Kenneth Calvert and M. Jeff Donahoo. A Quantitative Comparison of Graph-based Models for Interact Topology. IEEE/ACM Transactions on Networking ,, 1997, Volume 5, Issue 6,pp: 770- 783.
[77]Anindya Basu, Alvin Lin, Sharad Ramanathan. Routing Using Potentials:A Dynamic Traffic-Aware Routing Algorithm. Proceedings ofACM SIGCOMM 2003, Karlsruhe, Germany, August 2003, pp:37-48.
[78]T Ibaraki, N Katoh. Resource Allocation Problem: The Foundations of Computing. Cambridge, MA: MIT Press, 1988.
[79]D. Bertsekas, R. Gallager, Data Networks, PrenticeHall, 2nd ed., 1992.
[80]Shigang Chen. Routing Support for Providing Guaranteed End-To-End Quality-Of-Service. PhD thesis. University of Illinois Computer Science Department. 1999
[81]Kihong Park, Walter Willinger. Self-similar network traffic and performance evaluation. Published by wiley Inter-science.2001
[82]Leonard Kleinrock. Queueing Systems. Wiley-Interscience Publication. Canada, 1975.
[83]B. Fortz and M. Thorup.Intemet Traffic Engineering by optimizing OSPF weights. In Proceeding of 19th IEEE INFOCOM, 2000, pp. 519-528.
[84]Jacobson, V. Congestion avoidance and control. ACM Computer Communication Review, 1988, vol.18, No.4, pp:314～329.
[85]D. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, Belmont, MA, 1995
[86]R. Bellman. On a routing problem. Quartely of Applied Mathematics, 16(1):87-90, 1958.
[87]E.W.Dijkstra. A note on two problems in connection with graphs. Numerical Mathematics, 1959, pp: 269-271.
[88]L. K. Fleischer. Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York, NY, October 1999, pp: 24-31.
[89]N. Garg and J. Konemann. Faster and Simpler Algorithms for Multicommodity
Flow and Other Fractional Packing Problems. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, November 1998, pp: 300-309.
[90]J. Behrems and J. Garcia-Luna-Aceves. Distributed, Scalable routing based on link-state vectors. SIGCOMM, August 1994, pp: 136-147.
[91]Qingming Ma. Peter Steenkiste. On Path Selection for Traffic with Bandwidth Guarantees. Proceedings of IEEE International Conference on Network Protocols,1997, Atlanta, GA, pp: 191-202.
[92]M.Dorigo and L.M.Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, vol. 1, No. 1, 1997,pp:53-66.
[93]G.Di Caro and M.Dorigo. Ant colonies for adaptive routing in packet-switched communication networks. In Springer-Verlag, editor, PPSN V-Fifth International Conference on Parallel Problem Solving From Nature, 1998, pp:673-682.
[94]Goss.S, Aron.S, Deneubourg.J. Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 1976, pp:579-581.
[95]The Network Simulator—ns-2. http://www.isi.edu/nsnam/ns/.