[LARTC] Question on prio qdisc

[LARTC] Question on prio qdisc

[Cain, Joseph]

I have been doing some experiments with the 
prio qdisc. I haven't tried to understand the
code, but the behavior I have observed in the
experiments leads me to believe that the prio
qdisc operates in the following manner when the
interface queue is full:
1) Suppose that we are operating with the default
3 priority bands and the interface queue is full
of packets of the lowest priority (indicated by the
TOS byte).
2) Then suppose a new packet of highest priority is to be 
sent to the interface for queuing.
3) It appears to me that the newly arriving packet of 
highest priority will be dropped because the queue is
full. Prio does not appear to drop one of the lower priority
packets waiting in the queue to make room for the 
higher priority packet.

The evidence for this conclusion is that I can set the
"txqueuelen" to a large value to make ample room for 
queuing high priority packets. Then if the interface 
is sent a mixture of an overload of low priority
packets and a small load of high priority packets, the
high priority packet suffer just as high a packet loss
percentage as the low priority packets. To me this indicates
that they are getting dropped at the interface because the
queue is full.

Can anyone with knowledge of the code or more knowledge
of the proper operation of the prio qdisc verify that this
is indeed what is happening?

Also, the way I would really like prio to operate is that when
the queue is full, I want it not to drop a newly arriving packet
unless there are no lower priority packets waiting in the queue.
If there is a lower priority packets waiting in the queue, I would
like this packet to be dropped to make room for the higher priority packet.
Does anyone know if there is a version of prio that operates this way, or
if there is another qdisc that provides this capability?

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

Re: [LARTC] Question on prio qdisc

[Cheng Kwok Wing, William]

[-- Attachment #1: Type: text/plain, Size: 2842 bytes --]

Hi,
 
You can refer to http://lxr.linux.no/source/net/sched/sch_prio.c for the source code of prio qdisc.
 
If you look at the drop function of prio (prio_drop), it really drops packet with precedence of low to high priority. But when a incoming packet finds that there is no room in the queue, it's dropped without calling prio_drop function. The prio_drop will be called based on other condition that I can't remember.
 
If you want to achieve what you want, which is to drop packets with low priority first, I think you can attach a RED qdisc to low prioity queues and set the limit to drop packets before the queues are full.
 
I think my solution is worth trying.
 
Hope this helps,
Wing


"Cain, Joseph" <jcain01@harris.com> wrote:

I have been doing some experiments with the 
prio qdisc. I haven't tried to understand the
code, but the behavior I have observed in the
experiments leads me to believe that the prio
qdisc operates in the following manner when the
interface queue is full:
1) Suppose that we are operating with the default
3 priority bands and the interface queue is full
of packets of the lowest priority (indicated by the
TOS byte).
2) Then suppose a new packet of highest priority is to be 
sent to the interface for queuing.
3) It appears to me that the newly arriving packet of 
highest priority will be dropped because the queue is
full. Prio does not appear to drop one of the lower priority
packets waiting in the queue to make room for the 
higher priority packet.

The evidence for this conclusion is that I can set the
"txqueuelen" to a large value to make ample room for 
queuing high priority packets. Then if the interface 
is sent a mixture of an overload of low priority
packets and a small load of high priority packets, the
high priority packet suffer just as high a packet loss
percentage as the low priority packets. To me this indicates
that they are getting dropped at the interface because the
queue is full.

Can anyone with knowledge of the code or more knowledge
of the proper operation of the prio qdisc verify that this
is indeed what is happening?

Also, the way I would really like prio to operate is that when
the queue is full, I want it not to drop a newly arriving packet
unless there are no lower priority packets waiting in the queue.
If there is a lower priority packets waiting in the queue, I would
like this packet to be dropped to make room for the higher priority packet.
Does anyone know if there is a version of prio that operates this way, or
if there is another qdisc that provides this capability?

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


---------------------------------
Do you Yahoo!?
SBC Yahoo! DSL - Now only $29.95 per month!

[-- Attachment #2: Type: text/html, Size: 3445 bytes --]

Re: [LARTC] Question on prio qdisc

[Lars Landmark]

On Wed, 2 Jul 2003, Cain, Joseph wrote:

> 
> I have been doing some experiments with the 
> prio qdisc. I haven't tried to understand the
> code, but the behavior I have observed in the
> experiments leads me to believe that the prio
> qdisc operates in the following manner when the
> interface queue is full:
> 1) Suppose that we are operating with the default
> 3 priority bands and the interface queue is full
> of packets of the lowest priority (indicated by the
> TOS byte).
> 2) Then suppose a new packet of highest priority is to be 
> sent to the interface for queuing.
> 3) It appears to me that the newly arriving packet of 
> highest priority will be dropped because the queue is
> full. Prio does not appear to drop one of the lower priority
> packets waiting in the queue to make room for the 
> higher priority packet.
> 
> The evidence for this conclusion is that I can set the
> "txqueuelen" to a large value to make ample room for 
> queuing high priority packets. Then if the interface 
> is sent a mixture of an overload of low priority
> packets and a small load of high priority packets, the
> high priority packet suffer just as high a packet loss
> percentage as the low priority packets. To me this indicates
> that they are getting dropped at the interface because the
> queue is full.

In prio_init(), a FIFO queue is establish for each of these 
three bands.  I thought that each of these FIFO queues could occupy 
txqueuelen packages.  According to you, this is not true.  however if your 
assumption is right, and you want to achieve dropping low priority package 
if high priority package is entering, then you could just make a small 
extension to the prio_enqueue code in linux/net/sched/sch_prio.c.   

Class/band 0 has highest priority. If you unsuccessfully try to enqueue a 
package to this class, you could make a call to prio_drop(). 
This function drop the package from lowest priority class, that has a package.
When returning from this function, there should be enough place to your high 
priority package.  Try now to enqueue this package once more, 
and you should be done.  Hopefully this will work. But it will work only if 
Linux only count packages and do not count how many bytes each of these 
FIFO queue holds.


Lars

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

RE: [LARTC] Question on prio qdisc

[Cain, Joseph]

Thank you Lars and Wing for your responses.

I just ran another experiment using RED on the
lowest priority flow as suggested by Wing. I had
used RED before (on all flows) without success.
In this experiment, specified a large queue size for the interface.
In this case the result was roughly the same.
I overloaded the interface with 9.5 Mb/s of 
flow with 8 Mb/s at the lowest priority, 1 Mb/s
at the medium priority, and 0.5 Mb/s at the highest
priority hoping that RED would discard lowest
priority packets to make room for the higher priority
packets. The result was that all flows suffered
approximately the same packet loss rate (about 45%).
The interface was an 802.11b interface at 11 Mb/s
with the two nodes very close to each other so that
link quality was very high. Apparently RED does not
discard the lowest priority packets that are overloading
the interface. The following script was
used:

#############
tc qdisc add dev wlan0 root handle 1: prio
tc qdisc add dev wlan0 parent 1:3 handle 30: red min 4000 max 8000 burst 5 limit
18000 avpkt 1000 probability 0.2

ifconfig wlan0 txqueuelen 10000
###############################

My next step will be to modify the enqueue function to call
prio_drop() if there is not enough room to enqueue a new
packet as you have both suggested. I will have to get some help
for this from some of our engineers that can understand the code
better than I could.

Thanks for the help!

Bibb Cain







-----Original Message-----
From: Lars Landmark [mailto:larslan@solan.zapto.org]
Sent: Wednesday, July 02, 2003 12:42 PM
To: Cain, Joseph
Cc: lartc
Subject: Re: [LARTC] Question on prio qdisc


On Wed, 2 Jul 2003, Cain, Joseph wrote:

