Polling Strategies for Efficient Remapping of Internet Routing Events

• Elverton Fazzion Universidade Federal de Minas Gerais / Universidade Federal de São João del-Rei
• Dorgival Guedes Universidade Federal de Minas Gerais
• Wagner Meira Jr. Universidade Federal de Minas Gerais
• Ítalo Cunha Universidade Federal de Minas Gerais

DOI: https://doi.org/10.5753/sbrc.2019.7378

Abstract

Path changes caused by events such as traffic engineering, changing traffic exchange partnerships, or link failures impact multiple paths on the Internet. Topological monitoring platforms perform periodic measurements using traceroute for a large number of destinations. This approach, however, is inadequate to precisely identify the extent of the impact of routing events. For example, a link failure can be restored before all routes are measured. In this paper we present measurement strategies that minimize the cost of probing to identify paths impacted by a routing event. Our results show that it is possible to identify the set of paths impacted by an event efficiently. Our results further indicate that when integrated into a state-of-the-art pathway tracking system, our strategies more than double the number of changes detected.

Keywords: Monitoring, Routing Protocols, Traffic Engineering

References

Almeida, R., Fonseca, O., Fazzion, E., Guedes, D., Meira, W., and Cunha, Í. (2017). A Characterization of Load Balancing on the IPv6 Internet. In Proc. PAM.

Augustin, B., Friedman, T., and Teixeira, R. (2011). Measuring Multipath Routing in the Internet. IEEE/ACM Trans. Netw., 19(3):830–840.

Claffy, K., Hyun, Y., Keys, K., Fomenkov, M., and Krioukov, D. (2009). Internet Mapping: from Art to Science. In Proc. IEEE CATCH.

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

Cunha, I., Teixeira, R., and Diot, C. (2011). Measuring and Characterizing End-to-End Route Dynamics in the Presence of Load Balancing. In Proc. PAM.

Cunha, I., Teixeira, R., Veitch, D., and Diot, C. (2014). DTRACK: A System to Predict and Track Internet Path Changes. IEEE/ACM Trans. Netw., 22(4):1025–1038.

Fazzion, E., Cunha, I., Guedes, D., Meira, Jr., W., Teixeira, R., Veitch, D., and Diot, C. (2016). Efficient remapping of internet routing events. In SIGCOMM (SRC).

Giotsas, V., Dhamdhere, A., and kc claffy (2016). Periscope: Unifying Looking Glass Querying. In Proc. of PAM.

Giotsas, V., Smaragdakis, G., Huffaker, B., Luckie, M., and claffy, k. (2015). Mapping Peering Interconnections to a Facility. In Proc. ACM CoNEXT.

Goodin, D. (2018). Google goes down after major bgp mishap routes traffic through china. Ars Technica.

Katz-Bassett, E., Scott, C., Choffnes, D. R., Cunha, I., Valancius, V., Feamster, N.,
Madhyastha, H. V., Anderson, T., and Krishnamurthy, A. (2012). LIFEGUARD: Practical Repair of Persistent Route Failures. In Proc. ACM SIGCOMM.

Kompella, R., Yates, J., Greenberg, A., and Snoeren, A. (2007). Detection and Localization of Network Blackholes. In Proc. IEEE INFOCOM.

Levchenko, K., Dhamdhere, A., Huffaker, B., claffy, k., Allman, M., and Paxson, V. (2017). PacketLab: A Universal Measurement Endpoint Interface. In Proc. IMC.

Luckie, M. (2010). Scamper: A scalable and extensible packet prober for active measurement of the internet. In Proc. IMC.

Marder, A., Luckie, M., Dhamdhere, A., Huffaker, B., claffy, k., and Smith, J. M. (2018). Pushing the Boundaries with bdrmapIT: Mapping Router Ownership at Internet Scale. In Proc. IMC.

Ravaioli, R., Urvoy-Keller, G., and Barakat, C. (2015). Characterizing icmp rate limitation on routers. In Proc. IEEE Conference on Communications.

Shavitt, Y. and Weinsberg, U. (2009). Quantifying the Importance of Vantage Points Distribution in Internet Topology Measurements. In Proc. IEEE INFOCOM.

Vermeulen, K., Strowes, S. D., Fourmaux, O., and Friedman, T. (2018). Multilevel mdalite paris traceroute. CoRR.