UCB CS168 笔记 Chapter 2 Routing

本文最后更新于 2026年4月10日 上午

Introduction to Routing

What is Routing?

假设A和B都连接到了互联网，但是A和B不直接相连。现在A想给B发一条信息，A该把信息发送哪，才能送到B？消息在过程中经过怎样的路径？这就是本章需要解决的核心问题。

具体而言，本章内容涉及：

  • 构建一个 Internet 模型，明确定义出 Routing Problem，找到影响因素
  • 探讨几种不同的路由协议，并探讨如何将其扩展到整个 Internet
  • 简要了解一下用于实现这些路由协议的实际硬件设备

Inter-Domain and Intra-Domain Routing

从我们之前设计别的（和计算机网络无关）的系统的经验来看，可以有一个中央系统，能够管理全球的路由器，这样负责数据包在全球的传输，但是考虑到互联网的庞大性和复杂性，这显然不现实。

于是，我们将利用 Internet is Network of Networks 这一特性：

  • 每个 Local Networks 有自己的路由协议，专门处理该网络内部的 packet forwarding
  • Intra-Domain 之间，建立跨网络的路由协议

由于 Local Networks 之间存在巨大差异，选用不同的路由协议是很正常的。用于 Local Networks 内的路由数据包协议叫做 intra-domain routing protocols, or interior gateway protocols (IGPs)，现实中的例子包括 OSPF, IS-IS。

同样的，用于在不同网络之间进行沟通的协议被称为 inter-domain routing protocols, or exterior gateway protocols (EGPs)。显然的，为了构建互联网，只能存在唯一一种通用的 EGP，那就是 BGP (Border Gateway Protocol)。

IGP和BGP的概念似乎很泾渭分明，但是实践中二者并非总是如此，比如BGP偶尔也在 inter-domain-networks 中使用。

Model for Intra-Domain Routing

Modeling the Network as a Graph

和标题一样字面意思。注意一点，一条link只能连两台机器

Routers and Hosts

在我们的简化模型中，将机器归类为以下两类：

  • End Hosts，连接到互联网，发送和接受数据的机器，不负责转发中间数据包
  • Routers，负责转发中间数据包，路由器不发送数据包，也不作为数据包的最终目的地

路由器有时也被称为交换机。路由器和交换机在历史上存在差异，但如今这两个术语可以互换使用。在这些笔记中，我们将尽可能使用"路由器"一词。

上面这段存疑，可能学校的课程不这么认为，待查证，TODO

End Hosts in Routing

终端主机通常不参与路由协议，因为他们不转发中间数据包。

终端主机经常通过单条链路连接到单个路由器，然后把所有出站信息发送给路由器，由路由器决定如何将数据包转发到最终的目的地，这种策略叫 default route of the end host。

设计 Routing Protocols 的时候，经常忽略终端主机。

Packets

在这一章我们对数据包的抽象进行一些简化：

  • 每个数据包包含：
    • 一个 Header with metadata
    • 一个 Application Layer Level 的 payload
  • 忽略 nested headers and multiple layers

重点关注 Header 的 Metadata 的目的地地址字段和源地址字段。

Addressing

我们需要一个协议来为网络上的每台机器分配地址。

后面再详细讨论（当然，我们知道是IP协议）。

Define the Routing Problem: 当路由器收到数据包时，它如何知道该将数据包转发至何处，以确保数据包最终能抵达目的地？

Network Topologies Change

随时都有可能有新的设备离开和加入互联网，链路也可能随时发生故障。

因此，我们设计的路由协议需要对这些变化的网络拓扑结构具有鲁棒性。

Routing Protocols are Distributed

这一点我觉得很重要，网络的拓扑结构随时会变化，但是因为互联网是分布式的，单个路由器不具备得知整个网络的拓扑结构的能力，所以我们设计的路由协议也必须是分布式的，这样才可以通过路由协议将新的网络拓扑信息传播给各个路由器。

每个路由器必须计算自己负责的部分答案，最后共同构成路由问题的全局解决方案。

另外，路由器的分布式特性也决定了：如果某个路由器故障，协议也需要负责协调别的路由器，以及负责这个路由器的恢复。

设计的时候需要考虑这个特性，主要是考虑可能丢包。

Routing States

Routing State 路由状态：每个路由器用来转发接收到的数据包的一组规则，这个规则可能正确可能错误，我们需要检查。

Bad Routing Strategies

比如我们随便说两个不良的 rules：随便转发、向所有邻居转发

Forwarding Tables

路由器内部存储一个表，对于每个可能的目的地，写下对应下一跳该去哪，这个叫做转发表。

通过记录转发表我们就有了一个完整的 Routing State，因为只要知道目的地我们就能知道怎么走。

数据包将被转发至的下一个中间路由器被称为下一跳。

在现实世界中，路由器通常将目的地映射到物理端口，而非下一跳。

这是一个微妙的区别，它反映了路由器实际上并不关心相邻路由器的身份。路由器需要做出的唯一决定是将数据包沿着某条线路发送出去，而不管这条线路连接的是谁。为了简化起见，在这些笔记中，我们将绘制转发表，将目的地映射到下一跳（而不是物理端口）。

容易看出使用转发表是一种 Destination-Based Forwarding

Routing vs. Forwarding

Routing:

  • 路由器之间相互通信，以确定如何填充各自转发表的过程。
  • 是一个全局过程，为了填充转发表需要了解网络的全局拓扑结构

Forwarding:

  • 路由器接受 packet，在转发表中查找合适的下一跳，并把 packet 发送出去的过程
  • 是一个本地过程，只需要知道转发表即可完成

Routing State Validity

评估路由状态的有效性：

  • 路由状态由每个路由器的转发表组成，这些转发表共同告诉我们数据包将如何通过网络传输
  • 有效性必须在全局上下文中评估，而不是在局部上下文中

定义：

当且仅当对于任何目的地，数据包都不会陷入死胡同或循环时，全局路由状态才是有效的。

  • 死胡同 dead end 是说数据包到达路由器，但是路由器不知道该转发到哪
  • 环路 比较好理解，转发表互相指向，但是这里需要注意end host不能是环路的一部分

这个条件是一个充要条件。

  • 必要性证明：
    • 如果存在 dead end，数据包在抵达 dead end 的时候就出不去了
    • 如果存在环路，数据包会被困在环路里面，也出不去
    • 所以，一个有效的路由状态不存在dead end 和环路
    • 必要性比较显然
  • 充分性证明：
    • 如果不存在环路，那么数据包就不可能两次到达同一个路由器
    • 如果不存在死胡同，那么数据包在到达终点之前不会停止
    • 由于路由器总数目有限，总有一天能到目的地

Directed Delivery Trees

这一小节主要就是讲，怎么从图的角度判断一个全局路由状态是有效的。

为了简化问题，让我们先只考虑单个目标终端主机，忽略所有其他终端主机。也就是说，这个图有且仅有一个出度为0的点。

那么，对于这个图，满足以下需求即可：

  • 有且仅有一个出度为0的点
  • 其余所有结点的出度为1
  • 连通，一棵以end host为根的生成树

Least-Cost Routing

简单来说，这个图存在正边权，我们希望数据包能够沿着成本最低的路径到达目的地。

成本（边权）是如何分配的？一般来说是网络运营商分配的。

需要注意的是，成本是路由器本地的，也就是说，路由器知道自己出站的成本，但路由器自动获知整个 network 里面其他链路的成本。符合我们”路由器不具备对整个网络拓扑的全局视图“的说法。

这里我们假设边权总是正整数，而且从A到B和从B到A的成本总是相同。

Static Routing

可以理解为手动硬编码，得到所有转发表，以此构建Routing。

虽然我们肯定不可能在所有路由器上都这样干，但是在实际操作中是经常使用的，可以理解为手动写转发表。

Distance-Vector Protocol

我觉得是这一章最重要的一节。

Algorithm Sketch

典型的 distance-vector protocol 是 RIP(Routing Information Protocol)，我们要设计的 D-V Protocol 和 RIP 有许多相似之处。

概括一下就是有两个核心要点：

对于每个目的地：

  • 如果得知了有一条通往该目的地的 route，更新转发表
  • 告知所有邻居 (Announcement / Advertisement)

Direction of Announcements and Messages

这里其实只是提醒一个易错点：

发送数据包的方向，和 Announcements 的方向，是相反的。

Rule 1: Bellman-Ford

  • 这一块原文非常啰嗦，这里直接提炼精华

开始A到R1的转发表一般是 static route 也就是硬编码出来的

R3和R4都能到A，但是走R4的成本更小，所以R5会选择走R4的路径写入转发表。

这里我们更新一下之前的说法：转发表加一列，同时记录已知的到达目的地的最少成本( = 通告成本加上到邻居的链路成本)。

注意：从形式上讲，转发表存储的是键值对，将每个目的地映射到一个包含下一跳和距离的二元组。为简化起见，我们将用三列表格来绘制。

这个操作就是Dijkstra算法中的”松弛“操作，Bellman-Ford比Dijkstra算法还简单一点，就是对所有边都松弛一遍。

