EULER Newsletter No.4 (pdf )
This issue presents the studies on the curvature characteristic of the Internet graph and discusses the possible implications on the routing system design. In particular, it presents the new open researches of finding construction rules of hyperbolic spaces that best reproduce the hidden properties of observable topologies so as to allow for greedy routing using the standard metric for hyperbolic space.
References
[1] Shavitt, Y. and Tankel, T. (2004) On the curvature of the Internet and its usage for overlay construction and distance estimation. In INFOCOM 2004. 23rd IEEE International Conference on Computer Communications. march, 4 vol. (xxxv+2866). ((URL)) (BibTeX)
[2] Papadimitriou, C. H. and Ratajczak, D. (2005) On a conjecture related to geometric routing. Theor. Comput. Sci., 344:3-14. ((URL)) (BibTeX)
[3,4] Kleinberg, R. (2007) Geographic Routing Using Hyperbolic Space. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. may, pages 1902 -1909. ((URL)) (BibTeX)
[5] de Montgolfier, F., Soto, M. and Viennot, L. (2011) Treewidth and Hyperbolicity of the Internet. In Network Computing and Applications (NCA), 2011 10th IEEE International Symposium on. aug., pages 25 -32. ((URL)) (BibTeX)
[6] Ramasubramanian, V., Malkhi, D., Kuhn, F., Balakrishnan, M., Gupta, A. and Akella, A. (2009) On the treeness of internet latency and bandwidth. In Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems. New York, NY, USA. ACM, pages 61-72. ((URL)) (BibTeX)
[7] Gromov, M. (1987) Hyperbolic groups. In Essays in Group Theory. New York. (Gersten, S. M., Eds.) Math. Sciences Research Institute (MSRI). Springer, pages 75-263. (BibTeX)
[8] Gavoille, C. and Ly, O. (2005) Distance Labeling in Hyperbolic Graphs. In 16th International Symposium Algorithms and Computation (ISAAC), pages 1071-1079. . Springer Berlin / Heidelberg. ((URL)) (BibTeX)
[9] Chepoi, V., Dragan, F., Estellon, B., Habib, M. and Vaxès, Y. (2008) Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs. In Proceedings of the twenty-fourth annual symposium on Computational geometry. New York, NY, USA. ACM, pages 59-68. ((URL)) (BibTeX)
[10] Chepoi, V., Dragan, F., Estellon, B., Habib, M., Vaxès, Y. and Xiang, Y. (2012) Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs. Algorithmica, 62:713-732. ((URL)) (BibTeX)
[11] The Cooperative Association for Internet Data Analysis (CAIDA), Archipelago (Ark). Available at http://www.caida.org/projects/ark/. (BibTeX)
[12] Serrano, M. A., Krioukov, D. and Bogu\~n\'a, M. (2008) Self-Similarity of Complex Networks and Hidden Metric Spaces. Phys. Rev. Lett., 100:078701. ((URL)) (BibTeX)
[13] Boguna, M., Papadopoulos, F. and Krioukov, D. (2010) Sustaining the Internet with Hyperbolic Mapping. Nature Communications. ((URL)) (BibTeX)