From: Susumu Harada (harada@cs.washington.edu)
Date: Thu Oct 21 2004 - 00:13:32 PDT
"Analysis and Simulation of a Fair Queueing Algorithm"
A. Demers, S. Keshav, and S. Shenker
This paper presents a modification to Nagle's queueing algorithm for
network gateways and compares it under simulated environments against the
standard first-come-first-serve (FCFS) queueing, combining each with
various flow control mechanisms. The paper concludes that their
algorithm, based on fair queueing (FQ), combined with certain flow control
mechanisms such as DECbit, yielded significantly better results than FCFS
in terms of the two metrics they present, namely fairness and promptness.
They use the definition of fariness based on the max-min fairness
criterion, and also define the notion of a unit of "user" on a gateway as
one source-destination pair, or conversation. The notion of promptness is
defined under the goal that the delay experienced by the user should
depend as little as possible on the timing of their packet arrival.
They point out that the problem with the simple FCFS algorithm is that
they place too much faith on the hosts to adopt a proper flow control
algorithm, leaving room for abuse by malicious or malfunctioning hosts.
They also point out that Nagle's algorithm ignores packet length when
going about its round robin servicing, leading to sources sending longer
packets getting more bandwidth.
Their novel proposal is the modification to Nagle's round robin policy,
which approximates the behavior of a bit-by-bit round robin (BR) policy by
calculating the hypothetical finishing time (F) for each service's packet
under BR and letting the one with the least F preempt currently
transmitting packet if the latter's F is larger. They also add a
parameter to take into consideration the rate at which the user is sending
the packets, allowing those using less bandwidth than their fair share to
receive more prompt service.
I thought the idea presented in this paper was quite intriguing, to see
how a gateway can enforce fair sharing of its resource even in the
presence of non-cooperating hosts. I especially like the fact that the
little nice guys get to occasionally cut the line to the front.
I wonder if there is a way to exploit this mechanism if the host
somehow makes their packet small enough such that their finish time is
earlier than most other packets (although this would probably not lead to
any increase in throughput since the header to data overhead ratio would
grow beyond any gain made by more packets getting through.
This archive was generated by hypermail 2.1.6 : Thu Oct 21 2004 - 00:13:33 PDT