Random Early Dectection is the result of many years of research by the Internet Research Task Force into how to implement the generation of negative feedback aimed at controlling the average occupancy of router queues shared by many diverse flows. The group concluded that the best solution (taking current implementations in to account) involves statistical, randomly distributed feedback signals whose probability of occurrence was an increasing function of average queue occupancy (as covered in RFC2309. This RFC covers the random early detection (RED) (NOTE: It is not called Random Early Discard as many believe!) method specifically.
RED defines a series of rules for dropping packets based upon the average occupancy rate of packets within the router's queue. The average occupancy is measured each time a packet is received by this simple moving average-based formula:
Qavg = (1 - Wq) X Qavg + Qinst X Wq
Qavg is the average occupancy, Qinst is the instantaneous occupancy, and Wq is the weight for the moving average function. Wq is tunable: higher values are more aggressive, and lower values are more conservative. The goal is to dynamically tune Wq such that TCP's own congestion avoidance algorithm is not felt.
By now you may have been lead to ask:
But how does the value of Qavg affect this method directly?
Thesholds are set, and the value of Qavg is maintained and consulted. For packets less than the minimum threshold (minth), packets are left untouched. For packets about minth the probability of packet drop rises linearly toward a probability of maxp until the maximum average occupancy is reached at the maximum threshold maxth; afterwhich, packets are guaranteed to be dropped.
A router may support different values for minth, maxth, and maxp for different queues-- thereby effectively conserving resources and offering different levels of service. In addition, the value of Wq may also be different for each queue on the same principal.
Beginning random drops early (before the available queue space is exhausted) increases the likelihook of smoothing out the transient congestion before queue occupancy gets to be too high. This is based on the following: