路由和波长分配PPT课件

1、路由和波长分配1. 基本概念基本概念n路由和波长分配（Routing and Wavelength Assignment，RWA）问题是光网络优化设计中一个很重要的子问题n即在给定了网络拓扑和节点间连接请求（光路/呼叫）的前提下，需要：1.为这些连接请求寻找源节点到目的节点间的路由路由2.为这些路由分配合适的波长波长 光通路、光路、 Light Path OXCOXCOXCOXCOXCOXCOXC连接请求Client Network AClient Network B入口节点出口节点光通路 (OXC)Light Path = route + wavelength网络节点结构网络节点结构OXCN

2、xNPhotonic Switch1NxNPhotonic Switch2NxNPhotonic Switch3NxNPhotonic Switchw.光纤123w123w123w123w光纤结构之一：全波长转换全波长转换结构之二：无波长转换无波长转换的光交叉连接设备，每个端口一根光纤，每根光纤复用个波长波长转换波长转换n此外还有：有限波长转换有限波长转换 波长变换器只能把输入的部分波长转换成输出的部分波长，即波长转换器的波长转换范围不能覆盖整个复用波长集稀疏波长转换稀疏波长转换 只在部分节点配置了波长转换器（可以是完全或部分波长转化器） 光通道类型光通道类型n与有、无波长变化相对应，光通道可

3、分为两种类型：n波长通道波长通道（wavelength path，WP）n虚波长通道虚波长通道（virtual wavelength path，VWP）流量类型流量类型 n通常将网络支持的业务分为以下两类。n静态流量业务静态流量业务：事先给定一组光路连接请求，需要为这些请求寻找路由并在其路由上分配波长，以使网络地性能达到最优n动态流量业务动态流量业务：光路请求以满足一定概率分布地方式到达和离开网络，相应的性能指标通常是请求的阻塞率n按照所支持的业务类型划分，可将RWA的问题分为静态静态RWA问题问题和动态动态RWA问题问题寻路和信令光网中的寻路OSPF-TE、ISIS-TE、或距离向量协议等源

4、选路(Source Routing)光网中的信令根据寻路结果来建立光通路（Light Path)CR-LDP，RSVP-TE等2. RWA问题简介n传统网络中网络寻路和资源分配问题IP网络提供尽力而为尽力而为服务，只有寻路，没有资源分配没有资源分配ATM、Packet over SDH等网络需要寻路，同时也有资源的分配问题，但是资源的分配不具有全局重要性不具有全局重要性nWDM网络中的波长一致性条件波长一致性条件要求从入口到出口使用同一个波长入口到出口使用同一个波长波长分配具有全局重要性全局重要性合适地选择波长，可以使：所需波长数目最小、网络吞吐率最大，或连接请求阻塞率最小连接请求阻塞示例OX

5、C-aOXC-cOXC-dOXC-bOXC-eOXC-gOXC-f11连接请求1(a-g)连接请求2(c-g)请求被组塞波长重用波长重用格形网络拓扑在不同的链路可以实现波长重用在不同的链路可以实现波长重用节点执行波长信道的交换波长连续性限制波长连续性限制当输入端有两个波长相同的信道需要交换到同一根输出光纤时，会发生阻塞此时加入波长变换器波长变换器可以消除这种冲突，增加波长重用的灵活性3. 路由选择算法路由选择算法 n路由选择算法一般是基于一定的优化目标（如路径最短路由、负载均衡等）为连接请求决定最佳路由n路由的计算既可采用离线离线方式，也可采用实时实时计算的方式n目前常见的路由算法有以下四种：

6、 A. 固定路由（固定路由（Fixed Routing，FR）n这是最简单的路由方法，即采用最短路算法（如Dijkstras 算法）为网络中的每一个节点对之间预先计算一条路由，路由选好后固定不变n当源、宿节点对之间的连接请求到达时，在预先计算好的路由上为连接请求分配波长，从而建立光连接n如图，节点0到节点2的最短路由为012n最短路径算法的缺点是有时会使网络中某些链路过于拥挤；改进的方法是采用负载均衡负载均衡选路 B. 备选路由（备选路由（Alternate Routing，AR）n这种方法预先为网络中的每一个节点对之间预先计算多条路由，并按照路由长度从短到长排列，构成备选备选路由集路由集n当

7、源、宿节点对之间的连接请求到达时，首选选择其相应路由表中的第一条路由分配波长n如果没有找到可用波长，再选择第二条路由进行尝试，直到成功建立光路为止 n如图所示，节点0到节点2首选路由首选路由和备用路由备用路由分别为012和0542n与固定路由法相比，连接被阻塞的概率显著减小C. 自适应动态路由（自适应动态路由（Adaptive Dynamic Routing，ADR）n这种方法根据网络状态实时进行选路实时进行选路 n如图所示，节点0和节点2之间的自适应路由为05432ADRn这种路由方案能根据网络当前的状态和资源使用情况来计算路由，所以在提高网络资源利用率和降低网络阻塞率方面优于前两种路由方案

