4-5网络层-路由协议

复习：4-2网络层-路由算法

路由选择协议的功能包括：交换网络状态或通路信息、选择到达目的地的最佳路径、更新路由表等

一.路由信息协议（RIP）及距离向量算法

（一）路由信息协议（RIP）

1.概念：RIP是内部网关协议（IGP）中最先得到广泛应用的协议，是一种分布式的基于距离-向量的路由选择协议。RIP协议要求网络中每一个路由器都维护从它自己到其他每一个目的网络的唯一最佳距离记录（即一组距离）。

*注：RIP的路由器不知道全网的拓扑结构

*直接交付：路由器和目的网络直接相连

距离（跳数）：从源端口到目的端口所经过的路由器个数（含自身），经过一个路由器跳数+1。基本单位为“跳”。特别的，从路由器到直接连接的网络距离为1（或0）。RIP允许一条路由最多只能包含15个路由器，因此距离为16表示网络不可达。

2.路由信息在相邻路由之间交换
仅和相邻路由器交换自己的路由表的全部内容，每30秒广播一次RIP路由更新信息（即按照一定的时间间隔发布路由信息），建立并维护路由表（动态路由表），经过若干次更新后，所有路由器最终都会知道到达本自治系统任何一个网络的最短距离和下一跳路由器的地址，即“收敛”。若180s还没收到相邻路由器X的更新路由表，则可能链路出现故障。RIP协议中每个网络的子网掩码必须相同

*注：收敛是指当路由环境发生变化后，各路由器调整自己的路由表以适应网络拓扑结构的变化，最终达到稳定状态（路由表与网络拓扑状态保持一致）。收敛越快，路由器就能越快适应网络拓扑结构的变化。

3.缺点
（1）RIP限制了网络的规模，它能使用的最大距离为15（16表示不可达）
（2）路由器之间交换的是路由器中的完整路由表，因此网络规模越大，开销也越大
（3）网络出现故障时，会出现慢收敛现象（即需要较长时间才能将此信息传送到所有路由器），俗称“坏消息传得慢与使更新过程的收敛时间长"

4.优点：实现简单、开销小、收敛过程较快（好消息传得快）

（二）距离向量算法
1.修改相邻路由器发来的RIP报文中所有表项
对地址为X的相邻路由器发来的RIP报文，修改此报文中的所有项目：把“下一跳”字段中的地址改为X，并把所有的“距离”字段+1

X到Net3的最短距离为2，下一跳R2

R1通过X到达Net3，“距离”字段+1（将2改为3），“下一跳”字段中的地址改为X（R2改为X）

2.对修改后的RIP报文中的每一个项目，进行以下步骤
（1）R1路由表中若没有Net3，则把该项目填入R1路由表
（2）R1路由表中若有Net3，则查看下一跳路由器地址
①若下一跳是X，则用收到的项目替换源路由表中的项目
②若下一跳不是X，选择距离短的保留
即：没有就加入，下一跳路由器相同直接修改，不同选最小

3.若180s还没收到相邻路由器X的更新路由表，则把×记为不可达的路由器，即把距离设置为16
4.重复以上步骤

[例1]
已知路由器R6的路由表，现收到相邻路由器R4发来的路由更新信息，试更新路由器R6的路由表：

①对R4发来的信息：距离+1，下一跳写R4

②对比R6：Net1加入，Net2修改，Net3修改

[例2]

来自B的向量为（5,0,8,12,6,2）表示B到A为5，B到B为0，B到C为8…
C到B的延迟为6，说明从C到B需要6，即从C通过B到ABCDEF为（5+6,0+6,8+6,12+6,6+6,2+6）=（11,6,14,18,12,8）

同样C通过D到ABCDEF为（19,15,9,3,12,13）
C通过E到ABCDEF为（12,11,8,14,5,9）

因此C通过X到达各结点的最短为（11,6,8,3,5,8）
C到自己不需要经过X，改为0
即（11,6,0,3,5,8）
答案B

[例3]
已知路由器B的路由表，现收到相邻路由器C发来的路由更新信息，试更新路由器B的路由表，并说明每一个步骤

解：
先将收到的C路由信息的距离+1，下一跳设置为C

则

（三）RIP协议的报文格式（了解）

RIP是应用层协议，使用UDP传送数据；一个RIP报文最多可包括25个路由，如超过，必须再用一个RIP报文传送。

二.开放最短路径优先（OSPF）协议及链路状态算法

使用分布式链路状态路由算法的典型代表，也是内部网关协议（IGP）的一种，可以根据链路状态路由算法计算最佳路由，使用Dijkstra算法计算从自己到各目的网络的最优路径。

迪杰斯特拉算法（Dijkstra）详解

1.实现：
（1）使用洪泛法向自治系统内所有路由器发送信息。即路由器通过输出端口向所有相邻的路由器发送信息，而每一个相邻路由器又再次将此信息发往其所有的相邻路由器。
（2）发送的信息是与本路由器相邻的所有路由器的链路状态（本路由器和哪些路由器相邻，以及该链路的度量/代价——费用、距离、时延、带宽等）。
（3）只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息，并且更新过程收敛得快

最后，所有路由器都能建立一个链路状态数据库，即全网拓扑图。
*注：OSPF是网络层协议，它不使用UDP或TCP，而直接用IP数据报传送

2.分组类型
（1）问候分组HELLO：用来发现和维持邻站的可达性。
（2）数据库描述分组DD：向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息
（3）链路状态请求分组LSR：向对方请求发送某些链路状态项目的详细信息。
（4）链路状态更新分组LSU：用洪泛法对全网更新链路状态。
（5）链路状态确认分组LSAck：对链路更新分组的确认。

3.链路状态路由算法
（1）每个路由器发现它的邻居结点HELLO问候分组，并了解邻居节点的网络地址。
（2）设置到它的每个邻居的成本度量metric。
（3）构造DD数据库描述分组，向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息。
（4）如果DD分组中的摘要自己都有，则邻站不做处理；如果有没有的或者是更新的，则发送LSR链路状态请求分组请求自己没有的和比自己更新的信息。
（5）收到邻站的LSR分组后，发送LSU链路状态更新分组进行更新。
（6）更新完毕后，邻站返回一个LSAck链路状态确认分组进行确认。
（7）使用Dijkstra根据自己的链路状态数据库构造到其他节点间的最短路径。

只要一个路由器的链路状态发生变化：
（1）泛洪发送LSU链路状态更新分组进行更新。（因此，OSPF协议可以根据网络通信情况动态地改变路由）
（2）更新完毕后，其他站返回一个LSAck链路状态确认分组进行确认。

4.OSPF的区域
为了使OSPF能够用于规模很大的网络，OSPF将一个自治系统再划分为若干个更小的范围，叫做区域。

通过划分区域，将利用洪泛法交换链路状态信息的范围局限在每个区域内，而不是整个自治系统。因此，在一个区域内部的路由器只知道本区域的网络拓扑，而不知道其他区域的网络拓扑情况。即：OSPF协议的任何一个路由器都知道自己所在区域的拓扑结构。

主干路由器

区域边界路由器
可以看出，主干路由器可以兼作区域边界路由器

区域内部路由器

自治系统边界路由器

R6作为自治系统边界路由器，连接到其他自治系统

采用分层次划分区域的方法，使得交换信息的种类增多，使OSPF协议更加复杂，使得每个区域内部交换路由信息的通信量大大减少，因此OSPF协议适用于规模较大的自治系统。

5.OSPF分组：OSPF直接用IP数据报传送。

6.特点
（1）每隔30min刷新一次数据库中的链路状态
（2）由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF协议要比距离向量协议RIP好得多。
（3）OSPF不存在坏消息传的慢的问题，它的收敛速度很快。
（4）OSPF对不同的链路可根据IP分组的不同服务类型（TOS）而设置成不同的代价
（5）OSPF对于不同类型的业务可计算出不同的路由，十分灵活
（6）负载平衡：如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径
（7）所有在OSPF路由器之间交换的分组都具有鉴别功能，因而保证了仅在可信赖的路由器之间交换链路状态信息
（8）支持可变长度的子网划分和无分类编址CIDR
（9）每个链路状态都带上一个32位的序号，序号越大，状态就越新
（10）使用迪杰斯特拉算法
（11）使用洪泛法，就像水波一样，相互交互路由表信息

三.边界网关协议（BGP）

边界网关协议是不同自治系统的路由器之间交换路由信息的协议，是一种外部网关协议，常用于互联网的网关之间，采用的是路径向量路由选择协议。属于应用层协议，基于TCP

1.工作原理
（1）每个自治系统的管理员要选择至少一个路由器作为该自治系统的“BGP发言人”
（2）一个BGP发言人与其他自治系统中的BGP发言人要交换路由信息（包含一个完整的路径，即到达某个网络所经过的路径），先建立TCP连接，再然后在此连接上交换BGP报文以建立BGP会话（利用BGP会话交换路由信息）

（3）所有BGP发言人都相互交换网络可达性的信息后，各BGP发言人就可找出到达各个自治系统的较好路由

2.特点
（1）BGP交换路由信息的结点数量级是自治系统的数量级，要比这些自治系统中的网络数少很多
（2）每个自治系统中BGP发言人（或边界路由器）的数目是很少的
（3）BGP支持CIDR。因此BGP的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列。
（4）在BGP刚运行时，BGP的邻站交换整个BGP路由表，但以后只需在发生变化时更新有变化的部分

3.BGP-4的四种报文
（1）打开（Open）报文：用来与相邻的另一个BGP发言人建立关系，并认证发送方
（2）更新（Update）报文：通告新路径或撤销原路径。用来发送某一路由的信息，以及列出要撤销的多条路由
（3）保活（Keepalive）报文：用来确认打开报文并周期性地证实邻站关系（在无UPDATE时，周期性证实邻站的连通性；也作为OPEN的确认）。
（4）通知（Notification）报文：用来发送检测到的差错。报告先前报文的差错；也被用于关闭连接。

四.三种协议比较

1.RIP是一种分布式的基于距离向量的路由选择协议，它使用跳数来度量距离。RIP选择的路径不一定是时间最短的，但一定是具有最小距离（最少跳数）的路径。

2.OSPF协议使用分布式的链路状态协议，通过与相邻路由器频繁交流链路状态信息，来建立全网的拓扑结构图，然后使用Dijkstra算法计算从自己到各目的网络的最优路径。

3.由于BGP仅力求寻找一条能够到达目的网络且较好的路由（不能兜圈子），而并非寻找一条最佳路由，因此它采用的是路径向量路由选择协议。在BGP中，每个自治系统选出一个BGP发言人，这些发言人通过相互交换自己的路径向量（即网络可达性信息）后，就可找出到达各自治系统的较好路由。