Subject: RE: flooding

From: Alan Amis <[email-masked]>
Date: Fri, 2 Jun 2000 10:06:54 -0400

Hi Dmitri,

Based on previous responses I would assume that you are considering 
flooding as a means to actually route the control packets. However, 
if you are looking at flooding to provide the underlying infrastructure 
for routers in ad hoc networks I can suggest you take a look at a 
heuristic described in "Max-Min D-Closure Formations in Wireless 
Ad-Hoc Networks". This paper can be found in the proceeding of 
INFOCOM 2000. The main juice of this paper is that leaders (or 
effectively routers) are determined with no node in the network more 
than D hops away from its leader. The very attractive part of this 
heuristic is that it runs in D message rounds, not a function of how 
many nodes are in the network.

Alan Amis

-----Original Message-----
From: Dmitri Deshun Perkins [mailto:[email-masked]]
Sent: Thursday, June 01, 2000 6:19 PM
To: [email-masked]
Subject: flooding

Can anyone comment on the relative performance of "flooding" 
as a routing algorithm in ad hoc networks? Have any studies
been done that discuss when(under what conditions) it might 
be advantageous to simply use flooding(at least for control
pkts)?

Please point me to any papers that discuss this topic.
I briefly searched the archives and did not locate a discussion
directly related to the above questions. Please excuse me if 
this topic has already been discussed. Feel free to point me
to the correct archives.

Thanks for your time,
DDP

---

From: Dmitri Deshun Perkins <[email-masked]>
Date: Fri, 2 Jun 2000 11:13:51 -0400 (EDT)

Hi Alan,

Thanks for the reply. I just wanted to give a point of clarification 
to my previous e-mail(flooding). At this point, I am just exploring 
the issues(routing, security, etc)  of ad hoc networks as a possible
dissertation topic. As I discuss the routing issues with others(namely,
members of my advisory committee and students that attend weekly research
meetings), the first question(based only on intuition) is always,
"What's wrong with simply using flooding?" I suspect that many of you
must get this question as well.

Thus, I have been attempting to (quantitatively) answer this question via
simulation and wanted to reference other work related to flooding in an
ad hoc environment. I have read much of the info concerning routing in an
ad hoc environment and was just curious to know if flooding had been
considered/rejected as a possible routing solution and if so, why? Again, 
thanks for your comments.

Thanks,
Perkins

---

From: [email-masked]
Date: Fri, 02 Jun 2000 18:24:11 +0200

Clearly flooding data in the network is resource over-consuming. If your
network has 100 nodes, then each data packet needs to be repeated 100
times, thus reducing your efficient bandwidth by a factor 100. 

Philippe
PS: I also have problem on how the IP stack will support this.

---

From: Kenneth Brayer <[email-masked]>
Date: Fri, 02 Jun 2000 12:21:46 -0400

Dimitri

In a fixed network with fixed topology and using shortest path routing
you can calculate the traffic level that a network can carry, depending
on data rates, error rates, capacities of equipment, etc. If you use
flooding you send everything everywhere. That is you send many more
packets than are necessary. That is you deny your customer the use of
some of the networks capacity. In a MANET you are less efficient at
using the network than in a fixed network because the topology is
changing and you need to find the path to the packet's destination.
Again if you use ONLY flooding you will minimize the total traffic
handling capacity of the network. Some flooding may be necessary but it
is advantageous to use as little as possible. 

I was among the first researchers in this area in 1976-1981 before the
words MANET and Ad-Hoc were coined. If you look at my routing protocol
you will see I used a little flooding at startup but then tried to make
the network look as much like fixed path routing as possible. Parts of
my protocol have appeared in the internet protocols and in many of the
Ad-Hoc protocols under study today.

A thesis using only flooding is not useful, in my opinion, as it will
give a minimum capability network and is not new. You have to go back to
Paul Baran's papers on Hot Potato Routing and work that followed it. I
suggest you run the Science Citation Index on Paul Baran and find the
papers that reference him. This should uncover papers on flooding. You
might also contact Norm Abramson at U. of Hawaii. He invented the Aloha
Net back in the 1970s and is probably knowledgeable on flooding papers.

A list of my Ad-Hoc papers follows (sorry there are no computer copies,
my work preceded on line databases): The Proc. IEEE paper is a good
place to get a view of my work.

