以太网络的拓扑发现

1、项目1:以太网络的拓扑发现目的：加深对以太网逻辑拓扑、物理拓扑、交换机、路由器工作原理和SNMP协议的理解任务：本项目分为两个阶段，第一阶段为网络逻辑拓扑的发现，第二阶段为网络物理拓扑的发 现。第一阶段：设计并实现一个简单的以太网的逻辑拓扑发现算法。逻辑拓扑是发现三层设备（包括路 由器和具有VLAN划分功能的交换机）与子网（包括VLAN）、三层设备与三层设备之 间的连接关系。这主要是网络层级别的。实现方法是根据SNMP协议读取访问路由器的一些M旧信息（M旧-II），根据这些信息来 计算网络的拓扑结构。第二阶段：设计并实现一个简单的以太网的物理拓扑发现算法。发现子网内交换机之间的连接关系。 以太

2、网交换机内存在一个地址转发表，利用SNMP协议获得该表，设计一个算法，对其 中的地址一端口对应关系进行分析，可以找出以太网的物理拓扑。接着可以计算网络中 交换机与主机的连接情况，从而得到整个网络的拓扑情况。拓扑图中应该最终包含主机（假设主机是支持SNMP的）。以下介绍一种物理拓扑的发现方案，分为设备发现和拓扑计算两部分：发现子网内可以发现的所有交换机当交换机上配置了 IP地址并且开放了 SNMP协议，那么该交换机就是可以被发现的。 用集合SwitchSet表示发现的交换机集合。其中每个元素都为序偶交换机IP地址，交 换机MAC地址。理论上采用的方法是逐个对子网内的网络地址发送GetReques

3、t请求，请求的对象是 sysServices，对应的 oid = 1.3.6.1.2.1.1.7.0，收到U GetResponse 响应报文后，按 sysServices值来判断响应报文是否来自交换机设备。因为sysServices对象的取值按7 位编码来解释。每一位对应于TCP/IP或OSI结构的一层，其中最低位对应于第一层。 如果系统在某一特定层提供服务，则设置相应的位。该数值可表示为：sysServices = 习2项。在TCP/IP协议族中，层赋值如表1所示：服务值表层功能1物理层（例如转发）2数据链路层（例如网桥）3网络（例如IP路由器）4终端到终端（例如IP主机）7应用层（例如邮

4、件中继）如果是交换机，它工作在第二层，则sysServices值中必包含2（2-1） = 2,但没有路由功 能，必不包含2（3-1） = 4，因此，根据sysServices的值可以判断出此设备是否是交换机， 如是交换机则将其（IP地址，MAC地址）信息加入SwitchSet集合。拓扑计算拓扑计算就是计算交换机之间的连接关系并用集合Relation表示，其中每个元素的形式 为FatherNode、DownPort、SonNode、UpPor、type，FatherNode表示上级节点， DownPort为下行端口号，SonNode表示下级节点，UpPort为上行端口号，type是连接 类型。在

5、这里上级节点和下级节点可能是交换机节点，也可能是未知环节。连接类型表TypeFatherNodeDownPortSonNodeUpPort1g SwitchSet下行端口g SwitchSet上行端口2是未知环节g SwitchSet上行端口3g SwitchSet下行端口是未知环节4g SwitchSet（非上下行）端口其他网络设备设备的网络接口5是未知环节其他网络设备设备的网络接口在计算交换机之间的连接关系中，只涉及type = 1、2、3的情况，计算网络中的计算机 与交换机的连接情况时，涉及type = 4、5的情况。在介绍算法之前，先介绍一些概念：标志节点：运行算法的计算机。上行端口：

6、指端口对应的地址转发表中出现标志节点MAC地址的端口。下行端口 ：指端口对应的地址转发表中没有出现标志节点MAC地址，但是出现其它交换机 的MAC地址的端口。叶子节点：叶子节点是指满足如下条件之一的节点：没有下行端口的交换机节点，或者是对 于含有下行端口的交换机，其所有下行端口都被计算过了。注意，当下行端口和 一个未知环节连接时，需要计算n次。这里n是该下行端口所学习到的交换机MAC 地址的数量.父节点：当某个交换机的下行端口地址转发表中只含有当前节点的MAC地址的时候，那么 这个交换机就是这个当前节点的父节点。祖父节点：如果某节点存在父节点，那么父节点的父节点就是该节点的祖父节点。在不存在

7、父节点的情况下（指连接到未知环节），如果存在这样的交换机，它的某个下行端 口的地址转发表中包含该结点的MAC地址，那么这些交换机称为该节点的祖先节 点。如果交换机A、B都含有C的MAC地址，并且A含有B的MAC地址，那么B就 是离C近的，在多个祖先节点中，离该节点最近的是它的祖父节点。下面是物理网络拓扑发现算法流程：1）进行设备发现，其结果为SwitchSet。2）对SwitchSet中的所有交换机进行ping操作，使得所有交换机地址转发表中都包含标 志节点的MAC地址。3）依次读取每台交换机的地址转发表。使用GetNextRequest报文。4）从各交换机的地址转发表中构造每台交换机的上行端

8、口与下行端口集合，同时计算各个 下行端口的地址转发表。5）初始化Relation为空集合；NodeSet也为空集合，这是表示节点的集合，节点可能是 交换机或者中间未知节点，当拓扑计算后满足SwitchSet是NodeSet的子集。6）计算出所有叶子节点，其结果记做叶子节点集合LeafSet。7）从LeafSet中取走一个节点CurrentLeaf，此时叶子节点集合LeafSet为LeafSet-CurrentLeaf，如果此时LeafSet和SwitchSet都为空，那么算法结束，进行 算法验证。8）计算CurrentLeaf的父节点ParentNode，如果存在ParentNode节点，那么

9、NodeSet 改成 NodeSet u CurrentLeaf, ParentNode, Relation 改成 Relation u , SwitchSet 改成 SwitchSet-NodeSet,转到（11）。9）计算CurrentLeaf节点的祖父节点GrandpaNode。如果存在祖父GrandpaNode,那么 说明在CurrentLeaf和GrandpaNode之间有未知环节，用GrandpaNode-x表示，做 如下操作：NodeSet 改成 NodeSet u CurrentLeaf, GrandpaNode, GrandpaNode-x, Relation 改成 Rela

10、tion u , ，之后转到（11）。10）如果不存在祖父GrandpaNode,说明标志节点MarkNode和CurrentLeaf之间存在一 个未知环节，这样的未知环节仅有一个，用SpecialOnlyNode表示，做如下操作： NodeSet 改成 NodeSetu CurrentLeaf, SpecialOnlyNodeRelation 改成 Relationu。11）如果LeafSet为空，那么转到6）；否则转到7）。要求：使用C或者C+,在Microsoft Windows平台上实现，允许调用有关SNMP协议的类库。 网络拓扑结构输出格式要求为可视化的拓扑图方式。关于网络拓扑的发现，已经有很多 成型的算法，可以参考一些文章的算法，（上述介绍的也只是一种算法而已，同学们不 必停留在这个算法上）并改进。不提倡直接引用。提交：有关源代码，并且可以编译执行。论文中包括有关原理的概述和详细的程序设计说明。应该有主要的数据结构和算法 描述，程序流程和程序代码文件的说明。参考：Bruce. Lowekamp, David R. OHallaron, Thomas R. Gross, “Topology Discovery for Large Ethernet Networks, August 2001.R. Siamwalla, R. Sharma