Re: [LARTC] CBQ virtual clock

[bert hubert <ahu@ds9a.nl>]

On Fri, Dec 14, 2001 at 06:07:28PM -0500, Michael T. Babcock wrote:
> On Sat, Dec 15, 2001 at 12:00:18AM +0100, bert hubert wrote:
> > Oh, I've been exploring how the 'virtual clock' works in the Linux CBQ
> > implementation, it turns out that you can misconfigure it quite badly and
> > still get *statistically* accurate shaping. I'm still figuring out the
> > effects at short timescales of misconfiguring bandwidth.
> 
> Please post your observations as you come across them so we can also test
> them and see what's going on faster together.

The theory is like this. CBQ wants to know the idle time of the interface,
which would work like this.

Enqueue a packet
Enqueue a packet
Enqueue a packet
	Packet is dequeued to the interface
	interface busy sending packet
	interface notifies us that the packet was sent
	CBQ notes how much time has passed, and uses this for avgidle
		calculations
	Packet is dequeued to the interface
	process repeats.

Ok - now, this is not how it works in Unix, or at least, in Linux. In fact
it goes like this:

Enqueue a packet to the queue
	Dequeue all packets from the queue, give to the network interface
Enqueue a packet to the queue
	Dequeue all packets from the queue, give to the network interface
Enqueue a packet to the queue
	Dequeue all packets from the queue, give to the network interface
...
Enqueue a packet to the queue
	Network interface is fed up, will notice us when there is room again
	......
Enqueue a packet to the queue
Enqueue a packet to the queue
Enqueue a packet to the queue
Enqueue a packet to the queue
	Network interface tells us that there is room
	dequeue
	dequeue
	dequeue
	dequeue

Now - we don't now really *know* when the network interface was done
sending. So, what 'Alexey CBQ' does is to guesstimate how long the interface
would be busy, and move the clock ahead to the point where the interface
would be idle after sending a packet.

So it works like this:

Enqueue a packet
	Dequeue a packet, store how big it was
Enqueue a packet
	Calculate how long the previous packet will take to transmit.
	Calculate how much time has actually passed
	Move 'now' ahead by the maximum of the above two.

Ok, what does this mean.

Sending packets would look like this:

|
|
|-----+            +-+     +--- etc
|     |            | |     |
|     |            | |     |
|     |------------| |-----|
+-------------------------------------------------------
1     2            3 4     5


At moment 1, a packet starts to be send. At point 2, the packet is done
sending. CBQ knows that the packet was 10000 bits long. Say we want to shape
to 100kbit/s, then time time that should elapse between point 3, where we
start sending the next packet, and point 1 where we started sending the
first one, is 0.1 second.

In an ideal world, the next dequeue request comes directly when the network
device is done sending, at moment two. But it doesn't, it comes immediately.

However, the kernel can *calculate* when 2 should occur by dividing the size
of the packet by the actual bandwidth of the device. CBQ then shifts the
virtual time to point 2, and bases all calculations on that.

This is why CBQ needs to know the bandwidth of your link. Now, if the
you set the bandwidth of your link higher than it is in reality, CBQ will
mess up its avgidle calculations.

It appears that 'overlimit' is then still shaped at the proper rate, but
link sharing may be done wrong. This is what I'm investigating now.

The above may not make much sense, but perhaps you can make something of it
:-)

Regards,

bert

-- 
http://www.PowerDNS.com          Versatile DNS Software & Services
Trilab                                 The Technology People
Netherlabs BV / Rent-a-Nerd.nl           - Nerd Available -
'SYN! .. SYN|ACK! .. ACK!' - the mating call of the internet

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/