異質化帶寬分配下的復雜網絡數據流負載問題研究*

于灝 周玉成 井元偉 徐佳鶴 張星梅 馬妍3)

1)(東北大學信息科學與工程學院,沈陽 110004)

2)(中國林業科學研究院木材工業研究所,北京 100091)

3)(青島理工大學經濟與貿易學院,青島 266520)

(2012年7月17日收到;2012年12月23日收到修改稿)

1 引言

隨著小世界[1]和無標度[2]等重要的網絡特性在20世紀末被陸續發現,越來越多的科研工作者開始通過復雜網絡的視角來審視和研究自然和人類社會當中的復雜系統,投身于復雜網絡的研究中[3-8].復雜網絡的數據流研究是其中的重點研究方向之一.伴隨著網絡數據流量的不斷增加,發生傳輸擁塞是不可避免的.所以,盡可能地提升擁塞發生臨界的網絡負載能力便成了要解決的核心問題.許多科研工作者此前做出了大量的研究,取得了豐碩的成果.文獻[9]提供了一個狀態參量,為分析網絡自由狀態向擁塞狀態轉變提供了完美的理論描述方式;文獻[10—16]提出了多個能夠提高網絡負載的路由策略;文獻[17]發現了網絡數據流負載與網絡介數的關系,發現網絡負載與網絡節點的最大介數成反比;文獻[18,19]提出了通過刪除網絡上的一些邊,降低網絡節點最大介數,能提高網絡負載能力的‘刪邊擴容’方法,文獻[20,21]分析了勻質化的帶寬分配下的網絡負載能力變化.文獻[22]提出了一種帶寬分配方案,針對其文中的路由策略,對相對重要的連接邊有所偏重地分配帶寬,達到了提升網絡性能的目的.

通常對網絡數據流負載提升問題的研究主要從兩方面入手：一是尋求更適合數據傳輸的網絡拓撲結構,二是找尋更高效的路由策略.先前的許多研究中很少把連接邊帶寬約束加以考慮,在節點處理能力強的網絡中,連接邊的傳輸容量限制往往成為導致擁塞發生的重要原因.科學研究和生活經驗證明,網絡中連接邊的帶寬約束往往作為制約網絡數據流通的一個瓶頸,既然多數的現實問題不能回避和忽略帶寬約束,那么把合理有效的帶寬分配作為充分利用和發揮網絡資源優勢,提高網絡數據流通效率的重要武器將更具有現實意義.

因此,本文在流量模型中加入了連接帶寬約束機制,從制約數據傳輸的網絡關鍵拓撲特性出發,提出了一種異質化網絡帶寬分配方案;并結合路由選擇策略,運用連接帶寬的分配來調節網絡中數據流的流向,從而實現緩解網絡擁塞發生,提升網絡的負載能力;同時,定性分析了流量變化的過程及其原因.本文第二部分介紹了網絡模型和數據流模型;第三部分介紹本文提出的帶寬分配方案;第四部分模擬并分析應用帶寬方案的網絡數據流,第五部分是結論.

2 網絡模型與數據流量模型

2.1 網絡拓撲模型

2.1.1 WS小世界網絡

作為復雜網絡研究的一個重大發現——小世界現象,反映了許多現實網絡中所具有的大的聚類系數和小的平均距離的特性.為了構建能反映出這種特性的網絡,Watts和Strogatz[1]于1998年提出了小世界網絡模型,稱為WS小世界模型.該模型可以看作是從規則網絡向隨機網絡的過渡過程,其構造算法如下：給定含有N個點的最近鄰耦合網絡,其中每個節點都與它左右相鄰的各K/2個節點相連,以概率p隨機地重新連接網絡中的每條邊.其中規定,任意兩個不同的節點之間至多只能連一條邊,并且每一個節點都不能有邊與自身相連.

在WS模型中,p=0對應于完全規則網絡,p=1則對應于完全隨機網絡,通過調節p值就可以控制從完全規則網絡到完全隨機網絡的過渡[6].

2.1.2 BA無標度網絡

近年在復雜網絡研究上的另一重大發現就是許多復雜網絡,包括Internet,WWW以及新陳代謝網絡等的連接度分布函數具有冪律形式.由于這類網絡節點的連接度沒有明顯的特征長度,故稱為無標度網絡.為了解釋冪律分布的產生機理,Baraba′si和Albert[2]提出了一個無標度網絡模型,被稱為BA無標度網絡模型.BA模型包含著兩個主要特性：1)增長(growth)特性,即網絡的規模是不斷擴大的;2)優先連接(preferential attachment)特性,即新的節點更傾向于與那些具有較高連接度的節點相連接,這種現象也稱為“富者更富(rich get richer)”或“馬太效應(matthew effect)”特性.BA網絡模型構建如下：

