5.1 The Data Link Layer: Introduction, Services
In the previous chapter we learned that the network layer provides a communication
service between two hosts. As shown in Figure 5.1-1, this communication
path starts at the source host, passes through a series of routers, and
ends at the destination host. We'll find it convenient here to refer
to the hosts and the routers simply as nodes (since, as we'll see
shortly, we will not be particularly concerned whether a node is a router
or a host), and to the communication channels that connect adjacent nodes
along the communication path as links. In order to move a datagram
from source host to destination host, the datagram must be moved over each
of the individual links in the path. In this chapter, we focus on
the data link layer, which is responsible for transferring a datagram
across an individual link. We'll first identify and study the services
provided by the link layer. In sections 5.2 through 5.4, we'll then
examine important principles behind the protocols that provide these services
(including the topics of error detection and correction, so-called
multiple access protocols that are used share a single physical link among
multiple nodes, and link-level addressing). We'll see that many different
types of link-level technology can be used to connect two nodes. In sections
5.5 through 5.10, we'll examine specific link-level architectures and protocols
in more detail.
Figure 5.1-1: TheData Link Layer
5.1.1 The Services Provided by the Link Layer
A link-layer protocol is used to move a datagram over an individual link.
The link-layer protocol defines the format of the packets exchanged
between the nodes at the ends of the link, as well as the actions taken
by these nodes when sending and receiving packets. Recall from Chapter
1 that the packets exchanged by a link-layer protocol are called frames,
and that each link-layer frame typically encapsulates one network-layer
datagram. As we shall see shortly, the actions taken by a link-layer protocol
when sending and receiving frames include error detection, retransmission,
flow control and random access. Examples of link-layer protocols include
Ethernet, token ring, FDDI, and PPP; in some contexts, ATM and frame
relay can be considered link-layer protocols as well. We will cover
these protocols in detail in the latter half of this chapter.
Whereas the network layer has the end-to-end job of moving transport-layer
segments from the source host to the destination host, a link-layer protocol
has the node-to-node job of moving a network-layer datagram over a single
link in the path. An important characteristic of the link layer
is that a datagram may be handled by different link-layer protocols on
the different links in the path. For example, a datagram may be handled
by Ethernet on the first link, PPP on the last link, and frame relay on
all intermediate links. It is important to note that the services
provided by the different link-layer protocols may be different. For example,
a link-layer protocol may or may not provide reliable delivery. Thus, the
network layer must be able to accomplish its end-to-end job in the face
of a varying set of individual link-layer services.
In order to gain insight to 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 tr for a tourist traveling from Princeton, New
Jersey to Lausanne, Switzerland. Suppose 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 airport,
and finally a train from Geneva to Lausanne's train station. (There is
a train station at Geneva's airport.) Once the 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 responsibility
of the Swiss train service to get the tourist from the 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 entirely different 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. This service is used by the travel agent
to plan the tourist's trip. In this transportation analogy, the tourist
is analogous to a datagram, each transportation segment is analogous to
a communication link, the transportation mode is analogous to the link-layer
protocol, and the travel agent who plans the trip is analogous to a routing
protocol.
The basic service of the link layer is to "move" a datagram from one
node to an adjacent node over a single communication link. But the details
of the link-layer service depend on the specific link-layer protocol that
is employed over the link. Possible services that can be offered by a link-layer
protocol include:
-
Framing and link access: Almost all link-layer protocols encapsulate
each network-layer datagram within a link-layer frame before transmission
onto the link. A frame consists of a data field, in which the network-layer
datagram is inserted, and a number of header fields. (A frame may also
include trailer fields; however, we will refer to both header and trailer
fields as header fields.) A data link protocol specifies the structure
of the frame, as well as a channel access protocol that specifies the rules
by which a frame is transmitted onto the link. For point-to-point
links that have a single sender on one end of the link and a single receiver
at the other end of the link, the link access protocol is simple (or non-existent)
- 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 channel access
protocol serves to coordinate the frame transmissions of the many nodes;
we cover multiple access protocols in detail in section 5.3 . We'll
see several different frame formats when we examine specific link-layer
protocols in the second half of this chapter. In section 5.3, we'll see
that frame headers also often include fields for a node's so-called
physical address, which is completely distinct from
the node's network layer (e.g., IP) address.
-
Reliable delivery: If a link-layer protocol provides the reliable-delivery
service, then it guarantees to move each network-layer datagram across
the link without error. Recall that transport-layer protocols (such as
TCP) may also provide a reliable-delivery service. Similar to a transport-layer
reliable-delivery service, a link-layer reliable-delivery service is achieved
with acknowledgments and retransmissions (see Section 3.4). 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 at which the error occurs, rather than forcing an
end-to-end retransmission of the data by transport- or application-layer
protocol. However, link-layer reliable delivery is often considered to
be unnecessary overhead for low bit-error links, including fiber, coax
and many twisted-pair copper links. For this reason, many of the most popular
link-layer protocols do not provide a reliable-delivery service.
-
Flow control: The nodes on each side of a link have a limited amount
of packet buffering capacity. This is a potential problem, as a receiving
node may receive frames at a rate faster than it can process the frames
(over some time interval). Without flow control, the receiver's buffer
can overflow and frames can get lost. Similar to the transport layer, a
link-layer protocol can provide flow control in order to prevent the sending
node on one side of a link from overwhelming the receiving node on the
other side of the link.
-
Error detection: A node's receiver can incorrectly decide that a
bit in a frame to be a zero when it was transmitted as a one (and vice
versa). These 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 for a node to detect the
presence of one or more errors. This is done by having the transmitting
node set error detection bits in the frame, and having the receiving node
perform an error check. Error detection is a very common service among
link-layer protocols. Recall from Chapters 3 and 4 that the transport layer
and network layers in the Internet also provide a limited form of error
detection. Error detection in the link layer is usually more sophisticated
and implemented in hardware.
-
Error correction: Error correction is similar to error detection,
except that a receiver can not only detect whether errors have been introduced
in the frame but can also determine exactly where in the frame the errors
have occurred (and hence correct these errors). Some protocols (such as
ATM) provide link-layer error correction for the packet header rather than
for the entire packet. We cover error detection and correction in section
5.2.
-
Half-Duplex and Full-Dulpex: With full-duplex transmission, both
nodes at the ends of a link may transmit packets at the same time. With
half-duplex transmission, a node cannot both transmit and receive at the
same time.
As noted above, many of the services provided by the link layer have strong
parallels with services provided at the transport layer. For example, both
the link layer and the transport layer can provide reliable delivery. Although
the mechanisms used to provide reliable delivery in the two layers are
similar (see Section 3.4), the two reliable delivery services are not the
same. A transport protocol provides reliable delivery between two processes
on an end-to-end basis; a reliable link-layer protocol provides the reliable-delivery
service between two nodes connected by a single link. Similarly, both link-layer
and transport-layer protocols can provide flow control and error detection;
again, flow control in a transport-layer protocol is provided on an end-to-end
basis, whereas it is provided in a link-layer protocol on a node-to-adjacent-node
basis.
5.1.2 Adapters Communicating
For a given communication link, the link-layer protocol is for the most
part implemented in a pair of adapters. An adapter is a board (or
a PCMCIA card) that typically contains RAM, DSP chips, a host bus interface
and a link interface. Adapters are also commonly known as network interface
cards or NICs. As shown in Figure 5.1-2, the network layer in
the transmitting node (i.e., a host or router) passes a network-layer datagram
to the adapter that handles the sending side of the communication link.
The adapter encapsulates the datagram in a frame and then transmits the
frame into the communication link. At the other side, the receiving adapter
receives the entire frame, extracts the network-layer datagram, and passes
it to the network layer. If the link-layer protocol provides error detection,
then it is the sending adapter that sets the error detection bits and it
is the receiving adapter that performs the error checking. If the link-layer
protocol provides reliable delivery, then the mechanisms for reliable delivery
(e.g., sequence numbers, timers and acknowledgments) are entirely implemented
in the adapters. If the link-layer protocol provides random access (see
Section 5.3), then the random access protocol is entirely implemented in
the adapters.
Figure 5.1-2: The link-layer protocol for a communication link
is implemented in the adapters at the two ends of the link. DG abbreviates
"datagram".
A computer in itself, an adapter is a semi-autonomous unit. For example,
an adapter can receive a frame, determine if a frame is in error and discard
the frame without notifying its "parent" node. An adapter that receives
a frame only interrupts its parent node when it wants to pass a network-layer
datagram up the protocol stack. Similarly, when a node passes a datagram
down the protocol stack to an adapter, the node fully delegates to the
adapter the task of transmitting the datagram across that link. On
the other hand, an adapter is not an completely autonomous unit. Although
we have shown the adapter as a separate "box" in Figure 5.3.1, the adapter
is typically housed in the same physical box as rest of the node, shares
power and busses with the rest of the node, and is ultimately under the
control of the node.
Figure 5.1-3: The adapter is a semi-autonomous unit.
As shown in Figure 5.1.3, the main components of an adapter are the
bus interface and the link interface. The bus interface is responsible
for communicating with the adapter's parent node. It sends to and receives
from the parent node network-layer datagrams and control information. The
link interface is responsible for implementing the link-layer protocol.
In addition to framing and de-framing datagrams, it may provide error detection,
random access and other link-layer functions. It also includes the transmit
and receive circuitry. For popular link-layer technologies, such as Ethernet,
the link interface is implemented by chip set that can be bought on the
commodity market. For this reason, Ethernet adapters are incredibly cheap
-- often less than $30 for 10 Mbps and 100 Mbps transmission rates.
Adapter design has become very sophisticated over the years. One of
the critical issues in adapter performance has always been whether the
adapter can move data in and out of a node at the full line speed, that
is, at the transmission rate of the link. You can learn more about adapter
architecture for 10Mbps Ethernet, 100 Mbps Ethernet and 155 Mbps ATM by
visiting the 3Com adapter page [3Com]. Data Communications
magazine provides a nice introduction to Gbps Ethernet adapters [GigaAdapter].
References
[3Com] 3Com Corporation, Network Interface
Cards, http://www.3com.com/products/nics.html
[GigaAdapter] Data Communications,
"Lan Gear," http://www.data.com/hot_products/lan_gear/alteon.html
Return
to Table of Contents
Copyright 1996-1999 James F. Kurose and Keith W. Ross