基于AP算法的Internet自治系统层紧凑路由研究  

Compact Routing for Internet-AS Level Based on AP Algorithm

作　　者：任智博 傅忠谦[1] 刘勇[1] 蔡世民[1] 

机构地区：[1]中国科学技术大学电子科学与技术系

出　　处：《电子技术（上海）》2011年第6期12-14,共3页Electronic Technology

摘　　要：提出了一种基于AP算法的Internet自治系统层紧凑路由算法。用r近邻的负距离表示节点对的相似度,得到网络的相似度矩阵。基于相似度矩阵,利用AP算法对网络进行划分,得到每个聚类簇的基点。在聚类后的网络上进行紧凑路由。通过对Internet自治系统层网络拓扑数据进行大量实验,确定了AP算法中偏好参数的取值范围,并分析了该参数与路由性能中伸长系数和路由表长度的关系。实验结果表明该算法可以同时获得很小的平均伸长系数和很小的路由表长度,实现Internet自治系统层紧凑路由。A compact routing algorithm for Internet-AS Level based on AP algorithm is proposed.The similarity matrix of AP algorithm is obtained according to the negative distance among r-nearest neighbors.The network is clustered into different modules with labeled landmark via AP algorithm.The routing performance is computed based on clustered networks.The proper value of self-similarity,or so-called Preference which is a key argument of AP,is determined through large amount of experiments on Internet topology data.In particular,the relationship between self-similarity and routing performance is analyzed.The results show that the AP-based routing algorithm achieves very low stretch and very short route table length simultaneously,and realizes a compact routing of Internet-AS Level.

关 键 词：紧凑路由 聚类 AP算法 复杂网络 

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