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

• 作者: 刘宇靖 吕保平 孙力伟 彭伟
• 来源期刊: 计算机应用研究
• 关键词: AS拓扑 监测点 最短路径树
• 年，卷（期）: 2010,（9）
• 页码范围: 3473-3475
• 分类号: TP309
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2010.09.073

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	彭伟	国防科学技术大学计算机学院	29	510	12.0	22.0
2	孙力伟	国防科学技术大学计算机学院	2	1	1.0	1.0
3	刘宇靖	国防科学技术大学计算机学院	2	17	1.0	2.0
4	吕保平	国防科学技术大学计算机学院	1	1	1.0	1.0