-----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-----
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 _______________________________________________ LARTC mailing list LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
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/
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 :)
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.