From: Shobhit Raj Mathur (shobhit@cs.washington.edu)
Date: Sun Oct 24 2004 - 13:48:10 PDT
Analysis and Simulation of a Fair Queueing Algorithm
====================================================
This paper proposes modifications to Nagle's Fair Queueing Algorithm(FQ) and then compares its performance mainly with the FCFS
algorithm. FQ performs much better than FCFS when compared to fair allocation of bandwidth, lower delay for sources using less than
jtheir full share of bandwidth and protection from ill-behaved sources. On
the whole, FQ delivers satisfactory performance in a wide
variety of network scenarios and is much better than the naive FCFS algorithm.
This paper correctly identifies the deficiencies(packet size etc.) in
Nagles' approach and corrects them. It uses a source-destination pair to
represent a 'user' which seems to be the best available option for
bandwidth and buffer space allocation. It attempts to find a practical
match for the ideal bit-by-bit round robin(BR) transmission scheme. For
this purpose it proposes a non-preemptive packetized algorithm that uses
the finishing time of a packet according to BR to order the outgoing
queue. It also proposes an algorithm for promptness, which results in
lesser delay to users who utilize less than their fair share of bandwidth.
The authors choose to simulate their algorithm on a network which consists
of Telnet and FTP conversations. This scenario is not sufficient and the
authors agree to this. A wider variety of applications(like streaming
media, web browsing etc.) would make the results more relevant. The
results suggest that FQ is definitely better than FCFS and when combined
with the DECbit algorithm the performance of FQ improves.
Irrespective of the experimental results, the paper convinces the reader
that FQ is a viable alternative to FCFS. The internet today has many
malicious and non-cooperating users, FQ attempts to provide fair
allocation of bandwidth in such an environment. This is a big leap from
the FCFS queueing algorithm which makes the inadmissible assumption of
cooperating users and fails miserably in non-cooperating scenarios. Among
the 3 goals that the paper had, it does well on proposing the modified FQ
and providing a rigorous understanding of the proposed algorithm. It
doesn't do very well in the performance evaluation section, but the
results are sufficient to claim that FCFS is not adequate and that FQ
addresses the major concerns. I liked the game-theoretic analysis of FQ,
according to which users are rewarded for devising more sophisticated and
responsive algorithms. As the paper says, FQ algorithms make
self-optimizing source behavior result in fair, protective,
non-manipulable and stable networks. Coupled with the fact that no changes
in flow control algorithms are required and that gateways have enough
computing resources today, this is more than sufficient incentive to
implement FQ in the gateways.
In future, Weighted FQ can be used to provide simple QoS guarantees
without changing the underlying internet architecture. This is an simple
extension to FQ and has many useful consequences, though it does not solve
the problem of QoS completely.
This archive was generated by hypermail 2.1.6 : Sun Oct 24 2004 - 13:48:10 PDT