Nalanda

Citation: Floyd, S. and Jacobson, V. 1993. Random early detection gateways for congestion avoidance. IEEE/ACM Trans. Netw. 1, 4 (Aug. 1993), 397-413. DOI= http://dx.doi.org/10.1109/90.251892

Floyd and Jacobson’s work on RED gateways is motivated by the observation that TCP is designed to detect congestion only after a packet is dropped at a gateway, which would typically result in large, mostly full, queues at gateways, contributing to increased average delay in the network. While RED’s congestion notification mechanisms (which are referred to as “marking”) are similar to those available in TCP (drop a packet) and explicit notification as proposed by Chiu and Jain (1989), RED detects congestion differently. Instead of reporting congestion when it occurs (i.e., queues approaching full), RED computes average queue size, and probabilistically “marks” packets when the the average queue size exceeds a a certain threshold value.

This approach should allow a RED gateway to maintain smaller queues on average, while also responding well to bursty connections, especially TCP’s Slow Start phase. Additionally, the probabilistic marking of packets ensures avoidance of global synchronization, where multiple TCP connections respond to congestion notification by concurrently reverting to Slow Start.

Two distinct algorithms are used to satisfy RED’s design goals, one for congestion detection, and another for deciding which connections to notify when congestion is detected. These function differently across three different ranges of operation, depending on the average queue size, computed as an exponential weighted moving average, with a low-pass filter. When average queue size is under a minimum threshold, all packets are passed through. When it is over a maximum threshold, all packets are marked. In between these two thresholds, packets are marked with a probability proportional to the share of bandwidth that a connection is consuming. I found the discussion of approaches to randomization in order to avoid clustering of marked packets (and hence global synchronization problems) particularly interesting.

RED makes two major assumptions: that FIFO scheduling will continue to be useful and prevalent, and that the host transport protocols are responsive to congestion notifications. From discussions in class, it would seem that the former assumption is no longer an issue with the current generation of routers. The latter assumption, that of cooperative transport protocols, is explicitly stated in the paper initially, but also refuted later, when the authors state that one of their design goals is to maintain proper function even in the presence of uncooperative transport protocols. In my reading, it seems to me an open question as to how well RED would function in the presence of uncooperative transport protocols.

An interesting characteristic of RED that I would have liked to see more discussion of is the fact that it does not attempt to be fair. Rather, it allows connections to take more than their fair share of bandwidth for brief periods, as long as average queue sizes are under the maximum threshold. While this is dependent on tuning the thresholds and weight, it seems a sensible approach - get as much through as possible - which is, after all, the function of the network.