RFC 975

RFC 975: Autonomous Confederations 🎀

okay bestie, here's the title block tea ☕:

• Series: Network Working Group
• RFC number: 975
• Author: D. L. Mills, M/A-COM Linkabit
• Date: February 1986
• Category: not stated in this title block
• Obsoletes / Updates: neither is listed in this title block

---

Status of This Memo

so this RFC proposes some upgrades to the Exterior Gateway Protocol (EGP) ✨ so it can do simple multiple-level routing while keeping the robustness features of the current EGP model 🛡️. it's literally asking for discussion and suggestions for improvements 💬. distribution of this memo is unlimited 🦋.

---

Overview

the enhancements don't need retrofits in existing implementations to interoperate with enhanced implementations 🫶. they basically generalize the concept of core system to include multiple communities of autonomous systems, called autonomous confederations 👑. autonomous confederations keep a higher degree of mutual trust than autonomous systems usually assume between each other, including reasonable protection against routing loops between member systems 🔒. but they let the routing restrictions of the current EGP model get relaxed 💅.

the enhancements involve the "hop count" or distance field of the EGP Update message, and the current EGP model doesn't cover how that field gets interpreted 🙈. here it gets a special interpretation within each autonomous confederation to support up to three levels of routing: one within the autonomous system, a second within the autonomous confederation, and an optional third within the universe of confederations 🌈.

---

1. Introduction and Background ✨

okay so the historical development of Internet exterior-gateway routing algorithms started with a rather rigid and restricted topological model 🧱. it put robustness and stability first, at the expense of routing dynamics and flexibility. evolving robust and dynamic routing algorithms has been extraordinarily difficult ever since 😭, and it's probably more about varying perceptions of service requirements than actual engineering problems 🤷‍♀️.

the original exterior-gateway model suggested in RFC-827 [1] and refined in RFC-888 [2] restricted the Internet topology basically to a tree structure 🌳, with the root being the BBN-developed "core" gateway system. the most important thing about this model was that debilitating, resource-consuming routing loops between clusters of gateways (called autonomous systems) couldn't happen in a tree-structured topology 💖. the catch? the administrative and enforcement difficulties, plus the performance liabilities, made widespread implementation impractical 💀.

1.1. The Exterior Gateway Protocol

near-term interoperability between the BBN core gateways and the rest of the gateway population, implemented by other organizations, needed an interim protocol 🧚. it had to be able to exchange reachability information, but it didn't necessarily have to function as a true routing algorithm. that protocol is the Exterior Gateway Protocol (EGP), documented in RFC-904 [3].

EGP was not designed as a routing algorithm, since no agreement could be reached on a trusted, common metric 🙅‍♀️. BUT it was designed to provide high-quality reachability information, both about neighbor gateways and about routes to non-neighbor gateways 💜. right now, dynamic routes get computed only by the core system and handed to non-core gateways, with EGP only acting as an interface mechanism 🔌. non-core gateways can provide routes to the core system and even to other non-core gateways, but they cannot pass on "third-party" routes computed from data received from other gateways 🚫.

as operational experience with EGP built up, it became clear that a more decentralized dynamic routing capability is needed, so that resource-consuming suboptimal routes get avoided 🗺️. there's also been long-standing resistance to the a-priori assumption of a single core system 😤. that comes with suboptimal performance, administrative problems, impossible enforcement, and possible subversion. whether or not that resistance is real or justified, the important technical question is still whether a more dynamic, distributed approach is possible without significantly diluting stability and robustness 🤔.

this document proposes enhancements of EGP that generalize the concept of core system to include multiple communities of autonomous systems, called autonomous confederations 🎀. autonomous confederations keep a higher degree of mutual trust than autonomous systems generally assume, including reasonable protection against routing loops between member systems. the enhancements involve the "hop count" or distance field of the EGP Update message, which gets a special interpretation described later. ngl the interpretation of this field isn't specified in RFC-904, and it's left as a matter for further study 📚.

the interpretation of the distance field involves three levels of metrics 🪜. the lowest level is available to the interior gateway protocol (IGP) of the autonomous system itself, to extend the interior routes to the autonomous system boundary. the next higher level selects preferred routes within the autonomous system to those outside. the third and highest level selects preferred routes within the autonomous confederation to those outside 👑.

the proposed model is believed compatible with the current specifications and practices used in the Internet 🫶. in fact, the entire present conglomeration of autonomous systems, including the core system, can be represented as a single autonomous confederation. new confederations can be formed from existing and new systems as necessary 🦋.

1.2. Routing Restrictions

it was the intent in RFC-904 that its stipulated routing restrictions superseded all previous documents, including RFC-827 and RFC-888 🧾. the idea that a non-core gateway must not pass on third-party information came up in planning meetings. those meetings happened after the previous documents were published but before RFC-904 was finalized 📅. this effectively obsoletes older notions of "stub" or any other asymmetry besides the third-party rule 💅.

so, the only restrictions on a non-core gateway are these. in its EGP messages, (a) a gateway can be listed only if it belongs to the same autonomous system (an internal neighbor), and (b) a net can be listed only if it's reachable via gateways belonging to that system. there are no other restrictions, overt or implied 🙌. the specification doesn't address the design of the core system or its gateways 🤐.

the restrictions imply that, to ensure full connectivity, every non-core gateway must run EGP with a core gateway 🔗. since the present core-gateway implementation disallows other gateways on EGP-neighbor paths, this further implies that every non-core gateway must share a net in common with at least one core gateway 🌉.

there's no a-priori prohibition on using EGP as an IGP, or even on using EGP with a gateway of another non-core system, as long as the third-party rule is observed ✅. if a gateway in each system ran EGP with a gateway in every other system, the notion of a core system would be unnecessary and superfluous 🙃.

at one time during the evolution of the EGP model, a strict hierarchical topology (tree structure) of autonomous systems was required. that's not the case now 🌿. at one time it was also forbidden for two nets to be connected by gateways of two or more systems. again, not the case now 🙌. autonomous systems are sets of gateways, not nets or hosts, so a given net or host can be reachable via more than one system. however, every gateway belongs to exactly one system 🧩.

1.3. Examples and Problems

picture the common case: two local-area nets, A and B, connected to the ARPANET by gateways of different systems 🌐. now assume A and B are connected to each other by a gateway A-B that belongs to the same system as the A-ARPANET gateway. that gateway could list itself and both the A and B nets in EGP messages sent to any other gateway, since both are reachable in its system 🙌. however, the B-ARPANET gateway could list itself and only the B net, because the A-B gateway isn't in its system 😬.

in principle, we could assume a second gateway, B-A, belonging to the same system as the B-ARPANET gateway. that would entitle it to list the A net as well 🤓. however, it may be easier for both systems to sign a treaty and consider the A-B gateway under joint administration 🤝. the implementation of that treaty may not be trivial, though, since the joint gateway must appear to other gateways as two distinct gateways, each with its own autonomous-system number 🫠.

another case happens when, for some reason, a system has no path to a core gateway other than via another non-core system 🧭. consider a third local-area net, C, together with gateway C-A, which belongs to a system other than the A-ARPANET and B-ARPANET gateways. under the restrictions above, gateway C-A could list net C in EGP messages sent to A-ARPANET. A-ARPANET could list ARPANET in messages sent to C-A, but not the other nets it may learn about from the core 🚧. so gateway C-A cannot acquire full routing information unless it runs EGP directly with a core gateway 🥺.

2. Autonomous Systems and Confederations ✨

okay so the second example up there is basically screaming for a way to swap arbitrary routing info between non-core gateways 😭 without wrecking the robustness we already agreed on in our security model. 🔐 one way to do it is to stretch the single-core autonomous-system setup so it can hold multiple core systems 🌸 that needs two things: a topological model that defines the scope of each system, and a global, trusted metric to drive the routing computations 💅 the topological model is in the next section, and the metric is suggested in the section after that 🦋

2.1. Topological Models

bestie, an "autonomous system" is a group of gateways where every gateway can reach every other gateway in the group using only paths through gateways in that same group 🧚 the gateways in a system work together to keep a routing database going with an interior gateway protocol (IGP) and an intra-system trusted routing mechanism, which we're not worrying about here 💜 the IGP is expected to have security mechanisms so that only gateways from the same system can become neighbors with each other 🔥

one or more gateways in an autonomous system can run EGP with one or more gateways in a neighboring system ✨ there's no limit on how many EGP neighbor paths there are or how they're set up, the only rule is that each path has to involve gateways from just one system or the other and can't wander into a third system 🙈 it's specifically NOT required that EGP neighbors share a common network, but most probably will, lowkey 🌈

an "autonomous confederation" is a set of autonomous systems that share a common security model 🎀 that means they trust each other to compute routes to other systems in the same confederation 💖 every gateway in a confederation can reach every other gateway in that confederation using only paths inside it 🦋 there's still no limit on the number or setup of EGP paths beyond what we just said, but it's expected that some mechanism exists so potential EGP neighbors can figure out whether they're in the same confederation 👑 this could be done with access-control lists, for example, or by splitting up the set of system numbers 🍓

a network is "directly reachable" from an autonomous system if a gateway in that system has an interface to it 🌸 every gateway in that system is allowed to list all its directly reachable networks in EGP messages sent to any other system 💅 in general, a particular network might be directly reachable from more than one system, and that's totally a thing 🫶

a network is "reachable" from an autonomous system if it's directly reachable from an autonomous system in the same confederation 💜 a directly reachable net is always reachable from the same system 🧚 every gateway in that confederation is allowed to list all reachable nets in EGP messages sent to any other system ✨ a particular net can end up being either directly reachable or reachable from different confederations, which is giving complicated but also kind of iconic 🌈

so, to keep global routing stable on the Internet, it's explicitly assumed that routes inside an autonomous system to a directly reachable net are always preferred over routes outside that system 🔥 and routes inside an autonomous confederation are always preferred over routes outside that confederation 👑 the mechanism that makes sure this happens is described in the next section 🦋

okay this part is important: in general, EGP Update messages can include two lists of gateways, one for gateways in the same system (internal neighbors) and one for gateways in different systems (external neighbors) 🚨 directly reachable nets must always be associated with gateways of the same system, so that means internal neighbors 💖 meanwhile, non-directly reachable nets can be associated with either internal or external neighbors 🌸 nets that are reachable but not directly reachable must always be associated with gateways of the same confederation 🫶

2.2. Trusted Routing Metrics

there's a general principle that describes distributed systems, and it's kind of the vibe of this whole section 🧚 the "nearer" a thing is, the more dynamic and trustable it is, and the "farther" a thing is, the more static and suspicious it is 🤨 like, the concept of a network is built into the Internet model, and so is the concept of gateways tying networks together 🌐 a cluster of gateways that are "near" each other (like inside one autonomous system) usually swaps routing info with a high-performance routing algorithm 🏎️ that algorithm can sensitively monitor changing performance indicators like queueing delays and link loading, and adapt to them quickly ⚡

clusters that are "far" from each other (like widely separated autonomous systems) usually only need coarse routing info 🌙 sometimes it's just "hints" about the best likely next hop to the general destination area 💭 on the flip side, mutual suspicion goes up with distance, so these clusters might need elaborate security stuff, including peer authentication, confidentiality, secrecy, and signature verification 🔐 also, efficiency usually means the network bandwidth the routing protocol itself is allowed to eat should go down with distance 📉 the trade-off for all of this is usually responsiveness, so the farther apart the clusters are, the less dynamic the routing algorithm is 🐢

the observations above give us a starting point for a globally acceptable routing metric 🌍 so let's assume the metric is an integer 🔢 low values mean finer distinctions for "nearer" stuff relative to the gateway, and high values mean coarser distinctions for "farther" stuff 🔭 values less than a globally agreed constant X are tied to paths confined to the same autonomous system as the sender 🏠 values greater than X but less than another constant Y are tied to paths confined to the autonomous confederation of the sender 🫂 and values greater than Y are tied to the remaining paths 🌌

at each of those three levels (autonomous system, autonomous confederation, and universe of confederations), multiple routing algorithms could run at the same time 🎪 each one could produce a possibly different subtree and metric for each destination net, as long as it stays in the ranges we just talked about 💜 but within each system, the metric has to have the same interpretation, so other systems can mitigate routes between multiple gateways in that system 🧩 the same goes for each confederation, where the metric has to mean the same thing so other confederations can mitigate routes to gateways in it 🫶 all confederations have to agree on a common universe-of-confederations algorithm, but not all confederations need to use the same confederation-level algorithm, and not all systems in the same confederation need to use the same system-level algorithm 🌈✨

3. Implementation Issues ✨

okay so the eight-bit "hop count" (aka the distance field) in the EGP Update is where things get spicy 🌶️. RFC-904 never says how to use it. It just goes "we'll figure that out later" 💀. The model below gives it a meaning AND hints at how to design routing algorithms, so it's kind of a big deal 💅.

For illustration, say X is 128 and Y is 192. Gateways in a particular system give directly-reachable nets distance values less than 128, and exterior gateways can compare those values freely to pick between gateways 🎯. Gateways in every system of a confederation give nets that aren't directly reachable in their system, but are reachable in the confederation, distance values between 128 and 192 🌸. We're also assuming you can tell confederations apart with some feature of the 16-bit system-number field, maybe by reserving a subfield 🧩.

3.1. Data-Base Management Functions

this model is giving "here's one way to organize the gateway data base," and it's honestly a good starting point 🧠. The data base is a routing table. Each entry has a net number plus a list of items, and each item holds (a) the gateway address, system number, and distance that an EGP neighbor provided, and (b) a time-to-live counter, local routing info, and whatever else is needed to manage the data base 📚.