8、优于前两种路由方案n但这种方案需要光网络控制和管理平面提供网络状态状态信息信息，网络节点之间还有不断交换链路状态信息，所以实现起来较复杂较复杂n而且RWA算法的运行速度不及路由预计算的方式 路由算法比较nFR方法可以节省业务到达时由于实时计算路由所花费的时间，从而提高RWA 算法的运行速度，但这样得到的路由往往不是当前网络状态下的最佳路由nADR方式可以克服离线路由计算的不足，但付出的代价就是导致RWA 算法的运行速度降低n为了兼顾预计算在时间上的优势和实时计算在优化路由选择上的优势，可以在采用预计算时计算多条候选路由，在连接请求到达时根据网络状态选用其中最佳的路由，AR就属于此类算法4. 波

9、长分配算法波长分配算法 1.随机分配（Random Assignment，RA）法2.首次命中（First Fit，FF）法3.最大使用（Most-Used，MU）法4.最少使用（ Least-Used，LU）法5.最小乘积（ Min-Product，MP）法6.最轻承载（Lest-Loaded，LL）法7.最大和法（MAX-SUM）8.相对容量损失法（RCL）1）随机分配（）随机分配（Random Assignment，RA） n首先搜索所有可用波长的集合，找出路由可用的波长子集n再从中随机选取波长分配给光通道随机选取波长分配给光通道n这种算法简单，不必知道全网的状态信息2）首次命中（）首次

10、命中（First Fit，FF）法）法n这种方法将所有的波长按一定的规则进行编号，按编号从小到达的顺序搜索可用波长n找到的第一个可用波长即被分配给光路找到的第一个可用波长即被分配给光路n与RA相比，FF不必搜索全部可用波长，找到一个可用波长就停止，因此计算量较小3）最大使用（）最大使用（Most-Used，MU）法）法n这种方法的基本思想是，将网络流量集中在少数将网络流量集中在少数波长上波长上，即通过统计当前波长的占用情况，优先优先选取被最多链路占用的波长选取被最多链路占用的波长n这样，后续光通道就有更多的可选波长。n有关研究表明该方法的效率明显优于前两种 4）最少使用（）最少使用（ Leas

11、t-Used，LU）法）法n这种方法根据波长被占用情况的统计，优先选取被最优先选取被最少链路占用的波长少链路占用的波长n这种算法的出发点是使得网络流量更均匀的分摊到各个波长上，即波长的负载均衡负载均衡n但LU下，较长的光通道往往被拆开较长的光通道往往被拆开，只有较短的光通道容易保持波长一致性5）最小乘积（）最小乘积（ Min-Product，MP）法）法n这种方法是一种适用于多纤多纤光网络的算法 n它先给所有波长编号，对于每个波长j，计算 ，其中Dlj表示链路l上的波长j已被占用的光纤数，(p)表示光通道p所经过的链路集合n优先选择能使乘积项最小且编号较低的波长优先选择能使乘积项最小且编号较低

12、的波长n当每条链路的光纤数是1时，MP就退化为FF( )ljlpD6）最轻承载（）最轻承载（Lest-Loaded，LL）法）法n这也是一种适用于多纤多纤光网络的算法n它首先计算 ，其中Sp表示光通道p上空闲波长集合，Ml指链路l上的光纤数n优先选择满足上式且编号较小的波长优先选择满足上式且编号较小的波长nLL算法的出发点是将最空闲的波长优先分配给最将最空闲的波长优先分配给最繁忙的链路繁忙的链路，它的效果比MU法好 ()maxmin()lljlpj SpMD7）最大和法（）最大和法（MAX-SUM）n既可用于单纤单纤网络又可用于多纤多纤网络的算法n它首先计算波长j在链路l上的空闲容量（定义为链

13、路l上的光纤总数减去链路l上占用波长j的光纤总数），然后优先选择能使空闲容量最大的那个波长进行波长分配n该算法考虑了资源分配对整个网络的影响，而不仅仅是对所选路由和波长的影响，因而能够获得较好的性能。该算法适用于静态波长静态波长分配问题 8）相对容量损失法（）相对容量损失法（RCL）n这种方法类似于MAX-SUMnMAX-SUM法致力于将绝对绝对空闲容量最大化n而RCL法则致力于将相对相对空闲容量最大化n它们都适用于流量非标准的网络，其中RCL的性能稍好 分析分析n总体来说，波长分配方法所考虑的网络状态（如波长使用率、波长在网络链路上的空闲容量等）越全面，则波长分配方法对网络资源优化率越高n但

14、这样的波长分配方法的复杂度复杂度也越高n因此，为了在兼顾RWA算法性能的基础上尽量降低算法的复杂度，目前大量研究在解决波长分配问题时都使用了FF或RA波长分配方法 5. 静态静态RWA问题问题 n静态RWA问题又称为静态光路建立静态光路建立（Static Lightpath Establishment, SLE）问题，即预先给出多条光路连接需求，计算路由和分配波长n这种计算可以是离线（off line）的，即不需在线（on line）的实时计算n静态RWA问题所考虑的是，如何从全局优化的角度来如何从全局优化的角度来为所有光路连接需求建立光路为所有光路连接需求建立光路静态静态RWA问题问题n常用

