RFC 911
EGP Gateway under Berkeley UNIX 4.2
Title Block 🎀
RFC 911: EGP GATEWAY UNDER BERKELEY UNIX 4.2 💖
This one's from the Network Working Group, and it's numbered Request for Comments: 911. The author is Paul Kirton from the University of Southern California, Information Sciences Institute, where he was a Visiting Research Fellow from Telecom Australia Research Laboratories. It's dated 22 August 1984. The title block doesn't list anything it obsoletes or updates, so it's standing on its own 🦋
ABSTRACT ✨
This report describes an implementation of the Exterior Gateway Protocol running under the Unix 4.2 BSD operating system. It also talks through some issues tied to local network configurations. 🌸
Status of this Memo:
Okay, so this memo describes an implementation of the Exterior Gateway Protocol (EGP), which means it's basically a status report 📋 It also digs into some possible extensions and design issues, so it's an invitation for further discussion too 💬 Distribution of this memo is unlimited ✨
Funding for this research was provided by DARPA and Telecom Australia. 💜
Table of Contents
1. INTRODUCTION 1
1.1 Motivation for Development 1
1.2 Overview of EGP 2
2. GATEWAY DESIGN 4
2.1 Routing Tables 4
2.1.1 Incoming Updates 5
2.1.2 Outgoing Updates 5
2.2 Neighbor Acquisition 6
2.3 Hello and Poll Intervals 6
2.4 Neighbor Cease 7
2.5 Neighbor Reachability 7
2.6 Sequence Numbers 8
2.7 Treatment of Excess Commands 8
2.8 Inappropriate Messages 8
2.9 Default Gateway 9
3. TESTING 10
4. FUTURE ENHANCEMENTS 11
4.1 Multiple Autonomous Systems 11
4.2 Interface Monitoring 11
4.3 Network Level Status Information 11
4.4 Interior Gateway Protocol Interface 12
5. TOPOLOGY ISSUES 13
5.1 Topology Restrictions and Routing Loops 13
5.1.1 Background 13
5.1.2 Current Policy 14
5.2 Present ISI Configuration 15
5.2.1 EGP Across ARPANET 17
5.2.2 EGP Across ISI-NET 17
5.2.3 Potential Routing Loop 18
5.3 Possible Future Configuration 18
5.3.1 Gateway to UCI-ICS 18
5.3.2 Dynamic Switch to Backup Gateway 19
5.3.2.1 Usual Operation 19
5.3.2.2 Host Initialization 19
5.3.2.3 When Both the Primary and Backup are Down 20
5.3.2.4 Unix 4.2 BSD 20
6. ACKNOWLEDGEMENT 21
7. REFERENCES 221. INTRODUCTION 🦋
The Exterior Gateway Protocol (EGP) [Rosen 82; Seamonson & Rosen 84; Mills 84a] was specified so different gateway systems could develop autonomously while global distribution of internet routing information still gets maintained 🌍 EGP gives different autonomous gateway systems a way to swap info about the networks reachable through them, which is so iconic ✨
This report mainly describes an implementation of EGP that runs as a user process under the Berkeley Unix 4.2 operating system, running on a VAX* computer 💻 It also discusses some related issues about local autonomous system configurations.
The EGP implementation is experimental and is not part of Unix 4.2 BSD 🧪 It's anticipated that Berkeley will incorporate a version of EGP in the future 👀
The program is written in C 💖 The EGP part is based on the C-Gateway code written by Liza Martin at MIT, and the route management part is based on the Unix 4.2 BSD route management daemon, "routed" 🎀
The EGP functions are consistent with the specification of [Mills 84a] except where noted 📚
A knowledge of EGP as described in [Seamonson & Rosen 84; Mills 84a] is assumed, so come in knowing your stuff 💅
This chapter discusses the motivation for the project. Chapter 2 describes the gateway design, Chapter 3 is about testing, Chapter 4 suggests some enhancements, and Chapter 5 discusses topology issues 🌈
More info about running the EGP program and describing the software is being published in an ISI Research Report, ISI/RR-84-145 [Kirton 84] 📝
Requests for documentation and copies of the EGP program should be sent to Joyce Reynolds (JKReynolds@USC-ISIF.ARPA). Software support is not provided 🫶
* Unix is a trade mark of AT&T ** VAX is a trade mark of Digital Equipment Corporation
Hmm, wait, I put the VAX marker on the wrong word in that last paragraph; the original marks both Unix and VAX, so here's the corrected pairing: Unix* and VAX** ✨
1.1 Motivation for Development 🌸
With EGP arriving, the internet gateways get split into a "core" autonomous system (AS) of gateways run by Bolt, Beranek and Newman (BBN), plus lots of "stub" ASes run by different organizations. Each stub AS shares at least one network with a core AS gateway 🍓 The core AS acts as a hub for passing routing info between different stub ASes, so stub ASes only need to run EGP with a core gateway. Further detail is in [Rosen 82] 💜
At the time of this project there were 28 "non-routing" gateways in the internet. Non-routing gateways didn't exchange routing info. They needed static entries in the core gateway routing tables instead 😭 Since August 1, 1984, those static entries have been eliminated, and previously non-routing gateways are required to tell the core gateways this info dynamically via EGP [Postel 84] 🔥
At the USC Information Sciences Institute (ISI) there was a non-routing gateway to the University of California at Irvine network (UCI-ICS). With non-routing gateways removed from the core gateway tables, the core ISI gateway needs to be told about the route to UCI-ICS using EGP 🧚
Also, we'd love a backup gateway between ISI-NET and the ARPANET, in case the core ISI gateway goes down 🙈 That kind of gateway would need to convey routing info via EGP too. Details of the ISI network configuration are in Section 5.2 👑
Of the 28 non-routing gateways, 23 were implemented on Unix systems, including ISI's. ISI's proposed backup gateway was also a Unix system 💅 So there was a local and general need for an EGP implementation that runs under Unix. The current version of Unix that included Department of Defense (DoD) protocols was Berkeley Unix 4.2, so that's what got picked ✨
1.2 Overview of EGP 🦋
This report assumes you already know EGP, but a brief overview is included here for completeness 🎀 For more details, check out [Rosen 82] for the background to EGP, [Seamonson & Rosen 84] for an informal description, and [Mills 84a] for a more formal specification and implementation details 📖
EGP is generally run between gateways in different ASes that share a common network. In other words, they're neighbor gateways 🫶
EGP consists of three procedures: neighbor acquisition, neighbor reachability, and network reachability 💖
Neighbor acquisition is a two-way handshake in which gateways agree to run EGP by exchanging Request and Confirm messages, which include the minimum Hello and Poll intervals 🤝 Acquisition ends when gateways exchange Cease and Cease-ack messages 👋
Neighbor reachability is a periodic exchange of Hello commands and I-H-U (I heard you) responses, which makes sure each gateway is up 🌈 Right now a 30 second minimum interval is used across ARPANET ⏱️ Only one gateway needs to send commands, because the other can use them to figure out reachability. A gateway that sends reachability commands is said to be in the active mode, while a gateway that just responds is in the passive mode 🎀
Network reachability is determined by periodically sending Poll commands and receiving Update responses, which indicate the networks reachable via one or more gateways on the shared network. Right now a 2 minute minimum interval is used across ARPANET 🧁
2. GATEWAY DESIGN 🌷
Okay, so EGP is a polling protocol with loose timing constraints 😌 That means the only gateway function that really needs good performance is packet forwarding. Unix 4.2 already has packet forwarding built into the kernel, which is where the best performance can be achieved 🚀 When this was written, Unix 4.2 didn't send ICMP (Internet Control Message Protocol) redirect messages for misrouted packets. That's a requirement of internet gateways, and Berkeley will add it later 🙄
The EGP and route update functions are implemented as a user process. This makes development and distribution way easier, since only minor changes need to be made to the Unix kernel 💅 It's a similar approach to the Unix route distribution program "routed" [Berkeley 83], which is based on the Xerox NS Routing Information Protocol [Xerox 81]. Main character energy 👑
2.1 Routing Tables 🗺️
A route is made up of a destination network number, the address of the next gateway to use on a directly connected network, and a metric that gives the distance in gateway hops to the destination network 🦋
There are two sets of routing tables: the kernel tables (used for packet forwarding) and the EGP process tables. The kernel has separate tables for host and network destinations. The EGP process only maintains the network routing tables 🌸 The EGP tables get updated when EGP Update messages are received. When a route changes, the kernel network tables are updated via the SIOCADDRT and SIOCDELRT ioctl system calls. At initialization, the kernel network routing tables are read through the kernel memory image file, /dev/kmem, and copied into the EGP tables for consistency 🧠
This EGP implementation is designed to run on a gateway that's also a host. Because the polling for route updates is relatively slow, the host might hear about routing changes through ICMP redirects before the EGP process gets notified via EGP 😭 Redirects update the kernel tables directly. The EGP process listens for redirect messages on a raw socket and updates its routing tables to keep them consistent with the kernel 🫶
The EGP process routing tables are kept as two separate tables: one for exterior routes (via different AS gateways) and one for interior routes (via the gateways of this AS) 💜 The exterior routing table is updated by EGP Update messages. The interior routing table is currently static and is set at
initialization time. It includes all directly attached nets, found through the SIOCGIFCONF ioctl system call, plus any interior non-routing gateways read from the EGP initialization file, EGPINITFILE. The interior routing table could in future be updated dynamically by an Interior Gateway Protocol (IGP) 🌸
Keeping separate tables for exterior and interior routing is lowkey genius, bestie 🧠 It makes it easier to prepare outgoing Update messages that only contain interior routing information [Mills 84b]. It also lets alternative external routes sit next to the internal routes as a backup in case an interior route fails. Alternate routes get flagged with RTS_NOTINSTALL, which means the kernel routes should not be updated. In the current implementation, alternate routes are not used 💤
2.1.1 Incoming Updates 📥
EGP Updates are used to update the exterior routing table if one of the following is satisfied:
- No routing table entry exists for the destination network and the metric indicates the route is reachable (
< 255). - The advised gateway is the same as the current route.
- The advised distance metric is less than the current metric.
- The current route is older (plus a margin) than the maximum poll interval for all acquired EGP neighbors. That is, the route was omitted from the last Update.
If any exterior route entry, except the default route, is not updated by EGP within 4 minutes or 3 times the maximum poll interval, whichever is the greater, it is deleted. Gone, no notes 🗑️
If there is more than one acquired EGP neighbor, the Update messages received from each are treated the same way, in the order they are received 💅
In the worst case, when a route changes to a longer route and the old route is not first notified as unreachable, it could take two poll intervals to update a route. With the current poll interval, this could be 4 minutes. Under Unix 4.2 BSD, TCP connections (Transmission Control Protocol) are closed automatically after they are idle for 6 minutes. So this worst case will not result in the automatic closure of TCP connections 🙈 Phew, no drama!
2.1.2 Outgoing Updates 📤
Outgoing Updates include the direct and static networks from the interior routing table, except for the network shared with the EGP neighbor.
The networks that are allowed to be advised in Updates may be specified at initialization in EGPINITFILE. This lets particular routes be excluded from exterior updates in cases where routing loops could be a problem. Another case where this option is necessary is when there is a non-routing gateway belonging to a different AS which has not implemented EGP yet. Its routes may need to be included in the kernel routing table, but they are not allowed to be advised in outgoing updates 🚫
If the interior routing table includes other interior gateways on the network shared with the EGP neighbor, they are included in Updates as the appropriate first hop to their attached networks 🧚
The distance to networks is set as in the interior routing table, except if the route is marked down, in which case the distance is set to 255. At present, routes are only marked down if the outgoing interface is down. The state of all interfaces is checked prior to preparing each outgoing Update, using the SIOCGIFFLAGS ioctl system call 🔍
Unsolicited Updates are not sent. No surprise texts, period 🤐
2.2 Neighbor Acquisition 🫶
EGPINITFILE lists the addresses of trusted EGP neighbor gateways, which are read at initialization. These will usually be core gateways, as only core gateways provide full internet routing information. At the time of writing, there were three core gateways on ARPANET that support EGP, CSS-GATEWAY, ISI-GATEWAY and PURDUE-CS-GW, and two on MILNET, BBN-MINET-A-GW and AERONET-GW 🌈
EGPINITFILE also includes the maximum number of these gateways that should be acquired at any one time. This is usually expected to be just one. If this gateway is declared down, another gateway on the list will then be acquired automatically, in sufficient time to make sure the current routes don't time out ⏰
The gateway will only accept acquisitions from neighbors on the trusted list, and it will not accept them if it has already acquired its maximum quota. This prevents Updates from being accepted from possibly unreliable sources 🛡️
The ability to acquire core gateways that are not on the trusted list but have been learned of indirectly via Update messages is not included, because not all core gateways run EGP 🤷♀️
New acquisition Requests are sent to neighbors in the order they appear in EGPINITFILE. No more new Requests than the maximum number of neighbors yet to be acquired are sent at once. Any outstanding Requests are retransmitted at 32 second intervals, up to 5 retransmissions each. At that point, the acquisition retransmission interval is increased to 4 minutes. Once the maximum number of neighbors has been acquired, unacquired neighbors with outstanding Requests are sent Ceases. This approach balances a fast response when neighbors don't initially respond against a desire to minimize the chance that a neighbor gets Ceased after it has sent a Confirm but before that Confirm has been received 🥹 If the specified maximum number of neighbors cannot be acquired, Requests are retransmitted indefinitely to all unacquired neighbors ♾️
2.3 Hello and Poll Intervals ⏱️
The Request and Confirm messages include minimum values for Hello and Poll intervals. The advised minimums by this gateway and the core gateways are currently 30 and 120 seconds respectively.
The received intervals are checked against upper bounds to guard against nonsense values. The upper bounds are currently set at 120 and 480 seconds respectively. If they are exceeded, the particular neighbor is considered bad and is not sent further Requests for one hour. This gives the other gateway time to fix the situation, and lets normal operation resume automatically from this gateway without an excess of unnecessary network traffic 😤➡️😌
The actual Hello and Poll intervals are chosen by first selecting the maximum of the intervals advised by this gateway and its peer. A 2 second margin is then added to the Hello interval to account for possible network delay variations, and the Poll interval is increased to the next integer ratio of the Hello interval. This results in 32 second Hello and 128 second Poll intervals 🧮✨
If an Update is not received in response to a Poll, at most one repoll (same sequence number) is sent instead of the next scheduled Hello 🔁
2.4 Neighbor Cease 👋
If the EGP process is sent a SIGTERM signal via the Kill command, all acquired neighbors are sent Cease(going down) commands. Ceases are retransmitted at the hello interval, at most 3 times. Once all of them have either responded with Cease-acks or been sent three retransmitted Ceases, the process is terminated. Bye bye, bestie 🫡
2.5 Neighbor Reachability 🔦
Only active reachability determination is implemented. It is done as recommended in [Mills 84a], with a minor variation noted below 🧐
A shift register of responses is maintained. For each Poll or Hello command sent, a zero is shifted into the shift register. If a response (I-H-U, Update or Error) is received with the correct sequence number, the zero is replaced by a one. Before each new command is sent, the reachability is determined by examining the last four entries of the shift register. If the neighbor is reachable and <= 1 response was received, the neighbor is considered unreachable. If the neighbor is considered unreachable and >= 3 responses were received, it is now considered reachable 📊
A neighbor is considered reachable immediately after acquisition, so that the first poll received from a core gateway (once it considers this gateway reachable) will be responded to with an Update. Polls are not sent unless a neighbor is considered reachable and it has not advised that it considers this gateway unreachable in its last Hello, I-H-U or Poll message. This prevents the first Poll from being discarded after a down/up transition, which matters because the Polls are used for reachability determination. Following acquisition, at least one message must be received before the first Poll is sent. This is to determine that the peer does not consider this gateway down. This usually requires at least one Hello to be sent before the first poll. This paragraph differs from [Mills 84a], which recommends that a peer be considered down following acquisition, and that Polls may be sent as soon as the peer is considered up. This is the only significant departure from the recommendations in [Mills 84a] 🫣
Polls received from peers that are considered unreachable are sent an Error response, which lets their reachability determination progress correctly. This action is an option within [Mills 84a] 💡
When a neighbor becomes unreachable, all routes using it as a gateway are deleted from the routing table. If there are known unacquired neighbors, the unreachable gateway is ceased and an attempt is made to acquire a new neighbor. If all known neighbors are acquired, reachability determination continues for 30 minutes ([Mills 84a] suggests 60 minutes). After that, the unreachable neighbor is ceased and reacquisition is attempted every 4 minutes. This is aimed at reducing unnecessary network traffic 🌿
If valid Update responses are not received for three successive polls, the neighbor is ceased and an alternative acquired, or reacquisition is attempted in 4 minutes. This provision exists in case erroneous Update data formats are being sent by the neighbor. This situation did occur on one occasion during testing 😱
2.6 Sequence Numbers 🔢
Sequence numbers are managed as recommended in [Mills 84a]. Single send and receive sequence numbers are maintained for each neighbor. The send sequence number is initialized to zero and is incremented before each new Poll (not repoll) is sent, and at no other time. The send sequence number is used in all commands. The receive sequence number is maintained by copying the sequence number of the last Request, Hello, or Poll command received from a neighbor. This sequence number is used in outgoing Updates. All responses (including Error responses) return the sequence number of the message just received 📬
2.7 Treatment of Excess Commands 🚨
If more than 20 commands are received from a neighbor in any 8 minute period, the neighbor is considered bad, Ceased, and reacquisition is prevented for one hour. Too much chatter, not it 🙅♀️
At most one repoll (same sequence number) received before the poll interval has expired (less a 4 second margin for network delay variability) is responded to with an Update. Others are sent an Error response. When an Update is sent in response to a repoll, the unsolicited bit is not set, which differs from the recommendation in [Mills 84a] 🎀
2.8 Inappropriate Messages 🙅♀️
If a Confirm, Hello, I-H-U, Poll or Update is received from any gateway (known or unknown) that is in the unacquired state, synchronization has probably been lost for some reason. A Cease(protocol violation) message is sent to try to reduce unnecessary network traffic. This action is an option in [Mills 84a] 🔧
2.9 Default Gateway 🛟
A default gateway may be specified in EGPINITFILE. The default route (net 0 in Unix 4.2 BSD) is used by the kernel packet forwarder if there is no specific route for the destination network. This provides a final level of backup if all known EGP neighbors are unreachable. This is especially useful if there is only one available EGP neighbor, as in the ISI case, Section 5.2.2 🦋
The default route gets installed at initialization 🌸, then deleted the moment a valid EGP Update message shows up 💅. It comes back (reinstalled) if every known neighbor is acquired but none of them are reachable 😭, if routes time out while there are no acquired and reachable EGP neighbors 💀, and right before process termination 🫶.
It gets deleted after a valid Update because the default gateway won't know any more routing info than EGP already taught us 🙈. If it stayed put, all traffic headed to unreachable nets would get sent to the default gateway under the Unix 4.2 forwarding strategy, and that's a whole mess, bestie 😭.
The default gateway should normally be set to a full-routing core gateway other than the known EGP neighbor gateways 👑. That gives you another backup in case all of the EGP gateways go down at the same time 🧚.
3. Testing 🎀
Here are a few spicy moments from testing, quickly summarised 🌶️.
Different implementers read the sequence number rules differently 🙃. So some implementations rejected messages for having "incorrect" sequence numbers, and the peer gateway got declared down 😱. The real problem was that the spec was only written in narrative form, and narrative is super prone to inconsistencies, ambiguities and incompleteness 📜. The more formal specification in [Mills 84a] cleared up those ambiguities ✅.
When they tested how the gateways responded to packets addressed to a neighbor gateway's interface that wasn't on the shared net, a loop happened 🔁. Both gateways kept trading error messages about an invalid interface, over and over 🙃. The cause was that both gateways sent Error responses after checking the addresses but before checking the EGP message type. The fix: don't send an Error response unless you're certain the message isn't itself an Error response 🫶.
One time a core gateway had some kind of data error in its Update messages 🤒. Those Updates got rejected even though reachability was going great, and all routes ended up timing out 💀. The solution was to count the number of successive Polls that don't result in valid Updates being received. If that number reaches 3, Cease EGP and attempt to acquire an alternative gateway 🦋.
Mike Karels at Berkeley reported another quirk 🧠, one that comes from having multiple gateways between MILNET and ARPANET. Each ARPANET host has an assigned gateway to use for MILNET access 🔌. When the EGP gateway is a host as well as a gateway, the EGP Update messages may point to a different MILNET/ARPANET gateway than the assigned one 🤹. When that host/gateway sends a packet routed via the EGP-reported gateway, it gets a redirect to its assigned gateway 🔀. So the MILNET gateway can keep getting switched between the gateway reported by EGP and the assigned gateway 🏓. A similar thing happens when using routes to other nets reached via MILNET/ARPANET gateways 🌈.
4. Future Enhancements 🚀
4.1 Multiple Autonomous Systems 🏰
Right now, acquiring a maximum number of EGP neighbors from a trusted list implies that all the neighbors are in the same AS 💅. The plan is for them all to be members of the core AS. When updating the routing tables, Updates are treated independently, with no distinction made as to whether the advised routes are internal or external to the peer's AS. Routing metrics are also compared without reference to the AS of the source 🙈.
If EGP is going to run with additional AS's beside the core AS, all neighbors on the list would need to be acquired so that gateways from both AS's are always acquired 😩. That leads to an unnecessary excess of EGP traffic if redundant neighbors are acquired for reliability 📈. A more desirable approach would be to have separate lists of trusted EGP gateways, plus the maximum number to acquire, for each AS 🧃. Routing entries would also need the source AS added, so that preference can be given to information received from the owning AS (see Section 5.1.2) 💜.
4.2 Interface Monitoring 🔌
At present, interface status only gets checked immediately before an Update is sent in response to a Poll 😴. It could be monitored more regularly, with an unsolicited Update sent when a change is detected 🚨. This is one area where the slow response of EGP polling could be improved 🐢. It's of particular interest to networks connected by dial-in lines 📞. When a network like that dials in, its associated interface is marked as up, but it can't receive packets until the change has been propagated by EGP 🥲. This is one case where the unsolicited Update message would help, but there's still a delay for other non-core gateways polling core EGP gateways for the new routing info 🕰️.
At first, people thought a kernel EGP implementation might help 💡. But the kernel doesn't presently pass interface status changes by interrupts, so a new facility would need to be built 🛠️. If that was done, it may be just as easy to provide a user level signal when an interface status changes 🙌.
4.3 Network Level Status Information 📡
At present, network level status reports, such as IMP Destination Unreachable messages, aren't used to detect changes in the reachability of EGP neighbors or other neighbor gateways 🙃. This information should be used to improve the response time to changes ⚡.
4.4 Interior Gateway Protocol Interface 🧩
Right now, any routing information interior to the AS is static and read from the initialization file 📂. The internal route management functions were written so it should be reasonably easy to interface an IGP for dynamic interior route updates 🧠. This is made possible by separating the exterior and interior routing tables 🫶.
The outgoing EGP Updates will be correctly prepared from the interior routing table by rt_NRnets(), whether or not static or dynamic interior routing is done ✨. Functions are also provided for looking up, adding, changing and deleting internal routes: rt_int_lookup(), rt_add(), rt_change() and rt_delete() respectively 🗂️.
Basically, an IGP interacts with the current data structures through three functions: updating the interior routing table using something similar to rt_NRupdate(), preparing outgoing interior updates similarly to rt_NRnets(), and timing out interior routes similarly to rt_time() ⏳.
5. Topology Issues 🕸️
5.1 Topology Restrictions and Routing Loops 🔁
5.1.1 Background 📚
EGP isn't a routing algorithm 🙅. It just lets exterior neighbors exchange routing information that a routing algorithm is likely to need. It doesn't pass enough information to prevent routing loops if cycles exist in the topology [Rosen 82] 🌀.
Routing loops can occur when two gateways think there are alternate routes to reach a third gateway via each other 😵. When the third gateway goes down, they end up pointing at each other, forming a routing loop 🔄. Within the present core system, loops are broken by counting to "infinity" (the internet diameter in gateway hops) 🔢. This (usually) works satisfactorily because GGP propagates changes fairly quickly, since routing updates are sent as soon as changes occur ⚡. Also, the diameter of the internet is quite small (5), and a universal distance metric, hop count, is used. But this will be changed in the future 🔮.
With EGP, changes are propagated slowly 🐌. Although a single unsolicited NR message can be sent, it won't necessarily be passed straight on to other gateways, which must hear about it indirectly 🤷♀️. Also, the distance metrics of different AS's are quite independent, and hence can't be used to count to infinity 🚫.
The initial proposal was to prevent routing loops by restricting the topology of AS's to a tree structure, so there are no multiple routes via alternate AS's 🌳. Multiple routes within the same AS are allowed, since it's the interior routing strategy's responsibility to control loops 💅.
[Mills 84b] has noted that even with the tree topology restriction, "we must assume that transient loops may form within the core system from time to time and that this information may escape to other systems; however, it would be expected that these loops would not persist for very long and would be broken in a short time within the core system itself. Thus a loop between non-core systems can persist until the first round of Update messages sent to the other systems after all traces of the loop have been purged from the core system or until the reachability information ages out of the tables, whichever occurs first" 👀.
With the initial simple stub EGP systems, the tree topology restriction could be satisfied. But for the long term, this does not provide sufficient robustness 🥺.
[Mills 83] proposed a procedure by which the AS's can dynamically reconfigure themselves such that the topology restriction is always met, without the need for a single "core" AS 🪄. One AS would own a shared net, and its neighbor AS's would just conduct EGP with the owner. The owner would pass on such information indirectly, as the core system does now 📬. If the owning AS is defined to be closest to the root of the tree topology, any haphazard interconnection can form itself into an appropriate tree-structured routing topology 🌲. By routing topology I mean the topology as advised in routing updates 📣. There may well be other physical connections, but if they are not advised, they will not be used for routing 🚫. Each AS can conduct EGP with at most one AS that owns one of its shared nets 1️⃣. Any AS that is not conducting EGP over any net owned by another AS is the root of a subtree 🌱. It may conduct EGP with just one other AS that owns one of its shared nets. This "attachment" combines the two subtrees into a single subtree, such that the overall topology is still a tree 🧩. Topology violations can be determined because two different AS's will report that they can reach the same net 🕵️♀️.
With such a dynamic tree, there may be preferred and backup links. In such cases it is necessary to monitor the failed link so that routing can be changed back to the preferred link when service is restored 🔙.
Another aspect to consider is detecting routing loops and then breaking them 🔍. Expiration of the packet time-to-live (TTL) could be used to do this. If such a loop is suspected, a diagnostic packet, such as ICMP echo, could be sent over the suspect route to confirm whether it is a loop 🏓. If a loop is detected, a special routing packet could be sent over the route that instructs each gateway to delete the route after forwarding the packet on 🗑️. The acceptance of new routing information may need to be delayed for a hold down period ⏸️. This approach would require sensible selection of the initial TTL. But this is not done by many hosts 😬.
5.1.2 Current Policy 🎯
Considering the general trend toward increased network interconnection, and the availability of alternative long-haul networks such as ARPANET, WBNET (wideband satellite network), and public data networks, the tree topology restriction is generally unacceptable 🙅♀️. A less restrictive topology is currently recommended ✅. The following is taken from [Mills 84b] 👇.
EGP topological model: okay, the rules for how the whole EGP setup is supposed to look, and they're lowkey so clean 💅
- An autonomous system is a bunch of gateways hooked together by networks. Every gateway in the system must be reachable from every other gateway in that same system, using only paths that go through gateways in that system 🫶
- A gateway in one system can run EGP with a gateway in any other system, as long as the path EGP itself runs over doesn't include a gateway in a third system 🦋
- The "core system" is the main character 👑 It's the only one allowed to share reachability info about systems other than itself
- Every system needs at least one gateway that shares a net with a gateway in the core system 🌸
- And that's it! There are no other topological or connectivity restrictions beyond the ones above ✨
A gateway builds its routing tables using three sources: its own configuration (the directly connected nets), the IGP of its own system (called S from here on, covering the interior nets), and EGP (the interior and exterior nets of neighboring systems). If there's a clash about a particular net N, here's how it gets sorted out 🧚
- If N is directly connected to the gateway, every IGP and EGP report about N gets tossed out 🙈
- If N is reported by IGP as interior to S, and by EGP as either interior or exterior to another system, the IGP report wins 💜
- If N is reported by EGP as interior to one system and exterior to another, the interior report wins 🍓
- If N is reported as interior by two or more gateways in the same system using EGP, the reports with the smallest hop count win 🏆
- In every other case, the latest report received wins ⏰
Old info gets aged out of the tables too 🕰️
The interim model is honestly pretty self-organizing, and I'm obsessed 🥹 Transient routing loops can happen between systems, but they eventually get broken when old reachability info ages out of the tables. Since transient loops can already happen because of temporary core-system loops, the extra loops that could show up with local nets homed to multiple systems don't seem to make the risk go up much at all 💖
5.2 Present ISI Configuration
Okay, so a simplified version of the ISI network setup is in Figure 5-1 ✨ ISI-Hobgoblin can act as a backup gateway function for the core ISI-Gateway, between ARPANET and ISI-NET. ISI-Hobgoblin is a VAX 11/750 running Berkeley Unix 4.2, and the EGP implementation described in this report runs on it 🎀
ISI-Troll is part of a split gateway to the University of California at Irvine network (UCI-ICS) 🌈 The whole logical gateway is ISI-Troll, the 9600 baud link and UCI-750A [Rose 84]. ISI-Troll runs Berkeley Unix 4.1a, so it can't run the EGP program, which means it's a non-routing gateway 🙃 The existence of the UCI-ICS net has to be advised to the core AS by ISI-Hobgoblin. That's done by adding an appropriate entry to the EGPINITFILE 📝
Hosts on ISI-NET, including ISI-Troll, have static route entries that name ISI-Gateway as the first hop for every network except UCI-ICS and ISI-NET 🦋
-------------------------------------------------
/ \
/ ARPANET \
\ 10 /
\ /
-------------------------------------------------
| | |
| | |
| | |
+-------------+ +-------------+ +---------------+
| ISI-PNG11 | | | | |
| Arpanet | | ISI-GATEWAY | | ISI-HOBGOBLIN |
| Address | | | | Vax 11/750 |
| logical | | Core EGP | | Unix 4.2 |
| multiplexer | | | | |
+-------------+ +-------------+ +---------------+
| | |
| | |
| | |
--------------- ----------------------------
/ \ / \
/ 3 Mb/s Ethernet \ / ISI-NET \
\ net 10 / \ 128.9 /
\ / \ /
--------------- ----------------------------
|
|
|
+--------------+
| ISI-TROLL |
| Vax 11/750 |
| Unix 4.1a |
| Non-routing |
| | |
| | 9600 | ISI-TROLL, UCI-750A
| | baud | and the link form a
| | link | single logical gateway
| | |
| UCI-750A |
| Vax 11/750 |
| Unix 4.2 |
+--------------+
|
|
|
----------------------
/ \
/ UCI-ICS \
\ 192.5.19 /
\ /
----------------------Figure 5-1: Simplified ISI Network Configuration 🗺️
EGP can be conducted with ISI-Gateway either across ARPANET or across ISI-NET ✨
5.2.1 EGP Across ARPANET
ISI-Hobgoblin will advise ISI-Gateway across ARPANET, and so the core system, that it can reach ISI-NET and UCI-ICS 📡
Packets from AS's outside ISI that are headed for UCI-ICS get routed via ISI-Gateway, ISI-Hobgoblin and ISI-Troll 🛣️ That extra hop through ISI-Gateway (or some other core EGP gateway) happens because the core gateways don't currently pass on indirect-neighbor exterior gateway addresses in their IGP messages (Gateway-to-Gateway Protocol). Packets leaving UCI-ICS for exterior AS's get routed via ISI-Troll and ISI-Gateway. So the incoming and outgoing routes are different, which is a whole vibe 🙃
Packets that ISI-Hobgoblin originates as a host and sends to exterior AS's will go out through the right gateway on ARPANET 🚀
UCI-ICS can only talk to exterior AS's if ISI-Troll, ISI-Hobgoblin and ISI-Gateway are all up 😭 The dependence on ISI-Gateway could be removed if ISI-Troll routed packets through ISI-Hobgoblin instead. But ISI-Hobgoblin is mainly a host and not a gateway, so it's better for ISI-Gateway to route packets whenever it can 💅
ISI-Hobgoblin can act as a back-up gateway for ISI-Gateway, because it can automatically switch to an alternative core EGP peer if ISI-Gateway goes down 🦸 Even though ISI-Hobgoblin normally tells the core system it can reach ISI-NET, the core prefers its own internal route through ISI-Gateway 🙄 For hosts on ISI-NET to route outgoing packets correctly, their static gateway entries need changing from ISI-Gateway to ISI-Hobgoblin. Right now that would have to be done by hand 🛠️ It's only worth doing if ISI-Gateway is going to be down for an extended period ⏳
5.2.2 EGP Across ISI-NET
ISI-Hobgoblin will advise ISI-Gateway across ISI-NET that its indirect neighbor, ISI-Troll, can reach the UCI-ICS net 🌸
All exterior packet routing for UCI-ICS goes through ISI-Gateway in both directions, with no hops via ISI-Hobgoblin 🎯 Packets that ISI-Hobgoblin originates as a host and sends to exterior AS's go through ISI-Gateway, instead of the ARPANET interface, in both directions, which adds an extra hop 🥲
UCI-ICS can only talk to exterior AS's if ISI-Troll and ISI-Gateway are up, and ISI-Hobgoblin has advised ISI-Gateway about the UCI-ICS route 🫠 If ISI-Hobgoblin goes down, communication can still work, because ISI-Gateway (and the other core gateways) don't time out routes to indirect neighbors 🙌 If ISI-Gateway goes down, ISI-Hobgoblin will need to re-advise it about the UCI-ICS route once it comes back up 🔁
Running EGP over ISI-NET instead of ARPANET should give UCI-ICS more reliable service, for these reasons: ISI-Gateway is specifically designed to be a gateway, it's expected to be up more than ISI-Hobgoblin, it's good to cut out extra routing hops where possible, and the exterior routing information sticks around after ISI-Hobgoblin goes down 💯 If ISI-Hobgoblin is used in its back-up mode, EGP could be restarted across ARPANET once the new gateway routes are manually installed in the hosts 🛠️ So EGP across ISI-NET was picked as the preferred way to operate 🏆
5.2.3 Potential Routing Loop
Okay, the tea ☕ Both ISI-Gateway and ISI-Hobgoblin provide routes between ARPANET and ISI-NET, so there's a potential routing loop 😳 This topology actually breaks the original tree structure restriction. But as long as ISI-Hobgoblin doesn't run EGP over ISI-NET and ARPANET at the same time as ISI-Gateway, the gateways will only ever learn about the alternative route from the shared EGP network, and not from the other one. So a loop can't happen 🙅♀️ For example, if EGP runs over ISI-NET, both ISI-Gateway and ISI-Hobgoblin will know about the alternative routes to ARPANET via each other from ISI-NET, but they won't know the gateway addresses on ARPANET needed to reach ISI-NET from ARPANET. So they don't have enough routing data to bounce packets back and forth between themselves 🧠✨
5.3 Possible Future Configuration
5.3.1 Gateway to UCI-ICS
We can make the service to UCI-ICS more reliable and faster by moving the UCI-ICS interface from ISI-Troll to ISI-Hobgoblin 🚀 Reliability goes up because the connection then only needs ISI-Hobgoblin and its ARPANET interface to be up, and performance gets better because the extra gateway hop disappears 💨
This would also let EGP run across ARPANET, which gives access to the alternative core gateways running EGP 🌐 That makes it more likely to reliably get an EGP neighbor at all times 🥰 It would also cut out the extra hop through ISI-Gateway for packets that ISI-Hobgoblin originates, as a host, and sends to exterior networks 🙌
This configuration change will happen at some point in the future ⏰ It wasn't done at first because ISI-Hobgoblin was experimental and went down more often than ISI-Troll 😅
5.3.2 Dynamic Switch to Backup Gateway
As noted in Section 5.2.1, ISI-Hobgoblin can act as a backup gateway function for ISI-Gateway between ARPANET and ISI-NET 🦸♀️ Backup gateways like this could become a common way to boost reliability 🌈
Right now, switching over to the backup gateway means the new gateway route has to be entered by hand for hosts on ISI-NET 🫤 This section describes a possible
okay so the possible method for flipping over to the backup gateway dynamically when the primary goes down is kinda iconic, bestie 💅✨
The goal is to detect when the primary gateway is down and get every host on the local network switching to the backup gateway with a minimum amount of extra network traffic. Once the primary is back up, the hosts should switch back to it 🦋
The proposed method is for only the backup gateway to keep an eye on the primary gateway's status. When something changes, it tells all the hosts about the new gateway address 👀
5.3.2.1 Usual Operation 🌸
The backup gateway runs a process that sends reachability-probe messages, like ICMP echoes, to the primary gateway every 30 seconds. It uses the responses to figure out reachability, the same way EGP does 🧚 If the primary gateway goes down, a "gateway-address message" that says the backup gateway address gets broadcast (or, even better, multicast) to all hosts. When the primary gateway comes back up, another gateway message gets broadcast, this time with the primary gateway address 🎀
These broadcasts should be done four times at 30 second intervals. That way nobody needs acknowledgements or has to know the host addresses. no cap, it's so clean 🫶
Each host runs a process that listens for gateway-address messages. If a different gateway is advised, the host changes its default gateway entry to the new address 💖
5.3.2.2 Host Initialization 🧚
When a host comes up, the primary gateway could be down, so the host needs a way to figure out that it should use the backup gateway instead 😭 The host could read the addresses of the primary and backup gateways from a static initialization file. Then it sets its default gateway to the primary gateway and sends a "gateway-request message" to the backup gateway, asking for the current gateway address. The backup gateway responds with a gateway-address message. If no response comes back, the gateway-request should be retransmitted three times at 30 second intervals. If there's still no response, the backup gateway can be assumed down and the primary gateway is kept as the default 🙈
Whenever the backup gateway comes up, it broadcasts a gateway-address message ✨
Alternatively, a broadcast (or multicast) gateway-request message could be defined, and only gateways would respond to it. The backup gateway-address message needs to say that it's the backup gateway, so future requests don't need to be broadcast. Again, three retransmissions should be used. But the primary gateway also needs to broadcast its address whenever it comes up 🍓
5.3.2.3 When Both the Primary and Backup are Down 💀
If the primary gateway is down and the backup knows it's about to go down, the backup should broadcast gateway-address messages that indicate the primary gateway. That covers the case where the primary comes up first 🧚
But the backup could go down without any warning, and the primary could come up before it. If the primary gateway broadcasts a gateway-address message when it comes up, there's no problem. Otherwise, while hosts are using the backup gateway, they should send a gateway-request message every 10 minutes. If no response comes back, it should be retransmitted 3 times at 30 second intervals. If there's still no response, the backup is assumed down and hosts revert to the primary gateway 🦋
So the only time hosts need to send messages periodically is when the primary gateway doesn't send gateway-address messages on coming up and the backup gateway is being used. In some cases, such as at ISI, the primary gateway is managed by a different organization, and experimental features can't be conveniently added. 🙈
5.3.2.4 Unix 4.2 BSD 🦋
One difficulty with all of this is that there's no standard way of specifying internet broadcast or multicast addresses. Multicast addressing is preferable, since only the processes participating need to handle the message (interfaces with hardware multicast detection are available) 💅 On Unix 4.2 BSD, an internet address with a zero local address is assumed for the internet broadcast address. However, the general Internet Addressing policy is to use an all ones value to indicate a broadcast function 🤓
On Unix 4.2 BSD systems, both the gateway and host processes could run at the user level, so no kernel modifications are required ✨
A User Datagram Protocol (UDP) socket could be reserved for host-backup-gateway communication 🎀
Super user access to raw sockets, for sending and receiving ICMP Echo messages, requires a minor modification to the internet-family protocol switch table 🔥
6. ACKNOWLEDGEMENT 🫶
I acknowledge with thanks the many people who helped with this project, but in particular: Dave Mills, who suggested the project; Jon Postel, for discussion and encouragement; Liza Martin, for providing the initial EGP code; Berkeley, for providing the "routed" code; Mike Brescia, for assistance with testing; Telecom Australia, for funding me; and ISI, for providing facilities. the whole group is giving main character energy 👑🌈
7. REFERENCES 📚
[Berkeley 83] "Unix Programmer's Manual", Vol. 1, 4.2 Berkeley Software
Distribution, University of California, Berkeley.
[Kirton 84] Kirton, P.A., "EGP Gateway Under Berkeley Unix 4.2", University
of Southern California, Information Sciences Institute,
Research Report ISI/RR-84-145, to be published.
[Mills 83] Mills, D.L., "EGP Models and Self-Organizing Systems" Message
to EGP-PEOPLE@BBN-UNIX, Nov. 1983.
[Mills 84a] Mills, D.L., "Exterior Gateway Protocol Formal Specification",
Network Information Center RFC 904, April 1984.
[Mills 84b] Mills, D.L., "Revised EGP Model Clarified and Discussed",
Message to EGP-PEOPLE@BBN-UNIX, May 1984.
[Postel 84] Postel, J., "Exterior Gateway Protocol Implementation Schedule"
Network Information Center RFC 890, Feb. 1984.
[Rose 84] Rose, M.T., "Low-Tech Connection into the ARPA-Internet: The
Raw-Packet Split Gateway", Department of Information and
Computer Science, University of California, Irvine, Technical
Report 216, Feb. 1984.
[Rosen 82] Rosen, E.C., "Exterior Gateway Protocol", Network Information
Center RFC 827, Oct. 1982.
[Seamonson & Rosen 84]
Seamonson, L.J. and Rosen, E.C., "Stub Exterior Gateway
Protocol", Network Information Center RFC 888, Jan. 84.
[Xerox 81] "Internet Transport Protocols", Xerox System Integration
Standard XSIS 028112, Dec. 1981.📦 where this page comes from
- ietf: rfc911 1984-08
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms