基于最小節點負載優先的邏輯承載網構建方法

李志敏 ，湯創為 ，譚敏生 ，王 舒 ，周 歡

LI Zhimin1，2,TANG Chuangwei1,TAN Minsheng1,WANG Shu1,ZHOU Huan1

1.南華大學 計算機科學與技術學院，湖南 衡陽 421001

2.湖南機電職業技術學院 信息工程學院，長沙 410151

1.School of Computer Science and Technology,University of South China,Hengyang,Hunan 421001,China

2.Shool of Information Technology,Hunan Mechanical&Eelectrical Polytechnic,Changsha 410151,China

1 引言

近年來，網絡技術取得了飛速發展，服務能力比以前有了很大提高。現有網絡采用面向業務支撐的體系架構，用戶業務和網絡提供的服務是緊耦合關系。當用戶出現了新的業務需求，或者對原有業務的需求提高時，就需要對網絡進行改造，而這種改造通常都是從增加鏈路帶寬、提高節點處理速度、增加協議的復雜度等方面展開，難以滿足特性差異日益擴大的用戶業務承載需求[1]。一體化邏輯承載網是一種面向服務提供的新型網絡技術體系，它根據網絡服務提供能力和用戶的業務需求及業務特性，以可重構路由交換平臺為物理基礎。這種定制網絡的服務提供方式能夠更好地滿足用戶多樣化的業務需求，是將來網絡技術發展的趨勢[2]。

構建邏輯承載網的關鍵是對鏈路帶寬、節點端口等公共資源進行分配，如何在資源有限的情況下有效地構建功能可升級重組，性能可編程分配，管理可分層配置的邏輯承載網，是一體化網絡研究的熱點問題[3]。文獻[4]研究了低成本的虛擬網構建問題，提出了基于收益的啟發式算法的虛擬網構建方法。文獻[5]利用混合整數規劃，針對不同的應用場景，提出了確定型虛擬網映射算法（D-ViNE）及隨機虛擬網映射算法（R-ViNE）。文獻[6]認為底層物理網絡中的一條虛擬鏈路可以由多個分割的物理路徑組成，提出了基于多商品流問題，并采用啟發式算法進行路徑集構建。文獻[7]采用子圖同構判定技術，綜合考慮構建過程中的節點映射和鏈路映射，將節點和鏈路映射同時進行。文獻[8]通過基于流量均衡并采用子圖分割以及節點優化策略來實現虛擬網的拓撲設計。

上述虛擬網的構建方法，沒有考慮底層物理網絡的整體均衡性，一方面容易導致物理網絡上發生擁塞或者出現節點負載過重的問題，尤其是在最短路徑上，從而降低網絡傳輸性能；另一方面，由于后續建網的關鍵路徑很可能被占用，導致其構建成功率大大下降。針對上述構建方法的不足，本文在節點虛擬網構建算法中將多源多匯問題簡化為多個單源單匯問題進行求解，在構建邏輯承載網時充分考慮底層物理網絡的均衡性，提出最小節點負載優先映射策略（MinNLP），在此基礎上通過實驗從構建成功率、節點資源利用率、節點負載標準差三方面來驗證MinNLP的優越性。

2 邏輯承載網模型分析

將邏輯承載網構建需求用無向圖Gu=(Nu，Eu，Ru)表示，其中Nu和Eu代表邏輯承載網中虛節點和虛邊的集合，它們分別是Np和Ep的子集，邏輯承載網構建請求通常包含對物理節點和邊的限制條件，用Ru表示這些約束條件。

邏輯承載網厚繭問題在圖論上的描述就是從Gu到Gp子集的一個滿足Gu中約束條件Ru的映射，表示如下[9]：

其中 Ns?Np，Es?Ep，Cs代表構建邏輯承載網的物理網絡服務能力。

節點映射：

鏈路映射：

將邏輯承載網的構建轉化為單源單匯問題求解，構建需求就可以分解為虛節點需求和虛鏈路需求，由三元組 (s，t，d)表示，其中 s、t為源目節點，d 為帶寬需求，這樣分解后，邏輯承載網的構建問題簡化為逐一求解元需求的過程[10]。

3 最小節點負載優先映射策略

節點負載是底層物理節點的負擔，不同的承載網構建算法可能導致不同的節點負載。能夠獲得負載較均衡的映射算法可以實現資源更有效的利用，而均衡性較差的算法可能使得某些節點負載很輕，某些節點負載很重，這樣很有可能會因為某些重要節點的資源不夠而拒絕請求[11]。

定義1（節點強度SN）節點上承載的LCN資源之和與該節點擁有的資源的比值。

在虛擬網的研究中，多采用節點承載的虛擬網個數來描述節點的負載強度，因為虛擬網節點主要是服務器，節點的資源主要是內存、CPU等。一體化邏輯承載網絡的節點資源主要是可重構的路由交換平臺，節點的處理能力受到內存、CPU和節點交換帶寬等影響，本文采用歸一化的處理方式，只考慮內存使用情況反映節點負載，因此：

HNi表示第i個邏輯承載網占用某個節點的資源量，HNall表示該節點總的資源量，k為所承載的LCN的個數。

定義2（節點資源剩余量RN）在某時刻節點經過一系列的映射后還剩余的資源：

其中，HNi表示第i個邏輯承載網所花費的節點資源，而HNall為總的節點資源。

那么基于節點負載的構建策略思想就是在每次節點映射時選擇負載較小且滿足需求的物理節點進行映射。當有多個節點的負載強度相同時，就用節點資源剩余量為輔助標準[12]。

如圖1所示，物理節點a、b、c的資源總量分別為80、60、40。在 T0 時刻，節點a、b、c的負載強度和剩余資源分別是25%（60），16.7%（50），12.5%（35）。 T1時刻，虛擬節點4（VN-4）到達，資源需求為5，此時節點c具有最小節點負載，且 Rn-c＞5，所以VN-4映射到節點c，映射后各節點負載強度和剩余資源分別為25%（60），16.7%（50），25%（30）。 T2時刻，虛擬節點5（VN-5）到達，資源需求為10，此時a和c的負載強度相同，但是Rn-a大于 Rn-c且大于10，所以VN-5映射到節點a，映射后各節點負載強度和剩余資源分別為37.5%（50），16.7%（50），25%（30）。 T3時刻，虛擬節點6（VN-6）到達，資源需求為20，此時節點b具有最小節點負載，且Rn-b＞10，所以VN-6映射到節點b，映射后各節點負載強度和剩余資源分別為37.5%（50），35%（30），25%（30）。

最小節點負載優先映射策略的目標是在節點映射時實現底層物理節點的負載均衡，通過綜合考慮節點負載和節點剩余可用資源，提高資源利用率。

圖1 最小節點負載優先的映射策略原理

最小節點負載優先映射策略的核心思想描述如下：

（1）將虛擬節點(Vnode)按申請資源大小排序。

（2）判斷Vnode是否有剩余，若無剩余跳至步驟（5）。

（3）若Vnode有剩余，選擇申請資源最多的Vnode映射到具有最小負載強度且相對剩余資源較多物理節點(Snode)。

（4）若找不到滿足資源需求的Snode，則將該LCN請求送入等待隊列或拒接請求，若能找到映射節點則跳到步驟（2）。

（5）節點映射成功，等待執行鏈路映射。

4 最小節點負載優先的邏輯承載網構建方法

在底層物理資源有限的條件下，考慮對LCN的構建請求執行接入控制，借鑒最小節點負載優先的思想，采用周期性的LCN映射處理方式來考慮LCN的映射處理問題。將LCN的到達過程看成是排隊系統，LCN請求實時到達，以時間窗LCN映射的時間單位，對一個時間窗內到達的LCN構建請求進行收集，在一個時間窗內進行一次映射。如圖2所示，LCN在時間窗模式下映射的方法是：

（1）釋放上個時間窗內離開的LCN請求占用的資源，包括到達服務時間和主動拒絕的請求。

（2）統計本時間窗內LCN構建請求，包括新到達的請求和上個時間窗內為映射成功重新排隊的請求。

（3）將LCN構建請求按實際收益多少降序排序，然后按收益大小映射到物理網絡。如果該LCN映射成功，更新物理網絡底層資源狀態；如果映射失敗，則將該請求放入等待隊列，等待下一個時間窗來映射，對每個LCN請求允許重新映射的最大請求次數Max-Mapping預先設置，超過最大請求次數將不再送入等待隊列，該LCN構建請求被拒絕。該映射方法能夠保證LCN的實時處理，并且能夠通過調節入口參數實現LCN準入機制的調節。在單位時間窗內，基于最小節點負載優先的邏輯承載網構建的核心算法描述如下：

圖2 時間窗模式下LCN映射架構圖

