Lecture #13 - BGPv4: Part 1

Border Gateway Protocol - Version 4

What is it?

Border Gateway Protocol version 4 (BGPv4) is the exterior routing protocol used to route between Autonomous Systems (AS) - an AS is usually a group of networks and/or subnets under one administrative control. RFC4271 is the current RFC for BGPv4.

Within each individual AS an interior routing protocol (such as RIP, IGRP, EIGRP or OSPF) is used to exchange routing information.

With BGP each AS is identified by a 16-bit AS number assigned by one of the Internet registries - ARIN, RIPE NCC or APNIC.

There were almost 31,000 separate ASs being advertised within the Internet as at April 2009 (up from 28,000 just 12 months earlier) - see http://bgp.potaroo.net/ for some impressive graphs and figures!

BGPv4 may also be used within an AS, however this is to exchange exterior routing information between routers, not as an interior routing protocol. This is the case for ISPs, where they want to keep all BGP speakers consistent. Internal BGP (IBGP) may co-exist with other interior routing protocols.

BGP AS Types

When to use BGP

When multiple connections exist to one ISP.
When multiple ISPs are used and routing needs to be optimised. eg. Multi-Homed Stub AS.
When you want to influence path selection.
When you are a "transit AS".

When not to use BGP

When connected to a single ISP - eg. Stub AS.
When there is to be no control over the path traffic takes out of the AS.
If the links between the ASs are heavily loaded.
When routers have limited memory and/or CPU power.

At April 2009 the full BGP routing table contains around 300,000 active routes (up from 260,000 active routes in April 2008). You may not want it all!

BGP Characteristics

Unlike internal routing protocols, BGP has to be told who it is to talk to (rather than discovering neighbours itself). In BGP terminology, a router must be told who its peers are. In turn, the peers must be similarly configured. This is because peering arrangements have to be negotiated between a customer and the ISP (or between ISPs if that is the connection being established).
When BGP first establishes a relationship, the routers exchange (possibly filtered) copies of their routing tables. After that, only incremental changes are sent.
BGP uses long-lived TCP connections (using TCP port 179) to carry its routing information.
BGP keeps all the topology information learned from its peers in the "BGP table". If a destination becomes unreachable, BGP can select an alternative path without having to request any further routing information.
BGP uses a simple Distance Vector to select the best path to insert in the routing table (a count of the number of ASs in the path). As a result it is often referred to as a Path Vector protocol.

EBGP and IBGP

External BGP

External BGP is run between routers that are in different ASs. A router can only belong to one AS, however the each end of a link between the two are in different ASs. For example, R1 and R2 below:

Normally, EBGP peers are required to be directly connected (ie. they have interfaces that are directly connected via the same subnet).

Internal BGP

Internal BGP is run between routers in the same AS (eg. R2 and R3 in the previous diagram). Internal BGP peering is required when the AS is a transit AS for BGP routed traffic.

Unlike EBGP, there is no requirement for routers to be directly connected. They just have to be reachable from one another. In fact, often IBGP traffic will be routed using routes determined via an interior routing protocol!

If an IBGP router receives a route from an EBGP neighbour, it will pass it to its immediate IBGP neighbours (with the same "next hop" attribute). This keeps all BGP speakers witin the same AS in synchronisation with each other.

Note that IBGP routers don't pass the BGP routes to other IBGP routers, so the peering relationships need to be fully meshed. ie. every IBGP router needs to have a peer relationship with an EBGP router.

Starting BGP

On Cisco routers, it is deceptively easy to start BGP (of course there is a lot more involved than just starting the BGP process :)

interface Ethernet0/0              Configure an network connection.
 ip address x.x.x.x   y.y.y.y      Our IP address and subnet mask
....
ip classless                       Use CIDR/VLSM (not A,B,C)
....
router bgp 200                     Start BGP! Our router is in AS200
network IP_address mask IP_mask    Networks to announce to peers
network ....                       insert actual numbers here
network ....                       Can announce multiple networks
....
neighbor A.B.C.D remote-as 300     Who we are peering with

BGP Message Types

Open

This is the first message sent when establishing TCP session. It includes hold-time and router ID.

Keepalive

These are used to confirms an Open message and to keep the connection live. Once a BGP session has been established, keepalive messages are normally sent at regular intervals (on Cisco IOS they are sent every 60 seconds, or one third of the hold-time). If a keepalive or update message is not received within the hold-time the BGP session is closed.

Notification

Sent when an error is detected and the connection is immediately closed.

Update

Each update message describes one BGP route - a path through various ASs to one or more CIDR networks. An update message consists of the following information:

Network Layer Reachability Information (NLRI): The NLRI consists of one or more IP network addresses that are reachable via this BGP route, along with their associated netmask length. This is provided in the form of (Length, Prefix) tuples, where Length is the number of bits in the netmask and Prefix is the IP address prefix (the network address).
Path Attributes: The Path Attributes provide information specific to this BGP route, including a list of the ASs that this path crosses. More on this shortly.
Withdrawn Routes: Withdrawn Routes are (Length, Prefix) tuples that were previously advertised via NLRI, however are no longer reachable or have been withdrawn from service.

Initially BGP peers exchange their (possibly filtered) full routing tables. After that, updates are sent only when a routing table changes.

BGP Path Attributes

Each advertised BGP route will contain a number of path attributes. An attribute can be mandatory (must be included) or discretionary (may be included). An attribute can also be transitive or non-transitive.

For a transitive attribute, if the router does not support this attribute it should still process the Update and pass the BGP route on to its peers (with the transitive attribute included). For non-transitive attributes that are not supported the router should silently ignore the Update message.

AS Path

When BGP updates pass through an AS, that AS number gets prepended to the update. Thus when a router receives the update, each destination is tagged with all the ASs the update has passed through (in effect, the list represents the path to the destination).

The AS Path attribute is a "well known and mandatory" attribute. It must be present in all BGP route updates and must be recognised by all BGP implementations.

This attribute is central to BGP's loop-free operation. A BGP router will not accept a route that contains its own AS number within the AS Path attribute.

Origin

Another "well known and mandatory" attribute. Its purpose is to indicate the origin of path information. It can have one of three values:

IGP: The network was redistributed from an interior routing protocol in the current AS.
EGP: The network was redistributed from an exterior routing protocol in another AS.
INCOMPLETE: The origin is unknown. One such example is static routes that have been redistributed into BGP.

Next Hop

Another "well known and mandatory" attribute - this attribute provides the IP address of the next hop router for this path. If the advertising router and the receiving router are in different ASs, the Next Hop attribute will specify the IP address of the advertising router.

If the advertising and receiving routers are both within the same AS, the Next Hop is dependent on the route destination. If the destination is in the same AS, Next Hop will specify the IP address of the neighbour which is advertising the route. If the destination is in a different AS the Next Hop will refer to the external peer from which the route was learned.

Administrative Weight

This is an optional attribute originally used by Cisco, but also adopted by other router manufacturers, such as Juniper Networks. It influences path selection when there is more than one path to a destination. It is configurable on a per-neighbour or AS Path basis but has no significance outside that router and is never propagated to other routers.

Local Preference

This is an attribute distributed between routers in the same AS. It is designed to influence the choice of a preferred exit point from the AS. A higher value is preferred - a typical default is 100. The Local Preference is not distributed to EBGP neighbours.

On Cisco routers, this value can be manipulated by Route Maps. It can be applied to routes originating or transiting a given AS.

Metric

The Metric or Multi Exit Discriminator (MED) is an optional attribute. It is advertised to EBGP neighbours with the intent of influencing the choice of path entering the AS from which it was received. It is not propagated to a third AS. Generally, routers only compare the Metrics for a given destination if the updates come from the same AS.

BGP Router ID

This is calculated the same as an OSPF router ID, ie. the highest active IP address on the router. An address assigned to a loopback interface overrides a physical interface address.

How BGP Chooses a Path

BGP applies the following hierarchy of rules:

The path is ignored if the next-hop is unreachable.
The highest Weight is preferred (if in use by this router).
The highest Local Preference is preferred.
Prefer a route that has originated from the router that is advertising it.
Prefer the shortest AS path.
Prefer the lowest Origin code.
Prefer the lowest Metric or MED value.
Prefer an external BGP path to an internal BGP path.
If only internal paths exist and IGP synchronisation is turned off, the path through the closest IGP neighbour is preferred.
Prefer the path through the BGP router with the lowest BGP router ID.

To be continued...

References

RFC4271: A Border Gateway Protocol 4 (BGP-4)

BGP Reports at http://bgp.potaroo.net/

BGP - The Movie (59.5MB MPEG)

BGPlay

BGP: the Border Gateway Protocol Advanced Internet Routing Resources

BGP Looking Glass Servers