RFC 1265

BGP Protocol Analysis

📅 published October 1991, from ietf

✨ Okay bestie, the title block first 🎀

This is RFC 1265, BGP Protocol Analysis 🦋 It's from the Network Working Group, and Y. Rekhter is the editor 💜 Y. Rekhter is at the T.J. Watson Research Center, IBM Corp., and it's dated October 1991 🌸 The status is that it's giving info for the Internet community, not a standard 🌈 The title block doesn't list anything it obsoletes or updates 🙈

1. Status of this Memo ✨

Okay so this memo is literally just giving info for the Internet community 🌈 It does not specify an Internet standard, and distribution of this memo is unlimited 💅

2. Introduction 🦋

The whole point of this report is to document how the requirements for advancing a routing protocol to Draft Standard were satisfied by the Border Gateway Protocol (BGP) 👑 It sums up BGP's key features and analyzes the protocol with respect to scaling and performance 📊 This is the first of two reports on BGP, so yes, the sequel is coming 💖

BGP is an inter-autonomous system routing protocol designed for the TCP/IP internets 🌐 Version 1 was published in RFC 1105 🎀 Then versions 2 and 3 got developed. Version 2 was documented in RFC 1163, and Version 3 is documented in [1] 💜 The changes between versions 1, 2 and 3 are explained in Appendix 3 of [1] 🫶

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

Please send comments to iwg@rice.edu 💌

3. Acknowledgements 🙌

BGP was developed by the IWG/BGP Working Group of the Internet Engineering Task Force, and the thank-yous are huge 🫶 We want to say a massive thank you to Guy Almes (Rice University), who was the previous chairman of the IWG Working Group 👑 We also want to explicitly thank Bob Braden (ISI) and Bob Hinden (BBN) for reviewing this document, plus their constructive and valuable comments 💅

4. Key features and algorithms of the BGP protocol 🔥

This section is the highlight reel of BGP's key features and algorithms ✨ BGP is an inter-autonomous system routing protocol, which means it's 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 the intra-autonomous system routing protocols that the various autonomous systems use. 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 info BGP exchanges is enough to construct a graph of autonomous systems connectivity, from which routing loops may be pruned and some routing policy decisions at the autonomous system level may be enforced 🦋

The key feature of the protocol is the notion of Path Attributes 💖 This gives BGP flexibility and expandability. Path attributes are partitioned into well-known and optional 🎀 The provision for optional attributes lets a group of BGP routers experiment without affecting the rest of the Internet 🧪 New optional attributes can be added to the protocol in much the same fashion as new options get added to the Telnet protocol, for instance 🍓 One of the most important path attributes is the AS-PATH 👑 As reachability information traverses the Internet, it gets augmented by the list of autonomous systems that have been traversed thusfar, and that list forms the AS-PATH 🦋 The AS-PATH allows straightforward suppression of the looping of routing information 🌈 It also serves as a powerful and versatile mechanism for policy-based routing 💅

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

To conserve bandwidth and processing power, BGP uses incremental updates 🫶 After the initial exchange of complete routing information, a pair of BGP routers exchanges only the changes (deltas) to that information. The incremental updates technique requires reliable transport between a pair of BGP routers, so BGP uses TCP as its transport 🔒

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

To allow graceful coexistence with EGP, BGP provides support for carrying EGP derived exterior routes 🫶 BGP also lets you carry statically defined exterior routes ✨

5. BGP performance characteristics and scalability 📊

In this section we're going to try to answer how much link bandwidth, router memory and router CPU cycles BGP consumes under normal conditions 💀 We'll also address BGP's scalability 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 🫶

Immediately after the initial BGP connection setup, the peers exchange a complete set of routing information 🎀 If we 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 we 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:

                        O(N + M * A)

(provided that an implementation supports multiple networks per message as outlined in Appendix 5 of [1]). This information is roughly on the order of the number of networks reachable via each peer (see also Section 5.2) 💜

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) 📋

         # Networks   Mean AS Distance       # AS's    Bandwidth
         ----------   ----------------       ------    ---------
         2,100        5                      59        9,000 bytes
         4,000        10                     100       18,000 bytes
         10,000       15                     300       49,000 bytes
         100,000      20                     3,000     520,000 bytes

Note that most of the bandwidth is consumed by the exchange of the Network Reachability Information 👀

After the initial exchange is completed, the amount of bandwidth and 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 BGP can be expressed as O(C * M). The greatest overhead per UPDATE message occurs when each UPDATE message contains only a single network 🙃 In practice, routing changes exhibit strong locality with respect to the AS path. That is, routes that change are likely to have a common AS path 💜 In this case multiple networks can be grouped into a single UPDATE message, thus significantly reducing the amount of bandwidth required (see also Appendix 5 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 of 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 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 5 of [1]) 🏠 We'd like to point out that, regardless of BGP, one should not underestimate the significance of stability in the Internet 🚨 Growth of the Internet will make 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 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 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) 🏆

5.2. Memory requirements ✨

okay so bestie, let's talk memory 🧠 To figure out the absolute worst case memory BGP could eat, we need some variables. N is the total number of networks in the Internet. M is the mean AS distance (how many autonomous systems you pass through, on average). A is the total number of autonomous systems in the Internet. K is the total number of BGP speakers a system is peering with, and K is basically dominated by how many BGP speakers live inside one AS 🫶 Put it all together and the worst case memory requirements (MR) look like this:

MR = O((N + M * A) * K)

Now the NSFNET Backbone, which is giving real-world vibes 🌈 with 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 info (on top of the full set of exterior routes) is less than 7 percent of the total memory usage. Lowkey tiny, highkey impressive 💅

Fun fact 🦋 Before BGP showed up on the NSFNET Backbone, routers running EGP needed memory on the order of O(N * K). So the extra memory the NSFNET routers picked up after BGP arrived is still less than 7 percent. Iconic.

Here's the scaling part, and it's a vibe. The mean AS distance grows super slowly as the number of networks grows. The NSFNET backbone has about 60 autonomous systems and well over 2,000 networks known to its routers, and the mean AS distance of the current Internet is well below 5 🙈 So for all practical purposes, the worst case router memory is 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 the total number of networks to grow way faster than the average number of peers per router, so memory scaling is heavily dominated by the factor that's linearly proportional to the total number of networks in the Internet. Main character energy for that one 👑

Here's a typical memory vibe check 📊 for a router running BGP. Each network is encoded as 4 bytes, each AS is encoded as 2 bytes, and each network is reachable via some fraction of all of the peers (# BGP peers/per net).

# Networks  Mean AS Distance # AS's # BGP peers/per net Memory Req
----------  ---------------- ------ ------------------- ----------
2,100       5                59     3                   27,000 bytes
4,000       10               100    6                   108,000 bytes
10,000      15               300    10                  490,000 bytes
100,000     20               3,000  20                  1,040,000 bytes

Okay, now let's put BGP's memory in perspective 🔍 For a sec, let's pretend we don't care what info builds the forwarding tables and just focus on the tables themselves. Then you can ask about the limits on those tables. Right now the NSFNET Backbone routers carry well over 2,000 entries, so could a functional router handle a table with 20,000 entries? The answer to that has nothing to do with BGP. BUT the original question about BGP is directly tied to it, so no escaping it 😭

Paul Tsuchiya had some very real comments on this in March of 1990, in his review of BGP as part of the BGP review committee that Bob Hinden appointed. He said:

"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."

So basically, BGP's memory limits are tied to the underlying Internet Protocol (IP), and specifically the addressing scheme IP uses. BGP would scale way better in environments with more flexible addressing schemes 🧚 It's also worth knowing that with very minor additions, BGP can be extended to support hierarchies of autonomous systems. Those hierarchies, combined with an addressing scheme that allows more flexible address aggregation, can be used by BGP to give practically unlimited scaling. Slay 💖

6. Applicability of BGP 🌸

So where does BGP actually fit? 🤔 Section 2 of [1] answers part of this. The doc says:

"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."

So BGP is well suited to the current Internet, and it's honestly almost a necessity 🫶 Operational experience with EGP showed it was highly inadequate for the current Internet. EGP's topological restrictions are unjustifiable from a technical point of view and unenforceable from a practical one. EGP's inability to efficiently handle information exchange between peers caused severe routing instabilities in the operational Internet 💀 Meanwhile, the info BGP provides is well suited for enforcing a variety of routing policies.

The BGP designers didn't try to predict the future and overload the protocol with functions that may (or may not) be needed. Instead, BGP contains only the essential functionality, while also providing flexible mechanisms within the protocol itself that allow it to expand. Since BGP was designed with flexibility and expandability in mind, it should be able to handle new or evolving requirements with relative ease. The proof is in how new features (like repairing a partitioned autonomous system with BGP) have already been introduced into the protocol. Receipts, bestie 🧾✨

To sum it all up 🎀 BGP is well suited as an inter-autonomous system routing protocol for the current Internet, which is based on IP (RFC 791) as the Internet Protocol and the "hop-by-hop" routing paradigm. It's hard to speculate whether BGP will suit other environments, where internetting is done by something other than IP protocols, or where the routing paradigm is different. We'll see 🔮

References 📚

[1] Lougheed, K., and Y. Rekhter, "A Border Gateway Protocol 3 (BGP-3)", RFC 1267, cisco Systems, T.J. Watson Research Center, IBM Corp., October 1991.

[2] Rekhter, Y., and P. Gross, Editors, "Application of the Border Gateway Protocol in the Internet", RFC 1268, T.J. Watson Research Center, IBM Corp., ANS, October 1991.

Security Considerations 😱

Plot twist: security issues are not discussed in this memo. Not a single word, bestie 💀

Author's Address 🎀

Yakov Rekhter
T.J. Watson Research Center IBM Corporation
P.O. Box 218
Yorktown Heights, NY 10598

Phone:  (914) 945-3896
EMail: yakov@watson.ibm.com

IETF BGP WG mailing list: iwg@rice.edu
To be added: iwg-request@rice.edu
📦 where this page comes from