Internet DraftIETF MANET Working Group                                         V. Park
draft-ietf-manet-tora-spec-01.txt
INTERNET-DRAFT                                 Naval Research Laboratory
draft-ietf-manet-tora-spec-02.txt                              S. Corson
                                                  University of Maryland
                                                 Submitted: Aug  7, 1998
                                                 Expires:   Feb  7,
                                                         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."

   To learn the current status

   The list of any Internet-Draft, please check the
   "1id-abstracts.txt" listing contained in the current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or
   ftp.isi.edu (US West Coast). can be accessed at
   http://www.ietf.org/shadow.html.

Abstract

   This document provides a detailed specification of Version 1 of the
   Temporally-Ordered Temporally-
   Ordered Routing Algorithm (TORA)--a distributed routing protocol for mobile, multihop, wireless
   multihop networks. Its intended use A key concept in the protocol's design is
   for routing of Internet Protocol (IP) datagrams within an autonmous
   system.
   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 a
   traditionally distance-vector nor a link-state; it is one of a family
   of algorithms referred to as
   ``link reversal'' "link reversal" algorithms. The 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 is highly adaptive, efficient and scalable; and is well-
   suited for use can operate in large, dense, mobile networks. In these networks,
   the protocol's reaction to link failures typically involves only a
   localized ``single pass'' of the distributed algorithm. This desirable
   behavior is achieved through the use of either a physical reactive,
   proactive or logical clock
   to establish the ``temporal order'' of topological change events. The
   established temporal ordering is subsequently used to structure (or
   order) the algorithm's reaction to topological changes. mixed mode.

