INTERNET-DRAFT Bhargav Bellur
Richard G. Ogier
Fred L. Templin
SRI International
2 March 2001
Topology Broadcast Based on Reverse-Path Forwarding (TBRPF)
<draft-ietf-manet-tbrpf-01.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
proactive, link-state routing protocol designed for use in mobile
ad-hoc networks. TBRPF has two modes: full topology (FT) and partial
topology (PT). TBRPF-FT uses the concept of reverse-path forwarding
to reliably and efficiently broadcast each topology update in the
reverse direction along the dynamically changing broadcast tree
formed by the min-hop paths from all nodes to the source of the
update. TBRPF-PT achieves a further reduction in control traffic,
especially in large, dense networks, by providing each node with the
state of only a relatively small subset of the network links,
sufficient to compute minimum-hop paths to all other nodes. In both
the FT and PT modes, a node forwards an update only if the node is
not a leaf of the broadcast tree rooted at the source of the update.
In addition, in the PT mode, a node forwards an update only if it
results in a change to the node's source tree. As a result, each
node reports only changes to a relatively small portion of its source
tree.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page i]
INTERNET-DRAFT TBRPF 2 March 2001
Contents
Status of This Memo ............................................... i
Abstract .......................................................... i
1. Introduction ................................................... 1
2. Changes ........................................................ 2
3. TBRPF Terminology .............................................. 3
4. Applicability Section .......................................... 4
4.1. Networking Context ........................................ 4
4.2. Protocol Characteristics and Mechanisms ................... 4
5. Neighbor Discovery ............................................. 6
5.1. Overview .................................................. 7
5.2. Neighbor Table ............................................ 8
5.3. Sending HELLO Messages .................................... 9
5.4. Processing a Received HELLO Message ....................... 9
5.5. Processing a Received UPDATE REQUEST Message .............. 10
5.6. Processing a received UPDATE REPLY message ................ 10
5.7. Sending an UPDATE REQUEST message ......................... 11
5.8. Expiration of the Timer nbr_life .......................... 11
5.9. Events Causing a Link to be Declared Down ................. 11
6. Reliable Delivery to Neighbors ................................. 12
6.1. Reliable, Sequenced Delivery Using NACKs .................. 12
6.2. Reliable Delivery Using ACKs .............................. 13
7. TBRPF-PT ....................................................... 14
7.1. Conceptual Data Structures and Messages ................... 15
7.2. Operation of TBRPF-PT ..................................... 16
7.2.1. Computing the Source Tree ............................ 17
7.2.2. Generating Tree Updates .............................. 17
7.2.3. Updating Parents ..................................... 18
7.2.4. Sending NEW PARENT Messages .......................... 18
7.2.5. Processing TREE UPDATE Messages ...................... 18
7.2.6. Processing NEW PARENT Messages ....................... 19
7.2.7. Processing a New Neighbor ............................ 19
7.2.8. Processing a Lost Neighbor ........................... 20
7.2.9. Packet Forwarding .................................... 20
7.3. Pseudocode for TBRPF-PT ................................... 20
7.4. Configurable Parameters ................................... 23
Bellur, Ogier, and Templin Expires 2 September 2001 [Page ii]
INTERNET-DRAFT TBRPF 2 March 2001
8. TBRPF-FT ....................................................... 23
8.1. Conceptual Data Structures and Messages ................... 24
8.2. Operation of TBRPF-FT ..................................... 26
8.3. Pseudocode for TBRPF-FT ................................... 30
8.4. Configurable Parameters ................................... 34
9. Application of TBRPF In Mobile Ad-hoc Networks (MANETs) ........ 34
9.1. Data Link Layer Assumptions ............................... 35
9.2. Internetworking Assumptions ............................... 36
9.3. Address Resolution Extensions for TBRPF Neighbor Discovery. 36
10. TBRPF Packets and TBRPF Protocol Messages ..................... 37
10.1. TBRPF Packet Header ...................................... 39
10.2. TBRPF Packet Body ........................................ 42
11. IANA Considerations ........................................... 69
12. Security Considerations ....................................... 70
13. Implementation Status ......................................... 70
Acknowledgments ................................................... 70
References ........................................................ 70
Bellur, Ogier, and Templin Expires 2 September 2001 [Page iii]
INTERNET-DRAFT TBRPF 2 March 2001
1. Introduction
TBRPF is a proactive, link-state routing protocol designed for mobile
ad hoc networks. It maintains optimal paths to all destinations at
all times, unlike on-demand routing protocols. It does not require
the periodic broadcast of topology information, unlike OLSR [18].
Instead, only differential changes in topology are reported in order
to minimize overhead. TBRPF has two modes: full topology (FT) and
partial topology (PT).
TBRPF-FT uses the concept of reverse-path forwarding to reliably
broadcast each topology update in the reverse direction along the
dynamically changing broadcast tree formed by the min-hop paths from
all nodes to the source of the update. Each node is thus provided
with the state of each link in the network. Since the leaves of the
broadcast tree rooted at a particular source do not forward updates
originating from that source, a dramatic reduction in control traffic
is achieved compared to link-state flooding (e.g., OSPF), as shown in
simulations [7]. TBRPF-FT is recommended for sparse networks and
when full topology information is needed (e.g., if multiple paths
need to be computed to each destination). A previous version of
TBRPF-FT (called just TBRPF) was presented in [1].
TBRPF-PT achieves a further reduction in control traffic, especially
in large, dense networks, by providing each node with the state of
only a relatively small subset of the network links, sufficient to
compute minimum-hop paths to all other nodes. As in the FT mode, a
node forwards an update only if the node is not a leaf of the broad-
cast tree rooted at the source of the update. In addition, a node
forwards an update only if it results in a change to the node's
source tree (which provides min-hop paths to all other nodes). As a
result, each node reports only changes to a relatively small portion
of its source tree, in contrast to FTSP [7] and STAR [4], in which
each node reports changes to its entire source tree.
TBRPF-PT also allows the computation of *approximately* optimal paths
(with the degree of approximation determined by a configurable param-
eter), in order to achieve a further reduction in control traffic and
scalability to networks having a large diameter.
TBRPF-PT has some features in common with PTSP (Partial Tree Sharing
Protocol) [7], which also has the property that each node reports
changes to a small portion of its source tree. However, in PTSP, a
node sends each update only to a subset of neighbors (the children
with respect to the broadcast tree), whereas TBRPF-PT takes advantage
of the broadcast nature of wireless networks by sending each update
to *all* neighbors. Also PTSP does not allow path optimality to be
traded off to reduce control traffic. (We note that PTSP allows the
computation of shortest paths with respect to any metric, but control
traffic is reduced significantly if min-hop paths are computed.)
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 1]
INTERNET-DRAFT TBRPF 2 March 2001
The FT and PT modes of TBRPF use the same neighbor discovery protocol
(TND). TND is a new protocol whose HELLO messages are much smaller
than existing neighbor discovery protocols such as the one use by
OSPF [17]. A HELLO message in TND contains only the IDs of nodes
that have recently been heard but with which a 2-way link has not yet
been established. In contrast, a HELLO message in OSPF contains the
IDs of *all* neighbors, resulting in a much larger message, espe-
cially in dense networks. The use of TND thus contributes to the
efficiency of TBRPF. In addition, since HELLO messages are smaller,
they can be sent more frequently, resulting in a faster response to
topology changes.
TBRPF can easily be extended to hierarchical 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, it 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. Changes
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 mes-
sage 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
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 2]
INTERNET-DRAFT TBRPF 2 March 2001
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 fol-
lowing 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.
topology update or link-state update (LSU)
A message or part of a message that reports a state change for one
or more links.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 3]
INTERNET-DRAFT TBRPF 2 March 2001
update source
The node that originated a given topology update.
broadcast tree
A directed tree rooted at an update source that is used to
broadcast topology updates in TBRPF-FT.
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. It is also the node
preceding node i in the broadcast tree rooted at u.
child
The inverse of the parent relationship. A node j is a child of
node i for source u if and only if node i is the parent of node j
for source u.
leaf
A node is a leaf of the broadcast tree rooted at source u if it
has no children for source 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.
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].
4.1. Networking Context
TBRPF-PT is appropriate for large, dense networks, including networks
with a large diameter, in which only min-hop routing is needed and
bandwidth or power is limited. Simulation experiments are needed to
determine the range of network parameters, such as degree of mobility
and number of communicating pairs, for which TBRPF-PT performs better
than on-demand protocols.
TBRPF-FT is appropriate for sparse networks, and when full topology
information is useful, such as for computing multiple disjoint paths
or paths subject to quality-of-service objectives and constraints.
4.2. Protocol Characteristics and Mechanisms
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 4]
INTERNET-DRAFT TBRPF 2 March 2001
* 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 a HELLO message periodically. Topology
updates and other messages are transmitted only when the topology
changes.
* Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?)
The protocol provides reliable, sequenced delivery of topology
updates using NACKs. It also provides reliable delivery of other
messages using ACKs.
* 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.
* Does the protocol support the IP addressing architecture? (if so,
how?)
Yes.
* Does the protocol require link or neighbor status sensing (if so,
how?)
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 5]
INTERNET-DRAFT TBRPF 2 March 2001
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 (FT and PT) 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 sleep-
ing nodes, and determining when a node can go into sleep mode
without partitioning the network.
* 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.
5. Neighbor Discovery
This section describes the TBRPF Neighbor Discovery (TND) protocol,
designed for mobile ad-hoc networks. The purpose of the protocol is
to allow each node in the network to quickly detect the neighboring
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 6]
INTERNET-DRAFT TBRPF 2 March 2001
nodes with which the node has a direct and symmetric 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 symmetric link to some neigh-
bor no longer exists.
TBRPF neighbor discovery operates correctly even under the following
harsh conditions: (1) an asymmetric (unidirectional) link can exist
between any two nodes at any time, (2) link states can change fre-
quently due to mobility and interference, and (3) the channel is
noisy so that not all transmitted packets are successfully received
by all neighbors.
The main advantage of TND over existing neighbor discovery protocols,
such as the one used by OSPF [OSPF], is that the average size of a
HELLO message is much smaller, resulting in reduced message overhead.
In addition, since HELLO messages are smaller, they can be sent more
frequently, resulting in a faster response to topology changes.
5.1. Overview
Each node transmits a HELLO message periodically, every
HELLO_INTERVAL seconds. Each HELLO message contains a list of node
IDs, called the neighbor request list, which includes neighbors from
which HELLO messages have recently been heard but for which a 2-way
link has not yet been established. (Message formats are given in
Section 10.2.) Upon receiving a HELLO message from a neighbor that
has not been heard from recently, a node includes the neighbor's ID
in each transmitted HELLO message until a 2-way indication (defined
below) is received from the neighbor, but for at most NBR_HOLD_TIME
seconds (typically equivalent to 3 HELLO messages).
A 2-way indication can be either a received HELLO that includes the
node's own ID, or an UPDATE REQUEST message. Upon receiving a 2-way
indication, the node sends an UPDATE REQUEST message to the new
neighbor and waits for the neighbor to respond with an UPDATE REPLY
message. The UPDATE REPLY message serves two purposes: (1) to confirm
that the other node agrees that the link is 2-way, and (2) for the
exchange of topology information.
Depending on the routing protocol, an update for the new link may be
generated upon receiving a 2-way indication, or (similarly to OSPF)
after topology information is exchanged (i.e., the UPDATE REPLY is
received). In this section, an "update" refers to a TREE UPDATE in
TBRPF-PT or an LSU in TBRPF-FT.
Upon receiving a 2-way indication from a new neighbor, the node
copies the current NACK sequence number (NSEQ) of the neighbor from
the packet, and thus becomes capable of sending a NACK when a missed
sequence number is detected. (The use of NSEQ is described in Sec-
tion 6.)
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 7]
INTERNET-DRAFT TBRPF 2 March 2001
If an UPDATE REQUEST message is retransmitted MAX_NUM_RXMT times to a
given neighbor, and no UPDATE REPLY is received from the neighbor,
the link is declared down and an update reporting the link failure is
sent reliably to all neighbors (using NACKs). If the neighbor that
was sent the UPDATE REQUEST message has already received a 2-way
indication, then it is capable of sending NACKs and will thus either
receive the update, or will declare the link down after sending a
NACK MAX_NUM_RXMT times, or will stop hearing HELLO messages and thus
declare the link down after NBR_HOLD_TIME seconds. In this manner,
both nodes will agree that the link is up if it is 2-way, and will
otherwise agree that the link is down.
If a link (i,j) has been up (2-way) for some time and then becomes
unidirectional from node i to node j, then node i will stop hearing
HELLO messages from node j, will declare the link down after
NBR_HOLD_TIME seconds, and will send an update reporting the link
failure. The neighbor will either receive the update or will declare
the link down after sending a NACK MAX_NUM_RXMT times. In this
manner, both nodes will agree that the link is down. The different
events that result in a link being declared down are listed in Sec-
tion 5.9.
The contents and formats of the UPDATE REQUEST and UPDATE REPLY mes-
sages depend on the routing protocol, and are different for the FT
and PT modes of TBRPF. These formats, and the specific procedures
for sending and processing these messages, are given in the sections
describing each mode of TBRPF. For the FT mode, the UPDATE REQUEST
and UPDATE REPLY messages are the same as the NEW PARENT and NEW
PARENT REPLY messages, respectively. This section describes the gen-
eral neighbor discovery procedure that is common to both the FT and
PT modes of TBRPF.
5.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 of the link to node j, which can
be LOST, 1-WAY, 2-WAY, or SYNC.
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_request_time(j) - The amount of remaining time (in seconds)
during which the ID of node j is included in each transmitted
HELLO message. Set to NBR_HOLD_TIME if a HELLO is received from
node j when nbr_level(j) = LOST.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 8]
INTERNET-DRAFT TBRPF 2 March 2001
The table entry for a neighbor j may be deleted at any time after
nbr_level(j) becomes LOST. The absence of an entry for a given node
j is equivalent to an entry with nbr_level(j) = LOST.
The four possible values of nbr_level(j) at node i have the following
meaning:
LOST
No HELLO message has been received from node j within the last
NBR_HOLD_TIME seconds.
1-WAY
The link is 1-way. A HELLO message was received recently from node
j, but the link is not 2-way.
2-WAY
The link is 2-way. Node i recently received from node j either a
HELLO message that contains the ID of node i, or an UPDATE REQUEST
message.
SYNC
An UPDATE REPLY message has been received from node j. The
topology information at the two nodes is consistent for routes
that pass through node j.
Depending on the routing protocol, an update reporting that the link
(i,j) is UP can be generated either when nbr_level(j) changes to 2-
WAY or when it changes to SYNC.
5.3. Sending HELLO Messages
Each node sends a HELLO message periodically every HELLO_INTERVAL
seconds, possibly with a small jitter. Each HELLO message includes a
(possibly empty) list (called the neighbor request list) including
the identities of all neighbors j such that nbr_level(j) = 1-WAY and
nbr_request_time(j) has not expired. In this manner, upon receiving
a HELLO message from a neighbor that has not been heard from
recently, the neighbor's ID is included in each HELLO message for at
most NBR_HOLD_TIME seconds (sooner if a 2-way indication is received
from the neighbor).
5.4. Processing a Received HELLO Message
Upon receiving a HELLO message from node j, node i performs the fol-
lowing steps:
1. If a neighbor table entry does not exist for node j, create one
with nbr_level(j) = LOST (temporarily).
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 9]
INTERNET-DRAFT TBRPF 2 March 2001
2. If nbr_level(j) = LOST, then set nbr_level(j) = 1-WAY and
nbr_request_time(j) = NBR_HOLD_TIME.
3. Set nbr_life(j) = NBR_HOLD_TIME.
4. If the ID of node i appears in the HELLO message, and nbr_level(j)
is not 2-WAY, then:
a. Set nbr_level(j) = 2-WAY
b. Send an UPDATE REQUEST message to node j (see the section below
on sending an UPDATE REQUEST message)
c. Copy the current NACK sequence number (NSEQ) of node j from the
TBRPF packet header.
d. An update reporting that link (i,j) is UP MAY be generated at
this time.
5.5. Processing a Received UPDATE REQUEST Message
Upon receiving an UPDATE REQUEST message from node j, node i performs
the following steps:
1. If nbr_level(j) is LOST or 1-WAY, then (the UPDATE REQUEST is a
2-WAY indication):
a. Set nbr_level(j) = 2-WAY
b. Send an UPDATE REQUEST message to node j
c. Copy the current NACK sequence number (NSEQ) of node j from the
TBRPF packet header.
d. An update reporting that link (i,j) is UP MAY be generated at
this time.
2. Send an UPDATE REPLY message to node j (same as NEW PARENT REPLY
message for the FT mode, details are given in the sections for
TBRPF-FT and TBRPF-PT).
5.6. Processing a Received UPDATE REPLY Message
Upon receiving an UPDATE REPLY message (or a NEW PARENT REPLY message
for the FT mode) from node j, node i performs the following steps:
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 10]
INTERNET-DRAFT TBRPF 2 March 2001
1. Set nbr_level(j) to SYNC.
2. An update reporting that link (i,j) is UP is generated if not
already generated when the link became 2-WAY.
3. Process the message as described in the sections for TBRPF-FT and
TBRPF-PT.
5.7. Sending an UPDATE REQUEST message
The contents of the UPDATE REQUEST message depends on the routing
protocol used. For TBRPF-FT, it is the same as a NEW PARENT message.
An UPDATE REQUEST message can be delayed, typically until the next
HELLO message is scheduled, in order to allow message aggregation.
An UPDATE REQUEST for a given neighbor j is retransmitted after
RXMT_INTERVAL if an UPDATE REPLY has not yet been received.
Node i performs the following steps if an UPDATE REQUEST has been
transmitted MAX_NUM_RXMT times to node j with no reply:
1. Generate an update reporting that link (i,j) is DOWN.
2. Set nbr_level(j) = LOST and nbr_life(j) = 0.
In Step 1, if node j has received a 2-WAY indication, then it is
capable of sending NACKs and will therefore receive the update
correctly, or will declare the link DOWN after sending MAX_NUM_RXMT
NACKs for this update. If node j receives the update, it will
declare link (j,i) DOWN.
5.8. Expiration of the Timer nbr_life
The timer nbr_life(j) is set to NBR_HOLD_TIME whenever a HELLO is
received from node j. If nbr_life(j) expires (becomes zero), node i
performs the following steps:
1. If nbr_level(j) is 2-WAY or SYNC, generate an update reporting
that link (i,j) is DOWN.
2. Set nbr_level(j) = LOST.
5.9. Events Causing a Link to be Declared Down
The following events at node i result in link (i,j) being declared
DOWN, if it is currently UP.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 11]
INTERNET-DRAFT TBRPF 2 March 2001
1. No HELLO message is received from node j for NBR_HOLD_TIME
seconds.
2. An update is received from node j reporting that link (j,i) is
DOWN.
3. An UPDATE REQUEST or NEW PARENT message is transmitted
MAX_NUM_RXMT times to node j, and no reply is received within
RXMT_INTERVAL of the last transmission.
4. A NACK is sent to node j for the same message MAX_NUM_RXMT times,
and the message is not received within RXMT_INTERVAL of the last
NACK.
5. A failure notification is received from the link layer (e.g.,
based on the maximum number of retransmissions being reached for a
data packet).
In each of these cases, an update is generated reporting the link
failure. In most cases, this update can be delayed (typically until
the next HELLO message) to allow message aggregation. However, since
a failure notification from the link layer implies that the link is
currently being used for data traffic, in this case the update is
sent immediately, subject to the minimum time between updates
(MIN_UPDATE_INTERVAL).
6. Reliable Delivery to Neighbors
A TBRPF packet can contain multiple messages, some of which must be
delivered reliably to some or to all neighbors. TBRPF uses NACKs to
deliver topology updates reliably and in the correct order to all
neighbors. Using NACKs results in less ACK/NACK overhead than using
ACKs if links are mostly reliable. A message that is sent reliably
using NACKs is called NACKable.
Some messages, such as NEW PARENT messages, are sent reliably to one
or more neighbors by requiring each intended recipient to send an ACK
or another message in response. Such a message will be called ACK-
able. The same TBRPF packet can contain NACKable and ACKable mes-
sages, together with messages that do not require reliable delivery
(e.g., HELLO, ACK). This section describes the procedures used by
TBRPF to provide reliable delivery using NACKs and ACKs.
6.1. Reliable, Sequenced Delivery Using NACKs
Each node maintains an 8-bit sequence number NSEQ, which is incre-
mented whenever a packet is sent that contains one or more new NACK-
able messages. Each NACKable message in a packet contains a sequence
number which is the value of NSEQ when the message was first
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 12]
INTERNET-DRAFT TBRPF 2 March 2001
transmitted. Each TBRPF packet also contains the current value of
NSEQ in its header, whether or not the packet contains any NACKable
messages. This allows each neighbor to determine the sequence
numbers of transmitted NACKable messages that it did not receive.
For example, if a node i receives a TBRPF packet from node j that
contains no NACKable messages and whose header contains NSEQ = 32,
and if the node i has not yet received any NACKable message from node
j with sequence number 32, then node i knows that it should have
received a packet from node j containing one or more NACKable mes-
sages with sequence number 32. Node i will then send a NACK message
to node j requesting the retransmission of these NACKable messages.
(Only the NACKable messages are retransmitted, not the entire
packet.)
NACKs and ACKs can be delayed (typically until the next HELLO is
scheduled) to allow message aggregation, in order to minimize the
number of packets transmitted. Thus, a single packet can contain
NACKs for several neighbors and for several sequence numbers per
neighbor. A NACK is retransmitted after RXMT_INTERVAL if no response
is received. If a NACK for a given neighbor and sequence number is
retransmitted MAX_NUM_RXMT times with no response, the link to the
neighbor is declared down.
Since since each TBRPF packet contains the latest value of NSEQ, each
node will learn this value for each neighbor whenever it receives a
HELLO message from the neighbor. Therefore, if node i sends a NACK-
able message that is not received by neighbor node j, then node j
will either detect the missed sequence number within NBR_HOLD_TIME
seconds, or will declare the link to node i down. If node j detects
the missed sequence number, it will send a NACK up to MAX_NUM_RXMT
times every RXMT_INTERVAL seconds. Therefore, a node that has sent a
NACKable message must store the message for NBR_HOLD_TIME +
MAX_NUM_RXMT * RXMT_INTERVAL seconds for possible retransmission.
6.2. Reliable Delivery Using ACKs
Each node maintains an 8-bit sequence number ASEQ, which is incre-
mented whenever a packet is sent that contains one or more new ACK-
able messages. Each ACKable message in a packet contains a sequence
number which is the value of ASEQ when the message was first
transmitted.
The intended recipients of an ACKable message is determined from the
contents of the message. For example, in TBRPF-PT a NEW PARENT mes-
sage must be ACKed by the new parent (whose ID is included in the
message) and the old parent (if it exists and is still a neighbor).
The ACK message includes the neighbor's ID and the value of ASEQ in
the received packet. A packet may contain multiple new ACKable mes-
sages having the same sequence number, along with retransmitted ACK-
able messages having older sequence numbers. A single ACK is used to
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 13]
INTERNET-DRAFT TBRPF 2 March 2001
acknowledge all ACKable messages having a given sequence number.
An ACKable message is retransmitted after RXMT_INTERVAL seconds if an
ACK for the message has not been received from each intended reci-
pient that is still a neighbor. If the message contains a list of
intended recipients, then the neighbors from which an ACK has been
received may be removed from this list in the retransmitted message.
If an ACK from an intended recipient is not received after the mes-
sage is retransmitted MAX_NUM_RXMT times, the link to that neighbor
is declared down. The message is discarded after an ACK has been
received from each intended recipient that is still a neighbor.
Since not all neighbors are required to receive each ACKable message,
the above mechanism does not ensure sequenced delivery, which may or
may not be required, depending on the protocol. Sequenced delivery
can be achieved by including additional sequence information in each
message, or by other means. A mechanism for ensuring that NEW PARENT
messages are processed in the correct order is described in Section
7.2.4.
7. TBRPF-PT
TBRPF-PT is a proactive, link-state routing protocol that provides
hop-by-hop routing along minimum-hop paths to each destination. Each
node running TBRPF-PT 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 called Restricted Approximate Dijkstra (RAD). RAD allows
path optimality to be traded off in order to reduce the amount of
control traffic in networks with a large diameter, where the degree
of approximation is determined by the configurable parameter
NONTREE_PENALTY.
Each node computes the next node p(u) on the computed path to each
destination (or update source) u, called the *parent* of the node for
source u, and informs its parent of this selection by sending a NEW
PARENT message, so that each parent becomes aware of its *children*
for each source u.
A link (u,v) in a node's source tree is defined to be *reportable* if
the node has at least one child for source u. A node reports changes
(additions and deletions) to the reportable portion of its source
tree in TREE UPDATE messages, which are sent reliably to all neigh-
bors using NACKs. In dense networks, most nodes will have no children
for a given source; thus, on average, a node will report only a small
portion of its source tree.
When a node discovers one or more new neighbors (using TND), an
UPDATE REPLY message is sent to inform the new neighbors of the
reportable portion of the node's source tree. To minimize the number
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 14]
INTERNET-DRAFT TBRPF 2 March 2001
of packets transmitted, multiple control messages are aggregated into
a single packet whenever possible. TBRPF-PT does not use per-source
sequence numbers for updates (unlike TBRPF-FT), and does not require
the periodic broadcast of topology updates (unlike OLSR).
7.1. Conceptual Data Structures and Messages
In addition to the information required by the neighbor discovery
protocol (Section 5) and for reliable, sequenced delivery (Section
6), each node running TBRPF-PT contains a topology table (TT) that
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, and 0
otherwise. The set of links in the source tree is denoted T.
r(u,v) - The list of neighbors that are currently reporting link
(u,v) in their source tree. The set of links reported by a given
neighbor j is denoted T(j). (Each node reports only part of its
source tree.)
r(u) - The list of neighbors that are reporting for source u,
i.e., that have at least one child for source u.
p(u) - The current parent for source u, equal to the next node on
the min-hop path to u.
prev_p(u) - The last parent for source u that was confirmed. A
new parent p(u) is confirmed when the list r(u) contains p(u). If
the current parent is confirmed, then prev_p(u) = p(u).
children(u) - The list of children for source u.
pred(u) - The node preceding node u in node i's source tree.
Equal to NULL if node u is not reachable.
next(u) - The next node on the min-hop path to desination u, used
for forwarding data packets. In the current version, next(u) is
always equal to p(u).
dist(u) - The number of hops on the shortest path to u.
Each node also maintains the following information:
N_i - the set of neighbors to which 2-way communication has been
established via the neighbor discovery protocol.
next_update_time - timer that specifies the earliest time the
source tree may next be updated.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 15]
INTERNET-DRAFT TBRPF 2 March 2001
update_flag - indicates whether the topology information has been
modified since the source tree was last updated.
TBRPF-PT uses the following message types, in addition to the HELLO,
ACK, and NACK messages described in other sections. All messages are
broadcast to all neighbors. Message formats are specified in Section
10.2.
TREE UPDATE
A message containing one or more updates of the form (u, v, ADD)
(u, v, DEL), (u, ADD), and/or (u, DEL), reporting that a link
(u,v) or a node u has been added to or deleted from the reportable
part of the router's source tree. This is the only NACKable
message type used by TBRPF-PT.
NEW PARENT
A message informing a neighbor that it has been selected as a
parent for one or more sources. Contains the ID of the neighbor
and a list of source nodes.
UPDATE REQUEST
A message requesting an UPDATE REPLY from one or more new
neighbors. Contains a list of neighbor IDs.
UPDATE REPLY
A message describing the reportable part of the router's source
tree to one or more new neighbors. Contains a list of neighbor IDs
and updates of the form (u, v, ADD) and (u, ADD).
7.2. Operation of TBRPF-PT
This section describes the operation of TBRPF-PT, with the aid of the
pseudocode given in the next section. The main computation of
TBRPF-PT occurs in the procedure Update_Source_Tree, which is called
after a TREE UPDATE message is received, either immediately or
delayed (typically until the next HELLO is scheduled) to allow mes-
sage aggregation. The variables update_flag and next_update_time are
used to determine whether an update has been received (update_flag =
1) and the next time that Update_Source_Tree should be executed if
update_flag = 1. The parameter MIN_UPDATE_INTERVAL determines the
minimum time between executions of Update_Source_Tree. However,
Update_Source_Tree SHOULD be executed immediately if a failure notif-
ication is received from the link layer.
Update_Source_Tree first calls Restricted_Approx_Dijkstra (RAD),
which computes the new source tree and new parents based on informa-
tion stored in the topology table. Generate_Tree_Updates is then
called to generate ADD and DELETE updates by comparing the new source
tree to the old one. (As described below, some delete updates are
implied.) Update_Parents is then called to generate NEW PARENT
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 16]
INTERNET-DRAFT TBRPF 2 March 2001
messages for parents that have changed. Finally, the generated TREE
UPDATE and NEW PARENT messages are sent. Whenever possible, these
messages are aggregated with a HELLO message into a single packet, in
order to minimize the number of transmitted packets.
Each TBRPF packet is broadcast to all neighbors. TREE UPDATE mes-
sages are delivered reliably to all neighbors using NACKs, as
described in Section 6. NEW PARENT messages are delivered reliably
to the new parent and old parent (if it exists) using ACKs.
7.2.1. Computing the Source Tree
RAD is a modification of Dijkstra's algorithm that computes min-hop
paths subject to the following "reporting neighbor restriction": a
link can belong to a path only if the second node of the path is a
reporting neighbor for the link. This restriction ensures correctness
and avoids routing loops.
To allow immediate rerouting without having to wait for the new
parent to report links on the new path to u, the reporting neighbor
restriction is relaxed temporarily for links (u,v) leaving node u,
when the parent p(u) changes to a neighbor that does not yet belong
to r(u), i.e., that does not yet have any children for u. When a new
parent belongs to r(u), it is said to be "confirmed", which implies
that the new parent is a reporting neighbor for links (u,v) leaving
node u. When a new parent p(u) is confirmed, prev_p(u) is set to
p(u), as specified in the procedure Confirm_Parent.
When NONTREE_PENALTY > 0, RAD computes paths that are approximately
minimum hop, in exchange for reducing the number of tree updates gen-
erated. This is accomplished by penalizing the addition of new links
to the source tree. Using a positive value for NONTREE_PENALTY
(e.g., 0.25) provides improved scalability for networks of large
diameter.
For each node u, RAD sets next(u) equal to the next node on the min-
hop (or approximately min-hop) path to desination u.
7.2.2. Generating Tree Updates
The procedure Generate_Tree_Updates compares the new source tree to
the old source tree and generates ADD and DELETE updates. Updates
are generated only for links (u,v) such that children(u) is not NULL.
(In dense networks, children(u) will be NULL in most cases.) If such
a link belongs to the new tree but not the old tree, then an ADD
update (u, v, ADD) is generated. If such a link belongs to the old
tree but not the new tree, then a DELETE update (u, v, DEL) is gen-
erated only if node u is reachable (pred(u) is not NULL) and node v
is not reachable via reportable links (pred(v) is NULL or
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 17]
INTERNET-DRAFT TBRPF 2 March 2001
children(pred(v)) is NULL). Otherwise, the DELETE update is implied
by an ADD update.
7.2.3. Updating Parents
The procedure Updating_Parents generates, for each neighbor j, a
source list that, if nonempty, will be sent in a NEW PARENT message
to that neighbor. The source list for neighbor j includes all
sources u such that the new parent for source u is j and the old
parent was not j. In addition, if the new parent belongs to r(u),
then it is already confirmed, and Confirm_Parent is called. Other-
wise, the parent p(u) will be confirmed when a TREE UPDATE is
received from p(u) that contains either (u, ADD) or (u, v, ADD) for
some v.
7.2.4. Sending NEW PARENT Messages
NEW PARENT messages are sent reliably using ACKs. A NEW PARENT mes-
sage that is transmitted for the first time contains the current
value of the sequence number ASEQ (see Section 6). A NEW PARENT mes-
sage is retransmitted (with the same sequence number) after
RXMT_INTERVAL seconds if an ACK is not received from both the new
parent and the old parent (if it exists and is still a neighbor). If
the source list is too large to include in a single packet (due to
message size limitations), multiple NEW PARENT messages are sent,
each having a different ASEQ value and a different source list.
To ensure that NEW PARENT messages containing the same source are
processed in the correct order, if the parent p(u) for some source u
changes while a previously generated NEW PARENT message containing
source u is still being retransmitted, then u is removed from the
previously generated NEW PARENT message, and is included in a new NEW
PARENT message having a larger sequence number.
7.2.5. Processing TREE UPDATE Messages
All TREE UPDATE messages are processed by all neighbors. When a TREE
UPDATE is received from a neighbor j, update_flag is set. For each
add update (u, v, ADD) in the message, node j is added to r(u,v), and
if node j is not already reporting for source u, node j is added to
r(u) and Confirm_Parent(i,u) is called if j = p(u). In addition,
since a source tree cannot contain two links entering the same node,
the add update (u, v, ADD) implies a delete update (w, v, DEL) for
any other link entering node v that is reported by node j.
For each (explicit) delete update (u, v, DEL) in the message, node j
is removed from r(u,v) and r(v), and from r(w) for all nodes w down-
stream of v on the neighbor tree T(j). If the delete update is for
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 18]
INTERNET-DRAFT TBRPF 2 March 2001
the link (j,i) from the neighbor j sending the update, then link
(i,j) is declared down.
For each add source update (u, ADD) in the message, node j is added
to r(u), and Confirm_Parent(i,u) is called if j = p(u). Finally, for
each delete source update (u, DEL) in the message, node j is removed
from r(u) and from r(w) for all nodes w downstream of u on the neigh-
bor tree T(j).
7.2.6. Processing NEW PARENT Messages
A NEW PARENT message is processed and ACKed by the new parent (whose
ID is included in the message), and by the existing parent for any
source u listed in the message. The new parent sends a TREE UPDATE
in response to the message only if children(u) = NULL for some source
u listed in the NEW PARENT message. In that case, the new parent
sends a TREE UPDATE (to all neighbors) containing the add update (u,
v, ADD) for each such node u and for each node v such that (u,v) is
on its source tree. The new parent also adds the sender of the NEW
PARENT message to children(u) for each source u listed in the mes-
sage.
A node i that receives a NEW PARENT message from node j, but is not
the new parent, processes the message as follows. For each source u
listed in the message such that node j belongs to children(u) (i.e.,
node i is the existing parent of j for source u), node j is removed
from children(u), and if this causes children(u) to be NULL, a delete
source update (u, DEL) is sent, indicating that node i is no longer
reporting for source u.
7.2.7. Processing a New Neighbor
When a node i receives a 2-way indication (see Section 5) from a node
j that does not belong to N_i, i.e., when node i sees its own ID in
the neighbor request list of a HELLO message or in an UPDATE REQUEST
message sent by node j, it adds node j to N_i, sets update_flag = 1,
and sends an UPDATE REQUEST message to node j.
The UPDATE REQUEST message can be delayed, typically until the next
HELLO message is scheduled, to allow message aggregation. The UPDATE
REQUEST is retransmitted every RMXT_INTERVAL seconds, up to
MAX_NUM_RXMT times, until an UPDATE REPLY message is received. (As
described in the neighbor discovery section, the link is declared
down if no response is received.)
The UPDATE REPLY message contains the IDs of neighbors that are being
replied to, and describes the reportable part of the router's current
source tree. I.e., for each source u such that children(u) is
nonempty, it contains the set of links (u,v) in the source tree whose
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 19]
INTERNET-DRAFT TBRPF 2 March 2001
head node is u, or only the ID of node u if the source tree contains
no links with head u.
An UPDATE REPLY can be partial (due to message size limitations), in
which case the P (partial) bit (defined in Section 10.2) is set and
the information is sent in multiple packets having different sequence
numbers. Each partial UPDATE REPLY must be ACKed by the neighbors
listed in the message, and is retransmitted (removing the IDs of
neighbors for which an ACK was received) after RXMT_INTERVAL seconds
if an ACK has not been received by all listed neighbors. If the P
bit is not set, then the UPDATE REPLY message need not be ACKed,
since the listed neighbors that do not receive it will retransmit the
UPDATE REQUEST.
7.2.8. Processing a Lost Neighbor
If any event occurs that results in a neighbor j being declared down
(see Section 5.9), node i removes node j from N_i, removes j from
children(u), and sets update_flag = 1. A TREE UPDATE reporting the
deletion of link (i,j) from node i's source tree will be generated
the next time Update_Source_Tree is executed. As stated above,
Update_Source_Tree SHOULD be executed immediately if a failure notif-
ication is received from the link layer.
7.2.9. Packet Forwarding
TBRPF-PT forwards data packets on a hop-by-hop basis. At any node
that is not the destination, an IP packet whose destination address
is that of node u is forwarded to the node given by next(u).
7.3. Pseudocode for TBRPF-PT
Update_Source_Tree(i){
Restricted_Approx_Dijkstra(i).
Generate_Tree_Updates(i, tree_update).
Update_Parents(i, src_list[]).
If (tree_update is not empty) {
Send tree_update to all neighbors. }
For each neighbor k in N_i {
Send New_Parent(src_list[k]) to node k.
Set update_flag = 0.
Set next_update_time = current_time + MIN_UPDATE_INTERVAL.}}
Restricted_Approx_Dijkstra(i){
For each link (u,v) in T, set c(u,v) = 1.
For each link (u,v) not in T, set c(u,v) = 1 + NONTREE_PENALTY.
For each node v in TT {
Set d(v) = infinity.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 20]
INTERNET-DRAFT TBRPF 2 March 2001
Set pred(v) = NULL.
Set new_p(v) = NULL.}
Set d(i) = 0.
Set S = {i} (labeled nodes).
For each node j in N_i {
Set d(j) = c(i,j).
Set new_p(j) = j. }
While there exists a node v in TT - S s.t. d(v) < infinity {
Let u be a node in TT - S with minimum d(u).
Add u to S.
For each node v s.t. (u,v) is in TT {
If ([d(u) + c(u,v) < d(v) AND
(new_p(u) or prev_p(u) is in r(u,v))]
OR [d(u) + c(u,v) = d(v) AND
(new_p(u) is in both r(u,v) and r(v))])
Set d(v) = d(u) + c(u,v).
Set pred(v) = u.
Set new_p(v) = new_p(u).}}
Set old_T = T and T = empty set.
For each node u in TT {
dist(u) = d(u).
next(u) = new_p(u).
Add (pred(u), u) to T. }}
Generate_Tree_Updates(i, tree_update) {
Set tree_update = empty.
For each link (u,v) in TT s.t. children(u) != NULL {
If (u,v) is in T but not in old_T {
Add the update (u, v, ADD) to tree_update. }
Else if ([(u,v) is in old_T but not in T] AND [pred(u) != NULL]
AND [pred(v) = NULL OR children(pred(v)) = NULL]) {
(Node v is not reachable using only reportable links.)
Add the update (u, v, DEL) to tree_update. }
If new_p(u) = NULL, remove (u,v) from TT.
If r(u,v) is empty, remove (u,v) from TT. }}
Update_Parents(i, src_list[]) {
For each node j in N_i, set src_list[j] = empty.
For each node u != i in TT {
If (new_p(u) != p(u) AND new_p(u) != NULL) {
Add u to src_list[new_p(u)].}
Set p(u) = new_p(u).
If (p(u) belongs to r(u) AND prev_p(u) != p(u)) {
Confirm_Parent(i, u).}}
Confirm_Parent(i, u){
Set prev_p(u) = p(u).
For each neighbor j in N_i {
For each node v s.t. (u,v) is in TT {
If j is in r(u,v) - r(u), remove j from r(u,v).}}}
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 21]
INTERNET-DRAFT TBRPF 2 March 2001
Process_Tree_Update(i, j, tree_update) {
(TREE UPDATE received from neighbor j.)
Set update_flag = 1.
For each add update (u, v, ADD) in tree_update {
Add node j to r(u,v).
If r(u) does not contain node j {
Add node j to r(u).
If (p(u) = j AND prev_p(u) != p(u)) {
Confirm_Parent(i, u).}}
For each w other than u such that r(w,v) contains j {
Remove j from r(w,v). (Implicit delete update.) }}
For each delete update (u, v, DEL) in tree_update {
Remove node j from r(u,v) and r(v).
Remove node j from r(w) for all nodes w downstream of v
on the neighbor tree T(j).
If (u = j and v = i) {
(Link (j,i) from neighbor failed.)
Link_Down(i,j).}}
For each add source update (u, ADD) in tree_update {
Add node j to r(u).
If (p(u) = j AND prev_p(u) != p(u)) {
Confirm_Parent(i, u).}}
For each delete source update (u, DEL) in tree_update {
Remove node j from r(u) and from r(w) for all nodes w
downstream of u on the neighbor tree T(j). }}
Process_New_Parent(i, j, parent, src_list) {
(NEW PARENT message received from neighbor j.)
Set tree_update = empty.
If (parent = i) {
For each node u in src_list {
If (children(u) = NULL) {
If node u is a leaf of T {
Add the update (u, ADD) to tree_update.}
Else {
For each v s.t. (u,v) is in T {
Add the update (u, v, ADD) to tree_update.}}}
Add j to children(u).}}
If (parent != i) {
For each node u in src_list {
If (j is in children(u)) {
Remove j from children(u).
If (children(u) = NULL) {
Add the update (u, DEL) to tree_update.}}}}
If (tree_update is not empty) {
Send tree_update to all neighbors. }}
Process_Update_Requests(i, update_request_list) {
Set update_reply = empty.
For each neighbor j in update_request_list {
Add the ID of node j to update_reply. }
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 22]
INTERNET-DRAFT TBRPF 2 March 2001
For each node u s.t. children(u) != NULL {
If node u is a leaf of T {
Add the update (u, ADD) to update_reply.}
Else {
For each v s.t. (u,v) is in T {
Add the update (u, v, ADD) to tree_update.}}}
Send update_reply.}
Process_Update_Reply(i, j, update_reply) {
If update_reply includes node i in the neighbor list {
Set update_flag = 1.
For each update (u, v, ADD) in tree_update {
Add node j to r(u,v).
Add node j to r(u). }
For each update (u, ADD) in tree_update {
Add node j to r(u). }}}
7.4. Configurable Parameters
This section lists the values of the parameters used in the descrip-
tion of the protocol, and their proposed default values.
HELLO_INTERVAL (2 seconds)
NBR_HOLD_TIME (6 seconds)
RXMT_INTERVAL (2 seconds)
MAX_NUM_RXMT (3)
MIN_UPDATE_INTERVAL (2 seconds)
NONTREE_PENALTY (0.25)
8. TBRPF-FT
Unlike TBRPF-PT, the full topology (FT) mode of TBRPF provides each
node with the state of every link in the network. TBRPF-FT 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, there being one tree per
source.
The broadcast trees are updated dynamically using the topology infor-
mation that is received along the trees themselves, thus requiring
very little additional overhead for maintaining the trees. Minimum-
hop-path trees are used because they change less frequently than
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 23]
INTERNET-DRAFT TBRPF 2 March 2001
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 chil-
dren on the tree rooted at source u. TBRPF-FT achieves reliability
despite topology changes, using sequence numbers. The correctness of
TBRPF-FT has been proven [1]. A node having no children for source u
is a leaf and need not forward updates generated by u. In dense net-
works, most nodes are leaves. In simulation experiments [7], TBRPF-
FT generated up to 85% less update/control traffic than an efficient
version of link-state 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-FT computes optimal routes based on the advertised link states;
however, the advertised link states themselves may be approximate in
order to reduce the frequency at which each link is updated.
8.1. 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 asso-
ciated 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). Therefore,
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.
In addition to the information required by the neighbor discovery
protocol (Section 5) and for reliable, sequenced delivery (Section
6), each node i running TBRPF-FT stores the following information:
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
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 24]
INTERNET-DRAFT TBRPF 2 March 2001
(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-FT 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. The state of the neighboring node nbr as a parent of node i
with respect to node u, denoted pstate_i(u, nbr). pstate_i(u,
nbr) can take on the values Null_Parent, Inactive_Parent,
Pending_Parent, or Active_Parent.
c. A list of children, denoted children_i(u).
d. The sequence number of the most recent link-state update ori-
ginating from node u received by node i, denoted sn_i(u).
e. The routing table entry for node u, consisting of the next node
on the preferred path to u.
4. The list of NEW PARENT and CANCEL PARENT messages, denoted ACK_i,
sent to neighboring nodes for which a acknowledgment has not yet
been received.
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.
TBRPF-FT uses the following message types. Message formats are
specified in Section 10.2.
Link-State Update (LSU)
A NACKable 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.
NEW PARENT REPLY
A message sent in response to a NEW PARENT message.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 25]
INTERNET-DRAFT TBRPF 2 March 2001
CANCEL PARENT
An ACKable message informing a neighbor that it is no longer a
parent with respect to one or more sources.
8.2. Operation of TBRPF-FT
This section describes the network-level operation of TBRPF-FT, with
the aid of the pseudocode given at the end of the section. Examples
illustrating the operation of TBRPF-FT and the the proof of correct-
ness for TBRPF-FT 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-FT 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 i selects a neighboring node nbr as the parent for source src
by broadcasting a NEW PARENT(nbr, src, sn) message containing the
identity of node src and the sequence number sn = sn_i(src). A node
cancels an existing parent nbr' by broadcasting a CANCEL PARENT(nbr',
src) message containing the identity 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(i, src, -) message. In general, a node will simultaneously
select a neighboring node nbr as the parent for multiple sources,
when it broadcasts a NEW PARENT(nbr, src_list, sn_list) message,
where src_list is the list of sources and sn_list is the correspond-
ing list of sequence numbers. Like the NEW PARENT message, a CANCEL
PARENT message may 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. The processing of the link
state updates received from node p_i(src), denoted nbr, is delayed
until pstate_i(src, nbr) is equal to Active_Parent. When processed,
the link-state update is entered into the topology table of node i,
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 26]
INTERNET-DRAFT TBRPF 2 March 2001
and then broadcast to neighbors of node i if children_i(src) is
nonempty. (see the procedures Update_Topology_Table and
Process_Update).
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 of a link to an exist-
ing neighbor. A node computes its parents by (1) computing minimum-
hop paths to all other nodes using Dijkstra's algorithm, 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 performs the follow-
ing actions. It broadcasts the message CANCEL PARENT(nbr', src) if
the old parent nbr' exists. In addition, node i broadcasts the mes-
sage NEW PARENT(nbr, src, sn) if the newly computed parent exists,
where nbr denotes the new parent and 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 (originating from node src) from the old
parent, and after which the new parent should commence. However, if
node i has no information regarding link-state updates originating
from node src in its topology database, the "sn" field of the NEW
PARENT(nbr, src, sn) message is set to NULL.
Upon receiving the CANCEL PARENT(k, src) message from node i, the old
parent k removes node i from the list children_k(src). Upon receiv-
ing the NEW PARENT(j, src, sn) message from node i, the new parent j
= p_i(src) adds node i to the list children_j(src). In addition, node
j sends (to node i) a NEW PARENT REPLY(i, update_list) message, where
update_list consists 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). However, if the "sn" field of the
NEW PARENT(j, src, sn) message is equal to NULL, the new parent
should respond by transmitting a NEW PARENT REPLY(i, update_list)
message, where update_list now consists of all link-state updates in
its topology database that originate from node src. Thus, only
updates not yet known to node i are sent to node i.
NEW PARENT and CANCEL PARENT messages are transmitted reliably using
positive acknowledgments (see Section 6). Therefore, each message
contains a sequence number, denoted ack_sn, which is the value of the
ACK sequence number (ASEQ) when the message was first transmitted.
The NEW PARENT REPLY message serves as an acknowledgment for the NEW
PARENT message, and the ACK message is used to acknowledge the CANCEL
PARENT message. Both the NEW PARENT REPLY and ACK messages contain
the sequence number of the corresponding NEW PARENT or CANCEL PARENT
message. To achieve reliable transmission, both the NEW PARENT and
CANCEL PARENT messages are retransmitted (for upto MAX_NUM_RXMT
times) if no acknowledgment is received within a given timeout period
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 27]
INTERNET-DRAFT TBRPF 2 March 2001
(RXMT_INTERVAL).
To ensure that NEW PARENT messages containing the same source are
processed in the correct order, if the parent p_i(u) for some source
u changes while a previously generated NEW PARENT message containing
source u is still being retransmitted, then source u is removed from
the previously generated NEW PARENT message, and is included in a new
NEW PARENT message having a larger sequence number.
After transmitting a NEW PARENT(nbr, src, sn) message, node i changes
the state of the newly computed parent node nbr to Pending_Parent
i.e., pstate_i(src, nbr) = Pending_Parent. As mentioned above, the
sequence number of the NEW PARENT message, denoted ack_sn, is used by
the parent node in the NEW PARENT REPLY message. In addition, node i
stores the tuple (ack_sn, nbr, src) in the list, ACK_i, which
includes the list of NEW PARENT messages sent to neighboring nodes
for which a response has not yet been received. Upon receiving a NEW
PARENT REPLY(i, update_list) message with the appropriate sequence
number ack_sn, node i retrieves and deletes the appropriate tuple
(ack_sn, nbr, src) from ACK_i. At this time, if the NEW PARENT REPLY
message is received from the parent node p_i(src), node i changes
pstate_i(src, nbr) (i.e, the state of the neighboring node nbr as a
parent of node i with respect to source node src) from Pending_Parent
to Active_Parent (see the procedure Proc_New_Parent_Reply). From this
point on, node i can accept and process link-state updates originat-
ing from node src from the parent node p_i(src) beginning with the
link-states in the NEW PARENT REPLY message.
If a node receives several NEW PARENT messages from different neigh-
bors at around the same time, it is possible to efficiently combine
the different responses into one NEW PARENT REPLY message transmis-
sion. In this case, the NEW PARENT REPLY message should contain for
each NEW PARENT message that is being acknowledged (i) the identity
of the neighboring node from which the NEW PARENT message was
received, followed by (ii) the sequence number, ack_sn, of the NEW
PARENT message. Finally, the NEW PARENT REPLY message contains a set
of link-state updates, which can be computed as follows.
Suppose each of the NEW PARENT messages was being acknowledged indi-
vidually in a separate NEW PARENT REPLY message, each of which con-
tains a set of link-state updates. The union of the link-state
updates in each of these NEW PARENT REPLY messages is present in the
single NEW PARENT REPLY message transmission.
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 broadcast to all neighbors if children_i(i) is not empty.
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
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 28]
INTERNET-DRAFT TBRPF 2 March 2001
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 executed at node i in response to a change in the cost to an
existing neighbor node nbr. However, this procedure does not recom-
pute 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
set, and sn_i(src) = NULL for every node src. Every node then exe-
cutes 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.
Therefore, 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-FT 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.
To minimize the amount of link-state update traffic that is transmit-
ted within the network, TBRPF-FT makes use of the following two
parameters. The parameter MIN_FORW_UPDATE_INTERVAL specifies the
minimum time between forwarding link-state updates at a given node.
In addition, the parameter MIN_UPDATE_INTERVAL specifies the minimum
time between link-state updates generated at a given node regarding
its outgoing links.
TBRPF-FT does not require an age field in link-state updates. How-
ever, 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 a certain time in order to con-
serve memory. When an update is received reporting a link failure,
the link remains in the topology table for DOWN_LINK_HOLD_TIME
(default 120 sec) and is then deleted. When node i detects that
source node u becomes unreachable for UNREACHABLE_HOLD_TIME (default
60 sec), all links outgoing from that source are deleted from the
topology table. In addition, sn_i(u) is set to NULL which indicates
that node i has no information regarding link-state updates
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 29]
INTERNET-DRAFT TBRPF 2 March 2001
originating from source node u. For correct operation of TBRPF-FT,
it is required that UNREACHABLE_HOLD_TIME is less than
DOWN_LINK_HOLD_TIME.
The reason these updates are not deleted immediately 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) during 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 different 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 recovers 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 impor-
tant to ensure the efficiency of TBRPF-FT 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 DOWN_LINK_HOLD_TIME seconds.
Periodic updates are not strictly required for the correctness of
TBRPF-FT. However, infrequent periodic updates can be used to
correct rare errors that may occur. As discussed above, periodic
updates are also required if the sequence number space is not large
enough to avoid wraparound. Periodic updates are generated as
described in the procedure Send_Periodic_Updates.
TBRPF-FT provides each node with complete link-state information.
Each node can then apply a path selection algorithm to compute pre-
ferred paths to all possible destinations, and to update these paths
when link states are updated. The default path selection algorithm
for TBRPF-FT is to apply Dijkstra's algorithm to compute shortest
paths (with respect to c) to all destinations. However, TBRPF-FT can
employ any path selection algorithm. Once preferred paths are com-
puted, the routing table entry for node u is set to the next node on
the preferred 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-FT, data packets are forwarded based
on the routing table as in IP routing. However, source routing can
also be used.
8.3. Pseudocode for TBRPF-FT
The following pseudocode describes the network-level procedures per-
formed at node i by TBRPF-FT. The notation LSU(update_list)
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 30]
INTERNET-DRAFT TBRPF 2 March 2001
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).
Set send_list to empty
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 (children_i(src) is nonempty) Add update_list(src) to send_list }
If (send_list is nonempty)
Broadcast the message LSU(send_list) to all neighbors.}
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(pstate_i(u, nbr) == Pending_Parent)
Withhold processing of link state updates in
update_list until pstate_i(u, nbr) is
equal to Active_Parent.
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((v == i) and (u belongs to N_i) and (c == infinity))
Link_Down(i, u) }
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.
If((v == i) and (u belongs to N_i) and (c == infinity))
Link_Down(i, u) }}}}
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)}.
If (children_i(i) is nonempty)
Broadcast the message LSU(update_list) to all neighbors.}}
Link_Down(i,j){
(Called when link (i,j) goes down.)
Remove j from N_i.
Set TT_i(i,j).c = infinity.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 31]
INTERNET-DRAFT TBRPF 2 March 2001
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)}.
If (children_i(i) is nonempty)
Broadcast the message LSU(update_list) to all neighbors.}
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)}.
If (children_i(i) is nonempty)
Broadcast message LSU(update_list) to all neighbors.}
Update_Parents(i){
Compute_New_Parents(i).
Set cancel_parent_msgs and new_parent_msgs to empty.
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)
pstate_i(src, k) = Inactive_Parent. }
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).
pstate_i(src, k) = Pending_Parent. }}}
For each (node k in N_i){
If (src_list(k) is nonempty){
Add (ack_sn_i, k, src_list(k), sn_list(k)) to new_parent_msgs.
Add (ack_sn_i, k, src_list(k)) to ACK_i.
Set ack_sn_i = ack_sn_i + 1}
If (cancel_src_list(k) is nonempty){
Add (ack_sn_i, k, cancel_src_list(k)) to cancel_parent_msgs.
Add (ack_sn_i, k, cancel_src_list(k)) to ACK_i.
Set ack_sn_i = ack_sn_i + 1 }}
If(new_parent_msgs is nonempty)
Broadcast message NEW PARENT(new_parent_msgs) to all neighbors.
If(cancel_parent_msgs is nonempty)
Broadcast message CANCEL PARENT(cancel_parent_msgs) to all neighbors.}
Increment_nontree_edge_cost(i){
Compute min-hop paths using Dijkstra.
For each (node src in TT_i such that src != i) {
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 32]
INTERNET-DRAFT TBRPF 2 March 2001
Set q_i(src) equal to the neighbor of node src along the
minimum hop path from i to src. }
For each ((u, v, c, sn) in TT_i) {
if(u != q_i(v)){ /* nontree edge */
TT_i(u, v).c = TT_i(u, v).c + 0.001
TT_i(u, v).nontree_edge = YES }}}
Decrement_nontree_edge_cost(i){
For each ((u, v, c, sn) in TT_i)
if(TT_i(u, v).nontree_edge == YES){
TT_i(u, v).c = TT_i(u, v).c - 0.001
TT_i(u, v).nontree_edge = NO }}
Compute_New_Parents(i){
For each (node src in TT_i such that src != i)
Set new_p_i(src) = NULL.
Increment_nontree_edge_cost(i)
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. }
Decrement_nontree_edge_cost(i) }
Process_New_Parent(i, nbr, new_parent_msgs){
(Called when node i receives a NEW PARENT(new_parent_msgs)
message from nbr.)
For each ((newpsn, k, src_list, sn_list) in new_parent_msgs) {
if (k == i){ /* This part of the NEW PARENT message is for node i. */
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 = {(x,y,c,sn) in TT_i such that x = src
and sn > sn_list.src}.
Add new_updates to update_list.}
Broadcast the message NEW PARENT REPLY(nbr, newpsn, update_list)
to all neighbors. }}}
Process_Cancel_Parent(i, nbr, cancel_parent_msgs) {
(Called when node i receives a CANCEL PARENT(cancel_parent_msgs) message
from node nbr.)
For each ((cnclpsn, k, src_list) in cancel_parent_msgs) {
if(k == i){
For each (node src in src_list) remove nbr from children_i(src).
Send the message ACK (nbr, cnclpsn) }}}
Proc_New_Parent_Reply(i, nbr, nbr', newpsn, update_list){
(Called when node i receives a NEW PARENT REPLY(nbr', newpsn, update_list)
message from nbr.)
if(nbr' == i){ /* The NEW PARENT REPLY is for node i */
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 33]
INTERNET-DRAFT TBRPF 2 March 2001
Retrieve (and delete) the tuple (newpsn, nbr, src_list') from
the list ACK_i.
For each (node src in src_list')
if((pstate_i(src, nbr) == Pending_Parent) and (p_i(src) == nbr))
Set pstate_i(src, nbr) = Active_Parent.
Process_Update(i, nbr, update_list) }}
Proc_Cancel_Parent_Ack(i, nbr, nbr', cnclpsn){
(Called when node i receives an ACK (nbr', cnclpsn)
message from nbr.)
if(nbr' == i){
Retrieve (and delete) the tuple (cnclpsn, nbr, src_list') from
the list ACK_i.
For each (node src in src_list') pstate_i(src, nbr) = Null_Parent }}
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. }
If (children_i(i) is nonempty)
Broadcast message LSU(update_list) to all neighbors.}
8.4. Configurable Parameters
This section lists the values of the parameters used in the descrip-
tion of the protocol, and their proposed default values.
HELLO_INTERVAL (2 seconds)
NBR_HOLD_TIME (6 seconds)
RXMT_INTERVAL (2 seconds)
MAX_NUM_RXMT (3)
DOWN_LINK_HOLD_TIME (120 seconds)
UNREACHABLE_HOLD_TIME (60 seconds)
MIN_UPDATE_INTERVAL (2 seconds)
MIN_FORW_UPDATE_INTERVAL (1 second)
9. Application of TBRPF In Mobile Ad-hoc Networks (MANETs)
The TBRPF routing protocols provide proactive, automatic topology
discovery with dynamic adaptation to link state changes in both fixed
and mobile environments whether the topology is relatively static or
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 34]
INTERNET-DRAFT TBRPF 2 March 2001
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 chan-
nel. (An example 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 unicast, multicast and broadcast packet
transmissions.) Although applicable across a much broader field of
use, TBRPF is particularly well suited for carrying routing informa-
tion that supports the standard DARPA Internet protocols (IPv4) [10]
as per current practices, as advocated by the IETF MANET working
group [RFC2501]. We therefore target this document toward the appli-
cation of TBRPF over MANETs that observe these current practices.
In the following sections, we discuss assumptions for the data link
layer, Internetworking assumptions, and address resolution extensions
for TBRPF neighbor discovery in a MANET environment.
9.1. Data Link Layer Assumptions
We assume a data link layer broadcast channel with multiple access
capabilities, such that nodes wishing to transmit unicast, broadcast
and/or multicast packets must arbitrate with other nodes for channel
access before doing so. We further assume that packets 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 limitations, terrain features,
and other hidden terminal conditions incurred in a mobile environ-
ment. We consider a pair of nodes (A and B) to have a bidirectional
link (or simply "link") if and only if both node A can receive pack-
ets sent from node B and node B can receive packets sent from node A
at a given instant in time.
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) delivery services
between nodes with bidirectional links. Finally, we assume that each
node in the MANET is assigned a unique data link layer unicast
address. 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.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 35]
INTERNET-DRAFT TBRPF 2 March 2001
9.2. Internetworking Assumptions
We assume that each MANET router [14] is assigned at least one unique
IPv4 address, but may have multiple interfaces; each identified by
one or more IPv4 address. For the purpose of TBRPF protocol message
exchanges, each MANET router is identified by a unique Router ID
(RID). While not a requirement, the RID is typically selected from
one of the IPv4 addresses assigned to one of the MANET router's
interface(s). As with data link level addressing assumptions
described in the previous section, we require each node to provide a
means for duplicate IPv4 address detection. The next section provides
a method for duplicate IPv4 address detection, but methods for dupli-
cate IPv4 address deconfliction are beyond the scope of this docu-
ment.
Since each MANET router participates in the TBRPF neighbor discovery
process, TBRPF provides a means for automatic (rather than on-demand)
address resolution. Thus, the requirement for on-demand discovery
through the Address Resolution Protocol (ARP) [9] is obviated. More-
over, we suggest that ARP need not be used on TBRPF interfaces, since
the ARP discovery process adds unnecessary broadcast traffic overhead
and the on-demand table management policies in most ARP implementa-
tions (e.g. flushing entries which have not been used for data
traffic within a certain timeout period) conflict with the automatic
nature of TBRPF neighbor discovery. We further assume that each MANET
router supports the multi-hop relay paradigm; in other words, each
MANET router must be prepared to provide a third-party 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 relay paradigm provides
intra-MANET forwarding services which may result in multiple hops
within a single logical IPv4 subnet. Conversely, standard Internet
routing provides forwarding between distinct IPv4 networks only.
9.3. Address Resolution Extensions for TBRPF Neighbor Discovery
TBRPF employs a neighbor discovery protocol that dynamically estab-
lishes bidirectional links and detects bidirectional link failures
through the periodic transmission of HELLO messages. To enable an
automatic address resolution capability, a TBRPF router MUST ensure
the following information is encoded in each packet that contains a
HELLO message:
- the unicast data link address of the sending interface
- the primary unicast IPv4 address of the sending interface
The choice of whether TBRPF neighbor discovery messages are sent as
transport level, network level or data link-level entities is an
implementation and/or configuration dependent decision that must be
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 36]
INTERNET-DRAFT TBRPF 2 March 2001
consistent among all MANET routers in the network. In the case that
HELLOs are sent as UDP/IPv4 packets, the above information is
automatically encoded in the headers of the UDP/IPv4 packets that
carry the HELLO messages. In other cases, mechanisms are provided to
encode this information within the HELLO message body as described in
Section 10.2.2. Given the above information in HELLO messages, a
MANET router that forms a bidirectional link to a neighbor can use
TBRPF address resolution to simply bind the neighbor's IPv4 address
to the neighbor's data link level address UNLESS duplicate address
detection determines that the IPv4 address is already in use. A
duplicate address is detected when:
1. Two or more nodes in the MANET that are actively sending HELLOs
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 that has
ceased sending HELLOs - perhaps indicating that the former node
MAY have recently left the MANET.
In all cases, the receiver MUST NOT form a link with the MANET router
that is sending the duplicate address. In case 1, the receiver SHOULD
print some form of "duplicate IPv4 address detected" warning to the
console and/or system log file. In case 2, the MANET router will
cease sending HELLO messages with its *old* data link address and
begin sending HELLO messages with its *new* data link address. Neigh-
bors of this MANET router will perceive messages containing the new
data link address as originating from a *different* node that uses a
duplicate IPv4 addresses UNTIL the existing state information con-
taining the *old* data link address expires. But, since the MANET
router no longer sends HELLO messages using its *old* data link
address, state expiration is guaranteed. At this point, neighbors
will re-negotiate their bidirectional links to the MANET router and
cache its *new* data link address to IPv4 address resolution. Case 3
is handled in an identical manner to case 2.
10. TBRPF Packets and TBRPF Protocol Messages
TBRPF protocol messages (or simply, TBRPF *messages*) encode the
individual TBRPF protocol primitives described in earlier sections.
TBRPF messages are embedded within the bodies of TBRPF *packets*,
which may contain one or more TBRPF message(s) as described in the
following section. All TBRPF packets are sent to the
"All_TBRPF_Neighbors" multicast address. Each packet sent to the
"All_TBRPF_Neighbors" multicast address is accepted by all TBRPF
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 37]
INTERNET-DRAFT TBRPF 2 March 2001
routers that physically receive the packet, whether or not they have
established a link to the sender via TBRPF neighbor discovery. Pack-
ets sent to the "All_TBRPF_Neighbors" multicast address MUST NOT be
multi-hopped to MANET routers that are not single-hop neighbors of
the sender. See: "IANA Considerations" for more information.
Since packets sent to the "All_TBRPF_Neighbors" multicast address 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). Since packet loss due to link failure,
interference, etc can occur, implementations MUST choose a maximum
TBRPF packet length that is less than the interface MTU to avoid IPv4
fragmentation and reassembly (*). IN ALL CASES, the absolute maximum
TBRPF packet length for packets sent on a particular interface is
calculated as MIN(interface MTU, 64KB).
(*) Although it may seem reasonable to allow implementations to
send larger-than-MTU sized TBRPF packets (up to the maximum of
64KB) with the understanding that such packets will incur IPv4
fragmentation, it should be noted that the loss of ANY fragment
will result in the loss of the ENTIRE TBRPF packet, which must
then be retransmitted. Thus, to avoid the unnecessary retransmis-
sion of data, we mandate IPv4 fragmentation avoidance as described
above.
For the application of TBRPF in IPv4 MANETs, implementations MUST
send and receive TBRPF packets via the User Datagram Protocol (UDP)
[11] as the default. This approach requires an official UDP service
port number registration (see: IANA Considerations). The use of
UDP/IPv4 provides:
- A UDP message length field
- UDP checksum facilities
- Simple application level access for routing daemons
- IPv4 multicast addressing
- Internet security mechanisms with policy-based address filtering
Implementations MAY OPTIONALLY employ an alternate data delivery ser-
vice other than UDP/IPv4 for the transmission of some or all TBRPF
packets. The choice of an alternate data delivery service MUST be
presented as a configurable option beyond the default of using
UDP/IPv4. Any such configuration choice MUST be consistent among all
MANET routers in the network.
All TBRPF packets consist of two components: (1) a packet header
(with optional header extension fields) immediately followed by (2) a
packet body that includes header options, message options, one or
more TBRPF message(s) and padding options as needed. As noted above,
the total length of all packet components must be less than the max-
imum TBRPF packet length as calculated by MIN(interface MTU, 64KB).
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 38]
INTERNET-DRAFT TBRPF 2 March 2001
In the following sections, we describe the elements of a TBRPF packet
in detail.
10.1. TBRPF Packet Header
TBRPF packet headers are variable-length (minimum of two octets) with
length determined by the sense of "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. (The 8-octet
alignment requirement provides a natural boundary for the alignment
of n-octet data elements up to 8-octets in length for anticipated
future use in 64-bit architectures.) IT SHOULD BE NOTED THAT ALL
FURTHER ALIGNMENT 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 in this section omit the bit ordering
notation.
The format for the TBRPF packet header and a detailed 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 2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - -+
|C|L|R|Z| Vers | Current NSEQ | Extension Fields (optional) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - -+
Flags (4 bits):
Three flag bits (C, L, R) that 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 alignment/compression
considerations for the TBRPF message. The flag bits and their
usage are described in detail below:
C - Checksum Field Included:
When the underlying delivery service provides a checksum facil-
ity (e.g. UDP/IPv4), a sender normally sets C = '0' to indicate
that NO checksum field is included in the TBRPF packet header.
If C = '0', the sender MUST enable the checksum facility pro-
vided by the underlying delivery service.
If the underlying delivery service DOES NOT provide a checksum
facility (or, if the sender chooses to avoid the underlying
delivery service checksum facility) the sender MUST set C = '1'
to indicate that a 16-bit TBRPF checksum field follows immedi-
ately after the "Current LSEQ" field. When C = '1', the sender
MUST calculate the checksum of the TBRPF packet in the manner
described in [11] and write the resulting sum into the 16-bit
message checksum field. The checksum is calculated across ALL
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 39]
INTERNET-DRAFT TBRPF 2 March 2001
data bytes in the packet header, header extension fields, and
packet body, but DOES NOT include a pseudo-header of the under-
lying delivery service.
A receiver MUST examine the C bit to determine whether a check-
sum field is present. If C = '1', the receiver MUST verify the
checksum encoded in the 16-bit TBRPF checksum field as
described in [11] to ensure TBRPF packet data integrity. When C
= '1', checksum verification is required WHETHER OR NOT the
underlying delivery service also provides a checksum facility.
The receiver MUST discard any TBRPF packet that contains an
incorrect checksum. Additionally, the receiver MUST discard any
TBRPF packet that is not protected by either a checksum facil-
ity provided by the underlying delivery service or a checksum
field encoded by the sender in the TBRPF packet header.
L - Length Field Included:
When the underlying delivery service provides a length field
(e.g. UDP/IPv4), a sender SHOULD set L = '0' to indicate that
NO TBRPF packet length field is included. If the underlying
delivery service DOES NOT provide a length field, the sender
MUST set L = '1' to indicate that a 16-bit unsigned integer
TBRPF packet length field follows immediately after any previ-
ous header fields. When L = '1', the sender MUST calculate the
length of the TBRPF packet (including all header and data
bytes) and write the resulting length into the 16-bit unsigned
integer packet length field in network byte order. (If a check-
sum field is also provided, the sender MUST write the length
field BEFORE the checksum is calculated.)
A receiver MUST examine the L bit to determine whether a length
field is included. If a length field is included, the receiver
must convert the length field to host byte order and treat the
result as the length of the TBRPF packet, including the TBRPF
packet header. If the underlying delivery service ALSO provides
a length field, the receiver MUST verify that the length pro-
vided by the underlying delivery service matches the length
provided by the length field in the TBRPF packet header. (The
receiver MUST discard any TBRPF packet in which the two lengths
do not match.) Similarly, the receiver MUST discard any TBRPF
packet if neither the underlying delivery service nor the TBRPF
packet header provide packet length.
Since the TBRPF packet header is guaranteed to begin on an even
8-octet boundary, and since all preceding header fields are
guaranteed to end on an even 2-octet boundary, the length field
is guaranteed to begin on an even 2-octet boundary. Thus,
software MAY access the 2-octet length field as a single 16-bit
unsigned integer rather than two independent 8-bit integers.
(See the following sections for more information regarding
"natural" N-bit word alignment.)
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 40]
INTERNET-DRAFT TBRPF 2 March 2001
R - Reserved:
The R bit is RESERVED for future use. The R bit may be used in
the future to indicate that an additional header extension
field follows immediately after any previous header fields.
Z - Message Alignment/Compression:
If the Z bit is '0', the sender MUST align 64-bit, 32-bit and
16-bit words within the TBRPF packet body on on "natural" boun-
daries. (i.e. 64-bit words MUST begin on integral modulo-8 byte
addresses, 32-bit words MUST begin on integral modulo-4 byte
addresses and 16-bit words MUST begin on integral module-2 byte
addresses.) If the Z bit is '0', the sender MUST use Pad1
and/or PadN padding options (see the description of these
options in the next section) where necessary to ensure natural
word alignment.
If the Z bit is '1', the sender MAY OPTIONALLY omit padding in
the interest of providing compression. Since the omission of
padding options may result in 64-bit, 32-bit and 16-bit words
aligned non-integral byte boundaries, a receiver MUST NOT pro-
cess such multi-octet words as atomic data units if Z is '1'.
Instead, the receiver must process multi-octet words "byte-by-
byte" as 8-octet, 4-octet and 2-octet arrays, respectively.
Due to the considerable additional overhead for processing
non-aligned words, it is RECOMMENDED that senders set the Z bit
to '0' and insert Pad1 and PadN options where necessary. How-
ever, it may be preferable in some contexts to set the Z bit to
'1' in order to save transmission overhead at the cost of extra
processing. Receivers MUST be able to process both aligned and
compressed packets.
Version (4 bits):
The TBRPF protocol version field provides a transition mechanism
for future versions of the TBRPF protocol. Also provides a sanity
check for host software to identify bogus messages purporting to
be TBRPF protocol messages. 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. Implementations which transmit packets as defined in
the previous draft version set the value TBRPFVERSION_1 in the
version field. TBRPF version 2 implementations MAY OPTIONALLY
provide backwards compatibility for TBRPFVERSION_1 packets.
Current NSEQ (8 bits):
The current NACK sequence number. Allows each neighbor to
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 41]
INTERNET-DRAFT TBRPF 2 March 2001
determine the sequence numbers of transmitted NACKable messages
that it did not receive. For further information, see Section 6.1:
"Reliable, Sequenced Delivery Using NACKs".
10.2. TBRPF Packet Body
The TBRPF packet body consists of the concatenation of a number of
elements including: header options, message options, one or more
TBRPF message(s), and padding options where necessary. These ele-
ments are encoded using a method derived directly from the type-
length-value (TLV) encoding method described in pp. 9-10 of Internet
RFC 2460 [15]. We will refer to our adaptation of this method as
TBRPF TLV (or, T_TLV) to distinguish it from the original TLV method
described in [15], but otherwise adopt the same terminology whenever
possible. This method encodes elements within the TBRPF packet body
(heretofore referred to as "T_TLV Elements") using the following for-
mat:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -+- - - -
| TYPE |P|L| LEN(0) | LEN(1) | VALUE
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -+- - - -
TYPE (6 bits):
A 6-bit identifier that gives the type of the T_TLV Element.
NOTE: Although the TYPE field is in the first octet of the T_TLV
Element, the TYPE field itself may NOT always begin on an n-octet
natural word boundary. Following sections will describe TYPE-
dependent alignment considerations for T_TLV Elements.
P - Partial message bit (1 bit):
A 1-bit flag; if P = '0', this T_TLV Element contains either a
complete TBRPF message in its entirety, or the final segment of a
TBRPF message that spans multiple T_TLV Elements. If P = '1', this
T_TLV Element contains a partial segment of a TBRPF message that
spans multiple T_TLV Elements.
L - Length extension bit (1 bit):
A 1-bit flag; if L = '0', the T_TLV Element is said to be in SHORT
format, and the LEN field is a single octet. If L = '1', the T_TLV
Element is said to be in LONG format, and the LEN field comprises
2 octets.
LEN (8/16 bits):
The length of the VALUE field, in octets. Note that this length
excludes the lengths of the TYPE and LEN fields themselves.
If L = '0', the T_TLV Element is in SHORT format, and the LEN
field is a single octet that encodes an 8-bit unsigned integer
which MUST contain a value within the range from 0 - 253. (Thus,
the maximum length of the T_TLV Element *including* the TYPE and
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 42]
INTERNET-DRAFT TBRPF 2 March 2001
LEN fields in SHORT format is 255 octets.)
If L = '1', the T_TLV Element is in LONG format, and the LEN field
comprises TWO octets; each encoding an 8-bit unsigned integer. The
FIRST 8-bit unsigned integer encodes the least significant byte
and the SECOND 8-bit unsigned integer encodes the most significant
byte of the length of the VALUE field, in octets. If L = '1', the
length of the value field is calculated as a 16-bit unsigned
integer as follows:
length = (LEN(1) * 256) + LEN(0)
If L = '1', the length calculated by the above equation MUST be
within the range from 0 - 65532. (Thus, the maximum length of the
T_TLV Element *including* the TYPE and LEN fields in LONG format
is 65535 octets.) When LONG format is used, implementations MUST
NOT access the two-octet LEN field as a 16-bit unsigned integer,
since the first octet of the LEN field is NOT guaranteed to fall
on a natural 16-bit word alignment.
VALUE
Variable-length field. Format and length depends on TYPE, as
described in the following sections.
As described in [15], the sequence of T_TLV Elements MUST be pro-
cessed strictly in the order they appear within the TBRPF packet
body; a receiver must not, for example, scan through the TBRPF packet
body looking for a particular type of T_TLV Element and process that
element prior to processing all preceding elements.
Also as described in [15], individual T_TLV Elements may have
specific alignment requirements to ensure that multi-octet values
fall on natural boundaries. The alignment requirement of a T_TLV Ele-
ment is specified using the notation xn+y, meaning the element type
must appear 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.
When the Z bit in the TBRPF packet header is '0', the insertion of
padding options to satisfy the alignment requirements of T_TLV Ele-
ments is MANDATORY. When Z = '1', padding options MAY be omitted and
natural word alignment is NOT guaranteed.
T_TLV Elements are grouped into four categories: padding options,
header options, message options, and TBRPF messages. The following
subsections describe these four categories in detail.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 43]
INTERNET-DRAFT TBRPF 2 March 2001
10.2.1. T_TLV Padding Options (TYPE = 0 thru 1)
As described in [15], there are two padding options which senders
insert where necessary to satisfy the alignment requirements of other
T_TLV Elements. Padding options may occur anywhere within the TBRPF
packet body. When the Z bit in the TBRPF packet header is '0', pad-
ding options MUST be inserted to ensure that the alignment require-
ments for other T_TLV 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|
+-+-+-+-+-+-+-+-+
Pad1 is indicated by TYPE = 0. The P, L bits MUST be '0', and the LEN
and VALUE fields are omitted. The Pad1 option is used to insert one octet
of padding into the TBRPF packet body. If more than one octet of padding
is required, the PadN option, described next, should be used, rather
than multiple Pad1 options.
PadN option (TYPE = 1)
- Alignment requirement: none
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - -
| 1 |0|L| LEN(0) | LEN(1) | VALUE
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - -
PadN is indicated by TYPE = 1. PadN is used to insert two or
more octets of padding into the TBRPF packet body. The P bit MUST
be '0'. If L = '0', the LEN field is one octet in length and contains
the value N-2. The VALUE field consists of N-2 zero-valued octets up
to a maximum of 253 octets, for a maximum of N = 255 padding bytes,
including the TYPE and LEN fields themselves.
If L = '1', the LEN field is TWO octets in length and contains the
value N-3. The VALUE field consists of N-3 zero-valued octets up to a
maximum of 65,532 octets, for a maximum of N = 65,535 padding bytes,
including the TYPE and LEN fields themselves.
10.2.2. T_TLV Header Options (TYPE = 2 thru 7)
T_TLV header options provide packet parameters in addition to the
information encoded in the TBRPF packet header. T_TLV header options
MUST appear immediately after the TBRPF packet header and BEFORE any
T_TLV Elements with TYPE > 7 within the message body. (Note that pad-
ding options may be intermixed with T_TLV header options.) If a
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 44]
INTERNET-DRAFT TBRPF 2 March 2001
receiver detects a T_TLV header option AFTER processing any T_TLV
Element(s) with TYPE > 7, the receiver MUST skip past the VALUE field
(ignoring its contents) and resume processing at the next T_TLV Ele-
ment, if any.
The following T_TLV header options are defined:
Router ID (RID) option (TYPE = 2)
- Alignment requirement: 4n+3
+-+-+-+-+-+-+-+-+
| 2 |0|0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID (4 octets) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The RID header option is indicated by TYPE = 2. The P, L bits MUST be
'0', and the LEN field is omitted. The VALUE field contains the 4-
octet IPv4 address corresponding to the Router ID (RID) of the
sender, encoded in network byte order (least significant byte first).
Senders MUST encode the RID option when the RID cannot be derived
from header information transmitted by the underlying data delivery
service. (For example, when the IPv4 header contains an IPv4 source
address that is *different* than the RID.) If a sender's RID and the
sender's source address as it appears in the IPv4 header are one and
the same, NO RID option is required and senders SHOULD avoid encoding
an RID option to eliminate unnecessary data octets.
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
an network level address(es) that appear either in the network-level
header or in any Alias Address header options (see the following sec-
tion) that appear within the same TBRPF packet. A sender SHOULD
encode at most one RID option within each TBRPF packet. If multiple
RID options occur, a receiver MUST accept the RID that appears in the
first such option and skip past any subsequent RID options.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 45]
INTERNET-DRAFT TBRPF 2 March 2001
Alias Address (ALIASADDR) option (TYPE = 3)
- Alignment requirement: 4n+3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 3 |AF | NUMADDR |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Alias Address (1) (N octets) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Alias Address (2) (N octets) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Alias Address (NUMADDR) (N octets) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The ALIASADDR header option is indicated by TYPE = 3. The P, L bits
are used to encode a 2-bit Address Family (AF) field. The LEN field
is used to contain a value (NUMADDR) which gives the number of Alias
Addresses of the specific Address Family given in the AF field
encoded back-to-back. (The length of each encoded Alias Address (N)
is inferred from the value in the AF field as specified below.) The
VALUE field contains NUMADDR many N-octet Alias Address encoded
back-to-back; each in network byte order (least significant byte
first). The following AF field bit values are defined, where the bits
shown are ordered as MOST significant bit followed by LEAST signifi-
cant bit:
(Note that for AF values '00' and '01', each ALIASADDR is guaranteed
to begin on a natural 4-octet boundary if the 'Z' bit in the TBRPF
packet header is '0'.)
Senders MAY OPTIONALLY encode the ALIASADDR option when they wish to
publish one or more Alias Addresses that differ from their Router ID
(RID). Receivers MUST accept each alias address thus encoded and
create a NARP binding between the sender's RID and each alias
address.
MAC Address (MACADDR) option (TYPE = 4)
- Alignment requirement: none
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -
| 4 |FMT| NUMADDR | MAC(1) (N octets)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -
~ ... ~
- - - - - - - - +-+-+-+-+-+-+-+-+
MAC(NUMADDR) (N octets) | (May end on an arbitrary boundary)
- - - - - - - - +-+-+-+-+-+-+-+-+
The MACADDR header option is indicated by TYPE = 4. The P, L bits are
used to encode a 2-bit "Format" (FMT) field. The LEN field is used to
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 46]
INTERNET-DRAFT TBRPF 2 March 2001
contain a value (NUMADDR) which gives the number of MAC addresses of
the specific Format given in the FMT field encoded back-to-back. (The
length of each encoded MAC Address (N) is inferred from the value in
the Format field as specified below.) The VALUE field contains
NUMADDR-many N-octet MAC addresses encoded back-to-back in network
byte order (least significant byte first). The following FMT field
bit values are defined where the bits shown are ordered as MOST sig-
nificant bit followed by LEAST significant bit:
commonly referred to as "EUI-48 Format"
commonly referred to as "EUI-64 Format"
Senders MUST encode a MACADDR option when the MAC address cannot be
derived directly from header information transmitted by the underly-
ing data delivery service. (The MAC address is ALWAYS available in
the MAC header when IEEE 802-compliant data link interfaces are used.
Thus the transmission of MACADDR is OPTIONAL when such interfaces are
used.) Senders MAY encode multiple MACADDR options within each TBRPF
packet, but the purpose of encoding multiple MACADDR options in this
manner is current UNDEFINED. A receiver MUST accept the first such
MAC address encoded in a MACADDR option and MAY OPTIONALLY cache the
values encoded in any subsequent MACADDRs encoded within the same
packet.
TYPE = 5 thru 7 are RESERVED for future use.
10.2.3. T_TLV Message Options (TYPE = 8 thru 15)
T_TLV message options provide parameters that apply to subsequent
T_TLV messages within the packet body. T_TLV message options MAY
appear anywhere within the TBRPF packet body after the TBRPF packet
header and T_TLV header options if any are present. Senders MAY
encode MULTIPLE instances of the same T_TLV message option type
within each TBRPF packet. If a receiver detects multiple occurrences
of the same T_TLV message option type within the same packet body,
the VALUE of the MOST RECENT such option overrides the VALUE from any
previous occurrence.
The following T_TLV message options are defined:
NONACKable Block (NONACKBLK) option (TYPE = 8)
- Alignment requirement: none
+-+-+-+-+-+-+-+-+
| 8 |0|0|
+-+-+-+-+-+-+-+-+
The NONACKBLK message option is indicated by TYPE = 8. The P, L bits
MUST be '0', and both the LEN and VALUE fields are omitted. The
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 47]
INTERNET-DRAFT TBRPF 2 March 2001
presence of a NONACKBLK message option delineates the beginning of a
"NONACK Block" that consists of one or more T_TLV messages for which
neither NACK nor ACK messages occur. We refer to this class of T_TLV
messages as "NONACKable".
The initial segment of the TBRPF packet is considered a NONACK Block
by default, and the encoding of a NONACKBLK message option in the
initial segment is NOT REQUIRED. The NONACK Block ends when:
- an ACKBLK message option occurs (see below)
- a NACKBLK message option occurs (see below)
- the end of the TBRPF packet is reached
A sender MAY encode multiple NONACK Blocks within a single TBRPF
packet. Under ordinary circumstances, NONACKable T_TLV messages are
encoded within the initial segment of the TBRPF packet body. Thus,
the NONACKBLK message option is rarely used.
ACK Block (ACKBLK) option (TYPE = 9)
- Alignment requirement: none
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 9 |0|0| ASEQ |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The ACKBLK message option is indicated by TYPE = 9. The P, L bits
MUST be '0', and the LEN field is omitted. The VALUE field contains a
single octet with an ACK Sequence Number. The presence of an ACKBLK
message option delineates the beginning of an "ACK Block" consisting
of one or more "ACKable" T_TLV messages belonging to the ACK sequence
number in the VALUE field. As described in Section 6.2: "Reliable
Delivery Using ACKs", each T_TLV message within an ACK Block MUST be
ACK'd via a positive acknowledgment. The ACK Block ends when:
- a NONACKBLK message option occurs
- another ACKBLK message option occurs
- a NACKBLK message option occurs (see below)
- the end of the TBRPF packet is reached
A sender MAY encode multiple ACK Blocks within a single TBRPF packet.
The T_TLV messages encoded in each ACK Block represent either new
transmissions or retransmissions of messages for which the sender has
not yet received a positive acknowledgment. As a receiver processes
each ACK Block within the TBRPF packet, it MUST prepare a positive
acknowledgment message for each ACKable message for which it is the
specified receiver. (NOTE: the receiver SHOULD process the entire
TBRPF packet before sending a positive acknowledgment, since the
TBRPF packet may contain MULTIPLE ACKable messages for that
receiver.)
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 48]
INTERNET-DRAFT TBRPF 2 March 2001
NACK Block (NACKBLK) option (TYPE = 10)
- Alignment requirement: none
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 10 |0|0| NSEQ |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The NACKBLK message option is indicated by TYPE = 10. The P, L bits
MUST be '0', and the LEN field is omitted. The VALUE field contains a
single octet with a NACK sequence number. The presence of a NACKBLK
message option delineates the beginning of a "NACK Block" consisting
of one or more "NACKable" T_TLV messages belonging to the NACK
sequence number in the VALUE field. As described in Section 6.1:
"Reliable, Sequenced Delivery Using NACKs", each receiver must note
the most recent NACK sequence numbers it processes from a particular
sender to detect whether any have been missed. The NACK Block ends
when:
- another NACKBLK message option occurs
- an ACKBLK message option occurs
- a NONACKBLK message option occurs
- the end of the TBRPF packet is reached
A sender MAY encode multiple NACK Blocks within a single TBRPF
packet. The T_TLV messages encoded in each NACK Block represent
either new transmissions or retransmissions of messages for which the
sender has received one or more NACK(s). After a receiver has pro-
cessed ALL NACK Blocks in the TBRPF packet, it MUST send a NACK mes-
sage to the sender if it detects missing NACK sequence numbers.
TYPE = 11 thru 15 are reserved for future use.
10.2.4. T_TLV Messages (TYPE = 16 thru 63)
T_TLV messages encode the TBRPF protocol messages described in Sec-
tions 5-8. Some protocol messages apply to both the TBRPF-FT and
TBRPF-PT protocol variants, while other messages are specific to one
of the two variants. As described in previous sections, T_TLV mes-
sages are said to be NONACKable, ACKable, or NACKable. NONACKable
message are encoded as TYPE = 16 thru 31 and contain T_TLV messages
for which neither ACK nor NACK messages occur. ACKable messages are
encoded as TYPE = 32 thru 47 and contain T_TLV messages for which the
sender requires an ACK message or some other form of positive ack-
nowledgment. Finally, NACKable messages are encoded as TYPE = 48 thru
63 and contain T_TLV messages for which NACK messages MAY occur.
T_TLV messages that require a LEN field may be encoded in either
SHORT or LONG format, as described in previous sections. If the T_TLV
message also has an alignment requirement, alignment is based on the
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 49]
INTERNET-DRAFT TBRPF 2 March 2001
decision of whether SHORT or LONG format is used. In the following
subsections, we provide formats for T_TLV messages belonging to each
of the three categories using SHORT format when a LEN field is
required. (LONG format encoding can be inferred from the alignment
requirement and text in the earlier sections.) For each T_TLV mes-
sage, we note the message alignment requirements for both SHORT and
LONG format, the protocol variant(s) for which the message applies
(TBRPF-FT and/or TBRPF-PT) and message format.
10.2.4.1. NONACKable Messages (TYPE = 16 thru 31)
As described above, NONACKable T_TLV messages are those for which
neither ACK nor NACK messages occur. NONACKable T_TLV messages may
occur ONLY within a NONACK Block delineated by either the beginning
of the TBRPF message body or the presence of a NONACKBLK message
option. The following NONACKable messages are defined:
HELLO (TYPE = 16)
- SHORT format alignment requirement: 4n+2
- LONG format alignment requirement: 4n+1
- Applies to: both TBRPF-FT and TBRPF-PT
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 16 |P|L| LEN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The body of the HELLO message consists of N 4-octet Neighbor Router
IDs (RIDs), where N is derived from the T_TLV LEN field as follows:
N = LEN / 4
NOTE that LEN modulo 4 MUST be ZERO. If LEN modulo 4 != 0, a FORMAT
ERROR is said to occur and a receiver MUST stop processing the
current TBRPF packet; discarding the remainder of its contents.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 50]
INTERNET-DRAFT TBRPF 2 March 2001
ACK (TYPE = 17)
- SHORT format alignment requirement: 4n+2
- LONG format alignment requirement: 4n+1
- Applies to: both TBRPF-FT and TBRPF-PT
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 17 |P|L| LEN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ASEQ(1) | ASEQ(2) | ASEQ(3) | ASEQ(4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
- - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - -
| ASEQ(N) | (Ends on an arbitrary boundary)
- - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - -
The body of the ACK message consists of N 4-octet Neighbor Router IDs
(RIDs) followed by N 1-octet ACK Sequence Numbers, where Neighbor
RID(i) corresponds to ASEQ(i) for 1 <= i <= N. N is derived from the
T_TLV LEN field as follows:
N = LEN / 5
NOTE that LEN modulo 5 MUST be ZERO. If LEN modulo 5 != 0, a FORMAT
ERROR is said to occur and a receiver MUST stop processing the
current TBRPF packet; discarding the remainder of its contents.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 51]
INTERNET-DRAFT TBRPF 2 March 2001
NACK (TYPE = 18)
- SHORT format alignment requirement: 4n+2
- LONG format alignment requirement: 4n+1
- Applies to: both TBRPF-FT and TBRPF-PT
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 18 |P|L| LEN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NSEQ(1) | NSEQ(2) | NSEQ(3) | NSEQ(4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
- - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - -
| NSEQ(N) | (Ends on an arbitrary bondary)
- - - - - - - - +-+-+-+-+-+-+-+-+ - - - - - - - - - - - - - - - -
The body of the NACK message consists of N 4-octet Neighbor Router
IDs (RIDs) followed by N 1-octet NACK Sequence Numbers, where Neigh-
bor RID(i) corresponds to NSEQ(i) for 1 <= i <= N. N is derived from
the T_TLV LEN field as follows:
N = LEN / 5
NOTE that LEN modulo 5 MUST be ZERO. If LEN modulo 5 != 0, a FORMAT
ERROR is said to occur and a receiver MUST stop processing the
current TBRPF packet; discarding the remainder of its contents.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 52]
INTERNET-DRAFT TBRPF 2 March 2001
NEW_PARENT_REPLY (TYPE = 19)
- SHORT format alignment requirement: 4n+1
- LONG format alignment requirement: 4n
- Applies to: TBRPF-FT ONLY
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 19 |P|L| LEN | N (= # NBRs) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ASEQ(1) | ASEQ(2) | ASEQ(3) | ASEQ(4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+- - - - - +-+-+-+-+-+-+-+-+- - - - - - - - - - - - - - - - - - +
| ... | ASEQ(N) | ZERO-PADDING TO 4-OCTET BOUNDARY |
+- - - - - +-+-+-+-+-+-+-+-+- - - - - - - - - - - - -- - - - - -+
********************* LSU_B for SRC(1) **************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(1) |
+---------------------------------------------------------------+
| NNBR (==k[1]) | ZERO PADDING |
+---------------------------------------------------------------+
| RID for NBR(1) of SRC(1) |
+-------------------------------+-------------------------------+
| Link Metrics for NBR(1) | LSUSEQ for SRC(1),NBR(1) |
+-------------------------------+-------------------------------+
| RID for NBR(2) of SRC(1) |
+-------------------------------+-------------------------------+
| Link Metrics for NBR(2) | LSUSEQ for SRC(1),NBR(2) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| RID for NBR(k[1]) of SRC(1) |
+-------------------------------+-------------------------------+
| Link Metrics for NBR(k[1]) | LSUSEQ for SRC(1),NBR(k[1]) |
+-------------------------------+-------------------------------+
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 53]
INTERNET-DRAFT TBRPF 2 March 2001
********************** LSU_B for SRC(2) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(2) |
+---------------------------------------------------------------+
| NNBR (==k[2]) | ZERO PADDING |
+---------------------------------------------------------------+
| RID for NBR(1) of SRC(2) |
+-------------------------------+-------------------------------+
| Link Metrics for NBR(1) | LSUSEQ for SRC(2),NBR(1) |
+-------------------------------+-------------------------------+
| RID for NBR(2) of SRC(2) |
+-------------------------------+-------------------------------+
| Link Metrics for NBR(2) | LSUSEQ for SRC(2),NBR(2) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| RID for NBR(k[2]) of SRC(2) |
+-------------------------------+-------------------------------+
| Link Metrics for NBR(k[2]) | LSUSEQ for SRC(2),NBR(k[2]) |
+-------------------------------+-------------------------------+
~ ... ~
~ ... ~
~ ... ~
********************** LSU_B for SRC(m) *************************
+-------------------------------+-------------------------------+
| RID for SRC(m) |
+---------------------------------------------------------------+
| NNBR (==k[m]) | ZERO PADDING |
+---------------------------------------------------------------+
| RID for NBR(1) of SRC(m) |
+-------------------------------+-------------------------------+
| Link Metrics for NBR(1) | LSUSEQ for SRC(m),NBR(1) |
+-------------------------------+-------------------------------+
~ ... ~
+-------------------------------+-------------------------------+
| RID for NBR(k[m]) of SRC(m) |
+-------------------------------+-------------------------------+
| Link Metrics for NBR(k[m]) | LSUSEQ for SRC(m),NBR(k[m]) |
+-------------------------------+-------------------------------+
The NEW_PARENT_REPLY message provides positive acknowledgment to one
or more NEW_PARENT messages (described in the following section).
The body of the NEW_PARENT_REPLY message contains the concatenation
of an ACK Block with a number of Link State Update (LSU_B) Blocks.
The LEN field provides the total length (in octets) of the ACK Block
and all LSU_B Blocks thus concatenated.
The ACK Block is preceded by a single octet (included in the LEN cal-
culation) that encodes an 8-bit unsigned integer containing N = the
number of neighbors being acknowledged. As described in the ACK mes-
sage format, the body of the ACK Block consists of N 4-octet Neighbor
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 54]
INTERNET-DRAFT TBRPF 2 March 2001
Router IDs (RIDs) followed by N 1-octet ACK Sequence Numbers, where
Neighbor RID(i) corresponds to ASEQ(i) for 1 <= i <= N. If the ACK
block ends on a non-integral 4-octet boundary, and if the Z bit in
the TBRPF packet header is '0', ZERO PADDING bytes are inserted to
the nearest 4-octet boundary. If Z = '1', however the ZERO PADDING
octets are OMITTED, and the first octet of the first LSU_B Block
immediately follows. Thus, the total length of the ACK Block is cal-
culated as:
length = 1 + (N * 5) + # padding octets
This length is deducted from LEN BEFORE the ACK Block is processed.
If LEN is decremented below 0, an UNDERFLOW ERROR is said to occur,
and the receiver MUST stop processing the current TBRPF packet; dis-
carding the remainder of its contents.
The ACK Block is immediately followed by a number of concatenated
LSU_B Blocks. Each LSU_B Block begins with the 4-octet Router ID
(RID) for the Source (SRC) for which he LSU_B Block applies. The next
2-octet field contains an unsigned 16-bit integer with the number of
neighbors (NNBR) for this SRC. If Z = '0', the NNBR field is followed
by a 2-octet ZERO PADDING field; otherwise, the ZERO PADDING field is
OMITTED. Following the (optional) ZERO PADDING field are NNBR-many
8-octet chunks which contain:
- the 4-octet RID for a NBR of SRC
- the 2-octet Link Metrics for this NBR
- the 2-octet Link State Update sequence number (LSUSEQ)
for the NBR
Thus, if Z = '0', the total length of each LSU_B Block is calculated
as:
length = 4 + 2 + 2 + (NNBR * 8)
else, (if Z = '1') the length is calculated as:
length = 4 + 2 + (NNBR * 8)
LSU_B Blocks are processed consecutively, with the total length of
each LSU_B Block deducted from LEN BEFORE the LSU_B Block is pro-
cessed. If LEN is decremented below 0, and UNDERFLOW ERROR is said
to occur, and the receiver MUST stop processing the current TBRPF
packet; discarding the remainder of its contents. The final LSU_B
Block is detected when LEN is decremented to ZERO.
TYPE = 20 thru 31 are RESERVED for future use.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 55]
INTERNET-DRAFT TBRPF 2 March 2001
10.2.4.2. ACKable Messages (TYPE = 32 thru 47)
As described above, ACKable T_TLV messages are those for which a
receiver must send an ACK message or some other positive acknowledg-
ment. ACKable T_TLV messages may occur ONLY within an ACK Block del-
ineated by the presence of an ACKBLK message option. The following
ACKable messages are defined:
NEW_PARENT (TYPE = 32)
- SHORT format alignment requirement: 4n+2
- LONG format alignment requirement: 4n+1
- Applies to: TBRPF-FT and TBRPF_PT
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 32 |P|L| LEN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source RID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source RID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source RID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The body of the NEW_PARENT message consists of 1 4-octet Neighbor RID
and N 4-octet Source RIDs. The Neighbor RID is the neighbor to which
this NEW_PARENT message is directed. The next N RIDs are the RIDs of
the Sources for which the Neighbor must become the NEW_PARENT. N is
derived from the T_TLV LEN field as follows:
N = (LEN / 4) - 1
NOTE that LEN modulo 4 MUST be ZERO. If LEN modulo 4 != 0, a FORMAT
ERROR is said to occur and the receiver MUST stop processing the
current TBRPF packet; discarding the remainder of its contents. If N
<= 0, the NEW_PARENT message contains a NULL list of Source RIDs, and
the receiver MUST skip the current VALUE field and begin processing
the next T_TLV message in the TBRPF packet body.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 56]
INTERNET-DRAFT TBRPF 2 March 2001
NEW_PARENT_SEQ (TYPE = 33)
- SHORT format alignment requirement: 4n+1
- LONG format alignment requirement: 4n
- Applies to: TBRPF-FT ONLY
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 33 |P|L| LEN | N (= # NSRC) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
**************** N Source RIDs WITHOUT LSUSEQs ******************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NSRC RID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NSRC RID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NSRC RID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
****************** M Source RIDs WITH LSUSEQs *******************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC ID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LSUSEQ for SSRC(1) | LSUSEQ for SSRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC ID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC ID(3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LSUSEQ for SSRC(3) | LSUSEQ for SSRC(4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC ID(4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC ID(5) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LSUSEQ for SSRC(5) | LSUSEQ for SSRC(6) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC ID(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The body of the NEW_PARENT_SEQ message consists of a 1-octet field
that encodes an 8-bit unsigned integer N, a 1-octet Neighbor RID, N
4-octet Source RIDs (NSRCs) that do NOT include Link State Update
sequence numbers (LSUSEQs) and M 6-octet (Source RID (SSRC), LSUSEQ)
tuples. The Neighbor RID is the neighbor to which the NEW_PARENT_SEQ
message is directed. The next N RIDs are the RIDs of the Sources for
which the Neighbor must become the NEW_PARENT. (As mentioned, these
N Source RIDs DO NOT include LSUSEQs.) If LEN < ((N+1) * 4) + 1, an
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 57]
INTERNET-DRAFT TBRPF 2 March 2001
UNDERFLOW ERROR is said to occur, and the receiver MUST stop process-
ing the current TBRPF packet; discarding the remainder of its con-
tents.
M is derived from the T_TLV LEN field as follows:
REMAINDER = LEN - ((N+1) * 4) -1 M = REMAINDER / 6
NOTE that REMAINDER modulo 6 MUST be ZERO. If REMAINDER modulo 6 !=
0, a FORMAT ERROR is said to occur and the receiver MUST stop pro-
cessing the current TBRPF packet; discarding the remainder of its
contents. If M > 0 the next M 6-octet tuples contain the 4-octet RID
and 2-octet LSUSEQ for which the Neighbor must become the NEW_PARENT.
The RIDs and LSUSEQs are "tiled" in the manner shown in the diagram
to avoid "holes" in the packet body.
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:
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC RID(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LSUSEQ for SSRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
CANCEL_PARENT (TYPE = 34)
- SHORT format alignment requirement: 4n+2
- LONG format alignment requirement: 4n+1
- Applies to: TBRPF-FT ONLY
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 34 |P|L| LEN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID (1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source RID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source RID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source RID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The body of the CANCEL_PARENT message consists of 1 4-octet Neighbor
RID and N 4-octet Source RIDs. The Neighbor RID is the neighbor to
which this CANCEL_PARENT message is directed. The next N RIDs are the
RIDs of the Sources for which the sender is requesting CANCEL_PARENT.
N is derived from the T_TLV LEN field as follows:
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 58]
INTERNET-DRAFT TBRPF 2 March 2001
N = (LEN / 4) - 1
NOTE that LEN modulo 4 MUST be ZERO. If LEN modulo 4 != 0, a FORMAT
ERROR is said to occur and the receiver MUST stop processing the
current TBRPF packet; discarding the remainder of its contents. If N
<= 0, the CANCEL_PARENT message contains a NULL list of Source RIDs,
and the receiver MUST skip the current VALUE field and begin process-
ing the next T_TLV message in the TBRPF packet body.
UPDATE_REQUEST (TYPE = 35)
- SHORT format alignment requirement: 4n+2
- LONG format alignment requirement: 4n+1
- Applies to: TBRPF-PT ONLY
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 35 |P|L| LEN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The body of the UPDATE_REQUEST message consists of N 4-octet Neighbor
RIDs. N is derived from the T_TLV LEN field as follows:
N = (LEN / 4)
NOTE that LEN modulo 4 MUST be ZERO. If LEN modulo 4 != 0, a FORMAT
ERROR is said to occur and the receiver MUST stop processing the
current TBRPF packet; discarding the remainder of its contents. If N
<= 0, the UPDATE_REQUEST message contains a NULL list of Neighbor
RIDs, and the receiver MUST skip the current VALUE field and begin
processing the next T_TLV message in the TBRPF packet body, if any.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 59]
INTERNET-DRAFT TBRPF 2 March 2001
UPDATE_REPLY (TYPE = 36)
(SHORT format alignment requirement: 4n+2)
(LONG format alignment requirement: 4n+1)
(Applies to: TBRPF-PT ONLY)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 36 |P|L| LEN | N (= # NBRs) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor RID(N) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*********************** LSU_C for SRC(1) ************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[1]) | ZERO PADDING |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 60]
INTERNET-DRAFT TBRPF 2 March 2001
********************** LSU_C for SRC(2) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[2]) | ZERO PADDING |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
~ ... ~
~ ... ~
********************** LSU_C for SRC(M) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[M]) | ZERO PADDING |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The UPDATE_REPLY message provides positive acknowledgment to one or
more UPDATE_REQUEST messages (described in the following section).
The body of the UPDATE_REPLY message contains the concatenation of an
ACK Block with a number of Link State Update (LSU_C) Blocks. The LEN
field provides the total length (in octets) of the ACK Block and all
LSU_C Blocks thus concatenated.
The ACK Block is preceded by a single octet (included in the LEN cal-
culation) that encodes an 8-bit unsigned integer containing N = the
number of neighbors being acknowledged. As described in the ACK mes-
sage format, the body of the ACK Block consists of N 4-octet Neighbor
Router IDs (RIDs), however ACK Sequence Numbers (ASEQs) are not
necessary and thus not encoded. Thus, the total length of the ACK
Block is calculated as:
length = 1 + (N * 4)
This length is deducted from LEN BEFORE the ACK Block is processed.
If LEN is decremented below 0, an UNDERFLOW ERROR is said to occur,
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 61]
INTERNET-DRAFT TBRPF 2 March 2001
and the receiver MUST stop processing the current TBRPF packet; dis-
carding the remainder of its contents.
The ACK Block is immediately followed by a number of LSU_C Blocks
concatenated together. Each LSU_C Block begins with the 4-octet
Router ID (RID) for the Source (SRC) for which the LSU_C Block
applies. The next 2-octet field contains an unsigned 16-bit integer
with the number of neighbors (NNBR) for this SRC. UNLIKE the
TREE_UPDATE message (see the following section), ALL LSU_C Blocks in
an UPDATE reply encode an ADD update for their SRC.
If Z = '0', the 2-octet NNBR field is immediately followed by a 2-
octet ZERO PADDING field as shown above. Otherwise, the ZERO PADDING
field is OMITTED, and the first NBR RID begins immediately after the
NNBR field. Following the ZERO PADDING field (if any), are NNBR-many
4-octet RIDs for NBRs of the SRC. If Z = '0', the ZERO PADDING field
is present and the length for the LSU_C Block is calculated as:
length = 4 + 4 + (NNBR * 4)
Otherwise, the ZERO PADDING field is omitted and the length of the
LSU_C Block is calculated as:
length = 4 + 2 + (NNBR * 4)
LSU_C Blocks are processed consecutively, with the total length of
each LSU_C Block deducted from LEN BEFORE the LSU_C Block is pro-
cessed. If LEN is decremented below 0, and UNDERFLOW ERROR is said
to occur, and the receiver MUST stop processing the current TBRPF
packet; discarding the remainder of its contents. The final LSU_C
Block is detected when LEN is decremented to ZERO.
TYPE = 37 thru 47 are RESERVED for future use.
10.2.4.3. NACKable Messages (TYPE = 48 thru 63)
As described above, NACKable T_TLV messages are those for which the
sender may receive a NACK message from one or more receivers that
detect a gap in the NACK sequence number space. NACKable T_TLV mes-
sages may occur ONLY within a NACK Block delineated by the presence
of a NACKBLK message option. The following NACKable messages are
defined:
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 62]
INTERNET-DRAFT TBRPF 2 March 2001
LINK_STATE_UPDATE (TYPE = 48)
- SHORT format alignment requirement: 4n+2
- LONG format alignment requirement: 4n+1
- Applies to: TBRPF-FT ONLY
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 48 |P|L| LEN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*********************** LSU_A for SRC(1) ************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[1]) | LSUSEQ for SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Metrics for NBR(1) | Link Metrics for NBR(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(3) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Metrics for NBR(3) | Link Metrics for NBR(4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(4) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(5) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 63]
INTERNET-DRAFT TBRPF 2 March 2001
********************** LSU_A for SRC(2) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[2]) | LSUSEQ for SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Metrics for NBR(1) | Link Metrics for NBR(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(3) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Metrics for NBR(3) | Link Metrics for NBR(4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(4) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(5) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
~ ... ~
~ ... ~
********************** LSU_A for SRC(M) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[M]) | LSUSEQ for SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Metrics for NBR(1) | Link Metrics for NBR(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(3) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Metrics for NBR(3) | Link Metrics for NBR(4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(4) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(5) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 64]
INTERNET-DRAFT TBRPF 2 March 2001
The LINK_STATE_UPDATE message consists of a number of LSU_A Blocks
concatenated together. Each LSU_A Block begins with the 4-octet
Router ID (RID) for the Source (SRC) for which the LSU_A Block
applies. The next 2-octet field contains an unsigned 16-bit integer
with the number of neighbors (NNBR) for this SRC. This field is
immediately followed by another 2-octet field containing that LSUSEQ
for the SRC.
Following the LSUSEQ field are NNBR-many 6-octet chunks which con-
tain:
- the 4-octet RID for a NBR of SRC
- the 2-octet Link Metrics for this NBR
The order in which the two elements in each 6-octet chunk are coded
is staggered in the manner shown in the diagram to avoid unused
"holes" in the message. Note that if NNBR is an EVEN number, the
LSU_A chunk will end on an even 4-octet boundary. But, if NNBR is
ODD, the LSU_A chunk will end as follows:
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SSRC RID(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LSUSEQ for SSRC(M) | ZERO PADDING |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
If Z = '0', the LSU_A chunk is terminated by a 2-octet ZERO PADDING
field as shown above. Otherwise, the ZERO PADDING field is OMITTED,
and the NEXT LSU_A chunk begins immediately after the final LSUSEQ
field. Thus, if NNBR is EVEN, OR if Z = '1', the total length of the
LSU_A Block is calculated as:
length = 4 + 2 + 2 + (NNBR * 6)
Otherwise, if NNBR is ODD AND Z = '0', the length of the LSU_A Block
is calculated as:
length = 4 + 2 + 2 + (NNBR * 6) +2
LSU_A Blocks are processed consecutively, with the total length of
each LSU_A Block deducted from LEN BEFORE the LSU_A Block is pro-
cessed. If LEN is decremented below 0, and UNDERFLOW ERROR is said
to occur, and the receiver MUST stop processing the current TBRPF
packet; discarding the remainder of its contents. The final LSU_A
Block is detected when LEN is decremented to ZERO.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 65]
INTERNET-DRAFT TBRPF 2 March 2001
TREE_UPDATE (TYPE = 49)
- SHORT format alignment requirement: 4n+2
- LONG format alignment requirement: 4n+1
- Applies to: TBRPF-PT ONLY
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 49 |P|L| LEN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*********************** LSU_C for SRC(1) ************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[1]) |A| ZERO PADDING |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 66]
INTERNET-DRAFT TBRPF 2 March 2001
********************** LSU_C for SRC(2) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[2]) |A| ZERO PADDING |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
~ ... ~
~ ... ~
********************** LSU_C for SRC(M) *************************
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NNBR (==k[M]) |A| ZERO PADDING |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(1) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(2) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RID for NBR(k[1]) of SRC(M) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The TREE_UPDATE message consists of a number of LSU_C Blocks con-
catenated together. Each LSU_C Block begins with the 4-octet Router
ID (RID) for the Source (SRC) for which the LSU_C Block applies. The
next 2-octet field contains an unsigned 15-bit integer with the
number of neighbors (NNBR) for this SRC. The most significant bit of
this 2-octet field (the 'A' bit) signifies the type of update. If A =
'1', the LSU_C Block encodes an ADD update for this SRC. If A = '0',
the LSU_C Block encodes a DELETE update.
If Z = '0', the 2-octet NNBR field is immediately followed by a 2-
octet ZERO PADDING field as shown above. Otherwise, the ZERO PADDING
field is OMITTED, and the first NBR RID begins immediately after the
NBR field. Following the ZERO PADDING field (if any), are NNBR-many
4-octet RIDs for NBRs of the SRC. If Z = '0', the ZERO PADDING field
is present and the length for the LSU_C Block is calculated as:
length = 4 + 4 + (NNBR * 4)
Otherwise, the ZERO PADDING field is omitted and the length of the
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 67]
INTERNET-DRAFT TBRPF 2 March 2001
LSU_C Block is calculated as:
length = 4 + 2 + (NNBR * 4)
LSU_C Blocks are processed consecutively, with the total length of
each LSU_C Block deducted from LEN BEFORE the LSU_C Block is pro-
cessed. If LEN is decremented below 0, and UNDERFLOW ERROR is said
to occur, and the receiver MUST stop processing the current TBRPF
packet; discarding the remainder of its contents. The final LSU_C
Block is detected when LEN is decremented to ZERO.
TYPE = 50 thru 63 are RESERVED for future use.
10.2.5. Implementation Considerations for SHORT and LONG Format
Encoding
A sender that encodes a T_TLV message with both a LEN field and an
alignment requirement may know a priori whether SHORT format will
suffice or whether LONG format will be necessary. In this case, the
implementation SHOULD choose the appropriate LEN format and MUST
align the T_TLV message properly based on the specific LEN format
chosen.
If the implementation DOES NOT have a priori knowledge of the LEN
requirement, but the current offset within the TBRPF packet would
allow for either SHORT or LONG format T_TLV message alignment with
minimal/no insertion of padding octets, the implementation may first
encode the T_TLV message VALUE at the first properly-aligned octet
beyond the current offset, then prepend the TYPE and LEN fields (pre-
ceded by any Pad0/PadN options required) in the space before the
beginning of the VALUE field.
If the implementation DOES NOT have a priori knowledge of the LEN
requirement, AND the current offset within the TBRPF packet would
allow for a SHORT format T_TLV message with no padding octets but NOT
a LONG format, the implementation may employ one of a number of stra-
tegies to ensure that T_TLV message are both efficiently coded and
properly aligned. The implementation may optionally:
- Insert padding octets into the TBRPF packet body until the padding
requirement for LONG format is met. Then, begin writing the T_TLV
message into the TBRPF packet body using LONG format whether/not
the encoded T_TLV message exceeds 255 octets in length. (May
result in wasted space for padding options if LONG format was
not required.
- Pre-process the T_TLV message into a temporary data buffer. Then,
append the temporary data buffer to the TBRPF packet body using
the appropriate LEN format (SHORT or LONG). (Results in an extra
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 68]
INTERNET-DRAFT TBRPF 2 March 2001
data copy operation if vectored I/O data buffer chaining is not
available.)
- Begin writing the T_TLV message into the TBRPF packet body using SHORT
format. Then, if the maximum length for a SHORT format T_TLV message
is reached, terminate the construction of the current SHORT format
T_TLV message and begin the construction of a NEW T_TLV message *of
the same type*.
Note that this final consideration implies that a "jumbo" TBRPF
message MAY be split into multiple, independently-coded T_TLV messages.
When a jumbo TBRPF message is split in this manner, each T_TLV
message that encodes a portion of the jumbo TBRPF message MUST be
wholly self-contained; that is, a receiver MUST be able to process
any T_TLV message independently of any other T_TLV message(s). In
summary, while a jumbo TBRPF message may be split into multiple T_TLV
messages, each T_TLV message must be self-contained and properly
contained within a single TBRPF packet.
11. 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 IEEE Ethertype assignment for TBRPF messages not sent
via UDP (OPTIONAL)
Note that the IPv4 Multicast assignment implied by 1. MAY have gen-
eral application for MANET beyond its anticipated use for TBRPF.
Specifically, IANA designates IPv4 Multicast assignments within the
range 224.0.0.0 thru 224.0.0.255 as "NON-ROUTEABLE", meaning that
messages sent to those addresses MUST NOT be routed to a different
logical IPv4 subnet regardless of the TTL in the IPv4 header. How-
ever, MANET applications may require one or more multicast address
assignments that are "NON-RELAYABLE", meaning that messages sent to
those addresses MUST NOT be relayed beyond a single hop within the
same logical IPv4 subnet.
We therefore propose that MANET consider the procurement of one or
more "NON-RELAYABLE" IPv4 Multicast assignments from IANA. For exam-
ple, MANET could register an "All_MANET_Neighbors" IPv4 multicast
address with IANA, specifying that messages sent to that address MUST
NOT be relayed. The existence of such assignments would obviate the
requirement for an "All_TBRPF_Neighbors" multicast address assign-
ment.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 69]
INTERNET-DRAFT TBRPF 2 March 2001
12. 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
or all of these issues.
13. Implementation Status
The TBRPF Version 1 protocol (as described in the previous draft ver-
sion) 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 experiments since June 1999.
As of January 2001, the TBRPF Version 1 protocol 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.
14. Acknowledgments
The authors would like to thank ASEO/CECOM for funding this work, ONR
for funding the Linux port, and the following people for helping in
the development of TBRPF: Mark G. Lewis, Yonael Gorfu, and Julie S.
Wong.
15. 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.
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 70]
INTERNET-DRAFT TBRPF 2 March 2001
[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] 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-03.txt, November 2000 (work in progress).
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 71]
INTERNET-DRAFT TBRPF 2 March 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
Bellur, Ogier, and Templin Expires 2 September 2001 [Page 72]
