基于RED算法的擁塞控制的研究

1、基于RED算法的擁塞控制的研究摘要隨機(jī)早期檢測RED(RandEarlyDetetin)算法是目前路由器中采用的重要的隊(duì)列管理算法。本文介紹了目前廣泛研究的擁塞控制算法RED算法，指出了其運(yùn)用于網(wǎng)絡(luò)時(shí)存在的缺陷，對幾種改良的RED算法做了介紹和分析。關(guān)鍵字擁塞控制隨機(jī)早期檢測SREDDREDFRED1引言在過去的十幾年里，計(jì)算機(jī)網(wǎng)絡(luò)經(jīng)歷了爆炸式的增長，給我們的生活帶來了極大的方便，同時(shí)也帶來了嚴(yán)重的擁塞問題。據(jù)統(tǒng)計(jì)，由于緩存的缺乏，其中發(fā)送端發(fā)送的數(shù)據(jù)包大約%10的包都將會被丟棄。我們使用圖1來描繪擁塞的發(fā)生，其中有兩個關(guān)鍵點(diǎn)，分別是Knee和liff。當(dāng)網(wǎng)絡(luò)負(fù)載較輕時(shí)，吞吐量的增長和網(wǎng)絡(luò)負(fù)載

2、相比根本成線性關(guān)系，網(wǎng)絡(luò)延遲增長緩慢；在網(wǎng)絡(luò)負(fù)載超過Knee之后，網(wǎng)絡(luò)的吞吐量增長緩慢，而網(wǎng)絡(luò)延遲增長較快。當(dāng)網(wǎng)絡(luò)負(fù)載超過liff之后，網(wǎng)絡(luò)吞吐量急劇下降，而網(wǎng)絡(luò)延遲急劇上升。從圖1中我們可以看出擁塞控制的目的就是使網(wǎng)絡(luò)在Knee附近工作，.流控制和擁塞控制不同，流控制主要考慮了發(fā)送過程中的發(fā)送端和接收端,目的是使發(fā)送端的發(fā)送速率不超過接收端的接收才能.而擁塞控制那么主要考慮了發(fā)送端和接收端之間的網(wǎng)絡(luò)環(huán)境,他們的目的是保證網(wǎng)絡(luò)環(huán)境中的數(shù)據(jù)不超過網(wǎng)絡(luò)的傳送才能,從而防止圖一出現(xiàn)的網(wǎng)絡(luò)性能嚴(yán)重下降的情況。1993年，F(xiàn)lyds和Jabsn提出了如何利用隨機(jī)早期檢測RED機(jī)制提供的路由器來檢測網(wǎng)絡(luò)的

3、擁塞狀況。當(dāng)今的網(wǎng)絡(luò)使用的TP傳輸控制協(xié)議中，檢測到有數(shù)據(jù)包喪失時(shí)，才能檢測到網(wǎng)絡(luò)擁塞。而Flyds和Jabsn指出這很可能會造成長隊(duì)列一直占用整個時(shí)間，這將可能會極大的增加隊(duì)列的延遲時(shí)間。因此，隨著網(wǎng)絡(luò)速度的進(jìn)步，急迫需要一種機(jī)制保證較高的吞吐量和較低的延遲。2RED算法TP基于窗口的端到端擁塞控制對于Internet的魯棒性起到了關(guān)鍵作用。然而，隨著網(wǎng)絡(luò)的不斷開展，網(wǎng)絡(luò)規(guī)模越來越大，僅僅依靠TP擁塞控制機(jī)制來進(jìn)步網(wǎng)絡(luò)的效勞質(zhì)量是遠(yuǎn)遠(yuǎn)不夠的，事實(shí)上，在Internet這樣復(fù)雜的系統(tǒng)中，不能指望所有的用戶都能兼容這種端到端的擁塞控制機(jī)制。而必須是網(wǎng)絡(luò)中的中間節(jié)點(diǎn)也參入到網(wǎng)絡(luò)擁塞的控制當(dāng)中來。如

4、采用路由器端的擁塞控制方法IP擁塞控制問題，通常也稱之為隊(duì)列管理機(jī)制。其主要的思想就是通過排隊(duì)算法決定那些包可以傳輸，以此分配帶寬，通過丟棄策略決定承受到的包哪些包被丟棄，哪些包被轉(zhuǎn)發(fā)，以此來分配緩存。RED算法鑒于以上原因，一種主動隊(duì)列管理AtiveQueueanageent技術(shù)REDRandEarlyDetetin,隨機(jī)早期檢測應(yīng)運(yùn)而生，RED通過隨機(jī)丟棄數(shù)據(jù)分組，控制平均隊(duì)列長度，從而防止網(wǎng)絡(luò)擁塞和全網(wǎng)同步重發(fā)，保證相對的公平性，并確保沒有傳輸層的協(xié)同工作時(shí)也能使平均隊(duì)列長度不超過某個上界。其根本思想是：隨著隊(duì)列尺寸的增大，數(shù)據(jù)分組被丟棄的可能性也會增大。RED利用指數(shù)加權(quán)平滑低通濾波器

5、計(jì)算平均隊(duì)列長度AVQ，將AVQ與兩個門限值INth和AXth，INthAXth比擬。當(dāng)平均隊(duì)列長度小于INth時(shí)，不標(biāo)記任何數(shù)據(jù)分組。當(dāng)平均隊(duì)列長度大于AXth時(shí)，那么標(biāo)記所有后續(xù)到達(dá)的數(shù)據(jù)分圖一組。通過丟棄標(biāo)記分組或通知源節(jié)點(diǎn)降低發(fā)送速率的方式，保證平均隊(duì)列長度不超過AXth所限定的隊(duì)列長度。假設(shè)平均隊(duì)列長度介于兩個門限值之間，那么以概率Pa丟棄或標(biāo)記后續(xù)到達(dá)分組，其中Pa是平均隊(duì)列長度的函數(shù)。事實(shí)上，連接中分組丟棄的概率大致和該連接占用的帶寬成正比。這是因?yàn)閷σ粋€發(fā)送量較大的數(shù)據(jù)流來說，可供隨機(jī)丟棄的分組的數(shù)量也相對較多，不能保證公平性，這也是RED算法的缺陷。其分組丟棄如圖二所示。事實(shí)

6、上，RED路由器有兩個獨(dú)立的算法，計(jì)算平均隊(duì)列長度算法與計(jì)算丟棄概率算法。計(jì)算平均隊(duì)列長度的算法決定了路由器隊(duì)列包容突發(fā)性數(shù)據(jù)流的長度，計(jì)算丟棄概率決定了在給定的當(dāng)前擁塞級別時(shí)分組的丟棄頻度。整個算法大體描繪如下：Avq=0，unt=-1;當(dāng)有分組到達(dá)時(shí)：If(隊(duì)列空)=f(tie-q_tie);Avq=(1-)Avq;elseAvq(1)Avq+q；If(INth=Avq=AXth)unt=unt+1;Pbaxp(Avq-INth)/(AXth-INth);Pa=Pb/(1-unt*P);elseif(Avq=AXth)丟棄分組elseunt=-1;其中：Avq:路由器隊(duì)列平均長度;q:當(dāng)前

7、隊(duì)列長度。Pa:當(dāng)前分組被丟棄的概率;Pb:計(jì)算中臨時(shí)使用的概率。:路由器空閑期間可能發(fā)送的最小分組數(shù);tie:當(dāng)前時(shí)間。q_tie:隊(duì)列空閑時(shí)間的開場;f(t):時(shí)間t的一個線性函數(shù);unt:上次丟棄分組后收到的分組個數(shù);axp:Pb的最大值。RED算法的缺陷參數(shù)設(shè)置問題：RED性能的優(yōu)劣很大程度上是由其預(yù)先設(shè)置的參數(shù),AXth和INth決定的。如何權(quán)衡吞吐量延遲之間的關(guān)系，從而找到一組最優(yōu)的參數(shù)有待進(jìn)一步研究.圖2尚不能有效估計(jì)擁塞的嚴(yán)重性：RED通過檢測早期的擁塞減輕了“尾部丟棄機(jī)制造成的大量分組無畏丟棄，但必須配置足夠的緩沖區(qū)包容從檢測到擁塞到瓶頸鏈路負(fù)荷開場下降這段時(shí)間內(nèi)到達(dá)的數(shù)據(jù)分

