AODV协议分析

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