INTERNET-DRAFT Destination-Driven ODMRP November 2008
Internet Engineering Task Force K. Tian
Internet Draft Beijing University of Posts
Intended status: Proposed Standard and Telecommunications
Z. Zhao
B. Zhang
H. Liu
Chinese Academy of Sciences
J. Ma
Nokia Research Center
Expires: May 2009 November 2008
Destination-Driven On-Demand Multicast Routing Protocol
draft-ke-dodmrp-00
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
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.
Copyright Notice
Copyright (C) the IETF Trust (2008).
Abstract
Our protocol embeds a destination-driven feature into the on-demand
multicast structure building process of an existing multicast
protocol ODMRP (On-Demand Multicast Routing Protocol), which is a
mesh-based multicast scheme and uses a forwarding group concept. The
design objective of destination-driven on-demand multicast routing
protocol (D-ODMRP) is to improve the multicast forwarding efficiency
Tian et al. Expires: May 2009 [Page 1]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
for wireless Ad Hoc networks. To achieve this goal, the path to
reach a multicast destination is biased towards those paths passing
through another multicast destination.
Conventions used in this document
"D-ODMRP" indicates Destination-Driven On-Demand Multicast Routing
Protocol.
"Forwarding group" indicates a group of nodes participating in
multicast packet forwarding.
"Multicast mesh" indicates the topology defined by the link
connection between forwarding group members.
"Join Query" indicates the special data packet sent by multicast
sources to establish and update group memberships and routes.
"Join Reply" indicates the table broadcasted by each multicast
receiver and forwarding node to establish and update group
memberships and routes
"FG_FLAG" indicates a soft state, which implies the node is a member
of the forwarding group.
"Extra Hop" indicates the hop distance on a forwarding structure
from the last group member to the current group member. In a routing
process, its initial value is set to zero and it will be reset to
zero again once a Join Query reaches a group member node.
"Rand (t1, t2)" indicates a random time chosen between time t1 and
time t2. Introduction of rand(0, T) is to reduce retransmission
contention possibilities by different nodes in the network.
The key words "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 [2].
Tian et al. Expires: May 2009 [Page 2]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
Table of Contents
Status of This Memo
Abstract
1. Introduction...................................................4
2. Protocol Overview..............................................4
2.1 Overview of ODMRP..........................................4
2.2 Destination-Driven Idea....................................4
2.3 Selection of Deferring Timer Values........................5
2.4 An Example of Join Query forwarding process................5
2.5 Contents of Tables.........................................6
2.5.1 Routing Table......................................6
2.5.2 Forwarding Group Table.............................6
2.5.3 Message Cache......................................6
3. Operation......................................................7
3.1 Forwarding Group Setup.....................................7
3.1.1 Originating a Join Query...........................7
3.1.2 Processing a Join Query............................7
3.1.3 Originating a Join Reply...........................7
3.1.4 Processing a Join Reply............................7
3.2 Handling a Multicast Data Packet...........................8
Security Considerations...........................................8
IANA Considerations...............................................8
References........................................................8
Normative References...........................................8
Informative References.........................................8
Acknowledgments...................................................8
Author's Addresses................................................9
Full Copyright Statement..........................................9
Intellectual Property.............................................9
Tian et al. Expires: May 2009 [Page 3]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
1. Introduction
In this draft, we present the design of multicast routing protocol,
which embeds the destination-driven idea into an existing on-demand
multicast protocol ODMRP [4][5][6] and accordingly the designed
protocol is referred to as Destination-driven ODMRP (D-ODMRP) [3].
The design objective is effectively to build a cost-effective mesh-
based multicast forwarding structure and improves the multicast
forwarding efficiency. In D-ODMRP, to build a multicast forwarding
structure, the path to reach a multicast destination is biased
towards those paths passing through another multicast destination.
The destination-driven protocol design is simple and can greatly
improve the multicast forwarding efficiency without extra protocol
overhead.
2. Protocol Overview
2.1 Overview of ODMRP
ODMRP is a mesh-based multicast protocol using a forwarding group
concept, which is a subset of nodes forwarding multicast packets. A
soft state approach is taken in ODMRP to maintain multicast group
members, and no explicit control message is required for a node to
join or leave the group. The data source establishes and updates
group membership and multicast routes.
In ODMRP, once receiving a non-duplicate Join Query, each node in
the network stores the upstream node address (i.e., reverse path
learning) into its local route table and rebroadcasts the packet
further to its neighbor nodes. When a multicast group member
receives the Join Query, it composes a Join Reply packet and sends
this packet all the way back to the source along the learned reverse
path until reaching a node who has already sent upstream such a
Reply or reaching the multicast data source. Nodes on the reverse
path is flagged as forwarders (i.e., these nodes are members of the
so-called Forwarding Group) and each of them locally keeps a soft
state of Forwarding Group flag. During the data transferring phase,
nodes in the forwarding group broadcast received multicast packets
from the source.
2.2 Destination-Driven Idea
To realize the destination-driven idea in an on-demand construction
of multicast forwarding structure, we modify the procedures for
every node to handle received Join Queries in ODMRP. Specifically,
we intentionally add extra deferring time at every node receiving a
Join Query, and the value of deferring time is set based on how far
this received Join Query has left from the last group member that
the Join Query has met. In general, the larger this distance is, the
Tian et al. Expires: May 2009 [Page 4]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
longer the deferring time will be. This time deferring is to enable
those Join Queries taking better routes to travel faster than others,
in order to reduce the extra cost for adding new nodes into the
forwarding structure.
2.3 Selection of Deferring Timer Values
In D-ODMRP, when a member node receives a Join Query packet, it
further forwards the packet within rand(0, T) time, where T is a
system parameter. When a non-member node receives a Join Query, it
defers its retransmission with a period of time JQDelay, which is
calculated as follows:
JQDelay = min{pow(2,ExtraHop)*T, MAX*T}+rand(0, T) (1)
The introduction of MAX is to avoid a non-member node to defer its
forwarding of a Join Query with too large delay.
2.4 An Example of Join Query forwarding process
(1,1) (2,2)
+-+[2T,3T] +-+[4T,5T]
-->|E|------------------->|F|---
/ +-+ +-+ \
/ \
(0,0)/ \ [6T,8T]
+-+/ -> +-+
|S| |D|(4,1)>(3,3)
+-+\ -> +-+
\ / [2T,5T]
\ /
\+-+[0,T] +-+[2T,T] +-+[0,T]
|A|---------->|B|----------->|C|
+-+ +-+ +-+
(1,1) (2,1) (3,2)
Source: S;
Multicast Destinations: A, C and D;
Forwarding structure includes S, A, B, C, and D.
Let us see the above figure as an example of building an efficient
forwarding structure. In the figure, node S is the multicast source,
and nodes A, C and D are the multicast destinations. The figures in
parentheses besides each node represent the hop distance from source
and that from the last group member, which Join Query met, to the
current node, respectively. The figures in square brackets besides
each node represent the deferring time before the node transmitting
Join Query. For example, [0, T] besides node A means the deferring
time at node A is between 0 and T. The figures in square brackets
besides node D represent the total delay time for Join Queries
taking the two different paths from S to D.
Tian et al. Expires: May 2009 [Page 5]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
To build a forwarding structure, source S floods a Join Query packet
across the network. After nodes A and E receive the Join Query, they
defer their re-transmissions with different delays. Node E defers
its re-transmission with a time of [2T, 3T], and node F defers [4T,
5T] time. The Join Query travelling along the path S->E->F->D takes
a total delay of [6T, 8T] before reaching D. In contrast, the Join
Query traveling along the path S->A->B->C->D takes a total delay of
[2T, 5T] before reaching D since nodes A and C are group members of
the multicast session. Thus, the Join Query taking the down path
will arrive at node D ahead of that taking the upper path.
Accordingly, group member D composes a Join Reply according to the
Join Query received from C. As a result, only nodes A, B, and C will
be flagged as forwarders for the multicast session under
investigation. A reduction in the total number of forwarders is
achieved.
2.5 Contents of Tables
Nodes running D-ODMRP are required to maintain the following tables
including the specified fields.
2.5.1 Routing Table
According to D-OMDRP, each node maintains the routing table for
providing the next hop information when transmitting Join Replies.
When a non-duplicate Join Query is received, an entry of the routing
table is inserted or updated. The destination (i.e., the source node
of multicast packet) and the next hop to the destination are stored
into the routing table.
2.5.2 Forwarding Group Table
The table is maintained by each multicast forwarder for storing the
forwarding group soft state, which records the multicast group ID
and the time when the node was last refreshed.
2.5.3 Message Cache
When a node receives a new Join Query or data, it stores the source
address and the unique identifier of the packet. When a new Join
Query or data packet is delivered to a node, it stores the source ID
and the unique identifier of the packet, and maintains the cache
employing scheme of FIFO (First In First Out).Message Cache is
maintained to prevent duplicate packet to be sent.
Tian et al. Expires: May 2009 [Page 6]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
3. Operation
3.1 Forwarding Group Setup
3.1.1 Originating a Join Query
When a source wants to send data packet but has no route to the
multicast group, it composes a Join Query packet. The packet must
contain the following fields:
* TIME_TO_LIVE_VALUE, is adjusted based on network size.
* Source ID and Last Hop ID, is initially set to the source ID.
* Sequence Number, must be large enough to prevent wraparound
ambiguity
* Hop Count, is initially set to zero.
* Extra Hop, is initially set to zero.
3.1.2 Processing a Join Query
When a node receives a Join Query packet:
1. Check if it is a duplicate by comparing the (Source ID, Sequence
Number) combination with the entries in the message cache. If a
duplicate, then discard the packet. DONE.
2. If it is not a duplicate, insert an entry into the message cache
with the information of the received packet (i.e., sequence
number and source ID) and insert/update the entry for routing
table (i.e., backward learning).
3. If the node is a multicast group member, it originates a Join
Reply packet.
4. Increase the Hop Count field by one and decrease the TTL field by
one. If the node is a group member, increase the Cost Hop field by
one.
5. If the TTL field value is less than or equal to zero, then discard
the packet. DONE.
6. If the TTL field value is greater than zero, then calculate the
delay timer values JQDelay by the equation (1) and set the node ID
into Last Hop ID field.
7. Broadcast the Join Query packet. DONE.
3.1.3 Originating a Join Reply
When a multicast group member receives a Join Query, it transmits a
Join Reply packet containing each sender ID and next hop ID of a
multicast group, which according to the Join Query.
3.1.4 Processing a Join Reply
When a node receives a Join Reply, it checks Next Hop ID field of
the received Join Reply. If one or more entries coincide with the
node ID, the node is flagged as forwarding group member, composes a
Tian et al. Expires: May 2009 [Page 7]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
new Join Reply, and broadcasts the packet. The next hop node ID can
be obtained from the routing table.
3.2 Handling a Multicast Data Packet
Multicast source broadcasts out data packets to nodes in the
forwarding group. When an intermediate node receives a data packet,
it first checks the setting of FG_FLAG for the multicast group. If
the node is in the forwarding group, it broadcasts the received
packet at an instant of rand(0, T) time.
Security Considerations
Security is outside the scope of this document and not discussed.
IANA Considerations
This document has no actions for IANA.
References
Normative References
[1] Bradner, S., Ed., "IETF Rights in Contributions", BCP 78, RFC
3978, January 2005.
[2] S. Bradner. Key words for use in RFCs to Indicate Requirement
Levels. RFC 2119, March 1997.
Informative References
[3] K. Tian, B. Zhang, H. Mouftah, Z. Zhao, J. Ma. Destination-
Driven On-Demand Multicast Routing Protocol for Wireless Ad Hoc
Networks. Submitted to IEEE ICC'09.
[4] S.-J. Lee, W. Su, and M. Gerla. On-Demand Multicast Routing
Protocol in Multihop Wireless Mobile Networks. ACM/Kluwer Mobile
Networks and Applications, 2002, vol. 7, no. 6, pp. 441-453.
[5] S.-J. Lee, M. Gerla, and C.-C. Chiang. On-Demand Multicast
Routing Protocol. In Proceedings of IEEE WCNC'99, New Orleans,
LA, Sep. 1999, pp. 1298-1302.
[6] S.-J. Lee, W. Su, and M. Gerla. Ad hoc Wireless Multicast with
Mobility Prediction. In Proceedings of IEEE ICCCN'99, Boston, MA,
Oct. 1999, pp. 4-9.
Acknowledgments
The protocol described in this draft was supported in part by
National High-Tech Research and Development Plan of China under
Grant No. 2006AA01Z207-1, the Knowledge Innovation Program of the
Chinese Academy of Sciences under Grant No. KGCX2-YW-120, which are
Tian et al. Expires: May 2009 [Page 8]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
for developing robust and efficient wireless multihop routing
protocols.
Author's Addresses
Ke Tian
Beijing University of Posts and Telecommunications
10 Xitucheng Road, Beijing 100876, China
Email: tianke999@gmail.com
Zhuang Zhao and Baoxian Zhang
Graduate University of Chinese Academy of Sciences
19A Yuquan Road, Beijing 100049, China
Email: {zhaozh, bxzhang}@gucas.ac.cn
Haitao Liu
Key Lab of Wireless Sensor Network and Communications
Shanghai Institute of Microsystem and Information Technology of
Chinese Academy of Sciences
865 Changning Road, Shanghai 200050, China
Jian Ma
Nokia Research Center
Beijing 100176, China
Email: jian.j.ma@nokia.com
Full Copyright Statement
Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE
IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL
WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY
WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE
ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS
FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed
to pertain to the implementation or use of the technology described
in this document or the extent to which any license under such
Tian et al. Expires: May 2009 [Page 9]
INTERNET-DRAFT Destination-Driven ODMRP November 2008
rights might or might not be available; nor does it represent that
it has made any independent effort to identify any such rights.
Information on the procedures with respect to rights in RFC
documents can be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use
of such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository
at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Tian et al. Expires: May 2009 [Page 10]