Sergio D. Servetto
ABSTRACT
We consider a routing problem in the context of large scale networks with uncontrolled dynamics. A case of uncontrolled dynamics that has been studied extensively is that of mobile nodes, as this is typically the case in cellular and mobile ad-hoc networks. In this paper however we study routing in the presence of a different type of dynamics: nodes do not move, but instead switch between active and inactive states at random times. Our interest in this case is motivated by the behavior of sensor nodes powered by renewable sources, such as solar cells or ambient vibrations. In this paper we formalize the corresponding routing problem as a problem of constructing suitably constrained random walks on random dynamic graphs. We argue that these random walks should be designed so that their resulting invariant distribution achieves a certain load balancing property, and we give simple distributed algorithms to compute the local parameters for the random walks that achieve the sought behavior. A truly novel feature of our formulation is that the algorithms we obtain are able to route messages along all possible routes between a source and a destination node, without performing explicit route discovery/repair computations, and without maintaining explicit state information about available routes at the nodes. To the best of our knowledge, these are the first algorithms that achieve true multipath routing (in a statistical sense), at the complexity of simple stateless operations.
- E. Ayanoglu, C.-L. I, R. D. Gitlin, and J. E. Mazo. Diversity Coding for Self-Healing and Fault-Tolerant Communication Networks. IEEE Trans. Commun., COM-41(11):1677--1686, 1993.Google Scholar
- A. Banerjea. On the Use of Dispersity Routing for Fault Tolerant Realtime Channels. European Trans. Telecommun., 8(4):393--407, 1997.Google ScholarCross Ref
- D. Bertsekas and R. Gallager. Data Networks (2nd ed). Prentice Hall, 1992. Google ScholarDigital Library
- U. Black. IP Routing Protocols (RIP, OSPF, BGP, PNNI & CISCO routing protocols). Prentice Hall, 2000. Google ScholarDigital Library
- S. Chen and K. Nahrstedt. Distributed Quality of Service Routing in Ad-Hoc Networks. IEEE J. Select. Areas Commun., 17(8):1488--1505, 1999. Google ScholarDigital Library
- S.-N. Chiou. Dispersity Routing and Reliability in a Communication Network. PhD thesis, University of Southern California, 1988.Google Scholar
- T. M. Cover and J. Thomas. Elements of Information Theory. John Wiley and Sons, Inc., 1991. Google ScholarDigital Library
- D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly-Resilient, Energy-Efficient Multipath Routing in Wireless Sensor Networks. ACM Mobile Computing and Communications Review, 5(4):11--29, 2001. Google ScholarDigital Library
- D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. B. Wicker. An Empirical Study of Epidemic Algorithms in Large Scale Multihop Wireless Networks. UCLA Computer Science Technical Report UCLA/CSD-TR 02-0013. Submitted for publication.Google Scholar
- P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Inform. Theory, 46(2):388--404, 2000. Google ScholarDigital Library
- B. Hajek. Minimum Mean Hitting Times of Brownian Motion with Constrained Drift. In Proc. 27th Conf. Stoch. Proc. App., Cambridge, England, 2001.Google Scholar
- D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In T. Imielinsky and H. Korth, editors, Mobile Computing. Kluwer Academic Publishers, 1996.Google ScholarCross Ref
- E. C. Kan, Z. Liu, P. Wang, M. Kim, Y. N. Shen, and G. Pei. Si Fleas: Technology Demonstration of Functional Modules in Submillimeter Autonomous Microsystems. Invited talk, Ninth Foresight Conference on Molecular Nanotechnology, Santa Clara, CA, Nov. 9-11, 2001.Google Scholar
- F. P. Kelly. Network Routing. Phil. Trans. R. Soc. Lond. A, 337:343--363, 1991.Google ScholarCross Ref
- J. Kleinberg. Approximation Algorithms for Disjoint Paths Problems. PhD thesis, Massachusetts Institute of Technology, 1996. Google ScholarDigital Library
- J. Kleinberg. The Small-World Phenomenon: An Algorithmic Perspective. Technical Report 99-1776, Dept. of Computer Science, Cornell University, October 1999. Google ScholarDigital Library
- N. Maxemchuk. Dispersity Routing in Store and Forward Networks. PhD thesis, University of Pennsylvania, 1975.Google Scholar
- N. Maxemchuk and M. El Zarki. Routing and Flow Control in High-Speed Networks. Proc. IEEE, 78(1):204--221, 1990.Google ScholarCross Ref
- J. M. McQuillan, I. Richer, and E. C. Rosen. The New Routing Algorithm for the ARPANET. IEEE Trans. Commun., COM-28(5):711--719, 1980.Google Scholar
- M. Medard, S. G. Finn, R. A. Barry, and R. G. Gallager. Redundant Trees for Preplanned Recovery in Arbitrary Vertex-Redundant or Edge-Redundant Graphs. IEEE/ACM Trans. Networking, 7(5):641--652, 1999. Google ScholarDigital Library
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google ScholarDigital Library
- A. Nasipuri and S. R. Das. On-Demand Multipath Routing for Mobile Ad-Hoc Networks. In Proc. 8th Int. Conf. Comp. Comm. Networks (IC3N), Boston, MA, 1999.Google ScholarCross Ref
- V. D. Park and M. S. Corson. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. In Proc. IEEE INFOCOM, Kobe, Japan, 1997. Google ScholarDigital Library
- M. R. Pearlman and Z. J. Haas. Determining the Optimal Configuration for the Zone Routing Protocol. IEEE J. Select. Areas Commun., 17(8):1395--1414, 1999. Google ScholarDigital Library
- C. E. Perkins and E. M. Royer. Ad-Hoc On-Demand Distance Vector Routing. In Proc. 2nd IEEE Workshop Mobile Comp. Syst. Applic., New Orleans, LA, 1999. Google ScholarDigital Library
- G. J. Pottie and W. Kaiser. Wireless Sensor Networks. Comm. ACM, 43(5):51--58, 2000. Google ScholarDigital Library
- L. C. G. Rogers and D. Williams. Diffusions, Markov Processes and Martingales---Volume I: Foundations. Cambridge University Press, 2000.Google Scholar
- A. Scaglione and S. D. Servetto. On the Interdependence of Routing and Data Compression in Multi-Hop Sensor Networks. In Proc. ACM MobiCom, Atlanta, GA, 2002. Google ScholarDigital Library
- I. Stoica, S. Shenker, and H. Zhang. Core-Stateless Fair Queueing: a Scalable Architecture to Approximate Fair Bandwidth Allocations in High Speed Networks. In Proc. ACM SIGCOMM, 1998. Google ScholarDigital Library
- S. H. Strogatz. Exploring Complex Networks. Nature, 410:268--276, 2001.Google ScholarCross Ref
- D. J. Watts. Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton University Press, 1999. Google ScholarDigital Library
Index Terms
- Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks
Recommendations
Coalescing-branching random walks on graphs
SPAA '13: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architecturesWe study a distributed randomized information propagation mechanism in networks we call the coalescing-branching random walk (cobra walk, for short). A cobra walk is a generalization of the well-studied "standard" random walk, and is useful in modeling ...
Multiple Random Walks in Random Regular Graphs
We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs. The cover time of a random walk on a random $r$-regular ...
Pseudorandom generators from polarizing random walks
CCC '18: Proceedings of the 33rd Computational Complexity ConferenceWe propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1, 1]n. ...
Comments