利用ＳＤＧＰ算法進行實時動態帶寬分配的研究及仿真

摘 要：提出一種在網絡通信帶寬分配領域，結合自動控制理論，利用基于優先級的串行主導因子法對鏈路帶寬進行動態分配的方案。該算法通過引入主導因子和容忍因子，可以實現在具有流量工程基礎的網絡中對共享帶寬進行實時動態分配。

關鍵詞：基于優先級的串行主導因子法；主導因子；容忍因子；帶寬分配

中圖分類號：TP393.04 文獻標識碼：A 文章編號：1004373X(2008)1506704

Research and Simulation for Dynamic Bandwidth Deployment with SDGP Algorithm

YU Xi，LI Dan

(College of Information Science and Technology，Chengdu University，Chengdu，610106，China)

Abstract：This pager refers to a dynamic bandwidth deployment method called SDGP algorithm，which comes from automatic control theory.SDGP has capability to locate the bandwidth in flux engineering network dynamically by introducing two control parameters: Leading key ξ and acceptance key ρ.

Keywords：SDGP;leading key;acceptance key;wideband distribution

1 引 言

現代網絡技術中，以提升網絡服務質量，提供更多網絡業務為目的的網絡構建，越來越多地使用到流量工程。以基于MPLS (Multiprotocol Label Switching，多協議標簽交換)的PWE3(Pseudo Wire Emulation Edge-to-Edge，邊緣到邊緣的偽線仿真)網絡為例，不是隨時都存在足夠資源，使每條Pseudo Wire連接都能擁有完全獨立的LSP流量路徑，這就不可避免地存在多條Pseudo Wire共享一段LSP鏈路的有限帶寬，如圖1所示\\。

這種情況不僅局限于PWE3網絡，在其他具有流量工程基礎的網絡中，在配置鏈路共享帶寬時，都會遇到以下問題：

可操作性問題 配置方法復雜，專業性強，配置時需要網絡設備制造商的技術支持人員進行指導，用戶自行配置易出錯。

合理性問題 用戶通常知道每條連接的數據流的重要性，卻只能簡單采用固定帶寬分配方法為每條連接分配相應帶寬，這種分配方法隨意性較大，存在不合理因素。

靈活性問題 用戶常常希望在保證合理性的基礎上，根據自身需求，能夠進行更為靈活的帶寬配置，比如允許分配的帶寬值在一定的接受范圍內進行浮動。

及時性問題 用戶完成帶寬分配后，通常很長時間內保持不變，更新率低。不能及時根據網絡流量變化調整，使有限的帶寬得到優化配置。

為解決以上網絡中共享帶寬的分配問題，需要研究一種易操作、合理的、靈活的、及時的、能充分利用網絡資源和提升網絡效率的實時動態帶寬分配算法。這里的“實時”指表現這種帶寬分配算法的及時性，“動態”則表現了這種算法進行帶寬配置需要以動態變化的數據流量為主要依據。在這種需求下，通常會首先考慮到應用流量反饋進行實時帶寬分配控制。但是網絡帶寬分配的控制具有其特殊性，具體表現在：帶寬限制對使用不同協議流量源的影響是不確定的，其作用反饋到使用不同協議的流量源上，使得網絡流量增加、減少或者不變都是有可能的。因此流量反饋的實時帶寬分配控制方案，在研究諸如PWE3網絡環境的動態帶寬分配算法上，并不是理想的研究方向。

本文提出的一種解決方案是：在網絡通信帶寬分配領域，結合自動控制理論，利用基于優先級的串行主導因子法(Serial Dominant Gene with Priority，SDGP)對鏈路帶寬進行動態分配的方案。通過引入主導因子ξ和容忍因子ρ，實現PWE3網絡中共享帶寬的實時動態分配。同時，SDGP算法也能夠為其他具有流量工程基礎的網絡提供實時動態帶寬分配方案。

2 SDGP算法原理

