Bounding the locality of distributed routing algorithms

ABSTRACT

We examine bounds on the locality of routing. A local routing algorithm makes a sequence of distributed forwarding decisions, each of which is made using only local information. Specifically, in addition to knowing the node for which a message is destined, an intermediate node might also know a) the subgraph corresponding to all network nodes within k hops of itself, for some value of k, b) the node from which the message originated, and c) which of its neighbours last forwarded the message. Our objective is to determine which of these parameters are necessary and/or sufficient to permit local routing as k varies on a network modelled by a connected undirected graph. In particular, we establish tight bounds on k for the feasibility of deterministic k-local routing for various combinations of these parameters, as well as corresponding bounds on dilation (the worst-case ratio of actual route length to shortest path length).

REFERENCES

• 1: P. Bose, A. Brodnik, S. Carlsson, E. D. Demaine, R. Fleischer, A. López-Ortiz, P. Morin, and I. Munro. Online routing in convex subdivisions. International Journal of Computational Geometry and Applications, 12(4):283--295, 2002.
• 2: P. Bose and P. Morin. Online routing in triangulations. SIAM Journal on Computing, 33(4):937--951, 2004.
• 3: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 4: Mark Braverman, On ad hoc routing with guaranteed delivery, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400809]
• 5: E. Chávez , S. Dobrev , E. Kranakis , J. Opatrny , L. Stacho , J. Urrutia, Route discovery with constant memory in oriented planar geometric networks, Networks, v.48 n.1, p.7-15, August 2006 [doi>10.1002/net.v48:1]
• 6: S. Durocher, D. Kirkpatrick, and L. Narayanan. On routing with guaranteed delivery in three-dimensional ad hoc wireless networks. Wireless Networks, 2008. To appear.
• 7: G. G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI/RR-87-180, Information Sciences Institute, 1987.
• 8: R. Flury and R. Wattenhofer. Randomized 3D geographic routing. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), pages 834--842, 2008.
• 9: M. Fraser. Local routing on tori. In Proceedings of the Conference on Ad-Hoc, Mobile, and Wireless Networks, volume 4686 of Lecture Notes in Computer Science, pages 1--14. Springer, 2007.
• 10: M. Fraser, E. Kranakis, and J. Urrutia. Memory requirements for local geometric routing and traversal in digraphs. In Proceedings of the Canadian Conference on Computational Geometry (CCCG), volume 20, 2008.
• 11: E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proceedings of the Canadian Conference on Computational Geometry (CCCG), volume 11, pages 51--54, 1999.
• 12: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 13: I. Stojmenović. Position based routing in ad hoc networks. IEEE Communications Magazine, 40(7):128-134, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication; Distributed networks

General Terms:
Algorithms, Theory

Keywords:
dilation, distributed algorithms, local routing