On spectral analysis of the Internet delay space and detecting anomalous routing paths

Latency is one of the most critical performance metrics for a wide range of applications. Therefore, it isimportant to understand the underlying mechanisms that give rise to the observed latency values and diagnose the onesthat are unexpectedly high. In this paper, we study the Internet delay space via robust principal component analysis(RPCA). Using RPCA, we show that the delay space, i.e. the matrix of measured round trip times between end hosts,can be decomposed into two components: the estimated latency between end hosts with respect to the current state ofthe Internet and the inflation on the paths between the end hosts. Using this decomposition, first we study the wellknown low-dimensionality phenomena of the delay space and ask what properties of the end hosts define the dimensions.Second, using the decomposition, we develop a filtering method to detect the paths that experience unexpected latenciesand identify routing anomalies. We show that our filter successfully identifies an anomalous route even when its observedlatency is not obviously high in magnitude.

PDF

___

[1] Krishnan R, Madhyastha HV, Srinivasan S, Jain S, Krishnamurthy A, Anderson T, Gao J. Moving beyond endto-end path information to optimize CDN performance. In: ACM 2009 Internet Measurement Conference; 4–6 November 2009; Chicago, IL, USA. New York, NY, USA: ACM. pp. 190–201.
[2] Pucha H, Zhang Y, Mao ZM, Hu YC. Understanding network delay changes caused by routing events. SIGMETRICS Perform Eval Rev 2007; 35: 73–84.
[3] Zarifis K, Flach T, Nori S, Choffnes D, Govindan R, Katz-Bassett E, Mao ZM, Welsh M. Diagnosing path inflation of mobile client traffic. In: Springer 2014 Passive Active Measurement; 10–11 March 2014; Los Angeles, CA, USA. Berlin, Germany: Springer. pp. 23–33.
[4] Spring N, Mahajan R, Anderson T. The causes of path inflation. In: ACM 2003 SIGCOMM; 25–29 August 2003; Karlsruhe, Germany. New York, NY, USA: ACM. pp. 113–124.
[5] Tangmunarunkit H, Govindan R, Shenker S. Internet path inflation due to policy routing. SPIE 2001; 4526: 188-195.
[6] Abrahao B, Kleinberg R. On the Internet delay space dimensionality. In: ACM 2008 Internet Measurement Conference; 20–22 October 2008; Vouliagmeni, Greece. New York, NY, USA: ACM. pp. 157-168.
[7] Tang L, Crovella M. Virtual landmarks for the Internet. In: ACM 2003 Internet Measurement Conference; 27–29 October 2003. Miami Beach, FL, USA. New York, NY, USA: ACM. pp. 143–152.
[8] Candés EJ, Li X, Ma Y, Wright J. Robust principal component analysis? J ACM 2011; 58: 11-37.
[9] Lakhina A, Crovella M, Diot C. Diagnosing network-wide traffic anomalies. SIGCOMM Comput Commun Rev 2014; 34: 219–230.
[10] Roughan M. Simplifying the synthesis of Internet traffic matrices. SIGCOMM Comput Commun Rev 2005; 35: 93-96.
[11] Zhang Y, Roughan M, Lund C, Donoho DL. Estimating point-to-point and point-to-multipoint traffic matrices: An information-theoretic approach. IEEE ACM T Network 2005; 13: 947–960.
[12] Chang H, Jamin S, Mao ZM, Willinger W. An empirical approach to modeling inter-as traffic matrices. In: ACM 2005 Internet Measurement Conference; 19–21 October 2005; Berkeley, CA, USA. Berkeley, CA, USA: ACM USENIX Association. pp. 12-25.
[13] Chang H, Jamin S, Willinger W. To peer or not to peer: modeling the evolution of the Internet’s as-level topology. In: IEEE 2006 INFOCOM; 23–29 April 2006; Barcelona, Spain. Piscataway, NJ, USA: IEEE. pp. 1–12.
[14] Erramill V, Crovella M, Taft N. An independent-connection model for traffic matrices. In: ACM 2006 Internet Measurement Conference; 25–27 October 2006; Rio de Janeiro, Brazil. New York, NY, USA: ACM. pp. 251-256.
[15] Zhang Y, Roughan M, Willinger W, Qiu L. Spatio-temporal compressive sensing and Internet traffic matrices. SIGCOMM Comput Commun Rev 2009; 39: 267–278.
[16] Bharti V, Kankar P, Setia L, Gürsun G, Lakhina A, Crovella M. Inferring invisible traffic. In: ACM 2010 Conference on Emerging Networking Experiments and Technologies (Co-NEXT); 30 November–3 December 2010; Philadelphia, PA, USA. New York, NY, USA: ACM. pp. 22:1–22:12.
[17] Gürsun G, Crovella M. On traffic matrix completion in the Internet. In: ACM 2012 Internet Measurement Conference; 14–16 November 2012; Boston, MA, USA. New York, NY, USA: ACM pp. 399-412.
[18] Dabek F, Cox R, Kaashoek F, Morris R. Vivaldi: A decentralized network coordinate system. SIGCOMM Comput Commun Rev 2004; 34: 15-26.
[19] Liao Y, Du W, Geurts P, Leduc G. Dmfsgd: A decentralized matrix factorization algorithm for network distance prediction. IEEE ACM T Network 2013; 21: 1511-1524.
[20] Madhyastha HV, Anderson T, Krishnamurthy A, Spring N, Venkataramani A. A structural approach to latency prediction. In: ACM 2006 Internet Measurement Conference; 25–27 October 2006; Rio de Janeiro, Brazil. New York, NY, USA: ACM. pp. 99-104.
[21] Mao Y, Saul LK. Modeling distances in large-scale networks by matrix factorization. In: ACM 2004 Internet Measurement Conference; 5–7 November 2004; Vancouver, Canada. New York, NY, USA: ACM. pp. 278–287.
[22] Wong T, Jacobson V, Alaettinoglu C. Internet routing anomaly detection and visualization. In: 2005 International Conference on Dependable Systems and Networks; 28 June–1 July 2005; Yokohama, Japan. Piscataway, NJ, USA: IEEE. pp. 172–181.
[23] Zhang B, Ng TSE, Nandi A, Riedi R, Druschel P, Wang G. Measurement based analysis, modeling, and synthesis of the internet delay space. In: ACM 2006 Internet Measurement Conference; 25–27 October 2006; Rio de Janeiro, Brazil. New York, NY, USA: ACM. pp. 85–98.
[24] Ringberg H, Soule A, Rexford J, Diot C. Sensitivity of PCA for traffic anomaly detection. SIGMETRICS Perform Eval Rev 2007; 35: 109–120.
[25] Savage S, Collins A, Hoffman E, Snell J, Anderson T. The end-to-end effects of Internet path selection. In: ACM 1999 SIGCOMM; 31 August–3 September 1999; Cambridge, MA, USA. New York, NY, USA: ACM. pp. 289–299.
[26] Mühlbauer W, Uhlig S, Feldmann A, Maennel O, Quoitin B, Fu B. Impact of routing parameters on route diversity and path inflation. Computer Networks 2010; 54: 2506–2518.
[27] Hiran R, Carlsson N, Gill P. Characterizing large-scale routing anomalies: a case study of the China Telecom incident. In: Springer-Verlag 2013 Passive Active Measurement; 18–19 March 2013; Hong Kong. Berlin, Germany: Springer. pp. 229-–238.
[28] Al-Musawi B, Branch P, Armitage G. BGP anomaly detection techniques: a survey. IEEE Commun Surv Tut 2017; 19: 377–396.
[29] Deshpande S, Thottan M, Ho TK, Sikdar B. An online mechanism for BGP instability detection and analysis. IEEE T Comput 2009; 58: 1470–1484.
[30] Zhang K, Yen A, Zhao X, Massey D, Wu SF, Zhang L. On detection of anomalous routing dynamics in BGP. In: Springer 2004 International Conference on Research in Networking; 9–14 May 2004; Athens, Greece. Berlin, Germany: Springer. pp. 259–270.
[31] Sriram K, Borchert O, Kim O, Gleichmann P, Montgomery D. A comparative analysis of BGP anomaly detection and robustness algorithms. In: IEEE 2009 Cybersecurity Applications Technology Conference for Homeland Security; 3–4 March 2009; Washington, DC, USA. Piscataway, NJ, USA: IEEE. pp. 25-38.
[32] Ganiz MC, Kanitkar S, Chuah MC, Pottenger WM. Detection of interdomain routing anomalies based on higherorder path analysis. In: IEEE 2006 International Conference on Data Mining; 18–22 December 2006; Hong Kong. Piscataway, NJ, USA: IEEE. pp. 874–879.
[33] Fischer F, Fuchs J, Vervier PA, Mansmann F, Thonnard O. Vistracer: A visual analytics tool to investigate routing anomalies in traceroutes. In: ACM 2012 International Symposium on Visualization for Cyber Security (VizSec); 15 October 2012; Seattle, WA, USA. New York, NY, USA: ACM. pp. 80–87.
[34] Moriano P, Iyer S, Camp LJ. Characterization of Internet Routing Anomalies through Graph Mining. Technical Report. Bloomington, IN, USA: Indiana University School of Informatics, Computing, and Engineering, 2017.
[35] Hiran R, Carlsson N, Shahmehri N. Crowd-based detection of routing anomalies on the Internet. In: IEEE 2015 Conference on Communications and Network Security; 28–30 September 2015; Florence, Italy. Piscataway, NJ, USA: IEEE. pp. 388-396.
[36] Lim H, Hou JC, Choi CH. Constructing Internet coordinate system based on delay measurement. In: ACM 2003 Internet Measurement Conference; 27–29 October 2003; Miami Beach, FL, USA. New York, NY, USA: ACM. pp. 129-142.