Juha Korhonen
Department of Computer Science
Helsinki University of Technology
Tik-110.551 Internetworking Seminar
koju@cc.hut.fi
1. Introduction
In the early 1980's, the Internet was only a restricted network called
ARPANET. It was developed by the U.S. Defense Advanced Research Projects
Agency (DARPA). It was used to interconnect the computer networks
associated with a small number of research and university sites. Those
local area networks were connected to Arpanet by gateways. When the
Internet started to grow strongly, it became necessary for it to have some kind
of hierarchical structure. The Internet was thus split into a set of
autonomous systems (AS) [1].
The Internet is made up of a number of separately managed and run internets.
Each internet is treated as being an autonomous system with its own internal
routing algorithms and management authority.
An autonomous system is a set of interior gateways and networks under the
same technical administration. So the minimal autonomous system is composed
of exactly one router directly connecting one local network to the Internet
[1].
Each AS is identified by a 16-bit "AS-number". Interior gateways are used within an autonomous system, and the corresponding routing protocol is the Interior Gateway Protocol (IGP), such as RIP or OSPF.
One or more gateways of each autonomous system function as exterior gateways for that system. Within the autonomous system, these communicate with other interior gateways using the IGP for that system. Exterior gateways are used to connect an autonomous system to the core network.
These Autonomous Systems must exchange information in order to manage the connectivity. For this purpose an internet wide standard was designed: the Exterior Gateways Protocol (EGP).
2. EGP - Exterior Gateway Protocol
EGP was designed with a simple hierarchical topology in mind. A stub AS
should be connected to the backbone, which in 1983 was the Arpanet.
In the late 1980's, the Arpanet was replaced by NSFnet as the core backbone
[1]. NSFnet connected regional networks, which in turn
connected university campuses and research organizations.
Figure 2.1. General internet architecture [2]
The purpose of the Exterior Gateway Protocol (EGP) is to enable one or
more autonomous systems to be used as a transport media for traffic
originating in some other autonomous system and destined for yet another.
EGP organizes the exchange of reachability information between two adjacent
autonomous systems.
The three main functions associated with the EGP are:
2.1. Neighbors
Before exchanging any routing information the adjacent routers must agree
to become "neighbors" for EGP. Two gateways are neighbors if they are
connected by the some communications medium whose internal structure is
transparent to them [3].
Becoming neighbors means that each AS will eventually agree to relay the adjacent AS's traffic.
2.2. Exchanging Information Through EGP
The routing tables inside the AS, maintained by the IGP, should include
entries covering all possible Internet destinations. Routers that belong
to the AS must get the information about exterior networks through a
dialogue with exterior gateways, which are entry points in adjacent
autonomous systems. The role of the EGP is to exchange this reachability
information, which is naturally a set of connected networks
[1].
2.2.1. The EGP messages
The neighbor acquisition, neighbor reachability and network reachability
procedures are performed by exchanging EGP messages. All these messages
are carried inside IP datagrams: the protocol number 8 has been assigned
to EGP. The messages associated with each function are shown in table 2.1.
| Function | EGP Message | Meaning |
|---|---|---|
| Neighbor Acquisition | Acquisition Request | Request a gateway to become a neighbor |
| Neighbor Acquisition | Acquisition Reply | Gateway agrees to become a neighbor |
| Neighbor Acquisition | Acquisition Refuse | Gateway refuses |
| Neighbor Acquisition | Cease Request | Request termination of a neighbor relationship |
| Neighbor Acquisition | Cease Acknowledgment | Confirms break-up of relationship |
| Neighbor Reachability | Hello | Requests neighbor to confirm a previously established relationship Confirms relationship |
| Neighbor Reachability | I-Hear-You (I-H-U) | Confirms relationship |
| Network Reachability | Poll Request | Requests network reachability update |
| Network Reachability | Routing Update | Network reachability information |
| Error Response | Error | Response to any incorrect request message |
Table 2.1. EGP message types and their meanings
All these request-response messages start with the same 8-byte header [1]. The header carries a version number, a checksum, the number of the autonomous system to which the sending router belongs, and a sequence number. The type-field identifies the subprotocol; neighbor acquisitions messages carry the type 3, neighbor reachability messages carry the type 5 and network reachability messages carry either 1 (for updates) or 2 (for polls).
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | EGP Version | Type | Code | Info | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | Autonomous System # | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence # | Data - - - +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2.2. EGP Message format [1]
2.2.2. Neighbor acquisition
The neighbor acquisition is a very simple two-way handshake.
A gateway that wishes to initiate neighbor acquisition with another gateway,
sends it a Neighbor Acquisition Request. This message should be repeatedly
transmitted (at a reasonable rate, typically once every 30 seconds) until a
Neighbor Acquisition Reply is received [3]. The Request
will contain an identification number which is copied into the reply so that
the request and reply can be matched up.
A gateway receiving a Neighbor Acquisition Request must determine whether it wishes to become a neighbor of the source of the Request. If not, it may respond with a Neighbor Acquisition Refuse message, optionally specifying the reason for refusal. Otherwise, it should send a Neighbor Acquisition Reply message.
If a gateway wishes to cease being a neighbor of a particular exterior
gateway, it sends a Neighbor Cease message. A gateway receiving a Neighbor
Cease message should always respond with a Neighbor Cease Acknowledgment.
2.2.3. Neighbor Reachability
It is important for a gateway to keep real-time information of the
reachability of its neighbors. If a gateway concludes that a particular
neighbor cannot be reached, it should cease forwarding traffic to that
gateway. To make that determination, a Neighbor Reachability procedure
is needed. The EGP protocol provides two messages types for this purpose
- a "Hello" message and an "I Heard You" (I-H-U) message
[3].
When a Hello message is received from a neighbor, an I Heard You must be returned to that neighbor "immediately" [3]. The delay between receiving a Hello and returning an I Heard You should never be more than a few seconds.
The Hello's carry a sequence number, which is repeated in the I-H-U. Both messages carry the type 5. Hello's are identified by the code 0, and I Hear Yous by the code 1.
Choosing the frequency of the Hello's is indeed a balance between two inconveniences - if the frequency is too low, link status will not be detected in due time, and if it is too high, one will end up consuming too much network and processing resources. A typical Hello-interval is 30 seconds [1].
2.2.4. Network Reachability
The purpose of the network reachability procedure is to exchange the list
of networks that can be reached through each neighbor.
The actual exchange of routing information is carried out by one of the
gateways sending a Poll Request message to the other gateway asking it for
the list of networks (netids) that are reachable via that gateway and their
distances from it. A typical Poll Request -interval is 2 minutes
[1].
The response to the Poll Request message is a Routing Update message which
contains a list of reachable networks. If any request message is incorrect,
an Error message is returned as a response with an appropriate reason code
[2].
Polling messages are identified by the type number 2. The code field is
set to 0 and the information field is not used [3].
2.3 Routing Tables
When each exterior gateway is first initialized, it is given the unique
identity of the autonomous system which it is attached to. It also receives
the contents of a routing table, known also as the reachability table, which
enables it to communicate with all the other exterior gateways via the core
network [2].
Each exterior gateway, through its local routing table, knows about the netids within that system and their distances from that gateway. The EGP protocol carries a single integer varying between 0 and 255, which indicates the distance from given exterior gateway [1].
A router can advertise that an IP network is reachable through a given router. That means that there is an internal path within the autonomous system toward this destination, and that the management of the AS agrees to relay packets on this path.
There are four conditions that must be satisfied before a route through a neighbor to a given destination can be validated and the information inserted to the routing table [1]:
An exterior router that has learned of a path toward a given network
should update the AS routing tables, either by inserting an exterior
link in the OSPF database or by adding an entry in the RIP distance vector
[1].
Routes obtained through EGP should be removed from the routing tables, if
[1]:
2.4 The Limits of the EGP
Since the EGP was designed in 1983, the Internet has been growing
rapidly. When the EGP was designed there was only a few networks connected
to the Internet. By the year 1991 there was already 2100 networks, and
since then the growth has been even faster: by February 1994 the Internet
had grown to more than 25 000 networks [6].
Commercial networks and other diverse customers has been connected to the
Internet, and that has also caused new requirements for the exterior
gateway protocol.
EGP was designed to support a simple hierarchical topology, and certainly
not for a complex meshed topology, where the unique backbone would be
replaced by many competing commercial providers.
"Operational experience with EGP showed that it is highly inadequate for
the current Internet." [7] The three major requirements
were: the need to avoid false information, the need to allow more complex
topologies and the need to enable some form of policy routing
[1].
Because of these weaknesses, EGP is currently being phased out of the Internet, and is being replaced by other exterior gateway protocols, such as the Border Gateway Protocol (BGP).
3. BGP - Border Gateway Protocol
The Border Gateway Protocol (BGP) is an inter-autonomous system routing
protocol designed for TCP/IP internets, and is the recommended
protocol today for exchanging information between autonomous systems.
The first version of BGP was published in 1989. Since then, there have
been three new releases and the newest is BGP-4, published in 1994.
The Border Gateway Protocol is built on experience gained with EGP and EGP usage in the NSFnet Backbone [4]. Many of the concepts that were developed for EGP are used in BGP. For example, the division of the Internet into autonomous systems and the separation of the routing functions between interior and exterior gateway protocols.
Rather than trying to predict the future, and overload BGP with a variety of functions that may (or may not) be needed, the designers of BGP took a different approach. The protocol contains only the functionality that is essential, while at the same time it provides flexible mechanisms within the protocol itself that allow to expand its functionality [7].
The primary function of a BGP speaking system is to exchange network reachability information with other BGP systems. This network reachability information includes information on the list of Autonomous Systems (ASs) that reachability information traverses.
3.1. Path Vectors
Probably the most important innovation within the BGP is the path vector
concept which enables loop prevention in complex topologies.
In BGP, each routing update will carry the full list of AS's traversed between the source and the destination [1]. A loop would occur only if one AS was listed twice, which would be an error. When receiving a route advertisement, the exterior router will check that its own AS is not already listed in the path and then stick the local identification in the path before advertising it further. If its own identification is already in the path, it will refuse to use that path [1].
This path vector concept has one disadvantage. The need to list the complete path for every destination will increase the size of the routing messages and generally the amount of memory necessary for running the protocol [1]. This amount of memory increases with the number of networks in the Internet.
3.1.1. Path Attributes
Another key feature of the BGP-protocol is the notion of Path Attributes.
This feature provides BGP with flexibility and expandability.
BGP handles paths between autonomous systems. These paths are described by a set of attributes. The two most important attributes are the AS-Path (list of traversed AS) and the "list of reachable networks" attribute. When several paths are available, adding other attributes will help the exterior routers to choose the best path [1]. One very useful attribute is the "data rate of the slowest hop" attribute.
Path attributes are partitioned into well-known and optional. Well-known attributes are the AS-path, the origin, the next hop, the unreachable mark and the inter-AS metric attributes [1]. "The provision for optional attributes allows experimentation that may involve a group of BGP routers without affecting the rest of the Internet" [7]. Routers are not expected to know all the optional attributes. So if router receives optional attributes that it doesn't know how to use them, it must pass those attributes unchanged to their neighbors.
BGP identifies all path attributes by a 2-octet code shown in figure 3.1.
0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | O | T | P | E | 0 | Attr. Type Code | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+Figure 3.1. Path Attribute - code
The first octet is used to pass four attribute flags, indicating for example weather the attribute is optional (O=1) or well-known (O=0). The second octet carries the type code.
3.1.2. Interior and Exterior Peers
When an exterior router has learned a path toward a given network, it
should propagate the path attributes through the AS. That cannot normally
be done through the IGP alone [1]. In a BGP speaking
system each external router establishes an internal connection with all
other external routers in the AS; in other words, with all Interior peers.
These internal connections will be used to propagate external routing
information. They will also be used to get an agreement among the Internal
peers on the best route toward a given external network; in other words, to
a given Exterior peer.
3.2. Running BGP over TCP
The initial BGP implementation is based on TCP, but any reliable transport
protocol may be used. A message passing protocol such as VMTP might be
more natural for BGP [5]. TCP will be used,
however, since it is present in virtually all commercial routers and hosts.
BGP delegates all error control functions to TCP and that makes the protocol much simpler, so there is no need to implement explicit update fragmentation, retransmission, acknowledgement, and sequencing [5].
3.3. BGP Messages
BGP attaches before all messages a fixed-length header that includes
the length of the routing message. The layout of the header is shown below
[5]:
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + + | | + + | Marker | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Length | Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Figure 3.2 BGP Meaasge Header
The 16-byte Marker is designed to be used for security purposes.
The four procedures (packet type in the header) of BGP are:
After a transport protocol connection is established, the first message sent by each side is an Open message. If the Open message is acceptable, a Keepalive message confirming the Open is sent back. Once the Open is confirmed, Update, Keepalive, and Notification messages may be exchanged [5].
Update messages are used to transfer routing information between BGP peers. The Update messages are composed from a standard BGP header followed by a set of path attributes and a list of reachable networks [1]. Just after initiating the connection, each router sends to it's partner a list of proposed paths, using as many Update messages as necessary. After that, the routers will send Updates only for the paths that are changed. If a router receives a new path to a given destination that is shorter than the old path, it modifies the routing tables and sends the corresponding Updates to the BGP neighbors.
BGP does not use any transport protocol-based keep-alive mechanism to determine if neighbors are reachable, like was the case of EGP. Instead, Keepalive messages are exchanged between peers often enough [5]. A reasonable maximum time between Keepalive messages would be one third of the Hold Time interval. This typically results in sending messages every 2 minutes [1].
A Notification message is sent when an error condition is detected. The BGP connection is closed immediately after sending it [5].
The Routing Information Base (RIB) within a BGP speaker consists of three distinct parts [9]:
3.4. Different BGP versions and EGP
In the opening procedure, the BGP connection can be accepted only if both
ends support the same BGP version [1]. This version
number is passed in the Open message. If the version number that is
received is not equal to the version number that was sent, the connection
must be terminated. Then a new connection attempt can be made with a lower
version number.
If the neighbor use EGP and don't support BGP, one possibility is to send messages through such an autonomous system that has both EGP and BGP routers. Those routers can make the translation of formats through the internal connections [1].
3.5. BGP-4
BGP-4 is the newest version of BGP and was published in 1994.
The Key feature of the BGP-4 protocol is the aggregation of network laye
r reachability information (NLRI) [11]. "BGP-4 was
created specifically to reduce the amount of NLRI entries carried and
exchanged by border routers" [11].
BGP-4 provides a new set of mechanisms for supporting classless interdomain routing (CIDR). These mechanisms include support for advertising an IP prefix and eliminates the concept of network "class" within BGP. BGP-4 also introduces mechanisms which allow aggregation of routes, including aggregation of AS paths. These changes provide support for the proposed supernetting scheme, so that information about groups of networks may represented as a single entity.
BGP-4 has a Management Information Base (MIB). Apart from a few system variables, the BGP MIB is broken into two tables: the BGP Peer Table and the BGP Received Path Attribute Table [10].
The Peer Table reflects information about BGP peer connections, such as
their state and current activity. The Received Path Attribute Table
contains all attributes received from all peers before local routing policy
has been applied [10].
4. Conclusions
As the first exterior gateway protocol to gain widespread acceptance in
the Internet, the EGP served a valuable purpose. As the Internet grew,
the limitations of EGP became unacceptable. There was a strong user
demand to move away from the backbone-centered tree topology mandated by
EGP. This led to the standardization of the Border Gateway Protocol.
There are many differences between EGP and BGP, but the most important innovation within BGP is probably the path vector concept, which enables loop prevention in complex topologies.
While BGP is well suitable for the current Internet, it is also almost a necessity for the current Internet as well. The information provided by BGP is well suitable for enforcing a variety of routing policies [7]. "The extensive operational experience with BGP showed that the only problem attributed to BGP was the slow convergence problem in presence of congestion" [8].
There are multiple independent interoperable implementations of BGP currently available. The most common implementations are cisco Systems, gated consortium, 3COM, Bay Networks (Wellfleet) and Proteon [10].
By the year 1995 BGP-4 was used as an inter-autonomous system routing protocol between all significant autonomous systems, including: Alternet, ANS, Ebone, ICM, IIJ, MCI, NSFNET, and Sprint. The smallest know backbone consists of one router, whereas the largest contains nearly 90 BGP speakers. All together, there are several hundred known BGP speaking routers [10].
| Term | Meaning |
|---|---|
| AS | Autonomous System The classic definition of an Autonomous System is a set of routers under a single technical administration, using an interior gateway protocol and common metrics to route packets within the AS, and using an exterior gateway protocol to route packets to other ASs. Since this classic definition was developed, it has become common for a single AS to use several interior gateway protocols and sometimes several sets of metrics within an AS. |
| BGP | Border Gateway Protocol Border Gateway Protocol is an exterior routing protocol related to EGP, but it operates with more capability and greater flexibility. |
| CIDR | Classless interdomain routing |
| EGP | Exterior Gateway Protocol Exterior Gateway Protocol is the first exterior routing protocol designed and used for exchanging routing information with gateways in other autonomous systems. |
| Hold Time | During the opening exchange, the BGP stations have announced a hold time, which is the maximum delay during which the peer should have to wait between successive messages. |
| IGP | Interior Gateway Protocol Routing protocol used within an autonomous system |
| MIB | Management Information Base |
| NLRI | Network Layer Reachability Information |
| OSPF | Open Shortest Path First An Interior Gateway Protocol for TCP/IP networks based on the Internet Protocol (IP) network layer. The basic algorithm of OSPF is called the Shortest Path First Algorithm. |
| RIB | Routing Information Base |
| RIP | Routing Information Protocol An Interior Gateway Protocol that automatically creates and maintains network routes among routes that support RIP. |
Juha Korhonen