基于距離自適應和有效共享路徑感知的光疏導方法

劉煥淋 歲 蒙 徐一帆 陳 勇 張盛峰

?

基于距離自適應和有效共享路徑感知的光疏導方法

劉煥淋*①歲 蒙①徐一帆①陳 勇②張盛峰①

①(重慶郵電大學光纖通信技術重點實驗室 重慶 400065)②(重慶郵電大學自動化學院 重慶 400065)

針對靈活網格光網絡中如何節約轉發器與頻譜資源的問題，該文研究了多點到多點組播業務的光路環路由機制，提出一種基于距離自適應和有效共享路徑感知的光疏導方法。通過設計一種基于距離自適應的預處理機制，該疏導方法能根據業務成員節點的分布特點和距離自適應準則靈活地為業務構建光路環；在路由與頻譜分配階段，該疏導方法通過構造一個面向光疏導的業務決策矩陣和一個優先調度向量，將業務疏導到與當前業務具有有效共享路徑最多的已路由業務上，并優先分配所需的頻譜空間以提高光疏導的成功率，實現節約轉發器與頻譜資源的目的。仿真結果表明，該文提出的光疏導方法可以有效地減少業務消耗的轉發器數目和子載波數目。

靈活網格光網絡；光路環；光疏導；共享路徑感知

1 引言

隨著數字廣播、物聯網和云計算等多播應用需求的增長，光網絡面臨著業務流量爆炸式增長所帶來的巨大挑戰和壓力，光網絡的轉發器資源等也日益緊缺。目前光網絡綠色節能的路由傳輸研究主要集中于波分復用光網絡中[4,5]，而基于光正交頻分復用的靈活網格光網絡(Flexible Grid Optical Networks, FGON)中的研究及成果相對較少，因此FGON網絡中實現綠色節能的路由傳輸是當前的研究熱點[6]。在FGON網絡中，業務需要頻繁地通過轉發器調制到不同等級的子載波上，這樣便造成了轉發器的總能耗巨大，因此減少轉發器的使用是實現綠色路由傳輸的有效手段[7,8]；此外，網絡中不同業務間保護頻隙的額外頻譜開銷，造成頻譜資源的浪費，也增大了網絡能耗[9,10]。因此，如何有效地節約轉發器的使用與頻譜資源是一個值得研究的問題。

目前，國內外圍繞FGON網絡中節約轉發器與頻譜資源的研究已有若干成果：文獻[11]基于遺傳算法提出了生存性靈活光網絡的多目標優化算法，該算法研究了采用高調制等級方式，以及在業務的保護鏈路上采用轉發器共享策略可減少轉發器的使用問題。文獻[12]針對具有帶寬波動的時變業務提出了Mid Fit頻譜分配算法，該算法通過最大化相鄰業務間的空閑頻譜塊，選擇最大的連續空閑頻譜塊中居于中間位置的連續頻譜來安置業務。從頻譜分配的角度分析，該頻譜分配算法可以有效地提高光疏導的成功率，實現節約轉發器資源和頻譜資源的目的，但該算法總是選擇使用中間位置的頻譜，容易造成過多的頻譜碎片。文獻[13]提出了距離自適應和頻譜碎片感知的光疏導算法來減少網絡轉發器與頻譜資源的使用，算法至少可以節約14%的頻譜資源和13%的轉發器資源，但是算法在為進行光疏導的業務分配頻譜時，沒有提出靈活有效的頻譜分配策略，受子光路內的頻譜連續性和一致性約束，該算法頻譜分配的成功率很低，最終制約了算法的性能提升。文獻[14]提出了基于最多頻隙數優先的光疏導算法來節約轉發器資源和頻譜資源，但沒有綜合地考慮頻隙數和路徑跳數對光疏導算法性能的影響，且提出的算法不適合多播業務的疏導傳輸。

本文研究了多點到多點組播業務的路由與頻譜分配問題。主要針對如何節約轉發器與頻譜資源的使用問題，本文提出了一種光路環中基于距離自適應和有效路徑感知的光疏導算法(Effective Sharing Path-Aware Optical Grooming, ESPA-OG)。該算法主要包含兩個部分：(1)基于距離自適應的業務預處理機制，該機制為業務靈活地構建光路環，設計了業務大小的定義式和業務的排序準則；(2)基于有效共享路徑感知的光疏導算法，該算法設計了業務的光疏導路由機制和頻譜分配機制。在路由階段，通過構造一個面向光疏導的決策矩陣，選擇有效共享路徑最多的兩個光路環來靈活地進行光疏導；在頻譜分配階段，通過構建一個優先調度向量，為進行光疏導的業務優先分配頻譜，進一步優化光疏導算法的性能。

2 基于距離自適應的業務預處理機制

在確定多點到多點組播業務的路由排序準則時，以往的研究主要是由業務占用的帶子載波數目決定，而不考慮業務傳輸路徑的物理跳數。受頻譜連續性和一致性的約束，這就會造成業務消耗額外的轉發器資源和頻譜資源。因為業務的物理跳數越多其光疏導成功的概率就越低，而如果能綜合考慮業務占用的子載波數目和物理跳數，就可以提高光疏導成功的概率，從而減少轉發器與頻譜資源的消耗。

基于以上分析，本文提出了光路環中基于距離自適應的預處理機制，在該機制中，設計了業務大小的定義式。定義式的值由光路環占用的子載波數目和物理跳數決定，根據定義值再對業務進行降序排列。距離自適應是當兩個節點間最短路徑的權重值發生變化后，該機制可重新判斷變化后的權重值和不同調制等級下光信號的極限傳輸距離之間的大小關系，以使業務選擇最高的調制等級進行傳輸。構建光路環的方法及計算業務大小的步驟為：

步驟6 確定整個光路環。在半個光路環中查找光路連接度數為1的兩個成員節點和，從子圖中刪除半個光路環經過的所有中間節點和物理鏈路，然后在子圖上，采用Dijkstra算法計算節點到的最短路徑，將此最短路徑存入中；

3 基于有效共享路徑感知的光疏導算法

目前光網絡中，業務的路由選擇和頻譜分配是NP(Non-deterministic Polynomial)完全問題[18]，啟發式算法可以解決大型網絡中整數線性規劃方法存在的計算時間過長的問題，然而在FGON網絡中，現有的節約轉發器資源和頻譜資源問題的策略都是針對單播業務，還沒有針對多點到多點組播業務提出靈活有效的解決方法。在本文提出的光疏導算法中，根據預處理機制為業務構建光路環傳輸路徑，同時對業務進行降序排隊。算法按照路由與頻譜分配兩個階段來安置業務。

式(6)為算法的優化目標，即最小化網絡中業務消耗的轉發器數目與子載波數目。其中，為業務成員節點的數目；代表與已路由業務之間有效共享路徑中的成員節點個數；為式(5)中計算得到的業務的大小；代表業務與之間有效共享路徑經過的鏈路數目。式(7)中的表示已路由業務的光通道，表示業務疏導在業務上，業務可以與業務之間共享轉發器資源，同時這兩個業務之間不需要保護頻帶。式(8)和式(9)表示在滿足約束條件下，最大化有效共享路徑數目，即盡可能多地共享轉發器資源，節約共享路徑上的子載波數目。

3.1 ESPA-OG算法的路由機制

ESPA-OG算法中的感知是一個根據業務的光路環之間有效共享路徑情況確定業務之間光疏導情況的過程。在尋找能夠對當前業務進行光疏導的已路由業務時，當共享鏈路的兩個端節點均不是成員節點，而是光路環的中間節點時，表示該鏈路為無效共享路徑；當共享鏈路的兩個端節點至少有一個是成員節點時，表示該鏈路為有效共享路徑。采用有效路徑感知是為了保證算法不會在中間節點進行光疏導，由于在中間節點處進行業務的上下路，會導致消耗額外的轉發器資源。

ESPA-OG算法的業務傳輸路由步驟為：

步驟1 初始化網絡鏈路資源；

步驟2 根據本文的預處理機制計算出的業務的大小，將到達的多點到多點組播業務按業務大小降序插入鏈表中；

圖1 光路環中的光疏導

3.2 ESPA-OG中的頻譜分配策略

一般而言，在分配頻譜時，為了避免頻譜碎片化，算法會將新的業務安置在已占用的頻譜位置旁。但是采用光疏導后，如果依然采用這種頻譜分配，就會造成頻譜分配失敗。這是因為光疏導將多個業務疏導到一個轉發器中進行傳輸，也就是將多個子光路聚合為一個“光通道”，為這個光通道中的業務分配頻譜時，不僅要滿足子光路內的頻譜連續性和一致性約束，還要滿足子光路間的頻譜連續性和一致性約束，子光路間的約束條件使得頻譜分配的成功率大大降低。如果我們能夠優先為要聚合在一個光通道中的業務分配頻譜，就可以解決上述問題。

