Border Gateway Protocol
Border Gateway Protocol (BGP) is a routing protocol used to transmit routing information so that hosts or computers in one network can communicate with those in other networks anywhere on the internet. BGP is categorized as an external routing protocol since it deals with routing beyond an organization's internal network. BGP is standardized by the IETF.
BGP selects one best path based on a number of rules. BGP also ensures that paths are loop free. By adapting to route failures, BGP ensures network stability. When one path fails, a new path is quickly found. BGP uses TCP on port 179 as its transport protocol.
Can you explain some commonly used terms in BGP?
IP prefix is a block of IP addresses allocated to an organization. A collection of routers in a network having a group of IP prefixes and sharing a common routing policy is called an Autonomous System (AS). The internet connects many of these systems. The Internet Assigned Numbers Authority (IANA) assigns each AS with a globally unique Autonomous System Number (ASN).
There are broadly two types of routing protocols. An Interior Gateway Protocol (IGP) such as RIP, EIGRP, and OSPF does routing within an AS. An Exterior Gateway Protocol (EGP) such as BGP does inter-AS routing. However, BGP can also be used for intra-AS routing. For this reason, some use the terms Internal BGP (iBGP) and External BGP (eBGP) to distinguish between intra-AS and inter-AS usage of BGP.
Why do we need BGP?
BGP is a routing mechanism that connects and binds the entire internet globally. It's in charge of determining the optimum path for a packet from its origin to its destination through the autonomous systems. BGP controls how data packets are distributed between the massive networks that make up the internet, allowing it to function properly.
It's a critical protocol since the internet would not function without it. The whole path to each destination is included in BGP routing information. BGP maintains a database of network reachability information, which it shares with other BGP systems, using the routing information.
What are the characteristics of BGP?
BGP employs TCP as its transport protocol. Therefore BGP needn't implement functions already implemented at TCP, such as explicit update fragmentation, retransmission, acknowledgement, and sequencing. Since BGP doesn't have any built-in security mechanism, TCP Authentication Option (TCP-AO) was introduced. It improves the security and authenticity of TCP segments transmitted during BGP sessions. TCP-AO can handle both IPv4 and IPv6 traffic.
BGP has a mandatory attribute
NEXT_HOPfor all the routes in a BGP table. This value is typically the address of the peer in another AS. For intra-AS routing, we can use OSPF; or use iBGP and update the attribute to point to a neighbouring router within the AS. The figure shows an example where packets from CE2 to 188.8.131.52/8 are routed via 184.108.40.206. Hence CE2 has the
NEXT_HOPattribute set to 220.127.116.11 for destination 18.104.22.168/8.
What are the message types in BGP?
- Open Messages: After establishing a TCP connection by a three-way handshake, an open message is issued to establish a BGP connection. Subsequently, they can exchange other messages and data traffic.
- Update Messages: By sending update messages, network reachability information such as route announcements and withdrawals can be shared. Thus BGP maintains a graph of connections.
- Keepalive Messages: This is exchanged to keep the connection alive or to test connectivity. It's frequently exchanged to prevent the hold timer from expiring.
- Notification Messages: When a problem with the BGP session is discovered, such as a hold timer expiring, changing neighbour capabilities, or a request for BGP session reset, a notification message is provided. The BGP connection is then terminated.
- Route-Refresh Messages: It's requested by peers dynamically when a route advertiser needs to resend the update messages.
How does BGP choose the best path?
- Weight: Choose the route which has most weight. Greater the weight value, higher the preference for that path.
- Local Preference: If many routes have same weight, choose the one with highest local preference.
- Origin: Prefer the route which was originated by local router. Next hop for a locally originated route is 0.0.0.0.
- AS-Path: This is used in case two similar path is detected with same preference.
- Origin Code: If AS-Path length is same prefer path with lowest MED (Multi-Exit Discriminator) which selects best path when there are multiple connections between autonomous systems(AS).
- eBGP over iBGP: Prefer eBGP. eBGP's administrative distance is 20 whereas iBGP's is 200.
- IGP metric: Lowest IGP for next-hop is preferred.
- External Paths: If both routes are external select first and oldest.
- Router ID: Select the path to router which has lowest router ID.
- Cluster list: If multiple paths have same router ID select minimum length.
- Neighbour Address: Select path from lowest neighbour address which is the IP address used in BGP neighbour configuration.
What are the different BGP states?
Establishing a BGP session between speakers requiring a reliable transport protocol. This is provided by TCP. Thus a BGP session is established in two phases: TCP connection establishment phase and BGP session establishment phase. BGP maintains a Finite State Machine (FSM) per peer to track the operational status.
Three BGP states relate to establishing the TCP connection:
- IDLE: Initial state of BGP before any connection happens.
- Connect: BGP initiates TCP connection and waits for successful three-way handshake. If successful, it's transferred to open-sent state.
- Active: Failed to establish a connection and a new three-way handshake is initiated.
Three BGP states relate to establishing the BGP session:
What are the limitations of BGP?
The difficulty with BGP is that it doesn't explicitly incorporate built-in security and relies on network operators to effectively safeguard their systems. BGP hijacking and leak incidents have been a persistent source of concern since the early 2000s.
One of the major challenges that BGP faces is the expansion of the routing table. This issue arises when the routing table grows to the point where certain older, less capable routers are unable to meet the requirements for routing table maintenance, resulting in issues such as 512k day.
BGP is vulnerable to prefix hijacking, which is the deliberate generation of incorrect routing information. The attacker announces routes to disrupt a service on an IP space or hijack traffic to sniff any confidential information. The reasons for this are numerous and difficult to comprehend. Prefix hijacking will also have the same effects as route leaks caused by any router misconfiguration.
Gateway-to-Gateway Protocol (GGP), a first experimental internet gateway is implemented by Bolt, Beranek and Newman (BBN) for use in the US department of Defense for a project named ARPANET. This is the early days of the internet. . The gateway forwards datagrams between networks because it contains a dynamic routing table with an entry for every network that may be reached. The closest gateway is determined by the "number of hops" necessary. A gateway has zero hops when connected directly to the network. The number of hops increases as the number of gateways increases.
DARPA Internet is growing continuously requiring more gateways making GGP less feasible as it requires constant updates. As a result, the Exterior Gateway Protocol (EGP) is implemented through RFC904. The EGP includes autonomous systems, each with a unique identifier. It can transmit traffic from one autonomous system to another, making internet flat and uniform. . The protocol uses Hello/I-Heard-You (I-H-U) message exchanges to poll the reachability of neighbouring autonomous systems on a regular basis. The EGP was actually discussed conceptually in 1982.
Kirk Lougheed and Len Bosack of Cisco, and Yakov Rekhter of IBM write a new protocol with experience gained on EGP. EGP has problems with regional networks providing false information. Intra-regional routing is also isolated from the latest NSFNET, the backbone of internet. They write this new protocol on napkins. For this reason, it's sometimes called the Two-Napkin Protoco. In RFC 1105, these ideas becomes the Border Gateway Protocol.
Border Gateway Protocol (BGP) gets a major update with the publication of RFC 1163 and RFC 1164. It has resolved several issues that arose with the first version of BGP described in RFC 1105. Several Messages types and their applications are redefined. The concept of path attributes is introduced to communicate information about traffic routes. In addition, directional topology in routers that can be up, down or horizontal is removed and replaced with arbitrary AS topology.
RFC 1267: BGP-3 is published with several improvements and corrections. If two BGP speakers attempt to make a TCP connection to each other at the same time, two parallel connections may be formed. This is referred to as a connection collision. A new field BGP identifier is introduced now and been added to message type OPEN to detect and recover from a connection collision. Also, information exchange between previously reachable routes is optimized and simplified.
RFC 1771: BGP-4 is published as a Draft Standard based on last year's Proposed Standard RFC 1654: BGP-4. Major concept of Classless Inter-domain Routing (CIDR) is introduced with the support of advertising IP Prefix to the reachable destination. This eliminates the need for network classes. For storage and bandwidth efficiency, it also helps to aggregate route update messages received from several different routes to be advertised as single routing table entry. The handling of connection collision becomes more sophisticated in this upgrade.
With new RFC 2283, multiprotocol extensions with support for IPv6, IPX, and other network layer protocols are added to BGP-4, which previously only supported IPv4. This BGP-4 expansion is also known as Multiprotocol BGP (MBGP) or Multicast BGP. To facilitate this and offer backward compatibility, two new attributes are introduced: Multiprotocol Reachable NLRI (MP REACH NLRI) and Multiprotocol Unreachable NLRI (MP UNREACH NLRI).
RFC 4271: BGP-4 is published, thus obsoleting RFC 1771 that was published more than a decade earlier. Among many technical modifications, this update clarifies the use of the BGP identification in the AGGREGATOR attribute, the various types of NEXT HOPs, and the use of the ATOMIC AGGREGATE attribute.
To block YouTube access in Pakistan as a result of government order a Pakistan Telecom (AS17557) begins to advertise to its provider PCCW (AS 3491) a small part of 22.214.171.124/24 prefix owned by YouTube (AS36561). Without verifying ownership, PCCW propagates this wrong route. This results in requests to YouTube coming to Pakistan Telecom's network. When YouTube starts announcing the same prefix, BGP selects Pakistan Telecom because it has a shorter path.
As the two-octet encoding for autonomous system numbers approaches its limit, RFC 6793 is introduced with several clarifications and editorial changes obsoleting RFC 4893 (May 2007) to support four-octet ASNs. In addition, a BGP capability code with two new attributes AS4 PATH and AS4 AGGREGATOR is introduced to support this. These new attributes are introduced to disseminate this four-octet-based information to BGP speakers who don't support the new feature.
On 12th August, an Internet Service Provider (ISP) called "Verizon" pushes 15,000 new routes into BGP tables. This unexpectedly surpasses the maximum of 512,000 routes that BGP routers can actually hold. BGP routing tables are stored in TCAM (Tertiary Content Addressable RAM), which reached its memory limit on this fateful day. A remedy for this anticipated problem was recommended, and notifications were provided in May 2014. However, most ISPs failed to make the necessary modifications.
A group of criminal hackers known as 3ve (pronounced "eve") hacks 1 million IP addresses from reputable organizations such as the US Air Force, as well as from residential and business users in North America and Europe. Using botnets they hijack BGP for an endless supply of highly valuable IP addresses. Hackers generate $29 million via ad fraud involving bots placing bids on counterfeited domains.
Facebook and its affiliated services such as WhatsApp and Instagram become unavailable for nearly six hours. This is due to an incorrect internal configuration. They stop announcing BGP routes to their DNS Prefix around 15:58UTC. BGP UPDATE messages begin flooding in from Facebook, causing all routes to it to be withdrawn. DNS servers go offline, cutting it off from the internet. As a result, all DNS resolvers stopped resolving their domain names by responding SERVFAIL.
- A N, Shreya. 2020. "Border Gateway Protocol - Why do we need it and how does it work?" Engineering Education (EngEd) Program, June 08. Accessed 2022-05-11.
- Almes, Guy, Len Bosack, and Jeffrey C Honig. 1991. "A Border Gateway Protocol 3 (BGP-3)" IETF, October. Accessed 2022-04-18.
- Anand, Sarah. 2020. "Demystifying BGP Session Establishments." Packet Pushers, January 22. Accessed 2022-05-15.
- Bates, T, R Chandra, D Katz, and Y Rekhter. 1998. "Multiprotocol Extensions for BGP-4." Multiprotocol support in BGP-4, IETF, February. Accessed 2022-04-24.
- BGP Help. 2017. "BGP Next-Hop Self Explained." Blog, BGP Help, March 5. Accessed 2022-06-01.
- bgp.us. 2022. "Multiple access to the Internet via BGP4 protocol." bgp.us. Accessed 2022-04-22.
- Boutin, Jean-Ian. 2018. "3ve – Major online ad fraud operation disrupted." WeLiveSecurity, November 27. Accessed 2022-05-07.
- Braden, R., and J. Postel. 1987. "RFC 1009 - Requirements for Internet Gateways." IETF, June. Accessed 2022-04-15.
- Brown, Martin A. 2008. "Pakistan Hijacks YouTube: A Closer Look." Circleid, February 25. Accessed 2022-04-28.
- Burke, John. 2022. "BGP (Border Gateway Protocol)." Techtarget, April 06. Accessed 2022-04-06.
- Catchpoint. 2022. "The Complete Guide to BGP Attributes." Catchpoint.com, May 13. Accessed 2022-05-14.
- Chen, E. 2000. "Route Refresh Capability for BGP-4." IETF, September. Accessed 2022-05-13.
- Cisco. 2019. "Border Gateway Protocol (BGP)." Cisco, January 10. Accessed 2022-04-06.
- Cisco Press. 2017. "BGP Overview." Cisco Press, November 30. Accessed 2022-05-21.
- Cisco Press. 2018. "BGP Neighbor States." ciscopress.com, January 01. Accessed 2022-05-15.
- Cisco Press. 2018a. "BGP Fundamentals." Cisco Systems, January 18. Accessed 2022-05-13.
- Cisco Systems. 2016. "BGP Best Path Selection Algorithm." Cisco Systems, September 12. Accessed 2022-05-14.
- Davies, Alun. 2021. "Facebook Down and Out in BGPlay." RIPE Labs, October 05. Accessed 2022-05-07.
- Demicoli, Christopher. 2016. "Beginner's Guide to Understanding BGP." blog.cdemi.io, May 25. Accessed 2022-05-22.
- Donato, Rick. 2018. "BGP – Messages and Adjacency States." Fir3net, February 18. Accessed 2022-05-15.
- Donato, Rick. 2018a. "Routing Protocols Compared - Distance Vector, Path Vector, Link State and Hybrid." Packetcoders.io, November 10. Accessed 2022-05-27.
- Ferlin, Simone, and Michelle Alvarez. 2017. "BGP Internet Routing: What Are the Threats?" Security Intelligence, December 21. Accessed 2022-05-16.
- Francis, Mike. 2019. "Why Your Business Needs BGP, and What It Does for your Organization." WaveFly, February 21. Accessed 2022-05-11.
- Goodin, Dan. 2018. "How 3ve’s BGP hijackers eluded the Internet—and made $29M." arstechnica.com, December 12. Accessed 2022-05-07.
- Google, and White Ops. 2018. "The Hunt for 3ve." Google, November. Accessed 2022-05-07.
- Griffith, Kristina. 2019. "BGP Overview." Huawei Technologies. Accessed 2022-05-28.
- Haas, Jeffrey. 2018. "Some Observations on the History of BGP Protocol." NLNOG Day 2018, Netherlands Network Operator Group. Accessed 2022-04-18.
- Halabi, Sam, and Danny McPherson. 2001. "Internet Routing Architectures." Fourth printing (2004), Cisco Press. Accessed 2022-04-24.
- Haverty, J. F. 1982. "Combined Quarterly Technical Report No. 27." Report No. 5215, Defense Technical Information Center, November. Accessed 2022-04-16.
- Heffernan, A. 1998. "Protection of BGP Sessions via the TCP MD5 Signature Option." IETF. Accessed 2022-05-13.
- Hewlett Packard Enterprise. 2022. "BGP overview - BGP speaker and BGP peer." Techhub Hewlett Packard Enterprise, May. Accessed 2022-05-31.
- Hinden, Robert, and Alan Sheltzer. 1982. "The DARPA Internet Gateway." IETF, September. Accessed 2022-04-13.
- History of Computer Communications. 2022. "Appendix B: Supporting Documents Bolt Beranek & Newman (BBN) documents." History of Computer Communications, April 15. Accessed 2022-04-15.
- Honig, J, D. Katz Merit, M .Mathis, Y Rekhter, and J Yu. 1990. "Application of the Border Gateway Protocol in the Internet." IETF, June. Accessed 2022-04-18.
- Huawei. 2020. "NetEngine 8000 X V800R012C00SPC300 Feature Description - IP Routing 04." Huawei.com, June 20. Accessed 2022-05-12.
- Hunt, Craig. 1997. "Exterior Routing Protocols." Sec. 7.5 in: TCP/IP Network Administration, O'Reilly & Associates, December. Accessed 2022-05-09.
- Improta, Alessandro, and Luca Sani. 2019. "Vulnerabilities of BGP." Catchpoint.com, October 25. Accessed 2022-05-16.
- Internet Policy Research Initiative. 2019. "Addressing BGP Serial Hijacking." Massachusetts Institute of Technology, November 27. Accessed 2022-05-07.
- ISOC. 2014. "Securing BGP." Internetsociety.org, January 23. Accessed 2022-05-15.
- Jabloner, Paula. 2015. "The Two-Napkin Protocol - CHM." Computer History Museum, March 04. Updated 2019-09-03. Accessed 2022-04-14.
- Jabloner, Paula. 2016. "The Two-Napkin Protocol." Cisco Systems, June 01. Accessed 2022-04-29.
- Janardhan, Santosh. 2021. "More details about the October 4 outage." Engineering at Meta, October 05. Accessed 2022-05-07.
- Janardhan, Santosh. 2021a. "Update about the October 4th outage." Engineering at Meta, October 08. Accessed 2022-05-07.
- Juniper Networks. 2017. "Examples: Configuring TCP and BGP Security - TechLibrary - Juniper Networks." Juniper.net, September 13. Accessed 2022-05-20.
- Juniper Networks. 2021. "BGP User Guide." Juniper Networks, December 29. Accessed 2022-04-06.
- Juniper Networks. 2022. "Transport and Internet Protocols User Guide - TCP Authentication Option (TCP-AO)" Juniper Networks, March 11. Accessed 2022-05-13.
- Juniper Networks. 2022a. "Understanding BGP Path Selection." Juniper Networks, March 11. Accessed 2022-05-14.
- Kevin Wallace LLC. 2019. "Fundamentals of Border Gateway Protocol (BGP) - Part 2." kwtrain.com, March 12. Accessed 2022-05-13.
- Kozierok, Charles M. 2005. "The TCP/IP Guide." No Starch Press, October. Accessed 2022-04-18.
- Kozierok, Charles M. 2005a. "BGP Message Generation and Transport, and General Message Format." tcpipguide.com, September 20. Accessed 2022-05-14.
- Krzyzanowski, Paul. 2016. "Understanding Autonomous Systems." Rutgers University Computer Science Department - Paul Krzyzanowski, March 21. Accessed 2022-05-22.
- Lane, Karen. 2014. "The Day the Global Internet Broke Under its Own Weight.| FluidOne." fluidone.com, September 01. Accessed 2022-05-05.
- Lange, A. 2012. "Issues in Revising BGP-4 (RFC1771 to RFC4271)." Records of Issues discussed and consensus reached, IETF. Accessed 2022-04-25.
- Lougheed, K, and Y Rekhter. 1989. "A Border Gateway Protocol (BGP)" IETF, June. Accessed 2022-04-28.
- Lougheed, K, and Y Rekhter. 1990. "A Border Gateway Protocol (BGP)" IETF RFC 1105, June. Accessed 2022-04-18.
- Martinho, Celso, and Tom Strickx. 2021. "Understanding How Facebook Disappeared from the Internet." Cloudflare Blogs, May 10. Accessed 2022-05-07.
- Mills, D.L. 1984. "RFC 904 - Exterior Gateway Protocol Formal Specification." IETF, April. Accessed 2022-04-11.
- Network Urge. 2020. "BGP Best Path Selection Criteria." Networkurge.com, July. Accessed 2022-05-14.
- Noction. 2013. "How does BGP select the best routing path." Noction.com, January 18. Accessed 2022-05-12.
- Paloalto Networks. 2019. "What is BGP Neighbor Adjacency?" knowledgebase.paloaltonetworks.com, April 25. Accessed 2022-05-15.
- Pinto, Danny. 2021. "What will happen when the routing table hits 1024k?" APNIC, March 03. Accessed 2022-05-11.
- Prefixx Team. 2020. "How 512K day affected The Internet | What happened on 512K day." prefixx.net, August 05. Accessed 2022-05-05.
- Press, Cisco. 2018. "BGP Fundamentals." Cisco Press, January 01. Accessed 2022-05-27.
- Rekhter, Y, and T Li. 1994. "A Border Gateway Protocol 4 (BGP-4)" Initial Version of BGP-4, IETF, July. Accessed 2022-04-22.
- Rekhter, Y, and T Li. 1995. "A Border Gateway Protocol 4 (BGP-4)" First Major revision for BGP-4, IETF, March. Accessed 2022-04-22.
- Rekhter, Y, T Li, and S Hares. 2006. "RFC 4271: A Border Gateway Protocol 4 (BGP-4)." IETF, January. Accessed 2022-05-13.
- Richardson, Stephen. 2020. "BGP Messages and Neighbor States." Cisco Certified Expert. Updated 2022-05-10. Accessed 2022-05-16.
- RIPE NCC. 2008. "YouTube Hijacking: A RIPE NCC RIS case study." RIPE Network Coordination Centre, March 17. Accessed 2022-04-28.
- RIPE NCC. 2021. "Facebook Outage Recovery as Seen in BGPlay - 4 October 2021." RIPE Network Coordination Centre, October 05. Accessed 2022-05-07.
- Rosen, Eric C. 1982. "RFC 827 - Exterior Gateway Protocol (EGP)." IETF, October. Accessed 2022-04-11.
- Santos, Omar. 2014. "The Size of the Internet Global Routing Table and Its Potential Side Effects." community.cisco.com, December 12. Updated 2019-01-03. Accessed 2022-05-05.
- Seamonson, Linda J., and Eric C. Rosen. 1984. "RFC 888 - STUB Exterior Gateway Protocol." IETF, January. Accessed 2022-04-11.
- Shen, Ying. 2014. "Global Internet Routing Table Reaches 512k Milestone." Cisco Blogs, August 13. Accessed 2022-05-05.
- Stretch. 2010. "Why BGP Uses TCP and IGPs Don't." packetlife.net, June 24. Accessed 2022-05-13.
- ThousandEyes. 2022. "What are Autonomous System Numbers (ASN) for Internet?" thousandeyes.com, May 18. Accessed 2022-05-22.
- Urge, Network. 2020. "BGP States." Network Urge, July. Accessed 2022-05-28.
- Vohra, Q, and E Chen. 2012. "BGP Support for Four-Octet Autonomous System (AS) Number Space." IETF, December. Accessed 2022-04-29.