Wei Chen
Abstract
Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of an actual shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick [2001] to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello et al. [2000]. Our result is the first analytical bound coupled to the parameter of the power-law graph model for a compact routing scheme.
Let n denote the number of nodes in the network. We provide a labeled routing scheme that, after a stretch--5 handshaking step (similar to DNS lookup in TCP/IP), routes messages along stretch--3 paths. We prove that, instead of routing tables with Õ(n1/2) bits (Õ suppresses factors logarithmic in n) as in the general scheme by Thorup and Zwick, expected sizes of O(nγ log n) bits are sufficient, and that all the routing tables can be constructed at once in expected time O(n1+γ log n), with γ = τ-22/τ-3 + ε, where τ∈(2,3) is the power-law exponent and ε 0 (which implies ε < γ < 1/3 + ε). Both bounds also hold with probability at least 1-1/n (independent of ε). The routing scheme is a labeled scheme, requiring a stretch--5 handshaking step. The scheme uses addresses and message headers with O(log n log log n) bits, with probability at least 1-o(1). We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs.
With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick [2001, 2005] for stretch-3 and we obtain a new upper bound of expected Õ(n1+γ) for space and preprocessing for random power-law graphs. Our distance oracle is the first one optimized for power-law graphs. Furthermore, we provide a linear-space data structure that can answer 5--approximate distance queries in time at most Õ(n1/4+ε) (similar to γ, the exponent actually depends on τ and lies between ε and 1/4 + ε).
Supplemental Material
Available for Download
Supplemental movie, appendix, image and software files for, A compact routing scheme and approximate distance oracle for power-law graphs
- Abraham, I., Gavoille, C., Goldberg, A. V., and Malkhi, D. 2006a. Routing in networks with low doubling dimension. In Proceedings of the 26th International Conference on Distributed Computing Systems (ICDCS). Google Scholar
Digital Library
- Abraham, I., Gavoille, C., and Malkhi, D. 2005. Compact routing for graphs excluding a fixed minor. In Proceedings of the 19th International Symposium on Distributed Computing (DISC). 442--456. Google ScholarDigital Library
- Abraham, I., Gavoille, C., and Malkhi, D. 2006b. On space-stretch trade-offs: Lower bounds. In Proceedings of the 18th ACM Symposium on Parallel Algorithms and Architectures (SPAA). 207--216. Google ScholarDigital Library
- Abraham, I., Gavoille, C., and Malkhi, D. 2006c. On space-stretch trade-offs: Upper bounds. In Proceedings of the 18th ACM Symposium on Parallel Algorithms and Architectures (SPAA). 217--224. Google ScholarDigital Library
- Abraham, I., Gavoille, C., Malkhi, D., Nisan, N., and Thorup, M. 2008. Compact name-independent routing with minimum stretch. ACM Trans. Algor. 4, 3. Google ScholarDigital Library
- Achlioptas, D., Clauset, A., Kempe, D., and Moore, C. 2009. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. J. ACM 56, 4. Google ScholarDigital Library
- Agarwal, R., Godfrey, P. B., and Har-Peled, S. 2011. Approximate distance queries and compact routing in sparse graphs. In Proceedings of the 30th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).Google Scholar
- Aiello, W., Chung, F. R. K., and Lu, L. L. 2000. A random graph model for massive graphs. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC). 171--180. Google ScholarDigital Library
- Barabási, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 5439, 509--512.Google Scholar
- Bourgain, J. 1985. On Lipschitz embedding of finite metric spaces in Hilbert space. Isr. J. Math. 52, 1-2, 46--52.Google ScholarCross Ref
- Brady, A. and Cowen, L. 2006. Compact routing on power law graphs with additive stretch. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). 119--128.Google Scholar
- CAIDA Cooperative Association for Internet Data Analysis. 2003. CAIDA's router-level topology measurements. http://www.caida.org/tools/measurement/skitter/router_topology/, file: itdk0304_rlinks_undirected.gz.Google Scholar
- Chan, T. M. 2007. More algorithms for all-pairs shortest paths in weighted graphs. In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC). 590--598. Google ScholarDigital Library
- Cheng, J. and Yu, J. X. 2009. On-line exact shortest distance query processing. In Proceedings of the 12th International Conference on Extending Database Technology (EDBT). 481--492. Google ScholarDigital Library
- Chung, F. R. K. and Lu, L. L. 2002. The average distances in random graphs with given expected degrees. Internet Math. 1, 91--114.Google ScholarCross Ref
- Chung, F. R. K. and Lu, L. L. 2006. Complex Graphs and Networks. American Mathematical Society. Google ScholarDigital Library
- Clauset, A., Shalizi, C. R., and Newman, M. E. J. 2009. Power-law distributions in empirical data. SIAM Rev. 51, 4, 661--703. Google ScholarDigital Library
- Cohen, E., Halperin, E., Kaplan, H., and Zwick, U. 2003. Reachability and distance queries via 2--hop labels. SIAM J. Comput. 32, 5, 1338--1355. Google ScholarDigital Library
- Cowen, L. 2001. Compact routing with minimum stretch. J. Algor. 38, 1, 170--183. Google ScholarDigital Library
- Cvetkovski, A. and Crovella, M. 2009. Hyperbolic embedding and routing for dynamic graphs. In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM). 1647--1655.Google Scholar
- Dijkstra, E. W. 1959. A note on two problems in connection with graphs. Numer. Math. 1, 269--271.Google ScholarDigital Library
- Das Sarma, A., Gollapudi, S., Najork, M., and Panigrahy, R. 2010. A sketch-based distance oracle for web-scale graphs. In Proceedings of the 3rd International Conference on Web Search and Web Data Mining (WSDM). 401--410. Google ScholarDigital Library
- Dinitz, M. 2007. Compact routing with slack. In Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC). 81--88. Google ScholarDigital Library
- Enachescu, M., Wang, M., and Goel, A. 2008. Reducing maximum stretch in compact routing. In Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM). 336--340.Google Scholar
- Erdős, P. and Rényi, A. 1960. On the evolution of random graphs. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 5, 17--61.Google Scholar
- Faloutsos, M., Faloutsos, P., and Faloutsos, C. 1999. On power-law relationships of the Internet topology. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM). 251--262. Google ScholarDigital Library
- Ferrante, A., Pandurangan, G., and Park, K. 2008. On the hardness of optimization in power-law graphs. Theoret. Comput. Sci. 393, 1-3, 220--230. Google ScholarDigital Library
- Fraigniaud, P. and Gavoille, C. 2001. Routing in trees. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP). 757--772. Google ScholarDigital Library
- Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a sparse table with O(1) worst case access time. J. ACM 31, 3, 538--544. Google ScholarDigital Library
- Gavoille, C. and Hanusse, N. 1999. Compact routing tables for graphs of bounded genus. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP). 351--360. Google ScholarDigital Library
- Gavoille, C. and Perennes, S. 1996. Memory requirements for routing in distributed networks (extended abstract). In Proceedings of the 15th Symposium on Principles of Distributed Computing (PODC). 125--133. Google ScholarDigital Library
- Gavoille, C. and Sommer, C. 2011. Sparse spanners vs. compact routing. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 225--234. Google ScholarDigital Library
- Goldberg, A. V., and Harrelson, C. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 156--165. Google ScholarDigital Library
- Goldman, R., Shivakumar, N., Venkatasubramanian, S., and Garcia-Molina, H. 1998. Proximity search in databases. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB). 26--37. Google ScholarDigital Library
- Konjevod, G., Richa, A. W., and Xia, D. 2006. Optimal-stretch name-independent compact routing in doubling metrics. In Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC). 198--207. Google ScholarDigital Library
- Konjevod, G., Richa, A. W., Xia, D., and Yu, H. 2007. Compact routing with slack in low doubling dimension. In Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC). 71--80. Google ScholarDigital Library
- Korman, A. 2008. Improved compact routing schemes for dynamic trees. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC). 185--194. Google ScholarDigital Library
- Krioukov, D. V., Fall, K. R., and Yang, X. 2004. Compact routing on internet-like graphs. In Proceedings of the 23rd IEEE International Conference on Computer Communications (INFOCOM).Google Scholar
- Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., and Upfal, E. 2000. Random graph models for the web graph. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS). 57--65. Google ScholarDigital Library
- Li, L., Alderson, D., Doyle, J. C., and Willinger, W. 2005. Towards a theory of scale-free graphs: Definition, properties, and implications. Internet Math. 2, 4, 431--523.Google ScholarCross Ref
- Lu, H.-I. 2002a. Improved compact routing tables for planar networks via orderly spanning trees. In Proceedings of the 8th International Computing and Combinatorics Conference. 57--66. Google ScholarDigital Library
- Lu, L. L. 2002b. Probabilistic methods in massive graphs and internet computing. Ph.D. dissertation. University of California San Diego. Google ScholarDigital Library
- McDiarmid, C. 1998. Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms and Combinatorics Series, vol. 16. Springer, 1--46.Google Scholar
- Medina, A., Lakhina, A., Matta, I., and Byers, J. W. 2001. Brite: An approach to universal topology generation. In Proceedings of the 9th International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems. 346. Google ScholarDigital Library
- Mitzenmacher, M. 2003. A brief history of generative models for power law and lognormal distributions. Internet Math. 1, 2.Google Scholar
- Newman, M. E. J. 2005. Power laws, Pareto distributions and Zipf's law. Contemp. Phys. 46, 323--351.Google ScholarCross Ref
- Newman, M. E. J., Strogatz, S. H., and Watts, D. J. 2001. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 2, 026118.Google ScholarCross Ref
- Norros, I. and Reittu, H. 2006. On a conditionally Poissonian graph process. Adv. Appl. Prob. 38, 1, 59--75.Google ScholarCross Ref
- Papadopoulos, F., Krioukov, D. V., Boguñá, M., and Vahdat, A. 2010. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM). 2973--2981. Google ScholarDigital Library
- Patrascu, M. and Roditty, L. 2010. Distance oracles beyond the Thorup-Zwick bound. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS). 815--823. Google ScholarDigital Library
- Peleg, D. and Upfal, E. 1989. A trade-off between space and efficiency for routing tables. ACM 36, 3, 510--530. Google ScholarDigital Library
- Potamias, M., Bonchi, F., Castillo, C., and Gionis, A. 2009. Fast shortest path distance estimation in large networks. In Proceedings of the 18th ACM Conference on Information and Knowledge Management (CIKM). 867--876. Google ScholarDigital Library
- Roughan, M., Willinger, W., Maennel, O., Perouli, D., and Bush, R. 2011. 10 lessons from 10 years of measuring and modeling the internet's autonomous systems. IEEE J. Select. Areas Comm. 29, 9, 1810--1821.Google ScholarCross Ref
- Sen, S. 2009. Approximating shortest paths in graphs. In Proceedings of the 3rd International Workshop on Algorithms and Computation (WALCOM). 32--43. Google ScholarDigital Library
- Sommer, C. 2010. Approximate shortest path and distance queries in networks. Ph.D. dissertation. The University of Tokyo.Google Scholar
- Sommer, C., Verbin, E., and Yu, W. 2009. Distance oracles for sparse graphs. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS). 703--712. Google ScholarDigital Library
- Thorup, M. and Zwick, U. 2001. Compact routing schemes. In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA). 1--10. Google ScholarDigital Library
- Thorup, M. and Zwick, U. 2005. Approximate distance oracles. J. ACM 52, 1, 1--24. Google ScholarDigital Library
- Waxman, B. M. 1988. Routing of multipoint connections. IEEE J. Select. Areas Comm. 6, 9, 1617--1622. Google ScholarDigital Library
- Xiao, Y., Wu, W., Pei, J., Wang, W., and He, Z. 2009. Efficiently indexing shortest paths by exploiting symmetry in graphs. In Proceedings of the 12th International Conference on Extending Database Technology (EDBT). 493--504. Google ScholarDigital Library
Index Terms
- A compact routing scheme and approximate distance oracle for power-law graphs
Recommendations
Compact routing schemes
SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architecturesWe describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very small. The headers attached to the routed messages, ...
Compact routing in power-law graphs
DISC'09: Proceedings of the 23rd international conference on Distributed computingWe adapt the compact routing scheme by Thorup and Zwick to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello, Chung, and Lu. ...
Improved Compact Routing Scheme for Chordal Graphs
DISC '02: Proceedings of the 16th International Conference on Distributed ComputingThis paper concerns routing with succinct tables in chordal graphs. We show how to construct in polynomial time, for every n -node chordal graph, a routing scheme using routing tables and addresses of O (log 3 n / log log n ) bits per node, and O (...
Comments