Subject: Multicast draft

From: Anis LAOUITI <[email-masked]>
Date: Tue, 04 Dec 2001 17:07:37 +0100

Hi,

Here is the new version of the multicast OLSR draft.

Regards

Anis LAOUITI

INTERNET-DRAFT                                          Philippe Jacquet
IETF MANET Working Group                                   Pascale Minet
Expiration: 21 April 2002                                   Anis Laouiti
                                                         Laurent Viennot
                                                          Thomas Clausen
                                                            Cedric Adjih
                                              INRIA Rocquencourt, France
                                                        21 November 2001

                 Multicast Optimized Link State Routing
                   draft-ietf-manet-olsr-molsr-01.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.

1.  Abstract

   This document describes the Multicast extension for the Optimized
   Link State Routing protocol(MOLSR). MOLSR is designed for mobile
   routers, and works in a heterogenous network composed of simple OLSR
   routers, MOLSR routers and hosts.  In the last part of this document
   we introduce also a Wireless Internet Group Management Protocol
   (WIGMP). It offers the possibility for OLSR nodes (without multicast
   capabilities) to join multicast groups and receive multicast data.

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 1]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

                           Table of Contents

1. Abstract  . . . . . . . . . . . . . . . . . . . . . . . . . . . .   1
2. Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . .   3
2.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . .   3
2.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . .   3
3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . .   4
4. Tables  . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   6
4.1. MC_router_table . . . . . . . . . . . . . . . . . . . . . . . .   6
4.2. MC_tree_table . . . . . . . . . . . . . . . . . . . . . . . . .   6
4.3. Multicast_routing_table . . . . . . . . . . . . . . . . . . . .   7
5. Message format  . . . . . . . . . . . . . . . . . . . . . . . . .   7
5.1. MC_CLAIM message  . . . . . . . . . . . . . . . . . . . . . . .   8
5.2. SOURCE_CLAIM message  . . . . . . . . . . . . . . . . . . . . .   8
5.3. CONFIRM_PARENT and LEAVE messages . . . . . . . . . . . . . . .   9
6. Detailed operation  . . . . . . . . . . . . . . . . . . . . . . .  10
6.1. Requirements  . . . . . . . . . . . . . . . . . . . . . . . . .  10
6.2. Advertisement of multicast routers  . . . . . . . . . . . . . .  10
6.3. Advertisement of multicast sources  . . . . . . . . . . . . . .  10
6.4. Tree building . . . . . . . . . . . . . . . . . . . . . . . . .  10
6.4.1. SOURCE_CLAIM message processing . . . . . . . . . . . . . . .  11
6.4.2. CONFIRM_PARENT message processing . . . . . . . . . . . . . .  11
6.5. Tree maintenance  . . . . . . . . . . . . . . . . . . . . . . .  12
6.6. Detachement of a multicast tree . . . . . . . . . . . . . . . .  13
7. Sources without multicast capabilities  . . . . . . . . . . . . .  13
7.1. SOURCE_CLAIM generation and processing  . . . . . . . . . . . .  13
7.2. COMFIRM_PARENT message generation . . . . . . . . . . . . . . .  14
7.3. The computation of the next hop to reach the source . . . . . .  14
8. Proposed values for the constants . . . . . . . . . . . . . . . .  14
9. WIGMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  15
9.1. Motivation  . . . . . . . . . . . . . . . . . . . . . . . . . .  15
9.2. WIGMP overview  . . . . . . . . . . . . . . . . . . . . . . . .  15
9.3. WIGMP router  . . . . . . . . . . . . . . . . . . . . . . . . .  17
9.3.1. Elimination procedure . . . . . . . . . . . . . . . . . . . .  17
9.3.2. The router designation procedure  . . . . . . . . . . . . . .  17
9.3.3. Interaction between WIGMP and MOLSR . . . . . . . . . . . . .  18
9.4. The host behaviour  . . . . . . . . . . . . . . . . . . . . . .  18
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . .  18
11. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . .  19

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 2]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

2.  Introduction

   The Multicast Optimized Link State Routing (MOLSR) Protocol takes
   benefit of the topology knowledge gathered by the OLSR protocol with
   its Topology Control messages exchange to build multicast trees.
   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, multicast 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.

2.1.  Changes

   This is the first revision of this draft.
   Major changes from version 00 to version 01

     -    The WIGMP has been improved to keep unchanged the host part of
          IGMP.

     -    Sources which are not multicast routers are considered too.

2.2.  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 [2].  The
   terms "connection", "holding time" "multipoint relay", "MPR", "multi-
   point 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-05.txt [1].

   Additionally, the following terms are used throughout this document:

     Multicast router

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

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 3]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

     Designated multicast router

          A multicast router which has been designated to forward multi-
          cast data to a host in its neighborhood.

     Multicast source

          A host or a router which wants to send data to a multicast
          group.

     Multicast group member

          A node which wants to receive data multicast to group G.

     Participant

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

     Multicast tree

          A tree whose root is the source of the multicast data and
          whose nodes are multicast routers needed to forward data to
          all multicast group members.  There is one  multicast tree per
          tuple (source, multicast group).

     Parent

          A parent of a node is a multicast router which can relay mul-
          ticast packets coming from the source to that node. A parent
          has one or more downstream links (one per son) in the associ-
          ated multicast tree.

     Son

          A node which has an upstream link to its parent in the associ-
          ated multicast tree.

3.  Protocol Overview

   The multicast optimized link state routing protocol (MOLSR) belongs

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 4]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

   to the source based family. It maintains one multicast tree per tuple
   (source, multicast group). Those trees are only composed of multicast
   capable nodes. Three steps are distinguished: the tree building, the
   tree maintenance, and the tree detachement.

   Tree building

     Multicast routers declare themselves to the entire network by
     broadcasting a MC_CLAIM message (using the optimized flooding tech-
     nique of OLSR).  Such nodes will disseminate this information peri-
     odically.

     Once a source wants to send data to a specific multicast group G,
     it sends a SOURCE_CLAIM message enabling nodes which are members of
     this group to detect its presence and to attach themselves to the
     associated multicast tree.

     This message is flooded within the ad hoc network using the opti-
     mized flooding technique of OLSR. Branches are built in a backward
     manner: group members which do not know yet about this source try
     to attach themselves to the corresponding tree.

     More specifically, when a group member receives a SOURCE_CLAIM mes-
     sage and it is not already a participant of this (source, multicast
     group) tree, it attaches itself to the (source, multicast group)
     tree:

          -    it looks into the multicast routing table for the next
               hop to reach the source (the multicast routing table pro-
               vides shortest routes to all the multicast capable
               nodes). This next hop becomes its parent in the multicast
               tree.

          -    Then it sends a CONFIRM_PARENT message to its parent
               node.

          -    The parent node receiving this message attaches itself to
               the (source, multicast group) tree, if it is not already
               a participant to this tree.

     This message is handled hop by hop, by intermediate multicast
     routers which build the corresponding branch.

   Tree maintenance

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 5]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

     The trees are periodically refreshed, by means of the SOURCE_CLAIM
     message and the CONFIRM_PARENT message. Notice that topology
     changes are still detected by the exchange of topology control mes-
     sages which is done naturally by OLSR. Thus, trees updates are
     triggered by the detection of topology changes.

   Tree detachement

     If a node wants to leave the multicast tree and it is a leaf, it
     detaches itself from the tree: it just sends a LEAVE message to its
     parent in this multicast tree. If its parent becomes a leaf, and
     this parent is not a group member, it detaches itself from the tree
     on its turn.

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

4.  Tables

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

4.1.  MC_router_table

   This table contains all the nodes with multicast capabilities.  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.

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

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

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 6]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

     Multicast_Group_addr

          The address of the multicast goup (MT_group_addr).

     Parent address

          The address of the next node towards the source (MT_par-
          ent_addr).

     Sons information

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

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 multicast
   routers. The calculations 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 multicast router 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 a new multicast node is discovered, or
   it disappears.

5.  Message format

   Four new messages are needed to handle the multicast trees:

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 7]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

     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 its 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 section Proposed values for the constants).

5.1.  MC_CLAIM message

   The MC_CLAIM message does not carry a specific information. It is
   only needed to flood a message header with the corresponding type of
   message.

5.2.  SOURCE_CLAIM message

   The SOURCE_CLAIM is flooded by the source node, root of the multicast
   trees. The address of this source is specified in the message header.
   The source asks for members in the specified multicast groups.

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

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 8]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

     MULTICAST GROUP ADDRESS

          The multicast group address to which the source will multicast
          data.

5.3.  CONFIRM_PARENT and LEAVE messages

   Those two messages have the same message format. To distinguish
   between them,the message type of the header has to be checked.

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

   This message has several fields:

     PARENT ADDRESS

          The address of the next node toward the source of the multi-
          cast tree.

     MULTICAST GROUP ADDRESS

          The multicast group address for which the message is desti-
          nated.

     MULTICAST SOURCE ADDRESS

          The address of the multicast source. This address combined
          with the multicast group address identifies the multicast

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih             [Page 9]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

          tree.

6.  Detailed operation

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

6.1.  Requirements

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

6.2.  Advertisement of multicast routers

   Each node with multicast capabilities declares itself by sending a
   MC_CLAIM to all the other nodes in the network. With this information
   the other nodes can calculate routes to different sources in the same
   way as the regular OLSR routing calculation. The routes are composed
   only with multicast routers. 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_router_table for MC_HOLD_TIME sec-
   onds.

6.3.  Advertisement of multicast sources

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

6.4.  Tree building

   A tree is associated with any tuple (source, multicast group). This
   tree is built in a backward manner automatically without any central
   entity from the different multicast group members to the source.
   Branches are constructed hop by hop. The tree building is started
   when a multicast router receives a SOURCE_CLAIM message for a group
   in which it is participating. Branches are attached to the multicast

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 10]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

   tree by means of the CONFIRM_PARENT message.

6.4.1.  SOURCE_CLAIM message processing

   When a participant receives a SOURCE_CLAIM it does the following
   operations:

   IF there is no entry corresponding to that group and source

   THEN

     1    create a new one.

     2    set the MT_source_addr to the originator of the message.

     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.

     6    Send a CONFIRM_PARENT message to its parent. The parent is the
          corresponding MR_next in the multicast_routing_table to reach
          the source.

   ELSE update the MT_source_tree_time.

   IF the node is a MPR of the sender, THEN it relays the SOURCE_CLAIM
   message.

6.4.2.  CONFIRM_PARENT message processing

   The CONFIRM_PARENT message is sent by a node M to its parent. Upon
   receiving such a message, a node 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 the originator of the message.

     3    set the MT_source_tree_time to the SOURCE_HOLD_TIME.

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 11]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

     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_PAR-
          ENT message (found in the header of the message).

     3    set MT_son_time to current time + SON_HOLD_TIME.

   ELSE update 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) in the multi-
          cast routing table of the current node to reach the source.

     2    send a CONFIRM_PARENT message to the MR_next.

6.5.  Tree maintenance

   Each source periodically sends a SOURCE_CLAIM message to the whole
   network. In this way, new multicast group members can join the corre-
   sponding multicast tree. Upon a receipt of this message the nodes in
   the specific tree will update their time to live field
   MT_source_tree_time in the MC_tree_table.

   The multicast_routing_table is recalculated whenever the neighborhood
   or topology changes. If 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.  Then, 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 does not change.

   Each participant will send periodically a CONFIRM_PARENT message to
   its parents in order to refresh the corresponding timeout each CON-
   FIRM_PERIOD seconds.  Those messages may be grouped in a single one
   as allowed by the message format.

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 12]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

6.6.  Detachement of a multicast tree

   A LEAVE message is generated by a leaf node which wants to leave a
   multicast tree, or by another intermediate node which 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
   may send a LEAVE message to its parent. If this parent becomes a
   leaf, and if it is not a group member it will send on its turn a
   LEAVE message to its parent.

   Leaving a group means that the node leaves all the trees associated
   with this group.

   Leaving a multicast group means that a node is no more interested in
   that group. In this case, and if this node has no son, all the unused
   branches are eliminated. To leave the group a node may broadcast a
   LEAVE message to its parents.

   A participant will also send a LEAVE message to its parents 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.  Sources without multicast capabilities

   In this section we deal with the sources which are not multicast
   routers. As usual such sources send multicast data to multicast
   groups. In that case, the following MOLSR procedures are modified:

     -    The SOURCE_CLAIM generation and processing.

     -    The CONFIRM_PARENT generation for the source neighbors.

     -    The computation of the next hop to reach the source.

7.1.  SOURCE_CLAIM generation and processing

   The designated multicast router (see next section) of this source is
   in charge of generating a SOURCE_CLAIM message on behalf of this
   source. In that case, the first field of the SOURCE_CLAIM message
   contains the individual address of the source. The following fields
   specify the multicast group addresses to which the source sends data.
   Notice that it is easy to distinguish a multicast address from the

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 13]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

   individual address of the host.

   The SOURCE_CLAIM message is processed as previously described except
   that the MT_source_addr is set to the first field of the SOURCE_CLAIM
   message.

   The SOURCE_CLAIM message is periodically sent by the designated
   router to refresh the corresponding entry in the MC_tree_table.

7.2.  COMFIRM_PARENT message generation

   The source neighbors do not send a CONFIRM_PARENT message, because
   the source is not able to process them.

7.3.  The computation of the next hop to reach the source

   In order to compute the next hop to the source, the multicast routers
   which are not source neighbors, select the next hop to one of the
   MPRs with multicast capabilities of the source giving the shortest
   distance.

8.  Proposed values 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

      CONFIRM_DELAY = 1 sec

   The message types of this extension are given by the following table

      Mnemonic           Value   Extension
      ------------------------------------------------------------

      MC_CLAIM             7     Multicast
      SOURCE_CLAIM         8     Multicast

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 14]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

      CONFIRM_PARENT       9     Multicast
      LEAVE                10    Multicast

9.  WIGMP

9.1.  Motivation

   The Internet Group Management Protocol (IGMP) is used by hosts to
   report their multicast group membership to neighboring multicast
   routers. It is also used by multicast routers to discover group mem-
   bers.  According to IGMPv2 (RFC 2236) and IGMPv3, IGMP is required to
   be implemented by any host wishing to receive IP multicasts. However
   in a wireless context like MANET, the use of IGMP may lead to some
   inconsistencies. More precisely, the elimination procedure of queries
   as described in IGMP is problematic in a wireless context:

     -  The elimination procedure eliminates too many queriers, as
     illustrated by this example.

     Example :

               R1       R2            H

     A host H has only one neighbor router R2. Router R1 and router R2
     are neighbors. Initially both routers R1 and R2 are queriers. When
     router R2 receives the query of router R1 with a smaller address,
     router R2 becomes non querier. Router R1 is the only querier. As
     host H can only be heard by R2, router R1 does not receive the
     unsolicited report of H for group G.  Hence no router will forward
     IP multicast packets for group G to H.

   To cope with this problem we propose to modify the behaviour of IGMP
   in the routers.

