Compact routing with slack in low doubling dimension

ABSTRACT

We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek name-independent routing schemes with (1+ε) stretch and polylogarithmic storage at each node: since existing lower bound precludes such a scheme, we relax our guarantees to allow for (i) a small fraction of nodes to have large storage, say size of O(n log n) bits, or (ii) a small fraction of source-destination pairs to have larger, but still constant, stretch.

In this paper, given any constant ε ∈ (0,1), any δ ∈ Θ(1/ polylog n) and any connected edge-weighted undirected graph G with doubling dimension α ∈ O(log log n) and arbitrary node names, we present

1. 1. a (1+ε)-stretch name-independent routing scheme for G with polylogarithmic packet header size, and with (1-δ)n nodes storing polylogarithmic size routing tables each and the remaining δn nodes storing O(nlog n)-bit routing tables each.
2. 2. a name-independent routing scheme for G with polylogarithmic storage and packet header size, and with stretch (1+ε) for (1-α n source nodes and (9+ε) for the remaining α n source nodes.

.

These results are to be contrasted with our lower bound from PODC 2006, where we showed that stretch 9 is asymptotically optimal for name-independent compact routing schemes in networks of constant doubling dimension.

REFERENCES

• 1: Ittai Abraham , Yair Bartal , T-H. Hubert Chan , Kedar Dhamdhere Dhamdhere , Anupam Gupta , Jon Kleinberg , Ofer Neiman , Aleksandrs Slivkins, Metric Embeddings with Relaxed Guarantees, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.83-100, October 23-25, 2005 [doi>10.1109/SFCS.2005.51]
• 2: Ittai Abraham , Yair Bartal , Ofer Neimany, Advances in metric embedding theory, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132557]
• 3: Ittai Abraham , Yair Bartal , Ofer Neiman, Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.502-511, January 07-09, 2007, New Orleans, Louisiana
• 4: Ittai Abraham , Cyril Gavoille , Andrew V. Goldberg , Dahlia Malkhi, Routing in Networks with Low Doubling Dimension, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.75, July 04-07, 2006 [doi>10.1109/ICDCS.2006.72]
• 5: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: lower bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148143]
• 6: T.-H. Hubert Chan , Michael Dinitz , Anupam Gupta, Spanners with slack, Proceedings of the 14th conference on Annual European Symposium, p.196-207, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_20]
• 7: Hubert T-H. Chan , Anupam Gupta , Bruce M. Maggs , Shuheng Zhou, On hierarchical routing in doubling metrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Michael Dinitz, Compact routing with slack, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281114]
• 9: Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001 [doi>10.1145/568438.568451]
• 10: Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003 [doi>10.1007/s00446-002-0073-5]
• 11: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 12: Jon Kleinberg , Aleksandrs Slivkins , Tom Wexler, Triangulation and Embedding Using Small Sets of Beacons, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.444-453, October 17-19, 2004 [doi>10.1109/FOCS.2004.70]
• 13: Goran Konjevod , Andréa W. Richa , Donglin Xia, Optimal-stretch name-independent compact routing in doubling metrics, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146412]
• 14: Goran Konjevod , Andréa W. Richa , Donglin Xia, Optimal scale-free compact routing schemes in networks of low doubling dimension, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.939-948, January 07-09, 2007, New Orleans, Louisiana
• 15: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 16: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 17: Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073823]
• 18: Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007399]
• 19: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph labeling; Graph algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
compact routing, doubling dimension, name-indpendent routing, routing with slack