Linux系统上AODV协议实现的分析.pdf

下载

- 1 - Linux系统上 AODV协议实现的分析 齐朝霞 北京邮电大学信息与通信工程学院，北京 (100876) 摘 要： 无线Ad hoc 网络是一种不需要基础设施的自组织和自管理网络,网络中所有 的节点同时具有终端和路由器的功能。因此无线自组网是的一个重要研究领域就是路由技 术。为了适应各种不同的应用场合，研究人员设计了许多的路由协议。其中,AODV(Ad hoc on-Demand Distance Vector)路由协议是IETF (Internet Engineering Task Force)的MANET工作 组(Mobi1e Ad hoc Networks Working Group)推荐的无线自组网路由协议之一。本文论述如何 在Linux操作系统上实现AODV路由协议。首先,本文介绍了AODV路由协议的工作原理,它简 单、实用而且性能优越。然后介绍了Linux系统的网络框架,在其分析上提出AODV路由实现 方案。最后,对实现方案中的难点进行逐条分析。实现方案分成三个部分：一部分是与操作 系统的功能接口，第二部分是记录每条路由最后使用时间的内核模块代码，第三部分是 AODV逻辑算法的实现。 关键词： AODV 无线自组织网络 路由 Linux 中图分类号：TN91 1. 引 言 无线 Ad hoc 网络是一种不需要基础设施的自组织和自管理网络,网络中所有的节点同 时具有终端和路由器的功能。由于无线自组网的拓扑结构动态变化，如何在移动中保持通信 成为一个重要的研究方向。现阶段已经提出许多的路由算法，各个路由算法有各自的优缺点， 适合于不同的场合[1]。利用无线自组网的技术，可以扩大无线局域网的使用范围。同时，可 以利用基于无线局域网的设备，很方便的验证无线自组网的一些技术。 AODV(Ad hoc on-Demand Distance Vector)路由协议是 IETF 的 MANET(Mobile Ad hoc Networks)工作组推荐的无线自组网路由协议之一。本文在 或 协议 的基础上，利用无线局域网设备，对在 Linux 操作系统上实现 AODV 路由算法进行了分析。 2. AODV 路由协议介绍 AODV 路由协议是一种按需路由协议。当网络拓扑结构发生变化时，它能快速收敛， 具有断路的自我修复功能。计算量小，存储资源消耗小，对网络带宽占用小。通过使用目的 节点序列号，协议实现了无环路由，并且避免了无穷计数的问题，并且很容易编程实现。为 了避免单向链路引起的错误操作，协议引入了一个黑名单，把和自己是单向链路的邻居节点 放入黑名单中。 AODV 使用了分布式的、基于路由表的路由方式，所以建立路由表后，在路由中的每 个节点都要执行路由维持、管理路由表的任务。本文的重点是在 Linux 实现上的内核方面， 下面主要介绍 AODV 所需要 IP 底层相关的内容。 节点的路由中除了存储源和目的节点的序列号外，还存储了其他有用的信息，这些信息 成为有关路由项的软状态[2]。与反向路由相关的是路由请求定时器，这些定时器的目的是清 除一定时间内没有使用的反向路由项。定时器的设置依赖于自组网的规模大小，与路由表相 联系的另外一个重要的参数是路由缓存时间，即在超过这个时间之后，对应的路由表就变为 - 2 - 无效。所以每一个路由的最后使用时间都要保存,这是 AODV 路由表维护的重要依据,而这个 使用时间需要 Linux 内核来提供。 3. Linux 操作系统路由转发功能 Linux 网络系统基本可以分为硬件层/数据链路层、IP 层、INET Socket 层、BSD Socket 层和应用层五个部分[3]。下图说明了 Linux 基于 TCP/IP 协议的网络系统体系结构。 图 1 基于 TCP/IP 协议的 Linux 网络系统体系结构 其中，INET Socket 层比 IP 协议层次高，实现对 IP 分组排序、控制网络系统效率等功能。 从 INET Socket 层到 IP 层，主要是路由过程，发送时根据发送的目标地址确定需要使用的 网络设备接口和下一跳的主机地址;接收数据的时候需要在 IP 据分组是要发送给上一层协议 还是需要做一个 IP 转发，将数据传递给下一台机器 IP 层到硬件层，也就是到网络接口设备 驱动程序，由驱动程序负责将数据发送出去。 在 Linux 的路由功能子系统中，主要保存了三种与路由相关的数据。第一种是在物理上 和本机相连接的主机地址信息表，第二种是保存了在网络访问中判断一个网络地址应该走什 么路由的数据表，第三种是保存最新使用过的路由信息的缓存信息数据表。分组转发功能模 块在内核中基于一个内核路由表来工作，每次发送一个数据分组，都要向内核路由表查询， 取得对应的下一跳邻居节点的地址和对应的网络接口。 Linux 系统自带的分组寻路模块是在内核中的。这样将分组转发功能和分组寻路功能分 开以后，可以在分组转发功能模块保持不变的情况下，通过修改分组寻路功能模块，而用其 - 3 - 它路由协议来替代现有的路由协议。 4. Linux 上 AODV 协议实现方案 实现框架 在本文对 AODV 路由协议实现的方案中，将尽可能的利用 Linux 操作系统现有路由机 制。实现方案不改变 Linux 操作系统的分组转发功能模块，而是利用它的分组转发功能模块 的实现机制，巧妙的用我们自己的分组寻路功能模块来替换 Linux 操作系统现有的分组寻路 功能模块。 方案的基本实现思路是：用 NETFILTER 上的钩子函数时刻监测需要发送的数据报，一 旦没有路由，就用 Netlink 来通知用户态发起 AODV 路由查询[4]。考虑到程序的移植性和扩 展的方便性。拟在用户空间实现 AODV 的寻路功能。 AODV 路由协议实现的方案，按逻辑功能上可以分成三个主要部分：第一部分是接口 部分，第二部分是 AODV 路由算法部分，第三部分是内核模块部分。其中，前两部分是在 用户空间实现的，第三部分是内核空间实现的。具体结构如图 2 所示。 图 2 Linux 上 AODV 协议实现框架 第一部分：接口部分 接口部分的主要功能是利用 Linux 系统提供的应用程序接口，为实现 AODV 路由协议 提供所需要的各种信息和服务。我们借助用户分组数据的发送过程，来分析这部分的功能。 在实现方案里，我们使用 NETFILTER 功能框架，实现数据包过滤和处理。其框架如图 3 所 示： - 4 - 图 3 NETFILTER 功能框架 当用户分组到达的时候，在 NF_IP_PRE_ROUTING 函数处，肯定是原先就存在路由， 只需要顺着内核路由表的内容接着发送就好，这时候只可能出现原先存在的路由断开，以至 于找不到路由，缓存数据分组，这时候就发起 local-repair 的请求。在 NF_IP_LOCAL_OUT 函数处，是检测每一个由本机发出去的数据包，这时候如果没有路由，缓存数据分组，然后 就由原节点即本机发起路由查找程序。 第二部分:AODV 路由算法 从第一部分提取出用户分组数据分组的目的节点址，就可以有足够的信息来进行AODV 路由查找了。这部分涉及到 RREQ 的广播，RREP, RERR 帧的处理等等。这部分的功能就是 实现 AODV 路由协议，基本上不涉及和 Linux 的交互性问题。 AODV 各种数据帧的接收和发送可以利用普通的 UDP 套接口实现就可以，根据 AODV 协议，套接口使用的是 UDP 协议在 654 端口进行收发。每当收发一个帧，都需要对相应的 数据结构进行更新。在各种数据结构中，最重要的一个时间队列。各种 AODV 事件的管理 用了一个时间队列，每个事件发生的时候，都需要更新这个队列[5]。这个队列记录了这个事 件的超时时间。插入时间队列的时候，根据要求发生时间在前的事件插在队列的前面。然后 根据这个事件队列，建立一个计时器，用事件队列最前头的这个事件的时间来更新这个计时 器。这样，每当到了预期的超时时间，计时器将触发中断，这样，调用相应的程序进行处理。 第三部分：时间的提取 无线自组网的拓扑结构因为是动态变化的，所以它的路由协议都有一个时间要求，每一 条路径都有一个有效时间，如果超过这个时间路径没有更新，就需要将这条路由标记为不可 用。AODV 路由协议也一样。它要求记录每条路径的最后使用时间，如果空闲时间超过一 定的时间，就需要将这条路由标记为不可用。 为了实现这个功能，程序利用了 Linux 内核 以上版本的挂钩（hook）功能。程序就 是利用这个特征，通过在 POST ROUTEHOOK 上注册一个函数，每次检查出去的数据分组， 根据地址信息记下每条路由的最后使用时间。 记录下的每条路径的最后使用时间，调用 Netlink 套接口发送时间数据到用户态,创建时 间列表保存路由的最后使用时间。当需要的时候可以随时查询。 这个部分是相对独立的一部分，在内核空间利用加载模块技术实现. AODV 协议实现的难点及其解决方法 发起路由查找过程 传统的有线网络能够很好的适合前面阐述的 Linux 系统的路由实现方案。实际上，主动 - 5 - 的无线自组网路由协议也能跟 Linux 系统自身的路由方案很好的适应。然而，按需的无线自 组网路由协议却无法用上述框架实现。因为在传统的分组转发功能模块中，当数据分组在找 不到相匹配的路由表项的时候，操作系统将简单的把这个数据分组抛弃。这个特点给我们实 现 AODV 协议带来了困难，因为 AODV 是按需路由协议，在找不到路由表项的时候，不能 将数据分组抛弃，而应该发起路由查找过程，寻找到目的节点的路由。 在实现中，我们充分利用 Linux 系统现有的功能，不修改其分组转发功能模块，而仅仅 改变它的分组寻路功能模块，用 AODV 路由协议的逻辑算法替换现有的分组寻路功能模块。 路由协议的分组寻路功能模块既可以在内核中实现，也可以在用户空间实现，在用户空间寻 找到正确的路由以后，再将路由传递到内核中，供分组转发功能模块使用。在内核中实现和 在用户空间实现，各有自己的优缺点。在内核中实现的优点在于能够以更快的速度工作，因 为它不需要在内核层和用户层之间交换数据。同时，在内核中实现可以用更方便的方法操作 数据分组的 IP 头部域，使得可以根据协议的内容方便的修改 IP 头部信息。然而，在内核实 现的缺点也很明显，它增加了内核态的资源占用，降低了整个系统核心的性能。同时，在内 核中实现调试相对困难，开发周期要长,且在移植性兼容性上不如在用户层开发的程序。综 合考虑后，我们采用在用户空间实现分组寻路模块。 在实现中，在 NF_IP_LOCAL_OUT[5]挂上钩子函数,检测每一个出去的数据包,如果没有 路由,就缓存这个数据分组，提取出目的节点址，用 Netlink 发起 AODV 路由查找过程。如 果 AODV 成功查找出到目的节点的路由，则将这条路由插入到内核路由表中，然后将缓存 的数据分组发送。如果没有找出路径，就将缓存的数据分组释放，通知源节点出错。 记录每条路由的最后使用时间 无线自组网的按需路由协议通常自己保存有一个路由表，这个路由表的每一项都有一个 定时器与之相关联。当定时器到期以后，意味着路由表项过期了，则应该将这个路由表项删 除或者标记为过期不可用。AODV 路由协议需要记录每条路径的最后使用时间，而问题是， 系统自身并没有提供每条路径的最后使用时间给用户。这个信息必须自己提取。 为了提取每条路由的最后使用时间，POST ROUTE_HOOK 上注册一个函数。每次检查 出去的数据分组，根据地址信息就可以记下每条路由的最后使用时间，从而提供 AODV 路 由协议所需要的每条路由最后使用时间。 对路由表和网络接口的操作 在实现方案中，我们将不修改 Linux 自身的分组路由转发功能。因此我们需要做的是: 根据分组寻路模块计算的路由结果，修改 Linux 内核中的路由表。在实现方案中，我们将有 两个路由表，一个是内核的 Linux 自带的我们称为内核路由表:另外一个是自己在用户层自 己建立的，我们称为 AODV 路由表。 内核路由表，是 Linux 自身的分组路由转发模块工作的基础，我们没有对其表项结构进 行任何修改，以保持通用性和可移植性。AODV 路由表结构是根据 AODV 协议构造的，记 录了每条路由的目的序列号、到目的节点的跳数等信息，分组路由寻路模块需要利用这些信 息，来进行正确的路由查找。程序对用户层的路由表定义了各种操作函数，因为分组路由寻 路模块和 AODV 路由表都是在用户空间实现的，它们之间可以很方便的进行信息交互。对 内核路由表则不一样，它们之间涉及内核和用户空间之间的交互，不能直接交换信息。程序 利用 Linux 的 Netlink 来操作 Linux 内核路由表。 - 6 - 信息的发送和接收 在 AODV 路由协议的实现过程中，需要进行多种数据分组的发送和接收。一种是从应 用程序来的用户分组的接收、缓存和转发;一种是 AODV 协议帧的单播发送和接收:还有一种 是 AODV 协议帧的广播发送和接收。 从应用程序发出的用户分组，在经过路由表的时候，按缺省的路由发送到了 TUN 设备， 这是一个 TUN 文件套接口，程序可以使用各种流操作函数，从这个虚拟的设备中接收数据。 接收的用 户分组数据存储在一个散列(hash)表中。在实现中，利用用户分组数据的目的节点 作为关键字，将正在进行路由查找过程的用户分组数据缓存在一个散列表中。 当路由查找过程完成的时候，需要根据路由查找的结果，对缓存在本机的用户分组数据 进行处理。如果成功寻找到目的节点的路由，则修改内核路由表以后，用 Linux 的原始套接 口(raw socket)将缓存的用户分组重新发送出去。 在 AODV 协议的实现过程中，程序需要在两个套接口上侦听数据帧的到达，一个是 TUN 套接口，这个套接口到达的是来自应用程序用户分组;另外一个是在 654 端口上的 UDP 套接 口，这个套接口是接收和发送 AODV 协议帧。处理这种套接口复用的问题，程序不可能采 用不停循环扫描的办法来在这两个套接口上侦听，因为这种 CPU 的开销太大了。而应该让 程序平时阻塞在套接口输入上，等待数据的到达，在等待过程中将 CPU 让出。当有输入到 达，则离开阻塞状态，调用对应套接口的接收处理进程。 处理这种多套接口复用的问题，通常有两种方法。一种是使用线程，另一种就是使用 Select[5]系统调用。在 Linux 系统中，从移植性、编程和维护的难易度、以及性能上考虑， 使用 Select 都具有一定的优势。所以，我们采用 Select 来实现。Select 函数允许进程指示内 核等待多个事件中的任何一个发生，并仅在一个或者多个事件发生或经过指定的时间后才将 进程唤醒。这个函数通知内核我们对哪些描述字的哪些事件感兴趣，以及等待多长的时间。 当感兴趣的描述字上发生感兴趣的事件后，将进程唤醒。这里的描述字不仅仅局限在套接口， 任何描述字都可以。 5. 结论 本文介绍了应用于无线自组织网络的 AODV 路由协议的工作原理,以及 Linux 系统的网 络框架,在其分析基础上提出了 AODV 路由实现方案。最后,对实现方案中的难点进行了逐条 分析，验证了基于无线局域网设备，在 Linux 系统上实现 AODV 路由算法的可行性。 参考文献 [1] IETF MANET Working Group．Ad hoc On-Demand Distance Vector (AODV) Routing draft-ietf-manet [EB/OL] ．