端口基于IP网络的自动拓扑搜索算法

第20卷 第4期 五邑大学学报自然科学版 Vol 20 No 42007年 1月 JOURNAL OF WUYI UNIVERSITY (Natural Science Edition) Jan 2007

文章编号 1006-7302 2006 04-0006-07

基于IP网络的自动拓扑搜索算法

龚 兵

五邑大学 信息学院广东 江门 529020

摘要 目前局域网规模不断扩大、结构日趋复杂 网络速度及网络管理成为网络系统正常运行的主要指标及关键其中网络拓扑自动发现是网管系统的基本要求和重要功能.要求网络拓扑发现速度快并可反映使用权级而决定服务内容、服务器、路由器和交换机的布局状况提供可视化管理界面如系统配置、节点状态和流量监控、异常告警等对网络系统正常运行、防范网络攻击具有重要意义.本文提出一种基于移动Agent的网络拓扑发现改进算法广度优先搜索算法  降低了拓扑生成的复杂度从而提高了系统速度.

关键词 IP网络拓扑结构 自动搜索算法

中图分类号 TP392.02 文献标识码 A

An Automatic Topological Search Algorithm Based on IP Network

GONG Bing

(Info. School, Wuyi Univ. , Jiangmen 529020, China)

Abstract: Against the background of the ever increasing size of local networks andthe increasing complexity of their structure, the speed and management of networkshave become the main indexes of and key to the normal operation of network systems.Particularly, network automatic topological search is a basic requirement andimportant function of a network management system. Fast network topological searchspeed and the reflection of power levels, the determination of service content, thedistribution of servers, routers and switch boards, and the provision of visiblemanagement interface featuring system allocation, the status of nodes, themonitoring of flow and warning of abnormalities are of great significance to thenormal operation of network systems and to theprotection against network assaults.This paper advances an improved algorithm based on mobile Agent network topologicalsearch which canreduce the complexity of topological generationand therefore raisesthe speed of network systems.

Key words: IP network; topological structure; automatic search algorithm

1 引言

近10年来 随着计算机网络规模的不断扩大互联网络的迅猛发展路由技术在网络技术中已逐渐成为关键部分 路由器也随之成为最重要的网络设备.用户的需求推动着路由技术的发展和路由器的普及 人们已经不满足于仅在本地网络上共享信息 而希望最大限度地利用全球各个

收稿日期 2006-03-01

作者简介龚兵 1946-   男湖北仙桃人高级工程师主要从事数据采集及信息处理、计算机系统维护

及计算机数据安全教学与研究工作.

第20卷 第4期 龚兵基于IP网络的自动拓扑搜索算法 7

地区、各种类型的网络资源.而在目前的情况下任何一个有一定规模的计算机网络如企业网、校园网、智能大厦等  无论采用的是快速以太网技术、 FDDI技术还是ATM技术都离不开路由器 否则就无法正常运作和管理.

路由器有多个端口用于连接多个IP子网.每个端口的IP地址的网络号要求与所连接的IP子网的网络号相同.不同的端口为不同的网络号对应不同的IP子网这样才能使各子网中的主机通过自己子网的IP地址把要求出去的IP分组送到路由器上.生成树协议也是随着网络的不断发展而不断更新换代的.本文介绍了自动拓扑搜索生成树协议的新算法.生成树协议是一种二层管理协议 它通过有选择性地阻塞网络冗余链路来达到消除网络二层环路的目的 同时具备链路的备份功能.由于自动搜索生成树协议本身比较小所以并不像路由协议那样广为人知.但是它却掌管着端口的转发权限特别是在和别的协议一起运行的时候生成树就有可能断了其他协议的报文通路造成种种奇怪的现象.生成树协议和其他协议一样是随着网络的不断发展而不断更新换代的. “生成树协议”是一个广义的概念并不是特指IEEE 802.1D中定义的STP协议而是包括STP以及各种在STP基础上经过改进了的生成树协议.在生成树协议发展过程中老的缺陷不断被克服新的特性不断被开发出来.

2 系统模型

为了方便搜索算法的描述本文给出如下的定义.

定义1 自动拓扑搜索算法的目标域称为管理域AD 其模型如图 1所示.

图1 系统模型示意图

它可表示为一个无向图G其中顶点R1…4 ,S1…9分别对应实际网络中的路由器和交换机连接顶点的边(S1 R1)、 (R1 R2)、 (S6 S7)…是设备间物理连接的抽象表示.根据网络连通性原则显然G是一个连通图.

