tc-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 congestion 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 automatically.
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 probability 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 packets 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 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
probabilities 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 sightly larger than target , but
should not be set to values exceeding 1.5 times that of target .
Defaults to 25.
target 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 identified 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 throughput; 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 better 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.
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 Notification (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 previously 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. Michigan CSE-TR-387-99,
April 1999.
AUTHORS
This SFB implementation was contributed by Juliusz Chroboczek and Eric Dumazet.
Opportunity
Personal Opportunity - Free software gives you access to billions of dollars of software at no cost. Use this software for your business, personal use or to develop a profitable skill. Access to source code provides access to a level of capabilities/information that companies protect though copyrights. Open source is a core component of the Internet and it is available to you. Leverage the billions of dollars in resources and capabilities to build a career, establish a business or change the world. The potential is endless for those who understand the opportunity.
Business Opportunity - Goldman Sachs, IBM and countless large corporations are leveraging open source to reduce costs, develop products and increase their bottom lines. Learn what these companies know about open source and how open source can give you the advantage.
Free Software
Free Software provides computer programs and capabilities at no cost but more importantly, it provides the freedom to run, edit, contribute to, and share the software. The importance of free software is a matter of access, not price. Software at no cost is a benefit but ownership rights to the software and source code is far more significant.
Free Office Software - The Libre Office suite provides top desktop productivity tools for free. This includes, a word processor, spreadsheet, presentation engine, drawing and flowcharting, database and math applications. Libre Office is available for Linux or Windows.
Free Books
The Free Books Library is a collection of thousands of the most popular public domain books in an online readable format. The collection includes great classical literature and more recent works where the U.S. copyright has expired. These books are yours to read and use without restrictions.
Source Code - Want to change a program or know how it works? Open Source provides the source code for its programs so that anyone can use, modify or learn how to write those programs themselves. Visit the GNU source code repositories to download the source.
Education
Study at Harvard, Stanford or MIT - Open edX provides free online courses from Harvard, MIT, Columbia, UC Berkeley and other top Universities. Hundreds of courses for almost all major subjects and course levels. Open edx also offers some paid courses and selected certifications.
Linux Manual Pages - A man or manual page is a form of software documentation found on Linux/Unix operating systems. Topics covered include computer programs (including library and system calls), formal standards and conventions, and even abstract concepts.
