Mobile Ad Hoc Networking Working Group Charles E. Perkins INTERNET DRAFT Nokia Research Center 14 November 2000 Elizabeth M. Royer University of California, Santa Barbara Samir R. Das University of Cincinnati IP Broadcast in Ad hoc Mobile Networks draft-perkins-manet-bcast-01.txt Status of This Memo This document is a submission by the Mobile Ad Hoc Networking Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the manet@itd.nrl.navy.mil mailing list. Distribution of this memo is unlimited. This document is an Internet-Draft and is in full conformance with 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. Abstract An ad hoc mobile network is a collection of nodes, each of which communicates over wireless channels and is capable of movement. Nodes participating in such an ad hoc network communicate on a peer-to-peer basis. Broadcast is often a desired form of communication in these networks, as it can enable both the dissemination of control information and the delivery of data packets. This document describes a method for providing broadcast communication in ad hoc networks. Perkins, Royer, Das Expires 14 May 2001 [Page i] Internet Draft IP Broadcast in Ad hoc Networks 14 November 2000 1. Introduction This document makes a particular specification for a classical broadcast algorithm, as it can be used to disseminate IP packets across ad hoc networks. Broadcast is needed in many circumstances; in particular, it is useful for the kind of route discovery operations that are required for on-demand route acquisition in several candidate manet protocols. This protocol specification works when the nodes sending broadcast packets ensure that each distinct broadcast packet that they send is tagged with a distinct value in the ident field of the IP header. 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 [1]. 2. Broadcast For the purposes of this document, the IPv4 broadcast address is 255.255.255.255. The analogous address for IPv6 system-wide broadcast is the site-local All Routers multicast address (FF05::0002). This document does not specify transmissions to any directed broadcast address. Every node maintains a list to keep track of which broadcast packets have already been received and retransmitted. The list contains, for each distinct broadcast packet received, a value called the Broadcast Packet Identifier (BPI). For IPv4, this BPI is composed of the source IP address, the IP ident value, and the fragment offset values obtained from the IP header of the broadcast packet. For IPv6, the BPI is calculated as specified in section 3. When a node receives a broadcast packet, it checks its list for the BPI of the broadcast packet's IP header [2]. If there is such a list entry with matching BPI, the node silently discards the broadcast packet since it has already been received. The node then checks to see whether it is enabled for retransmitting broadcast packets. By default, all nodes in the ad hoc network are so enabled; however, this is not required (see section 5). If the node is not enabled for retransmitting broadcasts, it takes no further action. If there is no existing list entry containing the same BPI, and if the node has been enabled to forward broadcast packets, the node retransmits the broadcast packet. List entries SHOULD be kept for at least BROADCAST_RECORD_TIME before the node expunges the record. BROADCAST_RECORD_TIME Perkins, Royer, Das Expires 14 May 2001 [Page 1] Internet Draft IP Broadcast in Ad hoc Networks 14 November 2000 is a configurable parameter, but it MUST be at least equal to NET_TRAVERSAL_TIME. 3. BPI computation for IPv6 To obtain the BPI for IPv6 packets, a node uses MD5 [3] to perform the following calculation for the incoming broadcast packet: BPI = MD5 (IPv6 packet data). The IP packet data includes all non-mutable IPv6 headers and extensions, as well as any higher-level protocol data. The source node for each broadcast MUST ensure that this BPI is distinct from the BPI from every other broadcast packet which the node has transmitted during the last BROADCAST_RECORD_TIME. In the unlikely event that the BPI value is identical to some such recently transmitted packet, the source node MUST add a Unique Identifier Destination Option to the broadcast packet (see section 4). 4. Unique Identifier Destination Option The Unique Identifier option is encoded in type-length-value (TLV) format 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 | Option Length | Uniquifying Value | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Type TBD Option Length 2 Uniquifying Value The 16-bit Uniquifying Value is chosen to make the broadcast packet BPI computation different than that for any other broadcast packet from the same source node. Perkins, Royer, Das Expires 14 May 2001 [Page 2] Internet Draft IP Broadcast in Ad hoc Networks 14 November 2000 5. Selective Broadcast Retransmission By default, each node in the ad hoc network is enabled to retransmit each distinct broadcast packet that it receives. However, in some cases, there may be additional control signaling in place that is used to reduce the number of nodes that perform this retransmission, in order to reduce the overall bandwidth consumption and congestion which can be caused by excessive broadcast. This document does not specify any such control protocol to disable or enable such node selection. However, an ad hoc network which employs such a node selection protocol can still be considered to be compliant with the broadcast protocol specified in this document. 6. Configuration Parameters This section gives default values for some important values associated with broadcast operations. Mobile nodes in particular ad hoc networks may wish to change certain of the parameters, in particular the NET_DIAMETER and NODE_TRAVERSAL values. Choice of these parameters may affect the robustness of the broadcast operation. Parameter Name Value ---------------------- ----- BROADCAST_RECORD_TIME 2 * NET_TRAVERSAL_TIME NET_DIAMETER 35 NODE_TRAVERSAL_TIME 40 NET_TRAVERSAL_TIME 3 * NODE_TRAVERSAL_TIME * NET_DIAMETER / 2 NET_DIAMETER measures the maximum possible number of hops between two nodes in the network. NODE_TRAVERSAL_TIME is a conservative estimate of the average one hop traversal time for packets and should include queuing delays, interrupt processing times and transfer times. NET_TRAVERSAL_TIME is a conservative estimate of how long it should take for a message to traverse the entire ad hoc network. 7. Security Considerations This draft specifies a general mechanism for handling broadcast. It does not make any provision for securing the contents of the broadcast data, either to protect against tampering or to protect against unauthorized inspection of the data. Perkins, Royer, Das Expires 14 May 2001 [Page 3] Internet Draft IP Broadcast in Ad hoc Networks 14 November 2000 8. Acknowledgments This broadcast method is a codification of a well known algorithm which has been assumed for general use in various ad hoc protocols. Thus, the protocol specification in this draft should be considered the joint work of many engineers who have worked on producing ad hoc network protocols. The authors of this draft hope that we have been able to faithfully and usefully represent the work of these many engineers. References [1] S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. Request for Comments (Best Current Practice) 2119, Internet Engineering Task Force, March 1997. [2] J. Postel. Internet Protocol. Request for Comments (Standard) 791, Internet Engineering Task Force, September 1981. [3] R. Rivest. The MD5 Message-Digest Algorithm. Request for Comments (Informational) 1321, Internet Engineering Task Force, April 1992. Perkins, Royer, Das Expires 14 May 2001 [Page 4] Internet Draft IP Broadcast in Ad hoc Networks 14 November 2000 Author's Addresses Questions about this memo can be directed to: Charles E. Perkins Communications Systems Laboratory / Nokia Research Center 313 Fairchild Drive Mountain View, CA 94303 +1 650 625 2986 +1 650 625-2502 (fax) charliep@iprg.nokia.com Elizabeth M. Royer Dept. of Electrical and Computer Engineering University of California, Santa Barbara Santa Barbara, CA 93106 +1 805 893 7788 +1 805 893 3262 (fax) eroyer@alpha.ece.ucsb.edu Samir R. Das Dept. of Electrical and Computer Engineering & Computer Science University of Cincinnati Cincinnati, OH 45221-0030 +1 513 556 2594 +1 513 556 7326 (fax) sdas@ececs.uc.edu Perkins, Royer, Das Expires 14 May 2001 [Page 5]