WRR/DRR/WFQ

WRR

 

// calculate number of packets to be served each round by connectionsfor each flow f   f.normalized_weight = f.weight / f.mean_packet_sizemin = findSmallestNormalizedWeightfor each flow f   f.packets_to_be_served = f.normalized_weight / min// main looploop   for each non-empty flow queue f      min(f.packets_to_be_served, f.packets_waiting).times do         servePacket f.getPacket

WRR for network packet scheduling was first proposed by Katevenis, Sidiropoulos and Courcoubetis in 1991, specifically for scheduling in ATM networks using fixed size packets (cells). In the more general case of IP networks with variable size packets, in order to approximate GPS the weight factors must be adjusted based on the packet size

WFQ

WFQ选择离开时刻最早的包进行发送。

packet.virFinish = virStart + packet.size / Ri

Ri = R * Wi/(W1+W2+...+Wn)

DRR

Deficit Round Robin, 也叫DWRR

为每个queue分配一个quantum,则该queue的长期总体传输速率为R * Qi/(Q1+Q2+...+Qn)

Variables and Constants   const integer N             // Nb of queues   const integer Q[1..N]       // Per queue quantum    integer DC[1..N]            // Per queue deficit counter   queue queue[1..N]           // The queues   Scheduling Loopwhile (true)    for i in 1..N               if not queue[i].empty()            DC[i]:= DC[i] + Q[i]            while( not queue[i].empty() and                         DC[i] >= queue[i].head().size() )                DC[i]:= DC[i] - queue[i].head().size()                send( queue[i].head() )                queue[i].dequeue()            end while             if queue[i].empty()                DC[i]:= 0            end if        end if    end forend while

Head of Line 和 VOQ

Head of Line

Head-of-line blocking example: The 1st and 3rd input flows are competing to send packets to the same output interface. In this case if the switching fabric decides to transfer the packet from the 3rd input flow, the 1st input flow cannot be processed in the same clock cycle. Note that the 1st input flow is blocking a packet for output interface 3, which is available for processing.

VOQ

the physical buffer of each input port maintains a separate virtual queue for each output port. Therefore congestion on an egress port will block only the virtual queue for this particular egress port. Other packets in the same physical buffer destined to different (non-congested) output ports are in separate virtual queues and can therefore still be processed

SrTcm 和 TrTcm

rfc2697, rfc2698