Hi Javier, I am trying to introduce delay on one of the links using netem qdisc. When I use netem on the source node, I can see the delay is added (verified using ping) but when I add it to one of the intermediate hops, the delay does not show up in pcap file.
Logically the queuing disciplines should be invoked irrespective of whether a mesh node is forwarding traffic or not. I have wmediumd working fine for me, but I need a deterministic delay (in addition to the loss which makes the metric value for one of the paths higher, thus making it undesirable) on one of the paths to emulate the scenario in which the wrong usage of the originator sequence number (in a PREP) will be triggered. Any ideas? Thanks, -Qasim On Wed, May 30, 2012 at 7:08 PM, Qasim Javed <[email protected]> wrote: > 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
