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]