More Web Proxy on the site http://driver.im/

research-article

PredictRoute: A Network Path Prediction Toolkit

Authors:

Andrew McGregorAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 5, Issue 2

Article No.: 23, Pages 1 - 24

https://doi.org/10.1145/3460090

Published: 04 June 2021 Publication History

Abstract

Accurate prediction of network paths between arbitrary hosts on the Internet is of vital importance for network operators, cloud providers, and academic researchers. We present PredictRoute, a system that predicts network paths between hosts on the Internet using historical knowledge of the data and control plane. In addition to feeding on freely available traceroutes and BGP routing tables, PredictRoute optimally explores network paths towards chosen BGP prefixes. PredictRoute's strategy for exploring network paths discovers 4X more autonomous system (AS) hops than other well-known strategies used in practice today. Using a corpus of traceroutes, PredictRoute trains probabilistic models of routing towards prefixes on the Internet to predict network paths and their likelihood. PredictRoute's AS-path predictions differ from the measured path by at most 1 hop, 75% of the time. We expose PredictRoute's path prediction capability via a REST API to facilitate its inclusion in other applications and studies. We additionally demonstrate the utility of PredictRoute in improving real-world applications for circumventing Internet censorship and preserving anonymity online.

Supplementary Material

MP4 File (predictroute-network-path-prediction-toolkit.mp4)

Presentation video

Download
12.24 MB

References

[1]

CAIDA's Prefix to ASN dataset. https://www.caida.org/data/routing/routeviews-prefix2as.xml.

[2]

Peeringdb. https://www.peeringdb.com/.

[3]

Y. Afek, O. Ben-Shalom, and A. Bremler-Barr. On the structure and application of bgp policy atoms. In Proceedings of the 2Nd ACM SIGCOMM Workshop on Internet Measurment, IMW '02, pages 209--214, New York, NY, USA, 2002. ACM.

Digital Library

[4]

R. Anwar, H. Niaz, D. Choffnes, I. Cunha, P. Gill, and E. Katz-Bassett. Investigating interdomain routing policies in the wild. In ACM IMC, 2015.

Digital Library

[5]

A. Asadpour and H. Nazerzadeh. Maximizing stochastic monotone submodular functions. Management Science, 62(8):2374--2391, 2016.

[6]

A. Barton and M. Wright. Denasa: Destination-naive as-awareness in anonymous communications. Proceedings on Privacy Enhancing Technologies, 2016(4):356--372, 2016.

[7]

CAIDA Ark. http://www.caida.org/projects/ark/.

[8]

CAIDA AS Relationship dataset. http://data.caida.org/datasets/as-relationships/.

[9]

K. Chen, D. R. Choffnes, R. Potharaju, Y. Chen, F. E. Bustamante, D. Pei, and Y. Zhao. Where the sidewalk ends: Extending the internet as graph using traceroutes from p2p users. In Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies, CoNEXT '09, pages 217--228, New York, NY, USA, 2009. ACM.

Digital Library

[10]

Y. Chiu, B. Schlinker, A. Radhakrishnan, and E. Katz-Bassett. Are we one hop away from a better Internet? In Proceedings of the 2015 ACM Conference on Internet Measurement Conference, pages 71--77. ACM, 2015.

Digital Library

[11]

R. Dingledine, N. Mathewson, and P. Syverson. Tor: The second-generation onion router. Technical report, Naval Research Lab Washington DC, 2004.

[12]

U. Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634--652, July 1998.

Digital Library

[13]

T. Flach, E. Katz-Bassett, and R. Govindan. Quantifying violations of destination-based forwarding on the internet. In IMC '12, 2012.

Digital Library

[14]

S. Frolov, F. Douglas, W. Scott, A. McDonald, B. VanderSloot, R. Hynes, A. Kruger, M. Kallitsis, D. G. Robinson, S. Schultze, et al. An isp-scale deployment of tapdance. In 7th $$USENIX$$ Workshop on Free and Open Communications on the Internet (FOCI 17), 2017.

[15]

L. Gao and J. Rexford. Stable Internet routing without global coordination. 2001.

[16]

P. Gill, M. Arlitt, Z. Li, and A. Mahanti. The flattening internet topology: Natural evolution, unsightly barnacles or contrived collapse? In International Conference on Passive and Active Network Measurement, pages 1--10. Springer, 2008.

Digital Library

[17]

P. Gill, M. Schapira, and S. Goldberg. Let the market drive deployment: A strategy for transitioning to bgp security. SIGCOMM Comput. Commun. Rev., 41(4):14--25, Aug. 2011.

Digital Library

[18]

P. Gill, M. Schapira, and S. Goldberg. Modeling on quicksand: Dealing with the scarcity of ground truth in interdomain routing data. ACM SIGCOMM Computer Communication Review, 42(1):40--46, 2012.

Digital Library

[19]

P. Gill, M. Schapira, and S. Goldberg. A survey of interdomain routing policies. In ACM Computer Communications Review (CCR)., Jan 2014.

[20]

V. Giotsas, M. Luckie, B. Huffaker, and kc claffy. Inferring complex AS relationships. In ACM IMC, 2014.

[21]

T. Holterbach, C. Pelsser, R. Bush, and L. Vanbever. Quantifying interference between measurements on the RIPE Atlas platform. In ACM IMC, 2015.

Digital Library

[22]

J. Karlin, S. Forrest, and J. Rexford. Autonomous security for autonomous systems. Computer Networks, oct 2008.

[23]

E. Katz-Bassett, H. Madhyastha, V. Adhikari, C. Scott, J. Sherry, P. van Wesep, A. Krishnamurthy, and T. Anderson. Reverse traceroute. In USENIX Symposium on Networked Systems Design & Implementation (NSDI), 2010.

Digital Library

[24]

E. Katz-Bassett, P. Marchetta, M. Calder, Y.-C. Chiu, I. Cunha, H. Madhyastha, and V. Giotsas. Sibyl: A practical internet route oracle. In USENIX NSDI, 2016.

[25]

V. Krishnamurthy, M. Faloutsos, M. Chrobak, L. Lao, J.-H. Cui, and A. G. Percus. Sampling large Internet topologies for simulation purposes. 2007.

Digital Library

[26]

H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani. iPlane: An Information Plane for Distributed Services. In Proc. of Operatings System Design and Implementation, 2006.

Digital Library

[27]

H. V. Madhyastha, E. Katz-Bassett, T. E. Anderson, A. Krishnamurthy, and A. Venkataramani. iplane nano: Path prediction for peer-to-peer applications. In NSDI, volume 9, pages 137--152, 2009.

[28]

R. Nithyanand, R. Singh, S. Cho, and P. Gill. Holding all the ases: Identifying and circumventing the pitfalls of as-aware tor client design. CoRR, abs/1605.03596, 2016.

[29]

Raspberry Pi. https://www.raspberrypi.org/.

[30]

RIPE Atlas. https://atlas.ripe.net/.

[31]

Rule Based Learning Ensembles. https://statweb.stanford.edu/ jhf/R_RuleFit.html.

[32]

R. Singh and P. Gill. Pathcache: A path prediction toolkit. In Proceedings of the 2016 ACM SIGCOMM Conference, SIGCOMM '16, page 569--570, New York, NY, USA, 2016. Association for Computing Machinery.

Digital Library

[33]

O. Starov, R. Nithyanand, A. Zair, P. Gill, and M. Schapira. Measuring and mitigating as-level adversaries against tor. In NDSS, 2016.

[34]

Y. Sun, A. Edmundson, L. Vanbever, O. Li, J. Rexford, M. Chiang, and P. Mittal. Raptor: Routing attacks on privacy in tor. In 24th USENIX Security Symposium (USENIX Security 15), pages 271--286, Washington, D.C., Aug. 2015. USENIX Association.

Digital Library

[35]

M. Wojciechowski. Border gateway protocol modeling and simulation. master's thesis. 2008.

[36]

E. Wustrow, S. Wolchok, I. Goldberg, and J. A. Halderman. Telex: Anticensorship in the network infrastructure. In Proceedings of the 20th USENIX Conference on Security, SEC'11, pages 30--30, Berkeley, CA, USA, 2011. USENIX Association.

[37]

E. Wustrow, S. Wolchok, I. Goldberg, and J. A. Halderman. Telex: Anticensorship in the network infrastructure. In Proceedings of the 20th USENIX Conference on Security, SEC'11, pages 30--30, Berkeley, CA, USA, 2011. USENIX Association.

[38]

J. Y. Yen. Finding the k shortest loopless paths in a network. Management Science, 17(11):712--716, 1971.

Digital Library

Cited By

Kirci ETorsiello VVanbever L(2024)What is the next hop to more granular routing models?Proceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696859(343-351)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1145/3696348.3696859
Salamatian LVermeulen KCunha IGiotsas VKatz-Bassett EVallina-Rodríguez NSuarez-Tángil GLevin DPelsser C(2024)metAScritic: Reframing AS-Level Topology Discovery as a Recommendation SystemProceedings of the 2024 ACM on Internet Measurement Conference10.1145/3646547.3688429(337-364)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3646547.3688429
Raghunath ANdubuisi-Obi IMpogole HAnderson R(2024)Beyond Digital Financial Services: Exploring Mobile Money Agents in Tanzania as General ICT IntermediariesACM Journal on Computing and Sustainable Societies10.1145/36163862:1(1-26)Online publication date: 13-Jan-2024
https://dl.acm.org/doi/10.1145/3616386
Show More Cited By

Index Terms

PredictRoute: A Network Path Prediction Toolkit
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems
  2. Probability and statistics
    1. Probabilistic representations
      1. Markov networks
2. Networks
  1. Network properties
    1. Network range
      1. Wide area networks
  2. Network protocols
    1. Network layer protocols
      1. Routing protocols

Recommendations

PredictRoute: A Network Path Prediction Toolkit
SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

Accurate prediction of network paths between arbitrary hosts on the Internet is of vital importance for network operators, cloud providers, and academic researchers. We present PredictRoute, a system that predicts network paths between hosts on the ...
PredictRoute: A Network Path Prediction Toolkit
SIGMETRICS '21

Accurate prediction of network paths between arbitrary hosts on the Internet is of vital importance for network operators, cloud providers, and academic researchers. We present PredictRoute, a system that predicts network paths between hosts on the ...
An active approach to measuring routing dynamics induced by autonomous systems
ExpCS '07: Proceedings of the 2007 workshop on Experimental computer science

We present an active measurement study of the routing dynamics induced by AS-path prepending, a common method for controlling the inbound traffic of a multi-homed ISP. Unlike other inter-domain inbound traffic engineering methods, AS-path prepending not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 5, Issue 2

POMACS

June 2021

424 pages

EISSN:2476-1249

DOI:10.1145/3469656

Editors:
Augustin Chaintreau
Columbia University
,
Leana Golubchik
University of Southern California
,
Zhi-Li Zhang
University of Minnesota

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2021

Published in POMACS Volume 5, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
499
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kirci ETorsiello VVanbever L(2024)What is the next hop to more granular routing models?Proceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696859(343-351)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1145/3696348.3696859
Salamatian LVermeulen KCunha IGiotsas VKatz-Bassett EVallina-Rodríguez NSuarez-Tángil GLevin DPelsser C(2024)metAScritic: Reframing AS-Level Topology Discovery as a Recommendation SystemProceedings of the 2024 ACM on Internet Measurement Conference10.1145/3646547.3688429(337-364)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3646547.3688429
Raghunath ANdubuisi-Obi IMpogole HAnderson R(2024)Beyond Digital Financial Services: Exploring Mobile Money Agents in Tanzania as General ICT IntermediariesACM Journal on Computing and Sustainable Societies10.1145/36163862:1(1-26)Online publication date: 13-Jan-2024
https://dl.acm.org/doi/10.1145/3616386
Kastanakis SGiotsas VLivadariu ISuri NMontpetit MLeivadeas AUhlig SJaved M(2023)Replication: 20 Years of Inferring Interdomain Routing PoliciesProceedings of the 2023 ACM on Internet Measurement Conference10.1145/3618257.3624799(16-29)Online publication date: 24-Oct-2023
https://dl.acm.org/doi/10.1145/3618257.3624799
Milolidakis ABühler TWang KChiesa MVanbever LVissicchio S(2023)On the Effectiveness of BGP Hijackers That Evade Public Route CollectorsIEEE Access10.1109/ACCESS.2023.326112811(31092-31124)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3261128
Wu TWang JWang JZhuang S(2022)RouteInfer: Inferring Interdomain Paths by Capturing ISP Routing Behavior Diversity and GeneralityPassive and Active Measurement10.1007/978-3-030-98785-5_10(216-244)Online publication date: 28-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-030-98785-5_10

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents