commits July 2017

commits@lists.open-mesh.org

1 participants
1317 discussions

[doc] backup-redmine/2017-07-13, master: doc: open-mesh/Gsoc2011-ideas: adding some more detailed descriptions (f0c54298)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

1 0

[doc] backup-redmine/2017-07-13, master: doc: open-mesh/Gsoc2011-ideas: adding some more descriptions (191b4e11)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

Repository : ssh://git@open-mesh.org/doc On branches: backup-redmine/2017-07-13,master >--------------------------------------------------------------- commit 191b4e1177152ed582851dd409deaa8e948e6b63 Author: Linus Lüssing <linus.luessing(a)c0d3.blue> Date: Mon Feb 28 01:12:03 2011 +0000 doc: open-mesh/Gsoc2011-ideas: adding some more descriptions >--------------------------------------------------------------- 191b4e1177152ed582851dd409deaa8e948e6b63 open-mesh/Gsoc2011-ideas.textile | 140 +++++++++++++++------------------------ 1 file changed, 55 insertions(+), 85 deletions(-) diff --git a/open-mesh/Gsoc2011-ideas.textile b/open-mesh/Gsoc2011-ideas.textile index ec2a2073..4d762e76 100644 --- a/open-mesh/Gsoc2011-ideas.textile +++ b/open-mesh/Gsoc2011-ideas.textile @@ -1,104 +1,78 @@ += Google Summer of Code 2011 - Ideas = -h1. Google Summer of Code 2011 - Ideas +== batman-adv == +=== Categories + Usecases to improve === + * Increasing Robustness + * Improving Mobility / Convergence Speed + * Improving Indoor performance + * Improving VoIP group multicast performance + * Improving nomadic scenarios (circular + chain topology) - - -h2. batman-adv == - Categories + Usecases to improve === -* Increasing Robustness -* Improving Mobility / Convergence Speed -* Improving Indoor performance -* Improving [[VoIP]] group multicast performance -* Improving nomadic scenarios (circular + chain topology) - - -h3. Specific Tasks === - Dynamic OGM+NDP intervals ==== -*Brief description:* A batman-adv node shall select originator interval rates according to the dense and dynamics in its closer environment. +=== Specific Tasks === +==== Dynamic OGM+NDP intervals ==== +'''Brief description:''' A batman-adv node shall select originator interval rates according to the dense and dynamics in its closer environment. Depending on the usage scenario, people can adjust the bandwidth being used for batman-adv's route finding algorithms. Usually people were advised to increase the originator interval if the mesh network is small but needs fast route refresh rates or to decrease it if the mesh network is mostly a static setup with a lot of nodes. It would be great if a batman-adv node could determine the dynamics of the mesh network it is currently participating in on its own so that this option would not have to be administrated from a person anymore. For instance in combination with the 'B.A.T.M.A.N. protocol overhead reduction' project, the local broadcasts could be automatically increased if there are not that many direct neighbors. - -h4. OGM/NDP Hidden Node Problem Avoidance - -*Brief description:* Implement a suitable solution against hidden node broadcast packet problem. +==== OGM/NDP Hidden Node Problem Avoidance ==== +'''Brief description:''' Implement a suitable solution against hidden node broadcast packet problem. Especially in indoor scenarios where corners and thick walls are involved, hidden nodes can be a severe problem. Usually activating RTS/CTS is a common way of solving this problem at least to some degree. However, RTS/CTS can only be applied for unicast packets. Therefore a node sending a lot of data packets to another one, even with RTS/CTS those packets will interfere with BATMAN's broadcast packets (e.g. NDP packets or OGMs). The effect is, that the transmit quality of a node sending NDP packets which does not see the data packet transmission will greatly decrease. -A suitable solution shall be implemented. This might be based on time slots, multiple interfaces or channel switching and might be implemented within batman-adv or an extra module. See "here":http://www.open-mesh.org/wiki/bcast-hidden-node for a more detailed description of the problem and a solution proposal. - - -h4. OGM/NDP Congestion Avoidance +A suitable solution shall be implemented. This might be based on time slots, multiple interfaces or channel switching and might be implemented within batman-adv or an extra module. See [http://www.open-mesh.org/wiki/bcast-hidden-node here] for a more detailed description of the problem and a solution proposal. -*Brief description:* Implement a congestion avoidance mechanism for batman-adv's routing control packets against congestion caused by high data transfer rates. +==== OGM/NDP Congestion Avoidance ==== +'''Brief description:''' Implement a congestion avoidance mechanism for batman-adv's routing control packets against congestion caused by high data transfer rates. -In case of a mesh network congested due to e.g. a lot of UDP packets, the packet loss rate of batman's OGMs or NDP packets increases severely, as neither OGMs/NDP nor UDP have a congestion control mechanism. For one thing, lost OGMs lead to a high degradation of batman's convergence speed. For another, lost NDP packets lead to route flipping; in the worst case some of these chosen routes are not usable. batman-adv has the advantage of being able to control the whole packet, both data and control packets, within the mesh network. Therefore time spaces for OGMs/NDP packets could be allocated, as already described in "OGM/NDP Hidden Node Problem Avoidance" / "Or prioritized queues could be introduced. +In case of a mesh network congested due to e.g. a lot of UDP packets, the packet loss rate of batman's OGMs or NDP packets increases severely, as neither OGMs/NDP nor UDP have a congestion control mechanism. For one thing, lost OGMs lead to a high degradation of batman's convergence speed. For another, lost NDP packets lead to route flipping; in the worst case some of these chosen routes are not usable. batman-adv has the advantage of being able to control the whole packet, both data and control packets, within the mesh network. Therefore time spaces for OGMs/NDP packets could be allocated, as already described in "OGM/NDP Hidden Node Problem Avoidance" / [http://www.open-mesh.org/wiki/bcast-hidden-node]. Or prioritized queues could be introduced. - -h4. B.A.T.M.A.N. Routing Framework - -*Brief description:* Separate B.A.T.M.A.N. routing algorithm from routing infrastructure in batman-adv. +==== B.A.T.M.A.N. Routing Framework ==== +'''Brief description:''' Separate B.A.T.M.A.N. routing algorithm from routing infrastructure in batman-adv. Many features in batman-adv are routing algorithm independent: Link layer routing, link layer fragmentation, multicast optimizations, NDP, interface bonding. To allow other routing algorithms to use this already well tested infrastructure, the B.A.T.M.A.N. routing algorithm shall be separated more clearly from the routing infrastructure. Ultimately, other routing protocols shall be able to control the kernel space mesh routing infrastructure from userspace. - -h4. Improve Throughput Bonding - -*Brief description:* Improve performance gain of the throughput bonding mode. +==== Improve Throughput Bonding ==== +'''Brief description:''' Improve performance gain of the throughput bonding mode. The current bonding mode implementation simply sends a data packet in a round robin fashion to the interfaces available for bonding. However, the throughput gain seems to be only about 66%25 instead of doubling the throughput in case of TCP, even if there is no other interference involved. This seems to be the case due to a heavy reordering issue. Furthermore, the interface with the lowest capacity is a bottleneck for the throughput bonding performance: In case of one interface of 1MBit/s throughput and five more with 2MBit/s throughput, the actual throughput will be just 6x 1MBit/s. However in mixed wireless and wired networks, it might be desirable to accumulate the throughput of a Gigabit-Ethernet interface and a 802.11g interface. Therefore checks for links' capacities (detect full queues etc.) to gain performance of IF1 + IF2 + ... instead of min(IF1, IF2, ...) shall be implemented. If an interface is busy, it shall be skipped in this round robin cycle. Furthermore simple per hop pre-ordering on batman-adv's layer shall be implemented to increase the TCP performance. - -h4. Unit Test Infrastructure - -*Brief description:* Create a flexible unit test infrastructure to increase batman-adv's stability. +==== Unit Test Infrastructure ==== +'''Brief description:''' Create a flexible unit test infrastructure to increase batman-adv's stability. As batman-adv resides in the Linux kernel any crash in batman-adv has severe consequences for the whole system. For instance a deadlock or aceesing invalid memory in batman-adv will freeze the whole system. Typically most embedded routers have a watchdog to restart the device automatically in such situations. However in critical usage scenarios, a reboot of the device might not be tolerable. Therefore a unit test infrastructure shall be created which for one thing tests and verifies single functions and functionalities within the batman-adv code base. And for another it shall stress test the complete software for different virtualized, static and dynamic topologies. +==== IPv6 Stateless Autoconf Gateway Solution ==== +'''Brief description:''' Implement a gateway solution for IPv6 stateless autoconfiguration -h4. IPv6 Stateless Autoconf Gateway Solution - -*Brief description:* Implement a gateway solution for IPv6 stateless autoconfiguration - -batman-adv operates on layer 2, therefore intelligent layer 3 gateway handling is not straightforward. batman-adv currently supports intelligent gateway handling for DHCP (both IPv4 and IPv6), in that it forwards any DHCP discovery or request packet to the best (according to batman's metric) gateway available only, via unicast. However, this is not doable for IPv6 stateless autoconfiguration, as usually not the client is not actively requesting an IP address, but the router is advertising it's gateway capabilities periodically. However, such a stateless configuration is usually more desirable than a stateful configuration as in DHCP in dynamic mesh networks as it allows smoother transitions between subnets and is not as prone to packet loss. Therefore a solution for IPv6 Stateless autoconfiguration shall be implemented. This may be done by exploiting the router preference fields in the router advertisement messages, [http://tools.ietf.org/html/rfc4191 RFC4191":http://www.open-mesh.org/wiki/bcast-hidden-node]., and/or by limiting the range of router advertisements with the help of batman-adv's broadcast packet's TTL field or by introducing a new TQ limit field. A TQ limit field could be dynamically adapted to minimze the overhead of such router advertisements in case of many gateways but ensuring the availability of the best/closest of all gateways in the mesh network. +batman-adv operates on layer 2, therefore intelligent layer 3 gateway handling is not straightforward. batman-adv currently supports intelligent gateway handling for DHCP (both IPv4 and IPv6), in that it forwards any DHCP discovery or request packet to the best (according to batman's metric) gateway available only, via unicast. However, this is not doable for IPv6 stateless autoconfiguration, as usually not the client is not actively requesting an IP address, but the router is advertising it's gateway capabilities periodically. However, such a stateless configuration is usually more desirable than a stateful configuration as in DHCP in dynamic mesh networks as it allows smoother transitions between subnets and is not as prone to packet loss. Therefore a solution for IPv6 Stateless autoconfiguration shall be implemented. This may be done by exploiting the router preference fields in the router advertisement messages, [http://tools.ietf.org/html/rfc4191 RFC4191], and/or by limiting the range of router advertisements with the help of batman-adv's broadcast packet's TTL field or by introducing a new TQ limit field. A TQ limit field could be dynamically adapted to minimze the overhead of such router advertisements in case of many gateways but ensuring the availability of the best/closest of all gateways in the mesh network. +==== Improve Broadcast Data Performance ==== +'''Brief description:''' Optimize the flooding of broadcast data to reduce overhead and increase its packet delivery ratio. -h4. Improve Broadcast Data Performance +So far broadcast data packets are flooded through the whole mesh network. As broadcast packets do not have an ARQ mechanism to reduce packet losses like unicast data transfer has, batman-adv (re)transmits broadcast packets on each hop by default. In dense topologies this can introduce unnecessary overhead, in sparse topologies the packet delivery ratio might be too low. Therefore a smarter mechanism than classic flooding shall be implemented to improve batman-adv's performance for broadcast data packets. This may done taking link qualities in the local neighborhood into account and adjusting the number of rebroadcasts dynamically. Or by introducing [http://en.wikipedia.org/wiki/Multipoint_relay MPR]-like mechanisms. -*Brief description:* Optimize the flooding of broadcast data to reduce overhead and increase its packet delivery ratio. - -So far broadcast data packets are flooded through the whole mesh network. As broadcast packets do not have an ARQ mechanism to reduce packet losses like unicast data transfer has, batman-adv (re)transmits broadcast packets on each hop by default. In dense topologies this can introduce unnecessary overhead, in sparse topologies the packet delivery ratio might be too low. Therefore a smarter mechanism than classic flooding shall be implemented to improve batman-adv's performance for broadcast data packets. This may done taking link qualities in the local neighborhood into account and adjusting the number of rebroadcasts dynamically. Or by introducing "MPR":http://en.wikipedia.org/wiki/Multipoint_relay-like mechanisms. - - -h4. Reduce ARP (/ND) latency and overhead - -*Brief description:* Reduce ARP latency and overhead by implementing an ARP cache. +==== Reduce ARP (/ND) latency and overhead ==== +'''Brief description:''' Reduce ARP latency and overhead by implementing an ARP cache. batman-adv operates on the link layer, therefore any network protocol (e.g. IPv4/6) needs to perform an MAC address lookup for any IP address through the mesh network first. As ARP packets are broadcast packets, batman-adv simply floods them through the whole mesh network. This can create quite some overhead in large scale mesh networks or high latencies in case of mesh networks with poor links. Therefore an ARP cache shall be implemented on each node so that they could answer ARP requests directly to any host on their segment instead of flooding it through the whole mesh again. Something similiar may be implemented for IPv6's Neighbor Discovery (ND) mechanism. +==== Dead node fast path switching/invalidating ==== +'''Brief description:''' Improve batman-adv to respond quicker to node/link failures and avoid packet drops in case of link failures. -h4. Dead node fast path switching/invalidating - -*Brief description:* Improve batman-adv to respond quicker to node/link failures and avoid packet drops in case of link failures. - -When a node notices the breakdown of a neighbor (see [[routing_scenarios#Convergencespeed|routing scenarios]] to get an idea about the conditions), this node could send any data packet, which it would usually send over this neighbor to either its second best hop if available (which does not always have to be the case due to OGM forwarding policies). Or it could send the packet back to the next hop towards the source again. With the help of sequence numbers, any node on the 'backtracking' path (the backtracking path can be different from the usual path in case of asymmetric links) could notice that a path became invalid very quickly. - - -h4. Link layer FEC/ARQ/Fragmentation module +When a node notices the breakdown of a neighbor (see [wiki:routing_scenarios#Convergencespeed routing scenarios] to get an idea about the conditions), this node could send any data packet, which it would usually send over this neighbor to either its second best hop if available (which does not always have to be the case due to OGM forwarding policies). Or it could send the packet back to the next hop towards the source again. With the help of sequence numbers, any node on the 'backtracking' path (the backtracking path can be different from the usual path in case of asymmetric links) could notice that a path became invalid very quickly. -*Brief description:* Create a kernel module that can be added onto an interface which performs link layer optimizations (FEC, ARQ, Fragmentation, ...). +==== Link layer FEC/ARQ/Fragmentation module ==== +'''Brief description:''' Create a kernel module that can be added onto an interface which performs link layer optimizations (FEC, ARQ, Fragmentation, ...). The ARQ and FEC mechanisms provided in 802.11 for unicast data packets is mainly optimized for one hop scenarios only. While the packet delivery ratio on one hop might be fine, it might not be usable for multiple hops in a mesh network. Therefore a link-layer kernel module shall be implemented which performs Forward Error Correction and Automatic Repeat reQuest with dynamic parametrizations, to achieve a certain, configured target packet delivery ratio. Furthermore, the fragmentation from batman-adv could be moved to this link layer module, too. Such a module would then provide a virtual interface which batman-adv would use instead of the actual wifi/ethernet interfaces. - -h3. Further Tasks - -* Link quality / Packet delivery ratio measurement improvements +=== Further Tasks === + * Link quality / Packet delivery ratio measurement improvements -> weighted/exponential moving average -> testing / performance measurements of / improving NDP, find and improve "performance bottlenecks" -* Multicast Optimization Algorithm enhancements + * Multicast Optimization Algorithm enhancements -> implement reactive tracker packet mode -> decrease latency of reactive tracker packet mode: attaching small data packets to tracker packet, if MTU fits (otherwise broadcast) in react. mode? ...? -> ultimately, make proactive tracker mode obsolete @@ -106,23 +80,19 @@ h3. Further Tasks -> don't send tracker packets if <= 1 destination or > 50%25 of all nodes are destinations -> Enhance HNA, host network announcements, improvement scheme to also support MCAs, multicast announcements -> ... -* Further HNA roaming improvements -* "Network Coding":http://en.wikipedia.org/wiki/Network_coding? -* Packet signing: Add a signing mechanism to identify OGM's sender and drop malicious nodes -* built-in bandwidth test tool ? - - -h2. batctl - -* Enhance live link quality monitoring: bisect -> dot-files -> graphs -> to (live) video? (+ adding horst tool information, wifi interface stats?) -* Add further info to batman-adv vis servers/clients for debugging networks -* bisect, include initial state -* live vis in map (HTML5 + Openstreetmap?) - - -h2. misc - -* multiple interface support in Mesh 3D -* ap51flash GUI; ap51flash multi-flash on single interface -* Android/Maemo/Meego porting + _maintenance_! -* Cooperative work with Pidgin guys? (video/audio/file-transfer/bonjour in pidgin and improving its + batman-adv's combined performance in a mesh network?) \ No newline at end of file + * Further HNA roaming improvements + * [http://en.wikipedia.org/wiki/Network_coding Network Coding]? + * Packet signing: Add a signing mechanism to identify OGM's sender and drop malicious nodes + * built-in bandwidth test tool ? + +== batctl == + * Enhance live link quality monitoring: bisect -> dot-files -> graphs -> to (live) video? (+ adding horst tool information, wifi interface stats?) + * Add further info to batman-adv vis servers/clients for debugging networks + * bisect, include initial state + * live vis in map (HTML5 + Openstreetmap?) + +== misc == + * multiple interface support in Mesh 3D + * ap51flash GUI; ap51flash multi-flash on single interface + * !Android/Maemo/Meego porting + _maintenance_! + * Cooperative work with Pidgin guys? (video/audio/file-transfer/bonjour in pidgin and improving its + batman-adv's combined performance in a mesh network?) \ No newline at end of file

1 0

[doc] backup-redmine/2017-07-13, master: doc: batman-adv/Quick-start-guide: instead you are just using the new bridge interface 'mesh-bridge' for routing: clarify that IP has to be assigned to mesh-bridge (ea02ac39)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

Repository : ssh://git@open-mesh.org/doc On branches: backup-redmine/2017-07-13,master >--------------------------------------------------------------- commit ea02ac394601e48ed2de3af83b6d9373573eb003 Author: Hendrik Fabelje <batman(a)fabelje.de> Date: Wed Mar 2 16:55:26 2011 +0000 doc: batman-adv/Quick-start-guide: instead you are just using the new bridge interface 'mesh-bridge' for routing: clarify that IP has to be assigned to mesh-bridge >--------------------------------------------------------------- ea02ac394601e48ed2de3af83b6d9373573eb003 batman-adv/Quick-start-guide.textile | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/batman-adv/Quick-start-guide.textile b/batman-adv/Quick-start-guide.textile index 9258906b..1fcf9a38 100644 --- a/batman-adv/Quick-start-guide.textile +++ b/batman-adv/Quick-start-guide.textile @@ -1,4 +1,3 @@ - = B.A.T.M.A.N. Advanced quick start guide = {{{ @@ -72,6 +71,8 @@ ifconfig mesh-bridge up From now on you won't want to use eth0, wlan0 or bat0 for any routing anymore, instead you are just using the new bridge interface 'mesh-bridge'. Any packet our mesh access point receives over eth0 will be forwarded to bat0 because of the bridge. batman-adv will forward it through the mesh according to the destination's mac address. +'''Note:''' Assign the IP Address to mesh-bridge in this case, not bat0. + For the MTU-part have a look at the note above. ''(How does batman-adv know where it has to send a data packet of an external computer, that is not using batman-adv, to another computer that is not using batman-adv either? It is automatically listening on bat0 and will keep track of any host mac address passing by this interface. Those host's mac addresses will then be announced to other batman-adv nodes in the mesh network automatically - so called HNA messages - so that every batman-adv node is going to know behind which other batman-adv node it can find which mac addresses.)''

1 0

[doc] backup-redmine/2017-07-13, master: doc: batman-adv/OGM: adding some more OGM protocoll stuff (3f42c525)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

Repository : ssh://git@open-mesh.org/doc On branches: backup-redmine/2017-07-13,master >--------------------------------------------------------------- commit 3f42c5250a5865f7e7b8391ecea4a8fa3ded221e Author: Linus Lüssing <linus.luessing(a)c0d3.blue> Date: Wed Mar 2 11:35:53 2011 +0000 doc: batman-adv/OGM: adding some more OGM protocoll stuff >--------------------------------------------------------------- 3f42c5250a5865f7e7b8391ecea4a8fa3ded221e batman-adv/OGM.textile | 156 +++++++++++++++++++++---------------------------- 1 file changed, 68 insertions(+), 88 deletions(-) diff --git a/batman-adv/OGM.textile b/batman-adv/OGM.textile index fcb5cf41..6b29fc10 100644 --- a/batman-adv/OGM.textile +++ b/batman-adv/OGM.textile @@ -1,54 +1,46 @@ += Originator Message (OGM) = -h1. Originator Message (OGM) +{{{ +#!div style="width: 46em; text-align: justify" +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 [wiki:BATMANConcept B.A.T.M.A.N. concept page] and explained in details in [http://tools.ietf.org/html/draft-wunderlich-openmesh-manet-routing-00 the RFC draft] published in 2008. -<pre> -<code class="div"> - -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 [[BATMANConcept|BATMAN concept page]] and explained in details in "the RFC draft":http://tools.ietf.org/html/draft-wunderlich-openmesh-manet-routing-00 published in 2008. - -With the new concept of a separate [[batman-adv-ndp|NDP]] the tasks performed by OGMs becomes way simpler: While local work is done by NDP, information gets distributed in the mesh network with the OGM protocol, in that OGMs' primary task is to advertise path qualities, without determening link qualities. OGMs also still have the important task to distribute Host Network Annoncements, HNA for short. +With the new concept of a separate [wiki:batman-adv-ndp NDP] the tasks performed by OGMs becomes way simpler: While local work is done by NDP, information gets distributed in the mesh network with the OGM protocol, in that OGMs' primary task is to advertise path qualities, without determening link qualities. OGMs also still have the important task to distribute Host Network Annoncements, HNA for short. This bears the following advantages from the OGM point of view: -* Reduced overhead, as OGMs can then be send with a slower interval. The BATMAN routing algorithm still has a squared amount of overhead in worst case scenarios, therefore the the slower intervals are very desireable. -* The BATMAN core routing protocol becomes less entangled with other mechanisms and features, making it easier understand and to perform theoretical analysis on. -* Easier to optimize the OGMs convergence speed. - - -h2. Definitions - -* node - A mesh router which utilizes the B.A.T.M.A.N. protocol as specified in this document on at least one network interface. A node consists of one or more originators. -* originator - An addressable entity within one mesh network routing layer. An originator's address has to be unique within a mesh network routing layer and unique on a node. A node's hard-interface may only be utilized by zero or one originator. -* B.A.T.M.A.N./hard interface - Network interface utilized by B.A.T.M.A.N. for its own ethernet frames. -* sliding window - Sequence numbers are recorded in dedicated sliding windows until they are considered out-of range. Thus, such a sliding window always contains the set of recently received sequence numbers. The amount of sequence numbers recorded in the sliding window is used as a metric for the quality of detected links and paths. -* duplicate - A received NDP message from a neighbor containing an already received sequence number. -* out of order - A received NDP message from a neighbor containing a sequence number that is older than the newest sequence number ever received from this neighbor. -* HNA - Host Network Announcement, a host's MAC address which is addressable on the mesh layer and which this originator is responsible for. This may be either the originator itself (bat0's MAC) or a bridged in host. -* Router: -* Sender: The originator belonging to a received OGM's ethernet frame source address. -* global TQ value: The linear mapping of an OGM's global TQ field to a value between 0 and 1 (global TQ / TQ_MAX = global TQ value). - - -h2. Protocol Procedure - - - -h4. Broadcasting own Originator Message (OGM) - + * Reduced overhead, as OGMs can then be send with a slower interval. The BATMAN routing algorithm still has a squared amount of overhead in worst case scenarios, therefore the the slower intervals are very desireable. + * The BATMAN core routing protocol becomes less entangled with other mechanisms and features, making it easier understand and to perform theoretical analysis on. + * Easier to optimize the OGMs convergence speed. + +== Definitions == + * node - A mesh router which utilizes the B.A.T.M.A.N. protocol as specified in this document on at least one network interface. A node consists of one or more originators. + * originator - An addressable entity within one mesh network routing layer. An originator's address has to be unique within a mesh network routing layer and unique on a node. A node's hard-interface may only be utilized by zero or one originator. + * B.A.T.M.A.N./hard interface - Network interface utilized by B.A.T.M.A.N. for its own ethernet frames. + * sliding window - Sequence numbers are recorded in dedicated sliding windows until they are considered out-of range. Thus, such a sliding window always contains the set of recently received sequence numbers. The amount of sequence numbers recorded in the sliding window is used as a metric for the quality of detected links and paths. + * duplicate - A received NDP message from a neighbor containing an already received sequence number. + * out of order - A received NDP message from a neighbor containing a sequence number that is older than the newest sequence number ever received from this neighbor. + * HNA - Host Network Announcement, a host's MAC address which is addressable on the mesh layer and which this originator is responsible for. This may be either the originator itself (bat0's MAC) or a bridged in host. + * Router: + * Sender: The originator belonging to a received OGM's ethernet frame source address. + * global TQ value: The linear mapping of an OGM's global TQ field to a value between 0 and 1 (global TQ / TQ_MAX = global TQ value). + +== Protocol Procedure == + +==== Broadcasting own Originator Message (OGM) ==== Each node periodically (OGM interval) generates and broadcasts a single OGM on each interface B.A.T.M.A.N. is running on if at least one HNA is present. A jitter may be applied to avoid collisions. -+The Originator Message (OGM) Format:+ +__The Originator Message (OGM) Format:__ -* Packet type: Initialize this field with the OGM packet type. -* Version: Set your internal compatibility version. -* flags: Indicates certain attributes of this originator. So far 0x01 is reserved for VIS_SERVER (see [[VisAdv]]) -* global TQ: Is initially set to TQ_MAX by the originator. -* Sequence number: On first broadcast set the sequence number to an arbitrary value and increment the field by one for each following broadcast. -* Originator Address: Set this field to the primary MAC address of this B.A.T.M.A.N. node. -* Previous Sender: Indicates the originator address of the sender that routed the OGM to our sender. Initially, the originator of the OGM sets it to its originator address. -* Number of HNAs: The number of hosts that are announced with this message. + * Packet type: Initialize this field with the OGM packet type. + * Version: Set your internal compatibility version. + * flags: Indicates certain attributes of this originator. So far 0x01 is reserved for VIS_SERVER (see [wiki:VisAdv]) + * global TQ: Is initially set to TQ_MAX by the originator. + * Sequence number: On first broadcast set the sequence number to an arbitrary value and increment the field by one for each following broadcast. + * Originator Address: Set this field to the primary MAC address of this B.A.T.M.A.N. node. + * Previous Sender: Indicates the originator address of the sender that routed the OGM to our sender. Initially, the originator of the OGM sets it to its originator address. + * Number of HNAs: The number of hosts that are announced with this message. -<pre> +{{{ 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ @@ -64,13 +56,13 @@ Each node periodically (OGM interval) generates and broadcasts a single OGM on e +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TTL | Num HNA | GW flags | Alignment | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -</code></pre> +}}} A B.A.T.M.A.N. originator has to advertise at least one HNA. Otherwise no OGM shall be scheduled for sending. -+The Host Network Announcement (HNA) Message Format:+ +__The Host Network Announcement (HNA) Message Format:__ -<pre> +{{{ 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ @@ -78,71 +70,59 @@ A B.A.T.M.A.N. originator has to advertise at least one HNA. Otherwise no OGM sh +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Host Network Announcement | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -</code></pre> +}}} Note: An HNA entry is not 4 Byte aligned, as two 6 Bytes entries are. - -h2. Receiving Originator Messages - +== Receiving Originator Messages == Upon receiving a general B.A.T.M.A.N. packet a Node must perform the following preliminary checks before the packet is further processed: -* If the OGM contains a version which is different to the own internal version the message must be silently dropped (thus, it must not be further processed). -* If the sender address of the OGM's ethernet frame belongs to one of the B.A.T.M.A.N. interfaces the message must be silently dropped as this OGM originated from this node. -* If the sender address of the OGM's ethernet frame is a multicast address the message must be silently dropped. -* If the previous sender address of the OGM's ethernet frame is a multicast address the message must be silently dropped. -* If the OGM's sequence number is smaller (TODO: describe somewhere what "smaller" means here) or equal to Sender's Router Sequence Number for the OGM's Originator the message must be silently dropped. (TODO: does this make the Previous Sender field obsolete?) -* If the tuple of the origantor address, the sender's originator address and sequence number of the OGM are a duplicate the message must be silently dropped. -* If an OGM with a newer sequence number of the same originator address and sender's originator address has been received before, the message must be silently dropped. + * If the OGM contains a version which is different to the own internal version the message must be silently dropped (thus, it must not be further processed). + * If the sender address of the OGM's ethernet frame belongs to one of the B.A.T.M.A.N. interfaces the message must be silently dropped as this OGM originated from this node. + * If the sender address of the OGM's ethernet frame is a multicast address the message must be silently dropped. + * If the previous sender address of the OGM's ethernet frame is a multicast address the message must be silently dropped. + * If the OGM's sequence number is smaller (TODO: describe somewhere what "smaller" means here) or equal to Sender's Router Sequence Number for the OGM's Originator the message must be silently dropped. (TODO: does this make the Previous Sender field obsolete?) + * If the tuple of the origantor address, the sender's originator address and sequence number of the OGM are a duplicate the message must be silently dropped. + * If an OGM with a newer sequence number of the same originator address and sender's originator address has been received before, the message must be silently dropped. If the OGM has not been dropped after these preliminary checks, the OGM will be modified in the following way: -* The OGM's global TQ field needs to be multiplied with the best link TQ value towards the sender. -* This new OGM's global TQ field needs to be multiplied with the asymmetric penalty of the link with the best link TQ value towards the sender. See 'TODO' for the asymmetric penalty. -* The Neighbor Ranking needs to be performed. - - -h2. Router Ranking + * The OGM's global TQ field needs to be multiplied with the best link TQ value towards the sender. + * This new OGM's global TQ field needs to be multiplied with the asymmetric penalty of the link with the best link TQ value towards the sender. See 'TODO' for the asymmetric penalty. + * The Neighbor Ranking needs to be performed. +== Router Ranking == When a new neighbor ranking needs to be performed for an OGM the following steps need to be undertaken: -* If the OGM's Sequence Number is newer than the Originator's Sequence Number: -*** The new Originator's Sequence Number must be set to the Sequence Number contained in the received OGM. -*** for all Routers of the OGM's originator: if (Originator's Sequence Number - Router's Sequence Number) < OGM_SEQ_DIFF_LIMIT, purge the Neighbor Originator from the OGM's originator's Router List. (TODO: check whether this could introduce routing loops? Any additional checks for purging needed?) -* If a matching Router entry for the OGM's Sender and OGM's Originator exist, the global TQ value and Router Sequence Number in this Router entry need to be updated with the OGM's global TQ value and OGM's Sequence Number. Otherwise a Router entry with these values needs to be created. -* If the OGM's global TQ value is the best of all other Router's global TQ values, the OGM needs to be re-broadcasted. + * If the OGM's Sequence Number is newer than the Originator's Sequence Number: + * The new Originator's Sequence Number must be set to the Sequence Number contained in the received OGM. + * for all Routers of the OGM's originator: if (Originator's Sequence Number - Router's Sequence Number) < OGM_SEQ_DIFF_LIMIT, purge the Neighbor Originator from the OGM's originator's Router List. (TODO: check whether this could introduce routing loops? Any additional checks for purging needed?) + * If a matching Router entry for the OGM's Sender and OGM's Originator exist, the global TQ value and Router Sequence Number in this Router entry need to be updated with the OGM's global TQ value and OGM's Sequence Number. Otherwise a Router entry with these values needs to be created. + * If the OGM's global TQ value is the best of all other Router's global TQ values, the OGM needs to be re-broadcasted. TODO: Add a picture of the automata? (If that's not easily doable, simplify the Neighbor Ranking section, and out-source certain things to Pre/Post-Checks that do not modify the Originator List) - -h2. Re-broadcasting other nodes' OGMs - +== Re-broadcasting other nodes' OGMs == When an OGM is to be re-broadcasted some of the message fields must be changed others must be left unchanged. All fields not mentioned in the following section remain untouched: -* The TTL must be decremented by one. If the TTL becomes zero (after the decrementation) the packet must be dropped. -* The OGMs global TQ field needs to be multiplied with the hop penalty. See 'TODO' for the hop penalty. -* - - -h2. Originator List - -* Originator: -* Originator's Sequence Number: The newest OGM Sequence Number that has been accepted from the given Originator. This is described in 'TODO' -* Router List: A list of possible routers towards an originator - - -h3. Router List - -* Originator: -* global TQ value: The global TQ value towards the -* Router's Sequence Number: + * The TTL must be decremented by one. If the TTL becomes zero (after the decrementation) the packet must be dropped. + * The OGMs global TQ field needs to be multiplied with the hop penalty. See 'TODO' for the hop penalty. + * +== Originator List == + * Originator: + * Originator's Sequence Number: The newest OGM Sequence Number that has been accepted from the given Originator. This is described in 'TODO' + * Router List: A list of possible routers towards an originator -h2. Proposed Values for Constants +=== Router List === + * Originator: + * global TQ value: The global TQ value towards the + * Router's Sequence Number: +== Proposed Values for Constants == OGM_SEQ_DIFF_LIMIT: 5

