Weak state routing for large scale dynamic networks

ABSTRACT

Routing in communication networks involves the indirection from a persistent name (or ID) to a locator and delivering packets based upon the locator. In a large-scale, highly dynamic network, the ID-to-locator mappings are both large in number, and change often. Traditional routing protocols require high overhead to keep these in directions up-to-date. In this paper, we propose Weak State Routing (WSR), a routing mechanism for large-scale highly dynamic networks. WSR's novelty is that it uses random directional walks biased occasionally by weak indirection state information in intermediate nodes. The indirection state information is weak, i.e. interpreted not as absolute truth, but as probabilistic hints. Nodes only have partial information about the region a destination node is likely to be. This method allows us to aggregate information about a number of remote locations in a geographic region. In other words, the state information maps a set-of-IDs to a it geographical region. The intermediate nodes receiving the random walk use a method similar to longest-prefix-match in order to prioritize their mappings to decide how to bias and forward the random walk. WSR can also be viewed as an unstructured distributed hashing technique. WSR displays good rare-object recall with scalability properties similar to structured DHTs, albeit with more tolerance to dynamism and without constraining the degree distribution of the underlying network.

Through simulations, we show that WSR offers a high packet delivery ratio, more than 98%. The control packet overhead incurred in the network scales as O(N) for N-node networks. The number of mappings stored in the network appears to scale as Θ(N^(3/2)). We compare WSR with Dynamic Source Routing (DSR) and geographic forwarding (GPSR) combined with Grid Location Service (GLS). Our results indicate that WSR delivers more packets with less overhead at the cost of increased path length.

REFERENCES

• 1: Hls patch for ns-2.29. http://www.cn.uni-duesseldorf.de/staff/kiess/software/hls-ns2-patch.
• 2: Network simulator. ns-2. http://www.isi.edu/nsnam/ns.
• 3: BISNIK, N., AND ABOUZEID, A. A. Capacity deficit in mobile wireless ad hoc networks due to geographic routing overheads. In 26th IEEE International Conference on Computer Communications (INFOCOM'07). (2007), pp. 517--525.
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: Matthew Caesar , Miguel Castro , Edmund B. Nightingale , Greg O'Shea , Antony Rowstron, Virtual ring routing: network routing inspired by DHTs, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
• 6: CHAWATHE, Y., RATNASAMY, S., BRESLAU, L., LANHAM, N., AND SHENKER, S. Making gnutella-like p2p systems scalable. Computer Communication Review 33, 4 (2003), 407--418.
• 7: Bow-nan Cheng , Murat Yuksel , Shivkumar Kalyanaraman, Orthogonal Rendezvous Routing Protocol for Wireless Mesh Networks, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.106-115, November 12-15, 2006 [doi>10.1109/ICNP.2006.320204]
• 8: Henri Dubois-Ferriere , Matthias Grossglauser , Martin Vetterli, Age matters: efficient route discovery in mobile ad hoc networks using encounter ages, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778446]
• 9: GKANTSIDIS, C., MIHAIL, M., AND SABERI, A. Random walks in peer-to-peer networks. Proceedings - IEEE INFOCOM 1 (2004), 120--130.
• 10: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 11: Matthias Grossglauser , Martin Vetterli, Locating mobile nodes with EASE: learning efficient routes from encounter histories alone, IEEE/ACM Transactions on Networking (TON), v.14 n.3, p.457-469, June 2006 [doi>10.1109/TNET.2006.876204]
• 12: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 13: JOHNSON, D. B., AND MALTZ, D. A. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, T. Imielinski and H. Korth, Eds., vol. 353. Kluwer Academic Publishers, 1996.
• 14: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 15: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 16: Wolfgang Kieß , Holger Füßler , Jörg Widmer , Martin Mauve, Hierarchical location service for mobile ad-hoc networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.4, p.47-58, October 2004 [doi>10.1145/1052871.1052875]
• 17: KUMAR, A., XU, J., AND ZEGURA, E. W. Efficient and scalable query routing for unstructured peer-to-peer networks. Proceedings of IEEE INFOCOM 2 (2005), 1162--1173.
• 18: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 19: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 20: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 21: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.161-172, October 2001
• 22: RHEA, S. C., AND KUBIATOWICZ, J. Probabilistic location and routing. Proceedings - IEEE INFOCOM 3 (2002), 1248--1257.
• 23: SANTIVANEZ, C., AND RAMANATHAN, R. Hazy sighted link state (hsls) routing: A scalable link state algorithm. Tech. Rep. BBN-TM-1301, BBN Technologies, Cambridge, MA, 2001.
• 24: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 25: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.149-160, October 2001
• 26: Yong Wang , Sushant Jain , Margaret Martonosi , Kevin Fall, Erasure-coding based routing for opportunistic networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.229-236, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080140]
• 27: YOON, J., LIU, M., AND NOBLE, B. Random waypoint considered harmful. Proceedings - IEEE INFOCOM 2 (2003), 1312--1321.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Performance

Keywords:
dynamic networks, routing algorithms, unstructured distributed hashing, weak states