不过，由于路由协议的限制，我们设计的是分布式、异步的协议。

  • 该协议是分布式的，因为我们并非要求单台计算机运行整个算法，而是让每个路由器在无法看到完整网络图的情况下，计算自身负责的部分答案（填充自身的转发表）
  • 该协议是异步的，因为所有路由器可以同时运行该算法，无需控制操作执行的顺序

总结：对于每个目的地：

  • 如果收到通往该目的地的路径的Advertisement，则在以下情况下更新表：
    • 目标不在表中
    • Advertisement里面的成本加上到邻居的Link成本，优于已知的最佳成本
  • 然后，Advertise所有邻居

Rule 2: Updates From Next-Hop

我们之前说的规则里面，但凡接收到去某个目的地比当前转发表里面所记录的cost更低的Advertisement，就要更新转发表；如果cost更高就忽略。

但是这个规则会出一个问题，假设我们本来转发表里面记录的最优路径发生了改变，本来途径的路由器的那条route的成本上涨了，我们是不得不接收这个信息的。

总之，在之前的规则上加一条：

总结：对于每个目的地：

  • 如果收到通往该目的地的路径的Advertisement，则在以下情况下更新表：
    • 目标不在表中
    • Advertisement里面的成本加上到邻居的Link成本，优于已知的最佳成本
    • Advertisement来自当前的next-hop
  • 然后，Advertise所有邻居

Rule 3: Resending

简单加上一条规则：存在一个Advertisement Interval，每隔这段时间，路由器就要重新发一次Advertisement，广播自己当前的信息。

这是为了防止Advertisement在传输过程中丢包，导致转发表永远无法构建的问题。

总结：对于每个目的地：

  • 如果收到通往该目的地的路径的Advertisement，则在以下情况下更新表：
    • 目标不在表中
    • Advertisement里面的成本加上到邻居的Link成本，优于已知的最佳成本
    • Advertisement来自当前的next-hop
  • 当路由表更新时，向所有邻居Advertise，并定期进行。

注意：Resending可以和之前的规则结合使用，即：

  • 每当转发表发生变化，路由器立刻advertise，这叫triggered updates
  • 按照间隔advertise仍进行，不受triggered updates的影响

基于当前的规则，当协议收敛之后，路由器仍然将定期发送Advertisements，但是都不会被接受，因为此时网络处于稳定状态，每个节点都已拥有最低成本路径。

Rule 4: Expiring

路由器可能会故障，故障的路由器无法广播它有问题这一事实，因此我们的转发表只能继续往坏掉的地方转发，导致丢包。

为了解决这一问题，为转发表里面每一个entry（表项/行）设置一个time to live(TTL)，这是一个倒计时，告诉我们这个条目还能保留多久。

如果我们从next-hop收到Advertisement，就可以将TTL重设为default；否则，删除此条目。

总结：对于每个目的地：

  • 如果收到通往该目的地的路径的Advertisement，则在以下情况下更新表：
    • 目标不在表中
    • Advertisement里面的成本加上到邻居的Link成本，优于已知的最佳成本
    • Advertisement来自当前的next-hop
  • 当路由表更新时，向所有邻居Advertise，并定期进行。
  • 如果路由表条目过期，则将其删除。

Rule 5: Poisoning Expired Routes

如果TTL比较长，然后路由器又死了，等待TTL过期要很久，对于系统而言有点浪费时间，而且在等待过程中往已经故障的路由器转发也会导致丢包。

解决方案：poison，当：

  • 某个node故障时

  • TTL过期时

明确通告该路径已失效。

Poison Announcement会这样描述：我是xx路由器，yy路由器距离我无穷远。这样的传播方式和一般的Advertisement完全相同。

就必须注意避免沿中毒路径转发数据包。如果某条路由表项显示通过 R1 可达 A 且开销为无穷大，这实际上意味着通过 R1 无法抵达 A。当我们收到目的地为 A 的数据包时，绝不能将其转发给 R1。

应用Rule 2，本来记录的next-hop的有效路径在失效之后可以被快速更新。

总结：对于每个目的地：

  • 如果收到通往该目的地的路径的Advertisement，则在以下情况下更新表：
    • 目标不在表中
    • Advertisement里面的成本加上到邻居的Link成本，优于已知的最佳成本
    • Advertisement来自当前的next-hop，包含poison announcements
  • 当路由表更新时，向所有邻居Advertise，并定期进行。
  • 如果路由表条目过期，则将其设为毒性并通告。

Rule 6A: Split Horizon

这个问题下我们暂时忽略poison，因为就算有也没什么区别，仍然会有这样的问题。

展示另一个问题：

R2本来的

To: Via: Cost:
A R1 2

因为TTL expired，被删除了*(其实这里就算是poison也没区别)*，然后R3由于Resending，会给R2发送通告：

于是，就出现了一个loop，这是不好的。

为了解决这个问题，我们提出Split Horizon，即绝不将路由信息回传给提供该路由的人。

所谓回传，就是这里的Forwarding Table里面的Via属性，不往这里回传。

总结：对于每个目的地：

  • 如果收到通往该目的地的路径的Advertisement，则在以下情况下更新表：
    • 目标不在表中
    • Advertisement里面的成本加上到邻居的Link成本，优于已知的最佳成本
    • Advertisement来自当前的next-hop，包含poison announcements
  • 当路由表更新时，向所有邻居Advertise，并定期进行。
    • 但不要向next-hop回传advertisement
  • 如果路由表条目过期，则将其设为毒性并通告。

Rule 6B: Poison Reverse

这是另一种避免产生loop的方法，注意不能和Split Horizon同时使用。

在Poison Reverse的规则下，会明确回传Poison Announcement。

回到之前这个情形：

  • 如果是Split Horizon，R3什么也不会发
  • 如果是Poison Reverse，就会这样：

同样可以制止环路的产生。

总结：对于每个目的地：

  • 如果收到通往该目的地的路径的Advertisement，则在以下情况下更新表：
    • 目标不在表中
    • Advertisement里面的成本加上到邻居的Link成本，优于已知的最佳成本
    • Advertisement来自当前的next-hop，包含poison announcements
  • 当路由表更新时，向所有邻居Advertise，并定期进行。
    • 但不要向next-hop回传advertisement
    • 或者，向next-hop回传poison advertisement
  • 如果路由表条目过期，则将其设为毒性并通告。

务必注意Split Horizon和Poison Reverse只能二选一。

Rule 7: Count to Infinity

Split Horizon和Poison Reverse只能避免长度为2的环路，但是我们现在的Routing Protocol仍然可能涉及长度$\geq 3$的路由环路。

这个图的例子的展示比较复杂，这里简单解释一下：

  • 本来是一个R1-R2-R3-A的steady state
  • A-R3的link断掉了，根据Rule 5，R3修改自己的转发表，并给R1和R2释放poison announcements
  • 结果就这么个announcement，在传向R1的过程中dropped了
  • 虽然R3之后还可能再发消息（Rule 3），但是我们这里考虑所有可能发生的问题都在这之前发生了
  • 于是R1继续释放虚假的正常announcements，导致R2的毒化entry被cost更小、但是已经失效的annoucements覆盖了（为什么不向R3发送，因为split horizon）
  • 然后R2收到消息，继续向R3发送
  • ...以此进入循环，而且cost会不断增加，增加的部分是每个路由器出站所需的cost

为什么split horizon不发挥作用？因为R1只被限制了不能往R3但是没说不能往R2发。

解决这个问题的方法其实很粗暴，设置一个最大成本值，超过这个的都被视为是无穷（毒化entry），比如RIP协议中，这个值是16。

所以，上面的情况是环路会存在一段时间，然后又被全部毒化了。

总结：对于每个目的地：

  • 如果收到通往该目的地的路径的Advertisement，则在以下情况下更新表：
    • 目标不在表中
    • Advertisement里面的成本加上到邻居的Link成本，优于已知的最佳成本
    • Advertisement来自当前的next-hop，包含poison announcements
  • 当路由表更新时，向所有邻居Advertise，并定期进行。
    • 但不要向next-hop回传advertisement
    • 或者，向next-hop回传poison advertisement
    • 任何≥给定值的成本都被视为无穷大
  • 如果路由表条目过期，则将其设为毒性并通告。

Eventful Updates

标题的意思是”事件驱动的更新“.

其实只是一个总结

路由器发送通告的情况：

  1. 转发表发生变化时（triggered update），如：
    • 接受新的通告时
    • 添加新链路时（e.g. static route）
    • 链路中断时
  2. 定期发送
  3. 过期后（被毒化替代）发送

其中triggered update其实是一种优化，去掉之后Routing Protocol也能正常运行。

Link-State Protocols

另一种interior gateway protocols

IS-IS和OSPF是Link-State Protocl的两个例子

Link-State Protocol不同于Distance-Vector Protocol，执行的是本地计算：

  • 每个节点独立
  • 自己计算完整的解决方案，不使用来自邻居的计算结果

一句话概括：每个路由器学习完整的网络拓扑图，然后在该图上运行最短路径算法来填充转发表。

我们分两步设计这个协议：

  1. 如何计算最短路
  2. 如何学习整个网络图

Computing Paths

最短路算法有很多，用Dijkstra还是Bellman-Ford还是别的都可以。

主要问题是：每个路由器只能控制当前转发，无法影响next-hop的行为，假设next-hop计算出来的path不同，可能会导致环路。

为了避免这个问题，我们需要保证所有路由器做出的转发决策之间彼此兼容，需要满足以下条件：

  • 所有路由器知晓的网络拓扑图相同
  • 所有路由器找的都是最短路
  • 边权均为正（防止负权回路）
  • 所有路由器使用相同的平局决胜规则，即如果有多条成本相同的最短路，所有路由器都会选择相同的那一条

Learning About Graph Topology

首先向所有邻居发送”问候“信息：

问候信息需定期重新发送（类似DVP），如果一个邻居一段时间没发送，就认为它已经消失。

还需要广播自己的邻居是谁，而且以这张图为例，收到R2广播自己的邻居是R1和R3之后，R1和R3也要把R2的邻居是谁广播出去；别的路由器同理。

这就被称为flooding information across the network，这里我们也需要定期重发消息。

Avoiding Infinite Flooding

在这个结构里面，两台路由器会无限发送信息，持续浪费带宽。

请注意，这与为可靠性而定期重发消息不同。为了确保可靠性，我们可能每 5 秒重发一次消息。而在这个无限循环中，路由器正以最高速率（例如每秒数百万次）接收并重发重复的公告。

如果存在环路，那么广播数量的增长甚至会是指数级的，后果更严重。

为了解决这个问题：

  • 当首次看到一条消息时：
    • 将其发送给所有邻居
    • 并记录我们已经看到过这条消息
  • 如果再次看到相同的消息，就不再重复发送

为了唯一标识一条消息，我们可以引入时间戳（或其他针对每条消息唯一的计数器）。

Convergence

一旦网络拓扑发生变化，网络可能需要一些时间才能再次收敛。

需要先等待变化被检测到，然后还要等待新信息在网络中传播，再等待路由器计算转发表。

在这段等待时间里面，处于无效的路由状态，因为没有完整的网络拓扑图。

根据具体实现，距离向量协议的收敛速度可能较慢。如果网络发生变化，我们必须等待邻居重新计算并重新通告路径，然后才能更新自己的转发表。接着，我们所有的邻居又必须等待我们，依此类推。相比之下，在链路状态协议中，所有节点都可以快速泛洪新信息并同时重新计算。

链路状态协议适用于小型本地网络，但难以扩展到全球互联网。

在实践中，大多数网络会结合使用距离向量协议和链路状态协议。

Addressing

Scaling Routing

我们迄今为止一直在用这样的A, B, C, D来给目的地编号。然而，若想把路由协议扩展到整个互联网上，这显然是不现实的，因为：

  • 如果运行Distance-Vector Protocol，那么就需要announce全世界的每台主机
  • 如果运行Link-State Protocol，每台路由器都需要了解整个互联网的拓扑结构

所以，我们将扩展(Scaling)路由，使用更合适的编址方案。

IP Addressing

互联网在每一层都采用不同的编址方案，在Layer 3(Network Layer)采用的是IP Addressing。

这里不多解释了。

Hierarchical Addressing

之前我们说Internet = Network of Networks

这个图很直观，简单概括一下思想和好处：

  • 把几个 local networks 编号，用作第一个数字：网络标识符

  • local networks内的routers也编号，写在第二个数字：主机标识符

  • 对于Network 2中的R9，假设想去Network 1中的任何主机，转发表中只需要写1*，别的同理

  • 这样可以：

    • 简化转发表

    • 如果别的local networks中的网络拓扑结构发生变化，比如本来想去1.2，但是1.2离开了，不影响R9的转发表

      实际上，本地网络内的变化（例如新主机加入网络）比网络间的变化（例如新地下电缆铺设）发生得更频繁，因此本地变化仅影响本地转发表是件好事。

  • 对于比如Local Network内的任意一台路由器，转发表中对于本地网络内的路由器需要详细写出next-hop，但是对于本地网络外的就只需要用通配符`x.*就好了

Default Routes

上一小节我们知道了搭配通配符*可以用entry代表一个范围，这一思路可以进一步扩展。

以这张图为例，我们发现R2往外走，除了直接相连的2.4 2.5，其余都必须走R3，那直接写成*.*的形式。

而对于R4，转发表可能就长这样：

大多数主机只有一个硬编码的默认路由。例如，主机 2.4 的转发表中只有一个条目，指示将所有内容发送到 R2。实际上，您的家用计算机只有一个条目，指示将所有内容发送到您的家庭路由器。这就是为什么主机不需要参与路由协议。

Assigning Hierarchical IP Addresses: Classful Addressing

这一小节主要是介绍了一种已经被淘汰的编址方案：

  • 前面字段表明如何分段
  • Network字段给 local networks 编址
  • Hosts字段给域内主机编址

Assigning Hierarchical IP Addresses: CIDR

**CIDR(Classless Inter-Domain Routing) **是现代互联网仍在使用的方案，允许位数任意设定。

Multi-Layered Hierarchical Assignment

这一小节的主要内容，就是层级可以有很多（不止Networks-Hosts两层）。

这里以IPv4为例，由ICANN这个组织进行管理，ICANN 将地址块分配给代表特定国家或地区的区域互联网注册管理机构（RIR）。

比如，ICANN 将 1101 开头的所有地址分配给 ARIN（北美），然后ARIN再把后面的部分分给各种组织 / ISP，比如1101 11001开头的所有地址分配给 AT&T，At&T再继续往下分配。

这里想分配多少位是随意的。

Writing IP Addresses

点分四组表示法：每8位写成0~255之间的整数，中间用.连接。

想要表示范围有两种方式：斜线表示法 slash notation 和子网掩码 netmask。

slash notation

先写出固定的前缀，然后为所有剩余未固定的bit位补上 0，并将得到的 32 位值转换为点分四组形式的 IP 地址。接着，在斜线后面，我们写上固定bits位的数量。

比如，前缀是11000000，那么补零得到11000000 00000000 00000000 00000000，写成点分四组就是192.0.0.0，又因为前8位是固定的，就写成192.0.0.0/8。

斜线表示法有时看起来会有点令人困惑，因为我们使用的是任意的 8 位划分并用十进制书写数字。例如，8 位前缀 11000000 和 12 位前缀 11000000 0000 会被写成 192.0.0.0/8 和 192.0.0.0/12（相同的 IP 地址代表不同的范围）。再举一个例子，如果我拥有 4 位前缀 1100，我可以分配 5 位前缀 11001。作为范围，这些被写成 192.0.0.0/4 和 200.0.0.0/5。乍一看，并不清楚第二个范围实际上是第一个范围的子集，我们必须写出比特位来确认。

netmask

子网掩码是斜线表示法的斜线后面的部分的替代品。

要写一个子网掩码，我们为所有固定比特位写 1，为所有非固定比特位写 0，并将结果转换为点分四组。

比如，仍然以之前的192.0.0.0/8举例，因为前8位是固定的，那么子网掩码就是11111111 00000000 00000000 00000000，也就是255.0.0.0。

子网掩码在计算机内部常用，因为IP地址和子网掩码按位与，所有主机位都将被清零，只有网络位会保留下来。

Aggregating Routes with CIDR

如同Hierarchical Addressing和Default Route两节中所讲的聚合，这一节讲解如何用CIDR进行聚合。

其实道理很简单：

如图即可说明了。

Multi-Homing

对于Stanford，有两个Homing（两个上层Host）。

那么我们之前对AT&T做的合并就失效了，因为还可能走R7。

这个时候我们引入最长前缀匹配，也就是查询转发表的时候，总是先找最具体的那一个（前缀更长的）。

Router Hardware

What Do Routers Do?

  • 通过运行路由协议来填充转发表
  • 当数据包到达时，查看目标IP地址，选择合适的链路转发数据包

Data, Control, Management Planes

路由器的软件+硬件组件，从概念上可以分成三个平面：

  • 数据平面
    • 主要负责转发数据包
    • 在本地运行，无需与其他路由器协调
  • 控制平面
    • 主要负责与其他路由器通信并运行路由协议
  • 管理平面
    • 用于告知路由器该做什么，并查看它们正在做什么
    • 系统通过管理平面和人类交互，从而配置和监控路由器：每条链路应分配多少成本？应运行哪种路由协议？每条链路上承载了多少流量？路由器的任何物理组件是否出现故障？

数据层面运行非常快（硬件的速度），而由于数据包到达的频率远高于网络拓扑变化的频率，控制平面则用于更复杂的任务，运行相对慢；管理平面运行最慢

数据平面和控制平面实时运行，分别以纳秒级（数据）和秒级（控制）的时延接收和处理数据包。相比之下，管理平面的操作时间通常在数十秒到数百秒之间。

What's Inside a Router?

Chassis：机箱；Linecard：线卡

所有physical ports之间彼此相连，每个端口既可以接收也可以转发数据包。

当然，构成一个完全图的效率过低，我们采用fabric of wires去把linecards连接在一起，每块linecard配有CPU，以faciliate the connections.

除了所有linecards之外，还有一个独立的controller card with its own CPU，用于与其他路由器通信并执行路由协议，运行算法计算路径，编写转发表。

仔细体会这三张图：

Types of Packets

  • user packet: 转发芯片首先读取header中的目标字段，然后读转发表，选择合适的端口，如果目标端口在不同的linecard上，packet就沿着fabric (交换结构) 发送到相应的linecard，然后发送出去

  • control-plane traffic: 目的地是路由器本身，比如运行路由协议时候的announcements；路由器接收到此类packet的时候，转发芯片将其上传至controller card，然后controller card 的 CPU 再处理这些信息

  • punt traffic: 翻译是“转交流量”，本质是user packet，但是需要特殊处理：

    例如，如果我们收到一个 TTL 为 1 的数据包，该数据包已过期，我们不应转发它。我们可能还需要向发送者发送错误消息。当路由器收到转交数据包时，转发芯片会将该数据包“转交”给控制器卡进行特殊处理

Scaling Routers

为什么路由器要拆分成这种特定的架构？

本质是因为路由器对于不同的任务有不同的需求，对于转发的速度要求极高，但是别的可能就要求没那么高。

比如，针对转发数据包，在数据平面内有专门的优化。

这也就是所谓的"due to the scale"，因为单个路由器转发数据包的量极大。

Linecard Functionality

  1. 接收到数据包
    • PHY部分：将 analog signal 解析成 bits
    • MAC部分：执行链路层tasks
    • 这些都是在硬件里面实现的
  2. 处理数据包
    • 理解header
    • 找next-hop
    • 更新数据包：减小TTL，更新checksum等
  3. 沿着fabric转发数据包

为了加速上述的操作，转发芯片十分特化，基本只能执行这些有限的任务。如果需要完成转发芯片不支持的功能，就将其转发到控制卡上的CPU。

Packet Queuing

  • only one queue for a router
  • drop the packet if the queue is full
  • FIFO

Efficient Forwarding Table Lookup

回忆一下之前的内容，我们读取转发表是要求“前缀最长匹配”的。

使用Trie 字典树来实现比较高效的读取

Model for Inter-Domain Routing

Defining Autonomous Systems (AS)

定义AS来形式化 Local Network 的概念：AS是由同一运营商管理的一个或多个本地网络。

Types of ASes

  • stub AS: 仅为其本地网络中的主机提供互联网连接，仅代表其内部的主机发送和接收数据包，不在不同 AS 之间转发数据包
  • transit AS：可以转发和接收数据包，比如各种运营商

Inter-Domain Topology Is Defined by Business Relationships

AS之间的关系：

  • customer，消费流量
  • provider，提供流量
  • peer，互相发送流量，大致相等，不互相付费

AS Graph with Business Relationships

有向边从提供商指向客户，无向边连接两个对等体。

需要注意的是，箭头的方向并不表示数据包的传输方向。实际上，即使沿着有向边，数据包也可以双向传输。客户通常向提供商付费，以获得向互联网其他部分发送数据包以及从互联网其他部分接收数据包的能力。

AS Graphs are Acyclic

AS图无有向环路。这是因为环路会让资金流回自身，在现实中不合理。

Provider Hierarchy and Tier 1 ASes

可以把AS图排列，让所有箭头都指向下方，这样AS图自然会分层。

最高层的是 Tier 1 AS。这种现实中对应的实体比如中国电信。

Gao-Rexford Rules for Routing Policies

在实践中，大多数自治系统会根据一些标准惯例来设置策略，这些惯例被称为高-雷克斯福德规则。这些惯例基于一个假设：现实世界中的组织喜欢赚钱，而不喜欢亏钱。

具体而言，两条规则：

  1. 有多条路径可选时，优先级：客户>对等方>提供商
  2. AS没有义务提供服务，因此不再向所有邻居宣告路由、允许任何人通过AS转发数据包，而只宣告那些我能获得转发报酬的路由

Border Gateway Protocol

唯一在使用的域间路由协议。

BGM based on Distance-Vector Protocol

如标题所说，但是有点区别。

DVP里面的Announcement，在BGP里面被分为了export和import。

为什么？在 BGP 中，我们需要尊重各个AS的隐私。如果我们使用链路状态协议，那么每个自治系统都必须向整个网络公开其策略，以便每个人都能拥有完整的知识来自行计算路由。

这里就存在Policy-Based Import and Export.

每个AS仅会导出（通告）其根据策略偏好的路由。同时，在导入（选择）路由时，自治系统将依据策略而非距离来选择最佳路由。

我们使用Gao-Rexford Rule。

简单概括一下：

  • AS优先导入客户通告的路由，其次是同级通告的路由，最后是提供商通告的路由
  • AS只有在至少一个邻居是客户时，才会同意参与某条路由——AS仅应在接受该路由后，确保路由的一侧有邻居时，才对外通告该路由

给一个例子：

把D换成Customer或者Peer都会得到不同的结果，考虑赚钱即可。

Route Advertised by Export Route to
Customer Everyone
Peer Customer
Provider Customer

Some Modifications

BGP允许AS将多个目的地聚合成单个转发表entry

BGP里面每个AS都是靠自身偏好选择路径，可能会出现Loop。

为了避免这个问题，BGP 通告将不再包含到达目的地的距离，而是包含到达目的地的完整 AS 路径。这使协议从Distance-Vector Protocol转变为Path-Vector Protocol。

然后，AS就可以依据通告的内容判断是否存在环路。

BGP Implementation and Issues

iBGP and eBGP

i: internal, e: external

简单概括一下核心概念：

eBGP会话发生在来自不同AS的两个路由器之间

iBGP会话发生在同一AS内的两个路由器之间

图里面的A B G，被称为BGP speakers

这些speakers和外部沟通，然后把外部的信息传给AS内部，这个走的是另一个协议，是域间协议的一部分。

这样，每个路由器有两个表，一个是内部的表，一个是外部AS的表。

Hot Potato Routing

这里有两条路，从X发送的通往Verizon的包走哪里？

通过IGP计算出离F还是I更近，然后选择最近的出口出去，以此来尽量利用他人的带宽，节省自己的钱。

MED

如果两个出口距离相等，我们需要决胜规则。

出口AS可以宣布对某一路由的偏好高于另一路由，这个偏好用MED来衡量，越低越好。

因此这里选J出去。

Import Policy Priority

当收到同一目的地的多个通告时，按以下顺序根据这些决胜规则选择路径：

  1. Gao-Rexford rules, customer>peer>provider
  2. shorter path （AS层面的，即经过更少的AS的）
  3. 选择离出口路由器更近的 (hot-potato)
  4. 选择MED值更低的
  5. 任意选择

互联网中的路径往往是不对称的。如果两台主机来回发送数据包，一个方向的路径可能与另一个方向的路径不同。

BGP Attributes

这里只讲3个：

LOCAL PREFERENCE 属性在特定自治系统（AS）内部编码了 Gao-Rexford 导入规则。自治系统可以为更偏好的路由（例如来自客户的路由）分配较高数值，为较不偏好的路由（例如来自提供商的路由）分配较低数值。该属性具有局部性，仅通过 iBGP 消息传递。在 eBGP 通告中不会将此属性发送给其他自治系统，因为其他自治系统无需了解本自治系统的偏好设置。

通过LOCAL PERF可以区分是provider还是customer还是peer。

ASPATH就是之前说的，整个的路径，这个是全局的。

还有MED属性，之前有说，不解释了。

IP Header

简单概述

这一块感觉看起来云里雾里的，日后可以进行更多的补充，TODO，这里只是做一些简单的概述。

首先，为了所有设备能够解析数据包，报头包括：

  • IP Version （ipv4 ipv6），4位
  • header length，因为报头长度不固定，4位
  • 数据包长度 16位
  • 目标IP地址，32位，为了转发数据包
  • 协议值，指示使用TCP还是UDP，8位，6代表TCP，17代表UDP，IP Header之后是TCP/UDP Header
  • 源IP地址，为了发送回复，32位

为了处理特殊情况，还包括以下字段：

  • TTL，防止无限循环，8位
  • checksum，16位
    • checksum只针对fixed的部分，不检查Options and PAD之类不固定的部分

这两个字段只针对IP Header，无法检查Payload的异常。

路由器可以执行分片，The identification (16-bit), flags (3-bit), and offset (13-bit) fields in the header 是用于实现分片的。

还有一些别的，但是在现代已经停止使用了。

IPv6的改变

  1. 取消了checksum

    支持包含校验和的理由是：如果一个数据包损坏且未被检测到，损坏的数据包会继续发送，浪费带宽。包含校验和可以确保数据包被丢弃，不会浪费带宽在损坏的数据包上。在现代，带宽不再是瓶颈，因此校验和不再必要，即使一些损坏的数据包通过网络传输，也不会对性能产生巨大影响。

  2. 取消分片机制，如果 IPv6 数据包对于特定链路而言过大，路由器将丢弃该数据包；分片的职责交给了终端主机而不是路由器。

  3. 在 IPv6 中，头部长度是固定的，因此没有header length 字段。

还有一些别的，日后补充吧，TODO。