summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc1164.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc1164.txt')
-rw-r--r--doc/rfc/rfc1164.txt1291
1 files changed, 1291 insertions, 0 deletions
diff --git a/doc/rfc/rfc1164.txt b/doc/rfc/rfc1164.txt
new file mode 100644
index 0000000..4543327
--- /dev/null
+++ b/doc/rfc/rfc1164.txt
@@ -0,0 +1,1291 @@
+
+
+
+
+
+
+Network Working Group J. Honig, Cornell Univ. Theory Center
+Request for Comments: 1164 D. Katz, Merit/NSFNET
+ M. Mathis, Pittsburgh Supercomputing Center
+ Y. Rekhter, T.J. Watson Research Center, IBM Corp
+ J. Yu, Merit/NSFNET
+ June 1990
+
+ Application of the Border Gateway Protocol in the Internet
+
+Status of this Memo
+
+ This RFC, together with its companion RFC-1163, "A Border Gateway
+ Protocol (BGP)", define a Proposed Standard for an inter-autonomous
+ system routing protocol for the Internet.
+
+ This protocol, like any other at this initial stage, may undergo
+ modifications before reaching full Internet Standard status as a
+ result of deployment experience. Implementers are encouraged to
+ track the progress of this or any protocol as it moves through the
+ standardization process, and to report their own experience with the
+ protocol.
+
+ This protocol is being considered by the Interconnectivity Working
+ Group (IWG) of the Internet Engineering Task Force (IETF).
+ Information about the progress of BGP can be monitored and/or
+ reported on the IWG mailing list (IWG@nri.reston.va.us).
+
+ Please refer to the latest edition of the "IAB Official Protocol
+ Standards" RFC for current information on the state and status of
+ standard Internet protocols.
+
+ Distribution of this memo is unlimited.
+
+Table of Contents
+
+ 1. Acknowledgements....................................... 2
+ 2. Introduction........................................... 2
+ 3. BGP Theory and Application............................. 3
+ 3.1 Topological Model..................................... 3
+ 3.2 BGP in the Internet................................... 4
+ 3.2.1 Topology Considerations............................. 4
+ 3.2.2 Global Nature of BGP................................ 5
+ 3.2.3 BGP Neighbor Relationships.......................... 5
+ 3.3 Policy Making with BGP................................ 6
+ 4. Operational Issues..................................... 7
+ 4.1 Path Selection........................................ 7
+ 4.2 Syntax and Semantics for BGP Configuration Files...... 9
+ 5. The Interaction of BGP and an IGP...................... 17
+
+
+
+Interconnectivity Working Group [Page 1]
+
+RFC 1164 BGP - Application June 1990
+
+
+ 5.1 Overview.............................................. 17
+ 5.2 Methods for Achieving Stable Interactions............. 17
+ 5.2.1 Propagation of BGP Information via the IGP.......... 18
+ 5.2.2 Tagged Interior Gateway Protocol.................... 18
+ 5.2.3 Encapsulation....................................... 19
+ 5.2.4 Other Cases......................................... 19
+ 6. Implementation Recommendations......................... 20
+ 6.1 Multiple Networks Per Message......................... 20
+ 6.2 Preventing Excessive Resource Utilization............. 20
+ 6.3 Processing Messages on a Stream Protocol.............. 21
+ 6.4 Processing Update Messages............................ 21
+ 7. Conclusion............................................. 22
+ References................................................ 22
+ Security Considerations................................... 22
+ Authors' Addresses........................................ 22
+
+1. Acknowledgements
+
+ The authors would like to thank Guy Almes (Rice University), Kirk
+ Lougheed (cisco Systems), Hans-Werner Braun (Merit/NSFNET), Sue Hares
+ (Merit/NSFNET), and the Interconnectivity Working Group of the
+ Internet Engineering Task Force (chaired by Guy Almes) for their
+ contributions to this paper.
+
+2. Introduction
+
+ The Border Gateway Protocol (BGP), described in RFC 1163, is an
+ interdomain 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].
+
+ This memo uses the term "Autonomous System" throughout. 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. 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 ASs to have a single
+ coherent interior routing plan and presents a consistent picture of
+ what networks are reachable through it. From the standpoint of
+ exterior routing, an AS can be viewed as monolithic: reachability to
+ networks directly connected to the AS must be equivalent from all
+ border gateways of the AS.
+
+
+
+
+Interconnectivity Working Group [Page 2]
+
+RFC 1164 BGP - Application June 1990
+
+
+ This paper discusses the use of BGP in the Internet environment.
+ Issues such as topology, the interaction between BGP and IGPs, and
+ the enforcement of policy rules with BGP will be presented.
+
+ All of the discussions in this paper are based on the assumption that
+ the Internet is a collection of arbitrarily connected Autonomous
+ Systems. The AS is assumed to be administered by a single
+ administrative entity, at least for the purposes of representation of
+ routing information to systems outside of the AS.
+
+3. BGP Theory and Application
+
+3.1 Topological Model
+
+ We will be concerned throughout this paper with a general graph whose
+ nodes are ASs and whose edges are connections between pairs of ASs.
+ The notion of AS is discussed above in Section 2. When we say that a
+ connection exists between two ASs, we mean both of two things:
+
+ physical connection: there is a shared network between the two ASs,
+ 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
+ resort to Inter-AS or Intra-AS routing.
+
+ BGP connection: there is a BGP session between BGP speakers on each
+ of the ASs, and this session communicates to each connected AS
+ those routes through the physically connected border gateways of
+ the other AS that can be used for specific networks. 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 the adjacent ASs 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. Only the AS's border
+ gateways on the connection's shared network may be used by that AS's
+ BGP speakers on that shared network in NEXT_HOP attributes in Update
+ messages. 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 connection. In all BGP usage, we intend
+ that the flow of packets from one AS to the other correspond to
+ advertised AS paths.
+
+ Much of the traffic carried within an AS either originates or
+
+
+
+Interconnectivity Working Group [Page 3]
+
+RFC 1164 BGP - Application June 1990
+
+
+ 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 directly connected 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 another AS.
+ Naturally, a stub AS only carries local traffic.
+
+ multihomed AS: an AS that has more than one connection to other ASs,
+ but refuses to carry transit traffic.
+
+ transit AS: an AS that has more than one connection to other ASs and
+ is designed (under certain policy restrictions) to carry both
+ transit and local traffic.
+
+ Since a full AS path provides an efficient and straightforward way of
+ suppressing routing loops and eliminates the "count-to-infinity"
+ problem associated with some distance vector algorithms, BGP imposes
+ no topological restrictions on the interconnection of ASs.
+
+3.2 BGP in the Internet
+
+3.2.1 Topology Considerations
+
+ The overall Internet topology may be viewed as an arbitrary
+ interconnection of transit, multihomed, and stub ASs. In order to
+ minimize the impact on the current Internet infrastructure, stub and
+ multihomed ASs need not use BGP. These ASs may run other protocols
+ (e.g., EGP) to exchange reachability information with transit ASs.
+ Transit ASs then tag this information as having been learned via EGP
+ or some other method. The fact that BGP need not run on stub or
+ multihomed ASs has no negative impact on the overall quality of
+ inter-AS routing for traffic not local to the stub or multihomed ASs
+ in question.
+
+ Of course, BGP may be used for stub and multihomed ASs as well,
+ providing advantage in bandwidth and performance over some of the
+ currently used protocols (such as EGP). In addition, this would
+ result in less need for the use of defaults and in better choices of
+ Inter-AS routes for mulitihomed ASs.
+
+
+
+
+
+
+Interconnectivity Working Group [Page 4]
+
+RFC 1164 BGP - Application June 1990
+
+
+3.2.2 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 ASs, a combination of BGP and an IGP carries 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 this paper.
+
+3.2.3 BGP Neighbor Relationships
+
+ As discussed in the introduction, the Internet is viewed as a set of
+ arbitrarily connected Autonomous Systems (ASs). BGP gateways in each
+ AS communicate with each other to exchange network reachability
+ information based on a set of policies established within each AS.
+ Computers 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 ASs. For the sake of discussion, BGP communications
+ with neighbors in different ASs will be referred to as External BGP,
+ and with neighbors in the same AS as Internal BGP.
+
+ External BGP In the case of External BGP, the BGP neighbors must
+ belong to different ASs, 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.
+
+ Internal BGP There can be as many BGP gateways as deemed necessary
+ within an AS. Usually, if an AS has multiple connections to other
+ ASs, multiple BGP gateways are needed. All BGP gateways
+ representing the same AS must give a consistent image of the AS to
+ the outside. This requires that the BGP gateways 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 gateways within an AS must be consistent.
+
+
+
+
+Interconnectivity Working Group [Page 5]
+
+RFC 1164 BGP - Application June 1990
+
+
+3.3 Policy Making with BGP
+
+ BGP provides the capability of enforcing some policies based on
+ various preferences and constraints. Policies are determined by the
+ AS administration and are provided to BGP in the form of
+ configuration information. These policies are enforced within a BGP
+ speaker by affecting the selection of paths from multiple
+ alternatives, and by controlling the redistribution of routing
+ information. Policies are not directly encoded in the protocol.
+
+ Non-technical constraints are related to political, security, or
+ economic considerations. For example, if an AS is unwilling to carry
+ traffic to another AS, it can enforce a policy prohibiting this. The
+ following examples of non-technical constraints can be enforced with
+ the use of BGP:
+
+ 1. A multihomed AS can refuse to act as a transit AS for other
+ ASs. (It does so by not advertising routes to networks other
+ than those directly connected to it.)
+
+ 2. A multihomed AS can become a transit AS by allowing a certain
+ set of ASs to use it as such. (It does so by advertising
+ routes to networks to this set of ASs.)
+
+ 3. An AS can favor or disfavor the use of certain ASs for carrying
+ transit traffic from itself to networks advertised with
+ competing AS paths.
+
+ A number of performance-related criteria can be controlled with the
+ use of BGP:
+
+ 1. An AS can minimize the number of transit ASs. (Shorter AS
+ paths can be preferred over longer ones.)
+
+ 2. The quality of transit ASs. If an AS determines, using BGP,
+ that two or more AS paths can be used to reach a given
+ destination, that AS can use a variety of means to decide which
+ of the candidate AS paths it will use. The quality of an AS
+ can be measured by such things as diameter, link speed,
+ capacity, tendency to become congested, and quality of
+ operation. Information about these qualities might be
+ determined by means other than BGP.
+
+ 3. Preference of internal routes over external routes.
+
+ Non-technical policy will typically override performance issues.
+
+ For consistency, combinations of policies and route selection
+
+
+
+Interconnectivity Working Group [Page 6]
+
+RFC 1164 BGP - Application June 1990
+
+
+ procedures that might result in equal cost paths must be resolved in
+ a deterministic fashion.
+
+ Fundamental to BGP usage is the rule that an AS advertizes to its
+ neighboring ASs only those routes that it uses. This rule reflects
+ the "hop-by-hop" routing paradigm generally used by the current
+ Internet. Note that some policies that cannot be supported by the
+ "hop-by-hop" routing paradigm and which require such techniques as
+ source routing to enforce. For example, BGP does not enable one AS
+ to send traffic to a neighbor AS intending that that traffic take a
+ different route from that taken by traffic originating in the
+ neighbor AS. On the other hand, BGP can support any policy
+ conforming to the "hop-by-hop" routing paradigm. Since the current
+ Internet uses only the "hop-by-hop" routing paradigm and since BGP
+ can support any policy that conforms to that paradigm, BGP is highly
+ applicable as an inter-AS routing protocol for the current Internet.
+
+4. Operational Issues
+
+4.1 Path Selection
+
+ One of the major tasks of a BGP speaker for a given AS at a given
+ connection is to evaluate different paths to a destination network
+ from its border gateways at that connection, select the best one, and
+ then advertise it to all of its BGP neighbors at that same connection
+ (subject to policy constraints). The key issue is how different
+ paths are evaluated and compared.
+
+ In traditional distance vector protocols (e.g., RIP) there is only
+ one metric (e.g., hop count) associated with a path. As such,
+ comparison of different paths is reduced to simply comparing two
+ numbers. A complication in Inter-AS routing arises from the lack of
+ a universally agreed-upon metric among ASs that can be used to
+ evaluate external paths. Rather, each AS may have its own set of
+ criteria for path evaluation.
+
+ A BGP speaker within an Autonomous System builds a routing database
+ consisting of the set of all feasible paths and the list of networks
+ reachable through each path. In an efficient implementation, it will
+ be important to store and process these paths and bundle the networks
+ reachable through them. For purposes of precise discussion, however,
+ it's useful to consider the set of feasible paths for a given
+ destination network. In most cases, we would expect to find only one
+ feasible path in the set. This will often, however, not be the case.
+ All feasible paths must be maintained, and their maintenance speeds
+ adaptation to the loss of the primary path, but only the primary path
+ at any given time will ever be advertised.
+
+
+
+
+Interconnectivity Working Group [Page 7]
+
+RFC 1164 BGP - Application June 1990
+
+
+ The path selection process can be formalized by defining a partial
+ order over the set of all possible paths to a given destination
+ network. One way to define this partial order is to define a
+ function that maps each full AS path to a non-negative integer that
+ denotes the path's degree of preference. Path selection is then
+ reduced to applying this function to all feasible paths and choosing
+ the one with the highest degree of preference.
+
+ In actual BGP implementations, criteria for assigning degree of
+ preferences to a path can be specified in a configuration file.
+
+ The process of assigning a degree of preference to a path can be
+ based on several sources of information:
+
+ 1. Information explicitly present in the full AS path.
+
+ 2. A combination of information that can be derived from the full
+ AS path and information outside the scope of BGP.
+
+ The criteria used to assign a degree of preference to a path can be
+ classified as primitive or compound. Possible primitive criteria
+ include:
+
+ - AS count. Paths with a smaller AS count are generally better.
+
+ - Presence or absence of a certain AS or ASs in the path. By
+ means of information outside the scope of BGP, an AS may know
+ some performance characteristics (e.g., bandwidth, MTU, intra-
+ AS diameter) of certain ASs and may try to avoid or prefer
+ them.
+
+ - Path origin. A path whose endpoint is internal to the last AS
+ on the path (BGP is used over the entire path) is generally
+ better than one for which part of the path was learned via EGP
+ or some other means.
+
+ - AS path subsets. An AS path that is a subset of a longer AS
+ path to the same destination should be preferred over the
+ longer path. Any problem in the shorter path (such as an
+ outage) will also be a problem in the longer path.
+
+ - Link dynamics. Stable paths should be preferred over unstable
+ ones. Note that this criterion must be used in a very careful
+ way to avoid causing unnecessary route fluctuation. Generally,
+ any criteria that depend on dynamic information might cause
+ routing instability and should be treated very carefully.
+
+ - Policy consideration. BGP supports policy based routing based
+
+
+
+Interconnectivity Working Group [Page 8]
+
+RFC 1164 BGP - Application June 1990
+
+
+ on the policy based distribution of routing information defined
+ in RFC 1104 [2]. A BGP gateway may be aware of some policy
+ constraints (both within and outside of its own AS) and do
+ appropriate path selection. Paths that do not comply with
+ policy requirements are not considered further.
+
+ Metrics based on compound criteria can be computed as a weighted
+ combination of the degree of preferences of primitive criteria. The
+ use of compound criteria should be done with extreme caution since it
+ involves comparing potentially uncomparable quantities.
+
+4.2 Syntax and Semantics for BGP Configuration Files
+
+ A major task in using BGP is thus to assign a degree of preference to
+ each available AS-path. This degree of preference will generally be
+ a function of the number of ASs in the path, properties of the
+ specific ASs in the path, the origin of the route, and properties of
+ the specific border router to be used in the first hop. In this
+ section we consider how a network administrator might articulate this
+ function by means of a configuration file. In the future, we can
+ imagine using tools based on network management protocols such as
+ SNMP for this task, but the protocols do not currently support this
+ ability.
+
+ In addition to controlling the selection of the best path to a given
+ network, the network administrator must control the advertisement of
+ this best path to neighboring ASs. Therefore, path selection and
+ path distribution emerge as the two key aspects of policy expression
+ in BGP usage.
+
+ Since different aspects of one AS's policy interact, and since the
+ policies of different ASs interact, it is important to facilitate the
+ analysis of such interactions by means of high-quality and consistent
+ tools.
+
+ There is also a need for tools to translate the expression of the
+ network administrator's policy to some technical mechanism within a
+ BGP speaker to implement that policy.
+
+ These factors suggest that there should be a globally consistent way
+ of describing policies in the configuration file. The syntax and
+ semantics of these policies should be capable of expressing the path
+ selection phase within the local AS as well as the path
+ redistribution phase to other ASs.
+
+ Because it may be desirable to coordinate routing policy at an
+ external level, it may prove worthwhile to create a language to
+ describe this information in a globally consistent way. Policies
+
+
+
+Interconnectivity Working Group [Page 9]
+
+RFC 1164 BGP - Application June 1990
+
+
+ expressed in such a language could conceivably be used by some high-
+ level tools to analyze the interaction among the routing policies of
+ different Autonomous Systems.
+
+ The following defines one possible syntax and semantics for
+ describing AS path policies from the point of view of the local AS.
+ Alternative syntaxes with equivalent richness of functionality are
+ not precluded. Other mechanisms may be needed to provide a fully
+ functional configuration language.
+
+ A complete AS path, supplied by BGP, provides the most important
+ mechanism for policy enforcement. Assigning a degree of preference
+ to a particular AS path can be modelled as a matching between this
+ path and one or more predefined AS path patterns. Each predefined AS
+ path pattern has a degree of preference that will be assigned to any
+ AS path that matches it.
+
+ Since patterns are naturally expressed by regular expressions, one
+ can use regular expressions over the alphabet of AS numbers to define
+ AS path patterns and, therefore, to formulate policies.
+
+ Since certain constructs occur frequently in regular expressions, the
+ following notational shorthand (operators) is defined:
+
+ . matches any AS number. To improve readability, "." can be
+ replaced by "any" so long as this does not introduce ambiguity.
+
+ * a regular expression followed by * means zero or more
+ repetitions
+
+ + a regular expression followed by + means one or more
+ repetitions
+
+ ? a regular expression followed by ? means zero or one repetition
+
+ | alternation
+
+ () parentheses group subexpressions--an operator, such as * or
+ works on a single element or on a regular expression enclosed
+ in parentheses
+
+ {m,n} a regular expression followed by {m,n} (where m and n are
+ both non-negative integers and m <= n) means at least m and at
+ most n repetitions.
+
+ {m} a regular expression followed by {m} (where m is a positive
+ integer) means exactly m repetitions.
+
+
+
+
+Interconnectivity Working Group [Page 10]
+
+RFC 1164 BGP - Application June 1990
+
+
+ {m,} a regular expression followed by {m,} (where m is a positive
+ integer) means m or more repetitions.
+
+Any regular expression is generated by these rules.
+
+The Policy Based Routing Language can then be defined as follows:
+
+ <Policy-Based-Routing> ::= { <policy-statement> }
+
+ Semantics: each policy statement might cause a given possible BGP
+ advertisement (possibility) to be installed into the routing table
+ as the route to a given (set of) networks. Thus, an empty
+ Policy-Based-Routing means that no possibilities will be accepted.
+
+ <policy-statement> ::=
+ <policy-expression> '=' <dop-expression> ';'
+
+ Semantics: if a given possibility matches the policy-expression,
+ then that possibility will be accepted with a degree of preference
+ denoted by the integer value dop-expression.
+
+ <policy-expression> ::=
+ <policy-term> |
+ <policy-term> <policy-operator> <policy-term>
+
+ <policy-term> ::=
+ <network-list> <AS-path> <origin> <distribution-list> |
+ '(' <policy-expression> ')' |
+ NOT <policy-expression> |
+ <>
+
+ <policy-operator> ::= OR | AND
+
+ Semantics: the intersection of the network list of a possibility
+ and the network-list must be non-empty; the AS-path of the
+ possibility must match the AS-path as a sequence; the origin of
+ the possibility must be a member of the origin set; if these
+ conditions are met, the route denoted by the possibility is
+ accepted as a possible route to those networks of the intersection
+ of the possibility network list and the network-list.
+
+ <AS-path> ::= "regular expression over AS numbers"
+
+ Semantics: the AS-path of the possibility must be generated by the
+ regular expression <AS-path>.
+
+
+
+
+
+
+Interconnectivity Working Group [Page 11]
+
+RFC 1164 BGP - Application June 1990
+
+
+ <network-list> ::= '<' { network network-list } '>' |
+ '<' ANY '>'
+
+ Semantics: A non-empty sequence enumerates the network numbers of
+ the network-list; ANY denotes the set of all network numbers.
+
+ <origin> ::= IGP | EGP | INCOMPLETE | ANY
+
+ Semantics: origin enumerates the sequence of acceptable origins;
+ ANY denotes the set of all origins.
+
+ <distribution-list> ::= '<' { AS } '>' |
+ '<' ANY '>'
+
+ Semantics: if a given possibility as accepted and installed into
+ the routing table, then distribution-list is the set of
+ (neighboring) autonomous systems to whose border routers we will
+ distribute the BGP-derived routes.
+
+ <dop-expression> ::= <dop-term> |
+ <dop-term> '+' <dop-term> |
+ <dop-term> '-' <dop-term> |
+ <dop-term> '*' <dop-term> |
+ <dop-term> '/' <dop-term> |
+ REJECT
+
+ <dop-term> ::= <integer> |
+ <function> |
+ '(' <dop-expression> ')'
+
+ Semantics: if a possibility matches with degree of preference
+ REJECT, then that possibility will not be used. Otherwise, the
+ integer value of the degree of preference indicates the degree of
+ preference of the possibility, with higher values preferred over
+ lower ones.
+
+ White spaces can be used between symbols to improve readability.
+ "<>" denotes the empty sequence.
+
+ There are two built-in functions, PathLength() and PathWeight().
+ PathLength() takes the AS path as an argument and returns the number
+ of ASs in that path. PathWeight() takes the AS path and an AS weight
+ table as arguments and returns the sum of weights of the ASs in the
+ AS path as defined by the AS weight table. In order to preserve
+ determinism, the AS weight table must always have a default weight
+ which will be assigned to any AS which is not in that table.
+
+ The AS path, as used above, is constructed from right to left which
+
+
+
+Interconnectivity Working Group [Page 12]
+
+RFC 1164 BGP - Application June 1990
+
+
+ is consistent with BGP), so that the most recent AS in the path
+ occupies the leftmost position.
+
+ Each network (and its associated complete AS path) received from
+ other BGP neighbors is matched against local Routing Policies.
+
+ If either no match occurs or the degree of preference associated with
+ the matched policy is REJECT, then the received information is
+ rejected. Otherwise, a degree of preference associated with the
+ matched policy is assigned to that path. Notice that the process
+ terminates on the first successful match. Therefore, policy-terms
+ should be ordered from more specific to more general.
+
+ The semantics of a matched policy is as follows: If a network in
+ <network-list> that was originally introduced into BGP from <origin>
+ is received via <AS-path>, that network should be redistributed to
+ all ASs in <distribution-list>.
+
+ The following examples (some taken from RFC 1102 [3]) illustrate how
+ Policy Terms can be written.
+
+ In the following topology, H elements are hosts, G elements are
+ Policy Gateways running BGP, and numbered elements are ASs.
+
+ H1 --- 1 -G12...G21 - 2 -- G23...G32 -- 3 ----- H2
+ | |
+ | |
+ | |
+ |- G14...G41 - 4 -- G43...G34 ---|- G35...G53 - 5
+ | |
+ | |
+ | H4
+ H3
+
+ In this picture, there are four hosts, ten gateways, and five
+ Autonomous Systems. Gateways G12 and G14 belong to AS 1. Gateways
+ G21 and G23 belong to AS 2. Gateways G41 and G43 belongs to AS 4.
+ Gateways G32, G34, and G35 belong to AS 3. Gateway G53 belongs to AS
+ 5. Dashed lines denote intra-AS connections. Dotted lines denote
+ inter-AS connections.
+
+ First, consider AS 2. It has no hosts attached, and models a transit
+ service, such as the NSFNET backbone network. It may have a very
+ simple policy: it will carry any traffic between any two ASs, without
+ further constraint. If AS 1 and AS 3 are neighboring domains, then
+ its policy term could be written as:
+
+ AS 2: < ANY > < (1 | 3) .* > < IGP > < 1 3 > = 10
+
+
+
+Interconnectivity Working Group [Page 13]
+
+RFC 1164 BGP - Application June 1990
+
+
+ The first component in this policy, the network list
+
+ < ANY >
+
+ says that any network is subject to this policy. The second
+ component, the AS path
+
+ < (1 | 3) .* >
+
+ says that routing information that came from either AS 1 or AS 3
+ matches this policy, including routes from ASs that lie beyond AS 1
+ and AS 3. The third component, the origin
+
+ < IGP >
+
+ says that this route must be interior with respect to the originating
+ AS, implying that routes imported via EGP or some other mechanism
+ would not match this policy. The fourth component, the distribution
+ list
+
+ < 1 3 >
+
+ says that this route may be redistributed to both AS 1 and AS 3.
+ Finally, the degree of preference assigned to any route which matches
+ this policy is set to 10.
+
+ To improve readability, the above policy can be rewritten as:
+
+ AS 2: < ANY > < (1 | 3) ANY* > < IGP > < 1 3 > = 10
+
+ Next, consider AS 3. It is willing to provide transit service to AS
+ 4 and AS 5, presumably due to multilateral agreements. AS 3 should
+ set its policy as follows:
+
+ AS 3: < ANY > < (4 | 5) > < IGP > < 2 4 5 > = 10
+ AS 3: < ANY > < 2 .* > < ANY > < 4 5 > = 10
+ AS 3: < ANY > < 3 > < ANY > < 2 4 5 > = 10
+
+ This would allow AS 3 to distribute internal routes received from ASs
+ 4 and 5 to ASs 2, 4, and 5, and all backbone routes through AS 2
+ would be distributed to ASs 4 and 5. AS 3 would advertise its own
+ networks to ASs 2, 4, and 5. Hosts in AS 4 and AS 5 would be able to
+ reach each other, as well as hosts in ASs 1 and 3 and anything beyond
+ them. AS 3 allows any origin in routes from AS 2. This implies that
+ AS 3 trusts AS 2 to impose policy on routes imported by means other
+ than BGP. Note that although the policy statement would appear to
+ allow AS 3 to send ASs 4 and 5 their own routes, the BGP protocol
+ would detect this as a routing loop and prevent it.
+
+
+
+Interconnectivity Working Group [Page 14]
+
+RFC 1164 BGP - Application June 1990
+
+
+ Now consider AS 1. AS 1 wishes to use the backbone service provided
+ by AS 2, and is willing to carry transit traffic for AS 4. The
+ policy statements for AS 1 might read:
+
+ AS 1: < ANY > < 4 > < IGP > < 2 > = 150
+ AS 1: < ANY > < 2 .* > < ANY > < 4 > = 150
+ AS 1: < ANY > < 1 > < ANY > < 2 4 > = 150
+
+ AS 1 will redistribute all routes learned from the AS 2 backbone to
+ AS 4, and vice versa, and distribute routes to its own networks to
+ both AS 2 and AS 4. The degree of preference assigned to any route
+ which matches this policy is set to 150.
+
+ AS 5 is a more interesting case. AS 5 wishes to use the backbone
+ service, but is not directly connected to AS 2. Its policy
+ statements could be as follows:
+
+ AS 5: < ANY > < 3 4 > < IGP > < > = 10
+ AS 5: < ANY > < 3 2 .* > < . > < > = 10
+ AS 5: < ANY > < 5 > < . > < 3 > = 10
+
+ This policy imports routes through AS 2 and AS 3 into AS 5, and
+ allows AS 5 and AS 4 to communicate through AS 3. Since AS 5 does
+ not redistribute any routes other than its own, it is a stub AS.
+ Note that AS 5 does not trust AS 3 to advertise only routes through
+ AS 2, and thus applies its own filter to ensure that it only uses the
+ backbone. This lack of trust makes it necessary to add the second
+ policy term.
+
+ AS 4 is a good example of a multihomed AS. AS 4 wishes to use AS 3
+ as is primary path to the backbone, with AS 1 as a backup.
+ Furthermore, AS 4 does not wish to provide any transit service
+ between ASs 1 and 3. Its policy statement could read:
+
+ AS 4: < ANY > < 3 .* > < ANY > < > = 10
+ AS 4: < ANY > < 1 .* > < ANY > < > = 20
+ AS 4: < ANY > < 4 > < ANY > < 1 3 > = 10
+
+ Paths to any network through AS 3 are preferred, but AS 1 will be
+ used as a backup if necessary. Note that since AS 4 trusts AS 3 to
+ provide it with reasonable routes, it is not necessary to explicitly
+ import routes from AS 5. Since the redistribution terms are null
+ except for networks within AS 4, AS 4 will never carry any transit
+ traffic.
+
+ Given the topology and policies described above, it becomes apparent
+ that two paths of equal preference would be available from AS 2 to
+ any of the networks in AS 4. Since ties are not allowed, an
+
+
+
+Interconnectivity Working Group [Page 15]
+
+RFC 1164 BGP - Application June 1990
+
+
+ arbitrary tie-breaking mechanism would come into play (as described
+ above), which might result in less than optimal routes to some
+ networks. An alternative mechanism that would provide optimal routes
+ while still allowing fallback paths would be to provide network-by-
+ network policies in specific cases, and explicit tie-breaking
+ policies for the remaining networks. For example, the policies for
+ AS 2 could be rewritten as follows:
+
+ AS 2: < 35 > < 1 .* > < IGP > < 3 > = 10
+ AS 2: < 35 > < 3 .* > < IGP > < 1 > = 20
+ AS 2: < ANY > < 1 .* > < IGP > < 3 > = 20
+ AS 2: < ANY > < 3 .* > < IGP > < 1 > = 10
+
+ Paths to network 35 through AS 1 would be preferred, with AS 3 as a
+ fallback; paths to all other networks through AS 3 would be preferred
+ over those through AS 1. Such optimizations may become arbitrarily
+ complex.
+
+ There may be other, simpler ways to assign a degree of preference to
+ an AS path.
+
+ The simplest way to assign a degree of preference to a particular
+ path is to use the number of ASs in the AS path as the degree of
+ preference. This approach reflects the heuristic that shorter paths
+ are usually better than longer ones. This policy can be implemented
+ by using the PathLength() built-in function in the following policy
+ statement:
+
+ < ANY > < .* > < ANY > < ANY > = PathLength(ASpath)
+
+ This policy assigns to any network with an arbitrary AS path a degree
+ of preference equal to the number of ASs in the AS path; it then
+ redistributes this information to all other BGP speakers. As an
+ example, an AS path which traverses three different Autonomous
+ Systems will be assigned the degree of preference 3.
+
+ Another approach is to assign a certain degree of preference to each
+ individual AS, and then determine the degree of preference of a
+ particular AS path as the sum of the degree of preferences of the ASs
+ in that path. Note that this approach does not require the
+ assignment of a specific degree of preference to every AS in the
+ Internet. For ASs with an unknown degree of preference, a default
+ can be used. This policy can be implemented by using the
+ PathWeight() built-in function in the following policy statement:
+
+ < ANY > < .* > < ANY > < ANY >
+ = PathWeight(ASpath, ASWeightTable)
+
+
+
+
+Interconnectivity Working Group [Page 16]
+
+RFC 1164 BGP - Application June 1990
+
+
+ As an example, if Autonomous Systems 145 and 55 have 10 and 15 as
+ their weights in the ASWeightTable, and if the default degree of
+ preference in the ASWeightTable is 50, then an AS path that traverses
+ Autonomous Systems 145, 164, and 55 will be assigned degree of
+ preference 75.
+
+ The above examples demonstrate some of the simple policies that can
+ be implemented with BGP. In general, very sophisticated policies
+ based on partial or complete AS path discrimination can be written
+ and enforced. It should be emphasized that movement toward more
+ sophisticated policies will require parallel effort in creating more
+ sophisticated tools for policy interaction analysis.
+
+5. The Interaction of BGP and an IGP
+
+5.1 Overview
+
+ By definition, all transit ASs must be able to carry traffic external
+ to that AS (neither the source nor destination host belongs to the
+ AS). This requires a certain degree of interaction and coordination
+ between the Interior Gateway Protocol (IGP) used by that particular
+ AS and BGP. In general, traffic exterior to a given AS is going to
+ pass through both interior gateways (gateways that support IGP only)
+ and border gateways (gateways that support both IGP and BGP). All
+ interior gateways receive information about external routes from one
+ or more of the border gateways of the AS via the IGP.
+
+ Depending on the mechanism used to propagate BGP information within a
+ given AS, special care must be taken to ensure consistency between
+ BGP and the IGP, since changes in state are likely to propagate at
+ different rates across the AS. There may be a time window between
+ the moment when some border gateway (A) receives new BGP routing
+ information which was originated from another border gateway (B)
+ within the same AS, and the moment the IGP within this AS is capable
+ of routing transit traffic to that border gateway (B). During that
+ time window, either incorrect routing or "black holes" can occur.
+
+ In order to minimize such routing problems, border gateway (A) should
+ not advertise a route to some exterior network X to all of its BGP
+ neighbors in other ASs until all of the interior gateways within the
+ AS are ready to route traffic destined to X via the correct exit
+ border gateway (B). In other words, interior routing should converge
+ on the proper exit gateway before advertising routes via that exit
+ gateway to other ASs.
+
+5.2 Methods for Achieving Stable Interactions
+
+ The following discussion outlines several techniques capable of
+
+
+
+Interconnectivity Working Group [Page 17]
+
+RFC 1164 BGP - Application June 1990
+
+
+ achieving stable interactions between BGP and the IGP within an
+ Autonomous System.
+
+5.2.1 Propagation of BGP Information via the IGP
+
+ While BGP can provide its own mechanism for carrying BGP information
+ within an AS, one can also use an IGP to transport this information,
+ as long as the IGP supports complete flooding of routing information
+ (providing the mechanism to distribute the BGP information) and one-
+ pass convergence (making the mechanism effectively atomic). If an
+ IGP is used to carry BGP information, then the period of
+ desynchronization described earlier does not occur at all, since BGP
+ information propagates within the AS synchronously with the IGP, and
+ the IGP converges more or less simultaneously with the arrival of the
+ new routing information. Note that the IGP only carries BGP
+ information and should not interpret or process this information.
+
+5.2.2 Tagged Interior Gateway Protocol
+
+ Certain IGPs can tag routes exterior to an AS with the identity of
+ their exit points while propagating them within the AS. Each border
+ gateway should use identical tags for announcing exterior routing
+ information (received via BGP) both into the IGP and into Internal
+ BGP when propagating this information to other border gateways within
+ the same AS. Tags generated by a border gateway must uniquely
+ identify that particular border gateway--different border gateways
+ must use different tags.
+
+ All Border Gateways within a single AS must observe the following two
+ rules:
+
+ 1. Information received via Internal BGP by a border gateway A
+ declaring a network to be unreachable must immediately be
+ propagated to all of the External BGP neighbors of A.
+
+ 2. Information received via Internal BGP by a border gateway A about
+ a reachable network X cannot be propagated to any of the External
+ BGP neighbors of A unless/until A has an IGP route to X and both
+ the IGP and the BGP routing information have identical tags.
+
+ These rules guarantee that no routing information is announced
+ externally unless the IGP is capable of correctly supporting it. It
+ also avoids some causes of "black holes".
+
+ One possible method for tagging BGP and IGP routes within an AS is to
+ use the IP address of the exit border gateway announcing the exterior
+ route into the AS. In this case the "gateway" field in the BGP
+ UPDATE message is used as the tag.
+
+
+
+Interconnectivity Working Group [Page 18]
+
+RFC 1164 BGP - Application June 1990
+
+
+5.2.3 Encapsulation
+
+ Encapsulation provides the simplest (in terms of the interaction
+ between the IGP and BGP) mechanism for carrying transit traffic
+ across the AS. In this approach, transit traffic is encapsulated
+ within an IP datagram addressed to the exit gateway. The only
+ requirement imposed on the IGP by this approach is that it should be
+ capable of supporting routing between border gateways within the same
+ AS.
+
+ The address of the exit gateway A for some exterior network X is
+ specified in the "gateway" field of the BGP UPDATE message received
+ from gateway A via Internal BGP by all other border gateways within
+ the same AS. In order to route traffic to network X, each border
+ gateway within the AS encapsulates it in datagrams addressed to
+ gateway A. Gateway A then performs decapsulation and forwards the
+ original packet to the proper gateway in another AS.
+
+ Since encapsulation does not rely on the IGP to carry exterior
+ routing information, no synchronization between BGP and the IGP is
+ required.
+
+ Some means of identifying datagrams containing encapsulated IP, such
+ as an IP protocol type code, must be defined if this method is to be
+ used.
+
+ Note, that if a packet to be encapsulated has length that is very
+ close to the MTU, that packet would be fragmented at the gateway that
+ performs encapsulation.
+
+5.2.4 Other Cases
+
+ There may be ASs with IGPs which can neither carry BGP information
+ nor tag exterior routes (e.g., RIP). In addition, encapsulation may
+ be either infeasible or undesirable. In such situations, the
+ following two rules must be observed:
+
+ 1. Information received via Internal BGP by a border gateway A
+ declaring a network to be unreachable must immediately be
+ propagated to all of the External BGP neighbors of A.
+
+ 2. Information received via Internal BGP by a border gateway A about
+ a reachable network X cannot be propagated to any of the External
+ BGP neighbors of A unless A has an IGP route to X and sufficient
+ time (holddown) has passed for the IGP routes to have converged.
+
+ The above rules present necessary (but not sufficient) conditions for
+ propagating BGP routing information to other ASs. In contrast to
+
+
+
+Interconnectivity Working Group [Page 19]
+
+RFC 1164 BGP - Application June 1990
+
+
+ tagged IGPs, these rules cannot ensure that interior routes to the
+ proper exit gateways are in place before propagating the routes to
+ other ASs.
+
+ If the convergence time of an IGP is less than some small value X,
+ then the time window during which the IGP and BGP are unsynchronized
+ is less than X as well, and the whole issue can be ignored at the
+ cost of transient periods (of less than length X) of routing
+ instability. A reasonable value for X is a matter for further study,
+ but X should probably be less than one second.
+
+ If the convergence time of an IGP cannot be ignored, a different
+ approach is needed. Mechanisms and techniques which might be
+ appropriate in this situation are subjects for further study.
+
+6. Implementation Recommendations
+
+6.1 Multiple Networks Per Message
+
+ The BGP protocol allows for multiple networks with the same AS path
+ and next-hop gateway to be specified in one message. Making use of
+ this capability is highly recommended. With one network per message
+ there is a substantial increase in overhead in the receiver. Not
+ only does the system overhead increase due to the reception of
+ multiple messages, but the overhead of scanning the routing table for
+ flash updates to BGP peers and other routing protocols (and sending
+ the associated messages) is incurred multiple times as well. One
+ method of building messages containing many networks per AS path and
+ gateway from a routing table that is not organized per AS path is to
+ build many messages as the routing table is scanned. As each network
+ is processed, a message for the associated AS path and gateway is
+ allocated, if it does not exist, and the new network is added to it.
+ If such a message exists, the new network is just appended to it. If
+ the message lacks the space to hold the new network, it is
+ transmitted, a new message is allocated, and the new network is
+ inserted into the new message. When the entire routing table has
+ been scanned, all allocated messages are sent and their resources
+ released. Maximum compression is achieved when all networks share a
+ gateway and common path attributes, making it possible to send many
+ networks in one 4096-byte message.
+
+6.2 Preventing Excessive Resource Utilization
+
+ When peering with a BGP implementation that does not compress
+ multiple networks into one message, it may be necessary to take steps
+ to reduce the overhead from the flood of data received when a peer is
+ acquired or a significant network topology change occurs. One method
+ of doing this is to rate limit flash updates. This will eliminate
+
+
+
+Interconnectivity Working Group [Page 20]
+
+RFC 1164 BGP - Application June 1990
+
+
+ the redundant scanning of the routing table to provide flash updates
+ for BGP peers and other routing protocols. A disadvantage of this
+ approach is that it increases the propagation latency of routing
+ information. By choosing a minimum flash update interval that is not
+ much greater than the time it takes to process the multiple messages,
+ this latency should be minimized.
+
+6.3 Processing Messages on a Stream Protocol
+
+ Due to the stream nature of TCP, all the data for received messages
+ does not necessarily arrive at the same time, due to the nature of
+ TCP. This can make it difficult to process the data as messages,
+ especially on systems such as BSD Unix where it is not possible to
+ determine how much data has been received but not yet processed. One
+ method that can be used in this situation is to first try to read
+ just the message header. For the KeepAlive message type, this is a
+ complete message; for other message types, the header should first be
+ verified, in particular the total length. If all checks are
+ successful, the specified length, minus the size of the message
+ header is the amount of data left to read. An implementation that
+ would "hang" the routing information process while trying to read
+ from a peer could set up a message buffer (1024 bytes) per peer and
+ fill it with data as available until a complete message has been
+ received.
+
+6.4 Processing Update Messages
+
+ In BGP, all Update messages are incremental. Once a particular
+ network is listed in an Update message as being reachable through an
+ AS path and gateway, that piece of information is expected to be
+ retained indefinitely. In order for a route to a network to be
+ removed, it must be explicitly listed in an Update message as being
+ unreachable or with new routing information to replace the old. Note
+ that a BGP peer will only advertise one route to a given network, so
+ any announcement of that network by a particular peer replaces any
+ previous information about that network received from the same peer.
+
+ This approach has the obvious advantage of low overhead; if all
+ routes are stable, only KeepAlive messages will be sent. There is no
+ periodic flood of route information.
+
+ However, this means that a consistent view of routing information
+ between BGP peers is only possible over the course of a single
+ transport connection, since there is no mechanism for a complete
+ update. This requirement is accommodated by specifying that BGP
+ peers must transition to the Idle state upon the failure of a
+ transport connection.
+
+
+
+
+Interconnectivity Working Group [Page 21]
+
+RFC 1164 BGP - Application June 1990
+
+
+7. 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. It is hoped that the
+ guidelines presented here will provide a starting point for more
+ sophisticated and manageable routing in the Internet as it grows.
+
+References
+
+ [1] Lougheed, K. and Y. Rekhter, "A Border Gateway Protocol", RFC
+ 1163, cisco Systems and IBM Watson Research Center, June 1990.
+
+ [2] Braun, H-W., "Models of Policy Based Routing", RFC 1104,
+ Merit/NSFNET, June 1989.
+
+ [3] Clark, D., "Policy Routing in Internet Protocols", RFC 1102,
+ M.I.T., May 1989.
+
+Security Considerations
+
+ Security issues are not discussed in this memo.
+
+Authors' Addresses
+
+ Jeffrey C. Honig
+ Theory Center
+ 265 Olin Hall
+ Cornell University
+ Ithaca, NY 14853-5201
+
+ Phone: (607) 255-8686
+
+ Email: JCH@TCGOULD.TN.CORNELL.EDU
+
+
+ Dave Katz
+ Merit/NSFNET
+ 1075 Beal Ave.
+ Ann Arbor, MI 48109
+
+ Phone: (313) 763-4898
+
+ Email: DKATZ@MERIT.EDU
+
+
+
+
+
+
+
+Interconnectivity Working Group [Page 22]
+
+RFC 1164 BGP - Application June 1990
+
+
+ Matt Mathis
+ Pittsburgh Supercomputing Center
+ 4400 Fifth Ave.
+ Pittsburgh, PA 15213
+
+ Phone: (412) 268-3319
+
+ Email: MATHIS@FARADAY.ECE.CMU.EDU
+
+
+ Yakov Rekhter
+ T.J. Watson Research Center
+ IBM Corporation
+ P.O. Box 218
+ Yorktown Heights, NY 10598
+
+ Phone: (914) 945-3896
+
+ Email: YAKOV@IBM.COM
+
+
+ Jie Yun (Jessica) Yu
+ Merit/NSFNET
+ 1075 Beal Ave.
+ Ann Arbor, MI 48109
+
+ Phone: (313) 936-3000
+
+ Email: JYY@MERIT.EDU
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Interconnectivity Working Group [Page 23]
+ \ No newline at end of file