man/man8/tc-sfb.8

   1 .TH SFB 8 "August 2011" "iproute2" "Linux"
   2 .SH NAME
   3 sfb \- Stochastic Fair Blue
   4 .SH SYNOPSIS
   5 .B tc qdisc ... blue
   6 .B rehash
   7 milliseconds
   8 .B db
   9 milliseconds
  10 .B limit
  11 packets
  12 .B max
  13 packets
  14 .B target
  15 packets
  16 .B increment
  17 float
  18 .B decrement
  19 float
  20 .B penalty_rate
  21 packets per second
  22 .B penalty_burst
  23 packets
  24
  25 .SH DESCRIPTION
  26 Stochastic Fair Blue is a classless qdisc to manage congestion based on
  27 packet loss and link utilization history while trying to prevent
  28 non-responsive flows (i.e. flows that do not react to congestion marking
  29 or dropped packets) from impacting performance of responsive flows.
  30 Unlike RED, where the marking probability has to be configured, BLUE
  31 tries to determine the ideal marking probability automatically.
  32
  33 .SH ALGORITHM
  34
  35 The
  36 .B BLUE
  37 algorithm maintains a probability which is used to mark or drop packets
  38 that are to be queued.  If the queue overflows, the mark/drop probability
  39 is increased. If the queue becomes empty, the probability is decreased. The
  40 .B Stochastic Fair Blue
  41 (SFB) algorithm is designed to protect TCP flows against non-responsive flows.
  42
  43 This SFB implementation maintains 8 levels of 16 bins each for accounting.
  44 Each flow is mapped into a bin of each level using a per-level hash value.
  45
  46 Every bin maintains a marking probability, which gets increased or decreased
  47 based on bin occupancy.  If the number of packets exceeds the size of that
  48 bin, the marking probability is increased.  If the number drops to zero, it
  49 is decreased.
  50
  51 The marking probability is based on the minimum value of all bins a flow is
  52 mapped into, thus, when a flow does not respond to marking or gradual packet
  53 drops, the marking probability quickly reaches one.
  54
  55 In this case, the flow is rate-limited to
  56 .B penalty_rate
  57 packets per second.
  58
  59 .SH LIMITATIONS
  60
  61 Due to SFBs nature, it is possible for responsive flows to share all of its bins
  62 with a non-responsive flow, causing the responsive flow to be misidentified as
  63 being non-responsive.
  64
  65 The probability of a responsive flow to be misidentified is dependent on
  66 the number of non-responsive flows, M.  It is (1 - (1 - (1 / 16.0)) ** M) **8,
  67 so for example with 10 non-responsive flows approximately 0.2% of responsive flows
  68 will be misidentified.
  69
  70 To mitigate this, SFB performs performs periodic re-hashing to avoid
  71 misclassification for prolonged periods of time.
  72
  73 The default hashing method will use source and destination ip addresses and port numbers
  74 if possible, and also supports tunneling protocols.
  75 Alternatively, an external classifier can be configured, too.
  76
  77 .SH PARAMETERS
  78 .TP
  79 rehash
  80 Time interval in milliseconds when queue perturbation occurs to avoid erroneously
  81 detecting unrelated, responsive flows as being part of a non-responsive flow for
  82 prolonged periods of time.
  83 Defaults to 10 minutes.
  84 .TP
  85 db
  86 Double buffering warmup wait time, in milliseconds.
  87 To avoid destroying the probability history when rehashing is performed, this
  88 implementation maintains a second set of levels/bins as described in section
  89 4.4 of the SFB reference.
  90 While one set is used to manage the queue, a second set is warmed up:
  91 Whenever a flow is then determined to be non-responsive, the marking
  92 probabilities in the second set are updated.  When the rehashing
  93 happens, these bins will be used to manage the queue and all non-responsive
  94 flows can be rate-limited immediately.
  95 This value determines how much time has to pass before the 2nd set
  96 will start to be warmed up.
  97 Defaults to one minute, should be lower than
  98 .B
  99 rehash.
 100 .TP
 101 limit
 102 Hard limit on the real (not average) total queue size in packets.
 103 Further packets are dropped.  Defaults to the transmit queue length of the
 104 device the qdisc is attached to.
 105 .TP
 106 max
 107 Maximum length of a buckets queue, in packets, before packets start being
 108 dropped.  Should be sightly larger than
 109 .B target
 110 , but should not be set to values exceeding 1.5 times that of
 111 .B target .
 112 Defaults to 25.
 113 .TP
 114 target
 115 The desired average bin length.  If the bin queue length reaches this value,
 116 the marking probability is increased by
 117 .B increment.
 118 The default value depends on the
 119 .B max
 120 setting, with max set to 25
 121 .B target
 122 will default to 20.
 123 .TP
 124 increment
 125 A value used to increase the marking probability when the queue appears
 126 to be over-used.  Must be between 0 and 1.0.  Defaults to 0.00050.
 127 .TP
 128 decrement
 129 Value used to decrease the marking probability when the queue is found
 130 to be empty.  Must be between 0 and 1.0.
 131 Defaults to 0.00005.
 132 .TP
 133 penalty_rate
 134 The maximum number of packets belonging to flows identified as being
 135 non-responsive that can be enqueued per second. Once this number has been
 136 reached, further packets of such non-responsive flows are dropped.
 137 Set this to a reasonable fraction of your uplink throughput; the
 138 default value of 10 packets is probably too small.
 139 .TP
 140 penalty_burst
 141 The number of packets a flow is permitted to exceed the penalty rate before packets
 142 start being dropped.
 143 Defaults to 20 packets.
 144
 145 .SH STATISTICS
 146
 147 This qdisc exposes additional statistics via 'tc -s qdisc' output.
 148 These are:
 149 .TP
 150 earlydrop
 151 The number of packets dropped before a per-flow queue was full.
 152 .TP
 153 ratedrop
 154 The number of packets dropped because of rate-limiting.
 155 If this value is high, there are many non-reactive flows being
 156 sent through sfb.  In such cases, it might be better to
 157 embed sfb within a classful qdisc to better control such
 158 flows using a different, shaping qdisc.
 159 .TP
 160 bucketdrop
 161 The number of packets dropped because a per-flow queue was full.
 162 High bucketdrop may point to a high number of aggressive, short-lived
 163 flows.
 164 .TP
 165 queuedrop
 166 The number of packets dropped due to reaching limit.  This should normally be 0.
 167 .TP
 168 marked
 169 The number of packets marked with ECN.
 170 .TP
 171 maxqlen
 172 The length of the current longest per-flow (virtual) queue.
 173 .TP
 174 maxprob
 175 The maximum per-flow drop probability.  1 means that some
 176 flows have been detected as non-reactive.
 177
 178 .SH NOTES
 179
 180 SFB automatically enables use of Explicit Congestion Notification (ECN).
 181 Also, this SFB implementation does not queue packets itself.
 182 Rather, packets are enqueued to the inner qdisc (defaults to pfifo).
 183 Because sfb maintains virtual queue states, the inner qdisc must not
 184 drop a packet previously queued.
 185 Furthermore, if a buckets queue has a very high marking rate,
 186 this implementation will start dropping packets instead of
 187 marking them, as such a situation points to either bad congestion, or an
 188 unresponsive flow.
 189
 190 .SH EXAMPLE & USAGE
 191
 192 To attach to interface $DEV, using default options:
 193 .P
 194 # tc qdisc add dev $DEV handle 1: root sfb
 195
 196 Only use destination ip addresses for assigning packets to bins, perturbing
 197 hash results every 10 minutes:
 198 .P
 199 # tc filter add dev $DEV parent 1: handle 1 flow hash keys dst perturb 600
 200
 201 .SH SEE ALSO
 202 .BR tc (8),
 203 .BR tc-red (8),
 204 .BR tc-sfq (8)
 205 .SH SOURCES
 206 .TP
 207 o
 208 W. Feng, D. Kandlur, D. Saha, K. Shin, BLUE: A New Class of Active Queue Management Algorithms,
 209 U. Michigan CSE-TR-387-99, April 1999.
 210
 211 .SH AUTHORS
 212
 213 This SFB implementation was contributed by Juliusz Chroboczek and Eric Dumazet.