[PATCH] mac80211: mesh - don't special case routing to transmitter

[PATCH] mac80211: mesh - don't special case routing to transmitter

[Alexis Green]

From: Jesse Jones <jjones@cococorp.com>

Updating the path to the transmitter of a path message is optional
according to section 13.10.8.4 of the standard. Doing so can lead to
better performance since we can adjust the route to the transmitter based
on the freshest possible information. However it can also cause routing
loops with more than four or five nodes. Trading off routing correctness
for a marginal performance improvement seems like a bad idea so this patch
removes that feature.

Signed-off-by: Alexis Green <agreen@cococorp.com>
Signed-off-by: A. Riley Eller <reller@cococorp.com>

---

diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
index be63534..5042f48
--- a/net/mac80211/mesh_hwmp.c
+++ b/net/mac80211/mesh_hwmp.c
@@ -369,7 +369,7 @@ static u32 hwmp_route_info_get(struct ieee80211_sub_if_data *sdata,
 	struct mesh_path *mpath;
 	struct sta_info *sta;
 	bool fresh_info;
-	const u8 *orig_addr, *ta;
+	const u8 *orig_addr;
 	u32 orig_sn, orig_metric;
 	unsigned long orig_lifetime, exp_time;
 	u32 last_hop_metric, new_metric;
@@ -480,41 +480,6 @@ static u32 hwmp_route_info_get(struct ieee80211_sub_if_data *sdata,
 			spin_unlock_bh(&mpath->state_lock);
 	}
 
-	/* Update and check transmitter routing info */
-	ta = mgmt->sa;
-	if (ether_addr_equal(orig_addr, ta))
-		fresh_info = false;
-	else {
-		fresh_info = true;
-
-		mpath = mesh_path_lookup(sdata, ta);
-		if (mpath) {
-			spin_lock_bh(&mpath->state_lock);
-			if ((mpath->flags & MESH_PATH_FIXED) ||
-				((mpath->flags & MESH_PATH_ACTIVE) &&
-					(last_hop_metric > mpath->metric)))
-				fresh_info = false;
-		} else {
-			mpath = mesh_path_add(sdata, ta);
-			if (IS_ERR(mpath)) {
-				rcu_read_unlock();
-				return 0;
-			}
-			spin_lock_bh(&mpath->state_lock);
-		}
-
-		if (fresh_info) {
-			mesh_path_assign_nexthop(mpath, sta);
-			mpath->metric = last_hop_metric;
-			mpath->exp_time = time_after(mpath->exp_time, exp_time)
-					  ?  mpath->exp_time : exp_time;
-			mesh_path_activate(mpath);
-			spin_unlock_bh(&mpath->state_lock);
-			mesh_path_tx_pending(mpath);
-		} else
-			spin_unlock_bh(&mpath->state_lock);
-	}
-
 	rcu_read_unlock();
 
 	return process ? new_metric : 0;

RE: [PATCH] mac80211: mesh - don't special case routing to transmitter

[Yeoh Chun-Yeow]

> Updating the path to the transmitter of a path message is optional
> according to section 13.10.8.4 of the standard. Doing so can lead to
> better performance since we can adjust the route to the transmitter based
> on the freshest possible information. However it can also cause routing
> loops with more than four or five nodes.

Do you have the test scenario on how routing loops happen in this case?

Thanks

----
Chun-Yeow

RE: [PATCH] mac80211: mesh - don't special case routing to transmitter

[Jesse Jones]

> > Updating the path to the transmitter of a path message is optional
> > according to section 13.10.8.4 of the standard. Doing so can lead to
> > better performance since we can adjust the route to the transmitter
> > based on the freshest possible information. However it can also cause
> > routing loops with more than four or five nodes.
>
> Do you have the test scenario on how routing loops happen in this case?
>
> Thanks
>
> ----
> Chun-Yeow

We did this over a year ago and I don't think we saw routing loops though
iirc we saw better performance when we made the change. Most likely because
of the other problem with the original code: it creates a path to the ta if
none exists but does not go through discovery to do so. So if the direct hop
is not the best path you're going to be stuck with a crappy path until the
next refresh.

In any case updating metrics without doing an SN feasibility check is highly
suspect. I'm not 100% sure this instance will cause routing loops but I do
know that every time I have tried to be clever and optimize routing without
looking at both the SN and metric I have wound up with routing loops.

  -- Jesse

Re: [PATCH] mac80211: mesh - don't special case routing to transmitter

[Yeoh Chun-Yeow]

On Thu, Jun 25, 2015 at 9:55 AM, Yeoh Chun-Yeow <yeohchunyeow@gmail.com> wrote:
>> Updating the path to the transmitter of a path message is optional
>> according to section 13.10.8.4 of the standard. Doing so can lead to
>> better performance since we can adjust the route to the transmitter based
>> on the freshest possible information. However it can also cause routing
>> loops with more than four or five nodes.
>
> Do you have the test scenario on how routing loops happen in this case?
>

Sorry, I don't see the "optional" work in section 13.10.8.4. Please
note that this maybe useful for most of the cases.

I would recommend to add nl80211 command for doing so. So, others
still can enjoy freshest possible information. What do you think?

----
Chun-Yeow

Re: [PATCH] mac80211: mesh - don't special case routing to transmitter

[Yeoh Chun-Yeow]

Sorry I miss out your previous email.

> We did this over a year ago and I don't think we saw routing loops though
> iirc we saw better performance when we made the change. Most likely because
> of the other problem with the original code: it creates a path to the ta if
> none exists but does not go through discovery to do so.

Yes, it is a direct hop towards the mgmt->sa,

> So if the direct hop
> is not the best path you're going to be stuck with a crappy path until the
> next refresh.

But hey, the code has already compared the path metric, right? Next
refresh, so if you reduce the active path timeout
(dot11MeshHWMPactivePathTimeout), you solve the problem, right?

> In any case updating metrics without doing an SN feasibility check is highly
> suspect.

As cited in section 13.10.8.4, "the mesh STA may create or update its
forwarding information to the transmitter of the element if the path
metric improves." So it is correctly implemented.

> I'm not 100% sure this instance will cause routing loops but I do
> know that every time I have tried to be clever and optimize routing without
> looking at both the SN and metric I have wound up with routing loops.

I would recommend to add nl80211 command to disable this. After all,
it may change other people's network behavior.

Also, you may post you patch to o11s mailing list and your test
scenario. Maybe others can verify as well to be 100% sure.

Thanks

---
Chun-Yeow

RE: [PATCH] mac80211: mesh - don't special case routing to transmitter

[Jesse Jones]

> Sorry I miss out your previous email.
>
> > We did this over a year ago and I don't think we saw routing loops
> > though iirc we saw better performance when we made the change. Most
> > likely because of the other problem with the original code: it creates
> > a path to the ta if none exists but does not go through discovery to do
> > so.
>
> Yes, it is a direct hop towards the mgmt->sa,
>
> > So if the direct hop
> > is not the best path you're going to be stuck with a crappy path until
> > the next refresh.
>
> But hey, the code has already compared the path metric, right? Next
> refresh,
> so if you reduce the active path timeout
> (dot11MeshHWMPactivePathTimeout), you solve the problem, right?

Most likely. But selecting a bad path for 30s (or whatever
dot11MeshHWMPactivePathTimeout is set to) is not a good idea. Of course
usually the direct hop will be the best path but that is certainly not
guaranteed.

> > In any case updating metrics without doing an SN feasibility check is
> > highly suspect.
>
> As cited in section 13.10.8.4, "the mesh STA may create or update its
> forwarding information to the transmitter of the element if the path
> metric
> improves." So it is correctly implemented.

Yes, my argument is that that was a bad idea on the part of the standard and
optional so we can remove it.

> > I'm not 100% sure this instance will cause routing loops but I do know
> > that every time I have tried to be clever and optimize routing without
> > looking at both the SN and metric I have wound up with routing loops.
>
> I would recommend to add nl80211 command to disable this. After all, it
> may
> change other people's network behavior.
>
> Also, you may post you patch to o11s mailing list and your test scenario.
> Maybe others can verify as well to be 100% sure.

There are two test scenarios:
1) When creating the path to a ta where the direct hop is a bad path.
Relatively easy to setup and demonstrate poor performance pre-patch.
2) Incorrect routing when the metric for an existing SN is changed without
also updating the SN. Hard to demonstrate. We've certainly seen similar bugs
with our own mesh protocols but that was with protocols explicitly designed
with testing support. Best approach is probably via something like
http://alloy.mit.edu/alloy/

  -- Jesse

Re: [PATCH] mac80211: mesh - don't special case routing to transmitter

[Yeoh Chun-Yeow]

> There are two test scenarios:
> 1) When creating the path to a ta where the direct hop is a bad path.
> Relatively easy to setup and demonstrate poor performance pre-patch.
> 2) Incorrect routing when the metric for an existing SN is changed without
> also updating the SN. Hard to demonstrate. We've certainly seen similar bugs
> with our own mesh protocols but that was with protocols explicitly designed
> with testing support. Best approach is probably via something like
> http://alloy.mit.edu/alloy/

If the direct hop is a bad path, could it be due the metric calculation.

Also, you may also add your vendor specific mesh protocol to open
source community.

---
Chun-Yeow

RE: [PATCH] mac80211: mesh - don't special case routing to transmitter

[Jesse Jones]

> > There are two test scenarios:
> > 1) When creating the path to a ta where the direct hop is a bad path.
> > Relatively easy to setup and demonstrate poor performance pre-patch.
> > 2) Incorrect routing when the metric for an existing SN is changed
> > without also updating the SN. Hard to demonstrate. We've certainly
> > seen similar bugs with our own mesh protocols but that was with
> > protocols explicitly designed with testing support. Best approach is
> > probably via something like http://alloy.mit.edu/alloy/
>
> If the direct hop is a bad path, could it be due the metric calculation.

Sure, metric calculations are not perfect. But that is an entirely separate
can of worms. For the purposes of this discussion we can assume that the
metrics are perfect. Simplest case is the one I mentioned before: a U where
we're trying to route between the ends of the U but the direct hop is bad
and the links along the U are excellent.

> Also, you may also add your vendor specific mesh protocol to open source
> community.

Maybe. We spent many man years on it and eventually got it routing well. It
was all done in a commercial setting though so I don't know that we would
open source it.

  -- Jesse