Ad hoc路由协议实现研究

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)的新组件加入内核分组转发功能以实现按需路由功能。当内核收到一个分组并发现没有向应的路由时，它首先通知用户空间的路由守护进程对该分组的目的地发出路由请求，然后将该分组缓存等待守护进程返回路由发现状态。如果该过程成功完成，则填充相应路由表条目，缓存的分组重新插入转发队列。为解决路由缓存问题，必须在每个路由条目上加入时间戳，记录该条目最后被使用时间。时间戳用于删除一个未使用的过期路由。