INTERNET-DRAFT Bhargav Bellur
Richard G. Ogier
Fred L. Templin
SRI International
11 July 2000
Topology Broadcast based on Reverse-Path Forwarding (TBRPF)
<draft-ogier-manet-tbrpf-00.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
Topology Broadcast based on Reverse-Path Forwarding (TBRPF) is a
link-state routing protocol designed for use in a mobile ad-hoc
network (MANET) or an internet. TBRPF provides each node with the
state of each link in the network, but does so much more efficiently
than flooding (e.g., OSPF). TBRPF uses the concept of reverse-path
forwarding to efficiently and reliably broadcast each link-state
update along the minimum-hop-path tree rooted at the source of the
update. The broadcast trees (one tree per source) are updated
dynamically using the topology information that is received along the
trees themselves, thus requiring very little additional overhead for
maintaining the trees. This document describes TBRPF and discusses
details for the implementation of TBRPF in IPv4-based MANETs.
Bellur, Ogier, and Templin Expires 11 January 2001 [Page i]
INTERNET-DRAFT TBRPF 11 July 2000
Contents
Status of This Memo ............................................. i
Abstract ........................................................ i
1. Introduction ................................................. 1
2. Assumptions and Terminology .................................. 3
3. Conceptual Data Structures and Messages ...................... 3
4. TBRPF Operation .............................................. 6
4.1. TBRPF Pseudocode ........................................ 9
5. Link-Level Functions ......................................... 11
5.1. Neighbor Discovery ...................................... 11
5.2. Reliable Link-Level Transmission of Control Messages .... 12
6. TBRPF Implementation for IPv4-based MANETs ................... 16
6.1. Data Link Layer Assumptions ............................. 16
6.2. Internetworking Assumptions ............................. 17
6.3. TBRPF Neighbor Discovery in IPv4 MANETs ................. 18
6.4. TBRPF Protocol Messages in IPv4 MANETs .................. 21
7. IANA Considerations .......................................... 32
8. Security Considerations ...................................... 32
9. Implementation Status ........................................ 32
References ...................................................... 33
Authors' Addresses .............................................. 34
Bellur, Ogier, and Templin Expires 11 January 2001 [Page ii]
INTERNET-DRAFT TBRPF 11 July 2000
1. Introduction
This document describes the Topology Broadcast based on Reverse-Path
Forwarding (TBRPF) protocol [1], developed in the DARPA Small Unit
Operations (SUO) program. TBRPF addresses the problem of efficient
routing in a communication network, where by efficient we mean that
the amount of update and control traffic required to maintain shor-
test (or nearly shortest) paths to all destinations is minimized.
This problem is important if the network incurs frequent topology and
link-cost changes, or must use links of limited bandwidth, or if the
network is very large (for scalable routing). In particular, this
problem is important for mobile ad-hoc networks (MANETs).
Routing protocols can be classified as proactive protocols, in which
each node maintains paths at all times to all possible destinations,
and reactive (or on-demand) protocols, in which paths are found
(using route discovery) only when they are required. TBRPF is a
proactive, link-state protocol, as are flooding (e.g., OSPF) and STAR
(Source Tree Adaptive Routing) [4]. Examples of reactive protocols
are DSR [6] and AODV [8].
Reactive protocols tend to be more efficient when route requests are
infrequent, while proactive protocols tend to be more efficient when
route requests are frequent (since route discovery typically involves
flooding). In addition, the delay required by reactive protocols for
route discovery may be too large for some applications. Therefore,
the best solution may be a hybrid routing solution that combines
proactive and reactive techniques, or a protocol that changes dynami-
cally between proactive and reactive methods, based on network meas-
urements. TBRPF can be used as the proactive part of such a hybrid
solution.
Routing protocols can also be classified according to whether they
find optimal (shortest) routes or suboptimal routes. By not requir-
ing routes to be optimal, it is possible to reduce the amount of con-
trol traffic (including routing updates) necessary to maintain the
routes. However, optimal routes are desirable because they minimize
delay and the amount of resources (e.g., bandwidth and power) con-
sumed. TBRPF computes optimal routes based on the advertised link
states; however, the advertised link states themselves may be approx-
imate in order to reduce the frequency at which each link is updated.
TBRPF is a full-topology link-state protocol: each node is provided
with the state of each link in the network (or within a cluster if
hierarchical routing is used). Flooding is another full-topology
link-state protocol, but is very inefficient due to the following
redundancies: (1) updates are sent over multiple paths to each node;
and (2) every node forwards every update to all neighbors, even if
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 1]
INTERNET-DRAFT TBRPF 11 July 2000
none or only one neighbor needs to receive it. TBRPF removes these
redundancies, thus providing the same routing information as flooding
with much greater efficiency. In fact, in simulation experiments
[7], TBRPF generated up to 85% less update/control traffic than an
efficient version of flooding.
Full-topology link-state protocols have the following advantages over
partial-topology protocols: (1) alternate paths and disjoint paths
are immediately available, allowing faster recovery from failures and
topology changes; and (2) paths can be computed subject to any combi-
nation of quality-of-service (QoS) constraints and objectives. Exam-
ples of partial-topology link-state protocols include STAR and OLSR.
These protocols provide each node with sufficient topology informa-
tion to compute at least one path to each destination.
TBRPF uses the concept of reverse-path forwarding to broadcast each
link-state update in the reverse direction along the spanning tree
formed by the minimum-hop paths from all nodes to the source of the
update. That is, each link-state update is broadcast along the
minimum-hop-path tree rooted at the source of the update. The broad-
cast trees (one tree per source) are updated dynamically using the
topology information that is received along the trees themselves,
thus requiring very little additional overhead for maintaining the
trees. (The fact that this is possible in a dynamic network is a new
result.) Minimum-hop-path trees are used because they change less
frequently than shortest-path trees based on a metric such as delay.
Based on the information received along the broadcast trees, each
node computes its parent and children for the broadcast tree rooted
at each source u. Each node forwards updates originating from source
u to its children on the tree rooted at source u. TBRPF achieves
reliability despite topology changes, using sequence numbers. The
correctness of TBRPF has been proven [1].
For point-to-point links (or receiver-directed transmissions), each
link-state update is sent on only |V|-1 tree links in TBRPF versus
approximately |E| links for flooding, where |V| and |E| are the
number of nodes and links, respectively. For networks that allow
broadcast transmissions, a node having no children for source u is a
leaf and need not forward updates generated by u. In typical net-
works, most nodes are leaves. In addition, a node having only only
one child for source u can send the updates generated by u to only
that child (receiver directed), instead of broadcasting the updates
to all neighbors.
TBRPF can be easily extended to hierarchical link-state routing, in
which the network is divided into areas or clusters. However, in
this paper we focus on flat (non-hierarchical) networks. Because
TBRPF reduces update traffic dramatically compared to flooding, they
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 2]
INTERNET-DRAFT TBRPF 11 July 2000
can be used instead of hierarchical routing or in combination with
hierarchical routing, to reduce update traffic more than is possible
by using hierarchical routing alone.
2. Assumptions and Terminology
TBRPF requires very few assumptions regarding the network model.
TBRPF can operate in any internet or subnet in which IP hosts are
connected through broadcast or point-to-point links to routers. The
current implementation of TBRPF operates on top of IP, similarly to
an internet routing protocol such as OSPF. TBRPF can operate in ad-
hoc networks that use different medium access control (MAC) proto-
cols, which need not permit promiscuous listening of transmissions.
To describe TBRPF, the topology of a network is modeled as a directed
graph G = (V, E), where V is the set of nodes and E is the set of
edges or links. Each node has a unique identifier and represents a
router that runs TBRPF. In a wireless network, a node can have con-
nectivity with multiple nodes over a single physical radio link. We
consider two nodes u and v to be adjacent (i.e., neighbors) if each
node can reliably receive messages from the other. Thus, we map a
physical broadcast link connecting multiple nodes into multiple
point-to-point bidirectional links. Such a bidirectional link
between two nodes u and v is represented by a pair of links (u,v) and
(v,u). Each link has a positive cost that can vary in time, and the
cost of (u,v) may be different from that of (v,u). Each router u is
responsible for updating and reporting the cost and up/down status of
each outgoing link (u,v) to neighbors. TBRPF can also support the
broadcast of multiple link costs (or link metrics) for purposes of
quality-of-service routing.
TBRPF uses a neighbor discovery protocol based on hello packets to
establish links to new neighbors and to detect link failures. TBRPF
supports both unicast transmissions (e.g., point-to-point or receiver
directed), in which a packet reaches only a single neighbor; and
broadcast transmissions, in which a single packet is transmitted
simultaneously to all neighbors. In particular, TBRPF allows an
update to be sent either on a common broadcast channel or on one or
more unicast channels, depending on the number of neighbors that need
to receive the update.
3. Conceptual Data Structures and Messages
A link-state update reporting the state of the link (u,v) is a tuple
(u,v,c,sn), where c and sn are the cost and the sequence number
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 3]
INTERNET-DRAFT TBRPF 11 July 2000
associated with the update. A cost of infinity represents a failed
link. We say that node u is the head node of link (u,v). It is the
only node that can report changes to parameters of link (u,v). There-
fore, any link-state update (u,v,c,sn) originates from node u.
Each node i maintains a counter SN_i, which is incremented by at
least one each time the cost of one or more outgoing links (i,v)
changes value. For example, SN_i can be a time stamp that represents
the number of seconds (or other units of time) elapsed from some
fixed time. When node i generates a link-state update (i,v,c,sn),
the sequence number sn is set to the current value of SN_i. We note
that, unlike most link-state protocols, TBRPF does not require link-
state updates to contain an age field.
TBRPF stores the following information at each node i of the network:
1. A topology table, denoted TT_i, consisting of all link-states
stored at node i. The entry for link (u,v) in this table is
denoted TT_i(u,v) and consists of the most recent update
(u,v,c,sn) received for this link. The components c and sn of the
entry for link (u,v) will be denoted TT_i(u,v).c and TT_i(u,v).sn.
TBRPF can optionally support the dissemination of multiple link
metrics, in which case the single cost c would be replaced by a
vector of multiple metrics.
2. The list of neighbor nodes, denoted N_i.
3. The following is maintained for each node u not equal to i:
a. The parent, denoted p_i(u), which is the neighbor of i that is
the next node on the minimum-hop path from node i to node u, as
obtained from TT_i.
b. A list of children, denoted children_i(u).
c. The sequence number of the most recent link-state update ori-
ginating from node u received by node i, denoted sn_i(u).
d. The routing table entry for node u, consisting of the next node
on the preferred path to u.
We note that the routing table entry for node u can be equal to the
parent p_i(u) if minimum-hop routing is used for data packets. How-
ever, in general, the routing table entry for node u is not p_i(u),
since the selection of routes for data traffic can be based on any
objective.
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 4]
INTERNET-DRAFT TBRPF 11 July 2000
TBRPF uses the following message types. Message formats for the
current implementation of TBRPF are specified in Section 6. However,
as TBRPF is work in progress, message formats are subject to change.
Link-State Update (LSU)
A message containing one or more link-state updates (u,v,c,sn).
NEW PARENT
A message informing a neighbor that it has been selected as a
parent with respect to one or more sources.
CANCEL PARENT
A message informing a neighbor that it is no longer a parent
with respect to one or more sources.
HELLO
A message sent periodically by each node i for neighbor
discovery.
NEIGHBOR
A message sent in response to a HELLO message.
NEIGHBOR ACK
A message sent in response to a NEIGHBOR message.
ACK
A link-level acknowledgment to a unicast transmission.
NACK
A link-level negative acknowledgment reporting that one or more
update messages sent on the broadcast channel were not
received.
RETRANSMISSION OF BROADCAST
A retransmission, on a unicast channel, of link-state updates
belonging to an update message for which a NACK was received.
HEARTBEAT
A message sent periodically on the broadcast channel when there
are no updates to be sent on this channel, used to achieve
reliable link-level broadcast of update messages based on
NACKs.
END OF BROADCAST
A message sent to a neighbor over a unicast channel, to report
that updates originating from one or more sources are now being
sent on the unicast channel instead of the broadcast channel.
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 5]
INTERNET-DRAFT TBRPF 11 July 2000
4. TBRPF Operation
This section describes the network-level operation of TBRPF, with the
aid of the pseudocode given at the end of the section. The next sec-
tion describes the link-level functions of TBRPF, i.e., neighbor
discovery and reliable transmission of control packets. Examples
illustrating the operation of TBRPF and the the proof of correctness
for TBRPF can be found in [1].
For a given node u, the parents p_i(u) for all i not equal to u
define a minimum-hop spanning tree rooted at u (assuming the protocol
has converged). The basic idea of TBRPF is to broadcast link-state
updates generated by u along this spanning tree, while at the same
time modifying this tree based on the link-state information received
along the tree.
To simplify the presentation, we assume that the sequence number
space is large enough so that wraparound does not occur. However, if
a smaller space is used, wraparound can be handled by employing
infrequent periodic updates with a period that is less than half the
minimum wraparound period, and by using a cyclic comparison of
sequence numbers: i.e., sn is considered less than sn' if either sn
< sn' and their difference is less than half the largest possible
sequence number, or sn' < sn and their difference is greater than
half the largest possible sequence number.
A node selects a neighbor as the parent for source src by sending a
NEW PARENT(src, sn) message containing the identity of node src and
the sequence number sn = sn_i(src). A node cancels an existing
parent by sending a CANCEL PARENT(src) message containing the iden-
tity of the source. Consequently, the set of children,
children_i(src), at node i with respect to node src is the set of
neighbors from which it has received a NEW PARENT message with source
src. In general, a node will simultaneously select a neighbor as the
parent for multiple sources, so that it sends a NEW PARENT(src_list,
sn_list) message to the new parent, where src_list is the list of
sources and sn_list is the corresponding list of sequence numbers.
Similarly, a CANCEL PARENT message will generally contain a list of
sources.
The broadcast of link-state information is achieved in the following
manner. Any link-state update originating from node src is accepted
by node i if (1) it is received from the parent node p_i(src), and
(2) it has a larger sequence number than the corresponding link-state
entry in the topology table at node i. If accepted, the link-state
update is entered into the topology table of node i, and then for-
warded to every node in children_i(src) (see the procedures
Update_Topology_Table and Process_Update).
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 6]
INTERNET-DRAFT TBRPF 11 July 2000
Whenever its topology table changes, a node recomputes its parent
with respect to every source node (see the procedure Update_Parents).
This happens when the node receives a topology update, establishes a
link to a new neighbor, or detects the failure or change in cost of a
link to an existing neighbor. A node computes its parents by (1)
computing minimum-hop paths to all other nodes using Dijkstra's algo-
rithm, and then (2) selecting the parent for each source src to be
the next node on the min-hop path to src (see the procedure
Compute_New_Parents).
Then, if the parent p_i(src) has changed, node i sends the message
CANCEL PARENT(src) to the current (old) parent if it exists. It also
sends the message NEW PARENT(src, sn) to the newly computed parent if
it exists, where sn = sn_i(src) is the sequence number of the most
recent link-state update originating from node src received by node
i. This number indicates the "position" up to which node i has
received updates from the old parent, and after which the new parent
should commence.
Upon receiving the CANCEL PARENT(src) message, the old parent k
removes node i from the list children_k(src). Upon receiving the NEW
PARENT(src, sn) message, the new parent j = p_i(src) adds node i to
the list children_j(src) and sends to node i a link-state update mes-
sage consisting of all the link states originating from node src in
its topology table which have sequence number greater than sn (see
the procedure Process_New_Parent). Thus, only updates not yet known
to node i are sent to node i.
When a node i detects the existence of a new neighbor nbr, it exe-
cutes Link_Up(i, nbr) to process this newly established link. The
link cost and sequence number fields for this link in the topology
table at node i are updated. Then, the corresponding link-state
message is sent to all neighbors in children_i(i). As noted above,
node i also recomputes its parent node p_i(src) for every node src,
in response to this topological change. In a similar manner, when
node i detects the loss of connectivity to an existing neighbor nbr,
it executes Link_Down(i, nbr). Link_Change(i, nbr) is likewise exe-
cuted at node i in response to a change in the cost to an existing
neighbor node nbr. However, this procedure does not recompute
parents.
The method for assigning costs to links is beyond the scope of this
specification. As an example, the cost of a link could simply be one
(for min-hop routing), or the link delay plus a constant bias.
We assume that, initially, a node has no links to neighbors, and that
its topology table is empty. Also initially, at each node i,
p_i(src) = NULL (i.e., not defined), children_i(src) is the empty
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 7]
INTERNET-DRAFT TBRPF 11 July 2000
set, and sn_i(src) = 0 for every node src. Every node then executes
Link_Up to process each link established with a neighbor, which will
result in a NEW PARENT message being sent to each neighbor. Since
each neighbor j of node i is (trivially) the next node on the min-hop
path from i to j, p_i(j) = j whenever j is a neighbor of i. There-
fore, the NEW PARENT message sent to a new neighbor j contains j (and
possibly other sources) in its source list.
It is helpful to understand how TBRPF works when initially all nodes
of an ad-hoc network have no topology information. Each node i will
first select each of its neighbor j as a new parent p_i(j) for source
j. Then each neighbor j will inform node i of its outgoing links,
which will allow node i to compute min-hop paths, and thus new
parents p_i(u), for all sources u that are two hops away. Then each
parent p_i(u) for each such u will inform node i of node u's outgoing
links, which will allow node i to compute new parents for all sources
that are three hops away. This process continues until node i has
computed parents for all sources u.
TBRPF does not require an age field in link-state updates. However,
failed links (represented by an infinite cost) and links that are
unreachable (i.e., links (u,v) such that p_i(u) = NULL) are deleted
from the topology table after MAX_AGE seconds (e.g., 1 hour) in order
to conserve memory. The reason these updates are not deleted immedi-
ately is as follows. Failed links (u,v) must be maintained for some
time in the topology table to ensure that a node i that changes its
parent p_i(u) near the time of failure (or had no parent p_i(u) dur-
ing the failure) is informed of the failure by the new parent.
Unreachable links, i.e., links (u,v) such that i and u are on dif-
ferent sides of a network partition, are maintained for a period of
time to avoid having to rebroadcast the old link state for (u,v)
throughout i's side of the partition, if the network partition recov-
ers soon (which is likely to happen if the network partition is
caused by a marginal link that oscillates between the up and down
states). This property is important to ensure the efficiency of
TBRPF when network partitions are common.
A node that is turned off (or goes to sleep) operates as if the links
to all neighbors have gone down. Thus, the node remembers the link-
state information it had when it was turned off. Since all such
links are either down or unreachable, these link states are deleted
from the topology table if the node awakens after being in sleep mode
for more than MAX_AGE seconds.
Periodic updates are not strictly required for the correctness of
TBRPF. However, we allow infrequent periodic updates to correct
errors that may occur in table entries or update messages. (See
Send_Periodic_Updates.) As discussed above, periodic updates are
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 8]
INTERNET-DRAFT TBRPF 11 July 2000
also useful if the sequence number space is not large enough to avoid
wraparound.
TBRPF provides each node with complete link-state information. Each
node can then apply a path selection algorithm to compute preferred
paths to all possible destinations, and to update these paths when
link states are updated. The default path selection algorithm for
TBRPF is to apply Dijkstra's algorithm to compute shortest paths
(with respect to c) to all destinations. However, TBRPF can employ
any path selection algorithm. Once preferred paths are computed, the
routing table entry for node u is set to the next node on the pre-
ferred path to u. If min-hop routing is desired, then the routing
table entry for u can be set to the parent p_i(u). In the current
implementation of TBRPF, data packets are forwarded based on the
routing table as in IP routing. However, source routing can also be
used.
4.1. Pseudocode
The following pseudocode describes the network-level procedures per-
formed at node i by TBRPF. The notation LSU(update_list) represents
a link-state-update message that includes the updates (u,v,c,sn) in
update_list.
Process_Update(i, nbr, in_message){
(Called when an update message in_message is received from nbr.)
Update_Topology_Table(i, nbr, in_message, update_list).
Update_Parents(i).
For each node src in TT_i {
Let update_list(src) consist of all tuples (k,l,c,sn)
in update_list such that k = src.
If update_list(src) is nonempty
Send message LSU(update_list(src)) to children_i(src).}}
Update_Topology_Table(i, nbr, in_message, update_list){
Set update_list to empty list.
For each ((u,v,c,sn) in in_message) {
If (p_i(u) == nbr) {
If ((u,v) is in TT_i and sn > TT_i(u,v).sn) {
Add (u,v,c,sn) to update_list.
Set TT_i(u,v).sn = sn.
Set TT_i(u,v).c = c.
If (sn > sn_i(u)) Set sn_i(u) = sn.}
If ((u,v) is not in TT_i) {
Add (u,v,c,sn) to TT_i.
Add (u,v,c,sn) to update_list.
If (sn > sn_i(u)) Set sn_i(u) = sn.}}}}
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 9]
INTERNET-DRAFT TBRPF 11 July 2000
Link_Change(i,j){
(Called when the cost of link (i,j) changes.)
If (|TT_i(i,j).c - cost(i,j)|/TT_i(i,j).c > epsilon) {
Set TT_i(i,j).c = cost(i,j).
Set TT_i(i,j).sn = current time stamp SN_i.
Set update_list = {(i, j, TT_i(i, j).c, TT_i(i, j).sn)}.
Send message LSU(update_list) to children_i(i).}}
Link_Down(i,j){
(Called when link (i,j) goes down.)
Remove j from N_i.
Set TT_i(i,j).c = infinity.
Set TT_i(i,j).sn = current time stamp SN_i.
Update_Parents(i).
For each (node src in TT_i) remove j from children_i(src).
Set update_list = {(i,j, infinity, TT_i(i,j).sn)}.
Send message LSU(update_list) to children_i(i).}
Link_Up(i,j){
(Called when link (i,j) comes up.)
Add j to N_i.
Set TT_i(i,j).c = cost(i,j).
Set TT_i(i,j).sn = current time stamp SN_i.
Update_Parents(i).
Set update_list = {(i, j, TT_i(i,j).c, TT_i(i,j).sn)}.
Send message LSU(update_list) to children_i(i).}
Update_Parents(i){
Compute_New_Parents(i).
For each (node k in N_i)
Set cancel_src_list(k), src_list(k), and sn_list(k) to empty.
For each (node src in TT_i such that src != i){
If (new_p_i(src) != p_i(src)){
If (p_i(src) != NULL){
Set k = p_i(src).
Add src to cancel_src_list(k).}
Set p_i(src) = new_p_i(src).
If (new_p_i(src) != NULL){
Set k = new_p_i(src).
Add src to src_list(k).
Add sn_i(src) to sn_list(k).}}}
For each (node k in N_i){
If (src_list(k) is nonempty)
Send message NEW PARENT(src_list(k), sn_list(k)) to k.
If (cancel_src_list(k) is nonempty)
Send message CANCEL PARENT(cancel_src_list(k)) to k.}}
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 10]
INTERNET-DRAFT TBRPF 11 July 2000
Compute_New_Parents(i){
For each (node src in TT_i such that src != i)
Set new_p_i(src) = NULL.
Compute min-hop paths using Dijkstra.
For each (node src in TT_i such that src != i)
Set new_p_i(src) equal to the neighbor of node i along the
minimum hop path from i to src.}
Process_New_Parent(i, nbr, src_list, sn_list){
(Called when node i receives a NEW PARENT(src_list, sn_list)
message from nbr.)
Set update_list to empty list.
For each (node src in src_list) {
Let sn_list.src denote the sequence number
corresponding to src in sn_list.
Add nbr to children_i(src).
Set new_updates = {(k,l,c,sn) in TT_i such that k = src
and sn > sn_list.src}.
Add new_updates to update_list.}
Send message LSU(update_list) to nbr.}
Process_Cancel_Parent(i,nbr,src_list )
(Called when node i receives a CANCEL PARENT(src_list)
message from nbr.)
For each (node src in src_list) remove nbr from children_i(src).
Send_Periodic_Updates(i){
Set update_list to empty.
For each (j in N_i such that TT_i(i,j). c != infinity){
Set TT_i(i,j).sn = current time stamp SN_i.
Add (i, j, TT_i(i,j).c, TT_i(i,j).sn) to update_list. }
Send message LSU(update_list) to children_i(i).}
5. Link-Level Functions
This section describes the link-level functions of TBRPF, i.e.,
neighbor discovery and the reliable link-level transmission of
control messages.
5.1. Neighbor Discovery
The neighbor discovery protocol detects the following events:
1. A link to a new neighbor is established,
2. The link to an existing neighbor goes down.
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 11]
INTERNET-DRAFT TBRPF 11 July 2000
Neighbor discovery uses the following three types of control
messages: HELLO, NEIGHBOR, and NEIGHBOR ACK. Every HELLO_INTVL
seconds, each node i transmits, on the broadcast channel, a HELLO
message containing the identity of node i. Upon receiving a HELLO
message from a new neighbor i, a node j responds with a NEIGHBOR mes-
sage containing the identity of node j. Finally, upon receiving the
NEIGHBOR message, node i sends to node j a NEIGHBOR ACK containing
the identity of node i. NEIGHBOR and NEIGHBOR ACK messages also con-
tain the current link-level sequence number for the broadcast channel
(discussed below). A link from node i to node j is established if
node i receives a NEIGHBOR packet or NEIGHBOR ACK from node j.
The link to an existing neighbor is declared to be down if no traffic
(including HELLO messages and ACKs) has been received from the neigh-
bor in the last LINKDOWN_INTVL seconds.
5.2. Reliable Link-Level Transmission of Control Messages
In most link-state routing protocols, e.g., OSPF, each node forwards
the same link-state information to all neighbors. In contrast, in
TBRPF each node sends each link-state update only to neighbors that
are children on the minimum-hop path tree rooted at the source of the
update. TBRPF can therefore utilize bandwidth more efficiently by
using unicast transmissions if only one child (or a few children)
exists for the update source, and broadcast transmissions when several
children exist for the update. Therefore, TBRPF uses a rule to
decide whether to use unicast or broadcast transmissions, depending
on the number of children and the total number of neighbors.
Updates with only one intended receiver (e.g., only one child),
should use unicast transmissions. Updates with several intended
receivers should use broadcast transmissions, to avoid transmitting
the message several times. Therefore, it is reasonable to use the
following simple transmission rule, where k is the number of intended
receivers: Use unicast if k = 1 and use broadcast if k > 1. This
simple rule has the following possible drawback, where n is the
number of neighbors. If k = 2 and n = 20, then 18 neighbors are
wasting time listening to a message not intended for them when they
could be sending or receiving another message. To avoid this draw-
back, another (optional) rule is to use broadcast if k > (n+1)/2 and
unicast otherwise. In general, any rule of the form k > g(n) can be
used. We note that, for update messages, the number of children k
may be different for different update sources. Therefore, it is pos-
sible to use unicast for some sources and broadcast for other
sources, and the transmission mode for a given source u, denoted
mode_i(u), can change dynamically between unicast and broadcast as
the number of children changes.
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 12]
INTERNET-DRAFT TBRPF 11 July 2000
While Link-State Update messages can be transmitted in either unicast
or broadcast mode, HELLO messages and HEARTBEAT messages (discussed
below) are always transmitted on the broadcast channel, and the fol-
lowing messages are always transmitted on the unicast channel (to a
single neighbor): NEIGHBOR, NEIGHBOR ACK, ACK, NACK, NEW PARENT,
CANCEL PARENT, RETRANSMISSION OF BROADCAST, END OF BROADCAST, and
Link-State Update messages sent in response to a NEW PARENT message.
The procedure for sending a Link-State Update message (that is not a
response to a NEW PARENT message) on the broadcast or unicast channel
is as follows:
If (mode_i(src) == BROADCAST)
Append the message update_msg to the message queue
associated with the broadcast channel.
If (mode_i(src) == UNICAST)
For (each node k in children_i(src))
Append the message update_msg to the message queue
associated with the unicast channel to node k.
The reliable unicast transmission of control packets MUST be pro-
vided, either by an underlying link-layer protocol or by TBRPF
itself. Any existing method for reliable link-layer unicast transmis-
sion can be used. Such methods typically use sequence numbers and
ACKs, in which a packet is retransmitted if an ACK for it is not
received within a given amount of time. The method used for reliable
unicast of control packets is not part of the TBRPF specification.
The following two subsections describe the mechanism for the reliable
transmission of update messages in broadcast mode, and the procedure
for dynamically selecting the transmission mode.
5.2.1. Reliable Transmission of Update Messages in Broadcast Mode
In this subsection, we describe the procedure for the reliable
transmission of Link-State Update messages in broadcast mode. A
broadcast update message includes one or more link-state updates,
denoted lsu(src), originating from sources src for which the
transmission mode is BROADCAST. Each broadcast control packet is
identified by a sequence number that is incremented each time a new
broadcast control packet is transmitted.
Before describing the procedure, we discuss a few of its properties.
NACKs are used instead of ACKs for reliable transmission, so that the
amount of ACK/NACK traffic is minimized if most transmissions are
successful. Suppose node i receives a NACK from a neighbor k for a
broadcast update message. Then all updates lsu(src) in the original
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 13]
INTERNET-DRAFT TBRPF 11 July 2000
message, for each node src such that k belongs to children_i(src),
are retransmitted (reliably) on the UNICAST channel to neighbor k,
in a RETRANSMISSION OF BROADCAST message. This message includes the
original broadcast sequence number to allow node k to process the
updates in the correct order.
The procedure for the reliable transmission of broadcast update pack-
ets uses the following message types (in addition to Link-State
Update messages): HEARTBEAT(sn), NACK(sn, bit_map), and RETRANSMIS-
SION OF BROADCAST(sn, update_msg). A NACK(sn, bit_map) message con-
tains the sequence number (sn) of the last received broadcast control
packet, and a 16-bit vector (bit_map) specifying which of the 16
broadcast control packets from sn-15 to sn have been successfully
received.
The description of the procedure at node i requires the following
notation:
Pkt(sn)
Control packet with sequence number sn transmitted on the
broadcast channel by node i.
MsgQ
Message queue for new control messages to be sent on the
broadcast channel from node i.
brdcst_sn_i
sequence number of the last packet transmitted on the broadcast
channel by node i.
Heartbeat_Timer
Timer used in the transmission of the Heartbeat message.
Following the transmission of the broadcast control packet
Pkt(brdcst_sn_i) on the broadcast channel, node i increments
brdcst_sn_i and reinitializes Heartbeat_Timer.
When Heartbeat_Timer expires at node i, the node appends the control
message HEARTBEAT(brdcst_sn_i) to the message queue associated with
the broadcast channel, and reinitializes Heartbeat_Timer.
When node i receives NACK(sn, bit_map) from node nbr, node i performs
the following:
For each (sn' not received as indicated by bit_map){
Let update_msg = {(src*, v*, sn*, c*) in Pkt(sn') such that
nbr is in children_i(src*)}.
Append the message RETRANSMISSION OF BROADCAST(sn', update_msg)
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 14]
INTERNET-DRAFT TBRPF 11 July 2000
to the message queue associated with the unicast channel to
node nbr. (Message must be sent even if update_msg is empty.)}
Upon receipt at node nbr of control packet Pkt(sn) transmitted on the
broadcast channel by node i, node nbr performs the following:
If the control packet Pkt(sn) is received in error{
Append the control message NACK(sn, bit_map) to the message
queue associated with the unicast channel to node i.}
If the control packet Pkt(sn) is received out of order (i.e.,
at least one previous sequence number is skipped){
Withhold the processing of the control packet Pkt(sn).
Append the control message NACK(sn, bit_map') to the message
queue associated with the unicast channel to node i.}
Else (control packet Pkt(sn) is received correctly and in order){
For each Link-State Update message update_msg in Pkt(sn), call
Process_Update(i, nbr, update_msg).}
When a link is established from node i to a new neighbor k, node i
obtains the current value of brdcst_sn_k from the NEIGHBOR message or
NEIGHBOR ACK that was received from node k.
5.2.2. Changing the Transmission Mode Between Unicast and Broadcast
This subsection describes the mechanism used by each node i to dynam-
ically select the transmission mode for link-state updates originat-
ing from each source node src. As discussed above, this decision
uses a rule of the form k > g(n), where k is the number of children
(for src) and n is the number of neighbors of node i. However, addi-
tional care must be taken to ensure that updates are received in the
correct order, or that the receiver has enough information to reorder
the updates. This is accomplished by sending an END OF
BROADCAST(last_seq_no, src) message on the unicast channel to each
child when the mode changes to UNICAST, and by waiting for all update
packets sent on unicast channels to be acked on before changing to
BROADCAST mode.
To facilitate this process, each node i maintains a binary variable
unacked_i(nbr, src) for each neighbor nbr and source src, indicating
whether there are any unacked control packets sent to nbr containing
link-state updates originating at node src. The following procedure
is executed periodically at each node i.
For each (node src){
If (mode_i(src) = BROADCAST and |children_i(src)| <= g(n)){
For each (node k in children_i(src)){
Append the message END OF BROADCAST(brdcst_sn_i, src) to the
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 15]
INTERNET-DRAFT TBRPF 11 July 2000
message queue associated with the unicast channel to node k.}
Set mode_i(src) = UNICAST.}
If (mode_i(src) = UNICAST and |children_i(src)| > g(n)){
Set switch_flag = YES.
For each (node k in children_i(src)){
If (unacked_i(k,src) = YES) Set switch_flag = NO.}
If (switch_flag = YES) Set mode_i(src) = BROADCAST.}}
6. TBRPF Implementation for IPv4-based MANETs
The TBRPF routing protocols provide automatic full topology discovery
with dynamic adaptation to link state changes in highly mobile
environments. TBRPF is particularly well suited to MANETs consisting
of mobile nodes with wireless data link interfaces operating in
peer-to-peer fashion over either a single multiple access communica-
tions channel or a collection of receiver directed point-to-point
channels with a multiple access broadcast channel. (An example of
the former is the IEEE 802.11 Distributed Coordination Function (DCF)
[13], in which the mobile nodes collectively arbitrate channel access
via a Carrier Sense, Multiple Access with Collision Avoidance
(CSMA/CA) strategy for all unicast, multicast and broadcast message
transmissions.) Additionally, TBRPF is particularly well suited for
carrying routing information that supports the standard DARPA Inter-
net protocols (IPv4) [10]. In the following sections, we discuss
assumptions for the data link layer, Internetworking assumptions, and
TBRPF neighbor discovery and routing protocol message transmission in
an Internet addressing environment.
6.1. Data Link Layer Assumptions
We assume a data link layer broadcast channel (*) with multiple
access capabilities, such that nodes wishing to transmit IPv4 broad-
cast and/or multicast messages must arbitrate with other nodes for
channel access before doing so. We further assume that messages
transmitted over the data link layer broadcast channel will be
received by only a proper subset of the collection of nodes on the
multiple access data link, due to wireless interface range limita-
tions, terrain features, and other hidden terminal conditions
incurred in a mobile environment. We consider a pair of nodes (A and
B) to have a bi-directional link (or simply "link") if and only if
both node A can receive messages sent from node B and node B can
receive messages sent from node A at a given instant in time.
(*) Some wireless data link layer protocols may provide point-to-
point receiver directed (unicast) channels which operate out-of-
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 16]
INTERNET-DRAFT TBRPF 11 July 2000
band with respect to the multiple access broadcast channel while
others (such as IEEE 802.11) utilize a single multiple access
channel for all unicast and broadcast/multicast message transmis-
sions.
While TBRPF can be readily applied to a fixed network (in which no
link state changes due to node mobility occur) such a static network
configuration merely represents a simplified case of the general
mobile ad-hoc network model. We therefore assume a highly dynamic
mobile environment at the data link layer, in which link state
changes occur frequently and rapidly. We further assume a data link
layer addressing scheme that supports broadcast, multicast and uni-
cast addressing with best-effort (not guaranteed) message delivery
services between nodes with instantaneous bi-directional links.
Finally, we assume that each node in the MANET has a unique data link
layer unicast address assignment. While uniqueness for data link
layer address assignments is difficult to guarantee, the assumption
of uniqueness is consistent with current practices for the deployment
of IPv4 on specific link layers, such as Ethernet [5]. Methods for
duplicate data link layer address detection and deconfliction are
beyond the scope of this document.
6.2. Internetworking Assumptions
While TBRPF can be readily extended to support hierarchical address-
ing compatible with the generalized Internet addressing architecture,
we assume a "flat" addressing scheme within a singe MANET. In the
flat addressing model, we assume that each node is assigned an IPv4
address [10] which presumably has some topological relevance to its
"home" MANET, but we do not assume that all nodes within the MANET
share a common IPv4 network prefix. While it may be reasonable to
assume that all nodes in a MANET might initially be assigned IPv4
addresses with a common network prefix, dynamic topology changes may
result in nodes leaving their home MANETs and subsequently joining
foreign MANETs. Such mobility factors may result in an heterogeneous
conglomerate of IPv4 network prefixes within a single MANET unless
some form of dynamic address assignment (or other address renumbering
method) is used. As with data link layer addressing, we assume that
each node in the MANET is assigned a unique IPv4 address, but we
require each node to provide a means for duplicate IPv4 address
detection. Again, methods for duplicate address deconfliction are
beyond the scope of this document.
While we make no assumptions regarding IPv4 network address prefix
assignments within a MANET, we assume that each node in the MANET
will participate in the TBRPF routing protocol scheme. Therefore,
since each node in the MANET participates in the TBRPF dynamic full
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 17]
INTERNET-DRAFT TBRPF 11 July 2000
topology discovery process, the requirement for on-demand discovery
through the Address Resolution Protocol (ARP) [9] is obviated. We
further assume that each node in the MANET supports the multi-hop
relaying paradigm; in other words, each node in the MANET must be
prepared to provide a third-party message relay service as dictated
by the instantaneous MANET topology. Finally, we note that the multi-
hop relay paradigm occurs at a lower network sub-layer than standard
Internet routing. The multi-hop relaying paradigm provides intra-
MANET message forwarding services, whereas standard Internet routing
provides message forwarding between distinct IPv4 networks.
6.3. TBRPF Neighbor Discovery in IPv4 MANETs
6.3.1. Address Resolution Extensions for TBRPF Neighbor Discovery
TBRPF is an automatic, full topology discovery protocol that provides
dynamic reaction to link state changes. TBRPF employs a neighbor
discovery protocol that dynamically establishes bi-directional links
and detects bi-directional link failures through the periodic
transmission of HELLO messages. Thus, since the TBRPF neighbor
discovery process is both automatic and continuous, we piggyback a
data link-to-IPv4 address resolution capability onto the neighbor
discovery protocol messages in MANET applications. Since address
resolution is built-in to the TBRPF neighbor discovery protocol, the
use of ARP [9] is deprecated for TBRPF-based MANETs. Additionally,
since link state changes occur dynamically, stale ARP cache issues
are avoided by handling address resolution from within the TBRPF
neighbor discovery protocol itself.
6.3.2. TBRPF Neighbor Discovery Message Transmission
As discussed in the previous section, TBRPF neighbor discovery is
responsible for both link state maintenance and data link-to-IPv4
address resolution in MANETs. Therefore, TBRPF neighbor discovery
operates as a data link level protocol on MANETs. In the future, a
new IANA [12] Ethernet protocol ID assignment for TBRPF neighbor
discovery will be procured. Currently, the Ethernet protocol ID
assignment for ARP (0x806) is used, since the use of ARP is depre-
cated for TBRPF-based MANETs.
As described in Section 5.1, TBRPF neighbor discovery message types
include HELLO, NEIGHBOR, and NEIGHBOR_ACK. TBRPF HELLO messages MUST
be sent to the data link level broadcast address, while NEIGHBOR and
NEIGHBOR_ACK messages MUST be sent to the data link level unicast
address of a neighboring node on the MANET. Implementations SHOULD
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 18]
INTERNET-DRAFT TBRPF 11 July 2000
detect the event of a data link-to-IPv4 address mapping change for
existing links. This may occur in one of the following instances:
1. Two or more nodes in the MANET are using the same IPv4 address.
2. An existing node in the MANET has changed its data link layer
address.
3. A new node is now using the IPv4 address of a former node which
MAY have left the MANET.
In case 1, the implementation SHOULD print some form of "duplicate
IPv4 address detected" message to the console. In cases 2 and 3, the
cached link state SHOULD be updated to reflect the new data link-to-
IPv4 address mapping.
6.3.3. TBRPF Neighbor Discovery Packet Format
We now present the packet format for the TBRPF HELLO, NEIGHBOR, and
NEIGHBOR_ACK neighbor discovery protocol messages on MANETs. Note
that the packet format is similar to the format used by ARP [9]. The
data link header for each message is not shown, since it is specific
to the underlying data link layer. TBRPF places no requirements on
the underlying data link layer other than those described under "data
link layer assumptions" above.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H/W Address Space | Protocol Address Space |
+-------------------------------+---------------+---------------+
| H/W Len (=n) | Proto Len (=m)| Type | BCAST Seq# |
+-------------------------------+---------------+---------------+
~ Sender Hardware Address (m bytes) ~
~ ... ~
+-------------------------------+-------------------------------+
~ Sender Protocol Address (n bytes) ~
~ ... ~
+-------------------------------+-------------------------------+
~ Target Hardware Address (m bytes) ~
~ ... ~
+-------------------------------+-------------------------------+
~ Target Protocol Address (n bytes) ~
~ ... ~
+-------------------------------+-------------------------------+
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 19]
INTERNET-DRAFT TBRPF 11 July 2000
Type (8 bits):
HELLO 10
NEIGHBOR 11
NEIGHBOR_ACK 12
BCAST Seq# (8 bits):
A sequence number from 0...15 (effectively, only 4 bits), used
in NEIGHBOR and NEIGHBOR_ACK messages as described in Section
5.1.
All Other Fields: Identical to their usage in ARP [9].
The TBRPF neighbor discovery protocol requires that each node in the
MANET MUST send periodic HELLO messages to the data link broadcast
address at HELLO_INTVL timeout intervals. (The HELLO_INTVL value MUST
be common to all nodes within a MANET, but different MANETs MAY use
different HELLO_INTVL values.) A node receiving a HELLO message from
a new neighbor MUST send a NEIGHBOR message to the new neighbor's
data link unicast address. Finally, a node receiving a NEIGHBOR mes-
sage from a new neighbor MUST send a NEIGHBOR_ACK message to the new
neighbor's data link unicast address.
As with standard ARP, the four address fields (sender hardware
address; sender protocol address; target hardware address; target
protocol address) facilitate the address resolution process. The
fields contain the following values, based on the TBRPF neighbor
discovery message opcode:
HELLO
Sender Hardware Address: data link address of sender
Sender Protocol Address: IPv4 address of sender
Target Hardware Address: data link broadcast address
Target Protocol Address: unused
NEIGHBOR
Sender Hardware Address: data link address of sender
Sender Protocol Address: IPv4 address of sender
Target Hardware Address: sender H/W Address from HELLO
Target Protocol Address: sender IPv4 Address from HELLO
NEIGHBOR_ACK
Sender Hardware Address: data link address of sender
Sender Protocol Address: IPv4 address of sender
Target Hardware Address: sender H/W address from NEIGHBOR
Target Protocol Address: sender IPv4 address from NEIGHBOR
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 20]
INTERNET-DRAFT TBRPF 11 July 2000
6.4. TBRPF Protocol Messages in IPv4 MANETs
TBRPF protocol messages are exchanged between current neighbor nodes
which have established bi-directional links and performed data link
to IPv4 address resolution via TBRPF neighbor discovery as described
in the previous section. IPv4 addresses are therefore available for
use as node IDs in TBRPF protocol messages. TBRPF protocol messages
are sent via the User Datagram Protocol (UDP) [11]. This approach
requires an official UDP service port number registration (see: IANA
Considerations). The use of UDP/IPv4 provides several advantages
over a data link level approach, including:
- IP segmentation/reassembly facilities
- UDP checksum facilities
- Simple application level access for routing daemons
- IPv4 multicast addressing for link state messages
TBRPF protocol messages are sent to either the IPv4 unicast address
of a current neighbor or the "All_TBRPF_Neighbors" IPv4 multicast
address (see: IANA Considerations). In most cases, a message SHOULD
be sent to the IPv4 unicast address of a current neighbor if ALL com-
ponents of the message pertain ONLY to that neighbor. Similarly, a
message SHOULD be sent to the All_TBRPF_Neighbors IPv4 multicast
address if the message contains components which pertain to more than
one neighbor neighbors. Receivers MUST be prepared to receive TBRPF
protocol messages sent either to their own IPV4 unicast address or
the All_TBRPF_Neighbors multicast address. Actual addressing stra-
tegies are highly dependent on the underlying data link layer. (**)
(**) For data links such as IEEE 802.11, a single, multiple access
channel is available for all unicast and broadcast/multicast mes-
sages. In such cases, since channel occupancy for unicast and
multicast messages is identical, it would seem frugal to send a
single message to the All_TBRPF_Neighbors multicast address rather
than multiple unicast messages even if the message contains com-
ponents which pertain to only a subset of the current neighbors.
In other cases, in which point-to-point receiver directed channels
are available, sending multiple unicast messages may reduce con-
tention on the multiple access broadcast channel. Specific link
layer strategies are beyond the scope of the current document.
6.4.1. Atomic TBRPF Message Format
Individual (atomic) TBRPF messages consist of a message header fol-
lowed by a message body. Atomic messages may be transmitted either
individually or as components of a compound TBRPF message consisting
of multiple atomic messages within a single UDP/IPv4 datagram. See
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 21]
INTERNET-DRAFT TBRPF 11 July 2000
Section 6.4.2 for the compound message format.
TBRPF message headers are either 32-bits or 64-bits in length depend-
ing on whether the atomic message is BROADCAST or UNICAST. The format
for the TBRPF message header (and a detailed description of the indi-
vidual fields) is 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Vers|M| Num_sources | Offset | LSEQ |
+---------------+---------------+-------------------------------+
| Identity of Receiver (ONLY present if M=UNICAST) |
+---------------------------------------------------------------+
where the header fields are defined as follows:
Type (4 bits):
The atomic message type. The following types are currently
defined:
ACK 1
NACK 2
NEW_PARENT 3
CANCEL_PARENT 4
HEARTBEAT 5
END_OF_BROADCAST 6
LINK_STATE_UPDATE_A 7
LINK_STATE_UPDATE_B 8
RETRANSMISSION_OF_BROADCAST 9
Version (3 bits):
The TBRPF protocol version field provides a transition mechan-
ism for future versions of the TBRPF protocol. Also provides a
sanity check for host software to identify bogus messages pur-
porting to be TBRPF control messages. We currently define a
single value for TBRPF version 1:
TBRPFVERSION_1 1
Mode (1 bit):
The transmission mode for this atomic TBRPF message; either
UNICAST or BROADCAST. UNICAST refers to an atomic message which
must be processed by only a single neighbor. BROADCAST refers
to an atomic message which must be processed by ALL neighbor
nodes. (NB: For IPv4 MANETs, UNICAST implies a specific IPv4
unicast address while BROADCAST implies the All_TBRPF_Neighbors
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 22]
INTERNET-DRAFT TBRPF 11 July 2000
IPv4 multicast address.) The following mode bits are defined:
UNICAST 0
BROADCAST 1
Messages of type ACK, NACK, NEW_PARENT, and CANCEL_PARENT MUST
be sent as UNICAST. Messages of type LINK_STATE_UPDATE_A and
LINK_STATE_UPDATE_B MAY be sent as either UNICAST or BROADCAST.
Messages of type RETRANSMISSION_OF_BROADCAST and
END_OF_BROADCAST MUST be sent as UNICAST.
Num_Sources (==m) (8 bits):
Number of sources 'm' included in the atomic message. Takes on
a value from 1...255 for messages of type: NEW_PARENT,
CANCEL_PARENT, LINK_STATE_UPDATE_A, and LINK_STATE_UPDATE_B.
All other message types SHOULD set Num_Sources = 0.
Offset (12 bits):
Offset (in bytes) from the 0'th byte of the current atomic
message header to the 0'th byte of the NEXT atomic message
header in the "compound message" (see the following section for
the compound message specification.) Offset == 0 indicates no
further atomic messages follow. The 12-bit offset field imposes
a 4 kilobyte length restriction on individual atomic messages.
LSEQ (4 bits):
The link sequence number for this message.
Identity of Receiver (32 bits):
The IPv4 address of the receiving node which MUST process this
atomic message. All other nodes MUST NOT process this atomic
message. This field exists ONLY if the M bit is set to UNICAST.
6.4.2. Compound TBRPF Message Format
Multiple atomic TBRPF messages may be concatenated to form a compound
message within a single UDP/IPv4 packet. Atomic message headers MUST
be aligned on 32-bit boundaries, therefore an atomic message body
with a non-integral number of 32-bit words will include 1, 2 or 3
padding bytes preceding a subsequent message header. NO additional
header is required for a compound message; the header from the 1st
atomic message serves as the initial header for the compound message.
The format for a compound TBRPF message is shown below (where N is
the number of concatenated atomic messages):
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 23]
INTERNET-DRAFT TBRPF 11 July 2000
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ TBRPF atomic message header (1) ~
+---------------------------------------------------------------+
| |
~ TBRPF atomic message body (1) ~
~ (variable length) ~
~ +---------------+
| |PAD (0-3 bytes)|
+-----------------------------------------------+---------------+
~ TBRPF atomic message header (2) ~
+---------------------------------------------------------------+
| |
~ TBRPF atomic message body (2) ~
~ (variable length) ~
~ +---------------+
| |PAD (0-3 bytes)|
+---------------+---------------+---------------+---------------+
~ ... ~
~ ... ~
~ ... ~
+---------------+---------------+---------------+---------------+
~ TBRPF atomic message header (N) ~
+---------------+---------------+-------------------------------+
| |
~ TBRPF atomic message body (N) ~
~ (variable length) ~
~ ~
| (NO Padding bytes required on final message body) |
+---------------+---------------+---------------+---------------+
6.4.3. TBRPF Atomic Message Body Format
The format of the atomic message body depends on the 'Type' field in
the corresponding message header. The following sections define the
formats for atomic message bodies for TBRPF Version 1.
6.4.3.1. ACK
The ACK message carries a NULL message body. The 4-bit acknowledgment
sequence number (from 0...15) is carried in the TBRPF message header
LSEQ field.
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 24]
INTERNET-DRAFT TBRPF 11 July 2000
6.4.3.2. NACK
0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bitmap |
+-------------------------------+
Bitmap (16 bits):
A 16-bit vector; bits indicate messages lost/received for the 16
messages prior to the 4-bit sequence number supplied in the TBRPF
message header LSEQ field. As described in Section 5.2.1, the
LSEQ field is set to the sequence number of the last broadcast
control message received from the neighbor to which the NACK is
being sent.
6.4.3.3. NEW_PARENT:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identity for Src(1) |
+-------------------------------+-------------------------------+
| Identity for Src(2) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Identity for Src(m) |
+-------------------------------+-------------------------------+
| Sequence Number for Src(1) | Sequence Number for Src(2) |
+-------------------------------+-------------------------------+
| Sequence Number for Src(3) | Sequence Number for Src(4) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Sequence Number for Src(m-1) | Sequence Number for Src(m) |
+-------------------------------+-------------------------------+
Identity for Src(i) (32 bits):
The IPv4 address of the ith Source (1 <= i <= m)
Sequence Number for Src(i) (16 bits):
A sequence number from 0...65535
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 25]
INTERNET-DRAFT TBRPF 11 July 2000
NB: The above diagram shows the message format for 'm' being an even
number. For 'm' being an odd number, the message ends as follows:
~ ... ~
+-------------------------------+-------------------------------+
| Sequence Number for Src(m-2) | Sequence Number for Src(m-1) |
+-------------------------------+-------------------------------+
| Sequence Number for Src(m) |
+-------------------------------+
6.4.3.4. CANCEL_PARENT:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identity for Src(1) |
+-------------------------------+-------------------------------+
| Identity for Src(2) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Identity for Src(m) |
+-------------------------------+-------------------------------+
Identity for Src(i) (32 bits):
The IPv4 address of the ith Source (1 <= i <= m)
6.4.3.5. HEARTBEAT
0
0 1 2 3 4 5 6 7 8
+-+-+-+-+-+-+-+-+
|BCAST Sequence#|
+---------------+
Sequence # for BCAST Channel (8 bits):
A sequence number from 0...15 (effectively, only 4 bits)
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 26]
INTERNET-DRAFT TBRPF 11 July 2000
6.4.3.6. END_OF_BROADCAST
0
0 1 2 3 4 5 6 7 8
+-+-+-+-+-+-+-+-+
|BCAST Sequence#|
+---------------+
Sequence # for BCAST Channel (8 bits):
A sequence number from 0...15 (effectively, only 4 bits)
6.4.3.7. LINK_STATE_UPDATE_A
TBRPF provides two formats for link-state update messages. Messages
of type LINK_STATE_UPDATE_A include a single sequence number per
source, and is therefore used only if the updates for all links com-
ing out of the same source have the same sequence number. (For exam-
ple, periodic updates have this property.) This is done to reduce
the message size. Messages of type LINK_STATE_UPDATE_B include a
separate sequence number for each link.
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
*********************** lsuA for Src(1) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identity of node Src(1) |
+-------------------------------+-------------------------------+
| Num_Neighbors (==k[1]) | Sequence Number for Src(1) |
+-------------------------------+-------------------------------+
| Identity for Nbr(1) of Src(1) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(1) of Src(1) |
+-------------------------------+-------------------------------+
| Identity for Nbr(2) of Src(1) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(2) of Src(1) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Identity for Nbr(k[1]) of Src(1) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(k[1]) of Src(1) |
+-------------------------------+-------------------------------+
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 27]
INTERNET-DRAFT TBRPF 11 July 2000
*********************** lsuA for Src(2) *************************
+-------------------------------+-------------------------------+
| Identity of node Src(2) |
+-------------------------------+-------------------------------+
| Num_Neighbors (==k[2]) | Sequence Number for Src(2) |
+-------------------------------+-------------------------------+
| Identity for Nbr(1) of Src(2) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(1) of Src(2) |
+-------------------------------+-------------------------------+
| Identity for Nbr(2) of Src(2) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(2) of Src(2) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Identity for Nbr(k[2]) of Src(2) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(k[2]) of Src(2) |
+-------------------------------+-------------------------------+
~ ... ~
~ ... ~
*********************** lsuA for Src(m) *************************
+-------------------------------+-------------------------------+
| Identity of node Src(m) |
+---------------------------------------------------------------+
| Num_Neighbors (==k[m]) | Sequence Number for Src(m) |
+---------------------------------------------------------------+
| Identity for Nbr(1) of Src(m) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(1) of Src(m) |
+-------------------------------+-------------------------------+
| Identity for Nbr(2) of Src(m) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(2) of Src(m) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Identity for Nbr(k[m]) of Src(m) |
+-------------------------------+-------------------------------+
| Metrics for Nbr(k[m]) of Src(m) |
+-------------------------------+-------------------------------+
Each lsuA for Src(i), for (1 <= i <= m), contains:
Identity for Src(i) (32 bits):
The IPv4 address of Src(i)
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 28]
INTERNET-DRAFT TBRPF 11 July 2000
Num_Neighbors (==k[i]) (16 bits):
The number of neighbors 'k[i]' of Src(i)
Sequence Number for Src(i) (16 bits):
A sequence number from 0...65535
Identity for Nbr(j), for (1 <= j <= k[i]) (32 bits):
The IPv4 address of Nbr(j) of Src(i)
Link Metrics for Nbr(j), for (1 <= j <= k[i]) (32 bits):
The link metrics associated with Nbr(j) of Src(i)
6.4.3.8. LINK_STATE_UPDATE_B
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
*********************** lsuB for Src(1) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identity of node Src(1) |
+---------------------------------------------------------------+
| Num_Neighbors (==k[1]) | Reserved |
+---------------------------------------------------------------+
| Identity for Nbr(1) of Src(1) |
+-------------------------------+-------------------------------+
| Link Metrics for Nbr(1) | Sequence # for Src(1),Nbr(1) |
+-------------------------------+-------------------------------+
| Identity for Nbr(2) of Src(1) |
+-------------------------------+-------------------------------+
| Link Metrics for Nbr(2) | Sequence # for Src(1),Nbr(2) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Identity for Nbr(k[1]) of Src(1) |
+-------------------------------+-------------------------------+
| Link Metrics for Nbr(k) | Sequence # for Src(1),Nbr(k) |
+-------------------------------+-------------------------------+
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 29]
INTERNET-DRAFT TBRPF 11 July 2000
*********************** lsuB for Src(2) *************************
+-------------------------------+-------------------------------+
| Identity of node Src(2) |
+---------------------------------------------------------------+
| Num_Neighbors (==k[2]) | Reserved |
+-------------------------------+-------------------------------+
| Identity for Nbr(1) of Src(2) |
+-------------------------------+-------------------------------+
| Link Metrics for Nbr(1) | Sequence # for Src(2),Nbr(1) |
+---------------------------------------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Identity for Nbr(k[m-1]) of Src(m-1) |
+-------------------------------+-------------------------------+
| Link Metrics for Nbr(k[m-1]) | Seq. # for Src(m), Nbr(k[m-1])|
+-------------------------------+-------------------------------+
~ ... ~
~ ... ~
~ ... ~
*********************** lsuB for Src(m) *************************
+-------------------------------+-------------------------------+
| Identity of node Src(m) |
+---------------------------------------------------------------+
| Num_Neighbors (==k[m]) | Reserved |
+---------------------------------------------------------------+
| Identity for Nbr(1) of Src(m) |
+-------------------------------+-------------------------------+
| Link Metrics for Nbr(1) | Sequence # for Src(m),Nbr(1) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| Identity for Nbr(k[m]) of Src(m) |
+-------------------------------+-------------------------------+
| Link Metrics for Nbr(k[m]) | Seq. # for Src(m),Nbr(k[m]) |
+-------------------------------+-------------------------------+
Each lsuB for Src(i), for (1 <= i <= m), contains:
Identity for Src(i) (32 bits):
The IPv4 address of Src(i)
Num_Neighbors (==k[i]) (16 bits):
The number of neighbors 'k[i]' of Src(i)
Identity for Nbr(j), for (1 <= j <= k[i]) (32 bits):
The IPv4 address of Nbr(j) of Src(i)
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 30]
INTERNET-DRAFT TBRPF 11 July 2000
Link Metrics for Nbr(j), for (1 <= j <= k[i]) (16 bits):
The link metrics associated with Nbr(j) of Src(i) (really, only
8 bits are used)
Sequence # for Src(i), Nbr(j) for (1 <= j <= k[i]) (16 bits):
Sequence number associated with link Src(i), Nbr(j)
6.4.3.9. RETRANSMISSION_OF_BROADCAST
The RETRANSMISSION_OF_BROADCAST message provides the retransmission
of a compound update message in response to a NACK message. As
described in Section 5.2.1, broadcast update messages are retransmit-
ted only on unicast channels. The compound message has the same form
as that shown in Section 6.4.2, and may contain one or more atomic
messages of type LINK_STATE_UPDATE_A or LINK_STATE_UPDATE_B con-
catenated together.
The compound message is preceded by an atomic message header, where
LSEQ is the sequence number corresponding to the unicast channel on
which the message is sent. The LSEQ of each atomic message in the
compound message is the broadcast sequence number that was included
in the original (broadcast) transmission of the message. Multiple
RETRANSMISSION_OF_BROADCAST messages can be bundled into a compound
message as described in Section 6.4.2.
The RETRANSMISSION_OF_BROADCAST message 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 | Vers|M| Num_sources | Offset | LSEQ |
+-------------------------------+-------------------------------+
| |
~ Compound Message ~
| |
+-------------------------------+-------------------------------+
where the header fields have the following values:
Type (4 bits):
MUST be set to RETRANSMISSION_OF_BROADCAST (=9).
Version (3 bits):
Set to TBRPFVERSION_1 (=1) for the initial version.
Mode (1 bit):
MUST be set to UNICAST (=0).
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 31]
INTERNET-DRAFT TBRPF 11 July 2000
Num_Sources (8 bits):
SHOULD be set to 0.
Offset (16 bits):
Offset (in bytes) from the 0'th byte of the current compound
message header to the 0'th byte of the NEXT compound message
header in the RETRANSMISSION_OF_BROADCAST message. Allows con-
catenation of compound messages up to 64 kilobytes in length.
7. IANA Considerations
An application of TBRPF for IPv4-based MANETs will require the fol-
lowing assigned number procurements from IANA:
1. an official IPv4 multicast address assignment for
All_TBRPF_Neighbors,
2. an official UDP service port number for TBRPF protocol messages,
3. an official ETHERTYPE assignment for TBRPF Neighbor Discovery.
As an alternative to 3., TBRPF could continue to use the existing
ETHERTYPE assignment for ARP and new ARP opcodes could be reserved
for the three TBRPF neighbor discovery message types presented in
Section XXX. It must be noted, however, that TBRPF neighbor discovery
and ARP are mutually exclusive. TBRPF neighbor discovery is NOT an
extension of ARP.
8. Security Considerations
Authentication issues exist for allowing "foreign" nodes to join a
MANET via TBRPF neighbor discovery. Additionally, privacy issues
exist for any networking protocols run over unencrypted wireless data
links such as IEEE 802.11. Finally, denial-of-service attacks are
possible if rogue nodes join a TBRPF MANET and offer to provide a
multi-hop relay service, but then fail to perform the service when it
is required. We believe that IPSec may be useful in addressing
some/all of these issues.
9. Implementation Status
The current version of the TBRPF protocol as it applies to IPv4
MANETs (as described in this document) has been implemented in the
FreeBSD V3.2 operating system with the Merit Multi-Threaded Routing
Toolkit daemon (mrtd). The current implementation has been in use for
laboratory and fielded experiments since June 1999.
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 32]
INTERNET-DRAFT TBRPF 11 July 2000
10. 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).
[9] David C. Plummer. An Ethernet address resolution protocol: Or
converting 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.
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 33]
INTERNET-DRAFT TBRPF 11 July 2000
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
Bellur, Ogier, and Templin Expires 11 January 2001 [Page 34]