摘要：传统的拓扑发现算法是基于SNMP协议的，能够很好的发现网络主拓扑，但是对于子网却往往出现发现不完整的情况。针对这一个问题，本文提出了基于ICMP(Internet Control Messages Protocol,网间控制报文协议)协议的方法，来得到完整的子网结构。
关键词：简单网络管理协议(SNMP )；网络拓扑自动发现算法
中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)15-30661-02
Study on Arithmetic on Finding Network"s Topological Structure
YE Shun-fu
(Zhangzhou City Employment Center,Zhangzhou 363000,China)
Abstract:The original arithmetic is based on SNMP,which is fine in finding network"s main topological structure, but not well in getting a full one of a subnet.So,a way based on ICMP is putted forward to solve this problem for achieving the full one.
Key words:SNMP(Simple Network Management System);Arithmetic on auto-finding network"s topological structure
随着计算机网络的普及，人们对计算机网络的依赖性大大加强了。在现有的技术条件下，人们希望有一个更加稳定可靠的网络环境。计算机网络管理系统就是应这样的需求而产生的。它对网络上的各种设备进行管理，通过监视和控制这些设备，及时地向管理人员报告网络状态，并且简化网络故障的处理，减少故障造成的损失，提高网络的服务质量和效率。在我国，人们开始认识到网络管理的重要性。
国外在网络管理这一领域起步较早，取得了一些成果。在学术界，IEEE通信学会下属的网络营运与管理专业委员会(CNOM , Committee of Network Operation and Management)，从1988年起每两年举办一次网络营运与管理专题讨论会。国际信息联合会(1FIP)也从1989年开始每两年举办一届综合网络管理专题讨论会。以及OSI网络管理论坛(OSI/NM FORUM )，专门讨论网络管理的有关问题[1]。近年来，也有一些厂商和组织开始推出自己的网络管理解决方案[2]。比较有影响的有:网络管理论坛的OMNIPoint和开放软件基金会(OSF)的DME(Distributed Management Environment)[3]。本文详细介绍系统网络拓扑自动发现算法的实现。
1 拓扑发现算法的相关理论
1.1路由选择算法
网络拓扑的发现，实际上就是根据网络上节点连接情况，构造出来一个反应这种连接关系的图。网络节点可以是网关，也可以是子网:网关节点是与子网和其它网关节点相邻的节点;子网节点可被认为只与网关节点相邻，至少与它的缺省网关相邻。
各子网通过各目的网关与其他子网通信，这些子网可以是一个局域网，也可以是某个局域网的一部分，它们都连接到网关的一个端口上，网关的端口可以连接子网，也可以同其他路由器相连。当子网的某一机器发送数据时，数据包首先到达子网的缺省网关，缺省网关检测数据包中的目的地址，根据其路由确定该日的地址是否在与自己相连的子网中，如果是，则把数据包直接发往目的地，否则转发给路由表中规定的下一个网关。这样，下一个网关再进行类似处理，依次类推，数据包将最终到达目的地。
1.2图论中的遍历算法
遍历的定义是:对于无向图，以图中某一点为出发点，沿着边依次访问图的其余节点，如果图是连通的，则从图的任一点出发按一定的顺序沿着某些边可以访问图中的所有节点，而且每个节点仅被访问一次，这一过程称为图的遍历。
在网络上，一个节点可以和很多的节点连接，所以当进行网络拓扑结构发现的时候，有可能会访问己经被发现过的节点。因此，在遍历的时候，必须对每一个节点设置一个标志。当节点未被访问过时，相应的标志为0，否则，就置为1。
2 拓扑发现算法的设计与实现
2.1主拓扑的发现
主拓扑指的是反映出关键设备包括路由器，它们的接口和子网的连接关系，即路由器－路由器、路由器－子网、接口的关系。这些信息需要对网络进行搜索而获得:一般只需要对连接设备进行遍历就可以得到主拓扑结构。当前的网管软件都是通过对网络设备的MIB库进行访问，所以这种方法又被称为基于SNMP的拓扑发现。
2.2子网发现
经过上述的遍历过程，可以得到网络拓拓扑图的整体构成，知道了网络主干通道情况。但是子网内部的具体设备以及连接状态尚不可知。这就需要依靠子网发现来做进一步的工作。子网发现完成的任务是确定子网内各网络设备的状态、类型以及网络接口。
3 改进的拓扑算法
前面基于SNMP的拓扑算法在一定程度上是非常有效的，拓扑的速度也非常快。但它存在一个缺陷。那就是，在一个特定的域中，所有的子网的信息都依赖于设备具有SNMP的特性，如果系统不支持SNMP，则这种方法就无能为力了。还有对网络管理的不重视，或者考虑到安全方面的原因，人们往往把网络设备的SNMP功能关闭，这样就难于取得设备的MIB值，就出现了拓扑的不完整性，严重影响了网络管理系统的功能。针对这一的问题，下面讨论本文对上述算法的改进－基于ICMP协议的拓扑发现。
3.1 ICMP报文的格式
ICMP被认为是IP层的一个组成部分。它传递差错报文以及其他需要注意的信息。网际协议CIP)没有出错报告或出错校正机制，它依靠网际控制报文协议〔ICMP)模块来报告数据处理过程，井提供管理和状态信息。ICMP报文在传送时被封装在IP数据报中，使用IP协议发送，但ICMP不看作是高层协议的内容。ICMP报文的格式如图1。
图1 ICMP报文的格式
类型区:定义报文类型;
代码区:描述错误类型或状态信息;
校验和区:计算ICMP报文16位校验和；
利用ICMP进行网络拓扑图的发现，需要利用其中的响应请求与应答报文。其报文格式如图2所示，回应请求/应答被用于测试信宿机的可到达性或连通性。请求者(某机器)向特定信宿机发送一个回应请求，其中包含一个任选的数据区;信宿机发回响应的回应应答，其中包含一个请求中的任选数据区的拷贝。图2所示的“标识符”和“序号”用于匹配请求与应答(同一机器可以同时向若干信宿机发出请求)。
图2 回应请求(类型8)/应答(类型0)报文格式
回应请求与应答均以IP数据报的形式在网间传输，假如成功地收到一个应答(应答中的数据拷贝与请求中的任选数据完全一致)，不但说明信宿机可以到达，而且说明数据报传输系统的相应部分工作正常，至少信源机和信宿机的ICMP软件和IP软件工作正常，请求与应答经过中间网关也在正常工作。在许多TCP/IP实现中，用户命令Ping便是利用ICMP回应请求/应答报文测试信宿机的可到达性的。
3.2 PING的实现
PING的主要操作是发送报文，并简单地等待回答。PING之所以如此命名，是因为它是一个简单的回显协议，使用ICMP响应请求与响应应答报文。PING主要由系统程序员用于诊断和调试。一般的，PING的功能有:
LOOP BACK PING用于验证TCP/IP软件的操作。
PIN G地址确定能否寻址物理网络设备。
PING远程IP地址验证能否寻址网络。
PING远程主机名验证主机上某个服务器的操作。
实现PING的过程主要是:首先向目的机器发送一个响应请求的ICMP报文，然后等待目的机器的应答，直到超时。如收到应答报文，贝以报告目的机器运行正常，程序退出。
3.3 traceroute的实现
traceroute的实现与IP数据报文的报头有关。IP头的结构如下:
struct ip{
char ip_ verlen; //IP version&header length
char ip_ tos; //type of service
short ip_len; //total packet length(in octets)
short ip_ id;//datagram id
short ip_fragoff //fragment offset
char ip_t1;//time to live, in gateway hops
char ip_proto//IP protocol
short ip_chksum//header checksum
Ipaddr ip_src//IP address of source
Ipaddr ip_dst//IP address of destination
char ip_data//variable length data
}
在IP头的结构中，存在一个ip_ttl域，即生存时间(time to_ live,TTL ). TTL参数用于测量数据报在网际存在多长时间。网络中的每个路由器都检查该域，如果TTL值为0，路由器就抛弃该数据报。路由器还必须对它处理的每个数据报的该域进行减I操作。在实际执行中，TTL域是一个反映跳段的值。所以，当数据报穿过一个IP节点(网关)时，TTL域中的值就减1。
traceroute的功能就是利用IP头中的TTL域。开始时信源设置IP头的TTL值为0，发送报文给信宿，第一个网关收到此报文后，发现TTL值为0，它丢弃此报文，并发送一个类型为超时的ICMP报文给信源。信源接收到此报文后对它进行解析，这样就得到了路由中的第一个网关地址。然后信源发送TTL值为1的报文给信宿，第一个网关把它的TTL值减为0后转发给第二个网关，第二个网关发现报文TTL值为0，丢弃此报文并向信源发送超时ICMP报文。这样就得到了路由中和第二个网关地址。如此循环下去，直到报文正确到达信宿，这样就得到了通往信宿的路由。
3.4网络拓扑的发现算法
具体实现的步骤：
(1)于给定的IP区间，利用PING依次检测每个IP地址，将检测到的IP地址记录到IP地址表中。
(2)对第一步中查到的每个IP地址进行traceroute操作，记录到这些IP地址的路由。并把每条路由中的网关地址也加到IP表中。
(3)对IP地址表中的每个IP地址，通过发送掩码请求报文与接收掩码应答报文，找到这些IP地址的子网掩码。
(4)根据子网掩码，确定对应每个IP地址的子网地址，并确定各个子网的网络类型。把查到的各个子网加入地址表中。
(5)试图得到与IP地址表中每个IP地址对应的域名(Domain Name)，如具有相同域名，则说明同一个网络设备具有多个IP地址，即具有多个网络接口。
(6)根据第二步中的路由与第四步中得到的子网，产生连接情况表。
4 结论
本文主要论述了网管系统中一个重要的功能网络拓扑的自动发现。阐述了相关的理论知识，并具体讨论了基于SNMP和基于ICMP的拓扑发现，最后对算法所适用范围加以说明。虽然这种方法能够较好的发现网络拓扑，但是它需要占用大量的带宽资源。
参考文献：
[1]Breibart Y,et al.Topology Discovery in Heterogeneous IP Networks[C].Tel Avivl Israel Proceeding of INFOCOM 2000.
[2]Clarke,Freenet A Distributed Anonymous Information Storage and Retrieval System [C].Workshop on Design Issues in Anonym ity and Unobservability, 2000 25-31.
[3]ICE Reference Manual[EB/OL].http ///download/Ice-21.2 pdf.2005.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
