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