SOAST-1:一种综合优化的AS级拓扑推理算法

SOAST-1:A Synthetic Optimized Algorithm for AS-level Topology Inference

网络拓扑推理是网络管理系统的基本功能之一,AS级拓扑推理是其重点和难点。本文概括了目前已提出的,基于路径和基于Traceroute的两类AS级拓扑推理算法;针对它们的优缺点,提出了一种综合优化的AS级拓扑推理算法:SOAST 1。SOAST 1以BGP路由表作为路由信息的主要来源,以 Traceroute探测作为辅助手段,综合了上述两类 AS级拓扑推理算法的优点。算法分析和实际运行结果表明SOAST 1算法能够取得良好效果。

Network topology inference is one of the basic functions of a network management system, and the AS-level topology inference is its focus and difficult point. The paper summaries the two classes of the existing algorithms of Path-based and Traceroute-based AS-level topology inference. To aim directly at their features and drawbacks, we present a synthetic optimized AS-level topology inference algorithm named SOAST-1. In SOAST-1, the BGP routing table acts as the primary routing information resource, while the Traceroute exploration as the additional means, then the features of the two classes of existing algorithms are combined. The effects of SOAST-1 have been confirmed by the algorithmetic analysis and practical running.