idnits 2.17.1 draft-ietf-manet-amris-spec-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-24) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 22 longer pages, the longest (page 2) being 60 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 23 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. == There are 2 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 405 has weird spacing: '...tes the neigh...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (24 November 1998) is 9283 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-11) exists of draft-ietf-idmr-dvmrp-v3-06 ** Downref: Normative reference to an Informational draft: draft-ietf-idmr-dvmrp-v3 (ref. '1') ** Downref: Normative reference to an Historic RFC: RFC 1584 (ref. '2') ** Downref: Normative reference to an Historic RFC: RFC 2201 (ref. '3') ** Obsolete normative reference: RFC 2362 (ref. '4') (Obsoleted by RFC 4601, RFC 5059) == Outdated reference: A later version (-08) exists of draft-ietf-idmr-pim-dm-spec-05 -- Possible downref: Normative reference to a draft: ref. '5' -- No information found for draft-ietf - is the name correct? -- Possible downref: Normative reference to a draft: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' Summary: 15 errors (**), 0 flaws (~~), 7 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF MANET Working Group C.W. Wu 3 INTERNET-DRAFT Y.C. Tay 4 National University of Singapore 5 C-K. Toh 6 Georgia Institute of Technology 7 24 November 1998 9 Ad hoc Multicast Routing protocol utilizing Increasing id-numberS (AMRIS) 10 Functional Specification 11 13 Status of this Memo 15 This document is an Internet-Draft. Internet-Drafts are working 16 documents of the Internet Engineering Task Force (IETF), its areas, 17 and its working groups. Note that other groups may also distribute 18 working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet- Drafts as reference 23 material or to cite them other than as "work in progress." 25 To view the entire list of current Internet-Drafts, please check the 26 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 27 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern 28 Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific 29 Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 31 Abstract 33 This document introduces a new multicast routing protocol for use 34 over ad hoc networks. The protocol is called AMRIS, short for Ad hoc 35 Multicast Routing protocol utilizing Increasing id-numberS. The 36 conceptual idea behind AMRIS is to assign every node in a multicast 37 session with an id-number. A delivery tree rooted at a particular 38 node called Sid joins up the nodes participating in the multicast 39 session. The relationship between the id-numbers(and the node that 40 owns it) and Sid is that the id-numbers increase in numerical value 41 as they radiate from the root of the delivery tree. The significance 42 of the Sid is that it has the smallest id-number within that 43 multicast session. Utilizing the id-numbers, nodes are able to adapt 44 rapidly to changes in link connectivity. Recovery messages due to 45 link breakages are confined to the region where it occurred. 47 1. Introduction 49 Conventional multicast routing protocols for the Internet[1,2,3,4,5] 50 break down in ad hoc networks[6] because of the dynamic nature of the 51 network topology. The dynamically changing topology, coupled with 52 relatively low bandwidth wireless links causes long convergence 53 times(if they ever converge) and possibly formation of loops which 54 rapidly consume the already limited bandwidth. 56 AMRIS constructs a shared delivery tree among all participant nodes. 57 This is done by first building a DAG rooted at a special node called 58 Sid(Sid has the smallest id within the multicast session and is 59 generally the source node, i.e. the one that expresses the demand for 60 a route). A delivery tree is thus formed by using a subset of the 61 links of the DAG. Multiple senders and receivers are supported on 62 this tree. (We are currently investigating whether the leftover 63 links of the DAG(leftover - those not part of the delivery tree) can 64 be maintained as secondary/backup links. Is the overhead/cost of 65 maintaining them worthwhile vs the advantages that they can bring.) 67 Nodes participating in AMRIS does not require any globally consistent 68 routing state. Permanent loops which may occur due to node movements 69 etc will not occur. AMRIS allows nodes to recover from broken links 70 rapidly [within one multicast beacon period]. Repairs to damaged 71 links are performed locally without need for any central controlling 72 node thus increasing survivability. We expect that most multicast 73 applications are long-lived, therefore rapid route reconstruction is 74 of greater importance compared to rapid route discovery. This may not 75 necessarily be the case in the context of a unicast routing protocol 76 where short route discovery times may be favoured over recovery times 77 when the application lifespan is short. 79 2. Terminology 81 Smallest-ID node (read as Sid) 82 We call the node that starts/initiates a multicast session Sid 83 because it has the smallest msm-id compared with all other nodes 84 for that multicast session. 86 Node 87 A device in the ad hoc network willing to participate in the 88 routing protocol. 90 Potential Parent Node (PPx) 91 If a node X receive any NEW-SESSION message from PPx and PPx has a 92 smaller msm-id than node X, then PPx is considered a Potential 93 Parent Node of X. This information is updated in node X's 94 Neighbour-Status table. 96 Parent Node 97 A node X is the parent node of a node Y if node Y successfully 98 joined the multicast session through X. Node X must have a smaller 99 msm-id than node Y. This information is updated in both X and Y's 100 Neighbour-Status table. 102 Child Node 103 A node Y is the child node of a node X if node Y successfully 104 joined the multicast session through X. Node Y must have a larger 105 msm-id than node X. This information is updated in both X and Y's 106 Neighbour-Status table. 108 Bigger-id node 109 If a node X has a bigger multicast id then Y, then X is called 110 Bigger-id node. 112 Smaller-id node 113 If a node X has a smaller multicast id then Y, then X is called 114 Smaller-id node. 116 Multicast group 117 Nodes participating in multicast communication which includes the 118 senders/sources, receivers and intermediate nodes. 120 Multicast Session ID (ms-id) 121 A unique value identifying a particular multicast session. 123 Multicast Session Member ID (msm-id) 124 An ID number that all nodes within a multicast session must have. 125 The ID differs among nodes and generally increases in numerical 126 value the further a nodes is from Sid. 128 Neighbour-Status Table 129 This table is a conceptual data structure that we employ to keep 130 information regarding the neighbouring nodes and their status. Eg. 131 Participation in which multicast sessions, etc. 133 Multicast Beacon 134 This is a periodic one-hop broadcast sent by all nodes to update 135 neighbouring nodes about its multicast state information. Multicast 136 state information would include the node's unique ID, msm-id as 137 well as it's parent and child msm-ids. 139 3. Assumptions 140 We assume that all nodes within the ad hoc network are willing to 141 participate fully in the protocol. Every node has a unique ID at 142 either the network layer (e.g. IP address) or the link layer (e.g. 143 MAC Address for 802.11). We assume that the underlying unicast layer 144 provides information about symmetric links to upper layers. We assume 145 that there is no underlying beaconing mechanism to detect link 146 breakage. Link breakage detection is performed by making use of the 147 periodic multicast beacon but we do not exclude using additional 148 information such as fading link quality, positional information of 149 nodes, etc to ensure link detection is accurate. If the underlying 150 layers also utilize some form of beaconing, AMRIS can efficiently 151 utilize that beaconing instead for the purpose of supporting ad hoc 152 multicast routing. 154 4. Protocol Overview 156 Each multicast session is identified a globally unique identifier(eg 157 class D IP address). A single node (called Sid) initiates a multicast 158 session by broadcasting a NEW-SESSION message. Sid has the smallest 159 msm-id. All nodes that receive the NEW-SESSION message generates 160 their own msm-id based on the value found in the message. The new 161 msm-id replaces the old value when the NEW-SESSION message is 162 rebroadcasted. Nodes that receive multiple NEW-SESSION messages(for 163 the same multicast session) will choose only one of the messages to 164 process. The NEW-SESSION message thus travels in an expanding ring 165 fashion outwards from Sid. In the initial phase, nodes closer to Sid 166 will generally have smaller msm-ids than those further away. 168 The links of the multicast delivery tree are formed as follows: 170 1) If the requesting node X has a neighbouring node which is already 171 a member of the multicast session, X will join the multicast session 172 by sending a JOIN-REQ to that neighbour. A JOIN-ACK from that 173 neighbour confirms that X is a registered child of the neighbour. X 174 updates its Neighbour-Status table to indicate that that neighbour is 175 a registered parent of X. That neighbour node also updates its own 176 Neighbour-Status to indicate that X is a registered child. 178 2) If the requesting node X only has neighbouring potential 179 parents(i.e nodes with smaller msm-ids but are not yet members of the 180 multicast session), X will send a JOIN-REQ to one of the potential 181 parents. The potential parent is triggered to join the multicast 182 session when it receives the JOIN-REQ from X. It does so by sending 183 out its own JOIN-REQ to its potential parent, if any are available. 184 If the potential parent is Sid, it does not send out any JOIN-REQ 185 (since it has no parents). If the parent node determines that the 186 requesting node X is allowed to join successfully, it will send a 187 JOIN-ACK back the to requesting node X, otherwise it will send a 188 JOIN-NACK. 190 3) If the requesting node X does not have any neighbouring parents or 191 potential parents, it will send a broadcast JOIN-REQ with a ttl of 192 one but with range R. (The ttl determines whether the datagram should 193 be rebroadcast without modification. The range R is another field 194 that specifies if the node should send its own JOIN-REQ or JOIN- 195 REQ.passive in response to the one that was received) All nodes 196 withing range R(number of hops) from X will attempt to join the 197 multicast tree by sending out their own JOIN-REQ.passive. The range R 198 is decremented by one each time a node sends out the JOIN-REQ.passive 199 so that eventually only nodes that are within range R(no. of hops 200 from X) will have generated JOIN-REQ.passive. Nodes that receive a 201 JOIN-REQ.passive with range R equal to zero do not generate any more 202 JOIN-REQ.passve. Note that the contents of the sent JOIN-REQ.passive 203 is different from the JOIN-REQ.passive in that the node will modify 204 the contents with its own information before its sends it out. 206 A JOIN-REQ.passive received by an off-tree node will trigger that 207 node to send a JOIN-REQ.passive only if the range is greater than 208 zero. An on-tree node that receives a JOIN-REQ.passive will reply 209 with a JOIN-ACK.passive. This sets up a set of passive links between 210 the requesting node to possibly several on-tree nodes. The requesting 211 node may eventually receive several JOIN-ACK.passive messages from 212 different potential parents. It chooses one of the potential parents 213 as its registered parent and sends a JOIN-CONF to that parent. The 214 JOIN-CONF received by the parent node will trigger that parent node 215 to send a JOIN-CONF if necessary to its own parent. The passive links 216 maintained by the other potential parents will eventually time out. 217 Potential parent nodes with passive links are allowed to respond to 218 other nodes that might have sent out JOIN-REQ. In doing so, we "re- 219 use" state information collected and minimize expanding ring type 220 broadcasts. 222 Link breakage detection is performed in AMRIS by making use of the 223 multicast beacon. The multicast beacon contains the msm-id of the 224 node and the registered parent and child nodes of the node. 226 5. Protocol Specifics 228 We will explain the protocol in the following sequence: 230 1. Types of Membership/Node Classification 231 2. What is Sid and where does it come from? 232 3. Tree Initialization 233 4. Joining the Multicast Session 234 5. Reaction to mobility/broken links during JOINING phase 235 6. Forwarding Policy 236 7. Reactions to mobility/broken links 237 7.1 Leaf node moves 238 7.2. Intermediate moves 239 7.3. Core node moves 240 8. Reaction to Network partition 241 9. Group Membership 242 10. Terminating the Multicast Session 244 5.1 Types of Membership/Node Classification 246 Nodes are classified into the following types: 248 Interested node (I-node) 249 A node that is interested in a specific multicast session and 250 wishes to join, it does not matter if it is interested to join as 251 either a sender or receiver or both. 253 Uninterested Node (U-node) 254 A node that is not interested in a specific multicast session but 255 is "forced" and became part of the session anyway because it is 256 required to be a relay/intermediate node on the multicast delivery 257 path. If a U-node does not have any descendent nodes that are I- 258 nodes, it will prune itself off the tree. This is one of the main 259 difference between a U-node and a I-node. 261 Leaf node 262 A node at the edge of the multicast tree. A leaf node maybe a 263 sender or a receiver or both. U-nodes that becomes leaf nodes as a 264 result of node movements will remain as leaf nodes only temporarily 265 before they are pruned off. 267 Intermediate node 268 A node in the internal branches of the multicast tree. May be 269 either an I-Node or an U-Node. 271 5.2 What is Sid and where does it come from? 273 Sid is defined as the node that initiated the multicast session by 274 broadcasting the NEW-SESSION message to its surrounding nodes. In a 275 single-sender, multiple-receiver environment, the single-sender would 276 most likely assume the role of Sid. In a multiple-sender, multiple- 277 receiver environment, it is most probable that one of the multiple- 278 senders will assume the role of Sid in initiating the multicast 279 session. Any core-election type of algorithm can be used if there are 280 multiple nodes contending for the role of Sid. Obviously, the choice 281 of the core will have an initial effect on the shape of the delivery 282 tree formed. We hope to have more insight on this matter after 283 analyzing simulation results. 285 5.3 Initializing the Multicast Session 287 We assume that Sid has some means of obtaining a unique identifier 288 for the multicast session. Sid creates a new multicast session by 289 broadcasting a NEW-SESSION message to its surrounding neighbours. The 290 NEW-SESSION will contain among other things, Sid's msm-id, multicast 291 session address, and routing metrics. All nodes that receive the NEW- 292 SESSION message will then generate their own msm-id and replace the 293 msm-id in the message with their own, as well as various routing 294 metrics before broadcasting the message again. Information derived 295 from the NEW-SESSION message is kept in the Neighbour-Status table 296 for up to T1 secs. A random delay of T2 secs is inserted between the 297 receipt of a NEW-SESSION message and its subsequent rebroadcast. A 298 node may receive multiple NEW-SESSION messages from different nodes. 299 If it has not rebroadcast any messages yet, it will keep the message 300 that has the best routing metric. That message is then modified and 301 rebroadcast. Otherwise the messages received are dropped. 303 5.3.1 Bootstrapping the msm-id value 305 Each node that receives the NEW-SESSION message will calculate the 306 initial value of its msm-id using hop count as a parameter to the 307 function F1 Calculate_Initial_msm-id(Section 6 describes the 308 function in greater detail). In a nutshell, the larger the hop- 309 count value in NEW-SESSION message received, the larger will be its 310 msm-id which is the value returned by Calculate_Initial_msm-id. The 311 function's behaviour is such that there is a large msm-id insertion 312 window between nodes that are one hop-count away. This facilitates 313 the subsequent insertions of other nodes in between these two 314 nodes. The beacon will now include the msm-id. If the beacon is 315 implemented within the multicast routing layer and no other 316 multicast session existed before this, the beacon is started up for 317 the first time. 319 The NEW-SESSION message thus travels outward from the Sid in an 320 expanding ring fashion. Eventually every node will have assigned to 321 themselves a msm-id. The msm-id is used when the node joins the 322 multicast session. The msm-id will be removed when the multicast 323 session is no longer desired(or expired). This will release the msm- 324 id usage back to the pool. msm-id is related to specific nodes 325 supporting an active on-going multicast sesssion. 327 5.4 Joining the Multicast Session 329 When a NEW-SESSION message is received, a node X decides if it wishes 330 to join the session by examining the contents of the message. (The 331 contents of the message will obviously contain information about the 332 multicast session). The joining approach attempts to fultil the join 333 in an adjacent approach rather than resorting to localized broadcast 334 right away. If the immediate neighbouring nodes are nodes already on 335 the multicast tree, then this 1-hop 'peek' approach is very fast and 336 efficient. The presence of msm-id helps in identifying the likelihood 337 of a successful join. Our protocol does not cover the area of 338 notifying the senders the identities of receivers(old or new). A 339 node X joins a multicast session in one of several ways depending on 340 the situation: 342 1) Node X has a valid msm-id and has a neighbour that also has a 343 valid msm-id. (this is normally the case after tree initialization) 345 2) Node X does not have a valid msm-id and has a neighbour that also 346 has a valid msm-id. (Probably node X missed the NEW-SESSION 347 broadcast.) 349 3) Node X has a valid msm-id and does not have any neighbours with 350 valid msm-id. (Probably the neighbours have timed out that msm-ids. X 351 must therefore find other nodes that have valid msm-ids) 353 4) Node X does not have a valid msm-id and does not have any 354 neighbours with valid msm-id. (Probably node X missed the NEW-SESSION 355 broadcast.) 357 Case 1 358 Node X sends a JOIN-REQ to that neighbouring potential parent PP1. 359 Potential parent PP1 checks that X can be a child node (i.e. X has 360 a bigger msm-id than Y) of PP1 and sends a JOIN-ACK back to Node X. 361 Potential parent PP1 updates its Neighbour-Status table to indicate 362 that node X is a registered child of PP1. Node X updates its 363 Neighbour-Status table to indicate that node PP1 is a registered 364 parent of X. 366 Case 2 367 If Node X is aware that a neighbour Y can be a potential parent, 368 node X will also know Y's msm-id because it must have received Y's 369 beacon. Node X then assigns itself a msm-id using Y's as a 370 parameter. Node X's situation is now similar to case 1 and node X 371 will behave as in case 1. 373 Case 3-4 374 Node X initiates Branch Reconstruction (BR) with the msm-id. (Refer 375 to Section 5.7 for BR) 377 A node may also receive a JOIN-NACK instead of a JOIN-ACK, if so, 378 node X will initiate BR based on the error code returned in the 379 JOIN-NACK. If X does not receive any reply with T3 secs, it will 380 initiate BR accordingly. 382 When a node PP1 receives a JOIN-REQ from a bigger-msm-id node X, 383 PP1 will be in one of the following situations: 385 1) be part of the multicast session already (as in case 1 above) 387 or 2) it has a msm-id but has not sent out any JOIN-REQ before.(this 388 happens when the node PP1 received the NEW-SESSION message and 389 determined its own msm-id. However the node PP1 was not interested in 390 joining the multicast session. Thus it did not send out any JOIN-REQ 391 of its own yet.) 393 or 3) it has a msm-id and has sent out JOIN-REQ pending reply. (as in 394 case 1 or 2 above) 396 or 4) it does not have a msm-id yet. (as in case 3 or 4 above) 398 PP1's reaction to receiving a JOIN-REQ (dependent on which situation 399 it is it as discussed above) is as follows: 401 Case 1 402 If PP1's msm-id is smaller than the requesting node X, it sends a 403 JOIN-ACK and updates its multicast state tables. if it is bigger or 404 equal, it sends a JOIN-ACK.error="msm id too small/equal" to the 405 requesting node. It updates the neighbour-Status table to indicate 406 the node X is now a registered child node of node PP1. However no 407 multicast traffic is forwarded to X yet until X increases its msm- 408 id to be bigger than PP1. PP1 will know when X has increased its 409 msm-id through X's beacon. 411 Case 2 412 PP1 must now join ('coerced' into joining by X) the multicast 413 session. It sends out a JOIN-REQ.passive to its own potential- 414 parent node. If PP1 successfully joins the multicast session, it 415 will send a JOIN-ACK.passive back to requesting node X. Otherwise, 416 it sends a JOIN-NACK with the appropriate error code. Since PP1 was 417 'coerced' into joining, it will not forward any traffic to X until 418 X sends a JOIN-CONF message to confirm that X has selected PP1 as 419 its parent. Note that this is slightly different from the case 1. 420 (In general, JOIN-REQ/ACK.passive and JOIN-CONF is used when the 421 parent node does not yet have a msm-id) During the time PP1 is 422 waiting for X's JOIN-CONF, the links through PP1 are considered as 423 passive links. The passive links are converted to active links when 424 a JOIN-CONF from X is received. The JOIN-CONF from X will PP1 to 425 send its its parent a JOIN-CONF as well it the parent sent it a 426 JOIN-ACK.passive previously. 428 Case 3 429 PP1 waits until it receives a reply for its own JOIN-REQ or times 430 out. It sends a JOIN-ACK or JOIN-NACK depending on the success of 431 its own JOIN-REQ to node X. 433 Case 4 434 If it does not have a msm-id, then no node should have sent it a 435 JOIN-REQ. it sends a JOIN-NACK.error="NO msm-id yet" back to the 436 JOIN-REQ node. 438 All other nodes that receive a JOIN-REQ with a broadcast address will 439 forward the message provided the time-to-live is not zero yet. The 440 node must keep track of who sent the JOIN-REQ so that a reverse path 441 can be followed subsequently. A node PP1 may also receive a broadcast 442 JOIN-REQ, i.e. a JOIN-REQ with a broadcast address. PP1 will then 443 send out its JOIN-REQ but the ttl is always limited to one. It will 444 follow the behaviour as in case 3. 446 Only the core node does not try to send a JOIN-REQ out when it itself 447 receives JOIN-REQs. 449 5.5 Reaction to mobility/broken links during Joining Phase 451 We discuss how the protocol behaves when links break during Joining 452 Phase. 454 Case 1 455 X lookups Neighbour-Status table and sees Y as a Potential Parent. 456 X sends JOIN-REQ to Y. Y's link to X is broken thereafter. Hence, Y 457 is unable to reply. X eventually times out and goes into BR mode. A 458 broadcast JOIN-REQ is subsequently sent by X in BR mode. Y's status 459 as a potential parent is removed from X's Neighbour-Status table. 461 Case 2 462 X sends JOIN-REQ to Y. Y is not on multicast tree., so Y must join 463 multicast session as well. Y sends out JOIN-REQ.passive to Z. Z 464 sends JOIN-ACK.passive but at this time link between X and Y 465 breaks. Y tries to send to X but will not succeed. Since Y was a U- 466 node, and has no I-node children. Eventually it will time out and 467 prune itself off the tree. X will eventually go into BR mode as in 468 case 1. 470 5.6 Forwarding Policy 472 The forwarding policy rules are as follows for multicast _data_ 473 traffic(not control traffic): 475 1) When a multicast datagram is received, it first checks if the 476 originator is itself, if so, it will drop the datagram. 478 2) If a multicast datagram is received from its registered parent 479 node, it will forward to all registered child nodes. 481 3) If a multicast datagram is received from a registered child node, 482 it will forward to all other registered child nodes and its 483 registered parent node. 485 4) If a multicast datagram is received from any other node, it is not 486 forwarded to any other nodes. 488 5.7 Reaction to mobility/broken links 490 When a link breaks between two nodes, the node with the larger msm-id 491 is supposed to do recovery by going into BR mode. Nodes can also 492 enter BR mode because of unsuccessful joins to its neighbouring 493 nodes. A node X entering BR mode can be classified into having one 494 of the following initial states: 496 1) X has a valid msm-id but does not have any neighbour nodes that 497 can be potential parent or parent nodes. 499 2) X has a valid msm-id and has at least one neighbour node that can 500 be potential parent or parent nodes. 502 3) X does not have a valid msm-id and does not have any neighbouring 503 nodes that can be potential parent or parent nodes. 505 4) X does not have a valid msm-id and has at least one neighbouring 506 node that can be potential parent or parent nodes. 508 In cases 1 and 2, X may have child nodes whose parent node is X. i.e. 509 there is a sub-tree below X. 511 Initial State 1: 512 X sends a broadcast JOIN-REQ beginning with range R of two. If no 513 reply is received after T3 secs, R is increased by one. This is 514 repeated until the number of incremental attempts exceeds the 515 recover delay that may have been specified. If there is no reply, 516 then it means that the multicast session has either ended a long 517 time ago or a network partition has taken place. If X has child 518 nodes, it will send a New-Partition-Id message to all its child 519 nodes. If X does not have any child nodes, then X can either begin 520 a new multicast session or X is unable to join the multicast 521 session. 523 If a JOIN-ACK is received by X, it indicates that X has 524 successfully joined the multicast session. X updates its Neighbour- 525 Status table to indicate that the neighbour node which sent the 526 JOIN-ACK as X's registered parent. If a JOIN-ACK.passive is 527 received, X sends a JOIN-CONF to the neighbour node that send the 528 JOIN-ACK.passive. X updates its Neighbour-Status table that the 529 neigbour is the registered parent of X. A JOIN-ACK.passive is 530 received because the was neighbour 'coerced' to join the multicast 531 session. Since more than one neighbour might do this, a JOIN-CONF 532 is necessary to select the neighbour to be the registered parent. 534 A node that sends out JOIN-ACK.passive does not forward any traffic 535 until it receives a JOIN-CONF. Other requesting nodes can turn this 536 node's passive links into active links if they send a JOIN-CONF to 537 this node. If a JOIN-ACK.error="msm-id too small" is received, X 538 increases its msm-id as required and sends a multicast beacon. If X 539 is unable to increase its msm-id because of child nodes(the child 540 nodes' msm-id may be equal or smaller then the required new value 541 for X), X sends an Modify-msm-id message to its child nodes before 542 increasing its own msm-id. X can detect if its child nodes have 543 increased their msm-id when it receives their beacons. 545 Initial State 2: 546 X sends a JOIN-REQ to the potential parent node PP1. If a JOIN-ACK 547 is received, then X updates its Neighbour-Status table that PP1 is 548 the registered parent of X. If no reply is received from PP1 after 549 T3 secs, X goes into BR mode with initial state 1. 551 Initial State 3: 552 X sends a broadcast JOIN-REQ as in Initial State 1. It's msm-id is 553 set to a random value. Any necessary adjustments will be in 554 response to a JOIN-ACK.error="msm-id too small" message. 556 Initial State 4: 557 X can determine a msm-id for itself based on its neighbour's msm- 558 id. It then re-enters BR with initial state 1. 560 In the case of a JOIN-REQ broadcast, the child nodes Cx of the node 561 X executing BR will also receive the JOIN-REQ. When they 562 rebroadcast it, they must keep track of the rebroadcasted JOIN-REQ 563 so that if a reply should return from one of the child node's(C*) 564 neighbor, the child (C*1) must check that the msm-id of the 565 neighbour is smaller than its own, if not it will send a JOIN- 566 NACK(msm-id error) instead of forwarding the JOIN-ACK to its 567 parent. Child nodes which receive a JOIN-NACK will just forward it 568 along. 570 If X (the node executing BR) receives a JOIN-NACK(msm-id error) 571 forwarded through an on-tree child node, it is treated differently 572 than if it were received from other non-child nodes. To node X the 573 message means that a route exists to a potential parent but that 574 route runs through the its children's links instead. (This new 575 route may be the only available route to the rest of the multicast 576 tree). If the BR has no other routes to potential parents to choose 577 from, then it must change its msm-id such that it is now larger 578 than its children. This process continues to the descendent node 579 which swapped the JOIN-ACK with the JOIN-NACK(msm-id error). This 580 is a really worse case scenario. The BR node can initiate the 581 change by sending a Reverse-msm-id message to the affected child 582 nodes. The Reverse-msm-id message is forwarded only to downstream 583 neighbours that require the change as a result of the BR node's new 584 msm-id. It will stop at the node which swapped the JOIN-ACK with 585 JOIN-NACK. 587 We have looked at what happens when the broken link is between a 588 single upstream node and a single downstream node. We want to refine 589 the basic policy if the broken link is between a single upstream node 590 and multiple downstream nodes. 592 If there originally was a group of neighbouring nodes participating 593 in the same multicast session and their common parent node moves 594 away, then instead of having all the nodes broadcast a JOIN-REQ, it 595 makes more sense to have only a subset of those nodes broadcast the 596 JOIN-REQ. This is done by introducing a short random delay before a 597 JOIN-REQ is sent if a node has more than one neighbour sharing the 598 same parent who is also a member of the multicast session. If the 599 node hears its neighbour JOIN-REQ, it will delay its own JOIN-REQ 600 until either it hears a JOIN-ACK to its neighbour and some timer 601 timouts. A node X will wait random time before transmitting JOIN-REQ. 602 if it hears a JOIN-REQ from a neighbour for a parent node that is 603 also suitable for X. X will delay its JOIN-REQ for Ts. If it hears a 604 JOIN-ACK from the PP1 node, it will send its own JOIN-REQ directly to 605 PP1. If no reply is heard, then it will broadcast its own JOIN-ACK 606 after Ts. 608 We look at some link breakage scenarios and illustrate how BR works 609 out in each case. 611 5.7.1 Reaction to leaf node movement 612 There are two situations of leaf node movement. 614 5.7.1.1 Situation 1: Leaf node moves to new location where multicast 615 tree is already established 617 When the leaf node C1 moves, its parent P1 will eventually detect 618 this. P1 will proceed to prune itself from the tree if P1 is a U- 619 node and has no other child nodes. The pruning is as similar to 620 that described in Section 5.9 Group Membership except the parent 621 does not receive explicit notification from the child node. P1 has 622 received implicit notification as a result of broken link to C1. 624 When C1 moves into new location L2, it can hear node P2's multicast 625 beacon and discover that a multicast tree already exists there. 626 (Another way that C1 can discover P2 is on the multicast tree is 627 hearing multicast traffic for that session being forwarded by P2). 628 If P2 has a smaller msm-id than C1 then C1 can immediately send a 629 JOIN-REQ to P2. If P2 has a larger msm-id, then C1 will increase 630 its msm-id using P2's msm-id as a parameter into Calculate_MSM_ID() 631 to acquire its new msm-id. C1 then sends another JOIN-REQ using its 632 new msm-id. P2 replies with a JOIN-ACK to C1 after it receives the 633 second JOIN-REQ with the new msm-id from C1. It will subsequently 634 forward any multicast traffic to C1 as well. This is similar to the 635 tree initialization process. 637 [Note: C1 does not send a leave notification control message to its 638 old parent P1. Reason for not sending: Network resource consumed in 639 sending a leave message to P1 from C1's new location, must include 640 resource consumed to establish path to old parent no de etc.] 642 5.7.1.2 Situation 2: Leaf node moves to new location where no 643 multicast tree exists 645 The behaviour of the original parent P1 is as in situation 1. When 646 leaf node C1 reaches new location L2, it is unable to discover any 647 existing neighbours who can serve as parent nodes. It then 648 initiates a broadcast BR to its neighbours. Neighbouring nodes 649 which receive the JOIN-REQ will send out their own JOIN- 650 REQ.passive. This is repeated at each node until the range reaches 651 0. An on-tree node that receives the JOIN-REQ.passive will send a 652 JOIN-ACK.passive. The JOIN-ACK.passive travels along the reverse 653 path taken by the original JOIN-REQ and JOIN-REQ.passive. JOIN-REQ- 654 PENDING table. The multicast delivery tree now extends to C1 655 through a set of passive links. C1 must send a JOIN-CONF along one 656 of the passive links to turn it into an active parent link. The 657 parent nodes will start to forward traffic only when a JOIN-CONF is 658 received. 660 5.7.2 Reaction to Intermediate node movement 662 We explain the action taken by an intermediate node that moves such 663 that the link to is parent is broken but the link to its child 664 nodes are still active. The action taken by the intermediate node 665 is similar to that in 5.7.1. except if it receives a JOIN- 666 ACK.error="msm-id too small". Then the intermediate must send a 667 Modify-msm-id message to all its child nodes. If the intermediate 668 node's child links are broken as well, then intermediate node need 669 only to perform the BR if it is a I-node. 671 5.7.3 Reaction to Sid node movement 673 When Sid moves such that its child links are broken, the child 674 nodes will begin a BR process towards the Sid. Only a subset of the 675 child nodes actually broadcast the JOIN-REQ as a result of the 676 optimization performed. 678 5.8 Reaction to Network partition 680 A network partition will cause the multicast tree to be divided into 681 different segments. When a partition takes place, the node X at the 682 point of partition will behave as though it has lost the parent link 683 and will behave as discussed in section X and X. If BR does succeed 684 after n-tries, we can assume that a network partition has take place. 686 Within each partition, multicast traffic continues to be forwarded in 687 accordance to the forwarding rules as stated in Section 6.4, i.e. 688 intra-partition traffic can continue as per normal but inter- 689 partition traffic cannot take place. 691 When this happens, the child node (who is also the one with the 692 smallest-id within this partition) at the point of link breakage will 693 become the new temporary Sid-temp, i.e. the node with the smallest 694 msm-id within that partition. At a later time, the network may be 695 such that a path now exists either between the Sid-temp or one of its 696 child node back to the original partition. 698 When a partition takes place, the Sid-temp should send a Partition-Id 699 change message to its decendent nodes. The message can be sent 700 standalone or piggybacked along multicast traffic. This will update 701 all child nodes eventually. The multicast beacon will carry the new 702 partition-id. 704 Subsequently, any node that hears a beacon for the same multicast 705 session but with a different partition id will send a FOUND_PARTITION 706 message to its own partition's Sid-temp. Only the node with the 707 smallest msm-id will send the message to its own partition's core. 708 The node in the other partition will not. If there is a tie, the one 709 with largest unique id will inform its core. The core will send a 710 JOIN-REQ back to its child node if after it compares the msm-ids, 711 unique ids, of the reporting nodes and the other partitions reporting 712 nodes. 714 The temp core may receive several of such messages. It will choose 715 the one with the best routing metric and send a JOIN-REQ message back 716 to the node. Intermediate nodes which receive the JOIN-REQ will react 717 as discussed in Section 5.7. When a JOIN-ACK returns in response to 718 the JOIN-REQ, the temp core may need to send out Modify-msm-id 719 messages to a subset of its child ndoes that lie on the path to the 720 other partition. 722 So in this situation, we have two partitions with joining together. 723 The node with the smallest msm-id will eventually become the new Sid. 724 However we have a problem if we have two partitions whose core have 725 the same msm-id, then neither partition will join with each other but 726 they are still in different partitions because the original core may 727 be destroyed. 729 5.9 Group Membership 731 Group membership is dynamic in nature, any node is free to join or 732 leave the node at any time except for the Sid. If Sid wishes to 733 leave, another node will have to be designated as the new Sid before 734 the present one can leave. 736 Nodes wishing to join the multicast session after it has already 737 "started" will do so by sending a JOIN-REQ to any of the on-tree 738 nodes as discussed in Section 5.4. On-tree nodes can be detected by 739 listening to its neighbours' beacons and detecting if any of the 740 neighbours are already an on-tree node. If the node is unable to 741 locate any neighboring on-tree nodes, it will begin a N-hop-lifetime 742 JOIN-REQ broadcast to its neighbours. N begins from 2 to MAX-TTL. 743 After sending the broadcast, it will wait for a reply. If no reply is 744 received within time T1, it will increase N by one and send again. 746 Any node that receives the JOIN-REQ and is not an on-tree node will 747 update its NEIGHBOUR-STATUS table and rebroadcast. The behaviour here 748 is similar to tree initialization except that the intermediate nodes 749 may not yet have a msm-id. Similarly the I-node also does not yet 750 have a msm-id. Eventually, the JOIN-REQ will be received by an on- 751 tree node which will reply with a JOIN-ACK. The nodes along the path 752 from the I-node to the on-tree node will then dynamically program 753 their msm-id using their respective parent node's msm-id as parameter 754 into function Calculate_Initial_MSM_ID. 756 A leaf node can leave the multicast session by sending a SESSION- 757 LEAVE message to its parent node. If the parent node is a U-node in 758 the multicast session. It too will send a SESSION-LEAVE message to 759 its own parent node provided it does not have other child nodes. 761 5.10 Terminating the Multicast Session 763 Only Sid can close a multicast session. Nodes are of course free to 764 leave as and when subject to conditions in Section 5.9 - Group 765 Membership. 767 Sid closes the multicast session by sending a SESSION-END message 768 down to its child nodes. This is rebroadcasted by intermediate nodes. 769 All nodes that receive the SESSION-END message purge any 770 entries/state associated with the multicast session. The nodes store 771 the session-id for up to time T4 before finally expiring that entry. 772 This is to take into consideration partitioned networks. If the 773 network is partitioned, the original Sid may have closed the session 774 but the other partitions have not since they did not receive the 775 message. For this reason, nodes which receive the END-SESSION message 776 will remember the session-id for time T4. If the node hears a beacon 777 with state about the session. It will forward the END-SESSION message 778 to it. 780 Each multicast entry in the Neighbour-Status table has an associated 781 timeout value. Session termination can also be done via a soft state 782 approach, i.e. when the entries expire in the Neighbour-Status table. 784 6. msm-id 786 The Multicast Session Node ID (msm-id) is a numerical value that 787 identifies a node with a particular multicast session as well as give 788 an indication of the node's relative distance from the root of the 789 tree. 791 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 792 | Multicast Session Node ID | 793 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 795 6.1.1 Calculating the msm-id 797 Address Mapping Function - Calculate_Initial_MSM_ID 799 An address mapping function Calculate_Initial_MSM_ID is required to 800 map the node's current hop count from the session initiator into a 801 larger address space. We illustrate with an example of how the 802 function should perform: 804 Suppose M is the number of bits of msm-id, let's say 16 bits. The 805 value is calculated using a function that takes in the hop count in 806 the NEW-SESSION message and returns a value that is within the 16bit 807 range. 809 The value returned must be an increasing function of hop count**. We 810 do not give a specific function that one must use here. A possible 811 function, (though not a very good one is): 813 msm-id=INT((2^(M/2))/hop_count) 815 The idea is the function will give nodes a widely spaced address 816 within the allowable range with the hop count as a initial 817 parameter. The larger the hop count, the larger should be the 818 multicast node ID and thus msm-id as well. 820 **During multicast delivery path initialization, we just want to 821 use hop count to "jumpstart" the node's msm-id, subsequently the 822 node's msm-id can change as it moves around. Its msm-id would then 823 be a function of the upstream and downstream nodes' msm-ids. 825 We want to utilize a sparse address space because we foresee such a 826 situation: 828 Node X ===> Node Y ===> Node Z ===> downstream nodes 830 Suppose at time t, node X and node Z can communicate directly. Node 831 Z has a set of downstream nodes. At time t+1, link between node X 832 and node Z breaks. They must now communicate through an 833 intermediate node Y. 835 If we are just using hop-count directly as msm-id, then Z and its 836 downstream nodes must all increment their msm-id by one since 837 datagrams must go through 1 extra hop through Y. Some overhead will 838 be required to inform Z's downstream nodes to increment their msm- 839 ids. If we use a sparse address space, Y can just acquire an 840 address that is of the nature (X+Z) div 2. The increasing msm-id 841 property is maintained and Z and its sub-tree need not update their 842 msm-ids. There are other situations when this is also 843 useful. 845 To ensure that the msm-id remains consistent, each node would 846 require a self-check routine. This routine would possibly be based 847 on the msm-id of one's neighbours. Another issue is the scalability 848 and numbering overflow of msm-id. This will be examined in our 849 future work. 851 7. Multicast Beacon 853 The Multicast Beacon can be "piggy-backed" on existing underlying 854 layers' beacons, if they are available. Alternatively a separate 855 daemon to periodically broadcast the multicast beacon can be used, 856 existing within the multicast routing layer. 858 The beacon contains the following fields: 860 1) Node-unique-id 861 2) msm-id and status (member/non-member;lifetime) 862 3) Registered parent msm-id and unique-id 863 4) Registered child msm-id and unique-id 864 5) partition_id(initially will be the original core's id) 866 Every node must implement the beacon mechanism. The beacon is a 867 one-hop broadcast message sent by every node. The main use of the 868 beacon is to detect link breakages within a fixed time 869 interval(this is be closely related to the beacon interval) 871 8. Routing Metric 873 We are investigating how routing metrics such as 874 associativity[7], received signal strength[8] and can be 875 incorporated into AMRIS to select "better" routes. This will be 876 discussed further insubsequent drafts. 878 9. Tables 1. Neighbour-Status Table 880 [work-in-progress] 882 ----------------------------------------------------------- 883 |Neighbour| msm-id|Relation-Type |Status|Remaining|Routing| 884 |unique-id| |(eg. parent or| |Timeout |Metric | 885 | | | child) | |Value | | 886 ----------------------------------------------------------- 888 10. Message Formats 890 [work-in-progress] 10.1 NEW-SESSION 892 10.2 JOIN-REQ/JOIN-REQ.passive 894 10.3 JOIN-ACK/JOIN-ACK.passive/JOIN-NACK 895 10.5 JOIN-CONF 897 10.5 Modify-msm-id 899 10.6 LEAVE-SESSION/END-SESSION 901 11. Detailed psuedocode [work-in-progress] 903 12. Timers Description 905 Timer Name Timer value Timer Purpose 906 T1 NEW-SESSION Lifetime 907 T2 Random delay between receipt of NEW- 908 SESSION and subsequent rebroadcast 909 T3 Time out value for JOIN-REQ 910 T4 End-Session message lifetime 912 13. Future Directions 914 Perform Simulation to investigate performance and feasibility. 915 Investigate overhead of signalling requirements. Investigate QOS 916 aspects. 918 14. Applicability Statement 920 * Does the protocol provide support for unidirectional links? 921 (if so, 922 how?) 924 - No, bidirectional links are assumed with the first draft. 926 * Does the protocol require the use of tunneling? (if so, how?) 928 - No. 930 * Does the protocol require using some form of source routing? 931 (if 932 so, how?) 934 - No. 936 * Does the protocol require the use of periodic messaging? (if 937 so, 938 how?) 939 - Yes. The periodic messaging is in the form of a periodic 940 beacon. 942 * Does the protocol require the use of reliable or sequenced 943 packet 944 delivery? (if so, how?) 946 - No. 948 * Does the protocol provide support for multiple hosts per 949 router? 950 (if so, how?) 952 - This will be covered in subsequent drafts. 954 * Does the protocol support the IP addressing architecture? (if 955 so, 956 how?) 958 - Yes, the protocol is based on the IP multicast host group 959 model. 961 * Does the protocol require link or neighbor status sensing (if 962 so, 963 how?) 965 - Yes, this is done either by the periodic beacon or by 966 underlying layers if such facilities exist there 968 * Does the protocol have dependence on a central entity? (if so, 969 how?) 971 - No. 973 * Does the protocol function reactively? (if so, how?) 975 - Yes, the protocol reacts accordingly to maintain tree when 976 links are broken 978 * Does the protocol function proactively? (if so, how?) 980 - No. 982 * Does the protocol provide loop-free routing? (if so, how?) 984 - Yes. 986 * Does the protocol provide for sleep period operation? (if so, 988 how?) 990 - TBD. 992 * Does the protocol provide some form of security? (if so, how?) 994 - TBD. 996 * Does the protocol provide support for utilizing multi-channel, 997 link-layer technologies? (if so, how?) 999 - Yes. TBD. 1001 15. References 1003 [1] T. Pusateri. Distance Vector Multicast Routing Protocol. 1004 Internet-Draft, draft-ietf-idmr-dvmrp-v3-06.txt, March 1998. 1006 [2] John Moy. Multicast extensions to OSPF. RFC1584, March 1994. 1008 [3] A.J. Ballardie. Core Based Trees(CBT) Multicast Routing 1009 Architecture, RFC2201 (September 1997). 1011 [4] D.Estrin, D.Farinacci, A. Helmy, D.Thaler; S. Deering, M. 1012 Handley, V.Jacobson, C. Liu, P.Sharma, L. Wei. Protocol 1013 Independent 1014 Multicast-Sparse Mode (PIM-SM): Protocol Specification. RFC2362, 1015 June 1016 1997. 1018 [5] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, A. Helmy, and 1019 L. Wei. 1020 Protocol Independent Multicast Version 2, Dense Mode 1021 Specification. Internet-Draft, draft-ietf-idmr-pim-dm-spec-05.ps, 1022 May 21, 1997. 1024 [6] Corson, S., and J. Macker, "Mobile Ad hoc Networking (MANET): 1025 Routing 1026 Protocol Performance Issues and Evaluation Considerations", 1027 Internet Draft, draft-ietf.manet-issues-00.txt, September 1997. 1029 [7] C-K Toh, "Associativity Based Routing For Ad Hoc Mobile Networks" 1030 Wireless Personal Communications Journal', Special Issue on 1031 Mobile Networking & Computing Systems, Vol. 4, No. 2, March 1997. 1033 [8] Rohit Dube, Cynthia D. Rais, Kuang-Yeh Wang and Satish K. 1034 Tripath. 1035 Signal Stability based Adaptive Routing (SSA) for Ad-Hoc Mobile 1036 Networks, CS-TR-3646, August 1996. 1038 This work was supported in part by National University of Singapore 1039 ARF grant RP960683. 1041 Author's Address 1043 Questions about this document can also be directed to the authors: 1045 C.W. Wu 1046 Mobile Computing Group 1047 School of Computing 1048 National University of Singapore 1049 10 Kent Ridge Crescent 1050 Singapore 119260 1051 (65) 472-2628 1052 wuchunwe@comp.nus.edu.sg 1054 Y.C. Tay 1055 Department of Mathematics 1056 National University of Singapore 1057 10 Kent Ridge Crescent 1058 Singapore 119260 1059 (65) 874-2949 1060 tay@acm.org 1062 C-K. Toh 1063 Mobile Multimedia & HiSpeed Networking Lab 1064 School of Electrical and Computer Engineering 1065 Georgia Institute of Technology 1066 Atlanta, Georgia GA 30332, USA 1067 C-K.Toh@acm.org