INTERNET-DRAFT Destination-Driven ODMRP May 2010 Internet Engineering Task Force K. Tian Internet-Draft Beijing University of Posts Intended status: Proposed Standard and Telecommunications B. Zhang Graduate University of Chinese Academy of Sciences X. Gao, Q. Wang, and Z. Zhao Wuxi Ubisensing Internet of Things Technology Co., Ltd K. Huang Institute of Microelectronics of Chinese Academy of Sciences J. Ma Nokia Research Center Expires: November 2010 May 2010 Destination-Driven On-Demand Multicast Routing Protocol draft-ke-dodmrp-01 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and 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. This Internet-Draft will expire on September 8, 2010. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. Tian et al. Expires: May 2009 [Page 1] INTERNET-DRAFT Destination-Driven ODMRP May 2010 This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License. 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 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. "Energy Index" indicates energy level of node, the higher the index is, the higher remaining energy the corresponding node has. "Extra Hop" indicates the hop distance on a forwarding structure from the last group member to the current group member. In a routing Tian et al. Expires: May 2009 [Page 2] INTERNET-DRAFT Destination-Driven ODMRP May 2010 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 3] INTERNET-DRAFT Destination-Driven ODMRP May 2010 Table of Contents Status of This Memo Abstract 1. Introduction...................................................5 2. Protocol Overview..............................................5 2.1 Overview of ODMRP..........................................5 2.2 Destination-Driven Idea....................................5 2.3 Energy Index Idea..........................................6 2.4 Selection of Deferring Timer Values........................6 2.5 An Example of Join Query forwarding process................6 2.6 Contents of Tables.........................................7 2.6.1 Routing Table 7 2.6.2 Forwarding Group Table 8 2.6.3 Message Cache 8 3. Operation......................................................8 3.1 Forwarding Group Setup.....................................8 3.1.1 Originating a Join Query 8 3.1.2 Processing a Join Query 8 3.1.3 Originating a Join Reply 9 3.1.4 Processing a Join Reply 9 3.2 Handling a Multicast Data Packet...........................9 Security Considerations...........................................9 IANA Considerations...............................................9 References........................................................9 Normative References...........................................9 Informative References.........................................9 Acknowledgments..................................................10 Author's Addresses...............................................10 Tian et al. Expires: May 2009 [Page 4] INTERNET-DRAFT Destination-Driven ODMRP May 2010 1. Introduction In this draft, we present the design of multicast routing protocol, which embeds the destination-driven idea and energy index 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 and nodes with higher remaining energy. The destination-driven protocol design is simple and can greatly improve the multicast forwarding efficiency and energy 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 Tian et al. Expires: May 2009 [Page 5] INTERNET-DRAFT Destination-Driven ODMRP May 2010 this received Join Query has left from the last group member that the Join Query has met. In general, the longer this distance is, the 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 Energy Index Idea For our scheme to work, the full range of energy capacity EnergyMAX is divided into M intervals indexed for 1 to M. The energy index associated with a node u is denoted by EIu. For a node u associated with an index EIu, where EIu is an integer and 1 EIu M, we have (EIu-1)*(EnergyMAX/M) Energy.u < EIu*(EnergyMAX/M). In D-ODMRP, when a node receives a Join Query packet, the time deferring also references to the node energy index EIu. In general, the higher the node energy index is, the shorter the deferring time will be. This time deferring is to enable those Join Queries taking higher remaining energy routes to travel faster than others, which lead to energy balance in entire networks. 2.4 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}+T/EIu+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.5 An Example of Join Query forwarding process Let us see the following 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 the bottom right hand corner of the node represent the energy index, here the value of M is 3. The figures in square Tian et al. Expires: May 2009 [Page 6] INTERNET-DRAFT Destination-Driven ODMRP May 2010 brackets besides node D represent the total delay time for Join Queries taking the two different paths from S to D. 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 [3T, 4T], and node F defers [4.5T, 5.5T] time. The Join Query travelling along the path S->E->F->D takes a total delay of [7.5T, 9.5T] before reaching D. In contrast, the Join Query traveling along the path S->A->B->C->D takes a total delay of [3.1T, 6.1T] 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. (1,1) (2,2) +-+[3T,4T] +-+[4.5T,5.5T] -->|E|------------------->|F|--- / +-+ 1 +-+ 2 \ / \ (0,0)/ \ [7.5T,9.5T] +-+/ -> +-+ |S| |D|(4,1)>(3,3) +-+\ -> +-+ \ / [3.1T,6.1T] \ [0.3T,1.3T] [2.3T,3.3T] / \+-+ +-+ +-+[0.5T,1.5T] |A|---------->|B|----------->|C| +-+ 3 +-+ 3 +-+ 2 (1,1) (2,1) (3,2) Source: S; Multicast Destinations: A, C and D; Forwarding structure includes S, A, B, C, and D. 2.6 Contents of Tables Nodes running D-ODMRP are required to maintain the following tables including the specified fields. 2.6.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 Tian et al. Expires: May 2009 [Page 7] INTERNET-DRAFT Destination-Driven ODMRP May 2010 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.6.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.6.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. 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. Tian et al. Expires: May 2009 [Page 8] INTERNET-DRAFT Destination-Driven ODMRP May 2010 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 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 Tian et al. Expires: May 2009 [Page 9] INTERNET-DRAFT Destination-Driven ODMRP May 2010 [3] K. Tian, B. Zhang, H. Mouftah, Z. Zhao, J. Ma. Destination- Driven On-Demand Multicast Routing Protocol for Wireless Ad Hoc Networks. In Proc. IEEE ICC'09, Dresden, Germany, June 2009. [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 Key Special Program of China under Grant Nos. 2009ZX03006- 001-02, 2009ZX03006-006, 2010ZX03006-001-02, which are for developing robust and efficient wireless multihop routing protocols and related software. Author's Addresses Ke Tian State key Lab of Networking and Switching Technology Beijing University of Posts and Telecommunications 10 Xitucheng Road, Beijing 100876, China Email: tianke999@gmail.com Baoxian Zhang Graduate University of Chinese Academy of Sciences 19A Yuquan Road, Beijing 100049, China Email: bxzhang@gucas.ac.cn Xue Gao, Qin Wang, and Zhuang Zhao Wuxi Ubisensing Internet of Things Technology Co., Ltd, Building 7, Area C, TaiHu New Town Science & Education Industrial Park, Jinxi Road, BinHu District, Wuxi City, Jiangsu Province, China. Email: {gaoxue, wangqin, zhaozhuang}@ubisensing.com Kui Huang Research Center of IoT Institute of Microelectronics of Chinese Academy of Sciences, Beijing 100029, China Email: huangkui@ime.ac.cn Jian Ma Nokia Research Center Beijing 100176, China Tian et al. Expires: May 2009 [Page 10] INTERNET-DRAFT Destination-Driven ODMRP May 2010 Email: jian.j.ma@nokia.com Tian et al. Expires: May 2009 [Page 11]