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

On branches: batman-adv-doc,master

commit 9dced6419bb15f61a56079f7901b5fdcf0bb115b Author: Simon Wunderlich siwu@hrz.tu-chemnitz.de Date: Fri Jan 2 11:10:51 2009 +0100

fix typos, add illustrations for hop penalty

9dced6419bb15f61a56079f7901b5fdcf0bb115b batman_iv.docbook | 43 ++++++++++++++++++++++++------------------- images/hop_penalty3.dia | Bin 0 -> 1297 bytes images/hop_penalty4.dia | Bin 0 -> 1448 bytes images/hop_penalty5.dia | Bin 0 -> 1328 bytes images/hop_penalty6.dia | Bin 0 -> 1453 bytes 5 files changed, 24 insertions(+), 19 deletions(-)

diff --git a/batman_iv.docbook b/batman_iv.docbook index e7d651e2..cf05948c 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -252,7 +252,7 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, <para> <inlinemediaobject> <imageobject> <imagedata fileref="images/asym_link1.pdf" format="EPS" scale="50" /> </imageobject> - <imageobject> <imagedata fileref="images/asym_link1.png" format="PNG" /> </imageobject> + <imageobject> <imagedata fileref="images/asym_link1.png" format="PNG" scale="50" /> </imageobject> <textobject> <phrase>Asymetry situation without asymetry penalty</phrase> </textobject> </inlinemediaobject> </para> @@ -284,36 +284,41 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, B.A.T.M.A.N. IV loosens the strict packet drop policy used by B.A.T.M.A.N. III to make the TQ algorithm work. This introduces a new problem: In certain cases B.A.T.M.A.N. IV is unable to detect the 'real' source of an OGM which may lead to temporary routing loops. The following section is going to illustrate the issue and how it is going to be addressed using an Ethernet network as example for the sake of simplicity. WiFi and other mediums are less susceptible as Ethernet but still affected. </para> <para> - Example topology: The node SOURCE has a WiFi connection towards node A but no link to node B at all. Node A and node B are connected via Ethernet. We assume the Ethernet connection to be perfect (no packet loss) whereas the WiFi connection suffers from occasional collisions and interferences. [bild1 hier] + Example topology: The node SOURCE has a WiFi connection towards node A but no link to node B at all. Node A and node B are connected via Ethernet. We assume the Ethernet connection to be perfect (no packet loss) whereas the WiFi connection suffers from occasional collisions and interferences. + <inlinemediaobject> + <imageobject> <imagedata fileref="images/hop_penalty3.pdf" format="EPS" scale="50" /> </imageobject> + <imageobject> <imagedata fileref="images/hop_penalty3.png" format="PNG" /> </imageobject> + <textobject> <phrase>example topology</phrase> </textobject> + </inlinemediaobject> + </para> <para> - Whenever node A receives a packet via the WiFi connection it will rebroadcast the information on the Ethernet to inform neighbors nodes about the existance of the source node. Node B receive the broadcast and parses the packet before rebroadcasting it. At that point node A will receive that very packet again. [bild2] + Whenever node A receives a packet via the WiFi connection it will rebroadcast the information on the Ethernet to inform neighbor nodes about the existance of the source node. Node B receives the broadcast and parses the packet before rebroadcasting it. At that point node A will receive that very packet again. + <inlinemediaobject> + <imageobject> <imagedata fileref="images/hop_penalty4.pdf" format="EPS" scale="50" /> </imageobject> + <imageobject> <imagedata fileref="images/hop_penalty4.png" format="PNG" /> </imageobject> + <textobject> <phrase>packet hops</phrase> </textobject> + </inlinemediaobject>

B.A.T.M.A.N. III would have dropped the packet at this point. It has a duplicate packet detection based on sequence numbers. The sequence number is known, hence the packet dropped (the fastest packet wins). In asymetric environments this may lead to suboptimal routing decisions. Therefore B.A.T.M.A.N. IV interprets the arrival of this packet as second path towards the originator. This path transmits the packet slower (due to more hops for example) but but may offer a better transmit quality. </para> <para> On a lossy medium the TQ value is decreased while travelling from hop to hop (see asymetric link handling). The Ethernet connection does not suffer from packet loss which results in not decreasing the TQ value at all. Node A has 2 possible routes towards the originator: The SOURCE itself and node B (both will advertise the same TQ value). [bild3] + <inlinemediaobject> + <imageobject> <imagedata fileref="images/hop_penalty5.pdf" format="EPS" scale="50" /> </imageobject> + <imageobject> <imagedata fileref="images/hop_penalty5.png" format="PNG" /> </imageobject> + <textobject> <phrase>route candidates</phrase> </textobject> + </inlinemediaobject> +

As B.A.T.M.A.N. IV values TQ and fastest packet the node A's route will point towards the SOURCE node. Once the WiFi link quality drops (for a few moments due to some collisions) the TQ value from the SOURCE node will drop. At that point the B.A.T.M.A.N. IV node A will change its route towards node B which offers a better TQ value. Node A and node B will send packets forth and back in a loop. </para> <para> - To overcome this issue B.A.T.M.A.N. IV introduces a hop penalty: Every time an OGM passes a node the TQ value will be decreased by a fixed value regardless of the asymetric link penalty before rebroadcasting the packet. In the given example it decrease the value of the second route via node B. [bild???] -</para> -<para> - - The duplicate packet detection wont drop this packet because it was never received via this neighbor. It - TODO There would be loops in "perfect" networks without loss, e.g. ethernet. - <inlinemediaobject> - <imageobject> <imagedata fileref="images/hop_penalty1.pdf" format="EPS" scale="50" /> </imageobject> - <imageobject> <imagedata fileref="images/hop_penalty1.png" format="PNG" /> </imageobject> - <textobject> <phrase>no hop penalty</phrase> </textobject> - </inlinemediaobject> - - Explain hop penalty. + To overcome this issue B.A.T.M.A.N. IV introduces a hop penalty: Every time an OGM passes a node the TQ value will be decreased by a fixed value regardless of the asymetric link penalty before rebroadcasting the packet. In the given example it decrease the value of the second route via node B. <inlinemediaobject> - <imageobject> <imagedata fileref="images/hop_penalty2.pdf" format="EPS" scale="50" /> </imageobject> - <imageobject> <imagedata fileref="images/hop_penalty2.png" format="PNG" /> </imageobject> - <textobject> <phrase>hop penalty applied</phrase> </textobject> + <imageobject> <imagedata fileref="images/hop_penalty6.pdf" format="EPS" scale="50" /> </imageobject> + <imageobject> <imagedata fileref="images/hop_penalty6.png" format="PNG" /> </imageobject> + <textobject> <phrase>applied hop penalty</phrase> </textobject> </inlinemediaobject>

</para> diff --git a/images/hop_penalty3.dia b/images/hop_penalty3.dia new file mode 100644 index 00000000..26672e09 Binary files /dev/null and b/images/hop_penalty3.dia differ diff --git a/images/hop_penalty4.dia b/images/hop_penalty4.dia new file mode 100644 index 00000000..5f093c01 Binary files /dev/null and b/images/hop_penalty4.dia differ diff --git a/images/hop_penalty5.dia b/images/hop_penalty5.dia new file mode 100644 index 00000000..0e8d83a8 Binary files /dev/null and b/images/hop_penalty5.dia differ diff --git a/images/hop_penalty6.dia b/images/hop_penalty6.dia new file mode 100644 index 00000000..e002f695 Binary files /dev/null and b/images/hop_penalty6.dia differ