Subject: Re: Concerns with proposed MANET routing protocols (retry#2)

From: Zygmunt Haas <[email-masked]>
Date: Sun, 8 Feb 1998 10:33:05 -0500 (EST)

Dear Mike,

On Thu, 5 Feb 1998, Mike Butler wrote:
...
>    1) There is an apparent reliance on reversible links
>    2) The importance of load balancing seems to be overlooked
>    3) There seems to be no exploitation of "advantaged" nodes
>    4) An early quench of route discovery may hide the best route
>    5) The routing objective function is unclear
...
>    6) What does the charter's "a unicast algorithm" statement mean?
>    7) Has there been work in link-layer and network-layer coupling?

I am glad that you have asked these questions, (which, by the way are
excellent points) as they should allow our MANET group to focus some of
the discussions of our work. I will try to address some of them. Please
note that my "bias" is towards the ZRP protocol, as I have been working
a lot on the protocol (similation and design issues) and, thus, I am the
most familiar with it. I am sure others will address your questions from
their point of view.

> 1) There is an apparent reliance on reversible links.
> 
>     The proposed routing algorithms have an apparent reliance on
>     bidirectional or reversible links.  There are a number of factors
>     which will make wireless links unidirectional, among these are:
> 
>   - Differing radio capabilities.
> 
>     Radios within a network can have different transmit powers or
>     receive sensitivities.  This is quite likely in a tactical
>     environment where man-pack and vehicular radios exist.  Vehicular
>     radios, being less unconstrained by size and weight, typically
>     have 10dB greater transmit power than their man-pack counterparts.
>     Unidirectional links are exceedingly likely in tactical networks.

There are a number of "issues" here. First, at least in narrowband
communication, there is a tradeoff between the data-rate and transmitted
power. You can have a link between two reasonably close nodes, although
the data-rate of this link may be *really* low. So, I prefer to call the
problem that you have stated as "asymmetrical" links, rather than
uni/bi-directional. Similar argument can be made for broadband
transmission. Furthermore, I want to point out that due to propagation
conditions and mobility, links are fluctuating in quality all the time. 
Thus, the inherent imbalance in transmission power of the man-mounted and
vehicle-mounted radios is not, by itself a new problem.

There are few ways that your question could be answer. The first one (and
this is a rather poor solution) is to declare a link between two
(adjacent) nodes as "up" *only* if both directions are "up."  This will
work, although will *unnecessarily* limit the connectivity in the network. 
Another approach is not to rely on, what is called in ZRP as, "accumulated 
route" for reverse routing of the discovered route back to the querying node 
(which is currently done by reversing the accumulated route). Rather, a 
separate route discovery from the destination, back to the source could take 
place, through which the found forward-accumulated-route could be returned. 
This involves some additional control traffic, but protects you against the 
asymmetrical link problem.

>   - Interference
> 
>     Even a network of identical radios will have unidirectional links.
>     Interference, either by hostile jammers or by friendly "cosite"
>     will reduce a nearby receiver's sensitivity.  Since it is only one
>     receiver that is handicapped, unidirectional links may result.

See above.

>   - Wide-area information broadcast
> 
>     There is an increasing emphasis, especially in tactical networks,
>     on the wide-area broadcast of information. Satellite-based
>     transmitters (GBS) are being used for the forward links while the
>     the return links use alternative paths.  (The commercial sector
>     display similar topologies in Direct-PC and some HFC
>     configurations.) 

Again, as long as a path from the source to the destination and a path
from the destination to the source exist - although they do not have to 
be "the same path," there is no problem in discovering and using these
paths.
 
>   - EMCON operations
>     
>     An extreme instance---applicable only in military networks---is when
>     some not cannot transmit due to an impending threat (EMCON). In
>     such a case, it may be necessary to have some other node provide a
>     "likely" route in response to a route discovery request.
>     (Obviously, an EMCON node can not participate in bidirectional
>     communications, but it still needs to receive information.)

