摘 要：提出一種在網(wǎng)絡(luò)通信帶寬分配領(lǐng)域，結(jié)合自動(dòng)控制理論，利用基于優(yōu)先級(jí)的串行主導(dǎo)因子法對(duì)鏈路帶寬進(jìn)行動(dòng)態(tài)分配的方案。該算法通過引入主導(dǎo)因子和容忍因子，可以實(shí)現(xiàn)在具有流量工程基礎(chǔ)的網(wǎng)絡(luò)中對(duì)共享帶寬進(jìn)行實(shí)時(shí)動(dòng)態(tài)分配。

關(guān)鍵詞：基于優(yōu)先級(jí)的串行主導(dǎo)因子法；主導(dǎo)因子；容忍因子；帶寬分配

中圖分類號(hào)：TP393.04 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引 言

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

這種情況不僅局限于PWE3網(wǎng)絡(luò)，在其他具有流量工程基礎(chǔ)的網(wǎng)絡(luò)中，在配置鏈路共享帶寬時(shí)，都會(huì)遇到以下問題：

可操作性問題 配置方法復(fù)雜，專業(yè)性強(qiáng)，配置時(shí)需要網(wǎng)絡(luò)設(shè)備制造商的技術(shù)支持人員進(jìn)行指導(dǎo)，用戶自行配置易出錯(cuò)。

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

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

及時(shí)性問題 用戶完成帶寬分配后，通常很長(zhǎng)時(shí)間內(nèi)保持不變，更新率低。不能及時(shí)根據(jù)網(wǎng)絡(luò)流量變化調(diào)整，使有限的帶寬得到優(yōu)化配置。

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

本文提出的一種解決方案是：在網(wǎng)絡(luò)通信帶寬分配領(lǐng)域，結(jié)合自動(dòng)控制理論，利用基于優(yōu)先級(jí)的串行主導(dǎo)因子法(Serial Dominant Gene with Priority，SDGP)對(duì)鏈路帶寬進(jìn)行動(dòng)態(tài)分配的方案。通過引入主導(dǎo)因子ξ和容忍因子ρ，實(shí)現(xiàn)PWE3網(wǎng)絡(luò)中共享帶寬的實(shí)時(shí)動(dòng)態(tài)分配。同時(shí)，SDGP算法也能夠?yàn)槠渌哂辛髁抗こ袒A(chǔ)的網(wǎng)絡(luò)提供實(shí)時(shí)動(dòng)態(tài)帶寬分配方案。

2 SDGP算法原理

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

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

且不難推導(dǎo)Bwi，Bwrevi和Bwmax的關(guān)系為：Bwrevi=Bwmax-∑ij=0Bwj

(0≤i≤N-1，0≤j≤N-1)(3) 在進(jìn)行每條數(shù)據(jù)流的帶寬分配時(shí)，引入兩個(gè)重要調(diào)節(jié)控制因子：主導(dǎo)因子ξ和容忍因子ρ。ξi(0≤i≤N-1)表示第i條數(shù)據(jù)流的主導(dǎo)因子；ρi(0≤i≤N-1)表示第i條數(shù)據(jù)流的容忍因子。在通常需求下，網(wǎng)絡(luò)中所有數(shù)據(jù)流的主導(dǎo)因子都相同，且所有數(shù)據(jù)流的容忍因子也相同，即ξi=ξ，ρi=ρ，(0≤i≤N-1)。

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

Bwξi=Bwrev(i-1)×ξ (1≤i≤N-1)(5) 當(dāng)共享帶寬的數(shù)據(jù)流優(yōu)先級(jí)存在重疊現(xiàn)象時(shí)，需要利用εm(0≤m≤k)對(duì)以上兩個(gè)公式實(shí)施改進(jìn)，以支持優(yōu)先級(jí)重疊時(shí)Bwξi的計(jì)算。假設(shè)對(duì)優(yōu)先級(jí)為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)

當(dāng)Prii=Prii-1時(shí):

Bwξi=Bwtemp×ξ′

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

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

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

Bwi=Bwξi (當(dāng)Fluxi≥Bwtoli時(shí)，0≤i≤N-1)(11)

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

