Queueing algorithms can be evaluated in three quantities: bandwidth, promptness, and buffer space. The most common queueing algorithm used today is first-come-first-servced (FCFS). It simply discards any incoming packets when its buffer is full, and end-nodes could manipulate its implementations to take advantage of the network bandwidth. Furthermore, it lacks promptness for Telnet-like applications.
In order to achieve fairness throughout the network, Nagle proposed a fair queueing (FQ) algorithm that gateways maintain separate queues for each end-node. It lets data flows to take turns transferring packets (round-robin). But the main problem of FQ algorithm is that it implements fairness in the packet number level but doesn't take the packet length in to consideration. Thus, the authors incorporate a buffer allocation policy into the FQ algorithm.
Simulations of FCFS and FQ at the packet level were performed with different flow-control and queueing algorithms. Modified FQ rewards good-willed end-nodes and provides good bandwidth and promptness.
Comments: This paper sort of answers my question in mind when I read the two papers of last session, which factors in malicious end-nodes and smart queueing, instead of simply divides the bottleneck bandwidth into equal amounts for each thru-traffic connections.
I liked that this paper dealt with the malicious end node problem as well. One thing I wondered about though, the router still has to classify all incoming packets, so a misbehaving sender can still make a router do more work. If at some point a router is so overloaded it simply can't classify all the incoming packets and has to resort to something like RED it seems unfriendly nodes could still get more than their fair-share.
ReplyDelete