From tmroeder@CS.Cornell.EDU Wed Sep 11 15:39:52 2002 Received: from dhcp98-44.cs.cornell.edu (dhcp98-44.cs.cornell.edu [128.84.98.44]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8BJdqh03217 for ; Wed, 11 Sep 2002 15:39:52 -0400 (EDT) Received: (from tmroeder@localhost) by dhcp98-44.cs.cornell.edu (8.11.6/8.11.6) id g8BJdqs06655; Wed, 11 Sep 2002 15:39:52 -0400 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15743.39944.16201.244183@dhcp98-44.cs.cornell.edu> Date: Wed, 11 Sep 2002 15:39:52 -0400 To: Emin Gun Sirer Subject: 615 PAPER #9 X-Mailer: VM 7.07 under Emacs 21.2.1 This paper presents, analyzes, and seeks to avoid the broadcast storm problem, which we have been concerned about in the proactive routing algorithms particularly, but which affect the reactive ones as well. The main contribution of the authors is that they show the magnitude of the problem that such storms can create and also the sometimes little value that is gained from allowing the problem to exist and not seeking better solutions in rebroadcasting. They present a whole sequence of potential solutions, and analyze them in depth. It is, in general, a well-thought-out discussion of the issues involved in the storm problem. There is also more significant mathematical probabilistic analysis than we have seen in any of the papers up to this point. Some of the assumptions that they make in this analysis are questionable; although I doubt that they would change the gist of the recommendations, they might modify some judgements with respect to the particular methods, since the analysis of which avoidance strategy is the best is accomplished without recourse to intuition, and relies entirely on the numbers. Some of the parameters to their simulator look reasonable, and others, particularly the size and frequency of packets, do not. Two possibilities for improvement of the analysis would be to perform at least some of these tests either in the wild, or with many different choices of parameters for the simluation to see if they are artifacting the results in any noticeable way. Further, the math assumes that all hosts have the same transmission power, or at least are all choosing to transmit at the same power. There are many situations in which this is likely not true. Again the assumption of bidirectionality comes to bite us. You cannot assume that the transmission patterns as a circle or even near to one, since there might be whole sections which are less than the radius away from the host, but which are not reachable. A good project might be to project all of this into 3-space, to see if the math holds and the analysis that hangs off of it still works. Further, one might try to determine how transmissions actually look in general and apply some numerical techniques to approximate the same analysis, by integrating the shapes that result. It is hard to say if the same results would come out or not, particularly with respect to bidirectionality concerns. From hs247@cornell.edu Wed Sep 11 16:07:31 2002 Received: from mailout6-0 (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 g8BK7Vh09137 for ; Wed, 11 Sep 2002 16:07:31 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout6-0 (8.11.6/RoadRunner 1.20) with ESMTP id g8BK7Pf02196 for ; Wed, 11 Sep 2002 16:07:25 -0400 (EDT) Message-Id: <5.1.0.14.2.20020911160725.00b39c60@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Wed, 11 Sep 2002 16:07:51 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 PAPER 9 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The main contribution of this paper was the introduction and identification of the broadcast storm problem. Several approaches to try to solve this problem were proposed simulated and evaluated. It was identified that in most ad-hoc networks, broadcasting is used. The broadcast storm problem is when one node broadcasts a message to its neighbours. Upon receiving of the message, the neighbouring nodes will rebroadcast it. Through mathematics, the authors were able to show that rebroadcasting of messages may not necessarily increase the coverage depending on the positions of the nodes. In fact, the more neighbouring nodes there are, the more collision are possible and less efficient broadcasting is. Therefore a node should only rebroadcast a message if it thinks it will provide new information. Probabilistic, counter-based, distance-based, location-based and cluster based were proposed to solving this problem. After initial simulation it was found that the location-based scheme and counter-based scheme worked well. The authors did a good job in keeping the concepts in this paper simple. They kept the problem simple and proposed simple solutions. The results of their simulation were analysed and even if an solution was poor they were able to come up with an explanation. Like the previous papers, the model in which the algorithms were simulated does not really reflect the real world. It assumed that every node had equal broadcasting power, where as in reality, some nodes may be weaker then others. It also assumed connections were bidirectional. This is not always the case, a stronger node may be able to reach a weaker node, but the broadcast of the weaker node may not be able to reach the stronger node. This paper was based on theory. Even the simulation was more of a theoretical model then a practical model. If would be interesting to see how these proposed solutions would perform in places such as the MANET network. Also, how would real world applications perform on these proposed solutions? Experiments on which parameters yield optimal solutions would be useful. Would combining more than one proposed solution make things better? Or maybe use different solutions in different environments? From mr228@cornell.edu Wed Sep 11 21:55:50 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 g8C1tnh19072 for ; Wed, 11 Sep 2002 21:55:49 -0400 (EDT) Received: from cornell.edu (syr-24-58-63-179.twcny.rr.com [24.58.63.179]) by cornell.edu (8.9.3/8.9.3) with ESMTP id VAA20243 for ; Wed, 11 Sep 2002 21:55:48 -0400 (EDT) Message-ID: <3D7FF42F.8469B888@cornell.edu> Date: Wed, 11 Sep 2002 21:55:59 -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 9 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper identifies and suggests solutions for a problem it calls the "Broadcast Storm" problem. Many ad-hoc network protocols require some amount of flooding to occur to broadcast messages and/or setup routes. This obviously places a great strain on network resources, especially in networks where there is contention for a single communications medium. The paper provides a formal definition of the problem and provides an in depth statistical analysis of how "helpful" it is for a given host to rebroadcast a packet. They argue that only a reduced subset of nodes needs to rebroadcast packets in order for a majority of the nodes to be reached by a flood. The paper presents 5 different ways in which a host can decide whether or not to rebroadcast a packet. (1) Rebroadcast with some probability < 1. (2) Wait for a random timeout and rebroadcast only if you've not heard this packet broadcasted by K other nodes (3) Rebroadcast only if you are sufficiently distant for the packet's source (4) Rebroadcast only if there aren't a sufficient number of other nodes within the vicinity of you and the source node. (5) The fifth approach involves forming clusters of nodes and cannot be done in a completely autonomous fashion. The paper provides experimental results with all 5 methods. While the results seem promising, in some configurations only 70%-80% of the nodes were reached; depending on the application, this may or may not be acceptable. Not being able to reach 1/5 of the nodes in the network can be a big concern. Their simulations seem vaild, however they assume a 2D world. While it seems as though the concepts would nicely translate into 3 dimensional space, it may be helpful to see the results of a "real-world", 3D test. From liuhz@CS.Cornell.EDU Wed Sep 11 22:03:04 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 g8C234h20656 for ; Wed, 11 Sep 2002 22:03:04 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 9 Date: Wed, 11 Sep 2002 22:03:04 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE5E2@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 9 Thread-Index: AcJaAIetqRexdGe5TkmAqT13DYmryg== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8C234h20656 The main contribution of this paper is that it identified the broadcast storm problem and gives some solutions to this problem in depth for MANET. Broadcast storm is caused by blindly flooding and will result in redundant rebroadcasts, contentin and collision. Detailed analysis are given to show how serious this problem is and several schemes are proposed to address this problem. Location-based scheme is the best one according to the simulation result. However, it needs aids from some positioning device(like GPS) and the computing cost of this algorithm is quite high because the intersection of many cycles need to be caculated time to time. The authors suggest an alternative way(using a convex polygon as the metric) that can decrease this cost in price of acruracy and make this scheme applicable. Culster-based shemee works also very well in most aspects except that the reachability is unacceptable in sparse area. The counter-based scheme is also intriguing given its simple implementation although its performance is not so good as location-based one. In general, it's a very good paper, well-organized and easy to understand, but there are still some problems. - The simulation didn't capture the basic property of ad-hoc network: mobility. The authors didn't say anything about mobility. What will the result be if all the hosts in the system move fast? In such system, clusters will change frequently and the cost to maintain the clusters may be very high and the performance of cluster-based scheme will suffer. - In the distance-based scheme, signal strength is used to estimate the distance, but I think that's inaccurate in some case. In reality, signal strength is affected by many factors not only distance. - In the simulation of location-based scheme, exact positions and exact ACs(additional coverages, which are usually not available because of high cost) are used, but the authors don't give the result when only approximate ACs are available using the grid-filling or convex polygon algorithm, - The performance of some of the proposed schemes vary according to the density of the system. Then why not use some hybrid protocol that use different scheme in face of the system whose density will change frequently? Hongzhou Liu From xz56@cornell.edu Wed Sep 11 22:45:10 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 g8C2j9h29998 for ; Wed, 11 Sep 2002 22:45:09 -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 WAA20139 for ; Wed, 11 Sep 2002 22:45:08 -0400 (EDT) Message-ID: <007701c25a06$68479320$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 9 Date: Wed, 11 Sep 2002 22:45:07 -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 The paper raised a valuable problem in the MANET, i.e. the broadcast storm and the approaches the authors used to analyze the redundancy, contention are also very good. Although, the analysis on collision based on the CSMA/CA is not very meaningful, since carrier sensing is not that proper to use in wireless comm. as RTS/CTS dialog. Also, RF delay should not be that influential in a small range of transmission as in MANET and the transmission latency should be helpful for other nodes to do carrier sensing. The schemes part for dealing with the problem is relatively weak: Probabilistic scheme: The decision of the probability depends on the density of the distribution of nodes. It should need an adaptive approach. Counter-based scheme: This maybe the best one among the five with a higher efficiency/complexity ratio. Distance-based scheme: I doubt it's practicability. Two problems: one is the estimation of distance, another, as mentioned in the paper, is what if many nodes locate outside the threshold distance but in-sight? Location-based scheme: There may be much better way to route the broadcast packet with the help of info provided by GPS. Cluster-Based scheme: It seems interesting and promising and with good scalability. Maybe need more work on that. Maybe those are the best they can do using CSMA/CA in MAC. But if using RTS/CTS, the solution will be much easier and with much better result. The simulation is better than those in previous papers, although the 3*3 and esp. 1*1 cases are not that meaningful. From jsy6@cornell.edu Wed Sep 11 23:27:28 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 g8C3RSh07975 for ; Wed, 11 Sep 2002 23:27:28 -0400 (EDT) Received: from Janet (syr-24-58-41-193.twcny.rr.com [24.58.41.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id XAA04236 for ; Wed, 11 Sep 2002 23:27:27 -0400 (EDT) Message-ID: <000a01c25a0c$4678e270$a400a8c0@Janet> From: "Janet Suzie Yoon" To: Subject: 615 PAPER 9 Date: Wed, 11 Sep 2002 23:27:08 -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_0007_01C259EA.BF270520" 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 This is a multi-part message in MIME format. ------=_NextPart_000_0007_01C259EA.BF270520 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable One of the simplest ways to broadcast is by flooding: a host, upon = receiving a message for the first time, rebroadcasts the message. = Flooding, unfortunately, can result in rebroadcast redundancy which in = turn increases the chance of contention and collision. These problems = associated with flooding are known as the broadcast storm problem. The = severity of the broadcast storm problem is great within a mobile ad-hot = network (MANET), especially if the flooding is done blindly. The major = contributions of this paper are its analysis on the magnitude of the = broadcast storm problem in a MANET, possible solutions to reduce the = severity of the problem, and analysis of the solutions. =20 The paper calculates the redundancy generated by = rebroadcasting, and concludes that the expected additional coverage of a = host rebroadcasting a message after hearing it four or more times is = less that 0.05%. The probably of contention with only two receiving = hosts is 59%. This probability increases with the number of hosts = within the transmission range. If there are 6 or more hosts in a = transmission range, the probability of all the hosts experiencing = contention is over 0.8. Collision is just as severe as the above two = problems due to several reasons: flaws in backoff procedures, forwarding = dialogue are not used in a broadcast transmission, and increase in waste = without collision detection. =20 The paper offers five schemes to alleviate the broadcast = storm problem: the probabilistic scheme, the counter-base scheme, the = distance-base scheme, the location-based scheme, and the cluster-based = scheme. They all aim in reducing rebroadcasting, thus reducing = contention and collision. In the probabilistic scheme, a host will = rebroadcast a message it has heard for the first time with the = probability P. The Counter-base scheme requires a counter for each host = in order to keep track of the number of times a host has heard the same = message. If the number of times the message is heard is equal to or = greater than the set Counter threshold, the host will not rebroadcast = the message. The Distance-Based scheme determines whether or not to = rebroadcast based on the host's distance to the nearest host from which = the same message is heard. The Location-Base scheme acquires the actual = location of the broadcasting hosts in order to more accurately estimate = the additional coverage in rebroadcasting. One problem of the = Location-Base scheme is the cost of calculating the additional coverage. = A more cost-efficient solution is to instead use a grid-filling = approximation or a convex polygon to estimate the value. Lastly, the = Cluster-Based scheme forms clusters and gateway members using the = cluster formation algorithm. Only gateway members are allowed to = rebroadcast a message. A gateway member will rebroadcast a message = based on any of the above schemes listed. =20 The two important factors in rating the different schemes is = its reachability and the number of rebroadcasts saved. Distance-based = scheme provides a better reachability than the counter-based scheme, but = not as many rebroadcasts are saved. The cluster-based scheme performs = poorly in the reachability field in sparse areas. The best performing = scheme is the location-based scheme since it utilized the exact = information to calculate the additional coverage. =20 This paper described the broadcast storm problem well and = offered interesting solutions, but failed to comment how to deal with = two hosts being unable to communicate due to poor reachability in a = scheme. Suppose two hosts can in theory communicate with each other. = Using the distance based scheme, the hosts cannot reach each other due = to the relative distances of the other hosts in the network. Until the = topology of the network changes, they will not be able to communicate. = There should be a protocol to insure that eventually the two hosts = should be able to communicate, even when the network remains static. = Another improvement, which was mentioned in the paper, would be the = incorporation of GPS receivers to facilitate the retrieval of location = information. =20 ------=_NextPart_000_0007_01C259EA.BF270520 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

One of the simplest ways to broadcast is by = flooding: a=20 host, upon receiving a message for the first time, rebroadcasts the=20 message.   Flooding,=20 unfortunately, can result in rebroadcast redundancy which in turn = increases the=20 chance of contention and collision. =20 These problems associated with flooding are known as the = broadcast storm=20 problem.  The severity of = the=20 broadcast storm problem is great within a mobile ad-hot network (MANET), = especially if the flooding is done blindly.  The major contributions of = this paper=20 are its analysis on the magnitude of the broadcast storm problem in a = MANET,=20 possible solutions to reduce the severity of the problem, and analysis = of the=20 solutions.  =

           =20 The paper calculates the redundancy generated by rebroadcasting, = and=20 concludes that the expected additional coverage of a host rebroadcasting = a=20 message after hearing it four or more times is less that 0.05%.  The probably of contention = with only two=20 receiving hosts is 59%.  = This=20 probability increases with the number of hosts within the transmission=20 range.  If there are 6 or = more hosts=20 in a transmission range, the probability of all the hosts experiencing=20 contention is over 0.8.  = Collision=20 is just as severe as the above two problems due to several reasons: = flaws in=20 backoff procedures, forwarding dialogue are not used in a broadcast=20 transmission, and increase in waste without collision detection. 

           =20 The paper offers five schemes to alleviate the broadcast storm = problem:=20 the probabilistic scheme, the counter-base scheme, the distance-base = scheme, the=20 location-based scheme, and the cluster-based scheme.  They all aim in reducing = rebroadcasting,=20 thus reducing contention and collision. =20 In the probabilistic scheme, a host will rebroadcast a message it = has=20 heard for the first time with the probability P.  The Counter-base scheme = requires a=20 counter for each host in order to keep track of the number of times a = host has=20 heard the same message.  = If the=20 number of times the message is heard is equal to or greater than the set = Counter=20 threshold, the host will not rebroadcast the message.  The Distance-Based scheme = determines=20 whether or not to rebroadcast based on the host=92s distance to the = nearest host=20 from which the same message is heard. =20 The Location-Base scheme acquires the actual location of the = broadcasting=20 hosts in order to more accurately estimate the additional coverage in=20 rebroadcasting.  One = problem of the=20 Location-Base scheme is the cost of calculating the additional = coverage.  A more cost-efficient solution = is to=20 instead use a grid-filling approximation or a convex polygon to estimate = the=20 value.  Lastly, the = Cluster-Based=20 scheme forms clusters and gateway members using the cluster formation=20 algorithm.  Only gateway = members are=20 allowed to rebroadcast a message.  A=20 gateway member will rebroadcast a message based on any of the above = schemes=20 listed.  =

           =20 The two important factors in rating the different schemes is its=20 reachability and the number of rebroadcasts saved.  Distance-based scheme provides = a better=20 reachability than the counter-based scheme, but not as many rebroadcasts = are=20 saved.  The cluster-based = scheme=20 performs poorly in the reachability field in sparse areas.  The best performing scheme is = the=20 location-based scheme since it utilized the exact information to = calculate the=20 additional coverage. =20

           =20 This paper described the broadcast storm problem well and offered = interesting solutions, but failed to comment how to deal with two hosts = being=20 unable to communicate due to poor reachability in a scheme.  Suppose two hosts can in = theory=20 communicate with each other.  = Using=20 the distance based scheme, the hosts cannot reach each other due to the = relative=20 distances of the other hosts in the network.  Until the topology of the = network=20 changes, they will not be able to communicate.  There should be a protocol to = insure=20 that eventually the two hosts should be able to communicate, even when = the=20 network remains static.  = Another=20 improvement, which was mentioned in the paper, would be the = incorporation of GPS=20 receivers to facilitate the retrieval of location information.  =

------=_NextPart_000_0007_01C259EA.BF270520-- From shafat@CS.Cornell.EDU Thu Sep 12 00:14:32 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 g8C4EVh18438 for ; Thu, 12 Sep 2002 00:14:31 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 9 Date: Thu, 12 Sep 2002 00:14:29 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D150795@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 9 Thread-Index: AcJaEuPoRE1MAHW9SVmzRZsPdpxfaA== 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 g8C4EVh18438 This paper outlines the Broadcast Storm Problem in a Mobile Ad-Hock Network and how it is inadvertently caused by flooding in most widely used routing protocols. Flooding, as the paper highlights, leads to redundant rebroadcasts, contention and collisions. The paper also does a very strong job of doing a quantitative analysis of how these factors reduce the efficiency of the entire network, and proposes five schemes, with substantial simulation results, to alleviate the broadcast storm problem. Things missing from the analysis of the result is a good value for P in the Probabilistic Scheme. One reason for that may be the results failed to draw a good conclusion for this scheme. Another question that remains unclear is whether the P value is the same for all hosts on the network (as the simulations assume) and if so, how the hosts decide on this value. The Counter-Based Scheme is a reasonably good solution although there may be cases where a data packet may not reach the final destination. This situation may arise if the only node that can reach the final host drops the packet because of the conditions asserted in the scheme. Overall, the Location-Based scheme seems to give great results, but the associated extra overhead due to the use of devices such as GPS receivers may be too high. In a very dynamic network, this overhead may not be feasible at all. This scheme also makes an underlying assumption (all do, but this scheme is affected the most) that all hosts have the same transmission power. It would be interesting to observe how it holds up when an extra parameter (varying transmission power) is added to the simulations. The paper also does not address the load balancing issue, especially in the Cluster-Based Scheme. Due to its nature, the load of almost all transmissions within a cluster may fall on either the head or the gateway. This may have some serious implications on performance. It might be possible to periodically change these clusters or ID assignments to spread the load. From mp98@cornell.edu Thu Sep 12 00:38: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 g8C4cbh23494 for ; Thu, 12 Sep 2002 00:38:37 -0400 (EDT) Received: from Warren-Lapines-Computer.local. (r105572.resnet.cornell.edu [128.253.240.214]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA07133 for ; Thu, 12 Sep 2002 00:38:34 -0400 (EDT) Date: Thu, 12 Sep 2002 00:38:35 -0400 Mime-Version: 1.0 (Apple Message framework v543) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 PAPER 9 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <8011ECCE-C609-11D6-987E-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.543) The authors of this paper evaluate the theoretical efficency (and inefficiency of broadcasting) of broadcasts taking into account geography and network contention. They mathematically model the effects of broadcasts, suggest several techniques to alleviate the problems, and use simulations to measure their effectiveness. This paper has several nifty ideas to alleviate the effects of a broadcast flood, including creative geographic and distance solutions, as well as a cluster scheme. They also run extensive tests on all these methods. Unfortunately, most of these creative solutions are flawed. For example, their distance technique relies on an equation which may or may not be useful [it comes from a textbook on wireless communications, and so one suspects it is more theoretical than practical.] Their location based scheme requires hardware which is not standard yet. And the cluster based routing protocol is not adequately addressed: What happens if a head node is also a gateway node? In addition, their simulation is rather poor. I could find no specification of the number of nodes used, nor how they are placed in the network. There's no talk at all about the network being disjoint and their communications model seems fairly random. This work should be modified and re-implemented, with a standardized simulation environment and network model. From ag75@cornell.edu Thu Sep 12 02:49:22 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 g8C6nMh16656 for ; Thu, 12 Sep 2002 02:49:22 -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 CAA22984 for ; Thu, 12 Sep 2002 02:49:21 -0400 (EDT) Message-ID: <000d01c25a28$8ab19240$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 9 Date: Thu, 12 Sep 2002 02:49:28 -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 week's paper the authors discuss the problem of broadcast storms. They argue that serious redundancy, contention and collision could exist if flooding is done blindly. The paper presents five schemes for to deal with these problems. Each of these schemes attempts to reduce redundant broadcasts and differentiate timing of rebroadcasts to alleviate the broadcast storm problem. The authors present a good mathematical analysis of the problem and they show just how inefficient things become when flooding is done blindly. Based on their analysis the authors present five schemes that they tested with a simulator. The simulation was done using 100 nodes, which is a decent size. The testing area between 500x500 meters and 5000x5000 meters was also quite large. The schemes presented have several issues. First of all, they are all quite similar. Second, their differences concentrate on reducing redundant broadcasts, while the method for differentiating timing of rebroadcasts is the same "wait a random number of slots" for all five schemes. There are probably other methods that exist that were not explored in this paper, and it would be interesting to see how these other methods would impact the performance of the five schemes that were presented. From ashieh@CS.Cornell.EDU Thu Sep 12 04:44:33 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 g8C8iWh10722 for ; Thu, 12 Sep 2002 04:44:32 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8C8iWp18725 for ; Thu, 12 Sep 2002 04:44:32 -0400 (EDT) Date: Thu, 12 Sep 2002 04:44:32 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 9 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII ** Contributions This paper discusses the potential problems with broadcasting in an ad hoc network. Broadcasts in wireless networks are typically more vulnerable to collision than unicast. Furthermore, subsequent rebroadcasts may overlap in coverage area, resulting in redundancy. The expected added coverage area of a rebroadcast by a given node decays sharply as the number of broadcasts heard by that node increases. The authors characterized several mechanisms for reducing redundant broadcasts (collisions were addressed with randomizing the delay before broadcast): probabilistic (uniform probability of rebroadcasting or not), counter (rebroadcast if < N other broadcasts heard), distance (rebroadcast if > D distance from all broadcasts), positional (rebroadcast if far enough away from all other broadcasts heard), and cluster-positional (use positional information to cluster, and then restrict broadcasts within a cluster to a "head" node; all other rebroadcasts are through "gateway" nodes to neighboring clusters). The counter-based approach provided good reductions in redundancy, but poor connectivity; the distance based algorithm provided good connectivity, but less reduction in redundancy. Positional information allowed for markedly better redundancy reduction and latency. Clustering provided the best reduction in redundancy. However, for both the positional and clustering system, reduced redundancy also resulted in reduced connectivity. ** Problems As with previous papers, the simulation workload (random topology, random node chosen to broadcast) was unrealistic. Route discovery and propagation is a major client of broadcasts. A distance vector workload would consist of closely correlated broadcasts starting from each node. The route discovery techniques used in DSR and AODV already have broadcast controls; it would have been instructive to see how the control mechanisms proposed in this paper interact/compare with those used in the routing protocols. ** Extensions - Evaluate a hybrid scheme that utilized both counters and distance; such a scheme may achieve a better balance between redundancy reduction and connectivity - Evaluate schemes where unicasts are used to reliably send broadcast data to a node that subsequently rebroadcasts the data; this could provide better coverage per actual broadcast and improve connectivity. - Is it possible to alleviate the hidden terminal problem with RTS/CTS packets on broadcasts? CTS packets are short, so they are unlikely to collide with one another. In fact, looser time synchronization is necessary for constructing a TDMA schedule of short packets than for long packets, so it may be possible to reduce losses even further. - Conceivably, a MAC could capture CTS information, and propagate it over multiple hops; this information would build a local connectivity graph which may be useful for performing local optimizations. This is a special case of the general technique of sending short broadcast messages to organize the network in anticipation of much longer broadcast packets. - In general, these MAC schemes trade off effective bandwidth (potentially more time idle time in the channel) for power efficiency. From nbs24@cornell.edu Thu Sep 12 08:58:45 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 g8CCwjh06172 for ; Thu, 12 Sep 2002 08:58:45 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id IAA09860; Thu, 12 Sep 2002 08:58:43 -0400 (EDT) Date: Thu, 12 Sep 2002 08:58:43 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209121258.IAA09860@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: nbs24@cornell.edu X-Originating-IP: 64.185.145.94 Subject: 615 PAPER 9 This paper provides possible solutions to the key problems of flooding: redundant rebroadcasts, contention and collision. Using statistical and graph models, they propose five schemes whose goal is to alleviate these problems by reducing the redundancy, and subsequently the other two. In probabilistic scheme, a node only does 'delayed' rebroadcasts with a probability of P. In the counter_based scheme, a node rebroadcasts only if it has rebroadcasted the same message less times than a given threshold. In the distance_based scheme, a rebroadcast is made only if the received signal strength is greater than a given threshold. In the location_based scheme, a rebroadcast is made only if GPS information falls within a predefined coverage threshold. Finally, the cluster_based scheme, uses gateways to do rebroadcasting. The effect of topology changes, especially on the cluster_based scheme, wasn't addressed. How much computation overhead is needed in a rapidly changing topology? Since distance is not the only factor that affects signal strength, I didn't think it was a good metric to use to measure distance. They could just call the scheme a signal_strength scheme. Also, it is assumed that if node A can reach node B, the opposite is true. This is generally not true. Since they simulated the network in software, I would have expected them to simulate much more nodes than the 100 they did. Perfect circles also do not represent real transmission patterns. To build on the research, they can implement their schemes in a real network and evaluate their performance. They could probably start with the more realistic models, such as the counter_based scheme, and work their way up. Nana B. Sam From smw17@cornell.edu Thu Sep 12 09:06:53 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 g8CD6qh07487 for ; Thu, 12 Sep 2002 09:06:52 -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 JAA21371 for ; Thu, 12 Sep 2002 09:06:51 -0400 (EDT) Message-ID: <3D8090C6.2060902@cornell.edu> Date: Thu, 12 Sep 2002 09:04:06 -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 9 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Broadcast Storm I found this paper to be a very interesting and informative paper on both the impact of packet flooding and the net single-node gain by adding an additional node into the ad-hoc network. One of the most significant conclusions to me was the fact that the addition of a new node can at most provide additional coverage equal to 61% of the single node coverage (assuming identical nodes with a circular propagation pattern). This implies that wireless networks are not particualarly efficient with regards to covering a space, and that the marginal gain for each additional node in a congested network is quite small. The authors show exactly this, by demonstrating that the additional network area falls off rapidly when a host recieves multiple broadcast packets from adjacent nodes. Based on these analytical findings, the authors investigate a number of potential schemes to reduce the flooding overhead while still achieving the desired dissemination of packets. They consider five different schemes for achieving these goals. The first is a probabilistic scheme where a node has a given probability of re-broadcasting a flooded packet. The second scheme is a counter based scheme, in which a node that has recieved a given number of broadcast packets from neighboring nodes (a threshold number) will not forward the packet due to the low potential increase in network area. In the third scheme, the counter is replaced by a minimum distance threshold, such that any node that recieves a packet within a specified minimum distance will not re-broadcast the packet. The final two schemes involve more assumptions about hardware and/or network structures. The fourth scheme requires some absolute distance measure, such as a GPS reciever, at each node. This data may be used to analytically compute network coverage gain added through the addition of a new node. Nodes which do not add a sufficient increase in network area should not re-broadcast packets. The final scheme is one that assumes a cluster-based heirarchical network structure consisting of groups of nodes, with a single cluster head node and (potentially) a number of gateway nodes to communicate between adjacent clusters. Non-gateway nodes do not re-broadcast data packets. I felt that this paper did a good job in numerically evaluating the additional node effectiveness in different situations, and providing a number of different potential improvements to the straight flooding protocol without compromising the communication itself. They investigated the effects of the different improved flooding techniques with respect to node density and per node traffic. In some cases, they actually found that flooding resulted in a less reachable network due to collisions at network nodes. Despite this, there are still areas for improvement in the presented work. The authors simulated at different broadcast rates, but fail to show similar results from sample protocols indicating what range of broadcast rates can be expected for a given protocol. They also do not consider the case of an access point, where a single non- identical node may add a disproportionate additional area to the network. Combining these results with different representative protocols and networks to illustrate the real-world potential gain of the improved flooding algorithm would be a very interesting experiment. /Sean From mtp22@cornell.edu Thu Sep 12 09:49:19 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 g8CDnJh17577 for ; Thu, 12 Sep 2002 09:49:19 -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 JAA22023 for ; Thu, 12 Sep 2002 09:49:19 -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 9 Date: Thu, 12 Sep 2002 09:50:27 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02091209502702.00149@narnia> Content-Transfer-Encoding: 8bit The major contribution of this paper is the first mathematical analysis of the broadcast storm problem in mobile ad hoc networks. This problem is important because broadcasts are used extensively in current protocols, and, according to this paper, many of the broadcasts are redundant; wasting bandwidth and power. The authors' use of their own simulator is a weakness of this paper. Their simulator may have bugs that have not been worked out over time like those of established simulators. Also, it is hard for others to expand upon or compare the work in this paper if they don't have access to or aren't familiar with this homegrown simulator. Another weakness is the analysis of why the distance-based scheme results in more rebroadcasts than the counter-based scheme. The authors say "In the distance-based scheme, a host may have heard a broadcast message so many times but still rebroadcast the message because none of the transmission distances are below a given distance threshold, where the rebroadcast would have been canceled if the counter-based scheme is used." However, an analogous statement could be made to support the counter-based scheme resulting in more rebroadcasts: In the counter-based scheme, a host may have heard a broadcast message from a host within the distance threshold but still rebroadcast the message because the counter is below the counter threshold, whereas the rebroadcast would have been canceled if the distance-based scheme were used. There is also a weakness in the analysis of the location-based scheme as the best scheme because the simulation does not seem to take into account the time and processing that would be involved in obtaining coordinate data from GPS. This may severely impact the performance of this scheme. The work in this paper could be expanded upon by performing a similar analysis with non-homogeneous hosts. That is, mathematically analyze redudancy, collision, and contention when the hosts vary in, for example, transmission range. An analysis of the schemes proposed in this paper in such a non-homogeneous environment may also help in determining some of their real world usefulness. From kwalsh@CS.Cornell.EDU Thu Sep 12 10:00:23 2002 Received: from kwalsh.cs.cornell.edu (dhcp98-75.cs.cornell.edu [128.84.98.75]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8CE0Mh20289 for ; Thu, 12 Sep 2002 10:00:22 -0400 (EDT) Message-Id: <5.1.1.6.0.20020912094743.00a6f318@popsrv.cs.cornell.edu> X-Sender: kwalsh@popsrv.cs.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 Date: Thu, 12 Sep 2002 10:00:22 -0400 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 9 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The Broadcast Storm Problem in a Mobile Ad Hoc Network The paper presents a brief survey of strategies to avoid and minimize problems arising from "broadcast storms" in ad hoc networks. Most routing ad hoc routing protocols rely to some extent on unidirectional local broadcasts, which are then propagated by neighbors in subsequent broadcasts. Thus, a wave front of broadcasts is created, which often collide and can cause serious contention in the network. The authors also note that many of the subsequent broadcasts are also redundant, due to the limited additional range of neighbors. Using various techniques, neighbors can estimate the amount of additional area their broadcast might reach, and can therefore decide whether to suppress or propagate the broadcast. The techniques (each with a single tunable parameter) use probabilistic forwarding, message counting, distance estimation, location estimation, or local cluster information. Each technique is evaluated in a simulation for eventual coverage, savings over flooding, and total latency. The comparisons are helpful and interesting, but the results are not analyzed in any deep way. Several times, the authors resort to guesses about the underlying behavior without trying to study the behaviors in detail. Overall, however, the paper is informative, simple, and fairly comprehensive. From vivi@CS.Cornell.EDU Thu Sep 12 10:03:35 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 g8CE3Zh21247 for ; Thu, 12 Sep 2002 10:03:35 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper9 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 12 Sep 2002 10:03:34 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF61@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper9 Thread-Index: AcJaZS8Ak5J9UakbSRmkJQtqPYIl/w== 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 g8CE3Zh21247 This paper is unique in the sense that it does not propose a new protocol or architecture, but studies the Broadcast phenomenon, which is fairly commonly used in many protocols. The paper enumerates the redundancies that result due to broadcasts, and also lists out measures to alleviate the problems. One of the weaknesses of the paper is its presentation: there are frequent grammatical errors and ambiguities. Some of the schemes suggested by the paper require additional hardware for realization. For instance, the Distance-Based scheme requires any node to be able to compute the distance to other nodes that it receives broadcast packets from. Similarly the Location-Based scheme requires the GPS system. The cost of installing such extra functionalities has not been taken into consideration while evaluating the recommended modifications. Also, the extra costs of forming clusters in the Cluster-Based scheme are not studied. (How the clusters are formed is not described precisely) The Distance-Based Scheme does not seem to be very effective in curtailing the number of broadcasts. This is due to the fact that the dropping of a rebroadcast results only from a single event - when the original broadcast is from a node very close to this node. Repeated receptions of the same broadcast (from different nodes) do not have any effect on the working of this scheme. One major shortcoming of the simulations described in this paper is that the attempted modifications have not been compared with the original protocol (without the modifications). This comparison is essential in deciding if the modifications are worth attempting. Also, the paper has not given any pointers as to which of the suggested schemes is the best or the most appropriate. The simulations have also not measured the number of hops in the routes. It is probable that many of the paths formed are not the optimal ones, since a significant number of the re-broadcasts are dropped. From vrg3@cornell.edu Thu Sep 12 11:05:42 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 g8CF5gh06591 for ; Thu, 12 Sep 2002 11:05:42 -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 LAA24301 for ; Thu, 12 Sep 2002 11:05:40 -0400 (EDT) Date: Thu, 12 Sep 2002 11:05:40 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 9 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper discusses the "broadcast storm" problem: a flooding approach to broadcasting on a MANET results in redundant retransmissions, high contention, and many collisions. The presence of the problem is demonstrated with mathematical arguments, and then five suggestions are made as to how to alleviate the problem. The authors discuss some simulations they have done to test the effectiveness of each of these suggested modes of operation. The first scheme suggested is a simple probabilistic one; each node retransmits the broadcast with a fixed probability. The second is counter-based; a node will not rebroadcast if it receives the message more than a certain number of times. The third is distance-based; a rebroadcast is inhibited if the broadcast was received from a node sufficiently nearby. The fourth is location-based; it uses an external information source (such as GPS) to actually determine the additional coverage its rebroadcast would provide. In a sense, the counter-based and distance-based schemes are approximations of the location-based scheme. The fifth scheme is a layer that can go on top of any of the first four, which allows for local clusters of nodes, as ad-hoc "cells," with designated relaying agents. This paper makes it very clear that flooding is extremely inefficient. The probabilistic scheme really has no strong theoretical basis, and yet the simulation showed that it provided a significant improvement over naive flooding. The payoff for retransmission, it seems, very often is overwhelmed by the cost. While the results of the simulation may be telling, the description provided of the authors' simulation is somewhat inadequate. It is unclear how they distributed the nodes spatially or how they distributed the broadcasts temporally (or whether it mattered). For the clustering scheme, it is also relevant how the nodes move over time. No mention was made of how the movement was simulated, or if it was at all. It is not necessarily feasible or desirable to equip each mobile node with a positioning system, but it would be interesting to try to devise a scheme which incorporated both counter-based and distance-based information when trying to decide whether to retransmit. This may yield a closer approximation to the location-based scheme. Another interesting analysis may involve nodes with different capabilities. The assumption made in these analyses is that the transmission radius is fixed. In the real-life case, this is not always true. Some nodes have more powerful radios than others, and some physical materials in the vicinity may affect nodes' transmission and reception capabilities. From yao@CS.Cornell.EDU Thu Sep 12 11:15:49 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 g8CFFnh09194 for ; Thu, 12 Sep 2002 11:15:49 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 9 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 12 Sep 2002 11:15:49 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302ED4C27@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 9 Thread-Index: AcJab0a7RCxxM5+fTHuQanvuN2lb7Q== 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 g8CFFnh09194 This paper defines and analyses the 'Broadcast Storm' problem in details, proposes several techniques to alleviate the problem, and tests them through simulations. The paper shows that the blind flooding, which is a frequent operation in many MANET, could cause serious problems. Some of them are listed below: 1. Redundant Rebroadcasts: It is efficient to rebroadcast a flooding message for some hosts, expecially as the number of hosts increases. The paper demonstrates it trough computation and carefully designed experiments. It will also make other two problems more severe. 2. Contention & Collision: They are more like MAC layer problems. Without efficient MAC- layer support, like CD, contention and collision could be serious problems during broadcasting. Again, the paper discusses their influences to the network and what reasons are behind them. The author also proposes several improvements to alleviate Broadcast Storm. The key point is to reduce unnecessary rebroadcasting. It can be achieved by monitoring the behaviour of nerghboring nodes and introduce random delay, or constructing some additional structures to avoid redundancy. The paper has a detailed evaluation section to compare different methords through experiments on a well designed simulator. One possilbe extension of the paper is to study the interaction between their algorithms and existing protocols, which trigger broadcast storms in MANET. A specific solution might be the best in some particular scenarios. There might exist some high level solutions, combing additional topology information, and outperforming all these algorithms. Yong From adam@graphics.cornell.edu Thu Sep 12 11:24:10 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 g8CFO9h11829 for ; Thu, 12 Sep 2002 11:24:10 -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 g8CFO40k096737 for ; Thu, 12 Sep 2002 11:24:04 -0400 (EDT) Date: Thu, 12 Sep 2002 11:16:17 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 PAPER 9 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper describes the potential problems w/ a flood based routing system of MANET. It talks about the differences between the multi-hop and single-hop (peer-to-peer) systems and that multihop has many limitations or hardships to overcome. First and foremost this paper highlights the drawbacks to rebroacasting and notes only a maximum of 59% range extension based on the properties of bi-directional transmission. Further it brings up the problems of contention and collision in a network where many systems are rebroadcasting information. It offers some possible solutionst to the problem and some basic testing of them. The basic solutions to a flood-based MANET routing system (as assumed as the naive implementation of routing) included a probabilistic, counter-based, distance based and location based schemes. Each of these presented a slightly different way to limit the amount of rebroadcasts in each network. The criticisms of this paper would include the method in which they analyzed the paper. The simulation is just a program, not an actual mobile solution so it immediately has the drawback of not being the real thing. Further the "best" solution in my opinion uses GPS hardware which isn't standard on computers, nor is built in PC-CARD format which would require the dragging of another piece of hardwared along w/ the unit. Certainly a good deal of effort has been put into the math aspect of this paper. There is a clear, well thought out presentation of the advantages (or disadvantages) of rebroadcasting according to a flood based or other scheme. This paper also makes it blatantly obvious that anything will be better than a naive flood based system since it is so bad. The counter-based and distance-based schemes are nice (but not totally perfect) approximations to the location (gps use) based scheme. From ks238@cornell.edu Thu Sep 12 11:43:28 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 g8CFhRh17069 for ; Thu, 12 Sep 2002 11:43:27 -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 LAA05260 for ; Thu, 12 Sep 2002 11:43:26 -0400 (EDT) Message-Id: <5.1.0.14.2.20020912114151.01b37860@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 12 Sep 2002 11:42:52 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 Paper #9 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In their paper on Broadcast Storms, the authors define the problem as one which occurs in mobile ad hoc networks that employ broadcasting through periodic flooding of the network as a mechanism for communicating between mobile nodes. A storm occurs in such networks when flooding results in redundant broadcasts, contention between neighboring mobile hosts attempting to communicate, and collisions of messages. In order to mitigate or even to eradicate broadcast storms the authors propose four solutions. The first involves a counter-based scheme where the number of times that a broadcast is received is tallied, and should that number exceed a certain threshold, all subsequent packets are then dropped and the host is not allowed to resend that message. The second solution is a distance-based scheme where the distance between two communicating nodes is evaluated and should this distance be less than a certain threshold, then all subsequent packets are dropped from the host since the additional new range area that can be provided by the receiving node is too small. The third solution is the location-based scheme in which the exact location of a node receiving a message is assessed and then it is determined if the node's position allows it to rebroadcast to a substantial enough area. The final solution is the cluster-based scheme by which each node is part of a cluster of other nodes and communication is limited between those nodes that serve as gateways between two or more clusters. The authors test their probable solutions by creating a simulation on 100 nodes within different areas. The results indicate that should the tools be available the cluster-based scheme is good but with some problems. The protocols primary downfall is that in order to execute a cluster-based solution, one must develop an algorithm by which clusters are organized and maintained. This can definitely become memory intensive in a mobile network with a considerable amount of movement. Also, when nodes become spread out over larger areas (as indicated in the paper) clusters are less likely to be significant which would dwindle the results of this solution. The location-based solution apparently showed stronger results than the counter and the distance based solutions. However, I feel that the location-based solution will become more and more ineffective as the area for mobility grows larger. One of the problems then comes with how high should the threshold be set without compromising the results of preventing collision within the network. I feel that the paper should have discussed ideal thresholds for the final two protocols more extensively since this a pivotal aspect of their solutions and all results are contingent on picking ideal threshold values. From aed13@cornell.edu Thu Sep 12 11:56:13 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 g8CFuDh19970 for ; Thu, 12 Sep 2002 11:56:13 -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 LAA21080 for ; Thu, 12 Sep 2002 11:56:12 -0400 (EDT) Message-Id: <5.1.0.14.2.20020912110535.00ae6290@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 12 Sep 2002 11:56:09 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 PAPER9 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper "The Broadcast Storm Problem in a Mobile Ad Hoc Network" provides an in-depth mathematical and simulation based analysis of the costs of re-broadcasts in an ad-hoc network. The broadcast storm problem includes issues of contentions, collisions caused by blind flooding. Tow directions to relieve problem exist; first reduce the possibility of redundant broadcasts, second differentiate the timing of broadcasts: The paper provides an mathematical overview of the costs and benefits of re-transmission in Section 2. I proves mathematically that the coverage are gained by a blind transmission is at most 61%, by a second retransmision of 41%. It shows the effectiveness of re-broadcasts to strictly decrease as the number of nodes increase. When the number of nodes is > 4 the additional benefits become less then 4%. The paper provides 4 schemas to reduce redundancy, contention and collision. Probabilistic based schema decides with a probability weather to re-transmit or not and introduces a random delay. In a Counter-based schema a minimum threshold of delay is set during which the sender waits to listen for other to broadcast. When the threshold is passed the sender transmits its broadcast. If it is interrupted it increments its counter. In distance-based schema the relative distance between nodes is used to decide who should broadcast. Nodes at greater distance were shown to have greater increased coverage in section 2. Location-based schema's extend the design of distance-based with exact location information provided by system's such as GPS to calculate the exact additional coverage area before re-transmitting. Cluster-based schema uses graph theory to group nodes into logical clusters former a hierarchy or re-broadcasts. Simulations results show that introduction of a simple counter-based schema drastically improve re-broadcast results. Information based on distance and location provides the greatest benefit in re-broadcast schemas. The paper also briefly introduces the blind terminal problem. --Andrew Davis From pj39@cornell.edu Thu Sep 12 12:04:53 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 g8CG4rh22208 for ; Thu, 12 Sep 2002 12:04:53 -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 MAA11149 for ; Thu, 12 Sep 2002 12:04:50 -0400 (EDT) Date: Thu, 12 Sep 2002 12:04:50 -0400 (EDT) From: pj39@cornell.edu X-Sender: pj39@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 9 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper on Broadcast Storm in MANET describes the broadcast storm problem in mobile ad-hoc networks caused by flooding and rebroadcasting of packets in most of the ad hoc routing protocols. Flooding results in contention and collisions and hence is a serious problem that is to be dealt with. The paper presents several schemes, namely probabilistic, counter-based, distance based, location-based and cluster-bassed schemes to alleviate this problem. If location information is known through GPS devices than the paper states that the location based scheme is th best choice as this scheme can eliminate more redundant broadcast under all kinds of host distributions without compromising on the reachability. The paper gives a good anaylisis of the solutions proposed. One of the shortcomings of this paper is analysis of a good value for P in the Probabilistic Scheme. The paper is based more on theoretical approach. It would nice to see the schemes presented in this paper applied to real ad-hoc networks. Future work could be directed towards schemes that used two more of the above five schemes presented by the authors (hybrid schemes). This might turn out to perform better than the five schemes proposed. From mvp9@cornell.edu Thu Sep 12 12:22:47 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 g8CGMkh25829 for ; Thu, 12 Sep 2002 12:22:46 -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 LAA15614 for ; Thu, 12 Sep 2002 11:33:11 -0400 (EDT) Date: Thu, 12 Sep 2002 11:33:11 -0400 (EDT) From: mvp9@cornell.edu X-Sender: mvp9@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 9 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Paper 9 presents an analysis of the problem of broadcast storms. First, the authors analyze the 3 main negative aspects - redundant content, channel contention and collision. The analytical results set up a framework of possibilities and limitations that illuminate the capabilities of their suggested solutions and results of the simulation. Then, five schemes are presented that attempt to reduce the wastes of broadcast storms by allowing a host to gauge when its rebroadcast is unnecessary and should be canceled. Finally all five schemes are simulated in networks of various density and their success on several metrics judged. According to the results, the location-based scheme is the best, although it has additional requirements (GPS or its analog, and extra computation). The merit of reducing broadcast storms is obvious. The schemes proposed are fairly simple and yet quite successful, at least in some limited circumstances. Different applications could require either 100% reachability or immediate distribution in which case the solutions are inadequate. Also, each scheme has its own drawbacks: The cluster-based one requires significant overhead - hence bandwidth - for maintaining clusters, assigning unique ID's, etc; the location-based one requires knowing exact locations which requires a means of getting those coordinates and updating them when hosts move (after all, this is a Manet, and they never mention the host's mobility in any respect); the distance-based scheme depends on measures like signal strength, which in the real world may not provide accurate numbers; the counter-based scheme depends on a natural pause to receive the broadcasts from neighbors, and it is not at all clear that such pauses would occur in the real world; finally the simplest method - using probability, is just too random - the ill effect of which can be seen in the simulation, where in lower density graphs, reachability goes way down. The simulation is informative, but the metrics could be modified to increase usefulness. For example, how much overhead is introduced over pure flooding by each of the methods? Also, why not directly measure the most relevant quantity - something like how much of node's time was saved by a given scheme? I.e. let each node broadcast X kilobytes and see how much faster this can be done with a chosen scheme over others or over pure flooding. Also, can their analysis and schemes be extended to other wireless network systems, ones with collision detection, or different network layer protocols altogether? From sc329@cornell.edu Thu Sep 12 12:31:10 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 g8CGVAh27966 for ; Thu, 12 Sep 2002 12:31:10 -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 MAA11972 for ; Thu, 12 Sep 2002 12:31:09 -0400 (EDT) Message-Id: <5.1.0.14.2.20020912122756.02e225c8@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 12 Sep 2002 12:31:11 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 9 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed submitted by : Sangeeth Chandrakumar The broadcast storm problem in a Mobile Ad Hoc Network Summary : Broadcasting is a frequent operation in any MANET. This paper discuss some of the problems due to redundant rebroadcasts, collisions and contention. THe authors assume that the mobile hosts share a common channel with CSMA, but no Collision detection. The analysis shows that a rebroadcast can provide only an additional coverage of 61% over the already covered by the previous transmissions. On an average, it reduces down to 41 %. Rebroadcast from different nodes could cause serious contention issues if the timings are not proper. In a dense network(when the number of hosts becomes greater than 6), there is a sharp decline in contention free hosts. Absence of RTS/CTS dialogue in a mobile network makes it harder to prevent collisions in case of rebroadcasts occurring simultaneously. The proposed solutions are either by reducing the probability of redundant broadcasts or by differentiating the timing of broadcasts. The various schemes proposed are: Probabilistic scheme - Nodes rebroadcast with a probability of P, 0 < P < 1. Counter based - The additional coverage area becomes very low, if the message has already been received a number of times. By keeping a threshold counter, rebroadcasts are inhibited by this approach. Distance based - If the distance between two nodes are smaller, the additional coverage area from a rebroadcast would be insignificant that it could be suppressed. Location based - Knowledge of precise location could help in better calculation of the coverage area. Cluster based - Hosts within a range are made part of a cluster and broadcast are done only by the elected leader and by the gateway hosts. Simulation of all these models are presented showing tradeoffs between Reachable area, saved rebroadcasts and coverage latency for various network density. The charts suggests locations based scheme to be better than the rest. Comments: - The measuring of distance from the signal strength may be difficult, or often violated, due to multipath fading and other interferences. - The locations based scheme assumes the tracking of location with a GPS. This may be hard to realize in many mobile equipments and may also infringe with personal privacy if used for civil purposes. - In the cluster based approach, there would significant overhead in the formation of cluster. The paper does not present any study on its significance. - Also none of the schemes take the mobility of hosts into account. Overall the paper presents some interesting facts and does lay the framework for further studies.