
INTERNET-DRAFT                                                  K. Grace
IETF MANET Working Group                           The MITRE Corporation
Expiration: 22 March 2001                              22 September 2000


                      Mobile Mesh Routing Protocol
                     draft-grace-manet-mmrp-00.txt

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC 2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups. Note that other
   groups may also distribute working 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
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.


Abstract

   The Mobile Mesh Routing Protocol (MMRP) is a robust, scalable,
   efficient mobile adhoc routing protocol based upon the "link state"
   approach. MMRP is one protocol in a set of related Mobile Mesh
   protocols that also includes the Mobile Mesh Link Discovery Protocol
   (MMLDP) and the Mobile Mesh Border Discovery Protocol (MMBDP).
   Together, these protocols provide a flexible, extensible mobile adhoc
   networking capability.


1.  Introduction

   The Mobile Mesh Routing Protocol (MMRP) is a robust, scalable, and
   efficient mobile adhoc routing protocol based upon the "link state"
   approach. A node periodically broadcasts its own Link State Packet
   (LSP) on each interface participating in the protocol. LSP's are
   relayed by nodes, thus allowing each node to have full topology
   information for the entire adhoc network. From its topology database,
   a node is able to compute least cost unicast routes to all other
   nodes in the mobile adhoc network.

   An LSP indicates for each interface on the router, the addresses of
   neighbor interfaces that have links to it, and the associated cost of



Grace                                                   [Page 1]

INTERNET-DRAFT        Mobile Mesh Routing Protocol     22 September 2000


   these links.  Also in the LSP are a list of "External Route
   Advertisements" which enable the node to advertise routes into the
   mobile adhoc cloud for destinations that are "outside" of the mobile
   adhoc cloud.  One use of this mechanism is to allow routers
   possessing a wired connection to a fixed network to advertise a
   default route. This provides a mechanism for allowing mobile nodes to
   gain external connectivity. Also, this mechanism can be used by a
   wireless router to advertise a route for a collection of hosts which
   are directly connected to it.

   To enhance scalability, MMRP performs a technique known as fish-eye
   routing in which the resolution of a node's map of the network
   decreases as a function of hop distance from the node. This is
   achieved by decreasing the rate at which LSP's propagate across the
   network as they get farther away from their source. This effectively
   decreases the overhead associated with disseminating topology
   information. Also, this allows more recent LSP's to "catch up" and
   overwrite older LSP's as they propagate.

   MMRP is one protocol in a set of related Mobile Mesh protocols that
   also includes the Mobile Mesh Link Discovery Protocol (MMLDP) and the
   Mobile Mesh Border Discovery Protocol (MMBDP). Each of these are
   described in separate Internet Drafts. An aesthetically pleasing
   aspect of these protocols is that they each contain only a single
   message type. This form of simplicity, we believe, will enable others
   to easily understand and implement the protocols.


2.  Protocol Description

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC 2119].

   A node participating in the MMRP protocol MUST periodically broadcast
   its LSP message once every UPDATE_PERIOD seconds. The LSP message is
   a UDP datagram and MUST be sent to the limited IP broadcast address
   255.255.255.255. The UDP port number is configurable and SHOULD be
   the same for all nodes that desire participation in the adhoc
   network. In the future, it may be desirable to obtain a well-known
   port number for this protocol.










Grace                                                   [Page 2]

INTERNET-DRAFT        Mobile Mesh Routing Protocol     22 September 2000


   An LSP message has the following format:

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  Version = 1  |  Msg Type = 2 |                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           Router Id                           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Sequence Number                       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |             Age               |           Hop Count           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |         # Interfaces          |       # External Routes       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    Local Interface Address                    |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |           # Neighbors         |                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                   Neighbor Interface Address                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                   Neighbor Interface Metric                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                     ...
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                   Neighbor Interface Address                  |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                   Neighbor Interface Metric                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                                     ...
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    External Route Address                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                            Netmask                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                            Metric                             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                     ...
   The "Version" field enables future extensions to the protocol message
   and currently MUST be set to 1.

   The "Msg Type" field helps to ensure that non-LSP messages can be
   identified as such and it MUST be set to 2.

   The "Router Id" field is a globally unique number that identifies the



Grace                                                   [Page 3]

INTERNET-DRAFT        Mobile Mesh Routing Protocol     22 September 2000


   source of the LSP; this field MAY be set to one of the source node's
   IP interface addresses. This field MUST remain the same value across
   all LSP's sourced by a node. A relay node MUST NOT alter this field.

   The "Sequence Number" is used to distinguish a more recent LSP from
   an older one; this field MUST be incremented by one each time a node
   sends its own LSP. A relay node MUST NOT alter this field.

   The "Age" field indicates for how many seconds the LSP is valid
   before it MUST be discarded. A source node MUST set this field to the
   configurable parameter MAX_AGE. A relay node MUST decrement this
   field by the number of seconds the LSP has been stored at the relay
   prior to sending. This field takes on integer values representing
   whole seconds.

   The "Hop Count" indicates how many hops from the source the LSP has
   traveled. This field MUST be set to 0 by the source. A relay node
   MUST increment this field by one upon receiving the LSP.

   The "# Interfaces" field indicates how many interfaces on the source
   node are participating in the MMRP protocol. Each of these interfaces
   MUST have its address and associated list of neighbor interface
   addresses included in the LSP. A relay node MUST NOT alter this
   field.

   The "# External Routes" field indicates how many external route
   advertisements from the source node are included in the LSP. A relay
   node MUST NOT alter this field.

   Following the "#External Routes" field is a list of the source node's
   participating local interface addresses and their associated lists of
   neighbors. All addresses are 32 bit IPv4 addresses. All addresses
   listed in the LSP MUST be unique across the entire network. Each list
   of neighbors contains a "# Neighbors" field that MUST be set to the
   number of neighbors contained in the subsequent neighbor list. Each
   entry in the list of neighbors contains a "Neighbor Interface
   Address" and a "Neighbor Interface Metric". The "Neighbor Interface
   Metric" reflects the cost of the link from the neighbor interface to
   the source node's local interface. The link may or may not be
   bidirectional, however, all nodes MUST assume that it is
   unidirectional from the neighbor interface to the source node's local
   interface. MMRP does not specify a policy for how metrics should be
   assigned to links. Rather, it relies on whatever performs link
   discovery to provide a metric associated with each reported link. A
   relay node MUST NOT alter this list.

   Following the list of local interface addresses and their associated
   lists of neighbors, is a list of the source node's external route



Grace                                                   [Page 4]

INTERNET-DRAFT        Mobile Mesh Routing Protocol     22 September 2000


   advertisements. Each entry in the external route advertisement list
   contains an "External Route Address", a "Netmask", and a "Metric".
   Similar to entries in an IP route table, the "External Route Address"
   is logically AND'd with "Netmask" to define a range of IP addresses.
   "Metric" specifies the cost from the node to reach the range of IP
   addresses. External route advertisements enable a node to advertise
   routes into the mobile adhoc cloud for destinations that are
   "outside" of the mobile adhoc cloud. A relay node MUST NOT alter this
   list.

   Each node maintains a database containing the most recent LSP from
   each source. When a node receives an LSP it performs the following
   processing:

   - If the node's router id is the same as the "Router Id" field, it
     discards the message and is done processing.

   - If the "Age" field is 0, it discards the message and is done
     processing.

   - It increments the "Hop Count" field by 1.

   - It computes a delay that will be imposed on the LSP before it
     is relayed as:
                                                     hops
     delay = Max(MIN_TX_DELAY,Min(MAX_TX_DELAY,ALPHA^    ))

     where hops is the number of hops the LSP has traveled from its
     source, MIN_TX_DELAY and MAX_TX_DELAY are the configurable minimum
     and maximum delays, respectively, that will be imposed before
     relaying an LSP, and ALPHA is a configurable parameter which
     controls the rate at which the imposed delay grows as a function of
     the number of hops from the source.

     To avoid possible synchronization of relayed LSP's, jitter is added
     to the computed "delay". The jitter MUST be a random number
     uniformly distributed between 0 and (0.5 * delay). The actual time,
     then, when a node MUST relay the LSP is:

     txTime = currentTime + delay + jitter

   - If the node does not have an LSP in its database from the source,
     the node inserts the LSP into its database and remembers that the
     LSP needs to be relayed at the computed "txTime" and is done
     processing.

   - If the sequence number of the received LSP is greater than the
     sequence number of the stored LSP



Grace                                                   [Page 5]

INTERNET-DRAFT        Mobile Mesh Routing Protocol     22 September 2000


        OR
     if the sequence number of the received LSP is equal to the sequence
     number of the stored LSP and the hop count of the received LSP is
     less than the hop count of the stored LSP
        THEN
     the received LSP replaces the stored LSP and the node remembers the
     earlier of the "txTime" of the received LSP and the "txTime" of the
     replaced LSP.

   When a stored LSP's "txTime" arrives, the node MUST relay the LSP.

   A node MUST ensure that LSP's are not stored for longer than their
   Age field. Also, when a node relays an LSP, it MUST ensure that the
   Age field has been diminished by the amount of delay imposed by the
   node. One method for achieving these rules is to periodically
   decrement the Age field of all stored LSP's. If an Age field reaches
   zero, the LSP is removed from the database and discarded.

   At a minimum, a node MUST compute least cost routes and update its IP
   routing table once every UPDATE_PERIOD. The node MAY use any suitable
   algorithm such as Djykstra for the computation of least cost routes.

   An implementation MUST provide a mechanism that allows IP interfaces
   to be dynamically added and removed from the router without having to
   restart the router. This feature is important since it enables new IP
   interfaces to be utilized without causing the router to lose its LSP
   database. Also, if the router is a "border" router (ie. has a
   connection to a fixed network that is running the Mobile Mesh Border
   Discovery Protocol ), then any tunnel interfaces that are created by
   MMBDP can be readily added to the router.

   In order to simplify the task of assigning IP addresses, the tunnel
   interfaces created by MMBDP, for a single system, share a common IP
   address.  Since an LSP in MMRP identifies a router's interface solely
   by its IP address, it would be ambiguous for an LSP to list each
   MMBDP created tunnel interface separately. However, since packets
   sent/received on any of the tunnel interfaces are actually
   sent/received on the same fixed network interface, it is reasonable
   to aggregate all the tunnel interfaces and their respective neighbor
   lists into a single interface entry in the LSP. Therefore, an
   implementation of MMRP MUST aggregate local interfaces sharing a
   common address into a single local interface entry in its LSP. The
   neighbor list associated with this entry MUST contain the union of
   the neighbor addresses from the individual tunnel interfaces'
   neighbor lists.






Grace                                                   [Page 6]

INTERNET-DRAFT        Mobile Mesh Routing Protocol     22 September 2000


3.  Configurable Parameters

   The following are configurable parameters and their valid range of
   values:

    Parameter       Valid Range
     ALPHA          1.0 <= ALPHA <= 2.0
     MIN_TX_DELAY       >= 0 and <= MAX_TX_DELAY
     MAX_TX_DELAY       >= 0 and >= MIN_TX_DELAY
     MAX_AGE            >  0
     UPDATE_PERIOD      >  0

   Note, for ALPHA=1.0, the delay imposed by each node is independent of
   the number of hops; this is equivalent to traditional flooding.

   Due to the widely varying capabilities of wireless devices, MMRP does
   not recommend any default values. Factors which may or may not
   influence these values include the data rates of the links involved,
   anticipated network size, mobility rates, transmission ranges, desire
   to minimize overhead, and desire to reduce delay in discovering
   routes.

   In addition, the UDP port number to which all packets are sent and
   received is configurable.


4.  Security Considerations

   MMRP does not specify any particular security mechanism. It is
   important to ensure that in environments requiring security, adequate
   mechanisms are employed to authenticate messages. IPSec may provide a
   reasonable solution for these environments.


5.  References

   [RFC2119] S. Bradner.  Key words for use in RFCs to Indicate Requirement
             Levels.  Request for Comments (Best Current Practice) 2119,
             Internet Engineering Task Force, March 1997.












Grace                                                   [Page 7]

INTERNET-DRAFT        Mobile Mesh Routing Protocol     22 September 2000


6.  Author's Address

   Kevin H. Grace
   The MITRE Corporation
   202 Burlington Road
   Bedford, MA  01730
   (781) 271-8388
   EMail: kgrace@mitre.org











































Grace                                                   [Page 8]
