batman-adv: promisc destination reception
Hi everyone!
I've recently been wondering, if promiscuous packet reception could be used to enhance the probability of receiving data packets. The idea behind it is, to not feel bothered by the broadcast characteristic of WiFi but instead utilising this fact (it's a little bit inspired by COPE which also "exploits the broadcast property of radios instead of hiding it under an artificial abstraction"[1]).
The good thing about batman-adv is, that it is running in kernelspace and we have batman packet headers around the data already, so we are technically able to have a glance at all the packets we are receiving on the WiFi interface (which would not be doable in userspace on embedded devices).
The following rather simple patches are adding sequence numbers and duplicate checks for unicast data packets as well as the possiblity to receive unicast packets promiscuously on the final destination node. Especially in circular topologies like [2], this boosts the probability of reception from 53.1441% to ~99.7937% for instance with no additional packet overhead needed despite the unicast sequence numbers + originator address.
With the planned neighbor discovery protocol and the 2-hop-neighbourhood information it provides, the probability could be boosted even further, even in non-circular topologies.
However, I'm still having quite some difficulties with getting the desired effect in a VM setup. I'm not quite sure yet if this is an issue of these few patches, the setup configuration(, the hash-implementation in the trunk) or a routing issue. See the setup details below.
Cheers, Linus
[1]: XORs in the air: practical wireless network coding
by: Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, Jon Crowcroft
[2]: http://x-realis.dyndns.org/freifunk/circle-promisc-13-nodes.png
-----
I've tried to test and validate the assumptions in the following three node topology (with a "hub/broadcast" nature on C's links at least)
A -- 90% -- B
\ /
90% 60%
\ /
CWhere I'd expect to have (0.9 * 0.9)^2 = 0.6561 sucessful icmp replies with ping without the patches, and ((0.9 * 0.9) + (1 - 0.9 * 0.9) * 0.6)^2 = 0.853776 sucessful icmp replies with ping and with the patches.
For the actual setup, I've started three VMs, with A and B having two interfaces, vmtap1 and vmtap2, vmtap4 and vmtap5 and C having just one, vmtap7. They're bridged like this:
---
mesh0 8000.7a538525c787 no vmtap1
vmtap4
mesh1 8000.1a48b2e5ec2d no vmtap2
vmtap5 vmtap7
---
and "brctl setageing mesh0/1 0" to simulate a hub.
I simulated the link qualities stated above with tc inside of the VMs:
ssh vm1 "sudo tc qdisc add dev eth1 root netem loss 10%" ssh vm1 "sudo tc qdisc add dev eth2 root netem loss 10%" ssh vm2 "sudo tc qdisc add dev eth2 root netem loss 40%"
What I further did, is setting the hop penalty to 0, to force C to only send to B via A and to force B to only send to C via A too and to avoid tc's flakiness, which resulted to one-hop-connections between C and B quite often. I verified,
However, when I'm now trying to ping from B to C now, C receives B's icmp sucessfully but B does not receive the reply.
My first guess was, the first thing that seemed odd to me was, that the hash_find() in check_duplicate() returned NULL quite often on B according to some printk()s, resulting in dropped packets - but that turned out to be the own packet from B which was just sent and now also received promiscuously right away again.
Well, probably I'm just having something in the patches or setup wrong, I'm going to do some more tests with some more printk()s. However, if someone can spot something weird or would like to test the patches already, I'd be happy about any feedback :).
PATCH 1/3 batman-adv: Allow promiscuous reception of unicast packets
From: Linus Lüssing <[email protected]>
A very mobile node may want to enable this to increase the probability of unicast data reception on the last hop, especially when such a mobile node moves towards the sender.
The mobile node needs to place its hard-interfaces utilized by batman-adv into promisc-mode to let this optimization take effect. Be aware, that doing so will cost your devices more processing power.
It also increases the probability of succesful reception a lot, if there are (multiple) shorter, alternate but slightly "worse" paths, too. As WiFi is a broadcast medium, there can be a quite good chance to receive a packet from one of the nodes on the path to the receiver already.
Luckily batman-adv is running in kernelspace, therefore it does not make much of a performance difference, even on embedded devices.
To let this feature take effect, place your WiFi interface in promiscuous mode (e.g. 'ip link set wlan0 promisc on'/'ifconfig wlan0 promisc').
--- routing.c | 17 +++++++++++++---- 1 files changed, 13 insertions(+), 4 deletions(-)
routing.c +13 -4
@@ -1124,7 +1124,7 @@ static int check_unicast_packet(struct sk_buff *skb, int hdr_size)/* not for me */ if (!is_my_mac (ethhdr->h_dest)) -return -1 ; +return 1 ;return 0 ; }
@@ -1214,8 +1214,10 @@ int recv_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if) {struct unicast_packet *unicast_packet;int hdr_size =sizeof (struct unicast_packet ); +int check_ret; -if (check_unicast_packet (skb, hdr_size) <0 ) + check_ret =check_unicast_packet (skb, hdr_size); +if (check_ret <0 )return NET_RX_DROP ; unicast_packet = (struct unicast_packet *)skb->data;
@@ -1226,6 +1228,9 @@ int recv_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if)return NET_RX_SUCCESS ; } +if (check_ret) +return NET_RX_DROP ; +return route_unicast_packet (skb, recv_if, hdr_size); }
@@ -1235,9 +1240,10 @@ int recv_ucast_frag_packet(struct sk_buff *skb, struct batman_if *recv_if)struct unicast_frag_packet *unicast_packet;int hdr_size =sizeof (struct unicast_frag_packet );struct sk_buff *new_skb =NULL ; -int ret; +int ret, check_ret; -if (check_unicast_packet (skb, hdr_size) <0 ) + check_ret =check_unicast_packet (skb, hdr_size); +if (check_ret <0 )return NET_RX_DROP ; unicast_packet = (struct unicast_frag_packet *)skb->data;
@@ -1259,6 +1265,9 @@ int recv_ucast_frag_packet(struct sk_buff *skb, struct batman_if *recv_if)return NET_RX_SUCCESS ; } +if (check_ret) +return NET_RX_DROP ; +return route_unicast_packet (skb, recv_if, hdr_size); }
Signature · 1 line
1.7.1
PATCH 2/3 batman-adv: Generic sequence number checking for data packets
In reply to Linus LüssingFrom: Linus Lüssing <[email protected]>
This reduces the size of recv_bcast_packet, increasing its readability. It further introduces a generic function for duplicate checking for data packets (which might later be used for multicast or promiscous unicast packet handling or other packets).
--- originator.c | 2 +- routing.c | 86 +++++++++++++++++++++++++++++++++++---------------------- types.h | 10 +++++-- 3 files changed, 61 insertions(+), 37 deletions(-)
originator.c +1 -1
@@ -147,7 +147,7 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr)memcpy (orig_node->orig, addr,ETH_ALEN ); orig_node->router =NULL ; orig_node->hna_buff =NULL ; - orig_node->bcast_seqno_reset = jiffies -1 + orig_node->bcast_seqno_state.seqno_reset = jiffies -1 -msecs_to_jiffies (RESET_PROTECTION_MS ); orig_node->batman_seqno_reset = jiffies -1 -msecs_to_jiffies (RESET_PROTECTION_MS );
routing.c +53 -33
109 lines not on this page · raw message
types.h +7 -3
@@ -49,6 +49,12 @@ struct batman_if {struct rcu_head rcu; }; +struct seqno_state { +unsigned long seqno_reset; +uint32_t last_seqno; +TYPE_OF_WORD bits[NUM_WORDS ]; +}; +/** * orig_node - structure for orig_list maintaining nodes of mesh * @primary_addr: hosts primary interface address
@@ -73,7 +79,6 @@ struct orig_node {uint8_t tq_own;int tq_asym_penalty;unsigned long last_valid; -unsigned long bcast_seqno_reset;unsigned long batman_seqno_reset;uint8_t gw_flags;uint8_t flags;
@@ -81,11 +86,10 @@ struct orig_node {int16_t hna_buff_len;uint32_t last_real_seqno;uint8_t last_ttl; -TYPE_OF_WORD bcast_bits[NUM_WORDS ]; -uint32_t last_bcast_seqno;struct list_head neigh_list;struct list_head frag_list;unsigned long last_frag_packet; +struct seqno_state bcast_seqno_state;struct {uint8_t candidates;struct neigh_node *selected;
Signature · 1 line
1.7.1
PATCH 3/3 batman-adv: Add sequence number and duplicate checks for unicasts
In reply to Linus LüssingFrom: Linus Lüssing <[email protected]>
When a node is set in promiscuous mode it might receive a unicast data packet more than once. Therefore sequence number checking is required.
--- originator.c | 2 ++ packet.h | 4 +++- routing.c | 11 ++++++++++- soft-interface.c | 1 + types.h | 2 ++ unicast.c | 6 ++++++ 6 files changed, 24 insertions(+), 2 deletions(-)
originator.c +2 -0
@@ -147,6 +147,8 @@ struct orig_node *get_orig_node(struct bat_priv *bat_priv, uint8_t *addr)memcpy (orig_node->orig, addr,ETH_ALEN ); orig_node->router =NULL ; orig_node->hna_buff =NULL ; + orig_node->ucast_seqno_state.seqno_reset = jiffies -1 + -msecs_to_jiffies (RESET_PROTECTION_MS ); orig_node->bcast_seqno_state.seqno_reset = jiffies -1 -msecs_to_jiffies (RESET_PROTECTION_MS ); orig_node->batman_seqno_reset = jiffies -1
packet.h +3 -1
@@ -32,7 +32,7 @@#define BAT_UNICAST_FRAG 0x06/* this file is included by batctl which needs these defines */ -#define COMPAT_VERSION 12 +#define COMPAT_VERSION 13#define DIRECTLINK 0x40#define VIS_SERVER 0x20#define PRIMARIES_FIRST_HOP 0x10
@@ -98,7 +98,9 @@ struct icmp_packet_rr {struct unicast_packet {uint8_t packet_type;uint8_t version;/* batman version field */ +uint8_t orig[6 ];uint8_t dest[6 ]; +uint32_t seqno;uint8_t ttl; } __attribute__((packed));
routing.c +10 -1
@@ -1146,6 +1146,9 @@ static inline int check_duplicate(struct bat_priv *bat_priv, uint8_t *orig,case BAT_BCAST : seqno_state = &orig_node->bcast_seqno_state;break ; +case BAT_UNICAST : + seqno_state = &orig_node->ucast_seqno_state; +break ;default : goto out; }
@@ -1261,9 +1264,10 @@ int route_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if,int recv_unicast_packet (struct sk_buff *skb,struct batman_if *recv_if) { +struct bat_priv *bat_priv =netdev_priv (recv_if->soft_iface);struct unicast_packet *unicast_packet;int hdr_size =sizeof (struct unicast_packet ); -int check_ret; +int ret, check_ret; check_ret =check_unicast_packet (skb, hdr_size);if (check_ret <0 )
@@ -1271,6 +1275,11 @@ int recv_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if) unicast_packet = (struct unicast_packet *)skb->data; + ret =check_duplicate (bat_priv, unicast_packet->orig, +ntohl (unicast_packet->seqno),BAT_UNICAST ); +if (ret) +return NET_RX_DROP ; +/* packet for me */ if (is_my_mac (unicast_packet->dest)) {interface_rx (recv_if->soft_iface, skb, recv_if, hdr_size);
soft-interface.c +1 -0
@@ -596,6 +596,7 @@ struct net_device *softif_create(char *name)atomic_set (&bat_priv->batman_queue_left,BATMAN_QUEUE_LEN );atomic_set (&bat_priv->mesh_state,MESH_INACTIVE ); +atomic_set (&bat_priv->ucast_seqno,1 );atomic_set (&bat_priv->bcast_seqno,1 );atomic_set (&bat_priv->hna_local_changed,0 );
types.h +2 -0
@@ -89,6 +89,7 @@ struct orig_node {struct list_head neigh_list;struct list_head frag_list;unsigned long last_frag_packet; +struct seqno_state ucast_seqno_state;struct seqno_state bcast_seqno_state;struct {uint8_t candidates;
@@ -136,6 +137,7 @@ struct bat_priv {atomic_t orig_interval;/* uint */ atomic_t hop_penalty;/* uint */ atomic_t log_level;/* uint */ +atomic_t ucast_seqno;atomic_t bcast_seqno;atomic_t bcast_queue_left;atomic_t batman_queue_left;
unicast.c +6 -0
@@ -323,6 +323,12 @@ int unicast_send_skb(struct sk_buff *skb, struct bat_priv *bat_priv) unicast_packet->ttl =TTL ;/* copy the destination for faster routing */ memcpy (unicast_packet->dest, orig_node->orig,ETH_ALEN ); +/* copy the originator */ +memcpy (unicast_packet->orig, bat_priv->primary_if->net_dev->dev_addr, +ETH_ALEN ); +/* set unicast sequence number */ + unicast_packet->seqno = +htonl (atomic_inc_return (&bat_priv->ucast_seqno));if (atomic_read (&bat_priv->fragmentation) && data_len + sizeof(struct unicast_packet) >
Signature · 1 line
1.7.1
Re: [B.A.T.M.A.N.] [PATCH 3/3] batman-adv: Add sequence number and duplicate checks for unicasts
Review
Quoted 3 lines · On Sunday 07 November 2010 17:46:01 Linus Lüssing wrote:
/* this file is included by batctl which needs these defines */
(quoted diff) +1
-1-#define COMPAT_VERSION 12 +#define COMPAT_VERSION 13\
Please increase that to 14. 13 is already used in linux 2.6.37(-rc1)
Best regards,
Sven
Re: [B.A.T.M.A.N.] [PATCH 3/3] batman-adv: Add sequence number and duplicate checks for unicasts
Ah, thanks, oki doki.
I'm rectracting my Signed-off-by for now anyway, as I couldn't validate their effect yet. However, any feedback if this idea might or might not possibly work / make sense anyway is very welcome :).
Cheers, Linus
Quoted 9 lines · Sven Eckelmann
Review
Quoted 3 lines · On Sunday 07 November 2010 17:46:01 Linus Lüssing wrote:
/* this file is included by batctl which needs these defines */
(quoted diff) +1
-1-#define COMPAT_VERSION 12 +#define COMPAT_VERSION 13\Please increase that to 14. 13 is already used in linux 2.6.37(-rc1)
Best regards,
Sven
[B.A.T.M.A.N.] batman-adv promisc mode, further notes and recomendations
In reply to Linus LüssingHi,
After some discussions on IRC we've decided to skip the sequence number checking for now and to not care about forwarding a packet to the higher layers more than once. Usually, higher layer protocols are in charge and should be capable of detecting and coping not only with lost, but also duplicate packets. I'm not aware of any protocol which might have any difficulties with this (if you know one, please let me know). If you have special, "custom" protocol which is not able to cope with it, then you're adviced to not activate the promisc-mode on that node's interface.
I also did some further testing on how usable such a feature on embedded devices is. Smaller, less powerful devices like the Fonera 2.0 can have some performance decreases in a very busy, noisy mesh neighborhood. All other scenarios and more performant devices should be fine with the promisc mode, however feel free to do your own measurments to find out if this promisc-mode feature is suitable and benefitial for you (and share your experiences :) ).
Cheers,
Linus
PATCH v2 1/1 batman-adv: Allow promiscuous reception of unicast packets
In reply to Linus LüssingThis commits adds the possibility for the final destination node to also receive and accept unicast data packets promiscuously already from an arbitrary previous hop along the path, and not only the last previous hop.
This feature is especially useful in the following two scenarios:
Firstly, a very mobile node moving towards the sender along the hop path benefits from this as for such a mobility pattern the reception probability increases, no matter how slow the topology convergence speed is.
It also increases the probability of succesful reception a lot, if there are (multiple) shorter, alternate but slightly "worse" paths, too (like in a circular topology). As WiFi is a broadcast medium, there can be a quite good chance to receive a packet from one of the nodes on the path to the receiver already.
On smaller embedded devices, I would advice to run your own measurements before activating this feature. Depending on wifi chipset and driver as well as cpu, this can negatively affect your throughput.
To let this feature take effect, place your WiFi interface in promiscuous mode (e.g. 'ip link set wlan0 promisc on'/'ifconfig wlan0 promisc').
Also note, that higher layers might receive a data packet more than once. So if you have a special higher layer protocol that cannot deal with that, then do not activate the promisc mode on this node.
--- routing.c | 17 +++++++++++++---- 1 files changed, 13 insertions(+), 4 deletions(-)
routing.c +13 -4
@@ -1127,7 +1127,7 @@ static int check_unicast_packet(struct sk_buff *skb, int hdr_size)/* not for me */ if (!is_my_mac (ethhdr->h_dest)) -return -1 ; +return 1 ;return 0 ; }
@@ -1217,8 +1217,10 @@ int recv_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if) {struct unicast_packet *unicast_packet;int hdr_size =sizeof (struct unicast_packet ); +int check_ret; -if (check_unicast_packet (skb, hdr_size) <0 ) + check_ret =check_unicast_packet (skb, hdr_size); +if (check_ret <0 )return NET_RX_DROP ; unicast_packet = (struct unicast_packet *)skb->data;
@@ -1229,6 +1231,9 @@ int recv_unicast_packet(struct sk_buff *skb, struct batman_if *recv_if)return NET_RX_SUCCESS ; } +if (check_ret) +return NET_RX_DROP ; +return route_unicast_packet (skb, recv_if, hdr_size); }
@@ -1238,9 +1243,10 @@ int recv_ucast_frag_packet(struct sk_buff *skb, struct batman_if *recv_if)struct unicast_frag_packet *unicast_packet;int hdr_size =sizeof (struct unicast_frag_packet );struct sk_buff *new_skb =NULL ; -int ret; +int ret, check_ret; -if (check_unicast_packet (skb, hdr_size) <0 ) + check_ret =check_unicast_packet (skb, hdr_size); +if (check_ret <0 )return NET_RX_DROP ; unicast_packet = (struct unicast_frag_packet *)skb->data;
@@ -1262,6 +1268,9 @@ int recv_ucast_frag_packet(struct sk_buff *skb, struct batman_if *recv_if)return NET_RX_SUCCESS ; } +if (check_ret) +return NET_RX_DROP ; +return route_unicast_packet (skb, recv_if, hdr_size); }
Signature · 1 line
1.7.1
Re: [B.A.T.M.A.N.] [PATCHv2] batman-adv: Allow promiscuous reception of unicast packets
Quoted 3 lines · On Wednesday 10 November 2010 01:48:13 Linus Lüssing wrote:
Firstly, a very mobile node moving towards the sender along the hop path benefits from this as for such a mobility pattern the reception probability increases, no matter how slow the topology convergence speed is.
Would you mind explaining why you think it helps for mobile nodes in the scenario you mention ?
If I understand it correctly it helps for data originating from a non-mobile node traveling towards the mobile node but this is less critical (assuming the mobile node has a higher orig interval). For data originating at the mobile node traveling towards the non-mobile node it will only help if both nodes are single hop neighbors.
Regards,
Marek
[B.A.T.M.A.N.] Antwort: Re: [PATCHv2] batman-adv: Allow promiscuous reception of unicast packets
Marek Lindner <[email protected]> schrieb am 10.11.2010 12:06:18:
Quoted 10 lines
[Bild entfernt]
Re: [B.A.T.M.A.N.] [PATCHv2] batman-adv: Allow promiscuous reception of unicast packets
Marek Lindner
an:
The list for a Better Approach To Mobile Ad-hoc Networking, Linus
Lüssing
Quoted 5 lines
10.11.2010 12:08
[Bild entfernt]
Quoted 8 lines
Von:
Marek Lindner <[email protected]>
An:
"The list for a Better Approach To Mobile Ad-hoc Networking" <[email protected]>, Linus Lüssing
Quoted 3 lines · On Wednesday 10 November 2010 01:48:13 Linus Lüssing wrote:
Quoted 1 line
Firstly, a very mobile node moving towards the sender along the hop
path
Quoted 1 line
Quoted 1 line
benefits from this as for such a mobility pattern the reception
probability
Quoted 6 lines
Quoted 1 line
increases, no matter how slow the topology convergence speed is.
Would you mind explaining why you think it helps for mobile nodes in the
scenario you mention ?
If I understand it correctly it helps for data originating from a
non-mobile
Quoted 3 lines
node traveling towards the mobile node but this is less critical (assuming the
mobile node has a higher orig interval).
Correct, I was assuming equal intervals ;). Yes, this is usually not critical, but just
found it note worthy anyway, that you could possibly move towards the sender along the
path as fast as you wish without losing the stream from the sender, being independent
of the receivers OGM interval.
Quoted 2 lines
For data originating at the mobile
node traveling towards the non-mobile node it will only help if
bothnodes are
Quoted 1 line
single hop neighbors.
That's not what I've been claiming afaik :). And if both nodes are just one hop away, then
you don't have any advantage of this promisc-reception anyway.
Hope that paragraph did not cause too much confusion, if you think there's something misleading
in it, I can change it, no problem.
Quoted 3 lines
Regards,
Marek
Cheers,
Linus
Re: [B.A.T.M.A.N.] Antwort: Re: [PATCHv2] batman-adv: Allow promiscuous reception of unicast packets
Hi there,
Hmm, okay, and I made some further measurements. In typical scenarios with "default" settings, I unfortunately could not really get a reliability improvement. The thing is, due to the multicast rate of 1MBit/s in common wifi drivers, I wasn't able to put the devices close enough for the promisc-reception to take effect without BATMAN switching to the direct, shorter path. So I ended up setting the multicast rate to 48mbit/s and could get a reliability improvement from 14.5% packet loss down to about 9.5%. But of course, such a high multicast rate is not feasible.
So it'd be ok to ommit this patch, unless/until someone might have some further ideas to get the promisc-idea usable.
Cheers, Linus
Quoted 70 lines · Linus Luessing
Marek Lindner <[email protected]> schrieb am 10.11.2010 12:06:18:
Quoted 10 lines
[Bild entfernt]
Re: [B.A.T.M.A.N.] [PATCHv2] batman-adv: Allow promiscuous reception of unicast packets
Marek Lindner
an:
The list for a Better Approach To Mobile Ad-hoc Networking, Linus
Lüssing
Quoted 5 lines
10.11.2010 12:08
[Bild entfernt]
Quoted 8 lines
Von:
Marek Lindner <[email protected]>
An:
"The list for a Better Approach To Mobile Ad-hoc Networking" <[email protected]>, Linus Lüssing
Quoted 3 lines · On Wednesday 10 November 2010 01:48:13 Linus Lüssing wrote:
Quoted 1 line
Firstly, a very mobile node moving towards the sender along the hop
path
Quoted 1 line
Quoted 1 line
benefits from this as for such a mobility pattern the reception
probability
Quoted 6 lines
Quoted 1 line
increases, no matter how slow the topology convergence speed is.
Would you mind explaining why you think it helps for mobile nodes in the
scenario you mention ?
If I understand it correctly it helps for data originating from anon-mobile
Quoted 3 lines
node traveling towards the mobile node but this is less critical (assuming the
mobile node has a higher orig interval).Correct, I was assuming equal intervals ;). Yes, this is usually not critical, but just
found it note worthy anyway, that you could possibly move towards the sender along the
path as fast as you wish without losing the stream from the sender, being independent
of the receivers OGM interval.Quoted 2 lines
For data originating at the mobile
node traveling towards the non-mobile node it will only help ifbothnodes are
Quoted 1 line
single hop neighbors.
That's not what I've been claiming afaik :). And if both nodes are just one hop away, then
you don't have any advantage of this promisc-reception anyway.Hope that paragraph did not cause too much confusion, if you think there's something misleading
in it, I can change it, no problem.Quoted 3 lines
Regards,
MarekCheers,
Linus