一种复合的自治域级拓扑发现方法

胡一非，程　光

(1. 东南大学 计算机科学与工程学院，江苏 南京 211189；2. 东南大学 计算机网络和信息集成教育部重点实验室，江苏 南京 211189)



一种复合的自治域级拓扑发现方法

胡一非1,2，程光1,2

(1. 东南大学 计算机科学与工程学院，江苏 南京 211189；2. 东南大学 计算机网络和信息集成教育部重点实验室，江苏 南京 211189)

随着网络技术的发展，面对新的挑战，传统网络逐渐力不从心，软件定义网络(software-defined network,SDN)领衔的未来网络应运而生，随之而来的是各类网络测量技术纷纷针对未来网络发生演变，但拓扑结构测量在传统网络环境下的作用仍然不可忽视。在自治域级的网络拓扑中，每个自治域都可以简化为一个点,而用两点之间的连线表示自治域间的邻接关系。近年来有许多相关的研究展示了不同的拓扑发现算法。提出了一种简单高效的方法来推断自治域级的拓扑,利用在网络中部署高速采集器采集边界网关协议(border gateway protocol,BGP)路由器上的路由表以及BGP协议的更新信息来推断网络拓扑结构，并判定自治域的相关属性。实验证明了该方法能够达到预期效果，全面、准确地推断网络在自治域级的拓扑结构。

自治域；拓扑发现；边界网关协议(BGP)

0　引　言

近几年来互联网飞速发展，网络的规模变得越来越庞大，结构也越来越复杂。由于传统网络的一些固有缺陷导致未来网络逐渐兴起，吸引了大量研究者的关注，各国争相建设相关的基础设施，在这方面，我国建成了目前世界上最大的IPv6网络中国下一代互联网(China next generation internet，CNGI)。虽然网络技术在进步，但在新的网络体系结构中，拓扑测量仍然显得尤为重要，不仅为各类创新型实验提供了基本的服务，而且在例如分析网络拓扑结构属性[1]、推断网络层级结构[2]、在仿真软件中构造拓扑生成器[3]以及诊断网络故障等任务中均有着不可缺的作用。目前互联网的结构可以看作许多互相连接的子网络，我们把这些子网络称之为自治域(autonomous system，AS)，而边界网关协议[4](border gateway protocol,BGP)就是运行在自治域间用来交换连接信息一种域间路由协议。对于整个互联网，如果不关注自治域内的结构就可以被视作一张图，每个自治域为一个点，而自治域之间的连接则为一条边。

自治域级的拓扑结构可以通过BGP的路由信息来推断。BGP路由表中的每一项都包含了一个“AS路径”的属性，记录了到达一个特定IP地址前缀所经过的AS号，通过求出多个BGP路由表中的“AS路径”的并集，我们可以对网络的拓扑做一个大致的推断；另外，由于网络波动，链路故障及配置错误等原因触发的BGP更新报文也包含了“AS路径”这一属性，因此，可以用来作为通过BGP路由表推断出拓扑的一种补充。本文依托国防科技大学面向广域网实验床的软件定义组网方法-软件定义实验床(software difined testbed,SDTB)，提出了一种通过采集BGP路由表和BGP路由更新信息来推断自治域级拓扑的方法，并为二维路由实验和 IPv6 大规模编址实验提供了支撑，相比其他方法，可以用最小的代价得到最完整的拓扑信息，另外，还提供了一系列相关的辅助拓扑信息，比如时间戳，结点类型等，方便用户决策。

1　相关工作

拓扑发现一直以来都是一个很有价值的研究问题，很多研究者在这一方面已经取得了很多成果。目前主流的方法分为主动和被动2种。文献[5]介绍了一种通过主动发送探测包,采集往返时延(round trip time,RTT)时延信息，从而推断拓扑结构的方法，分析比较了几个影响实验结果的重要因素，并着重展示了4种图形化拓扑结构的技术，文献[6-7]提出了另一种主动测量的启发式方法来推测自治域级的拓扑结构，但主要采集的是traceroute的数据，通过首先得到路由级的拓扑二次推断自治域级的拓扑，难点在于要建立一个IP地址与AS编号的映射，以及如何确定一台路由器是否为边界路由器。针对边界路由器的判断，文献[8]给出了一种基于规则的新方法，区别于传统的基于别名的方法，有更好的性能表现。以上是一些主动测量的方法，能够在精度以及信息覆盖面上更胜被动测量一筹，但边界路由器的判定算法过于复杂，导致测量周期太长，且过分依赖现有的映射信息数据库，当处在实验网络或仿真网络环境而非真实互联网时则有很大困难。文献[9]指出在大规模的网络环境中，通过发送traceroute主动探测包发现拓扑会产生大量冗余流量的缺点。在引入Bloom Filter来降低冗余流量的同时，将监测站按流量目的地址进行分组，进一步缓解了在网络规模较大时性能下降的问题。相比主动测量方法，被动方法在难度上要低，同时具有精度低，信息覆盖面小的问题，文献[10]最早采用了纯被动的方法，采集BGP更新报文，通过对IP地址前缀以不同的更新频度来聚类，推断网络拓扑结构。另外，RouteView[11]和欧洲IP网络路由信息服务(réseaux IP européens routing information service,RIPERIS)[12]是2个著名的采集真实互联网BGP信息的项目，它们通过部署在全球各自的节点，采集来自互联网的真实BGP信息，为研究者提供第一手的数据资料。

2　拓扑发现算法

2.1基于BGP路由表

BGP协议与开放式最短路径优先(open shortest path first,OSPF)[13]等链路状态协议不同，它并不维护一个全局的视图，每个运行BGP协议的边界路由器选择它认为最好的路径并广播给它的邻居，导致的结果就是每一个不同的路由器都有可能存储着不同的路径信息；另外，同一个自治域中可能会存在多个边界路由器，它们之间采用内部网关协议(interior gateway protocol,IGP)交换路由信息，一个边界路由器可能会“隐藏”在另一边界路由器的后面。图1为未接入采集器网络拓扑图。图1中，路由器n1至n7都是自治域中的边界路由器，运行BGP协议，路由器n6到其他自治域的路径都要通过路由器n1，换句话说，对n6来说，n1屏蔽了大部分路由信息。这就决定了只从一个单独的节点中提取的信息不足以反映整个网络的拓扑，我们需要建立一套消息采集机制来最大可能地获取更加全面的拓扑信息。因此，我们在网络中部署了一台BGP信息采集器用来与各BGP路由器通信，抓取路由表。采集器与待测量网络中尽可能多的节点相连，同样运行BGP协议，但不同的是采集器只接收来自其他BGP路由器的更新报文，而不会向他的邻居广播自身存储的路由信息。这样配置是为了保证在采集到尽可能多的路由表的前提下，不影响整个网络的正常通信，否则，将有大量的正常数据流量被引导到采集器上。

我们在实验拓扑中加入了一台采集器，其网络拓扑如图2所示。由于实验网络规模较小，我们将采集器与所有的边界路由器连接，对每个边界路由器而言，它们只是增加了一个邻居，即后来部署的采集器，但由于采集器不广播任何路由消息，其他边界路由器只会定期广播自己的可达网络消息，并不会将流量引导到采集器上。同时，采集器又与普通边界路由器一样，从各邻居路由器广播的路由消息中推导出路径信息，存储在自身的路由表中。

一个典型的BGP路由表的结构如表1所示，主要提取“AS路径”这一属性来推断拓扑结构。“AS路径”是BGP路由表项中一项公认的强制属性，它表示到达目的前缀地址需要经过的一系列AS号。以表1中这条表项为例，这是一个通往10.0.0.0/24网段的路径，下一条地址是10.0.7.1，“AS路径”属性中包含了AS12，AS34，AS56，说明要到达目标网络，需要依次经过12，34，56这3个自治域，由于是依次传播的，显而易见每2个自治域之间是连通的，即存在12—34，34—56这2条路径。由此可见，通过提取“AS路径”中的邻接信息，是可以推断出网络拓扑结构的。图3表示了从“AS路径”推断拓扑的算法流程。首先将拓扑初始化为空，从采集器中的路由表中提取每一项“AS路径”属性，将其中相邻的2个AS号之间标记为“连通”，重复此过程直至处理完所有“AS路径”，得到初步推断的结果。

图1　未接入采集器网络拓扑 　　Fig.1　Topology without acquisition

图2　接入采集器后网络拓扑　　Fig.2　Topology with acquisition

优选路径前缀地址下一跳度量值本地优先级权重AS路径*i10.0.0.0/2410.0.7.111000123456

2.2基于更新信息

互联网是一个庞大且动态的结构，每一秒都会有成千上万的节点加入和退出，如果再考虑网络故障以及配置错误等因素，仅仅靠静态的路由表推断出的拓扑结构一定是不准确的，最多只能算是某一时刻的状态。而BGP路由表也不能准确地反映网络中数据包的传播路径，因为路由表会选择到一个特定前缀地址的最佳路径，忽略其余的，但BGP更新消息却可以保留多条路径。所以，在通过采集器上的路由表推断出拓扑后，还需要持续地接收BGP更新消息，从而获得更加全面和完整的拓扑信息。

BGP更新消息是BGP 4种消息类型之一，也是最主要的一种，负责在自治域传递路由更新信息。它的结构与BGP路由表的结构非常类似，同样，我们利用“AS路径”这一属性来推断拓扑结构。一条BGP更新消息可能同时新增一条路径和撤销一条已有的路径。对于新增的路径，只需要简单地将AS邻接信息设为“连通”，并补充进现有的拓扑中。但对于撤销的路径，不能草率地将相关的“连通”信息删除，因为可能只是出现了一条“更优”的路径，而非物理连接的断开。针对上述情况，设计了一种判定自治域或链路是否“消失”的算法，流程如图4所示，我们事先定义好一个阈值Δt，当接收到撤销报文时记录当前时刻，并且在超过这个阈值之后，如果该报文中撤销的自治域号以及相关路径都不在各路由器的路由表中出现，则认为该自治域或域间连接信息不存在，将其对应的“连通”关系从现有拓扑中删除。根据网络规模的差异，可以改变阈值Δt的大小，本文主要采用图1和图2中的小型实验网络，Δt设置为3 min，在真实的互联网当中，全球的自治域已经多达数十万个，BGP路由表收敛时间长达几十分钟[14]，Δt可能被设置为数小时。

图3　拓扑发现算法流程Fig.3　Process of topology discovery

图4　BGP路由撤销消息处理流程Fig.4　Process of withdraw message

BGP协议[4]规定，当路由消息从一个自治域传递到另一个自治域时，需要在“AS路径”的最前面加上最后一个新到达的自治域号，同一个自治域内2个边界路由器通过IGP协议传递路由信息时，不需要在“AS路径”里添加多个相同的AS号，所以，通常情况下“AS路径”中的AS号不会出现重复，但因为本地配置等原因也可能会出现连续重复的AS号，这种情况下，我们把连续出现的AS合并为一个，然后再按照正常的算法步骤进行计算。

2.3transit节点和stub节点的判定方法

我们把网络中的自治域分成2种类型：transit和stub。在网络拓扑图中，stub节点只出现在一条路径的两端，它不向其他节点提供中转服务，即网络中的流量不能经由它到达其他节点。除此之外的其他节点则为transit节点，因为它们存在于路径的中间，为其他节点提供中转服务。由上述定义得出以下2点结论。

1)在“AS路径”中，处在中间的节点一定是transit节点。设它为x，x的前一个节点为a，后一个节点为b，可知流量从a经过x再到另一个自治域b，符合了transit节点的特征。

2)在“AS路径”中，处在第一个和最后一个的节点不一定是stub节点，因为存在这种情况：一个AS在某一条路由表项是端节点，但在另一条表项中成为了中间节点。

明确了上述2点之后，我们提出一种判定transit节点和stub节点的方法，如图5所示。在采集器的路由表中，遍历所有表项的“AS路径”属性，设所有出现过的AS为集合c，将每个“AS路径”中第一个和最后一个删除，将剩余的所有结点归为transit节点，设为集合t，最后，c-t的部分归为stub节点。区分transit和stub自治域可以使我们对拓扑结构有更加深入的了解，对网络中核心区域和边缘区域的划分有很大的参考价值。

3　实验论证

3.1实验环境

为了验证方法的有效性，作为国家“863”大规模IPv6编址项目的一部分，使用通用开放研究仿真器(common open research emulator,CORE)[15]网络仿真器接入CNGI-CERNET2和CNGI-中国电信两大网络，依托国防科技大学软件定义组网方法SDTB进行了仿真实验。实验搭建了如图1所示的实验网络，包括n1-n7这7个边界路由器，分别属于AS1-AS6这6个自治域，自治域间的连接情况如图5所示。

图5　transit-stub判别算法流程Fig.5　Process of transit-stub discrimination

3.2部署采集器前后的比较

正如前文所述，在部署采集器之前，我们从单个BGP路由器上获得的路由表不足以推断出全面真实的拓扑结构，在图1中，以边界路由器n6为例，在运行BGP协议之后，其上的BGP路由表如表2所示，可见，除了直连网段10.0.7.0/24之外，到达其余网段的路径下一条地址均是10.0.7.1，即路由器n1与n6连接的接口地址。n1本质上对n6屏蔽了到达其他自治域的路径。使用该路由表中的信息运行图3中的拓扑发现算法后，生成的拓扑如表3所示，从表3中可以看出，仅从路由器n6推断出的拓扑中存在大量遗漏。

表2　路由器n6上的路由表Tab.2　Routing table on router n6

表3　由路由器n6推断出的拓扑Tab.3　Topology inferred by router n6

√：实际存在且推断正确×：实际存在但未推断

由于单个路由表不足以作出有效的拓扑推断，我们在网络中部署一台采集器，连接所有其他的BGP路由器，并通过配置一个prefix-list，限制采集器只接收来自邻居的路由更新消息而不会广播自身所记录的路由信息。图2中，网络中央为新加入的采集器，在运行BGP协议且收敛之后，提取出采集器上的BGP路由表，表4展示了部分内容，仅使用表4中展示的部分内容，我们就可以推断出完整的网络拓扑信息，如表5所示。

表4　采集器上部分路由表Tab.4　Partial routing table on the collector

表5　由采集器路由表推断出的拓扑Tab.5　Topology inferred by the collector

通过前后2个实验结果的比较，可以看出存在一些可能性，当仅使用一台路由器中的路由表信息来拓扑结构时，会发生拓扑信息遗漏。网络中每一台边界路由器中都存储了一份以自身视角生成的网络结构，在网络中加入采集器后，它将各个路由器上的路由信息汇总起来，所以，采集器连接的路由器越多，它得到的拓扑信息就越全面。在真实的互联网当中，绝大部分自治域都会在上游与互联网服务供应商(internet service provider,ISP)的网络相连，理论上我们可以把采集器部署为与ISP网络相连的节点，这样可以获得与该ISP相连所有自治域的BGP路由信息。

3.3BGP更新消息

本部分我们采用和上一部分同样的实验网络结构，在整个网络运行BGP协议并达到稳定后，将自治域AS6中的路由器n7与路由器n5和n4连接的2个接口关闭，以此来仿真网络节点的故障。此时，AS5—AS6和AS4—AS6这2条连接已经断开，通过wireshark捕捉到采集器接收到一条来自路由器n7的“撤销”消息，如图6所示。由于此时的n7已经不与其他任何自治域相连，所以，会向采集器发送一条“撤销”消息，将之前广播的所有经过它所在自治域即AS6的路径全部设为无效。记录下此刻时间t，经过Δt=3 min之后，运行一次拓扑推断的算法,结果如表6所示，可以发现，AS5—AS6和AS4—AS6之间的连通关系已经消失了。

图6　“撤销”消息Fig.6　Withdraw message

AS1AS2AS3AS4AS5AS6AS1AS2AS3AS4AS5AS6

3.4transit和stub节点的判定

我们在3.2节中的实验网络基础上增加一个AS7以及路由器n8，构成的实验网络如图7所示。在整个网络运行BGP协议并达到稳定之后，提取采集器上的路由表，并运行上面介绍的transit-stub节点判定算法，节点全集C={1,2,3,4,5,6,7}，将所有路由表项的“AS路径”中两端的节点删除之后，剩余的“AS路径”如表7所示，根据表7中的数据可求得transit节点集t={1,2,3,4,5,6}，stub节点集为c-t={7}。从图7的拓扑结构中也可以发现，AS7是一个末端自治域(stub AS)，除了和采集器之间的链路，有且只有一条与AS5相连的链路，这意味着没有任何其他自治域可以经过它到达另外一个自治域，也就是说它并不提供中转的服务。在真实互联网当中，大部分的transit节点也会在某些“AS路径”的端点出现，因为它们自身同时也会产生某些IP地址前缀。从实验结果来看，该算法是可以准确地识别出“AS路径”中transit节点与stub节点的。

图7　transit-stub判定实验网络Fig.7　Experimental network of transit-stub discrimination

编号AS路径1{5}2{3}3{5,6}4{2}5{5,4}6{4,3}7{1,5}8{2}

4　结束语

网络拓扑对网络研究有着重要的价值，自治域级的拓扑结构更是对了解互联网的结构有着重要意义。本文提出的利用BGP路由表和BGP更新消息推断自治域级拓扑的方法能够准确全面地测量出网络拓扑结构，同时还能提供一些网络节点的辅助信息。但本文的实验是在小型的仿真网络环境下进行的，下一步需要在真实的大规模网络中部署采集器，采集实验数据，并尝试加入主动探测的方法来提供方法的准确性及高效性。

[1]CHEN Q, CHANG H, GOVINDAN R, et al. The origin of power laws in Internet topologies revisited[C]∥IEEE INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. Piscataway, NJ, USA: IEEE, 2002: 608-617.

[2]BATTISTA G D, PATRIGNANI M, PIZZONIA M. Computing the types of the relationships between autonomous systems[C]∥INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies. Piscataway, NJ, USA: IEEE, 2003: 156-165.

[3]MEDINA A, LAKHINA A, MATTA I, et al. BRITE: an approach to universal topology generation[C]∥Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems,2001，Proceedings.Piscataway,NJ,USA:IEEE,2001:346-353.

[4]HARES S, REKHTER Y, LI T. A Border Gateway Protocol 4 (BGP-4)[EB/OL].(2006-01-18)[2016-02-01]. https:∥tools.ietf.org/html/rfc4271.

[5]HUFFAKER B, PLUMMER D, MOORE D, et al. Topology discovery by active probing[C]∥2002 Symposium on Applications and the Internet (SAINT) Workshops. Piscataway,NJ,USA:IEEE,2002:90-96.

[6]CHANG H, JAMIN S, WILLINGER W. Inferring AS-level Internet topology from router-level path traces[C]∥Scalability and Traffic Control in IP Networks. Denver, CO: SPIE, 2001: 196-207.

[7]FAGGIANI A, GREGORI E, IMPROTA A, et al. A study on traceroute potentiality in revealing the Internet AS-level topology[C]∥Networking Conference. Piscataway, NJ, USA: IEEE, 2014: 1-9.

[8]WEI Z, CHEN M, JI L, et al. An AS Border Judgment Method Based on IP Path Information[C]∥IEEE GLOBECOM 2008-2008 IEEE Global Telecommunications Conference. Piscataway, NJ, USA: IEEE, 2008: 1-5.

[9]DONNET B,FRIEDMAN T,CROVELLA M.Improved Algorithms for Network Topology Discovery[C]∥DOVROLIS C.Passive and Active Network Measurement.Berlin Heidelberg,German:Springer,2005:149-162.

[10] ANDERSEN D G,FEAMSTER N,BAUER S,et al.Topology Inference from BGP Routing Dynamics[C]∥Proceedings of the 2Nd ACM SIGCOMM Workshop on Internet Measurement.New York,NY,USA:ACM,2002:243-248.

[11] University of Oregon Route Views Project[EB/OL]. [2016-01-20]. http:∥www.routeviews.org.

[12] RIPE RIS Raw Data[EB/OL]. [2016-01-05]. https:∥www.ripe.net.

[13] MOY J. Ospf version 2[EB/OL]. (1998-10-20)[2016-02-01]. https:∥tools.ietf.org/html/rfc2328.

[14] LABOVITZ C, AHUJA A, BOSE A, et al. Delayed Internet Routing Convergence[C]∥Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. New York, NY, USA: ACM, 2000: 175-187.

[15] AHRENHOLZ J. Comparison of CORE network emulation platforms[C]∥2010-MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE. Piscataway, NJ, USA: IEEE, 2010: 864-869.

胡一非(1989-),男,江苏兴化人,硕士研究生,主要研究方向为计算机网络。E-mail:jsxhhyf@gmail.com。

程光(1973-),男,安徽黄山人,博士,教授，主要研究方向为计算机网络测量,网络安全等。E-mail:gcheng@njnet.edu.cn。

(编辑：刘勇)

The National High Technology Research and Development Program of China(“863” Program)(2015AA015603)

A compound topology discovery method at As-level

HU Yifei1,2, CHENG Guang1,2

(1. School of Computer Science and Engineering, Southeast University, Nanjing 211189, P.R. China;2.Key Laboratory of Computer Network and Information Integration, Southeast University, Ministry of Education,Nanjing 211189, P.R. China)

With the development of network technology, traditional network seems powerless when facing new challenges. Future network cames out at this time led by software defined network(SDN) with many advantages, but topology measurement is as important as it was in traditional environment. In an AS-level topology, we can simply take every single AS as a node, and edges between two nodes means adjacency of ASes. Large numbers of different topology discovery algorithms have been shown recently in various researches. In this paper, a simple but efficient method utilizing high speed collector is deployed in the network to collect border gateway protocol(BGP) routing tables on BGP routers and BGP update messages among them to deduce network topological structure is proposed, and it could also differentiate transit-node and stub-node in the network. Experiments are conducted to prove this method could achieve expected effect which is precisely and completely inferring the topological structure at AS-level.

autonomous system; topology discovery; border gateway protocol(BGP)

10.3979/j.issn.1673-825X.2016.05.018

2016-02-16

2016-04-30通讯作者：程光gcheng@njnet.edu.cn

国家“863”计划项目(2015AA015603)

TN92;TP393

A

1673-825X(2016)05-0729-08