RFC 1164

Application of the Border Gateway Protocol in the Internet 🌈

okay bestie, let's get into this 🦋

Here's the header tea ☕. This doc lives in the Network Working Group and it's RFC 1164, dated June 1990. It has five authors 💅:

• J. Honig, Cornell Univ. Theory Center
• D. Katz, Merit/NSFNET
• M. Mathis, Pittsburgh Supercomputing Center
• Y. Rekhter, T.J. Watson Research Center, IBM Corp
• J. Yu, Merit/NSFNET

It's a Proposed Standard (the Status section spells that out, it's giving). The header doesn't list anything it obsoletes or updates, so there's no drama there 🙈.

Status of this Memo 📜

So this RFC and its companion, RFC-1163 ("A Border Gateway Protocol (BGP)"), together define a Proposed Standard for an inter-autonomous system routing protocol for the Internet 🌸.

Like any protocol at this early stage, this one may change before it reaches full Internet Standard status, because of what people learn from actually deploying it 🔥. Implementers are encouraged to keep an eye on this protocol (or any protocol) as it moves through standardization, and to report their own experience with it 🫶.

This protocol is being considered by the Interconnectivity Working Group (IWG) of the Internet Engineering Task Force (IETF). You can follow BGP's progress or report on it through the IWG mailing list, IWG@nri.reston.va.us 💌.

For the current state and status of standard Internet protocols, check the latest "IAB Official Protocol Standards" RFC 📚.

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
   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 🫶

Huge thanks to 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 🌸

BGP, described in RFC 1163, is an interdomain routing protocol 🛣️. The network reachability info exchanged over BGP is enough to detect routing loops and to enforce routing decisions based on performance preference and policy constraints, as outlined in RFC 1104 [2].

This memo uses the term "Autonomous System" all the way through. The classic definition of an Autonomous System is a set of routers under one technical administration. Inside the AS they use an interior gateway protocol and common metrics to route packets, and to send packets to other ASs they use an exterior gateway protocol 🧠. Since that classic definition came out, it's become super common for one AS to run several interior gateway protocols and sometimes several sets of metrics. The point of the term here is that even with multiple IGPs and metrics, the administration of an AS still looks to other ASs like one coherent interior routing plan, and it gives a consistent picture of which networks are reachable through it ✨. From the outside, an AS is basically monolithic: reachability to networks directly connected to the AS must be equivalent from all border gateways of the AS.

This paper talks about using BGP in the Internet environment. We'll cover topology, how BGP and IGPs interact, and how policy rules get enforced with BGP 🎀.

All the discussions here are based on one assumption: the Internet is a collection of arbitrarily connected Autonomous Systems. Each AS is assumed to be run by a single administrative entity, at least for the purposes of representing its routing information to systems outside the AS 💅.

3. BGP Theory and Application 🦋

3.1 Topological Model 🗺️

Throughout this paper we're looking at a general graph where the nodes are ASs and the edges are connections between pairs of ASs. We already talked about what an AS is back in Section 2. When we say a connection exists between two ASs, we mean two things at once 👑:

physical connection: there's a shared network between the two ASs, and on that shared network each AS has at least one border gateway that belongs to it. So the border gateway of each AS can forward packets to the border gateway of the other AS without needing Inter-AS or Intra-AS routing 🚀.

BGP connection: there's a BGP session between BGP speakers in each of the ASs, and this session tells each connected AS which routes, through the physically connected border gateways of the other AS, can be used for specific networks 🧵. For this document we add one extra restriction on the BGP speakers that make up the BGP connection: they must themselves share the same network that their border gateways share. That way, a BGP session between adjacent ASs doesn't need any support from Inter-AS or Intra-AS routing. Cases that don't follow this restriction are outside the scope of this document 🙅‍♀️.

So at each connection, each AS has one or more BGP speakers and one or more border gateways, and all of those BGP speakers and border gateways sit on a shared network 🌈. On a given connection, only the AS's border gateways on that connection's shared network may be used by that AS's BGP speakers on that same 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 that same connection. In all BGP usage, we intend that the flow of packets from one AS to the other corresponds to the advertised AS paths 🧭.

A lot of the traffic inside an AS either starts or ends at that AS. (In other words, either the source or the destination IP address of the packet identifies a host on a network directly connected to that AS.) This is called "local traffic" 🏠. Traffic that doesn't fit that description is called "transit traffic" 🚗. A big goal of BGP usage is controlling the flow of transit traffic 💜.

Depending on how an AS handles transit traffic, it falls into one of these 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 is an efficient, straightforward way to suppress routing loops, and it gets rid of the "count-to-infinity" problem that some distance vector algorithms have, BGP doesn't impose any topological restrictions on how ASs get interconnected 🙌.

3.2 BGP in the Internet 🌐

3.2.1 Topology Considerations 🧩

The overall Internet topology can be seen as an arbitrary mix of transit, multihomed, and stub ASs 🕸️. To keep the impact on the current Internet infrastructure small, stub and multihomed ASs don't need to use BGP. They can run other protocols (e.g., EGP) to swap reachability information with transit ASs, and the transit ASs then tag that info as having been learned via EGP or some other method 🏷️. Not running BGP on stub or multihomed ASs doesn't hurt the overall quality of inter-AS routing for traffic that isn't local to those stub or multihomed ASs 💯.

BGP can still be used for stub and multihomed ASs too 💫. That gives them an edge in bandwidth and performance over some of the protocols in use today (like EGP). It would also mean less reliance on defaults and better choices of Inter-AS routes for multihomed ASs 🎯.

3.2.2 Global Nature of BGP 🌍

At a global level, BGP is what distributes routing information among multiple Autonomous Systems. The information flows look like this 👀:

                          +--------+       +--------+
                    BGP   |  BGP   |  BGP  |  BGP   |  BGP
                  --------+        +-------+        +-------
                          |  IGP   |       |  IGP   |
                          +--------+       +--------+

                         {___AS A___}     {___AS B___}

This diagram shows that BGP on its own carries information between ASs, while a combination of BGP and an IGP carries information across an AS. Making sure routing information stays consistent between BGP and an IGP inside an AS is a big deal, and the paper goes into it at length later on 🔥.

Part 1 of 5 is a wrap 🎀. More parts are coming, so stay tuned, bestie 🦋✨

3.2.3. BGP Neighbor Relationships

Okay so, remember how the Internet is basically a bunch of Autonomous Systems (ASs) connecting in whatever random way they like? ✨ BGP gateways inside each AS talk to each other to swap "hey, I can reach this network" info, and they base that on policies each AS sets up for itself 🦋. Computers that talk directly to each other over BGP are called BGP neighbors 💖. Neighbors can be in the same AS or in different ASs. To keep things simple, we call BGP chats with neighbors in different ASs External BGP, and chats with neighbors in the same AS Internal BGP 🎀.

External BGP: For External BGP, the BGP neighbors MUST belong to different ASs, but they share a common network 🌸. That common network SHOULD be used to carry the BGP messages between them. Using BGP across an intervening AS invalidates the AS path information 💀. Also, an Autonomous System number MUST be used with BGP to say 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, it needs multiple BGP gateways. All BGP gateways representing the same AS MUST give a consistent image of the AS to the outside world 👑. That means the gateways need consistent routing information among themselves. They can talk to each other via BGP or by other means ✨. And the policy constraints applied to all BGP gateways within an AS MUST be consistent 🫶.

---

3.3. Policy Making with BGP

BGP gives you the ability to enforce some policies based on various preferences and constraints 💅. The AS administration decides these policies and hands them to BGP as configuration information. Inside a BGP speaker, the policies work by affecting which paths get picked from multiple alternatives, and by controlling how routing information gets redistributed 🔥. Policies are not directly encoded in the protocol 🙈.

Non-technical constraints are all about political, security, or economic considerations 🌈. For example, if an AS is unwilling to carry traffic to another AS, it can enforce a policy that prohibits it. Here are some non-technical constraints you can enforce with BGP:

1. A multihomed AS can refuse to act as a transit AS for other ASs. (It does this by not advertising routes to networks other than the ones directly connected to it 🙅‍♀️.)
2. A multihomed AS can become a transit AS by letting a certain set of ASs use it as one. (It does this by advertising routes to networks to that set of ASs ✨.)
3. An AS can favor or disfavor certain ASs for carrying its transit traffic to networks advertised with competing AS paths 💜.

There are also performance-related criteria you can control with 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 figures out, using BGP, that two or more AS paths can reach a given destination, it can use a variety of means to decide which candidate AS path it'll actually use 🧐. The quality of an AS can be measured by things like diameter, link speed, capacity, tendency to get congested, and quality of operation. Info about these qualities might come from somewhere other than BGP 🦋.
3. Preferring internal routes over external routes 🏡.

Honestly? Non-technical policy will typically override performance issues 👑. It's giving politics over speed, and that's just how it goes 💀.

Now, for consistency, combinations of policies and route selection procedures that might end up with equal cost paths MUST be resolved in a deterministic fashion 🔒. Otherwise you get chaos.

Fundamental to BGP usage is the rule that an AS advertises to its neighboring ASs only the routes that it actually uses 🌸. This rule reflects the "hop-by-hop" routing paradigm that the current Internet generally uses. Note that some policies can't be supported by the "hop-by-hop" routing paradigm, and those require techniques like source routing to enforce 😭. For example, BGP doesn't let one AS send traffic to a neighbor AS and have that traffic take a different route from the one taken by traffic originating in the neighbor AS 🙃. On the flip side, BGP can support any policy that conforms to the "hop-by-hop" routing paradigm 💖. Since the current Internet uses only "hop-by-hop" routing, and BGP can support any policy that fits 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 jobs of a BGP speaker for a given AS, at a given connection, is to evaluate the different paths to a destination network from its border gateways at that connection, pick the best one, and then advertise it to all of its BGP neighbors at that same connection (subject to policy constraints) 💅. The key question is how those different paths get evaluated and compared 🤔.

In traditional distance vector protocols (like RIP), there's only one metric (like hop count) associated with a path 🦋. So comparing paths just comes down to comparing two numbers 🔢. Here's the complication with Inter-AS routing: there's no universally agreed-upon metric among ASs that can be used to evaluate external paths 😩. Instead, each AS may have its own set of criteria for path evaluation 🌈.

A BGP speaker within an Autonomous System builds a routing database that consists of the set of all feasible paths and the list of networks reachable through each path 🗂️. In an efficient implementation, it's important to store and process these paths and bundle together the networks reachable through them 🧠. For precise discussion, though, it's useful to think about the set of feasible paths for one given destination network 🎯. In most cases, we'd expect to find only one feasible path in the set. But this often isn't the case 🙈. All feasible paths MUST be maintained, and maintaining them speeds up adaptation when the primary path is lost, but only the primary path at any given time will ever be advertised 🔥.

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 with a function that maps each full AS path to a non-negative integer, which denotes that path's degree of preference 🔢. Path selection then reduces to applying this function to all feasible paths and choosing the one with the highest degree of preference 🏆.

In actual BGP implementations, the criteria for assigning degrees of preference 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 where 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 😭. Stable paths over sketchy ones, bestie 🫶.
• 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, so they should be treated very carefully 🙀.
• Policy consideration. BGP supports policy-based routing, based 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 aren't considered any further 🚫.

Metrics based on compound criteria can be computed as a weighted combination of the degrees of preference of the primitive criteria ⚖️. The use of compound criteria should be done with extreme caution, since it involves comparing potentially uncomparable quantities 🙃💀. Proceed with care, besties, it's a whole mess out there 🌸✨.

4.2. Syntax and Semantics for BGP Configuration Files ✨

okay so a big job in BGP is deciding how much you like each available AS-path 💅 That "degree of preference" is usually a function of how many ASs are in the path, properties of the specific ASs in it, where the route originated, and properties of the specific border router you'll use for the first hop 🧚 In this section we look at how a network admin might spell out that function in a configuration file. Someday we could maybe use tools built on network management protocols like SNMP for this, but the protocols don't support that ability yet 🥺

Besides picking the best path to a given network, the admin also has to control how that best path gets advertised to neighboring ASs 📣 So path selection and path distribution are the two key bits of policy expression in BGP usage. ✨

Different parts of one AS's policy interact, and the policies of different ASs interact too. That's why it's important to make analyzing those interactions easy with high-quality, consistent tools 🔍

We also need tools that translate the admin's policy into some technical mechanism inside a BGP speaker, so the policy actually gets carried out 🛠️

All of this suggests there should be a globally consistent way of describing policies in the configuration file. The syntax and semantics should be able to express path selection within the local AS, as well as path redistribution to other ASs. 🎀

Because it may be desirable to coordinate routing policy at an external level, it may prove worthwhile to create a language that describes this information in a globally consistent way. Policies written in such a language could conceivably be used by high-level tools to analyze the interactions 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, is the most important mechanism for policy enforcement. Assigning a degree of preference to a particular AS path can be modelled as a matching between that path and one or more predefined AS path patterns. Each predefined AS path pattern has a degree of preference, which gets assigned to any AS path that matches it. 💜

Since patterns are naturally expressed by regular expressions, you can use regular expressions over the alphabet of AS numbers to define AS path patterns, and therefore to formulate policies. 🧠

