red

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

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

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

2）避免全局同步現象；

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

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

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

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

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）算法將隊列的平均隊長作為決定擁塞避免機制是否應被處罰的隨機函數的參數，增加了在隊列長度變得太大之前平滑瞬時擁塞的可能性，減少了同時使多個流受分組丟棄影響的可能性。 ^[1] 

下圖是一個RED丟棄概率函數的例子

當隊列長度小於低的門限值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被首次提出來之後，它的參數配置就是一個沒有徹底解決的問題。 ^[2] 

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

（1）公平性問題

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

（2）參數設置問題

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

（3）網路性能問題

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