in-driver QoS

in-driver QoS

[Vladimir Kondratiev]

I'd like to discuss issue with QoS.

In 802.11 network, there is TGe (or 802.11e), working group, developing QoS 
extensions for 802.11. This group's work is close to finish. Current draft 
should be very close to the final standard.

Currently, according to TGe, NIC will support 4 different priorities (or 
access categories). Let's say, 4 distinct Tx queues will be supported by NIC. 
Each Tx queue have its own parameters.

In addition, there are separate streams (TSPEC's) that should be requested, 
i.e. before use, some initiation procedure should be performed. Sure, there 
is tear down for TSPEC as well.

Roughly, 4 access categories corresponds to diffserv, while TSPEC's - to 
intserv.

Now, question is: how will we support these QoS features in network stack?

Let's start from diffserv, it is easier.

skb->priority help determining Tx queue, but fundamental problem is with 
single Tx queue from network stack. Any smart queuing/scheduling etc. made by 
driver, will render useless while network stack provides single Tx queue.

Any ideas how to modify stack to support multiple Tx queues?

Vladimir

Re: in-driver QoS

[Andi Kleen]

> Any ideas how to modify stack to support multiple Tx queues?

It already has that kind of in the form of arbitary qdiscs. The trick
will be only to do all queueing in the qdisc and keep the hardware
queue length as small as possible. I think today's drivers can
do that already by just plugging the queue most of the time,
unless they really want a packet.

Disadvantage will be more use of CPU time to refill driver
queues, but at the relatively slow WLAN speeds that shouldn't 
be a big issue.

BTW the standard qdisc pfifo_fast already has three queues,
selected by the old TOS.  That may even be good enough for you
already. Users can fine tune it by using firewall rules
that change the TOS for specific protocols etc.

-Andi

Re: in-driver QoS

[Vladimir Kondratiev]

How could I use these multiple qdiscs? If I use existing driver framework, I 
have hard_start_xmit, that represent single queue. Do you have any examples 
how driver can access qdiscs directly? I.e. I have 4 queues in the driver, I 
want to fill it separately, start/stop incoming queues from stack etc.

Note also, we are talking about 100Mbps above MAC, which translates to about 
150 Mbps, within next 2 years. 100Mbps above MAC is criteria for TGn working 
group in IEEE (high throughput).

Vladimir.

On Monday 07 June 2004 17:00, Andi Kleen wrote:
> > Any ideas how to modify stack to support multiple Tx queues?
>
> It already has that kind of in the form of arbitary qdiscs. The trick
> will be only to do all queueing in the qdisc and keep the hardware
> queue length as small as possible. I think today's drivers can
> do that already by just plugging the queue most of the time,
> unless they really want a packet.
>
> Disadvantage will be more use of CPU time to refill driver
> queues, but at the relatively slow WLAN speeds that shouldn't
> be a big issue.
>
> BTW the standard qdisc pfifo_fast already has three queues,
> selected by the old TOS.  That may even be good enough for you
> already. Users can fine tune it by using firewall rules
> that change the TOS for specific protocols etc.
>
> -Andi

Re: in-driver QoS

[Andi Kleen]

On Mon, 7 Jun 2004 23:35:04 +0300
Vladimir Kondratiev <vkondra@mail.ru> wrote:

> How could I use these multiple qdiscs? If I use existing driver framework, I 
> have hard_start_xmit, that represent single queue. Do you have any examples 
> how driver can access qdiscs directly? I.e. I have 4 queues in the driver, I 
> want to fill it separately, start/stop incoming queues from stack etc.

Normally it would be configured by the user tools (using tc) 


-Andi

Re: in-driver QoS

[jamal]

On Mon, 2004-06-07 at 16:35, Vladimir Kondratiev wrote:
> How could I use these multiple qdiscs? If I use existing driver framework, I 
> have hard_start_xmit, that represent single queue. Do you have any examples 
> how driver can access qdiscs directly? I.e. I have 4 queues in the driver, I 
> want to fill it separately, start/stop incoming queues from stack etc.

Maybe you can explain a little more: Do these 4 queues translate to 4
DMA rings or channles on the NIC? Could you not use a tag like fwmark to
select DMA to send to? 
Explain the packet path once it hits the driver.

> Note also, we are talking about 100Mbps above MAC, which translates to about 
> 150 Mbps, within next 2 years. 100Mbps above MAC is criteria for TGn working 
> group in IEEE (high throughput).

Are these wireless NICs? Whats the big deal about 150Mbps?

cheers,
jamal

Re: in-driver QoS

[Vladimir Kondratiev]

On Tuesday 08 June 2004 02:38, jamal wrote:
> On Mon, 2004-06-07 at 16:35, Vladimir Kondratiev wrote:
> > How could I use these multiple qdiscs? If I use existing driver
> > framework, I have hard_start_xmit, that represent single queue. Do you
> > have any examples how driver can access qdiscs directly? I.e. I have 4
> > queues in the driver, I want to fill it separately, start/stop incoming
> > queues from stack etc.
>
> Maybe you can explain a little more: Do these 4 queues translate to 4
Exactly
> DMA rings or channles on the NIC? Could you not use a tag like fwmark to
> select DMA to send to?
> Explain the packet path once it hits the driver.
Let's put aside integrated service. For diff serv,
NIC have 4 DMA queues. These 4 queues acts as 4 independent 802.11 channels 
with different backoff and contention window parameters. Actually, it is 
dictated by TGe, and should be common for wireless stack. Queue consumption 
depends on conditions on air and access point settings. Access point set 
these different parameters for queues, and may change it time to time.

I think it would be not good to rely on 'tc' to provide proper mix of packets. 
Meanwhile, it is what I use, but it is not proper solution.
>
> > Note also, we are talking about 100Mbps above MAC, which translates to
> > about 150 Mbps, within next 2 years. 100Mbps above MAC is criteria for
> > TGn working group in IEEE (high throughput).
>
> Are these wireless NICs? Whats the big deal about 150Mbps?
Nothing special, but Andi mentioned that ...
> Disadvantage will be more use of CPU time to refill driver
> queues, but at the relatively slow WLAN speeds that shouldn't 
> be a big issue.
... and I want to note that it is not very slow network.

Vladimir.

Re: in-driver QoS

[jamal]

On Tue, 2004-06-08 at 01:41, Vladimir Kondratiev wrote:

> > DMA rings or channles on the NIC? Could you not use a tag like fwmark to
> > select DMA to send to?
> > Explain the packet path once it hits the driver.
>
> Let's put aside integrated service. For diff serv,
> NIC have 4 DMA queues. These 4 queues acts as 4 independent 802.11 channels 
> with different backoff and contention window parameters. Actually, it is 
> dictated by TGe, and should be common for wireless stack. Queue consumption 
> depends on conditions on air and access point settings. Access point set 
> these different parameters for queues, and may change it time to time.

Ok, Now that you explain this i dont think other people understood you
when you started talking about qos. We have discussed this topic on
netdev before under differnt context.

So the 4 DMA queues are infact different QoS levels? Another way to use
multiple tx DMA channels is to parallelize sending. Are there multiple
receive channels as well?
BTW, what is TGe?

The only obstacle i see at the moment in the architecture is we stop the
transmit path if a DMA ring is full. That is making assumption there is
only one DMA path. To work around this you could have 4 independent
virtual netdevices on top of the real physical device - something like a
tamed down bonding driver; this is not a very good abstraction because
there is only one physical MAC. 
Another scheme is to mark the fwmark or priority with the right DMA path
selection. Once it gets to the driver you try to send to the correct
ring and if thats full, you go to the next lower priority ring etc and
when theres no more DMA paths left you drop. The disadvantage with such
a scheme is complexity in keeping track of busy DMA paths.

I am trying to think of a clean way - maybe i need to get some caffeine
first. Jeff? Andi?

cheers,
jamal

Re: in-driver QoS

[Jean Tourrilhes]

Vladimir Kondratiev wrote :
> 
> In 802.11 network, there is TGe (or 802.11e), working group, developing QoS 
> extensions for 802.11.

	802.11e is about prioritisation of the traffic, not QoS. QoS
is about bandwidth reservation and enforcement of policies, and
802.11e does none of that.

> Now, question is: how will we support these QoS features in network stack?

	Simple : Linux driver should always send traffic at the
highest priority, and never use the lowest priority. This way, we are
guaranteed to always get the highest performance, and get higher
benchmarks than Win32 or other OSes.

> skb->priority help determining Tx queue, but fundamental problem is with 
> single Tx queue from network stack.

	Andi already corrected you about the fact that the net layer
can offer multiple queue. If you look in .../net/sched/, you will see
that skb->priority is used intensively, even for the generic
scheduler. Most often, skb->priority is derived from sk->sk_priority,
which is the socket priority.

Andi Kleen wrote :
> It already has that kind of in the form of arbitary qdiscs. The trick
> will be only to do all queueing in the qdisc and keep the hardware
> queue length as small as possible.

	I fully agree with that statement. One of the advantage of TC
is that it enforces policies, which is more like real QoS.
	Note that the netdev queue is potentially larger than the
hardware queue, especially with the recent increase due to Gigabit
Ethernet, so there is more gain to be expected scheduling the netdev
queue than the hardware queue in case of congestion.

> Disadvantage will be more use of CPU time to refill driver
> queues.

	More precisely, you increase the Tx-done interrupt frequency,
so the number of context switches. The time to refill the queues
remain the same. But, interrupt mitigation seems like a good thing in
general.

> BTW the standard qdisc pfifo_fast already has three queues,
> selected by the old TOS.

	TOS is part of the IP header, and you don't want to read IP
headers in the link layer, it's a clear layer violation. I think using
skb->priority is a better way.

Vladimir Kondratiev wrote :
> 
> How could I use these multiple qdiscs?

	You need to enable "advanced router" in ***config and check
pointers in this excellent howto :
		http://linux-ip.net/html/index.html
		(see section I.1.12)

> I.e. I have 4 queues in the driver, I want to fill it separately,
> start/stop incoming queues from stack etc.

	The driver is not the one deciding the policy, the network
stack is. Therefore the driver accept whatever packet the network
scheduler decide to give it and store it in the most appropriate
queue (based on some meta-information such as skb->priority).
	This way the behavior of the driver is simple and predictable,
you don't need to implement intserv/diffserv in the driver, and you
can easily plug any scheduling you decide on top of it by
reconfiguring the network stack.

	Have fun...

	Jean

Re: in-driver QoS

[Jean Tourrilhes]

On Tue, Jun 08, 2004 at 03:18:37PM -0400, jamal wrote:
> On Tue, 2004-06-08 at 14:48, Jean Tourrilhes wrote:
> > Vladimir Kondratiev wrote :
> > > 
> > > In 802.11 network, there is TGe (or 802.11e), working group, developing QoS 
> > > extensions for 802.11.
> > 
> > 	802.11e is about prioritisation of the traffic, not QoS. QoS
> > is about bandwidth reservation and enforcement of policies, and
> > 802.11e does none of that.
> 
> Prioritization is a subset of QoS. So if 802.11e talks prioritization,
> thats precisely what it means - QoS.

	Yes, it's one component of a QoS solution. But, my point is
that on it's own, it's not enough.
	This means that we should not see 802.11e as a complete QoS
solution, and the center of the QoS universe, but only as a mechanism
that need to be integrated in the QoS solution. Which means, instead
of trying to fit TC in 802.11e, we need to fit 802.11e in TC. That's a
totally different perspective.

> The guy has some valid points in terms of multiple DMA rings if i
> understood him correctly. Theres current architectural deficiencies.

	I don't buy that. The multiple DMA ring is not the main thing
here, all DMA transfer share the same I/O bus to the card and share
the same memory pool, so there is no real performance gain there. The
I/O bnandwidth to the card is vastly superior to the medium bandwidth,
so the DMA process will never be a bottleneck.
	The real benefit is that the contention on the medium is
prioritised (between contenting nodes). The contention process (CSMA,
backoff, and all the jazz) will give a preference to stations with
packet of the highest priority compared to stations wanting to send
packet of lower priorities. To gain advantage of that, you only need
to assign your packet the right priority at the driver level, and the
CSMA will send it appropriately.
	With respect to the 4 different hardware queue, you should see
them only as an extension of the netdev queues. Basically, you just
have a pipeline between the scheduler and the MAC which is almost a
FIFO, but not exactly a FIFO. Those queues may do packet reordering
between themselves, based on priorities. But at the end of the day
they are only going to send what the scheduler is feeding them, and
every packet the scheduler pass to those queues is eventually sent, so
they are totally slave to the scheduler.
	So, I would not worry about the DMA rings. I may worry a
little bit about packet reordering between queues, but I don't think
it's a problem. And about the new contention behaviour, this is only
between different stations, not within a node, so it won't impact you.

> cheers,
> jamal

	Have fun...

	Jean

Re: in-driver QoS

[jamal]

On Tue, 2004-06-08 at 15:52, Jean Tourrilhes wrote:
> On Tue, Jun 08, 2004 at 03:18:37PM -0400, jamal wrote:
> > Prioritization is a subset of QoS. So if 802.11e talks prioritization,
> > thats precisely what it means - QoS.
> 
> 	Yes, it's one component of a QoS solution. But, my point is
> that on it's own, it's not enough.

There is no mapping or exclusivity of QoS to bandwidth reservation.
The most basic QoS and most popular QoS mechanisms even on Linux is 
just prioritization and nothing to do with bandwidth allocation.

> > The guy has some valid points in terms of multiple DMA rings if i
> > understood him correctly. Theres current architectural deficiencies.
> 
> 	I don't buy that. The multiple DMA ring is not the main thing
> here, all DMA transfer share the same I/O bus to the card and share
> the same memory pool, so there is no real performance gain there. The
> I/O bnandwidth to the card is vastly superior to the medium bandwidth,
> so the DMA process will never be a bottleneck.

According to Vladimir the wireless piece of it is different.
i.e each DMA ring will get different 802.11 channels 
with different backoff and contention window parameters. 
So nothing to do with the DMA process being a bottleneck.

Help me understand this better:
theres a wired side and a wireless side or are both send and receive
interafacing to the air?

> The real benefit is that the contention on the medium is
> prioritised (between contenting nodes). The contention process (CSMA,
> backoff, and all the jazz) will give a preference to stations with
> packet of the highest priority compared to stations wanting to send
> packet of lower priorities. To gain advantage of that, you only need
> to assign your packet the right priority at the driver level, and the
> CSMA will send it appropriately.

Yes, but how does the CSMA figure that? Is it not from the different
DMA rings?

> With respect to the 4 different hardware queue, you should see
> them only as an extension of the netdev queues. Basically, you just
> have a pipeline between the scheduler and the MAC which is almost a
> FIFO, but not exactly a FIFO. Those queues may do packet reordering
> between themselves, based on priorities. But at the end of the day
> they are only going to send what the scheduler is feeding them, and
> every packet the scheduler pass to those queues is eventually sent, so
> they are totally slave to the scheduler.

Is it a FIFO or there are several DMA rings involved? If the later:
when do you stop the netdevice (i.e call netif_stop_queue())? 

> 	So, I would not worry about the DMA rings. I may worry a
> little bit about packet reordering between queues, but I don't think
> it's a problem. And about the new contention behaviour, this is only
> between different stations, not within a node, so it won't impact you.

Anyone putting different packets from same flow cant guarantee ordering.

cheers,
jamal

Re: in-driver QoS

[Jean Tourrilhes]

On Tue, Jun 08, 2004 at 04:55:39PM -0400, jamal wrote:
> On Tue, 2004-06-08 at 15:52, Jean Tourrilhes wrote:
> > On Tue, Jun 08, 2004 at 03:18:37PM -0400, jamal wrote:
> > > Prioritization is a subset of QoS. So if 802.11e talks prioritization,
> > > thats precisely what it means - QoS.
> > 
> > 	Yes, it's one component of a QoS solution. But, my point is
> > that on it's own, it's not enough.
> 
> There is no mapping or exclusivity of QoS to bandwidth reservation.
> The most basic QoS and most popular QoS mechanisms even on Linux is 
> just prioritization and nothing to do with bandwidth allocation.

	The difference is that the Linux infrastructure can do it,
even if you don't do it, the 802.11e can't.
	Whatever, it does not matter.

> > 	I don't buy that. The multiple DMA ring is not the main thing
> > here, all DMA transfer share the same I/O bus to the card and share
> > the same memory pool, so there is no real performance gain there. The
> > I/O bnandwidth to the card is vastly superior to the medium bandwidth,
> > so the DMA process will never be a bottleneck.
> 
> According to Vladimir the wireless piece of it is different.
> i.e each DMA ring will get different 802.11 channels 

	Nope they can't get to different wireless channel, unless you
have two radio modem in your hardware. If you have two radio hardware,
then you might as well present two virtual devices.
	The standard 802.11e (EDCF/HCF) is mostly a modification of
the contention process on the medium, everything happens on the same
wireless channel. Vladimir's use of "channel" is confusing, but I
think he meant a virtual channel in the hardware, or something else.

> with different backoff and contention window parameters. 

	Yep. This impact the contention process.
	This is similar to what was implemented in 100VG / IEEE
802.12, but in more elaborated.

> So nothing to do with the DMA process being a bottleneck.

	You were the one worried about having multiple DMA rings.

> Help me understand this better:
> theres a wired side and a wireless side or are both send and receive
> interafacing to the air?

	This is like old coax-Ethernet, but instead of having a common
coax cable, you have a single wireless channel shared by all
stations. For more details, please look in my Wireless Howto.
	Both send and receive are done on the same frequency. The
other side of the hardware plug in the PCI bus.

> > The real benefit is that the contention on the medium is
> > prioritised (between contenting nodes). The contention process (CSMA,
> > backoff, and all the jazz) will give a preference to stations with
> > packet of the highest priority compared to stations wanting to send
> > packet of lower priorities. To gain advantage of that, you only need
> > to assign your packet the right priority at the driver level, and the
> > CSMA will send it appropriately.
> 
> Yes, but how does the CSMA figure that? Is it not from the different
> DMA rings?

	Yes. So, what the drivers need to do in the xmit handler is to
figure out what is the packet priority (probably using skb->priority
or another mechanism) and put it in the appropriate queue/ring/FIFO.

> Is it a FIFO or there are several DMA rings involved? If the later:
> when do you stop the netdevice (i.e call netif_stop_queue())? 

	There is 4 FIFOs (or whichever number then want to configure)
in parallel.
	Most likely, the FIFOs will share the same memory pool on the
card, so when a FIFO is full, most likely the other FIFOs will be full
or close to it.
	In theory, they could dedicate card memory to each FIFO. But,
in such case, if one FIFO is full and the other empty, it means that
the card scheduler doesn't process packets according to the netdev
scheduler. The netdev scheduler is the authoritative one, because
directly controled by the policy and the intserv/diffserv
software. Therefore you really want the card scheduler to start
draining the full FIFO before we resume sending to the other FIFOs,
otherwise the card scheduler will biased the policy netdev tries to
enforce.
	So, in any case, my suggestion would be to netif_stop_queue()
as soon as one FIFO is full, and to netif_wake_queue() as soon as all
FIFO have space. This is the most simple and predictable solution.

	But, we are talking there as if the hardware was going to have
some incredibly smart scheduler across FIFOs. From my experience with
wireless MAC implementations, the behaviour will be really simplistic
(always send from the highest priority FIFO), if not totally
broken. And you will probably have very little control over it in low
end cards (hardwired ?).
	This is why I would not trust MAC level scheduling (within a
single host), and my concern is more to avoid the card scheduler to
mess up netdev scheduling (which is a known quantity) rather than try
to find way to take advantage of it.

> > 	So, I would not worry about the DMA rings. I may worry a
> > little bit about packet reordering between queues, but I don't think
> > it's a problem. And about the new contention behaviour, this is only
> > between different stations, not within a node, so it won't impact you.
> 
> Anyone putting different packets from same flow cant guarantee ordering.

	For performance reason, because of TCP behaviour, you really
want to keep packets of a flow ordered. I agree that keeping ordering
across flow in non realistic, because the point of QoS is to reorder
packet across flows.

> cheers,
> jamal

	Have fun...

	Jean

Re: in-driver QoS

[jamal]

On Tue, 2004-06-08 at 18:01, Jean Tourrilhes wrote:


> > According to Vladimir the wireless piece of it is different.
> > i.e each DMA ring will get different 802.11 channels 
> 
> Nope they can't get to different wireless channel, unless you
> have two radio modem in your hardware. If you have two radio hardware,
> then you might as well present two virtual devices.

Since Vladimir is not speaking up i am gonna take your word for it.

> The standard 802.11e (EDCF/HCF) is mostly a modification of
> the contention process on the medium, everything happens on the same
> wireless channel. Vladimir's use of "channel" is confusing, but I
> think he meant a virtual channel in the hardware, or something else.
>
> > with different backoff and contention window parameters. 
> 
> 	Yep. This impact the contention process.
> 	This is similar to what was implemented in 100VG / IEEE
> 802.12, but in more elaborated.

so the only differentiation is on backoff and contention window
parameters. In other words, higher prio will get opportunity to be more
of a hog or aggressive?

> > So nothing to do with the DMA process being a bottleneck.
> 
> 	You were the one worried about having multiple DMA rings.
> 
> > Help me understand this better:
> > theres a wired side and a wireless side or are both send and receive
> > interafacing to the air?
> 
> This is like old coax-Ethernet, but instead of having a common
> coax cable, you have a single wireless channel shared by all
> stations. For more details, please look in my Wireless Howto.
> Both send and receive are done on the same frequency. The
> other side of the hardware plug in the PCI bus.

I think i gotcha.


> > Yes, but how does the CSMA figure that? Is it not from the different
> > DMA rings?
> 
> Yes. So, what the drivers need to do in the xmit handler is to
> figure out what is the packet priority (probably using skb->priority
> or another mechanism) and put it in the appropriate queue/ring/FIFO.
> 

Sure this is the easy part. The hard part is below.

> > Is it a FIFO or there are several DMA rings involved? If the later:
> > when do you stop the netdevice (i.e call netif_stop_queue())? 
> 
> There is 4 FIFOs (or whichever number then want to configure)
> in parallel.
> Most likely, the FIFOs will share the same memory pool on the
> card, so when a FIFO is full, most likely the other FIFOs will be full
> or close to it.

How do you reach such a conclusion?
There maybe packets of the same priority for longs periods of time.

> In theory, they could dedicate card memory to each FIFO. But,
> in such case, if one FIFO is full and the other empty, it means that
> the card scheduler doesn't process packets according to the netdev
> scheduler. The netdev scheduler is the authoritative one, because
> directly controled by the policy and the intserv/diffserv
> software. Therefore you really want the card scheduler to start
> draining the full FIFO before we resume sending to the other FIFOs,
> otherwise the card scheduler will biased the policy netdev tries to
> enforce.

But then you loose sync with the qdisc level scheduling.
Assume a burst of low prio packets arrive, they get drained to the low
prio FIFO in the driver. It gets full and now we lock the driver.
Next a burst of high prio packets come in and they cantt be sent to the
driver until all low prio packets already on FIFO are sent.

> So, in any case, my suggestion would be to netif_stop_queue()
> as soon as one FIFO is full, and to netif_wake_queue() as soon as all
> FIFO have space. This is the most simple and predictable solution.

Simple, yes. Predictable or even accurate, no.
Take a very simple prio based scheduling. The rules are you only process
low priority packets if higher ones dont exist.
It also means that higher priority packets can starve the low prio ones
and that would be fine.

> But, we are talking there as if the hardware was going to have
> some incredibly smart scheduler across FIFOs. From my experience with
> wireless MAC implementations, the behaviour will be really simplistic
> (always send from the highest priority FIFO), if not totally
> broken. 

"Always send from highest priority" is fine. Its what the default linux
scheduler and the prio qdisc do. A lot of research and experienece has
gone into understanding their behaviors.
Perhaps you could tell users to configure such prioritization when using
these NICs.

> And you will probably have very little control over it in low
> end cards (hardwired ?).

Actually there are ethernet MACs today which have multiple DMA rings. so
the general problem is not just for wireless devices.

> This is why I would not trust MAC level scheduling (within a
> single host), and my concern is more to avoid the card scheduler to
> mess up netdev scheduling (which is a known quantity) rather than try
> to find way to take advantage of it.

We need to make chnages and do it properly. 
Your approach to use only one priority/FIFO is not sane. 
Of course the wireless people dont have to use it - Although that will
be a mistake. I have a NIC that has two DMA channels which i plan to map
to X priority levels at the the qdisc levels. 

> For performance reason, because of TCP behaviour, you really
> want to keep packets of a flow ordered. I agree that keeping ordering
> across flow in non realistic, because the point of QoS is to reorder
> packet across flows.

That can be handled at the TC level using policies.

cheers,
jamal

Re: in-driver QoS

[Vladimir Kondratiev]

On Tuesday 08 June 2004 23:55, jamal wrote:
> On Tue, 2004-06-08 at 15:52, Jean Tourrilhes wrote:
> > On Tue, Jun 08, 2004 at 03:18:37PM -0400, jamal wrote:
> > > Prioritization is a subset of QoS. So if 802.11e talks prioritization,
> > > thats precisely what it means - QoS.
> >
> > 	Yes, it's one component of a QoS solution. But, my point is
> > that on it's own, it's not enough.
>
> There is no mapping or exclusivity of QoS to bandwidth reservation.
> The most basic QoS and most popular QoS mechanisms even on Linux is
> just prioritization and nothing to do with bandwidth allocation.
Correct. If you deal with bandwidth allocation, this is integrated service. 
Usually, diff serv used, which is just priority. BTW, in wireless QoS, 
bandwidth allocation present as well. Protocol is as follows: transmitter 
station should ask access point to establish new TSPEC (traffic 
specification), it get ID for this traffic, and then AP will poll station for 
this TSPEC, providing guranteed bandwidth, delay etc.
>
> > > The guy has some valid points in terms of multiple DMA rings if i
> > > understood him correctly. Theres current architectural deficiencies.
> >
> > 	I don't buy that. The multiple DMA ring is not the main thing
> > here, all DMA transfer share the same I/O bus to the card and share
> > the same memory pool, so there is no real performance gain there. The
> > I/O bnandwidth to the card is vastly superior to the medium bandwidth,
> > so the DMA process will never be a bottleneck.
>
> According to Vladimir the wireless piece of it is different.
> i.e each DMA ring will get different 802.11 channels
> with different backoff and contention window parameters.
> So nothing to do with the DMA process being a bottleneck.
>
> Help me understand this better:
> theres a wired side and a wireless side or are both send and receive
> interafacing to the air?
>
All on wireless.
> > The real benefit is that the contention on the medium is
> > prioritised (between contenting nodes). The contention process (CSMA,
> > backoff, and all the jazz) will give a preference to stations with
> > packet of the highest priority compared to stations wanting to send
> > packet of lower priorities. To gain advantage of that, you only need
> > to assign your packet the right priority at the driver level, and the
> > CSMA will send it appropriately.
>
> Yes, but how does the CSMA figure that? Is it not from the different
> DMA rings?
>
> > With respect to the 4 different hardware queue, you should see
> > them only as an extension of the netdev queues. Basically, you just
> > have a pipeline between the scheduler and the MAC which is almost a
> > FIFO, but not exactly a FIFO. Those queues may do packet reordering
> > between themselves, based on priorities. But at the end of the day
> > they are only going to send what the scheduler is feeding them, and
> > every packet the scheduler pass to those queues is eventually sent, so
> > they are totally slave to the scheduler.
>
> Is it a FIFO or there are several DMA rings involved? If the later:
> when do you stop the netdevice (i.e call netif_stop_queue())?
You hit the problem. Due to single queue, I can't provide separate back 
pressure for different access categories. What I do now, I do some internal 
buffering and netif_stop_queue() when total number of packets (or bytes) 
exceed some threshold. Of course, with watermarks to fight jitter.

Let's consider real example. Some application do FTP transfer, lots of data. 
Simultaneously, voice-over-IP connection invoked. Now question is: how to 
assure voice quality? Accordingly to TGe, voice is send either with high 
priority, or in TSPEC. If we will send all packets with high priority, we 
will hit ourselves. If we can't provide some back pressure for low priority 
traffic, it will block voice packets, since some moment you should 
netif_stop_queue().

Ideal would be if I can call netif_stop_queue(id), separately for each id.

I will send explanation for TGe in separate mail

Re: in-driver QoS

[jamal]

On Wed, 2004-06-09 at 01:51, Vladimir Kondratiev wrote:

> > Is it a FIFO or there are several DMA rings involved? If the later:
> > when do you stop the netdevice (i.e call netif_stop_queue())?
>
> You hit the problem. 

Sorry, I should have made it clear and reemphasized it a few times. I
think Jean understands the issue but not its repurcassions.

> Due to single queue, I can't provide separate back 
> pressure for different access categories. What I do now, I do some internal 
> buffering and netif_stop_queue() when total number of packets (or bytes) 
> exceed some threshold. Of course, with watermarks to fight jitter.

Will work fine if you have mostly only one priority really. 

> Let's consider real example. Some application do FTP transfer, lots of data. 
> Simultaneously, voice-over-IP connection invoked. Now question is: how to 
> assure voice quality? 

Non-trivial with current setup. 

> Accordingly to TGe, voice is send either with high 
> priority, or in TSPEC. If we will send all packets with high priority, we 
> will hit ourselves. If we can't provide some back pressure for low priority 
> traffic, it will block voice packets, since some moment you should 
> netif_stop_queue().
> 
> Ideal would be if I can call netif_stop_queue(id), separately for each id.

Indeed. 
Looking at the transmit path code it seems doable.
for each dev->id you also maintain a dev->id_state.
We either use skb->fwmark or skb->priority to map to the different
dev->ids.
The major challenge would be how to start the different queues once they
are stopped. I suspect there is only tx completed interupt; i take it
you can tell when each of the FIFOs is ready to swallow more packets?

cheers,
jamal

Re: in-driver QoS

[Jean Tourrilhes]

On Tue, Jun 08, 2004 at 11:46:49PM -0400, jamal wrote:
> On Tue, 2004-06-08 at 18:01, Jean Tourrilhes wrote:
> 
> > 	Yep. This impact the contention process.
> > 	This is similar to what was implemented in 100VG / IEEE
> > 802.12, but in more elaborated.
> 
> so the only differentiation is on backoff and contention window
> parameters. In other words, higher prio will get opportunity to be more
> of a hog or aggressive?

	Yep. It's like a fast pass to cut the line at DisneyWorld.

> > There is 4 FIFOs (or whichever number then want to configure)
> > in parallel.
> > Most likely, the FIFOs will share the same memory pool on the
> > card, so when a FIFO is full, most likely the other FIFOs will be full
> > or close to it.
> 
> How do you reach such a conclusion?
> There maybe packets of the same priority for longs periods of time.

	If all the FIFO take from the same memory pool, when one FIFO
is full, it means that the memory pool is exhausted. If the memory
pool is exhausted, then you can't fill the other FIFOs.

> But then you loose sync with the qdisc level scheduling.
> Assume a burst of low prio packets arrive, they get drained to the low
> prio FIFO in the driver. It gets full and now we lock the driver.
> Next a burst of high prio packets come in and they cantt be sent to the
> driver until all low prio packets already on FIFO are sent.

	Yep. That's no worse than what we have today with a single
FIFO in today's cards. Remember that amount of buffer on the card is
limited, so we are not talking of an incredible number of packets in
those FIFO. I'm 100% with Andy in suggesting to keep hardware FIFO as
short as possible, precisely so that the TC scheduling is effective.
	If you let the card scheduler take over, it will screw up your
TC scheduling no matter what, unless the card scheduler use the exact
same scheduling as TC (which is unlikely for complex TC policies).
	If the card policy is to always drain the highest priority
queue first, and you want to guarantee a minimum bandwidth for low
priority traffic at the TC level, if you let the card scheduler do its
business and always feed high priority traffic when it wants it, then
there is no way you can guarantee your minimum bandwidth for low
priority traffic.

> > But, we are talking there as if the hardware was going to have
> > some incredibly smart scheduler across FIFOs. From my experience with
> > wireless MAC implementations, the behaviour will be really simplistic
> > (always send from the highest priority FIFO), if not totally
> > broken. 
> 
> "Always send from highest priority" is fine.

	No, it's fine only if TC policy is "Always send from highest
priority". If TC policy is different, then it's not fine at all.

> Its what the default linux
> scheduler and the prio qdisc do. A lot of research and experienece has
> gone into understanding their behaviors.
> Perhaps you could tell users to configure such prioritization when using
> these NICs.

	You assume that the card scheduler will be configurable, and
work as expected. Wait and see ;-)

> We need to make chnages and do it properly. 
> Your approach to use only one priority/FIFO is not sane. 
> Of course the wireless people dont have to use it - Although that will
> be a mistake. I have a NIC that has two DMA channels which i plan to map
> to X priority levels at the the qdisc levels. 

	Good luck ;-)

> cheers,
> jamal

	Have fun...

	Jean

Re: in-driver QoS

[Vladimir Kondratiev]

> > Due to single queue, I can't provide separate back
> > pressure for different access categories. What I do now, I do some
> > internal buffering and netif_stop_queue() when total number of packets
> > (or bytes) exceed some threshold. Of course, with watermarks to fight
> > jitter.
>
> Will work fine if you have mostly only one priority really.
Unfortunately, yes.
>
> > Let's consider real example. Some application do FTP transfer, lots of
> > data. Simultaneously, voice-over-IP connection invoked. Now question is:
> > how to assure voice quality?
>
> Non-trivial with current setup.
>
> > Accordingly to TGe, voice is send either with high
> > priority, or in TSPEC. If we will send all packets with high priority, we
> > will hit ourselves. If we can't provide some back pressure for low
> > priority traffic, it will block voice packets, since some moment you
> > should netif_stop_queue().
> >
> > Ideal would be if I can call netif_stop_queue(id), separately for each
> > id.
>
> Indeed.
> Looking at the transmit path code it seems doable.
> for each dev->id you also maintain a dev->id_state.
> We either use skb->fwmark or skb->priority to map to the different
BTW, what is fwmark? in 2.6.6 it is not present.
> dev->ids.
> The major challenge would be how to start the different queues once they
> are stopped. I suspect there is only tx completed interupt; i take it
> you can tell when each of the FIFOs is ready to swallow more packets?
Sure. I know when each DMA queue have space to accept new packets. w.r.t Tx 
discipline, it is really like 4 (taking into account TSPEC, see my mail about 
TGe, minimum 5 for STA and 6 (i did not said about power save buffering) for 
AP) independent devices.

I see you got the idea. Question is, how to implement it.

Re: in-driver QoS

[jamal]

On Wed, 2004-06-09 at 13:40, Jean Tourrilhes wrote:
> On Tue, Jun 08, 2004 at 11:46:49PM -0400, jamal wrote:
> > > Most likely, the FIFOs will share the same memory pool on the
> > > card, so when a FIFO is full, most likely the other FIFOs will be full
> > > or close to it.
> > 
> > How do you reach such a conclusion?
> > There maybe packets of the same priority for longs periods of time.
> 
> If all the FIFO take from the same memory pool, when one FIFO
> is full, it means that the memory pool is exhausted. 

Is this how these things are designed?

> If the memory
> pool is exhausted, then you can't fill the other FIFOs.

So there are no bounds defined for each FIFO?
If yes, whoever designed those boards is on some really cheap crack.
Fire his or her ass.
If no, then please dont use this approach.
Put some limits to the FIFOs and use the strict priority scheme defined
(it seems by that standard).

> Yep. That's no worse than what we have today with a single
> FIFO in today's cards. Remember that amount of buffer on the card is
> limited, so we are not talking of an incredible number of packets in
> those FIFO. I'm 100% with Andy in suggesting to keep hardware FIFO as
> short as possible, precisely so that the TC scheduling is effective.
> If you let the card scheduler take over, it will screw up your
> TC scheduling no matter what, unless the card scheduler use the exact
> same scheduling as TC (which is unlikely for complex TC policies).

I am assuming it will use _exactly_ the same prioritization approiach;
even if bandwidth allocation is used in the scheduling, the
prioritization will match _exactly_ what the NIC does.

> If the card policy is to always drain the highest priority
> queue first, and you want to guarantee a minimum bandwidth for low
> priority traffic at the TC level, if you let the card scheduler do its
> business and always feed high priority traffic when it wants it, then
> there is no way you can guarantee your minimum bandwidth for low
> priority traffic.

You can. But the bigger question is do you care?

> 
> No, it's fine only if TC policy is "Always send from highest
> priority". If TC policy is different, then it's not fine at all.

Not really. Just pick any of the other schedulers which do bwidth
scheduling and map the priorities to the FIFO priorities. 

> You assume that the card scheduler will be configurable, and
> work as expected. Wait and see ;-)

I am assuming the only thing it can do is strict priority. I trust you
know more about how these cards look like - so when you express doubts
about the lack of configurability you are also putting doubts in me; but
let me say this: If you can have configurability such that you can
partition finite FIFOs one for each priority or for a set of priorities,
then you are set.

cheers,
jamal

Re: in-driver QoS

[jamal]

On Wed, 2004-06-09 at 14:27, Vladimir Kondratiev wrote:

> Sure. I know when each DMA queue have space to accept new packets. w.r.t Tx 
> discipline, it is really like 4 (taking into account TSPEC, see my mail about 
> TGe, minimum 5 for STA and 6 (i did not said about power save buffering) for 
> AP) independent devices.

