draft-ietf-grow-bgp-wedgies-00.txt   draft-ietf-grow-bgp-wedgies-01.txt 
Grow T. Griffin GROW T. Griffin
Internet-Draft Intel Internet-Draft University of Cambridge
Expires: April 5, 2005 G. Huston Expires: September 27, 2004 G. Huston
APNIC APNIC
October 5, 2004 March 29, 2004
BGP Wedgies BGP Wedgies
draft-ietf-grow-bgp-wedgies-00.txt draft-ietf-grow-bgp-wedgies-01.txt
Status of this Memo Status of this Memo
This document is an Internet-Draft and is subject to all provisions This document is an Internet-Draft and is subject to all provisions
of section 3 of RFC 3667. By submitting this Internet-Draft, each of section 3 of RFC 3667. By submitting this Internet-Draft, each
author represents that any applicable patent or other IPR claims of author represents that any applicable patent or other IPR claims of
which he or she is aware have been or will be disclosed, and any of which he or she is aware have been or will be disclosed, and any of
which he or she become aware will be disclosed, in accordance with which he or she become aware will be disclosed, in accordance with
RFC 3668. RFC 3668.
skipping to change at page 1, line 37 skipping to change at page 1, line 37
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on April 5, 2005. This Internet-Draft will expire on September 27, 2004.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2004). Copyright (C) The Internet Society (2004).
Abstract Abstract
It has commonly been assumed that the Border Gateway Protocol (BGP) It has commonly been assumed that the Border Gateway Protocol (BGP)
is a tool for distributing reachability information in a manner that is a tool for distributing reachability information in a manner that
creates forwarding paths in a deterministic manner. In this memo we creates forwarding paths in a deterministic manner. In this memo we
will describe a class of BGP configurations for which there is more will describe a class of BGP configurations for which there is more
than one potential outcome, and where forwarding states other than than one potential outcome, and where forwarding states other than
the intended state are equally stable, and that the stable state the intended state are equally stable, and that the stable state
where BGP converges may be selected by BGP in a non-deterministic where BGP converges may be selected by BGP in a non-deterministic
manner. These stable, but unintended, BGP states are termed here manner. These stable, but unintended, BGP states are termed here
"BGP Wedgies". "BGP Wedgies".
1. Introduction 1. Introduction
It has commonly been assumed that the Border Gateway Protocol (BGP) It has commonly been assumed that the Border Gateway Protocol (BGP)
[1] is a tool for distributing reachability information in a manner [RFC1771] is a tool for distributing reachability information in a
that creates forwarding paths in a deterministic manner. This is a manner that creates forwarding paths in a deterministic manner. This
'problem statement' memo that describes a class of BGP configurations is a 'problem statement' memo that describes a class of BGP
for which there is more than one stable forwarding state. In this configurations for which there is more than one stable forwarding
class of configurations forwarding states other than the intended state. In this class of configurations forwarding states other than
state are equally stable, and the stable state where BGP converges the intended state are equally stable, and the stable state where BGP
may be selected by BGP in a non-deterministic manner. converges may be selected by BGP in a non-deterministic manner.
These stable, but unintended, BGP states are termed here "BGP These stable, but unintended, BGP states are termed here "BGP
Wedgies". Wedgies".
2. Describing BGP Routing Policy 2. Describing BGP Routing Policy
BGP routing policies generally reflect each network administrator's BGP routing policies generally reflect each network administrator's
objective to optimize their position with respect to their network's objective to optimize their position with respect to their network's
cost, performance and reliability. cost, performance and reliability.
skipping to change at page 3, line 15 skipping to change at page 3, line 15
It is possible to express this primary / backup policy using local AS It is possible to express this primary / backup policy using local AS
path prepending, where the AS path is artificially lengthened towards path prepending, where the AS path is artificially lengthened towards
the backup providers, using additional instances of the local AS. the backup providers, using additional instances of the local AS.
This is not a deterministic selection algorithm, as the selected This is not a deterministic selection algorithm, as the selected
primary provider may in turn be using AS path prepending to its primary provider may in turn be using AS path prepending to its
backup upstream provider, and in certain cases the path through the backup upstream provider, and in certain cases the path through the
backup provider may still be selected as the shortest AS path length. backup provider may still be selected as the shortest AS path length.
An alternative approach to routing policy specification uses BGP An alternative approach to routing policy specification uses BGP
communities [2]. In this case the provider publishes a set of communities [RFC1997]. In this case the provider publishes a set of
community values that allows the client to select the provider's community values that allows the client to select the provider's
local preference. The client can use a community to mark a route as local preference setting. The client can use a community to mark a
"backup only" towards the backup provider, and "primary preferred' to route as "backup only" towards the backup provider, and "primary
the primary provider. In this case the local preference overrides preferred' to the primary provider, assuming both providers suppoprt
the AS path length metric, so that if the route is marked "backup community values with such semantics. In this case the local
only", the route will be selected only when there is no other source preference overrides the AS path length metric, so that if the route
of the route. is marked "backup only", the route will be selected only when there
is no other source of the route.
3. BGP Wedgies 3. BGP Wedgies
The richness of local policy expression through the use of The richness of local policy expression through the use of
communities, when coupled with the behavior of a distance vector communities, when coupled with the behavior of a distance vector
protocol like BGP leads to the observation that certain protocol like BGP leads to the observation that certain
configurations have more than one "solution", or more than one stable configurations have more than one "solution", or more than one stable
BGP state. An example of such a situation is indicated in Figure 1. BGP state. An example of such a situation is indicated in Figure 1.
+----+ +----+ +----+ +----+
skipping to change at page 4, line 22 skipping to change at page 4, line 22
the AS3 advertisement over the AS1 advertisement. the AS3 advertisement over the AS1 advertisement.
This is the intended outcome of AS1's policy settings, where no This is the intended outcome of AS1's policy settings, where no
traffic passes from AS2 to AS1, and AS2, reaches AS1 via a path that traffic passes from AS2 to AS1, and AS2, reaches AS1 via a path that
transits AS3 and AS4. transits AS3 and AS4.
This intended outcome is achieved as long as AS1 announces its routes This intended outcome is achieved as long as AS1 announces its routes
on the primary path, to AS4, before announcing its backup routes to on the primary path, to AS4, before announcing its backup routes to
AS2. AS2.
If the AS1 AS4 path is broken AS4 will withdraw its advertisement of If the AS1 - AS4 path is broken, causing aBGP sesssion failure
between AS1 and AS4, then AS4 will withdraw its advertisement of
AS1's routes to AS3, who, in turn will send a withdrawal to AS2. AS1's routes to AS3, who, in turn will send a withdrawal to AS2.
As2, will then select the backup path to AS1. AS2 will advertise As2, will then select the backup path to AS1. AS2 will advertise
this path to AS3, and AS3 will advertise this path to AS4. Again, this path to AS3, and AS3 will advertise this path to AS4. Again,
this is part of the intended operation of the primary / backup policy this is part of the intended operation of the primary / backup policy
setting. setting.
When connectivity between AS4 and AS1 is restored the BGP state will When connectivity between AS4 and AS1 is restored the BGP state will
not revert to the original state. AS4 will learn the primary path to not revert to the original state. AS4 will learn the primary path to
AS1, and readvertise this to AS3 using the path "AS4, AS1". AS3, AS1, and readvertise this to AS3 using the path "AS4, AS1". AS3,
using a default preference of preferring customer-advertised routes using a default preference of preferring customer-advertised routes
skipping to change at page 5, line 38 skipping to change at page 5, line 38
traffic for addresses in the range 192.9.200.128/25 from AS2. traffic for addresses in the range 192.9.200.128/25 from AS2.
In this case if the link between AS3 and AS4 is reset, AS3 will learn In this case if the link between AS3 and AS4 is reset, AS3 will learn
both routes from AS2, and AS4 will learn both routes from AS5. As both routes from AS2, and AS4 will learn both routes from AS5. As
these customer routes are preferred over peer routes, when the link these customer routes are preferred over peer routes, when the link
between AS3 and AS4 is restored, neither AS will alter its routing between AS3 and AS4 is restored, neither AS will alter its routing
behavior with respect to AS1's routes. This situation is now wedged, behavior with respect to AS1's routes. This situation is now wedged,
in that there is no eBGP peering that can be reset that will flip BGP in that there is no eBGP peering that can be reset that will flip BGP
back to the intended state. This is an instance of a BGP Wedgie. back to the intended state. This is an instance of a BGP Wedgie.
The mediation is that AS1 has to withdraw the backup advertisements The restoration path here is that AS1 has to withdraw the backup
on both paths and then operate for an interval without backup, and advertisements on both paths and operate for an interval without
then readvertise the prefixes. The length of the interval cannot be backup, and then readvertise the backup prefix advertisements. The
readily determined in advance, as it has to be sufficiently long so length of the interval cannot be readily determined in advance, as it
as to allow AS2 and AS5 to learn of an alternate path to AS1. At has to be sufficiently long so as to allow AS2 and AS5 to learn of an
this stage the backup routes can be readvertised. alternate path to AS1. At this stage the backup routes can be
readvertised.
4. Multi-Party BGP Wedgies 4. Multi-Party BGP Wedgies
This situation can be more complex when three or more parties provide This situation can be more complex when three or more parties provide
upstream transit services to an AS. An example is indicated in upstream transit services to an AS. An example is indicated in
Figure 3. Figure 3.
+----+ +----+ +----+ +----+
|AS 3|----------------|AS 4| |AS 3|----------------|AS 4|
+----+ peer peer +----+ +----+ peer peer +----+
||provider |providerS ||provider |provider
|+-----------+ | |+-----------+ |
|customer |customer | |customer |customer |
+----+ +----+ | +----+ +----+ |
|AS 2|-------|AS 5| | |AS 2|-------|AS 5| |
+----+ peer +----+ | +----+ peer +----+ |
|provider |provider | |provider |provider |
| | | | | |
|customer +-+customer |customer |customer +-+customer |customer
+-------+ |+----------+ +-------+ |+----------+
backup| ||primary backup| ||primary
skipping to change at page 8, line 29 skipping to change at page 8, line 29
forwarding agent, allowing routing information to be modified, forwarding agent, allowing routing information to be modified,
deleted or false information to be inserted without the knowledge of deleted or false information to be inserted without the knowledge of
the originator of the routing information or any of the recipients. the originator of the routing information or any of the recipients.
The memo proposes no modifications to the BGP protocol, nor does it The memo proposes no modifications to the BGP protocol, nor does it
propose any changes to the manner of deployment of BGP, and therefore propose any changes to the manner of deployment of BGP, and therefore
introduces no new factors in terms of the security and integrity of introduces no new factors in terms of the security and integrity of
inter-domain routing. inter-domain routing.
The memo illustrates that in attempting to create policy-based The memo illustrates that in attempting to create policy-based
outcomes relalting to path selection for incoming traffic it is outcomes relating to path selection for incoming traffic it is
possible to generate BGP configurations where there are multiple possible to generate BGP configurations where there are multiple
stable outcomes, rather than a single outcome. Furthermore, of these stable outcomes, rather than a single outcome. Furthermore, of these
instances of multiple outcomes, there are cases where the BGP instances of multiple outcomes, there are cases where the BGP
selection of a particular outcome is not a deterministic selection. selection of a particular outcome is not a deterministic selection.
7. References 7. References
7.1 Normative References 7.1 Normative References
[1] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)", [RFC1771] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4
RFC 1771, March 1995. (BGP-4)", RFC 1771, March 1995.
7.2 Informative References 7.2 Informative References
[2] Chandrasekeran, R., Traina, P. and T. Li, "BGP Communities [RFC1997] Chandrasekeran, R., Traina, P. and T. Li, "BGP Communities
Attribute", RFC 1997, August 1996. Attribute", RFC 1997, August 1996.
Authors' Addresses Authors' Addresses
Tim Griffin Tim Griffin
Intel Research Cambridge University of Cambridge
EMail: Tim.Griffin@intel.com EMail: Timothy.Griffin@cl.cam.ac.uk
Geoff Huston Geoff Huston
Asia Pacific Network Information Centre Asia Pacific Network Information Centre
EMail: gih@apnic.net EMail: gih@apnic.net
Intellectual Property Statement Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/