diff options
Diffstat (limited to 'doc/rfc/rfc1774.txt')
| -rw-r--r-- | doc/rfc/rfc1774.txt | 563 |
1 files changed, 563 insertions, 0 deletions
diff --git a/doc/rfc/rfc1774.txt b/doc/rfc/rfc1774.txt new file mode 100644 index 0000000..8582bf5 --- /dev/null +++ b/doc/rfc/rfc1774.txt @@ -0,0 +1,563 @@ + + + + + + +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 iwg@ans.net. + +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] + +RFC 1774 BGP-4 Protocol Analysis March 1995 + + +Memory requirements + + To quantify the worst case memory requirements for BGP, denote the + total number of networks 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 the total + number of BGP speakers that a system is peering with by K (note that + K will usually be dominated by the total number of the BGP speakers + within a single autonomous system). Then the worst case memory + requirements (MR) can be expressed as + + MR = O((N + M * A) * K) + + In the current NSFNET Backbone (N = 2110, A = 59, and M = 5) if each + network is stored as 4 octets, and each autonomous system is stored + as 2 octets then the overhead of storing the AS path information (in + addition to the full complement of exterior routes) is less than 7 + percent of the total memory usage. + + It is interesting to point out, that prior to the introduction of BGP + in the NSFNET Backbone, memory requirements on the NSFNET Backbone + routers running EGP were on the order of O(N * K). Therefore, the + extra overhead in memory incurred by the NSFNET routers after the + introduction of BGP is less than 7 percent. + + Since a mean AS distance grows very slowly with the total number of + networks (there are about 60 autonomous systems, well over 2,000 + networks known in the NSFNET backbone routers, and the mean AS + distance of the current Internet is well below 5), for all practical + purposes the worst case router memory requirements are on the order + of the total number of networks in the Internet times the number of + peers the local system is peering with. We expect that the total + number of networks in the Internet will grow much faster than the + average number of peers per router. Therefore, scaling with respect + to the memory requirements is going to be heavily dominated by the + factor that is linearly proportional to the total number of networks + in the Internet. + + The following table illustrates typical memory requirements of a + router running BGP. It is assumed that each network is encoded as 4 + bytes, each AS is encoded as 2 bytes, and each networks is reachable + via some fraction of all of the peers (# BGP peers/per net). + + + + + + + + +Traina [Page 6] + +RFC 1774 BGP-4 Protocol Analysis March 1995 + + + # Networks Mean AS Distance # AS's # BGP peers/per net Memory Req + ---------- ---------------- ------ ------------------- ---------- + 2,100 5 59 3 27,000 + 4,000 10 100 6 108,000 + 10,000 15 300 10 490,000 + 100,000 20 3,000 20 1,040,000 + + To put memory requirements of BGP in a proper perspective, let's try + to put aside for a moment the issue of what information is used to + construct the forwarding tables in a router, and just focus on the + forwarding tables themselves. In this case one might ask about the + limits on these tables. For instance, given that right now the + forwarding tables in the NSFNET Backbone routers carry well over + 20,000 entries, one might ask whether it would be possible to have a + functional router with a table that will have 200,000 entries. + Clearly the answer to this question is completely independent of BGP. + On the other hand the answer to the original questions (that was + asked with respect to BGP) is directly related to the latter + question. Very interesting comments were given by Paul Tsuchiya in + his review of BGP in March of 1990 (as part of the BGP review + committee appointed by Bob Hinden). In the review he said that, "BGP + does not scale well. This is not really the fault of BGP. It is the + fault of the flat IP address space. Given the flat IP address space, + any routing protocol must carry network numbers in its updates." With + the introduction of CIDR [4] and BGP-4, we have attempted to reduce + this limitation. Unfortunately, we cannot erase history nor can + BGP-4 solve the problems inherent with inefficient assignment of + future address blocks. + + To reiterate, BGP limits with respect to the memory requirements are + directly related to the underlying Internet Protocol (IP), and + specifically the addressing scheme employed by IP. BGP would provide + much better scaling in environments with more flexible addressing + schemes. It should be pointed out that with only very minor + additions BGP was extended to support hierarchies of autonomous + system [8]. Such hierarchies, combined with an addressing scheme that + would allow more flexible address aggregation capabilities, can be + utilized by BGP-like protocols, thus providing practically unlimited + scaling capabilities. + +Applicability of BGP + + In this section we'll try to answer the question of what environment + is BGP well suited, and for what is it not suitable? Partially this + question is answered in the Section 2 of [1], where the document + states the following: + + + + + +Traina [Page 7] + +RFC 1774 BGP-4 Protocol Analysis March 1995 + + + "To characterize the set of policy decisions that can be enforced + using BGP, one must focus on the rule that an AS advertises to its + neighbor ASs only those routes that it itself uses. This rule + reflects the "hop-by-hop" routing paradigm generally used + throughout the current Internet. Note that some policies cannot + be supported by the "hop-by-hop" routing paradigm and thus require + techniques such as source routing to enforce. For example, BGP + does not enable one AS to send traffic to a neighbor AS intending + that the traffic take a different route from that taken by traffic + originating in the neighbor AS. On the other hand, BGP can + support any policy conforming to the "hop-by-hop" routing + paradigm. Since the current Internet uses only the "hop-by-hop" + routing paradigm and since BGP can support any policy that + conforms to that paradigm, BGP is highly applicable as an inter-AS + routing protocol for the current Internet." + + While BGP is well suitable for the current Internet, it is also + almost a necessity for the current Internet as well. Operational + experience with EGP showed that it is highly inadequate for the + current Internet. Topological restrictions imposed by EGP are + unjustifiable from the technical point of view, and unenforceable + from the practical point of view. Inability of EGP to efficiently + handle information exchange between peers is a cause of severe + routing instabilities in the operational Internet. Finally, + information provided by BGP is well suitable for enforcing a variety + of routing policies. + + Rather than trying to predict the future, and overload BGP with a + variety of functions that may (or may not) be needed, the designers + of BGP took a different approach. The protocol contains only the + functionality that is essential, while at the same time provides + flexible mechanisms within the protocol itself that allow to expand + its functionality. Since BGP was designed with flexibility and + expandability in mind, we think it should be able to address new or + evolving requirements with relative ease. The existence proof of this + statement may be found in the way how new features (like repairing a + partitioned autonomous system with BGP) are already introduced in the + protocol. + + To summarize, BGP is well suitable as an inter-autonomous system + routing protocol for the current Internet that is based on IP (RFC + 791) as the Internet Protocol and "hop-by-hop" routing paradigm. It + is hard to speculate whether BGP will be suitable for other + environments where internetting is done by other than IP protocols, + or where the routing paradigm will be different. + + + + + + +Traina [Page 8] + +RFC 1774 BGP-4 Protocol Analysis March 1995 + + +Security Considerations + + Security issues are not discussed in this memo. + +Acknowledgments + + The BGP-4 protocol has been developed by the IDR/BGP Working Group of + the Internet Engineering Task Force. I would like to express thanks + to Yakov Rekhter for providing RFC 1265. This document is only a + minor update to the original text. I'd also like to explicitly thank + Yakov Rekhter and Tony Li for their review of this document as well + as their constructive and valuable comments. + +Editor's Address + + Paul Traina + cisco Systems, Inc. + 170 W. Tasman Dr. + San Jose, CA 95134 + + EMail: pst@cisco.com + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Traina [Page 9] + +RFC 1774 BGP-4 Protocol Analysis March 1995 + + +References + + [1] Rekhter, Y., and T., Li, "A Border Gateway Protocol 4 (BGP-4)", + RFC 1771, T.J. Watson Research Center, IBM Corp., cisco Systems, + March 1995. + + [2] Rekhter, Y., and P. Gross, Editors, "Application of the Border + Gateway Protocol in the Internet", RFC 1772, T.J. Watson Research + Center, IBM Corp., MCI, March 1995. + + [3] Willis, S., Burruss, J., and J. Chu, "Definitions of Managed + Objects for the Fourth Version of the Border Gateway Protocol + (BGP-4) using SMIv2", RFC 1657, Wellfleet Communications Inc., + IBM Corp., July 1994. + + [4] Fuller V., Li. T., Yu J., and K. Varadhan, "Classless Inter- + Domain Routing (CIDR): an Address Assignment and Aggregation + Strategy", RFC 1519, BARRNet, cisco, MERIT, OARnet, September + 1993. + + [6] Moy J., "Open Shortest Path First Routing Protocol (Version 2)", + RFC 1257, Proteon, August 1991. + + [7] Varadhan, K., Hares S., and Y. Rekhter, "BGP4/IDRP for IP---OSPF + Interaction", Work in Progress. + + [8] ISO/IEC 10747, Kunzinger, C., Editor, "Inter-Domain Routing + Protocol", October 1993. + + + + + + + + + + + + + + + + + + + + + + + +Traina [Page 10] + |