(no subject)

This paper presents a so-called "Fair Queuing" algorithm that
allocates bandwidth and router buffer space fairly, where fairness is
defined as giving no user greater resources than requested, providing
the largest possible allocation to the user with the smallest
allocation, and if the smallest user is recursively removed providing
the largest possible allocation to each of the next smallest users.
This seems like a reasonable definition of fairness.

The paper describes the pros and cons of a number of different
definitions of a "user", before eventually settling upon each source-
destination pair as a distinct user. While I am convinced that this
is the correct choice to ensure fairness and prevent malicious
behaviour, it results in a very large number of users, which could
potentially lead to implementation difficulties.

The fair queuing algorithm is designed to determine the time at which
each packet would finish in a bit-by-bit round-robin queuing scheme,
which would be perfectly fair, but impossible in reality, and always
transmit the packet with the lowest theoretical finishing time first,
ensuring that packet orderings are the same as in a theoretically
fair system. Pre-emptive and nonpreemptive versions are discussed,
although only the nonpreemptive version would be feasible.

The paper looks at the behaviour of the Fair Queuing (FQ) and First
Come First Served (FCFS) algorithms in various toy networks with a
range of end-to-end congestion control mechanisms and determine that
in general FQ is much more fair and tends to reward more advanced and
fairer congestion control mechanisms.

My primary concern with this paper, and this issue is actually
mentioned by the authors, is that they have no idea how FQ might
actually be implemented efficiently in real routers. I believe the
paper would be made stronger by a simulated comparison of FQ and
Nagle's algorithm, which seems much more easily implemented. If
Nagle's algorithm performs similarly to FQ, then there is not a
strong case for FQ's level of complexity, whereas if Nagle's
algorithm shows considerably less fairness, then efforts to implement
FQ may be worthwhile.
Received on Wed Sep 27 2006 - 22:53:05 EDT