Summary: Controlling High-Bandwidth Flows at the Congested Router

This paper describes an extension to RED called RED-PD. Traditional
RED does not distinguish flows from each other. It assumes that high
bandwidth flows will be affected more often than low bandwidth flows
simply because high bandwidth flows tend to have more packets. However,
since no per-flow decisions are made, RED does not provide any strong
guarantees as to how bandwidth will be allocated to each flow when the
router is overloaded. This is especially a problem when the flows are
not using end-to-end congestion control (ie. they don't backoff when
the router drops the occasional packet).

In contrast, RED-PD does distinguish flows. It ensures that all flows
will not consume more than a set "target bandwidth" while the router is
in overload (ie. when it is dropping packets). Should a flow consume
more than the target, the drop rate for that flow only is increased
until it no longer exceeds the target. Since the drop rate for
offending flows can be adjusted independently, the overall RED drop
rate (the "ambient drop rate") does not need to be pushed as high as
using RED. The bandwidth recovered from the offending flows can
therefore be diverted to the flows which are not exceeding the target.
Finally, RED-PD will continue to increase the drop rate for an
offending flow until it either backs itself off enough to fall below
the target (ie. TCP congestion control), or until the drop rate goes so
high as to directly control the bandwidth consumed by the flow. RED-PD
can therefore control both behaving and misbehaving flows.

The authors observe that an efficient way to keep track of the
bandwidth used by each flow is simply to examine how often RED selects
a packet from the flow for drop/ECN. The exact relationship between
the bandwidth used by a flow and the number of packets dropped by RED
over a given time is provided. The advantage to this measuring scheme
is that per-flow state does not need to be stored. Instead, the router
simply needs to keep track of the flows that owned packets selected by
RED for the last few seconds. Furthermore, no explicit measurement of
each flow's bandwidth needs to be done, as RED-PD uses work that needed
to be done anyway (as part of RED) to measure bandwidths.

The results look very good. Figure 10 shows that RED-PD gives each
flow nearly the same bandwidth that they would have received with a
fair-share algorithm. The paper also presents a "worst case" memory
consumption analysis: even if the incoming link was 1Gbps and RED was
dropping at 1%, the total extra memory needed by RED-PD would be only
200KB. This seems like a good way to get the benefits of per-flow
control without paying a full memory cost. I also found Figures 3 and
4 particularly interesting. These show just how skewed flow are in
their demand for resources.
Received on Sat Sep 30 2006 - 17:28:01 EDT