A Model of BGP Routing for Network Engineering
用于网络工程的BGP路由模型

ABSTRACT
抽象

The performance of
的性能 IP
知识产权 networks depends on
networks 依赖于 a wide
宽 variety
品种 of
之 dy- namic conditions.
条件。 Traffic
交通 shifts,
变化 equipment
设备 failures,
失败 planned
计划 main- tenance, and topology changes in other parts of the Internet can
Internet 其他部分的维护和拓扑更改可以 all
都 degrade
降低 performance.
性能。 To
自 maintain
保持 good
好 performance,
性能 network operators must continually reconfigure the routing
网络运营商必须不断重新配置路由 protocols.
协议。 Op- erators configure BGP
操作器配置 BGP to
自 control how traffic
控制流量 flows
流 to
自 neighboring Autonomous
邻近的自治 Systems
系统 (ASes),
（AS）、 as
如 well
井 as
如 how
如何 traffic
交通 traverses
遍历 their networks.
他们的网络。 However, because BGP route selection is distributed, indirectly controlled by configurable policies, and influenced by complex
但是，由于 BGP 路由选择是分布式的，间接受可配置策略控制，并受复杂 interactions
相互 作用 with
跟 intradomain
域内 routing
路由 protocols,
协议 operators
运营商cannot predict how
无法预测如何 a particular
特定 BGP
边界网关协议 configuration
配置 would
愿意 behave
做人 in
在practice.
实践。 To avoid inadvertently degrading network performance, operators
为避免无意中降低网络性能，运营商 need
需要 to
自 evaluate
评价 the
这 effects
影响 of
之 configuration
配置 changes
变化 be- fore deploying them on a live network
在将它们部署到实时网络上之前. We propose an algorithm that computes the outcome of the BGP route selection process for each router in
我们提出了一种算法，用于计算 a single
单 AS, given only a
AS，仅给定 static
静态的 snapshot of the net-
网络快照-work
工作 state, without
state，不带 simulating
模拟 the
这 complex details
复杂细节 of
之 BGP
边界网关协议 message
消息passing.
通过。 We describe a BGP emulator based on this algorithm;
我们描述了基于此算法的 BGP 仿真器; the emulator exploits the unique characteristics of routing data to reduce computational overhead.
仿真器利用路由数据的独特特性来减少计算开销。 Using data from a large ISP, we show that
使用来自大型 ISP 的数据，我们表明 the emulator
模拟器 correctly computes BGP
正确计算 BGP routing decisions and has a running time that is acceptable for many tasks, such as traffic engineering and capacity planning.
路由决策，并且具有许多任务（如流量工程和容量规划）可接受的运行时间。

Categories and Subject Descriptors
类别和主题描述符

C.2.2 [Network Protocols]: Routing Protocols; C.2.6 [Computer- Communication Networks]: Internetworking
C.2.2[NetworkProtocols（网络协议）]：路由协议;C.2.6[计算机 - 通信网络]：互联互通

General Terms
一般条款

Algorithms, Management, Performance, Measurement
算法，管理，性能，测量

Keywords
关键字

BGP, traffic engineering, modeling, routing
BGP，流量工程，建模，路由

INTRODUCTION
介绍

The delivery of IP packets through the Internet depends on a large collection of routers that compute end-to-end paths in a dis-
通过Internet传输IP数据包取决于大量路由器，这些路由器以

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
允许免费制作本作品的全部或部分数字或纸质副本供个人或课堂使用，前提是副本不是出于营利或商业利益而制作或分发，并且副本上带有本声明和完整引文第一页。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特别许可和/或付费。

SIGMETRICS/Performance’04, June 12–16, 2004, New York, NY, USA. Copyright 2004 ACM 1-58113-664-1/04/0006 ...$5.00.
SIGMETRICS/Performance'04,2004 年 6 月 12 日至 16 日，美国纽约州纽约市。版权所有 2004 ACM 1-58113-664-1/04/0006 ...5.00 美元。

tributed fashion,
致敬时尚， using standardized routing protocols.
使用标准化路由协议。 Providing low
提供低 latency,
延迟 high
高 throughput, and
吞吐量，以及 high
高 reliability
可靠性 requires network
需要网络operators
运营商 to
自 adjust
调整 routing
路由 protocol configuration
协议配置 when
什么时候 performance
性能problems arise
问题出现 or network conditions
或网络状况 change.
改变。 For example, an
例如， op- erator
操作器 might
可能 adjust
调整 the
这 configuration
配置 to
自 respond
响应 to
自 network
网络 conges- tion or equipment failures or to prepare for planned maintenance. However,
冷凝或设备故障或为计划维护做准备。然而 the
这 complexity
复杂性 of
之 the
这 protocols,
协议 the
这 large
大 number
数 of
之 tun- able
可调 parameters,
参数 and
和 the
这 size
大小 of
之 the
这 network
网络 make
做 it
它 extremely difficult for operators to reason about the effects of their actions. The common approach of “tweak and pray” is no longer accept- able
操作员极难推断其操作的效果。“调整和祈祷”的常见方法不再被接受 in
在 an
一 environment
环境 where
哪里 users
用户 have
有 high
高 expectations
期望值 for
为 per- formance and reliability [1].
性能和可靠性 [1]。 To avoid costly debugging time and catastrophic mistakes, operators must be able to make predictions quickly based on an
为避免昂贵的调试时间和灾难性错误，操作员必须能够根据accurate
准确model of the routing protocols.
路由协议的模型。

Previous
以前 work
工作 in
在 this
这 area
面积 has
具有 focused
集中 on
上 Interior
内部 Gateway
网关 Pro- tocols (IGPs), such as Open Shortest Path First
协议 （IGP），例如开放最短路径优先 (OSPF)
（OSPF） and Inter- mediate
和中级 System-Intermediate
系统-中间体 System
系统 (IS-IS),
（IS-IS）、 that
那 operate
操作 within
在 a single
单 Autonomous System
自治系统 (AS).
（AS） 的 S In
在 these
这些 protocols, each
协议，每个 link
链接 has
具有 a configurable
配置 integer
整数 “cost”
“成本” that
那 is
是 used
使用 to
自 compute
计算 the
这 shortest
最短 path (smallest
路径（最小 cost
成本 path)
路径） through
通过 the
这 network.
网络。 Tuning
调音 these
这些 link
链接 weights gives operators a way to modify the paths inside the AS to satisfy network
weights 为运营商提供了一种修改 AS 内部路径以满足网络 and
和 user
用户 performance
性能 goals
目标 [2]. Several
[2]. 几个 existing
现存 tools
工具 [3, 4, 5] capture
捕获 how
如何 changes
变化 to
自 the
这 link
链接 weights
权重 would
愿意 affect
影响 the
这 flow of
流程 the
这 offered
提供 traffic
交通 over
多 the
这 new
新增功能 paths
路径 and
和 also
也 propose
提出 good
好 can- didate settings of the link weights.
can- didate 链接权重的设置。 Although these tools are ex- tremely valuable to network operators, the flow of traffic in large service
尽管这些工具对网络运营商来说非常有价值，但大型服务中的流量 provider
供应商 backbones
骨干 ultimately
最终 depends
取决于 on
上 the
这 inter
国米domain routing
域路由 protocol
协议 as
如 well. A
井。一个 provider
供应商 uses
使用 the
这 Border
边境 Gateway
网关 Pro-
优点-tocol (BGP) to exchange reachability information with neighboring
tocol （BGP） 与邻居交换可访问性信息domains
域 and
和 to
自 propagate
传播 these
这些 routes
路线 within
在 its
其 own
有 network. Un- fortunately,
网络。不幸的是， several
几个 subtleties
微妙 make
做 modeling
建 模 BGP
边界网关协议 route
路线 selection in an AS much more challenging than emulating IGP:
在 AS 中选择比模拟 IGP 更具挑战性：

BGP’s distributed, path vector operation means that every router may have a different view of network state. In contrast to link state protocols that flood complete information throughout the network, a BGP-speaking router sends incremental reachability in- formation only to its immediate neighbors. In BGP, a router sends an advertisement to notify its neighbor of a new route to a desti- nation prefix and a withdrawal to revoke the route when it is no longer available. Each BGP-speaking router locally computes its own best BGP route from the best routes announced by its neigh- bors. A change in the best path at one router can affect the selection of the best route at another router, and no single router has a com- plete view of the available BGP routes in the AS.
BGP 的分布式路径向量操作意味着每个路由器可能具有不同的网络状态视图。与在整个网络中泛洪完整信息的链路状态协议相比，使用 BGP 的路由器仅向其直接邻居发送增量可达性信息。在 BGP 中，路由器发送通告以通知其邻居新路由到目的地前缀，并在路由不再可用时发送撤销以撤销该路由。每个 BGP 语言路由器都会根据其邻居宣布的最佳路由在本地计算自己的最佳 BGP 路由。一台路由器上最佳路径的更改可能会影响另一台路由器上最佳路由的选择，并且没有单个路由器可以完整地了解 AS 中可用的 BGP 路由。

BGP route selection is a complex process that depends on a combination of route attributes. While most IGPs advertise a sin- gle integer metric for each link and select routes based on shortest
BGP 路由选择是一个复杂的过程，取决于路由属性的组合。虽然大多数 IGP为每个链路通告一个单整数度量，并根据最短

eBGP
eBGP 协议

routes
路线

Neighboring AS
相邻AS

eBGP
eBGP 协议

b routes
B路由

BGP
边界网关协议 routing
路由 decisions
决定when
什么时候 the
这 network is
network 是 configured “correctly”
配置“正确”, which can be checked separately by testing
可通过测试单独检查 certain sufficient con- ditions.
某些足够的条件。 Our
我们 model
型 can
能 also
也 be
是 combined
组合的 with
跟 prefix-level
前缀级别 traffic
交通

A B

R

ingress router
入口路由器

Figure 1: Network engineering terminology.
图1：网络工程术语。

paths, BGP route advertisements include various attributes, such as the list of the ASes in the path (the AS path) and the IP address of the router responsible for the route (the next hop). BGP route selec- tion is based on a complex, multi-stage decision process [6]. BGP allows operators to specify complex policies that have an indirect effect on the selection of the best path.
paths，BGP 路由通告包括各种属性，例如路径中的 AS 列表（AS路径）和负责路由的路由器的 IP 地址（下一跳）。BGP路由选择基于复杂的多阶段决策过程[6]。BGP 允许运营商指定对最佳路径的选择产生间接影响的复杂策略。

BGP route selection depends on interactions with intradomain routing protocols. Whereas the IGP can be modeled in isolation, the selection of the best BGP route at each router also depends on the IGP path cost to the BGP next hop announcing the route. “Hot potato” routing, where a router prefers the route with the shortest IGP path (the closest exit point), introduces a complex coupling between BGP and the underlying IGP.
BGP路由选择取决于与域内路由协议的交互。虽然 IGP 可以单独建模，但在每个路由器上选择最佳 BGP路由还取决于通告路由的BGP下一跃点的 IGP路径成本。“烫手山芋”路由，即路由器首选具有最短 IGP 路径（最近的出口点）的路由，在 BGP 和底层 IGP 之间引入了复杂的耦合。

Hierarchical iBGP configuration affects the routing choices that are available at each router. Internal BGP (iBGP) is used to distribute BGP-learned routes throughout an AS. Rather than having an iBGP session between each pair of routers (“full mesh iBGP”), large provider networks typically distribute routes in a hi- erarchical fashion. This makes the choices available at one router dependent on the decisions made at other routers and may prevent the protocol from converging.
分层iBGP配置会影响每个路由器上可用的路由选择。内部BGP （iBGP）用于在整个 AS 中分配 BGP 学习的路由。大型提供商网络通常以分层方式分发路由，而不是在每对路由器之间有一个 iBGP 会话（“全网状 iBGP”）。这使得一个路由器上的可用选择取决于其他路由器上做出的决策，并且可能会阻止协议收敛。

In
在 this
这 paper,
纸 we
我们 present
目前 a model
型 that
那 accurately
准确 determines
决定 how the
如何 network
网络 configuration
配置 and
和 the
这 routes
路线 learned
博学 via
通过 external
外部 BGP (eBGP) affect the flow of traffic through an AS. While some ex- isting tools simulate BGP’s behavior [7], this is the first paper to develop a model that determines the
BGP （eBGP） 会影响通过 AS 的流量。虽然一些现有的工具模拟了 BGP 的行为 [7]，但这是第一篇开发模型来确定outcome
结果of the BGP
BGP 的 path se- lection process at each router in
每个路由器的路径选择过程 an AS without simulating the dy- namics of the protocol.
一个 AS，而不模拟协议的动态。 This type of model is important for sev- eral reasons.
这种类型的模型很重要，原因如下。 First, network operators need to know the paths that routers ultimately
首先，网络运营商需要知道路由器最终的路径 select to perform engineering tasks (e.g., traffic engineering and maintenance), but they have no need for a com- putationally
选择执行工程任务（例如，流量工程和维护），但他们不需要计算 expensive
贵 simulation
模拟 of
之 routing
路由 dynamics.
动力学。 We
我们 present an
现在 emulator
仿真 based
基于 on
上 our
我们 model
型 that
那 facilitates
促进 these
这些 tasks
任务 by
由 pro- viding fast, accurate answers to “what if” questions about the ef- fects
快速、准确地回答有关效果的 “假设” 问题 of
之 changes
变化 to
自 the
这 network.
网络。 Second,
第二 an
一 accurate
准确 model
型 of
之 BGP
边界网关协议route
路线 selection
选择 can be
可以是 used
使用 to
自 improve
提高 and
和 validate existing
验证现有 simula-
模拟-tors
托尔斯 by
由 highlighting
突出 subtleties
微妙 of
之 the
这 protocol
协议 and
和 situations
情况 where BGP might not converge to a unique solution.
其中 BGP 可能不会收敛到唯一的解决方案。 A simulator may only
模拟器只能 compute
计算 one
一 possible
可能 outcome,
结果 which
哪 may
五月 not
不 accurately
准确 re- flect the outcome in a real network.
在真实的网络中重新调整结果。 The modeling framework we present can determine whether a BGP configuration would con- verge to a unique outcome.
我们提供的建模框架可以确定 BGP 配置是否会趋近于独特的结果。

Predicting how a configuration change would affect the flow of traffic first requires a way to determine which route each ingress router in the AS would select for each destination prefix, given a network configuration and the eBGP routes learned at the egress routers (as shown in Figure 1). This paper solves precisely this problem. The model of BGP routing that we present is essentially an abstraction that conceals protocol details that are irrelevant to the outcome of the BGP decision process. The model computes
要预测配置更改将如何影响流量，首先需要一种方法来确定 AS 中的每个入口路由器将为每个目标前缀选择哪个路由，给定网络配置和在出口路由器上学习的 eBGP 路由 （如图 1 所示）。本文正是解决了这个问题。我们提供的BGP路由模型本质上是一个抽象，它隐藏了与 BGP决策过程结果无关的协议细节。模型计算