Sort（LCN）表示對單位時間窗內已有或新加入的LCN構建請求按收益排序；NumLCN為LCN構建數目；NumLCN_max為單位時間窗允許構建的最大值；Wait（NextLCN）表示等待下一個時間窗對LCN的映射；Resolve（LCN_max）為對最大收益的LCN進行分解；(s′=＞s，d′=＞d＜—MLS)表示采用最小節點負載優先策略（MinNLP）對 s、d進行節點映射；(Jump≤Rjump＜—KSP)表示采用K短路徑優先（KSP K Shortest Path）的鏈路映射算法[13]進行鏈路映射，并且滿足約束條件Jump≤Rjump；JoinWait（LCN）代表LCN加入等待隊列；s′∈Gs，d′∈Gs，w(s′，d′)＞ 0，Rjump≥ 1。

5 實驗及分析

5.1 仿真實驗平臺

本文使用Java語言設計仿真器來評估算法性能。該仿真器能夠產生承載網請求，并將請求轉化為單源單匯形式。請求隊列管理器主要負責請求隊列和時間窗的管理，資源狀態管理器主要動態跟蹤物理資源的變化情況，請求映射管理器負責承載網的映射，是仿真器的核心，通過給定的算法將邏輯承載網映射到底層物理網中，同時展現映射結果，輸出各種實驗數據（圖3）。

圖3 仿真器架構圖

5.2 參數設置

給定20個節點的物理網絡，節點資源在20到30之間隨機分布，每條物理鏈路帶寬資源在8到12個單位隨機分布；每個LCN的節點數在3到5之間，節點需求資源在4到6之間，帶寬資源請求在1到3之間隨機分布。每個LCN的生命周期為一個時間窗，時間窗大小設置為60 s，前5個時間窗內LCN請求數在4到6之間均勻到達，后5個時間窗LCN請求數在15到18之間均勻到達，實驗一共模擬10個時間窗，并進行10組實驗，統計每次實驗結果，取其平均值。

用下面兩種LCN構建方法進行仿真實驗：

（1）G-SP方法。基于貪心K短路徑思想構建，其中節點映射采用貪心（Greedy）算法[14]，鏈路采用K短路徑算法（K Shortest Path）映射。

（2）MinNLP-LLB方法。基于最小節點負載優先K短路徑思想構建，節點采用最小節點負載優先（Minimum Node Lode Priority，MinNLP）算法，鏈路采用鏈路負載均衡策略映射LLB（Link Lode Balance）[15]。

5.3 構建成功率

圖4 MinNLP-LLB與G-SP構建成功率對比曲線

構建成功率是指單位時間內LCN構建成功的個數與總的申請數的比值。由圖4可以看出，在第一個時間窗內，節點和鏈路基本處于空閑狀態，底層物理資源相對較多，兩種方法的構建成功率都接近100%。在第二個時間窗內，由于第一個時間窗構建的LCN還未離去，占用的資源還沒有釋放，因此兩者的構建成功率出現了小幅度下降。第二個時間窗到第五個時間窗，隨著原來存在的LCN達到生存時間，網絡資源不斷被釋放，構建成功率達到一種統計上的穩定狀態，此時Min-LLB優勢初步顯示出來。第六個時間窗開始，由于大幅度增加了每個時間窗內LCN的請求個數，相對可用資源減少，兩種方法的構建成功率出現了大幅度下降，第六個時間窗兩種方法的構建成功率只有50.7%和36.3%。第七個時間窗開始到實驗結束，構建成功率達到一種統計上的穩定狀態，兩者的構建成功率在46.5%和35.5%左右。從兩個時間段的差異可以看出，在底層物理資源數不變而LCN請求數量大增的情況下，MinNLP-LLB方法的優勢非常明顯，構建成功率比G-SP方法高出近11個百分點。

5.4 資源利用率

單位時間窗構建LCN所花費資源與物理網總資源的比值。圖5橫坐標表示運行的時間窗，縱坐標表示LCN的資源利用率。在第一個時間窗到第五個時間窗內，由于實驗設定的LCN的生存時間為一個時間窗，某個時間窗結束時，上一個時間窗生成的LCN也達到離開時間，對整個物理網而言承載的LCN數量較少，大部分資源處于空閑狀態，因此該階段兩種方法節點資源利用率相近且處于較低的水平，MinNLP-LLB的優勢不明顯。到第六個時間窗，LCN的請求數量大增，雖然兩種方法的構建成功率下降了，但是整個物理網承載的LCN增加。由于MinNLP-LLB方法在資源分配過程中考慮了實時負載情況，因此利用該方法構建時，在單位時間LCN請求增多的情況下，節點資源利用率達到了77.9%，遠高于G-SP方法的63.7%。

