More understanding HFSC

More understanding HFSC

[John A. Sullivan III]

To try to understand more about HFSC, I've tried to map out a real world
scenario and how we'd handle it.  My apologies in advance for a
consequently long email :(

As others have pointed out, we immediately noticed that
http://trash.net/~kaber/hfsc/SIGCOM97.pdf seems to speak of sc and ul
whereas the Linux implementation adds rt and ls.  Is it correct to
assume that this is because the Linux implementation foresaw instances
where one might not want the sharing ratio of available bandwidth to be
the same as the ratio of guaranteed bandwidth?

I'm guessing a practical illustration would be a bulk class where I have
low rt just to keep the class from being starved but want it to obtain
available bandwidth more aggressively.  Is that correct?

So trying to put the four possible parameters together, it sounds like
ul is normally used to specify the maximum link speed and can be
specified at the root, no, next child from root class and then flow down
to all descendants without being explicitly specified? But one can also
give a class an explicit ul if one wants to limit the amount of
bandwidth a leaf or branch can consume when sharing available bandwidth?

sc would be used where rt=ls?

ls is used solely to determine ratios of sharing available bandwidth
between peers, does not need to aggregate to <= ul but normally does by
convention? Thus, it has nothing to do with the actual amount of
bandwidth available, just ratios?

rt only applies to leaves and is the guaranteed bandwidth and must
aggregate to <= ul if all guarantees are to be honored?

Very important for my understanding, specifying rt and ls in the same
class is NOT the mechanism used for decoupling latency guarantees from
bandwidth allocations.  That is simply specifying that available
bandwidth will be obtained in a different proportion than the guaranteed
bandwidth.  The decoupling of latency from bandwidth happens by having a
dilinear service curve, i.e., specifying either m1, d, and m2 or
specifying umax, dmax, and rate where umax/dmax != rate.  Is that
correct? If I have that wrong, I think I really missed the point (which
is quite possible!).

So, it then seems like:
virtual time is dependent upon ls
eligible time is dependent upon available bandwidth as determined by ul
and ls
deadline time is dependent on the curve which is why a dilinear curve
can be used to "jump the queue" so to speak or to drop back in the
queue.

This raises an interesting question about dilinear curves and ul.  If m1
is being used to "jump the queue" and not to determine guaranteed
bandwidth, do we need to take into account the resultant bandwidth
calculation of m1 when ensuring rt <= ul? To illustrate, let's say we
have a 100kbits link.  We give interactive traffic 40kbits, VoIP
20kbits, and bulk 40kbits so rt = ul.  However, we specify interactive
as rt 1534b 10ms 40kbits and VoiP as rt 254b 10ms 20kbits.  The m1 rate
puts us way over ul (~= 400kbits + 200kbits + 40kbits).  Is this OK
since it is not actually the guaranteed bandwidth but just the data used
to calculate deadline? I am guessing that if we are in the situation
where packets simply cannot be transmitted fast enough to meet the
requested deadline that this implies we do not have sufficient eligible
time and so deadline becomes moot.


If I've got that right, does the following illustration hold:
Let's assume we have a T1 at 1.544 Mbps (if I've remembered that
correctly).  So we create the highest level child class with a ul of 1.5
Mbps to keep it slightly under the link speed to ensure we do not trip
QoS on the upstream router.  Hmm . . . I suppose that principle would
not hold true in a shared environment like cable or DSL.  In any event,
I think that means 1536kbits in tc-speak.

We then create five child classes named Interactive, VoIP, Video, Web,
and Bulk with the following characteristics and settings:

Bulk is basically everything that has no latency sensitivity and can
tolerate dropped packets.  We assign it rt=100kbits just to keep it from
being starved when other classes are highly active but we'd like it to
access excess bandwidth a little more aggressively so we set
ls=300kbits.  Does this seem reasonable?

Interactive must nowadays include VDI so it is no longer small ssh or
telnet packets.  It needs to accommodate full sized Ethernet packets in
order to transfer screens with a minimum of latency.  It is moderately
latency sensitive and cannot tolerate dropped packets.  I'll assume umax
needs to account for Ethernet header, CRC, preamble, and IFG.  We want
this router to add no more than 30ms to any interactive session.  Thus
we define it with:
rt umax 1534b dmax 30ms rate 300kbits ls rate 500kbits
We defined ls because we want this type of traffic to aggressively
acquire excess bandwidth if we need more than we have guaranteed.
1534b/30ms~=409kbits so we have a concave service curve.

VoIP is very latency sensitive and cannot tolerate drops.  We want to
add no more than 10ms latency to the traffic flow.  We are figuring that
ulaw/alaw will produce the largest packets at 254b including IFG et al.
So we define it as:
rt umax 254b dmax 10ms rate 200kbits ls rate 500kbits
254b/10ms~=203kbits so we have a slightly concave service curve.  This
raises an interesting question.  What if we had set dmax to 20 ms? This
would have given us a convex service curve where m1 != 0.  Is that
illegal? I thought the specification said any convex curves must have m1
= 0.  If it is illegal and we did this by accident, what would happen?

Video is always a problem :) We need to guarantee a large amount of
bandwidth but we also do not want to be eaten alive by video.  We
characterize it as very latency sensitive but we would rather tolerate
drops than queueing and unwanted latency.  Hmm . . . is queue depth
induced latency even an issue with HFSC?
In any event, we want to introduce no more than 10ms latency.  The
typical frame size is 16Kb and there is no difference between the rt and
ls rate so we define the class with:
sc umax 16kbits dmax 10ms rate 400kbits
Interestingly, m1 (1.6Mbps) exceeds ul.  As asked previously, is this a
problem?

Web follows the example cited in my previous email.  We want the text
and css of the served web pages to load quickly.  Larger, non-text data
can take a back seat.  We will guess that the average text is 10KB and
we want to introduce no more than 200ms to start loading the page text.
We thus define it as:
rt umax 80kbits dmax 200ms rate 200kbits ls 400 kbits

Is this setup reasonable, practical, and reflecting a proper
understanding of HFSC or have I missed the boat entirely and need to go
to the back of the class? Thanks to anyone who has taken the time to
read this novel :) - John

Re: More understanding HFSC

[Michal Soltys]

On 11-12-04 07:12, John A. Sullivan III wrote:
> To try to understand more about HFSC, I've tried to map out a real
> world scenario and how we'd handle it.  My apologies in advance for a
> consequently long email :(
> 
> As others have pointed out, we immediately noticed that
> http://trash.net/~kaber/hfsc/SIGCOM97.pdf 

For the paper, use: http://www.cs.cmu.edu/~istoica/hfsc-tr.ps.gz
or
http://www.cs.cmu.edu/~istoica/hfsc_extended.ps.gz

More detailed, with correct sub/superscripts. 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.

> seems to speak of sc and ul whereas the Linux implementation adds rt
> and ls.  Is it correct to assume that this is because the Linux
> implementation foresaw instances where one might not want the sharing
> ratio of available bandwidth to be the same as the ratio of guaranteed
> bandwidth?

The paper talks only about LS and RT curves, which (in context of the
example implementation) were assumed to be the same (meaning, not
literally 1 curve - two separate ones, but defined in identical way).

The actual altq implementation (initially ported to Linux ~2003) allows
them to be specified separately, and adds an UL curve which is used to
limit LS. It also allows specifying leaf classes with only one kind of
the curve.

In a nutshell, RT's role is to guarantee certain bandwidth and latency
(within limits of what the cpu and whole network path can deliver), LS's
role is to distribute remaining bandwidth, and UL's role is to make sure
LS doesn't send too fast (or in more exotic case, to make sure that some
subtrees never get more bandwidth than some predetermined value due to
some policies). UL is ... ugly thing working a bit against LS, but it's
necessary to shape properly for speeds other than interface's native
speed (which is almost always the case).

> I'm guessing a practical illustration would be a bulk class where I
> have low rt just to keep the class from being starved but want it to
> obtain available bandwidth more aggressively.  Is that correct?

Hmmmm ... The class will never be starved in HFSC (if things are setup
correctly). It's more about non-linearity and using real clock for RT
case. LS is just simple arbitrator - go down the tree, selecting
smallest virtual times. RT ignores tree hierarchy completely, and
chooses a set of all eligible leaf classes, and from those the one with
smallest deadline time. Due to non-linearity, it has to use two curves
(eligible and deadline) to achieve its endes. It's all detailed in the
paper and man pages, though not necessarily an easy chunk to read.

> So trying to put the four possible parameters together,

Four ? LS, RT, UL. Unless you also mean RT's split in to eligible and
deadline parts.

> it sounds like ul is normally used to specify the maximum link speed
> and can be specified at the root, no, next child from root class and
> then flow down to all descendants without being explicitly specified?

UL set for some node is only applicable to that node. It prohibits that
node (and implicitly, its whole subtree - so in this context you can
think of it as "flowing down") from participating in LS. But only LS.

> But one can also give a class an explicit ul if one wants to limit the
> amount of bandwidth a leaf or branch can consume when sharing
> available bandwidth?

+/- yes. Keep in mind, that RT is independent from LS (and UL will not
block it in any way), but it still updates cumulative total amount of
service a class received, so it implicitly influences virtual times used
by LS.

> sc would be used where rt=ls?

yes (2 identical curves used for 2 different things)

> ls is used solely to determine ratios of sharing available bandwidth
> between peers, does not need to aggregate to<= ul but normally does by
> convention?

Only ratio, yes. Actual values are irrelevant for LS (only). 2 linear
curves with 10kbit slopes will have the same effect like 100kbit ones.

But, like mentioned above, UL so-to-speak decides whenever a class (and
its subtree, implicitly) is "eligible" to participate in LS, so its
subtree will never push more than UL using LS criterion.

> rt only applies to leaves and is the guaranteed bandwidth and must
> aggregate to<= ul if all guarantees are to be honored?

Only leafs, yes.

RT completely ignores LS[+UL] though.

> Very important for my understanding, specifying rt and ls in the same
> class is NOT the mechanism used for decoupling latency guarantees from
> bandwidth allocations.  That is simply specifying that available
> bandwidth will be obtained in a different proportion than the
> guaranteed bandwidth.

yes

> The decoupling of latency from bandwidth happens by having a dilinear
> service curve, i.e., specifying either m1, d, and m2 or specifying
> umax, dmax, and rate where umax/dmax != rate.  Is that correct?

yes

> So, it then seems like: virtual time is dependent upon ls

yes

> eligible time is dependent upon available bandwidth as determined by
> ul and ls

no, eligible curve is derived from RT curve. For linear and concave
curves it's the same as RT curve. For convex RT - eligible curve is
linear using RT's second slope. The time calculated from it is relative
to packets' heads - essentially answering question: which packets should
be in transit already by current time (and for convex - which should be
sent earlier, so when the curve is violated later by some other
class(es), everything remains fine with reference to the amount of
service received by some time). RT ignores LS/UL.

> deadline time is dependent on the curve which is why a dilinear curve
> can be used to "jump the queue" so to speak or to drop back in the
> queue.

deadline curve is also derived from RT curve, and it's always of the
same parameters. But packets tails are used here - essentialy answering
question: what packet should go first (as only 1 can be send at a time
after all). No relevance to LS/UL in any way or form either.

So more correct way to say is: RT *is* deadline and eligible.

> This raises an interesting question about dilinear curves and ul. If
> m1 is being used to "jump the queue" and not to determine guaranteed
> bandwidth, do we need to take into account the resultant bandwidth
> calculation of m1 when ensuring rt<= ul? To illustrate, let's say we
> have a 100kbits link.  We give interactive traffic 40kbits, VoIP
> 20kbits, and bulk 40kbits so rt = ul.  However, we specify interactive
> as rt 1534b 10ms 40kbits and VoiP as rt 254b 10ms 20kbits.  puts us
> way over ul (~= 400kbits + 200kbits + 40kbits). Is this OK since it
> is not actually the guaranteed bandwidth but just the data used to
> calculate deadline? I am guessing that if we are in the situation
> where packets simply cannot be transmitted fast enough to meet the
> requested deadline that this implies we do not have sufficient
> eligible time and so deadline becomes moot.

1534b/10ms is roughly 1.2mbit rate. So you effectively defined (~1.2mbit
for 10ms, then 40kbit) and (~200kbit for 10ms, then 20kbit). HFSC will
of course schedule this - and such approach to keep certain class
favored on fresh backlog pariod is ok, but keep in mind the side effects
(there're example in man pages mentioned in previous reply):

- any excess like that contributes to total service => influences
  virtual times. the class will have to pay for that during LS
- LS main point is to keep all virtual times as equal as possible; if
  they drift apart that means something is wrong. It's not a big deal
  (or not a deal at all, if user knows what he wants and what he's
  doing) during m1, but might have disastrous effects during m2 (on
  other sibling classes in particular)
- in your example, LS is unusable, as there's always something eligible
  by RT; even if your interface's native speed is 10gbit, RT will cover
  100kbit of the real uplink, and UL will block any LS attempts.

Interesting point is, that some other OSes (BSDs using pf) try to pamper
the user, and won't even let you specify RT going beyond LS, or sum(RTs)
going beyond 80% of interface's speed (iirc). It's bad approach
(limiting legitimate tricks/uses), but certainly a way to avoid misuse
... 

> [cut]

later, though you might want to update the questions first by now :)

Re: More understanding HFSC

[John A. Sullivan III]

----- Original Message -----
> From: "Michal Soltys" <soltys@ziu.info>
> To: "John A. Sullivan III" <jsullivan@opensourcedevel.com>
> Cc: netdev@vger.kernel.org
> Sent: Monday, December 5, 2011 5:18:26 PM
> Subject: Re: More understanding HFSC
> 
> On 11-12-04 07:12, John A. Sullivan III wrote:
><snip> 
> > Very important for my understanding, specifying rt and ls in the
> > same
> > class is NOT the mechanism used for decoupling latency guarantees
> > from
> > bandwidth allocations.  That is simply specifying that available
> > bandwidth will be obtained in a different proportion than the
> > guaranteed bandwidth.
> 
> yes
> 
> > The decoupling of latency from bandwidth happens by having a
> > dilinear
> > service curve, i.e., specifying either m1, d, and m2 or specifying
> > umax, dmax, and rate where umax/dmax != rate.  Is that correct?
> 
> yes
> 
> > So, it then seems like: virtual time is dependent upon ls
> 
> yes
> 
> > eligible time is dependent upon available bandwidth as determined
> > by
> > ul and ls
> 
> no, eligible curve is derived from RT curve. For linear and concave
> curves it's the same as RT curve. For convex RT - eligible curve is
> linear using RT's second slope. The time calculated from it is
> relative
> to packets' heads - essentially answering question: which packets
> should
> be in transit already by current time (and for convex - which should
> be
> sent earlier, so when the curve is violated later by some other
> class(es), everything remains fine with reference to the amount of
> service received by some time). RT ignores LS/UL.
> 
> > deadline time is dependent on the curve which is why a dilinear
> > curve
> > can be used to "jump the queue" so to speak or to drop back in the
> > queue.
> 
> deadline curve is also derived from RT curve, and it's always of the
> same parameters. But packets tails are used here - essentialy
> answering
> question: what packet should go first (as only 1 can be send at a
> time
> after all). No relevance to LS/UL in any way or form either.
> 
> So more correct way to say is: RT *is* deadline and eligible.

Ah, OK.  I think I'm starting to get it.  I had read that but had not put it all together.  It all makes great sense.  So eligible time is answering the question of what packets should we start sending (hence looking at the beginning of the packet) and deadline is answering by when must the packet be fully delivered (hence looking at the tail).

<snip>
> later, though you might want to update the questions first by now :)
<snip>
I don't think what I've learned changes anything that I outlined in the rest of the email but I think I understand it a whole lot better now.  Thanks - John

Re: More understanding HFSC

[John A. Sullivan III]

----- Original Message -----
From: "John A. Sullivan III" <jsullivan@opensourcedevel.com>
To: netdev@vger.kernel.org
Sent: Sunday, December 4, 2011 1:12:19 AM
Subject: More understanding HFSC

<snip>

A great thanks to all those who took a great deal of time to help me understand HFSC.  It was particularly helpful to gain a better understanding of the relationship between fit time, virtual time, eligible time, and deadline time.  I would still like to make sure I've got it in a practical way.  If any one does have the time to see if the below illustration is valid, I'd appreciate it.  And I also appreciate that no one may have that time :)  Thanks again - John

If I've got that right, does the following illustration hold:
Let's assume we have a T1 at 1.544 Mbps (if I've remembered that
correctly).  So we create the highest level child class with a ul of 1.5
Mbps to keep it slightly under the link speed to ensure we do not trip
QoS on the upstream router.  Hmm . . . I suppose that principle would
not hold true in a shared environment like cable or DSL.  In any event,
I think that means 1536kbits in tc-speak.

We then create five child classes named Interactive, VoIP, Video, Web,
and Bulk with the following characteristics and settings:

Bulk is basically everything that has no latency sensitivity and can
tolerate dropped packets.  We assign it rt=100kbits just to keep it from
being starved when other classes are highly active but we'd like it to
access excess bandwidth a little more aggressively so we set
ls=300kbits.  Does this seem reasonable?

Interactive must nowadays include VDI so it is no longer small ssh or
telnet packets.  It needs to accommodate full sized Ethernet packets in
order to transfer screens with a minimum of latency.  It is moderately
latency sensitive and cannot tolerate dropped packets.  We want
this router to add no more than 30ms to any interactive session.  Thus
we define it with:
rt umax 1514b dmax 30ms rate 300kbits ls rate 500kbits
We defined ls because we want this type of traffic to aggressively
acquire excess bandwidth if we need more than we have guaranteed.
1514b/30ms~=400kbits so we have a concave service curve.

VoIP is very latency sensitive and cannot tolerate drops.  We want to
add no more than 10ms latency to the traffic flow.  We are figuring that
ulaw/alaw will produce the largest packets at 234b so we define it as:
rt umax 234b dmax 10ms rate 200kbits ls rate 500kbits
234b/10ms~=203kbits so we have a slightly concave service curve.  This
raises an interesting question.  What if we had set dmax to 20 ms? This
would have given us a convex service curve where m1 != 0.  Is that
illegal? I thought the specification said any convex curves must have m1
= 0.  If it is illegal and we did this by accident, what would happen?

Video is always a problem :) We need to guarantee a large amount of
bandwidth but we also do not want to be eaten alive by video.  We
characterize it as very latency sensitive but we would rather tolerate
drops than queueing and unwanted latency.  Hmm . . . is queue depth
induced latency even an issue with HFSC?
In any event, we want to introduce no more than 10ms latency.  The
typical frame size is 16Kb and there is no difference between the rt and
ls rate so we define the class with:
sc umax 16kbits dmax 10ms rate 400kbits
Interestingly, m1 (1.6Mbps) exceeds ul.  As asked previously, is this a
problem?

Web follows the example cited in my previous email.  We want the text
and css of the served web pages to load quickly.  Larger, non-text data
can take a back seat.  We will guess that the average text is 10KB and
we want to introduce no more than 200ms to start loading the page text.
We thus define it as:
rt umax 80kbits dmax 200ms rate 200kbits ls 400 kbits

Is this setup reasonable, practical, and reflecting a proper
understanding of HFSC or have I missed the boat entirely and need to go
to the back of the class? Thanks to anyone who has taken the time to
read this novel :) - John