idnits 2.17.1 draft-ietf-manet-tora-spec-04.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: ---------------------------------------------------------------------------- ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 4 instances of too long lines in the document, the longest one being 2 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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 (20 July 2001) is 7872 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) == Unused Reference: '4' is defined on line 1045, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- No information found for draft-ietf- - is the name correct? -- Possible downref: Normative reference to a draft: ref. '4' Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF MANET Working Group V. Park 3 INTERNET-DRAFT S. Corson 4 draft-ietf-manet-tora-spec-04.txt Flarion Technologies, Inc. 5 20 July 2001 7 Temporally-Ordered Routing Algorithm (TORA) Version 1 8 Functional Specification 10 Status of this Memo 12 This document is an Internet-Draft and is subject to all provisions 13 of Section 10 of RFC2026. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that other 17 groups may also distribute working documents as Internet-Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months 20 and may be updated, replaced, or obsoleted by other documents at any 21 time. It is inappropriate to use Internet-Drafts as reference 22 material or to cite them other than as "work in progress." 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt. 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 30 Abstract 32 This document provides both a functional description and a detailed 33 specification of the Temporally-Ordered Routing Algorithm (TORA)--a 34 distributed routing protocol for multihop networks. A key concept in 35 the protocol's design is an attempt to de-couple the generation of 36 far-reaching control message propagation from the dynamics of the 37 network topology. The basic, underlying algorithm is neither 38 distance-vector nor link-state; it is a member of a class referred to 39 as link-reversal algorithms. The protocol builds a loop-free, 40 multipath routing structure that is used as the basis for forwarding 41 traffic to a given destination. The protocol can simultaneously 42 support both source-initiated, on-demand routing for some 43 destinations and destination-initiated, proactive routing for other 44 destinations. 46 1 Introduction 48 The Temporally-Ordered Routing Algorithm (TORA) [1] is an adaptive 49 routing protocol for multihop networks that possesses the following 50 attributes: 51 * Distributed execution, 52 * Loop-free routing, 53 * Multipath routing, 54 * Reactive or proactive route establishment and maintenance, and 55 * Minimization of communication overhead via localization of 56 algorithmic reaction to topological changes. 57 TORA is distributed, in that routers need only maintain information 58 about adjacent routers (i.e., one-hop knowledge). Like a distance- 59 vector routing approach, TORA maintains state on a per-destination 60 basis. However, TORA does not continuously execute a shortest-path 61 computation and thus the metric used to establish the routing 62 structure does not represent a distance. The destination-oriented 63 nature of the routing structure in TORA supports a mix of reactive 64 and proactive routing on a per-destination basis. During reactive 65 operation, sources initiate the establishment of routes to a given 66 destination on-demand. This mode of operation may be advantageous in 67 dynamic networks with relatively sparse traffic patterns, since it 68 may not be necessary (nor desirable) to maintain routes between every 69 source/destination pair at all times. At the same time, selected 70 destinations can initiate proactive operation, resembling traditional 71 table-driven routing approaches. This allows routes to be proactively 72 maintained to destinations for which routing is consistently or 73 frequently required (e.g., servers or gateways to hardwired 74 infrastructure). 76 TORA is designed to minimize the communication overhead associated 77 with adapting to network topological changes. The scope of TORA's 78 control messaging is typically localized to a very small set of nodes 79 near a topological change. A secondary mechanism, which is 80 independent of network topology dynamics, is used as a means of route 81 optimization and soft-state route verification. The design and 82 flexability of TORA allow its operation to be biased towards high 83 reactivity (i.e., low time complexity) and bandwidth conservation 84 (i.e., low communication complexity) rather than routing 85 optimality--making it potentially well-suited for use in dynamic 86 wireless networks. 88 2 Terminology 90 MANET router or router: 91 A device--identified by a "unique Router ID" (RID)--that executes 92 a MANET routing protocol and, under the direction of which, 93 forwards IP packets. It may have multiple interfaces, each 94 identified by an IP address. Associated with each interface is a 95 physical layer communication device. These devices may employ 96 wireless or hardwired communications, and a router may 97 simultaneously employ devices of differing technologies. For 98 example, a MANET router may have four interfaces with differing 99 communications technologies: two hardwired (Ethernet and FDDI) and 100 two wireless (spread spectrum and impulse radio). 102 adjacency: 103 The name given to an "interface on a neighboring router". 105 medium: 106 A communication channel such as free space, cable or fiber through 107 which connections are established. 109 communications technology: 110 The means employed by two devices to transfer information between 111 them. 113 connection: 114 A physical-layer connection--which may be through a wired or 115 wireless medium--between a device attached to an interface of one 116 MANET router and a device utilizing the same communications 117 technology attached to an interface on another MANET router. From 118 the perspective of a given router, a connection is a (interface, 119 adjacency) pair. 121 link: 122 A "logical connection" consisting of the logical *union* of one or 123 more connections between two MANET routers. Thus, a link may 124 consist of a heterogeneous combination of connections through 125 differing media using different communications technologies. 127 neighbor: 128 From the perspective of a given MANET router, a "neighbor" is any 129 other router to which it is connected by a link. 131 topology: 132 A network can be viewed abstractly as a "graph" whose "topology" 133 at any point in time is defined by set of "points" connected by 134 "edges." This term comes from the branch of mathematics bearing 135 the same name that is concerned with those properties of geometric 136 configurations (such as point sets) which are unaltered by elastic 137 deformations (such as stretching) that are homeomorphisms. 139 physical-layer topology: 140 A topology consisting of connections (the edges) through the 141 *same* communications medium between devices (the points) 142 communicating using the *same* communications technology. 144 network-layer topology: 145 A topology consisting of links (the edges) between MANET routers 146 (the points) which is used as the basis for MANET routing. Since 147 "links" are the logical union of physical-layer "connections," it 148 follows that the "network-layer topology" is the logical union of 149 the various "physical-layer topologies." 151 IP routing fabric: 152 The heterogeneous mixture of communications media and technologies 153 through which IP packets are forwarded whose topology is defined 154 by the network-layer topology. 156 3 Protocol Functional Description 158 This section is intended to provide an overview of the protocol and 159 insight into its operation. The protocol specification provided in a 160 subsequent section is intended to serve as the basis for protocol 161 implementations. Thus, in the case of any discrepancies between the 162 description in this section and the subsequent specification section, 163 the specification section should be considered more athoritative. 165 TORA has been designed to work on top of lower layer mechanisms or 166 protocols that provide the following basic services between 167 neighboring routers: 168 * Link status sensing and neighbor discovery 169 * Reliable, in-order control packet delivery 170 * Link and network layer address resolution and mapping 171 * Security authentication 172 Events such as the reception of control messages and changes in 173 connectivity with neighboring routers trigger TORA's algorithmic 174 reactions. 176 A logically separate version of TORA is run for each "destination" to 177 which routing is required. The following discussion focuses on a 178 single version of TORA running for a given destination. The term 179 destination is used herein to refer to a traditional IP routing 180 destination, which is identified by an IP address and mask (or 181 prefix). Thus, the route to a destination may correspond to the 182 individual address of an interface on a specific machine (i.e., a 183 host route) or an aggregation of addresses (i.e., a network route). 185 TORA assigns directions to the links between routers to form a 186 routing structure that is used to forward datagrams to the 187 destination. A router assigns a direction ("upstream" or 188 "downstream") to the link with a neighboring router based on the 189 relative values of a metric associated with each router. The metric 190 maintained by a router can conceptually be thought of as the router's 191 "height" (i.e., links are directed from the higher router to the 192 lower router). The significance of the heights and the link 193 directional assignments is that a router may only forward datagrams 194 downstream. Links from a router to any neighboring routers with an 195 unknown or undefined height are considered undirected and cannot be 196 used for forwarding. Collectively, the heights of the routers and the 197 link directional assignments form a loop-free, multipath routing 198 structure in which all directed paths lead downstream to the 199 destination, see Figure 1. Note that in this example, C is closer to 200 the destination than B in terms of number of hops, but the height 201 metric of C is greater than that of B. 203 .-----. .-----. .-----. 204 | A |---->| B |<----| C | Relative height of the routers 205 `-----' `-----' `-----' ------------------------------ 206 ^ | | 207 | | | H(C) > H(B) > H(E) > H(DEST) 208 | | | 209 | v v H(D) > H(A) > H(B) > H(E) > H(DEST) 210 .-----. .-----. .-----. 211 | D |---->| E |---->| DEST| 212 `-----' `-----' `-----' 214 Figure 1: Conceptual representation of the directed acyclic 215 graph defined by the relative height of network routers. 217 TORA can be separated into four basic functions: creating routes, 218 maintaining routes, erasing routes, and optimizing routes. Creating 219 routes corresponds to the selection of heights to form a directed 220 sequence of links leading to the destination in a previously 221 undirected network or portion of the network. Maintaining routes 222 refers to the adapting the routing structure in response to network 223 topological changes. For example, following the loss of some router's 224 last downstream link, some directed paths may temporarily no longer 225 lead to the destination. This event triggers a sequence of directed 226 link reversals (caused by the re-selection of router heights), which 227 re-orients the routing structure such that all directed paths again 228 lead to the destination. In cases where the network becomes 229 partitioned, links in the portion of the network that has become 230 partitioned from the destination must be marked as undirected to 231 erase invalid routes. During this erasing routes process, routers set 232 their heights to null and their adjacent links become undirected. 233 Finally, TORA includes a secondary mechanism for optimizing routes, 234 in which routers re-select their heights in order to improve the 235 routing structure. TORA accomplishes these four functions through the 236 use of four distinct control packets: query (QRY), update (UPD), 237 clear (CLR), and optimization (OPT). 239 3.1 Creating Routes 241 Creating routes can be initiated on-demand by a source or proactively 242 by a destination. In either case, routers select heights with respect 243 to the given destination and assign directions to the links between 244 neighboring routers. 246 In the on-demand mode, creating routes is accomplished via a query- 247 reply mechanism using QRY and UPD packets. A source initiates the 248 process by sending a QRY packet to its neighbors that identifies the 249 destination for which a route is requested. The QRY packet is 250 propagated out from the source (i.e., processed and forwarded by 251 neighboring routers) until it is received by one or more routers that 252 have a trusted route to the destination. As the QRY packet is 253 forwarded, routers set a route-requested flag and discard any 254 subsequent QRY packets received for the same destination. The route- 255 requested flag supresses redundant route requests and reduces the 256 need for subsequent route requests when a destination is temporarily 257 unreachable. Routers that have a trusted route to the destination 258 repsond to the QRY packet by sending an UPD packet to their neighbors 259 that identifies the relevant destination and the height of the router 260 sending the UPD packet. Routers also maintain the time at which an 261 UPD packet was last sent to its neighbors and the time at which links 262 to neighboring routers became active, to reduce redundant replies to 263 a given route request. When a router with the route-requested flag 264 set receives an UPD packet, it sets its height and sends an UPD 265 packet to its neighbors that identifies the relevant destination and 266 the new height of the router sending the UPD packet. Thus, routers in 267 the network select heights for the requested desination, learn of 268 their neighbors heights for the destination and assign link 269 directions based on those heights. To ensure that a route request 270 continues to propagate when the destination was initially 271 unreachable, routers with the route-requested flag set must resend a 272 QRY packet upon activation of a new link (i.e., discovery of a new 273 neighbor). 275 In the proactive mode, the destination initiates the creating routes 276 process by sending an OPT packet that is processed and forwarded by 277 neighboring routers. The OPT packet identifies the destination, the 278 mode of operation for the destination and the height of the router 279 sending the OPT packet. The OPT packet also contains a sequence 280 number used to uniquely identify the packet and ensure that each 281 router processes and forwards a given OPT packet from a destination 282 at most once. As the OPT packet is forwarded, routers set their mode 283 of operation correspondingly, reselect their heights, and send an OPT 284 packet to their neighbors that identifies the relevant destination 285 and the new height of the router sending the UPD packet. 287 3.2 Maintaining Routes 289 Maintaining routes is only performed for nodes that have a height 290 other than NULL. Furthermore, any neighbor's height that is NULL is 291 not used for the computations. A node i is said to have no downstream 292 links if HEIGHT < HT_NEIGH[k] for all non-NULL neighbors k. This will 293 result in one of five possible reactions depending on the state of 294 the node and the preceding event. Each node (other than the 295 destination) that has no downstream links modifies its height, HEIGHT 296 = (tau[i], oid[i], r[i], delta[i], i), as follows: 298 Case 1 (Generate): 300 Node i has no downstream links (due to a link failure). 302 (tau[i], oid[i], r[i])=(t, i, 0), where t is the time of the 303 failure. 305 (delta[i],i)=(0, i) 307 In essence, node i defines a new reference level. The above 308 assumes node i has at least one upstream neighbor. If node i 309 has no upstream neighbors it simply sets its height to NULL. 311 Case 2 (Propagate): 313 Node i has no downstream links (due to a link reversal 314 following reception of an UPD packet) and the ordered sets 315 (tau[k], oid[k], r[k]) are not equal for all neighbors k. 317 (tau[i], oid[i], r[i])=max{(t[k], oid[k], r[k]) of all 318 neighbors k} 320 (delta[i],i)=(delta[m]-1, i), where m is the lowest neighbor 321 with the maximum reference level defined above. 323 In essence, node i propagates the reference level of its 324 highest neighbor and selects a height that is lower than all 325 neighbors with that reference level. 327 Case 3 (Reflect): 329 Node i has no downstream links (due to a link reversal 330 following reception of an UPD packet) and the ordered sets 331 (tau[k], oid[k], r[k]) are equal with r[k] = 0 for all 332 neighbors k. 334 (tau[i], oid[i], r[i])=(tau[k], oid[k], 1) 336 (delta[i],i)=(0, i) 338 In essence, the same level (which has not been "reflected") has 339 propagated to node i from all of its neighbors. Node i 340 "reflects" back a higher sub-level by setting the bit r. 342 Case 4 (Detect): 344 Node i has no downstream links (due to a link reversal 345 following reception of an UPD packet), the ordered sets 346 (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all 347 neighbors k, and oid[k] = i (i.e., node i defined the level). 349 (tau[i], oid[i], r[i])=(-, -, -) 351 (delta[i],i)=(-, i) 353 In essence, the last reference level defined by node i has been 354 reflected and propagated back as a higher sub-level from all of 355 its neighbors. This corresponds to detection of a partition. 356 Node i must initiate the process of erasing invalid routes as 357 discussed in the next section. 359 Case 5 (Generate): 361 Node i has no downstream links (due to a link reversal 362 following reception of an UPD packet), the ordered sets 363 (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all 364 neighbors k, and oid[k] != i (i.e., node i did not define the 365 level). 367 (tau[i], oid[i], r[i])=(t, i, 0), where t is the time of the 368 failure 370 (delta[i],i)=(0, i) 372 In essence, node i experienced a link failure (which did not 373 require reaction) between the time it propagated a reference 374 level and the reflected higher sub-level returned from all 375 neighbors. This is not necessarily an indication of a 376 partition. Node i defines a new reference level. 378 Following determination of its new height in cases 1, 2, 3, and 5, 379 node i updates all the entries in its link-status table; and 380 broadcasts an UPD packet to all neighbors k. The UPD packet consists 381 of the destination-ID, j, and the new height of the node i that is 382 broadcasting the packet, HEIGHT. When a node i receives an UPD packet 383 from a neighbor k, node i reacts as described in the creating routes 384 section and in accordance with the cases outlined above. In the event 385 of the failure a link (i, k) that is not its last downstream link, 386 node i simply removes the entries HT_NEIGH[k] and LNK_STAT[k] in its 387 height and link-status tables. 389 3.3 Erasing Routes 391 Following detection of a partition (case 4), node i sets its height 392 and the height entry for each neighbor k to NULL (unless the 393 destination j is a neighbor, in which case the corresponding height 394 entry is set to ZERO), updates all the entries in its link-status 395 table, and broadcast a CLR packet. The CLR packet consists of the 396 destination-ID, j, and the reflected reference level of node i, 397 (tau[i], oid[i], 1). In actuality the value r[i] = 1 need not be 398 included since it is always 1 for a reflected reference level. When a 399 node i receives a CLR packet from a neighbor k it reacts as follows: 401 a) If the reference level in the CLR packet matches the reference 402 level of node i; it sets its height and the height entry for each 403 neighbor k to NULL (unless the destination j is a neighbor, in 404 which case the corresponding height entry is set to ZERO), updates 405 all the entries in its link-status table and broadcasts a CLR 406 packet. 408 b) If the reference level in the CLR packet does not match the 409 reference level of node i; it sets the height entry for each 410 neighbor k (with the same reference level as the CLR packet) to 411 NULL and updates the corresponding link-status table entries. 412 Thus, the height of each node in the portion of the network that 413 was partitioned is set to NULL and all invalid routes are erased. 414 If (b) causes node i to lose its last downstream link, it reacts 415 as in case 1 of maintaining routes. 417 3.4 Optimizing Routes 419 TBD. 421 4 Protocol Specification 423 The subsequent specification is intended to be of sufficient detail 424 to serve as a template for implementations. 426 4.1 Configuration 428 A router is configured with a router ID (RID), which must be unique 429 among the set of routers collectively running TORA within a routing 430 domain. This value may correspond to one of the router's IP 431 addresses. 433 For each interface "i" of a router, the following parameters must be 434 configured. 436 IP_ADDR[i] IP address of interface. 437 ADDR_MASK[i] Address mask of interface. 438 PRO_MODE[i] Indicates reactive/proactive mode of operation. 439 OPT_MODE[i] Indicates optimization mode of operation. 440 OPT_PERIOD[i] Period for optimization mechanism. 442 For each interface, a network route corresponding to the address and 443 mask of the interface may be added to the routing table. 444 Additionally, TORA may respond to requests (i.e., QRY packets) for 445 routes to destination addresses that match the set of addresses 446 identified by the interface configurations. PRO_MODE[i] (0=OFF, 1=ON) 447 indicates if routes to the destination identified by the 448 corresponding interface address and mask should be created 449 proactively. OPT_MODE[i] (00=OFF, 01=PARTIAL, 10=FULL, 11=reserved 450 for future use) indicates the type (if any) of optimizations that 451 should be used for the destination identified by the corresponding 452 interface address and mask, while the OPT_PERIOD[i] sets the 453 frequency at which the optimizations will occur. 455 4.2 State Variables 457 A router maintains the state of the configuration parameters outlined 458 above. In addition, for each interface a router maintains a sequence 459 number that is incremented upon changes to the interface mode of 460 operation. 462 MODE_SEQ[i] Sequence number associated with mode of interface "i". 464 For each destination "j", a router maintains the following state 465 variables. 467 HEIGHT[j] This router's height metric for routing to "j". 468 MODE_SEQ[j] Sequence number of most recent mode for "j". 469 PRO_MODE[j] Indicates reactive/proactive mode of operation for "j". 470 OPT_MODE[j] Indicates optimization mode of operation for "j". 471 OPT_PERIOD[j] Indicates optimization period for "j". 472 RT_REQ[j] Indicates whether a route request to "j" is pending. 473 TIME_UPD[j] Time last UPD packet regarding "j" sent by this router. 475 For each destination "j", a router maintains a separate instance of 476 the following state variables for each neighbor "k". 478 HT_NEIGH[j][k] The height metric of neighbor "k." 479 LNK_STAT[j][k] The assigned status of the link to neighbor "k." 480 TIME_ACT[j][k] Time the link to neighbor "k" became active. 482 4.3 Auxiliary Variables 484 For each destination "j" to which routing is required, a router may 485 maintain the following auxiliary variables. Although each of the 486 variables can be computed based on the entries in the LNK_STAT table, 487 maintaining the values continuously may facilitate implementation of 488 the protocol. Whether these variables are maintained continuously or 489 computed when needed is implementation specific. 491 NUM_ACTIVE[j] Number of neighbors (i.e., active links). 492 NUM_DOWN[j] Number of links marked DN in the LNK_STAT table. 493 NUM_UP[j] Number of links marked UP in the LNK_STAT table. 495 4.4 Height Data Structure 497 Each HEIGHT[j] and HT_NEIGH[j][k] entry requires a data structure 498 that comprises five components. The first three components of the 499 Height data structure represent the reference level of the height 500 entry, while the last two components represent an offset with respect 501 to the reference level. The five components of the Height data 502 structure are as follows. 504 HEIGHT.tau Time the reference level was created. 505 HEIGHT.oid Unique id of the router that created the reference level. 506 HEIGHT.r Flag indicating if it is a reflected reference level. 507 HEIGHT.delta Value used in propagation of a reference level. 508 HEIGHT.id Unique id of the router to which the height metric refers. 510 To simplify notation in this specification, a height may be written 511 as an ordered quintuple--e.g., HEIGHT[j]=(tau,oid,r,delta,id). The 512 following two predefined values for a height are used throughout the 513 specification of the protocol. 515 NULL=(-,-,-,-,id) An unknown or undefined height. Conceptually, 516 this can be thought of as an infinite height. 518 ZERO=(0,0,0,0,id) The assumed height of a given destination. Note 519 that here "id" is the unique id of the given 520 destination. 522 4.5 Determination of Link Status 524 Each entry in the LNK_STAT table is maintained in accordance with the 525 following rule. 527 if HT_NEIGH[k]==NULL then LNK_STAT[k]=UN; 528 else if HEIGHT==NULL then LNK_STAT[k]=DN; 529 else if HT_NEIGH[k]HEIGHT then LNK_STAT[k]=UP; 532 4.6 TORA Packet Formats 534 4.6.1 Query (QRY) Packet Format 536 0 1 2 3 537 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 538 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 539 | Version # | Type | Reserved | 540 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 541 | Destination IP Address | 542 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 544 Version # 545 The TORA version number. This specification documents version 1. 547 Type 548 The TORA packet type. For QRY packet this field is set to 1. 550 Reserved 551 Field reserved for future use. 553 Destination IP Address 554 The IP address for which a route is being requested. 556 4.6.2 Update (UPD) Packet Format 558 0 1 2 3 559 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 560 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 561 | Version # | Type | Reserved | 562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 563 | Destination IP Address | 564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 | Destination IP Address Mask | 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 567 | Mode Sequence # | 568 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 569 | Mode | Optimization Period | 570 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 571 | H.tau | 572 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 573 | H.oid | 574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 575 | H.r | H.delta | 576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 577 | H.id | 578 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 580 Version # 581 The TORA version number. This specification documents version 1. 583 Type 584 The TORA packet type. For UPD packet this field is set to 2. 586 Reserved 587 Field reserved for future use. 589 Destination IP Address 590 The IP address for which a route is being requested. 592 Destination IP Address Mask 593 The network mask associated with the destination IP address. 595 Mode Sequence # 596 Sequence number associated with the subsequent mode and 597 optimization period fields. Used for propagation of most recent 598 mode state and to ensure each router processes mode information at 599 most once. 601 Mode 602 The mode of operation associated with the destination IP address 603 and mask. This field is used to indicate reactive/proactive 604 routing and also the type (if any) of optimizations used for the 605 destination. 607 Optimization Period 608 The period for optimization packets originated by the destination. 610 H.tau 611 The H.tau value, associated with the destination IP address and 612 mask, of the router sending the UPD. 614 H.oid 615 The H.oid value, associated with the destination IP address and 616 mask, of the router sending the UPD. 618 H.r 619 The H.r value, associated with the destination IP address and 620 mask, of the router sending the UPD. 622 H.delta 623 The H.delta value, associated with the destination IP address and 624 mask, of the router sending the UPD. 626 H.id 627 The H.id value, associated with the destination IP address and 628 mask, of the router sending the UPD (i.e., unique router ID). 630 4.6.3 Clear (CLR) Packet Format 632 0 1 2 3 633 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 634 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 635 | Version # | Type | Reserved | 636 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 637 | Destination IP Address | 638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 639 | Destination IP Address Mask | 640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 641 | H.tau | 642 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 643 | H.oid | 644 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 645 | H.id | 646 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 648 Version # 649 The TORA version number. This specification documents version 1. 651 Type 652 The TORA packet type. For CLR packet this field is set to 3. 654 Reserved 655 Field reserved for future use. 657 Destination IP Address 658 The IP address for which a route is being requested. 660 Destination IP Address Mask 661 The network mask associated with the destination IP address. 663 H.tau 664 The H.tau value, associated with the destination IP address and 665 mask, of the router sending the UPD. 667 H.oid 668 The H.oid value, associated with the destination IP address and 669 mask, of the router sending the UPD. 671 H.id 672 The H.id value, associated with the destination IP address and 673 mask, of the router sending the UPD (i.e., unique router ID). 675 4.6.4 Optimization (OPT) Packet Format 677 0 1 2 3 678 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 679 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 680 | Version # | Type | Reserved | 681 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 682 | Destination IP Address | 683 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 684 | Destination IP Address Mask | 685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 686 | Mode Sequence # | 687 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 688 | Mode | Optimization Period | 689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 690 | H.tau | 691 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 692 | H.oid | 693 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 694 | H.r | H.delta | 695 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 696 | H.id | 697 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 699 Version # 700 The TORA version number. This specification documents version 1. 702 Type 703 The TORA packet type. For OPT packet this field is set to 4. 705 Reserved 706 Field reserved for future use. 708 Destination IP Address 709 The IP address for which a route is being requested. 711 Destination IP Address Mask 712 The network mask associated with the destination IP address. 714 Mode Sequence # 715 Sequence number associated with the subsequent mode and 716 optimization period fields. Used for propagation of most recent 717 mode state and to ensure each router processes mode information at 718 most once. 720 Mode 721 The mode of operation associated with the destination IP address 722 and mask. This field is used to indicate reactive/proactive 723 routing and also the type (if any) of optimizations used for the 724 destination. 726 Optimization Period 727 The period for optimization packets originated by the destination. 729 H.tau 730 The H.tau value, associated with the destination IP address and 731 mask, of the router sending the UPD. 733 H.oid 734 The H.oid value, associated with the destination IP address and 735 mask, of the router sending the UPD. 737 H.r 738 The H.r value, associated with the destination IP address and 739 mask, of the router sending the UPD. 741 H.delta 742 The H.delta value, associated with the destination IP address and 743 mask, of the router sending the UPD. 745 H.id 746 The H.id value, associated with the destination IP address and 747 mask, of the router sending the UPD (i.e., unique router ID). 749 4.7 Event Processing 751 4.7.1 Initialization 753 TBD 755 4.7.2 Connection Status Change 757 The TORA process receives notification of link status changes from 758 lower layer mechanisms or protocols. It is anticipated that the TORA 759 process will have access to all the information about the 760 connections. Thus, upon notification, TORA will have sufficient 761 information to determine if any new links have been established or 762 any existing links have been severed. If either is the case, then 763 TORA must proceed as outlined in appropriate subsequent section 764 (4.7.3 or 4.7.4). In addition, since a link is potientially composed 765 of multiple connections, it is also possible for a connection that 766 was used in the routing table to be severed without resulting in the 767 corresponding link being severed. In this case TORA must modify the 768 appropriate routing table entries. 770 4.7.3 Link with a New Neighbor "k" Established 772 For each destination "j": 774 Set TIME_ACT[j][k] to the current time and increment NUM_ACTIVE[j]. 776 If the neighbor "k" is the destination "j", then set 777 HT_NEIGH[j][k]=ZERO, LNK_STAT[j][k]=DN and increment NUM_DOWN[j], 778 else set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN. 780 If the RT_REQ[j] flag is set && neighbor "k" is the destination "j" 781 then I) else II). 783 I) Set HEIGHT[j]=HT_NEIGH[j][k]. Increment HEIGHT[j].delta. Set 784 HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] 785 for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the 786 current time. Create an UPD packet and place it in the queue to 787 be sent to all neighbors. Event Processing Complete. 789 II) If PRO_MODE==1 and HEIGHT[j]!=NULL then A) else B). 791 A) Set TIME_UPD[j] to the current time. Create an UPD packet 792 and place it in the queue to be sent to all neighbors. If the 793 RT_REQ[j] flag is set, create a QRY packet and place it in the 794 queue to be sent to all neighbors. Event Processing Complete. 796 B) If the RT_REQ[j] flag is set, create a QRY packet and place 797 it in the queue to be sent to all neighbors. Event Processing 798 Complete. 800 4.7.4 Link with Prior Neighbor "k" Severed 802 For each destination "j": 804 Decrement NUM_ACTIVE[j]. If LNK_STAT[j][k]==DN, decrement 805 NUM_DOWN[j]. If LNK_STAT[j][k]==UP, decrement NUM_UP[j]. 807 If NUM_DOWN[j]==0 then I) else II). 809 I) If NUM_ACTIVE[j]==0 then A) else B). 811 A) Set HEIGHT[j]=NULL. Unset the RT_REQ[j] flag. Event 812 Processing Complete. 814 B) If NUM_UP==0 then 1) else 2). 816 1) If HEIGHT[j]==NULL then a) else b). 818 a) Event Processing Complete. 820 b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current 821 time. Create an UPD packet and place it in the queue to 822 be sent to all neighbors. Event Processing Complete. 824 2) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid 825 to the unique id of this node. Set HEIGHT[j].r=0. Set 826 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of 827 this node. Update LNK_STAT[j][n] for all n. Unset the 828 RT_REQ[j] flag. Set TIME_UPD[j] to the current time. 829 Create an UPD packet and place it in the queue to be sent to 830 all neighbors. Event Processing Complete. 832 II) Event Processing Complete. 834 4.7.5 QRY Packet Regarding Destination "j" Received from Neighbor "k" 836 If the RT_REQ[j] flag is set then I) else II). 838 I) Event Processing Complete. 840 II) If HEIGHT[j].r==0 then A) else B). 842 A) If TIME_ACT[j][k]>TIME_UPD[j] then 1) else 2). 844 1) Set TIME_UPD[j] to the current time. Create an UPD 845 packet and place it in the queue to be sent to all 846 neighbors. Event Processing Complete. 848 2) Event Processing Complete. 850 B) If HT_NEIGH[j][n].r==0 for any n then 1) else 2). 852 1) Find m such that HT_NEIGH[j][m] is the minimum of all 853 height entries with HT_NEIGH[j][n].r==0. Set 854 HEIGHT[j]=HT_NEIGH[j][m]. Increment HEIGHT.delta. Set 855 HEIGHT[j].id to the unique id of this node. Update 856 LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current 857 time. Create an UPD packet and place it in the queue to be 858 sent to all neighbors. Event Processing Complete. 860 2) Set the RT_REQ[j] flag. If NUM_ACTIVE[j]>1 then a) else 861 b). 863 a) Create a QRY packet and place it in the queue to be 864 sent to all neighbors. Event Processing Complete. 866 b) Event Processing Complete. 868 4.7.6 UPD Packet Regarding Destination "j" Received from Neighbor "k" 870 If MODE_SEQ field of received packet is greater than MODE_SEQ[j], 871 update entries PRO_MODE[j], OPT_MODE[j], and MODE_SEQ[j]. 873 Update the entries HT_NEIGH[j][k], and LNK_STAT[j][k]. If the 874 RT_REQ[j] flag is set and HT_NEIGH[j][k].r==0 then I) else II). 876 I) Set HEIGHT[j]=HT_NEIGH[j][k]. Increment HEIGHT.delta. Set 877 HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] 878 for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the 879 current time. Create an UPD packet and place it in the queue to 880 be sent to all neighbors. Event Processing Complete. 882 II) If NUM_DOWN[j]==0 then A) else B). 884 A) If NUM_UP[j]==0 then 1) else 2). 886 1) If HEIGHT[j]==NULL then a) else b). 888 a) Event Processing Complete. 890 b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current 891 time. Create an UPD packet and place it in the queue to 892 be sent to all neighbors. Event Processing Complete. 894 2) If all HT_NEIGH[j][n], for all n such that HT_NEIGH[j][n] 895 is non-NULL, have the same reference level then a) else b). 897 a) If HT_NEIGH[j][n].r==0, for any n such that 898 HT_NEIGH[j][n] is non-NULL, then i) else ii). 900 i) Set HEIGHT[j]=HT_NEIGH[j][n], where n is such that 901 HT_NEIGH[j][n] is non-NULL. Set HEIGHT[j].r=1. Set 902 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id 903 of this node. Update LNK_STAT[j][n] for all n. Set 904 TIME_UPD[j] to the current time. Create an UPD packet 905 and place it in the queue to be sent to all neighbors. 906 Event Processing Complete. 908 ii) If HT_NEIGH[j][n].oid==id, where n is such that 909 HT_NEIGH[j][n] is non-NULL and id is the unique id of 910 this node, then x) else y). 912 x) Save the current values of HEIGHT[j].tau and 913 HEIGHT[j].oid in temporary variables. Set 914 HEIGHT[j]=NULL. Set NUM_DOWN[j]=0. Set 915 NUM_UP[j]=0. For every active link n, if the 916 neighbor connected via link n is the destination j, 917 set HT_NEIGH[j][n]=ZERO and LNK_STAT[j][n]=DN else 918 set HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. 919 Create a CLR packet, with the previously saved 920 values of tau and oid, and place it in the queue to 921 be sent to all neighbors. Event Processing 922 Complete. 924 y) Set HEIGHT[j].tau to the current time. Set 925 HEIGHT[j].oid to the unique id of this node. Set 926 HEIGHT[j].r=0. Set HEIGHT[j].delta=0. Set 927 HEIGHT[j].id to the unique id of this node. Update 928 LNK_STAT[j][n] for all n. Unset the RT_REQ[j] 929 flag. Set TIME_UPD[j] to the current time. Create 930 an UPD packet and place it in the queue to be sent 931 to all neighbors. Event Processing Complete. 933 b) Find n such that HT_NEIGH[j][n] is the maximum of all 934 non-NULL height entries. Find m such that HT_NEIGH[j][m] 935 is the minimum of the non-NULL height entries with the 936 same reference level as HT_NEIGH[j][n]. Set 937 HEIGHT[j]=HT_NEIGH[j][m]. Decrement HEIGHT.delta. Set 938 HEIGHT[j].id to the unique id of this node. Update 939 LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current 940 time. Create an UPD packet and place it in the queue to 941 be sent to all neighbors. Event Processing Complete. 943 B) IF PRO_MODE changed from OFF to ON as a result of this UPD 944 packet reception and HEIGHT[j]==NULL then 1) else 2) 946 1) Find m such that HT_NEIGH[j][m] is the minimum of all 947 non-NULL height entries. Set HEIGHT[j]=HT_NEIGH[j][m]. 948 Increment HEIGHT[j].delta. Set HEIGHT[j].id to the unique 949 id of this node. Update LNK_STAT[j][n] for all n. Set 950 TIME_UPD[j] to the current time. Create an UPD packet and 951 place it in the queue to be sent to all neighbors. Event 952 Processing Complete. 954 2) Event Processing Complete. 956 4.7.7 CLR Packet Regarding Destination "j" Received from Neighbor "k" 958 If HEIGHT[j].tau and HEIGHT[j].oid match the values of tau and oid 959 from the CLR packet and HEIGHT[j].r==1 then I) else II). 961 I) Save the current values of HEIGHT[j].tau and HEIGHT[j].oid in 962 temporary variables. Set Height[j]=NULL. Set NUM_DOWN[j]=0. Set 963 NUM_UP[j]=0. For every active link n, if the neighbor connected 964 via link n is the destination j, set HT_NEIGH[j][n]=ZERO and 965 LNK_STAT[j][n]=DN else set HT_NEIGH[j][n]=NULL and 966 LNK_STAT[j][n]=UN. If NUM_ACTIVE[j]>1 then A) else B). 968 A) Create a CLR packet, with the previously saved values of tau 969 and oid, and place it in the queue to be sent to all neighbors. 970 Event Processing Complete. 972 B) Event Processing Complete. 974 II) Set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN. For all n such 975 that HT_NEIGH[j][n].tau and HT_NEIGH[j][n].oid match the values of 976 tau and oid from the CLR packet and HT_NEIGH[j][n].r==1, set 977 HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. If NUM_DOWN[j]==0 then 978 A) else B). 980 A) If NUM_UP==0 then 1) else 2). 982 1) If HEIGHT[j]==NULL then a) else b). 984 a) Event Processing Complete. 986 b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current 987 time. Create an UPD packet and place it in the queue to 988 be sent to all neighbors. Event Processing Complete. 990 2) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid 991 to the unique id of this node. Set HEIGHT[j].r=0. Set 992 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of 993 this node. Update LNK_STAT[j][n] for all n. Unset the 994 RT_REQ[j] flag. Set TIME_UPD[j] to the current time. 995 Create an UPD packet and place it in the queue to be sent to 996 all neighbors. Event Processing Complete. 998 B) Event Processing Complete. 1000 4.7.8 OPT Packet Regarding Destination "j" Received from Neighbor "k" 1002 If MODE_SEQ field of received packet is greater than MODE_SEQ[j] then 1003 I) else II). 1005 I) Update entries PRO_MODE[j], OPT_MODE[j], and MODE_SEQ[j]. If 1006 PRO_MODE[j] changed as a result of this OPT packet reception || 1007 (OPT_MODE[j]==PARTIAL && HEIGHT[j]!=NULL) || OPT_MODE[j]==FULL 1008 then A) else B). 1010 A) Set HEIGHT[j]=ZERO. Set HEIGHT[j].delta to the value of the 1011 DELTA field in the received OPT packet + 1. Set HEIGHT[j].id 1012 to the unique id of this node. Update LNK_STAT[j][n] for all 1013 n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the current 1014 time. Create an OPT packet and place it in the queue to be 1015 sent to all neighbors. Event Processing Complete. 1017 B) Event Processing Complete. 1019 II) Event Processing Complete. 1021 4.7.9 Mode Configuration Change or Optimization Timer Event for local 1022 interface "i" 1023 Increment MODE_SEQ[i]. Create an OPT packet and place it in the queue 1024 to be sent to all neighbors. If OPT_MODE[i]==PARTIAL || 1025 OPT_MODE[i]==FULL, schedule a local optimization timer event for 1026 interface "i" to occur at a time randomly selected between 1027 0.5*OPT_PERIOD[i] and 1.5*OPT_PERIOD[i] seconds based on a uniform 1028 distribution. Event Processing Complete. 1030 5 Security Considerations 1032 TBD. 1034 6 Intellectual Property Rights Notice 1036 Both the University of Maryland and the U.S. Naval Research 1037 Laboratory have applied for patents relating to the technology 1038 described in this internet draft. 1040 References 1042 [1] V. Park and M. S. Corson, A Highly Adaptive Distributed Routing 1043 Algorithm for Mobile Wireless Networks, Proc. IEEE INFOCOM '97, Kobe, 1044 Japan (1997). 1045 [4] M.S. Corson and V. Park, An Internet MANET Encapsulation Protocol 1046 (IMEP), draft-ietf- 1048 Author's Addresses 1050 Vincent D. Park 1051 park@flarion.com 1052 (908) 947-7084 1054 M. Scott Corson 1055 corson@flarion.com 1056 (908) 947-7033 1057 Flarion Technologies, Inc. 1058 Bedminster One 1059 135 Route 202/206 South 1060 Bedminster, NJ 07921