隨機帶寬分配對復雜網(wǎng)絡傳輸性能的影響分析

于 灝，馬 妍，王新華，井元偉，周玉成，王 丹

（1.山東科技大學經(jīng)濟管理學院，山東 青島266590；2.青島理工大學經(jīng)濟與貿(mào)易學院，山東 青島266520；3.東北大學a.工商管理學院；b.信息科學與工程學院，遼寧 沈陽110819；4.中國林業(yè)科學院木材工業(yè)研究所，北京100091；5.沈陽大學裝備制造綜合自動化重點實驗室，遼寧 沈陽110044）

0 引言

研究任何現(xiàn)實系統(tǒng)時都不能忽略的一個重要問題，就是資源的有限性，在復雜網(wǎng)絡傳輸問題研究上也不例外?，F(xiàn)實網(wǎng)絡傳輸系統(tǒng)發(fā)生擁堵的主要原因來自于網(wǎng)絡資源方面的限制，通常在網(wǎng)絡傳輸中的資源限制主要包括兩個方面：一是網(wǎng)絡節(jié)點資源的有限性，例如：通信網(wǎng)絡路由器的轉(zhuǎn)發(fā)能力和緩沖區(qū)的隊列長度限制，交通網(wǎng)絡中的交通樞紐站點的轉(zhuǎn)運能力和容納能力等；二是網(wǎng)絡中連接邊的容量（帶寬）資源的有限性，它主要是指網(wǎng)絡中連接邊在單位時間運送數(shù)據(jù)包的能力，例如：通信網(wǎng)絡的傳輸帶寬限制，交通道路上承載車流量的能力等等。除了提高網(wǎng)絡資源供給之外，制定有效的資源分配策略是提高網(wǎng)絡傳輸性能的必要手段。在考慮連接邊帶寬資源限制下的復雜網(wǎng)絡傳輸問題的研究中，文獻［1］分析了平均分配帶寬時，帶寬限制對網(wǎng)絡傳輸性能的影響。文獻［2］提出了一種“反直覺”的帶寬分配方案，通過引入“受控邊”優(yōu)化了帶寬資源的利用效率，使得網(wǎng)絡負載性能較勻質(zhì)化分配帶寬有了很大提升，文獻［3］設計了帶寬分配方案，有效地改善了網(wǎng)絡負載性能。本文通過設計異質(zhì)化隨機帶寬分配方案來分析帶寬分配對網(wǎng)絡傳輸性能的影響。

1 傳輸流量模型

在本文傳輸流量模型中，網(wǎng)絡中的所有節(jié)點被看作是主機和路由器的結(jié)合體，具有產(chǎn)生、儲存、傳遞數(shù)據(jù)包的功能。每個節(jié)點的處理數(shù)據(jù)包能力為Ci，規(guī)定每個節(jié)點的處理能力Ci相同且為常數(shù)。每個節(jié)點容量為無限大，且每個節(jié)點緩沖隊列中等待發(fā)送的數(shù)據(jù)包都是按照先入先出的規(guī)則按順序進行處理。連接邊只具有傳遞功能。如發(fā)生網(wǎng)絡擁塞僅出現(xiàn)在節(jié)點處。R為數(shù)據(jù)包產(chǎn)生率，即：單位時間內(nèi)新加入R個數(shù)據(jù)包。數(shù)據(jù)包的出發(fā)節(jié)點和目的節(jié)點隨機選取，到達目的節(jié)點后的數(shù)據(jù)包自動從網(wǎng)絡上移除。數(shù)據(jù)包的傳遞依照路由策略進行。其中路由策略以文獻［4－6］中的路由策略方案為基礎，并加以改進得到——G－L路由策略。

G－L路由策略中的節(jié)點權(quán)值為

其中，Li→t為節(jié)點i到目標節(jié)點t的最短路徑長度，Qi為節(jié)點i當前所存儲待處理的數(shù)據(jù)包個數(shù)，相當于路由器的緩沖隊列長度，α為一個可以調(diào)節(jié)的參數(shù)，其范圍位于0和1之間。Bi為節(jié)點i的連接邊帶寬，即節(jié)點i所有相鄰連接邊帶寬的總和。

路由選擇策略中，選取相鄰連接節(jié)點權(quán)值最小的節(jié)點作為下一路由節(jié)點，進行傳遞。如遇到最小權(quán)值節(jié)點不唯一的情況，則隨機選擇一個作為下一路由節(jié)點。

為了更好描述網(wǎng)絡傳輸中流量狀態(tài)變化過程，引入狀態(tài)相變參數(shù)η來進行描述［7－9］：

其中，〈ΔW（t）〉為相鄰時刻網(wǎng)絡中總的數(shù)據(jù)包變化量。Rc作為網(wǎng)絡流量由自由流狀態(tài)向擁塞狀態(tài)轉(zhuǎn)變過程中數(shù)據(jù)包產(chǎn)生率的臨界值。當R＜Rc時，網(wǎng)絡系統(tǒng)中產(chǎn)生的數(shù)據(jù)包和到達目標節(jié)點的數(shù)據(jù)包數(shù)量維持均衡，此時η值近似為零，網(wǎng)絡傳輸系統(tǒng)處于穩(wěn)定的自由流狀態(tài)；當R＞Rc時，網(wǎng)絡傳輸系統(tǒng)不能及時地、完全地消化新產(chǎn)生的數(shù)據(jù)包，數(shù)據(jù)包在網(wǎng)絡中開始累積，此時系統(tǒng)進入擁塞狀態(tài)，且η值伴隨著R的增加而增大，同時η值越大，表示擁塞程度越高。最終η＝1時，網(wǎng)絡傳輸系統(tǒng)處于完全堵塞狀態(tài)，此時代表網(wǎng)絡中新產(chǎn)生的數(shù)據(jù)包一個都不能傳出，全部滯留在網(wǎng)絡中。本文中把傳輸效率最高時的狀態(tài)相變臨界值Rc作為網(wǎng)絡最大負載能力的標志進行研究。

2 隨機帶寬分配方案設計

為了通過帶寬隨機分配對網(wǎng)絡傳輸?shù)挠绊?，探索合理的分配方案制定依?jù)，本文設計了兩種隨機帶寬分配方案：完全隨機帶寬分配方案和分類隨機帶寬分配方案來進行研究。

完全隨機帶寬分配方案：為每條連接邊隨機分配帶寬集合B∈［a －b］，1≤a＜b中的帶寬值。為了使得每次隨機分配帶寬的網(wǎng)絡傳輸之間能夠進行性能比較，這里規(guī)定網(wǎng)絡的連接邊帶寬資源總量固定為常數(shù)BT。

分類隨機帶寬分配方案：為網(wǎng)絡中的每條邊分配權(quán)值σij＝gi＊gj，其中g(shù)i和gj分別為連接邊兩端節(jié)點i和節(jié)點j的介數(shù)，網(wǎng)絡邊的平均權(quán)值為。網(wǎng)絡的邊被分成兩組E1和E2。E1中，所有連接邊權(quán)值小于或等于平均邊權(quán)值；E2中，所有連接邊權(quán)值大于平均邊權(quán)值。網(wǎng)絡連接邊的平均帶寬，選取兩個帶寬集合B1∈［a～］，1≤a＜和B2∈分別為兩組邊隨機分配帶寬集B1，B2中的帶寬值。規(guī)定網(wǎng)絡的連接邊帶寬資源總量固定為常數(shù)BT。

3 隨機帶寬分配網(wǎng)絡流量仿真與分析

選取HK－BA無標度網(wǎng)絡［10］作為網(wǎng)絡拓撲平臺。網(wǎng)絡規(guī)模為1 000個節(jié)點。網(wǎng)絡模型初始節(jié)點互不相連m0＝m＝3，調(diào)節(jié)概率為0.5。

應用完全隨機帶寬分配方案，帶寬集B∈ ［1 ～ 10］。使用最短路徑路由策略（SPR）（α＝1）和G－L路由策略

