mac80211: Jitter HWMP MPATH reply frames to reduce collision on dense networks.
PATCH v2 1/1 mac80211: Jitter HWMP MPATH reply frames to reduce collision on dense networks.
From: Jesse Jones <[email protected]>
Changes since v1: Only flush tx queue if interface is mesh mode.
This prevents kernel panics due to uninitialized spin_lock.
When more than one station hears a broadcast request, it is possible that multiple devices will reply at the same time, potentially causing collision. This patch helps reduce this issue.
--- net/mac80211/ieee80211_i.h | 11 ++++ net/mac80211/iface.c | 61 ++++++++++++++++++++++ net/mac80211/mesh.c | 2 + net/mac80211/mesh_hwmp.c | 124 +++++++++++++++++++++++++++++++++++---------- 4 files changed, 171 insertions(+), 27 deletions(-)
net/mac80211/ieee80211_i.h +11 -0
@@ -330,6 +330,11 @@ struct mesh_preq_queue {u8 flags; }; +struct mesh_tx_queue { +struct list_head list; +struct sk_buff *skb; +}; +struct ieee80211_roc_work {struct list_head list;
@@ -670,6 +675,11 @@ struct ieee80211_if_mesh {spinlock_t mesh_preq_queue_lock;struct mesh_preq_queue preq_queue;int preq_queue_len; +/* Spinlock for trasmitted MPATH frames */ +spinlock_t mesh_tx_queue_lock; +struct mesh_tx_queue tx_queue; +int tx_queue_len; +struct mesh_stats mshstats;struct mesh_config mshcfg;atomic_t estab_plinks;
@@ -919,6 +929,7 @@ struct ieee80211_sub_if_data {struct work_struct work;struct sk_buff_head skb_queue; +struct delayed_work tx_work;u8 needed_rx_chains;enum ieee80211_smps_mode smps_mode;
net/mac80211/iface.c +61 -0
79 lines not on this page · raw message
net/mac80211/mesh.c +2 -0
@@ -1381,6 +1381,8 @@ void ieee80211_mesh_init_sdata(struct ieee80211_sub_if_data *sdata) ieee80211_mesh_path_root_timer, (unsigned long) sdata);INIT_LIST_HEAD (&ifmsh->preq_queue.list); +INIT_LIST_HEAD (&ifmsh->tx_queue.list); +spin_lock_init (&ifmsh->mesh_tx_queue_lock);skb_queue_head_init (&ifmsh->ps.bc_buf);spin_lock_init (&ifmsh->mesh_preq_queue_lock);spin_lock_init (&ifmsh->sync_offset_lock);
net/mac80211/mesh_hwmp.c +97 -27
180 lines not on this page · raw message
Johannes Berg
maintainerQuoted 8 lines · Alexis Green
From: Jesse Jones <[email protected]>
Changes since v1: Only flush tx queue if interface is mesh mode. This prevents kernel panics due to uninitialized
spin_lock.When more than one station hears a broadcast request, it is possible that multiple devices will reply at the same time, potentially causing collision. This patch helps reduce this issue.
It's not clear to me what you mean by "collision"? Over the air the NAV should handle the avoidance thereof, so I don't really see what this does wrt. collisions?
Are these frames somehow duplicates? But I don't see any suppression if you've already put a frame on the "jittered" list then it will never be deleted from it again, so it doesn't suppress anything in that sense?
johannes
Hi Johannes,
This is loosely based on RFC5148, specifically event-triggered message generation as described in section 5.2.
The frames are not duplicated, but, hopefully offset enough so they don't collide at the receiver (and, since, these are management frames, there is no retransmission and we may lose the information contained in them). If the two (or more) devices that reply are synchronized well enough, carrier sense will tell them that air is clear and messages will go out at the same time. It doesn't happen too often, but we found it noticeable enough in our testing.
Best regards,
Alexis Green
Quoted 17 lines · Johannes Berg
Quoted 5 lines · Alexis Green
From: Jesse Jones <[email protected]>
When more than one station hears a broadcast request, it is possible that multiple devices will reply at the same time, potentially causing collision. This patch helps reduce this issue.
It's not clear to me what you mean by "collision"? Over the air the NAV should handle the avoidance thereof, so I don't really see what this does wrt. collisions?
Are these frames somehow duplicates? But I don't see any suppression if you've already put a frame on the "jittered" list then it will never be deleted from it again, so it doesn't suppress anything in that sense?
johannes
Johannes Berg
maintainerHi Alexis,
Quoted 2 lines
This is loosely based on RFC5148, specifically event-triggered message generation as described in section 5.2.
I'm confused. I see how that generally seems to apply to any mobile network, but it *does* state up-front that
In some instances, these problems can be solved in these lower layers, but in other instances, some help at the network and higher layers is necessary.
I believe 802.11 *does* in fact solve these issues at lower layers.
Can you explain how you observed any problem in this area?
Quoted 2 lines
The frames are not duplicated, but, hopefully offset enough so they don't collide at the receiver
That wasn't my question - my question regarding duplicating was if this was intended to *suppress* duplicates, but it sounds like not.
Quoted 2 lines
(and, since, these are management frames, there is no retransmission and we may lose the information contained in them).
That statement isn't true in general, though it does seem that some of the frames you're touching are actually *multicast* frames and as such don't have any retries.
Quoted 4 lines
If the two (or more) devices that reply are synchronized well enough, carrier sense will tell them that air is clear and messages will go out at the same time. It doesn't happen too often, but we found it noticeable enough in our testing.
I'm still curious how it happens at all, since NAV synchronisation should prevent it at a much lower level?
johannes
Quoted 5 lines
Hi Alexis,
Quoted 2 lines
This is loosely based on RFC5148, specifically event-triggered message generation as described in section 5.2.
Quoted 8 lines
I'm confused. I see how that generally seems to apply to any mobile network, but it *does* state up-front that
In some instances, these problems can be solved in these lower layers, but in other instances, some help at the network and higher layers is necessary.I believe 802.11 *does* in fact solve these issues at lower layers. Can you explain how you observed any problem in this area?
Well it certainly attempts to via stuff like carrier sense. But that is not fool proof and any time two routers hear a frame and both decide to forward it immediately there is a chance that they will both sense the air at the same time, decide that it is clear, and lose both their forwarded frames due to a collision. How often that happens is hard to say but we have observed that exact behavior a few years ago with an 802.11 multicast routing protocol and adding jitter significantly improved reliability.
An example of where this would be solved at a lower layer would be something like a TDMA network that has better mechanisms to ensure that multiple devices do not send at the same time.
Quoted 6 lines
Quoted 2 lines
The frames are not duplicated, but, hopefully offset enough so they don't collide at the receiver
That wasn't my question - my question regarding duplicating was if this was
intended to *suppress* duplicates, but it sounds like not.
No, it's not intended to suppress duplicates.
-- Jesse
Johannes Berg
maintainerQuoted 9 lines
Well it certainly attempts to via stuff like carrier sense. But that is not fool proof and any time two routers hear a frame and both decide to forward it immediately there is a chance that they will both sense the air at the same time, decide that it is clear, and lose both their forwarded frames due to a collision. How often that happens is hard to say but we have observed that exact behavior a few years ago with an 802.11 multicast routing protocol and adding jitter significantly improved reliability.
I'm really surprised by this since they both should jitter their
transmissions already between CWmin and CWmax. Is that window somehow really super small for what you're doing?
johannes
Quoted 9 lines
Quoted 8 lines
Well it certainly attempts to via stuff like carrier sense. But that is not fool proof and any time two routers hear a frame and both decide to forward it immediately there is a chance that they will both sense the air at the same time, decide that it is clear, and lose both their forwarded frames due to a collision. How often that happens is hard to say but we have observed that exact behavior a few years ago with an 802.11 multicast routing protocol and adding jitter significantly improved reliability.
Quoted 4 lines
I'm really surprised by this since they both should jitter their transmissions
already between CWmin and CWmax. Is that window somehow really super small for what you're doing?
I don't think so.
-- Jesse
Quoted 10 lines · Johannes Berg
Quoted 9 lines
Well it certainly attempts to via stuff like carrier sense. But that is not fool proof and any time two routers hear a frame and both decide to forward it immediately there is a chance that they will both sense the air at the same time, decide that it is clear, and lose both their forwarded frames due to a collision. How often that happens is hard to say but we have observed that exact behavior a few years ago with an 802.11 multicast routing protocol and adding jitter significantly improved reliability.
Quoted 5 lines
I'm really surprised by this since they both should jitter their
transmissions already between CWmin and CWmax. Is that window somehow really super small for what you're doing?johannes
Isn't CWmin and CWmax only used for retries?
We recently had the problem that on 5MHz channels probe-responses of APs which can't hear each other (hidden node problem) always collide. See [1] for a trace showing the problem.
Yellow is the probe-request (and ack on success), the other colours are 3 APs.
Putting probe-responses on their own queue with it's own timing results in [2] and seems to make the problem less worse.
However the first frame still always collides, and only subsequent retries have the randomness of cwmin/cwmax added.
5MHz channels make the problem worse since frames are 4 times longer.
I'm currently trying to find a way to add some randomness to the initial response, which it seems this patchset attempts to solve as well (different context though).
[1] http://may.nu/images/problem.png
[2] http://may.nu/images/jittered.png
Quoted 2 lines · Matthias May
[1] http://may.nu/images/problem.png
[2] http://may.nu/images/jittered.png
I get 404 "Not Found" for these.
Signature · 1 line
Kalle Valo
These images work intermittently for me. Here they are rehosted:
[1] http://i.imgur.com/zM0eLNk.png
[2] http://i.imgur.com/E7GL7U3.png
Quoted 9 lines · Kalle Valo
Quoted 2 lines · Matthias May
[1] http://may.nu/images/problem.png
[2] http://may.nu/images/jittered.pngI get 404 "Not Found" for these.
--
Kalle Valo
Am 09.03.2017 um 16:49 schrieb Matthias May:
Quoted 26 lines · Johannes Berg
Quoted 8 lines
Quoted 8 lines
Well it certainly attempts to via stuff like carrier sense. But that is not fool proof and any time two routers hear a frame and both decide to forward it immediately there is a chance that they will both sense the air at the same time, decide that it is clear, and lose both their forwarded frames due to a collision. How often that happens is hard to say but we have observed that exact behavior a few years ago with an 802.11 multicast routing protocol and adding jitter significantly improved reliability.
Quoted 5 lines
I'm really surprised by this since they both should jitter their
transmissions already between CWmin and CWmax. Is that window somehow really super small for what you're doing?johannes
Isn't CWmin and CWmax only used for retries?
We recently had the problem that on 5MHz channels probe-responses of APs which can't hear each other (hidden node problem) always collide. See [1] for a trace showing the problem.
Yellow is the probe-request (and ack on success), the other colours are 3 APs.
Putting probe-responses on their own queue with it's own timing results in [2] and seems to make the problem less worse.
However the first frame still always collides, and only subsequent retries have the randomness of cwmin/cwmax added.
5MHz channels make the problem worse since frames are 4 times longer.
Quoted 6 lines
I'm currently trying to find a way to add some randomness to the initial response, which it seems this patchset attempts to solve as well (different context though).
[1] http://may.nu/images/problem.png
[2] http://may.nu/images/jittered.png
How do you measure this signals ? Maybe the first choose of in the contention window is the same for all nodes caused by simulation, or so ... In general the chance for choosing all nodes the same waiting value is 1/16 * n (for best effort). So for 3 nodes it seems unlikely.
But from first look on your pictures, CW seems to work, since the cyan AP is slightly earlier then magenta and green one, which may the distance of some slot times. But of course for hidden stations this (at best) 16 slot times (which may be only 5 to 8 slot times in average) are much shorter than the actual probe response air time. Would they have proper carrier sense they would not collide. The jitter of path request are also only a bit of more gambling, which may help ... at this point the client should probe a smaller set of APs a time, but the APs cannot change their behavior ...
But the actual patch fro PREPs have another goal. Since they could only collide, if multiple routes to destination exists, it might help to spread the a bit. But from what I see, every PREP is jittered. Maybe the first PREP should not be artificially delayed, but all following PREPs of this specific PREQ (which mostly only contain redundant routes, without a better ALM).
kind regards
Signature · 15 lines
M.Sc. Benjamin Beichler Universität Rostock, Fakultät für Informatik und Elektrotechnik Institut für Angewandte Mikroelektronik und Datentechnik University of Rostock, Department of CS and EE Institute of Applied Microelectronics and CE Richard-Wagner-Straße 31 18119 Rostock Deutschland/Germany phone: +49 (0) 381 498 - 7278 email: [email protected] www: http://www.imd.uni-rostock.de/
Johannes Berg
maintainerQuoted 2 lines
Isn't CWmin and CWmax only used for retries?
No.
Quoted 2 lines
We recently had the problem that on 5MHz channels probe-responses of APs which can't hear each other (hidden node problem) always collide.
I think this is what I neglected - if the APs won't hear each other, all their own sensing and NAV won't help since it'll never be updated.
CWmin/max are short enough to not actually matter in this case since they're not long enough to avoid colliding entirely even if one picks the lowest and the other the largest possible value.
johannes
Quoted 14 lines · Jesse Jones
Quoted 5 lines
Hi Alexis,
Quoted 2 lines
This is loosely based on RFC5148, specifically event-triggered message generation as described in section 5.2.
Quoted 8 lines
I'm confused. I see how that generally seems to apply to any mobile network, but it *does* state up-front that
In some instances, these problems can be solved in these lower layers, but in other instances, some help at the network and higher layers is necessary.I believe 802.11 *does* in fact solve these issues at lower layers. Can you explain how you observed any problem in this area?
Quoted 7 lines
Well it certainly attempts to via stuff like carrier sense. But that is not fool proof and any time two routers hear a frame and both decide to forward it immediately there is a chance that they will both sense the air at the same time, decide that it is clear, and lose both their forwarded frames due to a collision. How often that happens is hard to say but we have observed that exact behavior a few years ago with an 802.11 multicast routing protocol and adding jitter significantly improved reliability.
Have you tried performing RTS/CTS before sending path selection frames to manage the hidden node problem?
Signature · 1 line
thomas
Johannes Berg
maintainerHi,
So I guess after all the discussion, you should amend the commit log a bit, certainly at least to mention the hidden-node issue.
Regarding the patch itself, I'm not super happy with how big it is, some additional comments below:
net/mac80211/ieee80211_i.h struct mesh_preq_queue { · line 336
Quoted 4 lines
net/mac80211/ieee80211_i.h +4
-0+struct mesh_tx_queue { +struct list_head list; +struct sk_buff *skb; +};
This seems awkward, what's wrong with using an SKB list (struct sk_buff_head, skb_queue_* etc)?
net/mac80211/ieee80211_i.h struct ieee80211_if_mesh { · line 679
Quoted 2 lines
net/mac80211/ieee80211_i.h +2
-0+/* Spinlock for trasmitted MPATH frames */ +spinlock_t mesh_tx_queue_lock;
That would also contain the extra spinlock.
net/mac80211/ieee80211_i.h struct ieee80211_if_mesh { · line 680
Quoted 1 line
net/mac80211/ieee80211_i.h +1
-0+struct mesh_tx_queue tx_queue;
This was always a bad idea, since you never need the skb pointer here - should've just used struct list_head.
net/mac80211/ieee80211_i.h struct ieee80211_if_mesh { · line 681
Quoted 1 line
net/mac80211/ieee80211_i.h +1
-0+int tx_queue_len;
Also contained in the skb queue.
net/mac80211/ieee80211_i.h struct ieee80211_sub_if_data { · line 932
Quoted 1 line
net/mac80211/ieee80211_i.h +1
-0+struct delayed_work tx_work;
I don't really see any value here for a delayed work - a pure timer would work just as well?
Also, these fields should be in ifmsh, I think?
johannes
Johannes Berg
maintainerSorry - this is the other half of my reply that I accidentally deleted before sending...
net/mac80211/iface.c static int ieee80211_open(struct net_device *dev) · line 790
Quoted 11 lines
net/mac80211/iface.c +8
-0+static void flush_tx_skbs (struct ieee80211_sub_if_data *sdata) +{ +struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh; +struct mesh_tx_queue *tx_node; + +spin_lock_bh (&ifmsh->mesh_tx_queue_lock); + +/* Note that this check is important because of the two- stage
net/mac80211/iface.c +2
-0+* way that ieee80211_if_mesh is initialized. +*/
I think you should fix that rather than work around it. If this is called with iftype != mesh then this is super problematic anyway, since ifmsh->tx_queue_len would alias some other variable (there's a union).
Quoted 9 lines
(quoted diff) +2
-0+ if (ifmsh->tx_queue_len > 0) { + mhwmp_dbg(sdata, "flushing %d skbs", ifmsh-Quoted 1 line
tx_queue_len);net/mac80211/iface.c +3
-0+ +while (!list_empty (&ifmsh->tx_queue.list)) { + tx_node = list_last_entry(&ifmsh-Quoted 1 line
tx_queue.list,
(quoted diff) +1
-0+ struct
mesh_tx_queue, list);
net/mac80211/iface.c static int ieee80211_open(struct net_device *dev) · line 805
Quoted 9 lines
net/mac80211/iface.c +9
-0+kfree_skb (tx_node->skb); +list_del (&tx_node->list); +kfree (tx_node); + } + ifmsh->tx_queue_len =0 ; + } + +spin_unlock_bh (&ifmsh->mesh_tx_queue_lock); +}
All of this also gets *vastly* simpler if it's just skb_queue_purge() :)
net/mac80211/iface.c static int ieee80211_open(struct net_device *dev) · line 821
Quoted 5 lines
net/mac80211/iface.c +5
-0+spin_lock_bh (&ifmsh->mesh_tx_queue_lock); + +list_for_each_entry (tx_node, &ifmsh->tx_queue.list, list) { +ieee80211_tx_skb (sdata, tx_node->skb); + }
I don't think you should hold the lock across _tx_skb(), ISTR problems with that - particularly with the STA lock, so this might be OK, but it might also cause lock ordering issues. It's easy to avoid anyway, so better not to do it.
johannes
Hi Johannes,
Thank you for the comments, I'll see if I can apply all of your suggestions and resubmit.
Alexis
Quoted 53 lines · Johannes Berg
Sorry - this is the other half of my reply that I accidentally deleted before sending...
net/mac80211/iface.c static int ieee80211_open(struct net_device *dev) · line 790
Quoted 11 lines
net/mac80211/iface.c +8
-0+static void flush_tx_skbs (struct ieee80211_sub_if_data *sdata) +{ +struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh; +struct mesh_tx_queue *tx_node; + +spin_lock_bh (&ifmsh->mesh_tx_queue_lock); + +/* Note that this check is important because of the two- stage
net/mac80211/iface.c +2
-0+* way that ieee80211_if_mesh is initialized. +*/ I think you should fix that rather than work around it. If this is called with iftype != mesh then this is super problematic anyway, since
ifmsh->tx_queue_lenwould alias some other variable (there's a union).Quoted 9 lines
(quoted diff) +2
-0+ if (ifmsh->tx_queue_len > 0) { + mhwmp_dbg(sdata, "flushing %d skbs", ifmsh-Quoted 1 line
tx_queue_len);net/mac80211/iface.c +3
-0+ +while (!list_empty (&ifmsh->tx_queue.list)) { + tx_node = list_last_entry(&ifmsh-Quoted 1 line
tx_queue.list,
+ struct
mesh_tx_queue, list);net/mac80211/iface.c static int ieee80211_open(struct net_device *dev) · line 805
Quoted 9 lines
net/mac80211/iface.c +9
-0+kfree_skb (tx_node->skb); +list_del (&tx_node->list); +kfree (tx_node); + } + ifmsh->tx_queue_len =0 ; + } + +spin_unlock_bh (&ifmsh->mesh_tx_queue_lock); +}All of this also gets *vastly* simpler if it's just
skb_queue_purge():)net/mac80211/iface.c static int ieee80211_open(struct net_device *dev) · line 821
Quoted 5 lines
net/mac80211/iface.c +5
-0+spin_lock_bh (&ifmsh->mesh_tx_queue_lock); + +list_for_each_entry (tx_node, &ifmsh->tx_queue.list, list) { +ieee80211_tx_skb (sdata, tx_node->skb); + }I don't think you should hold the lock across
_tx_skb(), ISTR problems with that - particularly with the STA lock, so this might be OK, but it might also cause lock ordering issues. It's easy to avoid anyway, so better not to do it.johannes