[RFC] mac80211: Use correct originator sequence number in a Path Reply

[RFC] mac80211: Use correct originator sequence number in a Path Reply

[Qasim Javed]

Sorry for the duplicate email. As suggested by Julian I have marked this as RFC (was PATCH previously), so that people can comment on it.

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 has 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 originato
 r 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 know.

Signed-off-by: Qasim Javed <qasimj-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
---
 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

Re: [RFC] mac80211: Use correct originator sequence number in a Path Reply

[Yeoh Chun-Yeow]

Hi, Qasim Javed

I think that you are referring to the target HWMP sequence number in
PREP element.

Based on the 802.11s standard, it has specified that
dot11MeshHWMPnetDiameterTraversalTime is only applied to original HWMP
sequence number for PREQ as mentioned in the "Contents of a PREQ
element" in section 11C.

For PREP element, it should be based on the description in section 11C.9.8.3:
"If it is a target mesh STA, it shall update its own HWMP sequence
number to maximum (current HWMP sequence number, target HWMP sequence
number in the PREQ) + 1 immediately before it generates a PREP in
response to a PREQ. The target HWMP sequence number of the PREQ is
relevant when a link was broken along the path and the stored sequence
number was increased at an intermediate mesh STA."

So the target HWMP sequence number should be modified as follow:

diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
index 70ac7d1..5988e82 100644
--- a/net/mac80211/mesh_hwmp.c
+++ b/net/mac80211/mesh_hwmp.c
@@ -538,12 +538,10 @@ static void hwmp_preq_frame_process(struct
ieee80211_sub_if_data *sdata,
                forward = false;
                reply = true;
                metric = 0;
-               if (time_after(jiffies, ifmsh->last_sn_update +
-                                       net_traversal_jiffies(sdata)) ||
-                   time_before(jiffies, ifmsh->last_sn_update)) {
-                       target_sn = ++ifmsh->sn;
-                       ifmsh->last_sn_update = jiffies;
-               }
+               if (SN_LT(ifmsh->sn, target_sn))
+                       ifmsh->sn = target_sn;
+               target_sn = ++ifmsh->sn;
+               ifmsh->last_sn_update = jiffies;

Comments.

Regards,
Chun-Yeow

Re: [RFC] mac80211: Use correct originator sequence number in a Path Reply

[Qasim Javed]

Please see my comments below.

On Fri, May 25, 2012 at 10:30 AM, Yeoh Chun-Yeow <yeohchunyeow-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
> Hi, Qasim Javed
>
> I think that you are referring to the target HWMP sequence number in
> PREP element.

No. I am referring to the originator sequence number in PREP because
when the PREP reaches the originator of the PREQ, the originator
sequence number in the PREP and the value of the metric is used to
determine which PREP will be accepted. If the originator sequence
numbers in the PREPs are different, then the PREP with the higher
sequence number will be accepted irrespective of the value of the
metric. Only if the originator sequence numbers in the PREP are equal
will the metric values in the PREPs be examined.

>
> Based on the 802.11s standard, it has specified that
> dot11MeshHWMPnetDiameterTraversalTime is only applied to original HWMP
> sequence number for PREQ as mentioned in the "Contents of a PREQ
> element" in section 11C.
>
> For PREP element, it should be based on the description in section 11C.9.8.3:
> "If it is a target mesh STA, it shall update its own HWMP sequence
> number to maximum (current HWMP sequence number, target HWMP sequence
> number in the PREQ) + 1 immediately before it generates a PREP in
> response to a PREQ. The target HWMP sequence number of the PREQ is
> relevant when a link was broken along the path and the stored sequence
> number was increased at an intermediate mesh STA."
>
> So the target HWMP sequence number should be modified as follow:
>
> diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
> index 70ac7d1..5988e82 100644
> --- a/net/mac80211/mesh_hwmp.c
> +++ b/net/mac80211/mesh_hwmp.c
> @@ -538,12 +538,10 @@ static void hwmp_preq_frame_process(struct
> ieee80211_sub_if_data *sdata,
>                forward = false;
>                reply = true;
>                metric = 0;
> -               if (time_after(jiffies, ifmsh->last_sn_update +
> -                                       net_traversal_jiffies(sdata)) ||
> -                   time_before(jiffies, ifmsh->last_sn_update)) {
> -                       target_sn = ++ifmsh->sn;
> -                       ifmsh->last_sn_update = jiffies;
> -               }
> +               if (SN_LT(ifmsh->sn, target_sn))
> +                       ifmsh->sn = target_sn;
> +               target_sn = ++ifmsh->sn;
> +               ifmsh->last_sn_update = jiffies;
>
> Comments.

I agree with the description in the standard but you seem to be
misinterpreting it. Please note that the function being considered
here is hwmp_preq_frame_process, which evidently processes a PREQ.
However, because a PREP is generated in response to a PREQ, this
function also checks whether a PREP needs to be generated and then
calls mesh_path_sel_frame_tx with frame type being MPATH_PREP. This
function is also passed the originator and target sequence numbers.

What I am saying is that, in the scenario described in my original
email, the wrong originator sequence number is being used for the
PREP.

Please notice that in hwmp_preq_frame_process, target_sn ends up being
used as orig_sn for the PREP. This is probably what is causing the
confusion in your case.

Your patch is definitely not what I was pointing out, in fact it
diverts from the standard functionality since it removes the check for
HWMPNetDiameterTraversalTime.

>
> Regards,
> Chun-Yeow
> _______________________________________________
> Devel mailing list
> Devel-ZwoEplunGu1xMJw8dq7oimD2FQJk+8+b@public.gmane.org
> http://lists.open80211s.org/cgi-bin/mailman/listinfo/devel

Re: [RFC] mac80211: Use correct originator sequence number in a Path Reply

[Yeoh Chun-Yeow]

> No. I am referring to the originator sequence number in PREP because
> when the PREP reaches the originator of the PREQ, the originator
> sequence number in the PREP and the value of the metric is used to
> determine which PREP will be accepted. If the originator sequence
> numbers in the PREPs are different, then the PREP with the higher
> sequence number will be accepted irrespective of the value of the
> metric. Only if the originator sequence numbers in the PREP are equal
> will the metric values in the PREPs be examined.

Based on the "Table 11C-17—Contents of a PREP element in Case A", the
originator HWMP sequence number is the HWMP sequence number of the
originator mesh STA. So this value (orig_sn in
hwmp_preq_frame_process) is unchanged in the generated PREP element
upon receiving the PREQ element.

The target HWMP sequence number is the HWMP sequence number of the
target mesh STA or target proxy mesh gate after it has been updated
according to 11C.9.8.3. So this value is changed based on target_sn in
hwmp_preq_frame_process.

I think that the confusion is in the hwmp_route_info_get,

case MPATH_PREP:
                /* Originator here refers to the MP that was the target in the
                 * Path Request. We divert from the nomenclature in the draft
                 * so that we can easily use a single function to gather path
                 * information from both PREQ and PREP frames.
                 */
                orig_sn = PREP_IE_TARGET_SN(hwmp_ie);

orig_sn here is actually the target HWMP sequence number of PREP
element generated by hwmp_preq_frame_process.

> Please notice that in hwmp_preq_frame_process, target_sn ends up being
> used as orig_sn for the PREP. This is probably what is causing the
> confusion in your case.

I think that the PREQ element has originator sequence number at the
end but the PREQ element has the target sequence number at the end.
This is what mesh_path_sel_frame_tx is doing.

> Your patch is definitely not what I was pointing out, in fact it
> diverts from the standard functionality since it removes the check for
> HWMPNetDiameterTraversalTime.

I thought that this is only for originator sequence number which is
done by mesh_path_start_discovery.

Regards,
Chun-Yeow

Re: [RFC] mac80211: Use correct originator sequence number in a Path Reply

[Yeoh Chun-Yeow]

> I think that the PREQ element has originator sequence number at the
> end but the PREQ element has the target sequence number at the end.
> This is what mesh_path_sel_frame_tx is doing.

PREP element has originator sequence number at the end but the PREQ
element has the target sequence number at the end.

Regards,
Chun-Yeow

Re: [RFC] mac80211: Use correct originator sequence number in a Path Reply

[Qasim Javed]

Forgot to add Javier. Could you please comment on this?

Thanks,
-Qasim

On Fri, May 25, 2012 at 11:31 AM, Yeoh Chun-Yeow <yeohchunyeow-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>> I think that the PREQ element has originator sequence number at the
>> end but the PREQ element has the target sequence number at the end.
>> This is what mesh_path_sel_frame_tx is doing.
>
> PREP element has originator sequence number at the end but the PREQ
> element has the target sequence number at the end.
>
> Regards,
> Chun-Yeow
> _______________________________________________
> Devel mailing list
> Devel-ZwoEplunGu1xMJw8dq7oimD2FQJk+8+b@public.gmane.org
> http://lists.open80211s.org/cgi-bin/mailman/listinfo/devel