基于弹性光网络的多播业务保护算法

吴菁晶，张建芳



基于弹性光网络的多播业务保护算法

吴菁晶，张建芳

（东北大学计算机科学与工程学院，辽宁 沈阳 110819）

随着网络中业务量的急剧增长以及宽带业务的普及，传统的波分复用光网络由于灵活性差、频谱资源浪费严重而面临严峻挑战。弹性光网络以灵活利用频谱为特征，可以根据用户需要和业务量大小动态分配适量的频谱资源并配置相应的调制格式，有效克服了波分复用光网络的缺陷。同时，弹性光网络中的多播路由和频谱分配以及网络的生存性问题也变得更加复杂。针对弹性光网络中多播路由和保护算法进行了研究，首先引入整数线性规划模型（ILP, integer linear programming），最大限度地利用网络中的频谱资源。在此基础上，提出了启发式算法——基于多播子树的分段路由频谱分配保护算法（MSPA, multicast sub-tree protection algorithm），为多播业务请求提供保护的同时最小化频谱资源的使用。仿真结果表明，与传统的多播路由算法及多播保护算法相比，所提算法通过改变信号调制格式，灵活运用链路上的频谱碎片，可以降低网络的阻塞率，提高网络的频谱利用率。

弹性光网络；网络生存性；多播；路由

1 引言

随着互联网的急速发展，如何提高频谱利用率成为一个热门的研究课题。尽管传统的波分复用（WDM, wavelength division multiplexing）网络在高速传输方面有很多优势，但WDM网络的缺点也比较明显。WDM网络是固定带宽粒度，对于各种带宽需求的业务连接请求，WDM网络需要将整个波长的带宽都分配给该业务，即便有的业务连接请求并不需要如此大的带宽，因此造成了在WDM网络中频谱利用率降低的缺点。此外，波分复用的效率较低也造成了业务连接请求的可扩展性降低。因此，基于正交频分复用（OFDM, orthogonal frequency division multiplexing）的弹性光网络应运而生[1-3]。

弹性光网络提供了更细的频谱粒度和距离自适应调制格式，可以实现频谱的有效分配。随着光网络向灵活栅格方向发展，网络资源的实体由波长向频谱转变，使资源管理与调控问题的复杂性提高，路由计算和频谱资源的分配策略变得复杂多样。同时，与传统的点到点通信方式相比，多播传输不仅节省了大量的网络带宽，还提高了效率。多播传输是一种有效利用现有带宽的技术，因此对多播技术的相关研究有非常大的意义。

对于弹性光网络，人们不仅要关注有效性和可扩展性，网络的生存性也至关重要。网络生存性是指网络在受到各种故障（如链路、节点等失效）后能够维持可接受的连接质量的能力，因为任何链路的失效都会导致大量数据的丢失，当在光网络中建立光通道时，同时也需要建立链路不相交或者节点不相交的保护链路。随着多播技术的快速发展，光网络的多播路由及多播生存性问题成为研究的热点。多播业务的路由和保护算法也越来越受到业界学者的重视。

为了更好地解决频谱利用及网络阻塞问题，本文将关注点放在路由及频谱资源的分配调度上，采用多播子树算法解决频谱资源有限时利用足够光收发器解决多播业务请求阻塞以及频谱的利用率问题，采用基于分段的多播保护算法为多播业务请求提供保护，当网络发生故障时，可以快速为多播业务请求提供保护，使业务连接请求得以快速恢复。

2 相关工作

目前，已有很多文献研究了光网络中的保护问题。文献[4]将粗细粒度路由结合，主要研究了两方面内容，分别是将共享保护应用于粗、细粒度和对这2种不同共享保护方案形成静态网络设计算法。文献[5]主要研究了光物理层受到侵害时光网络的生存性问题，文章回顾了光网络容易受到侵害的类型并讨论了几个保护算法以提高网络的安全性。文献[6]首先针对被单一链路失效影响到的链路分组，提出分组工作路径保护，目标是建立组内链路不相交的工作路径和备份路径，首先为工作路径和备份路径的路由和波长分配提供两步法整数线性规划模型，然后提出启发式算法应用到大型网络。

