Charles M. Kozierok The TCP-IP Guide

Подождите немного. Документ загружается.

Key Concept: BGP supports an arbitrary topology of autonomous systems. Each

autonomous system using BGP assigns one or more routers to implement the

protocol. These devices then exchange messages to establish contact with each

other and share information about rates through the internetwork using TCP. BGP employs

a sophisticated path vector route calculation algorithm that determines routes from path

attributes that describe how different networks can be reached.

Note: BGP maintains backwards compatibility with the older exterior routing

protocol, EGP.

BGP Topology, Speakers, Border Routers and Neighbor Relationships (Internal and

External Peers)

In my overview of BGP, I boiled down the function of the Border Gateway Protocol (BGP)

into this summary: the exchange of network reachability information between autonomous

systems (ASes) of routers and networks, and the determination of routes from this infor-

mation. The actual method that BGP uses to accomplish this, however, is fairly complex. To

help us understand how BGP works, we should start by looking at the structure of BGP

internetworks, and also a discussion of key BGP terms.

BGP Topology and Speakers

One of the most important characteristics of BGP is its flexibility. The protocol can connect

together any internetwork of autonomous systems using an arbitrary topology. The only

requirement is that each AS have at least one router that is able to run BGP and that this

router connect to at least one other AS's BGP router. Beyond that, “the sky's the limit,” as

they say. BGP can handle a set of ASes connected in a full mesh topology (each AS to

each other AS), a partial mesh, a chain of ASes linked one to the next, or any other config-

uration. It also handles changes to topology that may occur over time.

Another important assumption that BGP makes is that it doesn't know anything about what

happens within the AS. This is of course an important prerequisite to the notion of an AS

being autonomous—it has its own internal topology and uses its own choice of routing

protocols to determine routes. BGP only takes the information conveyed to it from the AS

and shares it with other ASes.

Creating a BGP internetwork begins with the designation of certain routers in each AS as

ones that will run the protocol. In BGP parlance, these are called BGP speakers, since they

speak the BGP “language”. A protocol can reasonably be called a language, but I have not

encountered this notion of a “speaker” in any other protocol, so it's somewhat interesting

terminology.

BGP Router Roles and Neighbors

An autonomous system can contain many routers which are connected in an arbitrary

topology. We can draw a distinction between routers in an AS that are connected only to

other routers within the AS, versus those that connect to other ASes. Routers in the former

group are usually called internal routers, while the latter group are called border routers in

BGP, and similar names in other protocols. For example, in OSPF they are called boundary

routers.

Of course, the notion of a border is the basis for the name of the BGP protocol itself. To

actually create the BGP internetwork, the BGP speakers bordering each AS are physically

connected to one or more BGP speakers in other ASes, in whatever topology the inter-

network designer decrees. When a BGP speaker in one AS is linked to a BGP speaker in

another AS, they are deemed neighbors. The direct connection between them allows them

to exchange information about the ASes of which they are a part.

BGP Internal and External Peers

Most BGP speakers will be connected to more than one other speaker. This provides both

greater efficiency in the form of more direct paths to different networks, and also redun-

dancy to allow the internetwork to cope with either device or connection failures. It is

possible (and in many cases, likely) for a BGP speaker to have neighbor relationships with

other BGP speakers both within its own AS and outside its AS. A neighbor within the AS is

called an internal peer, while a neighbor outside the AS is an external peer. BGP between

internal peers is sometimes called Internal BGP (IBGP) while use of the protocol between

external peers is External BGP (EBGP). The two are similar, but differ in certain areas,

especially path attributes and route selection. You can see an example of BGP topology

and the designation of internal and external peers in Figure 191.

Key Concept: Each router configured to use BGP is called a BGP speaker; these

devices exchange route information using the BGP messaging system. Routers that

only connect to other routers in the same autonomous system are called internal

routers, while those that connect to other ASes are border routers. Neighboring BGP

speakers in the same AS are called internal peers, while those in different ASes are

external peers.

A peer connection between BGP speakers can be either a direct link using some form of

layer two technology, or an indirect link using TCP. This allows the BGP speakers to

establish BGP sessions and then exchange routing information, using the messaging

system we will see later in this section. Of course, it also is the means by which actual “end

user” traffic moves between autonomous systems. External peers are normally connected

directly, while internal peers are often linked indirectly.

In the next topic we will see that the method in which ASes are connected has an important

impact on the overall function of the internetwork and how traffic is carried on it.

BGP Autonomous System Types, Traffic Flows and Routing Policies

When we connect autonomous systems (ASes) together to form an internetwork, the paths

between AS border routers form the conduit by which messages move from one AS to

another. It is very important that the flow of messages between ASes be carefully

controlled. Depending on circumstances, we may wish to limit or even prohibit certain types

of messages from going to or from a certain AS. These decisions in turn have a direct

impact on BGP route determination.

BGP Traffic Flow and Traffic Types

The flow of messages in an internetwork is sometimes collectively called traffic. This term

presents a good analogy, because we can consider the matter of traffic flow control in a

BGP internetwork in much the same way we do on the streets of a city. You have probably

in the past seen signs on residential streets that say “No Through Traffic” or “Local Traffic

Figure 191: BGP Example Topology and Designations

This diagram is a variation on Figure 171 that shows the names used by BGP to refer to different types of

routers and autonomous systems. Internal routers are shown in blue while border routers are red. BGP

speakers that communicate within an AS are internal peers, while those that communicate between ASes are

external peers. This highly simplified internetwork shows two stub ASes, both of which only connect to the

multihomed AS #2.

Autonomous System #2

(Multihomed)

Autonomous System #1

(Stub)

Autonomous System #3

(Stub)

R1C

R1B

R1A

R2A

R2B

R2C

R2D

R2E

Ext e r n a l

Peers

Ext e r n a l

Peers

Ext e r n a l

Peers

Internal

Peers

Only”. These are attempt to control the flow of traffic over those streets. A more extreme

example of this would be a street in the neighborhood where I used to live, where a

barricade was intentionally erected in the middle to turn a busy through street into a pair of

dead-ends. Again, the goal was traffic control.

These measures highlight a key distinction between local traffic and through traffic in a

neighborhood. The very same categorization is important in BGP:

☯ Local Traffic: Traffic carried within an autonomous system that either originated in

that same AS, or is intended to be delivered within that AS. This is like local traffic on a

street.

☯ Transit Traffic: Traffic that was generated outside that AS and is intended to be

delivered outside the AS. This is like what we commonly call through traffic on the

streets.

BGP Autonomous System Types

In the previous topic we discussed the distinction between internal routers and border (or

boundary) routers in an AS. If we look at the entire BGP internetwork, we can make a

similar distinction between different types of ASes, based on how they are interconnected in

the overall BGP topology. There are two main types of AS:

☯ Stub AS: This is an AS that is connected to only one other AS. It is comparable to a

cul-de-sac (dead-end street) in our road analogy; usually, only vehicles coming from or

going to houses on the street will be found on that street.

☯ Multihomed AS: This is an AS that is connected to two or more other ASes. It is

comparable to a through street in our road analogy, because it is possible that cars

may enter the street and pass through it without stopping at any of the street's houses.

In the example BGP internetwork in Figure 191, I have linked border routers in AS #2 to

both AS #1 and AS #3. While traffic from AS #2 can flow both to and from AS #1 and AS #3,

it is possible that traffic from AS #1 may also flow to AS #3 and vice-versa. AS #2 acts as

the “through street” for these datagrams.

BGP Autonomous System Routing Policies

The reason why BGP makes a distinction between traffic types and AS types is the same

as why it is done on the streets: many folks have a dim view of through traffic. In a neigh-

borhood, everyone wants to be able to get from their homes to anywhere they need to go in

the city, but they don't want lots of other people using their streets. Similarly, every auton-

omous system must use at least one other autonomous system to communicate with

distance ASes, but many are less than enthusiastic about being a conduit for lots of

external traffic.

This reluctance really does make sense in many cases, both in the case of a neighborhood

or in the case of BGP. Having lots of cars and trucks on a residential street can be a

problem in a number of ways: safety issues, wear and tear on the road, pollution and so

forth. Similarly, if a multihomed AS was forced to carry all transit traffic that other ASes want

to send to it, it might become overloaded.

To provide control over the carrying of transit traffic, BGP allows an AS to set up and use

routing policies. These are sets of rules that govern how an AS will handle transit traffic. A

great deal of flexibility exists in how an AS decides to handle transit traffic. Some of the

many options include:

☯ No Transit Policy: An AS can have a policy that it will not handle transit traffic at all.

☯ Restricted AS Transit Policy: An AS may allow handling of traffic from certain ASes

but not others. In this case it tells the ASes it will handle that they may send it traffic,

but does not say this to the others.

☯ Criteria-Based Transit Policy: An AS may use a number of different criteria to decide

whether to allow transit traffic. For example, it might allow transit traffic only during

certain times, or only when it has enough spare capacity.

Note: An autonomous system that is willing to carry transit traffic is sometimes

called a transit AS.

In a similar manner, policies can be set that control how an AS will have its own traffic

handled by other autonomous systems. Obviously a stub AS will always connect to the

internetwork as a whole using the single AS to which it connects. A multihomed AS,

however, may have policies that influence route selection by specifying the conditions

under which one AS should be used over another. These policies may be based on consid-

erations of security (if one connecting AS is deemed more secure than another),

performance (one AS is faster than another), reliability or other factors.

Issues With Routing Policies and Internetwork Design

What would happen to a city if every street only allowed local traffic? It would be pretty hard

to get around. Of course this problem never occurs in well-designed cities, because traffic

planners understand the dual need for connectivity and through-traffic avoidance in

residential areas. Cities are laid out in a somewhat hierarchical fashion, so local traffic

“funnels” to thoroughfares intended specifically to carry non-local traffic.

The same basic situation exists in an internetwork. It wouldn't work very well if every AS

declared it was not interested in carrying transit traffic! Usually, internetworks are designed

so that certain autonomous systems are intended to carry large amounts of transit traffic.

This is typically the function of high-speed, high-capacity backbone connections, which

serve other ASes as customers. An AS will usually only carry another AS's traffic if arrange-

ments have been made to allow this.

Key Concept: One important issue in BGP is how to handle the flow of traffic

between autonomous systems. Each autonomous system in a BGP internetwork is

either a stub AS, if it connects to only one other AS, or a multihomed AS if it connects

to two or more others. BGP allows the administrators of a multihomed AS to establish

routing policies that specify under what conditions the AS is willing to handle transit traffic

(messages sent over the AS whose source and destination are both external to that AS.)

BGP Route Storage and Advertisement, and BGP Routing Information Bases (RIBs)

The job of the Border Gateway Protocol is to facilitate the exchange of route information

between BGP devices, so that each router can determine efficient routes to each of the

networks on an IP internetwork. This means that descriptions of routes are the key data that

BGP devices work with. Every BGP speaker is responsible for managing route descriptions

according to specific guidelines established in the BGP standards.

BGP Route Information Management Functions

Conceptually, the overall activity of route information management can be considered to

encompass four main tasks:

☯ Route Storage: Each BGP stores information about how to reach networks in a set of

special databases. It also uses databases to hold routing information received from

other devices.

☯ Route Update: When a BGP device receives an Update from one of its peers, it must

decide how to use this information. Special techniques are applied to determine when

and how to use the information received from peers to properly update the device's

knowledge of routes.

☯ Route Selection: Each BGP uses the information in its route databases to select

good routes to each network on the internetwork.

☯ Route Advertisement: Each BGP speaker regularly tells its peers what it knows

about various networks and methods to reach them. This is called route advertisement

and is accomplished using BGP Update messages. We'll learn more about these

messages in the next few topics, and examine them in detail in the detailed section on

BGP message formats.

BGP Routing Information Bases (RIBs)

The heart of BGP's system of routing information management and handling is the

database where routes are stored. This database is collectively called the Routing Infor-

mation Base (RIB), but it is in fact not a monolithic entity. It is comprised of three separate

sections that are used by a BGP speaker to handle the input and output of routing infor-

mation. Two of these sections themselves consist of several individual parts, or copies.

The three RIB sections (using the cryptic names given them by the BGP standards, sorry!)

are:

☯ Adj-RIBs-In: A set of input database parts that holds information about routes

received from peer BGP speakers.

☯ Loc-RIB: The local RIB. This is the core database that stores routes that have been

selected by this BGP device and are considered valid to it.

☯ Adj-RIBs-Out: A set of output database parts that holds information about routes that

this BGP device has selected to be disseminated to its peers.

Thus, the RIB can be considered either a single database or a set of related databases,

depending on how you look at it. (The divisions above are conceptual in nature; the entire

RIB can be implemented as a single database with an internal structure representing the

different components, or as separate databases.)

The RIB is a fairly complex data structure, not just because of this multi-section structure,

but because BGP devices store considerably more information about routes than simpler

routing protocols. Routes are also called paths in BGP, and the detailed descriptions of

them are stored in the form of special BGP path attributes.

The three sections of the RIB are the mechanism by which information flow is managed in a

BGP speaker. Data received from Update messages transmitted by peer BGP speakers is

held in the Adj-RIBs-In, with each Adj-RIB-In holding input from one peer. This data is then

analyzed and appropriate portions of it selected to update the Loc-RIB, which is the main

database of routes this BGP speaker is using. On a regular basis, information from the Loc-

RIB is placed into the Adj-RIBs-Out to be sent to other peers using Update messages. This

information flow is accomplished as part of the system of route update, selection and adver-

tisement known as the BGP Decision Process.

Key Concept: The routine operation of BGP requires BGP speakers to store,

update, select and advertise routing information. The central data structure used for

this purpose is the BGP Routing Information Base (RIB). The RIB actually consists of

three sections: a set of input databases (Adj-RIBs-In) that hold routing information received

from peers, a local database (Loc-RIB) that contains the router’s current routes, and a set of

output databases (Adj-RIBs-Out) used by the router to send its routing information to other

routers.

BGP Path Attributes and Algorithm Overview

Routing protocols using a distance-vector algorithm such as RIP are relatively simple in

large part because the information each device stores about each route is itself simple.

Each router only knows that it can reach a network at a specific cost through a particular

next-hop router. It doesn't have knowledge of the route that datagrams will take to reach

any of these networks. This level of knowledge is simply insufficient for the needs of a

protocol like BGP.

BGP's Path-Vector Routing Algorithm and Path Attributes

In order to handle the calculation of efficient, non-looping routes in an arbitrary topology of

autonomous systems, we need to know not just “to get to network N7 send to router R4”;

we need to have some understanding of the characteristics of the entire path between

ourselves and network N7. By storing this additional information, it is possible to make

decisions about how to compute and change routes, using knowledge of the entire path

between a router and a network.

Thus, in BGP, instead of advertising networks in terms of a destination and the distance to

that destination, BGP devices advertise networks as destination addresses and path

descriptions to reach those destinations. This means BGP uses, instead of a distance-

vector algorithm, a path-vector algorithm. Each communication of a reachable network

provides considerable information about the entire sequence of routers to a destination.

Due to this inclusion of topology information, path-vector protocols are sometimes

described as a combination of distance-vector and link-state algorithms. This doesn't really

do them justice, however, since they do not function in the same way as either of those

algorithm types.

On The Web: If you are interested in additional general information about path-

vector algorithms, you can find some in RFC 1322, A Unified Approach to Inter-

Domain Routing. Warning: do not read before operating heavy machinery. ☺

The information about the path to each route is stored in the Routing Information Base

(RIB) of each BGP speaker in the form of BGP path attributes. These attributes are used to

advertise routes to networks when BGP devices send out Update messages. The storing,

processing, sending and receiving of path attributes is “the” method by which routers decide

how to create routes, so understanding them is obviously quite important.

There are several different path attributes, each of which describes a particular character-

istic of a route. Attributes are divided into different categories based on their level of

importance and specific rules designed to manage their propagation. The most important

path attributes are called well-known attributes; every BGP speaker must recognize and

process these, but only some are required to be sent with every route. Other attributes are

optional and may or not be implemented. These are further differentiated based on how

they are handled when received by a device that does not recognize them.

BGP Path Attribute Classes

The four formal classifications of path attributes are:

☯ Well-Known Mandatory: These are the most important path attributes; they must be

included in every route description in Update messages, and must be processed by

each BGP device receiving them.

☯ Well-Known Discretionary: These path attributes must be recognized by a BGP

device if received, but they may or may not be included in an Update message. Thus,

they are optional for a sender of information, but mandatory for a receiver to process.

☯ Optional Transitive: These path attributes may be recognized by a BGP router and

may be included in an Update message. They must be passed on to other BGP

speakers when the route is advertised, even if received by a device that does not

recognize the attribute.

☯ Optional Non-Transitive: Optional attributes that may be recognized by a BGP

device and may be included in an Update message. If received by a device that does

not recognize the attribute, it is dropped and not passed on to the next router.

Note: As you might imagine, all well-known attributes are by definition transitive—

they must be passed on from one BGP speaker to the next.

Key Concept: Unlike simpler routing protocols that store only limited information

about how to reach a network, such as its cost and the next hop to reach it, BGP

stores detailed information about complete routes to various networks. This infor-

mation takes the form of path attributes that describe various characteristics of a path

(route) through the ASes that connect a router to a destination network.

BGP Path Attribute Characteristics

Table 136 contains a summary of the characteristics of each of the most common BGP path

attributes used to describe the route to a destination, as well as the Attribute Type code

assigned to each in BGP Update messages:

Table 136: Summary of BGP Path Attributes (Page 1 of 2)

BGP Path

Attribute

Classifica-

tion

Attribute

Type Value

Description

Origin

Well-Known

Mandatory

Specifies the origin of the path information. This

attribute indicates whether the path came originally

from an interior routing protocol, the older exterior

routing protocol EGP, or some other source.

AS_Path

Well-Known

Mandatory

A list of autonomous system numbers that describes

the sequence of ASes through which this route

description has passed. This is a critically important

attribute, since it contains the actual path of auton-

omous systems to the network. It is used to calculate

routes and to detect routing loops.

Next_Hop

Well-Known

Mandatory

The next-hop router to be used to reach this

destination.

Some of these path attributes are straight-forward to understand; others are fairly cryptic

and probably confusing. Delving into any more detail on the path attributes leads us into a

full-blown description of detailed inter-AS route calculations. We'll look at that to some

degree in the next topic.

For full details on the message format used to communicate path attributes, see the format

of BGP Update messages.

BGP Route Determination and the BGP Decision Process

The last two topics have described the fundamentals of how BGP devices store and

manage information about routes to networks. This included an overview of the four route

information management activities performed by BGP speakers: route storage, update,

selection and advertisement. Route storage is the function of the Routing Information Base

(RIB) in each BGP speaker. Path attributes are the mechanism by which BGP stores details

about routes and also describes those details to BGP peers.

BGP Decision Process Phases

As we have seen, the RIB also contains sections for holding input information received from

BGP peers, and for holding output information each BGP device wants to send to those

peers. The functions of route update, selection and advertisement are concerned with

analyzing this input information, deciding what to include in the local database, updating

Multi_Exit_Disc

(MED)

Optional Non-

Transitive

When a path includes multiple exit or entry points to

an AS, this value may be used as a metric to discrim-

inate between them (that is, choose one exit or entry

point over the others.)

Local_Pref

Well-Known

Discretionary

Used in communication between BGP speakers in

the same AS to indicate the level of preference for a

particular route.

Atomic_Aggregate

Well-Known

Discretionary

In certain circumstances, a BGP speaker may

receive a set of overlapping routes where one is

more specific than the other. For example, consider

a route to the network 34.15.67.0/24 and to the

network 34.15.67.0/26. The latter network is a

subset of the former, which makes it more specific. If

the BGP speaker uses the less-specific route (in this

case, 34.15.67.0/24) it sets this path attribute to a

value of 1 to indicate that this was done.

Aggregator

Optional

Transitive

Contains the AS number and BGP ID of the router

that performed route aggregation; used for

troubleshooting.

Table 136: Summary of BGP Path Attributes (Page 2 of 2)

BGP Path

Attribute

Classifica-

tion

Attribute

Type Value

Description