measurements to form the basis of a traffic engineering tool.
测量以构成流量工程工具的基础。

The rest of the paper is organized as follows.
本文的其余部分组织如下。 In Section 2, we present several examples of network engineering tasks that moti- vate the need for an accurate, predictive model of BGP path se- lection in an AS. Section 3 describes the practical constraints that the
在第 2 节中，我们提供了几个网络工程任务示例，这些任务激发了对 AS 中 BGP 路径选择的准确预测模型的需求。第 3 节描述了 network
网络 configuration
配置 and
和 routing
路由 advertisements
广告 must
必须 satisfy to make modeling BGP route selection possible and applies these constraints
satisfy 使建模 BGP 路由选择成为可能，并应用这些约束 in
在 a novel
小说 way
道路 to
自 decompose
分解 the
这 route
路线 prediction
预测 prob- lem
问题 into
到 three
三 distinct
不同 phases.
阶段。 In
在 Section
部分 4, we
我们 describe
描述 each
每 phase of the route prediction algorithm in detail.
阶段。 Section 5 describes a prototype
第 5 节 描述了原型 implementation
实现 of
之 a BGP
边界网关协议 emulator. In
仿真。在 Sections
部分 6 and
和 7, we
7、我们 present
目前 an
一 evaluation
评估 and
和 validation
验证 of
之 our
我们 prototype
原型 on
上 routing and configuration data from a large tier-1
来自大型 Tier-1 的路由和配置数据 ISP.
国际互联网服务提供商。 These experiments show that the route prediction algorithm accurately predicts BGP routing decisions and that it is efficient enough to be practical for many network engineering tasks.
这些实验表明，路由预测算法可以准确预测 BGP 路由决策，并且它的效率足以用于许多网络工程任务。 Section 8 provides an overview of related work. We conclude in Section 9.
第 8 节概述了相关工作。我们在第 9 节中总结。

NETWORK ENGINEERING
网络工程

In this section, we discuss network engineering problems that operators commonly face. These examples demonstrate the need to systematically model BGP’s route selection process and move beyond today’s “tweak and pray” techniques. We then discuss why a practical model of BGP is useful; in particular, we discuss the advantages a model has over simulation and live testing.
在本节中，我们将讨论运营商通常面临的网络工程问题。这些示例表明，需要系统地对 BGP 的路由选择过程进行建模，并超越当今的 “调整和祈祷” 技术。然后，我们将讨论为什么实用的 BGP 模型很有用;特别是，我们讨论了模型相对于模拟和实时测试的优势。

Network Engineering Problems
网络工程问题

Network operators must adjust routing protocol configuration to respond to the following common changes in network conditions:
网络运营商必须调整路由协议配置，以响应网络状况中的以下常见变化：

Changes in traffic load. Because traffic is dynamic, the amount of traffic to any destination may suddenly change, causing changes in traffic distribution across network links. For example, a Web site sometimes experiences a traffic surge due to a flash crowd (i.e., the “Slashdot effect”); a network that was routing traffic to that desti- nation through a neighboring AS could experience congestion on an outbound link to that destination. A network operator must re- configure routing policy to alleviate congestion.
流量负载的变化。由于流量是动态的，因此到任何目的地的流量可能会突然发生变化，从而导致跨网络链接的流量分配发生变化。例如，网站有时会由于突发事件（即“Slashdot 效应”）而遇到流量激增;通过相邻 AS 将流量路由到该目的地的网络可能会在到该目的地的出站链路上遇到拥塞。网络运营商必须重新配置路由策略以缓解拥塞。

Changes in link capacity. Network links are frequently up- graded to higher capacity. In response, network operators may wish to adjust configuration to route additional traffic through recently upgraded links. For example, if link in Figure 1 were upgraded from an OC12 to an OC48, a network operator would want to shift traffic from to .
链路容量的变化。网络链接经常升级到更高的容量。作为回应，网络运营商可能希望调整配置，以通过最近升级的链路路由额外的流量。例如，如果图 1 中的链路从OC12 升级到 OC48，则网络运营商希望将流量从转移到 。

Long-term connectivity changes. On longer timescales, the points where a network connects to neighboring ASes, as well as the ASes that it connects to, change. As links to other ASes appear and disappear, network operators must move large amounts of traf- fic. If the AS shown in Figure 1 added a third link to its neighboring AS, an operator would shift a portion of traffic to that AS from and to the new link.
长期连接更改。在更长的时间尺度上，网络连接到相邻 AS 的点以及它所连接的AS都会发生变化。随着到其他AS的链接出现和消失，网络运营商必须移动大量的流量。如果图1中所示的AS 向其相邻 AS 添加了第三条链路，则运营商会将一部分流量从新链路转移到该 AS。

Changes in available routes. Due to protocol dynamics and changing commercial agreements, an AS might suddenly receive an alternate route to a destination that could cause traffic flow to shift dramatically; alternatively, an existing route could suddenly disappear. These events may require a network operator to rebal- ance the flow of traffic.
可用路线的更改。由于协议动态和不断变化的商业协议，AS 可能会突然收到一条通往目的地的备用路由，这可能会导致流量发生巨大变化;或者，现有路由可能会突然消失。这些事件可能需要网络运营商重新平衡流量。

Planned maintenance. Network operators commonly perform routine maintenance on portions of their network, adjusting inte-
计划内维护。网络运营商通常会对其网络的某些部分进行例行维护，调整内部

rior routing link weights to divert traffic away from the part of the network that is undergoing maintenance. If router were under- going an upgrade, the network operator could adjust both the IGP link weights and the BGP configuration to divert traffic away from
RIOR路由链路权重，用于将流量从正在维护的网络部分转移出去。如果路由器正在进行升级，网络运营商可以调整IGP 链路权重和BGP配置，以将流量从

without overloading links that border neighboring domains.
而不会使与相邻域接壤的链接过载。

Failure and disaster planning. An operator may wish to evaluate the robustness of the network by examining the effects of failures on routing and traffic flow. Studying the effects of a component or link failure or even a more serious catastrophe (e.g., fiber cut, tunnel fire, or terrorist attack) helps network operators and planners make design decisions.
故障和灾难规划。运营商可能希望通过检查故障对路由和流量的影响来评估网络的稳健性。研究组件或链路故障甚至更严重的灾难（例如，光纤切断、隧道火灾或恐怖袭击）的影响，有助于网络运营商和规划者做出设计决策。

Tools exist to help network operators adjust interior routing pro- tocol parameters to rebalance traffic within an AS [3, 4, 5], but op- erators must also rebalance traffic across its external links to other networks by reconfiguring BGP. A network operator who wants to shift traffic from link to in Figure 1 typically would adjust the import policy for a set of routes at router , commonly by decreas- ing the “local preference” attribute that router assigns to these routes [8]. This would cause the routes learned at router for these destinations to appear more attractive than those at , causing the traffic to those destinations to exit the AS via .
存在帮助网络运营商调整内部路由协议参数的工具，以重新平衡AS 内的流量[3,4,5]，但操作者还必须在其通过重新配置BGP 连接到其他网络的外部链接。想要将流量从链路转移到图 1 中的网络运营商通常会调整路由器上一组路由的导入策略，通常是通过减少路由器分配给这些路由的 “本地首选项” 属性[8]。这将导致在路由器上为这些目的地学习的路由看起来比在路由器上学习的路由更具吸引力，从而导致到这些目的地的流量通过 AS 退出。

Network Engineering Requirements
网络工程要求

Motivated by these practical network engineering examples, we now present several requirements for a network engineering tool that predicts the outcome of BGP route selection. (Throughout the paper, we use the term “prediction” to describe the process of de- termining the outcome of BGP route selection offline.)
在这些实际网络工程示例的启发下，我们现在提出了对预测BGP路由选择结果的网络工程工具的几个要求。（在整篇论文中，我们使用术语“预测”来描述离线 BGP 路由选择结果的过程。

Operators need to be able to predict the effects of a configura- tion change before deployment in the live network. Operators typi- cally handle network engineering tasks by tuning the existing con- figuration of the live network, witnessing the effects of the change, and reverting to the previous configuration if the desired effects are not achieved. This method is time consuming and can lead to unnecessary performance degradation. The complexity of interdo- main routing makes it essentially impossible to compute back-of- the-envelope estimates of the effects of configuration changes.
运营商需要能够在部署到实时网络之前预测配置更改的影响。操作员通常通过调整实时网络的现有配置、见证更改的影响以及如果未达到预期效果，则恢复到以前的配置来处理网络工程任务。此方法非常耗时，并且可能导致不必要的性能下降。interdo- main routing 的复杂性使得基本上不可能计算配置更改影响的包络估计。

Because network engineering involves exploring a large search space, operators need to predict the effects of each candidate con- figuration change as quickly as possible. Operators usually need to experiment with many possible configuration changes before arriv- ing at an acceptable solution. This requires techniques for quickly evaluating the effects of a proposed configuration change. In prac- tice, the candidate configuration changes typically are just small modifications to the existing configuration, which are less likely to cause significant unexpected changes in routes or the offered traffic load. To be useful, a route prediction tool should be fast at evaluat- ing incremental changes.
由于网络工程涉及探索大型搜索空间，因此操作员需要尽快预测每个候选配置变化的影响。 操作员通常需要尝试许多可能的配置更改，然后才能找到可接受的解决方案。这需要快速评估提议的配置更改效果的技术。在实践中，候选配置更改通常只是对现有配置的微小修改，不太可能导致路由或提供的流量负载发生重大意外变化。为了有用，路线预测工具应该能够快速评估增量变化。

Network engineering tasks require an accurate prediction of the outcome of the BGP path selection process but do not require a detailed simulation of the protocol dynamics. Network simulators (e.g., SSFNet [7]) help operators understand dynamic routing pro- tocol behavior, but simulation represents network behavior in terms of message passing and protocol dynamics over a certain period of time. In contrast, network engineers usually just need to know the outcome of the path-selection process and not the low-level timing details. Furthermore, existing simulators do not capture some of the relevant protocol interactions that can affect the outcome of the decision process. Simulating every detailed interaction is hard to do without a higher level model of BGP in the first place.
网络工程任务需要准确预测BGP路径选择过程的结果，但不需要对协议动态进行详细仿真。网络模拟器（例如 SSFNet[7]）帮助运营商了解动态路由协议行为，但模拟表示一段时间内消息传递和协议动态的网络行为的时间。相比之下，网络工程师通常只需要知道path-selection过程的结果，而不是低级的timing 细节。此外，现有的模拟器无法捕获一些可能影响决策过程结果的相关协议交互。首先，如果没有更高级别的 BGP 模型，就很难模拟每一个详细的交互。

In summary, BGP path selection is a massive, highly tunable, distributed computation. To maintain good end-to-end performance,
总之，BGP 路径选择是一种大规模、高度可调的分布式计算。为了保持良好的端到端性能，

operators need a way to predict the outcome of this computation under various configurations (1) efficiently, (2) in a way that facil- itates evaluating incremental changes, and (3) without deploying configuration changes on a live network. In the following sections, we describe a way to model the BGP decision process across every router in an AS; our algorithm correctly and efficiently computes the outcome of the BGP decision process at each router.
运营商需要一种方法来预测各种配置下计算的结果 （1） 高效，（2） 以一种便于评估增量更改的方式，以及 （3） 无需在实时网络上部署配置更改。在以下部分中，我们将介绍一种在AS 中跨每个路由器对 BGP决策过程进行建模的方法;我们的算法正确有效地计算每个路由器的 BGP 决策过程的结果。

MODELING FRAMEWORK
建模框架

At a glance, modeling the routing decisions in an AS seems as simple as applying the BGP decision process at each router. How- ever, the BGP routing system inside an AS is not guaranteed to converge to a unique solution where routers make consistent deci- sions. Even when the system converges, the decision made at one router can affect the options available to other routers. Applying theoretical results from previous work, we impose three practical constraints on the routing system that make modeling BGP route selection possible. We then show that route selection can be mod- eled in three distinct phases when these constraints are satisfied.
乍一看，在 AS 中对路由决策进行建模似乎就像在每个路由器上应用BGP决策流程一样简单。然而，AS 内部的 BGP 路由系统并不能保证收敛到路由器做出一致决定的独特解决方案。即使系统收敛，在一个路由器上做出的决策也会影响其他路由器的可用选项。应用以前工作的理论结果，我们对路由系统施加了三个实际约束，使建模 BGP 路由选择成为可能。然后，我们表明，当满足这些约束条件时，路线选择可以分为三个不同的阶段进行修改。

Constraints on the Routing System
路由系统的约束

Given the eBGP-learned routes to a destination prefix, we would like to determine which route each router would ultimately select. Unfortunately, certain network configurations do not lend them- selves to efficient route prediction. This is a fundamental problem underlying BGP—some configurations do not converge, and deter- mining whether a system converges to a unique solution is compu- tationally intractable [9]. To make modeling BGP route selection feasible, we impose three constraints and explain why these con- straints are reasonable to assume in practice.
给定eBGP 学习到目标前缀的路由，我们想确定每个路由器最终会选择哪个路由。遗憾的是，某些网络配置本身并不适合进行有效的路线预测。这是 BGP 背后的一个基本问题— 某些配置不收敛，确定系统是否收敛到唯一的解决方案在计算上是棘手的 [9]。为了使建模 BGP 路由选择可行，我们施加了三个约束，并解释了为什么在实践中可以合理假设这些约束。

If the eBGP-learned routes change frequently, the internal rout- ing system does not have time to propagate the effects of one eBGP advertisement before the next one arrives. As such, we assume:
如果eBGP 学习的路由频繁更改，则内部路由系统没有时间在下一个 eBGP 通告到达之前传播一个 eBGP 通告的效果。因此，我们假设：

Constraint 1. The eBGP-learned routes change slowly with respect to the timescale of network engineering decisions.
约束1.eBGP 学习的路由会随着网络工程决策的时间尺度而变化缓慢。

In practice, most BGP routes are stable for days or weeks at a time [10], and the vast majority of traffic is associated with these stable routes [11]. This allows emulation to operate on a static snapshot of the eBGP routes. Any eBGP routing change can be treated as a separate problem instance.
在实践中，大多数 BGP 路由一次稳定数天或数周[10]，并且绝大多数流量都与这些稳定路由相关联 [11]。这允许仿真对 eBGP 路由的静态快照进行操作。任何 eBGP 路由更改都可以被视为单独的问题实例。

Network operators have significant flexibility in deciding how to propagate the eBGP-learned routes throughout the AS. In the simplest
网络运营商在决定如何在整个 AS 中传播 eBGP 学习的路由方面具有极大的灵活性。在最简单的 case,
箱 the
这 routers
路由器 are
是 configured
配置 in
在 a full
满 mesh
网孔 of
之 iBGP
iBGP 协议 ses- sions.
系列。 In
在 general,
常规 though,
虽然 the
这 routers
路由器 may
五月 form
形式 a more
更多 complicated
复杂signaling
信号 graph
图 of
之 iBGP
iBGP 协议 sessions,
会话 as
如 shown
显示 in
在 Figure
数字 2. Each
2. 每个 edge corresponds
边对应 to
自 an
一 iBGP
iBGP 协议 session
会期 between
之间 a pair
双 of
之 routers. A
路由器。一个 router does not normally forward iBGP-learned routes to its other iBGP neighbors.
路由器通常不会将 iBGP 学习的路由转发到其其他 iBGP 邻居。 However,
然而 a router
路由器 can
能 be
是 configured
配置 as
如 a route
路线 reflector
反射镜(RR),
（RR）、 which
哪 forwards
前锋 routes
路线 learned
博学 from
从 one
一 of
之 its
其 route-reflector clients to its other clients.
route-reflector 客户端连接到其其他客户端。 Following terminology from previous work
遵循以前工作中的术语 [12], we
我们 use
用 the
这 term
术语 up
向上 for
为 the
这 iBGP
iBGP 协议 session
会期 from
从 a router
路由器 to its
到其 RR,
RR， over
多for
为 a conventional iBGP
传统 iBGP session
会期 between
之间 two
二 routers, and
routers，以及down
下for the iBGP session from an RR to a client.
对于从 RR 到客户端的 iBGP 会话。 A valid signaling path
有效的信令路径consists of zero or more
由零个或多个组成up
向上edges, followed by at most
edges 的 Edge 上，后跟最多 one
一over
多edge, followed
边 （Edge） > 跟随 by
由 zero
零 or
或 more
更多 down
下 edges.
边缘。 Alter- natively,
Alter- native， routers
路由器 within
在 an
一 AS
如 can
能 also
也 be
是 grouped
分组 into
到 one
一 or
或 more “confederations”.
更多的 “联盟”。 Because confederations are
因为联盟是 used much less
用得少得多 fre- quently
经常 than
比 route
路线 reflectors,
反射 we
我们 focus
重点 on
上 modeling
建 模 route
路线 reflectors and do not model the effects of confederations.
reflectors 的 Reflects 的 S 的 Reflect S 的 S 的 Reflect

Every eBGP-learned route should propagate through the signal- ing graph to every other router in the AS. For example, consider
每个eBGP 获知的路由都应通过信令图传播到 AS 中的每个其他路由器。例如，考虑

Figure 2: Example iBGP signaling graph
图2：示例iBGP信令图

Figure 2. The edge between  and is an over session, whereas the edge from to is an up session. An eBGP route learned at can reach via and . An AS’s signaling graph can violate this property even if all routers are connected via IGP. For example, if the session between and were an over session instead of an up session, would have no way to receive an eBGP route learned at . These types of partitions can make modeling difficult; therefore, we assume:
图 2.和 之间的边是 over session，而fromto 之间的边是 up 会话。在 获知的eBGP 路由可以通过 和 到达。即使所有路由器都通过 IGP 连接，AS 的信令图也可能违反此属性。例如，如果和 之间的会话是over 会话而不是 up 会话，则无法接收获知的 eBGP 路由。这些类型的分区可能会使建模变得困难;因此，我们假设：

Constraint 2. Each router has a valid iBGP signaling path to every other router¹
约束2.每个路由器都有一条到其他路由器¹ 的有效 iBGP 信令路径.

An operational network should not violate this constraint, since this could create a network partition, even though the AS is connected at the IP level. An AS with a full mesh of iBGP sessions satisfies this constraint; so does a full iBGP mesh among the top-level RRs who, in turn, each have iBGP sessions to their RR clients (a common configuration scenario).
可操作的网络不应违反此约束，因为这可能会创建网络分区，即使AS在IP 级别连接也是如此。具有完整iBGP会话网格的 AS满足此约束;顶级RR之间的完整iBGP网格也是如此，而顶级 RR 又每个 RR 都有与其 RR 客户端的 iBGP 会话（一种常见的配置场景）。

