IP擁塞控制中隊列調度及優(yōu)化問題的研究.pdf

1、隨著互聯網、移動通訊、無線網絡、個人多媒體業(yè)務以及工業(yè)網絡中大量多媒體數據的出現，對路由器的隊列調度和隊列管理能力的要求越來越高。路由器在轉發(fā)傳統(tǒng)數據包業(yè)務的同時，還需要滿足越來越多的實時性業(yè)務的要求。傳統(tǒng)的隊列調度算法，如先來先服務(FCFS)、輪詢(RR)等算法已經不能滿足這種區(qū)分服務的要求。 本文首先分析了現有的隊列調度算法，指出從控制論的角度來看，當前存在的隊列調度算法基本都是使用開環(huán)控制方式。在“開環(huán)控制”的隊列調度算

2、法中，網絡服務器按照某種策略，以事先可以預知的確定順序轉發(fā)各活動業(yè)務流的數據包。這種確定模型的優(yōu)勢在于可以事先預知下一個時刻要發(fā)送哪個業(yè)務流的數據包，從而有利于定性定量地分析系統(tǒng)性能；其缺點則是往往需要假設某些參數已知或業(yè)務流符合某種函數限制，擴展性較差，僅對特定網絡類型表現出良好性能。針對上述算法的缺點，本文提出了一種全新的“服務量”和“服務概率”定義，并根據此定義提出了一種基于“服務概率”的柔性隊列調度策略。該算法根據調度器輸出端反

3、饋的數據包長度信息，動態(tài)調整各活動業(yè)務流的服務概率，并且利用隨機數實現了統(tǒng)計意義上的公平服務。與傳統(tǒng)的隊列調度算法相比，該算法具有計算復雜度低、需要維護的變量少、魯棒性強、數據源模型無關性等優(yōu)點。 網絡運營商在為用戶提供網絡服務，盡量滿足用戶要求的前提下，總是希望最大化自身收益。本文通過引入業(yè)務流服務價格等參數，將網絡收益作為優(yōu)化目標，把對業(yè)務流的帶寬要求、網絡流量、網絡延遲作為限制條件，使用控制論中經典的最優(yōu)控制理論對所提出的

4、基于“服務概率”的隊列調度算法進行參數優(yōu)化。相對于其他隊列調度算法，本文所提出的調度算法由于參數較少，只需要“服務概率”一個控制變量即可控制各種業(yè)務流所獲得的帶寬，這樣在線優(yōu)化所涉及的參數少，運算復雜度低，從而具有更高的應用價值。 從控制論的角度來看，隊列調度算法是一個典型的控制問題。各業(yè)務流所要求的帶寬、帶寬抖動和時延、時延抖動是控制目標，這非常類似經典控制問題中的穩(wěn)態(tài)值和超調量。隊列調度的目標便是使用盡量簡單的控制策略、盡量

5、少的控制變量和盡量短的控制時間實現控制目標。傳統(tǒng)的調度算法都是開環(huán)結構，根據預定策略分配帶寬，并不對實際分配的帶寬進行反饋校正，從而使得算法只能適用于特定模型，魯棒性較差。本文利用經典控制理論中的PI算法，基于“服務概率”參數，實現了反饋控制結構的隊列調度算法。算法只有“服務概率”一個控制參數，實現簡單；PI反饋保證了無論數據源模型如何變化，各業(yè)務流所獲帶寬始終實時跟蹤設定值。在無線網絡中，由于帶寬資源有限，調度算法需要根據各業(yè)務流的信

6、號狀態(tài)動態(tài)調整資源分配；本文提出的PI反饋結構的調度算法便非常適合應用于移動通訊基站和無線局域網接入點中。 論文的主要創(chuàng)新點包括： △提出了隊列算法的控制論模型；依據控制論的觀點對現有隊列調度算法進行分析，指出了當前存在的主要隊列調度算法的優(yōu)缺點。 △提出了“服務概率”的概念，通過定義業(yè)務流的“服務概率”來確定其所獲得的帶寬，通過隨機數實現統(tǒng)計意義上的公平帶寬分配；根據“服務概率”定義設計出用于定長數據包網絡的加

7、權公平隊列調度算法PWFQ。 △通過一階低通濾波器來估計業(yè)務流的平均數據包長度，將基于“服務概率”的隊列調度算法應用到變長度網絡環(huán)境；與變長度環(huán)境下現有的其他加權公平調度算法相比，本文提出的算法具有參數變量少、計算復雜度和空間復雜度低、帶寬分配平滑、公平性能優(yōu)良等特點。 △通過將各業(yè)務流的網絡使用費作為目標函數，提出了一種基于“效用函數”的隊列調度算法參數優(yōu)化模型；通過在線參數優(yōu)化，使網絡的整體性能指標達到最優(yōu)狀態(tài)。與現