Internet路由器主動式隊列管理機制綜述(3)

2019-11-05 00:34:11

字體：大中小

來源：轉載

供稿：網友

　　7 Adaptive RED
　　
　　
　　我們知道，Internet是基于統計復用的，一條鏈路上有很多活動連接在競爭有限的帶寬資源。在擁塞嚴重的網絡中，AQM必須將擁塞信息通知到足夠的源端，以充分降低負荷避免隊列溢出丟包。另一方面，AQM也要防止擁塞信息傳給了過多的源端，從而造成瓶頸鏈路利用率的下降。因此，進行擁塞通知時應充分考慮到瓶頸鏈路上流的數量。而RED并沒有考慮到這一點。為此ARED提出了一種自動配置機制，根據流量的變化來配置適當的參數。
　　
　　RED中，擁塞指示的發送速度是由參數maXP來體現的。假如maxp太大，那么丟包比例主要就是由于早期擁塞檢測中產生的丟包造成的；假如maxp太小，丟包主要就是由于隊列溢出造成的。RED的一個弱點是平均隊長對擁塞程度和參數設置很敏感。假如擁塞不太嚴重或者maxp很大，則平均隊長接近min_th；假如擁塞很嚴重或者maxp很小，則平均隊長接近或大于max_th。結果造成平均排隊時延對流量負荷和參數設置很敏感。
　　
　　TCP流獲得帶寬的上限可以通過下式估計：（1）
　　　

　　其中MSS：最大段尺寸（Maximum Segment Size） C ：常數 p ：丟包率
　　
　　假如有N個流競爭帶寬，我們可以得到：
　　　

　　（2）
　　
　　也即：
　　

　　（3）
　　
　　從上式可以看出，假如所有的流都采用了TCP的擁塞控制機制，那么丟包率的上限是和連接數的平方成正比。因此，激進的方法或者較大的maxp值適合于流較多的情況；保守的方法或者較小的maxp值適合于流較少的情況。
　　
　　ARED的基本思想就是通過檢查平均隊長的變化來感知RED是應更激進還是更保守。假如平均隊長是在min_th四周振蕩，那么擁塞控制就太激進了；假如在max_th四周振蕩，那么擁塞控制就太保守了。基于所觀察到的平均隊長，ARED動態地maxp調整的值。其算法如圖所示。
　　
　　Every avg_Q Update：
　　If（min_thmax_th && status!=Above）
　　　 status=Above
　　　 maxp= maxp *β
　　各參變量含義：
　　status　：平均隊長狀態
　　Between ：min_th和max_th之間
　　Below　：小于min_th
　　Above　：大于max_th
　　α　　　：maxp減少量
　　β　　　：maxp增加量
　　
　　
　　
　　ARED算法很簡單，就是根據平均隊長是否在min_th和max_th之間，對maxp采用積式增加和減少（Multiplicative Increase Multiplicative Decrease，MIMD）從而盡量保持平均隊長在min_th和max_th之間。
　　
　　ARED是對RED改動很小的一種算法，它保留了RED的基本結構，只需調節參數maxp從而保持平均隊長在min_th和max_th之間，消除了RED的隊列延時問題和參數敏感性問題。
　　
　　7．1 New ARED
　　
　　為了提高ARED的魯棒性，Sally Floyd等提出了一種新的ARED算法，我們姑且稱為New ARED。其基本思想和ARED一樣，都是采用自適應的maxp以保持平均隊長在min_th和max_th之間。不一樣之處在于，New ARED保持平均隊長在min_th和max_th的一半之內；不是每來一個包都改變，而是有一定時間間隔；maxp不采用積式增加和減少，而是和式增加和減少（Additive Increase Multiplicative Decrease，AIMD）；maxp限制在[0.01，0.5]。具體算法如下：
　　
　　Every interval seconds：
　　　If（avg_Q>target && maxp<=0.5）
　　maxp = maxp +α
　　else if（avg_Q=0.01）
　　　　 maxp = maxp *β
　　各參變量含義：
　　interval：時間間隔
　　target　：avg_Q的目標范圍
　　[min_th+0.4*(max_th-min_th),
　　min_th+0.6*(max_th-min_th)]
　　
　　
　　
　　New ARED的魯棒性主要來自于maxp不是很頻繁的變化。但假如擁塞程度急劇變化，則maxp需要過一段時間才能適應。為了保證ARED在這段時間里性能不會過度下降，因此將maxp限制在[0.01,0.5]之間。這樣，即使這段時間內平均隊長不足目標范圍內，平均延時和吞吐量也不會下降太多。
　　
　　7.2 ARED的缺陷
　　
　　ARED雖然解決了RED的參數敏感性問題，但其自身也帶來了參數設置問題。α、β設置太大，maxp振蕩過于頻繁，不利于網絡性能穩定；α、β設置太小，maxp就要經過多次調整蕩才能達到期望值。New ARED中參數interval的選擇也有類似問題。另外maxp的初值也會影響調整的過程和結果。
　　8其它幾種AQM機制
　　
　　
　　8.1 帶有懲罰盒的RED（RED with penalty box）
　　
　　這種算法是對RED不能有效保護適應流的一種改進。在RED的算法基礎之上增加了分類策略和調度策略。其基本思想是對流進行鑒別分類，鑒別出TCP-friendly和非TCP-friendly流。調度策略可以采用帶有權重的輪轉法（Weighted Round- Robin）、帶有權重的公平排隊（Weighted Fair- Queuing）或基于分類的排隊（Class-based Queueing CBQ）等。
　　
　　被鑒別為非TCP-friendly的流被分配到低優先級的調度區。若某一流在收到擁塞通知后，作出了降低發送速度的反應，那么它應該被重新分類（reclassfied）到高優先級調度區。
　　
　　8.2 GREEN
　　
　　GREEN的基本思想是根據擁塞程度來調整發送擁塞通知的速度，是一種反饋控制機制。GREEN主要是根據數據包到達路由器的速度來判定擁塞程度。假如包到達的速度超過了鏈路的容量，那么在某一時間間隔內，擁塞通知速度增加一次；反之，假如包到達的速度小于了鏈路的容量，那么在某一時間間隔內，那么擁塞通知速度減小一次。
　　
　　8.3 CHOKe（CHOose and Keep for responsive flows CHOose and Keep for unresponsive flows）
　　
　　CHOKe的主要目的也是保護適應流，懲罰非適應流。其基本思想是，當一個包到達擁塞的路由器時，CHOKe從FIFO隊列中隨機地挑出一個包進行比較。假如它們屬于同一個流，則這兩個包都被丟棄；否則，被挑出地包依然留下，而剛到達的包則依某種概率被丟棄，此概率的計算和RED中一樣。
　　
　　CHOKe算法是基于以下原因：由于非適應流的特點，FIFO隊列可能會更多地包含非適應流地包，也就意味著這種流的包更有可能被選中進行比較。從而對非適應流進行了懲罰。CHOKe基本上繼續了RED的優點，只是少量增加了一些額外開銷。

上一篇：關于路由器cpu利用率過高的解決

下一篇：移動IP的多層次位置管理及路由優化