From eyh5@ee.cornell.edu Wed Sep 26 21:03:55 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8R13tq22144 for ; Wed, 26 Sep 2001 21:03:55 -0400 (EDT) Received: from photon (photon.ee.cornell.edu [128.84.239.166]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f8R13s615133 for ; Wed, 26 Sep 2001 21:03:54 -0400 Date: Wed, 26 Sep 2001 21:12:45 -0400 (EDT) From: Edward Hua To: egs@CS.Cornell.EDU Subject: 615 Paper # 16 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII CEDAR: A Core-Extraction Distributed Ad-hoc Routing Algorithm This paper attempts to introduce the QoS guarantee, measured by the guaranteed available bandwidth (BW) along the path, into the mobile ad-hoc network. The idea behind CEDAR is to identify a number of core nodes, or the dominators, amongst all the mobile nodes in a network. These core nodes, using RTC/CTS, communicate with each other and form the core of the network. Each maintains link state information of its most immediate neighbors. The knowledge of each core node with respect to its constituents is purely local, and no core node needs to know the global link state information of the entire network.. The core nodes are connected via virtual links. In a way, the core nodes are analogous to the base stations in the cellular wireless technology. To incorporate the BW guarantee into establishing a path between a source (S) and a destination (D), the paper proposes the use of two signaling packets, ito and dto. Each constituent node under a core node's charge is responsible for monitoring the link BWs with its neighbors, and periodically reports this information to the core node via either ito (detecting an increase in BW) or dto (detecting a decrease in BW). This information is useful in assisting the core nodes to identify a suitable route that meets the BW requirement of a data transmssion. The ito-queue and dto-queue located in a core node are flushed in a way that ensures that the news of decreasing BW propogates much faster than the news of increasing BWs. One of its strengths is the scalability. Localizing the exchange of link-state information within the core node's coverage allows a new node moving in and out of this coverage to freely associate with and dissociate from the core node. Because each core node only possesses the knowledge of its constituents' link-state information, BW is conserved. One weakness may deserve some attention. Suppose S, whose has the core node, DOM(S), wants to send packets to D, with the core node DOM(D). And let's assume there is a direct virtual link connection between DOM(S) and DOM(D). The algorithm dictates that the packets from S be sent to DOM(S) first, which then routes them to DOM(D) via the virtual link. Once it receives the packets, DOM(D) then identifies D under its coverage and forwards the packet to it. However, there are circumstances where S and D may be sufficiently close to each other geographically, say one hop away from each other, and they belong to two different core nodes. If this is the case, routing all the way from DOM(S) and DOM(D) may not be as efficient as simply establishing a direct connection between S and D, and the BW is unneccessarily overused. This can be easily done with each of the borderline nodes holding information of its neighbors who don't belong to the same core node as it does. This borderline issue needs to be addressed in order to better utilize the bandwidth within the network. From wbell@CS.Cornell.EDU Thu Sep 27 01:09:22 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8R59Mq16274 for ; Thu, 27 Sep 2001 01:09:22 -0400 (EDT) Received: from [192.168.1.103] (syr-66-24-16-64.twcny.rr.com [66.24.16.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA12037 for ; Thu, 27 Sep 2001 01:09:20 -0400 (EDT) Subject: 615 PAPER #16 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Evolution-Format: text/plain X-Mailer: Evolution/0.13.99+cvs.2001.09.21.20.26 (Preview Release) Date: 27 Sep 2001 01:09:04 -0400 Message-Id: <1001567366.1055.0.camel@brute> Mime-Version: 1.0 16) CEDAR: A Core-Extraction Distributed Routing Algorithm In this paper we are introduced to CEDAR, the first algorithm we've seen that's completely based on election of special nodes which handle routing information for the majority of the network. In CEDAR, local nodes elect a core node, which dominates all nodes in the local neighborhood, and all core nodes dominate all nodes in the network. Core nodes are then responsible for disseminating routing information between themselves, and local nodes use the resources of their local core node in order to perform routing operations. The motivation behind core nodes is that previous algorithms waste too many resources publishing connectivity information to all nodes, and that by electing a smaller subset of the network to bear this burden, the overall resources used would be minimized. Another goal in CEDAR is to minimize the number of broadcasts, as they assert that contention during broadcast is much larger than previously believed. In addition to providing basic routing services, CEDAR attempts to provide a simple model for quality of service, where nodes can request a required bandwidth for a route from the source to destination. This is done by propagating available bandwidth information from the core nodes during dissemination. Because local bandwidth changes need to propagate to other core nodes, they exchange bandwidth changes greater than a certain threshold via ito (increase to) and dto (decrease to) which inform core nodes that available bandwidth has changed on a given link. QoS guarantees are achieved via simple bandwidth reservation of channels during route computation between senders and receivers. The motivation of the paper was clear, but I was somewhat disappointed with the execution. Electing core nodes seems like a good idea, but it seems to require more useful metrics than just a simple voting. Even simple schemes such as taking nodes with the longest lifetime or the least mobility would provide more stable core nodes. I was also unhappy with the bidirectional link assumption after the discussion of the hidden terminal problem. The idea of directed sends based on so-called core nodes is an interesting idea, if for nothing else than high level directional information. It would be interesting to model the network as a set of clusters [at higher and higher levels], such that long distance communications were directed at a cluster, which becomes more refined as the communication gets closer to the destination, which would remove the need for comprehensive routing information at each step. The simulations were weak. They postulate that CEDAR can handle tens to hundreds of nodes, but then proceed to evaluate with 6 nodes [albeit real nodes.] Later, they move to some simulation model [30 nodes], but with little details as to the real model behind the simulation. I would take all the results with a grain of salt. Overall, there were some good ideas hidden in this paper, but the execution of them was quite weak. From haom@csl.cornell.edu Thu Sep 27 04:41:23 2001 Return-Path: Received: from mauchly.csl.cornell.edu (mauchly.csl.cornell.edu [132.236.71.68]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8R8fNq06677 for ; Thu, 27 Sep 2001 04:41:23 -0400 (EDT) Received: from localhost (haom@localhost) by mauchly.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id EAA66130 for ; Thu, 27 Sep 2001 04:41:17 -0400 (EDT) (envelope-from haom@mauchly.csl.cornell.edu) X-Authentication-Warning: mauchly.csl.cornell.edu: haom owned process doing -bs Date: Thu, 27 Sep 2001 04:41:17 -0400 (EDT) From: Ming Hao To: egs@CS.Cornell.EDU Subject: 615 PAPER 16 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII CEDAR: a Core-Extraction Distributed Ad hoc Routing algorithm by Raghupathy Sivakumar the motives of inplementing QoS in Ad hoc net is the quality requirement of military and multimedia applications. ( estimation of available bandwidth is hard problem, in paticular for variable transmission range). the paper proposes a cluster based algorithm which can provide near optimal QoS service with the propagation of bandwidth info among core nodes. 1. geration and maintenance core graph each node selects its dominator based on the info of (d*, d) of its neighbor nodes and itself. d* represents the number of nodes it dominates. d the number of neighbor nodes. bandwidth info of links are propagated int his way: bandwidth increase info proagates slow while decrease info fast so that unstable links info are supressed.high bandwidth increase can propagates longer. all these are intuitively correct and helps achive the near optimal result. broadcasts among core codes is implemented unicast with RTS/CTS. the control messages are stored temporarily to eliminate the duplicate transmission. 2 routing is done in two steps. (a) establish core path which is similar to DSR. which selects almost shortest one(does it considering bandwidth requirement? if not, the selected path can reduce the possibility to find a path with enough bandwidth. if yes, is it accurate to use bandwidth of virtual links to estimate the bandwidth in that diredction?) (b) using core path as a guide, compute real path which support the bandwidth 3. routing maintenance: (a) repair it dynamically if failure hapens near the destination (b) recomputation if near source simulation: the paper claims that a protoytpe was implemented but many difficulties were faced, which were not detailed. only simulation results are given. 1. finding the shortest path without considering QoS. CEDAR can find the near optimal path. this is understandable. but two round trip overhead is obvious. what impressmed me is that CEDAR has little message overhead 2. for the performance of QoS routing, it can be concluded that with ito and dto queue, the accpet/reject ratio is improved greatly. the biggest weak of simulation result is that the bandwidth usage pattern is not detailed. i doubt it can achive near optimal results for all the cases. further, i think it would be interesting to compare the result of CEDAR with proactive routing algorithms where bandwidth is propagated periodically. summary: for QoS kind of routing, the link state has to be propagated, cluster based algorithms may be useful in the term of message overhead and scalability.the simulation result shows near optimal result can be achived be CEDAR. that is great. but delay, computation overhead may be a problem. another contribution of this paper is its new broadcast mechanism with the helpof RTS/CTS to avoid flooding. -ming Ming Hao PH.D Candidate, EE mh97@cornell.edu Cornell University Office: (607) 255-0817 Ithaca, NY 14853 http://www.ee.cornell.edu/~haom/ From gupta@CS.Cornell.EDU Thu Sep 27 10:41:25 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8REfOo13445 for ; Thu, 27 Sep 2001 10:41:24 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: 615 PAPER 16 Date: Thu, 27 Sep 2001 10:41:24 -0400 Message-ID: <404A3A4758DDCC4C8A5C9A537384F9D6043A9B@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 16 Thread-Index: AcFHYnt0Hn6XN3RIR9+Fdn/UK5lNUw== From: "Indranil Gupta" To: "Emin Gun Sirer" Cc: "Indranil Gupta" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f8REfOo13445 CEDAR: a code-extraction distributed ad hoc routing algorithm, R. Sivakumar, P. Sinha, V. Bhargavan. Reviewer: Indranil Gupta Summary: The authors propose using a subset of the nodes in the network as a 'core' for routing. Every node in the system is 'close' to another core node (dominating set => at most 1 hop away). Link states are propagated only among the nodes of the core nodes. Routes travel from the source to the nearest core node, then to another core node near the destination, and from there to the destination. The algorithm to find a nearby core node, or decision to turn into a core node, is a local process to the node in question. Any of the protocols - AODV, DSR, ZRP etc. can be used within the core subnetwork. The authors a source routing protocol. The authors also present a broadcast scheme that uses RTS-CTS to minimize the number of broadcasts across the core network, based on not transmitting the broadcast (or an RTS for it) if you've heard RTS's or CTS's from all your neighbors. The authors use the ideology of "bad news should spread quickly, good news slowly" regarding informing the rest of the network about link bandwidth availability (called increase/decrease waves in the paper). The QoS routing algorithms used in the paper seem to be orthogonal to the use of a core, and can potentially be implemented in a general ad-hoc routing protocol. For QoS, the authors are primarily concerned about satisfying user bandwidth requirements on a best effort basis. The simulation experiments show that the CEDAR schemes perform close to the optimal, in terms of minimum path length, path discovery time etc. Link failures closer to the destination cause a large number of reroutings, while a link failure closer to the source causes a large number of packets to be dropped. Comments: * The algorithms are not power-aware : core nodes' batteries are quickly depleted. Besides, the core nodes get overburdened with packets, and the QoS provided to *them* is affected. * There are several possible solutions to the problem posed in the previous point: 1) migrate the core membership from time to time using a cheap algorithm while guaranteeing short paths, or 2) using the core nodes to only convey routing information, and use other nodes to actually route the packets. There is good scope for future work. * The authors do not experimentally evaluate the benefits of their new broadcast scheme with RTS-CTS. For example, for dense ad-hoc networks, what % of broadcasts are saved (each node will broadcast since there will always be a neighbor that hasn't heard it) ? * The algorithms handle only the bandwidth part of the QoS problem - this is just the tip of the QoS iceberg. Introducing latency etc. in the user's QoS requirements might call for different route decision algorithms. Some of the research from the Internet QoS community would definitely be applicable. * The simulations are done with at most 20 radios, and for a single source-destination pair - these and sparseness of the resulting graph does not interfere with the ad-hoc routing protocol. Conceivably, any other routing protocol will perform close to the optimal by using bandwidth as a link cost. * What is the academic and industry community's attitude towards passing (and using) MAC layer information up in the network layer ? (the authors do this in their new broadcast scheme). * What percentage of nodes are core nodes (typical fraction) ? Gleanings: The good ideas/lessons in this paper are: 1) use of a core node subset for routing, 2) a new protocol for broadcast (not evaluated), 3) having bad news travel faster than good news (news about link up/down states and bandwidth), 4) broadcast through flooding is unreliable due to absence of RTS-CTS. From teifel@csl.cornell.edu Thu Sep 27 10:45:30 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8REjTo13877 for ; Thu, 27 Sep 2001 10:45:29 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8REjOl73419 for ; Thu, 27 Sep 2001 10:45:24 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Thu, 27 Sep 2001 10:45:24 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 16 Message-ID: <20010927103012.I56676-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII CEDAR: CEDAR, a Core-Extraction Distributed Ad hoc Routing algorithm that provides QoS in ad hoc network environments. The algorithm provides for the establishment and maintenance of routes, the propagation of QoS information, and a QoS route computation algorithm. This algorithm uses bandwidth and stability information as its QoS information. An interesting feature of this algorithm is its core extraction capability. They use core extraction to dynamically find a minimum dominating set of the adhoc network, using only local computation and local state. Each core node maintains the local topology of the nodes in its domain and gives route information to nodes in its domain. Propagation of QoS information is only done by core nodes. It trys to select the shortest-widest path to transmit on. I think that for dense networks, the overhead on this algorithm is possibly acceptable, but for sparse networks I have a feeling that the protocol overhead would be large--since there would be little clustering. As far as I could see, I don't think this was addressed. Why is the implementation so small--only six mobile nodes... I guess that is somewhat reasonable for 1999, but not reasonable enough that it should be included in a publication (although very few other papers even tried to implement their designs). From daehyun@csl.cornell.edu Thu Sep 27 10:49:51 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8REnpo14384 for ; Thu, 27 Sep 2001 10:49:51 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id KAA37799 for egs@cs.cornell.edu; Thu, 27 Sep 2001 10:49:01 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109271449.KAA37799@wilkes.csl.cornell.edu> Subject: 615 PAPER 16 To: egs@CS.Cornell.EDU Date: Thu, 27 Sep 2001 10:49:01 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper presents a routing algorithm called Core-Extraction Distributed Ad hoc Routing (CEDAR), which supports QoS routing in ad hoc network environments. The main goal of CEDAR is to provide routes that are highly likely to satisfy the bandwidth requirement. CEDAR establishes a core of the network, then propagates the link state to the nodes of the core. Route is computed on-demand at core nodes using only the local information. The basic idea of CEDAR is to establish a core network. A core node is like a base station of conventional wireless networks. It manages the nodes within its domain and calculates the route on behalf of them. It communicates to other core nodes to maintain the global core networks. Here, the key is that the core node information doesn't need to ge global. A core node maintains local information and some amount of global information. Complete information needed to establish a route will be obtained on-demand and distributedly by the routing algorithm. Three important components are as follows; 1. Core Extraction: A set of nodes form a core of the network. Each core node maintains local network information in its domain and calculate routes for the nodes in it. 2. Link State Propagation: The bandwidth information of stable links are propagated through the entire network to achieve QoS routing. Slow moving increase waves and fast moving decrease waves are used. 3. Rout Computation: A core path is established first, then a partial path is found iteratively, satisfying the quested bandwidth. In my opinion, the strength of CEDAR is that it finds the optimal trade-off point well. Because CEDAR uses the core network, it sacrifices the optimality of routes. the routes found by CEDAR may not be optimal paths. But, instead, CEDAR can reduce the complexity of the algorithm and achieve its owd goal, providing QoS routes quickly. I think it is a good engineering approach. This paper assumes that all the nodes communicate on the same shared wireless channel. In my opinion, this may limit the size of the network. Actually, this paper said that CEDAR is proposed as a routing algorithm for small to medium size networks and they have proposed a cluster algorithm for the large scale networks. I think it will be interesting to see how to expand the algorithm to the large size of network. I think maintaining the core network might be a hard work, especially in ad hoc networks. As they said in this paper, finding core nodes is a NP hard problem, and it will be harder if the network topology changes frequently. Though they propose a algorithm to solve this problem, I think, this might be a problem still. From avneesh@csl.cornell.edu Thu Sep 27 11:05:43 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8RF5ho16235 for ; Thu, 27 Sep 2001 11:05:43 -0400 (EDT) Content-Class: urn:content-classes:message Subject: 615 Paper 16 Date: Thu, 27 Sep 2001 11:10:48 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Message-ID: <97C142C1212ED545B0023A177F5349C4053AA5@capricorn.ds.csl.cornell.edu> X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper 16 Thread-Index: AcFHZpa6UhqalxWQS6uO/VzBfIdnlg== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8RF5ho16235 CEDAR: A core extraction Distributed Ad-hoc routing algorithm Paper Summary/Critique. This paper emphasizes the QOS properties of an adhoc network, while provding an alternative to how routing could be done within such a network. The basic idea (based upon the 'spine' architecture), is to use a locally centralized, globally decentralized mechanism to handle noad toplogy and message propagation. In other words, local nodes select a core node which dominates them and the set of core nodes in the network thus dominate all nodes in the network. Core node selection is done using the number of hops between any node and the core node. The centralized part i.e the core nodes thus are responsible for performing routing operations for the local nodes and distribute this information between other core nodes. Hence the aim is to alleviate the total amount of routing traffic with the help of this mechanism. No core node is required to know the entire topology of the graph. RTS and CTS messages are used to improve routing behaviour. The routing is source initiated. The paper also formalizes a model for evaluating the QOS of a link thus attempting to provide a minimum bandwidth requirement for a connection as well establishing a preference over stable high bandwidth link information propagation in the network. With the help of two kinds of 'waves' viz. ito (increase) and dto (decrease), the bandwidth information is spread through the network. A fairly simple algorithm ensures that dto waves travel faster than ito, which in other words means that bad news would travel faster and that is a good optimization since we are worried more about links breaking down than an slight improvement in bandwidth. With the help of a threshold value in bw change, the propagation of this info is managed. Simulations are then provided to demonstrate the routing algorithm with and without increase/decrease waves and QOS information as compared to an optimal case. They sufficiently show that with the help of ito and dto waves the accept/reject ratio for example, is vastly improved. Also from the discussion and design of the algorithm, it seems that it might be quite scalable. This is where the simulations were lacking. I felt that the CEDAR paper was very well written and formulated but in the end assumed a very simplistic simulation model. They mention all the valid constraints that ought to occur in the routing, but do not simulate them e.g performance vs node density, network toplogy layout and most of all the optimality of core node creation itself i.e, are core nodes created in such a way that the traffic is reduced as much as expected? The number of nodes simulated is about 30 which did not present a scalability picture either. Finally I think that the handing of link failure and recomputation was quite interesting, since it takes into account how far the failure is from the source. From ramasv@CS.Cornell.EDU Thu Sep 27 11:17:15 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8RFHFo17585 for ; Thu, 27 Sep 2001 11:17:15 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: cs615 PAPER 16 Date: Thu, 27 Sep 2001 11:17:15 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F272@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 16 Thread-Index: AcFHZ2hP9loq2rKaEdWTbwCQJ5m7oA== From: "Venu Ramasubramanian" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8RFHFo17585 CEDAR: a Core Extraction Distributed Ad Hoc Routing Algorithm This paper essentially makes two contributions: the maintenance of an approximate dominating set called the Core to reduce the complexity of routing and an algorithm to perform QoS (bandwidth) routing by local propagation of control messages. The goal of this algorithm is to find the shortest-widest path (the width being the bandwidth of the link) between two core nodes that represent the source and the destination. The core is an approximation of a minimum dominating set of the under-lying network i.e., every node is either a core node or has a link to a core node. Periodic updates by each node carrying the number of neighbors and the number of nodes for which it is a core, helps to maintain this dominating set. The efficiency of this method (how close to the minimum dominating set it actually gets) however is not evaluated. The set of core nodes are then expected to maintain virtual links (of length atmost 3) among the neighbors in the core graph. Broadcast of rotue requests to the core-neighbors is done by unicasting through the virtual links and caching RTS/CTS information inorder to make broadcast efficient. However the RTS/CTS is a scheme usually implemented in hardware and to change a hardware implementation is not a very easy task. QoS routing is performed by sending slow-moving increase wave and fast moving decrease wave among the core nodes whenever bandwidth of a link increases or decreases. Waves for higher bandwidth links travel further than lower bandwidth links. These waves are not propagated by the core nodes that does not have a cached value of b/w for this link. Such a propagation happens even for links that are not being currently used by any active routes, hence would be inefficient for dense networks. Further, the cached bandwidth information at the nodes could often be out-dated preventing the algoritm from calculating good routes soon. The paper also does not mention how virtual links of sufficient bandwdith are found. It appears that the algorithm does not make attempts to reserve bandwidth at the links. Hence it is not clear how bandwidth is shared in the presence of multiple routes. The simulation results presented in the paper are inadequate except as a proof of concept. The number of nodes in the simulation are only 30. It is not clear how the physical and MAC layers are modeled. They simulate mobility by introducing a single link break at different points in a single route. More elaborate simulations are required to establish the effectiveness of the protocol. The maintenance of core nodes and routing based on core nodes is an interesting concept that needs further evaluation. From ranveer@CS.Cornell.EDU Thu Sep 27 11:37:50 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8RFbno20036 for ; Thu, 27 Sep 2001 11:37:49 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: 615 PAPER 16 Date: Thu, 27 Sep 2001 11:37:48 -0400 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 16 Thread-Index: AcFHalwylvawIMvcQre7PpArE6M2ww== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f8RFbno20036 CEDAR: a Core-Extraction Distributed Ad hoc Routing algorithm This paper proposes a new algorithm for QoS routing in ad hoc networks. The nodes proactively maintain a dominating set through periodic beaconing. The dominators(or cores) are responsible to take further routing decisions. A node that wishes to establish a route, first sends a packet to its dominator who then uses the virtual links(paths connecting core nodes to its 3-nbrhood) to find the dominator of the destination. Based on the non-local bandwidth information, the dominators try to establish a shortest-widest route from the source to the destination. Control packets: 'ito' and 'dto' are used to propagate the bandwidth information of the links to distant nodes in the network. The main contribution of this paper is the idea of clustering by using dominator nodes. Since only the dominators are involved in routing decisions, most of the maintenance traffic is local. Besides, an unreliable broadcast is avoided by using a sequence of unicasts among core nodes that are much more reliable. This is a contrast to the other routing algorithms, such as AODV, DSR, etc. CEDAR aso looks into QoS routing, where bandwidth is the quality parameter. QoS seems to be an important requirement for most ad hoc networking applications and this paper presents one way to achieve that goal. It is also good that CEDAR has been implemented, although for a small network. However, there are a few points of concern: a) There are no results showing the effectiveness of the new broadcast algorithm that is proposed. It seems that the the time to flood the network increases, thereby reducing the responsiveness of the protocol. b) One of the advantages of CEDAR is that most of the state stored at core nodes is local. However, without any non-local state, CEDAR would fail to generate roubust and efficient routes. In non-QoS applications, the links in the core graph would be heavily used. This would drastically reduce the efficiency of the network. On the other hand, maintaining non-local state is an overhead that is not encountered in the other reactive routing schemes(AODV, DSR, etc). c) It seems that CEDAR could fail to provide QoS-specified paths if there is more than one session in progress. So, all the 'n' sessions could be using a single 'high-bandwidth' link: this link would fail to provide the bandwidth guarantees for which it was chosen. This is primarily because no 'dto' packets are sent when a link is used by an application, and also because there is no global knowledge of the use of a link by another application. d) The paper does not mention how the bandwidth of a link is measured. In 802.11 wavelan cards, we know that the bandwidth is adjusted based on the signal strength available(11, 5.5, 2 and 1 Mbps for 802.11b). How is this parameter measured?? Are sufficient unicast messages sent along a link to determine its bandwidth? If so, how long does it take for the badwidth of all links to be determined? Besides, does this mean that continuous overhead packets are sent to determine the bandwidth of links? e) The simulation environment is difficult to understand. There is a maximum of 30 nodes in the network. Bandwidth of nodes is assumed to be a constant(see (d) above). There is only one session in progress at a time. Mobility is not simulated appropriately: it is not only the loss of one link, but usually is accompanied with the formation of a new one. f) The results should have been presented as graphs rather than in tables. Besides, a comparison should have been made with the other routing protocols on the effectiveness. This paper also does not mention what the optimal algorithm is. From samar@ece.cornell.edu Thu Sep 27 11:40:33 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8RFeXo21168 for ; Thu, 27 Sep 2001 11:40:33 -0400 (EDT) Received: from photon (photon.ee.cornell.edu [128.84.239.166]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f8RFeX628584 for ; Thu, 27 Sep 2001 11:40:33 -0400 Date: Thu, 27 Sep 2001 11:49:26 -0400 (EDT) From: Prince Samar X-Sender: samar@photon.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 16 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 16) CEDAR: a Core-Extraction Distributed Ad hoc Routing algorithm CEDAR or Core-Extraction Distributed Routing Algorithm designed to provide QoS routing for dynamic ad hoc networks. It is based on identifying a group of nodes distributedly - called core of the network - which help in providing routes to applications with a minimum bandwidth requirements. It has the distinction of being one of the first few algorithms proposed to provide QoS routing for MANETs. CEDAR is claimed to be robust and adaptive, using only local state for route computation at each core node. CEDAR is composed of three important parts: 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, c) the QoS route computation algorithm. Each node chooses its dominator which is a node with highest degree (number of neighbors) with maximum effective degree (number of nodes which have chosen it as its dominator) from its one-hop neighborhood. MAC level RTS and CTS packets are buffered and the information used by the routing layer to make the broadcast to the core nodes more efficient by dropping duplicate packets before they reach the destination. Increase and decrease waves are used to broadcast the information about increase or decrease of link bandwidth to the core nodes. Decrease waves propagate much faster than increase waves, suppressing state propagation for unstable links. Thus a core node has information about not-so-stable links in its neighborhood and good links over a larger area around it. When a route is needed by a node, a core route is first formed between the dominators of the source and destination either by available information or by core-broadcast. In the next round trip, QoS route computation is carried out by using the information about good links at the core nodes. Comments: - One important issue about CEDAR left untouched by the authors is the possible exhaustion of the core nodes. If the role of core nodes is not frequently switched between nodes, it is quite likely that the core nodes may exhaust their battery power and die out soon. One possible way to rectify this is to take into account another metric - remaining battery power - while electing a dominator in the vicinity. - The authors do not mention if correctness for CEDAR has been shown. Their algorithm for core selection is said to provide good approximations in the "average" (?) case. In fact it is possible that the protocol will perform bad if the link qualities deteriorate (resulting in very less information available) or somehow improve (flooding of link state information) or if the parameters are not tuned to the network conditions. - For ongoing data communication along a route, are bandwidths of the links currently in use documented and reserved? - The simulation results provided are far from adequate. Simulation with more nodes, mobility and averaged out results (instead of snapshots) would have been more insightful. Each route computation is said to require two round trips. Hence some figures about the amount of control traffic generated would have been helpful. - The authors mention that broadcast flooding in MANETs perform badly. A sample result to substantiate their claim and the improvement, if any, by using CEDAR would have been nice. From c.tavoularis@utoronto.ca Thu Sep 27 11:51:32 2001 Return-Path: Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8RFpVo22666 for ; Thu, 27 Sep 2001 11:51:31 -0400 (EDT) Received: from webmail1.ns.utoronto.ca ([128.100.132.24] EHLO webmail1.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 48029]) by bureau6.utcc.utoronto.ca with ESMTP id <238697-12177>; Thu, 27 Sep 2001 11:50:53 -0400 Received: by webmail1.ns.utoronto.ca id <126211-4366>; Thu, 27 Sep 2001 11:50:34 -0400 To: COM S 615 Subject: 615 PAPER 16 Message-ID: <1001605823.3bb34abfc1587@webmail1.ns.utoronto.ca> Date: Thu, 27 Sep 2001 11:50:23 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 This article presents Core-Extraction Distributed Ad hoc Routing (CEDAR) whose goal is to provide quality of service (QoS) routing in small to medium sized ad hoc networks. In this case, QoS is measured in terms of available bandwidth along the chosen route, and CEDAR will choose the shortest-widest path rather than the optimal (shortest) route. CEDAR employs the MAC layer to determine link bandwidth. It relies on a connected set of core nodes with high-bandwidth and (presumably) stability for discovering routes. There are three steps to CEDAR: establishment of core infrastructure; increase/decrease wave propagation of link state such that high BW link states are propagated much further than low BW link states; and the QoS computation, requiring an extra round trip. A core graph is a group of nodes connected via high-bandwidth links such that each core node is 3 hops or less away from at least one other core node. Every node is either a core node, or a first neighbor to a core node. The core is set up as follows: each node periodically broadcasts state information to its immediate neighbors. A node will nominate the neighboring node with the highest degree (most neighbors) and with the maximum effective degree (most elections to be a dominator) to be its dominator (dom). Once a node has been elected as a dominator, it joins the core. Stability is achieved by giving preference to nodes already in the neighborhood. Once joined the core, broadcasts are piggybacked up to layer 3 neighbors, to propagate route knowledge to a local area. The dominator monitors it’s neighbors and breaks all virtual links when it loses it’s dominated nodes. A change in bandwidth greater than a threshold initiates a wave. Slow-moving increase waves keep low bandwidth link state local. Fast-moving decrease waves allow high bandwidth link state to propagate through the network. This is controlled by a time to live field (ttl), which is shorter for bandwidth decrease, and longer for bandwidth increase. Upon receiving a wave, a node will compare the cached bandwidth of the link (if it exists) with the received information, the update the cache. Increase/decrease waves will be added to ito/dto queues respectively. If ttl has timed out, the message is put in the dto queue notifying obsoleteness of the link state. Messages in the queue are propagated, but the queues are flushed periodically to avoid stale routes. Routing is initiated by the source and propagated as a core broadcast, rather than network-wide flooding. This increases QoS, since flooding is unreliable. A tradeoff is that nodes must temporarily cache RTS/CTS packets. The dom(source) will try to locate the dom(destination) along the core path by querying it’s core neighbors. This will propagate through the core nodes while choosing the shortest-widest links to satisfy QoS. If the path is found, a reply is propagated back through the path to the source. Source routing is then employed although this can be modified to hop-by-hop routing. The source will be notified upon the failure of a link the in the path, and it will reinitiate a route discovery. CEDAR was compared in simulation to optimal cases for path length and path bandwidth. Within the scope of the simulation, CEDAR performed well, although simulation was limited. A poor result is that the behavior of CEDAR in mobility situations strongly depends on the location of the failure in the path. This shows that CEDAR is not robust in the presence of mobility, and relies on a relatively stable core. I see a potential problem if the dominator of the source moves while the route is being discovered. The source will most likely timeout after not hearing a routing reply, but the delay will be enormous. A new dominator will have to be found and a repeat attempt on locating route is performed. As a final comment, relying on core nodes for route discovery could quickly deplete the core nodes of energy, making them unstable. From viran@csl.cornell.edu Thu Sep 27 12:49:12 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8RGnBo29471 for ; Thu, 27 Sep 2001 12:49:11 -0400 (EDT) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8RGn6940293 for ; Thu, 27 Sep 2001 12:49:06 -0400 (EDT) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Thu, 27 Sep 2001 12:49:06 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 PAPER 16 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII CEDAR is a routing algorithm to support QoS in ad-hoc networks. It relies on determining a set of "core" nodes (which are a maximum of 3 hops away from each other) that are reasonably stable and provide high bandwidth. All the topology information and routing is handled at the core nodes, which provides a measure of scalability as long as the number of core nodes is a small subset of the total number of nodes. Bandwidth and topology changes are propagated via fast decrease-waves (so that bandwidth reductions are propagated quickly) and slow increase-waves (so that high bandwidth links are ensured to be stable before the QoS routing is changed). Overall, the paper was concise and well-written, and the algorithms were described very clearly. The evaluation section was a little lacking -- I'm not sure why they even mentioned details of their hardware "implementation" when the haven't even given any results for it. I would also like to know what the justification was for picking slow/fast waves, since they haven't mentioned how they determined the best speed. Also I would have liked to have seen more variability in the link bandwidths (rather than the binary selection of low and high) From jcb35@cornell.edu Thu Sep 27 14:51:44 2001 Return-Path: Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8RIpho14873 for ; Thu, 27 Sep 2001 14:51:43 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id OAA01103 for ; Thu, 27 Sep 2001 14:51:40 -0400 (EDT) From: jcb35@cornell.edu Date: Thu, 27 Sep 2001 14:51:40 -0400 (EDT) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 paper 16 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper documented the CEDAR routing algorithm, which tries to tackle the issue of QoS in ad-hoc networks. Cedar uses a self-organizing set of nodes called the "core", which incrementally propagates the link state of stable high bandwidth links to the nodes of the core. Route computation is done on demand, and is performed by the core nodes using local state. Right off, the paper states that very mobile ad--hoc networks face a huge problem in QoS - cedar deals with this by providing routes that are highly likely to satisfy the bandwidth requirements of a route, instead of guaranteeing bandwidth. The algorithm determines these core nodes through a neighborhood decision. Among the core, cedar uses RTS/CTS packets for core broadcasts to limit excess propagation of route probes. For state propagation, cedar uses slow-moving increase-waves to indicate an increase of bandwidth, and fast-moving decrease-waves to indicate a decrease in bandwidth over a link. This idea of sending bad news quickly and good news slowly helps to propagate only stable high-bandwidth link state thorough the core, and keep the low-bandwidth and unstable link state local. Inside the core, any other ad-hoc routing protocol is suitable for use and nodes can route through their neighbor core nodes. The QoS route computation consists of many shortest-widest path decisions among the core nodes. They also offer route maintenance, offering route recomputation at the failure point or the source, depending on where the link error happens in a route. Finally, they implement and simulator cedar and present a performance evaluation. Comments: Isn't there more to QoS than bandwidth? This seems to be the first paper addressing QoS in ad-hoc networks, but I would have like to have seen other problems addressed. They dont show results from the rts/cts algorithm and justify using it in the results section. They claim the algorithms should work for medium sized networks, but their simulation results only have a smaller network. I would like to see what the problems they had implementing the protocol were they dont seem to mention it except that they ran into problems.