17 May, 2012

1 commit

  • codel_should_drop() logic allows a packet being not dropped if queue
    size is under max packet size.

    In fq_codel, we have two possible backlogs : The qdisc global one, and
    the flow local one.

    The meaningful one for codel_should_drop() should be the global backlog,
    not the per flow one, so that thin flows can have a non zero drop/mark
    probability.

    Signed-off-by: Eric Dumazet
    Cc: Dave Taht
    Cc: Kathleen Nichols
    Cc: Van Jacobson
    Signed-off-by: David S. Miller

    Eric Dumazet
     

15 May, 2012

1 commit

  • David pointed out gcc might generate poor code with 31bit fields.

    Using u16 is more than enough and permits a better code output.

    Also make the code intent more readable using constants, fixed point arithmetic
    not being trivial for everybody.

    Suggested-by: David Miller
    Signed-off-by: Eric Dumazet
    Signed-off-by: David S. Miller

    Eric Dumazet
     

13 May, 2012

1 commit

  • As Van pointed out, interval/sqrt(count) can be implemented using
    multiplies only.

    http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots

    This patch implements the Newton method and reciprocal divide.

    Total cost is 15 cycles instead of 120 on my Corei5 machine (64bit
    kernel).

    There is a small 'error' for count values < 5, but we don't really care.

    I reuse a hole in struct codel_vars :
    - pack the dropping boolean into one bit
    - use 31bit to store the reciprocal value of sqrt(count).

    Suggested-by: Van Jacobson
    Signed-off-by: Eric Dumazet
    Cc: Dave Taht
    Cc: Kathleen Nichols
    Cc: Tom Herbert
    Cc: Matt Mathis
    Cc: Yuchung Cheng
    Cc: Nandita Dukkipati
    Cc: Stephen Hemminger
    Signed-off-by: David S. Miller

    Eric Dumazet
     

11 May, 2012

1 commit

  • An implementation of CoDel AQM, from Kathleen Nichols and Van Jacobson.

    http://queue.acm.org/detail.cfm?id=2209336

    This AQM main input is no longer queue size in bytes or packets, but the
    delay packets stay in (FIFO) queue.

    As we don't have infinite memory, we still can drop packets in enqueue()
    in case of massive load, but mean of CoDel is to drop packets in
    dequeue(), using a control law based on two simple parameters :

    target : target sojourn time (default 5ms)
    interval : width of moving time window (default 100ms)

    Based on initial work from Dave Taht.

    Refactored to help future codel inclusion as a plugin for other linux
    qdisc (FQ_CODEL, ...), like RED.

    include/net/codel.h contains codel algorithm as close as possible than
    Kathleen reference.

    net/sched/sch_codel.c contains the linux qdisc specific glue.

    Separate structures permit a memory efficient implementation of fq_codel
    (to be sent as a separate work) : Each flow has its own struct
    codel_vars.

    timestamps are taken at enqueue() time with 1024 ns precision, allowing
    a range of 2199 seconds in queue, and 100Gb links support. iproute2 uses
    usec as base unit.

    Selected packets are dropped, unless ECN is enabled and packets can get
    ECN mark instead.

    Tested from 2Mb to 10Gb speeds with no particular problems, on ixgbe and
    tg3 drivers (BQL enabled).

    Usage: tc qdisc ... codel [ limit PACKETS ] [ target TIME ]
    [ interval TIME ] [ ecn ]

    qdisc codel 10: parent 1:1 limit 2000p target 3.0ms interval 60.0ms ecn
    Sent 13347099587 bytes 8815805 pkt (dropped 0, overlimits 0 requeues 0)
    rate 202365Kbit 16708pps backlog 113550b 75p requeues 0
    count 116 lastcount 98 ldelay 4.3ms dropping drop_next 816us
    maxpacket 1514 ecn_mark 84399 drop_overlimit 0

    CoDel must be seen as a base module, and should be used keeping in mind
    there is still a FIFO queue. So a typical setup will probably need a
    hierarchy of several qdiscs and packet classifiers to be able to meet
    whatever constraints a user might have.

    One possible example would be to use fq_codel, which combines Fair
    Queueing and CoDel, in replacement of sfq / sfq_red.

    Signed-off-by: Eric Dumazet
    Signed-off-by: Dave Taht
    Cc: Kathleen Nichols
    Cc: Van Jacobson
    Cc: Tom Herbert
    Cc: Matt Mathis
    Cc: Yuchung Cheng
    Cc: Stephen Hemminger
    Signed-off-by: David S. Miller

    Eric Dumazet