commits December 2017

commits@lists.open-mesh.org

1 participants
242 discussions

[doc] batman-adv-doc, master: clean up asym penalty graph (b42a7ebc)
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 b42a7ebcd6834c60c85729a376fd6e8ed65475c0 Author: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de> Date: Sat Apr 11 00:06:29 2009 +0200 clean up asym penalty graph >--------------------------------------------------------------- b42a7ebcd6834c60c85729a376fd6e8ed65475c0 images/asym_penalty.gp | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) diff --git a/images/asym_penalty.gp b/images/asym_penalty.gp index 8ed0e6b0..178c42d8 100644 --- a/images/asym_penalty.gp +++ b/images/asym_penalty.gp @@ -1,7 +1,7 @@ #!/usr/bin/gnuplot -set title "Asymetry Penalty illustration" -set xlabel "Receive Quality (RQ)" -set ylabel "applied Asymetry Penalty" +set title "Asymetry Penalty Illustration, assuming incoming TQ = 1.0" +set xlabel "receive quality (RQ)" +set ylabel "rebroadcasted TQ value" set xrange [0:1] set yrange [0:1] set grid @@ -9,11 +9,9 @@ set grid set terminal png set output "asym_penalty.png" -plot (1 - (1-x) ** 3) title "asymetry penalty 1 - (1-x)^3",\ - x title "receive quality" +plot (1 - (1-x) ** 3) title "asymetry penalty 1 - (1-x)^3" set terminal postscript eps enhanced color solid set output "asym_penalty.eps" -plot (1 - (1-x) ** 3) title "asymetry penalty 1 - (1-x)^3",\ - x title "receive quality" +plot (1 - (1-x) ** 3) title "asymetry penalty 1 - (1-x)^3"

1 0

[doc] batman-adv-doc, master: minor "assumption" fix (b411f17b)
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 b411f17bb490b941abcc4926ef023b28e9d31890 Author: Marek Lindner <lindner_marek(a)yahoo.de> Date: Sat Apr 11 07:56:00 2009 +0800 minor "assumption" fix >--------------------------------------------------------------- b411f17bb490b941abcc4926ef023b28e9d31890 batman_iv.docbook | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index 0b47682f..bf7004a4 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -379,7 +379,7 @@ So far, B.A.T.M.A.N. IV focusses only on the link quality to evaluate paths but not on the number of hops in the path as it is unaware of the topology beyond its horizon. In certain network setups the link quality of the neighbors is very similar whereas the number of hops is not. In these scenarios it is very desirable to choose the shortest path to reduce latency and to safe bandwidth (on wireless mediums). 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: The nodes A, B and C that are connected to a network switch. Node A originates the first message which is received, processed and rebroadcasted by B immediately. The rebroadcast from node B arrives at node C before the message from node A arrives. As the link quality is the same and perfect (in this example) Node C assumes a path towards node A via node B. [penalty1 bild] + Example: The nodes A, B and C that are connected to a network switch. Node A originates the first message which is received, processed and rebroadcasted by B immediately. Lets assume the rebroadcast from node B arrives at node C before the message from node A arrives. As the link quality is the same and perfect (in this example) Node C assumes a path towards node A via node B. [penalty1 bild] </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 route via node B and favors the direct connection. [penalty2 bild]

1 0

[doc] batman-adv-doc, master: improve HNA example (291b1ad3)
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 291b1ad353260895b0a0d44f9b1b52e61418dd43 Author: Marek Lindner <lindner_marek(a)yahoo.de> Date: Sat Apr 11 07:59:17 2009 +0800 improve HNA example >--------------------------------------------------------------- 291b1ad353260895b0a0d44f9b1b52e61418dd43 batman_iv.docbook | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index bf7004a4..4b9afe04 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -470,19 +470,19 @@ <row> <entry colname="colB">16-19</entry> <entry namest="col0" nameend="col0">TQ</entry> - <entry namest="col1" nameend="col1">HNA length (2)</entry> - <entry namest="col2" nameend="col3">HNA address</entry> + <entry namest="col1" nameend="col1">HNA length = 2</entry> + <entry namest="col2" nameend="col3">HNA address #1</entry> </row> <row> <entry colname="colB">20-23</entry> - <entry namest="col0" nameend="col1">HNA address</entry> - <entry namest="col2" nameend="col2">Subnetmask</entry> - <entry namest="col3" nameend="col3">HNA address</entry> + <entry namest="col0" nameend="col1">HNA address #1 (continued)</entry> + <entry namest="col2" nameend="col2">Subnetmask #1</entry> + <entry namest="col3" nameend="col3">HNA address #2 </entry> </row> <row> <entry colname="colB">24-27</entry> - <entry namest="col0" nameend="col2">HNA address</entry> - <entry namest="col3" nameend="col3">Subnetmask</entry> + <entry namest="col0" nameend="col2">HNA address #2 (continued)</entry> + <entry namest="col3" nameend="col3">Subnetmask #2 </entry> </row> <row> <entry colname="colB">28-31</entry>

1 0

[doc] batman-adv-doc, master: Remove race condition in creation of images from tex (1e142acb)
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 1e142acb56f539165841003088dce5b48c6a3b31 Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Mon Jan 26 13:29:42 2009 +0100 Remove race condition in creation of images from tex The conversation from tex to png and eps used a static name for temporary file names. This made it nearly impossible to use `make -j` to start a parallel build without overriding the results of another tex file. >--------------------------------------------------------------- 1e142acb56f539165841003088dce5b48c6a3b31 images/Makefile | 33 +++++++++++++++------------------ 1 file changed, 15 insertions(+), 18 deletions(-) diff --git a/images/Makefile b/images/Makefile index deb781eb..139f6e52 100644 --- a/images/Makefile +++ b/images/Makefile @@ -15,7 +15,7 @@ EPS_IMAGES+=$(GP_IMAGES:.gp=.eps) EPS_IMAGES+=$(TEX_IMAGES:.tex=.eps) .PHONY: clean -.SUFFIXES: .dia .png .eps .gp +.SUFFIXES: .dia .png .eps .gp .dvi .ps default: all all: stamp @@ -32,21 +32,18 @@ stamp: $(EPS_IMAGES) $(PNG_IMAGES) /usr/bin/dia -e $@ $< .dia.eps: /usr/bin/dia -e $@ $< -.tex.eps: - rm -f file_tmp.* - cp $< file_tmp.tex - latex file_tmp.tex - dvips file_tmp.dvi - ps2eps -l file_tmp.ps - mv file_tmp.eps $@ - 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.* + +.tex.dvi: + latex $< + rm $(<:.tex=.log) $(<:.tex=.aux) + +.dvi.ps: + dvips $< + +.ps.eps: + ps2eps -l $< + +.eps.png: + convert $< $@ clean: - rm -f *.png *.eps stamp + rm -f *.png *.eps *.aux *.dvi *.log stamp

1 0

[doc] batman-adv-doc, master: fix typos (thanks Linus) (90cbcf5b)
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 90cbcf5b0dd14521f8510b4d80f9bc03dba13925 Author: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de> Date: Wed Feb 11 19:38:43 2009 +0100 fix typos (thanks Linus) >--------------------------------------------------------------- 90cbcf5b0dd14521f8510b4d80f9bc03dba13925 batman_iv.docbook | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/batman_iv.docbook b/batman_iv.docbook index d965df4b..1531848c 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -152,7 +152,7 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, <sect2 id="batman4_tq"> <title>The Transmit Quality</title> <para> - 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. + 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 probability of a successful 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.

1 0

[doc] batman-adv-doc, master: Add build instructions (7eb727eb)
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 7eb727eb3925e71849af0bc29bd1cac80b12b965 Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Sun Feb 22 15:08:39 2009 +0100 Add build instructions >--------------------------------------------------------------- 7eb727eb3925e71849af0bc29bd1cac80b12b965 README | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) diff --git a/README b/README new file mode 100644 index 00000000..7d0f9179 --- /dev/null +++ b/README @@ -0,0 +1,34 @@ +Requirements +============ + + * GNU make - http://www.gnu.org/software/make/ + * xmlto - https://fedorahosted.org/xmlto/ + * docbook-xml (>= 4.5) - http://www.oasis-open.org/docbook/xml/ + * docbook-xsl - http://wiki.docbook.org/topic/DocBookXslStylesheets + * fop - http://xmlgraphics.apache.org/fop/ + * ghostscript - http://www.ghostscript.com/ + * coreutils - http://www.gnu.org/software/coreutils/ + * gnuplot - http://gnuplot.sourceforge.net/ + * dia - http://live.gnome.org/Dia + * texlive-latex-base - http://www.tug.org/texlive/ + * texlive-base - http://www.tug.org/texlive/ + * ps2eps - http://www.tm.uka.de/~bless/ps2eps + * imagemagick - http://www.imagemagick.org/ + + +Supported build targets +======================= + + $ make batman_doc +build complete documentation with all chapters + + $ make batman_iv_only_doc +build only chapter about B.A.T.M.A.N. algorithm + + +Troubleshooting +=============== + * libjli.so: cannot open shared object file: No such file or directory + Make sure that /proc is mounted and `ls -l /bin/ls -l /proc/self/exe` prints + [...] /proc/self/exe -> /bin/ls + See http://bugs.debian.org/435293 for more informations

1 0

