1 引言

目前的路由协议仅是在仿真条件下研究，很少有真正的测试床实现。但仿真不能完全反映路由协议在实际工作中的真实状态，无法获得实际系统的精确行为。实现一个移动自组织网路由协议需要许多系统组件。许多路由协议必须事件支持，因此要增加对相应事件的支持。这里探究在实际操作系统中实现Ad hoc路由协议所遇到的基本问题，并提出一种新的体系结构解决方案。

2 Ad hoc路由协议实现的基本问题

2．1 一般路由体系结构

当前的路由体系结构将按功能分为分组转发和分组路由两部分。其中，分组转发功能是在操作系统内核部分实现；而路由功能在用户空间作为守护程序实现。一般路由体系结构为：内核收到分组，查询路由表并通过相应的网络接口将分组转发到下一跳邻居。内核路由表实体由路由守护进程根据其路由算法生成。转发和路由功能分开的思想与基本 Unix系统机制一策略分开的思想一致。该机制高效，轻量，因为策略的设计可在很大的时间跨度上改变而不会影响机制。分组转发可高效转发每个分组，所以该机制应位于内核。这样分组可尽快通过该节点。该分离原理使得现代操作系统的路由功能更高效灵活。同时在不改变系统内核的情况下，也可不断改进路由功能。

2．2 按需路由实现的基本问题

Ad hoc网络的路由协议可分为主动路由和反应式路由两类。主动路由协议(表驱动)通过周期性的交换控制信息维护一个到所有可能目的地的路由，而反应式路由 (按需)仅当有需要时才发起路由请求。主动路南协议如(DSDV)在路由体系中能像有线网络中的路由协议(如RIP，OSPF，BGP)那样很容易地在用户空间中实现。而反应式路由协议．如AODV和DSR则带来以下挑战：

(1)没有路由分组的处理通常经转发模块的分组都会匹配内核路由表，如果人口没有匹配的目的地址，内核就会立即丢弃该分组。而在按需路由协议中这是不可取的，因为并不是所有的路由都是事先存在的，有些是在有路由需求的时才进行路由发现得到的，所以正确方法是通知路由守护进程路由请求，将分组缓存直到路由发现过程结束且更新路由表。但操作系统不支持这种新的分组转发行为的机制，而且内核不对这些任务(如排队)所有未处理的分组提供足够的支持。

(2)更新路由缓存按需路由协议通常是在用户空间中缓存最近使用的路南，以减少路由发现开销。路由缓存中的每个条目都有一个定时器，当相应的路由被使用时，需重新设置该定时器，而当达到定时时间，要被删除该条目。如果内核路由表中的条目在事先定义的时间内未被使用(如未被查找过)，该信息必须能够被用户空间的路由守护进程获得。而这在当前的路由协议体系下很难实现，因为内核中没有可用的路由使用记录。

(3)转发与路由混合有些Ad hoc路南协议转发和路由功能没有明显界线，如DSR。该协议要求每个分组(不只是路由控制分组)必需携带一个特殊的DSR头以供用户空间中的DSR守护进程处理。该路由和转发功能结合的方式与现代操作系统内部的路由体系结构不相适应，且很难高效应用。将整个路由协议放入内核，或把核心路由表分离出来而将转发功能放入用户空间。而有些情况，违反该分离原则，获得一些优化以减少路由开销。

(4)新的路由模型有些路由协议采用非传统的路由模式(如源路由、基于流的转发路由等)。这些路由模式与当前的IP路由体系结构相背离，并且对系统设计提出挑战。在源路由方式下，一个分组要经过的全部路径由源节点决定，并且将这些路由信息编码在分组头部。而传统IP路由转发功能是逐跳的，并且由本地路由表驱动。在基于流的转发方式下每个分组都有一个流ID，网络中的每个节点都有一个流表，转发的过程是根据流ID查找流表，而路由的过程是在每个节点建立流表。

大多数通用操作系统不能灵活支持新的路由模型，因此这些路由协议的实现既要修改内核；IP栈又要使用内核扩展机制避开IP栈。

(5)跨层交互无线信道为跨层交互作用提供许多机会。在某些路由算法中，路由协议的设计要使用物理层和链路层参数，如信号强度、链路状态等。概念上应放弃跨层交互，因为虽然跨层设计会提供最优化，但不加选择的访问所有底层参数会严重损害网络体系结构。许多路由协议使用其他层路由协议信息以提高性能，例如每个相邻节点的链路质量信息是某些路由算法所需的。尽管可得到这些信息，但跨越不同的硬件和操作系统时没有统一的标准，需通过标准方式以便获得低层信息，这对开发路由协议非常重要。

3 新的体系结构

首先提出一种通用方法以在通用操作系统中支持按需路由协议，并提出下面机制以增强当前分组转发功能。在内核路由表的每个条目增加一个标志表明该条目是否为按需路由条目，从而当路由不可达时，内核将分组排队缓存而不是直接丢弃。一个路由若具有空的下一条或接口则将缓存以等待路由发现。同时路由表无需包括所可能目的地，使用基于子网标志的路由和默认路由可到达同样的目的。将一种称为按需路由组件 (ODRC)的新组件加入内核分组转发功能以实现按需路由功能。当内核收到一个分组并发现没有向应的路由时，它首先通知用户空间的路由守护进程对该分组的目的地发出路由请求，然后将该分组缓存等待守护进程返回路由发现状态。如果该过程成功完成，则填充相应路由表条目，缓存的分组重新插入转发队列。为解决路由缓存问题，必须在每个路由条目上加入时间戳，记录该条目最后被使用时间。时间戳用于删除一个未使用的过期路由。

4 Linux下的一种实现

4．1 Linux系统网络协议栈体系结构

Linux网络系统有硬件，数据链路层、IP层、INET Socket层、BSD Socket层和应用层5部分。其中在Linux内核中分组包括前4部分。图1为Linux系统基于TCP／IP的网络体系结构。

4．2 Linux系统网络堆栈的IP层

Linux路由系统中主要保存3种路由相关的数据：(1)在物理上与本机相连接的主机地址信息表，即邻居节点表。邻居节点表用neigh_table{} 数据结构表示，以neighbour{}数据结构为节点；(2)在网络访问中判断一个网络地址的数据表，是转发信息库FIB，用来保存路由规则，用 fib_table{)数据结构链表来表示；(3)最近使用过的路由缓存表，称为路由缓存表，用rtable{}数据结构链表表示。

在类Unix操作系统中，路由功能一般包括2部分。一部分驻留在操作系统内核中，用以基于表驱动的进程，根据路由表信息，设定正确的地址，将数据分组发往对应的网络接口，这部分称为“分组转发功能模块”；另一部分实现路由协议的逻辑计算，通过与其他主机交换信息计算出到其他节点的正确路由，实现真正的寻找路由和维护路由功能，这部分称为“分组寻址功能模块”。分组转发路由模块在内核中基于一个内核路由表来工作，每次发送数据分组都要查询内核路由表，取得对应的下一跳邻居节点的地址和对应的网络接口。内核路由表一般由分组寻路功能模块操作维护。在查找内核路由表时根据路由表项转发。如果找不到匹配的路由表项，则按缺省路由发送，一般将网关作为缺省路由的下一跳节点。如果缺省路由不存在则操作系统将直接丢弃数据分组。分组寻路模块功能负责寻路，它和其他节点交换信息，采用一定的路由算法计算和维护内核路南表。分组寻路功能模块既可在内核实现，也可在用户空间实现，Linux系统自带的分组寻路模块在内核中。分组转发功能和分组寻路功能分开后，可在分组转发功能模块不变的情况下，通过修改分组寻路功能模块用其他路由协议代替现有的路由协议。

4．3 Netfilter／iptables网络分组的处理

Netfilter是嵌入在内核IP协议栈的一系列调用入口，设置在数据报处理的路径上。Netfilter为每种网络协议定义一套钩子函数(IPv4定义5个子函数)，这些钩子函数在数据分组流过协议栈的几个关键点时被调用。在这几个关键点上，协议把网络数据分组、钩子函数及钩子函数标号作为参数调用 Netfilter框架。内核的任何模块可对每种协议的一个或多个钩子进行注册。当某个数据报被传送至Netfilter框架时，内核能够检测是否有模块对该协议和钩子进行注册。若已注册则调用该模块注册时使用的回调函数，这些模块就有机会检查、修改或丢弃该分组及指示Netfilter将该数据分组传入用户空间的队列。排队的数据分组被传递至用户空间，在用户空间异步进行处理。

一个用户空间进程能够检查数据分组、修改数据分组，甚至还可重新将该数据分组通过离开内核的同一个钩子函数重新注入内核中。

综上所述，由于Linux的Netfilter／iptables功能强大，并且与内核结合完美，因此受到广泛关注并应用于Ad hoc路由协议的实现。

4．4 基本问题的解决

Linux体系结构下，在处理无路由分组和更新路由缓存时具有较好的解决途径。

通过使用一个本地隧道设备Universal TUN／TAP作为这些地址‘接口’过滤无路由分组。再将这些分组缓存在一张由目的地IP地址为索引的Hash队列。

当路由发现完成成功后，使用新发现的路由，内核中的这些分组被恰当地路由出去，从而较好处理了没有路由分组。为每个路南表条目在内核外面维护一个时间戳来更新路由缓存。

设计一个route_check的简单核心模块维护该表，每个路由出去的分组都将经该模块，还可查看分组头并更新对应的时间戳。

5 结束语

由于Linux操作系统，通过分析当前操作系统的网络模块，列出实现Ad hoc路由协议所面临的问题并提出了一种可行的解决方案。