A sysadmin's understanding of HFSC and IFB

A sysadmin's understanding of HFSC and IFB

[John A. Sullivan III]

Hello, all.  I've been trying to summarize my last week's worth of
research into HFSC and IFB.  Being neither a developer nor a
mathematician, I found most of the existing documentation daunting and
am truly grateful for the help I received on this list to understand the
technologies.

I do not currently have a blog to post this research and so was thinking
of posting it to this list so that it could be archived and searchable
for other poor sysadmin types like me to save them the days of
struggling to get their practical heads around the concepts.

However, since this is probably a 15 page or so document, I realized
this could be quite rude to those on dial up or metered connections.
Would it be appropriate to post my summary here? Thanks - John

Re: A sysadmin's understanding of HFSC and IFB

[Eric Dumazet]

Le vendredi 09 décembre 2011 à 02:17 -0500, John A. Sullivan III a
écrit :
> Hello, all.  I've been trying to summarize my last week's worth of
> research into HFSC and IFB.  Being neither a developer nor a
> mathematician, I found most of the existing documentation daunting and
> am truly grateful for the help I received on this list to understand the
> technologies.
> 
> I do not currently have a blog to post this research and so was thinking
> of posting it to this list so that it could be archived and searchable
> for other poor sysadmin types like me to save them the days of
> struggling to get their practical heads around the concepts.
> 
> However, since this is probably a 15 page or so document, I realized
> this could be quite rude to those on dial up or metered connections.
> Would it be appropriate to post my summary here? Thanks - John
> 

Please post here, thats definitely a good idea.

I am pretty sure your contribution could serve to add a page to 

http://www.linuxfoundation.org/collaborate/workgroups/networking/group

I believe we lack documentation. A lot.

Re: A sysadmin's understanding of HFSC and IFB

[Dave Taht]

you'd also be more than welcome to put it on bufferbloat.net's wiki.

I'm not huge on putting stuff that might need revision in email. Too
many of our problems
are created by old, in-accurate data in the field.

That said, where eric proposes is fine by me.

On Fri, Dec 9, 2011 at 8:17 AM, John A. Sullivan III
<jsullivan@opensourcedevel.com> wrote:
> Hello, all.  I've been trying to summarize my last week's worth of
> research into HFSC and IFB.  Being neither a developer nor a
> mathematician, I found most of the existing documentation daunting and
> am truly grateful for the help I received on this list to understand the
> technologies.
>
> I do not currently have a blog to post this research and so was thinking
> of posting it to this list so that it could be archived and searchable
> for other poor sysadmin types like me to save them the days of
> struggling to get their practical heads around the concepts.
>
> However, since this is probably a 15 page or so document, I realized
> this could be quite rude to those on dial up or metered connections.
> Would it be appropriate to post my summary here? Thanks - John

you'd also be more than welcome to put it on bufferbloat.net's wiki.

I'm not huge on putting stuff that might need revision in email.

Too many of our problems are created by old, in-accurate data in the field.

That said, where eric proposes is *fine* by me, but I think we have a need
for 'living' documents on issues such of this, and email and static web
sites, the wrong thing.


>
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html



-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
FR Tel: 0638645374
http://www.bufferbloat.net

Re: [WARNING - VERY LONG] A sysadmin's understanding of HFSC and IFB

[John A. Sullivan III]

On Fri, 2011-12-09 at 08:59 +0100, Eric Dumazet wrote:
> Le vendredi 09 décembre 2011 à 02:17 -0500, John A. Sullivan III a
> écrit :
> > Hello, all.  I've been trying to summarize my last week's worth of
> > research into HFSC and IFB.  Being neither a developer nor a
> > mathematician, I found most of the existing documentation daunting and
> > am truly grateful for the help I received on this list to understand the
> > technologies.
> > 
> > I do not currently have a blog to post this research and so was thinking
> > of posting it to this list so that it could be archived and searchable
> > for other poor sysadmin types like me to save them the days of
> > struggling to get their practical heads around the concepts.
> > 
> > However, since this is probably a 15 page or so document, I realized
> > this could be quite rude to those on dial up or metered connections.
> > Would it be appropriate to post my summary here? Thanks - John
> > 
> 
> Please post here, thats definitely a good idea.
> 
> I am pretty sure your contribution could serve to add a page to 
> 
> http://www.linuxfoundation.org/collaborate/workgroups/networking/group
> 
> I believe we lack documentation. A lot.
<snip>
OK - it's almost ready.  The only problem I know if is that, when I do
the math based upon my explanation, I sometimes violate an rt curve when
I should not.  I posed that in an email to the list entitled "An error
in my HFSC sysadmin documentation".  If anyone can figure out where my
error is, I will gladly change the documentation.  Here's what I have.
The graphics except the ASCII art are obviously missing.  All
corrections and suggestions very gratefully accepted - John


IFB
The Intermediate Functional Block (IFB) device is a pseudo-interface to
which traffic can be redirected by using a tc filter with the mirred
(mirror/redirect I assume) action.  The primary documentation appears to
be at
http://www.linuxfoundation.org/collaborate/workgroups/networking/ifb but
I found it less than helpful.  Perhaps the most helpful information was
found in a discussion on the mirred tc filter action at
http://www.sephidev.net/external/iproute2/doc/actions/mirred-usage and
particularly this section:
Remember that IFB is a very specialized case of packet redirecting
device. Instead of redirecting it puts packets at the exact spot
on the stack it found them from.
In other words, we redirect or mirror traffic from an interface into the
ifb interface and, when ifb is finished with it, it puts it right back
onto the interface which was redirected into it.  Why would one want to
do that?
Diagnostics are one important reason, e.g., to capture dropped packets.
Packets may be dropped on the interface either because of an iptables
rule or a traffic limiting rule.  The packets can be mirrored onto an
ifb interface which will see them before they are dropped allowing
packet analysis on them.  Another would be in a Linux based switch to
port mirror traffic from one port to another.
Another reason is for applying identical traffic shaping rules to
multiple interfaces.  Let's say one is using complicated traffic shaping
rules with several qdiscs (queue disciplines), classes, and filters and
the same set applies to many interfaces.  Rather than defining and
maintaining this complex set for multiple interfaces, one could set a
filter for each of those interfaces to redirect into an ifb interface
and apply the complex traffic shaping there.
A final reason is both complex and critically important, especially for
SimplicITy and Firepipes (or anyone using VDI across the Internet):
ingress traffic shaping.  Normal Linux ingress traffic shaping can only
police.  Policing cannot really shape packets.  It can edit them, drop
them, pass them, or do nothing.  One of the important goals of either
policing or shaping ingress traffic is to give us a fighting chance to
shape inbound traffic from the Internet when we have no control over the
upstream router.
For example, we may prioritize NX/RDP/Citrix and VoIP traffic outbound
to the Internet so that it is prioritized over web browsing and sending
huge email attachments or FTP transfers.  But, if someone starts pulling
down a huge file and consumes all the inbound bandwidth, our desktop
sessions can slow to a crawl and our VoIP calls become unintelligible.
We might face a similar problem if we host our own web servers; our web
servers could slow to a crawl in the public perception if their ability
to respond to queries is being blocked by monster downloads into our
network.  How can we keep the bulk traffic internal users are
downloading from mangling our time critical traffic?
The basic idea is to use the flow control mechanisms of traffic flow.
This is built in to any TCP transmission and may or may not be in the
upper layers of a UDP stream.  If we start dropping inbound packets, the
other side should get the point and start throttling its flow.
The recommended way to do this is to place an egress filter on the
internal interface of the firewall, i.e., we only let the firewall place
traffic on the internal network at a particular rate.  Egress traffic
shaping can be very powerful so we can use something like HTB
(Hierarchical Token Bucket) to reserve bandwidth for time sensitive
traffic but allow that bandwidth to be used for bulk traffic it is not
needed for time sensitive traffic.  We can also distinguish between well
behaved traffic (like most TCP traffic) and most poorly behaved traffic
which won't throttle (like most UDP traffic) and not allow UDP traffic
to use extra bandwidth if available.
This is fine if the firewall has only a single internal interface.  The
bulk traffic can only be output at the traffic shaping speed and, when
the inbound buffer overflows, packets will drop and the well behaved
application on the other end should throttle.  But what if we have a DMZ
or, as we often do with Firepipes, multiple internal interfaces?
Throttling the egress of the internal interface would also throttle
traffic flowing to it from the DMZ or other internal interfaces; that
would be very bad.
In these cases, it is better to create an ingress filter, i.e., filter
the traffic coming in off the Internet.  As mentioned, an ingress filter
can only police so the only way we can throttle download traffic is to
drop the packets.  We could create several bands to reserve bandwidth
for different types of traffic and drop packets which exceed those
bandwidth limits but we have no ability to do complex traffic shaping
such as allowing bulk traffic to use available bandwidth from higher
priority traffic if it is available.
This is where IFB comes into play.  We can redirect the inbound traffic
into an IFB interface and then apply an egress filter with full traffic
shaping to the IFB.  This will shape the traffic before it is placed
back onto the inbound interface.
This would allow us to use something like HTB on the inbound traffic so
that we could reserve bandwidth for time sensitive traffic, limit
bandwidth for bulk traffic, yet allow the bulk traffic to use the time
sensitive bandwidth when it is available.  But what happens if the bulk
traffic is using the bandwidth and a time sensitive packet arrives? It
is now queued behind the bulk packets and can suffer intolerable delay.
This is where HFSC steps in.
HFSC
HFSC (Hierarchical Fair Service Curve) is an incredibly powerful but,
again, poorly documented qdisc.  Its outstanding feature over qdiscs
like HTB is that it separates latency guarantees from bandwidth
guarantees.  In other queue disciplines, the only way to guarantee lower
latency is to allocate more bandwidth.  This is counter productive with
technologies such as VoIP which require low latency but send very small
packets and typically require far less bandwidth per flow than bulk
applications.  HFSC has three goals:
1. Decouple latency requirements from bandwidth requirements
2. Provide guaranteed bandwidth when specified
3. Fairly share available extra bandwidth
It recognizes it cannot always achieve all three goals and will preserve
guaranteed bandwidth over fair sharing when there is a conflict.
The paper describing HFSC is at
http://www.cs.cmu.edu/~istoica/hfsc_extended.ps.gz (with a note that
says, "You might need to treat it first with: sed "s|\[FontBBox
\]|/FontBBox load |" as it was generated with a little bit old (ancient)
idraw version." It is highly technical and mathematical but has some
excellent graphics to illustrate the principles.
A related site is http://www.cs.cmu.edu/~hzhang/HFSC/main.html
The latest man pages are a little less mathematical but still pretty
dense with the references to functions to describe the service curves.
I've downloaded the latest man pages
(http://git.kernel.org/?p=linux/kernel/git/shemminger/iproute2.git;a=blob_plain;f=man/man7/tc-hfsc.7;hb=HEAD and http://git.kernel.org/?p=linux/kernel/git/shemminger/iproute2.git;a=blob_plain;f=man/man8/tc-hfsc.8;hb=HEAD) to Tech/Equipment/Endian; they can be read with:
nroff -mandoc -rLL=<width>n <page> | less
A commonly reference resource is http://linux-ip.net/articles/hfsc.en/
I also found http://www.sonycsl.co.jp/~kjc/software/TIPS.txt helpful.
However, many articles attempting to explain HFSC didn't seem to really
get it - especially the part about decoupling latency and bandwidth
requirements.  It is all quite confusing and not well understood.  In
fact, as I'm thinking about how to record what I have learned, I'm
really struggling because there is no simple way to describe HFSC!
Let's break down the terms.  It is hierarchical because bandwidth can be
allocated and controlled on a hierarchical basis.  For example, the top
level of the hierarchy might be our overall available bandwidth.  The
next level of the hierarchy might be gold level customers who get 70% of
the available bandwidth and regular customers who get 30%.  The next
level might be individual customers or groups of customers who divide
the 70% or 30% allocated to their parent.  The final hierarchy might be
groups of traffic like VoIP, interactive, web, or bulk.  These end nodes
are called leaf nodes.  There is an important distinction between leaf
nodes and container nodes.  Bandwidth guarantees are only made at the
leaf node level.  Containers are only used for link sharing, i.e., how
excess bandwidth is shared when it is available.  Remember that we said
HFSC enforces guarantees even if it means bandwidth is not shared
evenly.  Bandwidth guarantees are always honored (if physically
possible) regardless of the bandwidth allocated to the higher layers of
the hierarchy.  Thus one must be careful to not overallocate bandwidth
at the leaves.
Moreover, the fair sharing of bandwidth only happens between peers.  In
other words, using our example, only two peers contend for the overall
bandwidth - Gold and Regular.  If the second level hierarchy of Gold has
clients A, B, and C and the second level of Regular has D and E, D and E
contend for Regular's share of the bandwidth and A, B, and C contend for
Gold's share of the bandwidth but, for example, D never contends with B
because they are in different parts of the tree.  Only peers contend for
available bandwidth.
So that explains "hierarchical."  What do we mean by fair? This refers
to how available extra bandwidth is allocated between those groups which
need it.  Let's say that we have 100Mbps of bandwidth divided into four
groups of traffic - Gold (40%), Silver (30%), Bronze (20%), and Regular
(10%).  Let's say that no Gold or Bronze users are active so 60% of our
bandwidth is unallocated but both Silver and Regular could use as much
bandwidth as we can give them.  How do we fairly share that 60% between
Silver and Regular? HFSC uses a concept called virtual time to which we
will return later.  In effect, it will divide the 60% in proportion to
the traffic allocated to each group asking for more.  Specifically, in
this case, three shares of bandwidth will be allocated to Silver for
every one allocated to Regular (30:10).
This is another area where HFSC is brilliant over other queue
disciplines.  For example, what if we have a stream of traffic that
doesn't require much bandwidth but, when it needs more, we need to
prioritize it over bulk traffic? If our service guarantees are that VoIP
gets a guaranteed 10% of the bandwidth, web traffic gets 30% and bulk
gets 60%, when web is inactive and both VoIP and bulk need more, the
excess would be allocated to bulk in a 6:1 ratio.  That's not good.  But
remember we said that guaranteeing bandwidth and sharing bandwidth are
two separate and sometimes conflicting functions in HFSC.  Thus, we can
say that VoIP is guaranteed 10% but, when it comes to sharing available
bandwidth, VoIP should get 70%, web gets 20%, and bulk gets 10%.
Brilliant! This is done by means of service curves, the last part of
Hierarchical Fair Service Curve traffic shaping.
A service curve is a mathematical way of describing how much service a
process is given over time.  The use of the term curve can throw us
non-mathematicians for a "curve" until we remember that, in strict
mathematical terms, a straight line is a curve - a curve which
represents a linear function.  To translate all that: a service curve is
the allocated bandwidth.  The y axis is the amount of data transferred
(service given) and the x axis is time.  The greater the bandwidth, the
steeper the slope of the curve (line).  Another brilliant thing about
HFSC is that a service curve can have two lines, i.e., for a certain
period of time one bandwidth can be allocated and after that time
period, a different bandwidth can be allocated.  I'll refer to this as a
"di-linear" curve.  This is how HFSC decouples bandwidth from latency
but we'll come back to that.
A service curve can be defined using tc with a single parameter if we
only need one line or with three parameters if we need two lines.  There
are two ways the parameters can be given to tc.  The mathematically
oriented way is "m1 <value> d <value> m2 <value>" where m1 is the slope
of the first curve (line for the non-mathematicians - translate: the
initial bandwidth), m2 is the slope of the second curve (translate: the
second bandwidth setting) and d is the intersection of the two curves
(translate how long we use the first bandwidth before switching to the
second bandwidth).
The second, more system administrator oriented syntax is "umax <value>
dmax <value> rate <value>".  This syntax makes it a little easier to see
how HFSC separates guarantees for latency from guarantees for bandwidth.
The rate parameter is the second curve.  In practical terms, this is the
guaranteed bandwidth.  The umax parameter is the size of some unit of
data.  It will often be the size of a data packet, e.g., 1514 bytes
(does not need to include CRC, preamble, or inter-frame gap) but it
could be some other unit.  For example, some have suggested that one
could use this so that the text portion of web pages are delivered with
low latency and the rest of the non-text, typically larger data
transmissions, will follow at a slower pace.  If the typical text page
size is 10KB, we might set umax to 10KB. Of course, this assumes that
text is always sent first. The dmax parameter is the maximum delay that
umax can tolerate.  So we might say that the first 1514 byte packet must
be delayed no more than 20ms, or the first 10KB of web page transmission
should be delayed no more than 100ms.  This is how bandwidth and latency
guarantees are separated.
Let's illustrate this a little further.  Let's say we have an FTP
transfer which is running as fast as its guaranteed bandwidth.  We also
have a VoIP traffic stream also running within its guaranteed bandwidth.
The classic problem is that my VoIP packet which must be delivered on
time is sitting behind my much larger FTP packet which is allowed to be
sent because it is within the guaranteed bandwidth for FTP.  How do I
jump the VoIP packet ahead of the FTP packet?
HFSC will see that both packets are eligible to be sent because both are
within the bandwidth limits set for their kind of traffic.  It then sees
that the FTP traffic only has a bandwidth guarantee, i.e., it can meet
its obligations to the FTP traffic as long as the packet is delivered
within the time frame necessary to meet the bandwidth requirements
regardless of how much the packet is delayed (as long as the delay is
not so long as to violate the bandwidth requirements).  It then looks at
the equally eligible VoIP packet and sees that, not only does it have an
obligation for bandwidth but it also must not delay this packet for more
than, say, 20ms.  In effect, it looks at the deadline for delivering the
FTP packet and compares it to the deadline for delivering the VoIP
packet and if the deadline for the VoIP packet is sooner than the
deadline for the FTP packet, it will service the VoIP packet first.
But how, exactly, does it work? It is done by the interplay of service
curves and timers.  In fact, we will come to see that eligible and
deadline are actually technical terms to describe some of the timers but
first, let's step back and explain a little more about service curves.
Service curves
There are actually three service curves used by HFSC.  They are:
1. The real-time service curve (rt)
2. The link-sharing service curve (ls)
3. The upper limit service curve (ul)
The abbreviations are used to specify which service curve we are
describing in the tc syntax, e.g., 
tc add class dev <device> parent parentID classid <ID> hfsc [ [ rt SC ]
[ ls SC ] | [ sc SC ] ] [ ul SC ] 
SC is the description of the curve as described above using m1 d m2 or
umax dmax rate, e.g., 
tc add class dev <device> parent parentID classid <ID> hfsc rt 1514b
20ms 200kbits
If we are not using two curves, we only need the last parameter, e.g., 
tc add class dev <device> parent parentID classid <ID> hfsc ls 500kbits
The sc parameter is used when rt and ls are the same, i.e., one can
specify them both in one definition rather than needing to write two.
It is not usual to specify all three curves in the same class.  The rt
parameter is only used on leaves.  The ul parameter is usually not used
leaves.
Real-time service curve
Real-time service curves can only be applied to leaf nodes (remember
this is Hierarchical Fair Service Curve).  Using our previous example,
rt curve would not be applied to "Gold Clients" but to "Web traffic".
The rt curves can have either one curve (line) or two.  In fact, it is
usually only rt curves which have two curves; ls and ul curves generally
do not.  If the first curve is steeper than the second curve
(translated: if the initial bandwidth guarantee is greater than the
sustained bandwidth guarantee), the curve is called concave in HFSC
terminology.  If the opposite is true, it is called convex.  This is
illustrated by the below graphic copied from
http://www.cs.cmu.edu/~hzhang/HFSC/main.html
One must be careful when specifying rt curves because they will be
honored above all other curves (remember we said that, when it is
impossible to satisfy the requirements for both guaranteed bandwidth and
fair sharing, guaranteed bandwidth wins).  This will be more
understandable when we discuss the upper limit (ul) curve.  To jump
ahead a little bit, the ul is typically though not exclusively used to
describe the maximum bandwidth available, e.g., a T1 circuit or a cable
connection.  We said that rt is honored above all other curves.  If the
ul curve says the maximum bandwidth available is 10 Mbps and the sum of
all our rt curves is 20 Mbps, the system will try to guarantee 20 Mbps
which, of course, means it will fail to meet its guarantees under
maximum load.
Jumping ahead once more, rt curves override ls curves, too.  The ls
curves are used to share extra bandwidth fairly.  So, if the ls curve
dictates that class A should have 2 Mbps of our 10 Mbps link and class B
should have 8 Mbps but the rt curve says that class A is guaranteed 3
Mbps, class A will get 3 Mbps and class B only 7 Mbps.  The rt curve
will always be honored whenever it is physically possible.  The bottom
line is that the rt service curve always "wins."
An important point to remember is that the rt curve determines the
bandwidth and latency guarantees, is the only curve which determines
bandwidth and latency guarantees, and has nothing to do with how
bandwidth is fairly shared (other than to override that sharing if
necessary!).  To put it another way, the function of the rt service
curve is independent of the ul and ls service curves.  They handle two
completely separate characteristics of HFSC.
Upper limit service curve
As mentioned above, the ul curve is often used to describe the maximum
bandwidth available.  More specifically, it sets an upper boundary to
the bandwidth which can be allocated by the ls curve.  As we will see,
the ls curve is used to determine how the excess available bandwidth is
fairly shared.  The ul service curve sets limits on that sharing.
Let's get some vocabulary defined.  Link sharing is the term used by
HFSC to describe how the bandwidth not actively used by the rt service
curve is fairly allocated among the rest of the network sessions which
are requesting bandwidth.  Let's connect the dots again as a way of
review.  Remember, the rt curve defines the guaranteed amounts of
bandwidth.  Let's go back to our 10 Mbps circuit and say we have VoIP
with an rt service curve rate of 1 Mbps, interactive traffic with an rt
service curve rate of 5 Mbps, web traffic with an rt service curve rate
of 2 Mbps, and bulk traffic with an rt service curve rate of 1 Mbps.
Note that the sum of the rt curves does not need to equal the total
bandwidth.  Now let's say it's the middle of the night so the phones are
not in use and no one is generating interactive traffic however web
traffic to our internal web servers is going at full speed as are our
overnight off site backups and FTP transfers.  Web is guaranteed 2 Mbps,
bulk is guaranteed 1 Mbps and link sharing will figure out how to divide
up the remaining 7 Mbps.  However, the ul curve could override the way
link sharing divides that 7 Mbps.
Let's illustrate how and learn more about ul at the same time.  The ul
service curve is normally specified at the top of the hierarchy and is
set to the maximum bandwidth available.  Think way back to when we said
that link sharing only happened between peers.  Classes lower in the
hierarchy can only contend for the bandwidth allocated to their parent
and not for bandwidth allocated to classes at the same level but under a
different parent.  Once again, I will copy a graphic from
http://www.cs.cmu.edu/~hzhang/HFSC/main.html to illustrate this:
Since children can only contend for the bandwidth allocated to their
parents, the ul limit on bandwidth flows down through the entire tree
under it.  If the parent with the ul limitation cannot receive the
bandwidth, its children cannot contend for it.  Thus, by placing the ul
at the top of the hierarchy and setting it to the maximum bandwidth
available, it flows down through the entire tree and we do not need to
define it in every descendant class.  That is, unless we want to
override it further down the tree.
Let's go back to our illustration.  If we had set ul rate 10240kbits (10
Mbps), the web traffic and the bulk traffic will be sharing the 7 Mbps
available bandwidth in whatever ratio was specified in their ls service
curves.  If no ls curves were specified, they will divide the bandwidth
according to their rt curves - in this case a 2:1 split.  For now, let's
assume that the ls curve is the same as the rt curve, that is 2 Mbps for
web and 1 Mbps for bulk.  Remember that the ul curve sets a limit on the
ls curve.  What if, for some reason, we wanted to make sure that bulk
traffic never exceeds 3 Mbps even if there is more available?  We would
create a  second ul service curve for the bulk traffic on the bulk
traffic class with ul rate 3072bkits.
Link sharing will try to allocate an extra 2.33 Mbps to bulk traffic
(7 / 3).  When this link sharing bandwidth is added to the guaranteed
bandwidth of 1 Mbps, we come out to 3.33 Mbps.  Since this is exceeds
the ul service curve set specifically for bulk traffic, link sharing
will not be able to service bulk traffic at 3.33 Mbps.  It will only be
able to provide service at 3 Mbps.  The rest will go to the web service.
So, to summarize, the ul service curve is not used to guarantee
bandwidth or latency.  That is the job of the rt service curve.
Allocated bandwidth can exceed the ul service curve if the sum of the rt
service curves is greater than the ul service curve and the circuit can
support the higher rt bandwidth allocation.  This is another way of
saying the rt guaranteed bandwidth always takes precedence.  The ul
service curve is used to determine the link sharing bandwidth, i.e., the
bandwidth allocated to classes of traffic from the unused portion of the
available bandwidth.  It is specifically used to limit how much
bandwidth can be allocated through link sharing, is typically set to the
maximum bandwidth of the circuit, and is normally set at the top of th
hierarchy because its affect is to flow down to all classes underneath
it.
Link-sharing service curve
The ls service curve is not used to guarantee bandwidth or latency.  Its
sole purpose is to determine the proportions in which unused bandwidth
is allocated to classes which are requesting more than their guaranteed
bandwidth, that is link sharing.  Although it is good practice to use
service curves with numbers that are realistic for the available
bandwidth, technically, only the ratio is important.
Let's illustrate by returning to our previous example.  The ul is set to
a rate of 10 Mbps.  We would expect the web ls service curve to use a
rate of 2 Mbps and the bulk ls service curve to use a rate of 1 Mbps.
However, we could say the web ls sc is 200 Mbps and the bulk ls sc is
100 Mbps and it would not break and not be illegal - just confusing.
The ratios are the same (2:1) and it is only the ratios which are
important.
The discussion about ul service curves has "stolen the thunder" from the
ls service curve discussion, i.e., there is not much left to say.  The
ls service curves determine how link sharing works, i.e., how the
bandwidth with is not being used to satisfy the guarantees of the rt
service curves is fairly allocated among all the other network traffic
flows who would like more bandwidth than they are guaranteed.
The Linux and BSD implementation of HFSC go beyond the original
specification by allowing us to specify the ls service curve separately
from the rt service curve.  This gives us some powerful flexibility as
we are about to illustrate.
Let's extend our previous example.  Remember we have a 10 Mbps circuit
and thus have set the ul service curve rate at the top of the hierarchy
to 10 Mbps.  We have four classes of traffic, VoIP, interactive, web,
and bulk.  The rt rate for VoIP is 1 Mbps, for interactive 5 Mbps, for
web 2 Mbps, and for bulk 1 Mbps.  That accurately reflects our desire
for guaranteed bandwidth but those proportions may not accurately
reflect how we want any available excess bandwidth distributed.
For our purposes, link sharing should have the following
characteristics.  Bulk should be able to use all the bandwidth if it is
available and uncontended.  However, if the VoIP traffic needs extra
bandwidth and there is available bandwidth, it should be granted that
extra bandwidth with priority since we do not want to starve our voice
traffic.  Furthermore, we want visitors to our web site to have a
positive experience and not one with substantial delays so, if there is
contention between bulk and web traffic, we want web traffic to take
more than a 2:1 ration of available bandwidth.  Thus, we might setup our
tc classes as follows:
VoIP:
tc add class dev eth0 parent 1:1 classid 1:10 hfsc rt rate1024kbits ls
rate 7168kbits
We first thought this should be rt umax 222b dmax 5ms rate 1024kbits
because the maximum sized VoIP packet is typically 222 bytes (ulaw/alaw
at 64Kbps = 8KB/s * 0.020s (20 ms per packet) = 160 Bytes + 8 (UDP
header) + 40 (IP header) + 14 (Ethernet header) = 222 Bytes) and we want
it delayed in the router for no more than 5ms.  However, to guarantee 1
Mbps bandwidth, a 222 byte packet needs to be sent within roughly 1.7ms
(222 * 8 = 1776 bits / (1024 * 1024)bits/s = 0.0017s).  Thus, our rate
is sufficient and we do not need to jump the delivery of VoIP packets by
specifying a larger initial bandwidth.
Interactive
tc add class dev eth0 parent 1:1 classid 1:11 hfsc sc rate5120kbits
We use sc since we want rt and ls to be the same
Web:
tc add class dev eth0 parent 1:1 classid 1:12 hfsc rt rate 2048kbits ls
rate 3072kbits
Bulk:
tc add class dev eth0 parent 1:1 classid 1:12 hfsc sc rate 1024kbits
Note that the sum of our ls service curves exceeds the ul service curve.
This is not a problem.  Remember it is only the ls service curve ratios
which are meaningful.  So what have we done? Even though our guarantees
can be met with a proportion of 1:5:2:1, we have specified that, if
there is extra bandwidth available and, if there is contention for it,
distribute it in the ratio of 7:5:3:1.  In other words, if interactive
and web are idle and VoIP and bulk can use more bandwidth than their
guarantees (backlogged in HFSC terminology), the bandwidth will be
allocated between VoIP and bulk at a 7:1 ration and not a 1:1 ratio.
Likewise, if VoIP and interactive are idle and web and bulk are
backlogged, the extra bandwidth will be allocated at a 3:1 ratio rather
than a 2:1 ratio.  Can we see the value of having separate rt and ls
service curves?
Timers
However, service curves are not the whole story.  In fact, it is not
really the service curves which determine which packet is sent when.
The service curves are used to set the timers and it is the timers which
determine which packet is sent when.
While service curves are quite understandable to system administrator
types once we translate the vocabulary (curves = bandwidth, umax and
dmax = latency (technically bandwidth I suppose but, latency in
practicality)), timers are they mysterious art of programmers and
mathematicians - an impenetrable black box.  Let's see if we can pry
open that black box and make it at least a little understandable to us
sysadmin types.
HFSC uses four separate timers to work its wonders:
1. Fit time
2. Virtual time
3. Eligible time
4. Deadline time
Virtual time
Let's start with virtual time.  Virtual time is used by link sharing to
determine which queue should be serviced to keep things fair, that is to
keep the bandwidth in proportion to the ls service curve ratios.
Virtual time appears to be a very complicated topic addressing
mind-bending issues like how to preserve fairness among several
backlogged queues when a new queue becomes backlogged as well and to
preserve this fairness without starving one of the queues while the
others catch up. Thus my explanation will be a dramatic
oversimplification but hopefully enough to give fellow sysadmins a
toehold to ascend this seemingly sheer rock face.
Virtual time is a measure of how much time has been spent servicing the
queue and how much it will take to service the next packet.  Here is a
very good ascii art representation copied from
http://www.sonycsl.co.jp/~kjc/software/TIPS.txt :
                    bytes         
                         |                   /
                         |                  /service curve
                         |                 /
           next   -->+   +----------------+
           packet    |   |               /|
           length    |   |              / |
                     |   |             /  |
           total --> +   +------------+   |
           bytes         |           /|   |
           already       |          / |   |
           sent          |         /  |   |
                                  /   |   |
                                      |   |
                                      |   |
                              --------+---+--------------> time
                                          vt for next packet
                                      vt for previous packet

