[LARTC] Re: ADSL Calculator

[LARTC] Re: ADSL Calculator

[Tobias Diedrich]

[-- Attachment #1: Type: text/plain, Size: 1500 bytes --]

Per Marker Mortensen wrote:

> http://www.adsl-optimizer.dk/thesis/
> http://www.adsl-optimizer.dk/thesis/main_final.ps
> 
> chapter 5, will give you extra information.

Hmm, I still haven't read all of it, but I'd like to make two
comments.

1)
I don't think the kernel patch is needed as you can fold that
information into the rate table AFAICS (See the patch at the end
of this mail).  Then again, depending on the overhead value you'd
of course have a slight inaccuracy (in case the overhead is not
divisible by 2^cell_log).  Thus in my patch I just assume the
worst.

2)
AFAICS you only looked at upstream shaping, right?
At least from my experience I can say that for my ADSL link
(3456kbit down / 448kbit up raw ATM speed, shared by 5 users)
it is quite easy to saturate the downstream with a bittorrent
download.  So some sort of downstream shaping is needed too.
Unfortunately the IMQ patch seems to panic the kernel when it
starts dropping packets.  I am currently using a shellscript
which monitors the downstream traffic and starts lowering the
upstream bandwidth limit when downstream usage is above a
threshold, which for now has stopped the complaints from the
two World of Warcraft gamers.  :-)

Patch to iproute2 attached (it compiles, otherwise untested [1]).

[1] And because I need a side-effect of my slightly older patch
    to the kernel currently running on the router I don't think it
    will get testing from me for now... :-/

-- 
Tobias						PGP: http://9ac7e0bc.uguu.de

[-- Attachment #2: iproute2-2.6.11-050330-atm.patch --]
[-- Type: text/plain, Size: 6994 bytes --]

diff -Naru iproute2-2.6.11-050330/tc/m_police.c iproute2-2.6.11-050330-atmpatch/tc/m_police.c
--- iproute2-2.6.11-050330/tc/m_police.c	2005-04-01 21:58:11.000000000 +0200
+++ iproute2-2.6.11-050330-atmpatch/tc/m_police.c	2005-06-17 02:25:44.000000000 +0200
@@ -264,7 +264,7 @@
 	}
 
 	if (p.rate.rate) {
-		if ((Rcell_log = tc_calc_rtable(p.rate.rate, rtab, Rcell_log, mtu, mpu)) < 0) {
+		if ((Rcell_log = tc_calc_rtable(p.rate.rate, rtab, Rcell_log, mtu, mpu, 0, 0)) < 0) {
 			fprintf(stderr, "TBF: failed to calculate rate table.\n");
 			return -1;
 		}
@@ -274,7 +274,7 @@
 	}
 	p.mtu = mtu;
 	if (p.peakrate.rate) {
-		if ((Pcell_log = tc_calc_rtable(p.peakrate.rate, ptab, Pcell_log, mtu, mpu)) < 0) {
+		if ((Pcell_log = tc_calc_rtable(p.peakrate.rate, ptab, Pcell_log, mtu, mpu, 0, 0)) < 0) {
 			fprintf(stderr, "POLICE: failed to calculate peak rate table.\n");
 			return -1;
 		}
diff -Naru iproute2-2.6.11-050330/tc/q_cbq.c iproute2-2.6.11-050330-atmpatch/tc/q_cbq.c
--- iproute2-2.6.11-050330/tc/q_cbq.c	2005-04-01 21:58:11.000000000 +0200
+++ iproute2-2.6.11-050330-atmpatch/tc/q_cbq.c	2005-06-17 02:26:07.000000000 +0200
@@ -137,7 +137,7 @@
 	if (allot < (avpkt*3)/2)
 		allot = (avpkt*3)/2;
 
-	if ((cell_log = tc_calc_rtable(r.rate, rtab, cell_log, allot, mpu)) < 0) {
+	if ((cell_log = tc_calc_rtable(r.rate, rtab, cell_log, allot, mpu, 0, 0)) < 0) {
 		fprintf(stderr, "CBQ: failed to calculate rate table.\n");
 		return -1;
 	}
@@ -336,7 +336,7 @@
 		unsigned pktsize = wrr.allot;
 		if (wrr.allot < (lss.avpkt*3)/2)
 			wrr.allot = (lss.avpkt*3)/2;
-		if ((cell_log = tc_calc_rtable(r.rate, rtab, cell_log, pktsize, mpu)) < 0) {
+		if ((cell_log = tc_calc_rtable(r.rate, rtab, cell_log, pktsize, mpu, 0, 0)) < 0) {
 			fprintf(stderr, "CBQ: failed to calculate rate table.\n");
 			return -1;
 		}
diff -Naru iproute2-2.6.11-050330/tc/q_htb.c iproute2-2.6.11-050330-atmpatch/tc/q_htb.c
--- iproute2-2.6.11-050330/tc/q_htb.c	2005-04-01 21:58:11.000000000 +0200
+++ iproute2-2.6.11-050330-atmpatch/tc/q_htb.c	2005-06-17 02:24:11.000000000 +0200
@@ -35,12 +35,13 @@
 		" r2q      DRR quantums are computed as rate in Bps/r2q {10}\n"
 		" debug    string of 16 numbers each 0-3 {0}\n\n"
 		"... class add ... htb rate R1 [burst B1] [mpu B] [overhead O]\n"
-		"                      [prio P] [slot S] [pslot PS]\n"
+		"                      [granule G] [prio P] [slot S] [pslot PS]\n"
 		"                      [ceil R2] [cburst B2] [mtu MTU] [quantum Q]\n"
 		" rate     rate allocated to this class (class can still borrow)\n"
 		" burst    max bytes burst which can be accumulated during idle period {computed}\n"
 		" mpu      minimum packet size used in rate computations\n"
 		" overhead per-packet size overhead used in rate computations\n"
+		" granule  packet size granularity (round up to granule sized units after overhead is added)\n"
 
 		" ceil     definite upper class rate (no borrows) {rate}\n"
 		" cburst   burst but for ceil {computed}\n"
@@ -108,7 +109,7 @@
 	unsigned buffer=0,cbuffer=0;
 	int cell_log=-1,ccell_log = -1;
 	unsigned mtu, mpu;
-	unsigned char mpu8 = 0, overhead = 0;
+	unsigned char mpu8 = 0, overhead = 0, granule = 0;
 	struct rtattr *tail;
 
 	memset(&opt, 0, sizeof(opt)); mtu = 1600; /* eth packet len */
@@ -135,6 +136,11 @@
 			if (get_u8(&overhead, *argv, 10)) {
 				explain1("overhead"); return -1;
 			}
+		} else if (matches(*argv, "granule") == 0) {
+			NEXT_ARG();
+			if (get_u8(&granule, *argv, 10)) {
+				explain1("granule"); return -1;
+			}
 		} else if (matches(*argv, "quantum") == 0) {
 			NEXT_ARG();
 			if (get_u32(&opt.quantum, *argv, 10)) {
@@ -210,14 +216,14 @@
 	mpu = (unsigned)mpu8 | (unsigned)overhead << 8;
 	opt.ceil.mpu = mpu; opt.rate.mpu = mpu;
 
-	if ((cell_log = tc_calc_rtable(opt.rate.rate, rtab, cell_log, mtu, mpu)) < 0) {
+	if ((cell_log = tc_calc_rtable(opt.rate.rate, rtab, cell_log, mtu, mpu, overhead, granule)) < 0) {
 		fprintf(stderr, "htb: failed to calculate rate table.\n");
 		return -1;
 	}
 	opt.buffer = tc_calc_xmittime(opt.rate.rate, buffer);
 	opt.rate.cell_log = cell_log;
 	
-	if ((ccell_log = tc_calc_rtable(opt.ceil.rate, ctab, cell_log, mtu, mpu)) < 0) {
+	if ((ccell_log = tc_calc_rtable(opt.ceil.rate, ctab, cell_log, mtu, mpu, overhead, granule)) < 0) {
 		fprintf(stderr, "htb: failed to calculate ceil rate table.\n");
 		return -1;
 	}
diff -Naru iproute2-2.6.11-050330/tc/q_tbf.c iproute2-2.6.11-050330-atmpatch/tc/q_tbf.c
--- iproute2-2.6.11-050330/tc/q_tbf.c	2005-04-01 21:58:11.000000000 +0200
+++ iproute2-2.6.11-050330-atmpatch/tc/q_tbf.c	2005-06-17 02:26:28.000000000 +0200
@@ -170,7 +170,7 @@
 		opt.limit = lim;
 	}
 
-	if ((Rcell_log = tc_calc_rtable(opt.rate.rate, rtab, Rcell_log, mtu, mpu)) < 0) {
+	if ((Rcell_log = tc_calc_rtable(opt.rate.rate, rtab, Rcell_log, mtu, mpu, 0, 0)) < 0) {
 		fprintf(stderr, "TBF: failed to calculate rate table.\n");
 		return -1;
 	}
@@ -178,7 +178,7 @@
 	opt.rate.cell_log = Rcell_log;
 	opt.rate.mpu = mpu;
 	if (opt.peakrate.rate) {
-		if ((Pcell_log = tc_calc_rtable(opt.peakrate.rate, ptab, Pcell_log, mtu, mpu)) < 0) {
+		if ((Pcell_log = tc_calc_rtable(opt.peakrate.rate, ptab, Pcell_log, mtu, mpu, 0, 0)) < 0) {
 			fprintf(stderr, "TBF: failed to calculate peak rate table.\n");
 			return -1;
 		}
diff -Naru iproute2-2.6.11-050330/tc/tc_core.c iproute2-2.6.11-050330-atmpatch/tc/tc_core.c
--- iproute2-2.6.11-050330/tc/tc_core.c	2005-04-01 21:58:11.000000000 +0200
+++ iproute2-2.6.11-050330-atmpatch/tc/tc_core.c	2005-06-17 02:23:09.000000000 +0200
@@ -47,11 +47,9 @@
  */
 
 int tc_calc_rtable(unsigned bps, __u32 *rtab, int cell_log, unsigned mtu,
-		   unsigned mpu)
+		   unsigned mpu, unsigned overhead, unsigned granularity)
 {
 	int i;
-	unsigned overhead = (mpu >> 8) & 0xFF;
-	mpu = mpu & 0xFF;
 
 	if (mtu == 0)
 		mtu = 2047;
@@ -65,8 +63,14 @@
 		unsigned sz = (i<<cell_log);
 		if (overhead)
 			sz += overhead;
+		/* FIXME: Maybe the mpu check should be done before adding the overhead */
 		if (sz < mpu)
 			sz = mpu;
+		/* Round up to specified granularity, usefull for ATM based links (ADSL) */
+		if (granularity) {
+			sz += granularity - 1;
+			sz -= sz % granularity;
+		}
 		rtab[i] = tc_core_usec2tick(1000000*((double)sz/bps));
 	}
 	return cell_log;
diff -Naru iproute2-2.6.11-050330/tc/tc_core.h iproute2-2.6.11-050330-atmpatch/tc/tc_core.h
--- iproute2-2.6.11-050330/tc/tc_core.h	2005-04-01 21:58:11.000000000 +0200
+++ iproute2-2.6.11-050330-atmpatch/tc/tc_core.h	2005-06-17 02:22:53.000000000 +0200
@@ -7,7 +7,8 @@
 long tc_core_usec2tick(long usec);
 long tc_core_tick2usec(long tick);
 unsigned tc_calc_xmittime(unsigned rate, unsigned size);
-int tc_calc_rtable(unsigned bps, __u32 *rtab, int cell_log, unsigned mtu, unsigned mpu);
+int tc_calc_rtable(unsigned bps, __u32 *rtab, int cell_log, unsigned mtu,
+                   unsigned mpu, unsigned overhead, unsigned granularity);
 
 int tc_setup_estimator(unsigned A, unsigned time_const, struct tc_estimator *est);
 

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

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

Re: [LARTC] Re: ADSL Calculator

[Per Marker Mortensen]

At Fri, 17 Jun 2005 03:11:35 +0200,
Tobias Diedrich wrote:

Hi

> 1)
> I don't think the kernel patch is needed as you can fold that
> information into the rate table AFAICS (See the patch at the end
> of this mail).  Then again, depending on the overhead value you'd
> of course have a slight inaccuracy (in case the overhead is not
> divisible by 2^cell_log).  Thus in my patch I just assume the
> worst.

I do not remember the details (is my office mate's thesis and not
mine), but from what I remember it will actually more than slightly
inaccurate. The thing is that the rate table is off-by-one with
respect to 2^cell_log  - see section 6.1.2 of the thesis.

If you use the patch in the thesis, the calculations will be 100%
accurate. 
 
> 2)
> AFAICS you only looked at upstream shaping, right?

Its the focus of my office mates thesis, but there is also a chapter
that looks at posible downstream problems. 

> At least from my experience I can say that for my ADSL link
> (3456kbit down / 448kbit up raw ATM speed, shared by 5 users)
> it is quite easy to saturate the downstream with a bittorrent
> download.  So some sort of downstream shaping is needed too.

From what I have seen in different places it is actually normally not
a problem. But 4/8Mbps/768kbps ADSL's are also very common here i
DK. The problem always seem the be the upstream capacity and the
extreme usage P2P programs. 

> Unfortunately the IMQ patch seems to panic the kernel when it
> starts dropping packets.  I am currently using a shellscript

There is actually no need to use IMQ, or there are at least other
ways. Several places I have just setup the queue disciplines on the
interface towards the LAN. If you need communication between the LAN
and the router, you can make a special HTB leaf for that, and map
packages with iptables. 

---
Yours

Per Marker Mortensen <per@markermortensen.dk>
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] Re: ADSL Calculator

[Andy Furniss]

Tobias Diedrich wrote:
> Per Marker Mortensen wrote:
> 
> 
>>http://www.adsl-optimizer.dk/thesis/
>>http://www.adsl-optimizer.dk/thesis/main_final.ps
>>
>>chapter 5, will give you extra information.
> 
> 
> Hmm, I still haven't read all of it, but I'd like to make two
> comments.
> 
> 1)
> I don't think the kernel patch is needed as you can fold that
> information into the rate table AFAICS (See the patch at the end
> of this mail).  Then again, depending on the overhead value you'd
> of course have a slight inaccuracy (in case the overhead is not
> divisible by 2^cell_log).  Thus in my patch I just assume the
> worst.

You end up either being a cell too safe around the optimal sizes even 
if, like you, your overhead is divisible by cell log. So you either have 
to undo your tweaking or underaccount for some packet sizes.

It's still better than doing nothing if you really can't change your 
kernel - Ed Wildgoose posted a similar patch some time ago.

> 
> 2)
> AFAICS you only looked at upstream shaping, right?
> At least from my experience I can say that for my ADSL link
> (3456kbit down / 448kbit up raw ATM speed, shared by 5 users)
> it is quite easy to saturate the downstream with a bittorrent
> download.  So some sort of downstream shaping is needed too.
> Unfortunately the IMQ patch seems to panic the kernel when it
> starts dropping packets.

If imq is unstable on your kernel you could try shaping download on 
egress / use a modified dummy device or use a policer on ingress.

Bittorrent is harder to shape than most things.

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

Re: [LARTC] Re: ADSL Calculator

[Ed W]

>
> Bittorrent is harder to shape than most things.


I think the issue is lots of connections all going into fast start?

I liked Andy's idea of having a seperate queue for the first few Kbytes 
of new connections and pegging it with a VERY short queue length.  This 
means that connections in fast start will get a packet drop very early 
on unless they play very nicely

I guess one could do something like making it the very lowest priority 
class in a standard HTB setup with near zero guaranteed rate and then it 
would be self throttling, the first few connections can come in, mop up 
all the bandwidth, and new connections after that get packet loss very 
early on (because they only get the leftovers), forcing them to slow 
down much more quickly.

Once they have transferred some small amount of data they fall back into 
your normal traffic shaping queues and everything proceeds as normal.

I guess for an even better approach, only do this nasty trick on your 
"bulk" incoming connections...

If anyone gives this a serious test then please do report back with your 
findings

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

Re: [LARTC] Re: ADSL Calculator

[Andy Furniss]

Ed W wrote:
>>
>> Bittorrent is harder to shape than most things.
> 
> I think the issue is lots of connections all going into fast start?
> 
> I liked Andy's idea of having a seperate queue for the first few Kbytes 
> of new connections and pegging it with a VERY short queue length.  This 
> means that connections in fast start will get a packet drop very early 
> on unless they play very nicely

Getting new connections out of slow start like this helps my ingress 
shaping for browsing - not bittorrent, though, it cycles through 
existing connections doing tit for tat, speculative and when new chuncks 
are available so they go in and out of slow start after they have passed 
data already.

See the last few paragraphs of the protocol for the choking rule.

http://www.bittorrent.com/protocol.html


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