WDM网络中一种基于分层图模型的RWA算法

——

作者：时间：2007-12-25来源：收藏

　　1 引言

　　宽带视频、多媒体等业务的日益兴起,业务的快速增长,对广域骨干网的带宽提出了越来越高的要求。光纤上的波分复用技术(WDM)以它的传输容量大,对高层协议和技术适应性强,以及易于扩展等优点而备受青睐。因此,WDM光传送网被认为是下一代高速广域骨干网的最具竞争力的候选者[1]。

　　WDM光网络是由网络节点和连接节点的光纤链路构成的，不同波长的光信道复用在同一根光纤中传输。当客户层业务到达时，WDM光网络需要给每条业务选择路由和分配波长,建立光通道传送业务。这就是WDM网络的关键技术一路由与波长分配(RWA]问题。虽然WDM光网络已经取得了巨大的进步,但由于各种物理的、技术的限制因素，光网络还不能提供我们所要求的物理性能，因此就存在对现有可用资源的高效利用和优化问题，RWA问题是最优化网络性能的核心问题之一。本文针对这个问题，将波长分层图和网络图论的最大边不相关理论引入RWA问题中，提出了一种基于分层图的最大边不相关(LG-BEDP)算法。仿真表明，该算法可以有效节省网络波长资源,且易于实施。

　　2 研究背景

　　作为光网络的核心问题,静态RWA问题已被广泛研究,且已被证明是一个问题[2],多用一些启发式算法来解决。文献[4]提出一种整数线性规划(ILP)法，但该算法复杂度较高,且随网络规模急剧增大。本文的算法将网络图论中的最大边不相关理论和波长分层图模型结合起来解决这个问题,因此可同时进行选路和波长分配,且能有效优化网络资源。

　　2.1 RWA的最大边不相关问题

　　WDM网络巾,由于波长连续性的限制,不同业务对应的光路在网络拓扑中必须边不相关，因此，我们可以将图论中最大边不相关原理[5, 7]的一些解决方案应用到RWA问题中。RWA的最大边不相关问题可描述为：给定网络的物理拓扑和业务请求集合，分别从该集合中找到不同的业务分组，要求每个分组中的业务在物理拓扑上存在不相关路径，且分组中的业务个数尽可能地多。由于每个分组中的连接请求都符合边不相关的要求,因此,每组连接请求都可以分配相同的波长。

　　在此基础上,我们又引入了波长分层图模型，来共同解决静态RWA问题。

　　2.2 波长分层图模型

　　定义：网络的物理拓扑为G(V,E]V表示节点集合,E表示两条光纤形成的双向链路集合。设单根光纤中共有W个波长。

　　该物理拓扑的分层图LG (V*，E*)可以描述为：将物理拓扑复制W份,形成分层图中的W层。物理拓扑中的节点Vi就对应各个分层图中的{V1i,V2i，…Vwi}，链路ei就对应{e1i，e2i，…ewi}。并且原来的双向链路变成方向相反的两条有向链路。vi∈V，ei∈E,这样，分层图LG(V*,E*)的每一层都代表一个波长，我们从上到下对每一层所对应的波长进行编号，依次为λ1、λ2、…λw。

　　如图1(a)所示的物理网络变成分层图就如图1(b)所示.其中W=3,波长分层图的每一层所对应的波长依次为λ1、λ2、和λ3。

　　在波长分层图模型中，光路从源节点到目的节点必须要在同一个波长分层内，即满足波长连续性限制。对于一个连接请求，在波长分层图上进行选路，它所经过的路径，就是该光连接在物理拓扑上经过的路径，路径所在的波长分层，就是它所占用的波长。如图1(b)中，光连接(V5，V4)的路径是V35→V32→V33→V34，即该请求在物理拓扑中的路径为V5→V2→V3→V4，且该路径被分配的波长为λ3。因此，可以说波长分层图模型可以同时解决WDM网络中的选路和波长分配问题。

　　3 基于分层图的最大边不相关RWA算法

　　定义：网络物理拓扑为G(V，E)它所对应的分层图模型为LG(V*E*)：业务请求集合为D，集合中的某请求为d：波长数目为W;业务所对应的通路集合为P,通路pi跳数长度为

　　图2 ，要求每个通路的长度满足hi≤h，其中，m表示拓扑图中边的个数。diam(G)表示拓扑图的直径。

　　该算法可以描述为：首先随机地从业务请求集合D中选择一个连接请求，记为d1，在波长分层图的第一层上为业务请求d1找到可用的最短路径，记为P1，长度为h1，，若h1≤h则p1∈P，为陔路径分配波长λ1。更新LG(V*，E*)和D，使E*=E*-p1，D=D-d1。对于随机从D中选取的请求di,从第一层依次向下对它进行选路，若最早在波长分层图的第m层为di找到一条最短的可用路径pi，且它的长度hi≤h，则pi∈P，为该请求分配的波长为λmc。更新LG(V*，E*)和D为：E*=E*-pi，D=D-di。重复上述过程，直到D=φ，该过程结束。这时，建立所有光路所用到的分层图的层数就是本算法计算出的所用波长数。下面是本算法的流程：

　　Step 1：已知给定的G(V,E)和D，初始生成LG(V*，E*);

　　Step2：将连接请求d1以最短路由p1分配在LG(V*,E*)的层，并且更新LG(V*，E*)和D。

　　SteP3：为剩余的连接请求D选择路由并分配波长。若为随机选择的业务请求di寻找路径，则从λ1层向下层开始搜索。若最早在第λm层找到满足长度hi≤h的最短路径pi，则更新波长分层图LG(V*，E*)和D，该请求被分配的波长为λm。

　　Step4：if D≠φ，则返回第三步。

　　Step 5：if D=φ，则算法完毕，返回m的最大值，即业务在网络中占用的波长数。

　　4 仿真分析

　　我们对本算法和最短路径--首次命中SP-FF(shortest path-first fit)算法进行了仿真比较。SP-FF即利用最短路径算法进行选路,采用首次命中算法分配波长的RWA算法。优化目标是最小化波长数目，所用的仿真拓扑图为14个节点的NSFNET，见图2。

　　首先,假设该网络中每根光纤上存在40个波长，并随机生成网络的业务请求集合D，并且网络的业务呈均匀分布,每个节点的业务量为1～13。在上述条件下,分别对LG-BEDP算法和SP-FF算法进行了200次仿真。

　　从图3可以看出，在不同负载下,LG-BEDP算法所使用的平均波长数都更少，并且业务负载越大,LG BEDP算法比SP-FF算法节省的波长数越多,当负载为13时，该算法可以比SP-FF算法少用4个以上的波长。

　　图4中对两种算法在不同负载下所使用的最大和最小的波长数进行了对比，LG-BEDP算法在相同负载下的波长使用数目上下波动不大,在2～3个波长之间，且LG-BEDP-max和SP-FF-min相接近。但是SPFF算法在相同负载下使用的波长数目波动幅度较大，且随着负载的增大这种情况更加明显。因此，LG BEDP算法不仅性能更优，而且算法的稳定性也较好。

　　表1是两种算法在波长λ1～λ10情况下的链路使用率，从表中可以看出，LG-BEDP算法的链路使用率更高，并且在波长λ1、λ2时，链路使用率最高可达100%。值得注意的是，某些时候链路的使用率会随着波长编号的增大而下降，这主要是因为我们在选路时，总是倾向于选择波长编号最小的那些路径。