Evaluation of Readings for Week 5.
Point - Counterpoint: FQ vs RED
Fair Queueing Algorithm (by Demers,Keshav,Shenker)
--------------------------------------------------
This algorithm attempts to improve the fairness for all users of the
allocation of gateway resources that include: bandwidth, promptness,
and buffer space. The authors feel that these three metrics can be
independently balanced among users, even though traditional routing
policy has them globbed together as one intertwined issue.
Strengths of the FQ algorithm include:
A) queue priority of a packet is partially based on size, which allows
small ACK packets very quick forwarding.
B) directly penalizes overeager sources that are trying to use more
than their fair share of bandwidth. Charges the user for "bandwidth
packet would have used" even when packet is dropped.
C) Their notion of "fair" has a good common sense perspective to it.
It seems that, if implemented well, no users would feel short changed.
D) Non-uniform dropping of packets, helps minimize synchronization of
source congestion control behaviors.
Weaknesses of the FQ algorithm include:
A) No clear notion of what a "user" really should be, and hard to have
a definition that is fair to all users.
B) No clear way to tell when a user is ending their conversation. How
do they decide when a source-destination pair are "done" without
inspecting the contents of every packet?
C) Doesn't solve congestion by itself; still needs good flow control
at sources.
D) Requires "fast and smart" gateways. May not be feasible or
affordable to build.
E) Puts a high work load on the gateway, to process and prioritize
arriving packets. Large overhead to keep track of all active
conversations.
Main idea: The packets getting through the gateway should be fair.
Does not directly address keeping queues from getting full.
Authors emphasize that they ran many simulations that gave "confusing
results with apparently complicated dynamic effects". In other words,
even they aren't sure how the algorithm behaves in some situations.
Random Early Detection Gateways (by Floyd,Jacobson)
---------------------------------------------------
This algorithm tries to capitalize on the information that a gateway
has direct knowledge about to influence the behaviors of the sources
that are sending packets through the gateway. Directly addresses
queue lengths, with the goal of preventing full queues and selectively
dropping packets to influence source congestion control algorithms.
Strengths of the RED algorithm:
A) designed specifically to work with the TCP congestion control
algorithm.
B) sends direct information to client about congestion (mark or
drop)
C) random drops help avoid the synchronization of window reductions
in TCP algorithms.
D) avoids bias against bursty traffic.
Weaknesses of the RED algorithm:
A) Does not directly confront overeager sources that use excessive
bandwidth.
B) The coefficients in the probability calculation seem suspect.
The authors state that good min/max cutoff values are "left for
further research." The "average queue length" seems to have no
close relationship to the actual queue length. They go to
great lengths to put bounds on these coefficients, but the end
effect of their method looks "just like" the older Random Drop
algorithm.
C) does nothing directly to address fairness of gateway utilization.
Main idea: keep queue lengths short to maximize throughput.
Conclusion
----------
These two algorithms are not incompatible, and could be combined to
provide both fairness and throughput. RED controls what gets into the
queue (storing) and FQ controls the order for leaving the queue
(forwarding).
The big question is how much processing can a gateway inflict on its
packet stream before it hinders overall performance capacity.