Fair queuing

In the context of network scheduling, fairness has multiple definitions. Nagel's article uses round-robin scheduling of packets,[2] which is fair in terms of the number of packets, but not on the bandwidth use when packets have varying size. Several formal notions of fairness measure have been defined including max-min fairness, worst-case fairness,[6] and fairness index.[7]

The initial idea gives to each flow the same rate. A natural extension consists in letting the user specify the portion of bandwidth allocated to each flow leading to weighted fair queuing and generalized processor sharing.

Modeling of actual finish time, while feasible, is computationally intensive. The model needs to be substantially recomputed every time a packet is selected for transmission and every time a new packet arrives into any queue.

To reduce computational load, the concept of virtual time is introduced. Finish time for each packet is computed on this alternate monotonically increasing virtual timescale. While virtual time does not accurately model the time packets complete their transmissions, it does accurately model the order in which the transmissions must occur to meet the objectives of the full-featured model. Using virtual time, it is unnecessary to recompute the finish time for previously queued packets. Although the finish time, in absolute terms, for existing packets is potentially affected by new arrivals, finish time on the virtual time line is unchanged - the virtual time line warps with respect to real time to accommodate any new transmission.

The virtual finish time for a newly queued packet is given by the sum of the virtual start time plus the packet's size. The virtual start time is the maximum between the previous virtual finish time of the same queue and the current instant.

With a virtual finishing time of all candidate packets (i.e., the packets at the head of all non-empty flow queues) computed, fair queuing compares the virtual finishing time and selects the minimum one. The packet with the minimum virtual finishing time is transmitted.

Shared variables
    const N             // Nb of queues 
    queues[1..N]        // queues
    lastVirFinish[1..N] // last virtual finish instant

receive(packet)
     queueNum := chooseQueue(packet)
     queues[queueNum].enqueue(packet)
     updateTime(packet, queueNum)

updateTime(packet, queueNum)
    // virStart is the virtual start of service
    virStart := max(now(), lastVirFinish[queueNum])
    packet.virFinish := packet.size + virStart
    lastVirFinish[queueNum] := packet.virFinish

send()
     queueNum := selectQueue()
     packet := queues[queueNum].dequeue()
     return packet

selectQueue()
     it := 1
     minVirFinish = ${\displaystyle \infty }$
     while it ≤ N do
         queue := queues[it]
         if not queue.empty and queue.head.virFinish < minVirFinish then
             minVirFinish = queue.head.virFinish
             queueNum := it 
         it := it + 1
     return queueNum

The function receive() is executed each time a packet is received, and send() is executed each time a packet to send must be selected, i.e. when the link is idle and the queues are not empty. This pseudo-code assumes there is a function now() that returns the current virtual time, and a function chooseQueue() that selects the queue where the packet is enqueued.

The function selectQueue() selects the queue with the minimal virtual finish time. For the sake of readability, the pseudo-code presented here does a linear search. But maintaining a sorted list can be implemented in logarithmic time, leading to a O(log(n)) complexity, but with more complex code.