隨機帶寬分配對復雜網絡傳輸性能的影響分析

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

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

0 引言

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

1 傳輸流量模型

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

G－L路由策略中的節點權值為

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

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

為了更好描述網絡傳輸中流量狀態變化過程，引入狀態相變參數η來進行描述［7－9］：

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

2 隨機帶寬分配方案設計

為了通過帶寬隨機分配對網絡傳輸的影響，探索合理的分配方案制定依據，本文設計了兩種隨機帶寬分配方案：完全隨機帶寬分配方案和分類隨機帶寬分配方案來進行研究。

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

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

3 隨機帶寬分配網絡流量仿真與分析

選取HK－BA無標度網絡［10］作為網絡拓撲平臺。網絡規模為1 000個節點。網絡模型初始節點互不相連m0＝m＝3，調節概率為0.5。

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

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

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

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

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

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

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

圖3 采用組合1時，網絡流量狀態Fig.3 The network traffic with group 1

圖4 采用組合2時，網絡流量狀態Fig.4 The network traffic with group 2

圖5 采用組合3時，網絡流量狀態Fig.5 The network traffic with group 3

圖6 采用組合4時，網絡流量狀態Fig.6 The network traffic with group 4

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

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

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

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

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

4 結論

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

［1］ 于灝，井元偉，周玉成，等.固定帶寬下的無標度網絡數據傳輸流量分析 ［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］ 于灝，周玉成，井元偉，等.異質化帶寬分配下的復雜網絡數據流負載問題研究 ［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］ 王丹，于灝，井元偉，等.無標度網絡中擁塞轉變的動態分析 ［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］ 王丹，于灝，井元偉，等.基于感知流量算法的復雜網絡擁塞問題研究 ［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.