AODV路由协议在Windows平台下实现的研究与设计

石朝阳

（广东轻工职业技术学院，广东 广州 510300）

1.引言

在Ad hoc网络研究进展中，其多跳路由问题一直是近年来的研究热点。AODV路由协议是Ad hoc网络中的一种被动式的按需动态路由协议，在节点有数据发送时，才激活路由发现机制寻找路由，这种路由协议能够节省Ad hoc网络紧缺的无线资源，因此在Ad hoc网络中得到了广泛应用。当前对于AODV的大多数研究都是基于仿真环境的，在实际系统中实现并应用的很少，特别是在Windows平台下的实现。在现实的操作系统环境中实现AODV路由协议对于AODV的进一步研究、验证以及实际应用都有重要的意义，Windows操作系统是在日常工作中应用最广泛的桌面操作系统，所以在Windows平台下实现AODV路由协议有重要的应用意义。

本文首先简单介绍了AODV路由协议，分析了在操作系统平台下实现AODV路由协议需要解决的问题，针对这些问题提出了在Windows平台下的实现方案。论文的重点是在分析和解决路由协议和操作系统相关的部分，路由协议本身工作机制是根据文献[1]在用户模式下实现的。

2.AODV协议概述

AODV路由协议是一种按需路由协议，也就是说当向目的节点发送数据包时，源节点才在网络中发起路由查找过程，找到相应的路由。AODV可以在各移动节点之间动态地、自启动地建立多跳路由。当链路断开时，AODV会通知受影响的节点，从而使这些节点能够被确认为无效路由。AODV允许移动节点响应链路的破损情况并以一种及时的方式更新网络拓扑。AODV操作是无环回（loop-free）的。AODV负责路由表管理，每个节点都要维护一张路由表来保存到目的节点的下一跳路由信息。

路由请求消息RREQ、路由应答消息RREP、路由错误消息RERR以及路由应答确认消息RREP-ACK是AODV定义的四种消息类型，AODV使用这些消息完成路由的查找过程，这些消息都通过UDP端口654进行发送和接收，适用于普通IP头处理。对于广播消息，使用了IP有限广播地址255.255.255.255，以防止此类消息盲目转发。

3.AODV实现面临的问题

操作系统中的路由功能一般分为两个部分：一部分是在系统内核中，根据路由表把包通过不同的网络接口转发到网络上，即包转发功能；另一部分在用户模式下，完成路由协议控制功能和设置具体的路由条目，即包路由功能。内核中的包转发功能维护一张路由表（如表1所示），转发包时需要查询该路由表并根据下一跳地址进行转发。内核中的路由表一般由用户模式下的包路由模块计算出来。包路由模块负责与对端进行路由消息交换并通过路由协议控制功能来计算路由。把包路由和包交换功能分开，传输数据时就不存在上下文切换的消耗，从而使得数据包流的效率更高，而且这样也增强了路由协议的可扩展性。而把包路由模块放在用户模式下可以减轻因为路由计算和路由发现所消耗的内核CPU时间和内存。

表1 内核路由表结构

总的来说，要实现AODV路由协议，需要考虑如下问题：

(1)确定何时需要发送RREQ：AODV是一个按需驱动的路由协议，所以在发送数据包的时候如果没有找到路由，并不能把包丢弃，而是应该触发RREQ。

(2)怎样通知用户模式下的包路由模块发送RREQ。

(3)将等待处理的包用队列缓存。

(4)路由发现后重新发送队列缓存的包。

这些都是在具体操作系统中实现AODV路由协议时需要考虑的问题，一般的操作系统本身并没有考虑这些问题，这就需要设计一定的方案来解决这些问题。

4.Windows平台下的实现

由于Windows平台的系统源代码不开放，所以不可能更改系统内核以满足实际的要求。所以需要使用一些策略来解决上节提到的问题。本节将讨论在Windows平台下的实现机制。

4.1 实现思路

路由协议需要维护系统内核中的路由表，因此需要和内核通信。在Windows平台下可以通过驱动程序来扩展内核的功能，微软和3Com公司在1989年制定了一套开发Windows下网络驱动程序的标准NDIS(Network Driver Interface Specification)，为网络驱动的开发提供了一套标准的接口，使得网络驱动程序的跨平台性更好。NDIS提供了一种基于链路层和IP层之间的中间层驱动(Intermediate driver)，可以通过这层驱动拦截链路层数据包。另外，NDIS提供了消息机制和共享内存机制，使得内核和用户程序可以进行消息通信和数据传输。因此在AODV的实现中可以使用NDIS技术实现内核部分的功能。

将Windows平台下实现的AODV路由协议分为包转发模块和包路由模块，包转发模块完成查询路由表并转发包的功能，包路由模块完成AODV路由协议控制功能。为了减少对操作系统内核的影响，包转发模块主要还是依赖Windows操作系统的包转发功能，实现中只是附加一些支持AODV路由协议的额外功能。包路由模块在Windows操作系统中既可以在内核模式下实现，也可以在用户模式下实现，考虑到上节提到的路由实现模式，需选择在用户模式下实现AODV路由协议的包路由模块。但是这也导致一个问题，就是当路由协议需要广播RREQ发现路由的时候，需要在内核外缓存数据包，这就要求把所有需要缓存的数据包从内核拷贝到用户模式下，在发现路由并更新路由表后再将这些数据包重新发送到内核，不过这种消耗相对于AODV的路由发现过程来说可以忽略不计。因此，实现的AODV需要满足两个功能要求：一是能够把向外发送的数据包从内核拷贝到用户模式下，另一个是能够把缓存的数据包再发送给内核。第一个要求在Windows操作系统下，可以通过驱动来实现，第二个要求可以通过socket来实现。

为了解决确定何时需要发送RREQ的问题，需要截获所有在路由表中没有找到路由的数据包。在Windows操作系统下可以用缺省路由来处理，如果在路由表中没有匹配路由，数据包就会转发到缺省路由上。使用NDIS驱动程序截获所有发送到缺省路由上的数据包（也就是没有匹配路由的数据包），并把它们缓存到队列中。查询路由表后，数据包的目的MAC地址将被填充为下一跳路由所对应的MAC地址，这样在ARP表中添加一条缺省网关对应的静态ARP条目（其MAC地址是固定的虚拟地址），就可以在驱动程序中根据MAC地址截获经过缺省路由的数据包了。

截获到数据包后，需要考虑如何将数据包发送到用户模式下的包路由模块，为此使用了前面提到的NDIS驱动程序的消息机制。驱动程序截获到数据包时，向包路由模块发送消息IO_PACKET_ARRIVAL_EVENT，并将数据包放入队列缓存，包路由模块收到消息后从队列读取数据包，并释放队列中已读的数据包。

接下来需要解决的问题就是在发现路由并更新路由表后如何将数据包重新发送到内核IP协议栈。这里可以使用raw socket机制。raw socket是一种特殊的套接字，称为原始套接字，可以用它来发送和接收IP层以下的原始数据包，通过raw socket发出去的包会直接被插入包转发之前的内核输出链表中，绕过了IP和包头的处理（之前已经做过这些处理）。用raw socket来发送队列中缓存的数据包，这些数据包就会直接经过路由表并用新发现的路由在内核中被转发。

最后需要解决的问题就是当一个路由条目被使用的时候需要刷新路由缓存。因为不可能更改内核路由表结构，所以需要单独维护一个和路由表条目对应的时间戳表，该表结构如表2所示，可以通过在NDIS驱动程序和包路由模块之间使用共享内存机制来实现这个时间戳表。在驱动程序中截获不经过缺省路由的数据包，检查使用的路由条目，并更新时间戳表中的中对应条目中的最后使用时间（last use time）。在包路由模块中通过访问这个时间戳表来检查路由是否过期，如果过期就从内核路由表中删除对应的路由条目。

表2 时间戳表

4.2 具体的实现

图1是在Windows平台下实现AODV路由协议的框架结构。主要包括内核模式中的NDIS中间驱动程序和用户模式下的包路由模块。本节将具体描述各个模块的实现细节。

图1 AODV在Windows平台下的实现框架

内核模式下的NDIS驱动程序位于IP层以下，拦截所有从IP层下来的数据包，将所有发送到缺省网关的数据包缓存以等待用户程序读取，并且检查所有不是经过缺省网关的数据包，根据IP包头来更新共享内存中的时间戳表。驱动程序的工作流程如图2所示。

图2 NDIS驱动程序处理流程

用户模式下的包路由模块采用多线程并行处理技术，主要完成两方面的功能：一方面用socket在端口654监听并处理AODV协议包，完成路由协议控制功能；另一方面处理和底层驱动程序通信，监听底层消息，在消息到来时从底层读取并缓存非协议数据，并在路由发现后用raw socket重发缓存数据。监听底层消息的线程工作流程如图3所示。

图3 监听底层消息的线程工作流程

5.结语

在Windows平台下实现AODV路由协议对于协议的验证、改进和应用都有重要的意义。论文首先介绍了AODV路由协议，并分析了实现AODV所面临的问题，然后提出了在Windows平台下的解决方案，文中使用的驱动程序和用户程序通信的方法很好地解决了按需路由的一些问题。

本文的设计思路对于所有按需路由协议在Windows平台下实现都有参考意义。今后需要进一步完善实现的AODV路由协议，还需要考虑和其它AODV路由协议实现的互通性；另一方面还可以在此基础上对所进行的路由协议的进一步研究进行验证，如QoS路由等方面。此外，还可以考虑在此基础上实现其它按需路由协议，将其中一部分抽象出来作为标准实现库。

[1]Charles E.Perkins，Elizabeth M.Belding-Royer，and Samir R.Das，Ad hoc On-Demand Distance Vector(AODV)Routing[A]IETF RFC3561，July 2003.

[2]V.Kawadia，Yongguang Zhang，B.Gupta，System Services for Implementing Ad-Hoc Routing Protocols.[A]Parallel Processing Workshops，2002.Proceedings.International Conference on，18-21 Aug.2002.Pages：135～142.

[3]E.M.Royer，C.E.Perkins，An Implementation Study of the AODV Routing Protocol.[A]Wireless Communications and Networking Conference，2000.WCNC.2000 IEEE，Volume：3，23-28 Sept.2000.Pages：1003-1008 vol：3.

[4]S.Desilva，S.R.Das，Experimental evaluation of a wireless ad hoc network. [A]Computer Communications and Networks，2000.Proceedings.N inth International Conference on，16-18 Oct.2000.Pages：528～534

[5]武亚静，黄钺峰等.Ad hoc网络AODV协议在Windows CE上的实现[J].计算机辅助工程，2009年第18卷第1期.

[6]金海军，余水宝等.Ad hoc网络中AODV路由协议的优化[J].计算机系统应用，2008年第12期.