As per Relevance of the word autonomous, we have this rfc below:
RFC 827
EXTERIOR GATEWAY PROTOCOL (EGP
Eric C.
Bolt Beranek and Newman Inc
October 1982
It is proposed to establish a standard for Gateway to Gateway
that allow the Gateways to be mutually suspicious. This document is
DRAFT for that standard. Your comments are strongly encouraged
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Table of
1 INTRODUCTION.......................................... 1
2 NEIGHBOR ACQUISITION.................................. 8
3 NEIGHBOR REACHABILITY PROTOCOL....................... 11
4 NETWORK REACHABILITY (NR) MESSAGE.................... 15
5 POLLING FOR NR MESSAGES.............................. 22
6 SENDING NR MESSAGES.................................. 25
7 INDIRECT NEIGHBORS................................... 27
8 HOW TO BE A STUB GATEWAY............................. 28
9 LIMITATIONS.......................................... 32
- i -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
1
The DARPA Catenet is expected to be a continuously
system, with more and more hosts on more and more
participating in it. Of course, this will require more and
gateways. In the past, such expansion has taken place in
relatively unstructured manner. New gateways, often
radically different software than the existing gateways, would
added and would immediately begin participating in the
routing algorithm via the GGP protocol. However, as the
grows larger and larger, this simple method of expansion
less and less feasible. There are a number of reasons for this
- the overhead of the routing algorithm becomes
large
- the proliferation of radically different
participating in a single common routing algorithm
maintenance and fault isolation nearly impossible,
it becomes impossible to regard the internet as
integrated communications system
- the gateway software and algorithms, especially
routing algorithm, become too rigid and inflexible,
any proposed change must be made in too many
places and by too many different people
- 1 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
In the future, the internet is expected to evolve into a
of separate domains or "autonomous systems", each of
consists of a set of one or more relatively homogeneous gateways
The protocols, and in particular the routing algorithm
these gateways use among themselves, will be a private matter
and need never be implemented in gateways outside the
domain or system
In the simplest case, an autonomous system might consist
just a single gateway connecting, for example, a local network
the ARPANET. Such a gateway might be called a "stub gateway",
since its only purpose is to interface the local network to
rest of the internet, and it is not intended to be used
handling any traffic which neither originated in nor is
for that particular local network. In the near-term future,
will begin to think of the internet as a set of
systems, one of which consists of the DARPA gateways on
and SATNET, and the others of which are stub gateways to
networks. The former system, which we shall call the "core
system, will be used as a transport or "long-haul" system by
latter systems
Ultimately, however, the internet may consist of a number
co-equal autonomous systems, any of which may be used (
certain restrictions which will be discussed later) as
- 2 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
transport medium for traffic originating in any system
destined for any system. When this more complex
comes into being, it will be inappropriate to regard any
autonomous system as a "core" system. For the sake
concreteness, however, and because the initial implementations
the Exterior Gateway Protocol are expected to focus on the
case of connecting "stub gateways" to the DARPA gateways
ARPANET and SATNET, we will often use the term "core" gateways
our examples and discussion
The purpose of the Exterior Gateway Protocol (EGP) is
enable one or more autonomous systems to be used as
media for traffic originating in some other autonomous system
destined for yet another, while allowing the end-user to see
composite of all the autonomous systems as a single internet
with a flat, uniform address space. The route which a
takes through the internet, and the number of autonomous
which it traverses, are to be transparent to the end-
(unless, of course, the end-user makes use of the IP "
route" option).
In describing the Exterior Gateway Protocol, we
deliberately left a great deal of latitude to the designers
implementers of particular autonomous systems, particularly
regard to timer values. We have done this because we expect
- 3 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
different gateway implementations and different
environments may just have different requirements and goals,
that no single strict implementation specification could apply
all. However, this does NOT mean that ANY implementation
conforms to the specification will work well, or that the
in which we have left latitude are not crucial to performance
The fact that some time-out value, for example, is not
here does not mean that everything will work no matter what
is assigned
Autonomous systems will be assigned 16-bit
numbers (in much the same ways as network and protocol
are now assigned), and every EGP message header contains one
for this number. Zero will not be assigned to any
system; rather, the presence of a zero in this field
indicate that no number is present
We need to introduce the concept of one gateway being
NEIGHBOR of another. In the simplest and most common case,
call two gateways "neighbors" if there is a network to which
has an interface. However, we will need a somewhat more
notion of "neighbor" to allow the following two cases
a) Two gateways may be regarded as neighbors if they
directly connected not by a network (in the usual
- 4 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
of the term), but by a simple wire, or HDLC line, or
similar means of "direct connection".
b) Two gateways may be regarded as neighbors if they
connected by an "internet" which is transparent to them
That is, we would like to be able to say that
gateways are neighbors even if they are connected by
internet, as long as the gateways utilize no knowledge
the internal structure of that internet in their
packet-forwarding algorithms
In order to handle all these cases, let us say that two
are NEIGHBORS if they are connected by some communications
whose internal structure is transparent to them. (See IEN 184
for a more general discussion of this notion of neighbor.)
If two neighbors are part of the same autonomous system,
call them INTERIOR NEIGHBORS; if two neighbors are not part
the same autonomous system, we call them EXTERIOR NEIGHBORS.
order for one system to use another as a transport medium
gateways which are exterior neighbors of each other must be
to find out which networks can be reached through the other.
Exterior Gateway Protocol enables this information to be
between exterior neighbors. Since it is a polling protocol,
also enables each gateway to control the rate at which it
- 5 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
and receives network reachability information, allowing
system to control its own overhead. It also enables each
to have an independent routing algorithm whose operation
be disrupted by failures of other systems
It must be clearly understood that any autonomous system
which routing needs to be performed among gateways within
system must implement its own routing algorithm. (A
algorithm is not generally necessary for a simple
system which consists of a single stub gateway.) The
Gateway Protocol is NOT a routing algorithm. It enables
neighbors to exchange information which is likely to be needed
any routing algorithm, but it does NOT specify what the
are to do with this information. The "routing updates" of
autonomous system's interior routing algorithm may or may not
similar in format to the messages of the exterior
protocol. The gateways in the DARPA "core" system will
use the GGP protocol (the old Gateway-Gateway protocol) as
routing algorithm, but this will be subject to change.
in other autonomous systems may use their own Interior
Protocols (IGPs), which may or may not be similar to the IGP
any other autonomous system. They may, of course, use GGP,
will not be permitted to exchange GGP messages with gateways
other autonomous systems
- 6 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
It must also be clearly understood that the Exterior
Protocol is NOT intended to provide information which could
used as input to a completely general area or
routing algorithm. It is intended for a set of
systems which are connected in a tree, with no cycles. It
not enable the passing of sufficient information to
routing loops if cycles in the topology do exist
The Exterior Gateway Protocol has three parts: (a)
Acquisition Protocol, (b) Neighbor Reachability Protocol, and (c
Network Reachability determination. Note that all
defined by EGP are intended to travel only a single "hop".
is, they originate at one gateway and are sent to a
gateway without the mediation of any intervening gateway
Therefore, the time-to-live field should be set to a very
value. Gateways which encounter EGP messages in their
streams which are not addressed to them may discard them
- 7 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
2 NEIGHBOR
Before it is possible to obtain routing information from
exterior gateway, it is necessary to acquire that gateway as
direct neighbor. (The distinction between direct and
neighbors will be made in a later section.) In order for
gateways to become direct neighbors, they must be neighbors,
the sense defined above, and they must execute the
ACQUISITION PROTOCOL, which is simply a standard three-
handshake
A gateway that wishes to initiate neighbor acquisition
another sends it a Neighbor Acquisition Request. This
should be repeatedly transmitted (at a reasonable rate,
once every 30 seconds or so) until a Neighbor Acquisition
is received. The Request will contain an identification
which is copied into the reply so that request and reply can
matched up
A gateway receiving a Neighbor Acquisition Request
determine whether it wishes to become a direct neighbor of
source of the Request. If not, it may, at its option,
with a Neighbor Acquisition Refusal message,
specifying the reason for refusal. Otherwise, it should send
Neighbor Acquisition Reply message. It must also send a
- 8 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Acquisition Request message, unless it has done so already
Two gateways become direct neighbors when each has sent
Neighbor Acquisition Message to, and received the
Neighbor Acquisition Reply from, the other
Unmatched Replies or Refusals should be discarded after
reasonable period of time. However, information about any
unmatched messages may be useful for diagnostic purposes
A Neighbor Acquisition Message from a gateway which
already a direct neighbor should be responded to with a Reply
a Neighbor Acquisition Message
If a Neighbor Acquisition Reply is received from
prospective neighbor, but a period of time passes during which
Neighbor Acquisition Message is received from that
neighbor, the neighbor acquisition protocol shall be
incomplete. A Neighbor Cease message (see below) should then
sent. If one gateway still desires to acquire the other as
neighbor, the protocol must be repeated from the beginning
If a gateway wishes to cease being a neighbor of
particular exterior gateway, it sends a Neighbor Cease message
A gateway receiving a Neighbor Cease message should
respond with a Neighbor Cease Acknowledgment. It should cease
- 9 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
treat the sender of the message as a neighbor in any way.
there is a significant amount of protocol run between
neighbors (see below), if some gateway no longer needs to be
direct neighbor of some other, it is "polite" to indicate
fact with a Neighbor Cease Message. The Neighbor Cease
should be retransmitted (up to some number of times) until
acknowledgment for it is received
Once a Neighbor Cease message has been received,
Neighbor Reachability Protocol (below) should cease to
executed
NOTE THAT WE HAVE NOT SPECIFIED THE WAY IN WHICH ONE
INITIALLY DECIDES THAT IT WANTS TO BECOME A NEIGHBOR OF ANOTHER
While this is hardly a trivial problem, it is not part of
External Gateway Protocol
- 10 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
3 NEIGHBOR REACHABILITY
It is important for a gateway to keep real-time
as to the reachability of its neighbors. If a gateway
that a particular neighbor cannot be reached, it should
forwarding traffic to that gateway. To make that determination
a NEIGHBOR REACHABILITY protocol is needed. The EGP
provides two messages types for this purpose -- a "Hello"
and an "I Heard You" message
When a "Hello" message is received from a direct neighbor
an "I Heard You" must be returned to that neighbor "immediately".
The delay between receiving a "Hello" and returning an "I
You" should never be more than a few seconds
At the current time, the reachability
algorithm is left to the designers of a particular gateway.
have in mind algorithms like the following
A reachable neighbor shall be declared unreachable if
during the time in which we sent our last n "Hello"s, we
fewer than k "I Heard You"s in return. An unreachable
shall be declared reachable if, during the time in which we
our last m "Hello"s, we received at least j "I Heard You"s
return
- 11 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
However, the frequency with which the "Hello"s are sent,
the values of the parameters k, n, j, and m cannot be
here. For best results, this will depend on the
of the neighbor and of the network which the neighbors have
common. THIS IMPLIES THAT THE PROPER PARAMETERS MAY NEED TO
DETERMINED JOINTLY BY THE DESIGNERS AND IMPLEMENTERS OF THE
NEIGHBORING GATEWAYS; choosing algorithms and parameters
isolation, without considering the characteristics of
neighbor and the connecting network, would not be expected
result in optimum reachability determinations
The "Hello" and "I Heard You" messages have a status
which the sending gateway uses to indicate whether it thinks
receiving gateway is reachable or not. This information can
useful for diagnostic purposes. It also allows one gateway
make its reachability determination parasitic on the other:
one gateway actually needs to send "Hello" messages, and
other can declare it up or down based on the status field in
"Hello". That is, the "passive" gateway (which sends only "
Heard You"s) declares the "active" one (which sends
"Hello"s) to be reachable when the "Hello"s from the active
indicate that it has declared the passive one to be reachable
Of course, this can only work if there is prior agreement as
which neighbor is to be the active one. (Ways of coming to
- 12 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
"prior agreement" are not part of the Exterior Gateway Protocol.)
A direct neighbor gateway should also be
unreachable if the network connecting it supplies lower
protocol information from which this can be deduced. Thus,
example, if a gateway receives an 1822 Destination Dead
from the ARPANET which indicates that a direct neighbor is dead
it should declare that neighbor unreachable. The neighbor
not be declared reachable again until the requisite number
Hello/I-Heard-You packets have been exchanged
A direct neighbor which has become unreachable does
thereby cease to be a direct neighbor. The neighbor can
declared reachable again without any need to go through
neighbor acquisition protocol again. However, if the
remains unreachable for an extremely long period of time, such
an hour, the gateway should cease to treat it as a neighbor
i.e., should cease sending Hello messages to it. The
acquisition protocol would then need to be repeated before
could become a direct neighbor again
"Hello" and "I Heard You" messages from gateway G to
G' also carry the identification number of the NR poll
(see below) which G has most recently received from G'.
- 13 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
"Hello" and "I Heard You" messages from gateway G to
G' also carry the minimum interval in minutes with which G
willing to be polled by G' for NR messages (see below).
"Hello" messages from sources other than direct
should simply be ignored. However, logging the presence of
such messages might provide useful diagnostic information
A gateway which is going down, or whose interface to
network which connects it to a particular neighbor is going down
should send a Gateway Going Down message to all direct
which will no longer be able to reach it. It should
that message (up to some number of times) until it receives
Gateway Going Down Acknowledgment. This provides the
with an advance warning of an outage, and enables them to
for it in a way which will minimize disruption to
traffic
- 14 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
4 NETWORK REACHABILITY (NR)
Terminology: Let gateway G have an interface to network N
We say that G is AN APPROPRIATE FIRST HOP to network M
to network N (where M and N are distinct networks) if and only
the following condition holds
Traffic which is destined for network M, and which
at gateway G over its network N interface, will be
to M by G over a path which does not include any
gateway with an interface to network N
In short, G is an appropriate first hop for network
relative to network N just in case there is no better gateway
network N through which to route traffic which is destined
network M. For optimal routing, traffic in network N which
destined for network M ought always to be forwarded to a
which is an appropriate first hop
In order for exterior neighbors G and G' (which
neighbors over network N) to be able to use each other as
switches for forwarding traffic to remote networks, each needs
know the list of networks for which the other is an
first hop. The Exterior Gateway Protocol defines a message
called the Network Reachability Message (or NR message),
transferring this information
- 15 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Let G be a gateway on network N. Then the NR message
G sends about network N must contain the following information
A list of all the networks for which G is an
first hop relative to network N
If G' can obtain this information from exterior neighbor G,
it knows that no traffic destined for networks which are NOT
that list should be forwarded to G. (It cannot simply conclude
however, that all traffic for any networks in that list ought
be forwarded via G, since G' may also have other neighbors
are also appropriate first hops to network N. For example, G
G'' might each be neighbors of G', but might be "equidistant
from some network M. Then each could be an appropriate
hop.)
For each network in the list, the NR message also contains
byte which specifies the "distance" (according to some
whose definition is left to the designers of the
system of which gateway G is a member) from G to that network
This information might (or might not) be useful in the
routing algorithm of gateway G', or for diagnostic purposes
The maximum value of distance (255.) shall be taken to
that the network is UNREACHABLE. ALL OTHER VALUES WILL BE
TO MEAN THAT THE NETWORK IS REACHABLE
- 16 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
If an NR message from some gateway G fails to mention
network N which was mentioned in the previous NR message from G
it shall be assumed that N is still reachable from G. HOWEVER
IF N IS NOT MENTIONED IN TWO SUCCESSIVE NR MESSAGES FROM G,
SHALL BE TAKEN TO MEAN THAT N IS NO LONGER REACHABLE FROM G
This procedure is necessary to ensure that networks which can
longer be reached, but which are never explicitly
unreachable, are timed out and removed from the list of
networks
It may often be the case that where G and G' are
neighbors on network N, G knows of many more gateway neighbors
network N, and knows for which networks those other neighbors
the appropriate first hop. Since G' may not know about all
other neighbors, it is convenient and often more efficient for
to be able to obtain this information from G. Therefore, the
NR message also contains fields which allow G to specify
following information
a) A list of all neighbors (both interior and exterior) of
(on network N) which G has reliably determined to
reachable. Gateways should be included in this list
if G is actively running its neighbor
protocol with them
- 17 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
b) For each of those neighbors, the list of networks
which that neighbor is an appropriate first hop (
to network N).
c) For each such <neighbor, network> pair, the "distance
from that neighbor to that network
Thus the NR message provides a means of allowing a
to "discover" new neighbors by seeing whether a neighbor that
already knows of has any additional neighbors on the
network. This information also makes possible the
of the INDIRECT NEIGHBOR strategy defined below
A more precise description of the NR message is
following
The data portion of the message will consist largely
blocks of data. Each block will be headed by a gateway address
which will be the address either of the gateway sending
message or of one of that gateway's neighbors. Each
address will be followed by a list of the networks for which
gateway is an appropriate first hop, and the distance from
gateway to each network
Preceding the list of data blocks is
a) The address of the network which this message is about
- 18 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
If G and G' are neighbors on network N, then in the
message going from G to G', this is the address
network N. For convenience, four bytes have
allocated for this address -- the trailing one, two,
three bytes should be zero
b) The count (one byte) of the number of interior
of G for which this message contains data blocks.
convention, this count will include the data block for
itself, which should be the first one to appear
c) The count (one byte) of the number of exterior
of G for which this message contains data blocks
Then follow the data blocks themselves, first the block
G itself, then the blocks for all the interior neighbors of G (
any), then the blocks for the exterior neighbors. Since
gateways mentioned are on the same network, whose address
already been given, the gateway addresses are given with
network address part (one, two, or three bytes) omitted, to
space
Each block includes a one-byte count of the number
networks for which that gateway is the appropriate first hop.
the list of networks, each network address is either one, two,
three bytes, depending on whether it is a class A, class B,
- 19 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
class C network. No trailing bytes are used
It may sometimes be necessary to fragment the NR message
The NR message contains a byte indicating the number of
fragment (fragments will be numbered from zero), and a
containing the number of the last fragment (NOT the number
fragments). If fragmentation is not used, these bytes must
be zero. EACH FRAGMENT MUST BE A FULLY SELF-CONTAINED
MESSAGE. That is, each fragment will begin with a count
interior and exterior neighbors, and will have some
number of gateway data blocks. The number of data blocks in
fragment must correspond to the neighbor counts at the
of that fragment. However, only the first fragment should
with a data block describing the sending gateway
This scheme enables each fragment to be
independently, and requires no complex reassembly mechanisms.
also enables processing of a message all of whose fragments
not been received. If, after some amount of time and some
of retransmissions of a poll, not all fragments have
received, the fragments which are present shall be processed
if they constituted the complete NR message. (This means
networks mentioned only in the missing fragment will retain
"distance" values they had in the previous NR message from
gateway. However, if no new value for a particular network
- 20 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
received in the next NR message from that gateway, the
will be declared unreachable.)
- 21 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
5 POLLING FOR NR
No gateway is required to send NR messages to any
gateway, except as a response to an NR Poll from a
neighbor. However, a gateway is required to respond to an
Poll from a direct neighbor within several seconds (subject
the qualification two paragraphs hence), even if the
believes that neighbor to be down
The EGP NR Poll message is defined for this purpose.
gateway may poll another for an NR message more often than
per minute. A gateway receiving more than one poll per
may simply ignore the excess polls, or may return an
message. The Hello and I Heard You messages which gateway
sends to gateway G' indicate the minimum interval which G
accept as the polling interval from G'. That is, G' will
guarantee to respond to polls from G that arrive less than
interval apart
Polls must only be sent to direct neighbors which
declared reachable by the neighbor reachability protocol
An NR Poll message contains an identification number
by the polling gateway. The polled gateway will return
number in the NR message it sends in response to the poll,
enable the polling gateway to match up received NR messages
- 22 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
polls. It will be the responsibility of the polling gateway
choose an identification number which is sufficiently "unique"
allow detection of out-of-date NR messages which may still
floating around the network. Since polls are
infrequent, this is not expected to be much of a problem
However, to aid in choosing an identification number, the
and I Heard You messages carry the identification number of
last NR poll received from the neighbor to which they are
sent
In general, a poll should be retransmitted some number
times (with a reasonable interval between retransmissions)
an NR message is received. IF NO NR MESSAGE IS RECEIVED
THE MAXIMUM NUMBER OF RETRANSMISSIONS, THE POLLING GATEWAY
ASSUME THAT THE POLLED GATEWAY IS NOT AN APPROPRIATE FIRST
FOR ANY NETWORK WHATSOEVER. The optimum parameters for
polling/retransmission algorithm will be dependent on
characteristics of the two neighbors and of the
connecting them
If only some fragments of an NR message are received
the maximum number of retransmissions, the fragments that
present shall be treated as constituting the whole of the
message
- 23 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Received NR messages whose identification numbers do
match the identification number of the most recently sent
shall be ignored. There is no provision for multiple
polls to the same neighbor
- 24 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
6 SENDING NR
In general, NR messages are to be sent only in response to
poll. However, between two successive polls from an
neighbor, a gateway may send one and only one unsolicited
message to that neighbor. This gives it limited ability
quickly announce network reachability changes that may
occurred in the interval since the last poll. Excess
NR messages may be ignored, or an error message may be returned
An NR message should be sent within several seconds
receipt of a poll. Failure to respond in a timely manner to
NR poll may result in the polling gateway's deciding that
polled gateway is not an appropriate first hop to any network
NR messages sent in response to polls carry
identification number of the poll message in
"identification number" fields. Unsolicited NR messages
the identification number of the last poll received, and have
"unsolicited" bit set. (Note that this allows for only a
unsolicited NR message per polling period.)
To facilitate the sending of unsolicited NR messages, the
poll message has a byte indicating the polling interval
minutes
- 25 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Polls from non-neighbors, from neighbors which are
declared reachable, or with bad IP source network fields,
be responded to with an EGP error message with the
"reason" field. If G sends an NR poll to G' with IP
network N, and G' is not a neighbor of G on its interface
network N (or G' does not have an interface to network N),
the source network field is considered "bad".
Duplicated polls (successive polls with the
identification number) should be responded to with duplicates
the same NR message. If that message is fragmented, the
fragments shall be sent each time. Note that there is
provision for handling multiple outstanding polls from a
neighbor. NOTE THAT IF THE SAME FRAGMENTS ARE NOT SENT
RESPONSE TO DUPLICATED POLLS, INCORRECT REASSEMBLY WILL BE
PROBABLE RESULT. If fragmentation is not being used, however
then no harm should result from responding to a duplicate
with a different (presumably more recent) NR message
- 26 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
7 INDIRECT
Becoming a "direct neighbor" of an exterior gateway
three steps: (a) neighbor acquisition, (b) running a
reachability protocol, and (c) polling the neighbor
for NR messages. Suppose, however, that gateway G receives an
message from G', in which G' indicates the presence of
neighbors G1, ..., Gn, each of which is an appropriate first
for some set of networks to which G' itself is not an
first hop. Then G should be allowed to forward traffic for
networks directly to the appropriate one of G1, ..., Gn,
having to send it to G' first. In this case, G may be
an INDIRECT NEIGHBOR of G1, ..., Gn, since it is a neighbor
these other gateways for the purpose of forwarding traffic,
does not perform neighbor acquisition, neighbor reachability,
exchange of NR messages with them. Neighbor and
reachability information is obtained indirectly via G', hence
designation "indirect neighbor". We say that G is an
neighbor of G1, ..., Gn VIA G'.
If G is an indirect neighbor of G' via G'', and then
receives an NR message from G'' which does not mention G',
should treat G' as having become unreachable
- 27 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
8 HOW TO BE A STUB
The most common application of EGP will probably be its
to enable a stub gateway to communicate with one of the
core gateways, so as to enable data flow between
accessible only via the stub and networks accessible only via
system of core gateways. As discussed previously, a stub
can be considered to be a one-gateway internet system with
interior neighbors. It is probably used to interface a
network or networks to a long range transport network (such
ARPANET or SATNET) on which there is a core gateway. In
case, the stub will not want the core gateways to forward it
traffic other than traffic which is destined for the network
networks which can be reached only via the stub. In general,
stub will not want to perform any services for the
transport system which are not needed in order to be able to
traffic to and from the networks that cannot be
reached
The stub should have tables configured in with the
of a small number of the core gateways (no more than two
three) with which it has a common network. It will be
responsibility of the stub to initiate neighbor acquisition
these gateways. When a stub and a core gateway become
neighbors, the core gateway will begin sending Hello messages
- 28 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
When the stub declares the core gateways which are
neighbors to be reachable, it should poll those gateways for
messages at a rate not to exceed once per minute (or as
in the Hello messages from the core gateways). The core
will also poll the stub for NR messages
The NR message sent by the stub should be the
allowable. That is, it should have only a single data block
headed by its own address (on the network it has in common
the neighboring core gateway), listing just the networks to
it is an appropriate first hop. These will be just the
that can be reached no other way, in general
The core gateways will send complete NR messages,
information about all other gateways on the common networks,
core gateways (which shall be listed as interior neighbors)
other gateways (which shall be listed as exterior neighbors,
may include the stub itself). This information will enable
stub to become an indirect neighbor of all these other gateways
That is, the stub shall forward traffic directly to these
gateways as appropriate, but shall not become direct
with them
The core gateways will report distances less than 128 if
network can be reached without leaving the core system (i.e.,
- 29 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
without traversing any gateway other than a core gateway),
greater than or equal to 128 otherwise
The stub should NEVER forward to any (directly
indirectly) neighboring core gateway any traffic for which
gateway is not an appropriate first hop, as indicated in an
message. Of course, this does not apply to datagrams which
using the source route option; any such datagrams should
be forwarded as indicated in the source route option field,
if that requires forwarding to a gateway which is not
appropriate first hop
If the direct neighbors of a stub should all fail, it
be the responsibility of the stub to acquire at least one
direct neighbor. It can do so by choosing one of the
gateways which it has had as an indirect neighbor, and
the neighbor acquisition protocol with it. (It is possible
no more than one core gateway will ever agree to become a
neighbor with any given stub gateway at any one time.)
If the stub gateway does not respond in a timely manner
Hello messages from the core gateway, it may be
unreachable. If it does not respond to NR poll messages in
timely manner, its networks may be declared unreachable. In
these cases, the core gateways may discard traffic destined
- 30 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
those networks, returning ICMP "destination network unreachable
to the source hosts
The stub gateway is expected to fully execute the
protocol, as well as the EGP protocol. In particular, it
respond to ICMP echo requests, and must send ICMP
dead messages as appropriate. It is also required to send
Redirect messages as appropriate
- 31 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
9
It must be clearly understood that the Exterior
Protocol does not in itself constitute a network
algorithm. In addition, it does not provide all the
needed to implement a general area routing algorithm. If
topology of the set of autonomous systems is not tree-
(i.e., if it has cycles), the Exterior Gateway Protocol does
provide enough topological information to prevent loops
If any gateway sends an NR message with false information
claiming to be an appropriate first hop to a network which it
fact cannot even reach, traffic destined to that network
never be delivered. Implementers must bear this in mind
- 32 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
NEIGHBOR ACQUISITION
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! EGP Version # ! Type ! Code ! Info !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Checksum ! Autonomous System # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Identification # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Description
The Neighbor Acquisition messages are used by interior
exterior gateways to become neighbors of each other
EGP Version #
1
3
Code = 0 Neighbor Acquisition
Code = 1 Neighbor Acquisition
Code = 2 Neighbor Acquisition Refusal (see Info field
Code = 3 Neighbor Cease Message (see Info field
Code = 4 Neighbor Cease
The EGP checksum is the 16-bit one's complement of the one'
complement sum of the EGP message starting with the
version number field. For computing the checksum,
checksum field should be zero
Autonomous System #
This 16-bit number identifies the autonomous
containing the gateway which is the source of this message
- 33 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
For Refusal message, gives reason for refusal
0
1 Out of table
2 Administrative
For Cease message, gives reason for ceasing to be neighbor
0
1 Going
2 No longer
Otherwise, this field MUST be zero
Identification
An identification number to aid in matching requests
replies
- 34 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
NEIGHBOR HELLO/I HEARD YOU
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! EGP Version # ! Type ! Code ! Status !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Checksum ! Autonomous System # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Sequence # !Min Poll Intvl ! Zero !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Last Poll Id # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Description
Exterior neighbors use EGP Neighbor Hello and I Heard
Messages to determine neighbor connectivity. When a
receives an EGP Neighbor Hello message from a neighbor
should respond with an EGP I Heard You message
EGP Version #
1
5
Code = 0 for
Code = 1 for I Heard
The EGP checksum is the 16-bit one's complement of the one'
complement sum of the EGP message starting with the
version number field. For computing the checksum,
checksum field should be zero
Autonomous System #
This 16-bit number identifies the autonomous
containing the gateway which is the source of this message
- 35 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Sequence
A sequence number to aid in matching requests and replies
0 No status
1 You appear reachable to
2 You appear unreachable to me due to
reachability
3 You appear unreachable to me due to
reachability information (such as 1822 "
dead" messages from ARPANET
4 You appear unreachable to me due to
with my network
Last Poll Id
The identification number of the most recently
NR poll message from the neighbor to which this
is being sent
Minimum Polling
This gateway should not be polled for NR messages
often than once in this number of minutes
- 36 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
NR POLL
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! EGP Version # ! Type ! Code ! Unused !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Checksum ! Autonomous System # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! IP Source Network ! Interval !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Identification # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Description
A gateway that wants to receive an NR message from
Exterior Gateway will send an NR Poll message. Each
mentioned in the NR message will have an interface on
network that is in the IP source network field
EGP Version #
1
2
0
The EGP checksum is the 16-bit one's complement of the one'
complement sum of the EGP message starting with the
version number field. For computing the checksum,
checksum field should be zero
Autonomous System #
This 16-bit number identifies the autonomous
containing the gateway which is the source of this message
- 37 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Identification
An identification number to aid in matching requests
replies
IP Source
Each gateway mentioned in the NR message will have
interface on the network that is in the IP source
field. The IP source network is coded as one byte
network number followed by two bytes of zero for class
networks, two bytes of network number followed by one
of zero for class B networks, and three bytes of
number for class C networks
The polling interval in minutes
- 38 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
NETWORK REACHABILITY
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! EGP Version # ! Type ! Code !U! Zeroes !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Checksum ! Autonomous System # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Fragment # !# of last frg. ! Identification # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! IP Source Network !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! # of Int Gwys ! # of Ext Gwys !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! # of Nets ! ; # of nets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Gateway 1
! Gateway 1 IP address (without network #) ! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net 1,1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! distance !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net 1,2 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! distance !
+-+-+-+-+-+-+-+-+
.
.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net 1,m !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; m nets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; via Gateway 1
.
.
+-+-+-+-+-+-+-+-+
! # of nets ! ;number of nets for Gateway
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Gateway n IP address (without network #) !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net n,1 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! distance !
+-+-+-+-+-+-+-+-+
- 39 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net n,2 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! distance ! .
+-+-+-+-+-+-+-+-+ .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! net n,m !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; m nets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ; via Gateway
! distance !
+-+-+-+-+-+-+-+-+
- 40 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Description
The Network Reachability message (NR) is used to
which networks may be reached through Exterior Gateways. The
message is sent in response to an NR Poll message
EGP Version #
1
1
0
The EGP checksum is the 16-bit one's complement of the one'
complement sum of the EGP message starting with the
version number field. For computing the checksum,
checksum field should be zero
Autonomous System #
This 16-bit number identifies the autonomous
containing the gateway which is the source of this message
U (Unsolicited)
This bit is set if the NR message is being sent unsolicited
Identification
The identification number of the last NR poll
received from the neighbor to whom this NR message is
sent. This number is used to aid in matching polls
replies
Fragment
Which Fragment this is in the NR Message. Zero,
fragmentation is not used
- 41 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Number of Last
Number of the last fragment in the NR Message. Zero,
fragmentation is not used
IP Source
Each gateway mentioned in the NR message will have
interface on the network that is in the IP source
field
# of Interior
The number of interior gateways that are mentioned in
message
# of Exterior
The number of exterior gateways that are mentioned in
message
# of
The number of networks for which the gateway whose
address immediately follows is the appropriate first hop
Gateway IP
1, 2 or 3 bytes of Gateway IP address (without network #).
Network
1, 2, or 3 bytes of network address of network which can
reached via the preceding gateway
1 byte of distance in # of hops
- 42 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
EGP ERROR
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! EGP Version # ! Type ! Code ! Unused !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Checksum ! Autonomous System # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Error Type ! Error Code ! Id. # of Erroneous Msg. !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
! Sequence # !
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Description
An EGP Error Message is sent in response to an EGP
that has a bad checksum or has an incorrect value in one
its fields
EGP Version #
1
8
0
The EGP checksum is the 16-bit one's complement of the one'
complement sum of the EGP message starting with the
version number field. For computing the checksum,
checksum field should be zero
Autonomous System #
This 16-bit number identifies the autonomous
containing the gateway which is the source of this message
- 43 -
RFC 827 Bolt Beranek and Newman Inc
Eric C.
Sequence
A sequence number assigned by the gateway sending the
message
Error
The Type of the EGP message that was in error
Error
The Code of the EGP message that was in error
Identification number of erroneous
The Sequence number of the EGP message that was in error
The reason that the EGP message was in error. The following
are defined
0 -
1 - Bad EGP
2 - Bad IP Source address in NR Poll or
3 - Undefined EGP Type or
4 - Received poll from non-
5 - Received excess unsolicted NR
6 - Received excess
7 - Erroneous counts in received NR
8 - No response received to NR
9 - Not all fragments of NR message
- 44 -
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
