路由算法 - 图1

路由表的内容

目的网络 N 距离（跳数）d 下一跳地址 X

层次路由

网络规模非常大，为了减少路由器之间的数据交换，并且减少缓存和路径选择的 CPU 开销，将互联网划分为若干个自治系统是一个好方法。

自治系统内使用的路由协议为内部网关协议（IGP），或域内路由选择。例如 RIP 和 OSPF 协议
自治系统之间使用的路由协议叫做外部网关协议（EGP），或域间路由选择。例如 BGP 协议

image.png

还可以进一步划分，将自治系统划分为若干个区域，每个路由器都知道本区域的路由细节，而不用知道其他区域的路由细节。例如 OSPF 协议

路由协议

协议的比较

RIP 协议 OSPF 协议 BGP 协议
发送方式及发送对象 广播，邻接的路由器 广播，整个自治系统 点对点，和本节点相邻的路由器
内容 整个路由表，大小和网络规模相关 邻接的链路状态信息，大小和网络规模无关 到达某个网络所要经过的一系列 AS
发送时机 固定的时间间隔 网络状况发生变化时
协议的层次 应用层，UDP，因为需要广播 网络层，IP 数据报（交换的信息量大，需要报文尽量短） 应用层，TCP（网络环境复杂，需要保证可靠传输）
算法特性 贪婪的，可以得到全局的最优解 每台路由器都知道全局的拓扑结构，可以做负载均衡
路径选择 跳数最少 代价最低
收敛速度比较 慢。有“坏消息传得慢”的特点 快
算法的复杂度 交换的信息种类增加了，算法复杂，每个区域的通信量比较少

RIP 协议

RIP 的工作模式：每隔固定的时间就向相邻的路由器发送 RIP 广播，广播内容是当前路由器的路由表。（因此，RIP 消息的大小是和网络规模相关的）

跳数：路由器到其直连网络的距离跳数为 1；距离每经过一个路由器，跳数 +1 。当跳数为 16 时，视为不可达。

距离向量算法
当收到来自邻接路由器发来的 RIP 消息时：

  • 首先将下一跳地址改为邻接路由器，并且将跳数 +1
  • 如果当前路由表中并没有目的网络，则将 RIP 中的表项添加到当自己的路由表中
  • 如果当前路由表中有目的网络
    • 并且下一跳地址就是邻接路由器，使用 RIP 消息中的表项替代自己的表项。这样做是为了更新网络状况。
    • 下一跳地址不是邻接路由器，则比较距离，选择距离小的那一个更新自己的路由表。

坏消息传得慢
直连到路由器 R1 上的网络 Net1 断开连接时，这个消息可能会经过很多个时间间隔才会收敛下来。
相反，好消息传得快。
image.png

距离向量算法路由环路的形成（考点）
简而言之就是，距离向量算法的慢收敛，导致了某个路由器收到了无效的路由信息。
比如：有个网络无法到达，最新的消息和旧的无效消息同时在网络中传播，产生冲突，形成环路。

OSPF 协议

工作方式：向自治系统内的所有路由器广播链路状态（包括当前路由器和哪些路由器相邻，链路的度量。）
其中，度量可以是费用，距离，时延，带宽等，可以人为指定，对于不同的业务类型，可以计算出不同的代价。

OSPF 将自治系统进行层次划分：

  • 位于最顶层的是主干区域，用于和其他区域进行沟通。
  • 普通的区域都有一个区域边界路由器，从该区域到主干网络的数据由这个区域边界路由器来概括。
  • 主干区域中还有一个自治系统边界路由器，用于和自治系统外进行沟通。

image.png

如何寻路：每个路由器都知道关于整个网络结构的拓扑信息，可以使用 Dijkstra 算法计算单源最短路径。

协议的细节：

  • 使用问候分组来保持和邻居节点的连接，也就是 Hello 分组。

BGP 协议

BGP 采用的是路径向量路由选择协议（并不是 RIP 的距离向量协议）。

BGP 需要考虑的因素太多，可以人为的设置很多的规则，且互联网的规模过大，因此 BGP 只是找出较好的路径，而不是找出最好的路径。

BGP 不仅要运行在自治系统的边界路由器上，还要运行在自治系统的内部。

BGP 是应用层协议，通过 TCP 发送消息