Networking of HF Radio Transmission
K. Brayer, IEEE MILCOM'86, Monterey, CA, October 1986

Packet Switching for Mobile Earth Stations via Low-Orbit Satellite Network
K. Brayer, Proceedings of the IEEE, November 1984

Autonomous Adaptive Local Area Networking: Ring Communications via
Point-to-Point Implementation
K. Brayer, IEEE INFOCOM'84, San Francisco, CA, April 1984

An Adaptive Computer Communication Network Designed with Decentralized Control
K. Brayer, IEEE Communications Magazine, November 1983

Adaptive Networking of Variable Topology Satellite Networks
K. Brayer, Sixth International Conference on Digital Satellite Communications,
Phoenix, AZ, September 1983

Routing in a "mobile" network - fact or fantasy?
K. Brayer, Data Communications, August 1983

Implementation and Performance of Survivable Computer Communication with
Autonomous Decentralized Control
K. Brayer, IEEE Communications Magazine, July 1983

Geographically Distributed Control of a Microprocessor Communications Network
K. Brayer, IEEE Communications Conference, Boston, MA, June 1983

Implementing Computer Communications with OEM Microprocessors:
Survivable Network Routing System
K. Brayer, IEEE Globecom'82, Miami, FL, November 1982

Implementing Computer Communications with OEM Microprocessors:
Survivable Routing System Performance
K. Brayer, IEEE Globecom'82, Miami, FL, November 1982

Survivable Computer Communications Routing using Decentralized Control
K. Brayer, IEEE International Conference on Circuits and Computers, 
New York, NY, September 1982

Simulation via Implementation with Applications in Computer Communication
K. Brayer, V.S. Lafleur, G.H. Simpson, 15th Simulation Symposium, Tampa,
FL, 	March 1982

---

From: Fabrizio Talucci <[email-masked]>
Date: Fri, 2 Jun 2000 11:03:15 -0700 (PDT)

To All (especially first researchers),
does anybody remember where this "Ad-Hoc" come from?
What does it exactly mean?
Anything to do with Latin?
When was it coined?
Who?
Thanx,

 Fabrizio Talucci

On Fri, 2 Jun 2000, Kenneth Brayer wrote:

> words MANET and Ad-Hoc were coined.

---

From: Ram Ramanathan <[email-masked]>
Date: Fri, 02 Jun 2000 14:02:19 -0400

I wonder if it is appropriate to dismiss flooding so. Surely, whether flooding
is viable in a network or not depends on several parameters including size,
radio data rate, traffic load and mobility.

For instance, consider a 100 node network of 11 Mbps radios (COTS today).
Suppose the only traffic were situational awareness traffic at 3 kbps per
node. Assume further that channel access and header overhead etc. reduce the 
raw data rate of 11 Mbps by a factor of 20 (pessimistically), to yield an
effective data rate per node of 550 kbps. Each node then runs comfortably
at about 50% utilization. Flooding is an adequate solution.

Moreover, as has been pointed out previously on this working group and several
papers, if the mobility is extremely high flooding may be the *only* way
to deliver data.

I am not advocating flooding, or implying that one should tailor network
design to low data rate traffic. I am merely pointing out that before one
goes off and designs complex schemes, one should examine the viability
bounds for the simplest possible solution for the problem -- and Dimitri
is asking the right set of questions in this context. Indeed, questions
that should have been asked (as Dimitri points out) and answered long ago,
but no answers seem to be around? Further, as technology improves (e.g., 
the data rate), it might be worthwhile examining such brute force methods 
for limited scenarios. 

Dimitri:
Some recent work that may be relevant on this topic (although perhaps not
answering the question directly)

Ho et al, "Flooding for Reliable Multicast in Ad hoc networks", DIAL-M 
Proceedings, 99

Ni et al, "The Broadcast Storm Problem...", Proc. Mobicom 99.

and citations therein.

Also check out NOAHnet -- this uses data flooding for wired nets.
Go to your favorite search engine (I used Google.com) and search for NOAHnet.

I would be interested in seeing your analysis of flooding when it is done!

-Ram.

> Date: Fri, 02 Jun 2000 12:21:46 -0400
> From: Kenneth Brayer <[email-masked]>
> Reply-To: [email-masked]
> Organization: The MITRE Corporation
> X-Mailer: Mozilla 4.61C-19990607M (Macintosh; U; PPC)
> X-Accept-Language: en
> MIME-Version: 1.0
> To: Dmitri Deshun Perkins <[email-masked]>
> CC: Alan Amis <[email-masked]>, [email-masked]
> Subject: Re: flooding(point of clarification)
> References: <[email-masked]>
> Content-Type: text/plain; charset=us-ascii
> Content-Transfer-Encoding: 7bit
> Sender: [email-masked]
> Precedence: bulk
> 
> Dimitri
>

---

From: Kenneth Brayer <[email-masked]>
Date: Fri, 02 Jun 2000 14:36:17 -0400

Ram
Generally some flooding is needed at some time and the more fragmented
the net the more you might need. Your example is perfectly fine but is
that the only traffic pattern. In general my customer wants a wide
variety of traffic in a large complex net so if I can find an approach
which preserves capacity for the user that is what I will do. Thus, I
seek to minimize flooding, overhead messages, connectivity table
distribution etc. There is a large body of literature on flooding but it
is more than 30 years old and exists only in hard copy in libraries. I
think the IEEE literature search engines available through most
libraries will find those citations.

Ken Brayer
The MITRE Corporation

---

From: Stefano Basagni <[email-masked]>
Date: Fri, 2 Jun 2000 14:07:17 -0500 (CDT)

> does anybody remember where this "Ad-Hoc" come from?

  Ad hoc (please, no hyphen) has been an English word for over a
hundred years (and yes, it has to do with Latin). Here's what the
Merriam-Webster on-line has to say:

ad hoc * \AD-HAHK or AD-HOKE\ * (adjective)

1 a : concerned with a particular end or purpose b : formed or used
for specific or immediate problems or needs

2 : fashioned from whatever is immediately available : improvised

Example sentence:
When the mayor learned that the mill, the town's main employer, was
scheduled to close, he assembled an ad hoc committee to address the
crisis.

In Latin, "ad hoc" literally means "for this." That historical meaning
is clearly reflected in contemporary English uses of "ad hoc" --
anything that is "ad hoc" can be thought of as existing "for this
purpose only." For example, an "ad hoc committee" is generally
authorized to look into a single matter of limited scope, not to
pursue any interesting issue. "Ad hoc" can also be used as an adverb
meaning "for the case at hand apart from other applications," as in "a
commission created ad hoc." The adverb is the older (it has been used
in English since the mid 17th century), but the adjective is no
quickly improvised addition to our language; it has been part of
English since at least 1879.

> Who?

  In the multi-hop mobile wireless nets community I do not know who used
this name first. I remember to have heard it from Dave Johnson at one of
the first mobiCom, but I am not really sure. Would love to know about
its genesis.

  Ciao, St.

--
Dr. Stefano Basagni
Center for Advanced Telecommunications Systems and Services     (CATSS)
The University of Texas at Dallas MS EC38          Richardson, TX 75080
Tel. 972 883 2216 ~~~ Fax 972 883 6204 ~~~ E-mail: [email-masked]

---

From: Fabrizio Talucci <[email-masked]>
Date: Fri, 2 Jun 2000 16:46:22 -0700 (PDT)

Thanx,
but, of course, by posting in this mailing list 
I was interested mainly in how this "ad hoc" thing relates to the
multihop wireless networks and not, for instance, to the wireless cellular ones.
I do have an english dictionary here and, fortunately, somehow
I write and read Latin. Exactly my problem!

 Fabrizo Talucci

---

From: "George N. Aggelou" <[email-masked]>
Date: Sat, 03 Jun 2000 12:03:50 +0100

Dimitri, you may want to have a look at our RDMAR protocol where
localisation of Route Discovery as well as of Route Repair is achieved,
thus reducing significantly the overhead of flooding the entire network
area. 

See my homepage for some RDMAR papers
http://www.ee.surrey.ac.uk/Personal/G.Aggelou/publications.html or the
IETF MANET WG homepage for the IETF draft 
(http://www.ietf.org/html.charters/manet-charter.html).

Regards,
George N. A.

-- 
*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.     
George N. Aggelou			     	
Centre for Communications Systems Research   
Mobile Communications Research Group      		
University of Surrey  		     

http://www.ee.surrey.ac.uk/Personal/G.Aggelou
*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.

---

From: "George N. Aggelou" <[email-masked]>
Date: Sat, 03 Jun 2000 15:08:33 +0100

> at about 50% utilization. Flooding is an adequate solution.

1) If, according to your assumptions, each node runs at about 50% of its
nominated data rate, don't you think this is a major reason to avoid
flooding  then?  Do you believe 50% effective utilisations is a good
performanmce indication for protocol design?

2) Uncontrolled propagation of control messages implies that:

	a. some areas of the network topology are unecessarily disturbed.
Hence, even if we accept the 50% effective utilisation for the set of
nodes that must propagate this control messaging, say during a Route
Discovery process, for the successful discovery of a route, then,
however, this 50% is not an acceptable figure for the rest of nodes
which even if they don't propagate the route discovery signalling, the
discovery will be successful.  For example, by localising the route
discovery signalling such that only the nodes between the source and
destination of the discovery are disturbed, then certainly the rest of
the network nodes will enjoy much better channel utilisation rates.

	b. (adding to a.), in CDMA-based networks where interference levels
increase as a function of the user activity (and ), the extra control
messaging will increase user interference. Therefore, system capacity
will be reduced.

	c. the probability of collisions at the channel access layer also
increases. This in turn implies more retransmissions and the such....
Which in turn implies more delay on per packet forwarding.

By any means, your scenario does not show any tradeoffs as what the
benefits of using flooding would be _compared_ to when floding is not
used.  
Therefore, I would say that your conclusion "Flooding is an adequate
solution" is not true.

Regards,
George N. A.

---

From: Ram Ramanathan <[email-masked]>
Date: Sat, 03 Jun 2000 22:22:57 -0400

George,

Your repeated reference to "control messages" tells me you have completely
misunderstood me. I was talking about flooding every DATA packet to
everywhere in the network. There ARE NO control messages in a "flooding
protocol". As I mentioned in my previous note, flooding is clearly not what
I would want to use as my routing mechanism all the time. However, 
understanding in what
regions of the n-dimensional space of (datarate, load, mobility, size ..)
flooding works, and in what regions it breaks would be valuable -- the 
example was one point in such a space, to make my point (no pun:)

Again, what I suggest is that data flooding might be competitive when
1) mobility is so high that no routing protocol can converge fast enough
2) when offered_load/data_rate is sufficiently low -- this could happen
   because load is low or as data_rate increases (as is the industry trend)

It seems like you've missed the example too, so here are some inline
comments.

> performanmce indication for protocol design?

Huh? Are you saying that 50% is too much or that it is too little?

If you are saying 50% is too much, i.e., people should run a link at less
than this, consider that most ISPs use 50% as a conservative, safe number.

If you are saying 50% is too little, you have missed this completely.
I use utilization, informally, as load/capacity. In the example, the node
effective capacity is 550 kbps. The load is 3kbps*100 (since every packet
is sent exactly once (using sequence numbers to purge duplicates) by every
node in the network) or 300 kbps. Thus, the utilization is 54.5%.

If you want to run it at a higher utilization, sure, that is fine, it 
supports even higher traffic. For instance, at 90% utilization, it
supports 5 kbps at every node. In other words, if you think I shuld
be saying 90% instead of 50%, just replace 3kbps by 5kbps in the exampel.

> 2) Uncontrolled propagation of control messages implies that:

What control messages (read above)?!

I'll ignore the points a,b,c since it seems like you're talking about 
the benefits of "constrained flooding" of routing control messages - 
a noble thought, but largely irrelevant to the discussion. 

> By any means, your scenario does not show any tradeoffs as what the

Didn't say I was showing tradeoffs....

> Therefore, I would say that your conclusion "Flooding is an adequate

Of course it is an adequate solution for the particular scenario. Of
course it is not in general.

Cheers,

-Ram.

---

From: "George N. Aggelou" <[email-masked]>
Date: Sun, 04 Jun 2000 11:53:07 +0100

Ram,

My previous comments address some problems of flooding "control
signalling" in a MANET as your wording "traffic" in your first message
was interpreted as "routing-related control + data traffic". 

Apologies for the confusion then.

Best,
George N.A.

> everywhere in the network.
> There ARE NO control messages in a "flooding protocol". As I mentioned in my previous note, flooding is clearly not what