Sigh...

Revert max queue mod to delay qdisc and modify delaysetup to make the delay
qdisc the parent of the HTB.  This correctly shapes the traffic.  The max queue depth on the delay qdisc made the HTB redundant.

Fix linux linkdelays to honor queue size properly.

This removes the problem where the delay queuing discipline would
collect packets indefinitely.  It now maintains a maximum queue
length, and drops packets when this fills (droptail).  The linux
delaysetup script has been altered to use this new queue size
mechanism.  Also, I'm committing the updated patch for the tc utility
that allows modification of this queue size parameter from user space.

Both changes to the kernel, and to userland control applications are included
in this checkin.  At present, these files are combined patches; I'll be
separating out the Emulab specific additions/changes in the near future.

The best resource (currently) for understanding the Linux traffic control
mechanisms is at the Linux Diffserv project home page (under Documentation):
http://diffserv.sourceforge.net/

The most noteworthy contributions I've made are the PLR module and DELAY
module port and enhancement.  These two modules are classful (though they
don't use classification filters) and can be chained together with other
modules such as the Heirarchical Token Bucket (used for limiting bandwith).
See: http://luxik.cdi.cz/~devik/qos/htb/

Note that this checkin also includes the patches necessary to obtain
Intermediate Queueing Devices (IMQ) and HTB control under iproute2+tc.  The
IMQ devices allow the attachment of qdiscs on the incoming side of a real
interface (can't do this without them). See: http://trash.net/~kaber/imq/

The Linux Advanced Routing HOWTO is another good source of information:
http://lartc.org

what i thought was variance
is actually std deviation.
eep. so i had to run right off and change variable names.

other: dave says that he shared my "poisson looks funny" intuition, but that
       (in the code that i stole) it is doing the right thing (can't make any
       promises yet about the code after i glued it in)

i have to take a good careful look at the argcount manipulation code.

what i thought was variance
is actually std deviation.
eep. so i had to run right off and change variable names.

other: small fixes and error checking, but nothing exciting.

to handle that. code somewhat cleaner, but not as much as i had hoped for.
kernel grew more than i expected. i think it was like 2k bigger. not that i
obsess over this, but i was surprised.
loss, delay, bw conf()s split from the main conf().
doing all of this made it easier to spot bugs, so yes it was worth it.

what next? oh, test test test. just my favorite thing in the world, don't
you know...

"you should be a tester, rob. you'd make a great tester."
   -- the head of the test team in my dept when i ibmed. she claimed to be
      serious, but i was never sure.

dn_pipe had grown ridiculously.

> commit msg)

haven't touched yet

> the command line reading code has ballooned and could use cleaning in some
> way. since this is user code, i'm not _terribly_ concerned, but...

i played with it and made it more deterministic and i won't have to do tons
of "well, you specified this distribution but you didnt specify this arg"
now. it's not really as nice as i had imagined, but it is improved.

> should add more to 'ipfw pipe show'.

i added some. i tend to forget about it, 'cause it's not like i use this
much. i'm probably not going to bother with writing code to return the
entries in tables.

> more validity checking would be nice, but having the kernel catch it and
>  give a printf() and EINVAL is not bad.

added some. sometimes, i just let the kernel catch it.

--
what next? test a lot.

----

not too convinced that poisson is correct (see corresponding dummynet
commit msg)

the command line reading code has ballooned and could use cleaning in some
way. since this is user code, i'm not _terribly_ concerned, but...

should add more to 'ipfw pipe show'.

more validity checking would be nice, but having the kernel catch it and
 give a printf() and EINVAL is not bad.

Bandwidth now has const rate, uniform, determ and random tables, poisson.

so that's all of the functionality that people wanted.
---

I don't think poisson is working right. it makes a poisson shape, it seems,
but it is _narrow_.
poisson for loss is particularly cheesy.
loss is given to ipfw as a real number 0..1.  ipfw translates it to 0..7fffffff.
i did not want to calculate P(x) for everything between 0 and 7fffffff, so i
do poisson for 0..7fff and shift it 16 bits before sending to kernel. i don't
think this makes a valid poisson dist. if you mess with the mean like that.

what next?
 try some restructuring. some things that made sense in vanilla dummynet
	became quite unwieldy as i kept adding things. making delay,loss,bw
	structs in the dn_pipe might clean things up (at the expense of having
	to say pipe->something->something).
 validity checks (eg mean 100 var 150)
 add more comments.
 test a lot. pretty much everything has had at least some pinging and
	"hmm, it seems to be doing what i want", but...

        const
        uniform
	poisson (right now, that's just random table. i plan to at least
		differentiate it by returning the mean for IP_DUMMYNET_GET)
        random table
        deterministic table
Loss:
        const rate
        const time between drops
        uniform rate dist.
        deterministic table for time between drops

	const
	uniform
	poisson (NB: currently implemented using code with restrictive license)
	random table
	deterministic table
Loss:
	const rate
	const time between drops
	uniform rate dist.
	deterministic table for time between drops

/n/marker/usr/lsrc/FreeBSD/3.4-utah/src/sbin/ipfw/

/n/marker/usr/lsrc/FreeBSD/3.4-utah/src/sys/netinet/

expiration policy for the buffers - we keep them around forever.
At some point, we can start putting queue management in here, but
we might as well be smart about things until then. :)

improvement under load

gets the job done.  Don't try for less than 80us granularity, though,
or, well, you just won't get it.

This improves our granularity to the range I'm interested in, but at
the expense of maxing out a CPU.

Remove -DSPIN_OK from the CFLAGS line in the makefile if you don't
want this behavior.  Note that this only happens if you're attempting
sleeps of < 1second.  If your sleeps are longer than that, the code
will just use the 10ms timers and figure you're getting time target
hits within 1% anyway.

delay now groks ICMP (in conjunction with the changes to libdivert).
No longer hangs in less-than-10ms-delay situations.
Added some help messages / usage messages.

libdivert.a and divert*.h over from the divert library directory.
So, before you try running 'make', do so! :)  Sorry - but it's really
just a proof-of-concept thing anyway.

the code for an itemization of the problems.