Not surprisingly, this makes a great deal of sense when we digest it.
Remember, the service curve we are using is the ls service curve, i.e.,
the one for link sharing.  The more the bandwidth allocated to the ls
service curve, the steeper the slope of the line.  The steeper the slope
of the line, the shorter the time to transmit the packet = the more
bandwidth, the shorter the time to transmit the packet.  Thus, the
change in virtual time for the same sized packet is less for a faster
queue than for a slower queue.  We'll see why that is important in a
second.
Remember that link sharing is used only among peers.  Only peers can
contend for available extra bandwidth.  Fairness is achieved in HFSC by
trying to keep the virtual time of all peers equal.  When a queue
becomes backlogged, i.e., needing more than its guaranteed bandwidth, it
starts accumulating virtual time.  The more it has been serviced while
backlogged, the more virtual time it accumulates.
When HFSC looks at the various backlogged queues, how does it determine
which one to service? Look again at the above diagram.  Each queue will
have its current virtual time and the virtual time that it will have
after it sends its next packet.  HFSC will choose the next packet which
will have the lowest virtual time.  Let's make this more understandable
with some real illustrations.  Let's say we have two backlogged queues
with identical ls service curves and each has a full sized Ethernet
packet pending.  Queue A has accumulated virtual time of 1000ms and
Queue B has accumulated virtual time of 999ms.  Let's say that sending
the full sized Ethernet packet will take 2ms.  The virtual time after
Queue A sends its packet would be 1002 whereas Queue B would be 1001ms
so HFSC sends Queue B's packet.  Now Queue B has VT (virtual time) of
1001ms and the next packet would bring it to 1003ms.  Queue A has VT of
1000ms and sending the next packet would bring it to 1002ms.  HFSC
chooses the packet which will result in the lowest VT thus it sends the
packet in Queue A.  See how it tries to keep the virtual times equal and
thus produces fairness.
Now let's alter the scenario.  Let's keep the virtual time the same,
1000ms for Queue A and 999ms for Queue B but Queue A is handling small
packets which only take 0.5ms to send.  Queue A has one of these packets
ready to send while Queue B has one of its full sized packets to send.
VT for Queue A after sending its packet would be 1000.5ms and for Queue
B would be 1001ms so, even though Queue A has already received more
service, it is services again because its final virtual time would be
smaller.
More importantly, let's go back to the idea that both Queue A and Queue
B use full sized packets but this time the ls service curves are not
equal.  Let's say the ls service curve rate for Queue A is 5120kbits and
for Queue B is 1024kbits.  Thus, a packet that would take Queue B 2ms to
transmit would take Queue A 0.4ms to transmit.  Both queues are
continually backlogged so they always have packets to send.  HFSC takes
a look and calculates the next VT for Queue A as 1000.4 and Queue B as
1001 so it sends Queue A.  It calculates again and A is 1000.8 and B
1001 so it sends A again.  The next calculation of VT puts A at 1001.2
and B at 1001 so it sends B.  The next calculation puts A at 1001.2 and
B at 1003 so A is sent.  Then 1001.6 versus 1003, then 1002 vs. 1003,
then 1002.4 vs. 1003, then 1002.8 vs. 1003, then 1003.2 vs. 1003.  Can
you see how the virtual time calculation is allocating service to Queue
A at a 5:1 ratio with Queue B - just the fairness we requested via the
ls service curves.
So, in summary, virtual time used to produce fairness when distributing
available excess bandwidth to backlogged queues in the ratio of the ls
service curves.  It does this by trying to keep virtual times for all
peers in the hierarchy equal and it does this by always choosing the
packet to send which will result in the smallest virtual time.
Fit time
Fit time is pretty simple to understand.  Recall that we said the ls
service curve was bounded by the ul service curve, i.e., even if a queue
should get say 10 Mbps according to link sharing, if the ul (Upper
Limit) service curve says we can use 8 Mpbs maximum, we are only going
to get 8 Mbps.  Fit time takes into account the ul service curve.
In effect, fit time looks at what the clock time would be to send the
packet based upon the ul service curve rate, i.e., what the time would
be to send the pending packet at the maximum transmission rate.  If that
time is later than the current clock time, the packet will not be sent
not matter what virtual time says.  If the current clock time is later
than fit time, i.e., we would not have exceeded out bandwidth
limitation, then the decision is made based upon virtual time.
As a reminder, this is all for traffic over and above the guaranteed
rate, i.e., the rt service curve rate.  Packets are always sent to
preserve the rt service curve rate as long as it is physically possible
regardless of fit time or virtual time.  This is the same as saying that
the rt service curve always wins or, to phrase it yet another way, to
meet the HFSC design criterion that, if there is a conflict between link
sharing and guaranteed bandwidth, choose guaranteed bandwidth.
Eligible time
The rt service curve uses two timers: eligible time and deadline time.
Recall, we used referred to eligible and deadline time toward the
beginning of this discussion when observed how HFSC provides decoupled
guarantees for both bandwidth and latency.  Like fit time, eligible time
is relative to clock time.  In other words, HFSC calculates what the
clock time would be to send the queued packet at the guaranteed rate,
i.e., the rt service curve rate.  If that time is later than the current
clock time, that packet's time has not come yet and it cannot be sent
based upon its real time guarantee.  I do believe it can be sent based
upon virtual time assuming that fit time allows it.  After all, that is
what link sharing is about - being able to exceed the guaranteed
bandwidth if there is extra bandwidth available.  On the other hand, if
current clock time is later than eligible time, then this packet had
better get moving because it is potentially running behind schedule.
So, eligible time is just as then name implies; it is the time the
packet becomes eligible for sending based upon the real-time service
curve, i.e., the guaranteed bandwidth/latency.
An important point to understand the difference between eligible time
and deadline time is that eligible time is measured from the beginning
or head of the packet, i.e., is HFSC ready to begin sending this packet.
But what happens when more than one queue has packets whose eligible
time has come? That's where deadline time comes into play.
Deadline time
Deadline time is closely related to eligible time and is likewise
measured against clock time.  However, deadline time is measured against
the end or tail of the packet, i.e., by when must we have finished
sending this packet at the specified bandwidth in order to meet our
packet delivery guarantees for bandwidth and latency.  Once again,
http://www.sonycsl.co.jp/~kjc/software/TIPS.txt has an excellent ASCII
graphic for illustrating the relationship between eligible time measured
at the beginning of the packet and deadline time measured from the end:
                    bytes         
                         |                   /
                         |                  /service curve
                         |                 /
           next   -->+   +----------------+
           packet    |   |               /|
           length    |   |              / |
                     |   |             /  |
      cumulative --> +   +------------+   |
           bytes         |           /|   |
           already       |          / |   |
           sent          |         /  |   |
                                  /   |   |
                                      |   |
                                      |   |
                              --------+---+--------------> time
                                eligible  deadline
                                time

This time, the slope is the rt service curve.  The way in which HFSC
chooses from among several different queues all with packets whose
eligible time is greater than current clock time is almost identical to
the way it chooses among backlogged queues with virtual time, viz., it
chooses the packet with the lowest deadline time.  Remember that the
steeper the curve, the greater the bandwidth and the shorter the
distance between eligible time and deadline time for the same sized
packet.
Let's walk through a real example.  We have Queue A with VoIP traffic -
small, 222 byte packets and an rt service curve bandwidth such that it
takes 0.2ms to send its packets; that equates to roughly 8.88 Mbps ((222
* 8)bits/0.0002s).  Let's also assume that we have so much VoIP traffic
that the queue is filled so we always have a VoIP packet asking to be
dequeued.  Queue B is sending FTP with large packets and an rt service
curve rate such that each packet takes 2ms to send; this equates to
6.056 Mbps ((1514 * 8)bits/0.002s).  Queue B is also completely full.
Let's assume that the maximum bandwidth available is the sum of the
guaranteed bandwidths, viz., 14.936 Mbps.  This will allow us to
calculated the progress of clock time, i.e., how long it actually takes
to send each packet.  Also remember that each packet has a 4 byte CRC,
and 8 byte preamble, and a 12 byte interframe gap time at least in
traditional Ethernet.  Thus to transmit a packet in Queue A, we really
need to transmit 246 bytes and, to transmit one in Queue B, we need to
transmit 1538 bytes.  Thus, the elapsed time to send a Queue A packet is
(246 * 8)bits / 14,936,000(b/s) = 0.132ms and the time to transmit a
Queue B packet is (1538 * 8)bits / 14,936,000(b/s) = 0.824ms.  Sorry for
all the math but this is what is inside the black box (and a very
simplified version!).
Let's assume that clock time (CT - the actual time) is 1000ms (not
realistic but it makes the explanation easier!).  The next packet queued
in Queue A has an ET (eligible time) of 1000ms and the next packet in
Queue B has an ET of 999ms, i.e., both are eligible to be sent.  A less
sophisticated traffic shaping algorithm would send the FTP packet first.
However, HFSC calculates the deadline time (DT) for the packet in Queue
A at 1000.2 (1000 + 0.2) and the deadline time for the packet in Queue B
at 1001ms (999 + 2) so it sends A instead since it has the smaller DT.
0.132ms has elapsed in real time so CT is now 1000.132.  The
eligible/deadline times (ET/DT) for A and B respectively are
1000.2/1000.4 and 999/1001.  Notice that A is no longer eligible to send
because its ET > CT so B is serviced.  0.824ms has elapsed to send B's
packet so CT is now 1000.956.  ET/DT for A is still 1000.2/1000.4 but B
has changed to 1001/1003.  B just misses being eligible to send but A is
eligible so A is sent.  Elapsed time is 0.132, CT is now 1001.088, ET/DT
for A is 1000.4/1000.6.  Both A and B are eligible at the same time
again as both their ETs <= CT.  A's DT is less than B's DT so A is
serviced.  
In fact, A will send 11 packets.  Let's see the result after A sends 11
packets.  Elapsed time is 11* 0.132 = 1.452ms so clock time is 1002.54.
A's ET/DT have incremented by 11 * 0.2 so they are 1002.6/1002.8.  B's
ET/DT have remained at 1001/1003.  A is no longer eligible so the fact
that its DT is less than B's DT is irrelevant.  B is serviced.
Pulling it all together
To this point, almost all of our discussion have involved rt service
curves based solely upon rate and we have been using some fairly large
circuits to illustrate.  What happens when our bandwidth really is
constrained such as a T1 circuit or the upload bandwidth of an
asymmetric DSL or cable connection and we need to balance time sensitive
traffic with bulk traffic? This is where di-linear curves save the day.
The best illustration I have found is from the SIGCOM97 paper on HFSC:

The results might not be obvious at first.  The packets arriving, e.g.,
coming from the internal network and heading toward the constricted T1
circuit  (well, in this specific example, it is a 10 Mbps circuit) are
shown in the second level of graphics from the top.  The resulting
output of those packets is shown in the very bottom set of graphics.
The illustrations on the left show a mono-linear curve, i.e., just based
upon bandwidth.  The video and FTP packets are flooding in, are being
lined up and scheduled for dequeueing based upon the bandwidth only.
Thus, the initial video packet sits in queue behind the FTP packets as
there is no need to rush to meet its bandwidth requirements.  Here is
how the authors describe what is happening:
"To illustrate the advantage of decoupling delay and bandwidth
allocation with non-linear service curves, consider the example in
Figure 2, where a video and a FTP session share a 10 Mbps link . . . .
Let the video source sends 30 8KB frames per second, which corresponds
to a required bandwidth of 2 Mbps. The remaining 8 Mbps is reserved by a
continuously backlogged FTP session. For simplicity, let all packets be
of size 8 KB. Thus, it takes roughly 6.5 ms to transmit a packet."
"As can be seen, the deadlines of the video packets occur every 33 ms,
while the deadlines of the FTP packets occur every 8.2 ms. This results
in a delay of approximately 26 ms for a video packet."
Let's work through the math to make that more understandable.  HFSC is
committed to deliver 2 Mbps to video and each packet is 8KB long.  Thus,
HFSC's commitment to deliver that packet is within (8000 * 8)bits /
2,000,000(b/s) = 32ms.  I'm not quite sure why I come up with 32 and
they say 33 but we'll use 33.  In other words, to meet the deadline
based solely upon the rate, the bandwidth part of the rt service curve,
the packet needs to be finished dequeueing at 33ms.  Since it only takes
6.5ms to send the packet, HFSC can sit on the packet it received for 33
- 6.5 = 26.5ms if it needs to in order to meet the guarantees for other
traffic.  This adds unnecessary latency to the video stream.
In the second scenario, we introduce an initial, elevated bandwidth
guarantee for the first 10ms.  The bandwidth for the first 10ms is now
6.6 Mbps instead of 2 Mbps.  We do the math again and HFSC's commitment
to video to maintain 6.6 Mbps is to finish dequeueing the packet within
(8000 * 8)bits / 6,600,000(b/s) = 10ms.  Since it takes 6.5 ms to send
the packet, HFSC can sit on the packet for no more than 10 - 6.5 = 3.5
ms.  Quite a difference!
I assume for simplicity's sake, the graphic leaves out an important
point.  The rt service curve either fully or partially resets when the
queue has been drained.  Fully or partially depends on how much time has
elapsed since the last service rendered and the new service requested
when the queue becomes active again.  Thanks for Michal Soltys on the
netdev kernel mail list for clarifying this for me.
Without this reset, the first part of the service curve (the m1 portion
if you recall the earlier discussion about how service curves can be
defined) would not have much practical value because once traffic
activates the queue, only the first packet or first few packets would be
guaranteed the latency of the first, accelerated part of the curve.
Everything else would use the second part of the curve (the m2 portion -
we'll use the terms m1 and m2 for the rest of the discussion).
So let's re-examine the above example in more detail.  The video packet
arrives, uses the m1 curve, is jumped ahead of the FTP packets because
of the low latency guarantee of the m1 curve, is dequeued, and now the
queue is empty for 33.33ms (remember the video is playing at 30 frames
per second, well, 32.69ms when you account for transmission time on a
100 Mbps circuit) which allows the curve to reset.  The next video
packet comes in and it is treated according to m1 and not m2 because we
have reset the curve.  Thus, each video packet is jumped in front of any
queued FTP packets.
We can even multiplex several video streams.  As long as the queue is
allowed to go idle long enough, each of those streams will be treated
with very low latency and jumped in front of the FTP packets, i.e.,
until we have so many video streams that the queue starts to backlog.
Then they will use the m2 curve.
This is not a bad thing; it is a good thing and allows us a new
perspective on the m1 and m2 curves.  Hopefully, we have allocated
enough bandwidth in our m2 curve to properly service our video or VoiP
or whatever we are pushing through this queue.  Thus, even if we are not
receiving the accelerated treatment, we are still experiencing
sufficient service.  If our queue is badly backlogged and overflowing,
then we have a different problem and need more raw bandwidth!
In this way, we can think of the m2 curve, the second level of service
in a concave service curve (remember a concave service curve is where we
start out with a higher bandwidth and then change to a lower bandwidth),
as a circuit breaker preventing overload.  In other words, we are saying
to this prioritized traffic that we will deliver it with a lower than
normal latency (and thus higher short term bandwidth) while we can but,
if it becomes too much (as determined by the system administrator who
defined the HFSC qdisc), we will drop it down to a more sustainable rate
that will not exceed the physical capabilities of the circuit.  This
assumes we have designed our traffic shaping so that the sum of all the
m2 portions of all the rt service curves do not exceed the capabilities
of the circuit.
Another way of saying this with familiar terminology is that we can
burst at the m1 rate as long as the queue doesn't backlog but, when it
does, we drop to our sustainable rate.  Thus, concave rt service curves
are very well suited to periodic traffic, i.e., traffic which sends
packets on a recurring interval with space in between like VoIP or
video.  It may be less effective on burstable traffic such as the
example of using it to accelerate the delivery of text on a web site
unless the traffic is low enough that the queue has a chance to drain
regularly.

Re: [WARNING - VERY LONG] A sysadmin's understanding of HFSC and IFB

[Julien Vehent]

This is an amazing email and I will definitely sit down and read it 
carefully.
I've been (silently) following your discussions about HFSC because I've been 
wanting to add a section on HFSC in the TC doc I wrote here:
http://wiki.linuxwall.info/doku.php/en:ressources:dossiers:networking:traffic_control

The doc I've read so far left me staring at the wall with more questions 
than answers. I'm hoping your text will finally bring a clear view of the 
problem :)

Cheers,
Julien

