Subject: Reflects on AODV

From: Manel Guerrero Zapata <[email-masked]>
Date: Mon, 14 Aug 2000 12:47:55 +0300

Hi everybody :)

I guess there are many persons in this list that are
still jet-lacked (like myself).

Anyway, lately I've been thinking and talking about
different isues AODV related. And maybe you could tell
me if you have any feelings about them.

o One of them is what do you think about the use of
  a jitter in the hello messages.
  I haven't seen a manet protocol with jitter. RIP
  implementations use it and I think it could be
  interesting to consider to use it in AODV.
  For me there are two reasons for using it:
  - It reduces collisions. (So this is only for those
    systems that do not solve collisions with some MAC)
  - It also reduces temporally network congestion dued
    to actuallizations in cascade.

  It is hard to know the best value in each situation,
  but I bet the intuitive value of +/- 50% will do fine.

  I don't know. Maybe there are some good reasons for
  not using jitter in AODV and other manet prots.

o Another thing is what happens if we have a gateway
  between AODV net and wired IP net.
  The metric used in both is hop count. But the real
  thing is that we will prefer to use a 6 hop path in
  wired than a 4 hop path in manet. So maybe a metric
  factor is required. But that means that then metrics
  are gonna be bigger than the hop counts. Think about
  the size of the metric or hop count field in the
  different protocols.
  Any ideas?

Manel Guerrero

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 14 Aug 2000 07:06:59 -0700

Hello Manel,

I don't see any problem with adding some jitter to the hello times.
50% seems a bit excessive, though.  How about 10%?

I also don't see any problem with adding a parameter which is
a multiplicative constant to be used when comparing wired hops
with wireless hops.  However, writing the specification for when
to use it might be tricky, and it isn't exactly an AODV problem.
It might better be viewed in the abstract, as the subject for a
separate Internet Draft.

Regards,
Charlie P.

---

From: Manel Guerrero Zapata <[email-masked]>
Date: Tue, 15 Aug 2000 12:42:27 +0300

Hi Charles :)

Maybe somebody should run some ns-2 simulations
to determine the best jitter (and maybe make some
paper for mobicom'2001 X-D).
Well, probably the best thing is just give it as
a parameter (HELLO_JITTER_PERCENTAGE or whatever).
Of course this jitter thing should be a MAY
(cos maybe the system has a MAC that solves it
or something).

The problem with the metric factor might be that
after aplying the factor the resulting metric does
not fit anymore in the metric field of the routing
protocol you are redistributing to.
But now I think this is not a big deal. First, I
expect it to happen very seldomly. And, second, if
it occurs a strait solution could be to just put it
to the maximum metric the field can store.
In addition if I recall it right RIP metric field
is 32-bit long and OSFP is 16-bit long.
(And when redistributing manet routes to wired tables
are gonna get bigger, and smaller in the other way round)

But, yeah, your probably right. It's not really an AODV
problem.

CU

Manel Guerrero

---

From: Jeff Boleng <[email-masked]>
Date: Wed, 16 Aug 2000 12:23:50 -0600

I have a naive question.  +/- 50% of what?

We have been using a jitter in our geocasting simulation using NS2 in order to reduce collisions of our control
packets.  Our jitter implementation is based on the granularity of the simulator and the 802.11 MAC layer implemented by
CMU.  Currently we use a random jitter between 0.0 and 0.0001 seconds uniformally distributed with a mean of 0.00005. 
This works well for us and has sucessfully stopped the collisions of our control packets.

This does introduce a more subtle issue into our simulations and protocol though.  Packets are now sent in a different
order than they might otherwise have been without the jitter.  Nothing we are doing depends on the scheduling of the
packets, but the network congestion can be reduced if they happen to occur in the expected sequence.  The jitter values
we've been using mean that sometimes two neighboring nodes receive a control packet, process it, and schedule it for
transmission.  The one that generates a lower jitter will send first, which in our case doesn't always generate the most
efficient routes.

A much more general observation though:  it seems to me that this whole issue should be handled at the MAC layer.

Jeff

---

From: Marc Pearlman <[email-masked]>
Date: Wed, 16 Aug 2000 16:53:24 -0400 (EDT)

Hi Jeff,

> We have been using a jitter in our geocasting simulation 
> using NS2 in order to reduce collisions of our control
> packets.  Our jitter implementation is based on the 
> granularity of the simulator and the 802.11 MAC layer
> implemented by CMU.  Currently we use a random jitter 
> between 0.0 and 0.0001 seconds uniformally distributed
> with a mean of 0.00005. This works well for us and has 
> sucessfully stopped the collisions of our control packets.

The proper jitter value should depend on node density (as in
neighbors per node).  What node densities are you working with
in your simulation?  As I recall, the AODV scenarios in ns-2 typically
have relatively large node densities, and thus probably benefit from
larger jitter values.  

Packet length matters too.  How does your packet length compare with AODV?

The "optimal" jitter value should also depend on average traffic
load.  If the channel is found to be busy on the initial transmission
attempt, the MAC's random backoff may effectively provide some of the
jitter that you're looking for.

> A much more general observation though:  
> it seems to me that this whole issue should be handled at the MAC layer.

This could be a fun issue to debate.  :-)

The problem is, not every packet at the MAC layer requires jitter.  Jitter
really should be targetted to those situations where multiple neighbors
are simultaneously attempting a packet transmission (typically in
response to a common neighbor's broadcast).  

Good candidates for jitter might be I-HEAR-YOU responses to HELLO neighbor
broadcasts, bordercast/broadcast ROUTE REQs, multicast data.  On
the other hand, a plain old data unicast probably does not need jitter
(and may be adversely affected by it).  Likewise, HELLO neighbor
broadcasts don't need jitter, as they are triggered independently by each
node.

So, the use of jitter is very context specific.  This is an
issue if you're a proponent of strict protocol layering.  If the higher
layers can't tell the MAC when to (and not to) apply jitter, then they
should probably perform jitter for themselves.

Similar arguments could be made for a reliable neighbor broadcast (NB)
service.  Certainly, the MAC seems like a logical place to offer such a
service.  But not all NBs need to be reliable.  Who (what layer) gets to
choose which NBs should be reliable (and how do they choose)?

It is a bit inconvenient that these services "bubble up" from the
MAC and end up in our routing protocols.  I think it's probably a good
approach to at least extract these services from our routing protocols and
run them beneath the routing protocol (similar to the TORA/IMEP
approach).  Based on the last two MANET meetings, I think this protocol +
underlying services approach is where we are heading.

regards,

Marc