既然完全隨機帶寬分配不是實用有效的帶寬分配方式，為了進一步探求帶寬的“合理”或接近“合理”的分配方案，下面討論研究本文提出的另一種帶寬分配方式——分類隨機帶寬分配方案。仿真中，網(wǎng)絡平均帶寬帶寬集B1∈［1～5］，B2∈（5～10］。網(wǎng)絡的連接邊帶寬資源總量固定。

為了清晰比較，選取4種帶寬分配與路由策略的組合進行網(wǎng)絡傳輸性能的對比。4種組合及對比關(guān)系如圖2所示，方框中標明了帶寬分配與路由策略的組合方式，雙向箭頭代表組合間進行對比。每種組合分別進行20次試驗，其結(jié)果的平均值呈現(xiàn)在圖3～圖6。在各組合采用的路由策略下，平均分配帶寬（每條邊的帶寬都相等，為5）的網(wǎng)絡最大負載作為對比中間值。（α＝0.7）選取了20組流量試驗得到的各自最大負載（每組20次試驗的平均結(jié)果）（見圖1），所有試驗中網(wǎng)絡節(jié)點處理能力相同Ci＝50。圖1中縱坐標是代表網(wǎng)絡最大負載能力的Rc值，橫坐標是試驗組序號，圓形標示是最短路徑路由策略下網(wǎng)絡帶寬完全隨機分配時的網(wǎng)絡最大負載值，方形標示是G－L路由策略下網(wǎng)絡帶寬完全隨機分配時的網(wǎng)絡最大負載值。通過圖1發(fā)現(xiàn)：1）在應用同一路由策略網(wǎng)絡時，隨機分配連接邊帶寬產(chǎn)生了不同的網(wǎng)絡最大負載能力，且無法判斷其中規(guī)律；2）在相同帶寬分配的網(wǎng)絡中，應用G－L路由策略所產(chǎn)生的網(wǎng)絡最大負載都要高于應用最短路由策略時的網(wǎng)絡最大負載；3）相對于最短路徑路由策略，G－L路由策略在不同帶寬分配時，對網(wǎng)絡最大負載影響方面表現(xiàn)出較強的魯棒性。

從以上對完全隨機分配帶寬方案的研究，可以看出，完全隨機地分配網(wǎng)絡連接邊帶寬對網(wǎng)絡負載的影響帶有不確定性，因此，這種方案不是一種實用有效的帶寬分配方案，但同時也發(fā)現(xiàn)不同帶寬分配時，不同路由策略對網(wǎng)絡性能的影響情況是不盡相同的。

文獻［4－6］對路由策略的性能的分析比較可以說明圖1發(fā)現(xiàn)中的第2點。下面來分析圖1中的第3點發(fā)現(xiàn)。網(wǎng)絡連接邊的介數(shù)反映了某條邊在網(wǎng)絡中的重要性，邊介數(shù)高代表網(wǎng)絡中通過這些邊的最短路徑數(shù)量較多。在應用最短路徑路由時，數(shù)據(jù)包傳輸路徑嚴格遵循著由拓撲結(jié)構(gòu)決定的最短拓撲距離線路，此時，通過高介數(shù)邊的數(shù)據(jù)包相應較多，并且整個網(wǎng)絡的數(shù)據(jù)包流向也是向著最高介數(shù)邊方向聚集，如果隨機分配帶寬時，分配到這些重要的介數(shù)高的邊的帶寬值很小，就會造成數(shù)據(jù)包在這些邊附近的節(jié)點大量累積，造成傳輸流量放緩，并很快擁堵，降低網(wǎng)絡傳輸性能。G－L路由策略本身能夠根據(jù)網(wǎng)絡局部節(jié)點數(shù)據(jù)包的擁塞程度的動態(tài)信息而選擇調(diào)整流向，離開最短路徑傳輸線路，這使得部分數(shù)據(jù)流避免涌向數(shù)據(jù)包最聚集的地方，能夠一定程度上緩解擁塞的發(fā)生，因此，使得G－L路由策略在遭遇上面所述高介數(shù)邊被分配小帶寬時，網(wǎng)絡性能表現(xiàn)不會像最短路徑策略時那么糟糕。而當網(wǎng)絡上連接邊帶寬的分配較為合理時，最短路徑策略路由下的網(wǎng)絡負載能力得到提升，此時，采用GL路由策略的路由線路也會靠近最短路徑線路。因此，G－L路由策略可以根據(jù)網(wǎng)絡不同帶寬分配情況，通過調(diào)節(jié)遠離或靠近最短路徑線路，來保持隨機性分配對網(wǎng)絡最大負載影響方面的魯棒性。

