idnits 2.17.1 draft-ietf-manet-tbrpf-11.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 2 instances of lines with control characters in the document. == There are 5 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. == There are 3 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 14, 2003) is 7471 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2460 (ref. '2') (Obsoleted by RFC 8200) -- Obsolete informational reference (is this intentional?): RFC 2461 (ref. '16') (Obsoleted by RFC 4861) -- Obsolete informational reference (is this intentional?): RFC 2002 (ref. '17') (Obsoleted by RFC 3220) -- Obsolete informational reference (is this intentional?): RFC 2740 (ref. '18') (Obsoleted by RFC 5340) -- Obsolete informational reference (is this intentional?): RFC 2401 (ref. '19') (Obsoleted by RFC 4301) -- Obsolete informational reference (is this intentional?): RFC 2402 (ref. '20') (Obsoleted by RFC 4302, RFC 4305) -- Obsolete informational reference (is this intentional?): RFC 2406 (ref. '21') (Obsoleted by RFC 4303, RFC 4305) == Outdated reference: A later version (-04) exists of draft-ietf-send-psreq-03 Summary: 3 errors (**), 0 flaws (~~), 6 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Mobile Ad-Hoc Networks Working Group R. Ogier 3 Internet-Draft SRI International 4 Expires: April 13, 2004 F. Templin 5 Nokia 6 M. Lewis 7 SRI International 8 October 14, 2003 10 Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) 11 draft-ietf-manet-tbrpf-11.txt 13 Status of this Memo 15 This document is an Internet-Draft and is in full conformance with 16 all provisions of Section 10 of RFC2026. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that other 20 groups may also distribute working documents as Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at http:// 28 www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on April 13, 2004. 35 Copyright Notice 37 Copyright (C) The Internet Society (2003). All Rights Reserved. 39 Abstract 41 TBRPF is a proactive, link-state routing protocol designed for mobile 42 ad-hoc networks, which provides hop-by-hop routing along shortest 43 paths to each destination. Each node running TBRPF computes a source 44 tree (providing paths to all reachable nodes) based on partial 45 topology information stored in its topology table, using a 46 modification of Dijkstra's algorithm. To minimize overhead, each node 47 reports only *part* of its source tree to neighbors. TBRPF uses a 48 combination of periodic and differential updates to keep all 49 neighbors informed of the reported part of its source tree. Each node 50 also has the option to report additional topology information (up to 51 the full topology), to provide improved robustness in highly mobile 52 networks. TBRPF performs neighbor discovery using "differential" 53 HELLO messages which report only *changes* in the status of 54 neighbors. This results in HELLO messages that are much smaller than 55 those of other link-state routing protocols such as OSPF. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 4 60 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . 4 61 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 62 4. Applicability Section . . . . . . . . . . . . . . . . . . 6 63 5. TBRPF Overview . . . . . . . . . . . . . . . . . . . . . . 6 64 5.1 Overview of Neighbor Discovery . . . . . . . . . . . . . . 7 65 5.2 Overview of the Routing Module . . . . . . . . . . . . . . 9 66 6. TBRPF Packets . . . . . . . . . . . . . . . . . . . . . . 11 67 6.1 TBRPF Packet Header . . . . . . . . . . . . . . . . . . . 11 68 6.2 TBRPF Packet Body . . . . . . . . . . . . . . . . . . . . 12 69 6.2.1 Padding Options (TYPE = 0 thru 1) . . . . . . . . . . . . 13 70 6.2.2 Messages (TYPE = 2 thru 10) . . . . . . . . . . . . . . . 13 71 7. TBRPF Neighbor Discovery . . . . . . . . . . . . . . . . . 13 72 7.1 HELLO Message Format . . . . . . . . . . . . . . . . . . . 14 73 7.2 Neighbor Table . . . . . . . . . . . . . . . . . . . . . . 15 74 7.3 Sending HELLO Messages . . . . . . . . . . . . . . . . . . 16 75 7.4 Processing a Received HELLO Message . . . . . . . . . . . 17 76 7.5 Expiration of Timer nbr_life . . . . . . . . . . . . . . . 18 77 7.6 Link-Layer Failure Notification . . . . . . . . . . . . . 18 78 7.7 Optional Link Metrics . . . . . . . . . . . . . . . . . . 19 79 7.8 Configurable Parameters . . . . . . . . . . . . . . . . . 19 80 8. TBRPF Routing Module . . . . . . . . . . . . . . . . . . . 20 81 8.1 Conceptual Data Structures . . . . . . . . . . . . . . . . 20 82 8.2 TOPOLOGY UPDATE Message Format . . . . . . . . . . . . . . 22 83 8.3 Interface, Host, and Network Prefix Association Message 84 Formats . . . . . . . . . . . . . . . . . . . . . . . . . 23 85 8.4 TBRPF Routing Operation . . . . . . . . . . . . . . . . . 24 86 8.4.1 Periodic Processing . . . . . . . . . . . . . . . . . . . 25 87 8.4.2 Updating the Source Tree and Topology Graph . . . . . . . 25 88 8.4.3 Updating the Routing Table . . . . . . . . . . . . . . . . 27 89 8.4.4 Updating the Reported Node Set . . . . . . . . . . . . . . 28 90 8.4.5 Generating Periodic Updates . . . . . . . . . . . . . . . 29 91 8.4.6 Generating Differential Updates . . . . . . . . . . . . . 30 92 8.4.7 Processing Topology Updates . . . . . . . . . . . . . . . 31 93 8.4.8 Expiring Topology Information . . . . . . . . . . . . . . 32 94 8.4.9 Optional Reporting of Redundant Topology Information . . . 33 95 8.4.10 Local Topology Changes . . . . . . . . . . . . . . . . . . 33 96 8.4.11 Generating Association Messages . . . . . . . . . . . . . 35 97 8.4.12 Processing Association Messages . . . . . . . . . . . . . 36 98 8.4.13 Non-Relay Operation . . . . . . . . . . . . . . . . . . . 38 99 8.5 Configurable Parameters . . . . . . . . . . . . . . . . . 38 100 9. TBRPF Flooding Mechanism . . . . . . . . . . . . . . . . . 38 101 10. Operation of TBRPF in Mobile Ad-Hoc Networks . . . . . . . 39 102 10.1 Data Link Layer Assumptions . . . . . . . . . . . . . . . 40 103 10.2 Network Layer Assumptions . . . . . . . . . . . . . . . . 40 104 10.3 Optional Automatic Address Resolution . . . . . . . . . . 40 105 10.4 Support for Multiple Interfaces and/or Alias Addresses . . 40 106 10.5 Support for Network Prefixes . . . . . . . . . . . . . . . 41 107 10.6 Support for non-MANET Hosts . . . . . . . . . . . . . . . 41 108 10.7 Internet Protocol Considerations . . . . . . . . . . . . . 41 109 10.7.1 IPv4 Operation . . . . . . . . . . . . . . . . . . . . . . 41 110 10.7.2 IPv6 Operation . . . . . . . . . . . . . . . . . . . . . . 42 111 11. IANA Considerations . . . . . . . . . . . . . . . . . . . 42 112 12. Security Considerations . . . . . . . . . . . . . . . . . 42 113 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . 42 114 Normative References . . . . . . . . . . . . . . . . . . . 43 115 Informative References . . . . . . . . . . . . . . . . . . 43 116 Authors' Addresses . . . . . . . . . . . . . . . . . . . . 44 117 A. Major Changes . . . . . . . . . . . . . . . . . . . . . . 45 118 Intellectual Property and Copyright Statements . . . . . . 46 120 1. Introduction 122 TBRPF is a proactive, link-state routing protocol designed for mobile 123 ad-hoc networks (MANETs), which provides hop-by-hop routing along 124 shortest paths to each destination. Each node running TBRPF computes 125 a source tree (providing shortest paths to all reachable nodes) based 126 on partial topology information stored in its topology table, using a 127 modification of Dijkstra's algorithm. To minimize overhead, each node 128 reports only *part* of its source tree to neighbors. 130 TBRPF uses a combination of periodic and differential updates to keep 131 all neighbors informed of the reported part of its source tree. Each 132 node also has the option to report addition topology information (up 133 to the full topology), to provide improved robustness in highly 134 mobile networks. 136 TBRPF performs neighbor discovery using "differential" HELLO messages 137 which report only *changes* in the status of neighbors. This results 138 in HELLO messages that are much smaller than those of other 139 link-state routing protocols such as OSPF [6]. 141 TBRPF consists of two modules: the neighbor discovery module and the 142 routing module (which performs topology discovery and route 143 computation). An overview of these modules is given in Section 5. 145 2. Requirements 147 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 148 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL", when 149 they appear in this document, are to be interpreted as described in 150 RFC2119 [1]. 152 This document also makes use of internal conceptual variables to 153 describe protocol behavior and external variables that an 154 implementation must allow system administrators to change. The 155 specific variable names, how their values change, and how their 156 settings influence protocol behavior are provided to demonstrate 157 protocol behavior. An implementation is not required to have them in 158 the exact form described here, so long as its external behavior is 159 consistent with that described in this document. 161 3. Terminology 163 The following terms are used to describe TBRPF: 165 node 166 A router that implements TBRPF. 168 router ID 169 Each node is identified by a unique 32-bit router ID (RID), which 170 for IPv4 is typically equal to the IP address of one of its 171 interfaces. The term "node u" denotes the node whose RID is equal 172 to u. 174 interface 175 A node's attachment to a communication facility or medium through 176 which it can communicate with other nodes. A node can have 177 multiple interfaces. An interface can be wireless or wired, and 178 can be broadcast (e.g., Ethernet) or point-to-point. Each 179 interface is identified by its IP address. The term "interface I" 180 denotes the interface whose IP address is I. 182 link 183 A link is an ordered pair of interfaces (I,J) where I and J are on 184 two different nodes, and where interface I has recently received 185 packets sent from interface J. A link (i,j) from node i to node j 186 is said to exist if node i has an interface I and node j has an 187 interface J such that (I,J) is a link. Nodes i and j are called 188 the "tail" and "head" of the link, respectively. 190 bidirectional link 191 A link (I,J) such that interfaces I and J can both hear each 192 other. Also called a 2-way link. 194 neighbor node 195 A node j is said to be a neighbor of node i if node i can hear 196 node j on some interface. Node j is said to be a 2-way neighbor if 197 there is a bidirectional link between i and j. 199 MANET interface 200 Any wireless interface such that two neighbor nodes on the 201 interface need not be neighbors of each other. MANET nodes 202 typically have at least one MANET interface, but this is not a 203 requirement. 205 topology 206 The topology of the network is described by a graph G = (V, E), 207 where V is the set of nodes u and E is the set of links (u,v) in 208 the network. 210 source tree 211 The directed tree (denoted T) computed by each node that provides 212 shortest paths to all other reachable nodes. 214 topology update 215 A message that reports the state of one or more links. 217 parent 218 The parent of node i for node u is the next node on the computed 219 shortest path from node i to node u. 221 predecessor 222 The predecessor of a node v on the source tree is the node u such 223 that the link (u,v) is in the source tree. 225 leaf node 226 A leaf node of the source tree is a node on the source tree that 227 is not the predecessor of any other node on the source tree. 229 proactive routing protocol 230 A routing protocol in which each node maintains routes to all 231 reachable destinations at all times, whether or not there is 232 currently any need to deliver packets to those destinations. In 233 contrast, an "on-demand" routing protocol discovers and maintains 234 routes only when they are needed. 236 4. Applicability Section 238 TBRPF is a proactive routing protocol designed for mobile ad-hoc 239 networks (MANETs). It can support networks with up to a few hundred 240 nodes, and can be combined with hierarchical routing techniques to 241 support much larger networks. Because it employs techniques to 242 greatly reduce control traffic, TBRPF can support much larger and 243 denser networks than routing protocols based on the classical 244 link-state algorithm (e.g., OSPF). 246 The number of nodes that can be supported depends on several factors, 247 including the MAC data rate, the rate of topology changes, and the 248 network density (average number of neighbors). Simulations have been 249 reported in which TBRPF has supported as many as 500 nodes. In 250 simulations with 100 nodes and 20 traffic streams (sources), using 251 IEEE 802.11 with a data rate of 2 Mbps, TBRPF was found to generate 252 approximately 80-120 kb/s of routing control traffic for the 253 scenarios considered, which compared favorably with other MANET 254 routing protocols [7][8]. A proof of correctness for TBRPF can be 255 found in references [8] and [9]. 257 5. TBRPF Overview 259 TBRPF consists of two main modules: the neighbor discovery module, 260 and the routing module (which performs topology discovery and route 261 computation). 263 5.1 Overview of Neighbor Discovery 265 The TBRPF Neighbor Discovery (TND) protocol allows each node i to 266 quickly detect the neighbor nodes j such that a bidirectional link 267 (I,J) exists between an interface I of node i and an interface J of 268 node j. The protocol also quickly detects when a bidirectional link 269 breaks or becomes unidirectional. 271 The key feature of TND is that it uses "differential" HELLO messages 272 which report only *changes* in the status of links. This results in 273 HELLO messages that are much smaller than those of other link-state 274 routing protocols such as OSPF, in which each HELLO message includes 275 the IDs of *all* neighbors. As a result, HELLO messages can be sent 276 more frequently, which allows faster detection of topology changes. 278 TND is designed to be fully modular and independent of the routing 279 module. TND performs ONLY neighbor sensing, i.e., it determines which 280 nodes are (1-hop) neighbors. In particular, it does not discover 281 2-hop neighbors (which is handled by the routing module). As a 282 result, TND can be used by other routing protocols, and TBRPF can use 283 another neighbor discovery protocol in place of TND, e.g., one 284 provided by the link layer. 286 Nodes with multiple interfaces run TND separately on each interface, 287 similar to OSPF. Thus, a neighbor table is maintained for each local 288 interface, and a HELLO sent on a particular interface contains only 289 information regarding neighbors heard on that interface. 291 We note that, in wireless networks, it is possible for a single 292 interface I to receive packets from multiple interfaces J associated 293 with the same neighbor node. This could happen, for example, if the 294 neighbor uses a directional antenna with different interfaces 295 representing different beams. For this reason, TBRPF includes 296 neighbor interface addresses in HELLO messages, unlike OSPF, which 297 includes only router IDs in HELLO packets. 299 Each TBRPF node maintains a neighbor table for each local interface 300 I, which stores state information for each neighbor interface J heard 301 on that interface, i.e., for each link (I,J) between interface I and 302 a neighbor interface J. The status of each link can be 1-WAY, 2-WAY, 303 or LOST. The neighbor table for interface I determines the contents 304 of HELLO messages sent on interface I, and is updated based on HELLO 305 messages received on interface I (and possibly on link-layer 306 notifications). 308 Each TBRPF node must send (on each interface) at least one HELLO 309 message per HELLO_INTERVAL. Each HELLO message contains three 310 (possibly empty) lists of neighbor interface addresses (which are 311 formatted as three message subtypes): NEIGHBOR REQUEST, NEIGHBOR 312 REPLY, and NEIGHBOR LOST. Each HELLO message also contains the 313 current HELLO sequence number (HSEQ), which is incremented with each 314 transmitted HELLO. 316 In the following overview of the operation of TND, we assume that 317 interface I belongs to node i, and interface J belongs to node j. 318 When a node i changes the status of a link (I,J), it includes the 319 neighbor interface address J in the appropriate list (NEIGHBOR 320 REQUEST/REPLY/LOST) in at most NBR_HOLD_COUNT (typically 3) 321 consecutive HELLOs sent on interface I. This ensures that node j will 322 either receive one of these HELLOs on interface J, or will miss 323 NBR_HOLD_COUNT HELLOs and thus declare the link (J,I) to be LOST. 324 This technique makes it unnecessary for a node to include each 1-WAY 325 or 2-WAY neighbor in HELLOs indefinitely, unlike OSPF. 327 To avoid establishing a link that is likely to be short lived (i.e., 328 to employ hysteresis), node i must receive (on interface I) at least 329 HELLO_ACQUIRE_COUNT (e.g., 2) of the last HELLO_ACQUIRE_WINDOW (e.g., 330 3) HELLOs sent from a neighbor interface J, before declaring the link 331 (I,J) to be 1-WAY. When this happens, node i includes J in the 332 NEIGHBOR REQUEST list in each of its next NBR_HOLD_COUNT HELLO 333 messages sent on interface I, or until a NEIGHBOR REPLY message 334 containing I is received on interface I from neighbor interface J. 336 If node j receives (on interface J) one of the HELLOs sent from 337 interface I that contains J in the NEIGHBOR REQUEST list, then node j 338 declares the link (J,I) to be 2-WAY (unless it is already 2-WAY), and 339 includes I in the NEIGHBOR REPLY list in each of its next 340 NBR_HOLD_COUNT HELLO messages sent on interface J. Upon receiving one 341 of these HELLOs on interface I, node i declares the link (I,J) to be 342 2-WAY. 344 If node i receives a HELLO on interface I, sent from neighbor 345 interface J, whose HSEQ indicates that at least NBR_HOLD_COUNT HELLOs 346 were missed, or if node i receives no HELLO on interface I sent from 347 interface J within NBR_HOLD_TIME seconds, then node i changes the 348 status of link (I,J) to LOST (unless it is already LOST), and 349 includes J in the NEIGHBOR LOST list in each of its next 350 NBR_HOLD_COUNT HELLO messages sent on interface I (unless the link 351 changes status before these transmissions are complete). Node j will 352 either receive one of these HELLOs on interface J or will miss 353 NBR_HOLD_COUNT HELLOs; in either case, node j will declare the link 354 (J,I) to be LOST. In this manner, both nodes will agree that the link 355 between I and J is no longer bidirectional, even if node j can still 356 hear HELLOs from node i. 358 Each node may maintain and update one or more link metrics for each 359 link (I,J) from a local interface I to a neighbor interface J, 360 representing the quality of the link. Such link metrics can be used 361 as additional conditions for changing the status of a neighbor, based 362 on the link metric going above or below some threshold. TBRPF also 363 allows link metrics to be advertised in topology updates, and to be 364 used for computing shortest paths. 366 5.2 Overview of the Routing Module 368 Each node running TBRPF maintains a source tree, denoted T, which 369 provides shortest paths to all reachable nodes. Each node computes 370 and updates its source tree based on partial topology information 371 stored in its topology table, using a modification of Dijkstra's 372 algorithm. To minimize overhead, each node reports only part of its 373 source tree to neighbors. The main idea behind the current version of 374 TBRPF came from PTSP [10], another protocol in which each node 375 reports only part of its source tree. (However, TBRPF differs from 376 PTSP in several ways.) The current version of TBRPF should not be 377 confused with its previous version [11], which is a full-topology 378 routing protocol. 380 The part of T that a node reports to neighbors is called the 381 "reported subtree" and is denoted RT. Each node reports RT to 382 neighbors in *periodic* topology updates (e.g., every 5 seconds), and 383 reports changes (additions and deletions) to RT in more frequent 384 *differential* updates (e.g., every 1 second). Periodic updates 385 inform new neighbors of RT, and ensure that each neighbor eventually 386 learns RT even if it does not receive all updates. Differential 387 updates ensure the fast propagation of each topology update to all 388 nodes that are affected by the update. A received topology update is 389 not forwarded, but *may* result in a change to RT, which will be 390 reported in the next differential or periodic update. Whenever 391 possible, topology updates are included in the same packet as a HELLO 392 message, to minimize the number of control packets sent. TBRPF does 393 not require reliable or sequenced delivery of messages, and does not 394 use ACKs or NACKs. 396 TBRPF supports multiple interfaces, associated hosts, and network 397 prefixes. Information regarding associated interfaces, hosts, and 398 prefixes is disseminated efficiently in periodic and differential 399 updates, similar to the dissemination of topology updates. 401 The reported subtree RT consists of links (u,v) of T such that u is 402 in the "reported node set" RN, which is computed as follows. Node i 403 includes a neighbor j in RN if and only if node i determines that one 404 of its neighbors may select i to be its next hop on its shortest path 405 to j. To make this determination, node i computes the shortest paths, 406 up to 2 hops, from each neighbor to each other neighbor, using only 407 neighbors (or node i itself) as an intermediate node, and using relay 408 priority (included in HELLO messages) and router ID to break ties. 409 After a node determines which neighbors are in RN, each reachable 410 node u is included in RN if and only if the next hop on the shortest 411 path to u is in RN. A node also includes itself in RN. As a result, 412 the reported subtree RT includes the subtrees of T that are rooted at 413 neighbors in RN, and also includes all local links to neighbors. 415 We note that neighbors in RN are analogous to multipoint relay (MPR) 416 selectors [12]. Thus, if node i selects neighbor j to be in RN, then 417 node i effectively selects itself to be an MPR of node j. This is 418 quite different from [12], in which a node does not select itself to 419 be an MPR, but selects a subset of its neighbors to be MPRs. 421 A node with a larger relay priority reports a larger part of its 422 source tree (on average), and is more likely to be selected as a 423 next-hop relay by its neighbors. A node with relay priority equal to 424 0 is called a non-relay node, and never forwards packets originating 425 from other nodes. 427 TBRPF does not use sequence numbers for topology updates, thus 428 reducing message overhead and avoiding wraparound problems. Instead, 429 a technique similar to SPTA [13] is used in which, for each link 430 (u,v) reported by one or more neighbors, only the next hop p(u) to u 431 is believed regarding the state of the link. (However, in SPTA each 432 node reports the full topology.) Using this technique, each node 433 maintains a topology graph TG, consisting of links that are believed 434 to be up, and computes T as the shortest-path tree within TG. To 435 allow immediate rerouting, the restriction that each link (u,v) in TG 436 must be reported by p(u) is relaxed temporarily if p(u) changes to a 437 neighbor that is not reporting the link. 439 Each node is required to report RT, but may report additional links, 440 e.g., to provide increased robustness in highly mobile networks. More 441 precisely, a node may maintain any subgraph H of TG that contains T, 442 and report the reported subgraph RH, which consists of links (u,v) of 443 H such that u is in RN. For example, H can equal TG, which would 444 provide each node with the full network topology if this is done by 445 all nodes. H can also be a biconnected subgraph that contains T, 446 which would provide each node with two disjoint paths to each other 447 node, if this is done by all nodes. 449 TBRPF allows the option to include link metrics in topology updates, 450 and to compute paths that are shortest with respect to the metric. 451 This allows packets to be sent along paths that are higher quality 452 than minimum-hop paths. 454 TBRPF allows path optimality to be traded off in order to reduce the 455 amount of control traffic in networks with a large diameter, where 456 the degree of approximation is determined by the configurable 457 parameter NON_TREE_PENALTY. 459 6. TBRPF Packets 461 Nodes send TBRPF protocol data in contiguous units known as 462 *packets*. Each packet includes a header, optional header extensions, 463 and a body comprising one or more *messages* and padding options as 464 needed. To facilitate efficient receiver processing, senders SHOULD 465 insert padding options as necessary to align multi-octet words within 466 the TBRPF packet on "natural" boundaries (i.e. modulo-8/4/2 addresses 467 for 64/32/16-bit words, respectively). Receivers MUST be capable of 468 processing multi-octet words whether or not aligned on natural 469 boundaries. The following sections specify elements of the TBRPF 470 packet in more detail. 472 6.1 TBRPF Packet Header 474 TBRPF packet headers are variable-length (minimum one octet). The 475 format for the packet header is as follows: 477 0 1 2 3 478 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 479 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 480 | Vers |L|I|R|R| Reserved | Header Extensions ... 481 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 483 Version (4 bits): 484 The TBRPF version number. This specification documents version 4 485 of the protocol. 487 Flags (4 bits): 488 Two bits (L,I) specify which header extensions (if any) follow. 489 Two bits (R) are reserved for future use, and MUST be zero. Any 490 extensions specified by these bits MUST appear in the same order 491 as the bits (i.e. first L, then I) as follows: 493 L - Length included: 494 If the underlying delivery service provides a length field, the 495 sender MAY set L = '0' and omit the length extension. 496 Otherwise, the sender MUST set L = '1' and include a 16-bit 497 unsigned integer length immediately after any previous header 498 field. The length includes all header and data bytes and is 499 written into the length field in network byte order. 501 Receivers examine the L bit to determine whether the length 502 field is present. If L = '1', the receiver converts the length 503 to host byte order to determine the length of the TBRPF packet, 504 including the TBRPF packet header. Receivers discard any TBRPF 505 packet if neither the underlying delivery service nor the TBRPF 506 packet header provide packet length. 508 I - Router ID (RID) included: 509 If the underlying delivery service encodes the sender's RID, 510 the sender MAY set I = '0' and omit the RID field. Otherwise, 511 the sender MUST set I = '1' and include a 32-bit unsigned 512 integer RID immediately after any previous header fields. The 513 RID option provides a mechanism for implicit network-level 514 address resolution. A receiver that detects a RID option SHOULD 515 create a binding between the RID and the source address that 516 appears in the network-level header. 518 Reserved: 519 Reserved for future use; MUST be zero. 521 6.2 TBRPF Packet Body 523 The TBRPF packet body consists of the concatenation of one or more 524 TBRPF messages (and padding options where necessary). Messages and 525 padding options within the TBRPF packet body are encoded using the 526 following format: 528 +-+-+-+-+-+-+-+-+- - - - - 529 |OPTIONS| TYPE | VALUE 530 +-+-+-+-+-+-+-+-+- - - - - 532 TYPE (4 bits): 533 A 4-bit identifier with value 0 - 15 that identifies the element. 535 VALUE 536 Variable-length field. (Format and length depend on TYPE, as 537 described in the following sections.) 539 OPTIONS 540 Four option bits that depend on TYPE. 542 The sequence of elements MUST be processed strictly in the order they 543 appear within the TBRPF packet body; a receiver must not, for 544 example, scan through the packet body looking for a particular type 545 of element prior to processing all preceding elements [2]. TBRPF 546 packet elements include *padding options* and *messages* as described 547 below. 549 6.2.1 Padding Options (TYPE = 0 thru 1) 551 Senders MAY insert two types of padding options where necessary, 552 e.g., to satisfy alignment requirements for other elements [2]. 553 Padding options may occur anywhere within the TBRPF packet body. The 554 following two padding options are defined: 556 Pad1 option (TYPE = 0) 558 +-+-+-+-+-+-+-+-+ 559 | 0 | 0 | 560 +-+-+-+-+-+-+-+-+ 562 The Pad1 option inserts one octet of padding into the TBRPF packet 563 body; the VALUE field is omitted. If more than one octet of padding 564 is required, the PadN option (described next) should be used, rather 565 than multiple Pad1 options. 567 PadN option (TYPE = 1) 569 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - 570 | 0 | 1 | LEN | Zero-valued Octets 571 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - - 573 The PadN option inserts two or more octets of padding into the TBRPF 574 packet body. The first octet of the VALUE field contains an 8-bit 575 unsigned integer length containing a value between 0 - 253 which 576 specifies the number of zero-valued octets that immediately follow, 577 yielding a maximum total of 255 padding octets. 579 6.2.2 Messages (TYPE = 2 thru 10) 581 Additional message types are described as they occur in the following 582 sections. Senders encode messages as specified by the individual 583 message formats. Receivers detect errors in message construction, 584 e.g., messages with unrecognized types, messages with a non-integral 585 number of elements or with fewer elements than indicated, etc. In all 586 cases, upon detecting an error the receiver MUST discontinue 587 processing the current TBRPF packet and discard any unprocessed 588 elements. 590 7. TBRPF Neighbor Discovery 592 This section describes the TBRPF Neighbor Discovery (TND) protocol, 593 which allows each node to quickly detect bidirectional links (I,J) 594 between a local interface I and a neighbor interface J, and to 595 quickly detect the loss of such links. The interface between TND and 596 the routing module is defined by the neighbor table maintained by TND 597 and the three procedures Link_Up(I,J), Link_Down(I,J), and 598 Link_Change(I,J), which are called by TND to announce a new link, the 599 loss of a link, and a change in the metric of a link, respectively. 601 7.1 HELLO Message Format 603 The HELLO message has the following three subtypes: 605 - NEIGHBOR REQUEST (TYPE = 2) 606 - NEIGHBOR REPLY (TYPE = 3) 607 - NEIGHBOR LOST (TYPE = 4) 609 Each HELLO subtype has the following format: 611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 | 0 | TYPE | HSEQ | Pri | n | 613 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 614 | Neighbor Interface Address (1) | 615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 616 | Neighbor Interface Address (2) | 617 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 618 ~ ... ~ 619 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 620 | Neighbor Interface Address (n) | 621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 623 HSEQ (8 bits) 624 The HELLO sequence number. 626 Pri (4 bits) 627 This field indicates the sending node's relay priority, which is 628 an integer between 0 and 15. A node with a higher relay priority 629 is more likely to be selected as the next hop on a route. The 630 value 0 is reserved for non-relay nodes, i.e., nodes that should 631 never forward packets originating from other nodes. A router in 632 normal operation SHOULD have a relay priority equal to 7. A router 633 can change its relay priority dynamically, e.g., when its power 634 supply becomes critical. 636 n (12 bits) 637 The number of 32-bit neighbor interface addresses in the message. 639 A HELLO message is the concatenation of a NEIGHBOR REQUEST message, a 640 NEIGHBOR REPLY message, and a NEIGHBOR LOST message, where each of 641 the last two messages is omitted if its list of neighbor interface 642 addresses is empty. Thus, a HELLO message always includes a (possibly 643 empty) NEIGHBOR REQUEST. 645 7.2 Neighbor Table 647 Each node maintains, for each of its local interfaces I, a neighbor 648 table, which stores state information for each neighbor interface J 649 from which HELLO messages have recently been received by interface I. 650 The entry for neighbor interface J, in the neighbor table for I, 651 contains the following variables: 653 nbr_rid(I,J) - The router ID of the node associated with neighbor 654 interface J. 656 nbr_status(I,J) - The current status of the link (I,J), which can 657 be LOST, 1-WAY, or 2-WAY. 659 nbr_life(I,J) - The amount of time (in seconds) remaining before 660 nbr_status(I,J) must be changed to LOST if no further HELLO 661 message from interface J is received. Set to NBR_HOLD_TIME 662 whenever a HELLO is received on interface I from interface J. 664 nbr_hseq(I,J) - The value of HSEQ in the last HELLO message 665 received on interface I from interface J. Used to determine the 666 number of HELLOs that have been missed. 668 nbr_count(I,J) - The remaining number of times a NEIGHBOR REQUEST/ 669 REPLY/LOST message containing J must be sent on interface I. 671 hello_history(I,J) - A list of the sequence numbers of the last 672 HELLO_ACQUIRE_WINDOW HELLO messages received on interface I from 673 interface J. 675 nbr_metric(I,J) - An optional measure of the quality of the link 676 (I,J), represented by an integer between 1 and 255, where smaller 677 values indicate better quality. Defaults to 1 if not used. 679 nbr_pri(I,J) - The relay priority of the node associated with 680 interface J. 682 The entry for interface J in the neighbor table for interface I may 683 be deleted if no HELLO has been received on interface I from 684 interface J within the last 2*NBR_HOLD_TIME seconds. (It is kept 685 while NEIGHBOR LOST messages containing J are being transmitted.) The 686 absence of an entry for a given interface J is equivalent to an entry 687 with nbr_status(I,J) = LOST and hello_history(I,J) = NULL. 689 The three possible values of nbr_status(I,J) have the following 690 informal meanings (the exact meanings are defined by the protocol): 692 LOST 693 Interface I has not received a sufficient number of HELLO messages 694 recently from Interface J. 696 1-WAY 697 Interface I has received a sufficient number of HELLO messages 698 recently from Interface J, but the link is not 2-WAY. 700 2-WAY 701 Interfaces I and J have both received a sufficient number of HELLO 702 messages recently from each other. 704 7.3 Sending HELLO Messages 706 Each node MUST send, on each local interface, at least one HELLO 707 message per HELLO_INTERVAL. HELLO messages MAY be sent more 708 frequently than this (e.g., for faster detection of topology 709 changes). However, to avoid the possibility that HSEQ wraps around to 710 the same number before a neighbor that stops receiving HELLO messages 711 changes the status of the link to LOST, the time between two 712 consecutive HELLO messages (sent on a given interface) MUST be 713 greater than NBR_HOLD_TIME/128 second. 715 To avoid synchronization of control messages, which can result in 716 collisions, HELLO messages SHOULD NOT be transmitted at equal 717 intervals. To achieve this, a node MAY choose the interval between 718 consecutive HELLO messages to be HELLO_INTERVAL - jitter, where 719 jitter is selected randomly from the interval [0, MAX_JITTER]. 721 Each HELLO message always includes a NEIGHBOR REQUEST message, even 722 if its list of neighbor addresses is empty. The NEIGHBOR REQUEST 723 message includes the sequence number HSEQ, which is incremented by 1 724 (modulo 256) each time a HELLO is sent. The HELLO message also 725 includes a NEIGHBOR REPLY message if its list of neighbor addresses 726 is nonempty, and a NEIGHBOR LOST message if its list of neighbor 727 addresses is nonempty. The contents of these three messages are 728 determined by the following steps at node i for each interface I: 730 1. For each interface J such that nbr_status(I,J) = LOST and 731 nbr_count(I,J) > 0, include J in the NEIGHBOR LOST message and 732 decrement nbr_count(I,J). 734 2. For each interface J such that nbr_status(I,J) = 1-WAY and 735 nbr_count(I,J) > 0, include J in the NEIGHBOR REQUEST message and 736 decrement nbr_count(I,J). 738 3. For each interface J such that nbr_status(I,J) = 2-WAY and 739 nbr_count(I,J) > 0, include J in the NEIGHBOR REPLY message and 740 decrement nbr_count(I,J). 742 If a node restarts, so that all entries are removed from the neighbor 743 table, then the node MUST ensure that (for each interface) at least 744 one of the following two conditions is satisfied: 746 1. The difference between the transmission times of the first 747 HELLO sent after restarting and the last HELLO sent before 748 restarting is at least 2*NBR_HOLD_TIME. 750 2. Letting HSEQ_LAST denote the sequence number of the last HELLO 751 that was sent before restarting, the sequence number of the 752 first HELLO sent after restarting is set to HSEQ_LAST + 753 NBR_HOLD_COUNT + 1 (modulo 256). 755 Either of these conditions ensures that, if node i with interface I 756 restarts, then each neighbor of node i that has a link (J,I) to 757 interface I will set the status of the link to LOST. 759 7.4 Processing a Received HELLO Message 761 When a node receives a HELLO message, it obtains the IP address of 762 the sending interface from the IP header. If the TBRPF packet header 763 of the received HELLO contains the RID option, then the RID of the 764 sending node is obtained from the TBRPF packet header; otherwise it 765 is equal to the IP address of the sending interface. If node i (with 766 RID equal to i) receives a HELLO message on interface I, sent by node 767 j (with RID equal to j) on interface J, with sequence number HSEQ and 768 relay priority PRI, then node i performs the following steps: 770 1. If the neighbor table for interface I does not contain an 771 entry for interface J, create one with nbr_rid(I,J) = j, 772 nbr_status(I,J) = LOST (temporarily), nbr_count(I,J) = 0, 773 and nbr_hseq(I,J) = HSEQ. 775 2. Update hello_history(I,J) to reflect the received HELLO message. 776 If nbr_hseq(I,J) > HSEQ (due to wraparound), set nbr_hseq(I,J) = 777 nbr_hseq(I,J) - 256. 779 3. If nbr_status(I,J) = LOST and hello_history(I,J) indicates that 780 HELLO_ACQUIRE_COUNT of the last HELLO_ACQUIRE_WINDOW HELLO 781 messages from interface J have been received: 783 a. If interface I does not appear in the NEIGHBOR REQUEST list 784 or the NEIGHBOR REPLY list, set nbr_status(I,J) = 1-WAY and 785 nbr_count(I,J) = NBR_HOLD_COUNT. 787 b. Else, set nbr_status(I,J) = 2-WAY and nbr_count(I,J) = 788 NBR_HOLD_COUNT. Call Link_Up(I,J). 790 4. Else, if nbr_status(I,J) = 1-WAY: 792 a. If HSEQ - nbr_hseq(I,J) > NBR_HOLD_COUNT, then set 793 nbr_status(I,J) = LOST and nbr_count(I,J) = NBR_HOLD_COUNT. 795 b. Else, if interface I appears in the NEIGHBOR REQUEST list, 796 set nbr_status(I,J) = 2-WAY and nbr_count(I,J) = 797 NBR_HOLD_COUNT. Call Link_Up(I,J). 799 c. Else, if interface I appears in the NEIGHBOR REPLY list, 800 set nbr_status(I,J) = 2-WAY and nbr_count(I,J) = 0. 801 Call Link_Up(I,J). 803 5. Else, if nbr_status(I,J) = 2-WAY: 805 a. If interface I appears in the NEIGHBOR LOST list, set 806 nbr_status(I,J) = LOST and nbr_count(I,J) = 0. Call 807 Link_Down(I,J). 809 b. Else, if HSEQ - nbr_hseq(I,J) > NBR_HOLD_COUNT, set 810 nbr_status(I,J) = LOST and nbr_count(I,J) = NBR_HOLD_COUNT. 811 Call Link_Down(I,J). 813 c. Else, if interface I appears in the NEIGHBOR REQUEST list 814 and nbr_count(I,J) = 0, set nbr_count(I,J) = NBR_HOLD_COUNT. 816 6. Set nbr_life(I,J) = NBR_HOLD_TIME, nbr_hseq(I,J) = HSEQ, and 817 nbr_pri(I,J) = PRI. 819 7.5 Expiration of Timer nbr_life 821 Upon expiration of the timer nbr_life(I,J) in the neighbor table for 822 interface I, node i performs the following step: 824 If nbr_status(I,J) = 1-WAY or 2-WAY, set nbr_status(I,J) = LOST 825 and nbr_count(I,J) = NBR_HOLD_COUNT. Call Link_Down(I,J). 827 7.6 Link-Layer Failure Notification 829 Some link-layer protocols (e.g., IEEE 802.11) provide a notification 830 that the link to a particular neighbor has failed, e.g., after 831 attempting a maximum number of retransmissions. If such an 832 notification is provided by the link layer, then node i SHOULD 833 perform the following step upon receipt of a link-layer failure 834 notification for the link (I,J) from local interface I to neighbor 835 interface J: 837 If nbr_status(I,J) = 2-WAY, set nbr_status(I,J) = LOST and 838 nbr_count(I,J) = NBR_HOLD_COUNT. Call Link_Down(I,J). 840 7.7 Optional Link Metrics 842 Each node MAY maintain and update one or more link metrics for each 843 link (I,J), representing the quality of the link, e.g., signal 844 strength, number of HELLOs received over some time interval, 845 reliability, stability, bandwidth, etc. Each node MUST declare a 846 neighbor to be LOST if either NBR_HOLD_COUNT HELLOs are missed or if 847 no HELLO is received within NBR_HOLD_TIME seconds; however, a node 848 MAY also declare a neighbor to be LOST based on a link metric being 849 above or below some threshold. Each node MUST receive at least 850 HELLO_ACQUIRE_COUNT of the last HELLO_ACQUIRE_WINDOW HELLOs from a 851 neighbor before declaring the neighbor 1-WAY or 2-WAY; however, a 852 node MAY require an additional condition based on a link metric being 853 above or below some threshold, before declaring the neighbor 1-WAY or 854 2-WAY. This document does not specify any particular link metric, but 855 an implementation of TBRPF that uses such metrics is considered to be 856 compliant with this specification. 858 The function Link_Change(I,J) is called to alert the routing module 859 whenever nbr_metric(I,J) changes significantly. If the configurable 860 parameter USE_METRICS is equal to 1, then the metrics nbr_metric(I,J) 861 are used by the routing module for route computation, as described in 862 Section 8. 864 7.8 Configurable Parameters 866 This section lists the parameters used by the neighbor discovery 867 protocol, and their proposed default values. All nodes MUST be 868 configured to have the same value for all of the following 869 parameters. 871 Parameter Name Default Value 872 -------------- ------------- 873 HELLO_INTERVAL 1 second 874 MAX_JITTER 0.1 second 875 NBR_HOLD_TIME 3 seconds 876 NBR_HOLD_COUNT 3 877 HELLO_ACQUIRE_COUNT 2 878 HELLO_ACQUIRE_WINDOW 3 880 8. TBRPF Routing Module 882 This section describes the TBRPF routing module, which performs 883 topology discovery and route computation. 885 8.1 Conceptual Data Structures 887 In addition to the information required by the neighbor discovery 888 protocol, each node running TBRPF maintains a topology table TT, 889 which stores information for each known node and link in the network. 890 Nodes are identified by their RIDs, i.e., node u is the node whose 891 RID is u. The following information is stored in the topology table 892 at node i for each node u and link (u,v): 894 T(u,v) - Equal to 1 if (u,v) is in node i's source tree T, and 0 895 otherwise. The previous source tree is also maintained as old_T. 897 RN(u) - Equal to 1 if u is in node i's reported node set RN, and 0 898 otherwise. The previous reported node set is also maintained as 899 old_RN. 901 RT(u,v) - Equal to 1 if (u,v) is in node i's reported subtree RT, 902 and 0 otherwise. Since RT is defined as the set of links (u,v) in 903 T such that u is in RN, this variable need not be maintained 904 explicitly. 906 TG(u,v) - Equal to 1 if (u,v) is in node i's topology graph TG, 907 and 0 otherwise. 909 N - The set of 2-way neighbors of node i. 911 r(u,v) - The list of neighbors that are reporting link (u,v) in 912 their reported subtree RT. The set of links (u,v) reported by 913 neighbor j is denoted RT_j. 915 r(u) - The list of neighbors that are reporting node u in their 916 reported node set RN. 918 p(u) - The current parent for node u, equal to the next node on 919 the shortest path to u. 921 pred(u) - The node that is the predecessor of node u in the source 922 tree T. Equal to NULL if node u is not reachable. 924 pred(j,u) - The node that is the predecessor of node u in the 925 subtree RT_j reported by neighbor j. 927 d(u) - The length of the shortest path to node u. If USE_METRICS = 928 0, d(u) is the number of hops to node u. 930 reported(u,v) - Equal to 1 if link (u,v) in TG is reported by 931 p(u), and 0 otherwise. 933 tg_expire(u) - Expiration time for links (u,v) in TG. 935 rt_expire(j,u) - Expiration time for links (u,v) in RT_j. 937 nr_expire(u,v) - Expiration time for a link (u,v) in TG such that 938 reported(u,v) = 0. Such non-reported links can be used temporarily 939 during rerouting. 941 metric(j,u,v) - The metric for link (u,v) reported by neighbor j. 943 metric(u,v) - The metric for link (u,v) in TG. For a neighbor j, 944 metric(i,j) is the minimum of nbr_metric(I,J) over all 2-WAY links 945 (I,J) from i to j. 947 cost(u,v) - The cost for link (u,v), equal to metric(u,v) if 948 USE_METRICS = 1, and otherwise equal to 1. 950 local_if(j) - The address of the preferred local interface for 951 forwarding packets to neighbor j. 953 nbr_if(j) - The address of the preferred interface of neighbor j. 955 The routing table consists of a list of tuples of the form (rt_dest, 956 rt_next, rt_dist, rt_if_id), where rt_dest is the destination IP 957 address or prefix, rt_next is the interface address of the next hop 958 of the route, rt_dist is the length of the route, and rt_if_id is the 959 ID of the local interface through which the next hop can be reached. 961 Each node also maintains three tables that describe associated IP 962 addresses or prefixes: the "interface table", which associates 963 interface IP addresses with router IDs, the "host table", which 964 associates host IP addresses with router IDs, and the "network prefix 965 table", which associates network prefixes with router IDs. 967 The "interface table" consists of tuples of the form (if_addr, 968 if_rid, if_expire), where if_addr is an interface IP address 969 associated with the router with RID = if_rid, and if_expire is the 970 time at which the tuple expires and MUST be removed. The interface 971 table at a node does NOT contain an entry in which if_addr equals the 972 node's own RID; thus, a node does not advertise its own RID as an 973 associated interface. 975 The "host table" consists of tuples of the form (h_addr, h_rid, 976 h_expire), where h_addr is a host IP address associated with the 977 router with RID = h_rid, and h_expire is the time at which the tuple 978 expires and MUST be removed. 980 The "network prefix table" consists of tuples of the form 981 (net_prefix, net_length, net_rid, net_expire), where net_prefix and 982 net_length describe a network prefix associated with the router with 983 RID = net_rid, and net_expire is the time at which the tuple expires 984 and MUST be removed. A MANET may be configured as a "stub" network, 985 in which case one or more gateway routers may announce a default 986 prefix such that net_prefix = net_length = 0. Two copies of each 987 table are kept: an "old" copy that was last reported to neighbors, 988 and the current copy that is updated when association messages are 989 received. 991 8.2 TOPOLOGY UPDATE Message Format 993 The TOPOLOGY UPDATE message has the two formats, depending on the 994 size of the message. The normal format is as follows, and is used 995 whenever n, NRL, and NRNL all do not exceed 255: 997 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 998 |M|D|0|0| TYPE | n | NRL | NRNL | 999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1000 | Router ID of u | 1001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1002 | Router ID of v_1 | 1003 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1004 ~ ... ~ 1005 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1006 | Router ID of v_n | 1007 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1008 | metric 1 | metric 2 | ... | 1009 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1010 | ... | 1011 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1013 The message body contains the n+1 router IDs for nodes u, 1014 v_1,...,v_n, which represent the links (u,v_1),..., (u,v_n). The 1015 first NRL of the v_k are reported leaf nodes, the next NRNL of the 1016 v_k are reported non-leaf nodes, and the last n - (NRL+NRNL) of the 1017 v_k are not reported (not in RN). 1019 The M bit indicates whether or not link metrics are included in the 1020 message. If M = 1, then a 1-octet metric is included for each of the 1021 links (u,v_1),..., (u,v_n), following the last router ID. 1023 The D bit indicates whether or not implicit deletion is used, and 1024 must be set to 1 if and only if IMPLICIT_DELETION = 1. 1026 The TOPOLOGY UPDATE message has the following three subtypes: 1028 FULL (TYPE = 5) 1029 A FULL update (FULL, n, NRL, NRNL, u, v_1,..., v_n) reports that 1030 the links (u,v_1),..., (u,v_n) belong to the sending router's 1031 reported subtree RT, and that RT contains no other links with tail 1032 u. 1034 ADD (TYPE = 6) 1035 An ADD update (ADD, n, NRL, NRNL, u, v_1,..., v_n) reports that 1036 the links (u,v_1),..., (u,v_n) have been added to the sending 1037 router's reported subtree RT. 1039 DELETE (TYPE = 7) 1040 A DELETE update (DELETE, n, NRL, NRNL, u, v_1,..., v_n) reports 1041 that the links (u,v_1),..., (u,v_n) have been deleted from the 1042 sending router's reported subtree RT. 1044 If n, NRL, or NRNL is larger than 255, then the long format of the 1045 TOPOLOGY UPDATE message is used, in which the first 4 octets of the 1046 normal format are replaced by the following 8 octets: 1048 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1049 |M|D|1|0| TYPE | 0 | n | 1050 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1051 | NRL | NRNL | 1052 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1054 8.3 Interface, Host, and Network Prefix Association Message Formats 1056 The INTERFACE ASSOCIATION (TYPE = 8) and HOST ASSOCIATION (TYPE = 9) 1057 messages have the following format: 1059 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1060 |ST | 0 | TYPE | Reserved | n | 1061 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1062 | Router ID | 1063 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1064 | IP Address | 1065 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1066 | IP Address | 1067 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1068 | ... | 1069 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1070 The message body contains the router ID of the originating node, and 1071 n IP addresses of interfaces (TYPE = 8) or hosts (TYPE = 9) that are 1072 associated with the router ID. The ST field is defined below. 1074 The NETWORK PREFIX ASSOCIATION message (TYPE = 10) has the following 1075 format: 1077 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1078 |ST | 0 | TYPE | Reserved | n | 1079 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1080 | Router ID | 1081 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1082 | PrefixLength | Prefix byte 1 | Prefix byte 2 | ... | 1083 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1084 | ... | PrefixLength | Prefix byte 1 | Prefix byte 2 | 1085 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1086 | ... | 1087 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1089 The message body contains the router ID of the originating node, and 1090 n network prefixes, each specified by a 1-octet prefix length 1091 followed immediately by the prefix, using the minimum number of whole 1092 octets required. To minimize overhead, the prefix lengths and 1093 prefixes are NOT aligned along word boundaries. 1095 The INTERFACE ASSOCIATION, HOST ASSOCIATION, and NETWORK PREFIX 1096 ASSOCIATION messages each have the following three subtypes (similar 1097 to those for the TOPOLOGY UPDATE message): 1099 FULL (ST = 0) 1100 Indicates that this is a FULL update that includes all interface 1101 addresses, host addresses, or network prefixes associated with the 1102 given router ID. 1104 ADD (ST = 1) 1105 Indicates that the included IP addresses or network prefixes are 1106 associated with the router ID, but may not include all such IP 1107 addresses or network prefixes. 1109 DELETE (ST = 2) 1110 Indicates that the included IP addresses or network prefixes are 1111 no longer associated with the router ID. 1113 8.4 TBRPF Routing Operation 1115 This section describes the operation of the TBRPF routing module. The 1116 operation is divided into the following subsections: periodic 1117 processing, updating the source tree and topology graph, updating the 1118 routing table, updating the reported node set, generating periodic 1119 updates, generating differential updates, processing topology 1120 updates, expiring topology information, optional reporting of 1121 redundant topology information, local topology changes, generating 1122 association messages, processing association messages, and non-relay 1123 operation. The operation is described in terms of procedures (e.g., 1124 Update_All), which may be executed periodically or in response to 1125 some event, and may be called by other procedures. In all procedures, 1126 node i is the node executing the procedure. 1128 8.4.1 Periodic Processing 1130 Each node executes the procedure Update_All() periodically, at least 1131 once every DIFF_UPDATE_INTERVAL seconds, which is typically equal to 1132 HELLO_INTERVAL. This procedure is defined as follows: 1134 Update_All() 1135 1. For each interface I, create empty message list msg_list(I). 1136 2. For each interface I, generate a HELLO message for 1137 interface I and add it to msg_list(I). 1138 3. Expire_Links(). 1139 4. Update_Source_Tree(). 1140 5. Update_Routing_Table(). 1141 6. If REPORT_FULL_TREE = 0, execute Update_RN(); otherwise (the 1142 full source tree is reported) Update_RN_Simple(). 1143 7. If current_time >= next_periodic: 1144 7.1. Generate_Periodic_Update(). 1145 7.2. Set next_periodic = current_time + PER_UPDATE_INTERVAL. 1146 8. Else, Generate_Diff_Update(). 1147 9. Generate_Association_Messages(). 1148 10. For each interface I, send the msg_list(I) on interface I. 1149 11. Set old_T = T and old_RN = RN. 1151 8.4.2 Updating the Source Tree and Topology Graph 1153 The procedure Update_Source_Tree() is a variant of Dijkstra's 1154 algorithm, which is called periodically and in response to topology 1155 changes, to update the source tree T and the topology graph TG. This 1156 algorithm computes shortest paths subject to two link cost penalties. 1157 The penalty NON_REPORT_PENALTY is added to the cost of links (u,v) 1158 that are not currently reported by the parent p(u) so that, whenever 1159 possible, a link (u,v) is included in T only if it is currently 1160 reported by the parent. To allow immediate rerouting when p(u) 1161 changes, it may be necessary to temporarily use a link (u,v) that is 1162 not currently reported by the new parent. The penalty 1163 NON_TREE_PENALTY is added to the cost of links (u,v) that are not 1164 currently in T, to reduce the number of changes to T. When there 1165 exist multiple paths of equal cost to a given node, router ID is used 1166 to break ties. 1168 The algorithm is defined as follows (where node i is the node 1169 executing the procedure): 1171 Update_Source_Tree() 1172 1. For each node v in TT, set d(v) = INFINITY, pred(v) = NULL, 1173 old_p(v) = p(v), and p(v) = NULL. 1175 2. Set d(i) = 0, p(i) = i, pred(i) = i. 1177 3. Set S = {i}. (S is the set of labeled nodes.) 1179 4. For each node j in N, set d(j) = c(i,j), pred(j) = i, 1180 and p(j) = j. (If USE_METRICS = 0, then all link costs 1181 c(i,j) are 1.) 1183 5. While there exists an unlabeled node u in TT such that 1184 d(u) < INFINITY: 1185 5.1. Let u be an unlabeled node in TT with minimum d(u). 1186 (A heap should be used to find u efficiently.) 1187 5.2. Add u to S (u becomes labeled). 1188 5.3. If p(u) is not equal to old_p(u) (parent has changed): 1189 5.3.1. For each link (u,v) in TG with tail u, if 1190 reported(u,v) = 1, set reported(u,v) = 0 and set 1191 nr_expire(u,v) = current_time + PER_UPDATE_INTERVAL. 1192 5.3.2. If p(u) is in r(u) (p(u) is reporting u): 1193 5.3.2.1. Set tg_expire(u) = rt_expire(p(u),u). 1194 5.3.2.2. If p(u) = u (u is a neighbor), remove all links 1195 (u,v) with tail u from TG. 1196 5.3.2.3. For each link (u,v) with p(u) in r(u,v): 1197 5.3.2.3.1. Add (u,v) to TG and set reported(u,v) = 1. 1198 5.3.2.3.2. Set metric(u,v) = metric(p(u),u,v). 1199 If USE_METRICS=1, set c(u,v)=metric(u,v). 1200 5.4. For each node v such that (u,v) is in TG: 1201 5.4.1. If reported(u,v) = 0, 1202 set cost = c(u,v) + NON_REPORT_PENALTY. 1203 (This penalizes (u,v) if not reported by p(u).) 1204 5.4.2. Else, if p(u) = u AND u is not in r(v), 1205 set cost = c(u,v) + NON_REPORT_PENALTY. 1206 (This penalizes (u,v) if u is a neighbor and is not 1207 reporting v.) 1208 5.4.3. If (u,v) is not in old_T and p(u) != u, 1209 set cost = cost + NON_TREE_PENALTY. 1210 5.4.4. If (d(u) + cost, u) is lexicographically less 1211 than (d(v), pred(v)), set d(v) = d(u) + c(u,v), 1212 pred(v) = u, and p(v) = p(u). 1214 6. Update the source tree T as follows: 1215 6.1. Remove all links from T. 1216 6.2. For each node u other than i such that pred(u) is not 1217 NULL, add the link (pred(u), u) to T. 1219 8.4.3 Updating the Routing Table 1221 The routing table is updated following any change to the source tree 1222 or the association tables (interface table, host table, or network 1223 prefix table). The routing table is updated according to procedure 1224 Update_Routing_Table(), which is defined as follows: 1226 Update_Routing_Table() 1227 1. Remove all tuples from the routing table. 1229 2. For each node u in TT (other than this node) such that p(u) is 1230 not NULL, add the tuple (rt_dest, rt_next, rt_dist, rt_if_id) 1231 to the routing table, where: 1232 rt_dest = u, 1233 rt_if_id = local_if(p(u)), 1234 rt_next = nbr_if(p(u)), 1235 rt_dist = d(u). 1237 3. For each tuple (if_addr, if_rid, if_expire) in the interface 1238 table, if a routing table entry (rt_dest, rt_next, rt_dist, 1239 rt_if_id) exists such that rt_dest = if_rid, add the tuple 1240 (if_addr, rt_next, rt_dist, rt_if_id) to the routing table. 1242 4. For each tuple (h_addr, h_rid, h_expire) in the host table, if 1243 there exists a routing table entry (rt_dest, rt_next, rt_dist, 1244 rt_if_id) such that rt_dest = h_rid, add the tuple (h_addr, 1245 rt_next, rt_dist, rt_if_id) to the routing table, unless an 1246 entry already exists with the same value for h_addr and a 1247 lexicographically smaller value for (rt_dist, rt_dest). 1249 5. For each tuple (net_prefix, net_length, net_rid, net_expire) 1250 in the network prefix table, if there exists a routing table 1251 entry (rt_dest, rt_next, rt_dist, rt_if_id) such that 1252 rt_dest = net_rid, add the tuple (net_prefix/net_length, 1253 rt_next, rt_dist, rt_if_id) to the routing table, unless an 1254 entry already exists with the same value for 1255 net_prefix/net_length and a lexicographically smaller value 1256 for (rt_dist, rt_dest). 1258 8.4.4 Updating the Reported Node Set 1260 Recall that the reported subtree RT is defined to be the set of links 1261 (u,v) in T such that u is in the reported node set RN. Each node 1262 updates its RN immediately before generating periodic or differential 1263 topology updates. 1265 If REPORT_FULL_TREE = 1 (so that a node reports its entire source 1266 tree), then RN simply consists of all reachable nodes, i.e., all 1267 nodes u such that pred(u) is not NULL. The procedure that computes RN 1268 in this manner is called Update_RN_Simple(). The rest of this section 1269 describes how RN is computed assuming REPORT_FULL_TREE = 0. 1271 A node first determines which of its neighbors belong to RN. Node i 1272 includes a neighbor j in RN if and only if node i determines that one 1273 of its neighbors may select i to be its next hop on its shortest path 1274 to j. To make this determination, node i computes the shortest paths, 1275 up to 2 hops, from each neighbor to each other neighbor, using only 1276 neighbors (or node i itself) as an intermediate node, and using relay 1277 priority and router ID to break ties. If a link metric is used, then 1278 shortest paths are computed with respect to the link metric; 1279 otherwise min-hop paths are computed. 1281 After a node determines which neighbors are in RN, each node u (other 1282 than node i) in the topology table is included in RN if and only if 1283 the next hop p(u) to u is in RN. Equivalently, node u is included in 1284 RN if and only if u is in the subtree of T rooted at some neighbor j 1285 that is in RN. Thus, the reported subtree RT includes the subtrees of 1286 T that are rooted at neighbors in RN. Node i also includes itself in 1287 RN; thus RT also includes all local links (i,j) to neighbors j. 1289 The precise procedure for updating RN is defined as follows: 1291 Update_RN() 1292 1. Set RN = empty. 1293 2. For each neighbor s in N such that s is in r(s), i.e., 1294 such that s is reporting itself: 1295 (Initialize to run Dijkstra for source s, for 2 hops.) 1296 2.1. For each node j in N+{i}, set dist(j) = INFINITY and 1297 par(j) = NULL. 1298 2.2. Set dist(s) = 0 and par(s) = s. 1299 2.3. For each node j in N+{i} such that (s,j) is in TG: 1300 2.3.1. Set dist(j) = metric(s,j), par(j) = j. 1301 2.3.2. For each node k in N such that (j,k) is in TG: 1302 2.3.2.1. Set cost = metric(j,k). 1303 2.3.2.2. If (dist(j) + cost, nbr_pri(j), j) 1304 is lexicographically less than 1305 (dist(k), nbr_pri(par(k)), par(k)), 1306 set dist(k) = dist(j) + cost and par(k) = j. 1307 2.4. For each neighbor j in N, add j to RN if par(j) = i. 1308 3. Add i to RN. (Node i is always in RN.) 1309 4. For each node u in the topology table, add u to RN if p(u) 1310 is in RN. 1312 In some cases it may be desirable to limit the radius (number of 1313 hops) that topology information is propagated. Since each TBRPF 1314 packet is sent only to immediate (1-hop) neighbors, this cannot be 1315 achieved by using a time-to-live field. Instead, the propagation of 1316 topology information can be limited to a radius of K hops by limiting 1317 RN (at all nodes) to include only nodes that are at most K-1 hops 1318 away. Assuming min-hop routing is used, so that d(u) is the number of 1319 hops to node u, this can be done by modifying Step 4 of Update_RN() 1320 as follows: 1322 4. For each node u in the topology table, add u to RN if p(u) 1323 is in RN and d(u) <= K-1. 1325 8.4.5 Generating Periodic Updates 1327 Every PER_UPDATE_INTERVAL seconds, each node generates and transmits, 1328 on all interfaces, a set of FULL TOPOLOGY UPDATE messages (one 1329 message for each node in RN that is not a leaf of T), which describes 1330 the reported subtree RT. Whenever possible, these messages are 1331 included in a single packet, in order to minimize the number of 1332 control packets transmitted. 1334 Each topology update message contains the router IDs for n+1 nodes u, 1335 v_1,...,v_n, which represent the n links (u,v_1),..., (u,v_n). The n 1336 head nodes v_1,..., v_n are divided into three lists in order to 1337 convey additional information and thus reduce the number of messages 1338 that must be generated. In particular, the first NRL head nodes are 1339 leaves of T, thus avoiding the need to generate separate topology 1340 update messages for leaf nodes u. Similarly, the last n-(NRL+NRNL) 1341 head nodes are not in RN, thus avoiding the need to generate separate 1342 topology update messages for nodes u that have been removed from RN. 1344 Periodic update messages are generated according to procedure 1345 Generate_Periodic_Update(), defined as follows (where node i is the 1346 node executing the procedure): 1348 Generate_Periodic_Update() 1349 For each node u in RN (including node i) that is not a leaf of T, 1350 add the update (FULL, n, NRL, NRNL, u, v_1,..., v_n) 1351 to msg_list(I) for each interface I, where: 1353 (a) v_1,..., v_n are the nodes v such that (u,v) is in T, 1354 the first NRL of these are nodes in RN that are leaves of T, 1355 the next NRNL of these are nodes in RN that are not leaves 1356 of T, and the last n-(NRL+NRNL) of these are not in RN. 1358 (b) If USE_METRICS = 1, then the M (metrics) bit is set to 1 and 1359 the link metrics metric(u,v_1),..., metric(u,v_n) are 1360 included in the message. 1362 8.4.6 Generating Differential Updates 1364 Every DIFF_UPDATE_INTERVAL seconds, if it is not time to generate a 1365 periodic update, and if RT has changed since the last time a topology 1366 update was generated, a set of TOPOLOGY UPDATE messages describing 1367 the changes to RT is generated and transmitted on all interfaces. 1368 These messages are constructed according to procedure 1369 Generate_Differential_Update(), defined as follows: 1371 Generate_Differential_Update() 1372 For each node u in RN: 1373 1. If u is not in old_RN (u was added to RN) and is not a leaf 1374 of T, add the update (FULL, n, NRL, NRNL, u, v_1,..., v_n) 1375 to msg_list(I) for each I, where: 1376 (a) v_1,..., v_n, NRL, and NRNL are defined as above for 1377 periodic updates. 1378 (b) If USE_METRICS = 1, then the M (metrics) bit is set to 1 1379 and the link metrics metric(u,v_1),..., metric(u,v_n) 1380 are included in the message. 1382 2. Else, if u is in old_RN and is not a leaf of T: 1383 2.1. Let v_1,..., v_n be the nodes v such that (u,v) is in T 1384 AND at least one of the following 3 conditions holds: 1385 (a) (u,v) is not in old_T, or 1386 (b) v is in old_RN but not in RN, or 1387 (c) v is a leaf and is in RN but not in old_RN. 1388 2.2. If this set of nodes is nonempty, add the update 1389 (ADD, n, NRL, NRNL, u, v_1,..., v_n) to msg_list(I) for 1390 each interface I, where: 1391 (a) NRL and NRNL are defined as above. 1392 (b) If USE_METRICS = 1, then the M (metrics) bit is 1393 set to 1 and the link metrics metric(u,v_1),..., 1394 metric(u,v_n) are included in the message. 1396 3. If u is in old_RN: 1397 3.1. Let v_1,..., v_n be the nodes v such that (u,v) is in 1398 old_T but not in TG, and either IMPLICIT_DELETION = 0 1399 or pred(v) is not in RN (or is NULL). 1401 (If IMPLICIT_DELETION = 1 and pred(v) is in RN, then 1402 the deletion of (u,v) is implied by an ADD update for 1403 another link (w,v).) 1404 3.2. If this set of nodes is nonempty, add the update 1405 (DELETE, n, u, v_1,..., v_n) to msg_list(I) for each I. 1407 8.4.7 Processing Topology Updates 1409 When a packet containing a list (msg_list) of TOPOLOGY UPDATE 1410 messages is received from node j, the list is processed according to 1411 the procedure Process_Updates(j, msg_list), defined as follows. In 1412 particular, this procedure updates TT, TG, and the reporting neighbor 1413 lists r(u) and r(u,v). If any link in T has been deleted from TG, 1414 then Update_Source_Tree() and Update_Routing_Table() are called to 1415 provide immediate rerouting. 1417 Process_Updates(j, msg_list) 1418 1. For each update = (subtype, n, NRL, NRNL, u, v_1,..., v_n) 1419 in msg_list: 1420 1.1. Create an entry for u in TT if it does not exist. 1421 1.2. If subtype = FULL, Process_Full_Update(j, update). 1422 1.3. If subtype = ADD, Process_Add_Update(j, update). 1423 1.4. If subtype = DELETE, Process_Delete_Update(j, update). 1424 2. If there exists any link in T that is not in TG: 1425 2.1. Update_Source_Tree(). 1426 2.2. Update_Routing_Table(). 1428 Process_Full_Update(j, update) 1429 1. Add j to r(u). 1430 2. Set rt_expire(j,u) = current_time + TOP_HOLD_TIME. 1431 3. For each link (u,v) s.t. j is in r(u,v): 1432 3.1. Remove j from r(u,v). 1433 3.2. If pred(j,v) = u, set pred(j,v) = NULL. 1434 4. If j = p(u) OR p(u) = NULL: 1435 4.1. Set tg_expire(u) = current_time + TOP_HOLD_TIME. 1436 4.2. For each v s.t. (u,v) is in TG, 1437 If reported(u,v) = 1, remove (u,v) from TG. 1438 5. Process_Add_Update(j, update). 1440 Process_Add_Update(j, update) 1441 For m = 1,..., n: 1442 ((u,v_m) is the mth link in update.) 1443 1. Let v = v_m. 1444 2. Create an entry for v in TT if it does not exist. 1445 3. Add j to r(u,v). 1446 4. If j = p(u) OR p(u) = NULL: 1447 4.1. Add (u,v) to TG. 1449 4.2. Set reported(u,v) = 1. 1450 5. If the M (metrics) bit in update is 1: 1451 5.1. Set metric(j,u,v) to the m-th metric in the update. 1452 5.2. If j = p(u) OR p(u) = NULL: 1453 5.2.1. Set metric(u,v) = metric(j,u,v). 1454 5.2.2. If USE_METRICS = 1, set c(u,v) = metric(u,v). 1455 6. If the D (implicit deletion) bit in update is 1: 1456 6.1. Set w = pred(j,v). 1457 6.2. If (w != NULL AND w != u): 1458 6.2.1. Remove j from r(w,v). 1459 6.2.2. If j = p(w), remove (w,v) from TG. 1460 7. Set pred(j,v) = u. (Set new predecessor.) 1461 8. If m <= NRL (v = v_m is a reported leaf): 1462 8.1. Set leaf_update = (FULL, 0, 0, 0, v). 1463 8.2. Process_Full_Update(j, leaf_update). 1464 9. If m > NRL + NRNL (v = v_m is not reported by j): 1465 9.1. Remove j from r(v). 1466 9.2. Set rt_expire(j,v) = 0. 1467 9.3. For each node w s.t. j is in r(v,w), 1468 remove j from r(v,w). 1469 9.4. If j = p(v), then for each node w s.t. (v,w) is in TG 1470 and reported(v,w) = 1, set reported(v,w) = 0 and set 1471 nr_expire(v,w) = current_time + PER_UPDATE_INTERVAL. 1473 Process_Delete_Update(j, update) 1474 For m = 1,..., n: 1475 ((u,v_m) is the mth link in update.) 1476 1. Let v = v_m. 1477 2. Remove j from r(u,v). 1478 3. If pred(j,v) = u, set pred(j,v) = NULL. 1479 4. If j = p(u), remove (u,v) from TG. 1481 8.4.8 Expiring Topology Information 1483 Each node periodically checks for outdated topology information based 1484 on the expiration timers tg_expire(u), rt_expire(j,u), and 1485 nr_expire(u,v), and removes any expired entries from TG and from the 1486 lists r(u) and r(u,v). This is done according to the following 1487 procedure Expire_Links(), which is called periodically just before 1488 the source tree is updated. 1490 Expire_Links() 1491 For each node u in TT other than node i: 1492 1. If tg_expire(u) < current_time, then for each v s.t. 1493 (u,v) is in TG, remove (u,v) from TG. 1494 2. Else, for each v s.t. (u,v) is in TG, 1495 if reported(u,v) = 0 AND nr_expire(u,v) < current_time, 1496 remove (u,v) from TG. 1497 3. For each node j in r(u), if rt_expire(j,u) < current_time: 1498 3.1. Remove j from r(u). 1499 3.2. For each link (u,v) s.t. j is in r(u,v), 1500 remove j from r(u,v). 1502 In addition, the following cleanup steps SHOULD be executed 1503 periodically to remove unnecessary entries from the topology table 1504 TT. A link (u,v) should be removed from TT if it is not in TG and not 1505 in old_T. A node u should be removed from TT if all of the following 1506 conditions hold: r(u) is empty, r(w,u) is empty for all w, and no 1507 link of TG has u as either the head or the tail. 1509 8.4.9 Optional Reporting of Redundant Topology Information 1511 Each node is required to report its reported subtree RT to neighbors. 1512 However, each node (independently of the other nodes) MAY report 1513 additional links, e.g., to provide increased robustness in highly 1514 mobile networks. For example, a node may compute any subgraph H of TG 1515 that contains T, and may report the "reported subgraph" RH which 1516 consists of links (u,v) of H such that u is in RN. In this case, each 1517 periodic update describes RH instead of RT, and each differential 1518 update describes changes to RH. If this option is used, then the 1519 parameter IMPLICIT_DELETION MUST be set to 0, since the deletion of a 1520 link cannot be implied by the addition of another link if redundant 1521 topology information is reported. 1523 8.4.10 Local Topology Changes 1525 This section describes the procedures that are followed when the 1526 neighbor discovery module detects a new link, the loss of a link, or 1527 a change in the metric for a link. 1529 When a link (I,J) from a local interface I to a neighbor interface J 1530 is discovered via the neighbor discovery module, the procedure 1531 Link_Up(I,J) is executed, as defined below. Letting j be the neighbor 1532 node associated with interface J, Link_Up(I,J) adds j to N (if it 1533 does not already belong), updates the preferred local interface 1534 local_if(j) and neighbor interface nbr_if(j) so that the link from 1535 local_if(j) to nbr_if(j) has the minimum metric among all links from 1536 i to j, and updates metric(i,j) to be this minimum metric. 1538 Link_Up(I,J) 1539 1. Let j = nbr_rid(I,J). 1540 2. If j is not in N: 1541 2.1. Add j to N. 1542 2.2. Add (i,j) to TG. 1543 2.3. Set reported(i,j) = 1. 1545 3. If nbr_metric(I,J) < metric(i,j), set local_if(j) = I, 1546 nbr_if(j) = J, and metric(i,j) = nbr_metric(I,J). 1547 4. If USE_METRICS = 1, set cost(i,j) = metric(i,j). 1549 When the loss of a link (I,J) from a local interface I to a neighbor 1550 interface J is detected via the neighbor discovery module, the 1551 procedure Link_Down(I,J) is executed, as defined below. Note that 1552 routes are updated immediately when a link is lost, and if the lost 1553 link is due to a link-layer failure notification, a differential 1554 topology update is sent immediately. 1556 Link_Down(I,J) 1557 1. Let j = nbr_rid(I,J). 1558 2. If there does not exist a link (K,L) from node i to 1559 node j with nbr_status(K,L) = 2-WAY: 1560 2.1. Remove j from N. 1561 2.2. Remove (i,j) from TG. 1562 3. If j is in N: 1563 3.1. Let (K,L) be a link from i to j such that 1564 nbr_metric(K,L) is the minimum metric among 1565 all links from i to j. 1566 3.2. Set local_if(j) = K, nbr_if(j) = L, and 1567 metric(i,j) = nbr_metric(K,L). 1568 3.3. If USE_METRICS = 1, set cost(i,j) = metric(i,j). 1569 5. Update_Source_Tree(). 1570 6. Update_Routing_Table(). 1571 7. If j is not in N and lost link is due to link-layer failure 1572 notification: 1573 7.1. If (REPORT_FULL_TREE = 0) Update_RN(). 1574 7.2. Else, Update_RN_Simple(). 1575 7.3. Set msg_list = empty. 1576 7.4. Generate_Diff_Update(). 1577 7.5. Send msg_list on all interfaces. 1578 7.6. Set old_T = T and old_RN = RN. 1580 If the metric of a link (I,J) from a local interface I to a neighbor 1581 interface J changes via the neighbor discovery module, the following 1582 procedure Link_Change(I,J) is executed. 1584 Link_Change(I,J) 1585 1. Let j = nbr_rid(I,J). 1586 2. Let (K,L) be a link from i to j such that 1587 nbr_metric(K,L) is the minimum metric among 1588 all links from i to j. 1589 3. Set local_if(j) = K, nbr_if(j) = L, and 1590 metric(i,j) = nbr_metric(K,L). 1591 4. If USE_METRICS = 1, set cost(i,j) = metric(i,j). 1593 8.4.11 Generating Association Messages 1595 This section describes the procedures used to generate INTERFACE 1596 ASSOCIATION, HOST ASSOCIATION, and NETWORK PREFIX ASSOCIATION 1597 messages. Addresses or prefixes in the interface table, host table, 1598 and network prefix table are reported to neighbors periodically every 1599 IA_INTERVAL, HA_INTERVAL, and NPA_INTERVAL seconds, respectively. In 1600 addition, differential changes to the tables are reported every 1601 DIFF_UPDATE_INTERVAL seconds if it is not time for a periodic update 1602 (similar to differential topology updates). Each node reports only 1603 addresses or prefixes that are associated with nodes in the reported 1604 node set RN; this ensures the efficient broadcast of all associated 1605 addresses and prefixes to all nodes in the network. 1607 The generated messages are sent on each interface. Whenever possible, 1608 these messages are combined into the same packet, in order to 1609 minimize the number of control packets transmitted. 1611 Generate_Association_Messages() 1612 1. Generate_Interface_Association_Messages(). 1613 2. Generate_Host_Association_Messages(). 1614 3. Generate_Network_Prefix_Association_Messages(). 1616 Generate_Interface_Association_Messages() 1617 1. If current_time > next_ia_time: 1618 1.1. Set next_ia_time = current_time + IA_INTERVAL. 1619 1.2. For each node u in RN: 1620 1.2.1. Let addr_1,..., addr_n be the interface IP 1621 addresses associated with RID u in the current 1622 interface table. 1623 1.2.2. If this list is nonempty, add the INTERFACE 1624 ASSOCIATION message (FULL, n, u, addr_1,..., addr_n) 1625 to msg_list(I) for each I. 1627 2. Else, for each node u in RN: 1628 2.1. Add the INTERFACE ASSOCIATION message (ADD, n, u, 1629 addr_1,..., addr_n) to msg_list(I) for each I, where 1630 addr_1,..., addr_n are the interface IP addresses that 1631 are associated with RID u in the current interface table 1632 but not in the old interface table. 1633 2.2. Add the INTERFACE ASSOCIATION message (DELETE, n, u, 1634 addr_1,..., addr_n) to msg_list(I) for each I, where 1635 addr_1,..., addr_n are the interface IP addresses that 1636 are associated with RID u in the old interface table 1637 but not in the current interface table. 1639 Generate_Host_Association_Messages() 1640 1. If current_time > next_ha_time: 1642 1.1. Set next_ha_time = current_time + HA_INTERVAL. 1643 1.2. For each node u in RN: 1644 1.2.1. Let addr_1,..., addr_n be the host IP addresses 1645 associated with RID u in the current host table. 1646 1.2.2. If this list is nonempty, add the HOST ASSOCIATION 1647 message (FULL, n, u, addr_1,..., addr_n) to 1648 msg_list(I) for each I. 1650 2. Else, for each node u in RN: 1651 2.1. Add the HOST ASSOCIATION message (ADD, n, u, 1652 addr_1,..., addr_n) to msg_list(I) for each I, where 1653 addr_1,..., addr_n are the host IP addresses that 1654 are associated with RID u in the current host table 1655 but not in the old host table. 1656 2.2. Add the HOST ASSOCIATION message (DELETE, n, u, 1657 addr_1,..., addr_n) to msg_list(I) for each I, where 1658 addr_1,..., addr_n are the host IP addresses that 1659 are associated with RID u in the old host table 1660 but not in the current host table. 1662 Generate_Network_Prefix_Association_Messages() 1663 1. If current_time > next_npa_time: 1664 1.1. Set next_npa_time = current_time + NPA_INTERVAL. 1665 1.2. For each node u in RN: 1666 1.2.1. Let length_1, prefix_1,..., length_n, prefix_n 1667 be the network prefix lengths and prefixes associated 1668 with RID u in the current network prefix table. 1669 1.2.2. If this list is nonempty, add the NETWORK PREFIX 1670 ASSOCIATION message (FULL, n, u, length_1, prefix_1, 1671 ..., length_n, prefix_n) to msg_list(I) for each I. 1673 2. Else, for each node u in RN: 1674 2.1. Add the NETWORK PREFIX ASSOCIATION message 1675 (ADD, n, u, prefix_1,..., prefix_n) to msg_list(I) for 1676 each I, where prefix_1,..., prefix_n are the network 1677 prefixes that are associated with RID u in the current 1678 prefix table but not in the old prefix table. 1680 2.1. Add the NETWORK PREFIX ASSOCIATION message 1681 (DELETE, n, u, prefix_1,..., prefix_n) to msg_list(I) for 1682 each I, where prefix_1,..., prefix_n are the network 1683 prefixes that are associated with RID u in the old prefix 1684 table but not in the current prefix table. 1686 8.4.12 Processing Association Messages 1688 When an INTERFACE ASSOCIATION, HOST ASSOCIATION, or NETWORK PREFIX 1689 ASSOCIATION message is received from node j, the interface table, 1690 host table, or network prefix table, respectively, is updated as 1691 described in the following three procedures. 1693 Process_Interface_Association_Messages(j, msg_list) 1694 For each message (subtype, n, u, addr_1,..., addr_n) in msg_list 1695 such that j = p(u): 1696 1. If subtype = FULL, remove all entries with if_rid = u 1697 from the interface table. 1698 2. If subtype = FULL or ADD, then for m = 1,..., n, 1699 add the tuple (if_addr, if_rid, if_expire) to the 1700 interface table, where: 1701 if_addr = addr_m, 1702 if_rid = u, 1703 if_expire = current_time + IA_HOLD_TIME. 1704 3. If subtype = DELETE, then for m = 1,..., n, 1705 remove the tuple (if_addr, if_rid, if_expire) from the 1706 interface table, where if_addr = addr_m and if_rid = u. 1708 Process_Host_Association_Messages(j, msg_list) 1709 For each message (subtype, n, u, addr_1,..., addr_n) in msg_list 1710 such that j = p(u): 1711 1. If subtype = FULL, remove all entries with h_rid = u 1712 from the host table. 1713 2. If subtype = FULL or ADD, then for m = 1,..., n, 1714 add the tuple (h_addr, h_rid, h_expire) to the 1715 host table, where: 1716 h_addr = addr_m, 1717 h_rid = u, 1718 h_expire = current_time + HA_HOLD_TIME. 1719 3. If subtype = DELETE, then for m = 1,..., n, 1720 remove the tuple (h_addr, h_rid, h_expire) from the 1721 host table, where h_addr = addr_m and h_rid = u. 1723 Process_Network_Prefix_Association_Messages(j, msg_list) 1724 For each message (subtype, n, u, length_1, prefix_1, ..., 1725 length_n, prefix_n) in msg_list such that j = p(u): 1726 1. If subtype = FULL, remove all entries with net_rid = u 1727 from the prefix table. 1728 2. If subtype = FULL or ADD, then for m = 1,..., n, 1729 add the tuple (net_prefix, net_length, net_rid, 1730 net_expire) to the network prefix table, where: 1731 net_prefix = prefix_m, 1732 net_length = length_m, 1733 net_rid = u, 1734 net_expire = current_time + NPA_HOLD_TIME. 1735 3. If subtype = DELETE, then for m = 1,..., n, 1736 remove the tuple (net_prefix, net_length, net_rid, 1737 net_expire) from the network prefix table, where 1738 net_prefix = prefix_m, net_length = length_m, 1739 and net_rid = u. 1741 8.4.13 Non-Relay Operation 1743 Nodes with relay priority equal to zero are called non-relay nodes, 1744 and do not forward packets (of any type) that are received from other 1745 nodes. A non-relay node is implemented simply by not generating or 1746 transmitting any TOPOLOGY UPDATE messages. A non-relay node may 1747 report (in association messages) addresses or prefixes that are 1748 associated with itself, but not those associated with other nodes. 1749 HELLO messages must be transmitted in order to establish links with 1750 neighbor nodes. The following procedures can be omitted in non-relay 1751 nodes: Update_RN(), Generate_Periodic_Update(), and 1752 Generate_Diff_Update(). 1754 8.5 Configurable Parameters 1756 This section lists the configurable parameters used by the routing 1757 module, and their proposed default values. All nodes MUST have the 1758 same value for all of the following parameters except 1759 REPORT_FULL_TREE and IMPLICIT_DELETION. 1761 Parameter Name Default Value 1762 -------------- ------------- 1763 DIFF_UPDATE_INTERVAL 1 second 1764 PER_UPDATE_INTERVAL 5 seconds 1765 TOP_HOLD_TIME 15 seconds 1766 NON_REPORT_PENALTY 1.01 1767 NON_TREE_PENALTY 0.01 1768 IA_INTERVAL 10 seconds 1769 IA_HOLD_TIME 3 * IA_INTERVAL 1770 HA_INTERVAL 10 seconds 1771 HA_HOLD_TIME 3 * HA_INTERVAL 1772 NPA_INTERVAL 10 seconds 1773 NPA_HOLD_TIME 3 * NPA_INTERVAL 1774 USE_METRICS 0 1775 REPORT_FULL_TREE 0 1776 IMPLICIT_DELETION 1 1778 9. TBRPF Flooding Mechanism 1780 This section describes a mechanism for the efficient best-effort 1781 flooding (or network-wide broadcast) of packets to all nodes of a 1782 connected ad-hoc network. This mechanism can be considered an 1783 optimization of the classical flooding algorithm in which each packet 1784 is transmitted by every node of the network. In TBRPF flooding, 1785 information provided by TBRPF is used to decide whether a given 1786 received flooded packet should be forwarded. As a result, each packet 1787 is transmitted by only a relatively small subset of nodes, thus 1788 consuming much less bandwidth than classical flooding. 1790 This document specifies that the flooding mechanism use the IPv4 1791 multicast address 224.0.1.20 (currently assigned by IANA for "any 1792 private experiment"). Every node maintains a duplicate cache to keep 1793 track of which flooded packets have already been received. The 1794 duplicate cache contains, for each received flooded packet, the 1795 flooded packet identifier (FPI), which for IPv4 is composed of the 1796 source IP address, the IP identification, and the fragment offset 1797 values obtained from the IP header [14]. 1799 When a node receives a packet whose destination IP address is the 1800 flooding address (224.0.1.255), it checks its duplicate cache for an 1801 entry that matches the packet. If such an entry exists, the node 1802 silently discards the flooded packet since it has already been 1803 received. Otherwise, the node retransmits the packet on all 1804 interfaces (see the exception below) if and only if the following 1805 conditions hold: 1807 1. The TBRPF node associated with the source IP address of the 1808 packet belongs to the set RN of reported nodes computed by TBRPF. 1810 2. When decremented, the 'ip_ttl' in the IPv4 packet header 1811 (respectively, the 'hop_count' in the IPv6 packet header) is 1812 greater than zero. 1814 If the packet is to be retransmitted, it is sent after a small random 1815 time interval in order to avoid collisions. If the interface on which 1816 the packet was received is not a MANET interface (see the Terminology 1817 section), then the packet should not be retransmitted on that 1818 interface. 1820 10. Operation of TBRPF in Mobile Ad-Hoc Networks 1822 TBRPF is particularly well suited to MANETs consisting of mobile 1823 nodes with wireless network interfaces operating in peer-to-peer 1824 fashion over a multiple access communications channel. Although 1825 applicable across a much broader field of use, TBRPF is particularly 1826 well suited for supporting the standard DARPA Internet protocols 1827 [3][2] as per current practices advocated by the IETF MANET working 1828 group. In the following sections, we discuss practical considerations 1829 the operation of TRBPF on MANETs. 1831 10.1 Data Link Layer Assumptions 1833 We assume a MANET data link layer that supports broadcast, multicast 1834 and unicast addressing with best-effort (not guaranteed) delivery 1835 services between neighbors (i.e. a pair of nodes within operational 1836 communications range of one another). We further assume that each 1837 interface belonging to a node in the MANET is assigned a unicast data 1838 link layer address that is unique within the MANET's scope. While 1839 such uniqueness is not strictly guaranteed, the assumption of 1840 uniqueness is consistent with current practices for deployment of the 1841 Internet protocols on specific link layers. Methods for duplicate 1842 link layer address detection and deconfliction are beyond the scope 1843 of this document. 1845 10.2 Network Layer Assumptions 1847 MANETs are formed as collections of routers and non-routing nodes 1848 that use network layer addresses when calculating the MANET topology. 1849 We assume that each node has at least one data link layer interface 1850 (described above) and that each such interface is assigned a network 1851 layer address that is unique within the MANET. (Methods for network 1852 layer address assignment and duplicate address detection are beyond 1853 the scope of this document.) We further assume that each node will 1854 select a unique Router ID (RID) for use in TBRPF protocol messages, 1855 whether or not the node acts as a MANET router. Finally, we assume 1856 that each MANET router supports the multi-hop relay paradigm at the 1857 network layer; i.e. each router provides an inter-node forwarding 1858 service via network layer host routes which reflect the current MANET 1859 topology as perceived by TBRPF. 1861 10.3 Optional Automatic Address Resolution 1863 TBRPF employs a proactive neighbor discovery protocol at the network 1864 layer that maintains bi-directional link state for neighboring nodes 1865 through the periodic transmission of messages. Since TBRPF neighbor 1866 discovery messages contain both the data link and network layer 1867 address of the sender, implementations MAY perform automatic 1868 network-to-data link layer address resolution for the nodes with 1869 which they form links. An implementation may use such a mechanism to 1870 avoid additional message overhead and potential for packet loss 1871 associated with on-demand address resolution mechanisms such as ARP 1872 [15] or IPv6 Neighbor Discovery [16]. Implementations MUST respond to 1873 on-demand address resolution requests in the normal manner. 1875 10.4 Support for Multiple Interfaces and/or Alias Addresses 1877 MANET nodes may comprise multiple interfaces; each with a unique 1878 network layer address. Additionally, MANET nodes may wish to publish 1879 *alias* addresses such as when multiple network layer addresses are 1880 assigned to the same interface or when the MANET node is serving as a 1881 Mobile IP [17] home agent. Multiple interfaces and alias addresses 1882 are advertised in INTERFACE ASSOCIATION messages, which bind each 1883 such address to the node's RID. 1885 10.5 Support for Network Prefixes 1887 MANET routers may advertise network prefixes which the router 1888 discovered via attached networks, external routes advertised by other 1889 protocols, or other means. Network prefixes are advertised in NETWORK 1890 PREFIX ASSOCIATION messages, which bind each such prefix to the 1891 node's RID. 1893 10.6 Support for non-MANET Hosts 1895 Non-MANET hosts may establish connections to MANET routers through 1896 on-demand mechanisms such as ARP or IPv6 Neighbor Discovery. Such 1897 connections do not constitute a MANET link and therefore are not 1898 reported in TBRPF topology updates. Non-MANET hosts are advertised in 1899 HOST ASSOCIATION messages, which bind the IP address of each host to 1900 the node's RID. 1902 10.7 Internet Protocol Considerations 1904 TBRPF packets are communicated using UDP/IP. Port XXX (TBA) has been 1905 assigned by IANA for exclusive use by TBRPF. Implementations in 1906 private networks MAY employ alternate data delivery services (i.e., 1907 raw IP or local data-link encapsulation). The selection of an 1908 alternate data delivery service MUST be consistent among all MANET 1909 routers in the private network. In all implementations, the data 1910 delivery service MUST provide a checksum facility. 1912 The following sections specify the operation of TBRPF over UDP/IP. 1914 10.7.1 IPv4 Operation 1916 When IPv4 is used, TBRPF nodes obey IPv4 host and router requirements 1917 [4][5]. TBRPF packets are sent to the multicast address 224.0.0.2 1918 (All Routers) and thus reach all TBRPF routers within single-hop 1919 transmission range of the sender. TBRPF routers MUST NOT forward 1920 packets sent to this multicast address. 1922 Since non-negligible packet loss due to link failure, interference, 1923 etc. can occur, implementations SHOULD avoid IPv4 fragmentation/ 1924 reassembly whenever possible, by splitting large TBRPF protocol 1925 packets into multiple smaller packets at the application layer. When 1926 fragmentation is unavoidable, senders SHOULD NOT send TBRPF packets 1927 that exceed the minimum reassembly buffer size ([4], section 3.3.2) 1928 for all receivers in the network. 1930 10.7.2 IPv6 Operation 1932 The specification of TBRPF for IPv6 is the same as for IPv4, except 1933 that 32-bit IPv4 addresses are replaced by 128-bit IPv6 addresses. 1934 However, to minimize overhead, router IDs remain at 32 bits, similar 1935 to OSPF for IPv6 [18]. 1937 11. IANA Considerations 1939 A UDP port number for TBRPF is requested. 1941 The TBRPF flooding mechanism specified in this document uses the IPv4 1942 multicast address 224.0.1.20, which is currently assigned by IANA for 1943 "any private experiment". In the event that this specification is 1944 advanced to standards track, a new multicast address assignment would 1945 be requested for this purpose. 1947 12. Security Considerations 1949 Wireless networks are vulnerable to a variety of attacks, including 1950 denial-of-service attacks (e.g., flooding and jamming), 1951 man-in-the-middle attacks (e.g., interception, insertion, deletion, 1952 modification, replaying) and service theft. To counter such attacks, 1953 it is important to prevent the spoofing (impersonation) of TBRPF 1954 nodes, and to prevent unauthorized nodes from joining the network via 1955 neighbor discovery. To achieve this, TBRPF packets can be 1956 authenticated using the IP Authentication Header [19][20]. In 1957 addition, the Encapsulating Security Payload (ESP) header [21] can be 1958 used to provide confidentiality (encryption) of TBRPF packets. 1960 The IETF SEcuring Neighbor Discovery (SEND) Working Group analyzes 1961 trust models and threats for ad hoc networks [22]. TBRPF can be 1962 extended in a straightforward manner to use SEND mechanisms, e.g., 1963 [23]. 1965 13. Acknowledgements 1967 The authors would like to thank the Army Systems Engineering Office 1968 (ASEO) for funding part of this work. 1970 The authors would like to thank several members of the MANET working 1971 group for many helpful comments and suggestions, including Thomas 1972 Clausen, Philippe Jacquet, and Joe Macker. 1974 The authors would like to thank Bhargav Bellur for major 1975 contributions to the original (full-topology) version of TBRPF, 1976 Ambatipudi Sastry for his support and advice, and Julie S. Wong for 1977 developing a new implementation of TBRPF and suggesting several 1978 clarifications to the TBRPF Routing Operation section. 1980 Normative References 1982 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 1983 Levels", BCP 14, RFC 2119, March 1997. 1985 [2] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) 1986 Specification", RFC 2460, December 1998. 1988 [3] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981. 1990 [4] Braden, R., "Requirements for Internet Hosts - Communication 1991 Layers", STD 3, RFC 1122, October 1989. 1993 [5] Baker, F., "Requirements for IP Version 4 Routers", RFC 1812, 1994 June 1995. 1996 Informative References 1998 [6] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 2000 [7] Ogier, R., Message in IETF email archive for MANET, 2001 ftp://ftp.ietf.org/ietf-mail-archive/manet/2002-02.mail, 2002 February 2002. 2004 [8] Ogier, R., "Topology Dissemination Based on Reverse-Path 2005 Forwarding (TBRPF): Correctness and Simulation Evaluation, 2006 Technical Report, SRI International", October 2003. 2008 [9] Ogier, R., Message in IETF email archive for MANET, 2009 ftp://ftp.ietf.org/ietf-mail-archive/manet/2002-03.mail, 2010 March 2002. 2012 [10] Ogier, R., "Efficient Routing Protocols for Packet-Radio 2013 Networks Based on Tree Sharing. Proc. Sixth IEEE Intl. Workshop 2014 on Mobile Multimedia Communications (MOMUC'99)", November 1999. 2016 [11] Bellur, B. and R. Ogier, "A Reliable, Efficient Topology 2017 Broadcast Protocol for Dynamic Networks. Proc. IEEE INFOCOM 2018 '99, New York", March 1999. 2020 [12] Jacquet, P., Minet, P., Muhlethaler, P. and N. Rivierre, 2021 "Increasing reliability in cable free radio LANs: Low level 2022 forwarding in HIPERLAN, Wireless Personal Communications", 2023 1996. 2025 [13] Bertsekas, D. and R. Gallager, "Data Networks, Prentice-Hall", 2026 1987. 2028 [14] Perkins, C., Belding-Royer, E. and S. Das, "IP Flooding in Ad 2029 Hoc Mobile Networks (work in progress)", November 2001. 2031 [15] Plummer, D., "Ethernet Address Resolution Protocol: Or 2032 converting network protocol addresses to 48.bit Ethernet 2033 address for transmission on Ethernet hardware", STD 37, RFC 2034 826, November 1982. 2036 [16] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery 2037 for IP Version 6 (IPv6)", RFC 2461, December 1998. 2039 [17] Perkins, C., "IP Mobility Support", RFC 2002, October 1996. 2041 [18] Coltun, R., Ferguson, D. and J. Moy, "OSPF for IPv6", RFC 2740, 2042 December 1999. 2044 [19] Kent, S. and R. Atkinson, "Security Architecture for the 2045 Internet Protocol", RFC 2401, November 1998. 2047 [20] Kent, S. and R. Atkinson, "IP Authentication Header", RFC 2402, 2048 November 1998. 2050 [21] Kent, S. and R. Atkinson, "IP Encapsulating Security Payload 2051 (ESP)", RFC 2406, November 1998. 2053 [22] Nikander, P., "IPv6 Neighbor Discovery trust models and 2054 threats", draft-ietf-send-psreq-03 (work in progress), April 2055 2003. 2057 [23] Arkko, J., "SEcure Neighbor Discovery (SEND)", 2058 draft-ietf-send-ipsec-01 (work in progress), June 2003. 2060 Authors' Addresses 2062 Richard G. Ogier 2063 SRI International 2064 333 Ravenswood Ave. 2065 Menlo Park, CA 94025 2066 USA 2068 Phone: +1 650 859-4216 2069 Fax: +1 650 859-4812 2070 EMail: ogier@erg.sri.com 2071 Fred L. Templin 2072 Nokia 2073 313 Fairchild Drive 2074 Mountain View, CA 94043 2075 USA 2077 Phone: +1 650 625 2331 2078 Fax: +1 650 625 2502 2079 EMail: ftemplin@iprg.nokia.com 2081 Mark G. Lewis 2082 SRI International 2083 333 Ravenswood Ave. 2084 Menlo Park, CA 94025 2085 USA 2087 Phone: +1 650 859-4302 2088 Fax: +1 650 859-4812 2089 EMail: lewis@erg.sri.com 2091 Appendix A. Major Changes 2093 Changes from version 10 to version 11: 2095 o Modified the Applicability Section to give references for 2096 simulation results and correctness proof. 2098 o Modified the definition of router ID so that it need not be equal 2099 to the IP address of one of the node's interfaces. 2101 o Modified the definition of a link to clarify that it is an 2102 *ordered* pair (I,J) of interfaces. 2104 Intellectual Property Statement 2106 The IETF takes no position regarding the validity or scope of any 2107 intellectual property or other rights that might be claimed to 2108 pertain to the implementation or use of the technology described in 2109 this document or the extent to which any license under such rights 2110 might or might not be available; neither does it represent that it 2111 has made any effort to identify any such rights. Information on the 2112 IETF's procedures with respect to rights in standards-track and 2113 standards-related documentation can be found in BCP-11. Copies of 2114 claims of rights made available for publication and any assurances of 2115 licenses to be made available, or the result of an attempt made to 2116 obtain a general license or permission for the use of such 2117 proprietary rights by implementors or users of this specification can 2118 be obtained from the IETF Secretariat. 2120 The IETF invites any interested party to bring to its attention any 2121 copyrights, patents or patent applications, or other proprietary 2122 rights which may cover technology that may be required to practice 2123 this standard. Please address the information to the IETF Executive 2124 Director. 2126 The IETF has been notified of intellectual property rights claimed in 2127 regard to some or all of the specification contained in this 2128 document. For more information consult the online list of claimed 2129 rights. 2131 Full Copyright Statement 2133 Copyright (C) The Internet Society (2003). All Rights Reserved. 2135 This document and translations of it may be copied and furnished to 2136 others, and derivative works that comment on or otherwise explain it 2137 or assist in its implementation may be prepared, copied, published 2138 and distributed, in whole or in part, without restriction of any 2139 kind, provided that the above copyright notice and this paragraph are 2140 included on all such copies and derivative works. However, this 2141 document itself may not be modified in any way, such as by removing 2142 the copyright notice or references to the Internet Society or other 2143 Internet organizations, except as needed for the purpose of 2144 developing Internet standards in which case the procedures for 2145 copyrights defined in the Internet Standards process must be 2146 followed, or as required to translate it into languages other than 2147 English. 2149 The limited permissions granted above are perpetual and will not be 2150 revoked by the Internet Society or its successors or assignees. 2152 This document and the information contained herein is provided on an 2153 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 2154 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 2155 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 2156 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 2157 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2159 Acknowledgment 2161 Funding for the RFC Editor function is currently provided by the 2162 Internet Society.