The routing table gets updated every time an EGP Update message comes in from a neighbor, and maybe through other stuff too, like the system IGP 🔄. The message gets decoded into a list of quads, each with a network number, gateway address, system number, and distance. If the gateway address is internal to the neighbor system (figured out from the EGP message), the quad's system number gets set to that system. If it isn't, the system number is set to zero, which means "external" 🌍.

Next up, a new distance value gets computed from the old one in the message, and it has to follow these vibes 🎀:

• If the system number matches the local system number, the new value comes from the rules for the system IGP, but it's gotta be less than 128. 🏠
• If not, and either the system number belongs to the same confederation, or the system number is zero and the old distance is less than 192, the value comes from the rules for the confederation EGP. It has to be at least 128 and less than 192. 🦋
• Otherwise, the value comes from the rules for the (global) universe-of-federations EGP, and it has to be at least 192. 👑

Now for each quad: the routing table gets searched for a matching net number, and if there's no match, a new entry gets made 🔍. Then the list of items for that net number gets searched for a matching gateway address and system number, and if nothing matches, a new entry gets made too 🧚. Last step: the distance field gets recomputed, the time-to-live field gets reset, and local routing info gets inserted 💖.

The time-to-live fields of all items in each list get incremented on a regular basis ⏰. If one goes past a preset maximum, that item is discarded. And if every item on a list gets discarded, the whole entry, net number included, goes too 💀.

When a gateway sends an EGP Update message to a neighbor, it must invert the data base so it's ordered by gateway address instead of net number. Part of that is scanning the routing table and picking the gateway with the minimum distance for each net number 🔎. The resulting list gets sorted by gateway address and partitioned by internal/external system number 🗂️.

Wait, hold on, I need to fix that: the original says "must" in lowercase, so here it is correctly, lowercase, and that's the only time it shows up in this section. Still a whole vibe. 🫶

3.2. Routing Functions

when a gateway gets a datagram (service unit), it searches the routing table for the matching destination net number, then picks the gateway on that list with the minimum distance 🎯. Because of the value assignments above, it's super clear that higher-level routes will never get chosen if lower-level routes exist 👑. It's also clear that route selection inside a system can't mess with route selection outside that system, except through the intra-confederation routing algorithm 🔒. And if a simple min-system-hop algorithm is used for the confederation EGP, the IGP of each system can only influence it as far as reachability goes 🌈.

3.3. Compatibility Issues

the proposed interpretation is backwards-compatible with known EGP implementations that don't interpret the distance field, and with a few known EGP implementations that take private liberties with it 🎀. The simplest way to evolve the current system is to collect the existing implementations that don't interpret the distance field at all into a single confederation, with the present core system and routing restrictions 🧺. Every distance from that confederation would be assumed to be 192, which gives at least a rudimentary capability for routing within the universe of confederations 🌸.

One or more existing or proposed systems where the distance field has a uniform interpretation throughout the system can be organized as autonomous confederations 🦋. That could include the Butterfly gateways that are being deployed now, plus clones somewhere else 🦋. These systems can select routes into the system based on the distance fields of the different gateways 🎯. The Butterfly distance fields can be set to at least 128 if the routing info comes from another Butterfly system, and to at least 192 if it comes from a non-Butterfly system that's presumed to be outside the confederation 🫧.

New systems using an implementation model like the one suggested above can select routes into a confederation based on the distance field ✨. For that to work properly, though, all systems and confederations need to adopt a consistent interpretation of distance values exceeding 192 🔥. That's the bestie rule 🫶.

4. Summary and Conclusions

taken at face value, this document is a proposal for interpreting the distance field of the EGP Update message 💅. Until now that field has had no architected interpretation, even though people have been using it informally 🙈. The proposal orders the autonomous systems into a hierarchy of systems and confederations, and treats the distance field as a three-level metric 🪜. The result is a matching three-level routing community: one that prefers routes inside a system, a second that prefers routes inside a confederation, and a third with no preference at all 👑.

The proposed three-level hierarchy could be extended to any number of levels, but that would strain the distance field, which is limited to eight bits in the current EGP model 😭.

The concept of distance can also be generalized to "administrative distance," as suggested by John Nagle and others 🌈.

5. References

• [1] Rosen, E., Exterior Gateway Protocol (EGP), DARPA Network Working Group Report RFC-827, Bolt Beranek and Newman, September 1982. 📖
• [2] Seamonson, L.J., and E.C., Rosen. "STUB" Exterior Gateway Protocol, DARPA Network Working Group Report RFC-888, BBN Communications, January 1984. 📖
• [3] Mills, D.L., Exterior Gateway Protocol Formal Specification, DARPA Network Working Group Report RFC-904, M/A-COM Linkabit, April 1984. 📖