我们刚刚了解到OSPF是AS内路由协议的一个示例。在同一AS内的源和目的地之间路由数据包时，数据包所遵循的路由完全由AS内路由协议决定。然而，要通过多个ASS路由数据包，例如从廷巴克图的智能手机到硅谷数据中心的服务器，我们需要一个**自治系统间路由协议（inter-autonomous system routing protocol）**。由于AS间路由协议涉及多个AS之间的协调，因此通信的AS必须运行相同的AS间路由协议。事实上，在Internet中，所有AS都运行相同的AS间路由协议，称为**边界网关协议（Border Gateway Protocol）**，通常称为**BGP**[RFC 4271；Stewart 1999]。<br />BGP可以说是所有Internet协议中最重要的(唯一的另一个竞争者是我们在第4.3节中研究的IP协议)，因为它是将Internet中的数千个ISP粘合在一起的协议。我们很快就会看到，BGP是一种**分散的异步协议（decentralized and asynchronous protocol）**，类似于第5.2.2节所述的距离矢量路由。虽然BGP是一个复杂且具有挑战性的协议，但要深入理解Internet，我们需要熟悉它的基础和操作。我们花在学习BGP上的时间将是非常值得的。
5.4.1 BGP的角色 The Role of BGP
要理解BGP的职责，请考虑AS和该AS中的任意路由器。回想一下，每台路由器都有一个转发表，它在将到达的数据包转发到出站路由器链路的过程中扮演核心角色。我们了解到，对于同一AS内的目的地，路由器转发表中的条目由AS的AS内路由协议确定。但是，如果目的地不在AS中，情况又会怎样呢？这正是BGP出手相救的地方。
在BGP中，数据包路由到的不是特定的目的地址，而是CIDR化的前缀，每个前缀代表一个子网或一组子网。在BGP世界中，目的地可能采用138.16.68/22的形式，在本例中包括1024个IP地址。因此，路由器的转发表将具有(x，I)形式的条目，其中x是前缀(例如138.16.68/22)，I是路由器接口之一的端口号。
作为AS间路由协议，BGP为每台路由器提供了一种实现以下目的的方法：
- 从相邻AS获取前缀可达性信息（Obtain prefix reachability information from neighboring ASs）。特别是，BGP允许每个子网向Internet的其余部分通告其存在。一个子网尖叫着，“我存在，我在这里”，BGP确保互联网上的所有路由器都知道这个子网。如果没有BGP，每个子网都将是一个孤岛—孤立、未知、互联网的其他部分无法到达。
- 确定通向前缀的“最佳”路由（Determine the “best” routes to the prefixes）。路由器可能会获知通向特定前缀的两条或多条不同路由。为了确定最佳路由，路由器将在本地运行BGP路由选择过程(使用通过相邻路由器获得的前缀可达性信息)。最佳路由将根据策略和可达性信息确定。
5.4.2 通告BGP路由信息 Advertising BGP Route Information
请考虑图5.8所示的网络。我们可以看到，这个简单的网络有三个自治系统：AS1、AS2和AS3。如图所示，AS3包含一个前缀为x的子网。对于每个AS，每台路由器要么是网关路由器（gateway router），要么是内部路由器（internal router）。网关路由器是位于AS边缘的路由器，它直接连接到其他AS中的一个或多个路由器。内部路由器仅连接到其自身AS内的主机和路由器。例如，在AS1中，路由器1c是网关路由器；路由器1a、1b和1d是内部路由器。
Figure 5.8 ♦ Network with three autonomous systems. AS3 includes a subnet with prefix x
图5.8♦三个自治系统的网络。AS3包括前缀为x的子网
让我们考虑一下将前缀x的可达性信息通告给所有路由器的任务，如图5.8所示。从高层次上讲，这是直截了当的。首先，AS3向AS2发送BGP消息，说明x存在并且在AS3中；让我们将此消息表示为“AS3 x”。然后，AS2向AS1发送一条BGP报文，说明x存在，您可以通过先通过AS2然后转到AS3来到达x；让我们将该消息表示为“AS2 AS3 x”。以这种方式，每个自治系统不仅将了解x的存在，而且还将了解通向x的自治系统的路径。
尽管上段中关于通告BGP可达性信息的讨论应该能让大家了解大体概念，但这并不准确，因为自治系统实际上并不彼此发送报文，而是路由器彼此发送报文。为了理解这一点，现在让我们重新检查图5.8中的示例。在BGP协议中，两台路由器通过179端口的半永久TCP连接交换路由信息。每个这样的TCP连接以及通过该连接发送的所有BGP报文称为BGP连接（BGP connection）。此外，跨越两个AS的BGP连接称为外部BGP(external BGP，eBGP)连接，同一路由器之间的BGP会话称为内部BGP(internal BGP，iBGP)连接。图5.8中网络的BGP连接示例如图5.9所示。通常对于直接连接不同AS中的网关路由器的每个链路都有一个eBGP连接；因此，在图5.9中，在网关路由器1c和2a之间存在eBGP连接，并且在网关路由器2c和3a之间存在eBGP连接。 
Figure 5.9 ♦ eBGP and iBGP connections
图5.9♦iBGP和eBGP连接
每个AS内的路由器之间也有iBGP连接。特别地，图5.9显示了AS内部每对路由器的一个BGP连接的通用配置，在每个AS中创建了TCP连接的网格。在图5.9中，eBGP连接用长划线显示；iBGP连接用短划线显示。请注意，iBGP连接并不总是对应于物理链路。
为了传播可达性信息，使用iBGP和eBGP会话。再次考虑将前缀x的可达性信息通告给AS1和AS2中的所有路由器。在该过程中，网关路由器3a首先向网关路由器2c发送eBGP消息“AS3 x”。然后，网关路由器2c向AS2中的所有其他路由器(包括网关路由器2a)发送iBGP消息“AS3 x”。然后，网关路由器2a向网关路由器1c发送eBGP消息“AS2 AS3 x”。最后，网关路由器1c使用iBGP向AS1中的所有路由器发送消息“AS2 AS3 x”。此过程完成后，AS1和AS2中的每台路由器都会知道x的存在，并且还会知道通向x的AS路径。
当然，在真实网络中，从给定路由器到给定目的地可能有许多不同的路径，每条路径都通过不同的AS序列。例如，考虑图5.10中的网络，它是图5.8中的原始网络，具有从路由器1d到路由器3d的额外物理链路。在这种情况下，从AS1到x有两条路径：通过路由器1c的路径“AS2 AS3 x”；以及通过路由器1d的新路径“AS3 x”。
Figure 5.10 ♦ Network augmented with peering link between AS1 and AS3
图5.10♦AS1和AS3之间增加了对等链路的网络
5.4.3 确定最佳路由 Determining the Best Routes
正如我们刚刚了解到的，从给定路由器到目的子网可能有许多路径。事实上，在Internet中，路由器通常会收到有关数十条不同可能路径的可达性信息。路由器如何在这些路径中进行选择(然后相应地配置其转发表)？
在解决这个关键问题之前，我们需要介绍更多的BGP术语。当路由器通过BGP连接发布前缀时，该前缀包含BGP的一些属性（attributes）。在BGP术语中，前缀及其属性称为路由（route）。其中两个更重要的属性是AS-PATH和NEXT-HOP。AS-PATH属性包含通告通过的AS列表，正如我们在上面的示例中看到的那样。为了生成AS-PATH值，当向AS传递前缀时，AS会将自己的ASN添加到AS-PATH中已有的列表中。例如，在图5.10中，有两条从AS1到子网x的路由：一条使用AS路径“AS2 AS3”；另一条使用AS路径“A3”。BGP路由器还使用AS-PATH属性来检测和防止循环通告；具体地说，如果路由器发现自己的AS包含在路径列表中，它将拒绝通告。
通过提供AS间和AS内路由协议之间的关键链路，NEXT-HOP属性具有微妙但重要的用途。NEXT-HOP是开始AS路径的路由器接口的IP地址。要深入了解该属性，让我们再次参考图5.10。如图5.10所示，通过AS2从AS1到x的路由“AS2 AS3 x”的NEXT-HOP属性是路由器2a上左侧接口的IP地址。绕过AS2的从AS1到x的路由“AS3 x”的NEXT-HOP属性是路由器3d最左侧接口的IP地址。总之，在这个玩具示例中，AS1中的每个路由器都知道前缀x的两条BGP路由：
路由器2a最左侧接口的IP地址；AS2 AS3；x
路由器3d最左侧接口的IP地址；AS3；x
这里，每个BGP路由被写成包含三个组成部分的列表：NEXT-HOP；AS-PATH；目的地前缀。实际上，BGP路由包含额外的属性，我们将暂时忽略这些属性。请注意，NEXT-HOP属性是不属于AS1的路由器的IP地址；但是，包含此IP地址的子网直接连接到AS1。
热土豆路由 Hot Potato Routing
现在我们终于可以精确地讨论BGP路由算法了。我们将从最简单的路由算法之一开始，即热土豆路由（hot potato routing）。
请考虑图5.10中网络中的路由器1b。如上所述，此路由器将了解两个可能的BGP路由以添加前缀x。在热土豆路由中，(从所有可能的路由中)选择的路由是到开始该路由的NEXT-HOP路由器的开销最低的路由。在该示例中，路由器1b将参考其AS内路由信息，以找到到NEXT-HOP路由器2a的最低成本的AS内路径和到NEXT-HOP路由器3d的最低成本的AS内路径，然后选择具有这些最低成本路径中的最小路径的路由。例如，假设成本定义为遍历的链路数。则从路由器1b到路由器2a的最低成本是2，从路由器1b到路由器3d的最低成本是3，因此将选择路由器2a。然后，路由器1b将查询其转发表(由其AS内算法配置)，并找到位于到路由器2a的最低开销路径上的接口I。然后，它将(x，I)添加到其转发表。
图5.11总结了在路由器转发表中添加outside-AS前缀以实现热土豆路由的步骤。重要的是要注意，当将AS外部前缀添加到转发表中时，使用AS间路由协议(BGP)和AS内路由协议(例如，OSPF)。
Figure 5.11 ♦ Steps in adding outside-AS destination in a router’s forwarding table
图5.11♦在路由器转发表中添加外部AS目的地的步骤
（从AS间协议了解到子网x可通过多个网关到达->使用AS内协议中的路由信息确定到每个网关的最低开销路径的开销->热土豆路由：选择开销最小的网关->根据转发表确定通向成本最低的网关的接口I，在转发表中输入(x，I)。）
热土豆路由背后的想法是让路由器1b尽可能快地(更具体地说，以尽可能低的成本)将数据包从其上取出，而不必担心在ITS之外的路径的剩余部分到目的地的开销。在“热土豆路由”的名称中，数据包类似于你手中烧焦的热土豆。因为它是灼热的，你想尽快把它传给另一个人(另一个人)。因此，热土豆路由是一种自私的算法-它试图降低其自身AS中的成本，而忽略其AS之外的端到端成本的其他组成部分。请注意，使用热土豆路由时，同一AS中的两台路由器可能会选择两条不同的AS路径到达相同的前缀。例如，我们刚才看到路由器1b会通过AS2发送数据包到达x。但是，路由器1d会绕过AS2，直接向AS3发送数据包到达x。
路由选择算法 Route-Selection Algorithm
实际上，BGP使用的算法比热土豆路由更复杂，但仍然包含热土豆路由。对于任何给定的目的地前缀，BGP路由选择算法的输入是路由器已获知并接受的到该前缀的所有路由的集合。如果只有一条这样的路由，那么BGP显然会选择该路由。如果有两个或多个路由指向同一前缀，则BGP会按顺序调用以下消除规则，直到剩余一条路由：
- 为路由分配本地优先级值（local preference value）作为其属性之一(除了AS-PATH和NEXT-HOP属性之外)。路由的本地优先级可以由路由器设置，也可以从同一AS中的另一台路由器获取。本地优先级属性的值是完全由AS的网络管理员决定的策略决定。(我们将很快详细讨论BGP策略问题。)。选择具有最高本地优先级值的路由。
- 从剩余的路由(都具有相同的最高本地优先级值)中，选择具有最短AS路径的路由。如果此规则是路由选择的唯一规则，则BGP将使用DV算法来确定路径，其中距离度量使用AS跳数（hops）而不是路由器跳数。
- 从剩余的路由(都具有相同的最高本地优先级值和相同的AS路径长度)中，使用热土豆路由，即选择具有最接近的NEXT-HOP路由器的路由。
- 如果仍有多条路由，路由器将使用BGP标识符来选择路由；请参阅[Stewart 1999]。
作为示例，让我们再次考虑图5.10中的路由器1b。回想一下，正好有两条到达前缀x的BGP路由，一条通过AS2，另一条绕过AS2。还记得，如果使用其自身的热土豆路由，则BGP将通过AS2将数据包路由到前缀x。但在上述路由选择算法中，规则2在规则3之前应用，导致BGP选择绕过AS2的路由，因为该路由具有较短的AS路径。因此，我们可以看到，使用上面的路由选择算法，BGP不再是一个自私的算法-它首先寻找具有较短AS路径的路由(从而可能减少端到端延迟)。
如上所述，BGP是Internet AS间路由的事实标准。查看各种BGP路由表(大型！)的内容。从第1级ISP中的路由器提取，请参阅http://www.routeviews.org。BGP路由表通常包含超过50万条路由(即前缀和相应的属性)。有关BGP路由表的大小和特征的统计信息请参见[Huston 2019b]。
5.4.4 IP-选播 IP-Anycast
除了作为Internet的AS间路由协议外，BGP还经常用于实现IP任播服务[RFC 1546，RFC 7094]，该服务通常在DNS中使用。为了推动IP任播，考虑到在许多应用中，我们感兴趣的是(1)在许多不同分散的地理位置的不同服务器上复制相同的内容，以及(2)让每个用户从最近的服务器访问内容。例如，CDN可能会在不同国家的服务器上复制视频和其他对象。同样，DNS系统可以在世界各地的DNS服务器上复制DNS记录。当用户想要访问该复制的内容时，希望将用户指向具有该复制的内容的“最近的”服务器。BGP的路由选择算法为这样做提供了一种简单而自然的机制。
为了让我们的讨论更加具体，让我们来描述一下CDN可能如何使用IP-Anycast。如图5.12所示，在IP任播配置阶段，CDN公司为其每台服务器分配相同的IP地址，并使用标准BGP从每台服务器通告该IP地址。当BGP路由器接收到该IP地址的多个路由通告时，它会将这些通告视为提供了通往同一物理位置的不同路径(实际上，通告是针对通往不同物理位置的不同路径)。在配置其路由表时，每台路由器将在本地使用BGP路由选择算法来挑选到该IP地址的“最佳”路由(例如，根据AS-HOP计数确定的最近路由)。例如，如果一个BGP路由(对应于一个位置)距离路由器只有一个AS跳，而所有其他BGP路由(对应于其他位置)是两个或更多个AS跳，则BGP路由器将选择将数据包路由到距离路由器一跳的位置。在最初的BGP地址通告阶段之后，CDN可以完成其主要工作，即分发内容。当客户端请求视频时，CDN会将地理位置分散的服务器使用的公共IP地址返回给客户端，无论客户端位于何处。当客户端向该IP地址发送请求时，Internet路由器会将请求数据包转发到BGP路由选择算法定义的“最近”服务器。
Figure 5.12 ♦ Using IP-anycast to bring users to the closest CDN server
图5.12♦CDN使用IP-Anycast将用户带到最近的服务器
尽管上面的CDN示例很好地说明了如何使用IP任播，但在实践中，CDN通常选择不使用IP任播，因为BGP路由更改可能会导致同一TCP连接的不同数据包到达Web服务器的不同实例。但是IP任播被DNS系统广泛使用来将DNS查询定向到最近的根DNS服务器。回想一下第2.4节，当前有13个IP地址用于根DNS服务器。但与这些地址中的每个地址对应的是多个DNS根服务器，其中一些地址有100多个DNS根服务器，分散在世界的各个角落。当DNS查询被发送到这13个IP地址中的一个时，IP任播被用来将查询路由到负责该地址的最近的DNS根服务器。[LI 2018]展示了互联网任播、使用、性能和挑战的最新测量结果。
5.4.5 路由策略 Routing Policy
当路由器选择到达目的地的路由时，AS路由策略可以凌驾于所有其他考虑因素之上，例如最短AS路径或热土豆路由。实际上，在路由选择算法中，首先根据本地优先级属性选择路由，该属性的值由本地AS的策略固定。
让我们用一个简单的例子来说明BGP路由策略的一些基本概念。图5.13显示了六个互连的自治系统：A、B、C、W、X和Y。请务必注意，A、B、C、W、X和Y是AS，而不是路由器。让我们假设自治系统W、X和Y是接入ISP，A、B和C是主干提供商网络。我们还假设A、B和C直接相互发送流量，并向它们的客户网络提供完整的BGP信息。所有进入ISP接入网络的流量都必须发往该网络，所有离开ISP接入网络的流量都必须源自该网络。W和Y显然是接入的ISP。X是一个多宿主接入ISP（multi-homed access ISP），因为它通过两个不同的提供商连接到网络的其余部分(这种情况在实践中变得越来越常见)。但是，与W和Y一样，X本身必须是进出X的所有流量的源/目的地。但是，如何实现和实施此末节网络行为？如何阻止X在B和C之间转发流量？这可以通过控制通告BGP路由的方式轻松实现。具体地说，如果X(向其邻居B和C)通告它除了自己之外没有通往任何其它目的地的路径，它将充当接入ISP网络。也就是说，即使X可能知道到达网络Y的路径，例如XCY，它也不会将该路径通告给B。因为B不知道X具有到达Y的路径，所以B永远不会通过X转发目的地为Y(或C)的流量。这个简单的例子说明了如何使用选择性路由通告策略（selective route advertisement policy）来实现客户/提供商路由关系。
Figure 5.13 ♦ A simple BGP policy scenario
图5.13♦简单BGP策略场景
接下来，让我们将重点放在提供商网络上，比如B。假设B(从A)了解到A具有到W的路径AW，B因此可以将路由AW安装到其路由信息库中。显然，B还想将路径BAW通告给其客户X，以便X知道它可以通过B路由到W。但是，B是否应该通告路径BAW到C？如果它这样做了，那么C可以通过BAW将流量路由到W。如果A、B和C都是主干提供商，那么B可能会正确地认为它不应该负担传输A和C之间的流量(和成本！)。B可能会正确地认为这是A和C的工作(以及成本！)。为了确保C可以通过A和C之间的直接连接来往于A的客户，目前还没有官方标准来管理主干ISP如何在它们之间路由。然而，商业ISP遵循的一条经验法则是，流经ISP主干网络的任何流量必须在该ISP的客户网络中有源或目的地(或两者都有)；否则，流量将在ISP的网络上免费通行。单独的对等协议(将管理上面提出的问题)通常在成对的ISP之间谈判，而且通常是保密的；[Huston 1999a；Huston 2012]提供了一个关于对等协议的有趣讨论。有关路由策略如何反映ISP之间的商业关系的详细说明，请参阅[高2001；Dmitiropoulos 2007]。有关从ISP角度讨论BGP路由策略的信息，请参阅[CAESAR 2005B]。
这就是我们对BGP的简要介绍。了解BGP非常重要，因为它在Internet中起着核心作用。我们鼓励您查看参考文献[Stewart 1999；Huston 2019a；Labovitz 1997；Halabi 2000；Huitema 1998；Gao 2001；Feamster 2004；Caesar 2005B；Li 2007]以了解更多关于BGP的信息。
PRINCIPLES IN PRACTICE 实践中的原则 WHY ARE THERE DIFFERENT INTER-AS AND INTRA-AS ROUTING PROTOCOLS? 为什么AS间和AS内存在不同的路由协议？ 在研究了当今Internet中部署的特定AS间和AS内路由协议的详细信息之后，让我们总结一下我们可能首先会问到的关于这些协议的最基本的问题(希望您一直都在想这一点，并且没有因为树而迷失森林！)：为什么AS间和AS内路由使用不同的协议？ 这个问题的答案是AS内部路由目标和AS之间路由目标之间的差异的核心：
- 策略（Policy）。在AS中，策略问题占主导地位。重要的是，源自给定AS的流量不能通过另一特定AS。类似地，给定AS很可能想要控制它在其他AS之间承载什么中转流量。我们已经看到，BGP承载路径属性并提供路由信息的受控分发，从而可以做出这种基于策略的路由决策。在AS内，所有内容名义上都处于相同的管理控制之下，因此策略问题在AS内选择路由时扮演的角色要小得多。
- 规模（Scale）。路由算法及其数据结构的规模是AS间路由中的一个关键问题，它能够处理去往/在大量网络之间的路由。在AS中，规模不是什么问题。首先，如果单个ISP变得太大，总是可以将其分成两个AS并在两个新AS之间执行AS间路由。(回想一下，OSPF允许通过将AS拆分成区域来构建这样的层次结构。)
- 性能（Performance）。因为AS间路由是以策略为导向的，所以使用的路由的质量(例如，性能)通常是次要的(即，满足特定策略标准的较长或更昂贵的路由很可能会接管较短但不符合该标准的路由)。事实上，我们看到在AS中，甚至没有与路由相关的开销(除了跳数)的概念。然而，在单个AS中，这样的策略问题就不那么重要了，这使得路由可以更多地关注在路由上实现的性能级别。
5.4.6 把所有信息拼凑在一起: 获得网络存在感 Putting the Pieces Together: Obtaining Internet Presence
虽然这个小节不是关于边界网关协议本身，它集合了许多我们已经看到的协议和概念，包括IP编址、DNS和BGP。
假设您刚刚创建了一家拥有多个服务器的小公司，其中包括描述公司产品和服务的公共Web服务器、员工从中获取电子邮件的邮件服务器和DNS服务器。当然，您希望全世界都能访问您的网站，以便了解您令人兴奋的产品和服务。此外，您还希望您的员工能够向世界各地的潜在客户发送和接收电子邮件。
要实现这些目标，您首先需要获得Internet连接，这是通过与当地ISP签订合同并连接到该ISP来实现的。您的公司将有一台网关路由器（gateway router），它将连接到您当地ISP中的路由器。此连接可以是通过现有电话基础设施的DSL连接，也可以是到ISP路由器的租用线路，也可以是第1章中介绍的许多其他接入解决方案之一。您当地的ISP还将为您提供IP地址范围，例如，由256个地址组成的/24地址范围。一旦您有了物理连接和IP地址范围，您就可以将其中一个IP地址(在您的地址范围内)分配给您的Web服务器，一个分配给您的邮件服务器，一个分配给您的DNS服务器，一个分配给您的网关路由器，并将其他IP地址分配给您公司网络中的其他服务器和网络设备。
除了与ISP签约外，您还需要与互联网注册机构签约为您的公司获取域名（domain name），如第二章所述。例如，如果您的公司的名称是Xanadu Inc.，您自然会尝试获得域名xanadu.com。您的公司还必须获得DNS系统中的存在。具体地说，由于外部人员希望联系您的DNS服务器以获取服务器的IP地址，因此您还需要向您的注册商提供您的DNS服务器的IP地址。然后，您的注册商会将您的DNS服务器(域名和相应的IP地址)条目放入.com顶级域服务器，如第2章所述。完成此步骤后，任何知道您的域名的用户(例如，xanadu.com)都可以通过DNS系统获取您的DNS服务器的IP地址。
为了使人们能够发现您的Web服务器的IP地址，您需要在DNS服务器中包含将Web服务器的主机名(例如www.xanadu.com)映射到其IP地址的条目。您将希望公司中的其他公开可用的服务器(包括您的邮件服务器)具有类似的条目。通过这种方式，如果Alice想要浏览您的Web服务器，DNS系统将联系您的DNS服务器，找到您的Web服务器的IP地址，并将其提供给Alice。然后，Alice可以直接与您的Web服务器建立TCP连接。
然而，还有另外一个必要和关键的步骤，以允许来自世界各地的外来者访问您的Web服务器。考虑一下当知道Web服务器的IP地址的Alice向该IP地址发送IP数据报(例如，TCP SYN段)时会发生什么。此数据报将通过Internet路由，访问许多不同AS中的一系列路由器，最终到达您的Web服务器。当任何一台路由器收到该数据报时，它将在其转发表中查找条目，以确定它应该在哪个传出端口上转发该数据报。因此，每台路由器都需要知道您公司的/24前缀(或某个聚合（aggregate）条目)的存在。路由器如何知道您公司的前缀？正如我们刚刚看到的，它从BGP开始意识到这一点！具体地说，当您的公司与本地ISP签订合同并获得前缀(即地址范围)时，您的本地ISP将使用BGP向其连接的ISP通告您的前缀。然后，这些ISP将依次使用BGP来传播通告。最终，所有Internet路由器都将知道您的前缀(或包含您的前缀的某个聚合)，从而能够适当地转发发往您的Web和邮件服务器的数据报。
若有收获，就点个赞吧
0 人点赞
