RFC 917

Internet subnets

📅 published October 1984, from ietf

RFC 917: INTERNET SUBNETS 🦋

  • Title: INTERNET SUBNETS ✨
  • RFC number: 917 🌸
  • Author: Jeffrey Mogul, Computer Science Department, Stanford University 💅
  • Working group: Network Working Group 🧚
  • Date: October 1984 📅
  • Status: a proposed protocol for the ARPA-Internet community (see the Status section below) 👑
  • Obsoletes / Updates: the title block doesn't list anything this one obsoletes or updates 🙈

Part 1 of 5, bestie! More coming 🫶💖

Status Of This Memo ✨

Okay so this RFC is basically suggesting a proposed protocol for the ARPA-Internet community 👑, and Jeffrey is literally asking everyone for discussion and suggestions for improvements 🙈. Distribution of this memo is unlimited, so share it with your whole group chat 🌈.

Overview 🦋

We're talking about "subnets" of Internet networks, which are logically visible sub-sections of a single Internet network 🧚. For administrative or technical reasons, lots of organizations have decided to split one Internet network into several subnets instead of getting a whole set of Internet network numbers 💅.

We propose procedures for using subnets and talk through approaches for solving the problems that come up, especially routing 🔥.

Acknowledgment 🫶

This proposal came out of discussions with several other people. J. Noel Chiappa, Chris Kent, and Tim Mann, in particular, gave important suggestions 💜.

1. Introduction ✨

The original vibe of the Internet universe was a two-level hierarchy 👑. The top level was the catenet as a whole, and the level below it was a collection of "Internet Networks," each with its own Network Number. (Not saying the Internet has a hierarchical topology, just that the way addresses get interpreted is hierarchical 🌸.)

This view has been super simple and powerful, but a bunch of organizations found it inadequate and added a third level to how they interpret Internet addresses 🔥. In this view, a given Internet Network might (or might not) be divided into a collection of subnets 🦋.

The original two-level view has a strong presumption: to a host on an Internet network, that network can be seen as a single edge. Put another way, the network can be treated as a "black box" that a set of hosts is plugged into 🧚. This is true of the ARPANET, because the IMPs mask the use of specific links in that network. It's also true of most local area network (LAN) technologies, like Ethernet or ring networks 💅.

But that presumption breaks down in lots of real situations 😭. In moderately large organizations (think Universities or companies with more than one building), it's often necessary to use more than one LAN cable to cover a "local area." For example, at the time of writing, there were eighteen such cables in use at Stanford University, with more planned 🙈.

There are several reasons an organization might use more than one cable to cover a campus 💀:

  • Different technologies: Especially in a research environment, there may be more than one kind of LAN in use. For example, an organization may have some equipment that supports Ethernet, and some that supports a ring network 🍓.
  • Limits of technologies: Most LAN technologies impose limits, based on electrical parameters, on the number of hosts connected and on the total length of the cable. It's easy to exceed these limits, especially the cable length limits 😩.
  • Network congestion: A small subset of the hosts on a LAN can hog most of the bandwidth 😤. A common fix is to divide the hosts into cliques of high mutual communication and put those cliques on separate cables 🫶.
  • Point-to-Point links: Sometimes a "local area," like a university campus, is split into two locations that are too far apart to connect using the preferred LAN technology. In that case, high-speed point-to-point links might connect several LANs 🌈.

