red[隨機早期檢測(Random Early Detection )]

基本思想

Random Early Detection，為避免發生網路中的全局同步現象，在路由器採用的一種措施。

基本思想上：通過監控路由器輸出連線埠佇列的平均長度來探測擁塞，一旦發現擁塞逼近，就隨機地選擇連線來通知擁塞，使他們在佇列溢出導致丟包之前減小擁塞視窗，降低傳送數據速度，從而緩解網路擁塞。由於RED是基於FIFO佇列調度策略的，並且只是丟棄正進入路由器的數據包，因此其實施起來也較為簡單。

隨機早期檢測的設計目標

1）最小化數據包丟失率和排隊延遲；

2）避免全局同步現象；

3）避免對突發業務的偏見：網路中含有大量的突發數據，而傳統的“去尾”算法對突發業務有很大的偏見。偏見就是在採用“去尾”算法的路由器中，如果某個流的突發性越高，則當該流的數據包進入佇列時越容易造成佇列溢出，從而導致連續地丟棄大量的該流的包；

4）即使在缺乏傳輸層協定有效配合的情況下，算法也能控制平均佇列長度，從而避免擁塞。為了達成以上目標，RED採用了基於時間的平均佇列長度，並且隨機地選擇正進入路由器地分組進行丟棄。這種方法能被有效地實施而無需在路由器中維持每個流（per-flow）的狀態信息。

RED算法

首先是計算平均佇列長度，以此作為對擁塞程度的估計。另一個就是計算丟棄分組的機率。

計算平均佇列長度

由於Internet數據的突發性，如果一個佇列很多時候是空的，然後迅速被充滿，又很快被取空，這時就不能說路由器發生擁塞而需要向源端傳送擁塞指示。因此，RED在計算平均隊長avgQ時，採用了類似低通濾波器（Low—pass filter）帶權值的方法：

avgQ=(1-Wq)*avgQ+ Wq* q。

其中，Wq為權值，q為採樣測量時實際佇列長度。這樣由於Internet數據的突發本質或者短暫擁塞導致的實際佇列長度暫時的增長將不會使得平均隊長有明顯的變化，從而“過慮"掉短期的隊長變化，儘量反映長期的擁塞變化。

在計算平均隊長的公式中，權值Wq相當於低通濾波器的時間常數，它決定了路由器對輸入流量變化的反應程度。因此對Wq的選擇非常重要，如果Wq過大，那么RED就不能有效地過慮短暫的擁塞；如果Wq太小，那么avgQ就會對實際佇列長度的變化反應過慢，

不能合理地反映擁塞狀況，在這種情況下，路由器就不能有效檢測到早期的擁塞。Wq的值應根據不同情況預先設定，一般來說，它是由路由器允許發生的突發業務的大小和持續的時間所決定的。

計算丟棄分組的機率

計算平均隊長的目的就是為了反映擁塞狀況，根據擁塞的程度來計算丟棄分組的機率，從而有效地控制平均佇列長度。

RED有兩個和佇列長度相關的閾值：MINth。和MAXth。當有分組達到路由器時，RED計算出平均隊長avgQ。若avgQ< MINth，則沒有分組需要丟棄；當MINth≤avgQ≤MAXth時，計算出機率P，並以此機率丟棄分組；當avgQ>MAXth時，所有的分組都被丟棄。由於RED使用的是基於時間的平均隊長度，就有可能會發生實際隊長大於平均隊長的情況，如果佇列已滿，則到達的分組只能被丟棄。

實例

隨機早起檢測（RED，Random Early Detection）算法將佇列的平均隊長作為決定擁塞避免機制是否應被處罰的隨機函式的參數，增加了在佇列長度變得太大之前平滑瞬時擁塞的可能性，減少了同時使多個流受分組丟棄影響的可能性。

下圖是一個RED丟棄機率函式的例子

red[隨機早期檢測(Random Early Detection )]

當佇列長度小於低的門限值Tmin時，不丟棄新到達的分組；當佇列長度介於Tmin和Tmax之間時，以一定的機率丟棄分組，且分組機率隨著佇列長度的增長線性增加，佇列長度達到Tmax時，到達的分組全部被丟棄。這3個階段分別被稱作正常、擁塞避免和擁塞控制三個階段。最壞情況的最大佇列大小被限制為Tmax。RED在佇列滿之前提前開始觸發擁塞標識。路由器可對不同的佇列支持不同的Tmin、Tmax和Pmax值以平衡佇列可用空間、要求的佇列數和使用每一個佇列的業務類的延遲/抖動範圍。

RED最初是作為IntServ中的一種擁塞避免機制提出來的，當用在DiffServ中時，為了獲得更好的性能，為一致的分組和不一致的分組提供不同的待遇，產生了一些改進的算法，如WEED、RIO等。

算法優缺點

1993年，Floyd 和Jacobson就提出了RED，當時的主要目的是克服“早期隨機丟棄”（Early Random Drop,ERD）網關偏袒突發業務而造成的不公平問題. RED為佇列管理增添了兩種新機制，其一，不是等佇列全滿後再丟棄到來的分組，而是利用機率判定機制事先丟掉部分分組來預防可能發生的擁塞；其二，通過平均佇列而非即時佇列調整分組丟棄機率，由此來儘可能地吸收部分短暫的突發流量。RED算法的性能敏感於設計參數和網路狀況，在特定的網路負載狀況下依然會導致多個TCP的同步，造成佇列震盪，吞吐量降低和時延抖動加劇。RED算法的公平性和穩定性也存在問題。自RED被首次提出來之後，它的參數配置就是一個沒有徹底解決的問題。

雖然RED能夠有效避免擁塞，但是該算法仍然存在以下主要缺陷：

（1）公平性問題

對於不回響擁塞通知的連線，RED算法無法有效處理，因此這樣的連線經常會擠占大量的網路頻寬，導致了各種連線不公平地共享頻寬。

（2）參數設定問題

RED算法對參數設定很敏感，兩個門限值和最大丟包機率的細微變化經常是對網路性能造成很大影響，如果根據具體業務環境選擇最合適的參數是RED存在的一個重要問題。另外，一組參數可能會獲得較高的吞吐量，但是可能也會造成較高的丟包率和較長的時間延遲。如何配置參數，使得算法在吞吐量、時間延遲和丟包率等各方面均獲得較好的性能也有待解決。

（3）網路性能問題

RED算法控制的平均佇列長度經常會隨著連線數目的增加而不斷增大，造成傳輸時延抖動，引起網路性能不穩定。