北邮光网络技术作业第2次路由波长分配(RWA)算法的研究现状

路由波长分配（RWA）算法的研究现状班级：2010211117学号：10210518姓名：刘芷若1.前言波分复用（WavelengthDivisionMultiplexing—WDM）网络利用了光纤传输链路的巨大带宽，随着WDM技术日趋成熟，WDM传输技术已经进入实用化和商用化阶段。WDM全光通信网是光纤通信未来发展的主要方向之一。由于光网络对传输信号的速率和格式透明，具有灵活的波长选路和动态资源配置能力，可以实现网络的动态重构，被认为是通信网络升级的首选方案。如何利用现有的和即将敷设的光纤连网，构成未来高速、大容量、多业务的WDM网络已经成为光通信领域中的一个重大问题。WDM网络节点处采用光分插复用器（OADM）或光交叉连接设备（OXC）在光层建立光连接，即光通道（opticalpath），为高层的多个逻辑电网络提供了高速、大容量的信息传送平台。光通道的建立，要求在传送网的物理结构中选择一条由业务源点到宿点的路由，并为其分配一定的波长信道（参见图1.1）。考虑到波长资源的重利用以及提高网络的阻塞性能，优化光通道的选路和波长分配（RoutingandWavelengthAssignment—RWA）方案成为光通道层设计的核心问题。RWA解决如何寻找一条合适的光通道并合理地分配通道所使用的波长，使有限的资源充分发挥作用，以提供尽可能大的通信容量。2.RWA算法的分类WRON被认为是构建下一代光网络的候选方案之一。但是由于网络资源有限(如波长数、收发器数目等)，不可能在网络中为每一节点对都建立一条直接相连的光路，因此针对不同的网络需求，需要考虑对现有可用资源进行高效利用和优化设计。WRON的核心问题是优化设计光路的选路和波长分配，寻找一条合适的光路并为之合理地分配波长，使有限的资源充分发挥作用，以提供尽可能大的通信容量。根据光通道连接请求的特点，可以把RWA问题分成静态和动态两类。(1)静态RWA(SRWA)问题：网络的业务类型是静态的，而且当所有连接建立好之后，连接将保持不变。光通道连接请求是预先给出的，因此要求离线计算路由和分配波长，而不需要实时计算。SR—WA问题的研究适合广域网(或骨干网)，因为对于广域网来说，其业务流量基本是确定的。SRWA的输出结果是所有的源一目的节点对之间的光通道的路由以及给这些光通道分配的波长。(2)动态RWA(DRWA)问题：光通道连接请求是逐条提出的，而且一条光通道持续一段时间后又被拆除，因此需要为每一条光通道做实时RWA计算。对于DRWA问题，对光通道建立请求的处理通常有两种策略：可重构型策略和不可重构型策略。所谓可重构型策略，就是当网络拥塞发生的时候，光网络的逻辑拓扑可以进行重构，以消除拥塞情况。但是这样的操作可能会中断很多现有的连接，而且需要对网络节点之间的光通道进行大量的调整(拆除或者重新建立)，因此不适合大规模的网络。而不可重构型策略，则在拥塞发生的时候不能重构光通道，只能拒绝该请求。图1RWA算法的分类表1典型RWA算法序号算法名称时间研究机构说明1固定路由选路(FR)法2008北京交通大学光波技术研究所解决路由选择子问题2固定备用路由选路(FAR)法2008北京交通大学光波技术研究所解决路由选择子问题3自适应选路(AR)法2008北京交通大学光波技术研究所解决路由选择子问题4整数线性规划(ILP)法2008北京交通大学光波技术研究所解决路由选择子问题5路由扩展方法2008北京交通大学光波技术研究所解决路由选择子问题6随机分配(R)算法2009河北工程大学基于局部信息的波长分配算法7首次命中(FF)算法2009河北工程大学基于局部信息的波长分配算法8最大使用(MU)算法：2009河北工程大学基于全局资源信息的波长分配算法9最小使用(LU)算法2009河北工程大学基于全局资源信息的波长分配算法10最小乘积(MP)算法2009河北工程大学基于全局光通道信息的波长分配算法11最轻承载(LL)算法2009河北工程大学基于全局光通道信息的波长分配算法12最大总和(MS)算法2009河北工程大学基于全局光通道信息的波长分配算法13最小影响(LI)算法2009河北工程大学基于全局光通道信息的波长分配算法14相对容量损失(RCL)算法2009河北工程大学基于全局光通道信息的波长分配算法15顶点着色算法、启发式算法16遗传算法和紧急搜启发式算法17索算法等启发式算法2.1固定路由选路(FR)法：选路是事先进行的，网络拓扑结构已知后，按照标准最短路径算法(如Dijkstra算法和Bellman-Ford算法)为每个节点对分配固定的光路。当光路请求到达时，源、目的节点对之间的通信连接总是建立在预定好的路由上。这种方法的优点是可以把RwA问题简化为波长分配问题，从而大大简化网络的控制和管理。缺点是网络性能较差、阻塞率较高。另外，该算法中网络不具备链路故障恢复能力。2.2固定备用路由选路(FAR)法：FAR的核心思想是为每个节点对预先确定多条备用路由，并按一定的优先级顺序排列。排在最前面的称为主路由，其他的视为备用路由。当业务到达时，按照工作路由建立光通路，当工作路由己被占用或失效时，选择次优路由。与固定路由方案相比，网络的阻塞率大大降低，网络具有故障恢复能力，但时间复杂度相对较高。2.3自适应选路(AR)法：AR算法中路由根据网络的状态动态地确定。它的实现可采用以下两类方法，第～类是预先为节点对之间确定多条备用路由，与固定、备用路由方案类似。第二类方法是不预先为节点对确定备选路由，当连接请求到达时根据网络状态为其确定路由。AR业务请求的阻塞率同FR和FAR相比最低，但网络的控制和管理比较复杂，时间复杂度也大大提高。2.4整数线性规划(ILP)法：通常分为基于流的II。P和基于通道的ILP。基本思路是：列写优化目标方程一列写约束条件方程一求解线性规划。这里可以利用现有的线性规划软件工具(Lingo)对光网络拓扑设计的ILP方程进行求解，最终求得优化路由的方法。利用ILP选路灵活，网络可以具有或不具有故障恢复机制，但是这种方法只适用于规模较小的网络。2.5路由扩展方法：该方法是在一段链路中插入一个节点，用新节点与原链路两端节点构成的两段链路来替换原来的一段链路，这样就构成了一个新路由，利用逐步扩展思想来构造节点之间所有的可能连接方式。此方法既可以用于网络的实际拓扑，也可以用于网络的虚拓扑。这种方法对于业务的恢复路由计算速度比较快，但路由扩展方法只是一种局部的方法，不具有全局性。2.6基于局部信息的波长分配算法2.6.1随机分配(R)算法：首先搜索所有波长的集合，找出可用波长集，再从中随机选择波长分配给光通道。2.6.2首次命中(FF)算法：将波长在可用波长集中按固定顺序排列，对新到达的连接请求要建立的光通路，每次选择波长时均按固定顺序选择可用波长，并将选到的可用波长分配给路由。2．7基于全局资源信息的波长分配算法2.7.1最大使用(MU)算法：首先统计全网中所有波长的使用率，然后优先选择使用率最高的可用波长。这种算法有利于将流量集中在少数波长上，这样可以减少网络的波长需求。2.7.2最小使用(LU)算法：首先统计全网中的所有波长的使用率，然后选择使用率最低的可用波长。这种算法的出发点是使网络流量均匀分摊到各个波长上。2.8基于全局光通道信息的波长分配算法2.8.1最小乘积(MP)算法：优先选择能使光通道的所有链路占用某波长的光纤总数乘积项最小的且编号较低的波长。当每条链路的光纤数目为1时，MP算法就蜕化为FF算法。2.8.2最轻承载(LL)算法：将最空闲的波长分配给最繁忙的链路段。2.8.3最大总和(MS)算法：该方法使得选择该波长后，全网的其他通道的剩余可用通道数目总和最大。2.8.4最小影响(LI)算法：选择该波长后，对全网其他通道的影响(相关通道造成的瓶颈总和)最小。2.8.5相对容量损失(RCL)算法：该方法类似于MS算法，也是针对提升网络其他链路的空闲容量。MS算法只是致力于将网络其他链路的绝对空闲容量最大化，而RCL算法则致力于将相对空闲容量最大化。2.7启发式算法3.结论WRON被认为是实现未来高速率、大容量全光网络的有效的解决方案。它以一个波长为交换粒度，采用WDM技术和波长路由技术，通过波长进行端到端之间的路由。但由于在WRON中，网络单元的功能、物理传输性能以及实际可使用的网络资源受到限制，在网络的所有接人节点之间都建立直接的光通道连接是非常困难的。所以，为了合理进行网络优化设计，有效利用网络资源，利用启发式算法对RWA算法进行优化已经成为研究的热点。Reference：[1].张曙光，叶运峰，李晓东，赵继军,“波长路由光网络中RWA算法的设计分析,”光通信研究,5,155,34,2009.10.[2].ThomasE.SternKrishnaBala徐荣龚倩,多波长光网络,人民邮电出版社AddisonWesleyLongman,Inc.2001.