[网络]路由算法（RIP、OSPF、BGP）

---

1.RIP算法

---

• 在AS¹内部使用的；
• 属于IGP²；
• 基于UDP协议；
• 基于距离-向量；
• 以讹传讹，坏消息传得慢；
• 只以跳数作为评价的标准，只适用于小型网络；
• 目前已经被OSPF取代；

1.概述

RIP是一种分布式的基于距离向量DV的路由选择协议
使用RIP协议的每一个路由节点各自维护一张到达其他目的网络的唯一最佳距离记录
这个只针对AS¹内部的目的网络，对于外部的网络无法维护（因此是有限的）

2.RIP关注的问题

1. 和谁交换信息？

• 和相邻的节点交换信息；

2. 交换什么信息？

• 交换完整的路由信息；

3. 何时交换信息？

• 每30秒交换一次；
• 若180秒未收到邻居的信息，则自动判定邻居没了（更改自己的路由信息：更改邻居不可达，值16）；

所以：

• 每一次只能获取邻居已掌握的路由信息；
• 若干次之后，便可获取完整路由信息；

3.RIP协议中的路由表

序号	目的网络	距离	下一跳的路由
1	IP_1	2	R_1
2	IP_2	3	R_2
3	IP_3	2	R_3
4	…	…	…

其中：

• 距离项，作用是给路由器维护路由表时使用的，转发时并不使用；
• 每个路由在转发时，只会根据目的网络来选择下一跳的路由（选中路由后，交由下层通过MAC转发）；
• 目的网络项，网络号，包含了掩码，通过掩码来计算；
• 路由表的条目中，对于一个目的网络只有一个下一跳（唯一）；

4.RIP算法过程

1. 相邻节点交换路由表，第一次结束后每一个节点都知道相邻节点的路由表；
2. 对于邻居的路由表，会和自己的路由表比较，修改项目时，会有以下场景；

判断	结果	判断	结果	操作
路由表有该网络？	√	-	-	+1后填入自己的路由表
路由表有该网络？	×	下一跳是该路由？	√	+1后填入自己的路由表
路由表有该网络？	×	下一跳是该路由？	×	则+1后和已有的条目比较距离，使用距离短的

3. 若持续180秒都没有收到邻居的信息，则更新邻居所在的条目的距离项值为16（表示不可达）；
4. 所谓邻居，就是路由表中下一跳的路由，第一次便可知道自己全部的邻居，之后同一邻居会有多个目的网络；

5.计算机网络的题中做法

实际的交换信息是完整的路由表，因此包含路由表的全部信息，可以是杂乱无章的。
但对于试卷题目中，一般RIP的信息是以向量体现的。

向量：（1 2 3 0 4 6）  
路由：（A B C D E F）  
二者一一对应即可。  
其中向量中为0的表示自己。

6.RIP缺点

1. 不能适用于大型网络。因为每次只能传邻居，而且每次交换的是完整路由表；
2. 收敛慢。因为每次在比较是总是优先使用距离小的，而断开的节点的邻居会更新距离为16，会很久才能判断出来；

2.OSPF算法

---

• 在AS¹内部使用的；
• 属于IGP²；
• 基于IP协议（因为数据量大）；
• 基于链路状态；
• 评价标准不局限于跳数，还包括链路状态、连通性、时延等；
• 得到的路径是最短路径，是时间最少的；

1.概述

OSPF是一种分布式的基于链路状态LS的路由选择协议
使用OSPF协议的每一个路由节点维护整网的拓扑图，每个节点单独计算到达每个网络的最短路径
这个只针对AS¹内部的目的网络，对于外部的网络无法维护（因此是有限的）

2.OSPF关注的问题

1. 和谁交换信息？

• 和全部节点交换信息（通过泛洪发送给所有节点，泛洪指的是向除了接收的端口外的所有端口转发数据）；

2. 交换什么信息？

• 交换自己的邻居信息（报文短）；

3. 何时交换信息？

• 链路发生变化，如新增或删除；
• 只有邻居变化了的节点才会发送；

3.OSPF算法过程

1. 起始状态，每个节点通过hello消息来获取邻居的信息（实际上会通知到所有的节点）；
   • 这个hello消息中包含了DR的Router-ID；
2. 然后各自泛洪到每一个节点（通过CSMA/CD来解决信道争用问题）；
3. 为了避免网络阻塞，会把整个网络划分区域，在各自区域中进行泛洪；
4. 获取到完整网络拓扑图后，通过Dijkstra算法算出到达各个路由的最短路径；
5. 知道到达各个路由的最短路径，同时也就可以得到下一跳和目标网络；

4.OSPF协议中的路由表

序号	目的网络	距离	下一跳的路由
1	IP_1	2	R_1
2	IP_2	3	R_2
3	IP_3	2	R_3
4	…	…	…

5.实际的OSPF

• OSPF成员分为以下三类：一个n个节点的网络，链接关系数 = 2×(n-2)+1；

OSPF成员类型	名称	备注
DR	指定路由	DR和BDR之间会建立联系
BDR	备用指定路由	DR和BDR之间会建立联系
DRother	其他路由	只会和DR和BDR建立联系

• OSPF汇聚过程中的状态；

状态	含义
down	没有与任何邻居交换信息
attempt	NBMA网络中，试图hello邻居但邻居未回复
init	收到邻居的hello消息，但未回应
2way	收到邻居的hello消息，但回应，则双方进入2way状态
exstart	DR、BDR选举完成后进入，在此状态会协商主从关系
exchange	交换DBD
loading	交换信息中
full	链路信息同步完成

