Flooding

[[Lesser-Rom-1990] .]

Lesser, O.; Rom, R.,
“Routing by controlled Flooding in communication Networks”,
INFOCOM, vol.3, #3, June 1990, pp. 910-917

ResiliNets Keywords: Flooding, Controlled Flooding

Keywords: Flooding;Controlled Flooding

Abstract: "A controlled flooding scheme for computer networks that retains the desired properties of flooding yet limits the extend of message flooding through the network is proposed. This is done by assigning costs for link traversal and allowing a packet to expend only a limited total cost for network traversal. A performance criterion is proposed, and the problem of assigning costs to links so that optimal performance is achieved is considered. The optimal assignment problem is characterized for networks with both homogeneous and heterogeneous traffic patterns. The latter, being computationally complex, can efficiently be solved only by heuristic algorithms, one of which is outlined."

[[Ni-Tseng-Chen-Sheu-1999] .]

Ni,Tseng,Chen,Sheu
“The Broadcast Storm Problem in Mobile Ad Hoc Network”,
Mobicom,1999, pp. 302-313

ResiliNets Keywords: Flooding,Broadcast Storm Problem

Keywords: Flooding;Broadcast Storm Problem

Abstract: "Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in particular,due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we refer as the broadcast storm problem. In this paper, we identify this problem by showing how serious it is through analyses and simulations. We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem. Simulation results are presented, which show different levels of improvement over the basic flooding approach"

[[Chang-Liu-2007] .]

Chang,Liu
“Controlled Flooding Search in Large Network”,
IEEE/ACM,2007,vol 15

ResiliNets Keywords: Flooding,Worst-case performance

Keywords: Flooding;Worst-case performance

Abstract: "In this paper,we consider the problem of searching for a node or an object (i.e., piece of data, file, etc.) in a large network. Applications of this problem include searching for a destination node in a mobile ad hoc network, querying for a piece of desired data in a wireless sensor network, and searching for a shared file in an unstructured peer-to-peer network.We consider the class of controlled flooding search strategies where query/search packets are broadcast and propagated in the network until a preset time-tolive (TTL) value carried in the packet expires. Every unsuccessful search attempt, signified by a timeout at the origin of the search, results in an increased TTL value (i.e., larger search area) and the same process is repeated until the object is found. The primary goal of this study is to find search strategies (i.e., sequences of TTL values) that will minimize the cost of such searches associated with packet transmissions. Assuming that the probability distribution of the object location is not known a priori,we derive search strategies that minimize the search cost in the worst-case, via a performance measure in the form of the competitive ratio between the average search cost of a strategy and that of an omniscient observer. This ratio is shown in prior work to be asymptotically (as the network size grows to infinity) lower bounded by 4 among all deterministic search strategies. In this paper, we show that by using randomized strategies (i.e., successiveTTL values are chosen from certain probability distributions rather than deterministic values), this ratio is asymptotically lower bounded by .We derive an optimal strategy that achieves this lower bound, and discuss its performance under other criteria. We further introduce a class of randomized strategies that are sub-optimal but potentially more useful in practice"

[[McQuillen-Richer-Rosen-1980] .]

McQuillen,Richer,Rosen
“The New Routing Algorithm for the ARPANET”,
IEEE,May 1980,vol 5

ResiliNets Keywords: Flooding,ARPANET Keywords: Flooding;ARPANET

Abstract: "The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term looorp so scillations.In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the databased escribing the network to generate a tree representing the minimum delay pathsfr om a given root node to every other network node.Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner.An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are 60th less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas"

[[Rahman-Olesinski-Gburzynski-2004] .]

Rahman,Olesinski,Gburzynski
“Controlled Flooding in Wireless Ad-hoc Network”,
IEEE,Volume31, May-3 June 2004 Page(s): 73 - 78

ResiliNets Keywords: Flooding,Controlled Flooding Keywords: Flooding;Controlled Flooding

Abstract: "We show how flooding can be adopted as a reliable and efficient routing scheme in ad-hoc wireless mobile networks. It turns out that, with the assistance of some tunable heuristics, flooding is not necessarily inferior to sophisticated point-to-point forwarding schemes, at least for some classes of wireless applications. We discuss a reactive broadcast-based ad-hoc routing protocol in which flooding exhibits a tendency to converge to a narrow strip of nodes along the shortest path between source and destination. The width of this strip can be adjusted automatically or by the user, e.g., in response to varying node density and mobility patterns. Finally, we point out a certain deficiency inherent in the IEEE 802.11 family of collision avoidance schemes and show how to fix it to provide better service to broadcast-based routing schemes represented by our variant of controlled flooding."