定义2 交换域 SD是将管理域中交换机与路由器之间的连接去掉后仅由交换机构成的连通分量.如图中的S D 1 、 S D 2、 S D 3它们的设备集合分别为S1,S 2,S 3, S4,S5 ,S 6,S 7, S8,S9.假设交换域中的所有交换机都利用生成树协议Spanning Tree Protocol来消除回路这将导致在

8 五邑大学学报自然科学版 2007年必要情况下阻塞交换机的端口使连接失效 在自动拓扑搜索中 系统将忽略这些连接.

定义3设备级连接 指当两台或以上管理设备路由器或交换机 的存活端口同处一个物理网段时则称它们之间存在着设备级连接.包括设备之间的直接电缆互连、通过HUB将多台设备连接起来、多台设备利用同轴电缆连接在同一物理网段上等情况.在本文中 如不特殊说明设备之间的相连均指设备级连接.

定义4 端口级连接指两台管理设备的存活端口之间存在着物理电缆的连接.设备级连接包括了端口级连接的情况 根据实际网络结构可知 这两种连接形式是并存的.

另外 为了和RF C中设备的描述一致 在本文中对交换机与网桥的意思不做区别 可互用路由器与网关也是一样.

3 搜索算法

假设在拓扑搜索过程中 网络结构保持不变 算法得到的结果将包括发现的设备路由器和交换机集合、路由器之间的连接关系、 交换机之间的连接关系、路由器与交换机之间的连接关系.

3. 1 路由器集合的产生及路由器之间连接关系的搜索算法

寻找管理域中的所有路由器 其基本思想类似于无向图的广度优先搜索算法 是从管理域内任一可访问的路由器出发在路由表中找到与其相邻的路由器及子网 并将新发现的路由器加入搜索队列把它们之间的连接关系加入路由器连接集合[1 ] .算法中涉及的MIB变量由表1所示.

表1

MIB变量名 OI D 解释ipRouteDest 1 3 6 1 2 1 421 1 1 该路由的目的地址

IpRouteIfIndex 1 3 6 1 2 1 421 1 2 该路由的本地接口索引ipRouteMetric1 1 3 6 1 2 1 421 1 3 该路由的主要跳步数ipRouteMetric2 1 3 6 1 2 1 421 1 4 该路由的次要跳步数2ipRouteMetric3 1 3 6 1 2 1 421 1 5 该路由的次要跳步数3ipRouteMetric4 1 3 6 1 2 1 421 1 6 该路由的次要跳步数4ipRouteNextHop 1 3 6 1 2 1 421 1 7 该路由表项的下一跳地址ipRouteType 1 3 6 1 2 1 421 1 8 路由的类型ipRouteMask 1 3 6 1 2 1 421 1 1 1 目的子网的网络掩码

在算法实现时利用面向对象的方法来描述路由器 并将下一跳网关集合、 路由器直接连接的子网用指针链表保存在路由器对象中其结构分别为typedef struct{int ConnectPortNum; // 连接子网的端口序号

IpAddress ItemIpAddress; // 子网 IP地址

IpAddress ItemNetworkMask; // 子网掩码

}NetworkStruct; // 子网的结构typedef struct{int ConnectPortNum; // 连接下一跳网关的端口的序号

第20卷 第4期 龚兵基于IP网络的自动拓扑搜索算法 9

IpAddress NextHopAddress; // 下一跳网关的地址

}NextHopStruct; // 下一跳的结构

算法描述如下void FindRouteMap(IpAddress OriAddress){

//初始化任一已知路由器 OriAddress为其可访问地址

CRouter OriRouter= new CRouter(OriAddress);

//将OriRouter加入路由器集合

RouterSet={OriRouter };

RouterVis ited=;

While(RouterSet){

从RouterSet中任取一路由器R

RouterSet=RouterSet–{R }

If( {R}RouterVis ited )

Continue;

RouterVis ited=RouterVis ited∪ {R}

For(遍历R的路由表){从路由表中取一表

项RouteEntry

//如果该路由是Direct表示IpRouteDest所指的是与该路由器直接相连的

//子网或该路由器的端口地址if(RouteEntry.ipRouteType==3 ){if(RouteEntry.ipRouteMask==255.255.255.255&&

RouteEntry.ipRouteNextHop == 0.0.0.0 )Continue;

}e ls e{

创建一个NetworkSturct结构将其加入该路由器的直接相连子网队列

}

//如果该路由是Indirect则IpRouteNextHop表示与本路由器相连的路由器if(RouteEntry.ipRouteType== 4){

//判断是否到达搜索边界if(RouteEntry.ipRouteNextHop ==

BoderAddress){Continue;

}e ls e{

创建一个NextHopStruct结构将其加入该路由器的下一跳网关队列

RouterSet=RouterSet∪ { ipRouterNextHop所表示的路由器}

}

}

}

}

}

