RFC relevance of gateways

As per Relevance of the word gateways, we have this rfc below:

Network Working Group J. Honig, Cornell Univ. Theory
Request for Comments: 1164 D. Katz, Merit/
M. Mathis, Pittsburgh Supercomputing
Y. Rekhter, T.J. Watson Research Center, IBM
J. Yu, Merit/
June 1990

Application of the Border Gateway Protocol in the

Status of this

This RFC, together with its companion RFC-1163, "A Border
Protocol (BGP)", define a Proposed Standard for an inter-
system routing protocol for the Internet

This protocol, like any other at this initial stage, may
modifications before reaching full Internet Standard status as
result of deployment experience. Implementers are encouraged
track the progress of this or any protocol as it moves through
standardization process, and to report their own experience with
protocol

This protocol is being considered by the Interconnectivity
Group (IWG) of the Internet Engineering Task Force (IETF).
Information about the progress of BGP can be monitored and/
reported on the IWG mailing list (IWG@nri.reston.va.us).

Please refer to the latest edition of the "IAB Official
Standards" RFC for current information on the state and status
standard Internet protocols

Distribution of this memo is unlimited

Table of

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.

The authors would like to thank Guy Almes (Rice University),
Lougheed (cisco Systems), Hans-Werner Braun (Merit/NSFNET), Sue
(Merit/NSFNET), and the Interconnectivity Working Group of
Internet Engineering Task Force (chaired by Guy Almes) for
contributions to this paper

2.

The Border Gateway Protocol (BGP), described in RFC 1163, is
interdomain routing protocol. The network reachability
exchanged via BGP provides sufficient information to detect
loops and enforce routing decisions based on performance
and policy constraints as outlined in RFC 1104 [2].

This memo uses the term "Autonomous System" throughout. The
definition of an Autonomous System is a set of routers under a
technical administration, using an interior gateway protocol
common metrics to route packets within the AS, and using an
gateway protocol to route packets to other ASs. Since this
definition was developed, it has become common for a single AS to
several interior gateway protocols and sometimes several sets
metrics within an AS. The use of the term Autonomous System
stresses the fact that, even when multiple IGPs and metrics are used
the administration of an AS appears to other ASs to have a
coherent interior routing plan and presents a consistent picture
what networks are reachable through it. From the standpoint
exterior routing, an AS can be viewed as monolithic: reachability
networks directly connected to the AS must be equivalent from
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,
the enforcement of policy rules with BGP will be presented

All of the discussions in this paper are based on the assumption
the Internet is a collection of arbitrarily connected
Systems. The AS is assumed to be administered by a
administrative entity, at least for the purposes of representation
routing information to systems outside of the AS

3. BGP Theory and

3.1 Topological

We will be concerned throughout this paper with a general graph
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
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
belonging to that AS. Thus the border gateway of each AS
forward packets to the border gateway of the other AS
resort to Inter-AS or Intra-AS routing

BGP connection: there is a BGP session between BGP speakers on
of the ASs, and this session communicates to each connected
those routes through the physically connected border gateways
the other AS that can be used for specific networks.
this document we place an additional restriction on the
speakers that form the BGP connection: they must themselves
the same network that their border gateways share. Thus, a
session between the adjacent ASs requires no support from
Inter-AS or Intra-AS routing. Cases that do not conform to
restriction fall outside the scope of this document

Thus, at each connection, each AS has one or more BGP speakers
one or more border gateways, and these BGP speakers and
gateways are all located on a shared network. Only the AS's
gateways on the connection's shared network may be used by that AS'
BGP speakers on that shared network in NEXT_HOP attributes in
messages. Paths announced by a BGP speaker of one AS on a
connection are taken to be feasible for each of the border
of the other AS on the same connection. In all BGP usage, we
that the flow of packets from one AS to the other correspond
advertised AS paths

Much of the traffic carried within an AS either originates

Interconnectivity Working Group [Page 3]

RFC 1164 BGP - Application June 1990

terminates at that AS (i.e., either the source IP address or
destination IP address of the IP packet identifies a host on
network directly connected to that AS). Traffic that fits
description is called "local traffic". Traffic that does not
this description is called "transit traffic". A major goal of
usage is to control the flow of transit traffic

Based on how a particular AS deals with transit traffic, the AS
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
is designed (under certain policy restrictions) to carry
transit and local traffic

Since a full AS path provides an efficient and straightforward way
suppressing routing loops and eliminates the "count-to-infinity
problem associated with some distance vector algorithms, BGP
no topological restrictions on the interconnection of ASs

3.2 BGP in the

3.2.1 Topology

The overall Internet topology may be viewed as an
interconnection of transit, multihomed, and stub ASs. In order
minimize the impact on the current Internet infrastructure, stub
multihomed ASs need not use BGP. These ASs may run other
(e.g., EGP) to exchange reachability information with transit ASs
Transit ASs then tag this information as having been learned via
or some other method. The fact that BGP need not run on stub
multihomed ASs has no negative impact on the overall quality
inter-AS routing for traffic not local to the stub or multihomed
in question

Of course, BGP may be used for stub and multihomed ASs as well
providing advantage in bandwidth and performance over some of
currently used protocols (such as EGP). In addition, this
result in less need for the use of defaults and in better choices
Inter-AS routes for mulitihomed ASs

Interconnectivity Working Group [Page 4]

RFC 1164 BGP - Application June 1990

3.2.2 Global Nature of

At a global level, BGP is used to distribute routing
among multiple Autonomous Systems. The information flows can
represented as follows

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

{___AS A___} {___AS B___}

This diagram points out that, while BGP alone carries
between ASs, a combination of BGP and an IGP carries
across an AS. Ensuring consistency of routing information
BGP and an IGP within an AS is a significant issue and is
at length later in this paper

3.2.3 BGP Neighbor

As discussed in the introduction, the Internet is viewed as a set
arbitrarily connected Autonomous Systems (ASs). BGP gateways in
AS communicate with each other to exchange network
information based on a set of policies established within each AS
Computers that communicate directly with each other via BGP are
as BGP neighbors. BGP neighbors can be located within the same AS
in different ASs. For the sake of discussion, BGP
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
belong to different ASs, but share a common network. This
network should be used to carry the BGP messages between them
The use of BGP across an intervening AS invalidates the AS
information. An Autonomous System number must be used with BGP
specify which Autonomous System the BGP speaker belongs to

Internal BGP There can be as many BGP gateways as deemed
within an AS. Usually, if an AS has multiple connections to
ASs, multiple BGP gateways are needed. All BGP
representing the same AS must give a consistent image of the AS
the outside. This requires that the BGP gateways have
routing information among them. These gateways can
with each other via BGP or by other means. The policy
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 provides the capability of enforcing some policies based
various preferences and constraints. Policies are determined by
AS administration and are provided to BGP in the form
configuration information. These policies are enforced within a
speaker by affecting the selection of paths from
alternatives, and by controlling the redistribution of
information. Policies are not directly encoded in the protocol

Non-technical constraints are related to political, security,
economic considerations. For example, if an AS is unwilling to
traffic to another AS, it can enforce a policy prohibiting this.
following examples of non-technical constraints can be enforced
the use of BGP

1. A multihomed AS can refuse to act as a transit AS for
ASs. (It does so by not advertising routes to networks
than those directly connected to it.)

2. A multihomed AS can become a transit AS by allowing a
set of ASs to use it as such. (It does so by
routes to networks to this set of ASs.)

3. An AS can favor or disfavor the use of certain ASs for
transit traffic from itself to networks advertised
competing AS paths

A number of performance-related criteria can be controlled with
use of BGP

1. An AS can minimize the number of transit ASs. (Shorter
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
destination, that AS can use a variety of means to decide
of the candidate AS paths it will use. The quality of an
can be measured by such things as diameter, link speed
capacity, tendency to become congested, and quality
operation. Information about these qualities might
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

Interconnectivity Working Group [Page 6]

RFC 1164 BGP - Application June 1990

procedures that might result in equal cost paths must be resolved
a deterministic fashion

Fundamental to BGP usage is the rule that an AS advertizes to
neighboring ASs only those routes that it uses. This rule
the "hop-by-hop" routing paradigm generally used by the
Internet. Note that some policies that cannot be supported by
"hop-by-hop" routing paradigm and which require such techniques
source routing to enforce. For example, BGP does not enable one
to send traffic to a neighbor AS intending that that traffic take
different route from that taken by traffic originating in
neighbor AS. On the other hand, BGP can support any
conforming to the "hop-by-hop" routing paradigm. Since the
Internet uses only the "hop-by-hop" routing paradigm and since
can support any policy that conforms to that paradigm, BGP is
applicable as an inter-AS routing protocol for the current Internet

4. Operational

4.1 Path

One of the major tasks of a BGP speaker for a given AS at a
connection is to evaluate different paths to a destination
from its border gateways at that connection, select the best one,
then advertise it to all of its BGP neighbors at that same
(subject to policy constraints). The key issue is how
paths are evaluated and compared

In traditional distance vector protocols (e.g., RIP) there is
one metric (e.g., hop count) associated with a path. As such
comparison of different paths is reduced to simply comparing
numbers. A complication in Inter-AS routing arises from the lack
a universally agreed-upon metric among ASs that can be used
evaluate external paths. Rather, each AS may have its own set
criteria for path evaluation

A BGP speaker within an Autonomous System builds a routing
consisting of the set of all feasible paths and the list of
reachable through each path. In an efficient implementation, it
be important to store and process these paths and bundle the
reachable through them. For purposes of precise discussion, however
it's useful to consider the set of feasible paths for a
destination network. In most cases, we would expect to find only
feasible path in the set. This will often, however, not be the case
All feasible paths must be maintained, and their maintenance
adaptation to the loss of the primary path, but only the primary
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
order over the set of all possible paths to a given
network. One way to define this partial order is to define
function that maps each full AS path to a non-negative integer
denotes the path's degree of preference. Path selection is
reduced to applying this function to all feasible paths and
the one with the highest degree of preference

In actual BGP implementations, criteria for assigning degree
preferences to a path can be specified in a configuration file

The process of assigning a degree of preference to a path can
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
AS path and information outside the scope of BGP

The criteria used to assign a degree of preference to a path can
classified as primitive or compound. Possible primitive
include

- AS count. Paths with a smaller AS count are generally better

- Presence or absence of a certain AS or ASs in the path.
means of information outside the scope of BGP, an AS may
some performance characteristics (e.g., bandwidth, MTU, intra
AS diameter) of certain ASs and may try to avoid or
them

- Path origin. A path whose endpoint is internal to the last
on the path (BGP is used over the entire path) is
better than one for which part of the path was learned via
or some other means

- AS path subsets. An AS path that is a subset of a longer
path to the same destination should be preferred over
longer path. Any problem in the shorter path (such as
outage) will also be a problem in the longer path

- Link dynamics. Stable paths should be preferred over
ones. Note that this criterion must be used in a very
way to avoid causing unnecessary route fluctuation. Generally
any criteria that depend on dynamic information might
routing instability and should be treated very carefully

- Policy consideration. BGP supports policy based routing

Interconnectivity Working Group [Page 8]

RFC 1164 BGP - Application June 1990

on the policy based distribution of routing information
in RFC 1104 [2]. A BGP gateway may be aware of some
constraints (both within and outside of its own AS) and
appropriate path selection. Paths that do not comply
policy requirements are not considered further

Metrics based on compound criteria can be computed as a
combination of the degree of preferences of primitive criteria.
use of compound criteria should be done with extreme caution since
involves comparing potentially uncomparable quantities

4.2 Syntax and Semantics for BGP Configuration

A major task in using BGP is thus to assign a degree of preference
each available AS-path. This degree of preference will generally
a function of the number of ASs in the path, properties of
specific ASs in the path, the origin of the route, and properties
the specific border router to be used in the first hop. In
section we consider how a network administrator might articulate
function by means of a configuration file. In the future, we
imagine using tools based on network management protocols such
SNMP for this task, but the protocols do not currently support
ability

In addition to controlling the selection of the best path to a
network, the network administrator must control the advertisement
this best path to neighboring ASs. Therefore, path selection
path distribution emerge as the two key aspects of policy
in BGP usage

Since different aspects of one AS's policy interact, and since
policies of different ASs interact, it is important to facilitate
analysis of such interactions by means of high-quality and
tools

There is also a need for tools to translate the expression of
network administrator's policy to some technical mechanism within
BGP speaker to implement that policy

These factors suggest that there should be a globally consistent
of describing policies in the configuration file. The syntax
semantics of these policies should be capable of expressing the
selection phase within the local AS as well as the
redistribution phase to other ASs

Because it may be desirable to coordinate routing policy at
external level, it may prove worthwhile to create a language
describe this information in a globally consistent way.

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
different Autonomous Systems

The following defines one possible syntax and semantics
describing AS path policies from the point of view of the local AS
Alternative syntaxes with equivalent richness of functionality
not precluded. Other mechanisms may be needed to provide a
functional configuration language

A complete AS path, supplied by BGP, provides the most
mechanism for policy enforcement. Assigning a degree of
to a particular AS path can be modelled as a matching between
path and one or more predefined AS path patterns. Each predefined
path pattern has a degree of preference that will be assigned to
AS path that matches it

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

Since certain constructs occur frequently in regular expressions,
following notational shorthand (operators) is defined

. matches any AS number. To improve readability, "." can
replaced by "any" so long as this does not introduce ambiguity

* a regular expression followed by * means zero or

+ a regular expression followed by + means one or

? a regular expression followed by ? means zero or one

|

() parentheses group subexpressions--an operator, such as *
works on a single element or on a regular expression
in

{m,n} a regular expression followed by {m,n} (where m and n
both non-negative integers and m <= n) means at least m and
most n repetitions

{m} a regular expression followed by {m} (where m is a
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
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

::= { statement> }

Semantics: each policy statement might cause a given possible
advertisement (possibility) to be installed into the routing
as the route to a given (set of) networks. Thus, an
Policy-Based-Routing means that no possibilities will be accepted

statement> ::=
expression> '=' expression> ';'

Semantics: if a given possibility matches the policy-expression
then that possibility will be accepted with a degree of
denoted by the integer value dop-expression

expression> ::=
|
operator>
::=
<distribution-list> |
'(' expression> ')' |
NOT expression> |
<>

operator> ::= OR |

Semantics: the intersection of the network list of a
and the network-list must be non-empty; the AS-path of
possibility must match the AS-path as a sequence; the origin
the possibility must be a member of the origin set; if
conditions are met, the route denoted by the possibility
accepted as a possible route to those networks of the
of the possibility network list and the network-list

::= "regular expression over AS numbers

Semantics: the AS-path of the possibility must be generated by
regular expression .

Interconnectivity Working Group [Page 11]

RFC 1164 BGP - Application June 1990

::= '<' { network network-list } '>' |
'<' ANY '>'

Semantics: A non-empty sequence enumerates the network numbers
the network-list; ANY denotes the set of all network numbers

::= IGP | EGP | INCOMPLETE |

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
the routing table, then distribution-list is the set
(neighboring) autonomous systems to whose border routers we
distribute the BGP-derived routes

expression> ::= |
'+' |
'-' |
'*' |
'/' |

::= |
<function> |
'(' expression> ')'

Semantics: if a possibility matches with degree of
REJECT, then that possibility will not be used. Otherwise,
integer value of the degree of preference indicates the degree
preference of the possibility, with higher values preferred
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
of ASs in that path. PathWeight() takes the AS path and an AS
table as arguments and returns the sum of weights of the ASs in
AS path as defined by the AS weight table. In order to
determinism, the AS weight table must always have a default
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

Interconnectivity Working Group [Page 12]

RFC 1164 BGP - Application June 1990

is consistent with BGP), so that the most recent AS in the
occupies the leftmost position

Each network (and its associated complete AS path) received
other BGP neighbors is matched against local Routing Policies

If either no match occurs or the degree of preference associated
the matched policy is REJECT, then the received information
rejected. Otherwise, a degree of preference associated with
matched policy is assigned to that path. Notice that the
terminates on the first successful match. Therefore, policy-
should be ordered from more specific to more general

The semantics of a matched policy is as follows: If a network
that was originally introduced into BGP from is received via , that network should be redistributed
all ASs in <distribution-list>.

The following examples (some taken from RFC 1102 [3]) illustrate
Policy Terms can be written

In the following topology, H elements are hosts, G elements
Policy Gateways running BGP, and numbered elements are ASs

H1 --- 1 -G12...G21 - 2 -- G23...G32 -- 3 ----- H
| |
| |
| |
|- G14...G41 - 4 -- G43...G34 ---|- G35...G53 - 5
| |
| |
| H
H

In this picture, there are four hosts, ten gateways, and
Autonomous Systems. Gateways G12 and G14 belong to AS 1.
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
5. Dashed lines denote intra-AS connections. Dotted lines
inter-AS connections

First, consider AS 2. It has no hosts attached, and models a
service, such as the NSFNET backbone network. It may have a
simple policy: it will carry any traffic between any two ASs,
further constraint. If AS 1 and AS 3 are neighboring domains,
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

< ANY >

says that any network is subject to this policy. The
component, the AS

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

< IGP >

says that this route must be interior with respect to the
AS, implying that routes imported via EGP or some other
would not match this policy. The fourth component, the

< 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
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
4 and AS 5, presumably due to multilateral agreements. AS 3
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
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
networks to ASs 2, 4, and 5. Hosts in AS 4 and AS 5 would be able
reach each other, as well as hosts in ASs 1 and 3 and anything
them. AS 3 allows any origin in routes from AS 2. This implies
AS 3 trusts AS 2 to impose policy on routes imported by means
than BGP. Note that although the policy statement would appear
allow AS 3 to send ASs 4 and 5 their own routes, the BGP
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
by AS 2, and is willing to carry transit traffic for AS 4.
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
AS 4, and vice versa, and distribute routes to its own networks
both AS 2 and AS 4. The degree of preference assigned to any
which matches this policy is set to 150.

AS 5 is a more interesting case. AS 5 wishes to use the
service, but is not directly connected to AS 2. Its
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,
allows AS 5 and AS 4 to communicate through AS 3. Since AS 5
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
AS 2, and thus applies its own filter to ensure that it only uses
backbone. This lack of trust makes it necessary to add the
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
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
used as a backup if necessary. Note that since AS 4 trusts AS 3
provide it with reasonable routes, it is not necessary to
import routes from AS 5. Since the redistribution terms are
except for networks within AS 4, AS 4 will never carry any
traffic

Given the topology and policies described above, it becomes
that two paths of equal preference would be available from AS 2
any of the networks in AS 4. Since ties are not allowed,

Interconnectivity Working Group [Page 15]

RFC 1164 BGP - Application June 1990

arbitrary tie-breaking mechanism would come into play (as
above), which might result in less than optimal routes to
networks. An alternative mechanism that would provide optimal
while still allowing fallback paths would be to provide network-by
network policies in specific cases, and explicit tie-
policies for the remaining networks. For example, the policies
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
fallback; paths to all other networks through AS 3 would be
over those through AS 1. Such optimizations may become
complex

There may be other, simpler ways to assign a degree of preference
an AS path

The simplest way to assign a degree of preference to a
path is to use the number of ASs in the AS path as the degree
preference. This approach reflects the heuristic that shorter
are usually better than longer ones. This policy can be
by using the PathLength() built-in function in the following
statement

< ANY > < .* > < ANY > < ANY > = PathLength(ASpath

This policy assigns to any network with an arbitrary AS path a
of preference equal to the number of ASs in the AS path; it
redistributes this information to all other BGP speakers. As
example, an AS path which traverses three different
Systems will be assigned the degree of preference 3.

Another approach is to assign a certain degree of preference to
individual AS, and then determine the degree of preference of
particular AS path as the sum of the degree of preferences of the
in that path. Note that this approach does not require
assignment of a specific degree of preference to every AS in
Internet. For ASs with an unknown degree of preference, a
can be used. This policy can be implemented by using
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
their weights in the ASWeightTable, and if the default degree
preference in the ASWeightTable is 50, then an AS path that
Autonomous Systems 145, 164, and 55 will be assigned degree
preference 75.

The above examples demonstrate some of the simple policies that
be implemented with BGP. In general, very sophisticated
based on partial or complete AS path discrimination can be
and enforced. It should be emphasized that movement toward
sophisticated policies will require parallel effort in creating
sophisticated tools for policy interaction analysis

5. The Interaction of BGP and an

5.1

By definition, all transit ASs must be able to carry traffic
to that AS (neither the source nor destination host belongs to
AS). This requires a certain degree of interaction and
between the Interior Gateway Protocol (IGP) used by that
AS and BGP. In general, traffic exterior to a given AS is going
pass through both interior gateways (gateways that support IGP only
and border gateways (gateways that support both IGP and BGP).
interior gateways receive information about external routes from
or more of the border gateways of the AS via the IGP

Depending on the mechanism used to propagate BGP information within
given AS, special care must be taken to ensure consistency
BGP and the IGP, since changes in state are likely to propagate
different rates across the AS. There may be a time window
the moment when some border gateway (A) receives new BGP
information which was originated from another border gateway (B
within the same AS, and the moment the IGP within this AS is
of routing transit traffic to that border gateway (B). During
time window, either incorrect routing or "black holes" can occur

In order to minimize such routing problems, border gateway (A)
not advertise a route to some exterior network X to all of its
neighbors in other ASs until all of the interior gateways within
AS are ready to route traffic destined to X via the correct
border gateway (B). In other words, interior routing should
on the proper exit gateway before advertising routes via that
gateway to other ASs

5.2 Methods for Achieving Stable

The following discussion outlines several techniques capable

Interconnectivity Working Group [Page 17]

RFC 1164 BGP - Application June 1990

achieving stable interactions between BGP and the IGP within
Autonomous System

5.2.1 Propagation of BGP Information via the

While BGP can provide its own mechanism for carrying BGP
within an AS, one can also use an IGP to transport this information
as long as the IGP supports complete flooding of routing
(providing the mechanism to distribute the BGP information) and one
pass convergence (making the mechanism effectively atomic). If
IGP is used to carry BGP information, then the period
desynchronization described earlier does not occur at all, since
information propagates within the AS synchronously with the IGP,
the IGP converges more or less simultaneously with the arrival of
new routing information. Note that the IGP only carries
information and should not interpret or process this information

5.2.2 Tagged Interior Gateway

Certain IGPs can tag routes exterior to an AS with the identity
their exit points while propagating them within the AS. Each
gateway should use identical tags for announcing exterior
information (received via BGP) both into the IGP and into
BGP when propagating this information to other border gateways
the same AS. Tags generated by a border gateway must
identify that particular border gateway--different border
must use different tags

All Border Gateways within a single AS must observe the following
rules

1. Information received via Internal BGP by a border gateway
declaring a network to be unreachable must immediately
propagated to all of the External BGP neighbors of A

2. Information received via Internal BGP by a border gateway A
a reachable network X cannot be propagated to any of the
BGP neighbors of A unless/until A has an IGP route to X and
the IGP and the BGP routing information have identical tags

These rules guarantee that no routing information is
externally unless the IGP is capable of correctly supporting it.
also avoids some causes of "black holes".

One possible method for tagging BGP and IGP routes within an AS is
use the IP address of the exit border gateway announcing the
route into the AS. In this case the "gateway" field in the
UPDATE message is used as the tag

Interconnectivity Working Group [Page 18]

RFC 1164 BGP - Application June 1990

5.2.3

Encapsulation provides the simplest (in terms of the
between the IGP and BGP) mechanism for carrying transit
across the AS. In this approach, transit traffic is
within an IP datagram addressed to the exit gateway. The
requirement imposed on the IGP by this approach is that it should
capable of supporting routing between border gateways within the
AS

The address of the exit gateway A for some exterior network X
specified in the "gateway" field of the BGP UPDATE message
from gateway A via Internal BGP by all other border gateways
the same AS. In order to route traffic to network X, each
gateway within the AS encapsulates it in datagrams addressed
gateway A. Gateway A then performs decapsulation and forwards
original packet to the proper gateway in another AS

Since encapsulation does not rely on the IGP to carry
routing information, no synchronization between BGP and the IGP
required

Some means of identifying datagrams containing encapsulated IP,
as an IP protocol type code, must be defined if this method is to
used

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

5.2.4 Other

There may be ASs with IGPs which can neither carry BGP
nor tag exterior routes (e.g., RIP). In addition, encapsulation
be either infeasible or undesirable. In such situations,
following two rules must be observed

1. Information received via Internal BGP by a border gateway
declaring a network to be unreachable must immediately
propagated to all of the External BGP neighbors of A

2. Information received via Internal BGP by a border gateway A
a reachable network X cannot be propagated to any of the
BGP neighbors of A unless A has an IGP route to X and
time (holddown) has passed for the IGP routes to have converged

The above rules present necessary (but not sufficient) conditions
propagating BGP routing information to other ASs. In contrast

Interconnectivity Working Group [Page 19]

RFC 1164 BGP - Application June 1990

tagged IGPs, these rules cannot ensure that interior routes to
proper exit gateways are in place before propagating the routes
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
is less than X as well, and the whole issue can be ignored at
cost of transient periods (of less than length X) of
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
approach is needed. Mechanisms and techniques which might
appropriate in this situation are subjects for further study

6. Implementation

6.1 Multiple Networks Per

The BGP protocol allows for multiple networks with the same AS
and next-hop gateway to be specified in one message. Making use
this capability is highly recommended. With one network per
there is a substantial increase in overhead in the receiver.
only does the system overhead increase due to the reception
multiple messages, but the overhead of scanning the routing table
flash updates to BGP peers and other routing protocols (and
the associated messages) is incurred multiple times as well.
method of building messages containing many networks per AS path
gateway from a routing table that is not organized per AS path is
build many messages as the routing table is scanned. As each
is processed, a message for the associated AS path and gateway
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.
the message lacks the space to hold the new network, it
transmitted, a new message is allocated, and the new network
inserted into the new message. When the entire routing table
been scanned, all allocated messages are sent and their
released. Maximum compression is achieved when all networks share
gateway and common path attributes, making it possible to send
networks in one 4096-byte message

6.2 Preventing Excessive Resource

When peering with a BGP implementation that does not
multiple networks into one message, it may be necessary to take
to reduce the overhead from the flood of data received when a peer
acquired or a significant network topology change occurs. One
of doing this is to rate limit flash updates. This will

Interconnectivity Working Group [Page 20]

RFC 1164 BGP - Application June 1990

the redundant scanning of the routing table to provide flash
for BGP peers and other routing protocols. A disadvantage of
approach is that it increases the propagation latency of
information. By choosing a minimum flash update interval that is
much greater than the time it takes to process the multiple messages
this latency should be minimized

6.3 Processing Messages on a Stream

Due to the stream nature of TCP, all the data for received
does not necessarily arrive at the same time, due to the nature
TCP. This can make it difficult to process the data as messages
especially on systems such as BSD Unix where it is not possible
determine how much data has been received but not yet processed.
method that can be used in this situation is to first try to
just the message header. For the KeepAlive message type, this is
complete message; for other message types, the header should first
verified, in particular the total length. If all checks
successful, the specified length, minus the size of the
header is the amount of data left to read. An implementation
would "hang" the routing information process while trying to
from a peer could set up a message buffer (1024 bytes) per peer
fill it with data as available until a complete message has
received

6.4 Processing Update

In BGP, all Update messages are incremental. Once a
network is listed in an Update message as being reachable through
AS path and gateway, that piece of information is expected to
retained indefinitely. In order for a route to a network to
removed, it must be explicitly listed in an Update message as
unreachable or with new routing information to replace the old.
that a BGP peer will only advertise one route to a given network,
any announcement of that network by a particular peer replaces
previous information about that network received from the same peer

This approach has the obvious advantage of low overhead; if
routes are stable, only KeepAlive messages will be sent. There is
periodic flood of route information

However, this means that a consistent view of routing
between BGP peers is only possible over the course of a
transport connection, since there is no mechanism for a
update. This requirement is accommodated by specifying that
peers must transition to the Idle state upon the failure of
transport connection

Interconnectivity Working Group [Page 21]

RFC 1164 BGP - Application June 1990

7.

The BGP protocol provides a high degree of control and
for doing interdomain routing while enforcing policy and
constraints and avoiding routing loops. It is hoped that
guidelines presented here will provide a starting point for
sophisticated and manageable routing in the Internet as it grows

[1] Lougheed, K. and Y. Rekhter, "A Border Gateway Protocol",
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

Security issues are not discussed in this memo

Authors'

Jeffrey C.
Theory
265 Olin
Cornell
Ithaca, NY 14853-5201

Phone: (607) 255-8686

Email: JCH@TCGOULD.TN.CORNELL.

Dave
Merit/
1075 Beal Ave
Ann Arbor, MI 48109

Phone: (313) 763-4898

Email: DKATZ@MERIT.

Interconnectivity Working Group [Page 22]

RFC 1164 BGP - Application June 1990

Matt
Pittsburgh Supercomputing
4400 Fifth Ave
Pittsburgh, PA 15213

Phone: (412) 268-3319

Email: MATHIS@FARADAY.ECE.CMU.

Yakov
T.J. Watson Research
IBM
P.O. Box 218
Yorktown Heights, NY 10598

Phone: (914) 945-3896

Email: YAKOV@IBM.

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

Phone: (313) 936-3000

Email: JYY@MERIT.

Interconnectivity Working Group [Page 23]

if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.

RFC documents can be found at I.E.T.F.

Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX