Document Open Access Logo

Mapping Networks via Parallel kth-Hop Traceroute Queries

Authors Ramtin Afshar , Michael T. Goodrich , Pedro Matias , Martha C. Osegueda

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.4.pdf
  • Filesize: 2.23 MB
  • 21 pages

Document Identifiers

Author Details

Ramtin Afshar
  • University of California-Irvine, CA, USA
Michael T. Goodrich
  • University of California-Irvine, CA, USA
Pedro Matias
  • University of California-Irvine, CA, USA
Martha C. Osegueda
  • University of California-Irvine, CA, USA

Cite AsGet BibTex

Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Mapping Networks via Parallel kth-Hop Traceroute Queries. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.4

Abstract

For a source node, v, and target node, w, the traceroute command iteratively issues "kth-hop" queries, for k = 1, 2, … , δ(v,w), which return the name of the kth vertex on a shortest path from v to w, where δ(v,w) is the distance between v and w, that is, the number of edges in a shortest-path from v to w. The traceroute command is often used for network mapping applications, the study of the connectivity of networks, and it has been studied theoretically with respect to biases it introduces for network mapping when only a subset of nodes in the network can be the source of traceroute queries. In this paper, we provide efficient network mapping algorithms, that are based on kth-hop traceroute queries. Our results include an algorithm that runs in a constant number of parallel rounds with a subquadratic number of queries under reasonable assumptions about the sampling coverage of the nodes that may issue kth-hop traceroute queries. In addition, we introduce a number of new algorithmic techniques, including a high-probability parametric parallelization of a graph clustering technique of Thorup and Zwick, which may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel algorithms
  • Networks → Network algorithms
  • Mathematics of computing → Graph theory
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Network mapping
  • graph algorithms
  • parallel algorithms
  • distributed computing
  • query complexity
  • kth-hop queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. TRACEROUTE for Linux. http://traceroute.sourceforge.net/. Accessed: April 6, 2020.
  2. TRACEROUTE(8) Traceroute For Linux, October 2006. Accessed: April 6, 2020. URL: http://man7.org/linux/man-pages/man8/traceroute.8.html.
  3. Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel. Graph reconstruction with a betweenness oracle. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 5:1-5:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.5.
  4. Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore. On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 694-703, 2005. URL: https://doi.org/10.1145/1060590.1060693.
  5. Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, and Kurt Mehlhorn. The query complexity of finding a hidden permutation. In Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pages 1-11, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-40273-9_1.
  6. Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Reconstructing binary trees in parallel. In Christian Scheideler and Michael Spear, editors, SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 491-492. ACM, 2020. URL: https://doi.org/10.1145/3350755.3400229.
  7. Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Reconstructing biological and digital phylogenetic trees in parallel. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 3:1-3:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.3.
  8. Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Parallel network mapping algorithms. In Kunal Agrawal and Yossi Azar, editors, SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 410-413. ACM, 2021. URL: https://doi.org/10.1145/3409964.3461822.
  9. Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM J. Discrete Math., 18(4):697-712, 2005. URL: https://doi.org/10.1137/S0895480103431071.
  10. Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM J. Comput., 33(2):487-501, 2004. URL: https://doi.org/10.1137/S0097539702420139.
  11. Dana Angluin and Jiang Chen. Learning a hidden hypergraph. J. Mach. Learn. Res., 7:2215-2236, 2006. URL: http://jmlr.org/papers/v7/angluin06a.html.
  12. Dana Angluin and Jiang Chen. Learning a hidden graph using O(log n) queries per edge. J. Comput. Syst. Sci., 74(4):546-556, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.006.
  13. Alain Barrat, Ignacio Alvarez-Hamelin, Luca Dall’Asta, Alexei Vázquez, and Alessandro Vespignani. Sampling of networks with traceroute-like probes. Complexus, 3(1-3):83-96, 2006. Google Scholar
  14. Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák, and L. Shankar Ram. Network discovery and verification. IEEE Journal on Selected Areas in Communications, 24(12):2168-2181, 2006. URL: https://doi.org/10.1109/JSAC.2006.884015.
  15. Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, and Lance Fortnow. An optimal procedure for gap closing in whole genome shotgun sequencing. In Thomas Lengauer, editor, Proceedings of the Fifth Annual International Conference on Computational Biology, RECOMB 2001, Montréal, Québec, Canada, April 22-25, 2001, pages 22-30. ACM, 2001. URL: https://doi.org/10.1145/369133.369152.
  16. Anna Bernasconi, Carsten Damm, and Igor Shparlinski. Circuit and decision tree complexity of some number theoretic problems. Information and Computation, 168(2):113-124, 2001. URL: https://doi.org/10.1006/inco.2000.3017.
  17. Mathilde Bouvel, Vladimir Grebinski, and Gregory Kucherov. Combinatorial search on graphs motivated by bioinformatics applications: A brief survey. In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers, volume 3787 of Lecture Notes in Computer Science, pages 16-27. Springer, 2005. URL: https://doi.org/10.1007/11604686_2.
  18. Sung-Soon Choi and Jeong Han Kim. Optimal query complexity bounds for finding graphs. Artificial Intelligence, 174(9):551-569, 2010. URL: https://doi.org/10.1016/j.artint.2010.02.003.
  19. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  20. Luca Dall'Asta, J. Ignacio Alvarez-Hamelin, Alain Barrat, Alexei Vázquez, and Alessandro Vespignani. Exploring networks with traceroute-like probes: Theory and simulations. Theor. Comput. Sci., 355(1):6-24, 2006. URL: https://doi.org/10.1016/j.tcs.2005.12.009.
  21. Luca Dall’Asta, Ignacio Alvarez-Hamelin, Alain Barrat, Alexei Vázquez, and Alessandro Vespignani. Exploring networks with traceroute-like probes: Theory and simulations. Theoretical Computer Science, 355(1):6-24, 2006. URL: http://www.sciencedirect.com/science/article/pii/S0304397505009126.
  22. Shahar Dobzinski and Jan Vondrak. From query complexity to computational complexity. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 1107-1116, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2213977.2214076.
  23. Benoit Donnet. Internet topology discovery. In Ernst Biersack, Christian Callegari, and Maja Matijasevic, editors, Data Traffic Monitoring and Analysis - From Measurement, Classification, and Anomaly Detection to Quality of Experience, volume 7754 of LNCS, pages 44-81. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36784-7_3.
  24. Benoit Donnet and Timur Friedman. Internet topology discovery: A survey. IEEE Communications Surveys and Tutorials, 9(1-4):56-69, 2007. URL: https://doi.org/10.1109/COMST.2007.4444750.
  25. Martin Erwig. The graph Voronoi diagram with applications. Networks, 36(3):156-163, 2000. URL: https://doi.org/10.1002/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L.
  26. Abraham D. Flaxman and Juan Vera. Bias reduction in traceroute sampling - towards a more accurate map of the internet. In Anthony Bonato and Fan R. K. Chung, editors, Algorithms and Models for the Web-Graph, 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007, Proceedings, volume 4863 of Lecture Notes in Computer Science, pages 1-15. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-77004-6_1.
  27. Vladimir Grebinski. On the power of additive combinatorial search model. In Wen-Lian Hsu and Ming-Yang Kao, editors, Computing and Combinatorics, 4th Annual International Conference, COCOON '98, Taipei, Taiwan, R.o.C., August 12-14, 1998, Proceedings, volume 1449 of Lecture Notes in Computer Science, pages 194-203. Springer, 1998. URL: https://doi.org/10.1007/3-540-68535-9_23.
  28. Vladimir Grebinski and Gregory Kucherov. Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discret. Appl. Math., 88(1-3):147-165, 1998. URL: https://doi.org/10.1016/S0166-218X(98)00070-5.
  29. Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica, 28(1):104-124, 2000. URL: https://doi.org/10.1007/s004530010033.
  30. Jotun J Hein. An optimal algorithm to reconstruct trees from additive distance data. Bulletin of mathematical biology, 51(5):597-603, 1989. Google Scholar
  31. S. Honiden, M. E. Houle, and C. Sommer. Balancing graph Voronoi diagrams. In Sixth International Symposium on Voronoi Diagrams, pages 183-191, 2009. Google Scholar
  32. B. Huffaker, D. Plummer, D. Moore, and K. Claffy. Topology discovery by active probing. In IEEE Symposium on Applications and the Internet (SAINT), pages 90-96, 2002. Google Scholar
  33. Bradley Huffaker, Daniel Plummer, David Moore, and KC Claffy. Topology discovery by active probing. In Proceedings 2002 Symposium on Applications and the Internet (SAINT) Workshops, pages 90-96. IEEE, 2002. Google Scholar
  34. Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Trans. Algorithms, 14(4):40:1-40:30, 2018. URL: https://doi.org/10.1145/3199606.
  35. Valerie King, Li Zhang, and Yunhong Zhou. On the complexity of distance-based evolutionary tree reconstruction. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 444-453, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644179.
  36. Maciej Kurant, Athina Markopoulou, and Patrick Thiran. Towards unbiased BFS sampling. IEEE Journal on Selected Areas in Communications, 29(9):1799-1809, 2011. URL: https://doi.org/10.1109/JSAC.2011.111005.
  37. A. Lakhina, J.W. Byers, M. Crovella, and P. Xie. Sampling biases in IP topology measurements. In IEEE INFOCOM, volume 1, pages 332-341, 2003. URL: https://doi.org/10.1109/INFCOM.2003.1208685.
  38. Claire Mathieu and Hang Zhou. A simple algorithm for graph reconstruction. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 68:1-68:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.68.
  39. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2/e edition, 2017. Google Scholar
  40. Lev Reyzin and Nikhil Srivastava. On the longest path algorithm for reconstructing trees from distance matrices. Inf. Process. Lett., 101(3):98-100, 2007. URL: https://doi.org/10.1016/j.ipl.2006.08.013.
  41. Guozhen Rong, Wenjun Li, Yongjie Yang, and Jianxin Wang. Reconstruction and verification of chordal graphs with a distance oracle. Theoretical Computer Science, 859:48-56, 2021. URL: https://doi.org/10.1016/j.tcs.2021.01.006.
  42. Sandeep Sen and V. N. Muralidhara. The covert set-cover problem with application to network discovery. In Md. Saidur Rahman and Satoshi Fujita, editors, WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010. Proceedings, volume 5942 of Lecture Notes in Computer Science, pages 228-239. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-11440-3_21.
  43. G. Tardos. Query complexity, or why is it difficult to separate NP^A∩ coNP^A from P^A by random oracles A? Combinatorica, 9(4):385-392, December 1989. URL: https://doi.org/10.1007/BF02125350.
  44. Fabien Tarissan, Matthieu Latapy, and Christophe Prieur. Efficient measurement of complex networks using link queries. CoRR, abs/0904.3222, 2009. URL: http://arxiv.org/abs/0904.3222.
  45. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Arnold L. Rosenberg, editor, 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1-10, 2001. URL: https://doi.org/10.1145/378580.378581.
  46. Zhaosen Wang and Jean Honorio. Reconstructing a bounded-degree directed tree using path queries. In 57th IEEE Allerton Conference on Communication, Control, and Computing, 2019. See also URL: https://arxiv.org/abs/1606.05183.
  47. Michael S Waterman, Temple F Smith, Mona Singh, and William A Beyer. Additive evolutionary trees. Journal of theoretical Biology, 64(2):199-213, 1977. Google Scholar
  48. Andrew Chi-Chih Yao. Decision tree complexity and Betti numbers. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC '94, pages 615-624, New York, NY, USA, 1994. ACM. URL: https://doi.org/10.1145/195058.195414.
  49. X. Zhang and C. Phillips. A survey on selective routing topology inference through active probing. IEEE Communications Surveys Tutorials, 14(4):1129-1141, 2012. Google Scholar
  50. Yaonan Zhang, Eric D. Kolaczyk, and Bruce D. Spencer. Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks. The Annals of Applied Statistics, 9(1):166-199, 2015. URL: https://doi.org/10.1214/14-AOAS800.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact