Saturday, June 29, 2013
ABSTRACT
BGP stands for Border Gateway Protocol and often plays
a critical role in reliable Internet connectivity. But often BGP isn't required
for reliable connectivity.
BGP is an inter-Autonomous System routing protocol. 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 AS’s.
BGP lets your routers pick
the best way for a packet leaving your network to reach its eventual
destination via the Internet.
It lets the routers that
comprise the "Internet Backbone" choose the best way for a packet to
reach your network.
It's of limited use in
avoiding congestion. It can't help hosts with a static default to a dead
router.
BGP-4 is an extension of BGP-3 that
provides support for routing information aggregation and reduction based on the
Classless inter-domain routing architecture.
BGP
uses TCP as its transport protocol.
The discussion contains
various BGP attributes, BGP-4 and concludes with the BGP-OSPF interaction.
OSPF (Open Shortest Path First)
protocol was developed due to a need in the internet community to introduce a
high functionality non-proprietary Internal Gateway Protocol (IGP) for the
TCP/IP protocol family while BGP is an Exterior Gateway Protocol.
This report summarizes the key
features of BGP, and analyzes the protocol with respect to scaling and
performance.
INTRODUCTION
BGP is an inter-Autonomous
System routing protocol. The network reachability information exchanged via BGP
provides sufficient information to detect routing loops and enforce routing
decisions based on performance preference and policy constraints as outlined in
RFC 1104 [2]. In particular, BGP exchanges routing information containing full
AS paths and enforces routing policies based on configuration information.
BGP :
§ Is a Path Vector Protocol.
§ Many options for policy enforcements
§ Classless Inter Domain Routing ( CIDR )
§ Widely used for Internet backbone
§ Used for Autonomous systems
Currently BGP-4 [BGP-4] is capable of
carrying routing information only for IPv4 [IPv4].
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. This information is sufficient to construct a graph of
AS connectivity from which routing loops may be pruned and some policy decisions
at the AS level may be enforced.
BGP runs
over a reliable transport protocol. This
eliminates the need to implement explicit update fragmentation, retransmission,
acknowledgement, and sequencing.
3. TOPIC DETAILS
3.1 Why BGP ?
As the Internet has evolved and grown over
in recent years, it has become painfully evident that it is soon to face
several serious scaling problems. These include:
- Exhaustion of the class-B network
address space. One fundamental cause of this problem is the lack of a network
class of a size which is appropriate for mid-sized organization; class-C, with
a maximum of 254 host addresses, is too small while class-B, which allows up to
65534 addresses, is too large to be densely populated.
- Growth of routing tables in Internet
routers are beyond the ability of current software (and people) to effectively
manage.
- Eventual exhaustion of the 32-bit IP
address space.
It has become clear that the first two of
these problems are likely to become critical within the next one to three
years. Classless inter-domain routing
(CIDR) attempts to deal with these problems by
proposing a mechanism to slow the growth of the routing table and
the need for allocating new IP network
numbers. It does not attempt to solve
the third problem, which is of a more long-term nature, but instead endeavors
to ease enough of the short to mid-term difficulties to allow the Internet to
continue to function efficiently while progress is made on a longer- term
solution.
BGP-4 is an extension
of BGP-3 that provides support for routing
information aggregation and reduction based on the Classless inter- domain routing architecture (CIDR) [3]. This memo describes the usage of BGP-4 in the Internet.
All of the
discussions in this paper are based on the assumption that the Internet is a
collection of arbitrarily connected Autonomous Systems. That is, the Internet
will be modeled as a general graph whose nodes are AS's and whose edges are
connections between pairs of AS's.
3. 2 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 AS's. 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. The use of the term Autonomous System
here stresses the fact that, even when multiple IGPs and metrics are used, the
administration of an AS appears to other AS's to have a single coherent
interior routing plan and presents a consistent picture of which networks are
reachable through it.
3.3 External and
Interior BGP :
Customers connect to ISPs, and
ISPs use BGP to exchange customer and ISP routes. When BGP is used between
autonomous systems (AS), the protocol is referred to as External BGP (EBGP). If
a service provider is using BGP to exchange routes within an AS, then the
protocol is referred to as Interior BGP (IBGP).
3.4 BGP Attributes
:
Routes learned via BGP have
associated properties that are used to determine the best route to a
destination when multiple paths exist to a particular destination. These
properties are referred to as BGP attributes, and an understanding of how BGP
attributes influence route selection is required for the design of robust
networks. This section describes the attributes that BGP uses in the route
selection process:
- Weight
- Local preference
- Multi-exit discriminator
- Origin
- AS_path
- Next hop
- Community
3.5 BGP
Topological Model :
When we say that a connection exists between
two AS's, we mean two things:
Physical connection: There is a shared network between the two
AS's, and on this shared network each AS has at least one border gateway belonging to that AS. Thus the
border gateway of each AS can
forward packets to the border gateway of the other AS without resorting to Inter-AS or Intra-AS
routing.
BGP connection: There is a BGP session
between BGP speakers in each of the AS's, and this session communicates those
routes that can be used for specific networks via the advertising AS.
Throughout this document we place an additional restriction on the BGP speakers
that form the BGP connection: they must themselves share the same network that
their border gateways share. Thus, a BGP session between adjacent AS's requires
no support from either Inter-AS or Intra-AS routing. Cases that do not conform
to this restriction fall outside the scope of this document.
Thus, at each connection, each AS has one or
more BGP speakers and one or more border gateways, and these BGP speakers and
border gateways are all located on a shared network. Note that BGP speakers do
not need to be a border gateway, and vice versa. Paths announced by a BGP speaker of one AS on a given
connection are taken to be feasible for
each of the border gateways of the other AS on the same shared network, i.e.
indirect neighbors are allowed.
Much of the traffic carried within an AS
either originates or terminates at that AS (i.e., either the source IP address
or the destination IP address of the IP packet identifies a host on a network
internal to that AS). Traffic that fits
this description is called "local traffic". Traffic that does not fit
this description is called "transit traffic". A major goal of BGP
usage is to control the flow of transit traffic.
Based on how a particular AS deals with
transit traffic, the AS may now be placed into one of the following categories:
Stub AS : an AS that has only a
single connection to one other AS. Naturally, a stub AS only carries local traffic.
Multihomed AS : An AS that has connections to more than
one other AS, but refuses to carry transit traffic.
Transit AS : An AS that has connections to more than one other AS,
and is designed (under certain policy restrictions) to carry both transit and
local traffic.
3.6 BGP in the
Internet :
Topology
Considerations :
The overall Internet topology may be
viewed as an arbitrary interconnection of transit, multihomed, and stub
AS's. In order to minimize the impact on the current Internet
infrastructure, stub and multihomed
AS's need not use BGP. These AS's may
run other protocols (e.g., EGP) to exchange reachability information with
transit AS's.
Transit AS's using BGP will tag this
information as having been learned by some method other than BGP. The fact that
BGP need not run on stub or multihomed AS's has no negative impact on the
overall quality of inter-AS routing for traffic that either destined to or
originated from the stub or multihomed AS's in question.
However, it is recommended that BGP be
used for stub and multihomed AS's as well. In these situations, BGP will
provide an advantage in bandwidth and performance over some of the currently
used protocols (such as EGP). In
addition, this would reduce the need for the use of default routes and in
better choices of Inter-AS routes for multihomed AS's.
Global Nature of
BGP :
At a global level, BGP is used to distribute
routing information among multiple Autonomous Systems. The information flows can
be represented as follows:
--------- ----------
BGP
| BGP | BGP
| BGP | BGP
---------| |----------| |---------
| IGP
| | IGP |
--------- ----------
AS A AS B
This diagram points out that, while BGP
alone carries information between AS's, both BGP and an IGP may carry
information across an AS.
Ensuring consistency of routing information
between BGP and an IGP within an AS is a significant issue and is discussed at
length later in Appendix A.
BGP Neighbor
Relationships :
The Internet is viewed as a set of
arbitrarily connected AS's. BGP
speakers in each AS communicate with each other to exchange network
reachability information based on a set of policies established within each AS.
Routers that communicate directly with each other via BGP are known as BGP
neighbors. BGP neighbors can be located within the same AS or in different
AS's. For the sake of discussion, BGP communications with neighbors in
different AS's will be referred to as External BGP, and with neighbors in the
same AS as Internal BGP.
There can be as many BGP speakers as deemed
necessary within an AS.
Usually, if an AS has multiple connections
to other AS's, multiple BGP speakers are needed. All BGP speakers representing
the same AS must give a consistent image of the AS to the outside. This
requires that the BGP speakers have consistent routing information among them.
These gateways can communicate with each
other via BGP or by other means. The policy constraints applied to all BGP
speakers within an AS must be
consistent. Techniques such as using a tagged IGP (see A.2.2) may be employed to detect possible
inconsistencies.
In the case of External BGP, the BGP
neighbors must belong to different
AS's, but share a common network. This common network should be used to carry the BGP messages
between them. The use of BGP across an intervening AS invalidates the AS path
information. An Autonomous System
number must be used with BGP to specify which
Autonomous System the BGP speaker belongs to.
General Operation
:
- Learns multiple paths via internal and external
BGP speakers.
- Picks the best path and installs in the
forwarding table.
- Policies applied by influencing the best path
selection.
- 3.7 BGP – 4 :Operation :Two systems form a transport protocol connection between one another.They exchange messages to open and confirm the connection parameters.The initial data flow is the entire BGP routing table. Incremental updates are sent as the routing tables change. BGP does not require periodic refresh of the entire BGP routing table. Therefore, a BGP speaker must retain the current version of the entire BGP routing tables of all of its peers for the duration of the connection. KeepAlive messages are sent periodically to ensure the liveness of the connection. Notification messages are sent in response to errors or special conditions. If a connection encounters an error condition, a notification message is sent and the connection is closed.The hosts executing the Border Gateway Protocol need not be routers.A non-routing host could exchange routing information with routers via EGP or even an interior routing protocol. That non-routing host could then use BGP to exchange routing information with a border router in another Autonomous System.Message Formats:Messages are sent over a reliable transport protocol connection. A message is processed only after it is entirely received. The maximum message size is 4096 octets. All implementations are required to support this maximum message size. The smallest message that may be sent consists of a BGP header without a data portion, or 19 octets.Message Header Format : Each message has a fixed-size header. There may or may not be a data portion following the header, depending on the message type.0 1 2 30 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 |+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Marker:This 16-octet field contains a value that the receiver of the message can predict. If the Type of the message is OPEN, or if the Authentication Code used in the OPEN message of the connection is zero, then the Marker must be all ones. Otherwise, the value of the marker can be predicted by some computation specified as part of the authentication mechanism used. The Marker can be used to detect loss of synchronization between a pair of BGP peers, and to authenticate incoming BGP messages.Length:This 2-octet unsigned integer indicates the total length of the message, including the header, in octets. Thus, e.g., it allows one to locate in the transport-level stream the (Marker field of the) next message. The value of the Length field must always be at least 19 and no greater than 4096, and may be further constrained, depending on the message type. No "padding" of extra data after the message is allowed, so the Length field must have the smallest value required given the rest of the message.Type:This 1-octet unsigned integer indicates the type code of the message. The following type codes are defined:1 - OPEN2 - UPDATE3 - NOTIFICATION4 - KEEPALIVEDecision Process:The Decision Process takes place in three distinct phases, each triggered by a different event:a) Phase 1 is responsible for calculating the degree of preference for each route received from a BGP speaker located in a neighboring autonomous system, and for advertising to the other BGP speakers in the local autonomous system the routes that have the highest degree of preference for each distinct destination.b) Phase 2 is invoked on completion of phase 1. It is responsible for choosing the best route out of all those available for each distinct destination, and for installing each chosen route into the appropriate Loc-RIB.c) Phase 3 is invoked after the Loc-RIB has been modified. It is responsible for disseminating routes in the Loc-RIB to each peer located in a neighboring autonomous system, according to the policies contained in the PIB. Route aggregation and information reduction can optionally be performed within this phase.3.8 Multiprotocol Extensions to BGP – 4 :Currently BGP-4 [BGP-4] is capable of carrying routing information only for IPv4 [IPv4]. Extensions to BGP-4 enable it to carry routing information for multiple Network Layer protocols (e.g., IPv6, IPX, etc...).The extensions are backward compatible - a router that supports the extensions can interoperate with a router that doesn't support the extensions.To enable BGP-4 to support routing for multiple Network Layer protocols the only two things that have to be added to BGP-4 are (a) the ability to associate a particular Network Layer protocol with the next hop information, and (b) the ability to associated a particular Network Layer protocol with NLRI.To provide backward compatibility, as well as to simplify introduction of the multiprotocol capabilities into BGP-4 this document uses two new attributes, Multiprotocol Reachable NLRI (MP_REACH_NLRI), and Multiprotocol Unreachable NLRI (MP_UNREACH_NLRI).Multiprotocol Reachable NLRI - MP_REACH_NLRI : This is an optional non-transitive attribute that can be used for the following purposes:(a) to advertise a feasible route to a peer(b) to permit a router to advertise the Network Layer address of the router that should be used as the next hop to the destinations listed in the Network Layer Reachability Information field of the MP_NLRI attribute.(c) to allow a given router to report some or all of the Subnetwork Points of Attachment (SNPAs) that exist within the local system.The attributes are as given below:§ Address Family Identifier (2 octets)§ Subsequent Address Family Identifier (1 octet)§ Length of Next Hop Network Address (1 octet)§ Network Address of Next Hop (variable)§ Number of SNPAs (1 octet)§ Length of first SNPA(1 octet)§ First SNPA (variable)§ Length of second SNPA (1 octet)§ Second SNPA (variable)§ Length of Last SNPA (1 octet)§ Last SNPA (variable)§ Network Layer Reachability Information (variable)Multiprotocol Unreachable NLRI - MP_UNREACH_NLRI : This is an optional non-transitive attribute that can be used for the purpose of withdrawing multiple unfeasible routes from service.The attribute is as given below:§ Address Family Identifier (2 octets)§ Subsequent Address Family Identifier (1 octet)§ Withdrawn Routes (variable)3.9 BGP OSPF INTERACTION :Introduction :This document defines the various criteria to be used when designing Autonomous System Border Routers (ASBR) that will run BGP with other ASBRs external to the AS, and OSPF as its IGP.The following fields in OSPF and attributes in BGP are to be set when interfacing between BGP and OSPF at an ASBR:OSPF cost and type vs. BGP INTER-AS METRICOSPF tag vs. BGP ORIGIN and AS_PATHOSPF Forwarding Address vs. BGP NEXT_HOPThis document uses the two terms "Autonomous System" and "Routing Domain"."A Routing Domain is a collection of routers which coordinatetheir routing knowledge using a single (instance of) a routingprotocol."Route Exchange :The exchange of routes between BGP and OSPF involves :
- Exporting OSPF routes into BGP
- Importing BGP routes into OSPF
BGP Identifier and OSPF router ID :The BGP identifier must be the same as the OSPF router id at alltimes that the router is up.CONCLUSION
The BGP protocol provides a high degree of control and flexibility for doing interdomain routing while enforcing policy and performance constraints and avoiding routing loops.The guidelines presented here will provide a starting point for using BGP to provide more sophisticated and manageable routing in the Internet as it grows.Border Gateway Protocol is a distance vector protocol. Other distance vector protocols often make wrong choice because they cannot tell which of their neighbors have independent routes to the destination and which do not. The current definition of BGP is in RFC 1654.BGP easily solves the count-to-infinity problem that plagues other distance vector algorithms.It's of limited use in avoiding congestion. It can't help hosts with a static default to a dead router.Extensions to the BGP are still in progress and the necessity to the protocol may not be felt to this day but will be a necessity in the future. - Exporting OSPF routes into BGP
