commits December 2017

commits@lists.open-mesh.org

1 participants
242 discussions

[doc] batman-adv-doc, master: minor text updates (d881b1e9)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit d881b1e9be096e019aeacc0c44ad6fa2c3920ecb Author: Marek <marek(a)openmoko.com> Date: Sun Sep 28 15:01:21 2008 +0800 minor text updates >--------------------------------------------------------------- d881b1e9be096e019aeacc0c44ad6fa2c3920ecb batman_iv.docbook | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index 565fe797..9354f25f 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -146,7 +146,10 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, The local link quality needs to be propagated throughout the network to inform other nodes about the transmit quality. Therefore B.A.TM.A.N. IV introduces a new field called "TQ" which is 1 byte long. This field is added to the known B.A.T.M.A.N. III packet. Whenever the OGM is generated this field is set to maximum length (256) before it is broadcasted. The receiving neighbor will calculate their own local link quality into the received TQ value and rebroadcast the packet. Hence, every node receiving a packet knows about the transmit quality towards the originator node. </para> <para> - To add the local link quality in the TQ value the following calculation is performed: TQ incoming * local TQ towards this node / TQ max. + To add the local link quality in the TQ value the following calculation is performed: +</para> +<para> + TQ incoming * local TQ towards this node / TQ max. </para> <para> Example: Node A broadcasts the packet with TQ max. Node B receives it, applies the TQ calculation and rebroadcasts it. When node C gets the packet it knows about the transmit quality towards node A. [illustration needed] @@ -163,18 +166,17 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, </orderedlist> </para> <para> - The calculation for the local TQ needs the OGM packet count of the neigbor and the own OGM packet count rebroadcasted by that very neighbor. Therefore a B.A.T.M.A.N. node has keep track of received packets over a certain interval. The slinding window size of these statistics is called TQ_LOCAL_WINDOW_SIZE. [what else shoud be mentioned here ?] + The calculation for the local TQ needs the OGM packet count of the neigbor and the own OGM packet count rebroadcasted by that very neighbor. Therefore a B.A.T.M.A.N. node has keep track of received packets over a certain interval. The slinding window size of these statistics is called TQ_LOCAL_WINDOW_SIZE. </para> <para> - The global TQ is an average of all received TQ values from one originator via a distinct neighbor. Packets with a TQ value of 0 also count as non-received packets. B.A.T.M.A.N. IV uses a sliding window size (TQ_GLOBAL_WINDOW_SIZE) greater than 1 [dat muss noch schöner ...] + The global TQ is an average of all received TQ values from one originator via a distinct neighbor. Packets with a TQ value of 0 also count as non-received packets. B.A.T.M.A.N. IV uses the sliding window size TQ_GLOBAL_WINDOW_SIZE greater than 1 to average the TQ. </para> </sect2> <sect2 id="batman4_tq_asymetry"> <title>Handling asymetric links</title> <para> -TODO Only transmit quality is not enough - nothing worth if the receive - direction is too bad to receive WIFI acks. + Although the transmit link quality is most important B.A.T.M.A.N. IV also keeps track of the receiving link quality. On the WiFi layer every unicast packet has to be acknowledged by the neighbor node. If this neighbor is not able to sucessfully transmit his ACKs the WiFi layer considers this transmission to be failed. <inlinemediaobject> <imageobject> <imagedata fileref="images/asym_link1.pdf" format="EPS" scale="50" /> </imageobject> <imageobject> <imagedata fileref="images/asym_link1.png" format="PNG" /> </imageobject>

1 0

[doc] batman-adv-doc, master: initial text for "Handling asymetric links" (13049888)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit 1304988897578234d0be07df160836344da11810 Author: Marek <marek(a)openmoko.com> Date: Mon Sep 29 10:21:59 2008 +0800 initial text for "Handling asymetric links" >--------------------------------------------------------------- 1304988897578234d0be07df160836344da11810 batman_iv.docbook | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index 9354f25f..cd50f816 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -176,21 +176,29 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, <sect2 id="batman4_tq_asymetry"> <title>Handling asymetric links</title> <para> - Although the transmit link quality is most important B.A.T.M.A.N. IV also keeps track of the receiving link quality. On the WiFi layer every unicast packet has to be acknowledged by the neighbor node. If this neighbor is not able to sucessfully transmit his ACKs the WiFi layer considers this transmission to be failed. + Although the transmit link quality is most important decision factor B.A.T.M.A.N. IV also keeps track of the receiving link quality. On the WiFi layer every unicast packet has to be acknowledged by the neighbor node to approve the transmission. If this neighbor is not able to sucessfully send his ACKs the WiFi layer considers this transmission to be failed and tries to retransmit until it gives up. +</para> +<para> <inlinemediaobject> <imageobject> <imagedata fileref="images/asym_link1.pdf" format="EPS" scale="50" /> </imageobject> <imageobject> <imagedata fileref="images/asym_link1.png" format="PNG" /> </imageobject> <textobject> <phrase>Asymetry situation without asymetry penalty</phrase> </textobject> </inlinemediaobject> - - -TODO Also calculate the receive direction - but weight it. +</para> +<para> + Thus B.A.T.M.A.N. IV needs to penalize links that have have a poor receiving link quality. To avoid a simple hysteresis which completely turns on or off a link B.A.T.M.A.N. IV uses a mathematical function to give the receiving link quality stronger negative impact the weaker the link becomes. +</para> +<para> <inlinemediaobject> <imageobject> <imagedata fileref="images/asym_penalty.pdf" format="EPS" /> </imageobject> <imageobject> <imagedata fileref="images/asym_penalty.png" format="PNG" /> </imageobject> <textobject> <phrase>graph for asymetry penalty</phrase> </textobject> </inlinemediaobject> - +</para> +<para> + This obtained value is calculated into the TQ before it gets rebroadcasted. Neighboring nodes can weight the routing decision based on this information. In some situations the weak link is the only link available, so you want to use it, whereas in other cases better connections may exist. +</para> +<para> <inlinemediaobject> <imageobject> <imagedata fileref="images/asym_link2.pdf" format="EPS" scale="50" /> </imageobject> <imageobject> <imagedata fileref="images/asym_link2.png" format="PNG" /> </imageobject>

1 0

[doc] batman-adv-doc, master: add diagram for tq propagation (377db766)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit 377db7667ec6d390757103266302c589f6724864 Author: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de> Date: Thu Oct 9 18:31:19 2008 +0200 add diagram for tq propagation >--------------------------------------------------------------- 377db7667ec6d390757103266302c589f6724864 batman_iv.docbook | 11 ++++++++++- images/Makefile | 2 +- images/tq_prop.dia | Bin 0 -> 2024 bytes 3 files changed, 11 insertions(+), 2 deletions(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index cd50f816..8b6dddd8 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -152,7 +152,16 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, TQ incoming * local TQ towards this node / TQ max. </para> <para> - Example: Node A broadcasts the packet with TQ max. Node B receives it, applies the TQ calculation and rebroadcasts it. When node C gets the packet it knows about the transmit quality towards node A. [illustration needed] + Example: Node A broadcasts the packet with TQ max. Node B receives it, applies the TQ calculation and rebroadcasts it. When node C gets the packet it knows about the transmit quality towards node A. +</para> +<para> + <inlinemediaobject> + <imageobject> <imagedata fileref="images/tq_prop.pdf" format="EPS" scale="40" /> </imageobject> + <imageobject> <imagedata fileref="images/tq_prop.png" format="PNG" /> </imageobject> + <textobject> <phrase>Transmit Link Quality (TQ)</phrase> </textobject> + </inlinemediaobject> + + </para> </sect2> diff --git a/images/Makefile b/images/Makefile index ae167d56..acca3164 100644 --- a/images/Makefile +++ b/images/Makefile @@ -1,5 +1,5 @@ GP_IMAGES=asym_penalty.gp -DIA_IMAGES=asymetry.dia tq.dia eq.dia rq.dia hop_penalty1.dia hop_penalty2.dia asym_link1.dia asym_link2.dia +DIA_IMAGES=asymetry.dia tq.dia eq.dia rq.dia hop_penalty1.dia hop_penalty2.dia asym_link1.dia asym_link2.dia tq_prop.dia PNG_IMAGES= $(DIA_IMAGES:.dia=.png) PNG_IMAGES+=$(GP_IMAGES:.gp=.png) PDF_IMAGES= $(DIA_IMAGES:.dia=.pdf) diff --git a/images/tq_prop.dia b/images/tq_prop.dia new file mode 100644 index 00000000..5af3eb1a Binary files /dev/null and b/images/tq_prop.dia differ

1 0

[doc] batman-adv-doc, master: add formulas (plus Makefile voodoo to generate them from tex) (2763c2af)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit 2763c2af03d69782b207428af749f99ffe9c97fa Author: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de> Date: Thu Oct 9 19:57:51 2008 +0200 add formulas (plus Makefile voodoo to generate them from tex) >--------------------------------------------------------------- 2763c2af03d69782b207428af749f99ffe9c97fa batman_iv.docbook | 24 +++++++++++++++++------- images/Makefile | 19 +++++++++++++++++++ images/compute_tq.tex | 6 ++++++ images/tq_prop_calc.tex | 6 ++++++ 4 files changed, 48 insertions(+), 7 deletions(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index 8b6dddd8..26c02a8a 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -131,13 +131,19 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, <imageobject> <imagedata fileref="images/tq.pdf" format="EPS" scale="50" /> </imageobject> <imageobject> <imagedata fileref="images/tq.png" format="PNG" /> </imageobject> <textobject> <phrase>Transmit Link Quality (TQ)</phrase> </textobject> - </inlinemediaobject></para> + </inlinemediaobject></para> + <para> + <inlinemediaobject> + <imageobject> <imagedata fileref="images/compute_tq.pdf" format="EPS"/> </imageobject> + <imageobject> <imagedata fileref="images/compute_tq.png" format="PNG" /> </imageobject> + <textobject> <phrase>compute the Transmit Link Quality</phrase> </textobject> + </inlinemediaobject> + </para> + </listitem> </orderedlist> - - As shown above B.A.T.M.A.N. IV is able to retrieve the local transmit quality by using the same mechanisms as B.A.T.M.A.N. III without adding further overhead. -[4 illustrations needed (for each list item and one for the tq alone)] -[??? what kind of 4th illustration? put the formular in a picture, or in the text?] + This shows that B.A.T.M.A.N. IV is able to compute the local Transmit Quality by using the same + mechanisms as B.A.T.M.A.N. III without adding further overhead. </para> </sect2> <sect2 id="batman4_tq_prop"> @@ -149,7 +155,11 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, To add the local link quality in the TQ value the following calculation is performed: </para> <para> - TQ incoming * local TQ towards this node / TQ max. + <inlinemediaobject> + <imageobject> <imagedata fileref="images/tq_prop_calc.pdf" format="EPS" /> </imageobject> + <imageobject> <imagedata fileref="images/tq_prop_calc.png" format="PNG" /> </imageobject> + <textobject> <phrase>TQ calcuation</phrase> </textobject> + </inlinemediaobject> </para> <para> Example: Node A broadcasts the packet with TQ max. Node B receives it, applies the TQ calculation and rebroadcasts it. When node C gets the packet it knows about the transmit quality towards node A. @@ -158,7 +168,7 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, <inlinemediaobject> <imageobject> <imagedata fileref="images/tq_prop.pdf" format="EPS" scale="40" /> </imageobject> <imageobject> <imagedata fileref="images/tq_prop.png" format="PNG" /> </imageobject> - <textobject> <phrase>Transmit Link Quality (TQ)</phrase> </textobject> + <textobject> <phrase>TQ propagation</phrase> </textobject> </inlinemediaobject> diff --git a/images/Makefile b/images/Makefile index acca3164..fd71db05 100644 --- a/images/Makefile +++ b/images/Makefile @@ -1,9 +1,12 @@ GP_IMAGES=asym_penalty.gp DIA_IMAGES=asymetry.dia tq.dia eq.dia rq.dia hop_penalty1.dia hop_penalty2.dia asym_link1.dia asym_link2.dia tq_prop.dia +TEX_IMAGES=compute_tq.tex tq_prop_calc.tex PNG_IMAGES= $(DIA_IMAGES:.dia=.png) PNG_IMAGES+=$(GP_IMAGES:.gp=.png) +PNG_IMAGES+=$(TEX_IMAGES:.tex=.png) PDF_IMAGES= $(DIA_IMAGES:.dia=.pdf) PDF_IMAGES+=$(GP_IMAGES:.gp=.pdf) +PDF_IMAGES+=$(TEX_IMAGES:.tex=.pdf) .PHONY: clean .SUFFIXES: .dia .png .eps .pdf .gp @@ -22,6 +25,22 @@ all: $(PDF_IMAGES) $(PNG_IMAGES) /usr/bin/dia -e $@ $< .eps.pdf: /usr/bin/epstopdf --outfile=$@ $< +.tex.pdf: + rm -f file_tmp.* + cp $< file_tmp.tex + latex file_tmp.tex + dvips file_tmp.dvi + ps2eps -l file_tmp.ps + epstopdf file_tmp.eps + mv file_tmp.pdf $@ + rm -f file_tmp.* +.tex.png: + rm -f file_tmp.* + cp $< file_tmp.tex + latex file_tmp.tex + dvips -x 3000 -y 3000 -E file_tmp.dvi + convert file_tmp.ps $@ + rm -f file_tmp.* clean: rm -f *.png *.eps *.pdf diff --git a/images/compute_tq.tex b/images/compute_tq.tex new file mode 100644 index 00000000..71f7bd75 --- /dev/null +++ b/images/compute_tq.tex @@ -0,0 +1,6 @@ +\documentclass{article} +\pagestyle{empty} +\begin{document} +$EQ = RQ \cdot TQ \qquad \Rightarrow \qquad TQ = \frac{EQ}{RQ}$ +\end{document} + diff --git a/images/tq_prop_calc.tex b/images/tq_prop_calc.tex new file mode 100644 index 00000000..23b71086 --- /dev/null +++ b/images/tq_prop_calc.tex @@ -0,0 +1,6 @@ +\documentclass{article} +\pagestyle{empty} +\begin{document} +$TQ = TQ_{incoming} * TQ_{local}$ +\end{document} +

1 0

[doc] batman-adv-doc, master: add some alternative illustration for the echo quality (33ded001)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit 33ded0015dfe712af138e6a3091c393eca68be69 Author: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de> Date: Thu Oct 9 20:02:35 2008 +0200 add some alternative illustration for the echo quality (only generated, not in the docbook) >--------------------------------------------------------------- 33ded0015dfe712af138e6a3091c393eca68be69 images/Makefile | 3 ++- images/eq_alt1.dia | Bin 0 -> 1138 bytes images/eq_alt2.dia | Bin 0 -> 1139 bytes images/eq_alt3.dia | Bin 0 -> 1136 bytes 4 files changed, 2 insertions(+), 1 deletion(-) diff --git a/images/Makefile b/images/Makefile index fd71db05..b36bed35 100644 --- a/images/Makefile +++ b/images/Makefile @@ -1,5 +1,6 @@ GP_IMAGES=asym_penalty.gp -DIA_IMAGES=asymetry.dia tq.dia eq.dia rq.dia hop_penalty1.dia hop_penalty2.dia asym_link1.dia asym_link2.dia tq_prop.dia +DIA_IMAGES=asymetry.dia tq.dia eq.dia eq_alt1.dia eq_alt2.dia eq_alt3.dia rq.dia \ + hop_penalty1.dia hop_penalty2.dia asym_link1.dia asym_link2.dia tq_prop.dia TEX_IMAGES=compute_tq.tex tq_prop_calc.tex PNG_IMAGES= $(DIA_IMAGES:.dia=.png) PNG_IMAGES+=$(GP_IMAGES:.gp=.png) diff --git a/images/eq_alt1.dia b/images/eq_alt1.dia new file mode 100644 index 00000000..ec32db21 Binary files /dev/null and b/images/eq_alt1.dia differ diff --git a/images/eq_alt2.dia b/images/eq_alt2.dia new file mode 100644 index 00000000..ab85fd17 Binary files /dev/null and b/images/eq_alt2.dia differ diff --git a/images/eq_alt3.dia b/images/eq_alt3.dia new file mode 100644 index 00000000..8623e9bc Binary files /dev/null and b/images/eq_alt3.dia differ

1 0

[doc] batman-adv-doc, master: use alternative 1 for echo quality (eebed9b0)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit eebed9b0178504f0304818aad14fd6679d0ad6e0 Author: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de> Date: Fri Oct 10 12:18:57 2008 +0200 use alternative 1 for echo quality >--------------------------------------------------------------- eebed9b0178504f0304818aad14fd6679d0ad6e0 batman_iv.docbook | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index 26c02a8a..dbcb4a4c 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -119,8 +119,8 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, <para>B.A.T.M.A.N. knows the echo link quality (EQ) by counting rebroadcasts of its own OGMs from his neighbors.</para> <para> <inlinemediaobject> - <imageobject> <imagedata fileref="images/eq.pdf" format="EPS" scale="50" /> </imageobject> - <imageobject> <imagedata fileref="images/eq.png" format="PNG" /> </imageobject> + <imageobject> <imagedata fileref="images/eq_alt1.pdf" format="EPS" scale="50" /> </imageobject> + <imageobject> <imagedata fileref="images/eq_alt1.png" format="PNG" /> </imageobject> <textobject> <phrase>Echo Link Quality (EQ)</phrase> </textobject> </inlinemediaobject></para> </listitem>

1 0

[doc] batman-adv-doc, master: hop penalty and packet format added (3d3bd8aa)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit 3d3bd8aa71697ff094b86402e1d2341c013c528c Author: Marek Lindner <lindner_marek(a)yahoo.de> Date: Thu Jan 1 16:24:13 2009 +0100 hop penalty and packet format added >--------------------------------------------------------------- 3d3bd8aa71697ff094b86402e1d2341c013c528c batman_iv.docbook | 100 ++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 90 insertions(+), 10 deletions(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index dbcb4a4c..e7d651e2 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -1,8 +1,8 @@ <?xml version="1.0" encoding="UTF-8" ?> <chapter id="batman_iv_tq"> -<title>B.A.T.M.A.N. IV/TQ Meshing</title> +<title>B.A.T.M.A.N. IV (TQ) Meshing</title> <sect1 id="batman3"> -<title>BATMAN III (introduction)</title> +<title>B.A.T.M.A.N. III (introduction)</title> <para> [RFC Introduction reused. I think we should do that - it is well @@ -25,7 +25,7 @@ </para> <sect2 id="how_works"> -<title>BATMAN III (brief overview)</title> +<title>B.A.T.M.A.N. III (brief overview)</title> <para> [RFC reused - 1.2. Protocol Overview (second paragraph)] @@ -68,7 +68,7 @@ [more text needed here ? we can add it later when we work on the IV advantages] - </para> +</para> </sect2> <sect2 id="multiple_interfaces"> <title>multiple interfaces</title> @@ -82,21 +82,73 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, </sect1> <sect1 id="batman4"> -<title>BATMAN IV/TQ</title> +<title>B.A.T.M.A.N. IV (TQ)</title> <para> The B.A.T.M.A.N. III algorithm has serious problems when it comes to asymetric links. The bidirectional link check tries to limit its impact but the result is far from being perfect. The timeframe in which B.A.T.M.A.N. accepts his own OGMs being rebroadcasted by its neighbor allows to tweak the behaviour. If this timeframe is rather short B.A.T.M.A.N. is very strict on choosing links. This may lead to many ignored links which might be usable in one direction. Only symetric connections will be considered. If the timeframe value is less strict B.A.T.M.A.N. will accept more links but tends to route in the wrong direction. </para> <para> - Example: OGMs from Node A propagate to B. The link is asymetric, therefore B receives all packets from A in contrast to A which receives almost nothing from B. As all the packets from A get to B the packet count at B's side goes up. B will assume that it has a perfect link towards A which is not the case. + Example: OGMs from Node A propagate to B. The link is asymetric, therefore B receives all packets from A in contrast to A which receives almost nothing from B. As all the packets from A get to B the packet count at B's side goes up. B will assume that it has a perfect link towards A which is not the case. <inlinemediaobject> - <imageobject> <imagedata fileref="images/asymetry.pdf" format="EPS" scale="50"/> </imageobject> - <imageobject> <imagedata fileref="images/asymetry.png" format="PNG" /> </imageobject> - <textobject> <phrase>asymetry illustration</phrase> </textobject> + <imageobject> <imagedata fileref="images/asymetry.pdf" format="EPS" scale="50"/> </imageobject> + <imageobject> <imagedata fileref="images/asymetry.png" format="PNG" /> </imageobject> + <textobject> <phrase>asymetry illustration</phrase> </textobject> </inlinemediaobject> </para> <para> - To overcome this flaw B.A.T.M.A.N. IV has been enhanced with the Transmit Quality (TQ) algorithm. The following section is going to outline its design and how it strengthens B.A.T.M.A.N.'s routing capabilities in asymetric environments. + To overcome this flaw B.A.T.M.A.N. IV has been enhanced with the Transmit Quality (TQ) algorithm. The following sections are going to outline its design and how it strengthens B.A.T.M.A.N.'s routing capabilities in asymetric environments. +</para> +<sect2 id="batman4_packet_layout"> +<title>The B.A.T.M.A.N. IV Orginator Message format</title> +<para> +<table> + <title>B.A.T.M.A.N. IV layer 3 packet format</title> + <tgroup cols="5"> + <colspec colnum="1" colname="colB" colwidth="1*"/> + <colspec colnum="2" colname="col0" colwidth="1*"/> + <colspec colnum="3" colname="col1" colwidth="1*"/> + <colspec colnum="4" colname="col2" colwidth="1*"/> + <colspec colnum="5" colname="col3" colwidth="1*"/> + <thead><row> + <entry>+</entry> + <entry>00</entry> + <entry>01</entry> + <entry>02</entry> + <entry>03</entry> + </row> + </thead> + <tbody> + <row> + <entry colname="colB">00-03</entry> + <entry namest="col0" nameend="col0">Version</entry> + <entry namest="col1" nameend="col1">Flags</entry> + <entry namest="col2" nameend="col2">TTL</entry> + <entry namest="col3" nameend="col3">GW Flags</entry> + </row> + <row> + <entry colname="colB">04-07</entry> + <entry namest="col0" nameend="col1">Seqence Number</entry> + <entry namest="col2" nameend="col3">GW Port</entry> + </row> + <row> + <entry colname="colB">08-11</entry> + <entry namest="col0" nameend="col3">Originator Address</entry> + </row> + <row> + <entry colname="colB">11-15</entry> + <entry namest="col0" nameend="col0">TQ</entry> + <entry namest="col1" nameend="col3">Old Originator Address</entry> + </row> + <row> + <entry colname="colB">16-19</entry> + <entry namest="col0" nameend="col0">Old Originator Address</entry> + <entry namest="col1" nameend="col3"> (...)</entry> + </row> + + </tbody> + </tgroup> + </table> </para> +</sect2> <sect2 id="batman4_tq"> <title>The Transmit Quality</title> <para> @@ -229,6 +281,27 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, <sect2 id="batman4_tq_hop_penalty"> <title>Hop penalty</title> <para> + 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] +</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] + + 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] + + 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> @@ -253,5 +326,12 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, </para> </sect2> +<sect2 id="batman4_packet_aggregation"> +<title>Packet Aggregation</title> +<para> + TODO aggregate packets to reduce overhead and CPU cycles +</para> +</sect2> + </sect1> </chapter>

1 0

[doc] batman-adv-doc, master: fix typos, add illustrations for hop penalty (9dced641)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit 9dced6419bb15f61a56079f7901b5fdcf0bb115b Author: Simon Wunderlich <siwu(a)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

1 0

[doc] batman-adv-doc,master: initial commit (311f820a)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit 311f820a30aea098d9a2839ff3474bd8e1f64fc0 Author: Simon Wunderlich <dotslash(a)prime.dot.net> Date: Sat Jul 5 16:52:55 2008 +0200 initial commit >---------------------------------------------------------------

1 0

[doc] batman-adv-doc, master: add batman IV content (5b3867ec)
by postmaster＠open-mesh.org 14 Dec '17

14 Dec '17

Repository : ssh://git@open-mesh.org/doc On branches: batman-adv-doc,master >--------------------------------------------------------------- commit 5b3867ec25c6033869a72144531960124f1c7f68 Author: Marek <marek(a)openmoko.com> Date: Wed Aug 20 16:04:44 2008 +0800 add batman IV content >--------------------------------------------------------------- 5b3867ec25c6033869a72144531960124f1c7f68 batman_iv.docbook | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 86 insertions(+), 8 deletions(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index 21d48170..85688d9c 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -2,16 +2,72 @@ <chapter id="batman_iv_tq"> <title>B.A.T.M.A.N. IV/TQ Meshing</title> <sect1 id="batman3"> -<title>BATMAN III</title> +<title>BATMAN III (introduction)</title> <para> -TODO What is BATMAN III, where was it implemented first? + + [RFC Introduction reused. I think we should do that - it is well + written. I would even mention that the RFC introduction has been reused.] + + B.A.T.M.A.N. is a proactive routing protocol for Wireless Ad-hoc Mesh + Networks, including (but not limited to) Mobile Ad-hoc Networks + (MANETs). The protocol proactively maintains information about the + existence of all nodes in the mesh that are accessible via single-hop + or multi-hop communication links. The strategy of B.A.T.M.A.N. is to + determine for each destination in the mesh one single-hop neighbor, + which can be utilized as best gateway to communicate with the + destination node. In order to perform multi-hop IP-based routing, + the routing table of a node must contain a link-local gateway for + each host or network route. To learn about the best next-hop for + each destination is all that the B.A.T.M.A.N. algorithm cares about. + There is no need to find out or calculate the complete route, which + makes a very fast and efficient implementation possible. + </para> <sect2 id="how_works"> -<title>BATMAN III</title> +<title>BATMAN III (brief overview)</title> +<para> + + [RFC reused - 1.2. Protocol Overview (second paragraph)] + + On a regular basis every B.A.T.M.A.N. node broadcasts an originator + message (or OGM), thereby informing its link-local neighbors about + its existence (first step). Link-local neighbors which are receiving the + Originator messages are relaying them by rebroadcasting it, according + to specific B.A.T.M.A.N. forwarding rules. The B.A.T.M.A.N. mesh + network is therefore flooded with Originator messages. This flooding + process will be performed by single-hop neighbors in the second step, + by two-hop neighbors in the third step, and so forth. OGMs are send + and repeated as UDP broadcasts, therefore OGMs are flooded until + every node has received it at least once, or until they got lost due + to packet loss of communication links, or until their TTL (time to + live) value has expired. In practise OGM packet loss caused by + interference, collision or congestion is significant. The number of + OGMs received from a given Originator via each link-local neighbor is + used to estimate the quality of a (single-hop or multi-hop) route. + In order to be able to find the best route to a certain Originator, + B.A.T.M.A.N counts the originator-messages received and logs which + link-local neighbor relayed the message. Using this information + B.A.T.M.A.N. maintains a table with the best link-local router + towards every Originator on the network. By using a sequence number, + embedded in each OGM, B.A.T.M.A.N. can distinguish between new + Originator message packets and duplicates ensuring that every OGM + gets only counted once. + +</para> <para> -TODO How does batman III work (briefly, explain bidirectional link checks etc) -Explain how asymetric links are handled (or rather not handled). + [new text! - may be put this into a different subsection (asymetric links)?] + + Unlike wired networks, WiFi setups often face the problem of asymetric + links (Node A has a better connection towards Node B than vice versa). + To ensure that the detected connections allow communication in both + directions each B.A.T.M.A.N. node awaits rebroadcasts of its own OGMs + from his neighbors within a certain timeframe (bidirectional link check). + If the OGMs are not successfully retransmitted the connection is + considered asymetric and therefore ignored. + + [more text needed here ? we can add it later when we work on the IV advantages] + </para> </sect2> <sect2 id="multiple_interfaces"> @@ -19,18 +75,40 @@ Explain how asymetric links are handled (or rather not handled). <para> TODO Explain multiple interfaces, which interface sends which OGM by which TTL, and why. (Maybe move this section somewhere else ... ) + +==> why explaining this in this document ? I would refer them to the RFC because this did not change with IV. </para> </sect2> </sect1> <sect1 id="batman4"> <title>BATMAN IV/TQ</title> +<para> + The B.A.T.M.A.N. III algorithm has serious problems when it comes to asymetric links. The bidirectional link check tries to limit its impact but the result is far from being perfect. The timeframe in which B.A.T.M.A.N. accepts his own OGMs being rebroadcasted by its neighbor allows to tweak the behaviour. If this timeframe is rather short B.A.T.M.A.N. is very strict on choosing links. This may lead to many ignored links which might be usable in one direction. Only symetric connections will be considered. If the timeframe value is less strict B.A.T.M.A.N. will accept more links but tends to route in the wrong direction. +</para> +<para> + Example: OGMs from Node A propagate to B. The link is asymetric, therefore B receives all packets from A in contrast to A which receives almost nothing from B. As all the packets from A get to B the packet count at B's side goes up. B will assume that it has a perfect link towards A which is not the case. [illustration needed] +</para> +<para> + To overcome this flaw B.A.T.M.A.N. IV has been enhanced with the Transmit Quality (TQ) algorithm. The following section is going to outline its design and how it strengthens B.A.T.M.A.N.'s routing capabilities in asymetric environments. +</para> <sect2 id="batman4_tq"> <title>The Transmit Quality</title> <para> -TODO BATMAN uses "receive quality", by counting packets, but should use/calculate - "transmit quality". Send metric (tq) with batman packets. -[ illustration: ... ] + B.A.T.M.A.N. IV divides a given link quality into 2 distinct parts: receiving link quality and transmit link quality. The receiving link quality expresses the propability of a successfull packet transmission towards the node. The transmit link quality describes the probability of a successful transmission towards a neighbor node. Obviously, B.A.T.M.A.N. is more interested in the transmit link quality as the receiving link quality can't be used to influence the routing decision. +</para> +<para> + As explained in the previous section the packet counting floods the network with receiving link quality rather than transmit link quality. On the link-local level the transmit link quality can be derived from the receiving link quality by applying some calculations on the packet count. + + <orderedlist> + <listitem><para>B.A.T.M.A.N. knows the receiving link quality (RQ) by counting the packets of its neighbors.</para></listitem> + <listitem><para>B.A.T.M.A.N. knows the echo link quality (EQ) by counting rebroadcasts of its own OGMs from his neighbors.</para></listitem> + <listitem><para>B.A.T.M.A.N. can calculate the transmit link quality (TQ) by dividing the echo link quality by the receiving link quality.</para></listitem> + </orderedlist> + + As shown above B.A.T.M.A.N. IV is able to retrieve the local transmit quality by using the same mechanisms as B.A.T.M.A.N. III without adding further overhead. + +[4 illustrations needed (for each list item and one for the tq alone)] </para> </sect2> <sect2 id="batman4_tq_prop">

1 0

← Newer
1
...
13
14
15
16
17
18
19
...
25
Older →

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

commits December 2017