張佳唯, 錢鳳臣, 楊俊強(qiáng), 趙 騫, 張崢嶸

(國(guó)防科技大學(xué)信息通信學(xué)院, 陜西 西安 710106)

0 引 言

近年來(lái),隨著云計(jì)算、視頻點(diǎn)播等高流量型應(yīng)用的不斷興起以及物聯(lián)網(wǎng)等新型網(wǎng)絡(luò)范式的廣泛使用,以光纖通信為基礎(chǔ)的現(xiàn)代信息通信技術(shù)受到越來(lái)越多的關(guān)注。其中,基于波分復(fù)用(wavelength division multiplexing,WDM)技術(shù)的第二代光網(wǎng)絡(luò)采用固定波長(zhǎng)資源分配模式,已無(wú)法滿足具有較大帶寬需求且靈活復(fù)雜的新型流量業(yè)務(wù),使得目前急需一種能夠支持高動(dòng)態(tài)、高容量和高傳輸質(zhì)量服務(wù)的網(wǎng)絡(luò)架構(gòu)。由此,以光正交頻分復(fù)用(optical orthogonal frequency division multiplexing,O-OFDM)技術(shù)為基礎(chǔ)的彈性光網(wǎng)絡(luò)(elastic optical networks,EONs)應(yīng)運(yùn)而生。

在EONs中,帶寬資源規(guī)劃的高靈活性是其彈性概念的重要體現(xiàn)之一,所涉及的關(guān)鍵技術(shù)稱為路由與頻譜分配(routing and spectrum allocation,RSA)算法。迄今為止,有關(guān)RSA算法的研究已經(jīng)較為深入,但當(dāng)前公開(kāi)發(fā)表的相關(guān)綜述性文章偏于陳舊,并且詳述的大多為靜態(tài)性算法,即業(yè)務(wù)需求均為已知。然而,未來(lái)應(yīng)用中網(wǎng)絡(luò)業(yè)務(wù)流量將呈現(xiàn)出較強(qiáng)的突發(fā)性和不確定性,因此對(duì)動(dòng)態(tài)求解算法的深入總結(jié)概括可以為后續(xù)研究人員提供更有實(shí)用價(jià)值的參考。本文首先簡(jiǎn)要介紹EONs的概念內(nèi)涵,接著對(duì)RSA問(wèn)題展開(kāi)描述,然后分別從靜態(tài)和動(dòng)態(tài)特性入手,基于精確算法、智能優(yōu)化算法、啟發(fā)式算法以及學(xué)習(xí)型算法4個(gè)大類對(duì)近5年來(lái)RSA算法的最新研究現(xiàn)狀進(jìn)行總結(jié)剖析,最后指出RSA算法的未來(lái)發(fā)展方向。

1 彈性光網(wǎng)絡(luò)

作為下一代最具前景的光傳輸網(wǎng)絡(luò),EONs的概念起源于頻譜可切片彈性光連接網(wǎng)絡(luò)(spectrum-sliced elastic optical path network, SLICE),通過(guò)在光頻域中引入靈活的粒度,提升頻譜資源的利用效率以及網(wǎng)絡(luò)的可擴(kuò)展性。

EONs的核心是O-OFDM技術(shù),這是一種多載波調(diào)制技術(shù),可以將高速數(shù)據(jù)流調(diào)制在相互正交的低速子載波上進(jìn)行傳輸。如圖1所示,與需要在波長(zhǎng)之間設(shè)置固定信道間隔來(lái)消除干擾的WDM技術(shù)相比,OFDM由于正交性而允許單個(gè)子載波的頻譜重疊,節(jié)約了帶寬資源。同時(shí),OFDM通過(guò)靈活的粒度聚合服務(wù)可以支持從Gbps到Tbps等多種數(shù)據(jù)速率,并能夠根據(jù)傳輸質(zhì)量調(diào)整子載波數(shù)量和調(diào)制格式,完成高效的頻譜分配,實(shí)現(xiàn)了動(dòng)態(tài)帶寬的擴(kuò)展與收縮,增大了系統(tǒng)容量。在傳輸流量不足時(shí),OFDM還可關(guān)閉某些子載波來(lái)節(jié)省功耗。此外,每個(gè)子載波所調(diào)制符號(hào)的持續(xù)時(shí)間比相同總數(shù)據(jù)速率的單載波系統(tǒng)的持續(xù)時(shí)間長(zhǎng)得多,縮減了OFDM信號(hào)的周期。

圖1 WDM與OFDM頻譜劃分示例

EONs的基礎(chǔ)網(wǎng)絡(luò)架構(gòu)如圖2所示,主要涉及兩大類節(jié)點(diǎn):一類是處在網(wǎng)絡(luò)邊緣位置上,連接用戶端和中心網(wǎng)絡(luò)的帶寬可變收發(fā)器(bandwidth-variable transponder, BVT);另一類是處在網(wǎng)絡(luò)中心位置上,連接BVT的帶寬可變波長(zhǎng)交叉連接器(bandwidth-variable wavelength cross-connector, BV-WXC)。工作時(shí),BVT依據(jù)用戶的業(yè)務(wù)需求配置子載波個(gè)數(shù)并選取調(diào)制方式,以此產(chǎn)生合適的光信號(hào);BV-WXC對(duì)接收的光信號(hào)進(jìn)行連續(xù)頻譜分割和多粒度交換,以完成相應(yīng)信號(hào)到下一節(jié)點(diǎn)的傳送。通過(guò)上述兩類節(jié)點(diǎn)的配合,最終能夠在EONs中以高頻譜效率建立起端到端的靈活光路徑。

圖2 EONs基礎(chǔ)架構(gòu)

2 RSA問(wèn)題

RSA問(wèn)題最早由Jinno等人于2009年和EONs的概念一同提出,是指根據(jù)用戶需求在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間找到一條合適的光路徑,并為此光路請(qǐng)求分配相應(yīng)的頻譜資源,目的是滿足某種最優(yōu)的性能指標(biāo)(如阻塞率最低、頻譜利用率最高等)。

在EONs中,頻譜資源的最小分配單元稱為頻隙(frequency slot, FS),多個(gè)連續(xù)FS的組合稱為FS塊(FS block, FSB),從簡(jiǎn)化網(wǎng)絡(luò)設(shè)計(jì)的角度出發(fā),單個(gè)FS的粒度大小通常被設(shè)置為12.5 GHz。頻譜資源在分配時(shí)需要遵循3個(gè)最基本的約束條件。

(1) 頻譜連續(xù)性約束:如果某業(yè)務(wù)請(qǐng)求需要個(gè)FS,則必須為其分配個(gè)連續(xù)的FS。

(2) 頻譜一致性約束:建立業(yè)務(wù)請(qǐng)求對(duì)應(yīng)的端到端光路徑時(shí),必須在該路徑所經(jīng)過(guò)的每條鏈路上分配位置相同的個(gè)連續(xù)FS。

(3) 頻譜不重疊約束:同一條鏈路中任意兩個(gè)已占用FSB之間不可以出現(xiàn)FS重疊的情況,即同一個(gè)頻隙不能同時(shí)被分配給多個(gè)業(yè)務(wù)。

應(yīng)用圖3所示的例子對(duì)上述3項(xiàng)約束內(nèi)涵加以解釋。圖3中,上半部分表示一個(gè)結(jié)構(gòu)簡(jiǎn)單的EONs,下半部分表示當(dāng)前時(shí)刻網(wǎng)內(nèi)各條鏈路上頻譜資源的使用情況(白色代表未被占用,灰色代表已被占用)。假設(shè)此時(shí)需要建立由節(jié)點(diǎn)到節(jié)點(diǎn)的一條光路請(qǐng)求,該請(qǐng)求占用2個(gè)FS。通過(guò)判斷發(fā)現(xiàn),由于在鏈路1和鏈路3中不存在相同位置上的連續(xù)兩個(gè)空閑FS,因此無(wú)法選擇——這條路徑。相比之下,在鏈路1、鏈路2和鏈路4中對(duì)應(yīng)位置索引為1和2的頻隙是連續(xù)(滿足連續(xù)性約束)且空閑的(滿足不重疊約束)以及對(duì)齊的(滿足一致性約束),從而可以選取路徑———來(lái)建立光路請(qǐng)求。

圖3 頻譜連續(xù)性約束、一致性約束和不重疊約束示例

經(jīng)過(guò)上述討論可以看出,EONs中網(wǎng)絡(luò)資源的規(guī)劃從單個(gè)波長(zhǎng)細(xì)化到了頻譜層面,精細(xì)的頻譜劃分粒度導(dǎo)致整個(gè)網(wǎng)絡(luò)范圍內(nèi)需要管理的資源數(shù)量變得巨大;加之存在連續(xù)性、一致性以及保護(hù)帶寬等更嚴(yán)苛的約束限制,使得每條光路徑的建立都會(huì)在一定程度上改變網(wǎng)內(nèi)資源的分布情況,進(jìn)而影響到業(yè)務(wù)的頻譜分配結(jié)果,這種緊密的耦合關(guān)系進(jìn)一步增大了實(shí)際應(yīng)用中資源規(guī)劃的復(fù)雜程度,從而加劇了RSA問(wèn)題的求解難度。同時(shí),RSA問(wèn)題已被證明是一種非確定性多項(xiàng)式(non-deterministic, NP)難問(wèn)題,即不存在多項(xiàng)式時(shí)間算法進(jìn)行最優(yōu)化求解。

當(dāng)前,基于RSA問(wèn)題的多種復(fù)雜變體形式也備受關(guān)注。如根據(jù)不同的路徑長(zhǎng)度和傳輸質(zhì)量采用不同的調(diào)制格式時(shí),RSA問(wèn)題演變?yōu)榱寺酚?、調(diào)制與頻譜分配(routing, modulation, and spectrum assignment, RMSA)問(wèn)題;考慮動(dòng)態(tài)建立和拆除光路產(chǎn)生的頻譜碎片時(shí),RSA問(wèn)題則變成了頻譜碎片感知RSA(fragmentation aware RSA, FA-RSA)問(wèn)題;依照業(yè)務(wù)流類型的不同,RSA問(wèn)題又可以劃分為單播(unicast)、任播(anycast)以及組播(multicast)RSA問(wèn)題。此外,還包括流量疏導(dǎo)RSA(traffic grooming with RSA, TG-RSA)問(wèn)題、生存性 RSA(survivability RSA, S-RSA)問(wèn)題等。

3 RSA算法

針對(duì)RSA這一關(guān)鍵問(wèn)題,根據(jù)業(yè)務(wù)請(qǐng)求是否為已知,將對(duì)應(yīng)的求解算法歸為兩大類,分別是靜態(tài)RSA算法(業(yè)務(wù)請(qǐng)求提前給定)以及動(dòng)態(tài)RSA算法(業(yè)務(wù)請(qǐng)求隨機(jī)到達(dá)),如圖4所示。

圖4 RSA配算法分類圖

3.1 靜態(tài)RSA算法

在靜態(tài)RSA算法中,輸入包括一組源節(jié)點(diǎn)、目的節(jié)點(diǎn)和帶寬需求均已知的業(yè)務(wù)請(qǐng)求,輸出的是在離線狀態(tài)下為每個(gè)請(qǐng)求所選擇的光路徑以及指定的連續(xù)FS資源,優(yōu)化目標(biāo)一般為最小化頻譜資源占用總量。

3.1.1 精確算法

為了深入解析RSA問(wèn)題的結(jié)構(gòu)特性并求取最優(yōu)化結(jié)果,整數(shù)線性規(guī)劃(integer linear programming, ILP)方法被提出用以建立問(wèn)題模型。其中,文獻(xiàn)[21-24]詳述了多種相關(guān)的ILP模型,這是在早期階段依據(jù)不同應(yīng)用背景、不同優(yōu)化目標(biāo)以及不同假設(shè)條件所提出的。在此基礎(chǔ)之上,文獻(xiàn)[25]根據(jù)定義決策變量的表達(dá)含義不同(即鏈路資源和FS資源的占用情況是用一組變量聯(lián)合表示,還是用兩組變量分別表示),共建立了4個(gè)基礎(chǔ)性的ILP模型并衍生出十多種變體形式,通過(guò)分析各模型所涉及變量與約束的數(shù)量級(jí),明確了模型的復(fù)雜度,最后利用數(shù)字優(yōu)化技術(shù)CPLEX軟件求解測(cè)試算例,對(duì)比各模型的性能,總結(jié)出其適用性。

當(dāng)問(wèn)題規(guī)模稍有增大時(shí),僅依靠求解器是無(wú)法在可行時(shí)間內(nèi)得出最佳解決方案的,為此一些精確算法被引入以提升求解效率,包括列生成法(column generation, CG)用于線性松弛模型求出問(wèn)題下界(lower bound, LB),或利用分支定界法(branch and bound, BB)、分支定價(jià)法(branch and price, BP)等直接求取整數(shù)解。由于具備求解大規(guī)模變量問(wèn)題的優(yōu)良特性,CG被廣泛采用,基本思路為:首先將“列”定義為可滿足業(yè)務(wù)請(qǐng)求的一種候選光路結(jié)構(gòu),該結(jié)構(gòu)包含鏈路與FS占用信息,通過(guò)啟發(fā)式規(guī)則首先獲得一組初始列,然后根據(jù)建立的光路生成子問(wèn)題模型(如最短路徑模型、最小化平均頻譜使用數(shù)量模型),查找并添加新列以提高求解質(zhì)量。此外,BP因?yàn)榻Y(jié)合了分支定界的求整特性與列生成的解大規(guī)模特性,也被引入到RSA問(wèn)題的求解中,并且通過(guò)相關(guān)啟發(fā)式方法的配合(如使用模擬退火(simulated annealing, SA)、貪婪規(guī)則、遺傳算法(genetic algorithm, GA)改善解方案的上界,使用松弛法則改善解方案的下界),提升了算法的求解性能,使其能夠解決商用求解器(如CPLEX)難以求出的較大規(guī)模問(wèn)題實(shí)例。

3.1.2 啟發(fā)式算法

利用精確算法固然能得到最優(yōu)解,但是隨著網(wǎng)絡(luò)規(guī)模與業(yè)務(wù)數(shù)量的進(jìn)一步增加,問(wèn)題對(duì)應(yīng)的復(fù)雜度會(huì)不斷提升,導(dǎo)致求解時(shí)間代價(jià)變得非常昂貴。比如,對(duì)于一種含有14個(gè)節(jié)點(diǎn)、46條鏈路的大型網(wǎng)絡(luò)結(jié)構(gòu)而言,采用ILP模型是無(wú)法在有效時(shí)間內(nèi)輸出可行結(jié)果的。因此,啟發(fā)式算法的提出對(duì)于在有限時(shí)間內(nèi)獲取問(wèn)題的可行解具有極為重要的意義。

從RSA問(wèn)題結(jié)構(gòu)的角度出發(fā),關(guān)于啟發(fā)式算法的設(shè)計(jì),通常做法是將其分為兩個(gè)獨(dú)立的子算法進(jìn)行研究,包括路由選擇子算法與頻譜分配子算法,稱為兩步法:首先為每個(gè)業(yè)務(wù)在光網(wǎng)絡(luò)中進(jìn)行選路,常用的策略包括固定路由(fixed routing, FR)、固定備選路由(fixed alternate routing, FAR)以及自適應(yīng)路由(adaptive routing, AR)等;接著依據(jù)所選路徑的狀態(tài)為其分配連續(xù)可用的FS,常用的策略包括首次適配(first fit, FF)、尾部適配(last fit, LF)、隨機(jī)適配(random fit, RF)以及精確適配(exact fit, EF)等。此外,還有綜合考慮兩類子算法特性的方式,通過(guò)采用貪婪策略或基于學(xué)習(xí)的規(guī)則同時(shí)進(jìn)行路由選擇與頻譜資源查找,稱為一步法。本節(jié)只涉及兩步法和一步法中用于靜態(tài)RSA算法設(shè)計(jì)的部分內(nèi)容,下節(jié)會(huì)重點(diǎn)介紹其在動(dòng)態(tài)RSA算法中的應(yīng)用。

根據(jù)以上多種基礎(chǔ)性策略,一些更為復(fù)雜有效的啟發(fā)式算法被提出。文獻(xiàn)[39]從提升能量效率和降低業(yè)務(wù)阻塞率的角度考慮,設(shè)計(jì)了一種基于能量感知的改進(jìn)RSA算法。文獻(xiàn)[40]以各FS對(duì)齊程度為考慮,提出了一種首尾精確適配(first-last-exact fit, FLEF)策略,目的就是為了增加連續(xù)可用的且對(duì)齊的FS數(shù)量,從而提升頻譜使用效率。文獻(xiàn)[41]中介紹了一種基于頻譜優(yōu)先的分層算法,該算法采用一步式貪婪策略,以業(yè)務(wù)的FS需求為基礎(chǔ),通過(guò)查找可用鏈路并構(gòu)建層級(jí)子圖的方式實(shí)現(xiàn)了路由與頻譜資源的聯(lián)合分配。文獻(xiàn)[42]利用節(jié)點(diǎn)度數(shù)設(shè)計(jì)了具有分光能力的節(jié)點(diǎn)選擇策略,并提出了一種預(yù)計(jì)算最短路徑樹(shù)的RSA算法并驗(yàn)證了其有效性。此外,存在部分研究以靜態(tài)RSA問(wèn)題特性為依據(jù),嘗試借鑒傳統(tǒng)的優(yōu)化調(diào)度理論進(jìn)行計(jì)算。比如,文獻(xiàn)[43-44]將靜態(tài)RSA問(wèn)題映射為多處理器調(diào)度模型,并通過(guò)設(shè)計(jì)表調(diào)度算法(list scheduling algorithm, LSA)進(jìn)行求解;文獻(xiàn)[45]建立了靜態(tài)RSA問(wèn)題的圖染色模型,并分別針對(duì)鏈狀網(wǎng)絡(luò)和環(huán)狀網(wǎng)絡(luò)提出了有效的頻譜分配算法。具體總結(jié)如圖5所示。

