BGP

Definitions

Term	Definition
IX	Internet Exchange
Transit	Accessing a backbone which interconnects other networks
Peering	Providing an interconnect between two or more networks
Tier 1 ISP	Only peers with other ISPs, connecting to all tier 1 ISPs guarantees connectivity to the entire internet
Tier 2 ISP	An ISP which uses a combination of peering and transit from Tier 1 ISPs
Tier 3 ISP	A smaller ISP with a minimal network, very little peering, receiving transit from a tier 1 or 2 ISP
IGP	Interior Gateway Protocol, a type of routing protocol used on smaller-scale, sometimes multi-site networks
EGP	Exterior Gateway Protocol, a type of routing protocol used outside of a network for internetwork, not to be confused with the deprecated protocol by the same name
BGP	Border Gateway Protocol, a routing protocol used for large-scale, internetworking applications
RIP	Routing Information Protocol, a distance-vector routing protocol
OSPF	Open Shortest Path First, a link-state routing protocol
AS	Autonomous System, a value used by BGP to group routes

Routing

Typically, routers store a table of the possible routes for an IP packet to take. These tables are usually a combination of directly connected routes and routes that have been statically set to point at another gateway which is directly connected. An example routing table is below for reference:

Route	Next Hop	Cost
10.0.0.0/16	Directly Connected on interface eth0	0
10.1.0.0/16	Directly Connected on interface eth1	0
10.2.0.0/16	10.1.25.4	10

In this scenario, a packet from 10.0.2.45 destined for 10.2.55.4 would be forwarded to the router at 10.1.25.4, which is directly available to the current router.

On larger and more complex networks, manually maintaining these routing tables becomes tedious, especially in complex network setups with multiple possible routes of varying cost. The solution to this problem is to use routing protocols, which automatically distribute routes and calculate cost to optimize routing.

Routing Protocols

The most basic of routing protocols is the distance-vector Routing Information Protocol, which periodically broadcasts the routes onto the specified broadcast domain, listening for other routers to share their routes, and forwarding received routes onto its other broadcast domains (in the process incrementing the cost). Notably, early versions of RIP predate Variable-Length Subnet Masks (VLSM), as they did not carry a subnet mask and instead used classful networking. A more powerful and complex alternative is Open Shortest Path First (OSPF). Unlike RIP and its newer alternatives, OSPF only sends updates when there is a change in the network, maintaining an internal topology map, and distributing limited updates to confirm that the router is still online. OSPF is therefore a link-state protocol, which calculates its cost metric based not just on the hop count but also the capacity of a particular link.

BGP is a distance-path protocol, which tracks more than just the hop count but does not attempt to maintain an internal topology map. Rather than using OSPF "areas", which group together routes to build an internal map, BGP makes use of Autonomous Systems (AS) numbers (or ASNs for short). BGP routing tables therefore contain ASNs, presuming that if a router can reach one network which is a part of that ASN, it can reach the rest as well. BGP routers only forward on the shortest routes it knows to a destination, but it can maintain multiple routes to a destination for fault tolerance.

BGP supports carrying routes of many types, including both classless and classful networks, and it even supports single IP addresses where the address is not a network or broadcast address. Since its creation in 1989, BGP has undergone 3 further revisions, adding support for AS identification, connection termination when two routers attempt to establish a TCP session with each other at the same time, and CIDR and aggregation support.

BGP Protocol

BGP (RFC 1771) uses TCP port 179, unlike most other routing protocols, which either run on top of IP directly or broadcast using UDP. With BGP, the peer addresses area already known, so TCP connections can be initiated directly. BGP packets use the following format:

Marker	Length	Type	Data
16 bytes	2 bytes	1 byte	0 - 4077 bytes

The message type can be one of either open (1), update (2), notification (3), or keepalive (4), or a newer message type defined in later RFCs. Each message type has a different format, stored in the data field.

Open

The open message is sent after the TCP connection is opened, to describe the capabilities of the client.

Version	ASN	Hold Time	Identifier	Parameter Length	Optional Parameters
1 bytes	2 bytes	2 bytes	4 bytes	1 byte	0 - 255 bytes

The BGP version nowadays should be 4. Next, the ASN of the sender identifies who is introducing the routes, and the hold time describes how long the BGP (not TCP) session should be kept alive. The hold time must be at least 3 seconds, the lowest of the hold times between the sender and receiver will be used, and if the time is set to 0, the connection will remain open indefinitely. The identifier is one of the sender's IP addresses, and must remain the same for all BGP sessions. Next, the parameter length specifies the size, in bytes, of the optional parameters field. The optional parameters field, in turn, contains options in the following format:

Parameter Identifier	Value
1 byte	1 byte

Once an open message has been accepted by the receiver, the two routers will exchange keepalive messages and send the full routing table using update messages, as configured. Once complete, only keepalive messages and incremental updates will be sent.

Update

Update messages contain routes and are used to both transfer the entire routing table from one device to another, and to send incremental updates to that table.

UR Length	Withdrawn Routes	PA Routes	Path attributes	NLRI
2 bytes	0 - 65535 bytes	2 bytes	0 - 65535 bytes