* Re: [WARNING - VERY LONG] A sysadmin's understanding of HFSC and IFB
2011-12-13 23:01 ` [WARNING - VERY LONG] " John A. Sullivan III
@ 2011-12-13 23:10 ` Julien Vehent
2011-12-13 23:35 ` John A. Sullivan III
2011-12-14 5:58 ` John A. Sullivan III
2011-12-14 10:32 ` John A. Sullivan III
2 siblings, 1 reply; 10+ messages in thread
From: Julien Vehent @ 2011-12-13 23:10 UTC (permalink / raw)
To: John A. Sullivan III; +Cc: Eric Dumazet, netdev
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [WARNING - VERY LONG] A sysadmin's understanding of HFSC and IFB
2011-12-13 23:01 ` [WARNING - VERY LONG] " John A. Sullivan III
2011-12-13 23:10 ` Julien Vehent
2011-12-14 5:58 ` John A. Sullivan III
@ 2011-12-14 10:32 ` John A. Sullivan III
2 siblings, 0 replies; 10+ messages in thread
From: John A. Sullivan III @ 2011-12-14 10:32 UTC (permalink / raw)
To: Eric Dumazet; +Cc: netdev
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).
^ permalink raw reply [flat|nested] 10+ messages in thread