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]