On 2011-12-13 18:01, John A. Sullivan III wrote:
> On Fri, 2011-12-09 at 08:59 +0100, Eric Dumazet wrote:
>> Le vendredi 09 décembre 2011 à 02:17 -0500, John A. Sullivan III a
>> écrit :
>> > Hello, all.  I've been trying to summarize my last week's worth of
>> > research into HFSC and IFB.  Being neither a developer nor a
>> > mathematician, I found most of the existing documentation daunting and
>> > am truly grateful for the help I received on this list to understand 
>> the
>> > technologies.
>> >
>> > I do not currently have a blog to post this research and so was 
>> thinking
>> > of posting it to this list so that it could be archived and searchable
>> > for other poor sysadmin types like me to save them the days of
>> > struggling to get their practical heads around the concepts.
>> >
>> > However, since this is probably a 15 page or so document, I realized
>> > this could be quite rude to those on dial up or metered connections.
>> > Would it be appropriate to post my summary here? Thanks - John
>> >
>>
>> Please post here, thats definitely a good idea.
>>
>> I am pretty sure your contribution could serve to add a page to
>>
>> http://www.linuxfoundation.org/collaborate/workgroups/networking/group
>>
>> I believe we lack documentation. A lot.
> <snip>
> OK - it's almost ready.  The only problem I know if is that, when I do
> the math based upon my explanation, I sometimes violate an rt curve when
> I should not.  I posed that in an email to the list entitled "An error
> in my HFSC sysadmin documentation".  If anyone can figure out where my
> error is, I will gladly change the documentation.  Here's what I have.
> The graphics except the ASCII art are obviously missing.  All
> corrections and suggestions very gratefully accepted - John
>
>
> IFB
> The Intermediate Functional Block (IFB) device is a pseudo-interface to
> which traffic can be redirected by using a tc filter with the mirred
> (mirror/redirect I assume) action.  The primary documentation appears to
> be at
> http://www.linuxfoundation.org/collaborate/workgroups/networking/ifb but
> I found it less than helpful.  Perhaps the most helpful information was
> found in a discussion on the mirred tc filter action at
> http://www.sephidev.net/external/iproute2/doc/actions/mirred-usage and
> particularly this section:
> Remember that IFB is a very specialized case of packet redirecting
> device. Instead of redirecting it puts packets at the exact spot
> on the stack it found them from.
> In other words, we redirect or mirror traffic from an interface into the
> ifb interface and, when ifb is finished with it, it puts it right back
> onto the interface which was redirected into it.  Why would one want to
> do that?
> Diagnostics are one important reason, e.g., to capture dropped packets.
> Packets may be dropped on the interface either because of an iptables
> rule or a traffic limiting rule.  The packets can be mirrored onto an
> ifb interface which will see them before they are dropped allowing
> packet analysis on them.  Another would be in a Linux based switch to
> port mirror traffic from one port to another.
> Another reason is for applying identical traffic shaping rules to
> multiple interfaces.  Let's say one is using complicated traffic shaping
> rules with several qdiscs (queue disciplines), classes, and filters and
> the same set applies to many interfaces.  Rather than defining and
> maintaining this complex set for multiple interfaces, one could set a
> filter for each of those interfaces to redirect into an ifb interface
> and apply the complex traffic shaping there.
> A final reason is both complex and critically important, especially for
> SimplicITy and Firepipes (or anyone using VDI across the Internet):
> ingress traffic shaping.  Normal Linux ingress traffic shaping can only
> police.  Policing cannot really shape packets.  It can edit them, drop
> them, pass them, or do nothing.  One of the important goals of either
> policing or shaping ingress traffic is to give us a fighting chance to
> shape inbound traffic from the Internet when we have no control over the
> upstream router.
> For example, we may prioritize NX/RDP/Citrix and VoIP traffic outbound
> to the Internet so that it is prioritized over web browsing and sending
> huge email attachments or FTP transfers.  But, if someone starts pulling
> down a huge file and consumes all the inbound bandwidth, our desktop
> sessions can slow to a crawl and our VoIP calls become unintelligible.
> We might face a similar problem if we host our own web servers; our web
> servers could slow to a crawl in the public perception if their ability
> to respond to queries is being blocked by monster downloads into our
> network.  How can we keep the bulk traffic internal users are
> downloading from mangling our time critical traffic?
> The basic idea is to use the flow control mechanisms of traffic flow.
> This is built in to any TCP transmission and may or may not be in the
> upper layers of a UDP stream.  If we start dropping inbound packets, the
> other side should get the point and start throttling its flow.
> The recommended way to do this is to place an egress filter on the
> internal interface of the firewall, i.e., we only let the firewall place
> traffic on the internal network at a particular rate.  Egress traffic
> shaping can be very powerful so we can use something like HTB
> (Hierarchical Token Bucket) to reserve bandwidth for time sensitive
> traffic but allow that bandwidth to be used for bulk traffic it is not
> needed for time sensitive traffic.  We can also distinguish between well
> behaved traffic (like most TCP traffic) and most poorly behaved traffic
> which won't throttle (like most UDP traffic) and not allow UDP traffic
> to use extra bandwidth if available.
> This is fine if the firewall has only a single internal interface.  The
> bulk traffic can only be output at the traffic shaping speed and, when
> the inbound buffer overflows, packets will drop and the well behaved
> application on the other end should throttle.  But what if we have a DMZ
> or, as we often do with Firepipes, multiple internal interfaces?
> Throttling the egress of the internal interface would also throttle
> traffic flowing to it from the DMZ or other internal interfaces; that
> would be very bad.
> In these cases, it is better to create an ingress filter, i.e., filter
> the traffic coming in off the Internet.  As mentioned, an ingress filter
> can only police so the only way we can throttle download traffic is to
> drop the packets.  We could create several bands to reserve bandwidth
> for different types of traffic and drop packets which exceed those
> bandwidth limits but we have no ability to do complex traffic shaping
> such as allowing bulk traffic to use available bandwidth from higher
> priority traffic if it is available.
> This is where IFB comes into play.  We can redirect the inbound traffic
> into an IFB interface and then apply an egress filter with full traffic
> shaping to the IFB.  This will shape the traffic before it is placed
> back onto the inbound interface.
> This would allow us to use something like HTB on the inbound traffic so
> that we could reserve bandwidth for time sensitive traffic, limit
> bandwidth for bulk traffic, yet allow the bulk traffic to use the time
> sensitive bandwidth when it is available.  But what happens if the bulk
> traffic is using the bandwidth and a time sensitive packet arrives? It
> is now queued behind the bulk packets and can suffer intolerable delay.
> This is where HFSC steps in.
> HFSC
> HFSC (Hierarchical Fair Service Curve) is an incredibly powerful but,
> again, poorly documented qdisc.  Its outstanding feature over qdiscs
> like HTB is that it separates latency guarantees from bandwidth
> guarantees.  In other queue disciplines, the only way to guarantee lower
> latency is to allocate more bandwidth.  This is counter productive with
> technologies such as VoIP which require low latency but send very small
> packets and typically require far less bandwidth per flow than bulk
> applications.  HFSC has three goals:
> 1. Decouple latency requirements from bandwidth requirements
> 2. Provide guaranteed bandwidth when specified
> 3. Fairly share available extra bandwidth
> It recognizes it cannot always achieve all three goals and will preserve
> guaranteed bandwidth over fair sharing when there is a conflict.
> The paper describing HFSC is at
> http://www.cs.cmu.edu/~istoica/hfsc_extended.ps.gz (with a note that
> says, "You might need to treat it first with: sed "s|\[FontBBox
> \]|/FontBBox load |" as it was generated with a little bit old (ancient)
> idraw version." It is highly technical and mathematical but has some
> excellent graphics to illustrate the principles.
> A related site is http://www.cs.cmu.edu/~hzhang/HFSC/main.html
> The latest man pages are a little less mathematical but still pretty
> dense with the references to functions to describe the service curves.
> I've downloaded the latest man pages
> 
> (http://git.kernel.org/?p=linux/kernel/git/shemminger/iproute2.git;a=blob_plain;f=man/man7/tc-hfsc.7;hb=HEAD
> and
> 
> http://git.kernel.org/?p=linux/kernel/git/shemminger/iproute2.git;a=blob_plain;f=man/man8/tc-hfsc.8;hb=HEAD)
> to Tech/Equipment/Endian; they can be read with:
> nroff -mandoc -rLL=<width>n <page> | less
> A commonly reference resource is http://linux-ip.net/articles/hfsc.en/
> I also found http://www.sonycsl.co.jp/~kjc/software/TIPS.txt helpful.
> However, many articles attempting to explain HFSC didn't seem to really
> get it - especially the part about decoupling latency and bandwidth
> requirements.  It is all quite confusing and not well understood.  In
> fact, as I'm thinking about how to record what I have learned, I'm
> really struggling because there is no simple way to describe HFSC!
> Let's break down the terms.  It is hierarchical because bandwidth can be
> allocated and controlled on a hierarchical basis.  For example, the top
> level of the hierarchy might be our overall available bandwidth.  The
> next level of the hierarchy might be gold level customers who get 70% of
> the available bandwidth and regular customers who get 30%.  The next
> level might be individual customers or groups of customers who divide
> the 70% or 30% allocated to their parent.  The final hierarchy might be
> groups of traffic like VoIP, interactive, web, or bulk.  These end nodes
> are called leaf nodes.  There is an important distinction between leaf
> nodes and container nodes.  Bandwidth guarantees are only made at the
> leaf node level.  Containers are only used for link sharing, i.e., how
> excess bandwidth is shared when it is available.  Remember that we said
> HFSC enforces guarantees even if it means bandwidth is not shared
> evenly.  Bandwidth guarantees are always honored (if physically
> possible) regardless of the bandwidth allocated to the higher layers of
> the hierarchy.  Thus one must be careful to not overallocate bandwidth
> at the leaves.
> Moreover, the fair sharing of bandwidth only happens between peers.  In
> other words, using our example, only two peers contend for the overall
> bandwidth - Gold and Regular.  If the second level hierarchy of Gold has
> clients A, B, and C and the second level of Regular has D and E, D and E
> contend for Regular's share of the bandwidth and A, B, and C contend for
> Gold's share of the bandwidth but, for example, D never contends with B
> because they are in different parts of the tree.  Only peers contend for
> available bandwidth.
> So that explains "hierarchical."  What do we mean by fair? This refers
> to how available extra bandwidth is allocated between those groups which
> need it.  Let's say that we have 100Mbps of bandwidth divided into four
> groups of traffic - Gold (40%), Silver (30%), Bronze (20%), and Regular
> (10%).  Let's say that no Gold or Bronze users are active so 60% of our
> bandwidth is unallocated but both Silver and Regular could use as much
> bandwidth as we can give them.  How do we fairly share that 60% between
> Silver and Regular? HFSC uses a concept called virtual time to which we
> will return later.  In effect, it will divide the 60% in proportion to
> the traffic allocated to each group asking for more.  Specifically, in
> this case, three shares of bandwidth will be allocated to Silver for
> every one allocated to Regular (30:10).
> This is another area where HFSC is brilliant over other queue
> disciplines.  For example, what if we have a stream of traffic that
> doesn't require much bandwidth but, when it needs more, we need to
> prioritize it over bulk traffic? If our service guarantees are that VoIP
> gets a guaranteed 10% of the bandwidth, web traffic gets 30% and bulk
> gets 60%, when web is inactive and both VoIP and bulk need more, the
> excess would be allocated to bulk in a 6:1 ratio.  That's not good.  But
> remember we said that guaranteeing bandwidth and sharing bandwidth are
> two separate and sometimes conflicting functions in HFSC.  Thus, we can
> say that VoIP is guaranteed 10% but, when it comes to sharing available
> bandwidth, VoIP should get 70%, web gets 20%, and bulk gets 10%.
> Brilliant! This is done by means of service curves, the last part of
> Hierarchical Fair Service Curve traffic shaping.
> A service curve is a mathematical way of describing how much service a
> process is given over time.  The use of the term curve can throw us
> non-mathematicians for a "curve" until we remember that, in strict
> mathematical terms, a straight line is a curve - a curve which
> represents a linear function.  To translate all that: a service curve is
> the allocated bandwidth.  The y axis is the amount of data transferred
> (service given) and the x axis is time.  The greater the bandwidth, the
> steeper the slope of the curve (line).  Another brilliant thing about
> HFSC is that a service curve can have two lines, i.e., for a certain
> period of time one bandwidth can be allocated and after that time
> period, a different bandwidth can be allocated.  I'll refer to this as a
> "di-linear" curve.  This is how HFSC decouples bandwidth from latency
> but we'll come back to that.
> A service curve can be defined using tc with a single parameter if we
> only need one line or with three parameters if we need two lines.  There
> are two ways the parameters can be given to tc.  The mathematically
> oriented way is "m1 <value> d <value> m2 <value>" where m1 is the slope
> of the first curve (line for the non-mathematicians - translate: the
> initial bandwidth), m2 is the slope of the second curve (translate: the
> second bandwidth setting) and d is the intersection of the two curves
> (translate how long we use the first bandwidth before switching to the
> second bandwidth).
> The second, more system administrator oriented syntax is "umax <value>
> dmax <value> rate <value>".  This syntax makes it a little easier to see
> how HFSC separates guarantees for latency from guarantees for bandwidth.
> The rate parameter is the second curve.  In practical terms, this is the
> guaranteed bandwidth.  The umax parameter is the size of some unit of
> data.  It will often be the size of a data packet, e.g., 1514 bytes
> (does not need to include CRC, preamble, or inter-frame gap) but it
> could be some other unit.  For example, some have suggested that one
> could use this so that the text portion of web pages are delivered with
> low latency and the rest of the non-text, typically larger data
> transmissions, will follow at a slower pace.  If the typical text page
> size is 10KB, we might set umax to 10KB. Of course, this assumes that
> text is always sent first. The dmax parameter is the maximum delay that
> umax can tolerate.  So we might say that the first 1514 byte packet must
> be delayed no more than 20ms, or the first 10KB of web page transmission
> should be delayed no more than 100ms.  This is how bandwidth and latency
> guarantees are separated.
> Let's illustrate this a little further.  Let's say we have an FTP
> transfer which is running as fast as its guaranteed bandwidth.  We also
> have a VoIP traffic stream also running within its guaranteed bandwidth.
> The classic problem is that my VoIP packet which must be delivered on
> time is sitting behind my much larger FTP packet which is allowed to be
> sent because it is within the guaranteed bandwidth for FTP.  How do I
> jump the VoIP packet ahead of the FTP packet?
> HFSC will see that both packets are eligible to be sent because both are
> within the bandwidth limits set for their kind of traffic.  It then sees
> that the FTP traffic only has a bandwidth guarantee, i.e., it can meet
> its obligations to the FTP traffic as long as the packet is delivered
> within the time frame necessary to meet the bandwidth requirements
> regardless of how much the packet is delayed (as long as the delay is
> not so long as to violate the bandwidth requirements).  It then looks at
> the equally eligible VoIP packet and sees that, not only does it have an
> obligation for bandwidth but it also must not delay this packet for more
> than, say, 20ms.  In effect, it looks at the deadline for delivering the
> FTP packet and compares it to the deadline for delivering the VoIP
> packet and if the deadline for the VoIP packet is sooner than the
> deadline for the FTP packet, it will service the VoIP packet first.
> But how, exactly, does it work? It is done by the interplay of service
> curves and timers.  In fact, we will come to see that eligible and
> deadline are actually technical terms to describe some of the timers but
> first, let's step back and explain a little more about service curves.
> Service curves
> There are actually three service curves used by HFSC.  They are:
> 1. The real-time service curve (rt)
> 2. The link-sharing service curve (ls)
> 3. The upper limit service curve (ul)
> The abbreviations are used to specify which service curve we are
> describing in the tc syntax, e.g.,
> tc add class dev <device> parent parentID classid <ID> hfsc [ [ rt SC ]
> [ ls SC ] | [ sc SC ] ] [ ul SC ]
> SC is the description of the curve as described above using m1 d m2 or
> umax dmax rate, e.g.,
> tc add class dev <device> parent parentID classid <ID> hfsc rt 1514b
> 20ms 200kbits
> If we are not using two curves, we only need the last parameter, e.g.,
> tc add class dev <device> parent parentID classid <ID> hfsc ls 500kbits
> The sc parameter is used when rt and ls are the same, i.e., one can
> specify them both in one definition rather than needing to write two.
> It is not usual to specify all three curves in the same class.  The rt
> parameter is only used on leaves.  The ul parameter is usually not used
> leaves.
> Real-time service curve
> Real-time service curves can only be applied to leaf nodes (remember
> this is Hierarchical Fair Service Curve).  Using our previous example,
> rt curve would not be applied to "Gold Clients" but to "Web traffic".
> The rt curves can have either one curve (line) or two.  In fact, it is
> usually only rt curves which have two curves; ls and ul curves generally
> do not.  If the first curve is steeper than the second curve
> (translated: if the initial bandwidth guarantee is greater than the
> sustained bandwidth guarantee), the curve is called concave in HFSC
> terminology.  If the opposite is true, it is called convex.  This is
> illustrated by the below graphic copied from
> http://www.cs.cmu.edu/~hzhang/HFSC/main.html
> One must be careful when specifying rt curves because they will be
> honored above all other curves (remember we said that, when it is
> impossible to satisfy the requirements for both guaranteed bandwidth and
> fair sharing, guaranteed bandwidth wins).  This will be more
> understandable when we discuss the upper limit (ul) curve.  To jump
> ahead a little bit, the ul is typically though not exclusively used to
> describe the maximum bandwidth available, e.g., a T1 circuit or a cable
> connection.  We said that rt is honored above all other curves.  If the
> ul curve says the maximum bandwidth available is 10 Mbps and the sum of
> all our rt curves is 20 Mbps, the system will try to guarantee 20 Mbps
> which, of course, means it will fail to meet its guarantees under
> maximum load.
> Jumping ahead once more, rt curves override ls curves, too.  The ls
> curves are used to share extra bandwidth fairly.  So, if the ls curve
> dictates that class A should have 2 Mbps of our 10 Mbps link and class B
> should have 8 Mbps but the rt curve says that class A is guaranteed 3
> Mbps, class A will get 3 Mbps and class B only 7 Mbps.  The rt curve
> will always be honored whenever it is physically possible.  The bottom
> line is that the rt service curve always "wins."
> An important point to remember is that the rt curve determines the
> bandwidth and latency guarantees, is the only curve which determines
> bandwidth and latency guarantees, and has nothing to do with how
> bandwidth is fairly shared (other than to override that sharing if
> necessary!).  To put it another way, the function of the rt service
> curve is independent of the ul and ls service curves.  They handle two
> completely separate characteristics of HFSC.
> Upper limit service curve
> As mentioned above, the ul curve is often used to describe the maximum
> bandwidth available.  More specifically, it sets an upper boundary to
> the bandwidth which can be allocated by the ls curve.  As we will see,
> the ls curve is used to determine how the excess available bandwidth is
> fairly shared.  The ul service curve sets limits on that sharing.
> Let's get some vocabulary defined.  Link sharing is the term used by
> HFSC to describe how the bandwidth not actively used by the rt service
> curve is fairly allocated among the rest of the network sessions which
> are requesting bandwidth.  Let's connect the dots again as a way of
> review.  Remember, the rt curve defines the guaranteed amounts of
> bandwidth.  Let's go back to our 10 Mbps circuit and say we have VoIP
> with an rt service curve rate of 1 Mbps, interactive traffic with an rt
> service curve rate of 5 Mbps, web traffic with an rt service curve rate
> of 2 Mbps, and bulk traffic with an rt service curve rate of 1 Mbps.
> Note that the sum of the rt curves does not need to equal the total
> bandwidth.  Now let's say it's the middle of the night so the phones are
> not in use and no one is generating interactive traffic however web
> traffic to our internal web servers is going at full speed as are our
> overnight off site backups and FTP transfers.  Web is guaranteed 2 Mbps,
> bulk is guaranteed 1 Mbps and link sharing will figure out how to divide
> up the remaining 7 Mbps.  However, the ul curve could override the way
> link sharing divides that 7 Mbps.
> Let's illustrate how and learn more about ul at the same time.  The ul
> service curve is normally specified at the top of the hierarchy and is
> set to the maximum bandwidth available.  Think way back to when we said
> that link sharing only happened between peers.  Classes lower in the
> hierarchy can only contend for the bandwidth allocated to their parent
> and not for bandwidth allocated to classes at the same level but under a
> different parent.  Once again, I will copy a graphic from
> http://www.cs.cmu.edu/~hzhang/HFSC/main.html to illustrate this:
> Since children can only contend for the bandwidth allocated to their
> parents, the ul limit on bandwidth flows down through the entire tree
> under it.  If the parent with the ul limitation cannot receive the
> bandwidth, its children cannot contend for it.  Thus, by placing the ul
> at the top of the hierarchy and setting it to the maximum bandwidth
> available, it flows down through the entire tree and we do not need to
> define it in every descendant class.  That is, unless we want to
> override it further down the tree.
> Let's go back to our illustration.  If we had set ul rate 10240kbits (10
> Mbps), the web traffic and the bulk traffic will be sharing the 7 Mbps
> available bandwidth in whatever ratio was specified in their ls service
> curves.  If no ls curves were specified, they will divide the bandwidth
> according to their rt curves - in this case a 2:1 split.  For now, let's
> assume that the ls curve is the same as the rt curve, that is 2 Mbps for
> web and 1 Mbps for bulk.  Remember that the ul curve sets a limit on the
> ls curve.  What if, for some reason, we wanted to make sure that bulk
> traffic never exceeds 3 Mbps even if there is more available?  We would
> create a  second ul service curve for the bulk traffic on the bulk
> traffic class with ul rate 3072bkits.
> Link sharing will try to allocate an extra 2.33 Mbps to bulk traffic
> (7 / 3).  When this link sharing bandwidth is added to the guaranteed
> bandwidth of 1 Mbps, we come out to 3.33 Mbps.  Since this is exceeds
> the ul service curve set specifically for bulk traffic, link sharing
> will not be able to service bulk traffic at 3.33 Mbps.  It will only be
> able to provide service at 3 Mbps.  The rest will go to the web service.
> So, to summarize, the ul service curve is not used to guarantee
> bandwidth or latency.  That is the job of the rt service curve.
> Allocated bandwidth can exceed the ul service curve if the sum of the rt
> service curves is greater than the ul service curve and the circuit can
> support the higher rt bandwidth allocation.  This is another way of
> saying the rt guaranteed bandwidth always takes precedence.  The ul
> service curve is used to determine the link sharing bandwidth, i.e., the
> bandwidth allocated to classes of traffic from the unused portion of the
> available bandwidth.  It is specifically used to limit how much
> bandwidth can be allocated through link sharing, is typically set to the
> maximum bandwidth of the circuit, and is normally set at the top of th
> hierarchy because its affect is to flow down to all classes underneath
> it.
> Link-sharing service curve
> The ls service curve is not used to guarantee bandwidth or latency.  Its
> sole purpose is to determine the proportions in which unused bandwidth
> is allocated to classes which are requesting more than their guaranteed
> bandwidth, that is link sharing.  Although it is good practice to use
> service curves with numbers that are realistic for the available
> bandwidth, technically, only the ratio is important.
> Let's illustrate by returning to our previous example.  The ul is set to
> a rate of 10 Mbps.  We would expect the web ls service curve to use a
> rate of 2 Mbps and the bulk ls service curve to use a rate of 1 Mbps.
> However, we could say the web ls sc is 200 Mbps and the bulk ls sc is
> 100 Mbps and it would not break and not be illegal - just confusing.
> The ratios are the same (2:1) and it is only the ratios which are
> important.
> The discussion about ul service curves has "stolen the thunder" from the
> ls service curve discussion, i.e., there is not much left to say.  The
> ls service curves determine how link sharing works, i.e., how the
> bandwidth with is not being used to satisfy the guarantees of the rt
> service curves is fairly allocated among all the other network traffic
> flows who would like more bandwidth than they are guaranteed.
> The Linux and BSD implementation of HFSC go beyond the original
> specification by allowing us to specify the ls service curve separately
> from the rt service curve.  This gives us some powerful flexibility as
> we are about to illustrate.
> Let's extend our previous example.  Remember we have a 10 Mbps circuit
> and thus have set the ul service curve rate at the top of the hierarchy
> to 10 Mbps.  We have four classes of traffic, VoIP, interactive, web,
> and bulk.  The rt rate for VoIP is 1 Mbps, for interactive 5 Mbps, for
> web 2 Mbps, and for bulk 1 Mbps.  That accurately reflects our desire
> for guaranteed bandwidth but those proportions may not accurately
> reflect how we want any available excess bandwidth distributed.
> For our purposes, link sharing should have the following
> characteristics.  Bulk should be able to use all the bandwidth if it is
> available and uncontended.  However, if the VoIP traffic needs extra
> bandwidth and there is available bandwidth, it should be granted that
> extra bandwidth with priority since we do not want to starve our voice
> traffic.  Furthermore, we want visitors to our web site to have a
> positive experience and not one with substantial delays so, if there is
> contention between bulk and web traffic, we want web traffic to take
> more than a 2:1 ration of available bandwidth.  Thus, we might setup our
> tc classes as follows:
> VoIP:
> tc add class dev eth0 parent 1:1 classid 1:10 hfsc rt rate1024kbits ls
> rate 7168kbits
> We first thought this should be rt umax 222b dmax 5ms rate 1024kbits
> because the maximum sized VoIP packet is typically 222 bytes (ulaw/alaw
> at 64Kbps = 8KB/s * 0.020s (20 ms per packet) = 160 Bytes + 8 (UDP
> header) + 40 (IP header) + 14 (Ethernet header) = 222 Bytes) and we want
> it delayed in the router for no more than 5ms.  However, to guarantee 1
> Mbps bandwidth, a 222 byte packet needs to be sent within roughly 1.7ms
> (222 * 8 = 1776 bits / (1024 * 1024)bits/s = 0.0017s).  Thus, our rate
> is sufficient and we do not need to jump the delivery of VoIP packets by
> specifying a larger initial bandwidth.
> Interactive
> tc add class dev eth0 parent 1:1 classid 1:11 hfsc sc rate5120kbits
> We use sc since we want rt and ls to be the same
> Web:
> tc add class dev eth0 parent 1:1 classid 1:12 hfsc rt rate 2048kbits ls
> rate 3072kbits
> Bulk:
> tc add class dev eth0 parent 1:1 classid 1:12 hfsc sc rate 1024kbits
> Note that the sum of our ls service curves exceeds the ul service curve.
> This is not a problem.  Remember it is only the ls service curve ratios
> which are meaningful.  So what have we done? Even though our guarantees
> can be met with a proportion of 1:5:2:1, we have specified that, if
> there is extra bandwidth available and, if there is contention for it,
> distribute it in the ratio of 7:5:3:1.  In other words, if interactive
> and web are idle and VoIP and bulk can use more bandwidth than their
> guarantees (backlogged in HFSC terminology), the bandwidth will be
> allocated between VoIP and bulk at a 7:1 ration and not a 1:1 ratio.
> Likewise, if VoIP and interactive are idle and web and bulk are
> backlogged, the extra bandwidth will be allocated at a 3:1 ratio rather
> than a 2:1 ratio.  Can we see the value of having separate rt and ls
> service curves?
> Timers
> However, service curves are not the whole story.  In fact, it is not
> really the service curves which determine which packet is sent when.
> The service curves are used to set the timers and it is the timers which
> determine which packet is sent when.
> While service curves are quite understandable to system administrator
> types once we translate the vocabulary (curves = bandwidth, umax and
> dmax = latency (technically bandwidth I suppose but, latency in
> practicality)), timers are they mysterious art of programmers and
> mathematicians - an impenetrable black box.  Let's see if we can pry
> open that black box and make it at least a little understandable to us
> sysadmin types.
> HFSC uses four separate timers to work its wonders:
> 1. Fit time
> 2. Virtual time
> 3. Eligible time
> 4. Deadline time
> Virtual time
> Let's start with virtual time.  Virtual time is used by link sharing to
> determine which queue should be serviced to keep things fair, that is to
> keep the bandwidth in proportion to the ls service curve ratios.
> Virtual time appears to be a very complicated topic addressing
> mind-bending issues like how to preserve fairness among several
> backlogged queues when a new queue becomes backlogged as well and to
> preserve this fairness without starving one of the queues while the
> others catch up. Thus my explanation will be a dramatic
> oversimplification but hopefully enough to give fellow sysadmins a
> toehold to ascend this seemingly sheer rock face.
> Virtual time is a measure of how much time has been spent servicing the
> queue and how much it will take to service the next packet.  Here is a
> very good ascii art representation copied from
> http://www.sonycsl.co.jp/~kjc/software/TIPS.txt :
>                     bytes
>                          |                   /
>                          |                  /service curve
>                          |                 /
>            next   -->+   +----------------+
>            packet    |   |               /|
>            length    |   |              / |
>                      |   |             /  |
>            total --> +   +------------+   |
>            bytes         |           /|   |
>            already       |          / |   |
>            sent          |         /  |   |
>                                   /   |   |
>                                       |   |
>                                       |   |
>                               --------+---+--------------> time
>                                           vt for next packet
>                                       vt for previous packet
>
> Not surprisingly, this makes a great deal of sense when we digest it.
> Remember, the service curve we are using is the ls service curve, i.e.,
> the one for link sharing.  The more the bandwidth allocated to the ls
> service curve, the steeper the slope of the line.  The steeper the slope
> of the line, the shorter the time to transmit the packet = the more
> bandwidth, the shorter the time to transmit the packet.  Thus, the
> change in virtual time for the same sized packet is less for a faster
> queue than for a slower queue.  We'll see why that is important in a
> second.
> Remember that link sharing is used only among peers.  Only peers can
> contend for available extra bandwidth.  Fairness is achieved in HFSC by
> trying to keep the virtual time of all peers equal.  When a queue
> becomes backlogged, i.e., needing more than its guaranteed bandwidth, it
> starts accumulating virtual time.  The more it has been serviced while
> backlogged, the more virtual time it accumulates.
> When HFSC looks at the various backlogged queues, how does it determine
> which one to service? Look again at the above diagram.  Each queue will
> have its current virtual time and the virtual time that it will have
> after it sends its next packet.  HFSC will choose the next packet which
> will have the lowest virtual time.  Let's make this more understandable
> with some real illustrations.  Let's say we have two backlogged queues
> with identical ls service curves and each has a full sized Ethernet
> packet pending.  Queue A has accumulated virtual time of 1000ms and
> Queue B has accumulated virtual time of 999ms.  Let's say that sending
> the full sized Ethernet packet will take 2ms.  The virtual time after
> Queue A sends its packet would be 1002 whereas Queue B would be 1001ms
> so HFSC sends Queue B's packet.  Now Queue B has VT (virtual time) of
> 1001ms and the next packet would bring it to 1003ms.  Queue A has VT of
> 1000ms and sending the next packet would bring it to 1002ms.  HFSC
> chooses the packet which will result in the lowest VT thus it sends the
> packet in Queue A.  See how it tries to keep the virtual times equal and
> thus produces fairness.
> Now let's alter the scenario.  Let's keep the virtual time the same,
> 1000ms for Queue A and 999ms for Queue B but Queue A is handling small
> packets which only take 0.5ms to send.  Queue A has one of these packets
> ready to send while Queue B has one of its full sized packets to send.
> VT for Queue A after sending its packet would be 1000.5ms and for Queue
> B would be 1001ms so, even though Queue A has already received more
> service, it is services again because its final virtual time would be
> smaller.
> More importantly, let's go back to the idea that both Queue A and Queue
> B use full sized packets but this time the ls service curves are not
> equal.  Let's say the ls service curve rate for Queue A is 5120kbits and
> for Queue B is 1024kbits.  Thus, a packet that would take Queue B 2ms to
> transmit would take Queue A 0.4ms to transmit.  Both queues are
> continually backlogged so they always have packets to send.  HFSC takes
> a look and calculates the next VT for Queue A as 1000.4 and Queue B as
> 1001 so it sends Queue A.  It calculates again and A is 1000.8 and B
> 1001 so it sends A again.  The next calculation of VT puts A at 1001.2
> and B at 1001 so it sends B.  The next calculation puts A at 1001.2 and
> B at 1003 so A is sent.  Then 1001.6 versus 1003, then 1002 vs. 1003,
> then 1002.4 vs. 1003, then 1002.8 vs. 1003, then 1003.2 vs. 1003.  Can
> you see how the virtual time calculation is allocating service to Queue
> A at a 5:1 ratio with Queue B - just the fairness we requested via the
> ls service curves.
> So, in summary, virtual time used to produce fairness when distributing
> available excess bandwidth to backlogged queues in the ratio of the ls
> service curves.  It does this by trying to keep virtual times for all
> peers in the hierarchy equal and it does this by always choosing the
> packet to send which will result in the smallest virtual time.
> Fit time
> Fit time is pretty simple to understand.  Recall that we said the ls
> service curve was bounded by the ul service curve, i.e., even if a queue
> should get say 10 Mbps according to link sharing, if the ul (Upper
> Limit) service curve says we can use 8 Mpbs maximum, we are only going
> to get 8 Mbps.  Fit time takes into account the ul service curve.
> In effect, fit time looks at what the clock time would be to send the
> packet based upon the ul service curve rate, i.e., what the time would
> be to send the pending packet at the maximum transmission rate.  If that
> time is later than the current clock time, the packet will not be sent
> not matter what virtual time says.  If the current clock time is later
> than fit time, i.e., we would not have exceeded out bandwidth
> limitation, then the decision is made based upon virtual time.
> As a reminder, this is all for traffic over and above the guaranteed
> rate, i.e., the rt service curve rate.  Packets are always sent to
> preserve the rt service curve rate as long as it is physically possible
> regardless of fit time or virtual time.  This is the same as saying that
> the rt service curve always wins or, to phrase it yet another way, to
> meet the HFSC design criterion that, if there is a conflict between link
> sharing and guaranteed bandwidth, choose guaranteed bandwidth.
> Eligible time
> The rt service curve uses two timers: eligible time and deadline time.
> Recall, we used referred to eligible and deadline time toward the
> beginning of this discussion when observed how HFSC provides decoupled
> guarantees for both bandwidth and latency.  Like fit time, eligible time
> is relative to clock time.  In other words, HFSC calculates what the
> clock time would be to send the queued packet at the guaranteed rate,
> i.e., the rt service curve rate.  If that time is later than the current
> clock time, that packet's time has not come yet and it cannot be sent
> based upon its real time guarantee.  I do believe it can be sent based
> upon virtual time assuming that fit time allows it.  After all, that is
> what link sharing is about - being able to exceed the guaranteed
> bandwidth if there is extra bandwidth available.  On the other hand, if
> current clock time is later than eligible time, then this packet had
> better get moving because it is potentially running behind schedule.
> So, eligible time is just as then name implies; it is the time the
> packet becomes eligible for sending based upon the real-time service
> curve, i.e., the guaranteed bandwidth/latency.
> An important point to understand the difference between eligible time
> and deadline time is that eligible time is measured from the beginning
> or head of the packet, i.e., is HFSC ready to begin sending this packet.
> But what happens when more than one queue has packets whose eligible
> time has come? That's where deadline time comes into play.
> Deadline time
> Deadline time is closely related to eligible time and is likewise
> measured against clock time.  However, deadline time is measured against
> the end or tail of the packet, i.e., by when must we have finished
> sending this packet at the specified bandwidth in order to meet our
> packet delivery guarantees for bandwidth and latency.  Once again,
> http://www.sonycsl.co.jp/~kjc/software/TIPS.txt has an excellent ASCII
> graphic for illustrating the relationship between eligible time measured
> at the beginning of the packet and deadline time measured from the end:
>                     bytes
>                          |                   /
>                          |                  /service curve
>                          |                 /
>            next   -->+   +----------------+
>            packet    |   |               /|
>            length    |   |              / |
>                      |   |             /  |
>       cumulative --> +   +------------+   |
>            bytes         |           /|   |
>            already       |          / |   |
>            sent          |         /  |   |
>                                   /   |   |
>                                       |   |
>                                       |   |
>                               --------+---+--------------> time
>                                 eligible  deadline
>                                 time
>
> This time, the slope is the rt service curve.  The way in which HFSC
> chooses from among several different queues all with packets whose
> eligible time is greater than current clock time is almost identical to
> the way it chooses among backlogged queues with virtual time, viz., it
> chooses the packet with the lowest deadline time.  Remember that the
> steeper the curve, the greater the bandwidth and the shorter the
> distance between eligible time and deadline time for the same sized
> packet.
> Let's walk through a real example.  We have Queue A with VoIP traffic -
> small, 222 byte packets and an rt service curve bandwidth such that it
> takes 0.2ms to send its packets; that equates to roughly 8.88 Mbps ((222
> * 8)bits/0.0002s).  Let's also assume that we have so much VoIP traffic
> that the queue is filled so we always have a VoIP packet asking to be
> dequeued.  Queue B is sending FTP with large packets and an rt service
> curve rate such that each packet takes 2ms to send; this equates to
> 6.056 Mbps ((1514 * 8)bits/0.002s).  Queue B is also completely full.
> Let's assume that the maximum bandwidth available is the sum of the
> guaranteed bandwidths, viz., 14.936 Mbps.  This will allow us to
> calculated the progress of clock time, i.e., how long it actually takes
> to send each packet.  Also remember that each packet has a 4 byte CRC,
> and 8 byte preamble, and a 12 byte interframe gap time at least in
> traditional Ethernet.  Thus to transmit a packet in Queue A, we really
> need to transmit 246 bytes and, to transmit one in Queue B, we need to
> transmit 1538 bytes.  Thus, the elapsed time to send a Queue A packet is
> (246 * 8)bits / 14,936,000(b/s) = 0.132ms and the time to transmit a
> Queue B packet is (1538 * 8)bits / 14,936,000(b/s) = 0.824ms.  Sorry for
> all the math but this is what is inside the black box (and a very
> simplified version!).
> Let's assume that clock time (CT - the actual time) is 1000ms (not
> realistic but it makes the explanation easier!).  The next packet queued
> in Queue A has an ET (eligible time) of 1000ms and the next packet in
> Queue B has an ET of 999ms, i.e., both are eligible to be sent.  A less
> sophisticated traffic shaping algorithm would send the FTP packet first.
> However, HFSC calculates the deadline time (DT) for the packet in Queue
> A at 1000.2 (1000 + 0.2) and the deadline time for the packet in Queue B
> at 1001ms (999 + 2) so it sends A instead since it has the smaller DT.
> 0.132ms has elapsed in real time so CT is now 1000.132.  The
> eligible/deadline times (ET/DT) for A and B respectively are
> 1000.2/1000.4 and 999/1001.  Notice that A is no longer eligible to send
> because its ET > CT so B is serviced.  0.824ms has elapsed to send B's
> packet so CT is now 1000.956.  ET/DT for A is still 1000.2/1000.4 but B
> has changed to 1001/1003.  B just misses being eligible to send but A is
> eligible so A is sent.  Elapsed time is 0.132, CT is now 1001.088, ET/DT
> for A is 1000.4/1000.6.  Both A and B are eligible at the same time
> again as both their ETs <= CT.  A's DT is less than B's DT so A is
> serviced.
> In fact, A will send 11 packets.  Let's see the result after A sends 11
> packets.  Elapsed time is 11* 0.132 = 1.452ms so clock time is 1002.54.
> A's ET/DT have incremented by 11 * 0.2 so they are 1002.6/1002.8.  B's
> ET/DT have remained at 1001/1003.  A is no longer eligible so the fact
> that its DT is less than B's DT is irrelevant.  B is serviced.
> Pulling it all together
> To this point, almost all of our discussion have involved rt service
> curves based solely upon rate and we have been using some fairly large
> circuits to illustrate.  What happens when our bandwidth really is
> constrained such as a T1 circuit or the upload bandwidth of an
> asymmetric DSL or cable connection and we need to balance time sensitive
> traffic with bulk traffic? This is where di-linear curves save the day.
> The best illustration I have found is from the SIGCOM97 paper on HFSC:
>
> The results might not be obvious at first.  The packets arriving, e.g.,
> coming from the internal network and heading toward the constricted T1
> circuit  (well, in this specific example, it is a 10 Mbps circuit) are
> shown in the second level of graphics from the top.  The resulting
> output of those packets is shown in the very bottom set of graphics.
> The illustrations on the left show a mono-linear curve, i.e., just based
> upon bandwidth.  The video and FTP packets are flooding in, are being
> lined up and scheduled for dequeueing based upon the bandwidth only.
> Thus, the initial video packet sits in queue behind the FTP packets as
> there is no need to rush to meet its bandwidth requirements.  Here is
> how the authors describe what is happening:
> "To illustrate the advantage of decoupling delay and bandwidth
> allocation with non-linear service curves, consider the example in
> Figure 2, where a video and a FTP session share a 10 Mbps link . . . .
> Let the video source sends 30 8KB frames per second, which corresponds
> to a required bandwidth of 2 Mbps. The remaining 8 Mbps is reserved by a
> continuously backlogged FTP session. For simplicity, let all packets be
> of size 8 KB. Thus, it takes roughly 6.5 ms to transmit a packet."
> "As can be seen, the deadlines of the video packets occur every 33 ms,
> while the deadlines of the FTP packets occur every 8.2 ms. This results
> in a delay of approximately 26 ms for a video packet."
> Let's work through the math to make that more understandable.  HFSC is
> committed to deliver 2 Mbps to video and each packet is 8KB long.  Thus,
> HFSC's commitment to deliver that packet is within (8000 * 8)bits /
> 2,000,000(b/s) = 32ms.  I'm not quite sure why I come up with 32 and
> they say 33 but we'll use 33.  In other words, to meet the deadline
> based solely upon the rate, the bandwidth part of the rt service curve,
> the packet needs to be finished dequeueing at 33ms.  Since it only takes
> 6.5ms to send the packet, HFSC can sit on the packet it received for 33
> - 6.5 = 26.5ms if it needs to in order to meet the guarantees for other
> traffic.  This adds unnecessary latency to the video stream.
> In the second scenario, we introduce an initial, elevated bandwidth
> guarantee for the first 10ms.  The bandwidth for the first 10ms is now
> 6.6 Mbps instead of 2 Mbps.  We do the math again and HFSC's commitment
> to video to maintain 6.6 Mbps is to finish dequeueing the packet within
> (8000 * 8)bits / 6,600,000(b/s) = 10ms.  Since it takes 6.5 ms to send
> the packet, HFSC can sit on the packet for no more than 10 - 6.5 = 3.5
> ms.  Quite a difference!
> I assume for simplicity's sake, the graphic leaves out an important
> point.  The rt service curve either fully or partially resets when the
> queue has been drained.  Fully or partially depends on how much time has
> elapsed since the last service rendered and the new service requested
> when the queue becomes active again.  Thanks for Michal Soltys on the
> netdev kernel mail list for clarifying this for me.
> Without this reset, the first part of the service curve (the m1 portion
> if you recall the earlier discussion about how service curves can be
> defined) would not have much practical value because once traffic
> activates the queue, only the first packet or first few packets would be
> guaranteed the latency of the first, accelerated part of the curve.
> Everything else would use the second part of the curve (the m2 portion -
> we'll use the terms m1 and m2 for the rest of the discussion).
> So let's re-examine the above example in more detail.  The video packet
> arrives, uses the m1 curve, is jumped ahead of the FTP packets because
> of the low latency guarantee of the m1 curve, is dequeued, and now the
> queue is empty for 33.33ms (remember the video is playing at 30 frames
> per second, well, 32.69ms when you account for transmission time on a
> 100 Mbps circuit) which allows the curve to reset.  The next video
> packet comes in and it is treated according to m1 and not m2 because we
> have reset the curve.  Thus, each video packet is jumped in front of any
> queued FTP packets.
> We can even multiplex several video streams.  As long as the queue is
> allowed to go idle long enough, each of those streams will be treated
> with very low latency and jumped in front of the FTP packets, i.e.,
> until we have so many video streams that the queue starts to backlog.
> Then they will use the m2 curve.
> This is not a bad thing; it is a good thing and allows us a new
> perspective on the m1 and m2 curves.  Hopefully, we have allocated
> enough bandwidth in our m2 curve to properly service our video or VoiP
> or whatever we are pushing through this queue.  Thus, even if we are not
> receiving the accelerated treatment, we are still experiencing
> sufficient service.  If our queue is badly backlogged and overflowing,
> then we have a different problem and need more raw bandwidth!
> In this way, we can think of the m2 curve, the second level of service
> in a concave service curve (remember a concave service curve is where we
> start out with a higher bandwidth and then change to a lower bandwidth),
> as a circuit breaker preventing overload.  In other words, we are saying
> to this prioritized traffic that we will deliver it with a lower than
> normal latency (and thus higher short term bandwidth) while we can but,
> if it becomes too much (as determined by the system administrator who
> defined the HFSC qdisc), we will drop it down to a more sustainable rate
> that will not exceed the physical capabilities of the circuit.  This
> assumes we have designed our traffic shaping so that the sum of all the
> m2 portions of all the rt service curves do not exceed the capabilities
> of the circuit.
> Another way of saying this with familiar terminology is that we can
> burst at the m1 rate as long as the queue doesn't backlog but, when it
> does, we drop to our sustainable rate.  Thus, concave rt service curves
> are very well suited to periodic traffic, i.e., traffic which sends
> packets on a recurring interval with space in between like VoIP or
> video.  It may be less effective on burstable traffic such as the
> example of using it to accelerate the delivery of text on a web site
> unless the traffic is low enough that the queue has a chance to drain
> regularly.
>
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [WARNING - VERY LONG] A sysadmin's understanding of HFSC and IFB

[John A. Sullivan III]

On Tue, 2011-12-13 at 18:10 -0500, Julien Vehent wrote:
> This is an amazing email and I will definitely sit down and read it 
> carefully.
> I've been (silently) following your discussions about HFSC because I've been 
> wanting to add a section on HFSC in the TC doc I wrote here:
> http://wiki.linuxwall.info/doku.php/en:ressources:dossiers:networking:traffic_control
> 
> The doc I've read so far left me staring at the wall with more questions 
> than answers. I'm hoping your text will finally bring a clear view of the 
> problem :)
> 
> Cheers,
> Julien
> 
<snip>
LOL - guess whose web site I have open in my browser as I walk through
experimenting with tc to build a test WAN environment in our lab:

http://wiki.linuxwall.info/doku.php/en:ressources:dossiers:networking:traffic_control

It's wonderfully well done and I've recommended it to several of my
peers.  Thanks for putting it together - John

Re: [WARNING - VERY LONG] A sysadmin's understanding of HFSC and IFB

[John A. Sullivan III]

On Tue, 2011-12-13 at 18:35 -0500, John A. Sullivan III wrote:
> On Tue, 2011-12-13 at 18:10 -0500, Julien Vehent wrote:
> > This is an amazing email and I will definitely sit down and read it 
> > carefully.
> > I've been (silently) following your discussions about HFSC because I've been 
> > wanting to add a section on HFSC in the TC doc I wrote here:
> > http://wiki.linuxwall.info/doku.php/en:ressources:dossiers:networking:traffic_control
> > 
> > The doc I've read so far left me staring at the wall with more questions 
> > than answers. I'm hoping your text will finally bring a clear view of the 
> > problem :)
> > 
> > Cheers,
> > Julien
> > 
> <snip>
> LOL - guess whose web site I have open in my browser as I walk through
> experimenting with tc to build a test WAN environment in our lab:
> 
> http://wiki.linuxwall.info/doku.php/en:ressources:dossiers:networking:traffic_control
> 
> It's wonderfully well done and I've recommended it to several of my
> peers.  Thanks for putting it together - John
<snip>
I should mention this is our internal, copyrighted documentation but I
do have the authority to share it freely and, as avid consumers and
contributors to the OSS world, we will want to make it as available as
possible assuming it is accurate - John

Re: [WARNING - VERY LONG] A sysadmin's understanding of HFSC and IFB

[John A. Sullivan III]

On Tue, 2011-12-13 at 18:01 -0500, John A. Sullivan III wrote:
> On Fri, 2011-12-09 at 08:59 +0100, Eric Dumazet wrote:
> > Le vendredi 09 décembre 2011 à 02:17 -0500, John A. Sullivan III a
> > écrit :
> > > Hello, all.  I've been trying to summarize my last week's worth of
> > > research into HFSC and IFB.  Being neither a developer nor a
> > > mathematician, I found most of the existing documentation daunting and
> > > am truly grateful for the help I received on this list to understand the
> > > technologies.
> > > 
> > > I do not currently have a blog to post this research and so was thinking
> > > of posting it to this list so that it could be archived and searchable
> > > for other poor sysadmin types like me to save them the days of
> > > struggling to get their practical heads around the concepts.
> > > 
> > > However, since this is probably a 15 page or so document, I realized
> > > this could be quite rude to those on dial up or metered connections.
> > > Would it be appropriate to post my summary here? Thanks - John
> > > 
> > 
> > Please post here, thats definitely a good idea.
> > 
> > I am pretty sure your contribution could serve to add a page to 
> > 
> > http://www.linuxfoundation.org/collaborate/workgroups/networking/group
> > 
> > I believe we lack documentation. A lot.
> <snip>
> OK - it's almost ready.  The only problem I know if is that, when I do
> the math based upon my explanation, I sometimes violate an rt curve when
> I should not.  I posed that in an email to the list entitled "An error
> in my HFSC sysadmin documentation".  If anyone can figure out where my
> error is, I will gladly change the documentation.  Here's what I have.
> The graphics except the ASCII art are obviously missing.  All
> corrections and suggestions very gratefully accepted - John
> 
<snip>
I realize I was using an incorrect definition of backlogged (needing
more bandwidth than the guaranteed bandwidth) and have corrected (having
a packet in queue) - John

Re: [WARNING - VERY LONG] A sysadmin's understanding of HFSC and IFB

[John A. Sullivan III]

On Tue, 2011-12-13 at 18:01 -0500, John A. Sullivan III wrote:
> On Fri, 2011-12-09 at 08:59 +0100, Eric Dumazet wrote:
> > Le vendredi 09 décembre 2011 à 02:17 -0500, John A. Sullivan III a
> > écrit :
> > > Hello, all.  I've been trying to summarize my last week's worth of
> > > research into HFSC and IFB.  Being neither a developer nor a
> > > mathematician, I found most of the existing documentation daunting and
> > > am truly grateful for the help I received on this list to understand the
> > > technologies.
> > > 
> > > I do not currently have a blog to post this research and so was thinking
> > > of posting it to this list so that it could be archived and searchable
> > > for other poor sysadmin types like me to save them the days of
> > > struggling to get their practical heads around the concepts.
> > > 
> > > However, since this is probably a 15 page or so document, I realized
> > > this could be quite rude to those on dial up or metered connections.
> > > Would it be appropriate to post my summary here? Thanks - John
> > > 
> > 
> > Please post here, thats definitely a good idea.
> > 
> > I am pretty sure your contribution could serve to add a page to 
> > 
> > http://www.linuxfoundation.org/collaborate/workgroups/networking/group
> > 
> > I believe we lack documentation. A lot.
> <snip>
> OK - it's almost ready.  The only problem I know if is that, when I do
> the math based upon my explanation, I sometimes violate an rt curve when
> I should not.  I posed that in an email to the list entitled "An error
> in my HFSC sysadmin documentation".  If anyone can figure out where my
> error is, I will gladly change the documentation.  Here's what I have.
> The graphics except the ASCII art are obviously missing.  All
> corrections and suggestions very gratefully accepted - John
> 
<snip>
Thanks to Michal's help, I took the time to understand how service
curves are updated and the practical implications for system
administration.  I thus added two sections to the very end of the
document - one on service curve update details and the other on general
guidelines.  I'll paste in those additions here. They bring the entire
document to somewhere around 22 pages.  Unfortunately, the non-ascii
graphics will be lost in the email.

PLEASE PROTECT OTHERS FROM ME :) This document is based upon my very new
and raw knowledge.  I have not yet run this through our lab and do not
have practical experience.  I would hate for this email to become an
authoritative document simply by its presence.  If there is something
wrong, please point it out.  Thanks.  Here goes:


Service curve updates in detail
This section is probably beyond what most system administrators need to
know to configure their systems but is included for completeness or for
those who may need more information to troubleshoot a configuration
which may not be behaving as expected.  If you do not need this much
detail, skip to the summary guidelines section.
As mentioned above, it is the complicated subject of updating service
curves which transforms HFSC's ability to guarantee latency separately
from bandwidth from an interesting theory with little practical
application into a fabulously powerful and practical traffic shaping
tool.  So how do these updates work?
Service curves are usually represented as a two dimensional graph - a
line with either one or two slopes with an x and y axis.  The x axis is
elapsed time and the y axis is service or work rendered.  Translated out
of mathematical formula terms and into system administrator terms, the
work or service rendered is the number of bits sent out of the queue.
That's why the slope of the line equals the bandwidth.  If we choose a
dot on the line (curve) where the y coordinate is 100kbits dequeued and
the x coordinate is 100ms elapsed, then the slope is 100kbits/0.1s = 1
Mbps.
When a queue first becomes backlogged, i.e., when it first has packets
to send, it starts to track the service curve, i.e., how many bits have
been delivered over how much time.  While it is backlogged, i.e., has
packets to send, the queue is active.  Once the packets are all dequeued
and there are no more to send, the queue becomes passive.  Now more
packets arrive and the queue becomes active, backlogged.  At this point,
the service curve needs to be updated.  We'll walk through this process
in several stages of increasing complexity.
The bottom line is that HFSC will dequeue the packets at the lesser of
the work which would have been rendered if we had been continually using
the previous service curve (the curve we were using when the queue was
last backlogged) or the work that would be rendered if we started the
queue over again.  What in the world does that mean?! Once we understand
it, it is actually a very practical way of making sure we can always
meet our guarantees and not overrun our circuit as long as the sum of
the rt m2 curves does not exceed the total bandwidth, i.e., as long as
we sys admins have done our job properly.  Let's take it apart piece by
piece to understand it.
Let's start with a very simple, monolinear rt service curve (i.e., the
m1 slope = the m2 slope) with no link sharing (no extra bandwidth
allocated).  Let's say the guaranteed bandwidth is 100 kbps.  Let's say
the queue initially goes active for one second so we have transmitted
100 kbits:
        |
200kbits|
        |
        |
100kbits|  x/
        |  /
        | /
  0kbits|/_________
        0s 1s 2s
Now let's say the queue goes passive, i.e., nothing to transmit, for one
second taking us to a total elapsed time of 2 seconds and the goes
active again.  HFSC will extrapolate what the total number of bits
dequeued (in HFSC terms, work performed) would have been if there had
been no passive period.  It then compares this to the total number of
bits transmitted so far (work already performed) plus how many new bits
we would transmit if we started the rt curve over again (this will make
more sense when we demonstrate this with dilinear curves).  It chooses
whichever would result is the least amount of work performed, i.e., the
fewest bits dequeued.  I'll represent this in the graph below by
extrapolating the first curve, sliding the amount of data already
transmitted (the x) over to the new elapsed time (the time the queue
became backlogged again), and then starting the original line from that
point:
300kbits|        z/
        |        /
        |       /
200kbits|      / z/ 
        |     /  /
        |    /  /
100kbits|  x/.x/
        |  /
        | /
  0kbits|/_________
        0s 1  2  3
Using the rt curve starting over again results in less work than if we
had been continually transmitting using the previous service curve (z)
so that is the rate at which we will dequeue.  In the case of monolinear
curves, that will always be the case.  It may not be the case in
dilinear curves.  Look at this illustration taken once more from
http://www.sonycsl.co.jp/~kjc/software/TIPS.txt :
                                                     ________
                                     ________--------
                                    /                  ______
                                   /   ________--------
                       ________---+----        
                      /          /             
                     /          /              
    total    ->     /          + new coordinate                
                   /                           
                  /                            
           service curve       |
                 of            +
          previous period   current
                             time

                        Update Operation

                                                       ______
                                       ________--------
                                  +----        
                                 /             
                                /              
    total    ->                + new coordinate                
                                               
                                               
                               |
                               +
                             current
                             time

                        New Service Curve

That can be a bit confusing. Let's go back and take it one step at a
time.  Unfortunately for those viewing this in text only, the next
several illustrations are difficult to render in ASCII art so we will
use graphics.
Let's consider the same monolinear rt service curve but this time there
will be some additional bandwidth added due to link sharing.
The solid black line is the first backlog period m2 curve, i.e., the
guaranteed bandwidth (100 kbits/s).  It is backlogged for 1s.  However,
more data is transmitted than 100 kbits because link sharing has
allocated another 50 kbps so the total data transmitted is 150 kbps.
This is represented by the green line.  The link goes passive for 1s and
then goes active again for another 1s.  The dashed black line shows the
data trajectory of the previous service curve, i.e., it shows how much
work would have been done (how many bits would have been dequeued) if it
had remained backlogged.  That is one point of comparison. The second
point of comparison is to take the total actual work done (the total
bits transmitted so far) and use that as the y starting point for a new
curve beginning with x at the current time.  This is the blue line.  The
only difference from the first illustration is that the second point
started  at a higher point on the y axis, i.e., with more bits already
dequeued, than the last time because of the link sharing bandwidth.  The
end result is the same - the new curve is chosen as the dequeuing rate.
What happens if link sharing gave us a lot of extra bandwidth, say 200
kbs?
In this case, so much extra data was transmitted that the amount of work
done by starting the curve over again exceeds the amount of work that
would have been done if the previous service curve had remained
backlogged so HFSC will choose to dequeue at the rate of the previous
service curve.  However, once again, the end result is the same because
the slope of the curves are the same, i.e., the bandwidth.




Now let's make the leap to see what happens with dilinear service
curves, i.e., where we are specifying latency separately from bandwidth.
In this case, lets say that m1 (the latency determining, temporary
bandwidth) is 200 kbps for a period of 1s and m2 (the guaranteed,
sustained bandwidth) is still 100 kbps and we have no additional
bandwidth from link sharing.  Let's say the first backlogged period
lasts two seconds, then there are two seconds of idle time followed by
one second of backlog.  HFSC will compare these two curves:

Notice the change in rate at 1s.  Once again, the black line is the
first service curve - the solid part being the actual transmission and
the dotted portion being the extrapolation as if it was continually
backlogged.  The blue line is the second service curve.  Notice that it
starts at the faster m1 rate.  Since the total work done, i.e., bits
dequeued is less when using the second curve, that is the one HFSC uses
to dequeue.  The effect is that the new packets are sent at the
accelerated rate and receive the full benefit of HFSC's ability to
separately guarantee latency and bandwidth.
Now, let's change the scenario.  Let's say the idle time between
backlogs is only 0.5s instead of 2s.  The curve comparison looks like
this:

Notice how the two service curves cross.  For the first half a second,
the number of bits which would be dequeued using the fully reset service
curve would be less than if the previous service curve had been
continually backlogged but, for the next half a second, the number of
bits which would be dequeued using the previous service curve is less.
In this case, HFSC will dequeue bits at the faster m1 rate for the first
half a second and then slow down to the m2 rate of the previous service
curve for the next half a second.  The service curve is "partially
reset" and the packets receive a partial "acceleration."
Let's consider one last scenario.  It is the same as the previous
scenario except that link sharing has added 50 kbps to the first two
seconds of dequeuing.  Because more work has been done, i.e., more bits
have been dequeued, the second curve will start its trajectory higher in
the graph because it always starts with how much work has already been
done, i.e., how many bits have already been dequeued.  Thus, the graph
looks like this:

Now note that, for the entire second period of backlog, the
extrapolation of the previous service curve would produce less work,
fewer bits, than starting a fresh curve.  In this case, the service
curve is not "reset" at all, the m2 rate of the previous service curve
is used for the entire dequeuing process and the packets receive no
acceleration however they will all be delivered on time because our m2
rate is guaranteed.
Piecing it all together and bringing the theory back to practical
application, we see that the total number of bits dequeued can never be
more than if the first service curve had remained permanently
backlogged.  This is how we can be sure we will never overrun the
circuit bandwidth assuming we have done our job of ensuring the sum of
the bandwidth guarantees do not exceed the circuit capacity.
However, in practicality, we can cheat a little bit.  In most cases, we
can simply be sure that the sum of the rt m2 service curves do not
exceed the circuit bandwidth.  If we need to set higher m1 curves to
guarantee latency, the sum of the rt m1 service curves could exceed
circuit capacity.  However, any idle time would quickly remedy the
situation (unless our m1 rates are excessively over capacity).
The only situations in which we could not practically cheat are the
extreme scenarios when, under no circumstances whatsoever can we
possibly not meet our guarantees (perhaps life critical systems) or
where the circuits are incredibly saturated and all queues are
constantly backlogged (in which case we probably have a bigger, non-HFSC
problem!).
Summary guidelines
Recall that HFSC classes call for defining any of ul, ls, sc, or rt
service curves.  We can use the following guidelines for the values of
these curves.  Remember these are guidelines.  Your needs may dictate a
different configuration.
ul
Set the ul service curve to just under the circuit capacity in a
dedicated circuit (to avoid tripping the carrier's traffic shaping) or
equal to the circuit capacity in a shared circuit (like DSL or Cable
where other users outside our control are adding traffic to ours so we
cannot avoid the carrier's traffic shaping).
Use a monolinear curve, i.e., only specify rate and not umax and dmax.
Set it at the highest level class and nowhere else (since it, in effect,
flows down through the hierarchy) unless you need to specifically limit
link sharing at a lower level in the hierarchy. Recall that ul does not
limit bandwidth guaranteed by rt.  Thus, one way of limiting bandwidth
at a leaf node is to simply specify the rt curve at the maximum amount
and do not specify an ls curve; this means it will nor borrow additional
bandwidth.  One would only need to specify ul in this case if one wanted
the leaf to be able to borrow above the rt guarantees but only up to a
set amount.  Finally, one might use a lower level ul if one wanted to
limit the bandwidth allocated to a non-leaf node (a branch).  Remember,
branches do not have rt curves and so one cannot limit bandwidth that
way. Thus, the only way to hard limit a branch is to set ul.  To
reiterate, ul is usually set only at the top level class.
When specifying a ul service curve, one must also specify an ls service
curve.  One cannot specify a ul curve  without an ls curve.
ls
The ls service curve is used ONLY to calculate link sharing, i.e., how
to allocate extra available bandwidth.  It does not specify directly how
much bandwidth a queue receives.
If a class does specify an ls service curve either directly or
indirectly (by specifying an sc service curve), it will not receive any
extra bandwidth over its rt service curve.
Only the ratios of ls service curves are important, not the values.
Nonetheless, for sanity's sake, it makes sense to use ls service curve
values which have some relevance to the circuit size.
Use monolinear ls service curves.
ls service curves and ul service curves are the only types of service
curves which can be applied to branches. This is how traffic is divided
between the branches of a hierarchy.  Remember that extra bandwidth is
only divided between peers at the same level in the hierarchy.
Use ls service curves on leaf nodes if you want the leaf node to use
extra bandwidth if it is available.
If the ratio in which extra bandwidth should be allocated is the same
ratio in which it is guaranteed, i.e., the ls service curve is the same
as the rt service curve, both can be specified in a single definition
using the sc service curve, i.e., no need for separate ls and rt
entries.  Use separate ls and rt definitions in a leaf node if the ratio
at which extra bandwidth is allocated is different than the ratio in
which it is guaranteed.  For example, we may have a small amount of
guaranteed bandwidth for our web server and a larger amount of
guaranteed traffic for all the rest of our bulk traffic but, if the web
site needs more bandwidth and there is contention for extra bandwidth
between web and bulk traffic, we want the web server to have top
priority.  Thus, the ratio of the web to bulk rt curves might be 1:5 but
the ratio of the ls curves 5:1.  This is one of the big advantages of
HFSC.
sc
Use sc service curves on leaf nodes when the rt service curve and the ls
service curves are identical.
Use monolinear sc service curves.  By implication, do not use sc service
curves if you want a dilinear rt curve, i.e., to guarantee latency
separately from bandwidth.
rt
The rt service curves are used for guaranteeing bandwidth and have
nothing to do with allocating extra available bandwidth.
If the minimum required latency is greater than the latency provided by
the guaranteed bandwidth, use a monolinear rt service curve.  For
example, let's say we have allocated 2 Mbps to VoIP traffic with a
maximum packet size of 222 bytes and we need latency of no more than 10
ms.  (222 * 8)/2,000,000(b/s) = 0.9ms per packet.  The latency provided
by the guaranteed bandwidth (the m2 curve) is already less than the
minimum latency we need so we do not need to specify a separate m1
curve.
If the minimum required latency is less than the latency provided by the
guaranteed bandwidth, use a dilinear rt service curve.  For example,
let's say we have allocated 2 Mbps to video with a frame size of 8KB and
the minimum latency for those frames should be 10ms.  (8000 *
8)bits/0.010s = 6.4 Mbps.  To meet our minimum latency, we need more
bandwidth than 2 Mbps so we need to specify an m1 curve which is steeper
(more bandwidth) than the m2 curve so rt umax 64kbit dmax 10ms rate
2000kbit.
The rt service curves are NOT limited by the ul service curves.
Ensure that the sum of all the m2 rt curves, i.e., the sum of all the
guaranteed bandwidths, are less than or equal to the top level ul which
should be less than or equal to the circuit capacity.
Unless carried to excess, specify m1 rt curves where needed according to
the queue latency requirements even if the sum of the m1 curves, i.e.,
the sum of all the temporary bandwidths necessary to meet the latency
guarantees, is greater than the top level ul.  Strictly speaking, this
violates the theory that HFSC should be able to meet all bandwidth
guarantees but, practically speaking, one can do this with no
deleterious effects except in the most extreme situations where all
queues are continually backlogged or there can be absolutely no
violation of guarantee whatsoever under any circumstances (perhaps life
critical systems).

Re: A sysadmin's understanding of HFSC and IFB

[John A. Sullivan III]

On Fri, 2011-12-09 at 08:59 +0100, Eric Dumazet wrote:
> Le vendredi 09 décembre 2011 à 02:17 -0500, John A. Sullivan III a
> écrit :
> > Hello, all.  I've been trying to summarize my last week's worth of
> > research into HFSC and IFB.  Being neither a developer nor a
> > mathematician, I found most of the existing documentation daunting and
> > am truly grateful for the help I received on this list to understand the
> > technologies.
> > 
> > I do not currently have a blog to post this research and so was thinking
> > of posting it to this list so that it could be archived and searchable
> > for other poor sysadmin types like me to save them the days of
> > struggling to get their practical heads around the concepts.
> > 
> > However, since this is probably a 15 page or so document, I realized
> > this could be quite rude to those on dial up or metered connections.
> > Would it be appropriate to post my summary here? Thanks - John
> > 
> 
> Please post here, thats definitely a good idea.
> 
> I am pretty sure your contribution could serve to add a page to 
> 
> http://www.linuxfoundation.org/collaborate/workgroups/networking/group
> 
> I believe we lack documentation. A lot.
<snip>
Well . . . it's finally done but, it required so many non-ascii graphics
that it turned into a 25 page PDF.  Would that be appropriate to post to
this list? I don't know if it allows attachments?

Would it be considered rude to cross post it to the new LARTC list?

Also, if it is of any help, I have a far less structured document - 12
pages of my notes on building a test WAN environment with IFB, HFSC, and
netem.  If that is of any interest, I can post that, too. I do not want
to be presumptuous and they are far from perfect but I also know how
much I struggled to find documentation.  Thanks - John