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

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

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

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

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

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

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

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