彈性光網絡中基于頻譜連續度的算法研究

陳秉鈞，張 寧，楊延嵩，陳曉丹

北京聯合大學 智慧城市學院，北京 100101

隨著信息化時代的到來，光通信技術發展越來越快[1-2]。近年來，彈性光網絡（elastic optical network，EON）受到了廣泛的研究，并被用來解決光纖光柵的結構中傳統波分復用（WDM）光網絡頻譜利用率低的問題。在WDM網絡中，信道帶寬是固定在50 GHz，不能根據實際業務的需要，靈活地分配頻譜資源，且業務請求一旦連接，網絡就無法根據實時情況，動態調整頻譜資源，導致WDM網絡無法處理來自不同帶寬要求大小的客戶端的連接需求。EON依靠正交頻分復用技術（OFDM），將頻隙粒度的信道帶寬容量劃分為更細的粒度，如6.25 GHz、12.5 GHz，允許通過選擇適當數量的頻隙資源來構建光路。同時，由于OFDM引入子載波技術，且子載波之間的正交性，使得不同業務之間不需要保護帶寬，因此EON可以靈活地和更有效地利用光纖帶寬。相比傳統的WDM網絡，EON能提高頻譜資源利用率。

對于光網絡來說，在頻譜分配的過程中，要遵循兩個基本的約束：頻譜連續性，以及頻譜一致性。頻譜連續性，要求在請求的路由光路中，每條鏈路上分配的頻譜必須是連續的；頻譜一致性，要求在請求的路由光路中，每條鏈路上占用連續的頻譜的位置，必須保持一致。因此，隨著不同的連接請求的建立和刪除，頻譜資源會出現空閑但不連續的頻譜碎片，這會導致頻譜資源不能滿足業務請求，造成極大的浪費。因此，一個良好的路由和頻譜資源分配（RSA）算法，是解決這類問題的關鍵。在光網絡中，研究這類RSA問題，常常劃分為兩個子問題，即路由選擇問題和頻譜資源分配問題。

1 網絡路由與頻譜分配問題

近年來，需要預留頻譜資源的業務數量迅速增加[3-5]。He等人[3]關注了在基于預留業務的RSA算法中一些不可用的頻譜資源，提出的基于無效頻譜感知的預留業務（advanced-reservation-based invalid-spectrumaware，AR-ISA）頻譜資源分配算法，采用碎片整理算法以進一步提高網絡性能。Li等人[4]提出一個指標，即四個因素的加權之和，通過最小化度量來分配業務的頻譜資源，降低阻塞率。Zhu等人[5]設計了二維碎片感知以及碎片的連續性感知算法，降低了在虛擬光網絡嵌入過程中的二維碎片。但是上述算法在運行過程中需要為這些業務預留出一部分頻譜資源，當預留業務沒有到來時，其他業務也不能占用這部分頻譜資源，這就不可避免地降低了頻譜資源的利用率。

Ujjwal等人[6]將距離自適應調制技術引入RSA算法中，允許在多條不相交路徑上執行自適應流量需求拆分。Araújo等人[7]提出了一種新的建模方法，最大限度地減少了插槽索引，同時最小化每種需求的備用光路所需求的鏈接數量。但是這些算法在路由和頻譜分配的過程中需要大量時間來計算，導致了算法整體的效率不高。Lezama等人[8]改進了蟻群優化算法，只需要很少的控制參數，就可以在任意靈活的場景最小化頻譜利用率。Pederzolli等人[9]提出了一種新的基于路徑的度量，更好地評估光網絡中的頻譜資源碎片化，并且提出了兩個啟發式RSA算法。Lechowicz等人[10]為了評估光網絡中頻譜碎片程度，提出了用于彈性光網絡的各種碎片測量標準。此外，介紹了邊界超級通道（bordering superchannels，bSChs）的新概念。但是算法在運行的過程中需要備份路由，備份的路徑過多會占用大量頻譜資源。Halder等人[11]提出了基于貪心算法的可生存路徑的貪婪啟發式算法（greedy heuristic for survivable multipath，SM-GR）和可生存多路徑的遺傳算法（genetic algorithm for survivable multipath，SM-GA）來求解大型網絡的近似最優解。作者將提出的算法和ILP線性規劃模型相比較，線性規劃模型在面對大型網絡時效率很低，SM-GR和SM-GA算法能有效降低業務阻塞率。但是算法運行過程中需要大量的計算，加大了每個節點處理數據的能耗。Yuan等人[12]提出了預切片的頻譜分配算法。將頻譜切片分為標準塊，連接所需求的頻譜資源預先被分成了標準塊。這些措施可以對準被占用的和可用的頻隙，從而降低阻塞率。但是，切塊的頻譜資源在面對靈活的頻譜資源需求時，還是會存在大量的頻譜資源不匹配導致頻譜資源的浪費。

Mahmoud等人[13]提出了一種遞歸分解的方法，對整個路由空間進行搜索，但是整個路由表的生成需要巨大的內存空間和處理時間。當整體網絡節點較多和業務量較大時，會浪費較多的時間和空間資源。Panchali等人[14]通過建立光樹，提出的頻譜劃分方法，對現有方法進行了修改，提出了基于派系劃分的疏導算法。使用首次命中頻譜分配策略，它從可用的第一個索引向奇數分區分配頻隙，并從最后一個索引開始為偶數分區來分配頻隙。Yuan等人[15]提出了鏈路相鄰縮減的概念，表示使用一個頻譜塊后鏈路上頻譜的變化情況，在此基礎上，提出了一種RSA算法，該算法選擇使鏈路相鄰縮減最小的頻譜資源分配給業務，提高頻譜資源利用率。王鵬輝等人[16]提出了重要節點的概念，算法將經過重要節點的業務分配次短路徑。但是算法需要提前知道所有業務的源節點和目的節點。李娜娜等人[17]提出了一種基于路徑長度和節點數的算法，算法選擇路由上節點最少的路徑，如果路徑的跳數相同則選擇距離最短的路徑。

2 提高頻譜資源利用率的頻譜連續度錯位感知算法

在彈性光網絡中，路由和頻譜分配問題一直是NP-hard問題，因此，在解決路由和頻譜分配問題時，本文提出一種頻譜連續度感知算法。該算法分為兩步：在路由選擇方面，KSP最短路徑算法能根據源節點和目的節點計算出一條最短路徑，業務需要的頻隙數量越少，分配的路徑越短，反之業務需要的頻隙數量越多，分配的路徑越長。在頻譜分配方面，考慮到新的業務到來后，承載該業務的路徑上各鏈路原本的頻譜資源連續性會減少，為此，專門在此算法中引入一個新的參數Cuts，根據Cuts值來分配頻譜位置，該算法能有效減少業務的阻塞率，并提高頻譜資源利用率。

2.1 基于KSP的路由選擇方式

在實際生活中，各網絡節點產生的業務量是不同的，例如大城市中產生的業務量更多，且節點數量更加集中，距離更近。如圖1簡單網絡拓撲所示，假設節點1和節點2為繁忙節點，這兩個節點產生的業務數量遠遠超過其他節點。

圖1 簡易網絡拓撲Fig.1 Simple network topology

假定同時出現2個請求，分別為（1-3）、（1-4），且所需要的頻隙數分別為1、2。經過計算可知兩個請求的路徑分別為（1-2-3）、（1-5-4）。節點1這個繁忙節點產生的兩個業務將不會同時使用節點1和節點2間的鏈路，降低鏈路的負載壓力。因此繁忙節點的產生大量業務就可以盡可能地分配到整個網絡空間，降低整個網絡的業務阻塞率，提高頻譜資源利用率。

2.2 基于頻譜連續度感知的頻譜分配方式

