WDM网络中基于最少波长转换次数的多播算法

WDM网络中基于最少波长转换次数的多播算法 WDM网络中基于最少波长转换次数的多播 算法 WDM网络中基于最少波长转换次数的多播算法 冉敏1,2高随祥徐葆 (中国科学院研究生院,北京100039) (中国科学院高能物理研究所,北京100049) E—mail:ranmin@sohu.com 摘要在WDM网络中,将使用不同波长的光通路连接起来需要进行波长转换.由于波长转换 器的成本较高,且使用 过多的波长转换器会增加传输时延,在进行波长路由分配时应尽可能减少波长转换的次数.文章提出了一种建立一棵多 播树的算法.该方法具有最少的波长转换次数,能有效地减少时延. 关键词WDM波长转换跳数多播 文章编号1002—8331一(2005)27—0154—03文献标识码A中图分类号TP301.6 AMulticastAlgorithmwithMinimalWavelength ConversioninWDMNetworks RanMin-GaoSuixiangXuBao (GraduateSchooloftheChineseAcademyofSciences,Beijing100039) (InstituteofHighEnergyPhysicsoftheChineseAcademyofSciences,Beijing100049) Abstract:Awavelengthconversionisrequiredatthejointoftwolightpathsiftheyusedifferentwavelengt hsinWDM networks.Itisexpensivetousewavelengthconveyor,whichcausesalongdelay.Soitisbe~ertominimize thenumber ofwavelengthsconversion.Thispaperproposesanalgorithmtoconstructamulticasttree,whichneedmi nimalwavelength conversionandCanreducethewavelengthcostandthedelayofmuhicastcommunicationseffectively. Keywords:WDM,wavelengthsconversion,hop,multicast l引言 随着网络技术的发展和应用,WDM(wavelength—division multiplexing)在传输速度和大带宽方面所具有的潜力越来越受 到人们的关注.基于WDM的光通信将成为下一代网络中解决 带宽限制的一种选择.多播是一种组通信机制,是一种将信息 从源节点同时发送到网络中多个目标节点的通信形式.目前的 许多多媒体业务如电视会议,远程教学及视频点播等都需要用 到这种通信形式.这些业务对时延要求较高,并且会占用大量 的网络资源.WDM网络由于其在带宽和速度方面的优势,被广 泛运用在多播传送领域. WDM网络的多播传送中,由于光分离技术的应用,在共有 的链路段不用再做多次的传输,而只要传输一次,然后在分叉 处用光分离器将一个信号分离成多个拷贝,分别传到不同的目 标节点即可,这样大大节省了带宽,提高了速度. 在WDM网络中,当有传输请求时,在源节点和目标节点 之间建立一条通路.并在该通路的每条链路上分配一个波长用 于传输信号.这个过程称为路由波长分配(RWARoutingand WavelengthAssignment).一般情况下,在进行波长路由分配时 需要遵守波长连续性的原则,即在一条通路上只能使用一种波 长.虽然wDM网络的带宽已比传统网络提高了很多.但随着 网络用户的激增,系统的波长数仍然大大少于实际节点数目和 用户数目.这样当两个或多个波长信号经过同一链路时就会产 生波长竞争,从而造成阻塞.这大大限制了WDM网络中波长 路由分配的随意性,这也是WDM全光网络与传统网络的不同 之处.波长转换器(wavelengthconveyor)可消除波长连续性的 约束,提高网络的通信能力.但由于目前波长转换器十分昂贵, 不可能每个点都配置波长转换器,况且在WDM全光网络中多 一 次波长转换对传输时延的影响较大.因此,在多播传送中,应 该充分考虑到波长转换次数的问题,在保证业务完成的基础 上.尽可能减少波长转换的次数. 目前在WDM网络中进行多播传送的问题,已经取得了许 多的研究成果.由于其计算的复杂性较高,一般采用启发式算 法.如文献【3,4忡介绍了光树(1ight~ee)的概念及应用,并提出 了在有限光分离能力的WDM网络中进行多播传送的寻径方 式.文献【2忡提出一种建立波长数最小的多播树.文献【7】介绍 了最小化波长转换器个数的一种路由分配算法.文献【1,5,6】介 绍了WDM全光网中.构造满足时延约束且具有较低成本的多 播树的方法.本文通过对现有文献的研究,提出了一种基于最 少波长转换次数的波长路由算法,该方法类似于一般网络的分 层方法.它先在较高层中找到多播传送所需的最少波长转换次 数,并以此建立一个高层拓扑图,然后再在下一层中找到各自 的最短路,从而建立一棵基于最少波长转换次数,且跳数较小 基金项目:国家自然科学基金资助(编号:10171095) 作者简介:冉敏(1973一),女,硕士生,主要研究方向为算法.高随祥(1962一),男,中科院研 究生院数学系教授,主要研究方向为组合最优化.绘 葆(1976--),女,硕士生,主要研究方向为算法设计. 1542005.27计算机工程与应用 的多播树. 2问题定义 假设用一带权的简单无向图G(,E,)来示一个网络, 其中V=,,…,n1是网络节点集,E={)是网络链路的集合, 每条链路e表示节点.到vj的一根光纤,和vi是链路的 两个端点.假设网络上的每个节点都具有光分离能力,即一个 信号可以在分叉处用光分离器分离成多个拷贝,再分别传输到 下一节点.:,1,0,…,1,0l表示网络中的可用波长集,即网络 中每条链路上可用波长集的并集.r(S;D)表示从源节点s到目 标节点集D的多播传送,且DV—fs1. 我们用w(e)表示链路e上的可用波长集,e?E.V.)表 示链路可用波长集中含有波长1,0.的所有链路e的端点集合.如 果;V(W).则称被波长1,0覆盖.E(w)表示链路可用波长集 中含有波长的所有链路e的集合.本文所要解决的问题就 是建立一棵从源节点s到目标节点集D的多播树,该树要求使 用最少的波长转换次数,且跳数较少.在这里分两步,第一步在 波长集节点的层次上求出波长转换次数最少的拓扑图,然后再 深入到每一个波长集节点中求出每一波长段最短路,从而得到 所需的多播树. 3求最少波长转换次数 拓扑图G(.E,)可进一步表示成k个波长覆盖图 G(V(毗),E(w),1,0.),i=1,2,…,k.若G((),E(w.),毗)不连 通.即覆盖波长的节点集和链路集所构成的拓扑图是不连 通的,则先将V()分成C个连通图.毗?W也分成C个波 长,即=,…,’},l,2.…,k.此时,拓扑图G(,E,W)中 的波长集合为=,…,.1=,,…,{l,1,2,…,z. 将拓扑图G(,E,)可进一步表示成Z个波长覆盖图 G(V(),E(w),1,0.),i=1,2,…,Z.对每个波长覆盖图用A., l,2,…,Z来表示.A表示A.覆盖的点集. 将拓扑图G(,E,)转换成一个波长集节点的拓扑图 F(,E,ccJ),其中表示拓扑图的节点集,它由波长集,源节点 和目标节点构成,即={slU{AdUD,l,2,…,Z.E是波长集节 点拓扑图的链路集合.它的生成方法如下:若A中包含源节点 s,则将A与s用一条边e相连,设该边的权值为O;若A中包 含目标节点d,d?D,则将A.与d用一条边e相连,设该边的权 值为0;若A.与A,所覆盖的节点集中包含有相同的节点,则 将A.与A用一条边e相连,并设该边的权值为l.用也来表 示A.与A共同覆盖的节点的集合.如此生成一个新的拓扑图 F(,E,ccJ). 以新的拓扑图F(,E,ccJ)为基础,从源节点s出发,构造一 棵总权值最小的多播树.即采用TM算法.生成一棵以源节点 为根,到所有目的节点的最小成本树.具体做法是首先将源节 点加入树中.然后计算树中任意一个节点与任意一个不在树中 的目的节点之间的权值最小的最短路径(可以使用Dijkstra算 法计算).选其中路径成本最小的目的节点及其相应的最短路 径加入到树中.重复进行,直到所有目的节点都加入到树中.最 后生成一棵总权值最小的steiner树(,E).该树的总权值就 是完成此项多播业务所需的最少波长转换次数. 当然,如果在开始定义权值时.设源节点和波长集节点相 连的边的权值为1的话,它所生成的多播树中的波长集节点的 个数就是完成此项多播业务所需的最小波长数. 到此.只是找到了完成此项多播业务最少所需的波长转 换次数.另外还需进一步地对多播业务进行波长和路由分配. 4基于最少波长转换次数进行波长和路由分配 多播树(,E)中所有波长集节点对应的波长就是完成 此项多播业务所需要上面的方法依次求出从源节点到每个目标节点跳数 最小的最短路.及各链路应选用的波长,然后将这些路径合并, 即得到一棵基于最小波长转换次数且跳数较少的多播树. 5仿真 对图l所示的网络拓扑模型G(,E,)应用上面提出的 算法进行仿真实验.设源节点为.点,目标节点集为{,,}. 图l中链路上所标的波长为该链路当前的可用波长.求一棵从 源节点到目标节点集所使用的波长转换器最少且满足跳数较 低的多播树. 囱1网络拓扑模型 由图1构造的波长集节点拓扑图F(V,E,cEJ)如图2所示, 其中=(Al,A2,A3,A4,l,2,5,61,0,1为边的权值. 图2波长集节点拓扑囱 对图2所示的拓扑图用TM方法求得权值最小的多播树. 得到图3中所示的基于波长集节点的多播树.然后从图3找到 从源节点到每个目标节点的代价最小的最短路.并展开该路径 中的波长集节点,求出从源节点到每个目标节点跳数最小的路 计算机工程与应用2005.27155