Subject: AODV: Sequence numbers problems ?

From: Yves Prelot <[email-masked]>
Date: Wed, 22 Aug 2001 13:49:11 +0500

Hello,

I have encountered a problem when handling HELLO messages in AODV.
Maybe don't I understand the AODV draft correctly, so could someone
enlighten me  please ?

Here is my problem:

Computer A and computer B are alone on the network.
They only exchange routing messages (no user traffic).

They start sending HELLO messages.

When A receives an HELLO from B (which is in fact an unasked for RREP),
it updates it's routing table and adds the entry for B in it's table
with the Sequence Number given in the HELLO message.

Now, I cut the link between both computers for a sufficient duration
that the new entry expires but not long enough that the entry is
deleted.
When the lifetime for B expires (which means that route to B goes from
state active to unactive) here are the operations done by A, as I
understand from the draft:

1) the operations indicated in paragraph 8.9 are undertaken because B
satisfies the conditions in (i) at the time of the expiry (and also
because paragraph 8.7 says so). In particular, B sequence number is
incremented.
2) the operations indicated in paragraph 8.10 are undertaken. In
particular, B sequence number is incremented.

The draft does not explicitely states the order of these operations,
which in itself might be a problem.
I assume that (1) is done before (2) .

Paragraph 8.9 says that B sequence number (as known to A) must be
incremented.
Paragraph 8.10 says that B sequence number (as known to A) must be
incremented.

Thus, B sequence number (as known to A) will be incremented twice. That
doesn't seem logical.

Of course, the link being broken, B doesn't receive the RERR and does
know that A has a sequence number for him greater that his own. Even if
it had received the RERR (one way link), it would still possess a
sequence number less that the one known to A (because A increased B
sequence number twice).

I reestablish the link between A and B (the route to B still exists, but
is unactive). A receives again HELLO messages from B. HELLO messages are
not treated in a different way that any other RREP messages and thus
proceed under the specifications of paragraph 8.5. In particular,
because the received sequence number is less that it's own copy, A
routing table is not updated. So, even though B signals it's presence, B
is still considered unreachable by A. In time, A will delete it's entry
for B from it's routing table, only to reestablish it as soon as it
receives an HELLO from B with the sequence number known to B (never
incremented).

So my question is: what did I do wrong ?

Thank you,

Yves

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 22 Aug 2001 08:56:33 -0700

Hello Yves,

You point out that the specification seems to allow that the
sequence number should be incremented twice.  Plus, in your
scenario, node A doesn't believe route information about node
B even when that information is delivered directly to A by B.
Both of these problems should be clarified in the draft, and the
effects were unintentional.  I think the best way to fix the first
problem is to say that, after the RERR is sent, the inactive
route entry does not cause the destination sequence number to
be incremented upon deletion.  This amounts to a new flag in
a conceptual data structure.  The second problem can be handled
by explicit specification at an appropriate point within the
sections for handling RREP/Hello.

Do you think this will suffice to solve the problem you found?

Regards,
Charlie P.

---

From: Yves Prelot <[email-masked]>
Date: Thu, 23 Aug 2001 17:15:51 +0500

Hello Charles,

About the problem with RERR and invalidation, I believe that what you suggest
is correct: a modification in the draft should be sufficient to make clear
that when a RERR is sent, the HopCount should not be incremented a second
time.

About the other point, somebody pointed to me that the sentence in paragraph
8.4:
"If the destination node has not detected any change in its set of neighbours
since it last incremented its destination number, it MAY use the same
destination sequence number"

could also be read as:
"If the destination node has detected a change in its set of neighbours since
it last incremented its destination number, it may not use the same
destination sequence number"

which would thus mean that whenever a node detects a change within it's
neighbours, it should increase it's own sequence number.
This would also solve the problem I found. However, this is not actually
written it the draft and it might have side effects. Was it the hidden
meaning of this sentence ?

Otherwise, a clarification somewhere in the HELLO paragraph would also solve
the problem.

However, the problem might be more general than it seems: it comes from the
fact that HELLO is an unasked for RREP. If it has been asked for (if a RREQ
had been sent and the RREP had been a consequence), the sequence number would
have been upgraded and the RREP believed. Because of this, I imagine that
gratuitous RREPs may encounter exactly the same problem. If that is the case,
then Gratuitous RREPs and HELLOs should be treated somewhat differently from
standard RREPs.

Regards,

Yves

---

From: Manel Guerrero Zapata <[email-masked]>
Date: Mon, 27 Aug 2001 14:36:45 +0300

Hi Yves:

1) Well, yeah, there is an ambiguos point in the actual draft
specification.
I've, actually, already metioned it in a mail 2 weeks ago:

> And for case (i) dsn should be incremented in the routing table.
> But remember that you are already incrementing it by making the
> the route to expire, because in the expiry section it is also
> said that dsn should be incremented.
> (let's not increment the dsn twice in different draft sections).

But it's not a big deal. It should just be rewriten in such
a way that everybody understands that you don't increment twice the dsn.

2) Yeah, if the node has detected any change in its set of neighbours
it should increment the dsn. I thing everybody got this (and actualy
is alright if you just increment it always).

3) Nope. There is no such problem with HELLO and G-RREP messages.
Dsn are just to see if a routing message is newer or older than
another one.

BR/Manel