Subject: Re: AODV RREQ forwarding

From: "Elizabeth M. Belding-Royer" <[email-masked]>
Date: Tue, 30 Oct 2001 09:47:50 -0800 (PST)

Hi Erik,

~> 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.
~> 

Right.  We've recently made some minor clarifications to the draft
based on feedback like this.  We've corrected this problem, so that
when a source node originates a RREQ, it records the BroadcastID and
its Src IP address so that it won't re-process its original RREQ when
it receives it from its neighbors.

~> 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?
~> 

You mean what happens when the destination is a node which is not
running AODV?  I'd assume in that case you won't be able to locate it,
unless its neighbors have learned some other way that it is its
neighbor.  I don't think this problem is unique to AODV, though.

~> 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?
~> 

Actually, what happens is that when a node loses a neighbor, it increments
its own sequence number as well.  We are adding some text to the draft
to clarify this.  Basically, a node increments its own seq# whenever
it either gains or loses a neighbor.  So in this case, the nodes would
increment their own seq#'s when they lost contact, and then increment their
seq# AGAIN when they come back into contact, so the scenario you are
describing will not occur.

~> 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.

It is not necessary for a node to always know its neighbor's most recent
seq#.  If it has a stale seq# for that neighbor, its fine.  Route finding
should still proceed correctly.  Hello messages do not have to be used
with AODV.  In this case, nodes will generally not discover each other's
sequence numbers until they are either the source or destination of a
route request.

~> 
~> 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. 
~> 

The added text I referred to above should take care of this.

I hope this clears things up for you.

Elizabeth

---

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

Hi.

Thank you for replying so quickly. Ok, so most of the issues I brought
up has already been covered by other feedback. The new text you are
refering to, is that available somewhere? I would need it for the
implementation I'm working on...

While I'm at it, I might as well ask about section 8.3. It is a bit
unclear if the time for "remembering" RREQ's should be updated with
BROADCAST_RECORD_TIME each time the same RREQ arrives or just for the
first one?

> neighbor.  I don't think this problem is unique to AODV, though.

Yes, I guess it is a problem shared by most reactive protocols (that use
RREQ's of some sort). The result would be that a node, or possibly
several depending on how many nodes the non-participant node (not
running AODV) is trying to communicate with, would send "bogus" RREQ's.
Other nodes would forward those RREQ's and thus generating a lot of
unnecessary traffic. But maybe not enough to do any harm...
I was just wondering if there would be some way to avoid this behavior?
Or is it something which is not seen as a problem?

/Erik

---

From: Dan Iregren <[email-masked]>
Date: Wed, 31 Oct 2001 09:53:04 +0100 (CET)

Hi,
Consider the following scenario with the four nodes, a - d, all running
AODV as described in draft 8.

			[c]
	[a]	[b]
			[d]

[a] is within range of [b].
[b], [c] and [d] are all within range of eachother.
All routing tables are empty and each node has sequence number 0.

Then,

[d] sends a request asking for route to [x] ([x] is not one of [a], [b],
[c] and [d]).

Only [b] receives the request. [b] does not have a route towards [x] so it
forwards the request but no one receives that packet. While processing the
request [b] creates a backward route towards [d].

[d] sends another request asking for [x] since the first one failed.

Only [b] receives the (second) request, [b] still does not have a route
towards [x] so it forwards the request.
[b] does nothing with its route entry towards [d].

[a] receives the (second) request forwarded by [b].
While processing the request [a] creates a backward route towards [d].

NOTE,
[a] and [b] now both have routes towards [d], [a]'s route towards
[d] has a longer remaining lifetime than [b]'s route towards [d].

After some time, [b] deactivates its route towards [d].

If for instance [c] sends a request asking for [d] then that request will
be answered by [a] and that will cause [b] to set up a route towards [d]
with nexthop [a] while [a] has a route towards [d] with nexthop [b].

We have a loop, so what is wrong here?

/Dan

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 31 Oct 2001 07:55:49 -0800

Hello Dan,

The assumption for these reverse routes is that they were
very short lived.  On the one hand, it means that any such
scenario as you describe would be very short-lived.  And on
the other hand, it also means that we didn't very much
consider whether our algorithm for these short-lived routes
might introduce difficulties when packets were dropped or
other unusual circumstances.

Here are some ideas on how to fix the problem you describe.

1) Cause the reverse route at any node to remain active
   until at least  (current_time  +  REV_ROUTE_LIFE).

2) Perhaps better, we might decrement the lifetime of the
   reverse route as the RREQ traverses the network.  This
   would protect against the possibility that
   node [a] times out its reverse route towards [x] _AFTER_
   node [b] times out its reverse route towards [x], setting
   up an even more miniscule but nonzero time window for AODV
   to follow your error script.

   For this, the reverse route lifetime should be:
   (current_time  +  REV_ROUTE_LIFE  -  HopCount*NODE_TRAVERSAL_TIME)

Do you think this fixes the problem?

By fortunate circumstance, I was just finishing a new revision
of AODV to update the Security Considerations, per IESG request,
and making some other clarifications about broadcast and so on.
I will now include some additional text to set the lifetime for
reverse routes more precisely, according to whatever discussion
follows on from these messages.

Thanks for your comments!

Regards,
Charlie P.