Traffic matrix estimation in large-scale IP networks

Understanding traffic matrices is useful for network design and so forth, but it is difficult to directly measure traffic matrices in IP networks. There is an existing method to estimate traffic matrices by link traffic information which is easy to measure, and routing information. However, this method requires significantly longer computation time as network size grows. This paper proposes large-scale traffic matrix estimation methods using a divide-and-conquer approach. The network is divided into multiple blocks, traffic matrices are estimated per block and estimation results are combined. In terms of division and combination, this paper proposes two detailed methods. By simulation, it is shown that both of the proposed methods can significantly improve computation time, while keeping estimation accuracy of the existing method. In particular, one of the proposed methods can perform traffic matrix estimation within practical computation time in a network of thousands of nodes.

I. Introduction

Amount of data traffic between every pair of network ingress/egress points is called traffic matrix. Ingress/egress points may be edge routers, PoPs, or ingress/egress links of the network. Understanding traffic matrices is crucial for network operation. For example, it can be used to understand current network status, and to design network (e.g., capacity design, topology design) in mid to long-term [1] [2].