| 摘要: |
| 研究关键流量矩阵发现问题,提出了近似算法MinMat.引入信息熵和耗费函数等概念,计算流量矩阵的信息熵,选取信息熵较大的若干个矩阵作为候选关键矩阵,然后对最小耗费的簇进行合并,直到最后获得需要的流量矩阵.使用Abilene提供的网络流量矩阵进行实验,使用Totem模拟验证了MinMat算法选择结果的有效性.理论分析与实验结果表明,MinMat比K-means层次凝聚CritAC效率更高,选择结果具有更好的代表性. |
| 关键词: 流量矩阵 流量测量 K-means CritAC MinMat |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.60803153 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2008AA01A325 (国家高技术研究发展计划(863)) |
|
| Algorithm Based on Entropy for Finding Critical Traffic Matrices |
|
WANG Hong,GONG Zheng-Hu
|
| Abstract: |
| 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. |
| Key words: traffic matrix flow measure K-means CritAC MinMat |
