在網際網路中
像 router 這樣的 intermediate device 其所擁有的資源是有限的
因此 packet buffer 的大小也是有限的
傳統最直接的 discard mechanism 就是 tail drop
因為 buffer 通常以 FIFO queue 來實作
因此若 buffer 還有空位就可以繼續存放 incoming packet
滿了的話就只好把 incoming packet 丟掉囉～
這一丟啊！
sender 端沒收到 receiver 端傳回的 ACK
就會降低封包傳送的速率（windows size）
看起來是網路擁塞唷～
sender 端會嘗試以爬坡的型式增加封包傳送的速率
這就是有名的 slow-start 演算法
當然，若網路順暢，則傳輸速率增快，反之降低
當此 router 所處理的是 multiple TCP stream 的話
若突然有個 bursty traffic 致使 packet loss
將會導致多個 sender 同時降低傳輸速率
然後幾乎以同樣的 time delay 過後再緩慢提升傳輸速率
當提升至一定量後， router 的 queue 再次 overflow
此時多個 sender 再度降低傳輸速率
這樣 sender 傳輸速率的增加和減少幾乎和其他的 sender 都是以同樣的時間在變化
謂之 TCP global synchronization
而 Random Early Detection（RED）可以避免此現象的發生
RED 的演算機制為
incoming packet 的丟棄是以機率來處理
並且此機率和 router 的 buffer 的佔滿率有關
當 buffer 幾乎是空的，封包被丟棄的機率就趨近於零
當 buffer 裡的封包增多時，進來封包被丟棄的機率也就增大
若是某個 sender 傳送了大量封包
想當然爾，遺失的封包會是該 sender 的機率也就愈高
成功避免了 TCP global synchronization
另外一種類似的 packet discard 機制為 Early Packet Discard（EPD）
但這似乎是專屬於 ATM cell
IP 關聯到的是 fragmentation and reassembly
ATM 關聯到的是 segmentation and reassembly
ATM 的 segmentation 是將 AAL5 data packet 切成一個一個的 cell
而 EPD 的精神就是
假設有某個 cell 被丟棄了
其他同屬於某 packet 的 cell 亦將全數同時被丟棄
參考資料：
[1] http://en.wikipedia.org/wiki/Random_early_detection
[2] http://en.wikipedia.org/wiki/TCP_global_synchronization
[3] Network Systems Design using Network Processors, Agere version, Comer, 6.5 and 6.8
留言列表
jubeat 
