Subject: Flooding & Hidden Terminal?

From: Chip Elliott <[email-masked]>
Date: Mon, 14 Sep 1998 12:28:47 -0400

I've been thinking about flooding schemes and the hidden
terminal problem, and hope that someone (CMU?) can enlighten me.

Imagine a large network using flooding as part of its path-building
activities. I expect that flooding would be accomplished via radio
level broadcasts; to be concrete, let's say 802.11 broadcasts.

Now it seems to me that such floods would suffer quite a bit
from hidden terminal problems, since the transmissions would be
highly synchronized -- a number of nodes will be transmitting
at virtually the same time -- and broadcasts are not protected
from hidden terminal problems. Hence it seems conceivable that
the actual completion rate on these flood searches might be
quite low... ie, a large fraction of the requests will be
damaged in transmission and hence have no effect.

CMU folks, have you noticed any such effects in your simulations?
If not, why not -- ie, what part of my thought experiments are wrong?

Many thanks!

-- Chip

---

From: Vishal Kothari <[email-masked]>
Date: Tue, 15 Sep 1998 10:27:08 -0400 (EDT)

Hello all,

Just wondering if any one of you has any references/models which allows 
one to determine the upper bound (in terms of time/computational 
complexity) as well as delay bounds for dynamic, mobile networks.

Thank you

Vishal Kothari
Wireless Communications
University of Toronto

---

From: Dave Johnson <[email-masked]>
Date: Wed, 16 Sep 1998 02:30:47 -0400

>If not, why not -- ie, what part of my thought experiments are wrong?

Chip,

We have indeed seen problems in our simulations with broadcasts,
although the problem is certainly not unique to any use of flooding.
Essentially all MANET routing protocols use broadcast (radio level,
which means physical and link level) somewhere in the protocol.  As
you point out, some protocols use it for a path-building-type algorithm,
although most also use it for some form of neighbor node discovery
or link status sensing mechanism.  The inherent unrealiability of
broadcasts affects both types of uses of broadcast packets.

In fact, we have a section in our upcoming MobiCom'98 paper (A
Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing
Protocols) about this very topic.  Here is a quote from the paper:
"Upon sampling a number of our scenarios, we found that over any
single hop, 99.8% of unicast data packets are received successfully,
while only 92.6% of broadcast packets are received, based on counting
the number of receivers within transmission range of the broadcasting
node."

In our simulations of each routing protocol, we tried to avoid the
synchronization effect you mentioned, by adding a slight randon delay
in the time at which periodic broadcast packets are sent by any node,
as well as a slight random delay before sending a packet in response
to receiving a broadcast packet.  We jittered the time at which such
packets are sent using a random delay uniformly distributed between 0
and 10 milliseconds.  The loss rate for broadcast packets above is what
we ended up with even after this randomization.

A complete copy of our MobiCom paper is available from our web pages
at http://www.monarch.cs.cmu.edu/.  MobiCom'98, where the paper will
be presented, is being held Oct 25-30 in Dallas, Texas.  For more
information on MobiCom'98, see http://www.mobicom98.utdallas.edu/.

					Dave

---

From: Erik Nordmark <[email-masked]>
Date: Wed, 16 Sep 1998 12:03:42 -0700 (PDT)

> we ended up with even after this randomization.

The reference paper "The synchronization of periodic routing messages"
available at http://ftp.ee.lbl.gov/nrg-papers.html
says that for periodic messages of period N the randomization 
has to be over the range .5N and 1.5N to avoid synchronization over time.
Thus 10ms sounds low for the jitter of the periodic messages.

   Erik

---

From: Dave Johnson <[email-masked]>
Date: Fri, 18 Sep 1998 00:41:57 -0400

>Thus 10ms sounds low for the jitter of the periodic messages.

Yes, I'm familiar with that paper, and you are probably right, in
general, Erik.  However, none of the protocols we simulated had
specified by their designers any jitter at all in their periodic
broadcasts, and we wanted to try to avoid too much becoming designers
of each of the other protocols (our protocol, DSR, doesn't use any
periodic broadcasts at all).  Changing the periodic broadcast time
from N to instead varying between .5N and 1.5N could have the effect
of at times increasing the number of broadcasts sent and thus locally
increasing overhead, or at other times, delaying broadcasts and thus
not noticing some changed routes as quickly.  If the jitter was truly
random, this shouldn't have been a problem on average, but since no
jitter was specified by the protocols' designers, we kept our jitter
small to avoid any such effects.  The moderate jitter we added seems
to have still helped and avoided at least the worst cases of
synchronized broadcasts.

					Dave

---

From: Joe Macker <[email-masked]>
Date: Fri, 18 Sep 1998 14:05:19 -0400

>the number of receivers within transmission range of the broadcasting

Dave:

Any comments/observations relating to the resultant effect of traffic
distribution scenarios and saturation in your above percentages?  <e.g.,
percentage of distributed sources producing flooded packets,  flooding
under congested or near congested conditions, etc.>

-joe

Joseph P. Macker
Information Technology Division
Naval Research Laboratory
+1-202-767-2001
[email-masked]
http://tonnant.itd.nrl.navy.mil/macker.html

---

From: Jose Garcia-Luna <[email-masked]>
Date: Fri, 18 Sep 1998 16:24:12 -0700

Joe:

This has little to do with DAve's paper, and is a bunch of
observations prompted by your email and Chip's (it's also a late
Friday afternoon, so bear that in mind :-)

Least-interference paths and smallest-delay paths need not be the
smallest hop count paths. If traffic and interference patterns
fluctuate, incremental routing delivers packets over "shorter" routes
than a source routing, where "shortest path" does not mean smallest
number of hops, but any or a combinatioin of delay, least
interference, etc.....so what we may argue?.....

Well, the problem is that: source routing delivers pkts w/o loops but
along paths that can be inefficient (very inefficient, actually), and
incremental routing delivers pkts along efficient (or as efficient as
routing table info permits) but pkts may loop. Furthermore, if we do
want to get close to optimum paths with incremental routing, we must
use multiple paths to the same destination with "distances" that can
be different (just as Gallager's min-delay routing algorithm
requires). Allowing multiple next-hops along paths of unequal cost is
not an easy task, and is one reason why OSPF uses paths of same
cost....but don't get me started on OSPF :-)

If we want the routing to be "efficient" under traffic and
interference fluctuations, we cannot do routing as the Internet does
(paths areindependent of traffic over them) and we have an
"interesting" problem at hand, no matter which type of routing we
choose!

With source routing, we will need multiple source QoS routes, a flow
allocation heuristic to use the "best" source route for each packet a
node forwards to a destination, and a QoS monitoring scheme that
changes the "relative weights" of the paths used. 

With incremental routing, we need multiple next hops along loop-free
paths (of unequal "cost") to each destination, a flow allocation
heuristic to chose the next hop for each pkt sent, and a QoS
monitoring scheme.

Delays in setting weights used in flow alloation, and in distributing
long-term path ifnormation will increase pkt delays (or whatever QoS
metric we choose to say that the routing is efficient).

For MANET routing, we need the ability to specify "path metrics" or
"link-cost metrics" that permit routers to compute QoS paths to
destinations and forward packets incrementally or source routed. Once
that is a given we need the flow allocation heuristic to distribute
packets to source routes or next hops.

I'd like to reach some consensus on what is a MANET acceptable
characterization of a QoS path and the associated link
parameters.....I am working on the problem and am eager to use good
ideas from anyone, specially from this list!

I also see an inevitable tradeoff between efficiency of QoS routing
and the desire to reduce the amount of routing information updated at
routers (a.k.a. on-demand routing). By the time a flood search comes
back to the source and provides a set of QoS source routes to a
destination, the traffic patterns have changed around the destination
and the paths are not as efficient. The table-driven routing approach,
in which routers update routing info continuously is the other
extreme, it provides the fastest way to adapt but costs us routing
traffic, which we may also equate to reducing the optimality of paths
(at least to soem degree).

Finally, if in fact the paths used are correlated to congestion (or
delay or interference), we can mount nice attacks on the routing
protocols, particulalry those using simple flooding (flood searches or
link-state flooding). By forcing flooding we degrade net performance.

....My only immediate conclusion to theabove is that, as I said, it is
Friday and is late, so is time to go home :-)

JJ

---------------

---

From: "M. Scott Corson" <[email-masked]>
Date: Sat, 19 Sep 1998 16:26:37 -0400 (EDT)

> If not, why not -- ie, what part of my thought experiments are wrong?

I guess I'm echoing some of Joe's thoughts, but it seems that 
any heavily-loaded network (read "congested" as some envisioned MANETs
will be) will suffer from HT problems using 802.11.  The "problem"
is less with flooding (it's simply a network-level traffic pattern)
and more with less-than-ideal MAC layers and slow radios.
Flooding is expensive and should be used sparingly, but it has 
legitimate uses.

In the near term, it may be that flooding is the only way to create
congestion in some otherwise lightly-loaded networks, thereby exposing 
otherwise hidden weaknesses of the link layer.  If the far term, as MAC
and radio technology improve (this will happen...right ;-),
flooding will become less of an issue, simply contributing 
a fraction of the overall network load.

Question: Has anyone simulated a fully-loaded 802.11 multihop network
          to measure performance in terms of supporting one-hop
          unicast and broadcast reliability?  JJ...have you done
          so with FAMA, and cross-compared with 802.11 under
          fully-loaded conditions?

-Scott

*******************************************************************************

M. Scott Corson                                 Institute for Systems Research
[email-masked]                              A.V. Williams Bldg. (115)
Phone: 301-405-6630 (Rm. 2205 AVW)              University of Maryland     
Fax:   301-314-8586                             College Park, MD  20742

*******************************************************************************