Vladimir - do you have one of these cards? Jean is putting some my
doubts in my mind about their designs. Do they have seperate DMA rings?

> I see you got the idea. Question is, how to implement it.

As suggested earlier:
- introduce id and id_state per ring.
- use a skb tag to select id
- if ring is full, use same id to requeue to qdisc.
- qdiscs above must have semantics that map to the strict priority
scheme (eg you could use CBQ which does both priorities and bandwith
allocation or use simple prio or strict prio qdiscs).
- netif stopping and starting is done per id/ring. 

Did i miss something?

Do you wanna try this? I could give you a hand but dont have much time
to code at the moment. I could point you to the different pieces of code
that need mods and suggest the changes.

cheers,
jamal

Re: in-driver QoS

[Horms]

On Wed, Jun 09, 2004 at 09:27:28PM +0300, Vladimir Kondratiev wrote:
> >
> > Indeed.
> > Looking at the transmit path code it seems doable.
> > for each dev->id you also maintain a dev->id_state.
> > We either use skb->fwmark or skb->priority to map to the different
> BTW, what is fwmark? in 2.6.6 it is not present.

The name in the kernel was changed to nfmark a while ago. 
Though is seems to be still referenced as fwmark quite a lot
in documentation. I believe its primary use is for the mark target
and match in netfilter/iptables. 

-- 
Horms

Re: in-driver QoS

[Vladimir Kondratiev]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thursday 10 June 2004 04:59, jamal wrote:
> On Wed, 2004-06-09 at 14:27, Vladimir Kondratiev wrote:
> > Sure. I know when each DMA queue have space to accept new packets. w.r.t
> > Tx discipline, it is really like 4 (taking into account TSPEC, see my
> > mail about TGe, minimum 5 for STA and 6 (i did not said about power save
> > buffering) for AP) independent devices.
>
> Vladimir - do you have one of these cards? Jean is putting some my
> doubts in my mind about their designs. Do they have seperate DMA rings?
Good question. Until I can really answer, let's say "in theory, all next 
generation wireless cards should have similar design". Hint: I have also mail 
ending by intel.com
>
> > I see you got the idea. Question is, how to implement it.
>
> As suggested earlier:
> - introduce id and id_state per ring.
> - use a skb tag to select id
skb->priority, correct?
> - if ring is full, use same id to requeue to qdisc.
how?
> - qdiscs above must have semantics that map to the strict priority
> scheme (eg you could use CBQ which does both priorities and bandwith
> allocation or use simple prio or strict prio qdiscs).
> - netif stopping and starting is done per id/ring.
how to do it? I am afraid several network interfaces is not a good idea.
>
> Did i miss something?
Sounds good. Next step is integrated service, where, prior to use some 
priority, STA have to allocate bandwidth and get admission from AP.
>
> Do you wanna try this? I could give you a hand but dont have much time
> to code at the moment. I could point you to the different pieces of code
> that need mods and suggest the changes.
It would be great help. Please...
I promise to share results.
>
> cheers,
> jamal
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAx/fZqxdj7mhC6o0RAv/6AJ9r0zqZN8E1Y6UFUBH+0Ikfl6yRPQCgqhCJ
OmLUtIXWDjtI8RpQcsUvQJ0=
=agJJ
-----END PGP SIGNATURE-----

