多芯光纖中串?dāng)_感知的路由頻譜分配算法

熊琪樂(lè)，劉煥淋，劉欣悅

(重慶郵電大學(xué) a.通信與信息工程學(xué)院; b.先進(jìn)制造工程學(xué)院，重慶 400065)

0 引 言

隨著5G移動(dòng)網(wǎng)絡(luò)、物聯(lián)網(wǎng)和云計(jì)算等新興技術(shù)的快速發(fā)展，多樣化和多元化的網(wǎng)絡(luò)業(yè)務(wù)使得以IP業(yè)務(wù)為代表的業(yè)務(wù)量呈現(xiàn)出指數(shù)級(jí)增長(zhǎng)[1]?；谡活l分復(fù)用技術(shù)的彈性光網(wǎng)絡(luò)(Elastic Optical Networks, EONs)和空分復(fù)用(Space Division Multiplexing, SDM)技術(shù)的應(yīng)用能更好地適應(yīng)多樣化的業(yè)務(wù)及傳輸容量需求[2-3]。本文主要研究多芯光纖(Multi-Core Fiber, MCF)承載的動(dòng)態(tài)業(yè)務(wù)下的路由頻譜纖芯分配(Routing, Spectrum and Core Allocation, RSCA)問(wèn)題。

文獻(xiàn)[4]提出的纖芯優(yōu)先級(jí)排序算法能在一定程度上避免芯間串?dāng)_(Inter Core Crosstalk, ICXT)問(wèn)題；文獻(xiàn)[5]提出了“四色原則”，進(jìn)一步對(duì)MCF進(jìn)行了分組操作；文獻(xiàn)[6]設(shè)計(jì)了一種可重構(gòu)的光分叉復(fù)用器，降低了SDM技術(shù)下可重構(gòu)分插復(fù)用器的結(jié)構(gòu)復(fù)雜度并減少了消耗的器件數(shù)目；文獻(xiàn)[7]分析了基于路徑型和鏈路型纖芯交換的區(qū)別；文獻(xiàn)[8]系統(tǒng)地介紹了ICXT的幾種類(lèi)型，能夠避免過(guò)保護(hù)現(xiàn)象。

基于以上分析，針對(duì)SDM-EONs下的資源分配問(wèn)題，本文提出了動(dòng)態(tài)路由和串?dāng)_感知算法，該算法不僅能夠根據(jù)動(dòng)態(tài)業(yè)務(wù)自適應(yīng)調(diào)整路由策略，同時(shí)還減少了ICXT的影響，降低了系統(tǒng)阻塞率并提高了吞吐量。

1 問(wèn)題描述

1.1 ICXT問(wèn)題

由于MCF的物理結(jié)構(gòu)特點(diǎn)，同一光纖內(nèi)的纖芯間沒(méi)有物理包層隔絕，在傳輸光信號(hào)時(shí)會(huì)因?yàn)楣夤β市孤┒鴮?dǎo)致ICXT問(wèn)題，而且串?dāng)_問(wèn)題會(huì)隨著業(yè)務(wù)量以及傳輸距離的增加而變得更加嚴(yán)重，限制了SDM技術(shù)所帶來(lái)的容量?jī)?yōu)勢(shì)，影響了網(wǎng)絡(luò)傳輸性能[9-11]。圖1所示為ICXT示意圖。

圖1 ICXT示意圖

目前，MCF中ICXT普遍被定義為

式中：h為ICXT增量；x、r、β和q分別為耦合系數(shù)、彎曲半徑、傳播常數(shù)和芯間距；XTav為ICXT平均值；n為相鄰纖芯數(shù)；L為光纖傳輸距離。

1.2 RSCA問(wèn)題

區(qū)別于傳統(tǒng)波分復(fù)用(Wavelength Division Multiplexing，WDM)網(wǎng)絡(luò)， EONs具有更加靈活的頻譜分配方式，能夠以更細(xì)粒度的頻隙(如12.5 GHz)代替WDM網(wǎng)絡(luò)的子載波(如100 GHz)，使得載波能夠更好地適應(yīng)不同類(lèi)型的業(yè)務(wù)需求，但與此同時(shí)，其資源分配算法也將從傳統(tǒng)的路由波長(zhǎng)分配(Routing Wavelength Allocation, RWA)問(wèn)題變?yōu)楦訌?fù)雜的路由頻譜分配(Routing Spectrum Allocation, RSA)問(wèn)題，其復(fù)雜度已被證明為非確定性多項(xiàng)式完備問(wèn)題。而隨著SDM(MCF)技術(shù)的引入，雖然其帶來(lái)了單模單芯光纖成倍的傳輸容量?jī)?yōu)勢(shì)，但空間維度的引入進(jìn)一步增加了原RSA問(wèn)題求解的復(fù)雜度，將原RSA問(wèn)題轉(zhuǎn)變?yōu)榱薘SCA問(wèn)題。因此，設(shè)計(jì)一個(gè)合理有效的啟發(fā)式算法不僅能夠降低算法的時(shí)間復(fù)雜度，同時(shí)還能夠高效可靠地利用現(xiàn)有的物理資源降低業(yè)務(wù)傳輸?shù)氖「怕?，提高資源利用率。

2 RSCA算法

2.1 動(dòng)態(tài)路由子算法

在資源分配的初始階段，首先應(yīng)該為到來(lái)的業(yè)務(wù)選擇傳輸路徑。而傳統(tǒng)的最短路徑算法是根據(jù)業(yè)務(wù)請(qǐng)求的源目的節(jié)點(diǎn)靜態(tài)地計(jì)算出最短跳數(shù)或最短物理距離的候選路徑，無(wú)法根據(jù)全網(wǎng)的負(fù)載和能耗情況做出動(dòng)態(tài)調(diào)整。

本算法首先設(shè)計(jì)了一個(gè)候選路徑優(yōu)先級(jí)排序公式，不僅考慮了物理跳數(shù)，同時(shí)還將動(dòng)態(tài)系統(tǒng)路徑和鏈路負(fù)載情況考慮了進(jìn)去：

路徑k頻譜利用率計(jì)算公式為

2.2 串?dāng)_感知算法

串?dāng)_感知算法的具體步驟如下：

步驟1:輸入：業(yè)務(wù)請(qǐng)求(s,d,r)，s、d、和r分別為源節(jié)點(diǎn)、目的節(jié)點(diǎn)和請(qǐng)求速率，纖芯優(yōu)先級(jí)分組集合Gi，對(duì)應(yīng)頻譜分區(qū)集合Si。選定候選路徑p。

步驟2:對(duì)于每條屬于p的鏈路li其中的每一個(gè)候選纖芯c,遍歷其頻譜資源，尋找能夠滿(mǎn)足請(qǐng)求速率為r的業(yè)務(wù)的空閑頻譜塊數(shù)目。若可用資源非空，則進(jìn)入步驟3，否則循環(huán)此步驟至遍歷完所有纖芯。

步驟3:對(duì)每個(gè)空閑頻譜FSi，從其起始頻隙fs開(kāi)始，計(jì)算新加入的串?dāng)_值XTa，以及活躍的相鄰纖芯對(duì)本頻隙的串?dāng)_值XTb。分別判斷XTa和XTb與串?dāng)_門(mén)限值的關(guān)系，若均未超過(guò)門(mén)限，則跳出步驟3并返回True，否則重復(fù)本步驟檢查下一個(gè)空閑頻譜塊FSi+1,直至檢查完所有可用空閑頻譜塊。

步驟4:若該候選路徑p中所有的纖芯都不能滿(mǎn)足該請(qǐng)求速率為r的業(yè)務(wù)，則返回False。

3 仿真與分析

為了驗(yàn)證本文算法的性能，本文將以中國(guó)拓?fù)錇榉抡鎸?duì)象。本文主要針對(duì)7芯光纖進(jìn)行仿真，在ICXT改善環(huán)節(jié)會(huì)對(duì)具有高串?dāng)_的19芯進(jìn)行仿真。仿真業(yè)務(wù)數(shù)目為十萬(wàn)個(gè)，業(yè)務(wù)到達(dá)服從參數(shù)為λ的泊松分布，持續(xù)時(shí)間服從參數(shù)為μ的負(fù)指數(shù)分布，算法中對(duì)業(yè)務(wù)進(jìn)行歸一化處理。

本文首先以經(jīng)典K條最短路徑首次匹配(K-Shortest Path First Fit,KSP-FF)算法為基準(zhǔn)算法，對(duì)比算法分別為按需結(jié)構(gòu)(Architecture of Demand, AoD)算法[12]和纖芯分組(Core Grouping, CG)算法[13]。

圖2所示為網(wǎng)絡(luò)拓?fù)湎聨捵枞市阅?，本文算法為藍(lán)色實(shí)線(xiàn)。由圖可知，基準(zhǔn)算法KSP-FF帶寬阻塞率最高，AoD與CG算法其次，而本文提出的算法在阻塞率性能上表現(xiàn)優(yōu)異。在相同業(yè)務(wù)負(fù)載下其帶寬阻塞率明顯比其他對(duì)比算法要低。這是由于本文不僅考慮了動(dòng)態(tài)路由機(jī)制，還把ICXT 的影響作為重要的度量，設(shè)計(jì)了串?dāng)_感知算法，進(jìn)一步降低了帶寬阻塞率。

圖2 帶寬阻塞率性能

圖3和4所示分別為7芯和19芯MCF在美國(guó)電信網(wǎng)絡(luò)(USNET)中針對(duì)不同算法與基準(zhǔn)KSP-FF相比較的ICXT改善效果。由于公式以KSP-FF算法為基準(zhǔn)，在業(yè)務(wù)負(fù)載較低時(shí)，MCF中資源充裕，不會(huì)出現(xiàn)資源不夠用的情況，所以在起始負(fù)載為0.1時(shí)，本文算法和CG算法相比于基準(zhǔn)KSP-FF算法均只有20%左右的提升，隨著業(yè)務(wù)量的增長(zhǎng)，性能差距逐漸明顯，這是因?yàn)楸粍?dòng)的串?dāng)_避免方案只能在網(wǎng)絡(luò)初始化階段對(duì)纖芯和頻隙進(jìn)行分組操作，當(dāng)業(yè)務(wù)負(fù)載較大時(shí)，所有無(wú)串?dāng)_分組都滿(mǎn)載，算法性能將會(huì)嚴(yán)重受限。

圖3 7芯MCF中串?dāng)_改善率

圖4 19芯MCF中串?dāng)_改善率

4 結(jié)束語(yǔ)

本文針對(duì)SDM-EONs中動(dòng)態(tài)資源分配問(wèn)題，提出了一種基于動(dòng)態(tài)路由與串?dāng)_感知的資源分配算法。首先設(shè)計(jì)了一種候選路徑排序公式來(lái)綜合性地對(duì)候選路徑集進(jìn)行排序，不僅考慮了物理跳數(shù)，還將鏈路利用率和剩余頻譜資源作為重要度量參數(shù)。同時(shí)，設(shè)計(jì)了串?dāng)_感知算法判斷IXCT情況，盡可能地降低串?dāng)_對(duì)系統(tǒng)阻塞率和吞吐量性能的影響。仿真結(jié)果表明，本算法在串?dāng)_解決和降低阻塞率等方面成效明顯。