A. Demers, S. Keshave, and S. Shenker, “Analysis and simulations of a fair queueing algorithm,” in Proc. ACM SIGCOMM‘89, Austin, TX, 1989, pp. 1–12.
As it is not possible to ensure an ethical and fair usage of network resources by only trusting the end nodes, the network gateways need to support fair resource allocation when it is desired. In other words, a fair and proper congestion avoidance algorithm needs the involvement of network and end users simultaneously and otherwise it is not possible.
The authors of this paper, propose a modification to the first fair queuing algorithm proposed by Nagle (1987) which further satisfies the design requirements they had envisioned for any such fair scheme (fair bandwidth, fair buffer space and continuity of service). Nagle proposed servicing distinct queues (one queue per flow) by a round-robin scheduler per packet basis which fails to allocate BW fairly when packet sizes can be different. The modified FQ algorithm tries to emulate a bit-by-bit round-robin scheduler (BR) by computing the end service time of each packet as it arrives similar to BR but servicing them per packet basis instead of per bit basis (servicing the packet with the earliest service time first).
It is interesting to know that in many of today's high speed routers, packets are divided into equal size cells at the input, processed internally and then reassembled at the output. This might mean that enforcing fairness and priorities over variable packet sizes is still hard to implement after 20 years. Even though the papers result is nice, the single size cell approach is still the dominant method in high speed routers. It would be interesting to better understand why after 20 years (from the publication of this paper) still it is preferred to work with single size packets?
Another very interesting point in this paper is that the proposed FQ algorithm discourages the ill-behaved sources by dropping their packets while counting them towards their BW usage! I find this very interesting and effective from game theoretic point of view. In overall I found this paper to be a great mixture of intuition, analysis, simulation and effective results and therefore I would suggest it to be kept in the syllabus.
As it is not possible to ensure an ethical and fair usage of network resources by only trusting the end nodes, the network gateways need to support fair resource allocation when it is desired. In other words, a fair and proper congestion avoidance algorithm needs the involvement of network and end users simultaneously and otherwise it is not possible.
The authors of this paper, propose a modification to the first fair queuing algorithm proposed by Nagle (1987) which further satisfies the design requirements they had envisioned for any such fair scheme (fair bandwidth, fair buffer space and continuity of service). Nagle proposed servicing distinct queues (one queue per flow) by a round-robin scheduler per packet basis which fails to allocate BW fairly when packet sizes can be different. The modified FQ algorithm tries to emulate a bit-by-bit round-robin scheduler (BR) by computing the end service time of each packet as it arrives similar to BR but servicing them per packet basis instead of per bit basis (servicing the packet with the earliest service time first).
It is interesting to know that in many of today's high speed routers, packets are divided into equal size cells at the input, processed internally and then reassembled at the output. This might mean that enforcing fairness and priorities over variable packet sizes is still hard to implement after 20 years. Even though the papers result is nice, the single size cell approach is still the dominant method in high speed routers. It would be interesting to better understand why after 20 years (from the publication of this paper) still it is preferred to work with single size packets?
Another very interesting point in this paper is that the proposed FQ algorithm discourages the ill-behaved sources by dropping their packets while counting them towards their BW usage! I find this very interesting and effective from game theoretic point of view. In overall I found this paper to be a great mixture of intuition, analysis, simulation and effective results and therefore I would suggest it to be kept in the syllabus.
No comments:
Post a Comment