Skip to contentSkip to conversation

HFSC & Stab documentation

PATCH In review Michal Soltys 2 participants 6 messages Feb 26, 2009 – May 11, 2009

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover HFSC & Stab documentation

These patches add documentation for HFSC scheduler and size tables. See patch covers for detailed info.

Michal Soltys (2):
HFSC (7) & (8) documentation + assorted changes
Stab documentation + assorted changes

 Makefile           |    2 +
 man/man7/tc-hfsc.7 |  525 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 man/man8/tc-hfsc.8 |   61 ++++++
 man/man8/tc-stab.8 |  156 ++++++++++++++++
 man/man8/tc.8      |    3 +
 tc/q_hfsc.c        |    6 +-
 tc/tc_core.c       |    4 +-
 tc/tc_stab.c       |    9 +-
 8 files changed, 759 insertions(+), 7 deletions(-)
 create mode 100644 man/man7/tc-hfsc.7
 create mode 100644 man/man8/tc-hfsc.8
 create mode 100644 man/man8/tc-stab.8
#1 lore raw

PATCH 1/2 HFSC (7) & (8) documentation + assorted changes

This patch adds detailed documentation for HFSC scheduler. It roughly follows HFSC paper, but tries to not rely too much on math side of things. Post-paper/Linux specific subjects (timer resolution, ul service curve, etc.) are also discussed.

I've read it many times over, but it's a lengthy chunk of text - so try to be understanding in case I made some mistakes.

tc-hfsc(7): explains algorithm in detail (very long) tc-hfsc(8): explains command line options briefly tc(8): adds references to new man pages
Makefile: adds man7 directory to install target q_hfsc.c: minimal help text changes, consistency with tc-hfsc(8)

---
 Makefile           |    2 +
 man/man7/tc-hfsc.7 |  525 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 man/man8/tc-hfsc.8 |   61 ++++++
 man/man8/tc.8      |    3 +
 tc/q_hfsc.c        |    6 +-
 5 files changed, 596 insertions(+), 1 deletions(-)
 create mode 100644 man/man7/tc-hfsc.7
 create mode 100644 man/man8/tc-hfsc.8
Makefile +2 -0
index 6096a99..8ac0fe6 100644
@@ -53,6 +53,8 @@ install: all
 	install -m 0644 $(shell find etc/iproute2 -maxdepth 1 -type f) $(DESTDIR)$(CONFDIR)
 	install -m 0755 -d $(DESTDIR)$(MANDIR)/man8
 	install -m 0644 $(shell find man/man8 -maxdepth 1 -type f) $(DESTDIR)$(MANDIR)/man8
+	install -m 0755 -d $(DESTDIR)$(MANDIR)/man7
+	install -m 0644 $(shell find man/man7 -maxdepth 1 -type f) $(DESTDIR)$(MANDIR)/man7
 	ln -sf tc-bfifo.8  $(DESTDIR)$(MANDIR)/man8/tc-pfifo.8
 	ln -sf lnstat.8  $(DESTDIR)$(MANDIR)/man8/rtstat.8
 	ln -sf lnstat.8  $(DESTDIR)$(MANDIR)/man8/ctstat.8
man/man7/tc-hfsc.7 new file +525 -0

525 lines not on this page · raw message

man/man8/tc-hfsc.8 new file +61 -0

61 lines not on this page · raw message

man/man8/tc.8 +3 -0
index 8c0880f..da26478 100644
@@ -368,12 +368,15 @@ was written by Alexey N. Kuznetsov and added in Linux 2.2.
 .SH SEE ALSO
 .BR tc-cbq (8),
 .BR tc-htb (8),
+.BR tc-hfsc (8),
+.BR tc-hfsc (7),
 .BR tc-sfq (8),
 .BR tc-red (8),
 .BR tc-tbf (8),
 .BR tc-pfifo (8),
 .BR tc-bfifo (8),
 .BR tc-pfifo_fast (8),
+.BR tc-stab (8),
 .br
 .RB "User documentation at " http://lartc.org/ ", but please direct bugreports and patches to: " <[email protected]>
 
tc/q_hfsc.c +5 -1
index b190c71..03539ec 100644
@@ -43,7 +43,7 @@ explain_class(void)
 	fprintf(stderr,
 		"Usage: ... hfsc [ [ rt SC ] [ ls SC ] | [ sc SC ] ] [ ul SC ]\n"
 		"\n"
-		"SC := [ [ m1 BPS ] [ d SEC ] m2 BPS\n"
+		"SC := [ [ m1 BPS ] d SEC ] m2 BPS\n"
 		"\n"
 		" m1 : slope of first segment\n"
 		" d  : x-coordinate of intersection\n"
@@ -57,6 +57,10 @@ explain_class(void)
 		" dmax : maximum delay\n"
 		" rate : rate\n"
 		"\n"
+		"Remarks:\n"
+		" - at least one of 'rt', 'ls' or 'sc' must be specified\n"
+		" - 'ul' can only be specified with 'ls' or 'sc'\n"
+		"\n"
 	);
 }
 
Signature · 1 line
1.6.1
#2 lore raw

Re: [PATCH/RFC 1/2] HFSC (7) & (8) documentation + assorted changes

It is really VERY VERY great documentation.
Thanks a lot for your efforts!

Quoted 4 lines · On Friday 27 February 2009 01:01:31 Michal Soltys wrote:

This patch adds detailed documentation for HFSC scheduler. It roughly follows HFSC paper, but tries to not rely too much on math side of things. Post-paper/Linux specific subjects (timer resolution, ul service curve, etc.) are also discussed.

#3 lore raw

PATCH 2/2 Stab documentation + assorted changes

In reply to Michal Soltys

This adds generic explanation about size tables.

tc-stab(8): Commandline + details
One thing I'm not sure, is whenever any layer2 data is included in case of shaping directly on ppp interface (see the bottom of the man page).

tc_stab.c: small fixes to commandline help

tc_core.c:
As kernel part of things relies on cell align which is always set to -1, I also added it to userspace computation stage. This way if someone specified e.g. 2048 and 512 for mtu and tsize respectively, one wouldn't end with tsize supporting mtu 4096 suddenly, New default mtu is also set to 2048 (disregarding weirdness of setting mtu to such values).

Unless I missed something, this is harmless and feels cleaner, but if it's not allowed, documentation will have to be changed back to 2047 + extra explanation as well.

---
 man/man8/tc-stab.8 |  156 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 tc/tc_core.c       |    4 +-
 tc/tc_stab.c       |    9 ++-
 3 files changed, 163 insertions(+), 6 deletions(-)
 create mode 100644 man/man8/tc-stab.8
man/man8/tc-stab.8 new file +156 -0
new file mode 100644
index 0000000..9e84f25
@@ -0,0 +1,156 @@
+.TH STAB 8 "25 February 2009" iproute2 Linux
+.
+.SH NAME
+tc\-stab \- Generic size table manipulations
+.
+.SH SYNOPSIS
+.nf
+tc qdisc add ... stab \\
+.RS 4
+[ \fBmtu\fR BYTES ] [ \fBtsize\fR SLOTS ] \\
+[ \fBmpu\fR BYTES ] [ \fBoverhead\fR BYTES ] [ \fBlinklayer\fR TYPE ] ...
+.RE
+
+TYPE := adsl | atm | ethernet
+.fi
+
+For the description of BYTES \- please refer to the \fBUNITS\fR
+section of \fBtc\fR(8).
+
+.IP \fBmtu\fR 4
+.br
+maximum packet size we create size table for, assumed 2048 if not specified explicitly
+.IP \fBtsize\fR
+.br
+required table size, assumed 512 if not specified explicitly
+.IP \fBmpu\fR
+.br
+minimum packet size used in computations
+.IP \fBoverhead\fR
+.br
+per\-packet size overhead (can be negative) used in computations
+.IP \fBlinklayer\fR
+.br
+required linklayer adaptation.
+.PP
+.
+.SH DESCRIPTION
+.
+Size tables allow manipulation of packet size, as seen by whole scheduler
+framework (of course, the actual packet size remains the same). Adjusted packet
+size is calculated only once \- when a qdisc enqueues the packet. Initial root
+enqueue initializes it to the real packet's size.
+
+Each qdisc can use different size table, but the adjusted size is stored in
+area shared by whole qdisc hierarchy attached to the interface (technically,
+it's stored in skb). The effect is, that if you have such setup, the last qdisc
+with a stab in a chain "wins". For example, consider HFSC with simple pfifo
+attached to one of its leaf classes. If that pfifo qdisc has stab defined, it
+will override lengths calculated during HFSC's enqueue, and in turn, whenever
+HFSC tries to dequeue a packet, it will use potentially invalid size in its
+calculations. Normal setups will usually include stab defined only on root
+qdisc, but further overriding gives extra flexibility for less usual setups.
+
+Initial size table is calculated by \fBtc\fR tool using \fBmtu\fR and
+\fBtsize\fR parameters. The algorithm sets each slot's size to the smallest
+power of 2 value, so the whole \fBmtu\fR is covered by the size table. Neither
+\fBtsize\fR, nor \fBmtu\fR have to be power of 2 value, so the size
+table will usually support more than is required by \fBmtu\fR.
+
+For example, with \fBmtu\fR\~=\~1500 and \fBtsize\fR\~=\~128, a table with 128
+slots will be created, where slot 0 will correspond to sizes 0\-16, slot 1 to
+17\~\-\~32, \&..., slot 127 to 2033\~\-\~2048. Note, that the sizes
+are shifted 1 byte (normally you would expect 0\~\-\~15, 16\~\-\~31, \&...,
+2032\~\-\~2047). Sizes assigned to each slot depend on \fBlinklayer\fR parameter.
+
+Stab calculation is also safe for an unusual case, when a size assigned to a
+slot would be larger than 2^16\-1 (you will lose the accuracy though).
+
+During kernel part of packet size adjustment, \fBoverhead\fR will be added to
+original size, and after subtracting 1 (to land in the proper slot \- see above
+about shifting by 1 byte) slot will be calculated. If the size would cause
+overflow, more than 1 slot will be used to get the final size. It of course will
+affect accuracy, but it's only a guard against unusual situations.
+
+Currently there're two methods of creating values stored in the size table \-
+ethernet and atm (adsl):
+
+.IP ethernet 4
+.br
+This is basically 1\-1 mapping, so following our example from above
+(disregarding \fBmpu\fR for a moment) slot 0 would have 8, slot 1 would have 16
+and so on, up to slot 127 with 2048. Note, that \fBmpu\fR\~>\~0 must be
+specified, and slots that would get less than specified by \fBmpu\fR, will get
+\fBmpu\fR instead. If you don't specify \fBmpu\fR, the size table will not be
+created at all, although any \fBoverhead\fR value will be respected during
+calculations.
+.IP "atm, adsl"
+.br
+ATM linklayer consists of 53 byte cells, where each of them provides 48 bytes
+for payload. Also all the cells must be fully utilized, thus the last one is
+padded if/as necessary.
+
+When size table is calculated, adjusted size that fits properly into lowest
+amount of cells is assigned to a slot. For example, a 100 byte long packet
+requires three 48\-byte payloads, so the final size would require 3 ATM cells
+\- 159 bytes.
+
+For ATM size tables, 16\~bytes sized slots are perfectly enough. The default
+values of \fBmtu\fR and \fBtsize\fR create 4\~bytes sized slots.
+.PP
+.
+.SH "TYPICAL OVERHEADS"
+The following values are typical for different adsl scenarios (based on
+\fB[1]\fR and \fB[2]\fR):
+
+.nf
+LLC based:
+.RS 4
+PPPoA \- 14 (PPP \- 2, ATM \- 12)
+PPPoE \- 40+ (PPPoE \- 8, ATM \- 18, ethernet 14, possibly FCS \- 4+padding)
+Bridged \- 32 (ATM \- 18, ethernet 14, possibly FCS \- 4+padding)
+IPoA \- 16 (ATM \- 16)
+.RE
+
+VC Mux based:
+.RS 4
+PPPoA \- 10 (PPP \- 2, ATM \- 8)
+PPPoE \- 32+ (PPPoE \- 8, ATM \- 10, ethernet 14, possibly FCS \- 4+padding)
+Bridged \- 24+ (ATM \- 10, ethernet 14, possibly FCS \- 4+padding)
+IPoA \- 8 (ATM \- 8)
+.RE
+.fi
+\p There're few important things regarding the above overheads:
+.
+.IP \(bu 4
+IPoA in LLC case requires SNAP, instead of LLC\-NLPID (see rfc2684) \- this is
+the reason, why it actually takes more space than PPPoA.
+.IP \(bu
+In rare cases, FCS might be preserved on protocols that include ethernet frame
+(Bridged and PPPoE).  In such situation, any ethernet specific padding
+guaranteeing 64 bytes long frame size has to be included as well (see rfc2684).
+In the other words, it also guarantees that any packet you send will take
+minimum 2 atm cells. You should set \fBmpu\fR accordingly for that.
+.IP \(bu
+When size table is consulted, and you're shaping traffic for the sake of
+another modem/router, ethernet header (without padding) will already be added
+to initial packet's length. You should compensate for that by subtracting 14
+from the above overheads in such case. If you're shaping directly on the router
+(for example, with speedtouch usb modem) using ppp daemon, layer2 header will
+not be added yet.
+
+For more thorough explanations, please see \fB[1]\fR and \fB[2]\fR.
+.
+.SH "SEE ALSO"
+.
+\fBtc\fR(8), \fBtc\-hfsc\fR(7), \fBtc\-hfsc\fR(8),
+.br
+\fB[1]\fR http://ace\-host.stuart.id.au/russell/files/tc/tc\-atm/
+.br
+\fB[2]\fR http://www.faqs.org/rfcs/rfc2684.html
+
+Please direct bugreports and patches to: <[email protected]>
+.
+.SH "AUTHOR"
+.
+Manpage created by Michal Soltys ([email protected])
tc/tc_core.c +2 -2
index 9a0ff39..ffaeb2d 100644
@@ -155,12 +155,12 @@ int tc_calc_size_table(struct tc_sizespec *s, __u16 **stab)
 	}
 
 	if (s->mtu == 0)
-		s->mtu = 2047;
+		s->mtu = 2048;
 	if (s->tsize == 0)
 		s->tsize = 512;
 
 	s->cell_log = 0;
-	while ((s->mtu >> s->cell_log) > s->tsize - 1)
+	while ((s->mtu - 1 >> s->cell_log) > s->tsize - 1)
 		s->cell_log++;
 
 	*stab = malloc(s->tsize * sizeof(__u16));
tc/tc_stab.c +5 -4
index 47b4e5e..e6b8770 100644
@@ -32,11 +32,12 @@ static void stab_help(void)
 	fprintf(stderr,
 		"Usage: ... stab [ mtu BYTES ] [ tsize SLOTS ] [ mpu BYTES ] \n"
 		"                [ overhead BYTES ] [ linklayer TYPE ] ...\n"
-		"   mtu       : max packet size we create rate map for {2047}\n"
+		"TYPE := adsl | atm | ethernet\n"
+		"   mtu       : max packet size we create size table for {2048}\n"
 		"   tsize     : how many slots should size table have {512}\n"
-		"   mpu       : minimum packet size used in rate computations\n"
-		"   overhead  : per-packet size overhead used in rate computations\n"
-		"   linklayer : adapting to a linklayer e.g. atm\n"
+		"   mpu       : minimum packet size used in size table computations\n"
+		"   overhead  : per-packet size overhead used in size table computations\n"
+		"   linklayer : required linklayer adaptation, (adsl and atm are synonyms)\n"
 		"Example: ... stab overhead 20 linklayer atm\n");
 
 	return;
Signature · 1 line
1.6.1
#4 lore raw
In reply to Michal Soltys

Is there any chances that this patches will go to mainstream?

Quoted 25 lines · On Friday 27 February 2009 01:01:30 Michal Soltys wrote:

These patches add documentation for HFSC scheduler and size tables. See patch covers for detailed info.

Michal Soltys (2):
HFSC (7) & (8) documentation + assorted changes
Stab documentation + assorted changes

 Makefile           |    2 +
 man/man7/tc-hfsc.7 |  525
++++++++++++++++++++++++++++++++++++++++++++++++++++ man/man8/tc-hfsc.8 |  
61 ++++++
 man/man8/tc-stab.8 |  156 ++++++++++++++++
 man/man8/tc.8      |    3 +
 tc/q_hfsc.c        |    6 +-
 tc/tc_core.c       |    4 +-
 tc/tc_stab.c       |    9 +-
 8 files changed, 759 insertions(+), 7 deletions(-)
 create mode 100644 man/man7/tc-hfsc.7
 create mode 100644 man/man8/tc-hfsc.8
 create mode 100644 man/man8/tc-stab.8

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

#5 lore raw
Quoted 10 lines · Denys Fedoryschenko

Is there any chances that this patches will go to mainstream?

Quoted 7 lines · On Friday 27 February 2009 01:01:30 Michal Soltys wrote:

These patches add documentation for HFSC scheduler and size tables. See patch covers for detailed info.

Michal Soltys (2):
HFSC (7) & (8) documentation + assorted changes
Stab documentation + assorted changes

I'll adjust/expand this a bit, and repost as v2.

Particulary:

- move hfsc's section about timers to a separate man page, so it can be referenced by other man pages (tbf, htb, ...) where it's important, in future

- expand stab into both stab/rtab; I'll refrain from changing the calculation as well, as it's minor and irrelevant

Still, if for some reason that documentation with cli help related changes is not acceptable for any formal and/or content-related reasons, it would be good to know that beforehand.