基于动态业务下的WDM网络阻塞率

罗丽献 宾志燕 王春霞 周耿铭

（广西科技大学 广西壮族自治区柳州市 545006）

在对WDM 光网络研究中一般有静态与动态两种流量模型。在静态流量模型中，网络的光路连接请求不是随机到达而是预先知道且不会随着时间的推移而产生变化，当全部的连接一旦被建立好之后，将维持这种连接关系。此时的网络状态将保持不变，既不会建立新的连接又不会拆除掉那些已经建立好了的连接，故对各个连接的路由和波长分配可以是非实时的（off-line）。此时主要是利用高效的路由与波长分配算法为光通路连接请求选择路由并分配波长，从而达到最佳的优化效果。

在静态流量模型下研究光网络的配置对网络规划是有一定意义的，但实际网络的业务请求通常不是静态的而是动态变化的。在动态流量模型中，网络中的光路连接请求是随机到达、无法预知的，光工作通路建立后将维持一段有限时间，在通信结束后光通道被拆除，这就是意味着工作通路及备份通路的建立与拆除是随着不断动态改变的业务流量需求而动态变化，而且这些连接请求能否被接纳还得取决于网络的当前状态。由于因此网络状态是不断变化的。可以预见未来的WDM 光网络将会是更加动态变化和对故障是较为敏感的。因此，与光网络生存性的动态服务配置将成为网络规划和管理的关键要求[1,2]。

基于动态流量的光网络性能分析，大都采用传统的短相关的泊松分布模型(Poisson Model)，即假设网络中业务的连接请求的到达速率服从泊松分布。早期相关研究人员对网络流量数据进行分析，首次提出了网络流量中存在着自相似现象[3,4]。在其后的一些研究中，研究人员发现网络通信量的自相似性始终是存在的。经典理论分析泊松过程体现的是短相关，自相似体现的是业务量的长相关性，因此泊松过程不再适合网络流量的分析和建模。由于传统的泊松模型不能准确地模拟网络中的真实业务量，而自相似性过程能更好的描述真实网络中的业务流量，所以在自相似性业务得到的网络阻塞率分析更接近事实。

本文采用分形高斯噪声（FGN）方法生成自相似业务流，结合P 圈启发式配置算法，将其应用到光网络的动态仿真中，并与泊松业务流的阻塞率相比较。

1 自相似动态流量

1.1 基于分形布朗运动和分形高斯噪声模型

图1：均值M=20，V=50，H=0.89 的自相似业务序列

当前网络流量建模研究中，相关研究者提出了不少模型理论，比较常用的是：统一建模的FARIMA（p，d，q)过程模型、M/G/co 排队模型、直接叠加具有重尾特性的ON/OFF 源模型及拥有平稳增量的随机过程的建模方法（典型方法为基于分形布朗运动和分形高斯噪声。本文将介绍一种典型的自相似生成模型——Mandelbrot和VanNess 于1968年提出的一种描述统计自相似过程的数学模型“分形布朗运动(fractional Brownian motion, FBM)及 FGN[6]，FBM的增量过程即为 FGN 序列分形高斯噪声（fractional Gaussian Noise, FGN）过程。

满足以下条件的随机函数x(t)为分形布朗运动过程：

（1）x(0)=0；

（2）对所有的t ≥0，有

其中，Н 满足0<Н<1。这个过程因具有分形维的故被称为分形布朗运动。当Н=1/2 的时候，分形布朗运动过程x(t)就退化成了一般的布朗运动过程（布朗运动B(t)是一种是初始位置为原点、在不相交叉的时间区间上有独立增量及服从高斯分布随机过程）。

基于分形布朗运动过程的整个网络的自相似业务流模型可形式化表示如下[7]：

单位时间内网络自相似流量模型为：

图2：均值M=20 的泊松业务分布序列

图3：动态P 圈配置的流程图

图4：NST 网络拓扑

其中At为到时刻t 为止的网络业务流，BН(t)表示为一个标准FBM 过程m 为业务的平均到达速率，a 为方差系数且取值范围为a > 0, BН(t)为Нurst 参数(即Н)，其取值范围为0.5<Н<1，主要用来描述自相似程度的高低，Н 值的数值越大，其自相似程度就越高。

1.2 生成泊松和自相似的时间序列

FGN 序列是一个精确自相似过程，该模型有3 个特征参数，即为自相似系数Н，单位时间内到达的平均连接数M，方差系数a。为便于取数，假设单位时间内达到的连接数的方差为V，a=V/M。确定此3 个特征参数即可生成自相似业务序列，图1 为随机生成的自相似业务序列。

基于泊松业务流量下，在仿真的过程中我们假设光路连接请求符合到达率均值为λ 泊松过程，光路的平均维持时间满足1/μ 指数分布。生成业务到达率服从均值为λ 泊松分布，相当于生成任意连续到达的两次业务的间隔时间服从参数为1/λ 的指数分布，因此，我们先生成通过函数(log(rand())/RAMD_MAX)产生0 到1 之间的随机数，并可通过1/λ*(log(rand())/RAMD_MAX)计算出下一个业务到达的时间间隔。为计算所有光路请求的维持时间，我们仍旧通过函数(log(rand())/RAMD_MAX)产生0 到1 之间的随机数，接着通过1/μ*(log(rand())/RAMD_MAX)计算出光路的持续时间。

比较图1 和图2 可看出，泊松业务序列较平稳，而自相似业务序列波动范围较大，较能体现出业务量的突发性。

2 动态的P圈配置

2.1 P圈启发式配置算法

光网络可表示为为一系列点V 和一系列边E 组成的图G = (V, E)。设i 为网络所有备选圈的集合。保护效率（ER）定义为此P 圈所能保护的工作容量与配置这个P 圈所需的空闲容量的比值[5]。

此式中，Wj表示链路的工作资源；xij表示当前情况下链路j 是否可以被备选 的所保护，是则xij为1，否则xij为0；pij表示表示链路j 是否为备选圈i 的圈上链路；是则pij为1，否则pij为0。ERj为性能指标，量化这个备选圈的高低，ERj值越大，代表此P 圈越高效。

基于P 圈启发式配置算法的配置如下：

（1）根据P 圈的最大物理长度或者所经过的节点数，计算出网络中的P 圈的物理长度都不超，构成所有简单圈的集合：

1.找出任一链路（边）e∈E，并从集合G 中删去边L；

2.在网络资源图G = (V, E)找出途经链路e 的两节点之间的所有路径的集合Lpath。

3.路径的集合Lpath 各自与原链路e 首尾连接，就可得到与链路e 相关的备选圈集。

4.转到步骤（1）直到找完所有的简单圈。

（2）根据网络中的流量需求,采用最短路径算法（链路的代价为链路空闲资源数的倒数）来给光路需求分配路由并计算网络每条链路上的工作容量。

（3）计算步骤（1）找出的每个备选圈所能保护的工作容量和构造此备选圈所消耗的空闲容量，求出所有备选圈的ER。

（4）选择具有最大ER的P圈，记为imax，并把imax配置到网络中，通过减去imax所能保护的工作容量，更新网络中未被保护的工作容量，同时通过释放构造imax所消耗的空闲容量，更新网络中剩余的工作容量。

（5）重新计算步骤（4）所选的P 圈及与此P 圈有一条或多条公共链路的备选圈的ER，并保留与此P 圈不存在公共链路的其他备选圈的ER，转步骤（4）。

（6）如果网络中每条链路的未被保护的工作容量都为0，则算法结束；否则，则转步骤（5）。

2.2 动态P圈设计

对于动态P 圈配置的过程中，网络间的业务是动态的，各个节点之间的业务是不是固定的，而是随机到达的，建立好的业务的连接请求在持续一段时间后将北释放掉，整个网络的业务分布情况都是动态变化的。因此，需要动态的P 圈配置来保护动态变化的网络业务。动态P 圈配置是根据当期网络的实时资源情况、故障发生情况及当前所计算的P 圈集合是否可以保护当前的网络业务的情况，动态地计算最优的P 圈，并且修改P 圈的配置情况，为下一次新业务的到达及发生的故障提供保护。动态P 圈配置具有能够为网络提供可靠的保护和资源利用率高的优点。

此算法为光通路连接请求动态的选择路由并分配波长，最终优化目标是使网络的阻塞率达到最小化。本文的阻塞率=被网络阻塞的业务数/到达网络的业务总数。此算法的流程图如图3 所示。

新业务请求随机到达时，本文基于动态P 圈配置的算法思路主要为：

（1）拆除所有先前配置的P 圈，释放占用的波长资源数，运用最短路由（Dijkstra）算法计算源节点到目的点的路由，如果能到为光通路连接请求选择路由并分配波长，则为该请求分配连接；否则就阻塞掉该请求。

（2）当步骤1 中的光通路成功连接后，更新网络中链路的工作容量，用基于P 圈启发式算法来配置P 圈，如能够对原有业务的光通路以及新业务的光通路进行100%的保护，则接受此连接请求，否则阻塞掉此连接请求。

2.3 实验结果分析

本文的实验数据结果选取点度数和网络密度较小的北美NSFNET 网络拓扑进行仿真，见图5 在仿真实验中，有两点前提假设。一是假设节点具有全波变化功能，每条链路都满足双向传输的工作要求，每个业务请求的带宽为1 个波长单位。二是假设网络中所有的节点间的业务强度都相同，即支持均匀分布的业务量。到达业务请求的源、宿节点在所有节点对之间随机选择，如果能够找到合适的工作路径和保护通道，则为该请求分配连接；否则阻塞该请求，即无等待队列。

本文所分析的阻塞率为全网平均阻塞率，图4 为NSF 网络拓扑下泊松业务流和自相似业务流的阻塞率，其中自相似业务流量的Н=0.83，V 为一个固定常数，两种流量的维持时间满足从均值为1/μ 的指数分布M 与泊松业务的均值λ 相对应。

从图5 中看观察到， 当整个网络处于较轻的网络负载且在相同的均值M 下，由于基于自相似业务具有突发性，所以其阻塞率要远远高于基于泊松业务流的阻塞率。随着均值M 的不断增大，整个网络处于较重的网络负载，而处于较重负载网络的阻塞是由于通道链路上没有足够剩余空闲波长可用，造成连接请求被阻塞掉，所以基于自相似业务的阻塞率与基于泊松业务的阻塞率的差距会大大缩小。

由以上数据可知，由于FGN 模型可以提供更详细的参数生成自相似性业务流，传统的泊松模型已不能准确地模拟网络中的真实业务量，故在自相似性业务得到的网络阻塞率分析更接近事实。

3 结语

本文主要介绍了FGN 法生成自相似业务分布序列的过程，并与泊松业务分布序列相比较，体现了自相似流量具有突发性。当整个网络处于较轻的网络负载且在相同的均值M 下基于自相似业务的阻塞率比基于泊松业务的阻塞率要高。由于FGN 模型可以提供更详细的参数生成自相似性业务流，而传统的泊松模型不能准确地模拟网络中的真实业务量，故在自相似性业务得到的网络阻塞率分析更接近事实。

图5：泊松与自相似的阻塞率比较