衛星融合交換系統負載均衡異構路徑算法

李靜玲，黎軍，張怡，崔濤，梁薇

中國空間技術研究院西安分院 空間微波技術重點實驗室，西安 710100

空間信息網絡中的微波激光混合通信技術集成了微波通信的高靈活性和激光傳輸的大帶寬、低損耗、高電磁兼容性的優勢[1]。未來的空間信息網絡必然是微波、激光等多種異構信息混合組網的形式，因此如何解決異構信息在衛星網絡節點上的混合交換成為未來空間異構信息組網的關鍵問題之一[2-3]。

地面網絡的迅速發展促使路由與交換技術不斷突破，其中光網絡由最初的SDH、MSTP、WDM、PTN/OTN逐漸演化到POTN，光、分組業務的路由與交換技術也由各自封閉獨立逐漸發展到相互融合[4]。其中，POTN網絡[5-6]集成了WDM/ROADM光層、SDH/OTN層和分組傳送層等的優良特性，在OTN層實現分組和電路業務的接入、匯聚和疏導，在光層實現損傷感知以及帶寬可變光波長級交換，但光骨干業務采用全光交換方式，將光、分組業務轉換為電業務進行分組交換，光、分組業務的交換屬于不同分層，并沒有在統一的交換系統中進行。在管理與控制面，地面通用多協議標簽交換(GMPLS)[7-8]對光、分組業務進行一體化標記，促進了光層與IP層的有機聯系，使得以光物理層為代表的傳輸網與以IP分組為代表的業務網進一步融合。

由地面光、電網絡的演化進展可以看到，光電進行深度融合是其技術發展的必然趨勢，光電交換也在進一步融合。

隨著與地面網絡的進一步融合，空間信息網絡包括大量異構信息的聚合、分發、管理和控制，異構信息交換可能發生在物理層、鏈路層或網絡層，僅靠現有的光交換或分組交換等獨立交換方式或其簡單組合形式，都無法適應空間信息的交換需求。文獻[9]提出由于星上資源的有限性，可借鑒光突發交換思想，在邊緣節點將控制信息采用分組格式封裝，提前發送進行資源預留，核心節點根據控制信息對突發包光域交換。但該方法還是一種光交換方式，沒有解決空間網絡多顆粒度統一交換問題。文獻[10]提出一種分布式交換模型，分別構建不同的光、分組交換矩陣模型，再通過交換矩陣模型的組合來完成多顆粒度業務的交換。文獻[11]提出一種光電融合交換信令模型，可對光電路徑進行一體化預約。文獻[1]提出空間光、射頻、分組融合交換的概念，指出其異構及多顆粒度等交換特點，并提出融合交換內部多路徑智能選擇問題。

由上述內容可知，衛星光電融合交換系統中，可能包含光數據流、分組數據流之間的數據交換，大顆粒度到小顆粒度數據流之間的數據交換，甚至單一數據流到多種數據流之間的數據交換。不同顆粒度業務可能通過不同的光、分組內部路徑組合的交換路徑進行聚合或分發交換，選擇不同的內部交換路徑對整體交換性能影響巨大，需要對其進行擇優選擇。若選擇不合理的交換路徑，可能造成交換網絡中部分路徑負載過于飽和，形成瓶頸鏈路，甚至導致路徑擁塞，而同時交換系統中的其他可用路徑處于空閑狀態，路徑資源沒有得到合理利用，使交換系統路徑負載不均衡、資源利用率不高。

文獻[12-13]基于經典的路由和波長分配(RWA)算法，提出根據各路徑上可用波長數來計算路徑的權值函數。文獻[14]提出針對LEO衛星網絡的并行鏈路不相交多徑路由算法SPEMR，該算法具有相對更強的實時傳輸海量數據的能力，主要聚焦于路徑的承載能力和傳輸時延等性能。文獻[15-16]提出以網絡鏈路剩余波長數量的方差為標準選擇路由，但該方法無法準確衡量分組路徑資源。文獻[17]根據鏈路時延因素和鏈路負載因素進行負載代價計算，但對于星上融合交換系統，其路徑跳數是確定的，鏈路時延因素并不是關鍵因素，而星上光、電鏈路負載本身差異巨大，無法單純通過負載進行路徑計算。文獻[18]針對空間信息網絡特點，提出基于負載均衡思想的虛擬網劃分方法，可以有效提高資源利用率。文獻[19]在所提出的光電混合數據中心網絡架構下，提出基于流量預測矩陣的負載均衡流量調度機制，但并沒有充分考慮光電異構特性。