[doc] batman-adv-doc, master: Ignore images/stamp in `git status` (c4539153)
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 c4539153697c3c995a9d5a60c65a775942cc27d3 Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Sun Feb 22 15:09:03 2009 +0100 Ignore images/stamp in `git status` >--------------------------------------------------------------- c4539153697c3c995a9d5a60c65a775942cc27d3 .gitignore | 1 + 1 file changed, 1 insertion(+) diff --git a/.gitignore b/.gitignore index b8e8991e..70a584bf 100644 --- a/.gitignore +++ b/.gitignore @@ -5,3 +5,4 @@ *~ images/*.eps images/*.png +images/stamp

1 0

[doc] batman-adv-doc, master: echo cancellation improved, hop penalty rewritten & packet aggregation added (4a6a7219)
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 4a6a72193876ed951f6965f7cea2d92908fd9477 Author: Marek Lindner <lindner_marek(a)yahoo.de> Date: Mon Mar 30 16:23:29 2009 +0800 echo cancellation improved, hop penalty rewritten & packet aggregation added >--------------------------------------------------------------- 4a6a72193876ed951f6965f7cea2d92908fd9477 batman_adv.docbook | 14 +-- batman_iv.docbook | 315 ++++++++++++++++++++++++++++++++++------------------- 2 files changed, 208 insertions(+), 121 deletions(-) diff --git a/batman_adv.docbook b/batman_adv.docbook index 9559075b..70cf8b4d 100644 --- a/batman_adv.docbook +++ b/batman_adv.docbook @@ -30,13 +30,13 @@ <tgroup cols="9"> <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*"/> - <colspec colnum="6" colname="col4" colwidth="1*"/> - <colspec colnum="7" colname="col5" colwidth="1*"/> - <colspec colnum="8" colname="col6" colwidth="1*"/> - <colspec colnum="9" colname="col7" colwidth="1*"/> + <colspec colnum="3" colname="col1" colwidth="1*"/> + <colspec colnum="4" colname="col2" colwidth="1*"/> + <colspec colnum="5" colname="col3" colwidth="1*"/> + <colspec colnum="6" colname="col4" colwidth="1*"/> + <colspec colnum="7" colname="col5" colwidth="1*"/> + <colspec colnum="8" colname="col6" colwidth="1*"/> + <colspec colnum="9" colname="col7" colwidth="1*"/> <thead><row> <entry>+</entry> <entry>00</entry> diff --git a/batman_iv.docbook b/batman_iv.docbook index 1531848c..aa2ffd36 100644 --- a/batman_iv.docbook +++ b/batman_iv.docbook @@ -4,10 +4,6 @@ <sect1 id="batman3"> <title>B.A.T.M.A.N. III (introduction)</title> <para> - - [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 @@ -21,15 +17,11 @@ 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> - </para> - - <sect2 id="how_works"> +<sect2 id="how_works"> <title>B.A.T.M.A.N. 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 @@ -45,40 +37,20 @@ 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, + 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> - [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 too asymetric (unusable) and therefore ignored. - - [more text needed here ? we can add it later when we work on the IV advantages] - + towards every originator on the network. 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 too asymetric + (unusable) and therefore ignored. </para> </sect2> - <sect2 id="multiple_interfaces"> -<title>multiple interfaces</title> -<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"> @@ -98,55 +70,55 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, 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> +<title>The B.A.T.M.A.N. IV originator message format</title> <para> -<table> - <title>B.A.T.M.A.N. IV layer 3 packet format</title> - <tgroup cols="5"> + <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> + <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> - + <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="col3">Previous Sender Address</entry> + </row> + <row> + <entry colname="colB">16-19</entry> + <entry namest="col0" nameend="col0">TQ</entry> + <entry namest="col1" nameend="col1">HNA length</entry> + <entry namest="col2" nameend="col3"> (...)</entry> + </row> </tbody> - </tgroup> - </table> + </tgroup> + </table> </para> </sect2> <sect2 id="batman4_tq"> @@ -212,7 +184,7 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, <sect2 id="batman4_tq_prop"> <title>Transmit Quality Propagation</title> <para> - 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. + 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 (255) 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: @@ -247,7 +219,7 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, </inlinemediaobject> </para> <para> - Due to this layout the originator messages from node A have a good chance arriving at B but the TQ value propagated by node B is very low due to the high packet loss towards node A. The messages from node A that travel via node C have a low probablity arriving at node B due to the packet loss towards node B but have a much better TQ value. Node B will propagate many messages with a low TQ value (received from node A directly) and a few messages with a high TQ value (received from node A via node C) although the connection towards node A is very good. + Due to this layout the originator messages from node A have a good chance arriving at B but the TQ value propagated by node B is very low due to the high packet loss towards node A. The messages from node A that travel via node C have a low probability arriving at node B due to the packet loss towards node B but have a much better TQ value. Node B will propagate many messages with a low TQ value (received from node A directly) and a few messages with a high TQ value (received from node A via node C) although the connection towards node A is very good. </para> <para> <inlinemediaobject> @@ -258,7 +230,7 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, </para> <para> - Therefore, B.A.T.M.A.N. IV will rebroadcast the received OGM with the TQ value of the best neighbor towards the originator. In the given example node B will place the TQ value received via node C in the message from node A before rebroadcasting it. It will flood its best TQ only. [bild3] + Therefore, B.A.T.M.A.N. IV will rebroadcast the received OGM with the TQ value of the best neighbor towards the originator. In the given example node B will place the TQ value received via node C in the message from node A before rebroadcasting it. It will flood its best TQ only. </para> <para> <inlinemediaobject> @@ -321,13 +293,42 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, </para> </sect2> -<sect2 id="batman4_tq_hop_penalty"> -<title>Hop penalty</title> +<sect2 id="batman4_tq_echo_cancellation"> +<title>Echo cancellation</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. + 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. B.A.T.M.A.N. IV checks for unknown sequence numbers via a specific neighbor whereas B.A.T.M.A.N. III checks for known sequence numbers. If this combination is "new" the OGM will be accepted, processed and rebroadcasted. This may duplicate known information when the message "comes back" due to rebroadcasting (so called echos). In dense areas without heavy packet loss this leads to increased bandwidth and CPU usage. </para> <para> - Example topology: The node S (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. + Example: 3 nodes (A, B and C) in a row (A can hear B but not C). Node A emits an OGM, Node B hears and rebroadcasts it. The broadcast from node B arrives at A and C. Node A will drop the message as A detects that it was the originator of this OGM. C will process and rebroadcasts the message. Node B will receive the very OGM that it sent before and happily rebroadcast again (the echo of its own message) because B can't detect that it broadcasted the message before. +</para> +<para> + <inlinemediaobject> + <imageobject> <imagedata fileref="images/echo_cancel1.eps" format="EPS" scale="50" /> </imageobject> + <imageobject> <imagedata fileref="images/echo_cancel1.png" format="PNG" /> </imageobject> + <textobject> <phrase>communication without echo cancellation</phrase> </textobject> + </inlinemediaobject> +</para> +<para> + To detect echos (messages that already passed through a node) B.A.T.M.A.N. IV introduces a new protocol field called "previous sender" which contains the IP address of the node rebroadcasting the OGM. Whenever a node receives a message from a neighbor it will fill the "previous sender" field with the address of the sending neighbor before rebroadcasting it. If a node detects his own IP address in the "previous sender" field the packet will be ignored. +</para> +<para> + Back to the example: Node B will ignore (drop) the packet coming back from node C as node C wrote the IP address of node B in the "previous sender" field. +</para> +<para> + <inlinemediaobject> + <imageobject> <imagedata fileref="images/echo_cancel2.eps" format="EPS" scale="50" /> </imageobject> + <imageobject> <imagedata fileref="images/echo_cancel2.png" format="PNG" /> </imageobject> + <textobject> <phrase>communication with echo cancellation</phrase> </textobject> + </inlinemediaobject> +</para> +<para> + Even in more sophisticated scenarios with more nodes/hops this concept successfully reduces the packets. It ensures that packet only travels paths which did not see this OGM before. +</para> +<para> + 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 the echo cancellation addresses it 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: The node S (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. </para> <para> <inlinemediaobject> @@ -363,9 +364,6 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, As B.A.T.M.A.N. IV values TQ and fastest packet the node A's route will point towards the node S. Once the WiFi link quality drops (for a few moments due to some collisions) the TQ value from the node S 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. -</para> -<para> <inlinemediaobject> <imageobject> <imagedata fileref="images/hop_penalty6.eps" format="EPS" scale="50" /> </imageobject> <imageobject> <imagedata fileref="images/hop_penalty6.png" format="PNG" /> </imageobject> @@ -375,46 +373,135 @@ TODO Explain multiple interfaces, which interface sends which OGM by which TTL, </para> </sect2> -<sect2 id="batman4_tq_echo_cancellation"> -<title>Echo cancellation</title> +<sect2 id="batman4_tq_hop_penalty"> +<title>Hop penalty</title> <para> - As explained in the hop penalty section B.A.T.M.A.N. IV floods the network with more packets than B.A.T.M.A.N. III due to the less strict duplicate detection mechanism. B.A.T.M.A.N. IV checks for unknown sequence numbers via a specific neighbor. If this combination is "new" the OGM will be accepted, processed and rebroadcasted. This may duplicate known information when the message "comes back" due to rebroadcasting (so called echos). In dense areas without heavy packet loss this leads to increased bandwidth and CPU usage. + So far, B.A.T.M.A.N. IV focusses only on the link quality to evaluate paths but not on the number of hops in the path as it is unaware of the topology beyond its horizon. In certain network setups the link quality of the neighbors is very similar whereas the number of hops is not. In these scenarios it is very desirable to choose the shortest path to reduce latency and to safe bandwidth (on wireless mediums). 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> - <inlinemediaobject> - <imageobject> <imagedata fileref="images/echo_cancel1.eps" format="EPS" scale="50" /> </imageobject> - <imageobject> <imagedata fileref="images/echo_cancel1.png" format="PNG" /> </imageobject> - <textobject> <phrase>communication without echo cancellation penalty</phrase> </textobject> - </inlinemediaobject> - + Example: The nodes A, B and C that are connected to a network switch. Node A originates the first message which is received, processed and rebroadcasted by B immediately. The rebroadcast from node B arrives at node C before the message from node A arrives. As the link quality is the same and perfect (in this example) Node C assumes a path towards node A via node B. [penalty1 bild] </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 route via node B and favors the direct connection. [penalty2 bild] +</para> +</sect2> +<sect2 id="batman4_packet_aggregation"> +<title>Packet Aggregation</title> <para> - Lets consider the following example: 3 nodes (A, B and C) in a row (A can hear B but not C). Node A emits an OGM, B hears and rebroadcasts it. This broadcast from B arrives at C which also rebroadcasts the message. B will receive the very OGM that it sent before and happily rebroadcast again (the echo of its own message). + In dense node areas with low packet loss B.A.T.M.A.N. III generates quite some packets which increases the probability of collisions, wastes air time and causes more CPU load. Each OGM being 20 Bytes small, B.A.T.M.A.N. IV introduces a packet aggregation that combines several distinct OGMs into one packet. To achieve this B.A.T.M.A.N. IV holds back packets that are to be sent and waits for incoming packets to append them before broadcasting the single aggregated packet. </para> <para> - To detect echos (messages that already passed through a node) B.A.T.M.A.N. IV introduces a new protocol field called "old originator" which contains the IP address of the node rebroadcasting the OGM. Whenever a node receives a message from a neighbor it will fill the "old originator" field with the address of this neighbor before rebroadcasting it. If the neighbor recognizes his own IP address in the "old originator" field the packet will be ignored. + Every OGM consists of the static B.A.T.M.A.N. IV header (see: originator message format) plus the dynamic HNA message part. </para> <para> - Back to the example: Node B will ignore (drop) the packet coming back from node C as node C wrote the IP address of node B in the "old originator" field. + <table> + <title>HNA (layer 3) message 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="col3">HNA address</entry> + </row> + <row> + <entry colname="colB">04-07</entry> + <entry namest="col0" nameend="col0">Subnetmask</entry> + </row> + </tbody> + </tgroup> + </table> </para> <para> - <inlinemediaobject> - <imageobject> <imagedata fileref="images/echo_cancel2.eps" format="EPS" scale="50" /> </imageobject> - <imageobject> <imagedata fileref="images/echo_cancel2.png" format="PNG" /> </imageobject> - <textobject> <phrase>communication without echo cancellation penalty</phrase> </textobject> - </inlinemediaobject> + B.A.T.M.A.N. IV allows to append none, one or multiple HNA messages. As each OGM may carry multiple HNA information it is necessary to store the number of HNA messages in the newly created HNA length field. </para> <para> - Even in more sophisticated scenarios with more nodes/hops this concept successfully reduces the packets. It ensures that packet only travels paths which did not see this OGM before. + <table> + <title>example B.A.T.M.A.N. IV (layer 3) aggregated packet</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="col3">Previous Sender Address</entry> + </row> + <row> + <entry colname="colB">16-19</entry> + <entry namest="col0" nameend="col0">TQ</entry> + <entry namest="col1" nameend="col1">HNA length (2)</entry> + <entry namest="col2" nameend="col3">HNA address</entry> + </row> + <row> + <entry colname="colB">20-23</entry> + <entry namest="col0" nameend="col1">HNA address</entry> + <entry namest="col2" nameend="col2">Subnetmask</entry> + <entry namest="col3" nameend="col3">HNA address</entry> + </row> + <row> + <entry colname="colB">24-27</entry> + <entry namest="col0" nameend="col2">HNA address</entry> + <entry namest="col3" nameend="col3">Subnetmask</entry> + </row> + <row> + <entry colname="colB">28-31</entry> + <entry namest="col0" nameend="col3">next B.A.T.M.A.N. IV header</entry> + </row> + </tbody> + </tgroup> + </table> </para> </sect2> -<sect2 id="batman4_packet_aggregation"> -<title>Packet Aggregation</title> + <sect2 id="multiple_interfaces"> +<title>multiple interfaces</title> <para> - TODO aggregate packets to reduce overhead and CPU cycles -</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>

1 0

[doc] batman-adv-doc, master: Correct /bin/ls test in README:Troubleshooting (e95ed364)
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 e95ed36496bc0964251ed59940411b598d1ec47c Author: Sven Eckelmann <sven.eckelmann(a)gmx.de> Date: Sun Feb 22 15:11:37 2009 +0100 Correct /bin/ls test in README:Troubleshooting >--------------------------------------------------------------- e95ed36496bc0964251ed59940411b598d1ec47c README | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/README b/README index 7d0f9179..8f4ff7dc 100644 --- a/README +++ b/README @@ -20,7 +20,7 @@ Supported build targets ======================= $ make batman_doc -build complete documentation with all chapters +build complete documentation with all chapters (default when running `make`) $ make batman_iv_only_doc build only chapter about B.A.T.M.A.N. algorithm @@ -28,7 +28,7 @@ build only chapter about B.A.T.M.A.N. algorithm Troubleshooting =============== - * libjli.so: cannot open shared object file: No such file or directory - Make sure that /proc is mounted and `ls -l /bin/ls -l /proc/self/exe` prints + * "libjli.so: cannot open shared object file: No such file or directory" + Make sure that /proc is mounted and `/bin/ls -l /proc/self/exe` prints [...] /proc/self/exe -> /bin/ls See http://bugs.debian.org/435293 for more informations

1 0

[doc] batman-adv-doc, master: update batman -> B.A.T.M.A.N. (cc5ecffd)
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 cc5ecffdad2dbfd2c7fa2b7fa50c17cdb543ae8f Author: Simon Wunderlich <siwu(a)hrz.tu-chemnitz.de> Date: Fri Apr 10 13:29:58 2009 +0200 update batman -> B.A.T.M.A.N. >--------------------------------------------------------------- cc5ecffdad2dbfd2c7fa2b7fa50c17cdb543ae8f images/asymetry.dia | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/images/asymetry.dia b/images/asymetry.dia index 9d6e3051..d77dafec 100644 --- a/images/asymetry.dia +++ b/images/asymetry.dia @@ -308,12 +308,12 @@ <dia:point val="11.238,6.272"/> </dia:attribute> <dia:attribute name="obj_bb"> - <dia:rectangle val="11.238,5.5945;15.023,8.767"/> + <dia:rectangle val="11.238,5.57325;16.5392,8.8095"/> </dia:attribute> <dia:attribute name="text"> <dia:composite type="text"> <dia:attribute name="string"> - <dia:string>#batman III + <dia:string>#B.A.T.M.A.N. III metric: 100% to A#</dia:string> </dia:attribute> @@ -343,12 +343,12 @@ metric: <dia:point val="0.3061,6.38"/> </dia:attribute> <dia:attribute name="obj_bb"> - <dia:rectangle val="0.3061,5.7025;3.9986,8.875"/> + <dia:rectangle val="0.3061,5.68125;5.60735,8.9175"/> </dia:attribute> <dia:attribute name="text"> <dia:composite type="text"> <dia:attribute name="string"> - <dia:string>#batman III + <dia:string>#B.A.T.M.A.N. III metric: 5% to B#</dia:string> </dia:attribute>

1 0

← Newer
1
...
8
9
10
11
12
13
14
...
25
Older →

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

commits December 2017