[LARTC] English translation of article on HFSC

[LARTC] English translation of article on HFSC

[Martin A. Brown]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Greetings all,

Working in concert with the original authors, Klaus Rechert and 
Patrick McHardy, I have translated their article "HFSC Scheduling 
mit Linux" [0] on Hierarchical Fair Service Curve (HFSC) into 
English [1].

   http://linux-ip.net/tc/hfsc.en/

Although the original content is not available directly from their 
website, Linux Magazin published the German article in 2/2005 [2].  
The article is apparently slated for republication in special 
edition 3 of 2006 [3] (I don't know whether it is available yet).

The HFSC queueing discipline itself was written by Patrick McHardy 
and added to the Linux kernel over two years ago, yet there isn't a 
great deal of documentation in English on the implementation itself, 
as he himself observes.

I undertook this effort as a result of a posting on this list [4] 
from several weeks ago, inquiring about further documentation on 
HSFC.  Thanks very much to Klaus Rechert for reviewing the 
translation and Linux Magazin for allowing the English translation 
to be distributed.

The academic work underlying HFSC was submitted as an ACM paper [5] 
in 1997, and is available in English to illustrate the conceptual 
underpinnings of HFSC.

The article announced here is a translation of a practical 
explanation of a typical usage case for the Linux HFSC 
implementation.

I welcome comments and questions,

- -Martin

 [0] http://klaus.geekserver.net/hfsc/hfsc.html
 [1] http://linux-ip.net/tc/hfsc.en/
 [2] http://www.linux-magazin.de/Artikel/ausgabe/2005/02
 [3] http://www.linux-magazin.de/Produkte/lms_2006_3.html
 [4] http://mailman.ds9a.nl/pipermail/lartc/2006q2/018857.html
 [5] http://www.acm.org/sigs/sigcomm/sigcomm97/papers/p011.html

- -- 
Martin A. Brown
http://linux-ip.net/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: For info see http://quantumlab.net/pine_privacy_guard/

iD8DBQFEm+6Fki79Zb8hnmwRAhSdAJ9DXD6ZcD91XLi/Pl7ZWKbauThFCwCfYG1y
O7xH+iYev2iCHnWfjxt5m44=DHJJ
-----END PGP SIGNATURE-----
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] English translation of article on HFSC

[Nickola Kolev]

[-- Attachment #1.1: Type: text/plain, Size: 914 bytes --]

Hello, Martin,

On Fri, 23 Jun 2006 08:37:07 -0500
"Martin A. Brown" <martin@linux-ip.net> wrote:

[ cut ]

> The HFSC queueing discipline itself was written by Patrick McHardy 
> and added to the Linux kernel over two years ago, yet there isn't a 
> great deal of documentation in English on the implementation itself, 
> as he himself observes.

[ cut ]

Just a question - wasn't Mr. Kenjiro Cho [1] the original writer of the
HFSC queueing discipline, following the work of Mr. Hui Zhang [2], et
al.? IIRC, Mr. Patrick McHardy just ported it to the linux kernel (in
no way I want to underestimate the amount of work involved). Because
I'm not a programmer myself, I have no way to check this. So, probably
Mr. McHardy could enlighten us on the question.

[1] http://www.csl.sony.co.jp/person/kjc/kjc/software.html
[2] http://www.cs.cmu.edu/~hzhang/HFSC/main.html

-- 
Greets,
Nickola

[-- Attachment #1.2: Type: application/pgp-signature, Size: 189 bytes --]

[-- Attachment #2: Type: text/plain, Size: 143 bytes --]

_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] English translation of article on HFSC

[Martin A. Brown]

Greetings Nickola!

 : Just a question - wasn't Mr. Kenjiro Cho [1] the original writer 
 : of the HFSC queueing discipline, following the work of Mr. Hui 
 : Zhang [2], et al.?

<snip/>

In fact, I was probably not quite exact enough in my introduction.  
I meant this remark to be understood specifically with regard to the 
Linux HFSC implementation.

You are quite correct to allude to the *BSD altq HFSC implementation 
which preceded Patrick McHardy's work.

Thanks for the point of clarification, Nickola.  Other history on 
HFSC would probably need to be introduced by somebody who knows this 
topic better than I do.

Best regards,

-Martin

-- 
Martin A. Brown
http://linux-ip.net/
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] English translation of article on HFSC

[Patrick McHardy]

Hi Martin,

first of all: thanks alot for your efforts (and sorry for a bit of
silence from my side, I'm busy as usual ..)

Martin A. Brown wrote:
> Greetings Nickola!
> 
>  : Just a question - wasn't Mr. Kenjiro Cho [1] the original writer 
>  : of the HFSC queueing discipline, following the work of Mr. Hui 
>  : Zhang [2], et al.?
> 
> <snip/>
> 
> In fact, I was probably not quite exact enough in my introduction.  
> I meant this remark to be understood specifically with regard to the 
> Linux HFSC implementation.
> 
> You are quite correct to allude to the *BSD altq HFSC implementation 
> which preceded Patrick McHardy's work.
> 
> Thanks for the point of clarification, Nickola.  Other history on 
> HFSC would probably need to be introduced by somebody who knows this 
> topic better than I do.


The first implementation was written by Hui Zhang and his colleagues
at Carnegie Mellon. It wasn't very pretty and IIRC not implemented in
a very efficient way. Kenjiro Cho reimplemented it while he was at
Carnegie Mellon, and incorporated his implementation into ALTQ. It
was later enhanced by Oleg Cherevko, who added upper-limit curves
for non-work-conserving mode. This is the implementation used in
the various BSDs. The Linux version if a port of the ALTQ version,
but includes a few enhancements like rbtrees instead of linked lists
and a couple of O(n) algorithms replaced by O(1) variants, which
increases scalability with many classes greatly.

Hope that clears up this history :)
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] English translation of article on HFSC

[Andy Furniss]

Martin A. Brown wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
> Greetings all,
> 
> Working in concert with the original authors, Klaus Rechert and 
> Patrick McHardy, I have translated their article "HFSC Scheduling 
> mit Linux" [0] on Hierarchical Fair Service Curve (HFSC) into 
> English [1].

Thanks Martin.

> 
>    http://linux-ip.net/tc/hfsc.en/

I don't claim to totally get hfsc and don't actually use it yet because 
until recently I only had 288kbit upstream at atm level, which doesn't 
leave enough to split 4/5 users equally. I have 448 now so will use it 
soon, especially if there is going to be a proper atm overhead accounting.

I did in the past test a 4/5 way equal user setup and what I saw makes 
me curious why all the classes in the example are sc.

 From the tests I did the nice thing about hfsc is that you can have 5 
backlogged ls classes and still only add jitter from the transmit time 
of one mtu packet. HTB will add 5x in this case but it's jitter and you 
can skew the average a bit.

5 backlogged/near rate rt with MTU sized packets = 5x jitter with hfsc 
so rt really needs to be uses carefully ?

Of course I havent re tested - it may have been because the ls each had 
very small rates but could borrow.

Andy.
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc