Chapter 3: The Data Link Layer
3.1 Data Link Layer Design Issues
-The data link layer uses the services of the physical layer to send and receive bits over communication
channels. It has a number of functions such as providing a well defined service interface to the network
layer, dealing with transmission errors, and regulating the flow of data so that slow receivers are not
swamped by fast senders.
Frames: the data link layer takes the packets it gets from the network layer and encapsulates them into
frames for transmission. Each frame contains a frame header, a payload field for holding the packet, and
a frame trailer. Frame management forms the heart of what the data link does.
3.1.1: Services Provided to the Network Layer
Unacknowledged Connectionless Service: consists of having the source machine send independent
frames to the destination machine without have the destination machine acknowledge them. Ethernet
is an example. No logical connection is established beforehand or afterward. If a frame is lose due to
noise on the line, no attempt is made to detect the loss or recover from it in the data link layer. This is
appropriate when the error rate is very low, so recovery is left to higher layers.
Acknowledged Connectionless Service: there are no logical connections used; each frame sent is
individually acknowledged. The sender knows whether a frame has arrived correctly or has been lost. It
if has not arrived within a specified time interval, it can be sent again. (Good for using in unreliable
networks such as WiFi)
Connection Oriented Service: the source and destination machines establish a connection before any
data are transferred. Each frame sent over the connection is numbered, and it guarantees that each
frame is received exactly once and that all frames are received in the right order. It this provides the
network layer processes with the equivalent of a reliable bit stream.
First Phase: connection is established by having both sides initialize variables and counters
needed to keep track of which frames have been received and which ones have not.
Second Phase: one or more frames are actually transmitted
Third Phase: the connection is released, freeing up the variables, buffers, and other resources
used to maintain the connection
-What the physical layer does is accept a raw bit stream and attempt to deliver it to the destination. If
the channel is noisy, the physical layer will add some redundancy to its signals to reduce the bit error
rate to a tolerable level. However, the bit stream received by the data link later is not guaranteed to be
error free. Some bits have different values and the numbers of bits received may be out of order.
-The usual approach is for the data link layer to break up the bit stream into discrete frames, compute a
short token called a checksum for each frame, and include the checksum in the frame when it is
transmitted. When a frame arrives at the destination, the checksum is recomputed. If the newly
computed checksum is different from the one contained in the frame, the data link layers knows that an
error has occurred.
Four Methods of Breaking up Bit Streams
1: Byte Count
-use a field in the header to specify the number of bytes in the frame. When the data link layer at the
destination sees the byte count, it knows how many byes follow and hence where the frame ends. The
disadvantages are that the count can be garbled by transmission errors.
2: Flag Bytes with Byte Stuffing
-gets around the problem of resynchronization after an error by having each frame start and end with
special bytes. Often the same byte, called the flag byte, is used as both the starting and ending delimiter.
The disadvantages are that it may happen that the flag byte occurs in the data; this situation would
interfere with the framing.
Byte Stuffing: The solution is to have the sender’s data link layer insert a special escape byte (ESC) just
before each “accidental” flag byte in the data. Thus, a framing flag byte can be distinguished from one in
the data by the absence or presence of an escape byte before it. The data link layer on the receiving end
moves the escape byte before giving data to the network layer.
3: Flag Bits with Bit Stuffing
-framing can also be done at a bit level, so frames can contain an arbitrary number of bits made up of
units of any size. Each frame begins and ends with a special bit pattern, 01111110 or 07E in hexadecimal.
This pattern is a flag byte.
Bit Stuffing: whenever the sender’s data link layer encounters five consecutive 1’s in the data, it
automatically stuffs a 0 bit into the outgoing stream. When the receiver sees five consecutive incoming
1 bits, following by a 0 bit, it automatically destuffs (delete) the 0 bit.
-With bit stuffing, the boundary between two frames can be unambiguously recognized by the flag
pattern. Thus, if the receiver loses track of where it is, all it has to do is scan the input for flag sequences,
since they can only occur at frame boundaries and never within data.
Disadvantages of Byte/Bit Stuffing: the length of a frame now depends on the contents of the data it
4: Physical Layer Coding Violations
-use the short cut from the physical layer by using some reserved signals to indicate the start and end of
frames because encoding bits as signals often includes redundancy to help the receiver. This redundancy
means that some signals will not occur in regular data.
3.1.3: Error Control
-The usual way to ensure reliable delivery is to provide the sender with some feedback about what is
happening at the other end of the line. Typically, the protocol calls for the receiver to send back special
control frames bearing positive or negative acknowledgements about the incoming frames.
Complication: comes from the possibility that hardware troubles may cause a frame to vanish
completely (noise burst). The receiver will not react at all, since it has no reason to
Solution: dealt with by introducing times into the data link layer. When the sender transmits a frame, it
generally also starts a timer. The timer is set to expire after an interval long enough for the frame to
reach the destination, be processed, and have the acknowledgement propagate back to the sender. If it
gets there on time, the timer will be cancelled. However, if either the frame or the acknowledgement is
lost, the time will go off, alerting the sender to a potential problem. If you transmit the frame again,
there is a danger that the receiver will accept the same frame two or more times and pass it to the