基于蚁群优化的OBS光网络多径路由保护算法研究
|
摘要
生存性问题是光突发交换网络面临的关键问题。传统的光路交换网络常用1+N的保护和修复技术解决此问题,但其发送冗余数据会导致大量资源的消耗,难以及时应对故障和业务处理的要求,尚不能直接用于解决光突发交换网络的生存性问题。
针对光突发交换网络的生存性问题,本文根据蚁群优化理论设计保护路由算法,实现多路径故障保护。一旦某条路由上的链路或者节点出现故障,整个网络仍然可以通过路由表的更新实现故障恢复。
经典蚁群算法只是根据蚂蚁走过路径的历史信息来进行路由,而对于目标食物的信息却无法获取。考虑利用网络中链路和节点的负载动态变化特性作为选路依据,若直接利用经典蚁群算法实现路由过程会出现信息滞后,因此需要对算法进行改进。
本文受自然蚂蚁可以靠嗅觉辨向的启发,在运用数据传输的历史信息来模拟路径信息素的基础上,对经典蚁群算法做出如下改进:增加目的节点泛洪负载信息来模拟食物向环境散发气味的过程,使得路径上的各节点都可以获得目的节点与路径的最新信息;节点根据链路上的信息素,目标节点信息,链路的可见度综合生成概率表,为后继蚂蚁提供选路依据。
本论文最后运用NS对改进算法进行仿真,测试结果表明该算法不仅可以实现网络的多路径保护,而且在故障发生时能尽快更新路由,减少传输时延,降低网络负载的波动幅度,实现网络故障的快速恢复。
A crucial issue in optical burst switching networks is survivability. Traditional optical circuit switching networks used 1 + N protection and restoration technology to solve this problem, but sending redundant data will lead to a great amount of resource consumption at the same time. Therefore it is difficult to deal with failure and operational requirements in time yet can not be directly used to solve optical burst switching networks survivable issue.
Aiming at survivability of optical burst switching networks, routing protection algorithm design in this thesis is under the theory of ant colony optimization to achieve multi-path failure protection. Hence,the whole network achieves restoration by updating routing table in case the route failure occurs on a link or node.
Classical ACO simply routing according to history path information which ants pass through, but can’t get the overall information of target food. Considering the dynamic load changing of links and nodes in the network, and routing is determined by the latest information, there will be lag error if we use ant algorithm directly to route path. Hereby the algorithm needs to be improved.
Inspired by ants use olfactory information for navigational means, the thesis adds the food giving off scents in order to simulate the destination address flooding load information, when pheromone trail is simulated by the history information of the forwarded data bursts. So every node can receive the latest information of destination node and links, and consequently the classical ACO expression is improved. Tables of probabilities are created by nodes based on pheromone,target node information, and link visibility, then the following ants can choose the routes in terms of the updating routing table mentioned above.
This routing algorithm is simulated by Network Simulator. The test result indicates that it can not only realize multi-path protection, but also update the routing table since failures take place, as well as to reduce the delay of transmission, decrease the fluctuating range of network loading, implement the load balancing of links and fast restoration.
针对光突发交换网络的生存性问题,本文根据蚁群优化理论设计保护路由算法,实现多路径故障保护。一旦某条路由上的链路或者节点出现故障,整个网络仍然可以通过路由表的更新实现故障恢复。
经典蚁群算法只是根据蚂蚁走过路径的历史信息来进行路由,而对于目标食物的信息却无法获取。考虑利用网络中链路和节点的负载动态变化特性作为选路依据,若直接利用经典蚁群算法实现路由过程会出现信息滞后,因此需要对算法进行改进。
本文受自然蚂蚁可以靠嗅觉辨向的启发,在运用数据传输的历史信息来模拟路径信息素的基础上,对经典蚁群算法做出如下改进:增加目的节点泛洪负载信息来模拟食物向环境散发气味的过程,使得路径上的各节点都可以获得目的节点与路径的最新信息;节点根据链路上的信息素,目标节点信息,链路的可见度综合生成概率表,为后继蚂蚁提供选路依据。
本论文最后运用NS对改进算法进行仿真,测试结果表明该算法不仅可以实现网络的多路径保护,而且在故障发生时能尽快更新路由,减少传输时延,降低网络负载的波动幅度,实现网络故障的快速恢复。
A crucial issue in optical burst switching networks is survivability. Traditional optical circuit switching networks used 1 + N protection and restoration technology to solve this problem, but sending redundant data will lead to a great amount of resource consumption at the same time. Therefore it is difficult to deal with failure and operational requirements in time yet can not be directly used to solve optical burst switching networks survivable issue.
Aiming at survivability of optical burst switching networks, routing protection algorithm design in this thesis is under the theory of ant colony optimization to achieve multi-path failure protection. Hence,the whole network achieves restoration by updating routing table in case the route failure occurs on a link or node.
Classical ACO simply routing according to history path information which ants pass through, but can’t get the overall information of target food. Considering the dynamic load changing of links and nodes in the network, and routing is determined by the latest information, there will be lag error if we use ant algorithm directly to route path. Hereby the algorithm needs to be improved.
Inspired by ants use olfactory information for navigational means, the thesis adds the food giving off scents in order to simulate the destination address flooding load information, when pheromone trail is simulated by the history information of the forwarded data bursts. So every node can receive the latest information of destination node and links, and consequently the classical ACO expression is improved. Tables of probabilities are created by nodes based on pheromone,target node information, and link visibility, then the following ants can choose the routes in terms of the updating routing table mentioned above.
This routing algorithm is simulated by Network Simulator. The test result indicates that it can not only realize multi-path protection, but also update the routing table since failures take place, as well as to reduce the delay of transmission, decrease the fluctuating range of network loading, implement the load balancing of links and fast restoration.
引文
[1] C. Qiao, M. Yoo. Optical burst switching (OBS)–A new paradigm for an optical internet. Journal of High Speed Networks, 1999, Vol.8, 69-84
[2] Jonathan Turner. Terabit burst switching. Journal of High Speed Networks, January 1999, Vol. 8, No. 1, 3-16
[3]纪越峰,王宏祥.光突发交换网络.北京邮电大学出版社,2005,76-79,99-103
[4] David Griffith, SuKyoung Lee. A 1+1 Protection Architecture for Optical Burst Switched Networks. IEEE Journal on Selected Areas in Communications, 2003, Vol. 21, No. 9, 1384-1398
[5] David Griffith, Kotikalapudi Sriram, Nada Golmie. Protection Switching for Optical Bursts Using Segmentation and Deflection Routing. IEEE communications letters, 2005, Vol. 9, No.10, 930-932
[6] Dorigo, M., Stützle, T. Ant Colony Optimization. MIT Press, 2004
[7] Pavani, G.S., Waldman, H. Evaluation of an ant-based architecture for all-optical networks. 10th Conference on Optical Network Design and Modelling, Copenhagen, Denmark, 2006
[8] Wittner, O., Helvik, B.E., Nicola, V. Internet failure protection using hamiltonian p-cycles found by ant-like agents. Proceedings of the 5th International Workshop on Design of Reliable Communication Networks, Island of Ischia, Italy, 2005, 437-444
[9] Pavani, G.S., Waldman, H.Traffic engineering and restoration in optical packet switching networks by means of ant colony optimization. Third International Conference on Broadband Communications, Network and Systems, San Jose, 2006
[10] Amit Kumar Garg , R S Kaler. Performance Analysis of Optical Burst Switching High-Speed Network Architecture. International Journal of Computer Science and Network Security, 2007,Vol.7 No.4, 292-301
[11] Jason P. Jue,Vinod M. Vokkarne. Optical Burst Switched Networks. Springer press, 2005, 11-14
[12] Amit Kumar Garg and R S Kaler. Enhancing Bandwidth Utilization and QoS in Optical Burst Switched High-Speed Network. Journal of Microwaves, Optoelectronics and Electromagnetic Applications, 2008, Vol. 7, No. 2
[13]黄蔚,郭丰,徐敏译.智能光网络——体系结构,协议和标准.北京:人民邮电出版,2007,62-63
[14] Martin Mainer. Optical Switching Networks. Cambridge University Press, 2008, 125-126
[15] Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1959, 1, 269-271
[16] Richard Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 1958, 16(1),87-90
[17] L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962
[18] Greg Bernstein, Bala Rajagopalan, Debanjan Saha. Optical Network Control: Architecture, Protocols, and Standards. Addison Wesley,2004,85-94
[19] M.Dorigo, V.Maniezzo, and A.Colorni. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on system: Man, and Cybernetics. Vol.B, 1996, 26 (1), 29-41
[20] Gianni Di Caro, Marco Dorigo. AntNet: distributed stigmergetic control for communications networks. J. Artif. Intell. Res. 1998, 9, 317–365
[21] Gianni Di Caro, Marco Dorigo. Two ant colony algorithms for best-effort routing in datagram networks. 10th International Conference on Parallel and Distributed Computing and Systems, Las Vegas, 1998, 541-546
[22] V. Laxmi, Lavina Jain, M. S. Gaur. Ant Colony Optimization Based Routing on NS-2. International Conference on Wireless Communication and Sensor Networks, India, December 2006
[23] Jacobson, V., Karels, M. Congestion avoidance and control. ACM Comput. Commun. Rev. 1990, 18(4), 314–329
[24] Gustavo Sousa Pavani,Helio Waldman. Restoration in wavelength-routed optical networks by means of ACO. Photon New Commun.2008, 16, 83–91
[25]李领治,郑洪源,丁秋林.一种基于改进蚁群算法的选播路由算法.电子与信息学报,2007,29(2), 340-344
[26] Barán, B., Sosa, R. AntNet—Routing algorithm for data networks based on mobile agents. Revista Iberoamericana de Inteligencia Artificial,2001,12, 75–84
[27] Glover, F., Laguna, M. Tabu Search. Kluwer Academic Publishers,1997
[28] Di Caro, G., Dorigo, M. AntNet: distributed stigmergetic control forcommunications networks. J. Artif. Intell. 1998, Res. 9, 317–365
[29] Bonabeau, E., Dorigo, M., Theraulaz, G.. Inspiration for optimization from social insect behaviour. Nature.2000, 406, 39–42
[30] Pham, V.A., Karmouch, A.Mobile software agents: an overview. IEEE Commun. Mag. 1998, 36(7), 26–37
[31] Lange, D.B., Oshima, M.: Seven good reasons for mobile agents. Commun. ACM 1999, 42(3), 88–89
[32] The ns Manual. http://www.isi.edu/nsnam/ns/ns-documentation.html, 2008
[33] OIRC OBS-ns Simulator http://wine.icu.ac.kr/~OBS-ns/, 2009
[2] Jonathan Turner. Terabit burst switching. Journal of High Speed Networks, January 1999, Vol. 8, No. 1, 3-16
[3]纪越峰,王宏祥.光突发交换网络.北京邮电大学出版社,2005,76-79,99-103
[4] David Griffith, SuKyoung Lee. A 1+1 Protection Architecture for Optical Burst Switched Networks. IEEE Journal on Selected Areas in Communications, 2003, Vol. 21, No. 9, 1384-1398
[5] David Griffith, Kotikalapudi Sriram, Nada Golmie. Protection Switching for Optical Bursts Using Segmentation and Deflection Routing. IEEE communications letters, 2005, Vol. 9, No.10, 930-932
[6] Dorigo, M., Stützle, T. Ant Colony Optimization. MIT Press, 2004
[7] Pavani, G.S., Waldman, H. Evaluation of an ant-based architecture for all-optical networks. 10th Conference on Optical Network Design and Modelling, Copenhagen, Denmark, 2006
[8] Wittner, O., Helvik, B.E., Nicola, V. Internet failure protection using hamiltonian p-cycles found by ant-like agents. Proceedings of the 5th International Workshop on Design of Reliable Communication Networks, Island of Ischia, Italy, 2005, 437-444
[9] Pavani, G.S., Waldman, H.Traffic engineering and restoration in optical packet switching networks by means of ant colony optimization. Third International Conference on Broadband Communications, Network and Systems, San Jose, 2006
[10] Amit Kumar Garg , R S Kaler. Performance Analysis of Optical Burst Switching High-Speed Network Architecture. International Journal of Computer Science and Network Security, 2007,Vol.7 No.4, 292-301
[11] Jason P. Jue,Vinod M. Vokkarne. Optical Burst Switched Networks. Springer press, 2005, 11-14
[12] Amit Kumar Garg and R S Kaler. Enhancing Bandwidth Utilization and QoS in Optical Burst Switched High-Speed Network. Journal of Microwaves, Optoelectronics and Electromagnetic Applications, 2008, Vol. 7, No. 2
[13]黄蔚,郭丰,徐敏译.智能光网络——体系结构,协议和标准.北京:人民邮电出版,2007,62-63
[14] Martin Mainer. Optical Switching Networks. Cambridge University Press, 2008, 125-126
[15] Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1959, 1, 269-271
[16] Richard Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 1958, 16(1),87-90
[17] L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962
[18] Greg Bernstein, Bala Rajagopalan, Debanjan Saha. Optical Network Control: Architecture, Protocols, and Standards. Addison Wesley,2004,85-94
[19] M.Dorigo, V.Maniezzo, and A.Colorni. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on system: Man, and Cybernetics. Vol.B, 1996, 26 (1), 29-41
[20] Gianni Di Caro, Marco Dorigo. AntNet: distributed stigmergetic control for communications networks. J. Artif. Intell. Res. 1998, 9, 317–365
[21] Gianni Di Caro, Marco Dorigo. Two ant colony algorithms for best-effort routing in datagram networks. 10th International Conference on Parallel and Distributed Computing and Systems, Las Vegas, 1998, 541-546
[22] V. Laxmi, Lavina Jain, M. S. Gaur. Ant Colony Optimization Based Routing on NS-2. International Conference on Wireless Communication and Sensor Networks, India, December 2006
[23] Jacobson, V., Karels, M. Congestion avoidance and control. ACM Comput. Commun. Rev. 1990, 18(4), 314–329
[24] Gustavo Sousa Pavani,Helio Waldman. Restoration in wavelength-routed optical networks by means of ACO. Photon New Commun.2008, 16, 83–91
[25]李领治,郑洪源,丁秋林.一种基于改进蚁群算法的选播路由算法.电子与信息学报,2007,29(2), 340-344
[26] Barán, B., Sosa, R. AntNet—Routing algorithm for data networks based on mobile agents. Revista Iberoamericana de Inteligencia Artificial,2001,12, 75–84
[27] Glover, F., Laguna, M. Tabu Search. Kluwer Academic Publishers,1997
[28] Di Caro, G., Dorigo, M. AntNet: distributed stigmergetic control forcommunications networks. J. Artif. Intell. 1998, Res. 9, 317–365
[29] Bonabeau, E., Dorigo, M., Theraulaz, G.. Inspiration for optimization from social insect behaviour. Nature.2000, 406, 39–42
[30] Pham, V.A., Karmouch, A.Mobile software agents: an overview. IEEE Commun. Mag. 1998, 36(7), 26–37
[31] Lange, D.B., Oshima, M.: Seven good reasons for mobile agents. Commun. ACM 1999, 42(3), 88–89
[32] The ns Manual. http://www.isi.edu/nsnam/ns/ns-documentation.html, 2008
[33] OIRC OBS-ns Simulator http://wine.icu.ac.kr/~OBS-ns/, 2009