draft-ietf-manet-tora-spec-01.txt   draft-ietf-manet-tora-spec-02.txt 
IETF MANET Working Group V. Park
Internet Draft V. Park INTERNET-DRAFT Naval Research Laboratory
draft-ietf-manet-tora-spec-01.txt Naval Research Laboratory draft-ietf-manet-tora-spec-02.txt S. Corson
S. Corson
University of Maryland University of Maryland
Submitted: Aug 7, 1998 22 October 1999
Expires: Feb 7, 1999
Temporally-Ordered Routing Algorithm (TORA) Version 1 Temporally-Ordered Routing Algorithm (TORA) Version 1
Functional Specification Functional Specification
Status of this Memo Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working This document is an Internet-Draft and is NOT offered in accordance
documents of the Internet Engineering Task Force (IETF), its areas, with Section 10 of RFC2026, and the author does not provide the IETF
and its working groups. Note that other groups may also distribute with any rights other than to publish as an Internet-Draft.
working documents as Internet-Drafts.
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 Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
To learn the current status of any Internet-Draft, please check the The list of current Internet-Drafts can be accessed at
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow http://www.ietf.org/ietf/1id-abstracts.txt.
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or The list of Internet-Draft Shadow Directories can be accessed at
ftp.isi.edu (US West Coast). http://www.ietf.org/shadow.html.
Abstract Abstract
This document provides a detailed specification of Version 1 of the This document provides a detailed specification of the Temporally-
Temporally-Ordered Routing Algorithm (TORA)--a distributed routing Ordered Routing Algorithm (TORA)--a distributed routing protocol for
protocol for mobile, multihop, wireless networks. Its intended use is multihop networks. A key concept in the protocol's design is an
for routing of Internet Protocol (IP) datagrams within an autonmous attempt to de-couple (to the greatest extent possible) the generation
system. The basic, underlying algorithm is neither a distance-vector of far-reaching control message propagation from the dynamics of the
nor a link-state; it is one of a family of algorithms referred to as network topology. The basic, underlying algorithm is neither
``link reversal'' algorithms. The protocol's reaction is structured as traditionally distance-vector nor link-state; it is one of a family
a temporally-ordered sequence of diffusing computations, each of algorithms referred to as "link reversal" algorithms. In
computation consisting of a sequence of directed link reversals. The particular, the protocol's reaction to certain link failures is
protocol is highly adaptive, efficient and scalable; and is well- structured as a temporally-ordered sequence of diffusing
suited for use in large, dense, mobile networks. In these networks, computations, each computation consisting of a sequence of directed
the protocol's reaction to link failures typically involves only a link reversals. The protocol can operate in either a reactive,
localized ``single pass'' of the distributed algorithm. This desirable proactive or mixed mode.
behavior is achieved through the use of a physical 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.
1 Introduction 1 Introduction
The Temporally-Ordered Routing Algorithm (TORA) [1] is a highly The Temporally-Ordered Routing Algorithm (TORA) [1] is an adaptive
adaptive routing protocol, which has been tailored for operation in a routing protocol for multihop networks. It possesses the following
Mobile Ad hoc Network (MANET). Such a network can be envisioned as a attributes:
collection of routers (equipped with wireless receiver/transmitters), * Distributed execution,
which are free to move about arbitrarily. The status of the * Loop-free routing,
communication links between the routers, at any given time, is a * Multipath routing,
function of their positions, transmission power levels, antenna * Reactive or proactive route establishment and maintenance, and
patterns, cochannel interference levels, etc. The mobility of the * Minimization of communication overhead via localization of
routers and the variability of other connectivity factors result in a algorithmic reaction to topological changes when possible.
network with a potentially rapid and unpredictably changing topology. Its operation can be biased towards high reactivity (i.e., low time
Congested links are also an expected characteristic of such a network complexity) and bandwidth conservation (i.e., low communication
as wireless links inherently have significantly lower capacity than complexity) rather than routing optimality (i.e., continuous
hardwired links and are therefore more prone to congestion. TORA's shortest-path computation). Its design and flexability make it
design is predicated on the notion that a routing algorithm that is potentially well-suited for use mobile ad hoc networks (MANETs).
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 of topological
changes. 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. TORA
includes a secondary mechanism, which allows far-reaching control
message propagation as a means of infrequent route optimization and
soft-state route verification. This propogation occurs periodically
at a very low rate and is independent of the network topology
dynamics.
TORA is distributed in that nodes need only maintain information
about adjacent nodes (i.e., one hop knowledge). It guarantees all
routes are loop-free, and typically provides multiple routes for any
source/destination pair that requires a route. TORA is "source
initiated" and quickly creates a set 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 at all. Following topological changes that do
require reaction, the protocol quickly re-establishes valid routes.
This ability to initiate and react infrequently serves to minimize
communication overhead. Finally, in the event of a network partition,
the protocol detects the partition and erases all invalid routes.
2 MANET Routing Functional Description
A protocol for routing packets in a MANET can be divided into two TORA is based, in part, on the work presented in [2] and [3]. A key
functional distinct components--a link status sensing mechanism and a concept in the protocol's design is an attempt to de-couple (to the
routing mechanism. Although these two components are somewhat greatest extent possible) the generation of far-reaching control
orthogonal, they can be designed to work together in a synergistic message propagation from the dynamics of the network topology. The
fashion. Originally, these two mechanisms were being designed scope of TORA's control messaging is typically localized to a very
together as a part of the TORA protocol specification. However, since small set of nodes near a topological change. TORA includes a
the basic functionality provided by a link status sensing mechanism secondary mechanism that is independent of network topology dynamics,
is required by a variety of different routing mechanisms, it seemed which allows far-reaching control message propagation as a means of
appropriate that a more generic link status sensing mechanism should route optimization or soft-state route verification.
be designed 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 a routing mechanism. Thus, TORA provides
only the routing mechanism 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 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.
IMEP and TORA have been designed to work together synergistically. 2 Terminology
TORA relies 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 neighboring routers)
* Control packet delivery (i.e., reliable, in-order control packet
delivery to the set of neighbors)
* Network-layer address resolution and mapping
* Security authentication
IMEP provides a rich interface for use by a variety of different
mobile wireless routing protocols, which may have varied needs for
underlying services.
2.2 Temporally-Ordered Routing Algorithm 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
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).
This section provides a functional description of TORA. A detailed adjacency:
specification of TORA is provided in a subsequent section. The name given to an "interface on a neighboring router".
2.2.1 Notation medium:
A communication channel such as free space, cable or fiber through
which connections are established.
A network can be modeled as a graph with a finite set of nodes communications technology:
connected by a set of initially undirected links--wherea node The means employed by two devices to transfer information between
represents a router and a link represents communication connectivity them.
between two routers. Each node i in the network is assumed to have a
unique node identifier (ID), and each link (i, k) is assumed to allow
two-way communication (i.e., nodes connected by a link can
communicate with each other in either direction). Due to the mobility
of the nodes, the set 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 is said to be "downstream" from node i. For
each node i, we define the "neighbors" of i, to be the set of nodes k
such that there exists a link between nodes i and k. The following
assumptions account for the functionality provided by the IMEP. It is
assumed that each node i is always aware of its set of neighbors.
Additionally, it is assumed that when a node i transmits a packet, it
is broadcast to all of its neighbors and that all transmitted packets
are received correctly and in order of transmission.
2.2.2 Foundation and Basic Structure 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.
A logically separate version of TORA is run for each destination to link:
which routing is required. The following discussion focuses on a A "logical connection" consisting of the logical *union* of one or
single version running for a given destination, j. more connections between two MANET routers. Thus, a link may
consist of a heterogeneous combination of connections through
differing media using different communications technologies.
TORA can be separated into three basic functions: creating routes, neighbor:
maintaining routes, and erasing routes. Creating a route from a given From the perspective of a given MANET router, a "neighbor" is any
node to the destination requires establishment of a sequence of other router to which it is connected by a link.
directed links leading from the node to the destination. This
function is only initiated when a node with no directed links
requires a route to the destination. Thus, creating routes
essentially corresponds to assigning directions to links in an
undirected network or portion of the network. The method used to
accomplish this is an adaptation of the query/reply process described
in [2], which builds a directed acyclic graph (DAG) rooted at the
destination (i.e., the destination is the only node with no
downstream links). Such a DAG will be referred to as a "destination-
oriented" DAG. Maintaining routes refers to reacting to topological
changes in the network in a manner such that routes to the
destination are re-established within a finite time--meaning that its
directed portions return to a destination-oriented DAG within a
finite time. Gafni and Bertsekas (GB) described two algorithms [3],
which are members of a general class of algorithms designed to
accomplish this task. However, the GB algorithms are designed for
operation in connected networks. Due to instability exhibited by
these algorithms in portions of the network that become partitioned
from the destination, they are deemed unacceptable for the current
task. TORA incorporates a new algorithm, in the same general class,
that is more efficient in reacting to topological changes and capable
of detecting a network partition. This leads to the third function--
erasing routes. Upon detection of a network partition, all links (in
the portion of the network that has become partitioned from the
destination) must be marked as undirected to erase invalid routes.
TORA accomplishes these three functions through the use of three topology:
distinct control packets: query (QRY), update (UPD), and clear (CLR). A network can be viewed abstractly as a "graph" whose "topology"
QRY packets are used for creating routes; UPD packets are used for at any point in time is defined by set of "points" connected by
both creating and maintaining routes; and CLR packets are used for "edges." This term comes from the branch of mathematics bearing
erasing routes. 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.
2.2.3 General Class of Algorithms 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.
It is beneficial at this point to briefly review the earlier GB network-layer topology:
algorithms. Consider a connected DAG with at least one node (in A topology consisting of links (the edges) between MANET routers
addition to the destination) that has no downstream links. Such a DAG (the points) which is used as the basis for MANET routing. Since
will be referred to as "destination-disoriented." The following "links" are the logical union of physical-layer "connections," it
excerpts (punctuation added for clarity) from [3] loosely describe follows that the "network-layer topology" is the logical union of
the two algorithms designed to transform a destination-disoriented the various "physical-layer topologies."
DAG into a destination-oriented DAG.
Full Reversal Method: At each iteration, each node (other than the IP routing fabric:
destination) that has no outgoing links reverses the direction of all The heterogeneous mixture of communications media and technologies
its incoming links. through which IP packets are forwarded whose topology is defined
by the network-layer topology.
Partial Reversal Method: Every node i (other than the destination) 3 Protocol Functional Description
keeps a list of its neighboring nodes k that have reversed the
direction of the corresponding links (i, k). At each iteration, each
node i that has no outgoing links reverses the directions 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 two algorithms are subsequently re-stated in the context of a TORA has been designed to work on top of lower layer mechanisms or
generalized numbering scheme that will be summarize here; however, protocols that provide the following basic services between
much detail will be left out. For a thorough understanding, one neighboring routers:
should review the original paper. Essentially, a value is associated * Link status sensing and neighbor discovery
with each node at all times, and the values are such that they can be * Reliable, in-order control packet delivery
totally ordered. For example, in the full reversal method, a pair * Link and network layer address resolution and mapping
(alpha[i], i) is associated with each node where i is the unique ID * Security authentication
of the node and alpha[i] is an integer. The pairs can then be totally Events such as the reception of control messages and changes in
ordered lexicographically (e.g. (alpha[i], i) > (alpha[k], k) if connectivity with neighboring routers trigger TORA's algorithmic
alpha[i] > alpha[k] ,or if alpha[i] = alpha[k] and i > k). The value reactions.
associated 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 the destination-disoriented DAG 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 is a local
minimum with respect to its neighbors, h[i] < h[k] for all neighbors
k. To achieve the desired behavior in the full reversal method, node
i must select a new height such that it becomes a local maximum with
respect 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 that
k is a neighbor of i}+1 and broadcasts the value to all of its
neighbors. The partial reversal method can neither be viewed
conceptually nor explained as easily. Again, a node selects a new
height only when it is a local minimum, but it does not always become
a local maximum. To reverse only some of its links (i.e., partial
reversal), a node selects a new height that is higher than its own
previous height and the height of some of its neighbors, but not
higher than the height of all of its neighbors.
The algorithms that belong to this general class are shown to be A logically separate version of TORA is run for each "destination" to
loop-free, and terminate in a finite number of iterations to a which routing is required. The following discussion focuses on a
destination-oriented DAG [3]. Furthermore, only nodes that have lost single version of TORA running for a given destination. The term
all downstream paths to the destination react to a given failure. The destination is used herein to refer to a traditional IP routing
new algorithm incorporated into TORA for the maintaining routes destination, which is identified by an IP address and mask. Thus, the
process is a member of this class, and thus inherits many of these route to a destination may correspond to the individual address of an
properties. The new algorithm is similar to the partial reversal interface on a specific machine (i.e., a host route) or an
method in that it often reverses only some of its links. However, in aggregation of addresses (i.e., a network route). TORA assigns
order to provide a partition detection capability, the rules for the directions to the links between routers to form a routing structure
selection of a new height are significantly more complex. These rules that is used to forward datagrams to the destination. A router
are discussed in detail in section 2.2.4.2. 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.
The basic idea is as follows. When a node loses its last downstream TORA can be separated into four basic functions: creating routes,
link (i.e., becomes a local minimum) as a result of a link failure, maintaining routes, erasing routes, and optimizing routes. Creating
the node selects a new height such that it becomes a global maximum routes corresponds to the selection of heights to form a directed
by defining a new "reference level". By design, when a new reference sequence of links leading to the destination in a previously
level is defined, it is higher than any previously defined reference undirected network or portion of the network. Maintaining routes
levels. This action results in link reversals that may cause other refers to the adapting the routing structure in response to network
nodes to lose their last downstream link. Any such node executes a topological changes. For example, following the loss of some router's
partial reversal with respect to its neighbors that have heights last downstream link, some directed paths may temporarily no longer
already associated with the newest (highest) reference level. In this lead to the destination--resulting a sequence of directed link
manner, the new reference level is propagated outward from the point reversals (caused by the re-selection of router heights) to re-orient
of the original failure (re-directing links in order to re-establish the routing structure such that all directed paths again lead to the
routes to the destination). This propagation will only extend through destination. In cases where the network becomes partitioned, links in
nodes that (as a result of the initial link failure) have lost all the portion of the network that has become partitioned from the
routes to the destination. Some nodes may experience link reversals destination must be marked as undirected to erase invalid routes.
from all neighbors (as a result of the same initial link failure). During this erasing routes process, routers set their heights to null
Any such node must select a new height such that it becomes a local and their adjacent links become undirected. Finally, TORA includes a
maximum. This is accomplished by defining a higher sub-level secondary mechanism for route optimization, in which routers re-
associated with the new reference level, which will be referred to as select their heights in order to improve the routing structure. TORA
the "reflected reference level". This node essentially "reflects" accomplishes these four functions through the use of four distinct
this higher sub-level back toward the node that originally defined control packets: query (QRY), update (UPD), clear (CLR), and
the new reference level. Should this reflected reference level be optimization (OPT).
propagated back to the originating node from all of its neighbors,
then it is determined that no route to the destination exists. The
originating node has then detected a partition and can begin the
process of erasing the invalid routes.
2.2.4 Detailed Description 3.1 Protocol State
At any given time, an ordered quintuple, HEIGHT = (tau[i], oid[i], 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 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 unique ID of the node. Conceptually, the quintuple associated with
each node represents the height of the node as defined by two each node represents the height of the node as defined by two
parameters: a reference level and a offset with respect to the parameters: a reference level and an offset with respect to the
reference level. The reference level is represented by the first reference level. The reference level is represented by the first
three values in the quintuple, while the offset is represented by the 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 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 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 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 "time" of the link failure. For now, it is assumed that all nodes
have synchronized clocks. This could be accomplished via interface have synchronized clocks. This could be accomplished via interface
with an external time source such as the Global Positioning System with an external time source such as the Global Positioning System
(GPS) [5] or through use of an algorithm such as the Network Time (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," Protocol [6]. This time tag need not actually indicate or be "time,"
skipping to change at page 8, line 42 skipping to change at page 6, line 49
considered lower, and the corresponding link is marked downstream 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 (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 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 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, 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 j); otherwise it is set to NULL, HT_NEIGH[k] = (-, -, -, -, k). The
corresponding link-status entry, LNK_STAT[k], is set as outlined corresponding link-status entry, LNK_STAT[k], is set as outlined
above. Nodes need not communicate any routing information upon link above. Nodes need not communicate any routing information upon link
activation. activation.
2.2.4.1 Creating Routes 3.2 Creating Routes
Creating routes requires use of the QRY and UPD packets. A QRY packet Creating routes requires use of the QRY and UPD packets. A QRY packet
consists of the destination-ID, j, which identifies the destination consists of the destination-ID, j, which identifies the destination
for which the algorithm is running. An UPD packet consists of the 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 destination-ID, j, and the height of the node i that is broadcasting
the packet, HEIGHT. the packet, HEIGHT.
Each node i (other than the destination) maintains a route-required Each node i (other than the destination) maintains a route-required
flag, which is initially un-set. Each node i (other than the flag, which is initially un-set. Each node i (other than the
destination) also maintains the time at which the last UPD packet was destination) also maintains the time at which the last UPD packet was
skipping to change at page 10, line 6 skipping to change at page 8, line 13
(tau[k], oid[k], r[k], delta[k], k) is the minimum height of its (tau[k], oid[k], r[k], delta[k], k) is the minimum height of its
non-NULL neighbors, updates all the entries in its link-status non-NULL neighbors, updates all the entries in its link-status
table, un-sets the route-required flag and then broadcasts an UPD table, un-sets the route-required flag and then broadcasts an UPD
packet that contains its new height. packet that contains its new height.
b) If the route-required flag is not set, node i need only react 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 if it has lost its last downstream link. The section on
maintaining routes discusses the reaction that occurs if reception maintaining routes discusses the reaction that occurs if reception
of the UPD packet resulted in loss of the last downstream link. of the UPD packet resulted in loss of the last downstream link.
2.2.4.2 Maintaining Routes 3.3 Maintaining Routes
Maintaining routes is only performed for nodes that have a height Maintaining routes is only performed for nodes that have a height
other than NULL. Furthermore, any neighbor's height that is NULL is 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 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 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 result in one of five possible reactions depending on the state of
the node and the preceding event. Each node (other than the the node and the preceding event. Each node (other than the
destination) that has no downstream links modifies its height, HEIGHT destination) that has no downstream links modifies its height, HEIGHT
= (tau[i], oid[i], r[i], delta[i], i), as follows: = (tau[i], oid[i], r[i], delta[i], i), as follows:
skipping to change at page 12, line 11 skipping to change at page 10, line 18
node i updates all the entries in its link-status table; and node i updates all the entries in its link-status table; and
broadcasts an UPD packet to all neighbors k. The UPD packet consists 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 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 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 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 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, 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 node i simply removes the entries HT_NEIGH[k] and LNK_STAT[k] in its
height and link-status tables. height and link-status tables.
2.2.4.3 Erasing Routes 3.4 Erasing Routes
Following detection of a partition (case 4), node i sets its height Following detection of a partition (case 4), node i sets its height
and the height entry for each neighbor k to NULL (unless the and the height entry for each neighbor k to NULL (unless the
destination j is a neighbor, in which case the corresponding height destination j is a neighbor, in which case the corresponding height
entry is set to ZERO), updates all the entries in its link-status 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 table, and broadcast a CLR packet. The CLR packet consists of the
destination-ID, j, and the reflected reference level of node i, 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 (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 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: node i receives a CLR packet from a neighbor k it reacts as follows:
skipping to change at page 12, line 39 skipping to change at page 10, line 46
b) If the reference level in the CLR packet does not match the 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 reference level of node i; it sets the height entry for each
neighbor k (with the same reference level as the CLR packet) to neighbor k (with the same reference level as the CLR packet) to
NULL and updates the corresponding link-status table entries. NULL and updates the corresponding link-status table entries.
Thus, the height of each node in the portion of the network that 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. 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 If (b) causes node i to lose its last downstream link, it reacts
as in case 1 of maintaining routes. as in case 1 of maintaining routes.
3 Protocol Specification 3.5 Optimizing Routes
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 address and mask.
Together, these two values may correspond to an individual interface
on a specific machine, or an aggregation 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 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 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
identified by an IP address. Associated with each interface is a
physical layer communication device. These devices may employ
wireless or hardwired communications, and a router may
simultaneousl 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: TBD.
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 utilizating 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: 4 Protocol Specification
A "logical connection" consisting of the logical *union* of one or The subsequent specification is intended to be of sufficient detail
more connections between two MANET routers. Thus, a link may to serve as a template for implementations.
consist of a heterogeneous combination of connections through
differing media using different communications technologies.
neighbor: 4.1 Configuration
From the perspective of a given MANET router, a "neighbor" is any
other router to which it is connected by a link.
topology: For each interface "i" of a router, the following configuration
A network can be viewed abstractly as a "graph" whose "topology" parameters are maintained.
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: IP_ADDR[i] IP address of interface.
A topology consisting of connections (the edges) through the ADDR_MASK[i] Address mask of interface.
*same* communications medium between devices (the points) PRO_MODE[i] Indicates reactive/proactive mode of operation.
communicating using the *same* communications technology. OPT_MODE[i] Indicates optimization mode of operation.
OPT_PERIOD[i] Period for optimization mechanism.
network-layer topology: For each interface, a network route corresponding to the address and
A topology consisting of links (the edges) between MANET routers mask of the interface may be added to the routing table.
(the points) which is used as the basis for MANET routing. Since Additionally, TORA may respond to requests (i.e., QRY packets) for
"links" are the logical union of physical-layer "connections," it routes to destination addresses that match the set of addresses
follows that the "network-layer topology" is the logical union of identified by the interface configurations. PRO_MODE[i] (0=OFF, 1=ON)
the various "physical-layer topologies." 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.
IP routing fabric: A router is also configured with a router ID (RID), which must be
The heterogeneous mixture of communications media and technologies unique among the set of routers collectively running TORA.
through which IP packets are forwarded whose topology is defined
by the network-layer topology.
3.2 State Variables 4.2 State Variables
For each destination "j" to which routing is required, a router For each destination "j" to which routing is required, a router
maintains the following state variables. maintains the following state variables.
HEIGHT[j] The height metric of this router. HEIGHT[j] This router's height metric for routing to "j".
RT_REQ[j] Flag indicating route to the destination is required. PRO_MODE[j] Indicates reactive/proactive mode of operation for "j".
TIME_UPD[j] Time an UPD packet was last sent by this router. 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 For each destination "j" to which routing is required, a router
maintains a separate instance of the following state variables for maintains a separate instance of the following state variables for
each neighbor "k". each neighbor "k".
HT_NEIGH[j][k] The height metric of 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." LNK_STAT[j][k] The assigned status of the link to neighbor "k."
TIME_ACT[j][k] Time the link to neighbor "k" became active. TIME_ACT[j][k] Time the link to neighbor "k" became active.
3.3 Auxiliary Variables 4.3 Auxiliary Variables
For each destination "j" to which routing is required, a router For each destination "j" to which routing is required, a router may
may maintain the following auxiliary variables. Although each of maintain the following auxiliary variables. Although each of the
the variables can be computed based on the entries in the LNK_STAT variables can be computed based on the entries in the LNK_STAT table,
table, maintaining the values continuously may facilitate maintaining the values continuously may facilitate implementation of
implementation of the protocol. the protocol.
num_active[j] Number of neighbors (i.e., active links). num_active[j] Number of neighbors (i.e., active links).
num_down[j] Number of links marked DN in the LNK_STAT table. 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. num_up[j] Number of links marked UP in the LNK_STAT table.
3.4 Height Data Structure 4.4 Height Data Structure
Each HEIGHT[j] and HT_NEIGH[j][k] entry requires a 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 that comprises five components. The first three components of the
Height data structure represent the reference level of the height Height data structure represent the reference level of the height
entry, while the last two components represent an offset with entry, while the last two components represent an offset with respect
respect to the reference level. The five components of the Height to the reference level. The five components of the Height data
data structure are as follows. structure are as follows.
Height.tau Time the reference level was created. Height.tau Time the reference level was created.
Height.oid Unique id of the router that created the reference level. Height.oid Unique id of the router that created the reference level.
Height.r Flag indicating if it is a reflected reference level. Height.r Flag indicating if it is a reflected reference level.
Height.delta Value used in propagation of a reference level. Height.delta Value used in propagation of a reference level.
Height.id Unique id of the router. Height.id Unique id of the router to which the height metric refers.
To simplify notation in this specification, a height may be To simplify notation in this specification, a height may be written
written as an ordered quintuple--e.g., as an ordered quintuple--e.g., HEIGHT[j]=(tau,oid,r,delta,id). The
HEIGHT[j]=(tau,oid,r,delta,id). The following two predefined following two predefined values for a height are used throughout the
values for a height are used throughout the specification of the specification of the protocol.
protocol.
NULL=(-,-,-,-,id) An unknown or undefined height. Conceptually, NULL=(-,-,-,-,id) An unknown or undefined height. Conceptually,
this can be thought of as an infinite height. this can be thought of as an infinite height.
ZERO=(0,0,0,0,id) The assumed height of a given destination. Note ZERO=(0,0,0,0,id) The assumed height of a given destination. Note
that here "id" is the unique id of the given that here "id" is the unique id of the given
destination. destination.
3.5 Determination of Link Status 4.5 Determination of Link Status
Each entry in the LNK_STAT table is maintained in accordance with Each entry in the LNK_STAT table is maintained in accordance with the
the following rule. following rule.
if HT_NEIGH[k]==NULL then LNK_STAT[k]=UN; if HT_NEIGH[k]==NULL then LNK_STAT[k]=UN;
else if HEIGHT==NULL then LNK_STAT[k]=DN; 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]=DN;
else if HT_NEIGH[k]>HEIGHT then LNK_STAT[k]=UP; else if HT_NEIGH[k]>HEIGHT then LNK_STAT[k]=UP;
3.6 TORA Packet Formats 4.6 TORA Packet Formats
TORA packets are encapsulated in IMEP messages, which are sent as TBD.
"raw" IP datagrams with protocol number ?. The bit level format of
the TORA packets has yet to be defined.
3.7 Event Processing 4.7 Event Processing
3.7.1 Initialization 4.7.1 Initialization
TBD. TBD
3.7.2 Connection Status Change 4.7.2 Connection Status Change
The TORA process receives notification of connection status changes The TORA process receives notification of link status changes. It is
from the the IMEP process. The interface between these two processes anticipated that the TORA process will have access to all the
has yet to be defined. However, it is anticipated that the TORA information about the connections. Thus, upon notification, TORA will
process will have access to all the information maintained by the have sufficient information to determine if any new links have been
IMEP process about the connections. Thus, upon notification, TORA established or any existing links have been severed. If either is the
will have sufficient information to determine if any new links have case, then TORA must proceed as outlined in appropriate subsequent
been established or any existing links have been severed. If either section (4.7.3 or 4.7.4). In addition, it is also possible for a
is the case, then TORA must proceed as outlined in appropriate connection that was used in the routing table to be severed without
subsequent section (3.7.3 or 3.7.4). In addition, it is also resulting in the corresponding link being severed. In this case TORA
possible for a connection that was used in the routing table to be must modify the appropriate routing table entries.
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 4.7.3 Link with a New Neighbor "k" Established
TBD. For each destination "j":
3.7.4 Link with Prior Neighbor "k" Severed Set TIME_ACT[j][k] to the current time and increment num_active[j].
TBD. 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.
3.7.5 Connection Used in Routing Table Severed If the RT_REQ[j] flag is set && neighbor "k" is the destination "j"
TBD. then I) else II).
3.7.6 QRY Packet Regarding Destination "j" Received from Neighbor "k" 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.
If the RTE_REQ flag set then I) else II). nk with Prior Neighbor "k" II) If PRO_MODE==1 and HEIGHT[j]!=NULL then A) else B).
Severed
A) Set TIME_UPD[j] to the current time. Create an UPD packet
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. I) Event Processing Complete.
II) If HEIGHT[j].r==0 then A) else B). II) If HEIGHT[j].r==0 then A) else B).
A) If TIME_ACT[j][k]>TIME_UPD[j] then 1) else 2). A) If TIME_ACT[j][k]>TIME_UPD[j] then 1) else 2).
1) Set TIME_UPD to the current time. Create an UPD packet 1) Set TIME_UPD[j] to the current time. Create an UPD
and place it in the queue to be sent to all neighbors. Event packet and place it in the queue to be sent to all
Processing Complete. neighbors. Event Processing Complete.
2) Event Processing Complete. 2) Event Processing Complete.
B) If HT_NEIGH[j][n].r==0 for any n then 1) else 2). 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 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 entries with HT_NEIGH[j][n].r==0. Set
HEIGHT[j]=HT_NEIGH[j][m]. Increment HEIGHT.delta. Set HEIGHT[j]=HT_NEIGH[j][m]. Increment HEIGHT.delta. Set
HEIGHT[j].id to the unique id of this node. Update HEIGHT[j].id to the unique id of this node. Update
LNK_STAT[j][n] for all n. Set TIME_UPD to the current time. LNK_STAT[j][n] for all n. Set TIME_UPD[j] to the current
Create an UPD packet and place it in the queue to be sent to time. Create an UPD packet and place it in the queue to be
all neighbors. Event Processing Complete. sent to all neighbors. Event Processing Complete.
2) Set the RT_REQ flag. If num_active>1 then a) else b). 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 a) Create a QRY packet and place it in the queue to be
sent to all neighbors. Event Processing Complete. sent to all neighbors. Event Processing Complete.
b) Event Processing Complete. b) Event Processing Complete.
3.7.7 UPD Packet Regarding Destination "j" Received from Neighbor "k" 4.7.6 UPD Packet Regarding Destination "j" Received from Neighbor "k"
Update the entries HT_NEIGH[j][k] and LNK_STAT[j][k]. If the RT_REQ If MODE_SEQ field of received packet is greater than MODE_SEQ[j],
flag is set and HT_NEIGH[j][k].r==0 then I) else II). 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 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] HEIGHT[j].id to the unique id of this node. Update LNK_STAT[j][n]
for all n. Unset the RT_REQ flag. Set TIME_UPD to the current for all n. Unset the RT_REQ[j] flag. Set TIME_UPD[j] to the
time. Create an UPD packet and place it in the queue to be sent to current time. Create an UPD packet and place it in the queue to
all neighbors. Event Processing Complete. be sent to all neighbors. Event Processing Complete.
II) If num_down[j]==0 then A) else B). II) If num_down[j]==0 then A) else B).
A) If num_up[j]==0 then 1) else 2). A) If num_up[j]==0 then 1) else 2).
1) If HEIGHT[j]==NULL then a) else b). 1) If HEIGHT[j]==NULL then a) else b).
a) Event Processing Complete. a) Event Processing Complete.
b) Set HEIGHT[j]=NULL. Set TIME_UPD to the current time. b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current
Create an UPD packet and place it in the queue to be sent time. Create an UPD packet and place it in the queue to
to all neighbors. Event Processing Complete. be sent to all neighbors. Event Processing Complete.
2) If all HT_NEIGH[j][n], for all n such that HT_NEIGH[j][n] 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). 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 a) If HT_NEIGH[j][n].r==0, for any n such that
HT_NEIGH[j][n] is non-NULL, then i) else ii). HT_NEIGH[j][n] is non-NULL, then i) else ii).
i) Set HEIGHT[j]=HT_NEIGH[j][n], where n is such that 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 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 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id
of this node. Update LNK_STAT[j][n] for all n. Set of this node. Update LNK_STAT[j][n] for all n. Set
TIME_UPD to the current time. Create an UPD packet and TIME_UPD[j] to the current time. Create an UPD packet
place it in the queue to be sent to all neighbors. and place it in the queue to be sent to all neighbors.
Event Processing Complete. Event Processing Complete.
ii) If HT_NEIGH[j].oid==id, where id is the unique id ii) If HT_NEIGH[j][n].oid==id, where n is such that
of this node, then x) else y). 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 x) Save the current values of HEIGHT[j].tau and
HEIGHT[j].oid in temporary variables. Set HEIGHT[j].oid in temporary variables. Set
HEIGHT[j]=NULL. Set num_down=0. Set num_up=0. For HEIGHT[j]=NULL. Set num_down[j]=0. Set
every active link n, if the neighbor connected via num_up[j]=0. For every active link n, if the
link n is the destination j, set neighbor connected via link n is the destination j,
HT_NEIGH[j][n]=ZERO and LNK_STAT[j][n]=DN else set set HT_NEIGH[j][n]=ZERO and LNK_STAT[j][n]=DN else
HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. Create a set HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN.
CLR packet, with the previously saved values of tau Create a CLR packet, with the previously saved
and oid, and place it in the queue to be sent to values of tau and oid, and place it in the queue to
all neighbors. Event Processing Complete. be sent to all neighbors. Event Processing
Complete.
y) Set HEIGHT[j].tau to the current time. Set y) Set HEIGHT[j].tau to the current time. Set
HEIGHT[j].oid to the unique id of this node. Set HEIGHT[j].oid to the unique id of this node. Set
HEIGHT[j].r=0. Set HEIGHT[j].delta=0. Set HEIGHT[j].r=0. Set HEIGHT[j].delta=0. Set
HEIGHT[j].id to the unique id of this node. Update HEIGHT[j].id to the unique id of this node. Update
LNK_STAT[j][n] for all n. Unset the RT_REQ flag. LNK_STAT[j][n] for all n. Unset the RT_REQ[j]
Set TIME_UPD to the current time. Create an UPD flag. Set TIME_UPD[j] to the current time. Create
packet and place it in the queue to be sent to all an UPD packet and place it in the queue to be sent
neighbors. Event Processing Complete. to all neighbors. Event Processing Complete.
b) Find n such that HT_NEIGH[j][n] is the maximum of all 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] non-NULL height entries. Find m such that HT_NEIGH[j][m]
is the minimum of the non-NULL height entries with the is the minimum of the non-NULL height entries with the
same reference level as HT_NEIGH[j][n]. Set same reference level as HT_NEIGH[j][n]. Set
HEIGHT[j]=HT_NEIGH[j][m]. Decrement HEIGHT.delta. Set HEIGHT[j]=HT_NEIGH[j][m]. Decrement HEIGHT.delta. Set
HEIGHT[j].id to the unique id of this node. Update HEIGHT[j].id to the unique id of this node. Update
LNK_STAT[j][n] for all n. Set TIME_UPD to the current 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 time. Create an UPD packet and place it in the queue to
be sent to all neighbors. Event Processing Complete. be sent to all neighbors. Event Processing Complete.
B) 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)
3.7.8 CLR Packet Regarding Destination "j" Received from Neighbor "k" 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 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). 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 I) Save the current values of HEIGHT[j].tau and HEIGHT[j].oid in
temporary variables. Set Height[j]=NULL. Set num_down=0. Set temporary variables. Set Height[j]=NULL. Set num_down[j]=0. Set
num_up=0. For every active link n, if the neighbor connected via num_up[j]=0. For every active link n, if the neighbor connected
link n is the destination j, set HT_NEIGH[j][n]=ZERO and 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]=DN else set HT_NEIGH[j][n]=NULL and
LNK_STAT[j][n]=UN. If num_active>1 then A) else B). 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 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. and oid, and place it in the queue to be sent to all neighbors.
Event Processing Complete. Event Processing Complete.
B) Event Processing Complete. B) Event Processing Complete.
II) Set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN. For all n such 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 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 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 then A) HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. If num_down[j]==0 then
else B). A) else B).
A) If num_up==0 then 1) else 2). A) If num_up==0 then 1) else 2).
1) If HEIGHT[j]==NULL then a) else b). 1) If HEIGHT[j]==NULL then a) else b).
a) Event Processing Complete. a) Event Processing Complete.
b) Set HEIGHT[j]=NULL. Set TIME_UPD to the current time. b) Set HEIGHT[j]=NULL. Set TIME_UPD[j] to the current
Create an UPD packet and place it in the queue to be sent time. Create an UPD packet and place it in the queue to
to all neighbors. Event Processing Complete. be sent to all neighbors. Event Processing Complete.
2) Set HEIGHT[j].tau to the current time. Set HEIGHT[j].oid 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 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 HEIGHT[j].delta=0. Set HEIGHT[j].id to the unique id of
node. Update LNK_STAT[j][n] for all n. Unset the RT_REQ this node. Update LNK_STAT[j][n] for all n. Unset the
flag. Set TIME_UPD to the current time. Create an UPD packet RT_REQ[j] flag. Set TIME_UPD[j] to the current time.
and place it in the queue to be sent to all neighbors. Event Create an UPD packet and place it in the queue to be sent to
Processing Complete. all neighbors. Event Processing Complete.
B) Event Processing Complete. B) Event Processing Complete.
4 Security Considerations 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. TBD.
References References
[1] V. Park and M. S. Corson, A Highly Adaptive Distributed Routing [1] V. Park and M. S. Corson, A Highly Adaptive Distributed Routing
Algorithm for Mobile Wireless Networks, Proc. IEEE INFOCOM '97, Kobe, Algorithm for Mobile Wireless Networks, Proc. IEEE INFOCOM '97, Kobe,
Japan (1997). Japan (1997).
[2] M.S. Corson and A. Ephremides, A distributed routing algorithm [2] M.S. Corson and A. Ephremides, A distributed routing algorithm
for mobile wireless networks, Wireless Networks 1 (1995). for mobile wireless networks, Wireless Networks 1 (1995).
[3] E. Gafni and D. Bertsekas, Distributed algorithms for generating [3] E. Gafni and D. Bertsekas, Distributed algorithms for generating
loop-free routes in networks with frequently changing topology, IEEE loop-free routes in networks with frequently changing topology, IEEE
Trans. Commun. (January 1981). Trans. Commun. (January 1981).
[4] M.S. Corson and V. Park, An Internet MANET Encapsulation Protocol [4] M.S. Corson and V. Park, An Internet MANET Encapsulation Protocol
(IMEP), draft-ietf-manet-imep-spec-00.txt (IMEP), draft-ietf-
[5] NAVSTAR GPS user equipment introduction, MZ10298.001 (February [5] NAVSTAR GPS user equipment introduction, MZ10298.001 (February
1991). 1991).
[6] D. Mills, Network time protocol, specification, implementation [6] D. Mills, Network time protocol, specification, implementation
and analysis, Internet RFC-1119 (September 1989). 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 Author's Addresses
Vincent D. Park Vincent D. Park
Information Technology Division Information Technology Division
Naval Research Laboratory Naval Research Laboratory
Washington, DC 20375 Washington, DC 20375
(202) 767-5098 (202) 767-5098
vpark@itd.nrl.navy.mil vpark@itd.nrl.navy.mil
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/