Questions wrt QoS code on Linux

Questions wrt QoS code on Linux

[Jonathan Day]

Hi,

Wondering if someone can answer a few questions on the
QoS code in Linux.

First off, I notice that all the code is lumped
together and much of it is generically labelled
"scheduling". I'm wondering if it might not be more
readable if the list were divided into four sections -
"queueing disciplines", "scheduling", "packet
classification" and "everything else". Would that seem
sensible? Or would it risk making things
over-structured?

Secondly, there seem to be an awful lot of QoS methods
not represented in Linux. Implementing them all might
easily double the kernel size for not very much
benefit, even if anyone could find the time to do so.
On the other hand, there are probably some that are
under development and others high on the wishlist.
Does anyone know what projects are currently underway
or being planned?

Jonathan


		
__________________________________ 
Do you Yahoo!? 
Yahoo! Mail - Helps protect you from nasty viruses. 
http://promotions.yahoo.com/new_mail

Re: Questions wrt QoS code on Linux

[Thomas Graf]

* Jonathan Day <20050512044040.61360.qmail@web31504.mail.mud.yahoo.com> 2005-05-11 21:40
> First off, I notice that all the code is lumped
> together and much of it is generically labelled
> "scheduling". I'm wondering if it might not be more
> readable if the list were divided into four sections -
> "queueing disciplines", "scheduling", "packet
> classification" and "everything else". Would that seem
> sensible? Or would it risk making things
> over-structured?

Sounds reasonable although I'm not sure if I understand
the difference between "scheduling" and "qdisc".

> Secondly, there seem to be an awful lot of QoS methods
> not represented in Linux. Implementing them all might
> easily double the kernel size for not very much
> benefit, even if anyone could find the time to do so.
> On the other hand, there are probably some that are
> under development and others high on the wishlist.
> Does anyone know what projects are currently underway
> or being planned?

We're lacking feedback on this subject from the users, we hear
a lot from the typical home user wanting to get some control
over his ADSL/cable link but not much from other areas.

There have been some recent additions, mainly Jamal's actions
and my small ematch API. They perfectly serve as a base to
solve more complex problems but are still in a early stage
of completness and documentation.

The current development direction is to get away from big and
complex problem solvers and focus on tiny and simple components
that can be put together to solve problems more individually.

Re: Questions wrt QoS code on Linux

[Jonathan Day]

I'll deal with the first part first, as it's the
easiest. :)

Very crudely, you can look at networking as being
carried out in two stages - collecing the packets to
be sent, and then sending them.

Something like CBQ tells the machine how to go about
collecting the packets, by creating a number of queues
into which the packets can be placed.

A distinct section of code for classifying packets is
used to help the collector to identify the different
types of packet so that the collector can handle them
correctly.

You've actually got another bit in there which
determines the ordering of the packets. a FIFO queue
won't be ordered the same as a PRIO queue, for
example.

A completely seperate stage is then needed to actually
gather the packets from the queue(s). You might drain
one queue completely before moving onto the next, you
might work in a round-robin manner, you might even
give a queue a fixed timeslice and grab as many
packets as possible within that slice before moving
on.

An additional section handles the case where the
network is overloaded. You can drop packets early, by
using systems like RED, BLUE, GREEN or BLACK. (Of
these, only RED and the variant GRED are in Linux at
the moment.)

At present, the Linux QoS menu is confusing. CBQ is
listed as a packet scheduler, when it in fact queues
the packets, rather than schedules them. RED is marked
as a queue, whereas it really filters, it doesn't
queue.

My proposal is to do the following:

1. Rename the sched directory to qos
2. Add a sched subdirectory and move the schedulers
into it
3. Add a queue subdirectory and move the queue
handlers into it
4. Add a classifier subdirectory and move the packet
classifiers into it
5. Add a processor subdirectory and move all code for
processing packets (such as RED) into it

Everything else would be left where it was. Help files
and menu syntax would be changed to reflect what the
option actually did. I would probably want to change
the symbols as well, to make it easier to follow in
the code as to what is happening.

--- Thomas Graf <tgraf@suug.ch> wrote:
> * Jonathan Day
>
<20050512044040.61360.qmail@web31504.mail.mud.yahoo.com>
> 2005-05-11 21:40
> > First off, I notice that all the code is lumped
> > together and much of it is generically labelled
> > "scheduling". I'm wondering if it might not be
> more
> > readable if the list were divided into four
> sections -
> > "queueing disciplines", "scheduling", "packet
> > classification" and "everything else". Would that
> seem
> > sensible? Or would it risk making things
> > over-structured?
> 
> Sounds reasonable although I'm not sure if I
> understand
> the difference between "scheduling" and "qdisc".



		
__________________________________ 
Yahoo! Mail Mobile 
Take Yahoo! Mail with you! Check email on your mobile phone. 
http://mobile.yahoo.com/learn/mail 

Re: Questions wrt QoS code on Linux

[Thomas Graf]

* Jonathan Day <20050512190721.17518.qmail@web31508.mail.mud.yahoo.com> 2005-05-12 12:07
> You've actually got another bit in there which
> determines the ordering of the packets. a FIFO queue
> won't be ordered the same as a PRIO queue, for
> example.

I don't see the point why we should draw a line between
something like PRIO and CBQ, I would agree that dsmark
should be splitted though.

> A completely seperate stage is then needed to actually
> gather the packets from the queue(s). You might drain
> one queue completely before moving onto the next, you
> might work in a round-robin manner, you might even
> give a queue a fixed timeslice and grab as many
> packets as possible within that slice before moving
> on.

a) The qdisc _must_ be able to define the ordering, otherwise
   we cannot do rate limiting correctly.

b) You definitely don't want reordering inside flows and the
   qdisc is the only player that is aware of the right ordering.
      
> An additional section handles the case where the
> network is overloaded. You can drop packets early, by
> using systems like RED, BLUE, GREEN or BLACK. (Of
> these, only RED and the variant GRED are in Linux at
> the moment.)

The current RED implementation uses a queue and its length
as criteria for the congestion probability. However, I do
agree that in theory this should be implemented differently,
the detection and marking should take place before the
queue possibly via actions. This would also easly allow for
(colored) TSW and EWMA rate estimators to be put in front.

Surely everyone can agree that there is potential in this
area and I hope someone brave stands up one day doing all
the work.

> At present, the Linux QoS menu is confusing. CBQ is
> listed as a packet scheduler, when it in fact queues
> the packets, rather than schedules them. RED is marked
> as a queue, whereas it really filters, it doesn't
> queue.

The menu really can be improved and I think such a patch
would get accepted, although please leave the qdiscs
alone for now. ;->

> 1. Rename the sched directory to qos

I don't see any improvement comming along with
change as well.

> 2. Add a sched subdirectory and move the schedulers
> into it
> 3. Add a queue subdirectory and move the queue
> handlers into it
> 4. Add a classifier subdirectory and move the packet
> classifiers into it
> 5. Add a processor subdirectory and move all code for
> processing packets (such as RED) into it

I think the (sch_|cls_|em_) prefixes are just fine
for now.