INTERNET-DRAFT Thomas Clausen IETF MANET Working Group Pascale Minet Expiration: 9 August 2004 INRIA Rocquencourt, France Charles E. Perkins Nokia Research Center 9 February 2004 Multipoint Relay Flooding for Manets draft-perkins-manet-mprf-00.txt Status of this Memo This document is a submission by the Mobile Ad Hoc Networking Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the manet@itd.nrl.navy.mil mailing list. Distribution of this memo is unlimited. 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 This document describes the MultiPoint Relay Flooding (MPRF) protocol for maintenance of efficient flooding structures in mobile ad-hoc networks. The protocol is an adaptation of the classical flooding algorithm, with the difference that many nodes are relieved of the responsibility to relay flooded messages while still ensuring that all nodes receive the messages. The key concept used in the protocol is that of multipoint relays (MPRs). MPRs are selected nodes which are the only nodes needed to forward messages during the flooding process. This technique substantially reduces the message overhead as compared to the more straightforward and well-known flooding mechanism, where every node retransmits each message just once, upon receiving the first copy of the message. The protocol is particularly suitable for dense networks. Clausen, Minet, Perkins MPRF [Page 1] INTERNET-DRAFT MPRF 1 August 2004 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. MPRF Terminology . . . . . . . . . . . . . . . . . . . . . 5 1.2. Applicability Section . . . . . . . . . . . . . . . . . . 6 1.3. Protocol Overview . . . . . . . . . . . . . . . . . . . . 7 2. MPRF Protocol Details . . . . . . . . . . . . . . . . . . . 8 2.1. Broadcast Processing and Message Flooding . . . . . . . . 9 2.2. MPRF Message Types . . . . . . . . . . . . . . . . . . . . 10 2.2.1. Message Emission and Jitter . . . . . . . . . . . . . . 10 2.3. Identification for Flooded Packets . . . . . . . . . . . . 11 2.4. Unique Identifier Destination Option . . . . . . . . . . . 12 2.5. Neighbor Solicitation Message Format . . . . . . . . . . . 12 2.5.1. Neighbor Advertisement Message Format . . . . . . . . . 13 2.5.2. Neighborhood Information Base . . . . . . . . . . . . . 14 2.5.2.1. Symmetric Neighbor Set . . . . . . . . . . . . . . . . 15 2.5.2.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . 15 2.5.2.3. MPR selector set . . . . . . . . . . . . . . . . . . . 15 2.5.3. Neighbor Advertisement Message Generation . . . . . . . 15 2.5.4. Neighbor Advertisement Message Processing . . . . . . . 16 3. Multipoint Relay Selection . . . . . . . . . . . . . . . . . 17 4. Proposed Values for the Constants . . . . . . . . . . . . . 20 5. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 20 Clausen, Minet, Perkins MPRF [Page 2] INTERNET-DRAFT MPRF 1 August 2004 Clausen, Minet, Perkins MPRF [Page 3] INTERNET-DRAFT MPRF 1 August 2004 1. Introduction The MultiPoint Relay Flooding protocol for Manets (MPRF) is a proto- col for reducing the overhead due to flooding in MANETs. MPRF operates by identifying a set of nodes called "multipoint relays" (MPRs) [1][2]. A node, N, selects a subset of its neighbors as MPRs. These MPRs are selected to ensure that a flooded message, emitted by node N and retransmitted by its MPRs, will be received by all the nodes which are two hops away from N. Every node in the net- work is a neighbor of some MPR, and every node (and every MPR) has an MPR among its set of neighbors. Thus, flooded messages are relayed by MPRs until the whole network has been covered. MPRF is developed to work independently from other protocols. MPRF can take advantages of various features that might be provided by a given link layer, and requires only that a node has the ability to transmit a message to all of its neighbors. This can be done by way of a broadcast primitive, or in the less efficient case by way of iterated unicast. MPRF operates by establishing state in the nodes of the ad hoc net- work. The MPRs accept the responsibility for retransmitting messages that are meant to be flooded. The messages themselves often may require processing and possible modifications to the message payload before retransmission. For such messages, the TTL value in the IP header MUST be set to 1, and the destination IP address MUST be set to the "All-Manet-Neighbors" multicast address. If there are mes- sages which do not require any modifications outside the IP header, they MAY be addressed to the "All-Manet-Nodes" multicast address, and the TTL set to a value larger than 1. The set of MPRs does not depend on whether or not the TTL is larger than 1. Note that many flooding algorithms will attempt to limit the spread of the flooded signaling by using an "expanding rings" search tech- nique. For these algorithms to work well with MPRF, the ring radius should be a parameter under control of the protocol algorithm, not the TTL parameter in the IP header. DISCUSSION: Should TTL > 1 be allowed when protocol processing would modify the payload? According to the algorithms presented in this document, the set of neighboring MPRs selected by a particular MPR node for relaying flooded packets is dependent on the particular MPR node running the algorithm. So, when a neighboring node receives a flooded packet, it must identify which of its neighbors transmitted the packet before Clausen, Minet, Perkins MPRF [Page 4] INTERNET-DRAFT MPRF 1 August 2004 determining whether to relay the flooded packet. When TTL is larger than one, the transmitter cannot be identified by the value of the source IP address of the flooded packet. In this situation, the appropriate action depends on whether the node receiving the flooded packet can identify the transmitter from the MAC address of the layer-2 framing for the payload. If the identification can be made, then the node has to keep track of the MAC address of its neighbors as well as their IP address to enable the identification. This is already done for many physical media such as Ethernet or WLAN, so no special arrangements are needed in these typical cases. Otherwise, flooded packets can be encapsulated for reliable identification of the originator of the flooded packet. DISCUSSION: Should the flooding ALWAYS work by way of encapsulation? IP-in-IP encapsulation? Or, is it better to attempt an MPR selection algorithm that does NOT depend on the selector node? The set of MPR nodes is selected based in information provided by periodic neighbor advertisements. In order to be compatible with network deployments in which some nodes are not MPR aware, by default every node in the network is an MPR. Thus, the MPR selection algo- rithm can be viewed as a "pruning" operation during which some nodes are relieved of their responsibility to retransmit broadcasts from some of their neighbors. 1.1. MPRF Terminology The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [5]. The MPRF protocol uses the following terminology: multipoint relay (MPR) A node which is selected by its one-hop neighbor, node X, to "re-transmit" all the flooded messages that it receives from X, provided that the same message is not already received, and the time to live field of the mes- sage is greater than one. multipoint relay selector (MPR selector) A node which has selected its one-hop neighbor, node X, as its multipoint relay, will be called a multipoint relay selector of node X. Clausen, Minet, Perkins MPRF [Page 5] INTERNET-DRAFT MPRF 1 August 2004 node A MANET router which supports this MPRF protocol. link A link is a physical medium which can carry data between a pair of network interfaces (from two different nodes). A node is said to have a link to another node when one of its network interfaces can use a link to transmit data to one of the network interfaces of the other node. symmetric link A confirmed (through neighbor sensing or otherwise) bi- directional link between two nodes. symmetric neighbor A node X is a symmetric neighbor of node Y if there exists a symmetric link between node X and Y. symmetric neighborhood The symmetric neighborhood of any node X is the set of nodes which have at least one symmetric link to X. symmetric 2-hop neighborhood The symmetric 2-hop neighborhood of X is the set of nodes which don't have a symmetric link to X but have a symmet- ric link to a node belonging to the symmetric neighbor- hood of X. 1.2. Applicability Section MPRF is a protocol for identifying MPRs. This optimization is well suited for dense wireless networks. The larger and more dense a net- work, the more optimization can be achieved as compared to the clas- sic flooding algorithm. In very small networks, or in sparse net- works, little or no performance improvement may be achieved by use of this technique. MPRF is designed to carry flooded control or data traffic. This is specifically intended to include Topology Control messages in OLSR [pick one 6,7,8] or TBRPF[citation needed], and Route Requests in AODV [9] or DSR [10]. MPRF is designed such that it can operate independantly from other Clausen, Minet, Perkins MPRF [Page 6] INTERNET-DRAFT MPRF 1 August 2004 protocols and does not rely on specific features from the underlying link layer except for the ability to transmit broadcast packets. If certain functionalities (e.g. neighbor sensing) are provided by the link layer or by other protocols, they may be utilized. The MPRF algorithm requires the receiver of a flooded packet to iden- tify of the transmitter for that flooded packet. Only in this way can the receiver determine whether or not it should further dissemi- nate the packet to all of the nodes in its own neighborhood. For flooded packets that have TTL larger than one, there are two sub- cases: 1. ALL of the nodes in the neighborhood of the forwarding node can detect the framing address (MAC address) of the forwarding node. 2. One of the nodes in the neighborhood of the forwarding node CANNOT detect the framing address (MAC address) of the forwarding node. In the latter case, the forwarding node MUST take action so that all of its neighbors can identify it as the source of the newly retrans- mitted packet. 1.3. Protocol Overview MPRF reduces the overhead from flooding by identifying selected nodes, called Multipoint Relays (MPRs), to retransmit flooded pack- ets. This technique significantly reduces the number of retransmis- sions required to flood a message to all nodes in the network. Multipoint relays minimize the overhead of flooding messages in the network by reducing duplicate retransmissions. Each node in the net- work selects a set of nodes in its symmetric neighborhood which may retransmit its messages. This set of selected neighbor nodes is called the "Multipoint Relay" (MPR) set of that node. The neighbors of node N which are *NOT* in its MPR set, receive and process flooded messages but do not retransmit flooded messages received from node N. Each node selects its MPR set among its one hop symmetric neighbors. This set is selected such that it covers (in terms of radio range) all nodes that are two hops away. The MPR set of N, denoted as MPR(N), is then a subset of the symmetric neighborhood of N which is only constrained to satisfy the following condition: every node in the symmetric 2-hop neighborhood of N must have a symmetric link to a node belonging to MPR(N). In general, the smaller the MPR set is, Clausen, Minet, Perkins MPRF [Page 7] INTERNET-DRAFT MPRF 1 August 2004 the less congestion will be created by flooding operations. For an analysis and example of MPR selection algorithms, see [2]. Each node maintains information about the set of neighbors that have selected it as MPR. This set is called the "Multipoint Relay Selec- tor set" (MPR selector set) of a node. A node obtains this informa- tion from periodically transmitted Neighbor Advertisement messages received from the neighbors. A flooded message, intended to be disseminated across the whole net- work, coming from any of the MPR selectors of node N is expected to be retransmitted by node N. 2. Protocol Details This section describes details about how MPRF functions. This includes descriptions of the format and contents of the packets being exchanged as well as the algorithms operating in each node in the network. The "Packet Forwarding" mechanism is used by MPRs to accomplish the flooding of packets. For this to function, the MPRs have to be selected and made aware that they have been selected to function as MPRs. For this, a neighbor advertisement mechanism and an MPR selec- tion algorithm are required. Through the neighbor advertisement mechanism, a node advertises its symmetric neighborhood as well as its MPR selection to neighboring nodes. With this information, each node can build up both its sym- metric neighborhood and its symmetric 2-hop neighborhood (for MPR selection). Using this information, the node must its selected MPR nodes and subsequently inform those MPR nodes that they have been selected. Neighbor advertisements provide each node with the addresses of its symmetric neighbors. This list may instead be provided by a neighbor sensing protocol, such as used in the proactive protocols [8], or by any link-layer mechanism, or by tabulating the neighbors from which Neighbor Advertisements are received with an indication that the nodes can detect each others' messages. The MPR selection algorithm specifies the conditions that each node must satisfy. Some heuristics are also provided for selecting MPRs. Clausen, Minet, Perkins MPRF [Page 8] INTERNET-DRAFT MPRF 1 August 2004 2.1. Broadcast Processing and Message Flooding To avoid unnecessary retransmission of a message which was already received, processed, and retransmitted, each node maintains a table of packets which have been transmitted to "All-Manet-Neighbors". In this table, called the node's "Flooding History" table, the node records information about the most recently received messages. This includes the source_addr, where source_addr is the originator address of the message, and a value called the Flooded Packet Identifier (FPI), which is a number uniquely identifying the flooded message. See section QQQ1 for details about computing the FPI for broadcast messages. In this section, the term "Originator Address" will be used for the main address of the node which sent the message. The term "Sender Interface Address" will be used for the sender address (given in the IP header of the packet containing the message) of the interface which sent the message. For messages with TTL = 1, these addresses are the same. Upon receiving a flooded packet, a node performs the following tasks: 1. If the TTL of the message is equal to '0' (zero), the message MUST silently be dropped. 2. If there exists an entry in the Flooding History such that source_addr == Originator Address, AND FPI == derived from packet data as in section QQQ1 then the message has already been completely processed and MUST silently be ignored. 3. Otherwise, if the node does not implement the message type of the message, and if TTL == 1, then the node MUST silently dis- card the message. 4 Otherwise, if the sender of the message is not detected to be in the symmetric neighborhood of the node, the message MUST silently be dropped. 5 Otherwise, if the message is addressed to All-Manet-Nodes, the message is processed according to the specifications for the message type, and Clausen, Minet, Perkins MPRF [Page 9] INTERNET-DRAFT MPRF 1 August 2004 5.1 an entry in the Flooding History is recorded with: source_addr = originator address the FPI (see section 2.3) 5.2 If the sender is an MPR selector of this node and if the time to live of the message is greater than '1', the mes- sage MUST be forwarded according to the following by broadcasting it on all interfaces that have symmetric neighbors other than the sender, with the TTL of the mes- sage reduced by one. When TTL=1 (and destination = All-Manet-Nodes) forwarding (and set- ting the correct message header in the forwarded, known, message) is the responsibility of the algorithm specifying how the message is to be handled. This enables, e.g., a message type to be specified such that the message can be modified while in transit (e.g. to reflect the route the message has taken). 2.2. MPRF Message Types The following message types are specified for MPRF. - Neighbor Solicitation message, for the case when a node has missed one of the Advertisement messages from one of its neighbors since the last full advertisement from that neighbor - Neighbor Advertisement messages, which announce symmetric neighbors and MPR selection. Each symmetric neighbor of any node N must be advertised by node N at least once per N_ADV_INTERVAL. These messages are carried over ICMP, or ICMPv6, with two new ICMP type values to be allocated by IANA. 2.2.1. Message Emission and Jitter As a basic implementation requirement, synchronization of flooded messages SHOULD be avoided. As a consequence, periodic messages SHOULD be emitted at slightly variable times. Emission of control traffic from neighboring nodes may, for various reasons (mainly timer interactions with packet processing), become Clausen, Minet, Perkins MPRF [Page 10] INTERNET-DRAFT MPRF 1 August 2004 synchronized such that several neighbor nodes attempt to transmit control traffic simultaneously. Depending on the nature of the under- lying link-layer, this may or may not lead to collisions and hence message loss - possibly loss of several subsequent messages of the same type. To avoid such synchronizations, the following simple strategy for emitting control messages is proposed. A node MAY add an amount of jitter to the interval at which messages are generated. The jitter must be a random value for each message generated. Thus, for a node utilizing jitter: Actual message interval = MESSAGE_INTERVAL - rnd_jitter where rnd_jitter is a value, randomly selected from the interval [0,MAXJITTER] and MESSAGE_INTERVAL is the value of the message inter- val specified for the message being emitted. Jitter MAY also be introduced when forwarding messages. The follow- ing simple strategy may be adopted: when a message is to be forwarded by a node, it should be delayed by the node during a short random period of time in the range [0,MAXJITTER]. This specification imposes a minimal rate of control message emis- sion. However, a node MAY send control messages at a higher rate (e.g. in cases of high mobility). Tuning the rate of protocol con- trol traffic to operational conditions is an implementation issue. 2.3. Identification for Flooded Packets Every node maintains a list to keep track of which flooded packets have already been received and retransmitted. The list contains, for each distinct flooded packet received, a value called the Flooded Packet Identifier (FPI). For IPv4, this FPI is composed of the source IP address, the IP ident value, and the fragment offset values obtained from the IP header of the flooded packet. For IPv6, the FPI is calculated as specified as follows. To obtain the FPI for IPv6 packets, a node uses MD5 [RFC 1321] to perform the following calculation for the incoming flooded packet: FPI = MD5 (IPv6 packet data). The IP packet data includes all non-mutable IPv6 headers and exten- sions, as well as any higher-level protocol data. The source node for each flooded packet MUST ensure that this FPI is distinct from the FPI from every other flooded packet which the node has Clausen, Minet, Perkins MPRF [Page 11] INTERNET-DRAFT MPRF 1 August 2004 transmitted during the last BROADCAST_RECORD_TIME. In the unlikely event that the FPI value is identical to some such recently transmit- ted packet, the source node MUST add a Unique Identifier Destination Option to the flooded packet (see section 2.4). 2.4. Unique Identifier Destination Option The Unique Identifier option is encoded in type-length-value (TLV) format as follows: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Option Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Uniquifying Value | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type TBD Option Length 2 Uniquifying Value The 16-bit Uniquifying Value is chosen to make the flooded packet FPI computation different than that for any other flooded packet from the same source node. The Unique Identifier MUST be placed in the Destination Options before the Routing Header (and, thus, before the fragment header). This allows proper handling by all intermediate forwarding nodes. 2.5. Neighbor Solicitation Message Format The format of a Neighbor Solicitation is as follows: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Clausen, Minet, Perkins MPRF [Page 12] INTERNET-DRAFT MPRF 1 August 2004 This is sent as the data-portion of the general packet format described in the Packet Format and Forwarding section, with the "Mes- sage Type" set to NEIGHBOR_SOLICITATION and the TTL field set to 1 (one). 2.5.1. Neighbor Advertisement Message Format To accommodate the above requirements, as well as to accommodate for future extensions, an approach similar to the overall packet format is taken. Thus the proposed format of a Neighbor Advertisement mes- sage is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # of MPRs |# of Non-MPRs|# of LostNbrs|I| Rsvd | Seq# | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MPR Addresses... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Other Non-MPR Neighbor Addresses... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Lost Neighbor Addresses... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : : This is sent as the data-portion of the general packet format described in the Packet Format and Forwarding section, with the "Mes- sage Type" set to NEIGHBOR_ADVERTISEMENT and the TTL field set to 1 (one). # of MPRs The number of IP addresses in the list following that belong to nodes that have been chosen as Multipoint Relays # of Non-MPRs The number of IP addresses in the list following that belong to nodes that have not been chosen as Multipoint Relays. For incremental advertisements, this includes those nodes that were formerly chosen as MPRs, but during the recent reselec- tion of MPRs were deselected. Clausen, Minet, Perkins MPRF [Page 13] INTERNET-DRAFT MPRF 1 August 2004 # of LostNbrs The number of IP addresses in the list following that belong to nodes that were previously neighbors but have been "lost" (i.e., are no longer detectable within the neighborhood). Seq# The Seq# for this advertisement is incremented by one for every advertisement. 'I' The 'I' flag specifies whether the advertisement is an Incre- mental advertisement or a Full advertisement. If the 'I' flag is zero, the number of Lost neighbors MUST be zero. Rsvd Ignored on reception; MUST be set to 0 on transmission. The sequence number of a full Advertisement MUST be at least 5 greater than the sequence number of the last incremental Advertise- ment which was broadcast by the node, and one greater than the last full Advertisement which was broadcast. If a node receives an Advertisement which contains a sequence number which is more than 5 greater than the sequence number in the last advertisement (modulo 64), then the node may have missed a full advertisement, and MUST transmit a Neighbor Solicitation to the source of the Advertise- ment. 2.5.2. Neighborhood Information Base Each node maintains an information base, consisting of a symmetric neighbor set, a 2-hop neighbor set and an MPR selector set. The symmetric neighbor set is populated by a neighbor sensing mecha- nism, which can be external to MPRF, or which can just consist of keeping track of the periodic transmissions of Neighbor Advertisement messages. The 2-hop neighbor set and the MPR selector set are both populated as a result of Neighbor Advertisement message exchange. Clausen, Minet, Perkins MPRF [Page 14] INTERNET-DRAFT MPRF 1 August 2004 2.5.2.1. Symmetric Neighbor Set A node stores, for each entry in its symmetric neighbor set, a "Sym- metric Neighbor Tuple" (node_addr, exp_time) where node_addr is the address of a neighbor which has been detected to be symmetric, and exp_time specifies the time at which this tuple expires and *MUST* be removed. In a node, the set of Symmetric Neighbor Tuples are denoted the "Symmetric Neighbor Set". 2.5.2.2. 2-hop Neighbor Set A node maintains a set of "2-hop tuples" (node_addr, N_2hop_addr, exp_time), describing symmetric links between nodes in its symmetric neighbor set and the symmetric 2-hop neighborhood. 'node_addr' is the address address of a symmetric neighbor, N_2hop_addr is an address of a 2-hop neighbor with a symmetric link to the neighbor with address node_addr, and exp_time specifies the time at which the tuple expires and *MUST* be removed. This information is gathered from the Neighbor Advertisement messages received by a node from its neighbor nodes. In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor Set". 2.5.2.3. MPR selector set A node, N, stores, for each neighbor which has selected node N as MPR, a "MPR selector tuple" (MPR_addr, MPR_time) where MPR_addr is the address of a neighbor which has selected node N as MPR and MPR_time specifies the time at which this tuple expires and *MUST* be removed. This information is used when deciding if an incoming message is to be forwarded or not. 2.5.3. Neighbor Advertisement Message Generation The list of nodes contained in an Neighbor Advertisement message can be partial (e.g. due to message size limitations, imposed by the net- work). However, every MPR selected by a node must be advertised at least once during N_ADV_INTERVAL. Notice that for limiting the impact from loss of control messages, it is desirable that a message (plus the generic package header) can fit Clausen, Minet, Perkins MPRF [Page 15] INTERNET-DRAFT MPRF 1 August 2004 into a single layer-2 frame. The use of incremental advertisements in networks of moderate mobilty is expected to substantially reduce the need for large-sized Advertisement messages. Each Neighbor Advertisement message generated is broadcasted on each MANET interface of the node. 2.5.4. Neighbor Advertisement Message Processing Upon receiving a Neighbor Advertisement message, the node SHOULD update its symmetric 2-hop neighbor set and MPR selector set. If the advertisement is an incremental Advertisement, the content of the last full Advertisement is revised according to the information pro- vided in the incremental Advertisement. The symmetric 2-hop neighbor set should be updated as follows: For each neighbor, listed in the Neighbor Advertisement message with a status of MPR or SYM_LINK a 2-hop tuple is created or updated with: node_addr = Originator Address; N_2hop_addr = the interface address of the 2-hop neigh- bor; exp_time = current time + 2HOP_HOLD_TIME. For each 2-hop node, listed in an incremental Advertisement message with a status of LOST_LINK, the 2-hop tuple with node_addr == Sender Address N_2hop_addr == the 2-hop node address is deleted. If a node finds itself in the Neighbor Advertisement message, listed with a link type of "MPR", it MUST update the MPR selector set as follows: Clausen, Minet, Perkins MPRF [Page 16] INTERNET-DRAFT MPRF 1 August 2004 If there exists no MPR selector tuple with MPR_addr == Sender Address a new tuple is created with: MPR_addr = Sender Address MPR_time = current time + MPR_HOLD_TIME otherwise, if a tuple exists where M_addr == Sender Address, it is updated as follows: MPR_time = current time + MPR_HOLD_TIME 3. Multipoint Relay Selection MPRs are used to flood control messages from a node into the network while reducing the number of retransmissions that will occur in a region. Thus, the concept of MPR is an optimization of a classical flooding mechanism. Each node in the network selects, independently, its own set of MPRs among its symmetric neighborhood. The neighbor nodes, selected as MPR, are announced to the neighborhood using Neighbor Advertisement messages as described in the previous section. The MPR set MUST be calculated by a node in such a way that it, through the neighbors in the MPR-set, can reach all symmetric 2-hop neighbors which are not at the same time symmetric neighbors of the node. This means that the union of the symmetric neighborhoods of the MPR nodes contains the symmetric 2-hop neighborhood. While it is not essential that the MPR set is minimal, it is essen- tial that all 2-hop neighbors can be reached through the selected MPR nodes. A node SHOULD select an MPR set such that any 2-hop neighbor is covered by at least MPR_COVERAGE MPR nodes. With MPR_COVERAGE=1 the overhead of the protocol is kept at a minimum. In presence of mobility and link failure, an MPR_COVERAGE=2 could provide a more redundant connectivity, for example to support a link failure without rerouting. Notice that MPR_COVERAGE can be tuned locally without affecting the consistency of the protocol. For example, a node can set MPR_COVER- AGE=2 if it observes many changes in its neighbor information base caused by mobility, while otherwise keeping MPR_COVERAGE=1. The Clausen, Minet, Perkins MPRF [Page 17] INTERNET-DRAFT MPRF 1 August 2004 fractional part of MPR_COVERAGE, if nonzero, specifies the likelihood for transmitting another broadcast. For instance, when MPR_COVERAGE = 1.4, there is a 40% chance that the node will transmit the broad- cast twice, and a 60% chance that the node will transmit the broad- cast only once. By default, the MPR set can coincide with the entire symmetric neigh- bor set. This will be the case at network initialization (and will correspond to classic flooding). The following specifies a proposed heuristic for selection of MPRs [2]. The following terminology will be used in describing this algo- rithm (neighbors are identified by their main address and 2-hop interfaces by their address): N: The set of neighbors with which there exists a symmetric link. N2: The set made of the symmetric 2-hop neighbors excluding (i) the node performing the computation, (ii) all the members of N, D(y): Degree of node y (where y is a member of N), defined as the number of symmetric neighbors of node y, EXCLUDING all the nodes which are of members of N and the node performing the computation. Poorly covered node: A poorly covered node is a node in N2 which is covered by (strictly) less than Floor(MPR_COVERAGE) nodes in N, where Floor(X) is the integer part of X. The proposed heuristic is as follows: 1 Start with an MPR set made of all members of N 2 Calculate D(y), where y is a member of N, for all nodes in N. 3 Select as MPRs those nodes in N which cover the poorly covered nodes in N2. The nodes are then removed from N2 for the rest of the computation. 4 While there exist nodes in N2 which are not covered by at least MPR_COVERAGE nodes in the MPR set: Clausen, Minet, Perkins MPRF [Page 18] INTERNET-DRAFT MPRF 1 August 2004 4.1 For each node in N, calculate the reachability, i.e. the number of nodes in N2 which are not yet covered by at least Floor(MPR_COVERAGE) nodes in the MPR set, and which are reachable through this one hop neighbor; 4.2 Select as a MPR a node with non zero reachability. In case of multiple choice take the node which which pro- vides reachability to the maximum number of those nodes in N2. In case of multiple nodes providing the same amount of reachability and reachability, select that node as MPR whose D(y) is greater. Remove from N2 the nodes that are now covered by Floor(MPR_COVERAGE) node in the MPR set. 5 As an optimization, process each node y in the MPR set; if all nodes in N2 are still covered by at least MPR_COVERAGE nodes in the MPR set excluding y, then remove node y from the MPR set. When the MPR set has been computed, all the corresponding main addresses are stored in the MPR Set. The outcome of the MPR calculation is a list of the neighbor nodes which have been selected as MPR. These are advertised through the Neighbor Advertisement messages, as previously described in section 2.5.1. MPR set recalculation should occur when changes are detected in the neighborhood or in the 2-hop neighborhood. A change in the neighbor- hood is detected when: - The exp_time field of a neighbor tuple expires. This is con- sidered as a neighbor loss. - A neighbor tuple is deleted according to the Neighbor Adver- tisement message processing section. This is also considered as a neighbor loss. - A new neighbor tuple is inserted in the Neighbor Set with a valid exp_time. A change in the 2-hop neighborhood is detected when a 2-hop neighbor tuple is inserted, or expires or is deleted according to the Neighbor Advertisement message processing section. The following processing should occur when changes in the neighbor- hood or the 2-hop neighborhood are detected: Clausen, Minet, Perkins MPRF [Page 19] INTERNET-DRAFT MPRF 1 August 2004 - In case of neighbor loss, all the 2-hop tuples with N_addr == main address of the lost neighbor are deleted. - In case of neighbor loss, all the MPR selector tuples with MPR_addr == main address of the neighbor are deleted - The MPR set is re-calculated when a neighbor appearance or loss is detected, or when a change in the 2-hop neighborhood is detected. - An additional Neighbor Advertisement message may be sent when the MPR set changes. 4. Proposed Values for the Constants This section list the values for the constants used in the descrip- tion of the protocol. MPR COVERAGE = 1 MAXJITTER = 0.5 seconds N_ADV_INTERVAL = 3 seconds 2HOP_HOLD_TIME = 2 seconds 5. Authors' Addresses Thomas Heide Clausen, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5133, Email: Thomas.Clausen@inria.fr Pascale Minet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 508832, Email: Pas- cale.Minet@inria.fr Charles E. Perkins, Communications Systems Laboratory, Nokia Research Center, 313 Fairchild Drive, Mountain View, CA 94303, USA, Phone: +1 650 625 2986, Email: charliep@iprg.nokia.com Clausen, Minet, Perkins MPRF [Page 20] INTERNET-DRAFT MPRF 1 August 2004 6. References 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia- bility in cable free radio LANs: Low level forwarding in HIPERLAN. Wireless Personal Communications, 1996 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. 35th Annual Hawaii International Conference on System Sciences (HICSS'2001). 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 1, functional specifications ETS 300-652, ETSI, June 1996 4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net- work Protocols, INRIA research report RR-3965, 2000 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev- els. Request for Comments (Best Current Practice) 2119, Internet Engineering Task Force, March 1997. 6. T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The Optimized Link State Routing Protocol, Evaluation through Experiments and Simulation. IEEE Symposium on "Wireless Personal Mobile Communica- tions", september 2001. 7. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum and L. Viennot. Optimized Link State Routing Protocol. IEEE INMIC Pakistan 2001. 8. T. Clausen, P. Jacquet, A. Laouiti, P. Minet, P. Muhlethaler, A. Qayyum and L. Viennot. Optimized Link State Routing Protocol, draft-ietf-manet-olsr-06.txt, work in progress, march 2002. 9. C. Perkins, E. Belding-Royer, S. Das. Ad hoc On-Demand Distance Vec- tor (AODV) Routing, draft-ietf-manet-aodv-09.txt, work in progress, november 2001 10. D. Johnson, D. Maltz, Y. Hu, J. Jetcheva. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks, draft-ietf-manet-dsr-06.txt, work in progress, november 2001