梁 根，梁活民

1.廣東石油化工學(xué)院 理學(xué)院，廣東 茂名 525000

2.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣州 510641

多業(yè)務(wù)流量預(yù)測(cè)動(dòng)態(tài)帶寬分配方法

梁 根1，梁活民2

1.廣東石油化工學(xué)院 理學(xué)院，廣東 茂名 525000

2.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣州 510641

1 引言

隨著寬帶網(wǎng)絡(luò)通信技術(shù)的快速發(fā)展，下一代寬帶網(wǎng)絡(luò)將承載話音、數(shù)據(jù)、多媒體等業(yè)務(wù)，如何保證多用戶、多業(yè)務(wù)的服務(wù)質(zhì)量（QoS）是寬帶網(wǎng)絡(luò)中一個(gè)至關(guān)重要的問(wèn)題[1]。因此，需要一種有效的帶寬分配機(jī)制，在保證多業(yè)務(wù)對(duì)服務(wù)質(zhì)量不同需求的前提下，盡可能充分地利用帶寬資源[2]。

當(dāng)前實(shí)現(xiàn)QoS的主要技術(shù)機(jī)制主要是基于不同業(yè)務(wù)對(duì)QoS的需求不同采用靜態(tài)帶寬資源分配方法（Static Bandwidth Allocation，SBA）[3]，即在節(jié)點(diǎn)設(shè)置各類業(yè)務(wù)的帶寬資源分配算法及相應(yīng)權(quán)值參數(shù)，網(wǎng)絡(luò)運(yùn)行時(shí)帶寬資源分配算法與QoS參數(shù)均不再變化。靜態(tài)資源的分配一般采用傳統(tǒng)的QoS參數(shù)方法估計(jì)各業(yè)務(wù)的峰值帶寬需求、平均帶寬需求，并根據(jù)各業(yè)務(wù)的相關(guān)QoS指標(biāo)要求，經(jīng)綜合平衡計(jì)算后固定設(shè)置。但SBA方法很難適應(yīng)業(yè)務(wù)流特性的變化，因此難以做到在網(wǎng)絡(luò)擁塞時(shí)有效保證優(yōu)先業(yè)務(wù)的服務(wù)質(zhì)量，又難以在網(wǎng)絡(luò)較為空閑時(shí)提高網(wǎng)絡(luò)的吞吐量[4]。

文獻(xiàn)[5]等利用適當(dāng)?shù)臉I(yè)務(wù)統(tǒng)計(jì)建模來(lái)預(yù)測(cè)未來(lái)的業(yè)務(wù)帶寬需要，通過(guò)這種預(yù)測(cè)的方式進(jìn)行帶寬分配。這種方法考慮了在不同用戶中利用區(qū)分服務(wù)的管理來(lái)保證 QoS優(yōu)先級(jí)，可以為不同業(yè)務(wù)提供相應(yīng)的QoS。文獻(xiàn)[6]基于業(yè)務(wù)分類的動(dòng)態(tài)帶寬分配算法（Class of Services Dynamic Bandwidth Allocation，CoSDBA）中，每個(gè)業(yè)務(wù)被劃分為高、中、低三個(gè)優(yōu)先級(jí)，CoSDBA算法根據(jù)這些優(yōu)先級(jí)來(lái)分配帶寬。具體來(lái)講，帶寬首先滿足高優(yōu)先級(jí)業(yè)務(wù)的請(qǐng)求，然后考慮中等優(yōu)先級(jí)的業(yè)務(wù)，若剩余帶寬不能滿足所有中等優(yōu)先級(jí)業(yè)務(wù)的需求，則按照中優(yōu)先級(jí)隊(duì)列的帶寬需求占整個(gè)系統(tǒng)中該優(yōu)先級(jí)的所有隊(duì)列的帶寬需求的比例來(lái)分配剩余帶寬，這種方法也適用于對(duì)低優(yōu)先級(jí)業(yè)務(wù)的帶寬分配，但在這種方法中低優(yōu)先級(jí)的隊(duì)列有可能得不到任何帶寬。

傳統(tǒng)的動(dòng)態(tài)帶寬分配方法存在著帶寬分配的多分配與少分配的情況，前者降低帶寬利用率，而后者則以侵犯業(yè)務(wù)的服務(wù)質(zhì)量為代價(jià)[7]。大量的研究結(jié)果表明：網(wǎng)絡(luò)業(yè)務(wù)流量具有自相似的特征，網(wǎng)絡(luò)流量在較長(zhǎng)時(shí)間范圍內(nèi)具有長(zhǎng)時(shí)相關(guān)性[8-9]。

因此，本文利用帶寬預(yù)測(cè)技術(shù)，對(duì)實(shí)際的業(yè)務(wù)流量信息進(jìn)行了預(yù)測(cè)，并且根據(jù)預(yù)測(cè)流量的大小對(duì)系統(tǒng)的帶寬進(jìn)行動(dòng)態(tài)分配，從而提高系統(tǒng)帶寬分配的精度和響應(yīng)速度。

2 MSTPDBA模型及方法設(shè)計(jì)

2.1 流量預(yù)測(cè)及帶寬分配模型設(shè)計(jì)

設(shè)有并發(fā)的m個(gè)業(yè)務(wù)流同時(shí)進(jìn)入系統(tǒng)，并行的流量控制器分別對(duì)每一個(gè)業(yè)務(wù)流作預(yù)測(cè)，把預(yù)測(cè)的結(jié)果發(fā)送到動(dòng)態(tài)帶寬分配器中，動(dòng)態(tài)帶寬分配器根據(jù)流量的預(yù)測(cè)大小和帶寬分配算法動(dòng)態(tài)地對(duì)系統(tǒng)的帶寬進(jìn)行分配，具體的模型如圖1。

圖1 流量預(yù)測(cè)帶寬分配模型

本文研究的多業(yè)務(wù)流量預(yù)測(cè)動(dòng)態(tài)帶寬分配方法的工作過(guò)程分為兩個(gè)階段：流量預(yù)測(cè)階段和帶寬分配階段。從時(shí)刻0開(kāi)始，以t為控制周期，每個(gè)控制周期內(nèi)分別循環(huán)完成流量預(yù)測(cè)和帶寬分配這兩個(gè)過(guò)程。在第t個(gè)周期里，并行帶寬控制器對(duì)輸入的業(yè)務(wù)流在下一個(gè)周期的流量進(jìn)行預(yù)測(cè)，在該周期內(nèi)對(duì)前一個(gè)周期預(yù)測(cè)的流量進(jìn)行帶寬分配，在下一個(gè)周期則對(duì)本周期預(yù)測(cè)的流量進(jìn)行帶寬分配。

2.2 流量預(yù)測(cè)計(jì)算方法

設(shè)系統(tǒng)的最小處理時(shí)隙為τ，每一次流量預(yù)測(cè)及帶寬分配的控制周期為t，并且有t=k×τ(n=1，2，…，∞)。一般來(lái)說(shuō)，k值越小，流量預(yù)測(cè)的誤差就越小，而當(dāng)k比較大時(shí)，或者當(dāng)流量變化比較大時(shí)，流量預(yù)測(cè)的誤差就會(huì)越大。

設(shè)系統(tǒng)支持i種業(yè)務(wù)類型(i=1，2，…，m)，業(yè)務(wù)的權(quán)重系數(shù)為φi(i=1，2，…，m)，Bti為業(yè)務(wù)類型i在周期t的預(yù)測(cè)流量，周期t前的過(guò)去n個(gè)周期t0，t1，…，tn的平均實(shí)際流量值為：，那么利用預(yù)測(cè)函數(shù)可得業(yè)務(wù)流i在控制周期t的流量值為：

其中：

2.3 基于流量預(yù)測(cè)的動(dòng)態(tài)帶寬分配方法

帶寬分配算法根據(jù)可用網(wǎng)絡(luò)帶寬的預(yù)測(cè)值和當(dāng)前各鏈路的情況，對(duì)各鏈路的可用帶寬進(jìn)行動(dòng)態(tài)分配，以優(yōu)化整體的控制性能。在本文中，基于下一周期各業(yè)務(wù)的流量預(yù)測(cè)以及當(dāng)前系統(tǒng)帶寬、各業(yè)務(wù)的優(yōu)先級(jí)指數(shù)等，計(jì)算各業(yè)務(wù)的帶寬分配參數(shù)。

（1）若預(yù)測(cè)的所有業(yè)務(wù)流量小于或者等于系統(tǒng)的總可用帶寬，即

在這種情況下，系統(tǒng)有足夠大的帶寬可以進(jìn)行分配，因此，各業(yè)務(wù)流的帶寬分配大小為：

由上式可以看出，帶寬的分配首先是在保證各鏈路有足夠的可用帶寬的基礎(chǔ)上，對(duì)當(dāng)前的系統(tǒng)可分配的帶寬資源按預(yù)測(cè)值大小按比例進(jìn)行分配。這樣，權(quán)重較低的鏈路也能獲得一定數(shù)量的帶寬資源，不會(huì)給權(quán)重高的鏈路占有大部分帶寬資源，導(dǎo)致部分權(quán)重低的鏈路得不到任何資源。利用這種帶寬分配策略，在系統(tǒng)負(fù)載低的時(shí)候也能提高總體利用率。

（2）若預(yù)測(cè)的所有業(yè)務(wù)流量大于系統(tǒng)的總可用帶寬，即

當(dāng)預(yù)測(cè)的所有業(yè)務(wù)流量大于系統(tǒng)的總可用帶寬，系統(tǒng)的總帶寬資源有限時(shí)，即網(wǎng)絡(luò)負(fù)載很重的時(shí)候，部分流量預(yù)測(cè)值比較低的鏈路可能長(zhǎng)時(shí)間得不到或得到很少的帶寬資源，導(dǎo)致該鏈路將在較大程度上受到丟包和長(zhǎng)時(shí)延的影響，使得傳輸性能持續(xù)惡化。

因此，為了優(yōu)化系統(tǒng)的整體性能，在這種情況下，首先對(duì)系統(tǒng)中的資源按照各業(yè)務(wù)的權(quán)重進(jìn)行初始化分配，即

設(shè)Bfree為空閑帶寬，對(duì)于所有初始化分配帶寬大于或者等于預(yù)測(cè)帶寬的業(yè)務(wù)，進(jìn)行如下配置：

然后，將空閑帶寬Bfree再重新分配到那些初始化分配帶寬小于預(yù)測(cè)帶寬的業(yè)務(wù)，具體分配的數(shù)量為：

3 實(shí)驗(yàn)和性能評(píng)估

3.1 實(shí)驗(yàn)方法、參數(shù)和環(huán)境

使用NS-2驗(yàn)證本文提出的MSTPDBA方法的有效性。網(wǎng)絡(luò)中業(yè)務(wù)流屬于不同優(yōu)先級(jí)，其到達(dá)速率為隨機(jī)，所有業(yè)務(wù)流的數(shù)據(jù)幀長(zhǎng)度均為1 000字節(jié)，測(cè)試時(shí)間長(zhǎng)度為100個(gè)控制周期。首先通過(guò)本文MSTPDBA方法預(yù)測(cè)業(yè)務(wù)流加入網(wǎng)絡(luò)后所能達(dá)到的吞吐量，并將預(yù)測(cè)結(jié)果與實(shí)際結(jié)果相比較。為充分驗(yàn)證本文MSTPDBA方法的有效性，再與靜態(tài)帶寬分配算法（SBA）、基于業(yè)務(wù)分類的動(dòng)態(tài)帶寬分配算法（CoSDBA）進(jìn)行了仿真比較，具體仿真參數(shù)如表1。

表1 仿真參數(shù)說(shuō)明

在仿真中，使用了三種業(yè)務(wù)流等級(jí)，最高優(yōu)先級(jí)的EF流，中等優(yōu)先級(jí)的AF數(shù)據(jù)流和最低優(yōu)先級(jí)的BE數(shù)據(jù)流，并且采用兩組不同的流量比例的仿真測(cè)試場(chǎng)景：在第一組仿真場(chǎng)景中，EF、AF和BE業(yè)務(wù)流分別各占33.3%；在第二組仿真場(chǎng)景中，EF、AF和BE流的比例分別變?yōu)?0%、30%、10%。分別對(duì)這兩組場(chǎng)景下的時(shí)延和總帶寬利用率進(jìn)行性能測(cè)試。

3.2 MSTPDBA方法預(yù)測(cè)性能分析

由于流量的突發(fā)和負(fù)載的變化，監(jiān)測(cè)到的實(shí)際流量和預(yù)測(cè)結(jié)果如圖2所示。實(shí)際流量在15～40之間波動(dòng)增加，從圖2中可知，MSTPDBA方法每個(gè)控制周期內(nèi)均能較好地預(yù)測(cè)下一個(gè)周期的流量。從圖3可以看出，其預(yù)測(cè)誤差范圍大致在±20%區(qū)間之間，但在流量瞬時(shí)波動(dòng)較大的時(shí)候，預(yù)測(cè)誤差較大。

圖2 實(shí)際帶寬與預(yù)測(cè)帶寬比較

圖3 預(yù)測(cè)誤差百分比

圖4 場(chǎng)景1下時(shí)延對(duì)比

圖5 場(chǎng)景2下時(shí)延對(duì)比

圖4和圖5分別給出了在兩種不同流量占用場(chǎng)景下三種算法的端到端平均包時(shí)延。在場(chǎng)景1中，根據(jù)圖4可以看出，對(duì)于BE業(yè)務(wù)流，CoSDBA顯示出最大的平均包時(shí)延，而SBA顯示出最小平均包時(shí)延。這是因?yàn)樵诟鞣N不同優(yōu)先級(jí)的業(yè)務(wù)流在占用相同比例的情況下，BE業(yè)務(wù)流流量較大，CoSDBA方法中低優(yōu)先級(jí)的業(yè)務(wù)流得不到優(yōu)先處理；對(duì)于AF業(yè)務(wù)流，三種方法的平均包時(shí)延相差不大；由于MSTPDBA和CoSDBA引入了業(yè)務(wù)權(quán)重或優(yōu)先級(jí)機(jī)制以滿足高優(yōu)先級(jí)業(yè)務(wù)的QoS需求，正如所預(yù)料的，對(duì)EF業(yè)務(wù)流來(lái)說(shuō)，MSTPDBA具有最小的平均時(shí)延，同時(shí)，CoSDBA的平均包時(shí)延與MSTPDBA的平均包時(shí)延接近，并較優(yōu)于SBA的平均包時(shí)延。

在場(chǎng)景2中，不同的業(yè)務(wù)流量占用場(chǎng)景對(duì)三個(gè)算法的時(shí)延性能有較明顯的影響，從圖5可以發(fā)現(xiàn)，當(dāng)EF業(yè)務(wù)占總流量的比例更多的時(shí)候，SBA由于不能給EF業(yè)務(wù)流保障足夠的帶寬分配，因此顯示出最差的性能。MSTPDBA在該場(chǎng)景負(fù)載較輕的情況下比CoSDBA的平均包時(shí)延稍好，但當(dāng)負(fù)載超過(guò)60%時(shí)，由于預(yù)測(cè)的誤差與運(yùn)算量的增加，MSTPDBA的平均包時(shí)延有所增加；在該場(chǎng)景下，三個(gè)算法的AF業(yè)務(wù)流的平均時(shí)延相差不大，CoSDBA表現(xiàn)出較好的性能；由于在該場(chǎng)景下，BE業(yè)務(wù)流只占總流量的10%，SBA分配給BE業(yè)務(wù)流的帶寬有所剩余，因此對(duì)于BE業(yè)務(wù)流，SBA的平均包時(shí)延在這三個(gè)算法中最小，CoSDBA最大，MSTPDBA次之，但通過(guò)對(duì)比圖4的BE流可以看出，它們之間的差距已經(jīng)明顯縮小。

圖6和圖7給出了在兩種不同流量占用場(chǎng)景下三種算法的系統(tǒng)帶寬利用率比較。由圖6可以看出，在場(chǎng)景1下，三種算法的系統(tǒng)帶寬利用率基本上呈現(xiàn)線性增加關(guān)系，除部分系統(tǒng)開(kāi)銷帶寬外，由于MSTPDBA能對(duì)剩余空閑帶寬進(jìn)行再分配，因此在負(fù)載較重的情況下表現(xiàn)出較好的帶寬利用率；由于在該場(chǎng)景下各類流量所占的比例相同，SBA的系統(tǒng)帶寬利用率基本上也能維持呈現(xiàn)線性增長(zhǎng)。

圖6 場(chǎng)景1下系統(tǒng)帶寬利用率對(duì)比

圖7 場(chǎng)景2下系統(tǒng)帶寬利用率對(duì)比

在圖7顯示的場(chǎng)景2的測(cè)試中，由于EF業(yè)務(wù)流占比例較大，當(dāng)系統(tǒng)負(fù)載超過(guò)50%的時(shí)候，SBA的EF業(yè)務(wù)流得不到足夠的帶寬，數(shù)據(jù)排隊(duì)時(shí)延加大，系統(tǒng)帶寬利用率較其他兩種方法增長(zhǎng)得慢許多；在該場(chǎng)景下，MSTPDBA仍然能維持較好的線性增長(zhǎng)，由于CoSDBA對(duì)占用比例較大的EF業(yè)務(wù)流處理得較有優(yōu)勢(shì)，系統(tǒng)帶寬利用率與MSTPDBA相差不大。

4 結(jié)論和進(jìn)一步的研究工作

實(shí)際的網(wǎng)絡(luò)帶寬控制系統(tǒng)一般在網(wǎng)絡(luò)帶寬受到一定限制且負(fù)載可變的動(dòng)態(tài)環(huán)境中運(yùn)行。傳統(tǒng)的靜態(tài)資源調(diào)度策略不能適應(yīng)不可預(yù)見(jiàn)的動(dòng)態(tài)環(huán)境。因此，開(kāi)發(fā)合適的動(dòng)態(tài)調(diào)度策略以適應(yīng)網(wǎng)絡(luò)中業(yè)務(wù)流的變化，優(yōu)化系統(tǒng)的性能尤為重要。

本文在多業(yè)務(wù)環(huán)境下提出了一種流量預(yù)測(cè)動(dòng)態(tài)帶寬分配方法，該方法基于插值預(yù)測(cè)函數(shù)動(dòng)態(tài)預(yù)測(cè)方法對(duì)系統(tǒng)的業(yè)務(wù)流量進(jìn)行在線預(yù)測(cè)，并通過(guò)帶寬管理器對(duì)預(yù)測(cè)到流量進(jìn)行可用帶寬資源動(dòng)態(tài)分配，提高了系統(tǒng)的整體性能，同時(shí)也優(yōu)化了帶寬資源的利用。仿真結(jié)果表明本文提出方法具有較好的性能和適應(yīng)性。

如何結(jié)合具體業(yè)務(wù)的服務(wù)質(zhì)量要求（吞吐量、延遲、丟包率等）以及網(wǎng)絡(luò)的業(yè)務(wù)流量配置協(xié)議參數(shù)，在滿足服務(wù)質(zhì)量要求的同時(shí)達(dá)到最佳的網(wǎng)絡(luò)性能，是下一步的研究目標(biāo)。

[1]林闖，李寅，萬(wàn)劍雄.計(jì)算機(jī)網(wǎng)絡(luò)服務(wù)質(zhì)量?jī)?yōu)化方法研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（1）：1-14.

[2]Cruz-Perez F A,Ortigoza-Guerrero L.Flexible resource allocation strategies for class-based QoS provisioning in mobile networks[J].IEEE Transactions on Vehicular Technology，2004，53（3）：805-819.

[3]賓雪蓮，楊玉海，金士堯.一種有限優(yōu)先級(jí)的靜態(tài)優(yōu)先級(jí)分配算法[J].軟件學(xué)報(bào)，2004，15（6）：815-822.

[4]Yeoul S，Lee S，Lee Tae-Jin，et al.Double-phase polling algorithm based on partitioned ONU subgroups for high utilization in EPONs[J].Journal Optical Communication Network，2009，1（5）：484-497.

[5]Chiti F，F(xiàn)antacci R，Tarchi D，et al.QoS provisioning in GEO satellite with onboard processing using sredictor algorithms[J]. IEEE Wireless Communications Magazine，2005，12（5）：21-27.

[6]Choi S I，Huh J D.Dynamic bandwidth allocation algorithm for multimedia services over Ethernet PONs[J].Journal of Electronics and Telecommunications Research Institute，2002，24（6）：465?468.

[7]張晉豫，劉犁.基于效用EPON分布式動(dòng)態(tài)帶寬分配實(shí)現(xiàn)機(jī)制[J].軟件學(xué)報(bào)，2008，19（7）：1693-1706.

[8]姜明，吳春明，張旻，等.網(wǎng)絡(luò)流量預(yù)測(cè)中的時(shí)間序列模型比較研究[J].電子學(xué)報(bào)，2009，37（11）：2354-2358.

[9]聶得欣，袁小坊，王東，等.鏈路層分類包的網(wǎng)絡(luò)流量自相似性研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（5）：129-131.

LIANG Gen1,LIANG Huomin2

1.College of Science,Guangdong University of Petrochemical Technology,Maoming,Guangdong 525000,China
2.School of Computer Science and Engineering,South China University of Technology,Guangzhou 510641,China

Static bandwidth resource allocation or class of services dynamic bandwidth allocation is difficult to adapt to the characteristics of service flow,and unable to ensure the QoS of all levels service.The model of traffic prediction and bandwidth allocation is designed.The method of traffic prediction and Multi-Service Traffic Prediction Dynamic Bandwidth Allocation（MSTPDBA）are proposed.MSTPDBA can reallocate the available bandwidth by the size of traffic prediction.MSTPDBA which can control the services delay and improve utilization ratio of system bandwidth is proven to be effective by simulated experiments.

Quality of Service（Qos）;class of service;interpolation prediction;available bandwidth;dynamic allocation

靜態(tài)帶寬資源分配方法或基于業(yè)務(wù)分類的動(dòng)態(tài)帶寬分配方法等很難適應(yīng)業(yè)務(wù)流特性，無(wú)法保證各級(jí)業(yè)務(wù)的服務(wù)質(zhì)量。設(shè)計(jì)了流量預(yù)測(cè)及帶寬分配模型，給出了流量預(yù)測(cè)計(jì)算方法，提出多業(yè)務(wù)流量預(yù)測(cè)動(dòng)態(tài)帶寬分配方法（MSTPDBA），該方法基于業(yè)務(wù)預(yù)測(cè)流量的大小進(jìn)行可用帶寬的重新分配。仿真實(shí)驗(yàn)證明了MSTPDBA的有效性，能控制不同業(yè)務(wù)的時(shí)延，并提高了系統(tǒng)帶寬資源的利用率。

服務(wù)質(zhì)量；業(yè)務(wù)類型；插值預(yù)測(cè)；可用帶寬；動(dòng)態(tài)分配

A

TP393

10.3778/j.issn.1002-8331.1202-0137

LIANG Gen,LIANG Huomin.Dynamic bandwidth allocation method of multi-service based on traffic prediction.Computer Engineering and Applications,2013,49（18）：82-85.

廣東省自然科學(xué)基金（No.10151601501000015）；廣東高校優(yōu)秀青年創(chuàng)新人才培育項(xiàng)目（No.LYM08080）。

梁根（1979—），男，副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)協(xié)議及算法；梁活民（1980—），男，博士，講師，主要研究方向?yàn)榫W(wǎng)絡(luò)并行分布式處理。E-mail：L_Gen@126.com

2012-02-08

2012-04-09

1002-8331（2013）18-0082-04

CNKI出版日期：2012-06-15 http://www.cnki.net/kcms/detail/11.2127.TP.20120615.1727.049.html