Subject: [manet] Dumb Question?

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Mon, 6 May 2002 15:08:27 -0600

Hello,

I am looking for a term, but have had no luck.

In wired nets, a packet is routed through the network from node to node, say
by routing tables.  However, in MANETs, in which packets are broadcast via
omnidirectional antennae on a shared channel, such a thing is not possible.
Instead, each node that receives a packet  decides to:
     1.  Discard the packet,
     2.  "Read" the packet, since it is addressed to the node, and/or
     3.  Rebroadcast the packet.

If the node is not to be an intermediary node in the end-to-end path between
the source and the destination, or if the node is receiving a copy of a
packet it had previously broadcast, it will not broadcast the packet.  This
is necessary to avoid overutilizing the channel.

If the node is an intermediary node on the path, then it must rebroadcast
the packet.  

I've got this much figured out, but what I do not know is what this process
is called.  It is the MANET equivalent to "routing," but is not really
routing, since the sending node has no way of directing the packet.  

I've tried a number of searches and read a few glossaries, but have not been
able to find this term.

I'd appreciate any help.

Thanks,

John P. Mullen

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

---

From: "Nast, Douglas P" <[email-masked]>
Date: Mon, 6 May 2002 15:16:23 -0700

John, 

Actually, the manet folks are designing routing protocols in the classical
sense, although the protocols of interest tend to be reactive rather than
proactive.  The fact that the mac layer supports broadcast via omni antennas
does not change this.  What you are suggesting is that an Manet does not
need layer 3 routing since it can "switch" at layer 2. In effect, you would
like to treat the manet as an ethernet segment where routing is not
necessary within the segment because everyone has a shared medium.  But I do
not believe that this is the paradigm that this group is working to.  

I think the reason for this (I am just a hanger-on, not one of the
old-timers) is that you need to talk to nodes that are not within range of
your antenna.  To get to them intermediate nodes have to forward your
traffic.  While this could be done at layer 2, it would involve building
mechanisms at layer 2 that are as complicated as traditional layer 3
routing, and would not be as flexible (i.e. lead to stovepipe solutions).
The name of the game seems to be to use IP infrastructure for multi-hop
forwarding.  Therefore layer 3 routing is indicated to relay the traffic
across long distances.  

I would call the process you describe layer 2 switching, as in ethernet
LANs.   But it is not considered to be a general solution for Manets.   

Regards, 
Doug Nast, Boeing

-----Original Message-----
From: Mullen, John P. (Contractor)
[mailto:[email-masked]]
Sent: Monday, May 06, 2002 2:08 PM
To: [email-masked]
Subject: [manet] Dumb Question?

Hello,

I'd appreciate any help.

Thanks,

John P. Mullen

---

From: "Nast, Douglas P" <[email-masked]>
Date: Tue, 14 May 2002 10:09:30 -0700

John,

You sent a reply saying you understood that layer 3 routing was going on but
wondered what this other process was.  Thanks for the clarification.

Note that in your question you say that "such a thing is not possible.
Instead, each node that receives a packet decides to..."  and then you give
3 possible behaviors, consume, re-broadcast, or discard.

By what process do the nodes come to understand which of these behaviors is
appropriate for them? Who/What is doing the teaching and to what purpose?
Are the decisions you describe being made on the basis of MAC layer
addresses or IP? 

The first thing that occurs to me is that this behavior was learned via a
route discovery process, sort of like source route bridging in 802 LANs.
This approach to routing in Manets was proposed a while back by David B.
Johnson, and is, I think, the basis of the reactive approach to manet
routing.  If that's the case, then you can call it routing or you can call
it switching, but it is not worthy of a new name.

Based on Perkins and Ram responses, I guess I am missing something, though.
Do you think your question has been resolved? If so how? 

Doug Nast, Boeing

-----Original Message-----

Hello,

I'd appreciate any help.

Thanks,

John P. Mullen

---

From: "Nast, Douglas P" <[email-masked]>
Date: Tue, 14 May 2002 10:09:30 -0700

John,

Doug Nast, Boeing

-----Original Message-----

Hello,

I'd appreciate any help.

Thanks,

John P. Mullen

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Tue, 14 May 2002 12:16:26 -0600

Hi Doug,

My concern was that the forwarding process might be called something else in
a MANET, since it functions differently from the analogous process in wired
networks.  However, the consensus seems to be that the same term is used.  I
think I've gotten my answer on that.

The process would be the consequence of the chosen protocol.  As I
understand it, the process by which a node obtains link information is
called "routing" and the process by which a node decides which of the three
things to do is called either "forwarding" or "switching," depending on who
you talk to.  The details of the processes would be limited by operational
and hardware constraints and defined in the protocols.

