Subject: Re: More AODV draft issues (+ loops)

From: Dan Iregren <[email-masked]>
Date: Thu, 1 Nov 2001 11:01:45 +0100 (CET)

On 1 Nov 2001, Erik Nordström wrote:

> Finally, in response to Dan Iregren's previous question about the loop
> scenario, here is what I find:
>
> In the last steps of the scenario node [c] sends a RREQ for a route to
> [d]. If received and responded to by [a], the RREQ must have gone
> through [b], and [b] would then have set up a reverse route to [c], the
> RREQ originator.

This is correct, that route is however not of interest for the scenario
and I have ommitted if from the discussion.

> Not [d] as described in the scenario. And during the

The route towards [d] was created earlier, when [d] sent the request for
[x].

> RREP phase, [b] sets up a forward route to [a]. So, a loop would not
> form.

When [a] sends a reply regarding the location of [d] [b] will create a
route towards [d] with [a] as nexthop (according to section 8.5 in the
draft), [a] already had a route towards [d] with [b] as nexthop,
and there we have the loop.

/Dan

---

From: Erik Nordström <[email-masked]>
Date: 01 Nov 2001 12:30:05 +0100

Hi Dan.

I guess you may be right, the RREP from [a] to [c] will create a forward
route to [d] from [b], via [a], right? The problem seems to lie in the
fact that hops closest to the requesting node along reverse routes times
out before hops further away, creating stale hops which no longer are
part of a complete route. The way it probably should work is that those
reverse hops created last will also time out first (or at least at the
same time), like LIFO (Last In First Out ;-)).

/Erik

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 01 Nov 2001 11:26:02 -0800

Hello Erik,

Thanks for your help in identifying these issues so that
I can make the appropriate clarifications for draft ...-09
which is now ust waiting for the conclusion of the
discussion with you and Dan Iregren

Erik Nordström wrote:

> Active routes
> =============
> First, there are some inconsistencies about what an ACTIVE route is:
> 
> In section 3. an active route is a routing entry with finite hop count.
> 
> Meanwhile, section 8.8. implies that an ACTIVE route (or next hop) is a
> route where packets has been forwarded within the last
> ACTIVE_ROUTE_TIMEOUT milliseconds.
> 
> This may seem like a trivial point since most routes fulfill both
> definitions most of the times. But if you use hello messages, a next hop
> may not have forwarded any data packets at all, but being ACTIVE
> according to the AODV terminology in section 3.

I reckon this is a solvable problem in terminology, but I am
not so sure if I can see the right solution just now.

On the one hand, routes to neighbors may (terminologically)
be inactive, simply because they aren't being used.  On the
other hand, it makes sense to keep the one-hop routes to all
neighbors in the routing table, because the information is
current and potentially useful.  In fact, it would be silly
to make a RREQ for a node that just sent you a HELLO message.

So, perhaps we ought to make the specfication allow for routes to
be maintained in the route table even for inactive destinations.
Then I just have to comb the specification to make sure it remains
consistent with this new premise.

Before I do that, what do you think?

> Section 8.9. in turn say that a RERR should be initiated whenever a link
> break occurs for a next hop of an active route. If detected by the
> absence of hello messages, we may send a RERR for a route/destination
> which no one use, and that seems a bit unnecessary. One way to prevent
> this would be to check if you actually have any precursors for that
> route. If not, don't send a RERR.

The specification already requires that a node only issue a RERR
for destinations that have nonempty precursor lists, so I think this
is O.K.

> Broadcast address
> =================
> Also, why is a broadcast address of 255.255.255.255 used with AODV? This
> is generally just used for protocols such as bootp, because the proper
> broadcast address is not known during boot. Is it used to be able to
> reach hosts that don't share the same type of network address?

There aren't too many choices.

1. A new multicast address.  This is being done for AODV for IPv6, which
   is ready for submission after some internal review and proofreading.
2. 255.255.255.255
3. Directed Broadcast -- but this seems like a clear candidate for
   rejection.

Since AODV has already essentially passed working group Last Call,
I have been reluctant to make protocol changes so that we can make
the most focused responses to IESG comments that have been received.
I think that (2) is a good choice for IPv4, because it has the right
semantics that cause each node to do processing before actually
retransmitting the RREQ.  That's what we need.

> The problem with the 255.255.255.255 address is that depending on OS, it
> may broadcast on all network interfaces or just the first one. On Linux
> for example, it only broadcasts on the first interface. This prevents me
> from running AODV on my computer at home, where my WaveLAN card is on
> eth1. Even if it would broadcasts on all interfaces, I might not want
> that, if my other interfaces are not connected to a "AODV network".

There is a section on "Interfaces".  I have added some text to this
section specifying that the network interfaces should be configured to
support AODV operation.  Then the broadcast packet SHOULD NOT be issued
over those interfaces which do not support AODV.  Do you think this is
a good solution?

