劉煥淋 張建劍 陳 勇 王展鵬 陳浩楠 邱 艷 霍星吉

①(重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065)

②(重慶郵電大學(xué)自動化學(xué)院 重慶 400065)

1 引言

突如其來的新冠疫情給人們的生活和工作帶來了翻天覆地的變化。一夜之間，許多工作及娛樂都需要在網(wǎng)絡(luò)上展開，催生出類似在線游戲、遠程會議、網(wǎng)絡(luò)直播等業(yè)務(wù)，這類業(yè)務(wù)的帶寬大多具有隨時間變化的特點[1]。在大多數(shù)情況下，為了確保服務(wù)質(zhì)量，網(wǎng)絡(luò)運營商按照時變業(yè)務(wù)的峰值帶寬需求為其分配頻譜資源，從而忽略了時變業(yè)務(wù)帶寬隨時間變化的特點，當時變業(yè)務(wù)需求帶寬降低時，網(wǎng)絡(luò)分配的頻譜資源得不到充分利用，導(dǎo)致嚴重的資源浪費[2,3]。因此，根據(jù)時變業(yè)務(wù)特點定制資源分配方法是十分必要的。

彈性光網(wǎng)絡(luò)(Elastic Optical Networks,EONs)能夠有效地克服傳統(tǒng)波分復(fù)用光網(wǎng)絡(luò)粗糙粒度帶寬資源劃分和固定不變調(diào)制格式的缺點，以靈活的帶寬分配和可變的調(diào)制格式提高資源的使用率，被廣泛地認為是一個極具發(fā)展?jié)摿Φ闹С盅杆侔l(fā)展的互聯(lián)網(wǎng)數(shù)據(jù)和時變業(yè)務(wù)需求的智能光網(wǎng)絡(luò)[4]。在EONs中，路由和頻譜分配(Routing and Spectrum Assignment,RSA)問題成為一個基本問題[5]。研究者提出的大多數(shù)RSA方法沒有考慮到時變業(yè)務(wù)特點[6,7]。

對于EONs中時變業(yè)務(wù)的資源分配問題，Kumar等人[8]提出了靈活頻譜重分配和頻譜擴展/壓縮(Spectrum Expansion/Contraction,SEC)方式，其中的SEC可以在不中斷業(yè)務(wù)傳輸?shù)耐瑫r完成時變業(yè)務(wù)帶寬的更新，極大地提高了頻譜使用率。文獻[9]提出了一種“頻譜交易”的時變業(yè)務(wù)資源分配策略，該策略根據(jù)業(yè)務(wù)請求的累計信用實現(xiàn)頻譜資源的共享，但是，當業(yè)務(wù)累計信用值小于設(shè)定閾值時，業(yè)務(wù)將被阻止使用網(wǎng)絡(luò)中的頻譜資源。為了進一步降低時變業(yè)務(wù)的阻塞率，Pathak等人[10]提出，通過將相鄰時變業(yè)務(wù)聚合，達到降低阻塞率的目的。針對時變業(yè)務(wù)帶寬變化的方向問題，文獻[11]提出了動態(tài)高擴展低收縮和動態(tài)交替方向(Dynam ic A lternate Direction,DAD)策略緩解時變業(yè)務(wù)被阻塞的概率，但是，其交替擴展收縮的頻譜分配策略對網(wǎng)絡(luò)高負載時的資源分配顯得較為“僵硬”，使資源使用率下降。

另外，生存性RSA是解決EONs的節(jié)點或者鏈路出現(xiàn)故障情況下保障業(yè)務(wù)服務(wù)傳輸質(zhì)量的重要手段[12–15]。Ding[16]研究了生存性EONs中時變業(yè)務(wù)的路由和頻譜分配問題，提出了基于專有路徑保護策略的動態(tài)可生存性路由算法(Dynam ic Su rvivab le Path Routing A lgorithm based on Dedicated Path Protection,DSPRA-DPP)，選擇跳數(shù)少和頻譜碎片小的工作和專有保護路徑；為了降低時變業(yè)務(wù)的保護開銷，進一步提出基于共享備份路徑保護(Shared Backup Path Protection,SBPP)的動態(tài)生存性路由算法(Dynam ic Survivab le Path Routing A lgorithm-SBPP,DSPRA-SBPP)。上述2種保護策略在頻譜分配階段采用首次命中(First Fit,FF)頻譜分配策略和中心頻譜壓縮擴展的SEC策略，導(dǎo)致業(yè)務(wù)SEC后頻譜分配失敗的風(fēng)險較大。Paira等人[17]設(shè)計了一種基于碎片感知的距離自適應(yīng)生存性多路徑的啟發(fā)式路由頻譜分配(Fragm en tationaw are survivab le M ultipath Distance-Adap tive RSA,FMDA-RSA)策略，該策略采用距離自適應(yīng)調(diào)制格式的多路徑共享保護方法選擇業(yè)務(wù)所需路由，為業(yè)務(wù)選擇跳數(shù)少、頻譜碎片化較小、調(diào)制格式較高的路由和頻譜塊，提高了業(yè)務(wù)生存性和頻譜使用率。但是，F(xiàn)MDA-RSA側(cè)重減少頻譜碎片，忽略了頻譜塊的業(yè)務(wù)承載能力和SEC特性，對時變業(yè)務(wù)帶寬擴展的適應(yīng)能力較差。

