蚁群算法在光突发交换网络路由中的研究
|
摘要
随着互联网的普及和深化,上网用户数急剧增加,网上IP数据流量爆炸式增长,造成网络的高阻塞率,需要扩大互联网的主干网信道容量。在一根光纤上能同时传输多路不同的信号的波分复用技术,能提供巨大的信道容量充分满足IP数据流量的高带宽和低延时的要求,是未来互联网主干网的核心技术和下一代光网络的研究热点。
采用波分复用技术的网络主要的光交换技术有光路交换、光分组交换和光突发交换。光突发交换具有中等交换粒度,比光路交换的资源利用率高,又比光分组交换容易实现。本文介绍了光突发交换网络模型和原理、光突发交换网络的控制协议、路由和波长分配问题特点,其中路由和波长分配是光突发交换网络的关键问题。在深入研究和分析常用的路由和波长分配算法的性能基础上,结合光突发交换网络的特点,改进基本蚁群算法,提出光突发交换网络中基于蚁群的路由和随机波长分配算法。该算法利用网络中局部的光纤链路的波长信道空余度信息,为突发数据包动态选择路由和分配波长,平衡网络业务的负载,能适应网络的局部动态变化,从而降低了整个网络的阻塞率。在扩展的NS-2网络仿真平台OBS-NS上,仿真本文算法和最短路由和波长随机分配算法。仿真数据结果显示,此算法的突发数据包阻塞率低于最短路由和随机波长分配算法。
With the popularity and deepening of the Internet, the number of users sharp increases in the Internet. The explosive growth of IP data traffic which results in the high blocking probability of the network needs to expand the channel capacity of the backbone network in the Internet. The WDM technology of simultaneously transmitting multiple different signals for a fiber can provide a huge channel capacity in order to sufficiently meet the high bandwidth and low latency demands of the IP data traffic, and is core technology for the backbone network of the Internet in the future.
In the network of using WDM technology, there are optical circuit switching, optical packet switching and optical burst switching in the major optical switching technologys. Optical burst switching with an intermediate particle size of the exchange, is higher than optical circuit switching in the utilization rate of resource and easier to achieve than optical packet switching and the research focus of the next-generation optical networks. The model and the principles of optical burst switching network was introduced, the control protocol of the optical burst switching network was presented, and the characteristics of routing and wavelength assigenment problem was described in this article. The routing and wavelength assignment in optical burst switching network is a key issue. On the foundation of in-depth research and analysis of the performance of routing and wavelength assignment algorithm in common use, combined with the characteristics of optical burst switching networks to improve the basic ant colony algorithm, ant colony routing and random wavelength assignment algorithm in the optical burst switching network was proposed. The algorithm uses the information of wavelength channel spare degree of the local fiber-optic link in the network, dynamicly selects routing and assigns wavelength for burst data packets to balance the load of the network traffic, adapting the local dynamic changes of the network and reducing the blocking probability of burst data packets in the whole network. On the extended OBS-NS network simulation platform of NS-2, this algorithm and the shortest routing and random wavelength assignment algorithm was simulated, the result of simulation data showed that the burst blocking probability of the algorithm less than that of the shortest routing and random wavelength assignment algorithm.
采用波分复用技术的网络主要的光交换技术有光路交换、光分组交换和光突发交换。光突发交换具有中等交换粒度,比光路交换的资源利用率高,又比光分组交换容易实现。本文介绍了光突发交换网络模型和原理、光突发交换网络的控制协议、路由和波长分配问题特点,其中路由和波长分配是光突发交换网络的关键问题。在深入研究和分析常用的路由和波长分配算法的性能基础上,结合光突发交换网络的特点,改进基本蚁群算法,提出光突发交换网络中基于蚁群的路由和随机波长分配算法。该算法利用网络中局部的光纤链路的波长信道空余度信息,为突发数据包动态选择路由和分配波长,平衡网络业务的负载,能适应网络的局部动态变化,从而降低了整个网络的阻塞率。在扩展的NS-2网络仿真平台OBS-NS上,仿真本文算法和最短路由和波长随机分配算法。仿真数据结果显示,此算法的突发数据包阻塞率低于最短路由和随机波长分配算法。
With the popularity and deepening of the Internet, the number of users sharp increases in the Internet. The explosive growth of IP data traffic which results in the high blocking probability of the network needs to expand the channel capacity of the backbone network in the Internet. The WDM technology of simultaneously transmitting multiple different signals for a fiber can provide a huge channel capacity in order to sufficiently meet the high bandwidth and low latency demands of the IP data traffic, and is core technology for the backbone network of the Internet in the future.
In the network of using WDM technology, there are optical circuit switching, optical packet switching and optical burst switching in the major optical switching technologys. Optical burst switching with an intermediate particle size of the exchange, is higher than optical circuit switching in the utilization rate of resource and easier to achieve than optical packet switching and the research focus of the next-generation optical networks. The model and the principles of optical burst switching network was introduced, the control protocol of the optical burst switching network was presented, and the characteristics of routing and wavelength assigenment problem was described in this article. The routing and wavelength assignment in optical burst switching network is a key issue. On the foundation of in-depth research and analysis of the performance of routing and wavelength assignment algorithm in common use, combined with the characteristics of optical burst switching networks to improve the basic ant colony algorithm, ant colony routing and random wavelength assignment algorithm in the optical burst switching network was proposed. The algorithm uses the information of wavelength channel spare degree of the local fiber-optic link in the network, dynamicly selects routing and assigns wavelength for burst data packets to balance the load of the network traffic, adapting the local dynamic changes of the network and reducing the blocking probability of burst data packets in the whole network. On the extended OBS-NS network simulation platform of NS-2, this algorithm and the shortest routing and random wavelength assignment algorithm was simulated, the result of simulation data showed that the burst blocking probability of the algorithm less than that of the shortest routing and random wavelength assignment algorithm.
引文
[1]徐宁榕,周春燕编著.WDM技术与应用[M].北京：人民邮电出版社,2002,12.
[2]纪越峰编著.光波分复用系统[M].北京：北京邮电大学出版社,1999,11.
[3]纪越峰,王宏祥等编著.光突发交换网络[M].北京：北京邮电大学出版社,2005.
[4]白杉.光交换技术发展综述[J].有线电视技术,2003,12(24)：63-66.
[5]杨舒雯著.全光光纤通信网[M].北京：科学出版社,2004.
[6]顾畹仪,张杰编著.全光通信网[M].北京：北京邮电学院出版社,1999,11.
[7]于挺进.光突发交换网络中路由波长分配算法研究[D].西安：西安电子科技大学硕士学位论文,2005.
[8]龚倩,编著.智能光交换网络[M].北京：北京邮电大学出版社,2003.
[9]S.Yao et al, Advnaces in Photonic Packet Switching:An Overview, [J]. IEEE Commun Mag, Feb.2000, pp84-94.
[10]Tarek S. El-Bawab. The Evolution to Optical-Switching Based Core Networks [J]. Optical Networks Magazine, v4, n2, p7-19, March-April 2003.
[11]B.Lavigne et al, All-optical 3R Regeneration[J]. LEOS 2000,13th Annual Mtg, vol.2,2000, pp407-408.
[12]翟锦华.全光通信中的光交换技术[J].科技信息,2009,(2)：272.
[13]Qiao, Chunming. Optical burst switching (OBS)-A new paradigm for an Optical Internet[J]. Journal of High Speed Networks, v 8, n1, pp69-84, 1999.
[14]S. J. Turner. Terabit Burst Switcing[J]. Journal of High Speed Network, 1999, (8):3-16.
[15]陈广文；刘庆国.全光通信网中的关键—技术光交换技术[J].现代电子技术,2002,(5)：84-85.
[16]王伟中.光交换技术及其发展[J].现代电信科技,1997,(4)：1-9.
[17]Dorigo, M., Stutzle, T.著；张军等译.蚁群优化[M].北京：清华大学出版社,2007,1.
[18]M Dorigo, L M Gambardella. Ant Colonies for the Traveling Salesman Problem [M]. BioSystems,1997(43):73-81.
[19]B Bullnheimer, R F Hartl, C Stauss. A New Bank-based Version of The ant System:A Computational Study[J]. Technical Report POM-03/97, Institute of Management Science, University of Vlenna,1997, (7):25-38.
[20]A Colorni, et al. Ant System for Job-shop Scheduling[J]. JORBEL,1994, 34(1):39-53.
[21]D Costa, A Hertz. Ants Can Colour Graphs[J]. J. of the Opnl. Res. Soc, 1997,48(3):295-305.
[22]P Kuntz, P Layzell, D Snyers. A colony of ant-like agents for partitioning in VLSI technology [J]. Proc. of the 4th European Conf. On Artificial Life. Boston:MIT Press,1997, pp417-424
[23]R Schoonderwoerd,O Holland, J Bruten. Ant like agents for load balancing in telecommunications networks[J]. Proc. of Agents'97. Marinadel Rey, CA:ACM Press,1997, pp209-216.
[24]G Di Caro, M Dorigo. Mobile Agents for Adaptive Routing[J]. Proc. of the 31st Hawaii Int. Conf. on System. Los Alamitos, CA:IEEE Computer Society Press,1998, pp74-83.
[25]B Bullnheimer, R F Hartl, C Strauss. Applying the ant System to the Vehicle Ruoting Problem[J]. Meta-Heuristics:Advances and Trends in Local Search Paradigms for Optimization. Kluwer, Boston,1998, pp109-120.
[26]Schoonderwoerd, R. Ant-based load balancing in telecommunications network[J]. HP Laboratories Technical Report, n96-76,26pp, May 1996.
[27]White, T. ASGA:Improving the Ant System by Integration with Genetic Algorithms[J]. Genetic Programming 1998. Proceedings of the Third Annual Conference, p 610-17,1998
[28]Dorigo, M. AntNet distributed stigmergetic control for communications networks[J]. Vivek, v12, n3-4, p2-37, July-Oct.1999.
[29]张爽.光突发交换网络中路由和波长分配问题的研究[D].西安：西安电子科技大学,博士学位论文,2005.
[30]YangChen, ChunmingQiao, Xiang Yu. optical burst switching an area in optical networking researeh, Network, IEEE, Volume(18), Issue(3), May-June,2004, pp 16-23.
[31]Y. Xiong, M. Vanderhoute and H. C. Cankaya. Controlarchitecture in optical burst-switched WDM networks [J]. IEEE Journal on Selected Areas in Communications, vol.18, No.10, October 2000, ppl838-1850.
[32]V. Vokkarane, J. P. Jue. Prioritized Routing and Burst Segmentation for QoS in Optical Burst-Switched Networks[J]. IEEE Journal on Selected Areas in Communications:Sep.2003,21(7):1198-1209.
[33]Ar.Duser, P. Bayvel. Performance of a Dynamically Wavelength-Routed Optical Burst Switched Network[J]. IEEE Photonics Technology Letters. Sep.2002,14(2):239-241.
[34]Sungchang Kim, Namook Kim. Contention Resolution for Optical Switching Network Using Alterative Routing[J]. IEEE International Conference on, Volume52002, pp2678-2681.
[35]C. Qiao and M. Yoo, Optical burst switching (OBS}-A new paradigm for an optical Internet[J]. High Speed Networks,1999, vol8, pp69-84.
[36]G Hudek and D. Muder, Signaling analysis for a multi-switch all-optical network[J]. Proceedings of Int'l Conf. on Communication (ICC), pp1206-1210, June,1995.
[37]J. S. Turner. Terabit burst switching[J]. Journal of High Speed Networks, v8, n1, p3-16,1999.
[38]C. Qiao, M. Yoo. Choices, Features and Issues in Optical Burst Switching[J]. Optical Networks Magazine, Apr,2000,1(2):37-44.
[39]C. Qiao, M. Yoo. Optical Burst Switching(OBS):A New Paradigm for an Optical Internet[J]. High Speed Network, Jan,1999,8(1):69-84.
[40]R. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, Survivable WDM mesh networks [J]. Journal of Lightwave Technology,2003,21(4): 870-883.
[41]王晓东.计算机算法设计与分析[M].北京：电子工业出版社,2001.
[42]王建英.WDM光网络中的路由与波长算法研究[D].新疆：新疆大学,硕士学位论文,2006.
[43]张爽,秦浩,刘曾基.基于搜索算法求解全光网络路由和波长分配问题[J].计算机学报,2004,27(3)：302-329.
[44]BIRMANA, et al. Routing and wavelength assignment methods in single-hop all-optical networks with blocking[A]. INFOCOM95: 431-438.
[45]Iizuka, M. A scheduling algorithm minimizing voids generated by arriving bursts in optical burst switched WDM network [J]. GLOBECOM'02-IEEE Global Telecommunications Conference. Conference Record (Cat. No.02CH37398), p2736-40, vol.3,2002
[46]CHLAMTAC I, et al. Lightpath communications:an approach to high bandwidth optical WANs[J]. IEEE Trans Comm,1992,40(7): 1171-1182.
[47]李士勇等.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社,2004,9.
[48]段海滨,王道波,朱家强,黄向华.蚁群算法理论及应用研究的进展[J].控制与决策,2004：(12)：1321-1326.
[49]段海滨,王道波,于秀芬.蚁群算法理论及应用研究的进展[J].控制与决策,2004,(12)：98-102.
[50]M Dorig, G Di Caro. Ant Colonies for Discrete Optimization[J]. Artificial Life, v5, n2, p137-72, Spring 1999.
[51]S Goss, S Aron, J-L Deneubourg et al. Solf-Organized Shortcuts in the Argentine Ant[J]. Naturwissenchaften,1989, (76):579-581.
[52]M Dorigo, L M Gambardella.Ant Colony System:A Cooperative Learning Approach to the Traveling Saleaman Problem[J]. IEEE Transactions on Evolutionary Computations,1997,1(1):53-56.
[53]L. M. Gambardella, M Dorigo. Solving Symmetric and Asymmetric TSPs by Ant Colonies [J]. IEEE International Conference on Evolutionary Computation,1996, pp622-627.
[54]徐雷鸣,庞博,赵耀.NS与网络模拟[M].北京：人民邮电出版社,2003.
[55]方路平等编著.NS-2网络模拟基础与应用[M].北京国防工业出版社,2008,5.
[56]郑和蒙,乐孜纯,付明磊.一种新型的OBS仿真平台的实现及其测试结果[J].计算机应用,2008,9.
[57]The Network Simulator ns-2. Http://www.isi.edu/nsnam/ns.
[58]Walter J, Gutjahr. A graph-based Ant System and its convergence [J]: Future Generation Computer Svstem,2000, (16):837-888.
[59]Dorigo M, Vittorio Maniezzo, Alberto Colorni. The Ant System: optimization by a colony ofcooperating agents[J]. IEEE Transactions on systems, Man and Cybernetics-part B,1996,26(1):1-13.
[2]纪越峰编著.光波分复用系统[M].北京：北京邮电大学出版社,1999,11.
[3]纪越峰,王宏祥等编著.光突发交换网络[M].北京：北京邮电大学出版社,2005.
[4]白杉.光交换技术发展综述[J].有线电视技术,2003,12(24)：63-66.
[5]杨舒雯著.全光光纤通信网[M].北京：科学出版社,2004.
[6]顾畹仪,张杰编著.全光通信网[M].北京：北京邮电学院出版社,1999,11.
[7]于挺进.光突发交换网络中路由波长分配算法研究[D].西安：西安电子科技大学硕士学位论文,2005.
[8]龚倩,编著.智能光交换网络[M].北京：北京邮电大学出版社,2003.
[9]S.Yao et al, Advnaces in Photonic Packet Switching:An Overview, [J]. IEEE Commun Mag, Feb.2000, pp84-94.
[10]Tarek S. El-Bawab. The Evolution to Optical-Switching Based Core Networks [J]. Optical Networks Magazine, v4, n2, p7-19, March-April 2003.
[11]B.Lavigne et al, All-optical 3R Regeneration[J]. LEOS 2000,13th Annual Mtg, vol.2,2000, pp407-408.
[12]翟锦华.全光通信中的光交换技术[J].科技信息,2009,(2)：272.
[13]Qiao, Chunming. Optical burst switching (OBS)-A new paradigm for an Optical Internet[J]. Journal of High Speed Networks, v 8, n1, pp69-84, 1999.
[14]S. J. Turner. Terabit Burst Switcing[J]. Journal of High Speed Network, 1999, (8):3-16.
[15]陈广文；刘庆国.全光通信网中的关键—技术光交换技术[J].现代电子技术,2002,(5)：84-85.
[16]王伟中.光交换技术及其发展[J].现代电信科技,1997,(4)：1-9.
[17]Dorigo, M., Stutzle, T.著；张军等译.蚁群优化[M].北京：清华大学出版社,2007,1.
[18]M Dorigo, L M Gambardella. Ant Colonies for the Traveling Salesman Problem [M]. BioSystems,1997(43):73-81.
[19]B Bullnheimer, R F Hartl, C Stauss. A New Bank-based Version of The ant System:A Computational Study[J]. Technical Report POM-03/97, Institute of Management Science, University of Vlenna,1997, (7):25-38.
[20]A Colorni, et al. Ant System for Job-shop Scheduling[J]. JORBEL,1994, 34(1):39-53.
[21]D Costa, A Hertz. Ants Can Colour Graphs[J]. J. of the Opnl. Res. Soc, 1997,48(3):295-305.
[22]P Kuntz, P Layzell, D Snyers. A colony of ant-like agents for partitioning in VLSI technology [J]. Proc. of the 4th European Conf. On Artificial Life. Boston:MIT Press,1997, pp417-424
[23]R Schoonderwoerd,O Holland, J Bruten. Ant like agents for load balancing in telecommunications networks[J]. Proc. of Agents'97. Marinadel Rey, CA:ACM Press,1997, pp209-216.
[24]G Di Caro, M Dorigo. Mobile Agents for Adaptive Routing[J]. Proc. of the 31st Hawaii Int. Conf. on System. Los Alamitos, CA:IEEE Computer Society Press,1998, pp74-83.
[25]B Bullnheimer, R F Hartl, C Strauss. Applying the ant System to the Vehicle Ruoting Problem[J]. Meta-Heuristics:Advances and Trends in Local Search Paradigms for Optimization. Kluwer, Boston,1998, pp109-120.
[26]Schoonderwoerd, R. Ant-based load balancing in telecommunications network[J]. HP Laboratories Technical Report, n96-76,26pp, May 1996.
[27]White, T. ASGA:Improving the Ant System by Integration with Genetic Algorithms[J]. Genetic Programming 1998. Proceedings of the Third Annual Conference, p 610-17,1998
[28]Dorigo, M. AntNet distributed stigmergetic control for communications networks[J]. Vivek, v12, n3-4, p2-37, July-Oct.1999.
[29]张爽.光突发交换网络中路由和波长分配问题的研究[D].西安：西安电子科技大学,博士学位论文,2005.
[30]YangChen, ChunmingQiao, Xiang Yu. optical burst switching an area in optical networking researeh, Network, IEEE, Volume(18), Issue(3), May-June,2004, pp 16-23.
[31]Y. Xiong, M. Vanderhoute and H. C. Cankaya. Controlarchitecture in optical burst-switched WDM networks [J]. IEEE Journal on Selected Areas in Communications, vol.18, No.10, October 2000, ppl838-1850.
[32]V. Vokkarane, J. P. Jue. Prioritized Routing and Burst Segmentation for QoS in Optical Burst-Switched Networks[J]. IEEE Journal on Selected Areas in Communications:Sep.2003,21(7):1198-1209.
[33]Ar.Duser, P. Bayvel. Performance of a Dynamically Wavelength-Routed Optical Burst Switched Network[J]. IEEE Photonics Technology Letters. Sep.2002,14(2):239-241.
[34]Sungchang Kim, Namook Kim. Contention Resolution for Optical Switching Network Using Alterative Routing[J]. IEEE International Conference on, Volume52002, pp2678-2681.
[35]C. Qiao and M. Yoo, Optical burst switching (OBS}-A new paradigm for an optical Internet[J]. High Speed Networks,1999, vol8, pp69-84.
[36]G Hudek and D. Muder, Signaling analysis for a multi-switch all-optical network[J]. Proceedings of Int'l Conf. on Communication (ICC), pp1206-1210, June,1995.
[37]J. S. Turner. Terabit burst switching[J]. Journal of High Speed Networks, v8, n1, p3-16,1999.
[38]C. Qiao, M. Yoo. Choices, Features and Issues in Optical Burst Switching[J]. Optical Networks Magazine, Apr,2000,1(2):37-44.
[39]C. Qiao, M. Yoo. Optical Burst Switching(OBS):A New Paradigm for an Optical Internet[J]. High Speed Network, Jan,1999,8(1):69-84.
[40]R. Ramamurthy, L. Sahasrabuddhe, B. Mukherjee, Survivable WDM mesh networks [J]. Journal of Lightwave Technology,2003,21(4): 870-883.
[41]王晓东.计算机算法设计与分析[M].北京：电子工业出版社,2001.
[42]王建英.WDM光网络中的路由与波长算法研究[D].新疆：新疆大学,硕士学位论文,2006.
[43]张爽,秦浩,刘曾基.基于搜索算法求解全光网络路由和波长分配问题[J].计算机学报,2004,27(3)：302-329.
[44]BIRMANA, et al. Routing and wavelength assignment methods in single-hop all-optical networks with blocking[A]. INFOCOM95: 431-438.
[45]Iizuka, M. A scheduling algorithm minimizing voids generated by arriving bursts in optical burst switched WDM network [J]. GLOBECOM'02-IEEE Global Telecommunications Conference. Conference Record (Cat. No.02CH37398), p2736-40, vol.3,2002
[46]CHLAMTAC I, et al. Lightpath communications:an approach to high bandwidth optical WANs[J]. IEEE Trans Comm,1992,40(7): 1171-1182.
[47]李士勇等.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社,2004,9.
[48]段海滨,王道波,朱家强,黄向华.蚁群算法理论及应用研究的进展[J].控制与决策,2004：(12)：1321-1326.
[49]段海滨,王道波,于秀芬.蚁群算法理论及应用研究的进展[J].控制与决策,2004,(12)：98-102.
[50]M Dorig, G Di Caro. Ant Colonies for Discrete Optimization[J]. Artificial Life, v5, n2, p137-72, Spring 1999.
[51]S Goss, S Aron, J-L Deneubourg et al. Solf-Organized Shortcuts in the Argentine Ant[J]. Naturwissenchaften,1989, (76):579-581.
[52]M Dorigo, L M Gambardella.Ant Colony System:A Cooperative Learning Approach to the Traveling Saleaman Problem[J]. IEEE Transactions on Evolutionary Computations,1997,1(1):53-56.
[53]L. M. Gambardella, M Dorigo. Solving Symmetric and Asymmetric TSPs by Ant Colonies [J]. IEEE International Conference on Evolutionary Computation,1996, pp622-627.
[54]徐雷鸣,庞博,赵耀.NS与网络模拟[M].北京：人民邮电出版社,2003.
[55]方路平等编著.NS-2网络模拟基础与应用[M].北京国防工业出版社,2008,5.
[56]郑和蒙,乐孜纯,付明磊.一种新型的OBS仿真平台的实现及其测试结果[J].计算机应用,2008,9.
[57]The Network Simulator ns-2. Http://www.isi.edu/nsnam/ns.
[58]Walter J, Gutjahr. A graph-based Ant System and its convergence [J]: Future Generation Computer Svstem,2000, (16):837-888.
[59]Dorigo M, Vittorio Maniezzo, Alberto Colorni. The Ant System: optimization by a colony ofcooperating agents[J]. IEEE Transactions on systems, Man and Cybernetics-part B,1996,26(1):1-13.