An organization that has been forced to use more than one LAN has three choices for assigning Internet addresses 🤔:

  1. Acquire a distinct Internet network number for each cable.
  2. Use a single network number for the entire organization, but assign host numbers without regard to which LAN a host is on. (We'll call this choice "transparent subnets.") 🫠
  3. Use a single network number, and partition the host address space by assigning subnet numbers to the LANs. ("Explicit subnets.") 💅

Each of these approaches has disadvantages 😬. The first one doesn't require any new or modified protocols, but it causes an explosion in the size of Internet routing tables 💥. Information about the internal details of local connectivity gets propagated everywhere, even though it's of little or no use outside the local organization. Since some current gateway implementations don't have much space for routing tables, it would be nice to avoid this problem 🙏.

The second approach needs some convention or protocol that makes the collection of LANs look like a single Internet network 🪄. For example, this can be done on LANs where each Internet address is translated to a hardware address using an Address Resolution Protocol (ARP), by having the bridges between the LANs intercept ARP requests for non-local targets. However, it isn't possible to do this for all LAN technologies, especially those that don't currently use ARP protocols, or LANs that don't support broadcasts 😵. A bigger problem is that bridges have to discover which LAN a host is on, perhaps with a broadcast algorithm. As the number of LANs grows, the cost of broadcasting grows too, and the size of the translation caches the bridges need grows with the total number of hosts in the network 📈.

The third approach goes straight for the key problem: existing standards assume that all hosts on an Internet local network are on a single cable 🎯. The solution is to explicitly support subnets 👑. The downside is that it's a modification of the Internet Protocol, so it requires changes to IP implementations that are already in use (if those implementations are going to be used on a subnetted network) 🛠️. But the authors believe these changes are relatively minor, and once they're made, they yield a simple and efficient solution to the problem ✨. Also, the approach in this document avoids any changes that would be incompatible with existing hosts on non-subnetted networks 🫶.

Further, when appropriate design choices are made, hosts that believe they're on a non-subnetted network can still be used on a subnetted one, as will be explained later 🧚. This is useful when some hosts can't be modified to support subnets explicitly, or when a gradual transition is preferred. Because of this, there seems to be little reason to use the second approach listed above 💅.

The rest of this document describes approaches to subnets of Internet Networks 📖.

1.1. Terminology 🌸

To avoid either ambiguity or prolixity (nobody wants a 900-word definition of a router, right? 💀), a few terms get defined here, and they'll be used in the following sections:

  • Catenet: The collection of connected Internet Networks 🌐
  • Network: A single Internet network (that may or may not be divided into subnets) 🦋
  • Subnet: A subnet of an Internet network 🧩
  • Network Number: As in [8]. 📚
  • Local Address: The bits in an Internet address not used for the network number. Also known as the "rest field" 🎀
  • Subnet Number: A number identifying a subnet within a network 🔢
  • Subnet Field: The bit field in an Internet address used for the subnet number 🫧
  • Host Field: The bit field in an Internet address used for denoting a specific host 🖥️
  • Gateway: A node connected to two or more administratively distinct networks and/or subnets, to which hosts send datagrams to be forwarded 🚪
  • Bridge: A node connected to two or more administratively indistinguishable but physically distinct subnets. It automatically forwards datagrams when necessary, but its existence isn't known to other hosts. Also called a "software repeater" 🌉

2. Standards for Subnet Addressing 💖

Following the division presented in [2], the authors observe that subnets are fundamentally an issue of addressing 🗺️. This section first describes a proposal for interpreting Internet addressing to support subnets. Then it discusses how this address format interacts with broadcasting. Finally, it presents a protocol for discovering which address interpretation is in use on a given network 🔍.

2.1. Interpretation of Internet Addresses 🧠

Say an organization has been assigned an Internet network number, has further divided that network into a set of subnets, and wants to assign host addresses. How should that be done? 🤷‍♀️ Since there are minimal restrictions on how the "local address" part of the Internet address gets assigned, several approaches have been proposed for representing the subnet number 🎨:

  1. Variable-width field: Any number of the bits of the local address part are used for the subnet number. The size of this field is constant for a given network but varies from network to network. If the field width is zero, subnets aren't in use 📏.
  2. Fixed-width field: A specific number of bits (e.g., eight) is used for the subnet number, if subnets are in use 🔒.
  3. Self-encoding variable-width field: Just as the width (i.e., class) of the network number field is encoded by its high-order bits, the width of the subnet field is similarly encoded 🪞.
  4. Self-encoding fixed-width field: A specific number of bits is used for the subnet number. Subnets are in use if the high-order bit of this field is one. Otherwise, the entire local address part is used for the host number 🧬.

Since there seems to be no advantage in doing otherwise, all these schemes place the subnet field as the most significant field in the local address part 👑. Also, since the local address part of a Class C address is so small, there's little reason to support subnets of anything other than Class A and Class B networks 💅.

So which of these four schemes should we pick? ⚖️ First question: do we want a self-encoding scheme? In other words, should it be possible to tell just by examining an Internet address whether it refers to a subnetted network, without referring to any other information? 👀

One advantage of self-encoding is that it lets you determine whether a non-local network has been divided into subnets. It's not clear that this would be useful for anything 🤨. The main advantage, though, is that no additional information is needed for an implementation to determine whether two addresses are on the same subnet 🙌. But that can also be seen as a disadvantage: it may cause problems for non-subnetted networks that already have host numbers using arbitrary bits in the local address part <1>. In other words, it's useful to be able to control whether a network is subnetted independently from how host addresses are assigned 🧩. Another disadvantage of any self-encoding scheme is that it reduces the local address space by at least a factor of two 📉.

The number of bits in a subnet field is a per-network setting, so a network's subnet field width can be anything its administrator picks. Before we get into that, here's the layout.

If a self-encoding scheme is not used, a variable-width subnet field is clearly the way to go 💅. Every network already needs some per-network "flag" saying whether subnets are in use, so storing an integer (the subnet field width) instead of a boolean costs basically nothing extra ✨. The payoff is that each organization gets to decide how to split its scarce local address bits between subnets and hosts. That's a whole vibe 🎀.

Here's the proposal 🦋. The Internet address gets read as:

<network-number><subnet-number><host-number>

The <network-number> field is the same as in [8]. The <host-number> field is at least one bit wide. The width of the <subnet-number> field stays constant for a given network. Nothing else is required for the <subnet-number> or <host-number> fields 🌸. If the subnet field width is zero, the network isn't subnetted, and the interpretation from [8] is used.

Here's an example: on a Class A network with an eight-bit subnet field, an address breaks down like this 👑:

                     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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|    NETWORK    |     SUBNET    |         Host number         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

We expect most organizations to pick a subnet field width that's a multiple of eight bits 🍓. That's simpler and easier to implement efficiently. Still, an implementation must be prepared to handle any other width 💜.

We reject "recursive subnets", where the host field gets split again into "sub-subnet" and host parts 🙅‍♀️. The reasons are:

  • There is no obvious need for a four-level hierarchy.
  • An IP address doesn't have enough bits for this to be useful in general.
  • The extra mechanism it needs is complex.

2.2. Changes to Host Software to Support Subnets

Most IP implementations have code in the module that handles outgoing packets that does something like this 💻:

IF ip_net_number(packet.ip_dest) = ip_net_number(my_ip_addr)
    THEN
        send_packet_locally(packet, packet.ip_dest)
    ELSE
        send_packet_locally(packet,
           gateway_to(ip_net_number(packet.ip_dest)))

(If the code supports multiple connected networks, it gets more complicated, but that doesn't matter for what we're talking about here 🙈.)

To support subnets, you need to store one more 32-bit quantity, called my_ip_mask 🧚. It's a bit-mask with bits set in the fields that match the IP network number, plus extra bits set for the subnet number field. For example, on a Class A network with an eight-bit subnet field, the mask would be 255.255.0.0 🌈.

The code then becomes:

IF bitwise_and(packet.ip_dest, my_ip_mask)
    = bitwise_and(my_ip_addr, my_ip_mask)
    THEN
        send_packet_locally(packet, packet.ip_dest)
    ELSE
        send_packet_locally(packet,
           gateway_to(bitwise_and(packet.ip_dest, my_ip_mask)))

Of course, part of the condition can be precomputed ✨.

It may or may not be necessary to change the "gateway_to" function so that it compares things the same way 🤷‍♀️.

To support multiply-connected hosts, you can keep the "my_ip_addr" and "my_ip_mask" values on a per-interface basis. The condition then has to be evaluated for each interface 🔥.

2.3. Subnets and Broadcasting

Without subnets, there are only two kinds of broadcast possible within the Internet Protocol <2>: broadcast to all hosts on a specific network, or broadcast to all hosts on "this network". The second one is handy when a host doesn't know what network it's on 🫶.

Once subnets are in play, things get a little more complicated 😭. First, you can now broadcast to one specific subnet. Second, broadcasting to all the hosts on a subnetted network needs extra machinery; [6] proposes using "Reverse Path Forwarding" [3] for this. Finally, a broadcast to "this network" should not be forwarded outside the original subnet 🚫.

So implementations must recognize three kinds of broadcast addresses, on top of their own host addresses 💖:

This physical network

A destination address of all ones (255.255.255.255) makes the datagram get sent as a broadcast on the local physical network. It must not be forwarded by any gateway 🛑.

Specific network

The destination address contains a valid network number, and the local address part is all ones (for example, 36.255.255.255) 🌸.

Specific subnet

The destination address contains a valid network number and a valid subnet number, and the host field is all ones (for example, 36.40.255.255) 🦋.

For more on Internet broadcasting, see [6] 📚.

One thing that might help you decide whether to use subnets: with subnets, the originating host can reach all the hosts of a subnetted network in a single operation. You can't do that in one step for the same set of hosts if they're on separate networks 🧁.

2.4. Determining the Width of the Subnet Field

So how does a host (or gateway) figure out what subnet field width is in use on a network it's connected to? 🤔 This is basically the same kind of "bootstrapping" problem hosts face in other places, like working out their own address or finding a gateway on the local network. For all three, there are two basic solutions: "hardwired" information, and broadcast-based protocols 🍭.

"Hardwired" information is whatever a host can know without being on a network. It might be compiled in, or (ideally) stored in a disk file 💾. But for diskless workstations that bootload over a LAN, which is an increasingly common setup, neither hardwired option works well 😩. Since most LAN technology supports broadcasting, the better move is for a newly booted host to broadcast a request for the info it needs. For example, to find out its Internet address, a host can use the "Reverse Address Resolution Protocol" [4] 🌷.

We propose extending the ICMP protocol [9] with a new pair of ICMP message types: "Address Format Request" and "Address Format Reply". They're modeled on the "Information Request" and "Information Reply" ICMP messages 🎀. They're described in full in Appendix I 📖.

Here's the plan. When a host boots, it broadcasts an "Address Format Request" message <3> 📣. A gateway (or a host standing in for one) that gets this message replies with an "Address Format Reply". If the request doesn't say which host sent it (meaning the IP Source Address is zero), the reply gets broadcast too 📡. The requesting host hears the response and uses it to determine the subnet field width 👂.

Since there's only one possible value that can go in an "Address Format Reply" on any given LAN, the requesting host doesn't need to match the replies it hears against the request it sent 🙌. Likewise, there's no problem if more than one gateway responds 💅. We assume hosts reboot infrequently, so this protocol shouldn't add much broadcast load to a network ✨.

If a host is connected to more than one LAN, it must use this protocol on each of them 🔁. The exception is when a response on one of the LANs tells it that several of the LANs are part of the same network, and therefore must share the same subnet field width.

Now, what should a host do if it gets no response to its "Address Format Request", even after a reasonable number of tries? 😬 Three interpretations are possible:

  1. The local net exists in (permanent) isolation from all other nets.
  2. Subnets are not in use, and no host supports this ICMP request.
  3. All gateways on the local net are (temporarily) down.

The first and second cases both mean the subnet field width is zero. In the third case there's no way to know the right value, so zero is the safest guess 🛟. It might turn out to be wrong later, but it won't stop transmissions that would otherwise have succeeded 💪. A host can also recover from a wrong guess. When a gateway comes up, it should broadcast an "Address Format Reply". If a host receives one that disagrees with its guess, it should update its data structures to match the received value 🔄. And no host or gateway should send an "Address Format Reply" based on a "guessed" value 🚫.

Finally, no host is required to use this ICMP protocol to discover the subnet field width. A host with non-volatile storage can perfectly reasonably use stored information instead 🍒.

3. Subnet Routing Methods ✨

okay so bestie, every Internet host has the same problem: how does it figure out a route to another host? 🗺️ With subnets, it's still that problem, just a little bit spicier. 🌶️

Subnets mean routing happens on two levels instead of one. 🎀 If the destination host is on the same network as the source, the routing decision only involves the subnet gateways between them. 🚪 If the destination is on a different network, the source has to pick a gateway out of its own network, and pick a route inside its network to get to that gateway. It's giving multi-step 💅

Here's the lowkey helpful part: lots of hosts can just ignore this whole thing (and honestly ignore all routing choices) 🙈 by using a "default" gateway as the first route to every destination, then relying on ICMP Host Redirect messages to set up better routes. 🦋 BUT, this isn't efficient for a gateway or a multi-homed host, because a redirect might not fix a bad first choice of route. 💀 Hosts like that should use a routing information exchange protocol. That's beyond the scope of this document though, and fr, the problem shows up even when subnets aren't being used at all. 🌸

For a singly-connected host, the goal is to find at least one neighbor gateway. 🧚 There are basically two ways to do that: use hard-wired information, or use broadcasts. 📡 We believe the neighbor-gateway problem is the same with or without subnets, so subnets don't change which solution you pick. 💜

BUT one problem is still left: a source host has to figure out whether a datagram to a given destination address must go through a gateway, or can go directly to the destination host. 🤔 In other words, is the destination on the same physical network as the source? This is the only phase of routing where an implementation has to be explicitly aware of subnets. 👑 Honestly, if broadcasts aren't used, it's the only place an Internet implementation has to be changed to support subnets. ✨

Because of that, some existing implementations can work with subnets without being modified <4>. 🫶 For this to work, those implementations:

  • must be used only on singly-homed hosts, and not as a gateway.
  • must be used on a broadcast LAN.
  • must use an Address Resolution Protocol (ARP), such [7].
  • must not be required to maintain connections in the case of gateway crashes.

Here's how it plays out. 🎬 You modify the ARP server module in a subnet gateway so that when it gets an ARP request, it checks the target Internet address to see if it's along the best route to the target. 🔍 If it is, the gateway sends the requesting host an ARP response with its own hardware address. 🪞 The requesting host thinks it knows the destination's hardware address, so it sends packets to that address. 📦 The gateway actually receives those packets, then forwards them to the destination host by the usual means. It's like a secret handoff 🤫

Ngl, this method is a little bit messy. It needs some blurring of the layers in the gateways, since the ARP server and the Internet routing table normally wouldn't talk to each other at all. 🙃 So it's somewhat unsatisfactory, not gonna lie. Still, it's pretty easy to implement, and it doesn't have significant performance costs. ✅ The big problem is that if the original gateway crashes, the source host has no way to pick an alternate route, even if one exists. 💔 So a connection that could've survived otherwise will break.

Don't mix up this "ARP-based subnetting" with the kinda similar-looking ARP-based bridges. 🙅‍♀️ ARP-based subnetting works because a gateway can look at an IP address and deduce a route to the destination, based on explicit subnet topology. 🧠 So a small part of the routing decision has moved from the source host into the gateway. ARP-based bridges are different: they have to locate each host without any help from a mapping between host address and topology. 🕵️‍♀️ Systems built out of ARP-based bridges should not be called "subnetted." Literally don't do it 😭

N.B.: ARP-based subnetting gets complicated because of broadcasts. 📣 An ARP server [7] should never respond to a request whose target is a broadcast address. 🚫 That kind of request can only come from a host that doesn't recognize the broadcast address as a broadcast, and honoring it would almost certainly lead to a forwarding loop. 🌀 Say there are N such hosts on the physical network that don't recognize this address as a broadcast. Then a packet sent with a Time-To-Live of T could potentially cause T**N spurious re-broadcasts. 💀🔥

4. Case Studies ✨

okay so this section is where we peek at how a few real organizations actually used subnets 🏫 bestie, it's giving real-world receipts 💅

4.1. Stanford University

At Stanford, subnets showed up first for historical reasons 🎓 Stanford had been running the Pup protocols [1] on a bunch of Experimental Ethernets [5] since 1979, which was several years before Internet protocols were a thing. They had a number of Pup gateways in service, and all the hosts and gateways got and swapped routing table info using a simple broadcast protocol 🌸

When the Internet Protocol came along, they picked an eight-bit wide subnet number 🔢 Internet subnet numbers were chosen to match the Pup network number of each Ethernet, and the Pup host numbers (also eight bits) became the host field of the Internet address. iconic matching energy 💖

The Pup-only gateways got modified so they could forward Internet datagrams using their Pup routing tables. Otherwise they had zero understanding of Internet packets, and they didn't adjust the Time-to-live field in the Internet header 🙈 ngl that seems wild, but it's considered acceptable, since bugs that caused forwarding loops never showed up. The Internet hosts that are multi-homed (so they can act as gateways) do adjust the Time-to-live field ✨ and since all of them also serve as Pup gateways, no extra routing information exchange protocol was needed 🧚

Internet host implementations were modified to understand subnets. There were several different ways to do it, but they all had identical effects 🫶 Since every host already had a Pup implementation, the Internet routing tables were maintained by the same process that maintained the Pup routing tables. It just translated the Pup network numbers into Internet subnet numbers. so efficient, periodt 💅

When 10Mbit Ethernets were added, the gateways were modified to use the ARP-based scheme described in an earlier section. This let unmodified hosts be used on the 10Mbit Ethernets 🦋

IP subnets have been in use since early 1982 🎀 Right now there are about 330 hosts, 18 subnets, and a similar number of subnet gateways in service. Once the Pup-only gateways are converted to be true Internet gateways, an Internet-based routing exchange protocol will be introduced, and Pup will be phased out 👑

4.2. MIT

MIT was the first IP site to accumulate a large collection of local network links 🧩 This happened before network numbers were divided into classes, so giving each link at MIT its own IP network number would have eaten up a good portion of the available address space 😭 So MIT decided to use one IP network number and manage the 24-bit "rest" field itself, dividing it into three 8-bit fields: "subnet", "reserved, must be zero", and "host".

The CHAOS protocol already in use at MIT had an 8-bit subnet number field, so it was possible to assign each link the same subnet number in both protocols 🍓 The IP host field was set to 8 bits because most of the local net hardware at that point used 8-bit addresses, as did the CHAOS protocol. It was felt that reserving some bits for the future was wise 🔮

The initial plan was to use a dynamic routing protocol between the IP subnet gateways. Several such protocols have been mooted, but nobody has bothered to implement one, so static routing tables are still used 💀 It is likely that this change will finally be made soon 🌈

To solve the problem that imported IP software always needed modification to work in the subnetted environment, MIT searched for a model of operation that led to the least change in host IP software. This led to a model where IP gateways send ICMP Host Redirects rather than Network Redirects, and all internal MIT IP gateways do so now 🧚 With hosts that can maintain IP routing tables for non-local communication on a per-host basis, this hides most of the subnet structure. The "minimum adjustment" for host software to work correctly in both subnetted and non-subnetted environments is the bit-mask algorithm mentioned earlier 🎯

MIT has no immediate plans to move toward a single "approved" protocol 🙃 This is due partly to the degree of local autonomy and the amount of installed software, and partly to the lack of a single prominent industry standard. Instead, the approach has been to provide a single set of physical links and packet switches, and to layer several "virtual" protocol nets on top of that single set of links 🌸 MIT has had some bad experiences trying to exchange routing information between protocols and wrap one protocol in another, so the general approach is to keep the protocols strictly separated except for sharing the basic hardware. Using ARP to hide the subnet structure isn't really in favor, because it's felt that this overloads the address resolution operation 🙅‍♀️ In a complicated system (i.e. one with loops and variant link speeds), a more sophisticated information interchange will be needed between gateways. Making this an explicit mechanism (but one insulated from the hosts) was felt to be best 💜

4.3. Carnegie-Mellon University

CMU uses a Class B network, currently divided into 11 physical subnets: two 3Mbit Experimental Ethernets, seven 10Mbit Ethernets, and two ProNet rings 🌈 Host numbers are assigned so that all addresses with a given third octet will be on the same subnet (but not necessarily vice versa). Honestly it's essentially an administrative convenience 📋 No software currently knows the specifics of this allocation mechanism or depends on it to route between cables 🙌

Instead, CMU uses an ARP-based bridge scheme 🌉 When a host broadcasts an ARP request, all bridges that receive it cache the original protocol address mapping, then forward the request (after the appropriate adjustments) as an ARP broadcast request onto each of their other connected cables. When a bridge receives a non-broadcast ARP reply with a target protocol address that isn't its own, it consults its ARP cache to determine the cable onto which the reply should be forwarded 🧠 The bridges basically try to transparently extend the ARP protocol into a heterogenous multi-cable environment. That means they are required to turn ARP broadcasts on a single cable into ARP broadcasts on all other connected cables, even when they "know better" 😤 This algorithm works only in the absence of cycles in the network connectivity graph, which is currently the case ✅ Work is underway to replace this simple-minded algorithm with a protocol implemented among the bridges, to support redundant paths and reduce the collective broadcast load. The intent is to retain the ARP base and host transparency, if possible 🦋

Implementations supporting the 3Mbit Ethernet and 10Mb proNET ring at CMU use RFC-826 ARP, instead of some wired-in mapping such as simply using the 8-bit hardware address as the fourth octet of the IP address 🎀

Since there are currently no redundant paths between cables, the issue of maintaining connections across bridge crashes is moot 🫠 With about 150 IP-capable hosts on the net, the bridge caches are still of reasonable size, and little bandwidth is devoted to ARP broadcast forwarding 🍰

CMU's network is likely to grow from its relatively small, singly-connected configuration (centered within their CS/RI facility) into a campus-wide intra-departmental configuration with 5000-10000 hosts and redundant connections between cables 🚀 It is possible that the ARP-based bridge scheme won't scale to that size, and a system of explicit subnets may be required 🤔 The medium-term goal, however, is an environment into which unmodified extant (especially 10Mb Ethernet based) IP implementations can be imported. The intent is to stay with a host-transparent (thus ARP-based) routing mechanism for as long as possible 🫶 CMU is concerned that even if subnets become part of the IP standard, they won't be widely implemented. This is the major obstacle to their use at CMU 😩

I. Address Format ICMP 🧚

Address Format Request or Address Format Reply

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |      Code     |          Checksum             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Identifier          |       Sequence Number         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

IP Fields

Addresses

The address of the source in an address format request message will be the destination of the address format reply message. To form an address format reply message, the source address of the request becomes the destination address of the reply, the source address of the reply is set to the replier's address, the type code changed to A2, the subnet field width inserted into the Code field, and the checksum recomputed. However, if the source address in the request message is zero, then the destination address for the reply message should denote a broadcast 📡

ICMP Fields

Type

A1 for address format request message

A2 for address format reply message

Code

0 for address format request message

Width of subnet field, in bits, for address format reply message

Checksum

The checksum is the 16-bit one's complement of the one's complement sum of the ICMP message starting with the ICMP Type. For computing the checksum, the checksum field should be zero. This checksum may be replaced in the future 🔐

Identifier

An identifier to aid in matching request and replies, may be zero 🪪

Sequence Number

A sequence number to aid in matching request and replies, may be zero 🔢

Description

A gateway receiving an address format request should return it with the Code field set to the number of bits of Subnet number in IP addresses for the network to which the datagram was addressed. If the request was broadcast, the destination network is "this network". The Subnet field width may be from 0 to (31 - N), where N is the width in bits of the IP net number field (i.e., 8, 16, or 24) 🦋

If the requesting host does not know its own IP address, it may leave the source field zero, and then the reply should be broadcast 📣 Since there is only one possible address format for a network, there is no need to match requests with replies. However, this approach should be avoided if at all possible, since it increases the superfluous broadcast load on the network 😬

Type A1 may be received from a gateway or a host 💌

Type A2 may be received from a gateway, or a host acting in lieu of a gateway 💜

II. Examples ✨

okay so for these examples, bestie, we're pretending the requesting host is 36.40.0.123, there's a gateway at 36.40.0.62, and network 36.0.0.0 uses an 8-bit wide subnet field 🎀

First up, say broadcasting is allowed and 36.40.0.123 already knows its own address. It sends this datagram 📮:

   Source address:          36.40.0.123
   Destination address:     36.255.255.255
   Protocol:                ICMP = 1
   Type:                    Address Format Request = A1
   Code:                    0

36.40.0.62 will hear it and should respond with this datagram 💌:

   Source address:          36.40.0.62
   Destination address:     36.40.0.123
   Protocol:                ICMP = 1
   Type:                    Address Format Reply = A2
   Code:                    8

For the rest of these examples, 255.255.255.255 means "broadcast to this physical network," as described in [6] 📡

Now, the previous example is kinda inefficient 💀 because it can end up broadcasting the request across tons of subnets. The most efficient move, and the one we recommend 🫶, is for a host to first figure out its own address (maybe using the "Reverse ARP" protocol from [4]), and then send the ICMP request to 255.255.255.255:

   Source address:          36.40.0.123
   Destination address:     255.255.255.255
   Protocol:                ICMP = 1
   Type:                    Address Format Request = A1
   Code:                    0

The gateway can then reply directly to the requesting host 🦋

Next, imagine 36.40.0.123 is a diskless workstation and doesn't even know its own host number 😭 It could send this:

   Source address:          0.0.0.0
   Destination address:     255.255.255.255
   Protocol:                ICMP = 1
   Type:                    Address Format Request = A1
   Code:                    0

36.40.0.62 will hear that and should respond with this 🌸:

   Source address:          36.40.0.62
   Destination address:     36.40.255.255
   Protocol:                ICMP = 1
   Type:                    Address Format Reply = A2
   Code:                    8

Notice the gateway uses the narrowest possible broadcast to reply 🧚 Sending the reply to 36.255.255.255 would mean it gets transmitted on tons of subnets when it only needs to land on one. Even so, overusing broadcasts puts an unnecessary load on every host on the subnet, so we recommend keeping use of the "anonymous" (0.0.0.0) source address to a minimum 🙈

Lowkey the big takeaway here: broadcasts are a whole group chat. Everyone gets pinged, even if only one person needed to see the message.

And if broadcasting is not allowed, we assume hosts have wired-in info about their neighbor gateways 🧠 So 36.40.0.123 might send this instead:

   Source address:          36.40.0.123
   Destination address:     36.40.0.62
   Protocol:                ICMP = 1
   Type:                    Address Format Request = A1
   Code:                    0

36.40.0.62 should respond exactly like it did in the previous case 💅

Notes 📝

<1> Okay, so some hosts get their addresses by sticking their Class A network number together with the low-order 24 bits of a 48-bit Ethernet hardware address 🔧

<2> Our take on Internet broadcasting is based on [6] 📖

<3> If broadcasting isn't supported, then a host presumably "knows" the address of a neighbor gateway, and should send the ICMP to that gateway 🚪

<4> This is what we were talking about earlier when we said transparent and explicit subnets can coexist on a single network 🌈

References 📚

  1. D.R. Boggs, J.F. Shoch, E.A. Taft, and R.M. Metcalfe. "Pup: An Internetwork Architecture." IEEE Transactions on Communications COM-28, 4, pp612-624, April 1980.
  2. David D. Clark. Names, Addresses, Ports, and Routes. RFC-814, MIT-LCS, July 1982.
  3. Yogan K. Dalal and Robert M. Metcalfe. "Reverse Path Forwarding of Broadcast Packets." Comm. ACM 21, 12, pp1040-1048, December 1978.
  4. Ross Finlayson, Timothy Mann, Jeffrey Mogul, Marvin Theimer. A Reverse Address Resolution Protocol. RFC-903, Stanford University, June 1984.
  5. R.M. Metcalfe and D.R. Boggs. "Ethernet: Distributed Packet Switching for Local Computer Networks." Comm. ACM 19, 7, pp395-404, July 1976. Also CSL-75-7, Xerox Palo Alto Research Center, reprinted in CSL-80-2.
  6. Jeffrey Mogul. Broadcasting Internet Datagrams. RFC-919, Stanford University, October 1984.
  7. David Plummer. An Ethernet Address Resolution Protocol. RFC-826, Symbolics, September 1982.
  8. Jon Postel. Internet Protocol. RFC-791, USC-ISI, September 1981.
  9. Jon Postel. Internet Control Message Protocol. RFC-792, USC-ISI, September 1981.
📦 where this page comes from