The Border Gateway Protocol (BGP) is the core routing protocol of the Internet. It works by maintaining a table of IP networks or 'prefixes' which designate network reachability among autonomous systems (AS). It is described as a path vector protocol. BGP does not use traditional IGP metrics, but makes routing decisions based on path, network policies and/or rulesets. In computing and telecommunications, the transport layer is the second highest layer in the four and five layer TCP/IP reference models, where it responds to service requests from the application layer and issues service requests to the Internet layer. ... The Transmission Control Protocol (TCP) is one of the core protocols of the Internet protocol suite. ... User Datagram Protocol (UDP) is one of the core protocols of the Internet protocol suite. ... The Datagram Congestion Control Protocol (DCCP) is a message-oriented transport layer protocol that is currently under development in the IETF. Applications that might make use of DCCP include those with timingconstraints on the delivery of data such that reliable in-order delivery, when combined with congestion control, is likely... In the field of computer networking, the IETF Signaling Transport (SIGTRAN) working group defined the Stream Control Transmission Protocol (SCTP) as a transport layer protocol in 2000. ... The Resource ReSerVation Protocol (RSVP), described in RFC 2205, is a Transport layer protocol designed to reserve resources across a network for an integrated services Internet. ... The network layer is third layer out of seven in OSI model and it is the third layer out of five in TCP/IP model. ... The Internet Protocol (IP) is a data-oriented protocol used for communicating data across a packet-switched internetwork. ... Internet Protocol version 4 is the fourth iteration of the Internet Protocol (IP) and it is the first version of the protocol to be widely deployed. ... Internet Protocol version 6 (IPv6) is a network layer protocol for packet-switched internetworks. ... The Open Shortest Path First (OSPF) protocol is a hierarchical interior gateway protocol (IGP) for routing in Internet Protocol, using a link-state in the individual areas that make up the hierarchy. ... Is Is is Yeah Yeah Yeahs third EP, to be released on July 24, 2007. ... IPsec (IP security) is a suite of protocols for securing Internet Protocol (IP) communications by authenticating and/or encrypting each IP packet in a data stream. ... In computer networking, the Address Resolution Protocol (ARP) is the standard method for finding a hosts hardware address when only its network layer address is known. ... Reverse Address Resolution Protocol (RARP) is a network layer protocol used to obtain an IP address for a given hardware address (such as an Ethernet address). ... This article is chiefly about the Routing Information Protocol (RIP) for the Internet Protocol, but also discusses some other routing information protocols. ... The Internet Control Message Protocol (ICMP) is one of the core protocols of the Internet protocol suite. ... The ICMP for IPv6 (Internet Control Message Protocol Version 6) is an integral part of the IPv6 architecture and must be completely supported by all IPv6 implementations. ... The Internet Group Management Protocol (IGMP) is a communications protocol used to manage the membership of Internet Protocol multicast groups. ... This article does not cite any references or sources. ... IEEE 802. ... The IEEE 802. ... Official Wi-Fi logo Wi-Fi (pronounced wye-fye, IPA: ) is a wireless technology brand owned by the Wi-Fi Alliance intended to improve the interoperability of wireless local area network products based on the IEEE 802. ... Official WiMax logo WiMAX, the Worldwide Interoperability for Microwave Access, is a telecommunications technology aimed at providing wireless data over long distances in a variety of ways, from point-to-point links to full mobile cellular type access. ... Asynchronous Transfer Mode (ATM) is a cell relay, packet switching network and data link layer protocol which encodes data traffic into small (53 bytes; 48 bytes of data and 5 bytes of header information) fixed-sized cells. ... Dynamic synchronous Transfer Mode , or DTM for short, is a network protocol. ... Token-Ring local area network (LAN) technology was developed and promoted by IBM in the early 1980s and standardised as IEEE 802. ... Ethernet is a large, diverse family of frame-based computer networking technologies that operate at many speeds for local area networks (LANs). ... In computer networking, fiber-distributed data interface (FDDI) is a standard for data transmission in a local area network that can extend in range up to 200 km (124 miles). ... In the context of computer networking, frame relay consists of an efficient data transmission technique used to send digital information quickly and cheaply in a relay of frames to one or many destinations from one or many end-points. ... General Packet Radio Service (GPRS) is a Mobile Data Service available to users of Global System for Mobile Communications (GSM) and IS-136 mobile phones. ... Evolution-Data Optimized or Evolution-Data only, abbreviated as EV-DO or EVDO and often EV, is one telecommunications standard for the wireless transmission of data through radio signals, typically for broadband Internet access. ... High-Speed Packet Access (HSPA) is a collection of mobile telephony protocols that extend and improve the performance of existing UMTS protocols. ... High-Level Data Link Control (HDLC) is a bit-oriented synchronous data link layer protocol developed by the International Organization for Standardization (ISO). ... In computing, the Point-to-Point Protocol, or PPP, is commonly used to establish a direct connection between two nodes. ... The Point-to-Point Tunneling Protocol (PPTP) is a method for implementing virtual private networks. ... In computer networking, the Layer 2 Tunneling Protocol (L2TP) is a tunneling protocol used to support virtual private networks (VPNs). ... ISDN redirects here. ... ARCNET (also CamelCased as ARCnet, an acronym from Attached Resource Computer NETwork) is a local area network (LAN) protocol, similar in purpose to Ethernet or Token Ring. ... This article does not cite any references or sources. ... IEEE photograph of a diagram with the original terms for describing Ethernet drawn by Robert M. Metcalfe around 1976. ... For other uses, see Modem (disambiguation). ... For other uses, see Power band. ... It has been suggested that this article be split into articles entitled Synchronous optical networking, SONET and Synchronous digital hierarchy. ... There are very few or no other articles that link to this one. ... Optical fibers An optical fiber (or fibre) is a glass or plastic fiber designed to guide light along its length. ... Coaxial Cable For the weapon, see coaxial weapon. ... 25 Pair Color Code Chart 10BASE-T UTP Cable Twisted pair cabling is a common form of wiring in which two conductors are wound around each other for the purposes of cancelling out electromagnetic interference known as crosstalk. ... This article is about routing (or routeing) in computer networks. ... In the Internet, an autonomous system (AS) is a collection of IP networks and routers under the control of one entity (or sometimes more) that presents a common routing policy to the Internet. ... A path vector protocol is a computer network routing protocol in which it maintains the path that update information takes as it diffuses through the network. ... A set of routing protocols that are used within an autonomous system are referred to as interior gateway protocols (IGP). ...

Since 1994, version four of the protocol has been in use on the Internet. All previous versions are now obsolete. The major enhancement in version 4 was support of Classless Inter-Domain Routing and use of route aggregation to decrease the size of routing tables. From January 2006, version 4 is codified in RFC 4271, which went through well over 20 drafts from the earlier RFC 1771 version 4. The RFC 4271 version corrected a number of errors, clarified ambiguities, and also brought the RFC much closer to industry practices. Warning! This Article contains disinformation. ... Route aggregration is the effort to route smaller prefixes via an aggregated larger prefix (supernetting). ... In computer networking a routing table is an electronic table (file) or database type object that is stored in a router or a networked computer. ...

BGP was created to replace the EGP routing protocol to allow fully decentralized routing in order to allow the removal of the NSFNet Internet backbone network. This allowed the Internet to become a truly decentralized system. The Exterior Gateway Protocol (EGP) is a routing protocol for the Internet originally specified in 1982 by Eric C. Rosen of Bolt, Beranek and Newman, and David L. Mills. ... National Science Foundation Network (NSFNet) was a major part of early 1990s Internet backbone. ... Each line is drawn between two nodes, representing two IP addresses. ...

Very large private IP networks can also make use of BGP. An example would be the joining of a number of large Open Shortest Path First (OSPF) networks where OSPF by itself would not scale to size. Another reason to use BGP would be multihoming a network for better redundancy either to a multiple access points of a single ISP (RFC 1998) or to multiple ISPs. The Internet Protocol (IP) is a data-oriented protocol used for communicating data across a packet-switched internetwork. ... The Open Shortest Path First (OSPF) protocol is a hierarchical interior gateway protocol (IGP) for routing in Internet Protocol, using a link-state in the individual areas that make up the hierarchy. ... Multihoming is a technique to increase the reliability of the Internet connection for an IP network. ...

Most Internet users do not use BGP directly. However, since most Internet service providers must use BGP to establish routing between one another (especially if they are multihomed), it is one of the most important protocols of the Internet. Compare this with Signalling System 7 (SS7), which is the inter-provider core call setup protocol on the PSTN. “ISP” redirects here. ... Multihoming is a technique to increase the reliability of the Internet connection for an IP network. ... Signalling System #7 (SS7) is a set of telephony signalling protocols which are used to set up the vast majority of the worlds PSTN telephone calls. ... The public switched telephone network (PSTN) is the concatenation of the worlds public circuit-switched telephone networks, in much the same way that the Internet is the concatenation of the worlds public IP-based packet-switched networks. ...

BGP operation

BGP neighbors, or peers, are established by manual configuration between routers to create a TCP session on port 179. A BGP speaker will periodically send 19-byte keep-alive messages to maintain the connection (every 60 seconds by default). Among routing protocols, BGP is unique in using TCP as its transport protocol. This article is about a computer networking device. ... The Transmission Control Protocol (TCP) is one of the core protocols of the Internet protocol suite. ... It has been suggested that this article or section be merged into Computer port (software). ...

When BGP is running inside an autonomous system (AS), it is referred to as Internal BGP (IBGP Interior Border Gateway Protocol). When BGP runs between ASs, it is called External BGP (EBGP Exterior Border Gateway Protocol). Routers that sit on the boundary of one AS, and exchange information with another AS, are called border or edge routers. In the Cisco operating system, IBGP routes have an administrative distance of 200, which is less preferred than either external BGP or any interior routing protocol. Other router implementations also prefer eBGP to IGPs, and IGPs to iBGP. In the Internet, an autonomous system (AS) is a collection of IP networks and routers under the control of one entity (or sometimes more) that presents a common routing policy to the Internet. ... Administrative distance is the feature used by routers to select the best path when there are two or more different routes to the same destination from two different routing protocols. ...

Optional Extensions negotiated at Connection Setup

During the OPEN handshake, BGP speakers can negotiate^[1] optional capabilities of the session, including multiprotocol extensions and various recovery modes. If the multiprotocol extensions to BGP ^[2] are negotiated at the time of creation, the BGP speaker can prefix the Network Layer Reachability Information (NLRI) it advertises with an address family prefix. These families include the default IPv4, but also IPv6, IPv4 and IPv6 Virtual Private Networks, and multicast BGP. Increasingly, BGP is used as a generalized signaling protocol to carry information about routes that may not be part of the global Internet, such as VPNs ^[3].

Finite state machine

BGP state machine

In order to make decisions in its operations with other BGP peers, a BGP peer uses a simple finite state machine (FSM) that consists of six states: Idle, Connect, Active, OpenSent, OpenConfirm, and Established. For each peer-to-peer session, a BGP implementation maintains a state variable that tracks which of these six states the session is in. The BGP protocol defines the messages that each peer should exchange in order to change the session from one state to another. The first mode is the “Idle” mode. In this mode BGP initalizes all resources, refuses all inbound BGP connection attempts, and initiates a TCP connection to the peer. The second state is “Connect”. In this state the router waits for the TCP connection to complete, transitioning to the "OpenSent" state if successful. If not, it resets the ConnectRetry timer and transitions to the "Active" state upon expiration. In the "Active" state, the router resets the ConnectRetry timer to zero, and returns to the "Connect" state. After "OpenSent," the router sends an Open message, and waits for one in return. Keepalive messages are exchanged next, and upon successful receipt, the router is placed in the “Established” state. Once established the router can now send/receive Keepalive, Update, and Notification messages to/from its peer. Fig. ...

Idle State:

o Initializes resources for the BGP process. o Tries to establish a TCP connection with its configured BGP peer. o Listen for a TCP connection from its peer. If an error occurs at any state of the FSM process, the BGP session is terminated immediately, and returned to the Idle State. Some of the reasons why a router does not progress from from the Idle state are:

 * TCP port 179 is not open. * A random port over TCP port greater than 1023 is not open. * Peer address configured incorrectly on either router. * AS number configured incorrectly on either router Connect State. 

Connect State

o Wait for successful TCP negotiation with peer. o BGP does not spend much time in this state if the TCP session has been successfully established. o Sends OPEN message to peer. o If an error occurs, BGP moves to the ACTIVE state. Some reasons for the error are:

 * TCP port 179 is not open. * A random port over TCP port greater than 1023 is not open. * Peer address configured incorrectly on either router. * AS number configured incorrectly on either router. 

Active State

o If the router was unable to establish a successful TCP session, then it ends up in the ACTIVE state. o The router will try to restart another TCP session with the peer and if successful, then it will send an OPEN message to the peer. o If it is unsuccessful again, the FSM is reset to the IDLE state. o If you see a router cycling between the IDLE and the ACTIVE state, here are some of the reasons:

 * TCP port 179 is not open. * A random port over TCP port greater than 1023 is not open. * BGP configuration error. * Network congestion. * Flapping network interface. 

OpenSent State

o The router listens for an OPEN message from its peer. o Once the message has been received, the router checks the validity of the OPEN message. o If there is an error it is because one of the fields in the OPEN message don’t match between the peers, e.g. BGP version mismatch, MD5 password mismatch, the peering router expects a different My AS. The router will then send a NOTIFICATION message to the peer indicating why the error occurred. o If there is no error, a KEEPALIVE message is sent.

OpenConfirm State

o The peer is listening for a KEEPALIVE message from its peer. o If a message is received, then BGP transitions to the next state. o If no KEEPALIVE message is received, the router transitions back to the IDLE state.

Established State

o In this state, the peers send UPDATE messages to exchange information about each route being advertised to the BGP peer. o If there is any error in the UPDATE message then a NOTIFICATION message is sent to the peer, and BGP transitions back to the IDLE state

The following shows a debug on 2 Routers, showing the various states it transitions before it establishes a peer relationship and exchange routes.

BGP FSM starts at the IDLE state and then transitions to the OPEN state once the TCP negotiation has been sent to Router2

 Sep 24 00:32:10.703 UTC: BGP: 12.144.8.93 went from Idle to Active Sep 24 00:32:10.703 UTC: BGP: 12.144.8.93 open active, delay 16818ms Sep 24 00:32:11.495 UTC: BGP: Import timer expired. Walking from 1 to 1 Sep 24 00:32:27.275 UTC: BGP: 12.144.8.93 passive open 

BGP transitions to IDLE state as it has not heard a TCP negotiation from Router2 as yet

 Sep 24 00:32:27.275 UTC: BGP: 12.144.8.93 went from Active to Idle 

BGP transitions to the Connect state again, as it sends out another TCP negotation

 Sep 24 00:32:27.275 UTC: BGP: 12.144.8.93 went from Idle to Connect 

Once it receives a TCP negotiation from Router2

 Sep 24 00:32:27.279 UTC: BGP: 12.144.8.93 rcv message type 1, length (excl. header) 26 

Router1 has received an OPEN message from Router2

 Sep 24 00:32:27.279 UTC: BGP: 12.144.8.93 rcv OPEN, version 4 

Router1 has sent an OPEN message to Router2 and transitions to the next state

 Sep 24 00:32:27.279 UTC: BGP: 12.144.8.93 went from Connect to OpenSent Sep 24 00:32:27.279 UTC: BGP: 12.144.8.93 sending OPEN, version 4, my as: 21994 

Router1 examines the OPEN message received from Router2

 Sep 24 00:32:27.279 UTC: BGP: 12.144.8.93 rcv OPEN w/ OPTION parameter len: 16 Sep 24 00:32:27.279 UTC: BGP: 12.144.8.93 rcvd OPEN w/ optional parameter type 2 (Capability) len 6 Sep 24 00:32:27.279 UTC: BGP: 12.144.8.93 OPEN has CAPABILITY code: 1, length 4 Sep 24 00:32:27.279 UTC: BGP: 12.144.8.93 OPEN has MP_EXT CAP for afi/safi: 1/1 Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 rcvd OPEN w/ optional parameter type 2 (Capability) len 2 Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 OPEN has CAPABILITY code: 128, length 0 Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 OPEN has ROUTE-REFRESH capability(old) for all address-families Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 rcvd OPEN w/ optional parameter type 2 (Capability) len 2 Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 OPEN has CAPABILITY code: 2, length 0 Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 OPEN has ROUTE-REFRESH capability(new) for all address-families 

As there are no errors in the OPEN message, Router1 sends a KEEPALIVE message to Router2 and transitions to the next state

 Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 sending KEEPALIVE (rcv_open) Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 went from OpenSent to OpenConfirm Sep 24 00:32:27.283 UTC: BGP: 12.144.8.93 send message type 1, length (incl. header) 45 

Router1 is waiting to receive a KEEPALIVE message from Router2

 Sep 24 00:32:27.291 UTC: BGP: 12.144.8.93 received KEEPALIVE, length (excl. header) 0 

As Router1 has received a KEEPALIVE message from Router2, it transition to the ESTABLISHED state

 Sep 24 00:32:27.291 UTC: BGP: 12.144.8.93 went from OpenConfirm to Established 

As Router1 has reached the ESTABLISHED state, a BGP adjacency has been formed

 Sep 24 00:32:27.291 UTC: %BGP-5-ADJCHANGE: neighbor 12.144.8.93 Up Sep 24 00:32:27.291 UTC: BGP: Delaying initial update for up to 120 seconds Sep 24 00:32:27.395 UTC: BGP: 12.144.8.93 sending KEEPALIVE (io) 

The two routers will now send UPDATE messages to each other to exchange routing information

 Sep 24 00:32:27.395 UTC: BGP(0): 12.144.8.93 rcvd UPDATE w/ attr: nexthop 120.12.12.2, origin i, metric 0, path 714 Sep 24 00:32:27.395 UTC: BGP(0): 12.144.8.93 rcvd 200.0.0.0/24 Sep 24 00:32:27.399 UTC: BGP: 12.144.8.93 received KEEPALIVE, length (excl. header) 0 Sep 24 00:32:27.399 UTC: BGP: 12.144.8.93 received KEEPALIVE, length (excl. header) 0 Sep 24 00:32:27.399 UTC: BGP: compute bestpath for address family 0 Sep 24 00:32:27.399 UTC: BGP(0): table version went from 1 to 4 Sep 24 00:32:27.403 UTC: BGP(0): nettable_walker 200.1.0.0/24 route sourced locally Sep 24 00:32:27.403 UTC: BGP(0): Revise route installing 1 of 1 route for 200.0.0.0/24 -> 12.144.8.93 to main IP table Sep 24 00:32:27.403 UTC: BGP(0): nettable_walker 200.2.0.0/24 route sourced locally Sep 24 00:32:27.403 UTC: BGP: compute bestpath for address family 1 Sep 24 00:32:27.403 UTC: BGP(1): table version went from 1 to 1 Sep 24 00:32:27.403 UTC: BGP: compute bestpath for address family 2 Sep 24 00:32:27.403 UTC: BGP(2): table version went from 1 to 1 Sep 24 00:32:27.407 UTC: BGP: compute bestpath for address family 3 Sep 24 00:32:27.407 UTC: BGP(3): table version went from 1 to 1 Sep 24 00:32:27.407 UTC: BGPNSF: notified IGPs about convergence Sep 24 00:32:27.407 UTC: BGPNSF: Listeners notified about convergence Sep 24 00:32:27.507 UTC: BGP(0): 12.144.8.93 computing updates, afi 0, neighbor version 0, table version 4, starting at 0.0.0.0 Sep 24 00:32:27.507 UTC: BGP(0): 12.144.8.93 send UPDATE (format)200.0.0.0/24, next 120.12.12.2, metric 0, path Sep 24 00:32:27.511 UTC: BGP(0): 12.144.8.92 updates enqueued (average=56, maximum=56) Sep 24 00:32:27.511 UTC: BGP(0): 12.144.8.93 update run completed, afi 0, ran for 4ms, neighbor version 0, start version 4, throttled to 4 Sep 24 00:32:27.511 UTC: BGP(0): 12.144.8.93 initial update completed 

Basic BGP UPDATES

Once a BGP session is running, the BGP speakers exchange UPDATE messages about destinations to which the speaker offers connectivity. In the protocol, the basic CIDR route description is called NLRI. NLRI includes the expected destination prefix, prefix length, path of autonomous systems to the destination and next hop in attributes, which can carry a wide range of additional information that affects the acceptance policy of the receiving router. BGP speakers incrementally announce new NLRI to which they offer reachability, but also announce withdrawals of prefixes to which the speaker no longer offers connectivity. Warning! This Article contains disinformation. ...

BGP Router Connectivity and Learning Routes

In the simplest arrangement all routers within a single AS and participating in BGP routing must be configured in a full mesh: each router must be configured as peer to every other router. This causes scaling problems, since the number of required connections grows quadratically with the number of routers involved. To get around this, two solutions are built into BGP: route reflectors (RFC 4456) and confederations (RFC 5065). For the following discussion of basic UPDATE processing, assume a full iBGP mesh. In mathematics, a function or sequence is said to exhibit quadratic growth when its values are proportional to the square of the function argument or sequence position, in the limit as the argument or sequence position goes to infinity. ...

Basic UPDATE Processing

A given BGP router may accept NLRI in UPDATEs from multiple neighbors and advertise NLRI to the same, or a different set, of neighbors. Conceptually, BGP maintains its own "master" routing table, called the Loc-RIB, separate from the main routing table of the router. For each neighbor, the BGP process maintains a conceptual Adj-RIB-In containing the NLRI received from the neighbor, and a conceptual Adj-RIB-Out for NLRI to be sent to the neighbor. In computer networking a routing table is an electronic table (file) or database type object that is stored in a router or a networked computer. ...

"Conceptual", in the preceding paragraph, means that the physical storage and structure of these various tables are decided by the implementer of the BGP code. Their structure is not visible to other BGP routers, although they usually can be interrogated with management commands on the local router. It is quite common, for example, to store both Adj-RIBs and the Loc-RIB in the same data structure, with additional information attached to the RIB entries. The additional information tells the BGP process such things as whether individual entries belong in the Adj-RIBs for specific neighbors, whether the per-neighbor route selection process made received policies eligible for the Loc-RIB, and whether Loc-RIB entries are eligible to be submitted to the local router's routing table management process. In computer networking a routing table is an electronic table (file) or database type object that is stored in a router or a networked computer. ...

By "eligible to be submitted", BGP will submit the routes that it considers best to the main routing table process. Depending on the implementation of that process, the BGP route is not necessarily selected. For example, a directly connected prefix, learned from the router's own hardware, is usually most preferred. As long as that directly connected route's interface is active, the BGP route to the destination will not be put into the routing table. Once the interface goes down, and there are no more preferred routes, the Loc-RIB route would be installed in the main routing table. Until recently, it was a common mistake to say "BGP carries policies". BGP really carried the information with which rules inside BGP-speaking routers could make policy decisions. Some of the information carried that is explicitly intended to be used in policy decisions are communities and multi-exit discriminators (MED).

Route Selection

The BGP standard specifies a number of decision factors, more than are used by any other common routing process, for selecting NLRI to go into the Loc-RIB. The first decision point for evaluating NLRI is that its next-hop attribute must be reachable (or resolvable). Another way of saying the next-hop must be reachable is that there must be an active route, already in the main routing table of the router, to the prefix in which the next-hop address is located. In computer networking a routing table is an electronic table (file) or database type object that is stored in a router or a networked computer. ...

Next, for each neighbor, the BGP process applies various standard and implementation-dependent criteria to decide which routes conceptually should go into the Adj-RIB-In. The neighbor could send several possible routes to a destination, but the first level of preference is at the neighbor level. Only one route to each destination will be installed in the conceptual Adj-RIB-In. This process will also delete, from the Adj-RIB-In, any routes that are withdrawn by the neighbor.

Whenever a conceptual Adj-RIB-In changes, the main BGP process decides if any of the neighbor's new routes are preferred to routes already in the Loc-RIB. If so, it replaces them. If a given route is withdrawn by a neighbor, and there is no other route to that destination, the route is removed from the Loc-RIB, and no longer sent, by BGP, to the main routing table manager. If the router does not have a route to that destination from any non-BGP source, the withdrawn route will be removed from the main routing table. In computer networking a routing table is an electronic table (file) or database type object that is stored in a router or a networked computer. ...

Per-Neighbor Decisions

After verifying that the next hop is reachable, if the route comes from an internal (i.e., iBGP) peer, the first rule to apply, according to the standard, is to examine the LOCAL_PREF attribute. If there are several iBGP routes from the neighbor, the one with the lowest LOCAL_PREF is selected, unless there are several routes with the same LOCAL_PREF. In the latter case, the route selection process moves to the next tie-breaker. While LOCAL_PREF is the first rule in the standard, once reachability of the NEXT_HOP is verified, Cisco and several other vendors first consider a decision factor called WEIGHT, which is local to the router (i.e., not transmitted by BGP). The route with the highest WEIGHT is preferred.

LOCAL_PREF, WEIGHT, and other criteria can be manipulated by local configuration and software capabilities. Such manipulation is outside the scope of the standard but is commonly used. For example, the COMMUNITY attribute (see below) is not directly used by the BGP selection process. The BGP neighbor process, however, can have a rule to set LOCAL_PREFERENCE or another factor based on a manually programmed rule to set the attribute if the COMMUNITY value matches some pattern-matching criterion. If the route was learned from an external peer, the per-neighbor BGP process computes a LOCAL_PREFERENCE value from local policy rules, and then compares the LOCAL_PREFERENCE of all routes from the neighbor.

At the per-neighbor level, ignoring implementation-specific policy modifiers, the order of tie-breaking rules is:

1. Prefer the route with the shortest AS_PATH. An AS_PATH is the set of AS numbers that must be traversed to reach the advertised destination. AS1-AS2-AS3 is shorter than AS4-AS5-AS6-AS7.
2. Prefer routes with the lowest value of their ORIGIN attribute.
3. Prefer routes with the lowest MULTI_EXIT_DISC (multi-exit discriminator or MED) value.

Before the most recent edition of the BGP standard, if an UPDATE had no MULTI_EXIT_DISC value, several implementations created an MED with the least possible value. The current standard, however, specifies that missing MEDs are to be treated as the highest possible value. Since the now-specified rule may cause different behavior than the vendor interpretations, BGP implementations that used the nonstandard default value have a configuration feature that allows the old or standard rule to be selected.

Decision Factors at the LOC-Rib Level

Once candidate routes are received from neighbors, the Loc-RIB software applies additional tie-breakers to routes to the same destination.

1. If at least one route was learned from an external neighbor (i.e., the route was learned from eBGP), drop all routes learned from iBGP.
2. Prefer the route with the lowest interior cost to the NEXT_HOP, according to the main Routing Table. If two neighbors advertised the same route, but one neighbor is reachable via a low-bandwidth link and the other by a high-bandwidth link, and the interior routing protocol calculates lowest cost based on highest bandwidth, the route through the high-bandwidth link would be preferred and other routes dropped.

If there is more than one route still tied at this point, several BGP implementations offer a configurable option to load-share among the routes, accepting all (or all up to some number). In computer networking a routing table is an electronic table (file) or database type object that is stored in a router or a networked computer. ...

1. Prefer the route learned from the BGP speaker the numerically lowest BGP identifier
2. Prefer the route learned from the BGP speaker with the lowest peer IP address

Communities

BGP communities are sets of routes with some common attribute (RFC 1997). RFC 1998 shows one technique, based on communities, for multihoming with several connections to the same AS.

Uses of Multi-Exit Discriminators

MEDs, defined in the main BGP standard, were originally intended to show the advertising AS's preference, to another neighbor AS, the advertising AS's preference as to which of several links, to the same AS, are preferred as the place to which the accepting AS should transmit traffic. Another application of MEDs is to advertise the value, typically based on delay, of multiple AS that have presence at an IXP, that they impose to send traffic to some destination.

BGP problems and mitigation

IBGP scalability

An autonomous system with IBGP must have all of its IBGP peers connect to each other in a full mesh (where everyone speaks to everyone directly). This full-mesh configuration requires that each router maintain a session to every other router. In large networks, this number of sessions may degrade performance of routers, due either to a lack of memory, or too much CPU process requirements. In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. ...

Route reflectors and confederations both reduce the number of iBGP peers to each router and thus reduce processing overhead. Route reflectors are a pure performance-enhancing technique, while confederations also can be used to implement more fine-grained policy.

Route reflectors^[4] reduce the number of connections required in an AS. A single router (or two for redundancy) can be made a route reflector: other routers in the AS need only be configured as peers to them. The route reflector (RR) offers an alternative to the logical full-mesh requirement of iBGP. A RR acts as a focal point for iBGP sessions. ...

Confederations are sets of autonomous systems. In common practice, ^[5] only one of the confederation AS numbers is seen by the Internet as a whole. Confederations are used in very large networks where a large AS can be configured to encompass smaller more manageable internal ASs.

Confederations can be used in conjunction with route reflectors. Confederations allow more fine-grained policy while route reflectors are a pure scaling technique, but either or both may be relevant to a particular situation.

Both confederations and route reflectors can be subject to persistent oscillation, unless specific design rules, affecting both BGP and the interior routing protocol, are followed ^[6].

However, these alternatives can introduce problems of their own, including the following:

• route oscillation,
• sub-optimal routing,
• increase of BGP convergence time ^[7]

Additionally, route reflectors and BGP confederation were not designed to ease BGP router's configuration. Nevertheless, these are common tools for experienced BGP network architects. These tools may be combined, as, for example, a hierarchy of route reflectors.

Instability

The routing tables managed by a BGP implementation are adjusted continually to reflect actual changes in the network, such as links breaking and being restored or routers going down and coming back up. In the network as a whole it is normal for these changes to happen almost continuously, but for any particular router or link changes are supposed to be relatively infrequent. If a router is misconfigured or mismanaged then it may get into a rapid cycle between down and up states. This pattern of repeated withdrawal and reannouncement, known as route flapping, can cause excessive activity in all the other routers that know about the broken link, as the same route is continuously injected and withdrawn from the routing tables. In computer networking and telecommunications, a flapping router is a router that transmits routing updates alternately advertising a destination network first via one route, then via a different route; this behavior is called route flapping. ...

A feature known as route flap damping (RFC 2439) is built into many BGP implementations in an attempt to mitigate the effects of route flapping. Without damping the excessive activity can cause a heavy processing load on routers, which may in turn delay updates on other routes, and so affect overall routing stability. With damping, a route's flapping is exponentially decayed. At first instance when a route becomes unavailable but quickly reappears for whatever reason, then the damping does not take effect, so as to maintain the normal fail-over times of BGP. At the second occurrence, BGP shuns that prefix for a certain length of time; subsequent occurrences are timed out exponentially. After the abnormalities have ceased and a suitable length of time has passed for the offending route, prefixes can be reinstated and its slate wiped clean. Damping can also mitigate denial of service attacks; damping timings are highly customizable. A quantity is said to be subject to exponential decay if it decreases at a rate proportional to its value. ... A denial-of-service attack (also, DoS attack) is an attack on a computer system or network that causes a loss of service to users, typically the loss of network connectivity and services by consuming the bandwidth of the victim network or overloading the computational resources of the victim system. ...

However, subsequent research has shown that flap damping can actually lengthen convergence times in some cases, and can cause interruptions in connectivity even when links are not flapping.^[8][9] Moreover, as backbone links and router processors have become faster, some network architects have suggested that flap damping may not be as important as it used to be, since changes to the routing table can be absorbed much faster by routers. This has led the RIPE Route Working Group to write that "with the current implementations of BGP flap damping, the application of flap damping in ISP networks is NOT recommended. ... If flap damping is implemented, the ISP operating that network will cause side-effects to their customers and the Internet users of their customers' content and services ... . These side-effects would quite likely be worse than the impact caused by simply not running flap damping at all." [1] Improving stability without the problems of flap damping is the subject of current research.[2]

Routing table growth

One of the largest problems faced by BGP, and indeed the Internet infrastructure as a whole, comes from the growth of the Internet routing table. If the global routing table grows to the point where some older, less capable, routers cannot cope with the memory requirements or the CPU load of maintaining the table, these routers will cease to be effective gateways between the parts of the Internet they connect. In addition, and perhaps even more importantly, larger routing tables take longer to stabilize (see above) after a major connectivity change, leaving network service unreliable, or even unavailable, in the interim.

Until late 2001, the global routing table was growing exponentially, threatening an eventual widespread breakdown of connectivity. In an attempt to prevent this from happening, there was a cooperative effort by ISPs to keep the global routing table as small as possible, by using CIDR and route aggregation. While this slowed the growth of the routing table to a linear process for several years, with the expanded demand for multihoming by end user networks the growth was once again exponential by the middle of 2004. The global routing table hit 200,000 entries on or about October 13, 2006. In mathematics, exponential growth (or geometric growth) occurs when the growth rate of a function is always proportional to the functions current size. ... Warning! This Article contains disinformation. ...

A network black hole is often used to improve aggregation of the BGP global routing table.^{[citation needed]} Consider an AS that has been allocated the address space 172.16.0.0/16, from which it has assigned the prefixes 172.16.0.0/18, 172.16.64.0/18, and 172.16.192.0/18. The AS can advertise the whole block, 172.16.0.0/16. This AS will still receive traffic sent to the "hole", 172.16.128.0/18, but will silently discard it. In networking, black holes refer to places in the network where incoming traffic is silently discarded (or dropped), without informing the source that the data did not reach its intended recipient. ... In the Internet, an autonomous system (AS) is a collection of IP networks and routers under the control of one entity (or sometimes more) that presents a common routing policy to the Internet. ...

Requirements of a router for use of BGP for Internet and backbone-of-backbones purposes

Routers, especially small ones intended for Small Office/Home Office (SOHO) use, may not include BGP software. Some SOHO routers simply are not capable of running BGP using BGP routing tables of any size. Other commercial routers may need a specific software executable image that contains BGP, or a license that enables it. Open source packages that run BGP include GateD, GNU Zebra, Quagga, OpenBGPD, and Vyatta. Devices marketed as Layer 3 switches are less likely to support BGP than devices marketed as routers, but high-end Layer 3 Switches usually can run BGP. The modern concept of Small Office and Home Office or SoHo, or Small or Home Office deals with the category of business which can be from 1 to 10 workers. ... Zebra is a routing software package that provides TCP/IP based routing services with routing protocols support such as RIP, OSPF and BGP. Zebra also supports special BGP Route Reflector and Route Server behavior. ... Quagga is a free software routing suite, providing implementations of OSPF (v2 & v3), RIP (v1, v2 & v3) and BGP (v4) for Unix platforms, particularly FreeBSD, GNU/Linux, Solaris and NetBSD. Quagga is a fork of the GNU Zebra project (inactive since 2003) which was developed by Kunihiro Ishiguro. ... OpenBPGD is a Unix system daemon that implements the Border Gateway Protocol version 4. ... Vyatta manufacturers open source software routers and firewalls. ... The network layer is third layer out of seven in OSI model and it is the third layer out of five in TCP/IP model. ... This article describes the computer networking device. ...

Products marketed as switches may or may not have a size limitation on BGP tables, such as 20,000 routes, far smaller than a full Internet table plus internal routes. These devices, however, may be perfectly reasonable and useful when used for BGP routing of some smaller part of the network, such as a confederation-AS representing one of several smaller enterprises that are linked, by a BGP backbone of backbones, or a small enterprise that announces routes to an ISP but only accepts a default route and perhaps a small number of aggregated routes. A Default route is the IP address used by a router when no other assigned route works for a given IP packets destination. ...

A BGP router used only for a network with a single point of entry to the internet may have a much smaller routing table size (and hence RAM and CPU requirement) than a multihomed network. Even simple multihoming can have modest routing table size. See RFC 4098 for vendor-independent performance parameters for single BGP router convergence in the control plane.

It is not a given that a router running BGP needs a large memory. The memory requirement depends on the amount of BGP information exchanged with other BGP speakers, and the way in which the particular router stores BGP information. Do be aware that the router may have to keep more than one copy of a route, so it can manage different policies for route advertising and acceptance to a specific neighboring AS. The term view is often used for these different policy relationships on a running router.

If one router implementation takes more memory per route than another implementation, this may be a legitimate design choice, trading processing speed against memory. A full BGP table from an external peer will have in excess of 222,000 routes as of June 2007. Large ISPs may add another 50% for internal and customer routes. Again depending on implementation, separate tables may be kept for each view of a different peer AS.

Open Source Implementations of BGP

• 6WINDGate, commercial embedded open-source routing modules from 6WIND including multi-core and network processors support.
• Vyatta, a commercial open-source router / firewall.
• Quagga, a fork of GNU Zebra for Unix-like systems.
• GNU Zebra, a GPL routing suite supporting BGP4.
• OpenBGPD, a BSD licensed implementation by the OpenBSD team.
• XORP, the eXtensible Open Router Platform, a BSD licensed suite.
• BIRD, a GPL routing package for Unix-like systems.

Vyatta manufacturers open source software routers and firewalls. ... Quagga is a free software routing suite, providing implementations of OSPF (v2 & v3), RIP (v1, v2 & v3) and BGP (v4) for Unix platforms, particularly FreeBSD, GNU/Linux, Solaris and NetBSD. Quagga is a fork of the GNU Zebra project (inactive since 2003) which was developed by Kunihiro Ishiguro. ... Diagram of the relationships between several Unix-like systems A Unix-like operating system is one that behaves in a manner similar to a Unix system, while not necessarily conforming to or being certified to any version of the Single UNIX Specification. ... Zebra is a routing software package that provides TCP/IP based routing services with routing protocols support such as RIP, OSPF and BGP. Zebra also supports special BGP Route Reflector and Route Server behavior. ... GPL redirects here. ... OpenBPGD is a Unix system daemon that implements the Border Gateway Protocol version 4. ... The BSD license is the license agreement that the BSD software (largely, a version of UNIX) is distributed under. ... OpenBSD is a Unix-like computer operating system descended from Berkeley Software Distribution (BSD), a Unix derivative developed at the University of California, Berkeley. ... XORP, or Extensible Open Router Platform, is a project to create open source routing system. ...

BGP simulators

• BGPlay, a Java applet that presents a graphical visualization of BGP routes and updates for any real AS on the Internet
• SSFnet, SSFnet network simulator includes a BGP implementation developed by BJ Premore
• C-BGP, a BGP simulator able to perform large-scale simulation trying to model the ASes of the Internet or modelling ASes as large as Tier-1^[10].
• BGP++, a patch integrating GNU Zebra software on ns-2 and GTNetS network simulators
• ns-BGP, a BGP extension for ns-2 simulator based on the SSFnet implementation

Zebra is a routing software package that provides TCP/IP based routing services with routing protocols support such as RIP, OSPF and BGP. Zebra also supports special BGP Route Reflector and Route Server behavior. ... NS-2 is a Nestor Series 2 robot first appearing in an Isaac Asimov story. ... NS-2 is a Nestor Series 2 robot first appearing in an Isaac Asimov story. ...

References

1. ^ Capabilities Advertisement with BGP-4,RFC 2842, R. Chandra & J. Scudder,May 2000
2. ^ Multiprotocol Extensions for BGP-4,RFC 2858, T. Bates et al.,June 2000
3. ^ BGP/MPLS VPNs.,RFC 2547, E. Rosen and Y. Rekhter,April 2004
4. ^ BGP Route Reflection: An Alternative to Full Mesh Internal BGP (IBGP), RFC 4456, T. Bates et al, April 2006
5. ^ Autonomous System Confederations for BGP, RFC 3065, P. Traina et al, February 2001
6. ^ Border Gateway Protocol (BGP) Persistent Route Oscillation Condition, RFC 3345, D. McPherson et al, August 2002
7. ^ Terminology for Benchmarking BGP Device Convergence in the Control Plane, RFC 4098, H. Berkowitz et al, June 2005
8. ^ Route Flap Damping Exacerbates Internet Routing Convergence
9. ^ Zhang, Beichuan; Pei Dan, Daniel Massey, Lixia Zhang (June 2005). Timer Interaction in Route Flap Damping. IEEE 25th International Conference on Distributed Computing Systems. Retrieved on 2006-09-26. “We show that the current damping design leads to the intended behavior only under persistent route flapping. When the number of flaps is small, the global routing dynamics deviates significantly from the expected behavior with a longer convergence delay.”
10. ^ Modeling the routing of an Autonomous System with C-BGP

Year 2006 (MMVI) was a common year starting on Sunday of the Gregorian calendar. ... is the 269th day of the year (270th in leap years) in the Gregorian calendar. ...

See also

• Autonomous system (Internet)
• Internet Assigned Numbers Authority
• Regional Internet Registry
• Routing
• Route filtering
• Routing Assets Database (RADB)
• QPPB

In the Internet, an autonomous system (AS) is a collection of IP networks and routers under the control of one entity (or sometimes more) that presents a common routing policy to the Internet. ... The Internet Assigned Numbers Authority (IANA) is the entity that oversees global IP address allocation, DNS root zone management, and other Internet protocol assignments. ... A Regional Internet Registry (RIR) is an organisation overseeing the allocation and registration of Internet number resources within a particular region of the world. ... This article is about routing (or routeing) in computer networks. ... Routing Assets Database, or RADB is run by Merit Network Inc. ... QPPB, an acronym for QoS Policy Propagation via BGP, is a mechanism that allows propagation of QoS policy and classification by the sending party based on access lists, community lists and AS paths, thus helping to classify based on destination instead of source address. ...

External links

• LinkRank A tool for BGP routing visualization by University of California, Los Angeles
• BGP Routing Resources (includes a dedicated section on BGP & ISP Core Security)
• BGP table statistics
• ASNumber Firefox Extension showing the AS number and additional information of the website currently open
• RIPE Routing Information Service collecting over 550 IPv4 and IPv6 BGP feeds at 14 sites around the world
• RIS Looking Glass into the Default Free Routing zone of the Internet
• RISwhois providing IPv4/IPv6 Address to BGP AS Origin Mapping
• RIS BGPlay BGP routing visualization tool by Università degli Studi Roma Tre
• Linux Magazine: Demystifying BGP (Good, Detailed BGP explanation; requires registration)
• Some important BGP RFCs
  • RFC 4456, BGP Route Reflection - An Alternative to Full Mesh Internal BGP (IBGP)(obsoletes: RFC 2796)
  • RFC 4278, Standards Maturity Variance Regarding the TCP MD5 Signature Option (RFC 2385) and the BGP-4 Specification
  • RFC 4277, Experience with the BGP-4 Protocol
  • RFC 4276, BGP-4 Implementation Report
  • RFC 4275, BGP-4 MIB Implementation Survey
  • RFC 4274, BGP-4 Protocol Analysis
  • RFC 4273, Definitions of Managed Objects for BGP-4
  • RFC 4272, BGP Security Vulnerabilities Analysis
  • RFC 4271, A Border Gateway Protocol 4 (BGP-4) (obsoletes: RFC 1771)
  • RFC 3392, Capabilities Advertisement with BGP-4
  • RFC 3065, Autonomous System Confederations for BGP
  • RFC 2918, Route Refresh Capability for BGP-4
  • RFC 1772, Application of the Border Gateway Protocol in the Internet Protocol (BGP-4) using SMIv2
• Obsolete RFCs
  • RFC 2796, Obsolete - BGP Route Reflection - An Alternative to Full Mesh IBGP
  • RFC 1965, Obsolete - Autonomous System Confederations for BGP
  • RFC 1771, Obsolete - A Border Gateway Protocol 4 (BGP-4)
  • RFC 1657, Obsolete - Definitions of Managed Objects for the Fourth Version of the Border Gateway
  • RFC 1655, Obsolete - Application of the Border Gateway Protocol in the Internet
  • RFC 1654, Obsolete - A Border Gateway Protocol 4 (BGP-4)
  • RFC 1105, Obsolete - Border Gateway Protocol (BGP)

• BGP Interactions at Router Startup Described as a Sequence Diagram (PDF)
• BGP Protocol Fuzzing and Robustness Testing Mu_Security