{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T07:08:30Z","timestamp":1760425710212,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T00:00:00Z","timestamp":1560902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["338402"],"award-info":[{"award-number":["338402"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,6,19]]},"abstract":"<jats:p>BGP is the de-facto Internet routing protocol for exchanging prefix reachability information between Autonomous Systems (AS). It is a dynamic, distributed, path-vector protocol that enables rich expressions of network policies (typically treated as secrets). In this regime, where complexity is interwoven with information hiding, answering questions such as \"what is the expected catchment of the anycast sites of a content provider on the AS-level, if new sites are deployed?\", or \"how will load-balancing behave if an ISP changes its routing policy for a prefix?\", is a hard challenge. In this work, we present a formal model and methodology that takes into account policy-based routing and topological properties of the Internet graph, to predict the routing behavior of networks. We design algorithms that provide new capabilities for informative route inference (e.g., isolating the effect of randomness that is present in prior simulation-based approaches). We analyze the properties of these inference algorithms, and evaluate them using publicly available routing datasets and real-world experiments. The proposed framework can be useful in a number of applications: measurements, traffic engineering, network planning, Internet routing models, etc. As a use case, we study the problem of selecting a set of measurement vantage points to maximize route inference. Our methodology is general and can capture standard valley-free routing, as well as more complex topological and routing setups appearing in practice.<\/jats:p>","DOI":"10.1145\/3341617.3326145","type":"journal-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:18:56Z","timestamp":1561033136000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Inferring Catchment in Internet Routing"],"prefix":"10.1145","volume":"3","author":[{"given":"Pavlos","family":"Sermpezis","sequence":"first","affiliation":[{"name":"Institute of Computer Science, FORTH, Heraklion, Greece"}]},{"given":"Vasileios","family":"Kotronis","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, FORTH, Heraklion, Greece"}]}],"member":"320","published-online":{"date-parts":[[2019,6,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815675.2815712"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04918-2_6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305433"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2005.1541715"},{"key":"e_1_2_1_5_1","volume-title":"http:\/\/data.caida.org\/datasets\/as-relationships\/. Dataset collected on 1st","author":"Relationships Dataset CAIDA.","year":"2018","unstructured":"CAIDA. 2018. AS-Relationships Dataset. http:\/\/data.caida.org\/datasets\/as-relationships\/. Dataset collected on 1st July 2018."},{"key":"e_1_2_1_6_1","unstructured":"CAIDA. 2018. Periscope Looking Glass API. http:\/\/www.caida.org\/tools\/utilities\/looking-glass-api\/."},{"key":"e_1_2_1_7_1","unstructured":"CAIDA. 2018. Routeviews Prefix-to-AS mappings (pfx2as) for IPv4 and IPv6. http:\/\/data.caida.org\/datasets\/routing\/routeviews-prefix2as\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2675013"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218670"},{"key":"e_1_2_1_10_1","unstructured":"Cisco. 2019. BGP Best Path Selection Algorithm. https:\/\/www.cisco.com\/c\/en\/us\/support\/docs\/ip\/border-gateway-protocol-bgp\/13753--25.html ."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90060-D"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2930611.2930633"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3131365.3131371"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-39814-3_16"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1012888.1005726"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-76481-8_16"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.974523"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192400"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043164.2018439"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2663716.2663743"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2398776.2398803"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2398776.2398818"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218436"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/861359"},{"key":"e_1_2_1_25_1","volume-title":"Submodular function maximization. Tractability: Practical Approaches to Hard Problems","author":"Krause Andreas","year":"2012","unstructured":"Andreas Krause and Daniel Golovin. 2012. Submodular function maximization. Tractability: Practical Approaches to Hard Problems, Vol. 3, 19 (2012), 8."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"P Lapukhov A Premji and J Mitchell. 2016. Use of BGP for routing in large-scale data centers. RFC 7938.","DOI":"10.17487\/RFC7938"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2010.10.004"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230547"},{"key":"e_1_2_1_29_1","unstructured":"Kurt Lindqvist and Joe Abley. 2006. Operation of Anycast Services. RFC 4786."},{"key":"e_1_2_1_30_1","volume-title":"Proc. IEEE INFOCOM .","author":"Lodhi Aemen","year":"2015","unstructured":"Aemen Lodhi, Nikolaos Laoutaris, Amogh Dhamdhere, and Constantine Dovrolis. 2015. Complexities in Internet peering: Understanding the \"black\" in the \"black art\". In Proc. IEEE INFOCOM ."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2504730.2504735"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071690.1064257"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2987443.2987446"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151659.1159937"},{"key":"e_1_2_1_35_1","unstructured":"NANOG mailing list archives. 2018. How to choose a transit provider? http:\/\/seclists.org\/nanog\/2018\/Dec\/281 ."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3278532.3278556"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2987443.2987482"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Judea Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference 1 ed.). Morgan Kaufmann.","DOI":"10.5555\/52121"},{"key":"e_1_2_1_39_1","unstructured":"PEERING. 2019. The PEERING testbed. https:\/\/peering.usc.edu\/."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2005.1541716"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","unstructured":"Yakov Rekhter Tony Li and Susan Hares. 2006. A Border Gateway Protocol 4 (BGP-4). RFC 4271. 10.17487\/RFC1654","DOI":"10.17487\/RFC1654"},{"key":"e_1_2_1_42_1","unstructured":"RIPE NCC. 2018. RIPE Atlas. https:\/\/atlas.ripe.net\/."},{"key":"e_1_2_1_43_1","unstructured":"RIPE NCC. 2018. Routing Information Service (RIS). https:\/\/www.ripe.net\/analyse\/internet-measurements\/routing-information-service-ris ."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670518.2673887"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.23919\/IFIPNetworking.2017.8264834"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Pavlos Sermpezis and Vasileios Kotronis. 2019. GitHub repository with the Catchment Inference in Internet Routing code and algorithm implementation. https:\/\/github.com\/FORTH-ICS-INSPIRE\/anycast_catchment_prediction .","DOI":"10.1145\/3376930.3376943"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2869798"},{"key":"e_1_2_1_48_1","unstructured":"University of Oregon. 2018. Route Views Project. www.routeviews.org ."},{"key":"e_1_2_1_49_1","unstructured":"Verizon. 2017. Seeing the World with RIPE Atlas. https:\/\/labs.ripe.net\/Members\/verizon_digital\/seeing-the-world-with-ripe-atlas."},{"key":"e_1_2_1_50_1","volume-title":"Does anycast hang up on you? IEEE Transactions on Network and Service Management","author":"Wei Lan","year":"2018","unstructured":"Lan Wei and John Heidemann. 2018. Does anycast hang up on you? IEEE Transactions on Network and Service Management (2018)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2018.2859480"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2877686"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341617.3326145","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341617.3326145","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:29Z","timestamp":1750200089000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341617.3326145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,19]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,19]]}},"alternative-id":["10.1145\/3341617.3326145"],"URL":"https:\/\/doi.org\/10.1145\/3341617.3326145","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2019,6,19]]},"assertion":[{"value":"2019-06-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}