波长路由全光网络动态RWA算法研究

波长路由全光网络动态RWA算法研究 湖 南 工 程 学 院 学 报 Vo1. 12. N .o 4 第 12 卷第 4 期 2002 年 12 月Dec . 2002 Journal of Hunan Institute of Engineering 波长路由全光网络动态 RWA 算法研究 ? 敏 , 郑善贤 何 ()湖南大学电气与信息工程学院 ,湖南 长沙 410082 摘 要 : 研究了波长路由全光互联网的动态路由和波长分配算法. 提出了一种新的动态 RWA 算法 ,此 算法能有效地利用网络资源 ,并保证负载分布的平衡 ,引入优先级的波长分配策略很好地兼顾了网络资 源分配的合理性. 关键词 : 波长路由 ;动态 RWA 算法 ;平衡 中图分类号 : TP393 . 4文献标识码 : A() 文章编号 : 1671 - 119X200204 - 0012 - 04 ( ) 交换网络无向多图 undirected multigraph的模型上 , ( 在该模型中首先为每个光路请求找出最佳路由 如 0 引言 ) 最短路径, 然后分配波长 . ( ) ( ) 全光网动态路由和波长分配 RWA算法作为 还有一种建立在不相交子图 disjoint subgraph实现全光通信的关键技术之一 ,是指在实时业务条 模型上的求解动态 RWA 问题的路由和波长分配分 件下为光通道进行路由选择并分配一定的波长. 光 解法. 但是由于不相交子图模型中每一个子图是单 通道的建立请求随机到达或离开网络 ,即业务是动 独考虑的 , 因而无法决定哪一条光路请求应分给哪 态的 ,常用的优化指标是阻塞概率. 在考虑到技术条 个子图 , 才能使光网络所能提供的光路数最大 .件和网络建设成本的条件下 , 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 出一个好的 RWA 如果网络的规模不是很大 , 可以考虑采用分层 () 算法 ,对减少网络阻塞率 、提高资源利用率及网络抗 图 layered - graph的模型将选路和波长分配一步完 [2 ] 毁能力是有重要意义的. 成 , 此类 RWA 算法称为路由和波长分配平行法, 动态 RWA 问题成为在分层图的各层中选取一条通 本文对无波长转换的波长路由的 WDM 全光网 络的动态 RWA 算法进行了研究和总结. 文章的最 道的问题. 所谓分层图模型是将网络拓扑中的全光 后提出了一种新的动态 RWA 算法 , 此算法能有效 部分复制层 , 每一层对应有限波长集合中的一个波 地利用网络资源 ,并保证负载分布的平衡 ,在波长分 长 . 每一个接入节点被复制为两份 , 一份作为发送节 配策略中引入优先级 ,较好地兼顾了网络的资源分 点 , 另一份为接收节点. 对分层图中各中间节点和接 配的合理性. 入节点进行编号 , 将第 K 层的 N 个顶点依次编为 ( ) K - 1N + 1 到 KN , 源节点编号为 0 , 目的节点编号 ( ) 为 WN + 1. 编号为 K - 1N + i 的第 K 层的顶点对 1 动态 RWA 算法模型 应物理节点 i . 应用分层图模型 , 能够明显地简化动 从总体上看 , RWA 中的路由和波长分配是不可 态 RWA 问题的复杂性 , 凡是分层图中边不相交的 ( 分割的. 但是 , 由于 RWA 是个 NP - C 非确定型多项 路径都能保证物理光网络中的波长连续性. 仿真表 ) 式 —完 全 Nondeterministic polynomial - Complete 问 明 , 采用较好选路算法的分层图法比将选路和波长 [1 ] 题, 要在合理的运算时间内解决大型网络的 RWA [2 ] 分配割裂的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 阻塞率小.问题是不可能的 , 所以常常强行拆成两个独立的子 问题分别解决 , 即 :一是按照某种优化目标寻找源和 目的节点对的路由 ; 二是在满足一定优化性能的情 2 路由子问题 况下为这些路由分配波长 , 此类 RWA 算法称为路 由和波长分配分解法. 它们大多建立在传统的电路 解决路由子问题的方法大致为三类 :固定路由 ( ( ) FR : Fixed Routing、替换路由 FAR : Fixed - Alternate ? 收稿日期 :2002 - 10 - 17() 作者简介 :何 敏 1977 - ,女 ,硕士研究生 ,研究方向 : WDM 光传送网络体系结构 、路由和波长分配算法. () ) Routing、自适应路由 AR :Adaptive Routing. 资源的分布保持均衡. 仿真表明它优于已有的 DMH 固定路由是三种路由方法中最简单的 , 它是指 和 MU 算法. 当光路请求到达时 , 为任意源 、目的节点对根据一定 的 原则 组织架构调整原则组织架构设计原则组织架构设置原则财政预算编制原则问卷调查设计原则 指定唯一的路径 , 如果存在多个符合 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 的 3 波长分配子问题 路径 , 则在其中随机选取一个 , 并在相应的固定路由 上分配波长以建立光路. 如果采用 FR 路由 , RWA 问 在没有波长转换器的波长路由网络中的波长信 ( ) 题就可以简化为波长分配问题 , 从而大大简化网络 道 WP分配主要受两个限制 : () ( 的控制和管理 . 但是如果在一个设计的通道上没有 1 波 长 连 续 限 制 Wavelength Continuity Con2 ) 可利用的波长 , 甚至在产生连接要求时 , 对该连接而 straint:波长路由网的节点对之间所建立的光路必 言存在一个具有空闲波长的不同的路由 , 这个连接 须在其路由的所有链路上使用同一波长. () ( 2不 同 信 道 分 配 限 制 Distinct channel assign2 都将被阻塞. ) 替换路由是指根据一定的原则为所到达的连接 ment Constraint:即一根光纤上的不同光路不能使用 请求分配一个可行通道的集合. 当连接请求到达时 , 同一波长. 按一定的顺序检查预定的各条备用路由 , 以寻找合 如果网络中存在稀疏波长变换器 , 则在每一个 适的路由并在其上分配波长. 与固定路由相比替换 包含有波长变换器的节点上就不存在波长连续性的 限制 , 因此 , 就可以在不同的通道段上分配不同的波 路由减小了阻塞率. 自适应路由最复杂 , 但是其性能最优 . AR 无需 长 . 对于全波长变换器 , 只要在通道上的每根光纤上 ( 预定路由 , 它根据网络的资源占用情况动态地为呼 至少存在一个未被利用的波长 并不一定为相同波 ) 叫选定路由. 为每个随机到达的连接请求进行实时 长, 就可以说存在可用信道 , 称此时的信道为虚波 () 长通道 .的计算以找出符合要求的路径 . 这便意味着必须全 VWP 被分配的波长一般取自波长列表 , 波长列表是 面了解网络的状况. ( ) 一般的路由问题大多基于最短路径算法 , 通过 按照利用的情况 波长产生的有效连接数量的减序 设置不同的链路权重 , 可以得出不同优化目标的算 或增序来进行排序. 前面的这种情况称为最大再用 () ( 方法 , 后 面 的 称 为 最 小 再 用 方 法 法 . 如果网络的总负载较重 , 那么一般根据节点间的 Max ReuseMin ) 实际距离或节点间跳数设定链路权重 , 对应的算法 Reuse. 在波长分配阶段 , 总是试图为被选的通道从 如最小跳数路由 、最短距离路由 波长列表的顶端开始向下寻找一个可用波长 , 由于此类算法尽可 . 在最 能少地占用网络资源 , 因而在网络上能建立尽可能 大再用的情况下 , 首先选择应用最多的波长 , 它保证多的连接. 如果网络总负载较轻 , 则根据链路上所承 在应用其他波长之前尽可能多地再用有效的波长 , 载的负荷量设定链路权重 , 算法往往选择具有最大 这便使得在一个长通道上得到满足波长连续性信道 空闲容量和的路由以保证总负载平衡 . 如果网络需 的可能性更大 . 在最小再用的情况下 , 它是在所有可 利用的波长上尽可能地平均分配承载业务. 模拟试 要重点考虑功率和噪声限制因素 , 链路权重的选择 将正比于链路的衰减 , 算法得到链路总衰减最低的 验表明 , 在波长路由光网络中 , 最大再用的情况效果 [ 4 ] 较好.路由. 关于波长分配问题 , 近年来已经提出了许多著 文献 3 提出了一种基于 FR 和 AR 的混合式路 [4 ] [3 ] 名的算法 , 如 First - fit 波长分配算法, 在为新的光 由解决方案. 此方案首先为每一个节点依据最短 时延或最短路径建立的路由信息表 , 再每隔一段时 路请求建立连接时 , 算法按照预先为网络定义的波 间 , 动态地更新网络节点的路由信息表 , 如果网络中 长顺序进行波长搜索 , 并分配第一个找到的波长 . 此 某条链路失效或超负载 , 假设其链路权重为 ?, 并重 算法并不考虑网络的当前状态 , 但是简单 ; Least - 6 新计算 各 节 点 的 最 佳 路 由 表. 此 算 法 优 于 传 统 的 Loaded算法选择可用路径中可用信道数最多的波 [5 ]FR 、AR 算法 , 并能有效地处理链路故障 , 使网络具 长 ;MaxSum 算法在选择波长时保证分配该波长后 [7 ] 全网可用信道数最大 ; Least Effect 算法是一种全 有部分自愈能力 , 增强了网络的生存能力. 湖南工程学院学报 2002 年 14 具体的算法流程如下 : G, G指以路径为顶点 , 在路由存在交叠的路径代 PI PI 表的顶点之间建立边得到的图形 , 则波长分配问题 () 首先为网络预热 , 根据 1式设置链路权重 ;就相当于图论中的干涉图着色问题 , 实际所需的波 STEP1 :等待光路请求 ,如果请求为建立连接转[7 ] 长数等于路径图的顶点颜色, 约束条件是相连的 STEP2 ,如果请求为拆除连接 ,转 STEP5 ;节点不能采用同一颜色 . 但是随着网络中节点和光 STEP2 :根据到达请求的节点对 ,按 Dijkstra 算法 纤数量的增加其可能在通道数量呈指数规律增长 , 计算各节点对之间的最轻链路权重总和路径 ; 因而此方法只适用于网络规模不大的情况下. STEP2 . 1 :如果找到的路径上所经过的链路总权 重为 ?,则拒绝请求 ,转 STEP5 ; STEP2 . 2 :如果找到的路径上所经过的链路总权4 提出的新算法 重为有限值 ,则接收请求 ,转 STEP3 ; 在对动态 RWA 算法进行分析和研究中 , 设定 STEP3 :根据所分配的路由 通 道 长 度 来 确 定 波 节点对间的业务量是均匀业务 , 光路建立请求以泊 长分配的优先级别 ,在相应的级别中为连接请求分 松过程随机到达 , 一旦建立光路则其持续时间服从 配一个波长 ; 指数分布 , 而且平均持续时间大大超过网络传输时STEP3 . 1 :如果此级别中有空闲波长 ,遵循最大 延以及连接建立时间 , 每个节点有足够多的收发器.再用原则为路由分配波长 . 转 STEP4 ; 已经提出的 RWA 算法大都只是考虑了某一个 STEP3 . 2 :如果此级别中无可用的波长 ,可以考 方面的优化问题 , 如最短路径或是最小跳数算法考 虑低 优 先 级 别 的 波 长 , 如 果 仍 没 有 , 拒 绝 请 求 , 转 虑的是网络占用资源最少和通讯的延时最短 , 忽略STEP1 ; 了负载的平衡 , 从而导致某些链路上过于拥挤 , 使得 () STEP4 :根据公式 1刷新链路 ,转至 STEP1 等待 全网的总阻塞率升高 ; 负载平衡算法过于强调业务 下一个请求. 量的均衡分配 , 忽略了通讯时延和网络资源有限所 () STEP5 :释放电路 ,根据公式 1刷新链路权重 ,带来的性能下降 , 在网络负载较重的情况下导致总 转 STEP1 等待下一个请求. 阻塞率上升 ; 同时 RWA 算法的规则使得长通道遇 到阻塞的可能性大于短的通道 , 这便导致相对较远5 结论 的节点对之间连接的不公平对待问题 . 以下提出的算法是自适应动态路由算法 , 进行 以上的动态 RWA 算法 , 不仅能有效地利用网 络资源 ,而且保证了负载分布的平衡 ,同时兼顾了网 路由时将综合考虑路径的长短和负载平衡问题 , 网 络资源分配的合理性. 但是它并未涉及到光网络健 络的公平性策略可以在波长分配时实现. 本算法的壮性问题. 光网络的抗毁十分重要. 如果只考虑光传 思想基于 Dijkstra 算法 , 但将链路权重设定为 :送网本身抗毁 ,可以分成保护和恢复两种机制 :保护 ( )1 C= d+ ?b ij ij ij机制是为每一条工作光路准备一条备用光路 ,要求 其中 d为节点对 i , j 之间的链路实际距离 , 当 这两条光路不会在一根光纤断裂时同时失效 ,解决 ij 的算法类似于替换路由算法 ; 恢复机制是在网络有 将每条链路的距离权重定为 1 时 , 节点间的距离就 故障造成某一条光路失效时 ,根据网络状态实时地 等同于节点对间路由经过的跳数 , b为当前时刻链 ij 重新构造一条光路 ,这种方法实现较复杂 ,同时也需 路上已被占用的信道数 , 也就是链路的负载 , 如果该 要网络有一定的冗余容量. 同时多光纤网的容错能 链路上已无可用的波长信道 , 置 b为 ?. ?为一个 ij 力和抗毁性都要优于单光纤网. 加权系数 , 它用于表征路径距离和负载平衡各自在 链路代价选取中所占的比重 , 在进行算法设计过程 中 , 可以根据实际需求进行选取. 链路权重的设定保 参 考 文 献 证算法在为某一连接请求选择路由时不仅仅考虑最 短路径或最小跳数 , 同时兼顾网络负载平衡.1 Chlamtac I ,etal . Lightpath communication :an approach to high 在波长的分配地问题上 , 首先将网络可用的波 ( ) bandwidth optical WANs. IEEE Trans Comm , 1992 , 40 7: 长分为 n 个优先等级 , 可根据网络的具体情况适当 1171 - 1182. 徐世中 ,李乐民 ,王晟. 多光纤波分复用网动态路由和 地设置通道长短的优先级别 , 将不同长度的通道划2 () 波长分配算法 J . 电子学报 ,2000 ,28 7:23 - 27. 分到各个优先级中 , 一般长通道具有较高的优先级. 3 罗启彬等. 波分复用光网络中的波长路由分配策略 J . - 196. () 电子学报 ,2001 ,29 12:1628 - 1630. 徐世中 ,李乐民 ,王晟. 固定选路的波分复用全光网中 6 () 的波长分配算法 J . 电子与信息学报 ,2001 ,23 3: 209 R. Ramaswami , K. N. Sivarajan. Routing and wavelength as2 4 - 213. signment in all - optical networks. IEEE/ ACM Trans. Net2 Thomas E. Stern Krishna Bala . Multiwavelength Optical Net2 () woking ,1995 , 3:489 - 500. 7 works A Layered ApproachM . 1999. 514 - 517. E. Karasan. Effects of wavelength routing and selection algo2 5 何荣希 ,李乐民 ,徐世中. WDM 光传送网中支持优先级 rithms on wavelength conversion gain in WDM optical net2 8 () 的波长分配算法J . 通信学报 ,2001 ,22 3:27 - 31. ( ) worksJ . IEEE/ ACM Trans on networking ,1998 ,6 2: 186 Dyna mic RWA in Wavelength Routing All - optical Net works HE Min ,ZHENG Shan - xian ( )College of Electrical and Information Engineering , Hunan Univ. ,Changsha 410082 ,China Abstract : Dynamic RWA algorithms in all - optical WRN are studied. A new dynamic RWA algorithm is proposed. This algorithm can make full use of network resourses and keep the network resourses in balance . The prority - based wave2 length assignment strategy takes the equitableness into consideration. Key words : WRN ;all - optical networks ; dynamic RWA algorithms ; balance