Performance Analysis of Probabilistic Flooding Using Random Graphs (bibtex)
by Konstantinos Oikonomou, Ioannis Stavrakakis
Abstract:
Probabilistic flooding (parameterized by a forwarding probability) has frequently been considered in the past, as a means of limiting the large message overhead associated with traditional (full) flooding approaches that are used to disseminate globally information in unstructured peer-to-peer and other networks. A key challenge in using probabilistic flooding is the determination of the forwarding probability so that global network outreach is achieved while keeping the message overhead as low as possible. By showing that a probabilistic flooding network generated by applying probabilistic flooding to a connected random graph network can be bounded by properly parameterized random graph networks and invoking random graph theory results, bounds on the value of the forwarding probability are derived guaranteeing global network outreach with high probability, while significantly reducing the message overhead. Bounds on the average number of messages - as well as asymptotic expressions - and on the average time required to complete network outreach are also derived, illustrating the benefits of the properly parameterized probabilistic flooding scheme.
Reference:
Konstantinos Oikonomou, Ioannis Stavrakakis, "Performance Analysis of Probabilistic Flooding Using Random Graphs", In 2007 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, pp. 1-6, 2007.
Bibtex Entry:
@inproceedings{oikonomou2007performance,
	Abstract = {Probabilistic flooding (parameterized by a forwarding probability) has frequently been considered in the past, as a means of limiting the large message overhead associated with traditional (full) flooding approaches that are used to disseminate globally information in unstructured peer-to-peer and other networks. A key challenge in using probabilistic flooding is the determination of the forwarding probability so that global network outreach is achieved while keeping the message overhead as low as possible. By showing that a probabilistic flooding network generated by applying probabilistic flooding to a connected random graph network can be bounded by properly parameterized random graph networks and invoking random graph theory results, bounds on the value of the forwarding probability are derived guaranteeing global network outreach with high probability, while significantly reducing the message overhead. Bounds on the average number of messages - as well as asymptotic expressions - and on the average time required to complete network outreach are also derived, illustrating the benefits of the properly parameterized probabilistic flooding scheme.},
	Author = {Oikonomou, Konstantinos and Stavrakakis, Ioannis},
	Booktitle = {2007 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks},
	Doi = {10.1109/WOWMOM.2007.4351694},
	Keywords = {own, refereed, ana},
	Month = {June},
	Pages = {1--6},
	Title = {{{Performance Analysis of Probabilistic Flooding Using Random Graphs}}},
	Venue = {Helsinki, Finland},
	Year = {2007},
	Bdsk-Url-1 = {https://doi.org/10.1109/WOWMOM.2007.4351694}}
Powered by bibtexbrowser