Readings for Lecture Sep 11, 2008

Analysis and Simulation of a Fair Queueing Algorithm

The queueing algorithms allocate three nearly independent quantities: bandwidth, promptness and buffer space. The first come first served (FCFS) queueing algorithm is not adequate to prevent ill-source from sending data to gateway at sufficiently high speed to capture all or high fraction of bandwidth. The fair queueing (FQ) algorithm proposed by Nagle can handle this issue by maintaining separate queues for packets from each individual source so each source cannot interfere with other sources.

However, Nagle’s proposal does not really satisfy the fairness in bandwidth since a source using long packets gets more bandwidth than a source using short packets. Additionally, static round-robin ordering violates the continuity requirement.

The max-min fairness states that an allocation is fair if: no user gets more than it requests, users with demand lower than average allocation resource get their demand and removed from list, users with demand higher than the average demand left get equal share of resource.

The straightforward bit-by-bit round-robin algorithm in which each time slot is given to one bit from one source sequentially is not realistic. The alternative way of implementing this algorithm is to collect all bits of one packet from one source and transmit the packet of a source with the smallest number of bits transmitted plus the number of bits in the packet, say F. This algorithm is thus emulating the bit-by-bit round robin. The preemptive version of this algorithm, newly arrived packet with smaller F will preempt the transmitting of the current transmitting packet.

Queueing non-negative delay δ is added to help inactive conversations have faster service. Now the sending order is determined by B¬i = Pi+max(Fi, R(ti) - δ), not Fi anymore. If a conversation is active then R(ti) ≤ Fi, thus δ has no effect to active conversations. In inactive conversations, R(ti) > Fi, the previous history of the source is taken into account.

This algorithm is complex in the sense that it has to keep state for each flow through a gateway, which is hard, and then the number of flows is large. Another issue is that how a gateway knows when a flow terminates so that it can clear the information about that flow.

Core-stateless Fair Queueing Architecture Achieving Approximately Fair Bandwidth Allocations in High Speed Network

To reduce the complexity of fair queueing (FQ) algorithm, an architecture call core-stateless FQ (CSFQ) can be used. In that architecture, only edge router maintain per flow state by estimating the incoming rate of each flow and insert a label into each packet header based on this estimation. Core routers maintain no per state; instead they use FIFO scheduling augmented by a probabilistic dropping algorithm that uses the packet labels and an estimate of the aggregate traffic at the router.

In an ideal model, fluid models, which are bufferless, the arrival rates, ri(t) of packets are supposed to know exactly and flows are modeled as a continuous stream of bits. The max-min bandwidth for flow i is a rate given by min(ri(t), ∝(t)), where ∝(t) is the fair share rate of the server. If the total arrival rate A(t) = Σri(t) is less than the output link speed C, then no bit is dropped. Otherwise bits from flows i that have ri(t) > ∝(t) will be dropped with the probability of max( 0, 1 - ∝(t)/ri(t)).

The packet algorithm is extended from the above algorithm with packetized transmission and buffering mechanism. The flow arrival rate is not fixed, instead it is estimated the flow rate of each flow in the form of e-T/K. The estimated aggregate arrival rate A is also estimated in the form e-T/K. This CSFQ can be continued to extend to support flows with different weights.
The flow rate is not fixed and supposed an exponential form that helps the estimated rate converge to real rate and allows to bound the excess service. The size of each island also needs more consideration in detail since this can affect the latency of the systems.

The paper does not discuss the latency of the approach while this can be a major issue for realtime-distributed systems. This architecture can be extend for future research to handle real time system communications in that edges router will not only estimate the flow but also classifies packets according to some patterns such that it still preserve the order of packets.