一种 WDM网状网中基于故障感知的业务量疏导算法

王 冕,刘成耀

(重庆邮电大学 重庆高校光纤通信技术重点实验室,重庆 南岸 400065)

目前,单纤可以支持 Tb/s业务速率,任何链路或者节点的失效将导致巨大损失.据美国 FCC报告显示,每两天就有一次影响 30 000名客户的网络故障发生,而故障修复的平均时间是 5～10 h.此外,若传输容量达 Tb/s的单根光纤失效,将影响 1 200万对以上的电话业务[1],因此网络的故障容忍策略则为重中之重[2-3].动态业务量疏导已经开始成为故障容忍策略的研究热点.文献[4]研究了业务量疏导过程中建立可靠业务连接的问题;文献[5]提出 2种基于固定备选路由的动态业务量疏导算法,在预计算过程中考虑疏导业务的均衡;文献[6]设计多层网状网络,在满足各种业务带宽要求和保护要求的同时,最小化全网费用,并提出一个数学模型和相关算法;文献[7]研究了在异构 WDM网状网中动态地为具有不同带宽粒度的单播业务请求建立连接的问题,通过扩展文献[8]中的通用图模型,进行有效的业务量疏导,达到不同的业务量工程(Traffic Engineering)目标;为了减小网络中OXC端口费用,文献[9]研究了具有不同交换粒度 OXC的WDM网络设计问题,提出了一种业务量疏导算法自动决定采用网络节点中的某种类型的 OXC;文献[10]研究了节点具有波长变换能力情况下,动态业务量疏导策略.但是,上述文献没有考虑网络故障的疏导策略将会产生负面效应,因此,设计有效的、合理的故障感知业务量疏导策略非常迫切.

1 问题描述

1.1 探测圈覆盖

探测圈覆盖的主要思想是把网络分解为圈的集合,使得网络上的每个节点和每条链路至少被集合中的一个圈所覆盖,称为“探测圈”,每个圈被分配一套探测模块等监测设备.探测圈实际上是闭合的波长通路,网状光网络可以建模为一个有限的无向连通无桥图G(V,E).

图1 探测圈覆盖示例图

任何无桥连通图G(V,E)都有它的圈覆盖C,但不唯一,其中 C中的元素用 c表示.c1和 c2构成了图1所示拓扑的圈覆盖[11].有 3种圈覆盖算法[12]用于发现网络的圈覆盖,即启发式深度优先搜索(HDFS)、最短路径匹配(SPEM)和启发式生成树圈覆盖算法(HST).本文拟采用启发式生成树圈覆盖算法(HST),如图2.

图2 基于HST启发式算法的圈覆盖

如前所述,探测圈覆盖方式使得物理拓扑层内的所有节点和链路至少都被一个探测圈所覆盖,其中圈内的监测节点通过探测包对其它节点以及节点之间链路的性能进行监测.显然,在这种情况下,可以认为网络存在两类节点,每类相同的节点组成各自的逻辑层,这样,探测圈将网络从逻辑上分解为多个圈的集合,网络拓扑结构出现分簇情况,每个监测节点和其所管理的节点构成一个簇.与传统的分簇方式不同,采用这种方式之后,业务量疏导问题可以进一步划分为 2个子问题,分别为簇内业务量疏导和簇间业务量疏导.显然,簇间业务量疏导需要由簇头节点负责,而簇内业务量疏导则按照传统方式执行.按照这种方式,整个业务量疏导过程需要增加网络分割、簇内业务量疏导和簇间业务量疏导 3个过程,其与通常情况下动态业务量疏导策略的流程区别如图3所示.

图3 业务量疏导问题流程描述

2 仿真及结果分析

2.1 网络仿真环境

为了充分验证疏导策略的性能,且便于网络分割,本文采用了如图4所示的网络拓扑结构.该拓扑在NSF网络的基础上新增了 2个节点,即 16个节点,24条链路.各节点之间由 WDM链路连接,每条 WDM链路包括 9个速率为 2.5Gbit/s的波长信道,固定其中的一个波长信道作为控制信道,每个节点都具有完全的波长转换能力.业务源所产生的数据包大小服从均值为 500 B的负指数分布,数据包的最小长度设为 40 B,最大长度设为 1.5 KB;数据包的到达时间间隔服从均值为 8μs的负指数分布;簇头节点的光交换矩阵的配置时间为 2μs.

图4 增加2个节点的 NSF网络拓扑

结合图2,本文将网络分割(如图5),按节点连通度高并同时考虑簇头节点到各成员节点距离最小来选取簇头,则拓扑(1)(2)(3)可选取的簇头节点为节点 11,节点 4,节点 9.

图5 网络分割后的仿真拓扑

2.2 性能评价指标

簇头节点(Cluster-head)成功调度的突发数据用 NB表示,用 SN表示光交换矩阵的开关次数,定义光交换矩阵的交换效率 SW为:

阻塞率[13](Blocking Probability,BP):在给定的网络拓扑和业务量需求情况下,没有成功建立的业务连接请求数与总的业务连接请求数之比.阻塞率越小,说明被拒绝的业务请求越少,算法性能越好.

2.3 仿真结果分析

对于采用业务疏导的节点,无须为被疏导突发配置光交换矩阵,因此数据疏导成功的比例越高,光交换矩阵的交换效率也越高.

对于未采用疏导的节点,每成功传输一个数据突发,光交换矩阵将开关一次,因此光交换矩阵的交换效率为 0.

簇头节点 4(CH 4)的光交换矩阵在不同负载下的交换效率如图6所示,其中节点 4的负载取 0～0.9最小间隔为 0.01的 17个不同值.图6中,当簇头结点 4的负载等于 1.75时,光交换矩阵的交换效率达到最大值 0.27.

图6 簇头节点 4光交换矩阵交换效率示意图

对于无时延突发疏导,当网络负载较小时,数据突发之间的间隔较大,满足疏导条件的数据突发(可疏导数据)较少,从而成功疏导的数据较少,光交换矩阵的效率也较低;随着网络负载的增加,数据突发数量增多,相邻数据突发之间的间隔减小,可疏导数据突发的数量随之增加,从而簇头节点能疏导更多的数据突发,提升了光交换矩阵的交换效率.

当网络负载增大到一定程度时,虽然满足疏导条件的突发数据数量继续增加,但由于簇头节点有限的波长信道资源,能被成功调度的数据比例必然减少,也降低了数据突发疏导成功的比例,此时簇头节点的交换效率不会一直提升.图6说明了这种情形.光交换矩阵的交换效率在簇头节点 4的负载等于 1.75时达到最大值 0.27,随着负载的增加,光交换矩阵的交换效率持续下降;当负载增加到一定程度时,可疏导突发数量的增加对光交换矩阵交换效率的提升作用大于簇头节点丢包率的增大对交换效率的降低作用,光交换矩阵的交换效率继续提高.簇头节点 4的负载从 0.4继续增加,此时节点丢包率的增大对交换效率的降低作用大于可疏导突发数量的增加对光交换矩阵交换效率的提升作用,光交换矩阵的交换效率又重新降低.

图7为核心节点采用业务疏导的网络系统(TG)和没有采用业务疏导算法的网络系统(NTG)随着网络负载增加,数据包丢失概率的变化曲线.

图7 数据包丢失概率曲线

当网络负载较低时,可疏导的数据突发较少,而节点有合适的信道资源调度数据,所以两者丢包率都维持在较低的数值;当网络负载增加时,数据突发的数量增加,节点可用的数据信道空隙长度减小,在相同的网络负载下,采用业务疏导技术的系统丢包概率肯定低于未采用业务疏导技术的系统丢包概率.如图7所示,当网络负载为 0.35～0.55时,采用业务疏导算法的丢包概率明显小于未采用业务疏导技术的系统丢包概率.当网络增加到一定程度时,数据突发数量的增多,使得每个节点都没有足够的波长信道资源调度数据突发,所以此时两者的丢包率都维持在较高的数值.

3 结语

疏导策略设计是 NP-Hard问题,除了需要考虑诸多约束条件,还必须针对广义网络故障进行相应调整.本文提出的面向故障容忍机制的业务疏导算法(FAA),在圈发现算法基础之上建立层次型网络以对业务量进行疏导,经仿真证明,该算法是一种有效的业务疏导算法.与已知算法相比,本文提出的算法既考虑了动态业务量疏导的复杂性,又考虑了网络突发故障,对今后的工程开发具有指导意义.

[1]宋鸿升,吴耀辉,顾碗仪.多层网络中的生存性策略[J].光通信技术,2004(4):33-36.

[2]GerstelO,Ramaswami R.Optical layer survivability:a services perspective[J].IEEEComm.Mag.,2000,38(3):104-113.

[3]Bhatia R S,Kodialam M,Lakshman T V.Bandwidth guaranteed routing with fast restoration against link and node failures[J].IEEE/ACM Transactions on Networking,2008,16(6):1321-1330.

[4]何荣希,温海波,王光兴,等.WDM网状网中基于共享风险链路组限制的业务量疏导算法[J].电子与信息学报,2004,26(4):549-555.

[5]黄善国,罗沛,薄明霞,等.WDM网状网中的动态流量疏导策略[J].北京邮电大学学报,2006,29(2):26-29.

[6]Chen B S,Rouskas G N,Dutta R.On hierarchical traffic grooming in WDM networks[J].IEEE/ACM Transactions on Networking,2008,16(6):1226-1238.

[7]Zhu K,Zhu H,Mukherjee B.Traffic engineering in multi-granularity heterogeneous optical WDM mesh networks through dynam ic traffic groom ing[J].IEEE/ACM Transactions on Network,2007,17(2):8-15.

[8]Zhu H,Zang H,Zhu K,et al.A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks[J].IEEE/ACM Transactions on Networking,2003,11(2):285-299.

[9]Zhu H,Zhu K,Zang H,et al.Cost-effective WDM backbone network design with OXCs of different bandwidth granularities.IEEE[J].Journal on Selected Areas in Communications,2003,21(9):1452-1466.

[10]Xin CS.Dynam ic traffic grooming in op tical networks with wavelength conversion[J].IEEE Journal on Selected Areas in Communications,2007,25(9):50-57.

[11]王汝言,常交法,隆克平,等.基于圈覆盖的光突发交换网状网故障监测方案[J].北京邮电大学学报,2007,30(4):111-112.

[12]Zeng Hong-qing,Huang Chang-cheng,Vukovic A.Span-ning-tree based monitoring-cycle construction for fau lt detection and localization in mesh AONs[M].Proceedings of IEEE ICC'05.Seoul:IEEE Press,2005:1726-1730.

[13]温海波.WDM网状网中的业务量疏导算法[D].成都:电子科技大学,2003:24-25.