圖5 靜態(tài)啟發(fā)式策略

3.1.3 智能優(yōu)化算法

除了上述基于直觀或經(jīng)驗(yàn)構(gòu)造出的啟發(fā)式算法外,還有一類是根據(jù)人體智能、生物群體社會(huì)性或自然現(xiàn)象規(guī)律總結(jié)出的方法,稱之為智能優(yōu)化算法,也稱元啟發(fā)式算法。與啟發(fā)式算法在可接受時(shí)間內(nèi)給出待解決優(yōu)化問(wèn)題的一個(gè)可行解不同,智能優(yōu)化算法在任務(wù)規(guī)模變得更大、約束條件變得更加苛刻時(shí)能夠具有良好的問(wèn)題探索能力和收斂效率,尤其是在解決NP難問(wèn)題時(shí),智能優(yōu)化算法可以有效應(yīng)對(duì)“組合爆炸”現(xiàn)象, 獲取到問(wèn)題的滿意解。

智能優(yōu)化算法目前已廣泛應(yīng)用于交通、醫(yī)療、工業(yè)制造等多個(gè)領(lǐng)域。其中,采用經(jīng)典之一的GA求解靜態(tài)RSA問(wèn)題已得到深入研究。為了建立完備的路由空間,文獻(xiàn)[46]提出了一種基于優(yōu)先權(quán)編碼尋路的GA,并結(jié)合最大化頻譜重合度原則來(lái)降低業(yè)務(wù)阻塞率。在考慮單播與任播業(yè)務(wù)資源聯(lián)合分配的需求下,文獻(xiàn)[47]將局部搜索引入GA中以改善RSA問(wèn)題的求解效率。在GA的基礎(chǔ)框架之下,文獻(xiàn)[48]根據(jù)組播業(yè)務(wù)特性設(shè)計(jì)了合理的選擇與交叉算子,有效提升了解的質(zhì)量。為了降低種群維護(hù)的高計(jì)算成本,文獻(xiàn)[49]提出了一種動(dòng)態(tài)子種群數(shù)量控制策略來(lái)設(shè)計(jì)相應(yīng)的RSA算法。文獻(xiàn)[50]根據(jù)GA的思想,分別提出了改進(jìn)資源分配算法來(lái)處理純單播業(yè)務(wù)以及混合資源分配算法來(lái)處理單播與組播混合業(yè)務(wù)。文獻(xiàn)[51]結(jié)合深度神經(jīng)網(wǎng)絡(luò)與GA,設(shè)計(jì)了一種基于軟故障感知的RSA算法。當(dāng)考慮同時(shí)優(yōu)化如FS占用總數(shù)、服務(wù)質(zhì)量等多個(gè)目標(biāo)時(shí),文獻(xiàn)[52-54]提出了多目標(biāo)GA來(lái)求解RSA問(wèn)題。

此外,其他一些成熟的智能優(yōu)化算法框架也被引入到靜態(tài)RSA算法的設(shè)計(jì)中,包括禁忌搜索(tabu search, TS)、粒子群優(yōu)化(particle swarm optimization, PSO)、差分進(jìn)化(differential evolution, DE)、SA、蜂群優(yōu)化(bee colony optimization, BCO)等。

以上總結(jié)了近年來(lái)主要的靜態(tài)RSA算法,而未來(lái)大多面臨的是隨機(jī)到來(lái)的業(yè)務(wù)請(qǐng)求,網(wǎng)絡(luò)環(huán)境會(huì)變得愈發(fā)復(fù)雜,因此動(dòng)態(tài)RSA算法的研究更加符合EONs的發(fā)展趨勢(shì),同時(shí)也更具挑戰(zhàn)性。

3.2 動(dòng)態(tài)RSA算法

在動(dòng)態(tài)RSA算法中,輸入為隨機(jī)到達(dá)的業(yè)務(wù)請(qǐng)求(包括源節(jié)點(diǎn)、目的節(jié)點(diǎn)、帶寬需求、到達(dá)時(shí)間和持續(xù)時(shí)間等屬性),輸出的是根據(jù)當(dāng)前網(wǎng)絡(luò)狀態(tài)為每項(xiàng)業(yè)務(wù)請(qǐng)求在線選擇的光路徑以及指定的連續(xù)頻譜資源,優(yōu)化目標(biāo)一般為最小化業(yè)務(wù)阻塞率。

3.2.1 啟發(fā)式算法

動(dòng)態(tài)RSA問(wèn)題通常涉及到業(yè)務(wù)的時(shí)間屬性,即隨著時(shí)間推移,光路連接會(huì)不斷被建立與釋放,由此導(dǎo)致網(wǎng)內(nèi)頻譜資源的狀態(tài)總是處于變化之中,極大增加了網(wǎng)絡(luò)資源的優(yōu)化難度。經(jīng)過(guò)工程實(shí)踐驗(yàn)證,啟發(fā)式算法目前是解決動(dòng)態(tài)優(yōu)化問(wèn)題的一類有效技術(shù)。區(qū)別于第3.1.2節(jié)中的內(nèi)容,本節(jié)將著重介紹啟發(fā)式算法在動(dòng)態(tài)RSA問(wèn)題中的應(yīng)用。

在動(dòng)態(tài)場(chǎng)景下,業(yè)務(wù)的隨機(jī)到來(lái)和離去使得光路連接處于不斷的拆建過(guò)程之中,路由狀態(tài)復(fù)雜多變;同時(shí),頻譜資源也隨之被反復(fù)占用與釋放,進(jìn)而產(chǎn)生了大量難以滿足一致性和連續(xù)性約束且無(wú)法為后續(xù)業(yè)務(wù)提供服務(wù)的小頻譜塊,稱之為頻譜碎片。迄今為止,絕大多數(shù)動(dòng)態(tài)RSA算法的研究都是以路由狀態(tài)和頻譜碎片作為最基礎(chǔ)的啟發(fā)式信息。圖6所示為動(dòng)態(tài)啟發(fā)式RSA算法的基本框架。

圖6 動(dòng)態(tài)啟發(fā)式算法框架

(1) 頻譜碎片感知

頻譜碎片感知是指當(dāng)業(yè)務(wù)到達(dá)時(shí)，通過(guò)某些策略預(yù)判出頻譜塊最適合的分配位置，所謂最適合，即盡可能使分配后剩余的空閑FS保持連續(xù)且齊整，以承載更多后續(xù)業(yè)務(wù)，達(dá)到最小化碎片產(chǎn)生數(shù)量的目的。

文獻(xiàn)[62]以指定時(shí)間窗內(nèi)到達(dá)業(yè)務(wù)的帶寬需求為基礎(chǔ)定義了業(yè)務(wù)的優(yōu)先級(jí)指標(biāo)，同時(shí)依據(jù)當(dāng)前光網(wǎng)絡(luò)中所有空閑FSB的大小找出中位數(shù)所在，接著通過(guò)判斷此中位數(shù)與各業(yè)務(wù)帶寬需求的關(guān)系并結(jié)合業(yè)務(wù)優(yōu)先級(jí)，進(jìn)而確定出最終的頻譜分配方案。文獻(xiàn)[63]采用了一種可變分組機(jī)制，該機(jī)制首先依據(jù)帶寬需求將業(yè)務(wù)分為不同種類，接著對(duì)應(yīng)不同業(yè)務(wù)類型將鏈路總頻段劃分為多個(gè)組，每個(gè)組僅需明確其起始FS位置，并規(guī)定相鄰兩組之間的空閑FS可根據(jù)實(shí)際需要合并至任意一組中；此外還定義了組規(guī)模的概念與計(jì)算公式，以此為動(dòng)態(tài)業(yè)務(wù)選取最優(yōu)路徑與頻譜塊。文獻(xiàn)[64]首先采用了條最短路算法離線計(jì)算業(yè)務(wù)路由，接著定義了塊成本函數(shù)的概念來(lái)評(píng)估可用的候選頻譜塊，該函數(shù)的取值基于鏈路中相鄰FS的狀態(tài)而定。文獻(xiàn)[65]引入了頻譜候選窗的概念來(lái)為新到達(dá)業(yè)務(wù)篩選可用的FSB，同時(shí)基于精確適配策略定義了空閑頻譜連續(xù)度的指標(biāo)，并以此為依據(jù)選出最適合此業(yè)務(wù)的頻譜資源。文獻(xiàn)[66]定義了鄰接度和鄰接度降低的概念分別來(lái)衡量空閑FSB的鄰接程度以及使用過(guò)后的鄰接變化程度，并據(jù)此提出了最小化路徑鄰接度降低和鏈路鄰接度降低算法。

(2) 頻譜碎片重構(gòu)

頻譜碎片重構(gòu)也稱碎片整理，即通過(guò)網(wǎng)絡(luò)中斷的方式，利用一定手段對(duì)已有光路徑進(jìn)行重新建立，或?qū)σ逊峙漕l譜進(jìn)行位置搬移，進(jìn)而達(dá)到最大化碎片集中整合的目的。

文獻(xiàn)[67]以定義頻譜連續(xù)度的預(yù)設(shè)閾值為啟動(dòng)機(jī)制，采用頻譜搬移的思想提出了基于滑動(dòng)窗口機(jī)制下的重路由算法；同時(shí)，根據(jù)網(wǎng)絡(luò)的實(shí)時(shí)拓?fù)錉顟B(tài)，利用介數(shù)分析法評(píng)估節(jié)點(diǎn)的重要度并確定出關(guān)鍵鏈路，由此提出了基于關(guān)鍵鏈路的重路由算法。文獻(xiàn)[68]在綜合考慮局部頻譜資源狀態(tài)和業(yè)務(wù)連接需求的情況下，巧妙設(shè)計(jì)了路徑整理前后的頻譜可用度、阻塞業(yè)務(wù)需求度等計(jì)算公式，并由此提出了基于策略的頻譜整理比較觸發(fā)機(jī)制以及基于所選路徑的阻塞觸發(fā)頻譜碎片整理算法。為了找尋頻譜分配結(jié)果的最優(yōu)性與頻譜重配置所導(dǎo)致的網(wǎng)絡(luò)中斷次數(shù)之間的平衡關(guān)系，文獻(xiàn)[69]通過(guò)建立一種新穎的混合整數(shù)線性規(guī)劃模型來(lái)為新到達(dá)業(yè)務(wù)選取合適的路徑，并基于首次適配策略提出了一種動(dòng)態(tài)啟發(fā)式算法來(lái)確定業(yè)務(wù)所占的FS位置。

(3) 路由狀態(tài)感知

所謂路由狀態(tài)感知，即通過(guò)對(duì)候選鏈路或光路徑的狀態(tài)信息(如能耗、距離、負(fù)載、碎片化程度等)進(jìn)行評(píng)估，并基于評(píng)估結(jié)果為新到達(dá)業(yè)務(wù)選取一條合適的光路徑，以達(dá)到最小化路由狀態(tài)受影響的目的。

