Repository : ssh://git@open-mesh.org/doc
On branches: backup-redmine/2017-07-13,master
commit 7558f3e9d4974a4b253f9a844b02c02a2862aaae Author: Linus Lüssing linus.luessing@c0d3.blue Date: Fri Jun 24 02:42:25 2011 +0000
doc: batman-adv/OGM: adding some descriptions of why certain steps are being done (those texts might need some more cleaning-up, restructuring / more clear separation from mandatory proceedings)
7558f3e9d4974a4b253f9a844b02c02a2862aaae batman-adv/OGM.textile | 38 +++++++++++++++++++++++++++++++++----- 1 file changed, 33 insertions(+), 5 deletions(-)
diff --git a/batman-adv/OGM.textile b/batman-adv/OGM.textile index 65238ef2..e4646a83 100644 --- a/batman-adv/OGM.textile +++ b/batman-adv/OGM.textile @@ -110,6 +110,8 @@ h4. 4.2.1. Preliminary Checks
h4. 4.2.2. Potential Router Checks
+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. + * 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. ** 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. @@ -126,10 +128,21 @@ A final check then needs to be applied:
h3. 5. Router Ranking
-For each OGM having passed the previous checks the according neighbor is a potential, loop-free router and therefore the following actions must be performed: +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 relinqushing 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 numbe, 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: + * 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.
@@ -142,12 +155,24 @@ h4. 5.1. Creating or Updating Originator and Router Entries
h4. 5.2. Purging Outdated Router Entries
+It might happen that for instance from a certain Neighbor we would receive an OGM of perfect quality first and will chose that Router. However after that the path over that Selected Router could suddenly be jammed, leading to no more updates from that Router, resulting in a stale entry. Newer and newer (higher sequence number) OGMs might arrive over other potential Routers, but would never be chosen because of a path TQ never being better than perfect, highest path TQ of the currently Selected Router. Therefore we need to at some point consider this Selected Router as outdated and switch to one of the alternative, loop-free Routers in our list which provide more up-to-date information. This is not being done time-based but based on the sequence number, a Selected Router may only be chosen if its OGM has not been older than OGM_SEQ_RANGE sequence numbers. + +Note that a lower OGM_SEQ_RANGE favours chosing Routers with the most-up-to date information: This especially penalizes asymmetric links and paths - although we do not receive that many OGMs from such a Router with such an asymmetric path (showing a not that good receive quality), it might still be the best choice for transmitting our own data packets though. And could lead to fast route flapping also in symmetric topologies when OGMs in general have a low probability of arrival. However having a too large OGM_SEQ_RANGE might favour too old, outdated information too much, as described with the example before. + +More precisely we have do: + * 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_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. + h4. 5.3. Switching to (or Keeping) best Router
+This step ensures a good Router selection to the best knowledge of a node. As the Router list only keeps potential, loop-free nodes (due to steps 4.2.2 and 5.4) which are further not too old (due to step 5.2) we can now freely chose a node from this list. If in this round we got an OGM of a Router which we did not and will not chose as the Selected Router (due to a lower path TQ, although it would be feasible to chose it due to a newer sequence number of this OGM), than we just updated this Routers values, without selecting it. Instead the next steps will chose the same old Router (which is not the one we received the current OGM from) again - but will avoid rebroadcasting the OGM of the old, though still best old and newly Selected Router, due to the Rebroadcasted flag. + +Specifically, we must undertake the following actions: + * Set the Selected Router to the Router with the highest path TQ. * If the Selected Router's Rebroadcasted flag is not set: ** Rebroadcast the OGM of this Selected Router. @@ -155,10 +180,13 @@ h4. 5.3. Switching to (or Keeping) best Router
h4. 5.4. Purging non-potential Routers
+When rebroadcasting a new OGM certain other Routers do not guarantee loop-freeness anymore. We can still chose the Routers from our list that either have broadcasted a higher sequence number than the one we might have just rebroadcasted, they or any next hop behind them are not allowed to switch their route to a lower sequence number (like the one we might just have rebroadcasted) again. Or we could chose any router in the list with the same sequence number and a higher path TQ than the one of the Selected Router (though this will not be the case, because step 5.3. ensured that we are already chosing the Router with the highest path TQ from our Router list). In all other cases we do not consider these Neighbors as potential Routers anymore, they or any next hop behind them might start chosing us as their router without us noticing. Therefore we remove them from the list to ensure a safe Router list: + * Purge all routers with a sequence number smaller than the Selected Router's Sequence Number. * Purge all routers with a sequence number equal to the Selected Router's Sequence Number and a path TQ smaller than the Selected Router's path TQ.
-h3. 5.5. Re-broadcasting other nodes' OGMs + +h3. 6. 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: @@ -166,9 +194,9 @@ When an OGM is to be re-broadcasted some of the message fields must be changed o * The TTL must be decremented by one. If the TTL becomes zero (after the decrementation) the packet must be dropped. * The hop penalty must be applied on the OGM's TQ field. See 'Penalties - Hop Penalty' for further details. If the OGM's TQ becomes zero (after hop penalty) the packet must be dropped.
-h2. 6. Penalties +h2. 7. Penalties
-h3. 6.1 Hop Penalty +h3. 7.1 Hop Penalty
In certain network setups the link quality between neighbors is very similar whereas the number of hops is not. In these scenarios it is desirable to chose the shortest path to reduce latency and to safe bandwidth (especially on wireless mediums). The hop penalty is a value greater than zero and smaller or equal to one. It is a fixed value but may be changed during runtime. The hop penalty is applied on an outgoing OGM in the followig way:
@@ -177,7 +205,7 @@ In certain network setups the link quality between neighbors is very similar whe The result always needs to be rounded down to ensure that an outgoing OGM's TQ is always smaller than the incoming OGM's TQ.
-h2. 7. Proposed Values for Constants +h2. 8. Proposed Values for Constants
OGM_SEQ_RANGE: 5