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