Repository : ssh://git@open-mesh.org/doc
On branches: backup-redmine/2017-07-13,master
commit 2d92f3d2c526a6afc968dff1b43b90f60420c0a8 Author: Linus Lüssing linus.luessing@c0d3.blue Date: Thu May 5 07:45:03 2011 +0000
doc: batman-adv/ELP
2d92f3d2c526a6afc968dff1b43b90f60420c0a8 batman-adv/ELP.textile | 180 +++++++++++++------------------------------------ 1 file changed, 48 insertions(+), 132 deletions(-)
diff --git a/batman-adv/ELP.textile b/batman-adv/ELP.textile index 09a43bcb..bb86bdc7 100644 --- a/batman-adv/ELP.textile +++ b/batman-adv/ELP.textile @@ -14,7 +14,7 @@ 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. +* 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. @@ -35,6 +35,7 @@ h4. The Neighborhood Discovery Protocol (NDP) Format: * 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 NDP interval of this interface. * 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. @@ -49,6 +50,8 @@ If this B.A.T.M.A.N. interface wants to announce neighboring nodes it should app +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Interval | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Num Neigh | Alignment | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ </code></pre> @@ -56,7 +59,7 @@ If this B.A.T.M.A.N. interface wants to announce neighboring nodes it should app h4. 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 that entry. +* 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.
Note: See 'Neighbor Ranking' and 'Time-based Window Adjustment' to get a detailed description of how to count/obtain the RQ value. Neighbors with an RQ value of 0 are not to be appended.
@@ -70,160 +73,73 @@ Note: See 'Neighbor Ranking' and 'Time-based Window Adjustment' to get a detaile +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ </code></pre>
+h4. NDP minimum packet size / padding + +An NDP 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 Neighborhood Discovery Messages (NDP)
-Upon receiving a NDP packet a node must perform the following preliminary checks before the packet is further processed: +Upon receiving an NDP packet a node must perform the following preliminary checks before the packet is further processed:
* If the NDP 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 originator address of the NDP message is our own the message must be silently dropped as this NDP message originated from this node. * If the sender address of the NDP message is an ethernet multicast (including broadcast) address the message must be silently dropped. -* If the NDP message is a duplicate or does not contain a newer sequence number (out-of-order) the message must be silently dropped. - - -h3. Neighbor Ranking - - -For each NDP message having passed the preliminary checks the following actions must be performed: - -* The sliding window to the sender of the NDP message must be updated (purged) to reflect the new upper and lower boundaries of the ranking range. The sequence number of the received NDP message must be added to the sliding window representing the link between the interfaces via which the NDP message has been send and received. -* 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 new current sequence number must be set to the sequence number contained in the received NDP message. -* 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 towards that neighbor as link TQ value and skip the further traversal of the list. If no matching entry was found, set the link TQ value towards that neighbor to 0. - - -h3. Time-based Window Adjustment - - -h3. Neighbor Node Purging Recommendations - -A node may be purged due .... - -h3. Questions - - -* checks whether the NDP packet is too old? (TODO: Simon, add/describe the protected window mechanism) -* What to do if RQ reaches 0 due to automatic sliding window? - - -h2. Extensions - -h3. Threshholds - -h3. EWMA - -h3. Weighted Window - -h3. Auto RQ window sliding - -h3. Fixed minimum NDP packet size? - -h3. Sometimes maximum packet size packets? - - - - ----- - - - -h2. examples of NDP advantages - -* Modularization of the code -* The delta changes between two OGMs can be increased with an NDP interval faster than the OGM interval, resulting in a higher influence of a single OGM. -* Separate optimization strategies can be used for NDP and OGMs individually then. -* The more sparse the network is (number of single hop neighbors significantly smaller than the number of all nodes), the faster the NDP interval can be chosen relative to the OGM interval, resulting in major convergence speed improvements in sparse networks. -* As NDP messages are never rebroadcasted it also helps to reduce the overhead in dense networks (many single hop neighbors). -* (Mobile nodes can chose a faster OGM + NDP interval then. It directly improves their transmit path - which was not the case with the OGM LQ measurements due to the echo-quality dependency, and indirectly improves their receive path a little, due to the asymmetric penalty) -* Less overhead: With the classic LQ measurements with NDP, the overhead increases in a squared way immediately due to the OGM rebroadcast mechanism. The squared factor in NDP has a very low base however, therefore it only applies at a large amount of neighbors. This means, that when having i.e. 10 neighbors (or probably even 50), you can select a 10 (or 50x) faster NDP interval compared to the LQ measurements with the classic OGMs. -* More accuracy in case of medium/bad links: The EQ mechanism "reduces" the effective window for the EQ measurements. So when having a TQ of 50%25, the effective EQ window will be only ~32 bits large instead of the 64, leading to many more TQ/RQ fluctuations on links with a low transmit quality. +* If the NDP message does not contain a newer sequence number (duplicate, out-of-order or out-of-range) the message must be silently dropped.
-* You usually should set the originator interval to a value suiting the most mobile node on all nodes, having a homogeneous interval. This means, that even if you have a very static neighborhood with lots of nodes (so resulting to a lot of rebroadcasts, which can be the case on VPN- or ethernet interfaces used by batman-adv), you can't lower the interval for that one because very mobile nodes far away might than not be able to reach you anymore. -* A OGM should not be rebroadcasted by the same node more than once because that could falsify the link-quality calculations. However you might want to do this to speed the convergence at more distant and/or weaker links. +h4. Duplicate
+An NDP 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.
-h2. RQ calculation +h4. Out-of-Order
-In periodic intervals, customizable per interface, a ndp packet gets broadcasted on each interface. As it has been done with the normal OGMs before, the rq-value is being calculated with a sliding window and counting the number of received ndp packets, but on a per interface basis now. +An NDP 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
-h2. local TQ propagation - -Additionally, a 2-tupel of neighbor-adresses and rq-values of neighbors on a certain interface will be attached to each ndp packet of the according interface. A neighbor will then pick the rq-value which the other node determined from the received ndp packets and insert this value as its own tq-value towards that node. - - -h2. global TQ propagation - -A node receiving an OGM will reduce its global TQ field by the local TQ fitting the neighbor and interface before processing/rebroadcasting (but after validation/duplicate checks). - - -h2. Data packet forwarding - -This will still be done according to the received global TQ. - ----- - - -h2. Further optimizations - - - -h3. Consider local-TQ for a final forwarding - -It might happen, that a node rapidly moves towards the sender of a data packet. If so, a forwarding node can notice, that the local TQ value towards the final destination of the data packet is suddenly better than the global TQ via another hop. This forwarding node can then forward the packet to its final destination instead of forwarding it to the other next-hop according to the global TQ. - - -h3. Rebroadcast OGM X times instead of once - -Every node could rebroadcast an OGM i.e. 3 times instead of just once to increase the probability of an OGM reaching every node in the mesh, resulting in a much better convergence speed (getting closer to linear convergence speed) for the trade-off of control overhead (getting closer to squared). - - -h3. Unscheduled OGM rebroadcasts - - - - -h3. Adaptive ndp interval - - - -h3. Probablistic flooding - -Although this does not optimize the convergence speed, it could greatly increase the efficiency of the flooding of broadcast/mulitcast-data packets. With ndp we now also know our neighbors' TQ-values on the same interface. With this information a node A can determine the probability, that a broadcast of node B has already reached all of A's neighbors: - -P(|N| = |N^+^|) = ∏_{n ∈ N} TQ(B, iface, n) with N being the set of A's neighbors and N^+^ the set of neighbors successfully receiving the broadcast. - -A node could then either decide with a threshold, if it might not rebroadcast (rebroadcast, if P(|N| = |N^+^|) < 0.9 i.e.). Or more elegantly rebroadcast to a certain probability: 1 - P(|N| = |N^+^|) (or 1 - P(|N| = |N^+^|)^3^ for a more conservative decision i.e.). - ----- +An NDP 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 window's current sequence number. + * The received sequence number is greater than the window's current sequence number minus 2^31.
+h3. Neighbor Ranking
-h4. Looping problems +For each NDP message having passed the preliminary checks the following actions must be performed:
+* The last seen time of this neighbor interface needs to be updated. +* The last updated time of this neighbor interface needs to be updated. +* The ndp interval of this neighbor interface needs to be updated with the ndp interval set in the received NDP message. +* The last received sequence number from this neighbor needs to be set to the sequence number of the received NDP message. +* If the sequence number of the received NDP message is higher than the window's current sequence number then: + * The window's current sequence number for this neighbor needs to be set to the sequence number of the received NDP message. + * The sliding window of the NDP message must be shifted (purged) to reflect the new upper and lower boundaries of the ranking range. +* The sequence number of the received NDP 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.
-_Not an NDP issue, also present for current OGM mechanism - moved it to a different page later_
-However, there seems to be a looping problem? (or do sequence numbers or global TQ window fix this?) -In the following 4 node scenario, the parameters are as follows: -* OGM interval: 1000 -* NDP interval: ε (very fast) -Now node R moves from B to A within the first second, so he'll arrive at B before it schedules its next OGM. Also this next OGM after this first second already uses the new link qualities due to the fast NDP interval. +h3. Time-based Window Adjustment
-*t = 0:* +At least once per second all NDP 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 NDP which do very likely not represent the current link quality anymore.
-!NDP-mobile-loop-0s.png! +More precisely, for any interface of a node towards any according, stored neighbor interface check whether:
-*t = 1:* +* The last updated time plus the ndp interval of this neighbor interface is higher than the current time.
-!NDP-mobile-loop-1s.png! +If so, the following actions must be performed:
-After about 10 seconds average, there will be a loop with S sending packets to B, and B sending them back to S. This loop will last for about 3.3 seconds average. +* The last updated time of this neighbor interface needs to be set to the current time. +* The current window sequence number of this neighbor needs to be set to the expected sequence number (= current window sequence number + rounded-down( (current time - last updated time) / neighbor interface's ndp interval). +* The sliding window of the NDP 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.
-The following [[table]] will hold some more in detail information with the times and events that will change BATMAN nodes topology knowledge. It holds the following information: -* The times t in the table are the average times of arrival of an OGM at a node in seconds. -* The table shows the TQ values towards R. The first six of these rows are from a nodes perspective, the last two ones the actual, real TQ values for the chosen path. -* Time span with loops is marked with YES in the 'loops' row. +h3. Neighbor Interface Purging Recommendations
-_Result:_ In this quite typical and small-scale scenario, we already have an average time with looping packets of *3.3* seconds. +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). \ No newline at end of file