Mobile Ad Hoc Networking Working Group Charles E. Perkins INTERNET DRAFT Nokia Research Center 29 June 2005 IP Flooding in Ad hoc Mobile Networks draft-perkins-manet-bcast-02.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@ietf.org mailing list. This document is an Internet-Draft and is subject to all provisions of section 3 of RFC 3667. 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. 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. Flooding 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 sending packets to every node in an ad hoc network. Perkins Expires 29 December 2005 [Page i] Internet Draft IP Flooding in Ad hoc Networks 29 June 2005 1. Introduction This document makes a particular specification for a well-known flooding algorithm, as it can be used to disseminate IP packets across ad hoc networks. For the well-known flooding algorithm to work, the nodes flooding packets must ensure that each distinct packet that they send is uniquely identifiable, at least during the expected time taken for the flooded packet to disseminate though an ad hoc network. In this document, the method used for insuring uniqueness depends upon whether an IPv4 or IPv6 packet is being transmitted. In IPv4, there are two kinds of broadcast address, and it seems that neither one of them is likely to present a good choice for the IP address to be used for network-layer flooding. The IPv4 address for "limited broadcast" is 255.255.255.255, and is not supposed to be forwarded. Since the nodes in an ad hoc network are asked to forward the flooded packets, the limited broadcast address should not used for network-layer flooding. The other available choice, the "directed broadcast" address, would presume a choice of routing prefix for the ad hoc network and thus is not a reasonable choice. 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. Applicability Statement The specification in this document is immediately useful for for network-layer flooding -- i.e., when the TTL or hop count in the IP header is initialized to a value greater than 1. Note that there is another useful alternative for flooding in an ad hoc network. Namely, it is often the case information to be flooded requires the attention of some application at every node receiving the flooded information, before that node would further disseminate the flooded information. For instance, a routing protocol might need to carry out several kinds of operations before allowing the packet to be retransmitted. In those cases, it may be quite appropriate (or even preferable) to use the limited broadcast address, 255.255.255.255, with the understanding that the packet will not be retransmitted at the network layer by any of the node's neighbors. This specification can be used to guarantee uniqueness for such packets even when the application makes no modification to the payload before it it is retransmitted. Perkins Expires 29 December 2005 [Page 1] Internet Draft IP Flooding in Ad hoc Networks 29 June 2005 3. Flooding In this specification, new multicast groups for flooding to all nodes of an ad hoc network are specified for use with network-layer flooding. These multicast groups are specified to contain all nodes of a contiguous ad hoc network, so that packets transmitted to the multicast address associated with the group will be delivered to all nodes as desired. In other words, any node that is reachable, is automatically granted membership in these multicast groups. For IPv6, the multicast address is specified to be "site-local". The names of the multicast groups are given as "ALL_IPv4_MANET_NODES" (TBD) and "ALL_IPv6_MANET_NODES" (TBD). This document does not specify transmissions to any directed broadcast address. Every node maintains a list of those flooded packets which have already been received and retransmitted. The list contains, for each distinct flooded packet received, a value called the Flooded Packet Identifier (FPI). For IPv4, this FPI is composed of the source IP address, the IP ident value, and the fragment offset values obtained from the IP header of the flooded packet. For IPv6, the FPI is calculated as specified in section 4. When a node receives a flooded packet, it checks its list for the FPI of the flooded packet's IP header [3]. If there is such a list entry with matching FPI, the node silently discards the flooded packet since it has already been received and forwarded. The node then checks to see whether it is enabled for retransmitting flooded packets. By default, all nodes in the ad hoc network are so enabled; however, this is not required (see section 6) and may be changed by configuration or by protocol action. If the node is not enabled for retransmitting flooded packets, it takes no further action. If there is no existing list entry containing the same FPI, and if the node has been enabled to forward flooded packets, the node retransmits the packet. List entries SHOULD be kept for at least BROADCAST_RECORD_TIME before the node expunges the record. BROADCAST_RECORD_TIME is a configurable parameter, but it MUST be at least equal to NET_TRAVERSAL_TIME. 4. FPI computation for IPv6 DISCUSSION QUESTION: Is another cryptographic function better, or good enough but easier? To obtain the FPI for IPv6 packets, a node uses MD5 [4] to perform the following calculation for the incoming flooded packet: Perkins Expires 29 December 2005 [Page 2] Internet Draft IP Flooding in Ad hoc Networks 29 June 2005 FPI = MD5 (IPv6 packet data). The IP packet data includes all unpredictable IPv6 headers and extensions [2], as well as any higher-level protocol data. The source node for each flooded packet MUST ensure that this FPI is distinct from the FPI from every other flooded packet which the node has transmitted during the last BROADCAST_RECORD_TIME. In the unlikely event that the FPI value is identical to some such recently transmitted packet, the source node MUST add a Unique Identifier Destination Option to the flooded packet (see section 5). DISCUSSION QUESTION: Should the same digestifying procedure be specified for IPv4 also? 5. Unique Identifier Destination Option DISCUSSION QUESTION: The IPv6 fragment header can serve this purpose very well, at a cost of only another two bytes. Should that be used instead of the Unique Identifier 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 flooded packet FPI computation different than that for any other flooded packet from the same source node. The Unique Identifier MUST be placed in the Destination Options before the Routing Header (and, thus, before the fragment header). This allows proper handling by all intermediate forwarding nodes. Perkins Expires 29 December 2005 [Page 3] Internet Draft IP Flooding in Ad hoc Networks 29 June 2005 6. Selective Retransmission for Flooded Packets By default, each node in the ad hoc network is enabled to retransmit each distinct flooded 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 flooding. 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 compliant with the flooding protocol specified in this document. 7. Configuration Parameters This section gives default values for some important values associated with flooding 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 flooding operation. Parameter Name Value ---------------------- ----- BROADCAST_RECORD_TIME 2 * NET_TRAVERSAL_TIME NET_DIAMETER 35 NODE_TRAVERSAL_TIME 40 milliseconds 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, medium access delays, and propagation delays. NET_TRAVERSAL_TIME is a conservative estimate of how long it should take for a message to traverse the entire ad hoc network. 8. Security Considerations This draft specifies a general mechanism for flooding packets in an ad hoc network. It does not make any provision for securing the contents of the flooded data, either to protect against tampering or to protect against unauthorized inspection of the data. Perkins Expires 29 December 2005 [Page 4] Internet Draft IP Flooding in Ad hoc Networks 29 June 2005 9. Acknowledgments This flooding 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. 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] S. Kent and R. Atkinson. IP Authentication Header. Request for Comments (Proposed Standard) 2402, Internet Engineering Task Force, November 1998. [3] J. Postel. Internet Protocol. Request for Comments (Standard) 791, Internet Engineering Task Force, September 1981. [4] R. Rivest. The MD5 Message-Digest Algorithm. Request for Comments (Informational) 1321, Internet Engineering Task Force, April 1992. A. Changes since the last revision - Added applicability section. - Changed author list - Added discussion points - Moved some text out of the introduction into the main body of the specification. - Othe minor editorial corrections. Author's Addresses Questions about this memo can be directed to: Charles E. Perkins Networking Technology Laboratory / Nokia Research Center 313 Fairchild Drive Mountain View, CA 94303 +1 650 625 2986 +1 650 625-2502 (fax) Charles.Perkins@nokia.com Perkins Expires 29 December 2005 [Page 5] Internet Draft IP Flooding in Ad hoc Networks 29 June 2005 Intellectual Property Statement 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 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. Disclaimer of Validity 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 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. Copyright Statement Copyright (C) The Internet Society (2005). 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. Perkins Expires 29 December 2005 [Page 6]