Exit Zen
101
../../protocols/bgp.rst:396
English
In this internetwork, we focus on the route towards `2001:db8::1234/48` which is advertised by `AS1`. Let us also assume that `AS3` (resp. `AS4`) prefers, e.g. for economic reasons, a route learned from `AS4` (`AS3`) over a route learned from `AS1`. When `AS1` sends `U(2001:db8::1234/48,AS1)` to `AS3` and `AS4`, three sequences of exchanges of BGP messages are possible :
0/3730 · 373
102
../../protocols/bgp.rst:398
English
`AS3` sends first `U(2001:db8:1234/48,AS3:AS1)` to `AS4`. `AS4` has learned two routes towards `2001:db8:1234/48`. It runs its BGP decision process and selects the route via `AS3` and does not advertise a route to `AS3`
0/2190 · 219
103
../../protocols/bgp.rst:399
English
`AS4` first sends `U(2001:db8:1234/48,AS4:AS1)` to `AS3`. `AS3` has learned two routes towards `2001:db8:1234/48`. It runs its BGP decision process and selects the route via `AS4` and does not advertise a route to `AS4`
0/2190 · 219
104
../../protocols/bgp.rst:400
English
`AS3` sends `U(2001:db8:1234/48,AS3:AS1)` to `AS4` and, at the same time, `AS4` sends `U(2001:db8:1234/48,AS4:AS1)`. `AS3` prefers the route via `AS4` and thus sends `W(2001:db8:1234/48)` to `AS4`. In the mean time, `AS4` prefers the route via `AS3` and thus sends `W(2001:db8:1234/48)` to `AS3`. Upon reception of the `BGP Withdraws`, `AS3` and `AS4` only know the direct route towards `2001:db8:1234/48`. `AS3` (resp. `AS4`) sends `U(2001:db8:1234/48,AS3:AS1)` (resp. `U(2001:db8:1234/48,AS4:AS1)`) to `AS4` (resp. `AS3`). `AS3` and `AS4` could in theory continue to exchange BGP messages for ever. In practice, one of them sends one message faster than the other and BGP converges.
0/6850 · 685
105
../../protocols/bgp.rst:402
English
The example above has shown that the routes selected by BGP routers may sometimes depend on the ordering of the BGP messages that are exchanged. Other similar scenarios may be found in :rfc:`4264`.
0/1970 · 197
106
../../protocols/bgp.rst:404
English
From an operational perspective, the above configuration is annoying since the network operators cannot easily predict which paths are chosen. Unfortunately, there are even more annoying BGP configurations. For example, let us consider the configuration below which is often named `Bad Gadget` [GW1999]_
0/3030 · 303
107
../../protocols/bgp.rst:410
English
The bad gadget internetwork
0/270 · 27
108
../../protocols/bgp.rst:413
English
In this internetwork, there are four ASes. `AS0` advertises one route towards one prefix and we only analyze the routes towards this prefix. The routing preferences of `AS1`, `AS3` and `AS4` are the following :
0/2100 · 210
109
../../protocols/bgp.rst:415
English
`AS1` prefers the path `AS3:AS0` over all other paths
0/530 · 53
110
../../protocols/bgp.rst:416
English
`AS3` prefers the path `AS4:AS0` over all other paths
0/530 · 53
111
../../protocols/bgp.rst:417
English
`AS4` prefers the path `AS1:AS0` over all other paths
0/530 · 53
112
../../protocols/bgp.rst:419
English
`AS0` sends `U(p,AS0)` to `AS1`, `AS3` and `AS4`. As this is the only route known by `AS1`, `AS3` and `AS4` towards `p`, they all select the direct path. Let us now consider one possible exchange of BGP messages :
0/2130 · 213
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