idnits 2.17.1 draft-ietf-manet-cedar-spec-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-19) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 28 longer pages, the longest (page 2) being 60 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 29 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 8 instances of too long lines in the document, the longest one being 4 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 31 has weird spacing: '... This draft...' == Line 33 has weird spacing: '...s three key ...' == Line 34 has weird spacing: '...tenance of a...' == Line 35 has weird spacing: '...", for perf...' == Line 36 has weird spacing: '...tate of stabl...' == (24 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 1998) is 9318 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '19' is mentioned on line 336, but not defined == Missing Reference: '20' is mentioned on line 336, but not defined ** Downref: Normative reference to an Informational draft: draft-ietf-qosr-framework (ref. '1') -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' Summary: 11 errors (**), 0 flaws (~~), 11 warnings (==), 14 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT October 1998 3 draft-ietf-manet-cedar-spec-00.txt 4 Expires in six months 6 Core Extraction Distributed Ad hoc Routing (CEDAR) Specification 8 Raghupathy Sivakumar Prasun Sinha Vaduvur Bharghavan 9 University of Illinois, Urbana-Champaign 11 Status of this Memo 13 This document is an Internet-Draft. Internet-Drafts are working 14 documents of the Internet Engineering Task Force (IETF), its areas, 15 and its working groups. Note that other groups may also distribute 16 working documents as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six months 19 and may be updated, replaced, or obsoleted by other documents at any 20 time. It is inappropriate to use Internet- Drafts as reference 21 material or to cite them other than as "work in progress." 23 To view the entire list of current Internet-Drafts, please check the 24 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 25 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern 26 Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific 27 Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 29 Abstract 31 This draft presents CEDAR, a Core-Extraction Distributed Ad 32 hoc Routing algorithm for QoS routing in ad hoc network environments. 33 CEDAR has three key components: (a) the establishment and 34 maintenance of a self-organizing routing infrastructure, called 35 the "core", for performing route computations, (b) the 36 propagation of the link-state of stable high-bandwidth links in the 37 core through "increase/decrease" waves, and (c) a QoS route 38 computation algorithm that is executed at the core nodes using only 39 locally available state. 41 Table of Contents 43 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 44 2. Network Model . . . . . . . . . . . . . . . . . . . . . . . 5 45 3. CEDAR Architecture and the Core . . . . . . . . . . . . . . 7 46 3a. Rationale for a Core-based Architecture in CEDAR . . . . . 8 47 3b. Generation and Maintenance of the Core in CEDAR . . . . . 10 48 3c. Core Broadcast and its Application to CEDAR . . . . . . . 12 49 4. QoS State Propagation in CEDAR . . . . . . . . . . . . . . 14 50 4a. Increase and Decrease Waves . . . . . . . . . . . . . . . 15 51 4b. Issues in link state propagation . . . . . . . . . . . . 19 52 5. QoS Routing in CEDAR . . . . . . . . . . . . . . . . . . . 20 53 5a. Establishment of the Core Path . . . . . . . . . . . . . 20 54 5b. QoS Route Computation . . . . . . . . . . . . . . . . . . 22 55 5c. Dynamic QoS Route Recomputation for Ongoing Connections . 24 56 6. Performance Results . . . . . . . . . . . . . . . . . . . 25 57 7. Conclusions . . . . . . . . . . . . . . . . . . . . . . . 26 58 8. References . . . . . . . . . . . . . . . . . . . . . . . . 27 59 9 . Authors' Addresses . . . . . . . . . . . . . . . . . . . . 28 61 1. Introduction 63 An ad hoc network is a dynamic multi-hop wireless network that is 64 established by a group of mobile hosts on a shared wireless 65 channel by virtue of their proximity t[o each other. These 66 channels, typically being scarce and dynamic, make it difficult to 67 perform efficient resource utilization or to execute critical 68 applications. Hence, QoS routing, as opposed to non-QoS routing, is 69 desirable in such environments. This draft focuses on a restricted 70 QoS Routing problem: the satisfaction of minimum bandwidth 71 requirements. Of course, since the network is highly dynamic, and 72 transmissions are susceptible to fades, interference, and collisions 73 from hidden/exposed stations, CEDAR cannot provide bandwidth 74 guarantees for the computed routes. Rather, its goal is to provide 75 routes that are highly likely to satisfy the bandwidth requirement of 76 a route, so long as such routes exist [1]. 78 Given the nature of the network and the requirements of the 79 applications, the following are the key goals of CEDAR. 81 (a) Route computation must be distributed because centralized 82 routing in a dynamic network is impossible even for fairly small 83 networks. (b) Route computation should not involve the maintenance of 84 global state, or even significant amounts of volatile non-local 85 state. In particular, link state routing is not feasible for highly 86 dynamic networks because of the significant state propagation 87 overhead when the network topology changes. (c) As few nodes as 88 possible must be involved in state propagation and route computation 89 (without becoming single points of failure), since this involves 90 monitoring and updating at least some state in the network. On the 91 other hand, every host must have quick access to routes on-demand. 92 (d) Each node must only care about the routes corresponding to its 93 destination, and must not be involved in frequent topology updates 94 for parts of the network to which it has no traffic. (e) Stale routes 95 must be either avoided, or detected and eliminated quickly. (f) 96 Broadcasts must be avoided as far as possible because broadcasts are 97 highly unreliable in ad hoc networks. (g) If the topology stabilizes, 98 then routes must converge to the optimal routes, and (h) It is 99 desirable to have a backup route when the primary route has become 100 stale and is being recomputed. 102 QoS routing for ad hoc networks is relatively unchartered territory. 103 In addition to the above, we have the following goals for QoS routing 104 in ad hoc networks. (a) Applications provide a minimum bandwidth 105 requirement for a connection, and the routing algorithm must 106 efficiently compute a route that can satisfy the bandwidth 107 requirement with high probability. (b) The amount of state 108 propagation and topology update information must be kept to a 109 minimum. In particular, every change in available bandwidth should 110 not result in updated state propagation. (c) Dynamic links (either 111 unstable or low bandwidth links) must not cause state propagation 112 throughout the network. Only stable high bandwidth link information 113 must be propagated throughout the network, and (d) The QoS route 114 computation algorithm should be simple and robust. Robustness, rather 115 than optimality, is the key requirement. 117 In order to achieve the above goals, this draft proposes the Core- 118 Extraction Distributed Ad hoc Routing (CEDAR) algorithm for QoS 119 routing in ad hoc networks. Briefly, CEDAR dynamically establishes a 120 "core" of the network, and then incrementally propagates link state 121 of stable high bandwidth links to the nodes of the core. Route 122 computation is on-demand, and is performed by core hosts using local 123 state only. CEDAR is proposed as a QoS routing algorithm for small 124 to medium size ad hoc networks consisting of tens to hundreds of 125 nodes. CEDAR does not compute optimal routes because of the 126 minimalist approach to state management, but the trade-off of 127 robustness and adaptation for optimality is believed to be well 128 justified in ad hoc networks. The following is a brief description of 129 the three key components of CEDAR. 131 1. Establishment and Maintenance of a core using Local Core 132 Extraction 134 CEDAR does core extraction in order to extract a subset of nodes 135 in the network that would be the only ones that perform state 136 management and route computation. The core extraction is done 137 dynamically by approximating a minimum dominating set of the ad 138 hoc network using only local computation and local state. Each 139 host in the core then establishes a virtual link (via a tunnel) to 140 nearby core hosts (within the 3rd neighborhood in the ad hoc 141 network). Each core host maintains the local topology of the hosts 142 in its domain, and also performs route computation on behalf of 143 these hosts. The core computation and core management upon change 144 in the network topology are purely local computations to enable 145 the core to adapt efficiently to the dynamics of the network. 147 2. Link State Propagation using Increase/Decrease waves 149 While it is possible to execute ad hoc routing algorithms using 150 only local topology information at the core nodes, QoS routing in 151 CEDAR is achieved by propagating, in the core, the bandwidth 152 availability information of stable links. The basic idea is that 153 the information about stable high-bandwidth links can be made 154 known to core nodes far away in the network, while information 155 about dynamic links or low bandwidth links should remain local. By 156 means of this link state propagation mechanism, CEDAR approximates 157 a minimalist local state algorithm in highly dynamic networks 158 while it approaches the maximalist link state algorithm in highly 159 stable networks. The propagation of link-state is achieved through 160 slow-moving 'increase' waves (which denote increase of bandwidth) 161 and fast-moving 'decrease' waves (which denote decrease of 162 bandwidth), which traverse the core. The key questions to answer 163 in link state propagation are: when should an increase/decrease 164 wave be initiated, how far should a wave propagate, and how fast 165 should a wave propagate. 167 3. Route Computation 169 Route computation first establishes a core path from the domain of 170 the source to the domain of the destination. This initial phase 171 involves probing on the core, and the resultant core path is 172 cached for future use. The core path provides the directionality 173 of the route from the source to the destination. Using this 174 directional information, CEDAR iteratively tries to find a partial 175 route from the source to the domain of the furthest possible node 176 in the core path (which then becomes the source for the next 177 iteration) which can satisfy the requested bandwidth, using only 178 local information. Effectively, the computed route is a 179 concatenation of the shortest-widest-furthest (the least hop path 180 among the maximum bandwidth paths) paths found locally using the 181 core path as the guideline. 183 Several algorithms have been proposed for routing in ad hoc networks. 184 The ad hoc routing algorithms proposed in [2,3,4] provide a single 185 route in response to a route query from a source. Previous work on 186 tactical packet radio networks had led to many of the fundamental 187 results in ad hoc networks. [3] has proposed an architecture similar 188 to the "core" called the linked clusterhead architecture but it uses 189 gateways for communication between clusterheads and does not attempt 190 to minimize the size of the core infrastructure. The multipath 191 routing algorithms proposed in [6,7,8] are more robust than the 192 single route on demand algorithms, at the cost of higher memory and 193 message requirements. 195 2. Network Model 197 This section describes the network model and the terminology used in 198 this draft. 200 Network Model 202 CEDAR assumes that all the hosts communicate on the same shared 203 logical wireless channel. CEDAR assumes that each transmitter has 204 a fixed transmission range, and that neighborhood is a commutative 205 property (i.e. if A can hear B, then B can hear A). Because of the 206 local nature of transmissions, hidden and exposed stations abound 207 in an ad hoc network. CEDAR assumes the use of a CSMA/CA like 208 algorithm for reliable unicast communication, and for solving the 209 problem of hidden/exposed stations. Essentially, data transmission 210 is preceded by a control packet handoff, and the sequence of 211 packets exchanged in a communication is the following: RTS (from 212 sender to receiver) - CTS (from receiver to sender) - Data (from 213 sender to receiver) - ACK (from receiver to sender). The RTS and 214 CTS packets avoid collisions from the exposed stations and the 215 hidden stations respectively. Local broadcasts are not guaranteed 216 to be reliable (because it is unreasonable to expect a CTS from 217 every receiver before commencing data transmission), and are 218 typically quite unreliable due to the presence of hidden and 219 exposed stations. 221 CEDAR assumes small to medium networks ranging upto to hundreds of 222 hosts. For larger networks, we believe that a clustering algorithm 223 [6] can be used to reduce the cluster size and apply CEDAR 224 hierarchically within each cluster, for a cluster of clusters, 225 etc. CEDAR also assumes that mobility and extended fades are the 226 main causes of link failures and topology changes. We assume that 227 the change in network topology is frequent, but not frequent 228 enough to render any sort of route computation useless. Note that 229 CEDAR only cares about the relative mobility of the hosts, not the 230 absolute mobility of the hosts. In particular, even if all the 231 hosts are moving, the ad hoc network would be considered to be 232 stable so long as the neighborhood of each host does not change. 234 As in most QoS routing algorithms, CEDAR assumes that the MAC/link 235 layer can estimate the available link bandwidth. Because all the 236 hosts in a region share the same channel, each host must share the 237 link bandwidth with the hosts in its second neighborhood [7]. In 238 related work on providing QoS in wireless channels, a mechanism is 239 provided for each host to fairly access a shared channel, and 240 claim at least B/N bandwidth, where B is the effective channel 241 bandwidth and N is the number of hosts locally contending for the 242 bandwidth [8]. This work is currently being extended to ad hoc 243 networks. While details of bandwidth sharing and estimation are 244 beyond the scope of this draft, it is assumed that each host can 245 estimate the available bandwidth of its links using some link- 246 level mechanisms. 248 CEDAR assumes a close coordination between the MAC layer and the 249 routing layer. In particular, it uses the reception of RTS and CTS 250 control messages at the MAC layer in order to improve the behavior 251 of the routing layer, as explained in Section 3. 253 Finally, bandwidth is the QoS parameter of interest in this draft. 254 When an application requests a connection, it specifies the 255 required bandwidth for the connection. The goal of CEDAR is then 256 to find a short stable route that can satisfy the bandwidth 257 requirement of the connection. 259 Graph Terminology 261 The ad hoc network is represented by means of an undirected graph 262 G=(V,E), where V is the set of nodes in the graph (hosts in the 263 network), and E is the set of edges in the graph (links in the 264 network). The i-th open neighborhood, Ni(x) of node x is the set 265 of nodes whose distance from x is not greater than i, except node 266 x itself. The i-th closed neighborhood Ni[x] of node x is N(i) U 267 {x}. 269 A dominating set S (a subset of V) is a set such that every node 270 in V is either in S or is a neighbor of a node in S. A dominating 271 set with minimum cardinality is called a minimum dominating set 272 (MDS). A virtual link [u,v] between two nodes in the dominating 273 set S is a path in G from u to v. The draft uses the term tunnel 274 interchangeably with virtual link. 276 Given an MDS Vc of graph G, define a core of the graph C=(Vc, Ec), 277 where Ec = { [u,v] u in Vc, v in Vc, u in N3(v) } . Thus, the core 278 graph consists of the MDS nodes Vc, and a set of virtual links 279 between every two nodes in Vc that are within a distance 3 of each 280 other in G. Two nodes u and v which have a virtual link [u,v] in 281 the core are said to be "nearby" nodes. 283 For a connected graph G, consider any dominating set S. If the 284 diameter of G is greater than 2, then for each node v in S, there 285 must be at least one other node of S in N3(v) (otherwise there is 286 at least one node in G which is neither in S nor has a neighbor in 287 S). From the definition of the core, if G is connected, then a 288 core C of G must also be connected (via virtual links). 290 3. CEDAR Architecture and the Core 292 This section focuses on the establishment and maintenance of the 293 core. Briefly, CEDAR extracts the core of the ad hoc network by 294 approximating the minimum dominating set (MDS) of the ad hoc network. 295 The nodes in the MDS comprise the core nodes of the network. Each 296 core node establishes a unicast virtual link (via a tunnel) with 297 nearby core nodes that are a distance of 3 or less away from it in 298 the ad hoc network. This guarantees that the core is connected so 299 long as the network is connected. The core nodes then collect local 300 topology information and information about stable high-bandwidth 301 links far away and perform routing for the nodes in their domain (or 302 immediate neighborhood). Each node that is not in the core chooses a 303 core neighbor as its dominator, i.e. the node which performs route 304 computations on its behalf. The core is merely an infrastructure for 305 facilitating route computation, and is itself independent of the 306 routing algorithm. In particular, it is possible to use any of the 307 well known ad hoc routing algorithms such as DSR [2], LMR [4], TORA 308 [5], DSDV [9], etc. in the core graph. 310 In the following subsections, the motivation for choosing a core- 311 based routing architecture is first described, then a low overhead 312 mechanism to generate and maintain the core of the network is 313 presented, and finally an efficient mechanism to accomplish a 'core 314 broadcast' using local unicast transmissions is described. The core 315 broadcast is used both for propagation of increase/decrease waves, 316 and for the establishment of the core path in the route computation 317 phase. 319 3a. Rationale for a Core-based Architecture in CEDAR 321 Many contemporary proposals for ad hoc networking require every 322 node in the ad hoc network to perform route computations and 323 topology management [2,6,19,20]. However, CEDAR uses a core-based 324 infrastructure for QoS routing due to two compelling reasons. 326 1. QoS route computation involves maintaining local and some 327 non-local link-state, and monitoring and reacting to some 328 topology changes. Clearly, it is beneficial to have as few 329 nodes in the network performing state management and route 330 computation as possible. 332 2. Local broadcasts are highly unreliable in ad hoc networks 333 due to the abundance of hidden and exposed stations. The 334 problem of local broadcasts in ad hoc networks has also been a 335 recent subject of discussion in the MANET working group. 336 Topology information propagation [19,20] and route probes [2,6] 337 are inevitable in order to establish routes and will, of 338 necessity, need to be broadcast if every node performs route 339 computation. On the other hand, if only a core subset of nodes 340 in the ad hoc network perform route computations, it is 341 possible to set up reliable unicast channels between nearby 342 core nodes and accomplish both the topology updates and route 343 probes much more effectively. 345 The issues with having only a core subset of nodes performing 346 route computations are threefold. First, nodes in the ad hoc 347 network that do not perform route computation must have easy 348 access to a nearby core node so that they can quickly request 349 routes to be setup. Second, the establishment of the core must be 350 a purely local computation. In particular, no core node must need 351 to know the topology of the entire core graph. Third, a change in 352 the network topology may cause a recomputation of the core graph. 353 Recomputation of the core graph must only occur in the locality of 354 the topology change, and must not involve a global recomputation 355 of the core graph. On the other hand, the locally recomputed core 356 graph must still only comprise of a small number of core nodes - 357 otherwise the benefit of restricting route computation to a small 358 core graph is lost. 360 o o 361 | | 362 | | 363 o * 364 / \ / \ 365 / \ / \ 366 o----o-----o----o o----*-----*----o 367 | | | | 368 o o o o 369 | | | | 370 | o | o 371 | | | | 372 o----o-----o----o o----*-----*----o 373 | | | | 374 | | | | 375 o-----o o-----o 377 (a) (b) 379 o nodes -- link 380 * core nodes 382 Figure 1 : (a) The example network (b) The example network with 383 core nodes chosen 385 3b. Generation and Maintenance of the Core in CEDAR 387 Ideally, the core comprises of the nodes in a minimum dominating 388 set Vc of the ad hoc network G=(V,E). While a greedy algorithm 389 can be used to generate the best known approximation for the MDS, 390 CEDAR uses a robust and simple, constant time algorithm which 391 requires only local computations and generates good approximations 392 for the MDS in the average case. 394 Consider a node u, with first open neighborhood N1(u), degree d(u) 395 = |N1(u)|, dominator dom(u), and effective degree d*(u), where 396 d*(u) is the number of nodes in the closed neighborhood N1[u], who 397 have chosen u as their dominator. The core computation algorithm, 398 which is performed periodically, works as follows at node u. 400 1. u broadcasts a beacon which contains the following 401 information pertaining to the core computation: 402 --------------------------- 403 | u | d*(u) | d(u) | dom(u) | 404 --------------------------- 406 2. u sets dom(u) <- v, where v is the node in N1[u] with the 407 largest value for , in lexicographic order. Note 408 that u may choose itself as the dominator. 410 3. u then sends v a unicast message including the following 411 information: 412 ---------------------------------------- 413 | u | {(w, dom(w)) : for all w in N1(u)} | 414 ---------------------------------------- 416 Upon reception of the message, v increments d*(v) if u is not 417 already in v's dominated list. 419 4. If d*(u) > 0, then u joins the core. 421 Essentially, each node that needs to find a dominator selects the 422 highest degree node with the maximum effective degree in its first 423 closed neighborhood. Ties are broken by node id. 425 When a node u joins the core, it issues a 'piggybacked broadcast' 426 in N3(u). A piggybacked broadcast is accomplished as follows. In 427 its beacon, u transmits a message: 429 ----------------------------------- 430 | u | DOM | 3 | path_traversed=null | 431 ----------------------------------- 433 When node w hears a beacon that contains a message 434 , it piggybacks the message 436 ---------------------------------- 437 | u | DOM | i-1 | path_traversed+w | 438 ---------------------------------- 440 in its own beacon if (i-1 > 0). Thus, the piggybacked broadcast of 441 a core node advertises its presence in its third neighborhood. As 442 mentioned in Section 2, this guarantees that each core node 443 identifies its nearby core nodes, and can set up virtual links to 444 these nodes using the path_traversed field in the broadcast 445 messages. The state that is contained in a core node u is the 446 following: 448 1. its nearby core nodes (i.e. the core nodes in N3(u)) 449 2. N*(u), the nodes that it dominates 450 3. for each node v in N*(u), > 452 Thus each core node has enough local topology information to reach 453 the domain of its nearby nodes and set up virtual links. However, 454 no core node has knowledge of the core graph. In particular, no 455 non-local state needs to be maintained by core nodes for the 456 construction or maintenance of the core. Note from steps 2 and 4 457 that over a period of time, the core graph prunes itself because 458 nodes have a propensity to choose their core neighbor with the 459 highest effective degree as their dominator. Figure 1 shows an 460 example network and the corresponding core for the network. 462 Maintaining the core in the presence of network dynamics is very 463 simple as the periodic computation of the original core 464 computation algorithm ensures nomination of an appropriate 465 dominator for each node that loses connectivity with its dominator 466 during mobility. 468 3c. Core Broadcast and its Application to CEDAR 470 As mentioned earlier, broadcasts do not work well in an ad hoc 471 network (because of hidden and exposed stations). Hence, CEDAR 472 uses a unicast based mechanism for achieving a 'core broadcast'. 473 Note that it is reasonable to assume a unicast based mechanism to 474 achieve broadcast in the core, because each core node is expected 475 to have few nearby core nodes. Besides, the core broadcast 476 mechanism ensures that each core node does not transmit a 477 broadcast packet to every nearby core node, as described before. 478 CEDAR uses a close coordination between the medium access layer 479 and the routing layer in order to achieve efficient core 480 broadcast. 482 Recall that a virtual link is a unicast path of length 1, 2, or 3. 483 Recall also, that CSMA/CA protocols use an RTS-CTS-Data-ACK 484 handshake sequence to achieve reliable unicast packet 485 transmission. Our goal is to use the MAC state in order to 486 achieve efficient core broadcast using O(|V|) messages, where |V| 487 is the number of nodes in the network. 489 In order to achieve efficient core broadcast, it is assumed that 490 each node temporarily caches every RTS and CTS packet that it 491 hears on the channel for core broadcast packets only. Each core 492 broadcast message M that is transmitted to a core node i has the 493 unique tag . This tag is put in the RTS and CTS packets of 494 the core broadcast packet, and is cached for a short period of 495 time by any node that receives (or overhears) these packets on the 496 channel. Consider that a core node u has heard a CTS() on 497 the channel. Then, it estimates that its nearby node v has 498 received M, and does not forward M to node v. Now suppose that u 499 and v are a distance 2 apart, and the virtual channel [u,v] passes 500 through a node w. Since w is a neighbor of v, w hears CTS(). 501 Thus, when u sends a RTS() to w, w sends back a NACK to u. 502 If u and v are a distance 3 apart, using the same argument there 503 will be atmost one extra message. Essentially, the idea is to 504 monitor the RTS and CTS packets in the channel in order to 505 discover when the intended receiver of a core broadcast packet has 506 already received the packet from another node, and suppress the 507 duplicate transmission of this packet. 509 o 510 | 511 | 512 * 513 # \ 514 # \ 515 S o----*#####*----o 516 # | 517 # | 518 # | 519 # | 520 # | 521 o----*#####*----o D 522 | | 523 | | 524 o-----o 526 S:source; D:destination; #:tunnels used in the core broadcast 528 Figure 2 : A core broadcast initiated by dom(S) for finding a 529 route to D 531 Note that the core broadcast has the following properties: 533 1. The core nodes do not explicitly maintain a source-based 534 tree. However, the core broadcast dynamically (and implicitly) 535 establishes a source-based tree (using the MAC-based broadcast 536 suppression), which is typically a breadth-first search tree 537 for the source of the core broadcast. 539 2. The number of messages is O(|V|) in the worst case, and 540 O(|Vc|) in the average case. In particular, the only case 541 extra messages are transmitted is when two nearby core nodes 542 are a distance 3 apart. 544 3. Since the trees are not explicitly maintained, different 545 messages may establish different trees. Likewise, changes in 546 the network topology do not require any explicit recomputation 547 of the implicitly generated source tree. However, the 548 coordination of the MAC layer and the routing layer ensures 549 that the core broadcast establishes a tree, and that a core 550 node typically does not receive duplicates for a core 551 broadcast. 553 While the core broadcast in CEDAR has low overhead and adapts 554 easily to topology changes, the RTS and CTS packets corresponding 555 to a core broadcast need to be cached for some time after their 556 reception. Figure 2 illustrates a core broadcast in an example 557 network. Notice that all tunnels need not be used for core 558 broadcast, as the core broadcast dynamically establishes a 559 source-based tree, as mentioned above. 561 Core broadcast finds applicability in two key aspects of CEDAR: 562 discovery of the core path, and propagation of increase/decrease 563 waves. The discovery of the core path is broadcast because the 564 sender may not know the location of the receiver. It initiates a 565 core broadcast to find the location of the receiver, and 566 simultaneously, discover the core path. 568 4. QoS State Propagation in CEDAR 570 Section 3 described the core routing infrastructure of CEDAR. Since 571 each core node uses only the locally cached state to compute the 572 shortest-widest furthest path along the core path in the route 573 computation phase, the focus is now turned to the nature of state 574 that is stored in each core node. At one extreme is the minimalist 575 approach of only storing local topology information at each core 576 node. This approach results in a poor routing algorithm (i.e. the 577 routing algorithm may fail to compute an admissible route even if 578 such routes exist in the ad hoc network) but has a very low overhead 579 for dynamic networks. At the other extreme is the maximalist approach 580 of storing the entire link state of the ad hoc network at each core 581 node. This approach may compute optimal routes but incurs a high 582 state management overhead for dynamic networks, and potentially 583 computes stale routes based on out-of-date cached state when the 584 network dynamics is high. 586 The problem with having only local state is that core nodes are 587 unable to compute good routes in the absence of link-state 588 information about stable high-bandwidth remote links, while the 589 problem of having global state is that it is useless to maintain the 590 link state corresponding to low-bandwidth and highly dynamic links 591 that are far away because the cached state is likely to be stale 592 anyway. Fundamentally, each core node needs to have the up-to-date 593 state about its local topology, and also the link-state corresponding 594 to relatively stable high-bandwidth links further away. Providing for 595 such a link-state propagation mechanism ensures that CEDAR approaches 596 the minimalist local state algorithm in highly dynamic networks, and 597 approaches the maximalist link-state algorithm in highly stable 598 networks. CEDAR achieves the goal of having stability and bandwidth 599 based link-state propagation using increase and decrease waves, as 600 described in this section. 602 In the rest of this section, the draft first describes the mechanics 603 of the increase and decrease waves, and then answers the three key 604 questions pertaining to these waves: when should a wave be generated, 605 how fast should a wave propagate, and how far should a wave 606 propagate. 608 4a. Increase and Decrease Waves 610 For every link l=(a,b), the node b is responsible for monitoring 611 the available bandwidth on l and informing a of the same if l is 612 bi-directional. b and a in turn notify their respective 613 dominators for initiating the increase or decrease waves, when the 614 bandwidth changes by some threshold value. These waves are then 615 propagated by the dominators (core nodes) to a subset of core 616 nodes via core broadcasts. Each core node has two queues: the 617 "ito-queue" that contains the pending core broadcast messages for 618 increase waves, and the "dto-queue" that contains the pending core 619 broadcast messages for decrease waves. For each link l about which 620 a core node caches link-state, the core node contains the cached 621 available bandwidth bav(l). 623 The following is the sequence of actions for an increase wave: 625 1. When a new link l=(a,b) comes up, or when the available 626 bandwidth b(a, b) increases beyond a threshold value, then the 627 two end-points of l inform their dominators for initiating a 628 core broadcast for an increase wave: 630 ito() 632 where ito (increase to) denotes the type of the wave, (a,b) 633 identifies the link, dom(a) denotes the dominator of a, dom(b) 634 denotes the dominator of b, b(a, b) denotes the available 635 bandwidth on the link, and ttl(b) is a 'time-to-live' field 636 that denotes the maximum distance to which this wave can be 637 propagated as an increase wave. The ids of the dominators of 638 the link end-points are required by the routing algorithm. 639 ttl(b) is an increasing function of the available bandwidth, as 640 described in Section 4c. 642 2. When a core node u receives an ito wave 644 ito(), 646 1 if u has no state cached for (a,b), 647 2 bav(a,b) <- b(a,b) 648 3 if (ttl > 0), then add the following message 649 to the ito-queue: 650 4 ito() 651 5 else if u has cached state for (a,b) and (ttl > 0), 652 6 if (bav(a,b) < b(a,b)) 653 7 bav(a,b) <- b(a,b) 654 8 delete any pending ito/dto message for (a,b) from the 655 9 ito-queue and dto-queue. 656 10 add the following message to the ito-queue: 657 11 ito() 658 12 else if (bav(a,b) > b(a,b)), 659 13 bav(a,b) <- b(a,b) 660 14 delete any pending ito/dto message for (a,b) from the 661 15 ito-queue and dto-queue. 662 16 add the following message to the dto-queue: 663 17 dto() 664 18 else if u has cached state for (a,b) and (ttl = 0), 665 19 bav(a,b) <- b(a,b) 666 20 delete any pending ito/dto message for (a,b) from the 667 ito-queue and dto-queue. 668 21 add the following message to the dto-queue: 669 22 dto() 670 The ito-queue and the dto-queues are flushed periodically, 671 depending on the speed of propagation of the increase/decrease 672 waves. 674 The following is the sequence of actions for a decrease wave: 676 1. When a link l=(a,b) goes down, or when the available 677 bandwidth b(a, b) decreases beyond a threshold value, then the 678 two end-points of l inform their dominators for initiating a 679 core broadcast for a decrease wave: 681 dto(), 683 where dto (decrease to) denotes the type of the wave, and the 684 other parameters are as defined before. 686 2. When a core node u receives a dto wave 688 dto(), 690 1 if u has no state cached for (a,b) and (b(a,b) = 0), 691 2 the wave is killed. 692 3 else if u has no state cached for (a,b) and (b(a,b) > 0), 693 4 bav(a,b) <- b(a,b) 694 5 if (ttl > 0), then add the following message 695 to the ito-queue: 696 6 ito() 697 7 else if u has cached state for (a,b) and (ttl > 0), 698 8 if (bav(a,b) < b(a,b)), 699 9 bav(a,b) <- b(a,b) 700 10 delete any pending ito/dto message for (a,b) from the 701 11 ito-queue and dto-queue. 702 12 add ito() to 703 13 the ito-queue. 704 14 else if (bav(a,b) > b(a,b)), 705 15 bav(a,b) <- b(a,b) 706 16 delete any pending ito/dto message for (a,b) from the 707 17 ito-queue and dto-queue. 708 18 add the following message to the dto-queue. 709 19 dto() 710 20 else if u has cached state for (a,b) and (ttl = 0), 711 21 bav(a,b) <- b(a,b) 712 22 delete any pending ito/dto message for (a,b) from the 713 23 ito-queue and dto-queue. 714 24 add the following message to the dto-queue. 715 25 dto() 717 There are several key points in the above algorithm. First, the 718 way that the ito-queue and the dto-queue are flushed ensures that 719 the decrease waves propagate much faster than the increase waves 720 and suppress state propagation for unstable links. Second, waves 721 are converted between ito and dto on-the-fly, depending on whether 722 the cached value for the available bandwidth is lesser than the 723 new update (ito wave generated) or not (dto wave generated). 724 Third, after a distance of ttl (which depends on the current 725 available bandwidth of the link), the dto() message ensures that all other core nodes which had 727 state cached for this link now destroy that state. However, the 728 dto() wave does not propagate 729 throughout the network - it is suppressed as soon as it hits the 730 core nodes which do not have link state for (a,b) cached (line 2 731 in decrease wave propagation). The increase/decrease waves use the 732 efficient core broadcast mechanism for propagation. Figure 3 733 illustrates a decrease wave cancelling a previously generated 734 increase wave for a link l. 736 ^ 737 | 738 | 739 | increase wave 740 ^ | nullified 741 | | + - 742 | | + - 743 | + - 744 # of hops | + - 745 from | + - 746 l | + - 747 | + - 748 | + - 749 | + - 750 | + - 751 | + - 752 | + - 753 -|----X-----------------X----------------> 754 | increase wave decrease wave 755 | for l generated for l generated 757 time -> 759 Figure 3 : A decrease wave cancelling an increase wave for l 761 Essentially, the above algorithm ensures that the link-state 762 information for stable high-bandwidth links gets propagated 763 throughout the core, while the link-state information for unstable 764 and low-bandwidth links remains local - which is the goal of the 765 CEDAR state propagation algorithm. 767 4b. Issues in link state propagation 769 In this subsection, the three key questions pertaining to the 770 propagation of increase/decrease waves are discussed: when should 771 a wave be generated, how fast should a wave propagate, and how far 772 should a wave propagate. 774 When is a wave generated ? 776 To avoid a large overhead, CEDAR generates waves only when the 777 bandwidth has changed by some threshold value. We suggest the 778 use of a constant threshold when the bandwidth request sizes 779 are comparable to the available bandwidth and a logarithmic 780 scale [10] for the threshold when the typical request sizes are 781 an order of a magnitude less than the available bandwidths. The 782 advantage of the logarithmic update is that it does not 783 wastefully generate increase/decrease waves when the change in 784 link capacity is unlikely to alter the probability of computing 785 admissible routes. Further work is needed to substantiate the 786 above heuristics. 788 How Far does a Increase/Decrease Wave Propagate? 790 The goal is to propagate link bandwidth information to a number 791 of nodes that is proportional to the amount of bandwidth being 792 propagated. The motivation for this approach is the fact that 793 every node that has knowledge about a particular link would 794 potentially contend for the link, and a higher percentage of 795 requests can be satisfied if the contention on a link is 796 proportional to its bandwidth. Hence we suggest that the 797 maximum distance that the link state travels (time to live - 798 ttl) be an increasing function of the available bandwidth of 799 the link. Although the current CEDAR simulation uses a linear 800 function of the available bandwidth for computing the ttl, a 801 fluid model analysis of an ad hoc network suggests that in 802 general, the ttl should be a function of b^(1/k), where k is a 803 small number between 1 and 3. 805 How Fast does a Increase/Decrease Wave Propagate? 807 An increase wave waits for a fixed timeout period (which is a 808 system parameter that should be approximately twice the 809 expected inter-arrival time between the generation of two 810 successive waves for any link in the network) at each node 811 before being forwarded to its neighbors (using the core 812 broadcast). Thus, increase waves propagate slowly. A decrease 813 wave is immediately forwarded to its neighbors (using the core 814 broadcast). Thus decrease waves move much faster and can kill 815 increase waves for unstable links. 817 5. QoS Routing in CEDAR 819 The previous two sections have described the core infrastructure 820 (i.e. which nodes in the ad hoc network perform route computation and 821 how they communicate among themselves) and the state propagation 822 algorithm (i.e. what state does each core node contain). This 823 section completes the description of CEDAR by specifying how the core 824 nodes use the state information to compute QoS routes. 826 The QoS route computation in CEDAR consists of three key components: 827 (a) discovery of the location of the destination and establishment of 828 the core path to the destination, (b) establishment of a short stable 829 admissible QoS route from the source to the destination using the 830 core path as a directional guideline, and (c) dynamic re- 831 establishment of routes for ongoing connections upon link failures 832 and topology changes in the ad hoc network. 834 5a. Establishment of the Core Path 836 The establishment of a core path takes place when s requests 837 dom(s) to set up a route to d, and dom(s) does not know the 838 identity of dom(d) or does not have a core path to dom(d). 839 Establishment of a core path consists of the following steps. 841 1. dom(s) initiates a core broadcast to set up a core path with 842 the following message: . 844 2. When a core node u receives the core path request message 845 , it appends u to P, and 846 forwards the message to each of its nearby core nodes 847 (according to the core broadcast algorithm) to whose domain 848 there exists atleast one path (from u's domain) satisfying 849 bandwidth b. 851 3. When dom(t) receives the core path request message 852 , it sends back a source rooted 853 unicast core_path_ack message to dom(s) along the inverse path 854 recorded in P. The response message also contains P, the core 855 path from dom(s) to dom(d). 857 Upon reception of the core_path_ack message from dom(d), dom(s) 858 completes the core path establishment phase and enters the QoS 859 route computation phase. 861 Note that by virtue of the core broadcast algorithm, the core path 862 request traverses an implicitly (and dynamically) established 863 source routed tree from dom(s) which is typically a breadth-first 864 search tree. Thus, the core path is approximately the shortest 865 admissible path in the core graph from dom(s) to dom(d), and hence 866 provides a good directional guideline for the QoS route 867 computation phase. Figure 4 shows an example for a core path. The 868 example assumes that the link marked with 0.5 has an available 869 bandwidth of 0.5 units, whereas all other links have 1 unit of 870 bandwidth available. The route request has a QoS requirement of 1 871 unit. 873 o 874 | 875 |1 876 * 877 1 / \ 1 878 1 / \ 1 879 S o----*-----*----o 880 + | 881 + | 882 1 + | 1 883 + | 884 1 + 0.5 | 1 885 o----*+++++*----o D 886 | | 887 1 | | 1 888 o-----o 1 890 + core path S source D destination 892 Figure 4 : Core path from dom(S) to dom(D) 894 5b. QoS Route Computation 896 After the core path establishment, dom(s) knows dom(d) and the 897 core path from dom(s) to dom(d). Recall from Section 3 that dom(s) 898 has the local topology - which includes all the nodes in its 899 domain, and for each dominated node u, the bandwidth of each link 900 incident on u, the adjacency list of u and the dominator of each 901 of the neighbors of u. Recall from Section 4 that dom(s) has the 902 information gathered about remote links through increase/decrease 903 waves, and for each such link (u, v), the bandwidth of (u,v), 904 dom(u), and dom(v). dom(s) thus has a partial knowledge of the ad 905 hoc network topology, which consists of the up-to-date local 906 topology, and some possibly out-of-date information about remote 907 stable high-bandwidth links in the network. The following is the 908 sequence of events in QoS route computation. 910 1. Using the local topology, dom(s) tries to find a path from s 911 to the domain of the furthest possible core node in the core 912 path (say dom(t)) that can provide at least a bandwidth of b 913 (bandwidth of the connection request). The bandwidth that can 914 be provided on a path is the minimum of the individual 915 available link bandwidths that comprise the path. 917 2. Among all the admissible paths (known using local state) to 918 the domain of the furthest possible core node in the core path, 919 dom(s) picks the shortest-widest path using a two phase 920 Dijkstra's algorithm [11]. The first phase is used to find the 921 available bandwidth B of the widest path. In the subsequent 922 phase, links with available bandwidth less than B are 923 eliminated before computing the shortest path in the resulting 924 graph. 926 3. Let t be the end point of the chosen path and p(s, t) denote 927 the path. dom(s) sends dom(t) the following message: < s, d, 928 b, P, p(s, t), dom(s), t>, where s, d, and t are the source, 929 destination, and intermediate node in the partially computed 930 path, b is the required bandwidth, P is the core path, and p(s, 931 t) is the partial path. 933 4. dom(t) then performs the QoS route computation using its 934 local state identical to the computation described above. 936 5. Eventually, either there is an admissible path to d or the 937 local route computation will fail to produce a path at some 938 core node. The concatenation of the partial paths computed by 939 the core nodes provides an end-to-end path that can satisfy the 940 bandwidth requirement of the connection with high probability. 941 Figure 5 shows how the core path found in Figure 4 is used to 942 find a QoS route satisfying the 1 unit bandwidth request. As 943 mentioned earlier, all links except the one indicated with 0.5, 944 have an available bandwidth of 1 unit. This example also 945 illustrates that the QoS route found in CEDAR can be non- 946 optimal as it uses a core path as the guiding direction (the 947 path along the core has 7 hops whereas there is another 948 feasible path - not along the chosen core path - with 6 hops). 950 The core path is computed in one round trip, and the QoS route 951 computation algorithm also takes one round trip. Thus, the route 952 discovery and computation algorithms together take two round trips 953 if the core path is not cached and one round trip otherwise. 955 Note that while the QoS route is being computed, packets may be 956 sent from s to d using the core path. The core path thus provides 957 a simple backup route while the primary route is being computed. 959 o 960 | 961 | 962 * 963 / \ 964 / \ 965 S o....*-----*----o 966 : | 967 o o 968 : | 969 : o 970 : 0.5 | 971 o----*-----*....o D 972 : : 973 : : 974 o.....o 976 Figure 5 : QoS route from S to D satisfying a bandwidth 977 requirement of 1 unit. 979 5c. Dynamic QoS Route Recomputation for Ongoing Connections 981 Route recomputations may be required for ongoing connections under 982 two circumstances: the end host moves, and there is some 983 intermediate link failure (possibly caused by the mobility of an 984 intermediate router or by a reduction in available bandwidth on 985 that link such that the connection can no longer be served). End 986 host mobility can be thought of as a special case of link failure, 987 wherein the last link fails. 989 CEDAR has two mechanisms to deal with link failures and reduce the 990 impact of failures on ongoing flows: dynamic recomputation of an 991 admissible route from the point of failure, and notification back 992 to the source for source-initiated route recomputation. These two 993 mechanisms work in concert and enable us to provide seamless 994 mobility. 996 1. QoS Route Recomputation at the Failure Point: Consider that 997 a link (u, v) fails on the path of an ongoing connection from s 998 to t. The node nearest to the sender, u, then initiates a local 999 route recomputation similar to the algorithm in Section 5b. 1000 Once the route is recomputed, u updates the source route in all 1001 packets from s to t accordingly. If the link failure happens 1002 near the destination, then dynamic route recomputation at the 1003 intermediate node works very well because the route 1004 recomputation time to the destination is expected to be small, 1005 and packets in-flight are re-routed seamlessly. 1007 2. QoS Route Recomputation at the Source: Consider that a link 1008 (u, v) fails on the path of an ongoing connection from s to t. 1009 The node nearest to the sender, u, then notifies s that the 1010 link (u, v) has failed. Upon receiving the notification, u 1011 stops its packet transmission, initiates a QoS route 1012 computation as in Section 5b, and resumes transmission upon 1013 the successful re-establishment of an admissible route. If the 1014 link failure happens near the source, then source-initiated 1015 recomputation is effective, because the source can quickly 1016 receive the link-failure notification and temporarily stop 1017 transmission. 1019 The combination of these two mechanisms is effective in supporting 1020 seamless communication inspite of mobility and dynamic topology 1021 changes. Basically, CEDAR uses source-initiated recomputation as 1022 the long-term solution to handling link failure, while the short- 1023 term solution to handle packets in-flight is through the dynamic 1024 recomputation of routes from the intermediate nodes. Recomputation 1025 at the failure point is not really effective if the failure 1026 happens close to the source, but in this case, the number of 1027 packets in flight from s to u is small. 1029 6. Performance Results 1031 We have evaluated the performance of CEDAR via both implementation 1032 and simulation. Our implementation consists of a small ad hoc network 1033 consisting of six mobile nodes that use Photonics (Data Technology) 1 1034 Mbps infrared network. We have customized the Linux 2.0.31 kernel to 1035 build our ad hoc network environment (written partly in user mode and 1036 partly in kernel mode). While the testbed shows proof of concept and 1037 has exposed some difficulties in implementing CEDAR, our detailed 1038 performance evaluation [12] has been using a simulator that 1039 faithfully implements the CEDAR algorithms. 1041 While the entire gamut of results obtained from the tests are not 1042 presented due to space constraints, the rest of this section briefly 1043 summarizes the performance of CEDAR as observed from these tests. For 1044 tests in a best-effort environment we assume the optimal performance 1045 to be the performance of a global algorithm that does shortest path 1046 computation, while in a QoS environment we assume this to be the 1047 performance of a global algorithm doing a shortest widest path 1048 computation. The metrics used for comparison in these results are: 1049 (i) stretch - the ratio of the number of hops in a route computed by 1050 CEDAR to the number of hops in a route computed by the global 1051 algorithm, (ii) bandwidth - the ratio of bandwidth available on the 1052 routes computed by CEDAR to that of the global algorithm, (iii) 1053 message complexity, (iv) time complexity and (v) crankbacks - the 1054 ratio of the number of rejects to the number of connection requests. 1056 In a best-effort environment, CEDAR performs reasonably well before 1057 the introduction of ito/dto waves, and progressively converges to a 1058 near optimal performance once these waves are introduced. In 1059 particular, for dynamic networks we observed a stretch of around 1.2 1060 before the waves were introduced. The stretch came down to 1.1 once 1061 the waves were introduced. For stable networks, the stretch observed 1062 was 1. Additionally, the message and time complexities of CEDAR were 1063 also comparable to the optimal performance [12]. 1065 In a QoS environment, CEDAR was compared to the optimal algorithm in 1066 terms of the number of hops and the bandwidth available on the 1067 computed path. In terms of bandwidth, CEDAR's performance was worse 1068 than the optimal performance by an average of 3%. For the number of 1069 hops on the computed path, CEDAR in fact performed better in some 1070 cases (the global algorithm could pick a longer path with a higher 1071 bandwidth). When the number of crank-backs was observed in these 1072 tests, CEDAR had 30% more crank-backs than the optimal algorithm 1073 before the introduction of waves, while after the introduction of 1074 ito/dto waves, the number of crank-backs were the same in both CEDAR 1075 and the optimal algorithm. 1077 For detailed performance results, please refer to [12]. 1079 7. Conclusions 1081 This draft presents CEDAR, a core-Extraction Distributed Ad hoc 1082 Routing algorithm for providing QoS in ad hoc network environments. 1083 CEDAR has three key components: (a) the establishment and 1084 maintenance of a self-organizing routing infrastructure, called 1085 the "core", for performing route computations, (b) the 1086 propagation of the link-state of stable high-bandwidth links in the 1087 core through "increase/decrease" waves, and (c) a QoS route 1088 computation algorithm that is executed at the core nodes using only 1089 locally available state. While the core provides an efficient and 1090 low-overhead infrastructure to perform routing and broadcasts in an 1091 ad hoc network, the increase/decrease wave based state propagation 1092 mechanism ensures that the core nodes have the important link-state 1093 they need for route computation without incurring the high overhead 1094 of state maintenance for dynamic links. The QoS routing algorithm is 1095 robust and uses only local state for route computation at each core 1096 node. 1098 CEDAR is a robust and adaptive algorithm that reacts quickly and 1099 efficiently to the dynamics of the network while still approximating 1100 link-state performance for stable networks. Our simulations show that 1101 CEDAR produces good stable admissible routes with a high probability 1102 if such routes exist. Furthermore, CEDAR does not require high 1103 maintenance overhead even for highly dynamic networks. Ongoing work 1104 on CEDAR is focusing on three areas. (a) While it is shown that CEDAR 1105 is effective for small to medium size networks, work is being done on 1106 a hierarchically clustered version of CEDAR that can provide QoS 1107 routing in large ad hoc networks. (b) While this draft has only 1108 considered bandwidth as the QoS parameter in this work, current work 1109 is extending CEDAR to include delay as a QoS parameter and (c) The 1110 heuristics mentioned in Section 4 need more study and are in the 1111 process of being refined. 1113 8. References 1115 [1] R. Nair, B. Rajagopalan, H. Sandick, and E. Crawley. "A 1116 framework for QoS-based routing in the Internet." Internet 1117 Draft draft-ietf-qosr-framework-05.txt, May 1998. 1119 [2] D. B. Johnson and D. A. Maltz. "Dynamic source routing in ad 1120 hoc wireless networks". In Mobile Computing, (ed. T. Imielinski 1121 and H. Korth), Kluwer Academic Publishers, 1996. 1123 [3] A. Ephremides, J. E. Wieselthier, and D. J. Baker. "A design 1124 concept for reliable mobile radio networks with frequency 1125 hopping signaling". In Proceedings of the IEEE, pages 56--73, 1126 January 1987. 1128 [4] M. S. Corson and A. Ephremides. "A highly adaptive distributed 1129 routing algorithm for mobile wireless networks". ACM/Baltzer 1130 Wireless Networks Journal, 1(1):61--81, February 1995. 1132 [5] V. D. Park and M. S. Corson. "A highly adaptive distributed 1133 routing algorithm for mobile wireless networks". In Proceedings 1134 of 1997 IEEE Conference on Computer Communications, April 1997. 1136 [6] R. Sivakumar, B. Das, and V. Bharghavan. "Spine routing in ad 1137 hoc networks". ACM/Baltzer Cluster Computing Journal (special 1138 issue on Mobile Computing). To appear, 1998. 1140 [7] V. Bharghavan, S. Shenker A. Demers, and L. Zhang. "MACAW: A 1141 medium access protocol for wireless LANs". In Proceedings of 1142 ACM SIGCOMM}, London, England, August 1994. 1144 [8] S. Lu, V. Bharghavan, and R. Srikant. "Fair queuing in wireless 1145 packet networks". In Proceedings of ACM SIGCOMM '97, Cannes, 1146 France, September 1997. 1148 [9] C. E. Perkins and P. Bhagwat. "Highly dynamic destination- 1149 sequenced distance-vector routing (DSDV) for mobile computers". 1150 In Proceedings of ACM SIGCOMM, pages 234--244, London, England, 1151 August 1994. 1153 [10] B. Awerbuch, Yi Du, B. Khan, and Y. Shavitt. "Routing through 1154 networks with topology aggregation". In IEEE Symposium on 1155 Computers and Communications, Athens, Greece, June 1998. 1157 [11] Q. Ma and P. Steenkiste. "On path selection for traffic with 1158 bandwidth guarantees". In Proceedings of Fifth IEEE 1159 International Conference on Network Protocols, Atlanta, October 1160 1997. 1162 [12] R. Sivakumar, P. Sinha and V. Bharghavan. "CEDAR: a Core- 1163 Extraction Distributed Ad hoc Routing algorithm". TIMELY Group 1164 Technical Report,http://www.timely.crhc.uiuc.edu/Papers/cedar.ps 1166 9. Author's Addresses 1168 Raghupathy Sivakumar 1169 458 C&SRL, Coordinated Science Lab 1170 University of Illinois, Urbana-Champaign 1171 1308 W. Main St., Urbana, IL 61801 1172 USA 1173 Email: sivakumr@timely.crhc.uiuc.edu 1175 Prasun Sinha 1176 458 C&SRL, Coordinated Science Lab 1177 University of Illinois, Urbana-Champaign 1178 1308 W. Main St., Urbana, IL 61801 1179 USA 1180 Email: prasun@timely.crhc.uiuc.edu 1182 Vaduvur Bharghavan 1183 457 C&SRL, Coordinated Science Lab 1184 University of Illinois, Urbana-Champaign 1185 1308 W. Main St., Urbana, IL 61801 1186 USA 1187 Email: bharghav@timely.crhc.uiuc.edu