[LARTC] Scheduler Mechnisms!

[LARTC] Scheduler Mechnisms!

[Zhenyu Wu]

Hello,

Normally, in addition to such qdisc scheduler mechanisms as FIFO, PQ, WRR, WFQ,
are there any more? Then, there is a confusion on scheduler in Linux enviroment:
Assume there is a qdisc, such as RED as a leaf qdisc in a router, we know, if
there is packet which want to enqueue the packet, the Function red_enqueue is
called, but when the packet leave the queue(when the Function red_dequeue is
called)? I think it is meaningless when the pack leaves the queue just it enterred
it. Is there anything need to be done betweent the packet's enqueue and dequeue?

Best,


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

Re: [LARTC] Scheduler Mechnisms!

[Jonathan Day]

It depends on what you mean by "more". More for Linux?
Certainly. HTB3 seems to be a popular mechanism, and
you can use IMQ to set up an intermediate device to
allow shaping of both inbound and outbound traffic,
using one (or more!) scheduling mechanisms in series.

(In fact, there are several versions of IMQ out there.
I've given links to both the projects that seem to be
alive, but there may be more.)

There's also ESFQ, but there doesn't seem to be much
active work on that. There are forward ports to recent
Linux kernels, though. QLinux has a version of H-SFQ
for Linux, but again it seems to be getting long in
the tooth. Unfortunately, I can't find any forward
ports of that.

http://luxik.cdi.cz/~devik/qos/htb/
http://www.linuximq.net/
http://pupa.da.ru/imq/

http://www.digriz.org.uk/jdg-qos-script/#qos-2.6
http://kem.p.lodz.pl/~peter/qnet/
http://lass.cs.umass.edu/software/qlinux/

There are a great many systems that I can't find a
Linux version of. Cisco routers support something
called "Class-Based Weighted Fair Queueing" (CBWFQ)
which seems to be a hybrid of classful and classless
scheduling. Cisco also has two versions of ECN, for
forwards and backwards propogation.

I've listed below a number of papers detailing various
QoS schemes. Some of these have been implemented in
other OS' (the BSDs tend to get a lot of this stuff
implemented quickly for them as part of ALTQ) and some
I've never seen an implementation at all. However, the
papers should all give enough information to write a
version for Linux.

Note: ALTQ can be found at:
http://www.csl.sony.co.jp/person/kjc/kjc/software.html

Please note that this list is not exhaustive. Rather,
I got exhausted after trying to find what was out
there and what state it was currently in. QoS is a big
field, if the number of papers is anything to go by.
Linux only touches the fringes of it. If anyone feels
particularly bored, or in need of a good ego boost, it
would be cool to see if a reasonable selection of
these could be introduced into Linux over the 2.7
cycle.

EDF (Earliest Deadline First)
http://citeseer.ist.psu.edu/13919.html

BLUE (an alternative to RED)
http://citeseer.ist.psu.edu/feng99blue.html

AF PHB (Assured Forwarding Per-Hop Behaviour)
http://citeseer.ist.psu.edu/552302.html

SFB (Stochastic Fair Blue)
http://citeseer.ist.psu.edu/551253.html

GREEN (a pro-active variant on the theme of RED)
http://citeseer.ist.psu.edu/feng02green.html

SMART (Scalable Multipath Aggregated RouTing)
http://citeseer.ist.psu.edu/vutukury00smart.html

CSFQ (Core Stateless Fair Queueing)
http://citeseer.ist.psu.edu/391.html

StFQ (Start-Time Fair Queueing)
http://citeseer.ist.psu.edu/goyal96starttime.html

RFQ (Rainbow Fair Queueing)
http://citeseer.ist.psu.edu/cao00rainbow.html

PrFQ (Probabalistic Fair Queueing)
http://citeseer.ist.psu.edu/anker00prfq.html

ERR (Elastic Round Robin)
http://citeseer.ist.psu.edu/kanhere02fair.html

GFQ (Greedy Fair Queueing)
http://citeseer.ist.psu.edu/690207.html

PERR (Prioritized Elastic Round Robin)
http://citeseer.ist.psu.edu/681127.html

AOQ (Anchored Opportunity Queueing)
http://citeseer.ist.psu.edu/701742.html

BSFQ (Bin Sort Fair Queueing)
http://citeseer.ist.psu.edu/622188.html


As for the final question on what happens between
enqueue and dequeue, there are various diagrams out
there which show different aspects of how packets
traverse the system. I've included a few links to
those I could find:

http://open-source.arkoon.net/kernel/kernel_net.png
http://ebtables.sourceforge.net/br_fw_ia/PacketFlow.png
http://ebtables.sourceforge.net/br_fw_ia/br_fw_ia.html
http://www.docum.org/docum.org/kptd/

The last of these is the infamous Kernel Packet
Travelling Diagram. Most links to this that I've been
able to find are broken. It should be noted that the
diagrams all refer to the Linux 2.4 kernel. Linux 2.6
has quite a few QoS changes to it, but I'm unclear as
to whether they significantly alter any of the flows.

I hope this is of some use. Or, at the very least, is
an effective remedy to insomnia. :)

Jonathan

--- Zhenyu Wu <y030729@njupt.edu.cn> wrote:

> Hello,
> 
> Normally, in addition to such qdisc scheduler
> mechanisms as FIFO, PQ, WRR, WFQ,
> are there any more? Then, there is a confusion on
> scheduler in Linux enviroment:
> Assume there is a qdisc, such as RED as a leaf qdisc
> in a router, we know, if
> there is packet which want to enqueue the packet,
> the Function red_enqueue is
> called, but when the packet leave the queue(when the
> Function red_dequeue is
> called)? I think it is meaningless when the pack
> leaves the queue just it enterred
> it. Is there anything need to be done betweent the
> packet's enqueue and dequeue?
> 
> Best,
> 
> 
> _______________________________________________
> LARTC mailing list / LARTC@mailman.ds9a.nl
> http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO:
> http://lartc.org/
> 



		
__________________________________ 
Do you Yahoo!? 
Jazz up your holiday email with celebrity designs. Learn more. 
http://celebrity.mail.yahoo.com
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

Re: [LARTC] Scheduler Mechnisms!

[Zhenyu Wu]

Thank you very much, i will try to find these papers which must be very helpful
for me. The "more" means that whether there are other mechanisms not only for
Linux. Sorry, i have not make it clear! Sometimes, i wonder whether the qdiscs
such as CBQ, RED, GRED ... are belong to the scheduler mechanisms in linux
enviroment. For example, In Red, which i can find are enqueue, and dequeue.... so,
if i add a RED qidsc to a class, must i add a scheduler mechanism so that i can
decide which packet in the queues will be scheduled and put to the link?

Good luck,
Best,



>It depends on what you mean by "more". More for Linux?
> Certainly. HTB3 seems to be a popular mechanism, and
> you can use IMQ to set up an intermediate device to
> allow shaping of both inbound and outbound traffic,
> using one (or more!) scheduling mechanisms in series.
> 
> (In fact, there are several versions of IMQ out there.
> I've given links to both the projects that seem to be
> alive, but there may be more.)
> 
> There's also ESFQ, but there doesn't seem to be much
> active work on that. There are forward ports to recent
> Linux kernels, though. QLinux has a version of H-SFQ
> for Linux, but again it seems to be getting long in
> the tooth. Unfortunately, I can't find any forward
> ports of that.
> 
> http://luxik.cdi.cz/~devik/qos/htb/
> http://www.linuximq.net/
> http://pupa.da.ru/imq/
> 
> http://www.digriz.org.uk/jdg-qos-script/#qos-2.6
> http://kem.p.lodz.pl/~peter/qnet/
> http://lass.cs.umass.edu/software/qlinux/
> 
> There are a great many systems that I can't find a
> Linux version of. Cisco routers support something
> called "Class-Based Weighted Fair Queueing" (CBWFQ)
> which seems to be a hybrid of classful and classless
> scheduling. Cisco also has two versions of ECN, for
> forwards and backwards propogation.
> 
> I've listed below a number of papers detailing various
> QoS schemes. Some of these have been implemented in
> other OS' (the BSDs tend to get a lot of this stuff
> implemented quickly for them as part of ALTQ) and some
> I've never seen an implementation at all. However, the
> papers should all give enough information to write a
> version for Linux.
> 
> Note: ALTQ can be found at:
> http://www.csl.sony.co.jp/person/kjc/kjc/software.html
> 
> Please note that this list is not exhaustive. Rather,
> I got exhausted after trying to find what was out
> there and what state it was currently in. QoS is a big
> field, if the number of papers is anything to go by.
> Linux only touches the fringes of it. If anyone feels
> particularly bored, or in need of a good ego boost, it
> would be cool to see if a reasonable selection of
> these could be introduced into Linux over the 2.7
> cycle.
> 
> EDF (Earliest Deadline First)
> http://citeseer.ist.psu.edu/13919.html
> 
> BLUE (an alternative to RED)
> http://citeseer.ist.psu.edu/feng99blue.html
> 
> AF PHB (Assured Forwarding Per-Hop Behaviour)
> http://citeseer.ist.psu.edu/552302.html
> 
> SFB (Stochastic Fair Blue)
> http://citeseer.ist.psu.edu/551253.html
> 
> GREEN (a pro-active variant on the theme of RED)
> http://citeseer.ist.psu.edu/feng02green.html
> 
> SMART (Scalable Multipath Aggregated RouTing)
> http://citeseer.ist.psu.edu/vutukury00smart.html
> 
> CSFQ (Core Stateless Fair Queueing)
> http://citeseer.ist.psu.edu/391.html
> 
> StFQ (Start-Time Fair Queueing)
> http://citeseer.ist.psu.edu/goyal96starttime.html
> 
> RFQ (Rainbow Fair Queueing)
> http://citeseer.ist.psu.edu/cao00rainbow.html
> 
> PrFQ (Probabalistic Fair Queueing)
> http://citeseer.ist.psu.edu/anker00prfq.html
> 
> ERR (Elastic Round Robin)
> http://citeseer.ist.psu.edu/kanhere02fair.html
> 
> GFQ (Greedy Fair Queueing)
> http://citeseer.ist.psu.edu/690207.html
> 
> PERR (Prioritized Elastic Round Robin)
> http://citeseer.ist.psu.edu/681127.html
> 
> AOQ (Anchored Opportunity Queueing)
> http://citeseer.ist.psu.edu/701742.html
> 
> BSFQ (Bin Sort Fair Queueing)
> http://citeseer.ist.psu.edu/622188.html
> 
> 
> As for the final question on what happens between
> enqueue and dequeue, there are various diagrams out
> there which show different aspects of how packets
> traverse the system. I've included a few links to
> those I could find:
> 
> http://open-source.arkoon.net/kernel/kernel_net.png
> http://ebtables.sourceforge.net/br_fw_ia/PacketFlow.png
> http://ebtables.sourceforge.net/br_fw_ia/br_fw_ia.html
> http://www.docum.org/docum.org/kptd/
> 
> The last of these is the infamous Kernel Packet
> Travelling Diagram. Most links to this that I've been
> able to find are broken. It should be noted that the
> diagrams all refer to the Linux 2.4 kernel. Linux 2.6
> has quite a few QoS changes to it, but I'm unclear as
> to whether they significantly alter any of the flows.
> 
> I hope this is of some use. Or, at the very least, is
> an effective remedy to insomnia. :)
> 
> Jonathan
> 
> --- Zhenyu Wu <y030729@njupt.edu.cn> wrote:
> 
> > Hello,
> > 
> > Normally, in addition to such qdisc scheduler
> > mechanisms as FIFO, PQ, WRR, WFQ,
> > are there any more? Then, there is a confusion on
> > scheduler in Linux enviroment:
> > Assume there is a qdisc, such as RED as a leaf qdisc
> > in a router, we know, if
> > there is packet which want to enqueue the packet,
> > the Function red_enqueue is
> > called, but when the packet leave the queue(when the
> > Function red_dequeue is
> > called)? I think it is meaningless when the pack
> > leaves the queue just it enterred
> > it. Is there anything need to be done betweent the
> > packet's enqueue and dequeue?
> > 
> > Best,
> > 
> > 
> > _______________________________________________
> > LARTC mailing list / LARTC@mailman.ds9a.nl
> > http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO:
> > http://lartc.org/
> > 
> 
> 
> 
> 		
> __________________________________ 
> Do you Yahoo!? 
> Jazz up your holiday email with celebrity designs. Learn more. 
> http://celebrity.mail.yahoo.com
> 
>


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

