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

From: Kilian Weniger <[email-masked]>
Date: Wed, 4 Feb 2004 15:02:27 +0100

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,

Kilian Weniger, Oliver Stanze

-- 
Dipl.-Ing. Kilian Weniger	
Institute of Telematics, Universitaet Karlsruhe (TH)
Zirkel 2, 76128 Karlsruhe, Germany
Email: [email-masked], HP: http://www.tm.uka.de/~weniger

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

---

From: Ian Chakeres <[email-masked]>
Date: Wed, 4 Feb 2004 09:32:57 -0800

How would you suggest to handle this situation? Or what is a better
way to perform DSN wrap-around?

Ian Chakeres

>Kilian Weniger wrote:

---

From: Kilian Weniger <[email-masked]>
Date: Thu, 5 Feb 2004 13:58:25 +0100

Hello Ian,

> way to perform DSN wrap-around?

A possible solution could be, that node A synchronizes DSN_A(C) with DSN_C(C) 
from time to time (e.g. once per day), so that the difference of DSN_A(C) and 
DSN_C(C) never grows larger than MAX_VALUE/2. Unfortunately, this would 
require some minor changes to AODV:

If a node would maintain a sequence number sync timer (SN_SYNC) per active 
route, it could issue a RREQ (with "D"-flag set) for C if the timer expires. 
Because the route exists and is active, the RREQ can even be send hop-by-hop 
per unicast to C to save bandwidth (hop-by-hop to establish reverse-path). If 
node A receives the RREP from C, DSN_A(C) will be equal to DSN_C(C) and the 
problem is solved. If node A does not receive a RREP(because RREQ/RREP got 
lost), node A invalidates the route to C and starts a normal RREQ procedure 
(with "D"-flag set).

SN_SYNC must be choosen small enough to prevent a difference of MAX_VALUE/2.
If SN_SYNC is one day, node C could send RREQs at the maximum RREQ_RATELIMIT 
and RREPs at the rate of about 25.000 per second (assuming that it increases 
the SN by one for each RREP). A RREP_RATELIMIT could be useful to have an 
upper bound for the maximum possible SN incrementation per second. 

Another very simple (but not very nice) solution could be, that node C reboots 
in case of a wrap-around....

Kilian Weniger,
Oliver Stanze

>
> >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).
> >3. D has an active route to C, which breaks frequently -> D issues RREQs
> > and DSN_C(C) increases permanently
> >5. B knows current DSN of C (DSN_B(C)==DSN_C(C)) because of received RREQs
> > or Hellos
> >8. E receives RREP from A and B and chooses A as next hop because DSN_A(C)
> > > DSN_B(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
> >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.
> >

Phone: +49 721 608 6415, Fax: +49 721 388097