隨機(jī)帶寬分配對(duì)復(fù)雜網(wǎng)絡(luò)傳輸性能的影響分析

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

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

0 引言

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

1 傳輸流量模型

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

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

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

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

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

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

2 隨機(jī)帶寬分配方案設(shè)計(jì)

為了通過(guò)帶寬隨機(jī)分配對(duì)網(wǎng)絡(luò)傳輸?shù)挠绊懀剿骱侠淼姆峙浞桨钢贫ㄒ罁?jù)，本文設(shè)計(jì)了兩種隨機(jī)帶寬分配方案：完全隨機(jī)帶寬分配方案和分類(lèi)隨機(jī)帶寬分配方案來(lái)進(jìn)行研究。

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

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

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

選取HK－BA無(wú)標(biāo)度網(wǎng)絡(luò)［10］作為網(wǎng)絡(luò)拓?fù)淦脚_(tái)。網(wǎng)絡(luò)規(guī)模為1 000個(gè)節(jié)點(diǎn)。網(wǎng)絡(luò)模型初始節(jié)點(diǎn)互不相連m0＝m＝3，調(diào)節(jié)概率為0.5。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

［1］ 于灝，井元偉，周玉成，等.固定帶寬下的無(wú)標(biāo)度網(wǎng)絡(luò)數(shù)據(jù)傳輸流量分析 ［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），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ì)化帶寬分配下的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)流負(fù)載問(wèn)題研究 ［J］.物理學(xué)報(bào)，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ú)標(biāo)度網(wǎng)絡(luò)中擁塞轉(zhuǎn)變的動(dòng)態(tài)分析 ［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），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］ 王丹，于灝，井元偉，等.基于感知流量算法的復(fù)雜網(wǎng)絡(luò)擁塞問(wèn)題研究 ［J］.物理學(xué)報(bào)，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.