基于OFDM的弹性光网络中RSA问题综述

◆邱 伟

基于OFDM的弹性光网络中RSA问题综述

◆邱 伟

（南京邮电大学电子与光学工程学院 江苏 210023）

基于OFDM的弹性光网络因为具有更高的频谱效率、更大的灵活性和可扩展性而成为极具潜力的下一代光网络，本文对弹性光网络中路由和频谱分配问题从概念，分类，以及目前的研究成果等进行综述，并提出未来的发展方向。

弹性光网络；路由；频谱分配；智能算法

随着大数据、云计算以及移动通信的快速发展，涌现出了一大批的高流量型在线应用和APP，比如直播平台，购物网站，短视频应用等等。这些高流量型应用的背后需要巨大的带宽支撑，作为传输层主要承载方式的光网络将面临巨大的挑战。传统的波分复用光网络（Wavelength division multiplexing，简称WDM）采用固定栅格的频谱分配方式，对于带宽需求远小于一个栅格带宽的业务，仍然需要分配一个栅格的频谱资源，造成了频谱资源的浪费[1]。为了满足未来互联网和通信的发展需求，光网络需要具备更高的频谱效率，更大的灵活性和可扩展性。因此，采用OFDM技术的弹性光网络（Elastic optical networks，简称EONs）被学者提出[2]。OFDM属于多载波调制技术的一种，可以将高速率的数据流均分成低速率的数据流并行的在子信道上进行传输，而因为子载波的正交性，相邻的子载波可以相互重叠。基于OFDM的弹性光网络可以实现更细粒度的频谱划分，提供灵活的频谱分配来满足所请求的带宽需求，此外还可以分配多个相邻的子载波用以组成超级信道，实现较高速率的传输。路由和频谱分配（Routing and spectrum allocation，简称RSA）问题是EONs中重要的研究点之一。本文将对EONs中RSA问题进行介绍，并分析阐述实现RSA的各种方法，最后对RSA问题的发展方向做出预测。

1 RSA的基本概念

EONs中RSA是指根据业务请求在源节点和目标节点之间找到一条合适路径，并根据最大化利用频谱资源原则分配合适的频谱资源以建立连接。RSA问题和传统的WDM光网络中RWA问题类似，在WDM光网络中，RWA是指在网络中通过选择路由和分配波长资源为连接请求建立光路，在建立光路时需满足波长一致性要求[3]。RSA与RWA不同，RSA计算需要同时满足频谱连续性约束和频谱邻接性约束[4]。这两个约束条件使得RWA计算方法不能直接运用于RSA计算，RSA计算将更复杂。频谱连续性约束是指经过光路的每一条链路都应该分配相同的频谱资源。频谱邻接性约束是指在光路径频谱轴上要占用连续的频隙。我们通过一个示例来解释这两个约束。如图1，我们需要建立一条从节点1到节点3的光路，并且业务带宽需要3个频隙。图中灰色代表频隙已被占用，白色代表频隙未被占用。我们可以使用链路2进行路由，但是发现链路2上没有连续的3个频隙可以分配，即频谱邻接性约束条件不满足，因此不能选择链路2进行路由。可以选择从节点1到节点2，再到节点3这样的方式进行路由，链路1和链路3有三个连续的可用频隙，即频隙3，频隙4和频隙5（满足频谱邻接性约束），且链路1和链路3上这三个连续的频隙是“对齐”的（满足频谱连续性约束），因此，可以采用链路1和链路3进行路由和频谱分配。

图1 频谱连续性约束和频谱邻接性约束示例

RSA问题已经被证实是一个NP-hard问题[5]，在多项式时间内找不到最优解。尽管RSA问题是一个比较难的问题，但是我们可以将问题简化成两个子问题，即路由子问题和频谱分配子问题。下面将对这两个子问题进行介绍。

2 路由和频谱分配子问题

2.1 路由选择

路由选择是为源节点和目的节点之间选择一条路径进行信息的传输。常见的路由选择方法有以下4种[6]：

（1）固定路由（Fixed Routing，简称FR）：在FR中，使用最短路径算法（比如Dijkstra算法，Bellman-Ford算法）为每个源节点和目的节点对预先计算单个固定路由。当连接请求到达网络时，该算法尝试沿固定路径建立光路。它检查所需的频隙是否在预定的路由的每个链路上可用。如果在链路上没有发现可用的频隙，则阻塞该连接请求。FR算法计算简单，复杂度低，但是由于不灵活，在动态场景下网络的阻塞率较高。

（2）固定备选路由（Fixed Alternate Routing，简称FAR）：FAR是FR的升级版本，在FAR中，网络中的每个节点都为所有其他节点维护一张路由表，路由表中包含了具有优先级顺序的固定路由，比如以路径长度作为优先级指标分为最短路径、次最短路径等。当具有给定源节点和目的节点的连接请求到达时，源节点尝试通过顺序获取路由表中的每个路由建立光路，直到找到能满足频隙要求的路由。如果在备用路由列表中找不到所需频隙的可用路由，则阻塞该连接请求。该算法的复杂度高于FR，但是和FR相比，可以降低网络的阻塞率。

（3）最少拥塞路由（Least Congested Routing，简称LCR）：LCR预先确定了与FAR类似的每个源节点和目的节点对的一系列路由。根据连接请求的到达时间，从预定路线中选择最不拥挤的路线。链路上的拥塞是通过链路上可用频隙的数量来衡量的。如果可用的频隙数较少，则认为此链路更为拥挤。LCR算法计算复杂度较高，网络阻塞率与FAR几乎相同。

（4）自适应路由（Adaptive Routing，简称AR）：根据网络的链路状态信息动态选择源节点和目的节点之间的路由。例如可以将链路的使用率作为依据进行路由，比如在网络中一条链路的使用率为100%，则在进行路由时应该避开该链路，寻找链路使用率低的链路进行路由。AR算法与FAR算法相比，网络阻塞率进一步降低，但是因为要根据链路的状态信息进行动态的选择路由，所以需要频繁的更新链路状态信息，导致网络的控制管理平面更为复杂。

2.2 频谱分配子问题

频谱分配，即为业务请求沿链路分配频谱资源，频谱分配需满足上文提到的频谱连续性约束和频谱邻接性约束。常见的频谱分配方法有以下几种：

（1）首次命中（First Fit，简称为FF）[7]：在这种方案中，首先会对所有可用频谱段进行标号。当进行业务频谱分配时，会优先选择编号低的频谱段进行频谱分配，这样就可以让使用中的频谱段在频谱空间中的低端位置，高端位置就可以留给更长的路径使用。此方案不需要网络全局信息，计算复杂度和网络的阻塞率都比较低。和FF类似的还有最后命中（Last Fit，简称LF）方案，LF方案会优先选择编号高的频谱段进行频谱分配。

（2）随机命中（Random Fit，简称RF）[8]：这种方案首先会先在频谱空间中搜寻所有适合业务的可用频谱段的集合，然后随机选取频谱段进行频谱分配。该方案需要网络全局信息，且比较容易产生频谱碎片，网络的阻塞率比较高。但是如果以分布式方式执行频谱分配，该方案可以降低多个连接选择相同频谱的可能性。

（3）最少使用（Least Used，简称LU）[9]：该方案将网络中使用频次最少的频谱进行分配，这种方案可以将负载均匀的分布在所有的频谱资源上。与LU相类似的还有最多使用（Most Used，简称为MU），该方案将网络中最多使用频次的频谱进行分配，在网络中实现最大频谱重用。

（4）精确命中（Exact Fit，简称EF）[8]：该方案根据连接请求的频隙数搜索与请求的频隙数相等的确切的可用频谱块，如果满足此条件，则分配该频谱，如果不满足，则退化为FF方案进行频谱分配。通过此方案进行频谱分配，可以减少光网络中的频谱碎片。

3 RSA问题的分类

根据所请求业务的属性，RSA可以分为静态RSA和动态RSA，还有一些和RSA相关方面的问题。

3.1 静态RSA[9]

静态RSA指的是在业务需求提前已知的情况下，为每个需求分配路径和连续频谱，目标是在能够成功建立连接的情况下最小化网络中所需要的频谱资源。静态RSA常使用整数线性规划（Integer Linear Programming，简称ILP）和启发式算法。

3.2 动态RSA[10]

动态RSA是指客户端根据需要随机向网络提交连接请求。连接建立成功与否取决于网络的状态，但是可用频谱资源可能不能满足建立连接所需要的频谱资源。所以，每次根据请求建立连接时，都必须实时计算以确定是否可以容纳请求所需的频谱资源，如果因为缺少频谱资源而不能建立连接，则会阻塞该请求。在动态RSA中，通常以最小化连接阻塞率为目标。动态RSA算法大致分为两类，一类是一步式算法（One-step algorithms），它是次优的使用贪心策略同时解决路由和频谱分配两个子问题。另一类是两步式算法（two-step algorithms）。即顺序的解决路由子问题和频谱分配子问题。

3.3 其他和RSA相关的问题

（1）距离自适应RSA（Distance-adaptive RSA，简称DA-RSA）

文献[11]提出距离自适应调制技术，具体是指，对于路径长的路由应该选择低阶调制格式（比如二进制相移键控，简称BPSK），而对于路径短的的路由应该选择高阶调制格式（比如六十四进制正交振幅调制，简称64QAM），这样可以提高频谱资源的利用率。因此，在频谱分配策略中可以考虑路径的长度和调制格式来为每个连接请求分配合适的光路。

（2）频谱碎片感知RSA（Fragmentation-aware RSA，简称FA-RSA）

EONs频隙的大小是弹性的，它可以是几GHz甚至更窄，因此动态的建立光路和拆除光路会产生频谱碎片[12]，这些频谱碎片很难被新连接所使用，会造成频谱利用率的下降。因此需要对频谱碎片进行整理，重新进行路由和频谱资源的分配，但是在执行碎片整理时，重新路由会造成新建连接中断，中断会使业务建立连接时间延迟和增加系统的复杂性。所以碎片感知RSA要在进行碎片整理时使正在进行路由和频谱分配的业务不受影响。

（3）生存性RSA（Survivability RSA）

EONs中光纤或网络节点之类的网络组件的故障可能会破坏数百万用户的通信，造成数据和收入的巨大损失，因此EONs网络应该要具备在出现故障时快速恢复的能力。EONs的生存性问题可以分为两类：保护和恢复[13]。保护是在故障未发生时，在进行RSA时就预先计算出备用路径，由于预先分配了频谱资源，会使得频谱资源利用率不高，因此，保护问题RSA一般采用共享路径保护方案，即在两个相邻路径之间共享频谱资源来提高频谱的利用率。恢复是在故障发生后，根据网络链路状态动态计算备用路径，与保护方案相比，可以提供更高的频谱使用率。

4 RSA研究现状与趋势

（1）频谱分配方案设计

RSA关注的主要是以降低网络阻塞率、提高频谱利用率为目标，使用ILP方法或者设计启发式算法来优化网络资源。因此设计出高效的频谱分配方案可以减少频谱碎片，提高频谱的利用率。刘晓玲等提出基于频谱候选窗的频谱分配方案[14]，该方案会根据频谱连续度进行筛选后再进行频谱分配，改善了带宽的阻塞率。蒋蕊等提出基于业务优先级的频谱分配方案[15]，该方案可以根据到达业务的优先级顺序进行排序后再进行频谱分配，有效降低了网络中的碎片化程度。此外，还可以根据业务所需的带宽大小分类来进行频谱分配。

（2）能量效率

除了网络阻塞率和频谱利用率，能量效率也是一个值得关注的问题，特别是如何让网络中的总能耗降低。文献[16]提出了一种动态节能RSA算法，该算法根据相应链路和中间路由器的能量消耗来计算成本，在可能的候选路径中找到能量消耗最少的路径用来建立连接。

（3）智能算法

除了ILP和启发式算法，智能算法也可以运用到RSA问题中，常见的智能算法有遗传算法，蚁群算法，模拟退火算法等。Ying Wang等采用蚁群算法解决RSA问题[17]，通过仿真验证了基于蚁群算法的动态RSA网络阻塞率比基于其他算法（基于WDM的RWA算法，基于KSP的RSA算法）要有所降低，充分发挥出了蚁群算法的优势。不过，蚁群算法本身也有些缺陷，比如算法本身相比其他算法执行时间较长、比较容易出现停滞的现象。在使用蚁群算法进行RSA时，需要尽量的避免蚁群算法本身的缺陷。

（4）机器学习

机器学习（Machine Learning，简称ML）作为人工智能的一个分支，是今后信息科技发展的一个重要领域，文献[18]中提出可以使用机器学习进行路由选择，流量预测，故障检测，调制格式识别等等。为不同领域研究的结合提供了参考和依据。目前，基于机器学习的RSA研究较少，未来可以尝试使用ML方法进行EONs的RSA。

5 结束语

EONs作为下一代极具潜力的光网络体现出了很多优势，可以适应未来大容量、且不断变化的带宽需求。RSA作为EONs的一个关键问题，目前已经有了大量的研究成果，但是仍然还有许多待解决的问题。本文综述了RSA问题的概念和分类，并提出一些RSA的研究方向，可供研究人员参考。

[1]H.Zhou，S.Mao and P.Agrawal "Optical power allocation for adaptive WDM transmissions in free space optical networks，"2014 IEEE Wireless Communications and Networking Conference （WCNC），Istanbul，2014 pp.2677-2682.

[2]M.Jinno，H.Takara and B. Kozicki，"Concept and enabling technologies of spectrum-sliced elastic optical path network（SLICE），"2009 Asia Communications and Photonics conference and Exhibition（ACP），Shanghai，2009，pp. 1-2.

[3]R.Ramaswami and K.N.Sivarajan，"Routing and wavelength assignment in all-optical networks，"in IEEE/ACM Transactions on Networking,vol.3，no.5，pp.489-500，Oct.1995.

[4]Y.Zhao，J.Zhang，Y.Ji and W.Gu，"Routing and Wavelength Assignment Problem in PCE-Based Wavelength-Switched Optical Networks，"in IEEE/OSA Journal of Optical Communications and Networking，vol.2，no.4，pp.196-205，April 2010.

[5]Y.Wang，X.Cao，and Y.Pan，"A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks，"in Proc.IEEE INFOCOM，2011，pp.1503-1511.

[6]R.Ramamurthy and B.Mukherjee，"Fixed-alternate routing and wavelength conversion in wavelength-routed optical networks，"IEEE/ACM Trans.Netw.，vol.10，no.3，pp.351-367，Jun.2002.

[7]R.Wang and B.Mukherjee，"Spectrum management in heterogeneous bandwidth optical networks，"Opt.Switching Netw.，vol.11，pp.83-91，Jan.2014.

[8]A.Rosa，C.Cavdar，S.Carvalho，J.Costa，and L.Wosinska，"Spectrum allocation policy modeling for elastic optical networks，"in Proc.9th Int.Conf.HONET，2012，pp.242-246.

[9]R.M.C.Siva and G.Mohan，"WDM Optical Networks：Concepts，Design and Algorithms，"Upper Saddle River，NJ，USA：Prentice-Hall，2003.

[10]Xin Wan，Lei Wang，Nan Hua，Hanyi Zhang and Xiaoping Zheng，"Dynamic routing and spectrum assignment in flexible optical path networks，"2011 Optical Fiber Communication Conference and Exposition and the National Fiber Optic Engineers Conference，Los Angeles，CA，2011，1-3.

[11]JINNO M，KOZICKI B，TAKARA H，et al."Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network [Topics in Optical Communications[J]，"IEEE Communications Magazine，2010，48（8）：138-145.

[12]K.Christodoulopoulos，I.Tomkos，and E.Varvarigos，"Elastic bandwidth allocation in flexible OFDM-based opticalnetworks，"J. Lightw.Technol.，vol.29，no.9，pp.1354-1366，May 2011.

[13]L.Ruan and N.Xiao，"Survivable multipath routing and spectrum allocation in OFDM-based flexible optical networks，"IEEE/OSA J. Opt.Commun. Netw.，vol.5，no.3，pp.172–182，Mar.2013.

[14]刘晓玲，张竞文，喻聪，罗凌琦，沈建华.基于频谱候选窗的弹性光网络频谱分配方案[J].光通信技术，2018，42（11）：5-7.

[15]蒋蕊，冯朦，沈建华.基于业务优先级的Eonss频谱分配方案[J].光通信技术，2017，41（10）：60-62.

[16]A.Fallahpour，H.Beyranvand，S.A.Nezamalhosseini， and J.A.Salehi，"Energy efficient routing and spectrum assignment with regenerator placement in elastic optical networks，"J. Lightw. Technol.，vol. 32，no.10，pp.2019-2027，May 2014.

[17]Wang Ying，Zhang Jie，Zhao Yongli，Wang Jingjing，Gu Wanyi. "ACO-based routing and spectrum allocation in flexible bandwidth networks，"Photonic Network Communications（2013）.25.10.1007/s11107-013-0397-z.

[18]F. Musumeci，et al.，"An Overview on Application of Machine Learning Techniques in Optical Networks，"in IEEE Communications Surveys & Tutorials.