An Entropy Based Algorithm to Find Critical Traffic Matrices

The entropy is a measure of diversity and homogeneity of one microstate in thermodynamic, which reflects the probably distribution of one microstate of the system. A traffic matrix has tremendous potential utility for many IP network engineering applications. In practical networking applications, dealing with thousands of measured traffic matrices is often inconvenient. This seriously limits the applicability of traffic matrices. So it is highly desirable to be able to extract a small number of "critical" traffic matrices. We study the problem of Critical Traffic Matrices Selection (CTMS) in this paper. We developed an approximation algorithm called MinMat which preselects a group of matrices as critical matrix candidates based on entropy analysis. We evaluated MinMat by a large collection of real traffic matrices collected in campus network and Abilene network. Our results demonstrated that MinMat algorithm are effective than K-means, Hierarchical Agglomeration and by simulating on totem we concluded that a small number of critical traffic matrices suffice to yield satisfactory performance.