Subject: RE:[manet] Loops in AODV due to seqno wrap-arounds?

From: Marc Mosko <[email-masked]>
Date: Wed, 04 Feb 2004 11:20:23 -0800

A missing element of Step 9 is that B would send a RERR to A when
it's link to C breaks.  Assuming that B had multiple predecessors
and it broadcasts the packet, the RERR could be lost easily.

Another thing would be that the loop is as permanent as the break
in link B-C.  If the link came back, node B should believe the
1-hop hello messages over the route from A, even if DSN_C(C) < DSN_A(C).
But one could construct a similar loop argument where B and C
were not directly attached.

One workaround to this is to use really big sequence numbers,
such as a 64-bit number that has 32-bits from the node's
real-time clock (to avoid reset on reboot) and 32-bits for
a counter.  One could use fewer bits for the counter,  whatever
is practical to avoid overflow in 1 second.  One would want
to use the UTC node time to avoid daylight savings, etc.

For all practical considerations, such a counter is unbounded
because one would assume the node's clock would not overflow
during the node's lifetime.

This, of course, is not compatible with the current version
of AODV.  Other solutions could include some sort of network-wide
reset, but that incurs flooding overhead and you have to make
it reliable and it will have problems with temporary network
partitons.

A heuristic that works with the current AODV version is what
we called "RREQ as error" [1].  It does not absolutely prevent
the loop forming, but could help avoid it. If a node, such as A,
receives a RREQ from its successor for that successor route and by all
metrics stored at A, the successor should have replied to it,
node A can take that RREQ as an implicit RERR.

Node A may assume that its successor B has DSN_B(C) >= DSN_A(C)
(in whatever modulo math used).  This must always be true for
loop-freedom.  If B transmits a RREQ for
C with DSN_RREQ(C) < DSN_A(C), node A may assume that node B
no longer has a valid loop-free route to C and node A can
break its successor link.

Marc Mosko
UC Santa Cruz

[1] J.J. Garcia-Luna-Aceves, Marc Mosko, Charles E. Perkins,
"A New Approach to On-Demand Loop Free Routing in Ad Hoc Networks",
PODC 2003, Boston, MA, July 2003, pp. 53 - 62

 >Kilian Weniger wrote:
 >Hi,
 >
 >we encountered a (admittedly very rare) scenario with AODV, which we think may
 >result in permanent loops in case a sequence number wrap-around occurs.
 >
 >In the following, we describe the scenario. We denote a DSN for node C at node
 >A with DSN_A(C).
 >The maximum possible value of the sequence number is denoted by MAX_VALUE.
 >
 >
 >.. - A - B - C - .. - D
 >
 >
 >1. A has an active route to C
 >2. DSN_A(C) < MAX_VALUE/2
 >3. D has an active route to C, which breaks frequently -> D issues RREQs and
 >DSN_C(C) increases permanently
 >4. A does not receive the RREQs -> DSN_A(C) does not change (still smaller
 >than MAX_VALUE/2)
 >5. B knows current DSN of C (DSN_B(C)==DSN_C(C)) because of received RREQs or
 >Hellos
 >6. Wrap-around of DSN_C(C) occurs -> 0 < DSN_C(C) < DSN_A(C) < MAX_VALUE/2
 >with DSN_B(C)==DSN_C(C)
 >7. New node E joins MANET and issues RREQ for C.
 >
 >The scenario is now as follows:
 >
 >
 >       E
 >     /  \
 >.. - A - B - C - .. - D
 >
 >
 >8. E receives RREP from A and B and chooses A as next hop because DSN_A(C) >
 >DSN_B(C)
 >9. Link B->C breaks and B issues RREQ for C.
 >10. B receives RREP only from E, because A did not receive the RREQ (or A's
 >RREP got lost), e.g., due to MAC layer collisions
 >11. B chooses E as next hop, because DSN_E(C) > DSN_B(C) -> Loop A-B-E
 >
 >
 >Our questions are:
 >
 >Is our conclusion correct?
 >
 >If so, is the scenario relevant enough in practice to be considered?
 >
 >Think of A, B, C as static nodes, e.g., because they are internet
 >gateways, which are connected via ad hoc links. Node D (and others) are mobile
 >nodes, so that link breaks occur frequently.
 >
 >An incrementation of the DSN_C(C) by MAX_VALUE/2 with MAX_VALUE=2^32-1 takes
 >at least MAX_VALUE/2*RREQ_RATE_LIMIT=~6.8 years per route to C, if the SN is
 >increased by one each time. With 100 routes to C, it takes at least ~24 days.
 >According to RFC 3561 section 6.3 ("...which is incremented prior..."), it not
 >forbidden to increase the SN by more than one before sending a RREQ. Thus, it
 >may take a much shorter time span, depending on the implementation.
 >
 >If the scenario is relevant, shouldn't wrap-arounds better be handled
 >differently in a future version of AODV?
 >
 >
 >Best regards,

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet