Computer|计算机网络之路由协议详解

在谈路由协议之前,我们先来看一下路由器的结构:
路由器是一种具有多个输入端口和多个输出端口的专用计算机,其任务是转发分组。
Computer|计算机网络之路由协议详解
文章图片


路由选择部分的核心是路由处理机,路由处理机可以根据选定的路由协议构造出路由表,同时经常或定期和相邻路由器交换路由信息来更新和维护自身的路由表。
分组转发部分包括一组输入端口、交换结构和一组输出端口。交换结构又称交换组织,它的作用就是根据转发表把收到的IP数据报从路由器合适的端口转发出去。交换结构可看成一个在路由器中的网络。


因为笔者主要研究WMN,所以首先从WMN的路由协议说起,但是WMN路由协议很多都是借鉴有线网络的路由协议,所以目的在于让读者对于网络层的路由协议有个全局的认识。本篇虽然有一些专业术语,但基本都在上下文可以找到解释。如果有些内容遗漏或解释不到位,请读者自己搜寻资料,请见谅。


WMN的动态性,多跳性使得传统的路由协议不能够很好的处理无线网状网中拓扑结构和链路状态的快速变化。
WMN由Ad hoc网络发展而来,Ad hoc网络重点在移动,而WMN重点在无线。目前主流的WMN路由协议也是从Ad hoc网络路由协议发展而来。主要包括三种类型的路由协议:先验式路由协议、反应式路由协议、混合式路由协议。


【Computer|计算机网络之路由协议详解】在先验式路由协议中,无论是否有通信需求,每个节点采用周期性的路由分组广播维护一张包含到达其他节点的路由信息的路由表,当检测到网络拓扑结构变化的时候,节点在网络中交换并更新路由表。源节点一旦要送分组,可以立即获得指向目的节点的路由。
这类的路由协议通常是通过修改现有的有线路由协议来适应 Ad Hoc无线网络要求,如通过修改路由信息协议(RIP)得到的目的节点序列距离矢量协议(DSDV)。 因此这种路由协议的时延较小,但是协议需要大量的路由控制报文路由,协议的开销较大。 常用的先验式路由协议有 DSDV,HSR,GSR,WRP等。
DSDV协议
DSDV协议的基本原理是:每一个节点维持一个到其它节点的路由表,表的内容为路由的“下一跳”节点。DSDV创新之处是为每一条路由设置一个序列号,序列号大的路由为优选路由,序列号相同时,跳数少的路由为优选路由。正常情况下,节点广播的序列号是单调递增的偶数,当节点B发现到节点D的路由(路由序列号为s)中断后,节点B就广播一个路由信息,告知该路由的序列号变为s+l,并把跳数设置为无穷大,这样,任何一个通过B发送信息的节点A的路由表中就包括一个无穷大的距离,这一过程直到A收到一个到达D的有效路由(路由序列号为s+1-1)为止。

使用分层次的路由选择方法,可将因特网的路由协议划分为:
内部网关协议IGPI(nterior Gateway Protocol):具体的协议有多种,如:RIP和OSPF等。
外部网关协议EGP(External Gateway Protocol):目前使用的协议就是BGP
下面我们分别介绍:
路由信息协议RIP(RoutingInformation Protocol)
RIP采用距离向量算法,最大优点是简单。在实际使用中已经较少适用。RIP协议允许一条路径最多只能包含15个路由器。因此,“距离”等于16时即相当于不可达。可见RIP只适用于小型互联网。对于规模较大的网络应当使用OSPF协议。RIP不能在两个网络之间同时使用多条路由。RIP选择一条具有最少路由器的路由(即最短路由),哪怕还存在另一条高速(低时延)但路由器较多的路由。RIP进程使用UDP的520端口来发送和接收RIP分组。RIP分组每隔30s以广播的形式发送一次,为了防止出现“广播风暴”,其后续的的分组将做随机延时后发送。在RIP中,如果一个路由在180s内未被刷,则相应的距离就被设定成无穷大,并从路由表中删除该表项。RIP分组分为两种:请求分组和响应分组。
Computer|计算机网络之路由协议详解
文章图片


RIP协议的特点是:
仅和相邻路由器交换信息
路由器交换的信息是当前本路由器所知道的全部信息,即自己的路由表
按照固定的时间间隔交换路由信息
RIP协议存在的一个问题是:当网络出现故障时,要经过比较长的时间才能将此信息传送到所有的路由器。

