CHOKe - A stateless active queue management scheme for approximating fair bandwidth allocation

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

Airline Maintenance

Here is a nice old joke I dug up from my funny mail forwards collection. I was searching for some old mails and saw this. Couldn’t stop laughing.

Qantas is an airline company based in Australia. After every flight, Qantas pilots fill out a form called a gripe sheet, which conveys to the mechanics problems encountered with the aircraft during the flight that need repair or correction. The engineers read and correct the problem, and then respond in writing on the lower half of the form what remedial action was taken, and the pilot reviews the gripe sheets before the next flight. Never let it be said that ground crews and engineers lack a sense of humor. Here are some actual logged maintenance complaints and problems as submitted by Qantas pilots and the solution recorded by maintenance engineers. By the way, Qantas is the only major airline that has never had an accident.

(P = the problem logged by the pilot)
(S = the solution and action taken by the engineers)

P: Left inside main tire almost needs replacement.
S: Almost replaced left inside main tire.

P: Test flight OK, except auto-land very rough.
S: Auto-land not installed on this aircraft.

P: Something loose in cockpit.
S: Something tightened in cockpit

P: Autopilot in altitude-hold mode produces a 200 feet per minute descent.
S: Cannot reproduce problem on ground.

P: Evidence of leak on right main landing gear.
S: Evidence removed.

P: DME volume unbelievably loud.
S: DME volume set to more believable level.

P: Friction locks cause throttle levers to stick.
S: That's what they're there for.

P: IFF inoperative.
S: IFF always inoperative in OFF mode.

P: Suspected crack in windshield.
S: Suspect you're right.

P: Number 3 engine missing.
S: Engine found on right wing after brief search.

P: Aircraft handles funny.
S: Aircraft warned to straighten up, fly right, and be serious.

P: Target radar hums.
S: Reprogrammed target radar with lyrics.

P: Mouse in cockpit.
S: Cat installed.

P: Noise coming from under instrument panel. Sounds like a midget pounding on something with a hammer.
S: Took hammer away from midget.