注意：

从init->2way的过程：
0.启动后，R1/R2均进入init状态
1.R1向邻居发送hello消息，包含自己的RID
2.R2收到了R1发来的hello消息，检测其中的OSPF信息是否匹配，同时发送hello消息
	- 若匹配，发送hello消息包含R1和R2的RID
	- 若不匹配，发送的hello消息包含R2的RID
3.R1收到R2的hello消息，发现里面包含自己的RID，则R1进入2way状态，同时发送hello报文，包含R2的RID
4.R2收到R1的hello消息，发现里面包含自己的RID，则R2进入2way状态

总结：
	启动后向邻居发送hello消息
	若收到的消息含有自己的RID，则切换到2way状态
	init状会主动发送hello消息，但2way状态只能回复邻居发来的含有自己RID的hello消息

在2way状态会根据hello消息的优先级确定DR、BDR（知道DR、BDR的IP）

选取DR、BDR后进入exstart状态，此状态下，DRother和DR、BDR建立主/从关系，谁的RID大谁作为master

确定主从关系后进入exchange状态，由master启动，传输DBD
DBD消息中的sequence number只能由master来更改，功能类似于TCP中的seq字段

DBD包含了整个链路状态数据库LSDB的描述信息，slave会收到这个DBD消息，然后与自己的数据库比较
如果发现有要更新的内容，则进入loading状态，此时slave发送LSR，master响应LSU，slave响应LSACK
如果此阶段LSA丢失，则会重发

链路状态信息交换完成后，进入full状态

注意：
	在广播网络中，邻居之间始终处于2way状态
	在非广播网络中，所有的节点之间都是进入full状态
	在exchange下发送DBD消息，在loading下发送完整的LSA信息

hello消息的格式

字段名	长度	功能
Network Mask	4字节	发送Hello报文接口所在的子网掩码
HelloInterval	2字节	指定发送Hello报文的时间间隔，默认为10秒
Options	1字节	可选项
Rtr Pri	1字节	指定DR优先级。默认为1/如果设为0，不参与DR/BDR选举
RouterDeadInterval	4字节	指定路由器失效时间，默认为40秒
Designated Router	4字节	指定DR的接口IP地址
Backup Designated Router	4字节	指定BDR的接口IP地址
Neighbor	4字节	指定邻居路由器的RID
…	4字节	指定邻居路由器的RID

因为hello是泛洪出去的，因此每个一个区域中的所有路由器都会收到这个路由器的hello消息
泛洪是有限制的，不会无限下去。每个节点只会执行一次操作（当重复收到同一内容的泛洪消息，则不会处理）
泛洪是一种技术，和广播、组播不同。泛洪是把特定的MAC帧“看作”广播帧一样去处理，本身还是普通数据帧。
DR、BDR的选举需要一定的时间（需要每一个节点都收到hello消息）。
之所以hello消息中会有多个Neighbor字段，是因为泛洪技术，节点会接收到多个hello，但回复hello不是一一回复的

• OSPF使用IP进行封装，使用自己的ack机制；

• OSPF组播地址有两个：224.0.0.5和224.0.0.6；

组播地址	用途
224.0.0.6	DRother通知DR、BDR
224.0.0.5	DR通知DRother

6.OSPF网络类型

类型	特点	是否选举DR/BDR	发现邻居方式	示例
P2P	224.0.0.5组播发送Hello、DD、LSR、LSU、LSACK	×	自动发现	HDLC、PPP
P2MP	224.0.0.5组播发送Hello，单播发送DD、LSR、LSU、LSACK	×	手动指定
NBMA	单播发送Hello、DD、LSR、LSU、LSACK	√	手动指定	帧中继
BMA	224.0.0.5组播发送：Hello和LSACK，224.0.0.6组播发送：LSU，单播发送DD、LSR、重传	√	自动发现	以太网

注意：

LSACK消息根据不同链路以单播或组播形式发送。
LSACK消息中包含了路由的RID，可以被DR收到并判断是否期望的应答。

7.关于master/slave、DR/BDR

DR/BDR是在交换Hello阶段确定的，涉及到DR/BDR的选举流程
master/slave是在exstart阶段确定的，彼此交换不含LSA信息的DD，谁大谁是master，根据master发的DD.M标志决定是否发送DD
master/slave只决定了谁可以修改DD中的seq，原则上master和slave都要发带LSA信息的DD给对方（可以选择不进行）

发送DD的条件：

1. master
   • 收到丛机的DD（DD.M标志=1）
   • 未收到确认，重传DD
2. slave
   • 响应主机的DD（DD.M标志=1）
   • 如果收到的DD中seq为旧的，则发送前一个DD/seq为新的，则发送新的DD

8.区域划分

不同区域的路由器必须和骨干路由器连接，这些路由器平级，需要骨干路由器进行路由。
平级的路由器之间不会进行路由选择。

4.BGP协议

---

• 在AS¹外部使用的；
• 属于EGP³；
• 基于TCP协议；
• 基于路径-矢量，避免环路；
• 支持CIDR和路由聚合；

1.概述

BGP是一种分布式的基于路径矢量的路由选择协议
使用BGP的每一条路由信息包含了完整的路径
这个只针对AS¹外部的目的网络

2.参考网址

BGP基础知识

BGP路由协议详解(完整篇)

---

1. 自治系统 ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

2. 内部网关协议 ↩︎ ↩︎

3. 外部网关协议 ↩︎