1 Introduction

   The Temporally-Ordered Routing Algorithm (TORA) [1] is a highly an adaptive
   routing protocol, which has been tailored 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 in a
   Mobile Ad hoc Network (MANET). Such a network can be envisioned as a
   collection of routers (equipped with wireless receiver/transmitters),
   which are free to move about arbitrarily. The status of the biased towards high reactivity (i.e., low time
   complexity) and bandwidth conservation (i.e., low communication links between the routers, at any given time,
   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 a
   function of their positions, transmission power levels, antenna
   patterns, cochannel interference levels, etc. The mobility of based, in part, on the
   routers 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 variability generation of other connectivity factors result in a
   network with a potentially rapid and unpredictably changing topology.
   Congested links are also an expected characteristic of such a network
   as wireless links inherently have significantly lower capacity than
   hardwired links and are therefore more prone to congestion. TORA's
   design is predicated on the notion that a routing algorithm that is
   well-suited for operation in this environment should possess the
   following properties:
   *  Executes distributedly
   *  Provides loop-free routes
   *  Provides multiple routes (i.e., to reduce the frequency of
      reactions to topological changes and potentially to alleviate
      congestion)
   *  Establishes routes quickly (i.e., so they may be used before
      the topology changes)
   *  Minimizes communication overhead by localizing algorithmic
      reaction to topological changes when possible (i.e., to conserve
      available bandwidth and increase scalability)
   Routing optimality (i.e., determination of the shortest-path) is of
   less importance. It is also not necessary (nor desirable) to maintain
   routes between every source/destination pair at all times. The
   overhead expended to establish a route between a given
   source/destination pair will be wasted if the source does not require
   the route prior to its invalidation due to topological changes.

   TORA is based, in part, on the work presented in [2] and [3]. TORA is
   designed to minimize reaction to topological changes. A key concept
   in its design is that it decouples the generation of potentially far-reaching control
   message propagation from the rate dynamics of topological
   changes. Control the network topology. The
   scope of TORA's control messaging is typically localized to a very
   small set of nodes near the change without having to resort to a dynamic,
   hierarchical routing solution with its attendant complexity. topological change. TORA includes a
   secondary mechanism, mechanism that is independent of network topology dynamics,
   which allows far-reaching control message propagation as a means of infrequent
   route optimization and or soft-state route verification. This propogation occurs periodically
   at a very low rate and is independent of the network topology
   dynamics.

   TORA is distributed distributed, in that nodes need only maintain information
   about adjacent nodes (i.e., one hop one-hop knowledge). It guarantees all
   routes are loop-free, and typically provides multiple routes for any
   source/destination pair that requires Like a route. distance-
   vector routing approaches, TORA is "source
   initiated" and quickly creates maintains state on a set per-destination
   basis. Its design allows reactive operation, in which sources
   initiate the establishment of routes to a given destination
   only when desired. Since multiple routes are typically established
   and having a single route is sufficient, many topological changes
   require no reaction on-
   demand, since it may not be necessary (nor desirable) to maintain
   routes between every source/destination pair at all. Following topological changes that do
   require reaction, all times. At the protocol quickly re-establishes valid routes.
   This ability to
   same time, selected destinations can initiate proactive operation,
   resembling traditional table-driven routing approaches. TORA
   maintains loop-free routing, and react infrequently serves to minimize
   communication overhead. Finally, in 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 all
   invalid routes.

2 Terminology

   MANET Routing Functional Description router or router:
      A protocol for routing packets in device--identified by a MANET can be divided into two
   functional distinct components--a link status sensing mechanism and "unique Router ID" (RID)--that executes
      a MANET routing mechanism. Although these two components are somewhat
   orthogonal, they can be designed to work together in a synergistic
   fashion. Originally, these two mechanisms were being designed
   together as a part of the TORA protocol specification. However, since and, under the basic functionality provided direction of which,
      forwards IP packets. It may have multiple interfaces, each
      identified by a link status sensing mechanism an IP address. Associated with each interface is required by a variety of different routing mechanisms, it seemed
   appropriate that a more generic link status sensing mechanism should
   be designed
      physical layer communication device. These devices may employ
      wireless or hardwired communications, and specified as a separate, underlying  protocol. This
   underlying protocol--the Internet MANET Encapsulation Protocol (IMEP)
   [4]--is being designed to provide several other basic functions that
   are commonly required by router may
      simultaneously employ devices of differing technologies. For
      example, a routing mechanism. Thus, TORA provides
   only the routing mechanism MANET router may have four interfaces with differing
      communications technologies: two hardwired (Ethernet and FDDI) and depends on IMEP for other underlying
   functions. Should it later be decided that the
      two protocols should
   be combined, IMEP's functionality will be incorporated back into the
   TORA specification.

2.1 Internet MANET Encapsulation Protocol

   IMEP wireless (spread spectrum and TORA have been designed impulse radio).

   adjacency:
      The name given to work together synergistically.
   TORA relies an "interface on IMEP for the following underlying functions and
   services:
   *  Link status sensing (i.e., monitoring and maintaining the
      status of connectivity with the set of a neighboring routers)
   *  Control packet delivery (i.e., reliable, in-order control packet
      delivery 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 the set 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 neighbors)
   *  Network-layer address resolution one
      MANET router and mapping
   *  Security authentication
   IMEP provides a rich device utilizing the same communications
      technology attached to an interface for use by on another MANET router. From
      the perspective of a given router, a connection is a variety (interface,
      adjacency) pair.

   link:
      A "logical connection" consisting of different
   mobile wireless routing protocols, which the logical *union* of one or
      more connections between two MANET routers. Thus, a link may have varied needs for
   underlying services.

2.2 Temporally-Ordered Routing Algorithm

   This section provides
      consist of a functional description heterogeneous combination of TORA. A detailed
   specification connections through
      differing media using different communications technologies.

   neighbor:
      From the perspective of TORA a given MANET router, a "neighbor" is provided in any
      other router to which it is connected by a subsequent section.

2.2.1 Notation link.

   topology:
      A network can be modeled viewed abstractly as a graph with a finite "graph" whose "topology"
      at any point in time is defined by set of nodes "points" connected by a set
      "edges." This term comes from the branch of initially undirected links--wherea node
   represents a router and a link represents communication connectivity
   between two routers.  Each node i in mathematics bearing
      the network is assumed to have a
   unique node identifier (ID), and each link (i, k) same name that is assumed to allow
   two-way communication (i.e., nodes connected by a link can
   communicate concerned with each other in either direction). Due to the mobility 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 nodes,
      *same* communications medium between devices (the points)
      communicating using the set *same* communications technology.

   network-layer topology:
      A topology consisting of links in the network is changing with time
   (i.e., new links can be established and existing links can be
   severed). Each initially undirected link (i, k) may subsequently be
   assigned one of three states; (1) undirected, (2) directed from node
   i to node k, or (3) directed from node k to node i. If a link (i, k)
   is directed from node i to node k, node i is said to be "upstream"
   from node k, while node k (the edges) between MANET routers
      (the points) which is said to be "downstream" from node i. For
   each node i, we define the "neighbors" of i, to be used as the set of nodes k
   such that there exists a link between nodes i and k. The following
   assumptions account basis for MANET routing. Since
      "links" are the functionality provided by the IMEP. It is
   assumed that each node i is always aware of its set logical union of neighbors.
   Additionally, physical-layer "connections," it is assumed
      follows that when a node i transmits a packet, it the "network-layer topology" is broadcast to all the logical union of its neighbors
      the various "physical-layer topologies."

   IP routing fabric:
      The heterogeneous mixture of communications media and that all transmitted technologies
      through which IP packets are received correctly 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 in order neighbor discovery
     *  Reliable, in-order control packet delivery
     *  Link and network layer address resolution and mapping
     *  Security authentication
   Events such as the reception of transmission.

2.2.2 Foundation control messages and Basic Structure changes in
   connectivity with neighboring routers trigger TORA's algorithmic
   reactions.

   A logically separate version of TORA is run for each destination "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, j.

   TORA can be separated into three basic functions: creating routes,
   maintaining routes, which is identified by an IP address and erasing routes. Creating a mask. Thus, the
   route from to a given
   node destination may correspond to the destination requires establishment individual address of an
   interface on a sequence specific machine (i.e., a host route) or an
   aggregation of
   directed links leading from the node addresses (i.e., a network route). TORA assigns
   directions to the destination. This
   function is only initiated when a node with no directed links
   requires between routers to form a route routing structure
   that is used to forward datagrams to the destination. Thus, creating routes
   essentially corresponds to assigning directions to links in an
   undirected network A router
   assigns a direction ("upstream" or portion of the network. The method used "downstream") to
   accomplish this is an adaptation of the query/reply process described
   in [2], which builds link with a directed acyclic graph (DAG) rooted at the
   destination (i.e., the destination is
   neighboring router based on the only node relative values of a metric
   associated with no
   downstream links). Such each router. The metric maintained by a DAG will router can
   conceptually be referred to thought of as a "destination-
   oriented" DAG. Maintaining routes refers to reacting the router's "height" (i.e., links are
   directed from the higher router to topological
   changes in the network in a manner such lower router). The
   significance of the heights and the link directional assignments is
   that routes a router may only forward datagrams downstream. Links from a
   router to the
   destination any neighboring routers with an unknown or "null" height
   are re-established within considered undirected and cannot be used for forwarding.
   Collectively, the heights of the routers and the link directional
   assignments form a finite time--meaning that its multipath routing structure, in which all directed portions return
   paths lead downstream to a destination-oriented DAG within a
   finite time. Gafni the destination.

   TORA can be separated into four basic functions: creating routes,
   maintaining routes, erasing routes, and Bertsekas (GB) described two algorithms [3],
   which are members optimizing routes. Creating
   routes corresponds to the selection of heights to form a general class directed
   sequence of algorithms designed links leading to
   accomplish this task. However, the GB algorithms are designed for
   operation in connected networks. Due to instability exhibited by
   these algorithms destination in portions of the a previously
   undirected network that become partitioned
   from or portion of the destination, they are deemed unacceptable for network. Maintaining routes
   refers to the current
   task. TORA incorporates a new algorithm, in adapting the same general class,
   that is more efficient routing structure in reacting response to network
   topological changes and capable changes. For example, following the loss of detecting a network partition. This leads some router's
   last downstream link, some directed paths may temporarily no longer
   lead to the third function--
   erasing routes. Upon detection of destination--resulting a network partition, 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 in
   the portion of the network that has become partitioned from the
   destination)
   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 three four functions through the use of three four distinct
   control packets: query (QRY), update (UPD), and clear (CLR).
   QRY packets are used for creating routes; UPD packets are used for
   both creating and maintaining routes; (CLR), and CLR packets are used for
   erasing routes.

