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]