SFB(8)                    (August 2011)                    SFB(8)

     NAME
          sfb - Stochastic Fair Blue

     SYNOPSIS
          tc qdisc ... blue rehash milliseconds db milliseconds limit
          packets max packets target packets increment float decrement
          float penalty_rate packets per second penalty_burst packets

     DESCRIPTION
          Stochastic Fair Blue is a classless qdisc to manage conges-
          tion based on packet loss and link utilization history while
          trying to prevent non-responsive flows (i.e. flows that do
          not react to congestion marking or dropped packets) from
          impacting performance of responsive flows.  Unlike RED,
          where the marking probability has to be configured, BLUE
          tries to determine the ideal marking probability automati-
          cally.

     ALGORITHM
          The BLUE algorithm maintains a probability which is used to
          mark or drop packets that are to be queued. If the queue
          overflows, the mark/drop probability is increased. If the
          queue becomes empty, the probability is decreased. The
          Stochastic Fair Blue (SFB) algorithm is designed to protect
          TCP flows against non-responsive flows.

          This SFB implementation maintains 8 levels of 16 bins each
          for accounting.  Each flow is mapped into a bin of each
          level using a per-level hash value.

          Every bin maintains a marking probability, which gets
          increased or decreased based on bin occupancy. If the number
          of packets exceeds the size of that bin, the marking proba-
          bility is increased. If the number drops to zero, it is
          decreased.

          The marking probability is based on the minimum value of all
          bins a flow is mapped into, thus, when a flow does not
          respond to marking or gradual packet drops, the marking
          probability quickly reaches one.

          In this case, the flow is rate-limited to penalty_rate pack-
          ets per second.

     LIMITATIONS
          Due to SFBs nature, it is possible for responsive flows to
          share all of its bins with a non-responsive flow, causing

     Page 1                      iproute2            (printed 5/23/22)

     SFB(8)                    (August 2011)                    SFB(8)

          the responsive flow to be misidentified as being non-
          responsive.

          The probability of a responsive flow to be misidentified is
          dependent on the number of non-responsive flows, M. It is (1
          - (1 - (1 / 16.0)) ** M) **8, so for example with 10 non-
          responsive flows approximately 0.2% of responsive flows will
          be misidentified.

          To mitigate this, SFB performs performs periodic re-hashing
          to avoid misclassification for prolonged periods of time.

          The default hashing method will use source and destination
          ip addresses and port numbers if possible, and also supports
          tunneling protocols.  Alternatively, an external classifier
          can be configured, too.

     PARAMETERS
          rehash
               Time interval in milliseconds when queue perturbation
               occurs to avoid erroneously detecting unrelated,
               responsive flows as being part of a non-responsive flow
               for prolonged periods of time.  Defaults to 10 minutes.

          db   Double buffering warmup wait time, in milliseconds.  To
               avoid destroying the probability history when rehashing
               is performed, this implementation maintains a second
               set of levels/bins as described in section 4.4 of the
               SFB reference.  While one set is used to manage the
               queue, a second set is warmed up: Whenever a flow is
               then determined to be non-responsive, the marking prob-
               abilities in the second set are updated. When the
               rehashing happens, these bins will be used to manage
               the queue and all non-responsive flows can be rate-
               limited immediately.  This value determines how much
               time has to pass before the 2nd set will start to be
               warmed up.  Defaults to one minute, should be lower
               than rehash.

          limit
               Hard limit on the real (not average) total queue size
               in packets.  Further packets are dropped. Defaults to
               the transmit queue length of the device the qdisc is
               attached to.

          max  Maximum length of a buckets queue, in packets, before
               packets start being dropped. Should be slightly larger
               than target , but should not be set to values exceeding
               1.5 times that of target . Defaults to 25.

          target

     Page 2                      iproute2            (printed 5/23/22)

     SFB(8)                    (August 2011)                    SFB(8)

               The desired average bin length. If the bin queue length
               reaches this value, the marking probability is
               increased by increment. The default value depends on
               the max setting, with max set to 25 target will default
               to 20.

          increment
               A value used to increase the marking probability when
               the queue appears to be over-used. Must be between 0
               and 1.0. Defaults to 0.00050.

          decrement
               Value used to decrease the marking probability when the
               queue is found to be empty. Must be between 0 and 1.0.
               Defaults to 0.00005.

          penalty_rate
               The maximum number of packets belonging to flows iden-
               tified as being non-responsive that can be enqueued per
               second. Once this number has been reached, further
               packets of such non-responsive flows are dropped.  Set
               this to a reasonable fraction of your uplink through-
               put; the default value of 10 packets is probably too
               small.

          penalty_burst
               The number of packets a flow is permitted to exceed the
               penalty rate before packets start being dropped.
               Defaults to 20 packets.

     STATISTICS
          This qdisc exposes additional statistics via 'tc -s qdisc'
          output.  These are:

          earlydrop
               The number of packets dropped before a per-flow queue
               was full.

          ratedrop
               The number of packets dropped because of rate-limiting.
               If this value is high, there are many non-reactive
               flows being sent through sfb. In such cases, it might
               be better to embed sfb within a classful qdisc to bet-
               ter control such flows using a different, shaping
               qdisc.

          bucketdrop
               The number of packets dropped because a per-flow queue
               was full.  High bucketdrop may point to a high number
               of aggressive, short-lived flows.

     Page 3                      iproute2            (printed 5/23/22)

     SFB(8)                    (August 2011)                    SFB(8)

          queuedrop
               The number of packets dropped due to reaching limit.
               This should normally be 0.

          marked
               The number of packets marked with ECN.

          maxqlen
               The length of the current longest per-flow (virtual)
               queue.

          maxprob
               The maximum per-flow drop probability. 1 means that
               some flows have been detected as non-reactive.

     NOTES
          SFB automatically enables use of Explicit Congestion Notifi-
          cation (ECN).  Also, this SFB implementation does not queue
          packets itself.  Rather, packets are enqueued to the inner
          qdisc (defaults to pfifo).  Because sfb maintains virtual
          queue states, the inner qdisc must not drop a packet previ-
          ously queued.  Furthermore, if a buckets queue has a very
          high marking rate, this implementation will start dropping
          packets instead of marking them, as such a situation points
          to either bad congestion, or an unresponsive flow.

     EXAMPLE & USAGE
          To attach to interface $DEV, using default options:

          # tc qdisc add dev $DEV handle 1: root sfb

          Only use destination ip addresses for assigning packets to
          bins, perturbing hash results every 10 minutes:

          # tc filter add dev $DEV parent 1: handle 1 flow hash keys
          dst perturb 600

     SEE ALSO
          tc(8), tc-red(8), tc-sfq(8)

     SOURCES
          o    W. Feng, D. Kandlur, D. Saha, K. Shin, BLUE: A New
               Class of Active Queue Management Algorithms, U. Michi-
               gan CSE-TR-387-99, April 1999.

     AUTHORS
          This SFB implementation was contributed by Juliusz Chro-
          boczek and Eric Dumazet.

     Page 4                      iproute2            (printed 5/23/22)