一种基于信息熵的关键流量矩阵发现算法  

Algorithm Based on Entropy for Finding Critical Traffic Matrices

作　　者：王宏[1] 龚正虎[1] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073

出　　处：《软件学报》2009年第5期1377-1383,共7页Journal of Software

基　　金：国家自然科学基金No.60803153;国家高技术研究发展计划(863)No.2008AA01A325~~

摘　　要：研究关键流量矩阵发现问题,提出了近似算法MinMat.引入信息熵和耗费函数等概念,计算流量矩阵的信息熵,选取信息熵较大的若干个矩阵作为候选关键矩阵,然后对最小耗费的簇进行合并,直到最后获得需要的流量矩阵.使用Abilene提供的网络流量矩阵进行实验,使用Totem模拟验证了MinMat算法选择结果的有效性.理论分析与实验结果表明,MinMat比K-means层次凝聚CritAC效率更高,选择结果具有更好的代表性.This paper studies the critical traffic matrices selection problem and develops an algorithm called MinMat which uses information entropy to select the first critical matrices at first, then takes merging cost into consideration when agglomerating a pair of clusters. The algorithm is evaluated by using a large collection of real traffic matrices collected in Abilene network. Theoretical analysis and experimental results demonstrate that MinMat algorithm is more effective than K-means, Hierarchical Agglomeration, CritAC, and by simulating on Totem, it is concluded that a small number of critical traffic matrices suffice to yield satisfactory performance.

关 键 词：流量矩阵 流量测量 K-MEANS CritAC MinMat 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]