Subject: Bluetooth IP Connections

From: Declan Quinn <[email-masked]>
Date: Fri, 16 Mar 2001 09:45:56 -0000

Hi,

I am looking for a simple method to set up IP addresses and ARP on the Ericsson BDKs.

Also, is there a list of commands that can be used for device discovery and quality of the link.

Thanks,

Declan

---

From: [email-masked]
Date: Fri, 16 Mar 2001 17:56:37 +0100

Hi,

Please find below a pre-draft proposal about some optional modes (power
saving,  multicast, etc). This is presented for OLSR protocol only, but it
may be also useful for proactive schemes in general. We plan to make it a
short presentation during our slot on Monday. Comments are welcome. 

Please have a good week-end,
Philippe

PS: this document is not yet submitted to the IETF server (although it has
the format)

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

INTERNET-DRAFT                                         Thomas H. Clausen
IETF MANET Working Group                                Philippe Jacquet
Expiration: 16 September 2001                               Anis Laouiti  
                                                         Laurent Viennot
							   Pascale Minet
                                              INRIA Rocquencourt, France
                                                           16 March 2001

	  Optimized Link State Routing Protocol Extensions
               draft-ietf-manet-olsr-extensions-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 except that the right to
   produce derivative works is not granted.

   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 various extensions to the Optimized Link
   State Routing Protocol (OLSR) for mobile ad-hoc networks. The
   OLSR-protocol, as described in [1], contains basic functionalities
   required for routing packets in a mobile ad-hoc network. This
   document describes extensions to the basic protocol,
   i.e. additional functionalities or optimizations to existing
   functionalities in OLSR.

   The extensions are designed such that their usage is entirely
   optional. In a given network, some nodes may implement some (or
   all) of the described extensions, while others may not. Routing of
   traffic depends solely on compliance with [1], and while nodes MAY
   take advantage of the availability of various extensions, they
   MUST NOT assume such to be present in order for the network to
   operate.

                                Contents

Status of This Memo                                             

Abstract                                                        

  1. Introduction						
  2. Changes							
  3. Terminology						

  4. Power Conservation Extension				
       4.1 Purpose of the extension
       4.2 Terminology
       4.3 Extension overview
       4.4 Detailed operation
              4.4.1 PC-messages
	      4.4.2 Sleep mode initiation
	      4.4.3 Wake up procedure
       4.5 Compatibility issues
       4.6 Proposed vaules for constants
       
  5. Unidirectional Link Extension
       5.1 Purpose of the extension
       5.2 Terminology
       5.3 Extension overview
       5.4 Detailed operation
              5.4.1 Unidirectional Link Activation Message
	      5.4.2 Link information
	      5.4.3 Unidirectional Link Activation
	      5.4.4 Generating UDLA-messages
	      5.4.5 Generating HELLO-messages
	      5.4.6 Generating TC-messages
	      5.4.7 Routing table calculation
	      5.4.8 Unidirectional Link deactivation
       5.5 Compatibility issues
       5.6 Proposed values for constants

  6. Fast Moving Node Extension
       6.1. Purpose of the extension
       6.2. Terminology
       6.3. Extension Overview
       6.4. Neighbor sensing information base
              6.4.1 Neighbor information
              6.4.2 FAST-HELLO message format
              6.4.2.1 Description of the fields
              6.4.2.1 Regular HELLO messages
       6.5. Fast moving node extension operation
              6.5.1 FAST-HELLO message generation
              6.5.2 Fast moving node extension operation
       6.6. FAST-HELLO message processing
       6.7. Regular HELLO message processing
       6.8. Proposed values for the constants

   7. Multicast Extension
       7.1. Purpose of the extension
       7.2. Extension overview
       7.3. Terminology
       7.4. Tables
              7.4.1. MC_MPR_table
              7.4.2. MC_tree_table
              7.4.3. Multicast_routing_table
       7.5. Message format
              7.5.1. MC_CLAIM message
              7.5.2. SOURCE_CLAIM message
              7.5.3. CONFIRM_PARENT and LEAVE messages
       7.6. Detailed operation
              7.6.1- Requirements
              7.6.2. MC_CLAIM 
              7.6.3. SOURCE_CLAIM 
              7.6.4. Tree building
              7.6.5. Tree maintenance
              7.6.6. LEAVE messages
       7.7. Proposed value for the constants

  8. Gateway and Subnet Announcement Extension
       8.1 Purpose of the extension
       8.2 Terminology
       8.3 Extension overview
       8.4 Detailed operation
       8.5 Compatibility Issues
       8.6 Proposed valued for constants

 9. Message type overview
 10. References
 11. Authors Addresses

1. Introduction
 
   The OLSR protocol communicats through a unified packet format
   described in [1]. Each such packet is made up from a number of
   messages, each of which is identified by a message type, a
   specification of if this message should be forwarded or not, an
   offset to the next message and an uninterpreted data-portion. Upon
   recieving a packet, a node parses each message. The messages which
   have a message type known to the node are processed. Those
   messages, which have a message type unknown to the node, are
   either discarded or forwarded, depending on the status of the
   "forward" field and on the nodes selector set (only MPR's are
   allowed to forward messages). This procedure is described into
   details in [1], and provides the foundation for the extensions in
   this document.

   Extension to OLSR may be introduced in form of introduction of new
   message types. It is, however, important to observe that if a node
   does not recognize a recieved message type, no notifications are
   made to the sender or originator of the message and the recieving
   node will continiue to expect full compliance with [1].

   In this document, the following extensions are introduced: 

      - power conservation, 
      - unidirectional links, 
      - fast moving node, 
      - static neighborhood,
      - multicast,
      - gateway and subnet announcement,

2. Changes

   This is the initial version of this document.

3. Terminology

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECCOMENDED", "MAY", and "OPTIONAL" in
   this doccument are to be interpreted as described in RFC2119
   [2]. The terms "connection", "holding time" "multipoint relay",
   "MPR", "multipoint relay selector", "MPR selector", "MS", "node"
   and "symmetric link" as well as other terms relating to the
   functionality of OLSR are to be interpreted as described in
   draft-ietf-olsr-04.txt [2].

4. Power Conservation or Sleep mode operation

4.1. Purpose of the extension

   A power conservation mode is very desirable for low capacity,
   battery operated terminals. With a constraint on the available
   power, nodes may wish to conserve their battery power by entering
   "sleep mode". Sleep mode may simply be a pause in the operation of
   a node, or it may be some intermittent sleep and wake periods of a
   node to economically use its battery resources.

4.2. Terminology

   PC-node

	A node, implementing power conservation as described in this
	draft.

   Sleep mode

	A node is said to be in sleep mode when it - temporarily -
	has suspended its operation in the MANET without actually
	leaving the network (i.e. the node is still present as a
	destination in the routing tables of other nodes.)

4.3. Extension overview

   When a node is in sleep-mode, it is incapable of both receiving
   traffic and relaying traffic for other nodes, yet it still appears
   as a valid destination to the other nodes in the network. Thus
   before power sleep-mode, a node (which in that case is denoted a
   "sleepy node") MUST ensure that:

	 - it is not routing traffic for any other nodes
	 - some other nodes are instructed to maintain the sleepy nodes
	   presence in the network,
	 - some other nodes are instructed to queue incomming traffic 
	   for the sleepy node.

   To ensure this, a sleepy node halts emission of HELLO-messages and
   initiates negotiations with its neighbor nodes to make a set of
   these announce its presence and queue incomming traffic.
   
   When a node wishes to resume normal operation in the network, it
   resumes emission of HELLO-messages, and requests any queued
   packets be forwarded.
    
4.4. Detailed operation

4.4.1. PC messages

   The unit of information exchanged between the nodes as part of
   negotiating power conservations is power conservation messages
   (PC-messages). The proposed format of a PC message 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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Request/Reply |     Sleep period (in msec)    |   Reserved    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            Address                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                            Address                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This is sent as the data part of the general packet format
   described in [1] with the "Message Type" set to PC_MESSAGE and the
   ttl field set to 0 (i.e. broadcast to the neighborhood only).

4.4.1.1 Description of the fields

   Request/Reply
      
      Identification of the nature of the PC-message. If this field
      is set to REQUEST, it indicates that the message is a request
      for nodes to keep incomming data packets on behalf of the
      originator of the PC-message. If the field is set to REPLY, it
      indicates that the message is a confirmation from a node (the
      originator of the PC message), willing to keep incomming
      data. If the field is set to FORWARD, it indicates that the
      sender of the PC-message is requesting kept data to be
      forwarded.
 
   Sleep period   

      The period of time in milliseconds, which the node will be
      sleeping.
		
   Reserved

      Reserved for future use. Must be set to '00000000' to be in
      compliance with this version of the draft.

   Address

      The address of a node. This sequence of address fields are
      interpreted differently, depending on the value of the
      Request/Reply field.

4.4.2. Sleep mode initiation

   When a node plans to enter sleep mode, it has to stop sending its
   periodic control messages:

      - HELLO messages: so that it is no more selected as a multipoint
        relay by its neighbor nodes, and

      - TC messages: so that it is no more used as an intermediate
        node while calculating a route.

   Next, the node examines its MPR Selector set. If this set is not
   empty, it means that some neighbors are using the node as a
   multipoint relay. This, in turn, means, that other nodes in the
   network may calculate the route to some destinations using this
   node as an intermediate node. In this case, the node MUST NOT
   enter sleep mode immediately but MUST wait until its MPR Selector
   set becomes empty. As the node has stopped sending HELLOs, it will
   eventually no longer be selected as a multipoint relay. Hence, the
   entries in the MPR Selector set will eventually expire.

   After terminating transmission of periodic messages, the node MUST
   negotiate with its multipoint relays to queue incomming data
   packets while it is in sleep mode. The node MUST keep only those
   MPRs in its MPR set, which agree to queue its packets.

   To initiate negotiation for entering power conservation mode, the
   node transmits a power conservation (PC) message, with the
   following contents:

      - Request/Reply = REQUEST
      - Sleep Period  = the intended sleep periode
      - Addresses     = the MPR-set of the sender node.
 
   In the following, the term "originator address" will be used to
   designate the address of the node from where the PC-message
   originates. Symmetrically, the term "receiver address" will be
   used to designate the address of the node receiving the PC-message.

   Upon receiving a PC-message where Request/Reply = REQUEST, the
   following following algorithm must be followed:

      1. if the recieving nodes MPR set contains the sender node's 
	 address, then this address MUST be removed from the MPR-set, 
	 and the MPR set MUST ber recomputed.

      2. if the receiver address is listed among the addresses in the
         PC message, it MUST decide if it can keep the packets for
	 the sender node during the sleep period mentioned in the PC
         message:

            2.1 if the node does not agree to queue the sender node's
	        packets, then no further processing of PC message is
		done;

            2.2 otherwise, if the node agrees to queue the packets of 
		the sender node for the intended sleep mode duration,
                then:

                   2.2.1 the node MUST add the intended sleep period 
			 time to the holding time of the tuple in the 
                         MPR Selector set corresponding to the sender
                         node's address

                   2.2.2 the node MUST reply to the sender node with 
			 a PC message, where the fields contains the
			 following:

			   - Request/Reply = REPLY
			   - Sleep Periode = the no, of ms which this
					     node agrees to queue
					     traffic (typically, this
					     is equal to that in the
					     received PC message)
			   - Address	   = sender address (i.e. the 
					     address of the node
					     which is allowed to
					     enter sleep mode).

   When the node, which intends to enter sleep mode, receives a reply
   of its PC message from one or more of its MPRs, it SHOULD keep
   only these addresses (of the MPRs) in its neighbor table and
   remove all others. It is now safe for the node to enter sleep
   mode.

   When a node receives a PC-message with Request/Reply = REPLY and
   an address, other than its own, listed as the only address, the
   message is silently discarded.

   If a node which emitted a PC-message with Request/Reply = REQUEST
   does not receive a reply after one HELLO_INTERVAL, it MAY re-send
   its PC message and wait for a reply. If still no reply is
   received, the node SHOULD NOT enter sleep mode.

   Alternatively, the node MAY enter sleep mode with the risk of
   loosing incomming packets. A "sleeping" node does not affect
   routing of packets, destined to other nodes in the network.

4.4.3. Wake up procedure

4.4.3.1. Wake up to resume activities after sleep mode

   The sleeping node MUST wake up before the sleep period (specified
   in its initial PC message) expires. It SHOULD then resume normal
   operation, i.e. sending periodic HELLO and TC messages. At the
   same time, the node SHOULD look up the addresses of the MPR's
   which agreed to queue its packets. Following, the node SHOULD
   request those nodes to send any queued packets. This is
   accomplished by sending a PC message to the MPRs with the
   Request/Reply field set to FORWARD and the sleep period set to
   zero. These PC-messages are sent to the nodes one by one to
   prevent all nodes from transmitting all their queued traffic to a
   waking node at the same time.

   A node which receives a PC message containing Request/Reply =
   FORWARD the sleep period equal to zero, should send all the
   packets, which it has queued for the sender node.

   If a node A is queuing packets for any node B, and the intended
   sleep period expires, node A SHOULD examine if a route to node B
   exists, i.e. if node B is alive or not. If the route exists, all
   queued packets MUST be send to node B. Otherwise, node A MAY
   discard all packets of node B.

