node i effectively selects itself to be an MPR of node j. This is
quite different from [12], in which a node does not select itself to
be an MPR, but selects a subset of its neighbors to be MPRs.
A node with a larger relay priority reports a larger part of its
source tree (on average), and is more likely to be selected as a
next-hop relay by its neighbors. A node with relay priority equal to
0 is called a non-relay node, and never forwards packets originating
from other nodes.
TBRPF does not use sequence numbers for topology updates, thus
reducing message overhead and avoiding wraparound problems. Instead,
a technique similar to SPTA [13] is used in which, for each link
(u,v) reported by one or more neighbors, only the next hop p(u) to u
is believed regarding the state of the link. (However, in SPTA each
node reports the full topology.) Using this technique, each node
maintains a topology graph TG, consisting of links that are believed
to be up, and computes T as the shortest-path tree within TG. To
allow immediate rerouting, the restriction that each link (u,v) in TG
must be reported by p(u) is relaxed temporarily if p(u) changes to a
neighbor that is not reporting the link.
Each node is required to report RT, but may report additional links,
e.g., to provide increased robustness in highly mobile networks.
More precisely, a node may maintain any subgraph H of TG that
contains T, and report the reported subgraph RH, which consists of
links (u,v) of H such that u is in RN. For example, H can equal TG,
which would provide each node with the full network topology if this
is done by all nodes. H can also be a biconnected subgraph that
contains T, which would provide each node with two disjoint paths to
each other node, if this is done by all nodes.
TBRPF allows the option to include link metrics in topology updates,
and to compute paths that are shortest with respect to the metric.
This allows packets to be sent along paths that are higher quality
than minimum-hop paths.
TBRPF 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 NON_TREE_PENALTY.
6. TBRPF Packets
Nodes send TBRPF protocol data in contiguous units known as packets.
Each packet includes a header, optional header extensions, and a body
comprising one or more messages and padding options as needed. To
facilitate efficient receiver processing, senders SHOULD insert
padding options as necessary to align multi-octet words within the
TBRPF packet on natural boundaries (i.e., modulo-8/4/2 addresses for
64/32/16-bit words, respectively). Receivers MUST be capable of
processing multi-octet words whether or not aligned on natural
boundaries. The following sections specify elements of the TBRPF
packet in more detail.
6.1. TBRPF Packet Header
TBRPF packet headers are variable-length (minimum one octet). The
format for the packet header is as follows:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Vers |L|I|R|R| Reserved | Header Extensions ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Version (4 bits)
The TBRPF version number. This specification documents version 4
of the protocol.
Flags (4 bits)
Two bits (L,I) specify which header extensions (if any) follow.
Two bits (R) are reserved for future use, and MUST be zero. Any
extensions specified by these bits MUST appear in the same order
as the bits (i.e., first L, then I) as follows:
L - Length included
If the underlying delivery service provides a length field, the
sender MAY set L = ’0’ and omit the length extension. Otherwise,
the sender MUST set L = ’1’ and include a 16-bit unsigned integer
length immediately after any previous header field. The length
includes all header and data bytes and is written into the length
field in network byte order.
Receivers examine the L bit to determine whether the length field
is present. If L = ’1’, the receiver reads the length field to
determine the length of the TBRPF packet, including the TBRPF
packet header. Receivers discard any TBRPF packet if neither the
underlying delivery service nor the TBRPF packet header provide
packet length.
I - Router ID (RID) included
If the underlying delivery service encodes the sender’s RID, the
sender MAY set I = ’0’ and omit the RID field. Otherwise, the
sender MUST set I = ’1’ and include a 4-octet RID in network byte
order immediately after any previous header fields. The RID
option provides a mechanism for implicit network-level address
resolution. A receiver that detects a RID option SHOULD create a
binding between the RID and the source address that appears in the
network-level header.
Reserved
Reserved for future use; MUST be zero.
6.2. TBRPF Packet Body
The TBRPF packet body consists of the concatenation of one or more
TBRPF messages (and padding options where necessary). Messages and
padding options within the TBRPF packet body are encoded using the
following format:
+-+-+-+-+-+-+-+-+- - - - -
|OPTIONS| TYPE | VALUE
+-+-+-+-+-+-+-+-+- - - - -
OPTIONS (4 bits)
Four option bits that depend on TYPE.
TYPE (4 bits)
Identifier for message type or padding option.
VALUE
Variable-length field. (Format and length depend on TYPE, as
described in the following sections.)
The sequence of elements MUST be processed strictly in the order they
appear within the TBRPF packet body; a receiver must not, for
example, scan through the packet body looking for a particular type
of element prior to processing all preceding elements [2]. TBRPF
packet elements include padding options and messages as described
below.
6.2.1. Padding Options (TYPE = 0 thru 1)
Senders MAY insert two types of padding options where necessary,
e.g., to satisfy alignment requirements for other elements [2].
Padding options may occur anywhere within the TBRPF packet body. The
following two padding options are defined:
Pad1 option (TYPE = 0)
+-+-+-+-+-+-+-+-+
| 0 | 0 |
+-+-+-+-+-+-+-+-+
The Pad1 option inserts one octet of padding into the TBRPF packet
body; the VALUE field is omitted. If more than one octet of padding
is required, the PadN option (described next) should be used, rather
than multiple Pad1 options.
PadN option (TYPE = 1)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - -
| 0 | 1 | LEN | Zero-valued Octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - -
The PadN option inserts two or more octets of padding into the TBRPF
packet body. The first octet of the VALUE field contains an 8-bit
unsigned integer length containing a value between 0 - 253 which
specifies the number of zero-valued octets that immediately follow,
yielding a maximum total of 255 padding octets.
6.2.2. Messages (TYPE = 2 thru 10)
Additional message types are described as they occur in the following
sections. Senders encode messages as specified by the individual
message formats. Receivers detect errors in message construction,
e.g., messages with unrecognized types, messages with a non-integral
number of elements, or with fewer elements than indicated, etc. In
all cases, upon detecting an error, the receiver MUST discontinue
processing the current TBRPF packet and discard any unprocessed
elements.
7. TBRPF Neighbor Discovery
This section describes the TBRPF Neighbor Discovery (TND) protocol,
which allows each node to quickly detect bidirectional links (I,J)
between a local interface I and a neighbor interface J, and to
quickly detect the loss of such links. The interface between TND and
the routing module is defined by the neighbor table maintained by TND
and the three procedures Link_Up(I,J), Link_Down(I,J), and
Link_Change(I,J), which are called by TND to announce a new link, the
loss of a link, and a change in the metric of a link, respectively.
7.1. HELLO Message Format
The HELLO message has the following three subtypes:
- NEIGHBOR REQUEST (TYPE = 2)
- NEIGHBOR REPLY (TYPE = 3)
- NEIGHBOR LOST (TYPE = 4)
Each HELLO subtype has the following format:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 0 | TYPE | HSEQ | Pri | n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address (1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address (2) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address (n) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
HSEQ (8 bits)
The HELLO sequence number.
Pri (4 bits)
This field indicates the sending node’s relay priority, which is
an integer between 0 and 15. A node with a higher relay priority
is more likely to be selected as the next hop on a route. The
value 0 is reserved for non-relay nodes, i.e., nodes that should
never forward packets originating from other nodes. A router in
normal operation SHOULD have a relay priority equal to 7. A
router can change its relay priority dynamically, e.g., when its
power supply becomes critical.
n (12 bits)
The number of 32-bit neighbor interface addresses in the message.
A HELLO message is the concatenation of a NEIGHBOR REQUEST message, a
NEIGHBOR REPLY message, and a NEIGHBOR LOST message, where each of
the last two messages is omitted if its list of neighbor interface
addresses is empty. Thus, a HELLO message always includes a
(possibly empty) NEIGHBOR REQUEST.
7.2. Neighbor Table
Each node maintains, for each of its local interfaces I, a neighbor
table, which stores state information for each neighbor interface J
from which HELLO messages have recently been received by interface I.
The entry for neighbor interface J, in the neighbor table for I,
contains the following variables:
nbr_rid(I,J) - The router ID of the node associated with neighbor
interface J.
nbr_status(I,J) - The current status of the link (I,J), which can
be LOST, 1-WAY, or 2-WAY.
nbr_life(I,J) - The amount of time (in seconds) remaining before
nbr_status(I,J) must be changed to LOST if no further HELLO
message from interface J is received. Set to NBR_HOLD_TIME
whenever a HELLO is received on interface I from interface J.
nbr_hseq(I,J) - The value of HSEQ in the last HELLO message
received on interface I from interface J. Used to determine the
number of HELLOs that have been missed.
nbr_count(I,J) - The remaining number of times a NEIGHBOR REQUEST/
REPLY/LOST message containing J must be sent on interface I.
hello_history(I,J) - A list of the sequence numbers of the last
HELLO_ACQUIRE_WINDOW HELLO messages received on interface I from
interface J.
nbr_metric(I,J) - An optional measure of the quality of the link
(I,J), represented by an integer between 1 and 255, where smaller
values indicate better quality. Defaults to 1 if not used.
nbr_pri(I,J) - The relay priority of the node associated with
interface J.
The entry for interface J in the neighbor table for interface I may
be deleted if no HELLO has been received on interface I from
interface J within the last 2*NBR_HOLD_TIME seconds. (It is kept
while NEIGHBOR LOST messages containing J are being transmitted.)
The absence of an entry for a given interface J is equivalent to an
entry with nbr_status(I,J) = LOST and hello_history(I,J) = NULL.
The three possible values of nbr_status(I,J) have the following
informal meanings (the exact meanings are defined by the protocol):
LOST
Interface I has not received a sufficient number of HELLO messages
recently from Interface J.
1-WAY
Interface I has received a sufficient number of HELLO messages
recently from Interface J, but the link is not 2-WAY.
2-WAY
Interfaces I and J have both received a sufficient number of HELLO
messages recently from each other.
7.3. Sending HELLO Messages
Each node MUST send, on each local interface, at least one HELLO
message per HELLO_INTERVAL. HELLO messages MAY be sent more
frequently than this (e.g., for faster detection of topology
changes). However, to avoid the possibility that HSEQ wraps around
to the same number before a neighbor that stops receiving HELLO
messages changes the status of the link to LOST, the time between two
consecutive HELLO messages (sent on a given interface) MUST be
greater than NBR_HOLD_TIME/128 second.
To avoid synchronization of control messages, which can result in
collisions, HELLO messages SHOULD NOT be transmitted at equal
intervals. To achieve this, a node MAY choose the interval between
consecutive HELLO messages to be HELLO_INTERVAL - jitter, where
jitter is selected randomly from the interval [0, MAX_JITTER].
Each HELLO message always includes a NEIGHBOR REQUEST message, even
if its list of neighbor addresses is empty. The NEIGHBOR REQUEST
message includes the sequence number HSEQ, which is incremented by 1
(modulo 256) each time a HELLO is sent. The HELLO message also
includes a NEIGHBOR REPLY message if its list of neighbor addresses
is nonempty, and a NEIGHBOR LOST message if its list of neighbor
addresses is nonempty. The contents of these three messages are
determined by the following steps at node i for each interface I:
1. For each interface J such that nbr_status(I,J) = LOST and
nbr_count(I,J) > 0, include J in the NEIGHBOR LOST message and
decrement nbr_count(I,J).
2. For each interface J such that nbr_status(I,J) = 1-WAY and
nbr_count(I,J) > 0, include J in the NEIGHBOR REQUEST message and
decrement nbr_count(I,J).
3. For each interface J such that nbr_status(I,J) = 2-WAY and
nbr_count(I,J) > 0, include J in the NEIGHBOR REPLY message and
decrement nbr_count(I,J).
If a node restarts, so that all entries are removed from the neighbor
table, then the node MUST ensure that (for each interface) at least
one of the following two conditions is satisfied:
1. The difference between the transmission times of the first HELLO
sent after restarting and the last HELLO sent before restarting is
at least 2*NBR_HOLD_TIME.
2. Letting HSEQ_LAST denote the sequence number of the last HELLO
that was sent before restarting, the sequence number of the first
HELLO sent after restarting is set to HSEQ_LAST + NBR_HOLD_COUNT +
1 (modulo 256).
Either of these conditions ensures that, if node i with interface I
restarts, then each neighbor of node i that has a link (J,I) to
interface I will set the status of the link to LOST.
7.4. Processing a Received HELLO Message
When a node receives a HELLO message, it obtains the IP address of
the sending interface from the IP header. If the TBRPF packet header
of the received HELLO contains the RID option, then the RID of the
sending node is obtained from the TBRPF packet header; otherwise it
is equal to the IP address of the sending interface. If node i (with
RID equal to i) receives a HELLO message on interface I, sent by node
j (with RID equal to j) on interface J, with sequence number HSEQ and
relay priority PRI, then node i performs the following steps:
1. If the neighbor table for interface I does not contain an entry
for interface J, create one with nbr_rid(I,J) = j, nbr_status(I,J)
= LOST (temporarily), nbr_count(I,J) = 0, and nbr_hseq(I,J) =
HSEQ.
2. Update hello_history(I,J) to reflect the received HELLO message.
If nbr_hseq(I,J) > HSEQ (due to wraparound), set nbr_hseq(I,J) =
nbr_hseq(I,J) - 256.
3. If nbr_status(I,J) = LOST and hello_history(I,J) indicates that
HELLO_ACQUIRE_COUNT of the last HELLO_ACQUIRE_WINDOW HELLO
messages from interface J have been received:
a. If interface I does not appear in the NEIGHBOR REQUEST list or
the NEIGHBOR REPLY list, set nbr_status(I,J) = 1-WAY and
nbr_count(I,J) = NBR_HOLD_COUNT.
b. Else, set nbr_status(I,J) = 2-WAY and nbr_count(I,J) =
NBR_HOLD_COUNT. Call Link_Up(I,J).
4. Else, if nbr_status(I,J) = 1-WAY:
a. If HSEQ - nbr_hseq(I,J) > NBR_HOLD_COUNT, then set
nbr_status(I,J) = LOST and nbr_count(I,J) = NBR_HOLD_COUNT.
b. Else, if interface I appears in the NEIGHBOR REQUEST list, set
nbr_status(I,J) = 2-WAY and nbr_count(I,J) = NBR_HOLD_COUNT.
Call Link_Up(I,J).
c. Else, if interface I appears in the NEIGHBOR REPLY list, set
nbr_status(I,J) = 2-WAY and nbr_count(I,J) = 0. Call
Link_Up(I,J).
5. Else, if nbr_status(I,J) = 2-WAY:
a. If interface I appears in the NEIGHBOR LOST list, set
nbr_status(I,J) = LOST and nbr_count(I,J) = 0. Call
Link_Down(I,J).
b. Else, if HSEQ - nbr_hseq(I,J) > NBR_HOLD_COUNT, set
nbr_status(I,J) = LOST and nbr_count(I,J) = NBR_HOLD_COUNT.
Call Link_Down(I,J).
c. Else, if interface I appears in the NEIGHBOR REQUEST list and
nbr_count(I,J) = 0, set nbr_count(I,J) = NBR_HOLD_COUNT.
6. Set nbr_life(I,J) = NBR_HOLD_TIME, nbr_hseq(I,J) = HSEQ, and
nbr_pri(I,J) = PRI.
7.5. Expiration of Timer nbr_life
Upon expiration of the timer nbr_life(I,J) in the neighbor table for
interface I, node i performs the following step:
If nbr_status(I,J) = 1-WAY or 2-WAY, set nbr_status(I,J) = LOST
and nbr_count(I,J) = NBR_HOLD_COUNT. Call Link_Down(I,J).
7.6. Link-Layer Failure Notification
Some link-layer protocols (e.g., IEEE 802.11) provide a notification
that the link to a particular neighbor has failed, e.g., after
attempting a maximum number of retransmissions. If such an
notification is provided by the link layer, then node i SHOULD
perform the following step upon receipt of a link-layer failure
notification for the link (I,J) from local interface I to neighbor
interface J:
If nbr_status(I,J) = 2-WAY, set nbr_status(I,J) = LOST and
nbr_count(I,J) = NBR_HOLD_COUNT. Call Link_Down(I,J).
7.7. Optional Link Metrics
Each node MAY maintain and update one or more link metrics for each
link (I,J), representing the quality of the link, e.g., signal
strength, number of HELLOs received over some time interval,
reliability, stability, bandwidth, etc. Each node MUST declare a
neighbor to be LOST if either NBR_HOLD_COUNT HELLOs are missed or if
no HELLO is received within NBR_HOLD_TIME seconds; however, a node
MAY also declare a neighbor to be LOST based on a link metric being
above or below some threshold. Each node MUST receive at least
HELLO_ACQUIRE_COUNT of the last HELLO_ACQUIRE_WINDOW HELLOs from a
neighbor before declaring the neighbor 1-WAY or 2-WAY; however, a
node MAY require an additional condition based on a link metric being
above or below some threshold, before declaring the neighbor 1-WAY or
2-WAY. This document does not specify any particular link metric,
but an implementation of TBRPF that uses such metrics is considered
to be compliant with this specification.
The function Link_Change(I,J) is called to alert the routing module
whenever nbr_metric(I,J) changes significantly. If the configurable
parameter USE_METRICS is equal to 1, then the metrics nbr_metric(I,J)
are used by the routing module for route computation, as described in
Section 8.
7.8. Configurable Parameters
This section lists the parameters used by the neighbor discovery
protocol, and their proposed default values. All nodes MUST be
configured to have the same value for all of the following
parameters.
Parameter Name Default Value
-------------- -------------
HELLO_INTERVAL 1 second
MAX_JITTER 0.1 second
NBR_HOLD_TIME 3 seconds
NBR_HOLD_COUNT 3
HELLO_ACQUIRE_COUNT 2
HELLO_ACQUIRE_WINDOW 3
8. TBRPF Routing Module
This section describes the TBRPF routing module, which performs
topology discovery and route computation.
8.1. Conceptual Data Structures
In addition to the information required by the neighbor discovery
protocol, each node running TBRPF maintains a topology table TT,
which stores information for each known node and link in the network.
Nodes are identified by their RIDs, i.e., node u is the node whose
RID is u. The following information is stored in the topology table
at node i for each node u and link (u,v):
T(u,v) - Equal to 1 if (u,v) is in node i’s source tree T, and 0
otherwise. The previous source tree is also maintained as old_T.
RN(u) - Equal to 1 if u is in node i’s reported node set RN, and 0
otherwise. The previous reported node set is also maintained as
old_RN.
RT(u,v) - Equal to 1 if (u,v) is in node i’s reported subtree RT,
and 0 otherwise. Since RT is defined as the set of links (u,v) in
T such that u is in RN, this variable need not be maintained
explicitly.
TG(u,v) - Equal to 1 if (u,v) is in node i’s topology graph TG,
and 0 otherwise.
N - The set of 2-way neighbors of node i.
r(u,v) - The list of neighbors that are reporting link (u,v) in
their reported subtree RT. The set of links (u,v) reported by
neighbor j is denoted RT_j.
r(u) - The list of neighbors that are reporting node u in their
reported node set RN.
p(u) - The current parent for node u, equal to the next node on
the shortest path to u.
pred(u) - The node that is the predecessor of node u in the source
tree T. Equal to NULL if node u is not reachable.
pred(j,u) - The node that is the predecessor of node u in the
subtree RT_j reported by neighbor j.
d(u) - The length of the shortest path to node u. If USE_METRICS
= 0, d(u) is the number of hops to node u.
reported(u,v) - Equal to 1 if link (u,v) in TG is reported by
p(u), and 0 otherwise.
tg_expire(u) - Expiration time for links (u,v) in TG.
rt_expire(j,u) - Expiration time for links (u,v) in RT_j.
nr_expire(u,v) - Expiration time for a link (u,v) in TG such that