針對(duì)傳輸速率實(shí)時(shí)變化的業(yè)務(wù),文獻(xiàn)[70]提出了兩種頻譜擴(kuò)展/縮減方案用于網(wǎng)絡(luò)性能分析,以確定出各方案實(shí)施后的網(wǎng)絡(luò)阻塞概率,并基于條最短路策略設(shè)計(jì)了路徑最小負(fù)載的啟發(fā)式規(guī)則。文獻(xiàn)[71]以網(wǎng)絡(luò)能耗為考慮,提出了持續(xù)時(shí)間感知的能效路由算法求取代價(jià)最小的光路徑,隨后根據(jù)業(yè)務(wù)與所選光路在時(shí)間域上的關(guān)系, 分配時(shí)間差較小且頻譜連貫度最高的頻譜塊作為承載資源。文獻(xiàn)[72]提出了一種固定/備用選路機(jī)制,該機(jī)制能夠?qū)崟r(shí)構(gòu)建節(jié)點(diǎn)對(duì)間的最短和次最短路徑信息,并通過(guò)定義頻譜碎片規(guī)模的權(quán)值量化公式選取合適的路徑,接著基于精確適配與最小可用原則設(shè)計(jì)了頻譜動(dòng)態(tài)匹配策略?？紤]在每條鏈路具有多根光纖的前提下,文獻(xiàn)[73]首先離線計(jì)算出每個(gè)節(jié)點(diǎn)對(duì)之間可行的候選路徑及其概率分布,接著提出了一種基于后續(xù)狀態(tài)感知和路徑選擇概率的頻譜分配算法。文獻(xiàn)[74]提出了一種距離自適應(yīng)路徑策略,該策略同步考慮了各條備選路徑的跳數(shù)及其可達(dá)的最高調(diào)制等級(jí),并以此為基礎(chǔ)確定出終選路徑。文獻(xiàn)[75]通過(guò)設(shè)置光路徑對(duì)應(yīng)跳數(shù)的增量閾值,提出了一種基于約束的低索引塊策略,該策略主要考慮在跳數(shù)較少的路徑上分配起始索引較低的頻譜塊,而當(dāng)某一路徑的跳數(shù)大于另一條但可用頻譜塊的最低起始索引又小于另一條時(shí),如果其跳數(shù)之差不大于預(yù)設(shè)閾值,則優(yōu)先選取低索引FSB及所在路徑。文獻(xiàn)[76]以高調(diào)制等級(jí)作為路徑的首選標(biāo)準(zhǔn),其次定義了外部碎片指標(biāo),考慮當(dāng)多條路徑調(diào)制等級(jí)相同時(shí)將選取該指標(biāo)最小的一條,同時(shí)還考慮當(dāng)多條路徑的上述指標(biāo)也均相同時(shí),則基于最小跳數(shù)作出路由決策,最后又結(jié)合首次適配與尾部適配策略提出了一種首尾混合適配頻譜分配方案?？紤]到光信號(hào)質(zhì)量易受物理層損耗的影響,文獻(xiàn)[77]引入了跨層優(yōu)化的思想,首先通過(guò)對(duì)鏈路中光信噪比與色散這兩項(xiàng)參數(shù)值的估計(jì)來(lái)評(píng)估其狀態(tài),接著基于評(píng)估結(jié)果提出了鏈路狀態(tài)感知路由算法來(lái)搜索滿足傳輸質(zhì)量要求的可行路徑,同時(shí)設(shè)計(jì)了碎片減少算法來(lái)分配頻譜資源。在光纖鏈路可以改變調(diào)制格式的前提下,文獻(xiàn)[78]優(yōu)先選擇節(jié)點(diǎn)數(shù)最少的路徑或在節(jié)點(diǎn)數(shù)相同時(shí)選擇距離之和最小的路徑,并將此路徑劃分成一定數(shù)目的子路徑,然后采用距離自適應(yīng)調(diào)制技術(shù)為每條子路徑分配頻譜資源。

(4) 其他策略

不同于上述3種常用的動(dòng)態(tài)啟發(fā)式思想,還有部分其他新穎的策略被提出。

例如,考慮不同網(wǎng)絡(luò)應(yīng)用在時(shí)延敏感度和帶寬感知度的差異性,文獻(xiàn)[79]構(gòu)建了3類典型的業(yè)務(wù)請(qǐng)求模型,通過(guò)在時(shí)間維度上采用離散化處理的方式進(jìn)行網(wǎng)絡(luò)操作,并依據(jù)各類業(yè)務(wù)特性設(shè)計(jì)了多種啟發(fā)式策略,由此生成了對(duì)應(yīng)的帶寬資源動(dòng)態(tài)調(diào)度算法。文獻(xiàn)[80]以分層圖模型為基礎(chǔ),對(duì)其進(jìn)行修改并建立了一種新的過(guò)濾圖來(lái)表示網(wǎng)絡(luò)實(shí)時(shí)狀態(tài),接著通過(guò)采用首次適配與最短路的思想設(shè)計(jì)出兩種動(dòng)態(tài)啟發(fā)式算法,此外還推導(dǎo)出一個(gè)具有較高精度的分析模型以估計(jì)所需的分層圖數(shù)量。文獻(xiàn)[81]通過(guò)建立一種線性規(guī)劃模型來(lái)離線解決路由子問(wèn)題,此模型可確保所有鏈路的阻塞水平維持在一個(gè)閾值域內(nèi),且該步計(jì)算耗時(shí)為可接受的秒級(jí)范圍,并基于獲取的路由信息采用首次適配策略在線分配頻譜。為了應(yīng)對(duì)業(yè)務(wù)分配路徑不均勻的現(xiàn)象,文獻(xiàn)[82]設(shè)計(jì)了一種基于節(jié)點(diǎn)重要度的路由選擇方法,該方法以犧牲業(yè)務(wù)路徑距離為代價(jià),將大量集中于關(guān)鍵節(jié)點(diǎn)上的業(yè)務(wù)安排至其他節(jié)點(diǎn),并利用精確適配策略與首次適配策略相結(jié)合的方式完成頻譜分配。文獻(xiàn)[83]考慮在傳統(tǒng)WDM光網(wǎng)絡(luò)向EONs轉(zhuǎn)型的過(guò)渡期間,主要是以固定柵格與靈活柵格并存的混合形式出現(xiàn),由此設(shè)計(jì)了一種基于混合網(wǎng)格感知的動(dòng)態(tài)資源規(guī)劃算法。

