Repository : ssh://git@open-mesh.org/doc
On branches: backup-redmine/2017-07-13,master
commit ee1cda6ebcb58608ac41ccbb156f437eccacfba6 Author: Simon Wunderlich sw@simonwunderlich.de Date: Sun Aug 21 18:44:09 2011 +0000
doc: batman-adv/OGMv2
ee1cda6ebcb58608ac41ccbb156f437eccacfba6 batman-adv/{OGM.textile => OGMv2.textile} | 101 +++++++----------------------- 1 file changed, 24 insertions(+), 77 deletions(-)
diff --git a/batman-adv/OGM.textile b/batman-adv/OGMv2.textile similarity index 69% copy from batman-adv/OGM.textile copy to batman-adv/OGMv2.textile index 074eb675..e9c9ce53 100644 --- a/batman-adv/OGM.textile +++ b/batman-adv/OGMv2.textile @@ -1,6 +1,7 @@ h1. Originator Message (OGM)
??This page is work-in-progress and will state the BATMAN V algorithm later.?? +It is a rework based on the original [[OGM]] page and will supercede it after completion.
h2. 1. Introduction
@@ -11,7 +12,7 @@ With the new concept of a separate [[ELP|ELP]] the tasks performed by OGMs becom 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. 2. Definitions @@ -104,54 +105,49 @@ Upon receiving an OGM a node must perform the following checks before the packet
h4. 4.2.1. Preliminary Checks
-* 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 is an ethernet multicast (including broadcast) address the message must be silently dropped. -* If the destination address of the OGM is a unicast address the message must be silently dropped. -* If the originator address of the OGM is our own the message must be silently dropped as this OGM originated from this node. +The following checks are simple sanity checks which don't affect the routing logic:
-h4. 4.2.2. Potential Router Checks +* *Version Check:* 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). +* *Source Check:* If the sender address of the OGM is an ethernet multicast (including broadcast) address the message must be silently dropped. +* *Destination Check* If the destination address of the OGM is a unicast address the message must be silently dropped. +* *Own Message Check:* If the originator address of the OGM is our own the message must be silently dropped as this OGM originated from this node.
-The following steps check whether the Neighbor we received the OGM from is a potential Router, meaning that we could switch to this Neighbor without creating a routing loop. If this is not the case we are going to drop and ignore this OGM. Otherwise we will further call this Neighbor a potential Router or just Router and will pass on to the Router Ranking. +h4. 4.2.2. Potential Router Checks
-* If an originator entry matching the originator address of the OGM and a Selected Router exist: -** If the OGM's Sequence Number is smaller than the Selected Router's Sequence Number then the message must be silently dropped. This step is needed to ensure loop-freeness, we may only select newer or in certain circumstances equal sequence numbers. -** If for the according originator entry's router list a router entry matching the neighbor we received the OGM from exists and this entry has a sequence number higher than the one in the OGM then the message must be silently dropped. Due to the previous check this step is not needed to ensure loop-freeness. Instead it ensures that we are not "updating" a router entry (which might not be the Selected Router at the moment) with older information. +The following steps check whether the Neighbor we received the OGM from is a potential Router.
If the OGM has not been dropped after these preliminary checks, the OGM will be modified in the following way to obtain the path TQ of the received OGM: +* *Update TQ:* The OGM's TQ field needs to be multiplied with the best link TQ towards the according neighbor. This new TQ value is further referenced as path TQ.
-* The OGM's TQ field needs to be multiplied with the best link TQ towards the according neighbor. This new TQ value is further referenced as path TQ. - -A final check then needs to be applied: +After that, we check the OGM against the current data we have (currently selected router and current entry):
* If an originator entry matching the originator address of the OGM and a Selected Router exist: -** If the OGM's Sequence Number is equal to the Selected Router's Sequence Number and the OGM's path TQ is lower than the Selected Router's path TQ then the message must be silently dropped. This step is needed to ensure loop-freeness, an OGM of the same sequence number and a lower path TQ might have been rebroadcasted from us before and might have made any next hop along the selected path to have chosen us a a next hop again, possibly creating a routing loop. And actually we are just interested for the best path TQ for now anyway. -** If for the according originator entry's router list a router entry matching the neighbor we received the OGM from exists and this entry has a sequence number equal to the one in the OGM and the OGM's path TQ is lower than or equal to the router entry's path TQ then the message must be silently dropped. Due to the previous check this step is not needed to ensure loop-freeness. Instead it ensures that we are only updating a router entry with the same sequence number to a better path TQ (which might have arrived over a "longer", more delayed path). This is also needed to ensure in case of very low packet loss over best paths to get the best, true path TQ values within the OGM flood of one sequence number. +** *drop if seqno smaller:* If the OGMs Sequence Number is smaller than the Selected Router's Sequence Number then the message must be silently dropped. +** *drop if not best router:* If the OGMs Sequence Number is equal or higher than the Selected Router's Sequence Number, but the the router is not our best router, the message must be silently dropped. +** *seqno same, but TQ smaller:* If the OGM's Sequence Number is equal to the Selected Router's Sequence Number and the OGM's path TQ is lower than the Selected Router's path TQ then the message must be silently dropped. + +If the OGM has not been dropped so far, we will further call this Neighbor a potential Router or just Router and will pass on to the Router Ranking.
h3. 5. Router Ranking
-For each OGM having passed the previous checks the according neighbor is a potential, loop-free router. The Router Ranking checks whether just an according Router or even completely new Originator entry needs to be created or an already existing Router entry matching the Router we received this OGM from just updated. Or whether also the currently Selected Router needs to be switched. Furthermore step 5.2. will force relinquishing the so far Selected Router if its information became too old because of this OGM received via a Router other than the Selected Router. +The Router Ranking checks whether just an according Router or even completely new Originator entry needs to be created or an already existing Router entry matching the Router we received this OGM from just updated. Or whether also the currently Selected Router needs to be switched. Furthermore step 5.2. will force relinquishing the so far Selected Router if its information became too old because of this OGM received via a Router other than the Selected Router.
If this OGM just results in updating a Router in the Router list which is not and not going to be the currently Selected Router, then no rebroadcasting of this OGM will take place in step 5.3. for now.
-Finally, any Neighbors which are not loop-safe Routers anymore after a possibly newly Selected Router will be removed from the Router list in step 5.4. - - For the Router Ranking the following actions must be performed:
h4. 5.1. Creating or Updating Originator and Router Entries
-In this step we are updating the according entries in the Router list. Step 4.2.2 ensured that the OGM which was not dropped yet is actually containing either newer (higher sequence number) information - which is a loop-safe, possible choice because that Router or any next hop on that path did not and will not be allowed to switch back to a lower sequence number again (like the lower sequence number we would have). Or information of the same originator's OGM flooding round, the same sequence number, as the currently Selected Router but with that OGM having travelled along a better path (better due to a higher path TQ of this OGM - and note that an OGM having travelled along such a better path can never have travelled over us before, as then the path TQ would have to be worse and not better in such a case as with each hop the path TQ gets at least 1/255 worse due to the Hop Penalty, see section 7.1). The OGM with the properties just stated might also have been received from a Neighbor which we do not have a Router entry - or even an Originator entry yet which will be created in that case first. - -More precisely, the following steps need to be undertaken in the updating and creating process: +The following steps need to be undertaken in the updating and creating process:
* If no originator entry matching the originator address of the OGM exists: ** Create a new originator entry with the originator address and originator's sequence number set to ones from the OGM.
* If no router entry matching the OGM's originator and the neighbor the OGM was received from exists: -** Create a new router entry with the Router Address set to the address of the Router we received the OGM from. Buffer the complete OGM in this entry. +** Create a new router entry with the Router Address set to the address of the Router we received the OGM from. Buffer the complete OGM in this entry. (TODO: really?) ** Unset this new router entry's Rebroadcasted flag. * Otherwise: -** Delete the old buffered OGM and buffer this newly received OGM instead. +** Delete the old buffered OGM and buffer this newly received OGM instead. (TODO: really?) ** Unset the Rebroadcasted flag in this matching router entry.
h4. 5.2. Purging Outdated Router Entries @@ -166,9 +162,7 @@ More precisely we have to: ** 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_RANGE, purge the router from the OGM's originator's Router List.
-Note that neither applying this outdated Router purging harms loop-freeness as we would Select a new Router with a higher sequence number in section 5.3. and again, the Router that would be selected next or any next hop behind it would not have selected us or will not select us due to them not being allowed to switch back to a lower sequence number again. Nor is this purging of outdated Routers needed to ensure loop-freeness. It is just an optimization for certain scenarios as described previously. - -Also note, that this step can result in rebroadcasting an OGM in step 5.3. which is not the one we have actually received and are currently processing - which is intended: This incoming OGM might be the cause of purging outdated entries, however there might be still other loop-free Routers in the Router list which have a higher path TQ and are therefore more desirable to chose as the new Selected Router than the Router we received this OGM from. +Note that this step can result in rebroadcasting an OGM in step 5.3. which is not the one we have actually received and are currently processing - which is intended: This incoming OGM might be the cause of purging outdated entries, however there might be still other Routers in the Router list which have a higher path TQ and are therefore more desirable to chose as the new Selected Router than the Router we received this OGM from.
h4. 5.3. Switching to (or Keeping) best Router
@@ -231,7 +225,6 @@ h1. Questions
h1. Notes
-* Section 'Receiving other nodes' OGMs' ensures the loop-freeness - any OGM having past that part and is accepted and loop-safe and can potentially be used as a (new) router * 'Router Ranking' purges routers that are outdated in terms of sequence number and selects the routers with the highest path TQ. It further updates the status of the according router the OGm was received from. * With the simple ELP link quality handling the EIGRP/BABEL feasibility is not necessary as any router we could switch to due to EIGRP feasibility but not due to DSDV feasibility is actually a _worse_ choice as that router would have a lower path TQ. * The ELP link quality information could possibly be made more use of. For now, it is always applied very early when receiving the OGM and never considered anymore. It could allow us to (a) switch to another router when the link quality of our currently selected router got worse without needing a higher sequence number of the other router (with the help of EIGRP feasibility). Or (b) allow us to avoid switching to a new, other router upon receiving an OGM from a router other than our selected router because the link quality towards our currently selected router (and therefore its path TQ) increased a lot since we last received the OGM of our currently selected router. So there is potential to optimize things within the _same_ sequence number, but that'd make things more complex and error prune of course. The way it is stated here for BATMAN V at the moment should be rather straight-forward and clear and make it rather unlikely that we'd miss a case where a routing loop could occure (both conception and implementation wise). @@ -256,11 +249,11 @@ if orig_node->last_seqno - router->last_seqno > SEQ_DIFF_MAX.
h2. Removed previous sender field
-h2. Bonding Mode using NDP's link qualities +h2. Bonding Mode using ELP's link qualities
h2. Removal of secondary interface originators
-Instead when receiving an OGM, always the best link quality measured by NDP +Instead when receiving an OGM, always the best link quality measured by ELP will be substracted from the OGM. This shall make multiple interfaces transparent from the OGM algorithm.
@@ -293,25 +286,6 @@ It will switch to the router with the highest path TQ which is still in the OGM_ and rebroadcast its buffered OGM instead of the just received OGM. The just received OGM will still be buffered (router-addr + seqno + path-TQ) though.
-h2. Strict hop-penalty - -In BATMAN V the hop penalty always decreases the OGM's path TQ (at least by 1/255: minimum selectable -hop penalty: 1, path TQ always rounded downwards) - -Routing loops could potentially occure if a link has 0%25 packet loss and: -* Either if the hop penalty is set to 0. -* (Or if the received OGMs path TQ is very low (and hop penalty would not change the path TQ -due to rounding issues?) - -Question: Or is the TTL check in the Router Ranking actually enough? Anyways, I guess having always -monotonically decreasing path TQ values of an OGM upon rebroadcasts is probably also easier to prove -to be loop-free. And shouldn't harm anything - therefore I'd have a better feeling with that change. - -h2. Increase NDP window size to 128 packets - -With removing the Path TQ averaging, things will get too unstable otherwise. Should be -later substituted with an EWMA [1]. - ----
h1. Further Ideas for Optimizations @@ -322,7 +296,7 @@ An accepted router with the highest sequence number has the most up-to-date info
h2. Also aggregate different packet types
-For instance NDP + OGMs to reduce number of packets sent. +For instance ELP + OGMs to reduce number of packets sent.
h2. Positive Feedback OGM rebroadcasting
@@ -331,30 +305,3 @@ When for any originator thes compared to the link quality used for the last rebr h2. No OGMs if no hosts
To be able to reduce the overhead by just putting some intelligent "repeater" nodes somewhere without them sending their own OGMs - -h2. OGM forwarding optimizations in asymmetric neighborhoods - -An asymmetric link can either mean that (a) TQ >> RQ or (b) TQ << RQ. -For OGMs only (b) causes trouble and reduces the propagation time of an OGM -and would therefore be the case to optimize. - -A node with a neighborhood with asymmetric links as in case (b) can be further -devided in the following three cases: -* Church-Tower-Scenario: A node in the valley has symmetric links to most of its close neighbors. -However there might be a few or a single, distant neighbor with an asymmetric link TQ << RQ -where the same node is receiving fine from but cannot forward packets that well to. -* "Valley"-Scenario: A node is surrounded by nodes with a higher transmit power, therefore -for most of its neighbors the link is asymmetric with TQ << RQ. -* Or mixtures - -The scenarios could be detected via NDP. - -h3. Extra OGM Unicasting - -In the Church-Tower-Scenario extra OGMs could be forwarded via unicast to the few nodes. -(Extra OGM broadcasts would be unfair for the other neighbors) - -h3. Extra OGM Broadcasting - -For the "Valley"-Scenario an OGM could be broadcasted more than once. -(Extra OGM Unicasting might result in too many packets) \ No newline at end of file