1 0

[doc] backup-redmine/2017-07-13, master: doc: open-mesh/Gsoc2011-ideas: adding some more descriptions (a1e53ff3)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

Repository : ssh://git@open-mesh.org/doc On branches: backup-redmine/2017-07-13,master >--------------------------------------------------------------- commit a1e53ff37444998dcd8b4ec85e1af49b770dd6d4 Author: Linus Lüssing <linus.luessing(a)c0d3.blue> Date: Mon Feb 28 01:12:03 2011 +0000 doc: open-mesh/Gsoc2011-ideas: adding some more descriptions >--------------------------------------------------------------- a1e53ff37444998dcd8b4ec85e1af49b770dd6d4 open-mesh/Gsoc2011-ideas.textile | 143 +++++++++++++++++++++++++-------------- 1 file changed, 92 insertions(+), 51 deletions(-) diff --git a/open-mesh/Gsoc2011-ideas.textile b/open-mesh/Gsoc2011-ideas.textile index da0fadee..ec2a2073 100644 --- a/open-mesh/Gsoc2011-ideas.textile +++ b/open-mesh/Gsoc2011-ideas.textile @@ -1,66 +1,104 @@ -= Google Summer of Code 2011 - Ideas = -== batman-adv == -=== Categories + Usecases to improve === - * Increasing Robustness - * Improving Mobility / Convergence Speed - * Improving Indoor performance - * Improving VoIP group multicast performance - * Improving nomadic scenarios (circular + chain topology) +h1. Google Summer of Code 2011 - Ideas -=== Specific Tasks === -==== Dynamic OGM+NDP intervals ==== -'''Brief description:''' A batman-adv node shall select originator interval rates according to the dense and dynamics in its closer environment. + + +h2. batman-adv == + Categories + Usecases to improve === +* Increasing Robustness +* Improving Mobility / Convergence Speed +* Improving Indoor performance +* Improving [[VoIP]] group multicast performance +* Improving nomadic scenarios (circular + chain topology) + + +h3. Specific Tasks === + Dynamic OGM+NDP intervals ==== +*Brief description:* A batman-adv node shall select originator interval rates according to the dense and dynamics in its closer environment. Depending on the usage scenario, people can adjust the bandwidth being used for batman-adv's route finding algorithms. Usually people were advised to increase the originator interval if the mesh network is small but needs fast route refresh rates or to decrease it if the mesh network is mostly a static setup with a lot of nodes. It would be great if a batman-adv node could determine the dynamics of the mesh network it is currently participating in on its own so that this option would not have to be administrated from a person anymore. For instance in combination with the 'B.A.T.M.A.N. protocol overhead reduction' project, the local broadcasts could be automatically increased if there are not that many direct neighbors. -==== OGM/NDP Hidden Node Problem Avoidance ==== -'''Brief description:''' Implement a suitable solution against hidden node broadcast packet problem. + +h4. OGM/NDP Hidden Node Problem Avoidance + +*Brief description:* Implement a suitable solution against hidden node broadcast packet problem. Especially in indoor scenarios where corners and thick walls are involved, hidden nodes can be a severe problem. Usually activating RTS/CTS is a common way of solving this problem at least to some degree. However, RTS/CTS can only be applied for unicast packets. Therefore a node sending a lot of data packets to another one, even with RTS/CTS those packets will interfere with BATMAN's broadcast packets (e.g. NDP packets or OGMs). The effect is, that the transmit quality of a node sending NDP packets which does not see the data packet transmission will greatly decrease. -A suitable solution shall be implemented. This might be based on time slots, multiple interfaces or channel switching and might be implemented within batman-adv or an extra module. See [http://www.open-mesh.org/wiki/bcast-hidden-node here] for a more detailed description of the problem and a solution proposal. +A suitable solution shall be implemented. This might be based on time slots, multiple interfaces or channel switching and might be implemented within batman-adv or an extra module. See "here":http://www.open-mesh.org/wiki/bcast-hidden-node for a more detailed description of the problem and a solution proposal. + + +h4. OGM/NDP Congestion Avoidance + +*Brief description:* Implement a congestion avoidance mechanism for batman-adv's routing control packets against congestion caused by high data transfer rates. + +In case of a mesh network congested due to e.g. a lot of UDP packets, the packet loss rate of batman's OGMs or NDP packets increases severely, as neither OGMs/NDP nor UDP have a congestion control mechanism. For one thing, lost OGMs lead to a high degradation of batman's convergence speed. For another, lost NDP packets lead to route flipping; in the worst case some of these chosen routes are not usable. batman-adv has the advantage of being able to control the whole packet, both data and control packets, within the mesh network. Therefore time spaces for OGMs/NDP packets could be allocated, as already described in "OGM/NDP Hidden Node Problem Avoidance" / "Or prioritized queues could be introduced. -==== OGM/NDP Congestion Avoidance ==== -'''Brief description:''' Implement a congestion avoidance mechanism for batman-adv's routing control packets against congestion caused by high data transfer rates. -In case of a mesh network congested due to e.g. a lot of UDP packets, the packet loss rate of batman's OGMs or NDP packets increases severely, as neither OGMs/NDP nor UDP have a congestion control mechanism. For one thing, lost OGMs lead to a high degradation of batman's convergence speed. For another, lost NDP packets lead to route flipping; in the worst case some of these chosen routes are not usable. batman-adv has the advantage of being able to control the whole packet, both data and control packets, within the mesh network. Therefore time spaces for OGMs/NDP packets could be allocated, as already described in "OGM/NDP Hidden Node Problem Avoidance" / [http://www.open-mesh.org/wiki/bcast-hidden-node]. Or prioritized queues could be introduced. +h4. B.A.T.M.A.N. Routing Framework -==== B.A.T.M.A.N. Routing Framework ==== -'''Brief description:''' Separate B.A.T.M.A.N. routing algorithm from routing infrastructure in batman-adv. +*Brief description:* Separate B.A.T.M.A.N. routing algorithm from routing infrastructure in batman-adv. Many features in batman-adv are routing algorithm independent: Link layer routing, link layer fragmentation, multicast optimizations, NDP, interface bonding. To allow other routing algorithms to use this already well tested infrastructure, the B.A.T.M.A.N. routing algorithm shall be separated more clearly from the routing infrastructure. Ultimately, other routing protocols shall be able to control the kernel space mesh routing infrastructure from userspace. -==== Improve Throughput Bonding ==== -'''Brief description:''' Improve performance gain of the throughput bonding mode. + +h4. Improve Throughput Bonding + +*Brief description:* Improve performance gain of the throughput bonding mode. The current bonding mode implementation simply sends a data packet in a round robin fashion to the interfaces available for bonding. However, the throughput gain seems to be only about 66%25 instead of doubling the throughput in case of TCP, even if there is no other interference involved. This seems to be the case due to a heavy reordering issue. Furthermore, the interface with the lowest capacity is a bottleneck for the throughput bonding performance: In case of one interface of 1MBit/s throughput and five more with 2MBit/s throughput, the actual throughput will be just 6x 1MBit/s. However in mixed wireless and wired networks, it might be desirable to accumulate the throughput of a Gigabit-Ethernet interface and a 802.11g interface. Therefore checks for links' capacities (detect full queues etc.) to gain performance of IF1 + IF2 + ... instead of min(IF1, IF2, ...) shall be implemented. If an interface is busy, it shall be skipped in this round robin cycle. Furthermore simple per hop pre-ordering on batman-adv's layer shall be implemented to increase the TCP performance. -==== Unit Test Infrastructure ==== -'''Brief description:''' Create a flexible unit test infrastructure to increase batman-adv's stability. + +h4. Unit Test Infrastructure + +*Brief description:* Create a flexible unit test infrastructure to increase batman-adv's stability. As batman-adv resides in the Linux kernel any crash in batman-adv has severe consequences for the whole system. For instance a deadlock or aceesing invalid memory in batman-adv will freeze the whole system. Typically most embedded routers have a watchdog to restart the device automatically in such situations. However in critical usage scenarios, a reboot of the device might not be tolerable. Therefore a unit test infrastructure shall be created which for one thing tests and verifies single functions and functionalities within the batman-adv code base. And for another it shall stress test the complete software for different virtualized, static and dynamic topologies. -==== IPv6 Stateless Autoconf Gateway Solution ==== -'''Brief description:''' Implement a gateway solution for IPv6 stateless autoconfiguration -batman-adv operates on layer 2, therefore intelligent layer 3 gateway handling is not straightforward. batman-adv currently supports intelligent gateway handling for DHCP (both IPv4 and IPv6), in that it forwards any DHCP discovery or request packet to the best (according to batman's metric) gateway available only, via unicast. However, this is not doable for IPv6 stateless autoconfiguration, as usually not the client is not actively requesting an IP address, but the router is advertising it's gateway capabilities periodically. However, such a stateless configuration is usually more desirable than a stateful configuration as in DHCP in dynamic mesh networks as it allows smoother transitions between subnets and is not as prone to packet loss. Therefore a solution for IPv6 Stateless autoconfiguration shall be implemented. This may be done by exploiting the router preference fields in the router advertisement messages, [http://tools.ietf.org/html/rfc4191 RFC4191], and/or by limiting the range of router advertisements with the help of batman-adv's broadcast packet's TTL field or by introducing a new TQ limit field. A TQ limit field could be dynamically adapted to minimze the overhead of such router advertisements in case of many gateways but ensuring the availability of the best/closest of all gateways in the mesh network. +h4. IPv6 Stateless Autoconf Gateway Solution + +*Brief description:* Implement a gateway solution for IPv6 stateless autoconfiguration + +batman-adv operates on layer 2, therefore intelligent layer 3 gateway handling is not straightforward. batman-adv currently supports intelligent gateway handling for DHCP (both IPv4 and IPv6), in that it forwards any DHCP discovery or request packet to the best (according to batman's metric) gateway available only, via unicast. However, this is not doable for IPv6 stateless autoconfiguration, as usually not the client is not actively requesting an IP address, but the router is advertising it's gateway capabilities periodically. However, such a stateless configuration is usually more desirable than a stateful configuration as in DHCP in dynamic mesh networks as it allows smoother transitions between subnets and is not as prone to packet loss. Therefore a solution for IPv6 Stateless autoconfiguration shall be implemented. This may be done by exploiting the router preference fields in the router advertisement messages, [http://tools.ietf.org/html/rfc4191 RFC4191":http://www.open-mesh.org/wiki/bcast-hidden-node]., and/or by limiting the range of router advertisements with the help of batman-adv's broadcast packet's TTL field or by introducing a new TQ limit field. A TQ limit field could be dynamically adapted to minimze the overhead of such router advertisements in case of many gateways but ensuring the availability of the best/closest of all gateways in the mesh network. + + +h4. Improve Broadcast Data Performance + +*Brief description:* Optimize the flooding of broadcast data to reduce overhead and increase its packet delivery ratio. -==== Improve Broadcast Data Performance ==== -'''Brief description:''' Optimize the flooding of broadcast data to reduce overhead and increase its packet delivery ratio. +So far broadcast data packets are flooded through the whole mesh network. As broadcast packets do not have an ARQ mechanism to reduce packet losses like unicast data transfer has, batman-adv (re)transmits broadcast packets on each hop by default. In dense topologies this can introduce unnecessary overhead, in sparse topologies the packet delivery ratio might be too low. Therefore a smarter mechanism than classic flooding shall be implemented to improve batman-adv's performance for broadcast data packets. This may done taking link qualities in the local neighborhood into account and adjusting the number of rebroadcasts dynamically. Or by introducing "MPR":http://en.wikipedia.org/wiki/Multipoint_relay-like mechanisms. -So far broadcast data packets are flooded through the whole mesh network. As broadcast packets do not have an ARQ mechanism to reduce packet losses like unicast data transfer has, batman-adv (re)transmits broadcast packets on each hop by default. In dense topologies this can introduce unnecessary overhead, in sparse topologies the packet delivery ratio might be too low. Therefore a smarter mechanism than classic flooding shall be implemented to improve batman-adv's performance for broadcast data packets. This may done taking link qualities in the local neighborhood into account and adjusting the number of rebroadcasts dynamically. Or by introducing [http://en.wikipedia.org/wiki/Multipoint_relay MPR]-like mechanisms. -=== Further Tasks === +h4. Reduce ARP (/ND) latency and overhead - * (link layer?) FEC, ARQ module (maybe create a separate kernel module, port also the link layer fragmentation to this module so other protocols might use it?) - * Dead-node fast path switching - * Link quality / Packet delivery ratio measurement improvements +*Brief description:* Reduce ARP latency and overhead by implementing an ARP cache. + +batman-adv operates on the link layer, therefore any network protocol (e.g. IPv4/6) needs to perform an MAC address lookup for any IP address through the mesh network first. As ARP packets are broadcast packets, batman-adv simply floods them through the whole mesh network. This can create quite some overhead in large scale mesh networks or high latencies in case of mesh networks with poor links. Therefore an ARP cache shall be implemented on each node so that they could answer ARP requests directly to any host on their segment instead of flooding it through the whole mesh again. Something similiar may be implemented for IPv6's Neighbor Discovery (ND) mechanism. + + +h4. Dead node fast path switching/invalidating + +*Brief description:* Improve batman-adv to respond quicker to node/link failures and avoid packet drops in case of link failures. + +When a node notices the breakdown of a neighbor (see [[routing_scenarios#Convergencespeed|routing scenarios]] to get an idea about the conditions), this node could send any data packet, which it would usually send over this neighbor to either its second best hop if available (which does not always have to be the case due to OGM forwarding policies). Or it could send the packet back to the next hop towards the source again. With the help of sequence numbers, any node on the 'backtracking' path (the backtracking path can be different from the usual path in case of asymmetric links) could notice that a path became invalid very quickly. + + +h4. Link layer FEC/ARQ/Fragmentation module + +*Brief description:* Create a kernel module that can be added onto an interface which performs link layer optimizations (FEC, ARQ, Fragmentation, ...). + +The ARQ and FEC mechanisms provided in 802.11 for unicast data packets is mainly optimized for one hop scenarios only. While the packet delivery ratio on one hop might be fine, it might not be usable for multiple hops in a mesh network. Therefore a link-layer kernel module shall be implemented which performs Forward Error Correction and Automatic Repeat reQuest with dynamic parametrizations, to achieve a certain, configured target packet delivery ratio. Furthermore, the fragmentation from batman-adv could be moved to this link layer module, too. Such a module would then provide a virtual interface which batman-adv would use instead of the actual wifi/ethernet interfaces. + + +h3. Further Tasks + +* Link quality / Packet delivery ratio measurement improvements -> weighted/exponential moving average -> testing / performance measurements of / improving NDP, find and improve "performance bottlenecks" - * Multicast Optimization Algorithm enhancements +* Multicast Optimization Algorithm enhancements -> implement reactive tracker packet mode -> decrease latency of reactive tracker packet mode: attaching small data packets to tracker packet, if MTU fits (otherwise broadcast) in react. mode? ...? -> ultimately, make proactive tracker mode obsolete @@ -68,20 +106,23 @@ So far broadcast data packets are flooded through the whole mesh network. As bro -> don't send tracker packets if <= 1 destination or > 50%25 of all nodes are destinations -> Enhance HNA, host network announcements, improvement scheme to also support MCAs, multicast announcements -> ... - * Further HNA roaming improvements - * Network Coding? - * Packet signing: Add a signing mechanism to identify OGM's sender and drop malicious nodes - * reduce latency by ARP buffering ? - * built-in bandwidth test tool ? - -== batctl == - * Enhance live link quality monitoring: bisect -> dot-files -> graphs -> to (live) video? (+ adding horst tool information, wifi interface stats?) - * Add further info to batman-adv vis servers/clients for debugging networks - * bisect, include initial state - * live vis in map (HTML5 + Openstreetmap?) - -== misc == - * multiple interface support in Mesh 3D - * ap51flash GUI; ap51flash multi-flash on single interface - * !Android/Maemo/Meego porting + _maintenance_! - * Cooperative work with Pidgin guys? (video/audio/file-transfer/bonjour in pidgin and improving its + batman-adv's combined performance in a mesh network?) \ No newline at end of file +* Further HNA roaming improvements +* "Network Coding":http://en.wikipedia.org/wiki/Network_coding? +* Packet signing: Add a signing mechanism to identify OGM's sender and drop malicious nodes +* built-in bandwidth test tool ? + + +h2. batctl + +* Enhance live link quality monitoring: bisect -> dot-files -> graphs -> to (live) video? (+ adding horst tool information, wifi interface stats?) +* Add further info to batman-adv vis servers/clients for debugging networks +* bisect, include initial state +* live vis in map (HTML5 + Openstreetmap?) + + +h2. misc + +* multiple interface support in Mesh 3D +* ap51flash GUI; ap51flash multi-flash on single interface +* Android/Maemo/Meego porting + _maintenance_! +* Cooperative work with Pidgin guys? (video/audio/file-transfer/bonjour in pidgin and improving its + batman-adv's combined performance in a mesh network?) \ No newline at end of file

