CBQ implementation issues on linux

CBQ implementation issues on linux

[ashwani kumar mehra]

Hi,

I'm currently looking at various CBQ implementation issues and 
have been comparing the ALTQ and the Linux approach in this 
regard. However I've been unable to fathom out as to how does 
Linux exactly address some of the CBQ requirements.

I've gone through the relevant portions of the code 
(sch_cbq.c;sch_generic.c;pkt_*.c, etc.) My current understanding 
is that the packet scheduler is invoked :

i) during packet enqueue (in 
dev_queue_xmit->queue_run->queue_restart
ii) on expiry of CBQ watchdog timers (thru raising a software 
interrupt from __netif_schedule in include/linux/netdevice.h).
iii) A late 1999 doc that i found on the web says the  dequeue 
code is also invoked via qdisc_run_queues (in sch_generic.c), thru 
a bottom half handler(net_bh). but am unable to locate it in the 
2.4.18 code. am i missing something obvious or has the same been 
reimplemented using tasklets/soft interrupts? maybe a call to 
qdisc_restart?

There are two issues
1. buffering at driver level: large buffering at driver level may 
negate the effect of the scheduler by delaying higher priority 
packets. ALTQ uses a token bucket regulator after the scheduler to 
counter this problem. however i've been unable to find something 
similar or any comment on this issue with regards to linux.

2. timer granularity issues: a driver will only interrupt after 
its buffer gets emptied. however the scheduler may be invoked in 
between by trigerring it on events like packet enqueue, expiry of 
watchdog timers, etc. In case of timer expiry events, the timer 
granularity remains 10 ms, so wont this lead to a bursty dequeue 
on the next timer tick?

Please CC any replies.

Thanx in advance
Ashwani
India
__________________________________________________________
Give your Company an email address like
ravi @ ravi-exports.com.  Sign up for Rediffmail Pro today!
Know more. http://www.rediffmailpro.com/signup/

Re: CBQ implementation issues on linux

[Werner Almesberger]

ashwani kumar mehra wrote:
> iii) A late 1999 doc that i found on the web says the  dequeue 
> code is also invoked via qdisc_run_queues (in sch_generic.c), thru 
> a bottom half handler(net_bh). but am unable to locate it in the 
> 2.4.18 code. am i missing something obvious or has the same been 
> reimplemented using tasklets/soft interrupts? maybe a call to 
> qdisc_restart?

This has changed a little. You may want to have a look at the
updated yet unfinished version of that ancient document:

ftp://icaftp.epfl.ch/pub/people/almesber/junk/tc-04FEB2001-0.tar.gz
(file tc/tc.ps)

Be warned that this "updated version" is for 2.4.0, so it's not
all that up to date anymore. But then, the traffic control code
hasn't changed very much in 2.4.

> 1. buffering at driver level: large buffering at driver level may 
> negate the effect of the scheduler by delaying higher priority 
> packets. ALTQ uses a token bucket regulator after the scheduler to 
> counter this problem. however i've been unable to find something 
> similar or any comment on this issue with regards to linux.

You could use something acting as a shaper (i.e. CBQ or HTB)
as the root qdisc, then cram all the other queuing inside it.

> 2. timer granularity issues: a driver will only interrupt after 
> its buffer gets emptied. however the scheduler may be invoked in 
> between by trigerring it on events like packet enqueue, expiry of 
> watchdog timers, etc. In case of timer expiry events, the timer 
> granularity remains 10 ms, so wont this lead to a bursty dequeue 
> on the next timer tick?

Yes, it does :-( Increasing HZ helps a little, and so do the
opportunistic checks (i.e. trying to dequeue whenever we're
handling an interrupt anyway). Unfortunately, the latter don't
improve worst-case burstiness, which is an issue if the next
network element in the path happens to be particularly picky.

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/