資源描述：
《基于red算法的擁塞控制的研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應用文檔-天天文庫。
1、從本學科出發(fā)，應著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果基于RED算法的擁塞控制的研究摘要隨機早期檢測RED(RandomEarlyDetection)算法是目前路由器中采用的重要的隊列管理算法。本文介紹了目前廣泛研究的擁塞控制算法RED算法，指出了其運用于網(wǎng)絡時存在的缺陷，對幾種改進的RED算法做了介紹和分析。關(guān)鍵字擁塞控制隨機早期檢測SREDDREDFRED1引言在過去的十幾年里，計算機網(wǎng)絡經(jīng)歷了爆炸式的增長，給我們的生活帶來了極大的方便，同時也帶來了嚴重的擁塞問題課題份量和難易程度要恰當，博士生能在二年內(nèi)
2、作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別是對實驗條件等要有恰當?shù)墓烙嫛谋緦W科出發(fā)，應著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果。據(jù)統(tǒng)計，由于緩存的不足，其中發(fā)送端發(fā)送的數(shù)據(jù)包大約%10的包都將會被丟棄。我們使用圖1來描述擁塞的發(fā)生，其中有兩個關(guān)鍵點，分別是Knee和Cliff。當網(wǎng)絡負載較輕時，吞吐量的增長和網(wǎng)絡負載相比基本成線性關(guān)系，網(wǎng)絡延遲增長緩慢；在網(wǎng)絡負載超過Knee之后，網(wǎng)絡的吞吐量增長緩慢，而網(wǎng)絡延遲增長較快。當網(wǎng)絡負載超過Cliff之后，網(wǎng)絡吞吐量急劇下降，而網(wǎng)絡延遲急劇上升。從圖1中我們可以看出
3、擁塞控制的目標就是使網(wǎng)絡在Knee附近工作，.流控制和擁塞控制不同，流控制主要考慮了發(fā)送過程中的發(fā)送端和接收端,目的是使發(fā)送端的發(fā)送速率不超過接收端的接收能力.而擁塞控制則主要考慮了發(fā)送端和接收端之間的網(wǎng)絡環(huán)境,他們的目的是保證網(wǎng)絡環(huán)境中的數(shù)據(jù)不超過網(wǎng)絡的傳送能力,從而避免圖一出現(xiàn)的網(wǎng)絡性能嚴重下降的情況。1993年，F(xiàn)loyds和Jacobson提出了如何利用隨機早期檢測機制提供的路由器來檢測網(wǎng)絡的擁塞狀況。當今的網(wǎng)絡使用的TCP中，檢測到有數(shù)據(jù)包丟失時，才能檢測到網(wǎng)絡擁塞。而Floyds和Jacobson指出這很可能會造成長隊列一直占用整個時間，這將可能會極大的增加隊列的延遲時間。因
4、此，隨著網(wǎng)絡速度的提高，急切需要一種機制保證較高的吞吐量和較低的延遲。2RED算法TCP基于窗口的端到端擁塞控制對于Internet的魯棒性起到了關(guān)鍵作用。然而，隨著網(wǎng)絡的不斷發(fā)展，網(wǎng)絡規(guī)模越來越大，僅僅依靠TCP擁塞控制機制來提高網(wǎng)絡的服務質(zhì)量是遠遠不夠的，事實上，在Internet這樣復雜的系統(tǒng)中，不能指望所有的用戶都能兼容這種端到端的擁塞控制機制。而必須是網(wǎng)絡中的中間節(jié)點也參入到網(wǎng)絡擁塞的控制當中來。如采用路由器端的擁塞控制方法－IP擁塞控制問題，通常也稱之為隊列管理機制。其主要的思想就是通過排隊算法決定那些包可以傳輸，以此分配帶寬，通過丟棄策略決定接受到的包哪些包被丟棄，哪些包被
5、轉(zhuǎn)發(fā)，以此來分配緩存。⑴ RED算法鑒于以上原因，一種主動隊列管理技術(shù)－RED應運而生，課題份量和難易程度要恰當，博士生能在二年內(nèi)作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別是對實驗條件等要有恰當?shù)墓烙?。從本學科出發(fā)，應著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果RED通過隨機丟棄數(shù)據(jù)分組，控制平均隊列長度，從而避免網(wǎng)絡擁塞和全網(wǎng)同步重發(fā)，保證相對的公平性，并確保沒有傳輸層的協(xié)同工作時也能使平均隊列長度不超過某個上界。其基本思想是：隨著隊列尺寸的增大，數(shù)據(jù)分組被丟棄的可能性也會增大。RED利用指數(shù)加權(quán)平滑低通濾波器計算
6、平均隊列長度，將AVQ與兩個門限值比較。當平均隊列長度小于MINth時，不標記任何數(shù)據(jù)分組。當平均隊列長度大于MAXth時，則標記所有后續(xù)到達的數(shù)據(jù)分圖一組。通過丟棄標記分組或通知源節(jié)點降低發(fā)送速率的方式，保證平均隊列長度不超過MAXth所限定的隊列長度。若平均隊列長度介于兩個門限值之間，則以概率Pa丟棄或標記后續(xù)到達分組，其中Pa是平均隊列長度的函數(shù)。事實上，連接中分組丟棄的概率大致和該連接占用的帶寬成正比。這是因為對一個發(fā)送量較大的數(shù)據(jù)流來說，可供隨機丟棄的分組的數(shù)量也相對較多，不能保證公平性，這也是RED算法的缺陷。其分組丟棄如圖二所示。事實上，RED路由器有兩個獨立的算法，計算平
7、均隊列長度算法與計算丟棄概率算法。計算平均隊列長度的算法決定了路由器隊列容納突發(fā)性數(shù)據(jù)流的長度，計算丟棄概率決定了在給定的當前擁塞級別時分組的丟棄頻度。整個算法大體描述如下：Avq=0，count=-1;當有分組到達時：If(隊列空){=f(time-q_time);Avq=(1-w)mAvq;}elseAvqb＝maxp((Avq-MINth)/(MAXth-MINth));Pa=Pb/(1-count*P);}elseif(Av
