Subject: Re: Concerns with proposed MANET routing protocols

From: [email-masked] (Joseph P. Macker)
Date: Thu, 5 Feb 1998 18:28:19 -0500

Mike:

Thanks for your input..
I, for one, do not agree with ALL your technical interpretations and I included some notes below.

Before going addressing some of your comments, I would like to add that this group is early in its work and sensible framework contributions remain WELCOME.  The group is defined by its member's contributions.  Also, present proposals are only first candidates and early drafts, although some have undergone significant simulation and early implementation.  They are not all in the same grain as you seem to imply.   Present proposals are technically very different as a far as routing algorithms and approaches go and the emphasis is on mobile routing algorithmic aspects at present.   We will likely fold in more system specific issues in over time.  If you have constructive general solutions please SUBMIT or specific comments on particular candidate proposals are welcome.

In my view, we are trying to standardize on improvements to dynamic, mobile IP routing.  We are not trying to standardize or work on every possible aspects of a mobile network system and architectures.  Some of the issues you raise seem very broad or architecture specific.  Within manet, we are concerning ourselves mainly with mobile routing algorithms.  Research needs to continue in a broader set of mobile networking areas.  In any case, the need for improved mobile routing algorithms exists across a wide variety of architectures and we are working this problem with some narrowed technical focus on the Internet layer.  Enough said....;-)  on to my comments.

-Joe

At  9:43 AM 2/5/98 -0500, Mike Butler wrote:
>The following paragraphs will elaborate on each of these points.
>
>----
>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:

Thanks for the tutorial which followed on wireless data communications ... ;->

I disagree with your blanket statement that complete bidirectionality is required.  IMEP/TORA or other approaches that use router IDs can handle some of this unidirectionality for single hop links that have logical bidirectionality.  Other than that we do not want to replicate the work of the UDLR WG which is looking at the more general problem of unidirectional link routing.  Also, when mature we can adopt anything that appears sensible in a mobile environment.  

Extensions we have previously thought of include the fact that the bidirectionality can be made logical not physical and this allows us to adopt protocols, (e.g., TORA), to work within such scenarios.  If you absolutely have no two-way communication paths (e.g., EMCON), static routes, gateway proxies...are there other great routing solutions in this space.  As routing goes, it's a trifling example.  We don't really have a multi-hop routing problem here, since EMCON nodes can't transmit for other nodes, there is no multihop relaying.  Nonetheless, we can typically engineer modes to fit particular architecture problems or operational needs.  A mixture of EMCON nodes in a multihop relay network can be handled through proxying.  Its getting curiosier and curiousier (as Alice said in Wonderland).

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

I don't agree this has been overlooked by all.. TORA, for one, finds multiple routes and it is up to routing policy to determine how to use these routes.  This may help load balancing vs. shortest path type of algorithms which may concentrate this.  We can always make a particulat flat algorithm do things differently when something is known about the infrastructure.  The right theoretical answer is scenario dependent.  If you are proposing ILS schemes, see our ILS simulation comparisons for some mobile network scenarios. 

http://tonnant.itd.nrl.navy.mil/tora/tora_sim.html

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

I'm confused by your observations.  First, previously it sounded like you did not technically recommend routing through the advantaged node and in this last paragraph it appears like perhaps you now want to.  Which is it, I'll let the system tweakers figure that out and say we MAY do either and that additionally not all proposals are equivalent in this regard.

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

By single, flat above I assume you mean single,flat MULTI-HOP networks.  O.k.?

Having worked on mobile networks in the past with load balanced routing, it is my opinion, there is both advantages and disadvantages to different load balancing techniques and the potential overall effect on general mobile network service and true resource utilization is generally unclear.  I could go on for several paragraphs but I will spare everyone that.  This is once again a very SCENARIO specific topic.  There are many aspects of load balancing, especially classical approaches which are detrimental in highly mobile networks, especially those that are heterogeneous.   We do need more research here (the jury is out..actually the evidence isn't even in) and in the mean time routing approaches which can work in multiple ways keep our options open for different architectures and scenarios.  If you have the generalized answers please reveal...

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

I believe this can also be done with TORA. If one designates an advantaged node special things can be done.  We wanted to provide specification to solve a general flat routing problem before we tweak improvements.  I see this as more a network management issue or protocol enhancement to a specific infrastructure scenario.  I contend this can be done.  Also, perhaps in your case you are not concerned about flat, mobile routing but are envisioning a centralized or hybrid structure.  I believe there will be such hybrid systems out there and manet routing need not be appropriate for more static pieces of the infrastructure.  Use the routing protocol that makes sense for your scenario.

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

Yes, I agree and I believe such tweaks to routing protocols can be done.

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

There is no quenching implicit as I see it.  The present TORA proposal for one, tries to limit overhead requirements for routing control information and constantly relearns routes on demand and under changing conditions.  Also, in highly mobile networks the concept of "best" route is debatable when stationarity is weak.  Minimizing routing reactions locally can make finding routes technically possible when they otherwise may never be found.  Still we have considered enhancements which add more protocol overhead to optimize routes when this seems sensible and time/overhead allowed in the network.  Once again, this is an enhancement and you pay an overhead/bandwidth penalty. The good news is the penalty may be alot less than for ILS style approaches. 

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

I agree it is unlikely there is a single solution for all scenarios.
This wording was bad in the charter and is being subbmitted to the Area Director for modification. The new charter and milestones were presented at the recent D.C. IETF.  I hope that clears the issue up.  What we don't want is two standard approaches that solve the same scenario problems. Likely some proposals will work better than other protocols over particular scenarios. Multiple standard solutions that solve separate scenarios well is acceptable.

BTW, as you mention size, topology, and rate of change as scenario metrics, in addition there is bandwidth, traffic patterns, loss statistics and a host of others... 

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

I have been very personally interested in this problem, but we are getting into some broad issues here.  Alas, in manet we are an Internet Protocol working group and must not concentrate on what is appropriate for other standards bodies or forums. You mention the tremendous richness of the link layer design space and this remains an ongoing topic and R&D process.  We are only looking at a routing piece of the bigger mobile standards and networking puzzle, but the need or lack thereof for enhanced standardized link layer interfaces is important and fits in.  Such interface specifications would be useful in the context of how enhanced lower layers work/communicate with an Internet routing layer and if defined and implemented are appropriate within this WG.  I would encourage more work here would you like to contribute an ID or implementation?

-Joe