Subject: repost again...

From: "M. Scott Corson" <[email-masked]>
Date: Fri, 22 Aug 1997 10:15:57 -0400 (EDT)

Sorry folks.  I understand that the attachment of the previous
draft repost was messed up.  Here it is below.

-Scott

*******************************************************************************

M. Scott Corson                                 Institute for Systems Research
[email-masked]                              A.V. Williams Bldg. (115)
Phone: 301-405-6630 (Rm. 2205 AVW)              University of Maryland     
Fax:   301-314-8586                             College Park, MD  20742

*******************************************************************************

Network Working Group                                          S. Corson
Internet-Draft                                    University of Maryland
Expires: February 1998                                         J. Macker
                                               Naval Research Laboratory
                                                             August 1997

                   Mobile Ad hoc Networking (MANET):
Routing Protocol Performance Issues and Evaluation Considerations

Status of this Memo

   This document is an Internet-Draft.  Internet-Drafts are working do-
   cuments of the Internet Engineering Task Force (IETF), its areas, and
   its working groups.  Note that other groups may also distribute work-
   ing documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet- Drafts as reference ma-
   terial or to cite them other than as "work in progress."

   To view the entire list of current Internet-Drafts, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).

   Distribution of this memo is unlimited.

Summary

   This memo describes the concept of mobile ad hoc networking--giving a
   rationale for its existence and outlining the unique issues and chal-
   lenges found in this form of purely wireless, mobile networking.

1. Introduction

   With recent performance advancements in computer and wireless commun-
   ications technologies, advanced mobile wireless computing is expected
   to see increasingly widespread use and application, much of which
   will involve the use of the Internet Protocol (IP) suite. The vision
   of mobile ad hoc networking is to support robust and efficient opera-
   tion in mobile wireless networks by incorporating routing functional-
   ity into mobile nodes.   Such networks are envisioned to have dynam-
   ic, sometimes rapidly-changing, random, multihop topologies which are
   likely composed of relatively bandwidth-constrained wireless links.

   Within the Internet community, routing support for mobile hosts is
   presently being formulated as "mobile IP" technology.  This is a
   technology to support nomadic host "roaming", where a roaming host
   may be connected through various means to the Internet other than its
   well known fixed-address domain space. The host may be directly phy-
   sically connected to the fixed network on a foreign subnet, or be
   connected via a wireless link, dial-up line, etc.  Supporting this
   form of host mobility (or nomadicity) requires address management,
   protocol interoperability enhancements and the like, but core network
   functions such as hop-by-hop routing still presently rely upon pre-
   existing routing protocols operating within the fixed network. In
   contrast, the goal of mobile ad hoc networking is to extend mobility
   into the realm of autonomous, mobile, wireless domains, where the
   nodes themselves form the network routing infrastructure in an ad hoc
   fashion.

   This memo first describes the characteristics of Mobile Ad hoc Net-
   works (MANETs), and their idiosyncrasies with respect to traditional,
   hardwired packet networks.  It then discusses the effect these
   differences have on the design and evaluation of network control pro-
   tocols with an emphasis on routing.

2. Applications

   The technology of Mobile Ad hoc Networking is somewhat synonomous
   with Mobile Packet Radio Networking (a term coined via during early
   military research in the 70's and 80's), Mobile Mesh Networking (a
   term that appeared in an article in The Economist regarding the
   structure of future military networks) and Mobile, Multihop, Wireless
   Networking (perhaps the most accurate term, although a bit cumber-
   some).

   There is current and future need for dynamic ad hoc networking tech-
   nology.  The emerging field of mobile and nomadic computing, with its
   current emphasis on mobile IP operation, should gradually broaden and
   require highly adaptive mobile networking technology to effectively
   manage multihop, ad hoc network clusters which can operate auto-
   nomously or, more than likely, be attached at some point(s) to the
   fixed Internet.

   Some applications of MANET technology could include industrial and
   commercial applications involving cooperative mobile data exchange.
   In addition,  mesh-based mobile networks can be operated as robust,
   inexpensive alternatives or enhancements to cell-based mobile network
   infrastructures. There are also existing and future military network-
   ing requirements for robust, IP-compliant data services within mobile
   wireless communication networks [1]--many of these networks consist
   of highly-dynamic autonomous topology segments. Also, the developing
   technologies of "wearable" computing and communications may provide
   applications for MANET technology. When properly combined with
   satellite-based information delivery, MANET technology can provide an
   extremely flexible method for establishing communications for
   fire/safety/rescue operations or other scenarios requiring rapidly-
   deployable communications with survivable, efficient dynamic network-
   ing. There are likely other applications for MANET technology which
   are not presently realized or envisioned by the authors.  It is, sim-
   ply put, efficient IP-based routing technology for highly dynamic,
   autonomous wireless networks.

3. Characteristics of MANETs

   A MANET consists of mobile platforms (combined router, host and wire-
   less communications platforms)--herein simply referred to as
   "nodes"--which are free to move about arbitrarily. The nodes may be
   located in or on airplanes, ships, trucks, cars, perhaps even on peo-
   ple, and there may be multiple hosts per router. A MANET is an auto-
   nomous system of mobile nodes.  The system may operate in isolation,
   or may have gateways to and interface with a fixed network--typically
   envisioned to operate as a stub network connecting to a fixed inter-
   network.

   The nodes are equipped with wireless transmitters and receivers using
   antennas which may be omnidirectional (broadcast), highly-directional
   (point-to-point) or some combination thereof. At a given point in
   time, depending on the nodes' positions and their transmitter and re-
   ceiver coverage patterns, transmission power levels and cochannel in-
   terference levels, a wireless connectivity in the form of a random,
   multihop graph or "ad hoc" network exists between the nodes.  This ad
   hoc topology may change with time as the nodes move or adjust their
   transmission and reception parameters.

   MANETs have several salient characteristics:

      1) Dynamic topologies: Nodes are free to move arbitrarily; thus,
      the network topology--which is typically multihop--may change ran-
      domly and rapidly at unpredictable times, and may consist of both
      bidirectional and unidirectional links.

      2) Bandwidth-constrained, variable capacity links: Wireless links
      will continue to have significantly lower capacity than their
      hardwired counterparts. In addition, the realized throughput of
      wireless communications--after accounting for the effects of mul-
      tiple access, fading, noise, and interference conditions, etc.--is
      often very much less than a radio's maximum transmission rate.

      One effect of the relatively low to moderate link capacities is
      that congestion is typically the norm rather than the exception,
      i.e.  aggregate application demand will likely approach or exceed
      network capacity frequently. As the mobile network is often simply
      an extension of the fixed network infrastructure, mobile ad hoc
      users will demand similar services. These demands will continue to
      increase as multimedia computing and collaborative networking ap-
      plications rise.

      3) Power-constrained operation: Some or all of the nodes in a
      MANET may rely on batteries for their energy. For these nodes, the
      most important system design criteria for optimization may be
      power conservation.

      4) Limited physical security: Mobile wireless networks are gen-
      erally more prone to physical security threats than are fixed-
      cable nets.  The increased possibility of eavesdropping, spoofing,
      and denial of service attacks should be carefully considered.  Ex-
      isting link security techniques are often applied within wireless
      network to reduce security threats. As a benefit, the decentral-
      ized nature of network control in MANETs provides additional
      robustness against single points of failure of more centralized
      approaches.

   In addition, some envisioned networks (e.g. mobile military networks
   or highway networks) may be relatively large (e.g. tens or hundreds
   of nodes per routing area).  The need for scalability is not unique
   to MANETS. However, in light of the preceding characteristics, the
   mechanisms required to achieve scalability likely are.

   These characteristics create a set of underlying assumptions and per-
   formance concerns for protocol design which extend beyond those guid-
   ing the design of routing within the higher-speed, semi-static topol-
   ogy of the fixed Internet.

4. Goals of IETF Mobile Ad Hoc Network (manet) Working Group

   The intent of the newly formed IETF manet working group is to develop
   a peer-to-peer mobile routing capability in a purely mobile, wireless
   domain.  This capability will exist beyond the fixed network (as sup-
   ported by traditional IP networking) and beyond the one-hop fringe of
   the fixed network.

   The near-term goal of the manet working group is to standardize an
   intra-domain unicast routing protocol which:

      * provides a mode(s) of operation for effective operation in a
      mobile networking "context". (a context is a set of defined net-
      working characteristics),

      * provides a standard "mode discovery" protocol so that newly-
      arriving nodes may learn the mode in which a given MANET is
      operating,

      * supports traditional, connectionless IP service,

      * reacts efficiently to topological changes while maintaining ef-
      fective routing in a mobile networking context.

   The working group will also address issues pertaining to security and
   interaction/interface with link-layer protocols and internet security
   protocols. In the longer term, the group may look at the issues of
   layering more advanced mobility services on top of the initial uni-
   cast routing developed.  These longer term issues will likely include
   investigating multicast and QoS extensions for a dynamic, mobile
   area.

5. Why Develop an IP-Layer Routing Solution?

   One can ask "why use an IP-layer routing solution when one based at
   the MAC layer can also work for a mobile subnet?"  The answer is that
   the intent here--in the context of mobile ad hoc networking--is the
   *same* as that for the original Internet, viz. "to develop an in-
   teroperable internetworking capability over a heterogeneous network-
   ing infrastructure". In this case, the infrastructure is wireless,
   rather than hardwired, consisting of multiple wireless technologies,
   channel access protocols, etc.  The separate wireless technologies
   form individual subnets.  As with the development of dual and
   triple-mode cellular phones, there are likely to be multimode wire-
   less devices capable of operating according to different link-layer
   standards.  These devices can form gateways between the subnets, and
   multiple subnets can co-exist simultaneously. IP routing and related
   networking services provide the glue to preserve the integrity of the
   mobile network.

6. MANET Routing Protocol Performance Issues

   To judge the merit of a routing protocol, one needs metrics--both
   qualitative and quantitative--with which to measure its suitability
   and performance.  These metrics should be somewhat *independent* of
   any given routing protocol.

   The following is a list of desirable qualitative properties:

      1) Distributed operation:  This is an essential property, but it
      should be stated nonetheless.

      2) Loop-freedom:  Not required per se in light of certain quanti-
      tative measures (performance criteria), but generally desirable to
      avoid problems such as worst-case phenomena, e.g. a small fraction
      of packets spinning around in the network for arbitrary time
      periods.  Ad hoc solutions such as TTL values can bound the prob-
      lem, but a more structured and well-formed approach is generally
      desirable as it oftentimes leads to better overall performance.

      3) Demand-based operation:  Instead of assuming uniform traffic
      distribution within the network (and maintaining routing between
      all nodes at all times), let the routing algorithm adapt to the
      traffic pattern on a demand or need basis.  If this is done intel-
      ligently, it will utilize network resources more efficiently.

      4) Unidirectional link support:  Bidirectional links are typically
      assumed in the design of routing algorithms, and many algorithms
      are incapable of functioning properly over unidirectional links.
      Nevertheless, unidirectional links can and do occur in wireless
      networks. Often times, a sufficient number of duplex links exist
      so that usage of unidirectional links is of limited added value.
      However, in situations where a pair of unidirectional links (in
      opposite directions) form the *only* bidirectional connection
      between two ad hoc clusters, the ability to make use of them is
      invaluable.

      5) Security: Without some form of network-level security or link
      layer security, a MANET routing protocol is vulnerable to many
      forms of attack.  It may be relatively simple to snoop network
      traffic, replay transmissions, manipulate packet headers, and
      redirect routing messages, within a wireless network without ap-
      propriate security provisions. While these concerns exist within
      wired infrastructures and routing protocols as well, maintaining
      the "physical" security of of the transmission media is harder in
      practice with MANETs. Sufficient security protection to prohibit
      distruption of modification of protocol operation is desired.
      This may be somewhat orthogonal to any particular routing protocol
      approach, e.g. through the application of IP Security techniques.

      6) "Sleep" period operation:  As a result of power conservation,
      or some other need to be inactive, nodes of a MANET may stop
      transmitting and/or receiving (even receiving requires power) for
      arbitrary time periods.  A routing protocol should be able to ac-
      comodate such sleep periods without overly adverse consequences.
      This property may require close coupling with the link layer pro-
      tocol through a standardized interface.

   The following is a list of quantitative metrics that can be used to
   assess the performance of any routing protocol.

      1) End-to-end data throughput and delay: Statistical measures of
      data routing performance (e.g., means, variances, distributions)
      are important. These are the measures of a routing policy's
      effectiveness--how well it does its job--as measured from the
      *external* perspective of other policies that make use of routing.

      2) Efficiency:  If data routing effectiveness is the external
      measure of a policy's performance, efficiency is the *internal*
      measure of its effectiveness.  To achieve a given level of data
      routing performance, two different policies may expend differing
      amounts of overhead, depending on their internal efficiency.  Pro-
      tocol efficiency may or may not directly affect data routing per-
      formance.  If control and data traffic must share the same chan-
      nel, and the channel's capacity is limited, then excessive control
      traffic may impact data routing performance.

      It is useful to track two ratios that illuminate the *internal*
      efficiency of a protocol in doing its job (there may be others
      that the authors have not considered):

         * Average number of data bits transmitted/data bit delivered--
         this can be thought of as a measure of the efficiency of
         delivering data within the network.

         * Average number of control bits transmitted/data bit
         delivered--this measures the efficiency of the protocol in ex-
         pending control overhead to delivery data packets.  Note that
         this should include not only the bits in the routing control
         packets, but also the bits in the header of the data packets.
         In other words, anything that is not data is control overhead,
         and should be counted in the control portion of the algorithm.

   Also, we must consider the networking *context* in which a protocol's
   performance is measured.  Essential parameters that should be varied
   include:

      1) Network size--measured in the number of nodes

      2) Network connectivity--the average degree of a node (i.e. the
      average number of neighbors of a node)

      3) Topological rate of change--the speed with which a network's
      topology is changing

      4) Link capacity--effective link speed measured in bits/second,
      after accounting for losses due to multiple access, coding, fram-
      ing, etc.

      5) Fraction of unidirectional links--how effectively does a proto-
      col perform as a function of the presence of unidirectional links?

      6) Traffic patterns--how effective is a protocol in adapting to
      non-uniform or bursty traffic patterns?

      7) Mobility--when, and under what circumstances, is temporal and
      spatial topological correlation relevant to the performance of a
      routing protocol?  In these cases, what is the most appropriate
      model for simulating node mobility in a MANET?

      8) Fraction and frequency of sleeping nodes--how does a protocol
      perform in the presence of sleeping and awakening nodes?

   A MANET protocol should function effectively over a wide range of
   networking contexts--from small, collaborative, ad hoc groups to
   larger mobile, multihop networks.  The preceding discussion of
   characteristics and evaluation metrics somewhat differentiate MANETs
   from traditional, hardwired, multihop networks.  The wireless net-
   working environment is one of scarcity rather than abundance, wherein
   bandwidth is relatively limited, and energy may be as well.

   In summary, the networking opportunities for MANETs are intriguing
   and the engineering tradeoffs are many and challenging.  A diverse
   set of performance issues requires new protocols for network control.
   A question which arises is "how should the *goodness* of a policy be
   measured?". To help answer that, we proposed here an outline of pro-
   tocol evaluation issues that highlight performance metrics that can
   help promote meaningful comparisons and assessments of protocol per-
   formance.  It should be recognized that a routing protocol tends to
   be well-suited for particular network contexts, and less well-suited
   for others. In putting forth a description of a protocol, both its
   *advantages* and *limitations* should be mentioned so that the ap-
   propriate networking context(s) for its usage can be identified.
   These attributes of a protocol can typically be expressed *qualita-
   tively*, e.g., whether the protocol can or cannot support shortest-
   path routing.  Qualitative descriptions of this nature permit broad
   classification of protocols, and form a basis for more detailed
   *quantitative* assessments of protocol performance. In future docu-
   ments, the group may put forth candidate recommendations regarding
   protocol design for MANETs. The metrics and the philosophy presented
   within this document are expected to continue to evolve as MANET
   technology and efforts mature.

6. References

[1] B. Adamson, "Tactical Radio Frequency Communication Requirements for
    IPng," RFC 1677, Aug. 1994.

Authors' Addresses

   M. Scott Corson
   Institute for Systems Research
   University of Maryland
   College Park, MD 20742
   (301) 405-6630
   [email-masked]

   Joseph Macker
   Information Technology Division
   Naval Research Laboratory
   Washington, DC 20375
   (202) 767-2001
   [email-masked]