跳转到内容

加权轮询算法

维基百科,自由的百科全书

加权轮询Weighted round robin )是网络中用于调度数据流的算法,也可用于调度进程

加权轮询[1]轮询调度的一般化。加权轮询在队列或一系列任务上循环,每个轮次中各数据包或进程按权重获得运行机会。

加权轮询[2]有若干种类,比如经典加权轮询和交替加权轮询。

算法

[编辑]

下面以网络调度程序为例介绍加权轮询。

假设有个输入队列。每个队列的权重是一个正整数。使用加权轮询时,队列运行过程有周期性。在每个周期中,队列次发送机会。

不同的加权轮询算法的区别是在一个周期中如何分配机会。

经典加权轮询

[编辑]

采用经典加权轮询算法时[2][3],调度程序会在队列间循环。轮到队列时,调度程序开始发送数据包,直到发出个数据包或遇到队尾为止。

常量和变量: 
    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

交替加权轮询

[编辑]

为所有队列中的最大权重。在交替加权轮询算法中[1][4],每个周期分为轮。第轮中,如果,队列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)的调度示例

假设一个系统有三个队列, 其各自的权重。第一个队列中有7个数据包A,B,C,D,E,F,G,第二队列中为3个数据包U,V,W,第三个队列中有两个数据包X,Y。且不会有新数据包到达。

如果使用经典加权轮询算法,在第一个周期中,调度程序首先选择并传送位于队列头部的A,B,C,D,E(因为),然后选择第二个队列 ,传送队列开头的U,V(因为),最后选择第三个队列,该队列的权重等于3,然而该队列一共只有两个数据包,因此传输X,Y 。在Y的传输完毕后,第二个周期开始,先是发送中的F,G,然后是中的W

如果使用交替加权轮询算法,第一个周期分为5轮。第一轮(r = 1),每个队列发送一个数据包(A,U,X),第二轮(r = 2),每个队列再发送一个数据包(B,V,Y),第三轮(r = 3),仅排队被允许发送数据包(),但由于为空,只有来自C被发送,在第四和第五轮,只有D,E被发送。然后开始第二个周期,依次发送F,W,G

任务调度

[编辑]

与数据包调度类似,加权轮询完成任务或进程调度时:个现行任务以循环方式安排,每个任务得到份的处理器时间[5][6]

性质

[编辑]

调度数据包时,如果所有数据包都具有相同的大小,则WRR是通用处理器共享算法的近似[7]:长期来看,队列将占据的带宽(假设所有队列均处于现行状态)。

如果数据包长度可变,则每个队列接收的带宽部分不仅取决于权重,还取决于数据包大小。

如果队列的平均数据包大小是,则每个队列将获得的长期带宽份额等于 。如果目标是给每个队列分配链接容量的 ),则可以设置权重

参考文献

[编辑]
  1. ^ 1.0 1.1 Katevenis, M.; Sidgiropoulos, S.; Courcoubetis, C. Weighted round-robin cell multiplexing in a general-purpose ATM switch chip. IEEE Journal on Selected Areas in Communications. 1991, 9 (8): 1265–1279. ISSN 0733-8716. doi:10.1109/49.105173. 
  2. ^ 2.0 2.1 Chaskar, H.M.; Madhow, U. Fair scheduling with tunable latency: A round-robin approach. IEEE/ACM Transactions on Networking. 2003, 11 (4): 592–601. ISSN 1063-6692. doi:10.1109/TNET.2003.815290. 
  3. ^ Brahimi, B.; Aubrun, C.; Rondeau, E. Modelling and Simulation of Scheduling Policies Implemented in Ethernet Switch by Using Coloured Petri Nets: 667–674. 2006. doi:10.1109/ETFA.2006.355373. 
  4. ^ Semeria, Chuck. Supporting Differentiated Service Classes: Queue Scheduling Disciplines (PDF) (报告): 15–18. [4 May 2020]. (原始内容存档 (PDF)于2017-08-29). 
  5. ^ Beaulieu, Alain. Real Time Operating Systems -- Scheduling & Schedulers (PDF). Winter 2017 [4 May 2020]. [失效链接]
  6. ^ 20190266019 
  7. ^ Fall, Kevin. EECS 122, "Introduction to Communication Networks", Lecture 27, "Scheduling Best-Effort and Guaranteed Connections". 29 April 1999 [4 May 2020]. (原始内容存档于2012-07-22).