The scheme used to assign node addresses is a key issue in military MANETs.
At the upper levels, one wants a scheme that reflects the hierarchical
military organization.  This facilitates the proper routing of orders,
partial orders, etc.  However, at the lower levels, one would want an
addressing scheme that reflects the actual network topology.  This would
allow clustering, which would make route determination and forwarding
simpler.  One solution is to do both, coordinating the system via the
interface.  However, the nodes are in constant motion, so the interface
would need to update its information on the fly.  Offsetting the higher
efficiency of the clusterable scheme at the lower levels is a more
complicated interface and more difficulty enforcing security.  I don't think
this issue has been resolved yet, so, of course, the protocols are also up
in the air.

I just started reading _Ad Hoc Networking_, edited by Charles Perkins.  In
"A DoD Perspective on Mobile Ad Hoc Networks," James Freebersyser speculates
on p. 33 that it is unlikely a single protocol will be able to operate
efficiently over the full range of conditions under which a military MANET
must operate.  If he is correct, the issue may never be fully resolved.

But, there is always hope,

And, graduate students.

:-)

John Mullen

-----Original Message-----
From: Nast, Douglas P [mailto:[email-masked]]
Sent: Tuesday, May 14, 2002 11:10 AM
To: 'Mullen, John P. (Contractor)'
Cc: [email-masked]
Subject: RE: [manet] Dumb Question?

John,

Doug Nast, Boeing

-----Original Message-----

Hello,

I'd appreciate any help.

Thanks,

John P. Mullen

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Tue, 14 May 2002 13:18:26 -0600

Hi Zygmunt,

Well, I hadn't gotten that far yet, but certainly some sort of adaptive
protocol would be in order.  Thanks for the links.  I will check it out.

Of course, I should mention that one characteristic of military MANETs is
that it is highly probable that someone will be trying to break your system.
For this reason, military commanders are skeptical of fully automatic
systems.  A system that is fully automated is also fully predictable to
anyone who knows the protocols and is susceptible to a focused attack.  On
the other hand, one that is at least partially under human control is more
difficult to disable.  The problem is, of course, training the human to
manage that level of control, making the necessary information available to
the decision maker, and instilling the discipline to make appropriate
selections under the immediate threats of war.  

Of course, with all the hackers about, this may become a problem for all
MANETs.

:-)

John Mullen

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: Tuesday, May 14, 2002 12:56 PM
To: Mullen, John P. (Contractor)
Cc: [email-masked]
Subject: RE: [manet] Dumb Question?

Hi John,

> must operate.  If he is correct, the issue may never be fully resolved.

Yes, I read this book too (:-) ...

I hate to bring this point over again ... and self-promote our work ... 
but the issue of "efficient operation over a wide range of conditions" can
and should be addressed by a *hybrid* routing scheme, where the "proactive" 
and "reactive" behavior are "mixed" in the amounts that match these
operational conditions. In other words, *adaptivity* is the key issue
here.

One such an example of a hybrid scheme is (of course, you have guessed)
the ZRP protocol, in which the amount of proactive vs reactive behavior is
*dynamically* adjusted through a single parameter - the zone radius.

Now imagine this - one could use the AODV (or DSR, or your favorite
reactive protocol) as the reactive protocol in ZRP and OLSR (or TBRPF, or
your favorite proactive protocol) as the proactive protocol in ZRP (I
tried to offend the smallest number of people here (;-)). This is why ZRP
is a framework for ... for exactly this - for "efficient operation over a 
wide range of conditions". So, maybe, there is a hope to resolve this
issue after all.

Zygmunt.
==-=-=====
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
Prof. Zygmunt J. Haas                    http://people.ece.cornell.edu/haas 
Wireless Networks Laboratory		 http://wnl.ece.cornell.edu
School of Electrical Engineering         
Cornell University			 tel: +1-607-255-3454
323 Frank Rhodes Hall			 fax: +1-607-255-9072
Ithaca, NY 14853			 e-mail: [email-masked]
U.S.A                             
	WNL web page: http://wnl.ece.cornell.edu
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-

---

From: "Nast, Douglas P" <[email-masked]>
Date: Tue, 14 May 2002 13:02:10 -0700

Zygmunt,

I think your idea is very interesting, as it addresses the latency issue for
routes in your zone (which is important in military apps), and offers the
promise of scalability:  The reactive inter-zone idea is reminiscent of the
hierarchical architecture of OSPF, which essentially operates LS intra-area
and DV inter-area.  How would you contrast your zone idea to OSPF areas?

Doug Nast, Boeing

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: Tuesday, May 14, 2002 11:56 AM
To: Mullen, John P. (Contractor)
Cc: [email-masked]
Subject: RE: [manet] Dumb Question?

Hi John,

Zygmunt.
==-=-=====

---

From: [email-masked] (cesar santivanez)
Date: Tue, 21 May 2002 17:52:39 -0400 (EDT)

Hi all,

When evaluating a routing protocol performance, we need to consider not only the network
size but also the traffic and mobility rate. Also, the traffic distribution is of paramount importance,
since uniformly distributed traffic will favor proactive approaches while a more reduced sets of destination
(in a period of time) will favor reactive approahes. Also, not only the impact of the control overhead
need to be considered, but also the effect of route information latency, etc. in route optimality,
and the final efferct of route sub-optimality in th esystem performance.

We have developed a methodology for the study of scalability of ad hoc networks, defining the total overhead as the metric
that
encompass the effect of control overhead (either proactive updates
or reactive route discovery packets) and the effect of sub-optimal routes (more transmissions that
required. We applied out methodology for comparing several ad-hoc routing
protocols, including standard link state,  hierarchical link state, ZRP, and Hazy Sighted
Link State (HSLS). Both, the methodology and our results (based on a set of realistics assumptions,
of which the more controversial may be the uniform traffci distribution ;-) can be found in
our upcoming INFOCOM'02 paper:

C. Santivanez, B. McDonald, I. Stavrakakis, and R. Ramanathan., "On the Scalability of Ad Hoc Routing Protocols," to appear in
Proceedings of IEEE INFOCOM'02, New York, June, 2002.

A copy of this paper may be found at the conference web page or at th efollowing URL

http://www.ir.bbn.com/documents/articles/index.html

Among other things, we found that ZRP - by being able to dynamically adapts its zone size
reduced de rate of increase of overhead w.r.t. network size (N) from N^2
for pure proactive or reactive approaches, to N^1.66.   Multilevel Hierarchical link state,
further reduced the overhead to a little more than N^1.5, and HSLS by balancing
the control overhead and the negative impact of route innacuracies reduced the
total overhead to N^1.5. We noted that ZRP behaves as a 2-level hierarchy system, while
multi-level Hierarchical link state and HSLS behave as having as many level as needed.

The results also relate total overhead to traffic intensity (assuming uniformly distributed
source-destinations) and mobility.  An important conclusion of these results is that as mobility
increases, it pays off to allow the control overhead to increase, but not linearly
with the rate of link changes, that is, to allow nodes to have a distorted view of the network.
Also, as traffic rate increases, it pays off to let the control overhead to increase as well,
since the quality of the routes become more important as these routes are used more intensively ...

I hope these results will help the discussion ...

Cesar Santivanez
Network Scientist 
BBN Technologies

[email-masked] wrote:

> Hi Charlie,
>
> Well, I agree with you that since pure on-demand protocol is a
> special case of a hybrid scheme, such as ZRP, a hybrid scheme
> performance is bound to produce at least as good results as any of the two
> extremes - purely proactive and purely proactive schemes. In fact, our
> study (for example, the paper in your book) shows that it can reduce the
> control traffic to a small fraction of those two extremes. These results
> have been confirmed both analytically and through simulation.
>
> Your point regarding scalability is a very valid point. We are currently
> evaluating the scalability of the hybrid (ZRP) approach for thousands to
> tens of thousands of nodes. This is not a trivial task, taking into the
> account the simulation runtime duration. But the preliminary results are
> *very* encouraging, to say the least. Stay tuned ....
>
> Zygmunt.
> ==-=-=====
> On Wed, 15 May 2002, Charlie Perkins wrote:
>
> >
> > Hello Douglas,
> >
> > We have results for scaling AODV up to 10,000 nodes.
> > We know that we can do better by improving the packet
> > delivery ratio.  In a few weeks, I reckon we'll have some
> > specific directions for algorithm improvement.
> >
> > ZDP is theoretically able to do better, simply because it
> > admits as special cases all on-demand protocols.  However,
> > I have never seen any results showing ZDP on a network
> > of 10,000 nodes (simulated).
> >
> > Regards,
> > Charlie P.
> >
> >
> > "Nast, Douglas P" wrote:
> >
> > > Zygmunt,
> > >

---

From: [email-masked] (cesar santivanez)
Date: Tue, 21 May 2002 17:52:39 -0400 (EDT)

Hi all,

Cesar Santivanez
Network Scientist 
BBN Technologies