BGP-4 Protocol Overview Border Gateway Protocol Version 4 (BGP-4), documented in RFC 1771, is the current exterior routing protocol used for the global Internet. BGP is essentially a distance-vector algorithm, but with several added twists. Other BGP-related documents are RFC 1772 (BGP Application), RFC 1773 (BGP Experience), RFC 1774 (BGP Protocol Analysis), and RFC 1657 (BGP MIB).
BGP uses TCP as its transport protocol, on port 179. On connection start, BGP peers exchange complete copies of their routing tables, which can be quite large. However, only changes (deltas) are then exchanged, which makes long running BGP sessions more efficient than shorter ones.
BGP's basic unit of routing information is the BGP path, a route to a certain set of CIDR prefixes. Paths are tagged with various path attributes, of which the most important are AS_PATH and NEXT_HOP.
One of BGP-4's most important functions is loop detection at the Autonomous System level, using the AS_PATH attribute, a list of Autonomous Systems being used for data transport. The syntax of this attribute is made more complex by its need to support path aggregation, when multiple paths are collapsed into one to simplify further route advertisements. A simplified view of AS_PATH is that it is the list of Autonomous Systems that a route goes through to reach its destination. Loops are detected and avoided by checking for your own AS number in AS_PATH's received from neighboring Autonomous Systems.
Every time a BGP path advertisement crosses an Autonomous System boundary, the NEXT_HOP attribute is changed to the IP address of the boundary router. Conversely, as a BGP path advertisement is passed among BGP speakers in the same AS, the NEXT_HOP attribute is left untouched. Consequently, BGP's NEXT_HOP is always the IP address of the first router in the next autonomous system, even though this may actually be several hops away. The AS's interior routing protocol is responsible for computing an interior route to reach the BGP NEXT_HOP. This leads to the distinction between Internal BGP (IBGP) sessions (between routers in the same AS) and External BGP (EBGP) sessions (between routers in different AS's). NEXT_HOPs are only changed across EBGP sessions, but left intact across IBGP sessions.
The two most important consequences of this design are the need for interior routing protocols to reach one hop beyond the AS boundary, and for BGP sessions to be fully meshed within an AS. Since the NEXT_HOP contains the IP address of a router interface in the next autonomous system, and this IP address is used to perform routing, the interior routing protocol must be able to route to this address. This means that interior routing tables must include entries one hop beyond the AS boundary. Furthermore, since BGP does not relay routing traffic from one Interior BGP session to another (only from an Exterior BGP session to an IBGP session or another EBGP session), BGP speakers must be fully meshed. When a BGP routing update is received from a neighboring AS, it must be relayed directly to all other BGP speakers in the AS. Do not expect to relay BGP paths from one router, through another, to a third, all within the same AS.
It the responsibility of the BGP implementation to select among competing paths using a nearly completely undefined algorithm. RFC 1771 states only that the computation be based on "preconfigured policy information. The exact nature of this policy information and the computation involved is a local matter." Since the AS_PATH attribute includes a list of Autonomous Systems used to reach the destination, it's possible to implement primative policy decisions such as "avoid all routes through AS XXXX".
A free software implementation of BGP-4 can be found in Gated.