IETF MANET Working Group J.J. Garcia-Luna-Aceves
INTERNET-DRAFT University of California, Santa Cruz
Marcelo Spohn, David Beyer
NOKIA
22 October 1999
SOURCE TREE ADAPTIVE ROUTING (STAR) PROTOCOL
<draft-ietf-manet-star-00.txt>
Status of This Memo
This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at:
http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft
Shadow Directories can be accessed at:
http://www.ietf.org/shadow.html.
Abstract
The Source-Tree Adaptive Routing (STAR) protocol is intended for use
by nodes (static and mobile) in an ad hoc network or an internet. A
Garcia-Luna-Aceves, Spohn, Beyer [Page 1]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
router in STAR communicates to its neighbors the parameters of its
source routing tree, which consists of each link that the router
needs to reach every known destination (and address range) in the ad
hoc network or internet. To conserve transmission bandwidth and
energy, a router communicates changes to its source routing tree only
when the router detects new destinations, the possibility of looping,
or the possibility of node failures or network partitions.
Introduction
This document describes the Source-Tree Adaptive Routing (STAR) pro-
tocol [11, 12], a proptocol developed in the SPARROW project part of
the DARPA GloMo program.
Routing algorithms for ad hoc networks can be categorized according
to the way in which routers obtain routing information, and according
to the type of information they use to compute preferred paths. In
terms of the way in which routers obtain information, routing proto-
cols have been classified as table-driven and on-demand. In terms of
the type of information used by routing protocols, routing protocols
can be classified into link-state protocols and distance-vector pro-
tocols. Routers running a link-state protocol use topology informa-
tion to make routing decisions. Routers running a distance-vector
protocol use distances or path information to destinations to make
routing decisions. Our characterization of distance-vector routing
protocols is broader than in other documents but is consistent with
our prior publications.
In an on-demand routing protocol, routers maintain routing informa-
tion for only those destinations that they need to contact as a
source or relay of information. The basic approach consists of allow-
ing a router that does not know how to reach a destination to send a
flood-search message to obtain the path information it needs. The
first routing protocol of this type was proposed to establish virtual
circuits in the MSE network [19], and there are several more recent
examples of this approach (e.g., AODV [23], ABR [30], DSR [15], TORA
[21], SSA [6], ZRP [13]). On-demand routing protocols differ on the
specific mechanisms used to disseminate flood-search packets and
their responses, cache the information heard from other nodes'
searches, determine the cost of a link, and determine the existence
of a neighbor.
In a table-driven algorithm, each router maintains path information
for each known destination in the network and updates its routing-
table entries as needed. Examples of table-driven algorithms based
Garcia-Luna-Aceves, Spohn, Beyer [Page 2]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
on distance vectors are the routing protocol of the DARPA packet-
radio network [16i], DSDV [22], WRP [27], WIRP [9], and least-
resistance routing protocols [24]. Prior table-driven approaches to
link-state routing in packet-radio networks are based on topology
broadcast. However, disseminating complete link-state information to
all routers incurs excessive communication overhead in an ad hoc net-
work, because of the dynamics of the network and the small bandwidth
available. Accordingly, all link-state routing approaches for
packet-radio networks have been based on hierarchical routing schemes
[25, 26, ,29].
A key issue in deciding which type of routing protocol is best for ad
hoc networks is the communication overhead incurred by the protocol.
Because data and control traffic share the same communication
bandwidth in the network, and because untethered routers use the same
energy source to transmit data and control packets, computing
minimum-cost (e.g., least interference) paths to all destinations at
the expense of considerable routing-update traffic is not practical
in ad hoc networks with untethered nodes and dynamic topologies. The
routing protocol used in an ad hoc network should incur as little
communication overhead as possible to preserve battery life at
untethered routers and to leave as much bandwidth as possible to data
traffic.
To date, the debate on whether a table-driven or an on-demand routing
approach is best for wireless networks has assumed that table-driven
routing necessarily has to provide optimum (e.g., shortest-path)
routing, when in fact on-demand routing protocols cannot ensure
optimum paths. STAR is the first example of a table-driven routing
protocol that is as efficient as an on-demand routing protocol by
exploiting link-state information and allowing paths taken to desti-
nations to deviate from the optimum in order to save bandwidth.
Assumptions and Terminology
We make very few assumptions for the efficient operation of STAR.
STAR assumes that the ad hoc network is in fact a wireless internet
in which IP hosts are connected through subnets or point-to-point
links to routers. Currently, STAR operates on top of IP, just like an
Internet routing protocol does.
STAR can operate in ad hoc networks based on vary different medium
access control (MAC) protocols, which need not permit promiscuous
listening of transmissions.
Garcia-Luna-Aceves, Spohn, Beyer [Page 3]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
To describe STAR, the topology of a network is modeled as a directed
graph G = (V, E), where V is the set of nodes and E is the set of
edges connecting the nodes. Each node has a unique identifier and
represents a router with input and output queues updated according to
a FIFO policy. In a wireless network, a node can have connectivity
with multiple nodes over a single physical radio link. For the pur-
pose of routing-table updating, a node A can consider another node B
to be adjacent (we call such a node a ``neighbor'') if there is
link-level connectivity between A and B and A receives update mes-
sages from B reliably. Accordingly, we map a physical broadcast link
connecting multiple nodes into multiple point-to-point bidirectional
links defined for these nodes. A functional bidirectional link
between two nodes is represented by a pair of edges, one in each
direction and with a cost associated that can vary in time but is
always positive.
For brevity, an underlying protocol (which we call the neighbor pro-
tocol) is assumed to assure that a router detects within a finite
time the existence of a new neighbor and the loss of connectivity
with a neighbor. In practice, simple techniques can be used by a
router to decide whether or not it maintains connectivity with a
neighbor router by keeping track of packets received from neighboring
nodes. In ad hoc networks with simple waveforms in which a node can
eavesdrop on its neighbors, a router can keep track of transmissions
from other neighbors to estimate who its neighbors are. Future
specifications of STAR will describe examples of such techniques.
All messages, changes in the cost of a link, link failures, and new-
neighbor notifications are processed one at a time within a finite
time and in the order in which they are detected. Routers are
assumed to operate correctly, and information is assumed to be stored
without errors.
A pseudocode description of STAR is presented in [12]. A subsequent
version of this draft will specify STAR in more detail.
Updating Routes in Wireless Networks
We can distinguish between two main approaches to updating routing
information in the routing protocols that have been designed for
wireless networks: the optimum routing approach (ORA) and the least-
overhead routing approach (LORA). With ORA, the routing protocol
attempts to update routing tables as quickly as possible to provide
paths that are optimum with respect to a defined metric. In con-
trast, with LORA, the routing protocol attempts to provide viable
Garcia-Luna-Aceves, Spohn, Beyer [Page 4]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
paths according to a given performance metric, which need not be
optimum, to incur the least amount of control traffic.
For the case of ORA, the routing protocol can provide paths that are
optimum with respect to different types of service (TOS), such as
minimum delay, maximum bandwidth, least amount of interference, max-
imum available battery life, or combinations of metrics. Multiple TOS
can be supported in a routing protocol.
On-demand routing protocols follow LORA, in that these protocols
attempt to minimize control overhead by: (a) maintaining path infor-
mation for only those destinations with which the router needs to
communicate, and (b) using the paths found after a flood search as
long as the paths are valid, even if the paths are not optimum. On-
demand routing protocols can be applied to support multiple TOS; an
obvious approach is to obtain paths of different TOS using separate
flood searches. However, we assume that a single TOS is used in the
network. ORA is not an attractive or even feasible approach in on-
demand routing protocols, because flooding the network frequently
while trying to optimize existing paths with respect to a cost metric
of choice consumes the available bandwidth and can make the paths
worse while trying to optimize them.
We can view the flood search messages used in on-demand routing pro-
tocols as a form of polling of destinations by the sources. In con-
trast, in a table-driven routing protocol, it is the destinations who
poll the sources, meaning that the sources obtain their paths to des-
tinations as a result of update messages that first originate at the
destinations. What is apparent is that some form of information
flooding occurs in both approaches.
Interestingly, all the table-driven routing protocols reported to
date for ad hoc networks adhere to ORA, and admittedly have been
adaptations of routing protocols developed for wired networks. A
consequence of adopting ORA in table-driven routing within a wireless
network is that, if the topology of the network changes very fre-
quently, the rate of update messages increases dramatically, consum-
ing the bandwidth needed for user data. The two methods used to
reduce the update rate in table-driven routing protocols are cluster-
ing and sending updates periodically. Clustering is attractive to
reduce overhead due to network size; however, if the affiliations of
nodes with clusters change too often, then clustering itself intro-
duces unwanted overhead. Sending periodic updates after long timeouts
reduces overhead, and it is a technique that has been used since the
DARPA packet-radio network was designed [16]; however, control
traffic still has to flow periodically to update routing tables.
A nice feature of such routing protocols as DSR [15] and WIRP [9] is
Garcia-Luna-Aceves, Spohn, Beyer [Page 5]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
that these protocols remain quiet when no new update information has
to be exchanged; they have no need for periodic updates. Both proto-
cols take advantage of promiscuous listening of any packets sent by
router's neighbors to determine the neighborhood of the router.
Given that both on-demand and table-driven routing protocols incur
flooding of information in one way or another, a table-driven routing
protocol could be designed that incurs similar or less overhead than
on-demand routing protocols by limiting the polling done by the des-
tinations to be the same or less than the polling done by the sources
in on-demand routing protocols. However, there has been no prior
description of a table-driven routing protocol that can truly adhere
to LORA, i.e., one that has no need for periodic updates, uses no
clustering, and remains quiet as long as the paths available at the
routers are valid, even if they are not optimum. The reason why no
prior table-driven routing protocols have been reported based on LORA
is that, with the exception of WIRP and WRP, prior protocols have
used either distances to destinations, topology maps, or subsets of
the topology, to obtain paths to destinations, and none of these
types of information permits a router to discern whether the paths it
uses are in conflict with the paths used by its neighbors. Accord-
ingly, routers must send updates after they change their routing
tables in order to avoid long-term routing loops, and the best that
can be done is to reduce the control traffic by sending such updates
periodically. STAR is the first table-driven routing protocol that
implements LORA.
STAR Overview
In STAR, each router reports to its neighbors the characteristics of
every link it uses to reach a destination. The set of links used by a
router in its preferred path to destinations is called the source
tree of the router. A router knows its adjacent links and the source
trees reported by its neighbors; the aggregation of a router's adja-
cent links and the source trees reported by its neighbors constitute
a partial topology graph. The links in the source tree and topology
graph must be adjacent links or links reported by at least one neigh-
bor. The router uses the topology graph to generate its own source
tree. Each router derives a routing table specifying the successor to
each destination by running a local route-selection algorithm on its
source tree.
Depending on the bandwidth available in an ad hoc network, the ORA or
LORA approach can be used to updating routing information. STAR
Garcia-Luna-Aceves, Spohn, Beyer [Page 6]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
supports both.
Under ORA, updates are sent when source trees change. Under LORA, a
router running STAR sends updates on its source tree to its neighbors
only when it loses all paths to one ore more destinations, when it
detects a new destination, or when it determines that local changes
to its source tree can potentially create long term routing loops.
Because each router communicates its source tree to its neighbors,
the deletion of a link no longer used to reach a destination is
implicit with the addition of the new link used to reach the destina-
tion and need not be sent explicitly as an update; a router makes
explicit reference to a failed link only when the deletion of a link
causes the router to have no paths to one or more destinations, in
which case the router cannot provide new links to make the deletion
of the failed link implicit.
The basic update unit used in STAR to communicate changes to source
trees is the link-state update (LSU). An LSU reports the charac-
teristics of a link; an update message contains one or more LSUs. For
a link between router u and router or destination v, router u is
called the headnode of the link in the direction from u to v. The
head node of a link is the only router that can report changes in the
parameters of that link. LSUs are validated using sequence numbers,
and each router erases a link from its topology graph if the link is
not present in the source trees of any of its neighbors. The head of
a link does not periodically send LSUs for the link, because link-
state information never ages out.
Unlike any of the hierarchical link-state routing schemes proposed to
date for packet-radio networks [29], STAR does not require backbones,
the dissemination of complete cluster topology within a cluster, or
the dissemination of the complete inter-cluster connectivity among
clusters. Furthermore, STAR can be used with distributed hierarchical
routing schemes proposed in the past for both distance-vector or
link-state routing [18, 29, 28, 2].
Prior proposals for link-state routing using partial link-state data
without clusters [8, 10] require routers to explicitly inform their
neighbors which links they use and which links they stop using. In
contrast, because STAR sends only changes to the structure of source
trees, and because each destination has a single predecessor in a
source tree, a router needs to send only updates for those links that
are part of the tree and a single update entry for the root of any
subtree of the source tree that becomes unreachable due to failures.
Routers receiving a STAR update can infer correctly all the links
that the sender has stopped using, without the need for explicit
delete updates.
Garcia-Luna-Aceves, Spohn, Beyer [Page 7]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
Conceptual Data Structures
To execute STAR, a router maintains a topology graph, a source tree,
a routing table, the set of neighbors, the source trees reported by
each neighbor, and the topology graphs reported by each neighbor.
The record entry for a link from u to v in the topology graph of
router i is denoted $TG sub {i(u, v)}$ and is defined by the tuple
$(u, v, l, sn, del)$, and an attribute $p$ in the tuple is denoted by
$TG sub i (u, v).p$. The same notation applies to a link $(u, v)$ in
$ST sub i$, $ST sup i sub x$, and $TG sup i sub x$. $TG sub i (u,
v).del$ is set to TRUE if the link is not in the source tree of any
neighbor.
A vertex $v$ in $TG sub i$ is denoted $TG sub i (v)$. It contains a
tuple $(d, pred, suc, d', suc', nbr)$ whose values are used on the
computation of the source tree. $TG sub i (v).d$ reports the dis-
tance of the path $i d$ is $v$'s predecessor in $i next hop along
the path towards $v$, $suc'$ holds the address of the previous hop
towards $v$, $d'$ corresponds to the previous distance to $v$
reported by $suc'$, and $nbr$ is a flag used to determine if an
update message must be generated when the distance reported by the
new successor towards $v$ increases. The same notation applies to a
vertex $v$ in $ST sub i$, $ST sup i sub x$, and $TG sup i sub x$.
The source tree $ST sub i$ is a subset of $TG sub i$. The routing
table contains record entries for destinations in $ST sub i$, each
entry consists of the destination address, the cost of the path to
the destination, and the address of the next-hop towards the destina-
tion.
The topology graph $TG sup i sub x$ contains the links in $ST sup i
sub x$ and the links reported by neighbor $x$ in a message being pro-
cessed by router $i$, after processing the message $TG sup i sub x =
ST sup i sub x$.
A router $i$ running LORA also maintains the last reported source
tree ${ST sub i}'$.
The cost of a failed link is considered to be infinity. The way in
which costs are assigned to links is beyond the scope of this specif-
ication. As an example, the cost of a link could simply be the number
of hops, or the addition of the latency over the link plus some con-
stant bias.
We refer to an LSU that has a cost infinity as a RESET, $TG sup i sub
i = TG sub i$, and $ST sup i sub i = ST sub i$.
Garcia-Luna-Aceves, Spohn, Beyer [Page 8]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
Validating Updates in STAR
Because of delays in the routers and links of an internetwork, update
messages sent by a router may propagate at different speeds along
different paths. Therefore, a given router may receive an LSU from a
neighbor with stale link-state information, and a distributed
termination-detection mechanism is necessary for a router to ascer-
tain when a given LSU is valid and avoid the possibility of LSUs cir-
culating forever. STAR uses sequence numbers to validate LSUs. A
sequence number associated with a link consists of a counter that can
be incremented only by the head node of the link. For convenience, a
router $i$ needs to keep only a counter $SN sub i$ for all the links
for which it is the head node, which simply means that the sequence
number a router gives to a link for which it is the head node can be
incremented by more than one each time the link parameters change
value.
A router receiving an LSU accepts the LSU as valid if the received
LSU has a larger sequence number than the sequence number of the LSU
stored from the same source, or if there is no entry for the link in
the topology graph and the LSU is not reporting an infinite cost.
Link-state information for failed links are the only LSUs erased from
the topology graph due to aging (which is in the order of an hour
after having processed the LSU). LSUs for operational links are
erased from the topology graph when the links are erased from the
source tree of all the neighbors.
We note that, because LSUs for operational links never age out, there
is no need for the head node of a link to send periodic LSUs to
update the sequence number of the link. This is very important,
because it means that STAR does not need periodic update messages to
validate link-state information like OSPF [20] and every single rout-
ing protocol based on sequence numbers or time stamps does!
To simplify our description, the specification in the rest of this
document describes STAR as if unbounded counters were available to
keep track of sequence numbers. Future specifications of STAR will be
more precise.
Exchanging Update Messages
How update messages are exchanged depends on the routing approach
used (ORA or LORA) and the services provided by the link layer. The
rest of this section describes how LORA and ORA can be supported in
STAR and describes the impact of the link layer on the way in which
Garcia-Luna-Aceves, Spohn, Beyer [Page 9]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
update messages are exchanged.
Supporting LORA and ORA in STAR
In an on-demand routing protocol, a router can keep using a path
found as long as the path leads to the destination, even if the path
does not have optimum cost. A similar approach can be used in STAR,
because each router has a complete path to every destination as part
of its source tree. To support LORA, router $i$ running STAR should
send update messages according to the following three rules, which
inform routers of unreachable destinations, new destinations, and
update topology information to prevent permanent routing loops.
Router $i$ implements these rules by comparing its source tree
against the source trees it has received from its neighbors.
[LORA-1:
Router $i$ finds a new destination, or any of its neighbors
reports a new destination.
Whenever a router hears from a new neighbor that is also a new desti-
nation, it sends an update message that includes the new LSUs in its
source tree. Obviously, when a router is first initialized or after
a reboot, the router itself is a new destination and should send an
update message to its neighbors. Link-level support should be used
for the router to know its neighbors within a short time, and then
report its links to those neighbors with LSUs sent in an update mes-
sage. Else, a simple way to implement an initialization action con-
sists of requiring the router to listen for some time for neighbor
traffic, so that it can detect the existence of links to neighbors.
[LORA-2:
At least one destination becomes unreachable to router $i$ or any
of its neighbors.
When a router processes an input event (e.g., a link fails, an update
message is received) that causes all its paths through all its
neighbors to one or more destination to be severed, the router sends
an update message that includes an LSU specifying an infinite cost
for the link connecting to the head of each subtree of the source
tree that becomes unreachable. The update message does not have to
include an LSU for each node in an unreachable subtree, because a
neighbor receiving the update message has the sending node's source
Garcia-Luna-Aceves, Spohn, Beyer [Page 10]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
tree and can therefore infer that all nodes below the root of the
subtree are also unreachable, unless LSUs are sent for new links used
to reach some of the nodes in the subtree.
[LORA-3:
This rule has three parts:
(1) A path implied in the source tree of router $i$ leads to a loop.
(2) The new successor chosen to a given destination has an address
larger than the address of router $i$.
(3) The reported distance from the new chosen successor $n$ to a desti-
nation $j$ is longer than the reported distance from the previous
successor to the same destination. However, if the link $(i, j)$
fails and $n$ is a neighbor of $j$, no update message is needed
regarding $j$ or any destination whose path from $i$ involves $j$.
Each time a router processes an update message from a neighbor, it
updates that neighbor's source tree and traverses that tree to deter-
mine for which destinations its neighbor uses the router as a relay
in its preferred paths. The router then determines if it is using the
same neighbor as a relay for any of the same destinations. A routing
loop is detected if the router and neighbor use each other as relay
to any destination, in which case the loop must be broken and the
router must send an update message with the corresponding changes.
To explain the need for the second part of LORA-3, we observe that,
in any routing loop among routers with unique addresses, one of the
routers must have the smallest address in the loop; therefore, if a
router is forced to send an update message when it chooses a succes-
sor whose address is larger than its own, then it is not possible for
all routers in a routing loop to remain quiet after choosing one
another, because at least one of them is forced to send an update
message, which causes the loop to break when routers update their
source trees.
The last part of LORA-3 is needed when link costs can assume dif-
ferent values in different directions, in which case the second part
of LORA-3 may not suffice to break loops because the node with the
smallest address in the loop may not have to change successors when
the loop is formed.
Examples of why these rules are used are presented in [11, 12]. The
next version of this document will include detailed examples as well.
Garcia-Luna-Aceves, Spohn, Beyer [Page 11]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
To ensure that the above rules work with incremental updates specify-
ing only changes to a source tree, a router must remember the source
tree that was last notified to its neighbors. If any of LORA-1 to
LORA-3 are satisfied, the router must do one of two things:
(1) If the new source tree includes new neighbors than those present in
the source tree that was last updated, then the router must send
its entire source tree in its update, so that new neighbors learn
about all the destinations the router knows.
(2) If the two source trees imply the same neighbors, the router sends
only the updates needed to obtain the new tree from the old one.
To ensure that STAR stops sending update messages, a simple rule can
be used to determine which router must stop using its neighbor as a
relay, such a rule can be, for example, ``the router with the smaller
address must change its path.''
The above rules are sufficient to ensure that every router obtains
loopless paths to all known destinations, without the routers having
to send updates periodically. In addition to the ability for a router
to detect loops in STAR, the two key features that enable STAR to
adopt LORA are: (a) validating LSUs without the need of periodic
updates, and (b) the ability to either listen to neighbors' packets
or use a neighbor protocol at the link layer to determine who the
neighbors of a router are.
If ORA is to be supported in STAR, the only rule needed for sending
update messages consists of a router sending an update message every
time its source tree changes.
The rules for update-message exchange stated above assume that an
update message is sent reliably to all the neighbors of a router.
This is a very realistic assumption, because STAR working under LORA
generates far fewer update messages than the topology changes that
occur in the network. However, if preserving bandwidth is of utmost
importance and the underlying link protocol is contention-based,
additional provisions must be taken, which we describe next.
Impact of The Link Layer
If the link layer provides efficient reliable broadcast of network-
level packets, then STAR can rely on sending an update message only
Garcia-Luna-Aceves, Spohn, Beyer [Page 12]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
once to all neighbors, with the update message specifying only incre-
mental changes to the router's source tree. The link layer will
retransmit the packet as needed to reach all neighbors, so that it
can guarantee that a neighbor receives the packet unless the link is
broke.
A reliable broadcast service at the link layer can be implemented
very efficiently if the MAC protocol being used guarantees
collision-free transmissions of broadcast packets. A typical example
of MAC protocols that can support collision-free broadcasts is TDMA,
and there are several recent proposals that need not rely on static
assignments of resources (e.g., FPRP [31]).
Unfortunately, reliable broadcasting from a node to all its neighbors
is not supported in the collision-avoidance MAC protocols that have
been proposed and implemented for ad hoc networks [1, 7, 14, 17].
Furthermore, any link-level or network-level strategy for reliable
exchange of broadcast update messages over a contention-based MAC
protocol will require substantial retransmissions under high-load
conditions and rapid changes to the connectivity of nodes.
Therefore, if the underlying MAC protocol does not provide
collision-free broadcasts over which efficient reliable broadcasting
can be built, then STAR, and any table-driven routing protocol for
that matter, is better off relying on the approach adopted in the
past in the DARPA packet-radio network. For STAR this means that a
router broadcasts unreliably its update messages to its neighbors,
and each update message contains the entire source tree. For STAR to
operate correctly with this approach under LORA, routers must prevent
the case in which permanent loops are created because an update mes-
sage is not received by a neighbor. A simple example is a two-node
loop between two neighbor routers, $A$ and $B$, in which the neighbor
with the smaller address $A$ sends an update to its neighbor $B$
specifying that $A$ is using $B$ to get to at least one destination
$D$, but the message does not reach $B$, which then starts using $A$
to reach $D$.
An additional simple rule to send an update message can be used to
eliminate permanent looping due to lost packets using unreliable
broadcasting:
[LORA-4:
A data packet is received from a neighbor who, according to its
source tree, is in the path to the destination specified in the
data packet. This rule is needed to eliminate permanent looping
under unreliable broadcasting.
Garcia-Luna-Aceves, Spohn, Beyer [Page 13]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
Details on The Processing of Input Events
The next version of this draft will provide a detailed account of how
input events (topology changes and update messages) are processed by
a router running STAR. Details can be found in [11, 12].
The neighbor set of the router is empty initially, and the sequence
number counter is set to zero.
If the neighbor protocol reports a new link to a neighbor $k$ (or the
mechanisms used instead of the neighbor protocol based on the recep-
tion of neighbor packets), the router then sends an update message to
its neighbor.
Router $i$ updates its source tree when router $i$ receives an update
message from neighbor $k$ or when the parameters of an outgoing link
have changed. First, the topology graphs $TG sub i$ and $TG sup i
sub k$ are updated, then the source trees $ST sup i sub k$ and $ST
sub i$ are updated, which may cause the router to update its routing
table and to send its own update message.
The state of a link in the topology graph $TG sub i$ is updated with
the new parameters for the link if the link-state update in the
received message is valid, i.e., if the LSU has a larger sequence
number than the sequence number of the link stored in $TG sub i$.
The parameters of a link in $TG sup i sub k$ are always updated when
processing an LSU sent by a neighbor $k$, even if the link-state
information is outdated, because they report changes to the source
tree of the neighbor. A node in a source tree $ST sup i sub k$ can
have only one link incident to it. Hence, when $i$ receives an LSU
for link $(u, v)$ from $k$ the current incident link $(u', v)$ to
$v$, with $u$ being different than $u'$, is deleted from $TG sup i
sub k$.
The information of an LSU reporting the failure of a link is dis-
carded if the link is not in the topology graph of the router.
A shortest-path algorithm (SPF) based on Dijkstra's SPF is run on the
updated topology graph $TG sup i sub k$ to construct a new source
tree $ST sup i sub k$, and then run on the topology graph $TG sub i$
to construct a new source tree $ST sub i$.
The incident link to a node $v$ in router's $i$ new source tree
is different from the link in the current source tree $ST sub i$
only if the cost of the path to $v$ has decreased or if the
incident link in $ST sub i$ was deleted from the source trees of all
neighbors.
Garcia-Luna-Aceves, Spohn, Beyer [Page 14]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
A new source tree $newST$ for a neighbor $k$, including the router's
new source tree, is then compared to the current source tree $ST sup
i sub k$, and the links that are in $ST sup i sub k$ but not in
$newST$ are deleted from $TG sup i sub k$. After deleting a link
$(u, v)$ from $TG sup i sub k$ the router sets $TG sub i (u, v).del$
to TRUE if the link is not present in the topology graphs $TG sup i
sub x$ for all $x$ in $N sub i$.
If a destination $v$ becomes unreachable, i.e., there is no path
to $v$ in the new source tree $newST$, then LSUs will be broadcast
to the neighbors for each link in the topology graph $TG sub i$ that
have $v$ as the tail node of the link and a link cost infinity.
The new router's source tree $newST$ is compared to the last reported
source tree (${ST sub i}'$ for LORA and $ST sub i$ for ORA), and an
update message that will be broadcast to the neighbors is constructed
from the differences of the two trees. An LSU is generated if the
link is in the new source tree but not in the current source tree, or
if the parameters of the link have changed. For the case of a router
running LORA, the source trees are only compared with each other if
at least one of the three conditions (LORA-1, LORA-2, and LORA-3) is
met, i.e., $M sub i =$ TRUE.
If the new router's source tree was compared against the last
reported source tree then the router removes from the topology graph
all the links that are no longer used by any neighbor in their source
trees.
Finally, the current shortest-path tree $ST sup i sub k$ is discarded
and the new one becomes the current source tree. The router's source
tree is then used to compute the new routing table, using for example
a depth-first search in the shortest-path tree.
Packet Formats
An update message in STAR has the following format:
Garcia-Luna-Aceves, Spohn, Beyer [Page 15]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+
| |
| HEADER ( 4-8 bytes) |
| |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+
| |
| ACKNOWLEDGMENT LIST ( 6 bytes per neighbor) |
| |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+
| |
| LSU LIST ( 24 + link parameters bytes ) |
| |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+
The header specifies control information for the proper processing of
acknowledgments to prior updates and LSUs contained in the update
message. Acknowledgments are specified in the acknowledgment list and
LSUs are specified in the LSU list of the message.
There are four types of packets in STAR: GUM, PUM, TUM, RUM, and SUM.
A SUM packet (Start Update Message) is broadcast or unciast and indi-
cates that the router has restarted operation. A GUM packet (Goodbye
Update Message) is broadcast and indicates that the router will be
out of reach for some time and should not be used as a neighbor. A
PUM packet (Partial Update Message) is broadcast or unicast and con-
tains a partial update. A TUM packet (Total Update Message) is
broadcast or unicast and contains an atomic upate. A RUM packet
(Reset Update Message) is broadcast and informs neighbors to disre-
gard the sequence numbers used in prior update messages.
Packet Headers
The next version of this document will provide more details on the
packet formats used in STAR, and the REQUIRED and the OPTIONAl infor-
mation it uses.
The packet header for packet types: GUM, PUM, TUM, and RUM is the
following:
Garcia-Luna-Aceves, Spohn, Beyer [Page 16]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
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 | Num. of ACKs | Sequence Number |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
The packet header for packet type SUM is the following:
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 | Num. of ACKs | Sequence Number |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
The current version is Protocol version 1.
SUM (0x1) : Start Update Message (broadcast/unicast)
GUM (0x2) : Goodbye Update Message (broadcast)
PUM (0x3) : Partial Update Message (broadcast/unicast)
TUM (0x4) : Total Update Message (broadcast/unicast)
RUM (0x5) : Reset Update Message (broadcast)
The Number of ACKs denotes the number of entries in the Acknowledg-
ment List
The Sequence Number has values in the range [0, 2^15 - 1]. The Most
Significant Bit is used to request acknowledgments when set in the
sequence numbers specified at the Acknowledgment List.
The Router ID:
The first packet sent to a new neighbor (SUM) must carry the
router ID so that the neighbor get to know how to uniquely
Garcia-Luna-Aceves, Spohn, Beyer [Page 17]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
identify the router.
Acknowledgment List Entry
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
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| Neighbor's Address |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
|R| Expected Sequence Number |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
Neighbor's Address
The address of the neighbor we are acknowledging receipt of
packet(s).
R (The request for acknowledgment bit - BAR)
This bit is set when the router is requesting an acknowledgment
from the neighbor with address specified in the Acknowledgment
List Entry.
Expected Sequence Number
Corresponds to the sequence number of the next expected packet
from the neighbor. It acknowledges the receipt of all the
packets with smaller sequence number.
LSU List Entry
Garcia-Luna-Aceves, Spohn, Beyer [Page 18]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
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
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
|H| Head Prefix |T| Tail Prefix | Link Type | TOS Bit Vector|
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| Time Stamp |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| IP address of the Head of the Link |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| IP address of the Tail of the Link |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| ID of the Head of the Link (OPTIONAL) |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| ID of the Tail of the Link (OPTIONAL) |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| Parameters of the Link (VARIABLE LENGTH) |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
. . .
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| Parameters of the Link (VARIABLE LENGTH) |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
H (Head ID bit - HIB)
This bit is set to 1 if the field "ID of the Head of the Link"
is present in the LSU, it is set to 0 otherwise.
Head Prefix
Number of 1's in the network mask associated with the "IP
address of the Head of the Link".
T (Tail ID bit - TIB)
This bit is set to 1 if the field "ID of the Tail of the Link"
is present in the LSU, it is set to 0 otherwise.
Tail Prefix
Number of 1's in the network mask associated with the "IP
address of the Tail of the Link".
Garcia-Luna-Aceves, Spohn, Beyer [Page 19]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
Link Type
LSU_BROADCAST (0x01) : Broadcast
LSU_P2P (0x02) : Point-to-Point with subnet
LSU_P2P_UN (0x03) : Point-to-Point unnumbered
LSU_P2P_BR (0x04) : Point-to-Point broadcast
LSU_ROUTER_TO_HOST (0x05) : Link to a host
LSU_LINK_EXTERNAL (0x06) : Link to EXTERIOR ROUTING information
TOS Bit Vector
The iTH bit in the vector is set to 1 if the link is present in
the source tree of the TOS associated with the iTH bit, other-
wise the iTH bit is set to 0.
Time Stamp
Used to determine if the LSU carries up-to-date information.
The time stamp corresponds to the number of seconds elapsed
from January 1st, 1990, to the moment the head of the link
generates the LSU reporting changes in the parameters of the
link. A router maintains a clock that does not reset when the
router stops operating. A time stamp based on 32 bits requires
resetting after 136 years of operation.
IP address of the Head of the Link
Corresponds to the IP address of the network interface through
which the head of the link has a bidirectional link with the
router at the tail of the link.
IP address of the Tail of the Link
Corresponds to the IP address of the network interface through
which the tail of the link has a bidirectional link with the
router at the head of the link. This field can be a vector of
IP addresses if the "Link Type" is LSU_ROUTER_TO_HOST (the
number of instances is then determined by "Number of Links".
ID of the Head of the Link (OPTIONAL)
This field is required if the head of the link has multiple
Garcia-Luna-Aceves, Spohn, Beyer [Page 20]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
network interfaces with different IP address. It specifies an
ID that uniquely identifices the head of the link in the
network, and should be chosen among the set of IP addresses
assigned to the router.
ID of the Tail of the Link (OPTIONAL)
This field is required if the tail of the link has multiple
network interfaces with different IP address. It specifies an
ID that uniquely identifices the tail of the link in the
network, and should be chosen among the set of IP addresses
assigned to the router.
Parameters of the Link
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 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
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
|Num. of Metrics| Metric 1 Type | Metric 2 Type | Metric 3 Type |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| Metric 1 Value |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| Metric 2 Value |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
| Metric 3 Value | Padding |
+-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-*-+-+-+-+-+-+-+-+
References
[1] V. Bharghavan , A. Demers , S. Shenker and L. Zhang , ``
MACAW: A Media Access Protocol for Wireless LAN's '' Proc. ACM
SIGCOMM 94 , London, UK, Aug. 31 - Sep. 2, 1994.
Garcia-Luna-Aceves, Spohn, Beyer [Page 21]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
[2] J. Behrens and J. J. Garcia-Luna-Aceves, ``Hierarchical Routing
Using Link Vectors,'' Proc. IEEE INFOCOM 98 , San Francisco, Cal-
ifornia, March 29-April 2, 1998
[3] D. Bertsekas and R. Gallager, Data Networks , Second Edition,
Prentice-Hall, Inc., 1992.
[4] J. Broch et al, ``A Performance Comparison of Multi-Hop Wireless Ad
Hoc Network Routing Protocols,'' Proc. ACM MOBICOM 98 , Dallas, TX,
October 1998.
[5] J. Broch et al, ``The Dynamic Source Routing Protocol for Mobile Ad
Hoc Networks,'' draft-ietf-manet-dsr-01.txt, December 1998.
[6] R. Dube et al., ``Signal Stability-Based Adaptive Routing (SSA) for
Ad-Hoc Mobile Networks,'' IEEE Pers. Commun. February 1997.
[7] C. L. Fullmer and J.J. Garcia-Luna-Aceves , `` Solutions to Hid-
den Terminal Problems in Wireless Networks ,'' Proc. ACM SIGCOMM 97
, Cannes, France, September 14-18, 1997.
[8] J.J. Garcia-Luna-Aceves and J. Behrens, ``Distributed, scalable
routing based on vectors of link states,''
IEEE Journal on Selected Areas in Communications , Vol. 13, No.
8, 1995.
[9] J.J. Garcia-Luna-Aceves et al., ``Wireless Internet Gateways
(WINGS),'' Proc. IEEE MILCOM'97 , Monterey, California, November
1997.
[10] J.J. Garcia-Luna-Aceves and M. Spohn, ``Scalable Link-State Inter-
net Routing,'' Proc. IEEE International Conference on Network
Protocols (ICNP 98) , Austin, Texas, October 14-16, 1998.
[11] J.J. Garcia-Luna-Aceves and M. Spohn, ``
Proc. IEEE International Conference on Network Protocols (ICNP
99) , November 1999.
Garcia-Luna-Aceves, Spohn, Beyer [Page 22]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
[12] J.J. Garcia-Luna-Aceves and M. Spohn, ``Efficient Routing in
Packet-Radio Networks Using Link-State Information,'' Proc. IEEE
WCNC 99, August 1999.
[13] Z. Haas and M. Pearlman, ``The Zone Routing Protocol for Highly
Reconfigurable Ad-Hoc Networks,'' Proc. ACM SIGCOMM 98 , Van-
couver, British Columbia, August 1998.
[14] P802.11--Unapproved Draft: Wireless LAN Medium Access Control (MAC)
and Physical Specifications , IEEE, January 1996.
[15] D. Johnson and D. Maltz, ``Protocols for Adaptive Wireless and
Mobile Networking,'' IEEE Pers. Commun. , Vol. 3, No. 1, February
1996.
[16] J. Jubin and J. Tornow, ``The DARPA Packet Radio Network Proto-
cols,'' Proceedings of the IEEE , Vol. 75, No. 1, January 1987.
[17] P. Karn , `` MACA - a new channel access method for packet
radio,'' in ARRL/CRRL Amateur Radio 9th Computer Networking
Conference , pp. 134--40, ARRL , 1990.
[18] L. Kleinrock and F. Kamoun, ``Hierarchical Routing for Large Net-
works: Performance Evaluation and Optimization,'' Computer Net-
works , Vol. 1, pp. 155-174, 1977.
[19] V.O.K. Li and R. Chang, ``Proposed routing algorithms for the US
Army mobile subscriber equipment (MSE) network,'' Proc. IEEE MIL-
COM'86 , Monterey, California, October 1986.
[20] J. Moy, ``OSPF Version 2,'' RFC 1583, Network Working Group, March
1994.
[21] V. Park and M. Corson, ``A Highly Adaptive Distributed Routing
Algorithm for Mobile Wireless Networks,'' Proc. IEEE INFOCOM 97 ,
Kobe, Japan, April 1997.
Garcia-Luna-Aceves, Spohn, Beyer [Page 23]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
[22] C. Perkins and P. Bhagwat, ``Highly Dynamic Destination-Sequenced
Distance-Vector Routing (DSDV) for Mobile Computers,'' Proc. ACM
SIGCOMM 94 , London, UK, October 1994.
[23] C. Perkins, ``Ad-Hoc On Demand Distance Vector (AODV) Routing,''
draft-ietf-manet-aodv-00.txt, November 1997.
[24] M. Pursley and H.B. Russell, ``Routing in Frequency-Hop Packet
Radio Networks with Partial-Band Jamming,''
IEEE Trans. Commun. , Vol. 41, No. 7, pp. 1117-1124, 1993.
[25] R. Ramanathan and M. Steenstrup, ``Hierarchically-organized, Mul-
tihop Mobile Wireless Networks for Quality-of-Service Support,''
ACM Mobile Networks and Applications , Vol.3, No. 1, pp. 101-119,
1998.
[26] C.V. Ramamoorthy and W. Tsai, ``An Adaptive Hierarchical Routing
Algorithm," Proceedings of IEEE COMPSAC '83, Chicago, Illinois,
pp. 93-104, November 1983.
[27] S. Murthy and J.J. Garcia-Luna-Aceves, ``An Efficient Routing
Protocol for Wireless Networks,'' ACM Mobile Networks and Appli-
cations Journal , Special issue on Routing in Mobile Communication
Networks, 1996.
[28] S. Murthy and J.J. Garcia-Luna-Aceves, ``Loop-Free Internet Routing
Using Hierarchical Routing Trees,'' Proc. IEEE INFOCOM 97 , Kobe,
Japan, April 7-11, 1997.
[29] M. Steenstrup (Ed.), Routing in Communication Networks ,
Prentice-Hall, 1995.
[30] C-K. Toh, ``Wireless ATM and Ad-Hoc Networks,'' Kluwer, November
1996.
[31] C. Zhu and S. Corson, ``A Five Phase Reservation Protocol (FPRP)
for Mobile Ad-Hoc Networks,'' Proc. IEEE INFOCOM 98.
Garcia-Luna-Aceves, Spohn, Beyer [Page 24]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
[32] The CMU Monarch Project, ``Wireless and Mobility Extensions to ns-2
- Snapshot 1.0.0-beta,'' URL: http://www.monarch.cs.cmu.edu/cmu-
ns.html, August 1998.
Implementation Status
We have implemented STAR running in gated. For convenienece, in this
implementation, STAR runs on top of UDP, just like RIP. We have
demonstrated STAR several times at DARPA PI meetings running in
testbed wireless internetworks consisting of wireless links and wired
segments.
The gated code for STAR can be made available to the MANET community
upon request.
We have verified the correctness of STAR, and the proof of its
correctness is presented in a forthcoming journal publication.
The exact same code used in the gated implementation of STAR has been
used in simulations comparing its performance against on-demand rout-
ing approaches. Part of these results appear in [11, 12].
An OPNET model of STAR is almost complete at the time of this writ-
ing, and we will start a public-domain simulation of STAR in the Par-
sec (GloMoSIM) package developed by UCLA.
The design and development work on STAR has been sponsored bt the
DARPA GloMo Program (Rob Ruth, Program Manager).
Chair's Address
The Working Group can be contacted via its current chairs:
Garcia-Luna-Aceves, Spohn, Beyer [Page 25]
Internet DRAFT Source Tree Adaptive Routing Protocol 22 October 1999
M. Scott Corson
Institute for Systems Research
University of Maryland
College Park, MD 20742
USA
Phone: +1 301 405-6630
Email: corson@isr.umd.edu
Joseph Macker
Information Technology Division
Naval Research Laboratory
Washington, DC 20375
USA
Phone: +1 202 767-2001
Email: macker@itd.nrl.navy.mil
Authors' Addresses
Questions about this document can also be directed to:
Garcia-Luna-Aceves, Spohn, Beyer [Page 26]
