From: Lillie Kittredge (kittredl@u.washington.edu)
Date: Mon Oct 25 2004 - 07:37:00 PDT
Fair queueing
Demers, Keshav & Shenker
This paper discusses the role of queueing algorithms in gateway congestion
avoidance. It proposes the Fair Queueing algorithm, which resolves some
of the shortcomings of first come, first serve.
The authors note that in FCFS gateways, the matters of bandwidth
allocation, promptness and buffer space are all dependent on each other.
Further, packet delay depends directly on the total queue size, allowing
one user to easily foul things up for everybody else.
The algorithm keeps a separate queue for each flow. The most fair flow
control would be to send data bit by bit in a round robin from these
queues, but alas that would be ridiculous. The authors instead use a
packet by packet round robin, emulating the bit-by-bit. This way, if any
one flow attempts to hog bandwidth, it just makes its own queue longer.
This paper leaves unresolved the question of defining users. The tension
between source, flow, application, and thread of application make it
tricky to say where the user lies. Where opening multiple streams can be
a way to hog bandwidth, I know that I do it just to multitask - load one
page while I'm reading another. I've found I do this a lot with tabbed
browsers; I think this is an interesting example of user applications
changing data flow patterns.
This archive was generated by hypermail 2.1.6 : Mon Oct 25 2004 - 07:37:01 PDT