网络基础-路由选择协议

为什么需要路由选择

如今，Internet是世界上最大的互联网络。为了解决主机与主机之间的通信问题，网络层需要考虑如何在庞大的网络中，为数据报的转发进行寻址。路由选择协议在解决主机之间的寻址问题有着重要作用。

路由选择就是寻找一条能够到达目的地点的路由器序列。不同的路由器序列对应的代价是不一样的，比如费用，延迟，跳数等等。

路由选择协议用来定义路由器如何实现路由选择功能，以达到让数据报从源主机到目的主机之间的传输路径是比较好的路由路径。

因为在Internet规模如此巨大的情况下，寻找最佳路径的成本和时延是很高的，所以这里是选择一条比较好的，代价较为低的路径，而不是最佳的路径。

我们知道，网络层的路由实际上是子网到子网的路由，那么，路由器与路由器之间的路由问题就等价于主机到主机之间的路由问题。这样一来，将网络看作是*有权联通图*的抽象。节点为使用路由器代表的子网，边为链路，边值为度量（路由代价，如跳数，时延，费用等等）。路由选择算法本质上就是图的路径算法。

路由选择的策略有：

• 静态路由选择策略
  • 非自适应，不能及时适应网络状态的变化，适合小型网络
• 动态路由选择策略（自适应）
  • 自适应的，能够较好地适应网络状态的变化，实现较为复杂，开销也较大，所以适合复杂的大型网络。

Internet主要的路由选择协议

现行Internet的路由选择协议主要是动态的，分布式路由选择协议。

Internet将整个互联网划分为多个较小的自治系统（autonomous system）,每个自治系统内部可以使用多种内部路由选择协议和度量（成本代价的度量），但是一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。

一个大的ISP就是一个自治系统。

按照自治系统的角度，可以将路由选择协议划分为两大类

• 内部网关协议IGP
  • 称之为域内路由选择协议
  • 也就是在一个AS内使用的路由选择协议，与其他AS选用的路由选择协议无关。
  • 目前使用得最多的就是RIP协议，OSPF协议
• 外部网关协议EGP
  • 称之为域间路由选择协议
  • 当数据报需要跨自治系统传输，到达一个AS边界的时候，就需要使用一种协议将路由选择信息（？具体什么信息？）传递到另一个AS中。
  • 目前使用得最多的就是BGP

协议	下层协议	算法	范围	环路检测
RIP、RIP2	UDP	距离向量	域内	不支持：使用跳数约束方法
OSPF	IP	链路状态	域内	支持
BGP	TCP	路径向量	域间	支持

RIP(Routing Information Protocol)

一种分布式的，基于距离矢量算法的路由选择协议。最大特点就是简单。

RIP认为，好的路由就是通过的路由器的数量少，所以RIP中的“距离”就是“跳数”，每经过一个路由，跳数就增加1。

距离矢量算法Distance Vector

DV是一种局部算法，路由器只知道与它有物理连接关系的邻居路由，和到他们之间的代价。叠代地与邻居交换路由信息，计算路由信息。这个交换的路由信息就是：“到所有网络的距离和下一跳路由器”。

实现是使用Bellman-Ford算法，具体算法实现过程见[#《计算机网络第六版-谢希仁》P153以及P154的例4-5]。

特点

RIP允许一条路径最多包含15个路由，距离超过15时，就认为不可达，由此可见，RIP只适用于小型网络。

主要特点：

• 仅仅和相邻路由器交换信息

  • 交换的信息就是本路由器当前的路由表
  • 路由表信息：目标网络，到这个网络的最短距离，以及对应的下一跳地址。

• 当前路由器到AS中所有网络的最短距离，以及经过每个网络应该经过的下一跳路由器

• 按固定的时间间隔交换路由信息。当网络拓扑变化时，也及时向邻居通告变化信息。

• **好消息传播得快，坏消息传播的慢。**网络出现故障的传播时间往往需要较长时间（数分钟），这是一个缺点。

• RIP协议由于发送频率高，所以使用的UDP协议进行信息传送。（可以将RIP协议实现当做是应用程序理解）

OSPF (Open Shortest Path First)

开放最短路径优先算法（之所以叫SPF，是因为使用了Dijkstra提出的SPF算法。），是分布式的，基于链路状态算法的路由选择协议。

链路状态算法Link State

LS是一种全局算法，分为两大步骤：所有路由器都要得到全局网络拓扑图和度量信息，对拓扑图进行运算得到路由表。

为了使得所有路由器都拥有完整的拓扑和边的度量信息（代价），当某个路由器的网络状态变化时，可以使用泛洪法，将自身与邻居之间的变化信息广播出去，其它路由器得到信息后继续向外扩散广播。最终所有路由器都能够得知变化信息。

当路由器拥有了全局拓扑结构后，就可以依据Dijkstra SPF算法构造出自己的路由表。

特点：

• 使用泛洪（flooding）法向本AS中所有的路由器发送信息。
  • 也就是通过所有输出端口向所有邻居发送信息，邻居收到信息之后再次向其所有邻居（排除来源路由器）发送接收到的信息，这样AS中所有路由器都能得到这个信息。
• 发送的信息就是本路由器相邻的所有路由器的链路状态
  • 链路状态就是本路由器和哪些路由器相邻，以及链路的度量（metric 表示距离，时延，带宽，费用等等）。这个度量可以理解为代价。
• 只有链路状态发生变化的时候，才会泛洪信息。与RIP的定时交换信息不同。
• 每个路由器都有一个链路状态数据库，存放的实际上就是全网（AS）的拓扑结构图，每一个路由器通过全网拓扑图构造出自己的路由表（使用Dijkstra算法计算）

为了避免泛洪导致的广播风暴问题，可以将AS再次划分为若干个更小的区域，泛洪就只是在当前区域内泛洪。

OSPF协议报文很短，所以只需要直接使用IP协议进行通信即可，不需要使用UDP。

BGP

BGP是一个基于路径向量（path vector）路由选择算法的，边界网关协议。考虑到实现的复杂度与成本，BGP协议目的不是寻找最佳的路由，而是寻找一条能够达到目的网络的比较好的路由。

原因有两个：

• Internet规模太大，使得AS之间路由选择非常困难。主干网上的路由表早已经超过5万个网络前缀。如果使用链路状态算法，每一个路由器都需要维持一个很大的链路状态数据库LSDB。同时如此大的LSDB，计算最短路径所花费的时间也太长了。
• AS之间的路由选择需要考虑有关策略。不同AS内部的代价可能是不同的，那么在AS之间使用最短路径也是不能适配的。另一方面，不同AS所在的国家地区，可能由于政治，安全等原因不允许某些AS的数据经过。这时，只能是网络管理人员对灭一个路由期进行设置。

BGP比较合理的做法是在AS之间交换可达性信息，而不是代价。这样一来BGP就采用了一种与RIP,OSPF都不同的算法：路径向量（Path Vector）算法。

每一个BGP都会由管理员配置一个或者多个路由器作为BGP发言人（BGP speaker），由他们进行路由信息交换。发言人之间需要事先建立TCP连接（端口179），确保通信的质量。当新增路由，撤销路由或者网络异常时，发言人就使用建立的TCP会话交换信息。

发言人借助交换的信息，得到最终的路径信息访问列表（AS Path List），例如要到达网络N1,N2,N3可经过路径(AS1,AS2)。具体例子：参考[《图解TCP/IP 第5版》7.6.2]