目前，針對衛星網絡提出了大量負載均衡機制[18]及星間路由算法[20-21]，但并沒有提出針對空間光電融合交換系統的負載均衡路徑計算方法。本文提出異構光電交換路徑算法，根據異構路徑帶寬的不同定義最小粒度路徑帶寬；根據異構路徑與最小粒度路徑帶寬的關系來計算路徑可用負載，并針對異構路徑分發和聚合所導致的路徑個數差異；提出路徑個數參數來衡量異構路徑資源權值，而不是路徑跳數；通過選擇具有最大路徑資源權值的交換路徑，獲得滿足負載均衡準則的最優交換路徑。

1 空間光電融合交換結構

空間信息網絡主要包括光、分組兩類異構信息，通過單顆衛星節點或多顆緊耦合衛星節點，完成光、分組等多粒度業務的聚合及分發交換功能。如圖1所示，空間光電融合交換系統的交換結構[10]主要包括3個層級，即前級交換單元、中間級交換單元及后級交換單元，每個交換單元由不同光、分組交換矩陣模塊組合而成。交換系統中與外部輸出/輸入端口相連的光、分組端口稱為外部端口，內部交換矩陣模塊之間的互聯端口稱為交換系統的內部端口。光業務到分組交換矩陣模塊需要經過分發模塊，將一路光業務轉換為多路分組業務，而分組業務到光交換矩陣模塊需要經過聚合模塊，將多路分組業務轉換為一路光業務。

其中，分發和聚合模塊的作用是采用光電/電光轉換模塊對輸入業務進行轉換。由于光業務帶寬遠大于電業務帶寬。因此分發和聚合模塊主要針對業務帶寬。若由光業務轉換為電業務，即由高帶寬業務轉換為多路低帶寬業務，可視為數據的分發；若由電業務轉換為光業務，即由多路低帶寬業務轉換為高帶寬業務，可視為數據的聚合。通過上述準則來完成數據的分發和聚合功能。

2 異構交換系統負載均衡路徑算法

2.1 異構交換系統拓撲描述

在空間光電融合交換系統中，由某外部輸入端口經過交換系統中若干光、分組交換矩陣模塊，到外部輸出端口，所經過的路徑組合稱為該交換系統中的交換路徑；系統中光、分組交換矩陣模塊的某輸入端口到該矩陣模塊輸出端口稱為交換系統中的子路徑；系統中光、分組交換矩陣模塊的某輸出端口經過聚合/分發模塊到另一交換矩陣模塊的輸入端口稱為子路徑轉換。將該交換系統中的端口視為點，子路徑視為邊，其交換系統拓撲可表示為N=(V,E,T,X,Y)，其中V為網絡中所有端口(點)集合；E為網絡中所有子路徑(邊)集合；T是E上的資源(權值)函數；X為輸入端口(源點)集合；Y為輸出端口(匯點)集合。

在該交換系統中，業務從外部輸入端口，經過不同的光、分組交換子路徑組合，最終交換到外部輸出端口。其中業務經過的路徑跳數(即交換次數)相同，而由于光、分組承載的數據量不同，不同交換路徑(包含不同子路徑組合)對應的子路徑個數可能不同。

為了便于算法描述，定義以下相關符號：

T(l,w)：該參數表示空間交換系統路徑資源狀態信息表，標注當前所有子路徑的可用路徑資源，其中l代表交換系統中的子路徑，w表示該子路徑的可用路徑資源。

R(x,y)：該參數表示由外部輸入端口x到外部輸出端口y的交換信令請求。

P(x,y)：該參數表示由外部輸入端口x到外部輸出端口y的交換路徑集合。

L(x,y)：該參數表示由外部輸入端口x到外部輸出端口y的交換路徑所包含的子路徑個數。

H(x,y)：該參數表示由外部輸入端口x到外部輸出端口y的交換路徑所包含的路徑跳數，由交換結構所確定，圖1所示空間異構融合交換結構中的路徑跳數H(x,y)=3。

C(x,y)：該參數表示由外部輸入端口x到外部輸出端口y的交換路徑所包含的路徑轉換次數。業務在異構交換系統中，每經過一次分發或聚合處理，其業務類型即發生變化(由光業務轉換為分組業務或者由分組業務轉換為光業務)，該過程稱為業務經過一次路徑轉換。

2.2 異構路徑資源的統一衡量方法

在空間異構融合交換系統中，光、分組異構業務的交換資源差異巨大，光業務交換主要包括光波長、光開關、光時隙等資源形式，分組業務交換主要包括報文可用路由表項/轉發表項、可用緩存容量、分組時隙等資源形式。光、分組交換資源的異構特性從本質上是由于光業務的物理特性導致其無法緩存，必須提前配置交換路徑；而分組業務可以通過緩存進行存儲轉發。由于光、分組業務都是承載在路徑中的，雖然無法對交換資源進行直接衡量，但可以考慮間接通過路徑承載業務的能力來對異構資源進行定量衡量。因此本文提出構建最小粒度路徑帶寬因子作為異構路徑負載能力的衡量標準，將交換子路徑與該因子的關聯倍數作為衡量該子路徑資源的有效權值，構建異構路徑影響因子υα。

該影響因子的計算方法如下：

首先根據系統中光路徑和分組路徑各自的最大路徑帶寬，計算兩類路徑帶寬值的最大公約數，定義為最小粒度路徑帶寬α。α表征空間異構交換系統中光、分組交換帶寬的最小衡量單位。計算光、分組路徑所包含的最小粒度路徑帶寬α的個數，分別將光、分組路徑所包含的α個數與光路徑和分組路徑所包含α個數的總和相除，得到光、分組異構路徑帶寬比值。

2.3 負載均衡路徑算法約束設計

在詳細介紹算法之前，首先明確以下幾條約束。

1)由于空間異構交換系統包含的矩陣級數(前級、中級和后級)是確定的，因而業務在不同交換路徑中所經過的路徑跳數(即交換次數)是相同的；

2)由于光、分組路徑承載業務的能力不同，導致不同交換路徑所包含的子路徑個數可能不同，在相同業務負載下子路徑越多，交換系統的控制及調度功能就越復雜，因此本方法在同等業務負載下傾向于采用較少的子路徑個數；

3)由于路徑轉換會增加系統復雜度，在進行業務交換時，本論文以路徑轉換次數較小的交換路徑為優選路徑。

在空間異構交換系統中，與通常路徑算法不同的是，對于確定輸入/輸出端口的不同交換路徑而言，其路徑跳數是相同的，并不存在最短路徑，但由于其異構特性，導致交換路徑中的子路徑個數和路徑轉換次數可能不同，因此將子路徑個數和路徑轉換次數作為路徑權值的衡量因子。

2.4 負載均衡路徑算法思想

當空間異構交換系統接收到包含外部輸入/輸出端口信息的信令消息時，需計算該業務的交換路徑，并預留相應的光、分組異構交換資源。為了避免空間異構交換系統中不同子路徑上業務負載差異較大，從而形成瓶頸路徑，導致交換系統資源利用率降低，需要采取一定的均衡機制調節業務流量分布。本文通過異構路徑影響因子將異構特性對于路徑負載均衡的影響轉換為與異構路徑可用帶寬資源相關的具體數值，利于進行定量衡量；根據光、分組路徑承載業務的顆粒度差異，將交換路徑所包含的子路徑個數作為衡量路徑的關鍵參數之一，構建空間異構交換系統中異構路徑權值函數，如下式所示：

式(1)用于計算由外部輸入端口x到外部輸出端口y的交換路徑權值Cp(x,y)。其中Lwl為任意子路徑的可用資源值；ωl為同構子路徑影響因子；υαk為異構路徑影響因子。路徑生成流程如圖2所示，具體算法步驟說明如下：

圖2 衛星異構交換路徑生成流程

步驟1：首先初始化空間異構交換系統，獲取各交換矩陣模塊中每條子路徑的資源使用情況，建立資源狀態信息表T(l,w)，當申請新的交換路徑或釋放已存在的交換路徑時都要對其相關子路徑的資源狀態信息進行更新。

步驟2：當路徑信令請求R(x,y)到達時，根據業務外部輸入端口x與輸出端口y，計算出交換系統中所有交換路徑的集合P(x,y)。

步驟3：計算集合P(x,y)中的每一條交換路徑的子路徑個數L(x,y)、路徑跳數H(x,y)以及路徑轉換次數C(x,y)。

步驟4：計算同構路徑影響因子ω和異構路徑影響因子υα，其中影響因子υα的計算方法見2.2節，影響因子ω的計算方法如下：

1)通過資源狀態信息表T(l,w)查詢每條子路徑的可用路徑資源Lw；

2)計算該交換路徑中的同構路徑中每條子路徑的可用資源Lw占同構子路徑可用資源總數的百分比，并將各資源比值按從小到大的順序排列；

步驟5：通過式(1)異構路徑權值函數計算交換路徑集P(x,y)中每一條交換路徑的路徑權值Cp。

步驟6：將路徑權值Cp按照由大到小的順序排列，選取最大Cp值所對應的交換路徑。

步驟7：若所選交換路徑中存在子路徑可用資源值Lwl小于業務申請資源最小值Lwmin，轉到步驟9，否則轉到步驟8。

步驟8：將所選交換路徑作為交換路徑，根據信令申請消息預留相應光、分組交換資源，并更新T(l,w)中子路徑資源狀態信息。

步驟9：從交換路徑集P(x,y)中刪除所選路徑，繼續判斷P(x,y)是否為空，若不為空，轉至步驟7，若為空，則本次信令申請失敗。

3 仿真分析與性能評價

在圖1所示衛星異構交換模型基礎上進行異構路徑算法(LBHP)的仿真分析。通過對比采用傳統的路由與波長分配(RWA)算法[12-13]，仿真了LBHP算法在隨機業務請求下的路徑負載平衡度、路徑阻塞概率性能，并對算法仿真結果進行分析。

3.1 仿真設置

為了驗證所提算法性能，采用Matlab與OMNET仿真工具進行聯合仿真，通過OMNET搭建衛星異構交換模型如圖3所示。該模型包括2個光業務輸入模塊(Port0，Port1，每個模塊設置2個端口)，2個分組業務輸入模塊(Port2，Port3，每個模塊設置4個端口)；輸出模塊(Port4，Port5，Port6，Port7)負責接收相應業務；交換矩陣包括前、中、后3級，其中前級包含2個2×2光交換矩陣(SwitchA、SwitchA1)和2個4×4分組交換矩陣(SwitchA2、SwitchA3)；中間級包含1個4×4光交換矩陣(Optical_switch)和一個16×16(Packet_switch)分組交換矩陣；后級與前級的架構相同。

圖3 衛星異構交換仿真模型

3.2 評價指標

本文所仿真的衛星異構交換系統總交換容量為15 Gbit/s，端口數為12×12，其中光端口為4×4，分組端口為8×8。光端口速率為2.5 Gbit/s，分組端口速率為625 Mbit/s，光、分組路徑帶寬比為4:1。采用增加業務模式進行仿真，當業務連接建立后，除非收到拆除信令，否則交換系統中的交換資源一直占用，不會被自動釋放。

定義參數路徑負載平衡度(LBD)：

定義參數路徑阻塞概率(PCP)：

PCP=LB/|L|

(3)

式中：若當前子路徑可用資源數w(l)

3.3 仿真分析

圖4、圖5展示了在隨機業務下，傳統RWA(路由與波長)算法與本文所提LBHP(異構交換負載均衡路徑)算法的路徑負載平衡度(LBD)和路徑阻塞概率(PCP)指標，分析算法性能及適用范圍。

圖4 不同業務請求下的網絡負載平衡度

圖5 不同業務請求下的網絡路徑阻塞率

如圖4(a)所示，在0～120個隨機業務請求下，傳統RWA算法在進行路徑選擇時，并沒有綜合考慮光、分組交換路徑的相互影響。將該算法進行了10次仿真，每次計算得到的交換路徑及LBD值都不同，而LBHP算法得到的結果都相同，其算法穩定度更優。當業務量為120個時，LBHP算法的LBD值接近0.06，小于傳統RWA算法得到的最低LBD值，其性能優于傳統算法。如圖4(b)所示，將傳統RWA算法經過10次仿真得到的路徑負載平衡度值進行平均，并與本文LBHP算法比較，可以看到LBHP算法可以有效降低負載平衡度，在網絡負載值達到120時，可將LBD值降低約32%，有效增強網絡負載平衡能力，提高交換系統路徑利用率。

圖5(a)比較了LBHP算法和傳統RWA算法在0～240個隨機業務請求下的阻塞概率。可以看到，傳統負載均衡算法無法綜合權衡光電融合交換系統的整體路徑資源情況，在進行的10次仿真下得到的結果都不同，且在隨機業務請求接近50時開始出現路徑阻塞；而LBHP算法不僅在不同次計算時的結果都保持一致，且在業務到達率接近200時才開始出現路徑擁塞。如圖5(b)所示，將傳統算法的10次仿真結果進行平均，在相同業務到達率下，LBHP算法的路徑阻塞概率均等于或低于傳統算法，當隨機業務請求達到240個時，LBHP算法的路徑阻塞率相對于傳統算法降低約51%。

綜上可以看到，在算法穩定性及算法性能方面，本文所提LBHP算法均優于傳統RWA算法。

4 結束語

衛星光電融合交換系統是未來空間衛星組網中的關鍵技術之一。由于空間體系架構特點以及對資源高效利用的需求，衛星光電交換系統并不適合采用現有的光電獨立交換或僅部分模塊融合的方式，而應尋求更進一步的融合機制。

基于衛星異構融合交換結構以及光電一體化信令方案，本文所提出的光電異構資源負載均衡路徑算法，不僅可以保證交換路徑計算結果的一致性，也可獲得基于負載平衡度以及路徑阻塞率指標的交換路徑的優化計算結果，對于衛星光電異構交換系統的深度融合有著較大的研究及應用意義，可極大提升衛星光電交換系統整體性能。在未來工作中，需要進一步加強本文所提算法的數學模型分析及構建。