draft-ietf-manet-tora-spec-02.txt   draft-ietf-manet-tora-spec-03.txt 
IETF MANET Working Group V. Park IETF MANET Working Group V. Park
INTERNET-DRAFT Naval Research Laboratory INTERNET-DRAFT Naval Research Laboratory
draft-ietf-manet-tora-spec-02.txt S. Corson draft-ietf-manet-tora-spec-03.txt S. Corson
University of Maryland University of Maryland
22 October 1999 24 November 2000
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 and is NOT offered in accordance 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 Section 10 of RFC2026, and the author does not provide the IETF
with any rights other than to publish as an Internet-Draft. with any rights other than to publish as an Internet-Draft.
skipping to change at page 1, line 34 skipping to change at page 1, line 35
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Abstract Abstract
This document provides a detailed specification of the Temporally- This document provides both a functional description and a detailed
Ordered Routing Algorithm (TORA)--a distributed routing protocol for specification of the Temporally-Ordered Routing Algorithm (TORA)--a
multihop networks. A key concept in the protocol's design is an distributed routing protocol for multihop networks. A key concept in
attempt to de-couple (to the greatest extent possible) the generation the protocol's design is an attempt to de-couple the generation of
of far-reaching control message propagation from the dynamics of the far-reaching control message propagation from the dynamics of the
network topology. The basic, underlying algorithm is neither network topology. The basic, underlying algorithm is neither
traditionally distance-vector nor link-state; it is one of a family distance-vector nor link-state; it is a member of a class referred to
of algorithms referred to as "link reversal" algorithms. In as link-reversal algorithms. The protocol builds a loop-free,
particular, the protocol's reaction to certain link failures is multipath routing structure that is used as the basis for forwarding
structured as a temporally-ordered sequence of diffusing traffic to a given destination. The protocol can simultaneously
computations, each computation consisting of a sequence of directed support both source-initiated, on-demand routing for some
link reversals. The protocol can operate in either a reactive, destinations and destination-initiated, proactive routing for other
proactive or mixed mode. destinations.
1 Introduction 1 Introduction
The Temporally-Ordered Routing Algorithm (TORA) [1] is an adaptive The Temporally-Ordered Routing Algorithm (TORA) [1] is an adaptive
routing protocol for multihop networks. It possesses the following routing protocol for multihop networks that possesses the following
attributes: attributes:
* Distributed execution, * Distributed execution,
* Loop-free routing, * Loop-free routing,
* Multipath routing, * Multipath routing,
* Reactive or proactive route establishment and maintenance, and * Reactive or proactive route establishment and maintenance, and
* Minimization of communication overhead via localization of * Minimization of communication overhead via localization of
algorithmic reaction to topological changes when possible. algorithmic reaction to topological changes.
Its operation can be biased towards high reactivity (i.e., low time TORA is distributed, in that routers need only maintain information
complexity) and bandwidth conservation (i.e., low communication about adjacent routers (i.e., one-hop knowledge). Like a distance-
complexity) rather than routing optimality (i.e., continuous vector routing approach, TORA maintains state on a per-destination
shortest-path computation). Its design and flexability make it basis. However, TORA does not continuously execute a shortest-path
potentially well-suited for use mobile ad hoc networks (MANETs). computation and thus the metric used to establish the routing
structure does not represent a distance. The destination-oriented
TORA is based, in part, on the work presented in [2] and [3]. A key nature of the routing structure in TORA supports a mix of reactive
concept in the protocol's design is an attempt to de-couple (to the and proactive routing on a per-destination basis. During reactive
greatest extent possible) the generation of far-reaching control operation, sources initiate the establishment of routes to a given
message propagation from the dynamics of the network topology. The destination on-demand. This mode of operation may be advantageous in
scope of TORA's control messaging is typically localized to a very dynamic networks with relatively sparse traffic patterns, since it
small set of nodes near a topological change. TORA includes a may not be necessary (nor desirable) to maintain routes between every
secondary mechanism that is independent of network topology dynamics, source/destination pair at all times. At the same time, selected
which allows far-reaching control message propagation as a means of destinations can initiate proactive operation, resembling traditional
route optimization or soft-state route verification. table-driven routing approaches. This allows routes to be proactively
maintained to destinations for which routing is consistently or
frequently required (e.g., servers or gateways to hardwired
infrastructure).
TORA is distributed, in that nodes need only maintain information TORA is designed to minimize the communication overhead associated
about adjacent nodes (i.e., one-hop knowledge). Like a distance- with adapting to network topological changes. The scope of TORA's
vector routing approaches, TORA maintains state on a per-destination control messaging is typically localized to a very small set of nodes
basis. Its design allows reactive operation, in which sources near a topological change. A secondary mechanism, which is
initiate the establishment of routes to a given destination on- independent of network topology dynamics, is used as a means of route
demand, since it may not be necessary (nor desirable) to maintain optimization and soft-state route verification. The design and
routes between every source/destination pair at all times. At the flexability of TORA allow its operation to be biased towards high
same time, selected destinations can initiate proactive operation, reactivity (i.e., low time complexity) and bandwidth conservation
resembling traditional table-driven routing approaches. TORA (i.e., low communication complexity) rather than routing
maintains loop-free routing, and typically provides multiple routes optimality--making it potentially well-suited for use in dynamic
for any source/destination pair that requires a route. In the event wireless networks.
of a network partition, the protocol detects the partition and erases
invalid routes.
2 Terminology 2 Terminology
MANET router or router: MANET router or router:
A device--identified by a "unique Router ID" (RID)--that executes A device--identified by a "unique Router ID" (RID)--that executes
a MANET routing protocol and, under the direction of which, a MANET routing protocol and, under the direction of which,
forwards IP packets. It may have multiple interfaces, each forwards IP packets. It may have multiple interfaces, each
identified by an IP address. Associated with each interface is a identified by an IP address. Associated with each interface is a
physical layer communication device. These devices may employ physical layer communication device. These devices may employ
wireless or hardwired communications, and a router may wireless or hardwired communications, and a router may
skipping to change at page 4, line 19 skipping to change at page 4, line 20
follows that the "network-layer topology" is the logical union of follows that the "network-layer topology" is the logical union of
the various "physical-layer topologies." the various "physical-layer topologies."
IP routing fabric: IP routing fabric:
The heterogeneous mixture of communications media and technologies The heterogeneous mixture of communications media and technologies
through which IP packets are forwarded whose topology is defined through which IP packets are forwarded whose topology is defined
by the network-layer topology. by the network-layer topology.
3 Protocol Functional Description 3 Protocol Functional Description
This section is intended to provide an overview of the protocol and
insight into its operation. The protocol specification provided in a
subsequent section is intended to serve as the basis for protocol
implementations. Thus, in the case of any discrepancies between the
description in this section and the subsequent specification section,
the specification section should be considered more athoritative.
TORA has been designed to work on top of lower layer mechanisms or TORA has been designed to work on top of lower layer mechanisms or
protocols that provide the following basic services between protocols that provide the following basic services between
neighboring routers: neighboring routers:
* Link status sensing and neighbor discovery * Link status sensing and neighbor discovery
* Reliable, in-order control packet delivery * Reliable, in-order control packet delivery
* Link and network layer address resolution and mapping * Link and network layer address resolution and mapping
* Security authentication * Security authentication
Events such as the reception of control messages and changes in Events such as the reception of control messages and changes in
connectivity with neighboring routers trigger TORA's algorithmic connectivity with neighboring routers trigger TORA's algorithmic
reactions. reactions.
A logically separate version of TORA is run for each "destination" to A logically separate version of TORA is run for each "destination" to
which routing is required. The following discussion focuses on a which routing is required. The following discussion focuses on a
single version of TORA running for a given destination. The term single version of TORA running for a given destination. The term
destination is used herein to refer to a traditional IP routing destination is used herein to refer to a traditional IP routing
destination, which is identified by an IP address and mask. Thus, the destination, which is identified by an IP address and mask (or
route to a destination may correspond to the individual address of an prefix). Thus, the route to a destination may correspond to the
interface on a specific machine (i.e., a host route) or an individual address of an interface on a specific machine (i.e., a
aggregation of addresses (i.e., a network route). TORA assigns host route) or an aggregation of addresses (i.e., a network route).
directions to the links between routers to form a routing structure
that is used to forward datagrams to the destination. A router TORA assigns directions to the links between routers to form a
assigns a direction ("upstream" or "downstream") to the link with a routing structure that is used to forward datagrams to the
neighboring router based on the relative values of a metric destination. A router assigns a direction ("upstream" or
associated with each router. The metric maintained by a router can "downstream") to the link with a neighboring router based on the
conceptually be thought of as the router's "height" (i.e., links are relative values of a metric associated with each router. The metric
directed from the higher router to the lower router). The maintained by a router can conceptually be thought of as the router's
significance of the heights and the link directional assignments is "height" (i.e., links are directed from the higher router to the
that a router may only forward datagrams downstream. Links from a lower router). The significance of the heights and the link
router to any neighboring routers with an unknown or "null" height directional assignments is that a router may only forward datagrams
are considered undirected and cannot be used for forwarding. downstream. Links from a router to any neighboring routers with an
Collectively, the heights of the routers and the link directional unknown or undefined height are considered undirected and cannot be
assignments form a multipath routing structure, in which all directed used for forwarding. Collectively, the heights of the routers and the
paths lead downstream to the destination. link directional assignments form a loop-free, multipath routing
structure in which all directed paths lead downstream to the
destination, see Figure 1. Note that in this example, C is closer to
the destination than B in terms of number of hops, but the height
metric of C is greater than that of B.
.-----. .-----. .-----.
| A |---->| B |<----| C | Relative height of the routers
`-----' `-----' `-----' ------------------------------
^ | |
| | | H(C) > H(B) > H(E) > H(DEST)
| | |
| v v H(D) > H(A) > H(B) > H(E) > H(DEST)
.-----. .-----. .-----.
| D |---->| E |---->| DEST|
`-----' `-----' `-----'
Figure 1: Conceptual representation of the directed acyclic
graph defined by the relative height of network routers.
TORA can be separated into four basic functions: creating routes, TORA can be separated into four basic functions: creating routes,
maintaining routes, erasing routes, and optimizing routes. Creating maintaining routes, erasing routes, and optimizing routes. Creating
routes corresponds to the selection of heights to form a directed routes corresponds to the selection of heights to form a directed
sequence of links leading to the destination in a previously sequence of links leading to the destination in a previously
undirected network or portion of the network. Maintaining routes undirected network or portion of the network. Maintaining routes
refers to the adapting the routing structure in response to network refers to the adapting the routing structure in response to network
topological changes. For example, following the loss of some router's topological changes. For example, following the loss of some router's
last downstream link, some directed paths may temporarily no longer last downstream link, some directed paths may temporarily no longer
lead to the destination--resulting a sequence of directed link lead to the destination. This event triggers a sequence of directed
reversals (caused by the re-selection of router heights) to re-orient link reversals (caused by the re-selection of router heights), which
the routing structure such that all directed paths again lead to the re-orients the routing structure such that all directed paths again
destination. In cases where the network becomes partitioned, links in lead to the destination. In cases where the network becomes
the portion of the network that has become partitioned from the partitioned, links in the portion of the network that has become
destination must be marked as undirected to erase invalid routes. partitioned from the destination must be marked as undirected to
During this erasing routes process, routers set their heights to null erase invalid routes. During this erasing routes process, routers set
and their adjacent links become undirected. Finally, TORA includes a their heights to null and their adjacent links become undirected.
secondary mechanism for route optimization, in which routers re- Finally, TORA includes a secondary mechanism for optimizing routes,
select their heights in order to improve the routing structure. TORA in which routers re-select their heights in order to improve the
accomplishes these four functions through the use of four distinct routing structure. TORA accomplishes these four functions through the
control packets: query (QRY), update (UPD), clear (CLR), and use of four distinct control packets: query (QRY), update (UPD),
optimization (OPT). clear (CLR), and optimization (OPT).
3.1 Protocol State
At any given time, an ordered quintuple, HEIGHT = (tau[i], oid[i],
r[i], delta[i], i), is associated with each node i, where i is the
unique ID of the node. Conceptually, the quintuple associated with
each node represents the height of the node as defined by two
parameters: a reference level and an offset with respect to the
reference level. The reference level is represented by the first
three values in the quintuple, while the offset is represented by the
last two values. A new reference level is defined each time a node
loses its last downstream link due to a link failure. The first value
representing the reference level, tau[i], is a time tag set to the
"time" of the link failure. For now, it is assumed that all nodes
have synchronized clocks. This could be accomplished via interface
with an external time source such as the Global Positioning System
(GPS) [5] or through use of an algorithm such as the Network Time
Protocol [6]. This time tag need not actually indicate or be "time,"
nor will relaxation of the synchronization requirement invalidate the
protocol. The second value, oid[i], is the originator-ID (i.e., the
unique ID of the node that defined the new reference level). This
ensures that the reference levels can be totally ordered
lexicographically, even if multiple nodes define reference levels due
to failures that occur simultaneously (i.e., with equal time tags).
The third value, r[i], is a single bit used to divide each of the
unique reference levels into two unique sub-levels. This bit is used
to distinguish between the original reference level and its
corresponding, higher, reflected reference level. When a distinction
is not required, both the original and reflected reference levels
will simply be referred to as "reference levels." The first value
representing the offset, delta[i], is an integer used to order nodes
with respect to a common reference level. This value is instrumental
in the propagation of a reference level. How delta is selected will
be clarified in a subsequent section. Finally, the second value
representing the offset, i, is the unique ID of the node itself. This
ensures that nodes with a common reference level and equal values of
delta (and in fact all nodes) can be totally ordered
lexicographically at all times.
Each node i (other than the destination) maintains its height,
HEIGHT. Initially the height of each node in the network (other than
the destination) is set to NULL, HEIGHT = (-, -, -, -, i), where i is
the unique ID of the node. Subsequently, the height of each node i
can be modified in accordance with the rules of the protocol. The
height of the destination j is always ZERO, HEIGHT = (0, 0, 0, 0, j),
where j is the unique ID of the destination for which the algorithm
is running). In addition to its own height, each node i maintains a
height table with an entry HT_NEIGH[k] for each neighbor k. Initially
the height of each neighbor is set to NULL, HT_NEIGH[k] = (-, -, -,
-, k). If the destination j is a neighbor of node i, node i sets the
corresponding height entry to ZERO, HT_NEIGH[j] = (0, 0, 0, 0, j).
Each node i (other than the destination) also maintains a link-status
table with an entry LNK_STAT[k] for each link (i, k), where node k is
a neighbor of node i. The status of the links is determined by the
height of the node, HEIGHT, and its height entry for the neighbor,
HT_NEIGH[k]. The link is directed from the higher node to the lower
node. If a neighbor k is higher than node i, the link is marked
upstream (UP). If a neighbor k is lower than node i, the link is
marked downstream (DN). If the neighbor's height entry, HT_NEIGH[k],
is NULL, the link is marked undirected (UN). Finally, if the height
of node i is NULL, then any neighbor's height that is not NULL is
considered lower, and the corresponding link is marked downstream
(DN). When a new link (i, k) is established (i.e., node i has a new
neighbor k), node i adds entries for the new neighbor to the height
and link-status tables. If the new neighbor is the destination j, the
corresponding height entry is set to ZERO, HT_NEIGH[j] = (0, 0, 0, 0,
j); otherwise it is set to NULL, HT_NEIGH[k] = (-, -, -, -, k). The
corresponding link-status entry, LNK_STAT[k], is set as outlined
above. Nodes need not communicate any routing information upon link
activation.
3.2 Creating Routes
Creating routes requires use of the QRY and UPD packets. A QRY packet
consists of the destination-ID, j, which identifies the destination
for which the algorithm is running. An UPD packet consists of the
destination-ID, j, and the height of the node i that is broadcasting
the packet, HEIGHT.
Each node i (other than the destination) maintains a route-required
flag, which is initially un-set. Each node i (other than the
destination) also maintains the time at which the last UPD packet was
broadcast and the time at which each link (i, k), where node k is
neighbor of node i, became active.
When a node with no directed links and an un-set route-required flag
requires a route to the destination, it broadcasts a QRY packet and
sets its route-required flag. When a node i receives a QRY it reacts
as follows:
a) If the receiving node i has no downstream links and its route-
required flag is un-set, it re-broadcasts the QRY packet and sets
its route-required flag.
b) If the receiving node i has no downstream links and the route-
required flag is set, it discards the QRY packet.
c) If the receiving node i has at least one downstream link and
its height is NULL, it sets its height to HEIGHT = (tau[k],
oid[k], r[k], delta[k] + 1, i), where HT_NEIGH[k] = (tau[k],
oid[k], r[k], delta[k], k) is the minimum height of its non-NULL
neighbors, and broadcasts an UPD packet.
d) If the receiving node i has at least one downstream link and
its height is non-NULL, it first compares the time the last UPD
packet was broadcast to the time the link over which the QRY
packet was received became active. If an UPD packet has been
broadcast since the link became active, it discards the QRY
packet; otherwise, it broadcasts an UPD packet.
If a node has the route-required flag set when a new link is 3.1 Creating Routes
established, it must broadcast a QRY packet.
When a node i receives an UPD packet from a neighbor k, node i first Creating routes can be initiated on-demand by a source or proactively
updates the entry HT_NEIGH[k] in its height table with the height by a destination. In either case, routers select heights with respect
contained in the received UPD packet. Node i then updates the entry to the given destination and assign directions to the links between
LNK_STAT[k] in its link-status table and reacts as follows: neighboring routers.
a) If the route-required flag is set (which implies that the In the on-demand mode, creating routes is accomplished via a query-
height of node i is NULL), node i sets its height to HEIGHT = reply mechanism using QRY and UPD packets. A source initiates the
(tau[k], oid[k], r[k], delta[k] + 1, i)--where HT_NEIGH[k] = process by sending a QRY packet to its neighbors that identifies the
(tau[k], oid[k], r[k], delta[k], k) is the minimum height of its destination for which a route is requested. The QRY packet is
non-NULL neighbors, updates all the entries in its link-status propagated out from the source (i.e., processed and forwarded by
table, un-sets the route-required flag and then broadcasts an UPD neighboring routers) until it is received by one or more routers that
packet that contains its new height. have a trusted route to the destination. As the QRY packet is
forwarded, routers set a route-requested flag and discard any
subsequent QRY packets received for the same destination. The route-
requested flag supresses redundant route requests and reduces the
need for subsequent route requests when a destination is temporarily
unreachable. Routers that have a trusted route to the destination
repsond to the QRY packet by sending an UPD packet to their neighbors
that identifies the relevant destination and the height of the router
sending the UPD packet. Routers also maintain the time at which an
UPD packet was last sent to its neighbors and the time at which links
to neighboring routers became active, to reduce redundant replies to
a given route request. When a router with the route-requested flag
set receives an UPD packet, it sets its height and sends an UPD
packet to its neighbors that identifies the relevant destination and
the new height of the router sending the UPD packet. Thus, routers in
the network select heights for the requested desination, learn of
their neighbors heights for the destination and assign link
directions based on those heights. To ensure that a route request
continues to propagate when the destination was initially
unreachable, routers with the route-requested flag set must resend a
QRY packet upon activation of a new link (i.e., discovery of a new
neighbor).
b) If the route-required flag is not set, node i need only react In the proactive mode, the destination initiates the creating routes
if it has lost its last downstream link. The section on process by sending an OPT packet that is processed and forwarded by
maintaining routes discusses the reaction that occurs if reception neighboring routers. The OPT packet identifies the destination, the
of the UPD packet resulted in loss of the last downstream link. mode of operation for the destination and the height of the router
sending the OPT packet. The OPT packet also contains a sequence
number used to uniquely identify the packet and ensure that each
router processes and forwards a given OPT packet from a destination
at most once. As the OPT packet is forwarded, routers set their mode
of operation correspondingly, reselect their heights, and send an OPT
packet to their neighbors that identifies the relevant destination
and the new height of the router sending the UPD packet.
3.3 Maintaining Routes 3.2 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 10, line 18 skipping to change at page 9, line 11
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.
3.4 Erasing Routes 3.3 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 10, line 46 skipping to change at page 9, line 39
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.5 Optimizing Routes 3.4 Optimizing Routes
TBD. TBD.
4 Protocol Specification 4 Protocol Specification
The subsequent specification is intended to be of sufficient detail The subsequent specification is intended to be of sufficient detail
to serve as a template for implementations. to serve as a template for implementations.
4.1 Configuration 4.1 Configuration
For each interface "i" of a router, the following configuration A router is configured with a router ID (RID), which must be unique
parameters are maintained. among the set of routers collectively running TORA within a routing
domain. This value may correspond to one of the router's IP
addresses.
For each interface "i" of a router, the following parameters must be
configured.
IP_ADDR[i] IP address of interface. IP_ADDR[i] IP address of interface.
ADDR_MASK[i] Address mask of interface. ADDR_MASK[i] Address mask of interface.
PRO_MODE[i] Indicates reactive/proactive mode of operation. PRO_MODE[i] Indicates reactive/proactive mode of operation.
OPT_MODE[i] Indicates optimization mode of operation. OPT_MODE[i] Indicates optimization mode of operation.
OPT_PERIOD[i] Period for optimization mechanism. OPT_PERIOD[i] Period for optimization mechanism.
For each interface, a network route corresponding to the address and For each interface, a network route corresponding to the address and
mask of the interface may be added to the routing table. mask of the interface may be added to the routing table.
Additionally, TORA may respond to requests (i.e., QRY packets) for Additionally, TORA may respond to requests (i.e., QRY packets) for
routes to destination addresses that match the set of addresses routes to destination addresses that match the set of addresses
identified by the interface configurations. PRO_MODE[i] (0=OFF, 1=ON) identified by the interface configurations. PRO_MODE[i] (0=OFF, 1=ON)
indicates if routes to the destination identified by the indicates if routes to the destination identified by the
corresponding interface address and mask should be created corresponding interface address and mask should be created
proactively. OPT_MODE[i] (00=OFF, 01=PARTIAL, 10=FULL, 11=reserved proactively. OPT_MODE[i] (00=OFF, 01=PARTIAL, 10=FULL, 11=reserved
for future use) indicates the type (if any) of optimizations that for future use) indicates the type (if any) of optimizations that
should be used for the destination identified by the corresponding should be used for the destination identified by the corresponding
interface address and mask, while the OPT_PERIOD[i] sets the interface address and mask, while the OPT_PERIOD[i] sets the
frequency at which the optimizations will occur. frequency at which the optimizations will occur.
A router is also configured with a router ID (RID), which must be
unique among the set of routers collectively running TORA.
4.2 State Variables 4.2 State Variables
For each destination "j" to which routing is required, a router A router maintains the state of the configuration parameters outlined
maintains the following state variables. above. In addition, for each interface a router maintains a sequence
number that is incremented upon changes to the interface mode of
operation.
MODE_SEQ[i] Sequence number associated with mode of interface "i".
For each destination "j", a router maintains the following state
variables.
HEIGHT[j] This router's height metric for routing to "j". HEIGHT[j] This router's height metric for routing to "j".
MODE_SEQ[j] Sequence number of most recent mode for "j".
PRO_MODE[j] Indicates reactive/proactive mode of operation for "j". PRO_MODE[j] Indicates reactive/proactive mode of operation for "j".
OPT_MODE[j] Indicates optimization 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". OPT_PERIOD[j] Indicates optimization period for "j".
RT_REQ[j] Indicates whether a route to "j" is required. RT_REQ[j] Indicates whether a route request to "j" is pending.
TIME_UPD[j] Time last UPD packet regarding "j" sent by this router. 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", a router maintains a separate instance of
maintains a separate instance of the following state variables for 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.
4.3 Auxiliary Variables 4.3 Auxiliary Variables
For each destination "j" to which routing is required, a router may For each destination "j" to which routing is required, a router may
maintain the following auxiliary variables. Although each of the maintain the following auxiliary variables. Although each of the
variables can be computed based on the entries in the LNK_STAT table, variables can be computed based on the entries in the LNK_STAT table,
maintaining the values continuously may facilitate implementation of maintaining the values continuously may facilitate implementation of
the protocol. the protocol. Whether these variables are maintained continuously or
computed when needed is implementation specific.
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.
4.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 respect entry, while the last two components represent an offset with respect
to the reference level. The five components of the Height data to the reference level. The five components of the Height 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 to which the height metric refers. HEIGHT.id Unique id of the router to which the height metric refers.
To simplify notation in this specification, a height may be written 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 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 following two predefined values for a height are used throughout the
specification of the protocol. specification of the 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
skipping to change at page 13, line 9 skipping to change at page 12, line 12
Each entry in the LNK_STAT table is maintained in accordance with the Each entry in the LNK_STAT table is maintained in accordance with 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;
4.6 TORA Packet Formats 4.6 TORA Packet Formats
TBD. 4.6.1 Query (QRY) Packet Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Version #
The TORA version number. This specification documents version 1.
Type
The TORA packet type. For QRY packet this field is set to 1.
Reserved
Field reserved for future use.
Destination IP Address
The IP address for which a route is being requested.
4.6.2 Update (UPD) Packet Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address Mask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mode Sequence # |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mode | Optimization Period |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.tau |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.oid |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.r | H.delta |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Version #
The TORA version number. This specification documents version 1.
Type
The TORA packet type. For UPD packet this field is set to 2.
Reserved
Field reserved for future use.
Destination IP Address
The IP address for which a route is being requested.
Destination IP Address Mask
The network mask associated with the destination IP address.
Mode Sequence #
Sequence number associated with the subsequent mode and
optimization period fields. Used for propagation of most recent
mode state and to ensure each router processes mode information at
most once.
Mode
The mode of operation associated with the destination IP address
and mask. This field is used to indicate reactive/proactive
routing and also the type (if any) of optimizations used for the
destination.
Optimization Period
The period for optimization packets originated by the destination.
H.tau
The H.tau value, associated with the destination IP address and
mask, of the router sending the UPD.
H.oid
The H.oid value, associated with the destination IP address and
mask, of the router sending the UPD.
H.r
The H.r value, associated with the destination IP address and
mask, of the router sending the UPD.
H.delta
The H.delta value, associated with the destination IP address and
mask, of the router sending the UPD.
H.id
The H.id value, associated with the destination IP address and
mask, of the router sending the UPD (i.e., unique router ID).
4.6.3 Clear (CLR) Packet Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address Mask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.tau |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.oid |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Version #
The TORA version number. This specification documents version 1.
Type
The TORA packet type. For CLR packet this field is set to 3.
Reserved
Field reserved for future use.
Destination IP Address
The IP address for which a route is being requested.
Destination IP Address Mask
The network mask associated with the destination IP address.
H.tau
The H.tau value, associated with the destination IP address and
mask, of the router sending the UPD.
H.oid
The H.oid value, associated with the destination IP address and
mask, of the router sending the UPD.
H.id
The H.id value, associated with the destination IP address and
mask, of the router sending the UPD (i.e., unique router ID).
4.6.4 Optimization (OPT) Packet Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address Mask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mode Sequence # |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mode | Optimization Period |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.tau |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.oid |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.r | H.delta |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| H.id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Version #
The TORA version number. This specification documents version 1.
Type
The TORA packet type. For OPT packet this field is set to 4.
Reserved
Field reserved for future use.
Destination IP Address
The IP address for which a route is being requested.
Destination IP Address Mask
The network mask associated with the destination IP address.
Mode Sequence #
Sequence number associated with the subsequent mode and
optimization period fields. Used for propagation of most recent
mode state and to ensure each router processes mode information at
most once.
Mode
The mode of operation associated with the destination IP address
and mask. This field is used to indicate reactive/proactive
routing and also the type (if any) of optimizations used for the
destination.
Optimization Period
The period for optimization packets originated by the destination.
H.tau
The H.tau value, associated with the destination IP address and
mask, of the router sending the UPD.
H.oid
The H.oid value, associated with the destination IP address and
mask, of the router sending the UPD.
H.r
The H.r value, associated with the destination IP address and
mask, of the router sending the UPD.
H.delta
The H.delta value, associated with the destination IP address and
mask, of the router sending the UPD.
H.id
The H.id value, associated with the destination IP address and
mask, of the router sending the UPD (i.e., unique router ID).
4.7 Event Processing 4.7 Event Processing
4.7.1 Initialization 4.7.1 Initialization
TBD TBD
4.7.2 Connection Status Change 4.7.2 Connection Status Change
The TORA process receives notification of link status changes. It is The TORA process receives notification of link status changes from
anticipated that the TORA process will have access to all the lower layer mechanisms or protocols. It is anticipated that the TORA
information about the connections. Thus, upon notification, TORA will process will have access to all the information about the
have sufficient information to determine if any new links have been connections. Thus, upon notification, TORA will have sufficient
established or any existing links have been severed. If either is the information to determine if any new links have been established or
case, then TORA must proceed as outlined in appropriate subsequent any existing links have been severed. If either is the case, then
section (4.7.3 or 4.7.4). In addition, it is also possible for a TORA must proceed as outlined in appropriate subsequent section
connection that was used in the routing table to be severed without (4.7.3 or 4.7.4). In addition, since a link is potientially composed
resulting in the corresponding link being severed. In this case TORA of multiple connections, it is also possible for a connection that
must modify the appropriate routing table entries. was used in the routing table to be severed without resulting in the
corresponding link being severed. In this case TORA must modify the
appropriate routing table entries.
4.7.3 Link with a New Neighbor "k" Established 4.7.3 Link with a New Neighbor "k" Established
For each destination "j": For each destination "j":
Set TIME_ACT[j][k] to the current time and increment num_active[j]. Set TIME_ACT[j][k] to the current time and increment NUM_ACTIVE[j].
If the neighbor "k" is the destination "j", then set 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], 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. else set HT_NEIGH[j][k]=NULL and LNK_STAT[j][k]=UN.
If the RT_REQ[j] flag is set && neighbor "k" is the destination "j" If the RT_REQ[j] flag is set && neighbor "k" is the destination "j"
then I) else II). then I) else II).
I) Set HEIGHT[j]=HT_NEIGH[j][k]. Increment HEIGHT[j].delta. Set 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] 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 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 current 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.
skipping to change at page 14, line 16 skipping to change at page 17, line 40
queue to be sent to all neighbors. Event Processing Complete. 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 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 it in the queue to be sent to all neighbors. Event Processing
Complete. Complete.
4.7.4 Link with Prior Neighbor "k" Severed 4.7.4 Link with Prior Neighbor "k" Severed
For each destination "j": For each destination "j":
Decrement num_active[j]. If LNK_STAT[j][k]==DN, decrement Decrement NUM_ACTIVE[j]. If LNK_STAT[j][k]==DN, decrement
num_down[j]. If LNK_STAT[j][k]==UP, decrement num_up[j]. NUM_DOWN[j]. If LNK_STAT[j][k]==UP, decrement NUM_UP[j].
If num_down[j]==0 then I) else II). If NUM_DOWN[j]==0 then I) else II).
I) If num_active[j]==0 then A) else B). I) If NUM_ACTIVE[j]==0 then A) else B).
A) Set HEIGHT[j]=NULL. Unset the RT_REQ[j] flag. Event A) Set HEIGHT[j]=NULL. Unset the RT_REQ[j] flag. Event
Processing Complete. Processing Complete.
B) If num_up==0 then 1) else 2). B) 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[j] to the current b) Set HEIGHT[j]=NULL. 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.
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
skipping to change at page 15, line 25 skipping to change at page 18, line 49
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[j] 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 be time. Create an UPD packet and place it in the queue to be
sent to all neighbors. Event Processing Complete. sent to all neighbors. Event Processing Complete.
2) Set the RT_REQ[j] flag. If num_active[j]>1 then a) else 2) Set the RT_REQ[j] flag. If NUM_ACTIVE[j]>1 then a) else
b). 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.
4.7.6 UPD Packet Regarding Destination "j" Received from Neighbor "k" 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], If MODE_SEQ field of received packet is greater than MODE_SEQ[j],
skipping to change at page 15, line 47 skipping to change at page 19, line 22
Update the entries HT_NEIGH[j][k], and LNK_STAT[j][k]. If the 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). 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[j] flag. Set TIME_UPD[j] to the 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 current 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.
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[j] to the current b) Set HEIGHT[j]=NULL. 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.
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]
skipping to change at page 16, line 31 skipping to change at page 20, line 7
TIME_UPD[j] to the current time. Create an UPD packet TIME_UPD[j] to the current time. Create an UPD packet
and 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][n].oid==id, where n is such that ii) If HT_NEIGH[j][n].oid==id, where n is such that
HT_NEIGH[j][n] is non-NULL and id is the unique id of HT_NEIGH[j][n] is non-NULL and id is the unique id of
this node, then x) else y). 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[j]=0. Set HEIGHT[j]=NULL. Set NUM_DOWN[j]=0. Set
num_up[j]=0. For every active link n, if the NUM_UP[j]=0. For every active link n, if the
neighbor connected via link n is the destination j, 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]=ZERO and LNK_STAT[j][n]=DN else
set HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. set HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN.
Create a CLR packet, with the previously saved Create a CLR packet, with the previously saved
values of tau and oid, and place it in the queue to values of tau and oid, and place it in the queue to
be sent to all neighbors. Event Processing be sent to all neighbors. Event Processing
Complete. 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
skipping to change at page 17, line 30 skipping to change at page 21, line 6
Processing Complete. Processing Complete.
2) Event Processing Complete. 2) Event Processing Complete.
4.7.7 CLR Packet Regarding Destination "j" Received from Neighbor "k" 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[j]=0. Set temporary variables. Set Height[j]=NULL. Set NUM_DOWN[j]=0. Set
num_up[j]=0. For every active link n, if the neighbor connected 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 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[j]>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[j]==0 then HT_NEIGH[j][n]=NULL and LNK_STAT[j][n]=UN. If NUM_DOWN[j]==0 then
A) 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[j] to the current b) Set HEIGHT[j]=NULL. 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.
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
skipping to change at page 19, line 4 skipping to change at page 22, line 26
4.7.9 Mode Configuration Change or Optimization Timer Event for local 4.7.9 Mode Configuration Change or Optimization Timer Event for local
interface "i" interface "i"
Increment MODE_SEQ[i]. Create an OPT packet and place it in the queue 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 || to be sent to all neighbors. If OPT_MODE[i]==PARTIAL ||
OPT_MODE[i]==FULL, schedule a local optimization timer event for OPT_MODE[i]==FULL, schedule a local optimization timer event for
interface "i" to occur at a time randomly selected between 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 0.5*OPT_PERIOD[i] and 1.5*OPT_PERIOD[i] seconds based on a uniform
distribution. Event Processing Complete. distribution. Event Processing Complete.
5 Security Considerations 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
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 [4] M.S. Corson and V. Park, An Internet MANET Encapsulation Protocol
(IMEP), draft-ietf- (IMEP), draft-ietf-
[5] NAVSTAR GPS user equipment introduction, MZ10298.001 (February
1991).
[6] D. Mills, Network time protocol, specification, implementation
and analysis, Internet RFC-1119 (September 1989).
Author's Addresses 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/