加权轮询算法

加权轮询（ 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}}}$。