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 ofapplications. Therefore, it is important to understand the underlyingmechanisms that give rise to the observed latency values and diagnose the onesthat are unexpectedly high. In this paper, we study the Internet delay spacevia robust principal component analysis (RPCA). Using RPCA, we show that thedelay space, i.e. the matrix of measured round trip times between end hosts,can be decomposed into two components - the expected latency between end hostswith respect to the current state of the Internet and the inflation on thepaths between the end hosts. Using this decomposition, first we study thewell-known low-dimensionality phenomena of the delay space and ask whatproperties of the end hosts define the dimensions. Second, using thedecomposition, we develop a filtering method to detect the paths whichexperience unexpected latencies and identify routing anomalies. We show thatour filter successfully identifies an anomalous route even when its observedlatency is not obviously high in magnitude.