Charles M. Kozierok The TCP-IP Guide

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

that database, and then choosing what routes to send from it to peer devices. In BGP, a

mechanism called the Decision Process is responsible for these tasks. It consists of three

overall phases:

1. Phase 1: Each route received from a BGP speaker in a neighboring AS is analyzed

and assigned a preference level. The routes are then ranked according to preference

and the best one for each network advertised to other BGP speakers within the auton-

omous system.

2. Phase 2: The best route for each destination is selected from the incoming data based

on preference levels, and used to update the local routing information base (the Loc-

RIB).

3. Phase 3: Routes in the Loc-RIB are selected to be sent to neighboring BGP speakers

in other ASes.

Criteria for Assigning Preferences to Routes

Obviously, if a BGP speaker only knows of a single route to a network, it will install and use

that route (assuming there are no problems with it). The assigning of preferences amongst

routes only becomes important when more than one route has been received by a BGP

speaker for a particular network. Preferences can be determined based on a number of

different criteria. Just a few typical ones include:

☯ The number of autonomous systems between the router and the network (fewer

generally being better).

☯ The existence of certain policies that may make certain routes unusable; for example,

a route may pass through an AS that this AS is not willing to trust with its data.

☯ The origin of the path—that is, where it came from.

In the case where a set of routes to the same network are all calculated to have the same

preference, a “tie-breaking” scheme is used to select from among them. Additional logic is

used to handle special circumstances, such as the case of overlapping networks (see the

description of the Atomic_Aggregate path attribute for an example of this).

The selection of routes for dissemination to other routers in Phase 3 is based on a rather

complex algorithm that I cannot do justice here. Route advertisement is guided by the

routing policies we discussed earlier in this section. Different rules are used to select routes

for advertising to internal peers compared to external peers.

Key Concept: The method used by a BGP speaker to determine what new routes to

accept from its peers and what routes to advertise back them is called the BGP

Decision Process. It is a complex algorithm in three phases that involves the compu-

tation of the best route based on both pre-existing and incoming path information.

Limitations on BGP's Ability to Select Efficient Routes

When considering the route selection process, it's very important to remember that BGP is

a routing protocol that operates at the inter-autonomous-system level. Thus, routes are

chosen between ASes and not at the level of individual routers within an AS.So, for

example, when BGP stores information about the path to a network, it stores it as a

sequence of autonomous systems, not a sequence of specific routers. BGP cannot deal

with individual routers in an AS because by definition, the details of what happens within an

AS are supposed to be “hidden” from the outside world. It doesn't know the structure of

ASes outside its own.

However, this has an important implication for how BGP selects routes: BGP cannot

guarantee that it will pick the fastest, lowest-cost route to every network. It can select a

route that minimizes the number of ASes that lie between itself and a particular network, but

of course ASes are not all the same. Some ASes are large and consist of many slow links,

while others are small and fast. Choosing a route through two of the latter type of AS will be

better than choosing a route through one of the former, but BGP can't know that. Policies

can be used to influence AS selection to some extent, but in general, since BGP doesn't

know what happens in an AS, it cannot guarantee the efficiency of a route overall. (Inciden-

tally, this is the reason why there is no general “cost” or “distance” path attribute in BGP.)

Key Concept: As an exterior routing protocol, BGP operates at the autonomous

system level. Its routes are calculated based on paths between ASes, not individual

routers. Since BGP, by definition, does not know the internal structure of routers

within an AS, it cannot know for certain the cost to send a datagram across a given AS. This

in turn means that BGP cannot always guarantee that it will select the absolute lowest-cost

route between any two networks.

Originating New Routes and Withdrawing Unreachable Routes

Naturally, a facility exists to allow BGP speakers to originate new routes to networks. A

BGP speaker may obtain knowledge about a new route from an interior routing protocol on

an AS to which it is directly attached and choose to share this information with other ASes.

It will create a new entry in its RIB for this network and then send information about it out to

other BGP peers.

BGP also includes a mechanism for not only advertising routes it can reach, but those it

cannot. The latter are called unfeasible or withdrawn routes, and are mentioned in Update

messages as needed to indicate that a router can no longer reach the specific network.

BGP General Operation and Messaging

In the previous topics we have seen how BGP stores information about routes and uses it

to determine paths to various networks. Let's now take a high-level look at how BGP

operates in general terms. Like many other protocols covered in this Guide, BGP's

operation can be described primarily in the form of messaging. The use of messages is the

means by which route information is communicated between BGP peers. This eventually

allows knowledge of how to reach networks to spread throughout the entire internetwork.

Speaker Designation and Connection Establishment

Before messaging can begin, BGP speakers must be designated, and then linked together.

The BGP standard does not specify how neighboring speakers are determined; this must

be done outside the protocol. Once accomplished, ASes are connected into a BGP-enabled

internetwork. Topological linking provides the physical connection and the means for

datagrams to flow between ASes. At this point the dance floor is prepared, but nobody is

dancing; BGP can function but isn't yet in operation.

BGP operation begins with BGP peers forming a transport protocol connection. BGP uses

TCP for its reliable transport layer, so the two BGP speakers establish a TCP session that

remains in place during the course of the subsequent message exchange. When this is

done, each BGP speaker sends a BGP Open message. This message is like an “invitation

to dance”, and begins the process of setting up the BGP link between the devices. In this

message, each router identifies itself and its autonomous system, and also tells its peer

what parameters it would like to use for the link. This includes an exchange of authenti-

cation parameters. Assuming that each device finds the contents of its peer's Open

message acceptable, it acknowledges it with a Keepalive message and the BGP session

begins.

Under normal circumstances, most BGP speakers will maintain simultaneous sessions with

more than one other BGP speaker, both within its own AS and outside the AS. Links

between ASes are of course what enable BGP routers to learn how to route through the

internetwork. Links within the AS are important to ensure that each BGP speaker in the AS

maintains consistent information.

Route Information Exchange

Assuming the link is initialized, the two peers begin an ongoing process of telling each other

what they know about networks and how to reach them. Each BGP speaker encodes infor-

mation from its Routing Information Bases (RIBs) into BGP Update messages. These

messages contain lists of known network addresses, as well as information about paths to

various networks, described in the form of path attributes. This information is then used for

the route determination as described in the preceding topic.

When a link is first set up between two peers, they ensure complete information is held by

each router by exchanging their complete routing tables. Subsequently, Update messages

are sent that contain only incremental updates about routes that have changed. Exchanging

only updated information as needed reduces unnecessary bandwidth on the network,

making BGP more efficient than it would be if it sent full routing table information on a

regular basis.

Connectivity Maintenance

The TCP session between BGP speakers can be kept open for a very long time, but

Updates need to be sent only when changes occur to routes, which are usually infrequent.

This means many seconds may elapse between the transmission of Update messages. To

ensure that the peers maintain contact with each other, they both send Keepalive

messages on a regular basis when they don’t have other information to send. These are

null messages that contain no data and just tell the peer device “I'm still here”. These

messages are sent infrequently—no more often than one per second—but regularly

enough that the peers won't think the session was interrupted.

Error Reporting

The last type of BGP message is the BGP Notification message. This is an error message;

it tells a peer that a problem occurred and describes the nature of the error condition. After

sending a BGP Notification message, the device that sent it will terminate the BGP

connection between the peers. A new connection will then need to be negotiated, possibly

after the problem that led to the Notification has been corrected.

Key Concept: BGP is implemented through the exchange of four different message

types between BGP speakers. A BGP session begins with a TCP connection being

established between two routers and each sending an Open message to the other.

BGP Update messages are the primary mechanism by which routing information is

exchanged between devices. Small BGP Keepalive messages are used to maintain

communication between devices between periods that they need to exchange information.

Finally, Notification messages are used for problem reporting.

For more details on the four BGP message types and a description of the format used by

each, refer to the detailed BGP operation section.

BGP Detailed Messaging, Operation and Message Formats

The previous section described the concepts and general operation of the Border Gateway

Protocol (BGP). To get a better understanding of exactly how BGP works, it is helpful to

take a deeper look at its four different message types and how they are used. As we do this,

we can examine the fields in each message type, to help us comprehend not just the way

that messaging is accomplished, but the way that routing data is actually communicated.

In this section I provide a comprehensive description of the communication that takes place

between BGP speakers by providing details on BGP message types, how they are used,

and the data elements they contain. I begin with a description of common attributes of BGP

message generation and transport, and the general format used for all BGP messages. I

then provide a detailed description of each of the four BGP message types: Open, Update,

Keepalive and Notification messages.

Background Information: If you have not yet already done so, you should read

the high-level description of general BGP operation and messaging, which shows

how these messages fit together.

BGP Message Generation and Transport, and General Message Format

Each router running BGP generates messages to implement the various functions of the

protocol. Some of these messages are created on a regular basis by the BGP software

during the course of its normal operation. These are generally controlled by timers that are

set and count down to cause them to be sent. Other messages are sent in response to

messages received from BGP peers, possibly after a processing step.

BGP Message Transport

BGP is different from most other routing protocols in that it was designed from the start to

operate using a reliable method of message delivery. The Transmission Control Protocol

(TCP) is present in the software of every IP router, making it the obvious choice for reliable

data communication in a TCP/IP internet, and that's what BGP uses. Routing protocols are

usually considered part of layer three, but this one runs over a layer four protocol, making

BGP a good example of why architectural models are best used only as a guideline.

TCP provides numerous advantages to BGP by taking care of most of the details of session

setup and management, allowing BGP to focus on the data it needs to send. TCP takes

care of session setup and negotiation, ensuring that messages are received and acknowl-

edged, flow control, congestion-handling and any necessary retransmissions of lost

messages. BGP uses well-known TCP port 179 for connections.

BGP General Message Format

The use of TCP also has an interesting impact on the way BGP messages are structured.

One thing that stands out when you look at the BGP message format (as we will see

shortly) is that a BGP message can have an odd number of bytes. Most routing protocols

are sized in units of 4 or 8 bytes, but since TCP sends data as a stream of octets there is no

need for BGP messages to break on a 32-bit or 64-bit boundary. The other impact is the

need of a special Marker field to help ensure that BGP messages can be differentiated from

each other in the TCP stream (more about this in a moment).

Like most messaging protocols, BGP uses a common message format for each of its four

message types. Each BGP message is conceptually divided into a header and a body

(called the data portion in the BGP standard). The header has three fields and is fixed in

length at 19 bytes. The body is variable in length, and in fact is omitted entirely in Keepalive

messages, since it is not needed for them.

The general format for all BGP message types is shown in Table 137 and Figure 192.

The Marker Field, Message Synchronization and Authentication

The Marker field is the most interesting one in the BGP message format, and as mentioned

in the table is used for both synchronization and authentication. BGP uses a single TCP

session to send many messages in a row. TCP is a stream-oriented transport protocol

Table 137: BGP General Message Format

Field Name

Size

(bytes)

Description

Marker 16

Marker: This large field at the start of each BGP message is used for

synchronization and authentication.

Length 2

Length: The total length of the message in bytes, including the fields of the

header. The minimum value of this field is 19 for a Keepalive message; it

may be as high as 4,096.

Type 1

Message Body /

Data Portion

Variable

Message Body / Data Portion: Contains the specific fields used to

implement each message type, for Open, Update and Notification

messages.

Type: Indicates the BGP message type:

Type Value (Decimal) Message Type

1 Open

2 Update

3 Notification

4 Keepalive

which just sends bytes across the link without any knowledge of what the bytes represent.

This means that the protocol using TCP is responsible for deciding where the line is drawn

between data units, in this case BGP messages.

Normally, the Length field tells each BGP device where to draw the line between the end of

one message and the start of the next. However, it is possible that due to various conditions

a device might lose track of where the message boundary is. The Marker field is filled with a

recognizable pattern that clearly marks the start of each message, to keep BGP peers

synchronized.

Before a BGP connection is established, the Marker field is just filled with all ones. Thus,

this is the pattern used for Open messages. Once a BGP session is negotiated, if

agreement is reached on an authentication method between the two devices, the Marker

field takes on the additional role of authentication. Instead of looking for a Marker containing

all ones, BGP devices look for a pattern generated using the agreed-upon authentication

method. Detection of this pattern simultaneously synchronizes the devices and ensures that

messages are authentic.

In extreme cases, BGP peers may be unable to maintain synchronization, and if so, a Notifi-

cation message is generated and the session is closed. This will also happen if the Marker

field contains the wrong data when authentication is enabled.

Figure 192: BGP General Message Format

Marker

(128 bits)

Length Type

Message Body

4 8 12 16 20 24 28 320

Key Concept: All four BGP message types use a general message format that

contains three fixed header fields—Marker, Length and Type—and room for a

message body that differs for each message type. The large Marker field is used to

denote the start of a new BGP message, and is also used to facilitate the BGP authenti-

cation method.

BGP Connection Establishment: Open Messages

Before a BGP session can be used to exchange routing information, a connection must first

be established between BGP peers. This process begins with the creation of a TCP

connection between the devices. Once this is done, the BGP devices will attempt to create

a BGP session by exchanging BGP Open messages.

The Open message has two main purposes. The first is identification and initiation of a link

between the two devices; it allows one peer to tell the other “I am a BGP speaker named X