> 
> I have been doing some experiments with the 
> prio qdisc. I haven't tried to understand the
> code, but the behavior I have observed in the
> experiments leads me to believe that the prio
> qdisc operates in the following manner when the
> interface queue is full:
> 1) Suppose that we are operating with the default
> 3 priority bands and the interface queue is full
> of packets of the lowest priority (indicated by the
> TOS byte).
> 2) Then suppose a new packet of highest priority is to be 
> sent to the interface for queuing.
> 3) It appears to me that the newly arriving packet of 
> highest priority will be dropped because the queue is
> full. Prio does not appear to drop one of the lower priority
> packets waiting in the queue to make room for the 
> higher priority packet.
> 
> The evidence for this conclusion is that I can set the
> "txqueuelen" to a large value to make ample room for 
> queuing high priority packets. Then if the interface 
> is sent a mixture of an overload of low priority
> packets and a small load of high priority packets, the
> high priority packet suffer just as high a packet loss
> percentage as the low priority packets. To me this indicates
> that they are getting dropped at the interface because the
> queue is full.

In prio_init(), a FIFO queue is establish for each of these 
three bands.  I thought that each of these FIFO queues could occupy 
txqueuelen packages.  According to you, this is not true.  however if your 
assumption is right, and you want to achieve dropping low priority package 
if high priority package is entering, then you could just make a small 
extension to the prio_enqueue code in linux/net/sched/sch_prio.c.   

Class/band 0 has highest priority. If you unsuccessfully try to enqueue a 
package to this class, you could make a call to prio_drop(). 
This function drop the package from lowest priority class, that has a package.
When returning from this function, there should be enough place to your high 
priority package.  Try now to enqueue this package once more, 
and you should be done.  Hopefully this will work. But it will work only if 
Linux only count packages and do not count how many bytes each of these 
FIFO queue holds.


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

RE: [LARTC] Question on prio qdisc

[Leonardo Balliache]

Hi, Joseph:

At 06:45 a.m. 03/07/03 +0200, you wrote:

>Thank you Lars and Wing for your responses.
>
>I just ran another experiment using RED on the
>lowest priority flow as suggested by Wing. I had
>used RED before (on all flows) without success.
>In this experiment, specified a large queue size for the interface.
>In this case the result was roughly the same.
>I overloaded the interface with 9.5 Mb/s of
>flow with 8 Mb/s at the lowest priority, 1 Mb/s
>at the medium priority, and 0.5 Mb/s at the highest
>priority hoping that RED would discard lowest
>priority packets to make room for the higher priority
>packets. The result was that all flows suffered
>approximately the same packet loss rate (about 45%).
>The interface was an 802.11b interface at 11 Mb/s
>with the two nodes very close to each other so that
>link quality was very high. Apparently RED does not
>discard the lowest priority packets that are overloading
>the interface. The following script was
>used:

RED doesn´t have any way to know which are lower, medium or higher priority 
packets. To do what you want you need to use GRED.

>My next step will be to modify the enqueue function to call
>prio_drop() if there is not enough room to enqueue a new
>packet as you have both suggested. I will have to get some help
>for this from some of our engineers that can understand the code
>better than I could.

The enqueue code is here:

static int
prio_enqueue(struct sk_buff *skb, struct Qdisc* sch)
{
    struct prio_sched_data *q = (struct prio_sched_data *)sch->data;
    struct Qdisc *qdisc;
    int ret;

    qdisc = q->queues[prio_classify(skb, sch)];

    if ((ret = qdisc->enqueue(skb, qdisc)) = 0) {
        sch->stats.bytes += skb->len;
        sch->stats.packets++;
        sch->q.qlen++;
        return 0;
     }
     sch->stats.drops++;
     return ret;
}

As you see in:

         qdisc = q->queues[prio_classify(skb, sch)];

each queue is an independent queue. Then if high priority packets are 
dropped is because the high priority queue has overflow, not because some 
(unique?) queue is full from low priority packets.

Also, in drop-tail queues, as its name imply and prio is, never a already 
enqueue packet is dropped to make room for a new one. Packets are dropped 
from the tail.

Best regards,

Leonardo Balliache




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

RE: [LARTC] Question on prio qdisc

[Cain, Joseph]

Hi Leonardo:

Thank you for the reply to my question>
See comments below.

Bibb Cain


-----Original Message-----
From: Leonardo Balliache [mailto:leoball@opalsoft.net]
Sent: Monday, July 07, 2003 2:08 PM
To: Cain Joseph
Cc: lartc@mailman.ds9a.nl
Subject: RE: [LARTC] Question on prio qdisc


Hi, Joseph:

At 06:45 a.m. 03/07/03 +0200, you wrote:

>Thank you Lars and Wing for your responses.
>
>I just ran another experiment using RED on the
>lowest priority flow as suggested by Wing. I had
>used RED before (on all flows) without success.
>In this experiment, specified a large queue size for the interface.
>In this case the result was roughly the same.
>I overloaded the interface with 9.5 Mb/s of
>flow with 8 Mb/s at the lowest priority, 1 Mb/s
>at the medium priority, and 0.5 Mb/s at the highest
>priority hoping that RED would discard lowest
>priority packets to make room for the higher priority
>packets. The result was that all flows suffered
>approximately the same packet loss rate (about 45%).
>The interface was an 802.11b interface at 11 Mb/s
>with the two nodes very close to each other so that
>link quality was very high. Apparently RED does not
>discard the lowest priority packets that are overloading
>the interface. The following script was
>used:

RED doesn´t have any way to know which are lower, medium or higher priority 
packets. To do what you want you need to use GRED.


*******************************************************
Thanks. I will take a look at GRED.
*****************************************************


>My next step will be to modify the enqueue function to call
>prio_drop() if there is not enough room to enqueue a new
>packet as you have both suggested. I will have to get some help
>for this from some of our engineers that can understand the code
>better than I could.

The enqueue code is here:

static int
prio_enqueue(struct sk_buff *skb, struct Qdisc* sch)
{
    struct prio_sched_data *q = (struct prio_sched_data *)sch->data;
    struct Qdisc *qdisc;
    int ret;

    qdisc = q->queues[prio_classify(skb, sch)];

    if ((ret = qdisc->enqueue(skb, qdisc)) = 0) {
        sch->stats.bytes += skb->len;
        sch->stats.packets++;
        sch->q.qlen++;
        return 0;
     }
     sch->stats.drops++;
     return ret;
}

As you see in:

         qdisc = q->queues[prio_classify(skb, sch)];

each queue is an independent queue. Then if high priority packets are 
dropped is because the high priority queue has overflow, not because some 
(unique?) queue is full from low priority packets.

*****************************************
I understand your point, but I have tried to determine
the answers to a couple of questions from the code
without success (I don't understand the source code
well enough). Maybe you could answer these:
1) If I specify a queue length for the interface
by configuring "txqueuelen" to some number (say 1000), then
does that mean that the 3 FIFO queues for the 3 bands
in either "prio" scheduler or the default "pfifo_fast" scheduler are set each
to a size of 1000 packets? If this is the case, then I don't
see how my high priority queue can drop packets when the high
priority flow rate is well below what the link can support.
Can you think of any reason this should happen?
2) My testing leads me to believe that there are 3 queues,
but the buffer allocated for a new packet enqueued to
any of the queues is allocated from a common pool of buffers
that might be of size equal to "txqueuelen" = 1000. Is it
possible that it is implemented this way? I could see
high priority packets being dropped if this was the
implementation?
******************************************


Also, in drop-tail queues, as its name imply and prio is, never a already 
enqueue packet is dropped to make room for a new one. Packets are dropped 
from the tail.

Best regards,

Leonardo Balliache



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

RE: [LARTC] Question on prio qdisc

[Leonardo Balliache]

Hi, Lars:

