Border Gateway Protocol

The Border Gateway Protocol (BGP) is the core routing protocol of the Internet. It works by maintaining a table of IP networks or 'prefixes' which designate network reachability between autonomous systems (AS). It is described as a path vector protocol. BGP does not use traditional IGP metrics, but makes routing decisions based on path, network policies and/or rulesets. As of January 2006, the current version of BGP, version 4, is codified in RFC 4271.

BGP supports Classless Inter-Domain Routing and uses route aggregation to decrease the size of routing tables. Since 1994, version four of the protocol has been in use on the Internet. All previous versions are considered obsolete.

BGP was created to replace the EGP routing protocol to allow fully decentralized routing in order to allow the removal of the NSFNET Internet backbone network. This allowed the Internet to become a truly decentralized system.

Very large private IP networks can also make use of BGP. An example would be the joining of a number of large Open Shortest Path First (OSPF) networks where OSPF by itself would not scale to size. Another reason to use BGP would be multihoming a network for better redundancy.

Most Internet users do not use BGP directly. However, since most Internet service providers must use BGP to establish routing between one another, it is one of the most important protocols of the Internet. Compare and contrast this with Signalling System #7, which is the inter-provider core call setup protocol on the PSTN.

BGP operation

BGP neighbours, or peers, are established by manual configuration between routers to create a TCP session on port 179. A BGP speaker will periodically send 19-byte keepalive messages to maintain the connection (every 60 seconds by default). Among routing protocols, BGP is unique in using TCP as its transport protocol.

When BGP is running inside an autonomous system (AS), it is referred to as Internal BGP (IBGP Interior Border Gateway Protocol). iBGP routes have an administrative distance of 200. When BGP runs between ASs, it is called External BGP (EBGP Exterior Border Gateway Protocol), and it has an administrative distance of 20. A BGP router that routes IBGP traffic, is called a transit router. Routers that sit on the boundary of an AS and that use EBGP to exchange information with the ISP are border or edge routers.

In the simplest solution all routers within a single AS and participating in BGP routing must be configured in a full mesh: each router must be configured as peer to every other router. This causes scaling problems, since the number of required connections grows quadratically with the number of routers involved. To get around this, two solutions are built into BGP: route reflectors (RFC 2796) and confederations (RFC 3065).

Route reflectors reduce the number of connections required in an AS. A single router (or two for redundancy) can be made a route reflector: other routers in the AS need only be configured as peers to them.

Confederations are used in very large networks where a large AS can be configured to encompass smaller more manageable internal ASs. Confederations can be used in conjunction with route reflectors.

Finite state machine

A BGP peer uses a simple finite state machine (FSM) to make decisions in its operations with other BGP peers. The FSM consists of six states - Idle, Connect, Active, OpenSent, OpenConfirm, and Established. A BGP peer will transition the TCP connection to another peer between these states as it attempts to establish and maintain a session with that peer.

BGP problems and mitigation

Route flapping

A feature known as "damping" is built into many BGP implementations in an attempt to mitigate the effects of route flapping. Flapping of routes can be caused by WAN / WLAN links or physical interfaces mending and breaking or by misconfigured or mismanaged routers. Without damping, routes can be injected and withdrawn rapidly from routing tables, possibly causing a heavy processing load on routers, thus affecting overall routing stability.

With damping, a route's flapping is exponentially decayed. At first instance when a route becomes unavailable but quickly reappears for whatever reason, then the 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 timed out exponentially. After the abnormalities have ceased and a suitable length of time has passed for the offending route, prefixes can be reinstated and its slate wiped clean. Damping can also mitigate malicious denial of service attacks; damping timings are highly customizable.

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 absorbed much faster by routers. Some have even suggested that damping may make things worse, not better, in such an environment. This topic is controversial and is the subject of much research.

Routing table growth

One of the largest problems faced by BGP, and indeed the Internet infrastructure as a whole, comes from 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 (see above) after a major connectivity change, leaving network service unreliable, or even unavailable, in the interim.

Until late 2001, the global routing table was growing exponentially, threatening an eventual widespread breakdown of connectivity. In an attempt to prevent this from happening, there was a cooperative effort by ISPs to keep the global routing table as small as possible, by using 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 exponential by mid 2004.

BGP black holes

A network black hole can occur in BGP intentionally or through mis-configuration. Intentional black holing of routes through BGP is a technique to discard traffic silently across an ASN. The mis-configuration is commonly due to ASN's with incomplete routing tables.

Implementations

Quagga, a fork of GNU Zebra for Unix-like systems
GNU Zebra, a GPL routing suite supporting BGP4
OpenBGPD, a BSD licensed implementation by the OpenBSD team for BSD descendants
XORP, the eXtensible Open Router Platform, a BSD licenced suite
BIRD, a GPL routing package for Unix-like systems

External links

BGP Routing Resources (includes a dedicated section on BGP & ISP Core Security)
BGP table statistics
ASNumber Firefox Extension showing the AS number and additional information of the website currently open
RIPE Routing Information Service collecting over 300 IPv4 and IPv6 BGP feeds at 12 sites in Europe, Japan and North America
RIS Looking Glass into the Default Free Routing zone of the Internet
RISwhois providing IPv4/IPv6 Address to BGP AS Origin Mapping
RIS BGPlay BGP routing visualization tool by Uni Roma
Linux Magazine: Demystifying BGP (Good, Detailed BGP explanation; requires registration)
Some important BGP RFCs
- RFC 4271, A Border Gateway Protocol 4 (BGP-4) (obsoletes: RFC 1771)
- RFC 4272, BGP Security Vulnerabilities Analysis
- RFC 4273, Definitions of Managed Objects for BGP-4
- RFC 4274, BGP-4 Protocol Analysis
- RFC 4275, BGP-4 MIB Implementation Survey
- RFC 4276, BGP-4 Implementation Report
- RFC 4277, Experience with the BGP-4 Protocol
- RFC 4278, Standards Maturity Variance Regarding the TCP MD5 Signature Option (RFC 2385) and the BGP-4 Specification
- RFC 3392, Capabilities Advertisement with BGP-4
- RFC 3065, Autonomous System Confederations for BGP
- RFC 2918, Route Refresh Capability for BGP-4
- RFC 2796, BGP Route Reflection - An Alternative to Full Mesh IBGP
- RFC 1772, Application of the Border Gateway Protocol in the Internet Protocol (BGP-4) using SMIv2
Obsolete RFCs
- RFC 1965, Obsolete - Autonomous System Confederations for BGP
- RFC 1771, Obsolete - A Border Gateway Protocol 4 (BGP-4)
- RFC 1657, Obsolete - Definitions of Managed Objects for the Fourth Version of the Border Gateway
- RFC 1655, Obsolete - Application of the Border Gateway Protocol in the Internet
- RFC 1654, Obsolete - A Border Gateway Protocol 4 (BGP-4)
- RFC 1105, Obsolete - Border Gateway Protocol (BGP)

BGP Interactions at Router Startup Described as a Sequence Diagram (PDF)

Internet standards | Internet protocols | Routing protocols | Internet architecture

Obsolete

Gourt Home::Gourt :: Border Gateway Protocol