IETF MANET Working Group V. Park INTERNET-DRAFT Naval Research Laboratory draft-ietf-manet-tora-spec-02.txt S. Corson University of Maryland 22 October 1999 Temporally-Ordered Routing Algorithm (TORA) Version 1 Functional Specification Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This document provides a detailed specification of the Temporally- Ordered Routing Algorithm (TORA)--a distributed routing protocol for multihop networks. A key concept in the protocol's design is an attempt to de-couple (to the greatest extent possible) the generation of far-reaching control message propagation from the dynamics of the network topology. The basic, underlying algorithm is neither traditionally distance-vector nor link-state; it is one of a family of algorithms referred to as "link reversal" algorithms. In particular, the protocol's reaction to certain link failures is structured as a temporally-ordered sequence of diffusing computations, each computation consisting of a sequence of directed link reversals. The protocol can operate in either a reactive, proactive or mixed mode. Park, Corson Expires 22 April 2000 [Page 1]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 1 Introduction The Temporally-Ordered Routing Algorithm (TORA) [1] is an adaptive routing protocol for multihop networks. It possesses the following attributes: * Distributed execution, * Loop-free routing, * Multipath routing, * Reactive or proactive route establishment and maintenance, and * Minimization of communication overhead via localization of algorithmic reaction to topological changes when possible. Its operation can be biased towards high reactivity (i.e., low time complexity) and bandwidth conservation (i.e., low communication complexity) rather than routing optimality (i.e., continuous shortest-path computation). Its design and flexability make it potentially well-suited for use mobile ad hoc networks (MANETs). TORA is based, in part, on the work presented in [2] and [3]. A key concept in the protocol's design is an attempt to de-couple (to the greatest extent possible) the generation of far-reaching control message propagation from the dynamics of the network topology. The scope of TORA's control messaging is typically localized to a very small set of nodes near a topological change. TORA includes a secondary mechanism that is independent of network topology dynamics, which allows far-reaching control message propagation as a means of route optimization or soft-state route verification. TORA is distributed, in that nodes need only maintain information about adjacent nodes (i.e., one-hop knowledge). Like a distance- vector routing approaches, TORA maintains state on a per-destination basis. Its design allows reactive operation, in which sources initiate the establishment of routes to a given destination on- demand, since it may not be necessary (nor desirable) to maintain routes between every source/destination pair at all times. At the same time, selected destinations can initiate proactive operation, resembling traditional table-driven routing approaches. TORA maintains loop-free routing, and typically provides multiple routes for any source/destination pair that requires a route. In the event of a network partition, the protocol detects the partition and erases invalid routes. 2 Terminology MANET router or router: A device--identified by a "unique Router ID" (RID)--that executes a MANET routing protocol and, under the direction of which, forwards IP packets. It may have multiple interfaces, each identified by an IP address. Associated with each interface is a Park, Corson Expires 22 April 2000 [Page 2]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 physical layer communication device. These devices may employ wireless or hardwired communications, and a router may simultaneously employ devices of differing technologies. For example, a MANET router may have four interfaces with differing communications technologies: two hardwired (Ethernet and FDDI) and two wireless (spread spectrum and impulse radio). adjacency: The name given to an "interface on a neighboring router". medium: A communication channel such as free space, cable or fiber through which connections are established. communications technology: The means employed by two devices to transfer information between them. connection: A physical-layer connection--which may be through a wired or wireless medium--between a device attached to an interface of one MANET router and a device utilizing the same communications technology attached to an interface on another MANET router. From the perspective of a given router, a connection is a (interface, adjacency) pair. link: A "logical connection" consisting of the logical *union* of one or more connections between two MANET routers. Thus, a link may consist of a heterogeneous combination of connections through differing media using different communications technologies. neighbor: From the perspective of a given MANET router, a "neighbor" is any other router to which it is connected by a link. topology: A network can be viewed abstractly as a "graph" whose "topology" at any point in time is defined by set of "points" connected by "edges." This term comes from the branch of mathematics bearing the same name that is concerned with those properties of geometric configurations (such as point sets) which are unaltered by elastic deformations (such as stretching) that are homeomorphisms. physical-layer topology: A topology consisting of connections (the edges) through the *same* communications medium between devices (the points) communicating using the *same* communications technology. Park, Corson Expires 22 April 2000 [Page 3]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 network-layer topology: A topology consisting of links (the edges) between MANET routers (the points) which is used as the basis for MANET routing. Since "links" are the logical union of physical-layer "connections," it follows that the "network-layer topology" is the logical union of the various "physical-layer topologies." IP routing fabric: The heterogeneous mixture of communications media and technologies through which IP packets are forwarded whose topology is defined by the network-layer topology. 3 Protocol Functional Description TORA has been designed to work on top of lower layer mechanisms or protocols that provide the following basic services between neighboring routers: * Link status sensing and neighbor discovery * Reliable, in-order control packet delivery * Link and network layer address resolution and mapping * Security authentication Events such as the reception of control messages and changes in connectivity with neighboring routers trigger TORA's algorithmic reactions. A logically separate version of TORA is run for each "destination" to which routing is required. The following discussion focuses on a single version of TORA running for a given destination. The term destination is used herein to refer to a traditional IP routing destination, which is identified by an IP address and mask. Thus, the route to a destination may correspond to the individual address of an interface on a specific machine (i.e., a host route) or an aggregation of addresses (i.e., a network route). TORA assigns directions to the links between routers to form a routing structure that is used to forward datagrams to the destination. A router assigns a direction ("upstream" or "downstream") to the link with a neighboring router based on the relative values of a metric associated with each router. The metric maintained by a router can conceptually be thought of as the router's "height" (i.e., links are directed from the higher router to the lower router). The significance of the heights and the link directional assignments is that a router may only forward datagrams downstream. Links from a router to any neighboring routers with an unknown or "null" height are considered undirected and cannot be used for forwarding. Collectively, the heights of the routers and the link directional assignments form a multipath routing structure, in which all directed paths lead downstream to the destination. Park, Corson Expires 22 April 2000 [Page 4]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 TORA can be separated into four basic functions: creating routes, maintaining routes, erasing routes, and optimizing routes. Creating routes corresponds to the selection of heights to form a directed sequence of links leading to the destination in a previously undirected network or portion of the network. Maintaining routes refers to the adapting the routing structure in response to network topological changes. For example, following the loss of some router's last downstream link, some directed paths may temporarily no longer lead to the destination--resulting a sequence of directed link reversals (caused by the re-selection of router heights) to re-orient the routing structure such that all directed paths again lead to the destination. In cases where the network becomes partitioned, links in the portion of the network that has become partitioned from the destination must be marked as undirected to erase invalid routes. During this erasing routes process, routers set their heights to null and their adjacent links become undirected. Finally, TORA includes a secondary mechanism for route optimization, in which routers re- select their heights in order to improve the routing structure. TORA accomplishes these four functions through the use of four distinct control packets: query (QRY), update (UPD), clear (CLR), and optimization (OPT). 3.1 Protocol State At any given time, an ordered quintuple, HEIGHT = (tau[i], oid[i], r[i], delta[i], i), is associated with each node i, where i is the unique ID of the node. Conceptually, the quintuple associated with each node represents the height of the node as defined by two parameters: a reference level and an offset with respect to the reference level. The reference level is represented by the first three values in the quintuple, while the offset is represented by the last two values. A new reference level is defined each time a node loses its last downstream link due to a link failure. The first value representing the reference level, tau[i], is a time tag set to the "time" of the link failure. For now, it is assumed that all nodes have synchronized clocks. This could be accomplished via interface with an external time source such as the Global Positioning System (GPS) [5] or through use of an algorithm such as the Network Time Protocol [6]. This time tag need not actually indicate or be "time," nor will relaxation of the synchronization requirement invalidate the protocol. The second value, oid[i], is the originator-ID (i.e., the unique ID of the node that defined the new reference level). This ensures that the reference levels can be totally ordered lexicographically, even if multiple nodes define reference levels due to failures that occur simultaneously (i.e., with equal time tags). The third value, r[i], is a single bit used to divide each of the unique reference levels into two unique sub-levels. This bit is used to distinguish between the original reference level and its Park, Corson Expires 22 April 2000 [Page 5]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 corresponding, higher, reflected reference level. When a distinction is not required, both the original and reflected reference levels will simply be referred to as "reference levels." The first value representing the offset, delta[i], is an integer used to order nodes with respect to a common reference level. This value is instrumental in the propagation of a reference level. How delta is selected will be clarified in a subsequent section. Finally, the second value representing the offset, i, is the unique ID of the node itself. This ensures that nodes with a common reference level and equal values of delta (and in fact all nodes) can be totally ordered lexicographically at all times. Each node i (other than the destination) maintains its height, HEIGHT. Initially the height of each node in the network (other than the destination) is set to NULL, HEIGHT = (-, -, -, -, i), where i is the unique ID of the node. Subsequently, the height of each node i can be modified in accordance with the rules of the protocol. The height of the destination j is always ZERO, HEIGHT = (0, 0, 0, 0, j), where j is the unique ID of the destination for which the algorithm is running). In addition to its own height, each node i maintains a height table with an entry HT_NEIGH[k] for each neighbor k. Initially the height of each neighbor is set to NULL, HT_NEIGH[k] = (-, -, -, -, k). If the destination j is a neighbor of node i, node i sets the corresponding height entry to ZERO, HT_NEIGH[j] = (0, 0, 0, 0, j). Each node i (other than the destination) also maintains a link-status table with an entry LNK_STAT[k] for each link (i, k), where node k is a neighbor of node i. The status of the links is determined by the height of the node, HEIGHT, and its height entry for the neighbor, HT_NEIGH[k]. The link is directed from the higher node to the lower node. If a neighbor k is higher than node i, the link is marked upstream (UP). If a neighbor k is lower than node i, the link is marked downstream (DN). If the neighbor's height entry, HT_NEIGH[k], is NULL, the link is marked undirected (UN). Finally, if the height of node i is NULL, then any neighbor's height that is not NULL is considered lower, and the corresponding link is marked downstream (DN). When a new link (i, k) is established (i.e., node i has a new neighbor k), node i adds entries for the new neighbor to the height and link-status tables. If the new neighbor is the destination j, the corresponding height entry is set to ZERO, HT_NEIGH[j] = (0, 0, 0, 0, j); otherwise it is set to NULL, HT_NEIGH[k] = (-, -, -, -, k). The corresponding link-status entry, LNK_STAT[k], is set as outlined above. Nodes need not communicate any routing information upon link activation. 3.2 Creating Routes Creating routes requires use of the QRY and UPD packets. A QRY packet Park, Corson Expires 22 April 2000 [Page 6]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 consists of the destination-ID, j, which identifies the destination for which the algorithm is running. An UPD packet consists of the destination-ID, j, and the height of the node i that is broadcasting the packet, HEIGHT. Each node i (other than the destination) maintains a route-required flag, which is initially un-set. Each node i (other than the destination) also maintains the time at which the last UPD packet was broadcast and the time at which each link (i, k), where node k is neighbor of node i, became active. When a node with no directed links and an un-set route-required flag requires a route to the destination, it broadcasts a QRY packet and sets its route-required flag. When a node i receives a QRY it reacts as follows: a) If the receiving node i has no downstream links and its route- required flag is un-set, it re-broadcasts the QRY packet and sets its route-required flag. b) If the receiving node i has no downstream links and the route- required flag is set, it discards the QRY packet. c) If the receiving node i has at least one downstream link and its height is NULL, it sets its height to HEIGHT = (tau[k], oid[k], r[k], delta[k] + 1, i), where HT_NEIGH[k] = (tau[k], oid[k], r[k], delta[k], k) is the minimum height of its non-NULL neighbors, and broadcasts an UPD packet. d) If the receiving node i has at least one downstream link and its height is non-NULL, it first compares the time the last UPD packet was broadcast to the time the link over which the QRY packet was received became active. If an UPD packet has been broadcast since the link became active, it discards the QRY packet; otherwise, it broadcasts an UPD packet. If a node has the route-required flag set when a new link is established, it must broadcast a QRY packet. When a node i receives an UPD packet from a neighbor k, node i first updates the entry HT_NEIGH[k] in its height table with the height contained in the received UPD packet. Node i then updates the entry LNK_STAT[k] in its link-status table and reacts as follows: a) If the route-required flag is set (which implies that the height of node i is NULL), node i sets its height to HEIGHT = (tau[k], oid[k], r[k], delta[k] + 1, i)--where HT_NEIGH[k] = (tau[k], oid[k], r[k], delta[k], k) is the minimum height of its Park, Corson Expires 22 April 2000 [Page 7]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 non-NULL neighbors, updates all the entries in its link-status table, un-sets the route-required flag and then broadcasts an UPD packet that contains its new height. b) If the route-required flag is not set, node i need only react if it has lost its last downstream link. The section on maintaining routes discusses the reaction that occurs if reception of the UPD packet resulted in loss of the last downstream link. 3.3 Maintaining Routes Maintaining routes is only performed for nodes that have a height other than NULL. Furthermore, any neighbor's height that is NULL is not used for the computations. A node i is said to have no downstream links if HEIGHT < HT_NEIGH[k] for all non-NULL neighbors k. This will result in one of five possible reactions depending on the state of the node and the preceding event. Each node (other than the destination) that has no downstream links modifies its height, HEIGHT = (tau[i], oid[i], r[i], delta[i], i), as follows: Case 1 (Generate): Node i has no downstream links (due to a link failure). (tau[i], oid[i], r[i])=(t, i, 0), where t is the time of the failure. (delta[i],i)=(0, i) In essence, node i defines a new reference level. The above assumes node i has at least one upstream neighbor. If node i has no upstream neighbors it simply sets its height to NULL. Case 2 (Propagate): Node i has no downstream links (due to a link reversal following reception of an UPD packet) and the ordered sets (tau[k], oid[k], r[k]) are not equal for all neighbors k. (tau[i], oid[i], r[i])=max{(t[k], oid[k], r[k]) of all neighbors k} (delta[i],i)=(delta[m]-1, i), where m is the lowest neighbor with the maximum reference level defined above. In essence, node i propagates the reference level of its highest neighbor and selects a height that is lower than all neighbors with that reference level. Park, Corson Expires 22 April 2000 [Page 8]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 Case 3 (Reflect): Node i has no downstream links (due to a link reversal following reception of an UPD packet) and the ordered sets (tau[k], oid[k], r[k]) are equal with r[k] = 0 for all neighbors k. (tau[i], oid[i], r[i])=(tau[k], oid[k], 1) (delta[i],i)=(0, i) In essence, the same level (which has not been "reflected") has propagated to node i from all of its neighbors. Node i "reflects" back a higher sub-level by setting the bit r. Case 4 (Detect): Node i has no downstream links (due to a link reversal following reception of an UPD packet), the ordered sets (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all neighbors k, and oid[k] = i (i.e., node i defined the level). (tau[i], oid[i], r[i])=(-, -, -) (delta[i],i)=(-, i) In essence, the last reference level defined by node i has been reflected and propagated back as a higher sub-level from all of its neighbors. This corresponds to detection of a partition. Node i must initiate the process of erasing invalid routes as discussed in the next section. Case 5 (Generate): Node i has no downstream links (due to a link reversal following reception of an UPD packet), the ordered sets (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all neighbors k, and oid[k] != i (i.e., node i did not define the level). (tau[i], oid[i], r[i])=(t, i, 0), where t is the time of the failure (delta[i],i)=(0, i) In essence, node i experienced a link failure (which did not require reaction) between the time it propagated a reference level and the reflected higher sub-level returned from all Park, Corson Expires 22 April 2000 [Page 9]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 neighbors. This is not necessarily an indication of a partition. Node i defines a new reference level. Following determination of its new height in cases 1, 2, 3, and 5, node i updates all the entries in its link-status table; and broadcasts an UPD packet to all neighbors k. The UPD packet consists of the destination-ID, j, and the new height of the node i that is broadcasting the packet, HEIGHT. When a node i receives an UPD packet from a neighbor k, node i reacts as described in the creating routes section and in accordance with the cases outlined above. In the event of the failure a link (i, k) that is not its last downstream link, node i simply removes the entries HT_NEIGH[k] and LNK_STAT[k] in its height and link-status tables. 3.4 Erasing Routes Following detection of a partition (case 4), node i sets its height and the height entry for each neighbor k to NULL (unless the destination j is a neighbor, in which case the corresponding height entry is set to ZERO), updates all the entries in its link-status table, and broadcast a CLR packet. The CLR packet consists of the destination-ID, j, and the reflected reference level of node i, (tau[i], oid[i], 1). In actuality the value r[i] = 1 need not be included since it is always 1 for a reflected reference level. When a node i receives a CLR packet from a neighbor k it reacts as follows: a) If the reference level in the CLR packet matches the reference level of node i; it sets its height and the height entry for each neighbor k to NULL (unless the destination j is a neighbor, in which case the corresponding height entry is set to ZERO), updates all the entries in its link-status table and broadcasts a CLR packet. b) If the reference level in the CLR packet does not match the reference level of node i; it sets the height entry for each neighbor k (with the same reference level as the CLR packet) to NULL and updates the corresponding link-status table entries. Thus, the height of each node in the portion of the network that was partitioned is set to NULL and all invalid routes are erased. If (b) causes node i to lose its last downstream link, it reacts as in case 1 of maintaining routes. 3.5 Optimizing Routes TBD. 4 Protocol Specification Park, Corson Expires 22 April 2000 [Page 10]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 The subsequent specification is intended to be of sufficient detail to serve as a template for implementations. 4.1 Configuration For each interface "i" of a router, the following configuration parameters are maintained. IP_ADDR[i] IP address of interface. ADDR_MASK[i] Address mask of interface. PRO_MODE[i] Indicates reactive/proactive mode of operation. OPT_MODE[i] Indicates optimization mode of operation. OPT_PERIOD[i] Period for optimization mechanism. For each interface, a network route corresponding to the address and mask of the interface may be added to the routing table. Additionally, TORA may respond to requests (i.e., QRY packets) for routes to destination addresses that match the set of addresses identified by the interface configurations. PRO_MODE[i] (0=OFF, 1=ON) indicates if routes to the destination identified by the corresponding interface address and mask should be created proactively. OPT_MODE[i] (00=OFF, 01=PARTIAL, 10=FULL, 11=reserved for future use) indicates the type (if any) of optimizations that should be used for the destination identified by the corresponding interface address and mask, while the OPT_PERIOD[i] sets the frequency at which the optimizations will occur. A router is also configured with a router ID (RID), which must be unique among the set of routers collectively running TORA. 4.2 State Variables For each destination "j" to which routing is required, a router maintains the following state variables. HEIGHT[j] This router's height metric for routing to "j". PRO_MODE[j] Indicates reactive/proactive mode of operation for "j". OPT_MODE[j] Indicates optimization mode of operation for "j". MODE_SEQ[j] Sequence number of most recent mode change regarding "j". RT_REQ[j] Indicates whether a route to "j" is required. TIME_UPD[j] Time last UPD packet regarding "j" sent by this router. For each destination "j" to which routing is required, a router maintains a separate instance of the following state variables for each neighbor "k". HT_NEIGH[j][k] The height metric of neighbor "k." LNK_STAT[j][k] The assigned status of the link to neighbor "k." Park, Corson Expires 22 April 2000 [Page 11]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 TIME_ACT[j][k] Time the link to neighbor "k" became active. 4.3 Auxiliary Variables For each destination "j" to which routing is required, a router may maintain the following auxiliary variables. Although each of the variables can be computed based on the entries in the LNK_STAT table, maintaining the values continuously may facilitate implementation of the protocol. num_active[j] Number of neighbors (i.e., active links). num_down[j] Number of links marked DN in the LNK_STAT table. num_up[j] Number of links marked UP in the LNK_STAT table. 4.4 Height Data Structure Each HEIGHT[j] and HT_NEIGH[j][k] entry requires a data structure that comprises five components. The first three components of the Height data structure represent the reference level of the height entry, while the last two components represent an offset with respect to the reference level. The five components of the Height data structure are as follows. Height.tau Time the reference level was created. Height.oid Unique id of the router that created the reference level. Height.r Flag indicating if it is a reflected reference level. Height.delta Value used in propagation of a reference level. Height.id Unique id of the router to which the height metric refers. To simplify notation in this specification, a height may be written as an ordered quintuple--e.g., HEIGHT[j]=(tau,oid,r,delta,id). The following two predefined values for a height are used throughout the specification of the protocol. NULL=(-,-,-,-,id) An unknown or undefined height. Conceptually, this can be thought of as an infinite height. ZERO=(0,0,0,0,id) The assumed height of a given destination. Note that here "id" is the unique id of the given destination. 4.5 Determination of Link Status Each entry in the LNK_STAT table is maintained in accordance with the following rule. if HT_NEIGH[k]==NULL then LNK_STAT[k]=UN; else if HEIGHT==NULL then LNK_STAT[k]=DN; Park, Corson Expires 22 April 2000 [Page 12]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 else if HT_NEIGH[k]<HEIGHT then LNK_STAT[k]=DN; else if HT_NEIGH[k]>HEIGHT then LNK_STAT[k]=UP; 4.6 TORA Packet Formats TBD. 4.7 Event Processing 4.7.1 Initialization TBD 4.7.2 Connection Status Change The TORA process receives notification of link status changes. It is anticipated that the TORA process will have access to all the information about the connections. Thus, upon notification, TORA will have sufficient information to determine if any new links have been established or any existing links have been severed. If either is the case, then TORA must proceed as outlined in appropriate subsequent section (4.7.3 or 4.7.4). In addition, it is also possible for a connection that was used in the routing table to be severed without resulting in the corresponding link being severed. In this case TORA must modify the appropriate routing table entries. 4.7.3 Link with a New Neighbor "k" Established For each destination "j": Set TIME_ACT[j][k] to the current time and increment num_active[j]. If the neighbor "k" is the destination "j", then set HT_NEIGH[j][k]=ZERO, LNK_STAT[j][k]=DN and increment num_down[j], else set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN. If the RT_REQ[j] flag is set && neighbor "k" is the destination "j" then I) else II). I) Set HEIGHT[j]=HT_NEIGH[j][k]. Increment HEIGHT[j].delta. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. II) If PRO_MODE==1 and HEIGHT[j]!=NULL then A) else B). A) Set TIME_UPD[j] to the current time. Create an UPD packet Park, Corson Expires 22 April 2000 [Page 13]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 and place it in the queue to be sent to all neighbors. If the RT_REQ[j] flag is set, create a QRY packet and place it in the queue to be sent to all neighbors. Event Processing Complete. B) If the RT_REQ[j] flag is set, create a QRY packet and place it in the queue to be sent to all neighbors. Event Processing Complete. 4.7.4 Link with Prior Neighbor "k" Severed For each destination "j": Decrement num_active[j]. If LNK_STAT[j][k]==DN, decrement num_down[j]. If LNK_STAT[j][k]==UP, decrement num_up[j]. If num_down[j]==0 then I) else II). I) If num_active[j]==0 then A) else B). A) Set HEIGHT[j]=NULL. Unset the RT_REQ[j] flag. Event Processing Complete. B) If num_up==0 then 1) else 2). 1) If HEIGHT[j]==NULL then a) else b). a) Event Processing Complete. b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. 2) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid to the unique id of this node. Set HEIGHT[j].r=0. Set HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. II) Event Processing Complete. 4.7.5 QRY Packet Regarding Destination "j" Received from Neighbor "k" If the RT_REQ[j] flag is set then I) else II). I) Event Processing Complete. Park, Corson Expires 22 April 2000 [Page 14]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 II) If HEIGHT[j].r==0 then A) else B). A) If TIME_ACT[j][k]>TIME_UPD[j] then 1) else 2). 1) Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. 2) Event Processing Complete. B) If HT_NEIGH[j][n].r==0 for any n then 1) else 2). 1) Find m such that HT_NEIGH[j][m] is the minimum of all height entries with HT_NEIGH[j][n].r==0. Set HEIGHT[j]=HT_NEIGH[j][m]. Increment HEIGHT.delta. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. 2) Set the RT_REQ[j] flag. If num_active[j]>1 then a) else b). a) Create a QRY packet and place it in the queue to be sent to all neighbors. Event Processing Complete. b) Event Processing Complete. 4.7.6 UPD Packet Regarding Destination "j" Received from Neighbor "k" If MODE_SEQ field of received packet is greater than MODE_SEQ[j], update entries PRO_MODE[j], OPT_MODE[j], and MODE_SEQ[j]. Update the entries HT_NEIGH[j][k], and LNK_STAT[j][k]. If the RT_REQ[j] flag is set and HT_NEIGH[j][k].r==0 then I) else II). I) Set HEIGHT[j]=HT_NEIGH[j][k]. Increment HEIGHT.delta. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. II) If num_down[j]==0 then A) else B). A) If num_up[j]==0 then 1) else 2). 1) If HEIGHT[j]==NULL then a) else b). Park, Corson Expires 22 April 2000 [Page 15]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 a) Event Processing Complete. b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. 2) If all HT_NEIGH[j][n], for all n such that HT_NEIGH[j][n] is non-NULL, have the same reference level then a) else b). a) If HT_NEIGH[j][n].r==0, for any n such that HT_NEIGH[j][n] is non-NULL, then i) else ii). i) Set HEIGHT[j]=HT_NEIGH[j][n], where n is such that HT_NEIGH[j][n] is non-NULL. Set HEIGHT[j].r=1. Set HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. ii) If HT_NEIGH[j][n].oid==id, where n is such that HT_NEIGH[j][n] is non-NULL and id is the unique id of this node, then x) else y). x) Save the current values of HEIGHT[j].tau and HEIGHT[j].oid in temporary variables. Set HEIGHT[j]=NULL. Set num_down[j]=0. Set num_up[j]=0. For every active link n, if the neighbor connected via link n is the destination j, set HT_NEIGH[j][n]=ZERO and LNK_STAT[j][n]=DN else set HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. Create a CLR packet, with the previously saved values of tau and oid, and place it in the queue to be sent to all neighbors. Event Processing Complete. y) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid to the unique id of this node. Set HEIGHT[j].r=0. Set HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. b) Find n such that HT_NEIGH[j][n] is the maximum of all non-NULL height entries. Find m such that HT_NEIGH[j][m] is the minimum of the non-NULL height entries with the Park, Corson Expires 22 April 2000 [Page 16]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 same reference level as HT_NEIGH[j][n]. Set HEIGHT[j]=HT_NEIGH[j][m]. Decrement HEIGHT.delta. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. B) IF PRO_MODE changed from OFF to ON as a result of this UPD packet reception and HEIGHT[j]==NULL then 1) else 2) 1) Find m such that HT_NEIGH[j][m] is the minimum of all non-NULL height entries. Set HEIGHT[j]=HT_NEIGH[j][m]. Increment HEIGHT[j].delta. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. 2) Event Processing Complete. 4.7.7 CLR Packet Regarding Destination "j" Received from Neighbor "k" If HEIGHT[j].tau and HEIGHT[j].oid match the values of tau and oid from the CLR packet and HEIGHT[j].r==1 then I) else II). I) Save the current values of HEIGHT[j].tau and HEIGHT[j].oid in temporary variables. Set Height[j]=NULL. Set num_down[j]=0. Set num_up[j]=0. For every active link n, if the neighbor connected via link n is the destination j, set HT_NEIGH[j][n]=ZERO and LNK_STAT[j][n]=DN else set HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. If num_active[j]>1 then A) else B). A) Create a CLR packet, with the previously saved values of tau and oid, and place it in the queue to be sent to all neighbors. Event Processing Complete. B) Event Processing Complete. II) Set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN. For all n such that HT_NEIGH[j][n].tau and HT_NEIGH[j][n].oid match the values of tau and oid from the CLR packet and HT_NEIGH[j][n].r==1, set HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. If num_down[j]==0 then A) else B). A) If num_up==0 then 1) else 2). 1) If HEIGHT[j]==NULL then a) else b). Park, Corson Expires 22 April 2000 [Page 17]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 a) Event Processing Complete. b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. 2) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid to the unique id of this node. Set HEIGHT[j].r=0. Set HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the current time. Create an UPD packet and place it in the queue to be sent to all neighbors. Event Processing Complete. B) Event Processing Complete. 4.7.8 OPT Packet Regarding Destination "j" Received from Neighbor "k" If MODE_SEQ field of received packet is greater than MODE_SEQ[j] then I) else II). I) Update entries PRO_MODE[j], OPT_MODE[j], and MODE_SEQ[j]. If PRO_MODE[j] changed as a result of this OPT packet reception || (OPT_MODE[j]==PARTIAL && HEIGHT[j]!=NULL) || OPT_MODE[j]==FULL then A) else B). A) Set HEIGHT[j]=ZERO. Set HEIGHT[j].delta to the value of the DELTA field in the received OPT packet + 1. Set HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n] for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the current time. Create an OPT packet and place it in the queue to be sent to all neighbors. Event Processing Complete. B) Event Processing Complete. II) Event Processing Complete. 4.7.9 Mode Configuration Change or Optimization Timer Event for local interface "i" Increment MODE_SEQ[i]. Create an OPT packet and place it in the queue to be sent to all neighbors. If OPT_MODE[i]==PARTIAL || OPT_MODE[i]==FULL, schedule a local optimization timer event for interface "i" to occur at a time randomly selected between 0.5*OPT_PERIOD[i] and 1.5*OPT_PERIOD[i] seconds based on a uniform distribution. Event Processing Complete. 5 Security Considerations Park, Corson Expires 22 April 2000 [Page 18]
INTERNET-DRAFT Temporally-Ordered Routing Algorithm 22 October 1999 TBD. References [1] V. Park and M. S. Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proc. IEEE INFOCOM '97, Kobe, Japan (1997). [2] M.S. Corson and A. Ephremides, A distributed routing algorithm for mobile wireless networks, Wireless Networks 1 (1995). [3] E. Gafni and D. Bertsekas, Distributed algorithms for generating loop-free routes in networks with frequently changing topology, IEEE Trans. Commun. (January 1981). [4] M.S. Corson and V. Park, An Internet MANET Encapsulation Protocol (IMEP), draft-ietf- [5] NAVSTAR GPS user equipment introduction, MZ10298.001 (February 1991). [6] D. Mills, Network time protocol, specification, implementation and analysis, Internet RFC-1119 (September 1989). Author's Addresses Vincent D. Park Information Technology Division Naval Research Laboratory Washington, DC 20375 (202) 767-5098 vpark@itd.nrl.navy.mil M. Scott Corson Institute for Systems Research University of Maryland College Park, MD 20742 (301) 405-6630 corson@isr.umd.edu Park, Corson Expires 22 April 2000 [Page 19]
