INTERNET-DRAFT Richard G. Ogier
IETF MANET Working Group Fred L. Templin
28 November 2001 Bhargav Bellur
Mark G. Lewis
SRI International
Topology Broadcast Based on Reverse-Path Forwarding (TBRPF)
<draft-ietf-manet-tbrpf-03.txt>
Status of This Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026 except that the right to
produce derivative works is not granted.
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
TBRPF is a proactive, link-state routing protocol designed for mobile
ad-hoc networks, which provides hop-by-hop routing along minimum-hop
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. This is in
contrast to other protocols (e.g., STAR) in which each node reports
its *entire* source tree to neighbors. TBRPF uses a combination of
periodic and differential updates to keep all neighbors informed of
the reportable 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 and OLSR.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 1]
INTERNET-DRAFT TBRPF 28 November 2001
Contents
1. Introduction ................................................... 1
2. Changes ........................................................ 1
3. TBRPF Terminology .............................................. 2
4. Applicability Section .......................................... 3
4.1. Networking Context ........................................ 4
4.2. Protocol Characteristics and Mechanisms ................... 4
5. TBRPF Overview ................................................. 6
5.1. Overview of Neighbor Discovery ............................ 6
5.2. Overview of Topology Discovery and Route Computation ...... 7
6. TBRPF Packets .................................................. 9
6.1. TBRPF Packet Header ....................................... 9
6.2. TBRPF Packet Body ......................................... 11
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 ....................... 15
7.5. Expiration of Timer nbr_life .............................. 16
7.6. Link-Layer Failure Indication ............................. 16
7.7. Configurable Parameters ................................... 17
8. Topology Discovery and Route Computation ....................... 17
8.1. Conceptual Data Structures and Messages ................... 17
8.2. TOPOLOGY UPDATE Messages .................................. 19
8.3. TBRPF Operation ........................................... 19
8.4. Pseudocode ................................................ 21
8.5. Configurable Parameters ................................... 26
9. Application of TBRPF In Mobile Ad-hoc Networks (MANETs) ........ 26
9.1. Data Link Layer Assumptions ............................... 26
9.2. Network Layer Assumptions ................................. 27
9.3. Optional Automatic Address Resolution ..................... 27
9.4. Support for Multiple Interfaces and/or Alias Addresses .... 27
9.5. Support for Hierarchical Network Prefixes ................. 28
9.6. Support for non-MANET Hosts ............................... 28
9.7. Internet Protocol Considerations .......................... 28
9.7.1. IPv4 Operation ..................................... 28
9.7.2. IPv6 Operation ..................................... 29
10. IANA Considerations ........................................... 29
11. Implementation Status ......................................... 29
12. Patent Rights Statement ....................................... 30
13. Acknowledgments ............................................... 30
14. References .................................................... 30
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page ii]
INTERNET-DRAFT TBRPF 28 November 2001
1. Introduction
TBRPF is a proactive, link-state routing protocol that provides hop-
by-hop routing along minimum-hop paths to each destination. Each
node running TBRPF computes a source tree (providing minimum-hop
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. This is in contrast to other protocols
(e.g., FTSP [7] and STAR [4]) in which each node reports its *entire*
source tree to neighbors.
TBRPF uses a combination of periodic and differential updates to keep
all neighbors informed of the reportable 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 and OLSR.
TBRPF consists of two modules: the neighbor discovery module and the
topology discovery and route computation module. An overview of
these modules is given in Section 5.
2. Changes
Major changes from version 02 to version 03:
- TBRPF no longer uses ACKs or NACKs to provide reliable delivery of
messages. Instead, it uses a combination of periodic and differen-
tial topology updates.
- NEW PARENT messages are no longer used for the selection of
parents. Instead, parents select themselves, thus avoiding the
overhead of NEW PARENT messages.
- The full topology (FT) mode of TBRPF has been merged with the par-
tial topology (PT) mode. Each node is required to report the
minimum topology information (as in PT), but has the option of
reporting additional topology information.
Major changes from version 01 to version 02:
- The neighbor discovery protocol has been modified so that it is
simpler and is independent of the routing protocol.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 1]
INTERNET-DRAFT TBRPF 28 November 2001
- Sections 9 and 10 have been shortened considerably.
- The IANA considerations section has been revised to bring it up to
date with recent discussions on the MANET email list.
Major changes from version 00 to version 01:
- A partial-topology mode (TBRPF-PT) has been introduced to achieve
a further reduction in control traffic in large, dense networks.
- The neighbor discovery protocol has been improved significantly.
- The unicast mode for transmitting TBRPF messages has been elim-
inated: each TBRPF packet is now broadcast to all neighbors. If
a message is to be processed by only a few neighbor nodes, their
identities are included in the message.
- All topology updates are now sent reliably to all neighbors using
NACKs.
- Two new configurable parameters, MIN_UPDATE_INTERVAL and
MIN_FORW_UPDATE_INTERVAL, have been introduced to minimize fre-
quent generation and forwarding of topology updates.
- TBRPF-FT includes a new message type NEW PARENT REPLY, which is
sent in response to one or more NEW PARENT messages. A single
message is sent in response to multiple NEW PARENT messages that
are received at about the same time.
- A new packet formatting scheme is used that provides optimal pack-
ing of TBRPF protocol elements with minimal insertion of header
and null padding octets. A packet compression mechanism is
included that eliminates all null padding octets when enabled.
- Formats have been added for new TBRPF-FT and TBRPF-PT message
types. Formats have been revised for some existing TBRPF-FT mes-
sage types.
- An implicit NARP mechanism has been provided for binding one or
more IP addresses to a Router ID.
- Optional checksum facilities have been provided for data
integrity.
3. TBRPF Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [2]. The
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 2]
INTERNET-DRAFT TBRPF 28 November 2001
following terms are also used to describe TBRPF:
node
A router that implements TBRPF, identified by a unique router ID
(RID), also called a node ID.
link
A logical connection from one node to another, identified by a
pair (u,v), where u and v represent nodes. Nodes u and v are
called the "head" and "tail" of the link, respectively. A link is
said to be bidirectional or 2-way if each node can receive
messages from the other. A bidirectional link need not use the
same interfaces or media in both directions.
neighbor
A node v is said to be a neighbor of node u if there is a
bidirectional link (u,v) between them.
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.
directed tree
A subset of (directed) links (u,v) that does not contain any
loops. The root of a directed tree is the only node u such that
the tree contains no link whose tail is u.
source tree
The directed tree computed by each node that provides shortest
paths to all other nodes. Not the same as a broadcast tree.
topology update
A message or part of a message that reports a state change for one
or more links.
update source
The node that originated a given topology update.
parent
The parent of a node i for an update source u is the next node on
the computed minimum-hop path to node u.
4. Applicability Section
This section describes the networking context and protocol charac-
teristics of the TBRPF protocol as specified in the MANET Routing
Protocol Applicability Statement [16].
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 3]
INTERNET-DRAFT TBRPF 28 November 2001
4.1. Networking Context
TBRPF is appropriate for any large MANET network, especially when
nodes are highly mobile and bandwidth is limited.
4.2. Protocol Characteristics and Mechanisms
* Does the protocol provide shortest path routes?
Yes.
* Does the protocol provide support for unidirectional links? (if
so, how?)
No. It uses only bidirectional links (as in 802.11).
* Does the protocol require the use of tunneling? (if so, how?)
No.
* Does the protocol require using some form of source routing? (if
so, how?)
No. The protocol uses hop-by-hop routing. However, since the
entire path is known, source routing can be used as an option.
* Does the protocol require the use of periodic messaging? (if so,
how?)
Each node transmits HELLO and topology update messages periodi-
cally.
* Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?)
No.
* Does the protocol provide support for routing through a multi-
technology routing fabric? (if so, how?)
Yes. Each network interface is assigned a unique IP address.
* Does the protocol provide support for multiple hosts per router?
(if so, how?)
Yes. The concept of a Router ID (RID) [3,14,17] can be used to
associate multiple hosts with a single RID.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 4]
INTERNET-DRAFT TBRPF 28 November 2001
* Does the protocol support the IP addressing architecture? (if so,
how?)
Yes.
* Does the protocol require link or neighbor status sensing (if so,
how?)
Yes. A new, efficient neighbor discovery protocol is presented,
in which each HELLO message contains only the IDs of nodes that
have recently been heard but with which a 2-way link has not yet
been established.
* Does the protocol depend on a central entity? (if so, how?)
No.
* Does the protocol function reactively? (if so, how?)
The protocol reacts to topology changes, but not to traffic
demand.
* Does the protocol function proactively? (if so, how?)
Yes. It maintains optimal paths to all reachable destinations at
all times.
* Does the protocol provide loop-free routing? (if so, how?)
Yes. Since routing is based on link states, it provides loop-free
routing when the topology is stable.
* Does the protocol provide for sleep period operation? (if so,
how?)
TBRPF operates correctly even if nodes can go into and out of
sleep mode at arbitrary times. Other features can be added, such
as assigning awake routers to store packets for sleeping nodes.
* Does the protocol provide some form of security? (if so, how?)
No. Other other protocols (such as IMEP [14]) can be used to pro-
vide security.
* Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?)
Yes. A network using multiple radio channels can be represented
by a single logical topology in which any link can use any channel
or combination of channels.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 5]
INTERNET-DRAFT TBRPF 28 November 2001
5. TBRPF Overview
TBRPF consists of two main modules: the neighbor discovery module,
and the topology discovery and route computation module.
5.1. Overview of Neighbor Discovery
The TBRPF Neighbor Discovery (TND) protocol allows each node to
quickly detect the neighboring nodes with which the node has a
direct, bidirectional link, i.e., a link such that the node at each
end of the link can hear the other node. The protocol also detects
when a bidirectional link to some neighbor no longer exists.
The key feature of TND is that it uses "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 and OLSR, in which each HELLO
message includes the IDs of *all* neighbors. As a result, HELLO mes-
sages can be sent more frequently in highly mobile networks without
increasing overhead significantly.
TND is designed to be fully modular and independent of the routing
protocol. As a result, TND can be used by other routing protocols,
and TBRPF can use another neighbor discovery protocols in place of
TND, e.g., one provided by the link layer.
Each node sends a HELLO message every HELLO_INTERVAL seconds, with a
small jitter. Each HELLO message contains three (possibly empty)
lists of router IDs, formatted as the following three message sub-
types: NEIGHBOR REQUEST, NEIGHBOR REPLY, and NEIGHBOR LOST. A NEIGH-
BOR REQUEST message is always included in a HELLO, even if its list
of router IDs is empty. However, a NEIGHBOR REPLY or NEIGHBOR LOST
message is included only if its list of router IDs is nonempty. Each
HELLO message also contains the current HELLO sequence number (HSEQ),
which is incremented with each transmitted HELLO. For convenience,
we say that "node i sends a NEIGHBOR REQUEST message for node j" if
node i sends such a message that includes the ID of node j, and simi-
larly for NEIGHBOR REPLY and NEIGHBOR LOST messages.
Each node maintains a neighbor table, which stores the state informa-
tion for other nodes. The state (or level) of each node can be 1-
WAY, 2-WAY, or LOST. When node i changes the state of a neighbor j,
it sends the appropriate message (NEIGHBOR REQUEST/UP/LOST) in at
most NBR_HOLD_COUNT (typically 3) consecutive HELLOs. This ensures
that node j will either receive the message, or will miss
NBR_HOLD_COUNT HELLOs and thus declare node i to be LOST. This tech-
nique also makes it unnecessary for a node to include each 1-WAY
neighbor in HELLOs indefinitely, unlike OSPF and OLSR.
The NEIGHBOR REQUEST message includes a list of neighbors from which
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 6]
INTERNET-DRAFT TBRPF 28 November 2001
HELLO messages have recently been heard but for which a 2-WAY link is
not currently established. To avoid establishing a link that is
likely to be short lived (i.e., to employ hysteresis), a node i must
receive at least HELLO_ACQUIRE_COUNT (typically 2) of the last
HELLO_ACQUIRE_WINDOW (typically 3) HELLOs from another node j before
declaring the node to be 1-WAY. In this case, node i sends a NEIGH-
BOR REQUEST message for node j in each of its next NBR_HOLD_COUNT
HELLO messages, or until a NEIGHBOR REPLY message for node i is
received from node j.
If node j receives a NEIGHBOR REQUEST from node i, then node j
declares the link to node i to be 2-WAY (if it is not already 2-WAY),
and includes a NEIGHBOR REPLY message for node i in its next
NBR_HOLD_COUNT transmitted HELLO messages. Upon receiving the NEIGH-
BOR REPLY message, node i declares the link to node j to be 2-WAY.
If node i receives a HELLO from a 1-WAY or 2-WAY neighbor j whose
HSEQ indicates that at least NBR_HOLD_COUNT HELLOs were missed, or if
node i receives no HELLO from node j within NBR_HOLD_TIME seconds,
then node i changes the state of node j to LOST, and sends a NEIGHBOR
LOST message for node i in its next NBR_HOLD_COUNT transmitted HELLO
messages (unless the link changes state before these transmissions
are complete). Node j will either receive the message or will miss
NBR_HOLD_COUNT HELLOs; in either case it will declare node i to be
LOST. In this manner, both nodes will agree that the link is no
longer bidirectional, even if node j can still hear HELLOs from node
i.
5.2. Overview of Topology Discovery and Route Computation
TBRPF is a proactive, link-state routing protocol that provides hop-
by-hop routing along minimum-hop paths to each destination. Each node
running TBRPF computes a source tree (providing paths to all reach-
able 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. This is in contrast to FTSP [7] and STAR [4], in which
each node reports its *entire* source tree to neighbors, which is
redundant since the source trees of different neighbors often overlap
considerably. The main idea behind the current version of TBRPF came
from PTSP [7], another protocol in which each node reports only part
of its source tree. However, PTSP differs in many ways from TBRPF:
e.g., PTSP uses NEW PARENT messages and reliable updates, unlike the
current version of TBRPF (but like previous versions of TBRPF [1]).
To decide which part of its source tree T to report to neighbors, a
node running TBRPF first computes its "reportable node set" RN.
Roughly speaking, node i includes node u in RN if it estimates that
the minimum-hop path from some neighbor j (of node i) to destination
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 7]
INTERNET-DRAFT TBRPF 28 November 2001
u goes through node i. In other words, node i includes node u in RN
if it estimates that it is the next hop (or parent) of some neighbor
to destination u. This technique avoids the need for the NEW PARENT
messages that were used in PTSP and previous versions of TBRPF.
The part of T that a node reports to neighbors is called the "report-
able subtree" and is denoted RT. RT consists of links (u,v) of T
such that u is in RN. 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 *differen-
tial* 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 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 does not use sequence numbers for topology updates, thus reduc-
ing message overhead and avoiding wraparound problems. Instead, a
technique similar to SPTA [20] is used in which, for each link (u,v)
reported by one or more neighbors, only the parent p(u) for u is
believed regarding the the state of the link. (However, in SPTA each
node reports the full topology.) Using this technique, each node
maintains a topology graph TG, consisting of "believable" links that
are reported by neighbors, and computes T as the shortest-path tree
within TG. To allow immediate rerouting, the restriction that each
link (u,v) in TG must be reported by p(u) is relaxed temporarily if
p(u) changes to a neighbor that is not reporting the link.
Each node is required to report RT, but MAY report additional links,
e.g., to provide increased robustness in highly mobile networks.
More precisely, a node may maintain any subgraph H of TG that con-
tains T, and report the reportable subgraph RH, which consists of
links (u,v) of H such that u is in RN. For example, H can equal TG,
which would provide each node with the full network topology if this
is done by all nodes. H can also be a biconnected subgraph that con-
tains T, which would provide each node with two disjoint paths to
each other node, if this is done by all nodes.
In a MANET, some nodes, called non-relay nodes, may choose not to
forward data packets for other nodes. Non-relay nodes are supported
by TBRPF in a very simple manner: they run TBRPF (and transmit HEL-
LOs) but do not do not transmit topology update messages. As a
result, no node will compute a path that uses a non-relay node as an
intermediate node.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 8]
INTERNET-DRAFT TBRPF 28 November 2001
6. TBRPF Packets
Nodes send TBRPF protocol data in *packets*. Each packet includes a
packet header, optional header extensions, and a packet body that
comprises one or more *message(s)* and padding options as needed.
The total length of all packet components MUST be less than the max-
imum length represented by an unsigned 16-bit integer, i.e. 64KB.
6.1. TBRPF Packet Header
TBRPF packet headers are variable-length (minimum two octets) as
determined by "flag" bits found in the first octet. Implementations
MUST ensure that the first octet of the TBRPF packet header is
aligned on an even 8-octet boundary in order to guarantee alignment
of n-octet data elements up to 8-octets in length. All further align-
ment requirements discussed throughout this section are relative to
the first octet of the TBRPF packet header. Therefore, bit ordering
beginning at bit 0 is shown ONLY in the TBRPF packet header diagram;
Other diagrams throughout this document omit the bit ordering nota-
tion. The format for the TBRPF packet header and a description of the
individual fields are given below:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - - - -
|C|L|R|Z| Vers | Reserved | Optional Extension Fields
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - - - -
Flags (4 bits):
Three flag bits (C, L, R) specify which header extension fields
(if any) are present. Any header extension fields enabled by these
bits MUST appear in canonical order (i.e. first C, then L, then
R). A fourth flag bit (Z) specifies either aligned or compressed
format for the TBRPF message. The flag bits and their usage are
described in detail below:
C - Checksum Field Included:
If the underlying delivery service provides a checksum facility
the sender MAY set C = '0' and omit the checksum extension
field. Otherwise, the sender MUST set C = '1' and include a
16-bit checksum field beginning in the first octet of the
header extension. When C = '1', the sender MUST calculate the
checksum of the packet in the manner described in [11] and
write the result into the checksum field. The checksum is cal-
culated across ALL data bytes in the packet header and body,
but DOES NOT include a pseudo-header of the underlying delivery
service. Therefore, if other header extension fields are also
included (see below), the sender MUST fill in such additional
fields BEFORE the checksum is calculated.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 9]
INTERNET-DRAFT TBRPF 28 November 2001
Receivers MUST examine the C bit to determine whether the
checksum field is present. If C = '1', a receiver MUST verify
the checksum encoded in the 16-bit message checksum field as
described in [11] WHETHER OR NOT a checksum was also performed
by the underlying delivery service. Receivers MUST discard any
TBRPF packet that contains an incorrect checksum as well as any
packet with neither a checksum provided by the underlying
delivery service nor a checksum in the packet header.
L - Length Field Included:
If the underlying delivery service provides a length field, the
sender MAY set L = '0' and omit the length field. Otherwise,
the sender MUST set L = '1' and include a 16-bit unsigned
integer length field immediately after any previous header
fields. When L = '1', the sender MUST calculate the length of
the TBRPF packet (including all header and data bytes) and
write the result into the length field in network byte order.
Receivers MUST examine the L bit to determine whether the
length field is present. If L = '1', a receiver MUST convert
the length field to host byte order to determine the length of
the TBRPF packet, including the TBRPF packet header. If the
underlying delivery service ALSO provides a length field,
receivers MUST verify that two lengths match (discarding the
packet if they do not.) Similarly, receivers MUST discard any
TBRPF packet if neither the underlying delivery service nor the
TBRPF packet header provide packet length.
R - Router ID (RID) Included:
If the underlying delivery service encodes the sender's RID,
the sender MAY set R = '0' and omit the RID field. Otherwise,
the sender MUST set R = '1' and include a 32-bit unsigned
integer RID immediately after any previous header fields. The
RID option provides a mechanism for implicit Network-level
Address Resolution (NARP) as described in [14]. A receiver that
detects an RID option MUST create a NARP binding between the
RID and the source address that appears in the network-level
header.
NB: The first octet of the RID field is NOT GUARANTEED to fall
on a natural 32-bit word alignment REGARDLESS of the sense of
the 'Z' bit in the TBRPF packet header (see below). Receivers
MUST copy the RID field byte-by-byte (rather than as an atomic
32-bit word) when the RID is not aligned on a natural 32-bit
boundary.
Z - Message Alignment/Compression:
If Z = '0', the sender MUST align multi-octet words within the
TBRPF packet body on "natural" boundaries (i.e. 64-bit words on
integral modulo-8 byte addresses, 32-bit on integral modulo-4
byte addresses and 16-bit words on integral module-2 byte
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 10]
INTERNET-DRAFT TBRPF 28 November 2001
addresses.) The sender MUST use Pad1 and/or PadN options
(described below) where necessary to achieve natural alignment.
If Z = '1', the sender MAY OPTIONALLY omit padding to provide
message compression. Since compression may result in multi-
octet words aligned on non-integral byte boundaries, receivers
MUST process such multi-octet words "byte-by-byte" rather than
as atomic n-byte data units. Senders SHOULD avoid message
compression to minimize processing overhead for receivers
unless maximal message compression is required (e.g. for low-
bandwidth links). Receivers MUST be prepared to process both
aligned and compressed packets.
Version (4 bits):
Identifies TBRPF protocol version. The following version field
values are defined:
TBRPFVERSION_2 2
TBRPFVERSION_1 1
The packet formats defined in this draft represent TBRPF version 2
and MUST be transmitted with the value TBRPFVERSION_2 in the ver-
sion field. TBRPF version 2 implementations MAY OPTIONALLY pro-
vide backwards compatibility for TBRPFVERSION_1 packets (specified
in earlier versions of this draft).
Reserved (8 bits):
Reserved for future use.
6.2. TBRPF Packet Body
The TBRPF packet body consists of the concatenation of a number of
elements including one or more TBRPF message(s) and padding options
where necessary. These elements are encoded using a method similar
to the type-length-value (TLV) encoding method described in pp. 9-10
of Internet RFC 2460 [15] and other documents, except that the length
of each element is calculated in a type-specific fashion. Therefore,
the "LENGTH" field is subsumed by the "VALUE" field in the symbolic
representation. This method encodes elements within the TBRPF packet
body using the following format:
+-+-+-+-+-+-+-+-+- - - - -
| TYPE |RES| VALUE
+-+-+-+-+-+-+-+-+- - - - -
TYPE (6 bits):
A 6-bit identifier with value 0 - 63 that identifies the element.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 11]
INTERNET-DRAFT TBRPF 28 November 2001
RES - Reserved (2 bits):
Reserved for future use.
VALUE
Variable-length field. Format depends on TYPE, as described in the
following sections.
As specified in [15], the sequence of elements MUST be processed
strictly in the order they appear within the TBRPF packet body; a
receiver must not, for example, scan through the packet body looking
for a particular type of element prior to processing all preceding
elements. Additionally, individual elements may have specific align-
ment requirements to ensure that multi-octet values fall on natural
boundaries. The alignment requirement of an element is specified
using the notation "xn+y", meaning the element type must begin at an
integer multiple of x octets from the start of the TBRPF packet
header, plus y octets. For example:
2n means any 2-octet offset from the start of the TBRPF
packet header.
8n+2 means any 8-octet offset from the start of the TBRPF
packet header, plus 2 octets.
TBRPF packet elements include *padding options* and *messages*. The
following subsections describe these elements.
6.2.1. Padding Options (Type = 0 thru 1)
As specified in [15], senders may insert two types of padding options
where necessary to satisfy alignment requirements for other elements.
Padding options may occur anywhere within the TBRPF packet body. When
the Z bit in the packet header is '0', senders MUST insert padding
options to ensure that the alignment requirements for other elements
are met. When Z = '1', padding options MAY be omitted and alignment
is NOT guaranteed. The following two padding options are defined:
Pad1 option (TYPE = 0)
- Alignment requirement: none
+-+-+-+-+-+-+-+-+
| 0 |0|0|
+-+-+-+-+-+-+-+-+
The Pad1 option inserts one octet of padding into the TBRPF packet
body. The RES bits MUST be '0', and the VALUE field is omitted.
If more than one octet of padding is required, the PadN option
(described next) should be used, rather than multiple Pad1 options.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 12]
INTERNET-DRAFT TBRPF 28 November 2001
PadN option (TYPE = 1)
- Alignment requirement: none
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - -
| 1 |0|0| LEN | Zero-valued Octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - -
The PadN option inserts two or more octets of padding into the TBRPF
packet body. The RES bits MUST be '0' and the first octet of the VALUE
field contains an 8-bit unsigned integer length containing a value
between 0 - 253 which specifies the number of zero-valued octets that
immediately follow, yielding a maximum total of 255 padding octets.
7. TBRPF Neighbor Discovery
This section describes the TBRPF Neighbor Discovery (TND) protocol,
which allows each node to quickly detect the neighboring nodes with
which the node has a direct, bidirectional (2-WAY) link, and to
quickly detect the loss of such a link.
TND is designed to be independent of the module of TBRPF that per-
forms topology discovery and route computation. The interface
between these two modules is defined simply by the two functions
Link_Up() and Link_Down(), which are called by TND to report a new
neighbor or the loss of a neighbor.
7.1. HELLO Message Format
The HELLO message has the following three subtypes:
- NEIGHBOR REQUEST (TYPE = 2)
- NEIGHBOR REPLY (TYPE = 3)
- NEIGHBOR LOST (TYPE = 4)
Each HELLO subtype has the following format:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TYPE |0|0| N | HSEQ |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 13]
INTERNET-DRAFT TBRPF 28 November 2001
- The message body contains N 4-octet router IDs.
- HSEQ is the 8-bit HELLO sequence number.
A HELLO message is the concatenation of a NEIGHBOR REQUEST message, a
NEIGHBOR REPLY message, and a NEIGHBOR LOST message, where each of
the last two messages is omitted if its list of router IDs is empty.
Thus, a HELLO message always includes a (possibly empty) NEIGHBOR
REQUEST.
7.2. Neighbor Table
Each node maintains a neighbor table, which stores state information
for each known neighbor. The entry for neighbor j contains the fol-
lowing variables:
nbr_level(j) - The current level (or status) of the link to node
j, which can be LOST, 1-WAY, or 2-WAY.
nbr_life(j) - The amount of time (in seconds) remaining before
nbr_level(j) must be changed to LOST if no further HELLO message
from node j is received. Set to NBR_HOLD_TIME whenever a HELLO is
received from node j.
nbr_hseq(j) - The last value of HSEQ received from node j. Used
to determine the number of HELLOs have been missed.
nbr_count(j) - The number of times a NEIGHBOR REQUEST/UP/LOST mes-
sage has been sent for node j since nbr_level(j) has changed.
hello_history(j) - A list of the sequence numbers of the last
HELLO_ACQUIRE_WINDOW HELLO messages received from node j.
The table entry for a neighbor j may be deleted if no HELLO has been
received from node j within the last 2*NBR_HOLD_TIME seconds. (It is
kept while the NEIGHBOR LOST for node j is being transmitted.) The
absence of an entry for a given node j is equivalent to an entry with
nbr_level(j) = LOST and hello_history(j) = NULL.
The three possible values of nbr_level(j) at node i have the follow-
ing meaning:
LOST
A neighbor is declared to be LOST if no HELLO message has been
received from node j within the last NBR_HOLD_TIME seconds, and
remains LOST until HELLO_ACQUIRE_COUNT of the last
HELLO_ACQUIRE_WINDOW HELLOs from node j are received.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 14]
INTERNET-DRAFT TBRPF 28 November 2001
1-WAY
HELLO_ACQUIRE_COUNT of the last HELLO_ACQUIRE_WINDOW HELLOs from
node j have been received, but the link is not 2-WAY.
2-WAY
Node i has received from node j either a NEIGHBOR REQUEST or a
NEIGHBOR REPLY from node j, and no event has since occurred to
change this status. A link that is 2-WAY is considered to be "up".
7.3. Sending HELLO Messages
Each node sends a HELLO message periodically every HELLO_INTERVAL
seconds, with a random jitter selected from the interval [0,
MAX_JITTER]. Each HELLO message always includes a NEIGHBOR REQUEST
message, even if its router ID list is empty. The NEIGHBOR REQUEST
message includes the sequence number HSEQ, which is incremented each
time a HELLO is sent. The HELLO message also includes a NEIGHBOR
REPLY message if its router ID list is nonempty, and a NEIGHBOR LOST
message if its router ID list is nonempty. The contents of these
three messages are determined by the following steps at node i:
1. For each node j such that nbr_level(j) = LOST and nbr_count(j) >
0, include node j in the NEIGHBOR LOST message and decrement
nbr_count(j).
2. For each node j such that nbr_level(j) = 1-WAY and nbr_count(j) >
0, include node j in the NEIGHBOR REQUEST message and decrement
nbr_count(j).
3. For each node j such that nbr_level(j) = 2-WAY and nbr_count(j) >
0, include node j in the NEIGHBOR REPLY message and decrement
nbr_count(j).
7.4. Processing a Received HELLO Message
Upon receiving a HELLO message with sequence number HSEQ from node j,
node i performs the following steps:
1. If a neighbor table entry does not exist for node j, create one
with nbr_level(j) = LOST (temporarily) and nbr_count(j) = 0.
Update hello_history(j) to reflect the received HELLO message.
2. If nbr_level(j) = LOST and hello_history(j) indicates that
HELLO_ACQUIRE_COUNT of the last HELLO_ACQUIRE_WINDOW HELLO mes-
sages from node j have been received:
a. If node i does not appear in the NEIGHBOR REQUEST list, set
nbr_level(j) = 1-WAY and nbr_count(j) = NBR_HOLD_COUNT (a
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 15]
INTERNET-DRAFT TBRPF 28 November 2001
NEIGHBOR REQUEST will be sent).
b. If node i appears in the NEIGHBOR REQUEST list, set
nbr_level(j) = 2-WAY and nbr_count(j) = NBR_HOLD_COUNT (a
NEIGHBOR REPLY will be sent). Call Link_Up().
3. Else if nbr_level(j) = 1-WAY:
a. If node i appears in the NEIGHBOR REQUEST list, then set
nbr_level(j) = 2-WAY, nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR
REPLY will be sent). Call Link_Up(j).
b. Else if node i appears in the NEIGHBOR REPLY list, then set
nbr_level(j) = 2-WAY and nbr_count(j) = 0. Call Link_Up(j).
c. Else if HSEQ - nbr_hseq(j) > NBR_HOLD_COUNT, then set
nbr_level(j) = LOST and nbr_count(j) = NBR_HOLD_COUNT (a NEIGH-
BOR LOST will be sent).
4. Else if nbr_level(j) = 2-WAY:
a. If node i appears in the NEIGHBOR LOST list, set nbr_level(j) =
LOST and nbr_count(j) = 0. Call Link_Down(j).
b. Else if HSEQ - nbr_hseq(j) > NBR_HOLD_COUNT, set nbr_level(j) =
LOST and nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR LOST will be
sent).
c. Else if node i appears in the NEIGHBOR REQUEST list and
nbr_count(j) = 0, then set nbr_count(j) = NBR_HOLD_COUNT (a
NEIGHBOR REPLY will be sent).
5. Set nbr_life(j) = NBR_HOLD_TIME and nbr_hseq(j) = HSEQ.
7.5. Expiration of Timer nbr_life
Upon expiration of the timer nbr_life(j), node i performs the follow-
ing step:
If nbr_level(j) = 1-WAY or 2-WAY, set nbr_level(j) = LOST and
nbr_count(j) = NBR_HOLD_COUNT (a NEIGHBOR LOST will be sent).
Call Link_Down(j).
7.6. Link-Layer Failure Indication
Some link-layer protocols (e.g., IEEE 802.11) provide an indication
that the link to a particular neighbor has failed, e.g., after
attempting a maximum number of retransmissions. If such an indication
is provided by the link layer, then node i SHOULD perform the
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 16]
INTERNET-DRAFT TBRPF 28 November 2001
following step upon receipt of a link-layer failure indication for
the link to node j:
If nbr_level(j) = 2-WAY, set nbr_level(j) = LOST and nbr_count(j)
= NBR_HOLD_COUNT (a NEIGHBOR LOST will be sent). Call
Link_Down(j).
7.7. Configurable Parameters
This section lists the parameters used in the description of the
neighbor discovery protocol, and their proposed default values.
HELLO_INTERVAL (1 second)
MAX_JITTER (0.1 second)
NBR_HOLD_TIME (3 seconds)
NBR_HOLD_COUNT (3)
HELLO_ACQUIRE_COUNT (2)
HELLO_ACQUIRE_WINDOW (3)
8. Topology Discovery and Route Computation
This section describes the module of TBRPF that performs topology
discovery and route computation. The interface of this module with
the neighbor discovery module (TND) is defined by the two functions
Link_Up(j) and Link_Down(j), which are called by TND. Therefore, it
is possible to use another neighbor discovery mechanism in place of
TND, e.g., one that is provided by the link layer.
8.1. Conceptual Data Structures
In addition to the information required by the neighbor discovery
protocol, each node running TBRPF contains a topology table TT, which
stores information for each known link and node in the network. The
following information is stored at node i for each known link (u,v)
and node u:
T(u,v) - Equal to 1 if (u,v) is in node i's source tree T, and 0
otherwise. The previous source tree is also maintained as old_T.
RN(u) - Equal to 1 if u is in node i's reportable node set RN, and
0 otherwise. The previous reportable node set is also maintained
as old_RN.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 17]
INTERNET-DRAFT TBRPF 28 November 2001
RT(u,v) - Equal to 1 if (u,v) is in node i's reportable subtree
RT, and 0 otherwise. Since RT is defined as the set of links (u,v)
in T such that u is in RN, this variable need not be maintained
explicitly.
TG(u,v) = Equal to 1 if (u,v) is in node i's topology graph TG,
and 0 otherwise.
N - The set of 2-way neighbors of node i.
r(u,v) - The list of neighbors that are reporting link (u,v) in
their reportable subtree RT. The set of links (u,v) reported by
neighbor j is denoted RT_j.
r(u) - The list of neighbors that are reporting source u in their
reportable node set RN. The set of nodes u reported by neighbor j
is denoted RN_j.
p(u) - The current parent for source u, equal to the next node on
the min-hop path to u.
next(u) - The next node on the min-hop path to destination u, used
for forwarding data packets. Equal to p(u) in the current version.
pred(u) - The node preceding node u in node i's source tree T.
Equal to NULL if node u is not reachable.
pred(j,u) - The node preceding node u in the subtree RT_j reported
by neighbor j.
dist(u) - The number of hops on the shortest path to u.
reported(u,v) - Equal to 1 if link (u,v) in TG is reported by
p(u).
tg_expire(u) - Expiration time for links (u,v) in TG.
rt_expire(j,u) - Expiration time for links (u,v) in RT_j.
nr_expire(u,v) - Expiration time for a link (u,v) in TG such that
reported(u,v) = 0. Such non-reported links can be used temporarily
during rerouting and usually have an earlier expiration time than
tg_expire(u).
8.2. TOPOLOGY UPDATE Message Format
The TOPOLOGY UPDATE message has the following format:
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 18]
INTERNET-DRAFT TBRPF 28 November 2001
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TYPE |0|0| n | NRL | NRNL |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID of u |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID of v_1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID of v_n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The message body contains the N+1 router IDs for nodes u,
v_1,...,v_n, which represent the links (u,v_1),..., (u,v_n). The
first NRL of the v_k are "reported leaf nodes", the next NRNL of the
v_k are "non-reported leaf nodes", and the last n - (NRL+NRNL) of the
v_k are "non-reported non-leaf nodes". (The meanings of these terms
are defined in the pseudocode.)
The TOPOLOGY UPDATE message has the following three subtypes:
FULL (TYPE = 5)
A FULL update (FULL, n, NRL, NRNL, u, v_1,..., v_n) reports that
the links (u,v_1),..., (u,v_n) belong to the sending router's
reportable subtree RT, and that RT contains no other links with
tail u.
ADD (TYPE = 6)
An ADD update (ADD, n, NRL, NRNL, u, v_1,..., v_n) reports that
the links (u,v_1),..., (u,v_n) have been added to the sending
router's reportable subtree RT.
DELETE (TYPE = 7)
A DELETE update (DELETE, n, NRL, NRNL, u, v_1,..., v_n) reports
that the links (u,v_1),..., (u,v_n) have been deleted from the
sending router's reportable subtree RT.
8.3. TBRPF Operation
This section describes the operation of TBRPF topology discovery and
route computation, with the aid of the pseudocode given in the next
section.
The procedure Update_All() is called periodically every
MIN_UPDATE_INTERVAL seconds, which is typically equal to
HELLO_INTERVAL. Update_All() first generates a HELLO message. It
then calls Update_Routes(), which updates T, TG, and the routing
table. Update_RN() is then called to update the reportable node set
RN. (Recall that the reportable subtree RT is defined to be the set
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 19]
INTERNET-DRAFT TBRPF 28 November 2001
of links (u,v) in T such that u is in RN.) If it is time for a
periodic update, Generate_Periodic_Update() is called; otherwise,
Generate_Diff_Update() is called, which generates differential topol-
ogy updates if RT has changed. The HELLO and TOPOLOGY UPDATE messages
are then broadcast to all neighbors. Whenever possible, these mes-
sages are combined into the same packet, in order to minimize the
number of control packets transmitted.
When a packet containing TOPOLOGY UPDATE messages is received,
Process_Updates() is called to update the topology table TT, in par-
ticular to update TG and the reporting neighbor lists r(u) and
r(u,v). If any link in T has been deleted from TG, then
Update_Routes() is called to provide immediate rerouting.
Link_Up(j) simply adds node j to the neighbor list N, and adds the
link (i,j) to TG, which will result in a change to the source tree T
when Update_All() is next called.
Link_Down(j) removes node j from N and link (i,j) from TG, and calls
Update_Routes() to provide immediate rerouting. If the link loss is
the result of a link-layer failure indication, a differential update
is generated immediately.
TBRPF maintains and updates the routing table, which is used by the
operating system to forward data packets. TBRPF does not specify how
data packets are to be forwarded, but assumes that the forwarding of
data packets is compliant with RFC1812.
Each node is required to report its reportable subtree RT to neigh-
bors. However, each node (independently of the other nodes) MAY
report additional links, e.g., to provide increased robustness in
highly mobile networks. More precisely, a node may compute any sub-
graph H of TG that contains T. It would then report the "reportable
subgraph" RH which consists of links (u,v) of H such that u is in RN.
RH is then be reported instead of RT to all neighbors, in periodic
and differential updates. Additional details for this option will be
described in a future version of this draft.
Non-relay nodes are implemented simply by not generating or transmit-
ting any TOPOLOGY UPDATE messages (only HELLO messages are transmit-
ted). Therefore, the following functions can be omitted in non-relay
nodes: Update_RN(), Generate_Periodic_Update(), and
Generate_Diff_Update().
8.4. Pseudocode
The following pseudocode describes the procedures of TBRPF for topol-
ogy discovery and route computation, as performed by node i.
Update_All() {
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 20]
INTERNET-DRAFT TBRPF 28 November 2001
// Called periodically every MIN_UPDATE_INTERVAL seconds
Set msg_list = empty.
Generate_HELLO(msg_list). // Adds HELLO to msg_list.
Expire_Links().
Update_Routes().
Update_RN().
If (current_time >= next_periodic) {
Generate_Periodic_Update(msg_list).
Set next_periodic = current_time + PER_UPDATE_INTERVAL.}
Else Generate_Diff_Update(msg_list).
Broadcast msg_list to neighbors.
Set old_T = T and old_RN = RN.
}
Update_Routes() {
For each node v in TT {
Set d(v) = INFINITY, pred(v) = NULL.
Set old_p(v) = p(v), p(v) = NULL. }
Set d(i) = 0, p(i) = i, pred(i) = i.
Set S = {i} (labeled nodes).
For each node j in N {
// c(u,v) = 1 for min-hop routing
Set d(j) = c(i,j), pred(j) = i, p(j) = j. }
While there exists a node u in TT - S s.t. d(u) < INFINITY {
Let u be a node in TT - S that minimizes d(u).
// A heap should be used to find u efficiently.
Add u to S.
If p(u) != old_p(u) { // parent has changed
For each link (u,v) in TG {
If (p(u) is not in r(u,v) AND reported(u,v) = 1) {
Set reported(u,v) = 0. // (u,v) is not reported by p(u)
Set nr_expire(u,v) = current_time + PER_UPDATE_INTERVAL.}}
If (p(u) is in r(u)) {
Set tg_expire(u) = rt_expire(j,u).
For each link (u,v) such that p(u) is in r(u,v) {
Add (u,v) to TG.
Set reported(u,v) = 1. }} // (u,v) is reported by p(u)
}
For each node v s.t. (u,v) is in TG {
// Penalize links (u,v) not reported by p(u).
If (reported(u,v) = 0 OR p(u) is not in r(v))
Set cost = c(u,v) + NON_REPORT_PENALTY.
If (d(u) + cost < d(v) OR
[d(u) + cost = d(v) AND ID(u) < ID(pred(v))]) {
Set d(v) = d(u) + c(u,v).
Set pred(v) = u.
Set p(v) = p(u). }}
}
Set T = empty set.
For each node u in TT - i {
Set dist(u) = d(u). // route metric
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 21]
INTERNET-DRAFT TBRPF 28 November 2001
If p(u) != NULL, set next(u) = p(u). // route table entry
Add link (pred(u), u) to T. }
}
Update_RN() {
// RN is the set of nodes reported by node i.
Set RN = empty.
// A neighbor j is in RN if some other neighbor s
// would select node i as p(j).
For each neighbor s in N s.t. j is in r(s) {
// Initialize to run Dijkstra for source s, for 2 hops
For each node j in N+{i},
Set d(j) = INFINITY, par(j) = NULL.
Set d(s) = 0, par(s) = s.
For each link (s,j) s.t. s is in r(s,j) and j is in N+{i} {
Set d(j) = 1, par(j) = j.
For each link (j,k) s.t. j is in r(j,k) and k in in N {
Set cost = 1.
If (1 + cost < d(k) OR
(1 + cost = d(k) AND ID(j) < ID(par(k)))) {
Set d(k) = 1 + cost, par(k) = j. }}}
// End of Dijkstra for source s
For each neighbor j in N {
// Add neighbor j to RN if its parent is i.
If par(j) = i, add j to RN. }
} // End of selection of neighbors in RN
Add i to RN. // Node i is always in RN
// A non-neighbor node u is in RN if p(u) is in RN.
For each node u in TT - i,
If p(u) is in RN, add u to RN.
}
Generate_Periodic_Update(msg_list) {
// Generates updates describing the reportable subtree RT.
For each node u in RN that is not a leaf of T,
add the update (FULL, n, NRL, NRNL, u, v_1,..., v_n)
to msg_list, where:
v_1,..., v_n are the nodes v such that (u,v) is in T,
the first NRL of these are nodes in RN that are leaves of T,
the next NRNL of these are nodes in RN that are not leaves of T,
and the last n-(NRL+NRNL) of these are not in RN.
}
Generate_Diff_Update(msg_list) {
// Generates updates reporting changes to the reportable
// subtree RT.
For each node u in RN {
If u is not in old_RN and is not a leaf of T {
// u was added to RN
Add the update (FULL, n, NRL, NRNL, u, v_1,..., v_n)
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 22]
INTERNET-DRAFT TBRPF 28 November 2001
to msg_list, where v_1,..., v_n, NRL, and NRNL are defined
as above for periodic updates.
}
Else if u is in old_RN and is not a leaf of T {
Let v_1,..., v_n be the nodes v s.t. (u,v) is in T AND {
[(u,v) is not in old_T] OR
[v is in RN - old_RN AND v is a leaf] OR
[v is in old_RN - RN] }
If this set of nodes is nonempty {
Add the update (ADD, n, NRL, NRNL, u, v_1,..., v_n)
to msg_list, where NRL and NRNL are defined as above.}
}
If (u is in old_RN) {
Let v_1,..., v_n be the nodes v s.t. (u,v) is in old_T - TG
AND [pred(v) is NULL or is not in RN].
// If pred(v) is in RN, the delete is implied by an add.
If this set of nodes is nonempty, add the update
(DELETE, n, u, v_1,..., v_n) to msg_list.
}
}
}
Process_Updates(j, msg_list) {
// Processes a list of update messages from node j.
Set update_routes_flag = 0.
// Flag will be set to 1 if a link in T is deleted.
For each update = (subtype, n, NRL, NRNL, u, v_1,..., v_n)
in msg_list {
Create an entry for u in TT if it does not exist.
Create an entry for u in TT_j if it does not exist.
If (subtype = FULL)
Process_Full_Update(j, update).
If (subtype = ADD)
Process_Add_Update(j, update).
If (subtype = DELETE)
Process_Delete_Update(j, update).
// Set update_routes_flag.
If update_routes_flag = 0 {
For each link (u,v) in TT(u) {
If (u,v) is in T but not in TG {
Set update_routes_flag = 1.
Break. }}}
} // End for each update
If (update_routes_flag = 1) Update_Routes().
}
Process_Full_Update(j, update) {
// update = (FULL, n, NRL, NRNL, u, v_1,..., v_n)
Add u to RN.
Set rt_expire(j,u) = current_time + TOP_HOLD_TIME.
For each link (u,v) s.t. j is in r(u,v) {
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 23]
INTERNET-DRAFT TBRPF 28 November 2001
Remove j from r(u,v).
If pred(j,v) = u, set pred(j,v) = NULL. }
If (j = p(u) OR p(u) = NULL) {
Set tg_expire(u) = current_time + TOP_HOLD_TIME.
For each v s.t. (u,v) is in TG,
// Delete old reported links before adding new ones.
If reported(u,v) = 1, remove (u,v) from TG.
}
Process_Add_Update(j, update).
}
Process_Add_Update(j, update) {
// update = (subtype, ADD, n, NRL, NRNL, u, v_1,..., v_n)
For m = 1,..., n {
Let v = v_m.
Create an entry for v in TT if it does not exist.
Create an entry for v in TT_j if it does not exist.
Add j to r(u,v).
If (j = p(u) OR p(u) = NULL) {
Add (u,v) to TG.
Set reported(u,v) = 1.
}
// Process implicit delete
Set w = pred(j,v).
Set pred(j,v) = u.
If (w != NULL AND w != u) {
Remove j from r(w,v).
If (j = p(w)) remove (w,v) from TG.
}
If (m <= NRL) { // v is a reported leaf
Set leaf_update = (FULL, 0, 0, 0, u)
Process_Full_Update(j, leaf_update).
}
If (m > NRL + NRNL) { // v is not reported by j
Remove j from r(v).
Set rt_expire(j,v) = 0.
For each node w s.t. j is in r(v,w)
Remove j from r(v,w).
If (j = p(v))
For each node w s.t. (v,w) is in TG {
Set reported(v,w) = 0. // (v,w) is not reported by p(v)
Set nr_expire(u,v) = current_time + PER_UPDATE_INTERVAL.}
}
}
}
Process_Delete_Update(j, update) {
// update = (DELETE, n, NRL, NRNL, u, v_1,..., v_n)
For m = 1,..., n {
Let v = v_m.
Remove j from r(u,v).
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 24]
INTERNET-DRAFT TBRPF 28 November 2001
If pred(j,v) = u, set pred(j,v) = NULL.
If (j = p(u)) remove (u,v) from TG.
}
}
Link_Up(j) {
// Called when a link to j is discovered
If j is not in N {
Add j to N.
Add (i,j) to TG.
Set report(i,j) = 1.
}
}
Link_Down(j) {
// Called when the link to neighbor j is lost
If j is in N {
Remove j from N.
Remove (i,j) from TG.
If lost link is due to link-layer failure indication {
Update_Routes(i).
Update_RN(i).
Set msg_list = empty.
Generate_Diff_Update(i, msg_list).
Broadcast msg_list to neighbors.
Set old_T = T and old_RN = RN.
}
Else Update_Routes(i).
}
}
Expire_Links() {
For each node u in TT - i {
If (tg_expire(u) < current_time) {
For each v s.t. (u,v) is in TG,
Remove (u,v) from TG. }
Else for each v s.t. (u,v) is in TG {
If (report(u,v) = 0 AND nr_expire(u,v) < current_time)
Remove (u,v) from TG. }
For each node j in r(u) {
If (rt_expire(j,u) < current_time) {
Remove j from r(u).
For each link (u,v) s.t. j is in r(u,v)
Remove j from r(u,v). }}
}
}
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 25]
INTERNET-DRAFT TBRPF 28 November 2001
8.5. Configurable Parameters
This section lists the values of the parameters used in the descrip-
tion of the protocol, and their proposed default values.
MIN_UPDATE_INTERVAL (1 second)
PER_UPDATE_INTERVAL (5 seconds)
NON_REPORT_PENALTY (0.01)
9. Application of TBRPF In Mobile Ad-hoc Networks (MANETs)
The TBRPF routing protocols provide efficient proactive topology
discovery with dynamic adaptation to link state changes in both fixed
and mobile environments whether the topology is relatively static or
highly dynamic in nature. TBRPF is particularly well suited to MANETs
consisting of mobile nodes with wireless network interfaces operating
in peer-to-peer fashion over a multiple access communications channel
(e.g. the IEEE 802.11 Distributed Coordination Function (DCF) [13].)
Although applicable across a much broader field of use, TBRPF is par-
ticularly well suited for supporting the standard DARPA Internet pro-
tocols [10] [IPv6] as per current practices advocated by the IETF
MANET working group. In the following sections, we discuss practical
considerations the operation of TRBPF on MANETs.
9.1. Data Link Layer Assumptions
We assume a MANET data link layer that supports broadcast, multicast
and unicast addressing with best-effort (not guaranteed) delivery
services between neighbors (i.e. a pair of nodes within operational
communications range of one another). We further assume that each
interface belonging to a node in the MANET is assigned a unicast data
link layer address that is unique within that particular MANET. While
uniqueness for data link layer address assignments is not strictly
guaranteed, the assumption of uniqueness is consistent with current
practices for deployment of the Internet protocols on specific link
layers, e.g. [5]. Methods for duplicate data link layer address
detection and deconfliction are beyond the scope of this document.
9.2. Network Layer Assumptions
MANETs are formed as collections of MANET routers [14] and non-
routing nodes that use network layer addresses when calculating the
MANET topology. We assume that each node has at least one data link
layer interface (as described above) and that each such interface is
assigned a network layer address that is unique within the MANET.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 26]
INTERNET-DRAFT TBRPF 28 November 2001
(Methods for network layer address assignment and duplicate address
detection are beyond the scope of this document.) We further assume
that each node will select a unique ID for use in TBRPF protocol mes-
sages, which we refer to as the Router ID (RID) whether/not the node
acts as a MANET router. Finally, we assume that each MANET router
supports the multi-hop relay paradigm at the network layer; i.e. each
router provides an inter-node forwarding service via network layer
host routes which reflect the current MANET topology as perceived by
TBRPF.
9.3. Optional Automatic Address Resolution
TBRPF employs a proactive neighbor discovery protocol at the network
layer that maintains bi-directional link state for neighboring nodes
through the periodic transmission of messages. Since each neighbor
discovery message contains both the data link and network layer
address of the sender, implementations MAY OPTIONALLY employ
automatic network-to-data link layer address resolution for the nodes
with which they form links. An implementation may use such a mechan-
ism to avoid additional message overhead and potential for packet
loss associated with on-demand address resolution mechanisms such as
ARP [9] or IPv6 Neighbor Discovery [DISC]. Since this behavior is
optional, however, implementations MUST respond to on-demand address
resolution requests in the normal manner.
9.4. Support for Multiple Interfaces and/or Alias Addresses
MANET nodes may comprise multiple interfaces; each with a unique net-
work layer address. Additionally, MANET nodes may wish to publish
*alias* addresses such as when multiple network layer addresses are
assigned to the same interface or when the MANET node is serving as a
Mobile IP [MobileIP] home agent for nodes that send binding updates
from foreign networks. Multiple interfaces and network layer alias
addresses will be handled in a manner similar to that described in
section A.4.8 of [OSPFv6], i.e. bindings between the MANET node's
RID and any additional network layer addresses will be established. A
future version of this draft will specify a new message format and
protocol extension to support this function.
9.5. Support for Hierarchical Network Prefixes
MANET routers may wish to advertise hierarchical network prefixes
which the router discovered via attached networks, route redistribu-
tions from other routing protocols, or other means. Hierarchical net-
work prefixes will be handled in a manner similar to that described
in section A.4.9 of [OSPFv6], i.e. bindings between the MANET node's
RID and any hierarchical network prefixes will be established. A
future version of this draft will specify a new message format and
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 27]
INTERNET-DRAFT TBRPF 28 November 2001
protocol extension to support this function.
9.6. Support for non-MANET Hosts
Non-MANET hosts may establish connections to MANET routers through
on-demand mechanisms such as ARP or IPv6 Neighbor Discovery. Such
connections do not constitute a MANET link and therefore are not
reported in TBRPF topology updates. Future versions of this draft
will specify methods for incorporating non-MANET hosts, such as
requiring that MANET routers initiate periodic Neighbor Unreachabil-
ity Detection to such hosts to detect connection failures.
9.7. Internet Protocol Considerations
As with [OSPF], TBRPF packets are sent directly over the Internet
Protocol's network layer and are encapsulated solely by IP and local
data-link headers. An official IP Protocol number registration
[IANA] for TBRPF will be procured in due course. The same IANA regis-
tration will be used whether encapsulation is via IPv4 or IPv6. (IPv6
treats the IP protocol number as a "Next Header" designator). While
IP encapsulation is specified, implementations MAY OPTIONALLY employ
alternate data delivery services (e.g. UDP/IP, local data-link encap-
sulation) in private networks. The selection of an alternate data
delivery service MUST be consistent among all MANET routers in the
private network.
The following subsections discuss the operation of TBRPF over IPv4
and IPv6, respectively.
9.7.1. IPv4 Operation
When the IPv4 protocol is used, all TBRPF packets are sent to the
"All_MANET_Neighbors" multicast address (see: "IANA Considerations")
and thus reach all MANET routers within single-hop transmission range
of the sender. MANET routers MUST NOT forward packets sent to the
"All_MANET_Neighbors" multicast address. Since packet loss due to
link failure, interference, etc. can occur, implementations SHOULD
split large TBRPF protocol packets into several smaller packets to
avoid IPv4 fragmentation/reassembly. Since packets sent to
"All_MANET_Neighbors" are delivered only to single-hop neighbors,
Path MTU Discovery is not required. Instead, MANET routers can
derive the maximum TBRPF packet length(s) directly from the maximum
transmission unit(s) (MTUs) of their attached interface(s).
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 28]
INTERNET-DRAFT TBRPF 28 November 2001
9.7.2. IPv6 Operation
Transition mechanisms described in the IETF NGTRANS working group
(e.g. ISATAP) enable IPv6 operation over IPv4 routing infrastruc-
tures. ISATAP [19] can be used on TBRPF MANETs to enable automatic
IPv6-in-IPv4 operation regardless of route changes due to mobility.
Future versions of this draft will specify a native IPv6 capability
for TBRPF using mechanisms similar to those specified in [OSPFv6].
Packet formats which implement such mechanisms will use 4-octet
router ID's instead of 16-octet IPv6 addresses for greater effi-
ciency.
10. IANA Considerations
An official IANA IP protocol number assignment is required for TBRPF
protocol messages. Additionally, an IANA IPv4 multicast address
assignment for "All_MANET_Neighbors" is required from the range of
addresses between 224.0.0.0 and 224.0.0.255 inclusive. This range of
addresses is reserved for the use of routing protocols and other
low-level topology discovery or maintenance protocols, such as gate-
way discovery and group membership reporting. Multicast routers
should not forward any multicast datagram with destination addresses
in this range, regardless of its TTL [12].
Note that such an IPv4 multicast address assignment may have general
application for MANET beyond its anticipated use for TBRPF. We there-
fore propose that MANET consider the procurement of an
"All_MANET_Neighbors" IPv4 multicast address from the range of
addresses between 224.0.0.0 and 224.0.0.255.
11. Implementation Status
The current version of TBRPF has been implemented in Linux and ns-2.
TBRPF version 1 (as described in version 0 of the draft) has been
implemented in the FreeBSD V3.2 operating system with the Merit
Multi-Threaded Routing Toolkit daemon (mrtd). The initial FreeBSD
V3.2 implementation has been in use for laboratory and fielded exper-
iments since June 1999.
TBRPF version 1 has been ported to Linux. The current port runs on
RedHat Version 7.0 and has been tested under multiple Linux kernel
releases including 2.2.16 and a 2.4 pre-release. Additionally, the
Linux and FreeBSD ports are fully interoperable under TBRPF Version
1.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 29]
INTERNET-DRAFT TBRPF 28 November 2001
12. Patent Rights Statement
SRI International has filed one or more patents protecting the inven-
tions described in this submission. If SRI's submission (or portions
thereof) is accepted and becomes part of the IETF standard, then SRI
will grant royalty-free permission under such patents for both com-
mercial and non-commercial uses, to the extent necessary for compli-
ance with the standard. Any aspects or variants of SRI's submission
that are not included in the IETF standard and/or are not necessary
for compliance with the standard may require an additional license
from SRI under terms to be negotiated by the parties.
13. Acknowledgments
The authors would like to thank ASEO for funding this work, and the
following people for helping in the development of TBRPF: Yonael
Gorfu and Julie S. Wong.
14. References
[1] Bhargav Bellur and Richard G. Ogier. A Reliable, Efficient
Topology Broadcast Protocol for Dynamic Networks. Proc. IEEE
INFOCOM '99, New York, March 1999.
[2] Scott Bradner. Key words for use in RFCs to Indicate Require-
ment Levels. RFC 2119, March 1997.
[3] M. Scott Corson and Joe Macker. Mobile Ad hoc Networking
(MANET): Routing Protocol Performance Issues and Evaluation Con-
sideration. RFC 2501, 1999.
[4] J.J. Garcia-Luna-Aceves and M. Spohn. Efficient Routing in
Packet-Radio Networks Using Link-State Information. Proc. IEEE
WCNC '99, September 1999.
[5] C. Hornig. Standard for the Transmission of IP Datagrams over
Ethernet Networks. STD0041, April 1984.
[6] David B. Johnson and David A. Maltz. Protocols for Adaptive
Wireless and Mobile Networking. IEEE Personal Communications,
Vol. 3, No. 1, pp 34-42, February 1996.
[7] Richard G. Ogier. Efficient Routing Protocols for Packet-Radio
Networks Based on Tree Sharing. Proc. Sixth IEEE Intl. Workshop
on Mobile Multimedia Communications (MOMUC'99), November 1999.
[8] Charles E. Perkins, Elizabeth M Royer, and Samir R. Das. Ad Hoc
On-Demand Distance Vector (AODV) Routing. draft-ietf-manet-
aodv-05.txt, March 2000 (work in progress).
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 30]
INTERNET-DRAFT TBRPF 28 November 2001
[9] D.C. Plummer. An Ethernet address resolution protocol: Or con-
verting network protocol addresses to 48.bit Ethernet addresses
for transmission on Ethernet hardware. RFC 826, November 1982.
[10] J. Postel. Internet Protocol. RFC 791, September 1981.
[11] J. Postel. User Datagram Protocol. RFC 768, August 1980.
[12] J. Reynolds and J. Postel. Assigned Numbers. RFC 1700, October
1994.
[13] Wireless LAN Medium Access Control (MAC) and Physical Layer
(PHY) Specifications, ISO/IEC Std. 8802-11, ANSI/IEEE Std
802.11, 1999.
[14] An Internet MANET Encapsulation Protocol (IMEP) Specification,
draft-ietf-manet-imep-spec-01.txt
[15] S. Deering and R. Hinden. Internet Protocol Version 6 (IPv6)
Specification. RFC 2460, December 1998.
[16] S. Corson. MANET Routing Protocol Applicability Statement,
draft-ietf-manet-appl-00.txt, November 1998 (work in progress).
[17] J. Moy. OSPF Version 2. RFC 1583, March 1994.
[18] P. Jacquet et al. Optimized Link State Routing Protocol,
draft-ietf-manet-olsr-04.txt, March 2001 (work in progress).
[19] F. Templin. "Intra-Site Automatic Tunnel Addressing Protocol
(ISATAP)", draft-ietf-ngtrans-isatap-02.txt (work in progress)
[20] D. Bertsekas and R. Gallager. Data Networks, Prentice-Hall,
1987.
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 31]
INTERNET-DRAFT TBRPF 28 November 2001
Authors' Addresses
Bhargav Bellur
SRI International
333 Ravenswood Ave.
Menlo Park, CA 94025
USA
Phone: +1 650 859-6335
Fax: +1 650 859-4812
Email: bhargav@erg.sri.com
Richard Ogier
SRI International
333 Ravenswood Ave.
Menlo Park, CA 94025
USA
Phone: +1 650 859-4216
Fax: +1 650 859-4812
Email: ogier@erg.sri.com
Fred L. Templin
SRI International
333 Ravenswood Ave.
Menlo Park, CA 94025
USA
Phone: +1 650 859-3144
Fax: +1 650 859-4812
Email: templin@erg.sri.com
Ogier, Templin, Bellur, Lewis Expires 28 May 2002 [Page 32]