WDM光传送网的选路和波长分配算法

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光网中的一种邻域加权累积的波长分配策略袁俊岭;张迪;张启坤;李旭红【摘要】针对光核心传送网中单纤场景下的路由选择与波长分配(Routing and Wavelength Assign-ment,RWA)问题,提出了一种邻域加权累积的波长分配策略.在一条路径上为一个连接请求选择波长时,将网络的所有链路归入当前路径的不同邻域中,然后根据与路径之间的距离为不同邻域赋予不同的权重,进而对每个波长在全网中被占用的个数进行加权累积,最后选择累积值最大的可用波长建立连接.仿真结果表明,相对于现有的阻塞率最低的最大使用(Most-Used)波长分配策略,所提策略具有更低的阻塞率.【期刊名称】《电讯技术》【年(卷),期】2019(059)002【总页数】6页(P151-156)【关键词】光网络;波长路由;路由与波长分配(RWA);邻域加权累积(WNA)【作者】袁俊岭;张迪;张启坤;李旭红【作者单位】郑州轻工业学院计算机与通信工程学院,郑州450002;郑州轻工业学院计算机与通信工程学院,郑州450002;郑州轻工业学院计算机与通信工程学院,郑州450002;中原工学院理学院,郑州450007【正文语种】中文【中图分类】TN929.11 引言随着光传输和光交换设备的快速发展，全光交换已成为核心传输网中的主要交换方式，其中波长路由是最成熟和最简单的交换技术。

在波长路由技术中，路由选择和波长分配问题(Routing and Wavelength Assignment，RWA)一直是一个核心研究内容[1]。

RWA问题的主要任务是，为一个连接请求它选择合适的路由并分配合适的波长。

根据应用场景的不同，RWA问题可以分为两类[2]：静态RWA问题和动态RWA问题。

在静态RWA问题中，网络中节点之间的业务量以业务矩阵的形式事先给定，需要根据业务情况在每对节点之间建立路由并分配相应数量的波长，静态RWA问题的优化目标是使得网络中总共所需要的波长数最小。

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光网络中的组播波长分配算法研究吴启武，王建萍，周贤伟，宋宁宁(北京科技大学信息工程学院通信工程系，北京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]。

一、填空题
1.WDM光传送网利用（波长）组网，在光域完成信号的选路、交换。

2.全光网中任意两节点之间的通信是靠（光通道）完成的。

3.WDM光传送网中波长路由算法有两种，即（波长通道）和虚波长通道。

4.WDM光网络中的虚波长通道，每一节点采用的波长集下一节点可以实现（动态空间）复用。

5.WDM光网络中光放大段层为了实现长距离超高速传输，主要解决放大和光纤的（色散）问题。

6.波分光交换能充分利用光路的（带宽）特性，可以获得电子线路所不能实现的波分型交换网络。

7.波长光分组交换机分为三个功能块，即波长选路由功能块、（光缓存功能块）和光交换功能块。

8.全光网的管理信息主要有故障信息、（缺陷信息）和性能质量信息三种。

9.光网对不同的速率、协议、调制频率和制式的信号同时兼容，并允许几代设备（PDH/SDH/ATM/）甚至与IP技术共存。

10.WDM利用（光波长分插复用器WADM）可实现不同节点灵活地上、下波长。

11.WDM利用（光波长交叉连接WXC）实现波长路由选择，动态重构、网间互连和自愈功能。

12.光网对不同的（速率、协议、调制频率和制式）的信号同时兼容，并允许几代设备PDH/SDH/ATM/甚至与IP技术共存。

13、光交换是在（光域中）完成光交换功能，而无需将光信号转换成电信号。

14、全光型光分组交换机的光信号的（定时提取）可由（光锁相环OPLL）来完成。

第 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 算法进行了研究和总结,在此基础上,提出一种新的自适应动态路由算法和考虑通道优先级的波长分配算法。

光在真空的速度c=299792458m/sλ为光波长，如1550nm（n为10的-9次方）。

f为光波的频率，如192.10THz（T为10的12次方）物理学上有c=λ*f，即λ=c/f，波长跟频率是成倒数关系ITU-T(国际电信联盟电信标准部）定义了两套DWDM的波长使用原则，第一个是40波系统，从f1~f40分别是192.10THz、192.20THz、192.30THz。

196.00THz，频率从低到高，每个波道间隔0.1THz，也就是100GHz第二个是80波系统，从f1~f80分别是196.05THz、196.00THz、195.95THz。

192.10THz，频率从高到低，每个波道间隔0.05THz，也就是50GHz当f1=192.10THz时，λ1=c/f1=299792458m/s/ 192.10THz=1560.61nm当f2=192.20THz时，λ2=c/f2=299792458m/s/ 192.20THz=1559.79nm当f3=192.30THz时，λ3=c/f3=299792458m/s/ 192.30THz=1558.98nm当f4=192.40THz时，λ3=c/f3=299792458m/s/ 192.40THz=1558.17nm。

以此类推λ1-λ2=1560.61nm-1559.79nm=0.82nmλ2-λ3=1559.79nm-1558.98nm=0.81nmλ3-λ4=1558.98nm-1558.17nm=0.81nm。

你会发现光在1550nm这个频带内，频率的间隔和波长的间隔非常接近线性关系100GHz的频率间隔反映到波长上，就非常近似于0.8nm的宽度同理，50GHz的频率间隔反映到波长上，就非常近似于0.4nm的宽度同理，200GHz的频率间隔反映到波长上，就非常近似于1.6nm的宽度.归根结底就是因为波长跟频率是成倒数关系，那个常数就是真空中的光速c。

WDM光传送网中支持优先级的波长分配算法何荣希;李乐民;徐世中【期刊名称】《通信学报》【年(卷),期】2001(022)003【摘要】In this paper，a novel priority-based wavelength assignmentalgorithm ，Dynamic Threshold Method，is proposed.By using the algorithm，the blocking ra te of the high priority request is guaranteed to be a lower degree，and at the s ame time performance of the low priority request is improved.So the network's a verage blocking rate is minimized.Simulation results of the network performance show that the proposed algorithm performs well in different dynamic traffic load situation.%文中提出了一种用于WDM光传送网的支持优先级的波长分配算法——动态门限法，该算法保证了较高优先级的光路建立请求具有较低的阻塞率，同时又考虑到较低优先级的光路建立请求的性能优化，从而很好地降低了全网的平均阻塞率。

文中给出了计算机仿真结果。

【总页数】6页(P27-32)【作者】何荣希;李乐民;徐世中【作者单位】电子科技大学宽带光纤传输与通信系统技术国家重点实验室，四川成都610054;电子科技大学宽带光纤传输与通信系【正文语种】中文【中图分类】TN913.24【相关文献】1.抗毁WDM网络中支持多优先级的波长分配算法 [J], 王烨;李乐民;徐世中;王晟2.WDM网络中一种支持优先级的波长分配算法 [J], 张品;张仕俊3.WDM光网络中一种备用路由下支持优先级的波长分配算法 [J], 刘凤洲;潘炜;罗斌;孟超4.WDM网络中备用路由下支持优先级的一种新的波长分配算法 [J], 封国剑;范俊锋;高随祥5.部分波长可变WDM网中支持优先级的波长分配算法 [J], 刘海霞;王玲因版权原因，仅展示原文概要，查看原文内容请购买。

适用于WDM全光网的自适应路由与波长分配算法
李培源;赵艳梅;顾畹仪;周锡增
【期刊名称】《北京邮电大学学报》
【年(卷),期】2005(28)6
【摘要】对波分复用(WDM)全光网中的动态路由与波长分配问题进行了深入的研究,并提出了最小通道权重优先(MPWF)自适应路由与波长分配算法.MPWF设计了新的链路权重计算方法,通过整理当前链路状态和通道长度信息为业务计算路由.MPWF算法的设计既适用于波长变换网络,也适用于波长选择网络.仿真结果显示,与一些文献中提出的自适应路由与波长分配算法相比,MPWF算法可提高网络资源的利用效率,降低业务的阻塞概率.
【总页数】4页(P69-72)
【关键词】路由与波长分配;波分复用;波长路由;全光网
【作者】李培源;赵艳梅;顾畹仪;周锡增
【作者单位】北京邮电大学电信工程学院;重庆邮电学院;台湾元智大学
【正文语种】中文
【中图分类】TN929.11
【相关文献】
1.WDM波长连续光网络中路由和波长分配算法研究 [J], 康巧燕;李维民;种满东
2.WDM全光网络中的多播路由与波长分配算法 [J], 于周秋;刘三阳
3.WDM全光网自适应路由和波长分配算法 [J], 孙俊
4.WDM全光网络中实时组播的分布式路由与波长分配算法 [J], 黄传河;陈莘萌;贾小华
5.WDM波长路由光网络的波长分配算法 [J], 李勇军;李维民;王洪刚
因版权原因，仅展示原文概要，查看原文内容请购买。