Border Gateway Protocol

BGP in the TCP / IP protocol stack :
application	BGP
transport	TCP
Internet	IP ( IPv4 , IPv6 )
Network access	Ethernet	Token bus	Token ring	FDDI	...

The Border Gateway Protocol ( BGP ) is the routing protocol used on the Internet and connects autonomous systems (AS) with one another. These autonomous systems are usually formed by Internet service providers . BGP is generally referred to as the Exterior Gateway Protocol (EGP) and path vector protocol and uses both strategic and technical-metric criteria for routing decisions, whereby in practice mostly business aspects are taken into account. Within autonomous systems are used Interior Gateway Protocols (IGP) such. B. OSPF is used.

Protocol description

BGP is described in RFC 1163 . In the currently used version 4, it is described in RFC 4271 . The BGP routers use TCP port 179.

In 1991, the Border Gateway Protocol (Version 3) MIB was published in RFC 1269 . This MIB enables the management of devices using SNMP , which support the BGP protocol as Autonomous System Routing Protocol .

In February 1998 the BGPv4 was provided with so-called multiprotocol extensions in RFC 2283 . The current version can be found in RFC 4760 . BGPv4 is no longer purely IPv4-specific, but also supports routing with other protocols of the network layer. I.a. MPLS labels can also be exchanged , which was a prerequisite for using BGP / MPLS IP VPNs ( RFC 4364 ).

scope of application

EBGP

BGP, currently the only exterior gateway protocol in use , is a protocol for routing between autonomous systems (AS). This use is called External BGP (EBGP).

IBGP

BGP can also be used within an autonomous system. This is typically done in order to propagate the routes learned by EBGP routers within the own autonomous system. Although this would also be possible with the help of an IGP, these are not designed to transmit the BGP attributes (see below). This use is known as Internal BGP (IBGP). All IBGP routers that exchange routes together use the same AS number of their own AS if no BGP confederations (see below) are used.

Complete meshing

When used within an autonomous system, BGP connections must be set up between all routers of the AS so that a complete meshing is created. If an autonomous system contains n routers, this results in BGP connections. Because of the resulting scaling problems, a so-called route reflector (RR) is used in larger networks . This eliminates the need for a full meshing of the IBGP router; instead, they set up a BGP connection to one or, for redundancy reasons, to several route reflectors. ${\ displaystyle {\ tfrac {n ^ {2} -n} {2}}}$

The reason for the need for complete meshing is that IBGP itself does not pass on BGP information received from neighboring BGP routers within an autonomous system to other IBGP routers (" split horizon principle"). This serves to avoid routing loops.

Route Reflector

In order to solve the problem of the large number of BGP sessions that occur with a complete meshing, one or, for reasons of redundancy, several BGP routers can be configured as route reflectors in an AS . Each EBGP router sends its routes learned via EBGP via IBGP only to a specific router (the route reflector ), which collects them and in turn distributes them via IBGP to the other BGP routers in the AS. Since each BGP router now only needs to maintain a single BGP connection to its route reflector , there are only n connections in total . This topology is for example the German Internet Exchange DE-CIX used to the peering simplifying between networks. All border routers that mediate to the connected networks send their routes to the routing server, i.e. the route reflector , from which all other routers can obtain these routes again. As a result, almost all connected networks a network in a simple manner together are.

A single route reflector represents a single point of failure . Therefore, several of these routers can be interconnected as a cluster to ensure failure safety. The IBGP routers must establish a connection to each of the cluster routers. With n routers and m route reflectors, n · m connections result.

Route reflectors can be routers that are provided in the network specifically for this task or that are located in the data path as normal routers and perform route reflector functionality.

Confederation

An autonomous system (AS) can in turn be subdivided into autonomous systems (Sub-AS) by means of confederation . These sub-AS are given different private AS numbers (ASN), for which the range 64512–65535 (16-bit AS number range) or 4200000000–4294967294 (32-bit AS number range) is reserved and freely available. There is no need to register to use these AS numbers. B. at the RIPE NCC . The AS numbers from this private area are not forwarded to other EBGP routers by EBGP routers with public AS numbers. Different AS numbers are thus used within the AS, but only the external AS number is presented via a public EBGP router. EBGP is used between the Sub-AS to exchange routes. On the one hand, the use of Confederation can simplify the management of large ASs and, on the other hand, the connection complexity can be reduced through the full meshing of all IBGP routers.

EBGP, IBGP, Confederation and Route Reflector

In the graphic, AS100 and AS200 represent public autonomous systems (AS) that exchange routes via EBGP. AS100 is divided into two private, autonomous systems AS65050 and AS65100 through Confederation . The two private AS also exchange their routes via EBGP. A BGP router is configured as a route reflector (RR) within both private AS . All other BGP routers within a private AS exchange their routes with the Route Reflector via IBGP.

Loopback addresses

In contrast to EBGP connections, which usually terminate on physical router interfaces, IBGP connections are defined between router loopback addresses. This is to prevent the IBGP connection from breaking off in the event of deactivation / failure of a physical router interface, although the router could switch it over to an alternative interface with appropriate redundancy provision within the autonomous system. However, since the loopback addresses cannot be propagated as a route without an existing IBGP connection, an underlying Interior Gateway Protocol (IGP) such as B. OSPF required. This means that an IGP router process is also configured on each IBGP router. Since every IBGP router has at least two physical network cards, the IGP will know several possible paths between the loopback addresses. If a physical network interface of an IBGP router fails, an alternative path is propagated via IGP. As long as at least one physical interface can be reached, the loopback address configured on the router can also be reached and the IBGP connection can be rerouted within the AS without interruption.

Without loopback addresses, the IBGP routers would be linked to one another by physical interfaces. If such an interface fails, the connection would be interrupted and a consistent distribution of routes within an autonomous system would no longer be ensured even if the internal network infrastructure is implemented redundantly .

Protocol overview

The direct connections between neighboring routers are specified manually. Routers that want to exchange routing information with one another via BGP first set up a TCP connection, via which the BGP messages are then sent. This connection is called a BGP session (“session”).

BGP protocol

Bit offset	0-15	16-23
0	Marker (16 bytes)
32
64
96
128	Message length	Message Type
	Message

Marker : All bits of the first 16 bytes are set to "1" for reasons of compatibility.
Message Length : Total size of the BGP message
Message Type : Type of BGP message

1 =	Open	RFC 4271 - A Border Gateway Protocol 4 (BGP-4) . July 2006. Section 4.2: OPEN Message Format. (English).
2 =	Update	RFC 4271 July 2006. Section 4.3: UPDATE Message Format. (English).
3 =	Notification	RFC 4271 July 2006. Section 4.5: NOTIFICATION Message Format. (English).
4 =	KeepAlive	RFC 4271 July 2006. Section 4.4: KEEPALIVE Message Format. (English).
5 =	ROUTE REFRESH	E. Chen: RFC 2918 . - Route Refresh Capability for BGP-4 . September 2000. Standard: [BGP4]. (Updated by RFC 7313 - English).

Message : When a route is updated, the routes that have been added or deleted are specified in this area.

Types of BGP messages

BGP uses four different types of messages in the protocol:

OPEN
Is only sent at the beginning of a connection and must be answered with a KEEPALIVE message. The parameters BGP version, AS number, hold timer , BGP identifier and optional parameters are sent with the OPEN message . The route information is then exchanged between the routers.

UPDATE
Notifies a path change. Several paths can be added and several removed at the same time for each UPDATE message. UPDATE messages are at the heart of BGP.

NOTIFICATION Terminates
a connection and reports error or status codes. All paths that were received via this terminated connection must now be deleted. A BGP update would then broadcast that this route is no longer available.

KEEPALIVE Confirms
the OPEN request. To regularly check whether the connected router is still online or whether the connection has been interrupted and the paths via the connected router have thus become invalid. The routers that have just established a BGP session send each other a KEEPALIVE message at regular intervals . This only consists of the message header . The Hold Time attribute of an OPEN message specifies the maximum time in which a BGP router expects a KEEPALIVE message from the BGP partner of the session. If no KEEPALIVE message arrives within the hold time , the BGP session is ended with a NOTIFICATION .

Connection status at BGP

State graph of BGP

The graphic shows the various states of a BGP connection. In practice, it is important to know that no routing entries have yet been exchanged if the status Active is displayed in a router configuration . This status means that an attempt is being made to establish a connection. A functioning connection between the BGP routers does not exist until the status established has been reached.

More detailed description

The core of BGP is the UPDATE message, which BGP routers use to communicate the existence of new routes ( announcement ) or the discontinuation of existing routes ( withdrawal ). The recipient of an UPDATE message decides on the basis of his routing guidelines ("policies") whether he changes his routing (and then has to send UPDATE messages himself ), simply forwards the message (e.g. via IBGP) or simply ignores it .

Attributes

A route in BGP has several attributes. The most important are explained below.

The AS Path describes the autonomous systems via which the specified destination (a CIDR prefix) can be reached. The autonomous systems are identified by their AS number (ASN). No loop may occur in the AS path; However, it is allowed for an AS to register several times in a row and thus artificially lengthen the AS path in order to make the route available but unattractive ( AS Path Prepending ).
The IGP metric describes the costs through the own network to reach the exit point in the next AS on the AS path.
The Multi-Exit Discriminator (MED) is used to prioritize different parallel connections to the same neighboring AS; the smallest value is preferred. This attribute is used between EBGP peers.
Communities are routing tags that can be used to mark routing changes (UPDATE messages) or transmitted prefixes to other BGP peers. A BGP community is a 32-bit value that can be used by other BGP routers as a filter criterion. In addition to standard communities, so-called extended communities12345:12345 can be used freely in the notation or as a decimal number.
Local Preference defines a preferred path from several paths within the same AS with the higher value in each case. If there are several routes with AS paths of the same length for the same target prefix, then certain routes can be preferred using Local Preference ; see. Section "Path Selection".
Next hop is the specification of the IP address of the next hop router with a prefix. The next-hop router is the gateway router that connects its own AS with the next AS on the AS path.
Weight is a local attribute (proprietary); see. Section "Path Selection".
Origin indicates the source of a prefix: IGP , EGP or Incomplete .

Path selection

Very often it happens that a router is informed of different routes to the same destination. The route selection that it ultimately decides on is known as the BGP Path Selection Process . The network operator can control and influence the path selection in the router by selecting suitable rules in the router.

The BGP Path Selection Process basically follows the following rules:

The path with the largest value for Weight is preferred (Cisco proprietary ).

If the value for Weight is the same, the value with the greatest local preference is preferred.

If the values for Local Preference are the same, preference is given to the path generated by BGP on this router.

If no path was generated on this router, prefer the path with the shortest AS_PATH attribute.

If all AS_PATH attributes are the same length, prefer the lowest Origin type ( IGP is lower than EGP , EGP is lower than Incomplete )

If all Origin types are the same, prefer the path with the lowest MED attribute.

If all paths have the same value for MED, prefer external paths over internal paths.

If all paths still have the same priority, give preference to the path to the closest IGP neighbor.

If all paths are the same, prefer the path with the lowest IP address of the BGP peer in relation to the router ID.

Interaction between IBGP and IGP

IBGP and IGP (the intradomain routing protocol, e.g. OSPF , IS-IS , EIGRP / IGRP , RIP , for example) allow a router to forward a packet to another network to which it has no direct connection ), which is required to forward packets to the corresponding gateway router. The BGP attribute Next Hop is used for this .

Example: A router R ₁ in AS1 is to 10.1.2.3forward a packet to the destination address . He previously learned from an IBGP update message that the target network can be 10.0.0.0/8reached via the neighboring AS 4711. However, R _{1 has} no direct connection to AS4711; this connection only exists on another router R ₂ (gateway router). However, through the BGP attribute Next Hop , R ₁ knows the IP address of R ₂ . Only on the basis of the information from the IGP does R ₁ know the shortest path within AS1 to R ₂ and thus knows to which neighbor router R _x it has to send the packet so that it arrives at the gateway router R ₂ , which ultimately receives it AS4711 can forward.

The provision of availability information for the IBGP protocol by an IGP protocol is also necessary to establish IBGP sessions between IBGP routers that are not immediately adjacent or to BGP route reflectors.

Special features of BGP

Routing loops

BGP is a path vector protocol . Its functionality is heavily dependent on distance vector algorithms and protocols such as B. Routing Information Protocol (RIP) based, but the problem of routing loops occurring there is effectively prevented. A routing loop occurs when an IP packet passes the same AS several times on its way through the Internet. When sending routing information (UPDATE), a BGP router not only informs the communication partner that it can reach a certain section of the Internet, but also the complete list of all autonomous systems (AS-Path), the IP packets up to must pass this section (his own AS comes first, the target AS comes last). If the communication partner now notices that the AS to which it belongs is already in this list, it discards the message and thus avoids creating a routing loop.

Route aggregation

With BGP, each router can combine common routes, in contrast to e.g. B. with OSPF, on whose routers a routing summary can only be carried out on the area border routers.

Link state

Different link speeds are not taken into account. The routes are mainly selected according to their length ( AS Path ) and strategic aspects.

Hop length

The number of (BGP) routers ("hops " ) is not taken into account by BGP as a decision criterion when selecting the best route to the destination - only the number of autonomous systems is important (apart from the IGP metric attribute ).

Problems with BGP

General

Due to its principle, BGP has a number of weaknesses that can arise in a minimal configuration. However, the weaknesses are usually compensated by the fact that the prioritization of paths is subject to routing policies that are controlled by the respective network operator.

Routing table growth

Growth of the BGP routing table on the Internet for IPv4

Since each BGP router has route information from others, in particular from neighboring BGP routers, each BGP router builds a database for the routes to all accessible autonomous systems. The size of the table with the route information was around 650,000 entries in around 56,000 autonomous systems in December 2016.

IPv4	Late 2005	April 2011	April 2012	May 2014	June 2015	December 2016
Routing entries	170,000	360,000	411,000	500,000	557.973	646.157
Autonomous systems	26,000	37,000	40,900	47.010	50,921	56,158

Route aggregation can counteract the growth of the routing tables to a certain extent.

Growth of the BGP routing table on the Internet for IPv6

When developing IPv6 , the problem of the growth of routing tables in IPv4 was also considered. When using IPv6, significantly fewer routing entries are to be expected. Not all Internet providers currently use IPv6 and therefore the following statistics cannot be compared directly with the table above about the IPv4 routing entries.

IPv6	April 2012	June 2015	December 2016
Routing entries	8,500	22,014	34,789
Autonomous systems	5,100	8,251	12,666

Load sharing

BGP does not come with any load balancing procedures by default . Only one possible route is selected at a time. However, there are proprietary extensions that allow configuration for load balancing. In contrast, these extensions enable B. OSPF is a load distribution on differently weighted connections.

safety

In its basic configuration, a BGP router is susceptible to spoofing attacks that can be used by attackers to manipulate routes. By using authentication with a password that is individually defined between the BGP peers (based on MD5 hashes), the data exchange between the BGP routers can be secured. Although this makes spoofing attacks much more difficult, it is particularly dependent on the security of MD5, which is no longer considered secure by crypto experts.

Furthermore, due to the point-to-point character of BGP router relationships, the permitted BGP peers can be restricted to the permitted partners using packet filter lists.

In addition, various other security mechanisms for BGP have been and are being proposed; However, even if the proposed methods were used across the board, it would be almost impossible to completely prevent attacks that intend to divert traffic flows.

Route Flap

Route flaps are caused by routes that fluctuate back and forth over longer periods of time, are advertised and withdrawn again. As a countermeasure, modern BGP implementations offer a method called Route Flap Damping , which, however, under certain conditions can lead to undesirably long delays in the forwarding of route changes.

Update bursts

Update bursts are large amounts of UPDATE messages that occur suddenly, often to destinations that are not closely correlated with one another.

Special events

YouTube blockage

In February 2008, a court order forced Pakistan Telecom to block YouTube traffic in Pakistan. Technically, this was implemented by feeding a wrong route to the YouTube network in IBGP. However, due to a configuration error, this wrong route was not only used in Pakistan, but also erroneously distributed to other Internet providers via EBGP, which led to YouTube being blocked for several hours, especially in Asia.

Misconfigured BGP router

In February 2009, AS paths that were too long were forwarded to public BGP routers via a Czech BGP router. Some BGP routers had problems processing these long AS paths, which resulted in impaired Internet traffic. Administrators can counteract such a problem through a configuration in which the maximum length of the accepted AS path is restricted.

Revolution in Egypt 2011

During the revolution in Egypt in January 2011, around 3,500 routes of all Egyptian Internet providers were withdrawn via BGP in a few minutes, which disconnected almost all of Egypt from the Internet. Cellular services and social networks were also no longer accessible. This appears to be the first case in the history of the Internet in which an entire country was isolated from the Internet for political reasons.

Software error

The BGP Path Attribute can have the value 255. This is available for developments (development, cf. RFC2042). As early as 2010, an experiment with this flag led to crashes in some routers. In a new attempt at the end of 2018, incorrectly implemented routers were found again.

Free software implementations

Bird Internet routing daemon
GNU Zebra (development discontinued)
Quagga (further development of Zebra)
OpenBGPD
eXtensible Open Router Platform (XORP)

Norms and standards

Y. Rekhter, T. Li, S. Hares: RFC 4271 . - A Border Gateway Protocol 4 . [Errata: RFC 4271 ]. July 2006. Standard: [BGP4]. (Replaces RFC 1771 - Updated by RFC 6286 - English).
T. Bates, E. Chen, R. Chandra: RFC 4456 . - BGP Route Reflection: An Alternative to Full Mesh Internal BGP . [Errata: RFC 4456 ]. April 2006. Standard: [IBGP]. (Replaces RFC 2796 - Updated by RFC 7606 - English).
S. Hares, D. Hares: RFC 4275 . - BGP-4 MIB Implementation Survey . [Errata: RFC 4275 ]. January 2006. (English).
P. Traina, D. McPherson, J. Scudder: RFC 5065 . - Autonomous System Confederations for BGP . [Errata: RFC 5065 ]. August 2007. Standard: [BGP]. (Replaces RFC 3065 - English).
Q. Vohra, E. Chen: RFC 4893 . - BGP Support for Four-octet AS Number Space . May 2007. (English).
C. Villamizar, R. Chandra, R. Govindan: RFC 2439 . - BGP Route Flap Damping . [Errata: RFC 2439 ]. November 1998. (English).
T. Bates, R. Chandra, D. Katz, Y. Rekhter: RFC 4760 . - Multiprotocol Extensions for BGP-4 . [Errata: RFC 4760 ]. January 2007. Standard: [BGP4]. (Replaces RFC 2858 - Updated by RFC 7606 - English).
E. Chen, J. Scudder, P. Mohapatra, K. Patel: RFC 7606 . - Revised Error Handling for BGP UPDATE Messages . August 2015. (English).

Web links

BGPlay - A Java program for graphically displaying BGP routing activities
BGP Toolkit Analysis of Autonomous Systems

Individual evidence

↑ Introducing Route Reflectors. Cisco, accessed May 18, 2017 .

^ Autonomous System (AS) Numbers. IANA, accessed May 1, 2017 .

↑ Cisco reference on BGP Confederation (English)

↑ Cisco reference to AS Path Prepending ( Memento of the original from April 16, 2012 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
↑ Cisco reference on BGP Path Selection
↑ cidr-report.org - CIDR Report (English) accessed on June 21, 2015
↑ RIPE NCC - Routing IPv6 in 2011
↑ IPv6 BGP Operational Report from Hurricane Electric (accessed June 21, 2015)
↑ IP Routing: BGP Best Path Selection Algorithm. on: cisco.com
↑ ^a ^b Kevin Butler, Toni Farley, Patrick McDaniel, and Jennifer Rexford: A survey of BGP security issues and solutions (PDF; 1.5 MB) . In: Proceedings of the IEEE, January 2010
^ Barry Raveendran Greene: BGPv4 Security Risk Assessment. (PDF; 159 kB) on: cymru.com
↑ List of scientific publications on the subject of BGP safety
↑ Routers don't lie - what if they do? on: heise security online August 27, 2008.
↑ Sharon Goldberg, Michael Schapira, Peter Hummon, and Jennifer Rexford: How secure are secure interdomain routing protocols? (PDF; 384 kB) In: Proceedings of the ACM SIGCOMM conference, August 2010.
↑ C. Labovitz, G. Malan, F. Jahanian: Internet routing instability. IEEE / ACM Transactions on Networking, 6 (5) 1998, pp. 515-528.
↑ Zhenhai Duan, Jaideep Chandrashekar, Jeffrey Krasky, Kuai Xu, Zhi-Li Zhang: Damping BGP Route Flaps . Proceedings of the 23rd IEEE International Performance Computing and Communications Conference (IPCCC), 2004.
↑ Ke Zhang, Amy Yen, Xiaoliang Zhao, Dan Massey, S. Felix Wu, Lixia Zhang: On Detection of Anomalous Routing Dynamics in BGP . In: LNCS NETWORKING 2004. ISBN 3-540-21959-5 .
↑ heise.de - Pakistan blocks YouTube
↑ Renesys: Pakistan hijacks Youtube
↑ heise.de - incorrectly configured router
↑ Renesys: Reckless Driving on the Internet and Longer is not Always Better
↑ heise.de - Egypt is offline
↑ Faulty routers stop BGP experiment

[1] Introducing Route Reflectors. Cisco, accessed May 18, 2017 .

[2] Autonomous System (AS) Numbers. IANA, accessed May 1, 2017 .

[3] Cisco reference on BGP Confederation (English)