Since certain constructs show up a lot 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 *, 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.
• {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. So 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, and the origin of the possibility must be a member of the origin set. If these conditions are all met, the route denoted by the possibility is accepted as a possible route to the networks in the intersection of the possibility's 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>. ✨

<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, and ANY denotes the set of all origins. 👑

<distribution-list> ::= '<' { AS } '>' |
                        '<' ANY '>'

Semantics: if a given possibility was accepted and installed into the routing table, then the distribution-list is the set of (neighboring) autonomous systems whose border routers we will distribute the BGP-derived routes to. 🦋

<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 how preferred the possibility is, 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 the weights of the ASs in the AS path as defined by the AS weight table. To preserve determinism, the AS weight table must always have a default weight, which will be assigned to any AS that is not in that table. 🧚

The AS path, as used above, is constructed from right to left (which is consistent with BGP), so 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 first match wins, so order your policy-terms from most specific to most general or you'll be sad later 😭

The semantics of a matched policy are as follows: if a network in <network-list> that was originally introduced into BGP from <origin> is received via <AS-path>, then 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 belong 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 it 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

Let's break that down, bestie 🤓

• 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 that 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 let AS 3 pass the internal routes it hears from ASs 4 and 5 along to ASs 2, 4, and 5, and all the backbone routes coming through AS 2 would get shared with ASs 4 and 5 🧚 AS 3 also tells ASs 2, 4, and 5 about its own networks 💅 Hosts in AS 4 and AS 5 can reach each other, plus hosts in ASs 1 and 3 and anything beyond them 🌸 AS 3 allows any origin in routes from AS 2, which implies that AS 3 trusts AS 2 to impose policy on routes imported by means other than BGP 🫶 Ngl, the policy statement looks like it would let AS 3 send ASs 4 and 5 their own routes back, but BGP would catch that as a routing loop and shut it down 🙈

Now let's talk about AS 1 💖 It wants to use the backbone service that AS 2 provides, and it's willing to carry transit traffic for AS 4. Its policy statements might look like this:

AS 1: < ANY > < 4 > < IGP > < 2 > = 150
AS 1: < ANY > < 2  .* > < ANY > < 4 > = 150
AS 1: < ANY > < 1 > < ANY > < 2  4 > = 150

AS 1 redistributes all routes learned from the AS 2 backbone to AS 4, and vice versa, and distributes routes to its own networks to both AS 2 and AS 4 🎀 Any route that matches this policy gets a degree of preference of 150. Slay.

AS 5 is a more interesting case 👑 It wants the backbone service too, but it isn't directly connected to AS 2. Its policy statements could look like this:

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 lets AS 5 and AS 4 communicate through AS 3 🦋 Since AS 5 doesn't redistribute any routes other than its own, it's a stub AS. Note that AS 5 doesn't trust AS 3 to advertise only routes through AS 2, so it applies its own filter to make sure it only uses the backbone 😭 That lack of trust is why the second policy term is needed.

AS 4 is a great example of a multihomed AS 🍓 It wants AS 3 as its primary path to the backbone, with AS 1 as a backup. AS 4 also doesn't want to provide any transit service between ASs 1 and 3 🙅

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 gets used as a backup if it's needed 🌈 Since AS 4 trusts AS 3 to provide reasonable routes, it doesn't need to explicitly import routes from AS 5. And because the redistribution terms are null except for networks within AS 4, AS 4 will never carry any transit traffic 💀 Lowkey iconic.

Okay, now the tea ☕ Given the topology and policies described above, it becomes clear 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 arbitrary tie-breaking mechanism would come into play (as described above), which might result in less than optimal routes to some networks 😬 A better alternative that still allows fallback paths would be to provide network-by-network policies in specific cases, plus explicit tie-breaking policies for the remaining networks. For example, the policies for AS 2 could be rewritten like this:

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, bestie 😵

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, and then redistributes this information to all other BGP speakers 🔥 As an example, an AS path that traverses three different Autonomous Systems will be assigned the degree of preference 3. Simple, clean, iconic.

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 degrees of preference of the ASs in that path 🎀 Note that this approach doesn't require assigning 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)

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 🧮 (10 + 50 + 15, the math ate ✅)

The examples above show 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 🧠 Periodt.

---

5. The Interaction of BGP and an IGP ✨

5.1 Overview

Okay so by definition, all transit ASs must be able to carry traffic external to that AS (neither the source nor the destination host belongs to the AS) 🚦 This needs a certain degree of interaction and coordination between the Interior Gateway Protocol (IGP) used by that 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 learn 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 keep BGP and the IGP consistent, 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 that 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 window, either incorrect routing or "black holes" can happen 🕳️

To minimize those 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 for 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, you 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, the period of desynchronization described earlier doesn't happen at all, since BGP information propagates within the AS synchronously with the IGP, and the IGP converges more or less at the same time as 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 when 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, so 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 🛡️ They also avoid 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 🎯

5.2.3 Encapsulation

Encapsulation provides the simplest mechanism (in terms of the interaction between the IGP and BGP) 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. 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 doesn't 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 🧩

Heads up, if a packet to be encapsulated has a length that is very close to the MTU, that packet would be fragmented at the gateway that performs encapsulation 😭

5.2.4 Other Cases 🌙

Okay bestie, so there can be ASs running IGPs that can neither carry BGP information nor tag exterior routes (RIP, I'm looking at you 💀). And encapsulation might be either infeasible or undesirable 🙃. In those 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. ⏳

These rules are necessary (but not sufficient) conditions for passing BGP routing information along to other ASs. Unlike tagged IGPs, though, they can't guarantee that the interior routes to the proper exit gateways are in place before the routes get sent out to other ASs. Not ideal, but we work with what we've got 💅

If the convergence time of an IGP is less than some small value X, then the window where the IGP and BGP are out of sync is also less than X, so the whole issue can be ignored. The cost is brief periods of routing instability (shorter than X) 🦋 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 can't be ignored, we need a different approach. Mechanisms and techniques that might be appropriate in that situation are subjects for further study 🧐

---

6. Implementation Recommendations ✨

6.1 Multiple Networks Per Message 📦

The BGP protocol lets you specify multiple networks with the same AS path and next-hop gateway in one message. Making use of this capability is highly RECOMMENDED 🙌 With one network per message, the receiver takes a big overhead hit. It's not just the extra messages coming in, it's also that the overhead of scanning the routing table for flash updates to BGP peers and other routing protocols (and sending the associated messages) gets repeated again and again 😩

One way to build messages with many networks per AS path and gateway, starting from a routing table that isn't organized by AS path, is to build the messages while you scan the table. As each network is processed, a message for the associated AS path and gateway is allocated if it doesn't exist yet, and the new network is added to it. If that message already exists, the new network is just appended. If the message doesn't have room for the new network, it gets transmitted, a new message is allocated, and the new network goes into the new message. Once the whole routing table has been scanned, all the allocated messages are sent and their resources released 🧹 Maximum compression happens when all networks share a gateway and common path attributes, which makes it possible to send many networks in one 4096-byte message. Main character energy ⭐

6.2 Preventing Excessive Resource Utilization 🚦

When you're peering with a BGP implementation that doesn't compress multiple networks into one message, it may be necessary to take steps to reduce the overhead from the flood of data you get when a peer is acquired or a significant network topology change happens. One way to do this is to rate limit flash updates. That gets rid of the redundant scanning of the routing table for flash updates to BGP peers and other routing protocols. The downside is that it increases the propagation latency of routing information. To keep that latency as low as possible, pick a minimum flash update interval that isn't 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 🌊

TCP is a stream, so all the data for a received message doesn't necessarily show up at the same time, because that's just how TCP works 🙃 This can make it hard to process the data as messages, especially on systems like BSD Unix where you can't tell how much data has been received but not yet processed. One approach is to first try to read just the message header. For the KeepAlive message type, that's a complete message. For other message types, the header SHOULD first be verified, especially the total length. If all the checks pass, the specified length minus the size of the message header is the amount of data left to read 🧠

If an implementation would "hang" the routing information process while trying to read from a peer, it can set up a message buffer (1024 bytes) per peer and fill it with data as it becomes available until a complete message has been received. Hang in there, bestie 🫶

6.4 Processing Update Messages 🔄

In BGP, all Update messages are incremental, no cap 💯 Once a network is listed in an Update message as reachable through an AS path and gateway, that info is expected to be retained indefinitely. For a route to a network to be removed, it MUST be explicitly listed in an Update message as unreachable, or come with new routing information that replaces the old. Also note that a BGP peer will only advertise one route to a given network. So any announcement of that network from a particular peer replaces any previous info 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 get sent, and there's no periodic flood of route information 🌸

The catch is that a consistent view of routing information between BGP peers is only possible over the course of a single transport connection, since there's no mechanism for a complete update. So the requirement is handled by specifying that BGP peers MUST transition to the Idle state when a transport connection fails 🔥

---

7. Conclusion 💖

The BGP protocol gives you a high degree of control and flexibility for interdomain routing. It enforces policy and performance constraints and avoids routing loops, which is honestly iconic 👑 It's hoped that the guidelines here give you a starting point for more sophisticated and manageable routing on 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. 😭 Yes, really. Nothing here covers security, so take that seriously when you're deploying anything based on it, periodt.

---

Authors' Addresses 🎀

Jeffrey C. Honig 🦋

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 🌸

Dave Katz
Merit/NSFNET
1075 Beal Ave.
Ann Arbor, MI  48109

Phone:  (313) 763-4898

Email:  DKATZ@MERIT.EDU

Matt Mathis 🧚

Matt Mathis
Pittsburgh Supercomputing Center
4400 Fifth Ave.
Pittsburgh, PA  15213

Phone:  (412) 268-3319

Email:  MATHIS@FARADAY.ECE.CMU.EDU

Yakov Rekhter 💜

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 🌈

Jie Yun (Jessica) Yu
Merit/NSFNET
1075 Beal Ave.
Ann Arbor, MI  48109

Phone:  (313) 936-3000

Email:  JYY@MERIT.EDU