2.2.3 General Class of Algorithms

   It
   optimization (OPT).

3.1 Protocol State

   At any given time, an ordered quintuple, HEIGHT = (tau[i], oid[i],
   r[i], delta[i], i), is beneficial at this point to briefly review the earlier GB
   algorithms. Consider a connected DAG associated with at least one node (in
   addition to the destination) that has no downstream links. Such a DAG
   will be referred to as "destination-disoriented." The following
   excerpts (punctuation added for clarity) from [3] loosely describe
   the two algorithms designed to transform a destination-disoriented
   DAG into a destination-oriented DAG.

   Full Reversal Method: At each iteration, each node (other than the
   destination) that has no outgoing links reverses the direction of all
   its incoming links.

   Partial Reversal Method: Every node i, where i (other than is the destination)
   keeps a list
   unique ID of its neighboring nodes k that have reversed the
   direction of node. Conceptually, the corresponding links (i, k). At each iteration, quintuple associated with
   each node i that has no outgoing links reverses represents the directions height of the
   links (i, k), for all k which do not appear on its list, and empties
   the list. If no such k exists (i.e., the list is full), node i
   reverses the directions of all incoming links and empties the list.

   These as defined by two algorithms are subsequently re-stated in the context of a
   generalized numbering scheme that will be summarize here; however,
   much detail will be left out. For
   parameters: a thorough understanding, one
   should review reference level and an offset with respect to the original paper. Essentially, a value
   reference level. The reference level is associated
   with each node at all times, and represented by the first
   three values are such that they can be
   totally ordered. For example, in the full reversal method, a pair
   (alpha[i], i) quintuple, while the offset is associated with represented by the
   last two values. A new reference level is defined each time a node where i
   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 unique ID
   "time" of the node and alpha[i] link failure. For now, it is an integer. The pairs can then assumed that all nodes
   have synchronized clocks. This could be totally
   ordered lexicographically (e.g. (alpha[i], i) > (alpha[k], k) if
   alpha[i] > alpha[k] ,or if alpha[i] = alpha[k] and i > k). The value
   associated accomplished via interface
   with each node i will be referred to as its "height" and
   denoted h[i]. Now, assume that we assign an initial height to each
   node in external time source such as the destination-disoriented DAG Global Positioning System
   (GPS) [5] or through use of an algorithm such that node i is upstream
   from node k if and only if h[i] > h[k]. Then it is clear that node i
   has no downstream links when, measured by its height, it 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 a local
   minimum with respect to its neighbors, h[i] < h[k] for all neighbors
   k. To achieve the desired behavior in originator-ID (i.e., the
   unique ID of the full reversal method, node
   i must select a that defined the new height such reference level). This
   ensures that it becomes a local maximum with
   respect the reference levels can be totally ordered
   lexicographically, even if multiple nodes define reference levels due
   to its neighbors (i.e., h[i] > h[k] for all neighbors k).
   Node i simply selects a new value alpha[i] = max {alpha[k] such failures that
   k occur simultaneously (i.e., with equal time tags).
   The third value, r[i], is a neighbor single bit used to divide each of i}+1 and broadcasts the value
   unique reference levels into two unique sub-levels. This bit is used
   to all of distinguish between the original reference level and its
   neighbors. The partial reversal method can neither be viewed
   conceptually nor explained as easily. Again, a node selects
   corresponding, higher, reflected reference level. When a new
   height only when it distinction
   is a local minimum, but it does not always become 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 local maximum. To reverse only some common reference level. This value is instrumental
   in the propagation of its links (i.e., partial
   reversal), a node selects reference level. How delta is selected will
   be clarified in a new height that subsequent section. Finally, the second value
   representing the offset, i, is higher 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 own
   previous height and height,
   HEIGHT. Initially the height of some of its neighbors, but not
   higher each node in the network (other than
   the height destination) is set to NULL, HEIGHT = (-, -, -, -, i), where i is
   the unique ID of all the node. Subsequently, the height of its neighbors.

   The algorithms that belong to this general class are shown to each node i
   can be
   loop-free, and terminate modified in a finite number accordance with the rules of iterations to a
   destination-oriented DAG [3]. Furthermore, only nodes that have lost
   all downstream paths to the destination react to a given failure. protocol. The
   new algorithm incorporated into TORA for
   height of the maintaining routes
   process destination j is a member of this class, and thus inherits many always ZERO, HEIGHT = (0, 0, 0, 0, j),
   where j is the unique ID of these
   properties. The new the destination for which the algorithm
   is similar running). In addition to the partial reversal
   method in that it often reverses only some of its links. However, in
   order to provide own height, each node i maintains a partition detection capability, the rules
   height table with an entry HT_NEIGH[k] for each neighbor k. Initially
   the
   selection of a new height are significantly more complex. These rules
   are discussed in detail in section 2.2.4.2.

   The basic idea of each neighbor is set to NULL, HT_NEIGH[k] = (-, -, -,
   -, k). If the destination j is as follows. When a node loses its last downstream
   link (i.e., becomes a local minimum) as a result neighbor of a link failure,
   the node selects a new i, node i sets the
   corresponding height such that it becomes a global maximum
   by defining a new "reference level". By design, when a new reference
   level is defined, it is higher than any previously defined reference
   levels. This action results in link reversals that may cause other
   nodes entry to lose their last downstream link. Any such ZERO, HT_NEIGH[j] = (0, 0, 0, 0, j).

   Each node executes i (other than the destination) also maintains a
   partial reversal with respect to its neighbors that have heights
   already associated link-status
   table with the newest (highest) reference level. In this
   manner, the new reference level an entry LNK_STAT[k] for each link (i, k), where node k is propagated outward from the point
   a neighbor of node i. The status of the original failure (re-directing links in order to re-establish
   routes to is determined by the destination). This propagation will only extend through
   nodes that (as a result
   height of the initial link failure) have lost all
   routes to node, HEIGHT, and its height entry for the destination. Some nodes may experience neighbor,
   HT_NEIGH[k]. The link reversals is directed from all neighbors (as a result of the same initial link failure).
   Any such higher node must select a new height such that it becomes to the lower
   node. If a local
   maximum. This neighbor k is accomplished by defining a higher sub-level
   associated with the new reference level, which will be referred to as
   the "reflected reference level". This node essentially "reflects"
   this higher sub-level back toward the than node that originally defined
   the new reference level. Should this reflected reference level be
   propagated back to i, the originating node from all of its neighbors,
   then it link is determined that no route to the destination exists. The
   originating node has then detected marked
   upstream (UP). If a partition and can begin the
   process of erasing the invalid routes.

2.2.4 Detailed Description

   At any given time, an ordered quintuple, HEIGHT = (tau[i], oid[i],
   r[i], delta[i], i), neighbor k is associated with each lower than node i, where i is the
   unique ID of link is
   marked downstream (DN). If the node. Conceptually, neighbor's height entry, HT_NEIGH[k],
   is NULL, the quintuple associated with
   each node represents link is marked undirected (UN). Finally, if the height
   of the node as defined by two
   parameters: a reference level and a offset with respect to the
   reference level. The reference level i is represented by the first
   three values in the quintuple, while the offset NULL, then any neighbor's height that is represented by not NULL is
   considered lower, and the
   last two values. A new reference level corresponding link is defined each time a node
   loses its last marked downstream link due to
   (DN). When a new link failure. The first value
   representing the reference level, tau[i], (i, k) is established (i.e., node i has a time tag set new
   neighbor k), node i adds entries for the new neighbor to the
   "time" of height
   and link-status tables. If the link failure. For now, it new neighbor 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 destination j, the Network Time
   Protocol [6]. This time tag
   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 actually indicate or be "time,"
   nor will relaxation communicate any routing information upon link
   activation.

3.2 Creating Routes

   Creating routes requires use of the synchronization requirement invalidate QRY and UPD packets. A QRY packet
   consists of the
   protocol. The second value, oid[i], is destination-ID, j, which identifies the originator-ID (i.e., destination
   for which the
   unique ID algorithm is running. An UPD packet consists of the node that defined
   destination-ID, j, and the new reference level). This
   ensures that height of the reference levels can be totally ordered
   lexicographically, even if multiple nodes define reference levels due
   to failures node i that occur simultaneously (i.e., with equal time tags).
   The third value, r[i], is a single bit used to divide each of broadcasting
   the
   unique reference levels into two unique sub-levels. This bit is used
   to distinguish between packet, HEIGHT.

   Each node i (other than the original reference level and its
   corresponding, higher, reflected reference level. When destination) maintains a distinction route-required
   flag, which is not required, both initially un-set. Each node i (other than the original and reflected reference levels
   will simply be referred to as "reference levels." The first value
   representing
   destination) also maintains 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, time at which the second value
   representing last UPD packet was
   broadcast and the offset, i, time at which each link (i, k), where node k is the unique ID
   neighbor of the node itself. This
   ensures that nodes i, became active.

   When a node with no directed links and an un-set route-required flag
   requires a common reference level route to the destination, it broadcasts a QRY packet and equal values of
   delta (and in fact all nodes) can be totally ordered
   lexicographically at all times.

   Each
   sets its route-required flag. When a node i (other than receives a QRY it reacts
   as follows:

      a) If the destination) maintains receiving node i has no downstream links and its height,
   HEIGHT. Initially route-
      required flag is un-set, it re-broadcasts the height of each QRY packet and sets
      its route-required flag.

      b) If the receiving node in i has no downstream links and the network (other than route-
      required flag is set, it discards the destination) QRY packet.

      c) If the receiving node i has at least one downstream link and
      its height is set to NULL, it sets its height to HEIGHT = (-, -, -, -, (tau[k],
      oid[k], r[k], delta[k] + 1, i), where i HT_NEIGH[k] = (tau[k],
      oid[k], r[k], delta[k], k) is the unique ID of the node. Subsequently, the minimum height of each its non-NULL
      neighbors, and broadcasts an UPD packet.

      d) If the receiving node i
   can be modified in accordance with the rules of the protocol. The has at least one downstream link and
      its height of the destination j is always ZERO, HEIGHT = (0, 0, 0, 0, j),
   where j is non-NULL, it first compares the unique ID of time the destination for last UPD
      packet was broadcast to the time the link over which the algorithm 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 running). In addition to its own height, each
   established, it must broadcast a QRY packet.

   When a node i maintains receives an UPD packet from a neighbor k, node i first
   updates the entry HT_NEIGH[k] in its 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).
   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 destination j route-required flag is a neighbor set (which implies that the
      height of node i, i is NULL), node i sets the
   corresponding its height entry to ZERO, HT_NEIGH[j] HEIGHT = (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
      (tau[k], oid[k], r[k], delta[k] + 1, i)--where HT_NEIGH[k] =
      (tau[k], oid[k], r[k], delta[k], k) is determined by the minimum height of the node, HEIGHT, and its height entry for the neighbor,
   HT_NEIGH[k]. The link is directed from
      non-NULL neighbors, updates all the higher node to entries in its link-status
      table, un-sets the lower
   node. route-required flag and then broadcasts an UPD
      packet that contains its new height.

      b) If a neighbor k is higher than node i, the link is marked
   upstream (UP). If a neighbor k route-required flag is lower than not set, node i, the link is
   marked i need only react
      if it has lost its last downstream (DN). If the neighbor's height entry, HT_NEIGH[k],
   is NULL, link. The section on
      maintaining routes discusses the link is marked undirected (UN). Finally, reaction that occurs if reception
      of the height UPD packet resulted in loss of node i the last downstream link.

3.3 Maintaining Routes

   Maintaining routes is NULL, then only performed for nodes that have a height
   other than NULL. Furthermore, any neighbor's height that is not NULL is
   considered lower, and
   not used for the corresponding link computations. A node i is marked said to have no downstream
   (DN). When
   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 new link (i, k) failure).

         (tau[i], oid[i], r[i])=(t, i, 0), where t is established (i.e., the time of the
         failure.

         (delta[i],i)=(0, i)

         In essence, node i has defines a new
   neighbor k), reference level. The above
         assumes node i adds entries for the new neighbor to the height
   and link-status tables. has at least one upstream neighbor. If the new neighbor is the destination j, the
   corresponding node i
         has no upstream neighbors it simply sets its height entry is set to ZERO, HT_NEIGH[j] = (0, 0, 0, 0,
   j); otherwise it is set NULL.

      Case 2 (Propagate):

         Node i has no downstream links (due 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 a link
   activation.

2.2.4.1 Creating Routes

   Creating routes requires use of the QRY and UPD packets. A QRY packet
   consists reversal
         following reception of the destination-ID, j, which identifies the destination
   for which the algorithm is running. An an UPD packet consists of the
   destination-ID, j, packet) and the height 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 the node i that all
         neighbors k}

         (delta[i],i)=(delta[m]-1, i), where m is broadcasting the packet, HEIGHT.

   Each node i (other than lowest neighbor
         with the destination) maintains a route-required
   flag, which is initially un-set. Each maximum reference level defined above.

         In essence, node i (other than the
   destination) also maintains the time at which the last UPD packet was
   broadcast and propagates the time at which each link (i, k), where node k is
   neighbor reference level of node i, became active.

   When its
         highest neighbor and selects a node height that is lower than all
         neighbors with that reference level.

      Case 3 (Reflect):

         Node i has no directed downstream links and an un-set route-required flag
   requires a route (due to the destination, it broadcasts a QRY packet link reversal
         following reception of an UPD packet) and the ordered sets its route-required flag. When a
         (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 receives from all of its neighbors. Node i
         "reflects" back a QRY it reacts
   as follows:

      a) If higher sub-level by setting the receiving node bit r.

      Case 4 (Detect):

         Node i has no downstream links and its route-
      required flag is un-set, it re-broadcasts (due to a link reversal
         following reception of an UPD packet), the QRY packet and ordered sets
      its route-required flag.

      b) If the receiving
         (tau[k], oid[k], r[k]) are equal with r[k] = 1 for all
         neighbors k, and oid[k] = i (i.e., node i has no downstream links and the route-
      required flag is set, it discards defined the QRY packet.

      c) If level).

         (tau[i], oid[i], r[i])=(-, -, -)

         (delta[i],i)=(-, i)

         In essence, the receiving last reference level defined by node i has at least one downstream link been
         reflected and propagated back as a higher sub-level from all of
         its height is NULL, it sets its height neighbors. This corresponds 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 detection of a partition.
         Node i must initiate the minimum height process of its non-NULL
      neighbors, and broadcasts an UPD packet.

      d) If erasing invalid routes as
         discussed in the receiving node next section.

      Case 5 (Generate):

         Node i has at least one no downstream links (due to a link and
      its height is non-NULL, it first compares reversal
         following reception of an UPD packet), the time 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 last UPD
      packet was broadcast to
         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 over which the QRY
      packet was received became active. If an UPD packet has been
      broadcast since failure (which did not
         require reaction) between the link became active, time it discards propagated a reference
         level and the QRY
      packet; otherwise, it broadcasts reflected higher sub-level returned from all
         neighbors. This is not necessarily an UPD packet.

   If 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 has 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 route-required flag set when a new link height of the node i that is
   established, it must broadcast a QRY packet.
   broadcasting the packet, HEIGHT. When a node i receives an UPD packet
   from a neighbor k, node i first
   updates reacts as described in the entry HT_NEIGH[k] creating routes
   section and in its height table accordance with the height
   contained in cases outlined above. In the received UPD packet. Node event
   of the failure a link (i, k) that is not its last downstream link,
   node i then updates simply removes the entry entries HT_NEIGH[k] and LNK_STAT[k] in its
   height and link-status table tables.

3.4 Erasing Routes

   Following detection of a partition (case 4), node i sets its height
   and reacts as follows:

      a) If the route-required flag height entry for each neighbor k to NULL (unless the
   destination j is set (which implies that 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 i,
   (tau[i], oid[i], 1). In actuality the value r[i] = 1 need not be
   included since it is NULL), 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 HEIGHT =
      (tau[k], oid[k], r[k], delta[k] + 1, i)--where HT_NEIGH[k] =
      (tau[k], oid[k], r[k], delta[k], k) NULL (unless the destination j is a neighbor, in
      which case the minimum corresponding height of its
      non-NULL neighbors, entry is set to ZERO), updates
      all the entries in its link-status
      table, un-sets the route-required flag table and then broadcasts an UPD
      packet that contains its new height. a CLR
      packet.

      b) If the route-required flag is reference level in the CLR packet does not set, match the
      reference level of node i need only react
      if i; it has lost its last downstream link. The section on
      maintaining routes discusses sets the reaction that occurs if reception
      of height entry for each
      neighbor k (with the UPD packet resulted same reference level as the CLR packet) to
      NULL and updates the corresponding link-status table entries.
      Thus, the height of each node in loss the portion of the last downstream link.

2.2.4.2 Maintaining Routes

   Maintaining routes is only performed for nodes that have a height
   other than NULL. Furthermore, any neighbor's height network that
      was partitioned is set to NULL is
   not used for the computations. A and all invalid routes are erased.
      If (b) causes node i is said to have no lose its last downstream
   links if HEIGHT < HT_NEIGH[k] for all non-NULL neighbors k. This will
   result link, it reacts
      as in one case 1 of five possible reactions depending on maintaining routes.

3.5 Optimizing Routes

   TBD.

4 Protocol Specification
   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 state 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 node address and
   mask of the preceding event. Each node (other than interface may be added to 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 routing table.
   Additionally, TORA may respond to a link failure).

         (tau[i], oid[i], r[i])=(t, i, 0), where t is requests (i.e., QRY packets) for
   routes to destination addresses that match the time set of addresses
   identified by 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 interface configurations. PRO_MODE[i] (0=OFF, 1=ON)
   indicates if routes 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.

      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
         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.

2.2.4.3 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 Protocol Specification

   In the previous description of TORA, some simplifications were made
   for clarity. In particular, j was used to represent the unique ID of the destination for which the algorithm was running.  However, when
   forwarding IP datagrams in an internetwork, "destinations" to which
   routing is required are usually identified by an IP the
   corresponding interface address and mask.
   Together, these two values may correspond to an individual interface
   on a specific machine, or an aggregation 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 addresses (e.g., a
   network address).  Thus, in the subsequent discussion a destination
   "j" refers to a typical IP destination.  Another significant
   simplification pertains to the link between to nodes. In the most
   general case, a MANET router may have multiple wireless and hardwired
   interfaces with differing communication technologies.  Therefore, it
   is necessary to make a distiction between a physical communication
   "connection" between two routers and a logical communication "link"
   between two routers.  The previous description also ommited any
   discussion about how the next-hop forwarding decision is made.  It is
   assumed optimizations that the IP packet forwarding performed by the kernel in
   accordance with a standard IP routing table maintained in kernel
   space.  The TORA process must have access to the information in the
   table and be able to manipulate the table entries.  The details
   regarding how the routing table manipulations made by TORA will be
   described in detail in the subsequent sections. Since the subsequent
   description is intended to
   should be in sufficient detail to serve as a
   template for implementations, some additional terminology is defined
   first.

3.1 Terminology

   The following definitions are identical to the definitions used in
   the IMEP specification.  Many of these definitions may be replaced by
   or merged with those of the MANET working group's terminology draft
   [7] now under development.

   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 for the destination identified by an IP address.  Associated with each the corresponding
   interface is a
      physical layer communication device.  These devices may employ
      wireless or hardwired communications, 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 may
      simultaneousl employ devices ID (RID), which must be
   unique among the set of differing technologies. routers collectively running TORA.

4.2 State Variables

   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 each destination "j" 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 routing is required, a device attached to an interface of one
      MANET router and a device utilizating
   maintains the same communications
      technology attached following state variables.

   HEIGHT[j]    This router's height metric for routing to an interface on another MANET router.  From
      the perspective "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 given router, a connection 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 (interface,
      adjacency) pair.

   link:
      A "logical connection" consisting router
   maintains a separate instance of the logical *union* of one or
      more connections between two MANET routers.  Thus, a link may
      consist following state variables for
   each neighbor "k".

   HT_NEIGH[j][k]  The height metric of a heterogeneous combination neighbor "k."
   LNK_STAT[j][k]  The assigned status of connections through
      differing media using different communications technologies.

   neighbor:
      From the perspective of a given MANET router, a "neighbor" is any
      other router link to neighbor "k."
   TIME_ACT[j][k]  Time the link to neighbor "k" became active.

4.3 Auxiliary Variables

   For each destination "j" to which it routing is connected by required, a link.

   topology:
      A network router may
   maintain the following auxiliary variables. Although each of the
   variables can be viewed abstractly as a "graph" whose "topology"
      at any point computed based on the entries in time is defined by set the LNK_STAT table,
   maintaining the values continuously may facilitate implementation of "points" connected by
      "edges."  This term comes from
   the branch protocol.

   num_active[j]  Number of mathematics bearing neighbors (i.e., active links).
   num_down[j]    Number of links marked DN in the same name that is concerned with those properties LNK_STAT table.
   num_up[j]      Number of geometric
      configurations (such as point sets) which are unaltered by elastic
      deformations (such as stretching) 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 are homeomorphisms.

   physical-layer topology:
      A topology consisting comprises five components. The first three components of connections (the edges) through the
      *same* communications medium between devices (the points)
      communicating using
   Height data structure represent the *same* communications technology.

   network-layer topology:
      A topology consisting reference level of links (the edges) between MANET routers
      (the points) which 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 as in propagation of a reference level.
   Height.id    Unique id of the basis 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 MANET routing.  Since
      "links" a height are used throughout the logical union
   specification of physical-layer "connections," it
      follows that the "network-layer topology" 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 logical union unique id of the various "physical-layer topologies."

   IP routing fabric:
      The heterogeneous mixture given
                      destination.

4.5 Determination of communications media and technologies
      through which IP packets are forwarded whose topology is defined
      by Link Status

   Each entry in the network-layer topology.

3.2 State Variables

      For each destination "j" to which routing LNK_STAT table is required, a router
      maintains maintained in accordance with the
   following state variables.

      HEIGHT[j] rule.

   if        HT_NEIGH[k]==NULL    then   LNK_STAT[k]=UN;
   else if   HEIGHT==NULL         then   LNK_STAT[k]=DN;
   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 height metric TORA process receives notification of this router.
      RT_REQ[j]    Flag indicating route link status changes. It is
   anticipated that the TORA process will have access to all the destination is required.
      TIME_UPD[j]  Time an UPD packet was last sent by this router.

      For each destination "j"
   information about the connections. Thus, upon notification, TORA will
   have sufficient information to which routing determine if any new links have been
   established or any existing links have been severed. If either is required, a router
      maintains a separate instance of the following state variables
   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
      each neighbor "k".

      HT_NEIGH[j][k]  The height metric of neighbor "k."
      LNK_STAT[j][k]  The assigned status of a
   connection that was used in the link routing table to neighbor "k."
      TIME_ACT[j][k]  Time be severed without
   resulting in the corresponding link to neighbor being severed. In this case TORA
   must modify the appropriate routing table entries.

4.7.3 Link with a New Neighbor "k" became active.

3.3 Auxiliary Variables Established

   For each destination "j" "j":

   Set TIME_ACT[j][k] 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.

3.4 Height Data Structure

      Each HEIGHT[j] current time 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 increment num_active[j].

   If the height
      entry, while neighbor "k" is the last two components represent an offset with
      respect to 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 reference level. The five components of RT_REQ[j] flag is set && neighbor "k" is the Height
      data structure are as follows.

      Height.tau   Time destination "j"
   then I) else II).

      I) Set HEIGHT[j]=HT_NEIGH[j][k].  Increment HEIGHT[j].delta.  Set
      HEIGHT[j].id to the reference level was created.
      Height.oid   Unique unique id of this node.  Update LNK_STAT[j][n]
      for all n.  Unset the router that created RT_REQ[j] flag.  Set TIME_UPD[j] to the reference level.
      Height.r     Flag indicating if
      current time.  Create an UPD packet and place it is a reflected reference level.
      Height.delta Value used in propagation of a reference level.
      Height.id    Unique id of the router.

      To simplify notation in this specification, a height may queue to
      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 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
      protocol.

      NULL=(-,-,-,-,id)  An unknown or undefined height. Conceptually,
                         this can be thought of as current time.  Create an infinite height.

      ZERO=(0,0,0,0,id)  The assumed height of a given destination. Note
                         that here "id" is UPD packet
         and place it in the unique id of queue to be sent to all neighbors.  If the given
                         destination.

3.5 Determination of Link Status

      Each entry
         RT_REQ[j] flag is set, create a QRY packet and place it in the LNK_STAT table
         queue to be sent to all neighbors.  Event Processing Complete.

         B) If the RT_REQ[j] flag is maintained set, create a QRY packet and place
         it in accordance with the following rule.

      if        HT_NEIGH[k]==NULL 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   LNK_STAT[k]=UN; I) else if   HEIGHT==NULL 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   LNK_STAT[k]=DN; 1) else if   HT_NEIGH[k]<HEIGHT 2).

            1) If HEIGHT[j]==NULL then   LNK_STAT[k]=DN; a) else if   HT_NEIGH[k]>HEIGHT   then   LNK_STAT[k]=UP;

3.6 TORA Packet Formats

      TORA packets are encapsulated 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 IMEP messages, which are sent as
      "raw" IP datagrams with protocol number ?. The bit level format of the TORA packets has yet queue to
               be defined.

3.7 sent to all neighbors.  Event Processing

3.7.1 Initialization

   TBD.

3.7.2 Connection Status Change

   The TORA process receives notification of connection status changes
   from the the IMEP process. The interface between these two processes
   has yet Complete.

            2) Set HEIGHT[j].tau to be defined. However, it is anticipated that the TORA
   process will have access current time.  Set HEIGHT[j].oid
            to all the information maintained by unique id of this node.  Set HEIGHT[j].r=0.  Set
            HEIGHT[j].delta=0.  Set HEIGHT[j].id to the
   IMEP process about unique id of
            this node.  Update LNK_STAT[j][n] for all n.  Unset the connections. Thus, upon notification, TORA
   will have sufficient information
            RT_REQ[j] flag.  Set TIME_UPD[j] 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 (3.7.3 or 3.7.4).  In addition, current time.
            Create an UPD packet and place it is also
   possible for a connection that was used in the routing table queue to be
   severed without resulting in the corresponding link being severed. In
   this case TORA must modify the appropriate routing table entries as
   outlined in section 3.7.5.

3.7.3 Link with a New Neighbor "k" Established

   TBD.

3.7.4  Link with Prior Neighbor "k" Severed

   TBD.

3.7.5  Connection Used in Routing Table Severed
   TBD.

3.7.6 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 RTE_REQ RT_REQ[j] flag is set then I) else II).  nk with Prior Neighbor "k"
   Severed

      I) Event Processing Complete.

      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 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 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 RT_REQ[j] flag. If num_active>1 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.

3.7.7

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] HT_NEIGH[j][k], and LNK_STAT[j][k].  If the RT_REQ
   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 RT_REQ[j] flag.  Set TIME_UPD 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).

               a) Event Processing Complete.

               b) Set HEIGHT[j]=NULL.  Set TIME_UPD 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
                  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].oid==id, 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=0. num_down[j]=0.  Set num_up=0.
                     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 RT_REQ[j]
                     flag.  Set TIME_UPD 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
               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 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.

3.7.8

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=0. num_down[j]=0.  Set
      num_up=0.
      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>1 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==0 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).

               a) Event Processing Complete.

               b) Set HEIGHT[j]=NULL.  Set TIME_UPD 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
            RT_REQ[j] flag.  Set TIME_UPD 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

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
   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-manet-imep-spec-00.txt 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).
   [7] C. Perkins, Mobile Ad Hoc Networking Terminology, draft-ietf-
   manet-term-00.txt, (October 1997).

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