[Ns-developers] GSoC 2009 - Minstrel rate control algorithm

[Luciano Jerez Chaves]

Hi,

I have detailed several issues in my proposal, but I didn't submit it
yet (I’ll do it as soon as possible). Answering some questions, the
following paragraphs describe what I’m planning to do.

Talking about the first problem of gathering the statistic for all the
links, the Minstrel algorithm uses the throughput as a performance
metric. It’s necessary to know the probability of a packet success
transmission in each rate, the number of bytes transmitted, and the
necessary time to transmit this single packet in the air.

The number of bytes transmitted is straightforward to obtain just
counting the number of packets transmitted, and the necessary time to
transmit a packet in the air can be obtained by the function
YansWifiPhy::CalculateTxDuration. There are also some functions in the
interference-helper class got probability of transmission packets, but
I’m not sure if it gives the right probability we are looking for.

Many rate control algorithms try to optimize the throughput. Even if
not all of them use this metric in the decision of a rate change, I
could be a good idea to provide simple functions capable of retrieving
this information and make it available for any other optimization
solution.

About the moving average, I think that will be simple. I don’t know
yet which values the Minstrel uses as alpha in the EWMA, but the
implementation is quite simple.

In my opinion, the retry chain mechanism is the major challenge in
this project. My initial solution is to look for the function
responsible for packet retransmissions and keep track of the attempt
number of each retransmission. As this number increases, the algorithm
needs to change the rate accordingly, but I don’t know how to perform
these adjustments in the Minstrel class yet. I think it can be done in
a similar way ARF updates or decreases its rate, using functions like
ArfWifiRemoteStation::DoReportRtsFailed.

Talking about the table to store the performance values, I had already
identified the need of some efficient structure and I agree with you
that a hash table could provide a very good performance. At ach cycle,
it’s necessary to read one positions for rate in each link, and update
as many positions as the rates tested. Since links can be included and
exclude accordingly the routing algorithms, it’s necessary to avoid
reading useless positions in the table, and a hash function can help
in this situation leading to the right position with minimum effort.

About the evaluation process, the tests need to be planed and well
discussed during the project.
About implementing other rate control solutions, I didn’t include it
in my proposal with intent to avoid over-working in the short duration
of this project. Despite the fact, I’m planning to implement it anyway
(even after the program ends), because I’ll need it for my personal
research.

Regards,

--
Luciano J. Chaves
MSc Computer Science Student
University of Campinas




On Wed, Apr 1, 2009 at 17:47, Ruben Merz <ruben at net.t-labs.tu-berlin.de> wrote:
> Hi Luciano,
>
> Comments below,
>
> On 3/31/09 4:32 PM, Luciano Jerez Chaves wrote:
>>
>> Hi Ruben,
>>
>> On Mon, Mar 30, 2009 at 17:36, Ruben Merz<ruben at net.t-labs.tu-berlin.de>
>>  wrote:
>>>
>>> Hi Luciano
>>>
>>> On 3/30/09 5:16 AM, Luciano Jerez Chaves wrote:
>>>>
>>>> Hi Ns-developers,
>>>>
>>>> My name is Luciano and I am a MSc Computer Science student at
>>>> University of Campinas, Brazil.
>>>>
>>>> I'm working with Rate Adaptation solutions to wireless networks in
>>>> my master's thesis and I'm interested in participating in Google
>>>> Summer of Code this year.
>>>>
>>>> I've been looking for an idea in ns-3 wiki page and I found a
>>>> interesting
>>>> project to implement Minstrel rate control algorithm in ns-3.
>>>>
>>>> I believe it would be very motivating and helpful to me, since I'm
>>>> evaluating my proposed algorithm based on simulations in ns-2.
>>>> I've implemented two other different rate adaptations solutions in
>>>> ns-2, using the dei802mr (develop by Nicola Baldo, and his team,
>>>> at DEI) to compare my algorithm with.
>>>
>>> Do you plan to also port these algorithms in ns-3?
>>
>> The algorithms that I implemented in ns-2 are the AARF (an extension
>> of the original ARF), CARA, and my own solution, that I didn't finish
>> yet.
>>
>> The initial idea was to port CARA and AARF to ns-3 in order to fairly
>> compare my solution with all available implementations, but I figured
>> out that the AARF is already implemented on it. Although, we still
>> have CARA, and there are other solutions in the literature that could
>> be incorporated into the ns-3 as far as possible.
>>
>>>> I think that a good implementation in ns-3 will contribute to my
>>>> project and to many other people.
>>>>
>>>> I am still not familiar with the ns-3 code, but I figured out that
>>>> there many others rate control algorithms implemented on it.
>>>> I have good knowledge in C++ programming and about rate
>>>> control in wireless networks. I'm currently studding the Minstrel
>>>> algorithm, and I think that will be possible to successfully implement
>>>> it in ns-3 during the GSoc program.
>>>
>>> The rate control algorithms are all in src/devices/wifi. You can also go
>>> in
>>> the example directory and grep for calls to SetRemoteStationManager.
>>
>> Looking in the suggested directory and in some rate control solutions
>> there, it doesn't seem very difficult to implement a new rate control
>> algorithm, since the code structure is well defined.
>
> Good to hear. But what I'd like to hear from you is a more detailed plan
> than what you describe below. Minstrel has several components. There are (1)
> gathering the statistics for all the links (2) the moving average algorithm
> (3) the retry chain algorithm and (4) the rate lookaround algorithm.
>
> How would you tackle those issues? For instance, gathering the statistics
> for all the links is something that might be of interest for the other rate
> control algorithms? So, it might be interesting to get a more general
> solution. The retry chain concept is something that is more related to the
> underlying hardware than the rate control algorithm in itself.
>
>> I believe that it's possible to implement the Minstrel algorithms in
>> something like five weeks or so.
>
> As I said above, try to come up with a more detailed plan.
>
>> Since the Minstrel solution is based solely in statistical measured
>> performance with minimum of assumptions, the coding difficulty is
>> linked to create a data structure that will be used by the algorithm
>> (a table to store values for each destiny) and to obtain, from the
>
> Typically, I'm not sure that a simple table would be the most efficient way.
> I'd rather advise a hash table or some tree structure.
>
> I think you should also look into the linux kernel code that implements
> Minstrel: http://lxr.linux.no/linux+v2.6.29/net/mac80211/rc80211_minstrel.c
>
>> simulated code, the performance metrics evaluated.
>>
>> After that, with the experience obtained with ns-3 programming, the
>> code style, simulator structure and many other things, it will be
>> possible to introduce other solutions.
>
> Let's see. Before moving to other solutions, I'd like to see some validation
> and testing done. I don't know yet how, but this should be planned.
>
> Once it's sure that the code performs reasonably well, I'll be happy to see
> some other rate control algorithm implemented.
>
>>>> I would like a feedback about these project, and any suggestion
>>>> that may arise. I would be happy with a mentor' contact.
>>>
>>> Let me know if you have questions.
>>
>> I'm looking forward to hearing from you in order to improve my GSoC
>> application.
>
> Well, don't forget to submit you proposal on the gsoc website.
>
> Best
> Ruben
>
>>> Best
>>> Ruben
>>>
>>>> Best regards,
>>>>
>>>> --
>>>> Luciano J. Chaves
>>>> MSc Computer Science Student
>>>> University of Campinas
>>>
>>> --
>>> Ruben Merz                   Deutsche Telekom Laboratories
>>> http://www.net.t-labs.tu-berlin.de/people/ruben_merz.shtml
>>>
>>
>> Regards
>>
>> --
>> Luciano J. Chaves
>> MSc Computer Science Student
>> University of Campinas
>