(a) NRL and NRNL are defined as above.
(b) If USE_METRICS = 1, then the M (metrics) bit is
set to 1 and the link metrics metric(u,v_1),...,
metric(u,v_n) are included in the message.
3. If u is in old_RN:
3.1. Let v_1,..., v_n be the nodes v such that (u,v) is in
old_T but not in TG, and either IMPLICIT_DELETION = 0
or pred(v) is not in RN (or is NULL).
(If IMPLICIT_DELETION = 1 and pred(v) is in RN, then
the deletion of (u,v) is implied by an ADD update for
another link (w,v).)
3.2. If this set of nodes is nonempty, add the update
(DELETE, n, u, v_1,..., v_n) to msg_list(I) for each I.
8.4.7. Processing Topology Updates
When a packet containing a list (msg_list) of TOPOLOGY UPDATE
messages is received from node j, the list is processed according to
the procedure Process_Updates(j, msg_list), defined as follows. In
particular, this procedure updates TT, TG, and the reporting neighbor
lists r(u) and r(u,v). If any link in T has been deleted from TG,
then Update_Source_Tree() and Update_Routing_Table() are called to
provide immediate rerouting.
Process_Updates(j, msg_list)
1. For each update = (subtype, n, NRL, NRNL, u, v_1,..., v_n)
in msg_list:
1.1. Create an entry for u in TT if it does not exist.
1.2. If subtype = FULL, Process_Full_Update(j, update).
1.3. If subtype = ADD, Process_Add_Update(j, update).
1.4. If subtype = DELETE, Process_Delete_Update(j, update).
2. If there exists any link in T that is not in TG:
2.1. Update_Source_Tree().
2.2. Update_Routing_Table().
Process_Full_Update(j, update)
1. Add j to r(u).
2. Set rt_expire(j,u) = current_time + TOP_HOLD_TIME.
3. For each link (u,v) s.t. j is in r(u,v):
3.1. Remove j from r(u,v).
3.2. If pred(j,v) = u, set pred(j,v) = NULL.
4. If j = p(u) OR p(u) = NULL:
4.1. Set tg_expire(u) = current_time + TOP_HOLD_TIME.
4.2. For each v s.t. (u,v) is in TG,
If reported(u,v) = 1, remove (u,v) from TG.
5. Process_Add_Update(j, update).
Process_Add_Update(j, update)
For m = 1,..., n:
((u,v_m) is the mth link in update.)
1. Let v = v_m.
2. Create an entry for v in TT if it does not exist.
3. Add j to r(u,v).
4. If j = p(u) OR p(u) = NULL:
4.1. Add (u,v) to TG.
4.2. Set reported(u,v) = 1.
5. If the M (metrics) bit in update is 1:
5.1. Set metric(j,u,v) to the m-th metric in the update.
5.2. If j = p(u) OR p(u) = NULL:
5.2.1. Set metric(u,v) = metric(j,u,v).
5.2.2. If USE_METRICS = 1, set c(u,v) = metric(u,v).
6. If the D (implicit deletion) bit in update is 1:
6.1. Set w = pred(j,v).
6.2. If (w != NULL AND w != u):
6.2.1. Remove j from r(w,v).
6.2.2. If j = p(w), remove (w,v) from TG.
7. Set pred(j,v) = u. (Set new predecessor.)
8. If m <= NRL (v = v_m is a reported leaf):
8.1. Set leaf_update = (FULL, 0, 0, 0, v).
8.2. Process_Full_Update(j, leaf_update).
9. If m > NRL + NRNL (v = v_m is not reported by j):
9.1. Remove j from r(v).
9.2. Set rt_expire(j,v) = 0.
9.3. For each node w s.t. j is in r(v,w),
remove j from r(v,w).
9.4. If j = p(v), then for each node w s.t. (v,w) is in TG
and reported(v,w) = 1, set reported(v,w) = 0 and set
nr_expire(v,w) = current_time + PER_UPDATE_INTERVAL.
Process_Delete_Update(j, update)
For m = 1,..., n:
((u,v_m) is the mth link in update.)
1. Let v = v_m.
2. Remove j from r(u,v).
3. If pred(j,v) = u, set pred(j,v) = NULL.
4. If j = p(u), remove (u,v) from TG.
8.4.8. Expiring Topology Information
Each node periodically checks for outdated topology information based
on the expiration timers tg_expire(u), rt_expire(j,u), and
nr_expire(u,v), and removes any expired entries from TG and from the
lists r(u) and r(u,v). This is done according to the following
procedure Expire_Links(), which is called periodically just before
the source tree is updated.
Expire_Links()
For each node u in TT other than node i:
1. If tg_expire(u) < current_time, then for each v s.t.
(u,v) is in TG, remove (u,v) from TG.
2. Else, for each v s.t. (u,v) is in TG,
if reported(u,v) = 0 AND nr_expire(u,v) < current_time,
remove (u,v) from TG.
3. For each node j in r(u), if rt_expire(j,u) < current_time:
3.1. Remove j from r(u).
3.2. For each link (u,v) s.t. j is in r(u,v),
remove j from r(u,v).
In addition, the following cleanup steps SHOULD be executed
periodically to remove unnecessary entries from the topology table
TT. A link (u,v) should be removed from TT if it is not in TG and
not in old_T. A node u should be removed from TT if all of the
following conditions hold: r(u) is empty, r(w,u) is empty for all w,
and no link of TG has u as either the head or the tail.
8.4.9. Optional Reporting of Redundant Topology Information
Each node is required to report its reported subtree RT to neighbors.
However, each node (independently of the other nodes) MAY report
additional links, e.g., to provide increased robustness in highly
mobile networks. For example, a node may compute any subgraph H of
TG that contains T, and may report the "reported subgraph" RH which
consists of links (u,v) of H such that u is in RN. In this case,
each periodic update describes RH instead of RT, and each
differential update describes changes to RH. If this option is used,
then the parameter IMPLICIT_DELETION MUST be set to 0, since the
deletion of a link cannot be implied by the addition of another link
if redundant topology information is reported.
8.4.10. Local Topology Changes
This section describes the procedures that are followed when the
neighbor discovery module detects a new link, the loss of a link, or
a change in the metric for a link.
When a link (I,J) from a local interface I to a neighbor interface J
is discovered via the neighbor discovery module, the procedure
Link_Up(I,J) is executed, as defined below. Letting j be the
neighbor node associated with interface J, Link_Up(I,J) adds j to N
(if it does not already belong), updates the preferred local
interface local_if(j) and neighbor interface nbr_if(j) so that the
link from local_if(j) to nbr_if(j) has the minimum metric among all
links from i to j, and updates metric(i,j) to be this minimum metric.
Link_Up(I,J)
1. Let j = nbr_rid(I,J).
2. If j is not in N:
2.1. Add j to N.
2.2. Add (i,j) to TG.
2.3. Set reported(i,j) = 1.
3. If nbr_metric(I,J) < metric(i,j), set local_if(j) = I,
nbr_if(j) = J, and metric(i,j) = nbr_metric(I,J).
4. If USE_METRICS = 1, set cost(i,j) = metric(i,j).
When the loss of a link (I,J) from a local interface I to a neighbor
interface J is detected via the neighbor discovery module, the
procedure Link_Down(I,J) is executed, as defined below. Note that
routes are updated immediately when a link is lost, and if the lost
link is due to a link-layer failure notification, a differential
topology update is sent immediately.
Link_Down(I,J)
1. Let j = nbr_rid(I,J).
2. If there does not exist a link (K,L) from node i to
node j with nbr_status(K,L) = 2-WAY:
2.1. Remove j from N.
2.2. Remove (i,j) from TG.
3. If j is in N:
3.1. Let (K,L) be a link from i to j such that
nbr_metric(K,L) is the minimum metric among
all links from i to j.
3.2. Set local_if(j) = K, nbr_if(j) = L, and
metric(i,j) = nbr_metric(K,L).
3.3. If USE_METRICS = 1, set cost(i,j) = metric(i,j).
5. Update_Source_Tree().
6. Update_Routing_Table().
7. If j is not in N and lost link is due to link-layer failure
notification:
7.1. If (REPORT_FULL_TREE = 0) Update_RN().
7.2. Else, Update_RN_Simple().
7.3. Set msg_list = empty.
7.4. Generate_Diff_Update().
7.5. Send msg_list on all interfaces.
7.6. Set old_T = T and old_RN = RN.
If the metric of a link (I,J) from a local interface I to a neighbor
interface J changes via the neighbor discovery module, the following
procedure Link_Change(I,J) is executed.
Link_Change(I,J)
1. Let j = nbr_rid(I,J).
2. Let (K,L) be a link from i to j such that
nbr_metric(K,L) is the minimum metric among
all links from i to j.
3. Set local_if(j) = K, nbr_if(j) = L, and
metric(i,j) = nbr_metric(K,L).
4. If USE_METRICS = 1, set cost(i,j) = metric(i,j).
8.4.11. Generating Association Messages
This section describes the procedures used to generate INTERFACE
ASSOCIATION, HOST ASSOCIATION, and NETWORK PREFIX ASSOCIATION
messages. Addresses or prefixes in the interface table, host table,
and network prefix table are reported to neighbors periodically every
IA_INTERVAL, HA_INTERVAL, and NPA_INTERVAL seconds, respectively. In
addition, differential changes to the tables are reported every
DIFF_UPDATE_INTERVAL seconds if it is not time for a periodic update
(similar to differential topology updates). Each node reports only
addresses or prefixes that are associated with nodes in the reported
node set RN; this ensures the efficient broadcast of all associated
addresses and prefixes to all nodes in the network.
The generated messages are sent on each interface. Whenever
possible, these messages are combined into the same packet, in order
to minimize the number of control packets transmitted.
Generate_Association_Messages()
1. Generate_Interface_Association_Messages().
2. Generate_Host_Association_Messages().
3. Generate_Network_Prefix_Association_Messages().
Generate_Interface_Association_Messages()
1. If current_time > next_ia_time:
1.1. Set next_ia_time = current_time + IA_INTERVAL.
1.2. For each node u in RN:
1.2.1. Let addr_1,..., addr_n be the interface IP
addresses associated with RID u in the current
interface table.
1.2.2. If this list is nonempty, add the INTERFACE
ASSOCIATION message (FULL, n, u, addr_1,..., addr_n)
to msg_list(I) for each I.
2. Else, for each node u in RN:
2.1. Add the INTERFACE ASSOCIATION message (ADD, n, u,
addr_1,..., addr_n) to msg_list(I) for each I, where
addr_1,..., addr_n are the interface IP addresses that
are associated with RID u in the current interface table
but not in the old interface table.
2.2. Add the INTERFACE ASSOCIATION message (DELETE, n, u,
addr_1,..., addr_n) to msg_list(I) for each I, where
addr_1,..., addr_n are the interface IP addresses that
are associated with RID u in the old interface table
but not in the current interface table.
Generate_Host_Association_Messages()
1. If current_time > next_ha_time:
1.1. Set next_ha_time = current_time + HA_INTERVAL.
1.2. For each node u in RN:
1.2.1. Let addr_1,..., addr_n be the host IP addresses
associated with RID u in the current host table.
1.2.2. If this list is nonempty, add the HOST ASSOCIATION
message (FULL, n, u, addr_1,..., addr_n) to
msg_list(I) for each I.
2. Else, for each node u in RN:
2.1. Add the HOST ASSOCIATION message (ADD, n, u,
addr_1,..., addr_n) to msg_list(I) for each I, where
addr_1,..., addr_n are the host IP addresses that
are associated with RID u in the current host table
but not in the old host table.
2.2. Add the HOST ASSOCIATION message (DELETE, n, u,
addr_1,..., addr_n) to msg_list(I) for each I, where
addr_1,..., addr_n are the host IP addresses that
are associated with RID u in the old host table
but not in the current host table.
Generate_Network_Prefix_Association_Messages()
1. If current_time > next_npa_time:
1.1. Set next_npa_time = current_time + NPA_INTERVAL.
1.2. For each node u in RN:
1.2.1. Let length_1, prefix_1,..., length_n, prefix_n
be the network prefix lengths and prefixes associated
with RID u in the current network prefix table.
1.2.2. If this list is nonempty, add the NETWORK PREFIX
ASSOCIATION message (FULL, n, u, length_1, prefix_1,
..., length_n, prefix_n) to msg_list(I) for each I.
2. Else, for each node u in RN:
2.1. Add the NETWORK PREFIX ASSOCIATION message
(ADD, n, u, prefix_1,..., prefix_n) to msg_list(I) for
each I, where prefix_1,..., prefix_n are the network
prefixes that are associated with RID u in the current
prefix table but not in the old prefix table.
2.1. Add the NETWORK PREFIX ASSOCIATION message
(DELETE, n, u, prefix_1,..., prefix_n) to msg_list(I) for
each I, where prefix_1,..., prefix_n are the network
prefixes that are associated with RID u in the old prefix
table but not in the current prefix table.
8.4.12. Processing Association Messages
When an INTERFACE ASSOCIATION, HOST ASSOCIATION, or NETWORK PREFIX
ASSOCIATION message is received from node j, the interface table,
host table, or network prefix table, respectively, is updated as
described in the following three procedures.
Process_Interface_Association_Messages(j, msg_list)
For each message (subtype, n, u, addr_1,..., addr_n) in msg_list
such that j = p(u):
1. If subtype = FULL, remove all entries with if_rid = u
from the interface table.
2. If subtype = FULL or ADD, then for m = 1,..., n,
add the tuple (if_addr, if_rid, if_expire) to the
interface table, where:
if_addr = addr_m,
if_rid = u,
if_expire = current_time + IA_HOLD_TIME.
3. If subtype = DELETE, then for m = 1,..., n,
remove the tuple (if_addr, if_rid, if_expire) from the
interface table, where if_addr = addr_m and if_rid = u.
Process_Host_Association_Messages(j, msg_list)
For each message (subtype, n, u, addr_1,..., addr_n) in msg_list
such that j = p(u):
1. If subtype = FULL, remove all entries with h_rid = u
from the host table.
2. If subtype = FULL or ADD, then for m = 1,..., n,
add the tuple (h_addr, h_rid, h_expire) to the
host table, where:
h_addr = addr_m,
h_rid = u,
h_expire = current_time + HA_HOLD_TIME.
3. If subtype = DELETE, then for m = 1,..., n,
remove the tuple (h_addr, h_rid, h_expire) from the
host table, where h_addr = addr_m and h_rid = u.
Process_Network_Prefix_Association_Messages(j, msg_list)
For each message (subtype, n, u, length_1, prefix_1, ...,
length_n, prefix_n) in msg_list such that j = p(u):
1. If subtype = FULL, remove all entries with net_rid = u
from the prefix table.
2. If subtype = FULL or ADD, then for m = 1,..., n,
add the tuple (net_prefix, net_length, net_rid,
net_expire) to the network prefix table, where:
net_prefix = prefix_m,
net_length = length_m,
net_rid = u,
net_expire = current_time + NPA_HOLD_TIME.
3. If subtype = DELETE, then for m = 1,..., n,
remove the tuple (net_prefix, net_length, net_rid,
net_expire) from the network prefix table, where
net_prefix = prefix_m, net_length = length_m,
and net_rid = u.
8.4.13. Non-Relay Operation
Nodes with relay priority equal to zero are called non-relay nodes,
and do not forward packets (of any type) that are received from other
nodes. A non-relay node is implemented simply by not generating or
transmitting any TOPOLOGY UPDATE messages. A non-relay node may
report (in association messages) addresses or prefixes that are
associated with itself, but not those associated with other nodes.
HELLO messages must be transmitted in order to establish links with
neighbor nodes. The following procedures can be omitted in non-relay
nodes: Update_RN(), Generate_Periodic_Update(), and
Generate_Diff_Update().
8.5. Configurable Parameters
This section lists the configurable parameters used by the routing
module, and their proposed default values. All nodes MUST have the
same value for all of the following parameters except
REPORT_FULL_TREE and IMPLICIT_DELETION.
Parameter Name Default Value
-------------- -------------
DIFF_UPDATE_INTERVAL 1 second
PER_UPDATE_INTERVAL 5 seconds
TOP_HOLD_TIME 15 seconds
NON_REPORT_PENALTY 1.01
NON_TREE_PENALTY 0.01
IA_INTERVAL 10 seconds
IA_HOLD_TIME 3 * IA_INTERVAL
HA_INTERVAL 10 seconds
HA_HOLD_TIME 3 * HA_INTERVAL
NPA_INTERVAL 10 seconds
NPA_HOLD_TIME 3 * NPA_INTERVAL
USE_METRICS 0
REPORT_FULL_TREE 0
IMPLICIT_DELETION 1
9. TBRPF Flooding Mechanism
This section describes a mechanism for the efficient best-effort
flooding (or network-wide broadcast) of packets to all nodes of a
connected ad-hoc network. This mechanism can be considered an
optimization of the classical flooding algorithm in which each packet
is transmitted by every node of the network. In TBRPF flooding,
information provided by TBRPF is used to decide whether a given
received flooded packet should be forwarded. As a result, each
packet is transmitted by only a relatively small subset of nodes,
thus consuming much less bandwidth than classical flooding.
This document specifies that the flooding mechanism use the IPv4
multicast address 224.0.1.20 (currently assigned by IANA for "any
private experiment"). Every node maintains a duplicate cache to keep
track of which flooded packets have already been received. The
duplicate cache contains, for each received flooded packet, the
flooded packet identifier (FPI), which for IPv4 is composed of the
source IP address, the IP identification, and the fragment offset
values obtained from the IP header [14].
When a node receives a packet whose destination IP address is the
flooding address (224.0.1.20), it checks its duplicate cache for an
entry that matches the packet. If such an entry exists, the node
silently discards the flooded packet since it has already been
received. Otherwise, the node retransmits the packet on all
interfaces (see the exception below) if and only if the following
conditions hold:
1. The TBRPF node associated with the source IP address of the packet
belongs to the set RN of reported nodes computed by TBRPF.
2. When decremented, the ’ip_ttl’ in the IPv4 packet header
(respectively, the ’hop_count’ in the IPv6 packet header) is
greater than zero.
If the packet is to be retransmitted, it is sent after a small random
time interval in order to avoid collisions. If the interface on
which the packet was received is not a MANET interface (see the
Terminology section), then the packet should not be retransmitted on
that interface.
10. Operation of TBRPF in Mobile Ad-Hoc Networks
TBRPF is particularly well suited to MANETs consisting of mobile
nodes with wireless network interfaces operating in peer-to-peer
fashion over a multiple access communications channel. Although
applicable across a much broader field of use, TBRPF is particularly
well suited for supporting the standard DARPA Internet protocols
[3][2]. In the following sections, we discuss practical
considerations for the operation of TBRPF on MANETs.
10.1. Data Link Layer Assumptions
We assume a MANET data link layer that supports broadcast, multicast
and unicast addressing with best-effort (not guaranteed) delivery
services between neighbors (i.e., a pair of nodes within operational
communications range of one another). We further assume that each
interface belonging to a node in the MANET is assigned a unicast data
link layer address that is unique within the MANET’s scope. While
such uniqueness is not strictly guaranteed, the assumption of
uniqueness is consistent with current practices for deployment of the
Internet protocols on specific link layers. Methods for duplicate
link layer address detection and deconfliction are beyond the scope
of this document.
10.2. Network Layer Assumptions
MANETs are formed as collections of routers and non-routing nodes
that use network layer addresses when calculating the MANET topology.
We assume that each node has at least one data link layer interface
(described above) and that each such interface is assigned a network
layer address that is unique within the MANET. (Methods for network
layer address assignment and duplicate address detection are beyond
the scope of this document.) We further assume that each node will
select a unique Router ID (RID) for use in TBRPF protocol messages,
whether or not the node acts as a MANET router. Finally, we assume
that each MANET router supports the multi-hop relay paradigm at the
network layer; i.e., each router provides an inter-node forwarding
service via network layer host routes which reflect the current MANET
topology as perceived by TBRPF.
10.3. Optional Automatic Address Resolution
TBRPF employs a proactive neighbor discovery protocol at the network
layer that maintains bi-directional link state for neighboring nodes
through the periodic transmission of messages. Since TBRPF neighbor
discovery messages contain both the data link and network layer
address of the sender, implementations MAY perform automatic
network-to-data link layer address resolution for the nodes with
which they form links. An implementation may use such a mechanism to
avoid additional message overhead and potential for packet loss
associated with on-demand address resolution mechanisms such as ARP
[15] or IPv6 Neighbor Discovery [16]. Implementations MUST respond
to on-demand address resolution requests in the normal manner.
10.4. Support for Multiple Interfaces and/or Alias Addresses
MANET nodes may comprise multiple interfaces; each with a unique
network layer address. Additionally, MANET nodes may wish to publish
alias addresses such as when multiple network layer addresses are
assigned to the same interface or when the MANET node is serving as a
Mobile IP [17] home agent. Multiple interfaces and alias addresses
are advertised in INTERFACE ASSOCIATION messages, which bind each