INTERNET-DRAFT Houda LABIOD 6 November 2001 ENST, Paris Hasnaa MOUSTAFA ENST, Paris The Source Routing-based Multicast Protocol for Mobile Ad Hoc Networks (SRMP) Status of This Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at: http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at: http://www.ietf.org/shadow.html. This document is an individual submission for consideration by the Manet Working Group of the Internet Engineering Task Force (IETF). Comments on this draft may be sent directly to authors and to the mailing list. Distribution of this memo is unlimited. Labiod and Moustafa Expires 6 June 2002 [Page i] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Abstract The Source Routing-based Multicast Protocol (SRMP) is designed to provide multicast functionality in mobile ad hoc networks. It applies the source routing mechanism defined by the Dynamic Source Routing (DSR) [1] in a modified manner decreasing the size of the packet header. SRMP obtains multicast routes on-demand through constructing a mesh (an arbitrary subnet) to connect group members providing robustness against mobility. This protocol minimizes the flooding scope using the Forwarding Group (FG) nodes concept [2]. The criteria used for selecting FG nodes allows the choice of stable paths with higher battery life. This protocol operates in a loop-free manner, minimizing channel overhead and making efficient use of network resources. The mesh-based approach avoids drawbacks of multicast trees, where multicast packets can be delivered to the destination in case of frequent node movements and channel fading. SRMP outperforms other multicast protocols by providing available paths based on future prediction for links state. These paths also guarantee nodes stability with respect to their neighbors, strong connectivity between nodes, and higher battery life. Labiod and Moustafa Expires 6 June 2002 [Page ii] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Contents Status of this memo i Abstract ii 1. Introduction 1 2. Overview of DSR 1 3. SRMP 2 3.1. Protocol Overview ........................................2 3.2. Assumptions ..............................................3 3.3. Used Terminology .........................................4 3.3.1. SRMP Terminology ...............................4 3.3.2. Specification Language .........................5 3.4. SRMP Header Format .......................................5 3.4.1. Fixed Portion of SRMP Header ...................5 3.4.2. Join Request Option ............................7 3.4.3. Join Reply Option ..............................8 3.4.4. Multicast Route Error Option ...................9 3.4.5. Leave Group Option ............................10 3.4.6. Pad1 Option ...................................11 3.4.7. PadN Option ...................................12 3.5. Data Packet Format ......................................12 3.6. FG Selection Criteria ...................................13 3.6.1. Association Stability .........................14 3.6.2. Link Signal Strength ..........................14 3.6.3. Battery Life ..................................14 3.6.4. Link Availability Estimation ..................15 3.7. Data Structures .........................................15 3.7.1. Multicast Message Duplication Table ...........15 3.7.2. Neighbor Stability Table ......................16 3.7.3. Multicast Routing Cache .......................16 3.7.4. Receiver Multicast Routing Table ..............17 4. SRMP Operation 18 4.1. Route Request Phase .....................................18 4.2. Reply Phase and FG Node Selection .......................19 4.3. Data Forwarding .........................................20 4.4. Member Node Transmission ................................21 4.5. Maintenance Procedures ..................................21 4.5.1. Neighbor Existence Mechanism ..................22 4.5.2. Mesh Refreshment Mechanism ....................22 4.5.3. Link Repair Mechanism .........................23 4.5.4. Pruning Scheme ................................24 5. SRMP-ODRMP Comparison 25 6. Constants 25 Labiod and Moustafa Expires 6 June 2002 [Page iii] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 7. IANA Considerations 26 8. QoS and Security Considerations 26 Acknowledgments 27 References 28 Authors Addresses 29 Labiod and Moustafa Expires 6 June 2002 [Page iv] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 1. Introduction Multipoint communication has emerged as one of the most important research areas in the field of network. Multicast plays an important role in ad hoc networks, where network hosts work in groups to carry out a given task. It is also very useful in one-to-many data dissemination in critical situations such as disaster recovery or in the battlefield. In fact, designing multicast routing protocols is a complex problem. Group membership MAY change, and network topology can also evolve (links and nodes can fail). The technical challenge lies in constructing protocols that minimize storage and network load, providing basic support for reliable transmission, and designing optimal routes [3]. There are few multicast routing protocols that have been recently proposed for ad hoc networks, this document describes the Source Routing-based Multicast Protocol (SRMP). SRMP is an on-demand multicast routing protocol constructing a mesh (an arbitrary subnet) to connect group members thus providing robustness against mobility. Multicast routes and group membership are obtained on-demand to use efficiently network resources, avoiding channel overhead and improving scalability. The mechanism of source routing proposed in DSR unicast protocol has been modified to be applied in SRMP. SRMP uses the concept of "forwarding group" to build a forwarding mesh for each multicast group. By maintaining and using a mesh instead of a tree, the drawbacks of multicast trees (e.g., intermittent connectivity, traffic concentration, frequent trees reconfiguration, non-shortest path in a shared tree) are avoided. Some relevant enhancements are introduced in SRMP to overcome some drawbacks of other protocols as ODMRP [4,5]. A selection criteria is used to provide stable paths based on links availability according to future prediction of link states, and higher battery life paths tending to power conserving. SRMP applies also an efficient mechanism to maintain group members making use of data propagation and requiring no extra control overhead. Moreover, a pruning mechanism is used to allow a node to leave the group, thus preventing stale routes to be found at the forwarding nodes. 2. Overview of DSR DSR is an on-demand routing protocol which allows nodes to dynamically discover a source route across multiple networks hops to any destination in the ad hoc network [1]. Each data packet follows a source route stored in its header giving the address of each node through which the packet SHOULD be forwarded in order to reach its final destination. Mobile nodes are REQUIRED to maintain route caches containing the learned source routes. Labiod and Moustafa Expires 6 June 2002 [Page 1] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 DSR employs two mechanisms to enable unicast routing: Route Discovery and Route Maintenance. When a node wishes to communicate with another node, which has no stored route for it in its cache, it invokes the Route Discovery procedure flooding a Route Request (RREQ) packet through the network in search of a route to the destination. Upon receiving a RREQ by the destination or an intermediate node with routing information about destination, it contains a route record yielding the sequence of hops taken. Then, a Route Reply (RREP) to the requestor node is generated following the reverse path. The Route Maintenance mechanism monitors the status of source route in use, detects link failures and repairs routes. This is accomplished through the use of Route Error (RERR) packets and acknowledgements. When the data link layer encounters a fatal transmitting problem at a node, RERR packets are generated to the original sender of the packet encountering the error. A node receiving a RERR packet removes the hop in error from its cache and all routes containing the hop are truncated. Acknowledgements are also used to verify the correct operation of the protocol. 3. SRMP This section gives an overview on SRMP, defining some terminology used in designing this protocol and stating the criteria used to select FG nodes. Data structures used for building SRMP together with the format of control messages are also described in this section. 3.1. Protocol Overview Source Routing-based Multicast Protocol (SRMP) is an on-demand multicast routing protocol. One distinguishing feature of SRMP is the on-demand establishment of a mesh structure to connect group members, providing redundant paths between members. By building a mesh, packets can be delivered to multicast receivers in the case of node movements and topology changes. Routers are allowed to accept unique packets coming from any neighbor in the mesh. In addition, drawbacks of multicast trees can be avoided (ex., intermittent connectivity, traffic concentration, frequent tree reconfiguration, non-shortest path in a shared tree). SRMP is based on the idea of source routing proposed in DSR unicast protocol. This is applied in a modified manner reducing the flooding scope for packets carrying the source route, such that source route accumulates in the reply packet during the reply phase instead of accumulating in the request packet during request phase of DSR. Source route accumulation takes place during FG nodes selection starting from the receiver side, and constructing a mesh towards the source. Applying the source route concept allows loop Labiod and Moustafa Expires 6 June 2002 [Page 2] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 free in packets routing, and avoids the need for up-to-date routing information in the intermediate nodes. Source routing also allows nodes that are forwarding the packets to cache the routing information for their own future use. To establish a mesh for each multicast group, SRMP uses the concept of Forwarding Group (FG) nodes. This scheme can be viewed as a "limited scope" flooding within a properly selected forwarding set of nodes. By the use of FG nodes concept and the application of on- demand routing technique, SRMP reduces channel and storage overhead thus improving performance and scalability. Operation starts when a node wants to transmit to the multicast group and has no route to this group. A route discovery procedure is then invoked through broadcasting Join-request message searching for the multicast group members. A multicast receiver, receiving a Join-request, starts selecting FG nodes from its neighbors and sends Join-reply messages to them. This process of selection and Join- reply transmission is repeated by each FG node until reaching the source. Then, a mesh is constructed between the source and the multicast receivers consisting of FG nodes to forward the multicast data. Finally, the source selects one of the routes of the mesh to transmit its data. For example, suppose a network consisting of source node S and two multicast receivers R1 and R2. The Join-reply packets initiated in this example selects nodes A and C as FG nodes (mesh members) and constructs the mesh {A,C} to connect the source S with the multicast receivers R1 and R2. +------+ +------+ +------+ | S |-----| A |-----| R1 | | |-----| |-----| | +------+ +------+ +------+ | || || | || || | || || +------+ +------+ +------+ | B |-----| C |-----| R2 | | | | |-----| | +------+ +------+ +------+ 3.2. Assumptions We assume that all nodes wishing to communicate with other nodes within the ad hoc network are willing to participate fully in the protocols of the network. In particular, each node participating in the network SHOULD also be willing to forward packets for other nodes in the network. We refer to the minimum number of hops necessary for a packet to Labiod and Moustafa Expires 6 June 2002 [Page 3] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 reach from any node located at one extreme edge of the network to another node located at the opposite extreme, as the diameter of the network. We assume that the diameter of an ad hoc network will be small (e.g., perhaps 5 or 10 hops), but MAY often be greater than 1. Packets MAY be lost or corrupted in transmission on the wireless network. A node receiving a corrupted packet can detect the error and discard the packet. 3.3. Used Terminology 3.3.1. SRMP Terminology This section defines some terminology used in SRMP. Source Routing Each data packet carries in its header the set of nodes through which this packet MUST be transmitted. Mesh A multicast mesh is a subset of the network topology that provides at least one path from each source to each receiver of the multicast group. Forwarding Group The forwarding group is a set of nodes responsible for forwarding multicast data between any member pairs. Available Paths By "a path being available", we mean that the radio quality of each link in the path satisfies the minimal requirements for successful communication [6]. Stale Routes Invalid routes between the node and different destinations that are still stored in the node's routing table. Pruning When a multicast member wants to leave the group. This MAY take place when a multicast source has finished its transmission, or when a multicast receiver is no more interested to receive from the group. Beacons Labiod and Moustafa Expires 6 June 2002 [Page 4] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Signals continuously emitted by the MAC layer, and received by neighbors. These signals inform each node with the existing neighbors. Multicast Session The period of communication setup between multicast group members. Multicast Group The subset of network nodes involved in a specific multicast session. 3.3.2. Specification Language The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [7]. 3.4. SRMP Header Format The Source-Routing-based multicast protocol (SRMP) makes use of a special header carrying control information that can be included in any existing IP packet. This SRMP header in a packet contains a small fixed-sized, 4-octet portion, followed by a sequence of zero or more SRMP options carrying OPTIONAL information. The end of the sequence of SRMP options in the SRMP header is implied by the total length of the SRMP header. The SRMP header is inserted in the packet following the packet's IP header, before any following header such as a traditional transport layer header (e.g., TCP or UDP). Specifically, the Protocol field in the IP header is used to indicate that an SRMP header follows the IP header, and the Next Header field in the SRMP header is used to indicate the type of protocol header (such as a transport layer header) following the SRMP header. The total length of the SRMP header (and thus the combined length of all SRMP options present) MUST be a multiple of 4 octets. This requirement preserves the alignment of any following headers in the packet. 3.4.1. Fixed Portion of SRMP Header The fixed portion of the SRMP header is used to carry information that MUST be present in any SRMP header. This fixed portion of the SRMP header has the following format: Labiod and Moustafa Expires 6 June 2002 [Page 5] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Header | Reserved | Payload Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . Options . . . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Next Header 8-bit selector. Identifies the type of header immediately following the SRMP header. Uses the same values as the IPv4 Protocol field [8]. Reserved Sent as 0; ignored on reception. Payload Length The length of the SRMP header, excluding the 4-octet fixed portion. The value of the Payload Length field defines the total length of all options carried in the SRMP header. Options Variable-length field; the length of the Options field is specified by the Payload Length field in the SRMP header. Contains zero or more pieces of OPTIONAL information (SRMP options), encoded in type-length-value (TLV) format (with the exception of the Pad1 option, described in Section 3.4.6). The placement of SRMP options following the fixed portion of the SRMP header MAY be padded for alignment. However, due to the typically limited available wireless bandwidth in ad hoc networks, this padding is not REQUIRED, and receiving nodes MUST NOT expect options within an SRMP header to be aligned. A node inserting an SRMP header into a packet MUST set the Don't Fragment (DF) bit in the packet's IP header. The following types of SRMP options are defined in this document for use within an SRMP header: - Join Request Option (Section 3.4.2) - Join Reply Option (Section 3.4.3) - Multicast Route Error Option (Section 3.4.4) - Leave Group Option (Section 3.4.5) Labiod and Moustafa Expires 6 June 2002 [Page 6] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 - Pad1 Option (Section 3.4.6) - PadN Option (Section 3.4.7) In this section, we use Join-request message to indicate Join Request Packet, Join-reply message to indicate Join Reply Packet, Leave Group message to indicate the packet used by a node to leave the group, and Multicast-RERR message to indicate the delivered packet by a node when a link failure is detected. 3.4.2. Join Request Option The Join-request message is sent by a node to discover a route towards a multicast group. The format of the Join Request SRMP option is illustrated below, and contains the following fields : 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Opt Data Len | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address MUST be set to the address of the node originating this packet. Intermediate nodes that propagate the packet MUST NOT change this field. Destination Address MUST be set to the IP limited broadcast address (255.255.255.255) . Join Request option fields: Option Type 1 Opt Data Len 8-bit unsigned integer. The length of the option, in octets, excluding the Option Type and Opt Data Len fields. Sequence Number A unique value generated by the initiator (original sender) of Labiod and Moustafa Expires 6 June 2002 [Page 7] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 the packet. Nodes generate a new Sequence Number for each Join- request message targeted to a given multicast group. Duplication in reception of Join-request messages is avoided. Duplicated messages MUST then be discarded. When forwarding a Join Request packet, this field MUST be copied from the received copy of the Join Request packet being forwarded. Multicast Group Address The address of the multicast group this node is trying to join. 3.4.3. Join Reply Option The Join Reply SRMP Option is encoded as follows : 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Opt Data Len | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route Record [1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route Record [2] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ............................ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route Record [n] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ IP fields: Source Address MUST be set to the address of the node originating this Join Reply packet. In the case of a node sending a reply from its Multicast Routing Cache (Section 3.7.3) this address will differ from the address that was the target of the Route discovery. Destination Address MUST be set to the IP address of the source node that originated the Route Request being replied to. Copied from the Source Address field of the Route Request. Join Reply option fields: Option Type 2 Labiod and Moustafa Expires 6 June 2002 [Page 8] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Opt Data Len 8-bit unsigned integer. The length of the option, in octets, excluding the Option Type and Opt Data Len fields. Destination ID The IP address of the selected FG node that satisfies the selection criteria. Route Record [1..n] The accumulated route during reply phase and FG nodes selection. This route indicates a sequence of hops originating at the receiver node specified in the Source Address field of the IP header of the packet carrying the Join-reply message. The number of addresses present in the Route Record [1..n] field is indicated by the Opt Data Len field in the option (n=(Opt Data Len -3) /4) 3.4.4. Multicast Route Error Option 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Opt Data Len | Type | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Broken Link | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route to Sender [1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route to Sender [2] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ....................... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route to Sender [n] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Multicast-RERR message is illustrated above, and contains the following fields : IP fields: Source Address MUST be set to the address of the node originating this packet. Intermediate nodes that retransmit the packet to forward the packet MUST NOT change this field. Labiod and Moustafa Expires 6 June 2002 [Page 9] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Destination Address MUST be set to the IP limited broadcast address (255.255.255.255) by the originator of the packet. Multicast Route Error option fields: Option Type 3 Opt Data Len 8-bit unsigned integer. The length of the option, in octets, excluding the Option Type and Opt Data Len fields. Type This field indicates the type of the error encountered. Currently, this field takes the value 0 if link failure occurs between two FG nodes, and value 1 if failure occurs between an FG node and a multicast receiver. Other values MAY be defined. Multicast Group Address Address of the multicast group. Broken Link The link that failed between the detector node [32-bit address] and other neighbor node [32-bit address]. Route to Sender The route from the node detecting the failure back to the original sender, this is formed by reversing the accumulated route in the packet header without including the failed link part. 3.4.5. Leave Group Option The Leave Group option is encoded as follows: 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Opt Data Len | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multicast Group Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Labiod and Moustafa Expires 6 June 2002 [Page 10] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 | Forwarding Group Member Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Leave Group option fields: Option Type 4 Opt Data Len 8-bit unsigned integer. The length of the option, in octets, excluding the Option Type and Opt Data Len fields. Multicast Group Address The IP address of the multicast group that the node decided to leave. Source ID The IP address of the node that will prune itself. Forwarding Group Member Address The IP Address of an FG node; this address is taken from the neighbor table of the node. 3.4.6. Pad1 Option The Pad1 SRMP option is encoded as follows: +-+-+-+-+-+-+-+ | Option Type | +-+-+-+-+-+-+-+ Pad1 option fields: Option Type 5 A Pad1 option MAY be included in the Options field of a SRMP header in order to align subsequent SRMP options, but such alignment is not REQUIRED and MUST NOT be expected by nodes receiving packets containing a SRMP header. The total length of a SRMP header, indicated by the Payload Length field in the SRMP header MUST be a multiple of 4 octets. When building a SRMP header in a packet, sufficient Pad1 or PadN options MUST be included in the Options field of the SRMP header to make the total length a multiple of 4 octets. Labiod and Moustafa Expires 6 June 2002 [Page 11] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 If more than one consecutive octet of padding is being inserted in the Options field of a SRMP header, the PadN option, described next, SHOULD be used, rather than multiple Pad1 options. Note that the format of the Pad1 option is a special case; it does not have an Opt Data Len or Option Data field. 3.4.7. PadN Option The PadN SRMP option is encoded as follows: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----------------- | Option Type | Opt Data Len | Option Data +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----------------- PadN option fields: Option Type 6 Opt Data Len 8-bit unsigned integer. Length of the option, in octets, excluding the Option Type and Opt Data Len fields. Option Data A number of zero valued octets equal to the Opt Data Len. A PadN option MAY be included in the Options field of a SRMP header in order to align subsequent SRMP options, but such alignment is not REQUIRED and MUST NOT be expected by nodes receiving packets containing a SRMP header. The total length of a SRMP header, indicated by the Payload Length field in the SRMP header MUST be a multiple of 4 octets. When building a SRMP header in a packet, sufficient Pad1 or PadN options MUST be included in the Options field of the SRMP header to make the total length a multiple of 4 octets. 3.5. Data Packet Format 0 1 2 3 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | Reserved | Labiod and Moustafa Expires 6 June 2002 [Page 12] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route Record [1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route Record [2] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ....................... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Route Record [n] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Data | . . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ To illustrate the main fields used in the data transmission, we give the format of the Data Packet without any details on header option as shown above. This format contains the following fields : Source ID ID (IP address) of the source of transmission. Destination ID ID (IP address) of the multicast group receiving the Data Packet. Route Record Sequence of hops to be followed from the source towards the multicast receivers of the group (source route). This is the reverse route accumulated during the reply phase and FG nodes selection. Sequence Number A unique number used in identifying each transmitted data packet. This identification detects duplication in reception of packets at each node. 3.6. FG Selection Criteria The Key advantage to efficient multicasting is the choice of FG nodes and how to elect and maintain them. The size of FG nodes SHOULD be as small as possible to reduce wireless channel overhead. At the same time, the forwarding path from sender to receiver SHOULD be available and stable to ensure reliable delivery and to eliminate the high end-to-end delay caused by link failure. For the choice of a path, an efficient selection criteria is used considering four metrics: association stability, link signal strength, battery life, and link availability. Labiod and Moustafa Expires 6 June 2002 [Page 13] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 3.6.1. Association Stability This metric measures how long is the node stable with respect to each neighbor, and has been first introduced in Associativity-based Routing (ABR) unicast routing protocol [9]. It is calculated through the use of a certain field stored in the node's stability table, called associativity ticks, which is incremented each time the node receives a beacon indicating neighbor's existence. In fact, a node is stable with respect to a certain neighbor, if the accumulated associativity ticks value corresponding to this neighbor reaches a certain predefined threshold. 3.6.2. Link Signal Strength This metric measures the signal strength between a node and each of its neighbors indicating connectivity strength, it is used as a part of Signal Strength Routing (SSR) unicast routing protocol [10]. Each time a node receives a beacon from a neighbor indicating its existence, it classifies the signal strength with respect to this neighbor as weak or strong and stores it in a certain field in the node's stability table called signal strength. This classification is done by comparing the level of strength the beacon is received with a certain predefined threshold. 3.6.3. Battery Life This metric calculates continuously the current battery power of each node, which is a decreasing function of time and processed packets. SRMP uses this metric for power conservation of nodes, where it selects paths with higher battery life indicating less power consumed. This is calculated with the following formula: Bp(t) = Bp(current) - [PCgp + PCrp + PCfp + K ] Bp(t) : Battery power at time t Bp(current) : Current battery power [Initially, Bp(current) = Bp(0)] PCgp : Total power consumed for each generated packet (including processing and transmission) PCrp : Total power consumed for each received packet (including reception and processing) PCfp : Total power consumed for each forwarded packet (including reception, processing and transmission) K : Power consumed by the node itself (equipment) Each node calculates its Bp(t) periodically, by a predefined time interval, following the above formula. This calculated Bp(t) value is stored in a certain counter reserved for each node called battery life counter. If the battery life of a node reaches a certain predefined threshold, the node is considerded with high battery life. Labiod and Moustafa Expires 6 June 2002 [Page 14] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 3.6.4. Link Availability Estimation This metric uses the prediction-based link availability estimation introduced in [11]. The basic idea of this estimation is to let a node to first predict a continuous time period (Tp) that a currently available link will last from time (t0) by assuming that both nodes of the link are keeping their current movements (i.e. speed and direction) unchanged. Then the probability L(Tp) that the link will last to (t0+Tp) is estimated by considering possible changes in the nodes' movements occurring between (t0) and (t0+Tp). It is considered that each node's movement consists of a sequence of random length intervals called mobility epochs [12]. Each epoch has exponentially distributed duration of mean 1/lamda. A node moves with constant speed and direction within an epoch, and speed and direction varies randomly from epoch to epoch. (-X) (-X) L(Tp)=([(1-e )/2*lamda*Tp]+[lamda*Tp*e /2] [X = 2*lamda*Tp] The mean available time [L(Tp) x Tp] is used by each node as a routing metric for link availability towards neighbors. We SHOULD consider strong, intermediate, and weak mobility cases. 3.7. Data Structures The identification of each received Join-request packet or data packet is stored in the Multicast Message Duplication Table (Section 3.7.1) at each node. In addition, each node maintains Neighbor Stability Table (Section 3.7.2) for continuous node-neighbor information. The Multicast Routing Cache (Section 3.7.3) stores different routes from each node to each multicast group, while the Receiver Multicast Routing Table (Section 3.7.4) is maintained at each receiver of each multicast group and stores the used route between the receiver and the source. 3.7.1. Multicast Message Duplication Table The Multicast Message Duplication Table is used to detect duplication when receiving Join-request or data packets by a node. +------------- +------------------- + ----------------------+ | Source ID | Sequence Number | Type | +--------------+--------------------+-----------------------+ | | | | | | | | | | | | +- ------------+--------------------+-----------------------+ This table contains one entry for each newly received Join-request or data packet, each entry includes the following fields: Labiod and Moustafa Expires 6 June 2002 [Page 15] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 - A Source ID to indicate the address of the original source of each message received. - A Sequence number to uniquely identify each message together with the Source ID. When the node receives other messages, it checks the table entries for an identification that matches the received message's identification and discards the received message if duplication is discovered. - A Type field to indicate whether the message is a Join-request or data packet. FIFO or LRU scheme MAY be used to expire old entries in this table preventing excessive growth in size. 3.7.2. Neighbor Stability Table The Neighbor Stability Table is concerned with neighbors' stability information for each node. +-----------+-------------+------------+------------- -----+-------+ |Neighbor ID|Node-Neighbor|Connectivity| Link Availability | Type | | | Stability | Flag | Flag | | +-----------+-------------+----- ------+--- ---------------+-------+ | | | | | | | | | | | | | | | | | | +-----------+-------------+------------+-------------------+-------+ This table contains one entry for each neighbor, each entry includes the following fields: - A neighbor ID indicating the address of each neighbor of the node - A node-neighbor stability field to indicate the degree of association stability with this neighbor. - A flag to indicate the degree of the connection's strength to the neighbor. - A flag to indicate if the link is available with the neighbor. - A type field to indicate if the neighbor is a member or non member of the group with respect to the node. 3.7.3. Multicast Routing Cache The Multicast Routing Cache stores all possible routes between the node and different multicast groups that this node is a member of its mesh. Labiod and Moustafa Expires 6 June 2002 [Page 16] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 +----------+--------------------+ -----------------+--------+ |Group ID | Route to multicast | Route Validation | Type | | | Group | Timer | | +----------+--------------------+------------------+--------+ | | | | | | | | | | | | | | | +-- -------+--- ----------------+---- ------------+--------+ It contains one or more entries for each multicast group for which it is a member, each entry includes the following fields: - A Multicast Group ID to indicate each multicast group for which the node is a member. An entry is first created for a multicast group during the first Join-reply received by a node from a multicast receiver, then other entries are created by the reception of other Join-replies. - A type field to indicate if the node is an FG node in the mesh or a multicast source transmitting data towards the mesh. - A route field to indicate the route to the multicast group (receivers). Multiple entries stored for the same multicast group indicates that there are more than one route towards this group. - A timer "Route Validation Timer" to indicate route validation. This timer stores the last time a route was stored, then it is refreshed during the propagation of data packets through the node. 3.7.4. Receiver Multicast Routing Table This Receiver Multicast Routing Table is maintained at each multicast receiver, it stores created routes between the receiver and each source for different multicast groups it belongs to. +----------+-----------+-----------------+-----------------------+ | Group ID | Source ID | Route to source | RouteValidation Timer | +----------+---- ------+-----------------+-----------------------+ | | | | | | | | | | | | | | | +----------+-----------+-----------------+-----------------------+ It contains an entry for each multicast source of the multicast groups for which the receiver is a member, each entry includes the following fields: - A Multicast Group ID to indicate each multicast group for which the receiver node is a member. - A Source ID to indicate the source of transmission in the multicast group. An entry is first created during the reception of Labiod and Moustafa Expires 6 June 2002 [Page 17] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 first data packet from the source. - A route field to indicate the route towards the multicast group (receivers). Multiple entries stored for the same multicast group indicates routes to different sources in this group. - A timer "Route Validation Timer" to indicate route validation. This timer stores the last time a route was stored, then it is refreshed by each data packet reception, that uses this route, from the corresponding source. 4. SRMP Operation Similar to the operation of on-demand routing protocols, a request phase and a reply-phase comprise the protocol. The request phase invokes a route discovery process to find routes to reach the multicast group. Different routes to the multicast group are setup during the reply phase through FG nodes selection and mesh construction. In the following sections, we are concerned with the operation that only takes place by SRMP protocol including request phase, reply phase, FG nodes selection, and data forwarding using the constructed mesh. We do not explain the process of setting the various fields within each originating packet or how the SRMP header is added to this packet. In addition, the sequence of steps used by the node receiving a packet with an SRMP header to process this packet is not outlined. 4.1. Route Request Phase The request phase starts when a source node, which is not a group member and wishing to join the group, has data to send to the multicast group. At this time, it invokes route discovery procedure towards the multicast group through broadcasting a Join-request packet to neighbors. The Join-request packet contains the ID of the source node as its source address, and the multicast group ID as its destination address. A sequence number is set by the source node, and is used to detect packet duplication by each node receiving the Join-request through checking its multicast message duplication table. No field is used for accumulating source route as in the case of unicast operation in DSR, due to applying the source route concept in a modified manner. For example, suppose node S (multicast source)is attempting to discover a route to node R (multicast receiver). The Route Discovery initiated by node S in this example would proceed as follows: Labiod and Moustafa Expires 6 June 2002 [Page 18] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 ^ ^ ^ ^ | | | | +------+ X +-------+ X +-------+ X +-------+ | S |------->| A |------>| B |------>| R | +------+ +---- --+ +-------+ +-------+ | | | | v v v v [X = "1,S-id,gp-id" ] 4.2. Reply Phase and FG Node Selection The reply phase starts by a multicast receiver or an FG node member. Initially before mesh construction, the replying phase starts by multicast receivers only. A multicast receiver first checks for stability among its neighbors to select FG nodes. This is achieved by checking associativity ticks, signal strength, and link availability towards each neighbor, battery life is also checked considering consumed power needed to transmit to this neighbor. If these metrics satisfy predefined thresholds, neighbor is selected as an FG node and the receiver starts sending Join-reply message to it setting its type as member node in its corresponding neighbor table entry. Otherwise, the neighbor is not an FG node and would not receive Join-reply. In the case where there is no neighbor nodes satisfying the predefined thresholds for stability and battery life, the node with the best metrics among all the neighbors will be selected as FG node. Before broadcasting the Join-reply packet by the multicast receiver to the selected neighbors, the receiver stores the multicast group ID in the packets' Source ID field and the ID of the requesting node (source of Join-request) in the packets' Destination ID field. A source route from the multicast receiver (source of Join-reply) to the requesting node is also accumulated in the route record field during Join-reply propagation. A selected FG node, receiving a Join-reply, creates an entry in its multicast routing cache corresponding to the multicast group. In this entry, the node sets its state as FG node and copies the reversed accumulated route of the received Join-reply. It also stores in this entry the source ID of the Join-reply, and the time at which the Join-reply is received. After table entry creation, the FG node performs the previous steps to select FG nodes among its own neighbors. Then, it sends Join-reply packets to the selected FG nodes after appending its address to the route record field of each transmitted Join-reply. This process continues until reaching the source of request constructing a mesh of FG nodes connecting group members. At this time, the source receiving a Join-reply packet becomes a multicast source (group member) and creates an entry corresponding to the multicast group in its multicast routing cache. In this entry, it sets its state as Source node and copies the reversed accumulated route in the Join-reply. It also stores the source ID of the reply Labiod and Moustafa Expires 6 June 2002 [Page 19] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 packet, and the time at which the Join-reply is received. Due to mesh structure, more than one Join-reply MAY be received by the source from the same multicast group and multiple routes are stored in the source multicast routing cache. For example, suppose node R (multicast receiver) is attempting to reply to a request from node S (multicast source). The reply phase initiated by R in this example would select D,B,A, and E as FG nodes and proceed as follows: ^ ^ ^ ^ thresholds | | | | not reached +-----+ +-----+ +------+ +-----+ +------+ | S |<-----| A |<--------| B |-------| C |-------| R | +-----+ +-----+ +------+ +-----+ +------+ ^thresholds thresholds ^ thresholds thresholds / \ reached reached \ reached reached / \ "R,D,B,A" "R,D,B" \ "R,D" "R" / \ +------+ +-----+ / -------- | E |<----------| D |<----------------- thresholds +------+thresholds +-----+ reached | reached | "R,D,E" v "R,D" v After mesh creation, an FG member node, having unexpired routes to a certain multicast group in its multicast routing cache, can reply to any Join-request for this group. At this case, the FG node broadcasts a Join-reply to the requesting source with the route record field taken as its ID together with the corresponding route to the multicast group stored in its multicast routing cache. 4.3. Data Forwarding Data forwarding towards a certain multicast group starts by the multicast source. It selects one of the routes from its multicast routing cache leading to the REQUIRED multicast group. Route selection takes place according to certain criteria, such that the shortest path route in terms of number of hops is selected. In the case of more than one shortest path route, the most fresh route is selected. After route selection, the multicast source starts transmitting data to multicast group. Each data packet carries in its header the selected route, indicating the sequence of hops to be followed by the packet. It stores also the ID of the multicast source in its Source ID field and multicast group ID in its Destination ID field. A sequence number, generated by the source, for each transmitted data packet is also stored in the Sequence number field of the packet. For example, suppose node S (multicast source) is attempting to transmit data to node R (multicast receiver) using the mesh created Labiod and Moustafa Expires 6 June 2002 [Page 20] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 of FG nodes D,B,A, and E. It selects the shortest route to the multicast receiver and proceeds in sending data carrying header as follows: ^ ^ ^ ^ | | | | +-----+ +-----+ +------+ +-----+ +------+ | S |------| A |---------| B |-------| C |-------| R | +-----+ +-----+ +------+ +-----+ +------+ \ \ ^ \ \ / \"S-id,gp-id,(E,D,R)" \ / \ 1 +------+ 2 +-----+ 3 / ------->| E |----------------->| D |----------> +------+"S-id,gp-id,(D,R)"+-----+"S-id,gp-id,(R)" | | v v FG nodes receiving the data packets will follow same route selection procedure and re-transmit the packet. This process continues until reaching all multicast receivers. To guarantee data transmission to all multicast receivers, the node duplicates transmission if the selected route leads directly to a multicast receiver. Duplication in transmission occurs by selecting one more route, following same previous criteria, and transmitting data to both routes. The sequence number together with the Source ID identify each data packet to prevent duplication in reception. When a node receives a new data packet, it stores the Source ID and sequence number of this packet in its message duplication table. During data packet propagation afterwards, the packet is checked in the nodes' message duplication tables and discarded if it was received before. A multicast receiver, receiving a data packet for the first time, creates an entry in its receiver multicast routing table towards the multicast source transmitting this packet. This entry stores the route to the multicast source by copying the reversed route stored in the packet header with adding the source ID at the beginning. Refreshment for this entry takes place through reception of another data packets from this source (Section 4.5.2). 4.4. Member Node Transmission During a multicast session, a mesh member node MAY have data to send to the multicast group. This node starts by checking its multicast routing cache for a valid route to the multicast group, if one is found then it is used by the node to transmit its data. Otherwise, same previous route discovery process SHOULD occur indicating that a link failure has occurred causing no valid routes to be found. 4.5. Maintenance Procedures Labiod and Moustafa Expires 6 June 2002 [Page 21] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Maintenance procedures refer to mechanisms within SRMP protocol by which the multicast mesh is refreshed, and link breaks are detected and repaired. They also support continuous node-neighbor information together with a pruning mechanism allowing any node to leave the group These procedures utilize three types of packets: MAC layer Beacons (Section 4.5.1), Multicast-RERR Message (Section 4.5.3), and Leave Group Message (Section 4.5.4). 4.5.1. Neighbor Existence Mechanism SRMP introduces MAC layer beacons providing each node with neighbors existence information. By the time a node receives a neighbor beacon, it updates or creates the corresponding entry of this neighbor in its stability table. Entry update takes place through incrementing the associativity ticks field, and setting the signal strength field according to the level of strength the beacon is received. In addition, the node performs continuous prediction for link availability towards the neighbor through periodical estimation for [L(Tp) x Tp]. If no beacons are received by a node from a certain neighbor upto a certain period of time, the node indicates neighbor's movement and updates its stability table fields towards this neighbor. In this case, update takes place through setting the associativity ticks value to zero and signal strength and link availability fields to null until new information from this neighbor is received. 4.5.2. Mesh Refreshment Mechanism One of the characteristics in SRMP is its simplicity in refreshing the multicast mesh without requiring extra control overhead. During each data packet propagation from the multicast source to the different multicast receivers, route refreshment for different paths on the mesh takes place. For each data packet transmitted by the multicast source, the source updates the timer of the corresponding route entry in the multicast routing cache. In addition, each FG node forwarding this data packet scans the route record field in the packet header, starting from its address, together with the Destination ID field and refreshes the Route Validation Timer of the corresponding route entry in the multicast routing cache. On the other hand, a multicast receiver scans the header of each data packet received for the Source ID, Route record, and Destination ID fields. This scanned information is used to refresh its timer of the corresponding entry to this source in the receiver multicast routing table. Each node performs continuous check on timers of the multicast Labiod and Moustafa Expires 6 June 2002 [Page 22] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 routing cache and receiver multicast routing table (in the case of a receiver node), such that multicast group entries with expired timers are purged. 4.5.3. Link Repair Mechanism SRMP reacts to link failure on-demand, such that it detects link failure during data transmission through the use of MAC layer support, it also follows two approaches in dealing with link failure. First, when link failure takes place between two FG nodes, SRMP follows the same proposed idea of DSR unicast protocol. In this case, the node detecting failure generates a Multicast-RERR packet of type 0 to the original source of data packet indicating the broken link. It also deletes from its cache any routes containing the broken link. Each node on the way receiving this packet updates its cache by deleting routes containing this broken link. For example, suppose node S (multicast source) is transmitting data to node R (multicast receiver) using the path E-D-R, and the link between E and D failed. Node E then attempts to send Multicast-RERR packet back to S informing of this failure. S then selects another path (S-A-B-D-R) to send its data and proceeds as follows: ^ ^ ^ ^ | | | | +-----+ +-----+ +------+ +-----+ +------+ | S |------| A |---------| B |-------| C |-------| R | | | ---> | | ---> | | | | | | +-----+ 4 +-----+ 5 +------+ +-----+ +------+ \^ \\ ^ \\ \\6 / \\ \v / \\ 3 +------+ +-----+ / \------- | E | | D | 7 / -------> | |-----x | |---------> 1 +------+ 2 +-----+ | | v v Second, when link failure takes place between an FG node and a multicast receiver, the FG node detecting the failure simply deletes this receiver membership from its neighbor table. Each FG node checks its neighbor table periodically, such that if it discovers no more members for a certain multicast group it deletes routes to this group from its caches, then sends a Multicast-RERR of type 1 to all its member neighbors. The broken link field in this packet stores the link between the failure detector FG node and the multicast group, while the route to sender field is set to the member neighbor address. Each member neighbor, receiving this packet, inturn Labiod and Moustafa Expires 6 June 2002 [Page 23] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 cleans its cache by deleting routes with this link. This process is repeated until all member nodes in the mesh are visited. For example, suppose node S (multicast source) is transmitting data to node R (multicast receiver) using the path E-D-R, and the link D-R failed. Then, D deletes R membership from its neighbor table. ^ ^ ^ ^ | | | | +-----+ +-----+ +------+ +-----+ +------+ | S |------| A |---------| B |-------| C |-------| R | +-----+ +-----+ +------+ +-----+ +------+ \ \ \ \ \ \ x \ 1 +------+ 2 +-----+ 3 / -------->| E |-------------->| D |----------> +------+ +-----+ | | v v 4.5.4. Pruning Scheme SRMP provides an efficient pruning mechanism allowing a member node to leave the multicast session cancelling its membership to the multicast group. A multicast source wishing to leave a certain multicast group simply stops transmitting data to this group, and removes entries concerning this group from its multicast routing cache. This causes expiration and deletion of all routes stored in the FG nodes' caches, connecting this source to the multicast group, due to no refreshment. Similarly, the receiver multicast routing table entries towards this source will be expired and deleted. On the other hand, a multicast receiver wishing to leave a certain multicast group sends a Leave Group message to all its member neighbors, and deletes from its Receiver Multicast Routing Table all entries corresponding to this group. A member neighbor receiving the Leave Group message cancels in its turn this receiver membership from its Neighbor Stability Table by setting its type as non-member node. Each FG node checks its neighbor table periodically, such that if it discovers no more members for a certain multicast group it deletes routes to this group from its caches, then sends a Multicast-RERR of type 1 to all its member neighbors following previous procedure of link failure. Moreover, an FG node wishing to leave a certain multicast group can cancel its membership to this group and prune itself from the mesh. This node sends a Leave Group message to its member neighbors following the same procedure mentioned above. Labiod and Moustafa Expires 6 June 2002 [Page 24] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 5. SRMP-ODMRP Comparison SRMP and ODMRP are mesh-based protocols using the concept of FG nodes to connect multicast group members. Although the latter does not guarantee optimal routes due to the use of the shortest path technique in its choice of FG nodes, the former applies a more effective criteria in the choice of FG nodes regarding paths stability and link availability based on future prediction of links state. Consequently, SRMP can guarantee reliable delivery together with less communication overhead and end-to-end delay. During data forwarding process, SRMP outperforms ODMRP through the use of source routing concept storing in the packet header the route to be followed, and allowing forwarding nodes to scan the routing information. ODMRP depends on next hop information to transmit a data packet. It also depends on periodical (Join-Query/Join-reply) to refresh route entries constituting the mesh. SRMP treats this case through the use of a more effective mechanism making use of data propagation and requiring no extra control overhead. In fact, the request/reply phase in SRMP has better impact on network performance, such that the request is sent once by a source wishing to join the group. Replies from multicast receivers are then sent back in form of small size reply packets targeted to the source. ODMRP follows a different approach by using periodical Query/reply during the period of data transmission requiring more control and communication overhead. In addition, it transmits a reply table with multiple reply entries to different sources causing reliability problem, such that the verification of the Join- reply delivery can not be handled by the MAC layer and special mechanisms are REQUIRED to overcome this problem. ODMRP has no special mechanism to handle link breakage, it only assumes that a receiver wanting to leave would stop sending replies. On the other hand, SRMP has an effective link breakage mechanism to discover unavailable routes and delete them from nodes caches giving more robustness to the protocol. It also uses a special pruning mechanism allowing mesh members to leave the group at any time. 6. Constants Multicast Routing cache Route_Validation_Timeout 500 seconds Receiver Multicast Routing Table Route_Validation_Timeout 200 seconds Neighbor Stability Table Association Stability Threshold 50 ticks Labiod and Moustafa Expires 6 June 2002 [Page 25] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Signal Strength Threshold 70% (transmitted power) Link Availability Threshold 75 % Battery Life Threshold 50 % (initial power) Link Availability Prediction 1/lamda 60 seconds Tp 50-120 seconds 7. IANA considerations This document proposes the use of an SRMP header, which requires an IP Protocol number. 8. QoS and Security Considerations This document does not specifically address QoS and/or security concerns. This document does assume that all nodes participating in the SRMP protocol do so in good faith and without malicious intent to corrupt the routing ability of the network. Concerning QoS, it can be taken into account by using a field in the packet header that allows the classification of data transmission. This field SHOULD be a combination of QoS criteria such as (delay and bit error rate) that specifies the QoS class accordingly. Labiod and Moustafa Expires 6 June 2002 [Page 26] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Acknowledgments We would like to thank our colleague in department INFRES (Informatique & Rėseaux : Computer & Networks), Philippe Godlewski for his comments and gracious help on the work carried out in this document. Labiod and Moustafa Expires 6 June 2002 [Page 27] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 References [1] D. Johnson, D. Maltz. "Dynamic source routing in ad hoc wireless networks", in Mobile Computing, T.Imielinski and H. korth,Eds. Norwell, MA: Kluwer, 1996. [2] C. Chiang, M. Gerla, and L. Zhang. "Forwarding Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless Networks ", Baltzer Cluster Computing, Vol.1, no. 2, pp. 187-196, 1998. [3] K. Obraczka, G. Tsudik. "Multicast Routing Issues in Ad Hoc Networks", IEEE International Conference on Universal Personal Communication (ICUPC'98), October 1998. [4] IETF MANET working group. "On-Demand Multicast Routing Protocol (ODMRP) for Ad Hoc Networks", Internet draft , January 2000. [5] S. Lee, W. Su, and M. Gerla. "On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks", ACM/Baltzer Mobile Networks and Applications, 2000. [6] A. B. McDonald and T. Znati, " A Path Availability Model for Wireless Ad Hoc Networks," Proceedings of IEEE WCNC, September 1999. [7] Scott Bradner. Key words for use in RFCs to Indicate Requirement Levels. RFC 2119, March 1997. [8] Joyce K. Reynolds and Jon Postel. Assigned numbers. Internet Request For Comments RFC 1700, October 1994. [9] C-K. Toh, "Associativity-Based Routing for Ad Hoc Mobile Networks," Wireless personal Communication, vol. 4, no. 2, March 1997, pp. 1-36. [10] R. Dube and al., "Signal Stability based Adaptive Routing (SSR) for Ad Hoc Mobile Networks," IEEE personal communication, febraury 1997, pp. 36-45. [11] S. Jiang, D. He and J. Rao, "A Prediction-based Link availability Estimation for Mobile Ad Hoc Networks". In the proceedings of IEEE Infocom, April 2001. [12] H. dajiang, J. Shengming and R. Jianqiang, "A Link Availability Prediction Model for Wireless Ad Hoc Networks," Proceedings 2000 International Conference on Distributed Computing System workshop, Taipei, Taiwan, April 2000, p. D7- D11. Labiod and Moustafa Expires 6 June 2002 [Page 28] INTERNET-DRAFT Source Routing-based Multicast Protocol 6 November 2001 Authors Addresses Questions about this document can be directed to: Houda Labiod ENST (Ecole Nationale Supėrieure des Tėlėcommunications), Paris INFRES (Informatique & Rėseaux : Computer & Networks) Department 46, rue Barrault-75634 Paris Cedexs 13 “ France Phone : +1 01 45 81 74 36 Fax : +1 01 45 81 31 19 Email : labiod@enst.fr Hasnaa Moustafa ENST, (Ecole Nationale Supėrieure des Tėlėcommunications) Paris INFRES (Informatique & Rėseaux : Computer & Networks) Department 46, rue Barrault-75634 Paris Cedexs 13 “ France Phone : +1 01 45 81 80 86 Fax : +1 01 45 81 31 19 Email : moustafa@enst.fr Labiod and Moustafa Expires 6 June 2002 [Page 29]