8、組。當(dāng)有大量突發(fā)性TP數(shù)據(jù)時(shí)，隊(duì)列長度的增減異常迅速，RED來不及做出反映。RED公平性問題：對RED而言，不同TP流RTT的差異是損害公平性的原因之一。理論上，在丟棄概率一定的情況下，TP的發(fā)送速率大致和RTT呈反比，而RED在特定時(shí)刻對所有流都使用同一丟棄概率，這就必然導(dǎo)致不公平。鑒于以上原因，RED出現(xiàn)了它的多種變體及改良，下面對其中的幾種算法的原理和性能進(jìn)展一下簡單的介紹。3RED的改良及性能介紹ARED在擁塞嚴(yán)重的網(wǎng)絡(luò)中，RED必須將擁塞信息通知到足夠的源端充分降低負(fù)荷，防止隊(duì)列溢出而喪失分組。Ranjan指出在TP連接中采用上述的RED模型將會出現(xiàn)許多非線性現(xiàn)象，比方隨參數(shù)的變化會

9、出現(xiàn)振蕩和混亂現(xiàn)象。其中RED的一個弱點(diǎn)就是平均隊(duì)列長度很大一局部依賴于網(wǎng)絡(luò)中的負(fù)載，假設(shè)負(fù)載較輕，那么平均隊(duì)列長度接近于最小隊(duì)列，并且系統(tǒng)處于不穩(wěn)定狀態(tài)。為理解決上述問題，F(xiàn)lyd提出了RED的改良機(jī)制，即ARED。ARED的根本思想是通過檢查平均隊(duì)列長度的變化來決定RED是更激進(jìn)還是更保守，即是丟棄更多的包還是選擇減少丟包的數(shù)量，從而盡量保持平均隊(duì)列的長度的變化在INth和AXth。詳細(xì)的說，假如平均長度在INth之間擺動就是說明擁塞控制算法太激進(jìn)了，那么就減小axp，axp=axp/a;相反的假如平均長度在AXth之間擺動，就是說明擁塞控制算法太保守了，那么就增大axp，axp=axp*

10、b.其中ba1.FREDFRED對每個業(yè)務(wù)流(或連接)都施行單獨(dú)的一個RED算法,它通過對每個活潑的數(shù)據(jù)流進(jìn)展記帳，對使用不同帶寬的流做出不同的標(biāo)記包的決策，從而進(jìn)步了不同的流享用帶寬的公平性。使用RED時(shí)，主要會產(chǎn)生公平性問題：對一些強(qiáng)壯的流，這些數(shù)據(jù)流可以對網(wǎng)絡(luò)中發(fā)生的擁塞做出反映，并可以充分利用現(xiàn)有的網(wǎng)絡(luò)條件繼續(xù)發(fā)送數(shù)據(jù)，但對一些脆弱流，他們也可以做出反映，但這些數(shù)據(jù)流要么對丟包過于敏感，要么對更多可用的帶寬適應(yīng)很慢，比方TELNET.。當(dāng)一個包進(jìn)入路由器時(shí)，不在是單單的采用RED算法來進(jìn)展數(shù)據(jù)包的丟棄，假如平均隊(duì)長Avq小于AXth，并且該包所屬流在緩沖區(qū)中排隊(duì)包的數(shù)量小于最小隊(duì)列長度

11、，該包總被接收。這樣，F(xiàn)RED就保護(hù)了脆弱的流。當(dāng)該流的隊(duì)列長度大于最大隊(duì)列長度時(shí)，那么標(biāo)記該流的概率就會大大增加。SREDSRED的根本思想就是比擬。當(dāng)有一個包到達(dá)buffer時(shí)，就和buffer中隨機(jī)選出的一個包進(jìn)展比擬，假設(shè)兩個包屬同一個流，那么稱為擊中hit。為了使系統(tǒng)有更長的記憶，SRED設(shè)計(jì)了一種數(shù)據(jù)構(gòu)造，稱為僵尸列表ZbieList。這個列表可以被認(rèn)為是一種流ahe，其中記錄了最近流經(jīng)該buffer的個流及其一些額外信息：unt和時(shí)間戳。起初列表為空，當(dāng)有一個包到達(dá)時(shí)，只要列表非空，那么該包的流標(biāo)識源、目的地址等參加列表，其僵尸的unt設(shè)為0，時(shí)間戳為該包的到達(dá)時(shí)間。一旦僵尸列表

12、滿了，那么作如下工作：當(dāng)一個包到達(dá)后，它和僵尸列表中隨機(jī)選出的僵尸進(jìn)展比擬：擊中：一旦到達(dá)包的流與僵尸匹配，稱為一個hit，在此情況下，僵尸的unt值加1，tiestap值更新為新到達(dá)包的時(shí)間。沒擊中：假如兩者不是同一個流，稱為“N-hit，在此情況下，以概率p重寫僵尸中的流描繪符，unt值設(shè)為0，tiestap設(shè)為新到包的時(shí)間，以1-p的概率維持原有僵尸表。SRED用一個函數(shù)Hit(t)來記錄第t個包是否擊中，假如擊中，那么Hit(t)取值為1，否那么為0。從惡意流相比擬良好流更易引發(fā)擊中，這個意義上說，假如一個包引發(fā)擊中，那么可認(rèn)為該包屬于惡意流。假如一個包擊中并且該僵尸的unt值很大，就

13、更明顯了。4算法比擬與評價(jià)以上RED算法均有改良之處，RED允許網(wǎng)關(guān)同時(shí)獲得較高吞吐量和較低的平均延遲，但是它對參數(shù)的設(shè)置非常敏感，同樣的參數(shù)設(shè)置在不同的網(wǎng)絡(luò)環(huán)境下獲得的網(wǎng)絡(luò)性能會有很大的差異，因此需要根據(jù)網(wǎng)絡(luò)環(huán)境的變化來動態(tài)地調(diào)節(jié)RED參數(shù)，ARED較好地解決了這個問題。FRED改良了帶寬分配的不公平性，假如擁塞比擬持久，意味著RED的Avq高于INth。這時(shí)丟包率是一個非零的值，即使占用帶寬較小的值也有包丟棄，且對于一樣類型的傳輸也會有短暫的不成比例的包丟棄。針對上述幾個問題，F(xiàn)RED進(jìn)展了有效的改良。與RED的隨機(jī)選擇某一個連接進(jìn)展擁塞通告的方式不同，F(xiàn)RED有選擇地向那些隊(duì)列中有較多數(shù)

14、據(jù)包地連接發(fā)送反應(yīng)信息，它能有效地隔離不規(guī)矩的連接，對突發(fā)數(shù)據(jù)較多和低速的連接提供了更好的保障，進(jìn)步了不同數(shù)據(jù)流帶寬分配的公平性。SRED的主要目的是保持FIF隊(duì)列的穩(wěn)定(與活潑流(Ativefls)的數(shù)量無關(guān));另外一個目的是鑒別惡的流(isbehavingfls)其主要思想是通過估計(jì)網(wǎng)絡(luò)中流的個數(shù)調(diào)整分組標(biāo)記/丟棄概率。而流的個數(shù)是通過概率統(tǒng)計(jì)的方法來獲得的，所以SRED中不需要使用Per-fl信息。SRED在相當(dāng)大的負(fù)荷范圍內(nèi)，都能保持隊(duì)列的穩(wěn)定而與活潑流的數(shù)量相獨(dú)立，從而有效的減小了延遲抖動。而且也給出了鑒別惡意流的方法并且對其進(jìn)展懲罰。5小結(jié)從以上討論可以看出,FRED,ARED和SRED幾乎在所有方面都要優(yōu)于RED算法,而這幾種算法之間那么很難說哪種算法性能更好.它本身各有其優(yōu)勢之處，但改良算法在完善了RED的根底上大都很難解決自身的參數(shù)設(shè)置問題，如何解決這個問題有待我們進(jìn)一步研究。參考文獻(xiàn)：1潘愛民,徐明偉.計(jì)算機(jī)網(wǎng)絡(luò).清華大學(xué)出版社,北京:2022年2徐恪，徐明偉.高等計(jì)算機(jī)網(wǎng)絡(luò)體系構(gòu)造，協(xié)議機(jī)制，算法設(shè)計(jì)與路由技術(shù)3S.Athuraliya,VH.Li,S.H.L,Netrk,vl.15,n.3,pp.48-53a