Subject: ZRP and Parallel Packet Flooding

From: "Bora A. Akyol" <[email-masked]>
Date: Tue, 25 Nov 1997 11:51:07 -0500

Please correct me if I am wrong, but I see the following problem
with ZRP's routing structure.

Regarding the prevention of parallel packet flooding in ZRP,
the packet eavesdropping approach to prevent parallel routing
queries will not work well in environments where some nodes are
hidden to other nodes or "directional" antennas are being used
to increase to S/N ratio or to lower the probability of detection and/or
intercept.

In such environments ZRP will cause parallel routing queries
being flooded through the network. A better approach would be
to use some sort of designated border node concept to resolve
routing problems. Then you can have one border node for
every neighboring zone. Hence no parallel queries by design.

I hope I managed to explain my concern.

-- 
Bora Akyol
BBN Technologies
GTE Internetworking

---

From: Zygmunt Haas <[email-masked]>
Date: Fri, 28 Nov 1997 06:49:51 -0400 (AST)

Hi Bora,

I think that I understand your question in the case of "directional"
transmissions. I am not sure about the case of "hidden terminal" nodes;
i.e., I am not sure how hidden terminals present a problem for the flood
termination process - you may want to explain this a bit more.

So, my answer here concentrates on the effect of "directional" transmission 
only. First let me state that I believe that one of the salient advantages 
that the wireless communication environment offers is the *broadcasting* 
feature. By taking advantage of this feature (such is the case in ZRP's 
eavesdropping) does simplify the algorithms and *saves bandwidth*. Thus, 
my claim would be that one should not use directional transmission in this 
environment at least not for the control traffic (i.e., route discovery
process). Note, that this does not mean that you cannot use directional
transmission for the actual data transmission (but you may need to have
two antennas or a more complex antenna design). 

To justify more why "directional" transmission is not a good idea for this 
environment, espacially for control traffic, look at the problem of "Neighbor
Node Discovery" process. How do you do this with a directional transmission
only? The only algorithm that I can think of involves scanning all around
the node in question. This is very time and resource consuming. On the
other hand, broadcasting allows you to send *a single* query either asking
who is around or advertising your presence to other nodes. Thus, my
conclusion is that "directional" transmission should not be used in the
ad-hoc environment for control operations. BTW, other routing protocols
also use the eavesdropping feature to improve the performance, so ZRP is
not the only case.

However, if you insist on using "directional" transmission - the ZRP
protocol still works. To explain this, I need to tell you that the
eavesdropping-based termination algorithm is only one of the three possible
termination algorithms that we have studied. It gives the best performance
(in terms of quickly terminating any search "threads" that wondered into
already-searched areas). Other algorithms do not rely on broadcasting at
all. We did not want to describe those in the Internet Draft, as we
believe that the currently-proposed termination algorithm is both
efficient and effective. If anyone wants me to add the other candidate
termination algorithms, I will be happy to do so.

A final word, the original ZRP termination algorithm will work as well 
without eavesdropping at all. It will be less efficient in that there will be
(unnecessary) nodes that are queried, but the flood will terminate and 
provide the necessary answer. We have some results showing the performance
of the original ZRP termination algorithm without the eavesdropping
feature. I will be happy to discuss this also.

To summarize my response:
* I am a strong believer that broadcasting should be used in the ad-hoc
  communication environment, at least for the control traffic
* There are other candidate for flood termination algorithms that do not 
  depend on the eavesdropping feature and that work well as part of the
  ZRP protocol,
* the original ZRP algorithm can work without eavesdropping as well,
  albeit at reduced efficiency

Hope that this addresses your concern.

(Congratulations on your position with BBN. So you traded the "sunny
California" for the East-Coast winter - I did the same mistake 10 years
ago and I regret it ever since (;-(. Well, maybe some day ... )

Happy Thanksgiving to all!

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