域间路由模型

域间路由

前面我们提到，路由是在由多个网络组成的网络中进行的。我们已经了解了距离向量协议和链路状态协议，它们可用于实现域内路由，使数据包能够在本地网络内发送。

在本节中，我们将构建一个模型，用于定义域间路由协议，该协议能够在不同的本地网络之间发送数据包。我们还将了解域间路由协议和域内路由协议如何结合，使数据包能够发送到任何网络中的任何主机。

定义自治系统

我们可以通过定义自治系统（AS） 来形式化本地网络的概念，自治系统是由同一运营商管理的一个或多个本地网络。例如，在谷歌这样的公司中，可能有一个供员工计算机使用的本地网络，还有一个供数据中心使用的本地网络，但这两个网络都由同一家公司控制。运营商可以部署单一的域内路由协议，在这些本地网络中的任何机器之间发送消息。有时，“域（domain）” 一词被非正式地用来指代 AS，但该术语也用于其他协议，因此我们尽可能使用 AS。

为了考虑自治系统之间的数据包路由，我们可以抽象掉 AS 内的所有单个路由器和主机，将 AS 视为一个单一实体。然后，我们可以绘制一个图，其中每个节点代表一个 AS，两个 AS 之间的边代表它们之间的连接。这个图有时被称为域间拓扑或AS 图。

自治系统的简要历史

在现实生活中，一个名为互联网编号分配机构（IANA）的组织管理着全球所有存在于互联网中的自治系统列表。要成为一个 AS，必须向该组织注册并获得唯一的自治系统编号（ASN）。

趣闻：在早期，IANA 由 Jon Postel 一个人手动管理。这意味着世界上任何想要注册新 AS 的人都必须获得他的批准。

如今，已有超过 9 万个自治系统，其中美国拥有的 AS 数量在所有国家中最多。

趣闻：加州大学伯克利分校的 ASN 是 25，考虑到有这么多 ASN，这个数字非常小。这反映出加州大学伯克利分校在互联网历史早期（20 世纪 80 年代）就获得了其 ASN。

AS 的类型

回想一下，在为域内路由建模时，我们区分了终端主机和路由器。在域间路由中，我们也会做类似的区分，定义两种类型的 AS。

Stub 自治系统的存在只是为其本地网络中的主机提供互联网连接。Stub AS 仅代表其内部的主机发送和接收数据包，不转发不同 AS 之间的数据包。这类似于我们域内路由模型中的终端主机，它们只发送和接收自己的数据包，不转发其他人的数据包。

Stub AS 的现实例子包括非互联网公司（例如，为员工提供连接的银行）或大学（例如，为学生和员工提供连接的加州大学伯克利分校）。这些组织不负责承载来自其他组织的互联网流量。世界上绝大多数 AS 都是 Stub AS。

相比之下，转接自治系统代表其他 AS 转发数据包。转接 AS 可以通过接收和转发数据包，在两个不同的 AS 之间承载数据包。

转接 AS 对应于那些业务包括向其他组织出售互联网连接的现实公司。转接 AS 的现实例子包括 AT&T 和 Verizon，这些公司可以付费为你提供互联网连接。一些转接 AS（如 AT&T）是全球性的，在世界各地都有基础设施。其他一些可能局限于特定地区，如 Sonic，这是一家仅转发往返加利福尼亚州流量的互联网服务提供商。

请注意，转接 AS 仍然可以包含发送和接收自己数据包的终端主机。尽管如此，转接 AS 类似于我们域内路由模型中的路由器，接收其他用户的数据包并代表用户转发它们。

我们在这些笔记中使用的是 Stub 和转接 AS 的模型，尽管在现实生活中，分类可能不太明确。例如，像谷歌、微软和亚马逊这样的大型科技公司控制着庞大的 AS，其承载的流量与转接 AS 一样多（甚至更多）。由于它们的主要作用是承载往返于其服务的流量（例如，接收谷歌搜索请求并发送搜索结果），它们可以被归类为 Stub AS。然而，近年来，这些公司也开始提供 AS 之间的流量承载服务，因此它们也可以有理由被归类为转接 AS。

域间拓扑由商业关系定义

在我们的域间拓扑中，如果两个 AS 交换流量，我们就在它们之间画一条边。是什么导致两个现实生活中的组织（如当地银行和 Verizon）同意交换流量呢？AS 中的边由 AS 之间的现实世界商业关系定义。

一对 AS 可能存在两种关系。

一对 AS 可能涉及客户 - 提供商关系。在现实生活中，客户付费购买服务，而提供商以金钱为交换提供连接。例如，当地银行 AS 可能是客户，向提供商 Verizon 支付互联网服务费用。

一对 AS 也可能涉及对等关系。两个对等 AS 通常向对方发送大致相等数量的流量。在现实生活中，两个 AS 可以通过签订公司间的法律合同成为对等方。通常，两个对等方同意不向对方支付连接服务费用，只要两个方向发送的流量大致相等。

带有商业关系的 AS 图

我们可以通过在图中添加箭头来将这些关系绘制到 AS 图中。有向边从提供商指向客户。无向边连接两个对等方。请注意，图中可以同时包含有向边和无向边（并非所有边都需要有箭头）。

图中的 Stub AS 只是客户。它们有入边，表示为它们提供连接的对象。然而，它们没有任何出边，因为它们不向其他方提供连接。

相比之下，图中的转接 AS 是提供商。它们的出箭头表示它们正在向其他组织出售连接。

请注意，箭头的方向并没有告诉我们数据包发送的方向。事实上，即使是沿着有向边，数据包也可以双向发送。客户通常向提供商付费，以获得向互联网其余部分发送数据包和从互联网其余部分接收数据包的能力。

AS 图是无环的

客户 - 提供商关系图是无环的。该图不包含任何由有向边组成的循环。

这种无环特性的存在是因为循环在现实世界中会带来不合理的影响。在现实生活中，循环意味着 A 向 B 付费，B 向 C 付费，然后 C 向 A 付费，资金从某人那里流回自己是不合理的。此外，这种循环意味着 A 为 C 提供服务，C 为 B 提供服务，B 为 A 提供服务。某人向自己提供连接也是不合理的。

打个比方，想象一下你向加州大学伯克利分校支付学费上课，然后加州大学伯克利分校向加州大学系统支付学费上课，接着加州大学系统向你支付学费上课。这种商业关系是毫无意义的！

请注意，无环特性仅适用于客户 - 提供商关系。对等关系形成循环是可以的。例如，A-B、B-C 和 C-A 都是对等关系是没问题的。它们之间没有人互相发送资金，因此不会有不明确的商业关系。

提供商层级和一级 AS

图的无环特性的一个结果是，我们可以形成提供商的层级结构。换句话说，我们可以安排节点，使所有箭头都向下指向。Stub AS 在底部，提供商在顶部。服务从较高节点流向较低节点。较低节点向较高节点支付资金。

在层级结构的最顶端，是一级自治系统，它们没有提供商（没有入边）。每个一级 AS 都与其他每个一级 AS 存在对等关系。

这种层级结构的一个结果是：每个非一级 AS 都至少有一个提供商（入边）。这在现实生活中是合理的，因为你必须向某人付费才能获得连接。

在这个层级结构中，从任何 AS 开始，沿着提供商的上行链，总会到达一个一级 AS。这在现实生活中也是合理的。一级 AS 彼此对等，这就是整个互联网能够连接在一起的原因（而不是像两个断开的子图那样，代表两个独立的互联网，你只能与自己所在一半的主机通信）。为了保证有一条路径到达图中的每个其他 AS，每个 AS 都必须有一条上行路径，最终通向一个一级 AS。

TODO - 图表

现实世界中一级 AS 的一些例子包括 AT&T 和 Verizon（美国）、法国电信和意大利电信（欧洲）以及日本电报电话公司（日本）。现实中有大约 20 个 AS 是一级或接近一级的。这些一级 AS 通常拥有跨越多个大陆的基础设施（例如，海底电缆）。

AS 图的层级结构由现实世界的商业和政治动机定义。理论上，AS 图可以是一棵树的形式，根部有一个单一的一级 AS，为所有 Stub AS 提供服务。然而，这意味着一个现实实体控制着全世界的互联网访问，这在政治上可能是不可取的。

基于策略的路由

回想一下，在域内路由中，我们的目标是找到有效的路径（无环路和无死胡同）和良好的路径（成本最低）。

在域间路由中，我们仍然希望路径是有效的。然而，与域内路由不同（在域内路由中，一个路由器与另一个路由器没有什么特别之处），每个自治系统都有自己的商业目标以及与其他 AS 的关系（例如，客户、提供商、对等方）。因此，我们需要重新定义 “良好”，以反映 AS 的现实世界商业目标和偏好。

为了允许每个 AS 以与其现实世界目标兼容的方式承载流量，我们的路由协议将允许每个 AS 设置自己的策略。然后，协议计算的路径应该正确尊重每个 AS 的策略。

理论上，AS 可以设置任何类型的策略，尽管确实存在标准约定（我们接下来会讨论）。以下是 AS 可以设置的一些策略示例：

• “我不想通过我的网络承载 AS#2046 的流量。”（定义我将如何处理来自其他 AS 的流量。）

• “我更希望我的流量由 AS#10 而不是 AS#4 承载。”（定义其他 AS 应该如何处理我的流量。）

• “除非万不得已，否则不要将我的流量通过 AS#54 发送。”

• “我在工作日更喜欢 AS#12，在周末更喜欢 AS#13。”（策略可以随时间变化！）

路由协议并不关心 AS 为什么有这些偏好。也许我拒绝承载来自 AS#2046 的流量是因为它是竞争对手公司，但协议不需要知道这一点。

到目前为止，我们的最小成本路由协议无法支持这些策略。最小成本是一个全局最小化问题，每个路由器都在尝试解决相同的问题。相比之下，在基于策略的路由中，每个 AS 只关心自己的策略，没有一个所有人都在合作解决的全局问题。

路由策略的高 - 雷克斯福德规则

尽管我们的路由协议允许每个 AS 设置任何任意策略，但实际上，大多数 AS 根据一些标准约定来设置它们的策略，这些约定被称为高 - 雷克斯福德规则。这些约定基于这样一种假设：现实世界的组织喜欢赚钱，不喜欢赔钱。

AS 通常遵循两个主要规则。首先，当一个 AS 有多个路由选择时，它更愿意将数据包转发到最有利可图的下一跳。具体来说，AS 更喜欢下一跳是客户的路由。如果没有这样的路由，AS 更喜欢下一跳是对等方的路由。只有在迫不得已（没有更好的路由）的情况下，AS 才会选择下一跳是提供商的路由。

这个原则决定了 AS 选择的路由。你可以将这个原则视为距离向量协议中路径选择的基于偏好的版本。我不是选择我所知道的最短路由，而是选择下一跳能让我赚钱（客户最好）、省钱（如果没有客户，那么是对等方）并且避免赔钱（如果没有客户或对等方，那么是提供商）的路由。

其次，AS 只有在获得报酬的情况下才会承载流量。AS 没有动力进行无偿劳动。这个原则决定了 AS 愿意参与的路径。你可以将这个原则视为距离向量协议中宣布路径的更严格版本。我不会向每个邻居广告路由（允许任何人通过我转发数据包），而是只广告那些我能获得报酬来转发数据包的路由。

这个第二个原则的一个结果是：作为一个 AS，我承载的流量应该来自客户或去往客户。换句话说，对于任何通过我的路由，我的一个邻居必须是客户。

让我们详细分析所有具体情况。

两个邻居都是客户的路由是好的，因为我从这两个客户那里获得报酬来转发数据包。

同样，一个邻居是客户、另一个邻居是对等方的路由也是好的，因为尽管对等方不向我付费，但客户会付费。

一个邻居是客户、另一个邻居是提供商的路由是好的。起初，这似乎是不好的，因为客户向我付费，然后我向提供商付费。难道我可能不赚钱甚至赔钱吗？这可能是真的，但如果我们不参与这些路由，我们就会成为一个没有客户的无用 AS。AS 的职责是为其用户提供连接，参与这些客户 - AS - 提供商路由可以解锁通往互联网其余部分的更多路由。

两个邻居都是对等方的路由是不好的，因为双方都没有付费让我转发数据包。

更一般地说，对等方不提供其他对等方之间的转接。从层级结构的角度来看，路径不应在同一级别停留多个跃点。

一个邻居是对等方、另一个邻居是提供商的路由也是不好的，因为同样，双方都没有付费让我转发数据包。

更一般地说，如果一个 AS 有对等链路，该链路将只承载往返于其自己客户的流量。换句话说，当数据包通过该对等链路到达 B 时，B 唯一有利可图的选择是将数据包转发给客户（而不是提供商，也不是另一个对等方）。同样，来自客户的数据包可以通过对等链路转发（客户付费），但来自提供商和对等方的数据包不能通过对等链路转发（没有人付费）。

同样，两个邻居都是提供商的路由是不好的，因为我必须向双方付费来转发数据包，而没有人付费给我做这件事。

高 - 雷克斯福德规则的示例

选择路由的策略（客户最好，提供商最差）和宣布路由的策略（只宣布和参与其中一个邻居是客户的路由）将在我们修改后的协议中用于计算尊重每个 AS 策略的路由。我们还没有说如何计算路由，但给定一条路由，我们可以检查它是否满足这两个策略。

在这个例子中，假设 D（一个 Stub AS）中的一台计算机想要与 E（另一个 Stub AS）中的一台计算机通信。D 和 E 可能想要交换消息（请记住，箭头代表客户 / 提供商关系，而不是数据包的方向）。

流量的一个可能路径是 D、B、A、C、E（E 到 D 的消息路径相反）。

在这条路径中，谁向谁付费？由于流量沿着 D-B 链路发送，客户（D）必须向提供商（B）付费。同样，E 必须向 C 付费，B 和 C 都必须向 A 付费。

转接 AS A、B 和 C 会同意宣布并参与这条路由吗？让我们检查它们的每个邻居。

A 在这条路径上的邻居都是客户，所以 A 在赚钱，认为这条路径是好的。

B 的邻居是客户（D）和提供商（A）。B 从客户（D）那里赚钱，认为这条路径是好的。（请记住，有一个客户邻居和一个提供商邻居的路径是好的，即使 AS 的净利润为 0，因为它们能提供更好的连接。）

同样，C 至少有一个客户邻居（E），所以它也认为这条路由是好的。

除了 B 和 C 都向 A 付费之外，它们可能会选择建立对等关系，这会导致 AS 图发生变化：

现在，流量的另一个可能路径是 D、B、C、E。现在，D 仍然需要向 B 付费，E 仍然需要向 C 付费。然而，B 和 C 不再需要向 A 付费，并且它们彼此也不付费（对等关系）。

同样，我们可以检查这条路径上的转接 AS（即 B 和 C）是否会同意宣布并参与这条路由。B 的邻居是客户（D）和提供商（C）。B 从客户（D）那里赚钱，认为这条路径是好的。同样，C 至少有一个客户邻居（E），所以 C 也认为这条路由是好的。

我们刚刚推断出有两条良好的路径可用于从 D 向 E 发送消息。现在，B 必须决定是通过路径 B-A-C-E 转发，还是通过路径 B-C-E 转发。根据我们的第一个原则，B 更喜欢最有利可图的路径（而不是最短路径）。在 B-A-C-E 中，下一跳是提供商 A（我们必须向其付费），而在 B-C-E 中，下一跳是对等方 C（无需付费）。因此，B 会选择通过 C 的路径，最终路径为 D-B-C-E。

注意：看起来 B 和 C 通过额外的对等关系节省了资金，那么为什么不是每个 AS 都建立对等关系来节省资金呢？在现实生活中，建立链路还需要安装物理基础设施（例如，在地下铺设电缆），因此建立 AS 之间的新关系需要权衡成本与更便宜路由带来的好处。

路由是无谷的

更一般地说，AS 图中的路径总是无谷的。

从层级结构的角度来看，如果一条路径包含通过对等链路的横向跃点，那么紧接的下一跳需要下坡到客户。下一跳不能再次横向（两个邻居都是对等方），也不能上坡到提供商（邻居是对等方和提供商）。

从层级结构的角度来看，如果一条路径包含从提供商到客户的下坡跃点，那么紧接的下一跳必须继续下坡到其某个客户。下一跳不能再次横向（邻居是提供商和对等方），也不能上坡（邻居都是提供商）。

如果下坡链路之后必须是另一条下坡链路，那么我们可以得出结论：一旦路径中有一条下坡链路，所有后续链路也必须是下坡的。“谷” 是指先下坡然后又开始上坡的路径。路径不能包含谷，因为一旦开始下坡，就必须一直下坡到目的地。

总之，我们得出的规则如下（不过，从尊重 AS 的资金偏好的角度理解它们比死记硬背更好）：

• 上坡链路之后可以是对等链路、下坡链路或另一条上坡链路。（如果前一跳向我付费，我很乐意将数据包转发给任何人。）

• 对等链路之后只能是下坡链路。（如果前一跳没有向我付费，我需要下一跳是向我付费的客户。）

• 下坡链路之后只能是下坡链路。（如果前一跳是我付费的提供商，我需要下一跳是向我付费的客户。）

这些规则意味着路由总是无谷且单峰的。一条路由可以开始于 0 个或多个上坡链路。最终，它会到达一个单峰，并经过 0 个或 1 个对等链路。然后，路由必须开始一路下坡到目的地（不再有横向或上坡移动）。

路径不能有谷（先下坡然后又上坡）。此外，路径只能在峰值处有横向移动。一旦进行了横向移动，就必须转向并下坡。不能继续横向或上坡移动。

AS 希望自治和隐私

在设计用于计算域间路由的协议时，我们的协议应该尊重每个 AS 的自治和隐私。

AS 希望自治，即自由选择自己的任意策略，无需与其他 AS 协调，也无需担心协议允许哪些策略。实际上，策略通常遵循我们描述的基于资金的原则，但协议不应强迫 AS 遵循任何特定策略。

AS 也希望隐私。AS 不希望必须向网络中的其他方明确透露它们的偏好和策略。例如，AS 不需要明确告诉所有人其邻居是对等方、客户还是提供商。这反映了现实世界的商业策略。作为一家公司，你可能不想向竞争对手透露你的客户和提供商的信息。

请注意，我们对隐私的定义是 AS 不需要明确透露它们的策略。实际上，AS 仍然需要与网络的其余部分协调，以确定通过网络的路径，因此某种程度的信息泄露是不可避免的。存在逆向工程技术来追踪数据包通过网络的路由。

例如，网络中的其他人不可避免地会发现数据包正在采用什么路由。然而，我们的协议不应强迫 AS 告诉全世界 “我更喜欢这条路径而不是另一条路径”。我们也不应强迫 AS 披露它们的提供商、对等方和客户是谁。

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