INTERNET-DRAFT October 1998 draft-ietf-manet-cedar-spec-00.txt Expires in six months Core Extraction Distributed Ad hoc Routing (CEDAR) Specification Raghupathy Sivakumar Prasun Sinha Vaduvur Bharghavan University of Illinois, Urbana-Champaign Status of this Memo This document is an Internet-Draft. 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." To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Abstract This draft presents CEDAR, a Core-Extraction Distributed Ad hoc Routing algorithm for QoS routing in ad hoc network environments. CEDAR has three key components: (a) the establishment and maintenance of a self-organizing routing infrastructure, called the "core", for performing route computations, (b) the propagation of the link-state of stable high-bandwidth links in the core through "increase/decrease" waves, and (c) a QoS route computation algorithm that is executed at the core nodes using only locally available state. Sivakumar, Sinha, Bharghavan [Page 1] INTERNET-DRAFT CEDAR Specification October 1998 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Network Model . . . . . . . . . . . . . . . . . . . . . . . 5 3. CEDAR Architecture and the Core . . . . . . . . . . . . . . 7 3a. Rationale for a Core-based Architecture in CEDAR . . . . . 8 3b. Generation and Maintenance of the Core in CEDAR . . . . . 10 3c. Core Broadcast and its Application to CEDAR . . . . . . . 12 4. QoS State Propagation in CEDAR . . . . . . . . . . . . . . 14 4a. Increase and Decrease Waves . . . . . . . . . . . . . . . 15 4b. Issues in link state propagation . . . . . . . . . . . . 19 5. QoS Routing in CEDAR . . . . . . . . . . . . . . . . . . . 20 5a. Establishment of the Core Path . . . . . . . . . . . . . 20 5b. QoS Route Computation . . . . . . . . . . . . . . . . . . 22 5c. Dynamic QoS Route Recomputation for Ongoing Connections . 24 6. Performance Results . . . . . . . . . . . . . . . . . . . 25 7. Conclusions . . . . . . . . . . . . . . . . . . . . . . . 26 8. References . . . . . . . . . . . . . . . . . . . . . . . . 27 9 . Authors' Addresses . . . . . . . . . . . . . . . . . . . . 28 Sivakumar, Sinha, Bharghavan [Page 2] INTERNET-DRAFT CEDAR Specification October 1998 1. Introduction An ad hoc network is a dynamic multi-hop wireless network that is established by a group of mobile hosts on a shared wireless channel by virtue of their proximity t[o each other. These channels, typically being scarce and dynamic, make it difficult to perform efficient resource utilization or to execute critical applications. Hence, QoS routing, as opposed to non-QoS routing, is desirable in such environments. This draft focuses on a restricted QoS Routing problem: the satisfaction of minimum bandwidth requirements. Of course, since the network is highly dynamic, and transmissions are susceptible to fades, interference, and collisions from hidden/exposed stations, CEDAR cannot provide bandwidth guarantees for the computed routes. Rather, its goal is to provide routes that are highly likely to satisfy the bandwidth requirement of a route, so long as such routes exist [1]. Given the nature of the network and the requirements of the applications, the following are the key goals of CEDAR. (a) Route computation must be distributed because centralized routing in a dynamic network is impossible even for fairly small networks. (b) Route computation should not involve the maintenance of global state, or even significant amounts of volatile non-local state. In particular, link state routing is not feasible for highly dynamic networks because of the significant state propagation overhead when the network topology changes. (c) As few nodes as possible must be involved in state propagation and route computation (without becoming single points of failure), since this involves monitoring and updating at least some state in the network. On the other hand, every host must have quick access to routes on-demand. (d) Each node must only care about the routes corresponding to its destination, and must not be involved in frequent topology updates for parts of the network to which it has no traffic. (e) Stale routes must be either avoided, or detected and eliminated quickly. (f) Broadcasts must be avoided as far as possible because broadcasts are highly unreliable in ad hoc networks. (g) If the topology stabilizes, then routes must converge to the optimal routes, and (h) It is desirable to have a backup route when the primary route has become stale and is being recomputed. QoS routing for ad hoc networks is relatively unchartered territory. In addition to the above, we have the following goals for QoS routing in ad hoc networks. (a) Applications provide a minimum bandwidth requirement for a connection, and the routing algorithm must efficiently compute a route that can satisfy the bandwidth requirement with high probability. (b) The amount of state propagation and topology update information must be kept to a Sivakumar, Sinha, Bharghavan [Page 3] INTERNET-DRAFT CEDAR Specification October 1998 minimum. In particular, every change in available bandwidth should not result in updated state propagation. (c) Dynamic links (either unstable or low bandwidth links) must not cause state propagation throughout the network. Only stable high bandwidth link information must be propagated throughout the network, and (d) The QoS route computation algorithm should be simple and robust. Robustness, rather than optimality, is the key requirement. In order to achieve the above goals, this draft proposes the Core- Extraction Distributed Ad hoc Routing (CEDAR) algorithm for QoS routing in ad hoc networks. Briefly, CEDAR dynamically establishes a "core" of the network, and then incrementally propagates link state of stable high bandwidth links to the nodes of the core. Route computation is on-demand, and is performed by core hosts using local state only. CEDAR is proposed as a QoS routing algorithm for small to medium size ad hoc networks consisting of tens to hundreds of nodes. CEDAR does not compute optimal routes because of the minimalist approach to state management, but the trade-off of robustness and adaptation for optimality is believed to be well justified in ad hoc networks. The following is a brief description of the three key components of CEDAR. 1. Establishment and Maintenance of a core using Local Core Extraction CEDAR does core extraction in order to extract a subset of nodes in the network that would be the only ones that perform state management and route computation. The core extraction is done dynamically by approximating a minimum dominating set of the ad hoc network using only local computation and local state. Each host in the core then establishes a virtual link (via a tunnel) to nearby core hosts (within the 3rd neighborhood in the ad hoc network). Each core host maintains the local topology of the hosts in its domain, and also performs route computation on behalf of these hosts. The core computation and core management upon change in the network topology are purely local computations to enable the core to adapt efficiently to the dynamics of the network. 2. Link State Propagation using Increase/Decrease waves While it is possible to execute ad hoc routing algorithms using only local topology information at the core nodes, QoS routing in CEDAR is achieved by propagating, in the core, the bandwidth availability information of stable links. The basic idea is that the information about stable high-bandwidth links can be made known to core nodes far away in the network, while information about dynamic links or low bandwidth links should remain local. By means of this link state propagation mechanism, CEDAR approximates Sivakumar, Sinha, Bharghavan [Page 4] INTERNET-DRAFT CEDAR Specification October 1998 a minimalist local state algorithm in highly dynamic networks while it approaches the maximalist link state algorithm in highly stable networks. The propagation of link-state is achieved through slow-moving 'increase' waves (which denote increase of bandwidth) and fast-moving 'decrease' waves (which denote decrease of bandwidth), which traverse the core. The key questions to answer in link state propagation are: when should an increase/decrease wave be initiated, how far should a wave propagate, and how fast should a wave propagate. 3. Route Computation Route computation first establishes a core path from the domain of the source to the domain of the destination. This initial phase involves probing on the core, and the resultant core path is cached for future use. The core path provides the directionality of the route from the source to the destination. Using this directional information, CEDAR iteratively tries to find a partial route from the source to the domain of the furthest possible node in the core path (which then becomes the source for the next iteration) which can satisfy the requested bandwidth, using only local information. Effectively, the computed route is a concatenation of the shortest-widest-furthest (the least hop path among the maximum bandwidth paths) paths found locally using the core path as the guideline. Several algorithms have been proposed for routing in ad hoc networks. The ad hoc routing algorithms proposed in [2,3,4] provide a single route in response to a route query from a source. Previous work on tactical packet radio networks had led to many of the fundamental results in ad hoc networks. [3] has proposed an architecture similar to the "core" called the linked clusterhead architecture but it uses gateways for communication between clusterheads and does not attempt to minimize the size of the core infrastructure. The multipath routing algorithms proposed in [6,7,8] are more robust than the single route on demand algorithms, at the cost of higher memory and message requirements. 2. Network Model This section describes the network model and the terminology used in this draft. Network Model CEDAR assumes that all the hosts communicate on the same shared Sivakumar, Sinha, Bharghavan [Page 5] INTERNET-DRAFT CEDAR Specification October 1998 logical wireless channel. CEDAR assumes that each transmitter has a fixed transmission range, and that neighborhood is a commutative property (i.e. if A can hear B, then B can hear A). Because of the local nature of transmissions, hidden and exposed stations abound in an ad hoc network. CEDAR assumes the use of a CSMA/CA like algorithm for reliable unicast communication, and for solving the problem of hidden/exposed stations. Essentially, data transmission is preceded by a control packet handoff, and the sequence of packets exchanged in a communication is the following: RTS (from sender to receiver) - CTS (from receiver to sender) - Data (from sender to receiver) - ACK (from receiver to sender). The RTS and CTS packets avoid collisions from the exposed stations and the hidden stations respectively. Local broadcasts are not guaranteed to be reliable (because it is unreasonable to expect a CTS from every receiver before commencing data transmission), and are typically quite unreliable due to the presence of hidden and exposed stations. CEDAR assumes small to medium networks ranging upto to hundreds of hosts. For larger networks, we believe that a clustering algorithm [6] can be used to reduce the cluster size and apply CEDAR hierarchically within each cluster, for a cluster of clusters, etc. CEDAR also assumes that mobility and extended fades are the main causes of link failures and topology changes. We assume that the change in network topology is frequent, but not frequent enough to render any sort of route computation useless. Note that CEDAR only cares about the relative mobility of the hosts, not the absolute mobility of the hosts. In particular, even if all the hosts are moving, the ad hoc network would be considered to be stable so long as the neighborhood of each host does not change. As in most QoS routing algorithms, CEDAR assumes that the MAC/link layer can estimate the available link bandwidth. Because all the hosts in a region share the same channel, each host must share the link bandwidth with the hosts in its second neighborhood [7]. In related work on providing QoS in wireless channels, a mechanism is provided for each host to fairly access a shared channel, and claim at least B/N bandwidth, where B is the effective channel bandwidth and N is the number of hosts locally contending for the bandwidth [8]. This work is currently being extended to ad hoc networks. While details of bandwidth sharing and estimation are beyond the scope of this draft, it is assumed that each host can estimate the available bandwidth of its links using some link- level mechanisms. CEDAR assumes a close coordination between the MAC layer and the routing layer. In particular, it uses the reception of RTS and CTS control messages at the MAC layer in order to improve the behavior Sivakumar, Sinha, Bharghavan [Page 6] INTERNET-DRAFT CEDAR Specification October 1998 of the routing layer, as explained in Section 3. Finally, bandwidth is the QoS parameter of interest in this draft. When an application requests a connection, it specifies the required bandwidth for the connection. The goal of CEDAR is then to find a short stable route that can satisfy the bandwidth requirement of the connection. Graph Terminology The ad hoc network is represented by means of an undirected graph G=(V,E), where V is the set of nodes in the graph (hosts in the network), and E is the set of edges in the graph (links in the network). The i-th open neighborhood, Ni(x) of node x is the set of nodes whose distance from x is not greater than i, except node x itself. The i-th closed neighborhood Ni[x] of node x is N(i) U {x}. A dominating set S (a subset of V) is a set such that every node in V is either in S or is a neighbor of a node in S. A dominating set with minimum cardinality is called a minimum dominating set (MDS). A virtual link [u,v] between two nodes in the dominating set S is a path in G from u to v. The draft uses the term tunnel interchangeably with virtual link. Given an MDS Vc of graph G, define a core of the graph C=(Vc, Ec), where Ec = { [u,v] u in Vc, v in Vc, u in N3(v) } . Thus, the core graph consists of the MDS nodes Vc, and a set of virtual links between every two nodes in Vc that are within a distance 3 of each other in G. Two nodes u and v which have a virtual link [u,v] in the core are said to be "nearby" nodes. For a connected graph G, consider any dominating set S. If the diameter of G is greater than 2, then for each node v in S, there must be at least one other node of S in N3(v) (otherwise there is at least one node in G which is neither in S nor has a neighbor in S). From the definition of the core, if G is connected, then a core C of G must also be connected (via virtual links). 3. CEDAR Architecture and the Core This section focuses on the establishment and maintenance of the core. Briefly, CEDAR extracts the core of the ad hoc network by approximating the minimum dominating set (MDS) of the ad hoc network. The nodes in the MDS comprise the core nodes of the network. Each core node establishes a unicast virtual link (via a tunnel) with nearby core nodes that are a distance of 3 or less away from it in the ad hoc network. This guarantees that the core is connected so Sivakumar, Sinha, Bharghavan [Page 7] INTERNET-DRAFT CEDAR Specification October 1998 long as the network is connected. The core nodes then collect local topology information and information about stable high-bandwidth links far away and perform routing for the nodes in their domain (or immediate neighborhood). Each node that is not in the core chooses a core neighbor as its dominator, i.e. the node which performs route computations on its behalf. The core is merely an infrastructure for facilitating route computation, and is itself independent of the routing algorithm. In particular, it is possible to use any of the well known ad hoc routing algorithms such as DSR [2], LMR [4], TORA [5], DSDV [9], etc. in the core graph. In the following subsections, the motivation for choosing a core- based routing architecture is first described, then a low overhead mechanism to generate and maintain the core of the network is presented, and finally an efficient mechanism to accomplish a 'core broadcast' using local unicast transmissions is described. The core broadcast is used both for propagation of increase/decrease waves, and for the establishment of the core path in the route computation phase. 3a. Rationale for a Core-based Architecture in CEDAR Many contemporary proposals for ad hoc networking require every node in the ad hoc network to perform route computations and topology management [2,6,19,20]. However, CEDAR uses a core-based infrastructure for QoS routing due to two compelling reasons. 1. QoS route computation involves maintaining local and some non-local link-state, and monitoring and reacting to some topology changes. Clearly, it is beneficial to have as few nodes in the network performing state management and route computation as possible. 2. Local broadcasts are highly unreliable in ad hoc networks due to the abundance of hidden and exposed stations. The problem of local broadcasts in ad hoc networks has also been a recent subject of discussion in the MANET working group. Topology information propagation [19,20] and route probes [2,6] are inevitable in order to establish routes and will, of necessity, need to be broadcast if every node performs route computation. On the other hand, if only a core subset of nodes in the ad hoc network perform route computations, it is possible to set up reliable unicast channels between nearby core nodes and accomplish both the topology updates and route probes much more effectively. The issues with having only a core subset of nodes performing Sivakumar, Sinha, Bharghavan [Page 8] INTERNET-DRAFT CEDAR Specification October 1998 route computations are threefold. First, nodes in the ad hoc network that do not perform route computation must have easy access to a nearby core node so that they can quickly request routes to be setup. Second, the establishment of the core must be a purely local computation. In particular, no core node must need to know the topology of the entire core graph. Third, a change in the network topology may cause a recomputation of the core graph. Recomputation of the core graph must only occur in the locality of the topology change, and must not involve a global recomputation of the core graph. On the other hand, the locally recomputed core graph must still only comprise of a small number of core nodes - otherwise the benefit of restricting route computation to a small core graph is lost. Sivakumar, Sinha, Bharghavan [Page 9] INTERNET-DRAFT CEDAR Specification October 1998 o o | | | | o * / \ / \ / \ / \ o----o-----o----o o----*-----*----o | | | | o o o o | | | | | o | o | | | | o----o-----o----o o----*-----*----o | | | | | | | | o-----o o-----o (a) (b) o nodes -- link * core nodes Figure 1 : (a) The example network (b) The example network with core nodes chosen 3b. Generation and Maintenance of the Core in CEDAR Ideally, the core comprises of the nodes in a minimum dominating set Vc of the ad hoc network G=(V,E). While a greedy algorithm can be used to generate the best known approximation for the MDS, CEDAR uses a robust and simple, constant time algorithm which requires only local computations and generates good approximations for the MDS in the average case. Consider a node u, with first open neighborhood N1(u), degree d(u) = |N1(u)|, dominator dom(u), and effective degree d*(u), where d*(u) is the number of nodes in the closed neighborhood N1[u], who have chosen u as their dominator. The core computation algorithm, which is performed periodically, works as follows at node u. 1. u broadcasts a beacon which contains the following information pertaining to the core computation: --------------------------- | u | d*(u) | d(u) | dom(u) | --------------------------- 2. u sets dom(u) <- v, where v is the node in N1[u] with the Sivakumar, Sinha, Bharghavan [Page 10] INTERNET-DRAFT CEDAR Specification October 1998 largest value for , in lexicographic order. Note that u may choose itself as the dominator. 3. u then sends v a unicast message including the following information: ---------------------------------------- | u | {(w, dom(w)) : for all w in N1(u)} | ---------------------------------------- Upon reception of the message, v increments d*(v) if u is not already in v's dominated list. 4. If d*(u) > 0, then u joins the core. Essentially, each node that needs to find a dominator selects the highest degree node with the maximum effective degree in its first closed neighborhood. Ties are broken by node id. When a node u joins the core, it issues a 'piggybacked broadcast' in N3(u). A piggybacked broadcast is accomplished as follows. In its beacon, u transmits a message: ----------------------------------- | u | DOM | 3 | path_traversed=null | ----------------------------------- When node w hears a beacon that contains a message , it piggybacks the message ---------------------------------- | u | DOM | i-1 | path_traversed+w | ---------------------------------- in its own beacon if (i-1 > 0). Thus, the piggybacked broadcast of a core node advertises its presence in its third neighborhood. As mentioned in Section 2, this guarantees that each core node identifies its nearby core nodes, and can set up virtual links to these nodes using the path_traversed field in the broadcast messages. The state that is contained in a core node u is the following: 1. its nearby core nodes (i.e. the core nodes in N3(u)) 2. N*(u), the nodes that it dominates 3. for each node v in N*(u), > Thus each core node has enough local topology information to reach the domain of its nearby nodes and set up virtual links. However, no core node has knowledge of the core graph. In particular, no Sivakumar, Sinha, Bharghavan [Page 11] INTERNET-DRAFT CEDAR Specification October 1998 non-local state needs to be maintained by core nodes for the construction or maintenance of the core. Note from steps 2 and 4 that over a period of time, the core graph prunes itself because nodes have a propensity to choose their core neighbor with the highest effective degree as their dominator. Figure 1 shows an example network and the corresponding core for the network. Maintaining the core in the presence of network dynamics is very simple as the periodic computation of the original core computation algorithm ensures nomination of an appropriate dominator for each node that loses connectivity with its dominator during mobility. 3c. Core Broadcast and its Application to CEDAR As mentioned earlier, broadcasts do not work well in an ad hoc network (because of hidden and exposed stations). Hence, CEDAR uses a unicast based mechanism for achieving a 'core broadcast'. Note that it is reasonable to assume a unicast based mechanism to achieve broadcast in the core, because each core node is expected to have few nearby core nodes. Besides, the core broadcast mechanism ensures that each core node does not transmit a broadcast packet to every nearby core node, as described before. CEDAR uses a close coordination between the medium access layer and the routing layer in order to achieve efficient core broadcast. Recall that a virtual link is a unicast path of length 1, 2, or 3. Recall also, that CSMA/CA protocols use an RTS-CTS-Data-ACK handshake sequence to achieve reliable unicast packet transmission. Our goal is to use the MAC state in order to achieve efficient core broadcast using O(|V|) messages, where |V| is the number of nodes in the network. In order to achieve efficient core broadcast, it is assumed that each node temporarily caches every RTS and CTS packet that it hears on the channel for core broadcast packets only. Each core broadcast message M that is transmitted to a core node i has the unique tag . This tag is put in the RTS and CTS packets of the core broadcast packet, and is cached for a short period of time by any node that receives (or overhears) these packets on the channel. Consider that a core node u has heard a CTS() on the channel. Then, it estimates that its nearby node v has received M, and does not forward M to node v. Now suppose that u and v are a distance 2 apart, and the virtual channel [u,v] passes through a node w. Since w is a neighbor of v, w hears CTS(). Thus, when u sends a RTS() to w, w sends back a NACK to u. If u and v are a distance 3 apart, using the same argument there Sivakumar, Sinha, Bharghavan [Page 12] INTERNET-DRAFT CEDAR Specification October 1998 will be atmost one extra message. Essentially, the idea is to monitor the RTS and CTS packets in the channel in order to discover when the intended receiver of a core broadcast packet has already received the packet from another node, and suppress the duplicate transmission of this packet. o | | * # \ # \ S o----*#####*----o # | # | # | # | # | o----*#####*----o D | | | | o-----o S:source; D:destination; #:tunnels used in the core broadcast Figure 2 : A core broadcast initiated by dom(S) for finding a route to D Note that the core broadcast has the following properties: 1. The core nodes do not explicitly maintain a source-based tree. However, the core broadcast dynamically (and implicitly) establishes a source-based tree (using the MAC-based broadcast suppression), which is typically a breadth-first search tree for the source of the core broadcast. 2. The number of messages is O(|V|) in the worst case, and O(|Vc|) in the average case. In particular, the only case extra messages are transmitted is when two nearby core nodes are a distance 3 apart. 3. Since the trees are not explicitly maintained, different messages may establish different trees. Likewise, changes in the network topology do not require any explicit recomputation of the implicitly generated source tree. However, the coordination of the MAC layer and the routing layer ensures Sivakumar, Sinha, Bharghavan [Page 13] INTERNET-DRAFT CEDAR Specification October 1998 that the core broadcast establishes a tree, and that a core node typically does not receive duplicates for a core broadcast. While the core broadcast in CEDAR has low overhead and adapts easily to topology changes, the RTS and CTS packets corresponding to a core broadcast need to be cached for some time after their reception. Figure 2 illustrates a core broadcast in an example network. Notice that all tunnels need not be used for core broadcast, as the core broadcast dynamically establishes a source-based tree, as mentioned above. Core broadcast finds applicability in two key aspects of CEDAR: discovery of the core path, and propagation of increase/decrease waves. The discovery of the core path is broadcast because the sender may not know the location of the receiver. It initiates a core broadcast to find the location of the receiver, and simultaneously, discover the core path. 4. QoS State Propagation in CEDAR Section 3 described the core routing infrastructure of CEDAR. Since each core node uses only the locally cached state to compute the shortest-widest furthest path along the core path in the route computation phase, the focus is now turned to the nature of state that is stored in each core node. At one extreme is the minimalist approach of only storing local topology information at each core node. This approach results in a poor routing algorithm (i.e. the routing algorithm may fail to compute an admissible route even if such routes exist in the ad hoc network) but has a very low overhead for dynamic networks. At the other extreme is the maximalist approach of storing the entire link state of the ad hoc network at each core node. This approach may compute optimal routes but incurs a high state management overhead for dynamic networks, and potentially computes stale routes based on out-of-date cached state when the network dynamics is high. The problem with having only local state is that core nodes are unable to compute good routes in the absence of link-state information about stable high-bandwidth remote links, while the problem of having global state is that it is useless to maintain the link state corresponding to low-bandwidth and highly dynamic links that are far away because the cached state is likely to be stale anyway. Fundamentally, each core node needs to have the up-to-date state about its local topology, and also the link-state corresponding to relatively stable high-bandwidth links further away. Providing for such a link-state propagation mechanism ensures that CEDAR approaches Sivakumar, Sinha, Bharghavan [Page 14] INTERNET-DRAFT CEDAR Specification October 1998 the minimalist local state algorithm in highly dynamic networks, and approaches the maximalist link-state algorithm in highly stable networks. CEDAR achieves the goal of having stability and bandwidth based link-state propagation using increase and decrease waves, as described in this section. In the rest of this section, the draft first describes the mechanics of the increase and decrease waves, and then answers the three key questions pertaining to these waves: when should a wave be generated, how fast should a wave propagate, and how far should a wave propagate. 4a. Increase and Decrease Waves For every link l=(a,b), the node b is responsible for monitoring the available bandwidth on l and informing a of the same if l is bi-directional. b and a in turn notify their respective dominators for initiating the increase or decrease waves, when the bandwidth changes by some threshold value. These waves are then propagated by the dominators (core nodes) to a subset of core nodes via core broadcasts. Each core node has two queues: the "ito-queue" that contains the pending core broadcast messages for increase waves, and the "dto-queue" that contains the pending core broadcast messages for decrease waves. For each link l about which a core node caches link-state, the core node contains the cached available bandwidth bav(l). Sivakumar, Sinha, Bharghavan [Page 15] INTERNET-DRAFT CEDAR Specification October 1998 The following is the sequence of actions for an increase wave: 1. When a new link l=(a,b) comes up, or when the available bandwidth b(a, b) increases beyond a threshold value, then the two end-points of l inform their dominators for initiating a core broadcast for an increase wave: ito() where ito (increase to) denotes the type of the wave, (a,b) identifies the link, dom(a) denotes the dominator of a, dom(b) denotes the dominator of b, b(a, b) denotes the available bandwidth on the link, and ttl(b) is a 'time-to-live' field that denotes the maximum distance to which this wave can be propagated as an increase wave. The ids of the dominators of the link end-points are required by the routing algorithm. ttl(b) is an increasing function of the available bandwidth, as described in Section 4c. 2. When a core node u receives an ito wave ito(), 1 if u has no state cached for (a,b), 2 bav(a,b) <- b(a,b) 3 if (ttl > 0), then add the following message to the ito-queue: 4 ito() 5 else if u has cached state for (a,b) and (ttl > 0), 6 if (bav(a,b) < b(a,b)) 7 bav(a,b) <- b(a,b) 8 delete any pending ito/dto message for (a,b) from the 9 ito-queue and dto-queue. 10 add the following message to the ito-queue: 11 ito() 12 else if (bav(a,b) > b(a,b)), 13 bav(a,b) <- b(a,b) 14 delete any pending ito/dto message for (a,b) from the 15 ito-queue and dto-queue. 16 add the following message to the dto-queue: 17 dto() 18 else if u has cached state for (a,b) and (ttl = 0), 19 bav(a,b) <- b(a,b) 20 delete any pending ito/dto message for (a,b) from the ito-queue and dto-queue. 21 add the following message to the dto-queue: 22 dto() Sivakumar, Sinha, Bharghavan [Page 16] INTERNET-DRAFT CEDAR Specification October 1998 The ito-queue and the dto-queues are flushed periodically, depending on the speed of propagation of the increase/decrease waves. The following is the sequence of actions for a decrease wave: 1. When a link l=(a,b) goes down, or when the available bandwidth b(a, b) decreases beyond a threshold value, then the two end-points of l inform their dominators for initiating a core broadcast for a decrease wave: dto(), where dto (decrease to) denotes the type of the wave, and the other parameters are as defined before. 2. When a core node u receives a dto wave dto(), 1 if u has no state cached for (a,b) and (b(a,b) = 0), 2 the wave is killed. 3 else if u has no state cached for (a,b) and (b(a,b) > 0), 4 bav(a,b) <- b(a,b) 5 if (ttl > 0), then add the following message to the ito-queue: 6 ito() 7 else if u has cached state for (a,b) and (ttl > 0), 8 if (bav(a,b) < b(a,b)), 9 bav(a,b) <- b(a,b) 10 delete any pending ito/dto message for (a,b) from the 11 ito-queue and dto-queue. 12 add ito() to 13 the ito-queue. 14 else if (bav(a,b) > b(a,b)), 15 bav(a,b) <- b(a,b) 16 delete any pending ito/dto message for (a,b) from the 17 ito-queue and dto-queue. 18 add the following message to the dto-queue. 19 dto() 20 else if u has cached state for (a,b) and (ttl = 0), 21 bav(a,b) <- b(a,b) 22 delete any pending ito/dto message for (a,b) from the 23 ito-queue and dto-queue. 24 add the following message to the dto-queue. 25 dto() There are several key points in the above algorithm. First, the Sivakumar, Sinha, Bharghavan [Page 17] INTERNET-DRAFT CEDAR Specification October 1998 way that the ito-queue and the dto-queue are flushed ensures that the decrease waves propagate much faster than the increase waves and suppress state propagation for unstable links. Second, waves are converted between ito and dto on-the-fly, depending on whether the cached value for the available bandwidth is lesser than the new update (ito wave generated) or not (dto wave generated). Third, after a distance of ttl (which depends on the current available bandwidth of the link), the dto() message ensures that all other core nodes which had state cached for this link now destroy that state. However, the dto() wave does not propagate throughout the network - it is suppressed as soon as it hits the core nodes which do not have link state for (a,b) cached (line 2 in decrease wave propagation). The increase/decrease waves use the efficient core broadcast mechanism for propagation. Figure 3 illustrates a decrease wave cancelling a previously generated increase wave for a link l. ^ | | | increase wave ^ | nullified | | + - | | + - | + - # of hops | + - from | + - l | + - | + - | + - | + - | + - | + - | + - -|----X-----------------X----------------> | increase wave decrease wave | for l generated for l generated time -> Figure 3 : A decrease wave cancelling an increase wave for l Essentially, the above algorithm ensures that the link-state information for stable high-bandwidth links gets propagated throughout the core, while the link-state information for unstable and low-bandwidth links remains local - which is the goal of the CEDAR state propagation algorithm. Sivakumar, Sinha, Bharghavan [Page 18] INTERNET-DRAFT CEDAR Specification October 1998 4b. Issues in link state propagation In this subsection, the three key questions pertaining to the propagation of increase/decrease waves are discussed: when should a wave be generated, how fast should a wave propagate, and how far should a wave propagate. When is a wave generated ? To avoid a large overhead, CEDAR generates waves only when the bandwidth has changed by some threshold value. We suggest the use of a constant threshold when the bandwidth request sizes are comparable to the available bandwidth and a logarithmic scale [10] for the threshold when the typical request sizes are an order of a magnitude less than the available bandwidths. The advantage of the logarithmic update is that it does not wastefully generate increase/decrease waves when the change in link capacity is unlikely to alter the probability of computing admissible routes. Further work is needed to substantiate the above heuristics. How Far does a Increase/Decrease Wave Propagate? The goal is to propagate link bandwidth information to a number of nodes that is proportional to the amount of bandwidth being propagated. The motivation for this approach is the fact that every node that has knowledge about a particular link would potentially contend for the link, and a higher percentage of requests can be satisfied if the contention on a link is proportional to its bandwidth. Hence we suggest that the maximum distance that the link state travels (time to live - ttl) be an increasing function of the available bandwidth of the link. Although the current CEDAR simulation uses a linear function of the available bandwidth for computing the ttl, a fluid model analysis of an ad hoc network suggests that in general, the ttl should be a function of b^(1/k), where k is a small number between 1 and 3. How Fast does a Increase/Decrease Wave Propagate? An increase wave waits for a fixed timeout period (which is a system parameter that should be approximately twice the expected inter-arrival time between the generation of two successive waves for any link in the network) at each node before being forwarded to its neighbors (using the core broadcast). Thus, increase waves propagate slowly. A decrease wave is immediately forwarded to its neighbors (using the core broadcast). Thus decrease waves move much faster and can kill Sivakumar, Sinha, Bharghavan [Page 19] INTERNET-DRAFT CEDAR Specification October 1998 increase waves for unstable links. 5. QoS Routing in CEDAR The previous two sections have described the core infrastructure (i.e. which nodes in the ad hoc network perform route computation and how they communicate among themselves) and the state propagation algorithm (i.e. what state does each core node contain). This section completes the description of CEDAR by specifying how the core nodes use the state information to compute QoS routes. The QoS route computation in CEDAR consists of three key components: (a) discovery of the location of the destination and establishment of the core path to the destination, (b) establishment of a short stable admissible QoS route from the source to the destination using the core path as a directional guideline, and (c) dynamic re- establishment of routes for ongoing connections upon link failures and topology changes in the ad hoc network. 5a. Establishment of the Core Path The establishment of a core path takes place when s requests dom(s) to set up a route to d, and dom(s) does not know the identity of dom(d) or does not have a core path to dom(d). Establishment of a core path consists of the following steps. 1. dom(s) initiates a core broadcast to set up a core path with the following message: . 2. When a core node u receives the core path request message , it appends u to P, and forwards the message to each of its nearby core nodes (according to the core broadcast algorithm) to whose domain there exists atleast one path (from u's domain) satisfying bandwidth b. 3. When dom(t) receives the core path request message , it sends back a source rooted unicast core_path_ack message to dom(s) along the inverse path recorded in P. The response message also contains P, the core path from dom(s) to dom(d). Upon reception of the core_path_ack message from dom(d), dom(s) completes the core path establishment phase and enters the QoS route computation phase. Note that by virtue of the core broadcast algorithm, the core path Sivakumar, Sinha, Bharghavan [Page 20] INTERNET-DRAFT CEDAR Specification October 1998 request traverses an implicitly (and dynamically) established source routed tree from dom(s) which is typically a breadth-first search tree. Thus, the core path is approximately the shortest admissible path in the core graph from dom(s) to dom(d), and hence provides a good directional guideline for the QoS route computation phase. Figure 4 shows an example for a core path. The example assumes that the link marked with 0.5 has an available bandwidth of 0.5 units, whereas all other links have 1 unit of bandwidth available. The route request has a QoS requirement of 1 unit. Sivakumar, Sinha, Bharghavan [Page 21] INTERNET-DRAFT CEDAR Specification October 1998 o | |1 * 1 / \ 1 1 / \ 1 S o----*-----*----o + | + | 1 + | 1 + | 1 + 0.5 | 1 o----*+++++*----o D | | 1 | | 1 o-----o 1 + core path S source D destination Figure 4 : Core path from dom(S) to dom(D) 5b. QoS Route Computation After the core path establishment, dom(s) knows dom(d) and the core path from dom(s) to dom(d). Recall from Section 3 that dom(s) has the local topology - which includes all the nodes in its domain, and for each dominated node u, the bandwidth of each link incident on u, the adjacency list of u and the dominator of each of the neighbors of u. Recall from Section 4 that dom(s) has the information gathered about remote links through increase/decrease waves, and for each such link (u, v), the bandwidth of (u,v), dom(u), and dom(v). dom(s) thus has a partial knowledge of the ad hoc network topology, which consists of the up-to-date local topology, and some possibly out-of-date information about remote stable high-bandwidth links in the network. The following is the sequence of events in QoS route computation. 1. Using the local topology, dom(s) tries to find a path from s to the domain of the furthest possible core node in the core path (say dom(t)) that can provide at least a bandwidth of b (bandwidth of the connection request). The bandwidth that can be provided on a path is the minimum of the individual available link bandwidths that comprise the path. 2. Among all the admissible paths (known using local state) to the domain of the furthest possible core node in the core path, dom(s) picks the shortest-widest path using a two phase Dijkstra's algorithm [11]. The first phase is used to find the Sivakumar, Sinha, Bharghavan [Page 22] INTERNET-DRAFT CEDAR Specification October 1998 available bandwidth B of the widest path. In the subsequent phase, links with available bandwidth less than B are eliminated before computing the shortest path in the resulting graph. 3. Let t be the end point of the chosen path and p(s, t) denote the path. dom(s) sends dom(t) the following message: < s, d, b, P, p(s, t), dom(s), t>, where s, d, and t are the source, destination, and intermediate node in the partially computed path, b is the required bandwidth, P is the core path, and p(s, t) is the partial path. 4. dom(t) then performs the QoS route computation using its local state identical to the computation described above. 5. Eventually, either there is an admissible path to d or the local route computation will fail to produce a path at some core node. The concatenation of the partial paths computed by the core nodes provides an end-to-end path that can satisfy the bandwidth requirement of the connection with high probability. Figure 5 shows how the core path found in Figure 4 is used to find a QoS route satisfying the 1 unit bandwidth request. As mentioned earlier, all links except the one indicated with 0.5, have an available bandwidth of 1 unit. This example also illustrates that the QoS route found in CEDAR can be non- optimal as it uses a core path as the guiding direction (the path along the core has 7 hops whereas there is another feasible path - not along the chosen core path - with 6 hops). The core path is computed in one round trip, and the QoS route computation algorithm also takes one round trip. Thus, the route discovery and computation algorithms together take two round trips if the core path is not cached and one round trip otherwise. Note that while the QoS route is being computed, packets may be sent from s to d using the core path. The core path thus provides a simple backup route while the primary route is being computed. Sivakumar, Sinha, Bharghavan [Page 23] INTERNET-DRAFT CEDAR Specification October 1998 o | | * / \ / \ S o....*-----*----o : | o o : | : o : 0.5 | o----*-----*....o D : : : : o.....o Figure 5 : QoS route from S to D satisfying a bandwidth requirement of 1 unit. 5c. Dynamic QoS Route Recomputation for Ongoing Connections Route recomputations may be required for ongoing connections under two circumstances: the end host moves, and there is some intermediate link failure (possibly caused by the mobility of an intermediate router or by a reduction in available bandwidth on that link such that the connection can no longer be served). End host mobility can be thought of as a special case of link failure, wherein the last link fails. CEDAR has two mechanisms to deal with link failures and reduce the impact of failures on ongoing flows: dynamic recomputation of an admissible route from the point of failure, and notification back to the source for source-initiated route recomputation. These two mechanisms work in concert and enable us to provide seamless mobility. 1. QoS Route Recomputation at the Failure Point: Consider that a link (u, v) fails on the path of an ongoing connection from s to t. The node nearest to the sender, u, then initiates a local route recomputation similar to the algorithm in Section 5b. Once the route is recomputed, u updates the source route in all packets from s to t accordingly. If the link failure happens near the destination, then dynamic route recomputation at the intermediate node works very well because the route recomputation time to the destination is expected to be small, and packets in-flight are re-routed seamlessly. Sivakumar, Sinha, Bharghavan [Page 24] INTERNET-DRAFT CEDAR Specification October 1998 2. QoS Route Recomputation at the Source: Consider that a link (u, v) fails on the path of an ongoing connection from s to t. The node nearest to the sender, u, then notifies s that the link (u, v) has failed. Upon receiving the notification, u stops its packet transmission, initiates a QoS route computation as in Section 5b, and resumes transmission upon the successful re-establishment of an admissible route. If the link failure happens near the source, then source-initiated recomputation is effective, because the source can quickly receive the link-failure notification and temporarily stop transmission. The combination of these two mechanisms is effective in supporting seamless communication inspite of mobility and dynamic topology changes. Basically, CEDAR uses source-initiated recomputation as the long-term solution to handling link failure, while the short- term solution to handle packets in-flight is through the dynamic recomputation of routes from the intermediate nodes. Recomputation at the failure point is not really effective if the failure happens close to the source, but in this case, the number of packets in flight from s to u is small. 6. Performance Results We have evaluated the performance of CEDAR via both implementation and simulation. Our implementation consists of a small ad hoc network consisting of six mobile nodes that use Photonics (Data Technology) 1 Mbps infrared network. We have customized the Linux 2.0.31 kernel to build our ad hoc network environment (written partly in user mode and partly in kernel mode). While the testbed shows proof of concept and has exposed some difficulties in implementing CEDAR, our detailed performance evaluation [12] has been using a simulator that faithfully implements the CEDAR algorithms. While the entire gamut of results obtained from the tests are not presented due to space constraints, the rest of this section briefly summarizes the performance of CEDAR as observed from these tests. For tests in a best-effort environment we assume the optimal performance to be the performance of a global algorithm that does shortest path computation, while in a QoS environment we assume this to be the performance of a global algorithm doing a shortest widest path computation. The metrics used for comparison in these results are: (i) stretch - the ratio of the number of hops in a route computed by CEDAR to the number of hops in a route computed by the global algorithm, (ii) bandwidth - the ratio of bandwidth available on the routes computed by CEDAR to that of the global algorithm, (iii) message complexity, (iv) time complexity and (v) crankbacks - the ratio of the number of rejects to the number of connection requests. Sivakumar, Sinha, Bharghavan [Page 25] INTERNET-DRAFT CEDAR Specification October 1998 In a best-effort environment, CEDAR performs reasonably well before the introduction of ito/dto waves, and progressively converges to a near optimal performance once these waves are introduced. In particular, for dynamic networks we observed a stretch of around 1.2 before the waves were introduced. The stretch came down to 1.1 once the waves were introduced. For stable networks, the stretch observed was 1. Additionally, the message and time complexities of CEDAR were also comparable to the optimal performance [12]. In a QoS environment, CEDAR was compared to the optimal algorithm in terms of the number of hops and the bandwidth available on the computed path. In terms of bandwidth, CEDAR's performance was worse than the optimal performance by an average of 3%. For the number of hops on the computed path, CEDAR in fact performed better in some cases (the global algorithm could pick a longer path with a higher bandwidth). When the number of crank-backs was observed in these tests, CEDAR had 30% more crank-backs than the optimal algorithm before the introduction of waves, while after the introduction of ito/dto waves, the number of crank-backs were the same in both CEDAR and the optimal algorithm. For detailed performance results, please refer to [12]. 7. Conclusions This draft presents CEDAR, a core-Extraction Distributed Ad hoc Routing algorithm for providing QoS in ad hoc network environments. CEDAR has three key components: (a) the establishment and maintenance of a self-organizing routing infrastructure, called the "core", for performing route computations, (b) the propagation of the link-state of stable high-bandwidth links in the core through "increase/decrease" waves, and (c) a QoS route computation algorithm that is executed at the core nodes using only locally available state. While the core provides an efficient and low-overhead infrastructure to perform routing and broadcasts in an ad hoc network, the increase/decrease wave based state propagation mechanism ensures that the core nodes have the important link-state they need for route computation without incurring the high overhead of state maintenance for dynamic links. The QoS routing algorithm is robust and uses only local state for route computation at each core node. CEDAR is a robust and adaptive algorithm that reacts quickly and efficiently to the dynamics of the network while still approximating link-state performance for stable networks. Our simulations show that CEDAR produces good stable admissible routes with a high probability if such routes exist. Furthermore, CEDAR does not require high maintenance overhead even for highly dynamic networks. Ongoing work Sivakumar, Sinha, Bharghavan [Page 26] INTERNET-DRAFT CEDAR Specification October 1998 on CEDAR is focusing on three areas. (a) While it is shown that CEDAR is effective for small to medium size networks, work is being done on a hierarchically clustered version of CEDAR that can provide QoS routing in large ad hoc networks. (b) While this draft has only considered bandwidth as the QoS parameter in this work, current work is extending CEDAR to include delay as a QoS parameter and (c) The heuristics mentioned in Section 4 need more study and are in the process of being refined. 8. References [1] R. Nair, B. Rajagopalan, H. Sandick, and E. Crawley. "A framework for QoS-based routing in the Internet." Internet Draft draft-ietf-qosr-framework-05.txt, May 1998. [2] D. B. Johnson and D. A. Maltz. "Dynamic source routing in ad hoc wireless networks". In Mobile Computing, (ed. T. Imielinski and H. Korth), Kluwer Academic Publishers, 1996. [3] A. Ephremides, J. E. Wieselthier, and D. J. Baker. "A design concept for reliable mobile radio networks with frequency hopping signaling". In Proceedings of the IEEE, pages 56--73, January 1987. [4] M. S. Corson and A. Ephremides. "A highly adaptive distributed routing algorithm for mobile wireless networks". ACM/Baltzer Wireless Networks Journal, 1(1):61--81, February 1995. [5] V. D. Park and M. S. Corson. "A highly adaptive distributed routing algorithm for mobile wireless networks". In Proceedings of 1997 IEEE Conference on Computer Communications, April 1997. [6] R. Sivakumar, B. Das, and V. Bharghavan. "Spine routing in ad hoc networks". ACM/Baltzer Cluster Computing Journal (special issue on Mobile Computing). To appear, 1998. [7] V. Bharghavan, S. Shenker A. Demers, and L. Zhang. "MACAW: A medium access protocol for wireless LANs". In Proceedings of ACM SIGCOMM}, London, England, August 1994. Sivakumar, Sinha, Bharghavan [Page 27] INTERNET-DRAFT CEDAR Specification October 1998 [8] S. Lu, V. Bharghavan, and R. Srikant. "Fair queuing in wireless packet networks". In Proceedings of ACM SIGCOMM '97, Cannes, France, September 1997. [9] C. E. Perkins and P. Bhagwat. "Highly dynamic destination- sequenced distance-vector routing (DSDV) for mobile computers". In Proceedings of ACM SIGCOMM, pages 234--244, London, England, August 1994. [10] B. Awerbuch, Yi Du, B. Khan, and Y. Shavitt. "Routing through networks with topology aggregation". In IEEE Symposium on Computers and Communications, Athens, Greece, June 1998. [11] Q. Ma and P. Steenkiste. "On path selection for traffic with bandwidth guarantees". In Proceedings of Fifth IEEE International Conference on Network Protocols, Atlanta, October 1997. [12] R. Sivakumar, P. Sinha and V. Bharghavan. "CEDAR: a Core- Extraction Distributed Ad hoc Routing algorithm". TIMELY Group Technical Report,http://www.timely.crhc.uiuc.edu/Papers/cedar.ps 9. Author's Addresses Raghupathy Sivakumar 458 C&SRL, Coordinated Science Lab University of Illinois, Urbana-Champaign 1308 W. Main St., Urbana, IL 61801 USA Email: sivakumr@timely.crhc.uiuc.edu Prasun Sinha 458 C&SRL, Coordinated Science Lab University of Illinois, Urbana-Champaign 1308 W. Main St., Urbana, IL 61801 USA Email: prasun@timely.crhc.uiuc.edu Vaduvur Bharghavan 457 C&SRL, Coordinated Science Lab University of Illinois, Urbana-Champaign 1308 W. Main St., Urbana, IL 61801 USA Email: bharghav@timely.crhc.uiuc.edu Sivakumar, Sinha, Bharghavan [Page 28] INTERNET-DRAFT CEDAR Specification October 1998 Sivakumar, Sinha, Bharghavan [Page 29]