Interdomain Routing (Border Gateway Protocol)

Internet is organized as autonomous systems, each of which is under the control of a single administrative entity. The Border Gateway Protocol (BGP) is an interautonomous system routing protocol. An autonomous system is a network or group of networks under a common administration and with common routing policies. BGP is used to exchange routing information for the Internet and is the protocol used between Internet service providers (ISP).

The basic idea behind autonomous systems is to provide an additional way to hierarchically aggregate routing information in a large internet, thus improving scalability. 

We divide the routing problem into two parts: routing within a single autonomous system and routing between autonomous systems. another name for autonomous systems in the Internet is routing domains, we refer to the two parts of the routing problem as interdomain routing and intradomain routing.

There have been two major interdomain routing protocols in the recent history of the Internet. The first was the Exterior Gateway Protocol (EGP). EGP had a number of limitations, perhaps the most severe of which was that it constrained the topology of the Internet rather significantly. EGP basically forced a treelike topology onto the Internet, or to be more precise, it was designed when the Internet had a treelike topology,there is a single backbone, and autonomous systems are connected only as parents and children and not as peers.

The replacement for EGP is the Border Gateway Protocol (BGP), which is in its fourth version at the time of this writing (BGP-4).

BGP assumes that the Internet is an arbitrarily interconnected set of ASs. This model is clearly general enough to accommodate non-treestructured internetworks, like the simplified picture of today’s multibackbone Internet shown in Figure.

Today’s Internet consists of an interconnection of multiple backbone networks and sites are connected to each other in arbitrary ways. Some large corporations connect directly to one or more of the backbones, while others connect to smaller, nonbackbone service providers.

Given this rough sketch of the Internet, if we define local traffic as traffic that originates at or terminates on nodes within an AS, and transit traffic as traffic that passes through an AS, we can classify ASs into three types:

•  Stub AS: an AS that has only a single connection to one other AS; such an AS will only carry local traffic. The small corporation in Figure is an example of a stub AS.

•  Multihomed AS: an AS that has connections to more than one other AS but that refuses to carry transit traffic; for example, the large corporation at the top of Figure.

•  Transit AS: an AS that has connections to more than one other AS and that is designed to carry both transit and local traffic, such as the backbone providers in Figure.

Finding optimal paths based on minimizing some sort of link metric, the problem of interdomain routing turns out to be so difficult that the goals are more modest. First and foremost, the goal is to find any path to the intended destination that is loop-free. We are more concerned with reachability than optimality. Finding a path that is anywhere close to optimal is considered a great achievement.

When configuring BGP, the administrator of each AS picks at least one node to be a “BGP speaker,” which is essentially a spokesperson for the entire AS. That BGP speaker establishes BGP sessions to other BGP speakers in other ASs. These sessions are used to exchange reachability information among ASs.the BGP speakers, the AS has one or more border “gateways,” which need not be the same as the speakers. The border gateways are the routers through which packets enter and leave the AS.

BGP advertises complete paths as an enumerated list of ASs to reach a particular network. This is necessary to enable the sorts of policy decisions described above to be made in accordance with the wishes of a particular AS. It also enables routing loops to be readily detected.

We should note that a given AS will only advertise routes that it considers good enough for itself. That is, if a BGP speaker has a choice of several different routes to a destination, it will choose the best one according to its own local policies, and then that will be the route it advertises. Furthermore, a BGP speaker is under no obligation to advertise any route to a destination, even if it has one. This is how an AS can implement
a policy of not providing transit—by refusing to advertise routes to prefixes that are not contained within that AS, even if it knows how to reach them.

In addition to advertising paths, BGP speakers need to be able to cancel previously advertised paths if a critical link or node on a path goes down. This is done with a form of negative advertisement known as a withdrawn route. Both positive and negative reachability information are carried in a BGP update message, the format of which is shown in Figure.

BGP-4 update packet format.