隊列調度

在網絡上傳送業務時，隊列調度實現網絡中的中繼節點和路由器如何從一個或多個數據包隊列中選擇一個待轉發的隊列。

常用的隊列調度算法有以下3種：SP（Strict Priority，嚴格優先級）、RR（Round Robin，循環調度）和WRR（Weighted Round Robin，加權循環調度算法）。

原理：對不同的隊列設置不同的優先級，優先級高的隊列絕對優先於優先級低的隊列，只要優先級高的隊列中有數據包存在，優先調度優先級高的隊列。

如下圖所示，假設隊列優先級從高到底的排序為：隊列0>隊列1>隊列2>隊列3。

各隊列的數據包存儲情況如上圖所示，現在開始進行隊列的調度。

1）.因為隊列0有數據包存在，優先調度隊列0，直至隊列0的數據包調空為止。然後調度隊列1。

2）. 隊列0和隊列1的數據包均空的情況下，調度隊列2 。

3）. 隊列0、隊列1、隊列2的數據包均空的情況下，調度隊列3 。

採用SP調度算法時，只要高優先級隊列中有數據包，低優先級隊列便得不到調度。但實際情況經常是高優先級的業務可能會一直存在，那麼隊列永遠不會為空，結果低優先級的隊列永遠得不到調度，例子中隊列3的得不到調度的情況尤其惡劣。

優點：配置簡單，絕對保證高優先級應用的帶寬。

缺點：不能保證高優先級外的服務得到合理帶寬，甚至會餓死，從而不能公平地保證各種應用的服務質量。

原理：依次調度各隊列的數據包，重複一個又一個週期。這是一個絕對公平的調度算法。

在所有隊列的數據包都可以調度的情況下，RR算法的調度過程如下圖所示。

優點：絕對公平。

缺點：分不清輕重緩急，高優先級的數據包得不到優先調度。

原理：設置一個權重表，通過對權重表的分配可以較多的調度優先級高的隊列。

假設我們配置的權重表如下表所示，從表中我們可以看出配置隊列0：隊列1：隊列2：隊列3的權重為6：4：3：2 。

根據權重表的配置，我們先查看最左邊第一個配置的隊列，此時隊列為2，那麼如果隊列2非空，我們就優先調度隊列2，隊列2空的情況下，指針下移至權重表下一個配置。隊列2調度完成後，指針指向隊列0，那麼優先調度隊列0，然後指針繼續下移。指針下移至權重表最後一個配置後，指針移至權重表第一個配置，新一個調度週期開始。

假設隊列0-隊列3所有隊列非空，那麼一個WRR調度週期的輸出隊列情況如下圖所示。