Summary
This paper describes a method for controlling congestion in a network. The technique is used on inner nodes or gateways and is designed to be easy to implement, require no per-connection state, and to be somewhat fair in that it drops packets in a manner that is roughly proportional to a connections share of the total bandwidth at the gateway.
The basic technique is to maintain the average length of the queue using a sliding window and to operate in one of three modes based on two thresholds. If the queue length is below a min threshold then all packets are forwarded. If the queue length is above a max threshold all packets are marked for congestion and/or dropped. In between the two thresholds the router randomly drops packets with a probability proportional to the queue size.
This works because the queue will be aggressively kept below the max, but since there is a sliding window for the length computation the gateway can handle short bursts of traffic. In addition, connections sending lots of packets will be more likely to have their packets marked/dropped, so the gateway is in some sense 'fair'.
The paper presents a number of simulations showing that RED does indeed control queue size, and that usage of the network is still quite high, even in the face of congestion. They discuss a number of parameters that can be set in the algorithm and their effects on the performance of the gateway. Some optimal values are suggested.
Discussion
I enjoyed this paper. The authors make a good case for the practicality of their approach (showing it's cheap to implement) and show that the algorithm works well. I think the number of parameters, and the sensitivity of the model to those parameters could be a barrier to adoption. Admins might be worried that if they tweak something a little wrong performance could become very poor.
The approach also doesn't explicitly deal with badly misbehaving clients. While those clients will be more likely to have their packets dropped, they don't get punished any extra for misbehaving.
Still, the elegance and simplicity of the approach make it quite appealing and I found this a worthwhile paper.
Subscribe to:
Post Comments (Atom)
Regarding the badly behaving clients, they do mention that other mechanisms for fairness can be integrated into RED. I think it would be interesting to see the results of integrating such a mechanism. I wonder if the approach would still remain simple, elegant and high-performing.
ReplyDelete