Side_1_360

sources to slow down. RED is mainly useful

when the bulk of the traffic is TCP traffic. A

potential consequence of RED is that UDP

sources, or some misbehaved greedy sources

can obtain an unfair advantage when TCP con-

nections slow down their rate.

The RED algorithm works as follows (ref. Fig-

ure 5): When a packet arrives, the algorithm cal-

culates the average queue size, for instance using

a low-pass filter with an exponential weighted

moving average:

• If the average queue size is lower than a mini-
  mum threshold (minth), the packet is queued.


• If the average queue size is greater than a
  maximum threshold (maxth), the packet is dis-
  carded.


• If the average queue size is greater than the
  minimum threshold, and lower than the maxi-
  mum one, the packet is discarded with a prob-
  ability p, which is a function of the average
  queue size.

Weighted RED (WRED) is a RED-derived

mechanism that assigns to each class a different

RED algorithm. Then it is possible to differenti-

ate between the different classes. Basically

WRED provides RED with separate thresholds

and weights for different classes. For example,

standard traffic may be dropped more frequently

than premium traffic during periods of conges-

tion.

As an example classes like green, yellow and red

may be used (as for the policing algorithm). This

is illustrated in Figure 6. Another example is to

use different dropping probabilities for TCP and

for UDP traffic flows.

RED and WRED commonly use the average

queue sizes, not considering the link utilisation,

which again could lead to oscillations for the

queueing level under congestion. To address this

a Shock-absorber RED (SRED) has been derived,

see Figure 7. Then the instantaneous dropping

probability depends not only on the queue size

but also on the offered load. This is to reduce the

variations for the queue filling. SRED may also

be extended to allow for several traffic classes.

RED with In/Out bit (RIO) is a RED-derived

mechanism that assigns two different priorities.

But instead of using the same average queue size

for both priorities (like WRED does for all the

classes), it uses the average queue size for OUT

(out of profile) packets, and the average queue

size without taking into account the queued

OUT packets for IN (in profile) packets, see

Figure 8.

Figure 5 RED algorithm

Figure 6 WRED with three classes (red, yellow, green)

Discarding Probability,

p

p = 1

pmax

minth maxth

Average

QueueLevel

Discarding Probability

1

Qmin1

0

Qmax1 Qmin2 Qmax2 Qmin3 Qmax3

R Y G

DP1, DP2

DP3

Average

Queue Level

Discarding Probability

1

Qmin

0

Qmax

Average

Queue Level

DP

SRED (*)

RED

Figure 7 Illustration of Shock-absorber RED compared to basic RED