Transmission-efficient routing in wireless networks using link-state information.
The efficiency with which the routing protocol of a multihop packet-radio network uses transmission bandwidth is critical to the ability of the network nodes to conserve energy. We present and verify the source-tree adaptive routing (STAR) protocol, which we show through simulation experiments to be far more efficient than both table-driven and on-demand routing protocols proposed for wireless networks in the recent past. A 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 destination. To conserve transmission bandwidth and energy, a router transmits changes to its source routing tree only when the router detects new destinations, the possibility of looping, ot the possibility of  node failures or network partitions. Simulation results show that STAR is an order of magnitude more efficient than any topology-broadcast protocol proposed to date and depending on the scenario is up to six times more efficient than the Dynamic Source Routing (DSR) protocol, which has been shown to be one of the best performing on-demand routing protocols.
Introduction
Multi-hop packet-radio networks, or ad-hoc networks, consist of mobile hosts interconnected by routers
that can also move. The deployment of such routers is ad-hoc and the topology of the network is very
dynamic, because of host and router mobility, signal loss and interference, and power outages. In addition,
the channel bandwidth available in ad-hoc networks is relatively limited compared to wired networks,
and untethered routers may need to operate with battery-life constraints.
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 protocols 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 protocols. Routers running a
link-state protocol use topology information to make routing decisions; routers running a distance-vector
protocol use distances and, in some cases, path information, to destinations to make routing decisions.
In an on-demand routing protocol, routers maintain path information for only those destinations that
they need to contact as a source or relay of information. The basic approach consists of allowing 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 [17], and there are several more recent examples of this approach (e.g., AODV [21],
ABR [28], DSR [13], TORA [19], SSA [6], ZRP [11]). The Dynamic Source Tree (DSR) protocol has
been shown to outperform many other on-demand routing protocols [4]. All of the on-demand routing
protocols reported to date are based on distances to destinations, and there have been no on-demand
link-state proposals to date. 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 on
distance vectors are the routing protocol of the DARPA packet-radio network [14], DSDV [20], WRP [25],
WIRP [9], and least-resistance routing protocols [22]. 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 network 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 [23, 24, 27].
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. In this paper, we
introduce and analyze the source-tree adaptive routing (STAR) protocol, which is the first example of a
table-driven routing protocol that is more efficient than any on-demand routing protocol by exploiting
link-state information and allowing paths taken to destinations to deviate from the optimum in order to
save bandwidth.
The intuition behind the approach used in STAR can be stated as follows: In an on-demand routing
protocol, every source polls all the destinations to find paths to a given destination; conversely, in a
table-driven routing protocol, every destination polls all the sources in the sense that they obtain paths
to a destination resulting from updates originated by the destination. Therefore, given that some form
of flooding occurs in either approach, it should be possible to obtain a table-driven protocol that needs
to poll as infrequently as on-demand routing protocols do to limit the overhead of the routing protocol.
In STAR, a router sends updates to its neighbors regarding the links in its preferred paths to destina-
tions. The links along the preferred paths from a source to each desired destination constitute a source
tree that implicitly specifies the complete paths from the source to each destination. Each router computes
its source tree based on information about adjacent links and the source trees reported by its neighbors,
and reports changes to its source tree to all its neighbors incrementally or atomically. The aggregation of
adjacent links and source trees reported by neighbors constitutes the partial topology known by a router.
Unlike any of the hierarchical link-state routing schemes proposed to date for packet-radio networks [27],
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 [16, 27, 26, 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.
Section 2 describes two different approaches that can be used to update routing information in wireless
networks: the optimum routing approach (ORA) and the least-overhead routing approach (LORA), and
elicit the reasons why STAR is the first table-driven routing protocol that can adopt LORA. Section 3
describes STAR and how it supports ORA and LORA. Section 4 demonstrates that routers executing
STAR stop disseminating link-state updates and obtain shortest paths to destinations within a finite
time after the cost of one or more links changes. Section 5 compares STAR's performance against
the performance of other table-driven and on-demand routing protocols using simulation experiments.
These experiments use the same methodology described by Broch et al. to compare on-demand routing
protocols [4], and our simulation code is the same code that runs in embedded wireless routers; the code we
used for DSR was ported from the ns2 code for DSR available from CMU [30]. The simulation results show
that STAR is four times more bandwidth-efficient than the best-performing link-state routing protocol
previously proposed, an order of magnitude more bandwidth-efficient than topology broadcasting, and
far more bandwidth-efficient than DSR, which has been shown to incur the least overhead among several
on-demand routing protocols [4]. To our knowledge, this is the first time that any table-driven routing
protocol has been shown to be more efficient than on-demand routing protocols in wireless networks.
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 contrast,
with LORA, the routing protocol attempts to provide viable 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,
maximum available battery life, or combinations of metrics. Multiple TOS can be supported in a routing
protocol; however, this paper focuses on a single TOS to address the performance of routing protocols
providing ORA, and uses shortest-path routing as the single TOS supported for ORA. We assume that
a single metric, which can be a combination of parameters, is used to assign costs to links.
On-demand routing protocols such as DSR follow LORA, in that these protocols attempt to minimize
control overhead by: (a) maintaining path information 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 protocols as a form of polling of
destinations by the sources. In contrast, in a table-driven routing protocol, it is the destinations who poll
the sources, meaning that the sources obtain their paths to destinations 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 frequently, the rate of update messages increases dramatically, consuming the
bandwidth needed for user data. The two methods used to reduce the update rate in table-driven routing
protocols are clustering 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
introduces 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 [14]; however,
control traffic still has to flow periodically to update routing tables.
A nice feature of such routing protocols as DSR [13] and WIRP [9] is that these protocols remain quiet
when no new update information has to be exchanged; they have no need for periodic updates. Both
protocols take advantage of promiscuous listening of any packets sent by router's neighbors to determine
the neighborhood of the router. A key difference between DSR and WIRP is that DSR follows LORA
while WIRP follows ORA, which means that WRP may incur unnecessary overhead when the network
topology is unstable.
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 destinations 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. Accordingly, 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. In the next section, we describe STAR, which is the
first table-driven routing protocol that implements LORA.
3 STAR Description
3.1 Network Model
In STAR, routers maintain a partial topology map of their network. In this paper we focus on flat
topologies only, i.e., there is no aggregation of topology information into areas or clusters.
To describe STAR, the topology of a network is modeled as a directed graph
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 of unlimited capacity updated according to a FIFO
policy. In a wireless network, a node can have connectivity with multiple nodes in a single physical radio
link. For the purpose 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 messages 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.
An underlying protocol, which we call the neighbor protocol, assures that a router detects within a
finite time the existence of a new neighbor and the loss of connectivity with a neighbor. 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.
3.2

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 adjacent 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
neighbor. 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.
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 destination 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 characteristics 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 head node 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.
3.3 Information Stored and Exchanged
We assume in the rest of the paper that a single parameter is used to characterize a link in one of its
directions, which we will call the cost of the directed link. Furthermore, although any type of local route
selection algorithm can be used in STAR, we describe STAR assuming that Dijkstra's shortest-path first
(SPF) algorithm is used at each router to compute preferred paths.
An LSU for a link (u; v) in an update message is a tuple (u; v; l; sn) reporting the characteristics of the
link, where l represents the cost of the link and sn is the sequence number assigned to the LSU.
A router i maintains a topology graph routing table, the set of neighbors N i ,
the source trees ST i
x
reported by each neighbor x 2 N i , and the topology graphs
x
reported by each
neighbor x 2 N i . The record entry for a link (u; v) in the topology graph of router i is denoted
and is defined by the tuple (u; v; l; sn; del), and an attribute p in the tuple is denoted by v):p. The
same notation applies to a link (u; v) in ST i , ST i
x
, and
x
. v):del is set to TRUE if the link is
not in the source tree of any neighbor.
A vertex v in
is denoted
(v). It contains a tuple (d; pred; suc; d whose values are
used on the computation of the source tree.
(v):d reports the distance of the path
(v):pred
is v's predecessor in i ; v,
(v):suc is the next hop along the path towards v, suc 0 holds the address
of the previous hop towards v, d 0 corresponds to the previous distance to v reported by suc 0 , 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 i , ST i
x
, and
x
The source tree ST i is a subset of TG i . The routing table contains record entries for destinations
in ST 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 destination.
The topology graph
x
contains the links in ST i
x
and the links reported by neighbor x in a message
being processed by router i, after processing the message
x
x
A router i running LORA also maintains the last reported source tree ST 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 specification. 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 constant bias.
We refer to an LSU that has a cost infinity as a RESET,
, and ST i
3.4 Validating Updates
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 ascertain when a given LSU is valid and avoid the possibility of LSUs circulating
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 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 [18] and every single routing protocol based on sequence numbers or time stamps does!
To simplify our description, the specification in the rest of this paper describes STAR as if unbounded
counters were available to keep track of sequence numbers.
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 update messages are
exchanged.
3.5.1 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.
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 destination, 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 message. Else, a simple way to implement an
initialization action consists 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 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 destination j is longer than the
reported distance from the previous successor to the same destination. However, if the link
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 determine 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 successor 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 different 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. The following
example illustrates this scenario. Consider the six-node wireless network shown in Figure 1 and assume
that the third part of LORA-3 is not in effect at the routers running STAR. In this example, nodes are
given identifiers that are lexicographically ordered, i.e., a is the smallest identifier and f is the largest
a
c
f
d
e
(c)
a
c
f
d
e
(d)
a
c
f
d
e
a
c
f
d
e

Figure

1: An example of a six node wireless network with routers running STAR without the third part
of LORA-3 being in effect.
identifier in the graph. All links and nodes are assumed to have the same propagation delays, and all the
links but link (b; c) have unit cost. Figures 1(b) through 1(d) show the source trees according to STAR
at the routers indicated with filled circles for the network topology depicted in Figure 1(a). Arrowheads
on solid lines indicate the direction of the links stored in the router's source tree. Figure 1(e) shows c's
new source tree after processing the failure of link (c; d); we note that c does not generate an update
message, because c ? b by assumption. Suppose link (b; e) fails immediately after the failure of (c; d),
node b computes its new source tree shown in Figure 1(f) without reporting changes to it because a is its
new successor to destinations d, e, and f , and a ! b. A permanent loop forms among nodes a, b, and c.

Figure

2 depicts the sequence of events triggered by the execution of the third part of LORA-3 in
the same example introduced in Figures 1, after the failures of links (c; d) and (b; e). The figure shows
the LSUs generated by the node with filled circle transmitted in an update message to the neighbors,
and shows such LSUs in parentheses. The third element in an LSU corresponds to the cost of the link
(a RESET has cost infinity). Unlike in the previous example, node c transmits an update message
after processing the failure of link (c; d) because of the third part of LORA-3; the distance from the new
successor b to d and f is longer than from the previous successor d. When link (b; e) fails, node b realizes
that the destinations d, e, and f are unreachable and generates an update message reporting the failure
of the link connecting to the head of the subtree of the source tree that becomes unreachable. The update
message from b triggers the update messages that allow nodes a, b, and c to realize that there are no
paths to d, e, and f . A similar sequence of events takes place at the other side of the network partition.
(b, e, 1) (e, d, 1) (e, f, 1)
(b)
a
c
f
d
e
(e, d, 1) (e, f, 1)
(c)
a
c
e
(b, e, infinity)
(d)
a
c
(b, e, infinity)
a
c
(b, e, infinity)

Figure

2: Example of a six-node wireless network with routers running STAR with the third part of
LORA-3 being in effect.
a
c
f
d
e
a
c
f
d
e
(b)

Figure

3: The third part of LORA-3 not always triggers the generation of an update message: (a) network
topology, and (b) the new source tree of node c after processing the failure of link (c; b).
The example shown in Figure 3 illustrates the scenario in which a router that chooses a new successor
to a destination with a larger distance to it does not need to send an update message. For this example,
the source trees of nodes a, b, and c are depicted in Figures 2(c), 1(c), and 2(b), respectively. Figure 3(b)
shows the new source tree of node c after the failure of link (c; b). In this case, c does not need to send
an update message because the parent node of the subtree headed by b is a neighbor of c and therefore
no permanent loop can be formed.
To ensure that the above rules work with incremental updates specifying 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:
ffl 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.
ffl 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 destina-
tions, 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. As the performance analysis of Section 5 shows, 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.
3.5.2 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 once to all neighbors, with the update message specifying only incremental
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 [29]).
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, 12, 15],
and IEEE 802.11 [12] appears to be the only commercial alternative at the MAC layer in ISM bands
today. 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 message 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.
3.6 Details on The Processing of Input Events

Figures

4 and 5 specify the main procedures of STAR (for both LORA and ORA approaches) used to
update the routing table and the link-state database at a router i. Procedure NodeUp is executed when
a router i starts up. 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 (procedure NeighborUp), the router then runs
Update with the appropriate message as input; the LSU in the message gets a current sequence number.
The same approach is used for link failures (NeighborDown) and changes in link cost (LinkCostChange).
When a router establishes connectivity to a new neighbor, the router sends its complete source tree to the
neighbor (much like a distance vector protocol sends its complete routing table). The LSUs that must
be broadcast to all neighbors are inserted into MSG i
The procedure Update is executed when router i receives an update message from neighbor k or when
the parameters of an outgoing link have changed. First, the topology graphs
and
are updated,
then the source trees ST i
and ST 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 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 i .
The parameters of a link in
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 i
can have only one link incident to it. Hence, when i receives an
LSU for link (u; v) from k the current incident link to v, u 6= u 0 , is deleted from
The information of an LSU reporting the failure of a link is discarded if the link is not in the topology
graph of the router.
A shortest-path algorithm (SPF) based on Dijkstra's SPF (procedure BuildShortestPathTree) is run
on the updated topology graph
to construct a new source tree ST i
, and then run on the topology
graph
to construct a new source tree ST 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 i only if the cost of the path to v has decreased or if the incident link in ST i was deleted
from the source trees of all neighbors.
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 i
(procedure UpdateNeighborTree), and the links that are in ST i
but not
in newST are deleted from
. After deleting a link (u; v) from
the router sets v):del to
TRUE if the link is not present in the topology graphs
x
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
that have v as the tail
node of the link and a link cost infinity.
This specification assumes that the Link Layer provides reliable broadcast of network-level packets and
consequently update messages specify only incremental changes to the router's source tree instead of the
complete source tree.
The new router's source tree newST is compared to the last reported source tree (ST i
for LORA and
(procedure ReportChanges), 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) described in Section 3.5.1 is met, i.e., M 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 i
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.
3.7 Example
The following example illustrates the working of STAR based on LORA. Consider the seven node wireless
network shown in Figure 6. All links and nodes are assumed to have the same propagation delays, and
all the links have unit cost. The figure shows only the LSUs with new information transmitted in update
messages to the neighbors, and shows such LSUs in parentheses located next to the node that generates
them. The third element in an LSU corresponds to the cost of the link (a RESET has cost infinity).

Figures

6(b) through 6(d) show the source trees according to STAR at the routers indicated with filled
circles for the network topology depicted in Figure 6(a). Arrowheads on solid lines indicate the direction
of the links stored in the router's source tree. When the link (f; g) fails (Figure 6(e)), the neighbor
protocol at node f triggers the execution of procedure NeighborDown, the link (d; g) is inserted into f 's
source tree and no update message is generated because f 's new successor towards g has an address
smaller than f and destination g is a neighbor of the new successor. Figure 6(f) shows the new source
tree of node d after the failure of link (d; g), since d has an address smaller than the new successor towards
g it is forced to send an update message reporting the new link added to the source tree. Nodes c, e,
and f do not generate any update message after processing d's message because there exist a path to all
description
f
description
Neighbor protocol reports connectivity to neighbor k
f
sendST / TRUE;
f
sendST / FALSE;
f
for each ( link (u; v) 2 ST i )
description
Neighbor protocol reports link failure to neighbor k
f
description
Neighbor protocol reports link cost change to neighbor k
f
description
Process update message msg sent by router k
f
description
Update
k from LSUs in msg
f
for each ( LSU (u; v; l; sn) 2 msg )
f
else
description
Update topology graphs
k from LSU (u; v; l; sn)
f
f
else
f
f
else
f
description
Update topology graphs
k from LSU
reporting link failure
f
f
f
f
f
Broadcast message MSG
f
for each ( vertex v 2
f
(v):d
(v):pred / null;
(k):d / 0;

Figure

4: STAR Specification
description
Construct ST i
f
set of vertices in
newST / ;;
while ( u 6= null and
f
(u):pred 6= null and
f
newST
f
path w u cost /
else
path w u cost / 0;
cost ?
f
for each ( vertex v 2 adjacency list of
f
f
else if (
else
else
f
else suc / k;
else
else u / null;
UpdateNeighborTree(k; newST );
f
f
else if ( ORA )
for each ( link (u; v) 2
f
k (u; v):l or
f
(v):d /
(v):pred /
f
was an unknown destination
else
description
Generate LSUs for new links in the router's source tree
f
for each ( link (u; v) 2 newST )
2 oldST or newST (u; v):sn 6= oldST (u; v):sn or NS i )
description
Delete links from
k and report failed links
f
for each ( link (u; v) 2 ST i
f
f
removed (u; v) from its source tree
f
// LORA-2 rule: k has no path to destination v
for each ( link
f
// i has no path to destination v or i is the head node
for each ( link
else if (
Needs to report failed link
f
f

Figure

5: STAR Specification (cont.)
a
c
f
d
e
(a)
a
c
f
d
e
(b)
a
c
f
d
e
(c)
a
c
f
d
e
(d)
a
c
f
d
e
a
c
f
d
e
(e, g, 1)

Figure

An example topology with links having unit cost, solid lines represent the links that are part
of the source tree of the node with filled circle, dashed lines represent links that are part of the network
topology, (a) network topology, (b) node's f source tree, (c) node's e source tree, (d) node's d source
tree, (e) node f does not generate any update message after adding link (d; g) to its source tree due to
the failure of link (f; g), (f) node d generates the update message with LSUs for links (e; g) and (d; g)
after detecting the failure of link (d; g).
destinations in the network and no routing loop was formed.
This example illustrates how link failures may not cause the generation of update messages by nodes
that have the failed link in their source trees as long as the nodes have a path to all destinations.
This section addresses STAR correctness for the case in which ORA is applied. The proof of correctness
under LORA is similar and is omitted for brevity. For simplicity, we assume that all links are point-to-
point and that shortest-path routing is implemented. Let t 0
be the time when the last of a finite number
of link-cost changes occur, after which no more such changes occurs. The network E) in which
STAR is executed has a finite number of nodes (j V j) and links (j E j), and every message exchanged
between any two routers is received correctly within a finite time. According to STAR's operation, for
each direction of a link in G, there is a router that detects any change in the cost of the link within a
finite time.
The following theorems assume the use of arbitrarily large sequence numbers in order to avoid having
to include cases in the proofs for which links are deleted due to aging.
Theorem 1: The dissemination of LSUs in STAR stops a finite time after t 0
Proof: A router that detects a change in the cost of any outgoing link must update its topology graph,
update its source tree as needed, and send an LSU if the link is added to or is updated in the source tree.
Let l be the link that last experiences a cost change up to t 0
, and let t l
be the time when the head of
the link l originates the last LSU of the sequence of LSUs originated as a result of the link-cost change
occurring up to t 0
. Any router that receives the LSU for link l originated at t l
must process the LSU
within a finite time, and decides whether or not to forward the LSU based on its updates to its source
tree. A router can accept and propagate an LSU only once because each LSU has a sequence
accordingly, given that G is finite, there can only be a finite chain of routers that propagate the LSU for
link l originated at t l , and the same applies to any LSU originated from the finite number of link-cost
changes that occur up to t 0
. Therefore, STAR stops the dissemination of LSUs a finite time after t 0
. 2
Because of Theorem 1, there must be a time t s ? t 0 when no more LSUs are being sent.
Theorem 2: In a connected network, and in the absence of link failures, all routers have the most
up-to-date link-states they need to compute shortest paths to all destinations within a finite time after t s .
Proof: The proof is by induction on the number of hops of a shortest path to a destination (the origin
of an LSU), and is similar to the proof for
Consider the shortest path from router s 0
to a destination j at time t s
, and let h be the number of
hops along such a path. For the path from s 0
to j consists of one of the router's outgoing links.
By assumption, an underlying protocol informs the router with the correct parameter values of adjacent
links within a finite time; therefore, the Theorem is true for
must have link (s 0
its
source tree and must have sent its neighbors an LSU for that link. Assume that the Theorem is true for
hops, i.e., that any router with a path of n or fewer hops to j has the correct link-state information
about all the links in the path and has sent LSUs to its neighbors with the most up-to-date state of each
such link, and consider the case in which the path from s 0
to j at time t s is
be the
next hop along the shortest path selected by s 0
to j at t s . The sub-path from s 1
to j has h hops and, by
the inductive assumption, such a path must be in the source tree of s 1 at time t s , which implies that all
the links in the path from s 1
to j are in its source tree, and that s 0
received and processed an LSU for
each link in the path from s 1
to j with the most recent link-state information. Because it is also true that
has the most recent link-state information about link (s
has the most recent
information about all the links in its chosen path to j. The Theorem is therefore true, because the same
argument applies to any chosen destination and router. 2
Theorem 3: All the routers of a connected network have the most up-to-date link-state information
needed to compute shortest paths to all destinations.
Proof: The result is immediate from Theorem 2 in the absence of link failures. Consider the case in
which the only link that fails in the network by time t 0
is link (s; d). Call this time t f - t 0
. According
to STAR's operation, router s sends an LSU reporting an infinite cost for (s; d) within a finite time after
furthermore, every router receiving the LSU reporting the infinite cost of (s; d) must forward the LSU
if the link exists in its topology graph, i.e., the LSU gets flooded to all routers in the network that had
heard about the link, and this occurs within a finite time after t 0
moreover, links with infinite cost are
not erased from the topology graph. It then follows that no router in the network can use link (s; d) for
any shortest path within a finite time after t 0
. Accordingly, within a finite time after t 0
all routers must
only use links of finite cost in their source trees; together with Theorem 2, this implies that the Theorem
is true. 2
Theorem 4: If destination j becomes unreachable from a network component C at t 0 ; the topology graph
of all routers in C includes no finite-length path to j.
Proof: STAR's operation is such that, when a link fails, its head node reports an LSU with an infinite
cost to its neighbors, and the state of a failed link is flooded through a connected component of the
network to all those routers that knew about the link. Because a node failure equals the failure of all
its adjacent links, it is true that no router in C can compute a finite-length path to j from its topology
graph after a finite time after t 0
. 2
Note that, if a connected component remains disconnected from a destination j all link-state information
corresponding to links for which j is the head node is erased from the topology graph of the routers
in the network component.
The previous theorems show that STAR sends correct routing tables within a finite time after link
costs change, without the need to replicate topology information at every router (like OSPF does) or use
explicit delete updates to delete obsolete information (like LVA and ALP do).
Performance Evaluation
5.1 Simulation Experiments
STAR has the same communication, storage, and time complexity than ALP [10] and efficient table-driven
distance-vector routing protocols proposed to date (e.g., WRP [25]). However, worst-case performance is
not truly indicative of STAR's performance; accordingly, we ran a number of simulation experiments to
compare STAR's average performance against the performance of table-driven and on-demand routing
protocols.
The protocol stack implementation in our simulator runs the very same code used in a real embedded
wireless router and IP (Internet Protocol) is used as the network protocol.
The link layer implements a medium access control (MAC) protocol similar to the IEEE 802.11 standard
and the physical layer is based on a direct sequence spread spectrum radio with a link bandwidth of 1
Mbit/sec. The neighbor protocol is configured to report loss of connectivity to a neighbor if the probation
of the link fails in a period of about 10 seconds.
The simulation experiments use 20 nodes forming an ad-hoc network, moving over a flat space (5000m
x 7000m), and initially randomly distributed at a density of one node per square kilometer. Nodes move
in the simulation according to the "random waypoint" model [4]. Each node begins the simulation by
remaining stationary for pause time seconds. It then selects a random destination and moves to that
destination at a speed of 20 meters per second for a period of time uniformly distributed between 5 and
seconds. Upon reaching the destination, the node pauses again for pause time seconds, selects another
destination, and proceeds there as previously described, repeating this behavior for the duration of the
simulation.
The simulation study was conducted in the C++ Protocol Toolkit (CPT) simulator environment. Two
sets of simulations were run. First, STAR based on ORA is compared against two other table-driven
routing protocols. Secondly, STAR based on LORA is compared with DSR, which has been shown to be
one of the best-performing on-demand routing protocols.
5.2 Comparison with Table-Driven Protocols
We chose to compare STAR against the traditional link-state approach and ALP [10]. The traditional
link-state approach (denoted by TOB for topology broadcast) corresponds to the flooding of link states
in a network, or within clusters coupled with flooding of inter-cluster connectivity among clusters. ALP
is a routing protocol based on partial link-state information that we have previously shown to outperform
prior table-driven distance-vector and link-state protocols. For these simulations STAR uses ORA since
both ALP and TOB attempt to provide paths that are optimum with respect to a defined metric. The
three protocols rely on the reliable delivery of broadcast packets by the link layer.
We ran our simulations with movement patterns generated for 5 different pause times: 0, 30, 45, 60,
and 90 seconds. A pause time of 0 seconds corresponds to continuous motion. The simulation time in all
the simulation scenarios is of 900 seconds.
As the pause time increases, we expect the number of update packets sent to decrease because the
number of link connectivity changes decreases. Because STAR and ALP generate LSUs for only those
links along paths used to reach destinations, we expect STAR and ALP to outperform any topology
broadcast protocol.
A router running ALP does not report to its neighbors the deletion of a link from its preferred paths
if the cost of the link has not increased (the state of the link transitions from 1 to 2). Consequently, all
the routers that have a link in state 2 in their topology graphs have to forward to their neighbors an LSU
that announces the failure of the link. Unlike ALP, routers running STAR only have in their topology
graphs link-state information for those links that are in the preferred paths of their neighbors, i.e., the
failure of a link will only make a router to send an update message reporting the failure if the link is
in the preferred paths of the router. Because of the dynamics in link connectivity change in a wireless
mobile network we expect STAR to outperform ALP.

Figures

7 and 8 depict the performance of STAR, ALP, and TOB in terms of the number of update
packets generated as a function of simulation time for four different pause times. The ordinates represent
the simulation time. Table 1 summarizes the behavior of the three protocols according to the pause time
of the nodes. The table shows the number of link connectivity changes and the total number of update
packets generated by the routing protocols; ALP generates on average more than 4 times update packets
than STAR, and topology broadcast generates more than 10 times packets than STAR.
Pause Connectivity Packets Generated
Time Changes STAR ALP TOB
90 50 138 623 1811

Table

1: Average performance of STAR, ALP, and the topology broadcast routing protocol for different
pause times.

Figure

9 shows the small number of update packets transmitted by STAR when routers are in continuous
motion; for 1090 changes in link connectivity the routers generated 2542 packets. The performance
of ALP and TOB for pause time 0 could not be assessed because the amount of update packets generated
by the routers lead to congestion at the link layer.
Because STAR can be used in combination with any clustering scheme proposed in the past for packet-radio
networks, it is clear from this study that STAR should be used instead of ALP and topology
broadcast for the provision of QoS routing in packet radio networks, given that any overhead traffic
associated with clustering would be equivalent for STAR, ALP, and topology broadcast.
5.3 Comparison with On-Demand Routing Protocols
We compare STAR using LORA with DSR, because DSR has been shown to be one of the best-performing
on-demand routing protocols [4].
As we have stated, our simulation experiments use the same methodology used recently to evaluate
DSR and other on-demand routing protocols [4]. To run DSR in our simulation environment, we ported
the ns2 code available from [30] into the CPT simulator. There are only two differences in our DSR
implementation with respect to that used in [4]: (1) in the embedded wireless routers and simulated
protocol stack we used there is no access to the MAC layer and cannot reschedule packets already
scheduled for transmission over a link (however, this is the case for all the protocols we simulate), and (2)
routers cannot operate their network interfaces in promiscuous mode because the MAC protocol operates
over multiple channels and a router does not know on which channels its neighbors are transmitting,
unless the packets are meant for the router. Both STAR and DSR can buffer 20 packets that are awaiting
discovery of a route through the network.
The overall goal of the simulation experiments was to measure the ability of the routing protocols to
react to changes in the network topology while delivering data packets to their destinations. To measure
this ability we applied to the simulated network three different communication patterns corresponding to
8, 14, and 20 data flows. The total workload in the three scenarios was the same and consisted of data
packets/sec, in the scenario with 8 flows each continuous bit rate (CBR) source generated 4 packets/sec,
in the scenario with 20 sources each CBR source generated 1.6 packets/sec, and in the scenario with 14
flows there were 7 flows from distinct CBR sources to the same destination D generating an aggregate of
4 packets/sec and 7 flows having D as the CBR source and the other 7 sources of data as destinations.
In all the scenarios the number of unique destinations was 8 and the packet size was 64 bytes. The data
flows were started at times uniformly distributed between 20 and 120 seconds (we chose to start the flows
after 20 seconds of simulated time to give some time to the Link Layer for determining the set of nodes
that are neighbors of the routers).
The protocol evaluations are based on the simulation of 20 wireless nodes in continuous motion
(pause time seconds of simulated time.

Tables

2 and 3 summarize the behavior of STAR and DSR according to the simulated time. The tables
show the total number of update packets transmitted by the nodes and the total number of data packets
delivered to the applications for the three simulated workloads. The total number of update packets
transmitted by routers running STAR varies with the number of changes in link connectivity while DSR
generates control packets based on both variation of changes in connectivity and the type of workload
inserted in the network. Routers running STAR generated less update packets than DSR in all simulated
scenarios, the difference increased significantly when data traffic was inserted in the network for 1800
seconds: routers running DSR sent from 100% to 600% more update packets than STAR when nodes
were moving during 1800 seconds of simulated time, and from 35% to 400% more update packets when
nodes were moving during 900 seconds. Both STAR and DSR were able to deliver about the same number
of data packets to the applications in the simulated scenarios with 8 and 14 flows. When we increased
the number of sources of data from 8 to 20 nodes, while inserting the same number of data packets in the
network (32 packets/sec), we observed that STAR was able to deliver as much as three times more data
packets than DSR during 1800 seconds of simulated time, and almost twice the amount of data packets
delivered by DSR during 900 seconds of simulated time.
Number Update Pkts Sent Data Pkts Delivered Data Pkts
of Flows STAR DSR STAR DSR Generated

Table

2: Average performance of STAR and DSR for nodes moving during 900 seconds of simulated time,
total changes in link connectivity was 1464.
Number Update Pkts Sent Data Pkts Delivered Data Pkts
of Flows STAR DSR STAR DSR Generated

Table

3: Average performance of STAR and DSR for nodes moving during 1800 seconds of simulated
time, total changes in link connectivity was 2714.
Number Protocol Number of Hops
of Flows 1
DSR 64.9 31.2 2.6 1.3
14 STAR 82.0 16.0 1.7 0.3
DSR 64.1 26.9 4.0 4.5 0.5
DSR 61.9 32.4 5.1 0.3 0.3

Table

4: Distribution of DATA packets delivered according to the number of hops traversed from the
source to the destination for nodes moving during 900 seconds of simulated time.
Number Protocol Number of Hops
of Flows 1
DSR 64.3 29.2 5.9 0.6
DSR 71.4 21.8 3.0 3.6 0.2

Table

5: Distribution of DATA packets delivered according to the number of hops traversed from the
source to the destination for nodes moving during 1800 seconds of simulated time.
The MAC layer discards all packets scheduled for transmission to a neighbor when the link to the
neighbor fails, which contributes to the high loss of data packets seen by nodes. In DSR, each packet
header carries the complete ordered list of routers through which the packet must pass and may be
updated by nodes along the path towards the destination. The low throughput achieved by DSR for
the case of 20 sources of data is due to the poor choice of source routes the routers make, leading to a
significant increase in the number of ROUTE ERROR packets generated. Data packets are also discarded
due to lack of routes to the destinations because the network may become temporarily partitioned or
because the routing tables have not converged in the highly dynamic topology we simulate.

Figures

10(a) through 10(c) show the cumulative distribution of packet delay experienced by data packets
during 900 seconds of simulated time, for a workload of 8, 14, and 20 flows respectively. Figures 11(a)
through 11(c) show the cumulative distribution of packet delay during 1800 seconds of simulated time.
The higher delay introduced by DSR when relaying data packets is not directly related with the number
of hops traversed by the packets (as shown in Tables 4 and 5) but with the poor choice of source routes
when the number of flows increase from 8 to 20.
In all the simulation scenarios the number of destinations was set to just 40% of the number of nodes in
the network in order to be fair with DSR. For the cases in which all the nodes in the network receive data,
STAR would introduce no extra overhead while DSR could be severely penalized. It is also important
to note the low ratio of update messages generated by STAR compared to the number of changes in link
connectivity (Tables 2 and 3).
We note that in cases where routers fail or the network becomes partitioned for extended time periods
the bandwidth consumed by STAR is much the same as in scenarios in which no router fails, because all
that must happen is for updates about the failed links to unreachable destinations to propagate across
the network. In contrast, DSR and several other on-demand routing protocols would continue to send
flood-search messages trying to reach the failed destination, which would cause a worst-case bandwidth
utilization for DSR. To illustrate the impact the failure of a single destination has in DSR we have re-run
the simulation scenario with 8 flows present in the network for 1800 seconds making one of the destinations
fail after 900 seconds of simulated time, routers running STAR sent 942 update packets while routers
running DSR sent 3043 update packets. The existence of a single flow of data to a destination that was
unreachable for 900 seconds made DSR to generate 55% more update packets while STAR generated
about the same number of updates (see Table 3).
6 Conclusions
We have presented STAR, a link-state protocol that incurs the smallest communication overhead of any
prior table-driven routing protocol, and also incurs less overhead than on-demand routing protocols.
STAR accomplishes its bandwidth efficiency by: (a) disseminating only that link-state data needed for
routers to reach destinations; (b) exploiting that information to ascertain when update messages must be
transmitted to detect new destinations, unreachable destinations, and loops; and (c) allowing paths to
deviate from the ideal optimum while not creating permanent loops. The bandwidth efficiency achieved
in STAR is critical for ad-hoc networks with energy constraints, because it permits routers to preserve
battery life for the transmission of user data while avoiding long-term routing loops or the transmission
of data packets to unreachable destinations.
Our simulation experiments show that STAR is an order of magnitude more efficient than the traditional
link-state approach, and more than four times more efficient than ALP (which has been shown
to outperform prior topology-driven protocols), in terms of the number of update packets sent. The
results of our experiments also show that STAR is more bandwidth efficient than DSR, which has been
shown to be one of the most bandwidth-efficient on-demand routing protocols. Because STAR can be
used with any clustering mechanism proposed to date, these results clearly indicate that STAR is a very
attractive approach for routing in packet-radio networks. Perhaps more importantly, the approach we
have introduced in STAR for least-overhead routing opens up many research avenues, such as developing
similar protocols based on distance vectors and determining how route aggregation works under LORA.



--R


"Hierarchical Routing Using Link Vectors,"
Data Networks
"A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Proto- cols,"
"The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks,"
"Signal Stability-Based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks,"
"Solutions to Hidden Terminal Problems in Wireless Networks,"
"Distributed, scalable routing based on vectors of link states,"
"Wireless Internet Gateways (WINGS),"
"Scalable Link-State Internet Routing,"
"The Zone Routing Protocol for Highly Reconfigurable Ad-Hoc Net- works,"

"Protocols for Adaptive Wireless and Mobile Networking,"
"The DARPA Packet Radio Network Protocols,"
"MACA - a new channel access method for packet radio,"
"Hierarchical Routing for Large Networks: Performance Evaluation and Optimization,"
"Proposed routing algorithms for the US Army mobile subscriber equipment (MSE) network,"
"OSPF Version 2,"
"A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,"
"Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,"
"Ad-Hoc On Demand Distance Vector (AODV) Routing,"
"Routing in Frequency-Hop Packet Radio Networks with Partial-Band Jamming,"
"Hierarchically-organized, Multihop Mobile Wireless Networks for Quality-of-Service Support,"
"An Adaptive Hierarchical Routing Algorithm,"
"An Efficient Routing Protocol for Wireless Networks,"
"Loop-Free Internet Routing Using Hierarchical Routing Trees,"
Routing in Communication Networks
"Wireless ATM & Ad-Hoc Networks,"
"A Five Phase Reservation Protocol (FPRP) for Mobile Ad-Hoc Networks,"
"Wireless and Mobility Extensions to ns-2 - Snapshot 1.0.0-beta,"
--TR
Data networks (2nd ed.)
Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers
Routing in communications networks
Solutions to hidden terminal problems in wireless networks
An efficient routing protocol for wireless networks
Hierarchically-organized, multihop mobile wireless networks for quality-of-service support
Location-aided routing (LAR) in mobile ad hoc networks
A distance routing effect algorithm for mobility (DREAM)
A performance comparison of multi-hop wireless ad hoc network routing protocols
Wireless ATM and Ad-Hoc Networks
Ad-hoc On-Demand Distance Vector Routing
A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks
Loop-Free Internet Routing Using Hierarchical Routing Trees
Source-Tree Routing in Wireless Networks

--CTR
Zhenjiang Li , J. J. Garcia-Luna-Aceves, Finding multi-constrained feasible paths by using depth-first search, Wireless Networks, v.13 n.3, p.323-334, June 2007
mobile wireless networks;source routing tree;link-state routing protocol