Subject: [manet] AODV v11: Ratelimit of control messages

From: Erik Nordström <[email-masked]>
Date: 02 Sep 2002 11:06:03 +0200

Hi

I am in the process of updating my AODV implementation (AODV-UU) to
conformance with the AODV draft v11. Having gone through most of the
changes in the new draft, there are still a couple of things that I find
strange, and would like the help of the list to understand.

AODV draft 11 introduces rate limiting of control messages. Specifically
for RREQs, a node should not generate more than RREQ_RATELIMIT RREQs per
second. I cannot make any sense of this, since RREQs should already be
rate limited by, for example, the expanding ring search algorithm.

In a similar way RERRs are rate limited. A node should not generate more
than RERR_RATELIMIT messages per second. However, since each RERR
message is unique by its combination of destination (i.e. the node(s)
that are supposed to receive the message) and the list of unreachable
destinations in the RERR message, I can not see how this is supposed to
be implemented. It is very difficult to rate limit messages on a per
unique message basis (lots of state must be kept). And to blindly limit
all types of RERRs by RERR_RATELIMIT  per second seems just wrong since
that would possibly hinder some important RERRs to ever being sent...

Comments?

Erik Nordström, 

Uppsala University, Sweden.

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 04 Sep 2002 10:11:13 -0700

Hello Erik,

I may nnot recall all the reasons for the rate limitation, but
I think that the actual discussion occurred early in the year,
just after the Minneapolis IETF.

For RERR, one reason is clear.  A node will generate RERR if
it does not have a route to the destination.  If a bidirectional
link goes unidirectional, then a previous hop can send a lot
of data packets and never hear the RERR.  The previous hop will
assume that the route remains active and continue transmitting
data packets at possibly high rates to be forwarded by the RERR semder.

For RREQ, the reasoning is similar.  Suppose a UDP
application generates a lot of packets, and for some
reason each packet generation would stimulate the Route
Discovery process.  As far as I remember, nothing in the
protocol would prevent the initation of a new Route Discovery
operation (a new RREQ) every time the application generated
another packet.  The rate limitation is sufficient as a
protocol mechanism to prevent this bad result.

There may be other better reasons, but I can't remember
them right now.  Plus, since the behavior is merely "strongly
recommended" instead of "mandated", one can envision creating
systems where the rate limitations are not applicable.  For
instance, if the links are gigabit links and sessions come
and go very rapidly, more RREQ messages may be needed.

Regards,
Charlie P.

Erik Nordstrvm wrote:
> Erik Nordstrvm,

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 04 Sep 2002 10:11:13 -0700

Hello Erik,

Regards,
Charlie P.

---

From: Erik Nordström <[email-masked]>
Date: 04 Sep 2002 19:29:34 +0200

Hi Charlie.

Thanks for the input.

See my comments below.

> just after the Minneapolis IETF.

I do see the point of having a rate limit in some cases, the question is
where? and how and if it can be implemented in a sound way. The thing is
that I really think the rate limiting in the draft is way to
simplistically described to really be useful for an implementor.

> data packets at possibly high rates to be forwarded by the RERR semder.

I see a point in having a rate limit in this scenario, but still the
question is how to implement it. Should we blindly filter all RERRs that
are generated in this fashion? or should we consider who the RERR is
destined for or even what unreachable destinations are in the message?
I.e. for example do a per destination rate limit? See my previous
message for details...

What about a malicious node? A node like that wouldn't care about rate
limiting... This leads me to believe that it only makes sense to
implement this on the forwarding nodes... i.e. we rate limit the RREQs
and RERRs that are forwarded. This will prevent a malicious node from
flooding the network.

> protocol mechanism to prevent this bad result.

This mechanism already exists. If a RREQ is already pending for a
destination (i.e. the expanding ring search has not timed out), there is
no reason to send a new RREQ for that destination even if the
applications wants to... Therefore lots of UDP packets would _not_
stimulate the Route Discovery process, unless it the packets where for
another destination... But in that case we wouldn't wanna kill the RREQ
for that destination, just because another request has filled all the
slots, would we?

Erik

-- 
Erik Nordström <[email-masked]>

---

From: "Luke Klein-Berndt" <[email-masked]>
Date: Wed, 4 Sep 2002 13:35:16 -0400

Hi,
I am a little confused now on the correct behavior for generating RREQs. The
fifth paragraph of section 5.3 of draft 11 says "Data packets waiting for a
route (i.e. waiting for a RREP after a RREQ has been sent) SHOULD be
buffered." For some reason I interpreted this to mean that, if a node sent
out a RREQ for an IP and was waiting for a RREP it would buffer any
additional packets it received for that IP instead of generating new RREQS
for each packet. A new RREQ would only be generated if the current one
failed the Expanding Ring Search rebroadcast. Is this incorrect behavior?
Should each packet be generating a RREQ?

-Luke Klein-Berndt

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Charles E. Perkins
> Sent: Wednesday, September 04, 2002 1:11 PM
> To: Erik Nordström
> Cc: MANET LIST; Luke Klein-Berndt; Elizabeth M.Belding-Royer; Ian
> Chakeres
> Subject: Re: [manet] AODV v11: Ratelimit of control messages
>
>
>
> Hello Erik,
>

---

From: Erik Nordström <[email-masked]>
Date: 04 Sep 2002 19:29:34 +0200

Hi Charlie.

Thanks for the input.

See my comments below.

Erik

---

From: Erik Nordström <[email-masked]>
Date: 04 Sep 2002 19:35:25 +0200

> failed the Expanding Ring Search rebroadcast. Is this incorrect behavior?

The behavior must be correct, it doesn't make sense to send additional
packets (RREQs) if a request is already pending...

Otherwise I have to rewrite my implementation ;-).

Erik

---

From: Erik Nordström <[email-masked]>
Date: 04 Sep 2002 19:35:25 +0200

Erik

---

From: "Luke Klein-Berndt" <[email-masked]>
Date: Wed, 4 Sep 2002 13:35:16 -0400

Hi,

-Luke Klein-Berndt

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 04 Sep 2002 10:45:27 -0700

Hello Luke,

Luke Klein-Berndt wrote:

> I am a little confused now on the correct behavior for generating RREQs.

Actually, I think you understand the issue very well!

>                                                                    The

No, each packet should NOT be generating a RREQ.  I did not at all
mean to suggest that.  I only pointed out that someone else MIGHT
somehow write an application interface that WOULD do that, and the
rate limitation would prevent poor results in the latter case.

If you think that no one could write such an interface between
kernel and application, then maybe the rate limitation would not be
necessary.  Or else maybe I am just not remembering the other reasons.

Regards,
Charlie P.

> > To: Erik Nordstrvm

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 04 Sep 2002 10:45:27 -0700

Hello Luke,

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 04 Sep 2002 10:52:20 -0700

Hello Erik,

> I.e. for example do a per destination rate limit? See my previous

Here the tradeoff is between complexity and usefulness.  One would
have to decide how often the multi-destination scenarios would occur,
and use that information to decide how much code to write to implement
the rate limitation.  Surely, the packet count can be done in a
more precise manner, but that would require yet another array of
IP addresses and associated timers.

> and RERRs that are forwarded. This will prevent a malicious node from

Well, that's true for RERRs almost by definition.  I had a chuckle
thinking about a destination emitting an RERR claiming that it
couldn't reach itself :-)

Your question about RREQ depends on the discussion from Luke's
note, and I certainly don't suggest rewriting your implementation!

Regards,
Charlie P.

---

From: "Charles E. Perkins" <[email-masked]>
Date: Wed, 04 Sep 2002 10:52:20 -0700

Hello Erik,

Regards,
Charlie P.

---

From: Sumeeth Nagaraj <[email-masked]>
Date: Thu, 05 Sep 2002 00:51:37 -0600

----- Original Message -----
From: "Charles E. Perkins" <[email-masked]>
To: "Erik Nordström" <[email-masked]>
Cc: "MANET LIST" <[email-masked]>; "Luke Klein-Berndt"
<[email-masked]>; "Elizabeth M.Belding-Royer"
<[email-masked]>; "Ian Chakeres" <[email-masked]>
Sent: Wednesday, September 04, 2002 11:11 AM
Subject: Re: [manet] AODV v11: Ratelimit of control messages

Hi,

Some comments on RERR messages and Uni-directional links.

> data packets at possibly high rates to be forwarded by the RERR semder.

I think, the previous hop will check the feednback from the MAC layer before
sending packets at a high rate to the RERR sender. Since the RERR can be a
broadcast or a unicast packet, ACK may or may not be sent for the RERR from
which it is not possible to detect Uni-directional links. But I think, In
the above scenario, since the MAC layer does not get any ACK for the packets
sent over uni-directional link to the RERR sender, It can stop sending
packets. In the case of IEEE 802.11, the CTS packets are not heard by the
node sending packet to the RERR sender packet because of Uni-directional
links.

---

From: Sumeeth Nagaraj <[email-masked]>
Date: Thu, 05 Sep 2002 00:51:37 -0600

----- Original Message -----
From: "Charles E. Perkins" <[email-masked]>
To: "Erik Nordström" <[email-masked]>
Cc: "MANET LIST" <[email-masked]>; "Luke Klein-Berndt"

Hi,