摘要：基于BGP协议的域间路由系统是Internet的核心基础设施。研究域间路由系统在自治系统AS级的拓扑结构，深入理解并揭示AS拓扑的结构及连通性方面的特性，对于提高互联网路由系统的安全性、健壮性以及性能都具有重要的指导意义。AS之间的商业关系模型是互联网域间路由系统的基本模型之一，是AS拓扑研究的基础。受商业关系的约束，AS拓扑的结构与连通性呈现出了与普通无向图或有向图所不具备的特性：层次结构特性与AS路径的无谷底约束。本文提出了针对AS拓扑的层次划分算法，对AS拓扑的连通性做了深入研究，分析并验证了顶级AS的全互联结构，并进一步阐述了从宏观上对单个AS的连通性的评估方法。

关键词：域间路由 自治系统 商业关系 层次结构 连通性 

单位：国防科学技术大学计算机学院 湖南长沙410073