Algorithms


An Introduction to Computer Networks—Queuing and Scheduling

Weighted Round Robin (WRR)

  • In WRR queuing packets are first classified into various service classes such as: real time, interactive and file transfer, and then assigned to a queue that is specifically dedicated to that service class. Each of the queues is serviced in a round robin order and empty queues are skipped. WRR queuing is also referred to as CBQ or custom queuing. wiki

    // calculate number of packets to be served each round by connections
    for each flow f
     f.normalized_weight = f.weight / f.mean_packet_size
    min = findSmallestNormalizedWeight
    for each flow f
     f.packets_to_be_served = f.normalized_weight / min
    // main loop
    loop
     for each non-empty flow queue f
        min(f.packets_to_be_served, f.packets_waiting).times do
           servePacket f.getPacket
    
  • Achieving bandwith allocation among tenants by calculating and providing different pps for them.

Deficit Round Robin (DRR)

  • Description : The DRR scans all non empty queues in sequence. When a non empty queue i is selected, its deficit counter is incremented by its quantum value. Then, the value of the deficit counter is a maximal amount of bytes that can be sent at this turn: if the deficit counter is greater than the packet’s size at the head of the queue (HoQ), this packet can be sent and the value of the counter is decremented by the packet size. Then, the size of the next packet is compared to the counter value, etc. Once the queue is empty or the value of the counter is insufficient, the scheduler will skip to the next queue. If the queue is empty, the value of the deficit counter is reset to 0. wiki

  • Implementation : sch_drr.c
  • Other
  • Extension : Weighted Deficit Round Robin (WDRR)

Max-min (Weighted) Fairness

  • Resource allocation is said to be max-min fair when : first, the minimum data rate that a dataflow achieves is maximized; second, the second lowest data rate that a dataflow achieves is maximized and so on. link
  • Example 1
  • Example 2
  • Max-min weighted

Strict Priority Queuing

  • The highest priority queue is serviced until it is empty, and then the lower priority queues are serviced sequentially until they are empty.
  • Cisco
  • QoS and Queuing

(Weighted) Fair Queuing

  • A byte-weighted fair queuing algorithm—This algorithm attempts to emulate the fairness of bitwise round-robin sharing of link resources among competing flows. Packet-based flows, however, must be transmitted packetwise and in sequence. The byte-weighted fair queuing algorithm selects transmission order for the packets by modeling the finish time for each packet as if they could be transmitted bitwise round robin. The packet with the earliest finish time according to this modeling is the next selected for transmission.wiki
  • Weighted Fair Queueing

      packet.virFinish = virStart + packet.size / Ri
    

Papers


1991

  • Weighted round-robin cell multiplexing in a general-purpose ATM switch chip (WRR) IEEE JSAC’91

1996

1999

  • Matching Output Queueing with a Combined Input Output Queued Switch IEEE JSAC’99

2016

  • Packet Transactions: High-Level Programming for Line-Rate Switches Sigcomm’16
  • Programmable Packet Scheduling at Line Rate Sigcomm’16

2017

  • Titan: Fair Packet Scheduling for Commodity Multiqueue NICs ATC’17

2019

  • Loom: Flexible and Efficient NIC Packet Scheduling NSDI’19