1.
引言
突如其来的新冠疫情给人们的生活和工作带来了翻天覆地的变化。一夜之间,许多工作及娱乐都需要在网络上展开,催生出类似在线游戏、远程会议、网络直播等业务,这类业务的带宽大多具有随时间变化的特点[1 ] 。在大多数情况下,为了确保服务质量,网络运营商按照时变业务的峰值带宽需求为其分配频谱资源,从而忽略了时变业务带宽随时间变化的特点,当时变业务需求带宽降低时,网络分配的频谱资源得不到充分利用,导致严重的资源浪费[2 ,3 ] 。因此,根据时变业务特点定制资源分配方法是十分必要的。
弹性光网络(Elastic Optical Networks, EONs)能够有效地克服传统波分复用光网络粗糙粒度带宽资源划分和固定不变调制格式的缺点,以灵活的带宽分配和可变的调制格式提高资源的使用率,被广泛地认为是一个极具发展潜力的支持迅速发展的互联网数据和时变业务需求的智能光网络[4 ] 。在EONs中,路由和频谱分配(Routing and Spectrum Assignment, RSA)问题成为一个基本问题[5 ] 。研究者提出的大多数RSA方法没有考虑到时变业务特点[6 ,7 ] 。
对于EONs中时变业务的资源分配问题,Kumar等人[8 ] 提出了灵活频谱重分配和频谱扩展/压缩(Spectrum Expansion/Contraction, SEC)方式,其中的SEC可以在不中断业务传输的同时完成时变业务带宽的更新,极大地提高了频谱使用率。文献[9 ]提出了一种“频谱交易”的时变业务资源分配策略,该策略根据业务请求的累计信用实现频谱资源的共享,但是,当业务累计信用值小于设定阈值时,业务将被阻止使用网络中的频谱资源。为了进一步降低时变业务的阻塞率,Pathak等人[10 ] 提出,通过将相邻时变业务聚合,达到降低阻塞率的目的。针对时变业务带宽变化的方向问题,文献[11 ]提出了动态高扩展低收缩和动态交替方向(Dynamic Alternate Direction, DAD)策略缓解时变业务被阻塞的概率,但是,其交替扩展收缩的频谱分配策略对网络高负载时的资源分配显得较为“僵硬”,使资源使用率下降。
另外,生存性RSA是解决EONs的节点或者链路出现故障情况下保障业务服务传输质量的重要手段[12 -15 ] 。Ding[16 ] 研究了生存性EONs中时变业务的路由和频谱分配问题,提出了基于专有路径保护策略的动态可生存性路由算法(Dynamic Survivable Path Routing Algorithm based on Dedicated Path Protection, DSPRA-DPP),选择跳数少和频谱碎片小的工作和专有保护路径;为了降低时变业务的保护开销,进一步提出基于共享备份路径保护(Shared Backup Path Protection, SBPP)的动态生存性路由算法(Dynamic Survivable Path Routing Algorithm-SBPP, DSPRA-SBPP)。上述2种保护策略在频谱分配阶段采用首次命中(First Fit, FF) 频谱分配策略和中心频谱压缩扩展的SEC策略,导致业务SEC后频谱分配失败的风险较大。Paira等人[17 ] 设计了一种基于碎片感知的距离自适应生存性多路径的启发式路由频谱分配(Fragmentation-aware survivable Multipath Distance-Adaptive RSA, FMDA-RSA)策略,该策略采用距离自适应调制格式的多路径共享保护方法选择业务所需路由,为业务选择跳数少、频谱碎片化较小、调制格式较高的路由和频谱块,提高了业务生存性和频谱使用率。但是,FMDA-RSA侧重减少频谱碎片,忽略了频谱块的业务承载能力和SEC特性,对时变业务带宽扩展的适应能力较差。
针对生存性EONs中时变业务的路由和频谱分配问题,本文提出一种基于频谱窗滑动的时变业务共享保护(Time-varying Traffic Sharing Protection based on Spectrum Window Sliding, TTSP-SWS)算法。TTSP-SWS算法的贡献在于:(1)设计考虑可用频谱块承载权重和保护频谱块共享度的保护路径代价函数,用于选择时变业务的保护路径;(2)设计基于频谱窗滑动的保护路径的频谱分配策略为时变业务分配所需频谱块;(3)根据时变业务带宽变化情况,设计基于频谱窗滑动的频谱扩展/压缩的调整策略。
2.
问题描述
EONs拓扑抽象为G (V , E , F ),其中,V 表示EONs节点集合,E 表示光纤链路集合,F 表示每条链路提供的频隙资源集合。时变业务表示为r (s , d , B , q ),其中,s ,d 分别表示时变业务的源、目的节点,B 表示时变业务所需带宽,q 表示时变业务需要的保护等级。
当时变业务r (s , d , B , q )到达EONs时,根据其源、目的节点以及所需带宽,采用最短路径算法确定两条链路分离的传输路径。
然后,为业务选择工作路径和保护路径物理传输距离约束的信号最高调制等级[2 ,3 ,17 ] 。
计算时变业务在保护路径上所需频隙(Frequency Slots, FSs)数目如式(1)
其中,C f 表示单位频隙的带宽,ρ m 表示信号调制等级,GB为业务之间的保护频隙。
最后,在频谱分配过程中,业务在工作和保护路径上分配的频谱应满足约束条件式(2)—式(5)
式(2)和式(3)保证了时变业务r (s , d , B , q )在工作路径和保护路径频谱分配都需要满足频谱一致性原则,其中,P w sd 表示工作路径,P p sd 为保护路径,E ( P w sd ) 为工作路径的链路集合,E ( P p sd ) 为保护路径的链路集合;r e , f w ( P w sd ) 表示工作路径的链路e 的频隙f w 是否被占用,若占用,r e , f w ( P w sd ) =1;若保护路径的链路e 上分配的频隙f p 被占用,则r e , f p ( P p sd ) =1;F ( P w sd ) 和F ( P p sd ) 分别表示工作路径和保护路径的频隙集合,式(4)和式(5)则保证了时变业务r (s , d , B , q )在工作路径和保护路径上分配的频谱需满足频谱连续性原则。
若不同业务的工作路径不相交,在单链路故障发生时,他们相交的保护路径中的频谱资源可以共享,以进一步减少频谱资源占用。
相较于带宽固定不变的业务,时变业务在带宽变化后,可以围绕着固定频率(Anchor Frequency, AF)进行动态扩展/压缩频谱。设I ( l r ) ,I ( u r ) 分别表示时变业务r (s , d , B , q )在其链路e 的AF左、右两边的已经分配频谱块的索引值,则AF对应的已分配频谱块带宽为:A r = I ( u r ) − I ( l r ) 频隙;L r ,R r 分别表示时变业务r (s , d , B , q )在链路 e 上其AF左、右两边潜在可以分配的空闲频隙数目,其计算公式为
式(6)中,R 1 表示在链路 e 上的时变业务r 的AF左边频隙索引位置的业务集合;式(7)中,R 2 表示在链路 e 上的时变业务r 的AF右边频隙索引位置的业务集合,|F |为每光纤频隙数目。
另外,根据时变业务的保护等级要求,在时变业务的所有保护路径上应至少提供q × B 的保护带宽资源,保证业务的生存性传输需求,即满足约束条件式(8)
其中,|P |表示时变业务r (s , d , B , q )的工作和保护路径数目,B k r 表示时变业务r (s , d , B , q )第k 条路径分配的带宽,B w r 表示时变业务r (s , d , B , q )在工作路径中分配的带宽值。
EONs为了服务更多时变业务,在分配AF频谱的左、右两端预留一些空闲频隙支持时变业务的频谱扩展,导致频谱使用率降低,为满足动态时变业务频谱分配的实时性要求,如何在提高频谱使用率和减少生存性时变业务L r 和R r 频隙闲置和碎片化问题是时间复杂度极高的工作[18 ] 。为此,本文设计TTSP-SWS启发式算法求解上述动态时变业务在EONs中生存性传输时的RSA问题。
3.
基于频谱窗滑动的时变业务共享保护(TTSP-SWS)方法
TTSP-SWS包括:执行最短路径算法确定时变业务的工作路径,采用中心命中的FF方法在工作路径上分配业务的频隙资源;其次,设计基于频谱窗滑动的共享频谱生存性RSA策略,选择共享保护代价值最小的保护路径,选择频谱共享度值最大的频谱块;最后,当时变业务带宽需求发生变化时,根据当前路径中频谱资源使用情况以及时变业务占用频隙位置信息,利用DAD策略滑动频谱窗,实现工作路径和保护路径上频谱分配的压缩或扩展的调整。
3.1
基于频谱窗滑动的共享频谱生存性RSA策略
采用K最短路径算法确定时变业务的工作/保护边分离的保护路径集合。在保护路径的可用频谱块中,可用频谱块包括共享FS和空闲FS,从减少网络频谱资源使用角度,考虑尽可能使时变业务占用可共享的保护FS。为此,本文设计共享保护代价函数为
其中,| B i A | ,| B j P | 分别表示第i 个可用频谱块和第j 个保护频谱块的FS数目;N ,M 分别表示保护路径中可用频谱块和共享频谱块的数目;W g 表示第g 个FS的共享度,共享度为该FS可保护业务的数量[16 ] 。
选择C ( P p sd ) 值最小且时变业务在保护路径所需要的FS数目的候选路径为时变业务的保护路径P p sd 。然后,根据所选保护路径P p sd 中共享频谱块的FS共享状态,创建频谱窗(Spectrum Window, SW),SW由一组连续的FSs构成,计算各SW频谱窗共享度,选择频谱窗共享度最大的频谱块分配给时变业务,其中,第m 个SW频谱窗共享度为
利用频谱窗滑动方法,搜寻候选保护路径中的频谱窗共享度值最大频谱块,能提高保护路径中的频谱块利用率,降低生存性业务的阻塞率。基于频谱窗滑动的频谱共享生存性RSA策略见算法1 。
3.2
基于频谱窗滑动的扩展/压缩频谱分配策略
若时变业务的带宽B 值变大,导致业务所需FS数目增加,即f n > f ,其中f n 表示时变业务带宽发生变化后所需的FS数目,则工作路径和保护路径的频谱分配均需要做出改变;如果工作路径和保护路径当前占用的频谱块能够满足频谱扩展的要求,则工作路径的频谱扩展采用DAD策略即可[11 ] 。对于保护路径中频谱扩展,若时变业务当前占用的共享频谱块可以满足业务带宽扩展的需求,则根据生存性保护需所需FS数目,建立滑动频谱窗SW,从当前共享频谱块中选择频谱窗共享度最高的SW分配给业务;若时变业务当前占用的共享频谱块不能满足频谱扩展需求,则需要在保护路径上寻找可用频谱块中对生存性业务所需FS数目进行频谱窗的调整,在频谱窗扩展调整中,为了提高FS的共享度,尽量使用时变业务当前占用的共享频谱块,并将时变业务的共享FS滑动在可用频谱块的中间位置。
基于频谱窗滑动的生存性扩展频谱分配策略详细过程见算法2 。
如果时变业务r (s , d , B , q )的带宽B 值变小,则在工作路径和保护路径上分配的频谱块比业务实际需要的频谱块大,在工作路径上采用DAD策略进行频谱压缩[11 ] ;在保护路径上,在保证频谱一致性条件下,采用基于频谱窗滑动的生存性频谱压缩分配策略,滑动频谱窗,选择出共享度最高的频谱块分配给时变业务r (s , d , B , q )。基于频谱窗滑动的生存性压缩频谱分配策略详细过程见算法3 。
4.
仿真分析
4.1
仿真环境及评价指标
为了验证本文所提TTSP-SWS算法的性能,本文分别对DSPRA-DPP[16 ] , DSPRA-SBPP[16 ] 和FMDA-RSA[17 ] 生存性策略在图1 所示的国家科学基金网(National Science Foundation Network, NSFNET)和美国网络(United States of America Network, USNET)拓扑[17 ] 中的业务阻塞率、保护冗余度和频谱使用率性能进行仿真,其中,NSFNET拓扑具有14个节点,21条链路,USNET拓扑包含24个节点,43条链路[17 ] ,设K =3,业务间保护频隙GB=1 fs,图1 的链路旁边数字表示节点之间的物理长度,单位km。其他默认仿真主要参数如表1 。
4.2
仿真结果及分析
图2 显示了不同负载情况下的业务阻塞率性能。随着业务负载的增多,图2 中所有算法的业务阻塞率都增加,这是因为网络中的可用频谱资源随着负载的增加而减少,当负载较大时,网络中的资源竞争加剧,业务在生存性路由选择和频谱分配中失败的概率增加。相比其他算法,本文所提TTSP-SWS算法在相同负载下的业务阻塞率最低,这是因为:TTSP-SWS算法在保护路径选择时,优先考虑可用或者保护频谱资源更集中的路径,选择共享保护代价值更小的保护路径;在频谱分配时,利用滑动频谱窗,将时变业务所需的FS分配在保护路径中频隙共享度较高的位置,提高了频隙的共享度和频谱窗的利用率。而对比的DSPRA-DPP算法的业务阻塞率最高,原因是DSPRA-DPP算法采用专有路径保护,频谱使用率较低;与之对应的是,DSPRA-SBPP算法,FMDA-RSA方法和TTSP-SWS算法采用共享路径保护,相较于DSPRA-DPP专有路径保护,共享路径保护可以减少保护资源的使用。相比DSPRA-SBPP算法,采用多路径生存性策略和最小频谱碎片的FMDS-RSA算法不能适应时变业务的SEC,当业务带宽变化时,FMDS-RSA算法使频谱碎片率和业务阻塞率增加。
图2(b) 是4种算法在USNET拓扑中的业务阻塞率性能,各算法在USNET中的业务阻塞率曲线呈现与图2(a) 相同的变化趋势;不同的是,在相同负载情况下,NSFNET中各算法的业务阻塞率高于USNET,原因是USNET具有更多的节点和链路数,网络的连通度更高,时变业务的路由成功概率更高。
图3 展示了4种算法在不同网络负载下的频谱使用率性能。随着业务负载增加,EONs的频谱资源被更多业务使用,提高了频谱使用率。在负载较大时,本文所提TTSP-SWS算法在NSFNET和USNET拓扑中均获得最大的频谱使用率,这是因为:TTSP-SWS算法不仅在业务路由选择阶段考虑网络中保护频谱块的频隙共享情况,在频谱分配阶段以及时变业务的带宽扩展或带宽压缩中,采用基于频谱窗滑动的生存性频谱扩展或频谱压缩策略,能将带宽变化后的业务分配在保护路径的频谱窗共享度高的频谱块位置,提高频谱资源的利用率。相较于DSPRA-SBPP算法,虽然DSPRA-DPP的冗余保护需要消耗更多的频谱资源,但是其业务阻塞率较大,所以其频谱使用率低于DSPRA-SBPP算法;而FMDA-RSA算法虽然在低负载时的业务阻塞率略低于DSPRA-SBPP算法,由于其频谱分配采用碎片感知的最小频偏率频谱块方法,减少了碎片频谱产生概率,因而其频谱使用率略低。相比于采用共享保护的DSPRA-SBPP算法和FMDS-RSA算法,TTSP-SWS算法在频谱扩展或压缩中考虑了时变业务带宽调整方向,增加了相邻时变业务之间的频谱窗共享度,进一步提高了共享频谱资源的利用率。
图4 是DSPRA-DPP, DSPRA-SBPP, FMDS-RSA和TTSP-SWS算法的保护冗余度性能对比。由于DSPRA-DPP算法采用专有路径保护,需要为业务预留更多的保护频谱资源开销,所以DSPRA-DPP的保护冗余度在4种算法中最高。相较于DSPRA-SBPP和FMDS-RSA共享保护算法,TTSP-SWS算法考虑了保护路径中频隙的共享度,并根据可用频谱块以及保护频谱块的大小,为时变业务选择共享保护代价值较小的保护路径,提高了保护路径上的频谱使用率,降低了生存性保护的资源开销;同时,在频谱分配和带宽调整中,进一步比较保护路径上频隙的共享度,选择频谱窗共享度大的频谱块,进一步降低了业务使用频谱资源的数目。另外,随着网络中负载的增多,DSPRA-SBPP, FMDS-RSA和TTSP-SWS算法的备份路径频谱保护冗余度呈现出缓慢下降的趋势,这是因为随着请求数目的增加,被业务预留的保护频谱资源增多,增加了保护频隙被其他业务共享概率,从而降低了生存性业务预留的保护频谱资源冗余度。
5.
结论
针对在EONs中时变业务高阻塞率和频谱使用率低的问题,本文提出一种基于频谱窗滑动的时变业务共享保护(TTSP-SWS)方法,为业务选择频谱使用率高和资源共享度高的保护路径;同时,通过滑动频谱窗,为业务选择频谱窗共享度高的频谱块以适应时变业务带宽扩展和压缩情况,提高了频谱资源的使用率。随着互联网中时变业务发展和生存性传输需求的增长,通过共享频谱的方式提高时变生存性业务可靠性和降低频谱资源的保护开销,对进一步增强EONs网络服务能力和质量保证能力具有积极意义。