一種費(fèi)用最優(yōu)令牌緩沖流量調(diào)度負(fù)載控制方法*

郭小雪 ，梁活民 ，袁 奕

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

網(wǎng)絡(luò)各種新業(yè)務(wù)帶動(dòng)Internet迅速發(fā)展的同時(shí)，也產(chǎn)生了大量流量，給網(wǎng)絡(luò)造成了極大的壓力，這就要求網(wǎng)絡(luò)管理者必須有效地提高網(wǎng)絡(luò)資源的利用率以滿足日益增長(zhǎng)的業(yè)務(wù)量需求。流量工程就是在這種背景下提出的一種用來監(jiān)測(cè)網(wǎng)絡(luò)狀態(tài)，控制網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)性能，滿足各種業(yè)務(wù)需求的網(wǎng)絡(luò)技術(shù)[1]。從定義上它涵括了對(duì)網(wǎng)絡(luò)進(jìn)行監(jiān)測(cè)、分類、建模和控制的科學(xué)原理和工程應(yīng)用，以及用于實(shí)現(xiàn)特定目標(biāo)的原理和技術(shù)。流量工程的實(shí)質(zhì)是對(duì)網(wǎng)絡(luò)性能進(jìn)行分析和實(shí)施優(yōu)化。從網(wǎng)絡(luò)管理者的角度，實(shí)施流量工程可以保證網(wǎng)絡(luò)資源的合理利用和網(wǎng)絡(luò)性能的優(yōu)化；從用戶的角度，實(shí)施流量工程可以更好地保證用戶的服務(wù)質(zhì)量。因此，實(shí)施流量工程對(duì)IP網(wǎng)絡(luò)，尤其是公共Internet骨干網(wǎng)是非常必要的[2]。

流量控制和資源分配技術(shù)是互聯(lián)網(wǎng)QoS保證的重要基礎(chǔ)[3]，不同網(wǎng)絡(luò)環(huán)境下的流量控制和資源分配技術(shù)有不同的特點(diǎn)。當(dāng)前互聯(lián)網(wǎng)采用的很多流量控制方法在效率、系統(tǒng)優(yōu)化以及公平性保障等方面存在著較大的缺點(diǎn)和不足。而優(yōu)化流量控制則基于擁塞計(jì)費(fèi)技術(shù)，借鑒微觀經(jīng)濟(jì)學(xué)原理，利用價(jià)格桿杠的調(diào)節(jié)作用使系統(tǒng)達(dá)到優(yōu)化狀態(tài)，并可實(shí)現(xiàn)用戶之間資源共享的比例公平性，是一種較好的流量控制和資源分配方法[4]。

1相關(guān)研究

最近很多研究提出的優(yōu)化流量控制機(jī)制借鑒了微觀經(jīng)濟(jì)學(xué)原理，通過效用函數(shù)的形式來表示用戶的帶寬需求，網(wǎng)絡(luò)以用戶效用函數(shù)的總和作為優(yōu)化的目標(biāo)函數(shù)[5]。網(wǎng)絡(luò)根據(jù)當(dāng)前的擁塞狀況不斷向用戶反饋擁塞費(fèi)用，用戶在利益的驅(qū)動(dòng)下，根據(jù)反饋的費(fèi)用不斷調(diào)整用戶速率，最后達(dá)到系統(tǒng)優(yōu)化的均衡狀態(tài)[6]。

[7]把微觀經(jīng)濟(jì)學(xué)方法引入網(wǎng)絡(luò)資源分配領(lǐng)域，分析了基于微觀經(jīng)濟(jì)學(xué)方法的網(wǎng)絡(luò)資源分配研究最新進(jìn)展，介紹了網(wǎng)絡(luò)資源分配的典型經(jīng)濟(jì)模型，研究了各種定價(jià)策略，并分析與網(wǎng)絡(luò)資費(fèi)相關(guān)的若干問題，最后研究基于價(jià)格的通信協(xié)議實(shí)現(xiàn)，為這一領(lǐng)域的研究提出了新思路。參考文獻(xiàn)[8]通過改變無向網(wǎng)絡(luò)流最小費(fèi)用問題的描述，借助Floyd算法思想，給出了一種求解無向網(wǎng)絡(luò)流最小費(fèi)用問題的算法，該算法具有路徑標(biāo)記功能，可以自動(dòng)生成費(fèi)用修正回路，并且適用于有向網(wǎng)絡(luò)流最小費(fèi)用問題。參考文獻(xiàn)[9]基于博弈論方法提出了一種不依賴于端系統(tǒng)用戶合作的IP網(wǎng)絡(luò)流速率控制框架，將網(wǎng)絡(luò)中的流量源模型化為網(wǎng)絡(luò)博弈中的局中人，競(jìng)爭(zhēng)共享網(wǎng)絡(luò)帶寬資源，通過一種有效的帶寬使用定價(jià)與收費(fèi)機(jī)制，使博弈的Nash均衡解達(dá)到全局最優(yōu)，得到有效與公平的網(wǎng)絡(luò)帶寬分配。

實(shí)現(xiàn)技術(shù)中常用的令牌緩沖調(diào)度方法是固定周期令牌緩沖調(diào)度方法[10-11]FCTB(Fixed Cycle Token Buffer)，F(xiàn)CTB根據(jù)當(dāng)前時(shí)間與上次添加令牌的時(shí)間內(nèi)使用的令牌總數(shù)量往緩沖池內(nèi)添加令牌，并且是一次性添加完畢，沒有分段添加。本文設(shè)計(jì)了一種多鏈路共享令牌緩沖池流量調(diào)度模型，研究了多鏈路令牌調(diào)度費(fèi)用計(jì)算，基于費(fèi)用最優(yōu)研究了令牌緩沖流量調(diào)度負(fù)載計(jì)算方法COTB(Cost Optimization Token Buffer)，并且通過實(shí)驗(yàn)與FCTB比較，證明了本文方法有較好的流量調(diào)度能力，能有效地控制鏈路的流量，改善系統(tǒng)負(fù)載均衡。

2基于時(shí)延反饋的流量擁塞控制模型

2.1多鏈路共享令牌流量調(diào)度模型

多鏈路共享會(huì)牌流量調(diào)度模型如圖1所示。假設(shè)某個(gè)系統(tǒng)中包含有N條邏輯鏈路，系統(tǒng)首先為每個(gè)進(jìn)入系統(tǒng)的鏈路分配一個(gè)隊(duì)列，各個(gè)鏈路的數(shù)據(jù)到達(dá)系統(tǒng)后，在各自的隊(duì)列里進(jìn)行排隊(duì)整形，經(jīng)過排隊(duì)整形后再依次被送到共享令牌緩沖池。緩沖池在某個(gè)固定的時(shí)間間隔內(nèi)產(chǎn)生一定的令牌，令牌是一種虛擬的資源，每個(gè)令牌代表允許通過一個(gè)最大的數(shù)據(jù)長(zhǎng)度。共享令牌緩沖池中的令牌總數(shù)量表示當(dāng)前系統(tǒng)允許通過的最大數(shù)據(jù)量，數(shù)據(jù)發(fā)送時(shí)將消耗令牌，令牌降到一定的數(shù)量后要重新申請(qǐng)加入補(bǔ)充令牌，流控實(shí)體可以通過控制共享令牌緩沖池令牌數(shù)量的存儲(chǔ)對(duì)流量和系統(tǒng)負(fù)載進(jìn)行控制。

費(fèi)用指某動(dòng)作或某狀態(tài)所消耗的系統(tǒng)資源。對(duì)網(wǎng)絡(luò)服務(wù)的計(jì)費(fèi)要以占用的系統(tǒng)資源為基準(zhǔn)，系統(tǒng)資源包括帶寬資源、緩沖隊(duì)列管理資源和CPU時(shí)間片資源等多種資源，網(wǎng)絡(luò)服務(wù)通過對(duì)各種資源的使用來為用戶提供服務(wù)質(zhì)量，當(dāng)對(duì)系統(tǒng)的某種資源出現(xiàn)競(jìng)爭(zhēng)時(shí)，費(fèi)用計(jì)算就必須要考慮多種資源的聯(lián)合計(jì)算問題，這樣才能使費(fèi)用計(jì)算成為系統(tǒng)負(fù)載控制的有效手段。

2.2費(fèi)用最優(yōu)令牌緩沖流量負(fù)載計(jì)算方法

為了便于分析，首先對(duì)數(shù)據(jù)包在鏈路中的處理情況定義如下變量：

p1：每次共享令牌緩沖池申請(qǐng)?jiān)黾恿钆频馁M(fèi)用。

p2：令牌來到緩沖池后在里面進(jìn)行排隊(duì)處理的費(fèi)用，即每個(gè)單位時(shí)間每個(gè)令牌的儲(chǔ)存費(fèi)用。由定義可知緩沖池內(nèi)令牌越多其平均儲(chǔ)存費(fèi)用就越大。

p3：當(dāng)令牌緩沖池為空時(shí)，每個(gè)單位時(shí)間每條鏈路的等待費(fèi)用。

n：每單位時(shí)間的令牌消耗總量。

Q：申請(qǐng)加入緩沖池的令牌總量。

T：申請(qǐng)令牌加入緩沖池的時(shí)間間隔，即申請(qǐng)周期。

q：任意時(shí)刻t緩沖池內(nèi)的令牌的剩余儲(chǔ)存量。

申請(qǐng)費(fèi)用p1、平均儲(chǔ)存費(fèi)用p2及單位時(shí)間消耗量n均為已知常數(shù)。模型要以總平均費(fèi)用為目標(biāo)函數(shù)確定申請(qǐng)周期T和申請(qǐng)量Q的最優(yōu)值。

一般來說，令牌緩沖池存在著兩種狀態(tài)：非空和空。非空表示不允許緩沖池內(nèi)的令牌個(gè)數(shù)為0，當(dāng)令牌個(gè)數(shù)大于或等于0時(shí)就可以申請(qǐng)往緩沖池中增加令牌；可以為空時(shí)表示允許緩沖池內(nèi)的令牌個(gè)數(shù)等于0，當(dāng)?shù)扔?時(shí)系統(tǒng)處于等待狀態(tài)，不進(jìn)行流量發(fā)送，將產(chǎn)生一定的等待費(fèi)用。

(1)令牌緩沖池非空情況下的費(fèi)用計(jì)算

由模型假設(shè)可以得出，申請(qǐng)周期T、申請(qǐng)量Q與每隔T時(shí)刻消耗量n之間滿足如下關(guān)系：

由式(2)得每T時(shí)刻的平均費(fèi)用為：

因此，制定最優(yōu)費(fèi)用令牌調(diào)度策略歸結(jié)為求申請(qǐng)周期T使得 C(T)最小。

圖 2 q>=0情況下 q(t)變化規(guī)律

利用微分法可以求出T和Q的最優(yōu)值，分別記作 T′和 Q′：

并且根據(jù)式(1)代入求得：

(2)令牌緩沖池為空時(shí)的費(fèi)用計(jì)算

當(dāng)令牌緩沖池內(nèi)的所有令牌都使用完畢后，令牌的存儲(chǔ)數(shù)量為0，系統(tǒng)不進(jìn)行流量發(fā)送，并進(jìn)入等待申請(qǐng)令牌加入的狀態(tài)，等待時(shí)可以把令牌儲(chǔ)存量q視作負(fù)值，因此，q(t)的變化規(guī)律可以用圖3表示。

圖 3 q＜0情況下 q(t)變化規(guī)律

假設(shè)令牌在t=T1時(shí)刻全部用完，在一段時(shí)間內(nèi)令牌的存儲(chǔ)量為0，并且假設(shè)這時(shí)候令牌的消耗量仍然為n，在t=T時(shí)刻下一次令牌申請(qǐng)量q到達(dá)系統(tǒng)。于是由圖3可以得出：

模型的目標(biāo)函數(shù)仍為每單位時(shí)間的平均費(fèi)用。

把式(7)中的 T1用式(6)代入，可知平均費(fèi)用是 T和Q的二元函數(shù)，記作 P(T，Q)，且：

利用微分法可以求得：

若記：

則可以求得一個(gè)申請(qǐng)周期內(nèi)的最小平均費(fèi)用為：

當(dāng) T′>T時(shí) Q′>Q，即在允許令牌緩沖池為空的情況下申請(qǐng)周期應(yīng)增大，而申請(qǐng)數(shù)量應(yīng)減少。但當(dāng)?shù)却M(fèi)用p3越大時(shí)(相當(dāng)于平均儲(chǔ)存費(fèi)用 p2時(shí))，μ 越小，T′和 Q′就越接近 T和 Q。特別地，當(dāng) p3→∞ 時(shí)，μ→1，于是有T′→T、Q′→Q， 因?yàn)?p3→∞即等待造成的費(fèi)用無限大相當(dāng)于不允許令牌緩沖池為空。

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

3.1實(shí)驗(yàn)環(huán)境

本文在NS2上實(shí)現(xiàn)了費(fèi)用最優(yōu)令牌緩沖流量調(diào)度負(fù)載控制方法，并進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)使用的仿真網(wǎng)絡(luò)拓?fù)淙鐖D4所示。網(wǎng)絡(luò)拓?fù)溆砂l(fā)送端s1～s3、路由器R1～R5和接收端r1、r2組成，各節(jié)點(diǎn)間鏈路帶寬如圖4所示，各發(fā)送端通過虛擬撥號(hào)連接建立一條到接收端的邏輯鏈路，分別為L(zhǎng)1～L3，鏈路路徑如圖4虛線所示。本文在R3節(jié)點(diǎn)上對(duì)所建立的邏輯鏈路進(jìn)行共享令牌流量控制。

3.2實(shí)驗(yàn)結(jié)果對(duì)比分析

實(shí)驗(yàn)中采用的對(duì)比方法為常用的固定周期令牌緩沖調(diào)度策略FCTB，主要考察這兩種方法在相同出口流量的情況下的系統(tǒng)負(fù)載對(duì)比。

圖5 緩沖池非空時(shí)出口流量對(duì)比

在令牌緩沖池非空的情況下，通過這兩種調(diào)度方法造成出口流量差不多維持在同一水平上，大約為平均150 Mb/s，具體結(jié)果如圖5所示，然后進(jìn)行系統(tǒng)的負(fù)載數(shù)據(jù)采集，數(shù)據(jù)采集結(jié)果如圖6所示。從圖6可以看到，F(xiàn)CTB的最高系統(tǒng)負(fù)載為60.4%，最低為35.7%，平均系統(tǒng)負(fù)載為47.9%；COTB的最高系統(tǒng)負(fù)載為44.7%，最低為33.6%，平均系統(tǒng)負(fù)載為39.5%。造成FCTB比COTB系統(tǒng)負(fù)載高的原因主要是FCTB令牌緩沖池里面的未用到的剩余令牌較多，系統(tǒng)要花費(fèi)大量的資源去維護(hù)整理那些在緩沖區(qū)里面的令牌，COTB雖然因?yàn)槎啻紊暾?qǐng)令牌到緩沖池增加了一定的系統(tǒng)負(fù)載，但總的系統(tǒng)平均負(fù)載仍然較FCTB低許多。

實(shí)驗(yàn)加大出口流量時(shí)，由圖7可以看出，兩種調(diào)度方法的出口流量最高達(dá)到約 160 Mb/s，約 20 s后，令牌緩沖池內(nèi)的令牌使用完畢，出口流量迅速降到接近0，再用這兩種方法對(duì)緩沖池進(jìn)行令牌補(bǔ)充然后，出口流量得以恢復(fù)。由數(shù)據(jù)采集統(tǒng)計(jì)得到，F(xiàn)CTB平均流量為131.3 Mb/s，COTB平均流量為 133.2 Mb/s，兩者大致相同。系統(tǒng)負(fù)載數(shù)據(jù)結(jié)果如圖8所示，F(xiàn)CTB的最高系統(tǒng)負(fù)載為66.4%，最低為38.8%，平均系統(tǒng)負(fù)載為51.3%；COTB的最高系統(tǒng)負(fù)載為52.7%，最低為41.6%，平均系統(tǒng)負(fù)載為46.8%。雖然FCTB比COTB在某段時(shí)間內(nèi)的最低系統(tǒng)負(fù)載要低，但是平均系統(tǒng)負(fù)載仍然比COTB高出約4.5%。由此可見，COTB在平均系統(tǒng)負(fù)載、負(fù)載峰值、負(fù)載均衡等方面都比FCTB要好。

本文討論了多鏈路流量調(diào)度系統(tǒng)負(fù)載優(yōu)化問題，給出了基于共享令牌調(diào)度和流量調(diào)度負(fù)載均衡體系模型，提出了基于費(fèi)用最優(yōu)的令牌緩沖流量調(diào)度負(fù)載計(jì)算方法，并在廣東茂名學(xué)院校園網(wǎng)上成功地實(shí)現(xiàn)了上述方法和體系結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，增大了網(wǎng)絡(luò)通過量，降低了平均系統(tǒng)負(fù)載，鏈路在整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)里有良好的時(shí)間響應(yīng)特性，取得較好的應(yīng)用效果。

下一步主要工作是對(duì)更多QoS受限條件下的多鏈路流量調(diào)度問題，對(duì)具有不同優(yōu)先權(quán)請(qǐng)求的鏈路進(jìn)行區(qū)分以及基于處理節(jié)點(diǎn)計(jì)算能力的負(fù)載遷移等問題進(jìn)行研究。

參考文獻(xiàn)

[1]WANG H， XIE H Y， QIU L L.COPE：traffic engineering in dynamic networks[A].In：Proceedings of ACM SIGCOMM[J].Pisa， Italy：ACM ComputerCommunication Review，2006，36(4)：99-110.

[2]劉郁恒，陳廣文，胡嚴(yán)，等.一種在接收端實(shí)現(xiàn)的 TCPFriendly 擁 塞 控 制 機(jī) 制[J].電 子 學(xué) 報(bào) ，2005，33(5)：835-841.

[3]張桂英，吳學(xué)智.下一代寬帶接入網(wǎng) QoS研究[J].計(jì)算機(jī)應(yīng)用，2007，27(6)：174-176.

[4]武航星，慕德俊，潘文平，等.網(wǎng)絡(luò)擁塞控制算法綜述[J].計(jì)算機(jī)科學(xué)，2007，34(2)：51-56.

[5]黃啟萍.流量控制與 IP服務(wù)質(zhì)量[J].計(jì)算機(jī)工程，2006，32(11)：144-146

[6]葛敬國(guó)，馬宏偉，錢華林.Internet自治系統(tǒng)間負(fù)載均衡機(jī)制及其性能分析 [J].計(jì)算機(jī)應(yīng)用，2005，25(12)：2916-2917.

[7]陳曉梅，盧錫城，王懷民.基于微觀經(jīng)濟(jì)學(xué)方法的網(wǎng)絡(luò)資源分配研究[J].計(jì)算機(jī)研究與發(fā)展，2001，38(11)：1345-1353.

[8]付彤，郭強(qiáng).無向網(wǎng)絡(luò)流的最小費(fèi)用問題[J].計(jì)算機(jī)工程與 應(yīng) 用 ，2005(28)：88-90.

[9]鐘伯成，韓江洪.網(wǎng)絡(luò)速率控制的博弈模型[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，35(9)：85-89.

[10]涂文偉，張進(jìn)，張興明.分級(jí)統(tǒng)籌分配令牌參數(shù)的流量整形算法[J].計(jì)算機(jī)應(yīng)用，2006，26(9)：2175-2177.

[11]雷雯，許都，黃振華.以數(shù)據(jù)流特性為導(dǎo)向的令牌調(diào)度算法[J].電子科技大學(xué)學(xué)報(bào)，2005，34(6)：955-958.