通过以上算法可以找出管理域中所有的路由器及其之间的连接关系. 这些连接关系还未落实

10 五邑大学学报自然科学版 2007年到设备的各端口之上 由于路由器的连接使用主要是为了划分子网、 隔离广播域 其端口级的连接是少数的 因此上面给出的路由器端口连接搜索算法实际上还是设备级连接的情况.端口搜索算法主要分析NextHopStruct结构[2] 该结构记录了当前路由器与下一跳网关R2的连接端口 P1 由于在大多数情况下一个IP地址对应网关的一个端口 因此可从R2的端口地址确定其连接端口 P2.当路由器R2端口配置了 IP地址时会出现一个IP地址对应多个端口的情况 这时可通过查询R2对应的NextHop Struct结构来确定P2.

3. 2 交换机集合的产生及交换机之间连接关系的搜索算法

各交换域内的交换机集合及连接关系汇总成了整个管理域的交换机信息 故算法的分析目标是单个的交换域.基本思想是依据交换域中自动产生的生成树结构 从根网桥开始采用树的层次遍历算法找出交换机之间的连接关系.

产生交换机集合的算法包括两步  1 初始化所有交换机对象生成交换机集合SwitchSet.这可通过网络管理员手工输入或分析管理域中路由器的地址转发表ipAddrTable (. 1.3.6.1.2. 1.4.20)得到. 对从路由器各端口地址转发表获得的每一个地址 尝试获取 MIB变量 sysServices .1.3.6.1.2.1.1.7及ipForwarding .1.3.6.1.2.1.4.1   当sysServices  3&&ipForwarding=1时可判断该设备为 一交换机 将它加入 SwitchSet.  2 对于 SwitchSet 中 MIB变量dot 1dStpDes ignatedRoot  .1.3.6.1.2.1. 17.2.5值相同的交换机归为一类 由生成树协议可知它们是处于同一交换域的[3] .

生成树协议借助交换机之间传递信息的网桥协议数据包BPDU在交换域中确定了根网桥、根端口、指定网桥、指定端口 并通过阻塞部分端口达到消除交换域中回路的目的. 由协议可知对每一棵生成树只有一个根网桥而指定网桥路径 因此根据它们之间的关系可以确定出交换机间的连接关系.算法中涉及的MIB变量由表2所示

表2

MIB变量名 OID 解释dot1dBaseBridgeAddress 1 3 6 1 2 1 17 1 1 用来唯一标识网桥的MAC地址dot1dBaseNumPorts 1 3 6 1 2 1 17 1 2 网桥端口数目dot1dStpPriority 1 3 6 1 2 1 17 2 2 网桥优先级dot1dStpDesignatedRoot 1 3 6 1 2 1 17 2 5 根网桥标识符dot1dStpRootPort 1 3 6 1 2 1 17 2 7 设备的根端口dot1dStpPortPriority 1 3 6 1 2 1 17 2 15 1 2 端口优先级

端口的指定网桥dot1dTpFdbAddress 1 3 6 1 2 1 17 4 3 1 1 桥端口学到的MAC地址dot1dTpFdbPort 1 3 6 1 2 1 17 4 3 1 2 学习到该MAC地址对应的端口

本搜索算法的理论基础

定理1 在一个交换域内 交换机S 1 、 S2相连的充要条件是S1的根端口的指定网桥是S2 反之亦然.

证明 充分性.如果S 1与S2是相连的那么  1 当S 1、 S2中有一个是根网桥时 不失一般性令S1为根网桥显然S1成为所有与根网桥相连的网段的指定网桥.而与这些网段相连的交换

第20卷 第4期 龚兵基于IP网络的自动拓扑搜索算法 11

机的端口由于到根网桥的费用最小便成为本交换机的根端口所以S2的根端口的指定网桥是S 1 .2当S 1 、 S2中没有根网桥时 由定义2可知 在S 1 、 S2互相连接的网段中必存在一指定网桥假定为S1  由于到根网桥费用最低的端口是本交换机的根端口 而指定网桥是本网段到根网桥费用最低的网桥 所以 S2的根端口的指定网桥是S 1 得证.

必要性.不失一般性设S2的根端口的指定网桥是S 1 . 由 802 1 d规范[4]可知设备的根端口与其指定网桥必在同一物理网段且该网段负责本网桥到指定网桥的流量 根据定义3可推出

S 1、 S2之间存在着设备级连接得证.

在本算法中树的结构用邻接表来表示具体过程描述如下void FindSwitchMap( SwitchDomainSet ){

// 给出一交换域内交换机的集合

// 初始化交换机链表将根网桥加入

SwitchQueue={RootSwitch};

Proc es sQueue=;

Sp an T re e=;

For(遍历SwitchDomainSet中交换

机){从SwitchDomainSet中取一交换

机Sif(S.RootPort.DesignatedBridge==

RootSwitch){ SwitchQueue=SwitchQueue∪

{S};

SwitchDomainSet= SwitchDomainSet– { S};

ProcessQueue=ProcessQueue∪ {S};

}

}

Tree=Tree∪ {SwitchQueue}; For(遍

历Process Queue){

SwitchQueue=;

从ProcessQueue中取一交换机PS;

ProcessQueue =Process Queue– { PS };

SwitchQueue= {PS};

For(遍历SwitchDomainSet中交换机){

从SwitchDomainSet中取一交换机Sif(S.RootPort.DesignatedBridge==

PS){SwitchQueue=SwitchQueue∪ {PS};

SwitchDomainSet= SwitchDomainSet– { PS};

ProcessQueue=ProcessQueue∪ {PS };

}

}

Tree=Tree ∪{SwitchQueue};

}

}

12 五邑大学学报自然科学版 2007年

以上给出了寻找交换机间连接关系的算法 在寻找交换机端口级连接算法给出以下的定义及表示方法.交换机i的第j个端口表示为Sij端口Sij学到的地址集合表示为A ij.令Us为交换域中处于同一子网 S的交换机及与该交换域相连的也属于S的路由器的MAC地址集合.

由于互联网的多样性和复杂性,使得网络模拟环境的建立面临很大的困难.通过以上的网络拓扑图的随机生成方法和基于域模型的随机生成方法的研究分析,提出了一种基于不同抽象层次的网络拓扑建模方法,并描述了这种方法的基本原理及其特点.

4 小结

在计算机网络研究中,路由器集合的产生用路由器之间连接的搜索算法基本上应用深度搜索与广度搜索算法.深度搜索与广度搜索的控制结构和产生系统很相似 唯一的区别在于对扩展节点选取上. 由于其保留了所有的前继节点 所以在产生后继节点时可以去掉一部分重复的节点从而提高了搜索效率.这两种算法每次都扩展一个节点的所有子节点 而不同的是深度搜索下一次扩展的是本次扩展出来的子节点中的一个.而本文提出的广度基础上有所改进 即在每一次都扩展一个节点的所有子节点 而搜索扩展的则是本次扩展节点的兄弟节点具体实现上为了提高效率,所以采用了不同的数据结构提高了搜索效率及时间.

在计算机网络研究中 网络模拟方法是一种快速而又经济的研究手段.IP 网络拓扑的自动搜索与结构是实现IP网络管理的基础论文简单介绍搜索算法如何利用网桥产生搜索生成树结构从根网桥开始 采用树的层次层遍历算法 降低了拓扑生成复杂度 找出交换连接关系 提高了拓扑发现的速度.

IP网络拓扑结构的自动搜索与构造是实现一个IP 网络管理系统的基础,它的目的是为了自动发现IP网络中的所有设备和整个网络的拓扑结构.然后详细描述了如何利用这两种协议来实现自动搜索算法,并提出了在算法中需要注意的问题

参考文献

[1]石硕计算机网络实验技术[M]北京: 电子工业出版社, 2002

[2]微软公司 Transmission Control Protocol/Internet Protocol[Z]

[3]微软公司中国计算机所M icrosoft Agent技术谈[N] 中国计算机报, 1997

[4] IEEE 802 1d 国际电子工程师协会标准[S]