WDM光网络中动态波长分配算法的研究
|
摘要
WDM光网络由于其高带宽、高速率、组网灵活等各种优越性被认为是未来骨干网的发展方向。波长资源是影响WDM光网络性能的主要因素,而波长分配算法是解决网络资源合理配置和提高网络运行效率的重要途径,所以研究波长分配算法具有十分重要的意义。本文把动态波长分配算法分成单纤和多纤两个不同的数学模型进行总结和改进,单纤光网络中波长分配算法以均衡波长数为目标,多纤光网络中波长分配算法以均衡每个波长的信道容量为目标。在研究方法上,针对改进的算法建立网络模型,通过软件仿真来比较不同算法的性能。本文主要分成以下四个方面:
1.从数学模型、理论算法等角度分析了单纤和多纤光网络的波长分配问题,并且介绍了当前比较常见的波长分配算法,分析了常见算法的思路和优劣性。针对软件仿真介绍了两种不同的业务量模型,并分别给出了生成方法。
2.基于光网络单纤数学模型提出了两种改进型的波长分配启发式算法。第一种是从预选波长角度出发,通过对路由子问题进行约束,提高波长使用率;第二种是运用波长分集重用思想,对不同QoS要求的业务设置不同的分配策略,在保证公平性的同时改善了网络效率。
3.基于光网络多纤数学模型提出了两种改进型的波长分配启发式算法。第一种基于均衡波长信道容量思想的波长分配算法,通过保护瓶颈链路容量,降低全网的拥塞概率;第二种是同时控制优先级和业务均衡的双优化目标算法。
4.介绍了论文作者设计开发的波长路由算法集成软件WRON-RWA,着重介绍了Topology Design组件和BlockingProbability组件。
Due to its enormous bandwidth, high-speed, flexible performance and other superiority, WDM optical network is considered the future of backbone network. Wavelength resource is the major factor on impacting WDM optical network's performance, and wavelength assignment algorithm is an important approach to allocate resource reasonably and improve the network efficiency, therefore it is crucial to study the wavelength assignment algorithm. In this thesis, wavelength assignment algorithm is analyzed in two mathematical models: single-fiber (SF) model and multi-fiber (MF) model. SF model's objective is to balance number of wavelengths. MF model's objective is to balance path capacity of every wavelength. In the research, model building and software simulation is used to compare the performance of different algorithms. This thesis is divided into 4 parts:
1. The SF and MF wavelength assignment are analyzed, including the mathematical model and theoretical algorithm. The author summarizes the wavelength assignment algorithms which can be often seen in the literatures, and interprets their ideas and performance. Besides, the author also introduces two traffic load model and explains how to generate them.
2. Two improved heuristic wavelength assignment algorithm based on single-fiber model are proposed. The first one is based on pre-selecting wavelength idea, it restricts route problem by resource and improves wavelength utilizations rate. The other one use the idea named wavelength-set, it allocates different strategy for the different QoS traffic so that fairness can be improved.
3. Two improved heuristic wavelength assignment algorithm based on multi-fiber model are proposed. The first one pays attention on the balancing strategy. The other one sets two optimized objectives in the algorithm, that are controlling priority and balancing traffic.
4. Software WRON-RWA is developed to evaluate the improved algorithm. The author's main contributions are the wavelength assignment part, Topology Design components and Blocking Probability components.
1.从数学模型、理论算法等角度分析了单纤和多纤光网络的波长分配问题,并且介绍了当前比较常见的波长分配算法,分析了常见算法的思路和优劣性。针对软件仿真介绍了两种不同的业务量模型,并分别给出了生成方法。
2.基于光网络单纤数学模型提出了两种改进型的波长分配启发式算法。第一种是从预选波长角度出发,通过对路由子问题进行约束,提高波长使用率;第二种是运用波长分集重用思想,对不同QoS要求的业务设置不同的分配策略,在保证公平性的同时改善了网络效率。
3.基于光网络多纤数学模型提出了两种改进型的波长分配启发式算法。第一种基于均衡波长信道容量思想的波长分配算法,通过保护瓶颈链路容量,降低全网的拥塞概率;第二种是同时控制优先级和业务均衡的双优化目标算法。
4.介绍了论文作者设计开发的波长路由算法集成软件WRON-RWA,着重介绍了Topology Design组件和BlockingProbability组件。
Due to its enormous bandwidth, high-speed, flexible performance and other superiority, WDM optical network is considered the future of backbone network. Wavelength resource is the major factor on impacting WDM optical network's performance, and wavelength assignment algorithm is an important approach to allocate resource reasonably and improve the network efficiency, therefore it is crucial to study the wavelength assignment algorithm. In this thesis, wavelength assignment algorithm is analyzed in two mathematical models: single-fiber (SF) model and multi-fiber (MF) model. SF model's objective is to balance number of wavelengths. MF model's objective is to balance path capacity of every wavelength. In the research, model building and software simulation is used to compare the performance of different algorithms. This thesis is divided into 4 parts:
1. The SF and MF wavelength assignment are analyzed, including the mathematical model and theoretical algorithm. The author summarizes the wavelength assignment algorithms which can be often seen in the literatures, and interprets their ideas and performance. Besides, the author also introduces two traffic load model and explains how to generate them.
2. Two improved heuristic wavelength assignment algorithm based on single-fiber model are proposed. The first one is based on pre-selecting wavelength idea, it restricts route problem by resource and improves wavelength utilizations rate. The other one use the idea named wavelength-set, it allocates different strategy for the different QoS traffic so that fairness can be improved.
3. Two improved heuristic wavelength assignment algorithm based on multi-fiber model are proposed. The first one pays attention on the balancing strategy. The other one sets two optimized objectives in the algorithm, that are controlling priority and balancing traffic.
4. Software WRON-RWA is developed to evaluate the improved algorithm. The author's main contributions are the wavelength assignment part, Topology Design components and Blocking Probability components.
引文
铩颷1]韦乐平.光网络的发展与挑战[J].通讯世界,2006,9:20-21.
[2]毛谦.光纤通信仍然是最主要的传输技术[J].电信科学,2000,4:38-42.
[3]龚倩,徐荣,张民,叶培大.光网络的组网与优化设计[M].北京,北京邮电大学出版社,2002.
[4]徐世中.波分复用光传送网中选路和波长分配算法的研究[D].电子科技大学,2000.
[5]罗先会.多波长光网络的路由算法和仿真的研究[D].南京邮电大学,2003.
[6]李健,杨爱平,顾畹仪,张杰.新的ASON路由实现方案[J].通信学报,2006,6:77-80.
[7]George N.Rouskas,Routing and Wavelength Assignment in Optical WDMNetworks,Wiley Encyclopedia of Telecommunications[M].2001.
[8]Rajiv Ramaswami and Kumar N.Sivarajan,Routing and Wavelength Assignmentin All-Optical Networks[J].IEEE/ACM Transactions on networking,1995,3(5):489-500.
[9]Hui Zang,Jason RJue,Biswanath Mukherjee.A review of routing andwavelength assignment approaches for wavelength routed optical WDM networks[J].Optical Networks Magazine,2000,1:47-60.
[10]George N.Rouskas,Harry G.Perros.A Tutorial on Optical Networks[C].Networking 2002 Tutorials,2002,2497:155-193.
[11]Mokkhtar A,Azizoglu M.Adaptive wavelength muting in all-optical networks[J].IEEE/ACM Trans Networking,1998,2:197-206.
[12]Subramaniam S,et al.Wavelength assignment in fixed-routing WDM networks[C].ICC97,1997:406-410.
[13]Zhang Xijun,Qiao Chunming.Wavelength assignment for dynamic traffic inmulti-fiber WDM networks[C].IEEE IC3N'98,1998:479-485.
[14]Xu Shizhong,Li Lemin,Wang Sheng.Wavelength assignment for dynamictraffic in WDM networks[C].APCC/OECC'99,1999.
[15]Xu Shizhong,Li Lemin,Wang Sheng.Wavelength Assignment for DynamicTraffic in WDM Networks[J].IEEE ICDN2000,2000:375-379.
[16]Ramaswami R,et al.Design of logical topologies for wavelength-routed opticalnetworks[J].IEEE JSAC,1996,14(5):840-851.
[17]Krishnaswamy R,et al.Design of logical topologies:a linear formulation forwavelength routed optical networks with no wavelength changers[C].INFOCOM98:919-927.
铩颷18]Harai H,et al.Performance of alternate routing methods in all-optical switchingnetworks[C].INFOCOM97:517-525.
[19]Harai H,et al.Performance of all-optical networks with limited-rangewavelength conversion[C].ICC97:416-421.
[20]Li L and Somani A K.Blocking performance analysis of fixed-pathleast-congestion routing in multi-fiber WDM network[C].SPIE all opticalnetworking 1999:56-67.
[21]Li L and Somani A K.Dynamic wavelength routing using congestion andneighborhood information[J].IEEE/ACM Trans.Networking,1999,7(6):779-786.
[22]刘次华.随机过程[M].武昌,华中科技大学出版社,2001.
[23]王杰.网络流量自相似特性分析与研究[D].西北大学,2006.
[24]张强,许进.自相似过程的几种模型[J].通信学报,2001,2:106-112.
[25]何荣希.WDM光网络中基于约束的动态选路和波长分配算法研究[D].电子科技大学,2001.
[26]李乐民.光网络选路和波长分配研究[J].中兴通讯技术,2004,06:1-3.
[27]金琦峰,乐孜纯,陆敏,付明磊.基于流量限制的动态自适应路由选择算法[J].光通信技术.2007,03:16-19.
[28]Garnot M,et al.Routing strategies for optical paths in WDM networks[C].ICC97:422-426.
[29]Chlamtac I,et al.Lightpath communication:an approach to high bandwidthoptical WAN's[J].IEEE Trans Comm,1992,40(7):1171-1182.
[30]Subramaniam S,Barry R.On the optimal placement of wavelength convertersin wavelength-routed networks[C].INFOCOM98:902-909.
[31]Wong E M,Chan A M,Yum Y P.Re-routing in circuit switched networks[C].INFOCOM97:1375-1380.
[32]Chan K M,Yum T E Analysis of least congested path routing in WDMlightwave network[C],INFOCOM94:1109-1113.
[33]何希荣,李乐民,徐世中.WDM光传送网中支持优先级的波长分配算法[J].通信学报,2001,3:27-32.
[34]刘凤洲,潘炜,罗斌,孟超.一种公平的多优先级WDM光网络波长分配算法[J].光通信研究,2007,2:1-4.
[35]Strong Cheng.Backtrack Routing and Priority-based Wavelength Assignmentin WDM networks[J].Computer Communications,1999,22:1-10.
[36]N.Wauters,P.Demeester.Wavelength requirements and survivability in WDMcross-connected networks[C].Proc.ECOC'94,1994:589-592.
[37]Z.Zhang and A.S.Acampora.A heuristic wavelength assignment algorithm for multihop WDM networks with wavelength routing and wavelength reuse[J].
IEEE/ACM Transactions on Networking,1995,3(5):281-288.
铩颷38]陆敏,乐孜纯,金琦峰,付明磊,刘恺.WDM网络中基于均衡策略的波长分配算法[J].光通信技术,2006,08:16-19.
[39]Zichun Le,Min Lu.A novel priority-based wavelength assignment algorithmfor dynamic traffic in WDM networks[C].APOC2007.
[40]何希荣,李乐民,徐世中,王晟.抗毁WDM网中支持QoS的选路和波长分配算法[J].电子与信息学报,2002,9:1153-1160.
[41]何荣希,李乐民,徐世中.多光纤WDM网中的QoS路由算法[J].电子与信息学报,2002,11:1589-1196.
[42]张治中,张云麒,李乐民.WDM网络中支持优先级的波长分配[J].通信学报,2001,7:54-60.
[43]乐孜纯,付明磊,陆敏,全必胜,方江平,金琦峰.路由与波长分配算法集成软件V1.0.软件著作权登字第066490号,2006,11.
[44]乐孜纯,陆敏,全必胜,付明磊,金琦峰.路由与波长分配算法集成软件V2.0.软件著作权登字第071922号.2007,02.
[2]毛谦.光纤通信仍然是最主要的传输技术[J].电信科学,2000,4:38-42.
[3]龚倩,徐荣,张民,叶培大.光网络的组网与优化设计[M].北京,北京邮电大学出版社,2002.
[4]徐世中.波分复用光传送网中选路和波长分配算法的研究[D].电子科技大学,2000.
[5]罗先会.多波长光网络的路由算法和仿真的研究[D].南京邮电大学,2003.
[6]李健,杨爱平,顾畹仪,张杰.新的ASON路由实现方案[J].通信学报,2006,6:77-80.
[7]George N.Rouskas,Routing and Wavelength Assignment in Optical WDMNetworks,Wiley Encyclopedia of Telecommunications[M].2001.
[8]Rajiv Ramaswami and Kumar N.Sivarajan,Routing and Wavelength Assignmentin All-Optical Networks[J].IEEE/ACM Transactions on networking,1995,3(5):489-500.
[9]Hui Zang,Jason RJue,Biswanath Mukherjee.A review of routing andwavelength assignment approaches for wavelength routed optical WDM networks[J].Optical Networks Magazine,2000,1:47-60.
[10]George N.Rouskas,Harry G.Perros.A Tutorial on Optical Networks[C].Networking 2002 Tutorials,2002,2497:155-193.
[11]Mokkhtar A,Azizoglu M.Adaptive wavelength muting in all-optical networks[J].IEEE/ACM Trans Networking,1998,2:197-206.
[12]Subramaniam S,et al.Wavelength assignment in fixed-routing WDM networks[C].ICC97,1997:406-410.
[13]Zhang Xijun,Qiao Chunming.Wavelength assignment for dynamic traffic inmulti-fiber WDM networks[C].IEEE IC3N'98,1998:479-485.
[14]Xu Shizhong,Li Lemin,Wang Sheng.Wavelength assignment for dynamictraffic in WDM networks[C].APCC/OECC'99,1999.
[15]Xu Shizhong,Li Lemin,Wang Sheng.Wavelength Assignment for DynamicTraffic in WDM Networks[J].IEEE ICDN2000,2000:375-379.
[16]Ramaswami R,et al.Design of logical topologies for wavelength-routed opticalnetworks[J].IEEE JSAC,1996,14(5):840-851.
[17]Krishnaswamy R,et al.Design of logical topologies:a linear formulation forwavelength routed optical networks with no wavelength changers[C].INFOCOM98:919-927.
铩颷18]Harai H,et al.Performance of alternate routing methods in all-optical switchingnetworks[C].INFOCOM97:517-525.
[19]Harai H,et al.Performance of all-optical networks with limited-rangewavelength conversion[C].ICC97:416-421.
[20]Li L and Somani A K.Blocking performance analysis of fixed-pathleast-congestion routing in multi-fiber WDM network[C].SPIE all opticalnetworking 1999:56-67.
[21]Li L and Somani A K.Dynamic wavelength routing using congestion andneighborhood information[J].IEEE/ACM Trans.Networking,1999,7(6):779-786.
[22]刘次华.随机过程[M].武昌,华中科技大学出版社,2001.
[23]王杰.网络流量自相似特性分析与研究[D].西北大学,2006.
[24]张强,许进.自相似过程的几种模型[J].通信学报,2001,2:106-112.
[25]何荣希.WDM光网络中基于约束的动态选路和波长分配算法研究[D].电子科技大学,2001.
[26]李乐民.光网络选路和波长分配研究[J].中兴通讯技术,2004,06:1-3.
[27]金琦峰,乐孜纯,陆敏,付明磊.基于流量限制的动态自适应路由选择算法[J].光通信技术.2007,03:16-19.
[28]Garnot M,et al.Routing strategies for optical paths in WDM networks[C].ICC97:422-426.
[29]Chlamtac I,et al.Lightpath communication:an approach to high bandwidthoptical WAN's[J].IEEE Trans Comm,1992,40(7):1171-1182.
[30]Subramaniam S,Barry R.On the optimal placement of wavelength convertersin wavelength-routed networks[C].INFOCOM98:902-909.
[31]Wong E M,Chan A M,Yum Y P.Re-routing in circuit switched networks[C].INFOCOM97:1375-1380.
[32]Chan K M,Yum T E Analysis of least congested path routing in WDMlightwave network[C],INFOCOM94:1109-1113.
[33]何希荣,李乐民,徐世中.WDM光传送网中支持优先级的波长分配算法[J].通信学报,2001,3:27-32.
[34]刘凤洲,潘炜,罗斌,孟超.一种公平的多优先级WDM光网络波长分配算法[J].光通信研究,2007,2:1-4.
[35]Strong Cheng.Backtrack Routing and Priority-based Wavelength Assignmentin WDM networks[J].Computer Communications,1999,22:1-10.
[36]N.Wauters,P.Demeester.Wavelength requirements and survivability in WDMcross-connected networks[C].Proc.ECOC'94,1994:589-592.
[37]Z.Zhang and A.S.Acampora.A heuristic wavelength assignment algorithm for multihop WDM networks with wavelength routing and wavelength reuse[J].
IEEE/ACM Transactions on Networking,1995,3(5):281-288.
铩颷38]陆敏,乐孜纯,金琦峰,付明磊,刘恺.WDM网络中基于均衡策略的波长分配算法[J].光通信技术,2006,08:16-19.
[39]Zichun Le,Min Lu.A novel priority-based wavelength assignment algorithmfor dynamic traffic in WDM networks[C].APOC2007.
[40]何希荣,李乐民,徐世中,王晟.抗毁WDM网中支持QoS的选路和波长分配算法[J].电子与信息学报,2002,9:1153-1160.
[41]何荣希,李乐民,徐世中.多光纤WDM网中的QoS路由算法[J].电子与信息学报,2002,11:1589-1196.
[42]张治中,张云麒,李乐民.WDM网络中支持优先级的波长分配[J].通信学报,2001,7:54-60.
[43]乐孜纯,付明磊,陆敏,全必胜,方江平,金琦峰.路由与波长分配算法集成软件V1.0.软件著作权登字第066490号,2006,11.
[44]乐孜纯,陆敏,全必胜,付明磊,金琦峰.路由与波长分配算法集成软件V2.0.软件著作权登字第071922号.2007,02.