Such a "proxy" services are perfectly ok and there is nothing in ZRP which
prevents this from happening. Of course, there are a couple of "deeper"
problems here, for example, how does the "proxy" node knows that it is in
radio contact with the EMCON node. To know this, EMCON node needs to
convey something to the "proxy" node, so it needs to transmit. Although,
its transmission could be at much lower power, it still needs to transmit
and reach at least one neighbor (i.e., the proxy node). If the EMCON node
can transmit even to one close neighbor only, the ZRP protocol will
discover the route to it anyway. So, nearly "by definition" I am not sure
whether there is a problem here at all. 

> 2) The importance of load balancing seems to be overlooked
> 
>     Another critically important issue in tactical networks will be
>     load balancing.  Specifically, a node's purview will change with
>     it's position.  A node in a particularly advantageous position
>     (e.g., mountain top) will "see" much more of the network.  The
>     current routing proposals seem to favor routing traffic through
>     this advantaged node, thereby causing a bottleneck.  The result is
>     that the introduction of an advantaged node can cripple the
>     network.

>     We expect that "advantaged nodes" will occur in most wireless
>     topologies; a person on stage is likely to have a much better view
>     of the wireless network throughout an auditorium.  Advantaged
>     nodes will certainly be an issue in tactical networks.  In fact,
>     there are efforts underway to introduce highly advantaged
>     (air-borne) communications nodes into tactical networks.
> 
>     The approach to load balancing in a wireless network will likely
>     differ from that used in wired networks.  In wired networks, load
>     balancing is only beneficial when multi-homed hosts (multiple
>     network segments) are present.  In the wireless environment, load
>     balancing is a problem even if there is a single, flat network
>     segment and no multi-homed hosts.

Load balancing is being currently addressed in our ZRP work. And yes, this 
is a very important aspect. I will not describe our solution here, but to 
give you one possible direction, there has been work by Michael Pursley on
"Least Resistance Routing," which could be used in this context.

> 3) There seems to be no exploitation of "advantaged" nodes
> 
>     Although "advantaged" nodes are a liability for the currently
>     proposed routing algorithms, we believe that other routing
>     algorithms could use these nodes to great advantage.  For example,
>     consider an airborne node with limited traffic handling capacity
>     but purview of the entire terrestrial network.  Such a node could
>     easily collect neighbor information from the terrestrial assets,
>     construct a theater-wide routing picture, and broadcast a common
>     routing picture. 

>     Furthermore, a node need not be omniscient to assist routing
>     decisions.  For example, if some advantaged node sees a superset
>     of another sees, it has a decided advantage in finding and
>     propagating routes.  Given radio's propagation phenomena, we
>     expect that advantaged nodes will occur in every wireless network,
>     even in flat, homogeneous networks.  A node on stage, in the
>     center of a group, or near a doorway is likely to have a much
>     wider view; it makes sense to exploit that in finding routes.

This is a "reverse" problem that you have stated in 2). Yes, strategically
placed nodes have advantage. In fact, this advantage is already used by a
number of MANET protocols, including ZRP. I would not go as far as saying
that the "advantaged" nodes should be responsible for route determination
(the single-point-of-failure problem). However, these "advantaged" nodes
have more path passing through them already and thus can reply to a route
request query if they know the answer. So, again, this is to a large degree
already there. If you had something more extensive in mind, please
explain.

> 4) An early quench of route discovery may hide the best route
> 
>     We are concerned that the current routing algorithms seem to
>     quench the route discovery as soon as a path is found.  The
>     concern is that the "best" route might easily escape discovery if
>     one packet along the "best" path is corrupted or lost.  Since
>     wireless bit error rates are quite high (even for good links), it
>     is not unlikely that a packet along a good link could be dropped.

No, not in ZRP. ZRP finds *all* the routes between the source and the
destination. The quenching process in ZRP is to ensure that you do not
unnecessarily discover the same route more than once and, thus, waste
network resources. However, all the routes are reported back to the
source.

Please note that there is a mechanism in ZRP (it was not described in the
Internet Draft, though), by which intermediate nodes can "get rid" of some
routes which are clearly inferior. This was created to reduce the amount
of control traffic and will not allow the best route to escape the
discovery process.

> 5) The routing objective function is unclear
> 
>     Unlike wired links, there are a large number of objective
>     functions which make sense when selecting routes in a wireless
>     network.  Although it is not explicitly stated in the
>     proposals, the tacit assumption seems to be that any
>     route is acceptable and the shortest path is generally preferable.
> 
>     The "shortest path" route is frequently a poor choice in a
>     wireless network.  A shortest path route through a wireless
>     networks would tend to favor longer hops which would (1) require
>     higher transmitter powers, (2) introduce higher bit-error rates,
>     (3) make hidden nodes more likely, etc.  Furthermore, as mentioned
>     above, blindly accepting the "first found" route may prevent the
>     discovery of much better routes.

I agree that any routing protocol should be able to "evaluate" paths based
on realistic criteria and choose the "best" one. Again, I would like to
mention the work by Michael Pursley on "Least Resistance Routing."
Further, I would like to point out that there is no reason while routes
cannot be compared in ZRP, since ZRP returns all the routes back to the
querrying node.

> 
>     Objective functions which make more sense for a wireless
>     (particularly tactical) environment are (1) most reliable path
>     (best link margin), (2) most stable path (least likely to change),
>     (3) minimum total power path, (4) least congested path, (5)
>     minimal spectral use, etc.  
> 
>     We believe that any of these five objective functions might be a
>     superior choice to the shortest path or first-found routes in
>     tactical wireless environments.  We also believe that route
>     discovery could provide this with little additional overhead---a
>     route's objective "cost" could be calculated as the route is
>     discovered and the high "cost" routes could be selectively pruned.
>     In short, we think that it is highly desirable to discover
>     multiple routes and down-select based on some criteria, and
>     first-found and shortest-path are unlikely to be provide a good
>     selection criteria.
  
I absolutely agree with you. Furthermore, the set of criteria may change
dynamically. I think that this would be a very good topic for the next
MANET discussion. 

> 6) What does the charter's "a unicast algorithm" statement mean?
> 
>     According to the working group's charter, the intention is to
>     select "a" unicast routing algorithm.  It seems highly unlikely
>     that a single algorithm will work well for all network sizes,
>     topologies, and rates of change.  Is the working group making some
>     tacit assumptions about the networks of interest when they discuss
>     "an algorithm?"  If so, would you please make those assumptions
>     explicit.

Let me do some ZRP advertising here (thanks for your question (:-)). 
I do not see ZRP as "a" routing algorithm, but rather as a framework under
which a number of routing protocols could be used. For example, the
Intrazone (IARP) protocol that each node runs could be any protocol
(preferably proactive). The IARP allows to discover routes in a local
neighborhood, which is an important aspect due to traffic locatization. Of
course, the major reason for doing so is to "partition" the problem, so
that in a large network the amount of control traffic is *significantly*
reduced. The size of the partitioning is govern by a single parameter -
the Zone Radius, which can be dynamically changed.

Joe Macker termed the feature in the December MANET meeting as "having a 
knob" to adjust the behavior of the protocol based on the particular current 
network conditions. I like the "knob" analogy. 

Thus, to summarize, ZRP addresses exactly your question on two levels -
the underlying IARP protocol can be selected based on the network and its
conditions and the geographical scope on which this IARP protocol operates
is (dynamically) determined (by setting teh Zone Radius) by the current
operational conditions.

> 7) Has there been work in link-layer and network-layer coupling?
> 
>     In "Mobile Ad hoc Networking (MANET): Routing Protocol Performance
>     Issues and Evaluation Considerations" the authors pointed out the
>     need for "interaction/interface with link-layer protocols".  At
>     the link level there is a tremendously rich design space which
>     trades-off power, bandwidth, latency, coding, bit error rates,
>     etc.  It would seem that these can be readily exploited in routing
>     through a wireless network, but none of the proposals addresses
>     these issues explicitly.
> 
>     Has any work been done in this area?  Does the working group
>     intend to explore this area at some future time?  Is there a tacit
>     assumption that the proposed algorithms can be retrofitted with
>     these link-layer embellishments?

We talked about this a bit in the last MANET meeting. In particular, the
issue of whether broadcasting (eavesdropping) could be assumed in the
design of the routing protocol was addressed. Yes, I agree that we need to
have much more detailed discussion about these issues.

Best regards,

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
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-