A compressive sensing-based network tomography approach to estimating origin-destination flow traffic in large-scale backbone networks

A traffic matrix can exhibit the volume of network traffic from origin nodes to destination nodes. It is a critical input parameter to network management and traffic engineering, and thus it is necessary to obtain accurate traffic matrix estimates. Network tomography method is widely used to reconstruct end-to-end network traffic from link loads and routing matrix in a large-scale Internet protocol backbone networks. However, it is a significant challenge because solving network tomography model is an ill-posed and under-constrained inverse problem. Compressive sensing reconstruction algorithms have been well known as efficient and precise approaches to deal with the under-constrained inference problem. Hence, in this paper, we propose a compressive sensing-based network traffic reconstruction algorithm. Taking into account the constraints in compressive sensing theory, we propose an approach for constructing a novel network tomography model that obeys the constraints of compressive sensing. In the proposed network tomography model, a framework of measurement matrix according to routing matrix is proposed. To obtain optimal traffic matrix estimates, we propose an iteration algorithm to solve the proposed model. Numerical results demonstrate that our method is able to pursuit the trace of each origin-destination flow faithfully. Copyright (c) 2014 John Wiley & Sons, Ltd.