Repository : ssh://git@open-mesh.org/doc
On branches: backup-redmine/2017-07-13,master
commit 3f7fbfd5a63f3cb312cd926878a9578f28ca1d2d Author: Linus Lüssing linus.luessing@c0d3.blue Date: Sat Jun 25 06:22:22 2011 +0000
doc: batman-adv/ELP
3f7fbfd5a63f3cb312cd926878a9578f28ca1d2d batman-adv/ELP.textile | 61 +++++++++++++++++++++++++++++++++++++------------- 1 file changed, 46 insertions(+), 15 deletions(-)
diff --git a/batman-adv/ELP.textile b/batman-adv/ELP.textile index 0778db24..e90b66e8 100644 --- a/batman-adv/ELP.textile +++ b/batman-adv/ELP.textile @@ -9,30 +9,48 @@ This approach was chosen for its simplicity during the protocol design phase and 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 determening the overall path transmit qualities.
-h2. Definitions +h2. 1. 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. * 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. +* Neighbor: An ELP sender within one hop distance (note, this is defined differently for the OGM protocol)
+h2. 2. Conceptual Data Structures
-h2. Protocol Procedure +h3. 2.1. Neighbor List
+* Neighbor Address: The ethernet source address of the received ELP message. +* Originator Address: The originator address of the node. +* Packet Count Window: +* Sequence Number: +* Last Seen: +* Last Updated: +* Link RQ: +* Link TQ:
-h3. Broadcasting own Echo Location Protocol (ELP) Messages +h3. 2.2. Originator List + +* Originator Address: The originator address of the node. +* Best Link TQ + +h2. 3. Protocol Procedure + + +h3. 3.1 Broadcasting own Echo Location Protocol (ELP) Messages
Each node periodically (ELP interval) generates and broadcasts ELP messages for each interface B.A.T.M.A.N. is running on. A jitter may be applied to avoid collisions.
-h4. The Echo Location Protocol (ELP) Format: ++The Echo Location Protocol (ELP) Format:+
* Packet type: Initialize this field with the ELP packet type. * Version: Set your internal compatibility version. * Originator Address: Set this field to the primary MAC address of this B.A.T.M.A.N. node. * Sequence number: On first broadcast set the sequence number to an arbitrary value and increment the field by one for each following broadcast. -* Interval: Set to the current ELP interval of this interface. +* Interval: Set to the current ELP interval of this interface in milli seconds. * Num Neigh: The number of neighbors that are announced with this message.
If this B.A.T.M.A.N. interface wants to announce neighboring nodes it should append a neighbor entry message for each neighbor to be announced and fill the "number of neighbors" field accordingly. @@ -53,7 +71,7 @@ If this B.A.T.M.A.N. interface wants to announce neighboring nodes it should app +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ </code></pre>
-h4. The Neighbor Entry Format: ++The Neighbor Entry Format:+
* Neighbor Address: This field contains the MAC address of the neighbor to be announced. * Link RQ: Fill this field with the total of the received sequence numbers (in percent) within the sliding sequence number window, including the time-based adjustment, from this neighbor. If that value would be 0, skip attaching that entry. @@ -70,11 +88,11 @@ Note: See 'Neighbor Ranking' and 'Time-based Window Adjustment' to get a detaile +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ </code></pre>
-h4. ELP minimum packet size / padding +h4. 3.3.1. ELP minimum packet size / padding
An ELP packet should be padded to at least 300 Bytes (excluding ethernet frame header) and may be padded to up to 1500 Bytes. Especially on wireless interfaces the packet size of broadcast packets can have quite an impact on the probability of arrival.
-h3. Receiving Echo Location Messages (ELP) +h3. 3.2. Receiving Echo Location Messages (ELP)
Upon receiving an ELP packet a node must perform the following preliminary checks before the packet is further processed: @@ -85,28 +103,28 @@ Upon receiving an ELP packet a node must perform the following preliminary check * If the originator address of the ELP message is our own the message must be silently dropped as this ELP message originated from this node. * If the ELP message does not contain a newer sequence number (duplicate, out-of-order or out-of-range) the message must be silently dropped.
-h4. Duplicate +h4. 3.2.1. Duplicate
An ELP packet is considered a duplicate if: * The last received sequence number is smaller than or equal to the current window sequence number. * The last received sequence number is greater than the current window sequence number minus WINDOW_SIZE. * The received sequence number is equal to the last received sequence number.
-h4. Out-of-Order +h4. 3.2.2. Out-of-Order
An ELP packet is considered out-of-order if: * The last received sequence number is smaller than or equal to the current window sequence number. * The last received sequence number is greater than the current window sequence number minus WINDOW_SIZE. * The received sequence number is smaller than the last received sequence number.
-h4. Out-of-Range +h4. 3.2.3. Out-of-Range
An ELP packet is considered out-of-range if: * The received sequence number is not a duplicate and not out-of-order. * The received sequence number is smaller than the current window sequence number. * The received sequence number is greater than the current window sequence number minus 2^31.
-h3. Neighbor Ranking +h3. 3.3. Neighbor Ranking
For each ELP message having passed the preliminary checks the following actions must be performed: @@ -121,9 +139,22 @@ For each ELP message having passed the preliminary checks the following actions * The sequence number of the received ELP message must be added to the sliding window. * The new resulting link RQ value is calculated by counting all sequence numbers that are to be found in the recently adjusted sliding window. * The neighbor entries must be parsed until an entry matching the MAC address of the incoming hard-interface has been found. If a match is found then save the received link RQ value as link TQ value towards this neighbor interface and skip the further traversal of the list. If no matching entry was found, set the link TQ value towards that neighbor to 0. +* The best link TQ needs to be updated. + +h4. 3.3.1. Best Link TQ + +The best link TQ is being determined in the following way: + +best link TQ = max{for all neighbors belonging to the originator: link TQ * asym_penalty(link RQ)} + +h5. 3.3.1.1 Asymmetric Link Penalty + +The asymmetric penalty is being determined in the following way: + +asym_penalty = 1 - (1 - link RQ)^3
-h3. Time-based Window Adjustment +h3. 3.4. Time-based Window Adjustment
At least once per second all ELP windows must be shifted to the expected current sequence number. This needs to be done to avoid that the OGM protocol picks up too high link quality values from ELP which do very likely not represent the current link quality anymore.
@@ -138,11 +169,11 @@ If so, the following actions must be performed: * The sliding window of the ELP message must be shifted (purged) to reflect the new upper and lower boundaries of the ranking range. * The new resulting link RQ value is calculated by counting all sequence numbers that are to be found in the recently adjusted sliding window.
-h3. Neighbor Interface Purging Recommendations +h3. 3.5. Neighbor Interface Purging Recommendations
A node may purge a neighbor interface from its neighbor list when its RQ value reaches 0. However a node with RQ 0 may be kept in the list as long as desired, as it does not make a difference for the routing decisions because of the asymmetric link penalty (see [ogm|OGM protocol] for details).
-h2. Proposed Values for Constants +h2. 4. Proposed Values for Constants
* _WINDOW_SIZE_: 2^32