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