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 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 _o_p_t_i_m_u_m _r_o_u_t_i_n_g _a_p_p_r_o_a_c_h (ORA) and the _l_e_a_s_t- _o_v_e_r_h_e_a_d _r_o_u_t_i_n_g _a_p_p_r_o_a_c_h (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 _s_o_u_r_c_e _t_r_e_e 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 _h_e_a_dnode 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]