針對生存性EONs中時變業(yè)務(wù)的路由和頻譜分配問題，本文提出一種基于頻譜窗滑動的時變業(yè)務(wù)共享保護(T im e-varying T raffic Sharing Protection based on Spectrum W indow Sliding,TTSPSWS)算法。TTSP-SWS算法的貢獻在于：(1)設(shè)計考慮可用頻譜塊承載權(quán)重和保護頻譜塊共享度的保護路徑代價函數(shù)，用于選擇時變業(yè)務(wù)的保護路徑；(2)設(shè)計基于頻譜窗滑動的保護路徑的頻譜分配策略為時變業(yè)務(wù)分配所需頻譜塊；(3)根據(jù)時變業(yè)務(wù)帶寬變化情況，設(shè)計基于頻譜窗滑動的頻譜擴展/壓縮的調(diào)整策略。

2 問題描述

EONs拓撲抽象為G(V, E, F)，其中，V表示EONs節(jié)點集合，E表示光纖鏈路集合，F(xiàn)表示每條鏈路提供的頻隙資源集合。時變業(yè)務(wù)表示為r(s,d,B,q)，其中，s,d分別表示時變業(yè)務(wù)的源、目的節(jié)點，B表示時變業(yè)務(wù)所需帶寬，q表示時變業(yè)務(wù)需要的保護等級。

當時變業(yè)務(wù)r(s,d,B,q)到達EONs時，根據(jù)其源、目的節(jié)點以及所需帶寬，采用最短路徑算法確定兩條鏈路分離的傳輸路徑。

然后，為業(yè)務(wù)選擇工作路徑和保護路徑物理傳輸距離約束的信號最高調(diào)制等級[2,3,17]。

計算時變業(yè)務(wù)在保護路徑上所需頻隙(Frequency Slots,FSs)數(shù)目如式(1)

其中，Cf表示單位頻隙的帶寬，ρm表示信號調(diào)制等級，GB為業(yè)務(wù)之間的保護頻隙。

最后，在頻譜分配過程中，業(yè)務(wù)在工作和保護路徑上分配的頻譜應(yīng)滿足約束條件式(2)—式(5)

式(2)和式(3)保證了時變業(yè)務(wù)r(s,d,B,q)在工作路徑和保護路徑頻譜分配都需要滿足頻譜一致性原則，其中，表示工作路徑，為保護路徑，為工作路徑的鏈路集合，為保護路徑的鏈路集合；表示工作路徑的鏈路e的頻隙fw是否被占用，若占用，；若保護路徑的鏈路e 上分配的頻隙fp被占用，則r e,f p=1；分別表示工作路徑和保護路徑的頻隙集合，式(4)和式(5)則保證了時變業(yè)務(wù)r(s,d,B,q)在工作路徑和保護路徑上分配的頻譜需滿足頻譜連續(xù)性原則。

若不同業(yè)務(wù)的工作路徑不相交，在單鏈路故障發(fā)生時，他們相交的保護路徑中的頻譜資源可以共享，以進一步減少頻譜資源占用。

相較于帶寬固定不變的業(yè)務(wù)，時變業(yè)務(wù)在帶寬變化后，可以圍繞著固定頻率(Anchor Frequency,AF)進行動態(tài)擴展/壓縮頻譜。設(shè)I(l r),I(u r)分別表示時變業(yè)務(wù)r(s,d,B,q)在其鏈路e的AF左、右兩邊的已經(jīng)分配頻譜塊的索引值，則AF對應(yīng)的已分配頻譜塊帶寬為：Ar=I(u r)-I(l r)頻 隙；Lr,Rr分別表示時變業(yè)務(wù)r(s,d,B,q)在鏈路e上其AF左、右兩邊潛在可以分配的空閑頻隙數(shù)目，其計算公式為

式(6)中，R1表示在鏈路e上的時變業(yè)務(wù)r的AF左邊頻隙索引位置的業(yè)務(wù)集合；式(7)中，R2表示在鏈路e上的時變業(yè)務(wù)r的AF右邊頻隙索引位置的業(yè)務(wù)集合，|F|為每光纖頻隙數(shù)目。

另外，根據(jù)時變業(yè)務(wù)的保護等級要求，在時變業(yè)務(wù)的所有保護路徑上應(yīng)至少提供q×B的保護帶寬資源，保證業(yè)務(wù)的生存性傳輸需求，即滿足約束條件式(8)

其中，|P|表示時變業(yè)務(wù)r(s,d,B,q)的工作和保護路徑數(shù)目，表示時變業(yè)務(wù)r(s,d,B,q)第k條路徑分配的帶寬，表示時變業(yè)務(wù)r(s,d,B,q)在工作路徑中分配的帶寬值。

EONs為了服務(wù)更多時變業(yè)務(wù)，在分配AF頻譜的左、右兩端預(yù)留一些空閑頻隙支持時變業(yè)務(wù)的頻譜擴展，導(dǎo)致頻譜使用率降低，為滿足動態(tài)時變業(yè)務(wù)頻譜分配的實時性要求，如何在提高頻譜使用率和減少生存性時變業(yè)務(wù)Lr和Rr頻隙閑置和碎片化問題是時間復(fù)雜度極高的工作[18]。為此，本文設(shè)計TTSPSWS啟發(fā)式算法求解上述動態(tài)時變業(yè)務(wù)在EONs中生存性傳輸時的RSA問題。

3 基于頻譜窗滑動的時變業(yè)務(wù)共享保護(TTSPSWS)方法

TTSP-SW S包括：執(zhí)行最短路徑算法確定時變業(yè)務(wù)的工作路徑，采用中心命中的FF方法在工作路徑上分配業(yè)務(wù)的頻隙資源；其次，設(shè)計基于頻譜窗滑動的共享頻譜生存性RSA策略，選擇共享保護代價值最小的保護路徑，選擇頻譜共享度值最大的頻譜塊；最后，當時變業(yè)務(wù)帶寬需求發(fā)生變化時，根據(jù)當前路徑中頻譜資源使用情況以及時變業(yè)務(wù)占用頻隙位置信息，利用DAD策略滑動頻譜窗，實現(xiàn)工作路徑和保護路徑上頻譜分配的壓縮或擴展的調(diào)整。

3.1 基于頻譜窗滑動的共享頻譜生存性RSA策略

采用K最短路徑算法確定時變業(yè)務(wù)的工作/保護邊分離的保護路徑集合。在保護路徑的可用頻譜塊中，可用頻譜塊包括共享FS和空閑FS，從減少網(wǎng)絡(luò)頻譜資源使用角度，考慮盡可能使時變業(yè)務(wù)占用可共享的保護FS。為此，本文設(shè)計共享保護代價函數(shù)為

利用頻譜窗滑動方法，搜尋候選保護路徑中的頻譜窗共享度值最大頻譜塊，能提高保護路徑中的頻譜塊利用率，降低生存性業(yè)務(wù)的阻塞率。基于頻譜窗滑動的頻譜共享生存性RSA策略見算法1。

算法1 基于頻譜窗滑動的頻譜共享生存性RSA策略

3.2 基于頻譜窗滑動的擴展/壓縮頻譜分配策略

若時變業(yè)務(wù)的帶寬B值變大，導(dǎo)致業(yè)務(wù)所需FS數(shù)目增加，即fn＞f，其中fn表示時變業(yè)務(wù)帶寬發(fā)生變化后所需的FS數(shù)目，則工作路徑和保護路徑的頻譜分配均需要做出改變；如果工作路徑和保護路徑當前占用的頻譜塊能夠滿足頻譜擴展的要求，則工作路徑的頻譜擴展采用DAD策略即可[11]。對于保護路徑中頻譜擴展，若時變業(yè)務(wù)當前占用的共享頻譜塊可以滿足業(yè)務(wù)帶寬擴展的需求，則根據(jù)生存性保護需所需FS數(shù)目，建立滑動頻譜窗SW，從當前共享頻譜塊中選擇頻譜窗共享度最高的SW分配給業(yè)務(wù)；若時變業(yè)務(wù)當前占用的共享頻譜塊不能滿足頻譜擴展需求，則需要在保護路徑上尋找可用頻譜塊中對生存性業(yè)務(wù)所需FS數(shù)目進行頻譜窗的調(diào)整，在頻譜窗擴展調(diào)整中，為了提高FS的共享度，盡量使用時變業(yè)務(wù)當前占用的共享頻譜塊，并將時變業(yè)務(wù)的共享FS滑動在可用頻譜塊的中間位置。

