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

梁 根，梁活民

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

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

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

梁 根1，梁活民2

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

2.2 流量預(yù)測計算方法

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

設(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ù)測流量，周期t前的過去n個周期t0，t1，…，tn的平均實際流量值為：，那么利用預(yù)測函數(shù)可得業(yè)務(wù)流i在控制周期t的流量值為：

其中：

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

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

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

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

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

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

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

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

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

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

3 實驗和性能評估

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

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

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

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

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

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

圖2 實際帶寬與預(yù)測帶寬比較

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

圖4 場景1下時延對比

圖5 場景2下時延對比

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

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

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

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

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

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

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

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

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

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

[1]林闖，李寅，萬劍雄.計算機網(wǎng)絡(luò)服務(wù)質(zhì)量優(yōu)化方法研究綜述[J].計算機學(xué)報，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)先級的靜態(tài)優(yōu)先級分配算法[J].軟件學(xué)報，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分布式動態(tài)帶寬分配實現(xiàn)機制[J].軟件學(xué)報，2008，19（7）：1693-1706.

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

[9]聶得欣，袁小坊，王東，等.鏈路層分類包的網(wǎng)絡(luò)流量自相似性研究[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ù)分類的動態(tài)帶寬分配方法等很難適應(yīng)業(yè)務(wù)流特性，無法保證各級業(yè)務(wù)的服務(wù)質(zhì)量。設(shè)計了流量預(yù)測及帶寬分配模型，給出了流量預(yù)測計算方法，提出多業(yè)務(wù)流量預(yù)測動態(tài)帶寬分配方法（MSTPDBA），該方法基于業(yè)務(wù)預(yù)測流量的大小進行可用帶寬的重新分配。仿真實驗證明了MSTPDBA的有效性，能控制不同業(yè)務(wù)的時延，并提高了系統(tǒng)帶寬資源的利用率。

服務(wù)質(zhì)量；業(yè)務(wù)類型；插值預(yù)測；可用帶寬；動態(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)新人才培育項目（No.LYM08080）。

梁根（1979—），男，副教授，主要研究方向為網(wǎng)絡(luò)協(xié)議及算法；梁活民（1980—），男，博士，講師，主要研究方向為網(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