(當(dāng)Fluxi

當(dāng)在一個(gè)T周期內(nèi)，利用主導(dǎo)因子法完成所有數(shù)據(jù)流的帶寬分配后，延時(shí)到下一個(gè)周期到來(lái)，并再次利用主導(dǎo)因子法，根據(jù)下一個(gè)周期到來(lái)時(shí)，實(shí)時(shí)流量的狀況進(jìn)行帶寬分配，從而實(shí)現(xiàn)基于SDGP算法的實(shí)時(shí)動(dòng)態(tài)帶寬分配。

根據(jù)以上分析，不難看出主導(dǎo)因子ξ和容忍因子ρ之間關(guān)系表現(xiàn)為：主導(dǎo)因子ξ對(duì)共享帶寬進(jìn)行主要的、粗糙的分配和調(diào)節(jié)；容忍因子ρ則對(duì)ξ調(diào)整后的帶寬進(jìn)行細(xì)微的，靈活的二次調(diào)配。只有兩者相互配合，共同作用，才能根據(jù)系統(tǒng)流量及時(shí)合理地利用SDGP算法進(jìn)行系統(tǒng)的實(shí)時(shí)動(dòng)態(tài)帶寬分配。

3 SDGP算法實(shí)現(xiàn)

在上節(jié)SDGP算法原理研究的基礎(chǔ)上，本節(jié)將對(duì)SDGP算法的具體實(shí)現(xiàn)進(jìn)行討論?？紤]到工程實(shí)現(xiàn)的方便性、移植性和維護(hù)性，故采用算法組件化思想對(duì)SDGP算法系統(tǒng)劃分為3大組件單元：SDGP Kernel Unit，Stream Information Collection Unit和Assignment Execution Unit。具體架構(gòu)如圖2所示。

圖2 SDGP算法系統(tǒng)實(shí)現(xiàn)架構(gòu)當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)使用能SDGP算法模塊進(jìn)行實(shí)時(shí)動(dòng)態(tài)帶寬分配后，Stream Information Collection Unit將在每個(gè)T周期開始時(shí)，負(fù)責(zé)實(shí)時(shí)收集Network Node上需要進(jìn)行帶寬分配的數(shù)據(jù)流信息。這些收集到的信息可以直接實(shí)時(shí)傳送到SDGP Kernel Unit，也可以保存在Trace文件中再供給SDGP Kernel Unit使用。SDGP Kernel Unit的作用是對(duì)進(jìn)行收集到的需分配共享帶寬的數(shù)據(jù)流信息進(jìn)行分析，并根據(jù)SDGP算法進(jìn)行帶寬指派。經(jīng)過SDGP Kernel Unit完成的帶寬分配信息，將傳遞到Assignment Execution Unit，由其進(jìn)行具體的帶寬分配下發(fā)工作。

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

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

SDGP實(shí)時(shí)動(dòng)態(tài)帶寬分配算法仿真方案如下：

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

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

當(dāng)ξ=0.5，ρ=0.1時(shí)，仿真結(jié)果如圖4所示。

當(dāng)ξ=0.7，ρ=0.1時(shí)，仿真結(jié)果如圖5所示。

當(dāng)ξ=0.5，ρ=0.2時(shí)，仿真結(jié)果如圖6所示。

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

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

綜合SDGP算法仿真結(jié)果，可以充分說明，SDGP算法根據(jù)需要共享鏈路帶寬的數(shù)據(jù)流(從Stream0到Stream6)的流量信息和優(yōu)先級(jí)信息，能夠?qū)崟r(shí)合理地動(dòng)態(tài)調(diào)節(jié)帶寬分配，達(dá)到SDGP的設(shè)計(jì)初衷。

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

5 結(jié) 語(yǔ)

綜上所述，SDGP算法能夠較好地實(shí)現(xiàn)，包括PWE3在內(nèi)的具有流量工程基礎(chǔ)網(wǎng)絡(luò)的實(shí)時(shí)動(dòng)態(tài)帶寬分配，具有良好的可操作性、合理性、靈活性與及時(shí)性。

參 考 文 獻(xiàn)

［1］沈清，馬林.十大電信熱點(diǎn)技術(shù)\\.計(jì)算機(jī)世界報(bào)，2005(7):90-100.

［2］Rosen E，Tappan D，F(xiàn)edorkow 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的動(dòng)態(tài)帶寬分配算法\\.光通信技術(shù)，2006(11):6-9.

［6］陳福都，李維民，張淳民，等.一種改進(jìn)的GPON動(dòng)態(tài)帶寬分配策略\\.光通信技術(shù)，2006，30(7):16-18.

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

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

［9］李曉東.MPLS技術(shù)與實(shí)現(xiàn)\\.北京:電子工業(yè)出版社，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的動(dòng)態(tài)帶寬分配算法\\.現(xiàn)代電子技術(shù)，2005，28(14):13-15，19.

作者簡(jiǎn)介 于 曦 男，1973年出生，碩士，講師。研究方向?yàn)檐浖こ?、?shù)據(jù)庫(kù)原理。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文