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 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]