RFC 1774

BGP-4 Protocol Analysis

📅 published March 1995, from ietf

BGP-4 Protocol Analysis 🎀

okay bestie, this RFC is all about BGP-4 and whether it's ready to level up to Draft Standard 💅

  • RFC number: 1774 🌸
  • Title: BGP-4 Protocol Analysis ✨
  • Network Working Group: this one lives in the Network Working Group 🧚
  • Author: P. Traina, Editor, cisco Systems 💖
  • Category: Informational 💜
  • Date: March 1995 🦋
  • Obsoletes / Updates: it doesn't list anything it obsoletes or updates 🫶

Status of this Memo

so this memo is giving info to the Internet community 🌈 it is NOT an Internet standard of any kind, just facts and analysis 🤓 and anyone can share it, distribution is unlimited no cap 💅

Introduction

the whole point of this report is to show how BGP-4 checks off the requirements for moving a routing protocol up to Draft Standard ✨ it also sums up the key features of BGP and looks at how it handles scaling and performance 🔥 this is the first of two reports on BGP, so stay tuned 👑

okay so BGP-4 is an inter-autonomous system routing protocol, and it was built for TCP/IP internets 🌐 version 1 of BGP got published in RFC 1105 🧚 then versions 2, 3, and 4 came along. version 2 is documented in RFC 1163 🍓 and version 3 is documented in RFC1267 💜 the changes between versions are explained in Appendix 2 of [1] 🫶

possible applications of BGP on the Internet are documented in [2] 🦋

and if you have comments, send them to iwg@ans.net 💌

Key features and algorithms of the BGP-4 protocol. 🔥

this section is the highlight reel of the key features and algorithms of BGP 💅 BGP is an inter-autonomous system routing protocol, which means it's built to work between multiple autonomous systems 🌸 it assumes that routing inside an autonomous system is handled by an intra-autonomous system routing protocol 🧚 BGP doesn't make any assumptions about which intra-autonomous system routing protocols each autonomous system uses 🙈 literally, BGP doesn't require every autonomous system to run the same one. main character energy of flexibility 👑

BGP is a real inter-autonomous system routing protocol 💖 it doesn't put any constraints on the underlying Internet topology 🌈 the info that BGP swaps is enough to build a graph of how autonomous systems connect, and from that graph you can prune routing loops and enforce some routing policy decisions at the autonomous system level 🔥

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

path attributes give BGP its flexibility and expandability 💅 they're split into well-known and optional 🎀 the optional ones let groups of BGP routers experiment without messing with the rest of the Internet 🫶 new optional attributes can be added to the protocol kinda like how new options get added to the Telnet protocol, for example 🦋

one of the most important path attributes is the AS-PATH 👑 as AS reachability info travels across the Internet, it picks up a list of the autonomous systems it has already gone through, and that list is the AS-PATH 🧚 the AS-PATH makes it simple to stop routing info from looping 🙈 on top of that, it's a powerful and versatile tool for policy-based routing 💅

BGP-4 upgrades the AS-PATH attribute so it can hold sets of autonomous systems as well as lists 🍓 this extended format lets generated aggregate routes carry the path info from the more specific routes used to build the aggregate 🌸

BGP doesn't fit neatly into either a pure distance vector or a pure link state algorithm, and that's the tea ☕ carrying a complete AS path in the AS-PATH attribute lets you rebuild large chunks of the overall topology, which is link state vibes 💜 but exchanging only the routes that are actually in use between peers is more like distance vector 🦋

to save bandwidth and processing power, BGP uses incremental updates 💖 after the initial exchange of complete routing info, a pair of BGP routers only swaps the changes (deltas) 🫶 incremental updates need reliable transport between the two BGP routers, so BGP uses TCP as its transport 🔥

on top of incremental updates, BGP-4 added route aggregation, so info about groups of networks can be represented as a single entity 🌈

BGP is a self-contained protocol ✨ it specifies how routing info is exchanged between BGP speakers in different autonomous systems and between BGP speakers inside a single autonomous system 💅

to allow graceful coexistence with EGP and OSPF, BGP supports carrying both EGP-derived and OSPF-derived exterior routes 🧚 it also lets you carry statically defined exterior routes, or routes derived from other IGP information 🎀

BGP performance characteristics and scalability 📈

in this section we're going to answer how much link bandwidth, router memory, and router CPU cycles the BGP protocol eats under normal conditions 🙈 we'll also dig into BGP's scalability and check out some of its limits 💅

BGP doesn't require all the routers in an autonomous system to join the BGP protocol 🫶 only the border routers that connect the local autonomous system to its adjacent autonomous systems take part in BGP 🦋 limiting the set of participants is just one way to handle the scaling issue 👑 it's giving smart design, no notes 💖

okay bestie, right after two BGP peers finish setting up their connection, they swap their entire routing table 📦 Let's say N is the total number of routes on the Internet, M is the mean AS distance (counted in autonomous systems), and A is the total number of autonomous systems. If we assume networks are spread evenly across ASes, the worst case bandwidth for that first exchange between a pair of BGP speakers looks like this 👇

MR = O(N + M * A)

The table below shows what that actually looks like in practice, assuming the same things and ignoring the BGP Header bytes 🎀

# 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

Plot twist: most of that bandwidth goes to NLRI (Network Layer Reachability Information) 👀 That's the main thing eating the pipe.

BGP-4 was built specifically to cut down how many NLRI entries border routers have to carry and trade 💅 Together with CIDR [4], it brought in the "Supernet," which is a power-of-two aggregation of more than one class-based network. Iconic. 🧚

Measuring how much BGP-4 actually saved over BGP3 is kinda tricky ngl. Advertising a few big aggregate blocks is way better than a bunch of little class-based networks, but if you break every aggregate back into its class-based pieces, you miss all the "dead" space that got reserved for future growth 🙈 So the best way to judge BGP-4's aggregation is to count the NLRI entries on the globally connected Internet today and compare that to the growth people projected before BGP-4 showed up 📈

Here's the receipts 🧾 In January of 1994, a router carrying a full routing load for the globally connected Internet had roughly 19,000 network entries (not exact, because local policies vary). The BGP deployment working group estimated growth at over 1000 new networks per month, and that rate was still climbing. After BGP-4 got widely deployed, the growth rate dropped a lot. A sample taken at the end of November 1994 showed about 21,000 entries, instead of the 30,000 people expected 😭✨

Now the CPU part. In a stable Internet, BGP only burns link bandwidth and router CPU cycles on the KEEPALIVE messages, which get exchanged only between peers. The suggested frequency is every 30 seconds. KEEPALIVEs are tiny (19 octets) and need basically zero processing, so they use about 5 bits/sec. Operational experience backs this up: the overhead (bandwidth and CPU) from KEEPALIVEs is totally negligible 💖

If the Internet is unstable, then only the reachability changes caused by those instabilities get passed between routers, through UPDATE messages 🌪️ If C is the number of routing changes per second, the worst case bandwidth BGP can use is O(C * M). The biggest overhead per UPDATE happens when each one carries just a single network. But in practice, routing changes show strong locality with respect to the AS path, meaning routes that change tend to share a common AS path. So multiple networks can be bundled into one UPDATE message, which seriously cuts the bandwidth needed (see also Appendix 6.1 of [1]) 🦋

Here's the big takeaway 🔥 In steady state, BGP's link bandwidth and CPU usage depend only on how stable the Internet is. They're totally independent of how many networks the Internet has. So BGP shouldn't have scaling problems in bandwidth or CPU as the Internet grows, as long as the overall stability of inter-AS connectivity (connectivity between ASs) can be kept under control. Stability could be handled with some form of dampening (e.g., hold downs). Because of how BGP works, that dampening should be viewed as a local-to-an-autonomous-system matter (see also Appendix 6.3 of [1]). Also, no matter what protocol we're talking about, stability in the Internet is seriously important, so don't underestimate it 🫶

Stability has become one of the most crucial issues as the Internet grows 👑 BGP, by itself, does not introduce instabilities into the Internet. Observations on the NSFNET show the instabilities are mostly caused by ill-behaved routing inside the autonomous systems that make up the Internet. So while BGP gets its own mechanisms to deal with stability, the real fix is to attack the root of the problem: come up with intra-autonomous routing schemes that are reasonably stable 🌸

It's also worth comparing BGP's bandwidth and CPU needs with EGP's 🆚 With BGP, the complete information gets exchanged only when the connection is established. With EGP, the complete information gets exchanged periodically (usually every 3 minutes). For both BGP and EGP, the amount of information exchanged is roughly on the order of the networks reachable through the peer that sends it (see also Section 5.2). So even if you assume BGP is extremely unstable, its worst case will look the same as EGP's steady state behavior 💅

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

Memory requirements 🧠

Let's figure out the worst case memory needs for BGP 💜 Denote the total number of networks in the Internet by N, the mean AS distance by M (again, counted in autonomous systems), the total number of autonomous systems by A, and the total number of BGP speakers that a system is peering with by K. (Heads up, K is usually dominated by how many BGP speakers live inside a single autonomous system.) Then the worst case memory requirements (MR) can be expressed as

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

Let's look at the current NSFNET Backbone, where 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 AS path information (on top of the full set of exterior routes) comes out to less than 7 percent of total memory usage. Not bad at all ✨

It's also interesting that before BGP got introduced on the NSFNET Backbone, memory requirements on those routers running EGP were on the order of O(N * K). So the extra memory overhead the NSFNET routers picked up after introducing BGP is less than 7 percent 🌈

Here's the vibe check 🔍 A mean AS distance grows super slowly as the total number of networks grows. The NSFNET backbone had 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, 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 much faster than the average number of peers per router, which means memory scaling is going to be heavily dominated by the factor that's linearly proportional to the total number of networks in the Internet 💀💅

The following table shows typical memory requirements for a router running BGP. It's assumed that 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
4,000       10               100    6                   108,000
10,000      15               300    10                  490,000
100,000     20               3,000  20                  1,040,000

To get some perspective on BGP's memory needs 🔭 let's set aside, just for a sec, the question of what information gets used to build a router's forwarding tables, and focus only on the forwarding tables themselves. Then you can ask what the limits on those tables are. For example, the NSFNET Backbone routers carry well over 20,000 entries right now, so you could ask whether a functional router with a table of 200,000 entries would be possible. The answer to that question is completely independent of BGP. But the answer to the original question (the one asked about BGP) is directly related to this one 🤯

Paul Tsuchiya had some very interesting comments in his review of BGP in March of 1990 (as part of the BGP review committee appointed by Bob Hinden). In that review 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." With CIDR [4] and BGP-4, we tried to reduce this limitation 🌷 Unfortunately, we can't erase history, and BGP-4 can't solve the problems that come from inefficient assignment of future address blocks 😭

Real talk: BGP's memory limits are directly tied to the underlying Internet Protocol (IP), and specifically to the addressing scheme IP uses 💜 BGP would scale a lot better in environments with more flexible addressing schemes. It's also worth noting that, with only very minor additions, BGP was extended to support hierarchies of autonomous systems [8]. Those hierarchies, combined with an addressing scheme that allows more flexible address aggregation, can be used by BGP-like protocols to provide practically unlimited scaling capabilities ✨🌈

Applicability of BGP ✨

okay so this is the part where we figure out what kind of world BGP is actually built for, and where it's not the one 💅 Section 2 of [1] already gives a pretty good answer, and it goes like this:

"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 basically 🦋 BGP is a total match for the current Internet, but it's also kinda a necessity lowkey 🫶 the reason is that EGP was tested in the real world and it was giving "not good enough" 💀 its topological restrictions were impossible to justify technically and impossible to enforce in practice, and its inability to handle information exchange between peers efficiently was causing severe routing instabilities across the operational Internet 😭 meanwhile, the information BGP provides is really well suited for enforcing a whole bunch of routing policies ✨

the BGP designers were like, "ngl we're not gonna predict the future and cram BGP with a bunch of functions that might (or might not) be needed" 🙈 so instead the protocol only includes the functionality that's essential, while also providing flexible mechanisms inside the protocol so it can grow later 🌈 since BGP was built with flexibility and expandability in mind, it should be able to handle new or evolving requirements with relative ease 💖 the proof is already there: new features, like repairing a partitioned autonomous system with BGP, have already been introduced into the protocol 👑

to wrap it 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 really hard to say whether BGP will be suitable for other environments, like ones where internetting is done with protocols other than IP, or where the routing paradigm is different 🤷‍♀️

Security Considerations 🔒

🚨 okay bestie, this one is serious: security issues are not discussed in this memo. please don't assume this document covers security just because it's the BGP analysis, because it does not 😭

Acknowledgments 🫶

the BGP-4 protocol was developed by the IDR/BGP Working Group of the Internet Engineering Task Force 🌸 big thank you to Yakov Rekhter for providing RFC 1265 💜 this document is only a minor update to the original text, and the author would also like to explicitly thank Yakov Rekhter and Tony Li for reviewing it and for 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

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.

📦 where this page comes from