skip to main content
article

Controlled flooding search in a large network

Published: 01 April 2007 Publication History

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-to-live (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 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., successive TTL values are chosen from certain probability distributions rather than deterministic values), this ratio is asymptotically lower bounded by e. 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.

References

[1]
{1} D. Braginsky and D. Estrin, "Rumor routing algorithm for sensor networks," in Proc. Int. Conf. Distributed Computing Systems (ICDCS- 22), Vienna, Austria, 2002, pp. 563-570.
[2]
{2} J. Broch, D. Maltz, D. Johnson, Y. Hu, and J. Jetcheva, "A performance comparison of multi-hop wireless ad hoc network routing protocols," in Proc. 4th Annu. Int. Conf. Mobile Computing and Networking (MobiCom 98), Dallas, TX, Oct. 1998, pp. 85-97.
[3]
{3} J. Xie, R. Talpade, T. McAuley, and M. Liu, "AMRoute: Ad hoc multicast routing protocol," ACM Mobile Networks and Applications (MONET), Special Issue on Mobility of Systems, Users, Data and Computing, vol. 7, no. 6, pp. 429-439, Dec. 2002.
[4]
{4} C. Carter, S. Yi, P. Ratanchandani, and R. Kravets, "Manycast: Exploring the space between anycast and multicast in ad hoc networks," in Proc. 9th Annu. Int. Conf. Mobile Computing and Networking (MobiCom'03) , San Diego, CA, Sep. 2003, pp. 273-285.
[5]
{5} N. Chang and M. Liu, "Revisiting the TTL-based controlled flooding search: Optimality and randomization," in Proc. 10th Annu. Int. Conf. Mobile Computing and Networking (MobiCom'04), Philadelphia, PA, Sep. 2004, pp. 85-99.
[6]
{6} Y. Baryshinikov, E. Coffman, P. Jelenkovic, P. Momcilovic, and D. Rubenstein, "Flood search under the california split rule," Oper. Res. Lett., vol. 32, no. 3, pp. 199-206, May 2004.
[7]
{7} S. Ni, Y. Tseng, Y. Chen, and J. Sheu, "The broadcast storm problem in a mobile ad hoc network," in Proc. 5th Annu. Int. Conf. Mobile Computing and Networking (MobiCom'99), Seattle, WA, Aug. 1999, pp. 151-162.
[8]
{8} A. Borodin and R. El-Yaniv, Online Computation and Competetive Analysis. Cambridge, U.K.: Cambridge Univ. Press, 1998.
[9]
{9} S. Nash and A. Sofer, Linear and Nonlinear Programming. New York: McGraw-Hill, 1996.

Cited By

View all
  • (2018)Study of detection method for spoofed IP against DDoS attacksPersonal and Ubiquitous Computing10.1007/s00779-017-1097-y22:1(35-44)Online publication date: 1-Feb-2018
  • (2015)Pro-DiluvianProceedings of the 2nd ACM Conference on Information-Centric Networking10.1145/2810156.2810162(9-18)Online publication date: 30-Sep-2015
  • (2015)Hybrid Search Scheme for Social Networks Supported by Dynamic Weighted Distributed Label ClusteringIEEE Transactions on Computers10.1109/TC.2014.237825464:9(2586-2594)Online publication date: 1-Sep-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 2
April 2007
232 pages

Publisher

IEEE Press

Publication History

Published: 01 April 2007
Published in TON Volume 15, Issue 2

Author Tags

  1. best worst-case performance
  2. competitive ratio
  3. controlled flooding search
  4. query and search
  5. randomized strategy
  6. time-to-live (TTL)
  7. wireless networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Study of detection method for spoofed IP against DDoS attacksPersonal and Ubiquitous Computing10.1007/s00779-017-1097-y22:1(35-44)Online publication date: 1-Feb-2018
  • (2015)Pro-DiluvianProceedings of the 2nd ACM Conference on Information-Centric Networking10.1145/2810156.2810162(9-18)Online publication date: 30-Sep-2015
  • (2015)Hybrid Search Scheme for Social Networks Supported by Dynamic Weighted Distributed Label ClusteringIEEE Transactions on Computers10.1109/TC.2014.237825464:9(2586-2594)Online publication date: 1-Sep-2015
  • (2014)P2P resource searching with Cloning Random Walker assisted by Weakly Connected Dominating SetThe Journal of Supercomputing10.1007/s11227-013-1046-068:1(443-458)Online publication date: 1-Apr-2014
  • (2011)Resource searching in an unstructured P2P network based on Cloning Random Walker assisted by Dominating SetComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.10.01455:3(722-733)Online publication date: 1-Feb-2011
  • (2011)Parsimonious flooding in dynamic graphsDistributed Computing10.1007/s00446-011-0133-924:1(31-44)Online publication date: 1-Sep-2011
  • (2009)Level biased random walk for information discovery in wireless sensor networksProceedings of the 2009 IEEE international conference on Communications10.5555/1817770.1818209(5036-5041)Online publication date: 14-Jun-2009
  • (2009)BF-chordProceedings of the 5th International Conference on Wireless communications, networking and mobile computing10.5555/1737966.1738160(2830-2833)Online publication date: 24-Sep-2009
  • (2009)Parsimonious flooding in dynamic graphsProceedings of the 28th ACM symposium on Principles of distributed computing10.1145/1582716.1582757(260-269)Online publication date: 10-Aug-2009
  • (2008)Coverage based expanding ring search for dense wireless sensor networksProceedings of the 15th international conference on High performance computing10.5555/1791889.1791918(245-256)Online publication date: 17-Dec-2008
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media