Subject: AODV v.9 draft issues

From: Erik Nordström <[email-masked]>
Date: 14 Nov 2001 22:06:08 +0100

Hi

I have been browsing through the new AODV draft and have some findings I
would like to report and get comments on.

RERR's
======
Section 8.11 about RERR messages has been updated since version 8, but I
now find it a bit confusing, especially how to interpret the actions for
"affected destinations" (a)-(g). These actions are to be performed for
each affected destination, which, following action (e), makes it seem as
if one RERR should be sent for each affected destination. The steps are
often ambiguous, like step (d) which for every unreachable destination
checks the precursor list for each unreachable destination for
emptiness, which would clearly be unnecessary work.

Hello messages
==============
When using hello messages, why do the draft imply having separate
timeouts for receiving hello messages and for route expiry? I mean, when
we use hello messages it seems intuitive to only base neighbor route
expiry on hello messages, i.e. we only update the lifetime of the route
when receiving a message (a hello or other type) from a neighbor. We
then update the lifetime with ALLOWED_HELLO_LOSS * HELLO_INTERVAL not
with ACTIVE_ROUTE_TIMEOUT as specified in the draft.
ACTIVE_ROUTE_TIMEOUT is (per default) larger than ALLOWED_HELLO_LOSS *
HELLO_INTERVAL, so it will not timeout before the latter anyway, making
it meaningless. Why would a neighbor route expire when we still receive
hello messages anyway?

For implementations this means (as described in section 8.9) that you
would intuitively keep one hello timer for each neighbor alongside a
timer for each corresponding route entry, instead of just keeping one
route expire timer, which you update with ALLOWED_HELLO_LOSS *
HELLO_INTERVAL when receiving a message from the neighbor. Note that
this would only apply for neighbors, i.e. hop count = 1.

The draft also says that a route should have its lifetime increased with
ACTIVE_ROUTE_TIMEOUT each time a data packet is sent on it. This is
unnecessary for neighbor routes when using hello messages, following the
discussion above. And when basing route expiry for neighbors solely on
hello messages this is bad, since a route may then be kept from expiring
after we stop receiving hello messages, as long as data is sent on the
route.

Do I make sense here?

Any comments or explanations are welcome.

Regards,

Erik Nordström

---

From: Charlie Perkins <[email-masked]>
Date: Wed, 14 Nov 2001 22:04:21 -0800

Hello Erik,

> emptiness, which would clearly be unnecessary work.

I see your point.  This wording should be made more clear.
It doesn't make the protocol wrong, and it could be interpreted
by a good programmer to do it the less expensive way, but a
literal reading seems to suggest doing it the more expensive way.
I'm hoping that this version will make it through the IESG, and
then this change is so small that I might be able to fix it on the
way to the RFC editor's desk.  Otherwise, it would be fixed in
another revision according to IESG suggestions anyway.

> Hello messages

Isn't that a separate timeout?  This is the behavior that we wanted to
specify.
I hope it is what is in there now.

> hello messages anyway

Well you would not.  But it was pointed out in previous discussion that
receiving
HELLO messages was not mandated to cause a route to be considered active,
and other language in the draft caused routes that were not "active" to be
expired.
The current wording was intended to clarify the behavior to conform to
expectation
under all interpretations.  As you point out, this behavior is clearly
intended anyway,
and the point was to make the draft say so very clearly.

> this would only apply for neighbors, i.e. hop count = 1.

I would think that the route table entries have an expiration time, and that

you can manage expiries in a number of ways, some of which require more
timeouts than other ways.

> after we stop receiving hello messages, as long as data is sent on the

You are correct, but I think that the specification is correct as it stands.

We could make yet another classification for neighbor routes, but often
the neighbors are just next hops, not destinations, and so maybe it
isn't so important to make the distinction.

Disclaimer: if these comments don't make sense, blame the viruses
going around...

Regards,
Charlie P.

---

From: Manel Guerrero Zapata <[email-masked]>
Date: Thu, 15 Nov 2001 16:32:12 +0200

Hi everybody :)

I thing that now that we have a new and fresh draft version (v9)
it is easier to discuss about it. So I'm gonna give my comments
on what I thing about it.

HOP COUNT
=========

It is a good thing that most of the errors concerning to hop count
that were in v8 have been corrected. Still there is one that has not:

