Project

General

Profile

This page is OUTDATED!

This page was superseded with an update for the feature, documentered here

Multi-link Optimizations (technical documentation)

Mesh nodes with multiple physical links to other mesh nodes can use this capability to gain various benefits, for example:

  • bonding: use multiple links for the same data stream to boost bandwidth
  • interface alternating: send on other interfaces (and therefore other channels, if configured correctly) to minimize multi-hop bandwidth degradation

These features operate under the following premises:

  • multiple links exist between two neighbors
  • the routing decision is independent of the link a packet is received on

Notably, these multi-interface features are independent of B.A.T.M.A.N. and could work with any routing algorithm/metric. The routing software only needs to detect that multiple peers belong to the same neighbor mesh node. This is also not related to Multi-Path Routing, which would require multiple independent links.

The multi-link optimization procedure can be broken into these steps:

  1. detect that a neighbor is reachable via multiple links
  2. select suitable candidates among the the available links
  3. use these multiple links for various manipulations

Link detection

The detection part is specific to batman-adv. To understand how the link detection works it is necessary to recall how batman-adv handles multiple interfaces:

The MAC address (Originator address) of the primary interface (usually the first added interface) is known throughout the mesh as OGMs containing the MAC address are broadcasted on all available interfaces with a big TTL. This ensures mesh nodes only reachable via secondary interfaces will know about this node. All remaining interfaces are "secondary" interfaces which are only known in the single hop neighborhood. The OGMs containing their MAC addresses are broadcasted with a small TTL on the respective interface only. These secondary OGMs uniquely serve the purpose of detecting local neighbors and estimate the link quality towards them.

Note: It does not matter which interface is the primary interface, it is only used to have a single Originator known in the mesh, thus avoiding OGM overhead.

To detect whether or not a neighbor has multiple links towards a node it suffices to analyze the incoming primary OGM. If the primary OGM is received via multiple interfaces a node can (almost) safely assume having multiple links towards its Originator. However, the OGM protocol demands to forward all incoming OGMs for the path detection which could confuse the multi-link detection because it has to distinguish single hop neighbors from neighbors that are further away. To resolve the issue the PRIMARIES_FIRST_HOP flag was introduced. Only primary OGMs are allowed to carry it and every node removes the flag before rebroadcasting the OGM.

In the illustration, A receives the OGM via A1 (sent out by B1) and A2 (sent out by B2) - and detects that these two Links A1-B1, A2-B2 exist. These link candidates are stored and further filtered

Candidate selection

To be usable for the target features, the links must have a similar quality and should operate on a different frequency. Therefore, in batman-adv only links are further considered if:

  • the link quality is not much worse than the best link within a certain TQ threshold (now: 50)
  • the link destination is different from the other already selected candidates - e.g. if A1-B1 was selected, A2-B1 would be forbidden as they would operate on the same frequency and therefore would interfere with each other

In the illustration below, A1-B1 and A2-B2 meet this criteria and are therefore selected as candidates.

Implementation note: Detected links are internally stored within the originator structure of the primary originator. The candidates are internally called "bonding candidates"

Using the candidates

Once a neighbor mesh node has been selected by the classic routing algorithm, the individual links can now be equally be selected to send data to the next neighbor without tampering with routing. Possible mechanisms exploiting this fact are described below.

More Info can be found in the Multi-Link Optimization feature description page.

Implementation note: the manipulations are hooked in the tx path when selecting a neighbor in find_router()

Interface Alternating

Interface Alternating basically tries to forward a packet on another interface than on which the frame was received. This is only done if suitable candidate with another source interface exists.

This feature is always enabled.

Bonding

In bonding, we split a single stream and distribute the packets over multiple links. Packets are sent in a round-robin fashion over the available candidates. This can be used to increase the throughput for data streams from node A to node B. In a perfect environment the throughput is n times higher, where n is the number of candidates.

Practice shows however that the theoretical bandwidth gain is not reached - even if the links are physically disjoint. E.g. using a 2.4 GHz and a 5 GHz with a modulation of 54 Mbit/s both has shown to gain 150% bandwith boost over a single link, not 200% as expected in theory. Possible reasons may be the packet reordering and slightly different queue load caused by random backoffs, retries, etc. For these reasons, bonding must be enabled explicitly.

Discussion and further work

As explained, the bonding mode stays behind the theoretical expectations. The packet loss based TQ metric is also not optimal for selecting bonding candidates - a bandwidth based metric would be more suitable for this task, as slow links will slow down the whole aggregated connection.

These shortcomings would be subject to further improvements of this featureset.

alternation_chain.dia.jpg View (19.6 KB) Simon Wunderlich, 06/04/2010 05:03 PM

bonding_roundrobin.dia.jpg View (15.7 KB) Simon Wunderlich, 06/04/2010 05:04 PM

interface_detection.dia.jpg View (22 KB) Simon Wunderlich, 06/04/2010 05:04 PM

alternation_chain.dia (1.78 KB) Simon Wunderlich, 05/22/2011 12:17 PM

bonding_roundrobin.dia (1.76 KB) Simon Wunderlich, 05/22/2011 12:17 PM

interface_detection.dia (1.68 KB) Simon Wunderlich, 05/22/2011 12:17 PM

primary_flag.dia (1.51 KB) Simon Wunderlich, 04/10/2012 10:03 PM

primary_flag.png View (15.6 KB) Simon Wunderlich, 04/10/2012 10:03 PM