论文研究 基于最短路径树覆盖的AS拓扑监测点部署方法.pdf

面向互联网AS级拓扑监测应用，提出了一种基于最短路径树SPT覆盖的算法，用于选择部署最少的监测点，发现尽量完整的AS拓扑。该算法求出所有顶点的最短路径树，按照启发式策略选择最小的顶点集合，使集合中节点的最短路径树可以覆盖全图的边。采用CAIDA AS -links的数据对算法进行验证，SPT算法选择了750个左右的监测点，即可发现互联网中16 500多个AS之间（约30 000条左右）的链路。与随机选择节点进行覆盖的方法相比，该方法选择的监测点数目减少了近37.5%。