From kwalsh@CS.Cornell.EDU Mon Sep 23 22:30:15 2002 Received: from smtp2.usadatanet.net (smtp2.usadatanet.net [208.48.41.42]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8O2UEh05190 for ; Mon, 23 Sep 2002 22:30:14 -0400 (EDT) Received: from localhost (localhost [127.0.0.1]) by smtp2.usadatanet.net (Postfix) with ESMTP id 6521962F78 for ; Mon, 23 Sep 2002 22:29:54 -0400 (EDT) Received: from mail.usadatanet.net (mail.usadatanet.net [208.48.41.252]) by smtp2.usadatanet.net (Postfix) with ESMTP id 6763262F15 for ; Mon, 23 Sep 2002 22:29:49 -0400 (EDT) Received: from home.cs.cornell.edu (unverified [208.178.3.58]) by mail.usadatanet.net (Vircom SMTPRS 5.1.202) with ESMTP id for ; Mon, 23 Sep 2002 22:21:42 -0400 Message-Id: <5.1.1.6.0.20020923212102.00a823b0@mail.flashmail.com> X-Sender: (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 Date: Mon, 23 Sep 2002 21:53:35 -0400 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 19 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Virus-Scanned: by amavisd-new amavisd-new-20020630 X-Razor-id: c26527149d3df8527e81e1ae8359a1b70497db34 CEDAR: a Core-Extraction Distributed Ad hoc Routing algorithm The paper has as a goal to design and present a QoS routing algorithm for ad hoc networks. But, I believe, it falls far short of its goals: the design seems lacking, the presentation poor, and the "ad hoc network" part appears to be an afterthought. On the bright side, I do see some contributions. Among them: - Traditional broadcast is replaced with unicast along a tree structure. Unicast is an order of magnitude more reliable than broadcast in mobile networks, so it is probably the case that their approach is not only more efficient and perhaps faster, but more reliable as well. - Routing updates are classified as either "increases" or "decreases". Each type of message is flooded (using the multicast tree) to the netowork at a different rate, so that "decrease" messages can overtake prior "increase" messages. - An attempt is made to spread routing information a distance proportional to the usefulness of the information: better links are advertised further. Aside from the numerous and typical complaints ("updations" is not really a word, poor evaluation, less than thorough simulation, etc.) are some serious ones: - They appear to use a reservation system, but this is not presented or even mentioned. - The simulation is poorly presented, and as it stands seems downright bizarre. Why is average node degree always a whole number? Why no mobility in the evaluation? Is there a reason for using a square transmission range? And is there really no transmission model, congestion, or collisions, or was that just left unmentioned? - The results, presented in table format, are meaningless to me (perhaps I did not invest the time to understand them properly, though). - As in another paper, the authors attempt to redefine "minimum" to be "what we implemented", when in fact they present no compelling reasons or evidence that their routes will be even close to minimal in realistic settings. Also, a "shortest path" is not defined as the path taken by the fastest message delivery. - In my view, the most glaring and problematic assumption is buried in section V, subsection B: "The bandwidth that can be provided on a path is the minimum of the individual available link bandwidths on the path." In a shared medium, is this really the case? In a path A-B-C where both links are 10mbit, the A-C path will have only 5mbit available, since B must transmit each message twice. Worse, assuming bidirectional flow, it might have as little as 2.5mbit in each direction. From shafat@CS.Cornell.EDU Mon Sep 23 23:11:29 2002 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.10) with ESMTP id g8O3BSh13660 for ; Mon, 23 Sep 2002 23:11:29 -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.5762.3 Subject: 615 PAPER 19 Date: Mon, 23 Sep 2002 23:11:28 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D1507B8@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 19 Thread-Index: AcJjeBMvzECNY63OSb+k1cJbuxAdOQ== From: "Syed Shafat Zaman" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8O3BSh13660 This paper presents a cluster-based routing algorithm called CEDAR, for mobile ad hoc wireless networks. It is tailored, more specifically for QoS routing, and regards bandwidth of links as the most important parameter. The network model comprises of clusters of nodes, each headed by a core node. Path creation and maintenance are carried out by these core nodes, while other nodes only maintain localized information of their neighbors. One aspect of CEDAR that I found quite interesting was the implementation of increase and decrease waves. The difference in the propagation speeds of these two types of waves is a clever idea of ensuring that stale information do not travel too far away from the origin. The paper, however, could talk more about the function that decides on the TTL value of link updates and study its performance in the simulation. The basic QoS routing algorithm is quite simple and straightforward. It minimizes the overhead cost of sharing link-state information. However, the paper does not address the load factor of core nodes and how it affects the network once a core node fails. Power consumption in these core nodes could also be considerably higher than the rest (according to last week's papers), and failure might be very common in reality. Another point noted in the simulation was the maximum number of nodes used - 30. This makes it harder to predict the actual performance of CEDAR in a larger setting. It also undermines the strong characteristics, like robustness, CEDAR displays through the simulations. From ag75@cornell.edu Mon Sep 23 23:12:07 2002 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.10) with ESMTP id g8O3C7h13691 for ; Mon, 23 Sep 2002 23:12:07 -0400 (EDT) Received: from sanya (r105361.resnet.cornell.edu [128.253.240.52]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with SMTP id XAA10227 for ; Mon, 23 Sep 2002 23:12:06 -0400 (EDT) Message-ID: <000901c26378$30c69060$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 19 Date: Mon, 23 Sep 2002 23:12:18 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4910.0300 In this paper the authors present us with CEDAR, a routing algorithm for QoS routing in ad hoc networks. The goal is to provide routes that are very likely to satisfy the bandwidth requirement of a route. In order to do this, CEDAR tries to compute unicast routes that satisfy a minimum bandwidth requirement from the source to the destination. This minimum bandwidth is supposed to be supplied by the application requesting a connection, which might be a problem if you want applications that were not designed specifically for this algorithm to work with it. Some of the assumptions that the authors make are that the paths are bidirectional and that the MAC/link layer can estimate the available link bandwidth. These might or might not be reasonable depending on the network. The authors use a simple constant time algorithm to calculate the minimum dominating set of the core. While it generates good approximations for MDS in the average case, the authors neglect to mention what happens in the worst case. The algorithm deals well with link failures that occur very close to the source or destination, but it fails to react fast enough if the failure is somewhere in the middle and a large number of packets can be lost. It would be interesting to see how much power the core nodes have to spend compared to non-core nodes, if the difference is very big then it would be a problem. Despite its shortcomings, the algorithm does have a lot of positives. The routing computation is performed by core nodes only using only local state, which makes it efficient and scalable. The algorithm also tries to propogate only stable high-bandwidth link-state throughout the core, and keep low-bandwidth and unstable link-state local, which is good for avoiding bottlenecks. Also, the core path provides a simple backup route if the QoS route is not available, which makes the algorithm more reliable. Finally, the authors made an implementation of their algorithm, which is more than what most others have done. Of course, it would be nice to see any kind of results derived from that implementation. From xz56@cornell.edu Mon Sep 23 23:14:33 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8O3EXh14409 for ; Mon, 23 Sep 2002 23:14:33 -0400 (EDT) Received: from XIN (dhcp-ece-167.ece.cornell.edu [132.236.232.167]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id XAA26162 for ; Mon, 23 Sep 2002 23:14:32 -0400 (EDT) Message-ID: <00d101c26378$7f09f6e0$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 19 Date: Mon, 23 Sep 2002 23:14:29 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 There are two main points in this paper: core-based algorithm and QoS (with respect to bandwidth) routing. Cores are elected by neighbors, thus the distance between any two cores is at most 3. It may be done further to enlarge the neighborhood but let the nodes 2 or more hops away elect their dominator, thus further shrink the dominating set. The good point is that the election is local although may not necessarily optimal. The shortcoming is in the case of a -> b -> c -> d with a and d are cores, when b wants to send to c, there will be a detour. But a possible solution here is that, since every node maintains a neighbor table, it should firstly search in its neighbor table for the destination before trying to route the packet through its dominator. QoS routing is achieved by using of increase/decrease wave msg. But there maybe a problem (or a typo) here at the second case sub-case (b) for the handling of increase wave: bw(a, b) in cache should be updated after forwarding is done. The establishment of the core path is kind of a DSR alg. in multi-path version (then the path is chosen to satisfy QoS requirements). So there are problems similar in DSR. Also, the paper didn't mention how the path between neighboring cores are decided and how the dom(d) is found. The use of RTS-CTS to relieve the problem of hidden-exposed terminal problem and the duplicate rebroadcast should be a very good approach. From pj39@cornell.edu Tue Sep 24 00:30:48 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8O4Umh29075 for ; Tue, 24 Sep 2002 00:30:48 -0400 (EDT) Received: from jalan (syr-24-58-49-124.twcny.rr.com [24.58.49.124]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id AAA18621 for ; Tue, 24 Sep 2002 00:30:47 -0400 (EDT) Message-ID: <001001c263e7$3385d800$7c313a18@twcny.rr.com> From: "Piyoosh Jalan" To: Subject: 615 PAPER 19 Date: Tue, 24 Sep 2002 12:26:56 -0400 MIME-Version: 1.0 X-Security: MIME headers sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.132 $Date: 2001-12-05 20:20:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_000D_01C263C5.ABE4C940" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 This is a multi-part message in MIME format. ------=_NextPart_000_000D_01C263C5.ABE4C940 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable CEDAR: a Core-Extraction Distributed Ad hoc Routing Algorithm In this paper CEDAR a QoS routing algorithm for mobile ad hoc networks = is presented. In CEDAR a core of the network is dynamically established = which is a subset of the network. Stable high bandwidth links are = incrementally propogated to the nodes of the core. Each core node is = responsible for mainitaining local topology of the nodes in its domain = and perform route computation on behalf of these nodes. The major goals = acheived in this paper are - The core broadcast which is used for propagation of increase/decrease = waves uses unicast transmission instead of broadcast. As flooding is = lossy which wastes lot of network and battery resources this results in = saving a lot in terms of network resources. - A change in network topology causes a recomputation of the core graph = in the locality of the topology change and hence does not involove = recomputation of the entire core graph. - The use of core based network topology management requires use of few = nodes for state managemen thus minimizing overhead. - Since broadcasts are highly unreliable due to the presence of hidden = and exposed nodes so reliable unicast channels computed by the core = nodes are expected to be more reliable. - Use of increase/decrease waves with different propagation speeds for = establishment of core path in route computation phase. The difference in = propagation speeds of these two type of waves ensures that information = about unstable links are propogated faster. The major weaknesses in the paper are=20 -There is geater load on core nodes as compared to other nodes in its = domain and hence more consumption of battery power. So keeping the chord = nodes up for a long time is a challenge which is not addressed in the = paper.=20 - As all the messages are routed through the core nodes resulting in = narrow links between core nodes other nodes in its domain. The paper = does not much discuss on load balancing. Also some some simulation = results pertaining to this could be provided.=20 - The paper also does not discuss the implications if a core nodes = fails.=20 ------=_NextPart_000_000D_01C263C5.ABE4C940 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
CEDAR: a Core-Extraction Distributed Ad = hoc Routing=20 Algorithm
 
In this paper CEDAR a QoS routing = algorithm for=20 mobile ad hoc networks is presented. In CEDAR a core of the network is=20 dynamically established which is a subset of the network. Stable = high=20 bandwidth links are incrementally propogated to the nodes of the core. = Each core=20 node is responsible for mainitaining local topology of the nodes in its = domain=20 and perform route computation on behalf of these nodes. The major goals = acheived=20 in this paper are
- The core broadcast which is used for propagation = of=20 increase/decrease waves uses unicast transmission instead of broadcast. = As=20 flooding is lossy which wastes lot of network and battery resources this = results=20 in saving a lot in terms of network resources.
- A change in network = topology=20 causes a recomputation of the core graph in the locality of the topology = change=20 and hence does not involove recomputation of the entire core graph.
- = The use=20 of core based network topology management requires use of few nodes = for=20 state managemen thus minimizing overhead.
- Since = broadcasts=20 are highly unreliable due to the presence of hidden and exposed nodes so = reliable unicast channels computed by the core nodes are expected to be = more=20 reliable.
- Use of increase/decrease waves with different propagation = speeds=20 for establishment of core path in route computation phase. The = difference in=20 propagation speeds of these two type of waves ensures that information = about=20 unstable links are propogated faster.
 
The major weaknesses in the paper are =
-There is geater load on core = nodes as=20 compared to other nodes in its domain and hence more consumption of = battery=20 power. So keeping the chord nodes up for a long time is a challenge = which=20 is not addressed in the paper. 
- As all the messages are routed = through the core=20 nodes  resulting in narrow links between core nodes other = nodes=20 in its domain. The paper does not much discuss on load balancing. Also=20 some some simulation results = pertaining to=20 this could be provided.
- The paper also does not discuss the = implications=20 if a core nodes fails.
 
------=_NextPart_000_000D_01C263C5.ABE4C940-- From mr228@cornell.edu Tue Sep 24 00:57:10 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8O4vAh03225 for ; Tue, 24 Sep 2002 00:57:10 -0400 (EDT) Received: from cornell.edu (syr-24-58-48-238.twcny.rr.com [24.58.48.238]) by cornell.edu (8.9.3/8.9.3) with ESMTP id AAA26981 for ; Tue, 24 Sep 2002 00:57:08 -0400 (EDT) Message-ID: <3D8FF0AD.FF813E84@cornell.edu> Date: Tue, 24 Sep 2002 00:57:17 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 19 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper present CEDAR: A Core-Extraction Distributed Routing Algorithm. The primary contribution is an interesting algorithm that can identify "core" hosts and use them to establish a sort of backbone for the network. Each node chooses a "core" or super node from amongst it neighbors to communicate with, and route all packets destined for far away hosts through this core node. This way, non-core nodes need only know about their nearby neighbors and one core. Core nodes communicate amongst themselves via some other routing protocol (DSR, AODV, etc.) Although you could still construct situations where the network diameter is arbitrarily large, this has the nice property of helping to bound the diameter. If everyone chooses a "core" that is within some fixed number of nodes, then the network diameter is proportional to the diameter of the core network. The goal is then to arrive at a minimal set of core nodes such that all nodes in the network have a core with which to communicate. This is an NP-complete task and worse still is that most approximation algorithms require global knowledge of the network to implement. They devise a local knowledge only algorithm to approximately find this minimal set. The algorithm works by each node deciding for itself who amongst its neighbors and itself would make the best core node. This algorithm forms the primary contribution of this paper. Their goal is to optimize for QoS, specifically bandwidth, and their performance analysis is heavily skewed towards it. Although it seems that things like latency aren't adversely affected by their protocol, they don't really mention any of these other performance metrics. Packet loss doesn't seem to be a big issue since nodes broadcast packets (beacons) at regular intervals, however, what may be more of a concern is node failure, specifically failure of a core node. Since they are reducing the networks tolerance for node failures, they should have provided analysis of this problem in the paper. Future work might look at optimizing on other metrics besides bandwidth, specifically latency. Many applications require low latency, but don't have high bandwidth requirements. One might look at how this would work with their proposed protocol. -- Mark Robson From jsy6@postoffice2.mail.cornell.edu Tue Sep 24 00:57:39 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8O4vdh03245 for ; Tue, 24 Sep 2002 00:57:39 -0400 (EDT) Received: from Janet.cornell.edu (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA18367 for ; Tue, 24 Sep 2002 00:57:37 -0400 (EDT) Message-Id: <5.1.0.14.2.20020924001125.00b49590@postoffice2.mail.cornell.edu> X-Sender: jsy6@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 24 Sep 2002 00:57:20 -0400 To: egs@CS.Cornell.EDU From: Janet Suzie Yoon Subject: 615 PAPER 19 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed CEDER is an algorithm for QoS routing in an ad-hoc network. The main goal of CEDER is to compute unicast routes that satisfy the bandwidth requirements with a high probability. An approximation of the minimum dominating connecting set of host in the network (known as the core) performs all the route computation and state propagation. The core, which is established via local elections in constant time, provides a mean to dynamically create and maintain routes efficiently with very little overheard. This is due to the fact that each node in the core is only concerned about local state for route computations. As usual, it is assumed that all links in the network are bidirectional. It is also assumed that the MAC and routing layer are closely coordinated and the two layers can estimate the available bandwidth and the source host can compute the minimum bandwidth needed to communicate to its destination. It was mentioned in the paper that optimality of routes are sacrificed for the ability to efficiently compute good routes. It would be more efficient for nodes to communicate directly with their neighbors instead of via their dominator. It is even more inefficient if two neighboring nodes happen to have different dominators. Also, any node u must periodically broadcast a beacon to aid in core computation and maintenance. These periodic decreases the available bandwidth significantly while also making contention and collision a much greater risk. From mvp9@cornell.edu Tue Sep 24 01:23:25 2002 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.10) with ESMTP id g8O5NPh07674 for ; Tue, 24 Sep 2002 01:23:25 -0400 (EDT) Received: from zoopark.cornell.edu (syr-24-58-46-186.twcny.rr.com [24.58.46.186]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA20723 for ; Tue, 24 Sep 2002 01:23:19 -0400 (EDT) Message-Id: <5.1.0.14.2.20020924012221.01a69bc8@postoffice.mail.cornell.edu> X-Sender: mvp9@postoffice.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 24 Sep 2002 01:23:16 -0400 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 19 Mime-Version: 1.0 Content-Type: text/html; charset="us-ascii" This week’s paper introduces an effective cluster-based protocol, CEDAR.  It’s novelty and contribution lies is in computing good routes using only locally available state, i.e. with minimum overhead, that also satisfy bandwidth requirements imposed from above.  A combination of interesting techniques are used to accomplish this  core graphs, increase/decrease waves, core-limited broadcasts and local state-based routing.  For stable networks it is claimed to approximates link-state algorithms, and good behavior is promised in a dynamic network.  The evaluation in simulation is very promising.
Unlike some of the previously reviewed protocols, there are obviously no extravagant assumptions; at first glance the approach appears very solid.  However, there is a nagging suspicion of some hidden problems.  The ideas of using local state and propagating only the most stable and high bandwidth links is indeed valuable, and the increase/decrease waves present a clever implementation.  The treatment of broadcasts as unicasts on the core graph is also advantageous.  But something is amiss.  Why are the trends in Tables I and II reversed?  how are bandwidth requests propagated? (this isn’t discussed at all, except to say that they are assumed to be instantaneous!)   Finally, how does the whole system perform in a dynamic environment?  The simulation only covers a static environment and the case where 1 link fails.  And even there  in case of link failure, which recovery mechanism is to be chosen?
Aside from these questions that can surely be resolved, CEDAR seems to fulfill many of the goals posited for MANETs in this and other papers.  Simulating it, and preferably implementing CEDAR on larger networks, with mobility would be the first extension of presented work.  Extending QoS to other metrics, delay reliability, etc, would be another.  How useful are various caching optimizations and what improvements could they provide?  Finally, what actual adjustments need to be made for well-behaved scaling, if any?
From hs247@cornell.edu Tue Sep 24 08:21:32 2002 Received: from mailout6-0.nyroc.rr.com (mailout6-0.nyroc.rr.com [24.92.226.125]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OCLVh20410 for ; Tue, 24 Sep 2002 08:21:31 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g8OCLVI14112 for ; Tue, 24 Sep 2002 08:21:31 -0400 (EDT) Message-Id: <5.1.0.14.2.20020924082155.00b7e1f8@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 24 Sep 2002 08:22:08 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 19 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed CEDAR is the first paper we have looked at which is based on clustering. CEDAR tries to established routes based on bandwidth. This is the performance measurement it uses and in this way it is Quality of Service algorithm which tries to satisfy minimum bandwidth requirement of a node. CEDAR has three main parts to it: finding the core graph, propagation of bandwidth information amoung the core, and route computation. One of the goals with having core nodes is to minimise the changes in the network core when topology changes. Changes are only effect local neighbour hoods, and other core nodes do not have to worry about this. CEDAR also has this idea of increase and decrease waves to denote high bandwidth stable links and short unstable low bandwidth links. This is the basis of how CEDAR calculates routes based on bandwidth. The idea is that short decrease waves are only travel far enough to be local within a neighbour hood, and long increase waves are used for links between neighbourhoods. In this way, short unreliable links do not need to be propagated to the whole network, where as more important stable bandwidth information is. There are many ideas in this paper that I like about CEDAR, and it would be interesting to see how this algorithm work in real life. Though they have many tables and results from simulations, they only briefly mention their implementation on Linux. They only briefly mentioned that there were implementation difficulties. What they found on the Linux implementation would have been interesting. Some things research would be to see how having core nodes and effectively a hierarchy effect the other properties of an ad-hoc network. Intuitively, core nodes are used more and require more computation and communication power. This probably means that they can be a bottle neck and their battery power (which we have established is important) can run out quickly. Perhaps the electing of a core node should take into consideration whether the core can handle the work that is required from it. And for practical reasons, one would like to research, does typical ad-hoc network really need this sort of structure? Do ad-hoc networks typically get large enough and stay alive long enough to require a hierarchy structure? From smw17@cornell.edu Tue Sep 24 10:45:23 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OEjNh18553 for ; Tue, 24 Sep 2002 10:45:23 -0400 (EDT) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id KAA24238 for ; Tue, 24 Sep 2002 10:45:22 -0400 (EDT) Message-ID: <3D9079CD.1020008@cornell.edu> Date: Tue, 24 Sep 2002 10:42:21 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4.1) Gecko/20020508 Netscape6/6.2.3 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 19 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit CEDAR CEDAR is an algorithm designed to provide QoS routing for ad-hoc networks. The CEDAR protocol first seeks to build a set of core nodes from the network set such that every member of the core set (the dominators) is elected by the local nodes. Local nodes select a dominator based on the local (no-hop) node with the largest number of neighbors. Once the local dominator is selected, individual dominators establish virtual links by broadcasting the join message out three hops from the originating dominator. Once the core set is established, transmissions are accomplished in a reactive fashion. If necessary, the local dominator first determines a core path to the local dominator of the destination node. The destination dominator replies with an acknowledgement. Once the core path is establshed, the source dominator attempts to find a path meeting the requested bandwidth that transverses the maximum possible distance (furthest dominator region based on the core route path). Within the same distance, the highest bandwidth is chosen. If this route did not reach the destination but did reach an intermediate node, the intermediate node repeats the routing as if it were the source, and catenates the two paths. If no route meeting the desired bandwidth is possible, the connection attempt fails. CEDAR adjusts to dynamic topologies in three ways. The first is the case where a link/node is severed. CEDAR performs both a route recomputation at the failure point to re-route in-flight packets, as well as a source route recomputation (once notification arrives) to re-establish the link. This is intended to provide both long-term and short term re-routing. The second case is the movement or removal of the dominators. Due to the dynamic election of dominators, a node should be able to select or elect a new dominator based on the beacons of other nodes once the failure is detected. The final adjustment is the case where a given link encounters a net increase or decrease in link bandwidth. Upon significant bandwidth changes, nodes will transmit either an ito (increase) or dto (decrease) packet to the local dominator. The node will also set a TTL based on the bandwidth change, restricting the number of hops over which to propagate the information. This helps to localize all but the most stable, high-bandwith links, reducing the communication overhead. In addition, dto packets propagate faster than ito packets, helping to quash dynamic link variations. CEDAR is an interesting protocol. Personally, I like the fact that CEDAR makes use of the actual network structure to simplify system routing. The implementation of the core set in a distributed fashion should permit reasonable scaling, and the limited distribution rate for information strikes an interesting balance in the system, permitting more efficient use of static or pseudo-static links. The simulation results were also interesting, in that they show the protocol's behavior, its evolution over time, and the reaction to failure conditions. They show only limited comparisons to other routing methods in this work, but given that they chose to use their simulation results to better illustrate their work, I can accept that. One downside I see is that the protocol does not consider the effect of dominators on network longevity. Setting up a core set has advantages, but also places an increased load on the core set. Depending on the network application, this additional load may significantly impact network longevity and cause premature node expiration. It also seems (to me) that the addition of some form of naming structure based on the information extracted in selecting dominators could simplify further the issue of routing, especially in the case of a network consisting of a number of stable, high-bandwith nodes in addition to more mobile hosts. From aed13@cornell.edu Tue Sep 24 10:45:37 2002 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.10) with ESMTP id g8OEjbh18564 for ; Tue, 24 Sep 2002 10:45:37 -0400 (EDT) Received: from andyd-laptop.cornell.edu (syr-66-67-66-109.twcny.rr.com [66.67.66.109]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id KAA28950 for ; Tue, 24 Sep 2002 10:45:35 -0400 (EDT) Message-Id: <5.1.0.14.2.20020924101413.023adf78@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 24 Sep 2002 10:45:36 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 Paper19 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper "CEDAR: a Core-Extraction Distributed Ad Hoc Routing algorithm" introduces a new paradigm of Quality of Service(bandwidth) in evaluating wireless area networks. CEDAR defines the optimal route to be shortest-widest-path, while introducing new goals for QoS in wireless ad hoc networks: First, all connections must specify required bandwidth. Second, state propagation(specifically available bandwidth) must be kept to a minimum, high bandwidth link information needs to propagate quickly, low bandwidth does not. Finally, routes most converge towards optimal routes over time, but simplicity and robustness of the algorithm and implementation is more desired then most optimal route. CEDAR establishes the concept of a core-nodes that engage in route discovery and link-state maintenance in order to minimize the overhead and redundancy of involving all nodes. By choosing a dominating set of nodes, CEDAR provides quick access to the routing information for all nodes and reduces local broadcasts. CEDAR develops the concept of QoS by effectively describing the stability and bandwidth of links. CEDAR uses a slow-moving increase bandwidth wave and a faster-moving decrease-bandwidth wave. For un-stable links that go up and down often the faster moving wave dominates, and reports low-bandwidth. Stable links slowly increase in bandwidth. This concept uses the motion of waves to effectively compute the temporal and capacity properties of the links. CEDAR divides routing into 3 components: route establishment, establishing stable route through the core, and re-establishing of failures after topology changes. CEDAR could easily be implemented using the any of the previously discussed routing algorithms on-top of the CEDAR layer gathering bandwidth data, but the authors have chosen to implement their own. CEDAR, unlike most papers to date, does include both a performance evaluation on real hardware and a simulation. The evaluation is quire in-depth but does not provide a base of comparison with algorithms it previously cited. The hw implementation used wireless infared-technology which has widely different properties the 802.11b which has been used in previous papers. From tmroeder@CS.Cornell.EDU Tue Sep 24 10:53:32 2002 Received: from dhcp99-233.cs.cornell.edu (dhcp99-233.cs.cornell.edu [128.84.99.233]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OErWh20247 for ; Tue, 24 Sep 2002 10:53:32 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp99-233.cs.cornell.edu (8.11.6/8.11.6) id g8OErWA30536; Tue, 24 Sep 2002 10:53:32 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15760.31851.947805.355755@dhcp99-233.cs.cornell.edu> Date: Tue, 24 Sep 2002 10:53:31 -0400 To: Emin Gun Sirer Subject: 615 PAPER #19 X-Mailer: VM 7.07 under Emacs 21.2.1 CEDAR seeks to be an algorithm which will allow Quality of Service paths to be quickly discovered and maintained in the network, so that those nodes which need good paths can find and use them, and that the low-bandwidth paths will not be overused. Because of this goal, QoS is the main metric they consider in the paper. They are also setting up a unique core structure which routes packets for all the non-core nodes in their neighborhood. In contrast to some other papers that we have read, I find this paper to be clearly laid out and well-written; I understood quickly and easily most of their points. One point, however, was the complaint about broadcasts: "broadcasts are highly unreliable in ad-hoc networks", which is based on the authors' experience, and is mainly a complaint about the hidden-terminal problem. I agree to a certain extent, but would not that in the wireless medium, even unicasts are broadcast, and so you avoid flooding, at least, but not some inherent hidden-terminal issues. Furthermore, you will not be able to avoid some level of local broadcast to establish the initial topology of the network, as is noted in the paper (they claim that you can use any of the standard routing protocols for the core, all of which use some sort of broadcast, and try to avoid the hidden terminal problem in other ways). Another concern of mine is that the approximation algorithm that they are using to get the MDS of the graph is not proven, in this paper, at least (it might be well know to have this property), to get near the MDS for some definition of near, but is rather simply claimed to do so. Given that their QoS routing depends for its quality on having a good approximation to the MDS, I would have thought it important to address the approximation very carefully. There are at least two parameters which I would also like to see addressed in greater detail. The first is the speed at which the increase waves propagate through the network. It seems to me that the choice of this value will greatly determine the stability of the route calculations. The second is the function used to calculate the ttl sent out for a given link. It is likely that the naive choice of linearity in the available bandwidth is not the optimal choice. Further work could look at these parameters in CEDAR and try to discover how their choice affects the performance and availability of high-bandwidth links. Two other quick points to examine: what happens in very sparse graphs where every node is in the core? Should there be some way to determine that the graph is wonky? ie. what if there are no particularly high-bandwidth links, and everything is fairly bad? There ought to be a way to detect that CEDAR is not going to buy us much and drop to a simpler protocol. From vrg3@cornell.edu Tue Sep 24 11:10:14 2002 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.10) with ESMTP id g8OFAEh23261 for ; Tue, 24 Sep 2002 11:10:14 -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 LAA24131; Tue, 24 Sep 2002 11:10:12 -0400 (EDT) Date: Tue, 24 Sep 2002 11:10:12 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 19 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents CEDAR, a routing algorithm whose main intent is to provide robust and efficient routing with QoS capability, by using a core: a "backbone" subset of all nodes, which form a dominating set. The idea of replacing a broadcast with a series of unicasts along the core is something of an evolution of the clustering solution to the broadcast storm problem we studied in the earlier paper. Like TORA, CEDAR does sacrifice optimality in order to achieve its other goals such as robustness and locality. However, CEDAR's routes do approach optimality as time goes on. The QoS discussion was interesting. There is one major problem that I see, however; the paper claims that "the bandwidth that can be provided on a path is the minumum of the individual available link bandwidths on the path." Without unacceptably high latency, a wireless MANET's paths will have bandwidth less than any of the individual links because a) typically mobile wireless stations have only one radio which can either transmit or receive at any given time, and b) the reception and transmission happen in the same medium. From adam@graphics.cornell.edu Tue Sep 24 11:11:20 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OFBJh23345 for ; Tue, 24 Sep 2002 11:11:19 -0400 (EDT) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id g8OFBA0k082645 for ; Tue, 24 Sep 2002 11:11:14 -0400 (EDT) Date: Tue, 24 Sep 2002 11:03:15 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 paper 19 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII CEDAR is a an algorithm that tries to provide QoS routing in ad hoc networks. The three key components of it are the core, increase/decrease waves, and QoS route computation. The goals of the alg is to have distributed route computation, local state route computation (not global), few nodes in state propogation, nodes only care about routes w/ destinations, stale routes need detection, avoidance, elimination, broadcasts must be avoided, stable routes should converge to optimal routes, backup routes when possible. These lofty goals are somewhat accomplished in CEDAR. The idea behind CEDAR is to build this 'core' which is a dominant set S of the connected graph G. These special nodes that makeup the set S carry the burden of establishing, routing, and managing traffic over the air waves. They are put in place by a self election system, implemented in a slightly clever way. Once the core is established then messages are sent to each nodes dominator in order to be passed across the network. The RTS/CTS system allows the dominant (core) nodes to manage the traffic across the network. Further as more or less bandwidth is available for a node, a message is propogated (as a wave, that dies w/ a TTL bit) through the network by the dominated nodes. Finally the QoS of the system is enforced by the dominants noticing the links go down, and finding a way to reroute (dynamically) to the nodes new location. I think this paper has a bunch of very good ideas. The broadcast storm problem has been adressed, by limiting the alg to have only local broadcasts, there are very few (if any) floods of the entire network (unless the entire network is just one dominant node, in which the network is simply peer-to-peer anyways). The performance evaluation is nice and shows that under at least some conditions CEDAR can perform well. Despite the many good contributions to this paper, I think there are some major problems. It addresses the flooding problem, but it doesn't address the bit about reliability of networks. Ad-hoc needs a fall back system... if one RTS/CTS sequence gets missed, that's a problem. Second I what happens if a dominant node moves? Won't whole chunks of the network get potentially cut off from each other? What about power efficiency? If the dominant node is getting hammered w/ transmissions and work is that "fair"? How long does it take to establish a dominant system? What happens w/ contention and rapid network movement? This alg seems to work for mostly stagnant ad-hoc networks, but not something where people would be moving fast (like on a conference floor). I think that a good next step would be to add some sort of robustness, and allowance for dropped packets in this system. I don't think any ad-hoc network will be able to truly successful w/ out the admittance that there will be loss, potentially lots of it. From liuhz@CS.Cornell.EDU Tue Sep 24 11:12:15 2002 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.10) with ESMTP id g8OFCFh23396 for ; Tue, 24 Sep 2002 11:12:15 -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.5762.3 Subject: 615 PAPER 19 Date: Tue, 24 Sep 2002 11:12:15 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE61D@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 19 Thread-Index: AcJj3MQCyy8pQtYhTcecgq3E0baSKQ== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8OFCFh23396 This paper presents CEDAR, the first cluster-based routing protocol we have seen in this class. In CEDAR, each node nominates one node among all the 1st neighbors as its dominator. The core graph consists of all these dominators. Each core node maintains only local states and some global information pertaining to those stable, high-bandwith links. CEDAR uses increase/decrease waves to propagate link states. Links with different bandwidth initiate waves with different ttl. CEDAR proposes ttl proportional to bandwidth, which guarantees that information about high-bandwidth links can be propagated far away while limits the scale for propagating low-bandwidth link states. Based on these core-extraction and state propagation schemes, it's possible to to use some well known ad hoc routing protocols in the core graph. CEDAR proposes a QoS routing protocol that uses source routing to find a path between the dominators of the source and destination, and then follows this core path as direction to build a source-to-destination path with quality guarantee. CEDAR reacts to link failure very quickly. Once a link fails, the node before this link will initiate a local route recomputation to find a new path to the destination. Meanwhile, it will notify the source node about this failure. Thus the source node will recompute the route to the destination. Good points: 1. CEDAR uses core broadcast instead of flooding. Core broadcast is based on reliable unicast(using RTS-CTS ect.) and can reduce the amount of unnecessary broadcast messages. 2. CEDAR uses different ttl for links with different bandwidth, and lets decrease-wave move faster than increase-wave. Thus low-bandwidth and unstable link-state are kept local while stable high-bandwidth link-state is propagated throughout the core. 3. A backup route is found just as the byproduct of the primary route, thus no overhead is introduced by the backup route. weakness: CEDAR doesn't always find the optimal route. Another problem is about the simulation. Although the paper claims CEDAR is applicable to small to medium networks with tens to hundreds of nodes. The simulation only shows result with at most 30 nodes. I believe when the networks become larger, the optimality will be hurt further. From sc329@cornell.edu Tue Sep 24 11:22:46 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OFMjh25364 for ; Tue, 24 Sep 2002 11:22:45 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA03684 for ; Tue, 24 Sep 2002 11:22:44 -0400 (EDT) Message-Id: <5.1.0.14.2.20020924111837.00b1e308@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 24 Sep 2002 11:22:50 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 19 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth Chadrakumar CEDAR : A Core-Extraction distributed ad-hoc routing algorithm 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 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. 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. Comments: 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. The simulations were weak. They postulate that CEDAR can handle tens to hundreds of nodes, but then proceed to evaluate with 6 nodes. Later, they move to some simulation model [30nodes], but not much details are provided on the real model behind the simulation. The algorithm also assumes bidirectional links. The algorithms are not power-aware. core nodes' batteries would be quickly depleted. Besides, the core nodes get overburdened with packets, and the QoS would slide down. From ks238@cornell.edu Tue Sep 24 11:46:36 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OFkZh29928 for ; Tue, 24 Sep 2002 11:46:35 -0400 (EDT) Received: from ks238.cornell.edu (syr-24-24-18-11.twcny.rr.com [24.24.18.11]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA17349 for ; Tue, 24 Sep 2002 11:46:33 -0400 (EDT) Message-Id: <5.1.0.14.2.20020924114516.01b37930@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 24 Sep 2002 11:46:17 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #19 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper discusses a new routing implementation called CEDAR: a Core-Extraction Distributed Ad hoc Routing Algorithm. One of the primary advantages or feature of CEDAR is that it supports QoS routing, which is the prioritization of applications that are transported through networks, to ensure that "mission critical packets" are sent even in times of network congestion (in this case ad hoc ones). At the heart of the CEDAR Architecture is this notion of nodes communicating solely with "core nodes" that are in the vicinity of them. These core nodes are responsible for the discovery and maintenance of all nodes that are communicating with it. This "dominating set of core nodes" is known as the spine architecture that limits the high costs of memory exhaustion and bandwidth consumption associated with network broadcasts. The next feature is the use of increase and decrease waves (an interesting new method of propagation) through which routes satisfying certain bandwidth thresholds are discovered and maintained in an effort to ensure that the route can support QoS. One of the weaknesses of the CEDAR algorithm is the limitation on the types of network topology that CEDAR can support. First, the authors contend that the protocol can support networks up to hundreds of nodes. Their simulation unfortunately isn't close to that level of scalability. Second, I think that the simulation also needs to address how CEDAR performs in clustered compared to non-clustered networks. Also, I was interested in seeing the amount of memory and power that is conserved with a spine architecture in a less clustered distribution. Also, just reading about power conservation peeks my interest in examining the level of power consumed in a spine architecture, specifically, amongst the "core nodes." This may have some deleterious effects in sustaining larger networks. I think the biggest issue with QoS in general is the level and number of parameters that need to be set in order to ensure that mission critical data is sent. Also, as the network topology changes and more nodes add and some nodes leave the network, these constraints need to be recalculated and maintained which can prove to be difficult and exhaustive. Calculating these constraints (i.e. threshold's for bandwidth) are significant to maintaining a QoS network. From mp98@cornell.edu Tue Sep 24 11:56:28 2002 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.10) with ESMTP id g8OFuSh01769 for ; Tue, 24 Sep 2002 11:56:28 -0400 (EDT) Received: from cornell.edu (dhcp226.libecafe-dhcp.cornell.edu [128.253.117.226]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA24482 for ; Tue, 24 Sep 2002 11:56:28 -0400 (EDT) Date: Tue, 24 Sep 2002 11:56:27 -0400 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 19 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <2F03AA56-CFD6-11D6-8593-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.546) In this paper the authors design an ad-hoc routing algorithm to provide some measure of confidence in bandwidth assurances (Quality of Service). To reduce bandwidth, most topographical updates and bandwidth changes are broadcasted only towards key nodes in the network (those positive increases in bandwidth are advertised globally) a feature which is achieved through the maintenance of a vertex covering subset of the graph (the core). All the nodes in the core maintain total knowledge bandwidth on local links and partial knowledge of high bandwidth on other parts of a network. This paper is notable in that it is the first one we've looked at with QoS assurances, though not guarantees and real elitism in routing decisions (that is, certain nodes are more responsible for it then others). The presence of both simulation and implementation are impressive and while they suffer from all the typical foibles (i.e. there's no real network model to their simulation, their entire algorithm assumes bidirectional links, etc.) it is rigorous in many regards (e.g. one appreciates an explicit section on the effects of link failure). However some omissions are unforgivable: For example, they mention 'time complexity' in their performance measurements, but are actually just measuring seconds this particular case took, which is a measurement contingent to particular circumstances. Also while they say that their algorithm calculates a close to minimum core set, I would like to see a proof of its efficiency (or even a citation). From ashieh@CS.Cornell.EDU Tue Sep 24 11:57:28 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OFvRh01848 for ; Tue, 24 Sep 2002 11:57:28 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8OFvRC24704 for ; Tue, 24 Sep 2002 11:57:27 -0400 (EDT) Date: Tue, 24 Sep 2002 11:57:27 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 19 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The central idea behind CEDAR is the use of a "core" dominating set of nodes to store and propagate routing information. Conceivably, such a set would be smaller and have lower degree than the original graph. A distributed, constant time algorithm is provided for generating an the core, which is used to construct a connected overlay network. Since the degree of this overlay is (supposedly) low, broadcasts may be implemented using unicast without much additional cost. Since the overlay has smaller diameter and fewer nodes, on-demand route discovery has lower cost. Routing information is propagated through the core. Since every node is at most one hop from some core node, each node always has access to some routing information. CEDAR assumes that the probability of bandwidth being available through a link for some path drops as the distance from the link to the endpoints increases; therefore, routing information is propagated a number of hops proportional to the bandwidth of a link. CEDAR also employs asymetric propagation of bandwidth updates in which bandwidth decreases are propagated much faster than increases; this approach reduces bandwidth usage from some outdated information, provides hysteresis against instability, and also conservatively helps QoS reservation (by quickly propagating reservations across the network). * Shortcomings - The paper claims that a RTS/CTS caching scheme at the MAC layer can prevent very many extraneous unicasts during core broadcast (at most one per node, "when nearby nodes are a distance 3 apart"). However, the RTS/CTS exchange only protects against the hidden/exposed node problem for the initiator and receiver; the intermediate node has not protected its own airspace. - There were many problems with the evaluation. Very few datapoints were provided. There is no way to tell how the performance ratio between optimal routing and CEDAR scales with network diameter (in fact, the tested diameters are tiny). It was not clear what the sources of routing failures were in the absence of ito/dto waves. Does this mean that QoS reservations were not propagated as quickly? Also, the authors did not explain where all the lost packets went in the recovery process; the numbers in the column don't add up. Did they get misrouted and ignored? They should have compared the recovery of CEDAR with that of DSR, since both use source routing and support some sort of full route-aware rerouting. * Extensions - All state info is stored in the dominators, which means that the non-dominating nodes have unutilized space. Moreover, dominators are, by nature, hotspots in the network. Perhaps these facts can be used to implement dominator load balancing. - Quantify more precisely the loss due to greedy routing to the furthest possible core node. - The TTL calculation and propagation strategy assumes uniform traffic patterns within a network. The loss of efficiency in the presence of hotspots should be analyzed. Also, an asymetric propagation technique maybe useful for providing back pressure to portions of the network that are hogging bandwidth (for instance, on one particular side of a link) From mtp22@cornell.edu Tue Sep 24 11:59:54 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OFxsh02649 for ; Tue, 24 Sep 2002 11:59:54 -0400 (EDT) Received: from narnia (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA14532 for ; Tue, 24 Sep 2002 11:59:53 -0400 (EDT) Content-Type: text/plain; charset="iso-8859-1" From: Matt Piotrowski Reply-To: mtp22@cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 19 Date: Tue, 24 Sep 2002 11:59:57 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02092411595702.00155@narnia> Content-Transfer-Encoding: 8bit There are three major contributions of this paper. One is a hierarchical routing algorithm for mobile ad hoc networks. This is important because a hierarchical scheme can greatly reduce the effect of broadcasts, and has the potential to scale much better than other schemes. Related to this contribution, is the contribution of an election algorithm for selecting the backbone of an ad hoc network. This is essential to forming the hierarchy used in the routing algorithm presented in this paper, but also is important to other ad hoc systems, such as peer-to-peer networks. The third major contribution is a routing algorithm that is concerned with QoS based on bandwidth. This is important because some applications need bandwidth guarantees and the fact that they are running over an ad hoc network should be transparent to them. A weakness of the paper is the lack of QoS analysis with respect to things such as delay. I know their protocol is based on bandwidth guarantees, but I think that delay is also important to the applications that would want these guarantees because a large bandwidth does not necessarily mean low delay, and so I'd like to see more analysis of this. It would be interesting to see larger simulations of this protocol. I think that in terms of scalability, hierarchical schemes are the most promising of the ones we have seen so far. The authors recommend the protocol for small to medium size networks; however, the work in the paper lays a good foundation for performance in large networks. From egs@CS.Cornell.EDU Tue Sep 24 13:32:22 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8OHWMh20629 for ; Tue, 24 Sep 2002 13:32:22 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id g8OHWMa12895 for egs; Tue, 24 Sep 2002 13:32:22 -0400 (EDT) Date: Tue, 24 Sep 2002 13:32:22 -0400 (EDT) Message-Id: <200209241732.g8OHWMa12895@zinger.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 19 >From linga@CS.Cornell.EDU Tue Sep 24 11:59:20 2002 >Date: Tue, 24 Sep 2002 11:59:19 -0400 (EDT) >From: Prakash Linga >To: Emin Gun Sirer >Subject: PAPER #19 > > > >CEDAR > >The goal of this paper is provide quality of service (QoS) routing in MANET. >Here bandwidth is used as the QoS metric. So the goal is to find a route from >source to destionation satisfying the b/w requirements with high probability, >given that there is one. Concentration here is on coming up with a robust >algorithm which may be way off from the optimal. >Main idea is to work with the core (a dominating set of the network which >approximates the minimum dominating set). Core is formed using only local >computation and local state using constant time (each node does a small amount >of work in parallel.) Each core node performs route computation for the nodes >in its domain and also maintains the local topology. Core broadcast is >achieved using a reliable unicast mechanism while avoiding redundant message >transfers by monitoring RTS/CTS packets. >Only b/w information of stable links is propagated through the core network >(info about dynamic or low b/w links is kept local). This is done using slow- >moving increase waves and fast-moving decrease waves. When the b/w of a link >(ab) changes (increases/decreases beyond a threshold) either node a or b will >inform its dominator about the change and that will propage the change across >the core n/w using increase/decrease waves. The maximum distance a link state >can travel is proportional to the b/w of that link so that a lot of nodes know >about the good links. >QoS routing has three key steps: >-discover the location of destination and establish a ccore path to the same. >-now by finding the shortest-widest furthest admissible path along the core >path and iterating, we find a short stable admissible QoS route from source to >destination. >-in face of link failures or topology changes dynamically reestablish the >routes for ongoing connections. >Performance evaluation: Three main kinds of results: characteristics of the >basic routing algorithm, performance of QoS routing and performance in case of >failures/mobility. >Pros: One of the first to talk about QoS routing in adhoc networks. They give >a list of goals for QoS routing in adhoc networks. Results show the proof of >concept and satisfactory performance numbers. >Cons: Only QoS metric used here is b/w. Other metrics like delay, jitter etc >have not been considered. It is not clear why robustness is much more important >than optimality (finding close to the best possible). Experiment/Simulation >results are not complete; try out with larger number of nodes and more >realistic topologies. Here they state that their goal is robustness and not >optimality. There are many details which need to worked out (like how good an >idea is caching RTS/CTS, how often do we send information about b/w updates, >how does using reliable unicast to simulate core broadcast compare to naive >broadcasting and hoping redundancy would take care of transmission failures or > have some other scheme to take care of failures). Future work would include >addressing the issues discussed above. > > From vivi@CS.Cornell.EDU Tue Sep 24 14:31:14 2002 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.10) with ESMTP id g8OIVDh03086 for ; Tue, 24 Sep 2002 14:31:13 -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.5762.3 Subject: 615paper19 Date: Tue, 24 Sep 2002 14:31:13 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF72@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper19 Thread-Index: AcJj+I+S+oNLblLQSWamwRbX/EzL7g== From: "Vivek Vishnumurthy" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8OIVDh03086 This is the first paper we have seen that talks about a protocol that supports QoS requirements. Such a protocol is essential when a real-time application is being run, and the application needs some minimum guarantee of resources to work. A nice feature of the paper is that at the beginning it lists out the goals of CEDAR and the goals of QoS routing. The protocol does away with broadcasts altogether. It achieves the desired results of a broadcast by first building an underlying Core Node network, and then transmitting unicast messages between these Core nodes. But this means that when a particular Core Node has a large number of neighbors in the core, it has to spend a long time sending messages to these nodes one after the other. (whereas in an equivalent setup where broadcasts are used, a broadcast is achieved with just a single message) The protocol avoids redundant message transmission between Core nodes by caching the RTS/CTS packets that precede a Core message. The paper also describes the concept of "Fast Moving Decrease Waves and Slow Moving Increase Waves" for state propagation. This feature prevents the problems caused by links coming up for a short time and then crashing. Weaknesses: - The period for which the RTS and CTS pkts corresponding to a Core broadcast are cached is not specified. - During the QoS route computation, the protocol tries to build the longest sub-path(that satisfies the Bandwidth requirement) possible along the computed core path. This process might miss out on some possible routes, and the route computation could fail. (Eg: Suppose that this stage builds a path from Source S to an intermediate point T, but T eventually fails to find a required route to Dest D. It is possible that a route with the reqd BW exists from S to D along some other path) - The simulation has been conducted with a maximum of only 20 nodes. Also, in each set of simulations, a maximum of 10 end-to-end connections have been run. This is not substantial enough to analyse the protocol. - When there is a link failure, the protocol attempts both Point of Failure and Source reconfigurations. The Point of Failure reconfiguration is wasteful, because the in-transmit packets that this reconfig tries to get to the dest will, in probability, get there after the deadlines of the packets (The application has a bandwidth requirement, so the pkts have some delay constraints) The work can be improved by running longer simulations over larger networks, and measuring the throughput achieved. Also comparisons can be made with an optimal shortest-Just_Enough algo(that computes the shortest route among all those routes that have at least as much bandwidth as reqd), instead of with an optimal shortest-widest algo. From yao@CS.Cornell.EDU Tue Sep 24 14:51:46 2002 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.10) with ESMTP id g8OIpkh06979 for ; Tue, 24 Sep 2002 14:51:46 -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.5762.3 Subject: 615 PAPER 19 Date: Tue, 24 Sep 2002 14:51:46 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D43024797F1@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 19 Thread-Index: AcJj+25vk2G61NgySRSWDREAs3v2jg== From: "Yong Yao" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8OIpkh06979 The CEDAR paper proposes using only the core, a subset of the nodes in the network, to perform routing. Each node is close to one core node, which is its dominator. Link states are propagated among core nodes to reduce the cost to construct and maintain routes. The communication between two nodes consists of three steps. First, the packet is sent to the dominator of the source, then forwarded to the dominator of the destination. Finally, it is delivered to the destination node from the dominator. CEDAR can also apply to other reactive routing protocols, like AODV,DSR, to increase the scalability of the algorithm. Its cluster-based structure is also useful to many other applications, like leader election, or collaborative signal processing algorithms. The paper also presents a local algorithm to select and maintain the core structure. Only local computation and topology information are involved to establish core nodes. Each core node behaves as the leader of its neighbors, and handles most routing workload. The link state algorithm will try to minimize the length of the path between arbitrary source and destination. The paper has a evaluation part including several experiments to demonstrate the routing algorithm and test its performance under different setup. However, the simulation model is a little simple. The number of nodes is small, and node density is not considered. The workload of the algorithm is not balanced over all nodes. It is reasonable to believe that core nodes are the bottleneck of the whole network, and may consume their battery power soon. How to dynamically switch the roles of core nodes and regular nodes and still keep the network topology relatively static is an interesting research problem. Scalability is another problem I worry while reading the paper. Is it possilbe to create large-size clusters or select higher level core nodes. CEDAR only leaves the routing problem to core nodes. It fails while network size increases. Recent hardware advances have enabled distribution of large scale ad hoc networks in the soon future. An interesting question is how to integrate CEDAR to other routing protocols. Yong