1.9: Case Study - Mapping the Internet to the Ethernet
- Page ID
- 58494
This case study begins with a brief description of Ethernet using the terminology and network model of this chapter. It then explores the issues involved in routing that are raised when one maps a packet-forwarding network such as the Internet to an Ethernet.
A Brief Overview of Ethernet
Ethernet is the generic name for a family of local area networks based on broadcast over a shared wire or fiber link on which all participants can hear one another's transmissions. Ethernet uses a listen-before-sending rule (known as "carrier sense") to control access and it uses a listen-while-sending rule to minimize wasted transmission time if two stations happen to start transmitting at the same time, an error known as a collision. This protocol is named Carrier Sense Multiple Access with Collision Detection, and abbreviated CSMA/CD. Ethernet was demonstrated in 1974 and documented in a 1976 paper by Metcalfe and Boggs [Suggestions for Further Reading 1.1.3]. Since that time several successively higher-speed versions have evolved. Originally designed as a half duplex system, a full duplex, point-to-point specification that relaxes length restrictions was a later development. The primary forms of Ethernet that one encounters either in the literature or in the field are the following:
- Experimental Ethernet, a long obsolete 3 megabit per second network that was used only in laboratory settings. The 1976 paper describes this version.
- Standard Ethernet, a 10 megabit per second version.
- Fast Ethernet, a 100 megabit per second version.
- Gigabit Ethernet, which operates at the eponymous speed.
Standard, fast, and gigabit Ethernet all share the same basic protocol design and format. The format of an Ethernet frame (with some subfield details omitted) is:
| leader | destination | source | type | data | checksum |
|---|---|---|---|---|---|
| 64 bits | 48 bits | 48 bits | 16 bits | 368 to 12,000 bits | 32 bits |
The leader field contains a standard bit pattern that frames the payload and also provides an opportunity for the receiver’s phase-locked loop to synchronize. The destination and source fields identify specific stations on the Ethernet. The type field is used for protocol multiplexing in some applications and to contain the length of the data field in others. (The format diagram does not show that each frame is followed by 96 bit times of silence, which allows finding the end of the frame when the length field is absent.)
The maximum extent of a half duplex Ethernet is determined by its propagation time; the controlling requirement is that the maximum two-way propagation time between the two most distant stations on the network be less than the 576 bit times required to transmit the shortest allowable packet. This restriction guarantees that if a collision occurs, both colliding parties are certain to detect it. When a sending station does detect a collision, it waits a random time before trying again; when there are repeated collisions it uses exponential backoff to increase the interval from which it randomly chooses the time to wait. In a full duplex, point-to-point Ethernet there are no collisions, and the maximum length of the link is determined by the physical medium.
There are many fascinating aspects of Ethernet design and implementation ranging from debates about its probabilistic character to issues of electrical grounding; we omit all of them here. For more information, a good place to start is with the paper by Metcalfe and Boggs. The Ethernet is completely specified in a series of IEEE standards numbered 802.3, and it is described in great detail in most books devoted to networking.
Broadcast Aspects of Ethernet
Section 1.4.5 of this chapter mentioned Ethernet as an example of a network that uses a broadcast link. As illustrated in Figure \(\PageIndex{1}\), the Ethernet link layer is quite simple: every frame is delivered to every station. At its network layer, each Ethernet station has a 48 bit address, which to avoid confusion with other addresses we will call a station identifier. (To help reduce ambiguity in the examples that follow, station identifiers will be the only two-digit numbers.)
.png?revision=1)
Figure \(\PageIndex{1}\): An Ethernet.
The network layer of Ethernet is quite simple. On the sending side, ETHERNET_SEND does nothing but pass the call along to the link layer. On the receiving side, the network handler procedure of the Ethernet network layer is straightforward:
procedure ETHERNET_HANDLE (net_packet, length)
destination ← net_packet.target_id
if destination = my_station_id then
GIVE_TO_END_LAYER (net_packet.data, net_packet.end_protocol, net_packet.source_id)
else
ignore packet
There are two differences between this network layer handler and the network layer handler of a packet-forwarding network:
- Because the underlying physical link is a broadcast link, it is up to the network layer of the station to figure out that it should ignore packets not addressed specifically to it.
- Because every packet is delivered to every Ethernet station, there is no need to do any forwarding.
Most Ethernet implementations actually place ETHERNET_HANDLE completely in hardware. One consequence is that the hardware of each station must know its own station identifier, so it can ignore packets addressed to other stations. This identifier is wired in at manufacturing time, but most implementations also provide a programmable identifier register that overrides the wired-in identifier.
Since the link layer of Ethernet is a broadcast link, it offers a convenient additional opportunity for the network layer to create a broadcast network. For this purpose, Ethernet reserves one station identifier as a broadcast address, and the network handler procedure acquires one additional test:
procedure ETHERNET_HANDLE (net_packet, length)
destination ← net_packet.target_id
if destination = my_station_id or destination = BROADCAST_ID then
GIVE_TO_END_LAYER (net_packet.data, net_packet.end_protocol, net_packet.source_id)
else
ignore packet
The Ethernet broadcast feature is seductive. It has led people to propose also adding broadcast features to packet-forwarding networks. It is possible to develop broadcast algorithms for a forwarding network, but it is a much trickier business. Even in Ethernet, broadcast must be used judiciously. Reliable transport protocols that require every receiving station to send back an acknowledgment lead to a problematic flood of acknowledgment packets. In addition, broadcast mechanisms are too easily triggered by mistake. For example, if a request is accidentally sent with its source address set to the broadcast address, the response will be broadcast to all network attachment points. The worst case is a broadcast sent from the broadcast address, which can lead to a flood of broadcasts. Such mechanisms make a good target for malicious attack on a network, so it is usually thought to be preferable not to implement them at all.
Layer Mapping: Attaching Ethernet to a Forwarding Network
Suppose we have several workstations and perhaps a few servers in one building, all connected using an Ethernet, and we would like to attach this Ethernet to the packet-forwarding network illustrated in Figure \(1.5.4\) from Section 1.5.2, by making the Ethernet a sixth link on router \(K\) in that figure. This connection produces the configuration of Figure \(\PageIndex{2}\).
There are three kinds of network-related labels in the figure. First, each link is numbered with a local single-digit link identifier (in \(italics\)), as viewed from within the station that attaches that link. Second, as in Figure \(\PageIndex{1}\), each Ethernet attachment point has a two-digit Ethernet station identifier. Finally, each station has a one-letter name, just as in the packet-forwarding network in the figure from Section 1.5.2. With this configuration, workstation \(L\) sends a remote procedure call to server \(N\) by sending one or more packets to station 18 of the Ethernet attached to it as link number \(1\).
.png?revision=1)
Figure \(\PageIndex{2}\): Connecting an Ethernet to a packet forwarding network.
Workstation \(L\) might also want to send a request to the computer connected to the destination \(E\), which requires that \(L\) actually send the request packet to router \(K\) at Ethernet station 19 for forwarding to destination \(E\). The complication is that \(E\) may be at address 15 of the packet-forwarding network, while workstation \(M\) is at station 15 of the Ethernet. Since Ethernet station identifiers may be wired into the hardware interface, we probably can’t set them to suit our needs, and it might be a major hassle to go around changing addresses on the original packet-forwarding network. The bottom line here is that we can’t simply use Ethernet station identifiers as the network addresses in our packet-forwarding network. But this conclusion seems to leave station \(L\) with no way of expressing the idea that it wants to send a packet to address \(E\).
We were able to express this idea in words because in the two figures we assigned a unique letter identifier to every station. What our design needs is a more universal concept of network—a cloud that encompasses every station in both the Ethernet and the packet-forwarding network and assigns each station a unique network address. Recall that the letter identifiers originally stood for addresses in the packet-forwarding network; they may even be hierarchical identifiers. We can simply extend that concept and assign identifiers from that same numbering plan to each Ethernet station, in addition to the wired-in Ethernet station identifiers.
What we are doing here is mapping the letter identifiers of the packet-forwarding network to the station identifiers of the Ethernet. Since the Ethernet is itself decomposable into a network layer and a link layer, we can describe this situation, as was suggested in Section 1.3.6, as a mapping composition—an upper-level network layer is being mapped to lower-level network layer. The upper network layer is a simplified version of the Internet, so we will label it with the name "internet," using a lower case initial letter as a reminder that it is simplified. Our internet provides us with a language in which workstation \(L\) can express the idea that it wants to send an RPC request to server \(E\), which is located somewhere beyond the router:
NETWORK_SEND (data, length, RPC, INTERNET, E)
where \(E\) is the internet address of the server, and the fourth argument selects our internet forwarding protocol from among the various available network protocols. With this scheme, station \(A\) also uses the same network address \(E\) to send a request to that server. In other words, this internet provides a universal name space.
Our new, expanded, internet network layer must now map its addresses into the Ethernet station identifiers required by the Ethernet network layer. For example, when workstation \(L\) sends a remote procedure call to server \(N\) by
NETWORK_SEND (data, length, RPC, INTERNET, N)
the internet network layer must turn this into the Ethernet network-layer call
NETWORK_SEND (data, length, RPC, ENET, 18)
in which we have named the Ethernet network-layer protocol ENET.
For this purpose, \(L\) must maintain a table like Table \(\PageIndex{2}\), in which each internet address maps to an Ethernet station identifier. This table maps, for example, address \(N\) to ENET, station 18, as required for the NETWORK_SEND call above. Since our internet is a forwarding network, our table also indicates that for address \(E\) the thing to do is send the packet on ENET to station 19, in the hope that it (a router in our diagram) will be sufficiently well connected to pass the packet along to its destination. This table is just another example of a forwarding table like the ones in Section 1.5 of this chapter.
| internet address | Ethernet/station |
|---|---|
| \(M\) | enet/15 |
| \(N\) | enet/18 |
| \(P\) | enet/14 |
| \(Q\) | enet/22 |
| \(K\) | enet/19 |
| \(E\) | enet/19 |
The Address Resolution Protocol
The forwarding table could simply be filled in by hand, by a network administrator who, every time a new station is added to an Ethernet, visits every station already on that Ethernet and adds an entry to its forwarding table. But the charm of manual network management quickly wears thin as the network grows in number of stations, and a more automatic procedure is usually implemented.
An elegant scheme, known as the address resolution protocol (ARP), takes advantage of the broadcast feature of Ethernet to dynamically fill in the forwarding table as it is needed. Suppose we start with an empty forwarding table and that an application calls the internet NETWORK_SEND interface in \(L\), asking that a packet be sent to internet address \(M\). The internet network layer in \(L\) looks in its local forwarding table, and finding nothing there that helps, it asks the Ethernet network layer to send a query such as the following:
NETWORK_SEND (“where is M?”, 11, ARP, ENET, BROADCAST)
where 10 is the number of bytes in the query, ARP is the network-layer protocol we are using, rather than INTERNET, and BROADCAST is the station identifier that is reserved for broadcast on this Ethernet.
Since this query uses the broadcast address, it will be received by the Ethernet network layer of every station on the attached Ethernet. Each station notices the ARP protocol type and passes it to its ARP handler in the upper network layer. Each ARP handler checks the query, and if it discovers its own internet address in the inquiry, sends a response:
NETWORK_SEND (“M is at station 15”, 18, ARP, ENET, BROADCAST)
At most, one station—the one whose internet address is named by the ARP request—will respond. All the others will ignore the ARP request. When the ARP response arrives at station 17, that station's Ethernet network layer will pass it up to the ARP handler in its upper network layer, which will immediately add an entry relating address \(M\) to station 15 to its forwarding table, shown below. The internet network handler of station 17 can now proceed with its originally requested send operation.
| Internet address | Ethernet/station |
|---|---|
| \(M\) | enet/15 |
Suppose now that station \(L\) tries to send a packet to server \(E\), which is on the internet but not directly attached to the Ethernet. In that case, server \(E\) does not hear the Ethernet broadcast, but the router at station 19 does, and it sends a suitable ARP response instead. The forwarding table then has a second entry as shown below. Station \(L\) can now send the packet to the router, which presumably knows how to forward the packet to its intended destination.
| Internet address | Ethernet/station |
|---|---|
| \(M\) | enet/15 |
| \(E\) | enet/19 |
One more step is required—the server at \(E\) will not be able to reply to station \(L\) unless \(L\) is in its own forwarding table. This step is easy to arrange: whenever router \(K\) hears, via ARP, of the existence of a station on its attached Ethernet, it simply adds that internet address to the list of addresses that it advertises, and whatever routing protocol it is using will propagate that information throughout the internet. If hierarchical addresses are in use, the region designer might assign a region number to be used exclusively for all the stations on one Ethernet, to simplify routing.
Mappings from Ethernet station identifiers to the addresses of the higher network level are thus dynamically built up, and eventually station \(L\) will have the full table shown in Table \(\PageIndex{2}\). Typical systems deployed in the field have developed and refined this basic set of dynamic mapping ideas in many directions: The forwarding table is usually managed as a cache, with entries that time out or can be explicitly updated, to allow stations to change their station identifiers; the ARP response may also be noted by stations that didn’t send the original ARP request for their own future reference; a newly-attached station may, without being asked, broadcast what appears to be an ARP response simply to make itself known to existing stations (advertising); and there is even a reverse version of the ARP protocol that can be used by a station to ask if anyone knows its own higher-level network address, or to ask that a higher-level address be assigned to it. These refinements are not important to our case study, but many of them are essential to smooth network management.