基于頻譜窗滑動的生存性擴展頻譜分配策略詳細過程見算法2。

如果時變業(yè)務(wù)r(s,d,B,q)的帶寬B值變小，則在工作路徑和保護路徑上分配的頻譜塊比業(yè)務(wù)實際需要的頻譜塊大，在工作路徑上采用DAD策略進行頻譜壓縮[11]；在保護路徑上，在保證頻譜一致性條件下，采用基于頻譜窗滑動的生存性頻譜壓縮分配策略，滑動頻譜窗，選擇出共享度最高的頻譜塊分配給時變業(yè)務(wù)r(s,d,B,q)。基于頻譜窗滑動的生存性壓縮頻譜分配策略詳細過程見算法3。

4 仿真分析

4.1 仿真環(huán)境及評價指標

為了驗證本文所提TTSP-SW S算法的性能，本文分別對DSPRA-DPP[16],DSPRA-SBPP[16]和FMDA-RSA[17]生存性策略在圖1所示的國家科學(xué)基金網(wǎng)(National Science Foundation Network,NSFNET)和美國網(wǎng)絡(luò)(United States of America Network,USNET)拓撲[17]中的業(yè)務(wù)阻塞率、保護冗余度和頻譜使用率性能進行仿真，其中，NSFNET拓撲具有14個節(jié)點，21條鏈路，USNET拓撲包含24個節(jié)點，43條鏈路[17]，設(shè)K=3，業(yè)務(wù)間保護頻隙GB=1 fs，圖1的鏈路旁邊數(shù)字表示節(jié)點之間的物理長度，單位km。其他默認仿真主要參數(shù)如表1。

表1 默認仿真參數(shù)

圖1 仿真網(wǎng)絡(luò)拓撲圖

算法2 基于頻譜窗滑動的生存性擴展頻譜分配策略

4.2 仿真結(jié)果及分析

圖2顯示了不同負載情況下的業(yè)務(wù)阻塞率性能。隨著業(yè)務(wù)負載的增多，圖2中所有算法的業(yè)務(wù)阻塞率都增加，這是因為網(wǎng)絡(luò)中的可用頻譜資源隨著負載的增加而減少，當負載較大時，網(wǎng)絡(luò)中的資源競爭加劇，業(yè)務(wù)在生存性路由選擇和頻譜分配中失敗的概率增加。相比其他算法，本文所提TTSP-SWS算法在相同負載下的業(yè)務(wù)阻塞率最低，這是因為：TTSP-SWS算法在保護路徑選擇時，優(yōu)先考慮可用或者保護頻譜資源更集中的路徑，選擇共享保護代價值更小的保護路徑；在頻譜分配時，利用滑動頻譜窗，將時變業(yè)務(wù)所需的FS分配在保護路徑中頻隙共享度較高的位置，提高了頻隙的共享度和頻譜窗的利用率。而對比的DSPRA-DPP算法的業(yè)務(wù)阻塞率最高，原因是DSPRA-DPP算法采用專有路徑保護，頻譜使用率較低；與之對應(yīng)的是，DSPRASBPP算法，F(xiàn)MDA-RSA方法和TTSP-SWS算法采用共享路徑保護，相較于DSPRA-DPP專有路徑保護，共享路徑保護可以減少保護資源的使用。相比DSPRA-SBPP算法，采用多路徑生存性策略和最小頻譜碎片的FMDS-RSA算法不能適應(yīng)時變業(yè)務(wù)的SEC，當業(yè)務(wù)帶寬變化時，F(xiàn)MDS-RSA算法使頻譜碎片率和業(yè)務(wù)阻塞率增加。

圖2(b)是4種算法在USNET拓撲中的業(yè)務(wù)阻塞率性能，各算法在USNET中的業(yè)務(wù)阻塞率曲線呈現(xiàn)與圖2(a)相同的變化趨勢；不同的是，在相同負載情況下，NSFNET中各算法的業(yè)務(wù)阻塞率高于USNET，原因是USNET具有更多的節(jié)點和鏈路數(shù)，網(wǎng)絡(luò)的連通度更高，時變業(yè)務(wù)的路由成功概率更高。

圖3展示了4種算法在不同網(wǎng)絡(luò)負載下的頻譜使用率性能。隨著業(yè)務(wù)負載增加，EONs的頻譜資源被更多業(yè)務(wù)使用，提高了頻譜使用率。在負載較大時，本文所提TTSP-SWS算法在NSFNET和USNET拓撲中均獲得最大的頻譜使用率，這是因為：TTSP-SWS算法不僅在業(yè)務(wù)路由選擇階段考慮網(wǎng)絡(luò)中保護頻譜塊的頻隙共享情況，在頻譜分配階段以及時變業(yè)務(wù)的帶寬擴展或帶寬壓縮中，采用基于頻譜窗滑動的生存性頻譜擴展或頻譜壓縮策略，能將帶寬變化后的業(yè)務(wù)分配在保護路徑的頻譜窗共享度高的頻譜塊位置，提高頻譜資源的利用率。相較于DSPRA-SBPP算法，雖然DSPRA-DPP的冗余保護需要消耗更多的頻譜資源，但是其業(yè)務(wù)阻塞率較大，所以其頻譜使用率低于DSPRA-SBPP算法；而FMDA-RSA算法雖然在低負載時的業(yè)務(wù)阻塞率略低于DSPRA-SBPP算法，由于其頻譜分配采用碎片感知的最小頻偏率頻譜塊方法，減少了碎片頻譜產(chǎn)生概率，因而其頻譜使用率略低。相比于采用共享保護的DSPRA-SBPP算法和FMDS-RSA算法，TTSP-SWS算法在頻譜擴展或壓縮中考慮了時變業(yè)務(wù)帶寬調(diào)整方向，增加了相鄰時變業(yè)務(wù)之間的頻譜窗共享度，進一步提高了共享頻譜資源的利用率。

圖4是DSPRA-DPP,DSPRA-SBPP,FMDSRSA和TTSP-SW S算法的保護冗余度性能對比。由于DSPRA-DPP算法采用專有路徑保護，需要為業(yè)務(wù)預(yù)留更多的保護頻譜資源開銷，所以DSPRA-DPP的保護冗余度在4種算法中最高。相較于DSPRASBPP和FMDS-RSA共享保護算法，TTSP-SWS算法考慮了保護路徑中頻隙的共享度，并根據(jù)可用頻譜塊以及保護頻譜塊的大小，為時變業(yè)務(wù)選擇共享保護代價值較小的保護路徑，提高了保護路徑上的頻譜使用率，降低了生存性保護的資源開銷；同時，在頻譜分配和帶寬調(diào)整中，進一步比較保護路徑上頻隙的共享度，選擇頻譜窗共享度大的頻譜塊，進一步降低了業(yè)務(wù)使用頻譜資源的數(shù)目。另外，隨著網(wǎng)絡(luò)中負載的增多，DSPRA-SBPP,FMDSRSA和TTSP-SWS算法的備份路徑頻譜保護冗余度呈現(xiàn)出緩慢下降的趨勢，這是因為隨著請求數(shù)目的增加，被業(yè)務(wù)預(yù)留的保護頻譜資源增多，增加了保護頻隙被其他業(yè)務(wù)共享概率，從而降低了生存性業(yè)務(wù)預(yù)留的保護頻譜資源冗余度。

5 結(jié)論

針對在EONs中時變業(yè)務(wù)高阻塞率和頻譜使用率低的問題，本文提出一種基于頻譜窗滑動的時變業(yè)務(wù)共享保護(TTSP-SWS)方法，為業(yè)務(wù)選擇頻譜使用率高和資源共享度高的保護路徑；同時，通過滑動頻譜窗，為業(yè)務(wù)選擇頻譜窗共享度高的頻譜塊以適應(yīng)時變業(yè)務(wù)帶寬擴展和壓縮情況，提高了頻譜資源的使用率。隨著互聯(lián)網(wǎng)中時變業(yè)務(wù)發(fā)展和生存性傳輸需求的增長，通過共享頻譜的方式提高時變生存性業(yè)務(wù)可靠性和降低頻譜資源的保護開銷，對進一步增強EONs網(wǎng)絡(luò)服務(wù)能力和質(zhì)量保證能力具有積極意義。