Tail-Drop

在介紹Drop Tail之前，我們先介紹兩種傳統的包的調度策略-決定包的傳送順序。

FIFO (First In First Out，先進先出)是一種經典的包調度策略，它的最大優點在於實施起來簡單。FIFO又叫“先到先服務”(FCFS)，即第一個到達路由器的數據包首先被 傳輸。FIFO的問題在於在排隊的時候沒有考慮包的重要程度，對FIFO排隊的一個簡單改進是優先順序排隊。基本思想是給每個數據包分配一個優先順序標誌。這 個優先順序標誌可以放在IP數據包內。路由器則執行多個FIFO排隊。一個隊列對應一個優先順序。路由器在排隊的時候總是給優先順序高的隊列先排隊。在同一優先 級隊列中，數據包仍按FIFO排隊。

公平排隊演演算法(Fair Queue FQ)是FIFO的一種改進。FIFO排隊的主要問題是無法區分不同的數據流。由於整個TCP的擁塞控制是在源端執行，而FIFO排隊不提供約束所有數據 源遵守擁塞控制的機制，這就有可能讓行為不良的數據流強佔大量帶寬。在Internet環境中，某個應用不使用TCP協議是完全可能的。結果，它可以繞開 端到端的擁塞控制機制，向路由器任意發送自己的數據包，從而引起其它應用的包被丟棄。FQ演演算法則解決了這個問題。在FQ演演算法中，路由器對每個輸出線路有一 個排隊隊列。路由器按“輪詢”方式處理包。當一條線路閑時，路由器就來回掃描所有隊列，依次將每隊每一個包發出。當某個流的數據包到達過快時，其隊列就會 很快佔滿，屬於這個流的新到的數據包就會被丟棄。採用這種方式，每個數據流就不可能犧牲其它數據流而多佔資源。另外，FQ演演算法並沒有告知源端路由器狀態的 機制，也就是說，FQ仍然要依賴於端到端的擁塞控制機制。它只是將數據流分隔，使不遵守擁塞控制機制的數據流不至於影響其它流。所以它在沒有犧牲統計復用 的情況下提供了公平性，與端到端的擁塞控制機制也可以較好地協同。

傳統的隊列長度管理機制是“去尾”( Drop Tail )。它有點類似於FIFO(先入先出)的存儲方式。Drop Tail最大的優點是原理簡單。當路由器隊列長度達到最大值時，通過丟包來指示擁塞，先到達路由器的分組首先被傳輸。由於路由器緩存有限，如果包到達時緩 存已滿，那麼路由器就丟棄該分組。一旦發生丟包，發送端立即被告知網路擁塞，從而調整發送速率。這種做法不考慮被丟棄包的重要程度。

Drop Tail仍是目前Internet使用最為廣泛的分組排隊、丟棄的方式。這種方式將擁塞控制的責任都推給網路邊緣。所以TCP假定網路中的路由器對擁塞控制不起任何作用，而獨自承擔檢測和響應擁塞的全部責任。

基於Drop Tail的一種改進演演算法是優先順序排隊。它的基本思路是將每個分組分配一個優先順序標誌。路由器則執行多個隊列排隊。一個隊列對應一個優先順序。路由器總是優先傳輸非空的最高優先順序隊列。在同一優先順序隊列中，分組仍按Drop Tail方式管理。

優先順序排隊的主要問題是最高優先順序隊列能“搶佔”其它所有的隊列。只要高優先順序隊列非空，低優先順序隊列就得不到服務。所以，不能允許用戶不受控地指定高優 先級。同時，Drop Tail無法“識別”面向連接的TCP流，所以對它們的公平性較差，對上層TCP快速恢復的效率也很低。

除了這些，它在具體實施過程中也存在著很多其它的弊端。如；若緩衝器很長，則每個分組所經歷的延遲就會增大：而若緩衝器很短的話，又不能夠適應突發性數據流；另外，全局同步的發生又將直接導致吞吐率的減小，等等。所有這些都可能引起網路崩潰。