第四章.网络层：4.6互联网的路由选择协议

文章目录

• 4.6.1 有关路由选择协议的几个基本概念
• • 1. 理想的路由选择算法
  • 2. 路由选择分类（自适应）
  • 3. 分层次的路由选择协议
• 4.6.2 内部网关协议RIP
• • 1. 协议RIP的工作原理
  • 2. 距离向量算法
  • 3. 坏消息传播得慢
• 4.6.3 内部网关协议OSPF
• • 1. 三个主要特点
  • 2. 链路状态数据库
  • 3. 划分区域
  • 4. OSPF的五种分组类型
  • 5. 指定路由器DR
• 4.6.4 外部网关协议BGP
• • 1. 协议BGP的主要特点
  • 2. BGP发言者
  • 3. eBGP连接和iBGP连接
  • 4. IGP、iBGP和eBGP的关系
  • 5. eBGP和iBGP
  • 6. BGP路由信息
  • 7. 三种不同的自治系统AS
  • 8. BGP路由如何避免兜圈子
  • 9. BGP的路由选择
  • 10. BGP-4的四种报文
• 4.6.5 路由器的构成
• • 1. 路由器的结构
  • 2. 交换结构

---

4.6.1 有关路由选择协议的几个基本概念

1. 理想的路由选择算法

正确完整、计算简单、自适应、稳定、公平、最佳。

关于“最佳路由”：

• 不存在一种绝对的最佳路由算法。
• 所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。

路由选择非常复杂：

• 需要所有节点共同协调工作的。
• 环境不断变化，而这种变化有时无法事先知道。
• 当网络发生拥塞时，很难获得所需的路由选择信息。

2. 路由选择分类（自适应）

3. 分层次的路由选择协议

• 互联网：
  • 采用自适应的（即动态的）、分布式路由选择协议。
  • 把整个互联网划分为许多较小的自治系统AS，采用分层次的路由选择协议。
• 分为2个层次：
  • 自治系统之间的路由选择或域间路由选择
  • 自治系统内部的路由选择或域内路由选择

自治系统AS：

是在单一技术管理下的许多网络、IP地址以及路由器，而这些路由器使用一种自治系统内部的路由选择协议和共同的度量。每一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。

两大类路由选择协议：

自治系统和内部网关协议、外部网关协议：

4.6.2 内部网关协议RIP

1. 协议RIP的工作原理

• 路由信息协议RIP是一种分布式的、基于距离向量的路由选择协议。
• 互联网的标准协议。
• 最大优点：简单。
• 要求网络中的每个路由器都要维护从它自己到其他每一个目的网络的距离记录（即一组距离）。

RIP“距离”的定义：

• 路由器到直接连接的网络的距离=1。
• 路由器到非直接连接的网络的距离=所经过的路由器数+1。
• RIP协议中的“距离"也称为’'跳数，每经过一个路由器，跳数就加1。

• 好路由=“距离短”的路由。最佳路由=“距离最短”的路由。
• 一条路径最多只能包含15个路由器。
• 距离’的最大值为16时即相当于不可达。
• RIP不能在两个网络之间同时使用多条路由，只选择距离最短的路由。

RIP协议的三个特点：

1. 仅和相邻路由器交换信息。
2. 交换的信息是当前本路由器所知道的全部信息，即自己的路由表。
3. 按固定时间间隔交换路由信息，例如，每隔30秒。当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。

路由表的建立：

• 路由器在刚刚开始工作时，路由表是空的。
• 然后，得到直接连接的网络的距离（此距离定义为1）。
• 之后，每一个路由器也只和数目非常有限的相邻路由器交换更新路由信息。
• 经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。
• RIP协议的收敛过程较快。“收敛”就是在自治系统中所有的结点都得到正确的路由选择信息的过程。

路由表主要信息和更新规则：

• 路由表主要信息

• 路由表更新规则

  使用距离向量算法找出到达每个目的网络的最短路径。

2. 距离向量算法

对每个相邻路由器（假设其地址为X）发送过来的RIP报文，路由器：

1. 修改RIP报文中的所有项目（即路由）：把“下一跳“字段中的地址都改为X，把 所有的“距离”字段的值加1。

2. 对修改后的RIP报文中的每一个顶目，重复以下步骤：

   (1)若路由表中没有目的网络N，则把该顶目添加到路由表中。

   (2)若路由表中有目的网络N

   ​ ①若路由表中网络N的下一跳路由器为X，则用收到的项目替换原路由表中的项目。

   ​ ②若下一跳不是X，收到项目中的距离小于路由表中的距离，则用收到项目更新原路由表中的顶目，否则不作处理。

3. 若3分钟还未收到相邻路由器的更新路由表，则把此相邻路由器记为不可达路由器， 即将距离置为16（表示不可达）。

4. 返回。

• 算法基础：Bellman-Ford算法（或Ford-Fulkerson算法）

• 算法要点：

  设X是结点A到B的最短路径上的一个结点。 若把路径A→B拆成两段路径A→X和X→B,则每一段路径A→X 和X→B也都分别是结点A到X和结点X到B的最短路径。

例如：

RIP2报文

• 组成：首部和路由2个部分。
• 路由部分：由若干个路由信息组成。每个路由信息共20个字节。
  • 地址族标识符（又称为地址类别）字段用来标志所使用的地址协议。
  • 路由标记填入自治系统的号码。
  • 后面为具体路由，指出某个网络地址、该网络的子网掩码、下一跳路由器地址以及到此网络的距离。
• 一个RIP报文最多可包括25个路由，因而RIP报文的最大长度是 4+20x25=504字节。如超过，必须再用一个RIP报文来传送。
• RIP2具简单的鉴别功能。

3. 坏消息传播得慢

• RIP协议特点：好消息传播得快，坏消息传播得慢。

• 问题：坏消息传播得慢（慢收敛）。

  当网络出现故障时，要经过比较长的时间才能将此信息 （坏消息）传送到所有的路由器。

在正常情况中，第一个“1”表示“从本路由器到网1”；第二个“1”表示“距离是1”；“-”表示“直接交付”；“R1”表示经过R1。

当网1出现故障时：

R1说：“我到网1的距离是16（表示无法到达），是直接交付。

但R2在收到R1的更新报文之前，还发送原来的报文，因为这时R2并不知道R1出了故障。

R1收到R2的更新报文后，误认为可经过R2到达网1，于是更新自己的路由表，说：“我到网1的距离是3，下一跳经过R2”。 然后将此更新信息发送给R2。

R2以后又更新自己的路由表为“1，4，R1”，表明“我到网1距离是4，下一跳经过RI”。

这样不断更新下去，直到R1和R2到网1的距离都增大到16时，RI和R2才知道网1是不可达的。

这就是好消息传播得快，而坏消息传播得慢。这是RIP的一个主要缺点。

RIP的优缺点：

优点：

实现简单，开销较小。

缺点：

1. 网络规模有限。最大距离为15（16表示不可达）。
2. 交换的路由信息为完整路由表，开销较大。
3. 坏消息传播得慢，收敛时间过长。

4.6.3 内部网关协议OSPF

• 开放最短路径优先OSPF是为克服RIP的缺点在1989年开发出来的。
• 原理很简单，但实现很复杂。
• 使用了Dijkstra提出的最短路径算法SPF。
• 采用分布式的链路状态协议。
• 现在使用OSPFv2。

1. 三个主要特点

• 采用洪泛法，向本自治系统中所有路由器发送信息。

  洪泛法：路由器通过输出端口向所有相邻路由器发送信息，而每一个相邻路由器又再次将此信息发往其所有的相邻路由器。

• 发送的信息是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。

  链路状态：说明本路由器都和哪些路由器相邻，以及该链路的度量（费用、距离、时延、带宽等）。

• 当链路状态发生变化或每隔一段时间（如30分钟），路由器才用洪泛法向所有路由器发送此信息。

2. 链路状态数据库

• 每个路由器最终都能建立。
• 全网的拓扑结构图。
• 在全网范围内是一致的（这称为链路状态数据库的同步）。
• 每个路由器使用链路状态数据库中的数据构造自己的路由表（例如，使用Dijkstra的最短路径路由算法）。
• 链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。重要优点：OSPF更新过程收敛速度快。

3. 划分区域

OSPF将自治系统划分为两种不同的区域。

主干区域标识符=0.0.0.0，作用：用来连通其他下层区域。

R3，R4，R7为区域边界路由器ABR；

R3，R4，R5，R6，R7为主干路由器BR。

R6为自治系统边界路由器ASBR。可以到其他自治系统。

划分区域的优点和缺点：

• 优点
  • 减少了整个网络上的通信量。
  • 减少了需要维护的状态数量。
  • 使每一个区域内部交换路由信息的通信量大大减小，因而使OSPF协议能够用于规模很大的自治系统中。
• 缺点
  • 交换信息的种类增多了。
  • 使OSPF协议更复杂了。

其他特点：

• 对于不同类型的业务可计算出不同的路由。
• 可实现多路径间的负载均衡。
• 所有在OSPF路由器之间交换的分组都具有鉴别的功能。
• 支持可变长度的子网划分和无分类编址CIDR。
• 32位的序号，序号越大状态就越新。全部序号空间在600年内不会产生重复号。

4. OSPF的五种分组类型

1. 问候分组。
2. 数据库描述分组。
3. 链路状态请求分组。
4. 链路状态更新分组。
5. 链路状态确认分组。

OSPF分组用IP数据报传送：

OSPF工作过程：

1. 确定邻站可达。

   • 相邻路由器每隔10秒钟要交换一次问候分组。
   • 令若有40秒钟没有收到某个相邻路由器发来的问候分组，则可认为该相邻路由器是不可达的。

2. 同步链路状态数据库。

   • 同步：指不同路由器的链路状态数据库的内容是一样的。
   • 两个同步的路由器叫做完全邻接的路由器。
   • 不是完全邻接的路由器：它们虽然在物理上是相邻的，但其链路状态数据库并没有达到一致。

3. 更新链路状态。

   • 只要链路状态发生变化，路由器就使用链路状态更新分组采用可靠的洪泛法向全网更新链路状态。
   • 为确保链路状态数据库与全网的状态保持一致OSPF还规定：每隔一段时间，如30分钟，要刷新一次数据库中的链路状态。

   OSPF链路状态只涉及相邻路由器，与整个互联网的规模井无直接关系，因此当互联网规模很大时，OSPF协议要比距离向量协议RIP好得多。OSPF没有“坏消息传播得慢“的问题，收敛速度快。

5. 指定路由器DR

• 多点接入的局域网采用了指定的路由器DR的方法，使广播的信息量大大减少。
• 指定的路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。

4.6.4 外部网关协议BGP

• BGP是不同自治系统的路由器之间交换路由信息的协议。
• BGP较新版本是2006年1月发表的BGP-4（BGP第4个版本），即RFC4271～4278。
• 可以将BGP-4简写为BGP。

1. 协议BGP的主要特点

• 用于自治系统AS之间的路由选择。
• 只能是力求选择出一条能够到达目的网络且比较好的路由（不能兜圈子），而井非要计算出一条最佳路由。
  1. 互联网的规模太大，使得自治系统AS之间路由选择非常困难。
  2. 自治系统AS之间的路由选择必须考虑有关策略（政治、经济、安全等）。
• 采用了路径向量路由选择协议。

2. BGP发言者

3. eBGP连接和iBGP连接

在AS之间，BGP发言者在半永久性TCP连接（端口号为179）上建立BGP会话。这 种连接又称为eBGP连接。

在AS内部，任何相互通信的两个路由器之间必须有一个逻辑连接（也使用TCP连接）。AS内部所有的路由器之间的通信是全连通的。这种连接常称为iBGP连接。

eBGP连接：运行eBGP协议在不同AS之间交换路由信息。

iBGP连接：运行iBGP协议，在AS内部的路由器之间交换BGP路由信息。

4. IGP、iBGP和eBGP的关系

• 在AS内部运行：
  • 内部网关协议IGP（可以是协议OSPF或RIP)。
  • 协议iBGP。
• 在AS之间运行：
  • 协议eBGP。

5. eBGP和iBGP

• 同一个协议BGP（使用的报文类型、使用的属性、使用的状态机等都完全一样）。
• 但它们在通报前缀时采用的规则不同：
  • 在eBGP连接的对等端得知的前缀信息，可以通报给一个iBGP连接的对等端。反过来也是可以的。
  • 但从iBGP连接的对等端得知的前缀信息，则不能够通报给另一个iBGP连接的对等端。

• R3从eBGP连接的对等端R4得到的前缀信息可以通报给iBGP连接的对等端RI或R20
• R3从iBGP连接的对等端RI和R2得到的前缀信息可以通报给eBGP连接的对等端R40
• 但R3从iBGP连接的对等端RI得到的前缀信息不允许再通报给另一个iBGP连接的对等

6. BGP路由信息

BGP路由=[前缀，BGP属性]=[前缀，AS-PATH，NEXT-HOP]

• 前缀：指明到哪一个子网（用CIDR记法表示），即通告BGP路由终点。
• BGP属性：最重要的两个属性是
  • 自治系统路径AS-PATH。
  • 下一跳NEXT-HOP。

R1a利用内部网关协议，找到从R1a到 R1d的最佳路由中的下一跳。

7. 三种不同的自治系统AS

• 末梢AS：不会把来自其他AS的分组再转发到另一个AS。必须向所连接的AS付费。
• 多归属AS：同时连接到两个或两个以上的AS。增加连接的可靠性。
• 穿越AS：为其他AS有偿转发分组。
• 对等AS：经过事先协商的两个AS，彼此之间的发送或接收分组都不收费。

8. BGP路由如何避免兜圈子

在属性AS-PATH中，不允许出现相同的AS号。

9. BGP的路由选择

• 本地偏好值最高：

  AS1选择通过路由器R1d到达X的BGP路由。

  本地偏好也就是本地优先，“本地”的意思是指。从本AS开始，到同一个前缀的不同BGP路由中，挑选一个较好的（即偏好值最高的）路由，这由路由器管理员或网络管理员根据政治上或经济上的策略来设置。

• AS跳数最小：

  本地偏好值相同的情况下。

  AS1选择通过路由器R1c到达X的BGP路由。

  但事实上，分组在AS4中反而要经过更多次数的转发。

  说明协议BGP不存在真正的最佳路由选择。

• 热土豆路由选择算法：

  如果按照前两种方法都无法选择最好的路由，那么就进入BGP路由的AS，执行热土豆路由选择算法。

  假定这两条BGP（AS1→AS2→AS5，AS1→AS4→AS5）路由的本地偏好相同，同时所经过的AS个数也相同。在这种情况下，AS1中的每一个路由器，就应采用热土豆路由选择算法。这种算法把分组比喻为烫手的热土豆，要尽快地转发出去。

  R1a选择R1c作为离开AS1的最佳选择，其BGP转发表中对应的项目应当是（匹配前缀X，下一跳路由器R1c)。（AS1→AS2→AS5）

  R1b选择R1d作为离开AS1的最佳选择，其BGP转发表中对应的项目应当是（匹配前缀X，下一跳路由器R1d)。（AS1→AS4→AS5）

• 选择路由器BGP标识符的数值最小的路由

  当以上几种方法都无法找出最好的BGP路由时，就可以使用BGP标识符来选择路由。在BGP进行交互的报文中，其首部都有一4字节的字段，叫做BGP标识符，记为BGP ID。这个字段被赋予一个无符号整数作为运行BGP的路由器的唯一标识符。具有多个接口的路由器有多个IP地址。BGP ID就使用该路由器的IP地址中数值最大的一个。

10. BGP-4的四种报文

BGP报文具有通用首部

4.6.5 路由器的构成

• 路由器工作在网络层，用于互连网络。

• 是互联网中的关键设备。

• 路由器的主要工作：转发分组。

  把从某个输入端口收到的分组，按照分组要去的目的地（即目的网络），把该分组从路由器的某个合适的输出端口转发给下一跳路由器。

1. 路由器的结构

“转发”和“路由选择”的区别：

• 转发

  • 根据转发表将用户的IP数据报从合适的端口转发出去。
  • 仅涉及到一个路由器。
  • 转发表是从路由表得出的。
  • 转发表必须包含完成转发功能所必需的信息，每一行必须包含从要到达的目的网络到输出端口和某些MAC地址信息（如下一跳的以太网地址）的映射。

• 路由选择

  • 按照路由选择算法，根据网络拓扑的变化情况，动态地改变所选择的路由，并由此构造出整个的路由表。
  • 涉及到很多路由器。
  • 路由表一般仅包含从目的网络到下一跳（用IP地址表示）的映射。

输入端口对线路上收到的分组的处理：

输出端口将交换结构传送来的分组发送到线路：

2. 交换结构

常用的交换方法有三种：通过存储器、通过总线、通过纵横交换结构。

通过存储器：

1. 当路由器的某个输入端口收到一个分组时，就用中断方式通知路由选择处理机。然后分组就从输入端口复制到存储器中。
2. 路由器处理机从分组首部提取目的地址，查找路由表，再将分组复制到合适的输出端口的缓存中。
3. 若存储器的带宽（读或写）为每秒M个分组，那么路由器的交换速率（即分组从输入端口传送到输出端口的速率）一定小于M/2。

通过总线：

1. 数据报从输入端口通过共享的总线直接传送到合适的输出端口，而不需要路由选择处理机的干预。
2. 当分组到达输入端口时若发现总线忙，则被阻塞而不能通过交换结构，在输入端口排队等待。
3. 因为每一个要转发的分组都要通过这一条总线，因此路由器的转发带宽就受总线速率的限制。

通过纵横交换结构：

• 常被称为互连网络。

1. 它有2N条总线，控制交叉节点可以使N个输入端口和N个输出端口相连接。

2. 当输入端口收到一个分组时，就将它发送到水平总线上。

3. 若通向输出端口的垂直总线空闲，则将垂直总线与水平总线接通，把该分组转发到这个输出端口。

4. 若输出端口已被占用，分组在输入端口排队等待。

• 特点：是一种无阻塞的交换结构，分组可以转发到任何一个输出端口，只要这个输出端口没有被别的分组占用。

---

参考资料：《计算机网络(第8版)》—— 谢希仁。