互联网的路由选择协议

路由选择协议规定了路由器如何交换信息生成路由表。

 

互联网的路由选择协议是动态的、分层次的、分布式路由选择协议。分层次是因为网络的数量很大，不可能让所有路由器都记录所有网络的路由，这点和DNS服务是一个道理。

互联网路由选择协议的整体思路是把整个互联网分为多个较小的自治系统 AS。一个AS包含多个路由器，是由多个最小单位的局域网组成的。

 

同时互联网路由选择协议分为两大类：

内部网关协议 IGP：用于自治系统内部路由器交换路由。内部网关协议用的最多的是RIP和OSPF协议

外部网关协议EGP：用于自治系统之间交换路由。用的最多的是BGP协议。

每一个AS都要同时运行一套 内部网关协议 和 外部网关协议。

 

RIP协议

RIP是一种分布式的、基于距离向量的路由选择协议。（分布式是指一个路由器不记录所有路由，而是部分路由；基于距离是指路由器只选择路过路由器最少的路径）。

运行RIP协议的路由器维护从它自己到AS内每个网络的距离记录。

 

距离的定义：

距离是指从本主机或路由器到某个网络的跳数，也等于从A到B（A和B可能是主机或路由器）中间经过的路由器（不含A和B）个数+1。

相邻的定义：

R1和R2相隔一个局域网（无论局域网内有无主机）就是相邻。

 

 

RIP特点

1、RIP允许一条路径最多只包含15个路由器（距离为16表示不可达），因此RIP只适合小型互联网（小型AS）。

2、RIP不能在两个网络之间同时使用多条路由（因为RIP只选择最短路径，但RIP2可以支持负载均衡，能根据负载选择多条路径）。因此RIP的缺点是只选择具有最少跳数的路由，哪怕还存在另一条高速（低时延大带宽）但路由器较多的路由。

3、好消息传播快，坏消息传播慢。

 

 

无论是什么路由选择协议，都需要解决3个问题：和谁交换路由信息、交换什么信息、什么时候交换。

 

对于RIP而言：

和谁交换路由信息：只和相邻路由器交换信息；

交换什么信息：交换自己的完整路由表给对方；

什么时候交换：一是定时交换，如每隔30秒，本路由器会向所有相邻的路由器发送一个RIP报文；二是当网络拓扑发生变化（比如有一个路由器从链路中移除了），路由器会及时向相邻路由器发送RIP报文通告自己的新完整路由。

 

 

RIP协议下路由表的建立

1、路由器刚开始⼯作时，只知道到自己连接的⽹络的距离和下一跳。

例如 路由器A有3个接口，分别连接到 128.0.1.0/28、 128.0.1.16/28、 128.0.1.32/28，所以路由表A启动后就有这3条路由记录。

2、以后，每⼀个路由器只和相邻路由器交换并更新路由信息。

3、经过若⼲次更新后，所有的路由器最终都会知道 ”从本路由器到达本⾃治系统中 任何⼀个⽹络的最短距离和下⼀跳路由器的地址“。

RIP路由表项：⽬的⽹络，距离（跳数，且是最小跳数），下⼀跳IP地址。

RIP收敛速度比较快（应该是正确信息收敛快，错误信息收敛慢）：即一个AS内所有路由器得到所有正确路由的速度比较快。

 

 

距离向量算法

RIP使用的算法是距离向量算法。该算法思路是：我到⽬的地的最⼩距离，等于我到邻居距离与邻居到⽬的地最⼩距离之 和（存在⼀个或多个邻居） 的最⼩值。

例如：路由器A和路由器R1~R3相连，R1~R3

 

算法具体：

1、本路由器为A，收到相邻路由器X的RIP报文，包含X的所有路由信息L。A把L的所有行中的下一跳字段改为X，把所有 距离 字段+1（其实是在X发出RIP之前加1的）。现在每一行都有：目的网络 N， 距离 d，下一跳IP地址 X。

2、对修改后的 每一行同步过来的路由P 进行以下步骤，假设A自己的路由表是LA：

如果A的路由表没有P的目的网络N的行，则把P添加到LA。

如果有则判断本路由的该行的N的下一跳是否为X，是则更新距离d。如果不是X，则判断本项目的距离d和P里面的d谁小，后者更小则更新本项目的下一跳为X，更新距离为新的d。

3、若3分钟还没有收到X的RIP报文则把X置为不可达的路由器，即把距离置为16。

 

 

RIP报文

RIP报文作为数据被封装在UDP报文段中，端口为520。一个RIP报文最多只能通告25条路由，如超过则要再用一个RIP报文传。RIP报文的头部固定为20字节，头部的路由标记是自治系统号，需要这个字段是考虑到一个路由器可能收到其他AS的RIP报文。

 

 

坏消息传播慢

当⽹络出现故障时， 要经过⽐较⻓的时间 (例如数分钟) 才能将此信息传送到所有的路由器。

一个例子，有一个AS，当前路由如下：

 

突然R3到 40.0.0.0/8的端口有故障，R3的路由表的该行的距离会变为16表示不可达。

 

下一刻，R2同步路由表给R3，于是16变为2

 

 

R3又同步路由表给R2：

 

这样循环下去，直到最终两个路由表的距离都是16为止。

解决方法其实也很简单，R3在把距离置为16之后，R3马上发送RIP给R2即可。

 

 

 

RIP的优缺点：

优点：

实现简单，开销较⼩。

 

缺点：

RIP 限制了⽹络的规模，它能使⽤的最⼤距离为 15（16 表 示不可达）；

路由器之间交换的是完整路由表，因⽽随着⽹络规模的扩 ⼤，交换路由信息的开销增加（网络中的RIP报文会增多）；

“坏消息传播得慢”，使更新过程的收敛时间过⻓。

只以最短路径为最优路径，可能错过一些更长但更优的路径。

 

 

 

OSPF协议

又称开放最短路径优先，使用链路状态协议，基于图算法中的“最短路径算法”得出路由路径。

 

OSPF的三个要点

交换什么信息：发送的信息是本路由器所有邻居的链路状态。

假设路由器R1和相邻路由器R2，则R1和R2的链路是指和这两个路由器的接口相连的网络。如图 R1到R2有3条链路。一条链路对应一对路由器接口。

 

链路状态指本路由器和哪些路由器相邻，以及这些链路的“度量”，度量相当于图的边的权重（RIP中的度量是跳数，而OSPF的度量包括距离（不是指跳数，而是真实距离）、带宽、时延等多个因素）。

和谁交换信息：使用洪泛法向AS的本区域中所有路由器发送消息。具体是路由器A向它所有邻居发送信息X，这些邻居又向它们自己的邻居原原本本的发送信息X（但不会向A发送，因为A是发送方）。

注意：一个路由器的所有邻居的链路状态只是该路由器的路由表中的一部分。

何时交换：当链路状态发生变化时（拓扑结构变化）才用洪泛法发送，并且每30分钟需要洪泛刷新一次链路状态。

 

链路状态数据库

若干次洪泛之后，所有路由器内部都能建立一个包含全网拓扑图的链路状态数据库，该数据库在全AS内是一致的。也就是说，每个路由器都知道全网有多少个路由器，每个路由器都知道整个网络拓扑图，知道从本节点到目的网络的完整链路和代价（RIP协议下，本节点只知道到目的网络的下一跳，而不知道完整链路）。

当路由器知道了全网（本AS的本区域）的网络图拓扑，就可以根据图的“最短路径算法”算出本路由器到目的路由的最短路径以及下一跳，并把该下一跳记录到路由表中的一行。

OSPF的更新过程收敛的很快。

 

OSPF的区域

由于当链路发生变化就要主动洪泛同步给整个AS的路由器，因此在规模很大的网络中就容易让整个网络充斥洪泛报文。

为了减小网络中的通信量，OPSF将一个AS再划分为若干个更小的区域。每个区域有一个32位的区域标识符，用点分十进制分隔。一个区域最多不超过200个路由器。

洪泛只局限于自己的区域发生，同一区域的路由器只知道本区域的完整网络拓扑。

上层的区域叫做主干区域，主干区域负责把下面多个分散的区域连接起来，其标识位 0.0.0.0。

如下图所示：

下面是一个AS，包含4个区域。

区域和区域之间的路由器是区域边界路由器，主干区域中的路由器是主干路由器，主干区域中负责和其他AS通信的路由器是AS边界路由器。

 

OSPF报文格式

OSPF不用UDP⽽是直接⽤ IP 数据报传送。

OSPF构成的数据报很短。可减少路由信息的通信量。

数据报短的另⼀好处是可以不必将⻓的数据报分⽚传送，分⽚传送的数据报只要丢失⼀个，就⽆法组装成原来的 数据报，导致整个数据报所有分片就必须重传。

 

 

OSPF的特点

如果到达同一目的网络有多条相似代价的路径，可以将通信量分配到多条路径做到负载均衡。

OSPF适用于大规模AS的路由同步，因为每个路由器洪泛的报文内容只和相邻路由器的链路数有关而与AS的规模无关。也就是说，无论AS的规模有多大，发送的OSPF数据报的大小都是不变的。而规模大可能带来的洪泛报文量大的问题可以通过AS内划分区域解决。

例如：R1和R2、R3相邻，R1和R2之间有3条链路，R1和R3间有2条链路，不管R1所在的区域有多大，此时R1发送OSPF报文只有5条链路状态内容。

下面是OSPF的通信过程，当一个节点R1的链路状态发生变化就会洪泛分组，并且每30分钟也会这样洪泛一次以确保区域内所有路由器的链路状态数据库是一致的。

 

注意：一个报文时不会经过重复的节点，即一个报文经过的链路不会成环（从上图可以看出）。

OSFP报文发出去后会收到确认报文以保证其可靠性。

除了洪泛之外，每两个相邻路由器会隔10秒交换一次OSPF问候分组（非洪泛），确保对方没有故障（确保2个路由器间的连通性）。

 

外部网关协议BGP

BGP 负责在AS与AS之间提供无环路的路由交换信息，基于路径向量协议。

BGP 使用TCP通信，端口是179。使用TCP连接是为了保证AS与AS间通信的可靠性和BGP路由的正确性。

每一个AS有至少一个AS边界路由器来和其他AS交换路由。并且除了启动的时候做全量交换路由信息之外，其他每次交换只做增量更新，交换时机是只有网络拓扑发生变化才会交换信息。

BGP路由交换过程：

 

 

1、首先，两个相邻的边界路由器R1和R2需要建立TCP连接，这个连接叫做 eBGP 连接，这个连接是一个长连接。两个AS之间通过R1和R2以及这个eBGP连接交换BGP路由。一个BGP报文包含多个BGP路由。

BGP路由 = “目的网络的网络地址X（或者说网络前缀），途经的AS的AS号（ASN），下一跳路由IP＂

假设R1和R2分别位于AS1和AS2。

R2发送的一条 "X, ASN1, R2"给R1 表示：R1如果想到达目的网络X，就需要经过ASN1这个自治系统和R2这个路由器。

R2会同步所有AS2内的目的网络的BGP路由给R1，但是由于是增量更新，所以其实R1和R2的每次交换的BGP路由是不会很多的。

2、一个AS内的所有路由器两两之间也要建立TCP连接，这个连接称为 iBGP连接。通过iBGP连接在AS内部交换IBGP报文（由此可知，BGP协议不仅是运行在AS与AS之间，也运行在AS内部）。

需要注意，一个AS内部的所有IBGP必须是全连通的，即使两个路由器间没有建立物理连接（即两个路由器不是相邻的），它们之间也仍要有IBGP连接。

边界路由器R1收到边界路由器R2的IBGP报文之后，R1会通过iBGP连接把这个BGP路由同步给所有AS1内的其他路由器。

所以AS内部，会同时运行 BGP和IGP协议（IGP泛指内部网关协议，即RIP或OSPF协议）。

 

AS1从EBGP邻居R2学到的路由会通过iBGP连接同步给AS1内的所有路由器，也会通过EBGP连接同步给另一个与AS1相邻的自治系统AS4的EBGP路由器R4。这么一来AS4和AS2是不相邻的两个AS，但AS4也能知道要到达AS2的目的网络X该怎么走。