Re: [LARTC] Scheduler Mechnisms!

[Jonathan Day]

I may be wrong on this, but I believe that RED can be
attached to any queueing system, including the basic
FIFO queues. In a sense, you're still using a
scheduling system, when using the default arrangement,
it's just a first-come, first-served one.

RED is classless and applies to the whole of a queue.
What that queue is attached to, if I understand it
correctly, isn't important. It can be a class, but it
can just as easily be everything going through that
device.

Again, someone correct me if I'm wrong, but as I
understand it, there are four levels to the whole
QoS/diffserv concept.

One of these levels is the queueing discipline. This
can be something like CBQ, WFQ, FIFO, PRIO, or
whatever. This is how the data is organized, it does
not describe how the data is sent. In the case of
something like CBQ, you have a defined set of queues
in parallel, with rules as to what packets fall into
what queue. On the other hand, queueing schemes such
as FIFO are flat. There's a single queue that
everything goes through, though there may be different
rules for how things get pushed to it.

Another level is the scheduling mechanism. This
describes how the data is sent, once organized, but
does not describe the organization itself. If you've
only one queue, then there's really not much to
schedule. If you've multiple queues, then it's fairly
normal to use "round robin" or "weighted round robin"
to pick which queue to pull a packet from. Linux' CBQ
uses "weighted round robin", according to the C file.

The next level is the packet dropping mechanism. When
queues flood, packets are going to be dropped. There's
nowhere to store them. I'm pretty sure the default
behaviour is to simply continue accepting packets, but
to drop any that expire before being sent or which
fall off the end of the queue (if the queue is
bounded). RED, GRED, and a whole host of similar
mechanisms, try to drop packets in a more controlled
manner. However, that is really all they do.

Finally, there are mechanisms for damping overly
active applications, such as ECN. The idea here is
that if you throttle back whatever is generating
excess traffic, you don't get the problems assoicated
with dealing with it. The "default" behaviour is to do
nothing.

When setting up QoS - on Linux or anything else - you
basically pick one of each of the four categories to
assemble a packet delivery system. Even without QoS,
you're doing that, you're just using the defaults in
all cases. The mechanisms are still going to be there.

The Linux configuration menu does NOT match the above
terminology, or the terminology in the source code.
Thus, the source code identifies CBQ as a queueing
discipline, but the configuration menu calls it a
scheduler. The QoS help is also not very helpful, as
it mostly tells people to look at the source. However,
if you look at the source for CBQ or RED, for example,
the explanation is relative to the cited papers, so
you then have to go and read those before coming back
and doing anything.

This is one area I hope is going to get resolved in
the reasonably near future. If not, I might have to
come up with a patch myself. The very thought of that
should send shivers down the spines of any kernel
developers out there.

Jonathan

--- Zhenyu Wu <y030729@njupt.edu.cn> wrote:

> Thank you very much, i will try to find these papers
> which must be very helpful
> for me. The "more" means that whether there are
> other mechanisms not only for
> Linux. Sorry, i have not make it clear! Sometimes, i
> wonder whether the qdiscs
> such as CBQ, RED, GRED ... are belong to the
> scheduler mechanisms in linux
> enviroment. For example, In Red, which i can find
> are enqueue, and dequeue.... so,
> if i add a RED qidsc to a class, must i add a
> scheduler mechanism so that i can
> decide which packet in the queues will be scheduled
> and put to the link?
> 
> Good luck,
> Best,



		
__________________________________ 
Do you Yahoo!? 
The all-new My Yahoo! - What will yours do?
http://my.yahoo.com 
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

Re: [LARTC] Scheduler Mechnisms!

[Zhenyu Wu]

Jonathan,

Yes, I think you are right, RED can be applied to any qdisc. The "RED" you
mentioned here is the RED algorithm, right? I know, in linux kernel (sch_red.c),
which implements the RED algotithm, just indeed uses a FIFO queue, do you think
so? So, if there are serveral RED qdiscs which attach to different classes, a
scheduling mechanism is needed, right?

