2. cnp3-ebook
3. protocols/bgp
4. English
5. Zen

117 ../../protocols/bgp.rst:425
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — `AS4` sends `U(p,AS4:AS0)` to `AS1` and `AS3`. `AS3` prefers the path via `AS4`. 80/10000 · 80
118 ../../protocols/bgp.rst:426
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — `AS3` sends `U(p,AS3:AS4:AS0)` to `AS1` and `W(p)` to `AS4`. `AS1` switches back to the direct path and we are back at the first step. 134/10000 · 134
119 ../../protocols/bgp.rst:428
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — This example shows that the convergence of BGP is unfortunately not always guaranteed as some interdomain routing policies may interfere with each other in complex ways. [GW1999]_ have shown that checking for global convergence is either NP-complete or NP-hard. See [GSW2002]_ for a more detailed discussion. 308/10000 · 308
120 ../../protocols/bgp.rst:430
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Fortunately, there are some operational guidelines [GR2001]_ [GGR2001]_ that can guarantee BGP convergence in the global Internet. To ensure that BGP will converge, these guidelines consider that there are two types of peering relationships : `customer->provider` and `shared-cost`. In this case, BGP convergence is guaranteed provided that the following conditions are fulfilled : 381/10000 · 381
121 ../../protocols/bgp.rst:432
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The topology composed of all the directed `customer->provider` peering links is a graph that does not contain any cycle 119/10000 · 119
122 ../../protocols/bgp.rst:433
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — An AS always prefers a route received from a `customer` over a route received from a `shared-cost` peer or a `provider`. 120/10000 · 120
123 ../../protocols/bgp.rst:436
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The first guideline implies that the provider of the provider of `ASx` cannot be a customer of `ASx`. Such a relationship would not make sense from an economic perspective as it would imply circular payments. Furthermore, providers are usually larger than customers. 266/10000 · 266
124 ../../protocols/bgp.rst:438
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The second guideline also corresponds to economic preferences. Since a provider earns money when sending packets to one of its customers, it makes sense to prefer such customer learned routes over routes learned from providers. [GR2001]_ also shows that BGP convergence is guaranteed even if an AS associates the same preference to routes learned from a `shared-cost` peer and routes learned from a customer. 408/10000 · 408
125 ../../protocols/bgp.rst:440
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — From a theoretical perspective, these guidelines should be verified automatically to ensure that BGP will always converge in the global Internet. However, such a verification cannot be performed in practice because this would force all domains to disclose their routing policies (and few are willing to do so) and furthermore the problem is known to be NP-hard [GW1999]. 370/10000 · 370
126 ../../protocols/bgp.rst:442
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — In practice, researchers and operators expect that these guidelines are verified [#fgranularity]_ in most domains. Thanks to the large amount of BGP data that has been collected by operators and researchers [#fbgpdata]_, several studies have analyzed the AS-level topology of the Internet. [SARK2002]_ is one of the first analysis. More recent studies include [COZ2008]_ and [DKF+2007]_ 386/10000 · 386
127 ../../protocols/bgp.rst:444
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Based on these studies and [ATLAS2009]_, the AS-level Internet topology can be summarized as shown in the figure below. 119/10000 · 119
128 ../../protocols/bgp.rst:450
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The layered structure of the global Internet 44/10000 · 44
129 ../../protocols/bgp.rst:454
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The domains on the Internet can be divided in about four categories according to their role and their position in the AS-level topology. 136/10000 · 136
130 ../../protocols/bgp.rst:465
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Due to this organization of the Internet and due to the BGP decision process, most AS-level paths on the Internet have a length of 3-5 AS hops. 143/10000 · 143
131 ../../protocols/bgp.rst:470
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Footnotes 9/10000 · 9
132 ../../protocols/bgp.rst:471
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — An analysis of the evolution of the number of domains on the global Internet during the last ten years may be found in http://www.potaroo.net/tools/asn32/. 155/10000 · 155
133 ../../protocols/bgp.rst:473
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Several web sites collect and analyze data about the evolution of BGP in the global Internet. http://bgp.potaroo.net provides lots of statistics and analyzes that are updated daily. 181/10000 · 181
134 ../../protocols/bgp.rst:475
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — See http://as-rank.caida.org/ for an analysis of the interconnections between domains based on measurements collected in the global Internet. 142/10000 · 142
135 ../../protocols/bgp.rst:478
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Two routers that are attached to the same IXP exchange packets only when the owners of their domains have an economical incentive to exchange packets on this IXP. Usually, a router on an IXP is only able to exchange packets with a small fraction of the routers that are present on the same IXP. 294/10000 · 294
136 ../../protocols/bgp.rst:480
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — See ftp://ftp.ripe.net/ripe/dbase for the RIPE database that contains the import and export policies of many European ISPs. 123/10000 · 123