构如图 ! 所示。
图B
74+ 在网络协议栈中的位置
图!
74+ 分组结构
插入 74+ 头以后， <E 头的结构无需改动但 <E 头中 的 若 干 个 域 需 要 修 改 以 区 分 74+ 分 组 与 普 通 的 <E 分 组 CJD： <E 头 中 的 ； 由 KL(0()(2 域需要修改为 74+ 头标识 （ 74+8E+>;>M>*8<7 ） 于 74+ 信息的插入，整个分组的长度即 <E 头中的 0(0.2 2-1N0O 域也必须被修改； <E 头 的 目 的 地 址 &.&&L 应 该 被 修 改 为 74+ 源路由中的下一跳的地址，如果是 74+ 路由请求分组则应该 将置为广播地址； <E 头 中 任 意 其 它 域 的 改 动 都 会 引 起 头 部 校 验和（ 的变化， 需要用函数 SK8/-1&8)O-)P 重新计算。 MO-)P/QR）
%Baidu NhomakorabeaJ !""#$!! 计算机工程与应用
自己的路由缓存。当一个结点听到 %& ’() 网络中结点之间的 新链路时会将该信息添加进缓存中； 同样的当一个结点得知现 存路由信息失效时， 将会从缓存中删除该信息， 如果路由缓存溢 出， 需要采用 *+,（ 算法来进行淘汰处理。 *-./0 +-)-1023 ,/-&） 发送缓冲区： 结点的发送缓冲区是一些由于该结点没有一 个到达目的节点的源路径而不能被该结点发送的分组组成的 队列。一般来讲， 节点在将分组插入发送缓冲区的同时就会发 起一个路由发现过程， 如果路由发现过程成功的话， 这些分组 就会被发送出去。 在发送缓冲区中的每个分组都标记了它进入 发送缓冲区的时间， 当 在 被 放 入 456789,::5+8;<=5>,; 秒 后， 它将被丢弃。如果必须的话， 可以采用 :<:> 策略将分组在 没有超时时将其丢弃以防止发送缓冲区的溢出。 路由请求表： 如果某节点发送或转发了发往某目的结点的 路由请求分组，则在接下来的 74+8+5?8;<=5>,; 时间间 隔 内，该节点将不允许再次向这个目的结点发送路由请求分组。 节点的路由请求表是最近该结点发出的或转发的路由请求分 组的的集合， 其中每一个条目都记录了其被插入路由请求表的 时间， 当超时后这些条目将会被删除， 如果路由请求表溢出， 需 要采用 *+, 算法来进行淘汰处理。 重传缓冲区： 74+ 路由维护的基础就是每个节点需要在发 出或者转发分组时保证分组能够顺利地被下一跳的节点所接 收； 如果不能确认下一跳已经成功接收到分组， 该节点需要作 出 相 应 的 反 应 如 重 传 或 者 到 达 最 大 重 传 次 数 =%@8+5A
所有的路由信息 简单和行之有效的路由协议 3%4。协议允许任一结点动态发现到达 0, 1)2 网络中其它任意节点的路由， 由 &’( 自动地进行维护。每个 &’( 头部都携带了到达目的节点的完整的路由跃点列表（ ， 中间节点只需简单地 ?)9:E86） 的特性可以显著减少路由协议的开销， 节省了电池能量， 减 对分组进行转发即可。同时 &’( 协议完全按需（ )*+,-./*, ） 少了分组冲突的概率并减少了潜在的大规模的路径更新信息的传播。使用 &’( 协议可以实现 0, 1)2 网络的完全的自 组织和自配置而无需任何已经存在的网络基础设施。论文详细论述了 &’( 路由协议在 KE*5L 操作系统 下 借 助 M-6AE:6-= 的实现。 关键词 动态源路由
M-6AE:6-=
路由发现
路由维护 文献标识码 0 中图分类号 BI#P#
文章编号 %""!+N##%+（ !""# ） !!+"%FJ+"O
)*+,-*-&./.%0& 01 !2&/*%3 "0’43- #0’.%&5 640.030, %& $%&’(
$% 7’/&538-&5 98/&5 $%/&1/&5 "8’ :/&./% 980’ :’;8-&5 （ &-9/=6.-*6 )A >).956-= ’2E-*2- /*, B-2?*):)G; ， BE/*QE* R*ES-=8E6;， BE/*QE* #"""F!）
动态源路由协议（ !"#） 在 $%&’( 下的实现
李光成 张连芳 舒炎泰 周宇征 （ 天津大学计算机科学与技术系， 天津 #"""F! ）
<+./E:： :EG5/*G2?-*GH-;)5$2).
摘 要
J4 动态源路由协议（ 是由移动节点组成的多跳无线 0, 1)2 网络 3#， 中一种 &;*/.E2 ’)5=2- ()56E*G I=)6)2):， &’(）
基金项目： 国家重大自然科学基金项目（ 编号： ； 教育部天地网项目资助 P"%"J"%O ） 作者简介： 李光成， 男， 天津大学电信学院计算机系， 硕士研究生， 研究方向： 计算机网络体系结构。张连芳， 男， 天津大学电信学院计算机系， 副教 授， 研究方向： 计算机网络性能评价。舒炎泰， 男， 天津大学电信学院计算机系， 教授， 研究方向： 实时计算机应用、 >XY’ 理论研究与工程 实施、 计算机网络性能评价及仿真。周宇征， 男， 天津大学电信学院计算机系， 硕士研究生， 研究方向： 计算机网络体系结构。
同 时 &’( 使 用 源 路 由 3!4 即 每 个 分 组 头 部 显 式 地 包 含 了 从 源 节 点到达目的节点的完整节点序列， 使用源路由的任何中间节点 都无需进行复杂的路由操作而只需根据分组头部的路由信息 将分组转发到下一个节点即可。 路由 &’( 协议主要由两部分构成即路由发现和路由维护。 发现和路由维护协同工作保证了节点维持的到达目的节点的 路由的及时和有效性： 路由发现： 当源节点 ’ 要发送一个数据分组到目的节点 但是源节点并不知道到达目的节点的路由信息时， 源节点 &， 就会发起一次路由发现过程。为了建立一条路由， 源节点广播 分组， 当该请求分组到达目的节 一个路由请求（ ()56- (-75-86） 点， 或者是到达某个中间节点且该节点具有到达目标节点的路 由信息时，这些节点就向源节 点 发 送 一 个 包 含 着 ’ 到 & 的 完
C!D
-0803K- 实 际 相 当 于 一 个 的 三 层 的 协 议 ， 如 SK8K.)P-0803K- ， CBBD 。除此之外还可以方便地使用 SKT8I"!#8K.)P-0803K- 等 ） 6-0US20-L， 6-0US20-L 是 2S1QT!$G 及 其 以 后 版 本 中 提 供 的 一 种 内 核 实现数据包过滤 X 数据包处理 X 6%; 等的功能框架， 6-0US20-L 提
! 系统结构 !$B 74+ 在网络协议栈中的位置
在链路 74+ 协 议 的 实 现 可 以 在 链 路 层 或 者 网 络 层 完 成 C#D， 层实现 74+ 具有如下的优势： （ 在 链 路 层 实 现 74+ ， 可 以 使 %& ’() 网 络 所 支 持 的 节 B） 点数目最大 化 ， 使 得 运 行 <EFG 、 <EFH 和 <E@ 的 节 点 可 以 做 相 同 的路由处理。 （ 历史的来讲， !） 74+ 从 地 址 解 析 协 议 %+E 和 <555I"! 源路由网桥 发展而来， 而这两者都是链路层的协议。
<=>.4/3.： B?- &;*/.E2 ’)5=2- ()56E*G 9=)6)2): （ &’(） E8 / 8E.9:- /*, -AAE2E-*6 =)56E*G 9=)6)2): ,-8EG*-, 89-2EAE2/::; J4 A)= 58- E* .5:6E+?)9 TE=-:-88 /, ?)2 *-6T)=U8 3#， )A .)CE:- *),-8 3%4$B?- &’( 9=)6)2): /::)T8 /*; *),- 6) ,;*/.E2/::; ,E82)S-= / 8)5=2- =)56- /2=)88 .5:6E9:- *-6T)=U ?)98 6) /*; )6?-= ,-86E*/6E)*8 E* 6?- /, ?)2 *-6T)=U， /:: =)56E*G E8 /56)./6E2/::; ./E*6/E*-, C; 6?- &’( =)56E*G 9=)6)2):$</2? &’(9/2U-6 2/==E-8 E* E68 ?-/,-= 6?- 2).9:-6- )=,-=-, :E86 )A ?)98 6?=)5G? T?E2? 6?- 9/2U-6 .586 9/88 /*, 6?- 6?- E*6-=.-,E/6- *),-8 Q586 A)=T/=,8 6?- 9/2U-68 8E.9:;$06 6?- 8/.6E.-， 6?- -*6E=-:; V*+&-./*, 9=)9-=6; )A &’( 2/* 8EG*EAE2/*6:; =-,52- 6?- )S-=?-/, )A 6?- =)56E*G 9=)6)2):， 8/S- 6?-*-=G; )A C/66-=; /*, ,-2=-/8- 6?- 9=)C/CE:E6; )A 9/2U-68 2)*A:E26E*G /*, 6?- A:)),E*G )A 9)6-*6E/: :/=G-+82/:- =)56- =-D A=-8?$&’( /::)T8 6?- *-6T)=U 6) C- 2).9:-6-:; 8-:A +)=G/*EWE*G /*, 8-:A +2)*AEG5=E*G， TE6?)56 6?- *--, A)= /*; -LE86E*G *-6T)=U E*A=/86=5265=-$B?E8 9/9-= ,-82=EC-8 6?- ,-6/E:-, E.9:-.-*6/6E)* )A &’( E* KE*5L TE6? 6?- /E, )A M-6AE:6-=$ ?-2@04A>： &;*/.E2 ’)5=2- ()56E*G ， M-6AE:6-=， ()56- &E82)S-=; ， ()56- ./E*6-*/*2-
%
引言
&’( 是 一 种 典 型 的 按 需 （ )*+,-./*, ） 0, 1)2 路 由 协 议 ，
整路由信息的路由应答（ 分组， 源节点 ’ 就会根 ()56- (-9:; ） 据这些信息建立新的路由。 路由维护： 由于网络中各节点的移动性， 网络拓扑随时会 发生变化， 一条路径中的某两个节点可能会因距离超出双方的 传输半径或其它的原因诸如中间节点故障等而导致现存路由 信息的失效。当路由维护指明某个源路由失效时， 就使用路由 分 组 通 知 源 节 点 ’， 源节点 ’ 就会尝试使用 错误（ ()56- <==)=） 或者再一次发起路由发 其它可以到达目的节点 & 的路由路径， 现过程来寻找一条新的路由路径。这个过程被称为路由维护。 使用 &’( 协议进行通讯的任何节点都需要维护如下四 个 概念性数据 结 构 即 路 由 缓 存 （ 、 发送缓冲区（ ()56- >/2?- ） ’-*, 、 路由请求表（ 和重传 缓 冲 区 （ @5AA-=） ()56- (-75-86 B/C:- ） (-D ： 6=/*8.E88E)* @5AA-=） 路 由 缓 存 ： 一 个 使 用 &’( 参 与 0, 1)2 网 络 的 结 点 所 需 的所有路由信息都存储在路由缓存中。 网络中的每个节点维护
;+%64=< ;58;<=54 后丢弃该分组，同 时 向 源 节 点 发 送 路 由
错误分组。 重传缓冲区是节点发送或转发的分组中那些尚未得 到下一跳确认的分组的集合。
# 74+ 在 *S1QT 下的实现 #$B *S1QT 6-0US20-L 简介
在 原 有 的 网 络 部 分 的 *V= （ 中， *(.&.W2- V-L1-2 =(&Q2- ） 如 果 对 网 络 部 分 进 行 处 理 ， 一 般 是 先 生 成 /0LQ)0 K.)P-0803K结 构 ， 在 用 &-F8.&&8K.)P 将 其 插 入 网 络 层 （ 此 时 的 K.)PA
供了一个抽象、 通用化的框架， 该框架定义的一个子功能的实 现 就 是 包 过 滤 子 系 统 CB!D ， 6-0US20-L 为 每 种 网 络 协 议 （ <EFG 、 <EFH 等） 定义一套钩 子 （ 函数（ ， 这 ’((P ） <EFG 定 义 了 Y 个 钩 子 函 数 ） 些钩子函数在数据报流过协议栈的几个关键点被调用。 在这几 个点中， 协议栈将把数据报及钩子函数标号作为参数调 用 1-0A US20-L 框 架 。 1-0US20-L 本 身 在 <E 层 内 提 供 了 另 外 的 Y 个 插 入 点 ： （ ’>>VCB!D） 6:8<E8E+58+>,;<6Z ， 6:8<E8*>M%*8<6 ， 6:8<E8