RED-PD Review

This paper presents the RED-PD algorithm, the Random Early Discard algorithm
improved with Preferential Dropping. RED-PD is a departure from other
approaches because it maintains state for just the high-bandwidth flows.
This makes sense because most Internet flows are short HTTP flows. The
router keeps a list of high bandwidth flows (above a target bandwidth) based
on RED packet drops and assigns a higher dropping probability to subsequent
packets from those flows. The actual dropping probability is a function of
the current throughput into the output queue and the excess sending rate of
the flow. Preferential dropping is suspended when total throughput is less
than a specific threshold. The changes in preferential dropping probability
are bounded to prevent oscillation,

In order for RED-PD to identify the high throughput flows and have an
advantage over previous approaches, it is necessary that a small fraction of
the flows be responsible for most of the bytes sent (over small and long
intervals) and that the high bandwidth flows in a given interval be a good
predictor of the high bandwidth flows in the next interval. Because the
RED-PD approach preferentially drops packets from a small number of
high-bandwidth flows, it provides for a lower ambient drop rate. RED-PD
maintains a history of high-bandwidth flows in M lists and when an incoming
packet corresponds to a flow that occurs in at least K of these lists, its
flow is monitored.

The authors state that RED-PD "explicitly leverages the skewed bandwidth
distribution" to "improve the performance of low-bandwidth flows using a
small amount of state" and that it has "a predictable effect on the traffic
going through the router". This is supported by the performance figures
which show that RED-PD is likely to identify misbehaving flows and have few
false positives, that it can handle constant bit rate flows, and that it can
quickly adapt dropping probability in response to changing sending rates.
Furthermore, it provides fairness among monitored flows, it does not starve
monitored flows and it does not guarantee a fixed amount of bandwidth for
the monitored flows without regard for the level of unmonitored traffic. It
should be noted that RED-PD does not punish persistently misbehaving flows
by assigning them a higher drop rate than if they had not been identified as
persistently misbehaving. Overall, the paper is well presented and easy to
read, and the performance section examines many likely network scenarios.
Received on Mon Oct 02 2006 - 19:26:58 EDT