idnits 2.17.1 draft-labiod-manet-srmp-00.txt: -(1493): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1494): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1502): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1503): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding 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: ---------------------------------------------------------------------------- ** 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 is more than 15 pages and seems to lack a Table of Contents. == There are 7 instances of lines with non-ascii characters in the document. == 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 separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The abstract seems to contain references ([2], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The "Author's Address" (or "Authors' Addresses") section title is misspelled. == Line 266 has weird spacing: '...odes in the n...' == Line 515 has weird spacing: '...s field of th...' == Line 601 has weird spacing: '...ress of the m...' == Line 844 has weird spacing: '...vements occur...' == Line 863 has weird spacing: '...ch node maint...' == (2 more instances...) == 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: 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' ** Obsolete normative reference: RFC 1700 (ref. '8') (Obsoleted by RFC 3232) -- 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: 7 errors (**), 0 flaws (~~), 10 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Houda LABIOD 2 6 November 2001 ENST, Paris 3 Hasnaa MOUSTAFA 4 ENST, Paris 6 The Source Routing-based Multicast Protocol for 7 Mobile Ad Hoc Networks (SRMP) 8 10 Status of This Memo 12 This document is an Internet-Draft and is subject to all provisions 13 of Section 10 of RFC2026. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 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 The list of current Internet-Drafts can be accessed at: 26 http://www.ietf.org/ietf/1id-abstracts.txt 27 The list of Internet-Draft Shadow Directories can be accessed at: 28 http://www.ietf.org/shadow.html. 30 This document is an individual submission for consideration by the 31 Manet Working Group of the Internet Engineering Task Force (IETF). 32 Comments on this draft may be sent directly to authors and to the 33 mailing list. 35 Distribution of this memo is unlimited. 37 Abstract 39 The Source Routing-based Multicast Protocol (SRMP) is designed to 40 provide multicast functionality in mobile ad hoc networks. It applies 41 the source routing mechanism defined by the Dynamic Source Routing 42 (DSR) [1] in a modified manner decreasing the size of the packet 43 header. SRMP obtains multicast routes on-demand through constructing 44 a mesh (an arbitrary subnet) to connect group members providing 45 robustness against mobility. This protocol minimizes the flooding 46 scope using the Forwarding Group (FG) nodes concept [2]. The criteria 47 used for selecting FG nodes allows the choice of stable paths with 48 higher battery life. This protocol operates in a loop-free manner, 49 minimizing channel overhead and making efficient use of network 50 resources. The mesh-based approach avoids drawbacks of multicast 51 trees, where multicast packets can be delivered to the destination 52 in case of frequent node movements and channel fading. SRMP 53 outperforms other multicast protocols by providing available paths 54 based on future prediction for links state. These paths also 55 guarantee nodes stability with respect to their neighbors, strong 56 connectivity between nodes, and higher battery life. 58 Contents 60 Status of this memo i 62 Abstract ii 64 1. Introduction 1 66 2. Overview of DSR 1 68 3. SRMP 2 69 3.1. Protocol Overview ........................................2 70 3.2. Assumptions ..............................................3 71 3.3. Used Terminology .........................................4 72 3.3.1. SRMP Terminology ...............................4 73 3.3.2. Specification Language .........................5 74 3.4. SRMP Header Format .......................................5 75 3.4.1. Fixed Portion of SRMP Header ...................5 76 3.4.2. Join Request Option ............................7 77 3.4.3. Join Reply Option ..............................8 78 3.4.4. Multicast Route Error Option ...................9 79 3.4.5. Leave Group Option ............................10 80 3.4.6. Pad1 Option ...................................11 81 3.4.7. PadN Option ...................................12 82 3.5. Data Packet Format ......................................12 83 3.6. FG Selection Criteria ...................................13 84 3.6.1. Association Stability .........................14 85 3.6.2. Link Signal Strength ..........................14 86 3.6.3. Battery Life ..................................14 87 3.6.4. Link Availability Estimation ..................15 88 3.7. Data Structures .........................................15 89 3.7.1. Multicast Message Duplication Table ...........15 90 3.7.2. Neighbor Stability Table ......................16 91 3.7.3. Multicast Routing Cache .......................16 92 3.7.4. Receiver Multicast Routing Table ..............17 94 4. SRMP Operation 18 95 4.1. Route Request Phase .....................................18 96 4.2. Reply Phase and FG Node Selection .......................19 97 4.3. Data Forwarding .........................................20 98 4.4. Member Node Transmission ................................21 99 4.5. Maintenance Procedures ..................................21 100 4.5.1. Neighbor Existence Mechanism ..................22 101 4.5.2. Mesh Refreshment Mechanism ....................22 102 4.5.3. Link Repair Mechanism .........................23 103 4.5.4. Pruning Scheme ................................24 105 5. SRMP-ODRMP Comparison 25 107 6. Constants 25 108 7. IANA Considerations 26 110 8. QoS and Security Considerations 26 112 Acknowledgments 27 114 References 28 116 Authors Addresses 29 117 1. Introduction 119 Multipoint communication has emerged as one of the most important 120 research areas in the field of network. Multicast plays an important 121 role in ad hoc networks, where network hosts work in groups to carry 122 out a given task. It is also very useful in one-to-many data 123 dissemination in critical situations such as disaster recovery or in 124 the battlefield. 126 In fact, designing multicast routing protocols is a complex problem. 127 Group membership MAY change, and network topology can also evolve 128 (links and nodes can fail). The technical challenge lies in 129 constructing protocols that minimize storage and network load, 130 providing basic support for reliable transmission, and designing 131 optimal routes [3]. 133 There are few multicast routing protocols that have been recently 134 proposed for ad hoc networks, this document describes the Source 135 Routing-based Multicast Protocol (SRMP). SRMP is an on-demand 136 multicast routing protocol constructing a mesh (an arbitrary subnet) 137 to connect group members thus providing robustness against mobility. 138 Multicast routes and group membership are obtained on-demand to use 139 efficiently network resources, avoiding channel overhead and 140 improving scalability. The mechanism of source routing proposed in 141 DSR unicast protocol has been modified to be applied in SRMP. 143 SRMP uses the concept of "forwarding group" to build a forwarding 144 mesh for each multicast group. By maintaining and using a mesh 145 instead of a tree, the drawbacks of multicast trees (e.g., 146 intermittent connectivity, traffic concentration, frequent trees 147 reconfiguration, non-shortest path in a shared tree) are avoided. 148 Some relevant enhancements are introduced in SRMP to overcome some 149 drawbacks of other protocols as ODMRP [4,5]. A selection criteria is 150 used to provide stable paths based on links availability according 151 to future prediction of link states, and higher battery life paths 152 tending to power conserving. SRMP applies also an efficient 153 mechanism to maintain group members making use of data propagation 154 and requiring no extra control overhead. Moreover, a pruning 155 mechanism is used to allow a node to leave the group, thus 156 preventing stale routes to be found at the forwarding nodes. 158 2. Overview of DSR 160 DSR is an on-demand routing protocol which allows nodes to 161 dynamically discover a source route across multiple networks hops 162 to any destination in the ad hoc network [1]. Each data packet 163 follows a source route stored in its header giving the address of 164 each node through which the packet SHOULD be forwarded in order to 165 reach its final destination. Mobile nodes are REQUIRED to maintain 166 route caches containing the learned source routes. 168 DSR employs two mechanisms to enable unicast routing: Route 169 Discovery and Route Maintenance. When a node wishes to communicate 170 with another node, which has no stored route for it in its cache, it 171 invokes the Route Discovery procedure flooding a Route Request 172 (RREQ) packet through the network in search of a route to the 173 destination. Upon receiving a RREQ by the destination or an 174 intermediate node with routing information about destination, it 175 contains a route record yielding the sequence of hops taken. Then, 176 a Route Reply (RREP) to the requestor node is generated 177 following the reverse path. 179 The Route Maintenance mechanism monitors the status of source route 180 in use, detects link failures and repairs routes. This is 181 accomplished through the use of Route Error (RERR) packets and 182 acknowledgements. When the data link layer encounters a fatal 183 transmitting problem at a node, RERR packets are generated to the 184 original sender of the packet encountering the error. A node 185 receiving a RERR packet removes the hop in error from its cache and 186 all routes containing the hop are truncated. Acknowledgements are 187 also used to verify the correct operation of the protocol. 189 3. SRMP 191 This section gives an overview on SRMP, defining some terminology 192 used in designing this protocol and stating the criteria used to 193 select FG nodes. Data structures used for building SRMP together 194 with the format of control messages are also described in this 195 section. 197 3.1. Protocol Overview 199 Source Routing-based Multicast Protocol (SRMP) is an on-demand 200 multicast routing protocol. One distinguishing feature of SRMP is 201 the on-demand establishment of a mesh structure to connect group 202 members, providing redundant paths between members. By building a 203 mesh, packets can be delivered to multicast receivers in the case of 204 node movements and topology changes. Routers are allowed to 205 accept unique packets coming from any neighbor in the mesh. In 206 addition, drawbacks of multicast trees can be avoided (ex., 207 intermittent connectivity, traffic concentration, frequent tree 208 reconfiguration, non-shortest path in a shared tree). 210 SRMP is based on the idea of source routing proposed in DSR unicast 211 protocol. This is applied in a modified manner reducing the 212 flooding scope for packets carrying the source route, such that 213 source route accumulates in the reply packet during the reply phase 214 instead of accumulating in the request packet during request phase 215 of DSR. Source route accumulation takes place during FG nodes 216 selection starting from the receiver side, and constructing a mesh 217 towards the source. Applying the source route concept allows loop 218 free in packets routing, and avoids the need for up-to-date routing 219 information in the intermediate nodes. Source routing also allows 220 nodes that are forwarding the packets to cache the routing 221 information for their own future use. 223 To establish a mesh for each multicast group, SRMP uses the concept 224 of Forwarding Group (FG) nodes. This scheme can be viewed as a 225 "limited scope" flooding within a properly selected forwarding set 226 of nodes. By the use of FG nodes concept and the application of on- 227 demand routing technique, SRMP reduces channel and storage overhead 228 thus improving performance and scalability. 230 Operation starts when a node wants to transmit to the multicast 231 group and has no route to this group. A route discovery procedure 232 is then invoked through broadcasting Join-request message searching 233 for the multicast group members. A multicast receiver, receiving a 234 Join-request, starts selecting FG nodes from its neighbors and sends 235 Join-reply messages to them. This process of selection and Join- 236 reply transmission is repeated by each FG node until reaching the 237 source. Then, a mesh is constructed between the source and the 238 multicast receivers consisting of FG nodes to forward the multicast 239 data. Finally, the source selects one of the routes of the mesh to 240 transmit its data. 242 For example, suppose a network consisting of source node S and two 243 multicast receivers R1 and R2. The Join-reply packets initiated in 244 this example selects nodes A and C as FG nodes (mesh members) and 245 constructs the mesh {A,C} to connect the source S with the multicast 246 receivers R1 and R2. 248 +------+ +------+ +------+ 249 | S |-----| A |-----| R1 | 250 | |-----| |-----| | 251 +------+ +------+ +------+ 252 | || || 253 | || || 254 | || || 255 +------+ +------+ +------+ 256 | B |-----| C |-----| R2 | 257 | | | |-----| | 258 +------+ +------+ +------+ 260 3.2. Assumptions 262 We assume that all nodes wishing to communicate with other nodes 263 within the ad hoc network are willing to participate fully in the 264 protocols of the network. In particular, each node participating in 265 the network SHOULD also be willing to forward packets for other 266 nodes in the network. 268 We refer to the minimum number of hops necessary for a packet to 269 reach from any node located at one extreme edge of the network to 270 another node located at the opposite extreme, as the diameter of the 271 network. We assume that the diameter of an ad hoc network will be 272 small (e.g., perhaps 5 or 10 hops), but MAY often be greater than 1. 274 Packets MAY be lost or corrupted in transmission on the wireless 275 network. A node receiving a corrupted packet can detect the error 276 and discard the packet. 278 3.3. Used Terminology 280 3.3.1. SRMP Terminology 282 This section defines some terminology used in SRMP. 284 Source Routing 286 Each data packet carries in its header the set of nodes through 287 which this packet MUST be transmitted. 289 Mesh 291 A multicast mesh is a subset of the network topology that provides 292 at least one path from each source to each receiver of the multicast 293 group. 295 Forwarding Group 297 The forwarding group is a set of nodes responsible for forwarding 298 multicast data between any member pairs. 300 Available Paths 302 By "a path being available", we mean that the radio quality of each 303 link in the path satisfies the minimal requirements for successful 304 communication [6]. 306 Stale Routes 308 Invalid routes between the node and different destinations that are 309 still stored in the node's routing table. 311 Pruning 313 When a multicast member wants to leave the group. This MAY take 314 place when a multicast source has finished its transmission, or when 315 a multicast receiver is no more interested to receive from the 316 group. 318 Beacons 319 Signals continuously emitted by the MAC layer, and received by 320 neighbors. These signals inform each node with the existing 321 neighbors. 323 Multicast Session 325 The period of communication setup between multicast group members. 327 Multicast Group 329 The subset of network nodes involved in a specific multicast 330 session. 332 3.3.2. Specification Language 334 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 335 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 336 document are to be interpreted as described in RFC 2119 [7]. 338 3.4. SRMP Header Format 340 The Source-Routing-based multicast protocol (SRMP) makes use of a 341 special header carrying control information that can be included in 342 any existing IP packet. This SRMP header in a packet contains a 343 small fixed-sized, 4-octet portion, followed by a sequence of zero 344 or more SRMP options carrying OPTIONAL information. The end of the 345 sequence of SRMP options in the SRMP header is implied by the total 346 length of the SRMP header. 348 The SRMP header is inserted in the packet following the packet's IP 349 header, before any following header such as a traditional transport 350 layer header (e.g., TCP or UDP). Specifically, the Protocol field 351 in the IP header is used to indicate that an SRMP header follows the 352 IP header, and the Next Header field in the SRMP header is used to 353 indicate the type of protocol header (such as a transport layer 354 header) following the SRMP header. 356 The total length of the SRMP header (and thus the combined length of 357 all SRMP options present) MUST be a multiple of 4 octets. This 358 requirement preserves the alignment of any following headers in the 359 packet. 361 3.4.1. Fixed Portion of SRMP Header 363 The fixed portion of the SRMP header is used to carry information 364 that MUST be present in any SRMP header. This fixed portion of the 365 SRMP header has the following format: 367 0 1 2 3 368 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 369 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 370 | Next Header | Reserved | Payload Length | 371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 372 . Options . 373 . . 374 . . 375 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 377 Next Header 379 8-bit selector. Identifies the type of header immediately 380 following the SRMP header. Uses the same values as the IPv4 381 Protocol field [8]. 383 Reserved 385 Sent as 0; ignored on reception. 387 Payload Length 389 The length of the SRMP header, excluding the 4-octet fixed 390 portion. The value of the Payload Length field defines the 391 total length of all options carried in the SRMP header. 393 Options 395 Variable-length field; the length of the Options field is 396 specified by the Payload Length field in the SRMP header. 397 Contains zero or more pieces of OPTIONAL information (SRMP 398 options), encoded in type-length-value (TLV) format (with the 399 exception of the Pad1 option, described in Section 3.4.6). 401 The placement of SRMP options following the fixed portion of 402 the SRMP header MAY be padded for alignment. However, due to 403 the typically limited available wireless bandwidth in ad hoc 404 networks, this padding is not REQUIRED, and receiving nodes 405 MUST NOT expect options within an SRMP header to be aligned. A 406 node inserting an SRMP header into a packet MUST set the Don't 407 Fragment (DF) bit in the packet's IP header. 409 The following types of SRMP options are defined in this 410 document for use within an SRMP header: 412 - Join Request Option (Section 3.4.2) 414 - Join Reply Option (Section 3.4.3) 416 - Multicast Route Error Option (Section 3.4.4) 418 - Leave Group Option (Section 3.4.5) 419 - Pad1 Option (Section 3.4.6) 421 - PadN Option (Section 3.4.7) 423 In this section, we use Join-request message to indicate Join 424 Request Packet, Join-reply message to indicate Join Reply Packet, 425 Leave Group message to indicate the packet used by a node to leave 426 the group, and Multicast-RERR message to indicate the delivered 427 packet by a node when a link failure is detected. 429 3.4.2. Join Request Option 431 The Join-request message is sent by a node to discover a route 432 towards a multicast group. The format of the Join Request SRMP 433 option is illustrated below, and contains the following fields : 435 0 1 2 3 436 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 437 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 438 | Option Type | Opt Data Len | Sequence Number | 439 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 440 | Multicast Group Address | 441 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 443 IP fields: 445 Source Address 447 MUST be set to the address of the node originating this packet. 448 Intermediate nodes that propagate the packet MUST NOT change 449 this field. 451 Destination Address 453 MUST be set to the IP limited broadcast address 454 (255.255.255.255) . 456 Join Request option fields: 458 Option Type 460 1 462 Opt Data Len 464 8-bit unsigned integer. The length of the option, in octets, 465 excluding the Option Type and Opt Data Len fields. 467 Sequence Number 469 A unique value generated by the initiator (original sender) of 470 the packet. Nodes generate a new Sequence Number for each Join- 471 request message targeted to a given multicast group. 472 Duplication in reception of Join-request messages is avoided. 473 Duplicated messages MUST then be discarded. When forwarding a 474 Join Request packet, this field MUST be copied from the 475 received copy of the Join Request packet being forwarded. 477 Multicast Group Address 479 The address of the multicast group this node is trying to join. 481 3.4.3. Join Reply Option 483 The Join Reply SRMP Option is encoded as follows : 485 0 1 2 3 486 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 487 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 488 | Option Type | Opt Data Len | Reserved | 489 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 490 | Destination ID | 491 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 492 | Route Record [1] | 493 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 494 | Route Record [2] | 495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 496 | ............................ | 497 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 498 | Route Record [n] | 499 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 501 IP fields: 503 Source Address 505 MUST be set to the address of the node originating this Join 506 Reply packet. In the case of a node sending a reply from its 507 Multicast Routing Cache (Section 3.7.3) this address will 508 differ from the address that was the target of the Route 509 discovery. 511 Destination Address 513 MUST be set to the IP address of the source node that 514 originated the Route Request being replied to. Copied from the 515 Source Address field of the Route Request. 517 Join Reply option fields: 519 Option Type 521 2 523 Opt Data Len 525 8-bit unsigned integer. The length of the option, in octets, 527 excluding the Option Type and Opt Data Len fields. 529 Destination ID 531 The IP address of the selected FG node that satisfies the 532 selection criteria. 534 Route Record [1..n] 536 The accumulated route during reply phase and FG nodes 537 selection. This route indicates a sequence of hops originating 538 at the receiver node specified in the Source Address field of 539 the IP header of the packet carrying the Join-reply message. 540 The number of addresses present in the Route Record [1..n] 541 field is indicated by the Opt Data Len field in the option 542 (n=(Opt Data Len -3) /4) 544 3.4.4. Multicast Route Error Option 546 0 1 2 3 547 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 548 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 549 | Option Type | Opt Data Len | Type | Reserved | 550 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 551 | Multicast Group Address | 552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 553 | Broken Link | 554 | | 555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 556 | Route to Sender [1] | 557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 558 | Route to Sender [2] | 559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 560 | ....................... | 561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 562 | Route to Sender [n] | 563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 The format of the Multicast-RERR message is illustrated above, and 566 contains the following fields : 568 IP fields: 570 Source Address 572 MUST be set to the address of the node originating this packet. 573 Intermediate nodes that retransmit the packet to forward the 574 packet MUST NOT change this field. 576 Destination Address 578 MUST be set to the IP limited broadcast address 579 (255.255.255.255) by the originator of the packet. 581 Multicast Route Error option fields: 583 Option Type 585 3 587 Opt Data Len 589 8-bit unsigned integer. The length of the option, in octets, 590 excluding the Option Type and Opt Data Len fields. 592 Type 594 This field indicates the type of the error encountered. 595 Currently, this field takes the value 0 if link failure occurs 596 between two FG nodes, and value 1 if failure occurs between an 597 FG node and a multicast receiver. Other values MAY be defined. 599 Multicast Group Address 601 Address of the multicast group. 603 Broken Link 605 The link that failed between the detector node [32-bit address] 606 and other neighbor node [32-bit address]. 608 Route to Sender 610 The route from the node detecting the failure back to the 611 original sender, this is formed by reversing the accumulated 612 route in the packet header without including the failed link 613 part. 615 3.4.5. Leave Group Option 617 The Leave Group option is encoded as follows: 619 0 1 2 3 620 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 621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 622 | Option Type | Opt Data Len | Reserved | 623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 624 | Multicast Group Address | 625 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 626 | Source ID | 627 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 628 | Forwarding Group Member Address | 629 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 631 Leave Group option fields: 633 Option Type 635 4 637 Opt Data Len 639 8-bit unsigned integer. The length of the option, in octets, 640 excluding the Option Type and Opt Data Len fields. 642 Multicast Group Address 644 The IP address of the multicast group that the node decided to 645 leave. 647 Source ID 649 The IP address of the node that will prune itself. 651 Forwarding Group Member Address 653 The IP Address of an FG node; this address is taken from the 654 neighbor table of the node. 656 3.4.6. Pad1 Option 658 The Pad1 SRMP option is encoded as follows: 660 +-+-+-+-+-+-+-+ 661 | Option Type | 662 +-+-+-+-+-+-+-+ 664 Pad1 option fields: 666 Option Type 668 5 670 A Pad1 option MAY be included in the Options field of a SRMP header 671 in order to align subsequent SRMP options, but such alignment is not 672 REQUIRED and MUST NOT be expected by nodes receiving packets 673 containing a SRMP header. 675 The total length of a SRMP header, indicated by the Payload Length 676 field in the SRMP header MUST be a multiple of 4 octets. When 677 building a SRMP header in a packet, sufficient Pad1 or PadN options 678 MUST be included in the Options field of the SRMP header to make the 679 total length a multiple of 4 octets. 681 If more than one consecutive octet of padding is being inserted in 682 the Options field of a SRMP header, the PadN option, described next, 683 SHOULD be used, rather than multiple Pad1 options. 685 Note that the format of the Pad1 option is a special case; it does 686 not have an Opt Data Len or Option Data field. 688 3.4.7. PadN Option 690 The PadN SRMP option is encoded as follows: 692 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----------------- 693 | Option Type | Opt Data Len | Option Data 694 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----------------- 696 PadN option fields: 698 Option Type 700 6 702 Opt Data Len 704 8-bit unsigned integer. Length of the option, in octets, 705 excluding the Option Type and Opt Data Len fields. 707 Option Data 709 A number of zero valued octets equal to the Opt Data Len. 711 A PadN option MAY be included in the Options field of a SRMP header 712 in order to align subsequent SRMP options, but such alignment is not 713 REQUIRED and MUST NOT be expected by nodes receiving packets 714 containing a SRMP header. 716 The total length of a SRMP header, indicated by the Payload Length 717 field in the SRMP header MUST be a multiple of 4 octets. When 718 building a SRMP header in a packet, sufficient Pad1 or PadN options 719 MUST be included in the Options field of the SRMP header to make the 720 total length a multiple of 4 octets. 722 3.5. Data Packet Format 724 0 1 2 3 725 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 726 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 727 | Source ID | 728 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 729 | Destination ID | 730 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 731 | Sequence Number | Reserved | 732 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 733 | Route Record [1] | 734 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 735 | Route Record [2] | 736 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 737 | ....................... | 738 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 739 | Route Record [n] | 740 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 741 | Data | 742 . . 743 . . 744 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 746 To illustrate the main fields used in the data transmission, we give 747 the format of the Data Packet without any details on header option 748 as shown above. This format contains the following fields : 750 Source ID 752 ID (IP address) of the source of transmission. 754 Destination ID 756 ID (IP address) of the multicast group receiving the Data 757 Packet. 759 Route Record 761 Sequence of hops to be followed from the source towards the 762 multicast receivers of the group (source route). This is the 763 reverse route accumulated during the reply phase and FG nodes 764 selection. 766 Sequence Number 767 A unique number used in identifying each transmitted data 768 packet. This identification detects duplication in reception of 769 packets at each node. 771 3.6. FG Selection Criteria 773 The Key advantage to efficient multicasting is the choice of FG 774 nodes and how to elect and maintain them. The size of FG nodes 775 SHOULD be as small as possible to reduce wireless channel overhead. 776 At the same time, the forwarding path from sender to receiver SHOULD 777 be available and stable to ensure reliable delivery and to eliminate 778 the high end-to-end delay caused by link failure. 780 For the choice of a path, an efficient selection criteria is used 781 considering four metrics: association stability, link signal 782 strength, battery life, and link availability. 784 3.6.1. Association Stability 786 This metric measures how long is the node stable with respect to 787 each neighbor, and has been first introduced in Associativity-based 788 Routing (ABR) unicast routing protocol [9]. It is calculated through 789 the use of a certain field stored in the node's stability table, 790 called associativity ticks, which is incremented each time the node 791 receives a beacon indicating neighbor's existence. In fact, a node 792 is stable with respect to a certain neighbor, if the accumulated 793 associativity ticks value corresponding to this neighbor reaches a 794 certain predefined threshold. 796 3.6.2. Link Signal Strength 798 This metric measures the signal strength between a node and each of 799 its neighbors indicating connectivity strength, it is used as a part 800 of Signal Strength Routing (SSR) unicast routing protocol [10]. Each 801 time a node receives a beacon from a neighbor indicating its 802 existence, it classifies the signal strength with respect to this 803 neighbor as weak or strong and stores it in a certain field in the 804 node's stability table called signal strength. This classification 805 is done by comparing the level of strength the beacon is received 806 with a certain predefined threshold. 808 3.6.3. Battery Life 810 This metric calculates continuously the current battery power of 811 each node, which is a decreasing function of time and processed 812 packets. SRMP uses this metric for power conservation of nodes, 813 where it selects paths with higher battery life indicating less 814 power consumed. This is calculated with the following formula: 816 Bp(t) = Bp(current) - [PCgp + PCrp + PCfp + K ] 817 Bp(t) : Battery power at time t 818 Bp(current) : Current battery power 819 [Initially, Bp(current) = Bp(0)] 820 PCgp : Total power consumed for each generated packet 821 (including processing and transmission) 822 PCrp : Total power consumed for each received packet 823 (including reception and processing) 824 PCfp : Total power consumed for each forwarded packet 825 (including reception, processing and transmission) 826 K : Power consumed by the node itself (equipment) 828 Each node calculates its Bp(t) periodically, by a predefined time 829 interval, following the above formula. This calculated Bp(t) value 830 is stored in a certain counter reserved for each node called battery 831 life counter. If the battery life of a node reaches a certain 832 predefined threshold, the node is considerded with high battery 833 life. 835 3.6.4. Link Availability Estimation 837 This metric uses the prediction-based link availability estimation 838 introduced in [11]. The basic idea of this estimation is to let a 839 node to first predict a continuous time period (Tp) that a currently 840 available link will last from time (t0) by assuming that both nodes 841 of the link are keeping their current movements (i.e. speed and 842 direction) unchanged. Then the probability L(Tp) that the link will 843 last to (t0+Tp) is estimated by considering possible changes in the 844 nodes' movements occurring between (t0) and (t0+Tp). 846 It is considered that each node's movement consists of a sequence of 847 random length intervals called mobility epochs [12]. Each epoch has 848 exponentially distributed duration of mean 1/lamda. A node moves 849 with constant speed and direction within an epoch, and speed and 850 direction varies randomly from epoch to epoch. 851 (-X) (-X) 852 L(Tp)=([(1-e )/2*lamda*Tp]+[lamda*Tp*e /2] 853 [X = 2*lamda*Tp] 855 The mean available time [L(Tp) x Tp] is used by each node as a 856 routing metric for link availability towards neighbors. We SHOULD 857 consider strong, intermediate, and weak mobility cases. 859 3.7. Data Structures 861 The identification of each received Join-request packet or data 862 packet is stored in the Multicast Message Duplication Table (Section 863 3.7.1) at each node. In addition, each node maintains Neighbor 864 Stability Table (Section 3.7.2) for continuous node-neighbor 865 information. The Multicast Routing Cache (Section 3.7.3) stores 866 different routes from each node to each multicast group, while the 867 Receiver Multicast Routing Table (Section 3.7.4) is maintained at 868 each receiver of each multicast group and stores the used route 869 between the receiver and the source. 871 3.7.1. Multicast Message Duplication Table 873 The Multicast Message Duplication Table is used to detect 874 duplication when receiving Join-request or data packets by a node. 876 +------------- +------------------- + ----------------------+ 877 | Source ID | Sequence Number | Type | 878 +--------------+--------------------+-----------------------+ 879 | | | | 880 | | | | 881 | | | | 882 +- ------------+--------------------+-----------------------+ 884 This table contains one entry for each newly received Join-request 885 or data packet, each entry includes the following fields: 887 - A Source ID to indicate the address of the original source of 888 each message received. 890 - A Sequence number to uniquely identify each message together with 891 the Source ID. When the node receives other messages, it checks 892 the table entries for an identification that matches the received 893 message's identification and discards the received message if 894 duplication is discovered. 896 - A Type field to indicate whether the message is a Join-request or 897 data packet. 899 FIFO or LRU scheme MAY be used to expire old entries in this table 900 preventing excessive growth in size. 902 3.7.2. Neighbor Stability Table 904 The Neighbor Stability Table is concerned with neighbors' stability 905 information for each node. 907 +-----------+-------------+------------+------------- -----+-------+ 908 |Neighbor ID|Node-Neighbor|Connectivity| Link Availability | Type | 909 | | Stability | Flag | Flag | | 910 +-----------+-------------+----- ------+--- ---------------+-------+ 911 | | | | | | 912 | | | | | | 913 | | | | | | 914 +-----------+-------------+------------+-------------------+-------+ 916 This table contains one entry for each neighbor, each entry includes 917 the following fields: 919 - A neighbor ID indicating the address of each neighbor of the node 921 - A node-neighbor stability field to indicate the degree of 922 association stability with this neighbor. 924 - A flag to indicate the degree of the connection's strength to 925 the neighbor. 927 - A flag to indicate if the link is available with the neighbor. 929 - A type field to indicate if the neighbor is a member or non member 930 of the group with respect to the node. 932 3.7.3. Multicast Routing Cache 934 The Multicast Routing Cache stores all possible routes between the 935 node and different multicast groups that this node is a member of 936 its mesh. 938 +----------+--------------------+ -----------------+--------+ 939 |Group ID | Route to multicast | Route Validation | Type | 940 | | Group | Timer | | 941 +----------+--------------------+------------------+--------+ 942 | | | | | 943 | | | | | 944 | | | | | 945 +-- -------+--- ----------------+---- ------------+--------+ 947 It contains one or more entries for each multicast group for which 948 it is a member, each entry includes the following fields: 950 - A Multicast Group ID to indicate each multicast group for which 951 the node is a member. An entry is first created for a multicast 952 group during the first Join-reply received by a node from a 953 multicast receiver, then other entries are created by the 954 reception of other Join-replies. 956 - A type field to indicate if the node is an FG node in the mesh or 957 a multicast source transmitting data towards the mesh. 959 - A route field to indicate the route to the multicast group 960 (receivers). Multiple entries stored for the same multicast group 961 indicates that there are more than one route towards this group. 963 - A timer "Route Validation Timer" to indicate route validation. 964 This timer stores the last time a route was stored, then it is 965 refreshed during the propagation of data packets through the node. 967 3.7.4. Receiver Multicast Routing Table 969 This Receiver Multicast Routing Table is maintained at each 970 multicast receiver, it stores created routes between the receiver 971 and each source for different multicast groups it belongs to. 973 +----------+-----------+-----------------+-----------------------+ 974 | Group ID | Source ID | Route to source | RouteValidation Timer | 975 +----------+---- ------+-----------------+-----------------------+ 976 | | | | | 977 | | | | | 978 | | | | | 979 +----------+-----------+-----------------+-----------------------+ 981 It contains an entry for each multicast source of the multicast 982 groups for which the receiver is a member, each entry includes the 983 following fields: 985 - A Multicast Group ID to indicate each multicast group for which 986 the receiver node is a member. 988 - A Source ID to indicate the source of transmission in the 989 multicast group. An entry is first created during the reception of 990 first data packet from the source. 992 - A route field to indicate the route towards the multicast group 993 (receivers). Multiple entries stored for the same multicast group 994 indicates routes to different sources in this group. 996 - A timer "Route Validation Timer" to indicate route validation. 997 This timer stores the last time a route was stored, then it is 998 refreshed by each data packet reception, that uses this route, 999 from the corresponding source. 1001 4. SRMP Operation 1003 Similar to the operation of on-demand routing protocols, a request 1004 phase and a reply-phase comprise the protocol. The request phase 1005 invokes a route discovery process to find routes to reach the 1006 multicast group. Different routes to the multicast group are setup 1007 during the reply phase through FG nodes selection and mesh 1008 construction. 1010 In the following sections, we are concerned with the operation that 1011 only takes place by SRMP protocol including request phase, reply 1012 phase, FG nodes selection, and data forwarding using the constructed 1013 mesh. We do not explain the process of setting the various fields 1014 within each originating packet or how the SRMP header is added to 1015 this packet. In addition, the sequence of steps used by the node 1016 receiving a packet with an SRMP header to process this packet is not 1017 outlined. 1019 4.1. Route Request Phase 1021 The request phase starts when a source node, which is not a group 1022 member and wishing to join the group, has data to send to the 1023 multicast group. At this time, it invokes route discovery procedure 1024 towards the multicast group through broadcasting a Join-request 1025 packet to neighbors. The Join-request packet contains the ID of the 1026 source node as its source address, and the multicast group ID as its 1027 destination address. 1029 A sequence number is set by the source node, and is used to detect 1030 packet duplication by each node receiving the Join-request through 1031 checking its multicast message duplication table. No field is used 1032 for accumulating source route as in the case of unicast operation in 1033 DSR, due to applying the source route concept in a modified manner. 1035 For example, suppose node S (multicast source)is attempting to 1036 discover a route to node R (multicast receiver). The Route 1037 Discovery initiated by node S in this example would proceed as 1038 follows: 1040 ^ ^ ^ ^ 1041 | | | | 1042 +------+ X +-------+ X +-------+ X +-------+ 1043 | S |------->| A |------>| B |------>| R | 1044 +------+ +---- --+ +-------+ +-------+ 1045 | | | | 1046 v v v v 1047 [X = "1,S-id,gp-id" ] 1049 4.2. Reply Phase and FG Node Selection 1051 The reply phase starts by a multicast receiver or an FG node member. 1052 Initially before mesh construction, the replying phase starts by 1053 multicast receivers only. A multicast receiver first checks for 1054 stability among its neighbors to select FG nodes. This is achieved 1055 by checking associativity ticks, signal strength, and link 1056 availability towards each neighbor, battery life is also checked 1057 considering consumed power needed to transmit to this neighbor. If 1058 these metrics satisfy predefined thresholds, neighbor is selected as 1059 an FG node and the receiver starts sending Join-reply message to it 1060 setting its type as member node in its corresponding neighbor table 1061 entry. Otherwise, the neighbor is not an FG node and would not 1062 receive Join-reply. In the case where there is no neighbor nodes 1063 satisfying the predefined thresholds for stability and battery life, 1064 the node with the best metrics among all the neighbors will be 1065 selected as FG node. 1067 Before broadcasting the Join-reply packet by the multicast receiver 1068 to the selected neighbors, the receiver stores the multicast group 1069 ID in the packets' Source ID field and the ID of the requesting node 1070 (source of Join-request) in the packets' Destination ID field. A 1071 source route from the multicast receiver (source of Join-reply) to 1072 the requesting node is also accumulated in the route record field 1073 during Join-reply propagation. 1075 A selected FG node, receiving a Join-reply, creates an entry in its 1076 multicast routing cache corresponding to the multicast group. In 1077 this entry, the node sets its state as FG node and copies the 1078 reversed accumulated route of the received Join-reply. It also 1079 stores in this entry the source ID of the Join-reply, and the time 1080 at which the Join-reply is received. After table entry creation, the 1081 FG node performs the previous steps to select FG nodes among its own 1082 neighbors. Then, it sends Join-reply packets to the selected FG 1083 nodes after appending its address to the route record field of each 1084 transmitted Join-reply. 1086 This process continues until reaching the source of request 1087 constructing a mesh of FG nodes connecting group members. At this 1088 time, the source receiving a Join-reply packet becomes a multicast 1089 source (group member) and creates an entry corresponding to the 1090 multicast group in its multicast routing cache. In this entry, it 1091 sets its state as Source node and copies the reversed accumulated 1092 route in the Join-reply. It also stores the source ID of the reply 1093 packet, and the time at which the Join-reply is received. Due to 1094 mesh structure, more than one Join-reply MAY be received by the 1095 source from the same multicast group and multiple routes are stored 1096 in the source multicast routing cache. 1098 For example, suppose node R (multicast receiver) is attempting to 1099 reply to a request from node S (multicast source). The reply phase 1100 initiated by R in this example would select D,B,A, and E as FG nodes 1101 and proceed as follows: 1103 ^ ^ ^ ^ thresholds 1104 | | | | not reached 1105 +-----+ +-----+ +------+ +-----+ +------+ 1106 | S |<-----| A |<--------| B |-------| C |-------| R | 1107 +-----+ +-----+ +------+ +-----+ +------+ 1108 ^thresholds thresholds ^ thresholds thresholds / 1109 \ reached reached \ reached reached / 1110 \ "R,D,B,A" "R,D,B" \ "R,D" "R" / 1111 \ +------+ +-----+ / 1112 -------- | E |<----------| D |<----------------- 1113 thresholds +------+thresholds +-----+ 1114 reached | reached | 1115 "R,D,E" v "R,D" v 1117 After mesh creation, an FG member node, having unexpired routes to a 1118 certain multicast group in its multicast routing cache, can reply to 1119 any Join-request for this group. At this case, the FG node 1120 broadcasts a Join-reply to the requesting source with the route 1121 record field taken as its ID together with the corresponding route 1122 to the multicast group stored in its multicast routing cache. 1124 4.3. Data Forwarding 1126 Data forwarding towards a certain multicast group starts by the 1127 multicast source. It selects one of the routes from its multicast 1128 routing cache leading to the REQUIRED multicast group. Route 1129 selection takes place according to certain criteria, such that the 1130 shortest path route in terms of number of hops is selected. In the 1131 case of more than one shortest path route, the most fresh route 1132 is selected. 1134 After route selection, the multicast source starts transmitting data 1135 to multicast group. Each data packet carries in its header the 1136 selected route, indicating the sequence of hops to be followed by 1137 the packet. It stores also the ID of the multicast source in its 1138 Source ID field and multicast group ID in its Destination ID field. 1139 A sequence number, generated by the source, for each transmitted 1140 data packet is also stored in the Sequence number field of the 1141 packet. 1143 For example, suppose node S (multicast source) is attempting to 1144 transmit data to node R (multicast receiver) using the mesh created 1145 of FG nodes D,B,A, and E. It selects the shortest route to the 1146 multicast receiver and proceeds in sending data carrying header as 1147 follows: 1149 ^ ^ ^ ^ 1150 | | | | 1151 +-----+ +-----+ +------+ +-----+ +------+ 1152 | S |------| A |---------| B |-------| C |-------| R | 1153 +-----+ +-----+ +------+ +-----+ +------+ 1154 \ \ ^ 1155 \ \ / 1156 \"S-id,gp-id,(E,D,R)" \ / 1157 \ 1 +------+ 2 +-----+ 3 / 1158 ------->| E |----------------->| D |----------> 1159 +------+"S-id,gp-id,(D,R)"+-----+"S-id,gp-id,(R)" 1160 | | 1161 v v 1163 FG nodes receiving the data packets will follow same route selection 1164 procedure and re-transmit the packet. This process continues until 1165 reaching all multicast receivers. To guarantee data transmission to 1166 all multicast receivers, the node duplicates transmission if the 1167 selected route leads directly to a multicast receiver. Duplication 1168 in transmission occurs by selecting one more route, following same 1169 previous criteria, and transmitting data to both routes. 1171 The sequence number together with the Source ID identify each data 1172 packet to prevent duplication in reception. When a node receives a 1173 new data packet, it stores the Source ID and sequence number of this 1174 packet in its message duplication table. During data packet 1175 propagation afterwards, the packet is checked in the nodes' message 1176 duplication tables and discarded if it was received before. 1178 A multicast receiver, receiving a data packet for the first time, 1179 creates an entry in its receiver multicast routing table towards the 1180 multicast source transmitting this packet. This entry stores the 1181 route to the multicast source by copying the reversed route stored 1182 in the packet header with adding the source ID at the beginning. 1183 Refreshment for this entry takes place through reception of another 1184 data packets from this source (Section 4.5.2). 1186 4.4. Member Node Transmission 1188 During a multicast session, a mesh member node MAY have data to send 1189 to the multicast group. This node starts by checking its multicast 1190 routing cache for a valid route to the multicast group, if one is 1191 found then it is used by the node to transmit its data. Otherwise, 1192 same previous route discovery process SHOULD occur indicating that a 1193 link failure has occurred causing no valid routes to be found. 1195 4.5. Maintenance Procedures 1196 Maintenance procedures refer to mechanisms within SRMP protocol by 1197 which the multicast mesh is refreshed, and link breaks are detected 1198 and repaired. They also support continuous node-neighbor information 1199 together with a pruning mechanism allowing any node to leave the 1200 group 1202 These procedures utilize three types of packets: MAC layer Beacons 1203 (Section 4.5.1), Multicast-RERR Message (Section 4.5.3), and Leave 1204 Group Message (Section 4.5.4). 1206 4.5.1. Neighbor Existence Mechanism 1208 SRMP introduces MAC layer beacons providing each node with neighbors 1209 existence information. By the time a node receives a neighbor 1210 beacon, it updates or creates the corresponding entry of this 1211 neighbor in its stability table. 1213 Entry update takes place through incrementing the associativity 1214 ticks field, and setting the signal strength field according to the 1215 level of strength the beacon is received. In addition, the node 1216 performs continuous prediction for link availability towards the 1217 neighbor through periodical estimation for [L(Tp) x Tp]. 1219 If no beacons are received by a node from a certain neighbor upto a 1220 certain period of time, the node indicates neighbor's movement and 1221 updates its stability table fields towards this neighbor. In this 1222 case, update takes place through setting the associativity ticks 1223 value to zero and signal strength and link availability fields to 1224 null until new information from this neighbor is received. 1226 4.5.2. Mesh Refreshment Mechanism 1228 One of the characteristics in SRMP is its simplicity in refreshing 1229 the multicast mesh without requiring extra control overhead. During 1230 each data packet propagation from the multicast source to the 1231 different multicast receivers, route refreshment for different paths 1232 on the mesh takes place. 1234 For each data packet transmitted by the multicast source, the source 1235 updates the timer of the corresponding route entry in the multicast 1236 routing cache. In addition, each FG node forwarding this data packet 1237 scans the route record field in the packet header, starting from its 1238 address, together with the Destination ID field and refreshes the 1239 Route Validation Timer of the corresponding route entry in the 1240 multicast routing cache. On the other hand, a multicast receiver 1241 scans the header of each data packet received for the Source ID, 1242 Route record, and Destination ID fields. This scanned information is 1243 used to refresh its timer of the corresponding entry to this source 1244 in the receiver multicast routing table. 1246 Each node performs continuous check on timers of the multicast 1247 routing cache and receiver multicast routing table (in the case of a 1248 receiver node), such that multicast group entries with expired 1249 timers are purged. 1251 4.5.3. Link Repair Mechanism 1253 SRMP reacts to link failure on-demand, such that it detects link 1254 failure during data transmission through the use of MAC layer 1255 support, it also follows two approaches in dealing with link 1256 failure. 1258 First, when link failure takes place between two FG nodes, SRMP 1259 follows the same proposed idea of DSR unicast protocol. In this 1260 case, the node detecting failure generates a Multicast-RERR packet 1261 of type 0 to the original source of data packet indicating the 1262 broken link. It also deletes from its cache any routes containing 1263 the broken link. Each node on the way receiving this packet updates 1264 its cache by deleting routes containing this broken link. 1266 For example, suppose node S (multicast source) is transmitting data 1267 to node R (multicast receiver) using the path E-D-R, and the link 1268 between E and D failed. Node E then attempts to send Multicast-RERR 1269 packet back to S informing of this failure. S then selects another 1270 path (S-A-B-D-R) to send its data and proceeds as follows: 1272 ^ ^ ^ ^ 1273 | | | | 1274 +-----+ +-----+ +------+ +-----+ +------+ 1275 | S |------| A |---------| B |-------| C |-------| R | 1276 | | ---> | | ---> | | | | | | 1277 +-----+ 4 +-----+ 5 +------+ +-----+ +------+ 1278 \^ \\ ^ 1279 \\ \\6 / 1280 \\ \v / 1281 \\ 3 +------+ +-----+ / 1282 \------- | E | | D | 7 / 1283 -------> | |-----x | |---------> 1284 1 +------+ 2 +-----+ 1285 | | 1286 v v 1288 Second, when link failure takes place between an FG node and a 1289 multicast receiver, the FG node detecting the failure simply deletes 1290 this receiver membership from its neighbor table. Each FG node 1291 checks its neighbor table periodically, such that if it discovers no 1292 more members for a certain multicast group it deletes routes to this 1293 group from its caches, then sends a Multicast-RERR of type 1 to all 1294 its member neighbors. The broken link field in this packet stores 1295 the link between the failure detector FG node and the multicast 1296 group, while the route to sender field is set to the member neighbor 1297 address. Each member neighbor, receiving this packet, inturn 1298 cleans its cache by deleting routes with this link. This process is 1299 repeated until all member nodes in the mesh are visited. 1301 For example, suppose node S (multicast source) is transmitting data 1302 to node R (multicast receiver) using the path E-D-R, and the link 1303 D-R failed. Then, D deletes R membership from its neighbor table. 1305 ^ ^ ^ ^ 1306 | | | | 1307 +-----+ +-----+ +------+ +-----+ +------+ 1308 | S |------| A |---------| B |-------| C |-------| R | 1309 +-----+ +-----+ +------+ +-----+ +------+ 1310 \ \ 1311 \ \ 1312 \ \ x 1313 \ 1 +------+ 2 +-----+ 3 / 1314 -------->| E |-------------->| D |----------> 1315 +------+ +-----+ 1316 | | 1317 v v 1319 4.5.4. Pruning Scheme 1321 SRMP provides an efficient pruning mechanism allowing a member node 1322 to leave the multicast session cancelling its membership to the 1323 multicast group. 1325 A multicast source wishing to leave a certain multicast group simply 1326 stops transmitting data to this group, and removes entries 1327 concerning this group from its multicast routing cache. This causes 1328 expiration and deletion of all routes stored in the FG nodes' 1329 caches, connecting this source to the multicast group, due to no 1330 refreshment. Similarly, the receiver multicast routing table entries 1331 towards this source will be expired and deleted. 1333 On the other hand, a multicast receiver wishing to leave a certain 1334 multicast group sends a Leave Group message to all its member 1335 neighbors, and deletes from its Receiver Multicast Routing Table all 1336 entries corresponding to this group. A member neighbor receiving the 1337 Leave Group message cancels in its turn this receiver membership 1338 from its Neighbor Stability Table by setting its type as non-member 1339 node. Each FG node checks its neighbor table periodically, such that 1340 if it discovers no more members for a certain multicast group it 1341 deletes routes to this group from its caches, then sends a 1342 Multicast-RERR of type 1 to all its member neighbors following 1343 previous procedure of link failure. 1345 Moreover, an FG node wishing to leave a certain multicast group can 1346 cancel its membership to this group and prune itself from the mesh. 1347 This node sends a Leave Group message to its member neighbors 1348 following the same procedure mentioned above. 1350 5. SRMP-ODMRP Comparison 1352 SRMP and ODMRP are mesh-based protocols using the concept of FG 1353 nodes to connect multicast group members. Although the latter does 1354 not guarantee optimal routes due to the use of the shortest path 1355 technique in its choice of FG nodes, the former applies a more 1356 effective criteria in the choice of FG nodes regarding paths 1357 stability and link availability based on future prediction of links 1358 state. Consequently, SRMP can guarantee reliable delivery together 1359 with less communication overhead and end-to-end delay. 1361 During data forwarding process, SRMP outperforms ODMRP through the 1362 use of source routing concept storing in the packet header the route 1363 to be followed, and allowing forwarding nodes to scan the routing 1364 information. ODMRP depends on next hop information to transmit a 1365 data packet. It also depends on periodical (Join-Query/Join-reply) 1366 to refresh route entries constituting the mesh. SRMP treats this 1367 case through the use of a more effective mechanism making use of 1368 data propagation and requiring no extra control overhead. 1370 In fact, the request/reply phase in SRMP has better impact on 1371 network performance, such that the request is sent once by a source 1372 wishing to join the group. Replies from multicast receivers are then 1373 sent back in form of small size reply packets targeted to the 1374 source. ODMRP follows a different approach by using periodical 1375 Query/reply during the period of data transmission requiring more 1376 control and communication overhead. In addition, it transmits a 1377 reply table with multiple reply entries to different sources 1378 causing reliability problem, such that the verification of the Join- 1379 reply delivery can not be handled by the MAC layer and special 1380 mechanisms are REQUIRED to overcome this problem. 1382 ODMRP has no special mechanism to handle link breakage, it only 1383 assumes that a receiver wanting to leave would stop sending replies. 1384 On the other hand, SRMP has an effective link breakage mechanism to 1385 discover unavailable routes and delete them from nodes caches giving 1386 more robustness to the protocol. It also uses a special pruning 1387 mechanism allowing mesh members to leave the group at any time. 1389 6. Constants 1391 Multicast Routing cache 1393 Route_Validation_Timeout 500 seconds 1395 Receiver Multicast Routing Table 1397 Route_Validation_Timeout 200 seconds 1399 Neighbor Stability Table 1401 Association Stability Threshold 50 ticks 1402 Signal Strength Threshold 70% (transmitted power) 1404 Link Availability Threshold 75 % 1406 Battery Life Threshold 50 % (initial power) 1408 Link Availability Prediction 1410 1/lamda 60 seconds 1412 Tp 50-120 seconds 1414 7. IANA considerations 1416 This document proposes the use of an SRMP header, which requires an 1417 IP Protocol number. 1419 8. QoS and Security Considerations 1421 This document does not specifically address QoS and/or security 1422 concerns. This document does assume that all nodes participating in 1423 the SRMP protocol do so in good faith and without malicious intent 1424 to corrupt the routing ability of the network. 1426 Concerning QoS, it can be taken into account by using a field in the 1427 packet header that allows the classification of data transmission. 1428 This field SHOULD be a combination of QoS criteria such as (delay 1429 and bit error rate) that specifies the QoS class accordingly. 1431 Acknowledgments 1433 We would like to thank our colleague in department INFRES 1434 (Informatique & R�seaux : Computer & Networks), Philippe Godlewski 1435 for his comments and gracious help on the work carried out in this 1436 document. 1438 References 1440 [1] D. Johnson, D. Maltz. "Dynamic source routing in ad hoc 1441 wireless networks", in Mobile Computing, T.Imielinski and H. 1442 korth,Eds. Norwell, MA: Kluwer, 1996. 1444 [2] C. Chiang, M. Gerla, and L. Zhang. "Forwarding Group Multicast 1445 Protocol (FGMP) for Multihop, Mobile Wireless Networks ", 1446 Baltzer Cluster Computing, Vol.1, no. 2, pp. 187-196, 1998. 1448 [3] K. Obraczka, G. Tsudik. "Multicast Routing Issues in Ad Hoc 1449 Networks", IEEE International Conference on Universal Personal 1450 Communication (ICUPC'98), October 1998. 1452 [4] IETF MANET working group. "On-Demand Multicast Routing Protocol 1453 (ODMRP) for Ad Hoc Networks", Internet draft , January 2000. 1456 [5] S. Lee, W. Su, and M. Gerla. "On-Demand Multicast Routing 1457 Protocol in Multihop Wireless Mobile Networks", ACM/Baltzer 1458 Mobile Networks and Applications, 2000. 1460 [6] A. B. McDonald and T. Znati, " A Path Availability Model for 1461 Wireless Ad Hoc Networks," Proceedings of IEEE WCNC, September 1462 1999. 1464 [7] Scott Bradner. Key words for use in RFCs to Indicate 1465 Requirement Levels. RFC 2119, March 1997. 1467 [8] Joyce K. Reynolds and Jon Postel. Assigned numbers. Internet 1468 Request For Comments RFC 1700, October 1994. 1470 [9] C-K. Toh, "Associativity-Based Routing for Ad Hoc Mobile 1471 Networks," Wireless personal Communication, vol. 4, no. 2, 1472 March 1997, pp. 1-36. 1474 [10] R. Dube and al., "Signal Stability based Adaptive Routing 1475 (SSR) for Ad Hoc Mobile Networks," IEEE personal 1476 communication, febraury 1997, pp. 36-45. 1478 [11] S. Jiang, D. He and J. Rao, "A Prediction-based Link 1479 availability Estimation for Mobile Ad Hoc Networks". In the 1480 proceedings of IEEE Infocom, April 2001. 1482 [12] H. dajiang, J. Shengming and R. Jianqiang, "A Link 1483 Availability Prediction Model for Wireless Ad Hoc Networks," 1484 Proceedings 2000 International Conference on Distributed 1485 Computing System workshop, Taipei, Taiwan, April 2000, p. D7- 1486 D11. 1488 Authors Addresses 1490 Questions about this document can be directed to: 1492 Houda Labiod 1493 ENST (Ecole Nationale Sup�rieure des T�l�communications), Paris 1494 INFRES (Informatique & R�seaux : Computer & Networks) Department 1495 46, rue Barrault-75634 Paris Cedexs 13 � France 1497 Phone : +1 01 45 81 74 36 1498 Fax : +1 01 45 81 31 19 1499 Email : labiod@enst.fr 1501 Hasnaa Moustafa 1502 ENST, (Ecole Nationale Sup�rieure des T�l�communications) Paris 1503 INFRES (Informatique & R�seaux : Computer & Networks) Department 1504 46, rue Barrault-75634 Paris Cedexs 13 � France 1506 Phone : +1 01 45 81 80 86 1507 Fax : +1 01 45 81 31 19 1508 Email : moustafa@enst.fr