From andre@CS.Cornell.EDU Mon Sep 10 18:22:36 2001 Return-Path: Received: from sundown.cs.cornell.edu (sundown.cs.cornell.edu [128.84.96.20]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8AMMZq19088 for ; Mon, 10 Sep 2001 18:22:35 -0400 (EDT) Received: from khaffy (mail@dhcp99-178.cs.cornell.edu [128.84.99.178]) by sundown.cs.cornell.edu (8.11.3/8.11.3/R-3.5) with ESMTP id f8AMMZC27748 for ; Mon, 10 Sep 2001 18:22:35 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.32 #1 (Debian)) id 15gaLV-0004pC-00 for ; Mon, 10 Sep 2001 18:20:05 -0500 Date: Mon, 10 Sep 2001 18:20:05 -0500 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: Emin Gun Sirer Subject: 615 PAPER 5 Message-ID: <20010910182005.A18538@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.20i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= The Broadcast Storm problem There is a single channel, using CSMA, no collision detection nor any syncronisation. Broadcast done by flooding leads to many redondancies and collisions [Assuming transmissions are not directional (circle of radius r)] This paper suggest methods to improve broadcast. - Probabilistic retransmission (poor results) - Counter Based Scheme (wait a while before retransmitting, if you hear the same message more than C times, don't retransmit it. The optimal value is 3 or 4. - Distance Based Scheme: retranmit if you are far enough. - Location Based Scheme: retranmit it you add a significant part to the aera coverd (need GPS). - Cluster Based System: there are head and gateways which transmit the other members don't. According to their simulations, the best scheme is Location Based. This means you have a GPS in each of the nodes, hope that its precision is good enough. You might not need to be lazy in computations to build the topology of the network since you are already carrying a GPS. Counter Based Scheme is quite good also. Distance Based is rather impractical, you usually figure out the distance by the power of the received signal, which depends linearly on the power of the emetting source (you don't know it), and the square of the invert of the distance. Using a power threshold could be a good way to take into account a heterogenous net. The results are poor because of collisions, but this could easilly be avoided by a random wait, (could be based on the difference of power, and even coupled with a another scheme) Cluster Based give bad results too, but they are not doing it well: they should decide of a unique gatewey to transmit from one cluster to another one. If this cannot be done, a random wait before retransmitting would avoid many of the collisions, and if the nodes were clever enough to know the direction of the received signals, then you would be able to reduce the number of unnessary retransmissions (some gateways would be able to guess that there job has already been executed by another gateway). -- André Allavena From eyh5@cornell.edu Mon Sep 10 18:44:51 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 f8AMioq21339 for ; Mon, 10 Sep 2001 18:44:50 -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 SAA23361 for ; Mon, 10 Sep 2001 18:44:47 -0400 (EDT) From: eyh5@cornell.edu Date: Mon, 10 Sep 2001 18:44:47 -0400 (EDT) X-Sender: eyh5@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper # 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper offers several schemes to address the broadcast storm problem that is inherent in the MANET. The authors of the paper study the MANET from the perspective of improving the efficiency of the broadcasting functionality in the network, as opposed to suggesting new routing algorithms in the previous papers. In fact, the schemes introduced in this paper may well be incorporated into routing algorithms such as AODV, where the exchange of advertising messages and the route-request packets may be handled more efficiently. One of the schemes, location-based, is based on the spatial coverage of a mobile node to determine the appropriateness of having that node rebroadcast the message. It involves more computational complexity than the other schemes proposed, but offers the best performance in terms of reduction in rebroadcasts and average latency. An additional dimension of complexity arises from the suggested use of GPS to locate positions of the mobile nodes in a MANET. This would require further research on the interfacing between the MANET and an external network (e.g., the Iridium satellite constellation). It means that the mobile nodes will not have to rely on themselves to construct the network topology of the MANET. This suggestion may run contradictory to some of the previous proposals, in which the transmission routes are found through the self-discovery of mobile nodes among themselves with the exchange of Hello messages and RREQs and RREPs. Another scheme defines the ad hoc network in terms of smaller clusters, each with a mobile node acting as the cluster head. This scheme tightly controls which nodes can rebroadcast outside their home cluster, therefore defining how far a rebroadcast can traverse in the network. In such a cluster, one or more nodes act as gateways, responsible for communicating with the gateway nodes of neighboring clusters. By defining such clusters, the rebroadcasts are not "leaked" to nodes outside the cluster, and only those gateway nodes can send the broadcasting message to the neighboring clusters to "spread the word." In evaluating the performance of the schemes, the authors define the parameters that may exceed the capabilities today's MANET can provide. For example, the transmission radius of a mobile node is set to be 500 meters. Such a large transmission radius will undoubtedly place stress on the mobile node power consumption and may cause some interference when the nodes are densely populated, which will require some kind of dynamic power control to ensure the nodes operate without interfering or being interfered. From avneesh@csl.cornell.edu Mon Sep 10 21:28:09 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 f8B1S8q05731 for ; Mon, 10 Sep 2001 21:28:08 -0400 (EDT) Content-Class: urn:content-classes:message Subject: 615 PAPER #5 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Mon, 10 Sep 2001 21:32:25 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Message-ID: <97C142C1212ED545B0023A177F5349C4053A62@capricorn.ds.csl.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER #5 Thread-Index: AcE6YZyVkMTm/mzxQJKU+lsEtc1+qQ== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8B1S8q05731 Broadcast Storm Problem in a Mobile Adhoc Network Paper Summary/Critique: This paper concentrates on finding an effective method for reducing redundant re-broadcasts within a wireless network which occur due to floading of messages. The environment used for these studies is that of MANET (mobile adhoc network), which incorporates CSMA on a single common channel. When a broadcats is performed by flooding the message, a mobile host may re-broadcast the message, but this might not be useful since its neighbors might already have the message( through the prev. broadcast). Furthermore, due to highly correlated re-broadcast timing (all nodes may pass their backoff procedures and then send at the same time) , contention as well as collsions occur. CSMA does not help to reduce the collision damage, since there is no detection. With the help of some statistical results, it is shown that re-broadcasts may only provide 41% more coverage on average (for two hosts) which reduces further when a third host is included. Similar analysis on contention shows that with increasing host density, the contention probability also increases. In order to alleviate the problem, five schemes have been proposed. The probabilistic scheme mantain a certain probablity for every node broadcast. The counter based scheme mantains a counter threshold for the number of times the same packet (i.e the rebroadcast is recieved). The Distance based scheme depends upon how close the hosts are, before determining when to broadcast, thus trying to maximize the expected additional coverage (EAC). The location based scheme, tries to determine precise location info of the hosts (using gps), to decide the rebroadcast rate. Finally there is the cluster based scheme, which distributes nodes into clusters with designated 'heads' and 'gateways' for data broadcast. I thought that this last idea was quite novel in this context. Performance simluations yield the best scheme to be location based, but it requires GPS units on each node. The probabilistic scheme has been simulated using a set of values, which have not been formally determined, I am not sure how hard that would have been. The distance based scheme suffers from the fact that rebroadcasts may still be high in number, while the counter based scheme tends to be better as long as the threshold value is correctly taken. Cluster based scheme combined with the location based scheme performs poorly (due to hidden terminal effect) when sparser areas are considered. I think that the paper is quite well written, but since the weight is on the simulation results, some more simulations could have been shown. e.g. How about Hybrid schemes, which the authors insinuate but do not simulate. It would have been interesting to see how the distance based scheme with a counter based heuristic would have performed. Another idea could have been a dynamic switching of schemes in response to node density and other factors. From c.tavoularis@utoronto.ca Mon Sep 10 22:18:43 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 f8B2Igq10333 for ; Mon, 10 Sep 2001 22:18:42 -0400 (EDT) Received: from webmail1.ns.utoronto.ca ([128.100.132.24] EHLO webmail1.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 34934]) by bureau6.utcc.utoronto.ca with ESMTP id <238749-10653>; Mon, 10 Sep 2001 22:18:37 -0400 Received: by webmail1.ns.utoronto.ca id <126209-4365>; Mon, 10 Sep 2001 22:18:23 -0400 To: COM S 615 Subject: 615 PAPER 5 Message-ID: <1000174701.3b9d746d20677@webmail1.ns.utoronto.ca> Date: Mon, 10 Sep 2001 22:18:21 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT User-Agent: IMP/PHP IMAP webmail program 2.2.3 This article addresses the broadcast storm problem experienced in many network environments, particularly in a MANET where communication relies on omni- directional broadcasting. The broadcast storm problem encompasses redundancy of message transmission, channel contention, and packet collision experienced during the rebroadcasting of messages. This article assumes that communication between mobile hosts is done through a common channel with carrier sense multiple access (CSMA) without collision detection. It goes on to prove the significance of redundancy, contention, and collision, employing mathematical models in the first two cases. Five schemes to deal with theses problems are proposed then analyzed through simulation. They are measured for Reachability, Saved Rebroadcast, and Average Latency. The probabilistic scheme allows hosts to rebroadcast with a probability P. The counter-based scheme inhibits rebroadcasting once a message has been heard C times. The distance-based scheme inhibits rebroadcasting of messages received within distance D (measured by signal strength). The location-based scheme uses the exact location information to compare additional coverage (AC) to threshold A. The cluster-based scheme combines location-based with clustering. All variables are varied in simulation to select the optimal value. Location-based has the best overall performance in all measures, but is unique since it requires a GPS system and is more computationally intensive. Counter-based, with C=3, has the best performance without exact location information. Distance- based performed poorly since it was not effective in reducing the number of rebroadcasts. Probabilistic-based scheme has lower latency with sparse hosts, although there is no explanation given for this result. COMMENTS The authors assume CSMA/CA, but the addition of collision detection (CD) would practically handle part of the problem at hand at a lower level. Also, it is not clear if this analysis takes into account the computational overhead involved by using the proposed schemes. This can slow down the propagation of messages, and cause congestion at busy nodes. As for the simulation, the area is once again chosen to be square, which is not a realistic assumption. Simulations are performed with an arrival rate of one broadcast per second. This is not rigorous enough to properly simulate the broadcast storm effect in a MANET. In the case of a 5x5 area, additional testing was performed and results significantly deteriorated with greater load conditions (up to 100 broadcasts per second). More simulation results should have been included for complete analysis. From wbell@CS.Cornell.EDU Mon Sep 10 23:16:55 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 f8B3Gtq16291 for ; Mon, 10 Sep 2001 23:16:55 -0400 (EDT) Received: from [192.168.1.100] (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 XAA21473 for ; Mon, 10 Sep 2001 23:16:53 -0400 (EDT) Subject: 615 PAPER #5 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.13.99+cvs.2001.09.08.07.08 (Preview Release) Date: 10 Sep 2001 23:16:35 -0400 Message-Id: <1000178220.10627.27.camel@brute> Mime-Version: 1.0 5) The Broadcast Storm Problem in a Mobile Ad Hoc Network This paper introduces a problem with networks that depend on broadcasts for communication and connectivity, which they dub the "Broadcast Storm" problem. The Broadcast Storm problem is that when a single node broadcasts a message to neighboring nodes, they will usually rebroadcast it [or a modified version], which in densely packed networks, will cause collisions and reduce network bandwidth. The key observation in the paper is that most rebroadcasts are redundant, and don't actually add much additional coverage to the network if hosts are close together. So the proposal to solve the Broadcast Storm problem is to trade reachability for effective bandwidth utilization by limiting rebroadcasts which probably will not add additional reachability to the network. They present several mechanisms to limit rebroadcasts using probabilistic rebroadcasts, counters, distance information, location information, and clustering. Their insight into the additional coverage of the network by additional rebroadcasts was interesting, and a useful observation in order to solve this problem, although I would have liked a worst case estimate on the amount of coverage that is lost in the network by limiting rebroadcasts of k hosts. This I see is the fundamental trade off, and since we're limiting coverage to effectively increase bandwidth, lower latency times, and lessen power consumption, I'd be interested in an evaluation as to how much coverage we could be losing in a worst case scenario. As much as they touted the results from the clustering based scheme, I was much more intrigued by the results from the counter based scheme, which seemed to not only be simple, but yield good results. However, I was skeptical of the simulation as it was geared towards incredibly dense networks in all cases [100 hosts in a 1x1 square means every broadcast hits almost every host.] They presented a nice discussion of a problem that needs to have some solution in a real ad hoc network environment, and pushed forth some good solutions. This paper probably generated a lot of subsequent work, having laid the groundwork well. Hybrid mechanisms where rebroadcasting is limited in densely packed areas would be an interesting thing to look at, because in densely packed cliques, you desire bandwidth utilization, but in sparse graphs, you value connectivity. From daehyun@csl.cornell.edu Tue Sep 11 00:01:30 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 f8B41Uq20280 for ; Tue, 11 Sep 2001 00:01:30 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id AAA14689 for egs@cs.cornell.edu; Tue, 11 Sep 2001 00:01:24 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109110401.AAA14689@wilkes.csl.cornell.edu> Subject: 615 PAPER 5 To: egs@CS.Cornell.EDU Date: Tue, 11 Sep 2001 00:01:24 -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 shows the 'Broadcast Storm' problem by analyses and simulations, And proposes several techniques to alleviate the problem. This paper shows that blind flooding causes Broadcast Storm. Three problems are presented. 1. Redundant Rebroadcasts: This paper shows that efficiency of rebroadcast for two hosts case is between 0% and 61% (average 41%), and as the number of hosts increases the efficiency goes down almost to 0%. 2. Contention: This paper shows that the contention probability for two hosts case is 59%, and as the host density increases the probability also increases quickly. 3. Collision: This paper explains that the collision in wireless ad hoc network is much more problematic than in other cases. This paper propose several methods to alleviate Broadcast Storm. General idea is to inhibit some hosts from rebroadcasting. But depending on the specific implementation 5 schemes are proposed. 1. Probabilistic Scheme: A host rebroadcasts with probability P. 2. Counter-based Scheme: A host rebroadcasts only if it hears the same broadcast messages less than C times. 3. Distance-based Scheme: A host rebroadcasts only if its distance to another host is bigger than D. 4. Location-based Scheme: A host rebroadcasts only if its additional coverage is bigger than A. 5. Cluster-based Scheme: A host rebroadcasts only if it is a cluster head or a gateway. Main contribution of this paper is to identify the Broadcast Storm problem and propose schemes to solve it. Generally, I think that this paper is well structured and the ideas are also very good. My comments are as follows; 1. Among 5 schemes, cluster-based scheme looks most powerful, though its reachability is a problem for the sparse network. I think a good cluster formation algorithm will solve this problem, which might be a future work. But it seems really hard especially for wireless add hoc network. 2. Every scheme proposed has a threshold and there is no one fixed number which shows optimal performance for every possible network parameter. So, I think it might be good to adjust the threshold dynamically, based on the network status. This might be a interesting future work too. 3. Contention and collision happens because many hosts share the same communication medium. I think CDMA technique might be helpful. If the channel is divided into several sub-channels and hosts choose channels probabilistically, then contention and collision can be alleviated. TDMA might be hard to use because of synchronization. I heard this kind of research is on-going. 4. This paper assumed no collision detection (CD). But I'm not sure if this is practical. Though I might be wrong due to my limited knowledge in this area, I think CD will be definitely helpful for collision. Is there any specific reason that CD can not be used in wireless ad hoc network? From papadp@ee.cornell.edu Tue Sep 11 01:06:22 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 f8B56Mq28891 for ; Tue, 11 Sep 2001 01:06:22 -0400 (EDT) Received: from photon (photon.ee.cornell.edu [128.84.239.166]) by memphis.ece.cornell.edu (8.11.2/8.11.2) with ESMTP id f8B56LN10084 for ; Tue, 11 Sep 2001 01:06:21 -0400 Date: Tue, 11 Sep 2001 01:13:59 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-Sender: papadp@photon To: Emin Gun Sirer Subject: 615 PAPER 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "The Broadcast Storm Problem in a Mobile Ad Hoc Network," By S. Yao, Y.C. Tseng, Y.S. Chen, and J.P. Sheu Panagiotis Papadimitratos papadp@ee.cornell.edu 09/11/01 Different facets of broadcasting are related to mobile ad hoc networking (MANET). On one hand, due to the use of omni-directional antennas and a shared channel, transmissions are received potentially by all nodes within range. On the other hand, broadcasting, i.e., the propagation of a packet to virtually all nodes via successive transmissions by receiving nodes to all of their neighbors (flooding) can be a plausible communication option for dynamically changing, multihop topologies. The propagation of route request packets during the route discovery phase, network services such as paging, or even regular IP-broadcasting can be such examples. Nevertheless, the broadcast nature of each individual transmission may render flooding very inefficient. This is exactly the problem discussed by the authors; a simplified analysis illustrates the problem, and simulation study probes further. Once the context is set, five alternative schemes that aim at mitigating the pertinent inefficiencies are proposed, followed by their simulation-based evaluation. Although the assumed medium access control protocol (IEEE 802.11) provides carrier sense and collision avoidance capabilities (CSMA/CA), the pursued broadcast operation does not allow the use of Request to Send/Clear to Send communication that would result in some form of local transmission scheduling. Consequently, (re) broadcasting nodes have to contend and possibly collide with others within their transmission range, especially because of the temporal correlation of such attempts. In addition, spatially overlapping transmission ranges result in redundant, multiply received copies of the same packet from different neighbors. Under an idealized model, with transmission range defined by a radius r, and links established between any two nodes at a 2-D Euclidean distance less than r, the authors provide insight to the causes of the broadcasting inefficiencies. The average additional coverage provided by a single re- retransmission is 41% of the pi*r^2 area, with this percentage falling to a contribution of 5% by the 4-th retransmission. Implying a uniform distribution of the nodes within the network coverage area, the probability of contention among n receivers is approximated and numerical results indicate it is most probable that most of the n nodes' broadcasts would subsequently collide. The proposed solutions are: i. A gossip-like broadcast, based on a probability P that determines the behavior of each receiving node, i.e., it re-transmits with probability P. ii. A counter-based scheme, which increments a counter, while the broadcast message is queued or backlogged, each time the same message is received. If a number (e.g., 4, if the above-mentioned numerical result is used) of receptions occur, the message is discarded, since the expected coverage contribution is low. iii. Similarly, the expected additional coverage is proportional to the transmitter-receiver geographical distance, and the receiver (which keeps track of the minimum (estimated) distance to the transmitter, for the same message) can infer the effectiveness of a retransmission. This is the distance-based scheme, which is essentially a signal strength based scheme; the node backs off for a random period of time and aborts the re-transmission if the minimum distance is below a threshold. iv. A GPS-based scheme assumes that for each reception, the transmitter location is known to the receiver. A node that delays its re-broadcast for a random period of time decides, by determining whether it lies within the convex polygon formed by the set of relevant locations. If so, it aborts, since it is conjectured that the additional coverage will not exceed a small percentage. v.Finally, under the assumption of a (apparently, single-hop) clustering scheme, it is proposed that only cluster heads or gateways relay broadcast messages, employing one of i.- iv. The simulation-based evaluation of the proposed schemes measures the % of re-transmissions that where not performed (SRB), the % of nodes that actually received the message (RE) and the corresponding latency. The scenarios generate topologies, ranging from a practically fully connected network to a 'sparse' one with an average number of 3.14 neighbors, out of a total of 100. The results suggest that SRB may be traded for reachability and that more complete location information allows a combined improvement. Moreover, it is not easy to verify whether a scheme outperforms the rest of the candidates under all circumstances. More importantly, the gains achieved by one scheme are not juxtaposed to the incurred costs. Similarly, there is no evaluation of the complexity and cost of the different schemes, which can vary and be attributed to various factors, e.g., additional required hardware, and processing and transmission overhead. In conclusion, the paper deals with an important issue related to the MANET paradigm and presents a set of potential solutions. It does not provide, though, a set of rules of thumb that would indicate how to make a choice under specific conditions, and ignores a handful of parameters (e.g., radio propagation, realistic MAC implementation, specific applications using flooding) that would probably affect the practicability of the schemes, in a more realistic setting than the one used for the simulation. From teifel@csl.cornell.edu Tue Sep 11 02:30:28 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 f8B6URq06917 for ; Tue, 11 Sep 2001 02:30:27 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8B6ULr90401 for ; Tue, 11 Sep 2001 02:30:21 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 11 Sep 2001 02:30:21 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 5 Message-ID: <20010911022822.E37347-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII MANET: This paper is an analysis of the broadcast storm problem in mobile ad hoc networks and an examination of the potential solutions. The broadcast problem occurs in wireless systems when multiple nearby nodes try to broadcast at the same time, causing redundancy, contention, and collision. They presented solid analytical explanations for the above three problems caused by flooding in broadcast communication. This paper proposed five possible solutions to the flooding problem: probabilistic, counter-based, distance-based, location-based, and cluster-based schemes. Of the five, only the location-based and cluster-based schemes are ones that are new and/or non-trivial. First, I don't really consider the location-based scheme (using GPS) to be a true ad hoc network because since you are already giving up a decentralized network (via GPS)-- you may as well piggy-back a full directory table along with the GPS communication and keep an updated table of all the nodes at some base station. The cluster-based scheme, I think is more promising for real ad hoc networks, even though they say it has reachability issues for sparse networks. Overall, this paper was very well organized and presented. However, its content was somewhat weak in terms of real results. Some of their simulation choices were questionable, for instance why did they choose not to have any collision detection on their CSMA channels (I am not sure, maybe this is standard). Some of their conclusions seem blately obvious, as if they didn't really understand their own results.... such as "Interestingly, a MANET with sparse hosts tend to complete broadcasting in a faster speed than one with denser hosts." (p.157). There is no explanation as to why, even though at least to me it is intuitive that denser hosts would have more contention and collisions slowing the system (if this is true and intuitive, why then is it "interesting"). This paper seemed like it was one of those papers that just had to be written in order to make the literature complete, but didn't really add anything to the field. From haom@csl.cornell.edu Tue Sep 11 10:38:24 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 f8BEcOq24230 for ; Tue, 11 Sep 2001 10:38:24 -0400 (EDT) Received: from localhost (haom@localhost) by mauchly.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id KAA04503 for ; Tue, 11 Sep 2001 10:38:19 -0400 (EDT) (envelope-from haom@mauchly.csl.cornell.edu) X-Authentication-Warning: mauchly.csl.cornell.edu: haom owned process doing -bs Date: Tue, 11 Sep 2001 10:38:19 -0400 (EDT) From: Ming Hao To: egs@CS.Cornell.EDU Subject: 615 PAPER 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The broadcast storm problem in a mobile ad hoc network. this paper explains the redundant transimission and contentions caused by broadcasting in ad hoc network and proposes 5 solutions. the simulation results is reasonable. the analysis of the problems are solid. it presents in theory incremental coverage decreases exponentially with the increase of number of transmission. they also explained that chances of contention increase sharply with the number of nodes. as for collision, their expaination is realtively simple, but understandable. but if nodes can recognize the broadcasting msg and be forced to back off for a random number even the media is not busy, the collision will be alleviated. i think the three problems stem from one problem: redundant broadcasting. so the kernel point of those solutions are trying to reduce unnecessary broadcasting as much as possible. the first three solutions comes directly from the analysis of coverage vs. transmission times. if host decides its broadcasting will not cover more enough new area, it gives up. location based solution needs location info. in fact, it can also help to route. cluster based solution directly takes advantage of topology of ad hoc network. but it is more complicated and cluster configuration keeps changing. the metrics, RE, SRB and Latency are choosed smartly as they expose the both good and bad sides of the solutions. the explaination of results is complete and reasonable. the contribution of this paper is to summarize and analize the well known problems already with a little math so that it is more logic and convincing. it also presents several priliminary solutions. but all of them has draw backs. -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 clint@csl.cornell.edu Tue Sep 11 10:53:01 2001 Return-Path: Received: from eckert.csl.cornell.edu (eckert.csl.cornell.edu [132.236.71.67]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8BEr1q25671 for ; Tue, 11 Sep 2001 10:53:01 -0400 (EDT) Received: from localhost (clint@localhost) by eckert.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id KAA38124 for ; Tue, 11 Sep 2001 10:52:56 -0400 (EDT) (envelope-from clint@eckert.csl.cornell.edu) X-Authentication-Warning: eckert.csl.cornell.edu: clint owned process doing -bs Date: Tue, 11 Sep 2001 10:52:56 -0400 (EDT) From: Clint Kelly To: egs@CS.Cornell.EDU Subject: 615 PAPER #5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper's main contribution is an analysis of several simple and easy-to-implement methods for solving the broadcast storm problem in MANETs. I thought the authors did a good job of explaining the problem and the motivations behind the various solutions. I also thought it was good that none of the schemes required any big changes to the MAC or anything like that (i.e. they all fit in with 802.11 well). My main problem with this paper is that the graphs in section 4 are INCREDIBLY ugly and (I thought) hard to understand. I thought overalying a bar graph and a line graph together was a very poor choice. I also thought it would have been nice to see some simulations that studied how well the different solutions scaled with more nodes, but I supposed squeezing the 100 nodes in their simulations into smaller sized maps is sort of the same thing. Finally, it might've been interesting to see how adding these broadcast-avoidance technques could improve the performance of something else, such as a routing protocol. Overall, I thought this paper was pretty good. From gupta@CS.Cornell.EDU Tue Sep 11 10:53:10 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 f8BEr9q25676 for ; Tue, 11 Sep 2001 10:53:09 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 5 Date: Tue, 11 Sep 2001 10:53:09 -0400 Message-ID: <404A3A4758DDCC4C8A5C9A537384F9D61BB806@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 5 Thread-Index: AcE60W8j0NL+L6I5EdW1ugCgydyP2Q== From: "Indranil Gupta" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8BEr9q25676 -----START------- The broadcast storm problem in a mobile ad hoc network; Ni, Tseng, Chen and Sheu. Reviewer: Indranil Gupta Summary; The authors describe the broadcast storm problem arising out of blindly flooding broadcasts in an ad-hoc network. Multiple rebroadcasts of the same broadcast message lead to 1) channel contention due to simultaneous rebroadcasts by neighboring nodes, and 2) each node receiving multiple copies of the same broadcast message. The inapplicability of the RTS-CTS dialogue and the lack of acknowledgments make this problem unique to the ad-hoc network broadcast scenario. The problem arises as broadcast is used by all ad-hoc routing protocols, proactive or reactive, to disseminate updates or route requests. Mathematical analysis shows that a rebroadcast can provide at most 61 % additional coverage, and only 41 % on the average. The authors solve the problem (1) above by having each node back off a random time before rebroadcasting the received message, as well as avoid rebroadcasting the same message twice by duplicate detection (sender-based sequence number). Orthogonally, they propose several solutions to the problem (2) above: a) probabilistic: each node rebroadcasts only with some probability; b) counter-based: at rebroadcasting time, the node aborts if it has received K copies of the message; c) distance-based: each node rebroadcasts only if the marginal coverage area (calculated form the distance of neighboring nodes that have broadcast this message earlier) is above some threshold; d) location based scheme: similar to (c), but using the GPS-based neighbor node coordinates; e) cluster-based scheme: a two-level scheme using one broadcast within each cluster, and one of strategies (a)-(d) among cluster heads. The authors compare the different approaches using a custom discrete-event simulator that runs a simplified version of IEEE 801.11 (CSMA/CA). The results reveal that there is a tradeoff between reliability (% of nodes reached) and saved rebroadcasts and broadcast latency, depending on individual algorithm parameters and node density. When the application desires a 100 % broadcast reliability, the cluster-based technique saves the most rebroadcasts at low node densities, but suffers from reliability loss (40 % reliability) at lower densities. At low node densities and high reliability requirements, all algorithms save practically no rebroadcasts, so flooding is the best technique. When a moderate reliability is desired ( > 80 %), the location-based scheme saves the most rebroadcasts at high densities, and the distance -based scheme does (slightly) better at higher densities. The authors conclude that the location-based scheme is the best choice, even under varying broadcast injection rate. Comments: - The authors use a signal/r^d estimator to measure distance to a neighbor in the distance-based scheme. In reality, distance measurement is more difficult, as the r^d law is often violated due to multipath fading and other interference. - Some protocols could potentially live with a broadcast delivered to about 90 % of the nodes. What might matter under such imperfect reliability, for these protocols, is the *distribution* of nodes receiving the broadcast, eg., for AODV, it would be preferable to have the recipients distributed uniformly over the entire network rather than clustered closer to the broadcast origin node. Has this characteristic of the different protocols presented by the author been studied ? - An adaptive scheme that switches between different protocols based on node density, could potentially obtain the best of all worlds. The density measurement and protocol selection need not involve any global agreement, but could be a local decision (even at an individual node). Has this been studied ? - In a real ad-hoc network, the node density might vary from place to place and time to time, eg., in a university with PDA-equipped students, densities tend to be concentrated in classrooms, but in a particular classroom only during class-times. As such, the performance of all the presented protocols might degrade even further (worst of all worlds). Have such circumstances been studied ? - A (local-) density based adaptive scheme might, however, perform very well under the circumstances outlined above..... - The node density in an ad-hoc network can actually be varied by varying the transmission power of the transceiver. This has been used by Li Li et al (2001, Cornell Univ.) to solve the broadcast storm problem. How does this compare to the schemes presented by the authors ? - The authors do not seem to measure the overhead of maintaining clusters in the cluster-based scheme. This can add significant overhead, especially under high (local) mobility conditions. ----END---- From ranveer@CS.Cornell.EDU Tue Sep 11 10:59:00 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 f8BEx0q26521 for ; Tue, 11 Sep 2001 10:59:00 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 5 Date: Tue, 11 Sep 2001 10:58:59 -0400 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 5 Thread-Index: AcE60knEhJ9qY9kaRremIq5AV+SPtw== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id f8BEx0q26521 The Broadcast Storm Problem In a Mobile Ad Hoc Network This paper highlights a very important phenomenon in ad hoc networks. Broadcasts are extremely expensive because of the absence of collision detection. Besides, there can be no RTS/CTS technique as is used by 802.11 for unicasts. So, the broadcasts are an overhead because of: redundant broadcasts, contention and collision. The authors then present some of their schemes to prevent redundant broadcasts and also avoid collision. The main contribution of this paper is in bringing to the forefront the overhead of broadcasts in MANETS. A number of protocols designed for such networks assume the success of broadcasts without much overhead, eg. RREQs in AODV, DSR and other protocols. This paper deals with another important point: to reduce the number of redundant broadcasts. This is extremely helpful for improving battery life. As has been shown in a number of research papers, any reduction in communication has a significant impact on the battery power of a wireless node. However, the analysis of the paper has a few shortcomings. It assumes that all the nodes have the same transmission power. So the analysis is not true for networks with unidirectional links, or even with heterogeneous transmission powers. Besides, it seems as the authors missed out on an important point in the paper: that flooding moves through the network in a cascading fashion. So, even though you may have covered only one more node through your broadcast, it could have been extremely important for the flood to reach all the nodes downstream of this one(and this may be large). It is because of this reason that the probabilistic scheme gives bad performance in sparse networks. The counter scheme is much better than the probabilistic approach as is shown in the graphs. However, subsequent approaches tend to assume much more knowledge, such as distance and location information, which might not always be practical. Besides, there was some ambiguity in the simulation parameters. For example, nothing was mentioned about the node placement: where it was uniform or random or something else. I also could not understand why such a big broadcast packet size was chosen. Sending big broadcast packets is always a bad idea because collision detection is not supported. This paper is very interesting, and a study of some more ideas would be extremely helpful. For example, the overhead of broadcasts in a heterogeneous environment would be interesting. The probabilities of retransmission could be made dependent on the transmission range of the node. So, a node with a relatively higher transmission power would have a higher coverage and so should have a higher probability of rebroadcast as compared to another node with a lower transmission range. Another interesting future work could focus on power conservation using the approach of the paper: avoiding redundant communication. From viran@csl.cornell.edu Tue Sep 11 11:06:15 2001 Return-Path: Received: from cray.csl.cornell.edu (cray.csl.cornell.edu [132.236.71.70]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8BF6Eq27165 for ; Tue, 11 Sep 2001 11:06:14 -0400 (EDT) Received: from localhost (viran@localhost) by cray.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id LAA99940 for ; Tue, 11 Sep 2001 11:06:09 -0400 (EDT) (envelope-from viran@cray.csl.cornell.edu) X-Authentication-Warning: cray.csl.cornell.edu: viran owned process doing -bs Date: Tue, 11 Sep 2001 11:06:09 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Broadcast Storm Problem in a Mobile Ad Hoc Network This paper attempts to analyze the problems arising due to broadcasting in ad-hoc networks. Five possible schemes to reduce problems such as redundant broadcasts, contention, and collision are presented: 1. Probabilistic where a packet is rebroadcast with an arbitrarily set probability. 2. Counter-based where a messages that are received more times than a certain threshold are dropped. 3. Distance-based where a packet is dropped if the receiver is too close to the sender. 4. Location-based where GPS receivers are used to determine the position of the senders and drop packets if there's no additional area coverage (basically a refinement of 3) 5. Cluster-based schemes, where a combination of the above methods are used at the gateway nodes between clusters. The different schemes were simulated in the paper with a square map containing a fairly large number of hosts (100). However, their attempts at comparing the algorithms seem to be rather high-level and simplistic. For example, no mention is made if the hosts were in fact mobile -- it seems as if the hosts were scattered about, but they did not mention any kind of movement algorithm. The links appear to have no error modelling or failure rate. Also, the coverage calculations are quite simplistic (although one has to give credit for providing an analytical approximation) since hosts appear to be very homogenous, with identical broadcasting radii assumed. In a real environment the signalling strengths will be varied, there may be obstacles which reduces the coverage area, etc. The GPS scheme did not use any modelling for the uncertainty in the coordinates. A side-point to bring up is that the location-based scheme which is presented as the best solution (which uses GPS) brings up serious privacy concerns if it's used in an civilian network. All in all, this was a rather interesting paper, which presented an overview on methods to make broadcast messages more palatable. The simulation methodology may have been rather simple, but it does lay the framework for more extensive studies. From ramasv@CS.Cornell.EDU Tue Sep 11 11:54:39 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 f8BFsdq03558 for ; Tue, 11 Sep 2001 11:54:39 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 5 Date: Tue, 11 Sep 2001 11:54:39 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F269@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 5 Thread-Index: AcE62b0UIWtjCpUTEdWTbQCQJ5m7oA== 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 f8BFsdq03558 The Broadcast Storm Problem in a Mobile Ad Hoc Network This 1999 MOBICOM paper is simulation based study of a very important problem of broadcasting in ad hoc networks. This paper analyzes the efficiency (redundancy) and reliability (reachability) aspects of boradcasting and the side effects such as increased contention, congestion caused by repeated broadcasts. The mathematical analysis in this paper provides an intuition into the problems associated with broadcasting. They also propose several methods of alleviating this problem and justify their suggestions by simulations. One of the interesting schemes proposed in this paper is the probablistic broadcast that has close resemblence to the Gossip Protocols studied at Cornell. The problem with this method is that the probablity of rebroadcast depends on the density of nodes and this information varies both spatially and temporally and also is often not available to the participating nodes. However, this could be combined with other methods suggested in this paper. For ex, the probablity could be a function that depends on the number of copies received until now. An comprehensive analysis of this scheme has been performed by Lili at this department. The most effective of the flat schemes described in this paper is the counter-based scheme. Although it is difficult to choose a particular threshold, the graphs in the paper suggest that a threshold of 4 is quite safe for several topologies. But the savings in rebraodcasts is significant only in dense networks. The distance based scheme dicussed in this paper depends on measuring accurate distance between nodes. Using signal strngth to estimate distance would only work in free space environments and hence may not be always useful. Further thresholds are chosen based on a simplistic analysis that only holds for specific environments. Not surprisingly the simulation results also do not encourage the use of this scheme. A location based scheme may be used if all the nodes have a GPS device. However, with a GPS available it may be more efficient to maintain a broadcast sub-structure (tree, mesh). The cluster-based technique has close resemblence to the zones of ZRP. While ZRP uses a clever method called border-casting to reduce the bad effects of broadcasting, the protocol described in this paper does not take advantage of this. The efficacy of this technique depends heavily on connectivity of the clusters and node density. A simple technique commonly used to alleviate some of the contention problem is to apply broadcast jitter i.e., rebroadcast after a small random amount of wait time. It is not clear whether the authors have incorporated this into their simulations. The latency graphs for the flat schemes show an increase in average latency as the threshold is increased (especially in dense network). Explanations for this observation is only hinted but not emphasized. On the whole a thorough analysis of problems due to broadcast in ad hoc networks definitely provides useful information to the community. From samar@ece.cornell.edu Tue Sep 11 12:22:19 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 f8BGMIq06805 for ; Tue, 11 Sep 2001 12:22:18 -0400 (EDT) Received: from ockham.ee.cornell.edu (ockham.ee.cornell.edu [128.84.236.58]) by memphis.ece.cornell.edu (8.11.2/8.11.2) with ESMTP id f8BGMIN21263 for ; Tue, 11 Sep 2001 12:22:18 -0400 Date: Tue, 11 Sep 2001 12:22:18 -0400 (EDT) From: Prince Samar X-Sender: samar@ockham.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 5) The Broadcast Storm Problem in Mobile Ad hoc Network In a mobile ad hoc network, broadcasting is frequently used to accomplish a variety of tasks. This paper identifies, analyses and proposes solution for a problem - the broadcast storm problem - associated with broadcasting information via flooding to all nodes in a mobile ad hoc network. Broadcast storm problem refers to the resulting redundancy, contentions and collisions if flooding is used blindly. The paper presents five schemes to alleviate the broadcast storm problem: - Probabilistic Scheme: A node rebroadcasts the received message with probability P (same as gossiping). - Counter-based Scheme: A node inhibits the rebroadcast if it receives more than C copies of the message. - Distance-based Scheme: A node inhibits the rebroadcast if it receives the message from a node within D meters from it. - Location-based Scheme: GPS is used to determine which node should or should not rebroadcast. - Cluster-based Scheme: Non-gateway members of a cluster do not rebroadcast. This can be coupled with any of the above schemes. Comments: - One important problem associated with reducing the number of rebroadcasts is that some important nodes may not get the message at all. For example, in a route discovery broadcast, the destination itself (and may be any other node with a route to the destination) may not get the RREQ packet, failing the route discovery process. - The paper considers carrier sense multiple access (CSMA) but no collision detection (CD). A RTS-CTS based MAC scheme or one with CD would have avoided many of the problems associated with broadcast storm problem. - The assumption that any mobile can issue a broadcast operation at any time may not be very realistic. - It is assumed that a host can communicate with any other host within R meters from it. How good an assumption is this? This may not hold true if there are obstacles/buildings etc in the surroundings. - The distance estimation method the authors have used may not be very accurate. - All nodes are assumed to have an equal transmit radius and equal power transmission levels. This excludes the possibility of nodes changing their power transmission levels adaptively depending on the surroundings and their needs. - The probabilistic scheme is equivalent to gossiping. The authors could have used the theoretical results available for that to strengthen their arguments. Also, the thresholding effect associated with gossiping is not clear from the results that they have produced. The value of P is crucial for good reachability of the message. - The schemes makes use of a node waiting for a random number of slots before rebroadcasting. However, they have not given any details of its distribution. - In a big network, a large percentage of the nodes may be gateways to other clusters, many of them redundant. Hence a further optimization could have been to choose only a selected few of these gateways to rebroadcast. - Formation of clusters would also incur some overhead. Hence the effective gain by using this scheme may not be as much as they have shown. - The GPS based schemes have a limited scope as it may not be possible to use it in all kinds of environments. Also it may lead to an increase in cost of the equipment. From jcb35@cornell.edu Tue Sep 11 14:14:47 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 f8BIElq19835 for ; Tue, 11 Sep 2001 14:14:47 -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 OAA07716 for ; Tue, 11 Sep 2001 14:14:43 -0400 (EDT) From: jcb35@cornell.edu Date: Tue, 11 Sep 2001 14:14:43 -0400 (EDT) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 paper #5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper discusses the "Broadcast Storm Problem" in a mobile ad hoc network (manet). The authors of this paper discuss how broadcasts are expected to be used frequently in ad-hoc networks; specifically, this paper addresses the problem of redundancy, contention, and collision that exist when blind broadcasts are attempted due to the fact that broadcasts in mantes are spontaneous, unreliable, and frequent. This paper begins by analyzing the problem of redundant broadcast and moves into the following schemes: 1. probability scheme: One receiving a broadcast message for the first time, a host will rebroadcast it with probability P after delaying for a small random time. 2. Counter based scheme: keep a counter c to keep track of the number of times a broadcast message is received, and for a period of time, if c doesn't exceed some threshold, then rebroadcast - this is so the host only broadcasts a message when it should increase the additional coverage. 3. distance based scheme: if we can determine the distance between nodes, we can determine how much additional coverage will be obtained by rebroadcasting a message. If this distance is large enough, then rebroadcast the message. 4. location based scheme: we can determine the coverage of nodes better if we know the location with gps - we can calculate if the coverage falls within a certain range, and if so, we want to rebroadcast. 5: cluster based scheme: the last scheme involves multiple nodes electing a cluster head, allowing him to rebroadcast to everyone within his cluster, and "gateway" edges that connect other clusters and propagate broadcasts. Other schemes can be incorporated into the gateway members also. Next the paper summerizes the performance simulation. The use a simulator that runs simplified version of the 801.11 protocol. They results show some tradeoff between nodes reached and saved rebroadcasts. The clustering scheme showed the greatest results, but the counter based system showed surprisingly good results for the simplicity of the scheme Comments: I would be curious to see schemes with varying power of the nodes within clusters to establish more efficient clusters when density is an issue. And I would think there would be more efficient ways of determining gateways in the clustering scheme, and I would think this would filter out broadcasts. I would also be curious to see mixtures of the schemes, for instance certain nodes, depending on node density, coverage area, or power, would adopt different schemes. More simulation results would be nice to see - instead of just a 5x5 block. From ms103@cornell.edu Thu Sep 13 12:34:02 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 f8DGY1q02030 for ; Thu, 13 Sep 2001 12:34:01 -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 LAA22959; Thu, 13 Sep 2001 11:54:24 -0400 (EDT) From: ms103@cornell.edu Date: Thu, 13 Sep 2001 11:54:23 -0400 (EDT) X-Sender: ms103@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 5 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Garcia-Lunes-Aceves' paper describes, validates and evaluates a distributed family of algorithms for loop-free routing, DUAL. The paper emphasizes the loop-free property of the algorithm and the distributed nature of the route discovery. In honesty, this was a hard paper to read and I didn't have time to critque the argument for the correctness of DUAL. However, the example was useful in understanding the methodology of DUAL. >From the performance evaluation section of the paper, DUAL appears better than the other algorithms it is compared to (DBF, Merlin-Segall) and even approaches the performance of and ideal link-state algorithm in some cases (while using less net CPU power). However, the presentation gives us little information about the simulation conditions and parameters.