Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 RED Algorithm The algorithm works by dropping packets from the queue.The probability of a packet drop increases when the queue gets larger. compute average queue length as weighted average of queue lengths (EWMA)each time a packet arrives Algorithm parameters Let Or be the average queue length. -LetTH be the minimum threshold -LetTHm be the maximum threshold Let P be the drop probability 2616009:Network Traffic Engineering 5:Buffer Management Page.16
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 5: Buffer Management Page.16 RED Algorithm • The algorithm works by dropping packets from the queue. The probability of a packet drop increases when the queue gets larger. • compute average queue length as weighted average of queue lengths (EWMA) each time a packet arrives • Algorithm parameters - Let be the average queue length. - Let be the minimum threshold - Let be the maximum threshold - Let be the drop probability Qavg TH min TH max Pa
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 Why average queue length? Example:RED Router with Two TCP Sessions 1000 Flow 1 Queue Size 900 Flow 2+ Avg.Queue Size 25 800 700 20 600 uanbas 500 15 400 10 300 200 5 100 0 0 234567 8 9 10 012.345678910 Time (sec) Time (sec) 2616009:Network Traffic Engineering 5:Buffer Management Page.17
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 5: Buffer Management Page.17 Why average queue length? Example: RED Router with Two TCP Sessions
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 RED Algorithm(cont'd) TH min TH max Discard Discard with increasing Do not discard Probability Pa For each packet which arrives to router Calculate Qavg IF Qavg THmin queue packet ELSE IF THmin <Qavg THmax calculate probability Pa WITH PROBAILITY Pa discard packet ELSE WITH PROBABILITY(1-Pa)queue packet ELSE IF Qavg >THmax discard packet 2616009:Network Traffic Engineering 5:Buffer Management Page.18
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 5: Buffer Management Page.18 RED Algorithm(cont’d) TH min TH max 0 Discard Discard with increasing Do not discard Probability Pa For each packet which arrives to router Calculate Qavg IF Qavg < THmin queue packet ELSE IF THmin <= Qavg < THmax calculate probability Pa WITH PROBAILITY Pa discard packet ELSE WITH PROBABILITY (1 - Pa ) queue packet ELSE IF Qavg >= THmax discard packet
Feng Gang National Laboratory of Communication,UESTC Aug 2017 Ver 1.4 RED Algorithm(cont'd) Discard Probability Pmax Pa 0 THmin THmax Q length Average Queue Length Qavg 2616009:Network Traffic Engineering 5:Buffer Management Page.19
2616009: Network Traffic Engineering Feng Gang National Laboratory of Communication, UESTC Aug 2017 Ver 1.4 5: Buffer Management Page.19 RED Algorithm(cont’d) Discard Probability Average Queue Length 0 1 THmin THmax Q_length Qavg Pa Pmax