15、的优化准则有两种：常用的优化准则有两种： 1.在满足所有连接请求的前提下，使用最少的波长数或光纤数2.在波长/光纤数目给定的前提下，满足尽可能多的连接请求静态静态RWA问题问题nRWA问题中涉及到了虚拓扑虚拓扑（Virtual Topology）n虚拓扑虚拓扑是指解决静态RWA问题后，所有光路构成的逻辑上的网络拓扑，也称为WDM光传送网的逻辑拓扑逻辑拓扑（Logical Topology）n虚拓扑中的节点就是网络物理拓扑的节点，这些节点通过建立的光路光路连接起来静态静态RWA问题问题n按照虚拓扑所支持的上层业务种类的不同上层业务种类的不同，可以将静态RWA问题分为两类：1.支持电路交换业务的静

16、态支持电路交换业务的静态RWA算法算法2.支持分组交换业务的虚拓扑设计支持分组交换业务的虚拓扑设计n前者的业务请求矩阵给出了每个节点对间需要支持的光路数光路数n而后者的业务请求矩阵中存放的是节点对之间归一化的平均分组业务强度平均分组业务强度1）支持电路交换业务的静态）支持电路交换业务的静态RWA算法算法 n静态RWA可通过整数线性规划（Integer Linear Programming，ILP）方法求解n但ILP求解复杂度随着网络规模的增大而急剧增加n因此，一般可以把将静态RWA问题拆成选路子问题选路子问题和波长分配子问题波长分配子问题，分成两步解决n第一步，为每条光路建立请求选择路由n选取

17、了路由之后，第二步就是分配波长 路由选择路由选择n路由选择方法通常采用FR或ARn由于FR通常采用的路由是最短路由，即光路经过的物理链路跳数或代价总和最小，因此此时波长分配方法对网络性能有很大影响n在采用AR时，需要预先为每个节点对之间计算多条备用路由，组成备用路由集。再按照一定的顺序检查备用路由集中的各条路由，寻找合适的路由并为其分配波长波长分配波长分配n波长分配方法通常采用RA或FFn最简单的波长分配方法是RAn由于波长连续约束波长连续约束，该方法使得长光路相对于短光路来说更容易被阻塞n为了克服这个缺点，可采用“长路由优先长路由优先”，即按照按照光路长度递减的顺序分配波长光路长度递减的顺序

18、分配波长2）支持分组交换业务的虚拓扑设计）支持分组交换业务的虚拓扑设计 n在支持分组业务的WDM光网络中，RWA涉及虚拓扑设计n虚拓扑设计的目的，是为了将光域的波长路由技术光域的波长路由技术和电域电域的传统交换技术的传统交换技术结合，以便更好地支持上层的分组业务分组业务n确定应该在哪些节点对之间建立光路，以及如何分配有限资源，此问题称为“虚拓扑设计虚拓扑设计”问题n支持分组业务的WDM光传送网，其设计的核心核心就是如何得就是如何得到网络性能最佳的虚拓扑到网络性能最佳的虚拓扑 虚拓扑设计虚拓扑设计A数据网数据网DCBEASON网络网络F6. 动态动态RWA问题问题 n在动态情况下，光路连接请求随

19、机、顺序随机、顺序到达网络，要求进行实时实时RWA计算；一条光路维持一段有限时间后又被拆除n动态RWA算法的目标，一般都是有效地选择光路路由和合理分配波长资源，以使光路建立的阻塞率阻塞率最低n通常又称为动态光路建立（Dynamic Lightpath Establishment，DLE）问题 动态业务动态业务n动态业务需求在下列情形下可能出现：1.当业务分布出现较大变化，或者链路、节点出现故障，需要对网络重新配置时2.随着宽带业务（如虚拟专用网、ISP租用速率超过2.5Gb/s的线路等）的出现和增长，业务需求有可能随时间而改变 动态动态RWA：分层图分层图n在动态RWA中，在网络规模不太大时，

20、可以采用分层图分层图(Layer Graph)方法将选路和波长分配选路和波长分配集合集合在一起考虑动态动态RWA：ADRn但随着网络规模增大，为了减小复杂性，常将选路和将选路和波长分配分两步进行波长分配分两步进行n常用的选路方法可采用前面介绍的FR、AR及ADR三种n前两种选路方式与静态RWA问题中一样，下面仅介绍基于ADR的动态RWA算法 动态动态RWA：ADRn在在ADR算法中，源、宿节点间的路由根据网络的状态进行动态选择算法中，源、宿节点间的路由根据网络的状态进行动态选择 , 1 如果：链路 代价基本代价其他jjfjf1876543211912101318765432119121013(a)(b)18765432119121013(a)7. 集中还是分布集中还是分布n集中式控制网管中心集中控制资源分配（决策者）光节点只负责利用信令建立/拆除光通路（实施者）n分布式控制光节点自主寻路，需要运行寻路协议集中还是分布集中还是分布n集中式控制减少光节点复杂度阻塞率降低可扩展性差，容错性较差n分布式控制容错性能较好需要复杂的寻路协议8. 波长转换与波长转换与RWA算法算法 n