3.2.2 學(xué)習(xí)型算法

當(dāng)前,啟發(fā)式算法仍是求解各類動(dòng)態(tài)性優(yōu)化問(wèn)題的常規(guī)方法,具有較強(qiáng)的適用性,但由于其受限在僅能維持某一種或某幾種特定的求解策略,這對(duì)于未來(lái)具有高動(dòng)態(tài)特性的EONs而言,將無(wú)法全面感知愈發(fā)復(fù)雜多變的環(huán)境狀態(tài),從而極大影響到資源的使用效率和業(yè)務(wù)請(qǐng)求的完成效率。

近年來(lái)隨著人工智能技術(shù)的崛起,以數(shù)據(jù)和知識(shí)為驅(qū)動(dòng)的計(jì)算智能、機(jī)器學(xué)習(xí)、深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)等一系列學(xué)習(xí)型算法迎來(lái)了發(fā)展高潮,并且已成功應(yīng)用于光網(wǎng)絡(luò)領(lǐng)域中的多個(gè)方面,如流量預(yù)估、故障檢測(cè)、業(yè)務(wù)分類、調(diào)制格式識(shí)別、網(wǎng)絡(luò)運(yùn)營(yíng)與規(guī)劃等,相關(guān)綜述性總結(jié)可查閱文獻(xiàn)[84-85]。

然而迄今為止,有關(guān)學(xué)習(xí)型算法求解光網(wǎng)絡(luò)中動(dòng)態(tài)資源分配問(wèn)題的研究開(kāi)展相對(duì)較少。經(jīng)過(guò)分析,本文將其歸為兩類,一類稱為間接學(xué)習(xí)型,另一類稱為直接學(xué)習(xí)型。

(1) 間接學(xué)習(xí)型

所謂間接學(xué)習(xí),即首先利用學(xué)習(xí)型算法充分挖掘光網(wǎng)絡(luò)中承載的歷史業(yè)務(wù)數(shù)據(jù),進(jìn)而對(duì)未來(lái)業(yè)務(wù)進(jìn)行預(yù)測(cè),并在此基礎(chǔ)上選取光路徑以及分配頻譜資源。例如,文獻(xiàn)[86]中引入了反向傳播神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)未來(lái)業(yè)務(wù)的到達(dá)時(shí)間和持續(xù)時(shí)間,提出了基于預(yù)測(cè)的最小綜合權(quán)重算法以及基于蜂群引導(dǎo)原則的混合蟻群算法;文獻(xiàn)[87]探索了深度學(xué)習(xí)算法在數(shù)據(jù)中心光網(wǎng)絡(luò)中的應(yīng)用,設(shè)計(jì)了一種基于深度神經(jīng)網(wǎng)絡(luò)的業(yè)務(wù)預(yù)測(cè)策略,并提出了基于深度學(xué)習(xí)的RSA資源分配算法。

(2) 直接學(xué)習(xí)型

所謂直接學(xué)習(xí),即通過(guò)實(shí)時(shí)分析光網(wǎng)絡(luò)環(huán)境特性,采用學(xué)習(xí)型算法對(duì)網(wǎng)絡(luò)狀態(tài)開(kāi)展在線學(xué)習(xí),進(jìn)而完成由動(dòng)態(tài)業(yè)務(wù)輸入到分配資源輸出的直接映射,一種典型的學(xué)習(xí)框架如圖7所示。早在2008年,文獻(xiàn)[88]就將光突發(fā)交換網(wǎng)絡(luò)的路由與波長(zhǎng)分配問(wèn)題描述為強(qiáng)化學(xué)習(xí)領(lǐng)域中經(jīng)典的多臂老虎機(jī)問(wèn)題(multi-armed bandits problem, MABP),即考慮把路徑選擇與波長(zhǎng)分配視為老虎機(jī)中對(duì)其支臂的選取決策,并通過(guò)設(shè)計(jì)一種改進(jìn)的Q-learning算法進(jìn)行求解,以最大程度地減小突發(fā)損失概率。隨著深度強(qiáng)化學(xué)習(xí)技術(shù)的火熱發(fā)展,到了2019年,文獻(xiàn)[89]采用了一種高效的異步學(xué)習(xí)框架——異步優(yōu)勢(shì)動(dòng)作評(píng)價(jià)(asynchronous advantage actor-critic, A3C)算法來(lái)求解動(dòng)態(tài)路由、調(diào)制與頻譜分配問(wèn)題,其依據(jù)問(wèn)題特性設(shè)計(jì)了狀態(tài)空間、動(dòng)作空間、獎(jiǎng)勵(lì)機(jī)制以及深度神經(jīng)網(wǎng)絡(luò)模型,同時(shí)將資源預(yù)配置過(guò)程劃分成多個(gè)回合,并提出了一種基于滑動(dòng)窗口的靈活訓(xùn)練策略以減小累計(jì)獎(jiǎng)勵(lì)的震蕩,從而提升算法運(yùn)行的收斂性。

圖7 一種典型的直接學(xué)習(xí)型算法框架

以上即為近年來(lái)EONs中主要的RSA算法,具體總結(jié)如表1所示。

表1 路由與頻譜分配算法總結(jié)

4 結(jié) 論

本文首先從靜態(tài)和動(dòng)態(tài)角度入手對(duì)EONs中RSA算法進(jìn)行綜述,接著依據(jù)不同類型的優(yōu)化算法框架將其分別歸納為精確算法、智能優(yōu)化算法、啟發(fā)式算法以及學(xué)習(xí)型算法,同時(shí)通過(guò)分析每一類算法的求解特性與優(yōu)缺點(diǎn),對(duì)其又做了進(jìn)一步細(xì)致的分類與概括。

總的來(lái)講,隨著未來(lái)多樣化業(yè)務(wù)請(qǐng)求數(shù)量的急劇攀升,網(wǎng)絡(luò)環(huán)境必定會(huì)變得越發(fā)復(fù)雜,而作為下一代最具前景的光網(wǎng)絡(luò),EONs展現(xiàn)出了較多優(yōu)勢(shì),這些優(yōu)勢(shì)很大程度上則依賴于網(wǎng)絡(luò)資源的高效靈活分配。對(duì)此,本文將RSA算法的未來(lái)發(fā)展趨勢(shì)總結(jié)為以下幾點(diǎn)。

(1) 由靜態(tài)向動(dòng)態(tài)轉(zhuǎn)變

隨著數(shù)據(jù)業(yè)務(wù)量的指數(shù)級(jí)增長(zhǎng),光網(wǎng)絡(luò)的承載壓力勢(shì)必會(huì)大大增加,此時(shí)考慮業(yè)務(wù)的動(dòng)態(tài)時(shí)間屬性就顯得尤為重要,特別是針對(duì)大量突發(fā)性業(yè)務(wù)請(qǐng)求的產(chǎn)生與結(jié)束,這將直接導(dǎo)致資源配置難度的急劇攀升。為了更好適應(yīng)未來(lái)發(fā)展,有關(guān)動(dòng)態(tài)性RSA算法的研究還需深入開(kāi)展下去,包括對(duì)不同類型動(dòng)態(tài)問(wèn)題結(jié)構(gòu)(如多播、任播業(yè)務(wù)等)、算法解決思路(如資源預(yù)留、動(dòng)態(tài)重構(gòu)等)以及動(dòng)態(tài)算法性能(如魯棒性、自適應(yīng)性等)等的進(jìn)一步探索。當(dāng)然,靜態(tài)性方面的研究仍不可忽視,比如數(shù)學(xué)模型構(gòu)建的合適與否體現(xiàn)的是對(duì)一個(gè)或一類問(wèn)題本質(zhì)特性的掌握程度,這有助于實(shí)現(xiàn)算法設(shè)計(jì)由靜態(tài)向動(dòng)態(tài)的高效轉(zhuǎn)變。

(2) 由單目標(biāo)向多目標(biāo)轉(zhuǎn)變

在現(xiàn)實(shí)生活中,多目標(biāo)優(yōu)化問(wèn)題是普遍存在的,而且處于非常重要的地位。作為EONs中的一項(xiàng)關(guān)鍵技術(shù),RSA算法在應(yīng)用時(shí)也存在著多個(gè)目標(biāo),例如阻塞率最低、頻譜利用率最高、任務(wù)完成率最大、鏈路負(fù)載均衡等,這些目標(biāo)之間還可能具有一定的沖突性,并且對(duì)于不同的用戶偏好與工程背景,優(yōu)化目標(biāo)的側(cè)重程度也會(huì)有較大差異。同時(shí),當(dāng)前較為成熟的一些多目標(biāo)優(yōu)化手段在求解帶有復(fù)雜約束的大規(guī)模問(wèn)題時(shí)仍存在著計(jì)算復(fù)雜度高、優(yōu)化結(jié)果質(zhì)量較差等弊端,而EONs在未來(lái)必然會(huì)愈發(fā)復(fù)雜化,面對(duì)的業(yè)務(wù)規(guī)模也會(huì)成倍數(shù)擴(kuò)大。因此,研究高效的多目標(biāo)RSA算法能夠更加深入了解問(wèn)題內(nèi)涵,理清不同目標(biāo)間的相關(guān)性,從而為工程決策提供綜合性的優(yōu)化方案。

(3) 由基于策略規(guī)則向基于數(shù)據(jù)知識(shí)轉(zhuǎn)變

針對(duì)EONs中RSA問(wèn)題的求解,現(xiàn)有研究大多是從策略角度入手,通過(guò)構(gòu)造多種啟發(fā)式規(guī)則設(shè)計(jì)相應(yīng)算法,尤其對(duì)于動(dòng)態(tài)性問(wèn)題更是如此。雖然這類方法應(yīng)用廣泛且取得了不錯(cuò)的效果,但為了更進(jìn)一步提升算法優(yōu)化性能,獲得更快的資源配置速率,實(shí)現(xiàn)更高的動(dòng)態(tài)響應(yīng)能力,就要充分利用數(shù)據(jù)并通過(guò)學(xué)習(xí)從中獲取知識(shí),例如使用可以感知復(fù)雜EONs狀態(tài)的深度神經(jīng)網(wǎng)絡(luò)來(lái)學(xué)習(xí)RSA參數(shù)化策略,由此設(shè)計(jì)出高動(dòng)態(tài)網(wǎng)絡(luò)資源的協(xié)同調(diào)度機(jī)理與方法。因此,嘗試引入深度學(xué)習(xí)、深度強(qiáng)化學(xué)習(xí)等新興人工智能技術(shù)框架來(lái)求解RSA問(wèn)題,有助于生成基于任務(wù)需求數(shù)據(jù)與網(wǎng)絡(luò)行為知識(shí)的資源調(diào)度能力,以便支持高資源利用率網(wǎng)絡(luò)建設(shè),完成網(wǎng)絡(luò)自配置與自優(yōu)化,從而為實(shí)現(xiàn)真正智能的光網(wǎng)絡(luò)提供理論與算法支撐,這將成為未來(lái)的主要研究趨勢(shì)。