弹性光网络中基于频谱连续度的算法研究

陈秉钧，张 宁，杨延嵩，陈晓丹

北京联合大学 智慧城市学院，北京 100101

随着信息化时代的到来，光通信技术发展越来越快[1-2]。近年来，弹性光网络（elastic optical network，EON）受到了广泛的研究，并被用来解决光纤光栅的结构中传统波分复用（WDM）光网络频谱利用率低的问题。在WDM网络中，信道带宽是固定在50 GHz，不能根据实际业务的需要，灵活地分配频谱资源，且业务请求一旦连接，网络就无法根据实时情况，动态调整频谱资源，导致WDM网络无法处理来自不同带宽要求大小的客户端的连接需求。EON依靠正交频分复用技术（OFDM），将频隙粒度的信道带宽容量划分为更细的粒度，如6.25 GHz、12.5 GHz，允许通过选择适当数量的频隙资源来构建光路。同时，由于OFDM引入子载波技术，且子载波之间的正交性，使得不同业务之间不需要保护带宽，因此EON可以灵活地和更有效地利用光纤带宽。相比传统的WDM网络，EON能提高频谱资源利用率。

对于光网络来说，在频谱分配的过程中，要遵循两个基本的约束：频谱连续性，以及频谱一致性。频谱连续性，要求在请求的路由光路中，每条链路上分配的频谱必须是连续的；频谱一致性，要求在请求的路由光路中，每条链路上占用连续的频谱的位置，必须保持一致。因此，随着不同的连接请求的建立和删除，频谱资源会出现空闲但不连续的频谱碎片，这会导致频谱资源不能满足业务请求，造成极大的浪费。因此，一个良好的路由和频谱资源分配（RSA）算法，是解决这类问题的关键。在光网络中，研究这类RSA问题，常常划分为两个子问题，即路由选择问题和频谱资源分配问题。

1 网络路由与频谱分配问题

近年来，需要预留频谱资源的业务数量迅速增加[3-5]。He等人[3]关注了在基于预留业务的RSA算法中一些不可用的频谱资源，提出的基于无效频谱感知的预留业务（advanced-reservation-based invalid-spectrumaware，AR-ISA）频谱资源分配算法，采用碎片整理算法以进一步提高网络性能。Li等人[4]提出一个指标，即四个因素的加权之和，通过最小化度量来分配业务的频谱资源，降低阻塞率。Zhu等人[5]设计了二维碎片感知以及碎片的连续性感知算法，降低了在虚拟光网络嵌入过程中的二维碎片。但是上述算法在运行过程中需要为这些业务预留出一部分频谱资源，当预留业务没有到来时，其他业务也不能占用这部分频谱资源，这就不可避免地降低了频谱资源的利用率。

Ujjwal等人[6]将距离自适应调制技术引入RSA算法中，允许在多条不相交路径上执行自适应流量需求拆分。Araújo等人[7]提出了一种新的建模方法，最大限度地减少了插槽索引，同时最小化每种需求的备用光路所需求的链接数量。但是这些算法在路由和频谱分配的过程中需要大量时间来计算，导致了算法整体的效率不高。Lezama等人[8]改进了蚁群优化算法，只需要很少的控制参数，就可以在任意灵活的场景最小化频谱利用率。Pederzolli等人[9]提出了一种新的基于路径的度量，更好地评估光网络中的频谱资源碎片化，并且提出了两个启发式RSA算法。Lechowicz等人[10]为了评估光网络中频谱碎片程度，提出了用于弹性光网络的各种碎片测量标准。此外，介绍了边界超级通道（bordering superchannels，bSChs）的新概念。但是算法在运行的过程中需要备份路由，备份的路径过多会占用大量频谱资源。Halder等人[11]提出了基于贪心算法的可生存路径的贪婪启发式算法（greedy heuristic for survivable multipath，SM-GR）和可生存多路径的遗传算法（genetic algorithm for survivable multipath，SM-GA）来求解大型网络的近似最优解。作者将提出的算法和ILP线性规划模型相比较，线性规划模型在面对大型网络时效率很低，SM-GR和SM-GA算法能有效降低业务阻塞率。但是算法运行过程中需要大量的计算，加大了每个节点处理数据的能耗。Yuan等人[12]提出了预切片的频谱分配算法。将频谱切片分为标准块，连接所需求的频谱资源预先被分成了标准块。这些措施可以对准被占用的和可用的频隙，从而降低阻塞率。但是，切块的频谱资源在面对灵活的频谱资源需求时，还是会存在大量的频谱资源不匹配导致频谱资源的浪费。

Mahmoud等人[13]提出了一种递归分解的方法，对整个路由空间进行搜索，但是整个路由表的生成需要巨大的内存空间和处理时间。当整体网络节点较多和业务量较大时，会浪费较多的时间和空间资源。Panchali等人[14]通过建立光树，提出的频谱划分方法，对现有方法进行了修改，提出了基于派系划分的疏导算法。使用首次命中频谱分配策略，它从可用的第一个索引向奇数分区分配频隙，并从最后一个索引开始为偶数分区来分配频隙。Yuan等人[15]提出了链路相邻缩减的概念，表示使用一个频谱块后链路上频谱的变化情况，在此基础上，提出了一种RSA算法，该算法选择使链路相邻缩减最小的频谱资源分配给业务，提高频谱资源利用率。王鹏辉等人[16]提出了重要节点的概念，算法将经过重要节点的业务分配次短路径。但是算法需要提前知道所有业务的源节点和目的节点。李娜娜等人[17]提出了一种基于路径长度和节点数的算法，算法选择路由上节点最少的路径，如果路径的跳数相同则选择距离最短的路径。

2 提高频谱资源利用率的频谱连续度错位感知算法

在弹性光网络中，路由和频谱分配问题一直是NP-hard问题，因此，在解决路由和频谱分配问题时，本文提出一种频谱连续度感知算法。该算法分为两步：在路由选择方面，KSP最短路径算法能根据源节点和目的节点计算出一条最短路径，业务需要的频隙数量越少，分配的路径越短，反之业务需要的频隙数量越多，分配的路径越长。在频谱分配方面，考虑到新的业务到来后，承载该业务的路径上各链路原本的频谱资源连续性会减少，为此，专门在此算法中引入一个新的参数Cuts，根据Cuts值来分配频谱位置，该算法能有效减少业务的阻塞率，并提高频谱资源利用率。

2.1 基于KSP的路由选择方式

在实际生活中，各网络节点产生的业务量是不同的，例如大城市中产生的业务量更多，且节点数量更加集中，距离更近。如图1简单网络拓扑所示，假设节点1和节点2为繁忙节点，这两个节点产生的业务数量远远超过其他节点。

图1 简易网络拓扑Fig.1 Simple network topology

假定同时出现2个请求，分别为（1-3）、（1-4），且所需要的频隙数分别为1、2。经过计算可知两个请求的路径分别为（1-2-3）、（1-5-4）。节点1这个繁忙节点产生的两个业务将不会同时使用节点1和节点2间的链路，降低链路的负载压力。因此繁忙节点的产生大量业务就可以尽可能地分配到整个网络空间，降低整个网络的业务阻塞率，提高频谱资源利用率。

2.2 基于频谱连续度感知的频谱分配方式

在光网络动态运行过程中，新业务的到来会造成业务所在链路上连续的频谱资源分段，本文使用参数Cuts来表示一个新的连接是否将链路上的连续频谱分段。如果新业务会将链路上的连续频谱分段，Cuts=1；反之，则Cuts=0。此时计算从源节点到目的节点所有经过的链路上连续频谱资源因该业务所引起的分段，参数Cuts的值等于承载该业务所引起的连续频谱资源分段之和，Cuts值定量地表现了一个新连接所引起的频谱碎片程度，Cuts值越低代表分配后的频谱碎片更少，频谱利用率更高。因此在分配频谱资源时应选择Cuts值最低的位置分配频谱资源。

假定在该网络中，每条链路的频隙数量为15，如图2所示，链路上黑色的小方块代表已经被占用的频谱资源，白色的小方块代表未被占用的频谱资源。假定网络中新的业务请求从节点1到节点5，其中经过链路1-2，链路2-3，链路3-4，链路4-5，需求的频谱资源为一个频隙。

图2 路径简易状态图Fig.2 Simple path state diagram

如图3所示，带箭头的虚线表示路径上满足业务需求的频谱资源，Cuts表示将这段频谱资源分配给新业务后，新业务中断的连续频谱资源的数量。此时假设新业务需要1个频隙的频谱资源，在一般的RSA算法中，从路径1-5上看，slot2、slot8、slot12是等价的。但是在本文的KSPDP算法中，slot2位置的Cuts值为3，而slot8位置上Cuts值为0，slot12位置上Cuts值为1，所以算法将这个业务分配在slot8的位置上，此时产生的频谱碎片最少。

图3 频谱分配示意图Fig.3 Spectrum allocation diagram

2.3 算法流程

算法通过仿真数据得到源节点和目的节点对，并利用KSP算法计算得出K条最短路径，根据这一节点对所需要的频隙数量分配路由路径，需要的频隙数量越少，分配的路径越短。比如业务需要一个频隙大小的频谱资源，就分配最短路径。需要的频隙数量越多，分配的路径越长，比如业务需要八个频隙大小的频谱资源，就分配第K短路径。之后算法计算各位置的频谱资源所引起分段的Cuts值，其用来计算分配频谱资源时，新的业务对原有频谱资源的影响，Cuts值越低，越会最大限度地避免影响各链路间可用频隙的对齐关系，通过计算Cuts值来分配业务所需频谱资源的位置，将业务分配在Cuts值最小的位置，减少频谱碎片的产生，提高各链路的业务承载能力。该算法可以最大限度地将单一连接上的频谱资源最大化利用起来，减少频谱资源碎片。

其工作流程图如图4所示。

图4 算法流程图Fig.4 Algorithm flowing diagram

步骤1根据业务请求的节点对计算K条最短路径并选择其中路径最短的5条路径。

步骤2根据业务请求所需要的连续频谱资源数量分配路由路径，业务需求的连续频谱资源数量越少，分配的路径越短。

步骤3确定路由路径之后并根据算法所计算的Cuts值，选择Cuts值最低的位置分配频谱位置。

步骤4继续为下一个业务分配频谱资源。

3 仿真实验

3.1 仿真环境

本文的仿真都是利用python语言进行编程的，并对仿真结果进行分析，仿真所用的网络拓扑为经典的NSFNET网络结构和USNET网络结构，图5为NSFNET网络拓扑，该结构共有14个节点和21条链路。图6为USNET网络拓扑，该网络结构共有24节点43条链路。

图5 NSFNET网络拓扑结构Fig.5 NSFNET network topology

图6 USNET网络拓扑Fig.6 USNET network topology

在仿真过程中，本文假设网络每条链路只有一个光线对。每条链路上的可分配频谱带宽为4.475 THz，每个频隙所需的带宽为12.5 GHz，因此每条连续所拥有的频隙数为358个。仿真中业务到达时间服从参数为λ泊松分布，且连接的持续时间是服从参数为μ指数分布，网络负载为λ/μ的爱尔兰Erlang。业务请求所需的频隙1、2、4、6、8中随机选择，在NSFNET网络中，源节点有一半产生于10、11、12、13这四个节点，另一半在剩下的节点中随机产生，目的节点随机产生。在USNET网络中，源节点有一半产生于2、12、15、20、23这五个节点，另一半在剩下的节点中随机产生，目的节点随机产生。

3.2 仿真结果

算法性能评价指标根据业界流行的业务阻塞率和频谱资源利用率来对比。业务阻塞率是指在算法运行过程中，分配失败的业务占整体业务的比值。频谱资源利用率是指在算法运行过程中，链路上被占用的频谱资源数量占所有频谱资源数量的比值，业务阻塞率越低，频谱资源利用率越高，代表算法性能越好。图7和图8展示了算法在NSFNET网络仿真下的业务阻塞率和频谱资源利用率。图9和图10展示了算法在USNET网络仿真下的业务阻塞率和频谱资源利用率。本文将最短路径路由首次命中（Hij+FF）算法和KSPDP算法进行对比。

如图7所示，在NSFNET网络拓扑下，业务请求的阻塞率都随着业务量的增长而增大。在网络负载较低的时候，KSPDP算法与传统的RSA算法差距比较小，但是从网络负载量上升之后，KSPDP算法明显降低了业务阻塞率，在负载流量较大的情况下降低的业务阻塞率可以提升16%～17%。KSPDP算法与传统的RSA算法相比，在相同的业务量下，KSPDP算法的业务阻塞率总是低于传统的RSA算法。仿真说明KSPDP算法的可以有效降低业务的阻塞率。

图7 NSFNET网络阻塞率对比图Fig.7 NSFNET network blocking probability comparison diagram

如图8所示，对于NSFNET网络拓扑，在业务量较小时，KSPDP算法将业务请求更大地分配在了整个网络空间，所以在繁忙节点间的单条链路上频谱资源利用率会低于传统的算法，此时整个网络的业务阻塞率普遍在一个比较低的水准，局部的频谱资源利用率低不影响整个网络的正常运行。但是当业务负载量变大时，相比传统算法，KSPDP算法在寻找频隙位置的方式上有所不同。当频谱上出现了一系列的大小不同的频隙时，KSPDP算法采用频谱资源连续度最高的频隙位置的方式来进行频谱资源的再分配，这样一来，由此产生的频谱碎片就会少一些。这样就提高了频谱资源利用率。相比于传统算法频谱资源利用率为0.575，KSPDP算法频谱利用率为0.66，频谱资源利用率提高约10%，更多的频谱资源被利用。仿真结果证明KSPDP算法可以有效提高频谱资源利用率，降低业务阻塞率。

图8 NSFNET网络频谱资源利用率对比图Fig.8 NSFNET network spectrum resource utilization comparison diagram

为了验证算法在更复杂的网络环境下的性能，同时验证算法的适用性，除了在NSFNET网络拓扑下进行仿真之外，实验在相同的仿真条件下，在USNET网络下进行了仿真实验，USNET网络拓扑网络规模和复杂度都更大，可以用来评价算法在更大的网络规模下的适用性和相关性能。

如图9所示，随着网络负载的增加，KSPDP算法和Hij+FF算法的业务阻塞率都随之增加。KSPDP算法与传统的RSA算法相比，业务阻塞率明显更低，同时比较算法NSFNET网络拓扑和USNET网络拓扑上的表现，KSPDP算法均比Hij+FF算法业务阻塞率更低。表明了KSPDP算法的性能与仿真所用的网络拓扑结构无关，能明显降低业务阻塞率。

图9 USNET网络业务阻塞率对比图Fig.9 USNET network blocking probability comparison diagram

如图10所示，KSPDP算法和Hij+FF算法的频谱利用率都随着网络负载的增加而增加，和NSFNET网络相似，算法在网络负载较低的时候将业务分散在整个网络空间内，随着网络负载的增加，KSPDP算法的频谱利用率比Hij+FF算法更高。USNET网络拓扑的仿真结果表明，KSPDP算法能提高频谱资源利用率。

图10 USNET网络频谱资源利用率对比图Fig.10 USNET network spectrum resource utilization comparison diagram

随着未来更多新的业务类型的出现，业界会利用算法阻塞率性能的劣化来评估算法面对网络中线路速率增多的情况，本文算法阻塞率性能的劣化是指网络上运行业务需求频隙数量是五种时业务阻塞率和网络上运行业务需求频隙数量为三种时业务阻塞率之差。

如图11所示，在NSFNET网络上，随着网络负载的增加，两种算法的业务阻塞率性能都有所下降，但是KSPDP算法在面对业务所需频隙数量的增加时，其业务阻塞率劣化比Hij+FF算法要好，表明算法在面对未来更多业务需求种类时有更好的适应性。

图11 NSFNET阻塞率性能劣化对比图Fig.11 NSFNET blocking probability performance degradation comparison diagram

如图12所示，在USNET网络上，KSPDP算法的阻塞率劣化依然优于Hij+FF算法，随着网络规模的扩大和业务的频繁产生和离开，网络中的频谱碎片会增多，更大需求的频隙大小也会导致频谱碎片的大小变大。此时，算法为后续的业务分配频谱资源的成功率也会下降，业务阻塞率也会随之上升。

图12 USNET阻塞率性能劣化对比图Fig.12 USNET blocking probability performance degradation comparison diagram

综上所述，通过仿真结果可以看出，KSPDP算法相比传统的RSA算法，可以将随机到来的业务请求尽可能均匀地分布在整个网络空间，相比首次命中算法寻找第一个满足频谱资源要求的频隙位置，KSPDP算法可以寻找使得频谱资源连续度最高的频隙位置来分配频谱资源，因此，产生的频谱碎片会尽量少一些，能将整个空间的频谱资源利用起来，减少频谱资源碎片，这可以更好地满足接下来的业务需求，所以，这种方法拥有更高的频谱资源利用率。

4 结论

本文研究了路由选择和频谱分配算法，为了提高光网络中频谱利用率，提升网络整体性能，提出了一种基于KSP的频谱连续度感知算法（KSPDP）。该算法在弹性光网络中，针对路由选择问题和频谱资源分配问题，提供了一种新的解决方案，在光通信网络中，面对同一个源节点和目的节点所产生的业务，需要按照业务请求的不同，分配不同的路径，以便使业务更均衡地分配在整个网络空间。针对频谱分配问题，根据业务请求频隙的不同，用不同的频谱分配方式，最大限度地节省频谱资源，从而提高频谱资源利用率。本文算法在NSFNET网络拓扑环境下进行了仿真实验。仿真结果显示所提出的基于KSP的频谱连续度感知算法（KSPDP），在业务阻塞率和频谱资源利用率方面，比传统的RSA算法有一定的提高。