Module 5
Link Layer and LANs
a. Introduction to the Link Layer
Let’s begin with some important terminology. We’ll find it convenient in this to
refer to any device that runs a link-layer (i.e., layer 2) protocol as a node. Nodes include
hosts, routers, switches, and WiFi access points. We will also refer to the communication
channels that connect adjacent nodes along the communication path as links. In order for
a datagram to be transferred from source host to destination host, it must be moved over
each of the individual links in the end-to-end path. As an example, in the company
network shown at the bottom of, consider sending a datagram from one of the wireless
hosts to one of the servers. This datagram will actually pass through six links: a WiFi link
between sending host and WiFi access point, an Ethernet link between the access point
and a link-layer switch; a link between the link-layer switch and the router, a link
between the two routers; an Ethernet link between the router and a link-layer switch; and
finally an Ethernet link between the switch and the server. Over a given link, a
transmitting node encapsulates the datagram in a link-layer frame and transmits the frame
into the link.
In order to gain further insight into the link layer and how it relates to the network
layer, let’s consider a transportation analogy. Consider a travel agent who is planning a
trip for a tourist traveling from Princeton, New Jersey, to Lausanne, Switzerland. The
travel agent decides that it is most convenient for the tourist to take a limousine from
Princeton to JFK airport, then a plane from JFK airport to Geneva’s airport, and finally a
train from Geneva’s airport to Lausanne’s train station. Oncethe travel agent makes the
three reservations, it is the responsibility of the Princeton limousine company to get the
tourist from Princeton to JFK; it is the responsibility of the airline company to get the
tourist from JFK to Geneva; and it is the responsibility of the Swiss train service to get
the tourist from Geneva to Lausanne. Each of the three segments of the trip is “direct”
between two “adjacent” locations. Note that the three transportation segments are
managed by different companies and use entirelydifferent transportation modes
(limousine, plane, and train). Although the transportation modes are different, they each
provide the basic service of moving passengers from one location to an adjacent location.
In this transportation analogy, the tourist is a datagram, each transportation segment is a
link, the transportation mode is a linklayer protocol, and the travel agent is a routing
protocol.
Framing. Almost all link-layer protocols encapsulate each network-layer
datagram within a link-layer frame before transmission over the link. A frame consists of
a data field, in which the network-layer datagram is inserted, and a number of header
fields. The structure of the frame is specified by the link-layer protocol. We’ll see several
different frame formats when we examine specific link-layer protocols in the second half.
Link access. A medium access control (MAC) protocol specifies the rules by
which a frame is transmitted onto the link. For point-to-point links that have a single
sender at one end of the link and a single receiver at the other end of the link, the MAC
protocol is simple (or nonexistent)—the sender can send a frame whenever the link is
idle. The more interesting case is when multiple nodes share a single broadcast link—the
so-called multiple access problem. Here, the MAC protocol serves to coordinate the
frame transmissions of the many nodes.
Reliable delivery. When a link-layer protocol provides reliable delivery service, it
guarantees to move each network-layer datagram across the link without error. Recall
that certain transport-layer protocols (such as TCP) also provide a reliable delivery
service. Similar to a transport-layer reliable delivery service, a link-layer reliable delivery
service can be achieved with acknowledgments and retransmissions. A link-layer reliable
delivery service is often used for links that are prone to high error rates, such as a
wireless link, with the goal of correcting an error locally—on the link where the error
occurs—rather than forcing an end-to-end retransmission of the data by a transport- or
application-layer protocol. However, link-layer reliable delivery can be considered an
unnecessary overhead for low bit-error links, including fiber, coax, and many twisted-pair
copper links. For this reason, many wired link-layer protocols do not provide a reliable
delivery service.
Error detection and correction. The link-layer hardware in a receiving node can
incorrectly decide that a bit in a frame is zero when it was transmitted asa one, and vice
versa. Such bit errors are introduced by signal attenuation and electromagnetic noise.
Because there is no need to forward a datagram that has an error, many link-layer
protocols provide a mechanism to detect such bit errors. This is done by having the
transmitting node include error-detection bits in the frame, and having the receiving node
perform an error check. That the Internet’s transport layer and network layer also provide
a limited form of error detection—the Internet checksum. Error detection in the link layer
is usually more sophisticated and is implemented in hardware. Error correction is similar
to error detection, except that a receiver not only detects when bit errors have occurred in
the frame but also determines exactly where in the frame the errors have occurred (and
then corrects these errors).
Before diving into our detailed study of the link layer, let’s conclude this
introduction by considering the question of where the link layer is implemented. Is a
host’s link layer implemented in hardware or software? Is it implemented on a separate
card or chip, and how does it interface with the rest of a host’s hardware and operating
system components?
The Ethernet capabilities are either integrated into the motherboard chipset or
implemented via a low-cost dedicated Ethernet chip. For the most part, the link layer is
implemented on a chip called the network adapter, also sometimes known as a network
interface controller (NIC). The network adapter implements many link layer services
including framing, link access, error detection, and so on. Thus, much of a link-layer
controller’s functionality is implemented in hardware.
On the sending side, the controller takes a datagram that has been created and
stored in host memory by the higher layers of the protocol stack, encapsulates the
datagram in a link-layer frame (filling in the frame’s various fields), and then transmits
the frame into the communication link, following the link-access protocol. On the
receiving side, a controller receives the entire frame, and extracts the networklayer
datagram. If the link layer performs error detection, then it is the sending controller that
sets the error-detection bits in the frame header and it is the receiving controller that
performs error detection.
b. Error-Detection and -Correction Techniques
In the previous section, we noted that bit-level error detection and correction—
detecting and correcting the corruption of bits in a link-layer frame sent from one node to
another physically connected neighboring node—are two services often provided by the
link layer. We saw that error-detection and -correction services are also often offered at
the transport layer as well. In this section, we’ll examine a few of the simplest techniques
that can be used to detect and, in somecases, correct such bit errors. A full treatment of
the theory and implementation of this topic is itself the topic of many textbooks (e.g.,
[Schwartz 1980] or [Bertsekas 1991]), and our treatment here is necessarily brief. Our
goal here is to develop an intuitive feel for the capabilities that error-detection and -
correction techniques provide and to see how a few simple techniques work and are used
in practice in the link layer.
At the sending node, data, D, to be protected against bit errors is augmented with
error-detection and -correction bits (EDC). Typically, the data to be protected includes
not only the datagram passed down from the network layer for transmission across the
link, but also link-level addressing information, sequence numbers, and other fields in the
link frame header. Both D and EDC are sent to the receiving node in a link-level frame.
At the receiving node, a sequence of bits, D′ and EDC′ is received. Note that D′ and EDC′
may differ from the original D and EDC as a result of in-transit bit flips.
The receiver’s challenge is to determine whether or not D′ is the same as the
original D, given that it has only received D′ and EDC′. The exact wording of the
receiver’s decision (we ask whether an error is detected, not whether an error has
occurred!) is important. Error-detection and -correction techniques allow the receiver to
sometimes, but not always, detect that bit errors have occurred. Even with the use of
error-detection bits there still may be undetected bit errors; that is, the receiver may be
unaware that the received information contains bit errors. As a consequence, the receiver
might deliver a corrupted datagram to the network layer, or be unaware that the contents
of a field in the frame’s header has been corrupted. We thus want to choose an error-
detection scheme that keeps the probability of such occurrences small. Generally, more
sophisticated error-detection and -correction techniques (that is, those that have a smaller
probability of allowing undetected bit errors) incur a larger overhead—more computation
is needed to compute and transmit a larger number of error-detection and -correction bits.
Perhaps the simplest form of error detection is the use of a single parity bit.
Suppose that the information to be sent, has d bits. In an even parity scheme, the sender
simply includes one additional bit and chooses its value such that the total number of 1s
in the d + 1 bits (the original information plus a parity bit) is even. For odd parity
schemes, the parity bit value is chosen such that there is an odd number of 1s.
Receiver operation is also simple with a single parity bit. The receiver need only
count the number of 1s in the received d + 1 bits. If an odd number of 1-valued bits are
found with an even parity scheme, the receiver knows that at least one bit error has
occurred. More precisely, it knows that some odd number of bit errors have occurred.
But what happens if an even number of bit errors occur? You should convince
yourself that this would result in an undetected error. If the probability of bit errors is
small and errors can be assumed to occur independently from one bit to the next, the
probability of multiple bit errors in a packet would be extremely small. In this case, a
single parity bit might suffice. However, measurements have shown that, rather than
occurring independently, errors are often clustered together in “bursts.” Under burst error
conditions, the probability of undetected errors in a frame protected by single-bit parity
can approach 50 percent [Spragins 1991]. Clearly, a more robust error-detection scheme
is needed (and, fortunately, is used in practice!). But before examining error-detection
schemes that are used in practice, let’s consider a simple generalization of one-bit parity
that will provide us with insight into error-correction techniques.
Suppose now that a single bit error occurs in the original d bits of information.
With this two-dimensional parity scheme, the parity of both the column and the row
containing the flipped bit will be in error. The receiver can thus not only detect the fact
that a single bit error has occurred, but can use the column and row indices of the column
and row with parity errors to actually identify the bit that was corrupted and correct that
error! Corrupted and switched to a 0—an error that is both detectable and correctable at
the receiver. Although our discussion has focused on the original d bits of information, a
single error in the parity bits themselves is also detectable and correctable. Two-
dimensional parity can also detect (but not correct!) any combination of two errors in a
packet. Other properties of the two-dimensional parity scheme are explored in the
problems at the end.
The ability of the receiver to both detect and correct errors is known as forward
error correction (FEC). These techniques are commonly used in audio storage and
playback devices such as audio CDs. In a network setting, FEC techniques can be used
by themselves, or in conjunction with link-layer ARQ techniques similar to those we
examined. FEC techniques are valuable because they can decrease the number of sender
retransmissions required. Perhaps more important, they allow for immediate correction of
errors at the receiver. This avoids having to wait for the round-trip propagation delay
needed for the sender to receive a NAK packet and for the retransmitted packet to
propagate back to the receiver—a potentially important advantage for real-time network
applications [Rubenstein 1998] or links (such as deep-space links) with long propagation
delays. Research examining the use of FEC in error-control protocols includes [Biersack
1992; Nonnenmacher 1998; Byers 1998; Shacham 1990].
In checksumming techniques, the d bits of data are treated as a sequence of k-bit
integers. One simple checksumming method is to simply sum these k-bit integers and use
the resulting sum as the error-detection bits. The Internet checksum is based on this
approach—bytes of data are treated as 16-bit integers and summed. The 1s complement
of this sum then forms the Internet checksum that is carried in the segment header. As
discussed, the receiver checks the checksum by taking the 1s complement of the sum of
the received data (including the checksum) and checking whether the result is all 0 bits. If
any of the bits are 1, an error is indicated. RFC 1071 discusses the Internet checksum
algorithm and its implementation in detail. In the TCP and UDP protocols, the Internet
checksum is computed over all fields (header and data fields included). In IP, the
checksum is computed over the IP header (since the UDP or TCP segment has its own
checksum). In other protocols, for example, XTP [Strayer 1992], one checksum is
computed over the header and another checksum is computed over the entire packet
Checksumming methods require relatively little packet overhead. For example,
the checksums in TCP and UDP use only 16 bits. However, they provide relatively weak
protection against errors as compared with cyclic redundancy check, which is discussed
below and which is often used in the link layer. A natural question at this point is, Why is
checksumming used at the transport layer and cyclic redundancy check used at the link
layer? Recall that the transport layer is typically implemented in software in a host as part
of the host’s operating system. Because transport-layer error detection is implemented in
software, it is important to have a simple and fast error-detection scheme such as
checksumming. On the other hand, error detection at the link layer is implemented in
dedicated hardware in adapters, which can rapidly perform the more complex CRC
operations. Feldmeier [Feldmeier 1995] presents fast software implementation techniques
for not only weighted checksum codes, but CRC (see below) and other codes as well.
An error-detection technique used widely in today’s computer networks is based
on cyclic redundancy check (CRC) codes. CRC codes are also known as polynomial
codes, since it is possible to view the bit string to be sent as a polynomial whose
coefficients are the 0 and 1 values in the bit string, with operations on the bit string
interpreted as polynomial arithmetic.
CRC codes operate as follows. Consider the d-bit piece of data, D, that the
sending node wants to send to the receiving node. The sender and receiver must first
agree on an r + 1 bit pattern, known as a generator, which we will denote as G. We will
require that the most significant (leftmost) bit of G be a 1. The key idea behind CRC
codes. For a given piece of data, D, the sender will choose r additional bits, R, and
append them to D such that the resulting d + r bit pattern (interpreted as a binary number)
is exactly divisible by G (i.e., has no remainder) using modulo-2 arithmetic. The process
of error checking with CRCs is thus simple: The receiver divides the d + r received bits
by G. If the remainder is nonzero, the receiver knows that an error has occurred;
otherwise the data is accepted as being correct
Each of the CRC standards can detect burst errors of fewer than r + 1 bits. (This
means that all consecutive bit errors of r bits or fewer will be detected.) Furthermore,
under appropriate assumptions, a burst of length greater than r + 1 bits is detected with
probability 1 - 0.5r . Also, each of the CRC standards can detect any odd number of bit
errors. See [Williams 1993] for a discussion of implementing CRC checks. The theory
behind CRC codes and even more powerful codes is beyond the scope of this text. The
text [Schwartz 1980] provides an excellent introduction to this topic.
c. Multiple Access Links and Protocols
In the introduction to this, we noted that there are two types of network links:
point-to-point links and broadcast links. A point-to-point link consists of a single sender
at one end of the link and a single receiver at the other end of the link. Many link-layer
protocols have been designed for point-to-point links; the point-to-point protocol (PPP)
and high-level data link control (HDLC) are two such protocols. The second type of link,
a broadcast link, can have multiple sending and receiving nodes all connected to the
same, single, shared broadcast channel. The term broadcast is used here because when
any one node transmits a frame, the channel broadcasts the frame and each of the other
nodes receives a copy. Ethernet and wireless LANs are examples of broadcast link-layer
technologies. In this section, we’ll take a step back from specific link-layer protocols and
first examine a problem of central importance to the link layer: how to coordinate the
access of multiple sending and receiving nodes to a shared broadcast channel—the
multiple access problem. Broadcast channels are often used in LANs, networks that are
geographically concentrated in a single building (or on a corporate or university campus).
Thus, we’ll look at how multiple access channels are used in LANs at the end of this
section.
We are all familiar with the notion of broadcasting—television has been using it
since its invention. But traditional television is a one-way broadcast (that is, one fixed
node transmitting to many receiving nodes), while nodes on a computer network
broadcast channel can both send and receive. Perhaps a more apt human analogy for a
broadcast channel is a cocktail party, where many people gather in a large room (the air
providing the broadcast medium) to talk and listen. A second good analogy is something
many readers will be familiar with—a classroom—where teacher(s) and student(s)
similarly share the same, single, broadcast medium. A central problem in both scenarios
is that of determining who gets to talk (that is, transmit into the channel) and when.
Computer networks similarly have protocols—so-called multiple access protocols
—by which nodes regulate their transmission into the shared broadcast channel. Multiple
access protocols are needed in a wide variety of network settings, including both wired
and wireless access networks, and satellite networks. Although technically each node
accesses the broadcast channel through its adapter, in this section, we will refer to the
node as the sending and receiving device. In practice, hundreds or even thousands of
nodes can directly communicate over a broadcast channel.
Because all nodes are capable of transmitting frames, more than two nodes can
transmit frames at the same time. When this happens, all of the nodes receive multiple
frames at the same time; that is, the transmitted frames collide at all of the receivers.
Typically, when there is a collision, none of the receiving nodes can make any sense of
any of the frames that were transmitted; in a sense, the signals of the colliding frames
become inextricably tangled together. Thus, all the frames involved in the collision are
lost, and the broadcast channel is wasted during the collision interval. Clearly, if many
nodes want to transmit frames frequently, many transmissions will result in collisions,
and much of the bandwidth of the broadcast channel will be wasted.
In order to ensure that the broadcast channel performs useful work when multiple
nodes are active, it is necessary to somehow coordinate the transmissions of the active
nodes. This coordination job is the responsibility of the multiple access protocol. Over
the past 40 years, thousands of papers and hundreds of PhD dissertations have been
written on multiple access protocols; a comprehensive survey of the first 20 years of this
body of work is [Rom 1990]. Furthermore, active research in multiple access protocols
continues due to the continued emergence of new types of links, particularly new wireless
links.
Over the years, dozens of multiple access protocols have been implemented in a
variety of link-layer technologies. Nevertheless, we can classify just about any multiple
access protocol as belonging to one of three categories: channel partitioning protocols,
random access protocols, and taking-turns protocols. We’ll cover these categories of
multiple access protocols in the following three subsections.
Recall from our early discussion back that time-division multiplexing (TDM) and
frequency-division multiplexing (FDM) are two techniques that canbe used to partition a
broadcast channel’s bandwidth among all nodes sharing that channel. As an example,
suppose the channel supports N nodes and that the transmission rate of the channel is R
bps. TDM divides time into time frames and further divides each time frame into N time
slots. (The TDM time frame should not be confused with the link-layer unit of data
exchanged between sending and receiving adapters, which is also called a frame. In order
to reduce confusion, in this subsection we’ll refer to the link-layer unit of data exchanged
as a packet.) Each time slot is then assigned to one of the N nodes. Whenever a node has
a packet to send, it transmits the packet’s bits during its assigned time slot in the
revolving TDM frame. Typically, slot sizes are chosen so that a single packet can be
transmitted during a slot time.
Returning to our cocktail party analogy, a TDM-regulated cocktail party would
allow one partygoer to speak for a fixed period of time, then allow another partygoer to
speak for the same amount of time, and so on. Once everyone had had a chance to talk,
the pattern would repeat.
TDM is appealing because it eliminates collisions and is perfectly fair: Each node
gets a dedicated transmission rate of R/N bps during each frame time. However, it has
two major drawbacks. First, a node is limited to an average rate of R/N bps even when it
is the only node with packets to send. A second drawback is that a node must always wait
for its turn in the transmission sequence—again, even when it is the only node with a
frame to send. Imagine the partygoer who is the only one with anything to say (and
imagine that this is the even rarer circumstance where everyone wants to hear what that
one person has to say). Clearly, TDM would be a poor choice for a multiple access
protocol for this particular party.
While TDM shares the broadcast channel in time, FDM divides the R bps channel
into different frequencies (each with a bandwidth of R/N) and assigns each frequency to
one of the N nodes. FDM thus creates N smaller channels of R/N bps out of the single,
larger R bps channel. FDM shares both the advantages and drawbacks of TDM. It avoids
collisions and divides the bandwidth fairly among the N nodes. However, FDM also
shares a principal disadvantage with TDM—a node is limited to a bandwidth of R/N,
even when it is the only node with packets to send.
A third channel partitioning protocol is code division multiple access (CDMA).
While TDM and FDM assign time slots and frequencies, respectively, to the nodes,
CDMA assigns a different code to each node. Each node then uses its unique code to
encode the data bits it sends. If the codes are chosen carefully, CDMA networks have the
wonderful property that different nodes can transmit simultaneously and yet have their
respective receivers correctly receive a sender’s encoded data bits (assuming the receiver
knows the sender’s code) in spite of interfering transmissions by other nodes. CDMA has
been used in military systems for some time (due to its anti-jamming properties) and now
has widespread civilian use, particularly in cellular telephony. Because CDMA’s use is so
tightly tied to wireless channels, we’ll save our discussion of the technical details of
CDMA. For now, it will suffice to know that CDMA codes, like time slots in TDM and
frequencies in FDM, can be allocated to the multiple access channel users.
The second broad class of multiple access protocols are random access protocols.
In a random access protocol, a transmitting node always transmits at the full rate of the
channel, namely, R bps. When there is a collision, each node involved in the collision
repeatedly retransmits its frame (that is, packet) until its frame gets through without a
collision. But when a node experiences a collision, it doesn’t necessarily retransmit the
frame right away. Instead it waits a random delay before retransmitting the frame. Each
node involved in a collision chooses independent random delays. Because the random
delays are independently chosen, it is possible that one of the nodes will pick a delay that
is sufficiently less than the delays of the other colliding nodes and will therefore be able
to sneak its frame into the channel without a collision.
There are dozens if not hundreds of random access protocols described in the
literature [Rom 1990; Bertsekas 1991]. In this section we’ll describe a few of the most
commonly used random access protocols—the ALOHA protocols [Abramson 1970;
Abramson 1985; Abramson 2009] and the carrier sense multiple access (CSMA)
protocols [Kleinrock 1975b]. Ethernet [Metcalfe 1976] is a popular and widely deployed
CSMA protocol.
The slotted ALOHA protocol required that all nodes synchronize their
transmissions to start at the beginning of a slot. The first ALOHA protocol [Abramson
1970] was actually an unslotted, fully decentralized protocol. In pure ALOHA, when a
frame first arrives (that is, a network-layer datagram is passed down from the network
layer at the sending node), the node immediately transmits the frame in its entirety into
the broadcast channel. If a transmitted frame experiences a collision with one or more
other transmissions, the node will then immediately (after completely transmitting its
collided frame) retransmit the frame with probability p. Otherwise, the node waits for a
frame transmission time. After this wait, it then transmits the frame with probability p, or
waits (remaining idle) for another frame time with probability 1 – p.
To determine the maximum efficiency of pure ALOHA, we focus on an
individual node. We’ll make the same assumptions as in our slotted ALOHA analysis and
take the frame transmission time to be the unit of time. At any given time, the probability
that a node is transmitting a frame is p. Suppose this frame begins transmission at time t0.
Order for this frame to be successfully transmitted, no other nodes can begin their
transmission in the interval of time [t0 - 1, t0]. Such a transmission would overlap with
the beginning of the transmission of node i’s frame. The probability that all other nodes
do not begin a transmission in this interval is (1 - p) N-1 . Similarly, no other node can
begin a transmission while node i is transmitting, as such a transmission would overlap
with the latter part of node i’s transmission. The probability that all other nodes do not
begin a transmission in this interval is also (1 - p) N-1 . Thus, the probability that a given
node has a successful transmission is p(1 - p) 2(N-1) . By taking limits as in the slotted
ALOHA case, we find that the maximum efficiency of the pure ALOHA protocol is only
1/(2e)—exactly half that of slotted ALOHA. This then is the price to be paid for a fully
decentralized ALOHA protocol.
In both slotted and pure ALOHA, a node’s decision to transmit is made
independently of the activity of the other nodes attached to the broadcast channel. In
particular, a node neither pays attention to whether another node happens to be
transmitting when it begins to transmit, nor stops transmitting if another node begins to
interfere with its transmission. In our cocktail party analogy, ALOHA protocols are quite
like a boorish partygoer who continues to chatter away regardless of whether other
people are talking. As humans, we have human protocols that allow us not only to behave
with more civility, but also to decrease the amount of time spent “colliding” with each
other in conversation and, consequently, to increase the amount of data we exchange in
our conversations.
The need to wait a random (rather than fixed) amount of time is hopefully clear—
if two nodes transmitted frames at the same time and then both waited the same fixed
amount of time, they’d continue colliding forever. But what is a good interval of time
from which to choose the random backoff time? If the interval is large and the number of
colliding nodes is small, nodes are likely to wait a large amount of time (with the channel
remaining idle) before repeating the sense-and-transmit-whenidle step. On the other hand,
if the interval is small and the number of colliding nodes is large, it’s likely that the
chosen random values will be nearly the same, and transmitting nodes will again collide.
What we’d like is an interval that is short when the number of colliding nodes is small,
and long when the number of colliding nodes is large.
The binary exponential backoff algorithm, used in Ethernet as well as in DOCSIS
cable network multiple access protocols [DOCSIS 3.1 2014], elegantly solves this
problem. Specifically, when transmitting a frame that has already experienced n
collisions, a node chooses the value of K at random from {0,1,2, . . . . 2n-1}. Thus, the
more collisions experienced by a frame, the larger the interval from which K is chosen.
For Ethernet, the actual amount of time a node waits is K # 512 bit times (i.e., K times
the amount of time needed to send 512 bits into the Ethernet) and the maximum value
that n can take is capped at 10.
Let’s look at an example. Suppose that a node attempts to transmit a frame for the
first time and while transmitting it detects a collision. The node then chooses K = 0 with
probability 0.5 or chooses K = 1 with probability 0.5. If the node chooses K = 0, then it
immediately begins sensing the channel. If the node chooses K = 1, it waits 512 bit times
(e.g., 5.12 microseconds for a 100 Mbps Ethernet) before beginning the sense-and-
transmit-when-idle cycle. After a second collision, K is chosen with equal probability
from {0,1,2,3}. After three collisions, K is chosen with equal probability from
{0,1,2,3,4,5,6,7}. After 10 or more collisions, K is chosen with equal probability from
{0,1,2, . . . , 1023}. Thus, the size of the sets from which K is chosen grows exponentially
with the number of collisions; for this reason this algorithm is referred to as binary
exponential backoff.
We also note here that each time a node prepares a new frame for transmission, it
runs the CSMA/CD algorithm, not taking into account any collisions that may have
occurred in the recent past. So it is possible that a node with a new frame will
immediately be able to sneak in a successful transmission while several other nodes are in
the exponential backoff state.
When only one node has a frame to send, the node can transmit at the full channel
rate (e.g., for Ethernet typical rates are 10 Mbps, 100 Mbps, or 1 Gbps). However, if
many nodes have frames to transmit, the effective transmission rate of the channel can be
much less. We define the efficiency of CSMA/CD to be the long-run fraction of time
during which frames are being transmitted on the channel without collisions when there
is a large number of active nodes, with each node having a large number of frames to
send. In order to present a closed-form approximation of the efficiency of Ethernet, let
dprop denote the maximum time it takes signal energy to propagate between any two
adapters. Let dtrans be the time to transmit a maximum-size frame (approximately 1.2
msecs for a 10 Mbps Ethernet). A derivation of the efficiency of CSMA/CD is beyond
the scope of this book (see [Lam 1980] and [Bertsekas 1991]).
Recall that two desirable properties of a multiple access protocol are (1) when
only one node is active, the active node has a throughput of R bps, and (2) when M nodes
are active, then each active node has a throughput of nearly R/M bps. The ALOHA and
CSMA protocols have this first property but not the second. This has motivated
researchers to create another class of protocols—the taking-turns protocols. As with
random access protocols, there are dozens of taking-turns protocols, and each one of
these protocols has many variations. We’ll discuss two of the more important protocols
here. The first one is the polling protocol. The polling protocol requires one of the nodes
to be designated as a master node. The master node polls each of the nodes in a round-
robin fashion. In particular, the master node first sends a message to node 1, saying that it
(node 1) can transmit up to some maximum number of frames. After node 1 transmits
some frames, the master node tells node 2 it (node 2) can transmit up to the maximum
number of frames. (The master node can determine when a node has finished sending its
frames by observing the lack of a signal on the channel.) The procedure continues in this
manner, with the master node polling each of the nodes in a cyclic manner. The polling
protocol eliminates the collisions and empty slots that plague random access protocols.
This allows polling to achieve a much higher efficiency. Butit also has a few drawbacks.
The first drawback is that the protocol introduces a polling delay—the amount of time
required to notify a node that it can transmit. If, for example, only one node is active,
then the node will transmit at a rate less than R bps, as the master node must poll each of
the inactive nodes in turn each time the active node has sent its maximum number of
frames. The second drawback, which is potentially more serious, is that if the master
node fails, the entire channel becomes inoperative. The Bluetooth protocol, which we
will study in, is an example of a polling protocol.
The second taking-turns protocol is the token-passing protocol. In this protocol
there is no master node. A small, special-purpose frame known as a token is exchanged
among the nodes in some fixed order. For example, node 1 might always send the token
to node 2, node 2 might always send the token to node 3, and node N might always send
the token to node 1. When a node receives a token, it holds onto the token only if it has
some frames to transmit; otherwise, it immediately forwards the token to the next node. If
a node does have frames to transmit when it receives the token, it sends up to a maximum
number of frames and then forwards the token to the next node. Token passing is
decentralized and highly efficient. But it has its problems as well. For example, the
failure of one node can crash the entire channel. Or if a node accidentally neglects to
release the token, then some recovery procedure must be invoked to get the token back in
circulation. Over the years many token-passing protocols have been developed, including
the fiber distributed data interface (FDDI) protocol [Jain 1994] and the IEEE 802.5 token
ring protocol [IEEE 802.5 2012], and each one had to address these as well as other
sticky issues.
d. Switched Local Area Networks
Having covered broadcast networks and multiple access protocols in the previous
section, let’s turn our attention next to switched local networks. A switched local network
connecting three departments, two servers and a router with four switches. Because these
switches operate at the link layer, they switch link-layer frames (rather than network-
layer datagrams), don’t recognize network-layer addresses, and don’t use routing
algorithms like OSPF to determine paths through the network of layer-2 switches. Instead
of using IP addresses, we will soon see that they use link-layer addresses to forward link-
layer frames through the network of switches. We’ll begin our study of switched LANs
by first covering link layer addressing. We then examine the celebrated Ethernet protocol.
After examining link-layer addressing and Ethernet, we’ll look at how link-layer switches
operate, and then how these switches are often used to build large-scale LANs.
Hosts and routers have link-layer addresses. Now you might find this surprising,
recalling from that hosts and routers have network-layer addresses as well. You might be
asking, why in the world do we need to have addresses at both the network and link
layers? In addition to describing the syntax and function of the link-layer addresses, in
this section we hope to shed some light on why the two layers of addresses are useful
and, in fact, indispensable. We’ll also cover the Address Resolution Protocol (ARP),
which provides a mechanism to translate IP addresses to link-layer addresses.
In truth, it is not hosts and routers that have link-layer addresses but rather their
adapters (that is, network interfaces) that have link-layer addresses. A host or router with
multiple network interfaces will thus have multiple link-layer addresses associated with
it, just as it would also have multiple IP addresses associated with it. It’s important to
note, however, that link-layer switches do not have link-layer addresses associated with
their interfaces that connect to hosts and routers. This is because the job of the link-layer
switch is to carry datagrams between hosts and routers; a switch does this job
transparently, that is, without the host or router having to explicitly address the frame to
the intervening switch. A link layer address is variously called a LAN address, a physical
address, or a MAC address. Because MAC address seems to be the most popular term,
we’ll henceforth refer to link-layer addresses as MAC addresses. For most LANs
(including Ethernet and 802.11 wireless LANs), the MAC address is 6 bytes long, giving
248 possible MAC addresses. These 6-byte addresses are typically expressed in
hexadecimal notation, with each byte of the address expressed as a pair of hexadecimal
numbers. Although MAC addresses were designed to be permanent, it is now possible to
change an adapter’s MAC address via software. For the rest of this section, however,
we’ll assume that an adapter’s MAC address is fixed.
One interesting property of MAC addresses is that no two adapters have the same
address. This might seem surprising given that adapters are manufactured in many
countries by many companies. How does a company manufacturing adapters in Taiwan
make sure that it is using different addresses from a company manufacturingadapters in
Belgium? The answer is that the IEEE manages the MAC address space. In particular,
when a company wants to manufacture adapters, it purchases a chunk of the address
space consisting of 224 addresses for a nominal fee. IEEE allocates the chunk of 224
addresses by fixing the first 24 bits of a MAC address and letting the company create
unique combinations of the last 24 bits for each adapter.
An adapter’s MAC address has a flat structure (as opposed to a hierarchical
structure) and doesn’t change no matter where the adapter goes. A laptop with an
Ethernet interface always has the same MAC address, no matter where the computer
goes. A smartphone with an 802.11 interface always has the same MAC address, no
matter where the smartphone goes. Recall that, in contrast, IP addresses have a
hierarchical structure (that is, a network part and a host part), and a host’s IP addresses
needs to be changed when the host moves, i.e., changes the network to which it is
attached. An adapter’s MAC address is analogous to a person’s social security number,
which also has a flat addressing structure and which doesn’t change no matter where the
person goes. An IP address is analogous to a person’s postal address, which is
hierarchical and which must be changed whenever a person moves. Just as a person may
find it useful to have both a postal address and a social security number, it is useful for a
host and router interfaces to have both a network-layer address and a MAC address.
When an adapter wants to send a frame to some destination adapter, the sending
adapter inserts the destination adapter’s MAC address into the frame and then sends the
frame into the LAN. As we will soon see, a switch occasionally broadcasts an incoming
frame onto all of its interfaces. We’ll see that 802.11 also broadcasts frames. Thus, an
adapter may receive a frame that isn’t addressed to it. Thus, when an adapter receives a
frame, it will check to see whether the destination MAC addressin the frame matches its
own MAC address. If there is a match, the adapter extracts the enclosed datagram and
passes the datagram up the protocol stack. If there isn’t a match, the adapter discards the
frame, without passing the network-layer datagram up. Thus, the destination only will be
interrupted when the frame is received.
However, sometimes a sending adapter does want all the other adapters on the
LAN to receive and process the frame it is about to send. In this case, the sending adapter
inserts a special MAC broadcast address into the destination address field of the frame.
For LANs that use 6-byte addresses (such as Ethernet and 802.11), the broadcast address
is a string of 48 consecutive 1s (that is, FF-FF-FF-FF-FF-FF in hexadecimal notation).
It should now be clear how ARP operates when a host wants to send a datagram
to another host on the same subnet. But now let’s look at the more complicated situation
when a host on a subnet wants to send a network-layer datagram to a host off the subnet
(that is, across a router onto another subnet). Let’s discuss this issue in the context, which
shows a simple network consisting of two subnets interconnected by a router. There are
several interesting things to note. Each host has exactly one IP address and one adapter.
But, a router has an IP address for each of its interfaces. For each router interface there is
also an ARP module (in the router) and an adapter. Because the router has two interfaces,
it has two IP addresses, two ARP modules, and two adapters. Of course, each adapter in
the network has its own MAC address.
Now let’s examine how a host on Subnet 1 would send a datagram to a host on
Subnet 2. Specifically, suppose that host 111.111.111.111 wants to send an IP datagram
to a host 222.222.222.222. The sending host passes the datagram to its adapter, as usual.
But the sending host must also indicate to its adapter an appropriate destination MAC
address. What MAC address should the adapter use? One might be tempted to guess that
the appropriate MAC address is that of the adapter for host 222.222.222.222, namely, 49-
BD-D2-C7-56-2A. This guess, however, would be wrong! If the sending adapter were to
use that MAC address, then none of the adapters on Subnet 1 would bother to pass the IP
datagram up to its network layer, since the frame’s destination address would not match
the MAC address of any adapter on Subnet 1. The datagram would just die and go to
datagram heaven.
If we look carefully, we see that in order for a datagram to go from
111.111.111.111 to a host on Subnet 2, the datagram must first be sent to the router
interface 111.111.111.110, which is the IP address of the first-hop router on the path to
the final destination. Thus, the appropriate MAC address for the frame is the address of
the adapter for router interface 111.111.111.110, namely, E6-E9-00-17- BB-4B. How
does the sending host acquire the MAC address for 111.111.111.110? By using ARP, of
course! Once the sending adapter has this MAC address, it creates a frame (containing
the datagram addressed to 222.222.222.222) and sends the frame into Subnet 1. The
router adapter on Subnet 1 sees that the link-layer frame is addressed to it, and therefore
passes the frame to the network layer of the router. Hooray—the IP datagram has
successfully been moved from source host to the router! But we are not finished. We still
have to move the datagram from the router to the destination. The router now has to
determine the correct interface on which the datagram is to be forwarded, this is done by
consulting a forwarding table in the router. The forwarding table tells the router that the
datagram is to be forwarded via router interface 222.222.222.220. This interface then
passes the datagram to its adapter, which encapsulates the datagram in a new frame and
sends the frame into Subnet 2. This time, the destination MAC address of the frame is
indeed the MAC address of the ultimate destination. And how does the router obtain this
destination MAC address? From ARP, of course!
Ethernet has pretty much taken over the wired LAN market. In the 1980s and the
early 1990s, Ethernet faced many challenges from other LAN technologies, including
token ring, FDDI, and ATM. Some of these other technologies succeeded in capturing a
part of the LAN market for a few years. But since its invention in the mid1970s, Ethernet
has continued to evolve and grow and has held on to its dominant position. Today,
Ethernet is by far the most prevalent wired LAN technology, and it is likely to remain so
for the foreseeable future. One might say that Ethernet has been to local area networking
what the Internet has been to global networking.
There are many reasons for Ethernet’s success. First, Ethernet was the first widely
deployed high-speed LAN. Because it was deployed early, network administrators
became intimately familiar with Ethernet—its wonders and its quirks—and were
reluctant to switch over to other LAN technologies when they came on the scene. Second,
token ring, FDDI, and ATM were more complex and expensive than Ethernet, which
further discouraged network administrators from switching over. Third, the most
compelling reason to switch to another LAN technology (such as FDDI or ATM) was
usually the higher data rate of the new technology; however, Ethernet always fought
back, producing versions that operated at equal data rates or higher. Switched Ethernet
was also introduced in the early 1990s, which further increased its effective data rates.
Finally, because Ethernet has been so popular, Ethernet hardware (in particular, adapters
and switches) has become a commodity and is remarkably cheap.
By the late 1990s, most companies and universities had replaced their LANs with
Ethernet installations using a hub-based star topology. In such an installation the hosts
(and routers) are directly connected to a hub with twisted-pair copper wire. A hub is a
physical-layer device that acts on individual bits rather than frames. When a bit,
representing a zero or a one, arrives from one interface, the hub simply re-creates the bit,
boosts its energy strength, and transmits the bit onto all the other interfaces. Thus,
Ethernet with a hub-based star topology is also a broadcast LAN—whenever a hub
receives a bit from one of its interfaces, it sends a copy out on all of its other interfaces.
In particular, if a hub receives frames from two different interfaces at the same time, a
collision.
To give this discussion about Ethernet frames a tangible context, let’s consider
sending an IP datagram from one host to another host, with both hosts on the same
Ethernet LAN (Although the payload of our Ethernet frame is an IP datagram, we note
that an Ethernet frame can carry other network-layer packets as well.) Let the sending
adapter, adapter A, have the MAC address AA-AA-AA-AA-AA-AA and the receiving
adapter, adapter B, have the MAC address BB-BB-BB-BB-BB-BB. The sending adapter
encapsulates the IP datagram within an Ethernet frame and passes the frame to the
physical layer. The receiving adapter receives the frame from the physical layer, extracts
the IP datagram, and passes the IP datagram to the network layer occurs and the nodes
that created the frames must retransmit.
In our discussion above, we’ve referred to Ethernet as if it were a single protocol
standard. But in fact, Ethernet comes in many different flavors, with somewhat
bewildering acronyms such as 10BASE-T, 10BASE-2, 100BASE-T, 1000BASE-LX,
10GBASE-T and 40GBASE-T. These and many other Ethernet technologies have been
standardized over the years by the IEEE 802.3 CSMA/CD (Ethernet) working group
[IEEE 802.3 2020]. While these acronyms may appear bewildering, there is actually
considerable order here. The first part of the acronym refers to the speed of the standard:
10, 100, 1000, or 10G, for 10 Megabit (per second), 100 Megabit, Gigabit, 10 Gigabit
and 40 Gigibit Ethernet, respectively. “BASE” refers to baseband Ethernet, meaning that
the physical media only carries Ethernet traffic; almost all of the 802.3 standards are for
baseband Ethernet. The final part of the acronym refers to the physical media itself;
Ethernet is both a link-layer and a physical-layer specification and is carried over a
variety of physical media including coaxial cable, copper wire, and fiber. Generally, a
“T” refers to twisted-pair copper wires.
Historically, an Ethernet was initially conceived of as a segment of coaxial cable.
The early 10BASE-2 and 10BASE-5 standards specify 10 Mbps Ethernet over two types
of coaxial cable, each limited in length to 500 meters. Longer runs could be obtained by
using a repeater—a physical-layer device that receives a signal on the input side, and
regenerates the signal on the output side. A coaxial cable corresponds nicely to our view
of Ethernet as a broadcast medium—all frames transmitted by one interface are received
at other interfaces, and Ethernet’s CDMA/CD protocol nicely solves the multiple access
problem. Nodes simply attach to the cable, and voila, we have a local area network!
Up until this point, we have been purposefully vague about what a switch actually
does and how it works. The role of the switch is to receive incoming link-layer frames
and forward them onto outgoing links; we’ll study this forwarding function in detail in
this subsection. We’ll see that the switch itself is transparent to the hosts and routers in
the subnet; that is, a host/router addresses a frame to another host/router (rather than
addressing the frame to the switch) and happily sends the frame into the LAN, unaware
that a switch will be receiving the frame and forwarding it. The rate at which frames
arrive to any one of the switch’s output interfaces may temporarily exceed the link
capacity of that interface. To accommodate this problem, switch output interfaces have
buffers, in much the same way that router output interfaces have buffers for datagrams.
Let’s now take a closer look at how switches operate.
e. Link Virtualization: A Network as a Link Layer
Because this concerns link-layer protocols, and given that we’re now nearing the
end, let’s reflect on how our understanding of the term link has evolved. We began this
by viewing the link as a physical wire connecting two communicating hosts. In studying
multiple access protocols, we saw that multiple hosts could be connected by a shared
wire and that the “wire” connecting the hosts could be radio spectra or other media. This
led us to consider the link a bit more abstractly as a channel, rather than as a wire. In our
study of Ethernet LANs, we saw that the interconnecting media could actually be a rather
complex switched infrastructure. Throughout this evolution, however, the hosts
themselves maintained the view that the interconnecting medium was simply a link-layer
channel connecting two or more hosts. We saw, for example, that an Ethernet host can be
blissfully unaware of whether it is connected to other LAN hosts by a single short LAN
segment or by a geographically dispersed switched LAN or by a VLAN.
In the case of a dialup modem connection between two hosts, the link connecting
the two hosts is actually the telephone network—a logically separate, global
telecommunications network with its own switches, links, and protocol stacks for data
transfer and signaling. From the Internet link-layer point of view, however, the dial-up
connection through the telephone network is viewed as a simple “wire.” In this sense, the
Internet virtualizes the telephone network, viewing the telephone network as a link-layer
technology providing link-layer connectivity between two Internet hosts. You may recall
from our discussion of overlay networks that an overlay network similarly views the
Internet as a means for providing connectivity between overlay nodes, seeking to overlay
the Internet in the same way that the Internet overlays the telephone network.
Multiprotocol Label Switching (MPLS) evolved from a number of industry efforts
in the mid-to-late 1990s to improve the forwarding speed of IP routers by adopting a key
concept from the world of virtual-circuit networks: a fixed-length label. The goal was not
to abandon the destination-based IP datagram-forwarding infrastructure for one based on
fixed-length labels and virtual circuits, but to augment it by selectively labeling
datagrams and allowing routers to forward datagrams based on fixed-length labels (rather
than destination IP addresses) when possible. Importantly, these techniques work hand-
in-hand with IP, using IP addressing and routing. The IETF unified these efforts in the
MPLS protocol [RFC 3031, RFC 3032], effectively blending VC techniques into a routed
datagram network.
f. Data Center Networking
Internet companies such as Google, Microsoft, Amazon, and Alibaba have built
massive data centers, each housing tens to hundreds of thousands of hosts. As briefly
discussed in the sidebar in, data centers are not only connected to the Internet, but also
internally include complex computer networks, called data center networks, which
interconnect their internal hosts. In this section, we provide a brief introduction to data
center networking for cloud applications. Broadly speaking, data centers serve three
purposes. First, they provide content such as Web pages, search results, e-mail, or
streaming video to users. Second, they serve as massively-parallel computing
infrastructures for specific data processing tasks, such as distributed index computations
for search engines. Third, they provide cloud computing to other companies. Indeed,
today a major trend in computing is for companies to use a cloud provider such as
Amazon Web Services, Microsoft Azure, and Alibaba Cloud to handle essentially all of
their IT needs.
Data center designs are carefully kept company secrets, as they often provide
critical competitive advantages to leading cloud computing companies. The cost of a
large data center is huge, exceeding $12 million per month for a 100,000 host data center
in 2009 [Greenberg 2009a]. Of these costs, about 45 percent can be attributed to the hosts
themselves (which need to be replaced every 3–4 years); 25 percent to infrastructure,
including transformers, uninterruptable power supplies (UPS) systems, generators for
long-term outages, and cooling systems; 15 percent for electric utility costs for the power
draw; and 15 percent for networking, including network gear (switches, routers, and load
balancers), external links, and transit traffic costs. (In these percentages, costs for
equipment are amortized so that a common cost metric is applied for one-time purchases
and ongoing expenses such as power.) While networking is not the largest cost,
networking innovation is the key to reducing overall cost and maximizing performance
[Greenberg 2009a].
The worker bees in a data center are the hosts. The hosts in data centers, called
blades and resembling pizza boxes, are generally commodity hosts that include CPU,
memory, and disk storage. The hosts are stacked in racks, with each rack typically having
20 to 40 blades. At the top of each rack, there is a switch, aptly named the Top of Rack
(TOR) switch, that interconnects the hosts in the rack with each other and with other
switches in the data center. Specifically, each host in the rack has a network interface that
connects to its TOR switch, and each TOR switch has additional ports that can be
connected to other switches. Today, hosts typically have 40 Gbps or 100 Gbps Ethernet
connections to their TOR switches [FB 2019; Greenberg 2015; Roy 2015; Singh 2015].
Each host is also assigned its own data-centerinternal IP address.
The data center network supports two types of traffic: traffic flowing between
external clients and internal hosts and traffic flowing between internal hosts. To handle
flows between external clients and internal hosts, the data center network includes one or
more border routers, connecting the data center network to the public Internet. The data
center network therefore interconnects the racks with each other and connects the racks to
the border routers. Data center network design, the art of designing the interconnection
network and protocols that connect the racks with each other and with the border routers,
has become an important branch of computer networking research in recent years. (See
references in this section.)
For a small data center housing only a few thousand hosts, a simple network
consisting of a border router, a load balancer, and a few tens of racks all interconnected
by a single Ethernet switch could possibly suffice. But to scale to tens to hundreds of
thousands of hosts, a data center often employs a hierarchy of routers and switches, such
as the topology. At the top of the hierarchy, the border router connects to access routers
(only two, but there can be many more). Below each access router, there are three tiers of
switches. Each access router connects to a top-tier switch, and each top-tier switch
connects to multiple second-tier switches and a load balancer. Each second-tier switch in
turn connects to multiple racks via the racks’ TOR switches (third-tier switches). All
links typically use Ethernet for their link-layer and physical-layer protocols, with a mix of
copper and fiber cabling. With such a hierarchical design, it is possible to scale a data
center to hundreds of thousands of hosts.
Because it is critical for a cloud application provider to continually provide
applications with high availability, data centers also include redundant network
equipment and redundant links in their designs. For example, each TOR switch can
connect to two tier-2 switches, and each access router, tier-1 switch, and tier-2 switch can
be duplicated and integrated into the design [Cisco 2012; Greenberg 2009b]. In the
hierarchical design , observe that the hosts below each access router form a single subnet.
In order to localize ARP broadcast traffic, each of these subnets is further partitioned into
smaller VLAN subnets, each comprising a few hundred hosts [Greenberg 2009a].
In order to reduce the cost of data centers, and at the same time improve their
delay and throughput performance, as well as ease of expansion and deployment, Internet
cloud giants are continually deploying new data center network designs. Although some
of these designs are proprietary, others (e.g., [FB 2019]) are explicitly open or described
in the open literature (e.g., [Greenberg 2009b; Singh 2015]). Many important trends can
thus be identified.
The data center interconnection network is comprised of a large number of
smallsized switches. For example, in Google’s Jupiter datacenter fabric, one
configuration has 48 links between the ToR switch and its servers below, and connections
figuretier-1 switches [Singh 2015]. In Facebook’s data center architecture, each ToR
switch connects up to four different tier-2 switches (each in a different “spline plane”),
and each tier-2 switch connects up to 4 of the 48 tier-1 switches in its spline plane; there
are four spline planes. Tier-1 and tier-2 switches connect down to a larger, scalable
number of tier-2 or ToR switches, respectively, below [FB 2019]. For some of the largest
data center operators, these switches are being built in-house from commodity, off-the-
shelf, merchant silicon [Greenberg 2009b; Roy 2015; Singh 2015] rather than being
purchased from switch vendors.
A multi-switch layered (tiered, multistage) interconnection network such as and
as implemented in the data center architectures discussed above is known as Clos
networks, named after Charles Clos, who studied such networks [Clos 1953] in the
context of telephony switching. Since then, a rich theory of Clos networks has been
developed, finding additional use in data center networking and in multiprocessor
interconnection networks.
