[Docs] [txt|pdf] [Tracker] [WG] [Email] [Nits]

Versions: 00

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]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/