边界网关协议（BGP）

BGP 的简要历史

最小成本路由协议与图论中的最短路径问题密切相关，早在互联网出现之前，计算机科学领域就已经对该问题进行了研究。迪杰斯特拉算法诞生于 1956 年，贝尔曼 - 福特算法诞生于 1958 年。在开发早期路由协议时，设计者可以借鉴这些算法的思想。

早期，互联网是一个政府资助的项目，网络由美国国防部集中控制。当时还没有自治系统的概念，最小成本算法能够适应早期互联网较小的规模。最终，随着互联网的发展，政府将控制权移交给了不同的商业实体，这些实体不得不临时开发域间路由协议。

与早期的最小成本路由协议不同，每个自治系统都有自己私有策略的概念在计算机科学中没有先例。域间路由协议背后的思想是为了响应这些新兴互联网公司的需求而临时发展起来的。

BGP 创建于 1989-1995 年，其临时的开发过程意味着该协议并不完美。如果今天我们能从头重写这个协议，结果可能会有所不同。然而，事实证明该协议是有效且具有弹性的，至今仍是正在使用的域间路由协议（请记住，所有人都必须同意使用相同的域间路由协议，所以只有这一个）。

BGP 基于距离向量

回想一下，我们已经了解了两类域内路由算法：距离向量算法和链路状态算法。在设计 BGP 时，哪一类算法会是更好的设计起点呢？

请记住，在 BGP 中，我们需要尊重各个自治系统的隐私。如果我们使用链路状态协议，那么每个自治系统都必须将其所有策略告知整个网络，以便每个人都有足够的信息自行计算路由。

此外，在 BGP 中，我们需要尊重自治权，允许每个自治系统做出自己的策略决策。然而，链路状态协议要求所有人以某种一致的方式计算路由（例如，所有人都同意使用最小成本路径）。

链路状态算法不尊重自治系统的隐私或自治权，因此将链路状态作为设计 BGP 的基础是一个糟糕的选择。相比之下，距离向量允许每个自治系统自行决定接受 / 拒绝哪些路由以及通告哪些路由。而且，由于距离向量不是全局协议，每个自治系统不需要了解其他所有人的策略就能计算出有效的路由。

距离向量协议中的许多核心思想在 BGP 中仍然适用。我们发送和接收的通告仍然针对特定的目的地。就像在前面的章节中一样，我们会考虑针对单个目的地的通告和路由，但要知道该协议会同时针对多个目的地运行。

在距离向量协议和 BGP 中，每个自治系统仅使用从接收到的通告中获取的信息来计算路由，而无需了解网络拓扑的全局情况。此外，在这两种协议中，自治系统会不断发送和接收通告，直到所有人都收敛到一组路由上。

BGP 遵循与距离向量协议相同的核心思想，但在术语上略有变化。我们不说每个自治系统通告（announce/advertise）路由，而是说自治系统正在导出（exporting）路由。然后，每个自治系统监听通告并选择其首选路由，我们称之为导入（importing）路由。

距离向量是一个很好的起点，但它缺少什么呢？

距离向量协议旨在寻找最小成本路由，但在 BGP 中，我们希望路由的决策基于每个自治系统的个人策略。

基于策略的导入和导出

从高层次来看，为了支持策略，我们将改变导入和导出路由的规则。每个自治系统只会导出（通告）其喜欢的路由（根据其策略）。此外，在导入（选择）路由时，自治系统会根据策略选择最佳路由，而不是根据距离。

当一个自治系统接收到针对同一目的地的多个通告时，它不再选择最短路径，而是基于策略选择（导入）一条路由。

请记住，通告从目的地向外传播，而消息则向靠近目的地的方向转发（与通告的方向相反）。导入决策决定了一个自治系统将出站流量发送到哪里。例如，如果 S 接收到来自 A、B 和 C 的关于同一目的地的通告，S 的导入决策（选择 A、B 或 C）决定了该目的地的数据包将被转发到哪里。

在距离向量协议中，当我接收到一个通告并安装新路由时，我总是会将这个新路由通告给所有邻居。

现在，由于自治系统有了自己的策略，它们可以选择是否想要参与某条路由。如果一个自治系统有一条它可能不喜欢的路由，它现在可以选择不向某些邻居导出该路由。

例如，假设我的策略是我不想承载 C 的流量。这可能是出于经济原因，也可能是我做出的其他政策决定。当我接受一个通告并安装一条路由时，我可以不向 C 通告该路由，这是没问题的。

再次提醒，数据的流动方向与通告的方向相反。导出决策决定了一个自治系统愿意承载哪些入站流量。如果我导出一条路由，我就是同意参与这条路由，并允许其他人沿着这条路由将数据包转发给我。

这条规则的一个结果是，即使底层网络是连通的（任意两个节点之间都存在路径），也不能保证每个自治系统都能到达其他所有自治系统。在实践中，我们可以通过建立一些关于自治系统策略和自治系统图结构的约定来保证可达性。

高 - 雷克斯福德规则的实现

一般来说，BGP 支持任意策略，但任意策略并不能保证互联网是完全连通的（数据包可以从任何源到达任何目的地）。

回想一下，高 - 雷克斯福德规则（Gao-Rexford Rules）基于常见的基于金钱的导入和导出策略，实施了一套更具限制性的策略。没有人强制要求自治系统必须遵循这些规则。然而，如果自治系统同意遵循这些规则，我们就可以对互联网的连通性做出更有力的假设。

简要历史：这些规则以 20 世纪 90 年代 AT&T 的高立新（Lixin Gao）和詹妮弗・雷克斯福德（Jennifer Rexford）的名字命名。当时，每个自治系统都临时制定自己的策略。高和雷克斯福德通过调查自治系统的策略提出了这些规则，并利用它们证明了关于互联网的一些保证。

在导入路由时，高 - 雷克斯福德规则规定，自治系统优先导入由客户通告的路由，其次是由对等体通告的路由，最后是由提供商通告的路由。

在实践中，自治系统除了高 - 雷克斯福德规则外，还会实施额外的打破平局的规则。例如，如果我接收到来自两个客户的通告，我需要一些额外的打破平局的规则来选择其中一个。性能是一个常见的打破平局的因素，我们会选择带宽更高或路径更短的路由。

基于高 - 雷克斯福德规则，我们应该如何导出路径呢？回想一下，如果至少有一个邻居是客户，自治系统就同意参与一条路由。因此，自治系统应该只在导出的路由（如果被接受）在某一侧有邻居的情况下才通告该路由。

让我们逐一分析具体情况。

我接收并安装了一条来自客户的路由。这意味着该路由的下一跳是该客户。我应该向谁导出这条路由呢？我已经保证在一侧有一个客户向我付费，所以我可以向所有人（客户、提供商和对等体）导出这条路由。

我接收并安装了一条来自对等体的路由（下一跳是对等体）。我应该向谁导出这条路由呢？目前还没有人向我付费，所以我应该只向客户导出这条路由。如果我向接受该路由的对等体或提供商导出，那么我就创建了一条两侧都没有人向我付费的路由。

同样，如果我接收并安装了一条来自提供商的路由，我应该只向客户导出这条路由，因为我需要至少有一侧向我付费，而提供商不会付费。

高 - 雷克斯福德规则使我们能够证明以下陈述是正确的：假设自治系统图是分层的且无环，并且所有自治系统都遵循高 - 雷克斯福德规则，那么我们可以保证在稳定状态下的可达性和收敛性。

对该陈述中的具体术语进行分解：可达性意味着图中的任意两个自治系统都可以通信。收敛性意味着所有自治系统最终会停止更新它们的路径，网络将达到一个稳定状态，其中任意两个自治系统之间都存在有效的路径。“在稳定状态下” 意味着如果网络拓扑发生变化，路径可能需要一些时间来改变并再次达到稳定状态。

回想一下，分层意味着从任何自治系统开始，沿着层次结构向上（从客户到提供商）会到达一级自治系统（Tier 1 AS）。无环意味着不存在客户 - 提供商关系的循环（有向边）。

该陈述的证明要求所有人都遵循高 - 雷克斯福德规则。如果自治系统运行自己的任意策略，这些保证将不再成立。

改进：BGP 聚合目的地

我们还需要对距离向量协议进行另外两项改进。

在距离向量协议中，我们已经表明每个目的地都有一个唯一的地址，并且转发表将每个目的地映射到一个下一跳和距离。

在 BGP 中，每个自治系统由一个前缀标识，这表明该自治系统内的所有机器都共享相同的前缀。

这些转发表可能会变得非常大（想象一下，如果一个提供商有数百个客户），并且每个目的地都需要在单独的通告中描述。有没有办法更简洁地表示这个转发表呢？

为了提高可扩展性，BGP 允许自治系统将多个目的地聚合（aggregate）到一个转发表项中，并通告一个更通用的前缀，该前缀包含所有组合的目的地。

请注意，在实践中，BGP 对于所通告的前缀大小有约定。例如，自治系统不会为单个 IP 地址发布通告。24 位前缀（256 个地址的块）通常是所通告的最小地址单元。

改进：路径向量协议

在像距离向量这样的最小成本协议中，我们不必担心环路。每个路由器都在尝试寻找最小成本路由，并且根据定义，最小成本路由不会包含环路。

现在，由于每个自治系统都基于自己的偏好选择路由，我们失去了无环路的保证。例如，假设 B 喜欢经过 C 的路径，而 C 喜欢经过 B 的路径。我们就创建了一个路由环路！

为了解决这个问题，BGP 通告不会包含到目的地的距离，而是包含到目的地的完整自治系统路径。这将协议从距离向量协议改变为路径向量（path-vector）协议。

例如，在距离向量协议中，A 会通告：“我可以到达目的地，成本为 1。” 然后，B 会通告：“我可以到达目的地，成本为 2。”

在路径向量协议中，A 会通告：“我可以通过路径 [A] 到达目的地。” 然后，B 会通告：“我可以通过路径 [B, A] 到达目的地。”

通过这种改进，自治系统可以通过跟踪通告中的路径来确定所通告的路径是否包含环路。具体来说，如果我接收到一个通告，我只需要检查路径中是否包含我自己。如果包含，这将导致数据包被发送回我自己，从而产生环路，因此我会忽略该通告，不接受也不通告带有环路的路由。

注意：如果所有人都同意丢弃带有环路的路由，这就保证了通告不会包含环路。所通告的路由产生环路的唯一可能是，我看到一条已经包含我自己的路由，而我自己的加入正是产生环路的原因。

从距离向量到路径向量的转变也允许自治系统实施任意策略。在距离向量协议中，我可能有一个策略，比如 “尽可能避开 AS#2063”。如果我接收到一个 “我可以到达目的地，成本为 12” 的通告，我根本不知道所通告的路径是否经过 AS#2063。相反，如果通告包含完整路径，我可以在决定接受或拒绝之前检查路径是否经过 AS#2063。

注意：我们前面看到的常规 BGP 导入策略（优先选择通向客户的路由，其次是通向对等体的路由，最后是通向提供商的路由）只取决于下一跳，而不取决于整个路径。尽管如此，向路径向量的转变对于环路检测很有用，并且使我们能够将协议推广到支持任意策略。

末梢自治系统使用默认路由

有些自治系统不需要运行 BGP 来确定如何通过网络转发数据包。特别是，如果一个末梢自治系统（stub AS）只连接到一个提供商，那么所有发往其他自治系统的数据包都应该发送到该提供商。这个末梢自治系统可以为其他自治系统中的所有目的地安装一个单一的硬编码默认路由（default route）。

那么其他自治系统想要向末梢自治系统发送数据包怎么办呢？末梢自治系统可以要求提供商安装一条静态路由（static route），该路由告诉提供商如何向末梢自治系统发送数据包。现在，提供商可以运行 BGP 并向互联网的其他部分通告这条静态路由。末梢自治系统可以要求提供商硬编码这条静态路由，而末梢自治系统本身永远不需要运行 BGP，因为提供商正在代表它向末梢自治系统通告路由。

互联网中的大多数小型自治系统都是使用默认路由和静态路由的末梢自治系统。

末梢自治系统类似于域内路由中的终端主机。它们为自己的自治系统发送和接收数据包，但不自行转发数据包，也不参与路由过程。就像在域内路由中一样，我们通常会忽略末梢自治系统，只考虑实际参与 BGP 的中转自治系统（transit ASes）。

（注：文档部分内容可能由 AI 生成）