近些年，由于弹性光网络可变颗粒度能提高网络的灵活性，弹性光网络中生存性问题得到广泛关注和应用。文献[7]对IP-over-EON提出多层生存性问题，应用整数线性规划模型给出最优解，然后提出多层概念提高网络疏导能力，对于特定的失效状态，不仅可以共享备份资源，还可以使工作路径和备份路径共享资源。文献[8]为共享保护提出整数线性规划模型，该算法能最大化网络吞吐量，最小化资源的使用，此外，还研究了单播的共享保护算法。文献[9]提出了基于频谱窗平面的有效启发式算法并且应用距离和调制格式自适应的路由和频谱分配来最大化共享保护路径的空闲容量。文献[10]提出自适应生存性方法实现保护路径有效性和路由花费的最佳权衡，此外，还提出新颖的路由、频谱和调制格式的分配算法最优化业务。

多播是一种有效利用现有带宽的技术，不仅可以高效率地传输业务，也可以节省频谱资源。文献[11]研究了弹性光网络中多种动态多播业务的保护策略，还对比了不同的多播保护方案。文献[12]研究了弹性光网络单链路失效前提下的多播保护问题，提出了2种基于分段的保护算法，2种算法在阻塞率和资源利用率性能方面有很大提升。文献[13]采用距离自适应频谱资源分配，目标是使用最少的频谱资源分配所有的多播请求，提出混合整数线性规划模型，采用可扩展升级的启发式算法改善运行时间长的缺点。文献[14]研究了光网络中多播保护问题，基于p-Cycle提出启发式算法，该算法将网络拓扑分解为一系列p-Cycle，为环上链路和跨接链路提供保护。

3 问题描述

目前，已有研究人员开始了对弹性光网络中多播业务保护问题的研究与探讨，但弹性光网络中的生存性研究仍存在着很多问题。首先，全光多播通常采用单一光树来服务多播业务请求；其次，多播业务请求不仅有工作频谱资源请求，还有保护频谱资源请求，而在资源分配过程中可能造成资源使用不平衡。因此，本文首先描述了弹性光网络中多播保护问题的数学模型，在此基础上，设计了针对动态业务请求的启发式算法。

3.1 整数线性规划模型

算法中用到的参数和变量定义如下。

：物理节点集合。

：物理光纤链路集合。

：多播业务请求集合。

：每条物理链路上连续子载波的集合。

对于静态业务请求，在完成对多播业务保护的同时还要提高网络频谱资源利用率，因此优化目标是当为所有业务请求提供服务后，最小化所有物理链路上使用的最大频谱分片数目。

目标函数定义为

约束条件为

3.2 多播子树

传统的多播路由和频谱分配问题通常采用全光多播距离自适应频谱分配应对大带宽业务，通常为多播业务请求建立单一光树，在这种方案中，调制格式的选择至关重要，源节点到每一个相关联的目的节点的距离是不同的，单一光树的调制格式是由距离最远的源—目的节点距离决定的。正是由于单一大型光树的限制，调制格式等级降低，需求的频谱容量增加，造成了频谱资源浪费及业务请求阻塞。频谱碎片的问题更是给这种方案造成了很大的困难。由此，本节提出多播子树路由算法，该算法的核心思想是将多播的目的节点分组，将大型单一光树分成若干个子树，每个子树可以根据子树当前频谱状态选择合适的调制格式。子树的形成方式可以分为以下2类：1) 源节点为光树分裂点，如图1所示；2) 中间节点为光树分裂点，如图2所示。

假设弹性光网络中每个节点都具有全光多播能力和足够数量的光收发器。考虑4种调制格式BPSK、QPSK、8QAM、16QAM，分别对应4种不同的透明传输距离，对应的最大传输距离分别为8 000 km、4 000 km、2 000 km、1 000 km，每个频谱分片的带宽为12.5 GHz，分别携带25 Gbit/s、50 Gbit/s、75 Gbit/s、100 Gbit/s的容量，然后分配一个额外的频谱分片作为保护带宽。

