RFC 3684
Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)
Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) 🦋
The title block, the vibe check 💖
- RFC number: 3684 🎀
- Working group: Network Working Group
- Category: Experimental 🧪
- Authors: R. Ogier (SRI International), F. Templin (Nokia), and M. Lewis (SRI International) 👑
- Date: February 2004
- Obsoletes / Updates: the title block doesn't list any RFCs this one obsoletes or updates ✨
Status of this Memo
okay so this memo is an Experimental Protocol for the Internet community 🧪. It is NOT an Internet standard, so don't go treating it like one 🙈. The authors are actively asking for discussion and suggestions for improvement, so if you have thoughts, share them! And distribution of this memo is unlimited 💅.
Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved. 🌸
Abstract ✨
Okay, the main character here is TBRPF (Topology Dissemination Based on Reverse-Path Forwarding) 👑. It's a proactive, link-state routing protocol built for mobile ad-hoc networks, and it gives you hop-by-hop routing along shortest paths to every destination 🦋. Each node running TBRPF builds a source tree (giving paths to all reachable nodes) from partial topology info stored in its topology table, using a tweaked version of Dijkstra's algorithm 🧠. To keep the overhead tiny, each node only reports part of its source tree to its neighbors 🤏.
TBRPF mixes periodic updates with differential updates so every neighbor stays in the loop about the reported part of the source tree 💌. Each node can also choose to report extra topology info (all the way up to the full topology) for better robustness when things are super mobile 🏃♀️💨. For neighbor discovery, it uses "differential" HELLO messages that only send changes in neighbor status ✨. The result? HELLO messages that are way smaller than the ones from other link-state protocols, like OSPF 🫶.
Table of Contents 📚
1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements. . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Applicability Section . . . . . . . . . . . . . . . . . . . . 5
5. TBRPF Overview. . . . . . . . . . . . . . . . . . . . . . . . 6
5.1. Overview of Neighbor Discovery . . . . . . . . . . . . 6
5.2. Overview of the Routing Module. .. . . . . . . . . . . 8
6. TBRPF Packets . . . . . . . . . . . . . . . . . . . . . . . . 10
6.1. TBRPF Packet Header. . . . . . . . . . . . . . . . . . 10
6.2. TBRPF Packet Body. . . . . . . . . . . . . . . . . . . 11
6.2.1. Padding Options (TYPE = 0 thru 1). . . . . . . 12
6.2.2. Messages (TYPE = 2 thru 10). . . . . . . . . . 13
7. TBRPF Neighbor Discovery. . . . . . . . . . . . . . . . . . . 13
7.1. HELLO Message Format . . . . . . . . . . . . . . . . . 13
7.2. Neighbor Table . . . . . . . . . . . . . . . . . . . . 14
7.3. Sending HELLO Messages . . . . . . . . . . . . . . . . 15
7.4. Processing a Received HELLO Message. . . . . . . . . . 16
7.5. Expiration of Timer nbr_life . . . . . . . . . . . . . 18
7.6. Link-Layer Failure Notification. . . . . . . . . . . . 18
7.7. Optional Link Metrics. . . . . . . . . . . . . . . . . 18
7.8. Configurable Parameters. . . . . . . . . . . . . . . . 19
8. TBRPF Routing Module. . . . . . . . . . . . . . . . . . . . . 19
8.1. Conceptual Data Structures . . . . . . . . . . . . . . 19
8.2. TOPOLOGY UPDATE Message Format . . . . . . . . . . . . 21
8.3. Interface, Host, and Network Prefix Association
Message Formats. . . . . . . . . . . . . . . . . . . . 23
8.4. TBRPF Routing Operation. . . . . . . . . . . . . . . . 24
8.4.1. Periodic Processing. . . . . . . . . . . . . . 24
8.4.2. Updating the Source Tree and Topology
Graph. . . . . . . . . . . . . . . . . . . . . 25
8.4.3. Updating the Routing Table . . . . . . . . . . 26
8.4.4. Updating the Reported Node Set . . . . . . . . 27
8.4.5. Generating Periodic Updates. . . . . . . . . . 29
8.4.6. Generating Differential Updates. . . . . . . . 29
8.4.7. Processing Topology Updates. . . . . . . . . . 30
8.4.8. Expiring Topology Information. . . . . . . . . 32
8.4.9. Optional Reporting of Redundant Topology
Information. . . . . . . . . . . . . . . . . . 32
8.4.10. Local Topology Changes . . . . . . . . . . . . 33
8.4.11. Generating Association Messages. . . . . . . . 34
8.4.12. Processing Association Messages. . . . . . . . 36
8.4.13. Non-Relay Operation. . . . . . . . . . . . . . 37
8.5. Configurable Parameters. . . . . . . . . . . . . . . . 38
9. TBRPF Flooding Mechanism. . . . . . . . . . . . . . . . . . . 38
10. Operation of TBRPF in Mobile Ad-Hoc Networks. . . . . . . . . 39
10.1. Data Link Layer Assumptions. . . . . . . . . . . . . . 39
10.2. Network Layer Assumptions. . . . . . . . . . . . . . . 39
10.3. Optional Automatic Address Resolution. . . . . . . . . 40
10.4. Support for Multiple Interfaces and/or
Alias Addresses. . . . . . . . . . . . . . . . . . . . 40
10.5. Support for Network Prefixes . . . . . . . . . . . . . 40
10.6. Support for non-MANET Hosts. . . . . . . . . . . . . . 40
10.7. Internet Protocol Considerations . . . . . . . . . . . 41
10.7.1. IPv4 Operation . . . . . . . . . . . . . . . . 41
10.7.2. IPv6 Operation . . . . . . . . . . . . . . . . 41
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 41
12. Security Considerations . . . . . . . . . . . . . . . . . . . 42
13. Acknowledgements. . . . . . . . . . . . . . . . . . . . . . . 42
14. References. . . . . . . . . . . . . . . . . . . . . . . . . . 42
14.1. Normative References . . . . . . . . . . . . . . . . . 42
14.2. Informative References . . . . . . . . . . . . . . . . 43
Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . . 45
Full Copyright Statement. . . . . . . . . . . . . . . . . . . . . 461. Introduction 🌷
Okay, so the intro basically says the same thing as the abstract, just with a bit more detail 💕. TBRPF is a proactive, link-state routing protocol made for mobile ad-hoc networks (MANETs) 🛰️. It gives hop-by-hop routing along shortest paths to each destination 🗺️. Each node running it builds a source tree (giving shortest paths to all reachable nodes) from partial topology info in its topology table, using a modified Dijkstra's algorithm 🧠. To keep overhead low, each node reports only part of its source tree to neighbors 🤏.
TBRPF uses a mix of periodic and differential updates to keep all neighbors up to date on the reported part of its source tree 📬. Each node can also choose to report additional topology information (up to the full topology) so the network holds up better in highly mobile situations 🏎️💨.
TBRPF does neighbor discovery with "differential" HELLO messages, which only report changes in neighbor status 🦋. That's why its HELLO messages are so much smaller than those of other link-state routing protocols, like OSPF [6] 🎀.
TBRPF has two modules: the neighbor discovery module, and the routing module (which handles topology discovery and route computation) 💅. You'll get an overview of both in Section 5 🌈.
2. Requirements ⭐
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL", when they appear in this document, are to be interpreted as described in BCP 14, RFC 2119 [1] 🫶. These are the official requirement words, so pay attention to them! 🔥
This doc also uses internal conceptual variables to describe how the protocol behaves, plus external variables that an implementation has to let system administrators change 🧚. The specific variable names, how their values change, and how their settings affect behavior are there to show the protocol's behavior 🍓. An implementation doesn't have to match those exact forms, as long as its external behavior is consistent with what's written here 💜.
3. Terminology 🧸
Here's the vocab you need to know for TBRPF ✨:
- node: a router that implements TBRPF 🖥️.
- router ID: each node is identified by a unique 32-bit router ID (RID), which for IPv4 is usually equal to the IP address of one of its interfaces 🆔. The term "node u" means the node whose RID is equal to u 💫.
- interface: a node's attachment to a communication facility or medium that it uses to talk to other nodes 🔌. A node can have several interfaces, and an interface can be wireless or wired, and broadcast (e.g., Ethernet) or point-to-point 📡. Each interface is identified by its IP address, and the term "interface I" means the interface whose IP address is I 🏷️.
- link: a link is an ordered pair of interfaces
(I,J), where I and J are on two different nodes, and where interface I has recently received packets sent from interface J 📦. A link(i,j)from node i to node j is said to exist if node i has an interface I and node j has an interface J such that(I,J)is a link ➡️. Nodes i and j are called the "tail" and "head" of the link, respectively 🎯. - bidirectional link: a link
(I,J)where interfaces I and J can both hear each other 👂👂. Also called a 2-way link 🤝. - neighbor node: node j is a neighbor of node i if node i can hear node j on some interface 👋. Node j is a 2-way neighbor if there's a bidirectional link between i and j 💞.
- MANET interface: any wireless interface where two neighbor nodes on that interface don't have to be neighbors of each other 🌀. MANET nodes usually have at least one MANET interface, but that isn't a requirement 🙃.
- topology: the network's topology 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 🕸️. - source tree: the directed tree (denoted
T) that each node computes, which gives shortest paths to all other reachable nodes 🌳. - topology update: a message that reports the state of one or more links 📣.
- parent: the parent of node i for node u is the next node on the computed shortest path from node i to node u 👣.
- predecessor: the predecessor of a node v on the source tree is the node u such that the link
(u,v)is in the source tree ⬅️. - leaf node: a leaf node of the source tree is a node on the source tree that isn't the predecessor of any other node on the source tree 🍃.
- proactive routing protocol: a routing protocol where each node keeps routes to all reachable destinations at all times, whether or not it currently needs to deliver packets to them ⏰. In contrast, an "on-demand" routing protocol only finds and maintains routes when they're actually needed 🙋♀️.
4. Applicability Section ✨
okay so TBRPF is a proactive routing protocol built for mobile ad-hoc networks (MANETs) 🛸💖 It can support networks with up to a few hundred nodes, and you can combine it with hierarchical routing techniques to support way bigger networks 🌈 Because it uses techniques that greatly reduce control traffic, TBRPF can support much larger and denser networks than routing protocols based on the classical link-state algorithm (e.g., OSPF) 👑
The number of nodes it can handle depends on a few things: the MAC data rate, the rate of topology changes, and the network density (average number of neighbors) 🧚 People have reported simulations where TBRPF supported as many as 500 nodes 😭 In simulations with 100 nodes and 20 traffic streams (sources), using IEEE 802.11 with a data rate of 2 Mbps, TBRPF generated approximately 80-120 kb/s of routing control traffic for the scenarios considered, which compared favorably with other MANET routing protocols [7][8] 💅 A proof of correctness for TBRPF can be found in references [8] and [9] 🫶
5. TBRPF Overview
ngl this is the fun part 🦋 TBRPF is made of two main modules: the neighbor discovery module, and the routing module (which performs topology discovery and route computation) 🎀
5.1. Overview of Neighbor Discovery
The TBRPF Neighbor Discovery (TND) protocol lets each node i quickly figure out which neighbor nodes j have a bidirectional link (I,J) between an interface I of node i and an interface J of node j 💜 It also quickly notices when a bidirectional link breaks or becomes unidirectional 👀
the key feature of TND is that it uses "differential" HELLO messages, which only report changes in the status of links ✨ This makes HELLO messages way smaller than the ones in other link-state routing protocols like OSPF, where each HELLO includes the IDs of all neighbors 🙈 Since they're so small, HELLO messages can be sent more often, which means topology changes get detected faster 🔥
TND is designed to be fully modular and independent of the routing module 🌸 TND performs ONLY neighbor sensing, meaning it determines which nodes are (1-hop) neighbors 💅 It does not discover 2-hop neighbors, because that's handled by the routing module 🍓 So TND can be used by other routing protocols, and TBRPF can swap in another neighbor discovery protocol instead of TND, e.g., one provided by the link layer 🦋
Nodes with multiple interfaces run TND separately on each interface, similar to OSPF 🫶 That means each local interface has its own neighbor table, and a HELLO sent on a particular interface only contains information about neighbors heard on that interface 🌈
We note that, in wireless networks, it's possible for a single interface I to receive packets from multiple interfaces J associated with the same neighbor node 🛰️ This could happen, for example, if the neighbor uses a directional antenna with different interfaces representing different beams 📡 For this reason, TBRPF includes neighbor interface addresses in HELLO messages, unlike OSPF, which includes only router IDs in HELLO packets 💖
Each TBRPF node keeps a neighbor table for each local interface I. That table stores state information for each neighbor interface J heard on that interface, i.e., for each link (I,J) between interface I and a neighbor interface J ✨ The status of each link can be 1-WAY, 2-WAY, or LOST 🎀 The neighbor table for interface I decides what goes in HELLO messages sent on interface I, and it gets updated based on HELLO messages received on interface I (and possibly on link-layer notifications) 🧚
Each TBRPF node sends (on each interface) at least one HELLO message per HELLO_INTERVAL 💜 Each HELLO message contains three (possibly empty) lists of neighbor interface addresses, which are formatted as three message subtypes: NEIGHBOR REQUEST, NEIGHBOR REPLY, and NEIGHBOR LOST 🌸 Each HELLO message also carries the current HELLO sequence number (HSEQ), which goes up by one with each transmitted HELLO 🔢
Now, in the following overview of how TND operates, we assume that interface I belongs to node i, and interface J belongs to node j 🫶 When node i changes the status of a link (I,J), it includes the neighbor interface address J in the appropriate list (NEIGHBOR REQUEST/REPLY/LOST) in at most NBR_HOLD_COUNT (typically 3) consecutive HELLOs sent on interface I 🍓 This makes sure that node j either receives one of these HELLOs on interface J, or misses NBR_HOLD_COUNT HELLOs and therefore declares the link (J,I) to be LOST 😭 This technique means a node doesn't have to keep including every 1-WAY or 2-WAY neighbor in HELLOs forever, unlike OSPF 💅
To avoid establishing a link that's likely to be short-lived (i.e., to employ hysteresis) 🌈, node i must receive (on interface I) at least HELLO_ACQUIRE_COUNT (e.g., 2) of the last HELLO_ACQUIRE_WINDOW (e.g., 3) HELLOs sent from a neighbor interface J, before declaring the link (I,J) to be 1-WAY 🛡️ When that happens, node i includes J in the NEIGHBOR REQUEST list in each of its next NBR_HOLD_COUNT HELLO messages sent on interface I, or until a NEIGHBOR REPLY message containing I is received on interface I from neighbor interface J 🎀
If node j receives (on interface J) one of the HELLOs sent from interface I that contains J in the NEIGHBOR REQUEST list, then node j declares the link (J,I) to be 2-WAY (unless it's already 2-WAY) ✨ It then includes I in the NEIGHBOR REPLY list in each of its next NBR_HOLD_COUNT HELLO messages sent on interface J 🦋 Once node i receives one of these HELLOs on interface I, node i declares the link (I,J) to be 2-WAY 🫶
Here's the sad part, but it's important 🥲 If node i receives a HELLO on interface I, sent from neighbor interface J, whose HSEQ shows that at least NBR_HOLD_COUNT HELLOs were missed, or if node i gets no HELLO on interface I sent from interface J within NBR_HOLD_TIME seconds, then node i changes the status of link (I,J) to LOST (unless it's already LOST) 💀 It also includes J in the NEIGHBOR LOST list in each of its next NBR_HOLD_COUNT HELLO messages sent on interface I (unless the link changes status before these transmissions are complete) 🌧️ Node j will either receive one of these HELLOs on interface J or miss NBR_HOLD_COUNT HELLOs; either way, node j declares the link (J,I) to be LOST 💜 That's how both nodes end up agreeing that the link between I and J is no longer bidirectional, even if node j can still hear HELLOs from node i 🙈
Each node may maintain and update one or more link metrics for each link (I,J) from a local interface I to a neighbor interface J, representing the quality of the link ⭐ These link metrics can be used as additional conditions for changing the status of a neighbor, based on the link metric going above or below some threshold 📊 TBRPF also allows link metrics to be advertised in topology updates, and to be used for computing shortest paths 🗺️✨
5.2. Overview of the Routing Module ✨
okay so every TBRPF node keeps a source tree, called T, that gives it the shortest paths to every reachable node 🌳 It builds and updates T from the partial topology info sitting in its topology table, using a tweaked version of Dijkstra's algorithm. To keep overhead low, each node only reports part of its source tree to its neighbors 💅 The core idea came from PTSP [10], which also reports only part of its tree. (TBRPF is still different from PTSP in a bunch of ways, so don't mix them up 🙈) And the current version should not be confused with the previous one [11], which was a full-topology routing protocol. That's a whole different vibe 💀
The part of T a node reports to its neighbors is called the "reported subtree," and it's written as RT 🎀 Each node sends RT in periodic topology updates (like every 5 seconds, for example) and sends changes to RT (additions and deletions) in differential updates that happen more often (like every 1 second, for example) ⚡ The periodic ones are how new neighbors find out about RT, and they make sure every neighbor eventually learns RT even if it misses some updates 🫶 The differential ones are what make sure each topology update spreads quickly to every node it affects 🚀 A received topology update is not forwarded, but it may change RT, and that change gets reported in the next differential or periodic update 🦋 Whenever it's possible, topology updates ride along in the same packet as a HELLO message, so fewer control packets get sent 📦 Also, TBRPF does not require reliable or sequenced delivery of messages, and it doesn't use ACKs or NACKs. No drama there 🌸
TBRPF supports multiple interfaces, associated hosts, and network prefixes 🌈 Info about associated interfaces, hosts, and prefixes gets spread efficiently in periodic and differential updates, the same way topology updates do ✨
Now for the fun part: RT is made up of links (u,v) from T where u is in the "reported node set," or RN 👑 Here's how RN gets computed. Node i puts a neighbor j into RN if and only if node i figures out that one of its neighbors may pick i as its next hop on that neighbor's shortest path to j. To make that call, node i works out the shortest paths, up to 2 hops, from each neighbor to every other neighbor. It only uses neighbors (or node i itself) as intermediate nodes, and it uses relay priority (which is included in HELLO messages) and router ID to break ties 🧠 Once a node has decided which neighbors are in RN, every reachable node u gets included in RN if and only if the next hop on the shortest path to u is in RN 💖 A node also includes itself in RN. So the reported subtree RT ends up with the subtrees of T rooted at neighbors in RN, plus all local links to neighbors. Iconic. 🦋
Lowkey, neighbors in RN are kind of like multipoint relay (MPR) selectors from [12] 🔥 So if node i picks neighbor j to be in RN, node i is basically picking itself to be an MPR of node j. That's a big difference from [12], where a node doesn't pick itself as an MPR. Instead, it picks a subset of its neighbors to be MPRs 🙃
A node with a bigger relay priority reports a bigger part of its source tree (on average), and it's more likely to get picked as a next-hop relay by its neighbors 🍓 A node with relay priority equal to 0 is called a non-relay node, and it never forwards packets that came from other nodes. Not a team player, but it's valid 💀
TBRPF doesn't use sequence numbers for topology updates. That keeps message overhead down and avoids wraparound problems, which is a huge win 🧚 Instead, it uses a technique similar to SPTA [13]. For each link (u,v) that one or more neighbors report, only the next hop p(u) to u is trusted when it comes to the state of that link. (In SPTA, though, each node reports the full topology.) With this trick, each node keeps a topology graph called TG, made of links that are believed to be up, and computes T as the shortest-path tree inside TG 🌸 To allow immediate rerouting, the rule that each link (u,v) in TG must be reported by p(u) gets relaxed temporarily if p(u) changes to a neighbor that isn't reporting that link. Flexible, bestie 💅
Each node is required to report RT, but it may report extra links too, for example to get more 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 is made of links (u,v) of H where u is in RN. For example, H can equal TG, which would give each node the full network topology if every node did this. H can also be a biconnected subgraph that contains T, which would give each node two disjoint paths to every other node, if every node did this too 😭🫶
TBRPF also lets you choose to include link metrics in topology updates, and to compute paths that are shortest with respect to that metric 🎀 This means packets can take paths that are higher quality than minimum-hop paths. Main character energy 👑
TBRPF can also trade path optimality for less control traffic in networks with a large diameter 🌍 How much approximation happens is set by the configurable parameter NON_TREE_PENALTY. Options, options 🦋
6. TBRPF Packets 🎁
Nodes send TBRPF protocol data in contiguous units called packets 📦 Each packet has a header, optional header extensions, and a body made of one or more messages, plus padding options when they're needed. To make life easier for receivers, senders SHOULD insert padding options as necessary to line up multi-octet words inside the TBRPF packet on natural boundaries (meaning modulo-8/4/2 addresses for 64/32/16-bit words, respectively) 🧩 Receivers MUST be capable of processing multi-octet words whether or not they're aligned on natural boundaries. Receivers have to be ready for anything 💪 The next sections spell out the elements of the TBRPF packet in more detail 💜
6.1. TBRPF Packet Header 💌
TBRPF packet headers are variable-length, with a minimum of one octet. The format looks like this:
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 check the L bit to figure out whether the length field is there. 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 provides a packet length. No length, no entry 🚪💀
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 gives you 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. Matchmaking for addresses 💘
Reserved Reserved for future use; MUST be zero. 🌙
6.2. TBRPF Packet Body 🍰
The TBRPF packet body is the concatenation of one or more TBRPF messages, with padding options where necessary. Messages and padding options inside 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 before processing all the preceding elements [2]. That's a hard no on skipping ahead 🙅♀️ 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, for example to satisfy alignment requirements for other elements [2]. Padding options can show up 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, and 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 with a value between 0 - 253, which specifies the number of zero-valued octets that immediately follow. That gives a maximum total of 255 padding octets. Big padding energy 🧸
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, for example messages with unrecognized types, messages with a non-integral number of elements, or messages with fewer elements than indicated, and so on. In all cases, upon detecting an error, the receiver MUST discontinue processing the current TBRPF packet and discard any unprocessed elements. Error detected? Stop, drop, and roll 🛑
7. TBRPF Neighbor Discovery 🔍
This section describes the TBRPF Neighbor Discovery (TND) protocol, which lets each node quickly detect bidirectional links (I,J) between a local interface I and a neighbor interface J, and quickly detect when those links go down 🚦 The interface between TND and the routing module is defined by the neighbor table that TND maintains, plus three procedures: Link_Up(I,J), Link_Down(I,J), and Link_Change(I,J). TND calls these 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 ✨
okay so HELLO messages come in three flavors 💅 NEIGHBOR REQUEST (TYPE = 2), NEIGHBOR REPLY (TYPE = 3), and NEIGHBOR LOST (TYPE = 4). Every HELLO subtype looks like this:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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 is the sending node's relay priority, an integer between 0 and 15. A node with a higher relay priority is more likely to be picked 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. And 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 🧮
Now the combo move 🫶 A HELLO message is the concatenation of a NEIGHBOR REQUEST message, a NEIGHBOR REPLY message, and a NEIGHBOR LOST message. Each of the last two gets skipped if its list of neighbor interface addresses is empty. So a HELLO message always includes a (possibly empty) NEIGHBOR REQUEST. Main character energy, always there 👑
7.2. Neighbor Table 🗂️
Every node keeps, for each of its local interfaces I, a neighbor table. It stores state info for each neighbor interface J that has recently sent HELLOs to interface I. The entry for neighbor interface J in the table for I has these variables:
nbr_rid(I,J)- The router ID of the node associated with neighbor interfaceJ.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) left beforenbr_status(I,J)must be changed to LOST if no further HELLO message from interfaceJarrives. It gets set toNBR_HOLD_TIMEevery time a HELLO comes in on interfaceIfrom interfaceJ. ⏳nbr_hseq(I,J)- The value ofHSEQin the last HELLO message received on interfaceIfrom interfaceJ. It's used to figure out how many HELLOs have been missed 🕵️♀️nbr_count(I,J)- The remaining number of times a NEIGHBOR REQUEST/REPLY/LOST message containingJmust be sent on interfaceI.hello_history(I,J)- A list of the sequence numbers of the lastHELLO_ACQUIRE_WINDOWHELLO messages received on interfaceIfrom interfaceJ. 📜nbr_metric(I,J)- An optional measure of the link quality(I,J), an integer between 1 and 255, where smaller values mean better quality. It defaults to 1 if not used.nbr_pri(I,J)- The relay priority of the node associated with interfaceJ. 💅
The entry for interface J in the neighbor table for interface I may be deleted if no HELLO has come in on interface I from interface J within the last 2*NBR_HOLD_TIME seconds. (It sticks around while NEIGHBOR LOST messages containing J are still going out 📣.) And no entry for a given interface J is the same as an entry with nbr_status(I,J) = LOST and hello_history(I,J) = NULL. Bestie, that's just nothing, lol 💀
The three possible values of nbr_status(I,J) have these informal vibes (the exact meanings are defined by the protocol):
LOST: interface I hasn't gotten a sufficient number of HELLO messages recently from interface J. 👻
1-WAY: interface I has gotten a sufficient number of HELLO messages recently from interface J, but the link isn't 2-WAY yet 🌗
2-WAY: interfaces I and J have both gotten a sufficient number of HELLO messages recently from each other. Mutual vibes 🫶💜
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) ⚡. But here's the catch: to avoid HSEQ wrapping around to the same number before a neighbor that stops receiving HELLOs changes the link status to LOST, the time between two consecutive HELLO messages (sent on a given interface) MUST be greater than NBR_HOLD_TIME/128 second. Timing is everything, babe ⏰
To avoid synchronization of control messages (which can lead to collisions 💥), HELLO messages SHOULD NOT be transmitted at equal intervals. To get that, a node MAY choose the interval between consecutive HELLO messages to be HELLO_INTERVAL - jitter, where jitter is picked 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 carries the sequence number HSEQ, which goes up by 1 (modulo 256) every 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 come from the following steps at node i for each interface I:
- For each interface
Jsuch thatnbr_status(I,J) = LOSTandnbr_count(I,J) > 0, includeJin the NEIGHBOR LOST message and decrementnbr_count(I,J). - For each interface
Jsuch thatnbr_status(I,J) = 1-WAYandnbr_count(I,J) > 0, includeJin the NEIGHBOR REQUEST message and decrementnbr_count(I,J). - For each interface
Jsuch thatnbr_status(I,J) = 2-WAYandnbr_count(I,J) > 0, includeJin the NEIGHBOR REPLY message and decrementnbr_count(I,J).
⚠️ Restart alert! If a node restarts, so that all entries get wiped from the neighbor table, then the node MUST make sure that (for each interface) at least one of these two conditions is satisfied:
- 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. - Letting
HSEQ_LASTdenote the sequence number of the last HELLO sent before restarting, the sequence number of the first HELLO sent after restarting is set toHSEQ_LAST + NBR_HOLD_COUNT + 1(modulo 256).
Either of these conditions makes sure 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. Clean reset, no ghosts 👻✨
7.4. Processing a Received HELLO Message 📥
When a node gets a HELLO message, it grabs 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 comes from the TBRPF packet header. Otherwise, it's 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 does the following steps:
- If the neighbor table for interface
Idoesn't have an entry for interfaceJ, create one withnbr_rid(I,J) = j,nbr_status(I,J) = LOST(temporarily),nbr_count(I,J) = 0, andnbr_hseq(I,J) = HSEQ. - Update
hello_history(I,J)to reflect the received HELLO message. Ifnbr_hseq(I,J) > HSEQ(due to wraparound), setnbr_hseq(I,J) = nbr_hseq(I,J) - 256. 🔄 - If
nbr_status(I,J) = LOSTandhello_history(I,J)shows thatHELLO_ACQUIRE_COUNTof the lastHELLO_ACQUIRE_WINDOWHELLO messages from interfaceJhave been received:- a. If interface
Idoesn't appear in the NEIGHBOR REQUEST list or the NEIGHBOR REPLY list, setnbr_status(I,J) = 1-WAYandnbr_count(I,J) = NBR_HOLD_COUNT. - b. Else, set
nbr_status(I,J) = 2-WAYandnbr_count(I,J) = NBR_HOLD_COUNT. CallLink_Up(I,J). 🎉
- a. If interface
- Else, if
nbr_status(I,J) = 1-WAY:- a. If
HSEQ - nbr_hseq(I,J) > NBR_HOLD_COUNT, then setnbr_status(I,J) = LOSTandnbr_count(I,J) = NBR_HOLD_COUNT. - b. Else, if interface
Iappears in the NEIGHBOR REQUEST list, setnbr_status(I,J) = 2-WAYandnbr_count(I,J) = NBR_HOLD_COUNT. CallLink_Up(I,J). - c. Else, if interface
Iappears in the NEIGHBOR REPLY list, setnbr_status(I,J) = 2-WAYandnbr_count(I,J) = 0. CallLink_Up(I,J).
- a. If
- Else, if
nbr_status(I,J) = 2-WAY:- a. If interface
Iappears in the NEIGHBOR LOST list, setnbr_status(I,J) = LOSTandnbr_count(I,J) = 0. CallLink_Down(I,J). 💔 - b. Else, if
HSEQ - nbr_hseq(I,J) > NBR_HOLD_COUNT, setnbr_status(I,J) = LOSTandnbr_count(I,J) = NBR_HOLD_COUNT. CallLink_Down(I,J). - c. Else, if interface
Iappears in the NEIGHBOR REQUEST list andnbr_count(I,J) = 0, setnbr_count(I,J) = NBR_HOLD_COUNT.
- a. If interface
- Set
nbr_life(I,J) = NBR_HOLD_TIME,nbr_hseq(I,J) = HSEQ, andnbr_pri(I,J) = PRI. 🔁
7.5. Expiration of Timer nbr_life ⏰
When the timer nbr_life(I,J) in the neighbor table for interface I expires, node i does this one 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) give a notification that the link to a particular neighbor has failed, e.g., after trying a maximum number of retransmissions 🔧. If the link layer provides such a notification, then node i SHOULD do the following step when it gets 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 ✨
okay so this one is giving "optional but make it iconic" 💅 Each node MAY maintain and update one or more link metrics for each link (I,J) 🦋 Think signal strength, how many HELLOs you got over some time window, reliability, stability, bandwidth, the whole vibe. 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. BUT a node MAY also declare a neighbor to be LOST based on a link metric being above or below some threshold, so there's room to be picky 🌸
Same energy for coming back to life 🧚 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. A node MAY require an additional condition based on a link metric being above or below some threshold before it declares the neighbor 1-WAY or 2-WAY. Literally so much flexibility 😭
Real talk: this document doesn't specify any particular link metric. But an implementation of TBRPF that uses such metrics is considered to be compliant with this specification, so you're totally good to bring your own metrics 🫶
The function Link_Change(I,J) gets called to alert the routing module whenever nbr_metric(I,J) changes significantly. And if the configurable parameter USE_METRICS is equal to 1, the metrics nbr_metric(I,J) are used by the routing module for route computation, as described in Section 8. Metrics on, route math gets spicy 🔥
7.8. Configurable Parameters 💜
This section lists the parameters used by the neighbor discovery protocol, along with their proposed default values. All nodes MUST be configured to have the same value for all of the following parameters. Non-negotiable bestie, everyone has to match 🙈
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 38. TBRPF Routing Module 🧚
This section is where the magic happens. The TBRPF routing module does topology discovery and route computation, and honestly it's the main character of this whole protocol 👑
8.1. Conceptual Data Structures 🎀
Okay so besides everything the neighbor discovery protocol already needs, each node running TBRPF keeps a topology table TT. This table stores info about every known node and link in the network. Nodes are identified by their RIDs, so node u is the node whose RID is u. At node i, the topology table holds the following for each node u and link (u,v):
T(u,v): equals 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): equals 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): equals 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 doesn't need to be maintained explicitly 🙌TG(u,v): equals 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): equals 1 if link (u,v) in TG is reported by p(u), and 0 otherwise.tg_expire(u): the expiration time for links (u,v) in TG.rt_expire(j,u): the expiration time for links (u,v) in RT_j.nr_expire(u,v): the expiration time for a link (u,v) in TG such that reported(u,v) = 0. These non-reported links can be used temporarily during rerouting, which is very clever ngl ✨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). It equals metric(u,v) if USE_METRICS = 1, and otherwise equals 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 is a list of tuples of the form (rt_dest, rt_next, rt_dist, rt_if_id). Here, 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 keeps three tables that describe associated IP addresses or prefixes. There's the "interface table", which links interface IP addresses to router IDs. There's the "host table", which links host IP addresses to router IDs. And there's the "network prefix table", which links network prefixes to router IDs. Three tables, one goal: knowing who's who 🫶
The "interface table" is made of tuples of the form (if_addr, if_rid, if_expire). Here, 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. So a node does not advertise its own RID as an associated interface. Which, honestly, is a very polite choice 🙈
The "host table" is made of tuples of the form (h_addr, h_rid, h_expire). Here, 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" is made of tuples of the form (net_prefix, net_length, net_rid, net_expire). Here, 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 that 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 gets updated when association messages are received.
8.2. TOPOLOGY UPDATE Message Format 🦋
The TOPOLOGY UPDATE message comes in two formats, depending on how big the message is. The normal format is below, and it's 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 holds the n+1 router IDs for nodes u, v_1,...,v_n. These 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). Sorting party 🎉
The M bit tells you 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 tells you whether or not implicit deletion is used. It must be set to 1 if and only if IMPLICIT_DELETION = 1.
The TOPOLOGY UPDATE message has 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. Full send, no leftovers 🍓
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. New friends just dropped ✨
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. Bye bye, links 👋
If n, NRL, or NRNL is larger than 255, the long format of the TOPOLOGY UPDATE message gets used instead. In this version, the first 4 octets of the normal format get 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 ✨
okay so the INTERFACE ASSOCIATION (TYPE = 8) and HOST ASSOCIATION (TYPE = 9) messages are literal twins 👯♀️ and they look like this:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|ST | 0 | TYPE | Reserved | n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+the body holds the router ID of the originating node 🆔 plus n IP addresses of interfaces (TYPE = 8) or hosts (TYPE = 9) that are associated with that router ID. the ST field gets explained right below 👀
the NETWORK PREFIX ASSOCIATION message (TYPE = 10) is the glow-up version 💅 and it's laid out like this:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|ST | 0 | TYPE | Reserved | n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PrefixLength | Prefix byte 1 | Prefix byte 2 | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | PrefixLength | Prefix byte 1 | Prefix byte 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+the body has the router ID of the originating node, then n network prefixes. each prefix is a 1-octet prefix length followed right away by the prefix itself, using the minimum number of whole octets needed 🧩. and here's the spicy bit 🌶️: the prefix lengths and prefixes are NOT aligned along word boundaries 🙈 they're packed in tight to keep the overhead low 🦋
INTERFACE ASSOCIATION, HOST ASSOCIATION, and NETWORK PREFIX ASSOCIATION each come with the same three subtypes, kinda like the TOPOLOGY UPDATE message does 🎀
FULL (ST = 0): this is a FULL update 💖 that includes every interface address, host address, or network prefix associated with the given router ID.ADD (ST = 1): the included IP addresses or network prefixes are associated with the router ID, but this might not be the whole list 🤷♀️DELETE (ST = 2): the included IP addresses or network prefixes are no longer associated with the router ID 💀
8.4. TBRPF Routing Operation 🗺️
okay now we're in the routing brain 🧠 this section walks through how the TBRPF routing module actually operates. it's broken into these pieces: 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 📋
everything is described as procedures (like Update_All), which can run on a timer or because of some event, and they can also call each other 📞. in every procedure, node i is the node running it. so "i" is always the main character 👑
8.4.1. Periodic Processing
every node runs the procedure Update_All() periodically, at least once every DIFF_UPDATE_INTERVAL seconds 🕰️ which is typically equal to HELLO_INTERVAL. here's the procedure:
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
Update_Source_Tree() is a variant of Dijkstra's algorithm 🧮 and it runs periodically and whenever topology changes happen, to update the source tree T and the topology graph TG. it computes shortest paths while dealing with two link cost penalties 💸
the first one, NON_REPORT_PENALTY, gets added to links (u,v) that the parent p(u) isn't currently reporting. the goal is that, whenever possible, a link (u,v) only lands in T if the parent is actually reporting it ✨. to allow immediate rerouting when p(u) changes, it could be necessary to temporarily use a link (u,v) that the new parent isn't reporting yet 🔄
the second one, NON_TREE_PENALTY, gets added to links (u,v) that aren't currently in T, so there are fewer changes to T 🫶. and when several paths tie on cost to the same node, router ID breaks the tie 🏆
the algorithm goes like this (node i is the one running it):
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 gets refreshed after any change to the source tree or to the association tables (interface table, host table, or network prefix table) 🔁. the job is handled by the procedure Update_Routing_Table(), which goes like this:
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
quick reminder 📌 the reported subtree RT is the set of links (u,v) in T where u is in the reported node set RN. every node updates its RN right before it generates periodic or differential topology updates ⏰
if REPORT_FULL_TREE = 1 (so the node reports its entire source tree 🌳), then RN is just every reachable node, meaning every node u where pred(u) isn't NULL. that calculation is called Update_RN_Simple(). the rest of this section explains how RN gets computed when REPORT_FULL_TREE = 0 🫧
first, a node figures out which of its neighbors belong in RN. node i puts a neighbor j into RN if and only if node i determines that one of its neighbors might pick i as its next hop on the shortest path to j 🎯. to figure that out, node i computes the shortest paths, up to 2 hops, from each neighbor to each other neighbor, only using neighbors (or node i itself) as intermediate nodes, and it uses relay priority and router ID to break ties. if a link metric is in use, the shortest paths are computed with respect to that metric; otherwise, min-hop paths get computed 📏
once node i knows which neighbors are in RN, each node u (other than node i) in the topology table gets included in RN if and only if its next hop p(u) is in RN 💅. put another way, u is in RN if and only if u sits in the subtree of T rooted at some neighbor j that's in RN. so the reported subtree RT includes the subtrees of T rooted at neighbors in RN. node i also counts itself in RN, which means RT includes all the 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.Okay so sometimes you only want topology info to travel K hops and no farther 🌸 A time-to-live field can't do that job, though, because every TBRPF packet only goes to immediate (1-hop) neighbors 🙈 So instead you limit RN at every node so it only includes nodes that are at most K-1 hops away. This assumes min-hop routing, so d(u) is the number of hops to node u. To make that happen, you swap Step 4 of Update_RN() for this:
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 makes and sends a set of FULL TOPOLOGY UPDATE messages on all interfaces, one for each node in RN that isn't a leaf of T 💖 These describe the reported subtree RT. Whenever it can, a node squeezes everything into a single packet so there are fewer control packets flying around 🫶
Each topology update message holds 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 get split into three lists, which is lowkey genius because it means fewer messages. The first NRL head nodes are leaves of T, so leaf nodes u don't need their own separate messages. The last n-(NRL+NRNL) head nodes aren't in RN, so nodes u that got removed from RN don't need separate messages either ✨
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, as long as it isn't periodic-update time, and as long as RT has changed since the last topology update went out, a set of TOPOLOGY UPDATE messages describing the changes to RT gets generated and sent on all interfaces 💅 Here's how that works, via Generate_Differential_Update():
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:
(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 carrying a list (msg_list) of TOPOLOGY UPDATE messages arrives from node j, it gets handled by the procedure Process_Updates(j, msg_list), shown below 🫶 This one is the main updater: it keeps TT, TG, and the reporting neighbor lists r(u) and r(u,v) up to date. If any link in T has been deleted from TG, then Update_Source_Tree() and Update_Routing_Table() get called so rerouting happens right away.
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().Here's the FULL update handler, which is where the real drama happens 😭
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).And the ADD handler, which does most of the heavy lifting ✨
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.And finally the DELETE handler, which is short and sweet 💅
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 ⏳
Every node periodically checks for outdated topology info using the expiration timers tg_expire(u), rt_expire(j,u), and nr_expire(u,v). Any expired entries get removed from TG and from the lists r(u) and r(u,v) 🧚 This is handled by Expire_Links(), which gets 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).Also, the following cleanup steps SHOULD be executed periodically to get rid of unnecessary entries in 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 its neighbors 🫶 But each node (totally independently of the others) MAY report additional links, for example to add robustness in highly mobile networks. A node may compute any subgraph H of TG that contains T, and may report the "reported subgraph" RH, which consists of the links (u,v) of H such that u is in RN. When that happens, 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. The reason is that a link's deletion can't be implied by another link's addition once redundant topology info is being reported. 🙅♀️
8.4.10. Local Topology Changes 🍓
This section covers the procedures that kick in 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 gets discovered through the neighbor discovery module, the procedure Link_Up(I,J) runs, as defined below. Letting j be the neighbor node associated with interface J, Link_Up(I,J) adds j to N (if it isn't already in there). It also 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. Then it updates metric(i,j) to be that 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).Okay so when a link (I,J) comes up 🌸, we do this little checklist ✨. First we look up j, the neighbor's router ID. If j isn't in N yet, it gets added, the (i,j) pair goes into TG, and reported(i,j) gets set to 1 🦋. Then, if this link's metric is better (lower) than what we already have, we swap in this interface and its metric 💅. And if USE_METRICS is 1, cost(i,j) just copies the metric 🎀.
When the neighbor discovery module notices that a link (I,J) from a local interface I to a neighbor interface J has been lost, Link_Down(I,J) runs 🔥. Routes get updated immediately when a link dies, and if the link-layer failure notification is what told us, a differential topology update gets sent right away 🚀.
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) changes via the neighbor discovery module, Link_Change(I,J) runs instead 💜.
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 is all about making the INTERFACE ASSOCIATION, HOST ASSOCIATION, and NETWORK PREFIX ASSOCIATION messages 🧚. Addresses or prefixes in the interface table, host table, and network prefix table get reported to neighbors on a regular schedule: every IA_INTERVAL, HA_INTERVAL, and NPA_INTERVAL seconds, respectively 🕰️. Differential changes to those tables get reported every DIFF_UPDATE_INTERVAL seconds whenever it isn't time for a periodic update, kind of like differential topology updates 💖. Each node only reports the addresses or prefixes tied to nodes in the reported node set RN. This is what keeps broadcasting every associated address and prefix to the whole network efficient 🌈.
The messages go out on each interface 📡. Whenever possible, they get bundled into the same packet so fewer control packets get sent 🫶.
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 shows up from node j, the matching table gets updated: the interface table, host table, or network prefix table, respectively 💅. The following three procedures spell out exactly how that happens 📝.
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 🍓. They don't forward packets of any type that come in from other nodes. A non-relay node just skips generating or transmitting any TOPOLOGY UPDATE messages 🌙. It can still report, in association messages, the addresses or prefixes tied to itself, but not the ones tied to other nodes 🫧. HELLO messages must be transmitted in order to establish links with neighbor nodes 📡. The following procedures can be left out in non-relay nodes: Update_RN(), Generate_Periodic_Update(), and Generate_Diff_Update() 💀.
8.5. Configurable Parameters 💜
This section is the list of configurable parameters the routing module uses, along with 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 19. TBRPF Flooding Mechanism ✨
okay so this section is about flooding, which is basically how you get a packet to every single node in a connected ad-hoc network 📡🌸 Classic flooding is kinda messy because every node retransmits every packet. TBRPF flooding is the optimized version. It uses info TBRPF already has to decide whether a received flooded packet should be forwarded at all. So each packet only gets sent by a small subset of nodes, which saves a LOT of bandwidth 💅 it's giving efficiency, bestie 🦋
This document says the flooding mechanism uses the IPv4 multicast address 224.0.1.20, which IANA currently has assigned for "any private experiment" 🧚 Every node keeps a duplicate cache so it can remember which flooded packets it has already seen 💜 For each one, the cache stores the flooded packet identifier (FPI). For IPv4, the FPI is built from the source IP address, the IP identification, and the fragment offset values from the IP header [14] ✨
Now the actual logic. When a node gets a packet whose destination IP address is the flooding address (224.0.1.20), it checks the duplicate cache for a matching entry 👀 If there's already a match, the node silently discards the flooded packet, because it already got it. 🙈 If there's no match, the node retransmits the packet on all interfaces (see the exception below), but ONLY if both of these are true:
- The TBRPF node associated with the source IP address of the packet belongs to the set RN of reported nodes computed by TBRPF.
- When decremented, the
ip_ttlin the IPv4 packet header (respectively, thehop_countin the IPv6 packet header) is greater than zero.
If the packet does get retransmitted, it goes out after a small random time interval so nodes don't all talk over each other and collide 🌈 And if the interface the packet came in on isn't a MANET interface (check the Terminology section), then the packet should not be retransmitted on that interface. 🫶
10. Operation of TBRPF in Mobile Ad-Hoc Networks
TBRPF is especially iconic for MANETs made of mobile nodes with wireless interfaces that talk peer-to-peer over a multiple access channel 📱✨ It's applicable way beyond that, but it's particularly good at supporting the standard DARPA Internet protocols [3][2] 💖 The next sections are the practical stuff for running TBRPF on MANETs.
10.1. Data Link Layer Assumptions
Here's what we assume about the MANET data link layer: it supports broadcast, multicast, and unicast addressing, with best-effort (not guaranteed) delivery between neighbors. Neighbors just means two nodes within operational communications range of each other 🦋 We also assume every interface on a node in the MANET gets a unicast data link layer address that's unique within the MANET's scope. Is that uniqueness strictly guaranteed? Nope, not really 🙃 But it matches what current practice looks like for running Internet protocols on specific link layers, so it's a fair assumption. And figuring out duplicate link layer address detection and deconfliction? That's out of scope for this document 🫠
10.2. Network Layer Assumptions
MANETs are built from routers and non-routing nodes that use network layer addresses to work out the MANET topology 🗺️✨ We assume each node has at least one data link layer interface (from above), and each of those interfaces gets a network layer address that's unique within the MANET. (Address assignment and duplicate address detection at the network layer are beyond the scope of this document, so don't come for me on that 💅) We also assume every node picks a unique Router ID (RID) for TBRPF protocol messages, whether or not it's acting as a MANET router. And finally, we assume each MANET router supports the multi-hop relay paradigm at the network layer. In other words, each router provides inter-node forwarding through network layer host routes that reflect the current MANET topology as TBRPF sees it 🌸
10.3. Optional Automatic Address Resolution
TBRPF uses a proactive neighbor discovery protocol at the network layer. It keeps bi-directional link state for neighboring nodes by sending messages periodically 🔁 Since TBRPF neighbor discovery messages carry 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 they form links with 🧠 That's a neat trick, because it avoids the extra message overhead and the chance of packet loss that come with on-demand address resolution like ARP [15] or IPv6 Neighbor Discovery [16]. Still, implementations MUST respond to on-demand address resolution requests in the normal manner. No skipping that part, periodt 💅
10.4. Support for Multiple Interfaces and/or Alias Addresses
MANET nodes can have multiple interfaces, each with its own unique network layer address 🌈 Nodes may also want to publish alias addresses, like when several network layer addresses are assigned to the same interface, or when the MANET node is acting as a Mobile IP [17] home agent 🏠 All of these multiple interfaces and alias addresses get advertised in INTERFACE ASSOCIATION messages, which bind each address to the node's RID 🎀
10.5. Support for Network Prefixes
MANET routers can advertise network prefixes. They might have found them on attached networks, picked them up as external routes from other protocols, or gotten them some other way 🌟 These prefixes get advertised in NETWORK PREFIX ASSOCIATION messages, which bind each prefix to the node's RID 🧚
10.6. Support for non-MANET Hosts
Non-MANET hosts can connect to MANET routers through on-demand mechanisms like ARP or IPv6 Neighbor Discovery 🫶 But these connections don't count as a MANET link, so they never show up in TBRPF topology updates. Instead, non-MANET hosts get advertised in HOST ASSOCIATION messages, which bind each host's IP address to the node's RID 💜
10.7. Internet Protocol Considerations
TBRPF packets are carried over UDP/IP 📦 Port 712 has been assigned by IANA for exclusive use by TBRPF 🔒 In private networks, implementations MAY use alternate data delivery services (raw IP or local data-link encapsulation, for example). But if you do switch, that choice MUST be consistent across all MANET routers in the private network, no exceptions 🙅♀️ And in every implementation, the data delivery service MUST provide a checksum facility. Non-negotiable, bestie 💀
The following sections cover how TBRPF runs over UDP/IP ✨
10.7.1. IPv4 Operation
When IPv4 is used, TBRPF nodes obey the IPv4 host and router requirements [4][5] 📜 TBRPF packets go to the multicast address 224.0.0.2 (All Routers), so they reach every TBRPF router within single-hop transmission range of the sender 📡 And TBRPF routers MUST NOT forward packets sent to that multicast address. Hard no 🚫
Non-negligible packet loss can happen because of link failure, interference, and so on, so implementations SHOULD avoid IPv4 fragmentation and reassembly whenever they can. The way to do that is splitting big TBRPF protocol packets into multiple smaller packets at the application layer 🧩 When fragmentation can't be avoided, senders SHOULD NOT send TBRPF packets that exceed the minimum reassembly buffer size ([4], section 3.3.2) for all receivers in the network 🍓
10.7.2. IPv6 Operation
The IPv6 version of TBRPF is basically the same as the IPv4 one, except the 32-bit IPv4 addresses get swapped for 128-bit IPv6 addresses 💅 The one twist: to keep overhead down, router IDs stay at 32 bits, which is similar to what OSPF for IPv6 [18] does 🌷
11. IANA Considerations ✨
IANA has assigned port number 712 for TBRPF 🎀
The TBRPF flooding mechanism in this document uses the IPv4 multicast address 224.0.1.20, which IANA currently has assigned for "any private experiment" 🧚 If this specification ever gets advanced to standards track, a new multicast address assignment would be requested for this purpose 🌈
12. Security Considerations 💀
Okay, serious moment, bestie 🥺 Wireless networks are vulnerable to a whole bunch of attacks: denial-of-service attacks (like flooding and jamming), man-in-the-middle attacks (interception, insertion, deletion, modification, replaying), and service theft 😭 To counter these, it's important to prevent the spoofing (impersonation) of TBRPF nodes, and to stop unauthorized nodes from joining the network via neighbor discovery 🚨 To do that, TBRPF packets can be authenticated using the IP Authentication Header [19][20] 🔐 On top of that, the Encapsulating Security Payload (ESP) header [21] can be used to give TBRPF packets confidentiality (encryption) 🫶
The IETF SEcuring Neighbor Discovery (SEND) Working Group analyzes trust models and threats for ad hoc networks [22] 🕵️♀️ TBRPF can be extended in a straightforward manner to use SEND mechanisms, for example [23] 💜
13. Acknowledgements 🌸
The authors would like to thank the Army Systems Engineering Office (ASEO) for funding part of this work 💖
The authors would also like to thank several members of the MANET working group for many helpful comments and suggestions, including Thomas Clausen, Philippe Jacquet, and Joe Macker 🫶
The authors would like to thank Bhargav Bellur for major contributions to the original (full-topology) version of TBRPF, Ambatipudi Sastry for his support and advice, and Julie S. Wong for developing a new implementation of TBRPF and suggesting several clarifications to the TBRPF Routing Operation section 👑 Iconic credits, honestly 🦋
14. References 📚
14.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[2] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998.
[3] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981.
[4] Braden, R., Ed., "Requirements for Internet Hosts - Communication Layers", STD 3, RFC 1122, October 1989.
[5] Baker, F., Ed., "Requirements for IP Version 4 Routers", RFC 1812, June 1995.
14.2. Informative References ✨
Okay bestie, these are the extra-credit reading list, the stuff that's not strictly required but gives you the whole backstory 📚💅
[6] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[7] Ogier, R., Message in IETF email archive for MANET, ftp://ftp.ietf.org/ietf-mail-archive/manet/2002-02.mail, February 2002.
[8] Ogier, R., "Topology Dissemination Based on Reverse-Path Forwarding (TBRPF): Correctness and Simulation Evaluation", Technical Report, SRI International, October 2003.
[9] Ogier, R., Message in IETF email archive for MANET, ftp://ftp.ietf.org/ietf-mail-archive/manet/2002-03.mail, March 2002.
[10] Ogier, R., "Efficient Routing Protocols for Packet-Radio Networks Based on Tree Sharing", Proc. Sixth IEEE Intl. Workshop on Mobile Multimedia Communications (MOMUC'99), November 1999.
[11] Bellur, B. and R. Ogier, "A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks", Proc. IEEE INFOCOM '99, New York", March 1999.
[12] Clausen, T. and P. Jacquet, Eds., "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003.
[13] Bertsekas, D. and R. Gallager, "Data Networks", Prentice-Hall, 1987.
[14] Perkins, C., Belding-Royer, E. and S. Das, "IP Flooding in Ad Hoc Mobile Networks", Work in Progress, November 2001.
[15] Plummer, D., "Ethernet Address Resolution Protocol: Or converting network protocol addresses to 48.bit Ethernet address for transmission on Ethernet hardware", STD 37, RFC 826, November 1982.
[16] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery for IP Version 6 (IPv6)", RFC 2461, December 1998.
[17] Perkins, C., Ed., "IP Mobility Support for IPv4", RFC 3344, August 2002.
[18] Coltun, R., Ferguson, D. and J. Moy, "OSPF for IPv6", RFC 2740, December 1999.
[19] Kent, S. and R. Atkinson, "Security Architecture for the Internet Protocol", RFC 2401, November 1998.
[20] Kent, S. and R. Atkinson, "IP Authentication Header", RFC 2402, November 1998.
[21] Kent, S. and R. Atkinson, "IP Encapsulating Security Payload (ESP)", RFC 2406, November 1998.
[22] Nikander, P., "IPv6 Neighbor Discovery Trust Models and Threats", Work in Progress, April 2003.
[23] Arkko, J., "SEcure Neighbor Discovery (SEND)", Work in Progress, June 2003.
Authors' Addresses 🫶
Meet the squad who made this happen! 🌸
Richard G. 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
Nokia
313 Fairchild Drive
Mountain View, CA 94043
USA
Phone: +1 650 625 2331
Fax: +1 650 625 2502
EMail: ftemplin@iprg.nokia.com
Mark G. Lewis
SRI International
333 Ravenswood Ave.
Menlo Park, CA 94025
USA
Phone: +1 650 859-4302
Fax: +1 650 859-4812
EMail: lewis@erg.sri.comFull Copyright Statement ✨
The Internet Society owns the copyright here (2004) 🎀 This document is subject to the rights, licenses and restrictions in BCP 78, and apart from what that covers, the authors keep all their rights.
This document and the info in it are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 💀
Intellectual Property 🔥
Okay so the IETF is not picking a side on who owns what. It doesn't say whether any of the IP rights that might apply to the tech in this doc are valid or how wide they reach, and it doesn't say whether anyone could actually get a license for them. It also hasn't done any independent digging to find those rights. If you want the rules on rights in RFC docs, check out BCP 78 and BCP 79 📜
Any IPR disclosures sent to the IETF Secretariat, plus any promises of licenses, or the results of trying to get a general license or permission to use the proprietary rights, are on the IETF online IPR repository at http://www.ietf.org/ipr. Implementers and users can look there too 👀
The IETF also invites anyone to flag any copyrights, patents, patent applications, or other proprietary rights that might cover technology needed to implement this standard. Send that info to the IETF at ietf-ipr@ietf.org 🦋
Acknowledgement 🌈
The RFC Editor function is currently funded by the Internet Society. Thank you, Internet Society! 🫶✨
📦 where this page comes from
- ietf: rfc3684 2004-02
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms