Thanks. That will do. -Qasim
On Wed, May 30, 2012 at 6:09 PM, Javier Cardona <[email protected]> wrote: > Hi Qasim, > > On Wed, May 30, 2012 at 2:55 PM, Qasim Javed <[email protected]> wrote: >> Hi Javier, >> >> I have set up disto11s, but where do I access the existing hwsim test >> cases that you have? > > Our test suite is not public but here is a template that should give > you a jump start: > https://github.com/cozybit/open80211s/wiki/HwsimTestTemplate > As you will see, it is trivial to modify to test your scenario. > > Cheers, > > Javier > >> On Tue, May 29, 2012 at 12:59 PM, Javier Cardona <[email protected]> wrote: >>> Hi Qasim, >>> >>> Thanks for looking into this. If your explanation is accurate, then >>> it looks like the originator and target sequence numbers are swapped >>> for PREPs. That said, the scenario you describe should be easily >>> testable using hwsim. In fact we have a very similar test on our test >>> suite that is currently passing. Would you consider writing a hwsim >>> test case to test your patch? >>> >>> Cheers, >>> >>> Javier >>> >>> PS. I've narrowed down the audience of this thread to avoid boring >>> everyone in linux, netdev and linux-wireless on obscure mesh >>> discussions... :) >>> >>> On Thu, May 24, 2012 at 10:02 PM, Qasim Javed <[email protected]> wrote: >>>> Hi, >>>> >>>> I have been doing some experiments using the 802.11s functionality in the >>>> mac80211 stack. Today I stumbled across something which I believe is a >>>> critical bug in the usage of originator sequence number for a Path Reply >>>> message upon the reception of a Path Request message. >>>> >>>> Consider the following topology: >>>> >>>> +---+ >>>> | S | >>>> +---+ >>>> / \ >>>> / \ >>>> +---+ +---+ >>>> | A | | B | >>>> +---+ +---+ >>>> \ / >>>> \ / >>>> +---+ >>>> | D | >>>> +---+ >>>> >>>> Node S is the source node and D the destination. Clearly there are two >>>> possible paths from S to D namely S->A->D and S->B->D. When S wants to >>>> communicate with D, it will broadcast a Path Request (PREQ) where the >>>> originator will be S and target will be D. On receiving the PREQ, both A >>>> and B will broadcast it further to D. Let us assume that aggregate value >>>> of the metric for path D->B->S denoted by cost(DBS) is greater than >>>> cost(DAS). Notice that according to HWMP operation, when the PREQ is >>>> propagating from S to D, the cost on the "reverse" path is aggregated, >>>> that is why I used cost(DB) + cost(BS) for cost(DBS) and did not consider >>>> cost(SBD). Suppose also that smaller the metric the better it is which is >>>> the case for the default airtime link metric used by the 802.11s stack. >>>> >>>> Let us suppose that the PREQ which passes through B arrives first at D and >>>> as mentioned earlier has a larger (worse) value than the soon to be >>>> received PREQ through the intermediate hop A. When D receives a PREQ from >>>> B, since it has not received any other PREQ, it generates a Path Reply >>>> (PREP). More specifically, the function hwmp_preq_frame_process generates >>>> the PREP. The PREQ contains originator and target sequence numbers which >>>> are used to avoid loops and ascertain the freshness of route information. >>>> On receiving a PREQ at D, the above mentioned function checks whether >>>> dot11MeshHWMPnetDiameterTraversalTime have elapsed since the last sequence >>>> number update (stored in ifmsh->last_sn_update). So suppose this is true >>>> when the first PREQ via B is received at D. So, in this case the >>>> originator sequence number in PREP is incremented (that is becomes one >>>> more than the target sequence number in the PREQ). >>>> >>>> Let us look at an example at this point. Suppose, the the originator >>>> sequence number in the PREQ is 1 and the target sequence number is 2. When >>>> this PREQ is received at D via B, and considering that >>>> dot11MeshHWMPnetDiameterTraversalTime have passed since the last sequence >>>> number update, we will increment the target sequence number which now >>>> becomes 3. Now for the PREP, the originator sequence number of PREQ, 1 in >>>> this case, becomes the target sequence number of PREP and the target >>>> sequence number of the PREQ (which has been updated and its value is 3) >>>> becomes the originator sequence number of the PREP. >>>> >>>> As this PREQ which was received at D via B has a larger metric, we know >>>> that when the PREQ from S is received via A, it will have a lower (better) >>>> metric, hence we will also generate a PREP for that PREQ. Suppose the >>>> second PREQ via A is received at D within >>>> dot11MeshHWMPnetDiameterTraversalTime (currently 50ms). This is a >>>> reasonable assumption since the PREQ is broadcast by S and further >>>> broadcast by A and B in some order. There is very less likelihood that the >>>> time difference between the PREQ from A and B would be greater than 50ms >>>> since this is a lot of time in 802.11 speak where the nodes are contending >>>> for the channel on the order of hundreds of microseconds (typically). In >>>> short, it is very likely (confirmed through experiments) that this >>>> difference is less than 50ms. >>>> >>>> So, when the PREQ from S arrives a D via A, since most likely this event >>>> happens within 50ms if the PREQ via B, the target sequence number will not >>>> be updated. Therefore, the originator sequence number stays at 1 and the >>>> target sequence number remains 2. It is very important to note that the >>>> code in hwmp_preq_frame_process just "swaps" the originator and target >>>> sequence numbers for use in the PREP. More specifically as mentioned >>>> earlier, the second PREP will have an originator sequence number of 2 and >>>> a target sequence number of 1. >>>> >>>> At this point, we have two PREPs in flight, one via B and one via A. >>>> >>>> PREP via B: originator sequence number = 3, target sequence number = 1 >>>> PREP via A: originator sequence number = 2, target sequence number = 1 >>>> >>>> The net effect is that when these PREPs reach S, irrespective of the order >>>> in which they arrive, the PREP via A will be ignored! This is very wrong >>>> since the reason we sent the PREP via A in the first place was that it had >>>> a better metric (albeit on the reverse path). >>>> >>>> I have not tested the patch yet. This is more of a heads up email to let >>>> everyone. >>>> >>>> Signed-off-by: Qasim Javed <[email protected]> >>>> --- >>>> net/mac80211/mesh_hwmp.c | 2 ++ >>>> 1 files changed, 2 insertions(+), 0 deletions(-) >>>> >>>> diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c >>>> index 70ac7d1..a13b593 100644 >>>> --- a/net/mac80211/mesh_hwmp.c >>>> +++ b/net/mac80211/mesh_hwmp.c >>>> @@ -543,6 +543,8 @@ static void hwmp_preq_frame_process(struct >>>> ieee80211_sub_if_data *sdata, >>>> time_before(jiffies, ifmsh->last_sn_update)) { >>>> target_sn = ++ifmsh->sn; >>>> ifmsh->last_sn_update = jiffies; >>>> + } else { >>>> + target_sn = ifmsh->sn; >>>> } >>>> } else { >>>> rcu_read_lock(); >>>> -- >>>> 1.7.1 >>>> >>>> _______________________________________________ >>>> Devel mailing list >>>> [email protected] >>>> http://lists.open80211s.org/cgi-bin/mailman/listinfo/devel >>> >>> >>> >>> -- >>> Javier Cardona >>> cozybit Inc. >>> http://www.cozybit.com >>> _______________________________________________ >>> Devel mailing list >>> [email protected] >>> http://lists.open80211s.org/cgi-bin/mailman/listinfo/devel > > > > -- > Javier Cardona > cozybit Inc. > http://www.cozybit.com _______________________________________________ Devel mailing list [email protected] http://lists.open80211s.org/cgi-bin/mailman/listinfo/devel
