互联网规模的急剧增加给传统路由算法带来了巨大的挑战,学者们在努力的设计能够大大降低路由表长度,同时又具有较小伸长系数的路由方法。本文在全面分析比较各种路由算法特别是各种紧凑路由算法的基础上,提出了一种以网络社团结构划分为核心思想,利用AP(Affinity Propagation)聚类算法对互联网自治系统层拓扑结构进行社团结构划分,从而现实紧凑路由的算法,可称为APCR(Affinity Propagation Compact Routing)算法。本文主要做了以下工作:通过全面总结各种路由算法特别是各种紧凑路由算法的性能和优缺点,发现地标路由具有广阔的前景,而地标路由的核心问题就是将网络进行恰当的社团结构划分,并且找到每个社团内部的地标(landmark)。通过对各种社团划分算法尤其是AP算法的分析总结,发现利用AP算法不仅能将网络进行划分,而且能找到每个类中的基点,即地标。因此本文把AP算法和地标路由结合起来,提出了APCR算法。在APCR算法中,对网络中任一节点,考虑它的r近邻,并给出该节点到它的这些近邻的相似度度量。采用两点间的负距离度量相似度,从而得到网络的相似度矩阵。基于相似度矩阵,利用AP算法对网络进行划分,得到每个聚类簇的基点。在聚类后的网络上进行地标路由。通过对互联网自治系统层网络拓扑数据进行大量实验,确定了APCR算法中偏好参数的取值范围,并分析了该参数与伸长系数和路由表长度的关系。实验结果表明该算法可以同时获得很小的平均伸长系数和很小的路由表长度,并且该算法构造地标集的方法跟传统路由算法有着本质不同,实现了一种针对互联网自治系统层紧凑路由的新方法。