on autonomous system Y, and I want to start exchanging BGP information with you”. The

second is negotiation of session parameters. These are the terms by which the BGP

session will be conducted. One important parameter negotiated using Open messages is

the method that each device wants to use for authentication. The importance of BGP

means that authentication is essential, to avoid bad information or a malicious person from

disrupting routes.

Each BGP receiving an Open message processes it. If its contents are acceptable,

including the parameters the other device wants to use, it responds with a Keepalive

message as an acknowledgment. Each peer must send an Open and receive a Keepalive

acknowledgment for the BGP link to be initialized. If either is not willing to accept the terms

of the Open, the link is not established. In that case, a Notification message may be sent to

convey the nature of the problem.

BGP Open Message Format

The specific format for BGP Open messages can be found in Table 138 and Figure 193.

Table 138: BGP Open Message Format (Page 1 of 2)

Field Name

Size

(bytes)

Description

Marker 16

Marker: This large field at the start of each BGP message is used for

synchronization and authentication. See the discussion of the BGP general

message format for details.

Length 2

Length: The total length of the message in bytes, including the fields of the

header. Open messages are variable in length.

Type 1 Type: BGP message type, value is 1 for Open messages.

Version 1

Version: Indicates the BGP version the sender of the Open message is

using. This field allows devices to reject connections with devices using

versions they may not be capable of understanding. The current value is 4,

for BGP-4, and is used by most, if not all, current BGP implementations.

My Autonomous

System

My Autonomous System: Identifies the autonomous system number of

the sender of the Open message. AS numbers are centrally managed

across the Internet in a manner similar to how IP addresses are

administered.

Hold Time 2

Hold Time: The number of seconds that this device proposes to use for

the BGP hold timer, which specifies how long a BGP peer will allow the

connection to be left silent between receipt of BGP messages. A BGP

device may refuse a connection if it doesn't like the value that its peer is

suggesting; usually, however, the two devices agree to use the smaller of

the values suggested by each device.

The value must be at least 3 seconds, or 0. If 0, this specifies that the hold

timer is not used. See the Keepalive message discussion for more on how

the hold timer is used.

BGP Identifier 4

BGP Identifier: Identifies the specific BGP speaker. Recall that IP

addresses are associated with interfaces, not devices, so each router will

have at least two IP addresses. Normally the BGP identifier is chosen as

one of these addresses. Once chosen, this identifier is used for all BGP

communications with BGP peers. This includes BGP peers on the interface

from which the identifier was chosen, and also BGP peers on other inter-

faces as well. So, if a BGP speaker with two interfaces has addresses IP1

and IP2, it will choose one as its identifier and use it on both of its

interfaces.

Opt Parm Len 1

Optional Parameters Length: The number of bytes used for Optional

Parameters (see below). If 0, no optional parameters are in this message.

Optional

Parameters

Variable

Table 138: BGP Open Message Format (Page 2 of 2)

Field Name

Size

(bytes)

Description

ona

arame

ers:

All

ows

pen message

o commun

e any

number of extra parameters during BGP session setup. Each parameter is

encoded using a rather standard “type / length / value” triple, as follows:

Subfield

Name

Size

(bytes)

Description

Parm Type 1

Parameter Type: The type of optional parameter.

At present, only one value is defined, 1, for

authentication Information.

Parm Length 1

Parameter Length: Specifies the length of the

Parameter Value subfield (thus, this value is the

length of the entire parameter less 2).

Parm Value Variable

Parameter Value: The value of the parameter

being communicated.

BGP Open messages currently use only one optional parameter: Authentication Infor-

mation. Its Parameter Value subfield contains a one-byte Authentication Code sub-subfield,

which specifies the type of authentication a device wishes to use. Following this is a

variable-length Authentication Data sub-subfield. The Authentication Code specifies how

authentication is to be performed, including the meaning of the Authentication Data field,

and the manner in which Marker fields are to be calculated.

Key Concept: BGP sessions begin with each peer in a connection sending the other

a BGP Open message. The purpose of this message is to establish contact between

devices, identify the sender of the message and its autonomous system, and

negotiate important parameters that dictate how the session will be conducted.

Figure 193: BGP Open Message Format

Marker

(128 bits)

Length Type = 1 Version

My Autonomous System Hold T ime

BGP Identifier

Optional Parameters

Length

Parameter Type #1 Parameter Length #1

Parameter Value #1

Parameter Type #N Parameter Length #N

Parameter Value #N

4 8 12 16 20 24 28 320

...