基于最優(yōu)化流控的擁塞控制算法研究.pdf

1、隨著計(jì)算機(jī)網(wǎng)絡(luò)的迅速發(fā)展，互聯(lián)網(wǎng)用戶不斷激增，網(wǎng)絡(luò)的擁塞也變得越來越重。自從Jacobson于1988年提出擁塞控制的概念以來，擁塞控制引起了人們極大的關(guān)注，各種擁塞控制理論以及算法也相繼提出。擁塞控制成了當(dāng)今互聯(lián)網(wǎng)研究的熱點(diǎn)問題。擁塞控制研究由于其巨大的復(fù)雜性，現(xiàn)有的擁塞控制算法已不滿足于以往的基于主觀的分析方法，而是借助于嚴(yán)格的數(shù)學(xué)證明、非線性動(dòng)力學(xué)方法、控制與優(yōu)化理論分析復(fù)雜多變的網(wǎng)絡(luò)系統(tǒng)，來設(shè)計(jì)新的、更適合網(wǎng)絡(luò)的擁塞控制算法。

2、 本文的理論基礎(chǔ)是非線性最優(yōu)化流控，最優(yōu)化流控理論是從微觀經(jīng)濟(jì)學(xué)、博弈論和非線性最優(yōu)化理論發(fā)展而來，1998年Kelly給出了關(guān)于最優(yōu)化流控框架的基礎(chǔ)性論文，1999年12月Low基于此提出了完整的最優(yōu)化流控理論。它的主要思想是：最優(yōu)化流控的目標(biāo)是最大化源端在其傳輸速率下的總效用，把網(wǎng)絡(luò)鏈路和源端看作是一個(gè)分布式計(jì)算系統(tǒng)的處理器，Low等使用了異步梯度投影算法求解這個(gè)最優(yōu)化問題的對(duì)偶問題，一個(gè)關(guān)鍵的特性就是這個(gè)對(duì)偶問題可以被分解成

3、一些簡(jiǎn)單的子問題，給定對(duì)偶問題的最優(yōu)價(jià)格，單個(gè)的源端就能個(gè)別地求解它的最大利益，而不需要與其它源端協(xié)調(diào)。在這個(gè)系統(tǒng)中，源端選擇能最大化自己利益的傳輸速率，而鏈路調(diào)節(jié)帶寬價(jià)格來協(xié)調(diào)源端的決策。Low等基于最優(yōu)化流控理論，提出了TCP/AQM的對(duì)偶模型，論模型的主導(dǎo)思想是：把發(fā)送速率看作原始變量，把擁塞度量看作對(duì)偶變量，源端據(jù)反饋回業(yè)的擁塞　度量調(diào)整其發(fā)送速率，而各源端發(fā)送速率的大小又會(huì)返過來影響擁塞度量，從而構(gòu)成一個(gè)閉環(huán)擁控制系統(tǒng)。該模型

4、把現(xiàn)有的TCP擁塞控制和AQM算法盾作是求解具有適當(dāng)效用函數(shù)的最優(yōu)速率分配問題的分布式算法，從而可從理論上分析網(wǎng)絡(luò)在平衡狀時(shí)的性能，如吞吐量、丟包率、時(shí)延和排隊(duì)長(zhǎng)度等。 在全面分析和討論最優(yōu)化流控理論的基礎(chǔ)上，基于TCP/AQM的對(duì)偶模型，把端算法和中間結(jié)點(diǎn)算法有效地結(jié)合起來，提出了兩個(gè)基于最優(yōu)化流控的擁寒控制算法，其主要工作有： 一、全面分析和研究了最優(yōu)化流控理論。這是本文擁塞控制算法的理論基礎(chǔ)。本文的第二章集中研究了

5、這個(gè)流控理論。本章首先介紹了最優(yōu)化流控理論框架，給出了最優(yōu)化流控的原對(duì)偶問題及其求解對(duì)偶問題的梯度投影算法，本章著基于最優(yōu)化流控理論，給出了一個(gè)TCP/AQM的對(duì)偶模型，仔細(xì)研究了TCP/AQM對(duì)偶模型的數(shù)學(xué)建模和主要思想。本章的最后探討了REM算法，分析了REM的特性及其參數(shù)設(shè)置。 二、提出了基于最優(yōu)化流控的擁塞控制算法：Mreno。針對(duì)Reno算法的周期性抖動(dòng)和效率很底的帶寬利用率，結(jié)合最優(yōu)先控制理論，提出了一個(gè)新的擁塞控制

6、算法，標(biāo)注的Reno算法（Mreno）。NS-2仿真實(shí)驗(yàn)證明，Mreno算法比Reno算法有更好的穩(wěn)定性和帶寬利用率，在公平性方面也比較好，這正是我們想看到的。模擬結(jié)果也符合最優(yōu)化流控的指導(dǎo)思想。但是Mreno算法與Reno算法一樣，隨著帶寬的增加，它的穩(wěn)定性就會(huì)減弱。這也是需要進(jìn)一步解決的問題。 三、提出了基于最優(yōu)化流控的擁寒控制算法：Pvegas。同Mreno算法一樣，這部分內(nèi)容安排在第三章。TCP Vegas,作為TCP

7、Reno的替代算法，不像TCP Reno（或者它的改進(jìn)，如NewReno,Sack）以丟包作為擁塞度理，而是以隊(duì)列延遲作為擁塞度量。TCP Vegas是一個(gè)優(yōu)點(diǎn)和缺點(diǎn)同樣明顯的算法。它的優(yōu)點(diǎn)是當(dāng)網(wǎng)絡(luò)里只有TCP Vegas連接時(shí)，它的吞吐量非常高，并且達(dá)到平衡時(shí)沒有丟包，此外，TCP Vegas對(duì)長(zhǎng)延遲的連接不會(huì)產(chǎn)生不公平。它的缺點(diǎn)是當(dāng)TCP Vegas連接與其它非TCP Vegas邊接競(jìng)爭(zhēng)有限帶寬時(shí)，除非路由器緩存非常小，否則TCP