As per Relevance of the word specific, we have this rfc below:
Network Working Group D.L.
Request for Comments: 904 April 1984
Exterior Gateway Protocol Formal
0. Status of this
This RFC is the specification of the Exterior Gateway
(EGP). This document updates RFCs 827 and 888. This RFC specifies
standard for the DARPA community. Interactions between gateways
different autonomous systems in the ARPA-Internet must follow this
protocol
1.
This document is a formal specification of the Exterior
Protocol (EGP), which is used to exchange net-reachability
between Internet gateways belonging to the same or different
systems. The specification is intended as a reference guide
implementation, testing and verification and includes
algorithmic parameters suitable for operation over a wide set
configurations, including the ARPANET and many local-
technologies now part of the Internet system
Specifically excluded in this document is discussion on
background, application and limitations of EGP, which have
discussed elsewhere (RFC-827, RFC-888). If, as expected, EGP evolves
include topologies not restricted to tree-structures and to
full routing capabilities, this specification will be amended
obsoleted accordingly. However, it is expected that, as new
are added to EGP, the basic protocol mechanisms described here
remain substantially unchanged, with only the format and
of the Update message (see below) changed
Section 2 of this document describes the nomenclature used,
Section 3 describes the state-machine model, including events, actions
parameters and state transitions. Section 4 contains a
description of the operation of the machine, together with
procedures and algorithms. Appendix A describes the EGP
formats, while Appendix B contains a summary of the minor
between these and the formats described in RFC-888. Appendix C
a reachability analysis including a table of composite state
for a system of two communicating EGP gateways
1.1. Summary and
EGP exists in order to convey net-reachability information
neighboring gateways, possibly in different autonomous systems.
protocol includes mechanisms to acquire neighbors, monitor
reachability and exchange net-reachability information in the form
Update messages. The protocol is based on periodic polling
Hello/I-Heard-You (I-H-U) message exchanges to monitor
reachability and Poll commands to solicit Update responses
Specification of EGP is based on a formal model consisting of
Exterior Gateway Protocol Formal Specification Page 2
D.L.
finite-state automaton with defined events, state transitions
actions. The following diagram shows a simplified
representation of this machine (see Section 3.4 for a detailed
transition table).
+-------+
| |---------------+---------------+
+---->| Idle | A
| | |-----------+ | |
| +-------+ | | |
| | A Request | | Cease |
| Start | | Cease | | |
| V | Refuse V | |
| +-------+ Confirm +-------+ Up +-------+
| | |-------->| |-------->| |
| | Aqsn | | Down | Down | Up |
| | |----+ | |<--------| |
| +-------+ | +-------+ +-------+
| | | |
| Stop | | |
| Cease-ack | Stop | Stop |
| +-------+ | | |
| | | V V
+-----| Cease |<---+--------+-----------------+
| |
+-------+
Following is a brief summary and overview of gateway operations
state as determined by this model
Idle State (0)
In the Idle state the gateway has no resources (table space
assigned to the neighbor and no protocol activity of any kind is
progress. It responds only to a Request command or a Start
(system or operator initiated) and ignores all other commands
responses. The gateway may optionally return a Cease-ack
to a Cease command in this state
Upon receipt of a Request command the gateway initializes the
variables as described in Section 3.1, sends a Confirm response
transitions to the Down state, if resource committments permit,
sends a Refuse response and returns to the Idle state if not.
receipt of a Start event it sends a Request command and
to the Acquistion state
Acquisition State (1)
In the Acquisition state the gateway periodically
Request commands. Upon receiving a Confirm response it
Exterior Gateway Protocol Formal Specification Page 3
D.L.
the state variables and transitions to the Down state.
receiving a Refuse response it returns to the Idle state.
gateway does not send any other commands or responses in this state
since not all state variables have yet been initialized
Down State (2)
In the Down state the gateway has received a Request command or
Confirm response has been received for a previously sent Request
The neighbor-reachability protocol has declared the neighbor to
down. In this state the gateway processes Request, Cease and
commands and responds as required. It periodically
Hello commands if enabled. It does not process Poll commands
does not send them, but may optionally process an unsolicited
indication
Up State (3)
In the Up state the neighbor-reachability protocol has declared
neighbor to be up. In this state the gateway processes and
to all commands. It periodically retransmits Hello commands,
enabled, and Poll commands
Cease State (4)
A Stop event causes a Cease command to be sent and a transition
the Cease state. In this state the gateway periodically
the Cease command and returns to the Idle state upon receiving
Cease-ack response or a another Stop event. The defined
transitions are designed to ensure that the neighbor does with
probability receive the Cease command and stop the protocol
In following sections of this document document a state
which can serve as a model for implementation is described. It
happen that implementators may deviate from this model while
to the protocol specification; however, in order to verify
to the specification, the state-machine model is intended as
reference model
Although not mentioned specifically in this document, it should
understood that all Internet gateways must include support for
Internet Control Message Protocol (ICMP), specifically ICMP Redirect
ICMP Destination Unreachable messages
2.
The following EGP message types are recognized in this document
The format of each of these messages is described in Appendix A
Exterior Gateway Protocol Formal Specification Page 4
D.L.
Name
------------------------------------------------------
Request request acquisition of neighbor and/
initialize polling
Confirm confirm acquisition of neighbor and/
initialize polling
Refuse refuse acquisition of
Cease request de-acquisition of
Cease-ack confirm de-acquisition of
Hello request neigbor
I-H-U confirm neigbor
Poll request net-reachability
Update net-reachability
Error
EGP messages are classed as commands which request some action
responses, which are sent to indicate the status of that action,
indications, which are similar to responses, but may be sent at
time. Following is a list of commands along with their
responses
Command Corresponding
---------------------------------------
Request Confirm, Refuse,
Cease Cease-ack,
Hello I-H-U,
Poll Update,
The Update and Error messages are classed both as responses
indications. When sent in reply to a previous command, either of
messages is classed as a response. In some circumstances an
Update message can be sent, in which case it is classed as
indication. The use of the Error message other than as a response to
previous command is a topic for further study
3. State
This section describes the state-machine model for EGP,
the variables and constants which establish the state at any time,
events which cause the state transitions, the actions which result
these transitions and the state-transition table which defines
behavior
3.1. State
The state-machine model includes a number of state variables
establish the state of the protocol between the gateway and each of
neighbors. Thus, a gateway maintaining EGP with a number of
must maintain a separate set of these state variables for each neighbor
The current state, events and actions of the state machine apply to
Exterior Gateway Protocol Formal Specification Page 5
D.L.
neighbor separately
The model assumes that system resources, including the set of
variables, are allocated when the state machine leaves the Idle state
either because of the arrival of a Request specifying a new
addreess, or because of a Start event specifying a new neighbor address
When either of these events occur the values of the state variables
initialized as indicated below. Upon return to the Idle state
resources, including the set of state variables, are deallocated
returned to the system. Implementators may, of course, elect
dedicate resources and state variables permananently
Included among the set of state variables are the following
determine the state transitions of the model. Initial values for all
the variables except the send sequence number S are set during
initial Request/Confirm exchange. The initial value for S is arbitrary
Name
--------------------------------------------------------------
R receive sequence
S send sequence
T1 interval between Hello command
T2 interval between Poll command
T3 interval during which neighbor-
indications are
M hello polling
t1 timer 1 (used to control Request, Hello and
command retransmissions
t2 timer 2 (used to control Poll command retransmissions
t3 timer 3 (abort timer
Additional state variables may be necessary to support various timer
similar internal housekeeping functions. The function and management
the cited variables are discussed in Section 4.
3.2. Fixed
This section defines several fixed parameters which
the gateway functions. Included is a suggested value for each
based on experimental implementations in the Internet system.
values may or may not be appropriate for the individual configuration
Following is a list of time-interval parameters which
retransmissions and other time-dependent functions
Exterior Gateway Protocol Formal Specification Page 6
D.L.
Name Value
--------------------------------------------------------------
P1 30 sec minimum interval acceptable between
Hello commands
P2 2 min minimum interval acceptable between
Poll commands
P3 30 sec interval between Request or Cease
P4 1 hr interval during which state variables
maintained in the absence of commands
responses in the Down and Up states
P5 2 min interval during which state variables
maintained in the absence of responses in
Acquisition and Cease
Parameters P4 and P5 are used only if the abort-timer option
implemented. Parameter P4 establishes how long the machine will
in the Down and Up states in the absence of commands or responses
would ordinarily be set to sustain state information while the
is dumped and restarted, for example. Parameter P5 establishes how
the machine will remain in the Acquisition or Cease states in
absence of responses and would ordinarily be set in the same order
the expected value of T3 variables
Following is a list of other parameters of interest
Name Active Passive
-----------------------------------------------
j 3 1 neighbor-up threshold
k 1 4 neighbor-down
The j and k parameters establish the "noise immunity" of
neighbor-reachability protocol described later. The values in
Active column are suggested if the gateway elects to do hello polling
while the values in the Passive column are suggested otherwise
3.3.
Following is a list of events that can cause state transitions
the model
Exterior Gateway Protocol Formal Specification Page 7
D.L.
Name
----------------------------------------------------------------------
Up At least j neighbor-reachability indications have
received within the last T3 seconds
Down At most k neighbor-reachabilitiy indications have
received within the last T3 seconds
Request Request command has been received
Confirm Confirm command has been received
Refuse Refuse response has been received
Cease Cease command has been received
Cease-ack Cease-ack response has been received
Hello Hello command has been received
I-H-U I-H-U response has been received
Poll Poll command has been received
Update Update response has been received
Start Start event has been recognized due to system
operator intervention
Stop/t3 Stop event has been recognized due to (a) system
operator intervention or (b) expiration of the
timer t3.
t1 Timer t1 has counted down to zero
t2 Timer t2 has counted down to zero
There is one special event, called a neighbor-
indication, which occurs when
1. The gateway is operating in the active mode (hello polling enabled
and either a Confirm, I-H-U or Update response is received
2. The gateway is operating in the passive mode (hello
disabled) and either a Hello or Poll command is received with
"Up state" code in the Status field
3.4. State Transition
The following table summarizes the state transitions that can
in response to the events listed above. Transitions are shown in
form n/a, where n is the next state and a represents the action
Exterior Gateway Protocol Formal Specification Page 8
D.L.
0 Idle 1 Aqsn 2 Down 3 Up 4
+-----------+-----------+-----------+-----------+-----------+
Up |0 |1 |3/Poll |3 |4 |
Down |0 |1 |2 |2 |4 |
Request |2/Confirm *|2/Confirm |2/Confirm |2/Confirm |4/Cease |
Confirm |0/Cease **|2 |2 |3 |4 |
Refuse |0/Cease **|0 |2 |3 |4 |
Cease |0/Cease-ack|0/Cease-ack|0/Cease-ack|0/Cease-ack|0/Cease-ack
Cease-ack |0 |1 |2 |3 |0 |
Hello |0/Cease **|1 |2/I-H-U |3/I-H-U |4 |
I-H-U |0/Cease **|1 |2/Process |3/Process |4 |
Poll |0/Cease **|1 |2 |3/Update |4 |
Update |0/Cease **|1 |2 |3/Process |4 |
Start |1/Request |1/Request |1/Request |1/Request |4 |
Stop/t3 |0 |0 |4/Cease |4/Cease |0 |
t1 |0 |1/Request |2/Hello |3/Hello |4/Cease |
t2 |0 |1 |2 |3/Poll |4 |
+-----------+-----------+-----------+-----------+-----------+
Note *: The transition shown applies to the case where
neighbor-acquisition request is accepted. The transition "0/Refuse
applies to the case where the request is rejected
Note **: The Cease action shown is optional
3.5. State Transitions and
The following table describes in detail the transitions of
state machine and the actions evoked
Next
Event State Sent
------------------------------------------------------------------------
Idle State (0)
Request 2 Confirm Initialize state variables
Hello reset timer t1 to T1 seconds
reset timer t3 to P5 seconds
(or) 0 Refuse Return resources
Cease 0 Cease-ack Return resources
Start 1 Request Reset timer t1 to P3 seconds
reset timer t3 to P5 seconds
Acquisition State (1)
Request 2 Confirm Initialize state variables
Hello reset timer t1 to T1 seconds
reset timer t3 to P5 seconds
Confirm 2 Hello Initialize state variables
Exterior Gateway Protocol Formal Specification Page 9
D.L.
reset timer t1 to T1 seconds
reset timer t3 to P5 seconds
Refuse 0 Stop timers and
resources
Cease 0 Cease-ack Stop timers and
resources
Start 1 Request Reset timer t1 to P3 seconds
reset timer t3 to P5 seconds
Stop/t3 0 Stop timers and
resources
t1 1 Request Reset timer t1 to P3 seconds
Down State (2)
Note: Reset timer t3 to P4 seconds on receipt of a
indication
Up 3 Poll Reset timer t2 to T2 seconds
Request 2 Confirm Reinitialize state variables
Hello reset timer t1 to T1 seconds
reset timer t3 to P5 seconds
Cease 0 Cease-ack Stop timers and
resources
Hello 2 I-H-
I-H-U 2 Process neighbor-
info
Start 1 Request Reset timer t1 to P3 seconds
reset timer t3 to P5 seconds
Stop/t3 4 Cease Reset timer t1 to P3 seconds
reset timer t3 to P5 seconds
t1 2 Hello Reset timer t1 to T1 seconds
Up State (3)
Note: Reset timer t3 to P4 seconds on receipt of a
indication
Down 2 Stop timer t2.
Request 2 Confirm Renitialize state variables
Hello reset timer t1 to T1 seconds
reset timer t3 to P5 seconds
Cease 0 Cease-ack Stop timers and
resources
Hello 3 I-H-
I-H-U 3 Process neighbor-
info
Poll 3
Update 3 Process net-reachability info
Start 1 Request Reset timer t1 to P3 seconds
reset timer t3 to P5 seconds
Stop/t3 4 Cease Reset timer t1 to P3 seconds
reset timer t3 to P5 seconds
Exterior Gateway Protocol Formal Specification Page 10
D.L.
t1 3 Hello Reset timer t1 to T1 seconds
t2 3 Poll Reset timer t2 to T2 seconds
Cease State (4)
Request 4
Cease 0 Cease-ack Stop timers and
resources
Cease-ack 0 Stop timers and
resources
Stop/t3 0 Stop timers and
resources
t1 4 Cease Reset timer t1 to P3 seconds
4. Functional
This section contains detailed descriptions of the
procedures and algorithms used to manage the protocol
4.1. Managing the State
The state variables which characterize the protocol are
in Section 3.1. This section describes the detailed management of
variables, including sequence numbers, polling intervals and timers
4.1.1. Sequence
All EGP commands and replies carry a sequence number. The
variable R records the last sequence number received in a command
that neighbor. The current value of R is used as the sequence
for all replies and indications sent to the neighbor until a
with a different sequence number is received from that neighbor
Implementors are free to manage the sequence numbers of
commands sent; however, it is suggested that a separate send
variable S be maintained for each EGP neighbor and that its value
incremented just before the time an Poll command is sent and at no
times. The actions upon receipt of a response or indication
sequence number not equal to S is not specified; however, it
recommended these be discarded
4.1.1. Polling
As part of the Request/Confirm exchange a set of polling
are established including T1, which establishes the interval
Hello command retransmissions, and T2, which establishes the
between Poll retransmissions
Each gateway configuration is characterized by a set of
parameters, including P1, which specifies the minimum polling
Exterior Gateway Protocol Formal Specification Page 11
D.L.
at which it will respond to Hello commands, and P2, which specifies
minimum polling interval at which it will respond to Poll commands. P
and P2 are inserted in the Hello Interval (S1) and Poll Interval (S2)
fields, respectively, of Request commands and Confirm responses
A gateway receiving a Request command or Confirm response uses
S1 and S2 fields in the message to calculate its own T1 and T2
variables, respectively. Implementors are free to perform
calculation in arbitrary ways; however, the following constraints
be observed
1. If T1 < S1 the neighbor may discard Hello commands. If T2 < S2
neighbor may discard Poll commands
2. The time window T3 in which neighbor-reachability indications
counted is dependent on T1. In the case where two neighbors
widely differing values for their T3 state variables,
neighbor-reachability algorithm may not work properly. This can
avoided if T1 > max(P1, S1).
3. If either S1 or S2 or both are unacceptable for some reason (e.g
exceed useful limits), the neighbor may either send a
response or declare a Stop event, depending on state
It is suggested that T3 be computed as four times the value of T1,
giving a window of four neighbor-reachability indications, which
been found appropriate in the experimental implementations
Implementors may choose to make T3 a fixed parameter in those
where the path between the neighbors has well-known characteristics
Note that, if a gateway attempts to send Hello commands near
rate max(P1, S1) or Poll commands near the rate max(P2, S2),
neighbor may observe their succeeding arrivals to violate the
restrictions due to bunching in the net. For this reason the
should send at rates somewhat below these. Just how much below
rates is appropriate depends on many factors beyond the scope of
specification
4.1.3. Hello Polling
The neighbor-reachability algorithm can be used in either
active or passive mode. In the active mode Hello commands are
periodically along with Poll commands, with reachability determined
the corresponding I-H-U and Update responses. In the passive mode
commands are not sent and I-H-U responses are not expected
Reachability is then determined from the Status field of received
or Poll commands or Update responses
The M state variable specifies whether the gateway operates in
active or passive mode. At least one of the two neighbors sharing
Exterior Gateway Protocol Formal Specification Page 12
D.L.
protocol must operate in the active mode; however,
neighbor-reachability protocol is designed to work even if
neighbors operate in the active mode. The value of M is determined
the Status field of a Request command or Confirm response. The
sets this field according to whether the implementation supports
active mode, passive mode or both
Status Sender
--------------------------------
0 either active or
1 active
2 passive
The receiver inspects this field and sets the value of M
to its own capabilities as follows
Status Receiver
field 0 1 2
-------------------------------
0 * active passive
1 passive active
2 active active **
In the case of "*" the mode is determined by comparing
autonomous system numbers of the neigbors. The neighbor with
smallest such number assumes active mode, while the other
assumes passive mode. In the case of "**" the neighbor may either
a Refuse response or declare a Stop event, depending on state
4.1.4.
There are three timers defined in the state machine: t1, used
control retransmission of Request, Hello and Cease messages, t2, used
control retransmission of Poll commands, and t3, which serves as
abort-timer mechanism should the protocol hang indefinately. The
are set to specified values upon entry to each state and count down
zero
In the case of t1 and t2 state-dependent events are declared
the timer counts down to zero, after which the timer is reset to
specified value and counts down again. In the case of t3 a Stop
is declared when the timer counts down to zero. Implementors may
not to implement t3 or, if so, may choose to implement it only
certain states, with the effect that Request, Hello and/or
commands may be retransmitted indefinately
The following table shows the initial values for each of the
in each state. A missing value indicates the timer is not used in
state. Note that timer t3 is set to P4 upon receipt of
neighbor-reachability indication when in either the Down or Up states
Exterior Gateway Protocol Formal Specification Page 13
D.L.
Idle Aqsn Down Up
Timer 0 1 2 3 4
---------------------------------------------
t1 P3 T1 P
t2 T2
t3 P5 P5 P
4.2. Starting and Stopping the
The Start and Stop events are intrinsic to the system
of the gateway. They can be declared as the result of the
process being started and stopped by the operator, for example. A
event has meaning only in some states; however, a Stop event
meaning in all states
In all except the Idle state the abort timer t3 is
running. This timer is initialized at P5 seconds upon entry to
state and at P4 seconds upon receipt of a neighbor-
indication in the Down and Up states. If it expires a Stop event
declared. A Stop event can also be declared by an intrinsic
action such as a resource problem or operator command
If the abort timer is not implemented a manually-initiated
event can be used to stop the protocol. If this is done in the Down
Up states, the machine will transition to the Cease state and emit
Cease command. If the neighbor does not respond to this command
machine will stay in the Cease state indefinately; however, a
Stop event can be used in this state to force a transition to the
state
A Cease command received in any state will cause the gateway
immediately send the Cease-ack response and transition to the
state. This causes the protocol to be stopped and all system
committed to the gateway process to be released. The interval
the time the gateway enters the Idle state as the result of receiving
Cease command and the time when it next sends a Request command
resume the protocol is not specified; however, it is recommended
interval be at least P5 seconds
It may happen that the Cease-ack response is lost in the network
causing the neighbor to retransmit the Cease response indefinately,
least if it has not implemented the abort-timer option. In order
reduce the likelihood of this happening, it is suggested that a
in the Idle state be prepared to reply to a Cease command with
Cease-ack response whenever possible
4.3. Determining Neighbor
The purpose of the neighbor-reachability algorithm is to
that the neighbor can safely be considered operational and capable
Exterior Gateway Protocol Formal Specification Page 14
D.L.
providing reliable net-reachability information. An equally
purpose is to filter noisy reachability information before sending it
to the remainder of the Internet gateway system, thus
unneccesary reachability changes
As described above, a gateway operating in the active mode
periodic Hello commands and listens for I-H-U responses in order
determine neighbor-reachability indications. A gateway operating in
passive mode determines reachability indications by means of the
field in received Hello commands. Poll commands and Update
can be used in lieu of Hello commands and I-H-U responses respectively
since they contain the same Status-field information
The neighbor-reachability algorithm runs continuously while
gateway is in the Down and Up states and operates as follows. Define
moving window in time starting at the present and extending
for t seconds. Then count the number n of neighbor-
indications which have occured in that window. If n increases to j
then declare a Up event. If n decreases to k, then declare a
event. The number n is set to zero upon entering the Down state
any state other than the Up state
The window t in this algorithm is defined as T3 seconds, the
of which is suggested as four times T1, which itself is
during the Request/Confirm exchange. For proper operation of
algorithm only one neighbor-reachability indication is significant
any window of T1 seconds and additional ones are ignored. Note that
only way n can increase is as the result of a new neighbor-
indication and the only way it can decrease is as the result of an
neighbor-reachability indication moving out of the window
The behavior of the algorithm described above and using
suggested fixed parameters j and k differs depending on whether
gateway is operating in the active or passive mode. In the active
(j = 3, k = 1 and T3/T1 = 4), once the neighbor has been declared
it will be forced down for at least two T1 intervals and, once it
been declared up it will be forced up for at least two T1 intervals.
will not change state unless at least three of the last
determinations of reachability have indicated that change
In the passive mode (j = 1, k = 4 and T3/T1 = 4), the neighbor
be considered up from the first time the Status field of a Hello or
command or Update response indicates "Up state" until four successive T
intervals have passed without such indication. This design,
by similar designs used in the ARPANET, has proven effective in
experimental implementations, but may need to be adjusted for
configurations
It is convenient for the active gateway to send Hello commands at
rate of one every T1 seconds and substitute a Poll command for a
Exterior Gateway Protocol Formal Specification Page 15
D.L.
command approximately once every T2 seconds, with
neighbor-reachability indication generated by the corresponding I-H-U
Update responses. Its passive neighbor generates neighbor-
indications from the Status field of received Hello and Poll
and Update responses
Implementors may find the following model useful in
understanding and implementation of this algorithm. Consider an n-
shift register that shifts one bit to the right each T1-second interval
If a neighbor-reachability indication was received during the
T1-second interval a one bit is shifted into the register at the end
the interval; otherwise, a zero bit is shifted. A table of 2**
entries indexed by the contents of the register can be used to
the number of one bits, which can then be used to declare
appropriate event to the state machine. A value of n equal to four
been found useful in the experimental implementations
4.4. Determining Network
Network reachability information is encoded into Update messages
the form of lists of nets and gateways. The IP Source Address field
the Poll command is used to specify a network common to the
systems of each of the neighbors, which is usually, but not necessarily
the one common to the neighbors themselves. The Update
includes a list of gateways on the common net. Associated with
gateway is a list of the networks reachable via that gateway
with corresponding hop counts
It is important to understand that, at the present state
development as described in RFC-827 and RFC-888, the EGP
model restricts the interpretation of "reachable" in this context.
consideration, as well as the implied topological restrictions,
beyond the scope of discussion here. The reader is referred to the
for further discussion
Two types of gateway lists can be included in the Update response
the format of which is described in Appendix A. Both lists include
those gateways directly connected to the net specified in the IP
Network field of the last-received Poll command. The internal
includes some or all of the gateways in the same autonomous system
the sender, together with the nets which are reachable via
gateways, with the sending gateway listed first. A net is reachable
this context if a path exists to that net including only gateways in
system. The external list includes those gateways in other
systems known to the sender. It is important to realize that the
counts do not represent a routing metric and are comparable
different gateways only if those gateways belong to the same
system; that is, are in the internal list
Exterior Gateway Protocol Formal Specification Page 16
D.L.
According to the current system architectural model, only
belonging to a designated system, called the core system, may
the external list in their Update responses. All other gateways
include only those gateways belonging to the same system and can
reachability for a particular net only if that net is reachable in
same system
The interval between successive Poll commands T2 is
during the Request/Confirm exchange. However, the specification
at most one unsolicited Update indication between succeeding
commands received from the neighbor. It is the intent of the model
that an Update indication is sent (a) upon entry to the Up state and (b
when a change in the reachability data base is detected, subject to
limitation
Occasionally it may happen that a Poll command or Update
is lost in the network, with the effect that net-
information may not be available until after another T2 interval. As
implementation option, the gateway sending a Poll command and
receiving an Update response after T1 seconds may send another Poll
The gateway receiving this Poll may either (a) send an Update
if it never received the original Poll for that interval, (b) send
second Update response (which counts as the unsolicited
indication mentioned in the preceeding paragraph) or (c) send an
response or not respond at all in other cases
4.5. Error
Error messages can be used to report problems such as described
Appendix A in connection with the Error Response/Indication
format. In general, an Error message is sent upon receipt of
command or response with bad format, content or ordering, but never
response to another Error message. Receipt of an Error message
be considered advisory and not result in change of state,
possibly to evoke a Stop event
Exterior Gateway Protocol Formal Specification Page 17
D.L.
Appendix A. EGP Message
The formats for the various EGP messages are described in
section. All EGP messages include a ten-octet header of six fields
which may be followed by additional fields depending on message type
The format of the header is shown below along with a description of
fields
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 # |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
EGP Version # assigned number identifying the EGP
(currently 2)
Type identifies the message
Code identifies the message code (subtype
Status contains message-dependent status
Checksum The EGP checksum is the 16-bit one's
of the one's complement sum of the EGP
starting with the EGP version number field.
computing the checksum the checksum field
should be zero
Autonomous System # assigned number identifying the
autonomous
Sequence # send state variable (commands) or receive
variable (responses and indications
Following is a description of each of the message formats.
that the above description applies to all formats and will not
repeated
Exterior Gateway Protocol Formal Specification Page 18
D.L.
A.1. 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 | Status |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | Autonomous System # |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence # | Hello Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Poll Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Note: the Hello Interval and Poll Interval fields are present only
Request and Confirm messages
Type 3
Code 0 Request
1 Confirm
2 Refuse
3 Cease
4 Cease-ack
Status (see below) 0
1 active
2 passive
3 insufficient
4 administratively
5 going
6 parameter
7 protocol
Hello Interval minimum Hello command polling interval (seconds
Poll Interval minumum Poll command polling interval (seconds
Following is a summary of the assigned Status codes along with a list
scenarios in which they might be used
Exterior Gateway Protocol Formal Specification Page 19
D.L.
Code Status
-------------------------------------------------------------------
0 unspecified when nothing else
1 active mode Request/Confirm
2 passive mode Request/Confirm only
3 insufficient resources 1. out of table
2. out of system
4 administratively 1. unknown Autonomous System
prohibited 2. use another
5 going down 1. operator initiated
2. abort
6 parameter problem 1. nonsense polling
2. unable to assume compatible
7 protocol violation 1. Invalid command or
received in this
Exterior Gateway Protocol Formal Specification Page 20
D.L.
A.2. Neighbor 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 | Status |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | Autonomous System # |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence # |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 5
Code 0 Hello
1 I-H-U
Status 0
1 Up
2 Down
Exterior Gateway Protocol Formal Specification Page 21
D.L.
A.3. 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 | Status |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | Autonomous System # |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence # | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP Source Network |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 2
Code 0
Status 0
1 Up
2 Down
IP Source Network IP network number of the network about
reachability information is being
(coded as 1, 2 or 3 octets, left justified
trailing zeros
Exterior Gateway Protocol Formal Specification Page 22
D.L.
A.4. Update Response/
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 # | # of Int Gwys | # of Ext Gwys |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP Source Network |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Gateway 1 IP address (without network #) | (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # Distances |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Distance 1 | # Nets |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| net 1,1,1 ||||||||||||||||||||||||||||||||| (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| net 1,1,2 ||||||||||||||||||||||||||||||||| (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Distance 2 | # Nets |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| net 1,2,1 ||||||||||||||||||||||||||||||||| (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| net 1,2,2 ||||||||||||||||||||||||||||||||| (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Gateway n IP address (without network #) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # Distances |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Distance 1 | # Nets |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| net n,1,1 ||||||||||||||||||||||||||||||||| (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| net n,1,2 ||||||||||||||||||||||||||||||||| (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Distance 2 | # Nets |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| net n,2,1 ||||||||||||||||||||||||||||||||| (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| net n,2,2 ||||||||||||||||||||||||||||||||| (1-3 octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...
Exterior Gateway Protocol Formal Specification Page 23
D.L.
Type 1
Code 0
Status 0
1 Up
2 Down
128 unsolicited message
# of Int Gwys number of interior gateways appearing in
# of Ext Gwys number of exterior gateways appearing in
IP Source Network IP network number of the network about
reachability information is being
(coded as 1, 2 or 3 octets, left justified
trailing zeros
Gateway IP addresses IP address (without network number) of
gateway block (coded as 1, 2 or 3 octets
# of Distances number of distances in the gateway
Distances numbers depending on autonomous
# of Nets number of nets at each
Nets IP network number reachable via the
Exterior Gateway Protocol Formal Specification Page 24
D.L.
A.5. Error Response/
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 # | Reason |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Error Message Header |
| (first three 32-bit words of EGP header) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 8
Code 0
Status 0
1 Up
2 Down
128 unsolicited message
Reason (see below) 0
1 bad EGP header
2 bad EGP data field
3 reachability info
4 excessive polling
5 no
Error Message Header first three 32-bit words of EGP
Following is a summary of the assigned Reason codes along with a list
scenarios in which they might be used
Exterior Gateway Protocol Formal Specification Page 25
D.L.
Code Reason
------------------------------------------------------------------------
0 unspecified when nothing else
1 bad EGP header format 1. bad message
2. invalid Type, Code or Status
Notes: The recipient can determine
of the above hold by inspecting the
header included in the message.
instance of a wrong EGP version or
checksum should not be reported,
the original recipient can not trust
header format. An instance of an
autonomous system should be caught
acquistion time
2 bad EGP data field 1. nonsense polling
format (Request/Confirm
2. invalid Update message
3. response IP Net Address field
not match command (Update
Notes: An instance of nonsense
intervals (e.g. too long to be useful
specified in a Request or Confirm
result in a Refuse or Cease with
cause specified
3 reachability info 1. no info available on net specified
unavailable IP Net Address field (Poll
4 excessive polling rate 1. two or more Hello commands
within minimum specified
2. two or more Poll commands
within minimum specified
3. two or more Request commands
within some (reasonably short
Notes: The recipient can determine
of the above hold by inspecting the
header included in the message
5 no response 1. no Update received for Poll
some (reasonably long)
Exterior Gateway Protocol Formal Specification Page 26
D.L.
Appendix B. Comparison with RFC-888
Minor functional enhancements are necessary in the RFC-888
formats to support certain features assumed of the state-machine model
in particular the capability to request a neighbor to suppress
commands. In addition, the model suggests a mapping between its
and certain status and error indications which clarifies and
the interpretation
All of the header fields except the Status field (called
Information field at some places in RFC-888) remain unchanged.
following table summarizes the suggested format changes in the
field for the various messages by (Type, Code) class
Class Messages Status
-------------------------------------------------------------------
3,0 Request 0
3,1 Confirm 1 active
3,2 Refuse 2 passive
3,3 Cease 3 insufficient
3,4 Cease-ack 4 administratively
5 going
6 parameter
5,0 Hello 0
5,1 I-H-U 1 Up
2,0 Poll 2 Down
1,0 Update 128 unsolicited message
8,0
The changes from RFC-888 are as follows
1. The status codes have been combined in two classes, one for
messages involved in starting and stopping the protocol and
other for those messages involved in maintaining the protocol
exchanging reachability information. Some messages of either
may not use all the status codes assigned
2. The status codes for the Request and Confirm indicate whether
sender can operate in active or passive mode. In RFC-888 this
must be zero; however, RFC-888 does not specify any mechanism
decide how the neighbors poll each other
3. The status codes for the Cease, Refuse and Cease-ack have the
interpretation. This provides a clear and unambiguous
when the protocol is terminated due to an unusual situation,
instance if the NOC dynamically repartitions the ARPANET.
assigned codes are not consistent with RFC-888, since the codes
the Refuse and Cease were assigned conflicting values; however,
differences are minor and should cause no significant problems
Exterior Gateway Protocol Formal Specification Page 27
D.L.
4. The status codes for the Hello, I-H-U, Poll, Update and Error
the same interpretation. Codes 0 through 2 are mutually
and are chosen solely on the basis of the state of the sender.
the case of the Update (and possibly Error) one of these codes
be combined with the "unsolicited bit," which corresponds to
128. In RFC-888 this field is unused for the Poll and Error and
contain only zero or 128 for the Update, so that the default case
to assume that reciprocal reachability cannot be determined by
messages
5. Some of the reachability codes defined in RFC-888 have been
as not applicable
Exterior Gateway Protocol Formal Specification Page 28
D.L.
Appendix C. Reachability
The following table shows the state transitions which can occur
a system of two neighboring EGP gateways. Besides being useful in
design and verification of the protocol, the table is useful
implementation and testing
The system of two neighboring EGP gateways is modelled as
finite-state automaton constructed as the cartesian product of two
machines as defined above. Each state of this machine is represented
[i,j], where i and j are states of the original machine. Each line
the table shows one state transition of the machine in the form
[i1,j1] -> [i2,j2] E
which specifies the machine in state [i1,j1] presented with event
transitions to state [i2,j2] and generates action A. Multiple
are separated by the "/" symbol. The special symbol "*" represents
set of lines where all "*"s in the line take on the (same) values 0 - 4
in turn
The table shows only those transitions which can occur as
result of events arriving at one of the two neighbors. The full
includes a duplicate set of lines for the other neighbor as well,
each line derived from a line of the table below using
transformation
[i1,j1] -> [i2,j2] E A => [j1,i1] -> [j2,i2] E
State State Event
---------------------------------------------------
[*,4] -> [0,4] Cease Cease-
[0,1] -> [2,1] Request Confirm/Hello/Up/t
[0,1] -> [0,1] Request
[0,*] -> [1,*] Start Request/t
[1,1] -> [2,1] Request Confirm/Hello/Up/t
[1,2] -> [2,2] Confirm Hello/Up/t
[1,3] -> [2,3] Confirm Hello/Up/t
[1,0] -> [0,0] Refuse
[1,*] -> [1,*] Start Request/r
[1,*] -> [0,*] Stop
[1,*] -> [1,*] t1 Request/t
[2,1] -> [3,1] Up Down/Hello/Poll/t1/t
[2,1] -> [2,1] Request Confirm/Hello/Up/t
[2,2] -> [2,2] Hello I-H-
[2,3] -> [2,3] Hello I-H-
[2,2] -> [2,2] I-H-U
Exterior Gateway Protocol Formal Specification Page 29
D.L.
[2,3] -> [2,3] I-H-U
[2,*] -> [1,*] Start Request/r
[2,*] -> [4,*] Stop Cease/t
[2,1] -> [2,1] t1 Hello/t
[2,2] -> [2,2] t1 Hello/t
[2,3] -> [2,3] t1 Hello/t
[3,1] -> [2,1] Down
[3,2] -> [2,2] Down
[3,3] -> [2,3] Down
[3,1] -> [2,1] Request Confirm/Hello/Up/t
[3,2] -> [3,2] Hello I-H-
[3,3] -> [3,3] Hello I-H-
[3,2] -> [3,2] I-H-U
[3,3] -> [3,3] I-H-U
[3,3] -> [3,3] Poll
[3,3] -> [3,3] Update
[3,*] -> [1,*] Start Request/r
[3,*] -> [4,*] Stop Cease/t
[3,1] -> [3,1] t1 Hello/t
[3,2] -> [3,2] t1 Hello/t
[3,3] -> [3,3] t1 Hello/t
[3,1] -> [3,1] t2 Poll/t
[3,2] -> [3,2] t2 Poll/t
[3,3] -> [3,3] t2 Poll/t
[4,1] -> [4,1] Request
[4,*] -> [0,*] Cease Cease-
[4,0] -> [0,0] Cease-ack
[4,*] -> [0,*] Stop
[4,*] -> [4,*] t1 Cease/t
In the state-machine model defined in this document all states
the above machine are reachable; however, some are reachable only
extreme cases when one neighbor crashes, for example. In the
case where only one of the neighbors initiates and terminates
protocol and neither one crashes, for example, not all states
reachable. Following is a matrix showing the states which can
reached in this case, where the neighbor that initiates and
the protocol is called the active gateway and the other the
gateway
Exterior Gateway Protocol Formal Specification Page 30
D.L.
Passive
Active 0 Idle 1 Aqsn 2 Down 3 Up 4
Gateway +-----------+-----------+-----------+-----------+-----------+
0 Idle |stable | | | |unstable |
1 Aqsn |unstable |unstable |unstable |unstable |unstable |
2 Down | | |stable |unstable | |
3 Up | | |unstable |stable | |
4 Cease |unstable |unstable |unstable |unstable |unstable |
+-----------+-----------+-----------+-----------+-----------+
In the above matrix the blank entries represent unreachable states
while those marked unstable represent transient states which
persist for long, due to retransmission of Request and Hello messages
for example
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
