Exterior Gateway Protocol formal specification
RFC 904

Document Type RFC - Historic (April 1984; No errata)
Updates RFC 888, RFC 827
Last updated 2013-03-02
Stream Legacy stream
Formats plain text html pdf htmlized (tools) htmlized bibtex
Stream Legacy state (None)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state RFC 904 (Historic)
Telechat date
Responsible AD (None)
Send notices to (None)
Network Working Group                                   D.L.  Mills
Request for Comments:  904                              April 1984

             Exterior Gateway Protocol Formal Specification

0.  Status of this Memo

     This RFC is the specification of the Exterior Gateway Protocol
(EGP).  This document updates RFCs 827 and 888.  This RFC specifies a
standard for the DARPA community.  Interactions between gateways of
different autonomous systems in the ARPA-Internet must follow this 

1.  Introduction

     This document is a formal specification of the Exterior Gateway
Protocol (EGP), which is used to exchange net-reachability information
between Internet gateways belonging to the same or different autonomous
systems.  The specification is intended as a reference guide for
implementation, testing and verification and includes suggested
algorithmic parameters suitable for operation over a wide set of
configurations, including the ARPANET and many local-network
technologies now part of the Internet system.

     Specifically excluded in this document is discussion on the
background, application and limitations of EGP, which have been
discussed elsewhere (RFC-827, RFC-888).  If, as expected, EGP evolves to
include topologies not restricted to tree-structures and to incorporate
full routing capabilities, this specification will be amended or
obsoleted accordingly.  However, it is expected that, as new features
are added to EGP, the basic protocol mechanisms described here will
remain substantially unchanged, with only the format and interpretation
of the Update message (see below) changed.

     Section 2 of this document describes the nomenclature used, while
Section 3 describes the state-machine model, including events, actions,
parameters and state transitions.  Section 4 contains a functional
description of the operation of the machine, together with specific
procedures and algorithms.  Appendix A describes the EGP message
formats, while Appendix B contains a summary of the minor differences
between these and the formats described in RFC-888.  Appendix C presents
a reachability analysis including a table of composite state transitions
for a system of two communicating EGP gateways.

1.1.  Summary and Overview

     EGP exists in order to convey net-reachability information between
neighboring gateways, possibly in different autonomous systems.  The
protocol includes mechanisms to acquire neighbors, monitor neighbor
reachability and exchange net-reachability information in the form of
Update messages.  The protocol is based on periodic polling using
Hello/I-Heard-You (I-H-U) message exchanges to monitor neighbor
reachability and Poll commands to solicit Update responses.

     Specification of EGP is based on a formal model consisting of a

Exterior Gateway Protocol Formal Specification                    Page 2
D.L. Mills

finite-state automaton with defined events, state transitions and
actions.  The following diagram shows a simplified graphical
representation of this machine (see Section 3.4 for a detailed state
transition table).

          |       |---------------+---------------+
    +---->| Idle  |               A               A
    |     |       |-----------+   |               |
    |     +-------+           |   |               |
    |       |   A     Request |   | Cease         | Cease
    | Start |   | Cease       |   |               |
    |       V   | Refuse      V   |               |
    |     +-------+ Confirm +-------+    Up   +-------+
    |     |       |-------->|       |-------->|       |
    |     | Aqsn  |         | Down  |   Down  |  Up   |
    |     |       |----+    |       |<--------|       |
    |     +-------+    |    +-------+         +-------+
    |                  |        |                 |
    | Stop             |        |                 |
    | Cease-ack        | Stop   | Stop            | Stop
    |     +-------+    |        |                 |
    |     |       |    V        V                 V
    +-----| Cease |<---+--------+-----------------+
          |       |

     Following is a brief summary and overview of gateway operations by
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 in
    progress.  It responds only to a Request command or a Start event
    (system or operator initiated) and ignores all other commands and
    responses.  The gateway may optionally return a Cease-ack response
    to a Cease command in this state.

    Upon receipt of a Request command the gateway initializes the state
    variables as described in Section 3.1, sends a Confirm response and
    transitions to the Down state, if resource committments permit, or
    sends a Refuse response and returns to the Idle state if not.  Upon
    receipt of a Start event it sends a Request command and transitions
Show full document text