[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02

Inter-Domain Routing                                      I. van Beijnum
Internet-Draft                                            IMDEA Networks
Expires: September 10, 2009                                    R. Winter
                                                         NEC Labs Europe
                                                           March 9, 2009


                     A BGP Inter-AS Cost Attribute
                      draft-van-beijnum-idr-iac-02

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on September 10, 2009.

Copyright Notice

   Copyright (c) 2009 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents in effect on the date of
   publication of this document (http://trustee.ietf.org/license-info).
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.

Abstract

   Although BGP implementations have extensive path selection
   algorithms, in practice operators have trouble performing



van Beijnum & Winter   Expires September 10, 2009               [Page 1]


Internet-Draft              BGP Inter-AS Cost                 March 2009


   satisfactory traffic engineering of incoming traffic based on BGP
   attributes that are taken into account in the path selection
   algorithm alone.  For this reason, many ASes deaggregate their
   address range(s) into smaller blocks and announce these blocks
   differently to different neighboring ASes in order to arrive at the
   desired traffic flow.  This practice contributes to the growth of the
   global routing table, which drives up capital expenditures for
   networks engaging in inter-domain routing.  This memo introduces a
   new inter-domain metric that supports finer-grained traffic
   engineering than current BGP attributes.


1.  Introduction

   An origin AS today has no appropriate means to express preference of
   a certain path leading towards it, as the BGP decision process is not
   designed to take such preference into account.  The two sole means an
   origin AS has in order to influence the way traffic enters its
   network are either prefix disaggregation - resulting in global
   routing table growth - or AS path prepending - a very imprecise
   method.  It's easy to see how comparing AS paths lengths is
   problematic in today's flat AS hierarchy.  Assume 10 tier-1 ISPs that
   can reach all destinations connected to the internet through peering,
   and assume that the local AS buys transit service from two tier-1
   ISPs.  The traffic to the customers of those ISPs will normally flow
   through the respective ISP.  However, for all destinations reachable
   over the 8 other tier-1s, the AS paths will have the same length over
   both transit ISPs.  This means that prepending the AS path towards
   one ISP has a very dramatic effect: as much as 80% of all traffic may
   subsequently flow over the non-prepended ISP.  A similar situation
   can occur in more complex types of connectivity.  With a finer-
   grained value that is communicated across ASes this problem would be
   reduced.

   This memo proposes such a finer-grained inter-AS metric: the inter-AS
   cost (IAC).  With this metric, it is possible for destinations of
   traffic to make precise adjustments to the metrics seen by the
   sources of traffic and thus make it possible to arrive at more
   favorable load sharing ratios between multiple links to different
   ASes without having to resort to the advertisement of more specific
   prefixes.

   In the past, efforts somewhat similar to this have been undertaken.
   In 1995, [I-D.antonov-bgp-metrics] proposed new per-hop BGP metrics.
   However, this proposal suffered from high complexity and a resulting
   risk of unforeseen consequences.  A year later, [I-D.chen-bgp-dpa]
   proposed a new inter-AS metric for the purpose of allowing symmetric
   routing and load sharing.  This proposal wasn't fleshed out in much



van Beijnum & Winter   Expires September 10, 2009               [Page 2]


Internet-Draft              BGP Inter-AS Cost                 March 2009


   detail.

   Neither proposal specifically addressed the issue of granularity in
   an inter-AS metric.

   Note that the definition of IAC and IAClocal have been fundamentally
   changed since version -01 of this draft.  See the end of the document
   for more information about the changes.


2.  IAC and IAClocal

   The new metric is named Inter-AS Cost (IAC) which is added by the
   origin AS as an optional transitive attribute to the prefix
   announcement.  The content of the IAC is an 8-bit signed value that
   represents the relative cost or preference towards the source of the
   associated prefix compared to other paths for reaching the same
   prefix.  However, to avoid small changes in IAC from having a very
   large effect, like prepending the AS path by one AS hop has a very
   large effect today, a randomization component is introduced.  The
   IAC, the randomization component and optionally a local cost towards
   the next hop together make up the IAClocal value, which is used to
   compare prefixes.

   The randomization component is computed by XORing all the octets in
   the AS numbers of the source of the announcement, the next hop AS and
   the local AS.  The resulting 8-bit value R is subsequently
   interpreted as a signed value with possible values -128 to 127.  The
   randomization component R makes sure that even when no policy is
   applied, destinations with the same properties will be preferred
   through different next hop addresses, and that different ASes make
   this selection differently, so there is a (very roughly) equal
   distribution of traffic over different links, both for the sending
   and the receiving ASes.

   The optional local cost (LC) is an integer that can take the values
   between -256 and 255.  Its purpose is to give some control to the
   local AS is case the comparison of the computed local is unfavorable
   for the local AS.  It has to be noted that the local AS has other
   means than the IAClocal to accomplish outbound traffic engineering:
   the LOCAL_PREF.

   IAClocal is computed as follows:

   IAClocal = IAC * 2 + R (+ LC)

   Hence, IAClocal can be an integer value between -640 and 636.  Any
   IAClocal values outside this range MUST lead to the presence of the



van Beijnum & Winter   Expires September 10, 2009               [Page 3]


Internet-Draft              BGP Inter-AS Cost                 March 2009


   IAClocal attribute being ignored.  The IAClocal is stored as a 16-bit
   signed value in network byte order in the IAC BGP path attribute.
   The new IAC path attribute is an optional transitive attribute that
   can take two forms: over eBGP, the attribute only contains the IAC.
   When communicated through iBGP, the attribute both contains the IAC
   and the IAClocal, in that order.  When a router generates a route
   locally for announcement over BGP, an IAC of 0 MAY be included.
   However, it is recommended that an IAC attribute is only generated
   when an IAC is specified in the configuration.  A missing IAC is
   semantically distinct from an IAC of 0, so configuring a 0 IAC MUST
   result in the inclusion of the IAC attribute.

   The IAClocal is computed by the router receiving a prefix containing
   the IAC attribute over eBGP, or when sourcing a prefix advertisement.
   If no IAC attribute is received over eBGP, a router MUST NOT create
   one, and no IAClocal is computed.  The IAClocal MUST NOT be computed
   when no IAC attribute is present.

   In the BGP route selection algorithm, the IAClocal is compared
   immediately following the comparison of the IGP cost.  As such, the
   IAClocal is only considered for routes that have identical
   LOCAL_PREF, AS_PATH, possibly MED and learned over eBGP/iBGP
   properties and more.  For these routes, without IAClocal, route
   selection would come down to the last two tie breaking steps.  In
   addition, the IAClocal is only considered when all the routes under
   consideration at this point in the selection process contain the IAC
   attribute holding an IAClocal value.  If the IAClocal is considered,
   the route with the highest IAClocal is selected.  If there are
   multiple routes that share the highest IAClocal, the remaining tie
   breaking rules are executed over the routes sharing the highest
   IAClocal.

   WARNING:

   In iBGP, there is no loop detection.  As such, loops may occur when
   the tie breaking rules aren't implemented identically by all iBGP
   routers.  Consider the following topology:

   R1 --- R2 --- R3 --- R4

   If R1 and R4 have external routes towards a destination, and the IGP
   costs that R2 and R3 see over both R1 and R4 are identical, it would
   be possible for R2 to prefer the path over R4 because of the
   IAClocal, but if R3 doesn't implement the IAC attribute, it may
   prefer the path over R1 because of the existing tie breaking rules.

   This situation may occur when not all routers in an AS support the
   IAC attribute, and next hop addresses for eBGP routes are



van Beijnum & Winter   Expires September 10, 2009               [Page 4]


Internet-Draft              BGP Inter-AS Cost                 March 2009


   redistributed in the IGP using a metric that doesn't take the
   interior hops into account, such as the OSPF external type 1 metric.
   For this reason, operators MUST avoid redistributing connected
   interfaces as E1 in OSPF (or similar in other IGPs) if there is a
   mixed IAC-capable and non-IAC-capable environment in the AS.


3.  Usage guidelines

   If the distribution of AS path lengths between two or more links
   towards the rest of the internet is equal, then the randomization
   factor should make the traffic distribution between different links
   very roughly equal.  Suppose there are two links, and a traffic
   distribution of 1 : 2 (33% vs 67%) is desired.  This means that for
   67 - 33 = 34% of the ASes the route selection must be pushed towards
   the other link using the IAClocal.  That means a difference of 127 *
   34% = 43 in IAC between the route announced over the first link and
   the same route announced over the second link.  This can be
   accomplished with an IAC of +43 on the first and 0 on the second link
   or -43 on the second link and 0 on the first, or any other
   combination of IACs with a difference of 43.

   However, in practice the new traffic distribution will probably not
   be immediately equal to what's desired, so additional adjustments
   will likely be necessary.  Those can be based on the difference
   between the observed traffic distribution and the desired traffic
   distribution.  So if the difference is 10%, the difference in IACs
   can be increased or decreased by 10%.  Other heuristics may prove
   useful in practice.


4.  Changes

   In the previous versions of this draft, the IAC replaced the AS path
   length in the path selection algorithm.  We changed this for two
   reasons.  The first is that the differences in path selection between
   routers that do and routers that don't support the IAC would be too
   large in this situation, making for a very challenging deployment
   scenario.  The second reason is because we believe that there is no
   real reason for intermediate ASes to update the IAC.  Intermediate
   ASes are almost always ISPs, which as a rule don't have a need for
   additional mechanisms to balance traffic between outgoing paths
   towards the same destination.  By having the IAC be considered after
   the IGP cost, existing mechanisms that ISPs use to influence the BGP
   traffic flow, such as manipulating MEDs and IGP costs, are
   maintained.





van Beijnum & Winter   Expires September 10, 2009               [Page 5]


Internet-Draft              BGP Inter-AS Cost                 March 2009


5.  IANA considerations

   IANA is requested to allocate a BGP optional transitive attribute
   type code.


6.  Security considerations

   As the IAClocal is compared so late in the BGP route selection
   process, there is little chance of the presence of the IAC being a
   security risk, other than the potential for iBGP loops as outlined
   earlier.

   It is highly recommended that implementers include a mechanism to
   remove the IAC attribute in incoming or outgoing BGP updates.  This
   mechanism MUST be disabled by default.


7.  References

7.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC4271]  Rekhter, Y., Li, T., and S. Hares, "A Border Gateway
              Protocol 4 (BGP-4)", RFC 4271, January 2006.

7.2.  Informational References

   [I-D.chen-bgp-dpa]
              Chen, E. and T. Bates, "Destination Preference Attribute
              for BGP", draft-ietf-idr-bgp-dpa-05 (work in progress),
              September 1996.

   [I-D.antonov-bgp-metrics]
              Antonov, V., "BGP AS Path Metrics",
              draft-ietf-idr-bgp-metrics-00 (work in progress),
              March 1995.


Appendix A.  Document and discussion information

   The latest version of this document will always be available at
   http://www.muada.com/drafts/.  Please direct questions and comments
   to the idr or grow mailinglists or directly to the authors.





van Beijnum & Winter   Expires September 10, 2009               [Page 6]


Internet-Draft              BGP Inter-AS Cost                 March 2009


Appendix B.  Acknowledgement

   Rolf Winter and Iljitsch van Beijnum are partly funded by Trilogy, a
   research project supported by the European Commission under its
   Seventh Framework Program.


Authors' Addresses

   Iljitsch van Beijnum
   IMDEA Networks
   Avda. del Mar Mediterraneo, 22
   Leganes, Madrid  28918
   Spain

   Email: iljitsch@muada.com


   Rolf Winter
   NEC Labs Europe
   Kurfuersten-Anlage 36
   Heidelberg  69115
   Germany

   Email: rolf.winter@nw.neclab.eu


























van Beijnum & Winter   Expires September 10, 2009               [Page 7]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/