Hi Javier, I have set up disto11s, but where do I access the existing hwsim test cases that you have?
Thanks, -Qasim 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 _______________________________________________ Devel mailing list [email protected] http://lists.open80211s.org/cgi-bin/mailman/listinfo/devel
