Re: A few comments on the BATMAN routing protocol
Commit Message
>
> > 2. BATMAN does not contain any loop avoidance mechanisms; in the
> > presence of so-called ``optimistic routing'', BATMAN may exhibit
> > persistent routing loops. Even without optimistic routing, BATMAN
> > will exhibit transitory routing loops.
>
> Here I completely agree with what Simon Wunderlich said. Personally, I am
> not aware of any scenario that can lead to transient routing loops, not
> even to a dead node! You might know better, then pleas let me know :-)
>
> Each batman node is only supposed to rebroadcast an OGM which it has
> received from the neighbor which it has configured itself as its best
> nexthop to the destination. Therefore, the OGM itself must have travelled a
> valid path with all traversed nodes having a loop free route configured
> towards the originator of the OGM. Of course, the configured end-to-end
> route might break down somewhere along the path just after an OGM has been
> received. This will cause a temporary dead route. But not a loop. Later on,
> only a newer OGM (with a larger sequence number), and which once again must
> have traversed a functional and configured path, can reconfigure any node
> receiving this OGM.
>
> Another remark:
> The batmand-0.2 implementation is not doing this completely correct and
> thus can cause temporary routing loops. The reason is, that it also
> reconfigures its best nexthop due to new OGMs which were not received via
> its currently *best-known* nexthop.
>
Just for the record:
Few days ago I recognized that for my gcc a 32-bit-word shifted by 32 bits is
NOT zero. This pointed me to another bug in the batmand-0.2.x implementation
which could cause a transient routing loop.
This and the above bug should be fixed with the attached patch.
ciao,
axel
Nur in batman-0.2.x-fixes: batmand.
@@ -121,9 +121,11 @@
seq_bits[i]=
(seq_bits[i - word_num] << word_offset) +
- /* take the lower port from the left half, shift it left to its final position */
- (seq_bits[i - word_num - 1] >> (WORD_BIT_SIZE-word_offset));
- /* and the upper part of the right half and shift it left to it's position */
+ /* take the lower port from the left half, shift it left to its final position */
+ /*fix: paradoxically uint32_t test = 1234; test<<32;
+ * results in: test == 1234 */
+ ( ( (seq_bits[i - word_num - 1]) >> ((WORD_BIT_SIZE-word_offset)-1) ) >> 1 );
+ /* and the upper part of the right half and shift it left to it's position */
/* for our example that would be: word[0] = 9800 + 0076 = 9876 */
}
/* now for our last word, i==word_num, we only have the it's "left" half. that's the 1000 word in
Nur in batman-0.2.x-fixes: bitarray.c~.
@@ -176,7 +176,11 @@
neigh_node->packet_count = bit_packet_count( neigh_node->seq_bits );
- if ( neigh_node->packet_count > max_packet_count ) {
+
+ /* fix: a node MUST NOT reconfigures its best nexthop
+ * due to new OGMs which were not received via its currently
+ * best-known nexthop.*/
+ if ( neigh_node->packet_count > max_packet_count && neigh_node->addr == neigh ) {
max_packet_count = neigh_node->packet_count;
best_neigh_node = neigh_node;
Nur in batman-0.2.x-fixes: originator.c~.
Gemeinsame Unterverzeichnisse: batman-0.2.x/.svn und batman-0.2.x-fixes/.svn.