波长路由光网络（精选4篇）
波长路由光网络 篇1
近年来, 技术改革逐渐深入, 进而使得我国的发展正朝着经济全球化与社会信息化方向快速发展。以虚拟网络为代表的数据业务量逐渐增多, 如:IP。另外, 新业务的大量出现, 从而使人们对宽带有了更大的需求。然而, 由于波长路由网络具有较强灵活性、透明性等, 发展成为当前非常重要的WDM层组网技术之一。其中, 波长路由光网络主要包含两种类型, 即静态与动态。但是, 在应用此技术时, 关键问题极为路由和波长分配问题。这样一来, 可以对所出现的故障进行有效管理, 为用户提供高质量的服务。
1 波长路由光网络概述和存在的问题分析
1.1 关于波长路由光网络概述
我们已知道, 因为器件技术逐渐朝着更高方向发展, 如, 在光网络中, 宽带复用技术应用十分广泛。事实上, 宽带复用技术主要划分为三大类, 即时分复用、波分复用以及码分复用。在把上述技术应用到光网络中时, 可使网络性能大大提高。其中, 光网络节点凭借波长信息决定路由功能, 严格按照端到端的逻辑来选择输出的, 并不是把信息发送给所有输出端, 这样以来, 能够节省网络终端使用量。
在将复用技术应用到光网络中后, 其波长路由光网络的实用价值将更大。此网络是由波长路由节点以及诸多点到点光线连接所构成的。
1.2 波长路由光网络具有的优势
和传统电信网络相比较来说, 波长路由光网络可提供更大通信容量。此外, 此网络的透明性、可管理性以及灵活性等都较强。因此, 我们可以将波长路由光网络所具有的优势大致总结为以下几点:
事实上, 波长路由网借助波长选择器对路由进行选择的。换言之, 结合波长信号来选择路由。另外, 传输码率、数据格式以及调制方式等不仅有较强的透明性, 而且又能够为用户提供多种高质量的协议业务, 对用户端到端业务不受任何限制。这种透明性是指网络所有信息由源地址在到达目的地址过程时, 不需要进行光-电-光间的转换。这主要是由于在波长路由光网络当中, 其所有的信号传输都必须在光域中完成, 而传输速率与格式都只受接收端与发射端限制。由此看来, 波长路由光网络对信号传输来说是极其透明的。
现如今, 波长路由网络既能够和现有通信网络相互兼容, 又能提供数字网等一些综合性业务与网络升级功能等。
另外, 波长路由网络也具有一定的可扩展性。而在增加新网络节点后, 既不会影响到网络结构以及设备运行, 又能给大大降低网络运行的成本。同时, 此网络通过增加波长来达到扩容的目的。
一般来说, 波长路由网络结构要比传统网络结构要简单的多, 并且端和端之间的通信都是借助光通道最终实现的, 同时, 在此路途当中, 并没有增设变换与存储设备。所以, 能够减轻网络成本运行成本, 同时又能大大提高信号传输质量。除此之外, 在波长路由网络中, 大多数光器件都为无源类型的, 这样一来, 网络的可靠性与维护性也非常高。
1.3 波长路由网中路由存在的问题
在波长路由网络中, 其路由方式大多数都是和传统线路交换网络相类似的。从整体上分析, 路由计算方法主要有两大类, 即静态算法与自适应算法。其中, 静态路由算法中路由分配并不需要对网络状态予以考虑。然而, 在静态路由中, 典型的两个例子即为固定路由和替换路由。但是, 在自适应路由中, 由网络运行状态决定连接请求的路由选择。因此, 我们对路由方式进行总结:
1.3.1 固定路由
在固定路由中, 源节点与目的节点只有唯一一条固定路由。在发出连接请求送达后, 在动态波长路由网络中, 若在这个固定的路由上缺少可用资源, 那么此连接请求便会阻塞。此问题的出现主要是由于可选用的路由过少, 导致阻塞率大大升高。其中, 固定路由方式最为常见的方式即为固定短径路由, 并且常应用到静态波长路由网络当中。
1.3.2 替代路由
在将固定路由改进之后便可成为替代路由。其中, 替代路由可允许一个源-目节点对有多个使用路由, 同时按照一定顺序予以配排列。当解决一些动态问题时, 某个连接请求到达后, 按次序查找路由中是否有一条可用资源符合此请求的要求, 若存在, 便会自动选择此路由;若不存在, 那么此项请求便会被阻塞。和固定路由来说, 此路由存在很多阻塞率指标。然而, 怎样选择能够相互替代路由是值得我们深入探究的。
1.3.3 自适应路由
自适应路由的路由在选择时, 所必须严格遵循的原则为结合当时网络运行状态选择。换言之, 结合网络中链路可用资源状态来最终予以决定的。其中, 最小阻塞路由便为自适应路由的一个典型例子。例如:在最小阻塞路由方式选择过程中, 由备选路由中选择可用路由的主要原则为:要选择占用网络资源偏少的路由。但是, 若处在动态播出路由网络当中, 若为自适应路由, 其阻塞率指标要比上述两种方式好得多。然而, 此种路由方式又对算法实时性提出较高的要求, 所以, 在选择自适应路由方式前, 还需要对路由效率与性能予以全面考虑。
1.4 波长路由网中波长分配问题
在波长路由光网络中, 波长分配问题是一非常重要的问题。其中, 在静态波长路由光网络当中, 常和路由问题紧密结合在一起, 从而获得最优解。但是, 在动态波长路由光网络当中, 其波长的分配策略对于阻塞率来说具有重大影响。常用的波长分配策略:
1.4.1 随机分配法
也就是说从可用波长中随机抽取一波长分配指定给光通道。可以说, 此种分配方法十分简单, 而不需要对网络状态信息全面了解, 但此种方法会有较高的阻塞率。
1.4.2 首次命中法
按照此方案, 在不同波长中都做好标记。这样, 在选择波长过程中, 由小到大进行排序, 从中选择最小波长。而在应用首次命中法时, 是极易实现的, 同时, 阻塞指标远比随机分配法小得多。
1.4.3 最小使用法
在应用最小使用法时, 波长选择方式是将网络中使用次数最少的波长。如果此波长不可用, 再选择第二使用次数最少的波长, 以此类推下去。这可以看做是改进首次命中法的一种方式。而此种波长排号不固定, 是结合网络当时情况而定的。这种方案的阻塞率要低于首次命中法的阻塞率, 但在实现过程中会存在一些麻烦。若要弄懂当前网络情况, 必须借助网络状态传输协议进行测定。然而, 这又和网络管理方式为集中式或是分布式有着紧密关联。
1.4.4 波长保留法
在这个方案里, 常常将波长予以保留, 而在一些特定业务当中, 才允许使用。但是, 它对降低网络阻塞率并没有做出任何贡献。然而, 却可以为某些特定业务提供高质量的服务。所以, 此种方法在高质量要求场合应用价值是非常高的。
1.5 故障管理的问题
网络当中的故障管理机制通常有两种。一种叫做保护机制, 就是备用资源已经被预先计算好了, 另一种叫做恢复机制, 就是未事先准备好备用资源, 是由中断后的连接动态来寻找。总之, 动态恢复机制对网络资源利用效率是非常高的, 并不需要预留出一定的闲置资源。然而, 保护机制恢复速度是极快的, 同时又能确保业务可以快速予以恢复。
一般保护主要包含两种:其一为路径保护;其二为链路保护。其中, 对于路径保护来说, 当存在一定故障时, 业务便快速被转移给其它保护路径中。但是, 在此处, 工作路径和保护路径是两条完全分离的链路, 这样一来, 才能够保证遇到一个故障只对一个链路产生影响, 而某个单个故障却不可以终止此业务。然而, 在链路保护中, 业务必须在失效光纤链路中重找新的路由。除此之外, 又有一种称之为是子路径保护方式, 在这种模式下, 工作路径划分为多个小段, 进而再对每一段路径予以保护。子路径保护能提供更快的故障恢复速度和更高的资源利用率。进一步深入研究波长路由网络中使用的保护机制, 将它与IP层中的恢复机制结合起来, 建立一个合适的协议, 为广大用户提供更高质量的服务。另外, 研究人员还需要对波长路由网络中Qo S问题进行深入的探究和分析, 建立起相应的协议, 为用户提供出等级区分的服务。
2 结束语
我国未来的电信网络的结构将会是以WDM传送网络构成的核心的网终, 由SDH、WDM环等所构成的城域网, 再通过多元化的宽带业务的接入向广大用户延伸。从网络构架上来说, IP over WDM将会成为网络发展的趋势。这当中WDM网最主要的形式是波长路由光网络, 因此, 波长路由光网络的发展前景非常广阔。
参考文献
[1]单玉洁, 王辉.静态环型波长路由光网络中RWA问题的研究[J].通信技术, 2008 (12) .
[2]陈明, 张峰, 秦曦.啁啾光纤光栅波长路由光网络的组播功能实现[J].光电子.激光, 2008 (3) .
[3]张曙光, 叶运峰, 李晓东.波长路由光网络中RWA算法的设计分析[J].光通信研究, 2009 (5) .
[4]项鹏, 王荣.WDM-TDM光网络中的动态波长路由与时隙分配算法研究[J].电子与信息学报, 2009 (3) .
波长路由光网络 篇2
光传送网(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.
智能光网络路由选择技术及其算法 篇3
智能光网络是当今传送网发展的趋势，是一种能够支持多种类型业务、具有动态连接能力，并可以根据实际工作的需求，能够对带宽进行实时分配的光网络，其主要代表是自动交换光网络(ASON)。路由技术是智能光网络标准化工作的难点和重点，作为智能光网络控制平面的一项重要的核心技术。路由技术也是国际标准化组织当前的主要研究对象。
1 智能光网络路由的基本特点
与传统的IP路由相比，智能光网络的路由有如下特点：
1) IP路由包括控制和数据平面的功能。控制平面的功能又分为两部分：扩散拓扑信息和路由拓扑信息计算转发表。数据平面的功能是利用转发表来转发IP数据包。在转发IP数据包之前，连接并没有建立，数据包是从源到宿一跳一跳地转发的。和其他电路交换网络一样，光网络中的数据平面并不参与连接的路由。在这些网络中，端到端连接是根据网络拓扑和资源信息来建立的。建立之后，数据就可以在连接上进行传输，路由就不需要再进行计算了。
2)在IP网络中，路由协议和数据平面的转发过程关系密切。一旦出现故障，就必然会有用户受到影响。而在光网络中，由于控制平面和数据平面是分离的，路由协议出现故障后，并不会影响到已经建立的连接。
3)在开始传输数据之前，必须先建立连接和预留资源。光网络中的路由需要知道网络中不同资源的可用性情况，目前的域内IP路由协议不处理资源可用性信息。而最近的为IP流量工程做了扩展的路由协议则涉及了这个内容。为了路由光网络中的连接，需要经过加强的路由协议来处理资源的可用性信息。
4) IP路由是逐跳计算的，而在光网络中，路由是由源节点计算的。也就是说，在IP路由中，路径上的各个节点会独立地选择下一跳来转发数据包。因此，所有节点都必须知道整个网络的拓扑，并且保持路由算法一致，这样才能计算得到正确的路由。而在光网络中，路由计算是由源节点完成的，只要源节点拥有正确的网络拓扑信息就可以了，而不需要所有节点都拥有网络拓扑信息以及进行路由计算。
5)对于保护和恢复的需求。在IP网络中，业务一般在最短路径上进行转发。当故障发生时，路由机制会选择其他路由，使得数据包可以绕过故障点，也就是说，网络对故障的处理多少会有一点延迟。然而，在光网络中，一个基本特征就是大量使用预先计算好的，同时也是常常预先指配好的设备分离备份路径来实现连接的保护。
6)邻居发现过程是许多域内IP路由协议的基本功能。光网络中的邻居发现则是由其他自动发现机制来实现的。在光网络中，邻居发现过程除了基本的邻居发现外，还包括链路相关属性的发现。
2 智能光网络的路由选择技术
2.1 基于约束（Constrain）的路由
基于约束的选路用于计算受到多个约束条件限制的路由，它从Qo S路由发展而来，但又不同于Qo S路由。在基于约束的路由选择算法中，寻找一条同时满足两个或两个以上度量约束的路径，是一个NP完全问题。该问题目前在数学上还没有统一确定的解决方法，这也意味着还没有标准的基于约束的路由算法。
2.2 QoS路由
2.2.1 Qo S路由的基本概念
Qo S的概念用来刻画服务提供者与用户之间用数量或质量来定义的性能约定。一次连接的服务质量由一系列约束条件给出，如带宽约束、时延约束、抖动约束等。Qo S路由的基本任务是为一次连接寻找一条有足够资源，能够满足Qo S要求的可行路径。Qo S路由不同于尽力而为的路由，因为Qo S路由通常是面向连接，有资源预留功能，并且能够提供质量保证的服务;而后者有可能是面向连接的，也可能是无连接的。
2.2.2 Qo S路由基本问题
Qo S路由问题就是找到一条满足一个或多个Qo S条件的路径。网络服务被要求提供的Qo S，对于给定路径相对于其成分链路而言一般表现如下3类性质： (1) 可加性：总Qo S等于构成这条路径的所有链路Qo S值之和(如跳数、时延等); (2) 可乘性：总Qo S等于构成这条路径的所有链路Qo S值之积(如误差率、丢包率等); (3) 最小最大性：总Qo S等于构成这条路径的所有链路Qo S值中的最小者(如费用等)，或者总Qo S等于构成这条路径的所有链路Qo S值中的最大者(如流量、带宽等)。
由于要同时满足这些性质各异的Qo S是比较复杂的，因此，对于最小性Qo S，进行路径选择之前不满足Qo S的链路将不作为路径选择对象;对于乘法性Qo S，可以将各链路的Qo S值进行对数变化，转换为加法性Qo S，保证在进行路径选择时只包括加法性Qo S，以便于处理。
2.3 GMPLS路由技术
MPLS对传统的路由协议进行了扩展用来支持流量工程(TE)。GMPLS在此基础上又对其进行了扩展和加强，从而支持链路状态信息的传送。GMPLS路由协议主要用于I-NNI接口的路由，即ASON域内路由。GMPLS对路由协议的扩展主要包括如下方面。 (1) 对未编号链路的支持; (2) 链路保护类型(LPT); (3) 共享风险链路组信息(SRLG)。如果一组链路共享某一种资源，而这种资源的失效可能会影响共享到所有这些链路，则称这一组链路为“共享风险链路组”; (4) 接口交换能力描述符。GMPLS定义了以下的接口交换能力：PSC(分组交换)、L2SC (L2交换)、TDM(时分交换)、LSC(波长交换)、FSC(光纤交换); (5) 带宽编码。
3 智能光网络的路由算法描述
3.1 路由算法的设计目标
路由算法的设计目标通常包括以下内容： (1) 最优化：路由算法选择最佳路径位置的能力; (2) 简单性：路由算法应该被设计成尽可能地简单，即必须以最少的开销和使用费用获得高效的功能; (3) 顽健性：路由算法必须是健壮的，在异常的或者无法预料的情况下(如硬件失败，高负载条件和不正确的安装和使用等)，要求算法仍能正确运行; (4) 快速收敛性：路由算法必须在短时间内收敛; (5) 灵活性：路由算法应迅速准确地适应各种各样的网络状况。
3.2 受限最短路径优先（CSPF）算法
在通信网络中，使用Dijkstra和Bellman-Ford算法计算最短路径是很有效的，但如果要求满足不同的Qo S条件，将约束引入优化问题时，算法会变得十分复杂。约束最短路径优先(Constrained SPF)算法属于启发式算法，它是一种改进的最短路径约束算法，是目前最适应于智能光网络的路由算法，在网络中主要用来完成流量工程和快速的重路由。
对于CSPF算法有几个输入变量：首先是配置的流量隧道特性(带宽、资源类所属关系、优先级、恢复性等);其次是与这些特性相关的资源状况;第三是网络的拓扑信息。其中网络的资源和拓扑信息可以通过IGP来获得。
CSPF的主要计算步骤如下： (1) CSPF会排除掉那些链路信息不全的链路，然后进行链路所属的资源类的检查，检查之后，如果发现有无效的资源所属关系的链路，就把这些链路排除掉; (2) 根据删减后的拓扑计算最短距离的路径。
3.3 用于CSPF计算的约束条件
通常约束条件分为两类：链路约束和路径约束。
1)链路约束。链路约束是指一条路径上链路的使用限制，即光链路的属性特征。单条成员(TE)链路可以包含如下属性(约束条件)： (1) 最大带宽：该参数描述了链路的容量; (2) 未预留带宽：该参数描述了链路上还没有被预留的带宽; (3) 最大、最小连接带宽：这两个参数决定了链路中可以分配给某条连接的最大和最小带宽。可分配的最大带宽小于链路上的未预留带宽;可分配的最小带宽取决于交换节点所支持的交叉粒度; (4) 链路保护类型：指链路的保护能力; (5) SRLG：一串无序的数字，用于表示和链路相关的SRLG标识符; (6) 接口交叉能力：包括交叉能力和交换能力细节信息。
2)路径约束。路径约束是指在选定路径上性能度量标准值的加性或乘性组合的界限。 (1) 路径跳数限制：到达目的地路径的最大跳数; (2) 松散显示路由：确定给出路径必须经过的一些中间链路或中间节点; (3) 保护恢复机制：当传输链路发生故障时采取哪种备份路径恢复链路。
4 结语
智能光网络中的路由技术是当前的研究热点和重点。由于目前还没有相关的行业标准，因此，在路径选择算法，约束条件选择上具有相当的灵活性，随着光传输技术的发展，需要考虑的约束条件也会随之而发生变化，根据不同的网络结构和性能需求来选择不同的参数，从而更好地适应智能光网络。
参考文献
[1]毛谦.传输与交换在光层的融合——自动交换光网络[C].//全国第十次光纤通信暨第十一届集成光学学术会议 (OF-CIO’2001) 论文集.2001.
[2]宋涛.新一代网络体系——智能光网络[J].光通信技术, 2004 (5) .
波长路由光网络 篇4
自动交换光网络(Automatic Switched Optical Network,ASON)是传送网发展的趋势,而路由技术是整个ASON的核心技术之一,也是ASON标准化工作的重点和难点。好的路由和波长分配算法不仅可以提高网络资源的利用率、降低网络建设和运营维护成本,还可以降低网络管理的难度、保证不同业务的通信质量。波分复用光网络中传统静态路由算法阻塞率较高,本文在Dijkstra算法的基础上,提出了基于流量均衡的静态路由算法来提高网络资源的利用率。
1 路由和波长分配算法简介
路由和波长分配(Routing and Wavelength Assignment,RWA)问题是在一组全光连接请求条件下,寻找源节点到目的节点的路由和给这些路由分配波长的问题[1]。研究RWA问题的目的是尽可能减少所需要的波长数和降低光路连接请求的阻塞率。
针对不同的业务和连接请求方式,RWA问题可分为动态RWA问题和静态RWA问题[2]。
波分复用(Wavelength Division Multiplexing,WDM)全光网中RWA问题是一个NP[3]完备问题,因此一般采用启发式算法进行求解。为了简化问题的研究,通常把路由和波长分配问题分解成两个子问题[2],分别加以研究解决。路由子问题:为业务选择一条路由,也就是选择业务经过的光节点和光纤链路;波长分配子问题:在所选定的路由经过的光纤链路上为业务分配波长。
静态RWA路由算法,一般文献中都采用最短路由算法,也有k最短路由算法以及重路由算法;对于波长分配,则有随机波长分配法、长路优先算法、首次命中(First-Fit)算法等。
动态RWA路由算法最常用的是Dijkstra算法[4],波长分配算法与静态RWA算法中类似,也有随机分配、首次命中等[5,6]。
本文基于Dijkstra算法的静态路由算法,即网络拓扑和业务需求矩阵给定的条件下,通过调用Dijkstra算法寻找网络中的最短路径,然后对比流量均衡前后网络性能的变化。
2 基于流量均衡路由算法的实现
2.1 静态路由算法实现
算法采用多次循环的思想,对于一个随机数生成需求矩阵,每次循环遍历所有n×n个节点对,每个节点对间只为一个需求调用Dijkstra算法分配一条路由,不能找到最短路径则阻塞该节点其他需求并标示该节点处理完毕,找到最短路径则更新路径。如此多次循环,直到所有节点对间的所有需求处理完。每次的循环流程图如图1所示。
2.2 基于流量均衡的路由算法实现
流量均衡的思想是通过动态改变网络链路的权重,均衡流量在网络上的分布达到优化网络的目的。均衡前:判断Dijkstra算法找到的最短路径中的各链路,流量不大于最大流量的链路,邻接矩阵的权值不变;均衡后,把Dijkstra算法找到的最短路径上各链路,流量不大于最大流量的链路,邻接矩阵的权重均增大,即该链路上的“费用”增多,下次Dijkstra算法寻找路径时不重复使用同一条链路,达到各链路流量均衡的目的。
3 计算机仿真
仿真网络我们选择泛欧模型Cost239,如图2所示。
3.1 仿真假设
为了建立在波长资源约束条件下的路由分配仿真模型,我们作如下假设:
1)网络中每条光纤可使用的波长数相同且具有相同的光特性。当设置的固定的波长资源耗尽时,即判定该路经断开;
2)任意两个节点之间的通信都只占用一个波长信道;
3)网络中有波长转换机制,即任意两个节点之间的连接可以用不同的波长建立,寻找路由时,只需找到最短路径即可;
4)光网络中的每个波长通道的信号都具有方向性,每个节点对之间都有双向的业务连接,而每个光缆链路包含两个单向光纤。
基于以上假设,把网络拓扑图抽象成为无向图,节点代表路由器,边代表光纤。
3.2 仿真参数
1)网络的阻塞率:在一定的业务负载下被阻塞掉的业务请求总数与网络的业务连接请求总数之比;
2)网络的资源利用率:相应的定义为网络为了满足业务流矩阵的需求而消耗的波长信道数与网络所能提供的最大波长信道数之比。
3.3 仿真模型流程
1)初始化。把实际的拓扑结构图抽象为数学模型,用邻接矩阵A=[aij]n×n表现;
2)随机数产生100个需求矩阵,随机数需求矩阵的平均需求数可设置,需求矩阵是对称矩阵。
3)均衡前,每个需求矩阵调用一次路由算法,100个随机数需求矩阵求出平均阻塞率、平均资源利用率。
4)在流量均衡的条件下,生成100个随机数矩阵,求出平均阻塞率、平均资源利用率。
5)均衡前后的各参数进行计算机绘图,并对结果进行分析。
3.4 仿真结果及分析
用MATLAB6.5绘出均衡前后平均阻塞率、平均资源利用率分别与平均需求的关系曲线图(Cost239网络中最大流量设置为32、随机数的取值范围0~15)。
1)均衡前后网络阻塞率如图3所示:
由曲线图可看出:(1)在网络容量一定的情况下,均衡前后随着平均需求增加,即业务量的增加,阻塞率单调上升,这是因为业务总量增加,网络容量不变,阻塞需求越多,阻塞率越大;(2)随着平均需求的继续增加,均衡前后阻塞率曲线上升平缓,二者有趋向一致的趋势;(3)由均衡前后图对比看出:均衡后的阻塞率曲线总在均衡前曲线下方,即阻塞率较小,网络性能得到优化,这是符合理论推理的,因为均衡后避免了局部链路阻塞,降低了阻塞率,优化了网络性能。
2)均衡前后网络资源录用率如图4所示:
由曲线图可看出:(1)在网络容量一定的情况下,均衡前后随着平均需求的增加,资源利用率曲线均单调上升,这是因为需求总数增加,找到的最短路径数越多,利用的资源越多,资源利用率越高;(2)由均衡前后图对比看出:在平均需求比较小时,均衡前的资源利用率大于均衡后;当平均需求比较大时,均衡后资源利用率明显大于均衡前。这是因为平均需求比较小时,均衡后在需求基本满足的基础上均衡了各链路上的流量,利用资源总数相比均衡前减小,资源利用率减小;平均需求比较大时,均衡后避免了局部阻塞,阻塞率下降,利用资源总数相比均衡前增加,所以资源利用率增加。
4 结论
本文在Dijkstra算法的基础上,实现了基于流量均衡的路由算法,通过仿真得到结论,对于Cost239网络,在相同的约束条件下,流量均衡后网络的阻塞率减小、资源利用率提高,这说明基于流量均衡的算法可以使网络的通信性能提高。
参考文献
[1]Al Sukhni,E.M.;Mouftah,H.T..Integrated Routing and Wa-velength Assignment and signaling in shared protection frame-work for survivable WDM optical mesh networks[C].Communications,200824th Biennial Symposium.2008:103-106.
[2]华剑浩,乐孜纯.波长路由光网络中路由问题研究[D].浙江工业大学,2007:4-6.
[3]C.S.R.Murthy and M.Gurusamy“,WDM Optical Networks:concepts,design,and algorithms,”Prentice Hall PTR,2002.
[4]黄铁瑛,王辉.智能光网络的路由技术[J].通信技术.2008,41(12):195-197.
[5]Xiaowen Chu,Bo Li.Dynamic routing and wavelength assign-ment in the presence of wavelength conversion for all-optical networks[J].Networking,IEEE/ACM Transactions.13(3),2005:704-715.