网络协议栈分析与设计 大作业 主题：AODV 协议 作者：于跃 杜睿桓 苏宇晗 2 队员信息统计队员信息统计 姓名 班级 学号 完成工作 占总量比例 于跃 网 1001 班 201092002 阅读全篇 RFC 文档； 三分之一源代码的 阅读，撰写分析；前 期搜集资料；撰写协 议分析部分 1 / 3 杜睿桓 网 1002 班 201092378 阅读全篇 RFC 文档； 三分之一源代码的 阅读，撰写分析；源 代码架构分析；整合 三人的代码分析 1 / 3 苏宇晗 网 1002 班 201092251 阅读全篇 RFC 文档； 三分之一源代码的 阅读，撰写分析；最 终定稿；整理论述层 次；审阅校对 1 / 3 3 目录目录 一、一、概述„„概述„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„4 4 二、二、协议帧及路由过程协议帧及路由过程„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„6 6 三、三、源代码分析源代码分析„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„1212 四、总结„„„„„„„„„四、总结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„5959 4 AODV:AODV: 按需距离矢量路由协议按需距离矢量路由协议 一、一、 概述概述 AODV 协议(Ad hoc on-demand distance vector routing)是应用于无线 自组织网络中进行路由选择的路由协议,它能够实现单播和多播路由。
该协议是 自组织网络中按需生成路由方式的典型协议用于特定网络中的可移动节点它 能在动态变化的点对点网络中确定一条到目的地的路由，并且具有接入速度快， 计算量小，内存占用低，网络负荷轻等特点它采用目的序列号来确保在任何时 候都不会出现回环，避免了传统的距离向量协议中会出现的很多问题 1.11.1 定义定义 AODV 是一种源驱动路由协议当一个节点需要给网络中的其他节点传送信 息时，如果没有到达目标节点的路由，则必须先以多播的形式发出 RREQ(路由请 求)报文过程如图 1 所示RREQ 报文中记录着发起节点和目标节点的网络层地 址，邻近节点收到 RREQ，首先判断目标节点是否为自己如果是，则向发起节 点发送 RREP(路由回应)；如果不是，则首先在路由表中查找是否有到达目标节 点的路由，如果有，则向源节点单播 RREP，否则继续转发 RREQ 进行查找，aodv 详细的工作流程图见图 4 在网络资源充分的情况下，AODV 协议可以通过定期广播 hello 报文来维护 路由，一旦发现某一个链路断开，节点就发送 ERROR 报文通知那些因链路断开而 不可达的节点删除相应的记录或者对已存在的路由进行修复。
图 1 5 图 2 1.2 1.2 特点特点 (1)AODV 协议采用的基本路由算法为距离向量算法，但有所改进 (2)AODV 协议是按需路由协议也就是说，只有在主机需要的时候才会激发 出路由寻找过程 (3)AODV 采用 UDP 封装，属于应用层协议每次寻找路由时都要触发应用层 协议，增加了实现的复杂度 (4)IEEE 802．15．4 规定的帧大小为 127 字节，MAC 头部及尾部校验最多使 用了 25 字节，IPv6 头部与 UDP 头部占用 48 字节，只剩下 54 字节的空余 (5)LR—WPAN 中，拓扑结构相对简单，网络的规模相对较小，节点的位置不 固定，对它的设计首先要考虑的因素是简单、节能等问题AODV 的路由框架和 报文设计并没有考虑这些问题 收到路由控制信息 结束 检查信息类型 更新到目的节点的 路由、目的节点 前驱列表等信息 将受到影响的路径 删除（置为无效） 更新到源节点的 反向路由 RREQ消息RERR消息 RREP消息 本节点是目的 节点吗？ 是否有到 达目的节点的 路由？ 发送RRE P路由应答帧 如果本节点尚没有 缓存该RREQ，缓存 之并转发 本节点是 发起节点（源 节点）吗？ 使用新建立的路由 发送缓存的数据包 单播RREP至路由的 下一跳 是否一条以上 路径被删除？ 转发RERR到 前驱节点 是 否 是 否 是否 否 是 6 1.31.3 路由表字段路由表字段 每个 AODV 协议的结点都要维护一张路由表，表的各字段如下： （1） 目的节点 IP 地址 （2） 目的节点序列号（Sequence Number） （3） 目的节点序列号有效标志位 （4） 下一跳节点 IP 地址 （5） 本节点到达目的节点的跳数 （6） 前驱节点列表（precursor list） （7） 生存时间（路由失效或删除时间） （8） 网络层接口 （9） 其他的状态和路由标志位 其特征如下： （1） 路由表每项只记录下一跳路由信息，而不是整条路由信息，简化了路由 表的建立和维护 （2） 源节点和目的节点都维护各自的序列号 （3） 如何管理序列号是提高路由建立和维护的关键 I． 序列号是用来标识路由信息新旧程度（freshness）的 II． 源节点发起路由请求 RREQ，或者目的节点返回路由应答 RREP，都要更新 各自的序列号 III． 其他节点（中间节点）依据序列号的大小判断路由的新旧 二、二、 协议协议帧帧及及路由过程路由过程 AODV 帧主要包括： （1） RREQ – 路由请求帧 （2） RREP – 路由应答帧 （3） RERR – 路由错误帧 （4） HELLO – 活跃路由链路监测帧 下面我们结合路由过程，分析各帧的格式。
2 2.1.1 RREQRREQ 路由请求帧路由请求帧 在两个节点之间的路由有效、通信正常的情况下，AODV 路由协议不起任何 作用只有当源节点 S 需要向目的节点 D 发送数据包，但又没有 D 节点的路由入 口时才会发起路由请求，即发送路由广播帧 RREQ 当 RREQ 在网络中传播时，中间节点会更新各自到源节点的路由，我们称此 路由为反向路由同时 RREQ 请求帧中包含源节点以前记录的到目的节点的序列 号，但此序列号可能不是最新的（最大的） 中间节点如果有到目的节点的路由 时， 只有该节点记录的目的节点序列号比 RREQ 中的目的节点序列号更新 （更大） 时，才认为这条路由是有效的RREQ 请求帧的格式： 7 具体每个域的含义如下： Type（种类） 1 J Join flag （加入标志） ：为多播保留 R Repair flag （修复标志） ： 为多播保留 G Gratuitous RREP flag （免费路由回复标志） ： 指示是否 该向目标节点 IP 地址域指定的节点发送一个免费路由回复 消息 D Destination only flag （仅允许目的节点回复标志） ：标 志置位则仅允许目的节点回复本条路由请求 U Unknown sequence number （未知序列号） ： 指示目标节点 序列号未知 Reserved Sent as 0 （填充 0） ： 接收端忽略此字段 Hop Count 从发起节点到处理该请求的节点的跳数。
RREQ ID （路由请求标识） 这是一个序列号，用它和发起节点的 IP 就可以 唯一标识一个 RREQ 信息 Destination IP Address （目标节点 IP 地址） 目的节点的 IP 地址， 本 RREQ 消息的任务就是想 在发起节点和目的节点之间建立一条路由 Destination Sequence Number （目标节点序列号） 发起节点在以前通往目标节点的路由信息中能 找到的最新的序列号 Originator IP Address （发起节点 IP 地址） 发起本条路由请求消息的节点的 IP 地址 Originator Sequence Number （发起节点序列号） 指向发起者的路由表项中正在使用的序列号 RREQ 广播方式见图 4 1 1 引用自百度百科 图 3 图 4 8 2.2 2.2 RREPRREP 路由应答帧路由应答帧 当 RREQ 最终到达目的节点时，目的节点通过向该反向路由（即该 RREQ 传播 路线）发送 RREP 应答帧，从而在该条路径的各个节点建立通向目的节点的前向 路由 只有在以下情况下节点才会产生 RREP: （1） 该节点本身就是目的节点； （2） 该节点为中间节点，但是它有通向目的节点的活跃路径； 当 RREP 传播到源节点时， 中间节点根据该 RREP 更新它们各自指向目的节点 的路由信息。
同时节点只对第一次收到的 RREQ 发送 RREP 应答帧，之后到达的 RREQ 将被忽略 RREP 路由应答帧格式如下： 包含字段如下： Type 2 R Repair flag 修复标志；用于多播 A Acknowledgment required 需要确认；见 5.4 节和 6.7 节 Reserved Sent as 0 填充 0； 接收时忽略此字段 Prefix Size 前缀长度这个字段为 5 个 bit（值为 0 到 31） ，如果非 0， 则代表下一跳节点可以作为任何具有相同路由前缀的节点 被请求时的目的节点 这个 “相同路由前缀” 就是Prefix Size 定义的前缀 Hop Count 从发起节点到目标节点的跳数对多播路由请求，这个跳数 则是从发起节点到多播节点组里产生 RREP 信息的节点的跳 数 Destination IP Address 目标节点的 IP 地址，一条路由将提供给这个节点 Destination Sequence Number 和这条路由联系在一起的目标序列号 Originator IP Address 发起 RREQ 消息的节点的 IP 地址， 路由将被提供给这个节点。
Lifetime 路由生命时间，单位为毫秒在这段时间内，接收 RREP 的 节点会认为这条路由是有效的 注意到 Prefix Size（前缀长度）使得一个子网的路由器能够为子网内所有 的主机提供路由信息，而这个所谓的“子网”则是由路由前缀来定义的路由前 图 5 9 缀由子网路由器和前缀长度共同决定比如 192.168.3 就是一个长度为 24 的路 由前缀，那么所有以 192.168.3 开头的 IP 就属于同一个子网——译者注） 为了 让这个特性发挥作用， 子网路由器必须保证它和其他所有具有相同子网前缀的主 机都是可达的详情请参考第 7 节当前缀长度非零时，所有的路由信息（包括 先驱信息）都必须遵循子网路由，而不是单独的包含子网内目的主机的地址 RREP 单播方式见图 6 2 2.3 2.3 路由发现和维护路由发现和维护 2.3.1 路由发现过程 （a） 广播 RRE Q 路由请求帧 （b） 中间节点更新各自到源节点的路由表 （c） 如果收到 RREQ 的节点不是目的节点，并且没有到达目的节点的更新的 有效路由，则转发该 RREQ （d） 中间节点维护指向路由发起节点（源节点）的反向路由 （e） 目的节点或存在到目的节点有效路由的中间节点产生 RREP 路由应答帧 （f） RREP 通过之前建立的反向节点单播至源节点 （g） 源节点收到 RREP 应答帧，至此源节点可以向目的节点发送数据包 2.3.2 路由发现算法 源节点 应用层有数据发送请求，并且指向目的节点的路由有效，直接通过 该路由发送数据包 如果没有到达目的节点的有效路径，则产生 RREQ 广播帧，RREQ 的 序列号、ID 字段加 1，将源节点的 IP、序列号，目的节点的 IP、 序列号等信息添加到该 RREQ 中，广播至网络 中间节点 如果中间节点路由表中记录的到目的节点的路由有效， 并且记录的 目的节点的序列号比 RREQ 中的目的节点序列号更新（大于或者等 于） ，。