4.4.3.2. Wake up in intermittent wake-and-sleep periods

   The sleeping node must wake up before the sleep period (mentioned
   in its PC message) expires. If the node intends to re-enter sleep
   mode after a small wake up period, it does not resume sending
   HELLO and TC messages. To collect queued packets, it broadcasts a
   PC message with the Request/Reply field set to FORWARD and the
   Sleep period field set to zero. There will be no list of MPR
   addresses attached to the PC message. A node which receives this
   PC message will send all the packets it has queued for the sender
   node of the PC message.

   To enter sleep mode after processing (and replying to, if
   necessary) the packets it receives, the node has to re-negotiate
   with its MPRs as described in section 4.4.2.

   (Future versions of the extension may explain if sending an
   intermittent wake-and-sleep pattern in the first negotiation could
   avoid the repetitive negotiations).

4.5. Compatibility issues

   Nodes implementing this PC-extension can coexist peacefully with
   nodes not implementing the extension. The presence of PC-nodes
   does not interact with the basic routing mechanisms of [1]. The
   concequence of having a mixed network of PC- and non-PC-nodes will
   be, that a PC-node which is not surrounded by other PC-nodes can
   not enter sleep mode.

4.6. Proposed values for the constants

   FORWARD    =	    0
   REQUEST    =	    1
   REPLY      =	    2

5. Unidirectional Links Extension

5.1. Purpose of the extension

   The purpose of this extension is to allow OLSR to operate on
   unidirectional links. In some configurations connectivity of the
   network can only be achieved by activating pairs of unidirectional
   links. This extension allows such unidirectional links to be used
   by OLSR for generating routes.

   The following diagram provides an example of unidirectional links
   use. Nodes A and C have bidirectional link, as does B and
   D. Ignoring the two unidirectinal links between A and B (and C and
   D, respectively), the network would appear partitioned: Node A
   cannot communicate with neither D nor B. 

          A-----> B
          |       |
          |       |
          C< ---- D

   Bi-directional links are prefered over unidirectional links since
   the latter are less reliable due to the absence of link layer
   packet acknowledgement. Therefore, unidirectional links SHOULD be
   activated only if required to obtain connectivity of the
   network. In the above example, through activating both the
   unidirectional links connectivity in the entire network is
   achieved. It is clear, that there must exists a pair of opposite
   unidirectional links in order to be able to establish and maintain
   connectivitiy in the network.

   When activating unidirectional links, the protocol strives to
   minimize this subset of unidirectinal links activated, in the
   sense that it should not contain any redundant unidirectional
   link.

5.2. Terminology

    UD-node

	A node, implementing unidirectional links, as described in
	this draft. An UD-node is capabel of maintaining an
	unidirectional link to another UD-node.

    Activated link

        A unidirectional link, selected for routing purposes, is said
        to be an activated link.  

    Unidirectional link

       A link, over which traffic can flow in only one
       direction. I.e. if there exists an unidirectional link between
       nodes A and B, traffic can flow from node A to node B, while
       no traffic can flow in the opposite direction from B to A.

    Tail node 

       The end-node of an unidirectional link, which can transmit
       data over the link. I.e. if there exists an unidirectional
       link between nodes A and B and traffic can flow from node A to
       node B, node A is said to be the tail node.

    Head node 

       The end-node of an unidirectional link, which can receive
       data over the link. I.e. if there exists an unidirectional
       link between nodes A and B and traffic can flow from node A to
       node B, node B is said to be the head node.

