基于OSPF协议的大规模网络拓扑发现模型

蒋亚平,郭 浩,郭培根

(郑州轻工业学院 计算机与通信工程学院,郑州 450002)

基于OSPF协议的大规模网络拓扑发现模型

蒋亚平,郭 浩,郭培根

(郑州轻工业学院 计算机与通信工程学院,郑州 450002)

针对传统大规模网络拓扑发现模型的准确性、完整性、实时性的局限性,借鉴OSPF协议周期性传播网络拓扑信息的机理,提出了基于OSPF协议的大规模网络拓扑发现模型LNTDM.该模型首先采用被动检测方式,通过获取OSPF协议中的链路状态更新报文,分析其中Router LSA、Network LSA获得区域内网络拓扑,然后通过边界路由获取的Summary Network LSA进行分析获得区域间网络拓扑,从而完成大规模网络拓扑结构的发现.实验结果表明,该模型能准确完整的获取大规模网络拓扑,可以很好的弥补现有大型网络拓扑发现技术的不足,实际应用前景广阔.

网络拓扑;OSPF协议;Router LSA;Network LSA;Summary Network LSA

随着计算机技术的发展,网络在国家的政治、经济、军事等领域的基础作用越发突出.网络一旦受损,几乎所有的社会系统将无法运行,而网络拓扑不仅能使使用者了解整个网络结构,对网络中的重要节点、数据流向等信息进行分析,而且可以对网络空间进行高效管理、合理分配资源以及有效的安全监测和防护[1].

近年来,大规模网络拓扑发现技术在国内外的研究取得了一定的进展.Aman Shaikh 等[2]提出利用OSPF 协议报文被动探测技术建立网络拓扑,但由于侧重分析网络实体的数目和接口,对于元素之间的连接关系缺少深入分析.Spring等[3]在RockFuel项目探测大规模网络拓扑中使用分布式、主动探测的技术,能够快速扫描网络空间,但需要发送大量探测数据包,增加了网络负担.王慧等[4]提出了TAOS 算法,通过获取LSU来计算网络拓扑为区域内和区域间网络拓扑发现提供了思路,但在多区域的大规模网络拓扑中往往得不到完整拓扑.

本文针对现有大规模网络拓扑发现技术的不足,提出了基于OSPF协议的拓扑发现模型LNTDM(Large-scale network topology discovery model).该模型在不增加网络负担的情况下,可以准确、完整、实时地得出网络拓扑.

1 LNTDM模型原理

图1 典型网络拓扑Fig.1 Typical network topology

OSPF(Open Shortest Path First)是用于自治系统(autonomous system,AS)内的链路状态路由协议,一个大型自治系统通常被划分为多个区域(Area),区域之间相对独立,用区域号(Area ID)标识[5].每台连接到特定OSPF区域的路由器在网络状态稳定情况下都应该学习到完全相同的拓扑数据.每台路由器在自己的链路状态数据库(LSDB)中存储独立LSA(链路状态通告)数据.由于承载着LSA的LSU的周期性传递,可以通过被动获取的方式得到该报文进行分析从而得到Area ID 、LinkStateID、 Advertising Router、 RouterID 等拓扑信息,综合以上拓扑信息构建网络拓扑.本文提出的LNTDM模型分为两个模块:一是区域内网络拓扑发现.二是区域间网络拓扑发现.根据OSPF中的四种网络链接类型更好的展开对LSA的分析,图1展示了一个典型网络拓扑,路由器相相关配置在这里不再赘述,查看配置结果分析网络链路类型.本文将一直使用这个网络拓扑做分析.

1.1区域内网络拓扑发现

区域内网络拓扑发现是在获取LSU报文的基础上过滤Router LSA和Network LSA,根据四种网络类型进行不同的处理.当网络类型是point-to-point、stub或者virtual时记录其Advertising router、link ID、link Data三个字段的拓扑连接信息,得到完整的网络连接信息;当网络类型是transit时,由Router LSA获取Advertising Router、Link ID字段信息,由Network LSA获得Link State ID 和Attached Router字段信息.整合所得到的transit类型的信息,判断Link ID和Link State ID字段是否一致,一致则构成transit类型的三个字段的拓扑连接信息.

图2 Router LSA的详细拓扑类型Fig.2 Detailed topology type of Router LSA

1.1.1 点对点和末节网络 从图1可以看出R1有三个末节网络(stub),两个点对点网络(piont-to-point).R2和R3的Router LSA中也有相同的信息,路由器有足够的信息可以判断通过那条末节网络来连接到哪台路由器,然后使用接口配置的IP地址来判断连接到其他路由器的接口.图2显示了基于R1、R2、R3Router LSA中所包含的详细信息构造出来的拓扑类型.

1.1.2 传输网 OSPF协议中SPF(最短路径优先算法)要求使用节点和节点之间的链路来构建拓扑模型.具体来说,每条链路必须是在一对节点之间,但当存在多路访问数据链路(如图1中area1左半部分中的三个路由器连接在同一个子网内)时,OSPF必须对其进行抽象描绘即选举指定路由器(DR)作为伪节点使用.如图3传输网.

图3 传输网Fig.3 The transmission network

1.1.3 虚链路 OSPF虚链路允许两台连接到同一非骨干区域的ABR通过该非骨干区域建立邻居关系,即便这两台ABR被许多其他路由器和子网分隔开.虚电路表现为两台路由器之间的虚拟的点到点链接.如图1,R2和R3.

1.2区域间网络拓扑发现

区域间网络拓扑是过滤含有Summary Network LSA的LSU报文获得Area ID,分析Summary Network LSA,获得Advertising router及所对应的Link ID字段,从获得的这些字段中可得到一个自治系统的所有区域ID号,这些区域中的边界路由器的ID号,以及这些区域的所有子网,进一步分析可以得到ABR都和那些区域相连等拓扑信息.区域间的路由信息依靠ABR创建的类型三LSA转递,而区域间的网络拓扑可以通过获取ABR产生的Summary Network LSA分析得来.OSPF的重要特征之一是它的灵活性,该协议可以使用ABR将任何区域构成的互联的网络连接在一起.ABR能够处理一组区域构成的全网状拓扑(每个区域都与其他所有区域相连)、部分网状拓扑、一个区域连接到下一个区域的链状拓扑或者其他任何网络配置,它也能处理随着时间推移可能出现的拓扑变化.

ABR的在它不了解区域内部拓扑的情况下,只是接受从区域传递给它的信息并将这些信息与其他区域共享.在图1中捕获ABR产生的LSU,读取Area ID和Summary Network LSA中的Advertising router字段,从而得到区域间的网络拓扑如图4所示.

图4 区域间网络拓扑Fig.4 Inter-area network topology

2 算法实现

本文提出的LNTDM模型基本思想是:提取包含拓扑信息的LSU,在拓扑结构不发生变化的情况下得到所有LSA[6-7],针对三类不同的LSA进行不同操作,得出完整拓扑列表AS后算法结结束.LNTDM算法分两步:①数据处理,建立域内拓扑连接关系集合CONNET.②建立域间拓扑连接关系集合ABR,合并CONNET和ABR得到集合AS.

1)数据处理,定义报文LSUi,i=1,2,…,n.按接收顺序排列.

设V为某一区域的结点集合,V={v|v=〈RouterIDi,AreaIDi,AR〉，RouterIDi,取自LSUi头部,AR∈LSA头部}.

设C、N为区域内连接的集合,C={c|c=〈RouterIDi,AreaIDi,AR〉，〈Type,LinkIDi,LinkData〉〉，RouterIDi,AreaIDi取自LSUi头部,AR∈RouterLSA},将三元组〈Type,LinkID,LinkData〉简记为l,当存在多个相同的RouterLSA时按照接收顺序替换旧信息.

N={n|n=〈RouterIDi,AreaIDi,AR,LinkStateID,AttachedRouter〉，RouterIDiAredIDi,取自LSUi头部,AR∈NetworkLSA},当存在多个相同的NetworkLSA时按照接收顺序替换旧信息.

连接集合C，V,检查∃C.Type≠trasit满足C.AR=V.AR,C.LinkID=N.LinkStateID,将两个集合连接得到集合CONNET,CONNET={connet|conner=〈RouterIDi,AreaIDi,AR，l〉}.

连接集合C，V，N,检查∃C.Type≠trasit满足C.AR=V.AR,C.LinkID=N.LinkStateID,将集合连接加入CONNET中.

图5 拓扑发现算法流程图Fig.5 The flow chart for topology discovery algorithm

2)建立区域间拓扑连接关系集合,合并集合得到AS.

设B为边界结点的集合,B={b|b=〈RouterIDi,AreaIDi…n,AR〉，RouterIDiAredIDi…n,取自LSUi头部，RouterIDi∈{ABR,ABSR},AR∈SummaryNetworkLSA}.

设E为区域间建立的连接的集合,E={e|e=〈RouterIDi,AreaIDi……AreaIDn,AR,LinkIDi〉}.

连接集合B,E检查是否存在∃B.RouterIDi∈V.RouterID,满足B.AR=E.AR,由B.AR和E.AR将集合B和E连接,得到集合ABR.

ABR={abr|abr=〈RouterIDi,AreaIDi…AreaIDn,AR,LinkIDi〉}.

将CONNET按照同一AreaID归类,得到n个区域集合CONNET1…CONNETn,检查同一AreaID中是否存在∃CONNRT.Type=stub,∃ABR.RouterIDi∈CONNET.RouterID,满足ABR.LinkID=CONNET.LinkID,将两个集合合并为AS.

AS={AS|RouterIDi,conneti…connetn,AR}.

经过以上处理后得到整个网络拓扑连接关系集合.使用上述算法先对区域内网络拓扑进行绘制,再用得到的区域内所有网络子网对其进行比对分析,之后使用ABR对所有区域进行连接从而得到整个网络拓扑.算法流程图如图5所示.

3 实验结果及分析

图6 两个学院网络拓扑Fig.6 The network topologies of two college

本实验遍布校园计共设置了20个不同的检测点,用于捕获网络上流经的OSPF协议报文.经过两周的搜集,剔除其余OSPF报文只保留LSU,然后使用LNTDM模型对校园网进行拓扑发现,最终确定校园中包含了1个路由器,16个三层设备和145个子网.然后对计通学院和经管学院的网络拓扑进行绘制.图6显示了两个学院的网络拓扑结构.其中areaID为0.0.0.20,包含了1个路由器和6个三层设备和33个子网.

将图6与网络中心提供的实际拓扑图相比,除了子网的数目少了俩个以外,其余链路信息基本准确.会出现上述的结果主要是因为设置的检测点没有覆盖所有子网,得到这样的结论之后又在之前没有设立检测点的区域进行检测,得到了之前没有的两个子网的拓扑信息.实验表明文中提出的算法能够有效的处理OSPF报文,针对多个区域的大型网络拓扑结构发现遇到的困难找到了合理的解决方案.

4 结语

文中提出的一种基于OSPF协议的网络拓扑发现算法改进,该算法通过对区域内网络拓扑发现和区域间网络拓扑发现,得到了整个自治系统的连接信息,从而进行拓扑发现解决了跨区域网络拓扑发现的困难.但由于OSPF报文的获取需要跨越多个区域,导致报文获取不全的现象.结合采集器在不同区域建立隧道从而获取完整的OSPF Update报文将是下一步的研究方向.

[1] 赵帆,罗向阳,刘粉林.网络空间测绘技术研究[J].网络与信息安全学报,2016(9):1-11.

[2] SHAIKH A,GREENBERG A.OSPF Monitoring: Architecture,Design and Deployment Experience[C]∥Proc of the 1st Symposium on Networked System Design and Implementation,San Francisco,CA:[s.n.],2004: 57-70.

[3] SPRING N,MAHAJAN R,WETHERALL D.Measuring ISP topologies with rocketfuel[J].ACM Sigcomm Computer Communication Review,2002,32(4): 133-145.

[4] 王慧,罗军勇,寇晓蕤.基于OSPF协议报文的网络拓扑分析算法[J].计算机工程,2008(6):103-105.

[5] CHARLES M KOZIEROK.The TCP/IP Guide,A Comperhensive,Illustrated Internet Protocols Reference,published by No Starch Press.

[6] 潘楠,王勇,陶晓玲.基于OSPF协议的网络拓扑发现算法[J].计算机工程与设计,2011(5):1550-1553,1567.

[7] 赵天福,周丹平.基于OSPF协议的网络拓扑发现技术的实现[J].江南大学学报(自然科学版),2008(2):151-156.

责任编辑：时凌

LargeScaleNetworkTopologyDiscoveryModelBasedonOSPFProtocol

JIANG Yaping,GUO Hao,GUO Peigen

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China )

For the traditional large-scale network topology discovery model,its real-time,accuracy and characterization are relatively limited.By referring to the mechanism of periodic propagation of network topology information by OSPF protocol,a Large Scale Network Topology Discovery Model Based on OSPF Protocol (LNTDM) is proposed.The model adopts the passive detection.Firstly,the link state update packets in the OSPF protocol are obtained and the router LSA and Network LSA are analyzed to obtain regional network topology.And then the Summary Network LSA obtained through the boundary routing is analyzed to obtain inter-regional network topology,thus completing the large-scale network topology discovery.The experimental results show that the model can accurately obtain the large-scale network topology and it can make up for the shortcomings of the existing large-scale network topology discovery technology.The practical application prospect of the model is broad.

network topology;OSPF protocol;router LSA;network LSA;summary network LSA

2017-05-24.

河南省科技厅科技攻关基金项目(0624220084);河南省科技厅基础与前沿技术项目(122300410255).

蒋亚平(1972-),男,博士,副教授,主要从事网络安全、计算机网络的研究.

1008-8423(2017)04-0434-04

10.13501/j.cnki.42-1569/n.2017.12.018

TP393

A