摘 要： 為有效解決多鏈路共享令牌緩沖流量調(diào)度系統(tǒng)負(fù)載較高的問題，設(shè)計了一種多鏈路共享令牌緩沖池流量調(diào)度模型，提出“費用”指標(biāo)以更準(zhǔn)確地刻畫系統(tǒng)負(fù)載狀況，基于費用最優(yōu)研究了令牌緩沖流量調(diào)度負(fù)載控制方法。該方法包含了令牌緩沖池非空和可以為空這兩種情況下的具體計算過程，從而保證了該方法的全局完整性。通過仿真實驗與固定周期令牌緩沖調(diào)度方法進行比較，證明了本文方法有較好的流量調(diào)度能力，能有效地控制鏈路的流量，改善系統(tǒng)負(fù)載均衡。
關(guān)鍵詞： 流量調(diào)度；令牌緩沖；費用；周期；負(fù)載均衡
網(wǎng)絡(luò)各種新業(yè)務(wù)帶動Internet迅速發(fā)展的同時，也產(chǎn)生了大量流量，給網(wǎng)絡(luò)造成了極大的壓力，這就要求網(wǎng)絡(luò)管理者必須有效地提高網(wǎng)絡(luò)資源的利用率以滿足日益增長的業(yè)務(wù)量需求。流量工程就是在這種背景下提出的一種用來監(jiān)測網(wǎng)絡(luò)狀態(tài)，控制網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)性能，滿足各種業(yè)務(wù)需求的網(wǎng)絡(luò)技術(shù)[1]。從定義上它涵括了對網(wǎng)絡(luò)進行監(jiān)測、分類、建模和控制的科學(xué)原理和工程應(yīng)用，以及用于實現(xiàn)特定目標(biāo)的原理和技術(shù)。流量工程的實質(zhì)是對網(wǎng)絡(luò)性能進行分析和實施優(yōu)化。從網(wǎng)絡(luò)管理者的角度，實施流量工程可以保證網(wǎng)絡(luò)資源的合理利用和網(wǎng)絡(luò)性能的優(yōu)化；從用戶的角度，實施流量工程可以更好地保證用戶的服務(wù)質(zhì)量。因此，實施流量工程對IP網(wǎng)絡(luò)，尤其是公共Internet骨干網(wǎng)是非常必要的[2]。
流量控制和資源分配技術(shù)是互聯(lián)網(wǎng)QoS保證的重要基礎(chǔ)[3]，不同網(wǎng)絡(luò)環(huán)境下的流量控制和資源分配技術(shù)有不同的特點。當(dāng)前互聯(lián)網(wǎng)采用的很多流量控制方法在效率、系統(tǒng)優(yōu)化以及公平性保障等方面存在著較大的缺點和不足。而優(yōu)化流量控制則基于擁塞計費技術(shù)，借鑒微觀經(jīng)濟學(xué)原理，利用價格桿杠的調(diào)節(jié)作用使系統(tǒng)達到優(yōu)化狀態(tài)，并可實現(xiàn)用戶之間資源共享的比例公平性，是一種較好的流量控制和資源分配方法[4]。
1 相關(guān)研究
最近很多研究提出的優(yōu)化流量控制機制借鑒了微觀經(jīng)濟學(xué)原理，通過效用函數(shù)的形式來表示用戶的帶寬需求，網(wǎng)絡(luò)以用戶效用函數(shù)的總和作為優(yōu)化的目標(biāo)函數(shù)[5]。網(wǎng)絡(luò)根據(jù)當(dāng)前的擁塞狀況不斷向用戶反饋擁塞費用，用戶在利益的驅(qū)動下，根據(jù)反饋的費用不斷調(diào)整用戶速率，最后達到系統(tǒng)優(yōu)化的均衡狀態(tài)[6]。
參考文獻[7]把微觀經(jīng)濟學(xué)方法引入網(wǎng)絡(luò)資源分配領(lǐng)域，分析了基于微觀經(jīng)濟學(xué)方法的網(wǎng)絡(luò)資源分配研究最新進展，介紹了網(wǎng)絡(luò)資源分配的典型經(jīng)濟模型，研究了各種定價策略，并分析與網(wǎng)絡(luò)資費相關(guān)的若干問題，最后研究基于價格的通信協(xié)議實現(xiàn)，為這一領(lǐng)域的研究提出了新思路。參考文獻[8]通過改變無向網(wǎng)絡(luò)流最小費用問題的描述，借助Floyd算法思想，給出了一種求解無向網(wǎng)絡(luò)流最小費用問題的算法，該算法具有路徑標(biāo)記功能，可以自動生成費用修正回路，并且適用于有向網(wǎng)絡(luò)流最小費用問題。參考文獻[9]基于博弈論方法提出了一種不依賴于端系統(tǒng)用戶合作的IP網(wǎng)絡(luò)流速率控制框架，將網(wǎng)絡(luò)中的流量源模型化為網(wǎng)絡(luò)博弈中的局中人，競爭共享網(wǎng)絡(luò)帶寬資源，通過一種有效的帶寬使用定價與收費機制，使博弈的Nash均衡解達到全局最優(yōu)，得到有效與公平的網(wǎng)絡(luò)帶寬分配。
實現(xiàn)技術(shù)中常用的令牌緩沖調(diào)度方法是固定周期令牌緩沖調(diào)度方法[10-11]FCTB(Fixed Cycle Token Buffer)，F(xiàn)CTB根據(jù)當(dāng)前時間與上次添加令牌的時間內(nèi)使用的令牌總數(shù)量往緩沖池內(nèi)添加令牌，并且是一次性添加完畢，沒有分段添加。本文設(shè)計了一種多鏈路共享令牌緩沖池流量調(diào)度模型，研究了多鏈路令牌調(diào)度費用計算，基于費用最優(yōu)研究了令牌緩沖流量調(diào)度負(fù)載計算方法COTB(Cost Optimization Token Buffer)，并且通過實驗與FCTB比較，證明了本文方法有較好的流量調(diào)度能力，能有效地控制鏈路的流量，改善系統(tǒng)負(fù)載均衡。
2 基于時延反饋的流量擁塞控制模型
2.1 多鏈路共享令牌流量調(diào)度模型
多鏈路共享會牌流量調(diào)度模型如圖1所示。假設(shè)某個系統(tǒng)中包含有N條邏輯鏈路，系統(tǒng)首先為每個進入系統(tǒng)的鏈路分配一個隊列，各個鏈路的數(shù)據(jù)到達系統(tǒng)后，在各自的隊列里進行排隊整形，經(jīng)過排隊整形后再依次被送到共享令牌緩沖池。緩沖池在某個固定的時間間隔內(nèi)產(chǎn)生一定的令牌，令牌是一種虛擬的資源，每個令牌代表允許通過一個最大的數(shù)據(jù)長度。共享令牌緩沖池中的令牌總數(shù)量表示當(dāng)前系統(tǒng)允許通過的最大數(shù)據(jù)量，數(shù)據(jù)發(fā)送時將消耗令牌，令牌降到一定的數(shù)量后要重新申請加入補充令牌，流控實體可以通過控制共享令牌緩沖池令牌數(shù)量的存儲對流量和系統(tǒng)負(fù)載進行控制。
費用指某動作或某狀態(tài)所消耗的系統(tǒng)資源。對網(wǎng)絡(luò)服務(wù)的計費要以占用的系統(tǒng)資源為基準(zhǔn)，系統(tǒng)資源包括帶寬資源、緩沖隊列管理資源和CPU時間片資源等多種資源，網(wǎng)絡(luò)服務(wù)通過對各種資源的使用來為用戶提供服務(wù)質(zhì)量，當(dāng)對系統(tǒng)的某種資源出現(xiàn)競爭時，費用計算就必須要考慮多種資源的聯(lián)合計算問題，這樣才能使費用計算成為系統(tǒng)負(fù)載控制的有效手段。
2.2 費用最優(yōu)令牌緩沖流量負(fù)載計算方法
為了便于分析，首先對數(shù)據(jù)包在鏈路中的處理情況定義如下變量：
p1：每次共享令牌緩沖池申請增加令牌的費用。
p2：令牌來到緩沖池后在里面進行排隊處理的費用，即每個單位時間每個令牌的儲存費用。由定義可知緩沖池內(nèi)令牌越多其平均儲存費用就越大。
p3：當(dāng)令牌緩沖池為空時，每個單位時間每條鏈路的等待費用。
n：每單位時間的令牌消耗總量。
Q：申請加入緩沖池的令牌總量。
T：申請令牌加入緩沖池的時間間隔，即申請周期。
q：任意時刻t緩沖池內(nèi)的令牌的剩余儲存量。
申請費用p1、平均儲存費用p2及單位時間消耗量n均為已知常數(shù)。模型要以總平均費用為目標(biāo)函數(shù)確定申請周期T和申請量Q的最優(yōu)值。
一般來說，令牌緩沖池存在著兩種狀態(tài)：非空和空。非空表示不允許緩沖池內(nèi)的令牌個數(shù)為0，當(dāng)令牌個數(shù)大于或等于0時就可以申請往緩沖池中增加令牌；可以為空時表示允許緩沖池內(nèi)的令牌個數(shù)等于0，當(dāng)?shù)扔?時系統(tǒng)處于等待狀態(tài)，不進行流量發(fā)送，將產(chǎn)生一定的等待費用。
(1)令牌緩沖池非空情況下的費用計算
由模型假設(shè)可以得出，申請周期T、申請量Q與每隔T時刻消耗量n之間滿足如下關(guān)系：
因此，制定最優(yōu)費用令牌調(diào)度策略歸結(jié)為求申請周期T使得C(T)最小。
利用微分法可以求出T和Q的最優(yōu)值，分別記作T′和Q′：
并且根據(jù)式(1)代入求得：
(2)令牌緩沖池為空時的費用計算
當(dāng)令牌緩沖池內(nèi)的所有令牌都使用完畢后，令牌的存儲數(shù)量為0，系統(tǒng)不進行流量發(fā)送，并進入等待申請令牌加入的狀態(tài)，等待時可以把令牌儲存量q視作負(fù)值，因此，q(t)的變化規(guī)律可以用圖3表示。
假設(shè)令牌在t=T1時刻全部用完，在一段時間內(nèi)令牌的存儲量為0，并且假設(shè)這時候令牌的消耗量仍然為n，在t=T時刻下一次令牌申請量q到達系統(tǒng)。于是由圖3可以得出：
則可以求得一個申請周期內(nèi)的最小平均費用為：
3 實驗與結(jié)果分析
3.1 實驗環(huán)境
本文在NS2上實現(xiàn)了費用最優(yōu)令牌緩沖流量調(diào)度負(fù)載控制方法，并進行了實驗，實驗使用的仿真網(wǎng)絡(luò)拓?fù)淙鐖D4所示。網(wǎng)絡(luò)拓?fù)溆砂l(fā)送端s1~s3、路由器R1~R5和接收端r1、r2組成，各節(jié)點間鏈路帶寬如圖4所示，各發(fā)送端通過虛擬撥號連接建立一條到接收端的邏輯鏈路，分別為L1~L3，鏈路路徑如圖4虛線所示。本文在R3節(jié)點上對所建立的邏輯鏈路進行共享令牌流量控制。
3.2 實驗結(jié)果對比分析
實驗中采用的對比方法為常用的固定周期令牌緩沖調(diào)度策略FCTB，主要考察這兩種方法在相同出口流量的情況下的系統(tǒng)負(fù)載對比。
在令牌緩沖池非空的情況下，通過這兩種調(diào)度方法造成出口流量差不多維持在同一水平上，大約為平均150 Mb/s，具體結(jié)果如圖5所示，然后進行系統(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)要花費大量的資源去維護整理那些在緩沖區(qū)里面的令牌，COTB雖然因為多次申請令牌到緩沖池增加了一定的系統(tǒng)負(fù)載，但總的系統(tǒng)平均負(fù)載仍然較FCTB低許多。
實驗加大出口流量時，由圖7可以看出，兩種調(diào)度方法的出口流量最高達到約160 Mb/s，約20 s后，令牌緩沖池內(nèi)的令牌使用完畢，出口流量迅速降到接近0，再用這兩種方法對緩沖池進行令牌補充然后，出口流量得以恢復(fù)。由數(shù)據(jù)采集統(tǒng)計得到，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在某段時間內(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ù)載均衡體系模型，提出了基于費用最優(yōu)的令牌緩沖流量調(diào)度負(fù)載計算方法，并在廣東茂名學(xué)院校園網(wǎng)上成功地實現(xiàn)了上述方法和體系結(jié)構(gòu)。實驗結(jié)果表明，增大了網(wǎng)絡(luò)通過量，降低了平均系統(tǒng)負(fù)載，鏈路在整個網(wǎng)絡(luò)結(jié)構(gòu)里有良好的時間響應(yīng)特性，取得較好的應(yīng)用效果。
下一步主要工作是對更多QoS受限條件下的多鏈路流量調(diào)度問題，對具有不同優(yōu)先權(quán)請求的鏈路進行區(qū)分以及基于處理節(jié)點計算能力的負(fù)載遷移等問題進行研究。
參考文獻
[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 Computer Communication Review， 2006，36(4):99-110.
[2] 劉郁恒，陳廣文，胡嚴(yán)，等.一種在接收端實現(xiàn)的TCP-Friendly擁塞控制機制[J].電子學(xué)報，2005，33(5):835-841.
[3] 張桂英，吳學(xué)智.下一代寬帶接入網(wǎng)QoS研究[J].計算機應(yīng)用，2007，27(6):174-176.
[4] 武航星，慕德俊，潘文平，等.網(wǎng)絡(luò)擁塞控制算法綜述[J].計算機科學(xué)，2007，34(2):51-56.
[5] 黃啟萍.流量控制與IP服務(wù)質(zhì)量[J].計算機工程，2006，32(11):144-146
[6] 葛敬國，馬宏偉，錢華林.Internet自治系統(tǒng)間負(fù)載均衡機制及其性能分析[J].計算機應(yīng)用，2005，25(12):2916-2917.
[7] 陳曉梅，盧錫城，王懷民.基于微觀經(jīng)濟學(xué)方法的網(wǎng)絡(luò)資源分配研究[J].計算機研究與發(fā)展，2001，38(11):1345-1353.
[8] 付彤，郭強.無向網(wǎng)絡(luò)流的最小費用問題[J].計算機工程與應(yīng)用，2005(28):88-90.
[9] 鐘伯成，韓江洪.網(wǎng)絡(luò)速率控制的博弈模型[J].華南理工大學(xué)學(xué)報(自然科學(xué)版)，2007，35(9):85-89.
[10] 涂文偉，張進，張興明.分級統(tǒng)籌分配令牌參數(shù)的流量整形算法[J].計算機應(yīng)用，2006，26(9):2175-2177.
[11] 雷雯，許都，黃振華.以數(shù)據(jù)流特性為導(dǎo)向的令牌調(diào)度算法[J].電子科技大學(xué)學(xué)報，2005，34(6):955-958.