基于最短路径树覆盖的AS拓扑监测点部署方法

摘要

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