Exit Zen
113
../../protocols/bgp.rst:421
English
`AS1` sends `U(p, AS1:AS0)` to `AS3` and `AS4`. `AS4` selects the path via `AS1` since this is its preferred path. `AS3` still uses the direct path.
0/1480 · 148
114
../../protocols/bgp.rst:422
English
`AS4` advertises `U(p,AS4:AS1:AS0)` to `AS3`.
0/450 · 45
115
../../protocols/bgp.rst:423
English
`AS3` sends `U(p, AS3:AS0)` to `AS1` and `AS4`. `AS1` selects the path via `AS3` since this is its preferred path. `AS4` still uses the path via `AS1`.
0/1510 · 151
116
../../protocols/bgp.rst:424
English
As `AS1` has changed its path, it sends `U(p,AS1:AS3:AS0)` to `AS4` and `W(p)` to `AS3` since its new path is via `AS3`. `AS4` switches back to the direct path.
0/1600 · 160
117
../../protocols/bgp.rst:425
English
`AS4` sends `U(p,AS4:AS0)` to `AS1` and `AS3`. `AS3` prefers the path via `AS4`.
0/800 · 80
118
../../protocols/bgp.rst:426
English
`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.
0/1340 · 134
119
../../protocols/bgp.rst:428
English
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.
0/3080 · 308
120
../../protocols/bgp.rst:430
English
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 :
0/3810 · 381
121
../../protocols/bgp.rst:432
English
The topology composed of all the directed `customer->provider` peering links is a graph that does not contain any cycle
0/1190 · 119
122
../../protocols/bgp.rst:433
English
An AS always prefers a route received from a `customer` over a route received from a `shared-cost` peer or a `provider`.
0/1200 · 120
123
../../protocols/bgp.rst:436
English
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.
0/2660 · 266
124
../../protocols/bgp.rst:438
English
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.
0/4080 · 408
125
../../protocols/bgp.rst:440
English
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].
0/3700 · 370
126
../../protocols/bgp.rst:442
English
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]_
0/3860 · 386
127
../../protocols/bgp.rst:444
English
Based on these studies and [ATLAS2009]_, the AS-level Internet topology can be summarized as shown in the figure below.
0/1190 · 119
128
../../protocols/bgp.rst:450
English
The layered structure of the global Internet
0/440 · 44
129
../../protocols/bgp.rst:454
English
The domains on the Internet can be divided in about four categories according to their role and their position in the AS-level topology.
0/1360 · 136
130
../../protocols/bgp.rst:465
English
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.
0/1430 · 143
131
../../protocols/bgp.rst:470
English
Footnotes
0/100 · 9
132
../../protocols/bgp.rst:471
English
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/.
0/1550 · 155