9.2.  WIGMP overview

   WIGMP is a Wireless IGMP. It is only concerned with the exchanges
   between hosts and routers to determine group membership. The goals of
   WIGMP are:

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 15]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

          (i) to enable any multicast router to know whether at least
          one host in its neighborhood is member of a multicast group;

          (ii) to enable a multicast router to know whether it must for-
          ward multicast data to a host in its neighborhood.

   On a multicast router, WIGMP coexists with a multicast routing proto-
   col.  The multicast routing protocol is in charge of building and
   maintaining a multicast structure (e.g. a tree between a source and
   all the multicast routers participants of a multicast group) enabling
   any member of a multicast group G to receive IP multicast data desti-
   nated to G.

   Notice that, in WIGMP there is no new messages added to the IGMP
   ones, we keep the same messages specified as in IGMPv3. The host IGMP
   is kept as it is also.

   The major change is in the router IGMP, by modifying the behaviour of
   the router when sending and receiving those messages.

     First :

          The rule for multicast routers elimination is modified.

     Second:

          For each host H, a multicast router in H neighborhood is des-
          ignated to forward multicast data.

     Third :

          A multicast router, member of a multicast group, plays the
          only role of IGMP router.

   Whenever a host H wants to join a multicast group G, it sends an IGMP
   report which is called Unsolicited Report to reach neighbor multicast
   routers. MOLSR routers do not send this kind of messages. If a MOLSR
   router wants to join a group it builds simply and immediately a route
   to the sources of the requested group.  A multicast router is desig-
   nated to forward multicast data to H (see the designation procedure
   in the next section).

   Multicast routers that have not been eliminated (see the elimination
   procedure in the next section), periodically send general queries to
   their neighbors.

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 16]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

9.3.  WIGMP router

9.3.1.  Elimination procedure

   The elimination procedure is modified in such a way that IGMP is a
   particular case of WIGMP.  The role of this procedure is to select a
   multicast router in charge of the host queries in the neighborhood.
   However, any host must be queried by a multicast router.  In IGMPv2
   and v3, if two multicast routers hear each other, only the one with
   the smallest address is elected as a querier.  In WIGMP, the follow-
   ing rule is applied:

   Let Ri and Rj, be any two multicast routers, and OneHop(Ri) be the
   one hop neighborhood of Ri

   IF OneHop(Ri) U {Ri} = OneHop(Rj) U {Rj}

   THEN the router Rj with the highest address is eliminated

   ELSE IF OneHop(Ri) U {Ri} is included in OneHop(Rj) U {Rj}

        THEN the router Ri is eliminated.

9.3.2.  The router designation procedure

   The router designation procedure enables the designation of the mul-
   ticast router in charge of forwarding multicast data to a host.

   When a multicast router receives an Unsolicited Report from a host H
   its checks its neighbor table to see whether it has the lowest IP
   address among the multicast routers neighbors of H. In fact, with
   OLSR, each node has a two hop neighbors table which provides all
   links in the neighborhood. In this way, the multicast router with the
   lowest IP address designates itself as a router to this host.

   If the host H moved or a link breaks with this router, another multi-
   cast router having detected the presence of H, is designated as a
   multicast router for H. It builds a branch to the multicast group (if
   it does not exist), and forwards the corresponding multicast data.

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 17]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

9.3.3.  Interaction between WIGMP and MOLSR

   Each time there is a change of group G membership, WIGMP notifies its
   local multicast routing protocol when:

     -    either an unsolicited report has been received from a new mem-
          ber,

     -    or a previous member has left.

9.4.  The host behaviour

   The host which is not a multicast router behaves according to IGMP as
   in the wired network.  When it wants to join a multicast group, it
   starts sending its unsolicited Report, and, then normal reports upon
   receiving queries from multicast routers.  In case of the presence of
   multiple multicast routers sending their query messages in the neigh-
   borhood, the host bundles multiples multicast group reports as in
   IGMPv3 and its reports are addressed to all multicast routers in its
   neighborhood.

10.  References

     1    Philippe Jacquet, Amir Qayyum, Thomas H. Clausen, Anis
          Laouiti, Laurent Viennot, Pascale Minet and Paul Muhlethaler.
          Optimized Link State Routing Protocol. Internet-Draft, draft-
          ietf-manet-olsr-05.txt, November 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.

     4    William C. Fenner. Internet Group Management Protocol, Version
          2.  Request for Comments 2236, Internet Engineering Task
          Force, November 1997.

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 18]

INTERNET-DRAFT   Multicast Optimized Link State Routing 21 November 2001

11.  Authors' Addresses

   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 5088 Email:
   [email-masked]

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

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

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

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

Jacquet, Minet, Laouiti, Viennot, Clausen and Adjih            [Page 19]