圖1 完全隨機異質(zhì)化帶寬分配時，SPR與G－L路由策略下網(wǎng)絡最大負載Fig.1 Maximum load with SPR and G－L routing strategy with complete random heterogeneous bandwidth allocation

圖2 帶寬分配與路由策略組合對比關(guān)系Fig.2 Correlation of bandwidth allocations and routing strategies

圖3 采用組合1時，網(wǎng)絡流量狀態(tài)Fig.3 The network traffic with group 1

圖4 采用組合2時，網(wǎng)絡流量狀態(tài)Fig.4 The network traffic with group 2

圖5 采用組合3時，網(wǎng)絡流量狀態(tài)Fig.5 The network traffic with group 3

圖6 采用組合4時，網(wǎng)絡流量狀態(tài)Fig.6 The network traffic with group 4

由圖3與圖4可以看出，采用組合1方式分配帶寬時網(wǎng)絡的最大負載能力Rc要高于組合2帶寬分配方式下的。對比圖5與圖6可以看出，采用組合3方式分配帶寬時網(wǎng)絡的最大負載能力Rc要高于組合4帶寬分配方式下的。并且，組合1、組合2仿真得到的網(wǎng)絡最大負載分別優(yōu)于組合3、組合4的。

節(jié)點介數(shù)可以表示理論上通過某一節(jié)點的最短路徑的數(shù)量，也就是說在網(wǎng)絡傳輸中節(jié)點的介數(shù)越高代表了數(shù)據(jù)包通過它的概率越高。在分類隨機帶寬分配方案中，這里為網(wǎng)絡中的每條邊分配權(quán)值σij＝gi＊gj，其中，gi和gj分別為連接邊兩端節(jié)點i和節(jié)點j的介數(shù)。此時，網(wǎng)絡中邊的權(quán)值σij高的邊意味著在網(wǎng)絡傳輸中占據(jù)著重要的位置，這些邊會是網(wǎng)絡上數(shù)據(jù)包流經(jīng)量很高的邊，肩負的傳遞負擔也重。因此，在帶有帶寬約束限制的網(wǎng)絡中，為權(quán)值高的連接邊分配的帶寬量對網(wǎng)絡傳輸性能會產(chǎn)生重大的影響。

組合2、組合3中，為低權(quán)值的邊（E1）分配低帶寬值（B1），相應權(quán)值高的邊（E2）分配高帶寬值（B2），這種分配方式下的網(wǎng)絡最大負載均高于各自網(wǎng)絡帶寬均分時產(chǎn)生的網(wǎng)絡最大負載。因此，在網(wǎng)絡總帶寬資源固定情況下，負載較重的高權(quán)值邊得到相應較高的帶寬分配會得到較好的網(wǎng)絡傳輸性能。

組合2、組合4中，為低權(quán)值的邊（E1）分配高帶寬值（B2），相應權(quán)值高的邊（E2）分配較低帶寬值（B1），這種分配方式下的網(wǎng)絡負載性能均劣于各自網(wǎng)絡帶寬均分時產(chǎn)生的網(wǎng)絡負載性能。此時，由于網(wǎng)絡傳輸中總的帶寬資源是固定不變的，為傳輸負載較重的邊分配較小帶寬會帶來網(wǎng)絡傳輸抑制數(shù)據(jù)包傳遞過程，而分配傳輸負載較輕的邊較多帶寬存在帶寬的浪費，從而影響到網(wǎng)絡負載性能，造成整個網(wǎng)絡負載能力降低。

