[Docs] [txt|pdf] [Tracker] [WG] [Email] [Nits]

Versions: 00

IETF MANET Working Group                                         C.W. Wu
INTERNET-DRAFT                                                  Y.C. Tay
                                        National University of Singapore
                                                                C-K. Toh
                                         Georgia Institute of Technology
                                                        24 November 1998


Ad hoc Multicast Routing protocol utilizing Increasing id-numberS (AMRIS)
                        Functional Specification
                  <draft-ietf-manet-amris-spec-00.txt>

Status of this Memo


   This document is an Internet-Draft.  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."

   To view the entire list of current Internet-Drafts, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern
   Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific
   Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast).


Abstract

   This document introduces a new multicast routing protocol for use
   over ad hoc networks. The protocol is called AMRIS, short for Ad hoc
   Multicast Routing protocol utilizing Increasing id-numberS. The
   conceptual idea behind AMRIS is to assign every node in a multicast
   session with an id-number. A delivery tree rooted at a particular
   node called Sid joins up the nodes participating in the multicast
   session. The relationship between the id-numbers(and the node that
   owns it) and Sid is that the id-numbers increase in numerical value
   as they radiate from the root of the delivery tree. The significance
   of the Sid is that it has the smallest id-number within that
   multicast session. Utilizing the id-numbers, nodes are able to adapt
   rapidly to changes in link connectivity. Recovery messages due to
   link breakages are confined to the region where it occurred.




Wu, Tay, and Toh           Expires 24 May 1999                  [Page 1]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


1. Introduction

   Conventional multicast routing protocols for the Internet[1,2,3,4,5]
   break down in ad hoc networks[6] because of the dynamic nature of the
   network topology. The dynamically changing topology, coupled with
   relatively low bandwidth wireless links causes long convergence
   times(if they ever converge) and possibly formation of loops which
   rapidly consume the already limited bandwidth.

   AMRIS constructs a shared delivery tree among all participant nodes.
   This is done by first building a DAG rooted at a special node called
   Sid(Sid has the smallest id within the multicast session and is
   generally the source node, i.e. the one that expresses the demand for
   a route). A delivery tree is thus formed by using a subset of the
   links of the DAG. Multiple senders and receivers are supported on
   this tree.  (We are currently investigating whether the leftover
   links of the DAG(leftover - those not part of the delivery tree) can
   be maintained as secondary/backup links. Is the overhead/cost of
   maintaining them worthwhile vs the advantages that they can bring.)

   Nodes participating in AMRIS does not require any globally consistent
   routing state. Permanent loops which may occur due to node movements
   etc will not occur. AMRIS allows nodes to recover from broken links
   rapidly [within one multicast beacon period]. Repairs to damaged
   links are performed locally without need for any central controlling
   node thus increasing survivability. We expect that most multicast
   applications are long-lived, therefore rapid route reconstruction is
   of greater importance compared to rapid route discovery. This may not
   necessarily be the case in the context of a unicast routing protocol
   where short route discovery times may be favoured over recovery times
   when the application lifespan is short.


2. Terminology

   Smallest-ID node (read as Sid)
     We call the node that starts/initiates a multicast session Sid
     because it has the smallest msm-id compared with all other nodes
     for that multicast session.

   Node
     A device in the ad hoc network willing to participate in the
     routing protocol.

   Potential Parent Node (PPx)
     If a node X receive any NEW-SESSION message from PPx and PPx has a
     smaller msm-id than node X, then PPx is considered a Potential
     Parent Node of X. This information is updated in node X's



Wu, Tay, and Toh           Expires 24 May 1999                  [Page 2]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


     Neighbour-Status table.

   Parent Node
     A node X is the parent node of a node Y if node Y successfully
     joined the multicast session through X. Node X must have a smaller
     msm-id than node Y. This information is updated in both X and Y's
     Neighbour-Status table.

   Child Node
     A node Y is the child node of a node X if node Y successfully
     joined the multicast session through X. Node Y must have a larger
     msm-id than node X. This information is updated in both X and Y's
     Neighbour-Status table.

   Bigger-id node
     If a node X has a bigger multicast id then Y, then X is called
     Bigger-id node.

   Smaller-id node
     If a node X has a smaller multicast id then Y, then X is called
     Smaller-id node.

   Multicast group
     Nodes participating in multicast communication which includes the
     senders/sources, receivers and intermediate nodes.

   Multicast Session ID (ms-id)
     A unique value identifying a particular multicast session.

   Multicast Session Member ID (msm-id)
     An ID number that all nodes within a multicast session must have.
     The ID differs among nodes and generally increases in numerical
     value the further a nodes is from Sid.

   Neighbour-Status Table
     This table is a conceptual data structure that we employ to keep
     information regarding the neighbouring nodes and their status. Eg.
     Participation in which multicast sessions, etc.

   Multicast Beacon
     This is a periodic one-hop broadcast sent by all nodes to update
     neighbouring nodes about its multicast state information. Multicast
     state information would include the node's unique ID, msm-id as
     well as it's parent and child msm-ids.


3. Assumptions




Wu, Tay, and Toh           Expires 24 May 1999                  [Page 3]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   We assume that all nodes within the ad hoc network are willing to
   participate fully in the protocol. Every node has a unique ID at
   either the network layer (e.g. IP address) or the link layer (e.g.
   MAC Address for 802.11). We assume that the underlying unicast layer
   provides information about symmetric links to upper layers. We assume
   that there is no underlying beaconing mechanism to detect link
   breakage. Link breakage detection is performed by making use of the
   periodic multicast beacon but we do not exclude using additional
   information such as fading link quality, positional information of
   nodes, etc to ensure link detection is accurate. If the underlying
   layers also utilize some form of beaconing, AMRIS can efficiently
   utilize that beaconing instead for the purpose of supporting ad hoc
   multicast routing.


4. Protocol Overview

   Each multicast session is identified a globally unique identifier(eg
   class D IP address). A single node (called Sid) initiates a multicast
   session by broadcasting a NEW-SESSION message. Sid has the smallest
   msm-id. All nodes that receive the NEW-SESSION message generates
   their own msm-id based on the value found in the message. The new
   msm-id replaces the old value when the NEW-SESSION message is
   rebroadcasted. Nodes that receive multiple NEW-SESSION messages(for
   the same multicast session) will choose only one of the messages to
   process. The NEW-SESSION message thus travels in an expanding ring
   fashion outwards from Sid. In the initial phase, nodes closer to Sid
   will generally have smaller msm-ids than those further away.

   The links of the multicast delivery tree are formed as follows:

   1) If the requesting node X has a neighbouring node which is already
   a member of the multicast session, X will join the multicast session
   by sending a JOIN-REQ to that neighbour. A JOIN-ACK from that
   neighbour confirms that X is a registered child of the neighbour. X
   updates its Neighbour-Status table to indicate that that neighbour is
   a registered parent of X. That neighbour node also updates its own
   Neighbour-Status to indicate that X is a registered child.

   2) If the requesting node X only has neighbouring potential
   parents(i.e nodes with smaller msm-ids but are not yet members of the
   multicast session), X will send a JOIN-REQ to one of the potential
   parents. The potential parent is triggered to join the multicast
   session when it receives the JOIN-REQ from X. It does so by sending
   out its own JOIN-REQ to its potential parent, if any are available.
   If the potential parent is Sid, it does not send out any JOIN-REQ
   (since it has no parents). If the parent node determines that the
   requesting node X is allowed to join successfully, it will send a



Wu, Tay, and Toh           Expires 24 May 1999                  [Page 4]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   JOIN-ACK back the to requesting node X, otherwise it will send a
   JOIN-NACK.

   3) If the requesting node X does not have any neighbouring parents or
   potential parents, it will send a broadcast JOIN-REQ with a ttl of
   one but with range R. (The ttl determines whether the datagram should
   be rebroadcast without modification. The range R is another field
   that specifies if the node should send its own JOIN-REQ or JOIN-
   REQ.passive in response to the one that was received) All nodes
   withing range R(number of hops) from X will attempt to join the
   multicast tree by sending out their own JOIN-REQ.passive. The range R
   is decremented by one each time a node sends out the JOIN-REQ.passive
   so that eventually only nodes that are within range R(no. of hops
   from X) will have generated JOIN-REQ.passive. Nodes that receive a
   JOIN-REQ.passive with range R equal to zero do not generate any more
   JOIN-REQ.passve. Note that the contents of the sent JOIN-REQ.passive
   is different from the JOIN-REQ.passive in that the node will modify
   the contents with its own information before its sends it out.

   A JOIN-REQ.passive received by an off-tree node will trigger that
   node to send a JOIN-REQ.passive only if the range is greater than
   zero. An on-tree node that receives a JOIN-REQ.passive will reply
   with a JOIN-ACK.passive. This sets up a set of passive links between
   the requesting node to possibly several on-tree nodes. The requesting
   node may eventually receive several JOIN-ACK.passive messages from
   different potential parents. It chooses one of the potential parents
   as its registered parent and sends a JOIN-CONF to that parent. The
   JOIN-CONF received by the parent node will trigger that parent node
   to send a JOIN-CONF if necessary to its own parent. The passive links
   maintained by the other potential parents will eventually time out.
   Potential parent nodes with passive links are allowed to respond to
   other nodes that might have sent out JOIN-REQ. In doing so, we "re-
   use" state information collected and minimize expanding ring type
   broadcasts.


   Link breakage detection is performed in AMRIS by making use of the
   multicast beacon. The multicast beacon contains the msm-id of the
   node and the registered parent and child nodes of the node.


5. Protocol Specifics

   We will explain the protocol in the following sequence:

     1. Types of Membership/Node Classification
     2. What is Sid and where does it come from?
     3. Tree Initialization



Wu, Tay, and Toh           Expires 24 May 1999                  [Page 5]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


     4. Joining the Multicast Session
     5. Reaction to mobility/broken links during JOINING phase
     6. Forwarding Policy
     7. Reactions to mobility/broken links
     7.1 Leaf node moves
     7.2. Intermediate moves
     7.3. Core node moves
     8. Reaction to Network partition
     9. Group Membership
     10. Terminating the Multicast Session


   5.1 Types of Membership/Node Classification

   Nodes are classified into the following types:

   Interested node (I-node)
     A node that is interested in a specific multicast session and
     wishes to join, it does not matter if it is interested to join as
     either a sender or receiver or both.

   Uninterested Node (U-node)
     A node that is not interested in a specific multicast session but
     is "forced" and became part of the session anyway because it is
     required to be a relay/intermediate node on the multicast delivery
     path. If a U-node does not have any descendent nodes that are I-
     nodes, it will prune itself off the tree. This is one of the main
     difference between a U-node and a I-node.

   Leaf node
     A node at the edge of the multicast tree. A leaf node maybe a
     sender or a receiver or both. U-nodes that becomes leaf nodes as a
     result of node movements will remain as leaf nodes only temporarily
     before they are pruned off.

   Intermediate node
     A node in the internal branches of the multicast tree. May be
     either an I-Node or an U-Node.

   5.2 What is Sid and where does it come from?

   Sid is defined as the node that initiated the multicast session by
   broadcasting the NEW-SESSION message to its surrounding nodes. In a
   single-sender, multiple-receiver environment, the single-sender would
   most likely assume the role of Sid. In a multiple-sender, multiple-
   receiver environment, it is most probable that one of the multiple-
   senders will assume the role of Sid in initiating the multicast
   session. Any core-election type of algorithm can be used if there are



Wu, Tay, and Toh           Expires 24 May 1999                  [Page 6]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   multiple nodes contending for the role of Sid. Obviously, the choice
   of the core will have an initial effect on the shape of the delivery
   tree formed. We hope to have more insight on this matter after
   analyzing simulation results.

   5.3 Initializing the Multicast Session

   We assume that Sid has some means of obtaining a unique identifier
   for the multicast session. Sid creates a new multicast session by
   broadcasting a NEW-SESSION message to its surrounding neighbours. The
   NEW-SESSION will contain among other things, Sid's msm-id, multicast
   session address, and routing metrics. All nodes that receive the NEW-
   SESSION message will then generate their own msm-id and replace the
   msm-id in the message with their own, as well as various routing
   metrics before broadcasting the message again. Information derived
   from the NEW-SESSION message is kept in the Neighbour-Status table
   for up to T1 secs. A random delay of T2 secs is inserted between the
   receipt of a NEW-SESSION message and its subsequent rebroadcast. A
   node may receive multiple NEW-SESSION messages from different nodes.
   If it has not rebroadcast any messages yet, it will keep the message
   that has the best routing metric. That message is then modified and
   rebroadcast. Otherwise the messages received are dropped.

   5.3.1 Bootstrapping the msm-id value

     Each node that receives the NEW-SESSION message will calculate the
     initial value of its msm-id using hop count as a parameter to the
     function F1 Calculate_Initial_msm-id(Section 6 describes the
     function in greater detail). In a nutshell, the larger the hop-
     count value in NEW-SESSION message received, the larger will be its
     msm-id which is the value returned by Calculate_Initial_msm-id. The
     function's behaviour is such that there is a large msm-id insertion
     window between nodes that are one hop-count away. This facilitates
     the subsequent insertions of other nodes in between these two
     nodes. The beacon will now include the msm-id. If the beacon is
     implemented within the multicast routing layer and no other
     multicast session existed before this, the beacon is started up for
     the first time.

   The NEW-SESSION message thus travels outward from the Sid in an
   expanding ring fashion. Eventually every node will have assigned to
   themselves a msm-id. The msm-id is used when the node joins the
   multicast session. The msm-id will be removed when the multicast
   session is no longer desired(or expired). This will release the msm-
   id usage back to the pool. msm-id is related to specific nodes
   supporting an active on-going multicast sesssion.





Wu, Tay, and Toh           Expires 24 May 1999                  [Page 7]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   5.4 Joining the Multicast Session

   When a NEW-SESSION message is received, a node X decides if it wishes
   to join the session by examining the contents of the message. (The
   contents of the message will obviously contain information about the
   multicast session). The joining approach attempts to fultil the join
   in an adjacent approach rather than resorting to localized broadcast
   right away. If the immediate neighbouring nodes are nodes already on
   the multicast tree, then this 1-hop 'peek' approach is very fast and
   efficient. The presence of msm-id helps in identifying the likelihood
   of a successful join. Our protocol does not cover the area of
   notifying the senders the identities of receivers(old or new).  A
   node X joins a multicast session in one of several ways depending on
   the situation:

   1) Node X has a valid msm-id and has a neighbour that also has a
   valid msm-id. (this is normally the case after tree initialization)

   2) Node X does not have a valid msm-id and has a neighbour that also
   has a valid msm-id. (Probably node X missed the NEW-SESSION
   broadcast.)

   3) Node X has a valid msm-id and does not have any neighbours with
   valid msm-id. (Probably the neighbours have timed out that msm-ids. X
   must therefore find other nodes that have valid msm-ids)

   4) Node X does not have a valid msm-id and does not have any
   neighbours with valid msm-id. (Probably node X missed the NEW-SESSION
   broadcast.)

   Case 1
     Node X sends a JOIN-REQ to that neighbouring potential parent PP1.
     Potential parent PP1 checks that X can be a child node (i.e. X has
     a bigger msm-id than Y) of PP1 and sends a JOIN-ACK back to Node X.
     Potential parent PP1 updates its Neighbour-Status table to indicate
     that node X is a registered child of PP1. Node X updates its
     Neighbour-Status table to indicate that node PP1 is a registered
     parent of X.

     Case 2
     If Node X is aware that a neighbour Y can be a potential parent,
     node X will also know Y's msm-id because it must have received Y's
     beacon. Node X then assigns itself a msm-id using Y's as a
     parameter. Node X's situation is now similar to case 1 and node X
     will behave as in case 1.

     Case 3-4
     Node X initiates Branch Reconstruction (BR) with the msm-id. (Refer



Wu, Tay, and Toh           Expires 24 May 1999                  [Page 8]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


     to Section 5.7 for BR)


     A node may also receive a JOIN-NACK instead of a JOIN-ACK, if so,
     node X will initiate BR based on the error code returned in the
     JOIN-NACK. If X does not receive any reply with T3 secs, it will
     initiate BR accordingly.

     When a node PP1 receives a JOIN-REQ from a bigger-msm-id node X,
     PP1 will be in one of the following situations:

   1) be part of the multicast session already (as in case 1 above)

   or 2) it has a msm-id but has not sent out any JOIN-REQ before.(this
   happens when the node PP1 received the NEW-SESSION message and
   determined its own msm-id. However the node PP1 was not interested in
   joining the multicast session. Thus it did not send out any JOIN-REQ
   of its own yet.)

   or 3) it has a msm-id and has sent out JOIN-REQ pending reply. (as in
   case 1 or 2 above)

   or 4) it does not have a msm-id yet. (as in case 3 or 4 above)

   PP1's reaction to receiving a JOIN-REQ (dependent on which situation
   it is it as discussed above) is as follows:

   Case 1
     If PP1's msm-id is smaller than the requesting node X, it sends a
     JOIN-ACK and updates its multicast state tables. if it is bigger or
     equal, it sends a JOIN-ACK.error="msm id too small/equal" to the
     requesting node. It updates the  neighbour-Status table to indicate
     the node X is now a registered child node of node PP1. However no
     multicast traffic is forwarded to X yet until X increases its msm-
     id to be bigger than PP1. PP1 will know when X has increased its
     msm-id through X's beacon.

   Case 2
     PP1 must now join ('coerced' into joining by X) the multicast
     session. It sends out a JOIN-REQ.passive to its own potential-
     parent node. If PP1 successfully joins the multicast session, it
     will send a JOIN-ACK.passive back to requesting node X. Otherwise,
     it sends a JOIN-NACK with the appropriate error code. Since PP1 was
     'coerced' into joining, it will not forward any traffic to X until
     X sends a JOIN-CONF message to confirm that X has selected PP1 as
     its parent. Note that this is slightly different from the case 1.
     (In general, JOIN-REQ/ACK.passive and JOIN-CONF is used when the
     parent node does not yet have a msm-id) During the time PP1 is



Wu, Tay, and Toh           Expires 24 May 1999                  [Page 9]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


     waiting for X's JOIN-CONF, the links through PP1 are considered as
     passive links. The passive links are converted to active links when
     a JOIN-CONF from X is received. The JOIN-CONF from X will PP1 to
     send its its parent a JOIN-CONF as well it the parent sent it a
     JOIN-ACK.passive previously.

   Case 3
     PP1 waits until it receives a reply for its own JOIN-REQ or times
     out. It sends a JOIN-ACK or JOIN-NACK depending on the success of
     its own JOIN-REQ to node X.

   Case 4
     If it does not have a msm-id, then no node should have sent it a
     JOIN-REQ. it sends a JOIN-NACK.error="NO msm-id yet" back to the
     JOIN-REQ node.

   All other nodes that receive a JOIN-REQ with a broadcast address will
   forward the message provided the time-to-live is not zero yet. The
   node must keep track of who sent the JOIN-REQ so that a reverse path
   can be followed subsequently. A node PP1 may also receive a broadcast
   JOIN-REQ, i.e. a JOIN-REQ with a broadcast address. PP1 will then
   send out its JOIN-REQ but the ttl is always limited to one. It will
   follow the behaviour as in case 3.

   Only the core node does not try to send a JOIN-REQ out when it itself
   receives JOIN-REQs.


   5.5 Reaction to mobility/broken links during Joining Phase

   We discuss how the protocol behaves when links break during Joining
   Phase.

   Case 1
     X lookups Neighbour-Status table and sees Y as a Potential Parent.
     X sends JOIN-REQ to Y. Y's link to X is broken thereafter. Hence, Y
     is unable to reply. X eventually times out and goes into BR mode. A
     broadcast JOIN-REQ is subsequently sent by X in BR mode. Y's status
     as a potential parent is removed from X's Neighbour-Status table.

     Case 2
     X sends JOIN-REQ to Y. Y is not on multicast tree., so Y must join
     multicast session as well. Y sends out JOIN-REQ.passive to Z. Z
     sends JOIN-ACK.passive but at this time link between X and Y
     breaks. Y tries to send to X but will not succeed. Since Y was a U-
     node, and has no I-node children. Eventually it will time out and
     prune itself off the tree. X will eventually go into BR mode as in
     case 1.



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 10]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   5.6 Forwarding Policy

   The forwarding policy rules are as follows for multicast _data_
   traffic(not control traffic):

   1) When a multicast datagram is received, it first checks if the
   originator is itself, if so, it will drop the datagram.

   2) If a multicast datagram is received from its registered parent
   node, it will forward to all registered child nodes.

   3) If a multicast datagram is received from a registered child node,
   it will forward to all other registered child nodes and its
   registered parent node.

   4) If a multicast datagram is received from any other node, it is not
   forwarded to any other nodes.


   5.7 Reaction to mobility/broken links

   When a link breaks between two nodes, the node with the larger msm-id
   is supposed to do recovery by going into BR mode. Nodes can also
   enter BR mode because of unsuccessful joins to its neighbouring
   nodes.  A node X entering BR mode can be classified into having one
   of the following initial states:

   1) X has a valid msm-id but does not have any neighbour nodes that
   can be potential parent or parent nodes.

   2) X has a valid msm-id and has at least one neighbour node that can
   be potential parent or parent nodes.

   3) X does not have a valid msm-id and does not have any neighbouring
   nodes that can be potential parent or parent nodes.

   4) X does not have a valid msm-id and has at least one neighbouring
   node that can be potential parent or parent nodes.

   In cases 1 and 2, X may have child nodes whose parent node is X. i.e.
   there is a sub-tree below X.

   Initial State 1:
     X sends a broadcast JOIN-REQ beginning with range R of two. If no
     reply is received after T3 secs, R is increased by one. This is
     repeated until the number of incremental attempts exceeds the
     recover delay that may have been specified. If there is no reply,
     then it means that the multicast session has either ended a long



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 11]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


     time ago or a network partition has taken place. If X has child
     nodes, it will send a New-Partition-Id message to all its child
     nodes. If X does not have any child nodes, then X can either begin
     a new multicast session or X is unable to join the multicast
     session.

     If a JOIN-ACK is received by X, it indicates that X has
     successfully joined the multicast session. X updates its Neighbour-
     Status table to indicate that the neighbour node which sent the
     JOIN-ACK as X's registered parent. If a JOIN-ACK.passive is
     received, X sends a JOIN-CONF to the neighbour node that send the
     JOIN-ACK.passive. X updates its Neighbour-Status table that the
     neigbour is the registered parent of X. A JOIN-ACK.passive is
     received because the was neighbour 'coerced' to join the multicast
     session. Since more than one neighbour might do this, a JOIN-CONF
     is necessary to select the neighbour to be the registered parent.

     A node that sends out JOIN-ACK.passive does not forward any traffic
     until it receives a JOIN-CONF. Other requesting nodes can turn this
     node's passive links into active links if they send a JOIN-CONF to
     this node. If a JOIN-ACK.error="msm-id too small" is received, X
     increases its msm-id as required and sends a multicast beacon. If X
     is unable to increase its msm-id because of child nodes(the child
     nodes' msm-id may be equal or smaller then the required new value
     for X), X sends an Modify-msm-id message to its child nodes before
     increasing its own msm-id. X can detect if its child nodes have
     increased their msm-id when it receives their beacons.

   Initial State 2:
     X sends a JOIN-REQ to the potential parent node PP1. If a JOIN-ACK
     is received, then X updates its Neighbour-Status table that PP1 is
     the registered parent of X. If no reply is received from PP1 after
     T3 secs, X goes into BR mode with initial state 1.

   Initial State 3:
     X sends a broadcast JOIN-REQ as in Initial State 1. It's msm-id is
     set to a random value. Any necessary adjustments will be in
     response to a JOIN-ACK.error="msm-id too small" message.

   Initial State 4:
     X can determine a msm-id for itself based on its neighbour's msm-
     id. It then re-enters BR with initial state 1.

     In the case of a JOIN-REQ broadcast, the child nodes Cx of the node
     X executing BR will also receive the JOIN-REQ. When they
     rebroadcast it, they must keep track of the rebroadcasted JOIN-REQ
     so that if a reply should return from one of the child node's(C*)
     neighbor, the child (C*1) must check that the msm-id of the



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 12]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


     neighbour is smaller than its own, if not it will send a JOIN-
     NACK(msm-id error) instead of forwarding the JOIN-ACK to its
     parent. Child nodes which receive a JOIN-NACK will just forward it
     along.

     If X (the node executing BR) receives a JOIN-NACK(msm-id error)
     forwarded through an on-tree child node, it is treated differently
     than if it were received from other non-child nodes. To node X the
     message means that a route exists to a potential parent but that
     route runs through the its children's links instead. (This new
     route may be the only available route to the rest of the multicast
     tree). If the BR has no other routes to potential parents to choose
     from, then it must change its msm-id such that it is now larger
     than its children. This process continues to the descendent node
     which swapped the JOIN-ACK with the JOIN-NACK(msm-id error). This
     is a really worse case scenario. The BR node can initiate the
     change by sending a Reverse-msm-id message to the affected child
     nodes. The Reverse-msm-id message is forwarded only to downstream
     neighbours that require the change as a result of the BR node's new
     msm-id. It will stop at the node which swapped the JOIN-ACK with
     JOIN-NACK.


   We have looked at what happens when the broken link is between a
   single upstream node and a single downstream node. We want to refine
   the basic policy if the broken link is between a single upstream node
   and multiple downstream nodes.

   If there originally was a group of neighbouring nodes participating
   in the same multicast session and their common parent node moves
   away, then instead of having all the nodes broadcast a JOIN-REQ, it
   makes more sense to have only a subset of those nodes broadcast the
   JOIN-REQ. This is done by introducing a short random delay before a
   JOIN-REQ is sent if a node has more than one neighbour sharing the
   same parent who is also a member of the multicast session. If the
   node hears its neighbour JOIN-REQ, it will delay its own JOIN-REQ
   until either it hears a JOIN-ACK to its neighbour and some timer
   timouts. A node X will wait random time before transmitting JOIN-REQ.
   if it hears a JOIN-REQ from a neighbour for a parent node that is
   also suitable for X. X will delay its JOIN-REQ for Ts. If it hears a
   JOIN-ACK from the PP1 node, it will send its own JOIN-REQ directly to
   PP1. If no reply is heard, then it will broadcast its own JOIN-ACK
   after Ts.

   We look at some link breakage scenarios and illustrate how BR works
   out in each case.

   5.7.1 Reaction to leaf node movement



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 13]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   There are two situations of leaf node movement.

   5.7.1.1 Situation 1: Leaf node moves to new location where multicast
   tree is already established

     When the leaf node C1 moves, its parent P1 will eventually detect
     this. P1 will proceed to prune itself from the tree if P1 is a U-
     node and has no other child nodes. The pruning is as similar to
     that described in Section 5.9 Group Membership except the parent
     does not receive explicit notification from the child node. P1 has
     received implicit notification as a result of broken link to C1.

     When C1 moves into new location L2, it can hear node P2's multicast
     beacon and discover that a multicast tree already exists there.
     (Another way that C1 can discover P2 is on the multicast tree is
     hearing multicast traffic for that session being forwarded by P2).
     If P2 has a smaller msm-id than C1 then C1 can immediately send a
     JOIN-REQ to P2. If P2 has a larger msm-id, then C1 will increase
     its msm-id using P2's msm-id as a parameter into Calculate_MSM_ID()
     to acquire its new msm-id. C1 then sends another JOIN-REQ using its
     new msm-id. P2 replies with a JOIN-ACK to C1 after it receives the
     second JOIN-REQ with the new msm-id from C1. It will subsequently
     forward any multicast traffic to C1 as well. This is similar to the
     tree initialization process.

     [Note: C1 does not send a leave notification control message to its
     old parent P1. Reason for not sending: Network resource consumed in
     sending a leave message to P1 from C1's new location, must include
     resource consumed to establish path to old parent no de etc.]

   5.7.1.2 Situation 2: Leaf node moves to new location where no
   multicast tree exists

     The behaviour of the original parent P1 is as in situation 1. When
     leaf node C1 reaches new location L2, it is unable to discover any
     existing neighbours who can serve as parent nodes. It then
     initiates a broadcast BR to its neighbours. Neighbouring nodes
     which receive the JOIN-REQ will send out their own JOIN-
     REQ.passive. This is repeated at each node until the range reaches
     0. An on-tree node that receives the JOIN-REQ.passive will send a
     JOIN-ACK.passive. The JOIN-ACK.passive travels along the reverse
     path taken by the original JOIN-REQ and JOIN-REQ.passive. JOIN-REQ-
     PENDING table. The multicast delivery tree now extends to C1
     through a set of passive links. C1 must send a JOIN-CONF along one
     of the passive links to turn it into an active parent link. The
     parent nodes will start to forward traffic only when a JOIN-CONF is
     received.




Wu, Tay, and Toh           Expires 24 May 1999                 [Page 14]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   5.7.2 Reaction to Intermediate node movement

     We explain the action taken by an intermediate node that moves such
     that the link to is parent is broken but the link to its child
     nodes are still active. The action taken by the intermediate node
     is similar to that in 5.7.1. except if it receives a JOIN-
     ACK.error="msm-id too small". Then the intermediate must send a
     Modify-msm-id message to all its child nodes. If the intermediate
     node's child links are broken as well, then intermediate node need
     only to perform the BR if it is a I-node.

   5.7.3 Reaction to Sid node movement

     When Sid moves such that its child links are broken, the child
     nodes will begin a BR process towards the Sid. Only a subset of the
     child nodes actually broadcast the JOIN-REQ as a result of the
     optimization performed.


   5.8 Reaction to Network partition

   A network partition will cause the multicast tree to be divided into
   different segments. When a partition takes place, the node X at the
   point of partition will behave as though it has lost the parent link
   and will behave as discussed in section X and X. If BR does succeed
   after n-tries, we can assume that a network partition has take place.

   Within each partition, multicast traffic continues to be forwarded in
   accordance to the forwarding rules as stated in Section 6.4, i.e.
   intra-partition traffic can continue as per normal but inter-
   partition traffic cannot take place.

   When this happens, the child node (who is also the one with the
   smallest-id within this partition) at the point of link breakage will
   become the new temporary Sid-temp, i.e. the node with the smallest
   msm-id within that partition. At a later time, the network may be
   such that a path now exists either between the Sid-temp or one of its
   child node back to the original partition.

   When a partition takes place, the Sid-temp should send a Partition-Id
   change message to its decendent nodes. The message can be sent
   standalone or piggybacked along multicast traffic. This will update
   all child nodes eventually. The multicast beacon will carry the new
   partition-id.

   Subsequently, any node that hears a beacon for the same multicast
   session but with a different partition id will send a FOUND_PARTITION
   message to its own partition's Sid-temp. Only the node with the



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 15]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   smallest msm-id will send the message to its own partition's core.
   The node in the other partition will not. If there is a tie, the one
   with largest unique id will inform its core. The core will send a
   JOIN-REQ back to its child node if after it compares the msm-ids,
   unique ids, of the reporting nodes and the other partitions reporting
   nodes.

   The temp core may receive several of such messages. It will choose
   the one with the best routing metric and send a JOIN-REQ message back
   to the node. Intermediate nodes which receive the JOIN-REQ will react
   as discussed in Section 5.7. When a JOIN-ACK returns in response to
   the JOIN-REQ, the temp core may need to send out Modify-msm-id
   messages to a subset of its child ndoes that lie on the path to the
   other partition.

   So in this situation, we have two partitions with joining together.
   The node with the smallest msm-id will eventually become the new Sid.
   However we have a problem if we have two partitions whose core have
   the same msm-id, then neither partition will join with each other but
   they are still in different partitions because the original core may
   be destroyed.

   5.9 Group Membership

   Group membership is dynamic in nature, any node is free to join or
   leave the node at any time except for the Sid. If Sid wishes to
   leave, another node will have to be designated as the new Sid before
   the present one can leave.

   Nodes wishing to join the multicast session after it has already
   "started" will do so by sending a JOIN-REQ to any of the on-tree
   nodes as discussed in Section 5.4. On-tree nodes can be detected by
   listening to its neighbours' beacons and detecting if any of the
   neighbours are already an on-tree node.  If the node is unable to
   locate any neighboring on-tree nodes, it will begin a N-hop-lifetime
   JOIN-REQ broadcast to its neighbours. N begins from 2 to MAX-TTL.
   After sending the broadcast, it will wait for a reply. If no reply is
   received within time T1, it will increase N by one and send again.

   Any node that receives the JOIN-REQ and is not an on-tree node will
   update its NEIGHBOUR-STATUS table and rebroadcast. The behaviour here
   is similar to tree initialization except that the intermediate nodes
   may not yet have a msm-id. Similarly the I-node also does not yet
   have a msm-id. Eventually, the JOIN-REQ will be received by an on-
   tree node which will reply with a  JOIN-ACK. The nodes along the path
   from the I-node to the on-tree node will then dynamically program
   their msm-id using their respective parent node's msm-id as parameter
   into function Calculate_Initial_MSM_ID.



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 16]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   A leaf node can leave the multicast session by sending a SESSION-
   LEAVE message to its parent node. If the parent node is a U-node in
   the multicast session. It too will send a SESSION-LEAVE message to
   its own parent node provided it does not have other child nodes.


   5.10 Terminating the Multicast Session

   Only Sid can close a multicast session. Nodes are of course free to
   leave as and when subject to conditions in Section 5.9 - Group
   Membership.

   Sid closes the multicast session by sending a SESSION-END message
   down to its child nodes. This is rebroadcasted by intermediate nodes.
   All nodes that receive the SESSION-END message purge any
   entries/state associated with the multicast session. The nodes store
   the session-id for up to time T4 before finally expiring that entry.
   This is to take into consideration partitioned networks. If the
   network is partitioned, the original Sid may have closed the session
   but the other partitions have not since they did not receive the
   message. For this reason, nodes which receive the END-SESSION message
   will remember the session-id for time T4. If the node hears a beacon
   with state about the session. It will forward the END-SESSION message
   to it.

   Each multicast entry in the Neighbour-Status table has an associated
   timeout value. Session termination can also be done via a soft state
   approach, i.e. when the entries expire in the Neighbour-Status table.


6. msm-id

   The Multicast Session Node ID (msm-id) is a numerical value that
   identifies a node with a particular multicast session as well as give
   an indication of the node's relative distance from the root of the
   tree.

     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |        Multicast Session Node ID              |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   6.1.1 Calculating the msm-id

   Address Mapping Function - Calculate_Initial_MSM_ID

   An address mapping function Calculate_Initial_MSM_ID is required to
   map the node's current hop count from the session initiator into a
   larger address space. We illustrate with an example of how the



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 17]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


   function should perform:

   Suppose M is the number of bits of msm-id, let's say 16 bits.  The
   value is calculated using a function that takes in the hop count in
   the NEW-SESSION message and returns a value that is within the 16bit
   range.

   The value returned must be an increasing function of hop count**. We
   do not give a specific function that one must use here. A possible
   function, (though not a very good one is):

     msm-id=INT((2^(M/2))/hop_count)

     The idea is the function will give nodes a widely spaced address
     within the allowable range with the hop count as a initial
     parameter. The larger the hop count, the larger should be the
     multicast node ID and thus msm-id as well.

     **During multicast delivery path initialization, we just want to
     use hop count to "jumpstart" the node's msm-id, subsequently the
     node's msm-id can change as it moves around. Its msm-id would then
     be a function of the upstream and downstream nodes' msm-ids.

     We want to utilize a sparse address space because we foresee such a
     situation:

     Node X ===> Node Y ===> Node Z ===> downstream nodes

     Suppose at time t, node X and node Z can communicate directly. Node
     Z has a set of downstream nodes. At time t+1, link between node X
     and node Z breaks. They must now communicate through an
     intermediate node Y.

     If we are just using hop-count directly as msm-id, then Z and its
     downstream nodes must all increment their msm-id by one since
     datagrams must go through 1 extra hop through Y. Some overhead will
     be required to inform Z's downstream nodes to increment their msm-
     ids.  If we use a sparse address space, Y can just acquire an
     address that is of the nature (X+Z) div 2. The increasing msm-id
     property is maintained and Z and its sub-tree need not update their
     msm-ids. There are other situations when this is also
      useful.

     To ensure that the msm-id remains consistent, each node would
     require a self-check routine. This routine would possibly be based
     on the msm-id of one's neighbours. Another issue is the scalability
     and numbering overflow of msm-id. This will be examined in our
     future work.



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 18]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


7. Multicast Beacon

   The Multicast Beacon can be "piggy-backed" on existing underlying
   layers' beacons, if they are available. Alternatively a separate
   daemon to periodically broadcast the multicast beacon can be used,
   existing within the multicast routing layer.

   The beacon contains the following fields:

       1) Node-unique-id
       2) msm-id and status (member/non-member;lifetime)
       3) Registered parent msm-id and unique-id
       4) Registered child msm-id and unique-id
       5) partition_id(initially will be the original core's id)

       Every node must implement the beacon mechanism. The beacon is a
       one-hop broadcast message sent by every node. The main use of the
       beacon is to detect link breakages within a fixed time
       interval(this is be closely related to the beacon interval)


8. Routing Metric


       We are investigating how routing metrics such as
       associativity[7], received signal strength[8] and can be
       incorporated into AMRIS to select "better" routes. This will be
       discussed further insubsequent drafts.


9. Tables 1. Neighbour-Status Table

     [work-in-progress]

     -----------------------------------------------------------
     |Neighbour| msm-id|Relation-Type |Status|Remaining|Routing|
     |unique-id|       |(eg. parent or|      |Timeout  |Metric |
     |         |       |  child)      |      |Value    |       |
     -----------------------------------------------------------


10. Message Formats

     [work-in-progress] 10.1 NEW-SESSION

     10.2 JOIN-REQ/JOIN-REQ.passive

     10.3 JOIN-ACK/JOIN-ACK.passive/JOIN-NACK



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 19]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


     10.5 JOIN-CONF

     10.5 Modify-msm-id

     10.6 LEAVE-SESSION/END-SESSION


11. Detailed psuedocode [work-in-progress]


12. Timers Description

     Timer Name   Timer value      Timer Purpose
     T1                            NEW-SESSION Lifetime
     T2                            Random delay between receipt of NEW-
     SESSION and subsequent rebroadcast
     T3                            Time out value for JOIN-REQ
     T4                            End-Session message lifetime


13. Future Directions

     Perform Simulation to investigate performance and feasibility.
     Investigate overhead of signalling requirements.  Investigate QOS
     aspects.

14. Applicability Statement

        * Does the protocol provide support for unidirectional links?
     (if so,
        how?)

        - No, bidirectional links are assumed with the first draft.

        * Does the protocol require the use of tunneling? (if so, how?)

        - No.

        * Does the protocol require using some form of source routing?
     (if
        so, how?)

        - No.

        * Does the protocol require the use of periodic messaging? (if
     so,
        how?)




Wu, Tay, and Toh           Expires 24 May 1999                 [Page 20]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


        - Yes. The periodic messaging is in the form of a periodic
     beacon.

        * Does the protocol require the use of reliable or sequenced
     packet
        delivery? (if so, how?)

        - No.

        * Does the protocol provide support for multiple hosts per
     router?
        (if so, how?)

        - This will be covered in subsequent drafts.

        * Does the protocol support the IP addressing architecture? (if
     so,
        how?)

        - Yes, the protocol is based on the IP multicast host group
     model.

        * Does the protocol require link or neighbor status sensing (if
     so,
        how?)

        - Yes, this is done either by the periodic beacon or by
     underlying layers if such facilities exist there

        * Does the protocol have dependence on a central entity? (if so,
        how?)

        - No.

        * Does the protocol function reactively? (if so, how?)

        - Yes, the protocol reacts accordingly to maintain tree when
     links are broken

        * Does the protocol function proactively? (if so, how?)

        - No.

        * Does the protocol provide loop-free routing? (if so, how?)

        - Yes.

        * Does the protocol provide for sleep period operation? (if so,



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 21]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


     how?)

        - TBD.

        * Does the protocol provide some form of security? (if so, how?)

        - TBD.

        * Does the protocol provide support for utilizing multi-channel,
        link-layer technologies? (if so, how?)

        - Yes. TBD.

15. References

   [1] T. Pusateri. Distance Vector Multicast Routing Protocol.
   Internet-Draft, draft-ietf-idmr-dvmrp-v3-06.txt, March 1998.

   [2] John Moy. Multicast extensions to OSPF. RFC1584, March 1994.

   [3] A.J. Ballardie. Core Based Trees(CBT) Multicast Routing
       Architecture, RFC2201 (September 1997).

   [4] D.Estrin, D.Farinacci, A. Helmy, D.Thaler; S. Deering, M.
       Handley, V.Jacobson, C. Liu, P.Sharma, L. Wei. Protocol
   Independent
       Multicast-Sparse Mode (PIM-SM): Protocol Specification. RFC2362,
   June
       1997.

   [5] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, A. Helmy, and
   L. Wei.
       Protocol Independent Multicast Version 2, Dense Mode
       Specification. Internet-Draft, draft-ietf-idmr-pim-dm-spec-05.ps,
       May 21, 1997.

   [6] Corson, S., and J. Macker, "Mobile Ad hoc Networking (MANET):
   Routing
       Protocol Performance Issues and Evaluation Considerations",
       Internet Draft, draft-ietf.manet-issues-00.txt, September 1997.

   [7] C-K Toh, "Associativity Based Routing For Ad Hoc Mobile Networks"
       Wireless Personal Communications Journal', Special Issue on
       Mobile Networking & Computing Systems, Vol. 4, No. 2, March 1997.

   [8] Rohit Dube, Cynthia D. Rais, Kuang-Yeh Wang and Satish K.
   Tripath.
       Signal Stability based Adaptive Routing (SSA) for Ad-Hoc Mobile



Wu, Tay, and Toh           Expires 24 May 1999                 [Page 22]


INTERNET-DRAFT       AMRIS Functional Specification     17 November 1998


       Networks, CS-TR-3646, August 1996.


     This work was supported in part by National University of Singapore
     ARF grant RP960683.


Author's Address

     Questions about this document can also be directed to the authors:

     C.W. Wu
     Mobile Computing Group
     School of Computing
     National University of Singapore
     10 Kent Ridge Crescent
     Singapore 119260
     (65) 472-2628
     wuchunwe@comp.nus.edu.sg

     Y.C. Tay
     Department of Mathematics
     National University of Singapore
     10 Kent Ridge Crescent
     Singapore 119260
     (65) 874-2949
     tay@acm.org

     C-K. Toh
     Mobile Multimedia & HiSpeed Networking Lab
     School of Electrical and Computer Engineering
     Georgia Institute of Technology
     Atlanta, Georgia GA 30332, USA
     C-K.Toh@acm.org

















Wu, Tay, and Toh           Expires 24 May 1999                 [Page 23]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/