Low Cost Online Network Traffic Measurement with Subspace-Based Matrix Completion

Traffic Matrix (TM) is important for network operation and management. However, it is hard to measure the complete TM due to the high measurement cost. Few recent studies propose using sparse measurement with only a subset of origin and destination pairs (OD pairs) while the other OD pairs are reconstructed through matrix completion. Although effective, current sparse network monitoring schemes can hardly support online network monitoring which requires scheduling the sample taking adaptively in each new time slot one by one. To meet the online network monitoring scenario, we propose a sparse network monitoring scheme by exploiting subspace-based matrix completion. Several novel techniques are proposed in our scheme. First, to capture the dynamic rank feature, we design the scheme based on sliding window and propose an algorithm to estimate the rank of current window even though we don't know the data of the upcoming time slot. Secondly, based on the rank estimated, we propose an adaptive sampling scheduling algorithm. Finally, we propose a lightweight algorithm to speed up the reconstruction process by reusing the matrix calculation results in the previous time slot. The experimental results demonstrate that our scheme guarantees the high precision of network-wide TM monitoring while significantly reducing the measurement cost.