圖5 MinNLP-LLB與G-SP節點資源利用率對比曲線

5.5 鏈路均衡度

為了更詳細描述資源在物理網絡中的使用情況，還需要考慮每個局部的情況，主要考慮局部資源使用率和整個網絡資源使用率的差異，即鏈路均衡度：

其中SLi(t)表示第t次抽樣時節點i的負載強度表示第t次抽樣時節點平均負載強度，其中e表示節點的總個數，其值越小，鏈路負載就更加平衡，說明網絡處于均衡使用的一種狀態。

從圖6可看出，在每個時間窗內，用MinNLP-LLB構建方法的鏈路均衡度均小于G-SP方法，說明鏈路負載越均衡，瓶頸節點的出現幾率就越小。

圖6 MinNLP-LLB與G-SP鏈路均衡度對比曲線

在底層物理資源充足，而請求構建的邏輯承載網較少時，MinNLP-LLB方法與G-SP方法的構建成功率基本相同，但MinNLP-LLB方法比G-SP的休眠率低13個百分點左右，表明MinNLP-LLB方法使用相對較多的物理節點，網絡拓撲相對復雜。但在映射后期，映射請求逐漸增多，MinNLP-LLB方法更大幅度地提高構建成功率、資源利用率和鏈路均衡度，更適合用來構建邏輯承載網。

6 結束語

作為下一代網絡關鍵技術的一體化邏輯承載網絡技術已逐漸成為研究熱點。本文分析了承載網的數學模型，提出了最小節點負載優先映射策略，在此基礎上給出了基于最小節點負載優先映射策略的邏輯承載網構建方法，并通過實驗從三個方面驗證了MinNLP-LLB的優越性。

邏輯承載網的構建方法還有很多問題有待進一步研究與探索，本文只是針對如何使得物理網更均衡映射進行研究，除此之外，用戶業務聚類、安全架構、適合大規模組網的構建算法，是下一步研究的重點。

[1]張偉，吳春明，姜明，等.一體化承載網絡的互斥問題研究[J].計算機應用研究，2010，27（3）：1148-1150.

[2]汪斌強，鄔江興.下一代互聯網的發展趨勢及相應對策分析[J].信息工程大學學報，2009，10（1）：1-6.

[3]張宏科.“一體化可信網絡于普適服務體系基礎研究”項目計劃任務書[R].北京：北京交通大學，2007.

[4]Lu J，Turner J.Efficient mapping of virtual networks onto a shared substrate，Technical Report WUCSE-2006-35[R].Washington University，2006.

[5]Mosharaf N M，Raihan R M，Raouf B.Virtual network embedding with coordinated node and link mapping[C]//Proceedings of the 28th Coference on Computer Communications.Riode Janeiro，USA：IEEE，2009：783-791.

[6]Yu Minlan，Yi Yung，Rexford J，et al.Rethinking virtual network embedding：substrate support for path splitting andmigration[C]//Proceedingof ACM SIGCOMM on Computer Communication，Seattle，WA，USA，2008：17-29.

[7]Jens L，Holger K.A virtual network mapping algorithm based on subgraph is omorphism detection[C]//Proceeding of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures，Barcelona，Spain，2009：81-88.

[8]Zhu Y，Ammar M.Algorithms for assigning substrate network resources to virtual network components[C]//Proceedings of IEEE INFOCOM，Barcelona，Catalunya，Spain，2006：1-12.

[9]齊寧，汪斌強，郭佳.邏輯承載網構建方法的研究[J].計算機學報，2010，9（15）：1536-1537.

[10]張旻，吳春明，王濱，等.跨域邏輯承載網映射方法研究[J].通信學報，2012，33（8）：200-208.

[11]張棟.基于可重構柔性網絡的邏輯承載網構建理論與方法[D].杭州：浙江大學，2010.

[12]Cui Y，Wu J P.Research on Internetwork QoS routing algorithms：a surevey[J].Journal of Software，2002，13（11）：2065-2075.

[13]齊寧.基于網絡生存性可重構服務承載網構建算法研究[D].鄭州：解放軍信息工程大學，2011.

[14]李文，吳春明，陳健，等.物理節點可重復映射的虛擬網映射算法[J].電子與信息學報，2011，33（4）：908-914.

[15]王海英，張建忠.多鏈路管理中的負載均衡策略[J].南開大學學報：自然科學版，2004（4）：59-63.