5.3. Extension overview

   The head node is able to detect the existance of an
   uni-directional link. When an UD-node detects the existance of an
   unidirectional link, through which an otherwise unreachable part
   of the network can be reached, it attempts to activate the link.

   To activate and maintain unidirectional links the UD-nodes nodes
   use UD Link Activation (UDLA) messages. The idea is that the head
   node, which detected the presence of the unidirectional link,
   floods an UDLA-message onto the network, containing its own
   address and the addresses of all its tail nodes. This message is
   flooded outside the MPR-optimizations from OLSR, and will thus be
   received by all nodes in the network. If there exists an opposite,
   uni-directional link (see 5.1), the UDLA-message will eventually
   arrive at the tail-node of the link announced. The tail-node now
   knows that it can "reach" the head node, and thus it MAY start
   announcing reachability by including the head node in its
   TC-messages.

   This extension maintains the flooding optimizations from OLSR
   based on multipoint relays (MPR's) among the bi-directional
   links. Such bi-directional links are expected to form the majority
   of used links in the network, with unidirectional links being the
   exceptional situation.

   In order to use a unidirectional links, it both the head and tail
   nodes MUST be UD-nodes node.

5.4. Detailed operation
       
5.4.1. Unidirectional Link Activation Message

   The unit of information exchanged between the nodes as part of
   activation of uni-directional links is Unidirectional Link
   Activation Messages (ULA). The proposed format of an ULA-message
   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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          Tail Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          Tail Address                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This is sent as the data part of the general packet format
   described in [1] with the "Message Type" set to UDLA
   and the TTL field set to 255.

5.4.1.1. Description of the fields

   Tail Address

	The address of a tail node

   The combined body of message consists of a list the addresses of
   all tail nodes known to the originator.

5.4.2 Link information

5.4.2.1 Head node information

   Each UD-node node maintains information about its head-nodes, i.e.
   information describing which nodes are head-nodes for ACTIVATED
   unidirectional links to which this node is a tail-node.

   Thus, for each head-node, a "Head Tupel" (HN_addr, H_time) is
   recorded, where HN_addr is the address of the head-node and H_time
   specifies the time at which this tupel expires and hence *MUST* be
   removed.

   In a node, the set of head tuples is called the head-set.

   Every time the head-node table is changed the MSSN [1] of the
   UD-nodes node SHOULD be incremented by 1.

5.4.2.2 Tail node information

   Each UD-node node maintains information about its tail-nodes, i.e.
   information describing which nodes are tail-nodes for ACTIVATED
   unidirectional links to which this node is a head-node.

   Thus, for each tail-node, a "Tail Tupel" (TN_addr, T_time) is
   recorded, where TN_addr is the address of the head-node and T_time
   specifies the time at which this tupel expires and hence *MUST* be
   removed.

   In a node, the set of tail tuples is called the tail-set.

   When a new tail tupel is created, a similar tupel is created in
   the MPR selector set (as described in [1]) with MS_addr equal to
   the TN_addr of the tail-node and with indefinite lifetime. The
   tupel in the MPR selector set is removed when the corresponding
   tupel in the tail-set is removed.

5.4.2.3 Activated UD link information

   Each UD-nodes node maintains information about activated
   unidirectional links. Thus, for each activated unidirectional
   link, an "UD-tuple" (TN_addr,HN_addr,UD_time) is recorded with
   TN_addr specifying the address of the tail-node, HN_addr the
   address of the head-node and UD_time specifies the time at which
   this tupel expires and hence *MUST* be removed.

5.4.3 Unidirectional link activation

5.4.3.1 Detection of unidirectional links

   The aim is to activate a link only if it is necessary. Thus, if,
   during a period UD_PRE_ACTIVATE_INTERVAL, an UD-node detects a
   node, X, which satisfies the following three conditions:

      - there exists no tuple in the tail-set with TN_addr equal to
        the address of node X, 

      - the neighbor set "permanently" contains a tuple with N_addr
        equal to the address of node X with N-status equal to
	ASYM_LINK,

      - the UD-nodes node does not receive any TC message, whose
        originator, or any MPR address contained in the TC message,
	identifies the address of the node X from any other node than
	the node X itself,

   then the UD-nodes node selects a random period between 0 and
   UD_PRE_ACTIVATE_INTERVAL. If during this period the UD-node does
   not receive a TC message originating from node X or announcing
   reachability to node X (i.e. containing the address of node X in
   the list of MPR address) other than from node X itself (i.e. over
   the unidirectional link) then:

      - a tail-tuple is created with TN_addr = address of X

      - an UDLA-message is emitted, containing the tail node list
        (including node X).

5.4.3.2 processing UDLA-messages

   In this section, the term "originator address" is used to
   designate the node from which the UDLA-message originally
   originated (i.e. the originator address from the message as
   specified in [1]). Upon receiving an UDLA message, the node
   performs the following tasks:
   
      1. An entry in the duplicate set is recorded for this message
         with:

	    D_addr = originator address

	    D_seq_num = Message Sequence Number

	    D_time = current time + D_HOLD_TIME.

      2. For each tail address in the UDLA-message:

	    2.1 If there exists an UD-tuple, where:

	           HN_addr == the originator address

		   TN_addr == the tail address

	        then, for that UD-tuple, the lifetime is set to:

		   UD_time = current time + UD_ACTIVATE_HOLD_TIME

            2.2 Otherwise, an UD-tuple is created with:

		   HD_addr = the originator address

		   TN_addr = the tail address

		   UD_time = current time + UD_ACTIVATE_HOLD_TIME

      3. If the node finds its own address among the tail addresses
	 in the UDLA-message,:

	    3.1. If a tuple in the head-set exists, where:

	    	    HN_addr == originator address
		 
		 then, for that tuple, the holding time is set to:

		    HN_time = current time + UD_ACTIVATE_HOLD_TIME

	    3.2. Otherwise, a new head-tuple is created with:

	    	    HN_addr = originator address

		    HN_time = current time + UD_ACTIVATE_HOLD_TIME

      4. If for the UDLA-message:

	    TTL > 0
	    
	 then the header of the UDLA message is modified:

	    TTL = TTL - 1

	    Hop count = Hop count +1

	 And the message is retransmitted (broadcast).

   Thus, through the UDLA-messages, a node is informed about its
   head-set, i.e. the nodes which it can reach directly through an
   unidirectional link.

   Notice, that UDLA-messages are diffused to all nodes, using pure
   flooding.

5.4.4 Generating UDLA messages 

   All UD-nodes node with a non-empty tail-nodeset MUST generate at
   least one UDLA message every UD_ACTIVATE_INTERVAL. Every TN_addr
   in the tail-table must be inserted in at least one UDLA message in
   every UD_ACTIVATE_INTERVAL.

5.4.5 Generating HELLO message

   HELLO messages MUST be transmitted as described in [1], with the
   annotation that all addresses, present in a nodes head-set, MUST
   be included in the HELLO message with a link status of SYM_LINK.

5.4.6 Generating TC message

   TC messages are transmitted by a node as described in [1], with
   the purpose of announcing partial topology information about the
   nodes neighborhood to the entire network. To announce topological
   information about the unidirectional links, it would suffice to
   include information about the tail-set in the TC-messages.

   In some cases nodes might wish to utilize information about the
   type of a link (i.e. if a link is bi- or unidirectional) - e.g. as
   the multicast extension, presented in section 6. Thus to
   accomodate for this, the "reserved" field of the TC-message
   defined in [1] is utilized.

   An UD-node transmits two "kinds" of TC-messages: regular
   TC-messages and ud TC-messaged.

5.4.6.1 Regular TC messages

   A regular TC-message is in strict conformance with [1], i.e.:

      - the "reserved" field of the TC-message has the value '0'
      - the addresses in the TC-message are the addresses of the MPR
        selectors for that node.

   I.e. regular TC-messages announce bidirectional links between a
   node and its MPR selectors.

5.4.6.2 UD TC-messages
   
   An UD TC-message is in conformance with [1] except for the
   following:
   
      - the "reserved" field of the TC-message has the value '1'
      - the addresses in the TC messages are the addresses of the
        head nodes for that node.

   I.e. an UD TC-message  announces unidirectional links from  a node
   and to head-nodes.

5.4.6.3 Processing of TC-messages

   A node, receiving a TC-message may choose to interpret the
   "reserved" field in the TC-message and annotate received
   topological information according to the contents. This, in turn,
   can then be used when computing routes (e.g. if it is required
   that a route consists of bidirectional links only).

   Alternatively, a node may ignore the contents of the "reserved"
   field in the TC-message. In that case, the node will interpret all
   TC-messages identically, and hence compute routes regardless of
   the nature of the underlying links.

5.4.7 Routing table calculation

   Routing tables are in the presence of uni-directional links
   calculated as described in [1].

5.4.8 Unidirectional link deactivation

   An entry from tail-node table with TN_addr equal to node W address
   is removed when any of the two following event occurs.  (i) the
   neighbor table does no longer contain an entry with N-addr equal
   to node W address with status ASSYM_LINK; (ii) there exist a
   bi-directional route to W (not necessariliy the shortest) which do
   not contain any activated unidirectional link (i.e. a link
   contained in the activated_UD_link table) .  In order to check
   point (ii) one has just to check if there is a path on the
   directed graph containing the arcs X->Y where Y is any one hop
   neighbor X (with link type SYM_LINK or MPR_LINK) and the arcs U->V
   where there exists an entry in the topology set with V as T_dest
   and U as T_last and where there do not exist an entry in the
   activated_UD_link table with V as HN_addr and U as TN_addr.

5.5. Compatibility issues

   Nodes, implementing this extension for unidirectional links can
   coexist with nodes, which do not implement the extension. 
   Moreover, even nodes without this extension are able to
   utilize unidirectional links, should such be present in the
   network. The only requirement for this extension to operate is,
   that both the head and tail node of an unidirectional link are
   UD-nodes.

5.5 Proposed value for the constant

   UD_PRE_ACTIVATE_INTERVAL		= 3* UD_ACTIVATE_HOLD_TIME
   UD_ACTIVATE_HOLD_TIME		= 3* UD_ACTIVATE_INTERVAL
   UD_ACTIVATE_INTERVAL 		= 5 seconds

6. Fast Moving Node Extension

6.1. Purpose of the extension

   An ideal pro-active protocol should    produce a control   overhead
   calibrated to mobility, i.e. no or very  low overhead when there is
   no  mobility and an an   increasing overhead as mobility increases.
   The aim of this extension is to cope with high mobility at the cost
   of  a greater control overhead.   Getting  a lower control overhead
   when mobility is low is addressed in an other extension.

   This extension  allows a node to  send  FAST-HELLO messages  with a
   higher rate than HELLO messages at the condition that their size is
   much smaller.  This can be  useful to  keep connectivity with  fast
   moving nodes, i.e.  nodes that stay connected to other nodes during
   a time  shorter  than   NEIGHB_HOLD_TIME.   This is   dedicated  to
   situations where fast moving nodes connect to static or slow moving
   nodes. Imagine for  example static  nodes  connected to a  backbone
   connecting fast mobiles nodes to the backbone.

6.2. Terminology

   Nodes that support the fast hello extension are called FMNExt-nodes.
   Other nodes are called NoExt-nodes.

6.3. Extension Overview

   FAST-HELLO  messages are sent at   higher rate than Hello messages.
   These messages are similar to classical  OLSR HELLO messages except
   that they include only a very limited number of neighbor addresses.
   They are used to establish quickly, and  refresh at high rate, some
   preferred links.

   To be connected, a fast  moving node must  establish quickly a link
   when it   looses connection.   For   that  purpose it  sends  empty
   FAST-HELLO messages announcing that it is in fast moving mode.  Any
   FMNExt-node receiving a FAST-HELLO message from a node for which it
   has no neighbor tuple replies  with a FAST-HELLO message containing
   the node address.  The fast moving node selects a limited number of
   responses and  declare their  emitters  as MPRs  in  its subsequent
   FAST-HELLO  messages (they are also included  in its MPR set).  Any
   FMNExt-node  receiving a  FAST-HELLO message where   its address is
   declared with MPR_LINK link type sends  immediately a regular a new
   TC message including the address of this new MPR selector.

   A link   refreshed    by  FAST-HELLO messages   may   be  refreshed
   asymmetrically,  i.e.  one   extremity   may send  both   HELLO and
   FAST-HELLO  messages concerning the  link while the other extremity
   sends  only regular HELLO  messages.   Regular  HELLO messages  are
   processed almost as in classical OLSR. The main difference concerns
   expiration time updates.

6.4. Neighbor sensing information base

6.4.1 Neighbor information

   Neighbor tuples  of  FMNExt-nodes have  an  additional field called
   N_moving_mode that is set  to FAST_MOVING_MODE when the neighbor is
   in fast moving  mode, FAST_DEFAULT_MODE when the  neighbor supports
   the extension and is not in fast moving mode, and 0 otherwise.

6.4.2 FAST-HELLO message format

   The   Message  Type   field  of  the  message    header  is  set to
   FAST_HELLO_MESSAGE.  FAST-HELLO messages  have a  similar format as
   regular HELLO messages. The only difference  is that the first word
   is  used  to  declare   the moving  mode   of  the  node  (fast  or
   normal). Thus the proposed format of a FAST-HELLO message 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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Moving Mode  |                   Reserved                    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Link Type   |   Reserved    |       Link Message Size       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Neighbor Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Neighbor Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                             . . .                             :
   :                                                               :
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Link Type   |   Reserved    |       Link Message Size       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Neighbor Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Neighbor Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                                                               :
   :                                                               :
                                 (etc)

6.4.2.1 Description of the fields

   Moving Mode

      This  field indicates  the  mode of  the  node.   It is  set  to
      FAST_MOVING_MODE  when  the  node is in  fast    moving mode and
      FAST_DEFAULT_MODE  otherwise. 00000000 is  forbidden as it would
      indicate a node not supporting the extension.

   Other fields

      Other  fields are the   same as in   regular HELLO messages.  

6.4.2.1 Regular HELLO messages

   No modification  is made    to  regular HELLO messages to    ensure
   interoperability with  nodes that  do  not support the  fast moving
   node extension. However,   an additionnal  link  type is   used  by
   FMNExt-nodes: FAST_UPDATE_LINK.

6.5. Fast moving node extension operation

6.5.1 FAST-HELLO message generation

   A node  MAY turn to  fast moving mode  (for  example, if it notices
   frequent  changes  of  its   neighbor  set).    It  then  generates
   continuously FAST-HELLO messages until this mode is  turned off.  A
   fast moving mode node MUST generate a FAST-HELLO message within any
   FAST_HELLO_INTERVAL period.    FMNExt-nodes SHOULD     NOT generate
   FAST-HELLO messages  at  a  rate  significantly exceeding one   per
   FAST_HELLO_INTERVAL period.

   In any  case the number of  neighbors  advertised in the FAST-HELLO
   messages   SHOULD  remain  very    small   (i.e.   no    more  than
   FAST_HELLO_MAX_LGTH). 

6.5.2 Fast moving node extension operation

   A fast moving  node cannot  discover  its 2-hop neighbors. Thus  it
   must use a heuristic to compute its MPRs. It MAY select arbitrarily
   one to FAST_HELLO_MAX_LGTH  neighbors as  MPRs. However it   SHOULD
   prefer neighbors with  N_moving_mode == FAST_DEFAULT_MODE. Its MPRs
   SHOULD be declared in all its FAST-HELLO messages.

   A  node in  fast moving mode   may also  compute its  routing table
   differently.  If its  MPR selector set   is not empty  then it MUST
   compute its routing table as a regular OLSR node.  Otherwise it MAY
   select randomly one of its MPRs as next  hop for known destinations
   that seem unreachable.

6.6. FAST-HELLO message processing

   In this section, the  term "Originator Address"  will be used about
   the address of the node  which sent the  FAST-HELLO message. If the
   node receiving  the FAST_HELLO   message  does not  implement   the
   extension,  then it   ignores  the messages.  Otherwise, the   node
   processes it as follows.

   A FAST-HELLO message  is processed as  a regular HELLO message with
   the following tuning:

      If the Moving Mode of  the originator is set  to 1 then all time
      expiration  updates    are made    with   FAST_NEIGHB_HOLD_TIME,
      otherwise, NEIGHB_HOLDING_TIME is used.

   The following processing should be added:

      The N_moving_mode field of the  tuple with N_addr ==  Originator
      Address (either it  was already  present,  either it is  created
      during the processing of the message) should be  set to the same
      value as the Moving Mode field of the FAST-HELLO message.

      If   there was no tuple  with  N_addr ==  Originator Address
         and Originator Moving Mode  == 1 
         and the  node is not in fast moving mode 
         and the node address was not found among the addresses listed
            in the FAST-HELLO message
      then a   FAST-HELLO message should   be  generated declaring the
      Originator Address with ASYM_LINK link type.

      If the   node finds its own  address  among the addresses listed
            with link type MPR_LINK
         and there was  no tuple with N_addr  == Originator Address or
            there was a tuple with N_status != MPR_LINK
      then an additionnal TC  should be generated  after the update of
      the MPR selector set.

6.7. Regular HELLO message processing

   FMNExt-nodes process regular  HELLO  messages almost as  a  regular
   OLSR node. They only have to be careful with expiration times.

   If there exists a neighbor  tuple with N_addr == Originator Address
   and N_moving_mode  == FAST_MOVING_MODE   then all time   expiration
   updates    are     made  with   FAST_NEIGHB_HOLD_TIME,   otherwise,
   NEIGHB_HOLDING_TIME is used.

   The rest of regular  HELLO message operation is  unchanged compared
   to classical OLSR.

6.8. Proposed values for the constants

   FAST_HELLO_INTERVAL   = HELLO_INTERVAL / 10.0
   FAST_NEIGHB_HOLD_TIME = 3 x FAST_HELLO_INTERVAL

   FAST_HELLO_MESSAGE    = 6

   FAST_HELLO_MAX_LGTH   = 4

   FAST_MOVING_MODE      = 1
   FAST_DEFAULT_MODE     = 2

7. Multicast Extension

7.1. Purpose of the extension

   The Multicast Optimized Link State Routing (MOLSR) Protocol takes 
   benefit of the topology knowledge gathered by the OLSR protcol with 
   its Topology Control messages exchange to build multicast trees.
   The MOLSR is developed as an extension to OLSR. It works even when 
   not all nodes are multicast capable provided that multicast nodes 
   offer the minimal connectivity between the sources and the members 
   of the multicast group.
   A multicast tree is built and maintained for any tuple (source, 
   group) in a distributed manner without any central entity and 
   provides  shortest routes from the source to the multicast group 
   members. The trees are updated whenever a topology change is 
   detected.

7.2. Extension overview

   The multicast optimized link state routing protcol belongs to the 
   source based family. 
   In order to build multicast trees, multicast capables nodes have to
   declare themselves to the entire network using a MC_CLAIM message. 
   Such nodes will disseminate this information periodically. Notice 
   that topology changes are still detected by the exchange of topology
   control messages which is done naturally by OLSR.
   Once a source wants to send data to a specific multicast goup G, it 
   will send a request (SOURCE_CLAIM) asking for nodes who are members 
   of this group. This invitation is flooded within the ad hoc network 
   using the MPRs nodes.
   Branches are built in a backward manner. When a group member 
   receives a SOURCE_CLAIM message and he is not already a participant 
   of this (source,group) tree, he attaches himself to the (source, 
   group) tree: he looks into the multicast routing table for the next 
   hop (PARENT) to reach the source (the multicast routing table 
   provides shortest routes to all the multicast capable). This next 
   hop becomes his parent in the multicast tree. 
   Then he sends a CONFIRM_PARENT message to his PARENT node. The 
   PARENT node receiving this message attaches himself to the (source,
   group) tree,if he is not already a participant to this tree.
   This message is handled hop by hop, by the intermediate MC_MPRs who 
   will build the corresponding branch. 

   Note that each node selects his MC_MPRs set which is basically 
   composed of subset of one hop nodes with multicast capabilities and 
   they must cover the two hops multicast nodes. The MC_MPR set must be 
   included in the MPR set.

   If a node wants to leave the multicast tree and he is a leaf, he 
   detaches himself from the tree: he just sends a LEAVE message to his
   PARENT in this multicast tree. If his PARENT becomes a leaf, he 
   detaches himself from the tree on his turn.

   This message is processed hop by hop and unused branchs are deleted 
   automatically.

7.3. Terminology

   Source tree

        A node who wants to send data to a multicast group G.   

   MC_MPR

        A node with multicast capabilities who can be used as router to
        build multicast trees.

   Multicast group member
        
        A node who wants to receive multicast data of a group G.

   Participant

        A node who belongs to a multicast tree. It may be a member of
        the group.

   Parent

        A parent of a node is an MC_MPR who can relay multicast packets 
        coming from the source to that node. A parent has one or more 
        downstream links (one per son) in the associated multicast tree.

   Son
        A node who has an upstream link to his parent in the associated 
        multicast tree.

7.4. Tables

   MOLSR uses the information stored and handled by OLSR. Additional
   information are kept in three different tables: MC_MPR_table, 
   MC_tree_table, and Multicast_routing_table.

7.4.1. MC_MPR_table:

   This table contains all the nodes with multicast capabilities
   (MC_MPRs).Each entry contains the MM_addr and the MM_time. MM_addr 
   stands for the node address and MM_time specifies the time at which 
   this record expires.

7.4.2. MC_tree_table:

   This table contains the information dealing with different multicast 
   groups that this node is participating in.The table stores one entry 
   per tuple (source, multicast group). Each entry has the following 
   information:

   - Source_tree_info

        consist of the address of the source_tree (MT_source_addr) and 
        the time to live for this entry (MT_source_tree_time).

   - Multicast_Group_addr

        The address of the multicast goup (MT_group_addr).

   - Parent address 

        The address of the next node towards the source (MT_parent_addr).

   - Sons information 

        List of the sons. For each son  we record its address 
        (MT_son_addr) and a time to live for it (MT_son_time).

7.4.3. Multicast_routing_table
  
    The multicast_routing_table provides the shortest routes to all 
    the multicast capable nodes in the network using only the MC_MPR 
    nodes.The calculation are done in the same way as they are done for 
    OLSR routing table. Each entry has the following information:

   - MR_dest

        the destination multicast capable node

   - MR_next

        The next hop MC_MPR in the route to MC_destination.

   - MR_dist

        The estimated number of hops to reach the MC_destination.

    The multicast_routing_table is updated whenever the OLSR routing 
    table is recalculated or when we discover a new multicast node, or 
    it disappears.

7.5. Message format

    Four new messages are needed to handle the multicast trees: 

    - MC_CLAIM message 

        used to declare the multicast capabilities of a node (i.e this 
        node supports MOLSR extension).
 
    - SOURCE_CLAIM message 

         used by the sources to declare themselves in a multicast group.

    - CONFIRM_PARENT message 
        
         used to attach a node to his parent in a multicast tree.

    - LEAVE message 

         used to leave a multicast tree or to change the parent of a node.

    The different messages use the uniform message format for OLSR.
    Each new message will be assigned a new type of message in the 
    message header. (see the end of this document)

7.5.1. MC_CLAIM message

    The MC_CLAIM message does not carry a specific information. We only 
    need to flood a message header with the corresponding type of 
    message. 

7.5.2. SOURCE_CLAIM message

   The SOURCE_CLAIM is flooded by the source tree. The address of this 
   source is specified in the message header.

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     MULTICAST GROUP ADDRESS                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    MULTICAST GROUP ADDRESS         

        The multicast group address to which we are asking for 
        members.

7.5.3. CONFIRM_PARENT and LEAVE messages

    Those two messages have the same message format. To distinguish 
    between them we have to check the message type of the header.

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     PARENT ADDRESS                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     MULTICAST GROUP ADDRESS                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     SOURCE TREE ADDRESS                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This message has several fields:

   PARENT ADDRESS  
        
        The address of the previous node toward the source of the 
        multicast tree.

   MULTICAST GROUP ADDRESS         

        The multicast group address for which the message is destinated.
        
   SOURCE TREE ADDRESS     

        The address of the source tree combined with multicast group 
        address identifies the unique tree.

7.6. Detailed operation

   We describe here the functioning of the multicast extension and how 
   the different messages are processed.

7.6.1- Requirements

   The calculation of the MPR set must be modified. The MPR set must be 
   calculated in such a way that, 2-hop multicast capable nodes are 
   covered by 1-hop multicast capable nodes when it is possible. Nodes 
   with multicast capabilities will be chosen preferably than the other 
   nodes.  And, of course, this set should be minimal and covers all the 
   second hop nodes. 

7.6.2. MC_CLAIM 

   Each node with multicast capabilities (MC_MPR) declares himself by 
   sending a MC_CLAIM to all the other nodes in the network. With this 
   information the other nodes can calculate routes to differents 
   sources in the same way as the regular OLSR routing calculation. The
   routes are composed only with MC_MPRs. The MC_CLAIM message is 
   flooded each MC_CLAIM_PERIOD seconds. Since this information does 
   not change in time, the MC_CLAIM_PERIOD should have a value as big 
   as possible. This information is kept in the MC_MPR_table for 
   MC_HOLD_TIME seconds.

7.6.3. SOURCE_CLAIM 

   The source declares himself by sending a SOURCE_CLAIM message. This 
   message is first generated whenever a node wants to send data to 
   multicast group G. This SOURCE_CLAIM message will be flooded in the 
   entire network.

7.6.4. Tree building

   A tree is built in a backward manner automatically without any 
   central entity between the sources and the different multicast group
   members.
   Branches are constructed hop by hop. When a multicast group member 
   receives a SOURCE_CLAIM it creates an entry in the MC_tree_table 
   corresponding to that group and source tree if such entry does not 
   exist. Then it will send a CONFIRM_PARENT message to his parent. The 
   parent is the corresponding MR_next in the multicast_routing_table 
   to reach the source node.

   The CONFIRM_PARENT message is sent to the PARENT. Upon a receiving 
   of such message a parent has to do the following operations:

   IF a corresponding entry to that group and source tree does not 
   exist in the MC_tree_table, THEN
  
        1- create a new one.
        2- set the MT_source_addr to SOURCE TREE ADDRESS. 
        3- set the MT_source_tree_time to the SOURCE_HOLD_TIME. 
        4- set the MT_group_addr to MULTICAST GROUP ADDRESS.
        5- set parent and sons information fields to NULL.

   IF the son address does not exist in the sons list, THEN

        1- create a new record for this son.
        2- set MT_son_addr to the originator address of the 
           CONFIRM_PARENT message (found in the header of the message).
        3- set MT_son_time to current time + SON_HOLD_TIME.

   IF the parent address is equal to NULL, THEN

        1- set the MT_parent_addr to the next hop (MR_next)of the current 
           node to reach the source tree.
        2- send a CONFIRM_PARENT message to the MR_next.

   Notice that the node will also relay the SOURCE_CLAIM message if it 
   is a MPR of the sender.

7.6.5. Tree maintenance

   Each source will continue sending periodic SOURCE_CLAIM message to 
   the whole network. In this way, new multicast group members can join
   the corresponding multicast tree. Upon a receipt of this message the 
   nodes in the specific tree will update their time to live field.

   The multicast_routing_table is recalculated whenever the 
   neighborhood or topology changes. In case of the next hop node 
   (MR_next) towards the source changes the node (the group member or a 
   participant node in the tree) must generate a new CONFIRM_PARENT 
   message to inform the new parent.
   It MAY generate a LEAVE message to disable the old route (of course 
   if the neighbor is still reachable). No message is sent if the next 
   hop did not change. Each participant will send periodically a 
   CONFIRM_PARENT message to his parents in order to refresh the 
   corresponding timeout each CONFIRM_PERIOD seconds.

7.6.6. LEAVE messages

   A LEAVE message is generated by a leaf node who wants to leave a 
   multicast tree, or by another intermediate node who has received 
   such a message and this participant is not a multicast group member.

   A node can leave a group or a specific tree. Leaving a specific tree 
   may occur when the topology changes and a participant finds a new 
   route to the corresponding source. To leave a specific tree a node 
   must send a LEAVE message to his PARENT. If this PARENT becomes a 
   leaf, and if he is not a group member he will send on his turn a 
   LEAVE message to his PARENT. 

   Leaving a group means that the node leaves all the trees that he is 
   participating in.

   Leaving a multicast group means that a node is no more interested in
   that group. In this case we must eliminate all the branchs leading 
   to that node. To leave the group a node may broadcast a LEAVE 
   message to his parents.

   A particpant will also send a LEAVE message to his parent when it 
   has no more sons (e.g timed out) and it is not itself a multicast 
   group member. This procedure eliminates quickly the unused branches 
   in the network.

7.7. Proposed value for the constants

   MC_CLAIM_PERIOD = 30 sec

   MC_HOLD_TIME = 3 x MC_CLAIM_PERIOD

   SOURCE_CLAIM = 15 sec

   SOURCE_HOLD_TIME = 3 x  SOURCE_CLAIM

   CONFIRM_PERIOD = 10 sec

   SON_HOLD_TIME = 3 x CONFIRM_PERIOD

8. Gateway and Subnet Announcement Extension

8.1. Purpose of the extension
    
   The purpose of this extension is to provide a way for a node to
   introduce additional routing information into the network. I.e. if
   a node is connected to both a MANET and to another network, the
   node may wish to announce its presence as a gateway to that
   network.

8.2. Terminology

   Gateway
   
      A node, connecting the MANET to another network and willing to
      route data between the networks.

8.3. Extension overview
   
   A node, which is connected to both a MANET and another network may
   wish to announce to the MANET that it is capable of acting as a
   gateway between the two nets. To accomplish this, the node
   periodically issues a gateway and subnet annoucement (GSA)
   message, containing sufficient information for the recipients to
   construct an appropriate routing table.

8.4. Detailed operation

8.4.1 Gateway and subnet announcement message

   The unit of information exchanged between the nodes as part of
   gateway and subnet announcement is called GSA-messages. The
   proposed format of an GSA-message 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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         Network Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             Netmask                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         Network Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             Netmask                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                              ...                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This is sent as the data part of the general packet format
   described in [1] with the "Message Type" set to GSA and the TTL
   field set to 255.

8.4.2 Gateway and subnet information base

   Each node maintains information about the gateways and their
   connected subnets by recording "routing tuples" (GW_addr,
   NET_addr, NET_mask, GS_time), where GW_addr is the address of the
   gateway, NET_addr and NET_mask specifies the network address and
   netmask of a network, reachable through this network, and GS_time
   specifies the time at which this tupel expires and hence *MUST* be
   removed.

   The set of all routing tuples in a node is called the "route set".

8.4.3 Generating GSA messages 

   A gateway SHOULD periodically generate a GSA-message, containing
   pairs of (network addres, netmask) corresponding to the connected
   networks. GSA-messages SHULD be transmitted periodically every
   GSA_INTERVAL.

8.4.4 Processing GSA messages

   In this section, the term "originator address" is used to
   designate the address of the node which originally issued the
   GSA-message.

   Upon receiving a GSA-message, the node performs the following:

      1. An entry in the duplicate set is recorded for this message
         with:

	    D_addr = originator address

	    D_seq_num = Message Sequence Number

	    D_time = current time + D_HOLD_TIME.

      2. For each (network address, netmask) pair in the message:

	    2.1 if an entry in the routing table allready exists,
	        where: 
		
		   GW_addr  == originator address

		   NET_addr == network address

		   NET_mask == netmask

		then the holding time for that tuple is set to:

		   GW_time = current time + GW_HOLDING_TIME

            2.2 otherwise, a new tuple is recorded with:

		   GW_addr  == originator address

		   NET_addr == network address

		   NET_mask == netmask

		   GW_time = current time + GW_HOLDING_TIME

8.4.5 Routing table calculation

   The routing table is recalculated as specified in [1], with the
   extension that:
   
	- For each entry in the routing set, record an entry in the
	  routing table, with: 

	      R_dest     = NET_addr/NET_mask

	      R_next     = the next hop on the path from the node to
			   GW_ADDR

	      R_dist	 = dist to GW_ADDR
	  
	  (R_next and R_dist can be found in the routing table
	  maintained by [1])    	

      - whenever a routing tuple expires, the corresponding entry
        MUST be removed from the routing table.

8.4.6 Assignment of addresses

   The nodes in the MANET network MUST be assigned addresses within a
   sequence, known by both the gateway and the nodes themself. I.e.
   the MANET MUST be associated with a network address and a netmask,
   in order for this extension to operate correctly.

8.4.7 Configuration

   The MANET nodes MUST be configured such that they have:

       - a network route set up on the interface participating in the
	 MANET. I.e., in lack of other routing information, any
	 incomming datagrams destined for a node in the MANET address
	 sequence is transmitted onto this interface (efficiently:
	 incomming data to a MANET node, which the node cannot find an
	 exact match for, is broadcast to all neighbors)

   The gateway MUST, in addition to the MANET node configuration, be
   configured such that it has: 

       - routes set up on all other interfaces, according to the
         networks they are connected to.

8.4.8 Routing 

   IP-routing performs the following actions when deciding how to
   route a packet [3]:
   
      1. search the routing table for an entry that matches the
         destination IP of the address. If found, forward the packet
	 (to the next-hop router or to the directly connected
	 interface), according to the entry in the routing table.
 
      2. search the routing table for an entry that matches the
         destination network ID. If found, forward the packet to the
	 next hop router or to the directly connected interface,
	 according to the entry in the routing table.

      3. search for a default routing entry. If found, forward the
         packets to the next-hop router  according to the entry in
	 the routing table.

   When a node receives an incomming packet, destined for another
   node than itself, it searches the routing table for an exact match
   of the IP-address. Failing that, it searches for a match on the
   network ID - and finally for the default routing entry.

   Thus, if a MANET node receives a packet, destined for another node
   in the MANET network sequence, but it does not have an exact
   host-route for that node, the packet will be transmitted into the
   neighborhood, rather than sent to the default router in the
   network.

   If the gateway receives, on the interface connected to the MANET,
   a packet destined for another node in the MANET to which there
   exists no exact match in the routing table, the packet is
   transmitted back onto the interface.

8.5. Compatibility issues

   While this extension alters the routing table, it does not
   interfer with normal operation of the routing protocol. Rather, it
   adds information to the routing table of those routers, capable of
   interpreting the GSA-messages, thereby possibly providing access
   to further destinations.

   Nodes with and without this extension can peacefully coexist in
   the network.
   
8.6. Proposed valued for constants

   GW_HOLDING_TIME   = 3 x GSA_INTERVAL
   GSA_INTERVAL	     = 5 seconds

9. Message type overview

   Mnemonic		Value	Extension
   ------------------------------------------------------------
   PC			   3	Pover Conservation
   UDLA			   4	Uni-directional links
   GSA			   5	Gateway and subnet announcement
   FAST_NODE_MESSAGE       6    Fast node moving
   MC_CLAIM                7    Multicast
   SOURCE_CLAIM            8    Multicast
   CONFIRM_PARENT          9    Multicast
   LEAVE                   10   Multicast

10. References

   1. Philippe Jacquet, Amir Qayyum, Thomas H. Clausen, Anis Laouiti, 
      Laurent Viennot and Paul Muhlethaler. Optimized Link State
      Routing Protocol. Internet-Draftm draft-ietf-manet-olsr-04.txt,
      March 2001. Work in progress.

   2. 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.

   3. Fred Baker. Requirements for IP Version 4 Routers. Request for
      Comments (standard track), Internet Engineering Task Force,
      June 1995.

11. Authors' Addresses

   Thomas Clausen
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5278
   Email: [email-masked]

   Philippe Jacquet
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5263
   Email: [email-masked]

   Anis Laouiti
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5278
   Email: [email-masked]

   Laurent Viennot
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5278
   Email: [email-masked]

   Pascale Minet
   Project HIPERCOM
   INRIA Rocquencourt
   BP 105
   78153 Le Chesnay Cedex, France
   Phone: +33 1 3963 5233
   Email: [email-masked]