rfc904.txt

RFC 相关的技术文档

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 
protocol.

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
    to the Acquistion state.

Acquisition State (1)

    In the Acquisition state the gateway periodically retransmits
    Request commands.  Upon receiving a Confirm response it initializes

Exterior Gateway Protocol Formal Specification                    Page 3
D.L. Mills


    the state variables and transitions to the Down state.  Upon
    receiving a Refuse response it returns to the Idle state.  The
    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 a
    Confirm response has been received for a previously sent Request.
    The neighbor-reachability protocol has declared the neighbor to be
    down.  In this state the gateway processes Request, Cease and Hello
    commands and responds as required.  It periodically retransmits
    Hello commands if enabled.  It does not process Poll commands and
    does not send them, but may optionally process an unsolicited Update
    indication.

Up State (3)

    In the Up state the neighbor-reachability protocol has declared the
    neighbor to be up.  In this state the gateway processes and responds
    to all commands.  It periodically retransmits Hello commands, if
    enabled, and Poll commands.

Cease State (4)

    A Stop event causes a Cease command to be sent and a transition to
    the Cease state.  In this state the gateway periodically retransmits
    the Cease command and returns to the Idle state upon receiving a
    Cease-ack response or a another Stop event.  The defined state
    transitions are designed to ensure that the neighbor does with high
    probability receive the Cease command and stop the protocol.

     In following sections of this document document a state machine
which can serve as a model for implementation is described.  It may
happen that implementators may deviate from this model while conforming
to the protocol specification;  however, in order to verify conformance
to the specification, the state-machine model is intended as the
reference model.

     Although not mentioned specifically in this document, it should be
understood that all Internet gateways must include support for the
Internet Control Message Protocol (ICMP), specifically ICMP Redirect and
ICMP Destination Unreachable messages.

2.  Nomenclature

     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. Mills


        Name            Function
        ------------------------------------------------------
        Request         request acquisition of neighbor and/or
                        initialize polling variables
        Confirm         confirm acquisition of neighbor and/or
                        initialize polling variables
        Refuse          refuse acquisition of neighbor
        Cease           request de-acquisition of neighbor
        Cease-ack       confirm de-acquisition of neighbor
        Hello           request neigbor reachability
        I-H-U           confirm neigbor reachability
        Poll            request net-reachability update
        Update          net-reachability update
        Error           error

     EGP messages are classed as commands which request some action,
responses, which are sent to indicate the status of that action, and
indications, which are similar to responses, but may be sent at any
time.  Following is a list of commands along with their possible
responses.

        Command         Corresponding Responses
        ---------------------------------------
        Request         Confirm, Refuse, Error
        Cease           Cease-ack, Error
        Hello           I-H-U, Error
        Poll            Update, Error

     The Update and Error messages are classed both as responses and
indications.  When sent in reply to a previous command, either of these
messages is classed as a response.  In some circumstances an unsolicited
Update message can be sent, in which case it is classed as an
indication.  The use of the Error message other than as a response to a
previous command is a topic for further study.

3.  State Machine

     This section describes the state-machine model for EGP, including
the variables and constants which establish the state at any time, the
events which cause the state transitions, the actions which result from
these transitions and the state-transition table which defines the
behavior.

3.1.  State Variables

     The state-machine model includes a number of state variables which
establish the state of the protocol between the gateway and each of its
neighbors.  Thus, a gateway maintaining EGP with a number of neighbors
must maintain a separate set of these state variables for each neighbor.
The current state, events and actions of the state machine apply to each

Exterior Gateway Protocol Formal Specification                    Page 5
D.L. Mills


neighbor separately.

     The model assumes that system resources, including the set of state
variables, are allocated when the state machine leaves the Idle state,
either because of the arrival of a Request specifying a new neighbor
addreess, or because of a Start event specifying a new neighbor address.
When either of these events occur the values of the state variables are
initialized as indicated below.  Upon return to the Idle state all
resources, including the set of state variables, are deallocated and
returned to the system.  Implementators may, of course, elect to
dedicate resources and state variables permananently.

     Included among the set of state variables are the following which
determine the state transitions of the model.  Initial values for all of
the variables except the send sequence number S are set during the
initial Request/Confirm exchange.  The initial value for S is arbitrary.

        Name    Function
        --------------------------------------------------------------
        R       receive sequence number
        S       send sequence number
        T1      interval between Hello command retransmissions
        T2      interval between Poll command retransmissions
        T3      interval during which neighbor-reachability
                indications are counted
        M       hello polling mode
        t1      timer 1 (used to control Request, Hello and Cease
                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 and
similar internal housekeeping functions.  The function and management of
the cited variables are discussed in Section 4.

3.2.  Fixed Parameters

     This section defines several fixed parameters which characterize
the gateway functions.  Included is a suggested value for each parameter
based on experimental implementations in the Internet system.  These
values may or may not be appropriate for the individual configuration.

     Following is a list of time-interval parameters which control
retransmissions and other time-dependent functions.

Exterior Gateway Protocol Formal Specification                    Page 6
D.L. Mills


        Name    Value   Description
        --------------------------------------------------------------
        P1      30 sec  minimum interval acceptable between successive
                        Hello commands received
        P2      2 min   minimum interval acceptable between successive