仍以PWE3網絡為例，某條鏈路可分配的共享帶寬為Bwmax。某時刻，該鏈路具有N條優先級從Pri0到PriN-1(Prii=Prii+1或Prii=Prii+1-1，0≤i≤N-2)的Pseudo Wire數據流。其中優先級數值越小，代表優先級越高，故Pri0=0優先級最高，且不存在優先級跳躍情況。從優先級Pri0到PriN-1，具有相同優先級的數據流條數表示為ε0，ε1，ε2，…，εk(0≤k≤N-1)，其中k表示N條數據流中，共有k個不同的優先級別，且εm(0≤m≤k)與N具有以下關系：∑km=0εm=N (0≤k≤N-1)(1) 當使用SDGP方法后，系統將進行周期為T的實時檢測和調整，重新分配從Bw0到BwN-1的各條數據流的帶寬。重新分配帶寬的計算順序基于每條數據流的優先級，從優先級最高的流開始，逐步分配帶寬，直到優先級最低的數據流帶寬分配完畢。Bwi表示第i條數據流應分配的帶寬。Bwrevi則表示第i條數據流分配后，鏈路剩余的共享帶寬值。兩者關系為：

Bwrevi=Bwi+1+ Bwrev(i+1) (0≤i≤N-2)(2)

且不難推導Bwi，Bwrevi和Bwmax的關系為：Bwrevi=Bwmax-∑ij=0Bwj

(0≤i≤N-1，0≤j≤N-1)(3) 在進行每條數據流的帶寬分配時，引入兩個重要調節控制因子：主導因子ξ和容忍因子ρ。ξi(0≤i≤N-1)表示第i條數據流的主導因子；ρi(0≤i≤N-1)表示第i條數據流的容忍因子。在通常需求下，網絡中所有數據流的主導因子都相同，且所有數據流的容忍因子也相同，即ξi=ξ，ρi=ρ，(0≤i≤N-1)。

主導因子ξi的物理意義表示第i條數據流相較其余優先級更低的數據流，在鏈路剩余共享帶寬中應該分配得到帶寬的比率。經過主導因子處理過的目前剩余帶寬稱為第i條流的主導帶寬，表示為Bwξi(0≤i≤N-1)。Bwξi在利用主導因子法進行帶寬分配時，具有重要作用。當共享帶寬的數據流優先級嚴格區分，互不相同的情況下，Bwξi計算方法為：Bwξ0=Bwmax×ξ(4)

Bwξi=Bwrev(i-1)×ξ (1≤i≤N-1)(5) 當共享帶寬的數據流優先級存在重疊現象時，需要利用εm(0≤m≤k)對以上兩個公式實施改進，以支持優先級重疊時Bwξi的計算。假設對優先級為Prii-1(Prii-1

Bwξi=Bwrev(i-1)×ξ′

(ξ′=ξ/εm，1≤i≤N-1，0≤m≤k)(7)

Bwtemp=Bwrev(i-1) (1≤i≤N-1)(8)

當Prii=Prii-1時:

Bwξi=Bwtemp×ξ′

(ξ′=ξ/εm，1≤i≤N-1，0≤m≤k)(9)

下文未加說明處，所使用的主導帶寬Bwξi均指利用支持優先級重疊的改進算法，由式(6)到式(9)計算得到的。

容忍因子ρi的物理意義表示當第i條流實際流量不足其Bwξi帶寬時，是否容忍其繼續占有多余帶寬與主導帶寬Bwξi的比率。值得注意的是，容忍因子ρ根據其應用方式不同，表現出較大靈活性，不僅適用于本節SDGP算法需要，即系統中流量不足引起的“下容忍”，也可以調節流量過載引起的“上容忍”，甚至對系統剩余保留帶寬Bwrev也能進行容忍范圍調節。本節研究的SDGP算法所涉及的“下容忍”標線稱為容忍帶寬，表示為Bwtoli，其具體算法為：Bwtoli=Bwξi×(1-ρ) (0≤i≤N-1)(10) 在一個T周期內，第i條數據流實際流量表示為Fluxi(0≤i≤N-1)，當第i條流分配帶寬時，先利用容忍帶寬Bwtoli與Fluxi進行比較，根據比較的結果不同，進行相應的帶寬分配。如果判斷為不能容忍第i條流分配到過多帶寬，則只對第i條流分配其流量加上容忍因子所容忍的最大額度流量帶寬；如果判斷為第i條流的閑置帶寬為0，或者在容忍范圍之內，對其分配的帶寬等于主導帶寬Bwξi大小。具體實施分配策略如下：

Bwi=Bwξi (當Fluxi≥Bwtoli時，0≤i≤N-1)(11)

Bwi=Fluxi+Bwξi×ρ

(當Fluxi

當在一個T周期內，利用主導因子法完成所有數據流的帶寬分配后，延時到下一個周期到來，并再次利用主導因子法，根據下一個周期到來時，實時流量的狀況進行帶寬分配，從而實現基于SDGP算法的實時動態帶寬分配。

根據以上分析，不難看出主導因子ξ和容忍因子ρ之間關系表現為：主導因子ξ對共享帶寬進行主要的、粗糙的分配和調節；容忍因子ρ則對ξ調整后的帶寬進行細微的，靈活的二次調配。只有兩者相互配合，共同作用，才能根據系統流量及時合理地利用SDGP算法進行系統的實時動態帶寬分配。

3 SDGP算法實現

在上節SDGP算法原理研究的基礎上，本節將對SDGP算法的具體實現進行討論。考慮到工程實現的方便性、移植性和維護性，故采用算法組件化思想對SDGP算法系統劃分為3大組件單元：SDGP Kernel Unit，Stream Information Collection Unit和Assignment Execution Unit。具體架構如圖2所示。

圖2 SDGP算法系統實現架構當網絡節點使用能SDGP算法模塊進行實時動態帶寬分配后，Stream Information Collection Unit將在每個T周期開始時，負責實時收集Network Node上需要進行帶寬分配的數據流信息。這些收集到的信息可以直接實時傳送到SDGP Kernel Unit，也可以保存在Trace文件中再供給SDGP Kernel Unit使用。SDGP Kernel Unit的作用是對進行收集到的需分配共享帶寬的數據流信息進行分析，并根據SDGP算法進行帶寬指派。經過SDGP Kernel Unit完成的帶寬分配信息，將傳遞到Assignment Execution Unit，由其進行具體的帶寬分配下發工作。

在整個SDGP算法模塊中，SDGP Kernel Unit處于核心地位，其處理流程圖如圖3所示。

圖3 SDGP Kernel Module處理流程4 SDGP仿真及結果分析

SDGP實時動態帶寬分配算法仿真方案如下：

假設在基于MPLS的PWE3網絡中，存在7條Pseudo Wire流(從Stream0到Stream6)需要共享一段100 Mb/s的LSP鏈路帶寬。其中，Stream0的優先級為0，Stream1和Stream2的優先級為1，Stream3，Stream4和Stream5的優先級為2，Stream6的優先級為3。當完成設置主導因子ξ和容忍因子ρ，且使用SDGP算法后，7條數據流開始進行流量變化，以檢測SDGP算法是否能夠及時合理地動態調整帶寬分配。其流量變化的具體策略為：首先7條流都具有100 Mb/s流量，然后Stream0由100 Mb/s開始，每隔一個T=1 sec依次減小5 Mb/s，直到Stream0流量變化為0，接著Stream1開始模仿Stream0進行流量變化，直到Stream1流量變化為0，依此類推，剩余Stream2到Stream6的流量依此規律進行變化，直至需要共享此段帶寬的7條數據流量都減至為0。這種流量輸入設計策略的好處在于，不僅可以收集每個T周期所完成的流量分配數據，還可以收集到多條數據流從流量過載變化到流量不足過程中，SDGP算法進行實時動態處理的帶寬分配數據，比較全面反映了SDGP算法對流量變化的應對處理結果，為準確地進行仿真分析奠定了基礎。

以下使用Network Simulator 2在Linux環境下對SDGP算法進行仿真，以觀察其性能。其中，主導因子ξ和容忍因子ρ具有不同配置。部分SDGP Kernel Module代碼見附錄。

當ξ=0.5，ρ=0.1時，仿真結果如圖4所示。

當ξ=0.7，ρ=0.1時，仿真結果如圖5所示。

當ξ=0.5，ρ=0.2時，仿真結果如圖6所示。

當ξ=0.7，ρ=0.2時，仿真結果如圖7所示。圖4 ξ=0.5，ρ=0.1時SDGP算法的動態帶寬分配情況圖5 ξ=0.7，ρ=0.1時SDGP算法的動態帶寬分配情況圖6 ξ=0.5，ρ=0.2時SDGP算法的動態帶寬分配情況圖7 ξ=0.7，ρ=0.2時SDGP算法的動態帶寬分配情況 由上述仿真結果，對主導因子ξ和容忍因子ρ對SDGP算法的影響進行分析。比較圖4與圖5，或者圖6與圖7，當容忍因子ρ相同時，主導因子ξ=0.7時，優先級最高的Stream0在流量足夠大的時候，分配的帶寬70 Mb/s明顯高于主導因子為ξ=0.5時所分配到的50 Mb/s。即使Stream0流量變化為0時，主導因子ξ=0.7時也能夠分配到7 Mb/s閑置帶寬，而主導因子ξ=0.5時，只能分配到5 Mb/s閑置帶寬。其余Stream1到Stream6的仿真數據也都呈現此規律。由此表明，當容忍因子ρ相同時，數據流在相同流量的情況下，主導因子ξ越大，所分配的帶寬越大。

比較圖4與圖6，或者圖5與圖7，當主導因子ξ相同時，如果Stream0流量足夠大且不存在閑置帶寬的情況下，其帶寬分配均為50 Mb/s，容忍因子ρ的大小對其沒有影響；如果Stream0流量下降到可以分配到閑置帶寬的情況，Stream0分配得到的帶寬，相較容忍因子ρ=0.1時，在容忍因子ρ=0.2時更晚出現下降的現象。且當Stream0流量變化為0時，分配的帶寬在ρ=0.2時為10 Mb/s，而在ρ=0.1時為5 Mb/s。其余Stream1到Stream6的仿真數據也呈現出規律。由此表明，當主導因子ξ相同時，容忍因子ρ越大則容忍分配到閑置帶寬的比例越大。

綜合SDGP算法仿真結果，可以充分說明，SDGP算法根據需要共享鏈路帶寬的數據流(從Stream0到Stream6)的流量信息和優先級信息，能夠實時合理地動態調節帶寬分配，達到SDGP的設計初衷。

根據以上分析，結合主導因子ξ和容忍因子ρ的物理意義，可以得到下面結論：主導因子ξ越大，當優先級高的數據流流量足夠大時，總是能分配到更多的帶寬；容忍因子ρ越大，表示該條流能被容忍占有更多的閑置帶寬。用戶可以根據自身業務需要，方便地調節主導因子ξ和容忍因子ρ，使SDGP算法在實時動態帶寬的分配上，取得用戶預想的效果。另外，T越小，表示動態調整帶寬的時間粒度越細，共享帶寬得到更及時地分配和調整。但當數據流條數較多時，減小周期T也會增加系統向硬件下發帶寬配置的時間開銷。

5 結 語

綜上所述，SDGP算法能夠較好地實現，包括PWE3在內的具有流量工程基礎網絡的實時動態帶寬分配，具有良好的可操作性、合理性、靈活性與及時性。

參 考 文 獻

［1］沈清，馬林.十大電信熱點技術\\.計算機世界報，2005(7):90-100.

［2］Rosen E，Tappan D，Fedorkow G.RFC3032:Multiprotocol Label Switching Label Stack Encoding.http://www.ietf.org/rfc/rfc3032.txt，2001.

［3］Xiao X，McPherson D，Pate P.RFC3916:Requirements for Pseudo-Wire Emulation Edge-to-Edge (PWE3).http://www.ietf.org/rfc/rfc3916.txt，2004.

［4］Bryant S，Pate P.RFC3985:Pseudo Wire Emulation Edge-to-Edge (PWE3) Architecture.http://www.ietf.org/rfc/rfc3985.txt，2005:2-11.

［5］王欣，趙洋，張永軍，等.一種新的基于GPON的動態帶寬分配算法\\.光通信技術，2006(11):6-9.

［6］陳福都，李維民，張淳民，等.一種改進的GPON動態帶寬分配策略\\.光通信技術，2006，30(7):16-18.

［7］Eric W.Gray.MPLS:Implementing the Technology\\.北京:電子工業出版社，2003.

［8］Ivan Pepelnjak，Jim Guichard.MPLS and VPN Architectures.Cisco Press，2001.

［9］李曉東.MPLS技術與實現\\.北京:電子工業出版社，2002.

［10］Luca Martini，Nasser El-Aawar，Matthew Bocci，et al.Draft-ietf-pwe3-atm-encap:Encapsulation Methods for Transport of ATM Over MPLS Networks.

［11］郭海，陳福深.EPON中保證QoS的動態帶寬分配算法\\.現代電子技術，2005，28(14):13-15，19.

作者簡介 于 曦 男，1973年出生，碩士，講師。研究方向為軟件工程、數據庫原理。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文