Repository : ssh://git@open-mesh.org/doc

On branches: backup-redmine/2017-07-13,master

commit bf48f391c3c0f36bf9e650964b4c5476b6b2024e Author: Simon Wunderlich sw@simonwunderlich.de Date: Wed Sep 28 18:33:25 2011 +0000

doc: batman-adv/OGMv2

bf48f391c3c0f36bf9e650964b4c5476b6b2024e batman-adv/OGMv2.textile | 25 ++++++++----------------- 1 file changed, 8 insertions(+), 17 deletions(-)

diff --git a/batman-adv/OGMv2.textile b/batman-adv/OGMv2.textile index 0eed8d9f..649a5ffd 100644 --- a/batman-adv/OGMv2.textile +++ b/batman-adv/OGMv2.textile @@ -120,21 +120,21 @@ The following steps need to be undertaken in the updating and creating process:

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. +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 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. +Note that a lower OGM_SEQ_RANGE favors choosing 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 favor too old, outdated information too much, as described with the example before.

More precisely we have to:

* 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. +** for all Routers of the OGM's originator: if the Originators Sequence Number is by OGM_SEQ_RANGE newer than the Routers Sequence Number, purge the router from the OGM's originator's Router List.

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

-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 choose any 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. +This step ensures a good Router selection to the best knowledge of a node. The Routers values are updated regardless whether it is the selected router or not. If the Rebroadcasted Flag is set for the selected router and the OGM was not received by this router, the OGM will not be rebroadcasted.

Specifically, we must undertake the following actions:

@@ -145,31 +145,22 @@ Specifically, we must undertake the following actions:

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: +To keep the routers list short and clean, we will purge routers with old sequence numbers which are not the selected router or have a lower TQ. These Routers are obsolete and will not be chosen in the future.

If an OGM was rebroadcasted in the previous step: * 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.

-Note: If no OGM was rebroadcasted in the previous section then no purging will be done in this section anyways. However the "If" shall emphasize, that not the switching of the Selected Router makes the router list clean-up in this section mandatory to ensure loop-freeness, but the rebroadcasting of an OGM does. +Note: If no OGM was rebroadcasted in the previous section then no purging will be done in this section anyways. (TODO: can we skip this condition?)

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:

* 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. 7. Penalties - -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: - -* Outgoing OGM's TQ = path TQ * (1 - hop penalty) +* The hop penalty must be applied on the OGM's TQ field. If the OGM's TQ becomes zero (after hop penalty) the packet must be dropped. The hop penalty is applied by reducing the path TQ by HOP_PENALTY percent.

-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. +Note: The Hop penalty is especially required in loss-less networks where shorter path should be favored. It is also useful to select the shortest path in lossy networks where the TQ values are very similar.

h2. 8. Proposed Values for Constants