数字技术与应用
DWDM网络中的动态RWA算法研究
冯雪庞尚珍
（四川理工学院自动化与电子信息学院
四川自贡
643000)
·信息科学。
[摘要]路由和波长分配(RWA)是DWDM网络中一个重要向题，RWA向题解决的好坏直接影响到光路通信所雷的波长数和光路阻塞这两个重要特性，RWA间题是一个NP-C间题，一般的把它分成静态和动RWA间题进行讨论，本文将对DWDM网络中的动态RWA同题给出几种算法。
[关键词]RWAQoS
带宽
[中图分类号ITN915
[文献标识码]A
由于光网络承载的业务需求呈爆炸式增长，面目前光网络的可用资源有限，因此，如何在有限资源网络中为业务选择合适的路由和分配优化的波长将直接影响到网络的传输效率，路由和波长分配算法(RWA间题)也就成为一个核心向题之一。本文就动态RWA算法给出几种算法，并进行总结。
以跳数和带宽碎片要求为权重合理分配带宽资源的算法。
在DWDM中，分层图可以将选路与被长分配统-考虑，来·次性解决RWA间题。面以跳数和带宽碎片要求为权重，合理分配带宽资象的算法，正是利用这一点来解决RWA问题。对于波长链路来讲，要通过最少的物理结点尽快到达宿结点，就要求跳数尽可能的小，对带宽使用情况中的碎片控制：传统SPF算法先计算出链路的最短路径，当链路中有业务请求的时，不论最短路径是否已经发生拥塞，都将通向这条最短路径，然面，实际情况往往是在·条路径发生拥寒面拒绝服务的同时，网络中还有·益路轻由于流量较少或根本没有流景面处于空闲状态，这就造成了网络资源的巨大浪费。为此，还应考虑下面的情况。以图1为例说明：设链路1(A 到B)的链路开销小于链路3(A到C)的链路开销，即A到B为最短路径。当有3M的流量到达a结点时，根据SPF算法将该流量将会直接转发给B结点；而紧接着义有8M 的流量到达A结点，这时两条路径的带宽资源均为不足，本次连接请求将被拒绝。这样就会将链路1的7M带宽白白地浪费掉面成为一个带宽碎片。为避免这种情况的发生，应尽量在路由选择时选择那益实际空闲带宽与请求带宽相近的路径，从而达到尽量产生较小的带宽醇片、提高带宽利用率的目的。以跳数和带宽碎片要求为权重的算法是根据物理拓扑和当前的网络状念构造相应的VG，在VG上利用Dijkstra 算法找出待选路轻集中值教小的路径作为工作通路。如在图1中，当3M的流量到达时理应选择与3M带宽接近的链路2上，即 A、C之同的带宽为5
M的链路2上，#?
00000
G
图1
120
物理拓扑结构
数字校术与应用万方数据
[文章编号]1007-9416（2010）07-0120-01
随后到达的8M流量则会转到链路1上，达样就达到了比较理想的效果"]。
基于光链路释放机制的分布式动 2
态波长分配算法
基于光链路释放机制的分布式动态波长分配算法利用开放式最短路径协议中常用的数短路径算法Dijkstra算法质先为每个节点设定路由表。本算法中的路由表是静态的，选用了最简单的Dijkstra算法来对每个节点的路由表进行建立，为了建立一条路径，源节点S通过控制通道向第一个路由器发送请求信息并等待路由器反馈回来的信息来执行下面的算法。在每条信息中包含着为建立一条路径所选定的路由器和路由器中使用的波长的清单。假设每条信息都有一个周定的时间间隔通过控制通道来访间路由器。当收到响应后，如果响应表示请求成功，函节点将知道使用什么波长来通信：如果响应表示请求被拒绝，则表示没有找到合适的波长供使用，源节点将试着寻找新路径。
在光链路寻路阶段些波长将分配到T 一锁存中，T一锁存在光通路寸路阶段结束时释放。如果太多的波长因光通路于路进入T一锁存，则找不到合适的波长建立新的连接，所以，希望大部分的波长在完成相应
请求的光通路寻路后立刻释放出来2]， 3QoS动态综合路由算法[3]
为广在IP/WDM网络中实现QoS路由，在进行动态综合路由时须考虑业务流的分类与优先级，为了方便这一题的研究，文龄将业务分为QoS业务和BE业务，而未对QoS业务的服务优先等级再进行细分，而该算法总是试图子找剩余带宽最小的IP逐辑链路，也就楚最拥挤的网络信，H根据这一逐辑链路的剩余带宽值通
m，将到来的业务需求带宽大于m的业务进行拆分，且最多可拆分为m和n两部分。这样可以提高网络的波长带宽利用率也可使每个波长的带宽资源得以充分利用。同时可为未来到达的QoS业务留下更多的网络带宽资源，BE业务的通信需求不会造成影响，但会增加传输的延时量，在对余下的n这部分业务子找逐辑链路时，尽量选择剩余带宽最接近n的逐辑链路，可以提高网络的波长带宽利用事，对于n这部分业务，如无合适的逻辑链路，需要建立新的波长通道时，使用首次命中法进行波长分配，这样，系统选择编号教小的波长平面上的光路建立长通道，这样可降低系统
寻由计算的复杂度。此算法中综合考虑了 QoS业务与BE业务的不同特点与需求，在算法中对它们分别进行处理，提高算法的效率，更好的优化算法性能3。
改进的基于负载均衡的自适应算法
在数群算法的基础上，改进的基于负载均衡的自适应算法考虑了负载均衡的因索。新算法的改进主要是对于转移概率的改进。奴群算法转移概率通过距离失量来计算，面改进的基于负载均衡的自适应算法重新定义了转移概率，综合转移概率定义如下：
其中，a和b分别表示两个转移概率的权重，文献中a和b都被设置为1，综合转移概率决定了蚂数从当前节点i向节点」转移的瓶率。用这个概事来代替奴群算法中的转移微率，但算法的基本步骤和蚁群相同，使用这种算法，可以使拥塞率比以前的算法要小，面且反映光网络均衡度的平均链路等级要大，即负载也更加购均衡，这种算法对光通道建立比较有效14]。
综上，儿种算法各有利整，随着光网络技术的发展，RWA间题将会得到更好的解决(5)],
[参考文献]
[1]基于GMPLS的动态分布式WDM 网状网路由选择算法研究，杜荔，党爱民光电子技术与信息[J].2006,Mar;19(2)44-
47.
[2]WDM光网络的选路和波长分配算
法研究[D]：范伟，新江工业大学，2005.
[3]波分复用IP光网络中有QoS约束的动态综合路由研究[D].郑华，福建师范大学，2004.
[4] Herrera F, Martinez L. A 2-tuple fuzzy linguistic representation model for computing with words [J].IEEE Trans on Fuzzy Systems, 2000, 8(6):746752.
[5] Zhu H Y,Zang H,and Zhu K Y. et al. A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks.IEEE/ACM Trans.on Networking,2003,11(2);295,299
[基金项目]
四川理工学院引进人才科研项目(07ZR26)。