Rate control & USB

Rate control & USB

[Ivo Van Doorn]

Hi,

I am currently looking into the old problem of the mac80211 rate
control algorithms
and USB devices. The Ralink USB devices (and as far as I know, the
other USB devices
as well), do not work well with the PID and Minstrel algorithms. This
is caused by the
fact that USB devices do not report the TX status to mac80211.

When the URB callback function is called, it only indicates the frame
was uploaded
to the hardware, and the frame has been enqueued in the hardware queue
within the
USB device itself. The statistics about the number of retries and the
ACK status are
therefor lost.

These statistics are however often still available (in a limited form)
within the device
registers. Although these statistics cannot be obtained per frame, it
might still be
possible to control a working rate control algorithm with it.

My current idea for this, is not to generate a completely new
algorithm, but base
it on the currently existing rate controls. For this I want to
introduce a new flag:
IEEE80211_HW_REQUIRES_BATCH_TX_STATUS, This flag will enable
polling in mac80211, where the callback function ieee80211_ops->get_tx_stats
is called. In this function the driver can fill in a structure
containing the number
of Acked frames, non-acked frames and retries. This structure can then be
passed to a new function in the rate_control_ops structure.

The problem here is that we have lost the per-sta statistics. However using the
single TX status reports, we can count the number of frames which are sent for
a given STA during the poll interval. We can then determine the percentage of
frames sent for that STA, We can then add the percentage of the retry and ACK
count to each STA. Throughout poll interval the rate algorithm would send all
frames to the same STA with the same TX rate, but between polls, the rate will
be updated.

Overall these changes will not make the optimal use of PID or
Minstrel, but it would
at least improve the situation for USB.

Any thoughts about this solution?

Ivo

Re: Rate control & USB

[Felix Fietkau]

On 2010-07-12 12:48 PM, Ivo Van Doorn wrote:
> The problem here is that we have lost the per-sta statistics. However using the
> single TX status reports, we can count the number of frames which are sent for
> a given STA during the poll interval. We can then determine the percentage of
> frames sent for that STA, We can then add the percentage of the retry and ACK
> count to each STA. Throughout poll interval the rate algorithm would send all
> frames to the same STA with the same TX rate, but between polls, the rate will
> be updated.
> 
> Overall these changes will not make the optimal use of PID or
> Minstrel, but it would
> at least improve the situation for USB.
> 
> Any thoughts about this solution?
I don't know how minstrel could work with this approach. Before it
starts to use a rate, it has to sample it first. How can you sample
rates with your tx status feedback approach?

- Felix

Re: Rate control & USB

[John W. Linville]

On Mon, Jul 12, 2010 at 05:17:51PM +0200, Felix Fietkau wrote:
> On 2010-07-12 12:48 PM, Ivo Van Doorn wrote:
> > The problem here is that we have lost the per-sta statistics. However using the
> > single TX status reports, we can count the number of frames which are sent for
> > a given STA during the poll interval. We can then determine the percentage of
> > frames sent for that STA, We can then add the percentage of the retry and ACK
> > count to each STA. Throughout poll interval the rate algorithm would send all
> > frames to the same STA with the same TX rate, but between polls, the rate will
> > be updated.
> > 
> > Overall these changes will not make the optimal use of PID or
> > Minstrel, but it would
> > at least improve the situation for USB.
> > 
> > Any thoughts about this solution?
> I don't know how minstrel could work with this approach. Before it
> starts to use a rate, it has to sample it first. How can you sample
> rates with your tx status feedback approach?

You would have to commit to that rate for at least one polling period, no?

John
-- 
John W. Linville		Someday the world will need a hero, and you
linville@tuxdriver.com			might be all we have.  Be ready.

Re: Rate control & USB

[Ivo Van Doorn]

On Mon, Jul 12, 2010 at 5:20 PM, John W. Linville
<linville@tuxdriver.com> wrote:
> On Mon, Jul 12, 2010 at 05:17:51PM +0200, Felix Fietkau wrote:
>> On 2010-07-12 12:48 PM, Ivo Van Doorn wrote:
>> > The problem here is that we have lost the per-sta statistics. However using the
>> > single TX status reports, we can count the number of frames which are sent for
>> > a given STA during the poll interval. We can then determine the percentage of
>> > frames sent for that STA, We can then add the percentage of the retry and ACK
>> > count to each STA. Throughout poll interval the rate algorithm would send all
>> > frames to the same STA with the same TX rate, but between polls, the rate will
>> > be updated.
>> >
>> > Overall these changes will not make the optimal use of PID or
>> > Minstrel, but it would
>> > at least improve the situation for USB.
>> >
>> > Any thoughts about this solution?
>> I don't know how minstrel could work with this approach. Before it
>> starts to use a rate, it has to sample it first. How can you sample
>> rates with your tx status feedback approach?
>
> You would have to commit to that rate for at least one polling period, no?

Exactly, it does mean that the sampled rate might be used longer then with
the regular TX status reporting, but I don't think that would be a too big of a
problem. If it reaslly is a problem, it might be changed that for
sampling shorter
polling periods are used, but that will make the interface a bit uglier... :(

Ivo

Re: Rate control & USB

[Steve deRosier]

Ivo,

I don't know much about the details of either the rate control
algorithms, or other USB devices, but the usb8388 with the libertas_tf
driver _does_ report per skb tx feedback, not just that the frame has
been sent to the hardware.  Perhaps there's other USB devices that
also have good feedback?

In any case, I'm just asking that nothing gets broken in the case
where the USB devices _do_ provide the tx feedback information.  I
assume you weren't going to break anything, but I just wanted to make
sure you knew that some USB devices did have this feature.

- Steve

On Mon, Jul 12, 2010 at 3:48 AM, Ivo Van Doorn <ivdoorn@gmail.com> wrote:
> Hi,
>
> I am currently looking into the old problem of the mac80211 rate
> control algorithms
> and USB devices. The Ralink USB devices (and as far as I know, the
> other USB devices
> as well), do not work well with the PID and Minstrel algorithms. This
> is caused by the
> fact that USB devices do not report the TX status to mac80211.
>
> When the URB callback function is called, it only indicates the frame
> was uploaded
> to the hardware, and the frame has been enqueued in the hardware queue
> within the
> USB device itself. The statistics about the number of retries and the
> ACK status are
> therefor lost.
>
> These statistics are however often still available (in a limited form)
> within the device
> registers. Although these statistics cannot be obtained per frame, it
> might still be
> possible to control a working rate control algorithm with it.
>
> My current idea for this, is not to generate a completely new
> algorithm, but base
> it on the currently existing rate controls. For this I want to
> introduce a new flag:
> IEEE80211_HW_REQUIRES_BATCH_TX_STATUS, This flag will enable
> polling in mac80211, where the callback function ieee80211_ops->get_tx_stats
> is called. In this function the driver can fill in a structure
> containing the number
> of Acked frames, non-acked frames and retries. This structure can then be
> passed to a new function in the rate_control_ops structure.
>
> The problem here is that we have lost the per-sta statistics. However using the
> single TX status reports, we can count the number of frames which are sent for
> a given STA during the poll interval. We can then determine the percentage of
> frames sent for that STA, We can then add the percentage of the retry and ACK
> count to each STA. Throughout poll interval the rate algorithm would send all
> frames to the same STA with the same TX rate, but between polls, the rate will
> be updated.
>
> Overall these changes will not make the optimal use of PID or
> Minstrel, but it would
> at least improve the situation for USB.
>
> Any thoughts about this solution?
>
> Ivo
> --
> To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: Rate control & USB

[Ivo Van Doorn]

Hi,

> I don't know much about the details of either the rate control
> algorithms, or other USB devices, but the usb8388 with the libertas_tf
> driver _does_ report per skb tx feedback, not just that the frame has
> been sent to the hardware.  Perhaps there's other USB devices that
> also have good feedback?

Ah ok, I wasn't aware that libertas had a working TX status reporting. :)

> In any case, I'm just asking that nothing gets broken in the case
> where the USB devices _do_ provide the tx feedback information.  I
> assume you weren't going to break anything, but I just wanted to make
> sure you knew that some USB devices did have this feature.

Well my plans were to enable the batch TX updating through a mac80211 flag,
or some other methoed where it is up to the driver to enable the batch TX
status updating. So nothing should change for the other drivers which do not
need this feature. :)

But it is good to know that at least some USB hardware do not have the
TX status problem. :)

Ivo

Re: Rate control & USB

[Helmut Schaa]

Am Montag 12 Juli 2010 schrieb Ivo Van Doorn:
> I am currently looking into the old problem of the mac80211 rate
> control algorithms
> and USB devices. The Ralink USB devices (and as far as I know, the
> other USB devices
> as well), do not work well with the PID and Minstrel algorithms. This
> is caused by the
> fact that USB devices do not report the TX status to mac80211.

Ivo, do you know by any chance if the USB devices also have a TX_STA_FIFO
register like the PCI variants? Does it contain useful data or just crap?

Helmut

Re: Rate control & USB

[Ivo Van Doorn]

On Mon, Jul 12, 2010 at 9:14 PM, Helmut Schaa
<helmut.schaa@googlemail.com> wrote:
> Am Montag 12 Juli 2010 schrieb Ivo Van Doorn:
>> I am currently looking into the old problem of the mac80211 rate
>> control algorithms
>> and USB devices. The Ralink USB devices (and as far as I know, the
>> other USB devices
>> as well), do not work well with the PID and Minstrel algorithms. This
>> is caused by the
>> fact that USB devices do not report the TX status to mac80211.
>
> Ivo, do you know by any chance if the USB devices also have a TX_STA_FIFO
> register like the PCI variants? Does it contain useful data or just crap?

Well I guess he has the registers (we don'[t have rt2870 specific specsheets,
but the register definitions from the original Ralink driver to
suggest the register
is there). However, even if it contains valid data, how do you want to match
the contents of that register with the sent frames in the queue?

And another downside, is that the above only applies to rt2800usb, and not
for rt73usb and rt2500usb, which neither have the TX status register, and were
replaced with statistics registers (which I want to read for the batch
TX status).

Ivo

Re: Rate control & USB

[Helmut Schaa]

Am Dienstag 13 Juli 2010 schrieb Ivo Van Doorn:
> On Mon, Jul 12, 2010 at 9:14 PM, Helmut Schaa
> <helmut.schaa@googlemail.com> wrote:
> > Am Montag 12 Juli 2010 schrieb Ivo Van Doorn:
> >> I am currently looking into the old problem of the mac80211 rate
> >> control algorithms
> >> and USB devices. The Ralink USB devices (and as far as I know, the
> >> other USB devices
> >> as well), do not work well with the PID and Minstrel algorithms. This
> >> is caused by the
> >> fact that USB devices do not report the TX status to mac80211.
> >
> > Ivo, do you know by any chance if the USB devices also have a TX_STA_FIFO
> > register like the PCI variants? Does it contain useful data or just crap?
> 
> Well I guess he has the registers (we don't have rt2870 specific specsheets,
> but the register definitions from the original Ralink driver to
> suggest the register
> is there). However, even if it contains valid data, how do you want to match
> the contents of that register with the sent frames in the queue?

We could stuff a unique packet ID into the TXWI and the TX_STA_FIFO should
contain the same ID alongside the TX status after the frame was processed
by the hw.

> And another downside, is that the above only applies to rt2800usb, and not
> for rt73usb and rt2500usb, which neither have the TX status register, and were
> replaced with statistics registers (which I want to read for the batch
> TX status).

Ok, that's a valid argument ...

Helmut

Re: Rate control & USB

[Ivo Van Doorn]

On Tue, Jul 13, 2010 at 9:15 PM, Helmut Schaa
<helmut.schaa@googlemail.com> wrote:
> Am Dienstag 13 Juli 2010 schrieb Ivo Van Doorn:
>> On Mon, Jul 12, 2010 at 9:14 PM, Helmut Schaa
>> <helmut.schaa@googlemail.com> wrote:
>> > Am Montag 12 Juli 2010 schrieb Ivo Van Doorn:
>> >> I am currently looking into the old problem of the mac80211 rate
>> >> control algorithms
>> >> and USB devices. The Ralink USB devices (and as far as I know, the
>> >> other USB devices
>> >> as well), do not work well with the PID and Minstrel algorithms. This
>> >> is caused by the
>> >> fact that USB devices do not report the TX status to mac80211.
>> >
>> > Ivo, do you know by any chance if the USB devices also have a TX_STA_FIFO
>> > register like the PCI variants? Does it contain useful data or just crap?
>>
>> Well I guess he has the registers (we don't have rt2870 specific specsheets,
>> but the register definitions from the original Ralink driver to
>> suggest the register
>> is there). However, even if it contains valid data, how do you want to match
>> the contents of that register with the sent frames in the queue?
>
> We could stuff a unique packet ID into the TXWI and the TX_STA_FIFO should
> contain the same ID alongside the TX status after the frame was processed
> by the hw.

True, but we would have the same problem in rt2800pci, that the number
of bits is too limited to completely identify a queue + queue index correctly.

>> And another downside, is that the above only applies to rt2800usb, and not
>> for rt73usb and rt2500usb, which neither have the TX status register, and were
>> replaced with statistics registers (which I want to read for the batch
>> TX status).
>
> Ok, that's a valid argument ...

:)

Ivo

Re: Rate control & USB

[Julian Calaby]

On Wed, Jul 14, 2010 at 05:51, Ivo Van Doorn <ivdoorn@gmail.com> wrote:
> On Tue, Jul 13, 2010 at 9:15 PM, Helmut Schaa
> <helmut.schaa@googlemail.com> wrote:
>> Am Dienstag 13 Juli 2010 schrieb Ivo Van Doorn:
>>> On Mon, Jul 12, 2010 at 9:14 PM, Helmut Schaa
>>> <helmut.schaa@googlemail.com> wrote:
>>> > Am Montag 12 Juli 2010 schrieb Ivo Van Doorn:
>>> >> I am currently looking into the old problem of the mac80211 rate
>>> >> control algorithms
>>> >> and USB devices. The Ralink USB devices (and as far as I know, the
>>> >> other USB devices
>>> >> as well), do not work well with the PID and Minstrel algorithms. This
>>> >> is caused by the
>>> >> fact that USB devices do not report the TX status to mac80211.
>>> >
>>> > Ivo, do you know by any chance if the USB devices also have a TX_STA_FIFO
>>> > register like the PCI variants? Does it contain useful data or just crap?
>>>
>>> Well I guess he has the registers (we don't have rt2870 specific specsheets,
>>> but the register definitions from the original Ralink driver to
>>> suggest the register
>>> is there). However, even if it contains valid data, how do you want to match
>>> the contents of that register with the sent frames in the queue?
>>
>> We could stuff a unique packet ID into the TXWI and the TX_STA_FIFO should
>> contain the same ID alongside the TX status after the frame was processed
>> by the hw.
>
> True, but we would have the same problem in rt2800pci, that the number
> of bits is too limited to completely identify a queue + queue index correctly.

We could have a table that matches queue and queue index to the
packet's ID. So if we're sending packet #47 from queue #1, and it gets
assigned id #9, then we drop that information into the table - so when
the hardware tells us the status of packet id #9 we can look up which
queue it is and send it to the right place.

Of course, this means storing a stack of extra data in system memory,
as well as having the complexity of looking up the queue data when we
get the status back, but if we've only got limited bits, then that'll
set a hard limit on the amount of data and time to retrieve, and we
may not even need all of it unless the hardware's running at full
capacity. We could reduce it further if we don't need a status of
*every* packet - we could potentially get away with only storing data
for, let's say, every fourth packet or something.

As we're likely to see similarly crippled devices elsewhere, maybe we
could incorporate this type of accounting into mac80211 somewhere.

Of course, this could just be a huge stack of overhead for a problem
that could be solved much more elegantly, but yeah.

*hands over $0.02*

Thanks,

-- 

Julian Calaby

Email: julian.calaby@gmail.com
.Plan: http://sites.google.com/site/juliancalaby/

Re: Rate control & USB

[Ivo Van Doorn]

On Wed, Jul 14, 2010 at 3:53 AM, Julian Calaby <julian.calaby@gmail.com> wrote:
> On Wed, Jul 14, 2010 at 05:51, Ivo Van Doorn <ivdoorn@gmail.com> wrote:
>> On Tue, Jul 13, 2010 at 9:15 PM, Helmut Schaa
>> <helmut.schaa@googlemail.com> wrote:
>>> Am Dienstag 13 Juli 2010 schrieb Ivo Van Doorn:
>>>> On Mon, Jul 12, 2010 at 9:14 PM, Helmut Schaa
>>>> <helmut.schaa@googlemail.com> wrote:
>>>> > Am Montag 12 Juli 2010 schrieb Ivo Van Doorn:
>>>> >> I am currently looking into the old problem of the mac80211 rate
>>>> >> control algorithms
>>>> >> and USB devices. The Ralink USB devices (and as far as I know, the
>>>> >> other USB devices
>>>> >> as well), do not work well with the PID and Minstrel algorithms. This
>>>> >> is caused by the
>>>> >> fact that USB devices do not report the TX status to mac80211.
>>>> >
>>>> > Ivo, do you know by any chance if the USB devices also have a TX_STA_FIFO
>>>> > register like the PCI variants? Does it contain useful data or just crap?
>>>>
>>>> Well I guess he has the registers (we don't have rt2870 specific specsheets,
>>>> but the register definitions from the original Ralink driver to
>>>> suggest the register
>>>> is there). However, even if it contains valid data, how do you want to match
>>>> the contents of that register with the sent frames in the queue?
>>>
>>> We could stuff a unique packet ID into the TXWI and the TX_STA_FIFO should
>>> contain the same ID alongside the TX status after the frame was processed
>>> by the hw.
>>
>> True, but we would have the same problem in rt2800pci, that the number
>> of bits is too limited to completely identify a queue + queue index correctly.
>
> We could have a table that matches queue and queue index to the
> packet's ID. So if we're sending packet #47 from queue #1, and it gets
> assigned id #9, then we drop that information into the table - so when
> the hardware tells us the status of packet id #9 we can look up which
> queue it is and send it to the right place.

True, but the overhead of having that lookup table is not really worth
it I believe.
This solution depends on the number of bits available, thus it works
only for rt2800usb,
while with a different RC method I am looking for a more generic solution.

> Of course, this means storing a stack of extra data in system memory,
> as well as having the complexity of looking up the queue data when we
> get the status back, but if we've only got limited bits, then that'll
> set a hard limit on the amount of data and time to retrieve, and we
> may not even need all of it unless the hardware's running at full
> capacity. We could reduce it further if we don't need a status of
> *every* packet - we could potentially get away with only storing data
> for, let's say, every fourth packet or something.

Well it should be up to the RC algorithm to indicate for which frames
it at least demands a TX status and for which frames it is less important.

> As we're likely to see similarly crippled devices elsewhere, maybe we
> could incorporate this type of accounting into mac80211 somewhere.

That really depends on which devices actually have the TX status reporting
registers without any mapping to a real packet. I think there are more devices
without TX status reporting and without TX status registers, than those with the
TX status registers.

Ivo