梁根，俞鶴偉，孫立民，秦勇

（1.廣東石油化工學(xué)院 理學(xué)院，廣東 茂名 525000；2.廣東省石化裝備故障診斷重點(diǎn)實(shí)驗(yàn)室，廣東 茂名 525000；3.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510641；4.東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東 東莞 523808）

1 引言

多鏈路寬帶接入網(wǎng)由于網(wǎng)絡(luò)結(jié)構(gòu)靈活、擴(kuò)展能力強(qiáng)、建網(wǎng)成本低和故障率低等特性使之成為業(yè)界組網(wǎng)的首選方案[1]。網(wǎng)絡(luò)應(yīng)用的發(fā)展使數(shù)據(jù)傳輸己逐步由單一的數(shù)據(jù)傳輸過(guò)渡到數(shù)據(jù)、語(yǔ)音、圖像等綜合信息的傳輸，因此，新一代寬帶接入網(wǎng)必須能夠同時(shí)提供高速的包括實(shí)時(shí)業(yè)務(wù)在內(nèi)的多種業(yè)務(wù)傳輸。然而，實(shí)時(shí)業(yè)務(wù)的傳輸不同于普通的數(shù)據(jù)傳輸，這些實(shí)時(shí)業(yè)務(wù)往往對(duì)服務(wù)質(zhì)量（QoS，quality of service）指標(biāo)如帶寬、時(shí)延、抖動(dòng)等有較高的要求[2]。因此，為了保證實(shí)時(shí)業(yè)務(wù)端到端的QoS，多鏈路寬帶接入網(wǎng)作為端到端網(wǎng)絡(luò)中的一段，必須要具備相應(yīng)的 QoS保障能力。如何進(jìn)一步優(yōu)化組合資源、提供更好的帶寬控制和更多樣的寬帶接入業(yè)務(wù)支持是多鏈路寬帶接入網(wǎng)中熱門(mén)的研究?jī)?nèi)容之一。

QoS是指數(shù)據(jù)分組在網(wǎng)絡(luò)傳輸中的各種性能參數(shù)滿(mǎn)足某業(yè)務(wù)的需求[3]，這些性能參數(shù)可以用傳輸時(shí)延、分組丟失率、時(shí)延抖動(dòng)、吞吐率和帶寬利用率等指標(biāo)來(lái)度量[4]，其主要目的就是為各種業(yè)務(wù)提供可靠的端到端的QoS保證。為了達(dá)到一定的QoS保證，通常會(huì)在網(wǎng)絡(luò)內(nèi)采用某種帶寬分配算法，通過(guò)對(duì)不同的業(yè)務(wù)分配不同的帶寬來(lái)控制其QoS等級(jí)。

在帶寬分配算法的研究中，不少學(xué)者和專(zhuān)家己經(jīng)做了很多研究工作，目前來(lái)看，主要分為2類(lèi)：靜態(tài)帶寬分配（SBA,static bandwidth allocation）算法和動(dòng)態(tài)帶寬分配（DBA,dynamic bandwidth allocation）算法[5]。

靜態(tài)帶寬分配算法SBA在一個(gè)輪詢(xún)周期內(nèi)為每個(gè)接入點(diǎn)AP（access point）分配固定大小的帶寬，SBA算法不需要帶寬協(xié)商過(guò)程，因此很簡(jiǎn)單，容易實(shí)現(xiàn)。但是，由于網(wǎng)絡(luò)流量的突發(fā)性，會(huì)造成有的接入點(diǎn)負(fù)載較小，而有的接入點(diǎn)負(fù)載較大。負(fù)載較小的接入點(diǎn)不能充分利用帶寬，其他負(fù)載大的接入點(diǎn)時(shí)延增大，系統(tǒng)吞吐量減小，造成帶寬浪費(fèi)。好的帶寬分配算法應(yīng)當(dāng)能夠根據(jù)系統(tǒng)的整體情況實(shí)時(shí)動(dòng)態(tài)地調(diào)整各接入點(diǎn)的帶寬分配[6]，SBA雖然簡(jiǎn)單，但在多鏈路寬帶接入網(wǎng)中不是理想的方案。

因此，必須在系統(tǒng)內(nèi)執(zhí)行動(dòng)態(tài)帶寬分配算法DBA，也就是說(shuō)，中央控制點(diǎn)根據(jù)每個(gè)接入點(diǎn)實(shí)時(shí)的帶寬需求分配不同的帶寬給每個(gè)接入點(diǎn)，這樣才能提高帶寬的利用率，降低分組時(shí)延，增加系統(tǒng)吞吐量[7]。

目前，國(guó)內(nèi)外對(duì)DBA算法的研究有很多，在這里把這些DBA算法劃分為兩大類(lèi)：一類(lèi)不支持QoS的DBA算法；一類(lèi)支持QoS的DBA算法。

不支持QoS的經(jīng)典DBA算法有自適應(yīng)交織輪詢(xún)IPACT(interleaved polling with adaptive cycle time)算法[8]，該算法通過(guò)交叉輪詢(xún)并且輪詢(xún)周期長(zhǎng)度隨著帶寬請(qǐng)求動(dòng)態(tài)變化的方法來(lái)降低數(shù)據(jù)時(shí)延，從而提高系統(tǒng)帶寬利用率。IPACT算法和SBA算法相比較，大大提高了帶寬利用率，但它仍然存在以下缺點(diǎn)：一個(gè)是存在輕負(fù)載懲罰問(wèn)題，因?yàn)镮PACT算法輪詢(xún)周期是不固定的，這樣當(dāng)系統(tǒng)的負(fù)載比較輕時(shí)，分配給每個(gè)接入點(diǎn)的時(shí)隙很短，輪詢(xún)周期也相應(yīng)變得很短，浪費(fèi)了大量的帶寬；另一個(gè)是IPACT算法是一種交織輪詢(xún)算法，不足之處在于只是基于當(dāng)前獲取的接入點(diǎn)帶寬請(qǐng)求信息來(lái)確定下一個(gè)接入點(diǎn)上行信道的帶寬，而不能從全局的角度出發(fā)，考慮所有接入點(diǎn)的上行帶寬請(qǐng)求來(lái)進(jìn)行更合理的帶寬分配；另外更重要的一點(diǎn)是，IPACT算法不支持QoS。

對(duì)于IPACT算法，國(guó)內(nèi)外很多文獻(xiàn)對(duì)其進(jìn)行了改進(jìn)。文獻(xiàn)中提出了預(yù)估授權(quán)協(xié)議IPACT-GE(IPACT with grant estimation)[9]，IPACT-GE 對(duì)加速轉(zhuǎn)發(fā)流(EF)的抖動(dòng)性能進(jìn)行了改進(jìn)，對(duì)EF數(shù)據(jù)流采用報(bào)告前授權(quán)，對(duì)于EF流，抖動(dòng)時(shí)延是完全確定的。IPACT-GE允許在收到反饋消息之前分配帶寬，在前一周期的消息中，局端設(shè)備包含了EF數(shù)據(jù)的帶寬分配信息。但是，IPACT-GE同樣可能在DBA計(jì)算和授權(quán)信息往返之間存在空閑信道。文獻(xiàn)采用多線程輪詢(xún)的方式改進(jìn)了IPACT算法，降低了數(shù)據(jù)時(shí)延，但是由于數(shù)據(jù)分組的時(shí)延抖動(dòng)比較大，因此不適合語(yǔ)音業(yè)務(wù)。

支持QoS的DBA算法有增強(qiáng)突發(fā)輪詢(xún)EBDBA(enhanced burst-polling DBA)算法[10,11]。在 EBDBA算法中，根據(jù)最小保證帶寬，確定是立即給相關(guān)的接入點(diǎn)授權(quán)帶寬，還是等待最后一個(gè)接入節(jié)點(diǎn)的反饋消息，進(jìn)行DBA計(jì)算之后，再授權(quán)分配帶寬。這種方法可以減少信道空閑時(shí)間，但如果所有接入節(jié)點(diǎn)終端都是重負(fù)載狀態(tài)，那么這時(shí)候EBDBA算法失效，完全退化為IPACT。

國(guó)內(nèi)有學(xué)者在支持QoS的EBDBA算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出了自適應(yīng)動(dòng)態(tài)帶寬早期分配(ADBEA，adaptivedynamicbandwidthearly allocation)算法[12,13]，ADBEA算法不是根據(jù)最小帶寬而是根據(jù)一個(gè)動(dòng)態(tài)變化的門(mén)限值，對(duì)接入終端進(jìn)行授權(quán)，對(duì)于超過(guò)門(mén)限值的帶寬，下一個(gè)周期進(jìn)行分配，當(dāng)系統(tǒng)負(fù)載較低時(shí)，輪詢(xún)周期較短，可以改進(jìn)系統(tǒng)的時(shí)延性能，當(dāng)系統(tǒng)負(fù)載較高時(shí)，輪詢(xún)周期會(huì)相應(yīng)加長(zhǎng)，減少了終端間的保證時(shí)隙，提高系統(tǒng)的利用率，而門(mén)限值的確定，依據(jù)業(yè)務(wù)的最大時(shí)延需求確定，從而保證在系統(tǒng)負(fù)載較高時(shí)，仍能滿(mǎn)足業(yè)務(wù)的時(shí)延需求。

上述算法解決了帶寬分配的QoS支持問(wèn)題，但是，上述算法均存在著若干缺陷，有待改進(jìn)。首先，鏈路的帶寬利用率有所下降，當(dāng)系統(tǒng)帶寬在滿(mǎn)足各接入終端的請(qǐng)求后還有剩余帶寬時(shí)無(wú)法繼續(xù)使用；其次，由于授權(quán)的集中進(jìn)行，局端必須在收到本輪所有請(qǐng)求后才能進(jìn)行下一輪的授權(quán)，這樣會(huì)導(dǎo)致在局端引入一部分等待延時(shí)；另外，更重要的是這些算法沒(méi)有考慮到實(shí)際網(wǎng)絡(luò)使用環(huán)境中帶寬分配的變化對(duì)系統(tǒng)造成的負(fù)載和時(shí)延增加問(wèn)題。

針對(duì)動(dòng)態(tài)帶寬分配問(wèn)題，同時(shí)考慮到QoS的支持，為了適當(dāng)?shù)販p少因帶寬切換造成的實(shí)際影響，提出了一種支持QoS的多鏈路最小變換動(dòng)態(tài)帶寬分配方法MCDBA，該方法的主要思想是根據(jù)不同的優(yōu)先級(jí)為不同QoS需求的業(yè)務(wù)分配帶寬，為提高系統(tǒng)整體的帶寬利用率，將剩余帶寬進(jìn)行重分配，同時(shí)加入時(shí)延及帶寬利用率QoS限制，減少帶寬切換對(duì)系統(tǒng)造成的不穩(wěn)定性。

2 帶寬分配問(wèn)題描述

支持QoS的DBA算法在帶寬分配架構(gòu)上通常是基于節(jié)點(diǎn)型的[14]，首先為每個(gè)接入點(diǎn)分配一塊帶寬，再在接入點(diǎn)帶寬內(nèi)根據(jù)各業(yè)務(wù)的需求為各業(yè)務(wù)分配帶寬。

2.1 帶寬分配體系結(jié)構(gòu)

如圖1所示，在基于節(jié)點(diǎn)型的DBA中，中央控制節(jié)點(diǎn)根據(jù)接入點(diǎn)上報(bào)的請(qǐng)求帶寬，按照某種分配原則為每個(gè)接入點(diǎn)分配一定數(shù)量的帶寬，在每個(gè)接入點(diǎn)內(nèi)，再由調(diào)度器負(fù)責(zé)把所獲得的帶寬分配給各類(lèi)業(yè)務(wù)，在這種帶寬分配方式中，中央控制節(jié)點(diǎn)僅僅分配給每個(gè)接入點(diǎn)總的帶寬，接入點(diǎn)自行決定如何把分到的帶寬在各個(gè)業(yè)務(wù)優(yōu)先級(jí)隊(duì)列之間進(jìn)行二次分配。

圖1 基于節(jié)點(diǎn)型的DBA

基于節(jié)點(diǎn)型的DBA中的隊(duì)列調(diào)度算法，其實(shí)質(zhì)就是基于Diffserv模型的隊(duì)列調(diào)度算法。國(guó)內(nèi)外對(duì)這方面的研究經(jīng)歷了相當(dāng)長(zhǎng)的時(shí)間，涌現(xiàn)出了很多成熟的調(diào)度算法，比如先到先服務(wù)、通用處理機(jī)共享、優(yōu)先級(jí)調(diào)度、循環(huán)調(diào)度以及隨機(jī)調(diào)度等[15]。但是，該架構(gòu)下的動(dòng)態(tài)帶寬分配存在帶寬利用率不高、不能對(duì)全網(wǎng)進(jìn)行統(tǒng)一控制等問(wèn)題。

由于在實(shí)際的網(wǎng)絡(luò)使用環(huán)境中QoS類(lèi)別相對(duì)較少和中央控制節(jié)點(diǎn)有較高的處理能力，因此設(shè)計(jì)了如圖2所示的基于業(yè)務(wù)型的DBA架構(gòu)，該架構(gòu)由中央控制節(jié)點(diǎn)集中控制整個(gè)系統(tǒng)，各終端通過(guò)邏輯鏈路連接到某接入點(diǎn)，首先，在系統(tǒng)中計(jì)算某業(yè)務(wù)所能獲得的總帶寬，然后在該業(yè)務(wù)帶寬內(nèi)對(duì)每個(gè)接入點(diǎn)分配帶寬，接入點(diǎn)通過(guò)反饋幀向中央控制節(jié)點(diǎn)報(bào)告它所有優(yōu)先級(jí)隊(duì)列的隊(duì)列長(zhǎng)度，該架構(gòu)便于對(duì)全局進(jìn)行統(tǒng)一控制，適用于核心交換機(jī)。

圖2 基于業(yè)務(wù)型的DBA

2.2 動(dòng)態(tài)帶寬分配方法

在實(shí)際的網(wǎng)絡(luò)使用環(huán)境中，業(yè)務(wù)的帶寬需求是不斷變化的，往往會(huì)造成網(wǎng)絡(luò)流量的突發(fā)，如圖3所示，在帶寬充足的環(huán)境下記錄的某業(yè)務(wù)在某段時(shí)間內(nèi)的流量情況，即帶寬需求。圖4和圖5表示的靜態(tài)帶寬分配算法SBA，在圖4所示的最大靜態(tài)帶寬分配方法下，雖然數(shù)據(jù)分組的時(shí)延會(huì)較小，但是會(huì)導(dǎo)致系統(tǒng)總帶寬利用率下降，若采用圖5所示的平均靜態(tài)帶寬分配方法，系統(tǒng)總帶寬利用率會(huì)提高，但是數(shù)據(jù)分組的時(shí)延會(huì)明顯增大。

圖6所示的是大部分常用的動(dòng)態(tài)帶寬分配方法，這些方法主要是根據(jù)帶寬請(qǐng)求動(dòng)態(tài)地分配帶寬，但是，在實(shí)際的網(wǎng)絡(luò)環(huán)境中，改變帶寬的分配會(huì)花費(fèi)系統(tǒng)更多的時(shí)間去完成，反而導(dǎo)致數(shù)據(jù)分組時(shí)延的增大[16]，過(guò)多的帶寬分配變換會(huì)成為系統(tǒng)的一個(gè)重要負(fù)擔(dān)。如圖7所示，本文算法的主要目的就是在保證一定QoS限制的前提下，減少帶寬分配的切換，達(dá)到盡量降低對(duì)系統(tǒng)的影響。

圖3～圖6中的細(xì)線代表帶寬需求，粗線代表分配的帶寬。

圖3 某業(yè)務(wù)帶寬需求

圖4 最大SBA

圖5 平均SBA

圖6 基于帶寬請(qǐng)求的DBA

圖7 最小變換DBA

3 支持QoS的動(dòng)態(tài)帶寬分配理論分析

3.1 符號(hào)約定

設(shè)多鏈路接入系統(tǒng)內(nèi)共有i個(gè)終端接入點(diǎn)，φi為接入點(diǎn)i的權(quán)重，由于本文側(cè)重研究算法對(duì)QoS的支持，所以在這里假設(shè)每個(gè)接入點(diǎn)的權(quán)重相等，并且φi滿(mǎn)足

實(shí)際的網(wǎng)絡(luò)數(shù)據(jù)中包含語(yǔ)音、視頻、數(shù)據(jù)等各種業(yè)務(wù)流，某些業(yè)務(wù)可能用于低時(shí)延，需要一定的穩(wěn)定帶寬保證，因此被分配較高權(quán)重；某些普通數(shù)據(jù)業(yè)務(wù)對(duì)時(shí)延、分組丟失不敏感，無(wú)特殊QoS要求，因此，可能被分配較低權(quán)重。假設(shè)系統(tǒng)支持m類(lèi)業(yè)務(wù)，ωj為j類(lèi)業(yè)務(wù)所能獲得的保證權(quán)重，并且ωj滿(mǎn)足條件

為了便于討論，各符號(hào)定義如表1所示。

表1 符號(hào)定義

3.2 問(wèn)題描述

QoS的支持通常希望端到端的時(shí)延最小，系統(tǒng)帶寬利用率最高，數(shù)據(jù)分組丟失率最小，系統(tǒng)負(fù)載最輕，但這些目標(biāo)的最優(yōu)值往往不能同時(shí)達(dá)到。因此，帶寬分配優(yōu)化問(wèn)題可以從其中的一個(gè)或部分參數(shù)去處理。

定義1系統(tǒng)總帶寬容量為所有接入點(diǎn)分配到的帶寬之和，即所有接入點(diǎn)中各類(lèi)業(yè)務(wù)已分配帶寬和可用剩余帶寬之和，可得

定義2接入點(diǎn)初始帶寬為系統(tǒng)的總帶寬與接入點(diǎn)權(quán)重的乘積，即

定義3重負(fù)載接入點(diǎn)集合為接入點(diǎn)中各業(yè)務(wù)帶寬需求總和大于該接入點(diǎn)的初始帶寬的接入點(diǎn)集合，即滿(mǎn)足

定義4輕負(fù)載接入點(diǎn)集合為接入點(diǎn)中各業(yè)務(wù)帶寬需求總和小于或等于該接入點(diǎn)的初始帶寬的接入點(diǎn)集合，即滿(mǎn)足

3.3 支持QoS的動(dòng)態(tài)帶寬分配計(jì)算

假設(shè)j類(lèi)業(yè)務(wù)所能獲得的保證權(quán)重大于j+1類(lèi)業(yè)務(wù)，因此，對(duì)于j+1類(lèi)業(yè)務(wù)來(lái)說(shuō)，要先完成j類(lèi)業(yè)務(wù)的帶寬分配，然后才能再對(duì)j+1類(lèi)業(yè)務(wù)進(jìn)行帶寬分配。

假設(shè)系統(tǒng)在第T個(gè)輪詢(xún)周期，在這個(gè)周期里，首先為j類(lèi)(j=1)業(yè)務(wù)分配帶寬。對(duì)于某接入點(diǎn)APi的j類(lèi)業(yè)務(wù)，在該輪詢(xún)周期開(kāi)始時(shí)所分配的帶寬為

對(duì)于j類(lèi)業(yè)務(wù)未獲得全部需求帶寬的接入點(diǎn)，將剩余帶寬按照以下方法重新進(jìn)行分配。

1)當(dāng)系統(tǒng)內(nèi)的剩余的帶寬大于或者等于不足帶寬即Bresidual≥Black時(shí)，說(shuō)明此時(shí)系統(tǒng)能滿(mǎn)足j類(lèi)業(yè)務(wù)的帶寬需求，因此，剩余的系統(tǒng)帶寬將被分別分配到各個(gè)接入點(diǎn)，由接入點(diǎn)將帶寬分配給各自的j類(lèi)業(yè)務(wù)，即

2)若系統(tǒng)內(nèi)的剩余的帶寬小于不足帶寬即Bresidual＜Black時(shí)，則說(shuō)明此時(shí)系統(tǒng)帶寬不能滿(mǎn)足j類(lèi)業(yè)務(wù)的帶寬需求，系統(tǒng)剩余帶寬Bresidual將按一定比例分配給重負(fù)載的接入點(diǎn)。

這樣，在該周期中，完成對(duì)j類(lèi)業(yè)務(wù)的帶寬分配。

對(duì)于j+1類(lèi)業(yè)務(wù)的帶寬分配，首先要計(jì)算已經(jīng)分配到帶寬的1到j(luò)類(lèi)業(yè)務(wù)的總和，然后在分配j+ 1 類(lèi)業(yè)務(wù)帶寬之前重新初始化，因此可得

4 MCDBA算法

由2.2節(jié)的說(shuō)明可知，在實(shí)際的網(wǎng)絡(luò)環(huán)境中，帶寬分配的改變往往會(huì)使系統(tǒng)花費(fèi)更多的時(shí)間去完成，不但沒(méi)有降低數(shù)據(jù)分組的時(shí)延，反而會(huì)導(dǎo)致數(shù)據(jù)分組時(shí)延的增大，過(guò)多的帶寬切換會(huì)成為系統(tǒng)的一個(gè)重要負(fù)擔(dān)，因此在本節(jié)設(shè)計(jì)一個(gè)算法，該算法控制帶寬分配的切換次數(shù)。

4.1 MCDBA算法設(shè)計(jì)

為了說(shuō)明MCDBA算法，新定義2個(gè)QoS變量Qd和Qu，其中Qd為QoS限制的時(shí)延上限，它表示系統(tǒng)內(nèi)所有數(shù)據(jù)分組的平均時(shí)延不能超過(guò)該值；Qu為QoS限制的系統(tǒng)總帶寬利用率下限，它表示系統(tǒng)的總帶寬利用率不能低于該值。顯然，Qd由業(yè)務(wù)數(shù)據(jù)分組的平均時(shí)延確定，當(dāng)Qd變小時(shí)，數(shù)據(jù)分組的時(shí)延會(huì)減少；Qu由系統(tǒng)帶寬利用率限制確定，當(dāng)Qu變高時(shí)，會(huì)使系統(tǒng)整體帶寬利用率上升。

4.2 MCDBA算法描述及步驟

在MCDBA算法中，通過(guò)Qd和Qu這2個(gè)參數(shù)控制帶寬分配的變換。設(shè)在周期T中，按照3.3節(jié)的計(jì)算方法對(duì)各接入點(diǎn)和各業(yè)務(wù)進(jìn)行帶寬分配，若在該周期內(nèi)，能夠滿(mǎn)足Qd和Qu，那么在下一個(gè)周期T+1中，將不進(jìn)行帶寬分配變換，避免因帶寬分配變換造成的隊(duì)列調(diào)整和系統(tǒng)負(fù)載，否則在下一個(gè)周期T+1中，在等待前一周期的數(shù)據(jù)全部發(fā)送完畢后，啟用CONVERSION操作。在CONVERSION操作過(guò)程中等被重新設(shè)置，MCDBA算法描述及步驟具體如下。

算法說(shuō)明：

1)QoS限制參數(shù)Qd和Qu可以在實(shí)際使用過(guò)程中根據(jù)系統(tǒng)狀況動(dòng)態(tài)調(diào)整；

3)先處理所有接入點(diǎn)中的高優(yōu)先級(jí)業(yè)務(wù)帶寬請(qǐng)求，通過(guò)判斷不足帶寬和剩余帶寬計(jì)算需分配帶寬的大??；

4)帶寬分配變換可以是部分接入點(diǎn)。

5 實(shí)驗(yàn)及性能分析

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

在實(shí)驗(yàn)測(cè)試中，采用OPNET Modeler仿真工具搭建了網(wǎng)絡(luò)測(cè)試環(huán)境，并進(jìn)行仿真測(cè)試。仿真實(shí)驗(yàn)環(huán)境包括一個(gè)中央控制節(jié)點(diǎn)，100個(gè)接入點(diǎn)，由此產(chǎn)生100條鏈路，并且假設(shè)鏈路的長(zhǎng)度為5 km，各鏈路的固定傳輸時(shí)延均為3 ms，鏈路的最大帶寬為100 Mbit/s，系統(tǒng)可供分配的總帶寬為1 Gbit/s，具體的仿真實(shí)驗(yàn)參數(shù)如表2所示。

表2 仿真實(shí)驗(yàn)參數(shù)

假設(shè)系統(tǒng)產(chǎn)生的流量包含3種業(yè)務(wù)流量，其中最高優(yōu)先級(jí)的EF數(shù)據(jù)流對(duì)應(yīng)語(yǔ)音業(yè)務(wù)，是固定比特速率的數(shù)據(jù)流，該類(lèi)業(yè)務(wù)流必須保證有較小的時(shí)延和時(shí)延抖動(dòng)；中等優(yōu)先級(jí)的AF數(shù)據(jù)流對(duì)應(yīng)視頻業(yè)務(wù)是可變比特速率的，該類(lèi)業(yè)務(wù)需要有一定帶寬保證；最低優(yōu)先級(jí)的BE數(shù)據(jù)流對(duì)應(yīng)數(shù)據(jù)傳輸業(yè)務(wù)對(duì)時(shí)延和抖動(dòng)沒(méi)有要求，需要提供盡力而為的服務(wù)。在實(shí)驗(yàn)中假設(shè)以上業(yè)務(wù)流數(shù)據(jù)分組的大小為64～1 518 byte之間平均分布，并且分別被隨機(jī)分配到各條鏈路。

為評(píng)估MCDBA算法的性能，本文對(duì)比的算法為平均靜態(tài)帶寬分配算法SBA、不支持QoS的周期自適應(yīng)交叉輪詢(xún)算法IPACT、支持QoS的EBDBA和ADBEA算法，對(duì)以上算法的不同業(yè)務(wù)分組時(shí)延和帶寬利用率進(jìn)行對(duì)比測(cè)試。

5.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)中鏈路的端到端時(shí)延主要由兩部分組成：從中央控制節(jié)點(diǎn)到接入點(diǎn)的固定傳輸時(shí)延和數(shù)據(jù)分組在接入點(diǎn)緩沖隊(duì)列中的排隊(duì)時(shí)延，其中傳輸時(shí)延由鏈路的長(zhǎng)度確定，它是一個(gè)固定值，在本實(shí)驗(yàn)中假設(shè)其為3 ms；排隊(duì)時(shí)延的大小則主要由調(diào)度算法來(lái)確定，它反映了算法的性能。圖8～圖10所示為各種業(yè)務(wù)分組在5種帶寬分配算法控制下的平均時(shí)延變化情況。

由于在開(kāi)始階段系統(tǒng)負(fù)載較小，并且存在足夠的可用帶寬，接入點(diǎn)的各種業(yè)務(wù)能得到足夠的帶寬分配，因此，各業(yè)務(wù)分組的平均時(shí)延相差不大；由圖8可以看出，隨著系統(tǒng)負(fù)載的增加，EF業(yè)務(wù)分組的時(shí)延開(kāi)始出現(xiàn)較大不同。對(duì)于SBA，由于不能借用其他低優(yōu)先級(jí)業(yè)務(wù)的帶寬，當(dāng)負(fù)載超過(guò)60%的時(shí)候，EF業(yè)務(wù)的時(shí)延超過(guò)了50 ms，并且時(shí)延出現(xiàn)增長(zhǎng)趨勢(shì)；IPACT的交叉輪詢(xún)策略對(duì)于降低業(yè)務(wù)的時(shí)延有一定的作用，但是在處理EF業(yè)務(wù)上，分組的平均時(shí)延相比EBDBA與ADBEA，仍然高出約23%和34%；由于MCDBA先處理高優(yōu)先級(jí)的業(yè)務(wù)，所以EF業(yè)務(wù)平均分組時(shí)延較其他4種算法有較大的降低。圖9表示的是各算法的AF業(yè)務(wù)平均分組時(shí)延，由該圖明顯可以看出，SBA的時(shí)延最大，但是對(duì)于AF業(yè)務(wù)，IPACT、EBDBA、ADBEA與MCDBA的平均時(shí)延則相差不大。圖10表示的是各算法的BE業(yè)務(wù)平均分組時(shí)延，SBA的BE業(yè)務(wù)時(shí)延最大時(shí)延達(dá)到約70 ms，與EF、AF業(yè)務(wù)基本相同；由于ADBEA的門(mén)限值可以動(dòng)態(tài)變化，對(duì)于低優(yōu)先級(jí)BE業(yè)務(wù)，在這5種算法中ADBEA顯示出最好的性能；由于MCDBA算法的優(yōu)先級(jí)順序原因，對(duì)于BE業(yè)務(wù)，MCDBA和IPACT的性能差不多，但是時(shí)延分別比EBDBA與ADBEA高出約45%和26%，的MCDBA算法在處理低優(yōu)先級(jí)業(yè)務(wù)的性能仍有待改善。

圖8 EF業(yè)務(wù)平均分組時(shí)延

圖9 AF業(yè)務(wù)平均分組時(shí)延

圖10 BE業(yè)務(wù)平均分組時(shí)延

在測(cè)試各算法隊(duì)列長(zhǎng)度和分組丟失率的實(shí)驗(yàn)中，設(shè)定各接入點(diǎn)隊(duì)列緩沖區(qū)的大小為1×106byte，超過(guò)緩沖區(qū)大小的分組將被丟棄。圖11和圖12反映的是接入點(diǎn)分組隊(duì)列長(zhǎng)度和分組丟失率的情況?？梢钥闯觯S著系統(tǒng)負(fù)載的增加，接入點(diǎn)隊(duì)列緩沖區(qū)最先填滿(mǎn)的是SBA，開(kāi)始出現(xiàn)大量分組丟失的情況；當(dāng)系統(tǒng)負(fù)載達(dá)到約60%的時(shí)候，IPACT和EBDBA出現(xiàn)分組丟失，并且最高分組丟失率達(dá)到約40%；由于在系統(tǒng)負(fù)載較高時(shí)，ADBEA輪詢(xún)周期可以相應(yīng)加長(zhǎng)，MCDBA的剩余帶寬可以重新分配，因此，重負(fù)載情況下，ADBEA和MCDBA的性能表現(xiàn)較好，直到系統(tǒng)負(fù)載超過(guò)了約75%才出現(xiàn)隊(duì)列緩沖滿(mǎn)和分組丟失的情況，并且最大分組丟失率不超過(guò)25%。

圖11 接入點(diǎn)分組隊(duì)列長(zhǎng)度

圖12 接入點(diǎn)分組丟失率

5種算法控制下系統(tǒng)帶寬利用率如圖13所示，由圖13可以看出，隨著系統(tǒng)負(fù)載的增加，各算法的系統(tǒng)帶寬利用率都有持續(xù)的上升。由于IPACT算法輪詢(xún)周期是不固定，在系統(tǒng)負(fù)載較輕時(shí)，浪費(fèi)了不少的帶寬，導(dǎo)致輕負(fù)載時(shí)其性能與SBA差不多，但是隨著系統(tǒng)負(fù)載的增加，IPACT的系統(tǒng)帶寬利用率比SBA有較大的提高；ADBEA比EBDBA在系統(tǒng)帶寬利用率方面約有8%的提高，并且在重負(fù)載時(shí)最高帶寬利用率比MCDBA高約6%；但是，該圖也反映出在系統(tǒng)輕負(fù)載時(shí)，MCDBA較其他4種算法有較大優(yōu)勢(shì)的系統(tǒng)帶寬利用率。

圖13 系統(tǒng)平均帶寬利用率

6 結(jié)束語(yǔ)

本文研究了帶寬分配方法和帶寬分配體系結(jié)構(gòu)，提出一種支持QoS的最少變換動(dòng)態(tài)帶寬分配算法MCDBA，該算法支持多業(yè)務(wù)，利用剩余帶寬重新分配提高了系統(tǒng)帶寬利用率，并且通過(guò)QoS參數(shù)限制減少了帶寬變換頻率，解決了實(shí)際網(wǎng)絡(luò)使用中因帶寬變換造成的時(shí)延和系統(tǒng)負(fù)載增加，仿真實(shí)驗(yàn)證明該算法對(duì)于系統(tǒng)性能有一定的提高。

此外，對(duì)于大規(guī)模網(wǎng)絡(luò)鏈路環(huán)境，下一步的研究工作重點(diǎn)是對(duì)提出的MCDBA算法進(jìn)行接入點(diǎn)分區(qū)策略，對(duì)于主要承載不同業(yè)務(wù)的接入點(diǎn)，為了減少系統(tǒng)負(fù)載，對(duì)接入點(diǎn)進(jìn)行分區(qū)，每個(gè)分區(qū)分別計(jì)算自己分區(qū)內(nèi)主要承載業(yè)務(wù)的綜合性能最優(yōu)QoS限制，從而獲得更佳的全網(wǎng)帶寬分配。

[1] 林闖,李寅,萬(wàn)劍雄.計(jì)算機(jī)網(wǎng)絡(luò)服務(wù)質(zhì)量?jī)?yōu)化方法研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2011,34(1):1-14.LIN C,LI Y,WAN J X.Optimization approaches for QoS in computer networks:a survey[J].Chinese Journal of Computers,2011,34(1):1-14.

[2]TOMKOS I,KAZOVSKY L,KITAYAMA K I.Next-generation optical access networks:dynamic bandwidth allocation,resource use optimization,and QoS improvements[J].Network,IEEE,2012,26(2):4-6.

[3] 徐戰(zhàn),王勁林,吳剛等.業(yè)務(wù)質(zhì)量約束下最大化收益的HFC頻點(diǎn)帶寬分配方法[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(6):1223-1227.XU Z,WANG J L,WU G,et al.HFC frequency bandwidth allocation method based on constraints of QoS and maximum revenue[J].Journal of Chinese Computer Systems,2012,33(6):1223-1227.

[4] ZHENG J,MOUFTAH H T.A survey of dynamic bandwidth allocation algorithms for ethernet passive optical networks[J].Optical Switching and Networking,2009,6(3):151-162.

[5] 張晉豫,劉犁.基于效用EPON分布式動(dòng)態(tài)帶寬分配實(shí)現(xiàn)機(jī)制[J].軟件學(xué)報(bào),2008,19(7):1693-1706.ZHANG J Y,LIU L.Implement mechanism on distributed EPON DBAbased on utility[J].Journal of Software,2008,19(7):1693-1706.

[6] 張耀東,王鉞,霍金海等.基于業(yè)務(wù)認(rèn)知的多用戶(hù)帶寬分配方法[J].通信學(xué)報(bào),2013,34(2):109-116.ZHANG Y D,WANG Y,HUO J H,et al.Multi-user bandwidth allocation method based on traffic cognition[J]. Journal on Communications,2013,34(2):109-116.

[7] SONG H,KIM B W,MUKERJEE B.Long-reach optical access networks:a survey of research challenges,demonstrations,and bandwidth assignment mechanisms[J].IEEE Communications Surveys&Tutorials 2010,12(l):112-123.

[8]KRAMER G,MUKHERJEE B,ESAVENTO G.Interleaved polling with adaptive cycle time(IPACT):a dynamic bandwidth distribution scheme in an optical access network[J]. Photon Network Communication,2002,4(1):89-107.

[9] ZHU Y Q,MA M D.IPACT with grant estimation(IPACT-GE)seheme for ethernet passive optical networks[J].Journal of Lightwave Technology,2008,26(14):2055-2063.

[10]YEOUL S,LEE S H,LEE T J,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.

[11]LIM W S,YUN C H,YANG Y M,et al.Burst-polling-based dynamic bandwidth allocation using adaptive minimum guaranteed bandwidth for EPONs[J].Journal Optical Communication Network,2009,1(7):594-599.

[12]汪學(xué)舜,余少華,羅婷等.自適應(yīng)門(mén)限的EPON動(dòng)態(tài)帶寬分配實(shí)現(xiàn)[J].軟件學(xué)報(bào),2012,23(3):724-734.WANG X S,YU S H,LUO T,et al.Dynamic bandwidth allocation with adaptive threshold in EPON[J].Journal of Software,2012,23(3):724-734.

[13]汪學(xué)舜,余少華,戴錦友.新穎的WDMEPON動(dòng)態(tài)帶寬調(diào)度算法[J].通信學(xué)報(bào),2012,33(2):69-75.WANG X S,YU S H,DAI J Y.Novel algorithm for dynamic bandwidth scheduling in WDM EPON[J].Journal on Communications,2012,33(2):69-75.

[14]CALINESCU R,GRUNSKE L,KWIATKOWSKA M,et al.Dynamic QoS management and optimization in service-based systems[J].IEEE Transactions on Software Engineering,2011,37(3):387-409.

[15]ZHAO H,NIU W,QIN Y,et al.Traffic load-based dynamic bandwidth allocation for balancing the packet loss in DiffServ network[A].Computer and Information Science(ICIS),2012 IEEE/ACIS 11th International Conference on[C].IEEE,2012.99-104.

[16]ESMAILPOUR A,NASSER N.Dynamic QoS-based bandwidth allocation framework for broadband wireless networks[J].IEEE Transactions on Vehicular Technology,2011,60(6):2690-2700.