Table of Contents Co-existence of TCP/IP and OSI Routing Protocols without IS-IS
TCP/IP Tutorial and Technical Overview

3.4 Exterior Routing Protocols

Exterior Routing Protocols or Exterior Gateway Protocols (EGPs) are used to exchange routing information between routers in different autonomous systems.

Note: The term Exterior Routing Protocol has no abbreviation in common use, so we shall use the abbreviation EGP as is usual in TCP/IP literature.

Two EGPs are in common use

EGP is being replaced progressively by BGP. We shall discuss the two protocols in turn.

3.4.1 Exterior Gateway Protocol (EGP)

EGP is a standard protocol. Its status is recommended.

The Exterior Gateway Protocol is the protocol used for exchange of routing information between exterior gateways (not belonging to the same autonomous system).

EGP gateways may only forward reachability information for networks within their autonomous system. This routing information must be collected by this EGP gateway, usually via an Interior Gateway Protocol (IGP), used to exchange information between gateways within an autonomous system (see Figure - The ARPANET Backbone).

EGP is based on periodic polling using Hello/I Hear You message exchanges, to monitor neighbor reachability and poll requests to solicit update responses. EGP restricts exterior gateways by allowing them to advertise only those destination networks reachable entirely within that gateway's autonomous system. Thus, an exterior gateway using EGP passes along information to its EGP neighbors but does not advertise reachability information about its EGP neighbors (gateways are neighbors if they exchange routing information) outside the autonomous system. It has three main features:

To perform these three basic functions, EGP defines 10 message types:

Acquisition Request
Request a gateway to become a neighbor (or peer)
Acquisition Confirm
Positive response to acquisition request
Acquisition Refuse
Negative response to acquisition request
Cease Request
Request termination of neighbor relationship
Cease Confirm
Confirmation response to cease request
Hello
Request neighbor to respond if alive
I Hear You
Response to Hello message
Poll Request
Request network routing table
Routing Update
Network reachability information
Error
Response to incorrect message

Let us consider the EGP routing update message shown in Figure - EGP Routing Update Message.


Figure: EGP Routing Update Message

The different fields are as follows (the EGP header is not considered; refer to RFC 904 for more details):

#Int GW
Number of interior gateways (in the AS) appearing in this message.
#Ext GW
Number of exterior gateways (outside the AS) appearing in this message.
IP Source Network
The IP network number about which all reachability is measured.
GW1 IP addr
IP address (without network number) of the gateway from which the distances are measured.
#Dist.
Number of distances in the gateway block.
Dist.Da
Distance value.
#Net Da
Number of networks at a given distance (Da).
Net1 at distance Da
IP network number reachable via GW1 and at distance Da from GW1.

As indicated above, the EGP routing information messages associate a distance qualifier to each route. But, EGP does not interpret these distance values. They merely serve as an indication of the reachability or unreachability of a network (a value of 255 means that the network is unreachable). The value cannot be used to compute the shorter of two routes unless those routes are both contained within a single autonomous system. For this reason, EGP cannot be used as a routing algorithm. As a result there will be only one path from the exterior gateway to any network.

EGP is gradually being replaced by the more functional Border Gateway Protocol (BGP). For a more detailed description of BGP refer to the next section.

3.4.2 Border Gateway Protocol (BGP)

Note: There are four different versions of BGP defined. Where BGP is specified without a version number, it normally refers to BGP Version 3 unless the document pre-dates the publication of the BGP-3 definition. BGP-3 is described in this section and BGP-4 in Border Gateway Protocol Version 4 (BGP-4). BGP-1 and BGP-2, described in RFC 1105 and RFC 1163, are obsolete. Changes from BGP-1 and BGP-2 to BGP-3 are documented in Appendix 2 and 3 of RFC 1267.

3.4.2.1 Border Gateway Protocol Version 3 (BGP-3)

BGP-3 is a draft standard protocol. Its status is elective. It is described in RFC 1267.

BGP-3 is an inter-Autonomous System (inter-AS) routing protocol based on experience gained from EGP (see Exterior Gateway Protocol (EGP)). Unlike other routing protocols which communicate via packets or datagrams, BGP-3 is connection oriented; it uses TCP as a transport protocol. The well-known port number is 179. See Transmission Control Protocol (TCP) for information on TCP and port numbers.

Recall that the EGP was designed as a protocol to exchange reachability information between autonomous systems, rather than a true routing protocol. Because inter-AS routing information is not available, EGP cannot detect the presence of a loop caused by a set of EGP routers all believing that one of the others can reach another AS to which none of them is connected. A further problem with EGP has to do with the amount of information exchanged; as the number of IP networks known to the NSFNET increased, the size of the EGP Neighbor Reachability (NR) messages became quite large and the amount of time it took to process them became significant.

BGP-3 has replaced EGP in the NSFNET backbone for these reasons. However, BGP-3 as described in RFC 1268 does not require the NSFNET or any other backbone to play any central role. Compare this to the Core System role played by the ARPANET in the early days of the Internet. Instead, BGP-3 views the Internet as an arbitrary collection of autonomous systems, and it does not take account of the internal topology of an AS nor of the IGP (or possibly multiple IGPs) used within an AS.

Before giving an overview of BGP-3 operation, we shall define some terms used in BGP-3:

BGP speaker
A system running BGP.
BGP neighbors
A pair of BGP speakers exchanging inter-AS routing information. BGP neighbors may be of two types:
Internal
A pair of BGP speakers in the same autonomous system. Internal BGP neighbors must present a consistent image of the AS to their External BGP neighbors. This is explained in more detail below.
External
A pair of BGP neighbors in different autonomous systems. External BGP neighbors must be connected by a BGP connection as defined below. This restriction means that in most cases where an AS has multiple BGP inter-AS connections, it will also require multiple BGP speakers.
BGP session
A TCP session between BGP neighbors which are exchanging routing information using BGP. The neighbors monitor the state of the session by sending a keepalive message regularly (the recommended interval is 30 seconds). (9)
AS Border Router (ASBR)
A router which has a connection to multiple autonomous systems.

Note: The nomenclature for this type of router is somewhat varied. RFC 1583, which describes OSPF, uses the term AS Boundary Router. RFC 1267 and 1268, which describe BGP-3, use the terms Border Router and Border Gateway. RFC 1340, which describes the interaction between OSPF and BGP-3, uses the term AS Border Router. We shall use the last term consistently when describing both OSPF and BGP. BGP-3 defines two types of AS Border Router, depending on its topological relationship to the BGP speaker which refers to it.

internal
A next hop router in the same AS as the BGP speaker.
external
A next hop router in a different AS from the BGP speaker.
The IP address of a border router is specified as a next hop destination when BGP-3 advertises an AS path (see below) to one of its external neighbors. Next hop border routers must share a physical connection (see below) with both the sending and receiving BGP speakers. If a BGP speaker advertises an external border router as a next hop, that router must have been learned of from one of that BGP speaker's peers.
AS connection
BGP-3 defines two types of inter-AS connection.
physical connection
An AS shares a physical network with another AS, and this network is connected to at least one border router from each AS. Since these two routers share a network, they can forward packets to each other without requiring any inter-AS or intra-AS routing protocols (that is, they require neither an IGP nor an EGP to communicate).
BGP connection
A BGP connection means that there is a BGP session between a pair of BGP speakers, one in each AS, and this session is used to communicate the routes through the physically connected border routers that can be used for specific networks. BGP-3 requires that the BGP speakers must be on the same network as the physically connected border routers so that the BGP session is also independent of all inter-AS or intra-AS routing protocols. The BGP speakers do not need to be border routers, and vice versa. In fact, BGP speakers do not need to be routers: it is quite feasible for a host to provide the BGP function and to pass exterior routing information to one or more border routers with another protocol.

Note: The term BGP connection can be used to refer to a session between two BGP speakers in the same AS.

Traffic type
BGP-3 categorizes traffic in an AS as one of two types:
local
Local traffic is traffic which either originates in or terminates in that AS. That is, either the source or the destination IP address is in the AS.
transit
Transit traffic is all non-local traffic.
One of the goals of BGP is to minimize the amount of transit traffic.
AS Type
An AS is categorized as one of three types:
stub
A stub AS has a single inter-AS connection to one other AS. A stub AS only carries local traffic.
multihomed
A multihomed AS has connections to more than one other AS but refuses to carry transit traffic.
transit
A transit AS has connections to more than one other AS and will carry transit traffic. The AS may impose policy restrictions on what transit traffic will be carried.
AS number
A 16-bit number uniquely identifying an AS. This is the same AS number used by GGP and EGP.
AS path
A list of all of the AS numbers traversed by a route when exchanging routing information. Rather than exchanging simple metric counts, BGP-3 communicates entire paths to its neighbors.
Routing Policy
A set of rules constraining routing to conform to the wishes of the authority which administers the AS. Routing policies are not defined in the BGP-3 protocol, but are selected by the AS authority and presented to BGP-3 in the form of implementation-specific configuration data. Routing policies may be selected by the AS authority in whatever way that authority sees fit. For example:

It can be seen from the definitions above that a stub AS or a multihomed AS has the same topological properties as an AS in the ARPANET architecture: that is it never acts as an intermediate AS in an inter-AS route. In the ARPANET architecture, EGP was sufficient for such an AS to exchange reachability information with its neighbors, and this remains true with BGP-3. Therefore, a stub AS or a multihomed AS may continue to use EGP (or any other suitable protocol) to operate with a transit AS. However, RFC 1268 recommends that BGP-3 is used instead of EGP for these types of AS because it provides an advantage in bandwidth and performance. Additionally, in a multihomed AS, BGP-3 is more likely to provide an optimum inter-AS route than EGP, since EGP only addresses reachability and not ``distance''.

Path Selection

Each BGP speaker must evaluate different paths to a destination from the border router(s) for an AS connection, select the best one that complies with the routing policies in force and then advertise that route to all of its BGP neighbors at that AS connection.

BGP-3 is a vector-distance protocol but, unlike traditional vector-distance protocols such as RIP where there is a single metric, BGP-3 determines a preference order by applying a function mapping each path to a preference value and selects the path with the highest value. The function applied is generated by the BGP-3 implementation according to configuration information.

Where there are multiple viable paths to a destination, BGP-3 maintains all of them but only advertises the one with the highest preference value. This approach allows a quick change to an alternate path should the primary path fail.

Routing Policies

RFC 1268 includes a recommended set of policies for all implementations:

AS Consistency

BGP-3 requires that a transit AS present the same view to every AS using its services. If the AS has multiple BGP speakers, they must agree on two aspects of topology: intra-AS and inter-AS. Since BGP-3 does not deal with intra-AS routing at all, a consistent view of intra-AS topology must be provided by the interior routing protocol(s) employed in the AS. Naturally, a protocol such as OSPF (see Open Shortest Path First Protocol (OSPF) Version 2) or Integrated IS-IS (see OSI Intermediate System to Intermediate System (IS-IS)) which implements synchronization of router databases lends itself well to this role. Consistency of the external topology may be provided by all BGP speakers in the AS having BGP sessions with each other, but BGP-3 does not require that this method be used, only that consistency be maintained.

Routing Information Exchange

BGP-3 only advertises routes that it uses itself to its neighbors. That is, BGP-3 conforms to the normal Internet hop-by-hop paradigm, even though it has additional information in the form of AS paths and theoretically could be capable of informing a neighbor of a route it would not use itself.

When two BGP speakers form a BGP session, they begin by exchanging their entire routing tables. Routing information is exchanged via UPDATE messages (see below for the format of these messages). Since the routing information contains the complete AS path to each listed destination in the form of a list of AS numbers in addition to the usual reachability and next hop information used in traditional vector distance protocols, it can be used to suppress routing loops and to eliminate the counting-to-infinity problem found in RIP. After BGP neighbors have performed their initial exchange of their complete routing databases, they only exchange updates to that information.

BGP-3 Message formats

All BGP-3 messages have a common basic format. They vary between 19 and 4096 bytes in length, are transmitted over TCP and are processed in their entirety (that is, a BGP speaker does not begin to process the message until it has received the whole message). Each message has a header shown in Figure - BGP-3 Header.


Figure: BGP-3 Header

