论文部分内容阅读
【摘 要】随着多媒体业务的迅速发展，网络中多播业务变得越来越普及，并且光传输网故障导致的业务中断将造成巨大经济损失，因此有必要研究光网络中多播生存性技术。本文研究了基于自动交换光网络（ASON）的多播专用保护算法。仿真结果表明，本文所设计的基于ASON的绿色多播专用疏导保护算法具有更低的业务阻塞率，而且可以节省较多的能耗。
【关键词】ASON 绿色光网络 动态多播 疏导保护
一、引言
光核心网技术的发展迅猛，一旦某条光纤断裂将造成严重后果，如何实现高效的网络保护和恢复，如何实现保护带宽的智能动态分配，都是自动交换光网络（ASON）需要解决的问题。ASON作为具有分布式智能的光传送网，它的最大特点就是在传送平面（TP）和管理平面（MP）的基础上引入了具有智能的控制平面（CP），并使用了信令、路由和自动发现等技术，因此ASON能够实现实时的光通道指配及灵活的带宽管理。
本文针对可能发生的光网络多播单链路失效情况提出了新的保护算法，即基于ASON的绿色多播专用疏导保护算法（Dedicated Multicast Green-grooming Algorithm based on Spanning-path）简称DMGAS，该算法基于遍历路径保护，结合ASON智能控制和动态自动调节的优势，大大提高了多播传输的服务质量，同时针对绿色节能方面我们提出的算法可以最小化由链路保护所带来的电能消耗。
二、数学模型
（一）辅助图模型Auxiliary Graph Model
为了进行动态的业务量疏导，本文在文献[1]所提出的疏导图的基础上定义两种辅助图：虚拓扑图（Virtual topology Graph，VG）和联合疏导图（Integrated Graph，IG），如图2.1所示。
数学符号说明如下：
：网络物理拓扑上的节点标号；
：IG中波长平面中的对应于物理拓扑节点的节点；
：VG和IG中的虚拓扑平面中，利用波长所建立的光路的端节点；
：IG中的节点对之间的物理链路；
：IG中波長平面中节点对之间的波长链路；
：IG中的虚拓扑平面，利用波长在节点对之间所建立的光路链路
：物理链路的代价
：波长链路的代价，与对应的物理链路代价相等；
：光路的代价，光路代价为组成条光路的所有波长链路代价之和；
：三种符号分别表示物理链路，波长链路，光路链路的状态，有四种状态，分别用u、w、p和mix来表示，分别为空闲、工作、保护和混合。
虚拓扑图VG是一个单层图，如图2.1（b），图中每条链路都是光路链路（Partially Available Lightpath， PAL）。虚拓扑中节点具有波长变换能力，这种波长变换的能力实现的前提是在该点处分配光收发器，通过光收发器将光信号转换成电信号，在电交换矩阵中实现业务融合以及波长变换。新到达的低速业务可以利用所有PAL链路上的剩余带宽来建立连接。
联合疏导图IG是将分层图和虚拓扑图联合在一起，如图2.1（c），即将物理拓扑转化为个互不相邻的波长平面，每个平面都对应一个特定的波长，另外又增加了虚拓扑图作为平面，将个平面联系起来的是虚链路（如图2.1（c）中的虚线所示），如果在节点中存在空闲的光收发器，那么就可以将在每个层中对应的这个点用虚链路连接起来。
图2.1辅助图
（二）问题描述
物理拓扑，其中是网络节点集；是链路集；为每根光纤支持的可用波长集，并且。每条链路赋予一正权值，表示使用该条链路疏导业务所需的代价。多播业务请求随机动态地到达和离开，其中是源节点；是目的节点集合；是业务请求带宽；是业务服务持续时间。
如果多播业务请求成功建立一棵工作树，工作树中的节点度为1的节点数目为，那么可以将这棵划分为条遍历路径，每条遍历路径可以看作一个单播请求，其中分别是源节点和目的节点。为这些单播请求计算保护路径，最后计算出最小代价树，使得工作树上任意一条链路失效后都能利用保护路径实现业务恢复。
优化目标：最小化
（2.1）
模型的优化目标（公式（2.1））最小化网络的能耗。公式前半部分计算光收发器和路由器端口的能耗，公式的后半部分统计光放大器的能耗。因为多播树的计算是一个NP-hard问题，所以针对如上问题我们在第三章中提出了启发式算法。
三、DMGAS算法描述
（一）选路图构建
在计算工作树和保护路径时需要根据疏导辅助图来构建有效的选路图。在构建计算工作树的选路图时只要辅助图的链路的带宽大于或是等于业务请求的带宽就可以加入到选路图中，但是在构建计算保护路径的选路图时不仅带宽要满足要求，并且要与被保护的工作路径链路分离。计算工作树和保护路径时，按照相关公式在选路图上设置各链路的代价。目的是使保护路径能够相对集中在同一条链路上，那么就可以有更多的设备可以进入睡眠状态，促进节能的实现。
（二）算法步骤
步骤1：根据物理拓扑和当前的网络状态初始化虚拓扑图或联合疏导图。
步骤2：等待多播业务请求，如果是建立连接请求，转至步骤3；如果是释放连接请求，转至步骤5；
步骤3：用下面的步骤为连接请求计算多播树和保护路径：如果成功，记录工作树和保护路径集信息，转至步骤4；如果失败，该业务请求被阻塞，返回步骤2。
（a）根据网络资源使用状况和多播业务请求带宽在虚拓扑图中裁减带宽值小于的光路链路PAL，并根据公式3.2和重新设置光路代价，得到有效虚拓扑图。用最小代价树MPH算法寻找连接源节点s并包含目的节点集D中所有节点的工作树，如果成功，则记录多播树信息，并找出节点度为1的节点，将工作树划分成条遍历路径，并根据第条遍历路径形成一个单播请求，并转至（c）；否则继续（b）。 （b）根据网络资源使用狀况和多播业务请求带宽，与（a）相同，根据公式3.1和3.2以及，重新设置光路和波长链路的代价。采用MPH算法为业务请求计算一棵多播树，在这棵多播树中可能是光路链路、波长链路和虚链路的组合。如果计算成功，与（a）相同，则转至（d）；否则业务阻塞，转至步骤2。
（c）针对每个单播请求。根据保护请求带宽形成与链路分离的可用的虚拓扑图，并根据公式3.4和重新设置光路代价，转至（e）。
（d）针对单播请求。根据保护请求带宽b形成与遍历路径链路分离的可用的联合疏导图，并根据公式3.3和3.4及重新设置光路和波长链路的代价，转至（e）。
（e）利用Dijkstra’s算法为所有单播请求计算保护路径，如果为至少个请求选路成功，则转至（f），否则业务阻塞，转至步骤2。
（f）利用最小遍历树算法选出代价最小的保护路径集。如果工作树中任意链路故障都通过保护路径恢复业务，则记录保护路径集信息，并转至步骤4，否则业务阻塞，转至步骤2。
步骤4：为多播业务请求分配资源，为建立的所有保护路径预留资源。统计新建光路在IP路由端口、光收发器、光放大器等器件所消耗的能量。
步骤5：释放链路带宽资源，更新节点空闲光收发器资源和IP路由器端口资源，如果某节点的光收发器由无到有，则恢复这个节点的虚链路。
四、仿真分析
本章将DMGAS算法分别与没有采用疏导技术的多播遍历路径专用保护算法（DMPAS）[3]、多播疏导专用树保护算法（DMGAT）[3]和多播疏导专用分段保护算法（DMGASE）[3]进行了比较。最后分析了不同的代价设置参数对算法DMGAS的影响。网络拓扑模型为USNET，每个节点都采用的是结构和功能相同的GMC-OXC，并且具有完全分光能力，且配备有足够多的光收发器。在网络中每条物理链路可容纳的波长数相同为2，每个波长所支持的带宽为OC-48。
如图4.1所示，四种算法在网络负载增加时业务阻塞率不断增加，其中DMPAS最差，DMGAT和DMGASE其次，DMGAS最好。DMGAS阻塞率较低的原因是采用了基于遍历路径的保护方式，这种方式不会像基于树保护时对链路分离的限制那么高，只需要与被保护的遍历路径链路分离即可，也不会像基于分段保护需要较多的保护路径。所以在网络负载较低的情况下业务阻塞率几乎为零，网络负载较高的情况下业务阻塞率的增涨也很缓慢。
图4.1四种算法业务阻塞率BR的比较
比如DMPAS算法的平均能耗一直比较平稳。DMGAS算法的平均能耗则是随着网络负载的增加而逐渐降低，但DMGAT算法的平均能耗最高，然后是DMGASE算法，最低是DMGAS算法。DMGAT和DMGASE这两个算法总能耗相差不多，但DMGASE的业务阻塞率低，平均每个业务的能耗就要低一些。DMGAS的平均能耗较低是因为除了采用光旁路和业务量疏导这两个技术外，还采用设备睡眠技术。
图4.2在DMGAS算法中代价设置参数对AEC的影响
图4.2所示，四种参数的DMGAS算法平均能耗趋势均与仿真时钟相似，随着网络负载的增加，平均能耗降低，在网络负载低时下降速度非常快，当网络负载高时平均能耗趋于平稳。在相同负载下，越大，平均能耗越低。平均能耗均降低的主要原因是随着网络负载的增加，处理相同数目的业务所需要的时间越短，消耗的总能耗也就越少。参数越大，就有越多的工作路径和保护路径分别集中，使更多的链路进入睡眠状态。但代价设置参数过高，并没有对能耗有更大的贡献，反而使业务阻塞率增加。的增加能有效的降低网络能耗，但其代价是业务阻塞率增加，并且其增加到一定程度后便失去了对节能的贡献。
五、结论
本文研究了基于ASON的多播专用绿色疏导保护算法，首先设计了辅助图，并将专用多播保护节能问题抽象成数学模型，然后提出了改变链路代价的公式并设计了算法。仿真分析显示，我们所提出的算法不但在阻塞率方面较先前算法有所提高，而且更加节能。
参考文献：
[1]温海波.WDM网状网中的业务量疏导算法研究[D]，电子科技大学，2004.
[2]Idzikowski F， Orlowski S， Raack C， et al. Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios[C]， Conference on Optical Network Design and Modeling （ONDM）， 2010， 1-6.
【关键词】ASON 绿色光网络 动态多播 疏导保护
一、引言
光核心网技术的发展迅猛，一旦某条光纤断裂将造成严重后果，如何实现高效的网络保护和恢复，如何实现保护带宽的智能动态分配，都是自动交换光网络（ASON）需要解决的问题。ASON作为具有分布式智能的光传送网，它的最大特点就是在传送平面（TP）和管理平面（MP）的基础上引入了具有智能的控制平面（CP），并使用了信令、路由和自动发现等技术，因此ASON能够实现实时的光通道指配及灵活的带宽管理。
本文针对可能发生的光网络多播单链路失效情况提出了新的保护算法，即基于ASON的绿色多播专用疏导保护算法（Dedicated Multicast Green-grooming Algorithm based on Spanning-path）简称DMGAS，该算法基于遍历路径保护，结合ASON智能控制和动态自动调节的优势，大大提高了多播传输的服务质量，同时针对绿色节能方面我们提出的算法可以最小化由链路保护所带来的电能消耗。
二、数学模型
（一）辅助图模型Auxiliary Graph Model
为了进行动态的业务量疏导，本文在文献[1]所提出的疏导图的基础上定义两种辅助图：虚拓扑图（Virtual topology Graph，VG）和联合疏导图（Integrated Graph，IG），如图2.1所示。
数学符号说明如下：
：网络物理拓扑上的节点标号；
：IG中波长平面中的对应于物理拓扑节点的节点；
：VG和IG中的虚拓扑平面中，利用波长所建立的光路的端节点；
：IG中的节点对之间的物理链路；
：IG中波長平面中节点对之间的波长链路；
：IG中的虚拓扑平面，利用波长在节点对之间所建立的光路链路
：物理链路的代价
：波长链路的代价，与对应的物理链路代价相等；
：光路的代价，光路代价为组成条光路的所有波长链路代价之和；
：三种符号分别表示物理链路，波长链路，光路链路的状态，有四种状态，分别用u、w、p和mix来表示，分别为空闲、工作、保护和混合。
虚拓扑图VG是一个单层图，如图2.1（b），图中每条链路都是光路链路（Partially Available Lightpath， PAL）。虚拓扑中节点具有波长变换能力，这种波长变换的能力实现的前提是在该点处分配光收发器，通过光收发器将光信号转换成电信号，在电交换矩阵中实现业务融合以及波长变换。新到达的低速业务可以利用所有PAL链路上的剩余带宽来建立连接。
联合疏导图IG是将分层图和虚拓扑图联合在一起，如图2.1（c），即将物理拓扑转化为个互不相邻的波长平面，每个平面都对应一个特定的波长，另外又增加了虚拓扑图作为平面，将个平面联系起来的是虚链路（如图2.1（c）中的虚线所示），如果在节点中存在空闲的光收发器，那么就可以将在每个层中对应的这个点用虚链路连接起来。
图2.1辅助图
（二）问题描述
物理拓扑，其中是网络节点集；是链路集；为每根光纤支持的可用波长集，并且。每条链路赋予一正权值，表示使用该条链路疏导业务所需的代价。多播业务请求随机动态地到达和离开，其中是源节点；是目的节点集合；是业务请求带宽；是业务服务持续时间。
如果多播业务请求成功建立一棵工作树，工作树中的节点度为1的节点数目为，那么可以将这棵划分为条遍历路径，每条遍历路径可以看作一个单播请求，其中分别是源节点和目的节点。为这些单播请求计算保护路径，最后计算出最小代价树，使得工作树上任意一条链路失效后都能利用保护路径实现业务恢复。
优化目标：最小化
（2.1）
模型的优化目标（公式（2.1））最小化网络的能耗。公式前半部分计算光收发器和路由器端口的能耗，公式的后半部分统计光放大器的能耗。因为多播树的计算是一个NP-hard问题，所以针对如上问题我们在第三章中提出了启发式算法。
三、DMGAS算法描述
（一）选路图构建
在计算工作树和保护路径时需要根据疏导辅助图来构建有效的选路图。在构建计算工作树的选路图时只要辅助图的链路的带宽大于或是等于业务请求的带宽就可以加入到选路图中，但是在构建计算保护路径的选路图时不仅带宽要满足要求，并且要与被保护的工作路径链路分离。计算工作树和保护路径时，按照相关公式在选路图上设置各链路的代价。目的是使保护路径能够相对集中在同一条链路上，那么就可以有更多的设备可以进入睡眠状态，促进节能的实现。
（二）算法步骤
步骤1：根据物理拓扑和当前的网络状态初始化虚拓扑图或联合疏导图。
步骤2：等待多播业务请求，如果是建立连接请求，转至步骤3；如果是释放连接请求，转至步骤5；
步骤3：用下面的步骤为连接请求计算多播树和保护路径：如果成功，记录工作树和保护路径集信息，转至步骤4；如果失败，该业务请求被阻塞，返回步骤2。
（a）根据网络资源使用状况和多播业务请求带宽在虚拓扑图中裁减带宽值小于的光路链路PAL，并根据公式3.2和重新设置光路代价，得到有效虚拓扑图。用最小代价树MPH算法寻找连接源节点s并包含目的节点集D中所有节点的工作树，如果成功，则记录多播树信息，并找出节点度为1的节点，将工作树划分成条遍历路径，并根据第条遍历路径形成一个单播请求，并转至（c）；否则继续（b）。 （b）根据网络资源使用狀况和多播业务请求带宽，与（a）相同，根据公式3.1和3.2以及，重新设置光路和波长链路的代价。采用MPH算法为业务请求计算一棵多播树，在这棵多播树中可能是光路链路、波长链路和虚链路的组合。如果计算成功，与（a）相同，则转至（d）；否则业务阻塞，转至步骤2。
（c）针对每个单播请求。根据保护请求带宽形成与链路分离的可用的虚拓扑图，并根据公式3.4和重新设置光路代价，转至（e）。
（d）针对单播请求。根据保护请求带宽b形成与遍历路径链路分离的可用的联合疏导图，并根据公式3.3和3.4及重新设置光路和波长链路的代价，转至（e）。
（e）利用Dijkstra’s算法为所有单播请求计算保护路径，如果为至少个请求选路成功，则转至（f），否则业务阻塞，转至步骤2。
（f）利用最小遍历树算法选出代价最小的保护路径集。如果工作树中任意链路故障都通过保护路径恢复业务，则记录保护路径集信息，并转至步骤4，否则业务阻塞，转至步骤2。
步骤4：为多播业务请求分配资源，为建立的所有保护路径预留资源。统计新建光路在IP路由端口、光收发器、光放大器等器件所消耗的能量。
步骤5：释放链路带宽资源，更新节点空闲光收发器资源和IP路由器端口资源，如果某节点的光收发器由无到有，则恢复这个节点的虚链路。
四、仿真分析
本章将DMGAS算法分别与没有采用疏导技术的多播遍历路径专用保护算法（DMPAS）[3]、多播疏导专用树保护算法（DMGAT）[3]和多播疏导专用分段保护算法（DMGASE）[3]进行了比较。最后分析了不同的代价设置参数对算法DMGAS的影响。网络拓扑模型为USNET，每个节点都采用的是结构和功能相同的GMC-OXC，并且具有完全分光能力，且配备有足够多的光收发器。在网络中每条物理链路可容纳的波长数相同为2，每个波长所支持的带宽为OC-48。
如图4.1所示，四种算法在网络负载增加时业务阻塞率不断增加，其中DMPAS最差，DMGAT和DMGASE其次，DMGAS最好。DMGAS阻塞率较低的原因是采用了基于遍历路径的保护方式，这种方式不会像基于树保护时对链路分离的限制那么高，只需要与被保护的遍历路径链路分离即可，也不会像基于分段保护需要较多的保护路径。所以在网络负载较低的情况下业务阻塞率几乎为零，网络负载较高的情况下业务阻塞率的增涨也很缓慢。
图4.1四种算法业务阻塞率BR的比较
比如DMPAS算法的平均能耗一直比较平稳。DMGAS算法的平均能耗则是随着网络负载的增加而逐渐降低，但DMGAT算法的平均能耗最高，然后是DMGASE算法，最低是DMGAS算法。DMGAT和DMGASE这两个算法总能耗相差不多，但DMGASE的业务阻塞率低，平均每个业务的能耗就要低一些。DMGAS的平均能耗较低是因为除了采用光旁路和业务量疏导这两个技术外，还采用设备睡眠技术。
图4.2在DMGAS算法中代价设置参数对AEC的影响
图4.2所示，四种参数的DMGAS算法平均能耗趋势均与仿真时钟相似，随着网络负载的增加，平均能耗降低，在网络负载低时下降速度非常快，当网络负载高时平均能耗趋于平稳。在相同负载下，越大，平均能耗越低。平均能耗均降低的主要原因是随着网络负载的增加，处理相同数目的业务所需要的时间越短，消耗的总能耗也就越少。参数越大，就有越多的工作路径和保护路径分别集中，使更多的链路进入睡眠状态。但代价设置参数过高，并没有对能耗有更大的贡献，反而使业务阻塞率增加。的增加能有效的降低网络能耗，但其代价是业务阻塞率增加，并且其增加到一定程度后便失去了对节能的贡献。
五、结论
本文研究了基于ASON的多播专用绿色疏导保护算法，首先设计了辅助图，并将专用多播保护节能问题抽象成数学模型，然后提出了改变链路代价的公式并设计了算法。仿真分析显示，我们所提出的算法不但在阻塞率方面较先前算法有所提高，而且更加节能。
参考文献：
[1]温海波.WDM网状网中的业务量疏导算法研究[D]，电子科技大学，2004.
[2]Idzikowski F， Orlowski S， Raack C， et al. Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios[C]， Conference on Optical Network Design and Modeling （ONDM）， 2010， 1-6.