[B.A.T.M.A.N.] [RFC] ELP

[B.A.T.M.A.N.] [RFC] ELP

[Marek Lindner]

Hi,

after numerous infrastructure changes in the past weeks ELP[1] slowly
approaches the state in which it can be tested and later merged into the
master branch.

Since its initial implementation by Linus Luessing last summer a lot has
happened:
 * the internal protocol name (NDP) was renamed to ELP
 * the old code was rebased on top of the master branch
 * the ELP code was adjusted to the many changes in our code base
 * several patches were squashed together
 * brought the code in sync with the spec
 * numerous bugs were fixed (buffer overflow, writing into random memory
   sections, memory corruptions, locking issues, elp packet length checks,
   printing the neighbors of the requested mesh only and many more)

The ELP code is the first to use the recently introduced routing protocol
abstraction. It is not compiled into batman-adv by default, therefore you
need to compile with CONFIG_BATMAN_ADV_BATMAN_V=y or modify the makefile.

Once the batman-adv kernel module has been loaded you can check for the
existence of the new routing protocol:

cat /sys/kernel/debug/batman_adv/routing_algos 
Available routing algorithms:
BATMAN IV
BATMAN V

To activate B.A.T.M.A.N. V (ELP) you should run the following command *before*
adding any interface via batctl:

echo -n "BATMAN V" > /sys/module/batman_adv/parameters/routing_algo

Caveats:
 * ELP alone (without OGMv2) isn't very useful because ELP handles single hop
 neighbors only. So don't expect to convert your entire mesh network to
 B.A.T.M.A.N. V just yet.
 * The batman-adv routing protocol abstraction still lacks the translation
 table integration which is why the following patches will lead to a kernel
 crash. The ELP repository[2] contains a patch to disable the TT propagation
 partially to mitigate the problem until a proper solution has been
 implemented.

Any comments and suggestions are appreciated. 

Regards,
Marek


[1] http://www.open-mesh.org/wiki/batman-adv/ELP
[2] http://git.open-mesh.org/?p=marek/batman-adv.git;a=shortlog;h=refs/heads/elp


Linus Luessing (5):
      batman-adv: ELP - adding basic infrastructure
      batman-adv: ELP - creating neighbor structures, updating LQs
      batman-adv: ELP - exporting neighbor list via debugfs
      batman-adv: ELP - adding sysfs parameter for elp interval
      batman-adv: ELP - add configurable minimum ELP packet length (def: 300B)

 Makefile                   |    2 +
 Makefile.kbuild            |    1 +
 README.external            |    1 +
 bat_algo.h                 |    6 +
 bat_debugfs.c              |   16 ++
 bat_sysfs.c                |    8 +
 bat_v_elp.c                |  500 ++++++++++++++++++++++++++++++++++++++++++++
 gen-compat-autoconf.sh     |    1 +
 hard-interface.c           |    7 +
 main.c                     |    1 +
 packet.h                   |   20 ++-
 sysfs-class-net-batman-adv |   13 ++
 types.h                    |   15 ++
 13 files changed, 590 insertions(+), 1 deletions(-)

[B.A.T.M.A.N.] [RFC 1/5] batman-adv: ELP - adding basic infrastructure

[Marek Lindner]

From: Linus Luessing <linus.luessing@web.de>

The B.A.T.M.A.N. protocol originally only used a single message type (called
OGM) to determine the link qualities to the direct neighbors and spreading these
link quality information through the whole mesh. This procedure is summarized on
the BATMAN concept page and explained in details in the RFC draft published in
2008.

This approach was chosen for its simplicity during the protocol design phase and
the implementation. However, it also bears some drawbacks:

 *  Wireless interfaces usually come with some packet loss, therefore a higher
    broadcast rate is desirable to allow a fast reaction on flaky connections.
    Other interfaces of the same host might be connected to Ethernet LANs / VPNs
    / etc which rarely exhibit packet loss would benefit from a lower broadcast
    rate to reduce overhead.
 *  It generally is more desirable to detect local link quality changes at a
    faster rate than propagating all these changes through the entire mesh (the
    far end of the mesh does not need to care about local link quality changes
    that much). Other optimizations strategies, like reducing overhead, might be
    possible if OGMs weren't used for all tasks in the mesh at the same time.

As a result detecting local link qualities shall be handled by an independent
message type, ELP, whereas the OGM message type remains responsible for flooding
the mesh with these link quality information and determining the overall path
transmit qualities.

Developed by Linus during a 6 months trainee study period in Ascom (Switzerland)
AG.

Signed-off-by: Linus Luessing <linus.luessing@web.de>
Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
---
 Makefile               |    2 +
 Makefile.kbuild        |    1 +
 README.external        |    1 +
 bat_algo.h             |    6 ++
 bat_v_elp.c            |  175 ++++++++++++++++++++++++++++++++++++++++++++++++
 gen-compat-autoconf.sh |    1 +
 hard-interface.c       |    6 ++
 main.c                 |    1 +
 packet.h               |   14 ++++-
 types.h                |    6 ++
 10 files changed, 212 insertions(+), 1 deletions(-)
 create mode 100644 bat_v_elp.c

diff --git a/Makefile b/Makefile
index ac84fba..3d08354 100644
--- a/Makefile
+++ b/Makefile
@@ -25,6 +25,8 @@ export CONFIG_BATMAN_ADV_DEBUG=n
 export CONFIG_BATMAN_ADV_BLA=y
 # B.A.T.M.A.N. distributed ARP table:
 export CONFIG_BATMAN_ADV_DAT=y
+# B.A.T.M.A.N. V routing algorithm (experimental):
+# export CONFIG_BATMAN_ADV_BATMAN_V=y
 
 PWD:=$(shell pwd)
 KERNELPATH ?= /lib/modules/$(shell uname -r)/build
diff --git a/Makefile.kbuild b/Makefile.kbuild
index ad002cd..dcffb7f 100644
--- a/Makefile.kbuild
+++ b/Makefile.kbuild
@@ -21,6 +21,7 @@
 obj-$(CONFIG_BATMAN_ADV) += batman-adv.o
 batman-adv-y += bat_debugfs.o
 batman-adv-y += bat_iv_ogm.o
+batman-adv-$(CONFIG_BATMAN_ADV_BATMAN_V) += bat_v_elp.o
 batman-adv-y += bat_sysfs.o
 batman-adv-y += bitarray.o
 batman-adv-$(CONFIG_BATMAN_ADV_BLA) += bridge_loop_avoidance.o
diff --git a/README.external b/README.external
index 95a7eb4..f1ec46a 100644
--- a/README.external
+++ b/README.external
@@ -38,6 +38,7 @@ module).  Available  options  and  their    possible   values are
  * CONFIG_BATMAN_ADV_DEBUG=[y|n*] (B.A.T.M.A.N. debugging)
  * CONFIG_BATMAN_ADV_BLA=[y*|n] (B.A.T.M.A.N. bridge loop avoidance)
  * CONFIG_BATMAN_ADV_DAT=[y*|n] (B.A.T.M.A.N. Distributed ARP Table)
+ * CONFIG_BATMAN_ADV_BATMAN_V=[y|n*] (B.A.T.M.A.N. V routing algorithm)
 
 e.g., debugging can be enabled by
 
diff --git a/bat_algo.h b/bat_algo.h
index 9852a68..2932082 100644
--- a/bat_algo.h
+++ b/bat_algo.h
@@ -24,4 +24,10 @@
 
 int bat_iv_init(void);
 
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+int bat_v_init(void);
+#else
+#define bat_v_init(...)		{}
+#endif /* CONFIG_BATMAN_ADV_BATMAN_V */
+
 #endif /* _NET_BATMAN_ADV_BAT_ALGO_H_ */
diff --git a/bat_v_elp.c b/bat_v_elp.c
new file mode 100644
index 0000000..c2dee5c
--- /dev/null
+++ b/bat_v_elp.c
@@ -0,0 +1,175 @@
+/*
+ * Copyright (C) 2011-2012 B.A.T.M.A.N. contributors:
+ *
+ * Linus Lüssing, Marek Lindner
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA
+ *
+ */
+
+#include "main.h"
+#include "hard-interface.h"
+#include "send.h"
+#include "bat_algo.h"
+
+static void bat_v_elp_start_timer(struct hard_iface *hard_iface)
+{
+	unsigned long elp_interval;
+
+	elp_interval = msecs_to_jiffies(atomic_read(&hard_iface->elp_interval)
+					 - JITTER + (random32() % 2 * JITTER));
+
+	queue_delayed_work(bat_event_workqueue,
+			   &hard_iface->elp_wq, elp_interval);
+}
+
+static void bat_v_elp_send_outstanding(struct work_struct *work)
+{
+	struct hard_iface *hard_iface;
+	struct bat_priv *bat_priv;
+	struct batman_elp_packet *elp_packet;
+	struct sk_buff *skb;
+
+	hard_iface = container_of(work, struct hard_iface, elp_wq.work);
+	bat_priv = netdev_priv(hard_iface->soft_iface);
+
+	if (atomic_read(&bat_priv->mesh_state) == MESH_DEACTIVATING)
+		goto out;
+
+	if ((hard_iface->if_status == IF_NOT_IN_USE) ||
+	    (hard_iface->if_status == IF_TO_BE_REMOVED))
+		goto out;
+
+	/* the interface was enabled but may not be ready yet */
+	if (hard_iface->if_status != IF_ACTIVE)
+		goto restart_timer;
+
+	skb = skb_copy(hard_iface->elp_skb, GFP_ATOMIC);
+	if (!skb)
+		goto out;
+
+	elp_packet = (struct batman_elp_packet *)skb->data;
+	elp_packet->seqno = htonl(atomic_read(&hard_iface->elp_seqno));
+	elp_packet->num_neighbors = 0;
+
+	bat_dbg(DBG_BATMAN, bat_priv,
+		"Sending elp packet on interface %s, seqno %d\n",
+		hard_iface->net_dev->name, atomic_read(&hard_iface->elp_seqno));
+
+	send_skb_packet(skb, hard_iface, broadcast_addr);
+
+	atomic_inc(&hard_iface->elp_seqno);
+	bat_v_elp_start_timer(hard_iface);
+
+out:
+	return;
+}
+
+static int bat_v_elp_iface_enable(struct hard_iface *hard_iface)
+{
+	struct batman_elp_packet *elp_packet;
+	unsigned long random_seqno;
+	int res = -1;
+
+	INIT_HLIST_HEAD(&hard_iface->neigh_list);
+	spin_lock_init(&hard_iface->neigh_list_lock);
+
+	hard_iface->elp_skb = dev_alloc_skb(ETH_DATA_LEN + ETH_HLEN);
+	if (!hard_iface->elp_skb)
+		goto out;
+
+	skb_reserve(hard_iface->elp_skb, ETH_HLEN + BATMAN_ELP_HLEN);
+	elp_packet = (struct batman_elp_packet *)skb_push(hard_iface->elp_skb,
+							  BATMAN_ELP_HLEN);
+	memset(elp_packet, 0, BATMAN_ELP_HLEN);
+
+	elp_packet->header.packet_type = BAT_V_ELP;
+	elp_packet->header.version = COMPAT_VERSION;
+	elp_packet->header.ttl = 0;
+
+	/* randomize initial seqno to avoid collision */
+	get_random_bytes(&random_seqno, sizeof(unsigned long));
+	atomic_set(&hard_iface->elp_seqno, (uint32_t)random_seqno);
+
+	INIT_DELAYED_WORK(&hard_iface->elp_wq, bat_v_elp_send_outstanding);
+	bat_v_elp_start_timer(hard_iface);
+	res = 0;
+
+out:
+	return res;
+}
+
+static void bat_v_elp_iface_disable(struct hard_iface *hard_iface)
+{
+	cancel_delayed_work_sync(&hard_iface->elp_wq);
+
+	dev_kfree_skb(hard_iface->elp_skb);
+	hard_iface->elp_skb = NULL;
+}
+
+static void bat_v_elp_iface_update_mac(struct hard_iface *hard_iface)
+{
+	return;
+}
+
+static void bat_v_elp_primary_iface_set(struct hard_iface *hard_iface)
+{
+	struct hard_iface *hard_iface_tmp;
+	struct batman_elp_packet *elp_packet;
+	struct sk_buff *skb;
+
+	/* update orig field of every elp iface belonging to this mesh */
+	rcu_read_lock();
+	list_for_each_entry_rcu(hard_iface_tmp, &hardif_list, list) {
+		if (hard_iface->soft_iface != hard_iface_tmp->soft_iface)
+			continue;
+
+		if (!hard_iface_tmp->elp_skb)
+			continue;
+
+		skb = hard_iface_tmp->elp_skb;
+		elp_packet = (struct batman_elp_packet *)skb->data;
+		memcpy(elp_packet->orig,
+		       hard_iface->net_dev->dev_addr, ETH_ALEN);
+	}
+	rcu_read_unlock();
+}
+
+static void bat_v_ogm_schedule(struct hard_iface *hard_iface,
+			       int tt_num_changes)
+{
+	return;
+}
+
+static void bat_v_ogm_emit(struct forw_packet *forw_packet)
+{
+	return;
+}
+
+
+static struct bat_algo_ops batman_v __read_mostly = {
+	.name = "BATMAN V",
+	.bat_iface_enable = bat_v_elp_iface_enable,
+	.bat_iface_disable = bat_v_elp_iface_disable,
+	.bat_iface_update_mac = bat_v_elp_iface_update_mac,
+	.bat_primary_iface_set = bat_v_elp_primary_iface_set,
+	.bat_ogm_schedule = bat_v_ogm_schedule,
+	.bat_ogm_emit = bat_v_ogm_emit,
+};
+
+int __init bat_v_init(void)
+{
+	return bat_algo_register(&batman_v);
+}
diff --git a/gen-compat-autoconf.sh b/gen-compat-autoconf.sh
index 7ea42aa..f6f32e7 100755
--- a/gen-compat-autoconf.sh
+++ b/gen-compat-autoconf.sh
@@ -39,6 +39,7 @@ gen_config() {
 gen_config 'CONFIG_BATMAN_ADV_DEBUG' ${CONFIG_BATMAN_ADV_DEBUG:="n"} >> "${TMP}"
 gen_config 'CONFIG_BATMAN_ADV_BLA' ${CONFIG_BATMAN_ADV_BLA:="y"} >> "${TMP}"
 gen_config 'CONFIG_BATMAN_ADV_DAT' ${CONFIG_BATMAN_ADV_DAT:="y"} >> "${TMP}"
+gen_config 'CONFIG_BATMAN_ADV_BATMAN_V' ${CONFIG_BATMAN_ADV_BATMAN_V:="n"} >> "${TMP}"
 
 # only regenerate compat-autoconf.h when config was changed
 diff "${TMP}" "${TARGET}" > /dev/null 2>&1 || cp "${TMP}" "${TARGET}"
diff --git a/hard-interface.c b/hard-interface.c
index daa6adc..e53e143 100644
--- a/hard-interface.c
+++ b/hard-interface.c
@@ -450,6 +450,12 @@ static struct hard_iface *hardif_add_interface(struct net_device *net_dev)
 	atomic_set(&hard_iface->seqno, 1);
 	hard_iface->packet_buff = NULL;
 
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+	atomic_set(&hard_iface->elp_interval, 500);
+	atomic_set(&hard_iface->elp_seqno, 1);
+	hard_iface->elp_skb = NULL;
+#endif /* CONFIG_BATMAN_ADV_BATMAN_V */
+
 	return hard_iface;
 
 free_if:
diff --git a/main.c b/main.c
index 0757c2d..b83a693 100644
--- a/main.c
+++ b/main.c
@@ -56,6 +56,7 @@ static int __init batman_init(void)
 
 	recv_handler_init();
 
+	bat_v_init();
 	bat_iv_init();
 
 	/* the name should not be longer than 10 chars - see
diff --git a/packet.h b/packet.h
index 3c4c533..cf516dc 100644
--- a/packet.h
+++ b/packet.h
@@ -33,7 +33,8 @@ enum bat_packettype {
 	BAT_UNICAST_FRAG	= 0x06,
 	BAT_TT_QUERY		= 0x07,
 	BAT_ROAM_ADV		= 0x08,
-	BAT_UNICAST_4ADDR	= 0x09
+	BAT_UNICAST_4ADDR	= 0x09,
+	BAT_V_ELP		= 0x10
 };
 
 enum bat_subtype {
@@ -136,6 +137,17 @@ struct batman_ogm_packet {
 
 #define BATMAN_OGM_HLEN sizeof(struct batman_ogm_packet)
 
+/* echo location packet */
+struct batman_elp_packet {
+	struct batman_header header;
+	uint8_t  num_neighbors;
+	uint32_t seqno;
+	uint32_t elp_interval;
+	uint8_t  orig[ETH_ALEN];
+} __packed;
+
+#define BATMAN_ELP_HLEN sizeof(struct batman_elp_packet)
+
 struct icmp_packet {
 	struct batman_header header;
 	uint8_t  msg_type; /* see ICMP message types above */
diff --git a/types.h b/types.h
index 15f538a..86f2250 100644
--- a/types.h
+++ b/types.h
@@ -58,6 +58,12 @@ struct hard_iface {
 	struct packet_type batman_adv_ptype;
 	struct net_device *soft_iface;
 	struct rcu_head rcu;
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+	atomic_t elp_interval;
+	atomic_t elp_seqno;
+	struct sk_buff *elp_skb;
+	struct delayed_work elp_wq;
+#endif /* CONFIG_BATMAN_ADV_BATMAN_V */
 };
 
 /**
-- 
1.7.9.1

[B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Marek Lindner]

From: Linus Luessing <linus.luessing@web.de>

Developed by Linus during a 6 months trainee study period in Ascom (Switzerland)
AG.

Signed-off-by: Linus Luessing <linus.luessing@web.de>
Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
---
 bat_v_elp.c |  255 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 packet.h    |    6 ++
 types.h     |    8 ++
 3 files changed, 267 insertions(+), 2 deletions(-)

diff --git a/bat_v_elp.c b/bat_v_elp.c
index c2dee5c..e252c04 100644
--- a/bat_v_elp.c
+++ b/bat_v_elp.c
@@ -23,6 +23,8 @@
 #include "hard-interface.h"
 #include "send.h"
 #include "bat_algo.h"
+#include "originator.h"
+#include "routing.h"
 
 static void bat_v_elp_start_timer(struct hard_iface *hard_iface)
 {
@@ -35,12 +37,78 @@ static void bat_v_elp_start_timer(struct hard_iface *hard_iface)
 			   &hard_iface->elp_wq, elp_interval);
 }
 
+static struct neigh_node *bat_v_elp_neigh_new(struct hard_iface *hard_iface,
+					      uint8_t *neigh_addr,
+					      uint32_t seqno)
+{
+	struct neigh_node *neigh_node;
+
+	neigh_node = neigh_node_new(hard_iface, neigh_addr, seqno);
+	if (!neigh_node)
+		goto out;
+
+	neigh_node->last_recv_seqno = seqno - 1;
+
+	spin_lock_bh(&hard_iface->neigh_list_lock);
+	hlist_add_head_rcu(&neigh_node->list, &hard_iface->neigh_list);
+	spin_unlock_bh(&hard_iface->neigh_list_lock);
+
+out:
+	return neigh_node;
+}
+
+static struct neigh_node *bat_v_elp_neigh_get(struct hard_iface *hard_iface,
+					      uint8_t *neigh_addr)
+{
+	struct neigh_node *neigh_node = NULL, *neigh_node_tmp;
+	struct hlist_node *node;
+
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(neigh_node_tmp, node,
+				 &hard_iface->neigh_list, list) {
+		if (!compare_eth(neigh_node_tmp->addr, neigh_addr))
+			continue;
+
+		if (!atomic_inc_not_zero(&neigh_node_tmp->refcount))
+			continue;
+
+		neigh_node = neigh_node_tmp;
+		break;
+	}
+	rcu_read_unlock();
+
+	return neigh_node;
+}
+
+static void bat_v_elp_neigh_purge(struct hard_iface *hard_iface)
+{
+	struct neigh_node *neigh_node;
+	struct hlist_node *node, *node_tmp;
+
+	spin_lock_bh(&hard_iface->neigh_list_lock);
+	hlist_for_each_entry_safe(neigh_node, node, node_tmp,
+				  &hard_iface->neigh_list, list) {
+
+		if ((!has_timed_out(neigh_node->last_seen, PURGE_TIMEOUT)) &&
+		    (hard_iface->if_status == IF_ACTIVE))
+			continue;
+
+		hlist_del_rcu(&neigh_node->list);
+		neigh_node_free_ref(neigh_node);
+	}
+	spin_unlock_bh(&hard_iface->neigh_list_lock);
+}
+
 static void bat_v_elp_send_outstanding(struct work_struct *work)
 {
 	struct hard_iface *hard_iface;
 	struct bat_priv *bat_priv;
 	struct batman_elp_packet *elp_packet;
+	struct elp_neigh_entry *elp_neigh_entry;
+	struct neigh_node *neigh_node;
+	struct hlist_node *node;
 	struct sk_buff *skb;
+	unsigned int max_len;
 
 	hard_iface = container_of(work, struct hard_iface, elp_wq.work);
 	bat_priv = netdev_priv(hard_iface->soft_iface);
@@ -48,6 +116,7 @@ static void bat_v_elp_send_outstanding(struct work_struct *work)
 	if (atomic_read(&bat_priv->mesh_state) == MESH_DEACTIVATING)
 		goto out;
 
+	/* we are in the process of shutting this interface down */
 	if ((hard_iface->if_status == IF_NOT_IN_USE) ||
 	    (hard_iface->if_status == IF_TO_BE_REMOVED))
 		goto out;
@@ -56,14 +125,40 @@ static void bat_v_elp_send_outstanding(struct work_struct *work)
 	if (hard_iface->if_status != IF_ACTIVE)
 		goto restart_timer;
 
+	max_len = min_t(unsigned int, ETH_DATA_LEN, hard_iface->net_dev->mtu);
+
 	skb = skb_copy(hard_iface->elp_skb, GFP_ATOMIC);
 	if (!skb)
 		goto out;
 
+	/* purge outdated entries first */
+	bat_v_elp_neigh_purge(hard_iface);
+
 	elp_packet = (struct batman_elp_packet *)skb->data;
 	elp_packet->seqno = htonl(atomic_read(&hard_iface->elp_seqno));
 	elp_packet->num_neighbors = 0;
 
+	elp_neigh_entry = (struct elp_neigh_entry *)(elp_packet + 1);
+
+	rcu_read_lock();
+	hlist_for_each_entry_rcu(neigh_node, node,
+				 &hard_iface->neigh_list, list) {
+		if (skb->len + sizeof(struct elp_neigh_entry) > max_len) {
+			if (printk_ratelimit())
+				bat_err(hard_iface->net_dev,
+					"Skipping ELP neigh entries: "
+					"packet length exhausted\n");
+			break;
+		}
+
+		memcpy(elp_neigh_entry->addr, neigh_node->addr, ETH_ALEN);
+		elp_neigh_entry->rq = neigh_node->rq;
+		elp_packet->num_neighbors++;
+		elp_neigh_entry++;
+		skb_put(skb, sizeof(struct elp_neigh_entry));
+	}
+	rcu_read_unlock();
+
 	bat_dbg(DBG_BATMAN, bat_priv,
 		"Sending elp packet on interface %s, seqno %d\n",
 		hard_iface->net_dev->name, atomic_read(&hard_iface->elp_seqno));
@@ -71,8 +166,9 @@ static void bat_v_elp_send_outstanding(struct work_struct *work)
 	send_skb_packet(skb, hard_iface, broadcast_addr);
 
 	atomic_inc(&hard_iface->elp_seqno);
-	bat_v_elp_start_timer(hard_iface);
 
+restart_timer:
+	bat_v_elp_start_timer(hard_iface);
 out:
 	return;
 }
@@ -117,6 +213,8 @@ static void bat_v_elp_iface_disable(struct hard_iface *hard_iface)
 
 	dev_kfree_skb(hard_iface->elp_skb);
 	hard_iface->elp_skb = NULL;
+
+	bat_v_elp_neigh_purge(hard_iface);
 }
 
 static void bat_v_elp_iface_update_mac(struct hard_iface *hard_iface)
