idnits 2.17.1 draft-ietf-manet-odmrp-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. 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. == 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 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. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 537 has weird spacing: '...ith the entri...' == Line 545 has weird spacing: '...oup, it origi...' == Line 561 has weird spacing: '...ith the entri...' == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- 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 (June 1999) is 9081 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: '3' is defined on line 838, but no explicit reference was found in the text == Unused Reference: '10' is defined on line 867, but no explicit reference was found in the text -- Possible downref: Normative reference to a draft: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' Summary: 6 errors (**), 0 flaws (~~), 7 warnings (==), 13 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 IETF MANET Working Group Sung-Ju Lee 2 INTERNET-DRAFT William Su 3 Expiration: December 1999 Mario Gerla 4 University of California, Los Angeles 5 June 1999 7 On-Demand Multicast Routing Protocol (ODMRP) for Ad Hoc Networks 9 11 Status of This Memo 13 This document is an Internet-Draft and is in full conformance with 14 all provisions of Section 10 of RFC2026. This document is a 15 a submission to the Mobile Ad-hoc Networks (manet) Working Group 16 of the Internet Engineering Task Force (IETF). Comments should be 17 submitted to the Working Group mailing list at 18 "manet@itd.nrl.navy.mil". Distribution of this memo is unlimited. 20 This document is an Internet-Draft. Internet-Drafts are working 21 documents of the Internet Engineering Task Force (IETF), its areas, 22 and its working groups. Note that other groups may also distribute 23 working documents as Internet-Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six 26 months and may be updated, replaced, or obsoleted by other documents 27 at any time. It is inappropriate to use Internet-Drafts as 28 reference material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 Abstract 38 On-Demand Multicast Routing Protocol (ODMRP) is a multicast routing 39 protocol designed for ad hoc networks with mobile hosts. ODMRP is 40 a mesh-based, rather than a conventional tree-based, multicast 41 scheme and uses a forwarding group concept (only a subset of nodes 42 forwards the multicast packets via scoped flooding). It applies 43 on-demand procedures to dynamically build routes and maintain 44 multicast group membership. ODMRP is well suited for ad hoc 45 wireless networks with mobile hosts where bandwidth is limited, 46 topology changes frequently and rapidly, and power is constrained. 48 Contents 50 Status of This Memo 1 52 Abstract 1 54 1. Introduction 3 56 2. Terminology 4 57 2.1. General Terms . . . . . . . . . . . . . . . . . . . . . . 4 58 2.2. Specification Language . . . . . . . . . . . . . . . . . 4 60 3. Protocol Overview 5 61 3.1. Group Establishment and Route Construction . . . . . . . 5 62 3.1.1. Mesh Creation . . . . . . . . . . . . . . . . . . 5 63 3.1.2. Adapting the Refresh Interval via 64 Mobility Prediction . . . . . . . . . . . . . . . 7 65 3.1.3. Soft State . . . . . . . . . . . . . . . . . . . 7 66 3.2. Contents of Tables . . . . . . . . . . . . . . . . . . . 8 67 3.2.1. Routing Table . . . . . . . . . . . . . . . . . . 8 68 3.2.2. Forwarding Group Table . . . . . . . . . . . . . 8 69 3.2.3. Message Cache . . . . . . . . . . . . . . . . . . 8 70 3.3. Unicast Routing Capability . . . . . . . . . . . . . . . 8 72 4. Packet and Table Formats 9 73 4.1. Join Data Packet Header . . . . . . . . . . . . . . . . 9 74 4.2. Join Table Packet . . . . . . . . . . . . . . . . . . . 11 76 5. Operation 13 77 5.1. Forwarding Group Setup . . . . . . . . . . . . . . . . . 13 78 5.1.1. Originating a Join Data . . . . . . . . . . . . . 13 79 5.1.2. Processing a Join Data . . . . . . . . . . . . . 13 80 5.1.3. Processing a Join Data When GPS is Used . . . . . 14 81 5.1.4. Originating a Join Table . . . . . . . . . . . . 15 82 5.1.5. Processing a Join Table . . . . . . . . . . . . . 15 83 5.1.6. Processing a Join Table When GPS is Used . . . . 16 84 5.1.7. Passive Acknowledgments . . . . . . . . . . . . . 17 85 5.2. Handling a Multicast Data Packet . . . . . . . . . . . . 17 87 6. Protocol Applicability 18 88 6.1. Networking Context . . . . . . . . . . . . . . . . . . . . . 18 89 6.2. Protocol Characteristics and Mechanisms . . . . . . . . . . 18 91 Acknowledgments 20 93 References 20 95 Chair's Address 21 97 Authors' Addresses 22 98 1. Introduction 100 This document describes the On-Demand Multicast Routing Protocol 101 (ODMRP) developed by the Wireless Adaptive Mobility (WAM) Lab [12] 102 at UCLA. ODMRP applies "on-demand" routing techniques to avoid 103 channel overhead and improve scalability. It uses the concept of 104 "forwarding group,"[3] a set of nodes responsible for forwarding 105 multicast data, to build a forwarding mesh for each multicast group. 106 By maintaining and using a mesh instead of a tree, the drawbacks of 107 multicast trees in mobile wireless networks (e.g., intermittent 108 connectivity, traffic concentration, frequent tree reconfiguration, 109 non-shortest path in a shared tree, etc.) are avoided. A soft-state 110 approach is taken to maintain multicast group members. No explicit 111 control message is required to leave the group. We believe the 112 reduction of channel/storage overhead and the relaxed connectivity 113 make ODMRP more scalable for large networks and more stable for 114 mobile wireless networks. 116 The following properties of ODMRP highlight its advantages. 118 * Low channel and storage overhead 120 * Usage of stable routes 122 * Robustness to host mobility 124 * Maintenance and exploitation of multiple redundant paths 126 * Scalability to a large number of nodes 128 * Exploitation of the broadcast nature of wireless environments 130 * Adaptivity to node movement patterns 132 * Reconstruction of routes in anticipation of topology changes 134 2. Terminology 136 2.1. General Terms 138 This section defines terminology used in ODMRP. 140 node 142 A device that implements IP. 144 neighbor 146 Nodes that are within the radio transmission range. 148 forwarding group 150 A group of nodes participating in multicast packet forwarding. 152 multicast mesh 154 The topology defined by the link connection between forwarding 155 group members. 157 join data 159 The special data packet sent by multicast sources to establish 160 and update group memberships and routes. 162 join table 164 The table broadcasted by each multicast receiver and forwarding 165 node to establish and update group membership and routes 167 2.2. Specification Language 169 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 170 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 171 document are to be interpreted as described in RFC 2119 [1]. 173 3. Protocol Overview 175 3.1. Group Establishment and Route Construction 177 3.1.1. Mesh Creation 179 In ODMRP, group membership and multicast routes are established and 180 updated by the source on demand. Similar to on-demand unicast 181 routing protocols, a request phase and a reply phase comprise the 182 protocol. When a multicast source has packets to send but no route 183 and group membership is known, it floods a control packet with data 184 payload attached. This packet, called "Join Data" (format shown in 185 Section 4.1) is periodically broadcasted to the entire network to 186 refresh the membership information and update the routes. When a 187 node receives a Join Data packet, it stores the source ID and the 188 sequence number to its "Message Cache" to detect duplicates. The 189 upstream node ID is inserted or updated as the next node for the 190 source node in its "Routing Table." If the Join Data packet is not 191 a duplicate and the Time-To-Live value is greater than zero, 192 appropriate fields are updated and it is rebroadcasted (operation 193 details are explained in Section 5.1.2). 195 When a Join Data packet reaches the multicast receiver, it creates 196 and broadcasts a "Join Table" to its neighbors. When a node receives 197 a Join Table, it checks if the next node ID of one of the entries 198 matches its own ID. If it does, the node realizes that it is on the 199 path to the source and thus is part of the forwarding group; 200 it sets the FG_FLAG. It then broadcasts its own Join Table built 201 upon matched entries. The next node ID field is filled in by 202 extracting the information from its routing table. This way, the 203 Join Table is propagated by each forward group member until it 204 reaches the multicast source via the selected path. This process 205 constructs (or updates) the routes from sources to receivers and 206 builds a mesh of nodes, the forwarding group. 208 +--+ +--+ +--+ 209 |S1|-------|I1|-------|R1| 210 +--+\ +--+ /+--+ Join Table of Node R1 and Node I1 211 \ / +----------------+ +----------------+ 212 \ / |Sender|Next Node| |Sender|Next Node| 213 \ / |------+---------| |------+---------| 214 \ / | S1 | I1 | | S1 | S1 | 215 \ / |------+---------| +----------------+ 216 +--+ \+--+/ +--+ | S2 | I2 | 217 |S2|-------|I2|-------|R2| +----------------+ 218 +--+ +--+ +--+ 220 Let us consider the above figure as an example of Join Table 221 forwarding process. Nodes S1 and S2 are multicast sources, and nodes 222 R1 and R2 are multicast receivers. Node R2 sends its Join Table to 223 both S1 and S2 via I2, and R1 sends its packet to S1 via I1 and to 224 S2 via I2. When receivers send their Join Tables to next hop nodes, 225 an intermediate node I1 sets the FG_FLAG and builds its own Join 226 Table since there is a next node ID entry in the Join Table received 227 from R1 that matches its ID. Note that the Join Table build by I1 228 has an entry for sender S1 but not for S2 because the next node ID 229 for S2 in the received Join table is not I1. In the meanwhile, node 230 I2 sets the FG_FLAG, constructs its own Join Table and sends it to 231 its neighbors. Note that I2 broadcasts the join table only once even 232 though it receives two Join Tables from the receivers because the 233 second table arrival carries no new source information. Channel 234 overhead is thus reduced dramatically in cases where numerous 235 multicast receivers share the same links to the source. 237 After this group establishment and route construction process, a 238 source can multicast packets to receivers via selected routes and 239 forwarding groups. While outgoing data packets exist, the source 240 sends Join Data every REFRESH_INTERVAL. This Join Data and Join 241 Table propagation process refreshes forwarding group and routes. 242 When receiving the multicast data packet, a node forwards it only 243 when it is not a duplicate and the setting of the FG_FLAG for the 244 multicast group has not expired. This procedure minimizes the 245 traffic overhead and prevents sending packets through stale routes. 247 3.1.2 Adapting the Refresh Interval via Mobility Prediction 249 ODMRP requires periodic flooding of Join Data} to build and refresh 250 routes. Excessive flooding, however, is not desirable in ad hoc 251 networks because of bandwidth constraints. Furthermore, flooding 252 often causes congestion, contention, and collisions. Finding the 253 optimal flooding interval is critical in ODMRP performance. In 254 highly mobile networks where nodes are equipped with GPS [9] (e.g., 255 tactical netwoks with tanks, ships, aircrafts, etc.), we can 256 efficiently adapt the REFRESH_INTERVAL to mobility patterns and 257 speeds by utilizing the location and movement information. Note 258 that ODMRP can still operate efficiently in networks where no such 259 information is available, but the protocol can be further improved 260 if those information can be utilized. 262 We use the location and movement information to predict the duration 263 of time routes will remain valid (the detail of the process is 264 explained in 5.1.3). With the predicted time of route disconnection, 265 Join Data are only flooded when route breaks of ongoing data 266 sessions are imminent. 268 A different route selection method is applied when we use the 269 mobility prediction. The idea is inspired by the Associativity-Based 270 Routing (ABR) protocol [11] which chooses associatively stable 271 routes. In our algorithm, instead of using the minimum delay path, 272 we can choose a route that is the most stable (i.e., the one that 273 will remain connected for the longest duration of time). To select 274 a route, a multicast receiver must wait for an appropriate amount of 275 time after receiving the first Join Data so that all possible routes 276 and their route qualities will be known. The receiver then chooses 277 the most stable route and broadcasts a Join Table. Route breaks will 278 occur less often and the number of Join Data propagation will reduce 279 because stable routes are used. 281 3.1.3. Soft State 283 In ODMRP, no explicit control packets need to be sent to leave the 284 group. If a multicast source wants to leave the group, it simply 285 stops sending any Join Data packets since it does not have any 286 multicast data to send to the group. If a receiver no longer wants 287 to receive from a particular multicast group, it does not send the 288 Join Table for that group. Nodes in the forwarding group are demoted 289 to non-forwarding nodes if not refreshed (no Join Tables received) 290 before they timeout. 292 3.2. Contents of Tables 294 Nodes running ODMRP are required to maintain the following tables. 295 These tables MAY be implemented in any format, but MUST include the 296 fields specified in this document. 298 3.2.1. Routing Table 300 A routing table is created on demand and is maintained by each node. 301 An entry is inserted or updated when a non-duplicate Join Data is 302 received. The node stores the destination (i.e., the source of the 303 Join Data) and the next hop to the destination (i.e., the last node 304 that propagated the Join Data). The routing table provides the next 305 hop information when transmitting Join Tables. 307 3.2.2. Forwarding Group Table 309 When a node is a forwarding group node of the multicast group, it 310 maintains the group information in the forwarding group table. The 311 multicast group ID and the time when the node was last refreshed are 312 recorded. 314 3.2.3. Message Cache 316 The message cache is maintained by each node to detect duplicates. 317 When a node receives a new Join Data or data, it stores the source 318 address and the sequence number of the packet. Note that entries in 319 the message cache need not be maintained permanently. Schemes such 320 as LRU (Least Recently Used) or FIFO (First In First Out) can be 321 employed to expire and remove old entries and prevent the size of 322 the message cache to be extensive. 324 3.3. Unicast Routing Capability 326 One of the major strengths of ODMRP is its unicast routing 327 capability. Not only ODMRP can work with any unicast routing 328 protocol, it can function as both multicast and unicast. Thus, ODMRP 329 can run without any underlying unicast protocol. Other ad hoc 330 multicast routing protocols such as AMRoute [2], CAMP [5], RBM [4], 331 and LAM [7] must be run on top of a unicast routing protocol. CAMP, 332 RBM, and LAM in particular, only work on top of certain underlying 333 unicast protocols. 335 4. Packet and Table Formats 337 4.1. Join Data Packet Header 339 0 1 2 3 340 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 341 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 342 | Type | Reserved | Time To Live | Hop Count | 343 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 344 | Multicast Group IP Address | 345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 346 | Sequence Number | 347 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 348 | Source IP Address | 349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 350 | Previous Hop IP Address | 351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 352 | Previous Hop X Coordinate | 353 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 354 | Previous Hop Y Coordinate | 355 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 356 | Previous Hop Moving Speed | Previous Hop Moving Direction | 357 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 358 | Minimum Link Expiration Time | 359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 361 Type 363 01; ODMRP Join Data. 365 Reserved 367 Sent as 0; ignored on reception. 369 Time To Live 371 Number of hops this packet can traverse. 373 Hop Count 375 The number of hops traveled so far by this packet. 377 Multicast Group IP Address 379 The IP address of the multicast group. 381 Sequence Number 383 The sequence number assigned by the source to uniquely 384 identify the packet. 386 Source IP Address 388 The IP address of the node originating the packet. 390 Previous Hop IP Address 392 The IP address of the last node that has processed this packet. 394 Previous Hop X Coordinate (Optional) 396 The x-coordinate of the last node that has processed this 397 packet. The information can be obtained from the GPS. This 398 field is required only when network hosts are GPS equipped. 400 Previous Hop Y Coordinate (Optional) 402 The y-coordinate of the last node that has processed this 403 packet. The information can be obtained from the GPS. This 404 field is required only when network hosts are GPS equipped.. 406 Previous Hop Moving Speed (Optional) 408 The mobility speed of the last node that has processed this 409 packet. The information can be obtained from the GPS or the 410 node's own instruments and sensors (e.g., campus, odometer, 411 speed sensors, etc.). This field is required only when network 412 hosts are GPS equipped. 414 Previous Hop Moving Direction (Optional) 416 The moving direction of the last node that has processed this 417 packet. The information can be obtained from the GPS or the 418 node's own instruments and sensors (e.g., campus, odometer, 419 speed sensors, etc.). This field is required only when network 420 hosts are GPS equipped. 422 Minimum Link Expiration Time (Optional) 424 The minimum expiration time among the links taken by this 425 packet so far. This field is required only when network hosts 426 are GPS equipped. 428 4.2. Join Table Packet 430 0 1 2 3 431 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 432 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 433 | Type | Count |R|F| Reserved | 434 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 435 | Multicast Group IP Address | 436 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 437 | Previous Hop IP Address | 438 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 439 | Sequence Number | 440 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 441 | Sender IP Address [1] | 442 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 443 | Next Hop IP Address [1] | 444 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 445 | Route Expiration Time [1] | 446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 447 | : | 448 | : | 449 | : | 450 | : | 451 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 452 | Sender IP Address [n] | 453 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 454 | Next Hop IP Address [n] | 455 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 456 | Route Expiration Time [n] | 457 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 459 Type 461 02; ODMRP receiver Join Table. 463 Count 465 Number of (Sender IP Address, Next Hop IP Address) 466 combinations. 468 R 470 Acknowledgment request flag. This flag is set when active 471 acknowledgment packet is requested. 473 F 475 Forwarding group flag. This flag is set when the packet is 476 transmitted by a forwarding group node. 478 Reserved 480 Sent as 0; ignored on reception. 482 Multicast Group IP address 484 The IP address of the multicast group. 486 Previous Hop IP Address 488 The IP address of the last node that has processed this packet. 490 Sequence Number 492 The sequence number assigned by the previous hop node to 493 uniquely identify the packet. 495 Sender IP Address [1..n] 497 The IP addresses of the sources of this multicast group. 499 Next Hop IP Address [1..n] 501 The IP addresses of next nodes that this packet is target to. 503 Route Expiration Time [1..n] (Optional) 505 The minimum route expiration times of this multicast group. 506 This field is required only when network hosts are GPS equipped. 508 5. Operation 510 5.1. Forwarding Group Setup 512 5.1.1. Originating a Join Data 514 When a multicast source has data packets to send but no route is 515 known, it originates a "Join Data" packet. The Type field MUST be 516 set to 01. TTL MAY be set to TIME_TO_LIVE_VALUE, but SHOULD be 517 adjusted based on network size and network diameter. The Sequence 518 number MUST be large enough to prevent wraparound ambiguity, and the 519 Hop Count is initially set to zero. The source puts its IP address 520 in the Source IP Address and Last Hop IP Address field. It appends 521 its location, speed, and direction into JOIN DATA. 523 When location and movement information is utilized, it sets the 524 MIN_LET (Link Expiration Time) field to the MAX_LET_VALUE since the 525 source does not have any previous hop node. When the source receives 526 Join Tables from multicast receivers, it selects the minimum RET 527 (Route Expiration Time) among all the Join Tables received. Then the 528 source can build new routes by originating a Join Data before the 529 minimum RET approaches (i.e., route breaks of ongoing data sessions 530 are imminent). 532 5.1.2. Processing a Join Data 534 When a node receives a Join Data packet: 536 1. Check if it is a duplicate by comparing the (Source IP Address, 537 Sequence Number) combination with the entries in message cache. 538 If duplicate, then discard the packet. DONE. 540 2. If it is not a duplicate, insert an entry into message cache with 541 the information of the received packet (i.e., sequence number and 542 source IP address) and insert/update the entry for routing table 543 (i.e., backward learning). 545 3. If the node is a member of the multicast group, it originates a 546 Join Table packet with the RET value enclosed (see Section 5.1.4). 548 4. Increase the Hop Count field by 1 and decrease the TTL field by 1. 550 5. If the TTL field value is less than or equal to 0, then discard 551 the packet. DONE. 553 6. If the TTL field value is greater than 0, then set the node's IP 554 Address into Last Hop IP Address field and broadcast. DONE. 556 5.1.3. Processing a Join Data When GPS is Used 558 When a node receives a Join Data packet: 560 1. Check if it is a duplicate by comparing the (Source IP Address, 561 Sequence Number) combination with the entries in message cache. 562 If duplicate, then discard the packet. DONE. 564 2. If it is not a duplicate, insert an entry into message cache with 565 the information of the received packet (i.e., sequence number and 566 source IP address) and insert/update the entry for routing table 567 (i.e., backward learning). 569 3. Predict the duration of time the link between the node and the 570 upstream node will remain connected using the following equation. 572 Assume node i is the upstream node and node j is the current node. 573 Let (x_{i}, y_{i}) be the coordinate of node i and (x_{j}, y_{j}) 574 be that of node j. Also let v_{i} and v_{j} be the speeds, and 575 theta_{i} and theta_{j} be the moving directions of nodes i and j, 576 respectively. The information of node i (the previous hop node) 577 can be obtained from the Join Data and the current node's 578 location and mobility information can be provided by the GPS. The 579 duration of time that the link between two nodes will stay 580 connected, D_{t}, is given by: 582 -(a*b + c*d) + sqrt((a^{2} + c^{2})*r^{2} - (a*d - b*c)^{2}) 583 D_{t} = ------------------------------------------------------------ 584 a^{2} + c^{2} 586 where 587 a = v_{i}*cos(theta_{i}) - v_{j}*cos(theta_{j}), 588 b = x_{i} - x_{j}, 589 c = v_{i}*sin(theta_{i}) - v_{j}*sin(theta_{j}), and 590 d = y_{i} - y_{j}. 592 Note that when v_{i} = v_{j} and theta_{i} = theta_{j}, D_{t} is 593 set to infinity without applying the above equation. 595 The minimum between this D_{t} value and the indicated value in 596 MIN_LET field of the Join Data is included in the packet. The 597 rationale is that as soon as a single link on the path is 598 disconnected, the entire path is invalidated. The node also 599 overwrites the location and mobility information field written 600 by the previous node with its own information. 602 4. If the node is a member of the multicast group, it calculates the 603 predicted LET of the last link of the path. The minimum between 604 the last link expiration time and the MIN_LET value specified in 605 the Join Data is the RET (Route Expiration Time). 607 To select a route, a multicast receiver must wait for an 608 appropriate amount of time after receiving the first Join Data 609 so that all possible routes and their RET will be known. The 610 receiver then chooses the most stable route (i.e., the route with 611 the largest RET) and originates a Join Table packet with the RET 612 value enclosed (see Section 5.1.3.). 614 5. Increase the Hop Count field by 1 and decrease the TTL field by 1. 616 6. If the TTL field value is less than or equal to 0, then discard 617 the packet. DONE. 619 7. If the TTL field value is greater than 0, then set the node's IP 620 Address into Last Hop IP Address field and broadcast. DONE. 622 5.1.4. Originating a Join Table 624 A multicast receiver transmits a "Join Table" packet after selecting 625 the multicast route. Each sender IP address and next hop IP address 626 of a multicast group are contained in the Join Table packet. The 627 route expiration time is also included if the network hosts operate 628 with GPS. 630 5.1.5. Processing a Join Table 632 When a Join Table is received: 634 1. The node looks up the Next Hop IP Address field of the received 635 Join Table entries. If no entries match the node's IP Address, do 636 nothing. DONE. 638 2. If one or more entries coincide with the node's IP Address, set 639 the FG_FLAG and build its own Join Table. The next hop IP address 640 can be obtained from the routing table. 642 3. Broadcast the Join Table packet to the neighbor nodes. DONE. 644 5.1.6. Processing a Join Table When GPS is Used 646 When a Join Table is received: 648 1. The node looks up the Next Hop IP Address field of the received 649 Join Table entries. If no entries match the node's IP Address, do 650 nothing. DONE. 652 2. If one or more entries coincide with the node's IP Address, set 653 the FG_FLAG and build its own Join Table. If multiple Join Tables 654 with different RET values are received (i.e., the node lies in 655 paths from the same source to multiple receivers), it selects the 656 minimum RET among them and attaches the chosen RET value. Next 657 hop IP address can be obtained from the routing table. 659 3. Broadcast the Join Table packet to the neighbor nodes. 661 4. If the node is a source, it selects the minimum RET among all the 662 Join Tables received. Then the source can build new routes by 663 flooding a Join Data before the minimum RET approaches (i.e., 664 route breaks of ongoing data sessions are imminent). 666 In addition to the estimated RET value, other factors need to be 667 considered when choosing the refresh interval of Join Data. If 668 the node mobility rate is high and the topology changes 669 frequently, routes will expire quickly and often. The source may 670 propagate Join Requests excessively and this excessive flooding 671 can cause collisions, congestion, and clogs the network with 672 control packets. Thus, the MIN_REFRESH_INTERVAL should be 673 enforced to avoid control message overflow. On the other hand, if 674 nodes are stationary or move slowly and link connectivity remains 675 unchanged for a long duration of time, routes will hardly expire 676 and the source will rarely send Join Data. A few problems arise 677 in this situation. First, if a node in the route suddenly changes 678 its movement direction or speed, the predicted RET value becomes 679 obsolete and routes will not be reconstructed. Second, when a 680 non-member node which is located remotely to multicast members 681 wants to join the group, it cannot inform the new membership or 682 receive data until a Join Data is received. Hence, the 683 MAX_REFRESH_INTERVAL should be set. The selection of the 684 MIN_REFRESH_INTERVAL and the MAX_REFRESH_INTERVAL should be 685 adaptive to network situations (e.g., traffic type, traffic load, 686 mobility pattern, channel capacity, etc.). 688 5.1.7. Passive Acknowledgments 690 The reliable transmission of Join Tables plays an important role 691 in establishing and refreshing multicast routes and forwarding 692 groups. Hence, if Join Tables are not properly delivered, 693 effective multicast routing cannot be achieved by ODMRP. The 694 IEEE 802.11 MAC protocol [6], which is the standard in wireless 695 networks, performs reliable transmission by retransmitting the 696 packet if no acknowledgment is received. However, if the packet 697 is broadcasted, the acknowledgments and retransmissions are not 698 sent. In ODMRP, the transmission of Join Tables are mostly 699 broadcasted. Thus, the verification of Join Table delivery and 700 the retransmissions must be done by the ODMRP layer. 702 We adopt a scheme that was used in [8]. When a node transmits a 703 Join Table packet to the immediate upstream node of the route, 704 the immediate downstream node can hear the transmission if it is 705 within the transmitter's radio range. Hence, the packet is used 706 as an "passive acknowledgment." We can utilize this passive 707 acknowledgments to verify the delivery of Join Tables. Multicast 708 sources must send active acknowledgments to the previous hops 709 since they do not have any next hops to send Join Tables to 710 unless they are forwarding group nodes. When no acknowledgment is 711 received within the timeout interval, the node retransmits the 712 message. If packet delivery cannot be verified after an 713 appropriate number of retransmissions, the node considers the 714 route to be invalidated. The node then broadcasts a message to 715 its neighbors specifying that the next hop to the source cannot 716 be reached. Upon receiving this packet, the neighboring node 717 builds and unicasts the Join Table to its next hop if it has a 718 route to the multicast source. If no route is known, it simply 719 rebroadcasts the packet specifying the next hop is not available. 720 In both cases, the node sets its FG_FLAG. The FG_FLAG setting of 721 every neighbors may create excessive redundancy, but most of 722 these settings will expire because only necessary forwarding 723 group nodes will be refreshed in the next Join Table propagation 724 phase. 726 5.2. Handling a Multicast Data Packet 728 Multicast sources send the Data whenever they have packets to send. 729 Nodes relay data packets only if the packet is not a duplicate and 730 the setting of FG_FLAG for the multicast group has not expired. 732 6. Protocol Applicability 734 6.1. Networking Context 736 ODMRP is best suited for mobile ad hoc wireless networks. 738 6.2. Protocol Characteristics and Mechanisms 740 * Does the protocol provide support for unidirectional links? (if so, 741 how?) 743 - No. We assume bidirectional links. 745 * Does the protocol require the use of tunneling? (if so, how?) 747 - No. 749 * Does the protocol require using some form of source routing? (if 750 so, how?) 752 - No. 754 * Does the protocol require the use of periodic messaging? (if so, 755 how?) 757 - No. 759 * Does the protocol require the use of reliable or sequenced packet 760 delivery? (if so, how?) 762 - No. 764 * Does the protocol provide support for routing through a multi- 765 technology routing fabric? (if so, how?) 767 - No. 769 * Does the protocol provide support for multiple hosts per router? 770 (if so, how?) 772 - No. In this document, we assume each mobile host is combined 773 with a router, sharing the same IP address. It is possible, 774 however, to extend the protocol to handle multiple hosts per 775 router. 777 * Does the protocol support the IP addressing architecture? (if so, 778 how?) 780 - Yes. The message contains host IP address as its identification. 782 * Does the protocol require link or neighbor status sensing (if so, 783 how?) 785 - No. 787 * Does the protocol have dependence on a central entity? (if so, 788 how?) 790 - No. 792 * Does the protocol function reactively? (if so, how?) 794 - Yes. For example, the source creates and maintains routes and 795 multicast group membership only when it has data packets to 796 send. 798 * Does the protocol function proactively? (if so, how?) 800 - No. 802 * Does the protocol provide loop-free routing? (if so, how?) 804 - Yes. By using the Message Cache, duplicate packets are detected 805 and packets can only go through the loop-free route. 807 * Does the protocol provide for sleep period operation? (if so, how?) 809 - TBD. The work is in progress. 811 * Does the protocol provide some form of security? (if so, how?) 813 - TBD. The work is in progress. 815 * Does the protocol provide support for utilizing multi-channel, 816 link-layer technologies? (if so, how?) 818 - This document assumed an arbitrary single channel link-layer 819 protocol. The protocol can work with any MAC and link-layer 820 technology. It can also support multi-channel link-layer 821 technology (e.g., separate channels for data, control packets, 822 etc.). 824 Acknowledgments 826 Authors thank Ching-Chuan Chiang and Guangyu Pei for their initial 827 contributions. 829 References 831 [1] Scott Bradner. Key words for use in RFCs to Indicate 832 Requirement Levels. RFC 2119, March 1997. 834 [2] E. Bommaiah, M. Liu, A. McAuley, and R. Talpade. AMRoute: 835 Adhoc Multicast Routing Protocol. Internet Draft, 836 draft-talpade-manet-amroute-00.txt, Aug. 1998. Work in progress. 838 [3] Ching-Chuan Chiang, Mario Gerla, and Lixia Zhang. Forwarding 839 Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless 840 Networks. ACM/Baltzer Cluster Computing, vol. 1, no. 2, 1998. 842 [4] M.S. Corson and S.G. Batsell. A Reservation-Based Multicast 843 (RBM) Routing Protocol for Mobile Networks: Initial Route 844 Construction Phase. ACM/Baltzer Wireless Networks, vol. 1, 845 no. 4, Dec. 1999, pp. 427-450. 847 [5] J.J. Garcia-Luna-Aceves and E.L. Madruga. A Multicast Routing 848 Protocol for Ad-Hoc Networks. In Proceedings of IEEE 849 INFOCOM'99, New York, NY, Mar. 1999, pp. 784-792. 851 [6] IEEE Computer Society LAN MAN Standards Committee. Wireless 852 LAN Medium Access Protocol (MAC) and Physical Layer (PHY) 853 Specification. IEEE std 802.11-1997. The Institute of Electrical 854 and Electronics Engineers, New York, NY, 1997. 856 [7] L. Ji and M.S. Corson. A Lightweight Adaptive Multicast 857 Algorithm. In Proceedings of IEEE GLOBECOM'98, Sydney, 858 Australia, Nov. 1998, pp. 1036-1042. 860 [8] J. Jubin and J.D. Tornow. The DARPA Packet Radio Network 861 Protocols. Proceedings of the IEEE, vol. 75, no. 1, Jan. 1987, 862 pp. 21-32. 864 [9] E.D. Kaplan (Editor). Understanding the GPS: Principles and 865 Applications, Artech House, Boston, MA, Feb. 1996. 867 [10] S.-J. Lee, M. Gerla, and C.-C. Chiang. On-Demand Multicast 868 Routing Protocol. In Proceedings of IEEE WCNC'99, New Orleans, 869 LA, Sep. 1999 (to appear). 871 [11] C.-K. Toh. Associativity-Based Routing for Ad-Hoc Mobile 872 Networks. Wireless Personal Communications Journal, Special 873 Issue on Mobile Networking and Computing Systems, Kluwer 874 Academic Publishers, vol. 4, no. 2, Mar. 1997, pp. 103-139. 876 [12] UCLA Wireless Adaptive Mobility (WAM) Laboratory. 877 http://www.cs.ucla.edu/NRL/wireless 879 Chair's Address 881 The Working Group can be contacted via its current chairs: 883 M. Scott Corson 884 Institute for Systems Research 885 University of Maryland 886 College Park, MD 20742 887 USA 889 Phone: +1 301 405-6630 890 Email: corson@isr.umd.edu 892 Joseph Macker 893 Information Technology Division 894 Naval Research Laboratory 895 Washington, DC 20375 896 USA 898 Phone: +1 202 767-2001 899 Email: macker@itd.nrl.navy.mil 901 Authors' Addresses 903 Questions about this document can also be directed to the authors: 905 Sung-Ju Lee 906 3771 Boelter Hall 907 Computer Science Department 908 University of California 909 Los Angeles, CA 90095-1596 910 USA 912 Phone: +1 310 206-8589 913 Fax: +1 310 825-7578 914 Email: sjlee@cs.ucla.edu 916 William Su 917 3771 Boelter Hall 918 Computer Science Department 919 University of California 920 Los Angeles, CA 90095-1596 921 USA 923 Phone: +1 310 206-8589 924 Fax: +1 310 825-7578 925 Email: wsu@cs.ucla.edu 927 Mario Gerla 928 3732F Boelter Hall 929 Computer Science Department 930 University of California 931 Los Angeles, CA 90095-1596 932 USA 934 Phone: +1 310 825-4367 935 Fax: +1 310 825-7578 936 Email: gerla@cs.ucla.edu