Hierarchical Fair Service Curve packet scheduler ------------------------------------------------ This is a port of the altq HFSC packet scheduler for Linux 2.4/2.6. HFSC is described in "A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Service" by Ion Stoica, Hui Zhang, and T. S. Eugene Ng. The altq implementation was made by Carnegie Mellon University and was released under a BSD-style license. News ------- 2004-02-01: - HFSC has been merged in both the 2.4 and 2.6 trees. 2004-01-26: - New patches, changes: - Remove duplicate list_for_each_entry_safe definition in 2.4 version - Remove some debugging code - Add GPL License, change MODULE_LICENSE to GPL - tc: New input format for service curve parameters - tc: Output format of tc class show similar to new input format - The new input format (m1/d/m2) is similar to what is used on the various BSDs The old format (umax/dmax/rate) is also supported, but output is always shown in the new format. - Here is some documentation for HFSC for Router Plugins, it should give you a good idea how to use HFSC: http://www.tik.ee.ethz.ch/~crossbow/rp/plugins/hfsc.html 2004-01-24: - Add patches for running HFSC inside tcsim (tcsim/). 2004-01-06: - New patches, changes: - Fix leaks in filter destruction - Make PSCHED_TIME_SOURCE == PSCHED_GETTIMEOFDAY work - Fix JIFFIE2US macro for PSCHED_GETTIMEOFDAY (Jonas Berlin) - Proper module refcounting for 2.4 version - Note: For kernels before 2.4.25-pre3/2.6.1-rc1 you need to apply one of 2.4-tcf_destroy/2.6-tcf_destroy which add the tcf_destroy function and fix a couple of memory leaks in other packet schedulers. 2003-12-05: - The original authors released a copy of the code without the advertising clause, the change was also made in the altq repository. The license is now GPL compatible. Thanks to Tze Sing Eugene Ng. - New patches, changes: - Remove advertising clause, change MODULE_LICENSE to Dual BSD/GPL - check cl->qdisc->ops->drop != NULL before calling it - rediffed iproute part, apparently it was broken with changed statistics 2003-11-14: - Update patches, changes: - fix double-free after failed requeue in qdisc_peek_len - don't allow classes without realtime or linkshare service curve - use noop_qdisc when qdisc_create_dflt fails due to memory shortage - consolidate statistics - allow class changing without purging the queue - fix vt initialization for first active child class - several minor fixes - cleanup 2003-11-01: - 2.4 patch was broken (2.4 has no jiffies.h), replaced by good one - include htb support in tc binary 2003-10-31: - Update patches, changes: - Fix static linking - adjust scale factors for linux - Fix update_vf for rt-only classes 2003-10-27: - Add pre-compiled tc binary. - Update patches again, changes to last version: - automatically create root class at initialization - changing parameters while operating works fine now - allow service curves to be removed - fix class destruction - avoid filter loops - several minor bugfixes - This version has been extensively stress-tested, all quirks from the previous version are gone. 2003-10-26: - Update patch with too many changes to list here, patch is for 2.6.0-test9 now (should apply to any 2.5 and 2.6). - Add patch for 2.4.23-pre8 (should apply to any recent 2.4). This patch will most likely be updated less often. - The original authors kindly agreed to evaluate alternative, GPL-compatible licenses so the port can be submitted to the kernel some day. 2003-10-17: - Initial release Patches ------- The directory contains six patches: linux-2.6.2-rc2-hfsc.diff patch for linux-2.6.2-rc2 linux-2.4.25-pre7-hfsc.diff patch for linux-2.4.25-pre7 iproute2-hfsc.diff patch for iproute2-2.4.7-now-ss020116-try iproute2-rates-1024-fix.diff patch to fix [km] multipliers in tc 2.4-tcf_destroy add tcf_destroy (for kernels < 2.4.25-pre3) 2.6-tcf_destroy add tcf_destroy (for kernels < 2.6.1-rc1) The first two patches contain the kernel part of HFSC (2.4 and 2.6), the third one contains the tc part. The forth one is a small fix for tc to calculate rates like they are specified for network equipment (1mbit = 1000000bit/s, not 1048576bit/s). The last two patches are only required for older kernels. Additionally you can find a pre-compiled tc binary with both iproute patches + HTB patches applied. tc syntax --------- Usage: ... hfsc [ rt SC ] [ ls SC ] [ ul SC ] SC := [ [ m1 BPS ] [ d SEC ] m2 BPS m1 : slope of first segment d : x-coordinate of intersection m2 : slope of second segment Alternative format: SC := [ [ umax BYTE ] dmax SEC ] rate BPS umax : maximum unit of work dmax : maximum delay rate : rate For information on how to use HFSC, please consult the above mentioned paper. -- Patrick McHardy,