Internet DRAFT - draft-perkins-manet-smurf
draft-perkins-manet-smurf
Mobile Ad Hoc Networking Working Group Charles E. Perkins
INTERNET DRAFT Nokia Research Center
8 July 2006 Thomas Clausen,
Philippe Jacquet
INRIA Rocquencourt, France
Multicast With Minimal Congestion Using Connected Dominating Sets
draft-perkins-manet-smurf-00.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
Flooding is useful for many reasons in ad hoc networks, but
causes congestion that can block traffic. Selecting multi-point
relays (MPRs) reduces congestion due to flooding, but has several
disadvantages. It is possible to select a subset of the MPRs to
do the same job more effectively. In this document, signaling is
specified for identifying a relatively small connected dominating set
that can still manage the flooding operation.
Perkins Expires 8 January 2006 [Page 1]
Internet Draft Low-Congestion Flooding 8 July 2006
1. Introduction
Flooding is useful for many reasons in ad hoc networks, but causes
congestion that can block traffic within such a network. The goal
of this document is to specify a flooding algorithm that greatly
reduces the number of packet retransmissions needed to flood the
whole network. Since there a many fewer retransmissions, the amount
of congestion due to flooding will be greatly reduced.
In order to reduce the total number of retransmissions, we can reduce
the number of nodes that perform the retransmissions, as long as
all nodes still receive at least one transmission of the flooded
packet. If a particular node can determine its one-hop and two-hop
neighborhoods, then it can identify a subset of its neighboring nodes
that still be able to reach every node of the two-hop neighborhood.
The nodes in such a subset are called "multi-point relays" (MPRs)
in the OLSR specification [7]. There are various ways to pick
enough MPRs so that, when each MPR retransmits a packet, the two-hop
neighborhood will be completely covered. These neighboring MPRs will
themselves have selected some of their other neighbors to be MPRs.
When the neighboring MPRs retransmit, then some of their neighbors
will again retransmit, until eventually the whole network is covered.
Selecting multi-point relays MPRs, as specified in OLSR [7] is
beneficial to reduce congestion due to flooding, but has several
disadvantages. Another related concept is that of a "connected
dominating set" (CDS). There are many distributed algorithms for
computing a CDS, with a variety of interesting properties. The set
of MPRs that retransmit a packet originated from a source node within
an ad hoc network is also a CDS. Otherwise, the set of MPRs would not
be able to cover the network by retransmission hop-by-hop.
In this document, signaling is specified for identifying a relatively
small connected dominating set that can still manage the flooding
operation.
The names of the multicast groups used for flooding are given as
"ALL_IPv4_MANET_NODES" and "ALL_IPv6_MANET_NODES" [5]. The backbone
nodes selected for flooding packets can, however, be used for
flooding to any designated multicast address as long as the members
of that multicast group form a connected subgraph of the ad hoc
network. Specifications for future multicast groups intended for
flooding or very dense dissemination should specifically indicate
that their members should communicate across the SMURF backbone.
Future documents may offer improved algorithms for the purpose of
identifying backbone nodes, while still utilizing the protocol in
this document for periodic updates to the necessary neighborhood
information.
Perkins Expires 8 January 2006 [Page 2]
Internet Draft Low-Congestion Flooding 8 July 2006
DISCUSSION: should there be a version field to handle
unforeseen future incompatibilities?
2. SMURF Terminology
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].
This section defines other terminology that is not already defined
in [3].
MPR
A "multi-point relay" -- that is, a neighboring node that can
relay flooded packets, thus assisting with the dissemination of
those packets throughout the network
broadcast
Transmit to the IPv4 Limited Broadcast address,
255.255.255.255, or else for IPv6 to the link-local
AllNodesMulticast address.
neighborhood, one-hop neighborhood
The neighborhood (also called the one-hop neighborhood) of a
node is the set of nodes which are directly reachable by that
node.
two-hop neighborhood
The two-hop neighborhood of a node is the set of nodes which
are either directly reachable by that node, or directly
reachable by one of the neighbors of that node.
dominating set
A subset of a graph is a dominating set if every node in the
graph is eiher a member of the subset, or else a neighbor of at
least one node in the subset.
connected set
A set with more than one element is connected if every node in
the subset is a neighbor of some other node in the subset. A
set with fewer than two elements is connected.
Perkins Expires 8 January 2006 [Page 3]
Internet Draft Low-Congestion Flooding 8 July 2006
CDS (connected dominating set)
A subset of a graph is a CDS if it is a dominating set, and it
is connected.
flooding backbone
The flooding backbone of an ad hoc network is a CDS which is
used for flooding packets throughout the network, considering
every node in the ad hoc network as a node in a graph with
edges defined by the (one-hop) communication links that are
available between the nodes in the ad hoc network.
backbone
in this document, ``backbone'' always means the flooding
backbone
3. Overview
Each node listens for advertisements from its neighbors. From the
advertisements, the node updates its stored information about its
one-hop neighborhood and its two-hop neighborhood. The sender of
the advertisement is a member of the node's one-hop neighborhood,
and the sender's neighbors are either members of the node's one-hop
neighborhood or its two-hop neighborhood.
There are two kinds of periodic local topology advertisements,
which are used to enable each node to construct a representation
of its two-hop neighborhood and subsequently select MPRs. The
first is called the "full advertisement", which has complete lists
of all the necessary data. The second is called the "incremental
advertisement", which only has information that has changed since
the last full advertisement. It is expected that the incremental
advertisement will be much smaller than the full advertisement.
A node's neighborhood is considered to be composed of three mutually
exclusive subsets:
- undistinguished first hop neighbors
- MPRs
- the node itself
Likewise, a node's two hop neighborhood is considered to be composed
of four mutually exclusive subsets:
- second hop neighbors
- undistinguished first hop neighbors
Perkins Expires 8 January 2006 [Page 4]
Internet Draft Low-Congestion Flooding 8 July 2006
- MPRs
- the node itself
If a node is described as being in any one of these subsets, then
by convention and agreement it does not belong to any of the other
subsets. This eliminates overlap of information in the local
topology advertisements.
The following information is present in full advertisements:
- advertisement sequence number
- reluctance for offering service as a backbone node
- first hop neighbors
- MPRs
- flags
The following information is present in incremental advertisements:
- advertisement sequence number of the last full advertisement
- reluctance for offering service as a backbone node
- addresses of new first hop neighbors
- addresses of new MPRs
- addresses of lost nodes
- flags
Any address in the lost node list has to be deleted from the neighbor
list or the MPR list of the last full advertisement, and the nodes in
these two lists reclassified if they were classified differently in
the last full advertisement.
A neighboring node cannot be considered for selection as an MPR until
the link to that node has been verified as bidirectional. For each
neighbor, two conditions must be verified:
1. an advertisement has been recently heard from the neighbor
2. the node itself must appear as a member of the one-hop neighbors
reported by that neighbor.
Once each node has constructed its two-hop neighborhood, it uses
any reasonable algorithm to identify a subset of neighbors which
are to be designated as MPRs. One algorithm that works well is the
so-called "greedy algorithm":
1. Initialize the set of uncovered two-hop neighbors to contain all
known two-hop neighbors
2. Pick the neighbor that is within range of the largest number of
uncovered nodes in the two-hop neighborhood.
Perkins Expires 8 January 2006 [Page 5]
Internet Draft Low-Congestion Flooding 8 July 2006
3. Mark the two-hop neighbors reachable by that neighbor's local
broadcasts as already covered.
4. If there are no more uncovered two-hop neighbors, stop.
5. Otherwise, iterate steps (2) -- (4).
Once the nodes have identified the MPRs in their neighborhoods, each
node must also determine whether to prune itself from the flooding
backbone (i.e., the connected dominating set of nodes which will take
responsibility for disseminating flooded data).
In order for a node to prune itself to the flooding backbone, it uses
the following algorithm [1]:
1. It forms a "CDS identifier" by appending its IP address to its
last advertised "reluctance" value.
2. If it is the node with a CDS identifier lower than any of its
neighbors, then it must continue to participate as a member of
the flooding backbone.
3. Otherwise, if it not a MPR of its neighbor with the lowest CDS
identifier, then it may prune itself from the flooding backbone.
A node advertises the status of its decision to prune itself from the
CDS backbone in its advertisement messages.
4. Full Advertisement
The Full Advertisement has the following format:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence # |Rel| #1-hop | #MPRs | reserved|C|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: List of IP addresses of 1-hop neighbors :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: List of IP addresses of MPR neighbors :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
Type == 1.
Perkins Expires 8 January 2006 [Page 6]
Internet Draft Low-Congestion Flooding 8 July 2006
Length
Length of the full advertisement data, in bytes, including all
fields except for the Type and Length.
Sequence #
Advertisement sequence number
Rel
Reluctance (2 bits). A node selects a low value for its
reluctance, if it is willing to be identified as an MPR, and
thus potentially as a member of the connected dominating set.
#1-hop
Number of one-hop neighbors
#MPRs
Number of one-hop neighbors reclassified as MPRs
'C'
The 'C' flag is set if the advertising node has selected itself
as a member of the connecting dominating set for flooding
1-hop list
List of IP addresses of 1-hop neighbors (#1-hop total
addresses)
MPR list
List of IP addresses of MPR neighbors (#MPRs total addresses)
The IP header TTL for the Full Advertisement packet MUST be 1.
DISCUSSION: is 255 better?
DISCUSSION: Is the Length field needed, or should we spend
the bits on enlarging the other fields?
5. Incremental Advertisement
The Incremental Advertisement has the following format:
Perkins Expires 8 January 2006 [Page 7]
Internet Draft Low-Congestion Flooding 8 July 2006
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence # |Rel| #1-hop|#MPRs| #lost |reservd|C|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: List of IP addresses of 1-hop neighbors :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: List of IP addresses of MPR neighbors :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: List of IP addresses of lost neighbors :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
Type == 2.
Length
Length of the incremental advertisement data, in bytes,
including
Sequence #
Advertisement sequence number
Rel
Reluctance (2 bits). A node selects a low value for its
reluctance, if it is willing to be identified as an MPR, and
thus potentially as a member of the connected dominating set.
#1-hop
Number of new one-hop neighbors
#MPRs
Number of new nodes classified as MPRs
#lost
Number of nodes no longer in the one-hop neighborhood
(and, thus, not possibly MPRs) as shown in the last full
advertisement
Perkins Expires 8 January 2006 [Page 8]
Internet Draft Low-Congestion Flooding 8 July 2006
'C'
The 'C' flag is set if the advertising node has selected itself
as a member of the connecting dominating set for flooding
1-hop list
List of IP addresses of new 1-hop neighbors (#1-hop total
addresses)
MPR list
List of IP addresses of new MPR neighbors (#MPRs total
addresses)
lost list
List of IP addresses of former neighbors that have not
exhibited local connectivity recently (#lost total addresses)
The IP header TTL for the Incremental Advertisement MUST be 1.
DISCUSSION: is 255 better?
DISCUSSION: Is the Length field needed, or should we spend
the bits on enlarging the other fields?
6. Security Considerations
This draft specifies a general mechanism for identifying a flooding
backbone 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.
It does not make any provision for ensuring that the nodes of the
flooding backbone are operating as expected. It does not make any
provision to guarantee the correctness of information presented
within the advertisement messages. The use of local broadcast for
the advertisement messages precludes the use of point-to-point
security associations such as might be used for constructing
Authentication Header digests.
In the future, if further security measures are to be undertaken,
one could attempt to utilize public keys for the purpose of
authenticating the flooded data, as long as the public keys were
known to be properly associated with the node in question (to avoid
man-in-the-middle attacks).
Perkins Expires 8 January 2006 [Page 9]
Internet Draft Low-Congestion Flooding 8 July 2006
7. IANA considerations
New multicast addresses have to be allocated. A new UDP port number
has to be allocated for the neighborhood messages. ICMP is another
possibility.
8. Acknowledgments
Thomas Clausen and Emmanuel Baccelli were frequent contributors to
the conversation which inspired the production of this document. The
algorithm for identifying the flooding backbone was published as
Research Report 4597 [1] by Cedric Adjih et al.
References
[1] Cedric Adjih, Phlippe Jacquet, and Laurent Veinnot. Computing
Connected Dominating Sets with Multipoint Relays. Technical
report, Institut National de Recherche en Informatique et en
Automatique (INRIA). INRIA RR 4597, October 2002.
[2] 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.
[3] Ed. J. Manner and Ed. M. Kojo. Mobility Related Terminology.
Request for Comments (Informational) 3753, Internet Engineering
Task Force, June 2004.
[4] C. Perkins. Minimal Encapsulation within IP. Request for
Comments (Proposed Standard) 2004, Internet Engineering Task
Force, October 1996.
[5] Charles E. Perkins. IP Flooding in Ad hoc Networks (Work In
Progress). Internet Draft, Internet Engineering Task Force.
draft-perkins-manet-bcast-02.txt, June 2005.
[6] J. Postel. Internet Protocol. Request for Comments (Standard)
791, Internet Engineering Task Force, September 1981.
[7] Ed. T. Clausen and Ed. P. Jacquet. Optimized Link State Routing
Protocol (OLSR). Request for Comments (Experimental Protocol)
3626, Internet Engineering Task Force, June 2004.
Author's Addresses
Questions about this memo can be directed to:
Perkins Expires 8 January 2006 [Page 10]
Internet Draft Low-Congestion Flooding 8 July 2006
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
Thomas Heide Clausen
INRIA Rocquencourt, BP 105,
78153 Le Chesnay Cedex
France
+33 1 3963 5133
Thomas.Clausen@inria.fr
Full Copyright Statement
Full 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.
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.
Perkins Expires 8 January 2006 [Page 11]