在光網絡動態運行過程中，新業務的到來會造成業務所在鏈路上連續的頻譜資源分段，本文使用參數Cuts來表示一個新的連接是否將鏈路上的連續頻譜分段。如果新業務會將鏈路上的連續頻譜分段，Cuts=1；反之，則Cuts=0。此時計算從源節點到目的節點所有經過的鏈路上連續頻譜資源因該業務所引起的分段，參數Cuts的值等于承載該業務所引起的連續頻譜資源分段之和，Cuts值定量地表現了一個新連接所引起的頻譜碎片程度，Cuts值越低代表分配后的頻譜碎片更少，頻譜利用率更高。因此在分配頻譜資源時應選擇Cuts值最低的位置分配頻譜資源。

假定在該網絡中，每條鏈路的頻隙數量為15，如圖2所示，鏈路上黑色的小方塊代表已經被占用的頻譜資源，白色的小方塊代表未被占用的頻譜資源。假定網絡中新的業務請求從節點1到節點5，其中經過鏈路1-2，鏈路2-3，鏈路3-4，鏈路4-5，需求的頻譜資源為一個頻隙。

圖2 路徑簡易狀態圖Fig.2 Simple path state diagram

如圖3所示，帶箭頭的虛線表示路徑上滿足業務需求的頻譜資源，Cuts表示將這段頻譜資源分配給新業務后，新業務中斷的連續頻譜資源的數量。此時假設新業務需要1個頻隙的頻譜資源，在一般的RSA算法中，從路徑1-5上看，slot2、slot8、slot12是等價的。但是在本文的KSPDP算法中，slot2位置的Cuts值為3，而slot8位置上Cuts值為0，slot12位置上Cuts值為1，所以算法將這個業務分配在slot8的位置上，此時產生的頻譜碎片最少。

圖3 頻譜分配示意圖Fig.3 Spectrum allocation diagram

2.3 算法流程

算法通過仿真數據得到源節點和目的節點對，并利用KSP算法計算得出K條最短路徑，根據這一節點對所需要的頻隙數量分配路由路徑，需要的頻隙數量越少，分配的路徑越短。比如業務需要一個頻隙大小的頻譜資源，就分配最短路徑。需要的頻隙數量越多，分配的路徑越長，比如業務需要八個頻隙大小的頻譜資源，就分配第K短路徑。之后算法計算各位置的頻譜資源所引起分段的Cuts值，其用來計算分配頻譜資源時，新的業務對原有頻譜資源的影響，Cuts值越低，越會最大限度地避免影響各鏈路間可用頻隙的對齊關系，通過計算Cuts值來分配業務所需頻譜資源的位置，將業務分配在Cuts值最小的位置，減少頻譜碎片的產生，提高各鏈路的業務承載能力。該算法可以最大限度地將單一連接上的頻譜資源最大化利用起來，減少頻譜資源碎片。

其工作流程圖如圖4所示。

圖4 算法流程圖Fig.4 Algorithm flowing diagram

步驟1根據業務請求的節點對計算K條最短路徑并選擇其中路徑最短的5條路徑。

步驟2根據業務請求所需要的連續頻譜資源數量分配路由路徑，業務需求的連續頻譜資源數量越少，分配的路徑越短。

步驟3確定路由路徑之后并根據算法所計算的Cuts值，選擇Cuts值最低的位置分配頻譜位置。

步驟4繼續為下一個業務分配頻譜資源。

3 仿真實驗

3.1 仿真環境

本文的仿真都是利用python語言進行編程的，并對仿真結果進行分析，仿真所用的網絡拓撲為經典的NSFNET網絡結構和USNET網絡結構，圖5為NSFNET網絡拓撲，該結構共有14個節點和21條鏈路。圖6為USNET網絡拓撲，該網絡結構共有24節點43條鏈路。

圖5 NSFNET網絡拓撲結構Fig.5 NSFNET network topology

圖6 USNET網絡拓撲Fig.6 USNET network topology

在仿真過程中，本文假設網絡每條鏈路只有一個光線對。每條鏈路上的可分配頻譜帶寬為4.475 THz，每個頻隙所需的帶寬為12.5 GHz，因此每條連續所擁有的頻隙數為358個。仿真中業務到達時間服從參數為λ泊松分布，且連接的持續時間是服從參數為μ指數分布，網絡負載為λ/μ的愛爾蘭Erlang。業務請求所需的頻隙1、2、4、6、8中隨機選擇，在NSFNET網絡中，源節點有一半產生于10、11、12、13這四個節點，另一半在剩下的節點中隨機產生，目的節點隨機產生。在USNET網絡中，源節點有一半產生于2、12、15、20、23這五個節點，另一半在剩下的節點中隨機產生，目的節點隨機產生。

3.2 仿真結果

算法性能評價指標根據業界流行的業務阻塞率和頻譜資源利用率來對比。業務阻塞率是指在算法運行過程中，分配失敗的業務占整體業務的比值。頻譜資源利用率是指在算法運行過程中，鏈路上被占用的頻譜資源數量占所有頻譜資源數量的比值，業務阻塞率越低，頻譜資源利用率越高，代表算法性能越好。圖7和圖8展示了算法在NSFNET網絡仿真下的業務阻塞率和頻譜資源利用率。圖9和圖10展示了算法在USNET網絡仿真下的業務阻塞率和頻譜資源利用率。本文將最短路徑路由首次命中（Hij+FF）算法和KSPDP算法進行對比。

如圖7所示，在NSFNET網絡拓撲下，業務請求的阻塞率都隨著業務量的增長而增大。在網絡負載較低的時候，KSPDP算法與傳統的RSA算法差距比較小，但是從網絡負載量上升之后，KSPDP算法明顯降低了業務阻塞率，在負載流量較大的情況下降低的業務阻塞率可以提升16%～17%。KSPDP算法與傳統的RSA算法相比，在相同的業務量下，KSPDP算法的業務阻塞率總是低于傳統的RSA算法。仿真說明KSPDP算法的可以有效降低業務的阻塞率。

圖7 NSFNET網絡阻塞率對比圖Fig.7 NSFNET network blocking probability comparison diagram

如圖8所示，對于NSFNET網絡拓撲，在業務量較小時，KSPDP算法將業務請求更大地分配在了整個網絡空間，所以在繁忙節點間的單條鏈路上頻譜資源利用率會低于傳統的算法，此時整個網絡的業務阻塞率普遍在一個比較低的水準，局部的頻譜資源利用率低不影響整個網絡的正常運行。但是當業務負載量變大時，相比傳統算法，KSPDP算法在尋找頻隙位置的方式上有所不同。當頻譜上出現了一系列的大小不同的頻隙時，KSPDP算法采用頻譜資源連續度最高的頻隙位置的方式來進行頻譜資源的再分配，這樣一來，由此產生的頻譜碎片就會少一些。這樣就提高了頻譜資源利用率。相比于傳統算法頻譜資源利用率為0.575，KSPDP算法頻譜利用率為0.66，頻譜資源利用率提高約10%，更多的頻譜資源被利用。仿真結果證明KSPDP算法可以有效提高頻譜資源利用率，降低業務阻塞率。

圖8 NSFNET網絡頻譜資源利用率對比圖Fig.8 NSFNET network spectrum resource utilization comparison diagram

為了驗證算法在更復雜的網絡環境下的性能，同時驗證算法的適用性，除了在NSFNET網絡拓撲下進行仿真之外，實驗在相同的仿真條件下，在USNET網絡下進行了仿真實驗，USNET網絡拓撲網絡規模和復雜度都更大，可以用來評價算法在更大的網絡規模下的適用性和相關性能。

如圖9所示，隨著網絡負載的增加，KSPDP算法和Hij+FF算法的業務阻塞率都隨之增加。KSPDP算法與傳統的RSA算法相比，業務阻塞率明顯更低，同時比較算法NSFNET網絡拓撲和USNET網絡拓撲上的表現，KSPDP算法均比Hij+FF算法業務阻塞率更低。表明了KSPDP算法的性能與仿真所用的網絡拓撲結構無關，能明顯降低業務阻塞率。

圖9 USNET網絡業務阻塞率對比圖Fig.9 USNET network blocking probability comparison diagram

如圖10所示，KSPDP算法和Hij+FF算法的頻譜利用率都隨著網絡負載的增加而增加，和NSFNET網絡相似，算法在網絡負載較低的時候將業務分散在整個網絡空間內，隨著網絡負載的增加，KSPDP算法的頻譜利用率比Hij+FF算法更高。USNET網絡拓撲的仿真結果表明，KSPDP算法能提高頻譜資源利用率。

圖10 USNET網絡頻譜資源利用率對比圖Fig.10 USNET network spectrum resource utilization comparison diagram

隨著未來更多新的業務類型的出現，業界會利用算法阻塞率性能的劣化來評估算法面對網絡中線路速率增多的情況，本文算法阻塞率性能的劣化是指網絡上運行業務需求頻隙數量是五種時業務阻塞率和網絡上運行業務需求頻隙數量為三種時業務阻塞率之差。

如圖11所示，在NSFNET網絡上，隨著網絡負載的增加，兩種算法的業務阻塞率性能都有所下降，但是KSPDP算法在面對業務所需頻隙數量的增加時，其業務阻塞率劣化比Hij+FF算法要好，表明算法在面對未來更多業務需求種類時有更好的適應性。

圖11 NSFNET阻塞率性能劣化對比圖Fig.11 NSFNET blocking probability performance degradation comparison diagram

如圖12所示，在USNET網絡上，KSPDP算法的阻塞率劣化依然優于Hij+FF算法，隨著網絡規模的擴大和業務的頻繁產生和離開，網絡中的頻譜碎片會增多，更大需求的頻隙大小也會導致頻譜碎片的大小變大。此時，算法為后續的業務分配頻譜資源的成功率也會下降，業務阻塞率也會隨之上升。

圖12 USNET阻塞率性能劣化對比圖Fig.12 USNET blocking probability performance degradation comparison diagram

綜上所述，通過仿真結果可以看出，KSPDP算法相比傳統的RSA算法，可以將隨機到來的業務請求盡可能均勻地分布在整個網絡空間，相比首次命中算法尋找第一個滿足頻譜資源要求的頻隙位置，KSPDP算法可以尋找使得頻譜資源連續度最高的頻隙位置來分配頻譜資源，因此，產生的頻譜碎片會盡量少一些，能將整個空間的頻譜資源利用起來，減少頻譜資源碎片，這可以更好地滿足接下來的業務需求，所以，這種方法擁有更高的頻譜資源利用率。

4 結論

本文研究了路由選擇和頻譜分配算法，為了提高光網絡中頻譜利用率，提升網絡整體性能，提出了一種基于KSP的頻譜連續度感知算法（KSPDP）。該算法在彈性光網絡中，針對路由選擇問題和頻譜資源分配問題，提供了一種新的解決方案，在光通信網絡中，面對同一個源節點和目的節點所產生的業務，需要按照業務請求的不同，分配不同的路徑，以便使業務更均衡地分配在整個網絡空間。針對頻譜分配問題，根據業務請求頻隙的不同，用不同的頻譜分配方式，最大限度地節省頻譜資源，從而提高頻譜資源利用率。本文算法在NSFNET網絡拓撲環境下進行了仿真實驗。仿真結果顯示所提出的基于KSP的頻譜連續度感知算法（KSPDP），在業務阻塞率和頻譜資源利用率方面，比傳統的RSA算法有一定的提高。