INTERNET-DRAFT September 1998 draft-ietf-manet-cedar-spec-00.txt 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 September 1998 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Network Model . . . . . . . . . . . . . . . . . . . . . . . 6 3. CEDAR Architecture and the Core . . . . . . . . . . . . . . 8 3a. Rationale for a Core-based Architecture in CEDAR . . . . . 9 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 . . . . . . . . . . . . 18 5. QoS Routing in CEDAR . . . . . . . . . . . . . . . . . . . 19 5a. Establishment of the Core Path . . . . . . . . . . . . . 19 5b. QoS Route Computation . . . . . . . . . . . . . . . . . . 21 5c. Dynamic QoS Route Recomputation for Ongoing Connections . 22 6. Performance Results . . . . . . . . . . . . . . . . . . . 23 7. Some Implementation related Issues . . . . . . . . . . . . 24 8. Conclusions . . . . . . . . . . . . . . . . . . . . . . . 25 9. References . . . . . . . . . . . . . . . . . . . . . . . . 25 10. Authors' Addresses . . . . . . . . . . . . . . . . . . . . 28 Sivakumar, Sinha, Bharghavan [Page 2] INTERNET-DRAFT CEDAR Specification September 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 to each other. These channels, typically being scarce, 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 [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, 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 minimum. In particular, every change in available bandwidth should Sivakumar, Sinha, Bharghavan [Page 3] INTERNET-DRAFT CEDAR Specification September 1998 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. 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 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 the bandwidth availability information of stable links in the core. The basic idea is that the information about stable high-bandwidth links can be made known to 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 a minimalist local state algorithm in highly dynamic networks while it approaches the maximalist link state algorithm in highly stable Sivakumar, Sinha, Bharghavan [Page 4] INTERNET-DRAFT CEDAR Specification September 1998 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). 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 (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 QoS and non-QoS 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. [5] 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 a cost of higher memory and message requirements. QoS routing algorithms can be mainly classified into two categories: distributed [9,10,11] and centralized [12,13,14] Wang and Crowcroft [9] show that if the total number of independent additive and multiplicative QoS constraints is more than one, then the QoS routing problem is NP complete. Assuming that all routers are using Weighted Fair Queuing scheduling, Ma and Steenkiste [10] show that the relationships between various QoS parameters (bandwidth, delay, delay-jitter and buffer space) can be utilized to find QoS routes in polynomial time. Wang and Sivakumar, Sinha, Bharghavan [Page 5] INTERNET-DRAFT CEDAR Specification September 1998 Crowcroft [9] and Guerin et. al. [11] propose shortest-widest path. A comparison of shortest- widest, widest-shortest, dynamic alternative and the shortest distance path is presented in [10]. Ma and Steenkiste [12] propose a centralized algorithm for finding the fair share of a best effort flow. The fair share of a bandwidth can be used for shortest-widest, widest-shortest or any other algorithm for routing the best effort traffic. Effects of uncertain parameters on QoS routing with end-to-end delay requirements is discussed in [13]. For a wide class of probability distributions, Lorenz and Orda [13] and Guerin and Orda [14] propose efficient exact solutions to {it optimal delay partition problem} (OP) and a pseudo polynomial solution to optimally partitioned most probable path} (OPMP). This work is currently being applied in order to extend the CEDAR approach to support delay as a QoS parameter in ad-hoc network environments. A simulation based study of the relationship between routing performance and the amount of update traffic is reported by Apostolopoulos et. al. [15]. 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 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. Sivakumar, Sinha, Bharghavan [Page 6] INTERNET-DRAFT CEDAR Specification September 1998 CEDAR assumes small to medium networks ranging upto to hundreds of hosts. For larger networks, we believe that a clustering algorithm [16] 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 [17]. 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 [18]. 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 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 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 Sivakumar, Sinha, Bharghavan [Page 7] INTERNET-DRAFT CEDAR Specification September 1998 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 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 [6], TORA [7], DSDV [19], 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. Sivakumar, Sinha, Bharghavan [Page 8] INTERNET-DRAFT CEDAR Specification September 1998 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. 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. While the adverse effects of unreliable broadcasts are typically not considered in most of the related work on ad-hoc routing, it is observed that flooding in ad-hoc networks is highly lossy [21]. 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 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 September 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) U {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 September 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)} | ---------------------------------------- v upon reception of the message 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 September 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. 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 back to u. If u and v are a distance 3 apart, using the same argument there will be atmost one extra message. Essentially, the idea is Sivakumar, Sinha, Bharghavan [Page 12] INTERNET-DRAFT CEDAR Specification September 1998 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 that the core broadcast establishes a tree, and that a core Sivakumar, Sinha, Bharghavan [Page 13] INTERNET-DRAFT CEDAR Specification September 1998 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 the minimalist local state algorithm in highly dynamic networks, and Sivakumar, Sinha, Bharghavan [Page 14] INTERNET-DRAFT CEDAR Specification September 1998 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 a is responsible for monitoring the available bandwidth on l and informing b of the same. a and b, 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 September 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(), if u has no state cached for (a,b), bav(a,b) <- b(a,b) if (ttl > 0), then add the following message to the ito-queue: ito() else if u has cached state for (a,b) and (ttl > 0), if (bav(a,b) < b(a,b)) bav(a,b) <- b(a,b) delete any pending ito/dto message for (a,b) from the ito-queue and dto-queue. add the following message to the ito-queue: ito() else if (bav(a,b) > b(a,b)), bav(a,b) <- b(a,b) delete any pending ito/dto message for (a,b) from the ito-queue and dto-queue. add the following message to the dto-queue. dto() else if u has cached state for (a,b) and (ttl = 0), bav(a,b) <- b(a,b) delete any pending ito/dto message for (a,b) from the ito-queue and dto-queue. add dto() to the dto-queue. The ito-queue and the dto-queues are flushed periodically, depending on the speed of propagation of the increase/decrease waves. Sivakumar, Sinha, Bharghavan [Page 16] INTERNET-DRAFT CEDAR Specification September 1998 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(), if u has no state cached for (a,b) and (b(a,b) = 0), the wave is killed. else if u has no state cached for (a,b) and (b(a,b) > 0), bav(a,b) <- b(a,b) if (ttl > 0), then add the following message to the ito-queue: ito() else if u has cached state for (a,b) and (ttl > 0), if (bav(a,b) < b(a,b)), bav(a,b) <- b(a,b) delete any pending ito/dto message for (a,b) from the ito-queue and dto-queue. add ito() to the ito-queue. else if (bav(a,b) > b(a,b)), bav(a,b) <- b(a,b) delete any pending ito/dto message for (a,b) from the ito-queue and dto-queue. add the following message to the dto-queue. dto() else if u has cached state for (a,b) and (ttl = 0), bav(a,b) <- b(a,b) delete any pending ito/dto message for (a,b) from the ito-queue and dto-queue. add the following message to the dto-queue. dto() There are several key points in the above algorithm. First, the 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 Sivakumar, Sinha, Bharghavan [Page 17] INTERNET-DRAFT CEDAR Specification September 1998 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 (point 2(a) in decrease wave propagation). The increase/decrease waves use the efficient core broadcast mechanism for propagation. 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. The following subsections now answers the three key questions pertaining to the propagation of increase/decrease waves: when should a wave be generated, how fast should a wave propagate, and how far should a wave propagate. 4b. Issues in link state propagation In this subsection the three key questions pertaining to the propagation of increase/decrease waves: when should a wave be generated, how fast should a wave propagate, and how far should a wave propagate are discussed and some solutions suggested. When is a wave generated ? To avoid a large overhead, CEDAR generates waves only when the bandwidth has changed by some threshold. We suggest the use of a constant threshold when the bandwidth request sizes are comparable to the available bandwidth and a logarithmic scale [22] 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. 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 Sivakumar, Sinha, Bharghavan [Page 18] INTERNET-DRAFT CEDAR Specification September 1998 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, fluid model analysis of an ad-hoc network suggests that in general, the ttl should be a function of b^(i/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 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. Sivakumar, Sinha, Bharghavan [Page 19] INTERNET-DRAFT CEDAR Specification September 1998 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 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 3 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. o | |1 * 1 / \ 1 1 / \ 1 S o----*-----*----o + | + | 1 + | 1 + | + 0.5 | 1 o----*+++++*----o D | | 1 | 1 | 1 o-----o Sivakumar, Sinha, Bharghavan [Page 20] INTERNET-DRAFT CEDAR Specification September 1998 + core path S source D destination Figure 3 : 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 [23]. The first phase is used to find the 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 Sivakumar, Sinha, Bharghavan [Page 21] INTERNET-DRAFT CEDAR Specification September 1998 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 4 shows how the core path found in Figure 3 is used to find a QoS route satisfying the 1 unit bandwidth request. As indicated earlier all links except the one indicated with 0.5, have 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 a guiding direction. 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. o | | * / \ / \ S o....*-----*---- D : | o o : | : o : 0.5 | o----*-----*....o D : : : : o.....o Figure 4 : 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). End host mobility can be thought of as a Sivakumar, Sinha, Bharghavan [Page 22] INTERNET-DRAFT CEDAR Specification September 1998 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. 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 Sivakumar, Sinha, Bharghavan [Page 23] INTERNET-DRAFT CEDAR Specification September 1998 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 [24] has been using a simulator that faithfully implements the CEDAR algorithms. While the entire gamut of results obtained from the tests are beyond the scope of this draft, the rest of this section summarizes the performance of CEDAR as observed from these tests. In a best-effort environment, CEDAR performs reasonably well before the introduction of the ito/dto waves, but converges to a near optimal performance once these waves are introduced. In particular, we observed a stretch of around 20% before the waves were introduced. The stretch came down to 10% once the waves were introduced. Besides the stretch, the message and time complexities of CEDAR were also comparable to the optimal performance [24]. In a QoS environment, CEDAR was compared to an optimal algorithm (which is assumed to have global knowledge) in terms of the number of hops and the bandwidth available on the computed path. For the bandwidth available, CEDAR performed worse than the optimal algorithm only by a marginal amount of 3% of the aggregate bandwidth. For the number of hops on the computed path, CEDAR in fact performed better in some cases because of the limited knowledge (an optimal solution would pick a longer path because of higher bandwidth). When the number of crank-backs was observed in these tests, CEDAR before the introduction of waves had 30% more crank-backs than the optimal algorithm while after the introduction of ito/dto waves, the number of crank-backs were the same in both CEDAR and the optimal algorithm. 7. Some Implementation related Issues For the purpose of QoS routing, the application needs to request a QoS route, before it can start using it. Transport layer protocols should include a call to set-up and a call to tear-down a QoS route. Along with destination address, the set-up call needs to specify the desired QoS. CEDAR currently supports only bandwidth as the QoS parameter, hence the minimum desired bandwidth is passed as an argument to the route set-up call. Routing in traditional networks is based on next hop, where every router keeps track of the next router for all destinations. In the realm of QoS routing, however, the next hop might be different for different QoS requirements even for the same pair of end hosts. Either of the following two methods can be used for supporting QoS routing: Sivakumar, Sinha, Bharghavan [Page 24] INTERNET-DRAFT CEDAR Specification September 1998 1. The sender can do source routing once the QoS route has been discovered. 2. Routers can decide on the next hop based on the flow-id, where a possible flow-id could be Currently a user level implementation of CEDAR is under progress at the TIMELY group at University of Illinois, Urbana-Champaign. 8. 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 the core of the network for performing the route computations, (b) propagation and use of bandwidth and stability information of links in the ad-hoc network, and (c) the QoS route computation algorithm. 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 effectively 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 on CEDAR is focusing on two 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 support delay also as a QoS parameter. 9. 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. Sivakumar, Sinha, Bharghavan [Page 25] INTERNET-DRAFT CEDAR Specification September 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] R. Dube, C. D. Rais, K.-Y. Wang, and S. K. Tripathi. "Signal stability based adaptive routing (SSA) for ad-hoc mobile networks". Technical Report UMCP-CSD:CS-TR-3646, Dept. of Computer Science, Univ. of Maryland, College Park, September 1996. [4] C.-K. Toh. "A novel distributed routing protocol to support ad-hoc mobile computing". In Proceedings of 15th IEEE Annual International Phoenix Conference on Computers and Communications, pages 480--486, 1996. [5] 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. [6] 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. [7] 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. [8] S. Corson, J. Macker, and S. Batsell. "Architectural considerations for mobile mesh networking", May 1996. [9] Z. Wang and J. Crowcroft. "QoS routing for supporting resource reservation". IEEE Journal on Selected Areas in Communications, 14(7):1228--1234, September 1996. [10] Q. Ma and P. Steenkiste. "Quality-of-service routing for traffic with performance guarantees". In Proceedings of IFIP Fifth International Workshop on Quality of Service, pages 115- -126, New York, May 1997. Sivakumar, Sinha, Bharghavan [Page 26] INTERNET-DRAFT CEDAR Specification September 1998 [11] R. A. Guerin, A. Orda, and D. Williams. "QoS routing mechanisms and OSPF extensions". Internet Draft, draft-guerin- qos-routing-ospf-00.txt, 1996. [12] Q. Ma, P. Steenkiste, and H. Zhang. "Routing high-bandwidth traffic in max-min fair share networks". In Proceedings of ACM SIGCOMM, pages 206--217, Stanford, California, August 1996. [13] D. H. Lorenz and A. Orda. "QoS routing in networks with uncertain parameters". In Proceedings of IEEE Conference on Computer Communications (INFOCOM), San Francisco, California, April 1998. [14] R. A. Guerin and A. Orda. "QoS-based routing in networks with inaccurate information: Theory and algorithms". In Proceedings of IEEE Conference on Computer Communications (INFOCOM), Kobe, Japan, April 1997. [15] G. Apostolopoulos, R. Guerin, S. Kamat, and S. K. Tripathi. "Quality of service routing: A performance perspective". In Proceedings of ACM SIGCOMM, Vancouver, Canada, September 1998. [16] 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. [17] 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. [18] S. Lu, V. Bharghavan, and R. Srikant. "Fair queuing in wireless packet networks". In Proceedings of ACM SIGCOMM '97, Cannes, France, September 1997. [19] 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. [20] S. Murthy and J. J. Garcia-Luna-Aceves. "A routing protocol Sivakumar, Sinha, Bharghavan [Page 27] INTERNET-DRAFT CEDAR Specification September 1998 for packet radio networks". In Proceedings of ACM SIGCOMM '97, Cannes, France, September 1997. [21] V. Bharghavan. "Performance of multiple access protocols in wireless packet networks". In International Performance and Dependability Symposium, Durham, North Carolina, September 1998. [22] 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. [23] 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. [24] R. Sivakumar, P. Sinha and V. Bharghavan. "CEDAR: a Core- Extraction Distributed Ad hoc Routing algorithm". submitted to IEEE Journal on Selected Areas in Communications, special issue on Wireless ad-hoc Networks, 1998. 10. 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 Sivakumar, Sinha, Bharghavan [Page 28] INTERNET-DRAFT CEDAR Specification September 1998 1308 W. Main St., Urbana, IL 61801 USA Email: bharghav@timely.crhc.uiuc.edu Sivakumar, Sinha, Bharghavan [Page 29]