Sparse spanners vs. compact routing

ABSTRACT

Routing with multiplicative stretch 3 (which means that the path used by the routing scheme can be up to three times longer than a shortest path) can be done with routing tables of Θ(√n) bits per node. The space lower bound is due to the existence of dense graphs with large girth. Dense graphs can be sparsified to subgraphs, called spanners, with various stretch guarantees. There are spanners with additive stretch guarantees (some even have constant additive stretch) but only very few additive routing schemes are known.

In this paper, we give reasons why routing in unweighted graphs with additive stretch is difficult in the form of space lower bounds for general graphs and for planar graphs. We prove that any routing scheme using routing tables of size μ bits per node and addresses of poly-logarithmic length has additive stretch Ω(√n/μ) for general graphs, and Ω(√n/μ) for planar graphs. Routing with tables of size O(n^1/3) thus requires a polynomial additive stretch Ω(n^1/3), whereas spanners with average degree O(n^1/3) and constant additive stretch exist for all graphs. Spanners, however sparse they are, do not tell us how to route. These bounds provide the first separation of sparse spanner problems and compact routing problems.

On the positive side, we give an almost tight upper bound: we present the first non-trivial compact routing scheme with o(log²n)-bit addresses, additive stretch O(n^1/3), and table size O(n^1/3) bits for all graphs with linear local tree-width such as planar, bounded-genus, and apex-minor-free graphs. Note: Asymptotic notation in this abstract suppresses factors logarithmic in n.

References

1. I. Abraham and C. Gavoille. Object location using path separators. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, July 23-26, 2006, pages 188--197, 2006.
2. I. Abraham, C. Gavoille, A. V. Goldberg, and D. Malkhi. Routing in networks with low doubling dimension. In 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006), 4-7 July 2006, Lisboa, Portugal, page 75, 2006.
3. I. Abraham, C. Gavoille, and D. Malkhi. Compact routing for graphs excluding a fixed minor. In DISC, pages 442--456, 2005.
4. I. Abraham, C. Gavoille, D. Malkhi, N. Nisan, and M. Thorup. Compact name-independent routing with minimum stretch. ACM Transactions on Algorithms, 4(3), 2008. Announced at SPAA 2004.
5. I. Abraham, C. Gavoille, D. Malkhi, and U. Wieder. Strong-diameter decompositions of minor free graphs. In SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, California, USA, June 9-11, 2007, pages 16--24, 2007.
6. I. Althöfer, G. Das, D. P. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81--100, 1993.
7. M. Arias, L. Cowen, K. A. Laing, R. Rajaraman, and O. Taka. Compact routing with name independence. SIAM J. Discrete Math., 20(3):705--726, 2006. Announced at SPAA 2003.
8. B. Awerbuch, A. B. Noy, N. Linial, and D. Peleg. Improved routing strategies with succinct tables. Journal of Algorithms, 11(3):307--341, 1990.
9. B. Awerbuch and D. Peleg. Sparse partitions (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, 22-24 October 1990, St. Louis, Missouri, USA, pages 503--513, 1990.
10. S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie. Additive spanners and (α,β)-spanners. ACM Transactions on Algorithms, 7(1), Nov. 2010.
11. F. Bazzaro and C. Gavoille. Localized and compact data-structure for comparability graphs. Discrete Mathematics, 309(11):3465--3484, June 2009.
12. B. Bollobás, D. Coppersmith, and M. L. Elkin. Sparse distance preservers and additive spanners. In Symposium on Discrete Algorithms (SODA), 2003.
13. A. Brady and L. J. Cowen. Compact routing on power law graphs with additive stretch. In 8th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 119--128, Jan. 2006.
14. A. Brady and L. J. Cowen. Exact distance labelings yield additive-stretch compact routing schemes. In $20^th$ International Symposium on Distributed Computing (DISC), volume 4167 of Lecture Notes in Computer Science, pages 339--354. Springer, Sept. 2006.
15. C. Busch, R. LaFortune, and S. Tirthapura. Improved sparse covers for graphs excluding a fixed minor. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12--15, 2007, pages 61--70, 2007.
16. W. Chen, C. Sommer, S.-H. Teng, and Y. Wang. Compact routing in power-law graphs. In Distributed Computing, 23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings, pages 379--391, 2009.
17. V. D. Chepoi, F. F. Dragan, B. Estellon, M. Habib, and Y. Vaxès. Additive spanners and distance and routing labeling schemes for hyperbolic graphs, 2009. preprint.
18. V. D. Chepoi, F. F. Dragan, and Y. Vaxès. Distance and routing labeling schemes for non-positively curved plane graphs. Journal of Algorithms, 61(2):60--88, 2006.
19. E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28(1):210--236, 1998. Announced at FOCS 1993.
20. L. Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38(1):170--183, 2001. Announced at SODA 1999.
21. E. D. Demaine and M. Hajiaghayi. Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In 14th Symposium on Discrete Algorithms (SODA), pages 840--849. ACM-SIAM, Jan. 2004.
22. E. D. Demaine, M. Hajiaghayi, and K. Kawarabayashi. Approximation algorithms via structural results for apex-minor-free graphs. In 36th International Colloquium on Automata, Languages and Programming (ICALP), volume 5555 of Lecture Notes in Computer Science, pages 316--327. Springer, July 2009.
23. Y. Dourisboure. Compact routing schemes for bounded tree-length graphs and for k-chordal graphs. In Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004, Proceedings, pages 365--378, 2004.
24. Y. Dourisboure and C. Gavoille. Improved compact routing scheme for chordal graphs. In Distributed Computing, 16th International Conference, DISC 2002, Toulouse, France, October 28-30, 2002 Proceedings, pages 252--264, 2002.
25. F. F. Dragan and I. Lomonosov. On compact and efficient routing in certain graph classes. Discrete Applied Mathematics, 155(11):1458--1470, 2007.
26. F. F. Dragan, C. Yan, and D. G. Corneil. Collective tree spanners and routing in AT-free related graphs. In 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 3353 of Lecture Notes in Computer Science. Springer, June 2004. 68--80.
27. M. L. Elkin and D. Peleg. (1+ε, β)-spanner constructions for general graphs. SIAM Journal on Computing, 33(3):608--631, 2004.
28. M. Enachescu, M. Wang, and A. Goel. Reducing maximum stretch in compact routing. In INFOCOM 2008. 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 13-18 April 2008, Phoenix, AZ, USA, pages 336--340, 2008.
29. D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27(3):275--291, 2000.
30. U. Feige, M. T. Hajiaghayi, and J. R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629--657, 2008. Announced at STOC 2005.
31. P. Fraigniaud and C. Gavoille. Routing in trees. In Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings, pages 757--772, 2001.
32. P. Fraigniaud and C. Gavoille. A space lower bound for routing in trees. In STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings, pages 65--75, 2002.
33. P. Fraigniaud, E. Lebhar, and L. Viennot. The inframetric model for the internet. In 27th Annual IEEE Conference on Computer Communications (INFOCOM), pages 1085--1093, Apr. 2008.
34. G. N. Frederickson and R. Janardan. Designing networks with compact routing tables. Algorithmica, 3:171--190, 1988.
35. C. Gavoille. Routing in distributed networks: overview and open problems. SIGACT News, 32(1):36--52, 2001.
36. C. Gavoille and M. Gengler. Space-efficiency of routing schemes of stretch factor three. Journal of Parallel and Distributed Computing, 61(5):679--687, 2001.
37. C. Gavoille and N. Hanusse. Compact routing tables for graphs of bounded genus. In Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings, pages 351--360, 1999.
38. C. Gavoille, M. Katz, N. A. Katz, C. Paul, and D. Peleg. Approximate distance labeling schemes. In Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings, pages 476--487, 2001.
39. C. Gavoille and D. Peleg. The compactness of interval routing for almost all graphs. SIAM Journal on Computing, 31(3):706--721, 2001.
40. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. Distance labeling in graphs. J. Algorithms, 53(1):85--112, 2004. Announced at SODA 2001.
41. C. Gavoille and S. Pérennès. Memory requirement for routing in distributed networks. In 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 125--133. ACM Press, May 1996.
42. K. Iwama and A. Kawachi. Compact routing with stretch factor of less than three. IEICE Transactions, 88-D(1):47--52, 2005. Announced at PODC 2000.
43. K. Iwama and M. Okita. Compact routing for flat networks. In Distributed Computing, 17th International Conference, DISC 2003, Sorrento, Italy, October 1-3, 2003, Proceedings, pages 196--210, 2003.
44. K. Kawarabayashi. Planarity allowing few error vertices in linear time. In 50st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 639--648. IEEE Computer Society Press, Oct. 2009.
45. G. Konjevod, A. W. Richa, and D. Xia. Optimal scale-free compact routing schemes in networks of low doubling dimension. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 939--948, 2007.
46. S. Kutten and D. Peleg. Fast distributed construction of small k-dominating sets and applications. Journal of Algorithms, 28(1):40--66, 1998. Announced at PODC 1995.
47. K. A. Laing. Name-independent compact routing in trees. Inf. Process. Lett., 103(2):57--60, 2007. Announced at PODC 2004.
48. K. A. Laing and R. Rajaraman. A space lower bound for name-independent compact routing in trees. Journal of Interconnection Networks, 8(3):229--251, 2007. Announced at SPAA 2005.
49. H.-I. Lu. Improved compact routing tables for planar networks via orderly spanning trees. SIAM J. Discrete Math., 23(4):2079--2092, 2010. Announced at COCOON 2002.
50. D. Peleg. Proximity-preserving labeling schemes. J. Graph Theory, 33(3):167--176, 2000. Announced at WG 1999.
51. D. Peleg and A. A. Schaffer. Graph spanners. Journal of Graph Theory, 13(1):99--116, 1989.
52. D. Peleg and E. Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510--530, July 1989. Announced at STOC 1988.
53. S. Pettie. Low distortion spanners. In Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, pages 78--89, 2007.
54. M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993--1024, 2004. Announced at FOCS 2001.
55. M. Thorup and U. Zwick. Compact routing schemes. In SPAA, pages 1--10, 2001.
56. M. Thorup and U. Zwick. Approximate distance oracles. Journal of the ACM, 52(1):1--24, 2005. Announced at STOC 2001.
57. M. Thorup and U. Zwick. Spanners and emulators with sublinear distance errors. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 802--809, 2006.
58. D. P. Woodruff. Lower bounds for additive spanners, emulators, and more. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 389--398, 2006.
59. D. P. Woodruff. Additive spanners in nearly quadratic time. In 37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6198 of Lecture Notes in Computer Science (ARCoSS), pages 463--474. Springer, July 2010.

Index Terms

• Networks

  • Network protocols

    • Network layer protocols

      • Routing protocols

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems