RFC 904
Exterior Gateway Protocol formal specification
Network Working Group 🎀 Request for Comments: 904
Author: D.L. Mills
Date: April 1984
Category: standard for the DARPA community ✨
Updates: RFCs 827 and 888
Exterior Gateway Protocol Formal Specification 🦋
0. Status of this Memo 🌸
okay bestie, first things first 💅 this RFC is the official spec for the Exterior Gateway Protocol (EGP). It updates RFCs 827 and 888 and specifies a standard for the DARPA community. so if gateways from different autonomous systems in the ARPA-Internet are talking to each other, they really must follow this protocol 🫶
1. Introduction ✨
so EGP is the protocol gateways use to swap net-reachability information with each other, whether they're in the same autonomous system or different ones 🌈 this doc is a formal spec, so it's meant to be your reference for implementing, testing, and verifying. it also includes suggested algorithmic parameters that work across a wide range of setups, including the ARPANET and a bunch of local-network technologies that are now part of the Internet system 💖
the vibe check: we are NOT talking about the background, applications, or limitations of EGP here. that's been covered elsewhere (RFC-827, RFC-888) 🙈
also, EGP is expected to evolve. it's going to include topologies that aren't limited to tree-structures and get full routing capabilities. when that happens, this spec will be amended or obsoleted accordingly 🧚 BUT the basic protocol mechanisms in here are expected to stay pretty much the same. the only thing that should change is the format and interpretation of the Update message (more on that below) 🍓
here's the roadmap 🗺️ Section 2 covers the nomenclature, Section 3 covers the state-machine model (events, actions, parameters, and state transitions), and Section 4 is the functional description of how the machine operates, with the specific procedures and algorithms. Appendix A describes the EGP message formats. Appendix B is a summary of the minor differences between those and the formats in RFC-888. Appendix C is the reachability analysis, including a table of composite state transitions for two communicating EGP gateways 💜
1.1. Summary and Overview 🦋
EGP exists to convey net-reachability information between neighboring gateways, which may be in different autonomous systems. the protocol has mechanisms to acquire neighbors, monitor neighbor reachability, and exchange net-reachability information in the form of Update messages. it runs on periodic polling: Hello/I-Heard-You (I-H-U) message exchanges keep tabs on neighbor reachability, and Poll commands go out to solicit Update responses ✨
EGP is specified using a formal model: a finite-state automaton with defined events, state transitions, and actions. here's a simplified diagram of the machine (check out Section 3.4 for the full 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 |<---+--------+-----------------+
| |
+-------+here's the quick tour of what the gateway does in each state 👑
Idle State (0)
in Idle, the gateway has no resources (table space) assigned to the neighbor, and no protocol activity is happening at all 😴 it only responds to a Request command or a Start event (triggered by the system or an operator), and it ignores every other command and response. the gateway may optionally return a Cease-ack response to a Cease command in this state 🙈
when a Request comes in, the gateway sets up its state variables (see Section 3.1), sends a Confirm response, and moves to Down, as long as resource commitments allow it. if they don't, it sends a Refuse response and stays in Idle. when a Start event comes in, it sends a Request command and moves to the Acquisition state 🌸
Acquisition State (1)
in Acquisition, the gateway keeps retransmitting Request commands on a schedule. when it gets a Confirm response, it initializes the state variables and moves to Down. when it gets a Refuse response, it goes back to Idle. no other commands or responses get sent in this state, because not all of the state variables are initialized yet 💅
Down State (2)
the Down state means the gateway got a Request command, or a Confirm came back for a Request it already sent. the neighbor-reachability protocol has decided the neighbor is down 📉 in this state the gateway handles Request, Cease, and Hello commands and responds as needed. it retransmits Hello commands periodically if that's enabled. it doesn't process Poll commands and doesn't send them, but it may optionally process an unsolicited Update indication 🧚
Up State (3)
in Up, the neighbor-reachability protocol has declared the neighbor up 🌈 the gateway processes and responds to every command here. it periodically retransmits Hello commands (if enabled) and Poll commands too 💖
Cease State (4)
a Stop event sends a Cease command and moves the gateway into Cease 🛑 in this state the gateway keeps retransmitting the Cease command, and it goes back to Idle once it gets a Cease-ack response or another Stop event. the transitions are designed so the neighbor very likely receives the Cease command and stops the protocol 🫶
the rest of this document describes a state machine that can serve as an implementation model. implementers might deviate from this model and still conform to the protocol spec, but when you're verifying conformance, the state-machine model is the reference 🔍
one last thing, even though it's not spelled out elsewhere in this doc: all Internet gateways must include support for the Internet Control Message Protocol (ICMP), specifically ICMP Redirect and ICMP Destination Unreachable messages 🎀
2. Nomenclature 💜
here are the EGP message types recognized in this document. you'll find the format of each one in Appendix A 🍓
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 errorEGP messages come in three flavors: commands (they request some action), responses (they report the status of that action), and indications (similar to responses, but they can be sent at any time) 🦋 here's each command with its possible responses ✨
Command Corresponding Responses
---------------------------------------
Request Confirm, Refuse, Error
Cease Cease-ack, Error
Hello I-H-U, Error
Poll Update, ErrorUpdate and Error messages are both responses and indications. when one is sent in reply to an earlier command, it counts as a response. sometimes an unsolicited Update can be sent, and then it counts as an indication. using Error for anything other than a response to a previous command is a topic for further study 👀
3. State Machine 🔥
this section lays out the state-machine model for EGP: the variables and constants that define the state at any given time, the events that trigger transitions, the actions that result from those transitions, and the state-transition table that defines the behavior 💅
3.1. State Variables 🌸
the state-machine model has a bunch of state variables that define the protocol state between the gateway and each of its neighbors 🧚 so a gateway talking EGP with several neighbors has to keep a separate set of these variables for each one. the current state, events, and actions of the state machine apply to each neighbor on its own 💖
the model assumes system resources (including the set of state variables) are allocated when the state machine leaves Idle. that happens either when a Request arrives specifying a new neighbor address, or when a Start event specifies a new neighbor address. when either one happens, the state variables get initialized as described below. when the machine returns to Idle, all the resources (including the state variables) are deallocated and handed back to the system. of course, implementers may elect to dedicate resources and state variables permanently 🍓
these are the state variables that determine the model's transitions. all of them except the send sequence number S get their initial values 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)there may be additional state variables for timers and other internal housekeeping. Section 4 covers how those cited variables work and get managed 🎀
3.2. Fixed Parameters 💖
this section defines a few fixed parameters that characterize the gateway functions. each one comes with a suggested value based on experimental implementations in the Internet system 🧁 but those values may or may not be right for your particular configuration, so keep that in mind ✨
Next up, the list of time-interval parameters that control
Implementors may, of course, elect to dedicate resources and state variables permanently, and to 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, and the initial value for S is arbitrary 🎀. 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 ✨
These are the fixed parameters the gateway uses for retransmissions and other time-dependent 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 🙈.
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 statesParameters P4 and P5 are used only if the abort-timer option is implemented. P4 establishes how long the machine will remain in the Down and Up states in the absence of commands or responses, and would ordinarily be set to sustain state information while the neighbor is dumped and restarted, for example. P5 establishes how long the machine will remain in the Acquisition or Cease states in the absence of responses, and would ordinarily be set in the same order as the 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 thresholdThe j and k parameters establish the "noise immunity" of the neighbor-reachability protocol described later 🛡️. The values in the Active 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 in the model 🦋.
Name 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-reachability indication 🔥, which occurs when:
- The gateway is operating in the active mode (hello polling enabled) and either a Confirm, I-H-U or Update response is received.
- The gateway is operating in the passive mode (hello polling disabled) and either a Hello or Poll command is received with the
Up statecode in the Status field.
3.4. State Transition Table 📊
The following table summarizes the state transitions that can occur in response to the events listed above 💖. Transitions are shown in the form n/a, where n is the next state and a represents the action.
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-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 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 the state machine and the actions evoked 🧁.
Next Message
Event 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 and
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 reachability
indication.
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-U
I-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 reachability
indication.
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-U
I-H-U 3 Process neighbor-reachability
info.
Poll 3 Update
Update 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.
t1 3 Hello Reset timer t1 to T1 seconds.
t2 3 Poll Reset timer t2 to T2 seconds.
Cease State (4)
Request 4 Cease
Cease 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 is the deep dive 🤓, with detailed descriptions of the various procedures and algorithms used to manage the protocol 💅.
4.1. Managing the State Variables 🧠
The state variables which characterize the protocol are summarized in Section 3.1. This section describes the detailed management of these variables, including sequence numbers, polling intervals and timers ⏰.
4.1.1. Sequence Numbers 🔢
All EGP commands and replies carry a sequence number. The state variable R records the last sequence number received in a command from that neighbor. The current value of R is used as the sequence number for all replies and indications sent to the neighbor until a command with a different sequence number is received from that neighbor 💌.
Implementors are free to manage the sequence numbers of the commands sent 🙌. However, it is suggested that a separate send state variable S be maintained for each EGP neighbor, and that its value be incremented just before the time a Poll command is sent and at no other times 🎯. The actions upon receipt of a response or indication with sequence number not equal to S are 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 intervals are established, including T1, which establishes the interval between Hello command retransmissions, and T2, which establishes the interval between Poll retransmissions 🔁.
Each gateway configuration is characterized by a set of fixed parameters, including P1, which specifies the minimum polling interval at which it will respond to Hello commands, and P2, which specifies the minimum polling interval at which it will respond to Poll commands. P1 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 the S1 and S2 fields in the message to calculate its own T1 and T2 state variables, respectively. Implementors are free to perform this calculation in arbitrary ways 🎨. Here's the thing though, bestie: the following constraints must be observed:
- Okay so, if
T1<S1, the neighbor may discard Hello commands 🙈 And ifT2<S2, it may discard Poll commands. Totally picky, but valid 💅 - T3, the window where neighbor-reachability indications get counted, depends on T1 🌸 If two neighbors pick super different T3 values, the neighbor-reachability algorithm may not work properly 😭 You can dodge that drama if T1 > max(P1, S1) ✨
- If S1 or S2 (or both) are unacceptable for some reason, like they go past 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. That's been found appropriate in the experimental implementations 🦋 Implementors may choose to make T3 a fixed parameter in cases where the path between the neighbors has well-known characteristics 🧚
Note that if a gateway tries to send Hello commands near the rate max(P1, S1), or Poll commands near the rate max(P2, S2), the neighbor may see those arrivals bunch up and seem to break the polling restrictions because of bunching in the net. For this reason the gateway should send at rates somewhat below these. Just how far below depends on many factors that are beyond the scope of this specification 🫶
4.1.3. Hello Polling Mode 🎀
The neighbor-reachability algorithm can be used in either the active or passive mode. In active mode, Hello commands are sent periodically along with Poll commands, and reachability is determined by the corresponding I-H-U and Update responses. In passive mode, Hello commands are not sent and I-H-U responses are not expected. Instead, reachability is determined from the Status field of received Hello 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 the protocol must operate in active mode. However, the neighbor-reachability protocol is designed to work even if both neighbors operate in active mode 🤝 The value of M is determined from the Status field of a Request command or Confirm response. The sender sets this field according to whether its implementation supports active mode, passive mode, or both:
Status Sender capabilities
--------------------------------
0 either active or passive
1 active only
2 passive onlyThe receiver inspects this field and sets the value of M according to 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 the autonomous system numbers of the neighbors. The neighbor with the smallest such number assumes active mode, while the other neighbor assumes passive mode. In the case of "**", the neighbor may either send a Refuse response or declare a Stop event, depending on state 🌈
4.1.4. Timers ⏰
There are three timers defined in the state machine. t1 is used to control retransmission of Request, Hello, and Cease messages. t2 is used to control retransmission of Poll commands. t3 serves as an abort-timer mechanism in case the protocol hangs indefinitely 😱 The timers are set to specified values upon entry to each state and count down to zero.
For t1 and t2, state-dependent events are declared when the timer counts down to zero. After that, the timer is reset to its specified value and counts down again. For t3, a Stop event is declared when the timer counts down to zero. Implementors may choose not to implement t3. If they do skip it, or only implement it in certain states, then Request, Hello, and/or Cease commands may be retransmitted indefinitely 🔁
The following table shows the initial values for each of the timers in each state. A missing value means the timer is not used in that state. Note that timer t3 is set to P4 upon receipt of a neighbor-reachability indication when in either the Down or Up states 💖
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 environment of the gateway. They can be declared as the result of the gateway process being started and stopped by the operator, for example. A Start event only has meaning in some states. A Stop event has meaning in all states ✨
In all states except Idle, the abort timer t3 is presumed to be running. This timer is initialized to P5 seconds upon entry to any state, and to P4 seconds upon receipt of a neighbor-reachability indication in the Down and Up states. If it expires, a Stop event is declared. A Stop event can also be declared by an intrinsic system action, such as a resource problem or an operator command 😤
If the abort timer is not implemented, a manually initiated Stop event can be used to stop the protocol. If this is done in the Down or Up states, the machine will transition to the Cease state and emit a Cease command. If the neighbor does not respond to this command, the machine will stay in the Cease state indefinitely. However, a second Stop event can be used in this state to force a transition to the Idle state 🛑
A Cease command received in any state will cause the gateway to immediately send the Cease-ack response and transition to the Idle state. This stops the protocol and releases all system resources committed to the gateway process 🧹 The interval between the time the gateway enters the Idle state as the result of receiving a Cease command and the time it next sends a Request command to resume the protocol is not specified. However, it is recommended that this interval be at least P5 seconds 🕰️
It may happen that the Cease-ack response is lost in the network. That causes the neighbor to retransmit the Cease response indefinitely, at least if it has not implemented the abort-timer option 😭 To reduce the likelihood of this, it is suggested that a gateway in the Idle state be prepared to reply to a Cease command with a Cease-ack response whenever possible 🫶
4.3. Determining Neighbor Reachability 🔍
The purpose of the neighbor-reachability algorithm is to confirm that the neighbor can safely be considered operational and capable of providing reliable net-reachability information. An equally important purpose is to filter noisy reachability information before sending it on to the rest of the Internet gateway system, which avoids unnecessary reachability changes 🧠
As described above, a gateway operating in active mode sends periodic Hello commands and listens for I-H-U responses in order to determine neighbor-reachability indications. A gateway operating in passive mode determines reachability indications by means of the Status field in received Hello commands. Poll commands and Update responses 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 the gateway is in the Down and Up states, and it works like this. Define a moving window in time that starts at the present and extends backwards for t seconds. Then count the number n of neighbor-reachability indications that have occurred in that window. If n increases to j, declare an Up event. If n decreases to k, declare a Down event. The number n is set to zero upon entering the Down state from any state other than the Up state 🎢
The window t in this algorithm is defined as T3 seconds. The value of T3 is suggested to be four times T1, which itself is determined during the Request/Confirm exchange. For proper operation of the algorithm, only one neighbor-reachability indication is significant in any window of T1 seconds, and additional ones are ignored 🙅♀️ Note that the only way n can increase is as the result of a new neighbor-reachability indication. The only way it can decrease is as the result of an old neighbor-reachability indication moving out of the window.
The behavior of the algorithm, using the suggested fixed parameters j and k, differs depending on whether the gateway is operating in active or passive mode. In active mode (j = 3, k = 1 and T3/T1 = 4), once the neighbor has been declared down, it will be forced down for at least two T1 intervals. Once it has been declared up, it will be forced up for at least two T1 intervals as well. It will not change state unless at least three of the last four determinations of reachability have indicated that change 💅
In passive mode (j = 1, k = 4 and T3/T1 = 4), the neighbor will be considered up from the first time the Status field of a Hello or Poll command or Update response indicates "Up state". It stays up until four successive T1 intervals have passed without such an indication. This design was suggested by similar designs used in the ARPANET. It has proven effective in the experimental implementations, but it may need to be adjusted for other configurations 🌸
It is convenient for the active gateway to send Hello commands at a rate of one every T1 seconds, and to substitute a Poll command for a Hello command approximately once every T2 seconds. The neighbor-reachability indication is generated by the corresponding I-H-U or Update responses. Its passive neighbor generates neighbor-reachability indications from the Status field of received Hello and Poll commands and Update responses 💜
Implementors may find the following model useful in understanding and implementing this algorithm. Picture an n-bit shift register that shifts one bit to the right each T1-second interval. If a neighbor-reachability indication was received during the preceding T1-second interval, a one bit is shifted into the register at the end of the interval. Otherwise, a zero bit is shifted in. A table of 2**n entries, indexed by the contents of the register, can be used to calculate the number of one bits. That count can then be used to declare the appropriate event to the state machine. A value of n equal to four has been found useful in the experimental implementations 🧚♀️
4.4. Determining Network Reachability 🗺️
Network reachability information is encoded into Update messages in the form of lists of nets and gateways. The IP Source Address field of the Poll command is used to specify a network common to the autonomous systems of each of the neighbors. This is usually, but not necessarily, the network common to the neighbors themselves. The Update response includes a list of gateways on the common net. Associated with each gateway is a list of the networks reachable via that gateway, together with corresponding hop counts 🛰️
It is important to understand that, at the present state of development as described in RFC-827 and RFC-888, the EGP architectural model restricts the interpretation of "reachable" in this context. This consideration, as well as the implied topological restrictions, is beyond the scope of this discussion. The reader is referred to those RFCs for further discussion 📚
Two types of gateway lists can be included in the Update response. The format of these is described in Appendix A. Both lists include only
those gateways directly connected to the net named in the IP Source Network field of the last Poll command they got 💅 The internal list is the good stuff: it has some or all of the gateways in the same autonomous system as the sender, plus the nets reachable through them, and the sending gateway goes first ✨ A net counts as reachable here if there's a path to it that only uses gateways inside the system. The external list has gateways from other autonomous systems that the sender knows about 🌍 Big reminder: hop counts are NOT a routing metric 🙅♀️ They can only be compared between gateways if those gateways are in the same autonomous system, aka they're both in the internal list.
Okay so, under the current system architectural model, only gateways that belong to a designated system called the core system are allowed to put the external list in their Update responses 👑 Everyone else can only include gateways from their own system, and they can only claim a net is reachable if that net is reachable inside the same system. Iconic restraint 💅
The interval between successive Poll commands, T2, gets set during the Request/Confirm exchange 🦋 The spec allows at most one unsolicited Update indication between two Poll commands from the neighbor, though. The model wants an Update indication to go out (a) when you first enter the Up state and (b) when the reachability database changes, but still respecting that one-per-interval limit 🫶
Sometimes a Poll command or an Update response just gets lost in the network 😭 That means the net-reachability info might not show up until the next T2 interval. As an implementation option, a gateway that sent a Poll and hasn't gotten an Update response after T1 seconds can send another Poll. The gateway that receives this second Poll can (a) send an Update response if it never got the original Poll for that interval, (b) send a second Update response (which counts as the unsolicited Update indication from the paragraph above), or (c) send an Error response or just not respond in any other case 🎀
4.5. Error Messages ✨
Error messages are how you report problems like the ones described in Appendix A, under the Error Response/Indication message format 🚨 Generally, an Error message gets sent when a gateway receives another command or response that has bad format, bad content, or bad ordering. But an Error message is NEVER sent in response to another Error message 🙅♀️ Receiving an Error message should be considered advisory, so it shouldn't change your state, unless it maybe evokes a Stop event 🫠
Appendix A. EGP Message Formats 🧚
Here's where we get into the actual message formats 🎀 Every EGP message starts with a ten-octet header made of six fields, and depending on the message type, more fields can follow it. The header layout is below, along with what each field means 💖
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 type
Code identifies the message code (subtype)
Status contains message-dependent status information
Checksum 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 system
Sequence # send state variable (commands) or receive state
variable (responses and indications)The checksum is the fun one 🧮 It's the 16-bit one's complement of the one's complement sum of the EGP message, starting from the EGP version number field. When you compute it, the checksum field itself should be zero. Sequence # is a send state variable for commands, and a receive state variable for responses and indications 🦋
Following is a description of each of the message formats. The above description applies to all of them, so it won't get repeated 💅
A.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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Heads up 🙈 the Hello Interval and Poll Interval fields only show up in Request and Confirm messages. Here are the Type, Code, and Status values, plus the field definitions:
Note: the Hello Interval and Poll Interval fields are present only in
Request and Confirm messages.
Type 3
Code 0 Request command
1 Confirm response
2 Refuse response
3 Cease command
4 Cease-ack response
Status (see below) 0 unspecified
1 active mode
2 passive mode
3 insufficient resources
4 administratively prohibited
5 going down
6 parameter problem
7 protocol violation
Hello Interval minimum Hello command polling interval (seconds)
Poll Interval minumum Poll command polling interval (seconds)Here's the summary of the assigned Status codes, with the scenarios where each one might get used 📋
Code Status Scenarios
-------------------------------------------------------------------
0 unspecified when nothing else fits
1 active mode Request/Confirm only
2 passive mode Request/Confirm only
3 insufficient resources 1. out of table space
2. out of system resources
4 administratively 1. unknown Autonomous System
prohibited 2. use another gateway
5 going down 1. operator initiated Stop
2. abort timeout
6 parameter problem 1. nonsense polling parameters
2. unable to assume compatible mode
7 protocol violation 1. Invalid command or response
received in this stateA.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 5
Code 0 Hello command
1 I-H-U response
Status 0 indeterminate
1 Up state
2 Down stateA.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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+The Poll command is the one that asks for reachability info about a specific network 🔍 Here are its field values:
Type 2
Code 0
Status 0 indeterminate
1 Up state
2 Down state
IP 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)A.4. Update Response/Indication ✨
okay bestie, the Update is where gateways actually trade reachability info 📬 here's the layout, and it's giving packed 💅
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)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
...The field values are where the Update gets its personality 🎀
Type 1
Code 0
Status 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
message
IP 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 block
Distances numbers depending on autonomous system
architecture
# of Nets number of nets at each distance
Nets IP network number reachable via the gatewayA.5. Error Response/Indication 💀
Now the Error. Same vibe as the Update, but this one is basically the gateway saying "something's not right, here's why" 🙈
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) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Here are the values, bestie 🌸
Type 8
Code 0
Status 0 indeterminate
1 Up state
2 Down state
128 unsolicited message bit
Reason (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 response
Error Message Header first three 32-bit words of EGP headerOkay, so the Reason field is the real tea ☕ Here's the full rundown of the Reason codes and when each one might show up 🔍
Code Reason Scenarios
------------------------------------------------------------------------
0 unspecified when nothing else fits
1 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) intervalAppendix B. Comparison with RFC-888 📚
Okay so this appendix is the glow-up story 🦋 Minor functional upgrades were needed in the RFC-888 message formats so the state-machine model could do its thing, mainly the ability to ask a neighbor to stop sending Hello commands 🤫 The model also suggests a mapping between its states and certain status and error indications, which clarifies and generalizes how those get interpreted ✨
Here's the status-field glow-up at a glance 💖
Class Messages Status Codes
-------------------------------------------------------------------
3,0 Request 0 unspecified
3,1 Confirm 1 active mode
3,2 Refuse 2 passive mode
3,3 Cease 3 insufficient resources
3,4 Cease-ack 4 administratively prohibited
5 going down
6 parameter problem
5,0 Hello 0 indeterminate
5,1 I-H-U 1 Up state
2,0 Poll 2 Down state
1,0 Update 128 unsolicited message bit
8,0 ErrorEvery header field stays the same except the Status field, which RFC-888 sometimes called the Information field 🎀 Here's what changed, bestie 👑
- The status codes got grouped into two classes. One is for the messages that start and stop the protocol, and the other is for the messages that keep it running and swap reachability info 🔄 Some messages in either class may not use every status code assigned to it.
- The Request and Confirm status codes show whether the sender can run in active or passive mode 🙌 In RFC-888 this field must be zero. RFC-888 also doesn't say how neighbors decide who polls whom, so that's a gap this fixes 💡
- Cease, Refuse and Cease-ack now mean the same thing 🚦 That gives a clear, no-confusion signal when the protocol shuts down because of something unusual, like the NOC dynamically repartitioning the ARPANET 😱 The codes don't line up with RFC-888, since Refuse and Cease had conflicting values there. The differences are minor, though, and should cause no significant problems 🫶
- Hello, I-H-U, Poll, Update and Error now share the same interpretation for their codes 🧚 Codes 0 through 2 are mutually exclusive and are picked only based on the sender's state. For the Update (and possibly the Error), one of those codes can be combined with the "unsolicited bit," which is code 128. In RFC-888, this field is unused for the Poll and Error, and for the Update it may contain only zero or 128. So by default, reciprocal reachability cannot be determined by these messages 🌈
- A few of the reachability codes from RFC-888 got removed since they didn't apply anymore 🗑️
Appendix C. Reachability Analysis 🧠
Okay, this is the big brain section 🧠💜 The table below shows the state transitions that can happen in a system of two neighboring EGP gateways. It's super useful for designing and verifying the protocol, and also for implementation and testing, so you're gonna want to keep it close 🔥
To model it, the two-neighbor system is treated as a finite-state automaton, built as the cartesian product of two state machines as defined above. It's giving math-but-make-it-fun ✨ Each state of this machine is represented as
[i,j], where i and j are states of the original machine. Each line of the table is one state transition, written as [i1,j1] -> [i2,j2] E A, which means: the machine in state [i1,j1] gets event E, moves to state [i2,j2], and does action A. Multiple actions are split with "/", and a "" stands for a whole group of lines where every "" in that line takes the same value, cycling through 0 - 4 in turn 💖
Here's the table, bestie. It only shows transitions that can happen when events come in from one of the two neighbors 🦋
State 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 Process
[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/t1The full table also has a duplicate set of lines for the other neighbor. Each of those comes from a line above using this flip: [i1,j1] -> [i2,j2] E A => [j1,i1] -> [j2,i2] E A 🔥
Now, here's the tea ☕. In this machine every state is reachable, which is wild, but some states only show up in extreme cases, like when one neighbor crashes 💀. In the common situation, where only one neighbor starts and stops the protocol and nobody crashes, not all states are reachable 🌸. We call the neighbor that starts and stops it the active gateway and the other one the passive gateway. The matrix below shows which states can be hit in that common case ✨
Passive Gateway
Active 0 Idle 1 Aqsn 2 Down 3 Up 4 Cease
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 that matrix, blank entries are states that can't be reached 🙈, and the ones marked unstable are transient states that can't stick around for long 😭. The retransmission of Request and Hello messages is one reason they don't last, periodt 🫶
📦 where this page comes from
- ietf: rfc904 1984-04
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms