WDM光网络的选路和波长分配算法研究

WDM光网络中的组播波长分配算法研究
WDM光网络中的组播波长分配算法研究
吴启武;王建萍;周贤伟;宋宁宁
【期刊名称】《光通信技术》
【年(卷),期】2009(033)009
【摘要】组播是一种应用广泛的点到多点或多点到多点的通信方式,光层组播以其独特优势引起了人们的关注和重视.在综合分类的基础上,对光网络组播波长分配算法的最新研究进展进行了归纳和总结,并对今后需重点研究的方向进行了展望.
【总页数】4页(19-22)
【关键词】WDM;光网络;组播;波长分配
【作者】吴启武;王建萍;周贤伟;宋宁宁
【作者单位】北京科技大学信息工程学院通信工程系,北京,100083;北京科技大学信息工程学院通信工程系,北京,100083;北京科技大学信息工程学院通信工程系,北京,100083;北京科技大学信息工程学院通信工程系,北京,100083
【正文语种】中文
【中图分类】TN929.11
【相关文献】
1.WDM光网络中的组播路由算法研究 [J], 吴启武; 王建萍; 周贤伟
2.WDM-TDM光网络中的动态波长路由与时隙分配算法研究[J], 项鹏; 王荣
3.WDM波长连续光网络中路由和波长分配算法研究[J], 康巧燕; 李维民; 种满东
4.全光网络中组播路由波长分配的一种遗传算法[J], 王营昌; 高随祥; 宋乃斌;。

WDM波长路由光网络的波长分配算法
李勇军;李维民;王洪刚
【期刊名称】《应用光学》
【年(卷),期】2004(025)005
【摘要】由于WDM网络中的传输和交换是以波长为粒度进行的,因此波长分配算法就成为光网络的研究热点.有效的算法可大大提高波长的利用率,并可充分挖掘WDM的带宽资源.介绍了WDM全光网络中静态和动态波长分配算法,尤其是结合大型网孔网络详述了几种动态波长分配算法. 针对波长变换器在全光网络中的应用,提出了一种可以解决任意类型光网络的分层图算法,它可以一次性解决路由选择和波长分配问题,大大提高了该算法的效率,是未来光网络中非常有前景的一种波长分配算法.
【总页数】5页(P11-15)
【作者】李勇军;李维民;王洪刚
【作者单位】空军工程大学,电讯工程学院,陕西,西安,710077;空军工程大学,电讯工程学院,陕西,西安,710077;空军工程大学,电讯工程学院,陕西,西安,710077
【正文语种】中文
【中图分类】TN919.85
【相关文献】
1.波长路由WDM网络中"稀疏-部分"波长转换的模型与研究 [J], 先茅家;陈明道
2.WDM-TDM光网络中的动态波长路由与时隙分配算法研究 [J], 项鹏;王荣
3.波长路由WDM网络中"稀疏-部分"波长转换的建模与分析 [J], 蔡伟祥;毛期俭;张治中
4.WDM网络中基于优先级的多任务波长路由分配算法 [J], 田相轩;杨君刚;车雅良;孙文正;刘故菁
5.DWDM波长路由网络光链路负载均衡的波长路由算法 [J], 李蔚;何军;刘德明;黄德修
因版权原因，仅展示原文概要，查看原文内容请购买。

WDM全光网自适应路由和波长分配算法孙俊【期刊名称】《光通信研究》【年(卷),期】2001(000)003【摘要】研究了无波长转换WDM全光网的路由和波长分配算法（RWA）.通过对已有算法的分析和比较，提出了一种自适应最小跳数路由算法（ADMH）.此算法以最小跳数路由为基础，同时考虑网络状态的变化，因而不仅能尽量少使用网络资源，也能使网络资源的分布保持均衡.计算机模拟仿真的结果表明，这种算法性能在各种网络参数条件下优于或等于已有算法.%Routing and wavelength assignment algorithms for NCWDM all-optical networks are studied in this paper. Through analysis and comparison, a new adaptive dynamic minimum-hop routing algorithm (ADMH) is proposed. The algorithm is based on DMH and takes the network statement into consideration, so that it can not only use network resources as little as possible but also keep the network resources as balanced as possible. The simulation results show that the performance is good than or equal to some existent algorithms for different network parameters.【总页数】4页(P8-11)【作者】孙俊【作者单位】华中科技大学电子与信息工程系,【正文语种】中文【中图分类】TN929.1【相关文献】1.WDM全光网络中的多播路由与波长分配算法 [J], 于周秋;刘三阳2.WDM全光网络中Multicast的寻径与波长分配算法 [J], 黄传河;陈莘萌;贾小华3.WDM全光网络中实时组播的分布式路由与波长分配算法 [J], 黄传河;陈莘萌;贾小华4.适用于WDM全光网的自适应路由与波长分配算法 [J], 李培源;赵艳梅;顾畹仪;周锡增5.共享波长转换器全光网的路由和波长分配算法 [J], 肖诗源;金鑫;刘贤德因版权原因，仅展示原文概要，查看原文内容请购买。

光通信网络中的路由与波长分配优化研究光通信网络是一种基于光纤传输的高速、高带宽网络技术。

在光通信网络中，路由与波长分配是网络性能和效率的关键因素。

优化路由与波长分配策略可以提高网络的传输能力、降低传输延迟和提高网络的可靠性。

本文将介绍光通信网络中路由与波长分配的相关研究和优化方法。

一、光通信网络中的路由优化研究在光通信网络中，路由优化是指通过选择合适的路径，使得数据包能够以最短的路径传输到目的地。

光通信网络中的路由优化研究主要有以下几个方面：1. 路由算法研究：在光通信网络中，路由算法是决定数据包传输路径的关键。

常用的路由算法包括最短路径优先算法、最小负载优先算法等。

研究者们通过对比不同路由算法的性能指标，如传输延迟、网络吞吐量等，来评估路由算法的优劣。

同时，也有研究者提出了一些新的路由算法，如基于流动性的路由算法、基于预测的路由算法等，以进一步提高路由的效率和性能。

2. 拓扑结构优化：光通信网络中的拓扑结构对路由的选择和效率有重要影响。

研究者们通过对网络拓扑结构的优化，如调整网络的连接方式、增加网络中的光纤等措施，来提高路由的性能。

例如，采用分层拓扑结构可以减少路由冲突，提高网络的传输能力。

3. 多路径路由研究：光通信网络中的多路径路由可以提高网络的可靠性和容错能力。

研究者们通过设计多路径路由算法，使数据包能够同时通过多条路径传输，以减少单点故障和降低网络的传输延迟。

多路径路由还可以通过合理分配负载，提高网络的吞吐量。

二、光通信网络中的波长分配优化研究波长分配是光通信网络中实现多路复用和分割信号的关键技术，它决定了光通信网络的传输能力和效率。

波长分配优化研究主要包括以下几个方面：1. 动态波长分配算法研究：光通信网络中，波长资源是有限的。

为了更好地利用波长资源，研究者们提出了一系列动态波长分配算法。

这些算法可以根据当前网络状态和传输需求，灵活地分配波长资源，以提高网络的传输能力和效率。

例如，基于启发式的波长分配算法可以基于历史数据和网络拓扑结构，预测和分配最优的波长。

WDM光传送网的选路和波长分配算法为了克服电处理的速率“瓶颈”，宽带网络向光网络发展。

目前，光突发交换、光分组(包)交换正在积极研究中，但是距商用还较远。

已可商用的是具有光分插复用器(OADM,OpticalAdd－DropMultiplexer)和光交叉连接器(OXC,OpticalCross－Connect)的波分复用(WDM)网络。

由于是提供可调度的传送用光路，称这种网络为WDM光传送网(OTN,OpticalTransportNetwork)。

1网络结构图1是网络物理结构的一个例子，虚线内为光传送网。

图中有5个OXC：A，B，C，D，E；5个具有光接口的电设备：S1～S5；6个将OXC相连的物理链路：l1～l6。

一般一条物理链路包含一对光纤供双向运用，有的OXC间没有物理链路相连。

但更多的情况是一条物理链路包含多根光纤供不同方向运用。

一根光纤上可采用多个波长。

一般情况下，OXC不直接和电设备相连，只起光交叉连接作用。

OXC可分为无波长变换和有波长变换(也可以是部分端口有波长变换或波长变换的范围有限)两种：无波长变换的OXC的作用是将一根输入光纤上的某一波长信号连到另一根输出光纤的同一波长上，即波长是连续的；有波长变换则是将一根输入光纤上的某一波长信号连到另一根输出光纤的另一波长上。

适当地安排路由和分配波长，可为电设备间建立光路(opticalpath)。

在一根光纤上，不能为不同光路分配相同波长。

图2(a)为图1建立的光路例子。

将图2(a)的光路连接用图2(b)来表示，称为逻辑结构，也称逻辑拓扑或虚拓扑。

例如，图2(a)中，节点B与E间的光路是经节点A中的OXC转接的，在图2(b)中用O4表示。

图2(b)中，O6、O4、O1都是中间有OXC转接的。

O2、O3、O5是直接光路。

这样建立的光路对信号是透明的，即信号可以是任意方式。

实际设计中，一种需求情况是：提出所需建立的光路，为这种光路选取物理路由并分配相应的波长[1,2]。

WDM光网络中的路由和波长分配算法研究的开题报告
一、选题背景
光纤通信技术作为现代通信领域中最为重要的技术之一，其优越的传输性能和巨大的数据传输容量一直引领着通信发展的方向。

然而，光网络中光波长资源的分配和
利用一直是研究的热点和难点，光波长分组多路复用（WDM）技术的出现，使得光网络中的数据传输更加的灵活和高效。

光网络中的路由和波长分配算法设计是实现高性
能光网络的关键技术之一，其目的是充分利用现有的光波长资源，减少光路的互相干
扰和光功率损失，同时还需要考虑网络的负载均衡、容错能力和性能指标等方面的因素。

二、研究目的
本次研究的目的是探究在WDM光网络中光路路由和波长分配算法的研究和设计，同时要对现有的路由和波长分配算法进行分析，找出其存在的问题和不足，提出新的
改进算法并进行验证和测试。

三、研究内容
1. WDM光网络路由和波长分配算法的原理和基础知识
2. 研究并总结现有的路由和波长分配算法，分析其中存在的问题和不足
3. 提出改进算法，比较不同算法的性能指标，进行验证和测试
4. 对算法的效率和可靠性进行评价
四、预期结果和意义
本次研究的预期结果是设计一种能够充分利用现有光波长资源的WDM光网络路由和波长分配算法，提高通信网络的效率和可靠性，同时提高数据传输的安全性和稳
定性。

研究结果对于光网络设计和建设具有重要指导意义，并具有良好的应用前景。

波长分配方法随着波分复用技术的应用，几个光信号可在单根光纤传输。

这种技术可以更有效的利用光纤的巨大力量，但也带来了新的网络设计和管理问题，尤其是当波长转换节点中没有可能的。

考虑在这样的网络中的路由和波长分配问题，一旦路线是固定的波长分配基本上是一个图着色问题。

对于一个给定的图着色算法，在当前的研究中较主流的有贪婪算法，穷举搜索，模拟退火以及遗传算法。

都是相当不错的路由和波长分配性能，本文主要介绍在路由选择确定的情况下的波长分配问题，且着重从贪婪算法和穷举搜索算法来讲述波长分配方法。

在本文中，我们集中在WDM网络路由和波长分配问题。

当多个信号共享相同的纤维，他们必须使用不同的波长。

现有的技术设置了一个上限的波长数。

因此，我们认为，导致建立一个给定的连接在与最低数量的波长网络设置的问题。

在制定的最优化问题，取决于是否有可能在波长转换节点或没有。

如果波长转换的最佳解决方案是可能的只是最大限度地减少了使用的通道的链接的最大数量。

路由问题是在正常的电路交换网络，在唯一的限制因素是对每一个环节通道数相同。

另一方面，如果波长转换不能在节点完成后，这便产生了优化问题新的约束。

每个连接使用上沿线的各个环节相同的波长。

一个可行的解决方案使用小于或等于各个环节的波长数比有可用的，没有两个连接共享一个共同的联系具有相同的波长。

也可以使用波长转换网络。

在本文中不讨论这种网络，因此，我们假定波长转换不能在任何节点完成。

我们还假设没有任何的网络动态重构的需要，即连接设置是静态的。

路由和波长分配问题是紧密联系在一起。

我们首先要确定每个连接的线路（即路由），然后尝试使用最小数量的波长来进行波长分配。

这样做，这样反复的进行着色尝试目的在于对路由连接不改变的同时使用最少的颜色来完成全图的着色。

同时，在实践中以求找到比现有技术使用更加少颜色的着色方案。

在路由和波长分配过程是代表在图1。

在左边是一个物理网络。

中间的是固定路由波长分配图，右侧的图是图着色方案，其中的节点表示连接，按来源目的地对应表示，和邻居节点的连接（表示之间存在共享），如果且仅当相应的连接有着一些共同的联系。

中文核心期刊WDM光网络中的组播波长分配算法研究吴启武，王建萍，周贤伟，宋宁宁(北京科技大学信息工程学院通信工程系，北京100083)摘要：组播是一种应用广泛的点到多点或多点到多点的通信方式，光层组播以其独特优势引起了人们的关注和重视。

在综合分类的基础上，对光网络组播波长分配算法的最新研究进展进行了归纳和总结，并对今后需重点研究的方向进行了展望。

关键词：W D M；光网络；组播；波长分配中图分类号：TN929.11文献标识码：A文章编号：1002-5561(2009)09-0019-04Research on multicast wavelength assignment algorithm inWDM optical networksWU Qi-wu,WANG Jian-ping,ZHOU Xian-wei,SONG Ning-ning(Department of Communication Engineering,School of Information Engineering,University of Science and Technology Beijing,Beijing100083,China)Abstract:Multicast provides a means of point-to-multipoint or multipoint-to-multipoint communication, which has several applications.Because of its specific advantage,optical multicasting arrests more attention.In this paper,the newest advance of multicast wavelength assignment algorithm in optical networks based on the integrated classification is summarized.Besides,the further direction which is critical to the problem is foreseen.Key words:WDM,optical network,multicast,wavelength assignment0引言组播是一种点到多点或多点到多点的通信，其应用十分广泛[1]。

基于遗传算法的静态WDM网络选路和波长分配方法
林小雨;陈辉
【期刊名称】《现代传输》
【年(卷),期】2006(000)001
【摘要】选路和波长分配(RWA)是ASON控制层面的重要功能之一.在静态RWA 问题中,我们讨论波长优化问题,即在给定网络物理结构和业务连接需求的情况下,找出建立这些业务连接所需的最小波长数.针对该NP-Complete问题的特点,提出了一种编码方式简单、算法效率较高、收敛速度较快的改进遗传算法.为了取得更好的实验结果,运用了正交均匀试验设计的方法来进行参数设置,针对不同的参数进行了仿真分析.对于实验结果,通过和经典ILP算法的对比分析,印证了该改算法的准确性和有效性.
【总页数】4页(P63-66)
【作者】林小雨;陈辉
【作者单位】信息产业部电信规划研究院,北京,100037;信息产业部电信规划研究院,北京,100037
【正文语种】中文
【中图分类】TN92
【相关文献】
1.WDM网络基于波长的一种多优先级波长分配算法 [J], 吴波;乐孜纯
2.任意拓扑结构全光WDM网络中波长转换器配置的遗传算法 [J], 高峰;高随祥
3.基于WDM网络的多播动态选路算法研究 [J], 叶必海
4.基于WDM网络的多播动态选路算法研究 [J], 叶必海
5.基于波长共享机制的机载WDM网络波长分配算法 [J], 李瑞欣; 赵海燕; 朱蒙; 于龙强
因版权原因，仅展示原文概要，查看原文内容请购买。

第 40卷第 10期2003年 10月计算机研究与发展J OU RNAL OF COMPU TER RESEARCH AND DEV ELOPM EN TVol 140,No 110Oct 12003收稿日期 :2002211220; 修回日期 :2003206227WDM 全光网络中实时组播的分布式路由与波长分配算法黄传河陈莘萌贾小华(武汉大学计算机学院武汉 430072 (hwanghe @public 1wh 1hb 1cn摘要在 WDM 网络中 , 由于每条链路上可用波长是动态变化的 , 在考虑波长转换延迟的条件下 , 实现实时组播连接的路由与波长分配是十分困难的 1假定WDM 网络中每条链路有多根光纤 , 只有部分结点具有波长转换器且波长转换时间是不可忽略的 , 据此提出了一种用于建立实时组播连接的分布式路由与波长分配算法 1该算法以 Prim 最小生成树算法为基础 , 生成一棵满足给定延迟时限的最小成本树 1当最小成本树不能包括所有目的结点时 , 对剩余目的结点生成一棵最短延迟树 , 然后合并两棵树得到一棵组播树 1波长分配使用最少波长转换和负载平衡策略1关键词 WDM 网络 ; 路由与波长分配 ; 组播路由 ; 延迟限制路由中图法分类号TP393101A Distributed Routing and W avelength Assignment Algorithm eal 2Time Mul2ticast in WDM All 2Optical N et worksHUAN G Chuan 2He , CHEN Xin 2Meng , and J IA (Com puter School , W uhan U niversity ,Abstract for online real 2time multicast connection setup is difficult due to the of availabilities of wavelengths on links and the consideration of wavelength con 2version delay in WDM networks 1Assuming that each link has multiple fibres , there are wavelength con 2verters only at part of nodes and the conversion delay is not negligible 1A distributed routing and wave 2length assignment algorithm for the setup of real 2time multicast connections is presented based on the above assumption 1The algorithm is based on Prim ’ s MST (minimum spanning tree algorithm 1It generates a sub 2minimal cost tree under a given delay bound first 1If there are nodes not included in the cost tree , a de 2lay tree is generated to include the rest nodes 1The two trees are merged together 1The wavelength assign 2ment uses least 2conversion and load balancing strategies 1K ey w ords WDM networks ; routing and wavelength assignment ; multicast routing ; delay bound routing1引言WDM (wavelength division multiplexing 将光纤的带宽分为互不重叠的并行通道 , 每个通道使用一个波长传输信号 1WDM 是充分利用光纤带宽的关键技术 1WDM 网络是面向连接的 , 在数据传输前 , 通信双方必须建立连接 1在 WDM 网络中建立连接包括路由选择和波长分配两个过程 , 简称为 RWA(routing and wavelength assignment 1组播是一种组通信机制 , 其发送者 (源结点将消息同时发送给一组接收者 (目的结点 1实时组播是一类特定的组播形式 , 要求在组播请求到达后尽快建立组播连接 , 同时在所建立的连接中从源结点到任一目的结点的延迟时间不超过给定的时限 1实时组播在现代计算机网络中有广泛的应用 , 例如电视会议、多媒体教学、视频点播、网上拍卖等 1建立实时组播的路由就是找到一棵以源结点为树根、包含所有目的结点的路由树 , 并且从源结点 (树根到任一目的结点 (树叶的传输时间不超过给定的时限 , 路由树的总成本最小 1寻找这种路由树的问题是 N P 2hard 问题 , 现已有一些启发式方法 [1]1在 WDM 网络中建立实时组播连接的主要困难是 :(1 每个网络结点只知道与其相连的链路上可用的波长 , 没有任何结点具有全网的拓扑结构或可用波长的信息 1(2 只有当路由请求到达一个结点时 , 才知道是否需要进行波长转换 , 而波长转换时间是不可忽略的 , 可能会使所选路径超过延迟时限而无效 1 (3 延迟和成本因素是相互独立的 , 具有最小成本的路径可能具有很长的延迟 , 反之亦然 1本文提出了一个在 WDM 网络中建立实时组播连接的分布式路由与波长分配算法 1该算法首先构造一棵最小成本树连接满足延迟限制的目的结点 1对没有连入最小成本树的结点 , 利用构造一棵最短延迟树 , 使其包含所有其余目的结点 1然后 , 将两棵树合并成一棵统一的树 1:,; ③所构造的树在满足延迟时限的条件下具有接近最优的成本 12问题定义网络用无向图 G (V , E 表示 , 其中V ={1, 2, … , N }为结点集 , E ={(i , j }是光纤链路集 , 链路 (i , j 可能包括多条光纤 , 编号为1, 2, … , k 1每条链路 (i , j 有 3个参数 :① σk ijΑ{1, 2, … , W }表示链路 (i , j 的光纤 k 上当前可用波长的集合 ;② c ij 表示使用链路 (i , j 的成本 ;③ d ij 表示链路 (i , j 的延迟时间 1链路 (i , j 上的可用波长是动态变化的 , 只有与此链路相连的两个结点确切知道当前σk ij 的值 1在建立连接时 , 为该连接的每一链路分配一根光纤及该光纤上一个当前未被使用的波长 1被分配的波长一直被占用 , 直到通信结束连接被终止 1网络中结点具有光纤交换功能 , 即从一根光纤上输入的光信号可以从输出链路的任一光纤上输出 1只有部分结点具有波长转换器 1同时假定每个波长转换器可以将任一波长转换为任一其他波长 1 R [i ]=1表示结点 i 有波长转换器 1在一条路径上的通信延迟包括链路延迟和波长转换时间两部分 1链路延迟 d ij 表示信号从结点 i 经链路 (i , j 到达结点 j 所需的时间 1波长转换时间d c i (λx , λy 表示结点 i 将波长λx (输入波长转换为波长λy (输出波长所需的时间 1假定所有波长转换器完成任何两个波长之间的转换所需时间是相同的 1如果没有进行波长转换 , 即λx =λy , 则d c i (λx , λx=01如果结点 i 没有波长转换器 , 且λx ≠ λy , 则d c i (λx , λx =∞ 1考虑建立组播连接的实时请求R =(s , D , Δ , 其中 s 是源结点 , D 是目的结点集合, Δ是延迟时限值 1组播连接是一棵树 T , T 的总成本定义为 COS T (T =(i , Tc ij 1(1 令 P (u , v T u 到结点 v 的 , u D EL A Y (u , vY (u , v =∑(i , j ∈ P (u , vd ij +∑i ∈ P (u , vd c i (λx , λy 1 (2 从树根 s 到任意结点 v 的延迟记为 D EL A Y (s , v , 树 T 的延迟定义为DEL A Y (T =max {DEL A Y (s , d , Πd ∈ D}1 (3 延迟时限条件可以表述为D EL A Y (T ≤ Δ1(4 本文所考虑的问题是设计一个分布式的路由和波长分配算法来构造一棵波长路由树 , 使得该树在满足式 (4 定义的条件下成本尽可能小 13相关研究成果最小成本树是 Steiner 树 , 加上延迟限制后 , 寻找带延迟限制的 Steiner 树是 N P 2hard 问题 [1]1关于构造最优组播树的研究已有一些结果 [1,2], 但这些结果并不能直接用于 WDM 网络 1目前关于 WDM 网络的路由与波长分配的研究主要是针对点到点通信的 1如Spath 提出了几种路由策略 [3],Jia 等人提出了一种针对静态请求、旨在使波长转换最少的 k 2cut 方法 [4]1在 WDM 网络中 , 路由算法应以链路上当前可用波长为基础 1Sahasrabuddhe 等人提出的光树概念 [5],Li [6],Pankaj [7]等人分别提出的计算需要最少波长数的路由树的方法 ,Jia 等人提出的一种为一组静态组播请求分配路由的算法 [8], 都为组播路由与波长分配问题提供了有益的借鉴 1但所有这些关于 WDM 网络的研究都是将路由 (构造树与波长分配作为独立的过程对待 , 或者假定网络状态、参数是静态不变的或具有特定的拓扑结构 1对一般的 WDM 网络上的组播它们并不适用 14分布式算法411算法基本思想本文所提出的分布式算法由两部分组成 : G enCtree 和 G enDtree 1G enCtree 以 Prim 的 MST 算法为基础 , 构造一棵最小成本树 Ctree 1其工作过程是 :每次选取一个离树最近 (按成本计算的结点 , 如果其延迟满足约束条件 , 则将其加入到树中 1如果 G enCtree 能将所有目的结点加入到 Ctree 中 , 则算法终止 1否则 , 调用过程 G enDtree1 G enDtree ,构造 Ctree 后 , 1在 1因此必须消除 Ctree 中的某些边以保证树的性质 , 同时满足延迟条件 1412数据结构路由表 CRoutab 和 DRoutab :每个结点都保存有成本路由表 CRoutab 和延迟路由表 DRoutab 1路由表中的项 CRoutab [d ]/DRoutab [d ]表示到达目的结点 d 的最小成本 /最小延迟及其可能的输出链路 , 其中第 1个链路为主链路 , 其余链路为候选链路 1路由表可以使用距离向量路由算法计算得到 1目的结点到树的距离 :在构造树时 , 为每个目的结点记录一个三元组〈 t reenode , dest , dist 〉 , 用于跟踪每个目的结点到已经构造的树的最短距离 1〈 t reenode , dest , dist 〉表示到目的结点dest 的最短距离是 dist , 它通过树上结点 t reenode 连接到树中 1可用波长链路数NL (λ :每个结点记录与其关联的链路上的可用波长1NL (λ 表示与本结点相关联的链路中波长λ可用的链路总数 , 每根光纤计算为 11413最小成本树 Ctree 的构造(1 Ctree 的构造算法 G enCtree①源结点 s 启动 G enCtree , 将 s 加入到 Ctree 中 1② s 利用 CRoutab 选择一个最近的目的结点 , 选择通往该目的结点、具有可用波长的一条输出链路 1如果主链路没有可用波长就选择一条候选链路 1然后通过所选择的链路向下一个结点发送一个 CFIND 消息 1③下一结点收到 CFIND 消息后 , 使用相同的方法选取通往选定的目的结点的输出链路 , 直到到达目的结点 1④ CFIND 消息在传递过程中收集从所构造的部分树到其他目的结点的最短路径的信息 1CFIND 消息所到达的目的结点通过所收集的三元组信息负责选取下一个加入到树 Ctree 中的目的结点 dest 及其相应的在树上的连入结点 t reenode , 然后向该树结点发送一个消息 , 由该树结点启动路径〈 t reenode , dest 〉的建立过程 1⑤每当 CFIND , 该目 Ctree 中的目的结点 1,, 并通知其进行相应的操作 1⑥重复上述过程直到没有目的结点可以加入到树中 , 这时 , 调用 G enDtree 过程 1G enCtree 用于选择目的结点的标准是最小成本 1树 Ctree 与目的结点 d 之间的最小成本距离定义为DIS T (Ct ree , d =min {COS T (t , d , Πt ∈ Ct ree , d ∈ D 2Ct ree}1(5 设所选择的输出链路为 (v , w , 则从源结点 s 经 v 到达 v 的邻结点 w 的延迟 DEL A Y (s , w 定义为 D EL A Y (s , w =D EL A Y (s , v +d vw +d c v (λv , λw , (6 该延迟在结点 v 进行计算并测试 1如果试探失败 , 发现失败的结点负责通知源结点 , 然后另外选取一个目的结点开始其连入树的操作 , 同时释放为失败的路径所预留的波长 1(2 G enCtree 的波长分配策略选择输出链路的结点负责进行分配波长 1波长分配策略为 :①输出链路任一光纤上与输入链路上相同的波长可用时 , 优先分配该光纤及波长 ;②如果该波长在所有光纤上不可用 , 则选择具有最大 N L (λ 值的波长及具有该波长的第 1根光纤 1 414最短延迟树 Dtree 的构造(1 Dtree 的构造算法 G enDtreeG enDtree 以源结点 s 为树根 , 将所有没有包含在 Ctree 中的目的结点连接起来构造一棵最短延迟树 Dtree 1在构造 Dtree 时 ,G enDtree 需考虑 3个因素 :①当最短延迟树存在时 , G enDtree 必须能够以很高的概率构造成功 ;② G enDtree 必须简单、执行速度快 , 以便能快速完成组播连接的建立 ;③所构造的延迟树 Dtree 应该易于与成本树 Ctree 合并 1Dtree 和 Ctree 可能有公共链路和结点 , 合并可能会产生回路 1G enDtree 以并行方式运行 , 构造算法为 :①对剩余的每个目的结点 d , 源结点 s 从 DR outab[d ]中的每个输出链路上发送 DFIND 消息 1②在每个中间结点 , 采用受限扩散方式 , 最多选取 K 条输出链路转发 DFIND 消息 , 直到选定的目的结点被连入 Dtree 树中 , 或者是因不能满足延迟条件或无可用波长而终止 1在中间结点 v , 选取到达目的结点 d 的输出链路的标准是到达 d 的最小延迟 1vw 的评价函数为f (w = D EL A Y (v -w Y (s (v , c v (v w ≤ Δ, ∞ , 1(7③当 DFIND 消息第 2次到达一个结点时 , G enDtree 采取下述方法处理重复的消息 :・如果本结点先前收到过 DFIND 消息 , 并且当前收到的 DFIND 消息与先前的 DFIND 消息来自不同的输入链路 , 则在两条输入链路中选择具有较长输出延迟(离开延迟的链路从树中删除 1・如果本结点的一个或多个子结点及其链路已经由先前的 DFIND 消息加入到树 Dtree 中 , 但当前的 DFIND 消息没有选择它们加入到 Dtree 中 , 则 G enDtree计算到这些邻结点的延迟以决定是否将它们保留在 Dtree 中 1决定取舍的标准是新的延迟 (当前 DFIND 消息计算结果是否比原延迟小 1当 Dtree 的一条旧链路被确定删除时 , 该链路以后的子树一同被删除 1④每个成功加入到 Dtree 的目的结点向源结点发送一个 DFOUND 消息 , 以通知源结点当前的进展状况 1(2 G enDtree 的波长分配策略①如果所选择的链路已经是 Ctree 的一条链路 , 则使用在 Ctree 中已分配的波长 ;②如果所选择的链路已经是 Dtree 的一条链路 , 则可以根据需要重新分配波长 ;③如果所选择的链路是一条新链路 , 则按 G enCtree 的分配策略进行分配 1415 Ctree 和 Dtree 的合并Ctree 和 Dtree 建立之后 , 需要将它们合并为一棵单一的树 1源结点 s 沿 Ctree 和 Dtree 的所有链路发送一个 M ER GE 消息开始合并操作 , 该消息被逐结点地进行处理 , 直到到达目的结点 1合并算法可简述为 :①如果 Ctree 和 Dtree 在结点 x 相交 , 并且分属于 Ctree 和 Dtree 的输入链路不同 , 则去掉 Ctree 的输入链路 1Ctree 中 x 的所有后继结点重新计算延迟时间 ;②如果沿合并的新树的路径不满足延迟条件 , 则算法失败终止 ;, 则 Ctree 中 , 直到到与 Dtree 的相交结点 1结论 11所构造的树包含源结点和所有目的结点 , 并且满足约束条件式 (4 , 同时具有接近最小的成本 1证明 1显然 , 所构造的树包含源结点和所有目的结点 1算法的每一步往树中增加一条链路及对应的对端结点 , 从源结点 s 到新增加结点的路径延迟不超过延迟时限 1所以从源结点到达每个目的结点的路径延迟都满足延迟约束条件式 (4 1由于 G enCtree 每次增加一条最小成本的路径到树中 , 因此每次加入到树中的是从树到目的结点的最小成本路径 1只有 G enDtree 增加的路径不具有最小成本 , 根据 Prim 算法可知 , 总的成本接近最优 1如果初始波长或者波长分配策略选择不当 , 可能会导致大量的波长转换 , 从而可能导致路径延迟超过时限 1尽管本算法在可能时试图替换部分链路或路径 , 但因为它并不为已经构造的部分树重新分配波长 , 因此仍然有可能最终不能构造出一棵满足要求的树 1当进行 Ctree 和 Dtree 的合并时 ,Ctree 的一些链路可能会被删除 , 这可能导致合并后的树无效 , 而算法并没有试图为删除的目的结点寻找候选路径 1因此存在着虽然有解但找不到解的可能 1但由于算法使用的是启发式方法 , 即选取最少转换和最小负载的方法为链路分配波长 , 因此上述情况通 764110期黄传河等 :WDM全光网络中实时组播的分布式路由与波长分配算法常可以避免 1证毕 1结论 21算法的通信复杂性是 O (n 1证明 1在 G enCtree 的路由选择过程中 ,CFIND , CFOUND 等消息的总数分别不超过 O (n , 最坏复杂性为 O (n 1在 G enDtree 中 ,DFIND 消息是以并行扩散方式传输的 , 最大消息数也是 O (n 1这样消息总数为 O (n , 所以通信复杂性不超过 O (n 1证毕 15模拟结果本文在模拟时 , 网络规模固定为 200个结点 , 网络拓扑随机生成并测试 , 直到生成一个连通的网络为止 1每条链路假定只有一根光纤 , 具有波长转换器的结点数为 50%且随机分布 1链路成本为 1~15之间的随机数 , 链路延迟为 1~10之间的随机数 , 光纤链路上的波长数为 81除非特别情况 , 假定 |D |为网络规模的 20%, 链路上波长的平均可用性定为 50%, K =11网络拓扑在模拟过程中保持不变 1本文模拟 3个算法进行比较 :SPT , MST 文提出的算法 dRWA 1SPT 和进行计算 , 成本 , D |组播连接建立时间 , 针对 |D |; , 针对波长可用性 1图 1说明了组播树成本与延迟时限Δ之间的关系 1SPT 和 MST 的曲线为常数 , 因为二者都不受Δ影响 1本文算法的曲线介于二者之间 , 其高端接近于 SPT 曲线 , 低端接近于 MST 曲线 1当Δ越小 , 越多的 MST 路径违反Δ限制而用 SPT 路径代替 1使得构造的树更宽 , 组播树成本就更高 1随着Δ的增加 , 更多的目的结点通过MST 路径连入树中 , 导致树的成本下降 1当Δ足够大时 , 不会影响路由选择 , 最终的组播树变成 MST1图 1不同Δ时的成本图 2说明树的成本与目的结点集大小间的关系 1当目的结点增加时 , 组播树包括更多的目的结点 , 导致树的成本增加 1SPT 曲线在其他两个曲线之上并上升得更快 1这是因为 SPT 不考虑路径共享 1本文算法的性能接近 MST , 二者的曲线随目的结点集的增大而增加得非常缓慢 , 因为目的结点集大 , 共享路径的可能性就大1图 2不同 |D |时的成本图 3说明树的成本与波长可用性之间的关系 1当波长可用性增大时 , 每条链路上有更多的可用波长 , , 进行波 , 降 1, (214个可用波长 , 组播树的成 1也就是说 , 当网络的负载不超过 70%时 , 路由选择与波长分配受负载影响较小1图 3不同波长可用性的成本图 4不同转换延迟的成本图 4说明树的成本与相对转换延迟之间的关系 1相对转换延迟是指波长转换时间与全网的平均链路延迟的比值 1结果显示 , 用 SPT 及本文算法构造树的成本随相对转换延迟的增加而非常缓慢地增加 ,MST 树的成本是常数 1本文算法的曲线几乎与8641计算机研究与发展 2003年10 期黄传河等 : WDM 全光网络中实时组播的分布式路由与波长分配算法1469 MST 曲线重合 , 说明当延迟时限给定之后 , 转换延迟时间主要影响建立连接的成功率 , 而对组播树成本的影响较小1 增大相对转换延迟的效果类似于减小延迟时限Δ1 图 5 说明建立连接时间与目的结点集大小之间图5不同| D | 的建立时间选择与波长分配的影响 ,并且是完全分布式的1 对于 WDM 网络中波长转换器只有部分波长转换能力的情况本文没有考虑 , 对此需要做进一步的研究1 参考文献1 Bin Wang , J C Hou1 Multicast routing and its QoS extension : (1/ 2 : 22～36 2000 , 23 (9 : 848～862 works , 2000 , 4 : 260～265 414～424 cations , 2001 , 49 (2 : 341～350 networks1 In : Proc of t he 9t h ICCCN , 20001 621～624 IEEE Communications Magazine , 1999 , 37 (2 : 67～73 X Jia , D Du , X Hu et al 1 Optimization of wavelengt h assignment 的关系1 建立时间是指最长路径上各链路的链路延迟时间的总和 ,没有计算波长转换时间1 当| D | 增大时 , 建立时间随之增大1 因为 D 是随机产生的 , 可能分布在全网范围 , 因此建立时间的增长速度远小于| D | 的增长速度1 2 3 4 5 6 图6 说明相对转换次数与波长可用性之间的关系1 相对转换次数是指总的波长转换次数与树中链路总数 ( 即所用波长的总数的比值 , 也就是平均链路 ( 即波长的转换次数1 当波长可用性增大时 , 每条链路上的可用波长增加 ,波长转换就会减少1结果显示 ,本文算法所进行的波长转换比 MST 少 , 但比 SP T 多1 当波长可用性很低时 , 需要进行波长转换的概率非常高 ,波长转换的累计时间会显著增加 ,因此会导致建立连接失败的概率增大1 7 8 图6不同波长可用性的波长转换次数 6结论本文提出了一种在 WDM 网络中建立实时组播连接的方法 ,该方法构造一棵满足延迟时限并具有接近最小成本的组播树 , 同时为树中的每条链路分配光纤与波长1该方法考虑了波长转换时间对路由 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. J Spat h1 Dynamic routing and resource allocation in WDM trans2 port networks1 Computer Networks , 2000 , 32 (4 : 519～538 signment met hod for minimal wavelengt h conversions in WDM ing for improved performance in wavelengt h2routed networks1 cal networks1 IEEE/ ACM Trans on Networking , 1999 , 7 ( 3 : Deying Li , Xiufeng Du , Xiaodong Hu et al 1 Minimizing number for QoS multicast in WDM networks1 IEEE Trans on Communi2 L H Sahasrabuddhe , B Mukherjee1 Light trees : Optical multicast2 R K Pankaj1 Wavelengt h requirements for multicasting in all2opti2 X Jia , Ding2zhu Du , Xiao2dong Hu et al 1 A new wavelengt h as2 of wavelengt hs in multicast routing trees in WDM networks1 Net 2C P Low , Y J Lee1 Distributed multicast routing wit h end2to2end delay and delay variation constraints1 Computer Communications , Problems , algorit hms and protocols1 IEEE Network , 2000 , 14 黄传河 ,1963 年生 , 教授 , 博士生男导师 ,主要研究方向为计算机网络、分布并行处理、量子计算1 陈莘萌 ,1939 年生 ,教授 ,博士生男导师 ,主要研究方向为分布并行处理、新型计算机理论1 贾小华 ,1962 年生 ,教授 ,博士生男导师 ,主要研究方向为计算机网络、分布式系统1 。

2004年4月第9卷　第2期 西　安　邮　电　学　院　学　报JOU RNA L OF XI 'AN U NI VERSIT Y O F POST AN D T ELECOM M UN ICAT IO NS A pr .2004V ol .9N o .2收稿日期:2003-08-09作者简介:康巧燕(1980-),女,福建永春人,空军工程大学电讯工程学院硕士研究生。

李维民(1960-),男,陕西西安人,空军工程大学电讯工程学院副教授。

种满东(1978-),男,陕西紫阳人,西安电子科技大学电子工程学院硕士研究生。

WDM 波长连续光网络中路由和波长分配算法研究康巧燕1,李维民1,种满东2(1.空军工程大学电讯工程学院,陕西西安　710077;2.西安电子科技大学电子工程学院,陕西西安　710071)摘要:在对W DM 波长路由光网络的路由和波长分配算法进行研究的基础上,提出一种新的自适应动态路由算法和考虑通道优先级及波长容量损失的波长分配算法,并给出具体分析及实现步骤。

该算法能有效地利用网络资源,保证负载分布的平衡,并能较好地兼顾网络资源分配的合理性。

关键词:光传送网;路由和波长分配;光通道;相对容量损失中图分类号:T N 913.7 文献标识码:A 文章编号:1007-3264(2004)02-0089-04引言在WDM 光传送网中,给定一组全光连接请求条件下,寻找源节点到目的节点的路由并给这些路由分配波长的问题称为路由和波长分配(RWA ,Routing and Waveleng th Assignment )问题。

WDM 光网络的一个核心问题就是如何选择有效的算法和协议来建立光通道,也就是如何解决RWA 问题。

在考虑到技术条件和网络建设成本的条件下,设计出一个好的RWA 算法,对减少网络阻塞概率、光通道通信所需的波长数,提高资源利用率及网络抗毁能力具有重要意义。

本文对WDM 波长路由光网络的RWA 算法进行了研究和总结,在此基础上,提出一种新的自适应动态路由算法和考虑通道优先级的波长分配算法。

波长路由光网络中的路由和波长分配算法研究的开题报告一、选题背景光通信技术始于20世纪80年代，随着带宽的快速增长和网络规模的不断扩大，光网络已成为当前和未来网络的发展趋势。

波长路由光网络是一种光网络结构，可以更好地利用光纤的带宽和传输特性，使网络具有更大的容量、更高的传输速率和更强的抗干扰能力。

因此，如何设计有效的路由和波长分配算法来实现光网络的高效和优化就成为了当前光通信领域的一个重要研究领域。

二、研究目的和意义随着光网络的持续发展和应用，传统的电路交换模式已经不能满足光网络的高速和多业务需求，因此波长路由光网络成为了光网络发展的一个重要方向。

波长路由光网络中的路由和波长分配算法是实现高效和优化通信的关键技术，因此开展波长路由光网络中的路由和波长分配算法研究对于光网络的发展和应用具有重要的意义。

三、研究内容本次研究将围绕波长路由光网络中的路由和波长分配算法这一主题展开，研究内容包括：1.波长路由光网络拓扑结构分析和建立。

2.分析波长路由光网络中的路由和波长分配技术，对常见的路由和波长分配算法进行比较和综合分析。

3.提出一种基于网络流的新型路由和波长分配算法，进行算法的设计和优化。

4.通过仿真实验和性能测试来验证所提出的路由和波长分配算法的有效性和优势。

四、预期研究成果1.完成波长路由光网络中路由和波长分配算法的研究，建立相关模型和仿真实验平台。

2.设计并实现基于网络流的新型路由和波长分配算法，对该算法进行优化。

3.通过对比实验，证明新型算法在性能表现上的优越性。

五、研究所需的条件和资金1. 研究所需的条件：（1）具备光通信和网络基础知识和技能，熟悉相关的光网络协议和算法。

（2）熟练掌握MATLAB等相关仿真软件的使用。

2.研究所需的资金：研究所需的资金包括技术设备、人工费等方面的支出，初步预计所需资金约为10万元。

六、研究进度安排1. 第一阶段（前三个月）主要任务：（1）文献调研：查阅相关文献，了解波长路由光网络及路由和波长分配算法的基本原理和发展现状。