1 0

[doc] backup-redmine/2017-07-13, master: doc: batman-adv/OGM: adding some more OGM protocoll stuff (0beaeba5)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

Repository : ssh://git@open-mesh.org/doc On branches: backup-redmine/2017-07-13,master >--------------------------------------------------------------- commit 0beaeba5c4534d94b7f16eaa40ac5cc56b0c49b8 Author: Linus Lüssing <linus.luessing(a)c0d3.blue> Date: Wed Mar 2 11:35:53 2011 +0000 doc: batman-adv/OGM: adding some more OGM protocoll stuff >--------------------------------------------------------------- 0beaeba5c4534d94b7f16eaa40ac5cc56b0c49b8 batman-adv/OGM.textile | 152 +++++++++++++++++++++++++++++++++++-------------- 1 file changed, 110 insertions(+), 42 deletions(-) diff --git a/batman-adv/OGM.textile b/batman-adv/OGM.textile index e5de9665..fcb5cf41 100644 --- a/batman-adv/OGM.textile +++ b/batman-adv/OGM.textile @@ -1,47 +1,58 @@ -= Originator Message (OGM) = -{{{ -#!div style="width: 46em; text-align: justify" +h1. Originator Message (OGM) -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 [wiki:BATMANConcept B.A.T.M.A.N. concept page] and explained in details in [http://tools.ietf.org/html/draft-wunderlich-openmesh-manet-routing-00 the RFC draft] published in 2008. -With the new concept of a separate [wiki:batman-adv-ndp NDP] the tasks performed by OGMs becomes way simpler: While local work is done by NDP, information gets distributed in the mesh network with the OGM protocol, in that OGMs' primary task is to advertise path qualities, without determening link qualities. OGMs also still have the important task to distribute Host Network Annoncements, HNA for short. +<pre> +<code class="div"> + +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 [[BATMANConcept|BATMAN concept page]] and explained in details in "the RFC draft":http://tools.ietf.org/html/draft-wunderlich-openmesh-manet-routing-00 published in 2008. + +With the new concept of a separate [[batman-adv-ndp|NDP]] the tasks performed by OGMs becomes way simpler: While local work is done by NDP, information gets distributed in the mesh network with the OGM protocol, in that OGMs' primary task is to advertise path qualities, without determening link qualities. OGMs also still have the important task to distribute Host Network Annoncements, HNA for short. This bears the following advantages from the OGM point of view: - * Reduced overhead, as OGMs can then be send with a slower interval. The BATMAN routing algorithm still has a squared amount of overhead in worst case scenarios, therefore the the slower intervals are very desireable. - * The BATMAN core routing protocol becomes less entangled with other mechanisms and features, making it easier understand and to perform theoretical analysis on. - * Easier to optimize the OGMs convergence speed. - -== Definitions == - * node - A mesh router which utilizes the B.A.T.M.A.N. protocol as specified in this document on at least one network interface. A node consists of one or more originators. - * originator - An addressable entity within one mesh network routing layer. An originator's address has to be unique within a mesh network routing layer and unique on a node. A node's hard-interface may only be utilized by zero or one originator. - * B.A.T.M.A.N./hard interface - Network interface utilized by B.A.T.M.A.N. for its own ethernet frames. - * sliding window - Sequence numbers are recorded in dedicated sliding windows until they are considered out-of range. Thus, such a sliding window always contains the set of recently received sequence numbers. The amount of sequence numbers recorded in the sliding window is used as a metric for the quality of detected links and paths. - * duplicate - A received NDP message from a neighbor containing an already received sequence number. - * out of order - A received NDP message from a neighbor containing a sequence number that is older than the newest sequence number ever received from this neighbor. - * HNA - Host Network Announcement, a host's MAC address which is addressable on the mesh layer and which this originator is responsible for. This may be either the originator itself (bat0's MAC) or a bridged in host. - -== Protocol Procedure == - -==== Broadcasting own Originator Message (OGM) ==== +* Reduced overhead, as OGMs can then be send with a slower interval. The BATMAN routing algorithm still has a squared amount of overhead in worst case scenarios, therefore the the slower intervals are very desireable. +* The BATMAN core routing protocol becomes less entangled with other mechanisms and features, making it easier understand and to perform theoretical analysis on. +* Easier to optimize the OGMs convergence speed. + + +h2. Definitions + +* node - A mesh router which utilizes the B.A.T.M.A.N. protocol as specified in this document on at least one network interface. A node consists of one or more originators. +* originator - An addressable entity within one mesh network routing layer. An originator's address has to be unique within a mesh network routing layer and unique on a node. A node's hard-interface may only be utilized by zero or one originator. +* B.A.T.M.A.N./hard interface - Network interface utilized by B.A.T.M.A.N. for its own ethernet frames. +* sliding window - Sequence numbers are recorded in dedicated sliding windows until they are considered out-of range. Thus, such a sliding window always contains the set of recently received sequence numbers. The amount of sequence numbers recorded in the sliding window is used as a metric for the quality of detected links and paths. +* duplicate - A received NDP message from a neighbor containing an already received sequence number. +* out of order - A received NDP message from a neighbor containing a sequence number that is older than the newest sequence number ever received from this neighbor. +* HNA - Host Network Announcement, a host's MAC address which is addressable on the mesh layer and which this originator is responsible for. This may be either the originator itself (bat0's MAC) or a bridged in host. +* Router: +* Sender: The originator belonging to a received OGM's ethernet frame source address. +* global TQ value: The linear mapping of an OGM's global TQ field to a value between 0 and 1 (global TQ / TQ_MAX = global TQ value). + + +h2. Protocol Procedure + + + +h4. Broadcasting own Originator Message (OGM) + Each node periodically (OGM interval) generates and broadcasts a single OGM on each interface B.A.T.M.A.N. is running on if at least one HNA is present. A jitter may be applied to avoid collisions. -__The Originator Message (OGM) Format:__ ++The Originator Message (OGM) Format:+ - * Packet type: Initialize this field with the OGM packet type. - * Version: Set your internal compatibility version. - * flags: Indicates certain attributes of this originator. So far 0x01 is reserved for VIS_SERVER (see [wiki:VisAdv]) - * TQ value: Is initially set to 255 by the originator. - * Sequence number: On first broadcast set the sequence number to an arbitrary value and increment the field by one for each following broadcast. - * Originator Address: Set this field to the primary MAC address of this B.A.T.M.A.N. node. - * Previous Sender: Indicates the originator address of the sender that routed the OGM to our sender. Initially, the originator of the OGM sets it to its originator address. - * Number of HNAs: The number of hosts that are announced with this message. +* Packet type: Initialize this field with the OGM packet type. +* Version: Set your internal compatibility version. +* flags: Indicates certain attributes of this originator. So far 0x01 is reserved for VIS_SERVER (see [[VisAdv]]) +* global TQ: Is initially set to TQ_MAX by the originator. +* Sequence number: On first broadcast set the sequence number to an arbitrary value and increment the field by one for each following broadcast. +* Originator Address: Set this field to the primary MAC address of this B.A.T.M.A.N. node. +* Previous Sender: Indicates the originator address of the sender that routed the OGM to our sender. Initially, the originator of the OGM sets it to its originator address. +* Number of HNAs: The number of hosts that are announced with this message. -{{{ +<pre> 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - | Packet Type | Version | flags | TQ value | + | Packet Type | Version | flags | global TQ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ @@ -53,13 +64,13 @@ __The Originator Message (OGM) Format:__ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | TTL | Num HNA | GW flags | Alignment | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -}}} +</code></pre> A B.A.T.M.A.N. originator has to advertise at least one HNA. Otherwise no OGM shall be scheduled for sending. -__The Host Network Announcement (HNA) Message Format:__ ++The Host Network Announcement (HNA) Message Format:+ -{{{ +<pre> 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ @@ -67,17 +78,74 @@ __The Host Network Announcement (HNA) Message Format:__ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Host Network Announcement | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -}}} +</code></pre> Note: An HNA entry is not 4 Byte aligned, as two 6 Bytes entries are. -== Receiving Originator Messages == + +h2. Receiving Originator Messages + Upon receiving a general B.A.T.M.A.N. packet a Node must perform the following preliminary checks before the packet is further processed: - * If the OGM contains a version which is different to the own internal version the message must be silently dropped (thus, it must not be further processed). - * If the sender address of the OGM's ethernet frame belongs to one of the B.A.T.M.A.N. interfaces the message must be silently dropped as this OGM originated from this node. - * If the sender address of the OGM's ethernet frame is a multicast address the message must be silently dropped. - * If the previous sender address of the OGM's ethernet frame is a multicast address the message must be silently dropped. - * ... \ No newline at end of file +* If the OGM contains a version which is different to the own internal version the message must be silently dropped (thus, it must not be further processed). +* If the sender address of the OGM's ethernet frame belongs to one of the B.A.T.M.A.N. interfaces the message must be silently dropped as this OGM originated from this node. +* If the sender address of the OGM's ethernet frame is a multicast address the message must be silently dropped. +* If the previous sender address of the OGM's ethernet frame is a multicast address the message must be silently dropped. +* If the OGM's sequence number is smaller (TODO: describe somewhere what "smaller" means here) or equal to Sender's Router Sequence Number for the OGM's Originator the message must be silently dropped. (TODO: does this make the Previous Sender field obsolete?) +* If the tuple of the origantor address, the sender's originator address and sequence number of the OGM are a duplicate the message must be silently dropped. +* If an OGM with a newer sequence number of the same originator address and sender's originator address has been received before, the message must be silently dropped. + +If the OGM has not been dropped after these preliminary checks, the OGM will be modified in the following way: + +* The OGM's global TQ field needs to be multiplied with the best link TQ value towards the sender. +* This new OGM's global TQ field needs to be multiplied with the asymmetric penalty of the link with the best link TQ value towards the sender. See 'TODO' for the asymmetric penalty. +* The Neighbor Ranking needs to be performed. + + +h2. Router Ranking + +When a new neighbor ranking needs to be performed for an OGM the following steps need to be undertaken: + +* If the OGM's Sequence Number is newer than the Originator's Sequence Number: +*** The new Originator's Sequence Number must be set to the Sequence Number contained in the received OGM. +*** for all Routers of the OGM's originator: if (Originator's Sequence Number - Router's Sequence Number) < OGM_SEQ_DIFF_LIMIT, purge the Neighbor Originator from the OGM's originator's Router List. (TODO: check whether this could introduce routing loops? Any additional checks for purging needed?) +* If a matching Router entry for the OGM's Sender and OGM's Originator exist, the global TQ value and Router Sequence Number in this Router entry need to be updated with the OGM's global TQ value and OGM's Sequence Number. Otherwise a Router entry with these values needs to be created. +* If the OGM's global TQ value is the best of all other Router's global TQ values, the OGM needs to be re-broadcasted. + +TODO: Add a picture of the automata? (If that's not easily doable, simplify the Neighbor Ranking section, and out-source certain things to Pre/Post-Checks that do not modify the Originator List) + + +h2. Re-broadcasting other nodes' OGMs + + +When an OGM is to be re-broadcasted some of the message fields must be changed others must be left unchanged. All fields not mentioned in the following section remain untouched: + +* The TTL must be decremented by one. If the TTL becomes zero (after the decrementation) the packet must be dropped. +* The OGMs global TQ field needs to be multiplied with the hop penalty. See 'TODO' for the hop penalty. +* + + +h2. Originator List + +* Originator: +* Originator's Sequence Number: The newest OGM Sequence Number that has been accepted from the given Originator. This is described in 'TODO' +* Router List: A list of possible routers towards an originator + + +h3. Router List + +* Originator: +* global TQ value: The global TQ value towards the +* Router's Sequence Number: + + +h2. Proposed Values for Constants + + +OGM_SEQ_DIFF_LIMIT: 5 + +TQ_MAX: 255 + +

1 0

[doc] backup-redmine/2017-07-13, master: doc: open-mesh/WikiStart (2edebe15)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

Repository : ssh://git@open-mesh.org/doc On branches: backup-redmine/2017-07-13,master >--------------------------------------------------------------- commit 2edebe15c53ce931bf027a5da98373524733e4cc Author: Marek Lindner <mareklindner(a)neomailbox.ch> Date: Thu Feb 24 16:45:27 2011 +0000 doc: open-mesh/WikiStart >--------------------------------------------------------------- 2edebe15c53ce931bf027a5da98373524733e4cc open-mesh/WikiStart.textile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/open-mesh/WikiStart.textile b/open-mesh/WikiStart.textile index cf7c866b..b23f21ee 100644 --- a/open-mesh/WikiStart.textile +++ b/open-mesh/WikiStart.textile @@ -19,7 +19,7 @@ B.A.T.M.A.N. (better approach to mobile ad-hoc networking) is a routing protocol * [wiki:BranchesExplained Branches explained] - learn about the B.A.T.M.A.N. flavours * [wiki:UserDocs UserDocs] - understand how B.A.T.M.A.N. works * [wiki:FAQ FAQ] - Frequently Asked Questions - * [wiki:Experience Experience] - Collection of links to B.A.T.M.A.N. papers / projects using B.A.T.M.A.N. + * [wiki:Experience Experience] - Collection of links to B.A.T.M.A.N. press reviews, papers and projects using B.A.T.M.A.N. * [wiki:Patches Patches] - contribution from others related to B.A.T.M.A.N. * [wiki:batman-adv B.A.T.M.A.N. Advanced] - information about the Layer 2 version of B.A.T.M.A.N. * [wiki:MailingList Mailing List]/[wiki:IRC IRC] - contact us

1 0

[doc] backup-redmine/2017-07-13, master: doc: open-mesh/Experience (eaa1e175)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

Repository : ssh://git@open-mesh.org/doc On branches: backup-redmine/2017-07-13,master >--------------------------------------------------------------- commit eaa1e1755979c9b45e5a335f3911e97fd4478d68 Author: Marek Lindner <mareklindner(a)neomailbox.ch> Date: Thu Feb 24 16:42:58 2011 +0000 doc: open-mesh/Experience >--------------------------------------------------------------- eaa1e1755979c9b45e5a335f3911e97fd4478d68 open-mesh/Experience.textile | 1 + 1 file changed, 1 insertion(+) diff --git a/open-mesh/Experience.textile b/open-mesh/Experience.textile index e045c101..8e48d3a0 100644 --- a/open-mesh/Experience.textile +++ b/open-mesh/Experience.textile @@ -10,6 +10,7 @@ __Projects:__ * building mesh potatoes with B.A.T.M.A.N.: http://villagetelco.org * powerful mesh nodes with batman-adv inside: http://www.saxnet.de * B.A.T.M.A.N. with dashboard integration: http://www.open-mesh.com + * The Batphone (VOIP + Mesh on your device): http://www.servalproject.org __Press:__ * [http://www.heise.de/open/artikel/Kernel-Log-Was-2-6-38-bringt-3-Netzwerk-11… Kernel-Log: Netzwerk-Treiber und -Infrastruktur], Heise (February 2011)

1 0

[doc] backup-redmine/2017-07-13, master: doc: batman-adv/ELP: adding changes from discussions (2e37ec74)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

1 0

[doc] backup-redmine/2017-07-13, master: doc: open-mesh/Wbmv4-batmandev-agenda (1c62ca7e)
by postmaster＠open-mesh.org 14 Jul '17

14 Jul '17

Repository : ssh://git@open-mesh.org/doc On branches: backup-redmine/2017-07-13,master >--------------------------------------------------------------- commit 1c62ca7e64f8bea83828ad965655ded8ea09246a Author: Marek Lindner <mareklindner(a)neomailbox.ch> Date: Sun Feb 27 03:04:20 2011 +0000 doc: open-mesh/Wbmv4-batmandev-agenda >--------------------------------------------------------------- 1c62ca7e64f8bea83828ad965655ded8ea09246a open-mesh/Wbmv4-batmandev-agenda.textile | 1 + 1 file changed, 1 insertion(+) diff --git a/open-mesh/Wbmv4-batmandev-agenda.textile b/open-mesh/Wbmv4-batmandev-agenda.textile index dc6ca0ec..bd6f156a 100644 --- a/open-mesh/Wbmv4-batmandev-agenda.textile +++ b/open-mesh/Wbmv4-batmandev-agenda.textile @@ -9,6 +9,7 @@ Celebrate batman-adv 2.6.38 Linux kernel integration * Explicit BATMAN header + unified TTL handling? * Making fragmentation more generic, adding Fragmentation header/layer? * Reviewing OGM protocol specification proposal + * reviewing the new papers related to B.A.T.M.A.N. (Simon brings printed versions) == Testing == * NDP

1 0

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

commits July 2017