As per Relevance of the word autonomous, we have this rfc below:
Network Working Group D. L.
Request for Comments: 975 M/A-COM
February 1986
Autonomous
Status of This
This RFC proposes certain enhancements of the Exterior
Protocol (EGP) to support a simple, multiple-level routing
while preserving the robustness features of the current EGP model
It requests discussion and suggestions for improvements
Distribution of this memo is unlimited
The enhancements, which do not require retrofits in
implementations in order to interoperate with
implementations, in effect generalize the concept of core system
include multiple communities of autonomous systems, called
confederations. Autonomous confederations maintain a higher degree
mutual trust than that assumed between autonomous systems in general
including reasonable protection against routing loops between
member systems, but allow the routing restrictions of the current
model to be relaxed
The enhancements involve the "hop count" or distance field of the
Update message, the interpretation of which is not covered by
current EGP model. This field is given a special
within each autonomous confederation to support up to three levels
routing, one within the autonomous system, a second within
autonomous confederation and an optional third within the universe
confederations
1. Introduction and
The historical development of Internet exterior-gateway
algorithms began with a rather rigid and restricted topological
which emphasized robustness and stability at the expense of
dynamics and flexibility. Evolution of robust and dynamic
algorithms has since proved extraordinarily difficult, probably
more to varying perceptions of service requirements than
engineering problems
The original exterior-gateway model suggested in RFC-827 [1]
subsequently refined in RFC-888 [2] severely restricted the
topology essentially to a tree structure with root represented by
BBN-developed "core" gateway system. The most
characteristic of the model was that debilitating resource-
routing loops between clusters of gateways (called
Mills [Page 1]
RFC 975 February 1986
Autonomous
systems) could not occur in a tree-structured topology. However,
administrative and enforcement difficulties involved, not to
the performance liabilities, made widespread
impractical
1.1. The Exterior Gateway
Requirements for near-term interoperability between the BBN
gateways and the remainder of the gateway population
by other organizations required that an interim protocol
developed with the capability of exchanging
information, but not necessarily the capability to function as
true routing algorithm. This protocol is called the
Gateway Protocol (EGP) and is documented in RFC-904 [3].
EGP was not designed as a routing algorithm, since no
could be reached on a trusted, common metric. However, EGP
designed to provide high-quality reachability information,
about neighbor gateways and about routes to non-neighbor gateways
At the present state of development, dynamic routes are
only by the core system and provided to non-core gateways
EGP only as an interface mechanism. Non-core gateways can
routes to the core system and even to other non-core gateways,
cannot pass on "third-party" routes computed using data
from other gateways
As operational experience with EGP has accumulated, it has
clear that a more decentralized dynamic routing capability
needed in order to avoid resource-consuming suboptimal routes.
addition, there has long been resistance to the a-
assumption of a single core system, with implications
suboptimal performance, administrative problems,
enforcement and possible subversion. Whether or not
resistance is real or justified, the important technical
remains whether a more dynamic, distributed approach is
without significantly diluting stability and robustness
This document proposes certain enhancements of EGP
generalize the concept of core system to include
communities of autonomous systems, called
confederations. Autonomous confederations maintain a
degree of mutual trust than that assumed between
systems in general, including reasonable protection
routing loops between the member systems. The
involve the "hop count" or distance field of the EGP
Mills [Page 2]
RFC 975 February 1986
Autonomous
message, which is given a special interpretation as
later. Note that the interpretation of this field is
specified in RFC-904, but is left as a matter for further study
The interpretation of the distance field involves three levels
metrics, in which the lowest level is available to the
gateway protocol (IGP) of the autonomous system itself to
the interior routes to the autonomous system boundary. The
higher level selects preferred routes within the autonomous
to those outside, while the third and highest selects
routes within the autonomous confederation to those outside
The proposed model is believed compatible with the
specifications and practices used in the Internet. In fact,
entire present conglomeration of autonomous systems, including
core system, can be represented as a single
confederation, with new confederations being formed from
and new systems as necessary
1.2. Routing
It was the intent in RFC-904 that the stipulated
restrictions superceded all previous documents, including RFC-827
and RFC-888. The notion that a non-core gateway must not pass
third-party information was suggested in planning meetings
occured after the previous documents had been published and
RFC-904 was finalized. This effectively obsoletes prior
of "stub" or any other asymmetry other than the third-party rule
Thus, the only restrictions placed on a non-core gateway is
in its EGP messages (a) a gateway can be listed only if it
to the same autonomous system (internal neighbor) and (b) a
can be listed only if it is reachable via gateways belonging
that system. There are no other restrictions, overt or implied
The specification does not address the design of the core
or its gateways
The restrictions imply that, to insure full connectivity,
non-core gateway must run EGP with a core gateway. Since
present core-gateway implementation disallows other gateways
EGP-neighbor paths, this further implies that every non-
gateway must share a net in common with at least one core gateway
Note that there is no a-priori prohibition on using EGP as an IGP
or even on using EGP with a gateway of another non-core system
Mills [Page 3]
RFC 975 February 1986
Autonomous
providing that the third-party rule is observed. If a gateway
each system ran EGP with a gateway in every other system,
notion of core system would be unneccessary and superflous
At one time during the evolution of the EGP model a
hierarchical topology (tree structure) of autonomous systems
required, but this is not the case now. At one time it
forbidden for two nets to be connected by gateways of two or
systems, but this is not the case now. Autonomous systems
sets of gateways, not nets or hosts, so that a given net or
can be reachable via more than one system; however, every
belongs to exactly one system
1.3. Examples and
Consider the common case of two local-area nets A and B
to the ARPANET by gateways of different systems. Now assume A
B are connected to each other by a gateway A-B belonging to
same system as the A-ARPANET gateway, which could then list
and both the A and B nets in EGP messages sent to any
gateway, since both are now reachable in its system. However,
B-ARPANET gateway could list itself and only the B net, since
A-B gateway is not in its system
In principle, we could assume the existence of a second
B-A belonging to the same system as the B-ARPANET gateway,
would entitle it to list the A net as well; however, it may
easier for both systems to sign a treaty and consider the A-
gateway under joint administration. The implementation of
treaty may not be trivial, however, since the joint gateway
appear to other gateways as two distinct gateways, each with
own autonomous-system number
Another case occurs when for some reason or other a system has
path to a core gateway other than via another non-core system
Consider a third local-are net C, together with gateway C-
belonging to a system other than the A-ARPANET and B-
gateways. According to the restrictions above, gateway C-A
list net C in EGP messages sent to A-ARPANET, while A-
could list ARPANET in messages sent to C-A, but not other
which it may learn about from the core. Thus, gateway C-A
acquire full routing information unless it runs EGP directly
a core gateway
Mills [Page 4]
RFC 975 February 1986
Autonomous
2. Autonomous Systems and
The second example above illustrates the need for a mechanism
which arbitrary routing information can be exchanged between non-
gateways without degrading the degree of robustness relative to
mutually agreed security model. One way of doing this is is
extend the existing single-core autonomous-system model to
multiple core systems. This requires both a topological model
can be used to define the scope of these systems together with
global, trusted metric that can be used to drive the
computations. An appropriate topological model is described in
next section, while an appropriate metric is suggested in
following section
2.1. Topological
An "autonomous system" consists of a set of gateways, each
which can reach any other gateway in the same system using
via gateways only in that system. The gateways of a
cooperatively maintain a routing data base using an
gateway protocol (IGP) and a intra-system trusted
mechanism of no further concern here. The IGP is expected
include security mechanisms to insure that only gateways of
same system can acquire each other as neighbors
One or more gateways in an autonomous system can run EGP with
or more gateways in a neighboring system. There is no
on the number or configuration of EGP neighbor paths, other
the requirement that each path involve only gateways of one
or the other and not intrude on a third system. It
specifically not required that EGP neighbors share a
network, although most probably will
An "autonomous confederation" consists of a set of
systems sharing a common security model; that is, they trust
other to compute routes to other systems in the
confederation. Each gateway in a confederation can reach
other gateway in the same confederation using paths only in
confederation. Although there is no restriction on the number
configuration of EGP paths other than the above, it is
that some mechanism be available so that potential EGP
can discover whether they are in the same confederation.
could be done by access-control lists, for example, or
partitioning the set of system numbers
A network is "directly reachable" from an autonomous system if
gateway in that system has an interface to it. Every gateway
Mills [Page 5]
RFC 975 February 1986
Autonomous
that system is entitled to list all directly reachable networks
EGP messages sent to any other system. In general, it may
that a particular network is directly reachable from more than
system
A network is "reachable" from an autonomous system if it
directly reachable from an autonomous system belonging to the
confederation. A directly reachable net is always reachable
the same system. Every gateway in that confederation is
to list all reachable nets in EGP messages sent to any
system. It may happen that a particular net is either
reachable or reachable from different confederations
In order to preserve global routing stability in the Internet,
is explicitly assumed that routes within an autonomous system to
directly reachable net are always preferred over routes
that system and that routes within an autonomous confederation
always preferred over routes outside that confederation.
mechanism by which this is assured is described in the
section
In general, EGP Update messages can include two lists of gateways
one for those gateways belonging to the same system (
neighbors) and the other for gateways belonging to
systems (external neighbors). Directly reachable nets must
be associated with gateways of the same system, that is,
internal neighbors, while non-directly reachable nets can
associated with either internal or external neighbors. Nets
are reachable, but not directly reachable, must always
associated with gateways of the same confederation
2.2. Trusted Routing
There seems to be a general principle which
distributed systems: The "nearer" a thing is the more dynamic
trustable it is, while the "farther" a thing is the more
and suspicious it is. For instance, the concept of network
intrinsic to the Internet model, as is the concept of
which bind them together. A cluster of gateways "near" each
(e.g. within an autonomous system) typically exchange
information using a high-performance routing algorithm capable
sensitive monitoring of, and rapid adaptation to,
performance indicators such as queueing delays and link loading
However, clusters of gateways "far" from each other (e.g.
separated autonomous systems) usually need only coarse
information, possibly only "hints" on the best likely next hop
Mills [Page 6]
RFC 975 February 1986
Autonomous
the general destination area. On the other hand, mutual
increases with distance, so these clusters may need
security considerations, including peer authentication
confidentiality, secrecy and signature verification. In addition
considerations of efficiency usually dictate that the
network bandidth consumed by the routing protocol itself
with distance. The price paid for both of these things
is in responsiveness, with the effect that the more
clusters are from each other, the less dynamic is the
algorithm
The above observations suggest a starting point for the
of a globally acceptable routing metric. Assume the metric
represented by an integer, with low values representing
distinctions "nearer" the gateway and high values
distinctions "farther" from it. Values less than a
agreed constant X are associated with paths confined to the
autonomous system as the sender, values greater than X but
than another constant Y with paths confined to the
confederation of the sender and values greater than Y
with the remaining paths
At each of these three levels - autonomous system,
confederation and universe of confederations - multiple
algorithms could be operated simultaneously, with each
for each destination net a possibly different subtree and
in the ranges specified above. However, within each system
metric must have the same interpretation, so that other
can mitigate routes between multiple gateways in that system
Likewise, within each confederation the metric must have the
interpretation, so that other confederations can mitigate
to gateways in that confederation. Although all
must agree on a common universe-of-confederations algorithm,
all confederations need to use the same confederation-
algorithm and not all systems in the same confederation need
use the same system-level algorithm
3. Implementation
The manner in which the eight-bit "hop count" or distance field
the EGP Update to be used is not specified in RFC-904, but left as
matter for further study. The above model provides both
interpretation of this field, as well as hints on how to
appropriate routing algorithms
For the sake of illustration, assume the values of X and Y above
128 and 192 respectively. This means that the gateways in
Mills [Page 7]
RFC 975 February 1986
Autonomous
particular system will assign distance values less than 128
directly-reachable nets and that exterior gateways can compare
values freely in order to select among these gateways. It also
that the gateways in all systems of a particular confederation
assign distance values between 128 and 192 for those nets
directly reachable in the system but reachable in the confederation
In the following it will be assumed that the various
can be distinguished by some feature of the 16-bit system-
field, perhaps by reserving a subfield
3.1. Data-Base Management
The following implementation model may clarify the above issues
as well as present at least one way to organize the gateway
base. The data base is organized as a routing table, the
of which include a net number together with a list of items,
each item consists of (a) the gateway address, system number
distance provided by an EGP neighbor, (b) a time-to-live counter
local routing information and other information as necessary
manage the data base
The routing table is updated each time an EGP Update message
received from a neighbor and possibly by other means, such as
system IGP. The message is first decoded into a list of
consisting of a network number, gateway address, system number
distance. If the gateway address is internal to the
system, as determined from the EGP message, the system number
the quad is set to that system; while, if not, the system
is set to zero, indicating "external."
Next, a new value of distance is computed from the old
provided in the message and subject to the following constraints
If the system number matches the local system number, the
value is determined by the rules for the system IGP but must
less than 128. If not and either the system number belongs to
same confederation or the system number is zero and the
distance is less than 192, the value is determined by the
for the confederation EGP, but must be at least 128 and less
192. Otherwise, the value is determined by the rules for
(global) universe-of-federations EGP, but must be at least 192.
For each quad in the list the routing table is first searched
matching net number and a new entry made if not already there
Next, the list of items for that net number is searched
matching gateway address and system number and a new entry made
not already there. Finally, the distance field is recomputed,
time-to-live field reset and local routing information inserted
Mills [Page 8]
RFC 975 February 1986
Autonomous
The time-to-live fields of all items in each list are
on a regular basis. If a field exceeds a preset maximum, the
is discarded; while, if all items on a list are discarded,
entire entry including net number is discarded
When a gateway sends an EGP Update message to a neighbor, it
invert the data base in order by gateway address, rather than
number. As part of this process the routing table is scanned
the gateway with minimum distance selected for each net number
The resulting list is sorted by gateway address and partitioned
the basis of internal/external system number
3.2. Routing
A gateway encountering a datagram (service unit) searches
routing table for matching destination net number and then
the gateway on that list with minimum distance. As the result
the value assignments above, it should be clear that routes at
higher level will never be chosen if routes at a lower
exist. It should also be clear that route selection within
system cannot affect route selection outside that system,
through the intervention of the intra-confederation
algorithm. If a simple min-system-hop algorithm is used for
confederation EGP, the IGP of each system can influence it only
the extent of reachability
3.3. Compatibility
The proposed interpretation is backwards-compatibile with
EGP implementations which do not interpret the distance field
with several known EGP implementations that take private
with this field. Perhaps the simplest way to evolve the
system is to collect the existing implementations that do
interpet the distance field at all as a single confederation
the present core system and routing restrictions. All
provided by this confederation would be assumed equal to 192,
which would provide at least a rudimentary capability for
within the universe of confederations
One or more existing or proposed systems in which the
field has a uniform interpretation throughout the system can
organized as autonomous confederations. This might include
Butterfly gateways now now being deployed, as well as
elsewhere. These systems provide the capability to select
into the system based on the distance fields for the
gateways. It is anticipated that the distance fields for
Butterfly system can be set to at least 128 if the
Mills [Page 9]
RFC 975 February 1986
Autonomous
information comes from another Butterfly system and to at
192 if from a non-Butterfly system presumed outside
confederation
New systems using an implmentation model such as suggested
can select routes into a confederation based on the
field. For this to work properly, however, it is necessary
all systems and confederations adopt a consistent
of distance values exceeding 192.
4. Summary and
Taken at face value, this document represents a proposal for
interpretation of the distance field of the EGP Update message,
has previously been assigned no architected interpretation, but
been often used informally. The proposal amounts to ordering
autonomous systems in a hierarchy of systems and confederations
together with an interpretation of the distance field as
three-level metric. The result is to create a
three-level routing community, one prefering routes inside a system
a second preferring routes inside a confederation and the third
no preference
While the proposed three-level hierarchy can readily be extended
any number of levels, this would create strain on the distance field
which is limited to eight bits in the current EGP model
The concept of distance can easily be generalized to "
distance" as suggested by John Nagle and others
5.
[1] Rosen, E., Exterior Gateway Protocol (EGP), DARPA
Working Group Report RFC-827, Bolt Beranek and Newman,
1982.
[2] Seamonson, L.J., and E.C., Rosen. "STUB" Exterior
Protocol, DARPA Network Working Group Report RFC-888,
Communications, January 1984.
[3] Mills, D.L., Exterior Gateway Protocol Formal Specification
DARPA Network Working Group Report RFC-904, M/A-COM Linkabit
April 1984.
Mills [Page 10]
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
