reported(u,v) = 0. Such non-reported links can be used
temporarily during rerouting.
metric(j,u,v) - The metric for link (u,v) reported by neighbor j.
metric(u,v) - The metric for link (u,v) in TG. For a neighbor j,
metric(i,j) is the minimum of nbr_metric(I,J) over all 2-WAY links
(I,J) from i to j.
cost(u,v) - The cost for link (u,v), equal to metric(u,v) if
USE_METRICS = 1, and otherwise equal to 1.
local_if(j) - The address of the preferred local interface for
forwarding packets to neighbor j.
nbr_if(j) - The address of the preferred interface of neighbor j.
The routing table consists of a list of tuples of the form (rt_dest,
rt_next, rt_dist, rt_if_id), where rt_dest is the destination IP
address or prefix, rt_next is the interface address of the next hop
of the route, rt_dist is the length of the route, and rt_if_id is the
ID of the local interface through which the next hop can be reached.
Each node also maintains three tables that describe associated IP
addresses or prefixes: the "interface table", which associates
interface IP addresses with router IDs, the "host table", which
associates host IP addresses with router IDs, and the "network prefix
table", which associates network prefixes with router IDs.
The "interface table" consists of tuples of the form (if_addr,
if_rid, if_expire), where if_addr is an interface IP address
associated with the router with RID = if_rid, and if_expire is the
time at which the tuple expires and MUST be removed. The interface
table at a node does NOT contain an entry in which if_addr equals the
node’s own RID; thus, a node does not advertise its own RID as an
associated interface.
The "host table" consists of tuples of the form (h_addr, h_rid,
h_expire), where h_addr is a host IP address associated with the
router with RID = h_rid, and h_expire is the time at which the tuple
expires and MUST be removed.
The "network prefix table" consists of tuples of the form
(net_prefix, net_length, net_rid, net_expire), where net_prefix and
net_length describe a network prefix associated with the router with
RID = net_rid, and net_expire is the time at which the tuple expires
and MUST be removed. A MANET may be configured as a "stub" network,
in which case one or more gateway routers may announce a default
prefix such that net_prefix = net_length = 0. Two copies of each
table are kept: an "old" copy that was last reported to neighbors,
and the current copy that is updated when association messages are
received.
8.2. TOPOLOGY UPDATE Message Format
The TOPOLOGY UPDATE message has the two formats, depending on the
size of the message. The normal format is as follows, and is used
whenever n, NRL, and NRNL all do not exceed 255:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|D|0|0| TYPE | n | NRL | NRNL |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID of u |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID of v_1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ... ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID of v_n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| metric 1 | metric 2 | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The message body contains the n+1 router IDs for nodes u,
v_1,...,v_n, which represent the links (u,v_1),..., (u,v_n). The
first NRL of the v_k are reported leaf nodes, the next NRNL of the
v_k are reported non-leaf nodes, and the last n - (NRL+NRNL) of the
v_k are not reported (not in RN).
The M bit indicates whether or not link metrics are included in the
message. If M = 1, then a 1-octet metric is included for each of the
links (u,v_1),..., (u,v_n), following the last router ID.
The D bit indicates whether or not implicit deletion is used, and
must be set to 1 if and only if IMPLICIT_DELETION = 1.
The TOPOLOGY UPDATE message has the following three subtypes:
FULL (TYPE = 5)
A FULL update (FULL, n, NRL, NRNL, u, v_1,..., v_n) reports that
the links (u,v_1),..., (u,v_n) belong to the sending router’s
reported subtree RT, and that RT contains no other links with tail
u.
ADD (TYPE = 6)
An ADD update (ADD, n, NRL, NRNL, u, v_1,..., v_n) reports that
the links (u,v_1),..., (u,v_n) have been added to the sending
router’s reported subtree RT.
DELETE (TYPE = 7)
A DELETE update (DELETE, n, NRL, NRNL, u, v_1,..., v_n) reports
that the links (u,v_1),..., (u,v_n) have been deleted from the
sending router’s reported subtree RT.
If n, NRL, or NRNL is larger than 255, then the long format of the
TOPOLOGY UPDATE message is used, in which the first 4 octets of the
normal format are replaced by the following 8 octets:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|D|1|0| TYPE | 0 | n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| NRL | NRNL |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
8.3. Interface, Host, and Network Prefix Association Message Formats
The INTERFACE ASSOCIATION (TYPE = 8) and HOST ASSOCIATION (TYPE = 9)
messages have the following format:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|ST | 0 | TYPE | Reserved | n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The message body contains the router ID of the originating node, and
n IP addresses of interfaces (TYPE = 8) or hosts (TYPE = 9) that are
associated with the router ID. The ST field is defined below.
The NETWORK PREFIX ASSOCIATION message (TYPE = 10) has the following
format:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|ST | 0 | TYPE | Reserved | n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PrefixLength | Prefix byte 1 | Prefix byte 2 | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | PrefixLength | Prefix byte 1 | Prefix byte 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The message body contains the router ID of the originating node, and
n network prefixes, each specified by a 1-octet prefix length
followed immediately by the prefix, using the minimum number of whole
octets required. To minimize overhead, the prefix lengths and
prefixes are NOT aligned along word boundaries.
The INTERFACE ASSOCIATION, HOST ASSOCIATION, and NETWORK PREFIX
ASSOCIATION messages each have the following three subtypes (similar
to those for the TOPOLOGY UPDATE message):
FULL (ST = 0)
Indicates that this is a FULL update that includes all interface
addresses, host addresses, or network prefixes associated with the
given router ID.
ADD (ST = 1)
Indicates that the included IP addresses or network prefixes are
associated with the router ID, but may not include all such IP
addresses or network prefixes.
DELETE (ST = 2)
Indicates that the included IP addresses or network prefixes are
no longer associated with the router ID.
8.4. TBRPF Routing Operation
This section describes the operation of the TBRPF routing module.
The operation is divided into the following subsections: periodic
processing, updating the source tree and topology graph, updating the
routing table, updating the reported node set, generating periodic
updates, generating differential updates, processing topology
updates, expiring topology information, optional reporting of
redundant topology information, local topology changes, generating
association messages, processing association messages, and non-relay
operation. The operation is described in terms of procedures (e.g.,
Update_All), which may be executed periodically or in response to
some event, and may be called by other procedures. In all
procedures, node i is the node executing the procedure.
8.4.1. Periodic Processing
Each node executes the procedure Update_All() periodically, at least
once every DIFF_UPDATE_INTERVAL seconds, which is typically equal to
HELLO_INTERVAL. This procedure is defined as follows:
Update_All()
1. For each interface I, create empty message list msg_list(I).
2. For each interface I, generate a HELLO message for
interface I and add it to msg_list(I).
3. Expire_Links().
4. Update_Source_Tree().
5. Update_Routing_Table().
6. If REPORT_FULL_TREE = 0, execute Update_RN(); otherwise (the
full source tree is reported) Update_RN_Simple().
7. If current_time >= next_periodic:
7.1. Generate_Periodic_Update().
7.2. Set next_periodic = current_time + PER_UPDATE_INTERVAL.
8. Else, Generate_Diff_Update().
9. Generate_Association_Messages().
10. For each interface I, send the msg_list(I) on interface I.
11. Set old_T = T and old_RN = RN.
8.4.2. Updating the Source Tree and Topology Graph
The procedure Update_Source_Tree() is a variant of Dijkstra’s
algorithm, which is called periodically and in response to topology
changes, to update the source tree T and the topology graph TG. This
algorithm computes shortest paths subject to two link cost penalties.
The penalty NON_REPORT_PENALTY is added to the cost of links (u,v)
that are not currently reported by the parent p(u) so that, whenever
possible, a link (u,v) is included in T only if it is currently
reported by the parent. To allow immediate rerouting when p(u)
changes, it may be necessary to temporarily use a link (u,v) that is
not currently reported by the new parent. The penalty
NON_TREE_PENALTY is added to the cost of links (u,v) that are not
currently in T, to reduce the number of changes to T. When there
exist multiple paths of equal cost to a given node, router ID is used
to break ties.
The algorithm is defined as follows (where node i is the node
executing the procedure):
Update_Source_Tree()
1. For each node v in TT, set d(v) = INFINITY, pred(v) = NULL,
old_p(v) = p(v), and p(v) = NULL.
2. Set d(i) = 0, p(i) = i, pred(i) = i.
3. Set S = {i}. (S is the set of labeled nodes.)
4. For each node j in N, set d(j) = c(i,j), pred(j) = i,
and p(j) = j. (If USE_METRICS = 0, then all link costs
c(i,j) are 1.)
5. While there exists an unlabeled node u in TT such that
d(u) < INFINITY:
5.1. Let u be an unlabeled node in TT with minimum d(u).
(A heap should be used to find u efficiently.)
5.2. Add u to S (u becomes labeled).
5.3. If p(u) is not equal to old_p(u) (parent has changed):
5.3.1. For each link (u,v) in TG with tail u, if
reported(u,v) = 1, set reported(u,v) = 0 and set
nr_expire(u,v) = current_time + PER_UPDATE_INTERVAL.
5.3.2. If p(u) is in r(u) (p(u) is reporting u):
5.3.2.1. Set tg_expire(u) = rt_expire(p(u),u).
5.3.2.2. If p(u) = u (u is a neighbor), remove all links
(u,v) with tail u from TG.
5.3.2.3. For each link (u,v) with p(u) in r(u,v):
5.3.2.3.1. Add (u,v) to TG and set reported(u,v) = 1.
5.3.2.3.2. Set metric(u,v) = metric(p(u),u,v).
If USE_METRICS=1, set c(u,v)=metric(u,v).
5.4. For each node v such that (u,v) is in TG:
5.4.1. If reported(u,v) = 0,
set cost = c(u,v) + NON_REPORT_PENALTY.
(This penalizes (u,v) if not reported by p(u).)
5.4.2. Else, if p(u) = u AND u is not in r(v),
set cost = c(u,v) + NON_REPORT_PENALTY.
(This penalizes (u,v) if u is a neighbor and is not
reporting v.)
5.4.3. If (u,v) is not in old_T and p(u) != u,
set cost = cost + NON_TREE_PENALTY.
5.4.4. If (d(u) + cost, u) is lexicographically less
than (d(v), pred(v)), set d(v) = d(u) + c(u,v),
pred(v) = u, and p(v) = p(u).
6. Update the source tree T as follows:
6.1. Remove all links from T.
6.2. For each node u other than i such that pred(u) is not
NULL, add the link (pred(u), u) to T.
8.4.3. Updating the Routing Table
The routing table is updated following any change to the source tree
or the association tables (interface table, host table, or network
prefix table). The routing table is updated according to procedure
Update_Routing_Table(), which is defined as follows:
Update_Routing_Table()
1. Remove all tuples from the routing table.
2. For each node u in TT (other than this node) such that p(u) is
not NULL, add the tuple (rt_dest, rt_next, rt_dist, rt_if_id)
to the routing table, where:
rt_dest = u,
rt_if_id = local_if(p(u)),
rt_next = nbr_if(p(u)),
rt_dist = d(u).
3. For each tuple (if_addr, if_rid, if_expire) in the interface
table, if a routing table entry (rt_dest, rt_next, rt_dist,
rt_if_id) exists such that rt_dest = if_rid, add the tuple
(if_addr, rt_next, rt_dist, rt_if_id) to the routing table.
4. For each tuple (h_addr, h_rid, h_expire) in the host table, if
there exists a routing table entry (rt_dest, rt_next, rt_dist,
rt_if_id) such that rt_dest = h_rid, add the tuple (h_addr,
rt_next, rt_dist, rt_if_id) to the routing table, unless an
entry already exists with the same value for h_addr and a
lexicographically smaller value for (rt_dist, rt_dest).
5. For each tuple (net_prefix, net_length, net_rid, net_expire)
in the network prefix table, if there exists a routing table
entry (rt_dest, rt_next, rt_dist, rt_if_id) such that
rt_dest = net_rid, add the tuple (net_prefix/net_length,
rt_next, rt_dist, rt_if_id) to the routing table, unless an
entry already exists with the same value for
net_prefix/net_length and a lexicographically smaller value
for (rt_dist, rt_dest).
8.4.4. Updating the Reported Node Set
Recall that the reported subtree RT is defined to be the set of links
(u,v) in T such that u is in the reported node set RN. Each node
updates its RN immediately before generating periodic or differential
topology updates.
If REPORT_FULL_TREE = 1 (so that a node reports its entire source
tree), then RN simply consists of all reachable nodes, i.e., all
nodes u such that pred(u) is not NULL. The procedure that computes
RN in this manner is called Update_RN_Simple(). The rest of this
section describes how RN is computed assuming REPORT_FULL_TREE = 0.
A node first determines which of its neighbors belong to RN. Node i
includes a neighbor j in RN if and only if node i determines that one
of its neighbors may select i to be its next hop on its shortest path
to j. To make this determination, node i computes the shortest
paths, up to 2 hops, from each neighbor to each other neighbor, using
only neighbors (or node i itself) as an intermediate node, and using
relay priority and router ID to break ties. If a link metric is
used, then shortest paths are computed with respect to the link
metric; otherwise min-hop paths are computed.
After a node determines which neighbors are in RN, each node u (other
than node i) in the topology table is included in RN if and only if
the next hop p(u) to u is in RN. Equivalently, node u is included in
RN if and only if u is in the subtree of T rooted at some neighbor j
that is in RN. Thus, the reported subtree RT includes the subtrees
of T that are rooted at neighbors in RN. Node i also includes itself
in RN; thus RT also includes all local links (i,j) to neighbors j.
The precise procedure for updating RN is defined as follows:
Update_RN()
1. Set RN = empty.
2. For each neighbor s in N such that s is in r(s), i.e.,
such that s is reporting itself:
(Initialize to run Dijkstra for source s, for 2 hops.)
2.1. For each node j in N+{i}, set dist(j) = INFINITY and
par(j) = NULL.
2.2. Set dist(s) = 0 and par(s) = s.
2.3. For each node j in N+{i} such that (s,j) is in TG:
2.3.1. Set dist(j) = metric(s,j), par(j) = j.
2.3.2. For each node k in N such that (j,k) is in TG:
2.3.2.1. Set cost = metric(j,k).
2.3.2.2. If (dist(j) + cost, nbr_pri(j), j)
is lexicographically less than
(dist(k), nbr_pri(par(k)), par(k)),
set dist(k) = dist(j) + cost and par(k) = j.
2.4. For each neighbor j in N, add j to RN if par(j) = i.
3. Add i to RN. (Node i is always in RN.)
4. For each node u in the topology table, add u to RN if p(u)
is in RN.
In some cases it may be desirable to limit the radius (number of
hops) that topology information is propagated. Since each TBRPF
packet is sent only to immediate (1-hop) neighbors, this cannot be
achieved by using a time-to-live field. Instead, the propagation of
topology information can be limited to a radius of K hops by limiting
RN (at all nodes) to include only nodes that are at most K-1 hops
away. Assuming min-hop routing is used, so that d(u) is the number
of hops to node u, this can be done by modifying Step 4 of
Update_RN() as follows:
4. For each node u in the topology table, add u to RN if p(u)
is in RN and d(u) <= K-1.
8.4.5. Generating Periodic Updates
Every PER_UPDATE_INTERVAL seconds, each node generates and transmits,
on all interfaces, a set of FULL TOPOLOGY UPDATE messages (one
message for each node in RN that is not a leaf of T), which describes
the reported subtree RT. Whenever possible, these messages are
included in a single packet, in order to minimize the number of
control packets transmitted.
Each topology update message contains the router IDs for n+1 nodes u,
v_1,...,v_n, which represent the n links (u,v_1),..., (u,v_n). The n
head nodes v_1,..., v_n are divided into three lists in order to
convey additional information and thus reduce the number of messages
that must be generated. In particular, the first NRL head nodes are
leaves of T, thus avoiding the need to generate separate topology
update messages for leaf nodes u. Similarly, the last n-(NRL+NRNL)
head nodes are not in RN, thus avoiding the need to generate separate
topology update messages for nodes u that have been removed from RN.
Periodic update messages are generated according to procedure
Generate_Periodic_Update(), defined as follows (where node i is the
node executing the procedure):
Generate_Periodic_Update()
For each node u in RN (including node i) that is not a leaf of T,
add the update (FULL, n, NRL, NRNL, u, v_1,..., v_n)
to msg_list(I) for each interface I, where:
(a) v_1,..., v_n are the nodes v such that (u,v) is in T,
the first NRL of these are nodes in RN that are leaves of T,
the next NRNL of these are nodes in RN that are not leaves
of T, and the last n-(NRL+NRNL) of these are not in RN.
(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.
8.4.6. Generating Differential Updates
Every DIFF_UPDATE_INTERVAL seconds, if it is not time to generate a
periodic update, and if RT has changed since the last time a topology
update was generated, a set of TOPOLOGY UPDATE messages describing
the changes to RT is generated and transmitted on all interfaces.
These messages are constructed according to procedure
Generate_Differential_Update(), defined as follows:
Generate_Differential_Update()
For each node u in RN:
1. If u is not in old_RN (u was added to RN) and is not a leaf
of T, add the update (FULL, n, NRL, NRNL, u, v_1,..., v_n)
to msg_list(I) for each I, where:
(a) v_1,..., v_n, NRL, and NRNL are defined as above for
periodic updates.
(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.
2. Else, if u is in old_RN and is not a leaf of T:
2.1. Let v_1,..., v_n be the nodes v such that (u,v) is in T
AND at least one of the following 3 conditions holds:
(a) (u,v) is not in old_T, or
(b) v is in old_RN but not in RN, or
(c) v is a leaf and is in RN but not in old_RN.
2.2. If this set of nodes is nonempty, add the update
(ADD, n, NRL, NRNL, u, v_1,..., v_n) to msg_list(I) for
each interface I, where: