View source for Border Gateway Protocol

{{short description|Protocol for communicating routing information on the Internet}}
{{Redirect|BGP}}

{{Infobox networking protocol
| image        = BGP FSM.svg{{!}}class=skin-invert-image
| caption      = BGP state machine
| abbreviation = BGP
| purpose      = exchange [[Internet Protocol]] routing information
| date         = {{Start date and age|1989|06|01}}<ref>{{cite web |title=History for rfc1105 |date=June 1989 |url=https://datatracker.ietf.org/doc/rfc1105/history/ |publisher=[[IETF]] |access-date=1 December 2023}}</ref>
| based on     = [[Exterior Gateway Protocol|EGP]]
| osilayer     = [[Application layer]]
| ports        = tcp/179
| rfcs         = {{slink||Standards documents for BGP-4}}
}}
{{IPstack}}

'''Border Gateway Protocol''' ('''BGP''') is a standardized [[exterior gateway protocol]] designed to exchange [[routing]] and reachability information among [[autonomous system (Internet)|autonomous systems]] (AS) on the [[Internet]].<ref name=orbit>{{cite web |url=http://www.orbit-computer-solutions.com/BGP.php |title=BGP: Border Gateway Protocol Explained |access-date=2013-10-08 |url-status=dead |archive-url=https://web.archive.org/web/20130928115120/http://www.orbit-computer-solutions.com/BGP.php |archive-date=2013-09-28 |website=Orbit-Computer Solutions.Com}}</ref> BGP is classified as a [[path-vector routing protocol]],<ref>{{cite web |title=Network Routing with Path Vector Protocols: Theory and Applications|url=https://conferences.sigcomm.org/sigcomm/2003/papers/p49-sobrinho.pdf |archive-url=https://web.archive.org/web/20100714080202/http://conferences.sigcomm.org/sigcomm/2003/papers/p49-sobrinho.pdf |archive-date=2010-07-14 |url-status=live |access-date=March 16, 2018 |date=2003 |last=Sobrinho |first=João Luís}}</ref> and it makes routing decisions based on paths, network policies, or rule-sets configured by a [[network administrator]].

BGP used for routing within an autonomous system is called '''Interior Border Gateway Protocol''' ('''iBGP'''). In contrast, the Internet application of the protocol is called '''Exterior Border Gateway Protocol''' ('''EBGP''').

== History ==
{{trim|{{#section:Yakov Rekhter|Two-Napkins}}}}

Half a year after the initial publication, the protocol definition was changed in 1990 with the publication of {{Sum RFC|1136|title=no|ref=yes}}. In October 1991, BGP version 3 was defined in {{Sum RFC|1267|title=no|ref=yes}}, obsoleting the two earlier versions. In 1994, the current version (BGP4), was published as {{Sum RFC|1654|title=no|ref=yes}}. Its definition was replaced in March 1995 by {{Sum RFC|1771|title=no|ref=yes}}. In January 2006, {{Sum RFC|4271|title=no|ref=yes}} was published, which currently is the latest definition of BGP4 (although updated by many other RFCs).

RFC 4271 corrected errors, clarified ambiguities and updated the specification with common industry practices. The major enhancement of BGP4 was the support for [[Classless Inter-Domain Routing]] (CIDR) and use of [[route aggregation]] to decrease the size of [[routing table]]s.
In its native form, the BGP4 protocol can only work with IPv4 addresses. Since the publication of {{Sum RFC|2283|title=no|ref=yes}} in 1998, routing information about a wide range of "address families" ([[IPv4]], [[IPv6 address|IPv6]], [[IPX]], etc.) can be carried. The 'Multiprotocol Extensions' have been updated in 2000 with {{Sum RFC|2858|title=no|ref=yes}} and finally in 2007 with {{Sum RFC|4760|title=no|ref=yes}}. With these extensions, the protocol is also referred to as [[Multiprotocol BGP]] (MP-BGP).

== Operation ==

BGP neighbors, called peers, are established by manual configuration among [[Router (computing)|router]]s to create a [[Transmission Control Protocol|TCP]] session on [[port (computer networking)|port]] 179. A BGP speaker sends 19-byte keep-alive messages every 30 seconds (protocol default value, tunable) to maintain the connection.{{Ref RFC|4274}} Among routing protocols, BGP is unique in using TCP as its transport protocol.

When BGP runs between two peers in the same [[autonomous system (Internet)|autonomous system]] (AS), it is referred to as ''Internal BGP'' (''iBGP'' or ''Interior Border Gateway Protocol''). When it runs between different autonomous systems, it is called ''External BGP'' (''eBGP'' or ''Exterior Border Gateway Protocol''). Routers on the boundary of one AS exchanging information with another AS are called ''border'' or ''edge routers'' or simply ''eBGP peers'' and are typically connected directly, while ''iBGP peers'' can be interconnected through other intermediate routers. Other deployment [[Network topology|topologies]] are also possible, such as running eBGP [[peering]] inside a [[VPN]] tunnel, allowing two remote sites to exchange routing information in a secure and isolated manner.

The main difference between iBGP and eBGP peering is in the way routes that were received from one peer are typically propagated by default to other peers:
* New routes learned from an eBGP peer are re-advertised to all iBGP and eBGP peers.
* New routes learned from an iBGP peer are re-advertised to all eBGP peers only.

These route-propagation rules effectively require that all iBGP peers inside an AS are interconnected in a full mesh with iBGP sessions.

How routes are propagated can be controlled in detail via the ''route-maps'' mechanism. This mechanism consists of a set of rules. Each rule describes, for routes matching some given criteria, what action should be taken. The action could be to drop the route, or it could be to modify some attributes of the route before inserting it in the routing table.

=== Extensions negotiation ===

During the peering handshake, when OPEN messages are exchanged, BGP speakers can negotiate optional capabilities of the session,<ref>{{cite IETF |rfc=2842 |title=Capabilities Advertisement with BGP-4 |author1=R. Chandra |author2=J. Scudder |date=May 2000}}</ref> including [[Multiprotocol BGP|multiprotocol extensions]]<ref>{{cite IETF |rfc=2858 |title=Multiprotocol Extensions for BGP-4 |author=T. Bates |display-authors=etal |date=June 2000}}</ref> and various recovery modes. If the multiprotocol extensions to BGP are negotiated at the time of creation, the BGP speaker can prefix the Network Layer Reachability Information (NLRI) it advertises with an address family prefix. These families include the IPv4 (default), IPv6, IPv4/IPv6 Virtual Private Networks and multicast BGP. Increasingly, BGP is used as a generalized signaling protocol to carry information about routes that may not be part of the global Internet, such as VPNs.<ref>{{cite IETF |rfc=2547 |title=BGP/MPLS VPNs |author1=E. Rosen |author2=Y. Rekhter |date=April 2004}}</ref>

In order to make decisions in its operations with peers, a BGP peer uses a simple [[finite-state machine]] (FSM) that consists of six states: Idle; Connect; Active; OpenSent; OpenConfirm; and Established. For each peer-to-peer session, a BGP implementation maintains a state variable that tracks which of these six states the session is in. The BGP defines the messages that each peer should exchange in order to change the session from one state to another.

The first state is the Idle state. In the Idle state, BGP initializes all resources, refuses all inbound BGP connection attempts and initiates a TCP connection to the peer. The second state is Connect. In the Connect state, the router waits for the TCP connection to complete and transitions to the OpenSent state if successful. If unsuccessful, it starts the ConnectRetry timer and transitions to the Active state upon expiration. In the Active state, the router resets the ConnectRetry timer to zero and returns to the Connect state. In the OpenSent state, the router sends an Open message and waits for one in return in order to transition to the OpenConfirm state. Keepalive messages are exchanged and, upon successful receipt, the router is placed into the Established state. In the Established state, the router can send and receive: Keepalive; Update; and Notification messages to and from its peer.
* '''Idle State''':
** Refuse all incoming BGP connections.
** Start the initialization of event triggers.
** Initiates a TCP connection with its configured BGP peer.
** Listens for a TCP connection from its peer.
** Changes its state to Connect.
** If an error occurs at any state of the FSM process, the BGP session is terminated immediately and returned to the Idle state. Some of the reasons why a router does not progress from the Idle state are:
*** TCP port 179 is not open.
*** A random TCP port over 1023 is not open.
*** Peer address configured incorrectly on either router.
*** AS number configured incorrectly on either router.
* '''Connect State''':
** Waits for successful TCP negotiation with peer.
** BGP does not spend much time in this state if the TCP session has been successfully established.
** Sends Open message to peer and changes state to OpenSent.
** If an error occurs, BGP moves to the Active state. Some reasons for the error are:
*** TCP port 179 is not open.
*** A random TCP port over 1023 is not open.
*** Peer address configured incorrectly on either router.
*** AS number configured incorrectly on either router.
* '''Active State''':
** If the router was unable to establish a successful TCP session, then it ends up in the Active state.
** BGP FSM tries to restart another TCP session with the peer and, if successful, then it sends an Open message to the peer.
** If it is unsuccessful again, the FSM is reset to the Idle state.
** Repeated failures may result in a router cycling between the Idle and Active states. Some of the reasons for this include:
*** TCP port 179 is not open.
*** A random TCP port over 1023 is not open.
*** BGP configuration error.
*** [[Network congestion]].
*** Flapping network interface.
* '''OpenSent State''':
** BGP FSM listens for an Open message from its peer.
** Once the message has been received, the router checks the validity of the Open message.
** If there is an error it is because one of the fields in the Open message does not match between the peers, e.g., BGP version mismatch, the peering router expects a different My AS, etc. The router then sends a Notification message to the peer indicating why the error occurred.
** If there is no error, a Keepalive message is sent, various timers are set and the state is changed to OpenConfirm.
* '''OpenConfirm State''':
** The peer is listening for a Keepalive message from its peer.
** If a Keepalive message is received and no timer has expired before reception of the Keepalive, BGP transitions to the Established state.
** If a timer expires before a Keepalive message is received, or if an error condition occurs, the router transitions back to the Idle state.
* '''Established State''':
** In this state, the peers send Update messages to exchange information about each route being advertised to the BGP peer.
** If there is any error in the Update message then a Notification message is sent to the peer, and BGP transitions back to the Idle state.

=== Router connectivity and learning routes ===
{{technical|section|date=April 2021}}
In the simplest arrangement, all routers within a single AS and participating in BGP routing must be configured in a full mesh: each router must be configured as a peer to every other router. This causes scaling problems, since the number of required connections [[quadratic growth|grows quadratically]] with the number of routers involved. To alleviate the problem, BGP implements two options: [[route reflector]]s (RFC 4456) and [[BGP confederation]]s (RFC 5065). The following discussion of basic update processing assumes a full iBGP mesh.

A given BGP router may accept [[#Update Packet|network-layer reachability information (NLRI) updates]] from multiple neighbors and advertise NLRI to the same, or a different set, of neighbors. The BGP process maintains several [[routing information base]]s:
* <code>RIB</code>: routers main routing information base table.
* <code>Loc-RIB</code>: local routing information base BGP maintains its own master routing table separate from the main routing table of the router.
* <code>Adj-RIB-In</code>: For each neighbor, the BGP process maintains a conceptual ''adjacent routing information base, incoming'', containing the NLRI received from the neighbor.
* <code>Adj-RIB-Out</code>: For each neighbor, the BGP process maintains a conceptual ''adjacent routing information base, outgoing '', containing the NLRI sent to the neighbor.

The physical storage and structure of these conceptual tables are decided by the implementer of the BGP code. Their structure is not visible to other BGP routers, although they usually can be interrogated with management commands on the local router. It is quite common, for example, to store the <code>Adj-RIB-In</code>, <code>Adj-RIB-Out</code> and the <code>Loc-RIB</code> together in the same [[data structure]], with additional information attached to the RIB entries. The additional information tells the BGP process such things as whether individual entries belong in the <code>Adj-RIBs</code> for specific neighbors, whether the peer-neighbor route selection process made received policies eligible for the <code>Loc-RIB</code>, and whether <code>Loc-RIB</code> entries are eligible to be submitted to the local router's routing table management process.

BGP submits the routes that it considers best to the main routing table process. Depending on the implementation of that process, the BGP route is not necessarily selected. For example, a directly connected prefix, learned from the router's own hardware, is usually most preferred. As long as that directly connected route's interface is active, the BGP route to the destination will not be put into the routing table. Once the interface goes down, and there are no more preferred routes, the Loc-RIB route would be installed in the main routing table.

BGP carries the information with which rules inside BGP-speaking routers can make policy decisions. Some of the information carried that is explicitly intended to be used in policy decisions are:
* [[#Communities|Communities]]
* [[#Multi-exit discriminators|multi-exit discriminators]] (MED).
* [[autonomous system (Internet)|autonomous systems]] (AS)

=== Route selection process ===

The BGP standard specifies a number of decision factors, more than the ones that are used by any other common routing process, for selecting NLRI to go into the Loc-RIB. The first decision point for evaluating NLRI is that its next-hop attribute must be reachable (or resolvable). Another way of saying the next-hop must be reachable is that there must be an active route, already in the main routing table of the router, to the prefix in which the next-hop address is reachable.

Next, for each neighbor, the BGP process applies various standard and implementation-dependent criteria to decide which routes conceptually should go into the Adj-RIB-In. The neighbor could send several possible routes to a destination, but the first level of preference is at the neighbor level. Only one route to each destination will be installed in the conceptual Adj-RIB-In. This process will also delete, from the Adj-RIB-In, any routes that are withdrawn by the neighbor.

Whenever a conceptual Adj-RIB-In changes, the main BGP process decides if any of the neighbor's new routes are preferred to routes already in the Loc-RIB. If so, it replaces them. If a given route is withdrawn by a neighbor, and there is no other route to that destination, the route is removed from the Loc-RIB and no longer sent by BGP to the main routing table manager. If the router does not have a route to that destination from any non-BGP source, the withdrawn route will be removed from the main routing table.

As long as there is a [[Tie_(draw)|tie]], the route selection process moves to the next step.

{| class="wikitable"
|+ Steps to determine best path, in order of [[tiebreaker]]:
<ref>{{cite web |url=https://www.cisco.com/c/en/us/support/docs/ip/border-gateway-protocol-bgp/13753-25.html |title=BGP Best Path Selection Algorithm |website=[[Cisco]].com}}</ref>
<ref>{{cite web |url=https://www.juniper.net/documentation/us/en/software/junos/vpn-l2/bgp/topics/concept/routing-protocols-address-representation.html |title=Understanding BGP Path Selection |website=[[Juniper]].com}}</ref>

! Step !! Scope !! Name !! Default !! Preferred !! BGP field !! Notes
|-
| 1 || Local to router || local Weight || {{notnom|"Off"}} || Higher || || Cisco-specific parameter
|-
| 2 || rowspan="2" |Internal to AS || Local preference || {{notnom|"Off", all set to 100.}} || Higher || LOCAL_PREF || If there are several iBGP routes from the neighbor, the one with the highest local preference is selected unless there are several routes with the same local preference.
|-
| 3 || Accumulated Interior Gateway Protocol (AIGP) || {{notnom|"Off"}} || Lowest || AIGP  || {{IETF RFC|7311}}
|-
| 4 ||  rowspan="3" |External to AS || Autonomous system (AS) jumps || {{good|"On", skipped if ignored in configuration}} || Lowest || AS-path || AS jumps is the number of AS numbers that must be traversed to reach the advertised destination. AS1–AS2–AS3 is a shorter path with fewer jumps than AS4–AS5–AS6–AS7.
|-
| 5 ||  origin type || "IGP" || Lowest || ORIGIN  ||0 = IGP<br />1 = EGP<br />2 = Incomplete
|-
| 6 || multi-exit discriminator (MED) || {{good|"on", imported from peer AS}} || Lowest || MULTI_EXIT_DISC|| By default only routes with the same peer autonomous system (AS) are compared. Can be set to ignore this. By default, IGP metric is not added. Can be set to add IGP metric.
Before the most recent edition of the BGP standard, if an update had no MED value, several implementations created a MED with the highest possible value. The current standard specifies that missing MEDs are treated as the lowest possible value. Since the current rule may cause different behavior than the vendor interpretations, BGP implementations that used the nonstandard default value have a configuration feature that allows the old or standard rule to be selected.
|-
| 7 ||  rowspan="6" |Local to router (Loc-RIB) || eBGP over iBGP paths || "on" ||  ||  || Directly connected, over indirectly
|-
| 8 || IGP metric to BGP next hop || {{good|"on", imported from IGP}} || Lowest ||  || Prefer the route with the lowest interior cost to the next hop, according to the main routing table. If two neighbors advertised the same route, but one neighbor is reachable via a low-bitrate link and the other by a high-bitrate link, and the [[interior routing protocol]] calculates lowest cost based on highest bitrate, the route through the high-bitrate link would be preferred and other routes dropped.
If a BGP extension is used to support [[multipath routing]], the best path selection may stop here and all paths selected up to this point will be added to the routing table.
|-
| 9 ||  Path that was received first || "on" || oldest ||  || Used to ignore changes on the next steps to minimize route flapping.
|-
| 10 || Neighbor Router ID || "on" || Lowest ||  ||
|-
| 11 || Cluster list length || "on" || Lowest ||  ||
|-
| 12 || Neighbor IP address || "on" || Lowest
|}

The local preference, weight, and other criteria can be manipulated by local configuration and software capabilities. Such manipulation, although commonly used, is outside the scope of the standard. For example, the ''community'' attribute (see below) is not directly used by the BGP selection process. The BGP neighbor process can have a rule to set local preference or another factor based on a manually programmed rule to set the attribute if the community value matches some pattern-matching criterion. If the route was learned from an external peer the per-neighbor BGP process computes a local preference value from local policy rules and then compares the local preference of all routes from the neighbor.

=== Communities ===

BGP communities are attribute tags that can be applied to incoming or outgoing prefixes to achieve some common goal.{{Ref RFC|1997}} While it is common to say that BGP allows an administrator to set policies on how prefixes are handled by ISPs, this is generally not possible, strictly speaking. For instance, BGP natively has no concept to allow one AS to tell another AS to restrict advertisement of a prefix to only North American peering customers. Instead, an ISP generally publishes a list of well-known or proprietary communities with a description for each one, which essentially becomes an agreement of how prefixes are to be treated.

{| class="wikitable"
|+ Well-known BGP communities<ref>{{Cite web |title=Border Gateway Protocol (BGP) Well-known Communities |url=https://www.iana.org/assignments/bgp-well-known-communities/bgp-well-known-communities.xhtml |access-date=2022-12-04 |website=www.iana.org}}</ref>
! Attribute value  !! Attribute  !! Description !! Reference
|-
| 0x00000000–0x0000FFFF || Reserved ||  || {{IETF RFC|1997}}
|-
| 0x00010000–0xFFFEFFFF || Reserved for private use ||  || {{IETF RFC|1997}}
|-
| 0xFFFF0000 || GRACEFUL_SHUTDOWN || At neighbor AS-peer, set LOCAL_PREF, lower to route away from source.  || {{IETF RFC|8326}}
|-
| 0xFFFF0001 || ACCEPT_OWN || Used to modify how a route originated within one VRF is imported into other VRFs ||  {{IETF RFC|7611}}
|-
| 0xFFFF0002 || ROUTE_FILTER_TRANSLATED_v4 ||  || RFC draft-l3vpn-legacy-rtc
|-
| 0xFFFF0003 || ROUTE_FILTER_v4 ||  || RFC draft-l3vpn-legacy-rtc
|-
| 0xFFFF0004 || ROUTE_FILTER_TRANSLATED_v6 ||  || RFC draft-l3vpn-legacy-rtc
|-
| 0xFFFF0005 || ROUTE_FILTER_v6 ||  || RFC  draft-l3vpn-legacy-rtc
|-
| 0xFFFF0006 || LLGR_STALE || Stale routes are retained for longer after a session failure  || {{IETF RFC|9494}}
|-
| 0xFFFF0007 || NO_LLGR || LLGR capability should not apply || {{IETF RFC|9494}}
|-
| 0xFFFF0008 || accept-own-nexthop ||  || RFC draft-agrewal-idr-accept-own-nexthop
|-
| 0xFFFF0009 || Standby PE || Allow for faster recovery of connectivity on different types of failures, with multicast in BGP/MPLS VPNs.  || {{IETF RFC|9026}}
|-
| 0xFFFF029A || BLACKHOLE || To temporarily protect against [[denial-of-service attack]] by asking the neighbour AS to discard all traffic to the prefix (blackholing)  || {{IETF RFC|7999}}
|-
| 0xFFFFFF01 || NO_EXPORT || Limit to a BGP confederation boundary || {{IETF RFC|1997}}
|-
| 0xFFFFFF02 || NO_ADVERTISE || Limit to a BGP peer || {{IETF RFC|1997}}
|-
| 0xFFFFFF03 || NO_EXPORT_SUBCONFED || Limit to an AS ||{{IETF RFC|1997}}
|-
| 0xFFFFFF04 || NOPEER || "No need" to advertise over a peer link || {{IETF RFC|3765}}
|}

Examples of common communities include:
* local preference adjustments,
* geographic 
* peer type restrictions
* [[denial-of-service attack]] identification
* AS prepending options.

An ISP might state that any routes received from customers with following examples:
*   To Customers North America (East Coast) 3491:100
*   To Customers North America (West Coast) 3491:200
The customer simply adjusts their configuration to include the correct community or communities for each route, and the ISP is responsible for controlling who the prefix is advertised to. The end user has no technical ability to enforce correct actions being taken by the ISP, though problems in this area are generally rare and accidental.<ref>{{Cite web |title=BGP Community Support {{!}} iFog GmbH |url=https://ifog.ch/en/blog/bgp-community-support |access-date=2022-12-04 |website=ifog.ch}}</ref><ref>{{Cite web |title=BGP communities |url=https://retn.net/bgp-communities |access-date=2022-12-04 |website=retn.net |language=en}}</ref>

It is a common tactic for end customers to use BGP communities (usually ASN:70,80,90,100) to control the local preference the ISP assigns to advertised routes instead of using MED (the effect is similar). The community attribute is transitive, but communities applied by the customer very rarely propagate outside the next-hop AS. Not all ISPs give out their communities to the public.<ref>{{cite web|title=BGP Community Guides|url=http://www.onesc.net/communities/|access-date=13 April 2015}}</ref>

==== BGP Extended Community Attribute ====
The BGP Extended Community Attribute was added in 2006,{{Ref RFC|4360}} in order to extend the range of such attributes and to provide a community attribute structuring by means of a type field. The extended format consists of one or two octets for the type field followed by seven or six octets for the respective community attribute content. The [[IANA]] administers the registry for BGP Extended Communities Types.<ref>{{Cite web |title=Border Gateway Protocol (BGP) Extended Communities |url=https://www.iana.org/assignments/bgp-extended-communities/bgp-extended-communities.xhtml |access-date=2022-12-04 |website=www.iana.org}}</ref>

The Extended Communities Attribute itself is a transitive optional BGP attribute. A bit in the 'Type' field within the attribute decides whether the encoded extended community is of a transitive or non-transitive nature. The IANA registry therefore provides different number ranges for the attribute types. Due to the extended attribute range, its usage can be manifold. RFC 4360 exemplarily defines the "Two-Octet AS Specific Extended Community", the "IPv4 Address Specific Extended Community", the "Opaque Extended Community", the "Route Target Community", and the "Route Origin Community". A number of BGP QoS drafts also use this Extended Community Attribute structure for inter-domain QoS signalling.<ref>[http://www.bgp-qos.org/forum/viewforum.php?f=6 IETF drafts on BGP signalled QoS] {{webarchive|url=https://web.archive.org/web/20090223214439/http://www.bgp-qos.org/forum/viewforum.php?f=6 |date=2009-02-23 }}, Thomas Knoll, 2008</ref>

With the introduction of 32-bit AS numbers, some issues were immediately obvious with the community attribute that only defines a 16-bit ASN field, which prevents the matching between this field and the real ASN value. Since 2014, extended communities are compatible with 32-bit ASNs.{{Ref RFC|7153}} To accommodate 32-bit AS numbers in BGP Communities, a Large Community attribute of 12 bytes was defined,{{Ref RFC|8092}}{{Ref RFC|8195}} divided in three field of 4 bytes each (AS:function:parameter).<ref>{{cite web |url=http://largebgpcommunities.net/ |title=Large BGP Communities |access-date=2021-11-27}}</ref>

=== Multi-exit discriminators ===

MEDs, defined in the main BGP standard, were originally intended to show to another neighbor AS the advertising AS's preference as to which of several links are preferred for inbound traffic. Another application of MEDs is to advertise the value, typically based on delay, of multiple ASs that have a presence at an [[IXP]], that they impose to send traffic to some destination.

Some routers (like Juniper) will use the Metric from OSPF to set MED.

'''Examples of MED used with BGP when exported to BGP on Juniper SRX'''
<syntaxhighlight lang="console">
# run show ospf route   
Topology default Route Table:
Prefix             Path  Route      NH       Metric NextHop       Nexthop     
                   Type  Type       Type            Interface     Address/LSP
10.32.37.0/24      Inter Discard    IP       16777215
10.32.37.0/26      Intra Network    IP          101 ge-0/0/1.0    10.32.37.241
10.32.37.64/26     Intra Network    IP          102 ge-0/0/1.0    10.32.37.241
10.32.37.128/26    Intra Network    IP          101 ge-0/0/1.0    10.32.37.241

# show route advertising-protocol bgp 10.32.94.169
  Prefix               Nexthop       MED    Lclpref            AS path
* 10.32.37.0/24           Self                 16777215           I
* 10.32.37.0/26           Self                 101                I
* 10.32.37.64/26          Self                 102                I
* 10.32.37.128/26         Self                 101                I
</syntaxhighlight>

== Packet format ==
=== Message header format ===
All BGP messages share the following header layout.
{{APHD|start|title=BGP version 4 message header format{{Ref RFC|4271|rsection=4.1}}}}
{{APHD|0|bits1=128|field1=Marker|value1=ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff}}
{{APHD|16|bits1=16|field1=Length|bits2=8|field2=Type}}
{{APHD|end}}
;{{APHD|def|name=Marker|length=128 bits|text=Included for compatibility, MUST be set to all ones.}}
;{{APHD|def|name=Length|length=16 bits|text=Total length of the message in octets, including the header.}}
;{{APHD|def|name=Type|length=8 bits|text=Type of BGP message. The following values are defined:}}
:* Open (1)
:* Update (2)
:* Notification (3)
:* KeepAlive (4)
:* Route-Refresh (5)

=== Open Packet ===
With an 'Open' packet a BGP session may be initiated.
{{APHD|start|title=BGP version 4 'OPEN' message format}}
{{APHD|999|bits1=32|field1=Marker|value1=ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff}}
{{APHD|16|bits1=16|field1=Length|value1=29+|bits2=8|field2=Type|value2=1|bits3=8|value3=4|field3=Version}}
{{APHD|20|bits1=16|field1=My AS|bits2=16|field2=Hold Time}}
{{APHD|24|bits1=32|field1=BGP Identifier}}
{{APHD|28|bits1=8|field1=Parameters Length|bits2=24|field2={{nbsp}}|background2=linen|border2=bottom}}
{{APHD|30|bits1=0|border1=top|background1=linen|field1=Parameters}}
{{APHD|end}}
;{{APHD|def|name=Version|length=8 bits|text=Version of BGP used.}}
;{{APHD|def|name=My AS|length=16 bits|text=Senders [[autonomous system (Internet)|autonomous system]] number.}}
;{{APHD|def|name=Hold Time|length=16 bits|text=Timeout timer, used to calculate  KeepAlive messages. Default 90 seconds.}}
;{{APHD|def|name=BGP Identifier|length=32 bits|text=Holds the IP address of the sender.}}
;{{APHD|def|name=Parameters Length|length=8 bits|text=Total length of the Parameters field in octets. If this (mandatory){{Ref RFC|4271|rsection=4.2}} field is zero, there are no parameters in the message.}}
;{{APHD|def|name=Parameters|length=variable|text=Optional parameters. This field is used to convey the capabilities the sender of this packet has to the peer.{{Ref RFC|5492}} A [https://www.iana.org/assignments/capability-codes/capability-codes.xhtml#capability-codes-2 list] of all capabilities is maintained by [[IANA]].}}
'''Example of Open Message'''
 Type: Open Message (1)
 Version: 4
 My AS: 64496
 Hold Time: 90
 BGP Identifier: {{IPaddr|192.0.2.254}}
 Optional Parameters Length: 16
 Optional Parameters:
  Capability: Multiprotocol Extensions Capability (1)
  Capability: Route Refresh Capability (2)
  Capability: Enhanced Route Refresh Capability (70)

=== Update Packet ===
Only changes are sent, after initial exchange, only difference (add/change/removed) are sent.
{{APHD|start|title=BGP version 4 'UPDATE' message format}}
{{APHD|999|bits1=32|field1=Marker|value1=ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff}}
{{APHD|16|bits1=16|field1=Length|value1=23+|bits2=8|field2=Type|value2=2|bits3=8|border3=right|field3=Withdrawn Routes Length}}
{{APHD|20|bits1=8|border1=left|field1=Length (cont.)|bits2=24|background2=linen|border2=bottom|field2={{nbsp}}}}
{{APHD|999|bits1=32|border1=top|background1=linen|field1=Withdrawn Routes}}
{{APHD|999|bits1=16|field1=Total Path Attribute Length|bits2=16|border2=bottom|background2=linen|field2={{nbsp}}}}
{{APHD|999|bits1=32|border1=top|background1=linen|field1=Path Attributes}}
{{APHD|999|bits1=64|background1=linen|field1=Network Layer Reachability Information}}
{{APHD|end}}
;{{APHD|def|name=Withdrawn Routes Length|length=16 bits|text=Length of the following withdrawn routes. May be zero if no routes are withdrawn.}}
;{{APHD|def|name=Withdrawn Routes|length=variable|text=A list of withdrawn routes, specified as a series of <nowiki><length, prefix></nowiki> [[tuples]].}}
;{{APHD|def|name=Total Path Attribute Length|length=16 bits|text=Length of the following path attributes. May be zero if there are no attributes.}}
;{{APHD|def|name=Path Attributes|length=variable|text=List of path attributes, specified as a series of [[Type-length-value|TLV]] structures.}}
;{{APHD|def|name=Network Layer Reachability Information|short=NLRI|length=variable|text=Reachability information, specified as a series of <nowiki><length, prefix></nowiki> tuples. The length of this field can be caclulated as: ''Length'' - 23 - ''Withdrawn Routes Length'' - ''Total Path Attribute Length''.}}
'''Example of UPDATE Message'''

 Type: UPDATE Message (2)
 Withdrawn Routes Length: 0
 Total Path Attribute Length: 25
 Path attributes
  ORIGIN: IGP
  AS_PATH: 64500
  NEXT_HOP: 192.0.2.254
  MULTI_EXIT_DISC: 0
 Network Layer Reachability Information (NLRI)
  {{IPaddr|192.0.2.0/27}}
  {{IPaddr|192.0.2.32/27}}
  {{IPaddr|192.0.2.64/27}}

=== Notification ===
If there is an error, it is because one of the fields in the OPEN or UPDATE message does not match between the peers. For example: BGP version mismatch, or the peering router expects a different 'My AS'. The router then sends a Notification message to the peer indicating why the error occurred.
An error in the communication usually leads to the teardown of the BGP session. To avoid a cascade of sessions being terminated due to a single error, which can happen in complex scenarios with routers with limited capabilities, extra effort is taken to isolate the problem and keep most sessions going.{{Ref RFC|7606}}
{{APHD|start|title=BGP version 4 'NOTIFICATION' message format}}
{{APHD|999|bits1=32|field1=Marker|value1=ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff}}
{{APHD|16|bits1=16|field1=Length|value1=21+|bits2=8|field2=Type|value2=3|bits3=8|field3=Error Code}}
{{APHD|20|bits1=8|field1=Error Subcode|bits2=24|background2=linen|border2=bottom|field2={{nbsp}}}}
{{APHD|24|bits1=0|border1=top|background1=linen|field1=Data}}
{{APHD|end}}
;{{APHD|def|name=Error Code|length=8 bits|text=A value indicating the type or origin of the error.}}
;{{APHD|def|name=Error Subcode|length=8 bits|text=A value specifying which error occurred.}}
:{| class="wikitable  mw-collapsible mw-collapsed
|+ Error{{nbsp}}Codes{{nbsp}}and{{nbsp}}Subcodes
! rowspan="2" |Error Code !! rowspan="2" |Name !! colspan="2" |subcodes
|-
|Code || Name
|-
|rowspan="3" | 1 || rowspan="3" |Message Header Error || 1 || style="text-align:left"| Connection Not Synchronized
|-
| 2 || style="text-align:left"| Bad Message Length
|-
| 3 || style="text-align:left"| Bad Message Type
|-
|rowspan="6" | 2 || rowspan="6" |OPEN Message Error || 1 || style="text-align:left"| Unsupported Version Number.
|-
|2 || style="text-align:left"| Bad Peer AS.
|-
| 3 || style="text-align:left"| Bad BGP Identifier.
|-
| 4 || style="text-align:left"|Unsupported Authentication Code.
|-
| 5 || style="text-align:left"|Authentication Failure.
|-
| 6 || style="text-align:left"|Unacceptable Hold Time.
|-
| rowspan="11" |3 || rowspan="11"; style="text-align:left"|UPDATE Message Error || 1 || style="text-align:left"|Malformed Attribute List.
|-
| 2 || style="text-align:left"|Unrecognized Well-known Attribute.
|-
| 3 || style="text-align:left"|Missing Well-known Attribute.
|-
| 4 || style="text-align:left"|Attribute Flags Error.
|-
| 5 || style="text-align:left"|Attribute Length Error.
|-
| 6 || style="text-align:left"|Invalid ORIGIN Attribute
|-
| 7 || style="text-align:left"|AS Routing Loop.
|-
| 8 || style="text-align:left"|Invalid NEXT_HOP Attribute.
|-
| 9 || style="text-align:left"|Optional Attribute Error.
|-
| 10 || style="text-align:left"|Invalid Network Field.
|-
| 11 || style="text-align:left"|Malformed AS_PATH.
|-
| 4 || colspan="3" |Hold Timer Expired
|-
| 5 || colspan="3" |Finite State Machine Error
|-
| 6 || colspan="3" |Cease
|}
;{{APHD|def|name=Data|length=variable|text=Optional data to help diagnose the problem.}}

'''Example of NOTIFICATION Message'''
 Type: NOTIFICATION Message (3)
 Major error Code: OPEN Message Error (2)
 Minor error Code (Open Message): Bad Peer AS (2)
 Bad Peer AS: 65200

=== KeepAlive ===
KeepAlive messages are sent periodically, by both peers of a session, to verify that remote peer is still alive.
They should be sent at intervals of one third the <code>holdtime</code>.
{{APHD|start|title=BGP version 4 'KEEPALIVE' message format}}
{{APHD|999|bits1=32|field1=Marker|value1=ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff}}
{{APHD|16|bits1=16|field1=Length|value1=19|bits2=8|field2=Type|value2=4}}
{{APHD|end}}
A keep-alive packet has no data content.
=== Route-Refresh ===
An addition to the initial BGP message types is route-refresh, which allows for soft updating of <code>Adj-RIB-in</code>, without resetting connection.{{Ref RFC|2918}}

Before making use of this feature, the capability 'Route Refresh Capability (2)' should be specified in the 'Open' message. Fine-grained routing updates may be acquired when the capability 'Enhanced Route Refresh Capability (70)' is also given.

{{APHD|start|title=BGP version 4 'ROUTE-REFRESH' message format}}
{{APHD|999|bits1=32|field1=Marker|value1=ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff}}
{{APHD|16|bits1=16|field1=Length|value1=23+|bits2=8|field2=Type|value2=5|bits3=8|border3=right|field3=Address Family Identifier}}
{{APHD|20|bits1=8|border1=left|field1=AFI (cont.)|bits2=8|field2=Message Subtype|bits3=8|field3=SAFI|bits4=8|field4={{nbsp}}|border4=bottom}}
{{APHD|999|bits1=0|border1=top|field1=Network Layer Reachability Information}}
{{APHD|end}}
;{{APHD|def|name=Address Family Identifier|short=AFI|length=16 bits|text=An identifier for the [https://www.iana.org/assignments/address-family-numbers/address-family-numbers.xhtml#address-family-numbers-2 address family] ([[IPv4]], [[IPv6]], [[IPX]], [[AppleTalk]], etc.) This list is maintained by [[IANA]].}}
;{{APHD|def|name=Message Subtype|length=8 bits|text=This field indicates what kind of route-refresh message this is.{{Ref RFC|7313}}}}
;{{APHD|def|name=Subsequent Address Family Identifier|length=8 bit|text=This field provides additional information about the type of the Network Layer Reachability Information (NLRI) carried in the attribute. Values: 1 (unicast); 2 (multicast); 3 (both).}}

;{{APHD|def|name=Network Layer Reachability Information|short=NLRI|length=variable|text=Reachability information, specified as a series of <nowiki><length, prefix></nowiki> tuples.}}

'''Example of ROUTE-REFRESH Message'''
 Type: ROUTE-REFRESH Message (5)
 Address family identifier (AFI): IPv4 (1)
 Subtype: Normal route refresh request (0)
 Subsequent address family identifier (SAFI): [[Unicast]] (1)

== Internal scalability ==
BGP is "the most scalable of all routing protocols."<ref>{{cite web |url=https://www.cisco.com/c/en/us/products/ios-nx-os-software/border-gateway-protocol-bgp/index.html |title=Border Gateway Protocol (BGP) |website=[[Cisco]].com}}</ref>

An autonomous system with internal BGP (iBGP) must have all of its iBGP peers connect to each other in a [[Complete graph|full mesh]] (where everyone speaks to everyone directly). This full-mesh configuration requires that each router maintain a session with every other router. In large networks, this number of sessions may degrade the performance of routers, due to either a lack of memory, or high CPU process requirements.

===Route reflectors===
'''Route reflectors''' (RRs) reduce the number of connections required in an AS. A single router (or two for redundancy) can be made an RR: other routers in the AS need only be configured as peers to them. An RR offers an alternative to the logical full-mesh requirement of iBGP. The purpose of the RR is concentration. Multiple BGP routers can peer with a central point, the RR{{snd}} acting as an RR server{{snd}} rather than peer with every other router in a full mesh. All the other iBGP routers become RR clients.<ref>{{cite IETF |title=BGP Route Reflection: An Alternative to Full Mesh Internal BGP (iBGP) |RFC=4456 |author=T. Bates |display-authors=etal |date=April 2006}}</ref>

This approach, similar to [[OSPF]]'s  DR/BDR feature, provides large networks with added iBGP scalability. In a fully meshed iBGP network of 10 routers, 90 individual CLI statements (spread throughout all routers in the topology) are needed just to define the remote-AS of each peer: this quickly becomes a headache to manage. An RR topology can cut these 90 statements down to 18, offering a viable solution for the larger networks administered by ISPs.

An RR is a [[single point of failure]], therefore at least a second RR may be configured in order to provide redundancy. As it is an additional peer for the other 10 routers, it approximately doubles the number of CLI statements, requiring an additional {{nowrap|1=11 × 2 − 2 = 20}} statements in this case. In a BGP multipath environment, the additional RR can also benefit the network by adding local routing throughput if the RRs are acting as traditional routers instead of just a dedicated RR server role.

RRs and confederations both reduce the number of iBGP peers to each router and thus reduce processing overhead. RRs are a pure performance-enhancing technique, while confederations can also be used to implement more fine-grained policy.

====Rules====
[[File:RR BGP.svg|thumbnail|300px|A typical configuration of a BGP RR deployment.{{Ref RFC|4456|rsection=6}}]]
RR servers propagate routes inside the AS based on the following rules:
* Routes are always reflected to eBGP peers.
* Routes are never reflected to the originator of the route.
* If a route is received from a non-client peer, reflect to client peers.
* If a route is received from a client peer, reflect to client and non-client peers.

====Cluster====
An RR and its clients form a ''cluster''. The ''cluster ID'' is then attached to every route advertised by the RR to its client or non-client peers. A cluster ID is a cumulative, non-transitive BGP attribute, and every RR must prepend the local cluster ID to the cluster list to avoid routing loops.

===Confederation===
Confederations are sets of autonomous systems. In common practice,{{Ref RFC|5065}} only one of the confederation AS numbers is seen by the Internet as a whole. Confederations are used in very large networks where a large AS can be configured to encompass smaller more manageable internal ASs.

The confederated AS is composed of multiple ASs. Each confederated AS alone has iBGP fully meshed and has connections to other ASs inside the confederation. Even though these ASs have eBGP peers to ASs within the confederation, the ASs exchange routing as if they used iBGP. In this way, the confederation preserves next hop, metric, and local preference information. To the outside world, the confederation appears to be a single AS. With this solution, iBGP transit AS problems can be resolved as iBGP requires a full mesh between all BGP routers: a large number of TCP sessions and unnecessary duplication of routing traffic.{{clarify|reason=My guess is this is trying to say that using eBGP within a confederation avoids scaling issues that would exist if iBGP were used instead.|date=October 2022}}

Confederations can be used in conjunction with route reflectors. Both confederations and route reflectors can be subject to persistent oscillation unless specific design rules, affecting both BGP and the interior routing protocol, are followed.{{Ref RFC|3345}}

These alternatives can introduce problems of their own, including the following:
* route oscillation
* sub-optimal routing
* increase of BGP convergence time{{Ref RFC|4098}}

Additionally, route reflectors and BGP confederations were not designed to ease BGP router configuration. Nevertheless, these are common tools for experienced BGP network architects. These tools may be combined, for example, as a hierarchy of route reflectors.

== Stability ==

The routing tables managed by a BGP implementation are adjusted continually to reflect actual changes in the network, such as links or routers going down and coming back up. In the network as a whole, it is normal for these changes to happen almost continuously, but for any particular router or link, changes are expected to be relatively infrequent. If a router is misconfigured or mismanaged, then it may get into a rapid cycle between down and up states. This pattern of repeated withdrawal and re-announcement, known as [[route flapping]] can cause excessive activity in all the other routers that know about the cycling entity, as the same route is continually injected and withdrawn from the routing tables. The BGP design is such that delivery of traffic may not function while routes are being updated. On the Internet, a BGP routing change may cause outages for several minutes.

A feature known as ''route flap damping'' is built into many BGP implementations,{{Ref RFC|2439}} in an attempt to mitigate the effects of route flapping. Without damping, the excessive activity can cause a heavy processing load on routers, which may in turn delay updates on other routes, and so affect overall routing stability. With damping, a route's flapping is [[exponential decay|exponentially decayed]]. At the first instance, when a route becomes unavailable and quickly reappears, damping does not take effect, so as to maintain the normal fail-over times of BGP. At the second occurrence, BGP shuns that prefix for a certain length of time; subsequent occurrences are ignored exponentially longer. After the abnormalities have ceased and a suitable length of time has passed for the offending route, prefixes can be reinstated with a clean slate. Damping can also mitigate [[denial-of-service attack]]s.

It is also suggested that route flap damping is a feature more desirable if implemented to Exterior Border Gateway Protocol Sessions (eBGP sessions or simply called exterior peers) and not on Interior Border Gateway Protocol Sessions (iBGP sessions or simply called internal peers).{{Ref RFC|2439|rsection=4}} With this approach when a route flaps inside an autonomous system, it is not propagated to the external ASs{{snd}} flapping a route to an eBGP will cause a chain of flapping for the particular route throughout the backbone. This method also successfully avoids the overhead of route flap damping for iBGP sessions.

Subsequent research has shown that flap damping can actually lengthen convergence times in some cases, and can cause interruptions in connectivity even when links are not flapping.<ref>{{cite web|url=http://web.eecs.umich.edu/~zmao/Papers/sig02.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://web.eecs.umich.edu/~zmao/Papers/sig02.pdf |archive-date=2022-10-09 |url-status=live|title=Route Flap Damping Exacerbates Internet Routing Convergence|date=November 1998}}</ref><ref>{{cite web | url = http://www.cs.arizona.edu/~bzhang/paper/05-icdcs-dtimer.pdf | last = Zhang | first = Beichuan | title = Timer Interaction in Route Flap Damping | access-date = 2006-09-26 |author2=Pei Dan |author3=Daniel Massey |author4=[[Lixia Zhang]] |date=June 2005 | work = IEEE 25th [[International Conference on Distributed Computing Systems]] | quote = We show that the current damping design leads to the intended behavior only under persistent route flapping. When the number of flaps is small, the global routing dynamics deviates significantly from the expected behavior with a longer convergence delay. }}</ref> Moreover, as backbone links and router processors have become faster, some network architects have suggested that flap damping may not be as important as it used to be, since changes to the routing table can be handled much faster by routers.{{Ref RFC|2439}} This has led the RIPE Routing Working Group to write, "With the current implementations of BGP flap damping, the application of flap damping in ISP networks is NOT recommended. ... If flap damping is implemented, the ISP operating that network will cause side-effects to their customers and the Internet users of their customers' content and services ... . These side-effects would quite likely be worse than the impact caused by simply not running flap damping at all."<ref>{{cite web|url=http://www.ripe.net/ripe/docs/ripe-378 |title=RIPE Routing Working Group Recommendations On Route-flap Damping |publisher= RIPE Network Coordination Centre |date=2006-05-10 | access-date = 2013-12-04 }}</ref>

==Routing table growth==
[[File:BGP Table growth.svg|thumb|BGP table growth on the Internet]]
[[File:Internet AS.svg|thumb|Number of AS on the Internet vs number of registered AS]]

One of the largest problems faced by BGP, and indeed the Internet infrastructure as a whole, is the growth of the Internet routing table. If the global routing table grows to the point where some older, less capable routers cannot cope with the memory requirements or the CPU load of maintaining the table, these routers will cease to be effective gateways between the parts of the Internet they connect. In addition, and perhaps even more importantly, larger routing tables take longer to stabilize after a major connectivity change, leaving [[network service]] unreliable, or even unavailable, in the interim.

Until late 2001, the global routing table was [[exponential growth|growing exponentially]], threatening an eventual widespread breakdown of connectivity. In an attempt to prevent this, ISPs cooperated in keeping the global routing table as small as possible by using [[Classless Inter-Domain Routing]] (CIDR) and [[route aggregation]]. While this slowed the growth of the routing table to a linear process for several years, with the expanded demand for [[multihoming]] by end-user networks, the growth was once again superlinear by the middle of 2004.

===512k day===
A [[Year 2000 problem|Y2K]]-like overflow triggered in 2014 for those models that were not appropriately updated.

While a full IPv4 BGP table {{as of|August 2014|lc=on}} (512k day)<ref>{{Cite web|url=https://www.cisco.com/c/en/us/support/docs/switches/catalyst-6500-series-switches/117712-problemsolution-cat6500-00.html#.U-okMKwClYO.twitter|title=CAT 6500 and 7600 Series Routers and Switches TCAM Allocation Adjustment Procedures|website=Cisco}}</ref><ref>{{cite web |url=http://www.renesys.com/2014/08/internet-512k-global-routes |title=Internet Touches Half Million Routes: Outages Possible Next Week|work = renesys.com|date = 13 August 2014|first = Jim|last = Cowie|archive-url = https://web.archive.org/web/20140813232628/http://www.renesys.com/2014/08/internet-512k-global-routes/ |archive-date = 13 August 2014}}</ref> was in excess of 512,000 prefixes,<ref name= "Potaroo&nbsp;— BGP Table data">{{cite web|url=http://bgp.potaroo.net/index-bgp.html|title=BGP Reports|work=potaroo.net}}</ref> many older routers had a limit of 512k (512,000–524,288)<ref>{{cite web|url=http://www.cisco.com/c/en/us/support/docs/switches/catalyst-6500-series-switches/117712-problemsolution-cat6500-00.html#.U-okMKwClYO.twitter |title= CAT 6500 and 7600 Series Routers and Switches TCAM Allocation Adjustment Procedures|date=9 March 2015|work=Cisco}}</ref><ref>{{cite web|url=http://www.renesys.com/2014/08/internet-512k-global-routes/|title=Internet Touches Half Million Routes: Outages Possible Next Week|author=Jim Cowie|work=Dyn Research|access-date=2015-01-02|archive-date=2014-08-17|archive-url=https://web.archive.org/web/20140817205028/http://www.renesys.com/2014/08/internet-512k-global-routes/|url-status=dead}}</ref> routing table entries. On August 12, 2014, outages resulting from full tables hit [[eBay]], [[LastPass]] and [[Microsoft Azure]], among others.<ref>{{cite news|title=Internet infrastructure 'needs updating or more blackouts will happen'|first1= Juliette |last1=Garside|first2= Samuel|last2= Gibbs|newspaper=The Guardian|date=14 August 2014|url=https://www.theguardian.com/technology/2014/aug/14/internet-infrastructure-needs-updating-more-blackouts-will-happen |access-date=15 Aug 2014}}</ref> A number of Cisco routers commonly in use had [[Ternary Content-Addressable Memory|TCAM]], a form of high-speed [[content-addressable memory]], for storing BGP advertised routes. On impacted routers, the TCAM was by default allocated as 512k IPv4 routes and 256k IPv6 routes. While the reported number of IPv6 advertised routes was only about 20k, the number of advertised IPv4 routes reached the default limit, causing a [[spillover effect]] as routers attempted to compensate for the issue by using slow software routing (as opposed to fast hardware routing via TCAM). The main method for dealing with this issue involves operators changing the TCAM allocation to allow more IPv4 entries by reallocating some of the TCAM reserved for IPv6 routes, which requires a reboot on most routers. The 512k problem was predicted by a number of IT professionals.<ref>{{cite web|url=https://www.nanog.org/meetings/nanog39/presentations/bof-report.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.nanog.org/meetings/nanog39/presentations/bof-report.pdf |archive-date=2022-10-09 |url-status=live |title=BOF report |publisher= www.nanog.org |access-date=2019-12-17}}</ref><ref>{{cite web|url=http://etherealmind.com/tcam-detail-review/|title=TCAM&nbsp;— a Deeper Look and the impact of IPv6|author=Greg Ferro|work=EtherealMind|date=26 January 2011}}</ref><ref>{{cite web|url=http://www.ipv4depletion.com/?p=672|title=The IPv4 Depletion site|work=ipv4depletion.com}}</ref>

The actual allocations, which pushed the number of routes above 512k, were the announcement of about 15,000 new routes in short order, starting at 07:48 UTC. Almost all of these routes were to [[Verizon]] [[Autonomous system (Internet)|Autonomous Systems]] 701 and 705, created as a result of the deaggregation of larger blocks, introducing thousands of new {{IPaddr||24}} routes, and making the routing table reach 515,000 entries. The new routes appear to have been reaggregated within 5 minutes, but instability across the Internet apparently continued for a number of hours.<ref>{{cite web|url=https://www.bgpmon.net/what-caused-todays-internet-hiccup/|title=What caused today's Internet hiccup|work=bgpmon.net}}</ref> Even if Verizon had not caused the routing table to exceed 512k entries in the short spike, it would have soon happened through natural growth.

[[Route summarization]] is often used to improve aggregation of the BGP global routing table, thereby reducing the necessary table size in routers of an AS. Consider AS1 has been allocated the big address space of {{IPaddr|172.16.0.0|16}}, this would be counted as one route in the table, but due to customer requirements or traffic engineering purposes, AS1 wants to announce smaller, more specific routes of {{IPaddr|172.16.0.0|18}}, {{IPaddr|172.16.64.0|18}}, and {{IPaddr|172.16.128.0|18}}. The prefix {{IPaddr|172.16.192.0|18}} does not have any hosts so AS1 does not announce a specific route {{IPaddr|172.16.192.0|18}}. This all counts as AS1 announcing four routes.

AS2 will see the four routes from AS1 ({{IPaddr|172.16.0.0|16}}, {{IPaddr|172.16.0.0|18}}, {{IPaddr|172.16.64.0|18}}, and {{IPaddr|172.16.128.0|18}}) and it is up to the routing policy of AS2 to decide whether or not to take a copy of the four routes or, as {{IPaddr|172.16.0.0|16}} overlaps all the other specific routes, to just store the summary, {{IPaddr|172.16.0.0|16}}.

If AS2 wants to send data to prefix {{IPaddr|172.16.192.0|18}}, it will be sent to the routers of AS1 on route {{IPaddr|172.16.0.0|16}}. At AS1, it will either be dropped or a destination unreachable [[ICMP]] message will be sent back, depending on the configuration of AS1's routers.

If AS1 later decides to drop the route {{IPaddr|172.16.0.0|16}}, leaving {{IPaddr|172.16.0.0|18}}, {{IPaddr|172.16.64.0|18}}, and {{IPaddr|172.16.128.0|18}}, the number of routes AS1 announces drops to three. Depending on the routing policy of AS2, it will store a copy of the three routes, or aggregate {{IPaddr|172.16.0.0|18}} and {{IPaddr|172.16.64.0|18}} to {{IPaddr|172.16.0.0|17}}, thereby reducing the number of routes AS2 stores to two ({{IPaddr|172.16.0.0|17}} and {{IPaddr|172.16.128.0|18}}).

If AS2 now wants to send data to prefix {{IPaddr|172.16.192.0|18}}, it will be dropped or a destination unreachable ICMP message will be sent back at the routers of AS2 (not AS1 as before), because {{IPaddr|172.16.192.0|18}} is not in the routing table.

=== AS number depletion and 32-bit ASNs<span class="anchor" id="AS23456"></span> ===
In 1995, the first BGP-4 specification coded AS numbers on 16 bits,{{Ref RFC|1771}} for 64,510 possible public AS numbers.{{efn|ASN 64512 to 65534 were reserved for private use and 0 and 65535 are forbidden.}} In 2011, only 15,000 AS numbers were still available, and projections<ref>[http://www.potaroo.net/tools/asn16/ ''16-bit Autonomous System Report''], [[Geoff Huston (scientist)]] 2011 (original archived at https://web.archive.org/web/20110906085724/http://www.potaroo.net/tools/asn16/)</ref> were envisioning a complete depletion of available AS numbers in September 2013.

In 2007 already, the AS coding was extended from 16 to 32 bits,{{Ref RFC|4893}} while retaining the 16-bit AS range (0 to 65535) and its reserved AS numbers. This now allows up to 4 billion available AS numbers. An additional private AS range is also defined.{{Ref RFC|6996}}{{efn|ASN 4200000000 to 4294967294 are private and 4294967295 is forbidden.{{Ref RFC|7300}}}} To allow the traversal of router groups not able to manage those new ASNs, the new attribute '''AS4_PATH''' (optional transitive) and the special 16-bit ASN '''AS_TRANS''' (AS23456) is used.{{Ref RFC|6793}} 32-bit ASN assignments started in 2007.

=== Load balancing ===
Another factor contributing to the growth of the routing table is the need for load balancing of [[multi-homed]] networks. It is not a trivial task to balance the inbound traffic to a multi-homed network across its multiple inbound paths, due to limitations of the BGP route selection process. For a multi-homed network, if it announces the same network blocks across all of its BGP peers, the result may be that one or several of its inbound links become congested while the other links remain under-utilized, because external networks all picked that set of congested paths as optimal. Like most other routing protocols, BGP does not detect congestion.

To work around this problem, BGP administrators of that multihomed network may divide a large contiguous IP address block into smaller blocks and tweak the route announcement to make different blocks look optimal on different paths, so that external networks will choose a different path to reach different blocks of that multihomed network. Such cases will increase the number of routes as seen on the global BGP table.

One method to address the routing table issue associated with load balancing is to deploy [[Locator/Identifier Separation Protocol]] (BGP/LISP) gateways within an [[Internet exchange point]] to allow ingress traffic engineering across multiple links. This technique does not increase the number of routes seen on the global BGP table.

== Security ==
By design, routers running BGP accept advertised routes from other BGP routers by default. This allows for automatic and decentralized routing of traffic across the Internet, but it also leaves the Internet potentially vulnerable to accidental or malicious disruption, known as [[BGP hijacking]]. Due to the extent to which BGP is embedded in the core systems of the Internet, and the number of different networks operated by many different organizations that collectively make up the Internet, correcting this vulnerability (such as by introducing the use of cryptographic keys to verify the identity of BGP routers) is a technically and economically challenging problem.<ref>{{cite news|author=Craig Timberg |url=https://www.washingtonpost.com/sf/business/2015/05/31/net-of-insecurity-part-2/|title=Quick fix for an early Internet problem lives on a quarter-century later|newspaper=The Washington Post|date=2015-05-31 |access-date=2015-06-01}}</ref>

== Extensions ==
Multiprotocol Extensions for BGP (MBGP), sometimes referred to as Multiprotocol BGP or Multicast BGP and defined in {{IETF RFC|4760}}, is an extension to BGP that allows different types of addresses (known as address families) to be distributed in parallel. Whereas standard BGP supports only IPv4 unicast addresses, Multiprotocol BGP supports IPv4 and IPv6 addresses and it supports unicast and multicast variants of each. Multiprotocol BGP allows information about the topology of IP multicast-capable routers to be exchanged separately from the topology of normal IPv4 unicast routers. Thus, it allows a multicast routing topology different from the unicast routing topology. Although MBGP enables the exchange of inter-domain multicast routing information, other protocols, such as the Protocol Independent Multicast family, are needed to build trees and forward multicast traffic.
Multiprotocol BGP is also widely deployed in the case of [[MPLS]] L3 VPN, to exchange VPN labels learned for the routes from the customer sites over the MPLS network, in order to distinguish between different customer sites when the traffic from the other customer sites comes to the [[provider edge router]] for routing.

Another extension to BGP is [[multipath routing]]<!--or is it [[Equal-cost multi-path routing]]?-->. This typically requires identical MED, weight, origin, and AS-path, although some implementations provide the ability to relax the AS-path checking to only expect an equal path length rather than the actual AS numbers in the path being expected to match too. This can then be extended further with features like Cisco's dmzlink-bw which enables a ratio of traffic sharing based on bandwidth values configured on individual links.

By default, BGP only supports the advertisement of a single locally selected best path to its neighbors through its Update messages. {{IETF RFC|7911}} defines the '''ADD-PATH''' extension, which allows a BGP speaker to advertise multiple paths for the same destination to peers. One application for this is when using [[route reflector]]s (RRs), because then the RR can advertise all known route paths to its clients, instead of sending only a single route it selected based on its local decision process, which is likely not the best path for all of its clients.

== Uses ==
BGP4 is standard for Internet routing and required of most [[Internet service provider]]s (ISPs) to establish routing between one another. Very large private [[IP network]]s use BGP internally. An example [[use case]] is the joining of a number of large [[Open Shortest Path First]] (OSPF) networks when OSPF by itself does not scale to the size required. Another reason to use BGP is multihoming a network for better redundancy, either to multiple access points to a single ISP or to multiple ISPs.

== Implementations ==
Routers, especially small ones intended for [[small office/home office]] (SOHO) use, may not include BGP capability. Other commercial routers may need a specific software executable image that supports BGP, or a license that enables it. Devices marketed as [[layer-3 switch]]es are less likely to support BGP than devices marketed as [[Router (computing)|routers]], but many high-end layer-3 switches can run BGP.

Products marketed as switches may have a size limitation on BGP tables that is far smaller than a full Internet table plus internal routes. These devices may be perfectly reasonable and useful when used for BGP routing of some smaller part of the network, such as a [[confederation-AS]] representing one of several smaller enterprises that are linked, by a BGP [[backbone of backbones]], or a small enterprise that announces routes to an ISP but only accepts a [[default route]] and perhaps a small number of aggregated routes.

A BGP router used only for a network with a single point of entry to the Internet may have a much smaller routing table size (and hence RAM and CPU requirements) than a multihomed network. Even simple multihoming can have a modest routing table size. The actual amount of memory required in a BGP router depends on the amount of BGP information exchanged with other BGP speakers and the way in which the particular router stores BGP information. The router may have to keep more than one copy of a route, so it can manage different policies for route advertising and acceptance to a specific neighboring AS. The term ''view'' is often used for these different policy relationships on a running router.

If one router implementation takes more memory per route than another implementation, this may be a legitimate design choice, trading processing speed against memory. A full IPv4 BGP table {{as of|September 2025|lc=on}} is in excess of one million prefixes.<ref>{{cite web |title=IPv4 Routing Table Report - Japan (Global) view - bgp-stats|url=https://orbit.apnic.net/hyperkitty/list/bgp-stats@lists.apnic.net/thread/FPRZKGQ5BJFRSA4ZDR5EFMQFZZFS7X6Z/|access-date=2025-09-20|website=orbit.apnic.net|publisher=[[APNIC]]}}</ref><ref name="Potaroo&nbsp;— BGP Table data"/> Large ISPs may add another 50% for internal and customer routes. Again, depending on implementation, separate tables may be kept for each view of a different peer AS.

Notable free and open-source implementations of BGP include:
* [[Bird Internet routing daemon|BIRD]], a [[GPL]] routing package for Unix-like systems.
* [[FRRouting]], a fork of Quagga for [[Unix-like]] systems; and its ancestors:
** [[Quagga (software)|Quagga]], a fork of GNU Zebra for [[Unix-like]] systems (no longer developed).
** [[GNU Zebra]], a GPL routing suite supporting BGP4 (decommissioned).<ref>{{Cite web|url=https://www.gnu.org/software/zebra/|title=Zebra - GNU Project - Free Software Foundation}}</ref>
* [[OpenBGPD]], a [[BSD licence|BSD-licensed]] implementation by the [[OpenBSD]] team.
* [[XORP]], the eXtensible Open Router Platform, a BSD-licensed suite of routing protocols.

Systems for testing BGP conformance, load or stress performance come from vendors such as:
* [[Agilent Technologies]]
* [[GNS3]] open source [[network simulator]]
* [[Ixia (company)|Ixia]]
* [[Spirent]]

==See also==
* {{annotated link|2021 Facebook outage}}
* {{annotated link|AS 7007 incident}}
* {{annotated link|BGP Monitoring Protocol}}
* {{annotated link|Default-free zone}}
* {{annotated link|Internet Assigned Numbers Authority}}
* {{annotated link|Packet forwarding}}
* {{annotated link|Private IP}}
* {{annotated link|QPPB}}
* {{annotated link|Regional Internet registry}}
* {{annotated link|Resource Public Key Infrastructure}}
* {{annotated link|Route filtering}}
* {{annotated link|Routing Assets Database}}
* {{annotated link|Timeline of the history of the Internet}}

== Notes ==
{{Notelist}}

== Standards documents for BGP-4==
* {{Sum RFC|1772|ref=yes}}
* {{Sum RFC|1997|ref=yes}}
* {{Sum RFC|2439|ref=yes}}
* {{Sum RFC|2918|ref=yes}}
* {{Sum RFC|3765|ref=yes}}
* {{Sum RFC|4271|ref=yes}}
* {{Sum RFC|4272|ref=yes}}
* {{Sum RFC|4273|ref=yes}}
* {{Sum RFC|4274|ref=yes}}
* {{Sum RFC|4275|ref=yes}}
* {{Sum RFC|4276|ref=yes}}
* {{Sum RFC|4277|ref=yes}}
* {{Sum RFC|4278|ref=yes}}
* {{Sum RFC|4360|ref=yes}}
* {{Sum RFC|4456|ref=yes}}
* {{Sum RFC|4724|ref=yes}}
* {{Sum RFC|4760|ref=yes}}
* {{Sum RFC|5065|ref=yes}}
* {{Sum RFC|5492|ref=yes}}
* {{Sum RFC|5701|ref=yes}}
* {{Sum RFC|6793|ref=yes}}
* {{Sum RFC|7153|ref=yes}}
* {{Sum RFC|7313|ref=yes}}
* {{Sum RFC|7606|ref=yes}}
* {{Sum RFC|7911|ref=yes}}
* {{Sum RFC|8092|ref=yes}}
* {{Sum RFC|8195|ref=yes}}
* {{Sum RFC|8642|ref=yes}}
* {{Sum RFC|8955|ref=yes}}
* {{Sum RFC|9552|ref=yes}}

== References ==

{{Reflist}}

== Further reading ==
* {{citation |url=http://docwiki.cisco.com/wiki/Border_Gateway_Protocol |title=Border Gateway Protocol (BGP) |archive-url=https://web.archive.org/web/20110708155259/http://docwiki.cisco.com/wiki/Border_Gateway_Protocol |archive-date=2011-07-08 |publisher=[[Cisco Systems]] |work=IOS Technology Handbook}}
* {{Cite book|title=BGP|first=Iljitsch|last=Van Beijnum|isbn=978-0-596-00254-1|year=2002|publisher=O'Reilly Media Inc.|url=https://www.oreilly.com/library/view/bgp/9780596002541/|access-date=2025-12-31}}

== External links ==
* [https://www.bgp4.as BGP Routing Resources] (includes a dedicated section on [http://www.bgp4.as/security BGP & ISP Core Security])
* [http://bgp.potaroo.net/ BGP table statistics]

{{Authority control}}

[[Category:Internet properties established in 1994]]
[[Category:Internet Standards]]
[[Category:Internet protocols]]
[[Category:Routing protocols]]
[[Category:Internet architecture]]
[[Category:Application layer protocols]]