Date:	Mon, 19 Dec 2011 22:54:33 -0500
From:	"John A. Sullivan III" <jsullivan@...nsourcedevel.com>
To:	netdev@...r.kernel.org
Subject: Re: An error in my HFSC sysadmin documentation

On Fri, 2011-12-09 at 14:35 -0500, John A. Sullivan III wrote:
> On Fri, 2011-12-09 at 13:24 -0500, John A. Sullivan III wrote:
> > Hello, all.  As I mentioned, I'm trying to compile documentation on IFB
> > and HFSC from a sysadmin's perspective but I think I have an error in
> > the way I'm explaining how HFSC determines when to send which packet to
> > meet bandwidth and latency guarantees of the rt service curve.  I'll
> > show where my math is breaking down in the hope someone can see and
> > correct my error.
> Argh!! After walking through it again, correcting my original error and
> using much closer rounding, I still hit a problem.  I'll paste in the
> documentation I've written on deadline time and the walk through of how
> it works but, at the very end, Queue B's rt service curve is violated
> when it should not be:
> 
> <snip>
> 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.
> 
> Here's the problem.  B is serviced when clock time is 1002.54.  It takes
> 0.824 to send B's packet so it has finished dequeueing at 1002.54 +
> 0.824 = 1003.364 which violates B's deadline time of 1003.  That seems
> too big for a rounding error.  Where am I wrong? Thanks - John
<snip>
Michal Soltys graciously pointed out to me off list that I had used the
full sized packet (CRC + preamble + IFG) to calculate clock time but did
not do so when calculating the overall bandwidth.  Once I used the same
method on both, the numbers worked perfectly.  Many thanks to Michal -
John

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

Powered by blists - more mailing lists