> Liftime of routes
> =================
> When intermediate nodes send route replies to a requesting node, it may
> send a ridiculously small lifetime for that route (expire time - current
> time) depending on situation, i.e. route is about to expire. Is this
> something you want? I could imagine that links along the forward route
> that are setup while the RREP makes it back to the requesting node may
> expire almost instantly so that the forward route doesn't exists anymore
> once it is about to be used. We have experienced issues we believe are
> related to this when testing our implementation, though I can't for sure
> say that it wasn't due to other bugs ;-). As a temporary solution we
> tried to always send back ACTIVE_ROUTE_TIMEOUT and that seemed to solve
> the problem.
> I almost assume I am missing something here... Could someone clearify
> this for me?

No, I think you have interpreted this correctly.  It would be possible
to update the specification to make ACTIVE_ROUTE_TIMEOUT the minimum
returnable value, but that would probably lead to other problems.
Maybe we should allow for some one-time "extension" of the route
lifetime in the case you mention, for some increment on the order
of NET_TRAVERSAL_TIME for instance.  However, we should allow this
increment to be applied to a route repeatedly, even for RREQs from
other sources or the same source.

How bad of a problem is it?  I'd be surprised if  this was a frequently
occuring problem.  Did you try larger values of ACTIVE_ROUTE_TIMEOUT?

More later...

Regards,
Charlie P.

---

From: Erik Nordström <[email-masked]>
Date: 02 Nov 2001 12:23:54 +0100

Hello again,

comments inlined.

> to make a RREQ for a node that just sent you a HELLO message.

I was assuming that this would be the normal operation, i.e. keep
neighbors in routing table. Since HELLO's are RREP's I assumed they
would be processed in a similar way, i.e. create a forward route entry.
Yes, it is useful information. If you get a HELLO from a neighbor it
would be, as you put it, silly to not use it to answer a RREQ. It would
be a way to reduce the overhead of hello messages, since the the RREQ
doesn't have to be forwarded all the way to the destination.

> be maintained in the route table even for inactive destinations.

If keeping the ("inactive"/non-used) one-hop routes to all neighbors in
the routing table wasn't the intended behavior, I don't see the point of
regularly broadcasting HELLO's. Then HELLO's would only be necessary
once a route has been setup, right? 

> Before I do that, what do you think?

I would prefer this behavior, but I can't really say right now if this
would bring unwanted problems. For now I am writing our implementation
to work this way.
> for destinations that have nonempty precursor lists, so I think this

Hmmm, not sure about this. As I see it, in section 8.9, checking the
precursor list for non-emptiness is _only_ done for case iii), i.e. for
"re-broadcasts" of received RERR's. Case (i) relies on the definition of
activeness as a "used" route and therefore a check of precursors would
not be necessary, since it would by definition have at least one
precursor. But this may not be true for neighbors added from hello
msg's, as seen by the discussion above.

>    is ready for submission after some internal review and proofreading.

The problem is, how do I force a broadcast to 255.255.255.255 on
interfaces that are not the first one if I use an OS that doesn't
broadcast on all interfaces? This may seem like an implementation issue,
but the specifications of broadcast addresses take no stand in this
issue, so OS's may do what they want. Therefore, it seems strange to
rely on a broadcast address which are not treated the same way on
different OS's. This means that I cannot run AODV on Linux unless I only
run it on the primary interface.

> over those interfaces which do not support AODV.  Do you think this is

I can't think of another solution, so I guess this makes sense for
preventing broadcasts on interfaces which doesn't run AODV.

> returnable value, but that would probably lead to other problems.

I guess a problem of always sending ACTIVE_ROUTE_TIMEOUT back is that 
the hops between the intermediate node and the destination to where the
RREQ won't be broadcasted could potentially timeout before any data
packets makes it there.

Actually, I don't really see the point of sending back a lifetime of a
route at all. Intuitively, I think that if an intermediate node responds
to a RREQ, it doesn't send a RREP if its route to the destination has a
lifetime less than a certain sane value. Instead it proceeds as if it
didn't have a route. Or it sends a RREP to the source and a gratuitous
RREP (or something) to the destination to keep that route alive. The
nodes along the path that the RREP traverses just use a predefined fixed
value for their hops, maybe adjusting it using the hopcount, so that
forward routes created earlier along the reply path do not timeout
first.

I think I may have missed the point of the LIFETIME field in the RREP
entirely. If my suggestion above seem completely insane, could someone
please explain to me why we need to send back the lifetime of a route?

> occuring problem.  Did you try larger values of ACTIVE_ROUTE_TIMEOUT?

We haven't done extensive testings yet, since we are still in a kind of
early development stage, so we don't know the frequency of it ocurring.
Anyway I don't think this should matter, it shouldn't be allowed to
happen if it can be avoided.

And no, we didn't try larger values than ACTIVE_ROUTE_TIMEOUT. What
would you expect to happen if we did?

/Erik