Flooding and Epidemic Routing
Contents |
Flooding
[Hutchinson-Patten-Unger-1986]
N. Hutchinson, T. Patten, and B. Unger,
“The Flooding Sink: A New Approach to Local Area Networking”,
Computer Networks and ISDN Systems
vol., 1986), pp. 1–14
Notes: This may be the first paper on controlled flooding.
[Farber-Parulkar-1986 (doi)]
David J. Farber and Gurudatta M. Parulkar,
“A Closer Look at Nohanet”,
Proceedings of ACM SIGCOMM 1986,
ACM SIGCOMM Computer Communication Review ,
vol.16,iss.3, Aug. 1986, pp. 204–213
ResiliNets Keywords: Redundant routing, flooding
Keywords:
Abstract: “Noahnet is a robust, highly available, high bandwidth local area network (LAN) architecture, in the implementation phase at the University of Delaware. Noahnet uses a distributed switch-oriented node topology, a flooding approach for message routing, and high bandwidth communication media. The purpose of this paper is to consider some of the important issues in detail such as: the various ways flood control can be implemented; their relative advantages/disadvantages; the functions of a node; and one possible implementation of a node in Noahnet. Expected performance of the Noahnet in comparison to Ethernet and token ring networks is also discussed. Though Noahnet uses more complex structure and protocol, we demonstrate that the overhead of using flooding in Noahnet is minimal and that a Noahnet node implementation is very simple and inexpensive. The paper concludes that Noahnet provides features such as robustness, high availability, high throughput, and high communication bandwidth at almost no additional cost.”
Notes:
[Parulkar-Sethi-Farber-1988 (doi) .]
Gurudatta M. Parulkar, Adarshpal S. Sethi, and David J. Farber,
“Performance Models for Nohanet”,
Proceedings of ACM SIGCOMM 1988,
ACM SIGCOMM Computer Communication Review ,
vol.18,iss.4, 1988, pp. 262–273
ResiliNets Keywords: Redundant routing, flooding
Keywords:
Abstract: “ Noahnet is an experimental flood local area network with features such as high reliability and high performance. Noahnet uses a randomly connected graph topology with four to five interconnections per node and a flooding protocol to route messages. The purpose of this paper is to present two analytical performance models which we have designed to understand the load-throughput behavior of Noahnet. Both models assume slotted Noahnet operation and also assume that if k messages attempt transmission in a slot, the network gets divided into k partitions of arbitrary sizes – one partition for each message. First, we show that the average number of successful messages in a slot given k partitions of transmissions is (M – k)/(N – 1), where N is the number of nodes in the network and M is the number of nodes out of N that participate in the flooding of k messages. This is an interesting result and is used in both models to derive the load-throughput equations. Each model is then presented using a set of assumptions, derivations of load-throughput equations, a set of plots, and the discussion of results. Models one and two differ in the way they account for retransmissions.”
Notes:
Epidemic Routing
[Vahdat-Becker-2000 .]
Amin Vahdat and David Becker,
Epidemic Routing for Partially-Connected Ad Hoc Networks,
Duke Technical Report CS-2000-06, Jul. 2000,
available from http://issg.cs.duke.edu/epidemic/epidemic.pdf
ResiliNets Keywords: Redundant epidemic routing
Keywords:
Abstract: “Mobile ad hoc routing protocols allow nodes with wireless adaptors to communicate with one another without any pre-existing network infrastructure. Existing ad hoc routing protocols, while robust to rapidly changing network topology, assume the presence of a connected path from source to destination. Given power limitations, the advent of short-range wireless networks, and the wide physical conditions over which ad hoc networks must be deployed, in some scenarios it is likely that this assumption is invalid. In this work, we develop techniques to deliver messages in the case where there is never a connected path from source to destination or when a network partition exists at the time a message is originated. To this end, we introduce Epidemic Routing, where random pair-wise exchanges of messages among mobile hosts ensure eventual message delivery. The goals of Epidemic Routing are to: i) maximize message delivery rate, ii) minimize message latency, and iii) minimize the total resources consumed in message delivery. Through an implementation in the Monarch simulator, we show that Epidemic Routing achieves eventual delivery of 100% of messages with reasonable aggregate resource consumption in a number of interesting scenarios.”
Notes:
