Subject: Re: loop in AODV?

From: Dan Iregren <[email-masked]>
Date: Thu, 1 Nov 2001 10:26:22 +0100 (CET)

Hello Charles,

Thanks for your reply.

On Wed, 31 Oct 2001, Charles E. Perkins wrote:
> 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

I have not found anything in the draft that claims that reverse route
should have a shorter lifetime than forward routes.

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

According to the draft AODV is "loop free at all times".
I reckon the changes you propose would lessen the risk of the
situation that I described, however the risk would not be eliminated.

I have developed some other situations where loops occur as well. The
problem in the scenario I described in my previous mail was that packets
(route requests) were dropped.

Another problem is packet reordering. Reordering of route request easily
create loops.
The draft assumes that data packets are buffered in fifo order but no
assumption about packet deliverance is made.
If AODV assumes that control packets are guaranteed to be delivered
in order I think this should be added to the draft.

Yet another problem is related to route lifetimes (as the first one) but
will occur even under perfect conditions (in order deliverance, and
deliverance of all packets). I will try to describe this problem briefly
here.

Consider the three nodes [a], [b] and [c].

	[a] 	[b]	[c]

All routing tables are empty and each node has sequence number 0.
All nodes have the same send range.
[b] is within range of [a] and [c].
[a] does not reach [c] directly and vice versa.

Now,
[a] sends a request asking for [x] (not in the picture).

[b] receives the request, creates a backward route to [a] and forwards the
request.

[c] receives the request, creates a backward route to [a] (nexthop [b])
and forwards the request.

The problem:
[b]'s route towards [a] was created prior to [c]'s route towards [a] and
therefore [b] will deactivate that route before [c] does.
So, there exists a short moment where [c] has a route towards [a] and [b]
does not, during this short moment a request for [a] would create a loop
between [b] and [c]!

No matter how short the unwanted state exists this is still a problem and
loop freedom at all times can not be guaranteed.

Regards,
Dan

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 01 Nov 2001 10:33:04 -0800

Hello Dan,

Here are some at least partial answers.  I am still reading
the e-mails and may develop more complete answers.

You point out that we claim that AODV is always loop free.
In fact, we can construct scenarios involving strange
behavior for the DELETE_PERIOD where this is not true.
It involves making unrealistic differences in the
tick-rate for the clocks, sometimes in conjunction with
scenarios where a link is able to transmit packets in one
direction reliably, but in the other direction only once
out of 50 or 1000 times.  This makes a quandary.  Do we
claim that AODV is "always" loop-free, or "always (under
realistic conditions of clock rate and link asymmetry)
loop-free"?  Maybe the right answer is to have another
section in the draft called "Loop Freedom Considerations".

This is relevant to the current discussion in two ways.
1.  For every protocol error that leads to loops, even
    if only in existence for milliseconds, I and the other
    AODV authors will endeavor to fix the problem.
2.  For loops that only come into existence under conditions
    which we can reasonably postulate will never happen,
    we should identify the conditions and explicitly state
    why we make the decision not to take the (perhaps onerous)
    needed steps to avoid the problem.  For instance, maybe
    _some_ loops could be avoided by time synchronization,
    which we explicitly DO NOT wish to require for AODV.

I hope you will agree that this is a reasonable approach, and
still help us to identify problems that fall into category (1)
above.

> should have a shorter lifetime than forward routes.

I would refer you to the section on parameter values:
        ACTIVE_ROUTE_TIMEOUT        3,000   Milliseconds
                          ..........
        REV_ROUTE_LIFE              NET_TRAVERSAL_TIME
and NET_TRAVERSAL_TIME would typically be a lot less than
3,000 milliseconds.  However, we probably SHOULD mandate
that the parameter values be adjusted to make this true.

> in order I think this should be added to the draft.

We definitely intend that packet reordering SHOULD NOT cause loops.
If you can show the cases where this happens, I would appreciate it.
We intend to rely on monotonically increasing sequence numbers towards
the destination to prevent this.

This was the reason that I made the suggestion:

>    reverse route as the RREQ traverses the network.
                  ...........
>    (current_time  +  REV_ROUTE_LIFE  -  HopCount*NODE_TRAVERSAL_TIME)

Do you see any reason why we should not expect this to solve the problem?

Now, I need to correct a false impression that I gave
in my earlier note.

You wrote, during your description of an error condition:

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

This was fixed in a previous version of the specification
so that [b] _would_ in fact increase the lifetime of the
reverse route towards [d], just as I suggested when I

>    until at least  (current_time  +  REV_ROUTE_LIFE).

Here is the relevant text from section 8.3.1 of the
draft revision '8' of AODV, as submitted last year:

======================================================================

   The node always creates or updates a reverse route to the Source IP
   Address in its routing table.    ..............

   When a reverse route is created or updated, the following actions are
   carried out:                ................

    4. the lifetime of the route is the higher of its current lifetime
       (for an active route) and current time plus REV_ROUTE_LIFE.

======================================================================

I should have checked to be sure whether or not the most recently
available specification already had the remedy before mentioning that
the particular remedy would help.

> (route requests) were dropped.

I suggest that the previous specification means that the RREQs are
not supposed to be dropped, and this substantially reduces the risk.

That's it for now.  I'll get on to the substance of the rest of your
notes and hopefully provide the other answers soon.

Regards,
Charlie P.

=======================================================================

---

From: Dan Iregren <[email-masked]>
Date: Fri, 2 Nov 2001 10:54:44 +0100 (CET)

> the e-mails and may develop more complete answers.

I think your answers have pointed out what had to be covered.

> still help us to identify problems that fall into category (1)

I agree, I thought that "at all times" was a little bold perhaps.

To summarize the discussion about loops, I think that what you have
pointed out prevents loops from occurring in the scenarios I have
described.

Regards,
Dan