Low cost network traffic measurement and fast recovery via redundant row subspace-based matrix completion

Figures & data

Table 1. List of notations.

Symbol	Meaning
${\mathbf{M}}_t$	tth row of a matrix $\mathbf{M}$
${\mathbf{M}}^t$	tth column of the matrix $\mathbf{M}$
$\mathbf{U}$	column subspace spanned by a matrix
$\mathbf{V}$	row subspace spanned by a matrix
$\hat{\mathbf{U}}$, $\hat{\mathbf{V}}$	estimated subspace
Ω	set of sampling locations
$|\mathrm{\Omega }|$	cardinality of Ω
$x_{\mathrm{\Omega }}$	sub-vector of x from the sampling coordinate set Ω
$\Vert x\Vert$	${\ell }_2$ norm of vector x

Figure 1. Good low-rank structure of real traffic traces.

Figure 2. Leverage score of two real network traffic flow traces.

Figure 3. Coherence feature of two real network traffic flow traces.

Figure 4. Example of high coherent matrices.

Figure 5. Problem.

Figure 6. Big recovery error of use the column subspace-based methods in high column-coherence case.

Figure 7. Solution overview.

Figure 8. An example of select largest residual from the current row subspace.

Table 2. Data description.

Data set	Description	Type
Abilene	Collects network traffic data every 5 minutes in 24 weeks in the Abilene network, which consists of 12 routers, and thus has 144 OD pairs.	Network traffic
GÈANT	Collects network traffic data every 15 minutes in several months in the GÈANT network, which consists of 23 routers, and thus has 529 OD pairs.	Network traffic
Synthetic	The Synthetic data set is generated as follows: (1) generate a low-rank matrix $\mathbf{M}$ with its size being $3000\times 20000$; (2) randomly select 5 rows and modify their values; (3) inject a Gaussian noise matrix $\mathbf{Z}$ into $\mathbf{M}$. Here we limit $\Vert \mathbf{Z}{\Vert }_F/\Vert \mathbf{M}{\Vert }_F=0.2$, where $\Vert \cdot {\Vert }_F$ denotes the Frobenius norm.	Generated

Figure 9. Parameter impacts.

Figure 10. Recover error for all schemes.

Figure 11. Sample number to achieve the same recovery accuracy.

Figure 12. Sampling time to achieve same recovery accuracy.

Figure 13. Recovery time to achieve same recovery accuracy.

Figure 14. Compare with column-based scheme.

Figure 15. Compared with non-redundant scheme.