From mboxrd@z Thu Jan 1 00:00:00 1970 From: "John A. Sullivan III" Subject: Re: An error in my HFSC sysadmin documentation Date: Mon, 19 Dec 2011 22:54:33 -0500 Message-ID: <1324353273.4187.43.camel@denise.theartistscloset.com> References: <1323455084.3159.63.camel@denise.theartistscloset.com> <1323459325.3159.73.camel@denise.theartistscloset.com> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit To: netdev@vger.kernel.org Return-path: Received: from mout.perfora.net ([74.208.4.195]:51999 "EHLO mout.perfora.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751827Ab1LTDyh (ORCPT ); Mon, 19 Dec 2011 22:54:37 -0500 In-Reply-To: <1323459325.3159.73.camel@denise.theartistscloset.com> Sender: netdev-owner@vger.kernel.org List-ID: 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: > > > 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 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