Queuing discipline functionality is only invoked from within dev_queue_xmit.
This function can be called in two possible cases: 1. When a source mesh station sends an IP packet it ends up calling dev_queue_xmit so the queuing discipline is exercised on the source. 2. As a result of ieee80211_deliver_skb which in turn is invoked from ieee80211_rx_h_data. So, basically when a mesh station is forwarding a frame, the qdisc (even if installed on a mesh interface using tc) will not be exercised. I had never thought about that. This means I cannot use netem for introducing delay on the intermediate hops. Since wmediumd does not introduce delays, I guess my test case would be probabilistic rather than deterministic. This is because, the bug that I am trying to reproduce would only trigger if the PREQs arrive at the target in a certain order as described previously. I will look some more into it and get back to you later. By the way, is it OK if I can show you a packet capture which clearly demonstrates that the wrong originator sequence number is being used in the PREP? Thanks, -Qasim On Thu, May 31, 2012 at 3:24 PM, Qasim Javed <[email protected]> wrote: > 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