Re: in-driver QoS

[jamal]

On Thu, 2004-06-10 at 01:55, Vladimir Kondratiev wrote:

> > Vladimir - do you have one of these cards? Jean is putting some my
> > doubts in my mind about their designs. Do they have seperate DMA rings?
>
> Good question. Until I can really answer, let's say "in theory, all next 
> generation wireless cards should have similar design". Hint: I have also mail 
> ending by intel.com

Ok, fine.

> Sounds good. Next step is integrated service, where, prior to use some 
> priority, STA have to allocate bandwidth and get admission from AP.

That part is easy using the current linux qdiscs - the hard part is
getting the separate ids for each FIFO/DMA ring. 

> >
> > Do you wanna try this? I could give you a hand but dont have much time
> > to code at the moment. I could point you to the different pieces of code
> > that need mods and suggest the changes.
>
> It would be great help. Please...
> I promise to share results.

Well, you are doing most of the work;-> Let me knwo when you have the
NIC then we could start. Actually we could discuss even before you get
the NIC; lets take it offline.

cheers,
jamal

Re: in-driver QoS

[Vladimir Kondratiev]

Jamal,
let's list the features need to be provided for 802.11 QoS, and problems.

It is worth to provide standard interface with wireless stack; otherwise each 
driver will invent its own solution.

1. NIC have number of Tx DMA channels, with different channels used for 
different priorities. It is dictated by standard (TGe).

Most likely, it should be 4 queues for EDCA traffic (4 priorities), 1 for HCCA 
(polled, pre-agreed streams) and optionally 1 for multicast traffic (AP need 
it).

Each queue need to start/stop separately. For flexibility, it should be some 
way for driver to request queues and specify mapping to these queues.

Ideas for how to implement it in stack?

Meanwhile, ideas how to get separate per-priority control with existing 
infrastructure?

2. There is traffic that require admission control. Unless driver performs 
allocation with AP, this traffic is not allowed. TGe standard dictates it.

Driver should participate in bandwidth allocation (via RSVP?). It should get 
some form of request (IOCTL?) which it will serve by performing allocation on 
link layer. It is easy to do proprietary IOCTL and white custom RSVP daemon, 
but it is much better to do something generic for all drivers to use.

Vladimir.

Re: in-driver QoS

[jamal]

On Mon, 2004-06-14 at 16:53, Vladimir Kondratiev wrote:
> Jamal,
> let's list the features need to be provided for 802.11 QoS, and problems.
> 
> It is worth to provide standard interface with wireless stack; otherwise each 
> driver will invent its own solution.
> 
> 1. NIC have number of Tx DMA channels, with different channels used for 
> different priorities. It is dictated by standard (TGe).
> 
> Most likely, it should be 4 queues for EDCA traffic (4 priorities), 1 for HCCA 
> (polled, pre-agreed streams) and optionally 1 for multicast traffic (AP need 
> it).
> 
> Each queue need to start/stop separately. For flexibility, it should be some 
> way for driver to request queues and specify mapping to these queues.
> 
> Ideas for how to implement it in stack?

Refer to my earlier note on implementation. 
The only challenge is in starting and stopping each hardware DMA/FIFO
separately. Thats whats missing today.
The mapping between s/ware level queues and DMA/FIFO level is done via
skb tags and is enforced via tc policies entered by the admin. Some of
the current tags could be used or a new one created just for this.

> Meanwhile, ideas how to get separate per-priority control with existing 
> infrastructure?

like i said the qdisc infrastruture is in place.

> 2. There is traffic that require admission control. Unless driver performs 
> allocation with AP, this traffic is not allowed. 

Is this admission control something like 802.1x/EAP?
I think stuff like that belongs to user space. You could use the new tc
extensions i have to redirect packets to a user space process which then
installs tc policies based on some compute the user space app does (eg
lookup some LDAP/RADIUS attributes etc)

> TGe standard dictates it.
> 
> Driver should participate in bandwidth allocation (via RSVP?). It should get 
> some form of request (IOCTL?) which it will serve by performing allocation on 
> link layer. It is easy to do proprietary IOCTL and white custom RSVP daemon, 
> but it is much better to do something generic for all drivers to use.

There is nothing new here as far as linux is concerned. Driver doesnt
participate in any of this directly. Traffic control is done by a layer
above driver. By the time the packet gets to the driver, it just looks
at the skb tag and maps it to the right DMA/FIFO (may stop the
netif_queue for the FIFO etc)
I dont know many people running RSVP or COPS for that matter. But we
have the mechanisms for them in place. I know a lot of fscked people who
will wanna do this via SNMP. And dont forget your bash scripts of
course.
Now imagine you trying to make all the above be aware of whatever your
driver is supposed to be doing via ioctls. Not a very scalable idea.

cheers,
jamal

Re: in-driver QoS

[Vladimir Kondratiev]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Tuesday 15 June 2004 15:26, jamal wrote:
> On Mon, 2004-06-14 at 16:53, Vladimir Kondratiev wrote:
> > Jamal,
> > let's list the features need to be provided for 802.11 QoS, and problems.
> >
> > It is worth to provide standard interface with wireless stack; otherwise
> > each driver will invent its own solution.
> >
> > 1. NIC have number of Tx DMA channels, with different channels used for
> > different priorities. It is dictated by standard (TGe).
> >
> > Most likely, it should be 4 queues for EDCA traffic (4 priorities), 1 for
> > HCCA (polled, pre-agreed streams) and optionally 1 for multicast traffic
> > (AP need it).
> >
> > Each queue need to start/stop separately. For flexibility, it should be
> > some way for driver to request queues and specify mapping to these
> > queues.
> >
> > Ideas for how to implement it in stack?
>
> Refer to my earlier note on implementation.
> The only challenge is in starting and stopping each hardware DMA/FIFO
> separately. Thats whats missing today.
> The mapping between s/ware level queues and DMA/FIFO level is done via
> skb tags and is enforced via tc policies entered by the admin. Some of
> the current tags could be used or a new one created just for this.
Sure, skb->priority is what I use currently to map packets to queue.
>
> > Meanwhile, ideas how to get separate per-priority control with existing
> > infrastructure?
>
> like i said the qdisc infrastruture is in place.
Examples? Do you know some driver that uses it?
>
> > 2. There is traffic that require admission control. Unless driver
> > performs allocation with AP, this traffic is not allowed.
>
> Is this admission control something like 802.1x/EAP?
> I think stuff like that belongs to user space. You could use the new tc
> extensions i have to redirect packets to a user space process which then
> installs tc policies based on some compute the user space app does (eg
> lookup some LDAP/RADIUS attributes etc)
It is different kind of admission. 802.1x is about opening port, and is done 
above MAC using data packets. It is exactly like TSPEC below. For TSPEC, it 
is MAC level protocol, implemented with management packets.
Idea here is that high priority EDCA(contention access) channels should be 
controlled. Otherwise one can Tx all traffic at high priority.
>
> > TGe standard dictates it.
> >
> > Driver should participate in bandwidth allocation (via RSVP?). It should
> > get some form of request (IOCTL?) which it will serve by performing
> > allocation on link layer. It is easy to do proprietary IOCTL and white
> > custom RSVP daemon, but it is much better to do something generic for all
> > drivers to use.
>
> There is nothing new here as far as linux is concerned. Driver doesnt
> participate in any of this directly. Traffic control is done by a layer
> above driver. By the time the packet gets to the driver, it just looks
> at the skb tag and maps it to the right DMA/FIFO (may stop the
> netif_queue for the FIFO etc)
My point is, in order to made this stream valid, driver should perform some 
handshake with AP. Driver should send management packet and get response.
If handshake is not done, this packet will be rejected by AP, and station will 
be thrown out of network for protocol violation.

> I dont know many people running RSVP or COPS for that matter. But we
> have the mechanisms for them in place. I know a lot of fscked people who
> will wanna do this via SNMP. And dont forget your bash scripts of
> course.
> Now imagine you trying to make all the above be aware of whatever your
> driver is supposed to be doing via ioctls. Not a very scalable idea.
>
> cheers,
> jamal
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAzyU8qxdj7mhC6o0RAizzAKCsd2wZcSqMa3pJ7FKduTdUU2lPawCfdcg8
RaW20rmN9hwifwwIFjgKHRE=
=MpoC
-----END PGP SIGNATURE-----