开放最短路径优先OSPF(OpenShortest Path First)
OSPF原理简单,实现复杂,使用了Dijkstra提出的最短路径算法SPF。
OSPF最主要特征是使用分布式链路状态协议,而不是像RIP那样的距离向量协议。和RIP协议相比,OSPF的三个要点和RIP都不一样。
1、 向本自治系统中所有路由器发送信息。这里使用的方法是洪泛法(Flooding)
洪泛法(Flooding)
在OSPF协议中,当链路状态发生变化时要用Flooding向所有路由器发送信息。
例如,源节点希望发送一段数据给目标节点。源节点首先通过网络将数据副本传送给它的每个邻居节点,每个邻居节点再将数据传送给各自的除发送数据来的节点之外的其他。如此继续下去,直到数据传送目标节点或者数据设定的生存期限为0为止。
2、 发送的信息就是与本路由器相邻的所有路由器的链路状态,但这只是路由器所知道的部分信息,“链路状态”包括本路由器和哪些路由器相邻,以及链路的一些度量信息。而RIP协议发送的是到所有路由器的距离和下一跳路由器。
3、 只有当链路状态发生变化时,路由器才向所有路由器用洪泛法发送此信息。
由于各路由器之间频繁的交换路由信息,因此所有路由器最终都能建立一个链路状态数据库,这个数据库实际上就是全网的拓扑结构图。RIP协议中的每一个路由器虽然知道所有网络的距离以及下一跳路由器,但却不知道全网的拓扑结构(只有到了下一跳路由器,才能知道再下一跳应当怎样走)。
OSPF的更新过程收敛的快是其重要优点。(“收敛”就是在自治系统中所有的节点都得到正确的路由选择信息的过程)
OSPF不用UDP而是直接用IP数据报传送(其IP数据报首部的协议字段值为89)
Computer|计算机网络之路由协议详解
文章图片


OSPF共有以下5种分组类型:
1、问候(Hello)分组,用来发现和维持邻站的可达性。
2、数据库描述(Database Description)分组,向邻站发出自己链路状态数据库中所有链路状态项目的摘要信息。
3、链路状态请求(Link State Request)分组,像对方请求发送某些链路状态项目的详细信息。
4、链路状态更新(Link State Update)分组,用洪泛法对全网更新链路状态。
5、链路状态确认(Link State Acknowledgment)分组,对链路更新分组的确认。
为了使OSPF能够用于规模很大的网络,OSPF将一个自治系统再划分为若干个更小的范围,叫做区域。下图表示一个自治系统划分为4个区域。每个区域都有一个32位的区域标志符(用点分十进制表示)
当然,一个区域也不能太大,一个区域内的路由器最好不超过200个。
Computer|计算机网络之路由协议详解
文章图片


划分区域的好处就是把利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个自治系统,这就减少了整个网络上的通信量。


外部网关协议BGP
BGP是不同AS(Area System)的路由器之间交换路由信息的协议。
边界网关协议BGP只能是力求寻找一条能够到达目的网络且比较好的路由(不能兜圈子),而并非要寻找一条最佳路由。BGP采用了路径向量路由选择协议。
一般说来,两个BGP发言人都是通过一个共享网络连接起来的。一个BGP发言人要与其他自治系统的BGP发言人交换路由信息,就要先建立TCP连接(端口号为179),然后在此连接上交换BGP报文以建立BGP会话,利用BGP会话交换路由信息。
Computer|计算机网络之路由协议详解
文章图片


在RFC4271中规定了BGP-4的4种报文:
1、OPEN(打开)报文,用来与相邻的另一个BGP发言人建立关系,使通信初始化。
2、UPDATE(更新)报文,用来通告某一路由的信息,以及列出要撤销的多条路由。
3、KEEPALIVE(保活报文),用来周期性的证实邻站的连通性。
4、NOTIFICATION(通知)报文,用来发送检测到的差错。
在RFC2918中增加了ROUTER—REQUEST报文,用来请求对等端重新通告。
Computer|计算机网络之路由协议详解
文章图片




反应式路由协议
反应式路由协议又称为随选型路由协议或者按需路由协议。是专门针对移动自组织网络工作组MANET(Mobile Ad-hoc NETworks)环境提出来的。与表驱动路由协议相反,该类协议并不事先生成路由,而是仅在源节点需要时才这样做。因此,路由表信息是按需建立的,它可能仅仅是整个拓扑结构信息的一部分。

节点并不保存整个网络的及时准确的路由信息。当源节点要向目的节点发送报文时,源节点在网络中发起路由查找过程,找到相应的路由后,才开始发送报文。为了提高效率,节点可以将找到的路由保存在缓存中供后续发送使用。反应式路由协议按需路由的特点可以较好地适应节点移动较为频繁的无线网络环境,节点发生移动后,只需要更新需要发送数据的相关路径的路由信息即可。


混合式路由协议
混合式路由是将先验式路由协议和反应式路由协议两种路由方式的组合,在局部范围内使用先验式路由协议,维护准确的路由信息,并可以缩小路由控制消息传播的范围。当目标节点较远时,则使用反应式路由协议查找发现路由。ZRP协议就是混合式路由协议的代表。
Computer|计算机网络之路由协议详解
文章图片


ZRP协议是一种专为多变的通信环境(如可重构无线网络,RwN)设计的平铺式路由协议。在每个节点定义一个区域,此区域包含一些节点,这些节点的距离(也就是跳数)在一个限定的范围之内。这个距离被成为区域半径rzone。每一个节点只需要知道它的路由区域内的拓扑结构,而且其路由信息随着区域内的拓扑更新而更新。这样,尽管网络很大,但更新仅仅在局部区域进行。由于距离大于1,这样区域就有大量重叠。



参考资料:
1、无线网状网络的路由协议分析.TechTarget[引用日期2016-6-27]
2、谢希仁. 计算机网络(第5版)[M]. 北京:电子工业出版社, 2012.


    推荐阅读