Network Working Group D.L. MillsRequest for Comments: 904 APRil 1984 Exterior Gateway Protocol Formal Specification0. Status of this Memo This RFCis the specification of the Exterior Gateway Protocol(EGP). This document updates RFCs 827 and 888. This RFCspecifies astandard for the DARPA community. Interactions between gateways ofdifferent autonomous systems in the ARPA-Internet must follow this protocol.1. IntrodUCtion This document is a formal specification of the Exterior GatewayProtocol (EGP), which is used to exchange net-reachability informationbetween Internet gateways belonging to the same or different autonomoussystems. The specification is intended as a reference guide forimplementation, testing and verification and includes suggestedalgorithmic parameters suitable for Operation over a wide set ofconfigurations, including the ARPANET and many local-networktechnologies now part of the Internet system. Specifically excluded in this document is discussion on thebackground, application and limitations of EGP, which have beendiscussed elsewhere (RFC-827, RFC-888). If, as eXPected, EGP evolves toinclude topologies not restricted to tree-structures and to incorporatefull routing capabilities, this specification will be amended orobsoleted accordingly. However, it is expected that, as new featuresare added to EGP, the basic protocol mechanisms described here willremain substantially unchanged, with only the format and interpretationof the Update message (see below) changed. Section 2 of this document describes the nomenclature used, whileSection 3 describes the state-machine model, including events, actions,parameters and state transitions. Section 4 contains a functionaldescription of the operation of the machine, together with specificprocedures and algorithms. Appendix A describes the EGP messageformats, while Appendix B contains a summary of the minor differencesbetween these and the formats described in RFC-888. Appendix C presentsa reachability analysis including a table of composite state transitionsfor a system of two communicating EGP gateways.1.1. Summary and Overview EGP exists in order to convey net-reachability information betweenneighboring gateways, possibly in different autonomous systems. Theprotocol includes mechanisms to acquire neighbors, monitor neighborreachability and exchange net-reachability information in the form ofUpdate messages. The protocol is based on periodic polling usingHello/I-Heard-You (I-H-U) message exchanges to monitor neighborreachability and Poll commands to solicit Update responses.
Specification of EGP is based on a formal model consisting of aExterior Gateway Protocol Formal Specification Page 2D.L. Millsfinite-state automaton with defined events, state transitions andactions. The following diagram shows a simplified graphicalrepresentation of this machine (see Section 3.4 for a detailed statetransition 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 bystate 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 initializesExterior Gateway Protocol Formal Specification Page 3D.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 machinewhich can serve as a model for implementation is described. It mayhappen that implementators may deviate from this model while conformingto the protocol specification; however, in order to verify conformanceto the specification, the state-machine model is intended as thereference model. Although not mentioned specifically in this document, it should beunderstood that all Internet gateways must include support for theInternet Control Message Protocol (ICMP), specifically ICMP Redirect andICMP 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 4D.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, andindications, which are similar to responses, but may be sent at anytime. Following is a list of commands along with their possibleresponses. 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 andindications. When sent in reply to a previous command, either of thesemessages is classed as a response. In some circumstances an unsolicitedUpdate message can be sent, in which case it is classed as anindication. The use of the Error message other than as a response to aprevious command is a topic for further study.3. State Machine This section describes the state-machine model for EGP, includingthe variables and constants which establish the state at any time, theevents which cause the state transitions, the actions which result fromthese transitions and the state-transition table which defines thebehavior.3.1. State Variables The state-machine model includes a number of state variables whichestablish the state of the protocol between the gateway and each of itsneighbors. Thus, a gateway maintaining EGP with a number of neighborsmust maintain a separate set of these state variables for each neighbor.The current state, events and actions of the state machine apply to eachExterior Gateway Protocol Formal Specification Page 5D.L. Millsneighbor separately. The model assumes that system resources, including the set of statevariables, are allocated when the state machine leaves the Idle state,either because of the arrival of a Request specifying a new neighboraddreess, or because of a Start event specifying a new neighbor address.When either of these events occur the values of the state variables areinitialized as indicated below. Upon return to the Idle state allresources, including the set of state variables, are deallocated andreturned to the system. Implementators may, of course, elect todedicate resources and state variables permananently. Included among the set of state variables are the following whichdetermine the state transitions of the model. Initial values for all ofthe variables except the send sequence number S are set during theinitial 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 ofthe cited variables are discussed in Section 4.3.2. Fixed Parameters This section defines several fixed parameters which characterizethe gateway functions. Included is a suggested value for each parameterbased on experimental implementations in the Internet system. Thesevalues may or may not be appropriate for the individual configuration. Following is a list of time-interval parameters which controlretransmissions and other time-dependent functions.Exterior Gateway Protocol Formal Specification Page 6D.L. Mills Name Value Description -------------------------------------------------------------- P1 30 sec minimum interval acceptable between successive Hello commands received P2 2 min minimum interval acceptable between successive Poll commands recieved P3 30 sec interval between Request or Cease command retransmissions P4 1 hr interval during which state variables are maintained in the absence of commands or responses in the Down and Up states. P5 2 min interval during which state variables are maintained in the absence of responses in the Acquisition and Cease states Parameters P4 and P5 are used only if the abort-timer option isimplemented. Parameter P4 establishes how long the machine will remainin the Down and Up states in the absence of commands or responses andwould ordinarily be set to sustain state information while the neighboris dumped and restarted, for example. Parameter P5 establishes how longthe machine will remain in the Acquisition or Cease states in theabsence of responses and would ordinarily be set in the same order asthe expected value of T3 variables. Following is a list of other parameters of interest. Name Active Passive Description ----------------------------------------------- j 3 1 neighbor-up threshold k 1 4 neighbor-down threshold The j and k parameters establish the "noise immunity" of theneighbor-reachability protocol described later. The values in theActive column are suggested if the gateway elects to do hello polling,while the values in the Passive column are suggested otherwise.3.3. Events Following is a list of events that can cause state transitions inthe model.Exterior Gateway Protocol Formal Specification Page 7D.L. MillsName Event----------------------------------------------------------------------Up At least j neighbor-reachability indications have been received within the last T3 seconds.
Down At most k neighbor-reachabilitiy indications have been 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 or operator intervention.Stop/t3 Stop event has been recognized due to (a) system or operator intervention or (b) expiration of the abort 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-reachabilityindication, 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 polling disabled) and either a Hello or Poll command is received with the "Up state" code in the Status field.3.4. State Transition Table The following table summarizes the state transitions that can occurin response to the events listed above. Transitions are shown in theform n/a, where n is the next state and a represents the action.Exterior Gateway Protocol Formal Specification Page 8D.L. Mills 0 Idle 1 Aqsn 2 Down 3 Up 4 Cease +-----------+-----------+-----------+-----------+-----------+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-ack0/Cease-ack0/Cease-ack0/Cease-ack0/Cease-ackCease-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 the
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 Actions The following table describes in detail the transitions of thestate machine and the actions evoked. Next MessageEvent State Sent Actions------------------------------------------------------------------------Idle State (0)Request 2 Confirm Initialize state variables and Hello reset timer t1 to T1 seconds and 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 and reset timer t3 to P5 seconds.Acquisition State (1)Request 2 Confirm Initialize state variables and Hello reset timer t1 to T1 seconds and reset timer t3 to P5 seconds.Confirm 2 Hello Initialize state variables andExterior Gateway Protocol Formal Specification Page 9D.L. Mills reset timer t1 to T1 seconds and reset timer t3 to P5 seconds.Refuse 0 Stop timers and return resources.Cease 0 Cease-ack Stop timers and return resources.Start 1 Request Reset timer t1 to P3 seconds and reset timer t3 to P5 seconds.Stop/t3 0 Stop timers and return resources.t1 1 Request Reset timer t1 to P3 seconds.Down State (2)Note: Reset timer t3 to P4 seconds on receipt of a reachabilityindication.Up 3 Poll Reset timer t2 to T2 seconds.Request 2 Confirm Reinitialize state variables and Hello reset timer t1 to T1 seconds and reset timer t3 to P5 seconds.Cease 0 Cease-ack Stop timers and return resources.Hello 2 I-H-UI-H-U 2 Process neighbor-reachability info.Start 1 Request Reset timer t1 to P3 seconds and reset timer t3 to P5 seconds.Stop/t3 4 Cease Reset timer t1 to P3 seconds and 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 reachabilityindication.Down 2 Stop timer t2.Request 2 Confirm Renitialize state variables and Hello reset timer t1 to T1 seconds and reset timer t3 to P5 seconds.Cease 0 Cease-ack Stop timers and return resources.Hello 3 I-H-UI-H-U 3 Process neighbor-reachability info.Poll 3 UpdateUpdate 3 Process net-reachability info.Start 1 Request Reset timer t1 to P3 seconds and reset timer t3 to P5 seconds.Stop/t3 4 Cease Reset timer t1 to P3 seconds and reset timer t3 to P5 seconds.Exterior Gateway Protocol Formal Specification Page 10D.L. Millst1 3 Hello Reset timer t1 to T1 seconds.t2 3 Poll Reset timer t2 to T2 seconds.Cease State (4)Request 4 CeaseCease 0 Cease-ack Stop timers and return resources.Cease-ack 0 Stop timers and return resources.Stop/t3 0 Stop timers and return resources.t1 4 Cease Reset timer t1 to P3 seconds.4. Functional Description This section contains detailed descriptions of the variousprocedures and algorithms used to manage the protocol.4.1. Managing the State Variables The state variables which characterize the protocol are summarizedin Section 3.1. This section describes the detailed management of thesevariables, including sequence numbers, polling intervals and timers.4.1.1. Sequence Numbers All EGP commands and replies carry a sequence number. The statevariable R records the last sequence number received in a command fromthat neighbor. The current value of R is used as the sequence numberfor all replies and indications sent to the neighbor until a commandwith a different sequence number is received from that neighbor. Implementors are free to manage the sequence numbers of thecommands sent; however, it is suggested that a separate send statevariable S be maintained for each EGP neighbor and that its value beincremented just before the time an Poll command is sent and at no othertimes. The actions upon receipt of a response or indication withsequence number not equal to S is not specified; however, it is
recommended these be discarded.4.1.1. Polling Intervals As part of the Request/Confirm exchange a set of polling intervalsare established including T1, which establishes the interval betweenHello command retransmissions, and T2, which establishes the intervalbetween Poll retransmissions. Each gateway configuration is characterized by a set of fixedparameters, including P1, which specifies the minimum polling intervalExterior Gateway Protocol Formal Specification Page 11D.L. Millsat which it will respond to Hello commands, and P2, which specifies theminimum polling interval at which it will respond to Poll commands. P1and 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 theS1 and S2 fields in the message to calculate its own T1 and T2 statevariables, respectively. Implementors are free to perform thiscalculation in arbitrary ways; however, the following constraints mustbe observed:1. If T1 < S1 the neighbor may discard Hello commands. If T2 < S2 the neighbor may discard Poll commands.2. The time window T3 in which neighbor-reachability indications are counted is dependent on T1. In the case where two neighbors select widely differing values for their T3 state variables, the neighbor-reachability algorithm may not work properly. This can be 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 Refuse 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 hasbeen found appropriate in the experimental implementations.Implementors may choose to make T3 a fixed parameter in those caseswhere the path between the neighbors has well-known characteristics. Note that, if a gateway attempts to send Hello commands near therate max(P1, S1) or Poll commands near the rate max(P2, S2), theneighbor may observe their succeeding arrivals to violate the pollingrestrictions due to bunching in the net. For this reason the gatewayshould send at rates somewhat below these. Just how much below theserates is appropriate depends on many factors beyond the scope of thisspecification.4.1.3. Hello Polling Mode The neighbor-reachability algorithm can be used in either theactive or passive mode. In the active mode Hello commands are sentperiodically along with Poll commands, with reachability determined bythe corresponding I-H-U and Update responses. In the passive mode Hellocommands are not sent and I-H-U responses are not expected.Reachability is then determined from the Status field of received Helloor Poll commands or Update responses.
The M state variable specifies whether the gateway operates in theactive or passive mode. At least one of the two neighbors sharing theExterior Gateway Protocol Formal Specification Page 12D.L. Millsprotocol must operate in the active mode; however, theneighbor-reachability protocol is designed to work even if bothneighbors operate in the active mode. The value of M is determined fromthe Status field of a Request command or Confirm response. The sendersets this field according to whether the implementation supports theactive mode, passive mode or both: Status Sender capabilities -------------------------------- 0 either active or passive 1 active only 2 passive only The receiver inspects this field and sets the value of M accordingto its own capabilities as follows: Status Receiver capabilites field 0 1 2 ------------------------------- 0 * active passive 1 passive active passive 2 active active ** In the case of "*" the mode is determined by comparing theautonomous system numbers of the neigbors. The neighbor with thesmallest such number assumes active mode, while the other neighborassumes passive mode. In the case of "**" the neighbor may either senda Refuse response or declare a Stop event, depending on state.4.1.4. Timers There are three timers defined in the state machine: t1, used tocontrol retransmission of Request, Hello and Cease messages, t2, used tocontrol retransmission of Poll commands, and t3, which serves as anabort-timer mechanism should the protocol hang indefinately. The timersare set to specified values upon entry to each state and count down tozero. In the case of t1 and t2 state-dependent events are declared whenthe timer counts down to zero, after which the timer is reset to thespecified value and counts down again. In the case of t3 a Stop eventis declared when the timer counts down to zero. Implementors may choosenot to implement t3 or, if so, may choose to implement it only incertain states, with the effect that Request, Hello and/or Ceasecommands may be retransmitted indefinately. The following table shows the initial values for each of the timersin each state. A missing value indicates the timer is not used in thatstate. Note that timer t3 is set to P4 upon receipt of aneighbor-reachability indication when in either the Down or Up states.Exterior Gateway Protocol Formal Specification Page 13D.L. Mills Idle Aqsn Down Up Cease Timer 0 1 2 3 4 --------------------------------------------- t1 P3 T1 P3
t2 T2 t3 P5 P5 P54.2. Starting and Stopping the Protocol The Start and Stop events are intrinsic to the system environmentof the gateway. They can be declared as the result of the gatewayprocess being started and stopped by the operator, for example. A Startevent has meaning only in some states; however, a Stop event hasmeaning in all states. In all except the Idle state the abort timer t3 is presumedrunning. This timer is initialized at P5 seconds upon entry to anystate and at P4 seconds upon receipt of a neighbor-reachabilityindication in the Down and Up states. If it expires a Stop event isdeclared. A Stop event can also be declared by an intrinsic systemaction such as a resource problem or operator command. If the abort timer is not implemented a manually-initiated Stopevent can be used to stop the protocol. If this is done in the Down orUp states, the machine will transition to the Cease state and emit aCease command. If the neighbor does not respond to this command themachine will stay in the Cease state indefinately; however, a secondStop event can be used in this state to force a transition to the Idlestate. A Cease command received in any state will cause the gateway toimmediately send the Cease-ack response and transition to the Idlestate. This causes the protocol to be stopped and all system resourcescommitted to the gateway process to be released. The interval betweenthe time the gateway enters the Idle state as the result of receiving aCease command and the time when it next sends a Request command toresume the protocol is not specified; however, it is recommended thisinterval 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, atleast if it has not implemented the abort-timer option. In order toreduce the likelihood of this happening, it is suggested that a gatewayin the Idle state be prepared to reply to a Cease command with aCease-ack response whenever possible.4.3. Determining Neighbor Reachability The purpose of the neighbor-reachability algorithm is to confirmthat the neighbor can safely be considered operational and capable ofExterior Gateway Protocol Formal Specification Page 14D.L. Millsproviding reliable net-reachability information. An equally importantpurpose is to filter noisy reachability information before sending it onto the remainder of the Internet gateway system, thus avoidingunneccesary reachability changes. As described above, a gateway operating in the active mode sendsperiodic Hello commands and listens for I-H-U responses in order todetermine neighbor-reachability indications. A gateway operating in thepassive mode determines reachability indications by means of the Status
field in received Hello commands. Poll commands and Update responsescan 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 thegateway is in the Down and Up states and operates as follows. Define amoving window in time starting at the present and extending backwardsfor t seconds. Then count the number n of neighbor-reachabilityindications which have occured in that window. If n increases to j,then declare a Up event. If n decreases to k, then declare a Downevent. The number n is set to zero upon entering the Down state fromany state other than the Up state. The window t in this algorithm is defined as T3 seconds, the valueof which is suggested as four times T1, which itself is determinedduring the Request/Confirm exchange. For proper operation of thealgorithm only one neighbor-reachability indication is significant inany window of T1 seconds and additional ones are ignored. Note that theonly way n can increase is as the result of a new neighbor-reachabilityindication and the only way it can decrease is as the result of an oldneighbor-reachability indication moving out of the window. The behavior of the algorithm described above and using thesuggested fixed parameters j and k differs depending on whether thegateway is operating in the active or passive mode. In the active mode(j = 3, k = 1 and T3/T1 = 4), once the neighbor has been declared downit will be forced down for at least two T1 intervals and, once it hasbeen declared up it will be forced up for at least two T1 intervals. Itwill not change state unless at least three of the last fourdeterminations of reachability have indicated that change. In the passive mode (j = 1, k = 4 and T3/T1 = 4), the neighbor willbe considered up from the first time the Status field of a Hello or Pollcommand or Update response indicates "Up state" until four successive T1intervals have passed without such indication. This design, suggestedby similar designs used in the ARPANET, has proven effective in theexperimental implementations, but may need to be adjusted for otherconfigurations. It is convenient for the active gateway to send Hello commands at arate of one every T1 seconds and substitute a Poll command for a HelloExterior Gateway Protocol Formal Specification Page 15D.L. Millscommand approximately once every T2 seconds, with theneighbor-reachability indication generated by the corresponding I-H-U orUpdate responses. Its passive neighbor generates neighbor-reachabilityindications from the Status field of received Hello and Poll commandsand Update responses. Implementors may find the following model useful in theunderstanding and implementation of this algorithm. Consider an n-bitshift register that shifts one bit to the right each T1-second interval.
If a neighbor-reachability indication was received during the preceedingT1-second interval a one bit is shifted into the register at the end ofthe interval; otherwise, a zero bit is shifted. A table of 2**nentries indexed by the contents of the register can be used to calculatethe number of one bits, which can then be used to declare theappropriate event to the state machine. A value of n equal to four hasbeen found useful in the experimental implementations.4.4. Determining Network Reachability Network reachability information is encoded into Update messages inthe form of lists of nets and gateways. The IP Source Address field ofthe Poll command is used to specify a network common to the autonomoussystems of each of the neighbors, which is usually, but not necessarily,the one common to the neighbors themselves. The Update responseincludes a list of gateways on the common net. Associated with eachgateway is a list of the networks reachable via that gateway togetherwith corresponding hop counts. It is important to understand that, at the present state ofdevelopment as described in RFC-827 and RFC-888, the EGP architecturalmodel restricts the interpretation of "reachable" in this context. Thisconsideration, as well as the implied topological restrictions, arebeyond the scope of discussion here. The reader is referred to the RFCsfor 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 onlythose gateways directly connected to the net specified in the IP SourceNetwork field of the last-received Poll command. The internal listincludes some or all of the gateways in the same autonomous system asthe sender, together with the nets which are reachable via thesegateways, with the sending gateway listed first. A net is reachable inthis context if a path exists to that net including only gateways in thesystem. The external list includes those gateways in other autonomoussystems known to the sender. It is important to realize that the hopcounts do not represent a routing metric and are comparable betweendifferent gateways only if those gateways belong to the same autonomoussystem; that is, are in the internal list.Exterior Gateway Protocol Formal Specification Page 16D.L. Mills According to the current system architectural model, only gatewaysbelonging to a designated system, called the core system, may includethe external list in their Update responses. All other gateways mayinclude only those gateways belonging to the same system and can claimreachability for a particular net only if that net is reachable in thesame system. The interval between successive Poll commands T2 is determinedduring the Request/Confirm exchange. However, the specification permitsat most one unsolicited Update indication between succeeding Poll
commands received from the neighbor. It is the intent of the model herethat 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 thislimitation. Occasionally it may happen that a Poll command or Update responseis lost in the network, with the effect that net-reachabilityinformation may not be available until after another T2 interval. As animplementation option, the gateway sending a Poll command and notreceiving an Update response after T1 seconds may send another Poll.The gateway receiving this Poll may either (a) send an Update responseif it never received the original Poll for that interval, (b) send asecond Update response (which counts as the unsolicited Updateindication mentioned in the preceeding paragraph) or (c) send an Errorresponse or not respond at all in other cases.4.5. Error Messages Error messages can be used to report problems such as described inAppendix A in connection with the Error Response/Indication messageformat. In general, an Error message is sent upon receipt of anothercommand or response with bad format, content or ordering, but never inresponse to another Error message. Receipt of an Error message shouldbe considered advisory and not result in change of state, exceptpossibly to evoke a Stop event.Exterior Gateway Protocol Formal Specification Page 17D.L. MillsAppendix A. EGP Message Formats The formats for the various EGP messages are described in thissection. 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 itsfields. 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 version (currently 2)Type identifies the message typeCode identifies the message code (suBType)Status contains message-dependent status informationChecksum The EGP checksum is the 16-bit one's complement of the one's complement sum of the EGP message starting with the EGP version number field. When
computing the checksum the checksum field itself should be zero.Autonomous System # assigned number identifying the particular autonomous systemSequence # send state variable (commands) or receive state variable (responses and indications) Following is a description of each of the message formats. Notethat the above description applies to all formats and will not berepeated.Exterior Gateway Protocol Formal Specification Page 18D.L. MillsA.1. Neighbor Acquisition Messages 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 inRequest and Confirm messages.Type 3Code 0 Request command 1 Confirm response 2 Refuse response 3 Cease command 4 Cease-ack responseStatus (see below) 0 unspecified 1 active mode 2 passive mode 3 insufficient resources 4 administratively prohibited 5 going down 6 parameter problem 7 protocol violationHello 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 ofscenarios in which they might be used.Exterior Gateway Protocol Formal Specification Page 19D.L. MillsCode Status Scenarios-------------------------------------------------------------------0 unspecified when nothing else fits1 active mode Request/Confirm only2 passive mode Request/Confirm only 3 insufficient resources 1. out of table space 2. out of system resources4 administratively 1. unknown Autonomous System prohibited 2. use another gateway
5 going down 1. operator initiated Stop 2. abort timeout6 parameter problem 1. nonsense polling parameters 2. unable to assume compatible mode7 protocol violation 1. Invalid command or response received in this stateExterior Gateway Protocol Formal Specification Page 20D.L. MillsA.2. Neighbor Reachability Messages 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 5Code 0 Hello command 1 I-H-U responseStatus 0 indeterminate 1 Up state 2 Down stateExterior Gateway Protocol Formal Specification Page 21D.L. MillsA.3. Poll Command 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 2Code 0Status 0 indeterminate 1 Up state 2 Down stateIP Source Network IP network number of the network about which reachability information is being requested (coded as 1, 2 or 3 octets, left justified with trailing zeros)Exterior Gateway Protocol Formal Specification Page 22D.L. MillsA.4. Update Response/Indication 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 23D.L. MillsType 1Code 0Status 0 indeterminate 1 Up state 2 Down state 128 unsolicited message bit# of Int Gwys number of interior gateways appearing in this message# of Ext Gwys number of exterior gateways appearing in this messageIP Source Network IP network number of the network about which reachability information is being supplied (coded as 1, 2 or 3 octets, left justified with
trailing zeros)Gateway IP addresses IP address (without network number) of the gateway block (coded as 1, 2 or 3 octets)# of Distances number of distances in the gateway blockDistances numbers depending on autonomous system architecture# of Nets number of nets at each distanceNets IP network number reachable via the gatewayExterior Gateway Protocol Formal Specification Page 24D.L. MillsA.5. Error Response/Indication 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 8Code 0Status 0 indeterminate 1 Up state 2 Down state 128 unsolicited message bitReason (see below) 0 unspecified 1 bad EGP header format 2 bad EGP data field format 3 reachability info unavailable 4 excessive polling rate 5 no responseError Message Header first three 32-bit words of EGP headerFollowing is a summary of the assigned Reason codes along with a list ofscenarios in which they might be used.Exterior Gateway Protocol Formal Specification Page 25D.L. MillsCode Reason Scenarios------------------------------------------------------------------------0 unspecified when nothing else fits1 bad EGP header format 1. bad message length 2. invalid Type, Code or Status fields Notes: The recipient can determine which of the above hold by inspecting the EGP header included in the message. An
instance of a wrong EGP version or bad checksum should not be reported, since the original recipient can not trust the header format. An instance of an unknown autonomous system should be caught at acquistion time.2 bad EGP data field 1. nonsense polling rates format (Request/Confirm) 2. invalid Update message format 3. response IP Net Address field does not match command (Update) Notes: An instance of nonsense polling intervals (e.g. too long to be useful) specified in a Request or Confirm should result in a Refuse or Cease with this cause specified.3 reachability info 1. no info available on net specified in unavailable IP Net Address field (Poll)4 excessive polling rate 1. two or more Hello commands received within minimum specified polling interval 2. two or more Poll commands received within minimum specified polling interval 3. two or more Request commands received within some (reasonably short) interval Notes: The recipient can determine which of the above hold by inspecting the EGP header included in the message.5 no response 1. no Update received for Poll within some (reasonably long) intervalExterior Gateway Protocol Formal Specification Page 26D.L. MillsAppendix B. Comparison with RFC-888 Minor functional enhancements are necessary in the RFC-888 messageformats to support certain features assumed of the state-machine model,in particular the capability to request a neighbor to suppress Hellocommands. In addition, the model suggests a mapping between its statesand certain status and error indications which clarifies and generalizesthe interpretation. All of the header fields except the Status field (called theInformation field at some places in RFC-888) remain unchanged. Thefollowing table summarizes the suggested format changes in the Statusfield for the various messages by (Type, Code) class.Class Messages Status Codes-------------------------------------------------------------------
3,0 Request 0 unspecified3,1 Confirm 1 active mode3,2 Refuse 2 passive mode3,3 Cease 3 insufficient resources3,4 Cease-ack 4 administratively prohibited 5 going down 6 parameter problem5,0 Hello 0 indeterminate5,1 I-H-U 1 Up state2,0 Poll 2 Down state1,0 Update 128 unsolicited message bit8,0 ErrorThe changes from RFC-888 are as follows:1. The status codes have been combined in two classes, one for those messages involved in starting and stopping the protocol and the other for those messages involved in maintaining the protocol and exchanging reachability information. Some messages of either class may not use all the status codes assigned.2. The status codes for the Request and Confirm indicate whether the sender can operate in active or passive mode. In RFC-888 this field must be zero; however, RFC-888 does not specify any mechanism to decide how the neighbors poll each other.3. The status codes for the Cease, Refuse and Cease-ack have the same interpretation. This provides a clear and unambiguous indication when the protocol is terminated due to an unusual situation, for instance if the NOC dynamically repartitions the ARPANET. The assigned codes are not consistent with RFC-888, since the codes for the Refuse and Cease were assigned conflicting values; however, the differences are minor and should cause no significant problems.Exterior Gateway Protocol Formal Specification Page 27D.L. Mills4. The status codes for the Hello, I-H-U, Poll, Update and Error have the same interpretation. Codes 0 through 2 are mutually exclusive and are chosen solely on the basis of the state of the sender. In the case of the Update (and possibly Error) one of these codes can be combined with the "unsolicited bit," which corresponds to code 128. In RFC-888 this field is unused for the Poll and Error and may contain only zero or 128 for the Update, so that the default case is to assume that reciprocal reachability cannot be determined by these messages.5. Some of the reachability codes defined in RFC-888 have been removed as not applicable.Exterior Gateway Protocol Formal Specification Page 28D.L. MillsAppendix C. Reachability Analysis The following table shows the state transitions which can occur ina system of two neighboring EGP gateways. Besides being useful in thedesign and verification of the protocol, the table is useful forimplementation and testing. The system of two neighboring EGP gateways is modelled as a
finite-state automaton constructed as the cartesian product of two statemachines as defined above. Each state of this machine is represented as[i,j], where i and j are states of the original machine. Each line ofthe table shows one state transition of the machine in the form: [i1,j1] -> [i2,j2] E Awhich specifies the machine in state [i1,j1] presented with event Etransitions to state [i2,j2] and generates action A. Multiple actionsare separated by the "/" symbol. The special symbol "*" represents theset of lines where all "*"s in the line take on the (same) values 0 - 4in turn. The table shows only those transitions which can occur as theresult of events arriving at one of the two neighbors. The full tableincludes a duplicate set of lines for the other neighbor as well, witheach line derived from a line of the table below using thetransformation: [i1,j1] -> [i2,j2] E A => [j1,i1] -> [j2,i2] E AState State Event Actions---------------------------------------------------[*,4] -> [0,4] Cease Cease-ack[0,1] -> [2,1] Request Confirm/Hello/Up/t1[0,1] -> [0,1] Request Refuse[0,*] -> [1,*] Start Request/t1[1,1] -> [2,1] Request Confirm/Hello/Up/t1[1,2] -> [2,2] Confirm Hello/Up/t1[1,3] -> [2,3] Confirm Hello/Up/t1[1,0] -> [0,0] Refuse Null[1,*] -> [1,*] Start Request/r1[1,*] -> [0,*] Stop Null[1,*] -> [1,*] t1 Request/t1[2,1] -> [3,1] Up Down/Hello/Poll/t1/t2[2,1] -> [2,1] Request Confirm/Hello/Up/t1[2,2] -> [2,2] Hello I-H-U[2,3] -> [2,3] Hello I-H-U[2,2] -> [2,2] I-H-U ProcessExterior Gateway Protocol Formal Specification Page 29D.L. Mills[2,3] -> [2,3] I-H-U Process[2,*] -> [1,*] Start Request/r1[2,*] -> [4,*] Stop Cease/t1[2,1] -> [2,1] t1 Hello/t1[2,2] -> [2,2] t1 Hello/t1[2,3] -> [2,3] t1 Hello/t1[3,1] -> [2,1] Down Null[3,2] -> [2,2] Down Null[3,3] -> [2,3] Down Null[3,1] -> [2,1] Request Confirm/Hello/Up/t1[3,2] -> [3,2] Hello I-H-U[3,3] -> [3,3] Hello I-H-U[3,2] -> [3,2] I-H-U Process[3,3] -> [3,3] I-H-U Process[3,3] -> [3,3] Poll Update[3,3] -> [3,3] Update Process[3,*] -> [1,*] Start Request/r1[3,*] -> [4,*] Stop Cease/t1[3,1] -> [3,1] t1 Hello/t1[3,2] -> [3,2] t1 Hello/t1[3,3] -> [3,3] t1 Hello/t1[3,1] -> [3,1] t2 Poll/t2[3,2] -> [3,2] t2 Poll/t2[3,3] -> [3,3] t2 Poll/t2
[4,1] -> [4,1] Request Cease[4,*] -> [0,*] Cease Cease-ack[4,0] -> [0,0] Cease-ack Null[4,*] -> [0,*] Stop Null[4,*] -> [4,*] t1 Cease/t1 In the state-machine model defined in this document all states ofthe above machine are reachable; however, some are reachable only inextreme cases when one neighbor crashes, for example. In the commoncase where only one of the neighbors initiates and terminates theprotocol and neither one crashes, for example, not all states arereachable. Following is a matrix showing the states which can bereached in this case, where the neighbor that initiates and terminatesthe protocol is called the active gateway and the other the passivegateway.Exterior Gateway Protocol Formal Specification Page 30D.L. Mills Passive GatewayActive 0 Idle 1 Aqsn 2 Down 3 Up 4 CeaseGateway +-----------+-----------+-----------+-----------+-----------+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 cannotpersist for long, due to retransmission of Request and Hello messages,for example.
新闻热点
疑难解答
