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

精品论文linux 系统上 aodv 协议实现的分析齐朝霞 北京邮电大学信息与通信工程学院，北京 (100876) e-mail：摘 要：无线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中图分类号：tn911.引 言无线 ad hoc 网络是一种不需要基础设施的自组织和自管理网络,网络中所有的节点同 时具有终端和路由器的功能。由于无线自组网的拓扑结构动态变化，如何在移动中保持通信 成为一个重要的研究方向。现阶段已经提出许多的路由算法，各个路由算法有各自的优缺点， 适合于不同的场合1。利用无线自组网的技术，可以扩大无线局域网的使用范围。同时，可 以利用基于无线局域网的设备，很方便的验证无线自组网的一些技术。aodv(ad hoc on-demand distance vector)路由协议是 ietf 的 manet(mobile ad hoc networks)工作组推荐的无线自组网路由协议之一。本文在 ieee802.11b 或 ieee802.11g 协议 的基础上，利用无线局域网设备，对在 linux 操作系统上实现 aodv 路由算法进行了分析。2.aodv 路由协议介绍aodv 路由协议是一种按需路由协议。当网络拓扑结构发生变化时，它能快速收敛， 具有断路的自我修复功能。计算量小，存储资源消耗小，对网络带宽占用小。通过使用目的 节点序列号，协议实现了无环路由，并且避免了无穷计数的问题，并且很容易编程实现。为 了避免单向链路引起的错误操作，协议引入了一个黑名单，把和自己是单向链路的邻居节点 放入黑名单中。aodv 使用了分布式的、基于路由表的路由方式，所以建立路由表后，在路由中的每 个节点都要执行路由维持、管理路由表的任务。本文的重点是在 linux 实现上的内核方面， 下面主要介绍 aodv 所需要 ip 底层相关的内容。节点的路由中除了存储源和目的节点的序列号外，还存储了其他有用的信息，这些信息 成为有关路由项的软状态2。与反向路由相关的是路由请求定时器，这些定时器的目的是清 除一定时间内没有使用的反向路由项。定时器的设置依赖于自组网的规模大小，与路由表相 联系的另外一个重要的参数是路由缓存时间，即在超过这个时间之后，对应的路由表就变为- 7 -无效。所以每一个路由的最后使用时间都要保存,这是 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 系统自带的分组寻路模块是在内核中的。这样将分组转发功能和分组寻路功能分 开以后，可以在分组转发功能模块保持不变的情况下，通过修改分组寻路功能模块，而用其它路由协议来替代现有的路由协议。4.linux 上 aodv 协议实现方案4.1 实现框架在本文对 aodv 路由协议实现的方案中，将尽可能的利用 linux 操作系统现有路由机 制。实现方案不改变 linux 操作系统的分组转发功能模块，而是利用它的分组转发功能模块 的实现机制，巧妙的用我们自己的分组寻路功能模块来替换 linux 操作系统现有的分组寻路 功能模块。方案的基本实现思路是：用 netfilter 上的钩子函数时刻监测需要发送的数据报，一 旦没有路由，就用 netlink 来通知用户态发起 aodv 路由查询4。考虑到程序的移植性和扩 展的方便性。拟在用户空间实现 aodv 的寻路功能。aodv 路由协议实现的方案，按逻辑功能上可以分成三个主要部分：第一部分是接口 部分，第二部分是 aodv 路由算法部分，第三部分是内核模块部分。其中，前两部分是在 用户空间实现的，第三部分是内核空间实现的。具体结构如图 2 所示。第一部分：接口部分图 2 linux 上 aodv 协议实现框架接口部分的主要功能是利用 linux 系统提供的应用程序接口，为实现 aodv 路由协议 提供所需要的各种信息和服务。我们借助用户分组数据的发送过程，来分析这部分的功能。 在实现方案里，我们使用 netfilter 功能框架，实现数据包过滤和处理。其框架如图 3 所 示：图 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 内核 2.4 以上版本的挂钩（hook）功能。程序就 是利用这个特征，通过在 post routehook 上注册一个函数，每次检查出去的数据分组， 根据地址信息记下每条路由的最后使用时间。记录下的每条路径的最后使用时间，调用 netlink 套接口发送时间数据到用户态,创建时 间列表保存路由的最后使用时间。当需要的时候可以随时查询。这个部分是相对独立的一部分，在内核空间利用加载模块技术实现.4.2 aodv 协议实现的难点及其解决方法4.2.1 发起路由查找过程传统的有线网络能够很好的适合前面阐述的 linux 系统的路由实现方案。实际上，主动的无线自组网路由协议也能跟 linux 系统自身的路由方案很好的适应。然而，按需的无线自组网路由协议却无法用上述框架实现。因为在传统的分组转发功能模块中，当数据分组在找 不到相匹配的路由表项的时候，操作系统将简单的把这个数据分组抛弃。这个特点给我们实 现 aodv 协议带来了困难，因为 aodv 是按需路由协议，在找不到路由表项的时候，不能 将数据分组抛弃，而应该发起路由查找过程，寻找到目的节点的路由。在实现中，我们充分利用 linux 系统现有的功能，不修改其分组转发功能模块，而仅仅 改变它的分组寻路功能模块，用 aodv 路由协议的逻辑算法替换现有的分组寻路功能模块。 路由协议的分组寻路功能模块既可以在内核中实现，也可以在用户空间实现，在用户空间寻 找到正确的路由以后，再将路由传递到内核中，供分组转发功能模块使用。在内核中实现和 在用户空间实现，各有自己的优缺点。在内核中实现的优点在于能够以更快的速度工作，因 为它不需要在内核层和用户层之间交换数据。同时，在内核中实现可以用更方便的方法操作 数据分组的 ip 头部域，使得可以根据协议的内容方便的修改 ip 头部信息。然而，在内核实 现的缺点也很明显，它增加了内核态的资源占用，降低了整个系统核心的性能。同时，在内 核中实现调试相对困难，开发周期要长,且在移植性兼容性上不如在用户层开发的程序。综 合考虑后，我们采用在用户空间实现分组寻路模块。在实现中，在 nf_ip_local_out5挂上钩子函数,检测每一个出去的数据包,如果没有 路由,就缓存这个数据分组，提取出目的节点址，用 netlink 发起 aodv 路由查找过程。如 果 aodv 成功查找出到目的节点的路由，则将这条路由插入到内核路由表中，然后将缓存 的数据分组发送。如果没有找出路径，就将缓存的数据分组释放，通知源节点出错。4.2.2 记录每条路由的最后使用时间 无线自组网的按需路由协议通常自己保存有一个路由表，这个路由表的每一项都有一个定时器与之相关联。当定时器到期以后，意味着路由表项过期了，则应该将这个路由表项删除或者标记为过期不可用。aodv 路由协议需要记录每条路径的最后使用时间，而问题是， 系统自身并没有提供每条路径的最后使用时间给用户。这个信息必须自己提取。为了提取每条路由的最后使用时间，post route_hook 上注册一个函数。每次检查 出去的数据分组，根据地址信息就可以记下每条路由的最后使用时间，从而提供 aodv 路 由协议所需要的每条路由最后使用时间。4.2.3 对路由表和网络接口的操作在实现方案中，我们将不修改 linux 自身的分组路由转发功能。因此我们需要做的是: 根据分组寻路模块计算的路由结果，修改 linux 内核中的路由表。在实现方案中，我们将有 两个路由表，一个是内核的 linux 自带的我们称为内核路由表:另外一个是自己在用户层自 己建立的，我们称为 aodv 路由表。内核路由表，是 linux 自身的分组路由转发模块工作的基础，我们没有对其表项结构进 行任何修改，以保持通用性和可移植性。aodv 路由表结构是根据 aodv 协议构造的，记 录了每条路由的目的序列号、到目的节点的跳数等信息，分组路由寻路模块需要利用这些信 息，来进行正确的路由查找。程序对用户层的路由表定义了各种操作函数，因为分组路由寻 路模块和 aodv 路由表都是在用户空间实现的，它们之间可以很方便的进行信息交互。对 内核路由表则不一样，它们之间涉及内核和用户空间之间的交互，不能直接交换信息。程序 利用 linux 的 netlink 来操作 linux 内核路由表。4.2.4 信息的发送和接收在 aodv 路由协议的实现过程中，需要进行多种数据分组的发送和接收。一种是从应 用程序来的用户分组的接收、缓存和转发;一种是 aodv 协议帧的单播发送和接收:还有一种 是 aodv 协议帧的广播发送和接收。从应用程序发出的用户分组，在经过路由表的时候，按缺省的路由发送到了 tun 设备， 这是一个 tun 文件套接口，程序可以使用各种流操作函数，从这个虚拟的设备中接收数据。 接收的用 户分组数据存储在一个散列(hash)表中。在实现中，利用用户分组数据的目的节点 作为关键字，将正在进行路由查找过程的用户分组数据缓存在一个散列表中。当路由查找过程完成的时候，需要根据路由查找的结果，对缓存在本机的用户分组数据 进行处理。如果成功寻找到目的节点的路由，则修改内核路由表以后，用 linux 的原始套接 口(raw socket)将缓存的用户分组重新发送出去。在 aodv 协议的实现过程中，程序需要在两个套接口上侦听数据帧的到达，一个是 tun套接口，这个套接口到达的是来自应用程序用户分组;另外一个是在 654 端口上的 udp 套接 口，这个套接口是接收和发送 aodv 协议帧。处理这种套接口复用的问题，程序不可能采 用不停循环扫描的办法来在这两个套接口上侦听，因为这种 cpu 的开销太大了。而应该让 程序平时阻塞在套接口输入上，等待数据的到达，在等待过程中将 cpu 让出。当有输入到 达，则离开阻塞状态，调用对应套接口的接收处理进程。处理这种多套接口复用的问题，通常有两种方法。一种是使用线程，另一种就是使用 select5系统调用。在 linux 系统中，从移植性、编程和维护的难易度、以及性能上考虑， 使用 select 都具有一定的优势。所以，我们采用 select 来实现。select 函数允许进程指示内 核等待多个事件中的任何一个发生，并仅在一个或者多个事件发生或经过指定的时间后才将 进程唤醒。这个函数通知内核我们对哪些描述字的哪些事件感兴趣，以及等待多长的时间。 当感兴趣的描述字上发生感兴趣的事件后，将进程唤醒。这里的描述字不仅仅局限在套接口， 任何描述字都可以。5.结论本文介绍了应用于无线自组织网络的 aodv 路由协议的工作原理,以及 linux 系统的网 络框架,在其分析基础上提出了 aodv 路由实现方案。最后,对实现方案中的难点进行了逐条 分析，验证了基于无线局域网设备，在 linux 系统上实现 aodv 路由算法的可行性。参考文献1ietf manet working groupad hoc on-demand distance vector (aodv) routing draft-ietf-manet-aodv-08.txt eb/ol /html/draft-ietf-manet-aodv-08,2001.32郑相全著无线自组网技术实用教程m，北京：清华大学出版社，2004.63毛德操，胡希明著linux 内核源代码情景分析m，浙江：浙江大学出版社，2001.5 4(美) jonathan corbet, alessandro rubini, greg kroah-hartman linux 设备驱动程序(第三版)m. 魏 永明，耿岳，钟书毅译北京：中国电力出版社，2006.15(美) w.richard stevens, bill fenner, andrew m. rudoff unix 网络编程(第三版)m.杨继张译北 京：清华大学出版社，2006.1the analysis of implementing aodv routing protocal on linux osqi zhaoxiaschool of information and communication engineering, beijing university of posts andtelecommunications, beijing (100876)abstractthe wireless ad hoc network is a network that is self-organizing, self-management, and doesnt need any basic equipment, every node in the network works as a terminal and a router. so routing is a very important searching field in wireless self-organizing network. in order to adapt various occasions, people has designed many routing protocols and aodv (ad hoc on-demand distance vector) is one of these. the manet wg (mobi1e ad hoc network