Marker
A value which can be predicted by the receiver, used for authentication and for identifying loss of synchronization. It is set to ``all ones'' when the Authentication Code is 0 (see below).
Length
Total length of the message including the header, in bytes. The message must not be padded since the length is used to calculate the length of the last field of the message in many cases.
type
An 8-bit unsigned value.
1
OPEN (10)
2
UPDATE
3
NOTIFICATION
4
KEEPALIVE

OPEN messages are used to initiate the BGP-3 session. The format of an OPEN message is shown in Figure - BGP-3 OPEN Message.


Figure: BGP-3 OPEN Message

Version
3 for BGP-3 (1 byte)
My Autonomous System
The AS number of the sender (2 bytes)
Hold time
The maximum length of time in seconds that may elapse between the receipt of successive KEEPALIVE and/or UPDATE and/or NOTIFICATION messages (2 bytes).
BGP Identifier
A unique 32-bit number identifying the BGP speaker. It is the IP address of any one of the speaker's interfaces. The same number is used for all interfaces and all BGP neighbors.
Authentication Code
Defines the interpretation of the Authentication Data (1 byte). BGP-3 defines no authentication codes other than zero (for no authentication).
Authentication Data
Dependent on the Authentication Code. The length is variable and is inferred from the message length. For authentication code zero, the data is omitted (it has a length of zero).

UPDATE messages are used to transfer routing information. The format of an UPDATE message is shown in Figure - BGP-3 UPDATE Message.


Figure: BGP-3 UPDATE Message

Attributes Length
Length of the path attributes field in bytes (2 bytes).
Path Attributes
Each path attribute is a triple: <attribute type, attribute length, attribute value> where:
attribute type
is a 2-byte field, consisting of an attribute flag byte and a 1-byte attribute type code. The bits in the flag byte are:
X'80'
Optional attribute. If set, the attribute is optional, otherwise it is well-known. Well-known attributes are those that all BGP-3 implementations must handle. There are two types: mandatory attributes must be included in every UPDATE message, discretionary attributes may be omitted from UPDATE messages.

Optional attributes are those that BGP-3 implementations are not required to recognize. If a receiving BGP speaker does not recognize the attribute, it should handle it according to the transitive bit. BGP speakers are allowed to make appropriate updates to attributes in messages which they receive from peers before relaying them to other BGP speakers.

X'40'
Transitive attribute. This bit must be set if the attribute is mandatory. For optional attributes, if this bit is set, the attribute is transitive, otherwise it is non-transitive. An unrecognized transitive optional attribute must be passed on to other BGP peers after setting the partial bit. An unrecognized non-transitive optional attribute must be quietly discarded. BGP speakers may add transitive optional attributes to the path attributes in an UPDATE message before relaying it to a peer.
X'20'
Partial attribute. This bit indicates that a transitive optional attribute was passed on by a BGP speaker that did not recognize it or was added by a BGP speaker other than the originator of the message. In all other cases it must be zero.
X'10'
Extended length. The attribute length field is two bytes if this bit is set and one byte if not. The low order four bits must be zero and must be ignored by the recipient.
Refer to RFC 1267 for more details of how these bits are interpreted.

The attribute type codes defined are shown in Table - BGP-3 UPDATE Path Attribute Type Values.


Table: BGP-3 UPDATE Path Attribute Type Values

ORIGIN
The method by which this path was learned by the originating AS.
0
IGP -- the networks listed are within the originating AS.
1
EGP -- the networks listed are outside the originating AS and the reachability information was learned from EGP.
2
INCOMPLETE -- the networks listed were learned by some other means.
AS_PATH
The 2-byte AS numbers of each AS in the path to the destination network(s). The number of hops in the path can be calculated by dividing the attribute length by 2.
NEXT_HOP
The IP address of the border router that is the next hop on the path to the listed network(s). This field is ignored for internal BGP connections.
UNREACHABLE
Previously advertised routes have now become unreachable.
INTER-AS METRIC
This value may be used to choose between multiple paths to one AS. If all other factors are equal, the path with the lower metric is to be preferred. This value may be sent to a BGP speaker in a neighboring AS, and if received over an external BGP connection, it may be propagated over internal BGP connections. A BGP speaker may not relay an INTER-AS METRIC in an UPDATE message which it receives from a peer to an external peer.
attribute length
One or two byte length (depending on the value of the extended length bit).
attribute value
Dependent upon the value of the attribute type code.
Each attribute can be specified only once. The end of the attributes is determined from the path attributes length field.
Network 1
The 32-bit network number of the first network described by the preceding path attributes. Subnets and hosts are explicitly disallowed.
Network n
The network number of the last network described by the preceding path attributes. The number of networks can be calculated by subtracting the lengths of the BGP-3 header and the path attributes information from the length of the message and dividing by 4.

NOTIFICATION messages are used to inform the neighbor of an error. The BGP connection is terminated after the message is sent. The format of a NOTIFICATION message is shown in Figure - BGP-3 NOTIFICATION Message.


Figure: BGP-3 NOTIFICATION Message

Code
One byte indicating the type of error. The following codes are defined:
1
Message Header Error
2
OPEN Message Error
3
UPDATE Message Error
4
Hold Timer Expired
5
Finite State Machine Error
6
Cease
Subcode
A single byte providing more information about the nature of the error. The value 0 (unspecific) indicates that no more appropriate subcode exists. In addition the following subcodes are defined:
Message Header Error Subcodes
1
Connection Not Synchronized
2
Bad Message Length
3
Bad Message Type
OPEN Message Error Subcodes
1
Unsupported Version Number
2
Bad Peer AS
3
Bad BGP Identifier
4
Unsupported Authentication Code
5
Authentication Failure
UPDATE Message Error Subcodes
1
Malformed Attribute List
2
Unrecognized Well-known Attribute
3
Missing Well-known Attribute
4
Attribute Flags Error
5
Attribute Length Error
6
Invalid ORIGIN Attribute
7
AS Routing Loop
8
Invalid NEXT_HOP Attribute
9
Optional Attribute Error
10
Invalid Network Field
Data
Variable length information dependent upon the code and subcode which can be used to diagnose the cause of the error. The length can be calculated by subtracting 21 from the total message length.

KEEPALIVE messages are used to ensure that the connection is still working. The KEEPALIVE message consists of just the header.

References

A detailed description of BGP-3 may be found in the following RFCs:

3.4.2.2 BGP OSPF Interaction

There is a proposed standard protocol with a status of elective defining how BGP-3 (an exterior routing protocol) should interact with OSPF (an interior routing protocol). Any host or router which dynamically exchanges information between BGP-3 and OSPF should adhere to this standard. It is described in RFC 1654 - BGP OSPF Interaction.

BGP OSPF interaction covers the conversion from OSPF fields in an External Links Advertisement to BGP path attributes, and vice versa, for three properties of a route definition.


Table: BGP OSPF Attribute-Field Mapping

The standard defines how these mappings should be done and what restrictions there are on what may be done automatically. Please refer to the RFC for more information.

3.4.2.3 Border Gateway Protocol Version 4 (BGP-4)

BGP-4 is a proposed standard protocol. Its status is elective. It is described in RFC 1654. The main changes are to support supernetting or Classless Inter-Domain Routing (CIDR) which is described in Classless Inter-Domain Routing (CIDR). In particular BGP-4 supports IP prefixes and path aggregation. Because CIDR is radically different from the normal Internet routing architecture, BGP-4 is incompatible with BGP-3. However, BGP does define a mechanism for two BGP speakers to negotiate a version which they both understand. This is done using the OPEN message. Therefore, it is possible to implement ``multi-lingual'' BGP speakers which will allow inter-operation of BGP-3 and BGP-4.

The following items identify the major changes between BGP-3 and BGP-4.

References

A detailed description of BGP-4 can be found in the following RFCs:

3.4.3 IP Routing Protocols in IBM TCP/IP Products

The routed program which supports RIP is implemented on the following IBM TCP/IP platforms:

  • MVS
  • VM
  • AIX
  • OS/2
  • DOS
    • The routed program is not implemented on OS/400.

    The gated program which supports RIP, Hello, EGP and BGP is implemented on AIX. On AIX 4.1, gated additionally supports OSPF Version 2 and RIP Version 2.

    The IBM 6611 Network Processor implements RIP, RIP Version 2, Hello, OSPF, EGP and BGP.

    The IBM 2210 Nways Network Processor implements RIP, OSPF and EGP.

    Table of Contents Application Protocols