RWA问题

RWA问题（精选6篇）

RWA问题 篇1

1 引言

随着网络技术的不断进步, 以及信息化程度的不断加深, 对通信的容量、速度、质量以及服务种类的要求也是越来越高, 这些都对带宽提出了更高的要求, 而自动交换光网络[1] (ASON) 是在信令网的控制之下完成光通道的建立和自动交换功能的新型网络, 代表未来光网络技术的发展方向。这种网络数据的传输和交换过程都在光域内完成, 不存在任何光电转换, 避免了电子器件所产生的电子瓶颈, 具有较大的带宽。

自动交换光网络中采用波分复用技术 (WDM) 进行信号传输, 即将信号由发送端复用到同一根光纤的不同波长段上, 再经信道传输, 这样将同一条链路分为多个通信信道, 扩大了信道传输容量。由于信道中波长资源是有限的, 如何合理优化网络, 利用有限的波长资源最大限度的建立连接, 改善网络阻塞性能, 是人们关注的焦点。路由选择和波长分配[2] (RWA, Routing and Wavelength Assignment) 问题是指当一个连接请求到达时, 为该请求选择合适的路由并分配波长资源, 它是ASON中的一个核心问题, 针对不同业务的特性和连接请求方式, 可将RWA问题分为静态RWA与动态RWA问题。对于静态RWA问题的优化目标是使所用波长数最小, 或者在波长数给定条件下, 尽可能多地建立连接, 而动态RWA主要优化目标是降低网络阻塞率。由于RWA问题是NP完备性问题, 为降低其复杂度, 通常将其分为路由选择子问题和波长分配子问题来研究。

2 静态RWA问题

静态RWA算法以最小化波长数为优化目标。该问题可以归结为一种规划问题, 通常用整数线性规划ILP (Integer Linear Programming) 方法进行描述, 这种方法适合于规模较小的网络, 当网络规模较大时, 通常拆分为路由选择子问题和波长分配子问题来求解。

2.1 静态RWA的类型

根据业务类型的不同, 静态RWA问题可以分为支持电路交换业务的SRWA算法和支持分组交换业务的SRWA算法两类。前者业务需求矩阵给出了每个节点对之间需要支持的光通道数目, 而后者则存放节点对之间归一化的平均分组业务强度。对于支持电路交换的SRWA, 由于同时实现业务需求的路由选择和波长分配需要较长计算时间, 因此不适合在大型网络中应用, 通常将其拆分为路由选择和波长分配两个子问题。而当光网络用于传送分组业务时, 光层网络的优化目标和优化策略方面存在明显的不同, 这时光网络上叠加有电交换层的重叠多层网络结构就成为主要的研究对象。影响支持分组交换的SRWA算法设计的主要因素主要有成本因素、拥塞因素、时延因素、映射因素等。

2.2 静态RWA中路由选择子问题

对于静态RWA路由选择子问题, 常采用启发式算法进行求解, 主要有固定路由算法 (Fixed routing) 和固定备选路由算法 (Fixed-alternate routing) 两类[3]。

2.2.1 固定路由算法

固定路由算法是一种最简单的路由算法, 选路是事先进行的, 网络总是为同一节点对提供固定不变的光通道。选路过程如图1所示, 在一个6节点的网络中使用该算法进行选路时, 节点0到节点2之间的工作路由依次经过了节点0、1、2, 而节点0到节点3之间的工作路由依次经过0、1、2、3。该路由算法比较简单, 容易实现, 但却需要较多的波长资源, 且容易使某些链路波长资源耗尽, 从而导致网路拥塞迅速增加, 由于没有备用路由, 故不具备故障恢复能力。

2.2.2 固定备选路由

固定备选路由算法是对固定路由算法的改进, 源节点和目的节点对之间不仅存在最短的工作光通路, 还存在一条或多条备用路由作为保护光通路, 且它们在物理上具有最大程度分离的特点。选路过程如图2所示, 在节点0与节点2之间除经过0、1、2的最短路由之外, 还存在另外一条经过节点0、5、4、2的备用路由。由于能够在工作路由发生阻塞时, 选择备用路由作为新的工作光通路, 该方法可使网路具有一定程度的故障恢复能力, 降低了网络的拥塞概率, 流量的阻塞概率明显减小。

2.3 静态RWA中波长分配子问题

当采用路由算法为一个连接选择一条路由之后, 必须在满足不同波长限制条件和波长连续性限制条件的基础上, 为光通道选择合适的波长。对于静态RWA, 波长分配算法主要有着色图算法以及遗传算法、模拟退火算法等启发式算法, 有时对于较复杂的网络, 常将一些算法结合起来使用。

着色图算法[3]首先为原网络拓扑图建立一个辅助图G' (V', E') , 然后将辅助图中的每条光通道用一个顶点V'来表示。对于经过相同链路的不同光通道, 采用边来将其顶点相连, 并在辅助图中为顶点V'着色, 保证相邻的顶点不着相同的颜色, 如此将波长分配问题转化为光通道着色问题。辅助图中的颜色总数就是网络的波长需求数目。这个着色问题已有有效的算法, 但较为复杂, 为简化可采用启发式算法求解, 如遗传算法、模拟退火算法等。

遗传算法[4] (GA:Genetic Algorithm) 是一种基于自然群体遗传演化机制的高效探索算法, 它是一种基于“适者生存”的一种高度并行、随机和自适应的优化算法, 编码和遗传操作比较简单, 优化不受限制性条件的约束, 其最显著的两个特性是:隐含并行性和全局解空间搜索。遗传算法常被广泛用于非常困难的混合优化问题的求解。

模拟退火算法对NP完全组合优化问题尤其有效。由于该算法源于固体退火过程, 即先将温度加高, 再慢慢降温 (即退火) , 使之达到能量最低点。虽然模拟退火算法会产生局部最小值, 但从整体来看, 还是能够给出较优解的, 并且较优解更容易产生在低开销区域中。总之, 该算法实现简单, 比较适用于组合优化问题中, 不足之处在于计算复杂度较大, 对于存在较优解的情况, 很难实现进一步改善。

3 动态RWA问题

动态RWA算法以降低网络阻塞率为优化目标, 一般采用启发式算法来求解, 由于连接请求的随机到达性, DRWA的求解不能采用整数线性规划 (ILP) 或者着色图等处理静态问题的方法来求解。动态RWA问题同样属于NP-C问题, 一般将该问题分解为路由选择子问题和波长分配子问题分别求解。

3.1 动态RWA中路由选择子问题

通常将动态RWA路由子问题分为三种, 即:固定路由算法、固定备选路由算法以及自适应路由算法。自适应路由算法是根据网络状态, 来为源、目节点对之间选择路由, 该算法与固定路由算法、固定备选路由算法相比, 在拥塞概率方面有明显优势, 但这也是以计算复杂度增加为代价的。这三种路由之间的比较如表1所示。

3.2 动态RWA中波长选择子问题

选定一条路由后, 要为其分配波长, 对于波长分配算法, 目前有较多的研究, 提出了多种算法, 常用的波长分配算法有以下几种[7]:

(1) 随机波长分配算法 (Random) :首先遍历所有波长, 确定选定路由上的可用波长集, 再从中随机选择波长分配给该路由。

(2) 首次适配波长分配算法 (FF:First-Fit) :在网络的规划阶段该算法将波长在可用波长集中按固定顺序 (如按由小到大顺序排列) 进行统一编号, 编号低的波长比编号较高的波长优先分配给光通道。与随机分配法相比, FF法不必搜索全部波长, 找到可用波长就进行分配, 计算量更小, 分配速度也较快, 不需要知道全网的状态信息, 在降低阻塞率和提高网络的公平性方面性能较好。

(3) 最长跳数算选择法:根据确定的连接请求路由, 将跳数从大到小进行排列, 首先为最长光路分配波长。当网络负载较大时, 其网络的公平性是以阻塞率的增加为代价的。

(4) 最少使用波长分配算法 (LU:Least-Used) :该算法根据网络当前的状态统计出各波长的使用情况, 并将波长使用率按升序排列, 在选定路由上, 选择波长使用率最小的可用波长分配给连接请求。

(5) 最大使用波长分配算法 (MU:Most-Used) :该算法与LU算法相反, 优先选用使用率最高的波长。

(6) 最小乘积算法 (MP:Min-Produce) :该算法针对多纤网络设计, 当每条链路中的光纤数目为1时, MP算法就蜕化为FF算法。算法首先对所有波长进行编号, 然后根据网络当前状态, 计算出选定路由上各段链路的每个波长已被占用的信道数的乘积, 最后选取具有最小乘积且编号较低的空闲波长建立光路。

(7) 最轻负载算法 (LL:Least-Loaded) :该算法也是对多纤网络设计的。首先对所有的波长进行编号, 以确定在选定路由上各波长的可用信道数, 然后从中选择具有最大可用信道数的波长。

(8) 最大总和算法 (MS:Max-Sum) :该算法可用于单纤网络或多纤网络。对于一个连接请求, 在选定的路由上, 对所有可用波长依次计算将可用波长分配给该连接请求后, 网路中其它所有通道可用信道数总和, 选择可用波长数总和最大的波长。

(9) 相对容量损失算法 (RLC:Relative Capacity Loss) :该算法在最大总和算法的基础上形成, 与MS算法类似, 都适用于流量非标准的网络, 但RLC算法的效果更好一些。RLC算法主要是使相对容量最大化。

(10) 最小影响算法 (LI:Least Influence) :该算法为新业务在选定路由上分配波长时, 考虑选用对全网其它通路影响最小 (对相关通路造成的瓶颈综合最小) 的波长。

(11) 相对最小影响算法 (RLI:Relative Lease Influence) :该算法在最小影响算法的基础上, 将各相关业务在各波长的瓶颈链路数除以此业务的可用信道总数, 再将此比值累加, 选择其中具有最小累加值的波长。

各种波长分配算法计算复杂度比较如表2所示, 其中L表示链路数目, N表示节点数目, W表示可用波长数目。

4 RWA算法中的其它问题

RWA问题是ASON设计中的一项关键技术, 不仅影响到网络中波长的利用率, 还会影响到网络的其它特性, 如业务容量、传输时延、设备端口数等, 从目前研究情况来看, RWA算法中还存在以下几个问题需要解决:

(1) 非精确网络状态问题[5]:在大规模网络中保持网络全局信息的精确性几乎是不可能的。网络的准确性受到许多因素的制约, 如时延问题、网络状态更新频率, 以及大型网络状态聚集等。因此, 对于非精确网络状态信息下的RWA算法进行研究很有很大的必要性。

(2) 波长转换问题:引入波长转换可使在一条光路上分配波长时更加灵活, 动态建立光路时阻塞率减小。由于波长转换器价格昂贵, 且技术上有限制, 因此波长转换器在网络中的作用仍是一个争论的焦点。波长变换对RWA问题结果的影响以及怎样在网络中引入波长变换以达到性能最佳等问题还需进一步的研究。

(3) 综合优化问题[6]:网络设计需要优化的目标有很多, 若仅仅考虑其中的一个, 而没有考虑各个特性之间的均衡折中, 网络的代价并没有因为算法的优化而降低。因此, 要研究基于提高网络综合性能 (如业务分级优化、公平性等) 的合理算法, 以减少网络代价。

(4) 多播技术问题:在光层实现多播, 就是将一个源节点光信号同时发送到多个目的节点, 需要建立一个光树。多播路由优化是指通过共享通信资源, 实现通信资源的优化配置, 该应用的普及导致多播主干网络的快速发展。对多播光网络的研究目前主要集中在RWA算法方面和流量疏导问题。

(5) 抗毁问题:光网络的抗毁主要针对光网络中可能出现的硬件故障 (如光纤断裂或网络节点故障) 而设计的故障保护和恢复机制。光网络的抗毁非常重要, 工作光通路和保护光通路的优化也很重要, 必须同时考虑才能达到网络的整体优化。一种情况是只考虑网络本身的抗毁, 可以分为保护和恢复两种机制。另一种则是考虑IP over WDM网络的抗毁, 将涉及到光层和IP层的多层抗毁问题。

(6) 服务策略问题:RWA分配过程中所选择的光通路一般未考虑物理层传输系统的约束和高层业务的要求, 但在网络实际运行时要引入各种策略, 例如引入优先级、某些光路必须经过某些节点, 而另一些光路则不用, 选择的光通路要满足WDM传输系统的可靠性要求等, 解决这些问题时需要有相应的RWA算法。

5 结束语

ASON是构建下一代光网络的核心技术之一, 本文重点对ASON中为连接请求建立光通路的波长路由算法进行了阐述和研究, 分别介绍了静态RWA与动态RWA问题的优化目标、路由选择和波长分配问题, 以及RWA算法设计中存在的其它问题。在ASON中, 受限于网络资源, 为了合理选择路由分配波长资源, 对RWA算法的优化已经成为了研究的热点。

参考文献

[1]赵丽霞, 胡宗福.自动交换光网络中路由问题的研究[J].光通信技术.2006, 12:96-101.

[2]张宝富等编著.全光网络[M].北京:人民邮电出版社.2002.

[3]乐孜纯, 张明, 全必胜.光网络实用组网技术[M].西安:西安电子科技大学出版社.2008.

[4]Peiyuan Lee, Yongtao Gong, Wanyi Gu.Adaptive routing and wavelength assignment algorithm for WDM networks with uniform and non-uniform traffic model[J].Communications Letters.IEEE.Jun2004, 8 (6) :397-399.

[5]吕翔.波长路由光网络相关问题研究[D].浙江:浙江大学, 2006.

[6]Esa Hyytia.Resource Allocation and Performance Analysis Problem in Optical Networks[D].Espoo Finland:Helsinki University of Technology, 2004.

[7]龚文芳.WDM全光网络中固定备选路由算法的实现及其算法优化[D].浙江:浙江工业大学, 2007.

[8]乐孜纯, 付明磊.IP over WDM网络中一种新型虚拓扑构造算法[J].通信学报.2007, 6 (28) :96-101.

RWA问题 篇2

1 基于下一代光网络的业务需求

电信网的发展正在由技术驱动向业务驱动演进。能否提供满足客户需要的业务,能否不断创新业务以满足不断增长的客户需求已经成为市场竞争成败的关键。ASON基础之上的业务光网络的发展演进趋势,正是逐渐丰富其业务提供和支撑能力,其核心是实现光层波长带宽资源的可管理和基于此的业务提供。基于ASON的业务光网络平台的业务框架如图1所示。

在此框架中,处于底层的是基于ION的新一代业务传送平台,主要由ASON来实现,具备快速灵活的传输资源配置能力和业务信息传送能力,其底层传输技术可以是OTN 技术或SDH 技术;在底层业务传送平台之上,是基于带宽资源的可管理连接业务,包括专线连接、光以太网业务等连接业务,这些业务可以由光层以传送连接相关的光层增值业务的形式直接向客户提供,也可以作为进一步开发增值业务的基础;处于最上层的是基于连接业务的可承载增值业务,光虚拟专网(OVPN)、带宽按需分配(BOD)、服务等级协定(SLA)分级业务等都可直接接入光层的新型光网络增值业务。ASON 可以支持多种业务模型,每种业务模型都具有自身的业务属性、目标市场和业务管理需求。综上所述,下一代光传送网应当满足如下业务需求,见表1。

这些业务需求的实现需要由下一代光网络关键技术来支撑,而下一代光网络关键技术的发展也应当充分考虑业务需求,如业务提供的动态化、业务种类的多样性、业务提供的个性化特点和业务的区分性特性等,以更好地实现业务需求。

2 面向业务的RWA问题研究

由以上分析可知,下一代光网络具有诸多不同于传统光网络的业务需求,而RWA是业务提供的一项核心技术,因此在为业务计算路由和分配波长的过程中,它需要面向业务需求进行相应的转变。

在传统WDM网络中,RWA问题主要表现在有光路径的建立请求时,计算如何在网络的物理拓扑结构中选择一条从业务源节点到目的节点的路由,并为路由经过的链路分配波长。在缺少波长变换器的条件下,还要遵循波长一致性限制。在前人工作中,用分层图模型综合考虑RWA问题,但网络规模较大时,问题解决难度大。鉴于RWA问题的复杂性,一般分为路由和波长分配两个子问题来分别解决。选路子问题即为寻找单个路由或多个路由问题。路由常见的算法有:固定路由(FR)、固定备选路由(FAR)和备选路由(AR)。当源宿节点间有多条波长可用时,波长分配算法负责从中选择一条最合适的建立光路。常用的算法有:随机分配(Random)、首次命中(FF)、MaxSum算法、最少使用(LU)、最多使用(MU)、相对容量损失(RCL)和相对最小影响(RLI)算法等。这些算法基于不同优化目标(如资源利用率、网络阻塞概率、生存性等),适用于不同的范围。但是,这些算法都没有考虑业务属性和业务等级,把所有的业务同等看待,没有体现出业务的“个性”,不能很好地满足业务需求。

因此,在面向业务的ION中,RWA问题的研究应该密切关注对新的业务需求的支持,在选路和波长分配环节增强对业务因素的考虑。业务提供的动态性要求RWA算法能够实时动态地为业务连接进行选路和分配波长;业务的个性化要求RWA算法按业务属性、业务参数进行选路和分配波长;业务的多样性和区分性要求对业务进行等级划分,为不同等级的业务绑定不同的连接技术指标,使用户可以按需选用不同等级的服务,这要求RWA算法能够区别对待不同等级的业务。基于业务的RWA算法以满足业务需求为目标,业务连接请求由网络中对应的资源实现。它与传统的RWA算法的区别体现在以业务为核心,即从业务视角来设计RWA算法,实现对业务参数的要求。通常,业务参数包括:SLA和业务等级、优先级和抢占能力、保护和恢复、策略属性等。SLA一般与用户的业务需求相对应,承诺各种分级的服务水平,不同级别的服务水平会对应一套不同的参数以及参数取值,包括服务质量(QoS)和业务等级(CoS)参数等。业务种类的多样性要求能为业务区分优先级,根据优先级的高低分配资源,使高优先级的业务可以更好地获得服务,还可以根据一定的规则实现资源的抢占机制。网络中出现故障时,就需要通过保护和恢复来保障生存性,保护所需的预分配资源并且能对故障作出快速响应,而恢复则依靠动态资源的建立。

基于业务的RWA算法可以将上面提到的业务参数转化为具体的约束条件用于选路和波长分配。基于业务的选路算法的设计可采用权值法、剪除法和选择法[2]。在权值法中,可将各约束条件量化,构造出一个评价指标,使它能同时满足多种业务需求和其他优化指标,并将此指标定义为“距离”,再使用Dijkstra或Bellman-Ford算法求得最短路径,则所求取的路径一定是最佳路径。剪除法在计算路由之前,将不满足条件的路径剪除,然后再在修剪过的拓扑上运用SPF算法。剪除法的计算方法相对简单,结果稳定,但一般只适用于前验性的约束条件(如带宽、时延、波长连续性、资源类型、特定的包含和排斥条件等),对于后验性的条件(如总长度、可靠性等)只能反复重试。选择法首先在不考虑约束条件的情况下,从源节点到目的节点之间找到多个可用的路径,然后在目的节点根据多种约束条件的综合考虑选出一条最优的路径。这3种方法还可以组合使用以降低算法的难度。在波长分配算法中,当源宿节点间有多条可用波长时,由于光交叉连接(OXC)为每条链路配置了共享风险链路组(SRLG)、保护类型、链路编码、最大和最小预留带宽等信息,选择波长时可同时考虑链路信息,使选择的波长链路能满足业务的属性。

3 面向区分业务的RWA问题研究

由于下一代网络中业务具有多样性和区分性的特点,因此应该为业务定义不同的业务等级,按业务等级提供差异化的传送服务。

目前国内外研究者已提出多种支持优先级的RWA 算法以实现区分服务。文献[3,4]通过为各个优先级业务对应的光路连接请求预留一定数量的波长来控制相应优先级请求的阻塞率,文献[5,6]采取的方法是为不同优先级连接请求预设不同的波长分配限额。上面提出的算法均基于固定路由策略,都是在波长分配子问题中通过限制不同优先级业务的波长使用情况来控制不同优先级业务的阻塞率。能否在选路过程中控制不同优先级的业务的阻塞率实现区分服务是个值得研究的问题。在FAR 中,可以考虑将各条备选路由按路径长短或其他的指标排序,这里以路径长短排序为例,最高优先级的业务从最短的路径开始搜索可用资源,如没有可用资源,则搜索次短路径直至所有路径。较低优先级的业务从某指定的路径开始搜索直至最长路径,如无可用资源,再依从长到短的顺序搜索未搜索过的路径。这样使得高优先级的业务可以优先占用较短的路径而低优先级的业务则首选较长的路径。

在上述算法的基础上,本文提出了面向区分业务的RWA实现框图,如图2所示。

用户可根据自身的业务需求选择合适的业务等级来定购自己满意的服务,业务等级的制定主要考虑来自用户的业务需求和来自网络的资源限制等,业务等级参数可包括连接建立时间、业务性能保证、业务可用性和弹性恢复和路由约束等。选择完成后,用户选取的业务等级参数将映射到业务等级解析模块,进而解析成算法可以实现的定量值,再通过在RWA算法库中调用相应的算法为业务选择路由配置资源,最终完成用户请求的服务。

4 结束语

本文分析了下一代光网络的业务需求,提出了面向业务的RWA问题——即把对业务需求的满足作为RWA算法的一个优化目标。实现上可把业务参数转化为约束条件用于RWA算法的设计中,可采取3种实现方法:权值法、裁剪法和选择法。以实现区分服务为目的对基于优先级的RWA算法进行了分析、研究,并提出了在选路中实现不同优先级业务区分的思想,给出了面向区分业务的RWA实现框图。本文只对面向业务的RWA问题进行了初步的探讨,对它的研究还有待深入进行。

参考文献

[1]赵继军,李永,施社平.基于ASON的业务提供与管理技术[J].中兴通讯技术,2004,10(6):33-37.

[2]李慧.智能光网络路由优化的研究[D].北京:北京邮电大学,2005.

[3]Birman A,Kershenbaum A.Routing and wavelengthassignment methods in single-hop all-optical networkswith blocking[J].IEEE INFOCOM,1995,(2):431-438.

[4]何荣希,李乐民,徐世中.WDM光传送网中支持优先级的波长分配算法[J].通信学报,2001,22(3):27-32.

[5]Cheng Shengtzong.Backtrack routing and priority-based wavelength assignment in WDM networks[J].Computer Communications,1999,22(1):1-10.

RWA问题 篇3

光传送网(OTN)的可重构节点技术已经趋于成熟,而上层的智能控制技术还处于研究和探索阶段。控制平面的关键技术包括:RWA技术、分布式呼叫和连接管理信令技术、链路诊断、源管理技术、自动发现技术以及数据通信网业务自适应技术等等。自动交换光网络(ASON)在一定程度上解决了RWA技术和分布式呼叫和连接管理信令技术的难题,但对WRON的RWA问题的优化和设计提出了更高要求。所以对WRON中RWA算法的研究具有十分重要的意义。

1 WRON中的RWA问题

WRON被认为是构建下一代光网络的候选方案之一。但是由于网络资源有限(如波长数、收发器数目等),不可能在网络中为每一节点对都建立一条直接相连的光路,因此针对不同的网络需求,需要考虑对现有可用资源进行高效利用和优化设计。WRON的核心问题是优化设计光路的选路和波长分配,寻找一条合适的光路并为之合理地分配波长,使有限的资源充分发挥作用,以提供尽可能大的通信容量。

根据光通道连接请求的特点,可以把RWA问题分成静态和动态两类。

(1) 静态RWA(SRWA)问题:

网络的业务类型是静态的,而且当所有连接建立好之后,连接将保持不变。光通道连接请求是预先给出的,因此要求离线计算路由和分配波长,而不需要实时计算。SRWA问题的研究适合广域网(或骨干网),因为对于广域网来说,其业务流量基本是确定的。SRWA的输出结果是所有的源-目的节点对之间的光通道的路由以及给这些光通道分配的波长。

(2) 动态RWA(DRWA)问题:

光通道连接请求是逐条提出的,而且一条光通道持续一段时间后又被拆除,因此需要为每一条光通道做实时RWA计算。对于DRWA问题,对光通道建立请求的处理通常有两种策略:可重构型策略和不可重构型策略。所谓可重构型策略,就是当网络拥塞发生的时候,光网络的逻辑拓扑可以进行重构,以消除拥塞情况。但是这样的操作可能会中断很多现有的连接,而且需要对网络节点之间的光通道进行大量的调整(拆除或者重新建立),因此不适合大规模的网络。而不可重构型策略,则在拥塞发生的时候不能重构光通道,只能拒绝该请求。

总体上看,RWA中的路由和波长分配是不可分割的,但是由于RWA是个NP-C(非确定型多项式-完全,Nondeterministic Polynomial-Complete)问题,要在合理的运算时间内解决大型网络的RWA问题是不可能的,只能对规模有限的网络优化作出RWA问题的解答,所以目前一种求解RWA的方法是采用图分层方法,这种算法可以将路由和波长分配一起完成。另一种方法是把RWA问题分解为路由子问题和波长分配子问题。这种方法通常先为WRON选路,即先解决路由子问题,然后在满足一定优化性能的情况下逐一为光路分配波长。它们大多建立在传统的无向图的模型之上,在该模型中首先为每个光路请求找出最佳路由,然后再分配波长。

1.1 路由子问题

对于将RWA问题分两步进行的求解,影响阻塞率的因素主要在路由算法上。目前解决路由子问题的主要方法大致如下:

(1) 固定路由选路(FR)法:

选路是事先进行的,网络拓扑结构已知后,按照标准最短路径算法(如Dijkstra算法和Bellman-Ford算法)为每个节点对分配固定的光路。当光路请求到达时,源、目的节点对之间的通信连接总是建立在预定好的路由上。这种方法的优点是可以把RWA问题简化为波长分配问题,从而大大简化网络的控制和管理。缺点是网络性能较差、阻塞率较高。另外,该算法中网络不具备链路故障恢复能力。

(2) 固定备用路由选路(FAR)法:

FAR的核心思想是为每个节点对预先确定多条备用路由,并按一定的优先级顺序排列。排在最前面的称为主路由,其他的视为备用路由。当业务到达时,按照工作路由建立光通路,当工作路由己被占用或失效时,选择次优路由。与固定路由方案相比,网络的阻塞率大大降低,网络具有故障恢复能力,但时间复杂度相对较高。

(3) 自适应选路(AR)法:

AR算法中路由根据网络的状态动态地确定。它的实现可采用以下两类方法,第一类是预先为节点对之间确定多条备用路由,与固定、备用路由方案类似。第二类方法是不预先为节点对确定备选路由,当连接请求到达时根据网络状态为其确定路由。AR业务请求的阻塞率同FR和FAR相比最低,但网络的控制和管理比较复杂,时间复杂度也大大提高。

(4) 整数线性规划(ILP)法:

通常分为基于流的ILP和基于通道的ILP。基本思路是:列写优化目标方程→列写约束条件方程→求解线性规划。这里可以利用现有的线性规划软件工具(Lingo)对光网络拓扑设计的ILP方程进行求解,最终求得优化路由的方法。利用ILP选路灵活,网络可以具有或不具有故障恢复机制,但是这种方法只适用于规模较小的网络。

(5) 路由扩展方法:

该方法是在一段链路中插入一个节点,用新节点与原链路两端节点构成的两段链路来替换原来的一段链路,这样就构成了一个新路由,利用逐步扩展思想来构造节点之间所有的可能连接方式。此方法既可以用于网络的实际拓扑,也可以用于网络的虚拓扑。这种方法对于业务的恢复路由计算速度比较快,但路由扩展方法只是一种局部的方法,不具有全局性。

WRON中的路由子问题是确定光通路经过哪些光纤链路,从整体上讲它可以分为基于全网信息和基于局部信息的两种方式,这两种方式可以在权重定义和选路算法中得到体现。所谓基于全网信息是指做出路由决策的节点维护有全网每一条链路的资源信息。这种方式既适用于集中式控制的网络,也适用于分布式控制的网络。基于全网信息的路由策略是基于端到端的通路来选择路由的,而基于局部信息的路由方式是以逐跳方式确定路由的。与基于全网信息的路由策略相比,基于局部信息的路由策略更为灵活,具有很强的可扩展性,但其缺点是连接建立的时间较长,信令过程比较复杂。目前,基于全网信息的路由方式是一种较为成熟的路由策略,因此很多文献都是讨论这种路由策略中的各种算法。

1.2 波长分配子问题

RWA中另外一个重要子问题是波长分配问题,它可以影响全网的资源利用率和网络负载,所以选择合适的波长分配算法对于提高全网的资源利用率和网络负载均衡有很重要的作用。下面介绍目前解决波长分配子问题的算法。

1.2.1 基于局部信息的波长分配算法

此类算法仅考虑待分配连接请求路由上的波长使用信息,不需要考虑全网的波长使用情况,是最简单的一类算法。此类算法中常见的有:

(1) 随机分配(R)算法:

首先搜索所有波长的集合,找出可用波长集,再从中随机选择波长分配给光通道。

(2) 首次命中(FF)算法:

将波长在可用波长集中按固定顺序排列,对新到达的连接请求要建立的光通路,每次选择波长时均按固定顺序选择可用波长,并将选到的可用波长分配给路由。

1.2.2 基于全局资源信息的波长分配算法

这类算法首先对全网所有波长资源的使用情况进行分析,根据分析的结果选取最适合全网状况的一个可用波长。常见的算法有:

(1) 最大使用(MU)算法:

首先统计全网中所有波长的使用率,然后优先选择使用率最高的可用波长。这种算法有利于将流量集中在少数波长上,这样可以减少网络的波长需求。

(2) 最小使用(LU)算法:

首先统计全网中的所有波长的使用率,然后选择使用率最低的可用波长。这种算法的出发点是使网络流量均匀分摊到各个波长上。

1.2.3 基于全局光通道信息的波长分配算法

此类算法在为新的连接请求分配波长时,必须考虑原有波长通道的建立情况,并根据对原有波长通道的影响来选择一个可用波长。常见的算法有:

(1) 最小乘积(MP)算法:

优先选择能使光通道的所有链路占用某波长的光纤总数乘积项最小的且编号较低的波长。当每条链路的光纤数目为1时,MP算法就蜕化为FF算法。

(2) 最轻承载(LL)算法:

将最空闲的波长分配给最繁忙的链路段。

(3) 最大总和(MS)算法:

该方法使得选择该波长后,全网的其他通道的剩余可用通道数目总和最大。

(4) 最小影响(LI)算法:

选择该波长后,对全网其他通道的影响(相关通道造成的瓶颈总和)最小。

(5) 相对容量损失(RCL)算法:

该方法类似于MS算法,也是针对提升网络其他链路的空闲容量。MS算法只是致力于将网络其他链路的绝对空闲容量最大化,而RCL算法则致力于将相对空闲容量最大化。

通过比较分析可知,波长分配子问题实际上是在给定的路径上寻找一个最优的波长分配方案,使得波长利用率最高。通常的分配方案有两种,一种就是利用上述9种算法进行波长分配;另一种是使用启发式算法(如顶点着色算法、遗传算法和紧急搜索算法等)来考虑不同路径之间波长分配的互相影响,反复修改波长分配方案,改善总的波长利用率,直到无法改善为止。

2 RWA问题优化解决方法分析研究

从目前文献中提出的RWA算法来看,主要有3类RWA问题的优化解决办法:

(1) 对于基于线性规划(LP)模型的RWA解决方案,目前已经提出了许多整数线性规划(ILP)公式或者是混合整数线性规划(MILP)公式,例如针对单跳WRON和多跳WRON。虽然LP模型可以很好地对WRON进行描述,获得网络的最优解,但是由于RWA问题是一个NP-C问题,也就是说,RWA问题不能够在多项式时间内完成问题的求解。对于这些MILP公式需要进行大量的运算,因而根据目前的计算资源,这类方法往往只适用于中小规模的WRON的优化设计。为了解决此问题,目前思路是考虑通过放松或是取消一定的约束条件使问题的公式简化,从而获得问题的近似解。

(2) 对于基于概率模型的RWA解决方案,目前进行了大量的研究。主要是研究各种网络系统设计参数,例如所用的波长数目、波长路由节点的规模、光通道的平均长度和可用的波长变换数目等,对网络的阻塞概率和网络的资源利用率的影响。这种模型主要用于动态通信模式的情况,也就是说,光通道请求是一种随机的方式。例如该过程可以描述成到达概率为泊松分布,持续时间呈指数分布。网络根据需求建立或者是拆除光通道连接,不难看出该模型类似于传统电信网络的电路交换。

(3) 基于快速有效启发式算法的RWA算法解决方案,由于WRON的RWA问题是一个NP-C问题,虽然线性规划方法能够获得准确的最优解,但是这种方法计算复杂,花费的代价太高,不适合用于大通信负荷或是大规模网络的设计。在这种情况下往往需要采用近似优化的启发式算法,这是因为启发式算法强调的是得到“满意解”,在实际问题的决策过程中,往往不去苛求最优性和探索最优解。启发式算法是在研究问题模型和优化解之间内在联系的基础上获得启发而建立的。它的优点是:计算步骤简单,易于实现;计算量小,能够在短时间内获得问题的求解;易于将定性分析和定量分析相结合。因而启发式算法具有很大的实用性,对于WRON中启发式算法的研究己经得到了广泛的重视。

3 RWA算法设计存在的问题分析

RWA是WRON设计中的一项关键技术,它不仅影响网络中波长的利用率,还会影响网络的其他特性,如业务容量、设备数目和传输时延等。从目前的研究情况来看,RWA算法设计中存在以下问题需要解决:

(1) 非精确网络状态问题:

在大规模网络中保持网络全局信息的精确性几乎是不可能的。许多因素,如时延问题、网络状态更新频率和大型网络状态聚集等都会影响网络状态信息的准确性。因此,对于非精确网络状态信息下的RWA算法进行研究也很有必要。

(2) 综合性能优化问题:

网络设计需要优化的目标很多,但现有的文献大多仅考虑其中的一个,其结果虽然在某一个网络特性上达到了最优(如阻塞率),但由于缺少各个特性之间的均衡与折中,网络的代价并没有因为RWA算法的优化而降低。因此,需要研究有利于提高网络综合性能(如业务等级划分、面向业务等)的合理的RWA算法。

(3) 服务策略问题:

选路和波长分配过程所选择的光通路一般都没有考虑物理层传输系统的约束和高层业务的要求,但网络实际运营时要引入各种策略,例如引入优先策略,一些光通路必须达到损伤要求,而另一些光通路不用达到一定的损伤要求,选择的光通路必须满足WDM传输系统通路可靠性要求等。要解决这些问题必须有相应的RWA算法。

(4) 组播技术问题:

组播路由优化旨在通过共享通信资源,实现通信资源的优化利用。组播应用的普及导致了组播网络的快速发展。组播问题的求解主要在于寻找从源节点到多个目的节点的最小生成树。从数学角度归结为Steiner树问题,它属于NP-C问题。对多波光网络的研究主要集中在RWA算法方面和业务量疏导问题。

(5) 抗毁问题:

光网络的抗毁十分重要,工作光通路和保护光通路的优化也是十分重要的,必须同时考虑这两方面才能达到网络的整体优化。一种情况是只考虑波长路由光网络本身的抗毁,可以分成保护和恢复两种机制:保护机制是为每一条工作光路准备一条备用光路,要求这两条光路不会在一根光纤断裂时同时失效,解决的算法类似于备用路由算法;恢复机制是在网络有故障造成某一条光路失效时,根据网络状态实时地重新构造一条光通路,这种方法实现较复杂,同时也需要网络有一定的剩余容量。另一种情况是考虑 IP over WDM网络的抗毁,涉及光层和IP层的多层抗毁问题。

(6) 波长变换问题:

引入波长变换可使在一条光路上分配波长时更灵活,动态建立光路时阻塞率降低。目前的波长变换研究有完全波长变换和稀疏波长变换。对于不同的波长变换配置,除了要解决RWA问题外,还要解决如何实现最佳配置的问题。由于波长变换器价格昂贵,而且技术上有限制,因此波长变换在网络中的作用仍是一个争论点,波长变换对RWA问题结果的影响以及怎样在网络中引入波长变换以达到性能最佳等问题的研究还需要进一步深入。

4 结束语

WRON被认为是实现未来高速率、大容量全光网络的有效的解决方案。它以一个波长为交换粒度,采用WDM技术和波长路由技术,通过波长进行端到端之间的路由。但由于在WRON中,网络单元的功能、物理传输性能以及实际可使用的网络资源受到限制,在网络的所有接入节点之间都建立直接的光通道连接是非常困难的。所以,为了合理进行网络优化设计,有效利用网络资源,利用启发式算法对RWA算法进行优化已经成为研究的热点。

摘要：文章通过对波长路由光网络中路由与波长分配(RWA)问题的研究,介绍了求解路由子问题和波长分配子问题的常用方法,总结了3种类型的RWA问题的优化解决方法,最后对目前RWA算法设计中存在的问题进行了分析并阐述了解决此类问题的重要性。

关键词：波分复用,波长路由光网络,路由与波长分配

参考文献

[1]王汝言,张普钊,隆克平,等.WDM网络中一种基于分层图模型的RWA算法[J].光通信技术,2007,(10):4-6.

[2]罗启彬,邱昆,张宏斌.波分复用光网络中的波长路由分配策略[J].电子学报,2001,29(12):1 628-1 631.

[3]项鹏,王荣.多域光网络中的动态RWA算法研究[J].光通信技术,2007,31(1):23-26.

[4]杨春勇,王文珍,刘德明,等.一种全光路由器的设计及性能分析研究[J].电子与信息学报,2008,30(2):455-458.

[5]Goran Z,Markovic Dusan B,Teodorovic Vladanka S.Acimovic-Raspopovic.Routing and wavelength assign-ment in all-optical networks based on the bee colonyoptimization[J].AI Communications,2007,20(4):273-285.

[6]Zhang Yu,Xu Anshi,Wu Deming.Dynamic routingand wavelength assignment in multi-granularity WDMnetworks[J].Photonic Network Communications,2007,13(3):267-276.

RWA问题 篇4

传统光网络假设物理层“光通道的信号质量都有保证,所有光纤链路具有标准的传输特性”。实际上随着传输速率的不断升级,在透明传送过程中,温度变化、色散、偏振模色散以及增益抖动等各种损伤的积累无法避免,这些都会造成光信号质量的严重劣化。为保证QoS(服务质量),基于物理层损伤感知的光网络近年来成为研究热点。基于物理层损伤感知的RWA(波长路由分配)算法是多目标和多约束的问题。特别对高优先级QoS业务能否得到优质光波长路由传送,以及IP业务的不确定性使得网络资源预留是否合理等这些都不得而知。经典的RWA算法没有考虑物理层损伤,使得理想的RWA算法用在全光网络时平均阻塞率并不理想。近年来国内外学者对基于物理损伤感知的RWA算法[1,2]已取得一些研究成果。文献[1]采用最短路径算法,以增加全网的阻塞率为代价,导致某些路径拥挤,资源分配不平衡。文献[2]在感知损伤的基础上,采用启发式算法,它是以增加算法的复杂度为代价的。本文在基于物理损伤感知网络的基础上,提出了一种新的分布式RWA算法,能很好地满足用户的QoS需求,降低全网的阻塞率和算法复杂度,减少资源的浪费。

1 分布式QoT(传输质量)RWA算法

基于QoT和QoS的RWA算法是一个多目标、多约束的问题。主要约束条件是波长连续性和各种物理损伤影响波长通道QoT的约束。多目标主要表现在高优先级QoS业务匹配优质波长路由,误码率要求和网络拥塞等目标要求。算法分为3部分:基于PIAR(物理层损伤感知的路由)、WPS(波长通道QoT优先级排序)和SWD(QoS需求分配波长)。QoT评估分布在中继段路由和波长信道中。

1.1 物理损伤评估分析模型

影响波长通道QoT的因素有CD(色度色散)、热噪声、散粒噪声、PMD(偏振模色散)、ASE(自发辐射)噪声、串扰、XPM(交叉相位调制)和FWM(四波混频)等。特别在WDM(波分复用)系统中,线性ASE噪声和非线性的XPM、FWM噪声对波长通道QoT影响较大,并且非线性的XPM噪声和FWM噪声不具有可加性。已有的文献对于感知损伤的RWA算法大都只考虑了线性损伤,而未涉及非线性损伤。本文重点考虑ASE、XPM和FWM 3种主要影响噪声。在PIAR方法中,候选光路根据信号质量来选择。考虑到不同损伤在光电探测后的影响,光路的综合信号质量通过Q因子来测量[3]:

undefined

式中,R为光电检测的响应;Ps,m为信道的峰值功率;σ0为线性噪声均方根功率;σ1为线性和非线性噪声均方根功率。且有

undefined

式中,σundefined为热噪声功率;σundefined为散粒噪声功率;σundefined为ASE光谱与信号间的差拍噪声功率;σundefined是ASE光谱间的差拍噪声功率;σundefined为XPM噪声功率;σundefined为FWM噪声功率。由于σ0≪σ1,所以Q因子可简化为

undefined

在WDM系统中,影响信号质量的主要是ASE光谱与信号之间的差拍噪声、XPM噪声和FWM噪声,因此,式(3)可简化为

undefined

假设WDM系统光接口允许的损耗是8×22 dB[4] (即该系统由8段构成,每两个EDFA(掺铒光纤放大器)之间线路的允许损耗为22 dB)。ASE、FWM和XPM噪声主要是由EDFA产生的。下面具体分析ASE、FWM和XPM噪声的功率。

(1) ASE噪声的功率

一个WDM系统总的ASE光功率表示如下:

undefined

式中,ASEP 为光路P上的ASE光功率,ASE(l)为每个中继段l产生的ASE噪声的功率。

ASE光谱与信号之间的差拍噪声功率如下[3]:

undefined

式中,Pch为信道功率。

(2) FWM噪声的功率

描述FWM的常见方法是假设所有的信道都是以CW(连续脉冲)为来源。FWM效应能够将原来各个波长信号的光功率转移到新产生的波长上,因此单个信道上总的FWM噪声光功率等于新产生的单个波长信号的光功率之和[3]:

undefined

式中,Pfwm为信道上总的FWM噪声光功率;P(m,n,p),fwm为FWM噪声产生的新波长信号的光功率。产生的新波长的频率为

undefined

(3) XPM噪声的功率

对于XPM来说,假设连接信道模型是一个CW来源。总的XPM噪声是沿传输路径产生的差分噪声的整合。

对于WDM系统,在单个波长信道上的XPM噪声由下式给出[3]:

undefined

式中,undefined为光连接信道的平均功率;Hxpm,j(ω)和PSDj(ω)分别为XPM转换函数和EDFA泵浦光信道的功率谱密度;Hopt,filter(ω)为光学滤波器传递函数。

综合上述物理信道损伤分析得知: ASE噪声的积累会降低系统接收端的信噪比,从而成为限制系统无中继传输距离的最主要因素;FWM噪声会产生新的光波长,并落入到其他信号的信道内,引起信道串扰;多信道系统中,由于折射率随输入光强变化而导致信号的相位受其他信道功率的调制,XPM噪声会引起信道间的串音。

1.2 分布式QoT RWA算法

DRWA(分布式RWA)算法分3个部分:PIAR、WPS和SWD。该算法的流程图如图1所示。

(1) PIAR方法

用PIAR方法确定每个中继段的路由,得到一组候选路由。由于光路所经过的EDFA数量一般会随着光通路跳数的增加而增加,而ASE噪声主要由光路通过的EDFA数量决定,因此,ASE噪声功率主要受限于光路的跳数,对路由影响较大。该方法重点考虑ASE噪声的约束,目标函数为undefined,尽量减少光路上的损耗,约束函数定义为

undefined

式中,P为候选路径;ASE(l)是连接l上集中的ASE光功率,阈值是由QoS的用户需求决定的。每个连接的集中ASE光功率被认为是一个连接属性,为进行路由计算而储存在边缘节点中。通过Q因子对光路的信号质量进行评估,把相关数据代入式(7)、(8)和(10),分别计算出ASE噪声功率、XPM噪声功率和FWM噪声功率,得到的数据代入式(5)中计算得到σ1,再将结果代入式(4),得到光路信号的综合评估值Q因子。判断是否有满足损伤限制的路由,如果没有满足条件的路由,即路由集为空,则造成阻塞;反之,进行WPS方法。

(2) WPS方法

用PIAR方法确定路由后,用WPS方法进行波长通道QoT优先级排序。在PIAR方法中,以Q因子对综合信号质量进行评估,主要包含两方面:中继段质量和波长信道质量。由物理损伤分析结论可知,ASE噪声是限制中继段距离的重要因素,主要影响Q因子中评估中继段质量的部分。XPM和FWM噪声会对波长信道造成串扰,主要影响Q因子中评估波长信道质量的部分。因此PIAR方法中,基于Q因子对波长通道QoT进行标识。波长通道QoT优先级排序采用WIBW (基于权重和的波长通道QoT标识方法)[4],先将这些参数进行归一化处理,然后再将其与相应的权重相乘,将这些乘积相加,得到表示波长通道QoT的参数。

(3) SWD方法

到达接入点的光路请求对应不同的上层业务具有不同的阻塞率要求,QoS需求有优先级高低之分。如果到达的请求是高优先级,则安排一个质量好并且空闲的波长与之匹配,若不存在与之匹配的空闲波长,则等待连接释放,产生新的空闲波长;如果到达的请求是低优先级,则安排相对质量差的波长与之匹配,匹配成功,连接建立。连接使用完毕后,实时进行连接释放,等待下一个连接请求。

2 仿真分析

采用图2所示的NSFNET(美国国家科学基金会网络)拓扑进行仿真,图中每条边上的数字表示光纤链路实际长度,长度的选取保证网络中任意两点之间至少有一条满足信号损伤约束的最短路径。假设所有请求均为泊松分布。

在相同环境条件下,将DRWA算法与First-Fit(首次命中)算法、LORA(字典序优化的路由算法)[5]进行了比较。 LORA是一种感知损伤的路由算法,3种算法的仿真结果如图3所示。由图3可以看出:DRWA算法在负载量为50～150时,阻塞率接近于零, LORA和First-Fit算法的阻塞率呈上升趋势;在负载量为150的轻负载时,DRWA算法的阻塞率比LORA低47%,比First-Fit算法低62.5%。在负载为250的重负载时,DRWA算法的阻塞率比LORA低27%,比First-Fit算法低31.3%。负载为50～300之间时,DRWA算法的阻塞率比LORA平均降低51.4%,比First-Fit算法平均降低63.9%。因此,相对First-Fit算法和LORA,DRWA算法在轻负载和重负载时都有效地降低了网络的阻塞率。

图4比较了3种算法的复杂度。经典的First-Fit算法没有考虑各种物理损伤,因此复杂度最低。

DRWA算法和LORA都是基于物理损伤的RWA,两者比较可以看出:在负载量为110的轻负载时,DRWA算法的复杂度比LORA降低22%。在负载为140的重负载时,DRWA算法的复杂度比LORA降低38.1%。在负载为100～160之间时,DRWA算法的复杂度比LORA平均降低29.7%。因此,相对LORA,DRWA算法在轻负载和重负载时都明显地降低了算法的复杂度,尤其在重负载时表现得更优异。

3 结束语

本文重点分析了主要的物理损伤感知,建立了3种起主要影响作用的线性和非线性物理损伤模型,将物理层QoT评估分布在中继段路由和波长信道中, 所建的DRWA算法分为PIAR、WPS和SWD 3部分,与现有算法比较,DRWA算法在阻塞率方面比基于物理损伤的LORA平均降低41.4%,比未考虑物理损伤的First-Fit算法平均降低63.9%。在复杂度方面比LORA平均降低29.7%。因此,DRWA算法在保证网络阻塞率较低的前提下,降低了算法的复杂度。

参考文献

[1]狄浩,李乐民,虞红芳,等.WDM网络中基于传输损伤的公平RWA算法[J].通信技术,2009,9(42):130-132.

[2]Eduard Escalona,Salvatore Spadaro.Advance reser-vations for service-aware GMPLS-based optical net-works[J].Computer Networks,2008,(52):1938-1950.

[3]Lin Wenhao,Hahn Timothy,Richard,et al.A dis-tributed impairment aware QoS framework for all-opti-cal networks[J].Optical Switching and Networking,2011,(8):56-67.

[4]沈若愚,朱娜,钱琴,等.WDM网感知波长传输质量的权重和波长标识[J].光通信技术,2010,(10):15-17.

RWA问题 篇5

随着光通信技术的快速发展和网络服务的急剧增加,光网络逐渐向全光网络演进。全光网是指从源节点到目的节点之间的信号传输和交换全部在光域内进行,使光网络突破了电子“瓶颈”的限制,极大地提升了传输速率,改善了网络性能。然而透明传输使光网络对于物理层攻击更加脆弱,恶意攻击信号能够在不丧失攻击能力的前提下在网络中传播, 引起网络中大范围用户信息的破坏或丢失。目前研究多集中于攻击发生之后的检测、定位和恢复机制[1,2,3],这些方法一是需要在网络中增加相应设备, 二是需要反应时间。针对上述问题,本文从对攻击的主动防御出发,首先构建了一种光网络的攻击传播模型,然后提出了一种限制物理层攻击影响范围的TS(禁忌搜索)-RWA(路由和波长分配)算法,无需在网络中额外增加设备,通过合理的路由规划,即可有效地限制攻击影响范围,提升光网络的安全性。

1物理层攻击及其传播模型

1.1物理层攻击

本文主要考虑光网络中比较容易实施且破坏性较强的大功率带间串扰攻击和光放大器增益竞争攻击,如图1所示。光信号在光纤中传播时会产生非线性效应[4],攻击者在网络中的某条光通道上注入大功率攻 击信号 (一般高于 用户信号 功率20 ~30dB)时,会在光纤中产生严重的带间串扰,造成与攻击信号相邻通道信号质量的恶化。增益竞争攻击则是攻击者利用光放大器的增益竞争现象,即攻击者注入在光放大器通带范围之内的大功率攻击信号,攻击信号将获得极大的增益,而用户信号则由于没有获得足够大的功率放大而恶化。

文献[5]的研究显示,大功率带间串扰攻击会造成同条光纤中相邻通道信号质量的严重下降(用户信号误码率接近0.5),而增益竞争会在一定程度上加重对用户信号的影响。

1.2攻击传播模型

基于上述研究和分析,本文首先构建了一种光网络攻击传播模型,如图2所示。当在光路LP1上注入大功率攻击信号时,会引发严重的带间串扰和增益竞争攻击,LP1以及和LP1具有共用链路(同条光纤)的LP2、LP3和LP4等共4条光路都会受到攻击影响。同理,在LP2上注入大功率攻击信号时,LP2、LP1两条光路会受到攻击影响。

针对构建的攻击传播模型,为进一步提出限制攻击传播的RWA算法,我们进行如下定义:

LAR(光路攻击范围):LAR指的是网络中路由与该光路路由具有共用链路的光路(包括其自身)数量。图2中LP1的LAR为4,LP2、LP3和LP4的LAR均为2,LP5的LAR为1。

MLAR(最大光路攻击范围):MLAR指的是所有LAR的最大值。图2中,LP1、LP2、LP3、LP4和LP5光路请求的MLAR为4,具有MLAR的光路为LP1。同理,LP1′、LP2、LP3、LP4和LP5光路请求的MLAR为2,具有MLAR的光路为LP1′、LP5。路由确定后,根据图着色法进行波长分配时, 这两组光路请求所需最少波长数均为2,但后者的MLAR小于前者,即通过合理的路由规划限制了攻击的影响范围。

ALAR(平均光路攻击范围):ALAR指的是某一组光路请求中所有LAR的均值。

链路负载:单条链路的负载等于路由通过该链路的光路数量,用c表示。

拥塞:网络中所有链路负载中的最大值,用C表示。

根据上述定义可知,MLAR是网络拥塞C的上限值,对于节点无波长转换能力的网络,MLAR是在波长分配时所需波长数量的上限值。

2TS-RWA算法

2.1光网络的 RWA算法

RWA是光网络的一个重要问题,RWA的目的是为光路请求寻找路由并分配波长。为了降低复杂度,一般将RWA问题分成路由分配和波长分配两个子问题来解决。常见的RWA算法有SP(最短路径)算法和基于分层图模型的FF(首次命中)算法[6]。

2.2TS算法

TS是一种全局逐步寻优算法,主要用于解决大规模组合优化问题[7]。该算法的思想是给出当前解和它的一种邻域,在邻域中确定若干候选解,以一定的目标函数对候选解进行逐步寻优搜索,当满足一定条件时,算法结束,找到最优解。

2.3限制攻击影响范围的TS-RWA算法

根据构建的攻击传播模型及其定义,本文进一步提出了一种基于TS的光网络TS-RWA算法。常用RWA算法的目标是控制路由跳数,而TS- RWA算法的目标则是在路由分配阶段寻优获得具有最小MLAR值的路由解,以达到限制攻击影响范围的目的,同时控制路由跳数。具体算法描述如下:

设图G(V,E)表示物理网络拓扑,V={v1,v2, …,vn}和E={e1,e2,…,en}分别表示节点集和链路集,每条链路上敷设一对方向相反的单向光纤,l ={LP1,LP2,…,LPm}表示网络中的一组光路请求,每条光路请求LPi(i=1,…m)由节点对(si, di)给出,si、di∈V,分别表示源节点和目的节点, 每个节点可用波长数为M,对于每条光路请求,使用K-shortest算法为其求出K条最短路径,则该组光路请求的所有可能的路由可表示为X ={x1,x2, …,xm},其中xi表示光路LPi的K- 最短路径中的其中一条路由。当网络中到达某一组光路请求后, 执行下面的算法,其步骤如下:

(1)初始化。某一组光路请求的路由初始解为其所有光路请求在图G中的最短路径,用X0表示, 计算MLAR(X0),并找出LAR为MLAR(X0)的光路集L={LPr1,LPr2,…,LPrs},禁忌表=φ,最大迭代次数=T;当小于迭代次数T时,寻求具有最小MLAR的最优路由解。

(2)分别为L中各光路从其K- 最短路径中重新任选一条路由,得到一组新的路由解,计算各个解的MLAR,具有最小MLAR的解成为当前解Xc,并将MLAR(Xc) 和MLAR(X0) 进行比较: 若MLAR(Xc)< MLAR(X0),并且Xc不在禁忌表中,转入步骤(3);否则,转入步骤(4)。

(3)Xc成为当前最优解,同时将该解放入禁忌表。

(4)随机选取一部分未被禁忌的光路请求为其重选路由,计算相应的MLAR,具有最小MLAR的成为当前解,相应的LAR等于MLAR的光路组成光路集L,T=T+1,返回步骤(2),开始进入下次迭代搜索。

(5)到达最大迭代次数T时,算法结束,获得具有最小MLAR的路由解。

在获得最优路由解之后,由前述定义和分析可知,TS-RWA算法通过减小MLAR值还能够限制波长分配时所需波长数量的上限值,故波长分配解的获取按照具有较小复杂度的文献[8]的方法进行, 不再细述。至此,我们为该组光路请求找到路由,并分配了波长。

3仿真分析

为验证本文提出的TS-RWA算法的有效性,分别采用图3和图4所示的11节点、26条链路的Pan-European网络(泛欧网络)拓扑和14节点、21链路的NSFNET(美国国家科学基金网络)拓扑进行仿真。

分别为两个网络拓扑随机生成20个业务矩阵, 每个业务矩阵决定了一组光路请求,包括光路请求的数量和每个光路请求的源、目的节点。表1和表2所示分别为以两种网络拓扑为基础生成的业务矩阵所确定的光路请求数量。两个网络拓扑中,每个节点可用波长数为10,K为3,迭代次数为1000, 禁忌表长度为10。

使用本文提出的TS算法、SP算法和FF算法分别为两种网络拓扑的20组光路请求进行路由分配,并就每组光路请求路由的MLAR和ALAR进行对比,仿真结果如图5和图6所示。从仿真结果可以看出:在两种网络拓扑下,相比于SP、FF算法, TS算法为20组光路请求获得的路由解均具有最小的MLAR和ALAR,即该算法可有效地限制物理层攻击的影响范围。从图5(a)可以看出,相比于SP、FF算法,TS算法的MLAR分别平均减小了约45%和40%。从图6(a)可以看出,相比于SP、FF算法,TS算法的MLAR分别平均减小了约21%和32%。从图5(b)和图6(b)可以得出,TS算法的ALAR也低于SP算法和FF算法。同时,MLAR是拥塞C的最大值,MLAR值的降低意味着减少了网络中 因某段链 路被切断 所破坏的 光路数量; MLAR也是在进行波长分配算法时所需波长数量的上限,MLAR值的降低减少了波长分配时所需的波长资源;TS算法限制了攻击影响范围,当网络异常时,我们只需检测更少的可能受影响的光路,这样就可以加快攻击检测和定位算法的运行,减少攻击对网络的破坏时间。

4结束语

光网络的物理层攻击防护问题具有重要的研究意义。本文构建了光网路物理层攻击传播模型,进而提出了一 种限制物 理层攻击 影响范围 的TS- RWA算法,并对该算法的性能进行了仿真分析。结果表明,相比于SP和FF算法,在Pan-European网络拓扑下,本文算法的MLAR平均减小了约45% 和40%;在NSFNET拓扑下,MLAR平均减小了约21%和32%。本文算法通过降低MLAR有效地限制了物理层攻击影响范围,并且不需要增加额外网络设备,减少了所要使用的波长资源,提高了网络的安全性。

摘要：攻击防护是光网络的一个重要问题。文章构建了光网络大功率带间串扰攻击和光放大器增益竞争攻击的传播模型,提出了一种限制物理层攻击影响范围的路由和波长分配算法。在路由分配阶段,该算法把具有较小最大光路攻击范围的路由分配给光路请求,以降低攻击影响范围。仿真结果表明,与常用算法相比,该算法能够有效限制物理层攻击影响范围,提升光网络的安全性。

RWA问题 篇6

关键词：蚁群算法,信息素,阻塞率,路由波长分配,电力通信网

0 引言

WDM(波分复用)技术以不同的波长作为传输信道来传递信息,因此波长资源是WDM光网络中最重要的资源[1,2]。由于RWA(路由波长分配)问题本身是NP-C问题,网络规模越大,算法的复杂度越高。在工程上,一般将RWA问题分为路由子问题和波长子问题串行解决,由于这类方法一般采用最短路径寻路,采用首次命中方式分配波长,可能出现多条光通道占用同一链路,导致网络需要的波长数较多,在网络波长资源有限的情况下阻塞率较高。因此,有必要研究新的启发式算法以期得到更优化的规划方案。

本文基于ACO(蚁群算法)的启发式思想,结合分层图方法,提出一种优化算法SS-ACO(服务选择ACO),增加了业务选择机制,引入业务信息素,改进了蚂蚁选路和信息素更新环节,能有效提高算法的寻优能力,降低网络业务阻塞率。然后,结合网格网络和某省电力骨干通信网络进行仿真实现,将算法结果与现有算法进行了比较。

1 SS-ACO数学模型

给定网络G=(V,E),其中,V={v1,…,v|V|}为网络节点集合,E={e1,…,e|E|}为节点间的光纤链路集合。每条光纤能够使用|Λ|个不同波长进行并行无干扰传输,Λ={λ1,…,λ|Λ|}。对于任一节点v,有邻节点预备集N{n1,…},其每一个元素与v直接相邻。网络链路e上分布的信息素τqe表示q的路由包含链路e的可能性。

设需求空间Q={q1,…,q|Q|},其中,qi=(si,di)(si、di∈V,si≠di)表示节点si到di的连接请求。对于同一源-宿节点对,可能有多个连接请求,这种情况对应于实际网络中带宽需求较大的业务。对于任一请求q,有相应信息素τq和启发式信息ηq,其中,τq表示最佳方案能应答q的可能性,ηq与q的最短路径长度成反比。

A={a1,…,a|A|}为解决方案,其中ai=(rj,λk),包括为请求q=(s,d)∈Q分配的波长λk(λk∈Λ)和路由,其中,。

此外,本文遵循以下原则:(1)对于光通路(sn→dn),在所分配路由包含的每条链路上都使用相同波长λk传递信息。这是由于在中继节点变换波长需要实现光/电/光转换,成本过高。(2)对于经过同一链路的不同光通道,必须采用不同波长承载信息。即对于e∈E,λ∈Λ,不存在e∈ri,e∈rj,且ai=(ri,λ),aj=(rj,λ)∈A。

本文中RWA的优化目标是使解决方案A能满足尽量多的业务需求。

2 SS-ACO描述

基于ACO框架,利用蚂蚁群体觅食过程中的正反馈机制,派出多只蚂蚁独立探索方案空间,经过多次迭代得到最佳方案。本文所提SS-ACO的框架如图1所示。

SS-ACO的主要步骤如下:

步骤1:初始化。初始化是设置ACO计算参数、方案空间中初始信息素和启发式信息的重要过程,关系到算法最终解决方案性能的优劣。ACO计算参数包括阻塞迭代次数Niter、蚂蚁数Nants、信息素蒸发速率ρ和信息素边界比γ等。

步骤2:派出新蚂蚁ai搜索方案空间。

步骤3:选择可用波长,其原则是使用一个波长响应尽可能多的请求。即将波长资源进行编号后,按一定顺序依次选择,判断当前波长不能再满足任一业务时,再启用新波长。

步骤4:基于选定的波长图,蚂蚁ai按照业务选择机制从需求空间选取请求q。

步骤5:为连接请求q寻路,按照蚁群寻路规则在步骤3选定的波长图上寻找最优路径。

步骤6:判断网络波长资源是否用尽:否,则转至步骤3;是,则得到蚂蚁ai的解决方案Ai。

步骤7:判断是否所有蚂蚁都找到解决方案:否,则转至步骤2;是,则从蚁群方案中选出本次迭代所得最佳迭代方案Aib。

步骤8:当|Aib|>|Abs|时,令Abs←Aib,其中Abs为准最佳方案。按照信息素更新规则更新全局信息素和局部信息素。

步骤9:判断是否满足算法终止条件,即准最佳方案Abs的性能在之后Niter次迭代不再提高。若不满足,则转至步骤2。

为避免算法陷入局部最优而使最终方案质量不够高,重启算法Nreset次。

2.1 业务选择机制

业务选择机制,即如何从需求集合中选取要响应的请求。首先,计算每个业务在当前波长图上的最短路由长度l,移除不可应答请求,为可应答请求设置启发式信息ηq,其与l成反比,即

然后,以概率pq从可响应请求中随机选取一个请求。pq定义为

式中,α、β分别为信息素和启发式信息的计算权重;γ为0~1的实数;Ni为当前的迭代次数。在算法运行初期,pq几乎与τq和ηq无关,随机选取请求进行应答,即蚂蚁能更自由地探索方案空间,利于获得更优质的解决方案。随着迭代次数的增加,pq受信息素和启发式信息的影响增大,即选择其他蚂蚁选过的或路由较短的请求的可能性更大,利于方案收敛。

2.2 蚂蚁寻路规则

当为请求q=(s,d)选定路由时,由源节点s起,从当前节点的动态候选点集N′中迭代地选择下一跳,直到到达目的节点d。一般地,对于节点u,其邻节点预备集是与u相邻且能到达d的节点集合。对于N′中的任一点v,计算其到d的最短路径长度lr,设置链路(u,v)上的启发式信息ηv,u与最短路径长度lr成反比。此处,当候选点就是目的节点时,lr为0,由于lr作分母,故将lr作加1处理,即该式为

以概率pr来选取候选节点作为下一跳,直至到达宿节点d。pr定义为

式中,τq(u,v)为链路(u,v)的信息素浓度。在算法运行初期,Ni/Niter较小,蚂蚁以近乎等概率选取下一跳节点,利于蚂蚁探索方案空间。随着算法的运行,蚂蚁会优先选靠近目的节点的节点及频繁访问的边缘附近的节点,利于方案收敛。

2.3 信息素更新

信息素蒸发是整个启发式算法的关键,它保证了随机得到的坏方案不会对之后的迭代造成持续影响。当蚁群方案建立完成后,令全局信息素以固定速率ρ蒸发:

在得到迭代准最佳方案Aib和准最佳方案Abs后,随机选取Aib或Abs为A。选择Aib的概率越大,越有利于探索方案空间,相反则更利于算法收敛。令:

从而使所得方案更好,该方案中各元素的信息素浓度越高,越有利于方案收敛。最后,按照MAX-MIN(最大-最小)蚂蚁系统的要求将信息素浓度限制在[τmin,τmax]范围内。

3 算法仿真分析

3.1 网格网络仿真实现

以4×4的网格网络为仿真网络,需求空间由计算机随机生成,将本文的SS-ACO与一般ACO(Tra-ACO)和SPMU(最短路径最多使用)算法方案进行比较,如图2所示。在一般ACO中,蚂蚁以相同概率从需求空间随机选取请求,蚂蚁寻路时的转移概率仅与网络信息素分布和启发式信息相关,当一只蚂蚁建立了蚂蚁方案后,便更新局部信息素。

由仿真结果可知:当需求空间大小一定时,随着网络波长数的增加,解决方案能响应更多的连接请求;当网络波长数一定时,需求空间越大,解决方案能支持的业务需求越多。且当波长资源一定,需求空间越大,SS-ACO相对于其他两种算法的优势越明显,这是由于SS-ACO引入了业务选择机制,在算法运行后期,会先应答路径较短的业务。如果先为路径较长的请求分配了网络资源,可能导致拒绝更多与其包含重复链路的请求。由于信息素更新是在建立蚁群方案之后,各蚂蚁探索方案空间不受其他蚂蚁信息素的影响,因此蚁群探索方案的过程是并行的,可避免过早进入局部最优。

3.2 实际网络仿真实现

以某省电力通信网省干OTN(光传输网)主平面为例,其拓扑如图3所示。全网采用40×10Gbit/s带宽,网络结构分为骨干层和接入层。骨干层节点为省公司和变电站,接入层节点为地市公司,共配置节点设备30套,光纤链路47条。

由于电力通信网是电网生产、管理及营销的专用通信网,该网络主要承载的业务包括调度数据网业务、数据通信网业务和省干A网。根据《电力通信网规划设计技术导则》、《“十三五”期间各类变电站和办公场所典型带宽预测模型》(信通计划[2015]82)的方法与要求[3,4,5],结合该省业务网络特点,预测该网络的主要业务带宽需求如表1所示。

为评价网络的业务发展适应性,引入LLR(链路负载率)指标,其定义如下:LLR=(Boccupy/B)×100%,式中,Boccupy为被占用的波长;B为链路总带宽。LLR是评价链路负载是否过重的指标,其中,空载链路、轻载链路、较重载链路和重载链路分别对应LLR=0、0<LLR≤30%、30<LLR≤60%和LLR>60%[6]。重载链路数比重越大,网络适应性越差。

基于上述网络与需求空间,考虑业务发展需求和阶段性部署特点,我们将各节点出口带宽以逐年递增的方式进行测算,即需求空间大小分别增长为140、280、420、560、840和1 120。下面利用SS-ACO优化算法对某省干OTN主平面的业务通道层进行模拟仿真,算法结果对比如图4所示。

比较算法方案可知,对于特定网络和可预测的需求空间,随着需求空间的增长,SS-ACO优化算法的解决方案一直优于其他两种算法。根据SS-ACO仿真结果,目前全网有70条业务需求都可应答,解决方案仅使用了20个波长。全网共有47×40条链路,方案链路利用率为12.3%。可见,对于目前的网络业务需求,该网络资源较为充裕。但是由于网络资源一定,随着业务需求的逐步增长,必定会有业务无法得到响应,网络阻塞率变高。

另外,考虑网络容灾、可靠性等因素,计算了当需求空间分别为140和280时,网络中负载较重的链路的分布情况,如图5所示。

图中,虚线链路表示重载链路(LLR>60%),加粗链路为较重载链路(30<LLR≤60%),其他为轻载链路(0<LLR≤30%)。可见,重载链路多为单根光缆链路,而对于链路(FX变-ZJ公司),虽然承载的业务数最多,但由于其采用双光缆配置,降低了负载压力。这是由于,在业务层各地市公司分别到省公司、备调公司的业务均呈汇聚型,而传输层主要呈现环网结构,因此网络负载不均衡。对于重载链路,其波长占用率较高,随着网络需求的增加,这些链路将成为“瓶颈”链路,因此应对该链路及时升级,对该链路进行双光缆配置,或在相关站点(如省公司1和SG变)间铺设直通光缆,并对中间路由器制定负载均衡策略,以缓解网络流量压力局部过大,使该网络由环网结构向网状网结构发展与演进。

4 结束语

本文基于ACO框架,提出了一种有业务选择机制的RWA优化算法,尤其在需求空间较大的情景中,能够有效提高网络的业务承载能力。通过改进蚂蚁转移概率,使蚂蚁在算法初期能自由地探索方案空间,算法后期又利于方案收敛。此外,本文的算法能延伸为解决多并发业务的DRWA(动态RWA)问题。结合网格网络和某省电力通信省干OTN进行了算法的仿真实现,并评价了该省干网络对承载业务发展的适应性。

参考文献

[1]刘爱波,陆月明,纪越峰.智能光网络路由及其关键技术分析[J].光网络,2004,(8):29-31.

[2]孙海金,朱娜,周乃富.基于蚁群系统的分布式RWA算法研究[J].光通信研究,2005,(2):30-34.

[3]周静,熊素琴,苏斌,等.一种电力通信网络运行质量量化评估方法及应用[J].电网技术,2012,36(9):168-172.

[4]刘贵荣,周静,赵子岩,等.电力通信网SDH环容量均衡优化算法研究[J].电信科学,2010,(12):140-144.

[5]周静,吕天光,陈希,等.省级电力调度数据网带宽分析与容量规划研究[J].电网技术,2012,36(5):173-177.