AODV 规范 RFC35612.docx
- 文档编号:18514417
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:36
- 大小:43.03KB
AODV 规范 RFC35612.docx
《AODV 规范 RFC35612.docx》由会员分享,可在线阅读,更多相关《AODV 规范 RFC35612.docx(36页珍藏版)》请在冰点文库上搜索。
AODV规范RFC35612
网络组诺基亚研发中心C.Perkins
RFC:
3561加州大学圣芭芭拉分校E.Belding-Royer
类别:
试验版辛辛那提大学S.Das
2003年7月
Adhoc网络中基于距离数组的按需(AODV)路由协议
本备忘状态
本备忘定义的只是一个试验性质的网络社区协议而已,它不是任何一种类型的网络标准。
我们非常需要各种讨论和建议用于改进这个协议。
本备忘录的分发不受任何限制。
版权声明
复制权属于整个因特网社区,保留所有权利。
摘要
本协议用于特定网络中的可移动节点。
它能在动态变化的点对点网络中确定一条到目的地的路由,并且具有接入速度快,计算量小,内存占用低,网络负荷轻等特点。
它采用目的序列号来确保在任何时候都不会出现回环(甚至在路由控制信息出现异常的时候也是如此),避免了传统的距离数组协议中会出现的很多问题(比如无穷计数问题)。
1.
导言
AODV算法旨在多个移动节点中建立和维护一个动态的,自启动的,多跳路由的专属网络。
AODV使得移动节点能快速获得通向新的目的节点的路由,并且节点仅需要维护通向它信号所及范围内的节点的路由,更远的节点的路由信息则不需要维护。
网络中连接的断开和异动会使得网络拓扑结构发生变化,AODV使得移动节点能适时对这种变化做出响应。
AODV的操作是无自环的,并且由于解决了Bellman-Ford“无穷计数”的问题,使得该算法在网络拓扑变化时(比如一个节点在网络中移动)能够快速收敛。
当一个连接断开时,AODV会告知所有受到影响的节点,这些节点会让用到这个连接的路由失效。
AODV的一个显著特点是它在每个路由表项上使用了目的序列号。
目的序列号由目的节点创建,并且被包含在路由信息中,然后这些路由信息将被回发到所有向它发起请求的节点。
目的序列号的使用确保了无回环,并且易于编程。
如果到一个目的有两条路由可供选择,那么收到请求的节点将会选择序列号最大的那一条(由于目的节点每次收到新的请求都会将目的序列号加一,所以序列号最大表明该路由最新)。
2.概述
路由请求(RREQ),路由回复(RREP)和路由错误(RERR)是AODV定义的三种消息种类。
这些消息通过UDP和通常的IP协议来接收。
举个例子,发起请求的节点需要用它自己的IP地址作为消息中的OriginatorIPaddress(发起者IP)。
对于广播,将采用IP协议指定的广播地址(255.255.255.255),这个地址意味着这种消息将不会被盲目转发。
但是,AODV操作确实要求特定的消息(例如RREQ)得到广泛的散布,甚至有可能散布至整个专有网络。
这些RREQ的散布的范围由IP头中的TTL来指定。
作为一个特点,将不会采用IP协议中的分片传输。
只要一条通道连接的两个端点都有通向对方的正确路由,AODV是不工作的。
当某节点需要连接到一个新的目的节点时,它将广播一个RREQ(路由请求消息)来尝试找到一条到目的节点的路由。
如果RREQ消息到达目的节点,这条路由将被找到。
另外一种情况下,路由也可以找到,就是RREQ到达了一个中间节点,该中间节点拥有到目的节点的“足够新鲜”的路由。
“足够新鲜”的路由首先要是一条到目的地的正确路由,该路由还需要拥有一个足够大的序列号,该序列号不得小于RREQ中的序列号(A‘freshenough’routeisavalidrouteentryforthedestinationwhoseassociatedsequencenumberisatleastasgreatasthatcontainedintheRREQ.)。
当朝发起RREQ的节点单播一个RREP后,这条路由就建立了。
所有接到请求的节点都会缓存一条回到发起节点的路由,所以RREP就可以通过单播从目的节点返回到发起节点,或者从一个能够找到目的节点的中间节点返回到发起节点。
节点将相邻节点(nexthops)的连接状态保存在活动路由表里(activeroutes)。
当活动路由表里有一条连接断开时,一条RERR消息(路由错误消息)将被用来通知其他节点发生了连接断裂。
RERR消息指出了不再能到达的目的节点(甚至是目的子网)。
为了实现这种报告机制,每个节点还要维护一个“先驱表”(precursorlist),表中包含了一些邻居的IP,这些邻居可能会将它用作达到目的地的下一跳节点。
先驱表里的信息可以很轻易的从回传RREP的过程中获得,因为按照定义,RREP就该是传往先驱节点的(见6.6节)。
如果RREP有一个非零的前缀长度,那么RREQ的发起者将被包括在先驱表里作为子网的路由。
(不是特定的某个精确目的地)。
RREQ也可以用来请求多播地址。
这篇文档将不细述这种类型消息处理的全过程(比如这种请求的发起者必须要遵循的某种特别的规则)。
但是,使中继节点能正确处理多播操作是非常重要的,特别网络中有没有做过发起节点或目的节点的中继节点,或类似的没有安装任何对多播有特殊操作的节点。
考虑到有这种“对多播不感冒”的节点,处理多播目的IP地址必须要和处理其他任何IP地址是一样的操作才行。
AODV是一个路由协议,它的工作就是管理路由表。
即使是短期的路由,也必须保留它在路由表里的信息。
比如为RREQ临时存储的返回路径。
AODV的每个路由表项将会包含下列的域:
-目的节点IP地址
-目的节点序列号
-目的节点序列号是否正确的标志
-其他状态和路由标志(比如,有效,无效,可修复,正在修复)
-网络接口
-跳数(到达目的节点需要的跳数)
-下一跳
-先驱表(在6.2节里描述)
-生命(路由过期或应当删除的时间)
管理序列号对避免路由回环至关重要,即使是当连接断裂,一个节点不再可达而无法提供他自己的序列号信息的时候也是如此。
当一条链路断开或失效,导致一个节点不可达,当这种情况发生时,将通过对序列号的操作和标注路由表项为不正确来使得这条路由失效。
细节请见6.1节。
3.AODV术语
按照惯例,本协议的说明使用全大写的单词,比如MUST,SHOULD等等来指出对协议各项特性的要求级别(参考文献1)。
参考文献3中没有定义的其他术语,在这一节定义如下:
(注,汉语中MUST会翻译为必须,SHOULD翻译为应当)
Activeroute(活跃路由)
路由表项里标为“有效”(valid)的通向目的节点的路由。
只有活跃路由能用来转发数据包。
Broadcast(广播)
广播的意思是向IP协议规定的广播地址255.255.255.255发送数据。
广播的包不会被盲目的转发。
但是广播在让AODV消息散布到整个专有网络的时候非常有用。
Destination(目的地)
数据包需要被送往的一个IP地址。
和“目的节点”是同一个意思。
当一个节点看到它自己的IP地址和数据包IP头特定的字段中的IP地址一样时,它就认为自己是这个数据包的目的节点。
到达目的节点的路由可以从AODV协议得到,AODV协议会在路由发现消息里得到路由信息。
Forwardingnode(转发节点)
愿意为其他节点转发数据包的节点。
转发节点会将数据包发送到它的下一个节点(就是在到达目的节点的路径上更靠近目的的那个相邻节点,这条路径由路由控制消息来建立)。
Invalidroute(无效路由)
一个过期的,在路由表项里被标记为无效(invalid)的路由。
当一个有效路由失效时,它会作为无效路由在路由表里再被保存一段时间。
无效路由不能用于转发数据包,但是它能在路由修复和以后的RREQ消息中提供一些有用信息。
Originatingnode(发起节点)
Adhoc网络内发出AODV路由发现消息的节点。
AODV路由发现消息需要被恰当的处理,然后会被传送到网络内其他节点。
例如,一个RREQ消息的发起节点就是发起一个路由发现过程并且将RREQ消息广播出去的那个节点。
Reverseroute(返回路由)
用于转发回复包的路由,这个回复包就是从目的节点或能达到目的节点的中间节点返回到发起节点的RREP包。
Sequencenumber(序列号)
一个单调递增的数字,由每个发起节点管理。
在AODV路由协议的消息里,这个序列号被其他节点用于检测发起节点发出的信息的新旧程度。
Validroute(有效路由)
见Activeroute(活跃路由)。
4.适用性综述
AODV路由协议被设计用于拥有数十个到上千个移动节点的Adhoc网络。
AODV能应付低速,中等速度,以及相对高速的移动速度,以及各种级别的数据通信。
AODV被设计用于节点间可以互相信任的网络,比如预先定义好密钥的网络,或者是确信不会有恶意入侵节点的网络。
为了提升可测量性和效能,AODV设计成尽力减低控制信息的流量,并且消除数据流量的影响(原文:
AODVhasbeendesignedtoreducethedisseminationofcontroltrafficandeliminateoverheadondatatraffic,inordertoimprovescalabilityandperformance)。
5.消息格式
5.1.路由请求(RREQ)消息格式
0123
01234567890123456789012345678901
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Type(种类)|J|R|G|D|U|Reserved(保留)|HopCount(跳数)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|RREQID(路由请求消息标识)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|DestinationIPAddress(目标节点IP地址)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|DestinationSequenceNumber(目标节点序列号)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|OriginatorIPAddress(发起节点IP地址)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|OriginatorSequenceNumber(发起节点序列号)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
路由请求消息的格式如上所示,包含下面几个域(或字段):
Type(种类)1
JJoinflag(加入标志):
为多播保留
RRepairflag(修复标志):
为多播保留
GGratuitousRREPflag(免费路由回复标志):
指示是否该向目标节点IP地址域指定的节点发送一个免费路由回复消息。
DDestinationonlyflag(仅允许目的节点回复标志):
标志置位则仅允许目的节点回复本条路由请求。
UUnknownsequencenumber(未知序列号):
指示目标节点序列号未知(见6.5节)
ReservedSentas0(填充0):
接收端忽略此字段
HopCount从发起节点到处理该请求的节点的跳数。
RREQID(路由请求标识)这是一个序列号,用它和发起节点的IP就可以唯一标识一个RREQ信息。
DestinationIPAddress(目标节点IP地址)
目的节点的IP地址,本RREQ消息的任务就是想在发起节点和目的节点之间建立一条路由。
DestinationSequenceNumber(目标节点序列号)
发起节点在以前通往目标节点的路由信息中能找到的最新的序列号。
OriginatorIPAddress(发起节点IP地址)
发起本条路由请求消息的节点的IP地址。
OriginatorSequenceNumber(发起节点序列号)
指向发起者的路由表项中正在使用的序列号。
5.2.路由回复(RREP)消息格式
0123
01234567890123456789012345678901
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Type|R|A|Reserved|PrefixSz|HopCount|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|DestinationIPaddress|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|DestinationSequenceNumber|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|OriginatorIPaddress|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Lifetime生命期|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
路由回复消息的格式如上所示,包含下面几个域(或字段):
Type2
RRepairflag修复标志;用于多播
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(前缀长度)使得一个子网的路由器能够为子网内所有的主机提供路由信息,而这个所谓的“子网”则是由路由前缀来定义的。
路由前缀由子网路由器和前缀长度共同决定。
(比如192.168.3就是一个长度为24的路由前缀,那么所有以192.168.3开头的IP就属于同一个子网——译者注)。
为了让这个特性发挥作用,子网路由器必须保证它和其他所有具有相同子网前缀的主机都是可达的。
详情请参考第7节。
当前缀长度非零时,所有的路由信息(包括先驱信息)都必须遵循子网路由,而不是单独的包含子网内目的主机的地址。
5.3.路由错误(RERR)消息格式
0123
01234567890123456789012345678901
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Type|N|Reserved|DestCount|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|UnreachableDestinationIPAddress
(1)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|UnreachableDestinationSequenceNumber
(1)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|
|AdditionalUnreachableDestinationIPAddresses(ifneeded)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|AdditionalUnreachableDestinationSequenceNumbers(ifneeded)|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
路由错误消息的格式如上所示,包含下面几个域(或字段):
Type类型,RERR的此字段为3
NNodeleteflag不必删除标志;当一个节点已经对这条连接作了本地修复时,这个标志位置位,这样上游的节点就不用删除这条路由。
Reserved保留字段,填充0,接收端不作处理。
DestCount本消息内包含的不可达目的节点的数目,必须至少为1.
UnreachableDestinationIPAddress
因为连接断开而不可达的目的节点的IP地址。
UnreachableDestinationSequenceNumber
路由表项里不可达目的节点的序列号。
这个不可达节点的IP就是上面那个UnreachableDestinationIPAddress。
当一条连接断开导致一个或多个节点不可达时,RERR消息就会被发出。
关于如何维护连接断开产生的记录,请见6.2节;如何建立目的节点列表的详细说明请见6.11节。
5.4.路由回复确认(RREP-ACK)消息格式
当收到一条’A’位(‘需要确认’位)被置位的RREP消息时,必须回发一条路由回复确认消息作为响应。
当网络中存在单向连接而导致路由发现的往返过程(见6.8节)无法完成时,这是一个典型的操作。
01
0123456789012345
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Type|Reserved|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type消息种类标志,RREP-ACK消息的这个标志是4
Reserved填充0;接收时忽略。
6.AODV操作
在本部分所描述的场景里,对于有某一特定目的地址的单播通信,节点生成了RouteRequest(RREQ),RouteReply(RREP)和RouteError(RERR)三种信息,并且还要决定如何处理这些消息。
为了正确处理这些消息并考虑到目的节点,在路由表项中需要维护某种特定的状态信息。
所有的AODV消息都要发送到654端口,并且使用UDP协议。
6.1.管理序列号
每一个节点的每一个路由表项必须包含关于目的节点(路由表就是为此而维护的)IP地址的序列号的最新可用信息。
这个序列号叫做“目的序列号”。
如果在任何时候一个节点接收到了新的(即未失效的)信息,而这个信息是跟RREQ,RREP,或者RERR消息(这些消息跟目的节点可能有关系)中的序列号有关的话,目的序列号就会更新。
AODV要求在网络中的每一个节点都要拥有并维护其目的序列号,以保证朝向这个目的节点的所有路由路径都是无环路的。
在两种情况下,目的节点会增加它自己的序列号:
-在一个节点发起一个路径发现的请求之前,他必须增加它自己的序列号。
这样,对于已经建立好了的朝向RREQ消息发起者的反向路由来说,可以防止本次请求与其相冲突。
-在目的节点生成RREP消息以响应RREQ消息之前,它必须更新它自己的序列号,新的值是它目前的序列号和RREQ消息包中目的序列号的较大者。
当目的节点要增加它的序列号时,它必须以无符号数的形式来处理序列号。
为了完成序列号的循环轮转,如果序列号已经达到了32位无符号整型变量所能达到的最大可能值(也就是4294967295),那么当它再增加时,这个数字将会变成0。
另一方面,如果序列号目前是2147483647——也就是32位以2的补码形式表示的最大可能值——下一个数字将会是2147483648,这是在此计数系统下的负数最大可能值。
负数的表示形式跟AODV序列号的增加无关。
比较两个需要处理的AODV序列号时的做法跟此正好相反(见下面)。
为了确定目的节点的信息是否是新的,当前节点会拿自己目前的序列号数跟接收到的AODV信息中的序列号数相比较。
这个比较必须使用32位有符号数,它对于完成序列号循环轮转是必须的。
如果从接收到的序列号数减去当前序列号的结果小于0的话,那么这个接收到的有关目的节点的AODV信息就必须被丢弃,因为跟节点当前所保存的信息相比,接收到的信息更加陈旧。
另外,节点为了修复路由路径中丢失了的或者过期了的下一跳时,可能会改变其路由表项中的目的序列号,这也是除了以上情况以外唯一要改变目的序列号的情况。
节点通过查询其路由表来查询都有哪些目的节点使用了这个不可使用的下一跳节点。
在这种情况下,对于每一个使用这个节点的目的节点,当前节点都会增加其序列号并把此路径标记为不可用(并见3.11,6.12部分)。
一旦节点接收到了一个足够新的(也就是包含大于等于本节点所记录的序号),并且是来自于已经标记相应路由表项为不可用的节点的路由信息时,当前节点应该以新的信息来更新其路由表信息。
节点需要改变目的路由表项中的序列号,当以下情况发生时:
-它自己就是目的节点,并且提供了一个到它自己的新的路由,或者
-它接收到了一个拥有关于目的节点序列号的新信息的AODV消息,或者
-朝向目的节点的路径过期了或者崩溃了。
6.2.路由表项和先驱列表
当一个节点从它的邻居接收到一条AODV控制包时,以及为某个特定的目的节点或目的子网创建或更新它的路由表的时候,它就会去检查它的路由表里是否有一个表项对应到那个目的。
当没有相关的表项时,新的表项就会被创建。
序列号要么就是从AODV控制消息里提取的,要么就干脆在路由表项里“序列号有效”这个位置标明“无效”
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- AODV 规范 RFC35612