idnits 2.17.1 draft-ietf-manet-tora-spec-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-25) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. 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 a Security Considerations section. (A line matching the expected section header was found, but with an unexpected indentation: ' 5 Security Considerations' ) ** 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 (24 November 2000) is 8553 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 1041, 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: 6 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 Naval Research Laboratory 4 draft-ietf-manet-tora-spec-03.txt S. Corson 5 University of Maryland 6 24 November 2000 8 Temporally-Ordered Routing Algorithm (TORA) Version 1 9 Functional Specification 11 Status of this Memo 13 This document is an Internet-Draft and is NOT offered in accordance 14 with Section 10 of RFC2026, and the author does not provide the IETF 15 with any rights other than to publish as an Internet-Draft. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that other 19 groups may also distribute working documents as Internet-Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet-Drafts as reference 24 material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt. 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 Abstract 34 This document provides both a functional description and a detailed 35 specification of the Temporally-Ordered Routing Algorithm (TORA)--a 36 distributed routing protocol for multihop networks. A key concept in 37 the protocol's design is an attempt to de-couple the generation of 38 far-reaching control message propagation from the dynamics of the 39 network topology. The basic, underlying algorithm is neither 40 distance-vector nor link-state; it is a member of a class referred to 41 as link-reversal algorithms. The protocol builds a loop-free, 42 multipath routing structure that is used as the basis for forwarding 43 traffic to a given destination. The protocol can simultaneously 44 support both source-initiated, on-demand routing for some 45 destinations and destination-initiated, proactive routing for other 46 destinations. 48 1 Introduction 50 The Temporally-Ordered Routing Algorithm (TORA) [1] is an adaptive 51 routing protocol for multihop networks that possesses the following 52 attributes: 53 * Distributed execution, 54 * Loop-free routing, 55 * Multipath routing, 56 * Reactive or proactive route establishment and maintenance, and 57 * Minimization of communication overhead via localization of 58 algorithmic reaction to topological changes. 59 TORA is distributed, in that routers need only maintain information 60 about adjacent routers (i.e., one-hop knowledge). Like a distance- 61 vector routing approach, TORA maintains state on a per-destination 62 basis. However, TORA does not continuously execute a shortest-path 63 computation and thus the metric used to establish the routing 64 structure does not represent a distance. The destination-oriented 65 nature of the routing structure in TORA supports a mix of reactive 66 and proactive routing on a per-destination basis. During reactive 67 operation, sources initiate the establishment of routes to a given 68 destination on-demand. This mode of operation may be advantageous in 69 dynamic networks with relatively sparse traffic patterns, since it 70 may not be necessary (nor desirable) to maintain routes between every 71 source/destination pair at all times. At the same time, selected 72 destinations can initiate proactive operation, resembling traditional 73 table-driven routing approaches. This allows routes to be proactively 74 maintained to destinations for which routing is consistently or 75 frequently required (e.g., servers or gateways to hardwired 76 infrastructure). 78 TORA is designed to minimize the communication overhead associated 79 with adapting to network topological changes. The scope of TORA's 80 control messaging is typically localized to a very small set of nodes 81 near a topological change. A secondary mechanism, which is 82 independent of network topology dynamics, is used as a means of route 83 optimization and soft-state route verification. The design and 84 flexability of TORA allow its operation to be biased towards high 85 reactivity (i.e., low time complexity) and bandwidth conservation 86 (i.e., low communication complexity) rather than routing 87 optimality--making it potentially well-suited for use in dynamic 88 wireless networks. 90 2 Terminology 92 MANET router or router: 93 A device--identified by a "unique Router ID" (RID)--that executes 94 a MANET routing protocol and, under the direction of which, 95 forwards IP packets. It may have multiple interfaces, each 96 identified by an IP address. Associated with each interface is a 97 physical layer communication device. These devices may employ 98 wireless or hardwired communications, and a router may 99 simultaneously employ devices of differing technologies. For 100 example, a MANET router may have four interfaces with differing 101 communications technologies: two hardwired (Ethernet and FDDI) and 102 two wireless (spread spectrum and impulse radio). 104 adjacency: 105 The name given to an "interface on a neighboring router". 107 medium: 108 A communication channel such as free space, cable or fiber through 109 which connections are established. 111 communications technology: 112 The means employed by two devices to transfer information between 113 them. 115 connection: 116 A physical-layer connection--which may be through a wired or 117 wireless medium--between a device attached to an interface of one 118 MANET router and a device utilizing the same communications 119 technology attached to an interface on another MANET router. From 120 the perspective of a given router, a connection is a (interface, 121 adjacency) pair. 123 link: 124 A "logical connection" consisting of the logical *union* of one or 125 more connections between two MANET routers. Thus, a link may 126 consist of a heterogeneous combination of connections through 127 differing media using different communications technologies. 129 neighbor: 130 From the perspective of a given MANET router, a "neighbor" is any 131 other router to which it is connected by a link. 133 topology: 134 A network can be viewed abstractly as a "graph" whose "topology" 135 at any point in time is defined by set of "points" connected by 136 "edges." This term comes from the branch of mathematics bearing 137 the same name that is concerned with those properties of geometric 138 configurations (such as point sets) which are unaltered by elastic 139 deformations (such as stretching) that are homeomorphisms. 141 physical-layer topology: 142 A topology consisting of connections (the edges) through the 143 *same* communications medium between devices (the points) 144 communicating using the *same* communications technology. 146 network-layer topology: 147 A topology consisting of links (the edges) between MANET routers 148 (the points) which is used as the basis for MANET routing. Since 149 "links" are the logical union of physical-layer "connections," it 150 follows that the "network-layer topology" is the logical union of 151 the various "physical-layer topologies." 153 IP routing fabric: 154 The heterogeneous mixture of communications media and technologies 155 through which IP packets are forwarded whose topology is defined 156 by the network-layer topology. 158 3 Protocol Functional Description 160 This section is intended to provide an overview of the protocol and 161 insight into its operation. The protocol specification provided in a 162 subsequent section is intended to serve as the basis for protocol 163 implementations. Thus, in the case of any discrepancies between the 164 description in this section and the subsequent specification section, 165 the specification section should be considered more athoritative. 167 TORA has been designed to work on top of lower layer mechanisms or 168 protocols that provide the following basic services between 169 neighboring routers: 170 * Link status sensing and neighbor discovery 171 * Reliable, in-order control packet delivery 172 * Link and network layer address resolution and mapping 173 * Security authentication 174 Events such as the reception of control messages and changes in 175 connectivity with neighboring routers trigger TORA's algorithmic 176 reactions. 178 A logically separate version of TORA is run for each "destination" to 179 which routing is required. The following discussion focuses on a 180 single version of TORA running for a given destination. The term 181 destination is used herein to refer to a traditional IP routing 182 destination, which is identified by an IP address and mask (or 183 prefix). Thus, the route to a destination may correspond to the 184 individual address of an interface on a specific machine (i.e., a 185 host route) or an aggregation of addresses (i.e., a network route). 187 TORA assigns directions to the links between routers to form a 188 routing structure that is used to forward datagrams to the 189 destination. A router assigns a direction ("upstream" or 190 "downstream") to the link with a neighboring router based on the 191 relative values of a metric associated with each router. The metric 192 maintained by a router can conceptually be thought of as the router's 193 "height" (i.e., links are directed from the higher router to the 194 lower router). The significance of the heights and the link 195 directional assignments is that a router may only forward datagrams 196 downstream. Links from a router to any neighboring routers with an 197 unknown or undefined height are considered undirected and cannot be 198 used for forwarding. Collectively, the heights of the routers and the 199 link directional assignments form a loop-free, multipath routing 200 structure in which all directed paths lead downstream to the 201 destination, see Figure 1. Note that in this example, C is closer to 202 the destination than B in terms of number of hops, but the height 203 metric of C is greater than that of B. 205 .-----. .-----. .-----. 206 | A |---->| B |<----| C | Relative height of the routers 207 `-----' `-----' `-----' ------------------------------ 208 ^ | | 209 | | | H(C) > H(B) > H(E) > H(DEST) 210 | | | 211 | v v H(D) > H(A) > H(B) > H(E) > H(DEST) 212 .-----. .-----. .-----. 213 | D |---->| E |---->| DEST| 214 `-----' `-----' `-----' 216 Figure 1: Conceptual representation of the directed acyclic 217 graph defined by the relative height of network routers. 219 TORA can be separated into four basic functions: creating routes, 220 maintaining routes, erasing routes, and optimizing routes. Creating 221 routes corresponds to the selection of heights to form a directed 222 sequence of links leading to the destination in a previously 223 undirected network or portion of the network. Maintaining routes 224 refers to the adapting the routing structure in response to network 225 topological changes. For example, following the loss of some router's 226 last downstream link, some directed paths may temporarily no longer 227 lead to the destination. This event triggers a sequence of directed 228 link reversals (caused by the re-selection of router heights), which 229 re-orients the routing structure such that all directed paths again 230 lead to the destination. In cases where the network becomes 231 partitioned, links in the portion of the network that has become 232 partitioned from the destination must be marked as undirected to 233 erase invalid routes. During this erasing routes process, routers set 234 their heights to null and their adjacent links become undirected. 235 Finally, TORA includes a secondary mechanism for optimizing routes, 236 in which routers re-select their heights in order to improve the 237 routing structure. TORA accomplishes these four functions through the 238 use of four distinct control packets: query (QRY), update (UPD), 239 clear (CLR), and optimization (OPT). 241 3.1 Creating Routes 243 Creating routes can be initiated on-demand by a source or proactively 244 by a destination. In either case, routers select heights with respect 245 to the given destination and assign directions to the links between 246 neighboring routers. 248 In the on-demand mode, creating routes is accomplished via a query- 249 reply mechanism using QRY and UPD packets. A source initiates the 250 process by sending a QRY packet to its neighbors that identifies the 251 destination for which a route is requested. The QRY packet is 252 propagated out from the source (i.e., processed and forwarded by 253 neighboring routers) until it is received by one or more routers that 254 have a trusted route to the destination. As the QRY packet is 255 forwarded, routers set a route-requested flag and discard any 256 subsequent QRY packets received for the same destination. The route- 257 requested flag supresses redundant route requests and reduces the 258 need for subsequent route requests when a destination is temporarily 259 unreachable. Routers that have a trusted route to the destination 260 repsond to the QRY packet by sending an UPD packet to their neighbors 261 that identifies the relevant destination and the height of the router 262 sending the UPD packet. Routers also maintain the time at which an 263 UPD packet was last sent to its neighbors and the time at which links 264 to neighboring routers became active, to reduce redundant replies to 265 a given route request. When a router with the route-requested flag 266 set receives an UPD packet, it sets its height and sends an UPD 267 packet to its neighbors that identifies the relevant destination and 268 the new height of the router sending the UPD packet. Thus, routers in 269 the network select heights for the requested desination, learn of 270 their neighbors heights for the destination and assign link 271 directions based on those heights. To ensure that a route request 272 continues to propagate when the destination was initially 273 unreachable, routers with the route-requested flag set must resend a 274 QRY packet upon activation of a new link (i.e., discovery of a new 275 neighbor). 277 In the proactive mode, the destination initiates the creating routes 278 process by sending an OPT packet that is processed and forwarded by 279 neighboring routers. The OPT packet identifies the destination, the 280 mode of operation for the destination and the height of the router 281 sending the OPT packet. The OPT packet also contains a sequence 282 number used to uniquely identify the packet and ensure that each 283 router processes and forwards a given OPT packet from a destination 284 at most once. As the OPT packet is forwarded, routers set their mode 285 of operation correspondingly, reselect their heights, and send an OPT 286 packet to their neighbors that identifies the relevant destination 287 and the new height of the router sending the UPD packet. 289 3.2 Maintaining Routes 291 Maintaining routes is only performed for nodes that have a height 292 other than NULL. Furthermore, any neighbor's height that is NULL is 293 not used for the computations. A node i is said to have no downstream 294 links if HEIGHT < HT_NEIGH[k] for all non-NULL neighbors k. This will 295 result in one of five possible reactions depending on the state of 296 the node and the preceding event. Each node (other than the 297 destination) that has no downstream links modifies its height, HEIGHT 298 = (tau[i], oid[i], r[i], delta[i], i), as follows: 300 Case 1 (Generate): 302 Node i has no downstream links (due to a link failure). 304 (tau[i], oid[i], r[i])=(t, i, 0), where t is the time of the 305 failure. 307 (delta[i],i)=(0, i) 309 In essence, node i defines a new reference level. The above 310 assumes node i has at least one upstream neighbor. If node i 311 has no upstream neighbors it simply sets its height to NULL. 313 Case 2 (Propagate): 315 Node i has no downstream links (due to a link reversal 316 following reception of an UPD packet) and the ordered sets 317 (tau[k], oid[k], r[k]) are not equal for all neighbors k. 319 (tau[i], oid[i], r[i])=max{(t[k], oid[k], r[k]) of all 320 neighbors k} 322 (delta[i],i)=(delta[m]-1, i), where m is the lowest neighbor 323 with the maximum reference level defined above. 325 In essence, node i propagates the reference level of its 326 highest neighbor and selects a height that is lower than all 327 neighbors with that reference level. 329 Case 3 (Reflect): 331 Node i has no downstream links (due to a link reversal 332 following reception of an UPD packet) and the ordered sets 333 (tau[k], oid[k], r[k]) are equal with r[k] = 0 for all 334 neighbors k. 336 (tau[i], oid[i], r[i])=(tau[k], oid[k], 1) 338 (delta[i],i)=(0, i) 340 In essence, the same level (which has not been "reflected") has 341 propagated to node i from all of its neighbors. Node i 342 "reflects" back a higher sub-level by setting the bit r. 344 Case 4 (Detect): 346 Node i has no downstream links (due to a link reversal 347 following reception of an UPD packet), the ordered sets 348 (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all 349 neighbors k, and oid[k] = i (i.e., node i defined the level). 351 (tau[i], oid[i], r[i])=(-, -, -) 353 (delta[i],i)=(-, i) 355 In essence, the last reference level defined by node i has been 356 reflected and propagated back as a higher sub-level from all of 357 its neighbors. This corresponds to detection of a partition. 358 Node i must initiate the process of erasing invalid routes as 359 discussed in the next section. 361 Case 5 (Generate): 363 Node i has no downstream links (due to a link reversal 364 following reception of an UPD packet), the ordered sets 365 (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all 366 neighbors k, and oid[k] != i (i.e., node i did not define the 367 level). 369 (tau[i], oid[i], r[i])=(t, i, 0), where t is the time of the 370 failure 372 (delta[i],i)=(0, i) 374 In essence, node i experienced a link failure (which did not 375 require reaction) between the time it propagated a reference 376 level and the reflected higher sub-level returned from all 377 neighbors. This is not necessarily an indication of a 378 partition. Node i defines a new reference level. 380 Following determination of its new height in cases 1, 2, 3, and 5, 381 node i updates all the entries in its link-status table; and 382 broadcasts an UPD packet to all neighbors k. The UPD packet consists 383 of the destination-ID, j, and the new height of the node i that is 384 broadcasting the packet, HEIGHT. When a node i receives an UPD packet 385 from a neighbor k, node i reacts as described in the creating routes 386 section and in accordance with the cases outlined above. In the event 387 of the failure a link (i, k) that is not its last downstream link, 388 node i simply removes the entries HT_NEIGH[k] and LNK_STAT[k] in its 389 height and link-status tables. 391 3.3 Erasing Routes 393 Following detection of a partition (case 4), node i sets its height 394 and the height entry for each neighbor k to NULL (unless the 395 destination j is a neighbor, in which case the corresponding height 396 entry is set to ZERO), updates all the entries in its link-status 397 table, and broadcast a CLR packet. The CLR packet consists of the 398 destination-ID, j, and the reflected reference level of node i, 399 (tau[i], oid[i], 1). In actuality the value r[i] = 1 need not be 400 included since it is always 1 for a reflected reference level. When a 401 node i receives a CLR packet from a neighbor k it reacts as follows: 403 a) If the reference level in the CLR packet matches the reference 404 level of node i; it sets its height and the height entry for each 405 neighbor k to NULL (unless the destination j is a neighbor, in 406 which case the corresponding height entry is set to ZERO), updates 407 all the entries in its link-status table and broadcasts a CLR 408 packet. 410 b) If the reference level in the CLR packet does not match the 411 reference level of node i; it sets the height entry for each 412 neighbor k (with the same reference level as the CLR packet) to 413 NULL and updates the corresponding link-status table entries. 414 Thus, the height of each node in the portion of the network that 415 was partitioned is set to NULL and all invalid routes are erased. 416 If (b) causes node i to lose its last downstream link, it reacts 417 as in case 1 of maintaining routes. 419 3.4 Optimizing Routes 421 TBD. 423 4 Protocol Specification 425 The subsequent specification is intended to be of sufficient detail 426 to serve as a template for implementations. 428 4.1 Configuration 430 A router is configured with a router ID (RID), which must be unique 431 among the set of routers collectively running TORA within a routing 432 domain. This value may correspond to one of the router's IP 433 addresses. 435 For each interface "i" of a router, the following parameters must be 436 configured. 438 IP_ADDR[i] IP address of interface. 439 ADDR_MASK[i] Address mask of interface. 440 PRO_MODE[i] Indicates reactive/proactive mode of operation. 441 OPT_MODE[i] Indicates optimization mode of operation. 442 OPT_PERIOD[i] Period for optimization mechanism. 444 For each interface, a network route corresponding to the address and 445 mask of the interface may be added to the routing table. 446 Additionally, TORA may respond to requests (i.e., QRY packets) for 447 routes to destination addresses that match the set of addresses 448 identified by the interface configurations. PRO_MODE[i] (0=OFF, 1=ON) 449 indicates if routes to the destination identified by the 450 corresponding interface address and mask should be created 451 proactively. OPT_MODE[i] (00=OFF, 01=PARTIAL, 10=FULL, 11=reserved 452 for future use) indicates the type (if any) of optimizations that 453 should be used for the destination identified by the corresponding 454 interface address and mask, while the OPT_PERIOD[i] sets the 455 frequency at which the optimizations will occur. 457 4.2 State Variables 459 A router maintains the state of the configuration parameters outlined 460 above. In addition, for each interface a router maintains a sequence 461 number that is incremented upon changes to the interface mode of 462 operation. 464 MODE_SEQ[i] Sequence number associated with mode of interface "i". 466 For each destination "j", a router maintains the following state 467 variables. 469 HEIGHT[j] This router's height metric for routing to "j". 470 MODE_SEQ[j] Sequence number of most recent mode for "j". 471 PRO_MODE[j] Indicates reactive/proactive mode of operation for "j". 472 OPT_MODE[j] Indicates optimization mode of operation for "j". 473 OPT_PERIOD[j] Indicates optimization period for "j". 474 RT_REQ[j] Indicates whether a route request to "j" is pending. 475 TIME_UPD[j] Time last UPD packet regarding "j" sent by this router. 477 For each destination "j", a router maintains a separate instance of 478 the following state variables for each neighbor "k". 480 HT_NEIGH[j][k] The height metric of neighbor "k." 481 LNK_STAT[j][k] The assigned status of the link to neighbor "k." 482 TIME_ACT[j][k] Time the link to neighbor "k" became active. 484 4.3 Auxiliary Variables 486 For each destination "j" to which routing is required, a router may 487 maintain the following auxiliary variables. Although each of the 488 variables can be computed based on the entries in the LNK_STAT table, 489 maintaining the values continuously may facilitate implementation of 490 the protocol. Whether these variables are maintained continuously or 491 computed when needed is implementation specific. 493 NUM_ACTIVE[j] Number of neighbors (i.e., active links). 494 NUM_DOWN[j] Number of links marked DN in the LNK_STAT table. 495 NUM_UP[j] Number of links marked UP in the LNK_STAT table. 497 4.4 Height Data Structure 499 Each HEIGHT[j] and HT_NEIGH[j][k] entry requires a data structure 500 that comprises five components. The first three components of the 501 Height data structure represent the reference level of the height 502 entry, while the last two components represent an offset with respect 503 to the reference level. The five components of the Height data 504 structure are as follows. 506 HEIGHT.tau Time the reference level was created. 507 HEIGHT.oid Unique id of the router that created the reference level. 508 HEIGHT.r Flag indicating if it is a reflected reference level. 509 HEIGHT.delta Value used in propagation of a reference level. 510 HEIGHT.id Unique id of the router to which the height metric refers. 512 To simplify notation in this specification, a height may be written 513 as an ordered quintuple--e.g., HEIGHT[j]=(tau,oid,r,delta,id). The 514 following two predefined values for a height are used throughout the 515 specification of the protocol. 517 NULL=(-,-,-,-,id) An unknown or undefined height. Conceptually, 518 this can be thought of as an infinite height. 520 ZERO=(0,0,0,0,id) The assumed height of a given destination. Note 521 that here "id" is the unique id of the given 522 destination. 524 4.5 Determination of Link Status 526 Each entry in the LNK_STAT table is maintained in accordance with the 527 following rule. 529 if HT_NEIGH[k]==NULL then LNK_STAT[k]=UN; 530 else if HEIGHT==NULL then LNK_STAT[k]=DN; 531 else if HT_NEIGH[k]HEIGHT then LNK_STAT[k]=UP; 534 4.6 TORA Packet Formats 536 4.6.1 Query (QRY) Packet Format 538 0 1 2 3 539 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 540 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 541 | Version # | Type | Reserved | 542 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 543 | Destination IP Address | 544 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 546 Version # 547 The TORA version number. This specification documents version 1. 549 Type 550 The TORA packet type. For QRY packet this field is set to 1. 552 Reserved 553 Field reserved for future use. 555 Destination IP Address 556 The IP address for which a route is being requested. 558 4.6.2 Update (UPD) Packet Format 560 0 1 2 3 561 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 562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 563 | Version # | Type | Reserved | 564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 | Destination IP Address | 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 567 | Destination IP Address Mask | 568 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 569 | Mode Sequence # | 570 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 571 | Mode | Optimization Period | 572 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 573 | H.tau | 574 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 575 | H.oid | 576 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 577 | H.r | H.delta | 578 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 579 | H.id | 580 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 582 Version # 583 The TORA version number. This specification documents version 1. 585 Type 586 The TORA packet type. For UPD packet this field is set to 2. 588 Reserved 589 Field reserved for future use. 591 Destination IP Address 592 The IP address for which a route is being requested. 594 Destination IP Address Mask 595 The network mask associated with the destination IP address. 597 Mode Sequence # 598 Sequence number associated with the subsequent mode and 599 optimization period fields. Used for propagation of most recent 600 mode state and to ensure each router processes mode information at 601 most once. 603 Mode 604 The mode of operation associated with the destination IP address 605 and mask. This field is used to indicate reactive/proactive 606 routing and also the type (if any) of optimizations used for the 607 destination. 609 Optimization Period 610 The period for optimization packets originated by the destination. 612 H.tau 613 The H.tau value, associated with the destination IP address and 614 mask, of the router sending the UPD. 616 H.oid 617 The H.oid value, associated with the destination IP address and 618 mask, of the router sending the UPD. 620 H.r 621 The H.r value, associated with the destination IP address and 622 mask, of the router sending the UPD. 624 H.delta 625 The H.delta value, associated with the destination IP address and 626 mask, of the router sending the UPD. 628 H.id 629 The H.id value, associated with the destination IP address and 630 mask, of the router sending the UPD (i.e., unique router ID). 632 4.6.3 Clear (CLR) Packet Format 634 0 1 2 3 635 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 636 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 637 | Version # | Type | Reserved | 638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 639 | Destination IP Address | 640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 641 | Destination IP Address Mask | 642 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 643 | H.tau | 644 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 645 | H.oid | 646 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 647 | H.id | 648 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 650 Version # 651 The TORA version number. This specification documents version 1. 653 Type 654 The TORA packet type. For CLR packet this field is set to 3. 656 Reserved 657 Field reserved for future use. 659 Destination IP Address 660 The IP address for which a route is being requested. 662 Destination IP Address Mask 663 The network mask associated with the destination IP address. 665 H.tau 666 The H.tau value, associated with the destination IP address and 667 mask, of the router sending the UPD. 669 H.oid 670 The H.oid value, associated with the destination IP address and 671 mask, of the router sending the UPD. 673 H.id 674 The H.id value, associated with the destination IP address and 675 mask, of the router sending the UPD (i.e., unique router ID). 677 4.6.4 Optimization (OPT) Packet Format 679 0 1 2 3 680 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 681 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 682 | Version # | Type | Reserved | 683 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 684 | Destination IP Address | 685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 686 | Destination IP Address Mask | 687 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 688 | Mode Sequence # | 689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 690 | Mode | Optimization Period | 691 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 692 | H.tau | 693 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 694 | H.oid | 695 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 696 | H.r | H.delta | 697 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 698 | H.id | 699 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 701 Version # 702 The TORA version number. This specification documents version 1. 704 Type 705 The TORA packet type. For OPT packet this field is set to 4. 707 Reserved 708 Field reserved for future use. 710 Destination IP Address 711 The IP address for which a route is being requested. 713 Destination IP Address Mask 714 The network mask associated with the destination IP address. 716 Mode Sequence # 717 Sequence number associated with the subsequent mode and 718 optimization period fields. Used for propagation of most recent 719 mode state and to ensure each router processes mode information at 720 most once. 722 Mode 723 The mode of operation associated with the destination IP address 724 and mask. This field is used to indicate reactive/proactive 725 routing and also the type (if any) of optimizations used for the 726 destination. 728 Optimization Period 729 The period for optimization packets originated by the destination. 731 H.tau 732 The H.tau value, associated with the destination IP address and 733 mask, of the router sending the UPD. 735 H.oid 736 The H.oid value, associated with the destination IP address and 737 mask, of the router sending the UPD. 739 H.r 740 The H.r value, associated with the destination IP address and 741 mask, of the router sending the UPD. 743 H.delta 744 The H.delta value, associated with the destination IP address and 745 mask, of the router sending the UPD. 747 H.id 748 The H.id value, associated with the destination IP address and 749 mask, of the router sending the UPD (i.e., unique router ID). 751 4.7 Event Processing 753 4.7.1 Initialization 755 TBD 757 4.7.2 Connection Status Change 759 The TORA process receives notification of link status changes from 760 lower layer mechanisms or protocols. It is anticipated that the TORA 761 process will have access to all the information about the 762 connections. Thus, upon notification, TORA will have sufficient 763 information to determine if any new links have been established or 764 any existing links have been severed. If either is the case, then 765 TORA must proceed as outlined in appropriate subsequent section 766 (4.7.3 or 4.7.4). In addition, since a link is potientially composed 767 of multiple connections, it is also possible for a connection that 768 was used in the routing table to be severed without resulting in the 769 corresponding link being severed. In this case TORA must modify the 770 appropriate routing table entries. 772 4.7.3 Link with a New Neighbor "k" Established 774 For each destination "j": 776 Set TIME_ACT[j][k] to the current time and increment NUM_ACTIVE[j]. 778 If the neighbor "k" is the destination "j", then set 779 HT_NEIGH[j][k]=ZERO, LNK_STAT[j][k]=DN and increment NUM_DOWN[j], 780 else set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN. 782 If the RT_REQ[j] flag is set && neighbor "k" is the destination "j" 783 then I) else II). 785 I) Set HEIGHT[j]=HT_NEIGH[j][k]. Increment HEIGHT[j].delta. Set 786 HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] 787 for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the 788 current time. Create an UPD packet and place it in the queue to 789 be sent to all neighbors. Event Processing Complete. 791 II) If PRO_MODE==1 and HEIGHT[j]!=NULL then A) else B). 793 A) Set TIME_UPD[j] to the current time. Create an UPD packet 794 and place it in the queue to be sent to all neighbors. If the 795 RT_REQ[j] flag is set, create a QRY packet and place it in the 796 queue to be sent to all neighbors. Event Processing Complete. 798 B) If the RT_REQ[j] flag is set, create a QRY packet and place 799 it in the queue to be sent to all neighbors. Event Processing 800 Complete. 802 4.7.4 Link with Prior Neighbor "k" Severed 804 For each destination "j": 806 Decrement NUM_ACTIVE[j]. If LNK_STAT[j][k]==DN, decrement 807 NUM_DOWN[j]. If LNK_STAT[j][k]==UP, decrement NUM_UP[j]. 809 If NUM_DOWN[j]==0 then I) else II). 811 I) If NUM_ACTIVE[j]==0 then A) else B). 813 A) Set HEIGHT[j]=NULL. Unset the RT_REQ[j] flag. Event 814 Processing Complete. 816 B) If NUM_UP==0 then 1) else 2). 818 1) If HEIGHT[j]==NULL then a) else b). 820 a) Event Processing Complete. 822 b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current 823 time. Create an UPD packet and place it in the queue to 824 be sent to all neighbors. Event Processing Complete. 826 2) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid 827 to the unique id of this node. Set HEIGHT[j].r=0. Set 828 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of 829 this node. Update LNK_STAT[j][n] for all n. Unset the 830 RT_REQ[j] flag. Set TIME_UPD[j] to the current time. 831 Create an UPD packet and place it in the queue to be sent to 832 all neighbors. Event Processing Complete. 834 II) Event Processing Complete. 836 4.7.5 QRY Packet Regarding Destination "j" Received from Neighbor "k" 838 If the RT_REQ[j] flag is set then I) else II). 840 I) Event Processing Complete. 842 II) If HEIGHT[j].r==0 then A) else B). 844 A) If TIME_ACT[j][k]>TIME_UPD[j] then 1) else 2). 846 1) Set TIME_UPD[j] to the current time. Create an UPD 847 packet and place it in the queue to be sent to all 848 neighbors. Event Processing Complete. 850 2) Event Processing Complete. 852 B) If HT_NEIGH[j][n].r==0 for any n then 1) else 2). 854 1) Find m such that HT_NEIGH[j][m] is the minimum of all 855 height entries with HT_NEIGH[j][n].r==0. Set 856 HEIGHT[j]=HT_NEIGH[j][m]. Increment HEIGHT.delta. Set 857 HEIGHT[j].id to the unique id of this node. Update 858 LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current 859 time. Create an UPD packet and place it in the queue to be 860 sent to all neighbors. Event Processing Complete. 862 2) Set the RT_REQ[j] flag. If NUM_ACTIVE[j]>1 then a) else 863 b). 865 a) Create a QRY packet and place it in the queue to be 866 sent to all neighbors. Event Processing Complete. 868 b) Event Processing Complete. 870 4.7.6 UPD Packet Regarding Destination "j" Received from Neighbor "k" 872 If MODE_SEQ field of received packet is greater than MODE_SEQ[j], 873 update entries PRO_MODE[j], OPT_MODE[j], and MODE_SEQ[j]. 875 Update the entries HT_NEIGH[j][k], and LNK_STAT[j][k]. If the 876 RT_REQ[j] flag is set and HT_NEIGH[j][k].r==0 then I) else II). 878 I) Set HEIGHT[j]=HT_NEIGH[j][k]. Increment HEIGHT.delta. Set 879 HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] 880 for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the 881 current time. Create an UPD packet and place it in the queue to 882 be sent to all neighbors. Event Processing Complete. 884 II) If NUM_DOWN[j]==0 then A) else B). 886 A) If NUM_UP[j]==0 then 1) else 2). 888 1) If HEIGHT[j]==NULL then a) else b). 890 a) Event Processing Complete. 892 b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current 893 time. Create an UPD packet and place it in the queue to 894 be sent to all neighbors. Event Processing Complete. 896 2) If all HT_NEIGH[j][n], for all n such that HT_NEIGH[j][n] 897 is non-NULL, have the same reference level then a) else b). 899 a) If HT_NEIGH[j][n].r==0, for any n such that 900 HT_NEIGH[j][n] is non-NULL, then i) else ii). 902 i) Set HEIGHT[j]=HT_NEIGH[j][n], where n is such that 903 HT_NEIGH[j][n] is non-NULL. Set HEIGHT[j].r=1. Set 904 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id 905 of this node. Update LNK_STAT[j][n] for all n. Set 906 TIME_UPD[j] to the current time. Create an UPD packet 907 and place it in the queue to be sent to all neighbors. 908 Event Processing Complete. 910 ii) If HT_NEIGH[j][n].oid==id, where n is such that 911 HT_NEIGH[j][n] is non-NULL and id is the unique id of 912 this node, then x) else y). 914 x) Save the current values of HEIGHT[j].tau and 915 HEIGHT[j].oid in temporary variables. Set 916 HEIGHT[j]=NULL. Set NUM_DOWN[j]=0. Set 917 NUM_UP[j]=0. For every active link n, if the 918 neighbor connected via link n is the destination j, 919 set HT_NEIGH[j][n]=ZERO and LNK_STAT[j][n]=DN else 920 set HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. 921 Create a CLR packet, with the previously saved 922 values of tau and oid, and place it in the queue to 923 be sent to all neighbors. Event Processing 924 Complete. 926 y) Set HEIGHT[j].tau to the current time. Set 927 HEIGHT[j].oid to the unique id of this node. Set 928 HEIGHT[j].r=0. Set HEIGHT[j].delta=0. Set 929 HEIGHT[j].id to the unique id of this node. Update 930 LNK_STAT[j][n] for all n. Unset the RT_REQ[j] 931 flag. Set TIME_UPD[j] to the current time. Create 932 an UPD packet and place it in the queue to be sent 933 to all neighbors. Event Processing Complete. 935 b) Find n such that HT_NEIGH[j][n] is the maximum of all 936 non-NULL height entries. Find m such that HT_NEIGH[j][m] 937 is the minimum of the non-NULL height entries with the 938 same reference level as HT_NEIGH[j][n]. Set 939 HEIGHT[j]=HT_NEIGH[j][m]. Decrement HEIGHT.delta. Set 940 HEIGHT[j].id to the unique id of this node. Update 941 LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current 942 time. Create an UPD packet and place it in the queue to 943 be sent to all neighbors. Event Processing Complete. 945 B) IF PRO_MODE changed from OFF to ON as a result of this UPD 946 packet reception and HEIGHT[j]==NULL then 1) else 2) 948 1) Find m such that HT_NEIGH[j][m] is the minimum of all 949 non-NULL height entries. Set HEIGHT[j]=HT_NEIGH[j][m]. 950 Increment HEIGHT[j].delta. Set HEIGHT[j].id to the unique 951 id of this node. Update LNK_STAT[j][n] for all n. Set 952 TIME_UPD[j] to the current time. Create an UPD packet and 953 place it in the queue to be sent to all neighbors. Event 954 Processing Complete. 956 2) Event Processing Complete. 958 4.7.7 CLR Packet Regarding Destination "j" Received from Neighbor "k" 960 If HEIGHT[j].tau and HEIGHT[j].oid match the values of tau and oid 961 from the CLR packet and HEIGHT[j].r==1 then I) else II). 963 I) Save the current values of HEIGHT[j].tau and HEIGHT[j].oid in 964 temporary variables. Set Height[j]=NULL. Set NUM_DOWN[j]=0. Set 965 NUM_UP[j]=0. For every active link n, if the neighbor connected 966 via link n is the destination j, set HT_NEIGH[j][n]=ZERO and 967 LNK_STAT[j][n]=DN else set HT_NEIGH[j][n]=NULL and 968 LNK_STAT[j][n]=UN. If NUM_ACTIVE[j]>1 then A) else B). 970 A) Create a CLR packet, with the previously saved values of tau 971 and oid, and place it in the queue to be sent to all neighbors. 972 Event Processing Complete. 974 B) Event Processing Complete. 976 II) Set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN. For all n such 977 that HT_NEIGH[j][n].tau and HT_NEIGH[j][n].oid match the values of 978 tau and oid from the CLR packet and HT_NEIGH[j][n].r==1, set 979 HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. If NUM_DOWN[j]==0 then 980 A) else B). 982 A) If NUM_UP==0 then 1) else 2). 984 1) If HEIGHT[j]==NULL then a) else b). 986 a) Event Processing Complete. 988 b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current 989 time. Create an UPD packet and place it in the queue to 990 be sent to all neighbors. Event Processing Complete. 992 2) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid 993 to the unique id of this node. Set HEIGHT[j].r=0. Set 994 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of 995 this node. Update LNK_STAT[j][n] for all n. Unset the 996 RT_REQ[j] flag. Set TIME_UPD[j] to the current time. 997 Create an UPD packet and place it in the queue to be sent to 998 all neighbors. Event Processing Complete. 1000 B) Event Processing Complete. 1002 4.7.8 OPT Packet Regarding Destination "j" Received from Neighbor "k" 1004 If MODE_SEQ field of received packet is greater than MODE_SEQ[j] then 1005 I) else II). 1007 I) Update entries PRO_MODE[j], OPT_MODE[j], and MODE_SEQ[j]. If 1008 PRO_MODE[j] changed as a result of this OPT packet reception || 1009 (OPT_MODE[j]==PARTIAL && HEIGHT[j]!=NULL) || OPT_MODE[j]==FULL 1010 then A) else B). 1012 A) Set HEIGHT[j]=ZERO. Set HEIGHT[j].delta to the value of the 1013 DELTA field in the received OPT packet + 1. Set HEIGHT[j].id 1014 to the unique id of this node. Update LNK_STAT[j][n] for all 1015 n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the current 1016 time. Create an OPT packet and place it in the queue to be 1017 sent to all neighbors. Event Processing Complete. 1019 B) Event Processing Complete. 1021 II) Event Processing Complete. 1023 4.7.9 Mode Configuration Change or Optimization Timer Event for local 1024 interface "i" 1025 Increment MODE_SEQ[i]. Create an OPT packet and place it in the queue 1026 to be sent to all neighbors. If OPT_MODE[i]==PARTIAL || 1027 OPT_MODE[i]==FULL, schedule a local optimization timer event for 1028 interface "i" to occur at a time randomly selected between 1029 0.5*OPT_PERIOD[i] and 1.5*OPT_PERIOD[i] seconds based on a uniform 1030 distribution. Event Processing Complete. 1032 5 Security Considerations 1034 TBD. 1036 References 1038 [1] V. Park and M. S. Corson, A Highly Adaptive Distributed Routing 1039 Algorithm for Mobile Wireless Networks, Proc. IEEE INFOCOM '97, Kobe, 1040 Japan (1997). 1041 [4] M.S. Corson and V. Park, An Internet MANET Encapsulation Protocol 1042 (IMEP), draft-ietf- 1044 Author's Addresses 1046 Vincent D. Park 1047 Information Technology Division 1048 Naval Research Laboratory 1049 Washington, DC 20375 1050 (202) 767-5098 1051 vpark@itd.nrl.navy.mil 1053 M. Scott Corson 1054 Institute for Systems Research 1055 University of Maryland 1056 College Park, MD 20742 1057 (301) 405-6630 1058 corson@isr.umd.edu