图1 源节点为光树分裂点

图2 中间节点为光树分裂点

图2展示了一个多播子树路由算法采取方式2)，即以中间节点为光树分裂点的子树形成方式。图2(a)展示了频谱使用现状（假设每条链路上有7个频谱分片）。一个同样的多播业务请求到达，源节点为A，目的节点分别为B、F、G，对于单一光树方案，由于合适的调制格式是由最远距离决定的，最远的距离是A—C—E—G，总距离为2 100 km，可用的最高调制格式为QPSK，需要5个频谱分片来满足该多播业务请求。但是链路A—B的频谱分片6、7已经被占用，所以没有足够的频谱分片来满足该多播业务请求需要的频谱分片（频谱一致性限制），所以该多播业务请求被阻塞。如图2(b)所示，对比于单一光树方案，多播子树路由算法采取方式1)以源节点为光树分裂点将多播业务请求分解为2个子树，子树1包含目的节点B，子树2包含目的节点F、G。根据每个子树的传播距离，子树1的最远距离为900 km，合适的调制格式为16QAM，需要3个频谱分片（1~3），子树2的最远距离为2 100 km，合适的调制格式为QPSK，需要5个频谱分片（3~7），但是，此时只有A—C的空闲频谱满足，C—G和C—F的频谱被占用，所以只采用方式1)，也无法满足多播业务请求，此时采取方式2)，以中间节点为光树分裂点的分子树形成方式来完成多播业务请求。如图2(c)将节点C作为新的源节点，在中间节点C处再形成子树，该子树最远的路径C—E—G，距离为1 200 km，合适的调制格式为8QAM，需要4个频谱分片（4~7）。由此，在中间节点C处形成子树使该多播业务请求得以实现。该方案不仅成功分配了多播业务请求，还节省了频谱资源，但是，该方案需要更多的光收发器。

4 启发式算法

弹性光网络中多播业务保护的路由和频谱分配问题是一个NP-hard问题[15]。为解决此问题，本节提出了基于多播子树的分段路由频谱分配保护机制（MSPA, multicast sub-tree protection algorithm）以改善频谱利用。该算法的核心思想是：首先，在多播业务请求到达以前，更新每条链路的可用频谱资源；然后，找到最佳路径建立工作路径，当多播业务请求到达弹性光网络时，网络的控制平面找到可用路径并且分配足够的频谱资源，计算源到目的节点的最短路径作为多播树干，接着在多播树干基础上对剩余节点进行连接并分配资源；最后，决定调制格式和保护方案，当多播树能够成功分配频谱资源，则直接为多播树提供保护；当频谱资源短缺，则先将多播树分成多播子树，再为每个子树分段提供保护，从而得到弹性光网络多播树保护的路由和频谱分配的解决方案。

4.1 多播树的建立

在弹性光网络中需要满足以下3个限制：频谱一致性、频谱连续性和频谱非重叠。换句话说，选定的频谱分片需要在端到端的光路上传输。如果频谱分片已经分配给现存的多播业务请求，则该分片不能再分配给其他多播业务请求。需要注意的是，不同的调制格式有不同的传输距离和频谱效率，因此，所需要设计的路由和频谱分配算法必须同时选择路径和调制格式。

为了详尽地描述该算法，以图3为例进行说明，在每个多播业务请求到达以前，更新每条链路的可用频谱资源，计算源到目的节点的主干多播树，建立连接。在多播树干基础上对剩余节点进行连接并分配资源，决定调制格式和放置光收发器，最后需要为已经建立的多播树或多播树分段计算保护路径。

图3 多播树的建立

4.2 多播树及多播子树的保护机制

为了对业务连接请求提供100%的保护，需要确保保护路径不能与其工作树相交。对于多播请求，若频谱资源充足，能够为该单一多播树成功分配频谱资源，只需为之前创建的多播工作树计算链路分离的保护路径即可。如图4(a)所示，为了创建链路分离的多播树，将工作路径从拓扑图中移除。本节提出的算法在选择保护路径时，优先选择共享链路最多的路径作为保护路径。从拓扑图中可以看出，保护路径为A—B—G—I—J。若频谱资源短缺，为了成功为多播业务选路并为其提供保护，采用基于多播子树的分段路由频谱分配保护机制为多播业务提供保护。假设该多播树分为子树1和子树2（如图3(c)所示），为子树1提供的保护路径为A—B—G—I，为子树2提供的保护路径为A—C—F—J，如图4(b)所示。此时，保护路径的计算是独立的，因此，从原始源节点A开始为目的节点J寻找保护路径。

4.3 MSPA具体流程

输出 弹性光网络中多播业务请求的工作路径和保护路径以及它们的频谱分配

步骤1 检测并更新当前网络频谱资源使用状态。

步骤2 等待网络中业务连接请求到达。如果业务连接请求是建立一个新的连接，转到步骤3；如果业务连接请求是释放一个旧的连接，转到步骤13。

步骤3 为业务连接请求计算并比较每一对源—目的节点的距离（如距离相同则随机选择一个），将距离最小的源—目的节点对所经过的链路作为多播树主干。

步骤4 在多播树主干基础上对剩余目的节点进行连接，剩余目的节点需要遵循到多播树干的距离最短。

步骤5 多播树选取完毕后根据当前网络频谱资源判断该多播请求是否成功分配，若成功分配，则根据最远传输距离为多播树决定调制格式并转到步骤6；若失败，转到步骤10。

步骤6 为工作通路分配资源，采用首次命中算法为工作路径分配频谱资源。

步骤7 将工作通路从网络拓扑移除，为连接请求计算保护通路。

步骤8 工作通路移除后为业务连接请求的源—目的节点计算保护通路，找到一棵源节点到所有目的节点的最小生成树为工作通路提供保护。

步骤9 为保护通路分配资源，采用首次命中算法为保护路径分配频谱资源，并输出工作路径和保护路径以及各自的频谱资源分配，转到步骤2。

步骤10 若多播树计算失败，根据多播子树路由算法将多播树分解为若干子树。

步骤11 为每个子树分段分配资源。

步骤12 将子树分段通路从拓扑中移除，分别为每个子树计算各自的保护通路，采用首次命中算法为保护路径分配频谱资源，转到步骤2。

步骤13 当释放连接请求到达时，释放业务连接请求所占资源，释放该请求所使用工作和保护通道的剩余频谱资源，转到步骤2。

5 仿真与性能评价

5.1 仿真参数

5.2 实验结果及分析

实验首先在14个节点21条链路的NSFNET网络拓扑上测试了MSPA和MLPA在业务阻塞率指标上的性能，如图6所示。从图6可以看出，MSPA和MLPA的业务阻塞率都是随着业务请求数量的增加而增加的。当网络负载为90 Erlang（爱尔兰）时，2种算法的业务阻塞率都较低，接近2%；当网络负载增加到240 Erlang时，2种算法的阻塞率都随负载的增加而提高，这是因为随着更多多播业务请求的到达，网络中没有足够的空闲频谱资源提供给后续到达的多播业务请求。但是MLPA在负载为240 Erlang时，阻塞率接近15%，而MSPA在负载为240 Erlang时，阻塞率仅接近5%，在同等条件下可以看出，MSPA可以显著降低业务阻塞率，这是因为MSPA可以将大型多播树分解为若干子树，当单一多播工作树业务阻塞时，可以通过小型多播子树承载业务请求，显著降低业务阻塞率。

图7展示了MSPA和MLPA在不同的网络负载下频谱利用率的比较，本节频谱利用率定义为网络中消耗的频谱与总频谱的比值。随着网络负载的增加，MSPA和MLPA的频谱利用率总体都呈缓慢增加趋势，这是因为多播请求增加意味着需要更多的频谱资源承载多播业务，而总的频谱资源是一定的。在同等条件下，MSPA的频谱利用率高于MLPA，这是因为MLPA不能满足频谱一致性限制，所以更多的业务被阻塞，频谱利用率低。而MSPA利用分子树的方法打破频谱一致性的限制，使更多的多播业务请求成功选路，提高了频谱利用率。

图5 仿真网络拓扑

图6 在不同的网络负载下，NSFNET网络中MSPA和MLPA平均业务阻塞率的比较

图7 在不同的网络负载下，NSFNET网络中MSPA和MLPA频谱利用率的比较

实验对比了MSPA和MLPA需要的光收发器的数目，如图8所示。为了确保没有业务阻塞，实验降低了到达业务请求的总数量，因为被阻塞的业务不消耗光收发器。随着多播请求业务的增加，MSPA和MLPA消耗的光收发器总数也随之增加。从图8可以看出，在同等条件下，MSPA消耗的光收发器总数比MLPA多，这是因为MSPA将单一的多播业务分解为多个子树，也就是说，将大型的单一业务分解为多个子业务来满足多播请求，所以MSPA会耗费更多的光收发器。

图8 在不同的网络负载下，NSFNET网络中MSPA和MLPA消耗光收发器数目的比较

考虑到预算及性价比，MSPA若应用在全部类型的网络则会大大地增加网络成本，所以该算法主要应用于以下2种场景以达到成本优化。

1) 网状型网络，且网络复杂，网络中每个节点的度（连接密集处）较大。虽然增加了成本，但是可以有效降低网络阻塞率，同时提高频谱利用率。

2) 服务质量等级（QoS）高。不同的群体，不同的用户，对业务传输的顺畅度、速度、受损恢复时间要求也是不同的，当用户需要高服务质量等级时，MSPA便可以实现低阻塞、快恢复的优势。虽然大量光收发器耗费网络成本，但是满足了用户的特殊需求，实现了成本优化。

图9~图11是在24个节点43条链路的USNET网络拓扑上的实验结果。尽管USNET有更大的拓扑尺寸、更多的网络节点和链路数目，但是仿真结果和关键观测结果相似。

图9 在不同的网络负载下，USNET网络中MSPA和 MLPA平均阻塞率的比较

图10 在不同的网络负载下，USNET网络中MSPA和 MLPA频谱利用率的比较

图11 在不同的网络负载下，USNET网络中MSPA和 MLPA消耗光收发器数目的比较

6 结束语

本文针对弹性光网络中的多播路由保护算法进行了研究。为了更好地解决频谱利用及网络阻塞问题，本文将关注点放在路由及频谱资源的分配调度上，采用多播子树算法解决频谱资源有限时利用足够光收发器解决多播业务请求阻塞率以及频谱利用率问题，采用基于分段的多播保护算法为多播业务请求提供保护，当网络发生故障时，可以快速为多播业务请求提供保护。仿真实验结果表明，与传统的多播路由算法及多播保护算法相比，所提算法通过改变信号调制格式、灵活运用链路上的频谱碎片，可以降低网络的阻塞率，提高网络的频谱利用率。

[1] SHIEH W. OFDM for adaptive ultra high-speed optical networks[C]// 2010 Conference on Optical Fiber Communication (OFC). 2010: 1-51.

[2] SZCZESNIAK I, GOLA A, JAJSZCZYK A, et al. Itinerant routing in elastic optical networks[J]. Journal of Lightwave Technology, 2017, 35(10): 1868-1857.

[3] HADI M, PAKRAVAN M R. Spectrum-convertible BVWXC placement in OFDM-based elastic optical networks[J]. IEEE Photonics Journal, 2017, 9(1): 1-12.

[4] ISHIKAWA T, MORI Y, HASEGAWA H, et al. Spectral efficiency maximization of grouped routing optical networks with shared protection[J]. IEEE/OSA Journal of Optical Communications and Networking, 2017, 9(10): 864-875.

[5] DAHAN D, MAHLAB U. Security threats and protection procedures for optical networks[J]. IET Optoelectronics, 2017, 11(5): 186-200.

[6] FURDEK M, SKORIN-KAPOV N, WOSINSKA L. Attack-aware dedicated path protection in optical networks[J]. Journal of Lightwave Technology, 2016, 34(4): 1050-1061.

[7] PAPANIKOLAOU P, CHRISTODOULOPOULOS K, VARVARIGOS E. Joint multi-layer survivability techniques for IP-over-elastic- optical-networks[J]. IEEE/OSA Journal of Optical Communications and Networking, 2017, 9(1): 85-98.

[8] XU R, CHEN B, DAI M, et al. Disaster survivability in elastic optical datacenter networks[C]// 2016 IEEE Optoelectronics Global Conference (OGC). 2016: 1-3.

[9] WANG C, SHEN G, BOSE S K. Distance adaptive dynamic routing and spectrum allocation in elastic optical networks with shared backup path protection[J]. Journal of Lightwave Technology, 2015, 33(14): 2955-2964.

[10] AIBIN M, WALKOWIAK K, SEN A. Software-defined adaptive survivability for elastic optical networks[J]. Optical Switching and Networking, 2016, 23(2): 85-96.

[11] AIBIN M, WALKOWIAK K. Different strategies for dynamic multicast traffic protection in elastic optical networks[C]// International Workshop on Resilient Networks Design and Modeling(RNDM). 2016: 174-180.

[12] DIN D, LAI I. Multicast protection problem on elastic optical networks using segment-base protection[C]// International Conference on Informatics, Electronics & Vision(ICIEV). 2015: 1-6.

[13] CAI A, GUO J, LIN R, et al. Multicast routing and distance-adaptive spectrum allocation in elastic optical networks with shared protection[J]. Journal of Lightwave Technology, 2016, 34(17): 4076-4088.

[14] PANAYIOTOU T, ELLINAS G, ANTONIADES N. P-cycle-based protection of multicast connections in metropolitan area optical networks with physical layer impairments constraints[J]. Optical Switching and Networking, 2016, 19(2): 66-77.

[15] FAN Z, LI Y, SHEN G, et al. Distance-adaptive spectrum resource allocation using subtree scheme for all-optical multicasting in elastic optical networks[J]. Journal of Lightwave Technology, 2017, 35(9): 1460-1468.

[16] AHUJA S S, RAMASUBRAMANIAN S, KRUNZ M. Single-link failure detection in all-optical networks using monitoring cycles and paths[J]. IEEE/ACM Transactions on Networking, 2009, 17(4): 1080-1093.

Multicast service protection algorithm based on elastic optical network

WU Jingjing, ZHANG Jianfang

School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China

With the rapid growth of the network traffic, the elastic optical network (EON) has been proposed as a promising solution due to its high spectrum efficiency and flexible bandwidth provision. Meanwhile, multicast routing and spectrum allocation, and the survivability of the network become more challenging than that in the conventional optical network. The routing for multicast traffic and its protection algorithm in EON was investigated. An integer linear programming (ILP) formulation with the objective to minimize total spectrum consumption was presented. In addition, a heuristic algorithm called multicast sub-tree protection algorithm (MSPA) to achieve sufficient protection and satisfy resources savings was designed. The simulation results demonstrate that comparing with the traditional multicast routing and protection algorithm, MSPA performs well in improving the blocking probability and the spectrum utilization of the network.

elastic optical network, network survivability, multicast, routing

TN915

A

10.11959/j.issn.1000−436x.2019061

2018−04−03；

2018−08−20

国家重点研发计划基金资助项目（No.2017YFB0306400）；国家自然科学基金资助项目（No.61501105, No.61871107）；中央高校基本科研业务费专项资金资助项目（No.N171612014）

The National Key R&D Program of China (No.2017YFB0306400), The National Natural Science Foundation of China (No.61501105, No.61871107), The Central University Basic Business Expenses Special Funding for Scientific Research Project (No.N171612014)

吴菁晶（1981-），女，辽宁沈阳人，博士，东北大学副教授，主要研究方向为光传送网、网络安全等。

张建芳（1992- ），女，河北宣化人，东北大学硕士生，主要研究方向为多播保护、网络生存性。