One Novel Dynamic Routing and Wavelength Assignment Integrate Algorithm in WDM Optical Network

Abstract

Dynamic routing and wavelength assignment in the WDM networks with.both dynamic service traffic and limited-range wavelength conversion have been discussed. According to probability and limitation of wavelength conversion, a novel heuristic algorithm, which could achieve dynamic minimum cost routing and optimal virtual wavelength path, DMC - OVWP, is proposed based on Moone-Dijkstra algorithm. With separation and combination of routing and wavelength assignment subproblems, the algorithm optimizes RWA problem. The results simulating CERNET using the algorithm show that low blocking probability has been obtained.

Content

《1 引言》

1 引言

众所周知, WDM网络系统的一个优良特性在于在光传输层可以实现波长路由选择^[1,2]。一般情况下, 网络中信号路径由源信号、网络交换状态、波长以及选路算法等决定。通过路由和波长分配 (RWA) 可建立从信源点到信宿点动态光通道^[3]。这样既充分调动和利用了网络资源, 又保证了网络中信息传输的安全性。因此, 动态路由和波长分配已成为WDM光网核心技术之一。目前WDM光网正从主干网延伸到城域网及其以下范围, 优化RWA并实现波长级管理和更多的服务内容^[4]。

以往进行波长分配大多采用固定或备用路由算法, 只考虑源宿节点对之间所有可能通路集合的一个子集^[5]。文献[6]提出具有波长转换能力的WDM网中路由算法的3种策略。文献[7]采用Dijkstra最小代价路径算法, 讨论了链路可用波长数、距离、链路波长总数3种因素的链路权重函数, 以基于跳数的算法作比较, 分析了不同光链路测度和权重函数的动态路由动态RWA算法的性能, 其中考虑了全波长变换和部分波长变换。文献[8]采用最短路径算法, 讨论了波长变换范围和波长变换节点分布对RWA的影响。文献[9]分析了有限范围波长变换对动态RWA的影响。文献[10]分析了多纤网中的情况, 在相等波长资源下, 获得了比单纤网更好的性能。但以上算法所考虑的方面均显单一, 综合考虑动态路由、波长变换、多纤、多种光链路测度时尚无合适的算法。而在选路和波长分配时, 为利用更多的全网信息, 一个有效的途径就是采用合适的光链路测度将RWA的2个子问题结合起来。关于光链路测度, 即波长路由测度, 除物理距离外, 主要考虑QoS测度 (服务要求) 和资源测度 (质量约束) 两个方面^[11]。

笔者讨论了WDM光网中, 在动态业务流量和有限范围波长变换情况下的动态路由和波长分配问题。基于Moone-Dijkstra算法, 考虑到动态波长变换的可能和限制, 提出了一种新型的、可实现动态最小代价路由和最佳虚波长通道的综合启发式算法DMC-OVWP (dynamic min-cost and optimal virtual wavelength path algorithm) 。该算法将路由子问题和波长分配子问题, 以既相互独立又相互结合来处理的思想为指导, 尽可能利用更多的网络状态信息, 以获取尽可能好的动态性能。

《2 DMC-OVWP算法》

2 DMC-OVWP算法

WDM网的物理拓扑可用加权图G (V, E, F) 表示, V 为网络节点集, E 为边集, F 为各边上的光纤集。

对于单纤网, 计算链路权重采用波长资源占用测度, 根据分散策略获取链路权重函数。光纤链路权重越小, 使用该光纤链路的代价越小, 则使用该光纤链路的概率越大。利用图论中的加权邻接矩阵表示链路权重, 应用Moone-Dijkstra算法即可获取动态的最小代价路径。则有邻接矩阵A (G) , a_ij表示相应的矩阵元素:

$a_{i j} = {\begin{cases} 0, i = j, \\ 1, i \neq j, (v_{i}, v_{j}) \in E \\ \inf, i \neq j (v_{i}, v_{j}) \notin E \end{cases} (1)$ $a_{i j} = {\begin{cases} 0, i = j, \\ 1, i \neq j, (v_{i}, v_{j}) \in E \\ \inf, i \neq j (v_{i}, v_{j}) \notin E \end{cases} (1)$

权重因子矩阵W_FM, w_f (a_ij) 表示相应的矩阵元素:

$w_{f} (a_{i j}) = {\begin{cases} 1, i = j 或 i \neq j, (v_{i}, v_{j}) \notin E \\ 1 + δ λ_{i j}, \begin{array}{l} i \neq j, (v_{i}, v_{j}) \in E, \\ λ_{i j} \in {0, 1, \dots, W - 1} \end{array} \\ \inf, i \neq j, (v_{i}, v_{j}) \in E, λ_{i j} = W \end{cases} (2)$ $w_{f} (a_{i j}) = {\begin{cases} 1, i = j 或 i \neq j, (v_{i}, v_{j}) \notin E \\ 1 + δ λ_{i j}, \begin{array}{l} i \neq j, (v_{i}, v_{j}) \in E, \\ λ_{i j} \in {0, 1, \dots, W - 1} \end{array} \\ \inf, i \neq j, (v_{i}, v_{j}) \in E, λ_{i j} = W \end{cases} (2)$

上式中, λ_ij∈{0, 1, …, W} 为边 (v_i, v_j) 上已占用的波长数。

由式 (1) 和式 (2) 得加权邻接矩阵W_AM =W_FMA (G) , 矩阵元w (a_ij) 表示节点i, j间的链路权重:

$w (a_{i j}) = {\begin{cases} 0, i = j ； \\ \begin{array}{l} 1 + δ λ_{i j}, \end{array} \begin{array}{l} i \neq j, (v_{i}, v_{j}) \in E, \\ λ_{i j} \in {0, 1, \ :, W - 1} ； \end{array} \\ \begin{array}{l} \inf, \end{array} \begin{array}{l} i \neq j, (v_{i}, v_{j}) \in E, λ_{i j} = W \\ 或 i \neq j, (v_{i}, v_{j}) \notin E \end{array} \end{cases} (3)$ $w (a_{i j}) = {\begin{cases} 0, i = j ； \\ \begin{array}{l} 1 + δ λ_{i j}, \end{array} \begin{array}{l} i \neq j, (v_{i}, v_{j}) \in E, \\ λ_{i j} \in {0, 1, \ :, W - 1} ； \end{array} \\ \begin{array}{l} \inf, \end{array} \begin{array}{l} i \neq j, (v_{i}, v_{j}) \in E, λ_{i j} = W \\ 或 i \neq j, (v_{i}, v_{j}) \notin E \end{array} \end{cases} (3)$

对于多纤网, 可以采用扩展的三维加权邻接矩阵, 先分别在各相邻节点的各光纤链路中选取最小代价链路, 将原邻接矩阵降维, 再利用Moone-Dijkstra算法寻找动态的最小代价路径, 各相邻节点对之间的双向光纤链路数F可以不同。

DMC-OVWP算法描述:

Step 1 根据全网状态——波长信道资源占用信息, 利用链路权重函数计算各个链路的权值, 获得网络当前的加权邻接矩阵, 并对三维加权邻接矩阵降维;

Step 2 利用加权邻接矩阵, 应用Moone-Dijkstra算法获取动态的最小代价路由, 若找到, 则转入Step 3, 否则输出空集, 转入Step 4;

Step 3 在VWP和有限波长变换范围条件下, 对该路由进行波长分配。将波长按从小到大顺序设置, 使用首次适配原则查找满足波长连续性条件的波长通道, 并统计各个波长关于该最小代价路由的连续性, 若找到波长通道则退出查找循环;否则, 依据循环所得的各波长信息, 使用首次适配原则查找最接近波长通道的一个虚波长通道, 记录主波长, 并对需波长变换的各链路, 在允许的波长变换范围内, 分别查找离主波长最近的空闲波长, 从而获得虚波长通道的波长分配信息;若仍未找到, 则占用波长信道信息为空集。输出路由和占用波长信道信息, 转入Step 4;

Step 4 退出RWA算法模块。

DMC-OVWP算法有2个优点:a. 普适性比较好, 支持无波长变换、全波长变换、有限范围波长变换, 支持有向链路、无向链路, 支持单纤网、多纤网;b. 扩展性比较强, 可换用不同的光链路测度, 进一步, 还可以采用不同的多光链路测度组合方法, 从而获取不同设计目标和不同意义下的最优路由和光通道。

《3 仿真实验和结果讨论》

3 仿真实验和结果讨论

以中国教育和科研计算机网CERNET的网络拓扑结构为背景进行模拟仿真, 见图1。设定相邻节点间以单纤连接, 多纤网可类似处理。设定连接建立请求以泊松速率到达, 已建立的各连接的服务时间服从指数分布, 全网的各节点负载均衡, 无建立连接的请求等待队列, 即一旦连接请求被拒则立即丢弃, 这类似爱尔兰损失系统模型, 但服务装置数动态变化。

《图1》

图1 仿真实验网络拓扑

Fig.1 Network topology for simulation

仿真程序从网络空载开始执行, 因而仿真系统在到达稳定状态前需经历一个称为暂态期的过渡过程, 为保证统计分析结果的准确性, 必须除去暂态影响, 因而在统计之前先额外处理1000个连接请求作为仿真系统的“预热”, 网络阻塞率的计算使用减去预热请求次数之后的连接请求数。仿真实验中维护2个实时信息库:全网波长信道资源占用信息库和已建立未拆除连接的路由表数据库。

《3.1 仿真实验的稳定性判定》

3.1 仿真实验的稳定性判定

为验证实验的统计稳定性, 用不同数量的建立请求获取实验结果。使用的建立连接请求总数越大, 获取的实验结果的随机性越小, 越稳定, 最多采用10⁶ 个建立连接请求数 (不包括“预热”) 。为更清楚的比较不同复用波长数和不同波长变换范围下的实验稳定性情况, 可将所得的实验结果归一化:在各自参数设定下, 将建立请求总数为10⁶时的实验结果作为基准值, 其他实验结果均除以对应的相同参数设定下的基准值, 得到相应的归一化实验结果。例如, 在复用波长总数W=64, 不同波长变换范围k= 0, 1, 2, 网络负载ρ=960 Erlangs 的参数设置下, 实验统计稳定性情况见图2。可以看出, 实验结果与前述分析是一致的, 给定的建立连接请求总数越大, 代表实验结果的曲线越趋于平稳, 10⁶个建立连接请求数完全可以满足要求。

《图2》

图2 稳定性判定 (归一化, W = 64, ρ=960Erlangs)

Fig.2 Simulation stability (normalized, W=64, ρ= 960 Erlangs)

《3.2 实验结果分析》

3.2 实验结果分析

1) 复用波长总数 (W = 8, 16, 32, 64) 一定时, 在不同波长变换范围k= 0, 1, 2内, 阻塞率随网络负载的变化分别见图3至图6。

《图3》

图3 网络阻塞率 (复用波长总数一定, W=8)

Fig.3 Blocking probability (W fixed, W= 8)

《图4》

图4 网络阻塞率 (复用波长总数一定, W= 16)

Fig.4 Blocking probability (W fixed, W= 16)

《图5》

图5 网络阻塞率 (复用波长总数一定, W= 32)

Fig.5 Blocking probability (W fixed, W= 32)

从图3至图6中可明显看出, 在相同复用波长总数和波长变换范围下, 随着网络负载的增加, 网络阻塞率相应增大, 且以接近指数的速率迅速增大。相对而言, 网络负载较小的前半段曲线斜率更大, 网络阻塞率变化更剧烈;而网络负载较大的后半段曲线缓慢增加, 最后网络阻塞率趋向于1。从各图中还可看出, 对于一定复用波长总数, 在提供相同网络负载时, 波长变换范围越大, 网络阻塞率越小, 这主要是由于波长变换范围的增大使选择VWP所受的限制变小, 使波长资源的利用率得以提高, 从而减小了光连接请求被阻塞的概率。对同样的单纤网, 在k=1, 2时, 这个算法与文献[10]所得阻塞率性能曲线 (W=16) 相比, 可取得相对更低的阻塞率。

《图6》

图6 网络阻塞率 (复用波长总数一定, W=64)

Fig.6 Blocking probability (W fixed, W= 64)

2) 在一定波长变换范围 (k=0, 1, 2) 内, 复用波长总数W=8, 16, 32, 64时, 阻塞率随相对网络负载的变化见图7至图9。

《图7》

图7 网络阻塞率 (波长变换范围一定, k=0)

Fig.7 Blocking probability (k fixed, k=0)

定义链路容量WF, 它表征了一条链路可承载光连接的能力。F 为每条链路具有的光纤对数。同一网络拓扑结构, 其他参数固定, 若W或F增大, 则可用的波长信道资源越多, 可建立的潜在光通道的数量就越多, 在计算阻塞率时所加的网络负载就应越大。这在以上图中亦可看出。为了比较不同复用波长总数下网络的阻塞率情况, 部分消除因复用波长总数的不同而造成实验中网络负载范围的不同, 定义:

《图8》

图8 网络阻塞率 (波长变换范围一定, k=1)

Fig.8 Blocking probability (k fixed, k= 1)

《图9》

图9 网络阻塞率 (波长变换范围一定, k=2)

Fig.9 Blocking probability (k fixed, k=2)

相对网络负载=W₀网络负载/链路容量 =W₀ρ/WF, W₀为一因子, 取 W₀= 8, F = 1。

从以上各图中可以看出, 在相同的波长变换范围下, 若相对负载相同, 复用波长总数越大, 则阻塞率越小。相对负载比网络负载更能反映波长级的信道承载情况。相对网路负载保持不变的情况下, 复用波长总数变为原来的2倍, 则各链路的链路容量WF也相应变为原来的2倍, 承载能力翻番, 这时阻塞率并非保持不变, 而是变小。图10的波长重用因子曲线进一步说明了这一结论。

《4 结论》

4 结论

在动态业务流量和有限范围波长变换情况下, 提出了DMC-OVWP算法, 实现动态最小代价路由和最佳虚波长通道分配。该算法以将路由子问题和波长分配子问题既相互独立、又相互结合来处理的思想为指导, 尽可能利用更多的网络状态信息, 保证网络信息的传输。仿真结果与已有文献的比较表明, 本算法不仅可获得较低的网络阻塞率, 而且计算复杂性不高, 保证了网络中信息的传输, 在WDM主干网及未来的WDM-MAN, WDM-AN中都有着很好的使用价值。

《图10》

图10 波长重用因子 (波长变换范围k= 0)

Fig.10 Wavelength reuse factor (k=0)

Show More