网络层与链路层综合拓扑发现算法及其实现


2012,48(4) 拓扑发现是一种用来展现计算机网络设备间连接关系的 技术[1]。作为网络管理技术得以实施的基础,它伴随计算机网 络的出现而诞生,但由于网络的复杂性,拓扑发现并不容易[2]。 因此,该领域也一直是人们研究的重点。从早期的网络层拓 扑发现到后来的物理网络拓扑发现,都涌现出了大批优秀算 法。例如,Yuri Breitbart等人提出的NetInventory 拓扑发现系 统[3],解决了大型异构网络物理拓扑发现问题,但该系统主要 基于 SNMP(Simple Network Management Protocol)协议,对 于不支持该协议的设备不能进行很好的发现;Alessio Botta等 人提出的路由器级拓扑发现算法[4],解决了网络层拓扑发现, 但并没有对链路层设备的拓扑结构进行讨论;Breitbart等人提 出的基于完整交换机地址转发表的物理网络拓扑发现算法[3], 解决了链路层拓扑发现问题,但该算法要求每个交换机上的 地址转发信息是完整无缺的;郑海等人提出的基于非完整地 址转发表的改进算法[5],解决了地址转发表不完整问题;孙延 涛等人提出的基于谓词推理技术的物理网络拓扑发现算法[6], 使用连接推理技术将拓扑发现问题转换为数学推理问题,提 高了拓扑发现的效率,但该算法没有对网络设备信息获取方 法进行讨论;Choonho Son等人提出的基于OSPF(Open Short- est Path First)路由协议的物理拓扑发现算法[7],使用路由协议 信息进行拓扑发现,改进了拓扑发现的效率,但只能适用于支 持路由协议的主干网络。通过对比发现,这些拓扑发现算法 主要专注于如何提升算法的性能和拓扑发现的完整性,而弱 化了算法实施的基础——拓扑信息获取问题,并且大多只单 独考虑网络层或物理网络拓扑发现问题,因此不能很好地实 施于现实的综合网络中。 针对网络层与链路层综合拓扑发现问题,本文提出了一 种基于广度优先遍历的探索式拓扑发现算法,该算法根据图 的广度优先遍历思想,从根节点开始,依次探索发现各层子 网,并针对每层子网发现其中的交换机等链路层网络设备。 在工程实现方面,本文根据TCP/IP网络模型特点,将整个拓扑 发现过程分为多个层次,每层由独立的模块构成,增强了算法 可实现性和可移植性。 1 拓扑发现算法原理与设计 1.1 相关概念 为了更好地说明算法,下面将本文中用到的一些概念集 中介绍如下。 IP 路由表:在支持网络管理要求的路由器中,都可通过 SNMP获取其IP路由表[8],该表中与拓扑发现有关的信息主要 有下一跳IP地址NextHop和路由类型type,其中type主要用来 判断下一跳IP地址是否与本子网直接相连,当不直接相连时, NextHop就代表下一网关地址。 IP地址表:在每个路由器上都维护着一张表,记录着与该 网络层与链路层综合拓扑发现算法及其实现 孙克辉 1,陈艳山 1,程 巍 1,张志强 2 SUN Kehui1, CHEN Yanshan1, CHENG Wei1, ZHANG Zhiqiang2 1.中南大学 物理科学与技术学院,长沙 410083 2.深圳市中联通电子有限公司,广东 深圳 518067 1.School of Physics Science and Technology, Central South University, Changsha 410083, China 2.ZhongLianTong Electronics Corporation, Ltd, Shenzhen, Guangdong 518067, China SUN Kehui, CHEN Yanshan, CHENG Wei, et al. Topology discovery algorithm and its realization for network layer and data link layer. Computer Engineering and Applications,2012,48(4):107-110. Abstract:In order to achieve effective management and monitoring for computer networks, a topology discovery algorithm based on BFS(Breadth-First Search)is proposed. In the algorithm, the process of a topology discovery is divided into several layers. In the bot- tom layer, all of the devices in subnets can be found, and in the higher layers, it can get the topology between these devices using some graph theories easily. Compared with current discovery algorithms, this method can get the topology both in network layer and data link layer. It has been successfully applied to the ZLT’s network management platform, and the tests show that it has good stability and portability. Key words:network management; topology discovery; breadth-first search; Simple Network Management Protocol(SNMP); Internet Control Message Protocol(ICMP) 摘 要:为了实现对网络的有效管理与监控,采用层次化模型,提出了一种基于广度优先遍历的探索式拓扑发现算法。该算法将 底层的设备发现与顶层的拓扑关系分析分离开来,在顶层利用图的相关理论,实现了网络层拓扑与物理网络拓扑的完整发现。 与现有方法相比,该算法解决了网络层拓扑与数据链路层拓扑发现相互独立的问题,增强了其实用性。算法在中联通综合网络 管理平台中的成功应用表明了其有效性。 关键词:网络管理;拓扑发现;广度优先遍历;简单网络管理协议(SNMP);互联网控制消息协议(ICMP) DOI:10.3778/j.issn.1002-8331.2012.04.032 文章编号:1002-8331(2012)04-0107-04 文献标识码:A 中图分类号:TP393 基金项目:中南大学研究生创新基金项目资助(No.2009ssxt138)。 作者简介:孙克辉(1968—),博士,教授,主要研究方向为混沌理论及其应用、网络监控;陈艳山(1985—),男,硕士研究生;程巍(1985—),男,硕士 研究生;张志强(1969—),男,总工程师。E-mail:chenyanshanchan@126.com 收稿日期:2010-09-07;修回日期:2010-11-15;CNKI出版:2011-03-04;http://www.cnki.net/kcms/detail/11.2127.TP.20110304.0926.002.html Computer Engineering and Applications计算机工程与应用 107 Computer Engineering and Applications计算机工程与应用2012,48(4) 路由器有关的 IP 地址信息。在多层子网中,为了保证子网间 能够相互通信,路由器一般都维护着两个或者以上的 IP 地 址。这些 IP 地址分别属于不同的子网,其中一个是本子网网 关地址,其他分别对应于与本子网直接相连的子网内某一 IP 地址。 地址转发表:在每个交换机上都维护着一张地址转发表, 该表中与拓扑发现有关的信息,主要有port和MAC地址,其中 port称为转发端口,MAC称为转发地址,通过port和MAC,就 能够获取物理网络拓扑关系。该表可通过 SNMP 获取,IETF 于2000年推出的Physical topology MIB中定义了该表信息[9]。 路由器连接类型:如果两个路由器不经过交换机,直接通 过一条物理线路连接在一起,称这两个路由器为直接相连。 如果两个路由器间有一个或多个交换机,称这两个路由器为 间接相连,间接相连又分为单管理域内交换机间接相连和多 管理域内交换机间接相连两种情况。 1.2 广度优先遍历算法 计算机网络拓扑结构图是由路由器、交换机、Hub和主机 等网络设备相互连接组成的图结构,因此可以使用图的广度 优先遍历思想对其拓扑结构进行逐层探索发现。由于主机一 般不起连接作用,属于叶子节点;Hub属于通明设备,因此在图 中可将这两者忽略,这样,图中的元素主要是路由器和交换机。 图的广度优先遍历一般借助队列来实现,对于从始发节 点root开始,借助队列Q来实现广度优先遍历的算法如下: enqueue(Q,root)//将始发节点入队 do node=dequeue(Q)//队尾节点出队并处理该节点 process(node) for each child of node //将当前节点的子节点依次入队 enqueue(Q,child) while Q is not empty 如图1所示,无向图的节点对应路由器R1、R2、R3 和交换机 S1、S2、S3,无向图的边对应这些设备间的连接关系。 1.3 路由器间连接关系 在只考虑网络层拓扑关系时,路由器在逻辑上的连接关 系比较简单,而在实际的综合拓扑发现中,必须将交换机加入 拓扑结构中,这时,路由器间(子网间)的连接关系就会更加复 杂。为了说明路由器间的连接关系,本文参考图的相关理论[10], 给出以下定义和定理。 定义 1 以路由器 R 作为网关的子网 G=(D,E),其中 D= S+R,S是子网内的交换机集合,E是由交换机端口引出的边,E 可以分为两类 Ei 和 Eo,定义 Ei 为子网 G 的内边,Ei ={< Ax By > |ABÎS},即Ei 是连接本子网内交换机的边的集合,其中 A、B是子网内交换机,x、y分别为A、B的一个端口;定义Eo为子 网G的外边,Eo ={< AxBy > |AÎS且BÏD},即Eo是连接本子 网内交换机与外网设备的边的集合。 定义2 将子网G=(D,E),D=S+R的外边Eo中每条边的外 接 端 点 的 集 合 定 义 为 Vo,Vo = {v|v是Eo中任意一条边的端点, 且v ÏD}。 定理1 两个直接相连子网G1=(D1,E1)与G2=(D2,E2)的网 关路由器R1、R2 是直接相连的充分非必要条件是V1o  D2 = ϕ , 且V2o  D1 = ϕ 。 证明 (1)充分性: 令子网G1=(D1,E1)与G2=(D2,E2)都包含于网络G=(D,E)。 由于 V1o  D2 = ϕ ,则说明G1 中没有交换机连接到G2 中的 交换机或路由器,同理V2o  D1 = ϕ ,则说明G2中没有交换机连 接到G1中的交换机或路由器。 又由于G1和G2同属于一个网络G,且直接相连,那么它们 只能够通过路由器直接相连这种方式实现互连了。 (2)非必要性说明: 在一些比较重要的网络中,两个子网之间可能存在多条 链路,以保证在一条链路失效的情况下,仍然可以通过备用链 路进行通信。 例如在图 2 中,V1o  D2 = ϕ ,且 V2o  D1 = ϕ ,因此路由器 R1、R2是直接相连的。 定理2 两个直接相连子网G1=(D1,E1)与G2=(D2,E2)的网 关 路 由 器 R1、R2 是间接相连的充分条件是 V1o  D2 ¹ ϕ 或 V2o  D1 ¹ ϕ 。 证明 条件 V1o  D2 ¹ ϕ 或 V2o  D1 ¹ ϕ 可以分为以下 3 种 情况: (1)V1o  D2 ¹ ϕ 且V2o  D1 = ϕ ,此条件说明子网G1中有交 换机与G2中交换机或路由器相连;同时,G2中没有交换机与G1 中网络设备相连,因此,可以推出子网G1的网关路由器R1通过 该子网下的交换机与子网G2的网关路由器R2间接相连。 (2)V2o  D1 ¹ ϕ 且V1o  D2 = ϕ ,同(1),此条件可以推出子 网G2的网关路由器R2通过该子网下的交换机与子网G1的网关 路由器R1间接相连。 (3)V1o  D2 ¹ ϕ 且V2o  D1 ¹ ϕ ,此条件说明子网G1中有交 换机与G2 中交换机或路由器相连,同时G2 中有交换机与G1 中 交换机或路由器相连,因此可以推出 G1、G2 的网关路由器 R1、 R2 通过各自子网内的交换机间接相连,或者在子网间有多重 链路的情况下还会同时出现(1)或(2)两种间接连接。 例如,在图 2 中,V1o  D3 ={R3} 且 V3o  D1 = ϕ ,属于上述 (1)情况,因此,R1、R3是间接相连的;V2o  D3 ={S5}且V3o  D2 = {S4},属于上述(3)情况,因此 R2、R3 是通过各自子网内的交换 机间接相连的。 1.4 综合网络拓扑发现算法 1.4.1 算法的数据结构 拓扑发现的过程,主要是探索子网间路由器、交换机的连 R1 S1 R2 R3 S2 S3 节点入队和出队顺序: R1入队 R1出队并记录R1下子网结构 R2和R3入队 R2出队并记录R2下子网结构 R3出队并记录R3下子网结构 图1 网络拓扑图结构及其广度优先遍历顺序 S1 S2 S3 S4 S5 R2R1 R3 G3 G1 G2 网络G 图2 子网间连接关系图 108 2012,48(4) 接关系,以及子网内交换机的连接,为了表示这些连接,一种 很好的方法就是使用链表结构,而链表中的节点元素可用以 下几种结构体表示。 (1)交换机 struct Switch{ … int routerIp;//本交换机从属于子网的网关IP struct Switch*pConnectedS;//与本交换机相连的交换机列表 struct Router*pConnectedR;//与本交换机相连的路由器列表 … }; (2)路由器 struct Router{ … struct Router* pPreRouter;//本路由器从*preRouter探索到 struct Router* pNextRouter;//本路由器连接的路由器列表 … }; (3)子网 struct Subnet{ struct Router router;//网关路由器 struct Switch*pSwitch;//子网内的交换机列表 }; 由这些节点及节点中的指针就可表示出需要探索的网络 拓扑结构,例如,图 2 经拓扑发现后可表示成如图 3 所示的链 表图。 1.4.2 拓扑发现算法设计 本文提出的拓扑发现算法以图的广度优先遍历作为基本 思想,从运行该算法的子网开始,运用前面提出的定义、定理 以及数据结构,对整个网络 G 进行遍历,并记录遍历过程,即 为网络的拓扑结构。算法描述如下。 从运行该算法的子网G1开始,进行以下操作步骤。 (1)获取子网网关R1。 (2)查找子网内设备,构造设备集合D1。 (3)根据子网内交换机的地址转发表分析设备间连接关 系,并找出该子网的外连接点集合V1o。 (4)根据网关路由器 R1 的 IP 路由表或IP 地址表找出与本 子网直接相连的子网网关。 (5)依次进入与本子网直接相连的子网Gx,并重复步骤(1) 到步骤(3)找出Gx的外连接点集合Vxo和设备集合Dx。 (6)由 V1o 与 Vxo 以及 D1、Dx,运用定理 1 和定理 2 分析出两 子网网关路由器R1与Rx的连接关系。 (7)依次以与子网 G1 直接相连的子网 Gx 为根节点实施该 算法直到相连子网为空或者都已被访问过为止。 2 拓扑发现算法实现 由于拓扑发现算法在实现过程中会遇到各种不同的网络 协议和设备,而各种设备信息获取方式又有所不同,为了使顶 层的算法统一对待这些设备,本文在算法实现上采用层次化 结构模型,整个模型结构如图4所示。 其中,设备IP获取层是整个算法得以实施的基础,该层的 主要任务是发现子网内设备 IP,以及与该子网直接相连的子 网网关IP。对于子网内设备IP的发现有多种方法,例如,可使 用ICMP(Internet Control Message Protocol)协议的回显应答 消息;或者在子网内使用 ARP(Address Resolution Protocol) 协议。本文采用 ICMP 协议的回显应答消息,并进行了改进。 由于ICMP回显应答消息并不包含目的主机的IP地址,这样在 测试IP地址是否存在时,只能顺序进行。为了解决这个问题, 本文在回显应答消息后添加一个 IP 字段,如图 5 所示。发送 IP 地址测试消息时,加入要测试的 IP 地址,当该 IP 地址有效 时,回复消息中IP字段并不会改变,读取该字段就可知该IP对 应的设备存在。这样,就可以同时对整个子网发送ICMP回显 应答消息,然后在另一线程超时等待回复消息,并读取所有回 复消息中的 IP 字段,即为该子网内的所有设备。而对于与该 子网直接相连的子网网关 IP,可以使用 SNMP 协议读取网关 路由器的 IP 路由表或 IP 地址表来获取,对于不支持 SNMP 协 议的路由器可以使用添加代理的方式来实现。 MAC地址完善层:该层的主要任务是完善子网内设备的 MAC地址,在使用地址转发表分析交换机间以及交换机与路 由器间的连接关系时,主要使用 MAC 地址。获取 MAC 地址 的方式也有多种,这里主要采用ARP协议和SNMP协议。 设备类型辨别层:在拓扑发现过程中,辨别设备是否为路 由器、交换机或者主机也是必须的。对于设备类型的辨别方 法本文主要是通过 MIB-II 中的 sysServices 信息来进行判断, sysServices信息表示设备所提供的协议层服务。例如,两层交 换机提供物理层和数据链路层服务;而路由器还提供网络层 服务,但其sysServices值与三层交换机相同,为了区分这两种 设备还需判断设备是否提供 Physical topology MIB 信息,若 提供则为三层交换机,否则为路由器。 拓扑连接分析层:该层在获取了网络设备信息的基础上 对网络实施上一章讨论的拓扑发现算法,从而得出整个网络 的拓扑结构。 拓扑结构展现层:该层将获取的拓扑结构数据以图形的 形式展现出来。 router: pSwitch: G1 R1 S1 S2 G2 R2 S3 S4 G3 R3 S5 S5 S4 R3 n p p 图3 网络图2对应的链接表图 拓扑连接分析层 设备类型辨别层 MAC地址完善层 设备IP获取层 设备信息存储区拓扑结构展现层 图4 拓扑发现算法实现模型图 类型(8) 代码(0) 校验和 序列号标识符 IP地址 图5 改进的ICMP回显应答消息格式图 孙克辉,陈艳山,程 巍,等:网络层与链路层综合拓扑发现算法及其实现 109 Computer Engineering and Applications计算机工程与应用2012,48(4) 3 应用与测试 本文在 VC++2005 平台下,采用面向对象设计方法,对提 出的拓扑发现算法进行了分模块实现,并已成功应用到深圳 中联通电子有限公司的综合网络管理平台中,该网络管理平 台以拓扑发现为基础,对整个网络中的设备进行实时监控,以 保证网络设备的正常运行。通过在多种网络环境和设备中测 试表明,该拓扑发现算法能够快速完整地发现计算机网络拓 扑结构,并且具有很好的稳定性和可移植性。图6是该网络管 理平台对某公司网络进行拓扑发现的结果(PC终端未显示), 该公司网络包含三层子网 ,其 中 子 网 192.168.1.* 与 子 网 192.168.2.*的网关路由器通过子网内交换机间接相连,而子网 192.168.2.*与子网192.168.3.*的网关路由器直接相连。 4 结语 为了发现交换式以太网网络层和物理网络拓扑结构,提 出了一种基于广度优先遍历的探索式拓扑发现算法,该算法 将整个拓扑发现过程分为几个相互独立的模块层,在底层完 成设备发现的基础上,实施顶层的拓扑结构分析算法,综合出 这些设备的连接关系。经过实验测试表明,本文算法解决了 以往网络层与物理网络拓扑发现相分离的情况,增强了其实 用性。另外,使用层次化模型,减小了层间耦合,增强了顶层 算法的适用性和可移植性。 参考文献: [1] Nazir F.Constella:a complete IP network topology discovery so- lution[C]//Lecture Notes in Computer Science 4773,2007:425-436. [2] Gobjuka H.Finding Ethernet-type network topology is not easy, TR-KSU-CS-2007-03[R].Kent State University,2007. [3] Breitbart Y.Topology discovery in heterogeneous IP networks: the NetInventory system[J].IEEE/ACM Transactions on Network- ing,2004,12(3):401-414. [4] Botta A.Discovering topologies at router level:part II[C]// GLOBECOM,2007:2696-2701. [5] 郑海,张国清.物理网络拓扑发现算法的研究[J].计算机研究与发 展,2002,39(3):264-268. [6] 孙延涛,吴志美,石志强.基于地址转发表的交换式以太网拓扑发 现[J].软件学报,2006,17(12):2565-2576. [7] Choonho S.Efficient physical topology discovery for large OSPF networks[C]//NOMS,2008:325-330. [8] Mccloghrie K,Rose M.Internet RFC-1213 Management informa- tion base for network management of TCP/IP-based internets: MIB-II[S].1991. [9] Bierman A,Jones K.Internet RFC-2922 Physical topology MIB[S].2000. [10] 徐俊明.组合网络理论[M].北京:科学出版社,2007. 图6 某公司网络拓扑发现图 [2] Xia Tianming,Song Ruiqi.A method of P2P traffic identifica- tion on Internet based on the deep flow inspection[C]//Interna- tional Conference on Communication Software and Networks, 2009. [3] Bob S.The trouble with“deep packet inspection”[EB/OL].[2008]. http://redtape.msnbc.com/2008/10/deep-down-most.html. [4] 王珊,陈松,周明天.网络流量分析系统的设计与实现[J].计算机工 程与应用,2009,45(10):86-88. [5] Stevens W R.TCP/IP illustrated volume 1:the protocols[M].[S.l.]: Addison Wesley,2000:170-173. [6] Stevens W R.TCP/IP illustrated volume 3:TCP for transactions, HTTP,NNTP,and the UNIX domain protocols[M].[S.l.]:Addi- son Wesley,2000:280-284. [7] Draper N R,Smith H.Applied regression analysis[M].3rd ed.[S.l.]: Wiley-Interscience,1998. [8] Doebelin E O.Measurement systems:application and design[M]. [S.l.]:MgGraw-Hill Companies,2007:86-88. [9] 蔡光兴.线性代数[M].北京:科学出版社,2003:66-68. [10] Backhaus K,Erichson B,Plinke W.Multivariate statistical analy- sis[M].Shanghai:Shanghai People’s Publishing House,2008:48-49. [11] 李子奈.计量经济学[M].北京:高等教育出版社,2003:142-144. [12] 潘鸿.应用统计学[M].北京:人民邮电出版社,2011:132-135. [13] 张翼,张勇,汪为农.防火墙过滤规则的建模和全面优化[J].计算 机工程与应用,2006,42(6):146-150. (上接106页) [6] Katti S,Hu W J,Medard M.The importance of being opportu- nistic:practical network coding for wireless environments[C]// Proceedings of the Annual Allerton Conference on Communica- tion Control,and Computing,Monticello,2005. [7] Katti S,Rahul H,Hu Wenjun,et al.XORs in the air:practical wireless network coding[J].IEEE/ACM Transactions on Network- ing,2008,16(3). [8] 樊凯,李令雄,龙冬阳.无线mesh网中网络编码感知的按需无线路 由协议的研究[J].通信学报,2009,30(1):128-134. [9] Fan Kai,Wei Xi,Long Dong-yang.A load-balanced route selec- tion for network coding in wireless mesh networks[C]//IEEE ICC,2009. [10] Alimi R,Li L,Ramjee R,et al.iPack:in-network packet mixing for high throughput wireless mesh networks[C]//Proc of IEEE INFOCOM’08,Anchorage,AK,2008. [11] Katti S,Katabi D,Balakrishnan H,et al.Symbol-level network coding for wireless mesh networks[C]//SIGCOMM’08,Seattle, Washington,USA,2008. [12] Keshavarz-Haddad A,Riedi R.Bounds on the benefit of net- work coding:throughput and energy saving in wireless net- works[C]//IEEE INFOCOM,2008. (上接103页) 110
还剩3页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf