V Bharti, P Kankar, L Setia, G Gürsun, A Lakhina, M Crovella
Proceedings of CoNext
Publication year: 2010

Abstract: A traffic matrix encompassing the entire Internet would be very valuable. Unfortunately, from any given vantage point in the network, most traffic is invisible. In this paper we describe results that hold some promise for this problem. First, we show a new characterization result: traffic matri- ces (TMs) typically show very low effective rank. This re- sult refers to TMs that are purely spatial (have no temporal component), over a wide range of spatial granularities. Next, we define an inference problem whose solution allows one to infer invisible TM elements. This problem relies crucially on an atomicity property we define. Finally, we show ex- ample solutions of this inference problem via two different methods: regularized regression and matrix completion. The example consists of an AS inferring the amount of invisible traffic passing between other pairs of ASes. Using this ex- ample we illustrate the accuracy of the methods as a function of spatial granularity.