Request for Comments: 3684 SRI International
Category: Experimental F. Templin
Nokia
M. Lewis
SRI International
February 2004
Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)
Status of this Memo
This memo defines an Experimental Protocol for the Internet
community. It does not specify an Internet standard of any kind.
Discussion and suggestions for improvement are requested.
Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract
Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) is a
proactive, link-state routing protocol designed for mobile ad-hoc
networks, which provides hop-by-hop routing along shortest paths to
each destination. Each node running TBRPF computes a source tree
(providing paths to all reachable nodes) based on partial topology
information stored in its topology table, using a modification of
Dijkstra’s algorithm. To minimize overhead, each node reports only
*part* of its source tree to neighbors. TBRPF uses a combination of
periodic and differential updates to keep all neighbors informed of
the reported part of its source tree. Each node also has the option
to report additional topology information (up to the full topology),
to provide improved robustness in highly mobile networks. TBRPF
performs neighbor discovery using "differential" HELLO messages which
report only *changes* in the status of neighbors. This results in
HELLO messages that are much smaller than those of other link-state
routing protocols such as OSPF.
Table of Contents
1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements. . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Applicability Section . . . . . . . . . . . . . . . . . . . . 5
5. TBRPF Overview. . . . . . . . . . . . . . . . . . . . . . . . 6
5.1. Overview of Neighbor Discovery . . . . . . . . . . . . 6
5.2. Overview of the Routing Module. .. . . . . . . . . . . 8
6. TBRPF Packets . . . . . . . . . . . . . . . . . . . . . . . . 10
6.1. TBRPF Packet Header. . . . . . . . . . . . . . . . . . 10
6.2. TBRPF Packet Body. . . . . . . . . . . . . . . . . . . 11
6.2.1. Padding Options (TYPE = 0 thru 1). . . . . . . 12
6.2.2. Messages (TYPE = 2 thru 10). . . . . . . . . . 13
7. TBRPF Neighbor Discovery. . . . . . . . . . . . . . . . . . . 13
7.1. HELLO Message Format . . . . . . . . . . . . . . . . . 13
7.2. Neighbor Table . . . . . . . . . . . . . . . . . . . . 14
7.3. Sending HELLO Messages . . . . . . . . . . . . . . . . 15
7.4. Processing a Received HELLO Message. . . . . . . . . . 16
7.5. Expiration of Timer nbr_life . . . . . . . . . . . . . 18
7.6. Link-Layer Failure Notification. . . . . . . . . . . . 18
7.7. Optional Link Metrics. . . . . . . . . . . . . . . . . 18
7.8. Configurable Parameters. . . . . . . . . . . . . . . . 19
8. TBRPF Routing Module. . . . . . . . . . . . . . . . . . . . . 19
8.1. Conceptual Data Structures . . . . . . . . . . . . . . 19
8.2. TOPOLOGY UPDATE Message Format . . . . . . . . . . . . 21
8.3. Interface, Host, and Network Prefix Association
Message Formats. . . . . . . . . . . . . . . . . . . . 23
8.4. TBRPF Routing Operation. . . . . . . . . . . . . . . . 24
8.4.1. Periodic Processing. . . . . . . . . . . . . . 24
8.4.2. Updating the Source Tree and Topology
Graph. . . . . . . . . . . . . . . . . . . . . 25
8.4.3. Updating the Routing Table . . . . . . . . . . 26
8.4.4. Updating the Reported Node Set . . . . . . . . 27
8.4.5. Generating Periodic Updates. . . . . . . . . . 29
8.4.6. Generating Differential Updates. . . . . . . . 29
8.4.7. Processing Topology Updates. . . . . . . . . . 30
8.4.8. Expiring Topology Information. . . . . . . . . 32
8.4.9. Optional Reporting of Redundant Topology
Information. . . . . . . . . . . . . . . . . . 32
8.4.10. Local Topology Changes . . . . . . . . . . . . 33
8.4.11. Generating Association Messages. . . . . . . . 34
8.4.12. Processing Association Messages. . . . . . . . 36
8.4.13. Non-Relay Operation. . . . . . . . . . . . . . 37
8.5. Configurable Parameters. . . . . . . . . . . . . . . . 38
9. TBRPF Flooding Mechanism. . . . . . . . . . . . . . . . . . . 38
10. Operation of TBRPF in Mobile Ad-Hoc Networks. . . . . . . . . 39
10.1. Data Link Layer Assumptions. . . . . . . . . . . . . . 39
10.2. Network Layer Assumptions. . . . . . . . . . . . . . . 39
10.3. Optional Automatic Address Resolution. . . . . . . . . 40
10.4. Support for Multiple Interfaces and/or
Alias Addresses. . . . . . . . . . . . . . . . . . . . 40
10.5. Support for Network Prefixes . . . . . . . . . . . . . 40
10.6. Support for non-MANET Hosts. . . . . . . . . . . . . . 40
10.7. Internet Protocol Considerations . . . . . . . . . . . 41
10.7.1. IPv4 Operation . . . . . . . . . . . . . . . . 41
10.7.2. IPv6 Operation . . . . . . . . . . . . . . . . 41
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 41
12. Security Considerations . . . . . . . . . . . . . . . . . . . 42
13. Acknowledgements. . . . . . . . . . . . . . . . . . . . . . . 42
14. References. . . . . . . . . . . . . . . . . . . . . . . . . . 42
14.1. Normative References . . . . . . . . . . . . . . . . . 42
14.2. Informative References . . . . . . . . . . . . . . . . 43
Authors’ Addresses. . . . . . . . . . . . . . . . . . . . . . . . 45
Full Copyright Statement. . . . . . . . . . . . . . . . . . . . . 46
1. Introduction
Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) is a
proactive, link-state routing protocol designed for mobile ad-hoc
networks (MANETs), which provides hop-by-hop routing along shortest
paths to each destination. Each node running TBRPF computes a source
tree (providing shortest paths to all reachable nodes) based on
partial topology information stored in its topology table, using a
modification of Dijkstra’s algorithm. To minimize overhead, each
node reports only *part* of its source tree to neighbors.
TBRPF uses a combination of periodic and differential updates to keep
all neighbors informed of the reported part of its source tree. Each
node also has the option to report addition topology information (up
to the full topology), to provide improved robustness in highly
mobile networks.
TBRPF performs neighbor discovery using "differential" HELLO messages
which report only *changes* in the status of neighbors. This results
in HELLO messages that are much smaller than those of other link-
state routing protocols such as OSPF [6].
TBRPF consists of two modules: the neighbor discovery module and the
routing module (which performs topology discovery and route
computation). An overview of these modules is given in Section 5.
2. Requirements
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL", when
they appear in this document, are to be interpreted as described in
BCP 14, RFC 2119 [1].
This document also makes use of internal conceptual variables to
describe protocol behavior and external variables that an
implementation must allow system administrators to change. The
specific variable names, how their values change, and how their
settings influence protocol behavior are provided to demonstrate
protocol behavior. An implementation is not required to have them in
the exact form described here, so long as its external behavior is
consistent with that described in this document.
3. Terminology
The following terms are used to describe TBRPF:
node
A router that implements TBRPF.
router ID
Each node is identified by a unique 32-bit router ID (RID), which
for IPv4 is typically equal to the IP address of one of its
interfaces. The term "node u" denotes the node whose RID is equal
to u.
interface
A node’s attachment to a communication facility or medium through
which it can communicate with other nodes. A node can have
multiple interfaces. An interface can be wireless or wired, and
can be broadcast (e.g., Ethernet) or point-to-point. Each
interface is identified by its IP address. The term "interface I"
denotes the interface whose IP address is I.
link
A link is an ordered pair of interfaces (I,J) where I and J are on
two different nodes, and where interface I has recently received
packets sent from interface J. A link (i,j) from node i to node j
is said to exist if node i has an interface I and node j has an
interface J such that (I,J) is a link. Nodes i and j are called
the "tail" and "head" of the link, respectively.
bidirectional link
A link (I,J) such that interfaces I and J can both hear each
other. Also called a 2-way link.
neighbor node
A node j is said to be a neighbor of node i if node i can hear
node j on some interface. Node j is said to be a 2-way neighbor
if there is a bidirectional link between i and j.
MANET interface
Any wireless interface such that two neighbor nodes on the
interface need not be neighbors of each other. MANET nodes
typically have at least one MANET interface, but this is not a
requirement.
topology
The topology of the network is described by a graph G = (V, E),
where V is the set of nodes u and E is the set of links (u,v) in
the network.
source tree
The directed tree (denoted T) computed by each node that provides
shortest paths to all other reachable nodes.
topology update
A message that reports the state of one or more links.
parent
The parent of node i for node u is the next node on the computed
shortest path from node i to node u.
predecessor
The predecessor of a node v on the source tree is the node u such
that the link (u,v) is in the source tree.
leaf node
A leaf node of the source tree is a node on the source tree that
is not the predecessor of any other node on the source tree.
proactive routing protocol
A routing protocol in which each node maintains routes to all
reachable destinations at all times, whether or not there is
currently any need to deliver packets to those destinations. In
contrast, an "on-demand" routing protocol discovers and maintains
routes only when they are needed.
4. Applicability Section
TBRPF is a proactive routing protocol designed for mobile ad-hoc
networks (MANETs). It can support networks with up to a few hundred
nodes, and can be combined with hierarchical routing techniques to
support much larger networks. Because it employs techniques to
greatly reduce control traffic, TBRPF can support much larger and
denser networks than routing protocols based on the classical link-
state algorithm (e.g., OSPF).
The number of nodes that can be supported depends on several factors,
including the MAC data rate, the rate of topology changes, and the
network density (average number of neighbors). Simulations have been
reported in which TBRPF has supported as many as 500 nodes. In
simulations with 100 nodes and 20 traffic streams (sources), using
IEEE 802.11 with a data rate of 2 Mbps, TBRPF was found to generate
approximately 80-120 kb/s of routing control traffic for the
scenarios considered, which compared favorably with other MANET
routing protocols [7][8]. A proof of correctness for TBRPF can be
found in references [8] and [9].
5. TBRPF Overview
TBRPF consists of two main modules: the neighbor discovery module,
and the routing module (which performs topology discovery and route
computation).
5.1. Overview of Neighbor Discovery
The TBRPF Neighbor Discovery (TND) protocol allows each node i to
quickly detect the neighbor nodes j such that a bidirectional link
(I,J) exists between an interface I of node i and an interface J of
node j. The protocol also quickly detects when a bidirectional link
breaks or becomes unidirectional.
The key feature of TND is that it uses "differential" HELLO messages
which report only *changes* in the status of links. This results in
HELLO messages that are much smaller than those of other link-state
routing protocols such as OSPF, in which each HELLO message includes
the IDs of *all* neighbors. As a result, HELLO messages can be sent
more frequently, which allows faster detection of topology changes.
TND is designed to be fully modular and independent of the routing
module. TND performs ONLY neighbor sensing, i.e., it determines
which nodes are (1-hop) neighbors. In particular, it does not
discover 2-hop neighbors (which is handled by the routing module).
As a result, TND can be used by other routing protocols, and TBRPF
can use another neighbor discovery protocol in place of TND, e.g.,
one provided by the link layer.
Nodes with multiple interfaces run TND separately on each interface,
similar to OSPF. Thus, a neighbor table is maintained for each local
interface, and a HELLO sent on a particular interface contains only
information regarding neighbors heard on that interface.
We note that, in wireless networks, it is possible for a single
interface I to receive packets from multiple interfaces J associated
with the same neighbor node. This could happen, for example, if the
neighbor uses a directional antenna with different interfaces
representing different beams. For this reason, TBRPF includes
neighbor interface addresses in HELLO messages, unlike OSPF, which
includes only router IDs in HELLO packets.
Each TBRPF node maintains a neighbor table for each local interface
I, which stores state information for each neighbor interface J heard
on that interface, i.e., for each link (I,J) between interface I and
a neighbor interface J. The status of each link can be 1-WAY, 2-WAY,
or LOST. The neighbor table for interface I determines the contents
of HELLO messages sent on interface I, and is updated based on HELLO
messages received on interface I (and possibly on link-layer
notifications).
Each TBRPF node sends (on each interface) at least one HELLO message
per HELLO_INTERVAL. Each HELLO message contains three (possibly
empty) lists of neighbor interface addresses (which are formatted as
three message subtypes): NEIGHBOR REQUEST, NEIGHBOR REPLY, and
NEIGHBOR LOST. Each HELLO message also contains the current HELLO
sequence number (HSEQ), which is incremented with each transmitted
HELLO.
In the following overview of the operation of TND, we assume that
interface I belongs to node i, and interface J belongs to node j.
When a node i changes the status of a link (I,J), it includes the
neighbor interface address J in the appropriate list (NEIGHBOR
REQUEST/REPLY/LOST) in at most NBR_HOLD_COUNT (typically 3)
consecutive HELLOs sent on interface I. This ensures that node j
will either receive one of these HELLOs on interface J, or will miss
NBR_HOLD_COUNT HELLOs and thus declare the link (J,I) to be LOST.
This technique makes it unnecessary for a node to include each 1-WAY
or 2-WAY neighbor in HELLOs indefinitely, unlike OSPF.
To avoid establishing a link that is likely to be short lived (i.e.,
to employ hysteresis), node i must receive (on interface I) at least
HELLO_ACQUIRE_COUNT (e.g., 2) of the last HELLO_ACQUIRE_WINDOW (e.g.,
3) HELLOs sent from a neighbor interface J, before declaring the link
(I,J) to be 1-WAY. When this happens, node i includes J in the
NEIGHBOR REQUEST list in each of its next NBR_HOLD_COUNT HELLO
messages sent on interface I, or until a NEIGHBOR REPLY message
containing I is received on interface I from neighbor interface J.
If node j receives (on interface J) one of the HELLOs sent from
interface I that contains J in the NEIGHBOR REQUEST list, then node j
declares the link (J,I) to be 2-WAY (unless it is already 2-WAY), and
includes I in the NEIGHBOR REPLY list in each of its next
NBR_HOLD_COUNT HELLO messages sent on interface J. Upon receiving
one of these HELLOs on interface I, node i declares the link (I,J) to
be 2-WAY.
If node i receives a HELLO on interface I, sent from neighbor
interface J, whose HSEQ indicates that at least NBR_HOLD_COUNT HELLOs
were missed, or if node i receives no HELLO on interface I sent from
interface J within NBR_HOLD_TIME seconds, then node i changes the
status of link (I,J) to LOST (unless it is already LOST), and
includes J in the NEIGHBOR LOST list in each of its next
NBR_HOLD_COUNT HELLO messages sent on interface I (unless the link
changes status before these transmissions are complete). Node j will
either receive one of these HELLOs on interface J or will miss
NBR_HOLD_COUNT HELLOs; in either case, node j will declare the link
(J,I) to be LOST. In this manner, both nodes will agree that the
link between I and J is no longer bidirectional, even if node j can
still hear HELLOs from node i.
Each node may maintain and update one or more link metrics for each
link (I,J) from a local interface I to a neighbor interface J,
representing the quality of the link. Such link metrics can be used
as additional conditions for changing the status of a neighbor, based
on the link metric going above or below some threshold. TBRPF also
allows link metrics to be advertised in topology updates, and to be
used for computing shortest paths.
5.2. Overview of the Routing Module
Each node running TBRPF maintains a source tree, denoted T, which
provides shortest paths to all reachable nodes. Each node computes
and updates its source tree based on partial topology information
stored in its topology table, using a modification of Dijkstra’s
algorithm. To minimize overhead, each node reports only part of its
source tree to neighbors. The main idea behind the current version
of TBRPF came from PTSP [10], another protocol in which each node
reports only part of its source tree. (However, TBRPF differs from
PTSP in several ways.) The current version of TBRPF should not be
confused with its previous version [11], which is a full-topology
routing protocol.
The part of T that a node reports to neighbors is called the
"reported subtree" and is denoted RT. Each node reports RT to
neighbors in *periodic* topology updates (e.g., every 5 seconds), and
reports changes (additions and deletions) to RT in more frequent
*differential* updates (e.g., every 1 second). Periodic updates
inform new neighbors of RT, and ensure that each neighbor eventually
learns RT even if it does not receive all updates. Differential
updates ensure the fast propagation of each topology update to all
nodes that are affected by the update. A received topology update is
not forwarded, but *may* result in a change to RT, which will be
reported in the next differential or periodic update. Whenever
possible, topology updates are included in the same packet as a HELLO
message, to minimize the number of control packets sent. TBRPF does
not require reliable or sequenced delivery of messages, and does not
use ACKs or NACKs.
TBRPF supports multiple interfaces, associated hosts, and network
prefixes. Information regarding associated interfaces, hosts, and
prefixes is disseminated efficiently in periodic and differential
updates, similar to the dissemination of topology updates.
The reported subtree RT consists of links (u,v) of T such that u is
in the "reported node set" RN, which is computed as follows. Node i
includes a neighbor j in RN if and only if node i determines that one
of its neighbors may select i to be its next hop on its shortest path
to j. To make this determination, node i computes the shortest
paths, up to 2 hops, from each neighbor to each other neighbor, using
only neighbors (or node i itself) as an intermediate node, and using
relay priority (included in HELLO messages) and router ID to break
ties. After a node determines which neighbors are in RN, each
reachable node u is included in RN if and only if the next hop on the
shortest path to u is in RN. A node also includes itself in RN. As
a result, the reported subtree RT includes the subtrees of T that are
rooted at neighbors in RN, and also includes all local links to
neighbors.
We note that neighbors in RN are analogous to multipoint relay (MPR)
selectors [12]. Thus, if node i selects neighbor j to be in RN, then