基于OFDM的彈性光網(wǎng)絡(luò)中RSA問題綜述

◆邱 偉

基于OFDM的彈性光網(wǎng)絡(luò)中RSA問題綜述

◆邱 偉

（南京郵電大學(xué)電子與光學(xué)工程學(xué)院 江蘇 210023）

基于OFDM的彈性光網(wǎng)絡(luò)因?yàn)榫哂懈叩念l譜效率、更大的靈活性和可擴(kuò)展性而成為極具潛力的下一代光網(wǎng)絡(luò)，本文對彈性光網(wǎng)絡(luò)中路由和頻譜分配問題從概念，分類，以及目前的研究成果等進(jìn)行綜述，并提出未來的發(fā)展方向。

彈性光網(wǎng)絡(luò)；路由；頻譜分配；智能算法

隨著大數(shù)據(jù)、云計(jì)算以及移動通信的快速發(fā)展，涌現(xiàn)出了一大批的高流量型在線應(yīng)用和APP，比如直播平臺，購物網(wǎng)站，短視頻應(yīng)用等等。這些高流量型應(yīng)用的背后需要巨大的帶寬支撐，作為傳輸層主要承載方式的光網(wǎng)絡(luò)將面臨巨大的挑戰(zhàn)。傳統(tǒng)的波分復(fù)用光網(wǎng)絡(luò)（Wavelength division multiplexing，簡稱WDM）采用固定柵格的頻譜分配方式，對于帶寬需求遠(yuǎn)小于一個(gè)柵格帶寬的業(yè)務(wù)，仍然需要分配一個(gè)柵格的頻譜資源，造成了頻譜資源的浪費(fèi)[1]。為了滿足未來互聯(lián)網(wǎng)和通信的發(fā)展需求，光網(wǎng)絡(luò)需要具備更高的頻譜效率，更大的靈活性和可擴(kuò)展性。因此，采用OFDM技術(shù)的彈性光網(wǎng)絡(luò)（Elastic optical networks，簡稱EONs）被學(xué)者提出[2]。OFDM屬于多載波調(diào)制技術(shù)的一種，可以將高速率的數(shù)據(jù)流均分成低速率的數(shù)據(jù)流并行的在子信道上進(jìn)行傳輸，而因?yàn)樽虞d波的正交性，相鄰的子載波可以相互重疊?；贠FDM的彈性光網(wǎng)絡(luò)可以實(shí)現(xiàn)更細(xì)粒度的頻譜劃分，提供靈活的頻譜分配來滿足所請求的帶寬需求，此外還可以分配多個(gè)相鄰的子載波用以組成超級信道，實(shí)現(xiàn)較高速率的傳輸。路由和頻譜分配（Routing and spectrum allocation，簡稱RSA）問題是EONs中重要的研究點(diǎn)之一。本文將對EONs中RSA問題進(jìn)行介紹，并分析闡述實(shí)現(xiàn)RSA的各種方法，最后對RSA問題的發(fā)展方向做出預(yù)測。

1 RSA的基本概念

EONs中RSA是指根據(jù)業(yè)務(wù)請求在源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間找到一條合適路徑，并根據(jù)最大化利用頻譜資源原則分配合適的頻譜資源以建立連接。RSA問題和傳統(tǒng)的WDM光網(wǎng)絡(luò)中RWA問題類似，在WDM光網(wǎng)絡(luò)中，RWA是指在網(wǎng)絡(luò)中通過選擇路由和分配波長資源為連接請求建立光路，在建立光路時(shí)需滿足波長一致性要求[3]。RSA與RWA不同，RSA計(jì)算需要同時(shí)滿足頻譜連續(xù)性約束和頻譜鄰接性約束[4]。這兩個(gè)約束條件使得RWA計(jì)算方法不能直接運(yùn)用于RSA計(jì)算，RSA計(jì)算將更復(fù)雜。頻譜連續(xù)性約束是指經(jīng)過光路的每一條鏈路都應(yīng)該分配相同的頻譜資源。頻譜鄰接性約束是指在光路徑頻譜軸上要占用連續(xù)的頻隙。我們通過一個(gè)示例來解釋這兩個(gè)約束。如圖1，我們需要建立一條從節(jié)點(diǎn)1到節(jié)點(diǎn)3的光路，并且業(yè)務(wù)帶寬需要3個(gè)頻隙。圖中灰色代表頻隙已被占用，白色代表頻隙未被占用。我們可以使用鏈路2進(jìn)行路由，但是發(fā)現(xiàn)鏈路2上沒有連續(xù)的3個(gè)頻隙可以分配，即頻譜鄰接性約束條件不滿足，因此不能選擇鏈路2進(jìn)行路由。可以選擇從節(jié)點(diǎn)1到節(jié)點(diǎn)2，再到節(jié)點(diǎn)3這樣的方式進(jìn)行路由，鏈路1和鏈路3有三個(gè)連續(xù)的可用頻隙，即頻隙3，頻隙4和頻隙5（滿足頻譜鄰接性約束），且鏈路1和鏈路3上這三個(gè)連續(xù)的頻隙是“對齊”的（滿足頻譜連續(xù)性約束），因此，可以采用鏈路1和鏈路3進(jìn)行路由和頻譜分配。

圖1 頻譜連續(xù)性約束和頻譜鄰接性約束示例

RSA問題已經(jīng)被證實(shí)是一個(gè)NP-hard問題[5]，在多項(xiàng)式時(shí)間內(nèi)找不到最優(yōu)解。盡管RSA問題是一個(gè)比較難的問題，但是我們可以將問題簡化成兩個(gè)子問題，即路由子問題和頻譜分配子問題。下面將對這兩個(gè)子問題進(jìn)行介紹。

2 路由和頻譜分配子問題

2.1 路由選擇

路由選擇是為源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間選擇一條路徑進(jìn)行信息的傳輸。常見的路由選擇方法有以下4種[6]：

（1）固定路由（Fixed Routing，簡稱FR）：在FR中，使用最短路徑算法（比如Dijkstra算法，Bellman-Ford算法）為每個(gè)源節(jié)點(diǎn)和目的節(jié)點(diǎn)對預(yù)先計(jì)算單個(gè)固定路由。當(dāng)連接請求到達(dá)網(wǎng)絡(luò)時(shí)，該算法嘗試沿固定路徑建立光路。它檢查所需的頻隙是否在預(yù)定的路由的每個(gè)鏈路上可用。如果在鏈路上沒有發(fā)現(xiàn)可用的頻隙，則阻塞該連接請求。FR算法計(jì)算簡單，復(fù)雜度低，但是由于不靈活，在動態(tài)場景下網(wǎng)絡(luò)的阻塞率較高。

（2）固定備選路由（Fixed Alternate Routing，簡稱FAR）：FAR是FR的升級版本，在FAR中，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都為所有其他節(jié)點(diǎn)維護(hù)一張路由表，路由表中包含了具有優(yōu)先級順序的固定路由，比如以路徑長度作為優(yōu)先級指標(biāo)分為最短路徑、次最短路徑等。當(dāng)具有給定源節(jié)點(diǎn)和目的節(jié)點(diǎn)的連接請求到達(dá)時(shí)，源節(jié)點(diǎn)嘗試通過順序獲取路由表中的每個(gè)路由建立光路，直到找到能滿足頻隙要求的路由。如果在備用路由列表中找不到所需頻隙的可用路由，則阻塞該連接請求。該算法的復(fù)雜度高于FR，但是和FR相比，可以降低網(wǎng)絡(luò)的阻塞率。

（3）最少擁塞路由（Least Congested Routing，簡稱LCR）：LCR預(yù)先確定了與FAR類似的每個(gè)源節(jié)點(diǎn)和目的節(jié)點(diǎn)對的一系列路由。根據(jù)連接請求的到達(dá)時(shí)間，從預(yù)定路線中選擇最不擁擠的路線。鏈路上的擁塞是通過鏈路上可用頻隙的數(shù)量來衡量的。如果可用的頻隙數(shù)較少，則認(rèn)為此鏈路更為擁擠。LCR算法計(jì)算復(fù)雜度較高，網(wǎng)絡(luò)阻塞率與FAR幾乎相同。

（4）自適應(yīng)路由（Adaptive Routing，簡稱AR）：根據(jù)網(wǎng)絡(luò)的鏈路狀態(tài)信息動態(tài)選擇源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的路由。例如可以將鏈路的使用率作為依據(jù)進(jìn)行路由，比如在網(wǎng)絡(luò)中一條鏈路的使用率為100%，則在進(jìn)行路由時(shí)應(yīng)該避開該鏈路，尋找鏈路使用率低的鏈路進(jìn)行路由。AR算法與FAR算法相比，網(wǎng)絡(luò)阻塞率進(jìn)一步降低，但是因?yàn)橐鶕?jù)鏈路的狀態(tài)信息進(jìn)行動態(tài)的選擇路由，所以需要頻繁的更新鏈路狀態(tài)信息，導(dǎo)致網(wǎng)絡(luò)的控制管理平面更為復(fù)雜。

2.2 頻譜分配子問題

頻譜分配，即為業(yè)務(wù)請求沿鏈路分配頻譜資源，頻譜分配需滿足上文提到的頻譜連續(xù)性約束和頻譜鄰接性約束。常見的頻譜分配方法有以下幾種：

（1）首次命中（First Fit，簡稱為FF）[7]：在這種方案中，首先會對所有可用頻譜段進(jìn)行標(biāo)號。當(dāng)進(jìn)行業(yè)務(wù)頻譜分配時(shí)，會優(yōu)先選擇編號低的頻譜段進(jìn)行頻譜分配，這樣就可以讓使用中的頻譜段在頻譜空間中的低端位置，高端位置就可以留給更長的路徑使用。此方案不需要網(wǎng)絡(luò)全局信息，計(jì)算復(fù)雜度和網(wǎng)絡(luò)的阻塞率都比較低。和FF類似的還有最后命中（Last Fit，簡稱LF）方案，LF方案會優(yōu)先選擇編號高的頻譜段進(jìn)行頻譜分配。

（2）隨機(jī)命中（Random Fit，簡稱RF）[8]：這種方案首先會先在頻譜空間中搜尋所有適合業(yè)務(wù)的可用頻譜段的集合，然后隨機(jī)選取頻譜段進(jìn)行頻譜分配。該方案需要網(wǎng)絡(luò)全局信息，且比較容易產(chǎn)生頻譜碎片，網(wǎng)絡(luò)的阻塞率比較高。但是如果以分布式方式執(zhí)行頻譜分配，該方案可以降低多個(gè)連接選擇相同頻譜的可能性。

（3）最少使用（Least Used，簡稱LU）[9]：該方案將網(wǎng)絡(luò)中使用頻次最少的頻譜進(jìn)行分配，這種方案可以將負(fù)載均勻的分布在所有的頻譜資源上。與LU相類似的還有最多使用（Most Used，簡稱為MU），該方案將網(wǎng)絡(luò)中最多使用頻次的頻譜進(jìn)行分配，在網(wǎng)絡(luò)中實(shí)現(xiàn)最大頻譜重用。

（4）精確命中（Exact Fit，簡稱EF）[8]：該方案根據(jù)連接請求的頻隙數(shù)搜索與請求的頻隙數(shù)相等的確切的可用頻譜塊，如果滿足此條件，則分配該頻譜，如果不滿足，則退化為FF方案進(jìn)行頻譜分配。通過此方案進(jìn)行頻譜分配，可以減少光網(wǎng)絡(luò)中的頻譜碎片。

3 RSA問題的分類

根據(jù)所請求業(yè)務(wù)的屬性，RSA可以分為靜態(tài)RSA和動態(tài)RSA，還有一些和RSA相關(guān)方面的問題。

3.1 靜態(tài)RSA[9]

靜態(tài)RSA指的是在業(yè)務(wù)需求提前已知的情況下，為每個(gè)需求分配路徑和連續(xù)頻譜，目標(biāo)是在能夠成功建立連接的情況下最小化網(wǎng)絡(luò)中所需要的頻譜資源。靜態(tài)RSA常使用整數(shù)線性規(guī)劃（Integer Linear Programming，簡稱ILP）和啟發(fā)式算法。

3.2 動態(tài)RSA[10]

動態(tài)RSA是指客戶端根據(jù)需要隨機(jī)向網(wǎng)絡(luò)提交連接請求。連接建立成功與否取決于網(wǎng)絡(luò)的狀態(tài)，但是可用頻譜資源可能不能滿足建立連接所需要的頻譜資源。所以，每次根據(jù)請求建立連接時(shí)，都必須實(shí)時(shí)計(jì)算以確定是否可以容納請求所需的頻譜資源，如果因?yàn)槿鄙兕l譜資源而不能建立連接，則會阻塞該請求。在動態(tài)RSA中，通常以最小化連接阻塞率為目標(biāo)。動態(tài)RSA算法大致分為兩類，一類是一步式算法（One-step algorithms），它是次優(yōu)的使用貪心策略同時(shí)解決路由和頻譜分配兩個(gè)子問題。另一類是兩步式算法（two-step algorithms）。即順序的解決路由子問題和頻譜分配子問題。

3.3 其他和RSA相關(guān)的問題

（1）距離自適應(yīng)RSA（Distance-adaptive RSA，簡稱DA-RSA）

文獻(xiàn)[11]提出距離自適應(yīng)調(diào)制技術(shù)，具體是指，對于路徑長的路由應(yīng)該選擇低階調(diào)制格式（比如二進(jìn)制相移鍵控，簡稱BPSK），而對于路徑短的的路由應(yīng)該選擇高階調(diào)制格式（比如六十四進(jìn)制正交振幅調(diào)制，簡稱64QAM），這樣可以提高頻譜資源的利用率。因此，在頻譜分配策略中可以考慮路徑的長度和調(diào)制格式來為每個(gè)連接請求分配合適的光路。

（2）頻譜碎片感知RSA（Fragmentation-aware RSA，簡稱FA-RSA）

EONs頻隙的大小是彈性的，它可以是幾GHz甚至更窄，因此動態(tài)的建立光路和拆除光路會產(chǎn)生頻譜碎片[12]，這些頻譜碎片很難被新連接所使用，會造成頻譜利用率的下降。因此需要對頻譜碎片進(jìn)行整理，重新進(jìn)行路由和頻譜資源的分配，但是在執(zhí)行碎片整理時(shí)，重新路由會造成新建連接中斷，中斷會使業(yè)務(wù)建立連接時(shí)間延遲和增加系統(tǒng)的復(fù)雜性。所以碎片感知RSA要在進(jìn)行碎片整理時(shí)使正在進(jìn)行路由和頻譜分配的業(yè)務(wù)不受影響。

（3）生存性RSA（Survivability RSA）

EONs中光纖或網(wǎng)絡(luò)節(jié)點(diǎn)之類的網(wǎng)絡(luò)組件的故障可能會破壞數(shù)百萬用戶的通信，造成數(shù)據(jù)和收入的巨大損失，因此EONs網(wǎng)絡(luò)應(yīng)該要具備在出現(xiàn)故障時(shí)快速恢復(fù)的能力。EONs的生存性問題可以分為兩類：保護(hù)和恢復(fù)[13]。保護(hù)是在故障未發(fā)生時(shí)，在進(jìn)行RSA時(shí)就預(yù)先計(jì)算出備用路徑，由于預(yù)先分配了頻譜資源，會使得頻譜資源利用率不高，因此，保護(hù)問題RSA一般采用共享路徑保護(hù)方案，即在兩個(gè)相鄰路徑之間共享頻譜資源來提高頻譜的利用率?；謴?fù)是在故障發(fā)生后，根據(jù)網(wǎng)絡(luò)鏈路狀態(tài)動態(tài)計(jì)算備用路徑，與保護(hù)方案相比，可以提供更高的頻譜使用率。

4 RSA研究現(xiàn)狀與趨勢

（1）頻譜分配方案設(shè)計(jì)

RSA關(guān)注的主要是以降低網(wǎng)絡(luò)阻塞率、提高頻譜利用率為目標(biāo)，使用ILP方法或者設(shè)計(jì)啟發(fā)式算法來優(yōu)化網(wǎng)絡(luò)資源。因此設(shè)計(jì)出高效的頻譜分配方案可以減少頻譜碎片，提高頻譜的利用率。劉曉玲等提出基于頻譜候選窗的頻譜分配方案[14]，該方案會根據(jù)頻譜連續(xù)度進(jìn)行篩選后再進(jìn)行頻譜分配，改善了帶寬的阻塞率。蔣蕊等提出基于業(yè)務(wù)優(yōu)先級的頻譜分配方案[15]，該方案可以根據(jù)到達(dá)業(yè)務(wù)的優(yōu)先級順序進(jìn)行排序后再進(jìn)行頻譜分配，有效降低了網(wǎng)絡(luò)中的碎片化程度。此外，還可以根據(jù)業(yè)務(wù)所需的帶寬大小分類來進(jìn)行頻譜分配。

（2）能量效率

除了網(wǎng)絡(luò)阻塞率和頻譜利用率，能量效率也是一個(gè)值得關(guān)注的問題，特別是如何讓網(wǎng)絡(luò)中的總能耗降低。文獻(xiàn)[16]提出了一種動態(tài)節(jié)能RSA算法，該算法根據(jù)相應(yīng)鏈路和中間路由器的能量消耗來計(jì)算成本，在可能的候選路徑中找到能量消耗最少的路徑用來建立連接。

（3）智能算法

除了ILP和啟發(fā)式算法，智能算法也可以運(yùn)用到RSA問題中，常見的智能算法有遺傳算法，蟻群算法，模擬退火算法等。Ying Wang等采用蟻群算法解決RSA問題[17]，通過仿真驗(yàn)證了基于蟻群算法的動態(tài)RSA網(wǎng)絡(luò)阻塞率比基于其他算法（基于WDM的RWA算法，基于KSP的RSA算法）要有所降低，充分發(fā)揮出了蟻群算法的優(yōu)勢。不過，蟻群算法本身也有些缺陷，比如算法本身相比其他算法執(zhí)行時(shí)間較長、比較容易出現(xiàn)停滯的現(xiàn)象。在使用蟻群算法進(jìn)行RSA時(shí)，需要盡量的避免蟻群算法本身的缺陷。

（4）機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)（Machine Learning，簡稱ML）作為人工智能的一個(gè)分支，是今后信息科技發(fā)展的一個(gè)重要領(lǐng)域，文獻(xiàn)[18]中提出可以使用機(jī)器學(xué)習(xí)進(jìn)行路由選擇，流量預(yù)測，故障檢測，調(diào)制格式識別等等。為不同領(lǐng)域研究的結(jié)合提供了參考和依據(jù)。目前，基于機(jī)器學(xué)習(xí)的RSA研究較少，未來可以嘗試使用ML方法進(jìn)行EONs的RSA。

5 結(jié)束語

EONs作為下一代極具潛力的光網(wǎng)絡(luò)體現(xiàn)出了很多優(yōu)勢，可以適應(yīng)未來大容量、且不斷變化的帶寬需求。RSA作為EONs的一個(gè)關(guān)鍵問題，目前已經(jīng)有了大量的研究成果，但是仍然還有許多待解決的問題。本文綜述了RSA問題的概念和分類，并提出一些RSA的研究方向，可供研究人員參考。

[1]H.Zhou，S.Mao and P.Agrawal "Optical power allocation for adaptive WDM transmissions in free space optical networks，"2014 IEEE Wireless Communications and Networking Conference （WCNC），Istanbul，2014 pp.2677-2682.

[2]M.Jinno，H.Takara and B. Kozicki，"Concept and enabling technologies of spectrum-sliced elastic optical path network（SLICE），"2009 Asia Communications and Photonics conference and Exhibition（ACP），Shanghai，2009，pp. 1-2.

[3]R.Ramaswami and K.N.Sivarajan，"Routing and wavelength assignment in all-optical networks，"in IEEE/ACM Transactions on Networking,vol.3，no.5，pp.489-500，Oct.1995.

[4]Y.Zhao，J.Zhang，Y.Ji and W.Gu，"Routing and Wavelength Assignment Problem in PCE-Based Wavelength-Switched Optical Networks，"in IEEE/OSA Journal of Optical Communications and Networking，vol.2，no.4，pp.196-205，April 2010.

[5]Y.Wang，X.Cao，and Y.Pan，"A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks，"in Proc.IEEE INFOCOM，2011，pp.1503-1511.

[6]R.Ramamurthy and B.Mukherjee，"Fixed-alternate routing and wavelength conversion in wavelength-routed optical networks，"IEEE/ACM Trans.Netw.，vol.10，no.3，pp.351-367，Jun.2002.

[7]R.Wang and B.Mukherjee，"Spectrum management in heterogeneous bandwidth optical networks，"Opt.Switching Netw.，vol.11，pp.83-91，Jan.2014.

[8]A.Rosa，C.Cavdar，S.Carvalho，J.Costa，and L.Wosinska，"Spectrum allocation policy modeling for elastic optical networks，"in Proc.9th Int.Conf.HONET，2012，pp.242-246.

[9]R.M.C.Siva and G.Mohan，"WDM Optical Networks：Concepts，Design and Algorithms，"Upper Saddle River，NJ，USA：Prentice-Hall，2003.

[10]Xin Wan，Lei Wang，Nan Hua，Hanyi Zhang and Xiaoping Zheng，"Dynamic routing and spectrum assignment in flexible optical path networks，"2011 Optical Fiber Communication Conference and Exposition and the National Fiber Optic Engineers Conference，Los Angeles，CA，2011，1-3.

[11]JINNO M，KOZICKI B，TAKARA H，et al."Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network [Topics in Optical Communications[J]，"IEEE Communications Magazine，2010，48（8）：138-145.

[12]K.Christodoulopoulos，I.Tomkos，and E.Varvarigos，"Elastic bandwidth allocation in flexible OFDM-based opticalnetworks，"J. Lightw.Technol.，vol.29，no.9，pp.1354-1366，May 2011.

[13]L.Ruan and N.Xiao，"Survivable multipath routing and spectrum allocation in OFDM-based flexible optical networks，"IEEE/OSA J. Opt.Commun. Netw.，vol.5，no.3，pp.172–182，Mar.2013.

[14]劉曉玲，張競文，喻聰，羅凌琦，沈建華.基于頻譜候選窗的彈性光網(wǎng)絡(luò)頻譜分配方案[J].光通信技術(shù)，2018，42（11）：5-7.

[15]蔣蕊，馮朦，沈建華.基于業(yè)務(wù)優(yōu)先級的Eonss頻譜分配方案[J].光通信技術(shù)，2017，41（10）：60-62.

[16]A.Fallahpour，H.Beyranvand，S.A.Nezamalhosseini， and J.A.Salehi，"Energy efficient routing and spectrum assignment with regenerator placement in elastic optical networks，"J. Lightw. Technol.，vol. 32，no.10，pp.2019-2027，May 2014.

[17]Wang Ying，Zhang Jie，Zhao Yongli，Wang Jingjing，Gu Wanyi. "ACO-based routing and spectrum allocation in flexible bandwidth networks，"Photonic Network Communications（2013）.25.10.1007/s11107-013-0397-z.

[18]F. Musumeci，et al.，"An Overview on Application of Machine Learning Techniques in Optical Networks，"in IEEE Communications Surveys & Tutorials.