此外，采用G－L路由策略的組合1、組合2帶寬分配下網(wǎng)絡傳輸性能分別優(yōu)于采用最短路由策略的組合3、組合4，說明文中的分類隨機帶寬分配方案沒有影響到路由策略本身對網(wǎng)絡傳輸性能的作用效果。

4 結(jié)論

設計了完全隨機帶寬分配方案和分類隨機帶寬分配方案。通過仿真試驗發(fā)現(xiàn)，完全隨機地分配網(wǎng)絡連接邊帶寬對網(wǎng)絡負載的影響帶有不確定性，因此，這種方案不是一種實用有效的帶寬分配方案，同時還發(fā)現(xiàn)，G－L路由策略相對于最短路由策略在保持帶寬隨機分配對網(wǎng)絡最大負載影響方面具有較好的魯棒性。在對分類隨機帶寬分配方案的研究中發(fā)現(xiàn)，在介數(shù)存在異質(zhì)性分布的復雜網(wǎng)絡中，為依據(jù)介數(shù)由高到低的邊集分派相應由高到低的帶寬集，有利于提升網(wǎng)絡負載性能。

［1］ 于灝，井元偉，周玉成，等.固定帶寬下的無標度網(wǎng)絡數(shù)據(jù)傳輸流量分析 ［J］.東北大學學報（自然科學版），2010，31（9）：1226－1229.Yu Hao，Jing Yuanwei，Zhou Yucheng，et al.Dynamic analysis of scale－free network traffic with fixed bandwidth［J］.Journal of Northeastern University（Natural Science），2010，31（9）：1226－1229.

［2］ 于灝，周玉成，井元偉，等.異質(zhì)化帶寬分配下的復雜網(wǎng)絡數(shù)據(jù)流負載問題研究 ［J］.物理學報，2013，62（8）：080502.Yu Hao，Zhou Yucheng，Jing Yuanwei，et al.Traffic dynamics of the complex networks with the heterogeneous bandwidth allocation［J］.Acta Phys Sin，2013，62（8）：080502.

［3］ Ling X，Hu M B，Du W B，et al.Bandwidth allocation strategy for traffic systems of scale－free network［J］.Physics Letters A，2010，374（48）：4825－4830.

［4］ Echenique Pablo，Oacute，Garde Mez，et al.improved routing strategies for internet traffic delivery［J］.Physical Review E，2004，70（5）：056105.

［5］ Chen Z Y，Wang X F.A congestion awareness routing strategy for scale－free networks with tunable clustering［J］.Physica A－Statistical Me－chanics and Its Applications，2006，364：595－602.

［6］ 王丹，于灝，井元偉，等.無標度網(wǎng)絡中擁塞轉(zhuǎn)變的動態(tài)分析 ［J］.東北大學學報（自然科學版），2009，30（4）：462－465.Wang Dan，Yu Hao，Jing Yuanwei，et al.Dynamics of jamming transitions in scale－free networks［J］.Journal of Northeastern University（Natural Science），2009，30（4）：462－465.

［7］ Arenas A，Danon，Diaz G A，et al.Local search with congestion in complex communication networks［J］.Lecture Notes in Computer Science，2004，3038：1078－1085.

［8］ Wang D，Jing Y W，Zhang S Y.Traffic dynamics based on a traffic awareness routing strategy on scale－free networks［J］.Physica A－Statistical Mechanics and Its Applications，2008，387：3001－3007.

［9］ 王丹，于灝，井元偉，等.基于感知流量算法的復雜網(wǎng)絡擁塞問題研究 ［J］.物理學報，2009，58（10）：6802－6808.Wang Dan，Yu Hao，Jing Yuanwei，et al.Study on the congestion in complex network based on traffic awareness algorithm［J］.Acta Phys Sin，2009，58（10）：6802－6808.

［10］Holme P，Kim B J.Growing scale－free networks with tunable clustering［J］.Physical Review E，2002，65：026107.