idnits 2.17.1 draft-talpade-manet-amroute-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-26) 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 Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** 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 are 219 instances of too long lines in the document, the longest one being 4 characters in excess of 72. ** There are 3 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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 (August 6, 1998) is 9395 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) == Unused Reference: '1' is defined on line 891, but no explicit reference was found in the text == Unused Reference: '2' is defined on line 894, but no explicit reference was found in the text == Unused Reference: '3' is defined on line 897, but no explicit reference was found in the text == Unused Reference: '4' is defined on line 900, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 905, but no explicit reference was found in the text ** Downref: Normative reference to an Historic RFC: RFC 2201 (ref. '1') == Outdated reference: A later version (-05) exists of draft-ietf-idmr-pim-arch-04 -- Possible downref: Normative reference to a draft: ref. '2' == 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. '3') == Outdated reference: A later version (-02) exists of draft-ietf-manet-issues-00 ** Downref: Normative reference to an Informational draft: draft-ietf-manet-issues (ref. '4') == Outdated reference: A later version (-01) exists of draft-ietf-manet-term-00 -- Possible downref: Normative reference to a draft: ref. '5' Summary: 14 errors (**), 0 flaws (~~), 10 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force Bommaiah, McAuley and Talpade 3 INTERNET-DRAFT Bellcore 4 Liu 5 Univ of Maryland 6 August 6, 1998 7 Expires: February 7, 1999 9 10 AMRoute: Adhoc Multicast Routing Protocol 12 Status of this Memo 14 This document is an Internet-Draft. Internet-Drafts are working documents 15 of the Internet Engineering Task Force (IETF), its areas, and its working 16 groups. Note that other groups may also distribute working documents as 17 Internet-Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months and 20 may be updated, replaced, or obsoleted by other documents at any time. It 21 is inappropriate to use Internet- Drafts as reference material or to cite 22 them other than as ``work in progress.'' 24 To learn the current status of any Internet-Draft, please check the 25 ``1id-abstracts.txt'' listing contained in the Internet- Drafts Shadow 26 Directories on ftp.ietf.org (US East Coast), nic.nordu.net (Europe), 27 ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). 29 Abstract 31 The Adhoc Multicast Routing Protocol (AMRoute) allows for robust IP 32 Multicast in mobile adhoc networks by exploiting user-multicast trees and 33 dynamic cores. It creates a bidirectional shared-tree for data 34 distribution using only the group senders and receivers as tree nodes. 35 Unicast tunnels are used as the tree links to connect neighbors on the 36 'user-multicast tree.' Thus, AMRoute does not need to be supported by 37 network nodes that are not interested/capable of multicast, and cost is 38 incurred only by group senders and receivers. AMRoute makes certain nodes 39 "core nodes" to initiate the signaling component of AMRoute, such as 40 detection of group members and tree setup. Core nodes differ significantly 41 from those in CBT and PIM-SM, since they are not a central point for data 42 distribution and can migrate dynamically among member nodes. AMRoute is 43 independent of the specific unicast routing protocol; therefore, it can 44 operate seamlessly over separate domains with different unicast protocols. 46 1 Introduction 48 This document describes the Adhoc Multicast Routing Protocol (AMRoute), 49 which enables the use of IP Multicast in mobile adhoc networks ([?], [?]). 50 Existing multicast protocols ([?], [?], [?]) do not work well in adhoc 51 networks as the frequent tree reorganization can cause excessive signaling 52 overhead and frequent loss of datagrams. 54 AMRoute emphasizes robustness even with rapidly changing membership or 55 highly dynamic networks; it does not attempt to provide the absolute 56 minimum bandwidth or latency guarantees in a given topology. It borrows 57 many of the best features of existing multicast protocols; however it has 58 two key new features that make it more robust and efficient in ad-hoc 59 networks: 61 * User-multicast trees, where replication and forwarding is only 62 performed by group members. 64 * Dynamic migration of core node according to group membership and 65 network connectivity. 67 The user-multicast tree includes only the group senders and receivers as 68 its nodes. Each node is aware of its tree neighbors, and forwards data on 69 the tree links. Multicast state is maintained by the group nodes only, and 70 is not required by other network nodes. In fact, AMRoute does not even 71 require non-member nodes to support any IP multicast protocol. The 72 elimination of state in other network nodes clearly saves node resources, 73 especially when compared with broadcast-and-prune native multicast 74 protocols that require per source and per group state at all network nodes. 75 More importantly, especially in highly dynamic adhoc networks, 76 user-multicast trees also eliminate the need to change the tree as the 77 network changes. Neighboring tree nodes are inter-connected by IP-in-IP 78 tunnels, similar to the approach adopted for connecting multicast routers 79 on the MBONE. Consequently, assuming unicast connectivity is maintained 80 among member nodes, the AMRoute distribution tree will continue to function 81 despite network changes. 83 Each group in the network has at least one logical core that is responsible 84 for discovering new group members and creating the multicast tree for data 85 distribution. This logical core is significantly different from the core 86 in CBT and the RP in PIM-SM as it is not the central point on the data path 87 (only for signaling), it is not a preset node (chosen from among currently 88 known members) and it can change dynamically. The absence of a single 89 point of failure is an important requirement for adhoc networks. 91 Other features of AMRoute include some of the best features of other 92 multicast protocols. Like CBT [?] and PIM-SM [?] it uses shared-trees, 93 so only one tree is required per group, improving its scalability. Like 94 DVMRP [?], CBT and PIM the protocol is independent from specific semantics 95 of the underlying unicast routing protocol. Although some efficiency gains 96 are possible by tying the protocol closely with a unicast protocol, we see 97 the independence as more important. Its independence allows use of the 98 optimal ad-hoc unicast protocol for the network and can work transparently 99 across domains supporting different unicast protocols. Like DVMRP and 100 PIM-DM AMRoute provides robustness by periodic flooding, without requiring 101 special core-nodes. Instead of flooding data, AMRoute periodically floods 102 a small signaling message. 104 Although AMRoute has been designed for adhoc networks, the use of shared 105 user multicast trees may also be appropriate for wired networks. We do not 106 describe this wider application here, except to briefly discuss its 107 possible application when group membership is sparsely distributed. As 108 members become more sparse more packet replication is done closer to a 109 source, and the bandwidth saving with multicast become less. Current 110 multicast protocols require per group (and possibly per source) state to be 111 maintained at all intermediate routers on the tree (and possibly all 112 routers in the network); so, even with limited sparseness, the costs of 113 multicast can outweigh the bandwidth savings. Using User Multicast trees 114 (using a version of AMRoute without the expanding search) is better for 115 these sparse members because it does not require group state at 116 intermediate network nodes. 118 2 Assumptions (or lack thereof) 120 AMRoute assumes the existence of an underlying unicast routing protocol 121 that can be utilized for unicast IP communication between neighboring tree 122 nodes. However, no assumptions are made about the syntax or semantics of 123 the unicast protocol, and the same unicast protocol is not required to be 124 used in all domains. The actual paths followed by the two directions of a 125 unicast tunnel connecting neighboring group members may be different. 127 It is not required that all network nodes support AMRoute or any other IP 128 Multicast protocol. Non-multicast routers only need to support unicast, 129 and forward the control packets (without any protocol processing) if the 130 IP-level TTL is non-zero during the expanding ring search. 132 All member nodes must be capable of processing IP-in-IP encapsulation. No 133 group members need have more than one interface or act as unicast routers 134 (we can build a tree entirely from host computers). However, at least one 135 member, and ideally all nodes, must be capable of being AMRouters: 136 forwarding and replicating datagrams to other members. AMRoute routers 137 must be able to set the TTL field in the IP headers (decrementing the inner 138 IP TTL field before a datagram is repackaged and forwarded). 140 We assume that the diameter of an adhoc network will be limited. Packets 141 may be lost or corrupted in transmission on the wireless network. 143 3 Terminology 145 3.1 General Terms 147 * Node: A device that implements IP. 149 * Router: A node that forwards IP packets not explicitly addressed to 150 itself. In case of adhoc networks, all nodes are at least unicast 151 routers. 153 * AMRouter: A node that implements the AMRoute protocol. 155 * Host: Any node that is not a router. 157 * Link: A communication facility or medium over which nodes can 158 communicate at the link layer, such as an Ethernet (simple or bridged). 160 * Interface: A node's attachment to a link. 162 * Group Member/Node: A node that is either a receiver or sender of an 163 IP multicast group. 165 * Logical Core (Node): A group member that is responsible for 166 initiating and maintaining the multicast tree in AMRoute. 168 * Non-core node: A group member that is not a core node. 170 * Mesh: A per group densely connected graph with group members as 171 nodes. 173 * Tree: A per group non-cyclic tree that connects all receivers and 174 possibly sources. 176 * Tree/Mesh link: A unicast tunnel connecting neighboring nodes in a 177 tree/mesh. 179 * Tree/Mesh segment: A set of connected nodes of a group and the 180 associated tree/mesh links. A network could have multiple disjoint 181 segments for the same multicast group. 183 * Native Multicast tree: A tree that is built using branches between 184 directly connected nodes. 186 * User-multicast tree: A tree that is built using virtual branches 187 between group members. 189 3.2 Specification Language 191 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 192 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 193 document are to be interpreted as described in RFC 2119. 195 4 Overview 197 AMRoute creates a per group multicast distribution tree using unicast 198 tunnels connecting group members. The protocol has two key parts: mesh 199 creation and tree creation. AMRoute continuously creates a mesh of 200 bidirectional tunnels between a pair of group members that are "close" 201 together. Using a subset of the available virtual mesh links, the protocol 202 periodically creates a multicast distribution tree. Only "logical core" 203 nodes initiate mesh and tree creation; however, unlike conventional core 204 based protocols the core can migrate dynamically according to group 205 membership and network connectivity. 207 4.1 User-Multicast Distribution Trees 208 G* X *G 209 | * | * / 210 | * | * / 211 | *| * / 212 X----G----X----X----X 213 \ * 214 \ * 215 \ * 216 \* 217 G------X---X----X 218 *| * \ | 219 * | * \ | 220 * | * \ | 221 G---X * X----X 222 / \ * | 223 / \ * | 224 / \ * | 225 X X G 227 G = group member router (AMRoute capable) 228 X = non-member router (need not be multicast or AMRoute capable) 229 ---- = link 230 **** = virtual user-multicast tree 232 Figure 1: A Virtual User-Multicast tree 234 Figure 1 shows a user-multicast tree connecting six members. The group 235 members forward and replicate multicast traffic along the branches of the 236 virtual tree. The datagram sent between logically neighboring nodes is 237 physically sent on a unicast tunnel through potentially many intermediate 238 routers. The path taken by the unicast tunnel can change without affecting 239 the User-multicast tree. 241 There are two key advantages to implementing our multicast protocol using 242 only members: 244 * Provided there remains a path among all nodes connected by mesh 245 branches, the user-multicast tree need not change because of network 246 changes (e.g., because of router movement). This independence improves 247 robustness and reduces signaling overhead. 249 * Non-members are not required to perform packet replication or even 250 support any IP multicast protocol. This places the processing and 251 storage overhead needed to support the multicast tree only on members. 253 The penalty paid for using a user-multicast tree is reduced efficiency. 254 Clearly, bandwidth efficiency is reduced as non-member routers are not 255 allowed to perform packet replication. Furthermore, the delay is often 256 increased. It can be shown, however, that there is at most a doubling in 257 bandwidth needs and increase in delay. Moreover, as the network becomes 258 more dynamic, maintaining a more optimal path will become harder and 259 require increasingly higher signaling overhead. 261 Just as there are many ways to create native multicast trees, there are 262 many ways to create user-multicast trees. We now describe a way that is 263 well suited to ad-hoc networks. 265 4.2 Logical core and non-core members 267 In the AMRoute protocol each group has at least one logical core that is 268 responsible for initiating signaling actions, specifically: a) mesh joins 269 (discovering new group members and disjoint mesh segments as described in 270 Section 4.3) and b) multicast tree creation (see Section 4.4). A non-core 271 node cannot initiate these two operations, acting only as a passive 272 responding agent. Limiting the number of nodes that perform these two 273 functions (ultimately to a single logical core) ensures that AMRoute can 274 scale, without causing excessive signaling or processing overhead. 276 An immediate reaction on hearing about using core nodes is that "Yes, a 277 core improves scalability (as shown by CBT or PIM-SM, but it also causes 278 robustness problems in dynamic networks." However, the AMRoute logical core 279 node is different from a CBT core and PIM-SM RP in several fundamental 280 aspects. In particular, an AMRoute core node: 282 * is not a central point for all data. Forwarding can continue on 283 working branches of the tree irrespective of the status of the logical 284 core and links to the logical core. 286 * is not a preset node. Each multicast tree segment designates one of 287 its nodes to be the core based on the "core resolution algorithm." 289 * changes dynamically. The core node migrates according to group 290 membership and network connectivity. 292 The core resolution algorithm is run in a distributed fashion by all nodes. 293 The goal of the algorithm is to ensure that any group segment has exactly 294 one core node and that the core node migrates to maintain a robust and 295 efficient multicast tree. 297 An AMRoute segment can temporarily have more than one core node for a group 298 after new nodes join or disjoint segments merge together. A network node 299 designates itself as a core when first joining a group. As a logical core 300 a node can quickly discover new group members and join the mesh and tree 301 with its closest neighbors (not just to the existing core (see Section ??). 302 When multiple core nodes exist in a segment, they will advertise their 303 presence by sending out tree creation messages. Core nodes use the 304 reception of tree creation messages from other cores to decide whether to 305 remain as a core (see Section ??). 307 An AMRoute segment can also have no core nodes because the core node 308 disappears (e.g., leaves the group) or an existing segment is split into 309 multiple disjoint segments (e.g., because of link or node failure). If a 310 segment does not have a core node, one of the nodes will designate itself 311 as the core node at some random time, on not receiving any join or tree 312 creation messages (Section ??). 314 A key issue with any algorithm that assigns a single core node is that it 315 can centralize the multicast tree and indeed the mesh links on itself. 316 AMRoute prevents centralization in a number of ways: 318 * A non-core node is not allowed to graft to its own logical core. 319 Without this limitation all group members would ultimately be connected 320 to the core. 322 * All nodes, including the core, are only allowed to have a limited 323 number of tree links. If the limit is reached the node must drop the 324 link furthest (at highest cost) from its current location. 326 * A logical core will only take responsibility as core for a limited time 327 or until some event makes changing the core desirable. A new logical 328 core can be picked, for example when the core's mesh connectivity limit 329 is reached. 331 Clearly the core resolution and change algorithms are key to the robustness 332 and performance of the AMRoute protocol. However, it is also desirable to 333 contain the complexity of the algorithms. Simulations are hence being 334 planned to determine the tradeoffs between simplicity, robustness and 335 efficiency. Any experience or insights other researchers might have had 336 with similar problems are welcome. 338 4.3 Mesh Creation 340 An AMRoute mesh is a graph where each node is a member (sender or receiver) 341 of the group and every link is a bi-directional unicast tunnel. While the 342 mesh establishes connectivity across all the members of a group, a tree is 343 needed for forwarding the data (see Section ??). We use a two step process 344 of creating a mesh before the tree because it is simpler and more robust. 346 A mesh is much simpler to maintain a mesh (that could potentially have 347 loops) than a tree (with no loops) at every stage of member mutual 348 discovery phase. For example, a very naive merging algorithm could result 349 in a loop when three disjoint trees discover each other. In addition, the 350 redundant mesh links contribute towards increased robustness in the case of 351 node/link failures. (Note that the use of unicast tunnels between 352 neighboring nodes of the mesh itself contributes towards robustness in the 353 face of intermediate node/link failures along routes between them as the 354 unicast protocol is expected to establish a separate route around the 355 failed network node/link). 357 4.3.1 Periodic JOIN-REQ Broadcast 359 To create a mesh encompassing all the members (senders or receivers) of a 360 specific group, mechanisms are needed to allow members to discover each 361 other. The expanding ring search mechanism based on TTL-limited broadcasts 362 is adopted. All core nodes periodically broadcast JOIN-REQ messages. The 363 period between JOIN-REQ will be proportional to the TTL value associated 364 with the last JOIN-REQ message. 366 Each member begins by identifying itself to be the core of a 1-node mesh 367 consisting of only itself. The core node sends out JOIN-REQ packets with 368 increasing TTL to discover other members of the group. When a member (core 369 or non-core) node receives a JOIN-REQ from a core for a different mesh for 370 the same group, the node responds back with a JOIN-ACK. A new 371 bi-directional tunnel is established between the core and the responding 372 node of the other mesh. As a consequence of mesh mergers, a mesh will have 373 multiple cores. One of the cores will emerge as the "winning" core of the 374 unified mesh as a result of the core resolution algorithm. 376 4.3.2 Becoming a Passive Non-core node 378 Only logical core nodes initiate the discovery of other disjoint meshes, 379 while both core and non-core nodes respond to the discovery messages. It 380 is simpler and more scalable (in bandwidth usage) to have only the core 381 node initiate discovery as against every node of the mesh. However, to 382 avoid the situation where every merger adds a link to a core (which might 383 result in too many links from the core), non-core nodes can participate in 384 the mergers by responding to discovery messages. 386 4.3.3 Leaving the group 388 If a node leaves a group, they send out a single JOIN-NAK message to their 389 neighboring nodes. If they subsequently receive any data or signaling 390 message for that group they can send out further JOIN-NAK messages. 392 4.3.4 Limitation on link connectivity 394 Whenever, the number of links adjacent to a node exceeds LINK-THRESHOLD, a 395 node must break one or more of its links. Each of the links could be 396 associated with a weight representing the "distance" (example, number of 397 hops) from the neighbor. The links chosen to be broken could be the ones 398 with the farthest neighbors. The farthest neighbor is notified about the 399 link breakage using a JOIN-NAK message. If the message is lost and data is 400 received from this non-neighbor, the JOIN-NAK message will be resent. 402 Periodic mesh reconfiguration is necessary to maintain a reasonably optimal 403 mesh in the face of mobility; however, removing links may result in 404 temporary loss of data and additional overhead. When the links are broken, 405 the mesh might be fragmented into disjoint meshes. Fragmentation is 406 handled in the same manner as node failures. 408 4.3.5 Dynamic Core Migration 410 There might be a need for dynamically migrating the logical core so as to 411 make the tree more optimal. If the core is "closer" to the senders, then 412 the tree may be a close approximation of a source-based tree (which is 413 shared). If the core is at the "center" of the mesh, then TREE-CREATE 414 messages (described in the next section) reach all the nodes of the mesh 415 faster than when the core is at the "edge". In addition, as the core is 416 involved in discovering and merging with other disjoint meshes, dynamically 417 changing the core might help in avoiding the situation where there are 418 excessive links adjacent to a core node. Policies and mechanisms for node 419 changes are still under research. 421 4.4 Tree Creation 423 This section discusses the creation of a tree for data forwarding purposes 424 once a mesh has been established. The core is responsible for initiating 425 the tree creation process. From the point of view of individual nodes of 426 the mesh, this phase involves identifying the subset of links adjacent to 427 it that belong to the tree. 429 4.4.1 Periodic TREE-CREATE Broadcast 431 The core sends out periodic TREE-CREATE messages along all the links 432 adjacent to it in the mesh. (Note that TREE-CREATE messages are sent along 433 the unicast tunnels in the mesh and are processed by group members only, 434 while JOIN-REQ messages are broadcast messages that are processed by all 435 network nodes). 437 The periodicity of the TREE-CREATE messages depends on the size of the mesh 438 and also on the mobility of the nodes of the mesh. As the mesh nodes are 439 mobile, the number of hops between neighbors keeps changing dynamically. 440 Thus, newer and more optimal trees might be created when TREE-CREATE 441 messages are sent out. Group members receiving non-duplicate TREE-CREATEs 442 forward it on all mesh links except the incoming, and mark the incoming and 443 outgoing links as tree links. If a node has a collection of neighbors all 444 1-hop away on the same broadcast capable interface, then the node can send 445 a single broadcast message to all 1-hop neighbors simultaneously. 447 4.4.2 TREE-CREATE-NAK 449 If a link is not going to be used as part of the tree, the TREE-CREATE 450 message is discarded and a TREE-CREATE-NAK is sent back along the incoming 451 links. On receiving a TREE-CREATE-NAK, a group member marks the incoming 452 link as a mesh link and not a tree link. Thus each non-core node considers 453 the link along which a non-duplicate TREE-CREATE message was received and 454 every other link along which no TREE-CREATE-NAK message was received to be 455 part of the tree for a specific group. (Core considers every link adjacent 456 to it to be part of the tree). Note that all these tree links are 457 bidirectional tunnels. 459 The choice of using ACK or NAK in response to the TREE-CREATE messages is 460 dictated by whether robustness or saving bandwidth is more important. If a 461 ACK-based (positive acknowledgment) scheme is used, then data may not be 462 delivered along links where ACKs were lost. This results in loss of data, 463 but no wasting of bandwidth. However, if a NAK (negative acknowledgment) 464 based scheme is used, loss of NAKs can only result in same data being 465 forwarded more than once (which is discarded by the downstream node on 466 reception). 468 When data arrives at a node along one of the tree links, the node forwards 469 the data along all other tree links. However, if data arrives along a 470 non-tree link a TREE-CREATE-NAK message is (again) sent back along that 471 link and the data is discarded. 473 4.4.3 Transient Loops 475 The tree created by the th TREE-CREATE message might not be the same as 476 the one created by th message. A situation may exist where some nodes 477 are forwarding data according to the older tree and some according to the 478 newer tree, which may result in loops or data loss. Such a phase is to be 479 expected due to the dynamic nature of adhoc networks. However it is 480 considered to be transient and AMRoute recovers from it as soon as the 481 network reduces its dynamicity. 483 4.4.4 Node Failures and Group Leaves 485 Nodes leaving a group or node failures are only partially handled by the 486 redundant links in the mesh. In some situation, node failures might result 487 in splitting the mesh into multiple disjoint meshes, where only one of 488 these meshes has the core. 490 Each node in the mesh expects to periodically receive TREE-CREATE messages. 491 In case this message is not received within a specific timeout, the node 492 designates itself to be the core after a random time. The node whose timer 493 expires the earliest succeeds in becoming the core and initiates the 494 processes of discovering other disjoint meshes as well as tree creation. 495 Multiple cores that may arise in this case are resolved by the core 496 resolution procedure. 498 4.4.5 Core Resolution 500 In the event of mesh mergers, there might be multiple active cores in the 501 new mesh. Nodes in the mesh become aware of this situation when they 502 receive TREE-CREATE messages from multiple cores. The nodes execute a core 503 resolution algorithm to decide on a unique core for the mesh and forward 504 TREE-CREATE messages arriving from the unique core and discard TREE-CREATE 505 messages from other cores. As the multiple cores in the mesh will also 506 become aware of the existence of other cores, they will also execute the 507 same core resolution algorithm. All the cores except the "winning" core 508 will demote themselves to non-core state. One simple core resolution 509 algorithm could pick the winning core to be the one with the highest IP 510 address. 512 4.4.6 Picking which branch to use for the Tree 514 There are several possible algorithms that can be used to decide which mesh 515 branches to use for the tree. The simplest approach is to simply accept 516 the first TREE-CREATE message that is received and discard and duplicate 517 TREE-CREATE messages using the sequence number included in each TREE-CREATE 518 message. This results is a reasonable tree, but it is not necessarily the 519 most bandwidth efficient (e.g., using minimum number of total hops) or 520 lowest latency. We are therefore investigating the tradeoff of increasing 521 the complexity of branch selection in order to improve bandwidth efficiency 522 or reduce latency. 524 To improve bandwidth efficiency a node can select the branch from which it 525 received a TREE-CREATE from its closest neighbor (based on the TTL value in 526 the outer IP header). However, in order to prevent the tree from becoming 527 broken (not connecting all group members), the algorithm must a) be able to 528 tell when the TREE-CREATE message has been received before, and b) not 529 change the initial selection until the next round of TREE-CREATE messages 530 are received. To detect duplicates it necessitates the use of a 531 path-vector field in the TREE-CREATE message 533 5 Message Formats 535 AMRoute uses five control messages for signaling purposes: JOIN-REQ, 536 JOIN-ACK, JOIN-NAK, TREE-CREATE, TREE-CREATE-NAK. These are sent directly 537 over IP. JOIN-REQ is the only message broadcast using the expanded ring 538 search, while the other control messages are unicast between group members. 539 The data packets are sent over UDP/IP, with no separate encapsulation for 540 AMRoute. 542 5.1 JOIN-REQ 544 This is broadcast periodically by a logical core for detecting other group 545 segments. 547 0 1 2 3 548 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 550 | Version | Message-ID | Unused | Initial-TTL | 551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 552 | Source IP Address | IP Multicast Address | 553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 555 5.2 JOIN-ACK 557 This is generated by a tree node in response to receiving a JOIN-REQ from a 558 different logical core. 560 0 1 2 3 561 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 563 | Version | Message-ID | Unused | Initial-TTL | 564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 | Source IP Address | IP Multicast Address | 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 568 5.3 JOIN-NAK 570 This is generated by a tree node if its application leaves the group. 572 0 1 2 3 573 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 575 | Version | Message-ID | Unused | Initial-TTL | 576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 577 | Source IP Address | IP Multicast Address | 578 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 579 5.4 TREE-CREATE 581 This is generated periodically by a logical core to refresh the group 582 spanning tree. 584 0 1 2 3 585 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 586 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 587 | Version | Message-ID | Seq-Number | Unused | 588 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 589 | Source IP Address | IP Multicast Address | 590 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 591 | Path Vector (only used with optimized trees) | 592 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 594 5.5 TREE-CREATE-NAK 596 This is generated by a tree node to convert a tree link into a mesh link. 598 0 1 2 3 599 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 600 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 601 | Version | Message-ID | Seq-Number | Unused | 602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 603 | Source IP Address | IP Multicast Address | 604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 606 5.6 Field Descriptions 608 * Version: Version number of AMRoute being used. 610 * Message-ID: Identifies message type; 1: JOIN-REQ 2: JOIN-ACK 3: 611 JOIN-NAK 4: TREE-CREATE 5: TREE-CREATE-NAK 613 * Seq-Number: Monotonically increasing sequence number is used to 614 identify messages uniquely from same source. 616 * Initial-TTL: Set by source of message; indicates number of IP hops 617 traversed when used along with TTL value in IP header. 619 * Source-IP-Address: IP address of original source of message. 621 * IP-Multicast-Address: Identifies multicast group that the message 622 pertains to. 624 * Path Vector: Used to distinguish among replicated versions of the 625 same TREE-CREATE messages when more bandwidth or latency optimal trees 626 are desired. Initially it is set to 0. Each node that performs any 627 replication modifies the value at each replication (see Section 6). 629 6 Detailed Node Operation 631 The detailed operation at each AMRoute-capable node in the adhoc network is 632 now described. The current emphasis of the protocol is on simplicity, 633 hence some of the optimizations (such as dynamic core migration) described 634 in earlier sections are not specified in this version of AMRoute. 636 6.1 State Diagram 638 +------------+ 639 | NON-MEMBER |<------------------------------------ 640 +------------+ ^ 641 | ^ | 642 | | | 643 | | | 644 JOIN | | LEAVE LEAVE | 645 ------------- | | ----- ----- | 646 snd JOIN-REQ | | snd JOIN-NAK snd JOIN-NAK| 647 & TREE-CREATE | | | 648 | | | 649 | | | 650 | | rcv TREE-CREATE & lose | 651 V | ---------------------- | 652 +------------+ x +----------+ 653 | CORE |----------------------------->| NON-CORE | 654 | |<-----------------------------| | 655 +------------+ TREE-CREATE timeout +----------+ 656 -------------------------- 657 snd JOIN-REQ & TREE-CREATE 659 FIGURE 2: Simplified AMRoute Node State Diagram 661 Figure 2 shows the three main AMRoute states and state transitions (with 662 causing events and resulting actions). The states can be interpreted as 663 follows : 665 * NON-MEMBER - a node does not belong to the multicast group. 667 * CORE - a node currently recognizes itself to be a logical core. 669 * NON-CORE - a node is currently a non-core member in the multicast 670 group. 672 A node transitions from the NON-MEMBER state when an application on the 673 node joins a group and transitions to it from all other states when the 674 application leaves the group. 676 A node transitions to the CORE state when an application joins a group, and 677 by default sets itself to be a logical core. A logical core sends out 678 periodic JOIN-REQ messages and TREE-CREATE messages. A logical core 679 becomes a non-core node if it loses in the core resolution procedure that 680 ensues when it receives a TREE-CREATE message from another core belonging 681 to the same multicast group, which means the other core becomes the new 682 core. 684 A non-core member expects periodic TREE-CREATE messages from a logical 685 core. If it does not receive one within the specified period, the 686 associated timer expires and the node resets itself to be a core. 688 6.2 Timers 690 A logical core keeps two timers, namely the JOIN-REQ-SEND timer and the 691 TREE-CREATE-SEND timer. The expiry of JOIN-REQ-SEND causes the node to 692 compute the new TTL value to use for the expanding ring search, broadcast a 693 new JOIN-REQ with this TTL value and reset the timer. The TREE-CREATE-SEND 694 timer is kept to send out periodic TREE-CREATE messages. 696 A non-core member uses a TREE-CREATE-RCV timer. When it expires, the node 697 waits for some random amount of time before it resets itself to be a core, 698 and starts sending out JOIN-REQs and TREE-CREATEs. This period is set to 699 be random to prevent multiple non-core nodes from becoming cores 700 simultaneously. 702 6.3 Data Structures 704 Each member keeps two tables, each containing a set of neighbors, the 705 neighbors on the mesh and the neighbors on the multicast tree. Note that 706 these neighbors are connected by unicast tunnels rather than being physical 707 neighbors. The member also keeps a "hop-count" associated with each mesh 708 link. This hop-count is obtained at the time of mesh link creation, and is 709 updated by the periodic control messages (control messages have original 710 TTL value used by source in the headers). 712 A node tracks the ID of the logical core it currently recognizes, which can 713 be itself. We allow the existence of multiple logical cores in a same 714 group. However, each node only recognizes one logical core at any instant. 715 This information is updated when the node receives a TREE-CREATE from a 716 logical core it did not recognize, or when the node resets itself to be 717 core, as described in detail in the next section. 719 6.4 State Functions 721 6.4.1 NON-MEMBER 723 When a node does not belong to any multicast group, it basically forward 724 any packets it receives, behaving as an intermediate router. 726 6.4.2 CORE 728 Upon entering this state, a node sets its CORE ID to be itself. 730 A logical core sends out two periodic messages: 732 1) JOIN-REQ 734 This message is used to detect other group members. An expanding ring 735 search is used whereby successive JOIN-REQs are broadcast with increasing 736 TTL values every JOIN-REQ-SEND time units. The TTL value can only be 737 increased to a specific upper bound, after which all JOIN-REQs are 738 broadcast using the same value. 740 2) TREE-CREATE 742 This message is used to build the multicast tree. This message is 743 transmitted over the existing mesh links, i.e., this message is sent 744 through unicast tunnels to mesh neighbors. On transmission of a 745 TREE-CREATE, a logical core considers its mesh neighbors as its tree 746 neighbors also until informed otherwise by a TREE-CREATE-NAK. 748 Note that when a node joins a group and sets itself to be a logical core, 749 it has no mesh neighbors prior to receiving a JOIN-ACK or JOIN-REQ. 750 Therefore, the TREE-CREATE message is not transmitted until one or more 751 mesh neighbors exist. 753 A logical core processes the following received messages pertaining to the 754 same multicast group for which it is the core : 756 1) JOIN-ACK 758 * If the JOIN-ACK is responding to a JOIN-REQ sent out by this core, the 759 logical core marks the source of the JOIN-ACK as its mesh neighbor and 760 drops the JOIN-ACK. 762 2) JOIN-REQ 764 * If the JOIN-REQ was transmitted by this core itself (because of the 765 broadcast medium), it is ignored. 767 * If this core is in the same group as the JOIN-REQ indicates and does 768 not have a mesh or tree link to the source of the JOIN-REQ, it returns 769 a JOIN-ACK and drops the JOIN-REQ. (Note that the JOIN-ACK is unicast 770 to the source of the JOIN-REQ). The core marks the source of the 771 JOIN-ACK as its mesh neighbor. 773 * Otherwise the core decrements the TTL of the JOIN-REQ and re-broadcasts 774 it. 776 3) JOIN-NAK 778 * The logical core deletes any existing mesh and tree links with the 779 source of the JOIN-NAK. 781 4) TREE-CREATE 783 * TREE-CREATE messages can only be generated by a logical core. 785 * On receiving the message, the logical core uses the core resolution 786 algorithm to determine the winner. If the core itself wins, the 787 TREE-CREATE is dropped. If the source of this message wins, the 788 receiving node becomes a non-core member and transitions into the 789 NON-CORE state. The receiving node also marks the winning core as a 790 mesh neighbor, and recognizes it as the new logical core. The 791 TREE-CREATE message is forwarded onto downstream mesh links, which are 792 then marked as tree links. 794 5) TREE-CREATE-NAK 796 * The incoming link is marked as a mesh link, instead of a tree link, and 797 the message is dropped. 799 6.4.3 NON-CORE 801 A non-core member does not send out control messages until the 802 TREE-CREATE-RCV timer expires. It then resets itself to be a logical core 803 after a random wait. 805 Similar to a logical core, a non-core member processes the following 806 received messages pertaining to its multicast group : 808 1) JOIN-ACK 810 * A non-core member will NEVER receive a JOIN-ACK message since JOIN-ACK 811 is sent to the source of a JOIN-REQ, which can only be a logical core. 812 Hence any JOIN-ACK received is dropped. 814 2) JOIN-REQ 816 * If this JOIN-REQ comes from a logical core that this node recognizes 817 (which means they are already on the same mesh), decrement the TTL 818 value of the JOIN-REQ and rebroadcast it. 820 * If this JOIN-REQ comes from a different logical core from that 821 recognized by this node, the node returns a JOIN-ACK to the source and 822 marks the source as a mesh neighbor. 824 * If this JOIN-REQ is for a different group, the node decrements the TTL 825 of the JOIN-REQ and re-broadcasts it (acting as an intermediate 826 router). 828 3) JOIN-NAK 830 * The node deletes any existing mesh and tree links with the source of 831 the JOIN-NAK. 833 4) TREE-CREATE 835 * If the source of this TREE-CREATE is the same core as that recognized 836 by this node, and the message has a new sequence number (not a 837 duplicate), the node marks the incoming link as a tree link. It also 838 forwards the message to neighbors along its downstream mesh links and 839 marks them as tree links. 841 * If this TREE-CREATE is a duplicate from the same core as that 842 recognized by this node, the node marks the incoming link as a mesh 843 link. It also sends a TREE-CREATE-NAK message to the upstream node and 844 drops this TREE-CREATE. 846 * If this TREE-CREATE comes from a different logical core from that 847 recognized by this node, it runs the core resolution algorithm to 848 decide the new core. If the new core wins, the node sets the CORE ID 849 to the new core, forwards the TREE-CREATE onto all its downstream mesh 850 links, and marks the incoming and outgoing links as tree links. If the 851 source loses in the core resolution, this TREE-CREATE is dropped. 853 The TREE-CREATE path vector is modified if a node performs does any 854 replication. The node reads the current content of path vector looking for 855 the least significant "1" (Initially the path vector is set to zero) 857 5) TREE-CREATE-NAK 859 * The incoming link is marked as a mesh link, instead of a tree link, and 860 the message is dropped. 862 7 Security 864 [TO BE DONE] Similar to issues in other IP Multicast protocols, but it has 865 the advantage that only group members are involved in the tree creation. 867 8 Current Status 869 Several issues related to the AMRoute protocol design have to be resolved. 870 An extremely simple version of the protocol has been specified above. 871 Depending on feedback received from the MANET working group and experience 872 gained from our simulations, the protocol shall be augmented to improve the 873 tree efficiency. 875 9 ACKNOWLEDGMENTS 877 This work was done under a grant from the Army Research Lab (ARL) ATIRP 878 program. The initial idea of using user-multicast trees was suggested to 879 us by C. Huitema. 881 10 Author Information 883 Bommaiah, Ethendranath (ethen@bellcore.com) 884 Liu, Mingyan (Univ of Maryland, daphnel@isr.umd.edu) 885 McAuley, Anthony (mcauley@bellcore.com) 886 Talpade, Rajesh (rrt@bellcore.com) 888 Bellcore, 445, South St., Morristown, NJ 07960 889 References 891 [1] Ballardie, T., "Core based Trees (CBT) Multicast Routing 892 Architecture", RFC 2201, September, 1997. 894 [2] Deering, S., et al, "Protocol Independent Multicast-Sparse Mode 895 (PIM-SM): Motivation and Architecture", Internet Draft, 896 draft-ietf-idmr-pim-arch-04.txt, October, 1996. 897 [3] Pusateri, T., "Distance Vector Multicast Routing Protocol", 898 Internet Draft, draft-ietf-idmr-dvmrp-v3-06.txt, March 1998. 900 [4] Corson, S., and J. Macker, "Mobile Ad hoc Networking (MANET): 901 Routing Protocol Performance Issues and Evaluation 902 Considerations", Internet Draft, draft-ietf-manet-issues-00.txt, 903 September, 1997. 905 [5] Perkins, C., "Mobile Ad hoc Networking Terminology", Internet 906 Draft, draft-ietf-manet-term-00.txt, October, 1997.