IETF MANET Working Group Jorjeta G. Jetcheva INTERNET-DRAFT Yih-Chun Hu Carnegie Mellon University David A. Maltz AON Networks David B. Johnson Rice University 20 July 2001 A Simple Protocol for Multicast and Broadcast in Mobile Ad Hoc Networks Status of This Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026 except that the right to produce derivative works is not granted. 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. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page i] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 Abstract The protocol specified in this document is designed to provide multicast and broadcast functionality in mobile ad hoc networks. It utilizes the Route Discovery mechanism defined by the Dynamic Source Routing protocol (DSR) [4, 5, 7] to flood the data packets through the network. Although this protocol is derived from DSR, it can be implemented as a stand-alone protocol. In fact, it does not rely on unicast routing to operate. If DSR is already implemented on the network, very minor modifications are required to enable this protocol. This multicast and broadcast protocol utilizes controlled flooding to distribute data in the network and does not require the establishment of state in the network for data delivery. It is not intended as a general purpose multicast protocol. Its applicability is mainly in environments characterized by very high mobility or by a relatively small number of nodes. In the former case, protocols relying on the establishment of multicast state perform inadequately because they are unable to track the rapid changes in topology. In the latter case, the overhead of keeping multicast state exceeds the overhead of flooding. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page ii] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 Contents Status of This Memo i Abstract ii 1. Introduction 1 2. Assumptions 2 3. Protocol Overview 3 3.1. Overview of DSR . . . . . . . . . . . . . . . . . . . . . 3 3.2. Overview of the Multicast and Broadcast Protocol . . . . 4 4. Detailed Operation 5 4.1. Originating a Packet . . . . . . . . . . . . . . . . . . 5 4.2. Originating a Route Request . . . . . . . . . . . . . . . 5 4.3. Processing a Received Route Request Option . . . . . . . 5 5. IANA Considerations 6 6. Security Considerations 7 Acknowledgments 8 References 9 Chair's Address 10 Authors' Addresses 11 Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page iii] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 1. Introduction This document describes a protocol for multicast and broadcast in wireless ad hoc networks. This protocol was developed by the Monarch Project [6, 3] at Rice University and Carnegie Mellon University. This protocol is not meant to be a general purpose multicast protocol. It is applicable to small networks, or networks characterized by very high mobility. The definition of this protocol is derived from the Dynamic Source Routing protocol (DSR) for unicast routing in wireless ad hoc networks described in [4, 5, 7]. Even though this protocol uses some mechanisms that are defined as part of DSR, it can be implemented and used independently. In fact, this protocol does not require any unicast functionality to operate. If DSR is employed as the unicast routing protocol in an ad hoc network, adding this protocol to it requires trivial modifications. DSR is an on-demand routing protocol which allows nodes to dynamically discover a source route across multiple network hops to any destination in the ad hoc network. DSR employs two mechanisms to enable unicast routing -- Route Discovery and Route Maintenance. When a node wishes to communicate with another node, it employs Route Discovery to flood a control packet, called a Route Request, through the network, in search of a route to the destination of the communication. The Route Maintenance mechanism monitors the status of source routes in use, detects link-failures and repairs routes with broken links. Multicast and broadcast forwarding in this protocol is based on the Route Discovery mechanism of DSR. Data packets are included in Route Requests and are thereby flooded through the network. No multicast state is setup in the network for data delivery. This protocol is superior to protocols which require explicit establishment of multicast state for data distribution in certain types of networks. In small networks, this protocol requires less overhead and provides the same level of functionality. In networks with a very high degree of mobility, a stateful protocol may not be able to track the rapidly changing topology and will only contribute overhead. 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 [2]. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 1] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 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. 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. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 2] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 3. Protocol Overview 3.1. Overview of DSR DSR employs two mechanisms termed Route Discovery and Route Maintenance. Route Discovery is the mechanism whereby a node S wishing to send a packet to a destination D obtains a source route to D. Route Maintenance is the mechanism whereby S is able to detect, while using a source route to D, if the network topology has changed such that it can no longer use its route to D because a link along the route no longer works. When Route Maintenance indicates a source route is broken, S can attempt to use any other route it happens to know to D, or can invoke Route Discovery again to find a new route. When the application layer on S first starts sending data to a destination D, the DSR layer buffers the data and initiates a Route Discovery. A Route Request packet with a target of D is broadcast in the network. It is forwarded hop-by-hop outward from the node initiating the Route Discovery. When the Route Request reaches D or a node N that has a route to D, it is not forwarded on. Instead, a Route Reply packet is sent back to S. The Route Reply packet includes a full source route to the destination D. This source route is included in the source header of each data packet sent to D and enables stateless forwarding by nodes in the network who can determine whether they need to forward the packet by checking whether they are listed on the source route in the data packet's header. Data sent to D by the application layer, is buffered by DSR, until a Route Reply with a route to D is received, at which point, these packets are forwarded to D along the acquired route. A Route Requests is forwarded by a node if the node (1) is not already listed in the recorded source route in this copy of the Request, and (2) has not recently seen another Route Request packet belonging to this same Route Discovery. A node can determine if it has recently seen such a Route Request, since each Route Request packet contains a unique identifier for this Route Discovery, generated by the initiator of the Discovery. Each node maintains an LRU cache, called a Route Request Table, of the unique identifier from each recently received Route Request. By not propagating any copies of a Request after the first, the overhead of forwarding additional copies that reach this node along different paths is avoided. In addition, the Time-to-Live field in the IP header of the packet carrying the Route Request MAY be used to limit the scope over which the Request will propagate, using the normal behavior of Time-to-Live defined by IP [8, 1]. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 3] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 3.2. Overview of the Multicast and Broadcast Protocol When a node wants to send a broadcast packet, it uses the DSR Route Discovery mechanism to propagate the packet in the network. This is accomplished by including the data packet in a Route Request packet. The Route Request is flooded through the ad hoc network using the normal Route Discovery procedure described in Section 3.1, within the specified TTL of the originator. Multicast data packets are flooded through the network in the same fashion. The target of the Route Request is the multicast group address. Multicast group receivers make a copy of the data packet included in the Route Request and pass it up the protocol stack, before forwarding the Route Request onward. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 4] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 4. Detailed Operation 4.1. Originating a Packet When node A originates a packet, the following steps MUST be taken before transmitting the packet: If the destination address is a multicast or broadcast address, piggyback the data packet on a Route Request packet targeting that address. Route Request origination is described in Section 4.2. 4.2. Originating a Route Request Route Discovery is the on-demand process by which nodes actively obtain source routes to destinations to which they are actively attempting to send packets. Route Discovery is initiated for each multicast or broadcast packet by the originator of this packet as described in Section 4.1. A Route Request is transmitted with the multicast group or broadcast address as the "target" of the Route Discovery. The Route Request initialization proceeds as described in [7], except for the following condition: Route Discoveries for a multicast or broadcast address SHOULD always be permitted and SHOULD not be rate limited. 4.3. Processing a Received Route Request Option Processing of a received Route Request option, proceeds as described in [7], except for the following: If node A is a member of the multicast group indicated by Request.Target_Address, then create copy of the data packet piggybacked in the Route Request and pass it up the protocol stack before re-propagating the Route Request. Non-duplicate Route Request packets with multicast or broadcast target addresses MUST always be re-propagated. The Route Cache SHOULD NOT be consulted on behalf of Route Requests with multicast and broadcast targets. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 5] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 5. IANA Considerations This protocol does not define any new constants or packet types. It does use, however, packet types and constants defined by [7] which must be assigned by IANA. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 6] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 6. Security Considerations Security issues relevant to DSR [7] apply also to the protocol described here. This protocol does not introduce any new security considerations. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 7] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 Acknowledgments The protocol described in this draft has been designed within the Monarch Project, a research project at Rice University and Carnegie Mellon University which is developing adaptive networking protocols and protocol interfaces to allow truly seamless wireless and mobile node networking [6, 3]. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 8] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 References [1] Robert T. Braden, editor. Requirements for Internet hosts---communication layers. RFC 1122, October 1989. [2] Scott Bradner. Key words for use in RFCs to indicate requirement levels. RFC 2119, March 1997. [3] Carnegie Mellon University Monarch Project. CMU Monarch Project Home Page. Available at http://www.monarch.cs.cmu.edu/. [4] David B. Johnson. Routing in ad hoc networks of mobile hosts. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pages 158--163, December 1994. [5] David B. Johnson and David A. Maltz. Dynamic Source Routing in ad hoc wireless networks. In Mobile Computing, edited by Tomasz Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer Academic Publishers, 1996. [6] David B. Johnson and David A. Maltz. Protocols for adaptive wireless and mobile networking. IEEE Personal Communications, 3(1):34--42, February 1996. [7] David B. Johnson, David A. Maltz, Yih-Chun Hu, and Jorjeta Jetcheva. The Dynamic Source Routing protocol for mobile ad hoc networks. Internet-Draft, draft-ietf-manet-dsr-05.txt, March 2 2001. Work in progress. [8] J. B. Postel, editor. Internet Protocol. RFC 791, September 1981. Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 9] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 Chair's Address The Working Group can be contacted via its current chairs: M. Scott Corson Phone: +1 301 405-6630 Institute for Systems Research Email: corson@isr.umd.edu University of Maryland College Park, MD 20742 USA Joseph Macker Phone: +1 202 767-2001 Information Technology Division Email: macker@itd.nrl.navy.mil Naval Research Laboratory Washington, DC 20375 USA Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 10] INTERNET-DRAFT Simple Multicast and Broadcast 17 November 2000 Authors' Addresses Questions about this document can also be directed to the authors: Jorjeta Jetcheva Phone: +1 412 268-3053 Carnegie Mellon University Fax: +1 412 268-5576 Computer Science Department Email: jorjeta@cs.cmu.edu 5000 Forbes Avenue Pittsburgh, PA 15213-3891 USA Yih-Chun Hu Phone: +1 412 268-3075 Carnegie Mellon University Fax: +1 412 268-5576 Computer Science Department Email: yihchun@cs.cmu.edu 5000 Forbes Avenue Pittsburgh, PA 15213-3891 USA David A. Maltz Phone: +1 650 688-3128 AON Networks Fax: +1 650 688-3119 3045 Park Blvd. Email: dmaltz@cs.cmu.com Palo Alto, CA 94306 USA David B. Johnson Phone: +1 713 348-3063 Rice University Fax: +1 713 348-5930 Computer Science Department, MS 132 Email: dbj@cs.rice.edu 6100 Main Street Houston, TX 77005-1892 USA Jetcheva, Hu, Maltz, and Johnson Expires 20 January 2002 [Page 11]