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)
<draft-labiod-manet-srmp-00.txt>
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 <draft-ietf-manet-
odmrp-02.txt>, 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]