• Eric Dumazet's avatar
    sch_red: Adaptative RED AQM · 8af2a218
    Eric Dumazet authored
    Adaptative RED AQM for linux, based on paper from Sally FLoyd,
    Ramakrishna Gummadi, and Scott Shenker, August 2001 :
    
    http://icir.org/floyd/papers/adaptiveRed.pdf
    
    Goal of Adaptative RED is to make max_p a dynamic value between 1% and
    50% to reach the target average queue : (max_th - min_th) / 2
    
    Every 500 ms:
     if (avg > target and max_p <= 0.5)
      increase max_p : max_p += alpha;
     else if (avg < target and max_p >= 0.01)
      decrease max_p : max_p *= beta;
    
    target :[min_th + 0.4*(min_th - max_th),
              min_th + 0.6*(min_th - max_th)].
    alpha : min(0.01, max_p / 4)
    beta : 0.9
    max_P is a Q0.32 fixed point number (unsigned, with 32 bits mantissa)
    
    Changes against our RED implementation are :
    
    max_p is no longer a negative power of two (1/(2^Plog)), but a Q0.32
    fixed point number, to allow full range described in Adatative paper.
    
    To deliver a random number, we now use a reciprocal divide (thats really
    a multiply), but this operation is done once per marked/droped packet
    when in RED_BETWEEN_TRESH window, so added cost (compared to previous
    AND operation) is near zero.
    
    dump operation gives current max_p value in a new TCA_RED_MAX_P
    attribute.
    
    Example on a 10Mbit link :
    
    tc qdisc add dev $DEV parent 1:1 handle 10: est 1sec 8sec red \
       limit 400000 min 30000 max 90000 avpkt 1000 \
       burst 55 ecn adaptative bandwidth 10Mbit
    
    # tc -s -d qdisc show dev eth3
    ...
    qdisc red 10: parent 1:1 limit 400000b min 30000b max 90000b ecn
    adaptative ewma 5 max_p=0.113335 Scell_log 15
     Sent 50414282 bytes 34504 pkt (dropped 35, overlimits 1392 requeues 0)
     rate 9749Kbit 831pps backlog 72056b 16p requeues 0
      marked 1357 early 35 pdrop 0 other 0
    Signed-off-by: 's avatarEric Dumazet <eric.dumazet@gmail.com>
    Signed-off-by: 's avatarDavid S. Miller <davem@davemloft.net>
    8af2a218
reciprocal_div.c 218 Bytes