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

Compact Routing for Internet-AS Level Based on AP Algorithm

提出了一种基于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.