If what i have said is right, it seems that there are no scheduler mechanisms for
serveral FIFO qdiscs(or RED qdiscs) in linux kernel. Of course, as we can see, CBQ
which can be regard as a scheduling queue also has a scheduler mechanisms WRR. But
if the FIFO is attached to the CBQ classes, then, when CBQ schedule different
queues(FIFOs) using WRR, will the packets in different queues are scheduled in
turn? In another condition, if i add a scheduling mechanism such as WRR behind all
FIFOs, i can use this mechnism to shedule the packets in different queues, are
there are any difference?

Thank you very much!
Regards,
Zhenyu Wu

>I may be wrong on this, but I believe that RED can be
> attached to any queueing system, including the basic
> FIFO queues. In a sense, you're still using a
> scheduling system, when using the default arrangement,
> it's just a first-come, first-served one.
> 
> RED is classless and applies to the whole of a queue.
> What that queue is attached to, if I understand it
> correctly, isn't important. It can be a class, but it
> can just as easily be everything going through that
> device.
> 
> Again, someone correct me if I'm wrong, but as I
> understand it, there are four levels to the whole
> QoS/diffserv concept.
> 
> One of these levels is the queueing discipline. This
> can be something like CBQ, WFQ, FIFO, PRIO, or
> whatever. This is how the data is organized, it does
> not describe how the data is sent. In the case of
> something like CBQ, you have a defined set of queues
> in parallel, with rules as to what packets fall into
> what queue. On the other hand, queueing schemes such
> as FIFO are flat. There's a single queue that
> everything goes through, though there may be different
> rules for how things get pushed to it.
> 
> Another level is the scheduling mechanism. This
> describes how the data is sent, once organized, but
> does not describe the organization itself. If you've
> only one queue, then there's really not much to
> schedule. If you've multiple queues, then it's fairly
> normal to use "round robin" or "weighted round robin"
> to pick which queue to pull a packet from. Linux' CBQ
> uses "weighted round robin", according to the C file.
> 
> The next level is the packet dropping mechanism. When
> queues flood, packets are going to be dropped. There's
> nowhere to store them. I'm pretty sure the default
> behaviour is to simply continue accepting packets, but
> to drop any that expire before being sent or which
> fall off the end of the queue (if the queue is
> bounded). RED, GRED, and a whole host of similar
> mechanisms, try to drop packets in a more controlled
> manner. However, that is really all they do.
> 
> Finally, there are mechanisms for damping overly
> active applications, such as ECN. The idea here is
> that if you throttle back whatever is generating
> excess traffic, you don't get the problems assoicated
> with dealing with it. The "default" behaviour is to do
> nothing.
> 
> When setting up QoS - on Linux or anything else - you
> basically pick one of each of the four categories to
> assemble a packet delivery system. Even without QoS,
> you're doing that, you're just using the defaults in
> all cases. The mechanisms are still going to be there.
> 
> The Linux configuration menu does NOT match the above
> terminology, or the terminology in the source code.
> Thus, the source code identifies CBQ as a queueing
> discipline, but the configuration menu calls it a
> scheduler. The QoS help is also not very helpful, as
> it mostly tells people to look at the source. However,
> if you look at the source for CBQ or RED, for example,
> the explanation is relative to the cited papers, so
> you then have to go and read those before coming back
> and doing anything.
> 
> This is one area I hope is going to get resolved in
> the reasonably near future. If not, I might have to
> come up with a patch myself. The very thought of that
> should send shivers down the spines of any kernel
> developers out there.
> 
> Jonathan
> 
> --- Zhenyu Wu <y030729@njupt.edu.cn> wrote:
> 
> > Thank you very much, i will try to find these papers
> > which must be very helpful
> > for me. The "more" means that whether there are
> > other mechanisms not only for
> > Linux. Sorry, i have not make it clear! Sometimes, i
> > wonder whether the qdiscs
> > such as CBQ, RED, GRED ... are belong to the
> > scheduler mechanisms in linux
> > enviroment. For example, In Red, which i can find
> > are enqueue, and dequeue.... so,
> > if i add a RED qidsc to a class, must i add a
> > scheduler mechanism so that i can
> > decide which packet in the queues will be scheduled
> > and put to the link?
> > 
> > Good luck,
> > Best,
> 
> 
> 
> 		
> __________________________________ 
> Do you Yahoo!? 
> The all-new My Yahoo! - What will yours do?
> http://my.yahoo.com 
>


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