RFC 904 (rfc904) - Page 1 of 29

Exterior Gateway Protocol formal specification

Alternative Format: Original Text Document
Next >
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
Next >