基于模拟退火方法的QoS约束组播路由算法研究
|
摘要
随着网络技术的飞速发展,当前通信网络带宽和处理能力的提高使网络能够提供更多的多媒体业务,也使得支持“点到多点”或“多点到多点”的组播通信方式成为网络支持多媒体业务的必要形式。组播路由是网络层具备的功能,组播问题的关键在于组播路由的确定,寻找简单、高效、健壮的组播路由算法一直是网络界致力研究但未完全解决的问题。另一方面,许多分布式的多媒体应用对时延、时延抖动、带宽以及包丢失率有不同的要求,这需要当前网络能够传送具有这些QoS要求的实时多媒体信息。因此,作为QoS为中心的网络体系结构中不可缺少的组成部分,基于QoS约束的组播路由算法的研究成为网络研究领域的重要内容和热点问题。
本文主要研究基于QoS约束的组播路由算法,针对时延和时延抖动约束的最小代价组播路由问题,提出了一种有效、实用的组播路由算法。主要研究工作和取得的成果如下:
(1)在介绍组播路由技术背景知识的基础上,研究了QoS路由的网络模型和QoS度量的定义,重点对组播路由问题进行分类讨论,分析了QoS组播路由的特性,并归纳了相关算法的优缺点;
(2)将模拟退火的优化思想引入组播路由计算中,提出一种基于模拟退火方法的时延及时延抖动约束的最小代价组播路由算法。该算法采用“路径交换”策略在可行解范围内构造邻域集,避免了搜索区域的扩大和计算时间的增加。
(3)对提出的改进算法进行仿真,并与改进前进行比较,仿真结果表明算法的可行性、有效性和稳定性,并验证了算法具有代价低、收敛快的特点。
With fast development of network technologies,increase of network bandwidth and processing power makes the network provide more multimedia applications,and also makes the multicast communication that supports "one-to-many" or "many-to-many" become a necessary mode of multimedia services.A fundamental issue in multicast communication is how to determine an efficient multicast routing, and finding simple,effective and robust multicast routing algorithms.This is unsolved problem in network fields.In addition,many distributed multimedia applications have various demands on delay,delay variation,bandwidth and packet loss,which requires current network to transmit real-time multimedia information with these quality-of-service(QoS)constraints.So,as an indispensable component in a QoS-centric network architecture,research on multicast routing algorithms based on IP QoS constraint becomes an important part and hotspot issue of network research fields.
This paper researches the structure,typical service model and mechanism of QoS based on network,and introduces the key technology about it;then classifies the multicast routing algorithms with QoS constraints which have been put forward.By analyzing the simulated annealing algorithm and importing the conception of paths-switching,the paper presents a kind of improved simulated annealing algorithm: SAD_DVMA.The simulative result illustrates SAD_DVMA is better than traditional algorithm in solving the least cost multicast routing problem with delay and delay variation constraint.
Generally,the main achievements in this paper are as follows:
(1)Concentrates on researching multicast routing algorithms with QoS constraints,proposes several simple,effective and practical QoS multicast routing heuristic algorithm to solve some classical multicast routing problems with NP difficulty;
(2)Apply the simulated annealing to multicast routing,and propose a multicast routing algorithm(SAD_DVMA)based on simulated annealing to solve delay and delay variation constrained least-cost multicast routing problem.To avoid enlargement of search area and increase of computing time,SAD_DVMA uses "paths-switching" strategy,which constructs neighbor set in the range of feasible solutions according to the relationship between delay and delay variation;
(3)Simulations demonstrate that the algorithm has characteristics of feasibility, stability and rapid convergence,and it can effectively construct multicast tree with lower cost according to QoS request,and has better real-time property.
本文主要研究基于QoS约束的组播路由算法,针对时延和时延抖动约束的最小代价组播路由问题,提出了一种有效、实用的组播路由算法。主要研究工作和取得的成果如下:
(1)在介绍组播路由技术背景知识的基础上,研究了QoS路由的网络模型和QoS度量的定义,重点对组播路由问题进行分类讨论,分析了QoS组播路由的特性,并归纳了相关算法的优缺点;
(2)将模拟退火的优化思想引入组播路由计算中,提出一种基于模拟退火方法的时延及时延抖动约束的最小代价组播路由算法。该算法采用“路径交换”策略在可行解范围内构造邻域集,避免了搜索区域的扩大和计算时间的增加。
(3)对提出的改进算法进行仿真,并与改进前进行比较,仿真结果表明算法的可行性、有效性和稳定性,并验证了算法具有代价低、收敛快的特点。
With fast development of network technologies,increase of network bandwidth and processing power makes the network provide more multimedia applications,and also makes the multicast communication that supports "one-to-many" or "many-to-many" become a necessary mode of multimedia services.A fundamental issue in multicast communication is how to determine an efficient multicast routing, and finding simple,effective and robust multicast routing algorithms.This is unsolved problem in network fields.In addition,many distributed multimedia applications have various demands on delay,delay variation,bandwidth and packet loss,which requires current network to transmit real-time multimedia information with these quality-of-service(QoS)constraints.So,as an indispensable component in a QoS-centric network architecture,research on multicast routing algorithms based on IP QoS constraint becomes an important part and hotspot issue of network research fields.
This paper researches the structure,typical service model and mechanism of QoS based on network,and introduces the key technology about it;then classifies the multicast routing algorithms with QoS constraints which have been put forward.By analyzing the simulated annealing algorithm and importing the conception of paths-switching,the paper presents a kind of improved simulated annealing algorithm: SAD_DVMA.The simulative result illustrates SAD_DVMA is better than traditional algorithm in solving the least cost multicast routing problem with delay and delay variation constraint.
Generally,the main achievements in this paper are as follows:
(1)Concentrates on researching multicast routing algorithms with QoS constraints,proposes several simple,effective and practical QoS multicast routing heuristic algorithm to solve some classical multicast routing problems with NP difficulty;
(2)Apply the simulated annealing to multicast routing,and propose a multicast routing algorithm(SAD_DVMA)based on simulated annealing to solve delay and delay variation constrained least-cost multicast routing problem.To avoid enlargement of search area and increase of computing time,SAD_DVMA uses "paths-switching" strategy,which constructs neighbor set in the range of feasible solutions according to the relationship between delay and delay variation;
(3)Simulations demonstrate that the algorithm has characteristics of feasibility, stability and rapid convergence,and it can effectively construct multicast tree with lower cost according to QoS request,and has better real-time property.
引文
[1]Deering S.Multicast Routing in a Datagram Internetwork.PhD thesis,Stanford University,1991.
[2]Xipeng Xiao and M.Ni Lionel.Internet QoS:a big picture.IEEE Network,1999,13(2):8-18.
[3]Wang Z,Crowcroft J.Quality of Service for Supporting Multimedia Applications.IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234
[4]E.Rosen,A.Viswanathan,R.Callon.Multi Protocol Label Switching Architecture.IETF RFC3031,2001.
[5]R.Yavatkar,D.Hoffman,Y Bernet,F.Baker,M.Speer.SBM(Subnet Bandwidth Manager):A Protocol for RSVP-based Admission Control over IEEE 802-style networks.RFC 2814.May 2000
[6]林闯,单志广,任丰原.计算机网络的服务质量(QoS).第1版.北京:清华大学出版社,2004.
[7]R.Braden,L.Zhang,S.Berson et al.Resource RserVation Protocol(RSVP)(Version 1):Function Specification.IETF RFC 2205.September 1997.
[8]Debasish Chakraborty,Goutam Chakraborty,Norio Shiratori.A dynamic multicast routing satisfying multiple QoS constraints.International Journal of Network Management,2003,5:Volume 13.
[9]E.Rosen,A.Viswanathan,R.Callon.Multiprotocol Label Switching Architecture.IETF RFC3031,2001
[10]李斯伟,薛文安.实现Internet业务分类处理的DiffServ模型分析.通信技术,2001,(4):19-21.
[11]F.Baker,C.Iturralde,F.L.Faucheur,B.Davie.Aggregation of RSVP for IPv4 and IPv6Reservations.IETF Internet Draft,1999
[12]Wang B,Hou J C.Multicast Routing and Its QoS Extension:Problem,Algorithm,and Protocols.IEEE Network,2000,14(1):22-36.
[13]Wang Z,Crowcroft J.QoS Routing for Supporting Resource Reservation.IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234
[14]赵键,吴介一,罗军舟等.一类基于源路由的多约束实时组播路由优化控制算法.电子学报,2001,29(4):490-494.
[15]Kompella V P,Pasqual J C,Polyzos G C.Multicast routing for multimedia communication.IEEE/ACM Trans on Networking,1993,1(3):286-292.
[16]Kou L,Markowsky G,Berman L.A fast algorithm for Steiner trees in graphs.Acta Informatica,1981,15(2):141-145.
[17]Zhu Q,Parsa M,Garcia-Luna-Aceves J J.A source-based algorithm for delay-constrained minimum-cost multicasting.In:Proc of IEEE-INFOCOM 95,Boston,MA,1995:452-458.
[18]顾亦然,江平,王锁萍.一种新的QoS保证的快速组播路由算法.南京邮电学院学报,2003,23(1):6-12.
[19]石坚,董天临等.一种基于延时及带宽受限的启发式组播路由算法.电子学报,2001,29(8):1113-1116.
[20]George N et al.Multicast Routing with End-to-End Delay and Delay Variation Constraints.IEEE JSAC,1997,15(3):346-356.
[21]B K Haberman,G N Rouskas.Cost,Delay and Delay Variation Conscious Multicast Routing.Technical Report TR-97-03,North Carolina State University,1997.
[22]余燕平,仇佩亮.时延和时延抖动约束的低费用多播路由算法.电路与系统学报,2001,6(4):65-68.
[23]李腊元,李春林.多QoS约束的多播路由协议.软件学报,2004,15(2):286-291.
[24]孙宝林,李腊元.多约束QoS多播路由的模型和算法研究.计算机工程与应用,2003,(29):41-44.
[25]陆慧梅,向勇,史美林等.一种基于带宽和时延约束的分布式组播路由算法.电子学报,2002,30(12A):1978-1981.
[26]崔勇,吴建平,徐格等.互联网络服务质量路由算法研究综述.软件学报,2002,13(11):2065-2075.
[27]刘先锋,舒林,陈松乔等.基于QoS约束的多播路由研究[J].计算机工程与应用,2005,(29):125-129.
[28]Zhang B X,Mouftah H T.A Destination-Driven Shortest Path Tree Algorithm[A].In Proceedings of the IEEE International Conference on Communications 2002(ICC'2002).New York:IEEE Communication Society,2002,4:2258-2262.
[29]Lee H Y,Youn C H.Scalable Multicast Routing Algorithm for Delay-Variation Constrained Minimum-Cost Tree[A].In Proceedings of IEEE International Conference on Communications.2000,3:1343-1347.
[30]Zhang Q F.An Orthogonal Genetic Algorithm for Multimedia Multicast Routing.IEEE Transactions on Evolutionary Computation,1999,3(1):53-62.
[31]Lee H Y,Youn C H.Scalable Multicast Routing Algorithm for Delay-Variation Constrained Minimim-Cost Tree[A].In Proceeding of IEEE International Conference on Communications.2000,3:1343-1347.
[32]Low C P.Loop-free Multicast Routing with End-to-End Delay Constraint.Computer Communications,1999,22:181-192.
[33]Shigang C,Nahrstedt K.An overview of quality of service routing for next-generation high-speed networks:Problems and solutions.IEEE Network,1998,12(6):64-79.
[34]Murthy C S R,Manimaran G.Resource Management in Rreal-Time Systems and Network.Cambridge,MA:MIT Press,2001.
[35]Salama H F,Reeves D S,Viniotis Y.A distributed algorithm for delay-constrained unicast routing.In:IEEE INFOCOM'97,Vol.1.Kobe,Japan,April,1997.84-91.
[36]Apostolopoulos G,Williams D,Kamat S,et al.Routing mechanisms and OSPF extensions.RFC 2676,August 1999.
[37]Salama H F,Reeves D S,Viniotis Y.Evalution of multicast routing algorithm for real-time commnunication on high-speed networks.IEEE Journal on Selected Areas in Communications,1997,15(3):332-345.
[38]Braden R,Clark D,Shenker S.Integrated services in the Internet architecture:An overview.IETF RFC 1633,June 1994.
[39]Wroclawski J.Specification of the controlled-load network element service.IETF RFC 2211,September 1997.
[40]Shenker S,Partridge C,Guerin R.Specification of guaranteed quality of service.IETF RFC 2212,September 1997.
[41]Zhou X,Chen C,Zhu G.A Genetic Algorithm for Multicast Routing Problem[A].In Proceedings of ICCT'2000.2000:1248-1253.
[42]LuqLiu Z.Multicast Routing Based on Ant-Algorithm with Delay and Delay Variation Constriants[A].In Proceedings of ICCT'2000.2000:243-246.
[43]Tsai C W,Tsai C F,Chen C P.A Novel Multiple-Searching Genetic Algorithm forMultimedia Multicast.In Proceedings of CEC'2002[C].2002,2:1624-1629.
[44]Low C P,Lee Y J.Distributed Multicast Routing,with End-to-End Delay and Delay Variation Constrains.Computer Communications,2000,23(9):848-862.
[45]刑文训,谢金星.现代优化计算方法.北京:清华大学出版社,1999
[46]Peterson L L,Davie B S.Computer Networks:A System Approach.2~(nd)edition.Morgan Kaufmann Publisher,Inc,2000.454-457.
[47]Pitsillides A,Stylianou G,et al.Bandwidth allocation for virtual paths(BAVP):Investigation of performance of classical constrained and genetic algorithm based optimization techniques.In:IEEE INFOCOM 2000.Tel Aviv,2000.1379-1387.
[48]Dovrolis C,et al.Proportional differentiated services:Delay differentiation and packet scheduling.In:Proceedings of SIGCOMM'99.September 1999.
[49]林闯,周文江,田立勤.IP网络传输控制的性能评价标准研究.电子学报,2002,30(12A):1973-1977.
[50]Sahasrabuddhe L H,Mukherjee B.Multicast Routing Algorithms and Protocols:A Tutorial.IEEE Network.2000,14(1):90-102.
[51]Wang B,Hou J C.Multicast Routing and Its QoS Extension:Problem,Algorithm,and Protocols.IEEE Network,2000,14(1):22-36.
[52]Ma Q,Steenkiste P.Quality-of-Service Routing with Performance Guarantees[A].In Proceedings of the 4~(th)International IFIP Workshop on Quality of Service.1997.
[53]Kompella V P,Pasquale J C,Polyzos G C.Multicasting Routing for Multimedia Communication.IEEE/ACM Transactions on Networking,1993,1(3):286-292.
[54]Hong S,Lee H,Park B H.An Eficient Multicast Routing Algorithm for Delay-Sensitive Applications with Dynamic Membership.In Proceedings of IEEE INFOCOM'98[C].1998:1433-1440.
[55]王凌.智能优化算法及其应用.北京:清华大学出版社,施普林格出版社,2001.
[56]GLOVER F,KELLY J,LAGUNA M.Genetic Algorithms and Tabu Search:Hybrids for optimizations.Computer Ops Res,1995,22(1):111-134
[57]Shreedhar M,Varghese G.Efficient fair queueing using deficit round-robin.IEEE Transactions on Networking,1996,4(3):375-385.
[58]Guo C.SRR:An O(1)time complexity packet scheduler for flows in multi-service packet networks.In:Proc of ACM SIGCOMM'01.2001.211-222.
[59]Shimonishi H,Yoshida M.An improvement of weighted round robin cell scheduling in ATM networks.In:Proc of IEEE Globecom'97.Vol.2,1997.1119-1123.
[60]Bennett J R,Zhang H.WF2Q:Worst-case fair weighted fair queueing.In:IEEE INFOCOM'96.Vol.1,San Francisco,CA,Mar.1996.120-128.
[61]Stiliadis D,Varma A.Latency-Rate sercers:A general model for analysis of traffic scheduling algorithms.IEEE/ACM Trans on Networking,1998,6(5).
[62]Peterson L L,Davie B S.Computer Networks:A System Approach.2~(nd)ed.Morgan Kaufmann.2000.456-457.
[63]Charles C.Palmer,Aaron Kershenbaum:Representing Trees in Genetic Algorithms,IEEE World Congress in Computational Intelligence,Vol.1,1993,379-384.
[64]Parekh A K,Gallagher R G.A generalized processor sharing approach to flow-control in integrated services networks:The multiple node case.IEEE/ACM Trans on Networking,1994,2(2):137-150.
[65]Zhu Kai,Zhuang Yan,Viniotis Yannis.Achieving end-to-end delay bounds by EDF scheduling:without traffic shaping.In:IEEE INFOCOM 2001.
[66]Rayward-Smith V.The Computation of Nearly Minimal Steiner Trees in Graphs.International Journal of Mathematical Education in Science and Technology,1983,14(1):15-23.
[67]Low C P,Song X Y On Finding Feasible Solutions for the Delay Constrained Group Multicast Routing Problem.IEEE Transactions on Computers,2002,51(5):581-588
[68]王重钢,隆克平等.分组交换网络中队列调度算法的研究及其展望.电子学报,2001,29(4).
[69]Stoica Ion,Shenker Scott,Zhang Hui.Providing guaranteed services without per flow management.In:ACM SIGCOMM'99.Boston,MA,Sept.1999.
[70]The Network Simulator-ns-2.http://www.isi.edu/nsnam/ns/.2005-05.
[71]OPNET Technologies Inc.OPNET.http://www.mil3.com.2005-05.
[72]Alaettinoglu C,Dussa-Zieger K,Matta I,et al.MaRS User's Manual.Tehnical Report UMIACS-TR-91-80,CS-TR-2687,Department of Comupter Science,University of Maryland,College Park,1991.
[73]Zhang P,Kantola R,Ma Z S.Design and Implemention of A New Routing Simulator.In Proceedings of 2000 SCS Symposium on Perfomance.Evaluation of Computer and Telecommunication System(SPECTS'2K)[C].Vancouver,Canada,2000.
[74]The Real-Time Communication Project,QoS Routing(Unicast and Multicast),Software.http://rtcomm.csc.ncsu.edu/qos.htm.2005-05
[75]Waxman B M.Routing of Multipoint Connections.IEEE Journal on Selection Area in Communications,1998,6(9):1617-1622.
[76]张琨,王珩,刘凤玉.QoS仿真器的设计与实现.系统仿真学报,2005,17(7):1621-1625.
[2]Xipeng Xiao and M.Ni Lionel.Internet QoS:a big picture.IEEE Network,1999,13(2):8-18.
[3]Wang Z,Crowcroft J.Quality of Service for Supporting Multimedia Applications.IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234
[4]E.Rosen,A.Viswanathan,R.Callon.Multi Protocol Label Switching Architecture.IETF RFC3031,2001.
[5]R.Yavatkar,D.Hoffman,Y Bernet,F.Baker,M.Speer.SBM(Subnet Bandwidth Manager):A Protocol for RSVP-based Admission Control over IEEE 802-style networks.RFC 2814.May 2000
[6]林闯,单志广,任丰原.计算机网络的服务质量(QoS).第1版.北京:清华大学出版社,2004.
[7]R.Braden,L.Zhang,S.Berson et al.Resource RserVation Protocol(RSVP)(Version 1):Function Specification.IETF RFC 2205.September 1997.
[8]Debasish Chakraborty,Goutam Chakraborty,Norio Shiratori.A dynamic multicast routing satisfying multiple QoS constraints.International Journal of Network Management,2003,5:Volume 13.
[9]E.Rosen,A.Viswanathan,R.Callon.Multiprotocol Label Switching Architecture.IETF RFC3031,2001
[10]李斯伟,薛文安.实现Internet业务分类处理的DiffServ模型分析.通信技术,2001,(4):19-21.
[11]F.Baker,C.Iturralde,F.L.Faucheur,B.Davie.Aggregation of RSVP for IPv4 and IPv6Reservations.IETF Internet Draft
[12]Wang B,Hou J C.Multicast Routing and Its QoS Extension:Problem,Algorithm,and Protocols.IEEE Network,2000,14(1):22-36.
[13]Wang Z,Crowcroft J.QoS Routing for Supporting Resource Reservation.IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234
[14]赵键,吴介一,罗军舟等.一类基于源路由的多约束实时组播路由优化控制算法.电子学报,2001,29(4):490-494.
[15]Kompella V P,Pasqual J C,Polyzos G C.Multicast routing for multimedia communication.IEEE/ACM Trans on Networking,1993,1(3):286-292.
[16]Kou L,Markowsky G,Berman L.A fast algorithm for Steiner trees in graphs.Acta Informatica,1981,15(2):141-145.
[17]Zhu Q,Parsa M,Garcia-Luna-Aceves J J.A source-based algorithm for delay-constrained minimum-cost multicasting.In:Proc of IEEE-INFOCOM 95,Boston,MA,1995:452-458.
[18]顾亦然,江平,王锁萍.一种新的QoS保证的快速组播路由算法.南京邮电学院学报,2003,23(1):6-12.
[19]石坚,董天临等.一种基于延时及带宽受限的启发式组播路由算法.电子学报,2001,29(8):1113-1116.
[20]George N et al.Multicast Routing with End-to-End Delay and Delay Variation Constraints.IEEE JSAC,1997,15(3):346-356.
[21]B K Haberman,G N Rouskas.Cost,Delay and Delay Variation Conscious Multicast Routing.Technical Report TR-97-03,North Carolina State University,1997.
[22]余燕平,仇佩亮.时延和时延抖动约束的低费用多播路由算法.电路与系统学报,2001,6(4):65-68.
[23]李腊元,李春林.多QoS约束的多播路由协议.软件学报,2004,15(2):286-291.
[24]孙宝林,李腊元.多约束QoS多播路由的模型和算法研究.计算机工程与应用,2003,(29):41-44.
[25]陆慧梅,向勇,史美林等.一种基于带宽和时延约束的分布式组播路由算法.电子学报,2002,30(12A):1978-1981.
[26]崔勇,吴建平,徐格等.互联网络服务质量路由算法研究综述.软件学报,2002,13(11):2065-2075.
[27]刘先锋,舒林,陈松乔等.基于QoS约束的多播路由研究[J].计算机工程与应用,2005,(29):125-129.
[28]Zhang B X,Mouftah H T.A Destination-Driven Shortest Path Tree Algorithm[A].In Proceedings of the IEEE International Conference on Communications 2002(ICC'2002).New York:IEEE Communication Society,2002,4:2258-2262.
[29]Lee H Y,Youn C H.Scalable Multicast Routing Algorithm for Delay-Variation Constrained Minimum-Cost Tree[A].In Proceedings of IEEE International Conference on Communications.2000,3:1343-1347.
[30]Zhang Q F.An Orthogonal Genetic Algorithm for Multimedia Multicast Routing.IEEE Transactions on Evolutionary Computation,1999,3(1):53-62.
[31]Lee H Y,Youn C H.Scalable Multicast Routing Algorithm for Delay-Variation Constrained Minimim-Cost Tree[A].In Proceeding of IEEE International Conference on Communications.2000,3:1343-1347.
[32]Low C P.Loop-free Multicast Routing with End-to-End Delay Constraint.Computer Communications,1999,22:181-192.
[33]Shigang C,Nahrstedt K.An overview of quality of service routing for next-generation high-speed networks:Problems and solutions.IEEE Network,1998,12(6):64-79.
[34]Murthy C S R,Manimaran G.Resource Management in Rreal-Time Systems and Network.Cambridge,MA:MIT Press,2001.
[35]Salama H F,Reeves D S,Viniotis Y.A distributed algorithm for delay-constrained unicast routing.In:IEEE INFOCOM'97,Vol.1.Kobe,Japan,April,1997.84-91.
[36]Apostolopoulos G,Williams D,Kamat S,et al.Routing mechanisms and OSPF extensions.RFC 2676,August 1999.
[37]Salama H F,Reeves D S,Viniotis Y.Evalution of multicast routing algorithm for real-time commnunication on high-speed networks.IEEE Journal on Selected Areas in Communications,1997,15(3):332-345.
[38]Braden R,Clark D,Shenker S.Integrated services in the Internet architecture:An overview.IETF RFC 1633,June 1994.
[39]Wroclawski J.Specification of the controlled-load network element service.IETF RFC 2211,September 1997.
[40]Shenker S,Partridge C,Guerin R.Specification of guaranteed quality of service.IETF RFC 2212,September 1997.
[41]Zhou X,Chen C,Zhu G.A Genetic Algorithm for Multicast Routing Problem[A].In Proceedings of ICCT'2000.2000:1248-1253.
[42]LuqLiu Z.Multicast Routing Based on Ant-Algorithm with Delay and Delay Variation Constriants[A].In Proceedings of ICCT'2000.2000:243-246.
[43]Tsai C W,Tsai C F,Chen C P.A Novel Multiple-Searching Genetic Algorithm forMultimedia Multicast.In Proceedings of CEC'2002[C].2002,2:1624-1629.
[44]Low C P,Lee Y J.Distributed Multicast Routing,with End-to-End Delay and Delay Variation Constrains.Computer Communications,2000,23(9):848-862.
[45]刑文训,谢金星.现代优化计算方法.北京:清华大学出版社,1999
[46]Peterson L L,Davie B S.Computer Networks:A System Approach.2~(nd)edition.Morgan Kaufmann Publisher,Inc,2000.454-457.
[47]Pitsillides A,Stylianou G,et al.Bandwidth allocation for virtual paths(BAVP):Investigation of performance of classical constrained and genetic algorithm based optimization techniques.In:IEEE INFOCOM 2000.Tel Aviv,2000.1379-1387.
[48]Dovrolis C,et al.Proportional differentiated services:Delay differentiation and packet scheduling.In:Proceedings of SIGCOMM'99.September 1999.
[49]林闯,周文江,田立勤.IP网络传输控制的性能评价标准研究.电子学报,2002,30(12A):1973-1977.
[50]Sahasrabuddhe L H,Mukherjee B.Multicast Routing Algorithms and Protocols:A Tutorial.IEEE Network.2000,14(1):90-102.
[51]Wang B,Hou J C.Multicast Routing and Its QoS Extension:Problem,Algorithm,and Protocols.IEEE Network,2000,14(1):22-36.
[52]Ma Q,Steenkiste P.Quality-of-Service Routing with Performance Guarantees[A].In Proceedings of the 4~(th)International IFIP Workshop on Quality of Service.1997.
[53]Kompella V P,Pasquale J C,Polyzos G C.Multicasting Routing for Multimedia Communication.IEEE/ACM Transactions on Networking,1993,1(3):286-292.
[54]Hong S,Lee H,Park B H.An Eficient Multicast Routing Algorithm for Delay-Sensitive Applications with Dynamic Membership.In Proceedings of IEEE INFOCOM'98[C].1998:1433-1440.
[55]王凌.智能优化算法及其应用.北京:清华大学出版社,施普林格出版社,2001.
[56]GLOVER F,KELLY J,LAGUNA M.Genetic Algorithms and Tabu Search:Hybrids for optimizations.Computer Ops Res,1995,22(1):111-134
[57]Shreedhar M,Varghese G.Efficient fair queueing using deficit round-robin.IEEE Transactions on Networking,1996,4(3):375-385.
[58]Guo C.SRR:An O(1)time complexity packet scheduler for flows in multi-service packet networks.In:Proc of ACM SIGCOMM'01.2001.211-222.
[59]Shimonishi H,Yoshida M.An improvement of weighted round robin cell scheduling in ATM networks.In:Proc of IEEE Globecom'97.Vol.2,1997.1119-1123.
[60]Bennett J R,Zhang H.WF2Q:Worst-case fair weighted fair queueing.In:IEEE INFOCOM'96.Vol.1,San Francisco,CA,Mar.1996.120-128.
[61]Stiliadis D,Varma A.Latency-Rate sercers:A general model for analysis of traffic scheduling algorithms.IEEE/ACM Trans on Networking,1998,6(5).
[62]Peterson L L,Davie B S.Computer Networks:A System Approach.2~(nd)ed.Morgan Kaufmann.2000.456-457.
[63]Charles C.Palmer,Aaron Kershenbaum:Representing Trees in Genetic Algorithms,IEEE World Congress in Computational Intelligence,Vol.1,1993,379-384.
[64]Parekh A K,Gallagher R G.A generalized processor sharing approach to flow-control in integrated services networks:The multiple node case.IEEE/ACM Trans on Networking,1994,2(2):137-150.
[65]Zhu Kai,Zhuang Yan,Viniotis Yannis.Achieving end-to-end delay bounds by EDF scheduling:without traffic shaping.In:IEEE INFOCOM 2001.
[66]Rayward-Smith V.The Computation of Nearly Minimal Steiner Trees in Graphs.International Journal of Mathematical Education in Science and Technology,1983,14(1):15-23.
[67]Low C P,Song X Y On Finding Feasible Solutions for the Delay Constrained Group Multicast Routing Problem.IEEE Transactions on Computers,2002,51(5):581-588
[68]王重钢,隆克平等.分组交换网络中队列调度算法的研究及其展望.电子学报,2001,29(4).
[69]Stoica Ion,Shenker Scott,Zhang Hui.Providing guaranteed services without per flow management.In:ACM SIGCOMM'99.Boston,MA,Sept.1999.
[70]The Network Simulator-ns-2.http://www.isi.edu/nsnam/ns/.2005-05.
[71]OPNET Technologies Inc.OPNET.http://www.mil3.com.2005-05.
[72]Alaettinoglu C,Dussa-Zieger K,Matta I,et al.MaRS User's Manual.Tehnical Report UMIACS-TR-91-80,CS-TR-2687,Department of Comupter Science,University of Maryland,College Park,1991.
[73]Zhang P,Kantola R,Ma Z S.Design and Implemention of A New Routing Simulator.In Proceedings of 2000 SCS Symposium on Perfomance.Evaluation of Computer and Telecommunication System(SPECTS'2K)[C].Vancouver,Canada,2000.
[74]The Real-Time Communication Project,QoS Routing(Unicast and Multicast),Software.http://rtcomm.csc.ncsu.edu/qos.htm.2005-05
[75]Waxman B M.Routing of Multipoint Connections.IEEE Journal on Selection Area in Communications,1998,6(9):1617-1622.
[76]张琨,王珩,刘凤玉.QoS仿真器的设计与实现.系统仿真学报,2005,17(7):1621-1625.