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

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

commit 6f0cce3e834c9b5852c12d6de95be4bb4f9eaf3a Author: Linus Lüssing linus.luessing@c0d3.blue Date: Sat May 7 19:35:23 2011 +0000

doc: batman-adv/T_X's_Junkyard_–_MGO

6f0cce3e834c9b5852c12d6de95be4bb4f9eaf3a .../T_X's_Junkyard_\342\200\223_MGO.textile" | 186 +++++++++++++++++++++ 1 file changed, 186 insertions(+)

diff --git "a/batman-adv/T_X's_Junkyard_\342\200\223_MGO.textile" "b/batman-adv/T_X's_Junkyard_\342\200\223_MGO.textile" new file mode 100644 index 00000000..12245755 --- /dev/null +++ "b/batman-adv/T_X's_Junkyard_\342\200\223_MGO.textile" @@ -0,0 +1,186 @@ +h1. MGO - Message Guided towards Originator + +h1. Concept + +In certain topologies the OGM (Originator Message) protocol can still have severe performance problems: When a link on the best path suddenly breaks down, it can take a long time for BATMAN to accept the alternative path, as many OGMs need to arrive over the alternative path to push away the previous best hops. This needs to be done as we need a strict OGM forwarding policy to avoid routing loops. + +The purpose of the MGO protocol is to react to (rapidly) decreasing local link qualities and to actively try to find an alternative, loop-free path, while only increasing the overhead on the currently selected and alternative paths. It shall complement the proactive OGM protocol. + +The MGO protocol is split into two parts: The Router Alert part to mark the currently selected best path(s) as 'fragile' in response to a previously detected emergency event. And the Router Request part to request newer sequence numbers from alternative paths that allow nodes on the marked 'fragile' path to switch to the alternative path safely, e.g. without causing routing loops. + + + +h2. RA - Router Alert + +h3. Concept + +The purpose of an MGO-RA is to mark the currently selected best path as 'fragile' in response to a previously detected emergency event. + +h3. Router Alert Event Detection + +A node usually measures the link quality more frequently than the quality of whole pathes (see NDP). If a node detects a major change in the global TQ it has last advertised, it will send a Router Alert Messages. More precisely, if: +* The best of all link RQ values towards a neighbor node decreased (e.g. a new NDP message with missed sequence numbers or the absence of NDP messages over time, see [[Ndp|NDP]] for details). +* The according node is a selected router towards one or more originators. + +For any of the originators this neighbor is a router for further check: +* The best of all link RQ values towards the according neighbor node is MGO_RA_THRESHOLD in absolute value lower than the link RQ used for the last rebroadcasted OGM of the according originator. +* If so, an alert event is triggered for this originator. + +If one or more originators exist that a router alert event has been triggered for, then an MGO-RA must be generated and sent. + +---- + +h3. Router Alert Event Detection (simple) + +A node usually measures the link quality more frequently than the quality of whole pathes (see NDP). If a node detects that a neighbor node is not reachable anymore, it will send (a) Router Alert message(s). More precisely, if: +* The only link RQ available towards a neighbor node reached zero (see [[Ndp|NDP]] for details) +* The according node is a selected router towards one or more originators. + +An MGO-RA needs to be generated for any of these matching originators then. + +---- + +h3. Broadcasting own Router Alert (MGO-RA) Message + +h4. The Router Alert (MGO-RA) Message Format: + +<pre> + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Packet Type | Version | Num RA Entries| Alignment | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +</pre> + +h4. The Router Alert Entry Format: + +<pre> + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Originator | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Originator | Preference Router | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Preference Router | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Last Seqno | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Path TQ | Alignment | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +</pre> + +An MGO-RA is always (re)broadcasted MGO_RA_NUM_BCASTS times. + +---- + +h4. The Router Alert (MGO-RA) Message Format (simple): + +<pre> + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Packet Type | Version | Originator | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Originator | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Last Seqno | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +</pre> + +---- + +h3. Reception + +h3. Reception (simple) + +h3. Forwarding + +h3. Forwarding (simple) + +h2. RR - Router Request + +h3. Concept +An MGO-RR is directly aimed at the originator(s) we are searching an alternative +path for. Its purpose is to request newer sequence numbers over the +alternative path and to notify nodes along this path that they should +forward OGMs more reliable (e.g. rebroadcast an OGM more than once or send it to the +requester via unicast or one broadcast and one unicast packet). +Such a request does not have to travel along the whole alternative path, +instead any node with a new enough OGM sequence number may resend its last OGM. + +h3. Initiation + +The MGO-RR process will be triggered for any MGO-RA entry in the packet +matching: +* We are the MGO-RA:Preference Router +* Last sender of MGO-RA is not our current best next hop towards the MGO-RA:orig. + +For any match we are sending an MGO-RR to our according best next hop. + +h3. Initiation (simple) + +h4. Unicasting own Router Request (MGO-RR) message + +h4. Unicasting own Router Request (MGO-RR) message (simple) + +h4. The Router Alert (MGO-RA) Message Format: + +<pre> + 0 1 2 3 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +</pre> + +h4. The Router Alert (MGO-RA) Message Format (simple): + +h3. Reception + +A node receiving an MGO-RR has to check whether it has a valid, non-'fragile' +path towards the stated originator. If it only has a 'fragile' path then +this means that node's previous MGO-RA have not be heard by the last sender +and the receiving node may resend its last MGO-RA. + +h3. Reception (simple) + +h3. Forwarding + +h3. Forwarding (simple) + +h4. OGM on 'fragile' path + +Any node will still process an OGM as usual. However, when an OGM were +dropped and not further forwarded the following additional checks have to +be performed instead: +* Am I on a matching, 'fragile' path? (has this node previously broadcasted +an MGO-UHM with an orig entry matching OGM:orig). +* If yes, is the OGM:seqno newer than MGO-RA:last-seqno? +* If yes, is the OGM:path-TQ higher than MGO-RA:path-TQ? + +If any of the previous checks does not match, then the OGM has to be dropped +as the OGM protocol would have done itself. Otherwise the OGM will be +further processed in the same way as if SEQ_DIFF_MAX were reached: +* The old, 'fragile' router will be purged. +* The OGM will be rebroadcasted. +Additionally the rebroadcasting should be done in a robust way, the same way +as nodes forwarding OGMs reliably due to MGO-DHMs (e.g. 3x rebroadcast). + +Furthermore, any rebroadcasted OGM matching an MGO-UHM will remove the 'fragile' +status for that originator (no matter if due to common OGM rebroadcast rule or +MGOs graceful rebroadcasting rule). As well as any OGM coming from the old, +'fragile' best next hop, no matter if we are going to rebroadcast it or not. + +h4. [OGM on 'fragile' path (simple)] + +h2. Proposed Values for Constants + +MGO_RA_NUM_BCASTS: 3 +MGO_RA_THRESHOLD: 50%25 + +---- + +h1. Questions + +* \ No newline at end of file