One Of The Greatest Protocols — and One of The Greatest Weaknesses — of the Internet … Meet The…
One Of The Greatest Protocols — and One of The Greatest Weaknesses — of the Internet … Meet The Mighty BGP
So the Internet isn’t the large-scale distributed network that DARPA tried to create, and which could withstand a nuclear strike on any part of it. At its core is a centralised infrastructure of routing devices and of centralised Internet services. The protocols its uses are basically just the ones that were drafted when we connected to mainframe computers from dumb terminals. Overall, though, a single glitch in its core infrastructure can bring the whole thing crashing to the floor. And then if you can’t get connected to the network, you often will struggle to fix it. A bit like trying to fix your car, when you have locked yourself out, and don’t have the key to get in.
As BGP still provides a good part of the core of the Internet, any problems with it can cause large scale outages. Recently Facebook took themselves off the Internet due to a BGP configuration errors, and there have been multiple times when Internet traffic has been “tricked” to take routes through countries which do not have a good track record for privacy.
BGP does the core of routing on the Internet, works by defining autonomous systems (AS). The ASs are identified with an ASN (Autonomous System Number) and keep routing tables which allows the ASs to pass data packets between themselves, and thus route between them. Thus the Facebook AS can advertise to other AS’s that it exists and that packets can be routed to them. When the Facebook outage happened, the Facebook AS failed to advertise its presence. Each AS then defines the network ranges that they can reach. Facebook’s ASN is AS32935 and covers around 270,000 IP address ranges [here].
What is BGP?
The two main interdomain routing protocols in recent history are EGP (Exterior Gateway Protocol) and BGP (Border Gateway Protocol). EGP suffers from several limitations, and its principal one is that it treats the Internet as a tree-like structure, as illustrated in Figure 1. This assumes that the structure of the Internet is made up of parents and children, with a single backbone. A more typical topology for the Internet is illustrated in Figure 2. BGP is now one of the most widely accepted exterior routing protocol, and has largely replaced EGP.
BGP is an improvement on EGP (the fourth version of BGP is known as BGP-4), and is defined in RFC1772. Unfortunately it is more complex than EGP, but not as complex as OSPF. BGP assumes that the Internet is made up of an arbitrarily interconnected set of nodes. It then assumes the Internet connects to a number of AANs (autonomously attached networks), as illustrated in Figure 3, which create boundaries around organizations, Internet service providers, and so on. It then assumes that, once they are in the AAN, the packets will be properly routed.
Most routing algorithms try to find the quickest way through the network, whereas BGP tries to find any path through the network. Thus, the main goal is reachability instead of the number of hops to the destination. So finding a path which is nearly optimal is a good achievement. The AAN administrator selects at least one node to be a BGP speaker and also one or more border gateways. These gateways simply route the packet into and out of the AAN. The border gateways are the routers through which packets reach the AAN.
The speaker on the AAN broadcasts its reachability information to all the networks within its AAN. This information states only whether a destination AAN can be reached; it does not describe any other metrics. An important point is that BGP is not a distance-vector or link state protocol because it transmits complete routing information instead of partial information.
The BGP update packet also contains information on routes which cannot be reached (withdrawn routes), and the content of the BGP-4 update packet is:
- Unfeasible routes length (2 bytes).
- Withdrawn routes (variable length).
- Total path attribute length (2 bytes).
- Path attributes (variable length).
- Network layer reachability information (variable length). This can contain extra information, such as ‘use AAN 1 in preference to AAN 2’.
Routers within AS’s share similar routing policies, and thus operate as a single administrative unit. All the routers outside the AS treat the AS as a single unit. The AS identification number is assigned by the Internet Assigned Numbers Authority (IANA) in the range of 1 to 65,535, where 64,512 to 65,535 are reserved for private use. The private numbers are only used within private domain, and must be translated to registered numbers when leaving the domain.
BGP and routing loops
BGP uses TCP segments on port 179 to send routing information (whereas RIP uses port 520). BGP overcomes routing loops by constructing a graph of autonomous systems, based on the information provided by exchanging information between neighbors. It can thus build up a wider picture of the entire interconnected ASs. A keep-alive message is send between neighbours, which allows the graph to be kept up-to-date.
Single-homed systems
ASs which have only one exit point are defined as single-homed systems, and are often referred to as stub networks. These stubs can use a default route to handle all the network traffic destined for non-local networks.
There are three methods that an AS can use so that the outside world can learn the addresses within the AS:
- Static configuration. For this, an Internet access provider could list the customer’s networks as static entries within its own router. These would then be advertised to other routers connected to its Internet core. This approach could also be used with a CIDR approach which aggregates the routes.
- Use an Interior Gateway Protocol (IGP) on the link. For this, an Internet access provider could run a IGP on the single connection, this can then be used to advertise the connected networks. This method allows for a more dynamic approach, than static configuration. A typical IGP is OSPF.
- Use an Exterior Gateway Protocol (EGP) on the link. An EGP can be used to advertise the networks. If the connected AS does not have a registered AS, the Internet access provider can assign it from a private pool of AS numbers (64,512 to 65,535), and then strip off the numbers when advertising the AS to the core of the Internet.
Multihomed system
A multi-homed system has more than one exit point from the AS. As it has more than one exit point, it could support the routing of data across the exit points. A system which does not support the routing of traffic through the AS is named a non-transit AS. Non-transit ASs thus will only advertise its own routes to the Internet access providers, as it does not want any routing through it. One Internet provider could force traffic through the AS if it knows that routing through the AS is possible. To overcome this, the AS would setup filtering to stop any of this routed traffic.
Multi-homed transit systems have more than one connection to an Internet access provider, and also allow traffic to be routed through it. It will route this traffic by running BGP internally so that multiple border routers in the same AS can share BGP information. Along with this, routers can forward BGP information from one border router to another. BGP running inside the AS is named Internet BGP (IBGP), while it is known as External BGP (EBGP) if it is running outside AS’s. The routers which define the boundary between the AS and the Internet access provider is known as border routers, while routers running internal BGP are known as transit routers.
BGP specification
Border Gateway Protocol (BGP) is an inter-Autonomous System routing protocol (exterior routing protocol), which builds on EGP. The main function of a BGP-based system is to communicate network reachability information with other BGP systems. Initially two systems exchange messages to open and confirm the connection parameters, and then transmit the entire BGP routing table. After this, incremental updates are sent as the routing tables change.
Each message has a fixed-size header and may or may not be followed a data portion. The fields are:
- Marker. Contains a value that the receiver of the message can predict. It can be used to detect a loss of synchronization between a pair of BGP peers, and to authenticate incoming BGP messages. 16 bytes.
- Length. Indicates the total length, in bytes, of the message, including the header. It must always be greater than 18 and no greater than 4096. 2 bytes.
- Type. Indicates the type of message, such as 1 — OPEN, 2 — UPDATE, 3 — NOTIFICATION and 4 — KEEPALIVE.
OPEN message
The OPEN message is the first message sent after a connection has been made. A KEEPALIVE message is sent back confirming the OPEN message. After this the UPDATE, KEEPALIVE, and NOTIFICATION messages can be exchanged.
Figure 4 shows the extra information added to the fixed-size BGP header. It has the following fields:
- Version. Indicates the protocol version number of the message. Typical values are 2, 3 or 4. 1 byte.
- My Autonomous System. Identifies the sender’s Autonomous System number. 2 bytes.
- Hold Time. Indicates the maximum number of seconds that can elapse between the receipt of successive KEEPALIVE and/or UPDATE and/or NOTIFICATION messages. 2 bytes.
- Authentication Code. Indicates the authentication mechanism being used. This should define the form and meaning of the Authentication Data and the algorithm for computing values of Marker fields.
- Authentication Data. The form and meaning of this field is a variable-length field which depends on the Authentication Code.
BGP configuration
BGP configuration commands are similar to those used for RIP (Routing Internet Protocol). To configure the router to support BGP the following commands is used:
RouterA # config t
RouterA(config)# router bgp AS-number
With IGP’s, such as RIP, the network command defined the networks on which routing table update are sent. For BGP a different approach is used to define the relationship between networks. This is [here]:
RouterA # config t
RouterA(config) # router bgp AS-number
Router(config-router)# network network-number [mask network-mask]
where the network command defines where to advertise the locally learnt networks. These networks could have been learnt from other protocols, such as RIP. An optional mask can be used with the network command to specify individual subnets. With the BGP protocol neiphbors must establish a relationship, for this the following is used:
RouterA # config t
RouterA(config) #router bgp AS-number
Router(config-router)#network network-number [mask network-mask]
Router(config-router)# neighbor ip-address remote-as AS-number
which defines the IP address of a connected BGP-based router, along with its AS number.
Conclusions
At its core, the Internet is not a decentralised infrastructure. It is fragile and open to human error and adversarial attacks. Too much of our time is spent on making our services work and very little on making them robust. We need to spend more time looking at scenarios and how to mitigate them. Previously it was Facebook taking themselves offline, the next time it could be a nation-state bring down a whole country … and that it is likely to have a devastating effect.
Now … I have setup more Cisco challenges for BGP for you, so go and learn more about BGP configuration here: