Doug Johnson
finson@whidbey.com
** Context
- Overbuffering to handle high speed/high volume transients causes
unacceptable latency.
- Enforcing short queues with drop tail is unfair to bursty traffic and
causes global synchronization.
** Summary of algorithm
- RED gateway algorithm monitors average queue length at the gateway using a
low pass filter to calculate the average. Starts notifying senders when avg
> threshold.min, notifies more as avg approaches threshold.max, and notifies
all when avg > threshold.max.
- Notification can be packet marking or dropping. Marking requires
cooperating hosts, dropping enforces queue length limits.
** Similar & related algorithms
DECbit - marks all packets during congestion. Depends on host calculating
congestion levels and acting on it. Unfair to bursty sources. Host
reaction to congestion is gradual so not too bad at causing synchronization.
Early Random Drop - better than Drop Tail at hitting "aggressive users" but
not good enough when using simple on / off drop control.
Feedback added to packet - Gateways add congestion info to the packet as it
goes by. F&J dismiss this as vulnerable to transient effects, but it seems
like using their average queue length instead of actual queue length and
similar changes might reduce that. It has the potential advantage that
information is collected on a flow basis, which I think is going to be more
important as many more different types of flows contend for resources.
** Implementation
- Calculates average queue length using low pass filter.
- If most packets of similar size, can use packet count, else fairer to use
byte count.
- Weighting factor in avg=avg+w(q-avg) is a function of desired burst
tolerance, th.min & th.max thresholds depend on delay * bandwidth product.
IE, tuning parameters depend heavily on traffic characterization.
- RED scales packet marking probability using average queue length and
packets since last mark. Discontinuous at th.max, which might lead to
gateway behavior that could be exploited by clients to force others to back
off, then put their traffic on the now uncongested link.
** Comments
- RED strategy better suited to mixed traffic than droptail - fairer to
bursty traffic and avoids synchronization.
- I believe that it still depends too much on information not identified to
a flow. Ultimately, congestion avoidance in a diverse, untrusting network
is going to depend on tying information about congestion to specific flows
and dealing with them directly. Also, the range of traffic types is getting
bigger, and one set of tuning parameters will not cover all the desirable
cases. Flow by flow data will be required for performance and security.
- F & J also comment that information found by the RED gateway could be
forwarded to "higher levels" in the protocol stack to deal with bad actors.
- Separation might be considered for control flow and data flow to reduce
effects like ack compression.
- Another twist might be for the gateways to explicitly use induced effects
in the hosts to control incoming traffic. For example, with specific flow
knowledge, a gateway might use deliberate ack pacing to throttle a babbling
host.