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

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

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

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

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

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

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

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