At 10:10 a.m. 08/07/03 +0200, you wrote:

> >
> > each queue is an independent queue. Then if high priority packets are
> > dropped is because the high priority queue has overflow, not because some
> > (unique?) queue is full from low priority packets.
>
>I am little confused.  If typed ifconfig, we can see "txqueuelen:100".
>Will this imply that all three bands hold by prio are sharing this 100
>packages capacity, or can each of these three bands each occupy 100
>packages in its buffer.  In the latter, this means prio can maximum occupy
>300 packages...
>
>This problem will also imply HTB and other schedulers..
>
>
>Regards
>
>Lars Landmark

I'm not very sure if the total queue length is 100 or 300 because I was
searching the code and I can't find any information that tell me what the
real length is.

Because "ip link" shows me that qlen is 100, I have to suppose that total
length is 100.

But anyway, PRIO queing discipline principle calls that each priority queue
is independent, then we can't have the prio 0 queue full of prio 1 or 2
packets (being the filters working well). It goes against the PRIO queuing
discipline principle.

In "Differentiated Service on Linux HOWTO" (work in progress) I present
a PRIO queuing discipline explanation using some documentation taken
from Juniper Networks. Have a look at http://opalsoft.net/qos.

Also if you read about Cisco PQ the principle is identical. If we don't
respect the principle, then the queue can be any sort of queue, but
certainly, not a PRIO queue. Then it´s not posible to ask on PRIO for something
that drops an already enqueue packet to make run for a new arriving one.

I suggest that configurations and tests made to reach that conclusions were 
revised.

Best regards,

Leonardo Balliache





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

RE: [LARTC] Question on prio qdisc

[Leonardo Balliache]

Hi, Joseph:

At 03:31 p.m. 08/07/03 -0400, you wrote:

>I understand your point, but I have tried to determine
>the answers to a couple of questions from the code
>without success (I don't understand the source code
>well enough). Maybe you could answer these:
>1) If I specify a queue length for the interface
>by configuring "txqueuelen" to some number (say 1000), then
>does that mean that the 3 FIFO queues for the 3 bands
>in either "prio" scheduler or the default "pfifo_fast" scheduler are set each
>to a size of 1000 packets? If this is the case, then I don't
>see how my high priority queue can drop packets when the high
>priority flow rate is well below what the link can support.
>Can you think of any reason this should happen?

Have a look to a previous e-mail I answered to Lars. Reason? What´s the 
entering rate? What's the departing rate? The queue will be filled to a 
rate defined by the difference between those rates.

>2) My testing leads me to believe that there are 3 queues,
>but the buffer allocated for a new packet enqueued to
>any of the queues is allocated from a common pool of buffers
>that might be of size equal to "txqueuelen" = 1000. Is it
>possible that it is implemented this way? I could see
>high priority packets being dropped if this was the
>implementation?
>******************************************

No, again, have a look to a previous e-mail I sent to Lars.

Best regards,

Leonardo Balliache

Here you have a copy of Lars' e-mail:

I'm not very sure if the total queue length is 100 or 300 because I was
searching the code and I can't find any information that tell me what the
real length is.

Because "ip link" shows me that qlen is 100, I have to suppose that total
length is 100.

But anyway, PRIO queing discipline principle calls that each priority queue
is independent, then we can't have the prio 0 queue full of prio 1 or 2
packets (being the filters working well). It goes against the PRIO queuing
discipline principle.

In "Differentiated Service on Linux HOWTO" (work in progress) I present
a PRIO queuing discipline explanation using some documentation taken
from Juniper Networks. Have a look at http://opalsoft.net/qos.

Also if you read about Cisco PQ the principle is identical. If we don't
respect the principle, then the queue can be any sort of queue, but
certainly, not a PRIO queue. Then it´s not posible to ask on PRIO for something
that drops an already enqueue packet to make run for a new arriving one.

I suggest that configurations and tests made to reach that conclusions were 
revised.



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