8.6.3 Generating Gratuitous RREPs
	Instead of:
	"Hop Count  The Hop Count as received in the RREQ"
	It should be:
	"Hop Count  The Hop Count as received in the RREQ plus one"

Why should it be 'plus one'? Follow me to the section 8.5:

8.5. Processing and Forwarding Route Requests
	At the begining of the section we don't have anything like:
	"When a node receives a RREQ message, it first increments the
	hop count value in the RREQ by one, to account for the new hop
	through the intermediate node." (like it is done for RREP in
	section 8.7). Which is nothig bad. But then, this is why all
	the time we have to use the hop count plus one:
	- "(ii)      the sequence numbers are equal, but the hop count
	as specified by the RREQ, plus one, is now smaller than the
        existing hop count in the routing table."
	- "3. the hop count is copied from the Hop Count in the RREQ
	message and incremented by one;"

	Now that we rebroadcast the RREQ we finaly say it:
	- "The Hop Count field in the broadcast RREQ message is
	incremented by one, to account for the new hop through the
	intermediate node."

	But then, in '8.6.3. Generating Gratuitous RREPs', says:
	"Hop Count  The Hop Count as received in the RREQ"
	
	But, it should be:
	"Hop Count  The Hop Count as received in the RREQ plus one"
	(otherwise we don't account for this hop)
	It is wrong because, the hop count in the G-RREP will be
	one less that what it should be.

PRECURSOR LISTS
===============

The following is something I commented to Elizabeth in the mailing list,
and that she agreed that should be corrected. But, somehow it
didn't make it to the draft. (Now I'm also adding a way of how to add
everybody in a precursor list).

Let me first stress the importance of the problem:

Without fixing it, route error recovery will only recover less
than the half of the routes that it should recover !
Therefore, route error recovery is broken without this fix!

Now, let's look again to the problem. Let's jump to the section 8.7:

8.7. Forwarding Route Replies
	(Paragraph 4)
	"When any node generates or forwards a RREP, the precursor list
	for the corresponding destination node is updated by adding to
	it the next hop node to which the RREP is forwarded. [...]"

	But there is nothing like that for Gratuitous RREPs or for RREQs.
	So the error recovery system that AODV has now will never work with
	routes that where created as reverse routes or by a G-RREP. The nodes
	will never forward RERRs.

	I think there should be something like this in the section
	'8.6.3. Generating Gratuitous RREPs':

	   When any node generates or forwards a _Gratuitous_ RREP, the
	   precursor list for the corresponding _source_ node is updated
	   by adding to it the next hop node to which the RREP is forwarded.

	And something like this in the section
	'8.5. Processing and Forwarding Route Requests':

	   When any node generates or forwards a _RREQ_, the precursor list
	   for the corresponding _source_ node is updated by adding to it
	   the next hop nodes to which the _RREQ_ is forwarded.

	   But the RREQ is forwarded to everybody. So precursor lists
	   should be as they used to be but with the 'everybody' flag.
	   When I want to add everybody in a precursor list, I clear
	   the list and set the flag. When I want to chech if somebody
	   is in a precursor list, I first check the flag and if it is
	   not set I search in the list. When I want to empty the list,
	   I clear the flag and empty the list.

RERR
====

I agree with Erik in that RERR in v9 is 'a bit confusing'.
Besides the issue that he points out (that has already been replied
by Charlie) I would like to comment some other issues:

6. Route Error (RERR) Message Format
	"Unreachable Destination Sequence Number
	          The last known sequence number, incremented by one,
	          of the destination listed in the previous Unreachable
	          Destination IP Address field."
	-> In the case of 8.11 (ii) the sequence number has
	already been incremented because it is not an active route
	anymore.

8.11. Route Error Message
	Paragraph 2:	"For cases (i) and (ii), for each unreachable
		destination the node copies the value in the Hop Count route
		table field into the Last Hop Count field, and marks the Hop
		Count for this destination as infinity, and thus invalidates
		the route."

	-> It should be only for the case (i).
	For the case (ii) there is only one unreachable destination and
	it is not an active route (so it has already been invalidated,
	so let's not do all this again).

	(a):	"updates the corresponding destination sequence number(s)
                with the Destination Sequence Number(s) in the packet"

	-> That only happens for (iii). Because there is no packet in (i).

BROADCASTING
============

The following, is my proposal to make AODV to work in multi-interface,
multi-routing-protocol scenarios:

3. AODV Terminology
        "Broadcasting means transmitting to the IP Limited Broadcast
        address, 255.255.255.255.  A broadcast packet may not be
        blindly forwarded, but broadcasting is useful to enable
        flooding."

	NOTE:	IMHO, it shouldn't be mandatory to use this address. I would
	propose to use a much more flexible option: "transmitting it to the
	broadcast addresses corresponding to all the connected addresses to all
	the AODV interfaces." And then define AODV interface as a "network
	interface that send and processes AODV messages". Otherwise the
	protocol is forcing that the hosts will play only one routing protocol
	or that some AODV messages will arrive to non AODV nodes; and that all
	the interfaces in an AODV host process AODV messages.

SEQUENCE NUMBERS
================

I've been working in trying to make secure AODV (though an extension of
the protocol) for a while. And, IMHO,
the latest changes of how sequence numbers are managed in v9 have made
completely impossible for anybody to secure the protocol with anything
that
will not be based in symetric cryptography (only suitable for military
and similar scenarios). Because it lets anybody to say to us
what is our destination sequence number. Therefore, any aproach to
secure
AODV by using certificates has been baned.

The draft says:

8.1. Maintaining Sequence Numbers
	NOTE:	"Immediately before a destination node orginates a RREP in
		response to a RREQ, it MUST update its own sequence number to
		the maximum of its current sequence number and the destination
		sequence number in the RREQ packet."

8.6.1. Route Reply Generation by the Destination
	NOTE:	(Paragraph 1) 
		"If the generating node is the destination itself, it MUST
		update its own sequence number to the maximum of its current
		sequence number and the destination sequence number in the RREQ
		packet."

8.9. Hello Messages
	Paragraph 1:	Destination Sequence number is set like in 8.6.1

8.11. Route Error Message
	(a):	"updates the corresponding destination sequence number(s)
                with the Destination Sequence Number(s) in the packet"

But, if the only reason to do this is to solve the problem that happens
when a node reboots and does not remember its own sequence number,
that can be easily solved by just storing its value in a non-volatile
place (like a hard drive).

Let me propose a solution to this situation:

* Every time you modify your sequence number, you store it somewhere.
* When you reboot you read the value, and start to operate

	- Who wants to wait for DELETE_PERIOD (15 seconds) !!!

* You increment your own sequence number in the following situations:
	- Before generating a RREP (being you the final destination)
	- Before sending a Hello (this can be considered as a specific
		case of the previos situation)
	- Before originating a RREQ flood (as it is said in 8.1)
* You don't update your destination sequence number believing in what
	others say. You _know_ which is your sequence number.

THE END
=======

Am I missing something?
Anyway, that was all. Please, don't hesitate to send comments back.
If you don't agree with something I say in this mail,
then just reply back and let's discuss about it.

Regards,

	Manel Guerrero

P.D.: If you have read the whole mail, you deserve a break. ;)

---

From: Manel Guerrero Zapata <[email-masked]>
Date: Thu, 15 Nov 2001 18:12:53 +0200

Hi,

BTW, what happened with all the dicussion about dsn in rerr processing?

In 8.11 says:

         (a):    "updates the corresponding destination sequence
number(s)
                 with the Destination Sequence Number(s) in the packet"

If we just update the dsn that is in the packet we might end up
invalidating
a route for which we already have a newer route.

Shouldn't we compare the dsn in the packet with the dsn in our routing
table?

Am I missing something?

BR/Manel Guerrero

---

From: Erik Nordström <[email-masked]>
Date: 15 Nov 2001 20:51:03 +0100

Hello,

here are my contribution to the discussion... Comments inlined.

> Why should it be 'plus one'? Follow me to the section 8.5:

I have discovered this problem too, so I agree... Actually there are
several places in the draft where the value of hopcounts used are a bit
unclear.

> 	section 8.7).
I would prefer this was the case, i.e. have the RREQ hopcount
incremented upon reception of the RREQ. There may be a problem with
calculating the MinimalLifeTime though. I assume this formula should use
the non-incremented hop count? But it could explicitly say that it
should use the non-incremented value if that is the case.

 Which is nothig bad. But then, this is why all
> 	one less that what it should be.

I agree, as stated above...

> PRECURSOR LISTS
Ok, this may clearify things, but since Gratuitous RREP's are just
RREP's they are treated the same as "regular" RREP's and therefore adds
the proper precursors, right? So there is really nothing wrong with the
draft here, or am I missing your point?

> 	   I clear the flag and empty the list.

To avoid having all neighbors as precursors, wouldn't it be possible to
add precursors for both the reverse route and the forward route whenever
a node is forwarding a RREP. This is what an intermediate node does when
it responds to a RREQ. Are there any problems with this solution I
haven't thought of? 

> 	-> That only happens for (iii). Because there is no packet in (i).
I was also very confused about which packet the draft was referring to
here. Also following a-g by the letter makes (g) only be performed for
the first affected destination. For the next unreachable destination we
will only do a-d, because then, all precursor lists for all affected
destinations are empty, following the first execution of (g). Is this
intended? I really think this section needs a thorough overhaul to avoid
any confusion.

Regards,

Erik Nordström

---

From: Manel Guerrero Zapata <[email-masked]>
Date: Fri, 16 Nov 2001 12:03:26 +0200

Hi Erik,

See comments.

> should use the non-incremented value if that is the case.

Well, concerning to the minimal lifetime. I thing is pretty useless.
Now, it can be claimed that in the theoretical world (where the
time that takes to a packet to go though a hop (NODE_TRANSVERSAL_TIME)
is constant for all the nodes during all the time, and where you do
know its value) it will work better than in v8. But let's face it,
in the real world this does not happen. So same kind of problems
that the minimal lifetime tries to solve will keep on happening,
with the difference that now nobody is going to try to find a solution
to it because of the 
"Hey-guys,-we-already-solved-that-with-minimal-lifetime" problem.

> >          by adding to it the next hop node to which the RREP is
Sorry, it should (of course) be:
             by adding to it the next hop node to which the G-RREP is

> >          forwarded.

No. Yes. If you look again two the two paragraphs you will see that
you don't do the same for a RREP than for a G-RREP:

Packet	| precursor list	
--------+----------------
RREP	| destination node
G-RREP	| _source_ node	

> it responds to a RREQ. Are there any problems with this solution I

Yes.
1) You are (implicitelly) assuming that all links are bidirectional.
2) Although reverse routes have a short lifetime. It might happen that
one
of those routes ends up being used for somebody else (and being
refreshed)
and it would not be in any precursor list.

BR/Manel Guerrero

---

From: "Samir R. Das" <[email-masked]>
Date: Mon, 19 Nov 2001 12:05:21 -0500

Hi Manel,

In some rare occasions the dsn carried by the RERR may be lower than the dsn
on an upstream route. This is possible when the RERR is very slow to
propagate -- slow enough to give the route other chances to get
reconstructed, for example. This, however, does not cause any looping, but
can invalidate a valid route and cause a new route discovery.

The only reason we didn't compare dsns carried by RERRs is that instituting
this will need some additional techniques to special case nodes that
rebooted recently. Such nodes have lost the dsns. So, we need additional
protocol components for them to learn the dsns back, for example. Or, may be
special case certain dsn values to indicate rebooted nodes, or introduce
incarnation numbers to be kept in non-volatile memory, or some such thing.

So, it boils down to an engineering tradeoff. Do we really need additional
protocol components to save some overhead in rare occasions? Do you really
think that the above would be frequent? Note also that AODV invalidates
valid routes in some other (rare IMO) occasions as well.

Samir

>-----Original Message-----
>From: [email-masked]
>[mailto:[email-masked]]On Behalf Of Manel Guerrero
>Zapata
>Sent: Thursday, November 15, 2001 11:13 AM
>To: Perkins Charles (IPRG); Erik Nordström; ext Elizabeth M.
>Belding-Royer; ext Samir R. Das
>Cc: [email-masked]
>Subject: My comments on AODV v.9 (II)
>
>
>Hi,
>
>

---

From: Manel Guerrero Zapata <[email-masked]>
Date: Tue, 20 Nov 2001 17:47:09 +0200

Hi Samir,

> rebooted recently. Such nodes have lost the dsns. So, we need additional

-----> Let's look at this carefully:

If a node reboots, it is not that it losts the dsns for the AODV routes.
It losts all the AODV routes.
And concerning to your own dsn: _store it_, so when you reboot
you always know its former value.
And then, you don't have to do nothing especial because a node just
reboot.

Don't patch the protocol (making compulsory that other nodes might
tell you which is your own dsn, and making wait a node 15 secs
after reboot) just because you are trying to solve
a problem that does not exist (or has a trivial solution).

Regards,

	Manel