加權輪詢算法

加權輪詢（ Weighted round robin ）是網絡中用於調度數據流的算法，也可用於調度進程。

加權輪詢是輪詢調度的一般化。加權輪詢在隊列或一系列任務上循環，每個輪次中各數據包或進程按權重獲得運行機會。

加權輪詢有若干種類，比如經典加權輪詢和交替加權輪詢。

算法

下面以網絡調度程序為例介紹加權輪詢。

假設有$n$個輸入隊列$q_{1},...,q_{n}$。每個隊列$q_{i}$的權重是一個正整數$w_{i}$。使用加權輪詢時，隊列運行過程有周期性。在每個周期中，隊列$q_{i}$有$w_{i}$次發送機會。

不同的加權輪詢算法的區別是在一個周期中如何分配機會。

經典加權輪詢

採用經典加權輪詢算法時，調度程序會在隊列間循環。輪到隊列$q_{i}$時，調度程序開始發送數據包，直到發出$w_{i}$個數據包或遇到隊尾為止。

常量和变量: const N // 队列数 N const weight[1..N] // 每个队列的权重 queues[1..N] // 队列 i // 队列序号 c // 数据包计数器 指令: while true do for i in 1 .. N do c:= 0 while (not queue[i].empty) and (c<weight[i]) do send( queue[i].head() ) queue[i].dequeue() c:= c+1

交替加權輪詢

令$w_{max}=\max\{w_{i}\}$為所有隊列中的最大權重。在交替加權輪詢算法中，每個周期分為$w_{max}$輪。第$r$輪中，如果$r\leq w_{i}$，隊列i可以發送一個數據包。

常量和变量: const N // 队列数 N const weight[1..N] // 每个队列的权重 const w_max queues[1..N] // 队列 i // 队列序号 r // 轮次计数器 指令: while true do for r in 1 .. w_max do for i in 1 .. N do if (not queue[i].empty) and (weight[1..N] >= r)then send( queue[i].head() ) queue[i].dequeue()

示例

經典加權輪詢（CWRR）和交替加權輪詢（IWRR）的調度示例

假設一個系統有三個隊列$q_{1},q_{2},q_{3}$, 其各自的權重$w_{1}=5,w_{2}=2,w_{3}=3$。第一個隊列中有7個數據包A，B，C，D，E，F，G，第二隊列中為3個數據包U，V，W，第三個隊列中有兩個數據包X，Y。且不會有新數據包到達。

如果使用經典加權輪詢算法，在第一個周期中，調度程序首先選擇$q_{1}$並傳送位於隊列頭部的A，B，C，D，E（因為$w_{1}=5$），然後選擇第二個隊列$q_{2}$ ，傳送隊列開頭的U，V（因為$w_{2}=2$），最後選擇第三個隊列，該隊列的權重等於3，然而該隊列一共只有兩個數據包，因此傳輸X，Y 。在Y的傳輸完畢後，第二個周期開始，先是發送$q_{1}$中的F，G，然後是$q_{2}$中的W。

如果使用交替加權輪詢算法，第一個周期分為5輪。第一輪（r = 1），每個隊列發送一個數據包（A，U，X），第二輪（r = 2），每個隊列再發送一個數據包（B，V，Y），第三輪（r = 3），僅排隊$q_{1},q_{3}$被允許發送數據包（$w_{1}>=r$，$w_{2}<r$ 和 $w_{3}>=r$），但由於$q_{3}$為空，只有來自$q_{1}$的C被發送，在第四和第五輪，只有D，E從$q_{1}$被發送。然後開始第二個周期，依次發送F，W，G。

任務調度

與數據包調度類似，加權輪詢完成任務或進程調度時：$n$個現行任務以循環方式安排，每個任務$\tau _{i}$得到$w_{i}$份的處理器時間 。

性質

調度數據包時，如果所有數據包都具有相同的大小，則WRR是通用處理器共享算法的近似：長期來看，隊列$q_{i}$將占據${\frac {w_{i}}{\sum _{j=1}^{n}w_{j}}}$的帶寬（假設所有隊列均處於現行狀態）。

如果數據包長度可變，則每個隊列接收的帶寬部分不僅取決於權重，還取決於數據包大小。

如果隊列$q_{i}$的平均數據包大小是$s_{i}$，則每個隊列將獲得的長期帶寬份額等於${\frac {s_{i}\times w_{i}}{\sum _{j=1}^{n}s_{j}\times w_{j}}}$ 。如果目標是給每個隊列$q_{i}$分配連結容量的$\rho _{i}$（ $\sum _{i=1}^{n}\rho _{i}=1$ ），則可以設置權重$w_{i}={\frac {\rho _{i}}{s_{i}}}$。