1)初始網絡,具有m0個節點;

2)網絡生長過程,每一步加入一個節點v和m條邊(m≤m0);

2.2 數據流量模型

本文采用加入連接邊傳輸容量限制(帶寬約束)的網絡數據流量模型,具體描述如下.

把N個節點的網絡中的每個節點看作主機和路由器的結合體,同時具有產生、轉發、接收數據包的能力;每個節點i的數據包處理能力為Ci,即每單位時間步節點i最多可以處理Ci個數據包.為簡單起見,定義每個節點的數據包處理能力Ci都相同,且為常數.節點擁有無限長的緩沖隊列,新加入的數據包放置在隊列的尾部,并按照“先入先出”(FIFO)原則處理;新產生的數據包選擇源節點和目標節點是隨機的;單位時間步,整個網絡中新數據包的產生率為R;網絡擁塞僅發生在節點端.

此外,每條連接邊傳遞能力定義為帶寬B,即單位時間步每條邊上單向最多可以有B個數據包在傳遞,且一條邊上同時有相向傳遞數據包時互不影響.如果帶寬使用飽和,那么數據包仍被儲存在發包節點的緩沖隊列當中.抵達目標節點的數據包將立刻從網絡中去除.

網絡上的數據包流量可以看作兩部分,一部分由新流入網絡中的數據包構成,另一部分則是到達目的地從網絡中消失的流出數據包構成.當兩者流量平衡時數據流處于自由流狀態,當前者大于后者時數據包開始在網絡中累積,達到一定的累積程度時網絡擁塞開始發生.為了清晰地描述網絡中的自由流狀態向擁塞狀態的相變過程,這里引入一個相變參量η[9]：

其中η(R)是R的函數,〈ΔW〉是相鄰時刻網絡中總數據包的平均增加量.當R＜Rc時,網絡中流入和流出的數據包能夠平衡,〈ΔW〉≈0,此時η≈0,網絡處于自由流狀態;當R＞Rc時,〈ΔW〉隨時間的增長逐漸增加,數據包開始在網絡中累積,此時η＞0并持續上升,數據流進入擁塞狀態,并且擁塞隨η值越大,越顯明顯.因此,擁塞轉變發生在R=Rc時,Rc是使網絡的自由流狀態向擁塞狀態相變的臨界值,標志此時網絡達到了最大的負載能力,也因此把R作為網絡負載的標志,本文把Rc作為網絡最大負載能力.

路由選擇策略：采用一種全局信息和局部信息相結合的具有擁塞感知能力的路由算法.假設數據包從源節點s傳遞到目標節點t.首先,對節點鄰居節點執行局域搜索.如果發現了目標節點,則數據包被直接送達目的地,否則,就按照如下策略尋找下一投遞節點.

首先,計算節點s的所有鄰居節點的權值ωi.對于鄰居節點i來說,權值ωi通過如下表達式進行計算：

其中,Li→t是節點i到目標節點t的最短路徑長度,Qi是節點i當前所存儲待處理的數據包個數,相當于路由器的緩沖隊列長度,α是一個可以調節的參數,其范圍位于0和1之間.當節點i發生擁塞時,Qi的值會非常大.

然后,選取權值最小的節點作為下一個路由節點.如果權值最小的節點有多個,那么隨機選取其中一個.

依照上述過程直到找到目標節點t.

當參數α=1時,或節點沒有累積數據包時,該算法則退化為最短路徑路由算法(SPR),當α向0靠近說明路由線路在遠離最短路徑.

3 帶寬分配方案

介數(betweenness centrality or betweenness)代表了網絡經過節點(邊)的最短路徑的數目,如果節點(邊)介數較高就說明通過該節點(邊)的最短路徑較多,所以經過該節點(邊)到達其他節點(邊)的平均路徑長度也就較短.通常一對節點之間進行傳遞,經過最短路徑無疑會使傳遞的成本最低.但在多對節點同時發生傳遞時,就會使經過最短路徑數目多的高介數節點負擔加重,產生擁堵的概率加大.

網絡節點介數對負載的影響起到至關重要的作用[17],存在如下關系：

即網絡最大負載能力Rc與網絡最大節點介數g?成反比.

理論上改變網絡結構,降低網絡節點的最大介數能夠提升網絡的負載能力.為了不破壞網絡現有結構,本文提出一個帶寬分配方案來降低高介數節點負載,提升網絡整體負載能力,可以看作改變網絡結構提升負載的等效方法.

3.1 異質化帶寬分配方案

網絡中的邊被劃分成“受控邊”和“非受控邊”兩部分,受控邊的帶寬為b1,非受控邊的帶寬為b2.這里,在考慮連接邊帶寬約束的網絡上,把整個網絡帶寬資源作為一個固定的總量來看待.

為了確定“受控邊”,首先計算每個節點的介數,并為整個網絡勻質化分配帶寬——每條邊分配帶寬b0,網絡上的帶寬總量為B=b0M,M是網絡總的邊數;然后,給每條邊賦權σij=gi·gj;其中gi和gj分別是一條邊兩端節點的介數,按權值從大到小的順序排列,將σij最大的那條邊刪除,在刪除邊的過程中,如權值最大的邊有多條,則隨機選取一條;同時,標記刪去的邊,作為“受控邊”放入一個“受控邊”表中;重復上述過程直到達到設定的“受控邊”比例上限 fce或網絡連通性遭到破壞停止,“受控邊”表中標記的刪除邊按刪除的先后順序排列.這樣就確定了網絡中的“受控邊”.

為“受控邊”表中的邊分配帶寬b1,且b1?b0,即：單位時間步只允許相對較少數據包通過該邊.這樣,保證了網絡的連通性,同時大大降低了這些“受控邊”的數據包傳遞能力.并為非受控邊分配帶寬當 fce=0時,網絡帶寬為勻質化分配b1=b2=b0.

4 仿真與分析

分別選取BA無標度網絡和WS小世界網絡作為網絡拓撲平臺.網絡規模都為1000個節點,且為無向網絡.BA網絡模型初始節點互不相連m0=m=3,〈K〉=6;WS網絡模型隨機重連概率p=0.3,〈K〉=4.節點節點數據包處理能力都為100,每條連接邊的初始帶寬為b0=10,受控邊帶寬b1=1.在流量模型中,運行5000時間步后認為網絡流量達到穩定,取后1000步的平均值來計算.仿真結果均取20次獨立實驗的平均值.

圖1反映了在受控邊比例變化時BA網絡模型中網絡負載能力的變化.可以看出受控邊比例 fce適度增加時,網絡的負載能力有不同程度的增加,當受控邊比例 fce加大到一定程度時,網絡中的負載能力開始下降,說明了受控邊比例在網絡中存在最優值.α值為達到Rc時的值,可以看出,通過異質化地分配帶寬,使得數據流向得以改變(α值改變反映了網絡數據流向的變化,而α具體值屬于路由算法的性質,不是本文重點,故在后面不再討論).在圖1仿真中BA網絡的最優受控邊比例 fce出現在0.45附近.

圖1 BA網絡N=1000,m0=m=3,在不同受控邊比例時η與R變化對比

在我們的流量模型中,Soiut不僅受到節點i處理數據包能力Ci的限制,還要受到節點i連接邊帶寬總量Bi的影響,即Siout=min(Ci,Bi).因此,盡量做到Ci和Bi接近是既不浪費資源又能提升負載性能的理想狀態.在我們的仿真中,BA網絡的節點度最大值為102,fce=0時節點i連接邊帶寬Bi=b0Ki.此時,最大度節點總的連接邊帶寬Bi達到1020,而節點的處理能力是100,Ci?Bi,因此在高度數節點存在著帶寬資源的浪費.BA無標度網絡中存在少數中心節點,擁有非常高的度,而大部分的一般節點度都較小,小于網絡節點度的平均值.在本文的仿真選取的BA網絡中,一般節點的連接邊帶寬要小于60,Ci＞Bi,這些節點的Siout受限于帶寬,提升這些節點的連接邊帶寬格外重要.

從圖2中可以看出,BA無標度網絡中,度數大的節點往往也是介數高的節點,節點的度與介數之間具有正相關性,且仿真中的BA網絡Pearson Correlation Coeffi cients達到了0.95.因此,根據我們的帶寬分配方案,在BA網絡中度數高的節點周圍會出現大量受控邊.

圖2 BA網絡中,各個節點的度和介數,插圖是序號1—50的節點相應的度和介數

圖3 顯示了隨著網絡中受控邊比例的增加,中心節點的連接邊帶寬資源被減少,并且減少的這部分帶寬資源被均勻地分配給了帶寬資源不足的一般節點,使得整個網絡各個節點的連接邊帶寬資源分配更加趨于均衡.

圖3 BA網絡中,在受控邊比例 f ce=0,0.1,0.2,0.3,0.4時,節點連接邊帶寬Bi的變化

這里,我們引入統計中的標準差概念來反映均衡程度和異質程度.標準差值越小代表越均衡,反之則表明異質性強.

圖4是在BA網絡中受控邊增加時,節點連接邊帶寬的標準差變化.隨著受控邊比例在BA網路中增加,帶寬標準差值是持續下降的,網絡中節點的連接邊帶寬在趨于均衡.

圖4 BA網絡(m0=m=3,〈K〉=6)節點連接邊帶寬Bi標準差在不同受控邊比例下的變化

圖5 WS網絡(p=0.3,〈K〉=4)節點連接度分布

圖5 和圖6分別是WS網絡節點度分布和介數分布,可以看出WS網絡的度分布較為均勻,而介數分布異質性較大.在對WS網絡平臺仿真中,圖7反映了WS網絡節點連接邊帶寬Bi的標準差和網絡最大負載能力Rc隨受控邊比例增加的變化.發現 fce為0.1(±0.01),帶寬標準差出現最小值時,網絡帶寬分布最優,同時負載能力最大.再加入受控邊的過程中,計算節點連接邊帶寬Bi標準差與網絡負載能力Rc的Pearson Correlation Coeffi cients為-0.87,可以看出,在WS小世界網絡中節點的連接邊帶寬分布得越均衡,網絡整體的負載能力越強.

由于WS小世界網絡中,雖然介數分布異質,但度分布均勻,在為負載重的節點周圍加入相對較少的受控邊就能使得網絡各個節點的負載和帶寬相對均衡,使得負載和帶寬具有較強的相關性;而BA網絡中,無論是節點介數還是連接度,中心節點與一般節點的差異性很大.所以,達到網絡最大負載能力時,各個節點間的節點連接邊帶寬Bi仍然存在較大異質性.

圖6 WS網絡(p=0.3,〈K〉=4)節點介數分布

圖7 WS網絡(p=0.3,〈K〉=4)節點連接邊帶寬Bi標準差和網絡最大負載能力R c在不同受控邊比例下的變化

圖 8 WS 網絡 (N=1000,p=0.1,0.2,0.3,0.4,0.5,〈K〉=4)節點度的標準差變化

網絡節點度的標準差可以衡量網絡拓撲結構的異質程度,標準差值越大網絡拓撲異質性越強.從圖8可以看出,WS小世界網絡拓撲異質化程度隨著p值增大而加強.從圖9中可見,在WS小世界網絡中,最優節點連接邊帶寬分布和相對應的受控邊比例都隨著網絡異質性加強而增加.

圖 9 WS 網絡 (N=1000,p=0.1,0.2,0.3,0.4,〈K〉=4)節點連接邊帶寬Bi標準差最小值和網絡最大負載能力R c在不同受控邊比例下的變化

5 結論

存在節點度或介數異質化分布的網絡中,在數據包傳遞過程中存在一定量的冗余路徑.當一些節點數據包負載較重時,存在可以繞開這些節點的其他路徑.我們發現,節點的處理能力相同且帶寬分配勻質時,負載重的中心節點受限于自身的數據處理能力,其周圍連接邊占據著大量過剩帶寬資源;而具有同樣數據處理能力的一般節點通常都是帶寬較少,在需要一般節點為中心節點分擔負載的時候往往又受限于連接邊的帶寬.根據這一發現,提出了帶寬分配方案,通過合理地釋放一些節點過剩的帶寬資源,把部分中心節點周圍的連接邊變成“受控邊”,減少“受控邊”的帶寬,在不破壞網絡拓撲結構的同時釋放出“受控邊”的帶寬資源分給其他一般節點周圍的連接邊,以此來提高帶寬資源的利用效率,提升網絡的負載性能.在相同類型和規模的WS網絡中,異質化程度越高,相應網絡中冗余邊存在的比例就越高,也因此需要加入的受控邊比例也越高.我們也對相同規模不同網絡做了仿真,發現異質化程度高的網絡,達到最優負載時需要加入的受控邊比例相應也高.

引入異質化帶寬分配方案使得BA網絡負載性能提升主要來自于兩部分貢獻,其一是異質化帶寬分配方案有效地限制了涌向中心節點數據流量,有效緩解了中心節點擁塞,將部分負載轉向一般節點,相對平衡了各個節點的負載;其二是將中心節點的過剩的連接邊帶寬分配給連接邊帶寬不足的一般節點,使得大多數節點連接邊的傳遞能力增強,同時更好地消化轉移過來的負載.

對于WS小世界網絡,由于節點度分布均勻,帶寬約束對所有節點的數據流量都起到了制約作用.加入少量受控邊就會使得各個節點的連接邊帶寬達到最佳狀態,同時實現網絡負載能力的最優.

本文中,帶寬分配方案是與感知節點擁塞的路由算法配合應用的.在特殊情況下,受控邊的帶寬為0時,本套方案仍然有效.值得注意的是,如果使用最短路徑路由時,加入受控邊帶寬為0則需要重新考慮網絡拓撲結構,按照刪除受控邊后新的網絡結構重新計算最短路徑,否則會造成數據包在原來最短路徑上的節點處大量累積,大大降低網絡負載能力.

總之,本文提出的異質化帶寬分配方案,優化了網絡上帶寬資源的分配,有效調節網絡流量走向,使得網絡總體負載能力較勻質分配帶寬時有較大提升,為提高網絡負載性能研究提供了一個新思路.

感謝中國科學研究院計算所(北京)的張國清副研究員對于刪邊擴容效應以及算法實現上的熱情討論和幫助.

[1]Watts D,Strogatz S 1998 Nature 393 440

[2]Barab′asi A L,Albert R 1999 Science 286 509

[3]Ohira T,Sawatari R 1998 Phys.Rev.E 58 193

[4]Faloutsos M,Faloutsos P,Faloutsos C 1999 Comp.Commun.Rev.29 251

[5]Albert R,Barab′asi A L 2002 Rev.Mod.Phys.74 47

[6]Newman M EJ2003 SIAM Rev.45 167

[7]Wang X F,Chen G R 2003 IEEETrans.Circuits Syst.3 6

[8]Hao B B,Yu H,Jing Y W,Zhang SY 2009 Physica A 388 1939

[9]Arenas A,Diaz-Guilera A,Guimera R 2001 Phys.Rev.Lett.86 3196

[10]Wang W X,Wang B H,Yin CY,Xie Y B,Zhou T 2006 Phys.Rev.E 73 026111

[11]Yan G,Zhou T,Hu B,Fu ZQ 2006 Phys.Rev.E 73 046108

[12]Chen Z Y,Wang X F 2006 Physica A 364 595

[13]Wang D,Jing Y W,Zhang SY 2008 Physica A 387 3001

[14]Pu CL,Pei W J2010 Acta Phys.Sin.59 3841(in Chinese)[濮存來,裴文江2010物理學報59 3841]

[15]Danila B,Yu Y,Marsh JA,Bassler K E 2006 Phys.Rev.E 74 046106

[16]Wang D,Yu H,Jing Y W,Jiang N,Zhang SY 2009 Acta Phys.Sin.58 6802(in Chinese)[王丹,于灝,井元偉,姜囡,張嗣贏2009物理學報58 6802]

[17]Guimer`a R,D′?az-Guilera A,Vega-Redondo F,Cabrales A,Arenas A 2002 Phys.Rev.Lett.89 248701

[18]Zhang GQ,Wang D,Li GJ2007 Phys.Rev.E 76 017101

[19]Zhang G Q,Cheng S Q 2012 Sci.Sin.Infom.42 151(in Chinese)[張國清,程蘇琦2012中國科學(信息科學)42 151]

[20]Hu M B,Wang W X,Jiang R,Wu Q S,Wu Y H 2007 Euro.Phys.Lett.79 14003

[21]Yu H,Jing Y W,Zhou Y C,Ma Y 2010 Journal of Northeastern University(Nat.Sci.)31 1226(in Chinese)[于灝,井元偉,周玉成,馬妍2010東北大學學報(自然科學版)31 1226]

[22]Ling X,Hu M B,Du WB,Jiang R,Wu Y H,Wu QS2010 Phys.Lett.A 374 4825