基于距离自适应和有效共享路径感知的光疏导方法

刘焕淋 岁 蒙 徐一帆 陈 勇 张盛峰



基于距离自适应和有效共享路径感知的光疏导方法

刘焕淋*①岁 蒙①徐一帆①陈 勇②张盛峰①

①(重庆邮电大学光纤通信技术重点实验室 重庆 400065)②(重庆邮电大学自动化学院 重庆 400065)

针对灵活网格光网络中如何节约转发器与频谱资源的问题，该文研究了多点到多点组播业务的光路环路由机制，提出一种基于距离自适应和有效共享路径感知的光疏导方法。通过设计一种基于距离自适应的预处理机制，该疏导方法能根据业务成员节点的分布特点和距离自适应准则灵活地为业务构建光路环；在路由与频谱分配阶段，该疏导方法通过构造一个面向光疏导的业务决策矩阵和一个优先调度向量，将业务疏导到与当前业务具有有效共享路径最多的已路由业务上，并优先分配所需的频谱空间以提高光疏导的成功率，实现节约转发器与频谱资源的目的。仿真结果表明，该文提出的光疏导方法可以有效地减少业务消耗的转发器数目和子载波数目。

灵活网格光网络；光路环；光疏导；共享路径感知

1 引言

随着数字广播、物联网和云计算等多播应用需求的增长，光网络面临着业务流量爆炸式增长所带来的巨大挑战和压力，光网络的转发器资源等也日益紧缺。目前光网络绿色节能的路由传输研究主要集中于波分复用光网络中[4,5]，而基于光正交频分复用的灵活网格光网络(Flexible Grid Optical Networks, FGON)中的研究及成果相对较少，因此FGON网络中实现绿色节能的路由传输是当前的研究热点[6]。在FGON网络中，业务需要频繁地通过转发器调制到不同等级的子载波上，这样便造成了转发器的总能耗巨大，因此减少转发器的使用是实现绿色路由传输的有效手段[7,8]；此外，网络中不同业务间保护频隙的额外频谱开销，造成频谱资源的浪费，也增大了网络能耗[9,10]。因此，如何有效地节约转发器的使用与频谱资源是一个值得研究的问题。

目前，国内外围绕FGON网络中节约转发器与频谱资源的研究已有若干成果：文献[11]基于遗传算法提出了生存性灵活光网络的多目标优化算法，该算法研究了采用高调制等级方式，以及在业务的保护链路上采用转发器共享策略可减少转发器的使用问题。文献[12]针对具有带宽波动的时变业务提出了Mid Fit频谱分配算法，该算法通过最大化相邻业务间的空闲频谱块，选择最大的连续空闲频谱块中居于中间位置的连续频谱来安置业务。从频谱分配的角度分析，该频谱分配算法可以有效地提高光疏导的成功率，实现节约转发器资源和频谱资源的目的，但该算法总是选择使用中间位置的频谱，容易造成过多的频谱碎片。文献[13]提出了距离自适应和频谱碎片感知的光疏导算法来减少网络转发器与频谱资源的使用，算法至少可以节约14%的频谱资源和13%的转发器资源，但是算法在为进行光疏导的业务分配频谱时，没有提出灵活有效的频谱分配策略，受子光路内的频谱连续性和一致性约束，该算法频谱分配的成功率很低，最终制约了算法的性能提升。文献[14]提出了基于最多频隙数优先的光疏导算法来节约转发器资源和频谱资源，但没有综合地考虑频隙数和路径跳数对光疏导算法性能的影响，且提出的算法不适合多播业务的疏导传输。

本文研究了多点到多点组播业务的路由与频谱分配问题。主要针对如何节约转发器与频谱资源的使用问题，本文提出了一种光路环中基于距离自适应和有效路径感知的光疏导算法(Effective Sharing Path-Aware Optical Grooming, ESPA-OG)。该算法主要包含两个部分：(1)基于距离自适应的业务预处理机制，该机制为业务灵活地构建光路环，设计了业务大小的定义式和业务的排序准则；(2)基于有效共享路径感知的光疏导算法，该算法设计了业务的光疏导路由机制和频谱分配机制。在路由阶段，通过构造一个面向光疏导的决策矩阵，选择有效共享路径最多的两个光路环来灵活地进行光疏导；在频谱分配阶段，通过构建一个优先调度向量，为进行光疏导的业务优先分配频谱，进一步优化光疏导算法的性能。

2 基于距离自适应的业务预处理机制

在确定多点到多点组播业务的路由排序准则时，以往的研究主要是由业务占用的带子载波数目决定，而不考虑业务传输路径的物理跳数。受频谱连续性和一致性的约束，这就会造成业务消耗额外的转发器资源和频谱资源。因为业务的物理跳数越多其光疏导成功的概率就越低，而如果能综合考虑业务占用的子载波数目和物理跳数，就可以提高光疏导成功的概率，从而减少转发器与频谱资源的消耗。

基于以上分析，本文提出了光路环中基于距离自适应的预处理机制，在该机制中，设计了业务大小的定义式。定义式的值由光路环占用的子载波数目和物理跳数决定，根据定义值再对业务进行降序排列。距离自适应是当两个节点间最短路径的权重值发生变化后，该机制可重新判断变化后的权重值和不同调制等级下光信号的极限传输距离之间的大小关系，以使业务选择最高的调制等级进行传输。构建光路环的方法及计算业务大小的步骤为：

步骤6 确定整个光路环。在半个光路环中查找光路连接度数为1的两个成员节点和，从子图中删除半个光路环经过的所有中间节点和物理链路，然后在子图上，采用Dijkstra算法计算节点到的最短路径，将此最短路径存入中；

3 基于有效共享路径感知的光疏导算法

目前光网络中，业务的路由选择和频谱分配是NP(Non-deterministic Polynomial)完全问题[18]，启发式算法可以解决大型网络中整数线性规划方法存在的计算时间过长的问题，然而在FGON网络中，现有的节约转发器资源和频谱资源问题的策略都是针对单播业务，还没有针对多点到多点组播业务提出灵活有效的解决方法。在本文提出的光疏导算法中，根据预处理机制为业务构建光路环传输路径，同时对业务进行降序排队。算法按照路由与频谱分配两个阶段来安置业务。

式(6)为算法的优化目标，即最小化网络中业务消耗的转发器数目与子载波数目。其中，为业务成员节点的数目；代表与已路由业务之间有效共享路径中的成员节点个数；为式(5)中计算得到的业务的大小；代表业务与之间有效共享路径经过的链路数目。式(7)中的表示已路由业务的光通道，表示业务疏导在业务上，业务可以与业务之间共享转发器资源，同时这两个业务之间不需要保护频带。式(8)和式(9)表示在满足约束条件下，最大化有效共享路径数目，即尽可能多地共享转发器资源，节约共享路径上的子载波数目。

3.1 ESPA-OG算法的路由机制

ESPA-OG算法中的感知是一个根据业务的光路环之间有效共享路径情况确定业务之间光疏导情况的过程。在寻找能够对当前业务进行光疏导的已路由业务时，当共享链路的两个端节点均不是成员节点，而是光路环的中间节点时，表示该链路为无效共享路径；当共享链路的两个端节点至少有一个是成员节点时，表示该链路为有效共享路径。采用有效路径感知是为了保证算法不会在中间节点进行光疏导，由于在中间节点处进行业务的上下路，会导致消耗额外的转发器资源。

ESPA-OG算法的业务传输路由步骤为：

步骤1 初始化网络链路资源；

步骤2 根据本文的预处理机制计算出的业务的大小，将到达的多点到多点组播业务按业务大小降序插入链表中；

图1 光路环中的光疏导

3.2 ESPA-OG中的频谱分配策略

一般而言，在分配频谱时，为了避免频谱碎片化，算法会将新的业务安置在已占用的频谱位置旁。但是采用光疏导后，如果依然采用这种频谱分配，就会造成频谱分配失败。这是因为光疏导将多个业务疏导到一个转发器中进行传输，也就是将多个子光路聚合为一个“光通道”，为这个光通道中的业务分配频谱时，不仅要满足子光路内的频谱连续性和一致性约束，还要满足子光路间的频谱连续性和一致性约束，子光路间的约束条件使得频谱分配的成功率大大降低。如果我们能够优先为要聚合在一个光通道中的业务分配频谱，就可以解决上述问题。

图2 优先分配策略

步骤1 初始化网络频谱资源；

算法在构建光路环路由业务时，只将业务成员节点集合中的各成员节点按序配对，然后依次计算配对后的成员节点间的最短路径，不再受光路环起点的约束，算法的时间复杂度为，疏导路由感知部分的时间复杂度是，其中为网络中业务数目，为多点到多点组播业务的平均成员节点个数；在频谱分配时，在安置完业务后，便调用业务的优先调度向量，然后为疏导在上的所有业务查询可用的频谱空间，即在安置一个光通道中的业务时，只需要查找一次即可，算法的时间复杂度就为，其中为一个光通道中的平均业务数目，总的时间复杂度为。

4 算法仿真及结果分析

为了验证所提算法的性能，本文对2个经典网络拓扑进行了仿真，即14个节点，21条链路构成的NSFNET网络(如图3)和24个节点，43条链路构成的USNET网络(如图4)，每根光纤可承载的子载波数目为358个，调制等级取值为{1, 2, 3, 4}，一个子载波的带宽容量为，每个节点配备的转发器数目为100，节点的业务带宽可取值为{1, 2, 3, 4, 5, 6}´12.5 Gb/s，每个组播业务的成员节点个数可取值为{2, 3, 4, 5}，与ESPA-OG算法进行对比的算法是FLPC-OG(Frequency LightPath Circle-Optical Grooming)[14]、无光疏导算法(LightPath Circle-No Grooming, LPC-NG)，其中LPC-NG算法采用了本文的预处理机制。仿真统计不同业务数和业务带宽粒度下的转发器使用数目，子载波使用数目等性能指标。

图3 NSFNET网络拓扑图

图4 USNET网络拓扑图

图5和图6分别表示2个网络的转发器使用情况，可以看出，3种算法消耗的转发器数目均随着网络中业务数的增加而增加。但是在相同的业务数下，本文提出的ESPA-OG算法性能最好，FLPC- OG算法次之，LPC-NG算法性能最差，且ESPA-OG算法相比FLPC-OG算法、LPC-NG算法分别有约36%, 70%的转发器节约。这是因为，相比LPC- NG算法，ESPA-OG算法中采用了有效共享路径感知的光疏导机制，使得不同的业务在相同的成员节点处可以共享转发器资源，而LPC-NG算法中没有光疏导机制；相比FLPC-OG算法，ESPA-OG算法的预处理机制综合考虑了子载波数目和物理跳数对光疏导的影响，使得更多的业务可以共享转发器资源。此外，ESPA-OG算法还采用了频谱优先分配策略，提高了业务间光疏导的成功率，从而节约了更多的转发器资源。在相同的业务数下，对比图5和图6可知，LPC-NG算法在USNET网络中消耗的转发器数目较少。这是因为USNET网络较大，当业务的成员节点数目较多时，网络中可能不存在链路代价最小的光路环，所以，在相同的业务总数下，USNET网络中传输成功的业务的平均成员节点数目较少，从而消耗的转发器就较少。然而，ESPA-OG算法和FLPC-OG算法在NSFNET网络中的性能较优，这是因为NSFNET网络中业务的平均物理跳数较少，受频谱连续性和一致性的约束小，业务光疏导成功的概率较大。

图5 NSFNET网络中业务数与消耗的转发器数目的关系

图6 USNET网络中业务数与消耗的转发器数目的关系

图7和图8分别表示2个网络的频谱使用情况，可以看出，在相同的业务数下，本文提出的ESPA- OG算法性能最优，且ESPA-OG算法相比FLPC- OG算法、LPC-NG算法分别有约11%, 37%的频谱节约。相比LPC-NG算法，ESPA-OG算法中采用了有效共享路径感知的光疏导机制，节约了不同业务在有效共享链路上的保护带，而LPC-NG算法中没有光疏导机制，业务间保护带会额外消耗网络频谱资源。相比FLPC-OG算法，ESPA-OG算法的预处理机制提高了业务间光疏导共享的链路数目，从而节约了更多的频谱资源；而且，ESPA-OG算法的频谱优先分配机制可以优先为参与疏导的业务分配频谱，提高了光疏导在频谱分配时的成功率。对比图7和图8可知，在相同的业务数下，3种算法在USNET网络中消耗的子载波数目都比在NSFNET网络中消耗的数目多，这是因为USNET网络较大，业务的平均路由跳数较多，业务间保护带所占用的总子载波数目就多。

图7 NSFNET网络中业务数与消耗的子载波数目的关系

图8 USNET网络中业务数与消耗的子载波数目的关系

图9和图10分析了节点的业务带宽粒度与网络消耗的频谱资源的情况。可以看出，当节点的业务带宽粒度从1´12.5 Gb/s增大到6´12.5 Gb/s(75 Gb/s)时，无论在NSFNET网络还是在USNET网络中，ESPA-OG算法性能均优于其他两种算法。随着业务带宽粒度的增加，3种算法消耗的子载波数目都明显增加。且与图7和图8相比，ESPA-OG算法和FLPC-OG算法的曲线上升幅度更加明显。因为对于这两种算法来说，随着网络中业务总数的增多，进行光疏导的业务数就增多，节约的频谱资源就增多，故网络频谱总消耗数目的上升趋势就不明显；但是随着业务粒度的增加，在相同的调制等级下，业务占用的子载波数目就明显增加，光疏导节约的频谱资源远不及业务粒度的增加所消耗的频谱资源，故网络频谱总消耗数目的上升趋势很明显。

图9 NSFNET网络中业务带宽与消耗的子载波数目的关系

图10 USNET网络中业务带宽与消耗的子载波数目的关系

5 结束语

本文研究了灵活网格光网络中多点到多点组播业务的转发器与频谱资源优化问题，提出了一种光路环中基于距离自适应和有效共享路径感知的光疏导方法，通过设计一种基于距离自适应的预处理机制，使得该疏导方法可根据业务成员节点的分布特点和距离自适应准则灵活地为业务构建光路环。在为业务进行路由时，该疏导方法构建了面向光疏导的决策矩阵，为业务选择有效共享路径最多的已路由业务进行光疏导，从而减少转发器与频谱资源的使用；为了增加光疏导后的频谱分配成功率，该疏导方法还构建了优先调度向量，为进行光疏导的业务优先分配合适的频谱空间。仿真结果验证了本文算法可以很大程度上节约转发器与频谱资源的使用。对于未来工作，可以通过优化灵活网格光网络的能耗模型和光疏导策略，来进一步节约资源消耗。

参考文献

[1] Pagès A, Perelló J, Spadaro S,.. Optimal route, spectrum, and modulation level assignment in split-spectrum-enabled dynamic elastic optical networks[J]., 2014, 6(2): 114-126.

[2] Wang Yang, Cao Xiao-jun, Hu Qian,.. Towards elastic and fine-granular bandwidth allocation in spectrum-sliced optical networks[J]., 2012, 4(11): 906-917.

[3] 刘焕淋, 方强, 雷芳. WDM光网络中多播业务量疏导方法分析[J]. 重庆邮电大学学报(自然科学版), 2012, 24(3): 269-277.

Liu Huan-lin, Fang Qiang, and Lei Fang. Analysis of multicast traffic grooming algorithms in WDM mesh networks[J].(), 2012, 24(3): 269-277.

[4] Guo Lei, Hou Wei-gang, Wei Xue-tao,.. Power efficient grooming based on optical bypass reconfiguration in green optical networks[J]., 2013, 124(5): 437-445.

[5] 刘焕淋, 刘洋, 陈勇, 等. WDM 光网络中带宽预留型业务的时间感知绿色疏导算法[J]. 北京邮电大学学报, 2014, 37(5): 71-74.

Liu Huan-lin, Liu Yang, Chen Yong,.. Time-aware green grooming algorithm for scheduled traffic in WDM networks[J]., 2014, 37(5): 71-74.

[6] Fallahpour A, Beyranvand H, Nezamalhosseini S A,.. Energy efficient routing and spectrum assignment with regenerator placement in elastic optical networks[J]., 2014, 32(10): 2019-2027.

[7] El-Gorashi T E H, Dong X, and Elmirghani J M H. Green optical orthogonal frequency-division multiplexing networks [J]., 2014, 8(3): 137-148.

