Border Gateway Protocol
From Wikipedia, the free encyclopedia
| Internet protocol suite |
| 5. Application layer |
|
DHCP • DNS • FTP • HTTP • IMAP4 • IRC • MIME • POP3 • SIP • SMTP • SNMP • SSH • TELNET • TLS/SSL • RPC • RTP • SDP • SOAP • … |
| 4. Transport layer |
| 3. Network layer |
| 2. Data link layer |
|
ATM • Bluetooth (PAN-Profile) • Ethernet • FDDI • Frame Relay • GPRS • Modems • PPP • Wi-Fi • … |
| 1. Physical layer |
|
Bluetooth RF • Ethernet physical layer • ISDN • Modems • RS232 • SONET/SDH • USB • Wi-Fi • … |
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 (especially true if they are multihomed), it is one of the most important protocols of the Internet. Compare this with Signalling System #7, which is the inter-provider core call setup protocol on the PSTN.
Contents |
[edit] BGP operation
BGP neighbors, 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.
[edit] Finite state machine
In order to make decisions in its operations with other BGP peers, a BGP peer uses a simple finite state machine 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 definition defines the messages that each peer should exchange in order to transition the session from one state to another.
[edit] BGP problems and mitigation
[edit] Route flap damping
The routing tables managed by a BGP implementation are adjusted continuously to reflect actual changes in the network, such as links breaking and being restored or routers going down and coming back up. In the network as a whole it is normal for these changes to happen continuously, but for any particular router or link changes are supposed 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 can cause excessive activity in all the other routers that know about the broken link, as the same route is continuously injected and withdrawn from the routing tables. This excessive activity is known as "route flapping".
A feature known as "damping" is built into many BGP implementations in an attempt to mitigate the effects of this route flapping. Without damping the excessive activity can cause a heavy processing load on routers, and so affect 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 [1]. This topic is controversial and is the subject of much research.
[edit] 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 of 2004. The global routing table hit 200,000[1] entries on or about October 13, 2006.
[edit] 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 AS. The mis-configuration is commonly due to AS's with incomplete routing tables.
[edit] Large IBGP Peer Meshes
An Autonomous System with IBGP must have all of its IBGP peers connect to each other in a full mesh (where everyone speaks to everyone directly.) The problem with this is that past 3 peers, full meshes become laborious to the design (for 4 peers you would need 6 connections; for 5 peers you would need 10). BGP solves this mesh-scaling issue with a Route reflector.
[edit] Implementations
- Quagga, a fork of GNU Zebra for Unix-like systems.
- GNU Zebra, a GPL routing suite supporting BGP4.
- OpenBGPD[2], a BSD licensed implementation by the OpenBSD team.
- XORP, the eXtensible Open Router Platform, a BSD licensed suite.
- BIRD, a GPL routing package for Unix-like systems.
[edit] BGP simulators
- BGPlay, a Java applet that presents a graphical visualization of BGP routes and updates for any real AS on the Internet
- SSFnet, SSFnet network simulator includes a BGP implementation developed by BJ Premore
- C-BGP, a BGP simulator able to simulate large ASes
- BGP++, a patch integrating GNU Zebra software on ns-2 and GTNetS network simulators
- ns-BGP, a BGP extension for ns-2 simulator based on the SSFnet implementation
[edit] References
- ^ Zhang, Beichuan; Pei Dan, Daniel Massey, Lixia Zhang (June 2005). Timer Interaction in Route Flap Damping. IEEE 25th International Conference on Distributed Computing Systems. Retrieved on 2006-09-26. “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.”
[edit] See also
- Autonomous system (Internet)
- Internet Assigned Numbers Authority
- Regional Internet Registry
- Routing
- Routing Assets Database (RADB)
[edit] 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 Università degli Studi Roma Tre
- Linux Magazine: Demystifying BGP (Good, Detailed BGP explanation; requires registration)
- Some important BGP RFCs
- RFC 4456, BGP Route Reflection - An Alternative to Full Mesh Internal BGP (IBGP)(obsoletes: RFC 2796)
- RFC 4278, Standards Maturity Variance Regarding the TCP MD5 Signature Option (RFC 2385) and the BGP-4 Specification
- RFC 4277, Experience with the BGP-4 Protocol
- RFC 4276, BGP-4 Implementation Report
- RFC 4275, BGP-4 MIB Implementation Survey
- RFC 4274, BGP-4 Protocol Analysis
- RFC 4273, Definitions of Managed Objects for BGP-4
- RFC 4272, BGP Security Vulnerabilities Analysis
- RFC 4271, A Border Gateway Protocol 4 (BGP-4) (obsoletes: RFC 1771)
- RFC 3392, Capabilities Advertisement with BGP-4
- RFC 3065, Autonomous System Confederations for BGP
- RFC 2918, Route Refresh Capability for BGP-4
- RFC 1772, Application of the Border Gateway Protocol in the Internet Protocol (BGP-4) using SMIv2
- Obsolete RFCs
- RFC 2796, Obsolete - BGP Route Reflection - An Alternative to Full Mesh IBGP
- 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)
