idnits 2.17.1 draft-ietf-manet-tora-spec-01.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-26) 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: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** 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 3 instances of too long lines in the document, the longest one being 4 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 122 has weird spacing: '...erlying proto...' -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. 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 937, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' == Outdated reference: A later version (-01) exists of draft-ietf-manet-imep-spec-00 -- Possible downref: Normative reference to a draft: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' ** Obsolete normative reference: RFC 1119 (ref. '6') (Obsoleted by RFC 1305) == Outdated reference: A later version (-01) exists of draft-ietf-manet-term-00 -- Possible downref: Normative reference to a draft: ref. '7' Summary: 10 errors (**), 0 flaws (~~), 5 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft V. Park 3 draft-ietf-manet-tora-spec-01.txt Naval Research Laboratory 4 S. Corson 5 University of Maryland 6 Submitted: Aug 7, 1998 7 Expires: Feb 7, 1999 9 Temporally-Ordered Routing Algorithm (TORA) Version 1 10 Functional Specification 12 Status of this Memo 14 This document is an Internet-Draft. Internet-Drafts are working 15 documents of the Internet Engineering Task Force (IETF), its areas, 16 and its working groups. Note that other groups may also distribute 17 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 To learn the current status of any Internet-Draft, please check the 25 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 26 Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 27 munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or 28 ftp.isi.edu (US West Coast). 30 Abstract 32 This document provides a detailed specification of Version 1 of the 33 Temporally-Ordered Routing Algorithm (TORA)--a distributed routing 34 protocol for mobile, multihop, wireless networks. Its intended use is 35 for routing of Internet Protocol (IP) datagrams within an autonmous 36 system. The basic, underlying algorithm is neither a distance-vector 37 nor a link-state; it is one of a family of algorithms referred to as 38 ``link reversal'' algorithms. The protocol's reaction is structured as 39 a temporally-ordered sequence of diffusing computations, each 40 computation consisting of a sequence of directed link reversals. The 41 protocol is highly adaptive, efficient and scalable; and is well- 42 suited for use in large, dense, mobile networks. In these networks, 43 the protocol's reaction to link failures typically involves only a 44 localized ``single pass'' of the distributed algorithm. This desirable 45 behavior is achieved through the use of a physical or logical clock 46 to establish the ``temporal order'' of topological change events. The 47 established temporal ordering is subsequently used to structure (or 48 order) the algorithm's reaction to topological changes. 50 1 Introduction 52 The Temporally-Ordered Routing Algorithm (TORA) [1] is a highly 53 adaptive routing protocol, which has been tailored for operation in a 54 Mobile Ad hoc Network (MANET). Such a network can be envisioned as a 55 collection of routers (equipped with wireless receiver/transmitters), 56 which are free to move about arbitrarily. The status of the 57 communication links between the routers, at any given time, is a 58 function of their positions, transmission power levels, antenna 59 patterns, cochannel interference levels, etc. The mobility of the 60 routers and the variability of other connectivity factors result in a 61 network with a potentially rapid and unpredictably changing topology. 62 Congested links are also an expected characteristic of such a network 63 as wireless links inherently have significantly lower capacity than 64 hardwired links and are therefore more prone to congestion. TORA's 65 design is predicated on the notion that a routing algorithm that is 66 well-suited for operation in this environment should possess the 67 following properties: 68 * Executes distributedly 69 * Provides loop-free routes 70 * Provides multiple routes (i.e., to reduce the frequency of 71 reactions to topological changes and potentially to alleviate 72 congestion) 73 * Establishes routes quickly (i.e., so they may be used before 74 the topology changes) 75 * Minimizes communication overhead by localizing algorithmic 76 reaction to topological changes when possible (i.e., to conserve 77 available bandwidth and increase scalability) 78 Routing optimality (i.e., determination of the shortest-path) is of 79 less importance. It is also not necessary (nor desirable) to maintain 80 routes between every source/destination pair at all times. The 81 overhead expended to establish a route between a given 82 source/destination pair will be wasted if the source does not require 83 the route prior to its invalidation due to topological changes. 85 TORA is based, in part, on the work presented in [2] and [3]. TORA is 86 designed to minimize reaction to topological changes. A key concept 87 in its design is that it decouples the generation of potentially 88 far-reaching control message propagation from the rate of topological 89 changes. Control messaging is typically localized to a very small set 90 of nodes near the change without having to resort to a dynamic, 91 hierarchical routing solution with its attendant complexity. TORA 92 includes a secondary mechanism, which allows far-reaching control 93 message propagation as a means of infrequent route optimization and 94 soft-state route verification. This propogation occurs periodically 95 at a very low rate and is independent of the network topology 96 dynamics. 98 TORA is distributed in that nodes need only maintain information 99 about adjacent nodes (i.e., one hop knowledge). It guarantees all 100 routes are loop-free, and typically provides multiple routes for any 101 source/destination pair that requires a route. TORA is "source 102 initiated" and quickly creates a set of routes to a given destination 103 only when desired. Since multiple routes are typically established 104 and having a single route is sufficient, many topological changes 105 require no reaction at all. Following topological changes that do 106 require reaction, the protocol quickly re-establishes valid routes. 107 This ability to initiate and react infrequently serves to minimize 108 communication overhead. Finally, in the event of a network partition, 109 the protocol detects the partition and erases all invalid routes. 111 2 MANET Routing Functional Description 113 A protocol for routing packets in a MANET can be divided into two 114 functional distinct components--a link status sensing mechanism and a 115 routing mechanism. Although these two components are somewhat 116 orthogonal, they can be designed to work together in a synergistic 117 fashion. Originally, these two mechanisms were being designed 118 together as a part of the TORA protocol specification. However, since 119 the basic functionality provided by a link status sensing mechanism 120 is required by a variety of different routing mechanisms, it seemed 121 appropriate that a more generic link status sensing mechanism should 122 be designed and specified as a separate, underlying protocol. This 123 underlying protocol--the Internet MANET Encapsulation Protocol (IMEP) 124 [4]--is being designed to provide several other basic functions that 125 are commonly required by a routing mechanism. Thus, TORA provides 126 only the routing mechanism and depends on IMEP for other underlying 127 functions. Should it later be decided that the two protocols should 128 be combined, IMEP's functionality will be incorporated back into the 129 TORA specification. 131 2.1 Internet MANET Encapsulation Protocol 133 IMEP and TORA have been designed to work together synergistically. 134 TORA relies on IMEP for the following underlying functions and 135 services: 136 * Link status sensing (i.e., monitoring and maintaining the 137 status of connectivity with the set of neighboring routers) 138 * Control packet delivery (i.e., reliable, in-order control packet 139 delivery to the set of neighbors) 140 * Network-layer address resolution and mapping 141 * Security authentication 142 IMEP provides a rich interface for use by a variety of different 143 mobile wireless routing protocols, which may have varied needs for 144 underlying services. 146 2.2 Temporally-Ordered Routing Algorithm 148 This section provides a functional description of TORA. A detailed 149 specification of TORA is provided in a subsequent section. 151 2.2.1 Notation 153 A network can be modeled as a graph with a finite set of nodes 154 connected by a set of initially undirected links--wherea node 155 represents a router and a link represents communication connectivity 156 between two routers. Each node i in the network is assumed to have a 157 unique node identifier (ID), and each link (i, k) is assumed to allow 158 two-way communication (i.e., nodes connected by a link can 159 communicate with each other in either direction). Due to the mobility 160 of the nodes, the set of links in the network is changing with time 161 (i.e., new links can be established and existing links can be 162 severed). Each initially undirected link (i, k) may subsequently be 163 assigned one of three states; (1) undirected, (2) directed from node 164 i to node k, or (3) directed from node k to node i. If a link (i, k) 165 is directed from node i to node k, node i is said to be "upstream" 166 from node k, while node k is said to be "downstream" from node i. For 167 each node i, we define the "neighbors" of i, to be the set of nodes k 168 such that there exists a link between nodes i and k. The following 169 assumptions account for the functionality provided by the IMEP. It is 170 assumed that each node i is always aware of its set of neighbors. 171 Additionally, it is assumed that when a node i transmits a packet, it 172 is broadcast to all of its neighbors and that all transmitted packets 173 are received correctly and in order of transmission. 175 2.2.2 Foundation and Basic Structure 177 A logically separate version of TORA is run for each destination to 178 which routing is required. The following discussion focuses on a 179 single version running for a given destination, j. 181 TORA can be separated into three basic functions: creating routes, 182 maintaining routes, and erasing routes. Creating a route from a given 183 node to the destination requires establishment of a sequence of 184 directed links leading from the node to the destination. This 185 function is only initiated when a node with no directed links 186 requires a route to the destination. Thus, creating routes 187 essentially corresponds to assigning directions to links in an 188 undirected network or portion of the network. The method used to 189 accomplish this is an adaptation of the query/reply process described 190 in [2], which builds a directed acyclic graph (DAG) rooted at the 191 destination (i.e., the destination is the only node with no 192 downstream links). Such a DAG will be referred to as a "destination- 193 oriented" DAG. Maintaining routes refers to reacting to topological 194 changes in the network in a manner such that routes to the 195 destination are re-established within a finite time--meaning that its 196 directed portions return to a destination-oriented DAG within a 197 finite time. Gafni and Bertsekas (GB) described two algorithms [3], 198 which are members of a general class of algorithms designed to 199 accomplish this task. However, the GB algorithms are designed for 200 operation in connected networks. Due to instability exhibited by 201 these algorithms in portions of the network that become partitioned 202 from the destination, they are deemed unacceptable for the current 203 task. TORA incorporates a new algorithm, in the same general class, 204 that is more efficient in reacting to topological changes and capable 205 of detecting a network partition. This leads to the third function-- 206 erasing routes. Upon detection of a network partition, all links (in 207 the portion of the network that has become partitioned from the 208 destination) must be marked as undirected to erase invalid routes. 210 TORA accomplishes these three functions through the use of three 211 distinct control packets: query (QRY), update (UPD), and clear (CLR). 212 QRY packets are used for creating routes; UPD packets are used for 213 both creating and maintaining routes; and CLR packets are used for 214 erasing routes. 216 2.2.3 General Class of Algorithms 218 It is beneficial at this point to briefly review the earlier GB 219 algorithms. Consider a connected DAG with at least one node (in 220 addition to the destination) that has no downstream links. Such a DAG 221 will be referred to as "destination-disoriented." The following 222 excerpts (punctuation added for clarity) from [3] loosely describe 223 the two algorithms designed to transform a destination-disoriented 224 DAG into a destination-oriented DAG. 226 Full Reversal Method: At each iteration, each node (other than the 227 destination) that has no outgoing links reverses the direction of all 228 its incoming links. 230 Partial Reversal Method: Every node i (other than the destination) 231 keeps a list of its neighboring nodes k that have reversed the 232 direction of the corresponding links (i, k). At each iteration, each 233 node i that has no outgoing links reverses the directions of the 234 links (i, k), for all k which do not appear on its list, and empties 235 the list. If no such k exists (i.e., the list is full), node i 236 reverses the directions of all incoming links and empties the list. 238 These two algorithms are subsequently re-stated in the context of a 239 generalized numbering scheme that will be summarize here; however, 240 much detail will be left out. For a thorough understanding, one 241 should review the original paper. Essentially, a value is associated 242 with each node at all times, and the values are such that they can be 243 totally ordered. For example, in the full reversal method, a pair 244 (alpha[i], i) is associated with each node where i is the unique ID 245 of the node and alpha[i] is an integer. The pairs can then be totally 246 ordered lexicographically (e.g. (alpha[i], i) > (alpha[k], k) if 247 alpha[i] > alpha[k] ,or if alpha[i] = alpha[k] and i > k). The value 248 associated with each node i will be referred to as its "height" and 249 denoted h[i]. Now, assume that we assign an initial height to each 250 node in the destination-disoriented DAG such that node i is upstream 251 from node k if and only if h[i] > h[k]. Then it is clear that node i 252 has no downstream links when, measured by its height, it is a local 253 minimum with respect to its neighbors, h[i] < h[k] for all neighbors 254 k. To achieve the desired behavior in the full reversal method, node 255 i must select a new height such that it becomes a local maximum with 256 respect to its neighbors (i.e., h[i] > h[k] for all neighbors k). 257 Node i simply selects a new value alpha[i] = max {alpha[k] such that 258 k is a neighbor of i}+1 and broadcasts the value to all of its 259 neighbors. The partial reversal method can neither be viewed 260 conceptually nor explained as easily. Again, a node selects a new 261 height only when it is a local minimum, but it does not always become 262 a local maximum. To reverse only some of its links (i.e., partial 263 reversal), a node selects a new height that is higher than its own 264 previous height and the height of some of its neighbors, but not 265 higher than the height of all of its neighbors. 267 The algorithms that belong to this general class are shown to be 268 loop-free, and terminate in a finite number of iterations to a 269 destination-oriented DAG [3]. Furthermore, only nodes that have lost 270 all downstream paths to the destination react to a given failure. The 271 new algorithm incorporated into TORA for the maintaining routes 272 process is a member of this class, and thus inherits many of these 273 properties. The new algorithm is similar to the partial reversal 274 method in that it often reverses only some of its links. However, in 275 order to provide a partition detection capability, the rules for the 276 selection of a new height are significantly more complex. These rules 277 are discussed in detail in section 2.2.4.2. 279 The basic idea is as follows. When a node loses its last downstream 280 link (i.e., becomes a local minimum) as a result of a link failure, 281 the node selects a new height such that it becomes a global maximum 282 by defining a new "reference level". By design, when a new reference 283 level is defined, it is higher than any previously defined reference 284 levels. This action results in link reversals that may cause other 285 nodes to lose their last downstream link. Any such node executes a 286 partial reversal with respect to its neighbors that have heights 287 already associated with the newest (highest) reference level. In this 288 manner, the new reference level is propagated outward from the point 289 of the original failure (re-directing links in order to re-establish 290 routes to the destination). This propagation will only extend through 291 nodes that (as a result of the initial link failure) have lost all 292 routes to the destination. Some nodes may experience link reversals 293 from all neighbors (as a result of the same initial link failure). 294 Any such node must select a new height such that it becomes a local 295 maximum. This is accomplished by defining a higher sub-level 296 associated with the new reference level, which will be referred to as 297 the "reflected reference level". This node essentially "reflects" 298 this higher sub-level back toward the node that originally defined 299 the new reference level. Should this reflected reference level be 300 propagated back to the originating node from all of its neighbors, 301 then it is determined that no route to the destination exists. The 302 originating node has then detected a partition and can begin the 303 process of erasing the invalid routes. 305 2.2.4 Detailed Description 307 At any given time, an ordered quintuple, HEIGHT = (tau[i], oid[i], 308 r[i], delta[i], i), is associated with each node i, where i is the 309 unique ID of the node. Conceptually, the quintuple associated with 310 each node represents the height of the node as defined by two 311 parameters: a reference level and a offset with respect to the 312 reference level. The reference level is represented by the first 313 three values in the quintuple, while the offset is represented by the 314 last two values. A new reference level is defined each time a node 315 loses its last downstream link due to a link failure. The first value 316 representing the reference level, tau[i], is a time tag set to the 317 "time" of the link failure. For now, it is assumed that all nodes 318 have synchronized clocks. This could be accomplished via interface 319 with an external time source such as the Global Positioning System 320 (GPS) [5] or through use of an algorithm such as the Network Time 321 Protocol [6]. This time tag need not actually indicate or be "time," 322 nor will relaxation of the synchronization requirement invalidate the 323 protocol. The second value, oid[i], is the originator-ID (i.e., the 324 unique ID of the node that defined the new reference level). This 325 ensures that the reference levels can be totally ordered 326 lexicographically, even if multiple nodes define reference levels due 327 to failures that occur simultaneously (i.e., with equal time tags). 328 The third value, r[i], is a single bit used to divide each of the 329 unique reference levels into two unique sub-levels. This bit is used 330 to distinguish between the original reference level and its 331 corresponding, higher, reflected reference level. When a distinction 332 is not required, both the original and reflected reference levels 333 will simply be referred to as "reference levels." The first value 334 representing the offset, delta[i], is an integer used to order nodes 335 with respect to a common reference level. This value is instrumental 336 in the propagation of a reference level. How delta is selected will 337 be clarified in a subsequent section. Finally, the second value 338 representing the offset, i, is the unique ID of the node itself. This 339 ensures that nodes with a common reference level and equal values of 340 delta (and in fact all nodes) can be totally ordered 341 lexicographically at all times. 343 Each node i (other than the destination) maintains its height, 344 HEIGHT. Initially the height of each node in the network (other than 345 the destination) is set to NULL, HEIGHT = (-, -, -, -, i), where i is 346 the unique ID of the node. Subsequently, the height of each node i 347 can be modified in accordance with the rules of the protocol. The 348 height of the destination j is always ZERO, HEIGHT = (0, 0, 0, 0, j), 349 where j is the unique ID of the destination for which the algorithm 350 is running). In addition to its own height, each node i maintains a 351 height table with an entry HT_NEIGH[k] for each neighbor k. Initially 352 the height of each neighbor is set to NULL, HT_NEIGH[k] = (-, -, -, 353 -, k). If the destination j is a neighbor of node i, node i sets the 354 corresponding height entry to ZERO, HT_NEIGH[j] = (0, 0, 0, 0, j). 356 Each node i (other than the destination) also maintains a link-status 357 table with an entry LNK_STAT[k] for each link (i, k), where node k is 358 a neighbor of node i. The status of the links is determined by the 359 height of the node, HEIGHT, and its height entry for the neighbor, 360 HT_NEIGH[k]. The link is directed from the higher node to the lower 361 node. If a neighbor k is higher than node i, the link is marked 362 upstream (UP). If a neighbor k is lower than node i, the link is 363 marked downstream (DN). If the neighbor's height entry, HT_NEIGH[k], 364 is NULL, the link is marked undirected (UN). Finally, if the height 365 of node i is NULL, then any neighbor's height that is not NULL is 366 considered lower, and the corresponding link is marked downstream 367 (DN). When a new link (i, k) is established (i.e., node i has a new 368 neighbor k), node i adds entries for the new neighbor to the height 369 and link-status tables. If the new neighbor is the destination j, the 370 corresponding height entry is set to ZERO, HT_NEIGH[j] = (0, 0, 0, 0, 371 j); otherwise it is set to NULL, HT_NEIGH[k] = (-, -, -, -, k). The 372 corresponding link-status entry, LNK_STAT[k], is set as outlined 373 above. Nodes need not communicate any routing information upon link 374 activation. 376 2.2.4.1 Creating Routes 378 Creating routes requires use of the QRY and UPD packets. A QRY packet 379 consists of the destination-ID, j, which identifies the destination 380 for which the algorithm is running. An UPD packet consists of the 381 destination-ID, j, and the height of the node i that is broadcasting 382 the packet, HEIGHT. 384 Each node i (other than the destination) maintains a route-required 385 flag, which is initially un-set. Each node i (other than the 386 destination) also maintains the time at which the last UPD packet was 387 broadcast and the time at which each link (i, k), where node k is 388 neighbor of node i, became active. 390 When a node with no directed links and an un-set route-required flag 391 requires a route to the destination, it broadcasts a QRY packet and 392 sets its route-required flag. When a node i receives a QRY it reacts 393 as follows: 395 a) If the receiving node i has no downstream links and its route- 396 required flag is un-set, it re-broadcasts the QRY packet and sets 397 its route-required flag. 399 b) If the receiving node i has no downstream links and the route- 400 required flag is set, it discards the QRY packet. 402 c) If the receiving node i has at least one downstream link and 403 its height is NULL, it sets its height to HEIGHT = (tau[k], 404 oid[k], r[k], delta[k] + 1, i), where HT_NEIGH[k] = (tau[k], 405 oid[k], r[k], delta[k], k) is the minimum height of its non-NULL 406 neighbors, and broadcasts an UPD packet. 408 d) If the receiving node i has at least one downstream link and 409 its height is non-NULL, it first compares the time the last UPD 410 packet was broadcast to the time the link over which the QRY 411 packet was received became active. If an UPD packet has been 412 broadcast since the link became active, it discards the QRY 413 packet; otherwise, it broadcasts an UPD packet. 415 If a node has the route-required flag set when a new link is 416 established, it must broadcast a QRY packet. 418 When a node i receives an UPD packet from a neighbor k, node i first 419 updates the entry HT_NEIGH[k] in its height table with the height 420 contained in the received UPD packet. Node i then updates the entry 421 LNK_STAT[k] in its link-status table and reacts as follows: 423 a) If the route-required flag is set (which implies that the 424 height of node i is NULL), node i sets its height to HEIGHT = 425 (tau[k], oid[k], r[k], delta[k] + 1, i)--where HT_NEIGH[k] = 426 (tau[k], oid[k], r[k], delta[k], k) is the minimum height of its 427 non-NULL neighbors, updates all the entries in its link-status 428 table, un-sets the route-required flag and then broadcasts an UPD 429 packet that contains its new height. 431 b) If the route-required flag is not set, node i need only react 432 if it has lost its last downstream link. The section on 433 maintaining routes discusses the reaction that occurs if reception 434 of the UPD packet resulted in loss of the last downstream link. 436 2.2.4.2 Maintaining Routes 438 Maintaining routes is only performed for nodes that have a height 439 other than NULL. Furthermore, any neighbor's height that is NULL is 440 not used for the computations. A node i is said to have no downstream 441 links if HEIGHT < HT_NEIGH[k] for all non-NULL neighbors k. This will 442 result in one of five possible reactions depending on the state of 443 the node and the preceding event. Each node (other than the 444 destination) that has no downstream links modifies its height, HEIGHT 445 = (tau[i], oid[i], r[i], delta[i], i), as follows: 447 Case 1 (Generate): 449 Node i has no downstream links (due to a link failure). 451 (tau[i], oid[i], r[i])=(t, i, 0), where t is the time of the 452 failure. 454 (delta[i],i)=(0, i) 456 In essence, node i defines a new reference level. The above 457 assumes node i has at least one upstream neighbor. If node i 458 has no upstream neighbors it simply sets its height to NULL. 460 Case 2 (Propagate): 462 Node i has no downstream links (due to a link reversal 463 following reception of an UPD packet) and the ordered sets 464 (tau[k], oid[k], r[k]) are not equal for all neighbors k. 466 (tau[i], oid[i], r[i])=max{(t[k], oid[k], r[k]) of all 467 neighbors k} 469 (delta[i],i)=(delta[m]-1, i), where m is the lowest neighbor 470 with the maximum reference level defined above. 472 In essence, node i propagates the reference level of its 473 highest neighbor and selects a height that is lower than all 474 neighbors with that reference level. 476 Case 3 (Reflect): 478 Node i has no downstream links (due to a link reversal 479 following reception of an UPD packet) and the ordered sets 480 (tau[k], oid[k], r[k]) are equal with r[k] = 0 for all 481 neighbors k. 483 (tau[i], oid[i], r[i])=(tau[k], oid[k], 1) 485 (delta[i],i)=(0, i) 487 In essence, the same level (which has not been "reflected") has 488 propagated to node i from all of its neighbors. Node i 489 "reflects" back a higher sub-level by setting the bit r. 491 Case 4 (Detect): 493 Node i has no downstream links (due to a link reversal 494 following reception of an UPD packet), the ordered sets 495 (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all 496 neighbors k, and oid[k] = i (i.e., node i defined the level). 498 (tau[i], oid[i], r[i])=(-, -, -) 500 (delta[i],i)=(-, i) 502 In essence, the last reference level defined by node i has been 503 reflected and propagated back as a higher sub-level from all of 504 its neighbors. This corresponds to detection of a partition. 505 Node i must initiate the process of erasing invalid routes as 506 discussed in the next section. 508 Case 5 (Generate): 510 Node i has no downstream links (due to a link reversal 511 following reception of an UPD packet), the ordered sets 512 (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all 513 neighbors k, and oid[k] != i (i.e., node i did not define the 514 level). 516 (tau[i], oid[i], r[i])=(t, i, 0), where t is the time of the 517 failure 519 (delta[i],i)=(0, i) 521 In essence, node i experienced a link failure (which did not 522 require reaction) between the time it propagated a reference 523 level and the reflected higher sub-level returned from all 524 neighbors. This is not necessarily an indication of a 525 partition. Node i defines a new reference level. 527 Following determination of its new height in cases 1, 2, 3, and 5, 528 node i updates all the entries in its link-status table; and 529 broadcasts an UPD packet to all neighbors k. The UPD packet consists 530 of the destination-ID, j, and the new height of the node i that is 531 broadcasting the packet, HEIGHT. When a node i receives an UPD packet 532 from a neighbor k, node i reacts as described in the creating routes 533 section and in accordance with the cases outlined above. In the event 534 of the failure a link (i, k) that is not its last downstream link, 535 node i simply removes the entries HT_NEIGH[k] and LNK_STAT[k] in its 536 height and link-status tables. 538 2.2.4.3 Erasing Routes 540 Following detection of a partition (case 4), node i sets its height 541 and the height entry for each neighbor k to NULL (unless the 542 destination j is a neighbor, in which case the corresponding height 543 entry is set to ZERO), updates all the entries in its link-status 544 table, and broadcast a CLR packet. The CLR packet consists of the 545 destination-ID, j, and the reflected reference level of node i, 546 (tau[i], oid[i], 1). In actuality the value r[i] = 1 need not be 547 included since it is always 1 for a reflected reference level. When a 548 node i receives a CLR packet from a neighbor k it reacts as follows: 550 a) If the reference level in the CLR packet matches the reference 551 level of node i; it sets its height and the height entry for each 552 neighbor k to NULL (unless the destination j is a neighbor, in 553 which case the corresponding height entry is set to ZERO), updates 554 all the entries in its link-status table and broadcasts a CLR 555 packet. 557 b) If the reference level in the CLR packet does not match the 558 reference level of node i; it sets the height entry for each 559 neighbor k (with the same reference level as the CLR packet) to 560 NULL and updates the corresponding link-status table entries. 561 Thus, the height of each node in the portion of the network that 562 was partitioned is set to NULL and all invalid routes are erased. 563 If (b) causes node i to lose its last downstream link, it reacts 564 as in case 1 of maintaining routes. 566 3 Protocol Specification 568 In the previous description of TORA, some simplifications were made 569 for clarity. In particular, j was used to represent the unique ID of 570 the destination for which the algorithm was running. However, when 571 forwarding IP datagrams in an internetwork, "destinations" to which 572 routing is required are usually identified by an IP address and mask. 573 Together, these two values may correspond to an individual interface 574 on a specific machine, or an aggregation of addresses (e.g., a 575 network address). Thus, in the subsequent discussion a destination 576 "j" refers to a typical IP destination. Another significant 577 simplification pertains to the link between to nodes. In the most 578 general case, a MANET router may have multiple wireless and hardwired 579 interfaces with differing communication technologies. Therefore, it 580 is necessary to make a distiction between a physical communication 581 "connection" between two routers and a logical communication "link" 582 between two routers. The previous description also ommited any 583 discussion about how the next-hop forwarding decision is made. It is 584 assumed that the IP packet forwarding performed by the kernel in 585 accordance with a standard IP routing table maintained in kernel 586 space. The TORA process must have access to the information in the 587 table and be able to manipulate the table entries. The details 588 regarding how the routing table manipulations made by TORA will be 589 described in detail in the subsequent sections. Since the subsequent 590 description is intended to be in sufficient detail to serve as a 591 template for implementations, some additional terminology is defined 592 first. 594 3.1 Terminology 596 The following definitions are identical to the definitions used in 597 the IMEP specification. Many of these definitions may be replaced by 598 or merged with those of the MANET working group's terminology draft 599 [7] now under development. 601 MANET router or router: 602 A device--identified by a "unique Router ID" (RID)--that executes 603 a MANET routing protocol and, under the direction of which, 604 forwards IP packets. It may have multiple interfaces, each 605 identified by an IP address. Associated with each interface is a 606 physical layer communication device. These devices may employ 607 wireless or hardwired communications, and a router may 608 simultaneousl employ devices of differing technologies. For 609 example, a MANET router may have four interfaces with differing 610 communications technologies: two hardwired (Ethernet and FDDI) and 611 two wireless (spread spectrum and impulse radio). 613 adjacency: 614 The name given to an "interface on a neighboring router". 616 medium: 617 A communication channel such as free space, cable or fiber through 618 which connections are established. 620 communications technology: 621 The means employed by two devices to transfer information between 622 them. 624 connection: 625 A physical-layer connection--which may be through a wired or 626 wireless medium--between a device attached to an interface of one 627 MANET router and a device utilizating the same communications 628 technology attached to an interface on another MANET router. From 629 the perspective of a given router, a connection is a (interface, 630 adjacency) pair. 632 link: 633 A "logical connection" consisting of the logical *union* of one or 634 more connections between two MANET routers. Thus, a link may 635 consist of a heterogeneous combination of connections through 636 differing media using different communications technologies. 638 neighbor: 639 From the perspective of a given MANET router, a "neighbor" is any 640 other router to which it is connected by a link. 642 topology: 643 A network can be viewed abstractly as a "graph" whose "topology" 644 at any point in time is defined by set of "points" connected by 645 "edges." This term comes from the branch of mathematics bearing 646 the same name that is concerned with those properties of geometric 647 configurations (such as point sets) which are unaltered by elastic 648 deformations (such as stretching) that are homeomorphisms. 650 physical-layer topology: 651 A topology consisting of connections (the edges) through the 652 *same* communications medium between devices (the points) 653 communicating using the *same* communications technology. 655 network-layer topology: 656 A topology consisting of links (the edges) between MANET routers 657 (the points) which is used as the basis for MANET routing. Since 658 "links" are the logical union of physical-layer "connections," it 659 follows that the "network-layer topology" is the logical union of 660 the various "physical-layer topologies." 662 IP routing fabric: 663 The heterogeneous mixture of communications media and technologies 664 through which IP packets are forwarded whose topology is defined 665 by the network-layer topology. 667 3.2 State Variables 669 For each destination "j" to which routing is required, a router 670 maintains the following state variables. 672 HEIGHT[j] The height metric of this router. 673 RT_REQ[j] Flag indicating route to the destination is required. 674 TIME_UPD[j] Time an UPD packet was last sent by this router. 676 For each destination "j" to which routing is required, a router 677 maintains a separate instance of the following state variables for 678 each neighbor "k". 680 HT_NEIGH[j][k] The height metric of neighbor "k." 681 LNK_STAT[j][k] The assigned status of the link to neighbor "k." 682 TIME_ACT[j][k] Time the link to neighbor "k" became active. 684 3.3 Auxiliary Variables 686 For each destination "j" to which routing is required, a router 687 may maintain the following auxiliary variables. Although each of 688 the variables can be computed based on the entries in the LNK_STAT 689 table, maintaining the values continuously may facilitate 690 implementation of the protocol. 692 num_active[j] Number of neighbors (i.e., active links). 693 num_down[j] Number of links marked DN in the LNK_STAT table. 694 num_up[j] Number of links marked UP in the LNK_STAT table. 696 3.4 Height Data Structure 698 Each HEIGHT[j] and HT_NEIGH[j][k] entry requires a data structure 699 that comprises five components. The first three components of the 700 Height data structure represent the reference level of the height 701 entry, while the last two components represent an offset with 702 respect to the reference level. The five components of the Height 703 data structure are as follows. 705 Height.tau Time the reference level was created. 706 Height.oid Unique id of the router that created the reference level. 707 Height.r Flag indicating if it is a reflected reference level. 708 Height.delta Value used in propagation of a reference level. 709 Height.id Unique id of the router. 711 To simplify notation in this specification, a height may be 712 written as an ordered quintuple--e.g., 713 HEIGHT[j]=(tau,oid,r,delta,id). The following two predefined 714 values for a height are used throughout the specification of the 715 protocol. 717 NULL=(-,-,-,-,id) An unknown or undefined height. Conceptually, 718 this can be thought of as an infinite height. 720 ZERO=(0,0,0,0,id) The assumed height of a given destination. Note 721 that here "id" is the unique id of the given 722 destination. 724 3.5 Determination of Link Status 726 Each entry in the LNK_STAT table is maintained in accordance with 727 the following rule. 729 if HT_NEIGH[k]==NULL then LNK_STAT[k]=UN; 730 else if HEIGHT==NULL then LNK_STAT[k]=DN; 731 else if HT_NEIGH[k]HEIGHT then LNK_STAT[k]=UP; 734 3.6 TORA Packet Formats 736 TORA packets are encapsulated in IMEP messages, which are sent as 737 "raw" IP datagrams with protocol number ?. The bit level format of 738 the TORA packets has yet to be defined. 740 3.7 Event Processing 742 3.7.1 Initialization 744 TBD. 746 3.7.2 Connection Status Change 748 The TORA process receives notification of connection status changes 749 from the the IMEP process. The interface between these two processes 750 has yet to be defined. However, it is anticipated that the TORA 751 process will have access to all the information maintained by the 752 IMEP process about the connections. Thus, upon notification, TORA 753 will have sufficient information to determine if any new links have 754 been established or any existing links have been severed. If either 755 is the case, then TORA must proceed as outlined in appropriate 756 subsequent section (3.7.3 or 3.7.4). In addition, it is also 757 possible for a connection that was used in the routing table to be 758 severed without resulting in the corresponding link being severed. In 759 this case TORA must modify the appropriate routing table entries as 760 outlined in section 3.7.5. 762 3.7.3 Link with a New Neighbor "k" Established 764 TBD. 766 3.7.4 Link with Prior Neighbor "k" Severed 768 TBD. 770 3.7.5 Connection Used in Routing Table Severed 771 TBD. 773 3.7.6 QRY Packet Regarding Destination "j" Received from Neighbor "k" 775 If the RTE_REQ flag set then I) else II). nk with Prior Neighbor "k" 776 Severed 778 I) Event Processing Complete. 780 II) If HEIGHT[j].r==0 then A) else B). 782 A) If TIME_ACT[j][k]>TIME_UPD[j] then 1) else 2). 784 1) Set TIME_UPD to the current time. Create an UPD packet 785 and place it in the queue to be sent to all neighbors. Event 786 Processing Complete. 788 2) Event Processing Complete. 790 B) If HT_NEIGH[j][n].r==0 for any n then 1) else 2). 792 1) Find m such that HT_NEIGH[j][m] is the minimum of all 793 height entries with HT_NEIGH[j][n].r==0. Set 794 HEIGHT[j]=HT_NEIGH[j][m]. Increment HEIGHT.delta. Set 795 HEIGHT[j].id to the unique id of this node. Update 796 LNK_STAT[j][n] for all n. Set TIME_UPD to the current time. 797 Create an UPD packet and place it in the queue to be sent to 798 all neighbors. Event Processing Complete. 800 2) Set the RT_REQ flag. If num_active>1 then a) else b). 802 a) Create a QRY packet and place it in the queue to be 803 sent to all neighbors. Event Processing Complete. 805 b) Event Processing Complete. 807 3.7.7 UPD Packet Regarding Destination "j" Received from Neighbor "k" 809 Update the entries HT_NEIGH[j][k] and LNK_STAT[j][k]. If the RT_REQ 810 flag is set and HT_NEIGH[j][k].r==0 then I) else II). 812 I) Set HEIGHT[j]=HT_NEIGH[j][k]. Increment HEIGHT.delta. Set 813 HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] 814 for all n. Unset the RT_REQ flag. Set TIME_UPD to the current 815 time. Create an UPD packet and place it in the queue to be sent to 816 all neighbors. Event Processing Complete. 818 II) If num_down[j]==0 then A) else B). 820 A) If num_up[j]==0 then 1) else 2). 822 1) If HEIGHT[j]==NULL then a) else b). 824 a) Event Processing Complete. 826 b) Set HEIGHT[j]=NULL. Set TIME_UPD to the current time. 827 Create an UPD packet and place it in the queue to be sent 828 to all neighbors. Event Processing Complete. 830 2) If all HT_NEIGH[j][n], for all n such that HT_NEIGH[j][n] 831 is non-NULL, have the same reference level then a) else b). 833 a) If HT_NEIGH[j][n].r==0, for any n such that 834 HT_NEIGH[j][n] is non-NULL, then i) else ii). 836 i) Set HEIGHT[j]=HT_NEIGH[j][n], where n is such that 837 HT_NEIGH[j][n] is non-NULL. Set HEIGHT[j].r=1. Set 838 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id 839 of this node. Update LNK_STAT[j][n] for all n. Set 840 TIME_UPD to the current time. Create an UPD packet and 841 place it in the queue to be sent to all neighbors. 842 Event Processing Complete. 844 ii) If HT_NEIGH[j].oid==id, where id is the unique id 845 of this node, then x) else y). 847 x) Save the current values of HEIGHT[j].tau and 848 HEIGHT[j].oid in temporary variables. Set 849 HEIGHT[j]=NULL. Set num_down=0. Set num_up=0. For 850 every active link n, if the neighbor connected via 851 link n is the destination j, set 852 HT_NEIGH[j][n]=ZERO and LNK_STAT[j][n]=DN else set 853 HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. Create a 854 CLR packet, with the previously saved values of tau 855 and oid, and place it in the queue to be sent to 856 all neighbors. Event Processing Complete. 858 y) Set HEIGHT[j].tau to the current time. Set 859 HEIGHT[j].oid to the unique id of this node. Set 860 HEIGHT[j].r=0. Set HEIGHT[j].delta=0. Set 861 HEIGHT[j].id to the unique id of this node. Update 862 LNK_STAT[j][n] for all n. Unset the RT_REQ flag. 863 Set TIME_UPD to the current time. Create an UPD 864 packet and place it in the queue to be sent to all 865 neighbors. Event Processing Complete. 867 b) Find n such that HT_NEIGH[j][n] is the maximum of all 868 non-NULL height entries. Find m such that HT_NEIGH[j][m] 869 is the minimum of the non-NULL height entries with the 870 same reference level as HT_NEIGH[j][n]. Set 871 HEIGHT[j]=HT_NEIGH[j][m]. Decrement HEIGHT.delta. Set 872 HEIGHT[j].id to the unique id of this node. Update 873 LNK_STAT[j][n] for all n. Set TIME_UPD to the current 874 time. Create an UPD packet and place it in the queue to 875 be sent to all neighbors. Event Processing Complete. 877 B) Event Processing Complete. 879 3.7.8 CLR Packet Regarding Destination "j" Received from Neighbor "k" 881 If HEIGHT[j].tau and HEIGHT[j].oid match the values of tau and oid 882 from the CLR packet and HEIGHT[j].r==1 then I) else II). 884 I) Save the current values of HEIGHT[j].tau and HEIGHT[j].oid in 885 temporary variables. Set Height[j]=NULL. Set num_down=0. Set 886 num_up=0. For every active link n, if the neighbor connected via 887 link n is the destination j, set HT_NEIGH[j][n]=ZERO and 888 LNK_STAT[j][n]=DN else set HT_NEIGH[j][n]=NULL and 889 LNK_STAT[j][n]=UN. If num_active>1 then A) else B). 891 A) Create a CLR packet, with the previously saved values of tau 892 and oid, and place it in the queue to be sent to all neighbors. 893 Event Processing Complete. 895 B) Event Processing Complete. 897 II) Set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN. For all n such 898 that HT_NEIGH[j][n].tau and HT_NEIGH[j][n].oid match the values of 899 tau and oid from the CLR packet and HT_NEIGH[j][n].r==1, set 900 HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. If num_down==0 then A) 901 else B). 903 A) If num_up==0 then 1) else 2). 905 1) If HEIGHT[j]==NULL then a) else b). 907 a) Event Processing Complete. 909 b) Set HEIGHT[j]=NULL. Set TIME_UPD to the current time. 910 Create an UPD packet and place it in the queue to be sent 911 to all neighbors. Event Processing Complete. 913 2) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid 914 to the unique id of this node. Set HEIGHT[j].r=0. Set 915 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of this 916 node. Update LNK_STAT[j][n] for all n. Unset the RT_REQ 917 flag. Set TIME_UPD to the current time. Create an UPD packet 918 and place it in the queue to be sent to all neighbors. Event 919 Processing Complete. 921 B) Event Processing Complete. 923 4 Security Considerations 925 TBD. 927 References 929 [1] V. Park and M. S. Corson, A Highly Adaptive Distributed Routing 930 Algorithm for Mobile Wireless Networks, Proc. IEEE INFOCOM '97, Kobe, 931 Japan (1997). 932 [2] M.S. Corson and A. Ephremides, A distributed routing algorithm 933 for mobile wireless networks, Wireless Networks 1 (1995). 934 [3] E. Gafni and D. Bertsekas, Distributed algorithms for generating 935 loop-free routes in networks with frequently changing topology, IEEE 936 Trans. Commun. (January 1981). 937 [4] M.S. Corson and V. Park, An Internet MANET Encapsulation Protocol 938 (IMEP), draft-ietf-manet-imep-spec-00.txt 939 [5] NAVSTAR GPS user equipment introduction, MZ10298.001 (February 940 1991). 941 [6] D. Mills, Network time protocol, specification, implementation 942 and analysis, Internet RFC-1119 (September 1989). 943 [7] C. Perkins, Mobile Ad Hoc Networking Terminology, draft-ietf- 944 manet-term-00.txt, (October 1997). 946 Author's Addresses 948 Vincent D. Park 949 Information Technology Division 950 Naval Research Laboratory 951 Washington, DC 20375 952 (202) 767-5098 953 vpark@itd.nrl.navy.mil 955 M. Scott Corson 956 Institute for Systems Research 957 University of Maryland 958 College Park, MD 20742 959 (301) 405-6630 960 corson@isr.umd.edu