IPviaMPLSoverDWDM网络的动态路由算法研究

路由和波长分配 (RWA) 是IP over DWDM光互联网中MPLmS控制层面的一个重要问题。RWA问题解决的好坏直接影响到光路通信所需的波长数和光路阻塞这两个重要特性, 本文将对IP via MPLS over DWDM网络中的动态路由问题给出几种算法。

1 多路径路由技术

在D W D M网络中, 单路径路由技术用最短路径来定义各个路由器的输出, 产生一条最优路径, 将到达的分组数据转到这条路径上来。在实践中, 会产生传输瓶颈, 在路由器的输出端产生阻塞, 增加流量负载, 也不能保证在DWDM网络实现中实现QoS。多路径路由技术利用网络的反馈信息来了解网络的路由信息, 然后根据优先级别的高低来确定转发分组数据。也就是说, 当中间路径的最优节点或最优路径处于忙的状态, 路由器就要查表再找一条路径来转发分组数据。如果所找的这条次优路径仍然存在上述问题, 按照预定义的优先级为分组数据寻找下一条次优路径, 直到找到合适的路径为止, 如果都没找到, 向发送端发送通知消息, 具体方案由ISP和用户协商确定。为有效的提供区分服务保证, 我们在网络的边缘路由器上设置多等级服务功能, 可以实现网络对区分服务的支持, 从而有效地提高网络的服务质量[1]。

2 于优先级的动态子通路保护算法 (PASPP)

PASPP算法[2]链路中的物理拓扑结构图映射为可达图, 然后将工作链路分为互不重叠的大致等长的n个子链路, 为每个链路提供保护, 然后利用最短路径算法为已到达的业务连接找到一条代价最小的工作链路, 如果有一条没找到得话, 则连接不能建立。PASPP算法[3]在ASPP算法基础上, 把到达的业务分为高低两个优先级。当业务连接到来时, 如果是高优先级的业务, 直接考虑通路中的剩余带宽, 当剩余带宽不能满足要求时, 可以直接抢占低优先级业务的保护通路来建立连接。如果是低优先级业务时, 若没有高优先级的业务时, 低优先级业务的保护通路直接建立, 如图1所示。

图1所示为一个单光纤、单波长、6节点的D W D M物理网络拓扑, 用一个波长所支持的传输速率作为带宽要求的基本单位, 按PASPP算法, 将业务分为高低两个优先级, 再为高优先级业务见通路时, 可以抢占低优先级业务通路, 设链路 (1, 2) 为某一连接的低优先级保护通路, 占用带宽为0.7单位, 剩余带宽为0.3单位。如果此时到达一个高优先级连接请求{5, 2, 0.6}, 选择路径5-3-2, 5-4-2或5-1-2建立通路, 选5-3-2时, 在为子通路3-2寻找保护通路时, 剩余带宽不够, 选5-4-2在为4-2寻找保护通路时, 剩余带宽不够, 此时又没有其他的空闲带宽可以用, 这时直接占用 (1, 2) 的保护通路, 等高优先级业务完成后, 被中断的低优先级业务通路保护恢复, 如果, 按ASPP算法, 由于业务级别相同, 对于最短路径, 不论选哪条, 通路都不能建立, 舍弃。所以, 对于A S P P, P A S P P两种算法来讲, P A S P P算法对资源的利用率更高些, 避免了保护通路的过多中断, 尽量给过于的通路提供更多的保护。

3 基于协商的重叠型路由算法

根据文献[5], 对等模型下的综合路由算法IR以扩大扩大IP/MPLS层和光层维护的数据库规模来提高网络的性能, 这样就加大了重叠模型下顺序路由机制SR与它的性能差距, 为了减小这种差距, 文献[4]提出在IP/MPLS层和光层之间引入一种协商机制 (consulting mechanism) , 这种协商机制可以能够降低标签交换请求的阻塞概率, 又能保持各层状态数据库的独立。具体工作过程如下。

当标签交换L SP请求到达IP/MPL S层, IP/MPL S层入口处的标签交换路由器LSR根据它所维护的路由拓扑为LSP计算显式路由。如果入口LSR认为与光层协商建立一条新的光路是有必要的, LSR就会向光层发送包含源目的地址信息的协商消息 (consulting message) 。光层收到协商信息后, 找到源目的OXC的地址后, 可以协商建立一条或多条光路, 这些光路信息可以通过相同的协商信息格式, 从而提高协商机制的效率, ({LSRx, LSRy}, cost) , 其中小括号内对应一条协商光路, 包括协商过程的开销 (cost) , 如果光层找到合适的就给IP/MPLS层一个肯定消息, 这里包括路径, 和建立光路径所需的开销, 当然这只是一种协商, 即使光层有足够的资源也可以给出否定信号。如果没找到合适的, 就直接返还否定信号, 这时将cost的值设置为无穷大就可以了。另外, 导致cost无穷大可能是管理方面或其他方面的原因, 也可能是缺少资源。但是在协商这一阶段, 不要求光路径进行预留或资源分配, 协商的目的只是简单的通知下当前的光层能否提供所需的空闲资源。光层资源最终是否实际被利用取决于IP/MPLS层的路由算法。协商过程如图2所示。

总的来说, IP via MPLS over DWDM网络中的动态路由问题是个NP[6]问题, 很多文献给出了不同的算法, 各有优缺点。

摘要：DWDM网络中的路由和波长分配 (RWA) 是一个NP-C问题, 文中给出了几种动态路由算法。

关键词：多路径路由技术,RWA,标签交换

参考文献

[1] 余一清, 等.基于QoS的WDM网络中多等级服务问题研究[J].计算机及应用, 2003, 9:12～13.

[2] Zhu H Y, Zang H, and Zhu K Y, etal..A novel generic graph model fortraffic grooming in heterogeneous WDMmesh networks.IEEE/ACM Trans.onNetworking, 2003, 11 (2) :285～289.

[3] 孙永飞, 等.一种新的WDM网状网中的动态子通路保护算法[J].计算机工程与应用, 2006 (17) :136～139.

[4] 王慕维.IPIMPLS over WDM网络综合路由策略研究[D].西安电子科技大学, 2006, 1.

[5] Y.Wang, Tee Hiang Cheng, and S.K.Bose, An Enquiry-Based DynamicService Provisionging Approach forOverlay IP over Optical Networks, Photon.Netw.Commun, 2005, 10 (3) :347～346

[6] Chlamtac I, et al.Lightpath communication:an approach to high bandwidth opticalWANs[J].IEEE Trans Comm, 2002, 40 (7) :1171～1182.