[8] Christodoulopoulos K, Tomkos I, and Varvarigos E A. Elastic bandwidth allocation in flexible OFDM-based optical networks[J]., 2011, 29(9): 1354-1366.

[9] Zhang Shu-qiang, Martel C, and Mukherjee B. Dynamic traffic grooming in elastic optical networks[J]., 2013, 31(1): 4-12.

[10] 吴凡, 毛玉明, 黄晓燕, 等. OFDMA 系统中最优能效功率分配[J]. 电子与信息学报, 2014, 36(7): 1673-1679.

Wu Fan, Mao Yu-ming, Huang Xiao-yan,.. Optimal energy-efficient power allocation in OFDMA system[J].&, 2014, 36(7): 1673-1679.

[11] Eira A, Santos J, Pedro J,.. Multi-objective design of survivable flexible-grid DWDM networks[J]., 2014, 6(3): 326-339.

[12] Khodashenas P S, Comellas J, Spadaro S,.. Using spectrum fragmentation to better allocate time-varying connections in elastic optical networks[J]., 2014, 6(5): 433-440.

[13] Ye Z, Patel A N, Ji P N,.. Distance-adaptive and fragmentation-aware optical traffic grooming in flexible grid optical networks[C]. Proceedings of OptoElectronics and Communication Conference and Australian Conference on Optical Fiber Technology (OECC/ACOFT), Melbourne, 2014: 355-356.

[14] Xu Zhan-qi, Wang Jing, Xu Bo,.. Modelling and heuristic algorithms for routing and spectrum assignment in elastic optical networks[J]., 2014, 43(7): 0706004-1-0706004-5.

[15] Saleh M A and Kamal A E. Many-to-many traffic grooming in WDM networks[J]., 2009, 1(5): 376-391.

[16] Saleh M A and Kamal A E. Design and provisioning of WDM networks with many-to-many traffic grooming[J]./, 2010, 18(6): 1869-1882.

[17] Guo Lei, Hou Wei-gang, Zheng Ze-yu,.. Green provisioning of many-to-many sessions over WDM optical networks[J]., 2013, 31(20): 3289-3301.

[18] Shachnai H, Voloshin A, and Zaks S. Optimizing bandwidth allocation in flex-grid optical networks with application to scheduling[C]. Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), Phoenix, 2014: 862-871.

Method of Optical Grooming for Distance-adaptive and Effective Sharing Path-aware

Liu Huan-lin①Sui Meng①Xu Yi-fan①Chen Yong②Zhang Sheng-feng①

①(,,400065,)②(,,400065,)

In order to address the problem of reducing the resources of transponder and spectrum in flexible grid optical networks, a lightpath circle mechanism is studied for many-to-many multicast requests, and a method of optical grooming is proposed based on distance-adaptive and effective sharing path-aware. By designing a strategy of traffic pre-processing based on distance-adaptive, a lightpath circle is constructed according to the distribution characteristics of member nodes and the distance-adaptive criterion in the proposed method. In the process of routing and spectrum allocation, by constructing a decision matrix oriented optical grooming and a priority scheduling vector, the multicast request is groomed into the established traffic with the highest effective sharing links. Moreover, the appropriate spectrum resources are allocated for the groomed requests to increase the success rates of grooming and to save the resources of transponder and spectrum. Simulation results show that the proposed method can significantly reduce the number of traffic consumed transponders and sub-carriers.

Flexible grid optical networks; Lightpath circle; Optical traffic grooming; Sharing path-aware

TN929.11

A

1009-5896(2015)08-1964-07

10.11999/JEIT141442

刘焕淋 liuhl2@sina.com

2014-11-20收到，2015-04-15改回，2015-06-09网络优先出版

重庆市教委自然科学基金(KJ1140421)，重庆市科委自然基金(2013jcyjA40052, 2011jjA1361)和国家自然科学基金(61275077, 61371096)资助课题

刘焕淋： 女，1970年生，教授，研究方向为光通信技术与未来网络.

岁 蒙： 女，1988年生，硕士生，研究方向为光组播路由及频谱分配算法.

徐一帆： 男，1990年生，硕士生，研究方向为绿色光网络路由算法.