论文部分内容阅读
摘要：提出了一种基于分层图的最大边不相关（Layered Graph-Based Edge Disjoint Path）算法，该算法不同于现有研究大多将WDM网络的RWA问题拆分为选路和分配波长两个子问题，而是将波长分层图和图论中的最大边不相关原理引入RWA问题中，可同时进行选路和波长分配。仿真证明，该算法可以有效节省网络波长资源，且易于实施。
关键字：WDM光网络; RWA; 分层图; 最大边不相关
中图分类号：F204文献标识码：A 文章编号：
1 引言
宽带视频、多媒体等业务的日益兴起，业务的快速增长，对广域骨干网的带宽提出了越来越高的要求。光纤上的波分复用技术（WDM）以它的传输容量大，对高层协议和技术适应性强，以及易于扩展等优点而备受青睐。因此，WDM光传送网被认为是下一代高速广域骨干网的最具竞争力的候选者[1]。
WDM光网络是由网络节点和连接节点的光纤链路构成的，不同波长的光信道复用在同一根光纤中传输。当客户层业务到达时，WDM光网络需要给每条业务选择路由和分配波长，建立光通道传送业务。这就是WDM网络的关键技术——路由与波长分配(RWA)问题。虽然WDM光网络已经取得了巨大的进步，但由于各种物理的、技术的限制因素，光网络还不能提供我们所要求的物理性能，因此就存在对现有可用资源的高效利用和优化问题，RWA问题是最优化网络性能的核心问题之一。本文针对这个问题，将波长分层图和网络图论的最大边不相关理论引入RWA问题中，提出了一种基于分层图的最大边不相关（LG-BEDP）算法。仿真表明，该算法可以有效节省网络波长资源，且易于实施。
2 研究背景
作为光网络的核心问题， 静态RWA问题已被广泛研究，且已被证明是一个问题[2]，多用一些启发式算法来解决。文献[4]提出一种整数线性规划（ILP）法，但该算法复杂度较高，且随网络规模急剧增大。部分文献（如文献[3]）还将之拆被分为路由选择和波长分配两个子问题来解决，但这种对RWA问题的描述并不一定完全贴切。本文的算法将网络图论中的最大边不相关理论和波长分层图模型结合起来解决这个问题，因此可同时进行选路和波长分配，且能有效优化网络资源。
2.1 RWA的最大边不相关问题
WDM网络中，由于波长连续性的限制，不同业务对应的光路在网络拓扑中必须边不相关，因此，我们可以将图论中最大边不相关原理[5]的一些解决方案应用到RWA问题中。RWA的最大边不相关问题可描述为：给定网络的物理拓扑和业务请求集合，分别从该集合中找到不同的业务分组，要求每个分组中的业务在物理拓扑上存在不相关路径，且分组中的业务个数尽可能地多。由于每个分组中的连接请求都符合边不相关的要求，因此，每组连接请求都可以分配相同的波长。
在此基础上，我们又引入了波长分层图模型，来共同解决静态RWA问题。
2.2 波长分层图模型
定义：网络的物理拓扑为G(V,E)，V表示节点集合，E表示两条光纤形成的双向链路集合。设单根光纤中共有W个波长。
该物理拓扑的分层图可以描述为：将物理拓扑复制W份，形成分层图中的W层。物理拓扑中的节点就对应各个分层图中的，链路就对应。并且原来的双向链路变成方向相反的两条有向链路。∈V，∈E．这样，分层图的每一层都代表一个波长，我们从上到下对每一层所对应的波长进行编号，依次为。
物理网络变成分层图时，其中，波长分层图的每一层所对应的波长依次为。
在波长分层图模型中，光路从源节点到目的节点必须要在同一个波长分层内，即满足波长连续性限制。对于一个连接请求，在波长分层图上进行选路，它所经过的路径，就是该光连接在物理拓扑上经过的路径，路径所在的波长分层，就是它所占用的波长。光连接（）的路径是，即该请求在物理拓扑中的路径为，且该路径被分配的波长为。因此，可以说波长分层图模型可以同时解决WDM网络中的选路和波长分配问题。
3 基于分层图的最大边不相关RWA算法
定义：网络物理拓扑为G(V,E)，它所对应的分层图模型为；业务请求集合为D，集合中的某请求为；波长数目为W；业务所对应的通路集合为P，通路的跳数长度为。设，要求每个通路的长度满足，其中，m表示拓扑图中边的个数。表示拓扑图的直径。
该算法可以描述为：首先随机地从业务请求集合D中选择一个连接请求，记为，在波长分层图的第一层上为业务请求找到可用的最短路径，记为，长度为，若则，为该路径分配波长。更新和D，使，。对于随机从D中选取的请求，从第一层依次向下对它进行选路，若最早在波长分层图的第m层为找到一条最短的可用路径，且它的长度，则 ，为该请求分配的波长为。更新和D为：，。重复上述过程，直到，该过程结束。这时，建立所有光路所用到的分层图的层数就是本算法计算出的所用波长数。下面是本算法的流程：
Step 1：已知给定的G（V,E）和D，初始生成；
Step 2：将连接请求以最短路由分配在的层，并且更新和D。
Step 3：为剩余的连接请求D选择路由并分配波长。若为随机选择的业务请求寻找路径，则从层向下层开始搜索。若最早在第层找到满足长度的最短路径，则更新波长分层图和D，该请求被分配的波长为。
Step 4：if ，则返回第三步。
Step 5：if ，则算法完毕，返回m的最大值，即业务在网络中占用的波长数。
4 仿真分析
我们对本算法和最短路径-首次命中SP-FF（shortest path-first fit）算法进行了仿真比较。SP-FF即利用最短路径算法进行选路，采用首次命中算法分配波长的RWA算法。我们的优化目标是最小化波长数目，所用的仿真拓扑图为14个节点的NSFNET。
首先，假设该网络中每根光纤上存在40个波长，并随机生成网络的业务请求集合D，并且网络的业务呈均匀分布，每个节點的业务量为1-13。在上述条件下，我们分别对LG-BEDP算法和SP-FF算法进行了200次仿真。
在不同负载下，LG-BEDP算法所使用的平均波长数都更少，并且业务负载越大，LG-BEDP算法比SP-FF算法节省的波长数越多，当负载为13时，该算法可以比SP-FF算法少用4个以上的波长。
对两种算法在不同负载下所使用的最大和最小的波长数进行了对比，LG-BEDP算法在相同负载下的波长使用数目上下波动不大，在2-3个波长之间，且LG-BEDP-max和SP-FF-min相接近。但是SP-FF算法在相同负载下使用的波长数目波动幅度较大，且随着负载的增大这种情况更加明显。因此，LG-BEDP算法不仅性能更优，而且算法的稳定性也比较好。
5 结论
在本文中，我们将波长分层图模型和RWA的最大边不相关问题结合起来，提出了一种新的RWA算法LG-BEDP，与其它算法相比，本算法可以同时解决RWA中的选路和波长分配问题。仿真证明，我们提出的LG-BEDP可以节省更多的波长资源，且算法稳定性更好、资源利用率较高。
参考文献:
RAMASWAMI R, SIVARAJAN K. Optical Networks: A Practical Perspective [M]. San Francisco：Morgan Kaufmann Publishers, CA, 1998.
CHLAMTAC I, GANZ A, KARMI G. Lightpath communications: An approach to high-bandwidth optical WANs [J]. IEEE Trans. Commun., July 1992, vol. 40, pp.1171-1182.
SATORU O, ARDIAN G. Comparison of routing and wavelength assignment algorithms for optical networks [J]. IEEE Communication Letter，2001，5(5)：203—205．
BANERJEE D, MUKHERJEE B. A practical approach for routing and wavelength assignment in large wavelength routed optical networks [J], IEEE J. Select. Areas Communication, June 1996, vol. 14, pp. 903–908.
KLEINBERG J M. Approximation algorithms for disjoint paths problems [D]. Ph.D. dissertation, MIT, Cambridge, May 1996.
关键字：WDM光网络; RWA; 分层图; 最大边不相关
中图分类号：F204文献标识码：A 文章编号：
1 引言
宽带视频、多媒体等业务的日益兴起，业务的快速增长，对广域骨干网的带宽提出了越来越高的要求。光纤上的波分复用技术（WDM）以它的传输容量大，对高层协议和技术适应性强，以及易于扩展等优点而备受青睐。因此，WDM光传送网被认为是下一代高速广域骨干网的最具竞争力的候选者[1]。
WDM光网络是由网络节点和连接节点的光纤链路构成的，不同波长的光信道复用在同一根光纤中传输。当客户层业务到达时，WDM光网络需要给每条业务选择路由和分配波长，建立光通道传送业务。这就是WDM网络的关键技术——路由与波长分配(RWA)问题。虽然WDM光网络已经取得了巨大的进步，但由于各种物理的、技术的限制因素，光网络还不能提供我们所要求的物理性能，因此就存在对现有可用资源的高效利用和优化问题，RWA问题是最优化网络性能的核心问题之一。本文针对这个问题，将波长分层图和网络图论的最大边不相关理论引入RWA问题中，提出了一种基于分层图的最大边不相关（LG-BEDP）算法。仿真表明，该算法可以有效节省网络波长资源，且易于实施。
2 研究背景
作为光网络的核心问题， 静态RWA问题已被广泛研究，且已被证明是一个问题[2]，多用一些启发式算法来解决。文献[4]提出一种整数线性规划（ILP）法，但该算法复杂度较高，且随网络规模急剧增大。部分文献（如文献[3]）还将之拆被分为路由选择和波长分配两个子问题来解决，但这种对RWA问题的描述并不一定完全贴切。本文的算法将网络图论中的最大边不相关理论和波长分层图模型结合起来解决这个问题，因此可同时进行选路和波长分配，且能有效优化网络资源。
2.1 RWA的最大边不相关问题
WDM网络中，由于波长连续性的限制，不同业务对应的光路在网络拓扑中必须边不相关，因此，我们可以将图论中最大边不相关原理[5]的一些解决方案应用到RWA问题中。RWA的最大边不相关问题可描述为：给定网络的物理拓扑和业务请求集合，分别从该集合中找到不同的业务分组，要求每个分组中的业务在物理拓扑上存在不相关路径，且分组中的业务个数尽可能地多。由于每个分组中的连接请求都符合边不相关的要求，因此，每组连接请求都可以分配相同的波长。
在此基础上，我们又引入了波长分层图模型，来共同解决静态RWA问题。
2.2 波长分层图模型
定义：网络的物理拓扑为G(V,E)，V表示节点集合，E表示两条光纤形成的双向链路集合。设单根光纤中共有W个波长。
该物理拓扑的分层图可以描述为：将物理拓扑复制W份，形成分层图中的W层。物理拓扑中的节点就对应各个分层图中的，链路就对应。并且原来的双向链路变成方向相反的两条有向链路。∈V，∈E．这样，分层图的每一层都代表一个波长，我们从上到下对每一层所对应的波长进行编号，依次为。
物理网络变成分层图时，其中，波长分层图的每一层所对应的波长依次为。
在波长分层图模型中，光路从源节点到目的节点必须要在同一个波长分层内，即满足波长连续性限制。对于一个连接请求，在波长分层图上进行选路，它所经过的路径，就是该光连接在物理拓扑上经过的路径，路径所在的波长分层，就是它所占用的波长。光连接（）的路径是，即该请求在物理拓扑中的路径为，且该路径被分配的波长为。因此，可以说波长分层图模型可以同时解决WDM网络中的选路和波长分配问题。
3 基于分层图的最大边不相关RWA算法
定义：网络物理拓扑为G(V,E)，它所对应的分层图模型为；业务请求集合为D，集合中的某请求为；波长数目为W；业务所对应的通路集合为P，通路的跳数长度为。设，要求每个通路的长度满足，其中，m表示拓扑图中边的个数。表示拓扑图的直径。
该算法可以描述为：首先随机地从业务请求集合D中选择一个连接请求，记为，在波长分层图的第一层上为业务请求找到可用的最短路径，记为，长度为，若则，为该路径分配波长。更新和D，使，。对于随机从D中选取的请求，从第一层依次向下对它进行选路，若最早在波长分层图的第m层为找到一条最短的可用路径，且它的长度，则 ，为该请求分配的波长为。更新和D为：，。重复上述过程，直到，该过程结束。这时，建立所有光路所用到的分层图的层数就是本算法计算出的所用波长数。下面是本算法的流程：
Step 1：已知给定的G（V,E）和D，初始生成；
Step 2：将连接请求以最短路由分配在的层，并且更新和D。
Step 3：为剩余的连接请求D选择路由并分配波长。若为随机选择的业务请求寻找路径，则从层向下层开始搜索。若最早在第层找到满足长度的最短路径，则更新波长分层图和D，该请求被分配的波长为。
Step 4：if ，则返回第三步。
Step 5：if ，则算法完毕，返回m的最大值，即业务在网络中占用的波长数。
4 仿真分析
我们对本算法和最短路径-首次命中SP-FF（shortest path-first fit）算法进行了仿真比较。SP-FF即利用最短路径算法进行选路，采用首次命中算法分配波长的RWA算法。我们的优化目标是最小化波长数目，所用的仿真拓扑图为14个节点的NSFNET。
首先，假设该网络中每根光纤上存在40个波长，并随机生成网络的业务请求集合D，并且网络的业务呈均匀分布，每个节點的业务量为1-13。在上述条件下，我们分别对LG-BEDP算法和SP-FF算法进行了200次仿真。
在不同负载下，LG-BEDP算法所使用的平均波长数都更少，并且业务负载越大，LG-BEDP算法比SP-FF算法节省的波长数越多，当负载为13时，该算法可以比SP-FF算法少用4个以上的波长。
对两种算法在不同负载下所使用的最大和最小的波长数进行了对比，LG-BEDP算法在相同负载下的波长使用数目上下波动不大，在2-3个波长之间，且LG-BEDP-max和SP-FF-min相接近。但是SP-FF算法在相同负载下使用的波长数目波动幅度较大，且随着负载的增大这种情况更加明显。因此，LG-BEDP算法不仅性能更优，而且算法的稳定性也比较好。
5 结论
在本文中，我们将波长分层图模型和RWA的最大边不相关问题结合起来，提出了一种新的RWA算法LG-BEDP，与其它算法相比，本算法可以同时解决RWA中的选路和波长分配问题。仿真证明，我们提出的LG-BEDP可以节省更多的波长资源，且算法稳定性更好、资源利用率较高。
参考文献:
RAMASWAMI R, SIVARAJAN K. Optical Networks: A Practical Perspective [M]. San Francisco：Morgan Kaufmann Publishers, CA, 1998.
CHLAMTAC I, GANZ A, KARMI G. Lightpath communications: An approach to high-bandwidth optical WANs [J]. IEEE Trans. Commun., July 1992, vol. 40, pp.1171-1182.
SATORU O, ARDIAN G. Comparison of routing and wavelength assignment algorithms for optical networks [J]. IEEE Communication Letter，2001，5(5)：203—205．
BANERJEE D, MUKHERJEE B. A practical approach for routing and wavelength assignment in large wavelength routed optical networks [J], IEEE J. Select. Areas Communication, June 1996, vol. 14, pp. 903–908.
KLEINBERG J M. Approximation algorithms for disjoint paths problems [D]. Ph.D. dissertation, MIT, Cambridge, May 1996.