@@ -158,6 +256,143 @@ static void bat_v_ogm_emit(struct forw_packet *forw_packet)
 	return;
 }
 
+/* extract my own tq to neighbor from the elp packet */
+static uint8_t bat_v_elp_fetch_tq(uint8_t *my_iface_addr,
+				  struct batman_elp_packet *elp_packet,
+				  int elp_packet_len)
+{
+	struct elp_neigh_entry *elp_neigh_entry;
+	uint8_t tq = 0;
+	int i;
+
+	elp_neigh_entry = (struct elp_neigh_entry *)(elp_packet + 1);
+	elp_packet_len -= BATMAN_ELP_HLEN;
+
+	for (i = 0; i < elp_packet->num_neighbors; i++) {
+		if (!compare_eth(my_iface_addr, elp_neigh_entry->addr))
+			goto next;
+
+		tq = elp_neigh_entry->rq;
+		break;
+
+	next:
+		elp_packet_len -= sizeof(struct elp_neigh_entry);
+		if (elp_packet_len < 0)
+			break;
+
+		elp_neigh_entry++;
+	}
+
+	return tq;
+}
+
+static void bat_v_elp_neigh_update_lq(struct hard_iface *hard_iface,
+				      struct neigh_node *neigh_node,
+				      uint8_t my_tq, uint32_t seqno)
+{
+	struct bat_priv *bat_priv = netdev_priv(hard_iface->soft_iface);
+	int32_t seq_diff;
+	int neigh_packet_count;
+	bool is_new_seqno;
+
+	seq_diff = seqno - neigh_node->last_recv_seqno;
+
+	is_new_seqno = bit_get_packet(bat_priv, neigh_node->elp_rq_bits,
+				      seq_diff, 1);
+	if (!is_new_seqno)
+		return;
+
+	bat_dbg(DBG_BATMAN, bat_priv,
+		"Updating last_seqno of neighbor %pM: old %d, new %d\n",
+		neigh_node->addr, neigh_node->last_recv_seqno, seqno);
+
+	/***
+	 * we only update the tq/last seen/last seqno fields upon
+	 * receival of a newer ELP sequence number
+	 */
+	neigh_node->tq = my_tq;
+	neigh_node->last_seen = jiffies;
+	neigh_node->last_recv_seqno = seqno;
+
+	neigh_packet_count = bitmap_weight(neigh_node->elp_rq_bits,
+					   TQ_LOCAL_WINDOW_SIZE);
+	neigh_node->rq = (neigh_packet_count * TQ_MAX_VALUE) /
+							TQ_LOCAL_WINDOW_SIZE;
+
+	bat_dbg(DBG_BATMAN, bat_priv,
+		"New rq/tq of neighbor %pM: rq %d, tq %d\n",
+		neigh_node->addr, neigh_node->rq, neigh_node->tq);
+}
+
+void bat_v_elp_neigh_update(uint8_t *neigh_addr,
+			    struct hard_iface *if_incoming,
+			    struct batman_elp_packet *elp_packet,
+			    int elp_packet_len)
+{
+	struct neigh_node *neigh_node;
+	uint8_t my_tq;
+
+	neigh_node = bat_v_elp_neigh_get(if_incoming, neigh_addr);
+	if (!neigh_node) {
+		neigh_node = bat_v_elp_neigh_new(if_incoming, neigh_addr,
+						 elp_packet->seqno);
+		if (!neigh_node)
+			goto out;
+	}
+
+	my_tq = bat_v_elp_fetch_tq(if_incoming->net_dev->dev_addr,
+				   elp_packet, elp_packet_len);
+
+	spin_lock_bh(&neigh_node->lq_update_lock);
+	bat_v_elp_neigh_update_lq(if_incoming, neigh_node,
+				  my_tq, elp_packet->seqno);
+	spin_unlock_bh(&neigh_node->lq_update_lock);
+
+out:
+	if (neigh_node)
+		neigh_node_free_ref(neigh_node);
+}
+
+static int bat_v_elp_packet_recv(struct sk_buff *skb,
+				 struct hard_iface *if_incoming)
+{
+	struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
+	struct batman_elp_packet *elp_packet;
+	struct hard_iface *primary_if;
+	struct ethhdr *ethhdr;
+	bool ret;
+
+	ret = check_management_packet(skb, if_incoming, BATMAN_ELP_HLEN);
+	if (!ret)
+		return NET_RX_DROP;
+
+	/* did we receive a B.A.T.M.A.N. V ELP packet on an interface
+	 * that does not have B.A.T.M.A.N. V ELP enabled ? */
+	if (bat_priv->bat_algo_ops->bat_ogm_emit != bat_v_ogm_emit)
+		return NET_RX_DROP;
+
+	primary_if = primary_if_get_selected(bat_priv);
+	if (!primary_if)
+		goto out;
+
+	ethhdr = (struct ethhdr *)skb_mac_header(skb);
+	elp_packet = (struct batman_elp_packet *)skb->data;
+
+	/* our own ELP packet */
+	if (compare_eth(primary_if->net_dev->dev_addr, elp_packet->orig))
+		goto out;
+
+	elp_packet->seqno = ntohl(elp_packet->seqno);
+
+	bat_v_elp_neigh_update(ethhdr->h_source, if_incoming,
+			       elp_packet, skb_headlen(skb));
+
+out:
+	if (primary_if)
+		hardif_free_ref(primary_if);
+	dev_kfree_skb(skb);
+	return NET_RX_SUCCESS;
+}
 
 static struct bat_algo_ops batman_v __read_mostly = {
 	.name = "BATMAN V",
@@ -171,5 +406,21 @@ static struct bat_algo_ops batman_v __read_mostly = {
 
 int __init bat_v_init(void)
 {
-	return bat_algo_register(&batman_v);
+	int ret;
+
+	/* batman v echo location protocol packet  */
+	ret = recv_handler_register(BAT_V_ELP, bat_v_elp_packet_recv);
+	if (ret < 0)
+		goto out;
+
+	ret = bat_algo_register(&batman_v);
+	if (ret < 0)
+		goto handler_unregister;
+
+	goto out;
+
+handler_unregister:
+	recv_handler_unregister(BAT_V_ELP);
+out:
+	return ret;
 }
diff --git a/packet.h b/packet.h
index cf516dc..ea1683f 100644
--- a/packet.h
+++ b/packet.h
@@ -148,6 +148,12 @@ struct batman_elp_packet {
 
 #define BATMAN_ELP_HLEN sizeof(struct batman_elp_packet)
 
+struct elp_neigh_entry {
+	uint8_t addr[ETH_ALEN];
+	uint8_t rq;
+	uint8_t align;
+} __attribute__((packed));
+
 struct icmp_packet {
 	struct batman_header header;
 	uint8_t  msg_type; /* see ICMP message types above */
diff --git a/types.h b/types.h
index 86f2250..abe27dd 100644
--- a/types.h
+++ b/types.h
@@ -61,6 +61,8 @@ struct hard_iface {
 #ifdef CONFIG_BATMAN_ADV_BATMAN_V
 	atomic_t elp_interval;
 	atomic_t elp_seqno;
+	struct hlist_head neigh_list;
+	spinlock_t neigh_list_lock;
 	struct sk_buff *elp_skb;
 	struct delayed_work elp_wq;
 #endif /* CONFIG_BATMAN_ADV_BATMAN_V */
@@ -158,6 +160,12 @@ struct neigh_node {
 	struct orig_node *orig_node;
 	struct hard_iface *if_incoming;
 	spinlock_t lq_update_lock;	/* protects: tq_recv, tq_index */
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+	uint8_t rq;
+	uint8_t tq;
+	uint32_t last_recv_seqno;
+	DECLARE_BITMAP(elp_rq_bits, TQ_LOCAL_WINDOW_SIZE);
+#endif
 };
 
 #ifdef CONFIG_BATMAN_ADV_BLA
-- 
1.7.9.1

[B.A.T.M.A.N.] [RFC 3/5] batman-adv: ELP - exporting neighbor list via debugfs

[Marek Lindner]

From: Linus Luessing <linus.luessing@web.de>

Lists all neighbours and their tq/rq values detected and measured by the Echo
Location Protocol (ELP).

Developed by Linus during a 6 months trainee study period in Ascom (Switzerland)
AG.

Signed-off-by: Linus Luessing <linus.luessing@web.de>
Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
---
 bat_debugfs.c |   16 +++++++++++++
 bat_v_elp.c   |   67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 83 insertions(+), 0 deletions(-)

diff --git a/bat_debugfs.c b/bat_debugfs.c
index 3b588f8..5365554 100644
--- a/bat_debugfs.c
+++ b/bat_debugfs.c
@@ -227,6 +227,16 @@ static int bat_algorithms_open(struct inode *inode, struct file *file)
 	return single_open(file, bat_algo_seq_print_text, NULL);
 }
 
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+int bat_v_elp_seq_print_text(struct seq_file *seq, void *offset);
+
+static int neighbors_open(struct inode *inode, struct file *file)
+{
+	struct net_device *net_dev = (struct net_device *)inode->i_private;
+	return single_open(file, bat_v_elp_seq_print_text, net_dev);
+}
+#endif
+
 static int originators_open(struct inode *inode, struct file *file)
 {
 	struct net_device *net_dev = (struct net_device *)inode->i_private;
@@ -283,6 +293,9 @@ struct bat_debuginfo bat_debuginfo_##_name = {	\
 };
 
 static BAT_DEBUGINFO(routing_algos, S_IRUGO, bat_algorithms_open);
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+static BAT_DEBUGINFO(neighbors, S_IRUGO, neighbors_open);
+#endif
 static BAT_DEBUGINFO(originators, S_IRUGO, originators_open);
 static BAT_DEBUGINFO(gateways, S_IRUGO, gateways_open);
 static BAT_DEBUGINFO(transtable_global, S_IRUGO, transtable_global_open);
@@ -293,6 +306,9 @@ static BAT_DEBUGINFO(transtable_local, S_IRUGO, transtable_local_open);
 static BAT_DEBUGINFO(vis_data, S_IRUGO, vis_data_open);
 
 static struct bat_debuginfo *mesh_debuginfos[] = {
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+	&bat_debuginfo_neighbors,
+#endif
 	&bat_debuginfo_originators,
 	&bat_debuginfo_gateways,
 	&bat_debuginfo_transtable_global,
diff --git a/bat_v_elp.c b/bat_v_elp.c
index e252c04..9232f28 100644
--- a/bat_v_elp.c
+++ b/bat_v_elp.c
@@ -394,6 +394,73 @@ out:
 	return NET_RX_SUCCESS;
 }
 
+static void bat_v_elp_seq_print_neigh(struct seq_file *seq,
+				      struct hard_iface *hard_iface,
+				      struct neigh_node *neigh_node)
+{
+	int last_secs, last_msecs;
+
+	last_secs = jiffies_to_msecs(jiffies - neigh_node->last_seen) / 1000;
+	last_msecs = jiffies_to_msecs(jiffies - neigh_node->last_seen) % 1000;
+
+	seq_printf(seq, "%pM %4i.%03is     (%3i,%3i) [%10s]\n",
+		   neigh_node->addr, last_secs, last_msecs, neigh_node->tq,
+		   neigh_node->rq, hard_iface->net_dev->name);
+}
+
+int bat_v_elp_seq_print_text(struct seq_file *seq, void *offset)
+{
+	struct net_device *net_dev = (struct net_device *)seq->private;
+	struct bat_priv *bat_priv = netdev_priv(net_dev);
+	struct hard_iface *hard_iface, *primary_if;
+	struct neigh_node *neigh_node;
+	struct hlist_node *node;
+	int ret = 0, batman_count = 0;
+
+	primary_if = primary_if_get_selected(bat_priv);
+
+	if (!primary_if) {
+		ret = seq_printf(seq, "BATMAN mesh %s disabled - "
+				 "please specify interfaces to enable it\n",
+				 net_dev->name);
+		goto out;
+	}
+
+	if (primary_if->if_status != IF_ACTIVE) {
+		ret = seq_printf(seq, "BATMAN mesh %s "
+				 "disabled - primary interface not active\n",
+				 net_dev->name);
+		goto out;
+	}
+
+	seq_printf(seq, "[B.A.T.M.A.N. adv %s, MainIF/MAC: %s/%pM (%s)]\n",
+		   SOURCE_VERSION, primary_if->net_dev->name,
+		   primary_if->net_dev->dev_addr, net_dev->name);
+	seq_printf(seq, "  %-15s %s (%s/%i) [%10s]\n",
+		   "Neighbor", "last-seen", "#TQ,#RQ", TQ_MAX_VALUE, "IF");
+
+	rcu_read_lock();
+	list_for_each_entry_rcu(hard_iface, &hardif_list, list) {
+		if (hard_iface->soft_iface != net_dev)
+			continue;
+
+		hlist_for_each_entry_rcu(neigh_node, node,
+					 &hard_iface->neigh_list, list) {
+			bat_v_elp_seq_print_neigh(seq, hard_iface, neigh_node);
+			batman_count++;
+		}
+	}
+	rcu_read_unlock();
+
+	if (batman_count == 0)
+		seq_printf(seq, "No batman nodes in range ...\n");
+
+out:
+	if (primary_if)
+		hardif_free_ref(primary_if);
+	return ret;
+}
+
 static struct bat_algo_ops batman_v __read_mostly = {
 	.name = "BATMAN V",
 	.bat_iface_enable = bat_v_elp_iface_enable,
-- 
1.7.9.1

[B.A.T.M.A.N.] [RFC 4/5] batman-adv: ELP - adding sysfs parameter for elp interval

[Marek Lindner]

From: Linus Luessing <linus.luessing@web.de>

This parameter can be set individually on each interface and allows the
configuration of the ndp interval for the link quality measurements during
runtime. Usually it is desirable to set it to a higher (= slower) value on
interfaces which have a more static characteristic (e.g. wired interfaces)
or very dense neighbourhoods to reduce overhead.

Developed by Linus during a 6 months trainee study period in Ascom
(Switzerland) AG.

Signed-off-by: Linus Luessing <linus.luessing@web.de>
Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
---
 bat_sysfs.c                |    6 ++++++
 sysfs-class-net-batman-adv |    7 +++++++
 2 files changed, 13 insertions(+), 0 deletions(-)

diff --git a/bat_sysfs.c b/bat_sysfs.c
index d0f8453..6195a66 100644
--- a/bat_sysfs.c
+++ b/bat_sysfs.c
@@ -630,10 +630,16 @@ static ssize_t show_iface_status(struct kobject *kobj, struct attribute *attr,
 static BAT_ATTR(mesh_iface, S_IRUGO | S_IWUSR,
 		show_mesh_iface, store_mesh_iface);
 static BAT_ATTR(iface_status, S_IRUGO, show_iface_status, NULL);
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+BAT_ATTR_HIF_UINT(elp_interval, S_IRUGO | S_IWUSR, 2 * JITTER, INT_MAX, NULL);
+#endif
 
 static struct bat_attribute *batman_attrs[] = {
 	&bat_attr_mesh_iface,
 	&bat_attr_iface_status,
+#ifdef CONFIG_BATMAN_ADV_BATMAN_V
+	&bat_attr_elp_interval,
+#endif
 	NULL,
 };
 
diff --git a/sysfs-class-net-batman-adv b/sysfs-class-net-batman-adv
index 38dd762..954ab1f 100644
--- a/sysfs-class-net-batman-adv
+++ b/sysfs-class-net-batman-adv
@@ -12,3 +12,10 @@ Date:           May 2010
 Contact:        Marek Lindner <lindner_marek@yahoo.de>
 Description:
                 Indicates the status of <iface> as it is seen by batman.
+
+What:           /sys/class/net/<mesh_iface>/batman-adv/elp_interval
+Date:           Mar 2012
+Contact:        Linus Lüssing <linus.luessing@web.de>
+Description:
+                Defines the interval in milliseconds in which batman
+                sends its probing packets for link quality measurements.
\ No newline at end of file
-- 
1.7.9.1

[B.A.T.M.A.N.] [RFC 5/5] batman-adv: ELP - add configurable minimum ELP packet length (def: 300B)

[Marek Lindner]

From: Linus Luessing <linus.luessing@web.de>

With the current setting of no minimum ELP packet length, BATMAN very
often choses too short paths. These paths are often only usable for small
packets, but not for e.g. larger TCP downloads.

Therefore this commit introduces a minimum ELP packet length. If the ELP
packet size is smaller than the specified minimum size the packet will be
padded with zeroes up to this specified size.

Developed by Linus during a 6 months trainee study period in Ascom
(Switzerland) AG.

Signed-off-by: Linus Luessing <linus.luessing@web.de>
Signed-off-by: Marek Lindner <lindner_marek@yahoo.de>
---
 bat_sysfs.c                |    2 ++
 bat_v_elp.c                |    9 ++++++++-
 hard-interface.c           |    1 +
 sysfs-class-net-batman-adv |    8 +++++++-
 types.h                    |    1 +
 5 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/bat_sysfs.c b/bat_sysfs.c
index 6195a66..69df249 100644
--- a/bat_sysfs.c
+++ b/bat_sysfs.c
@@ -632,6 +632,7 @@ static BAT_ATTR(mesh_iface, S_IRUGO | S_IWUSR,
 static BAT_ATTR(iface_status, S_IRUGO, show_iface_status, NULL);
 #ifdef CONFIG_BATMAN_ADV_BATMAN_V
 BAT_ATTR_HIF_UINT(elp_interval, S_IRUGO | S_IWUSR, 2 * JITTER, INT_MAX, NULL);
+BAT_ATTR_HIF_UINT(elp_min_len, S_IRUGO | S_IWUSR, 0, ETH_DATA_LEN, NULL);
 #endif
 
 static struct bat_attribute *batman_attrs[] = {
@@ -639,6 +640,7 @@ static struct bat_attribute *batman_attrs[] = {
 	&bat_attr_iface_status,
 #ifdef CONFIG_BATMAN_ADV_BATMAN_V
 	&bat_attr_elp_interval,
+	&bat_attr_elp_min_len,
 #endif
 	NULL,
 };
diff --git a/bat_v_elp.c b/bat_v_elp.c
index 9232f28..1bde84e 100644
--- a/bat_v_elp.c
+++ b/bat_v_elp.c
@@ -108,7 +108,7 @@ static void bat_v_elp_send_outstanding(struct work_struct *work)
 	struct neigh_node *neigh_node;
 	struct hlist_node *node;
 	struct sk_buff *skb;
-	unsigned int max_len;
+	unsigned int max_len, min_len;
 
 	hard_iface = container_of(work, struct hard_iface, elp_wq.work);
 	bat_priv = netdev_priv(hard_iface->soft_iface);
@@ -126,6 +126,8 @@ static void bat_v_elp_send_outstanding(struct work_struct *work)
 		goto restart_timer;
 
 	max_len = min_t(unsigned int, ETH_DATA_LEN, hard_iface->net_dev->mtu);
+	min_len = min_t(unsigned int, atomic_read(&hard_iface->elp_min_len),
+			max_len);
 
 	skb = skb_copy(hard_iface->elp_skb, GFP_ATOMIC);
 	if (!skb)
@@ -159,6 +161,11 @@ static void bat_v_elp_send_outstanding(struct work_struct *work)
 	}
 	rcu_read_unlock();
 
+	if (skb->len < min_len) {
+		memset(elp_neigh_entry, 0, min_len - skb->len);
+		skb_put(skb, min_len - skb->len);
+	}
+
 	bat_dbg(DBG_BATMAN, bat_priv,
 		"Sending elp packet on interface %s, seqno %d\n",
 		hard_iface->net_dev->name, atomic_read(&hard_iface->elp_seqno));
diff --git a/hard-interface.c b/hard-interface.c
index e53e143..68cd564 100644
--- a/hard-interface.c
+++ b/hard-interface.c
@@ -452,6 +452,7 @@ static struct hard_iface *hardif_add_interface(struct net_device *net_dev)
 
 #ifdef CONFIG_BATMAN_ADV_BATMAN_V
 	atomic_set(&hard_iface->elp_interval, 500);
+	atomic_set(&hard_iface->elp_min_len, 300);
 	atomic_set(&hard_iface->elp_seqno, 1);
 	hard_iface->elp_skb = NULL;
 #endif /* CONFIG_BATMAN_ADV_BATMAN_V */
diff --git a/sysfs-class-net-batman-adv b/sysfs-class-net-batman-adv
index 954ab1f..ddaa273 100644
--- a/sysfs-class-net-batman-adv
+++ b/sysfs-class-net-batman-adv
@@ -18,4 +18,10 @@ Date:           Mar 2012
 Contact:        Linus Lüssing <linus.luessing@web.de>
 Description:
                 Defines the interval in milliseconds in which batman
-                sends its probing packets for link quality measurements.
\ No newline at end of file
+                sends its probing packets for link quality measurements.
+
+What:           /sys/class/net/<mesh_iface>/batman-adv/elp_min_len
+Date:           Mar 2012
+Contact:        Linus Lüssing <linus.luessing@web.de>
+Description:
+                Defines the minimum ELP packet size.
diff --git a/types.h b/types.h
index abe27dd..f4164ea 100644
--- a/types.h
+++ b/types.h
@@ -60,6 +60,7 @@ struct hard_iface {
 	struct rcu_head rcu;
 #ifdef CONFIG_BATMAN_ADV_BATMAN_V
 	atomic_t elp_interval;
+	atomic_t elp_min_len;
 	atomic_t elp_seqno;
 	struct hlist_head neigh_list;
 	spinlock_t neigh_list_lock;
-- 
1.7.9.1

Re: [B.A.T.M.A.N.] [RFC] ELP

[Andrew Lunn]

On Fri, Mar 23, 2012 at 05:50:30AM +0800, Marek Lindner wrote:
> 
> Hi,
> 
> after numerous infrastructure changes in the past weeks ELP[1] slowly
> approaches the state in which it can be tested and later merged into the
> master branch.

Hi Marek

Great to see this work going forward.

Something that Linus and I discussed was using unicast packets as
well. We didn't do anything at the time, project deadlines looming
etc... It is also a while ago, so maybe i'm remembering this wrong...

The problem with broadcasting the ELP packets is that they are always
sent with the most robust coding rate. So ELP gives you an idea how
good the 1Mbps broadcast channel is, not how good the unicast channel
the automatic rate selection algorithm is using is. I think we
discussed mixing in some unicast packets in the forward direction. The
ELP packets containing the reports would stay the same, and so
function as node detection. But a node could also send out unicast ELP
packets to its known neighbours and they would be included into the
LQ.

There are obvious drawbacks. More overhead, especially in dense
networks. It is also not clear if the measurements would be
better. Unicast packets get a number of retries with fast ACKs, where
as multicast does not. So multicast might actually give a better
measure of the link at 1Mbps.

Do you know if Linus had chance to explore these ideas during his
GSOC?

	Thanks
		Andrew

Re: [B.A.T.M.A.N.] [RFC] ELP

[Andrew Lunn]

> cat /sys/kernel/debug/batman_adv/routing_algos 
> Available routing algorithms:
> BATMAN IV
> BATMAN V
> 
> To activate B.A.T.M.A.N. V (ELP) you should run the following command *before*
> adding any interface via batctl:
> 
> echo -n "BATMAN V" > /sys/module/batman_adv/parameters/routing_algo

Hi Marek

How about BATMAN_V and BATMAN_IV, so avoiding the need for "" or \
escaping of the space?

    Thanks
	Andrew

Re: [B.A.T.M.A.N.] [RFC 1/5] batman-adv: ELP - adding basic infrastructure

[Andrew Lunn]

> +static int bat_v_elp_iface_enable(struct hard_iface *hard_iface)
> +{
> +	struct batman_elp_packet *elp_packet;
> +	unsigned long random_seqno;

...

> +	/* randomize initial seqno to avoid collision */
> +	get_random_bytes(&random_seqno, sizeof(unsigned long));
> +	atomic_set(&hard_iface->elp_seqno, (uint32_t)random_seqno);

Hi Marek

Why not just make random_seqno a uint32_t and avoid the cast?

    Andrew

Re: [B.A.T.M.A.N.] [RFC 1/5] batman-adv: ELP - adding basic infrastructure

[Andrew Lunn]

> --- a/packet.h
> +++ b/packet.h
> @@ -33,7 +33,8 @@ enum bat_packettype {
>  	BAT_UNICAST_FRAG	= 0x06,
>  	BAT_TT_QUERY		= 0x07,
>  	BAT_ROAM_ADV		= 0x08,
> -	BAT_UNICAST_4ADDR	= 0x09
> +	BAT_UNICAST_4ADDR	= 0x09,
> +	BAT_V_ELP		= 0x10
>  };

Hi Marek

I guess you are not on the ARM linux kernel list. A couple of months
ago, Rusty had a rant about the last entry in such structures should
always have a , even though its optional. As part of the ARM cleanup
work he had to append a new entry to many board files, and found it
very error prone. Sometime you forget to add the , to the line before,
and then the compiler spits out a compile error. So since then i've
got into the habit of always having a , on the last entry.

     Andrew

Re: [B.A.T.M.A.N.] [RFC] ELP

[Antonio Quartulli]

[-- Attachment #1: Type: text/plain, Size: 1365 bytes --]

Hi all,

On Fri, Mar 23, 2012 at 07:32:06AM +0100, Andrew Lunn wrote:
> The problem with broadcasting the ELP packets is that they are always
> sent with the most robust coding rate. So ELP gives you an idea how
> good the 1Mbps broadcast channel is, not how good the unicast channel
> the automatic rate selection algorithm is using is. I think we
> discussed mixing in some unicast packets in the forward direction. The
> ELP packets containing the reports would stay the same, and so
> function as node detection. But a node could also send out unicast ELP
> packets to its known neighbours and they would be included into the
> LQ.

I agree with you Andrew, I didn't think about a concept yet, but adding a
unicast reply or something like that would help a lot imho. (Actually is this
what Babel do?)

> 
> There are obvious drawbacks. More overhead, especially in dense
> networks. It is also not clear if the measurements would be
> better.

What about having a dynamic advertisement period? Again, I don't have a concept
about that, but, if I remember correctly, there is another protocol called
Trickle[1] which does something similar. We could take some inspiration.


Cheers,

[1]: http://csl.stanford.edu/~pal/pubs/trickle-nsdi04.pdf

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

Re: [B.A.T.M.A.N.] [RFC] ELP

[Antonio Quartulli]

[-- Attachment #1: Type: text/plain, Size: 804 bytes --]

On Fri, Mar 23, 2012 at 07:34:18AM +0100, Andrew Lunn wrote:
> > cat /sys/kernel/debug/batman_adv/routing_algos 
> > Available routing algorithms:
> > BATMAN IV
> > BATMAN V
> > 
> > To activate B.A.T.M.A.N. V (ELP) you should run the following command *before*
> > adding any interface via batctl:
> > 
> > echo -n "BATMAN V" > /sys/module/batman_adv/parameters/routing_algo
> 
> Hi Marek
> 
> How about BATMAN_V and BATMAN_IV, so avoiding the need for "" or \
> escaping of the space?

I agree :) Spaces are baaaad (and ugly :P (and error prone))! I already imagine a number of people
trying to change protocol without using quotes.

Cheers,


p.s. Marek thank you very much for your work

-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Andrew Lunn]

> +/* extract my own tq to neighbor from the elp packet */
> +static uint8_t bat_v_elp_fetch_tq(uint8_t *my_iface_addr,
> +				  struct batman_elp_packet *elp_packet,
> +				  int elp_packet_len)
> +{
> +	struct elp_neigh_entry *elp_neigh_entry;
> +	uint8_t tq = 0;
> +	int i;
> +
> +	elp_neigh_entry = (struct elp_neigh_entry *)(elp_packet + 1);
> +	elp_packet_len -= BATMAN_ELP_HLEN;
> +
> +	for (i = 0; i < elp_packet->num_neighbors; i++) {
> +		if (!compare_eth(my_iface_addr, elp_neigh_entry->addr))
> +			goto next;
> +
> +		tq = elp_neigh_entry->rq;
> +		break;
> +
> +	next:
> +		elp_packet_len -= sizeof(struct elp_neigh_entry);
> +		if (elp_packet_len < 0)
> +			break;
> +
> +		elp_neigh_entry++;
> +	}

Hi Marek

I'm personally not a fan of using goto like this. Reminds me of BASIC.

Could this be changed? Maybe first validate elp_packet->num_neighbors
matches the packet length, and then skip elp_packet_len check in each
iteration of the loop. A normal if then else should then be possible.

  Thanks
	Andrew	  

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Andrew Lunn]

> +static int bat_v_elp_packet_recv(struct sk_buff *skb,
> +				 struct hard_iface *if_incoming)
> +{
> +	struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
> +	struct batman_elp_packet *elp_packet;
> +	struct hard_iface *primary_if;
> +	struct ethhdr *ethhdr;
> +	bool ret;
> +
> +	ret = check_management_packet(skb, if_incoming, BATMAN_ELP_HLEN);
> +	if (!ret)
> +		return NET_RX_DROP;
> +
> +	/* did we receive a B.A.T.M.A.N. V ELP packet on an interface
> +	 * that does not have B.A.T.M.A.N. V ELP enabled ? */
> +	if (bat_priv->bat_algo_ops->bat_ogm_emit != bat_v_ogm_emit)
> +		return NET_RX_DROP;

Hi Marek

I've not looked at the code, but i assume this can happen because
there is not a per algorithm receive handler? Maybe it makes sense to
have a receive handler in algo structure, which can handle per
algorithm receive functions? The common PDUs can be handled first and
then a call into the algo receive function made to dispatch algo
specific PDUs.

	 Andrew

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Antonio Quartulli]

[-- Attachment #1: Type: text/plain, Size: 1337 bytes --]

On Fri, Mar 23, 2012 at 10:22:33 +0100, Andrew Lunn wrote:
> > +static int bat_v_elp_packet_recv(struct sk_buff *skb,
> > +				 struct hard_iface *if_incoming)
> > +{
> > +	struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
> > +	struct batman_elp_packet *elp_packet;
> > +	struct hard_iface *primary_if;
> > +	struct ethhdr *ethhdr;
> > +	bool ret;
> > +
> > +	ret = check_management_packet(skb, if_incoming, BATMAN_ELP_HLEN);
> > +	if (!ret)
> > +		return NET_RX_DROP;
> > +
> > +	/* did we receive a B.A.T.M.A.N. V ELP packet on an interface
> > +	 * that does not have B.A.T.M.A.N. V ELP enabled ? */
> > +	if (bat_priv->bat_algo_ops->bat_ogm_emit != bat_v_ogm_emit)
> > +		return NET_RX_DROP;
> 
> Hi Marek
> 
> I've not looked at the code, but i assume this can happen because
> there is not a per algorithm receive handler? Maybe it makes sense to
> have a receive handler in algo structure, which can handle per
> algorithm receive functions? The common PDUs can be handled first and
> then a call into the algo receive function made to dispatch algo
> specific PDUs.

Does this mean that you want to support multiple algorithms at the same time?
I don't think it is a good idea..

Cheers,


-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

[-- Attachment #2: Type: application/pgp-signature, Size: 490 bytes --]

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Andrew Lunn]

On Sat, Mar 24, 2012 at 09:14:08AM +0100, Antonio Quartulli wrote:
> On Fri, Mar 23, 2012 at 10:22:33 +0100, Andrew Lunn wrote:
> > > +static int bat_v_elp_packet_recv(struct sk_buff *skb,
> > > +				 struct hard_iface *if_incoming)
> > > +{
> > > +	struct bat_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
> > > +	struct batman_elp_packet *elp_packet;
> > > +	struct hard_iface *primary_if;
> > > +	struct ethhdr *ethhdr;
> > > +	bool ret;
> > > +
> > > +	ret = check_management_packet(skb, if_incoming, BATMAN_ELP_HLEN);
> > > +	if (!ret)
> > > +		return NET_RX_DROP;
> > > +
> > > +	/* did we receive a B.A.T.M.A.N. V ELP packet on an interface
> > > +	 * that does not have B.A.T.M.A.N. V ELP enabled ? */
> > > +	if (bat_priv->bat_algo_ops->bat_ogm_emit != bat_v_ogm_emit)
> > > +		return NET_RX_DROP;
> > 
> > Hi Marek
> > 
> > I've not looked at the code, but i assume this can happen because
> > there is not a per algorithm receive handler? Maybe it makes sense to
> > have a receive handler in algo structure, which can handle per
> > algorithm receive functions? The common PDUs can be handled first and
> > then a call into the algo receive function made to dispatch algo
> > specific PDUs.
> 
> Does this mean that you want to support multiple algorithms at the
> same time?  I don't think it is a good idea..

I'm assuming the choice of algorithm is linked to the soft interface,
i.e, bat0 could be using a different algorithm to bat1. So i think
multiple algorithms are possible at the same time.

I have been thinking about this a bit more, and also about this bit of
code:

+       elp_packet = (struct batman_elp_packet *)skb_push(hard_iface->elp_skb,
+                                                         BATMAN_ELP_HLEN);
+       memset(elp_packet, 0, BATMAN_ELP_HLEN);
+
+       elp_packet->header.packet_type = BAT_V_ELP;
+       elp_packet->header.version = COMPAT_VERSION;
+       elp_packet->header.ttl = 0;

Marek, what are your plans for COMPAT_VERSION? Will there be a
COMPAT_VERSION_IV and COMPAT_VERSION_V sometime soon?

Maybe when registering a receive function, you can pass both the
packet_type and version. So a received ELP packet with
COMPAT_VERSION_IV would automatically get tossed away, and an ELP with
COMPAT_VERSION_V would get dispatched.

	 Andrew

Re: [B.A.T.M.A.N.] [RFC 5/5] batman-adv: ELP - add configurable minimum ELP packet length (def: 300B)

[Andrew Lunn]

> +	if (skb->len < min_len) {
> +		memset(elp_neigh_entry, 0, min_len - skb->len);
> +		skb_put(skb, min_len - skb->len);
> +	}
> +

Hi Marek

I don't know the skbuf code too well, maybe you know it better than
me.

Is this memset needed? The skb is a copy of the template ELP packet
created then the soft interface is created. So if the contents of the
template is set to 0, should we be able to skip this zeroing here?

	 Thanks
		Andrew

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Marek Lindner]

On Friday, March 23, 2012 22:52:12 Andrew Lunn wrote:
> > +/* extract my own tq to neighbor from the elp packet */
> > +static uint8_t bat_v_elp_fetch_tq(uint8_t *my_iface_addr,
> > +				  struct batman_elp_packet *elp_packet,
> > +				  int elp_packet_len)
> > +{
> > +	struct elp_neigh_entry *elp_neigh_entry;
> > +	uint8_t tq = 0;
> > +	int i;
> > +
> > +	elp_neigh_entry = (struct elp_neigh_entry *)(elp_packet + 1);
> > +	elp_packet_len -= BATMAN_ELP_HLEN;
> > +
> > +	for (i = 0; i < elp_packet->num_neighbors; i++) {
> > +		if (!compare_eth(my_iface_addr, elp_neigh_entry->addr))
> > +			goto next;
> > +
> > +		tq = elp_neigh_entry->rq;
> > +		break;
> > +
> > +	next:
> > +		elp_packet_len -= sizeof(struct elp_neigh_entry);
> > +		if (elp_packet_len < 0)
> > +			break;
> > +
> > +		elp_neigh_entry++;
> > +	}
> 


> I'm personally not a fan of using goto like this. Reminds me of BASIC.
> 
> Could this be changed? Maybe first validate elp_packet->num_neighbors
> matches the packet length, and then skip elp_packet_len check in each
> iteration of the loop. A normal if then else should then be possible.

Something like this ?

elp_packet_len -= BATMAN_ELP_HLEN;
elp_packet_len -= elp_packet->num_neighbors * sizeof(struct elp_neigh_entry;
if (elp_packet_len < 0)
	return;

Cheers,
Marek

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Marek Lindner]

On Friday, March 23, 2012 23:22:33 Andrew Lunn wrote:
> I've not looked at the code, but i assume this can happen because
> there is not a per algorithm receive handler? Maybe it makes sense to
> have a receive handler in algo structure, which can handle per
> algorithm receive functions? The common PDUs can be handled first and
> then a call into the algo receive function made to dispatch algo
> specific PDUs.

Each algorithm registers its own packet types which end up in the protocol 
specific receive function. Nevertheless, we might receive a B.A.T.M.A.N. V 
packet on an interface not running B.A.T.M.A.N. V. 

Regards,
Marek

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Marek Lindner]

On Saturday, March 24, 2012 22:21:17 Andrew Lunn wrote:
> I'm assuming the choice of algorithm is linked to the soft interface,
> i.e, bat0 could be using a different algorithm to bat1. So i think
> multiple algorithms are possible at the same time.

Correct.


> I have been thinking about this a bit more, and also about this bit of
> code:
> 
> +       elp_packet = (struct batman_elp_packet
> *)skb_push(hard_iface->elp_skb, +                                         
>                BATMAN_ELP_HLEN); +       memset(elp_packet, 0,
> BATMAN_ELP_HLEN);
> +
> +       elp_packet->header.packet_type = BAT_V_ELP;
> +       elp_packet->header.version = COMPAT_VERSION;
> +       elp_packet->header.ttl = 0;
> 
> Marek, what are your plans for COMPAT_VERSION? Will there be a
> COMPAT_VERSION_IV and COMPAT_VERSION_V sometime soon?

Currently, that is not planned. We hoped to keep the compat numbers in sync 
across the various protocols. Otherwise we all could end up in compat hell.


> Maybe when registering a receive function, you can pass both the
> packet_type and version. So a received ELP packet with
> COMPAT_VERSION_IV would automatically get tossed away, and an ELP with
> COMPAT_VERSION_V would get dispatched.

What would be the use case of ELP COMPAT_VERSION_IV vs ELP COMPAT_VERSION_V ? 
BATMAN IV does not have ELP at all .. maybe I misunderstand ?

Regards,
Marek

Re: [B.A.T.M.A.N.] [RFC 5/5] batman-adv: ELP - add configurable minimum ELP packet length (def: 300B)

[Marek Lindner]

On Saturday, March 24, 2012 22:39:45 Andrew Lunn wrote:
> > +	if (skb->len < min_len) {
> > +		memset(elp_neigh_entry, 0, min_len - skb->len);
> > +		skb_put(skb, min_len - skb->len);
> > +	}
> > +
> 
> I don't know the skbuf code too well, maybe you know it better than
> me.
> 
> Is this memset needed? The skb is a copy of the template ELP packet
> created then the soft interface is created. So if the contents of the
> template is set to 0, should we be able to skip this zeroing here?

skb_copy() does not initialize the skb with zeros as far as I can tell. 
bat_v_elp_iface_enable() only writes zeros into the ELP header 
(BATMAN_ELP_HLEN), so zeroing the rest of the skb seems correct. 
We could zero the entire skb in bat_v_elp_iface_enable() to save the memset.

Regards,
Marek

Re: [B.A.T.M.A.N.] [RFC 1/5] batman-adv: ELP - adding basic infrastructure

[Marek Lindner]

On Friday, March 23, 2012 08:50:44 Andrew Lunn wrote:
> I guess you are not on the ARM linux kernel list. A couple of months
> ago, Rusty had a rant about the last entry in such structures should
> always have a , even though its optional. As part of the ARM cleanup
> work he had to append a new entry to many board files, and found it
> very error prone. Sometime you forget to add the , to the line before,
> and then the compiler spits out a compile error. So since then i've
> got into the habit of always having a , on the last entry.

No, I don't follow the ARM list. If we wanted the comma to be there we should 
change the entire module. At the moment we never put the comma after the last 
item.

Regards,
Marek

Re: [B.A.T.M.A.N.] [RFC] ELP

[Marek Lindner]

Hi Andrew,

excuse the delayed answers - the wbmv5 was rather intense.  ;-)


> The problem with broadcasting the ELP packets is that they are always
> sent with the most robust coding rate. So ELP gives you an idea how
> good the 1Mbps broadcast channel is, not how good the unicast channel
> the automatic rate selection algorithm is using is. I think we
> discussed mixing in some unicast packets in the forward direction. The
> ELP packets containing the reports would stay the same, and so
> function as node detection. But a node could also send out unicast ELP
> packets to its known neighbours and they would be included into the
> LQ.
> 
> There are obvious drawbacks. More overhead, especially in dense
> networks. It is also not clear if the measurements would be
> better. Unicast packets get a number of retries with fast ACKs, where
> as multicast does not. So multicast might actually give a better
> measure of the link at 1Mbps.
> 
> Do you know if Linus had chance to explore these ideas during his
> GSOC?

the problem is known but we did not have enough time to explore it. One idea 
we had in mind was sending larger ELP broadcast packets every now and then in 
the hope of better estimating the link quality. The feature to increase the 
ELP packet size is part of this patchset and would allow to test this idea.

On the other hand I think we should move towards throughput based path 
decisions. It tells us so much more about what we really care about. Some 
obstacles are waiting for us if we go down this path. Have you ever 
experimented with this approach ?

Regards,
Marek

Re: [B.A.T.M.A.N.] [RFC] ELP

[Marek Lindner]

On Friday, March 23, 2012 08:34:18 Andrew Lunn wrote:
> > cat /sys/kernel/debug/batman_adv/routing_algos
> > Available routing algorithms:
> > BATMAN IV
> > BATMAN V
> > 
> > To activate B.A.T.M.A.N. V (ELP) you should run the following command
> > *before* adding any interface via batctl:
> > 
> > echo -n "BATMAN V" > /sys/module/batman_adv/parameters/routing_algo
> 
> How about BATMAN_V and BATMAN_IV, so avoiding the need for "" or \
> escaping of the space?

Sure, why not.

Regards,
Marek

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Andrew Lunn]

> > I have been thinking about this a bit more, and also about this bit of
> > code:
> > 
> > +       elp_packet = (struct batman_elp_packet
> > *)skb_push(hard_iface->elp_skb, +                                         
> >                BATMAN_ELP_HLEN); +       memset(elp_packet, 0,
> > BATMAN_ELP_HLEN);
> > +
> > +       elp_packet->header.packet_type = BAT_V_ELP;
> > +       elp_packet->header.version = COMPAT_VERSION;
> > +       elp_packet->header.ttl = 0;
> > 
> > Marek, what are your plans for COMPAT_VERSION? Will there be a
> > COMPAT_VERSION_IV and COMPAT_VERSION_V sometime soon?
> 

> Currently, that is not planned. We hoped to keep the compat numbers
> in sync across the various protocols. Otherwise we all could end up
> in compat hell.

Can they be kept in sync? I would assume that IV is becoming more and
more stable, with more effort going into V. So IV is less probable to
need an COMPAT increment than V. The three month kernel cycle helps
with the sync, but it would be a PITA to have to upgrade an entire IV
net because V have forced a COMPAT increment, but IV has not changed
and is compatible.

> > Maybe when registering a receive function, you can pass both the
> > packet_type and version. So a received ELP packet with
> > COMPAT_VERSION_IV would automatically get tossed away, and an ELP with
> > COMPAT_VERSION_V would get dispatched.
> 

> What would be the use case of ELP COMPAT_VERSION_IV vs ELP
> COMPAT_VERSION_V ?  BATMAN IV does not have ELP at all .. maybe I
> misunderstand ?

The COMPAT_VERSION effectively becomes an indicator of the protocol,
assuming they are different. However, this is the opposite to your
idea of keeping them in sync.

Since there would be no ELP registered for COMPAT_VERSION_IV, the
packet would be discarded by the dispatcher. However,
COMPACT_VERSION_V would register an ELP function and the dispatcher
would use it.

Making the dispatcher aware of these two dimensions, (MSG_Type,
Version), puts all the checking in one place and makes the individual
message handlers simpler.

Anyway, just an idea...

	Andrew

Re: [B.A.T.M.A.N.] [RFC 2/5] batman-adv: ELP - creating neighbor structures, updating LQs

[Marek Lindner]

On Friday, April 06, 2012 10:17:29 Andrew Lunn wrote:
> > Currently, that is not planned. We hoped to keep the compat numbers
> > in sync across the various protocols. Otherwise we all could end up
> > in compat hell.
> 
> Can they be kept in sync? I would assume that IV is becoming more and
> more stable, with more effort going into V. So IV is less probable to
> need an COMPAT increment than V. The three month kernel cycle helps
> with the sync, but it would be a PITA to have to upgrade an entire IV
> net because V have forced a COMPAT increment, but IV has not changed
> and is compatible.

If you check our compat number history[1] you will see that the compat number 
changes when features are added (tt rewrite, gateway flags, unicast 
fragmentation, etc). These features are the same across protocols.

Another motivation to not further grow the compat number world is backward 
compatibility. Larger mesh installations will need to upgrade the mesh step by 
step instead of updating everything at once. As a result we must switch 
towards smoother compatibility breaks in the future otherwise upgrading will 
become a real pain. We have created a wiki page [2] to collect ideas for 
better backward compatibility. 


> The COMPAT_VERSION effectively becomes an indicator of the protocol,
> assuming they are different. However, this is the opposite to your
> idea of keeping them in sync.
> 
> Since there would be no ELP registered for COMPAT_VERSION_IV, the
> packet would be discarded by the dispatcher. However,
> COMPACT_VERSION_V would register an ELP function and the dispatcher
> would use it.
> 
> Making the dispatcher aware of these two dimensions, (MSG_Type,
> Version), puts all the checking in one place and makes the individual
> message handlers simpler.

The dispatcher has to work on a per interface basis to make this work. It 
would need to do the same check we currently have, to verify that a given 
interface wants to have packets from this or that protocol.

Regards,
Marek


[1] http://www.open-mesh.org/wiki/batman-adv/Compatversion
[2] http://www.open-mesh.org/wiki/batman-adv/Packet-types

Re: [B.A.T.M.A.N.] [RFC] ELP

[Andrew Lunn]

On Thu, Apr 05, 2012 at 11:30:06PM +0300, Marek Lindner wrote:
> 
> Hi Andrew,
> 
> excuse the delayed answers - the wbmv5 was rather intense.  ;-)

I got that impression for the mailing lists... 
 
> On the other hand I think we should move towards throughput based
> path decisions. It tells us so much more about what we really care
> about. Some obstacles are waiting for us if we go down this
> path. Have you ever experimented with this approach ?

Not directly, but we did something in SPAWN which might be relevant.

SPAWN is the automatic deployment of nodes to form a mesh inside a
building. The use case is for firemen deploying nodes behind them to
give mesh access to outside the building.

We want to know the link quality to the last two nodes in the chain as
part of the decision when to deploy the next node in the chain. Due to
work split between partners in the project, and other reasons, BATMAN
is not involved in the deployment, it only gets involved once a node
has been deployed. However, there is obvious overlap here...

The user space code monitors the link quality making use of the
monitor interface of mac80211. One minor change was made in the kernel
that allowed us to set the rate the packet would be sent at from user
space on a packet by packet basis. So we could send probe packets at
different rates and see which got received. You then have some idea of
the link quality, what coding rates work. But it does not necessarily
tell you too much about the link capacity, since you have no idea
about other users of the air-space.

For a research project, such code is O.K. However, for something going
into mainline, i doubt it would be accepted without strong arguments
about why the existing rate control algorithm cannot be used. One
difference is active vs passive. Minstral, as far as i know, makes use
of existing data packets to determine the best coding rate. What the
project built used its own packets. Thus it was faster to react in a
changing environment when there was little traffic, which is the exact
conditions during deployment.

There is a continuum here. What BATMAN has, and probably also OLSR,
Babel, etc, is:

The quality of packets sent using broadcast at 1Mbps.

Using the idea above, probing using different rates we get:

The quality of packets sent using broadcast at X Mbps.

We can build a metric based on (TQ, X), picking X such that TQ is
above some threshold.

If we can get reliable information out of minstral, we get:

X Mbps used for sending unicast packets in the recent past.

but this is a big change. We have lost TQ, but gained unicast to the
specific originator we want the metric for. We no longer need to send
probe packets, so have less overhead, but depend on there being some
traffic in order that minstral can do its thing.

If we send unicast probe packets, and combine it with minstral:

The quality of packets send using unicast at X Mbps.

We have no choice on X, Minstral decides it. This is in fact good,
since the real data also get X. We have a metric based on (TQ, X). How
we actually determine X is interesting. TQ is a moving window
average. Can we do the same for X? Minstral will already be doing some
averaging, so maybe just use the latest value?

So far, we have no idea about available capacity of the link:

Determine X from Minstral. Send a burst of packets forcing them to be
sent at rate X and without retries. Time how long it takes to send the
packets. Compare this with the theoretical time needed, assuming no
congestion, to calculate a congestion factor C.

You now can build a metric based on (TQ, X, C). But you have more
overhead, because you need a burst of unicast packets, and a lot more
complexity, but you have an idea of the free capacity of the link.

	    Andrew

Re: [B.A.T.M.A.N.] [RFC] ELP

[dan]

>
> but this is a big change. We have lost TQ, but gained unicast to the
> specific originator we want the metric for. We no longer need to send
> probe packets, so have less overhead, but depend on there being some
> traffic in order that minstral can do its thing.
>
> If we send unicast probe packets, and combine it with minstral:
>
> The quality of packets send using unicast at X Mbps.
>
> We have no choice on X, Minstral decides it. This is in fact good,
> since the real data also get X. We have a metric based on (TQ, X). How
> we actually determine X is interesting. TQ is a moving window
> average. Can we do the same for X? Minstral will already be doing some
> averaging, so maybe just use the latest value?
>
> So far, we have no idea about available capacity of the link:
>
> Determine X from Minstral. Send a burst of packets forcing them to be
> sent at rate X and without retries. Time how long it takes to send the
> packets. Compare this with the theoretical time needed, assuming no
> congestion, to calculate a congestion factor C.
>
> You now can build a metric based on (TQ, X, C). But you have more
> overhead, because you need a burst of unicast packets, and a lot more
> complexity, but you have an idea of the free capacity of the link.
>
>            Andrew

disclaimer: I am an end user, not a dev.  I run a wISP (no mesh right
now, ringed).  Also, this is an evolved version of other ideas I
posted here.

So here is my thought.  How can you possibly test a wireless link for
quality and capacity without sending enough data to stress the link?
I do a lot of statistical work on historical product movement and
sales, so I am trying to apply some lessons learned there to this
problem.  The only way to know capacity is to measure it.  You cannot
measure nothing, that is 'null', and generating traffic to measure
decreases capacity/increases overhead.

My train of thought here says that you must use historical data and
statistics.  For this period of time x (5 seconds?), interface y
transfered the aggregate amount of data z and latency to the next node
in the path was L.  later, x and y are unchanged but z is higher and L
spikes. later x and y are unchanged but z in low and L is similar to
the first entry.  Keep these high water marks around and lower them
when the history shows them to be invalid.

From this we can statistically say that interface y is able to
transfer z before L spikes.  This is theoretical capacity of the
connection.  obviously, this is over wireless links so these are
dynamic numbers that must be adjusted within some timeframe to
changing conditions.

I find that most wireless links maintain good latency until they reach
a breaking point and then the latency collapses.  it hits a wall.

In the wISP world, I pre-test links and configure the radios
modulation to the highest stable value.  The link might negotiate at
MCS15 but collapses at anything over MCS13.  I do not rely on
auto-adjustments here.  The phenomenon of fresnel zone echo can make a
link look great until data is transfered, then the echos from fresnel
zone infractions destroys the link.  The only way to know what is on
the link is to push data across it.  When I do this test, I can
negatively effect other clients on the radio.  This is a necessary
evil for me and my tests are brief and infrequent.

If batman-adv is able to take these sort of measurements, or is able
to read the results of a helper application that does the math, then
it stands to reason that these numbers could be read by a helper
application and the maximum modulation of a radio could be set with
userspace utils (like iw) to fit the calculation to further stabilize
the link.  You can nudge the values up periodically to test with.  If
a link is MCS2 per the calculations, nudge it up to MCS3 and let the
algorythm do its magic.  If it still thinks that 19.5Mb is optimal we
can bring the mod back down to MCS2 (via helper app), if it shows as
good we will leave it at MCS3 for a while then nudge it up to MCS4.
Never jump up from MCS2 to 4 because the link might completely
collapse. rinse, repeat.

Re: [B.A.T.M.A.N.] [RFC] ELP

[Andrew Lunn]

> disclaimer: I am an end user, not a dev.  I run a wISP (no mesh right
> now, ringed).  Also, this is an evolved version of other ideas I
> posted here.

Hi Dan

Are you talking about point to point links using highly directional
antennas, or a bunch of omni directional systems all on the same
channel interfering with each other?

I've not yet looked at the details of what you said, but i get the
feeling you are thinking about the first? Is that right?

    Andrew

Re: [B.A.T.M.A.N.] [RFC] ELP

[dan]

On Fri, Apr 6, 2012 at 11:19 AM, Andrew Lunn <andrew@lunn.ch> wrote:
>> disclaimer: I am an end user, not a dev.  I run a wISP (no mesh right
>> now, ringed).  Also, this is an evolved version of other ideas I
>> posted here.
>
> Hi Dan
>
> Are you talking about point to point links using highly directional
> antennas, or a bunch of omni directional systems all on the same
> channel interfering with each other?
>
> I've not yet looked at the details of what you said, but i get the
> feeling you are thinking about the first? Is that right?
>
>    Andrew

Andrew, ideally all link types.  If you are going to select path based
on both TQ AND capacity, or you are going to adjust TQ based on the
current criteria as well as capacity, all links matter right?

Highly directional p2p links are usually much more predictable than
the AdHoc cloud, so I would say the local AdHoc cloud is the target.
I have been looking at how to get the throughput on adhoc clouds but
it seems that most wireless adapters 'monitor' mode is exclusive, it
would take the link down to monitor the connection.  In adhoc, the
local nodes throughput isn't so important, because two other clients
might be saturating the airwaves.  Need to listen to all traffic on
the waves to see capacity.

If it was easy, someone else would have already done it right ;)