Wednesday, September 10, 2008

Analysis and Simulation of a Fair Queuing Algorithm

Congestion control/avoidance has to be addressed in totality, and has to include routers along with the end-hosts. This paper does a very good job of presenting the context and providing a clear motivation. Traditional FIFO processing by routers is susceptible to a take-over by one of the sources, unfairly. Fair Queuing aims to equally divide the resources of a router among all the flows. The ideal algorithm would process bit by bit across all the flows in a round robin manner. The paper presents an approximation of the algorithm by a packetized scheduling scheme. This is done by calculating when packets would have finished being sent in the ideal algorithm, and scheduling them in that order.


1. I liked the fact that this paper is motivated by nodes misbehaving and taking over resources.

2. By introducing sophistication in scheduling, this paper seems to nicely set things up for reserving resources on the router for scheduling algorithms to kick in (QoS).

a. As a minor point, SIFF, a paper that counters DoS attacks, uses principles suggested in this paper.

3. Despite being a nice paper, I wouldn’t want to keep it in the reading list because of the limited slots available. Given that the algorithm is intuitive, I think we can directly read CSFQ along with a quick background read of Fair Queuing.

No comments: