Subject: AODV RREQ forwarding

From: Erik Nordström <[email-masked]>
Date: 30 Oct 2001 16:12:39 +0100

Hi

I have got some questions about the AODV draft.

RREQ's
======
When generating a RREQ and broadcasting it to neighbors, the neighbors
may forward the RREQ so that the node that originated the RREQ receives
its own forwarded RREQ which in turn forwards this forwarded message.
This may result in a loop. The loop will continue until a RREP is
received by the requesting node. Fortunately, the loop is prevented by
ignoring RREQ's received within BROADCAST_RECORD time as in section 8.3,
so the RREQ just makes 1 1/2 loop, i.e. from src -> neighbor -> src ->
neighbor. Is this correct, or am I missing something here?

Intuitively, a node generating a RREQ should not process any received
RREQ's which was originated by the node itself. Otherwise it will
process the RREQ (its own) as described in section 8.3.1 of the draft.
The result will be that it creates a reverse route entry to itself.

Even more serious is the case when a node which does not run AODV tries
to communicate with a node that runs AODV. The AODV node will then
generate a RREQ for a node to which there exists no route (at least if
you depend on hello messages) and a flooding of RREQ's will occur. This
could be exploited to attack the ad hoc network. I didn't manage to find
anything in the AODV draft that prevents this from happening, but maybe
I missed something? Are my findings at all valid?

Hello messages and sequence numbers
===================================
Another question is about sequence numbers in hello messages. The draft
explains how to send hello messages, but it says nothing about how to
process them. Should the sequence number in the hello message always be
put in the route entry for a destination? This would mean that a higher
number can be overwritten by a smaller one from a hello message. And
what happens when a node postpones hello mesages due to other broadcasts
being sent? Those messages do not necessarily contain a sequence number
that can replace the one in the hello message. 
A case study may clearify what I mean:

case 1).
If two nodes which are neighbors, both with sequence numbers 0, move out
of contact, they increase the sequnce number to the other node by one.
But their own sequence numbers remain at zero, right? But when they move
back into contact they send their own sequence numbers in the hello
messages and the receiveing node overwrites the incremented number in
the routing table, setting it to zero once again. Is this the desired
behavior?

case 2).
Finally, what happens in the case above if one of the nodes postpones a
hello message as implied in section 8.7, because of a recently
broadcasted RREQ? I assume one of the nodes will not update its sequence
number for the other destination, since a RREQ does not necessarily
contain a sequence number from the neighbor who sent it. This will
result in different behavior than in case 1, which seems strange.

Section 8.4.1. implicitly states that a node's own sequence number
should be updated whenever it detects a change in its neighbor set. This
would possibly change the cases described above, but I can't find any
section in the draft that describes when to update a nodes own sequence
number. 

Could someone fill me in on what I am missing?

Erik Nordström,
Uppsala University, Sweden.

---

From: "Samir R. Das" <[email-masked]>
Date: Tue, 30 Oct 2001 13:19:47 -0500

Hi Erik,

Comments inline.

Samir

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Erik Nordström
> Sent: Tuesday, October 30, 2001 10:13 AM
> To: MANET Mailing List
> Subject: AODV RREQ forwarding
>
>
> Hi
>

Any node, including the source, will ignore duplicate copies RREQ. So, there
is no possibility of any loop. The draft is probably not explicit in stating
in 8.3 that the source acts as if it has already seen the RREQ! I assume
that this is the source of your confusion.

> I missed something? Are my findings at all valid?

Yes. Attacks like this can happen. Even if an AODV implementation tries to
pace RREQ floods, attacks can still happen, possibility with less severity.
At present AODV (or for that matter the MANET routing protocols I am aware
of) do not specify any security measures. If you are too worried about it,
you may have put in some sort of authentication scheme, where a node will
not forward any packet not generated by a trusted party.

Note that such attacks are not AODV specific. All routing protocols
are vulnerable in one way or the other.

> Hello messages and sequence numbers

The draft treats hello messages as special type of RREP. See, 8.7. So they
are processed exactly as RREP is processed.

> the routing table, setting it to zero once again. Is this the desired

I am not sure I understand your scenario. Since there is a change
in the neigbor set, the nodes should increment their own
sequence numbers. Why do you think that they wouldn't?

> result in different behavior than in case 1, which seems strange.

This different behavior does not affect the intent of the protocol;
so we mandate this to save on overheads. All we care about here
is maintaining local connecitivity (neighborhood) information via hello
messages. It is OK even if we don't know the latest sequence no. of
the neighbor(s).

> section in the draft that describes when to update a nodes own sequence

Yes. They should update their sequence no. when they detect a change
in the nighbor set.

---

From: Erik Nordström <[email-masked]>
Date: 30 Oct 2001 20:20:10 +0100

Hello

Thank you for replying. I also inlined my comments below.

/Erik

> that this is the source of your confusion.

Yes, I assumed something like this would be the case. I found it strange
though that the draft didn't mention that the node originating the RREQ
should remember its own RREQ or just simply ignore them.
> sequence numbers. Why do you think that they wouldn't?

Elisabeth Royer explained to me in a reply... I knew something had to be
wrong with my scenario, otherwise I would not have asked about it. The
draft does not mention when to increase your own sequence number
(nowhere I can find anyway). There is only a vague hint in section 8.4.
that you should do something with your own sequence number. Elisabeth
mentioned that there are updated texts that clarifies this.

---

From: Sumit Gwalani <[email-masked]>
Date: Wed, 31 Oct 2001 02:12:44 -0800 (PST)

Hello,

I am currently involved in a simulation which
requires the Glomosim code for AODV IETF draft 
version 8. I would be greatful if anyone could
let me know where I could find the same.

Thanks,
Sumit