rfc1774.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 564 行 · 第 1/2 页

Network Working Group                                  P. Traina, Editor
Request for Comments: 1774                                 cisco Systems
Category: Informational                                       March 1995

                        BGP-4 Protocol Analysis

Status of this Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Introduction

   The purpose of this report is to document how the requirements for
   advancing a routing protocol to Draft Standard have been satisfied by
   the Border Gateway Protocol version 4 (BGP-4). This report summarizes
   the key features of BGP, and analyzes the protocol with respect to
   scaling and performance. This is the first of two reports on the BGP
   protocol.

   BGP-4 is an inter-autonomous system routing protocol designed for
   TCP/IP internets.  Version 1 of the BGP protocol was published in RFC
   1105. Since then BGP versions 2, 3, and 4 have been developed.
   Version 2 was documented in RFC 1163. Version 3 is documented in
   RFC1267.  The changes between versions are explained in Appendix 2 of
   [1].

   Possible applications of BGP in the Internet are documented in [2].

   Please send comments to [e-mail].

Key features and algorithms of the BGP-4 protocol.

   This section summarizes the key features and algorithms of the BGP
   protocol. BGP is an inter-autonomous system routing protocol; it is
   designed to be used between multiple autonomous systems. BGP assumes
   that routing within an autonomous system is done by an intra-
   autonomous system routing protocol. BGP does not make any assumptions
   about intra-autonomous system routing protocols employed by the
   various autonomous systems.  Specifically, BGP does not require all
   autonomous systems to run the same intra-autonomous system routing
   protocol.

   BGP is a real inter-autonomous system routing protocol. It imposes no
   constraints on the underlying Internet topology. The information
   exchanged via BGP is sufficient to construct a graph of autonomous
   systems connectivity from which routing loops may be pruned and some



Traina                                                          [Page 1]

RFC 1774                BGP-4 Protocol Analysis               March 1995


   routing policy decisions at the autonomous system level may be
   enforced.

   The key features of the protocol are the notion of path attributes
   and aggregation of network layer reachability information (NLRI).

   Path attributes provide BGP with flexibility and expandability. Path
   attributes are partitioned into well-known and optional. The
   provision for optional attributes allows experimentation that may
   involve a group of BGP routers without affecting the rest of the
   Internet.  New optional attributes can be added to the protocol in
   much the same fashion as new options are added to the Telnet
   protocol, for instance.

   One of the most important path attributes is the AS-PATH. AS
   reachability information traverses the Internet, this information is
   augmented by the list of autonomous systems that have been traversed
   thus far, forming the AS-PATH.  The AS-PATH allows straightforward
   suppression of the looping of routing information. In addition, the
   AS-PATH serves as a powerful and versatile mechanism for policy-based
   routing.

   BGP-4 enhances the AS-PATH attribute to include sets of autonomous
   systems as well as lists.  This extended format allows generated
   aggregate routes to carry path information from the more specific
   routes used to generate the aggregate.

   BGP uses an algorithm that cannot be classified as either a pure
   distance vector, or a pure link state. Carrying a complete AS path in
   the AS-PATH attribute allows to reconstruct large portions of the
   overall topology. That makes it similar to the link state algorithms.
   Exchanging only the currently used routes between the peers makes it
   similar to the distance vector algorithms.

   To conserve bandwidth and processing power, BGP uses incremental
   updates, where after the initial exchange of complete routing
   information, a pair of BGP routers exchanges only changes (deltas) to
   that information. Technique of incremental updates requires reliable
   transport between a pair of BGP routers. To achieve this
   functionality BGP uses TCP as its transport.

   In addition to incremental updates, BGP-4 has added the concept of
   route aggregation so that information about groups of networks may
   represented as a single entity.

   BGP is a self-contained protocol. That is, it specifies how routing
   information is exchanged both between BGP speakers in different
   autonomous systems, and between BGP speakers within a single



Traina                                                          [Page 2]

RFC 1774                BGP-4 Protocol Analysis               March 1995


   autonomous system.

   To allow graceful coexistence with EGP and OSPF, BGP provides support
   for carrying both EGP and OSPF derived exterior routes BGP also
   allows to carry statically defined exterior routes or routes derived
   by other IGP information.

BGP performance characteristics and scalability

   In this section we'll try to answer the question of how much link
   bandwidth, router memory and router CPU cycles does the BGP protocol
   consume under normal conditions.  We'll also address the scalability
   of BGP, and look at some of its limits.

   BGP does not require all the routers within an autonomous system to
   participate in the BGP protocol. Only the border routers that provide
   connectivity between the local autonomous system and its adjacent
   autonomous systems participate in BGP.  Constraining the set of
   participants is just one way of addressing the scaling issue.

Link bandwidth and CPU utilization

   Immediately after the initial BGP connection setup, the peers
   exchange complete set of routing information. If we denote the total
   number of routes in the Internet by N, the mean AS distance of the
   Internet by M (distance at the level of an autonomous system,
   expressed in terms of the number of autonomous systems), the total
   number of autonomous systems in the Internet by A, and assume that
   the networks are uniformly distributed among the autonomous systems,
   then the worst case amount of bandwidth consumed during the initial
   exchange between a pair of BGP speakers is

                    MR = O(N + M * A)

   The following table illustrates typical amount of bandwidth consumed
   during the initial exchange between a pair of BGP speakers based on
   the above assumptions (ignoring bandwidth consumed by the BGP
   Header).

   # NLRI       Mean AS Distance       # AS's    Bandwidth
   ----------   ----------------       ------    ---------
   10,000       15                     300       49,000 bytes
   20,000       8                      400       86,000 bytes *
   40,000       15                     400       172,000 bytes
   100,000      20                     3,000     520,000 bytes

   * the actual "size" of the Internet at the the time of this
     document's publication



Traina                                                          [Page 3]

RFC 1774                BGP-4 Protocol Analysis               March 1995


   Note that most of the bandwidth is consumed by the exchange of the
   Network Layer Reachability Information (NLRI).

   BGP-4 was created specifically to reduce the amount of NLRI entries
   carried and exchanged by border routers.  BGP-4, along with CIDR [4]
   has introduced the concept of the "Supernet" which describes a
   power-of-two aggregation of more than one class-based network.

   Due to the advantages of advertising a few large aggregate blocks
   instead of many smaller class-based individual networks, it is
   difficult to estimate the actual reduction in bandwidth and
   processing that BGP-4 has provided over BGP3.  If we simply enumerate
   all aggregate blocks into their individual class-based networks, we
   would not take into account "dead" space that has been reserved for
   future expansion.  The best metric for determining the success of
   BGP-4's aggregation is to sample the number NLRI entries in the
   globally connected Internet today and compare it to projected growth
   rates before BGP-4 was deployed.

   In January of 1994, router carrying a full routing load for the
   globally connected Internet had approximately 19,000 network entries
   (this number is not exact due to local policy variations).  The BGP
   deployment working group estimated that the growth rate at that time
   was over 1000 new networks per month and increasing.  Since the
   widespread deployment of BGP-4, the growth rate has dropped
   significantly and a sample done at the end of November 1994 showed
   approximately 21,000 entries present,  as opposed to the expected
   30,000.

   CPU cycles consumed by BGP depends only on the stability of the
   Internet. If the Internet is stable, then the only link bandwidth and
   router CPU cycles consumed by BGP are due to the exchange of the BGP
   KEEPALIVE messages. The KEEPALIVE messages are exchanged only between
   peers. The suggested frequency of the exchange is 30 seconds. The
   KEEPALIVE messages are quite short (19 octets), and require virtually
   no processing.  Therefore, the bandwidth consumed by the KEEPALIVE
   messages is about 5 bits/sec.  Operational experience confirms that
   the overhead (in terms of bandwidth and CPU) associated with the
   KEEPALIVE messages should be viewed as negligible.  If the Internet
   is unstable, then only the changes to the reachability information
   (that are caused by the instabilities) are passed between routers
   (via the UPDATE messages). If we denote the number of routing changes
   per second by C, then in the worst case the amount of bandwidth
   consumed by the BGP can be expressed as O(C * M). The greatest
   overhead per UPDATE message occurs when each UPDATE message contains
   only a single network. It should be pointed out that in practice
   routing changes exhibit strong locality with respect to the AS path.
   That is routes that change are likely to have common AS path. In this



Traina                                                          [Page 4]

RFC 1774                BGP-4 Protocol Analysis               March 1995


   case multiple networks can be grouped into a single UPDATE message,
   thus significantly reducing the amount of bandwidth required (see
   also Appendix 6.1 of [1]).

   Since in the steady state the link bandwidth and router CPU cycles
   consumed by the BGP protocol are dependent only on the stability of
   the Internet, but are completely independent on the number of
   networks that compose the Internet, it follows that BGP should have
   no scaling problems in the areas of link bandwidth and router CPU
   utilization, as the Internet grows, provided that the overall
   stability of the inter-AS connectivity (connectivity between ASs) of
   the Internet can be controlled. Stability issue could be addressed by
   introducing some form of dampening (e.g., hold downs).  Due to the
   nature of BGP, such dampening should be viewed as a local to an
   autonomous system matter (see also Appendix 6.3 of [1]). It is
   important to point out, that regardless of BGP, one should not
   underestimate the significance of the stability in the Internet.

   Growth of the Internet has made the stability issue one of the most
   crucial ones. It is important to realize that BGP, by itself, does
   not introduce any instabilities in the Internet. Current observations
   in the NSFNET show that the instabilities are largely due to the
   ill-behaved routing within the autonomous systems that compose the
   Internet.  Therefore, while providing BGP with mechanisms to address
   the stability issue, we feel that the right way to handle the issue
   is to address it at the root of the problem, and to come up with
   intra-autonomous routing schemes that exhibit reasonable stability.

   It also may be instructive to compare bandwidth and CPU requirements
   of BGP with EGP. While with BGP the complete information is exchanged
   only at the connection establishment time, with EGP the complete
   information is exchanged periodically (usually every 3 minutes). Note
   that both for BGP and for EGP the amount of information exchanged is
   roughly on the order of the networks reachable via a peer that sends
   the information (see also Section 5.2). Therefore, even if one
   assumes extreme instabilities of BGP, its worst case behavior will be
   the same as the steady state behavior of EGP.

   Operational experience with BGP showed that the incremental updates
   approach employed by BGP presents an enormous improvement both in the
   area of bandwidth and in the CPU utilization, as compared with
   complete periodic updates used by EGP (see also presentation by
   Dennis Ferguson at the Twentieth IETF, March 11-15, 1991, St.Louis).








Traina                                                          [Page 5]