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

AS topology monitor deployment method based on cover of shortest path trees

作　　者：孙力伟[1] 彭伟[1] 刘宇靖[1] 吕保平[1] 

机构地区：[1]国防科学技术大学计算机学院

出　　处：《计算机应用研究》2010年第9期3473-3475,共3页Application Research of Computers

基　　金：国家“973”计划资助项目(2009CD320503);国家“863”计划资助项目(2008AA01A325)

摘　　要：面向互联网AS级拓扑监测应用,提出了一种基于最短路径树SPT覆盖的算法,用于选择部署最少的监测点,发现尽量完整的AS拓扑。该算法求出所有顶点的最短路径树,按照启发式策略选择最小的顶点集合,使集合中节点的最短路径树可以覆盖全图的边。采用CAIDAAS-links的数据对算法进行验证,SPT算法选择了750个左右的监测点,即可发现互联网中16500多个AS之间（约30000条左右）的链路。与随机选择节点进行覆盖的方法相比,该方法选择的监测点数目减少了近37.5%。To deal with the Internet AS level topology monitoring,this paper proposed an SPT method based on the cover of shortest path tree. This two-phased approach attempted to minimize the number of monitors,while found a relative integrated topology. First,found the shortest path tree of each node,then found a minimum set of monitors with a greedy strategy to cover all the edges of the topology. Using the data of AS-links of CAIDA as input of SPT to find the links（ about 30 000） between more than 16 500 ASes,about 750 monitors selected. Compared with the random selection method,the number of monitors were reduced at about 37. 5% .

关 键 词：AS拓扑 监测点 最短路径树 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]