I had to do a literature/paper review as part of one of my courses (EE6902 Computer Communication Networks). I selected a queue management algorithm for internet routers which is R. Pan, B. Prabhakar and K. Psounis, “CHOKe: A stateless active queue management scheme for approximating fair bandwidth allocation”, IEEE Infocom 2000. It is a very interesting paper considering the fact that it was published nearly a decade ago. This is one of the very few ideas I have come across and thought, "Why haven't I thought about this before?" I am not attaching the whole paper here (it’s around 20 pages), but the summary part of my paper review. In a nutshell, I my review is “This is an excellent research paper in all aspects such as the organization of the contents, quality and quantity of the content. One can easily deduce both by reading the paper and by looking at the later works that are based on this paper, that this paper is the result of an extensive and painstaking research and also an important milestone in this field.”
1. Introduction
Congestion control has always been a topic of interest among network designers and engineers. This paper proposes a simple and elegant method of implementing congestion control in internet routers which incorporates both fairness and simplicity. The main motivation behind this work is the need for a simple stateless algorithm that can achieve flow isolation and/or approximate fair bandwidth allocation for internet routers.
The authors start off by presenting the difference between responsive and unresponsive flows and different models for congestion control. During the time of congestion in a router, a responsive flow (TCP based) adjusts its rate automatically where an unresponsive flow (UDP or a bad TCP implementation), will be impassive to the conditions in the router and aggressively use up more bandwidth than responsive flows. This shows the need for fairness while choosing a packet to keep/drop during the time of congestion.
The models for congestion control fall broadly in to two categories. 1. Scheduling algorithms and 2. Queue management algorithms. The scheduling algorithms drop packets depending on the state information of each flow stored locally and therefore results in a fairer bandwidth allocation. But they are expensive to implement in terms of computational complexity and storage required and naturally doesn’t scale well. Various implementations are Fair Queue (FQ), Core Stateless Fair Queuing (CSFQ), and Stochastic Fair Queuing (SFQ). The queue management algorithms are stateless and are simple to implement at the expense of fairness. The main algorithm in this category is Random Early Detection (RED) [2]. Even if RED solves some of the issues with drop tail mechanism, it doesn’t provide fairness among responsive and unresponsive flows. Other variations are RED with penalty box, Flow RED (FRED) etc which requires partial state information and Stabilized RED (SRED) which identified misbehaving flows but doesn’t provide a mechanism to penalize them.
CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for unresponsive flows) proposed here incorporates fairness similar to that of scheduling algorithms while keeping the simplicity of a queue management algorithms. When a packet arrives at a congested router, CHOKe draws a packet at random from the queue and compares it with the arriving packet. If they both belong to the same flow, both are dropped, else the randomly chosen packet is left intact and the arriving packet is admitted in to buffer with a probability of p (calculated in the same way as in RED). 2 main ideas drive the usage of this technique. 1. The likelihood of the randomly chosen packet belonging to a misbehaving flow is high. 2. A packet belonging to a misbehaving flow is more likely to trigger a comparison since they arrive more frequently.
2. CHOKe Algorithm
CHOke marks two thresholds in the FIFO buffer, minth and maxth. The algorithm is self-explanatory from figure 1.
Figure 1: The CHOKe algorithm
In general, one can randomly choose any number of packets from the buffer (drop candidate) for the comparison (m ≥ 1). CHOKe’s performance will increase as m increases especially when there are multiple malicious flows. The selection of value of m can be automated by having any number of intermediate thresholds and choosing different value for m depending on threshold (linearly).
The implementation details are also discussed and showed verbally that only a small overhead is associated in implementing CHOKe as compared to RED.
3. Simulation Results
A standard network configuration is used to test the performance of CHOKe and compare it with RED and Drop Tail mechanisms as their complexities are close to that of CHOKE. The simulation results are presented in 3 parts: single congested link, multiple congested links and multiple congested flows.
As expected, CHOKe outperforms RED and Drop Tail in UDP throughput comparison where the latter 2 doesn’t discriminates against unresponsive flows. The throughput per flow of CHOKe is also shown where the TCP throughput reaches near the ideal fairness values. Other simulation results presented include performance under different traffic loads and queue distribution under different loadings. Similar simulation results are presented for other 2 parts.
4. Analytical Models
In this section, the authors analyze 3 different versions of CHOKe. 1. Original CHOKe, 2. Front CHOKe (drop candidate is always the packet at the head of the queue) and 3. Back CHOKe (drop candidate is always the packet at the tail of the queue). The second and third variations are used because of the difficulty of analysis of the original model.
Both the models assume independent Poisson arrivals and independent exponential service times with a FIFO queuing discipline. The models depend on the PASTA property to arrive at the results. In the case of front CHOKe, the throughput with 1, 2 and 3 flows are calculated from the analytical models and are presented along with the simulation results which are almost identical. In the case of back CHOKe, they use Markov chains to find the stationary distribution, πi. The throughput for various flows calculated from the mathematical model is presented.
5. Conclusion
The paper proposes a packet dropping scheme which is simple to implement and also maintains fair queuing among responsive and unresponsive flows. Simulation and analytical models and results are also presented to support the claims.
6. Reference
[1] R. Pan, B. Prabhakar and K. Psounis, “CHOKe: A stateless active queue management scheme for approximating fair bandwidth allocation”, IEEE Infocom 2000
1. Introduction
Congestion control has always been a topic of interest among network designers and engineers. This paper proposes a simple and elegant method of implementing congestion control in internet routers which incorporates both fairness and simplicity. The main motivation behind this work is the need for a simple stateless algorithm that can achieve flow isolation and/or approximate fair bandwidth allocation for internet routers.
The authors start off by presenting the difference between responsive and unresponsive flows and different models for congestion control. During the time of congestion in a router, a responsive flow (TCP based) adjusts its rate automatically where an unresponsive flow (UDP or a bad TCP implementation), will be impassive to the conditions in the router and aggressively use up more bandwidth than responsive flows. This shows the need for fairness while choosing a packet to keep/drop during the time of congestion.
The models for congestion control fall broadly in to two categories. 1. Scheduling algorithms and 2. Queue management algorithms. The scheduling algorithms drop packets depending on the state information of each flow stored locally and therefore results in a fairer bandwidth allocation. But they are expensive to implement in terms of computational complexity and storage required and naturally doesn’t scale well. Various implementations are Fair Queue (FQ), Core Stateless Fair Queuing (CSFQ), and Stochastic Fair Queuing (SFQ). The queue management algorithms are stateless and are simple to implement at the expense of fairness. The main algorithm in this category is Random Early Detection (RED) [2]. Even if RED solves some of the issues with drop tail mechanism, it doesn’t provide fairness among responsive and unresponsive flows. Other variations are RED with penalty box, Flow RED (FRED) etc which requires partial state information and Stabilized RED (SRED) which identified misbehaving flows but doesn’t provide a mechanism to penalize them.
CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for unresponsive flows) proposed here incorporates fairness similar to that of scheduling algorithms while keeping the simplicity of a queue management algorithms. When a packet arrives at a congested router, CHOKe draws a packet at random from the queue and compares it with the arriving packet. If they both belong to the same flow, both are dropped, else the randomly chosen packet is left intact and the arriving packet is admitted in to buffer with a probability of p (calculated in the same way as in RED). 2 main ideas drive the usage of this technique. 1. The likelihood of the randomly chosen packet belonging to a misbehaving flow is high. 2. A packet belonging to a misbehaving flow is more likely to trigger a comparison since they arrive more frequently.
2. CHOKe Algorithm
CHOke marks two thresholds in the FIFO buffer, minth and maxth. The algorithm is self-explanatory from figure 1.
Figure 1: The CHOKe algorithmThe implementation details are also discussed and showed verbally that only a small overhead is associated in implementing CHOKe as compared to RED.
3. Simulation Results
A standard network configuration is used to test the performance of CHOKe and compare it with RED and Drop Tail mechanisms as their complexities are close to that of CHOKE. The simulation results are presented in 3 parts: single congested link, multiple congested links and multiple congested flows.
As expected, CHOKe outperforms RED and Drop Tail in UDP throughput comparison where the latter 2 doesn’t discriminates against unresponsive flows. The throughput per flow of CHOKe is also shown where the TCP throughput reaches near the ideal fairness values. Other simulation results presented include performance under different traffic loads and queue distribution under different loadings. Similar simulation results are presented for other 2 parts.
4. Analytical Models
In this section, the authors analyze 3 different versions of CHOKe. 1. Original CHOKe, 2. Front CHOKe (drop candidate is always the packet at the head of the queue) and 3. Back CHOKe (drop candidate is always the packet at the tail of the queue). The second and third variations are used because of the difficulty of analysis of the original model.
Both the models assume independent Poisson arrivals and independent exponential service times with a FIFO queuing discipline. The models depend on the PASTA property to arrive at the results. In the case of front CHOKe, the throughput with 1, 2 and 3 flows are calculated from the analytical models and are presented along with the simulation results which are almost identical. In the case of back CHOKe, they use Markov chains to find the stationary distribution, πi. The throughput for various flows calculated from the mathematical model is presented.
5. Conclusion
The paper proposes a packet dropping scheme which is simple to implement and also maintains fair queuing among responsive and unresponsive flows. Simulation and analytical models and results are also presented to support the claims.
6. Reference
[1] R. Pan, B. Prabhakar and K. Psounis, “CHOKe: A stateless active queue management scheme for approximating fair bandwidth allocation”, IEEE Infocom 2000
3 comments:
We recently implemented a variant of RED but more related to wireless. Maybe CHOKe made sense 10 years back, but bad TCP stacks are more or less extinct, i.e. after linux. But UDP, yes, they can kill systems.
great to know that Ajay. Infact, I was wondering whether anyone really implemented CHOKe. cos there are lot of academic work related to CHOKe, even now, but couldnt place my hands on any implementation of CHOKe. Infact, we are thinking about trying it on a real router platform. :)
Really good post!
Post a Comment