home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc1265 < prev    next >
Text File  |  1991-11-05  |  21KB  |  451 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                 Y. Rekhter, Editor
  8. Request for Comments: 1265        T.J. Watson Research Center, IBM Corp.
  9.                                                             October 1991
  10.  
  11.  
  12.                          BGP Protocol Analysis
  13.  
  14. 1. Status of this Memo.
  15.  
  16.    This memo provides information for the Internet community. It does
  17.    not specify an Internet standard. Distribution of this memo is
  18.    unlimited.
  19.  
  20. 2. Introduction.
  21.  
  22.    The purpose of this report is to document how the requirements for
  23.    advancing a routing protocol to Draft Standard have been satisfied by
  24.    the Border Gateway Protocol (BGP). This report summarizes the key
  25.    feature of BGP, and analyzes the protocol with respect to scaling and
  26.    performance. This is the first of two reports on the BGP protocol.
  27.  
  28.    BGP is an inter-autonomous system routing protocol designed for the
  29.    TCP/IP internets.  Version 1 of the BGP protocol was published in RFC
  30.    1105. Since then BGP versions 2 and 3 have been developed.  Version 2
  31.    was documented in RFC 1163. Version 3 is documented in [1]. The
  32.    changes between versions 1, 2 and 3 are explained in Appendix 3 of
  33.    [1].
  34.  
  35.    Possible applications of BGP in the Internet are documented in [2].
  36.  
  37.    Please send comments to iwg@rice.edu.
  38.  
  39. 3. Acknowledgements.
  40.  
  41.    The BGP protocol has been developed by the IWG/BGP Working Group of
  42.    the Internet Engineering Task Force. We would like to express our
  43.    deepest thanks to Guy Almes (Rice University) who was the previous
  44.    chairman of the IWG Working Group.  We also like to explicitly thank
  45.    Bob Braden (ISI) and Bob Hinden (BBN) for the review of this document
  46.    as well as their constructive and valuable comments.
  47.  
  48. 4. Key features and algorithms of the BGP protocol.
  49.  
  50.    This section summarizes the key features and algorithms of the BGP
  51.    protocol. BGP is an inter-autonomous system routing protocol; it is
  52.    designed to be used between multiple autonomous systems. BGP assumes
  53.    that routing within an autonomous system is done by an intra-
  54.    autonomous system routing protocol. BGP does not make any assumptions
  55.  
  56.  
  57.  
  58. BGP Working Group                                               [Page 1]
  59.  
  60. RFC 1265                 BGP Protocol Analysis              October 1991
  61.  
  62.  
  63.    about intra-autonomous system routing protocols employed by the
  64.    various autonomous systems.  Specifically, BGP does not require all
  65.    autonomous systems to run the same intra-autonomous system routing
  66.    protocol.
  67.  
  68.    BGP is a real inter-autonomous system routing protocol. It imposes no
  69.    constraints on the underlying Internet topology. The information
  70.    exchanged via BGP is sufficient to construct a graph of autonomous
  71.    systems connectivity from which routing loops may be pruned and some
  72.    routing policy decisions at the autonomous system level may be
  73.    enforced.
  74.  
  75.    The key feature of the protocol is the notion of Path Attributes.
  76.    This feature provides BGP with flexibility and expandability. Path
  77.    attributes are partitioned into well-known and optional. The
  78.    provision for optional attributes allows experimentation that may
  79.    involve a group of BGP routers without affecting the rest of the
  80.    Internet.  New optional attributes can be added to the protocol in
  81.    much the same fashion as new options are added to the Telnet
  82.    protocol, for instance.  One of the most important path attributes is
  83.    the AS-PATH. As reachability information traverses the Internet, this
  84.    information is augmented by the list of autonomous systems that have
  85.    been traversed thusfar, forming the AS-PATH.  The AS-PATH allows
  86.    straightforward suppression of the looping of routing information. In
  87.    addition, the AS-PATH serves as a powerful and versatile mechanism
  88.    for policy-based routing.
  89.  
  90.    BGP uses an algorithm that cannot be classified as either a pure
  91.    distance vector, or a pure link state. Carrying a complete AS path in
  92.    the AS-PATH attribute allows to reconstruct large portions of the
  93.    overall topology. That makes it similar to the link state algorithms.
  94.    Exchanging only the currently used routes between the peers makes it
  95.    similar to the distance vector algorithms.
  96.  
  97.    To conserve bandwidth and processing power, BGP uses incremental
  98.    updates, where after the initial exchange of complete routing
  99.    information, a pair of BGP routers exchanges only changes (deltas) to
  100.    that information. Technique of incremental updates requires reliable
  101.    transport between a pair of BGP routers. To achieve this
  102.    functionality BGP uses TCP as its transport.
  103.  
  104.    BGP is a self-contained protocol. That is, it specifies how routing
  105.    information is exchanged both between BGP speakers in different
  106.    autonomous systems, and between BGP speakers within a single
  107.    autonomous system.
  108.  
  109.    To allow graceful coexistence with EGP, BGP provides support for
  110.    carrying EGP derived exterior routes. BGP also allows to carry
  111.  
  112.  
  113.  
  114. BGP Working Group                                               [Page 2]
  115.  
  116. RFC 1265                 BGP Protocol Analysis              October 1991
  117.  
  118.  
  119.    statically defined exterior routes.
  120.  
  121. 5. BGP performance characteristics and scalability.
  122.  
  123.    In this section we'll try to answer the question of how much link
  124.    bandwidth, router memory and router CPU cycles does the BGP protocol
  125.    consume under normal conditions.  We'll also address the scalability
  126.    of BGP, and look at some of its limits.
  127.  
  128.    BGP does not require all the routers within an autonomous system to
  129.    participate in the BGP protocol. Only the border routers that provide
  130.    connectivity between the local autonomous system and its adjacent
  131.    autonomous systems participate in BGP.  Constraining the set of
  132.    participants is just one way of addressing the scaling issue.
  133.  
  134. 5.1 Link bandwidth and CPU utilization.
  135.  
  136.    Immediately after the initial BGP connection setup, the peers
  137.    exchange complete set of routing information. If we denote the total
  138.    number of networks in the Internet by N, the mean AS distance of the
  139.    Internet by M (distance at the level of an autonomous system,
  140.    expressed in terms of the number of autonomous systems), the total
  141.    number of autonomous systems in the Internet by A, and assume that
  142.    the networks are uniformly distributed among the autonomous systems,
  143.    then the worst case amount of bandwidth consumed during the initial
  144.    exchange between a pair of BGP speakers is
  145.  
  146.                         O(N + M * A)
  147.  
  148.    (provided that an implementation supports multiple networks per
  149.    message as outlined in Appendix 5 of [1]). This information is
  150.    roughly on the order of the number of networks reachable via each
  151.    peer (see also Section 5.2).
  152.  
  153.    The following table illustrates typical amount of bandwidth consumed
  154.    during the initial exchange between a pair of BGP speakers based on
  155.    the above assumptions (ignoring bandwidth consumed by the BGP
  156.    Header).
  157.  
  158.          # Networks   Mean AS Distance       # AS's    Bandwidth
  159.          ----------   ----------------       ------    ---------
  160.          2,100        5                      59        9,000 bytes
  161.          4,000        10                     100       18,000 bytes
  162.          10,000       15                     300       49,000 bytes
  163.          100,000      20                     3,000     520,000 bytes
  164.  
  165.    Note that most of the bandwidth is consumed by the exchange of the
  166.    Network Reachability Information.
  167.  
  168.  
  169.  
  170. BGP Working Group                                               [Page 3]
  171.  
  172. RFC 1265                 BGP Protocol Analysis              October 1991
  173.  
  174.  
  175.    After the initial exchange is completed, the amount of bandwidth and
  176.    CPU cycles consumed by BGP depends only on the stability of the
  177.    Internet. If the Internet is stable, then the only link bandwidth and
  178.    router CPU cycles consumed by BGP are due to the exchange of the BGP
  179.    KEEPALIVE messages. The KEEPALIVE messages are exchanged only between
  180.    peers. The suggested frequency of the exchange is 30 seconds. The
  181.    KEEPALIVE messages are quite short (19 octets), and require virtually
  182.    no processing.  Therefore, the bandwidth consumed by the KEEPALIVE
  183.    messages is about 5 bits/sec.  Operational experience confirms that
  184.    the overhead (in terms of bandwidth and CPU) associated with the
  185.    KEEPALIVE messages should be viewed as negligible.  If the Internet
  186.    is unstable, then only the changes to the reachability information
  187.    (that are caused by the instabilities) are passed between routers
  188.    (via the UPDATE messages). If we denote the number of routing changes
  189.    per second by C, then in the worst case the amount of bandwidth
  190.    consumed by the BGP can be expressed as O(C * M). The greatest
  191.    overhead per UPDATE message occurs when each UPDATE message contains
  192.    only a single network. It should be pointed out that in practice
  193.    routing changes exhibit strong locality with respect to the AS path.
  194.    That is routes that change are likely to have common AS path. In this
  195.    case multiple networks can be grouped into a single UPDATE message,
  196.    thus significantly reducing the amount of bandwidth required (see
  197.    also Appendix 5 of [1]).
  198.  
  199.    Since in the steady state the link bandwidth and router CPU cycles
  200.    consumed by the BGP protocol are dependent only on the stability of
  201.    the Internet, but are completely independent on the number of
  202.    networks that compose the Internet, it follows that BGP should have
  203.    no scaling problems in the areas of link bandwidth and router CPU
  204.    utilization, as the Internet grows, provided that the overall
  205.    stability of the inter-AS connectivity (connectivity between ASs) of
  206.    the Internet can be controlled. Stability issue could be addressed by
  207.    introducing some form of dampening (e.g., hold downs).  Due to the
  208.    nature of BGP, such dampening should be viewed as a local to an
  209.    autonomous system matter (see also Appendix 5 of [1]). We'd like to
  210.    point out, that regardless of BGP, one should not underestimate the
  211.    significance of the stability in the Internet. Growth of the Internet
  212.    will make the stability issue one of the most crucial one. It is
  213.    important to realize that BGP, by itself, does not introduce any
  214.    instabilities in the Internet. Current observations in the NSFNET
  215.    show that the instabilities are largely due to the ill-behaved
  216.    routing within the autonomous systems that compose the Internet.
  217.    Therefore, while providing BGP with mechanisms to address the
  218.    stability issue, we feel that the right way to handle the issue is to
  219.    address it at the root of the problem, and to come up with intra-
  220.    autonomous routing schemes that exhibit reasonable stability.
  221.  
  222.    It also may be instructive to compare bandwidth and CPU requirements
  223.  
  224.  
  225.  
  226. BGP Working Group                                               [Page 4]
  227.  
  228. RFC 1265                 BGP Protocol Analysis              October 1991
  229.  
  230.  
  231.    of BGP with EGP. While with BGP the complete information is exchanged
  232.    only at the connection establishment time, with EGP the complete
  233.    information is exchanged periodically (usually every 3 minutes). Note
  234.    that both for BGP and for EGP the amount of information exchanged is
  235.    roughly on the order of the networks reachable via a peer that sends
  236.    the information (see also Section 5.2). Therefore, even if one
  237.    assumes extreme instabilities of BGP, its worst case behavior will be
  238.    the same as the steady state behavior of EGP.
  239.  
  240.    Operational experience with BGP showed that the incremental updates
  241.    approach employed by BGP presents an enormous improvement both in the
  242.    area of bandwidth and in the CPU utilization, as compared with
  243.    complete periodic updates used by EGP (see also presentation by
  244.    Dennis Ferguson at the Twentieth IETF, March 11-15, 1991, St.Louis).
  245.  
  246. 5.2 Memory requirements.
  247.  
  248.    To quantify the worst case memory requirements for BGP, denote the
  249.    total number of networks in the Internet by N, the mean AS distance
  250.    of the Internet by M (distance at the level of an autonomous system,
  251.    expressed in terms of the number of autonomous systems), the total
  252.    number of autonomous systems in the Internet by A, and the total
  253.    number of BGP speakers that a system is peering with by K (note that
  254.    K will usually be dominated by the total number of the BGP speakers
  255.    within a single autonomous system). Then the worst case memory
  256.    requirements (MR) can be expressed as
  257.  
  258.                            MR = O((N + M * A) * K)
  259.  
  260.    In the current NSFNET Backbone (N = 2110, A = 59, and M = 5) if each
  261.    network is stored as 4 octets, and each autonomous system is stored
  262.    as 2 octets then the overhead of storing the AS path information (in
  263.    addition to the full complement of exterior routes) is less than 7
  264.    percent of the total memory usage.
  265.  
  266.    It is interesting to point out, that prior to the introduction of BGP
  267.    in the NSFNET Backbone, memory requirements on the NSFNET Backbone
  268.    routers running EGP were on the order of O(N * K). Therefore, the
  269.    extra overhead in memory incurred by the NSFNET routers after the
  270.    introduction of BGP is less than 7 percent.
  271.  
  272.    Since a mean AS distance grows very slowly with the total number of
  273.    networks (there are about 60 autonomous systems, well over 2,000
  274.    networks known in the NSFNET backbone routers, and the mean AS
  275.    distance of the current Internet is well below 5), for all practical
  276.    purposes the worst case router memory requirements are on the order
  277.    of the total number of networks in the Internet times the number of
  278.    peers the local system is peering with. We expect that the total
  279.  
  280.  
  281.  
  282. BGP Working Group                                               [Page 5]
  283.  
  284. RFC 1265                 BGP Protocol Analysis              October 1991
  285.  
  286.  
  287.    number of networks in the Internet will grow much faster than the
  288.    average number of peers per router. Therefore, scaling with respect
  289.    to the memory requirements is going to be heavily dominated by the
  290.    factor that is linearly proportional to the total number of networks
  291.    in the Internet.
  292.  
  293.    The following table illustrates typical memory requirements of a
  294.    router running BGP. It is assumed that each network is encoded as 4
  295.    bytes, each AS is encoded as 2 bytes, and each networks is reachable
  296.    via some fraction of all of the peers (# BGP peers/per net).
  297.  
  298. # Networks  Mean AS Distance # AS's # BGP peers/per net Memory Req
  299. ----------  ---------------- ------ ------------------- ----------
  300. 2,100       5                59     3                   27,000 bytes
  301. 4,000       10               100    6                   108,000 bytes
  302. 10,000      15               300    10                  490,000 bytes
  303. 100,000     20               3,000  20                  1,040,000 bytes
  304.  
  305.    To put memory requirements of BGP in a proper perspective, let's try
  306.    to put aside for a moment the issue of what information is used to
  307.    construct the forwarding tables in a router, and just focus on the
  308.    forwarding tables themselves. In this case one might ask about the
  309.    limits on these tables.  For instance, given that right now the
  310.    forwarding tables in the NSFNET Backbone routers carry well over
  311.    2,000 entries, one might ask whether it would be possible to have a
  312.    functional router with a table that will have 20,000 entries. Clearly
  313.    the answer to this question is completely independent of BGP. On the
  314.    other hand the answer to the original questions (that was asked with
  315.    respect to BGP) is directly related to the latter question. Very
  316.    interesting comments were given by Paul Tsuchiya in his review of BGP
  317.    in March of 1990 (as part of the BGP review committee appointed by
  318.    Bob Hinden).  In the review he said that, "BGP does not scale well.
  319.    This is not really the fault of BGP. It is the fault of the flat IP
  320.    address space.  Given the flat IP address space, any routing protocol
  321.    must carry network numbers in its updates." To reiterate, BGP limits
  322.    with respect to the memory requirements are directly related to the
  323.    underlying Internet Protocol (IP), and specifically the addressing
  324.    scheme employed by IP. BGP would provide much better scaling in
  325.    environments with more flexible addressing schemes.  It should be
  326.    pointed out that with very minor additions BGP can be extended to
  327.    support hierarchies of autonomous system. Such hierarchies, combined
  328.    with an addressing scheme that would allow more flexible address
  329.    aggregation capabilities, can be utilized by BGP, thus providing
  330.    practically unlimited scaling capabilities of the protocol.
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338. BGP Working Group                                               [Page 6]
  339.  
  340. RFC 1265                 BGP Protocol Analysis              October 1991
  341.  
  342.  
  343. 6. Applicability of BGP.
  344.  
  345.    In this section we'll try to answer the question of what environment
  346.    is BGP well suited, and for what is it not suitable?  Partially this
  347.    question is answered in the Section 2 of [1], where the document
  348.    states the following:
  349.  
  350.    "To characterize the set of policy decisions that can be enforced
  351.    using BGP, one must focus on the rule that an AS advertises to its
  352.    neighbor ASs only those routes that it itself uses.  This rule
  353.    reflects the "hop-by-hop" routing paradigm generally used throughout
  354.    the current Internet.  Note that some policies cannot be supported by
  355.    the "hop-by-hop" routing paradigm and thus require techniques such as
  356.    source routing to enforce.  For example, BGP does not enable one AS
  357.    to send traffic to a neighbor AS intending that the traffic take a
  358.    different route from that taken by traffic originating in the
  359.    neighbor AS.  On the other hand, BGP can support any policy
  360.    conforming to the "hop-by-hop" routing paradigm.  Since the current
  361.    Internet uses only the "hop-by-hop" routing paradigm and since BGP
  362.    can support any policy that conforms to that paradigm, BGP is highly
  363.    applicable as an inter-AS routing protocol for the current Internet."
  364.  
  365.    While BGP is well suitable for the current Internet, it is also
  366.    almost a necessity for the current Internet as well.  Operational
  367.    experience with EGP showed that it is highly inadequate for the
  368.    current Internet.  Topological restrictions imposed by EGP are
  369.    unjustifiable from the technical point of view, and unenforceable
  370.    from the practical point of view.  Inability of EGP to efficiently
  371.    handle information exchange between peers is a cause of severe
  372.    routing instabilities in the operational Internet. Finally,
  373.    information provided by BGP is well suitable for enforcing a variety
  374.    of routing policies.
  375.  
  376.    Rather than trying to predict the future, and overload BGP with a
  377.    variety of functions that may (or may not) be needed, the designers
  378.    of BGP took a different approach. The protocol contains only the
  379.    functionality that is essential, while at the same time provides
  380.    flexible mechanisms within the protocol itself that allow to expand
  381.    its functionality.  Since BGP was designed with flexibility and
  382.    expandability in mind, we think it should be able to address new or
  383.    evolving requirements with relative ease. The existence proof of this
  384.    statement may be found in the way how new features (like repairing a
  385.    partitioned autonomous system with BGP) are already introduced in the
  386.    protocol.
  387.  
  388.    To summarize, BGP is well suitable as an inter-autonomous system
  389.    routing protocol for the current Internet that is based on IP (RFC
  390.    791) as the Internet Protocol and "hop-by-hop" routing paradigm. It
  391.  
  392.  
  393.  
  394. BGP Working Group                                               [Page 7]
  395.  
  396. RFC 1265                 BGP Protocol Analysis              October 1991
  397.  
  398.  
  399.    is hard to speculate whether BGP will be suitable for other
  400.    environments where internetting is done by other than IP protocols,
  401.    or where the routing paradigm will be different.
  402.  
  403. References
  404.  
  405.    [1] Lougheed, K., and Y. Rekhter, "A Border Gateway Protocol 3 (BGP-
  406.        3)", RFC 1267, cisco Systems, T.J. Watson Research Center, IBM
  407.        Corp., October 1991.
  408.  
  409.    [2] Rekhter, Y., and P. Gross, Editors, "Application of the Border
  410.        Gateway Protocol in the Internet", RFC 1268, T.J. Watson Research
  411.        Center, IBM Corp., ANS, October 1991.
  412.  
  413. Security Considerations
  414.  
  415.    Security issues are not discussed in this memo.
  416.  
  417. Author's Address
  418.  
  419.    Yakov Rekhter
  420.    T.J. Watson Research Center IBM Corporation
  421.    P.O. Box 218
  422.    Yorktown Heights, NY 10598
  423.  
  424.    Phone:  (914) 945-3896
  425.    EMail: yakov@watson.ibm.com
  426.  
  427.    IETF BGP WG mailing list: iwg@rice.edu
  428.    To be added: iwg-request@rice.edu
  429.  
  430.  
  431.  
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439.  
  440.  
  441.  
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450. BGP Working Group                                               [Page 8]
  451.