圖2 優先分配策略

步驟1 初始化網絡頻譜資源；

算法在構建光路環路由業務時，只將業務成員節點集合中的各成員節點按序配對，然后依次計算配對后的成員節點間的最短路徑，不再受光路環起點的約束，算法的時間復雜度為，疏導路由感知部分的時間復雜度是，其中為網絡中業務數目，為多點到多點組播業務的平均成員節點個數；在頻譜分配時，在安置完業務后，便調用業務的優先調度向量，然后為疏導在上的所有業務查詢可用的頻譜空間，即在安置一個光通道中的業務時，只需要查找一次即可，算法的時間復雜度就為，其中為一個光通道中的平均業務數目，總的時間復雜度為。

4 算法仿真及結果分析

為了驗證所提算法的性能，本文對2個經典網絡拓撲進行了仿真，即14個節點，21條鏈路構成的NSFNET網絡(如圖3)和24個節點，43條鏈路構成的USNET網絡(如圖4)，每根光纖可承載的子載波數目為358個，調制等級取值為{1, 2, 3, 4}，一個子載波的帶寬容量為，每個節點配備的轉發器數目為100，節點的業務帶寬可取值為{1, 2, 3, 4, 5, 6}′12.5 Gb/s，每個組播業務的成員節點個數可取值為{2, 3, 4, 5}，與ESPA-OG算法進行對比的算法是FLPC-OG(Frequency LightPath Circle-Optical Grooming)[14]、無光疏導算法(LightPath Circle-No Grooming, LPC-NG)，其中LPC-NG算法采用了本文的預處理機制。仿真統計不同業務數和業務帶寬粒度下的轉發器使用數目，子載波使用數目等性能指標。

圖3 NSFNET網絡拓撲圖

圖4 USNET網絡拓撲圖

圖5和圖6分別表示2個網絡的轉發器使用情況，可以看出，3種算法消耗的轉發器數目均隨著網絡中業務數的增加而增加。但是在相同的業務數下，本文提出的ESPA-OG算法性能最好，FLPC- OG算法次之，LPC-NG算法性能最差，且ESPA-OG算法相比FLPC-OG算法、LPC-NG算法分別有約36%, 70%的轉發器節約。這是因為，相比LPC- NG算法，ESPA-OG算法中采用了有效共享路徑感知的光疏導機制，使得不同的業務在相同的成員節點處可以共享轉發器資源，而LPC-NG算法中沒有光疏導機制；相比FLPC-OG算法，ESPA-OG算法的預處理機制綜合考慮了子載波數目和物理跳數對光疏導的影響，使得更多的業務可以共享轉發器資源。此外，ESPA-OG算法還采用了頻譜優先分配策略，提高了業務間光疏導的成功率，從而節約了更多的轉發器資源。在相同的業務數下，對比圖5和圖6可知，LPC-NG算法在USNET網絡中消耗的轉發器數目較少。這是因為USNET網絡較大，當業務的成員節點數目較多時，網絡中可能不存在鏈路代價最小的光路環，所以，在相同的業務總數下，USNET網絡中傳輸成功的業務的平均成員節點數目較少，從而消耗的轉發器就較少。然而，ESPA-OG算法和FLPC-OG算法在NSFNET網絡中的性能較優，這是因為NSFNET網絡中業務的平均物理跳數較少，受頻譜連續性和一致性的約束小，業務光疏導成功的概率較大。

圖5 NSFNET網絡中業務數與消耗的轉發器數目的關系

圖6 USNET網絡中業務數與消耗的轉發器數目的關系

圖7和圖8分別表示2個網絡的頻譜使用情況，可以看出，在相同的業務數下，本文提出的ESPA- OG算法性能最優，且ESPA-OG算法相比FLPC- OG算法、LPC-NG算法分別有約11%, 37%的頻譜節約。相比LPC-NG算法，ESPA-OG算法中采用了有效共享路徑感知的光疏導機制，節約了不同業務在有效共享鏈路上的保護帶，而LPC-NG算法中沒有光疏導機制，業務間保護帶會額外消耗網絡頻譜資源。相比FLPC-OG算法，ESPA-OG算法的預處理機制提高了業務間光疏導共享的鏈路數目，從而節約了更多的頻譜資源；而且，ESPA-OG算法的頻譜優先分配機制可以優先為參與疏導的業務分配頻譜，提高了光疏導在頻譜分配時的成功率。對比圖7和圖8可知，在相同的業務數下，3種算法在USNET網絡中消耗的子載波數目都比在NSFNET網絡中消耗的數目多，這是因為USNET網絡較大，業務的平均路由跳數較多，業務間保護帶所占用的總子載波數目就多。

圖7 NSFNET網絡中業務數與消耗的子載波數目的關系

圖8 USNET網絡中業務數與消耗的子載波數目的關系

圖9和圖10分析了節點的業務帶寬粒度與網絡消耗的頻譜資源的情況。可以看出，當節點的業務帶寬粒度從1′12.5 Gb/s增大到6′12.5 Gb/s(75 Gb/s)時，無論在NSFNET網絡還是在USNET網絡中，ESPA-OG算法性能均優于其他兩種算法。隨著業務帶寬粒度的增加，3種算法消耗的子載波數目都明顯增加。且與圖7和圖8相比，ESPA-OG算法和FLPC-OG算法的曲線上升幅度更加明顯。因為對于這兩種算法來說，隨著網絡中業務總數的增多，進行光疏導的業務數就增多，節約的頻譜資源就增多，故網絡頻譜總消耗數目的上升趨勢就不明顯；但是隨著業務粒度的增加，在相同的調制等級下，業務占用的子載波數目就明顯增加，光疏導節約的頻譜資源遠不及業務粒度的增加所消耗的頻譜資源，故網絡頻譜總消耗數目的上升趨勢很明顯。

圖9 NSFNET網絡中業務帶寬與消耗的子載波數目的關系

圖10 USNET網絡中業務帶寬與消耗的子載波數目的關系

5 結束語

本文研究了靈活網格光網絡中多點到多點組播業務的轉發器與頻譜資源優化問題，提出了一種光路環中基于距離自適應和有效共享路徑感知的光疏導方法，通過設計一種基于距離自適應的預處理機制，使得該疏導方法可根據業務成員節點的分布特點和距離自適應準則靈活地為業務構建光路環。在為業務進行路由時，該疏導方法構建了面向光疏導的決策矩陣，為業務選擇有效共享路徑最多的已路由業務進行光疏導，從而減少轉發器與頻譜資源的使用；為了增加光疏導后的頻譜分配成功率，該疏導方法還構建了優先調度向量，為進行光疏導的業務優先分配合適的頻譜空間。仿真結果驗證了本文算法可以很大程度上節約轉發器與頻譜資源的使用。對于未來工作，可以通過優化靈活網格光網絡的能耗模型和光疏導策略，來進一步節約資源消耗。

參考文獻

[1] Pagès A, Perelló J, Spadaro S,.. Optimal route, spectrum, and modulation level assignment in split-spectrum-enabled dynamic elastic optical networks[J]., 2014, 6(2): 114-126.

[2] Wang Yang, Cao Xiao-jun, Hu Qian,.. Towards elastic and fine-granular bandwidth allocation in spectrum-sliced optical networks[J]., 2012, 4(11): 906-917.

[3] 劉煥淋, 方強, 雷芳. WDM光網絡中多播業務量疏導方法分析[J]. 重慶郵電大學學報(自然科學版), 2012, 24(3): 269-277.

Liu Huan-lin, Fang Qiang, and Lei Fang. Analysis of multicast traffic grooming algorithms in WDM mesh networks[J].(), 2012, 24(3): 269-277.

[4] Guo Lei, Hou Wei-gang, Wei Xue-tao,.. Power efficient grooming based on optical bypass reconfiguration in green optical networks[J]., 2013, 124(5): 437-445.

[5] 劉煥淋, 劉洋, 陳勇, 等. WDM 光網絡中帶寬預留型業務的時間感知綠色疏導算法[J]. 北京郵電大學學報, 2014, 37(5): 71-74.

Liu Huan-lin, Liu Yang, Chen Yong,.. Time-aware green grooming algorithm for scheduled traffic in WDM networks[J]., 2014, 37(5): 71-74.

[6] Fallahpour A, Beyranvand H, Nezamalhosseini S A,.. Energy efficient routing and spectrum assignment with regenerator placement in elastic optical networks[J]., 2014, 32(10): 2019-2027.

[7] El-Gorashi T E H, Dong X, and Elmirghani J M H. Green optical orthogonal frequency-division multiplexing networks [J]., 2014, 8(3): 137-148.

[8] Christodoulopoulos K, Tomkos I, and Varvarigos E A. Elastic bandwidth allocation in flexible OFDM-based optical networks[J]., 2011, 29(9): 1354-1366.

[9] Zhang Shu-qiang, Martel C, and Mukherjee B. Dynamic traffic grooming in elastic optical networks[J]., 2013, 31(1): 4-12.

[10] 吳凡, 毛玉明, 黃曉燕, 等. OFDMA 系統中最優能效功率分配[J]. 電子與信息學報, 2014, 36(7): 1673-1679.

Wu Fan, Mao Yu-ming, Huang Xiao-yan,.. Optimal energy-efficient power allocation in OFDMA system[J].&, 2014, 36(7): 1673-1679.

[11] Eira A, Santos J, Pedro J,.. Multi-objective design of survivable flexible-grid DWDM networks[J]., 2014, 6(3): 326-339.

[12] Khodashenas P S, Comellas J, Spadaro S,.. Using spectrum fragmentation to better allocate time-varying connections in elastic optical networks[J]., 2014, 6(5): 433-440.

[13] Ye Z, Patel A N, Ji P N,.. Distance-adaptive and fragmentation-aware optical traffic grooming in flexible grid optical networks[C]. Proceedings of OptoElectronics and Communication Conference and Australian Conference on Optical Fiber Technology (OECC/ACOFT), Melbourne, 2014: 355-356.

[14] Xu Zhan-qi, Wang Jing, Xu Bo,.. Modelling and heuristic algorithms for routing and spectrum assignment in elastic optical networks[J]., 2014, 43(7): 0706004-1-0706004-5.

[15] Saleh M A and Kamal A E. Many-to-many traffic grooming in WDM networks[J]., 2009, 1(5): 376-391.

[16] Saleh M A and Kamal A E. Design and provisioning of WDM networks with many-to-many traffic grooming[J]./, 2010, 18(6): 1869-1882.

[17] Guo Lei, Hou Wei-gang, Zheng Ze-yu,.. Green provisioning of many-to-many sessions over WDM optical networks[J]., 2013, 31(20): 3289-3301.

[18] Shachnai H, Voloshin A, and Zaks S. Optimizing bandwidth allocation in flex-grid optical networks with application to scheduling[C]. Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), Phoenix, 2014: 862-871.

Method of Optical Grooming for Distance-adaptive and Effective Sharing Path-aware

Liu Huan-lin①Sui Meng①Xu Yi-fan①Chen Yong②Zhang Sheng-feng①

①(,,400065,)②(,,400065,)

In order to address the problem of reducing the resources of transponder and spectrum in flexible grid optical networks, a lightpath circle mechanism is studied for many-to-many multicast requests, and a method of optical grooming is proposed based on distance-adaptive and effective sharing path-aware. By designing a strategy of traffic pre-processing based on distance-adaptive, a lightpath circle is constructed according to the distribution characteristics of member nodes and the distance-adaptive criterion in the proposed method. In the process of routing and spectrum allocation, by constructing a decision matrix oriented optical grooming and a priority scheduling vector, the multicast request is groomed into the established traffic with the highest effective sharing links. Moreover, the appropriate spectrum resources are allocated for the groomed requests to increase the success rates of grooming and to save the resources of transponder and spectrum. Simulation results show that the proposed method can significantly reduce the number of traffic consumed transponders and sub-carriers.

Flexible grid optical networks; Lightpath circle; Optical traffic grooming; Sharing path-aware

TN929.11

A

1009-5896(2015)08-1964-07

10.11999/JEIT141442

劉煥淋 liuhl2@sina.com

2014-11-20收到，2015-04-15改回，2015-06-09網絡優先出版

重慶市教委自然科學基金(KJ1140421)，重慶市科委自然基金(2013jcyjA40052, 2011jjA1361)和國家自然科學基金(61275077, 61371096)資助課題

劉煥淋： 女，1970年生，教授，研究方向為光通信技術與未來網絡.

歲 蒙： 女，1988年生，碩士生，研究方向為光組播路由及頻譜分配算法.

徐一帆： 男，1990年生，碩士生，研究方向為綠色光網絡路由算法.