基于IPv6的本地链路网内拓扑发现的设计及实现

朱宗敏

福建星网锐捷网络有限公司 福建福州 350002

1 现状

1994 年11 月7 日，IESG 正式将IPv6 作为下一代互联网的标准协议进行研究。

IPv6 协议考虑了用户现在和将来应用的需求，对IPv4 采取了吸收和改进的策略。相比于IPv4 协议，IPv6 不是在原有的协议上进行小修小补，而是加入了许多全新的机制。虽然协议本身建立的目的仍然是使应用和物理链路实现之间互相独立，但新的协议必然会给网络管理工作提出新的要求。

2 基于IPv4 的的拓扑发现机制

根据范围，拓扑发现软件可划分为两大类：工作在自治域上的拓扑发现软件，依靠BGP 实现；工作在自治域（局域网）之内的拓扑发现软件，主要依靠SNMP 和ICMP 实现。下面只讨论第二类。

2.1 网络层拓扑发现工具

该层的拓扑发现工具一般使用两种算法。

1 基于ICMP 和UDP 的算法

先获得尽可能多的子网内部信息。向地址空间内每个可能的IP 地址发送ICMP[7]请求报文，然后使用Traceroute 函数找到连接在设备上的所有路由器，最后发送ICMP 前缀请求报文得到它们的网络前缀地址。对于那些具有多个子网前缀的节点，向它们一个未使用的端口发送UDP 报文，返回的ICMP 出错消息可能会返回节点另一子网内的接口地址。根据收集到的这些信息来划分子网，路由器在节点和不同的网络链路间建立联系。

2 基于ICMP 和SNMP 的算法

先从IP 列表中挑出一个处于活动状态的IP，探明它是可达的后，通过ICMP 掩码请求报文获得子网号，然后使用Traceroute 函数或SNMP 请求找到该节点的默认路由器。通过这一路由器，获得可达的子网和路由器列表。最后在每个子网内通过穷举发送ICMP 回声请求来获得本子网内所有的可达节点。

2.2 链路层拓扑发现工具

可以分为两大模块：使用SNMP 和ICMP 的部分和利用图论的数学特性的部分。链路层的拓扑发现有两大任务：区分主机、交换机；发现节点链路层地址和链路之间的连接关系。具体来说：首先，通过类似网络层拓扑发现的方法，以SNMP 提供的类和对象为工具，得到链路内的所有可达节点的网络层和链路层信息；然后通过类似于图论的数学方法，发现那些可能存在的物理连接关系。

3 拓扑发现软件的设计实现

随着IPv6 网络部署规模的逐步扩大，尽管IPv4 拓扑发现的某些理论和方法仍然适用，但也不可避免地会出现一些新的问题。

3.1 IPv6 邻居发现过程

IPv6 链路上节点的邻居发现过程共分两步[1]∶

第一步：节点立刻向链路发送路由器请求报文（RS），路由器以路由器宣告报文（RA 回应，其中包含路由器的地址和网络前缀信息。

第二步：节点为获得目标通信节点的链路层地址信息，向链路内发送邻居请求（NS）报文，该报文中包含源主机的IP地址和MAC 地址信息，链路上的所有节点都能接到这个报文。目标节点再以邻居宣告（NA）报文回应，其中包含了目标节点的MAC 地址与IP 地址的对应信息。这样通信双方就能通信了，从而替代了ARP 的功能。

本地链路拓扑发现设计方案

本地链路拓扑发现的主要要实现的功能是，发现链路内所有节点的本地链路地址，链路层地址，区分节点类型（主机还是路由器），链路前缀，并以适当的方式展示出来。参考法国Renate 实验室所提出的层次化拓扑发现的方案[2]，决定采用本地代理的方式实现拓扑发现的功能。以这种方式，以本地代理收集本地链路的拓扑信息，而通过对分布式的本地代理所收集的链路信息的聚合，最终可以组合成完整的网络拓扑结构。

本实现方案通过ICMP 方式来收集本地链路的拓扑信息。本地代理模块将主动向本地链路主机节点和本地链路路由节点主动发送组播的ICMPv6 邻居请求报文(NS)，由于各个节点会对接收到的NS 回复邻居宣告报文（NA），由此可以通过对NA中所包含的信息来获取各个节点的连接信息。

3.2 实现过程中的主要困难和解决方案

由于IPv6 的地址机制与IPv4 发生了重大的变化，因此原来适用于IPv4 的算法在IPv6 环境下不再适用，以下将描述本项目的实现过程中遇到的困难，并针对各个难点进行分析，同时给出本实现所采取的解决方案。

1）海量“ICMP 回声请求”

造成这个问题的主要原因是IPv6 的地址空间发生了巨大的改变。每个IPv6 地址中，子网前缀为64 位，余下的64 位是表示子网内的唯一接口，因此，与IPv4 及其有限的本地链路主机数目相比，要在子网内穷举主机，就需要发送2^64 个ICMP 回声请求，不论以何种方式实现，这种高昂的代价在都是不可接受的。

本实现利用IPv6 的组播机制，解决了海量“ICMP 回声请求”的问题。IPv6 下定义了新的多播地址，格式为FF＜接口〉＜组标识〉：对于全局范围，接口号为E；对于本地站点范围，接口号为5；对于本地链路，接口号为2。

协议预留了一些组播地址：如FF02∶∶1 用来表示本地链路上所有IPv6 节点；FF02∶2 预留来标识本地链路上的所有路由器；FF05∶∶2 用来表示本地站点内的所有路由器。本实现利用IPv6 的预留组播地址，向目标地址FF02∶∶1 发送NS 报文，避免了穷举链路内主机，只需要周期性的一条NS 报文，取代2^64 个NS 报文。

2）无法获取全局IPv6 地址

本地代理通过向本地链路主机节点和本地链路路由节点发送目的地为FF02∶∶1 的NS 报文，并根据各节的NA 报文的回应来获取各个节点的连接信息。但是对NS 进行单播回应的NA 中通常只包含回应接口的链路层地址相关的本地链路地址。因此仅仅依靠NS 请求，无法获得目标设备的全局IPv6 地址。

本实现利用监听NA 报文的方式来获取各个节点的全局IPv6 地址。通常情况下，各个IPv6 节点同外界通讯并不使用本地链路地址，而是使用全局IPv6 地址。

因此，在实际的通信过程中，必然会发生通信双方进行全局IPv6 地址的MAC 解析。这个过程同样使用了NS 和NA 的报文机制。所不同的是，所监听到的邻居宣告报文的目标地址至少是链路内一台主机的全局IPv6 地址。因此籍由这种方式，通过一段时间的累积，可以收集本地链路的各个节点的的全局IPv6 地址。但是这种方式依赖于节点的通信状况，因此不一定能够反映当前链路内的信息情况。

3）大量IPv6 节点存在时的性能

由于IPv6 的地址结构比较IPv4 大大扩充，因此与IPv4不同的是，同一个网段内不再仅有有限的设备，可能存在海量的运行着IPv6 的设备。

因此，对于本地链路上节点的维护方法不能像IPv4 的本地链路算法那样，采用2 叉树，甚至简单的使用链表的方式来维护，这样在IPv6 节点增多的情况下，势必造成整体监控软件性能的下降。

为了让节点的插入，检索更加高效，本实现采用了AVL 平衡二叉树的方式来维护本地链路的IPv6 节点。使得IPv6 节点的操作接近于O(logN)的时间复杂度。

3.3 本地链路拓扑发现软件结构

本地链路拓扑发现软件框架图如下所示：

图2 拓扑发现软件子模块结构图

以下对模块一的各个主要部分的功能进行说明：

1）NS 主动探测部分组播发送目标为ff02∶∶1 以及ff02∶∶2 的ICMPv6 回声请求(NS)报文，查到链路内所有节点

2）NA 回应监听部分接收到各个IPv6 主机针对NS 主动探测发出的NS 报文，并以单播的方式回应的NA 报文，这里NA的回应目标地址主要为本机的本地链路地址，并对主机节点，路由节点进行区分；

3)主动探测模块将这个部分收集到的本地链路信息登记到节点数据库，并刷新节点定时器；

4）NA 全局监听截获所有的NA 通讯，这里的NA 的回应目标地址主要是各个不同主机的全局IPv6 地址；

5）在节点数据库中查找捕获到的NA 所对应的节点，并将NA 中所携带的IPv6 全局地址添加到节点数据库中的对应节点上；

6）处于超时状态的节点信息不再保存于节点数据库中；

7）作为分布式本地代理的一部分，向其上一级代理通告本地链路信息。

核心算法流程图，如图4.3 所示：

图3 拓扑软件后台程序流程图

4 结论

在本次具体实践的过程中，解决了IPv6 下拓扑发现的一些问题，但是还有部分问题的解决方法依然存在可以改善的地方。比如项目实现中通过对NA 报文的监听来获取全局IPv6 的做法，要得到完整的拓扑需要花费一定的等待时间。

另外也存在遗漏掉部分实际尚未参与网络通讯的网段配置的可能。同时，作为完整的IPv6 网络拓扑管理，仅仅实现在本地链路层的拓扑发现是不够的。

总之，与IPv4 相比，IPv6 所支持的庞大地址空间和新的路由策略使得拓扑发现的理论和算法与IPv4 的做法发生了很大的变化。

本文通过对原理的分析，以本地链路作为整个IPv6 网络的最小单位，由本地代理来管理其拓扑的想法已在本项目中基本实现。

[1]T.Narten, E.Nordmark.Neighbor Discovery for IP Version 6 (IPv6),RFC2461[Z]，1998.

[2]O.Festor.A Hierarchical Topology Discovery Service for IPv6 Networks[M].France：LORIA-INRIA Lorraine 2001.

[3]A.Conta, S.Deering.Internet Control Message Protocol (ICMPv6) for the Internet Protocol Version 6 (IPv6) Specification, RFC2463[Z] 1998.