Ensuring
确保 that
那 each eBGP-learned
每个 eBGP 学习 route
路线 has an
具有 iBGP
iBGP 协议 path to
路径 ev- ery
每个 other
其他 router
路由器 still
还 does not
不 guarantee
保证 that
那 each
每 router
路由器 converges to a unique solution.
收敛到一个独特的解决方案。 A router only learns about the routes adver- tised
路由器只了解所建议的路由 by
由 its
其 immediate
立即的 iBGP
iBGP 协议 and
和 eBGP
eBGP 协议 neighbors. For
邻居。为 example,
例 in Figure 2, if
在图 2 中，如果  and
和 have eBGP-learned routes, router
具有 eBGP 学习的路由、路由器 learns
学习 a single
单个 route
路线 from
从 its
其 route
路线 reflector
反射镜 RR1. Suppose
RR1.假设 that
那 RR1 selects the eBGP route advertised by
选择由 . Then,
然后  would pick
会选的 ’s route as well, even if
的 route 中，即使  would have preferred
本来更愿意 ’s
的 route
路线 over
多 ’s
的 route. Note that
路线。请注意， makes a different routing decision than it would if it could
做出与可以时不同的路由决策 select
选择 its
其 best
最好 route
路线 from
从 all
都 the
这 eBGP
eBGP 协议 routes
路线 (i.e.,
（即 from
从 both
双and
和 ). In some
在一些 situations,
情况 differences
差异 in the routers’
在路由器的 local rankings of the BGP routes can cause persistent oscillations and even forwarding loops,
BGP 路由的本地排名可能会导致持续振荡甚至转发循环， which make it difficult to model the out- come of the BGP decision process.
这使得很难对 BGP 决策过程的结果进行建模。 Fortunately,
幸运 these problems can
这些问题可以 be
是 avoided
避免 if
如果 the
这 network
网络 configuration
配置 satisfies
满足 the
这 following
以后

sufficient condition [12]:
充分条件[12]：

CONSTRAINT 3. (a) A router prefers routes learned from down neighbors over routes learned from other neighbors, (b) the signal- ing graph does not have any cycle of up edges, and (c) the shortest IGP path between each pair of routers is a valid signaling path.
C昂斯特兰特3.（a）路由器首选从下行邻居获知的路由，而不是从其他邻州获知的路由，（b）信令图没有任何上行沿周期，以及 （c）每对路由器之间最短的 IGP 路径是有效的信令路径。

Part (a) is satisfied when routers do not change the attributes of iBGP-learned routes and each router has a lower IGP path cost to its clients than to other routers. The common practices of applying import policies only on eBGP sessions and placing RRs and their clients in the same point-of-presence (i.e., “PoP”) ensure that these conditions hold. Part (b) states that if is an RR for , and is an RR for , then is not an RR for , consistent with the common practice of constructing a route-reflector hierarchy, rather than an arbitrary signaling graph. Part (c) ensures that all routers along a shortest path to an egress point have selected the same egress point,
当路由器不更改 iBGP 获知路由的属性，并且每个路由器到其客户端的 IGP 路径开销低于其他路由器时，满足 （a） 部分。仅在 eBGP 会话上应用导入策略并将 RR 及其客户端置于同一入网点（即“PoP”）的常见做法可确保这些条件成立。（b） 部分规定，如果是 RR for 并且是RR for，则不是 RR，这与构建路由反射器层次结构的常见做法一致，而不是任意信令图。（c） 部分确保通往出口点的最短路径上的所有路由器都选择了相同的出口点，

This property can be checked by a breadth-first walk through the edges in the signaling graph and marking the nodes as they are visited; in the graph walk, an over or down edge can only be followed by a down edge.
可以通过广度优先遍历信令图中的边并在访问节点时标记节点来检查此属性;在图形遍历中，上沿或下沿只能为后跟一个下沿。

Table 1: Steps in the BGP decision process
表1：BGP决策过程中的步骤

which prevents “deflections”. Part (c) is more difficult to ensure in practice but is consistent with the approach of assigning clients to RRs that are along the shortest path to each egress point.
这可以防止 “偏转”。Part（c） 在实践中更难确保，但与将客户分配到沿到每个出口点的最短路径上的 RR 的方法一致。

Imposing these three constraints make modeling BGP route se- lection possible. Each router applies a multi-stage decision pro- cess [6] to select a single best route, as summarized in Table 1. The decision process considers the set of available routes to a destina- tion and proceeds step-by-step to eliminate candidate routes. For example, the decision process first eliminates all routes that do not have the highest local preference value, and so forth, until a single best route remains. Since the route selected at one router can affect the routes available at another router, we cannot simply apply the BGP decision process independently at each router. Although we must model the distribution of routes within an AS, Constraints 1 and 3 ensure that the system converges to a unique solution, which allows us to apply the following intuitive result:
施加这三个约束使 BGP 路由选择建模成为可能。每个路由器都应用一个多阶段决策过程[6]来选择单个最佳路由，如表1 所示。决策过程考虑通往目的地的可用路线集，并逐步消除候选路线。例如，决策过程首先消除所有没有最高本地优先级值的路由，依此类推，直到保留单个最佳路由。由于在一个路由器上选择的路由会影响另一个路由器上可用的路由，因此我们不能简单地在每个路由器上独立应用 BGP 决策过程。尽管我们必须对 AS 内路由的分布进行建模，但约束 1 和3确保系统收敛到唯一的解决方案，这使我们能够应用以下直观的结果：