UNIT-II

The Data Link Layer

 The Data Link Layer

Data-Link Layer has responsibility of transferring

frames from one node to adjacent node over a
link
The data link layer takes the packets it gets from
the network layer and encapsulates them into
frames for transmission .
Each frame contains frame header ,a payload
field for holding the packet ,and a frame trailer

2
 3.1 Data Link Layer design issues

Services Provided to the Network Layer

Framing
Error Control
Flow Control

3
 3.1 Data Link Layer Design Issues
Functions of Data Link Layer

Providing a well-defined service interface to the

network layer
Determining how the bits of the physical layer
are grouped into frames
Dealing with transmission errors
Regulating the flow of frames so that slow
receivers are not swamped by fast senders

4
3.1 Data Link Layer Design Issues

Relationship between packets and frames

5
3.1 Data Link Layer Design Issues
3.1.1 Services Provided to the Network layer

Model
used

6
 3.1 Data Link Layer Design Issues
3.1.1 Services Provided to the Network layer

Three reasonable possibilities for data link services:

1. Unacknowledged connectionless service

2. Acknowledged connectionless service
3. Acknowledged connection-oriented service

7
 3.1 Data Link Layer Design Issues
3.1.1 Services Provided to the Network layer
Unacknowledged connectionless service
1. The source sends independent frames to the
destination without the destination acknowledging
them.
2. No connection is established beforehand or
released afterward
3. If a frame is lost due to noise on the line, no
attempt is made to recover it in the data link layer
4. Appropriate when the error rate is very low
5. Appropriate for real-time traffic, such as speech, in
which late data are worse than bad data
6. Most LANs use unacknowledged connectionless 8

service
 3.1 Data Link Layer Design Issues
3.1.1 Services Provided to the Network layer
Acknowledged connectionless service
Each frame sent is individually acknowledged. In
this way, the sender knows whether or not a
frame has arrived safely. If it has not arrived
within a specified time interval, it can be sent
again
It is perhaps worth emphasizing that providing
acknowledgements in the data link layer is just
an optimization, never a requirement. The
transport layer can always send a message and
wait for it to be acknowledged
9
 3.1 Data Link Layer Design Issues
3.1.1 Services Provided to the Network layer
Acknowledged connectionless service
The trouble with this strategy is that if the
average message is broken up into, say, 10
frames, and 20 percent of all frames are lost, it
may take a very long time for the message to get
through. If individual frames are acknowledged
and retransmitted, entire messages get through
much faster
On reliable channels, such as fiber, the
overhead of a heavyweight data link protocol
may be unnecessary, but on wireless channels it
is well worth the cost due to their inherent
unreliability
10
 3.1 Data Link Layer Design Issues
3.1.1 Services Provided to the Network layer
Acknowledged connection-oriented service
1. The source and the destination establish a
connection before and data are transferred
2. Each frame sent over the connection is numbered
3. The data link layer guarantees that each frame
sent is indeed received
4. Furthermore, it guarantees that each frame is
received exactly once and that all frames are
received in the right order
5. Connection-oriented service provides the network
layer with the equivalent of a reliable bit stream
11
 3.1 Data Link Layer Design Issues
3.1.2 Framing
The data link uses the services provided by the
physical layer. The physical layer will not be perfect.
It is up to the data link layer to detect, and if
necessary, correct errors
The usual approach is for the data link layer to
break the bit stream up into discrete frames and
compute the checksum for each frame. 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 layer knows that an error has occurred and12

takes steps to deal with it

 3.1 Data Link Layer Design Issues
3.1.2 Framing: The usual approach is for the data link
layer to break the bit stream up into discrete frames
and compute the checksum for each frame
Breaking the bit stream up into frames is more difficult
than it at first appears, One way to achieve this framing
is to insert time gaps between frames, much like the
spaces between words in ordinary text
Four framing methods are used :
1. Character count
2. Starting and ending characters, with
character stuffing
3. Starting and ending flags, with bit stuffing
4. Physical layer coding violations
13
3.1 Data Link Layer Design Issues
3.1.2 Framing: Character count

Without error

With one error

14
3.1 Data Link Layer Design Issues
3.1.2 Framing: Character count
The first framing method uses a field in the
header to specify the number of characters in
the frame
When the data link layer in the destination sees
the character count ,it knows how many
characters follow and hence where the end of
the frame is
Even if the checksum is incorrect so the
destination knows that the frame is bad, it still
has no way of telling where the next frame starts
The trouble with this algorithm is that the count
can be garbled by a transmission error
15
3.1 Data Link Layer Design Issues
3.1.2 Framing: Starting and ending characters,
with Character stuffing

a) A frame delimited by flag bytes b) Four examples of

byte sequences before and after byte stuffing
16
3.1 Data Link Layer Design Issues
3.1.2 Framing: Starting and ending characters,
with Character stuffing
Most protocols used the same byte ,called flag
byte, as both the starting and ending delimiter as
FLAG.
Two consecutive flag bytes indicate the end of
one frame and start of the next one
A major disadvantage of using this framing
method is that it is closely tied to 8-bit characters
in general and the ASCII character code in
particular
We need a technique to allow arbitrary sized
characters
17
3.1 Data Link Layer Design Issues
3.1.2 Framing: Starting and ending flags,
with Bit Stuffing
This new technique allows data frames to contain
an arbitrary number of bits and allow character
codes with an arbitrary number of bits per character
Each frame begins and ends with a special bit
pattern,01111110 called a flag byte.
whenever the senders data link layer encounters
five consecutive ones in the data , it automatically
stuffs a 0 bit into the outgoing bit stream.
whenever the receiver sees five consecutive
incoming 1 bits, followed by a 0 bit ,it automatically
destuffs (i.e deletes) the 0 bit.
18
3.1 Data Link Layer Design Issues
3.1.2 Framing: Starting and ending flags,
with Bit Stuffing
Flags (01111110) at the beginning and end

Bit-oriented framing with bit stuffing

19
3.1 Data Link Layer Design Issues
3.1.2 Framing: Physical layer coding violations

This method of framing is only applicable to

networks in which the encoding on the physical
medium contains some redundancy
For example, some LANs encode 1 bit of data
by using 2 physical bits. Normally, a 1 bit is a
high-low pair and a 0 bit is a low-high pair. The
combinations high-high and low-low are not
used for data and they can be used as frame
boundaries
20
3.1 Data Link Layer Design Issues
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
Data Frame

Sender Receiver
Acknowledgement (ACK)

Or negative
Acknowledgement (NAK)

21
3.1 Data Link Layer Design Issues
3.1.3 Error Control
An additional complication comes from the
possibility that hardware troubles may cause a
frame to vanish completely. In this case, the
receiver will not react at all
This possibility is dealt with by introducing timers
into the data link layer
When a 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 there ,and have the acknowledgement
to propagate back to the sender 22
3.1 Data Link Layer Design Issues
3.1.3 Error Control
However, when frames may be transmitted
multiple times there is a danger that the receiver
will accept the same frame two or more times,
and pass it to the network layer more than once
To prevent this from happening, it is generally
necessary to assign sequence numbers to
outgoing frames, so that the receiver can
distinguish retransmissions from originals

23
3.1 Data Link Layer Design Issues
3.1.4 Flow Control
When the sender is running on a fast (or lightly
loaded) computer and the receiver is running on
a slow (or heavily loaded machine) and what to
do with a sender that systematically wants to
transmit frames faster than the receiver can
accept them?
Even if the transmission is error free ,at a
certain point the receiver will simply be unable to
handle the frames as they arrive and will start to
loose someone
To prevent this situation, Feedback- based flow
control mechanism is used
24
3.1 Data Link Layer Design Issues
3.1.4 Flow Control
Feedback- based flow control ,the receiver
sends back information to the sender giving it
permission to send more data
Various flow control schemes are known, but
most of them use the same basic principle. The
protocol contains well-defined rules about when
a sender may transmit the next frame
These rules often prohibit frames from being
sent until the receiver has granted permission,
either implicitly or explicitly
25
 3.2 Error Detection and Correction
In some cases it is sufficient to detect an error
and in some, it requires the errors to be
corrected also
For e.g.
On a reliable medium : Error Detection is
sufficient where the error rate is low and asking
for retransmission after Error Detection would
work efficiently
In contrast, on an unreliable medium :
Retransmission after Error Detection may result
in another error and still another and so on.
Hence Error Correction is desirable
26
 3.2.1 Error Correcting codes
A frame consists of m data (i.e., message ) bits
and r redundant, or check bits
Let the total length be n (i.e., n=m+r). an n-bit unit
containing data and check bits is often referred to
as an n-bit codeword
Given any two code words ,say,10001001 and
10110001,it is possible to define how many bits
differ .In this case 3 bits differ. To determine how
many bits differ ,just EXCLUSIVE OR the two
code words ,and count the number of 1 bits in the
result. The number of bit positions in which two
code words differ is called the Hamming distance
Its significance is that if two code words are a
hamming distance d apart, it will require d single-
bit errors to convert one into another
27
 3.2.1 Error Correcting codes

To detect d errors, you need a distance d+1

code
To correct d errors, you need a distance 2d+1
code
Consider a code with only 4 valid codewords:
0000000000, 0000011111, 1111100000,
1111111111
This code has a distance of 5, which means that
it can detect double errors
28
 3.2.1 Error Correcting codes
A simple example an error-detecting code,
consider a code in which a single parity bit is
appended to the data
The parity bit is chosen so that the number of 1
bits in the codeword is even (or odd)
For example, when 10110101 is sent in even
parity by adding a bit at the end ,it becomes
101101011,where as 10110001 becomes
101100010 with even parity
A code word with a single parity bit has a
distance 2,since any single bit error produces a
codeword with the wrong parity
29
 3.2.1 Hamming code
In data communication, hamming code
is an error-correcting code named after its
inventor, Richard Hamming
Hamming codes can detect single and up to 3
bits error, and correct single-bit error as well.

30
3.2.1 Error Correcting codes: Hamming
Code

m data bits r check bits

n=m+r
Each of the 2m legal messages has n illegal codewords at a
distance 1 from it.
Thus each of the 2m legal messages requires n+1 bit patterns
dedicated to it.
Therefore, ( n 1) 2 m
2 n

( m r 1) 2 m 2 m r
( m r 1) 2 r
31
3.2.1 Error Correcting codes: Hamming
Code

32
Error Correcting codes: Hamming Code

33
Error Correcting codes: Hamming Code

34
Example of Hamming Code

35
Hamming Code: Single-bit error

36
Hamming Code: Single-bit error

37
3.2.1 Error Correcting codes: A 1-bit error
correcting code (Hamming Code)
Given m, this puts a lower limit on the number
of check bits needed to correct single errors
This theoretical lower limit can, in fact, be
achieved using a method due to Hamming

The bits of code words are numbered

consecutively, starting with bit 1 at the left end.
The bits that are power of 2 (1, 2, 4, 8, ) are
check bits. The rest are filled up with the data
bits. Each check bit forces the parity of some
collection of bits, including itself, to be even (or
odd)
38
3.2.1 Error Correcting codes: 1-bit error
correcting code (Hamming Code)
Consider the example, m= 1101110

11 10 9 8 7 6 5 4 3 2 1

1 1 0 r 1 1 1 r 0 r r

39
 3.2.1 Error Correcting codes: Hamming
Code
A bit may be included in several parity computations. To
see which check bits the data bit in position k contributes
to, rewrite k as a sum of powers of 2.
For example, 11= 1+2+8 and 29= 1+4+8+16. A bit is
checked by just those check bits occurring in its
expansion( e.g., bit 11 is checked by bits 1,2 and 8)
When a codeword arrives, the receiver initializes a
counter to zero. It then examines each check bit, k, to
see if it has the correct parity. If not, it adds k to the
counter. If the counter is zero afterwards, the codeword
is accepted as valid. If the counter is nonzero, it contains
the number of the incorrect bit.
40
 3.2.1 Error Correcting codes: Hamming
Code
Hamming codes can correct only single errors. However
there is a trick that can be used to permit hamming
codes to correct burst errors
A sequence of k consecutive codewords are arranged in
as a matrix, one codeword per row
To correct burst errors, the data should be transmitted
one column at a time (normally one codeword at a time
from left to right), starting with the left most column
When the frame arrives at the receiver, the matrix is
reconstructed, one column at a time
If a burst error of length k occurs, at most one bit in each
of the codewords will have been affected, but the
hamming code can one error per codeword, so the entire
block can be restored
41
 3.2.2 Error-detecting Codes: CRC (Cyclic
Redundancy Code)
When the polynomial code method is employed
,the sender and receiver must agree upon a
generator polynomial G(x) .
In advance both higher and lower order bits of
generator must be 1.
To compute the check sum for some frame with
m bits ,corresponding to the polynomial M(x), the
frame must be longer than the generator
polynomial.
The idea is to append a checksum to the end of
the frame in such a way that the polynomial
represented by the check summed frame is
divisible by G(x).
When the receiver gets the check summed
frame, it tries dividing it by G(x). If there is a
42
remainder ,there has been a transmission error
 3.2.2 CRC : Algorithm for computing
checksum
1. Let r be the degree of G(x). Append r zero bits
to the low-order end of the frame ,so it now
contains m+r bits and corresponds to the
polynomial xrM(x)
2. Divide the bit string corresponding to G(x) in to
the bit string corresponding to XrM(x) using
modulo 2 division
3. subtract the remainder (which is always r or
fewer bits ) from the bit string correspond to
XrM(x) using modulo 2 subtraction. The result is
the check summed frame to be transmitted .call
its polynomial T(x)
43
Calculation of the polynomial code checksum

Frame: 1001 Generator : 1011

44
Division in the CRC decoder for two cases

45
 DLL DESIGN ISSUES: FLOW CONTROL
3.3 Elementary Data Link Protocols
3.3.1 An Unrestricted Simplex Protocol

46
3.3.2 A Simplex Stop-and-Wait Protocol

47
3.3.3 A Simplex Protocol for Noisy Channel

Protocols in which the sender waits for a positive

acknowledgement before advancing to the next data
item are often called PAR (Positive Acknowledgement
with Retransmission) or ARQ (Automatic Repeat
reQuest).

Although it can handle lost frames by timing out, it

requires the timeout interval to be long enough to
prevent premature timeouts. If the sender times out
early, while the acknowledgement is still on the way, it
will send a duplicate.

48
 3.4 Sliding Window Protocols

Full-duplex operation: data and acknowledgements are

bi-directional and intermixed

Piggybacking: The technique of temporarily delaying

outgoing acknowledgements so that they can be hooked
onto the next outgoing data frame.

The principal advantage of using piggybacking over having

distinct acknowledgement frames is a better use of the
available channel bandwidth (because it saves the
overhead of a distinct frame).

49
 3.4 Sliding Window Protocols

However, piggybacking introduces a complication not

present with separate acknowledgements. How long should
the data link layer wait for a packet onto which to piggyback
the acknowledgements?

If the data link layer waits longer than the senders timeout
period, the frame will be retransmitted, defeating the whole
purpose of having acknowledgements.

Resort to some ad hoc schemes, such as waiting for a

fixed number of milliseconds.

50
 3.4 Sliding Window Protocols

The ultimate purpose: To design a protocol that remained

synchronized in the face of any combination of garbled
frames, lost frames, and premature timeouts.

Sliding window protocols: The essence of all sliding window

protocols is that at any instant of time, the sender maintains
a set of sequence numbers corresponding to frames it is
permitted to send. These frames are said to fall within the
sending window.

Similarly, the receiver also maintains a receiving window

corresponding to the set of frames it is permitted to accept.

51
 3.4 Sliding Window Protocols

The senders window and the receivers window need not

have the same lower and upper limits, or even have the
same size. In some protocols they are fixed in size, but in
others they can grow or shrink as frames are sent and
received.
The sequence numbers within the senders window
represent frames sent but as yet not acknowledged.
Whenever a new packet arrives from the network layer, it is
given the next higher sequence number, and the upper edge
of the window is advanced by one. When an
acknowledgement comes in, the lower edge is advanced by
one. In this way the window continuously maintains a list of
unacknowledged frames.
52
3.4 Sliding Window Protocols

A sliding window of
size 1 with 3-bit
sequence number.
(a) Initially
(b) After the first frame
has been sent.

53
3.4 Sliding Window Protocols

A sliding window of
size 1 with 3-bit
sequence number.

(c) After the first frame

has been received.

(d) After the first

acknowledgement
has been received.

54
 3.4 Sliding Window Protocols

Since frames currently within the senders window may

ultimately be lost or damaged in transmit, the sender must
keep all these frames in its memory for possible
retransmission.

Thus if the maximum window size is n, the senders need n

buffers to hold the unacknowledged frames.

If the window ever grows to its maximum size, the sending

data link layer must forcibly shut off the network layer until
another buffer becomes free.

55
 3.4 Sliding Window Protocols

The receiving data link layers window corresponds to the

frames it may accept. Any frame falling outside the window
is discarded without comment.
When a frame whose sequence number is equal to the lower
edge of the window is received, it is passed to the network
layer, an acknowledgement is generated, and the window is
rotated by one.

Unlike the senders window, the receivers window always

remains at its initial size. Note that a window size of 1 means
that the data link layer only accepts frames in order, but for
larger windows this is not so.

The network layer, in contrast, is always fed data in the

proper order, regardless of the data link layers window size.
56
 3.4 Sliding Window Protocols

3.4.1 A One Bit Sliding Window Protocol

normal scenario

sender 0 1 0 1

receiver

ACK0 ACK1 ACK0 ACK1 Stop-and-Wait
protocol
sender time-out

sender 0 1 time-out1 0 ignored

receiver
ACK0 ACK1 ACK1 ACK0
57
 3.4 Sliding Window Protocols

3.4.1 A One Bit Sliding Window Protocol

ACK lost or corrupted

sender 0 1 time-out1 0

receiver
ACK0 ACK1 ACK1 ACK0
Packet lost or corrupted

sender 0 1 time-out1 0

NAK

receiver
ACK0 ACK1 ACK0
NAK can be used here to speed up processing.
58
 3.4.1 A One Bit Sliding Window Protocol

A normal
scenario

(seq, ack, packet number)

An asterisk indicates where a network layer accepts a packet 59
 3.4.2 A Protocol Using Go Back n

The technique of pipelining: Filling the pipe with frames

For example, in the last satellite example, if the senders

window size is 26, after sending the 26th frame (at time
520 msec), the acknowledgement of the first frame will
be back. The 27th frame can be sent now without any
idle time in the sender.

60
 3.4.2 A Protocol Using Go Back n

Pipelining frames over an unreliable channel raises some

serious issues. First, what happens if a frame in the
middle of a long stream is damaged or lost. What should
the receiver do with all the correct frames following it?
Two approaches:
go back n: the receiver discards all frames (the receiver
has a window of size 1)

selective repeat: buffer all the correct frames

61
3.4.2 A Protocol Using Go Back n

Go Back n

62
 3.4.2 Selective Repeat

Selective Repeat

63
 Example data Link Protocols: High-level
Data Link Control(HDLC)
HDLC was defined by ISO for use on both point-to-point
and multipoint data links.
It supports full-duplex communication
Most widely used DLC protocol
Other similar protocols are
Synchronous Data Link Control (SDLC) by IBM
Advanced Data Communication Control Procedure
(ADCCP) by ANSI
Link Access Procedure, Balanced (LAP-B) by CCITT,
as part of its X.25 packet-switched network standard

64
 HDLC overview

Broadly HDLC features are as follows:

Reliable protocol
selective repeat or go-back-N
Full-duplex communication
receive and transmit at the same time
Bit-oriented protocol
use bits to stuff flags occurring in data
Flow control
adjust window size based on receiver capability
Uses physical layer clocking and synchronization to send
and receive frames

65
 HDLC overview

Defines three types of stations

Primary
Secondary
Combined
Defines three types of data transfer mode
Normal Response mode
Asynchronous Response mode
Asynchronous Balanced mode
Three types of frames
Unnumbered
information
Supervisory
66
 HDLC

The three stations are :

Primary station
Has the responsibility of controlling the operation of data flow
the link.
Handles error recovery
Frames issued by the primary station are called commands.
Secondary station,
Operates under the control of the primary station.
Frames issued by a secondary station are called responses.
The primary station maintains a separate logical link with
each secondary station.
Combined station,
Acts as both as primary and secondary station.
Does not rely on other for sending data

67
 HDLC

Unbalanced Mode

Commands
Primary
Responses

Secondary Secondary

Balanced mode

Combined Combined
commands/Responses
68
 HDLC

The three modes of data transfer operations are

Normal Response Mode (NRM)
Mainly used in terminal-mainframe networks. In this case,
Secondaries (terminals) can only transmit when specifically
instructed by the primary station in response to a polling
Unbalanced configuration, good for multi-point links
Asynchronous Response Mode (ARM)
Same as NRM except that the secondaries can initiate
transmissions without direct polling from the primary station
Reduces overhead as no frames need to be sent to allow
secondary nodes to transmit
Transmission proceeds when channel is detected idle , used
mostly in point-to-point-links
Asynchronous Balanced Mode (ABM)
Mainly used in point-to-point links, for communication
between combined stations

69
HDLC frame structure
(a) Frame
Format

(b) Control
field
format

70
 HDLC

There are three different classes of frames used in

HDLC
Unnumbered frames, used in link setup and
disconnection, and hence do not contain ACK.
Information frames, which carry actual information.
Such frames can piggyback ACK in case of ABM
Supervisory frames, which are used for error and flow
control purposes and hence contain send and receive
sequence numbers

71
3.6.2 The Data Link Layer in the Internet

72
 PPP (Point-to-Point Protocol)
PPP handles error detection, supports multiple protocols (not just
IP), allows IP addresses to be negotiated at connection time, permits
authentication, and has many other features.
PPP provides three things:

1. A framing method that unambiguously delineates the end of one

frame and the start of the next one. The frame format also
handles error detection.
2. A link control protocol for bringing lines up, testing them,
negotiating options, and bring them down again gracefully when
they are no longer needed. The protocol is called LCP (Link
Control Protocol).
3. A way to negotiate network-layer options in a way that is
independent of the network layer protocol to be used. The method
chosen is to have a different NCP (Network Control Protocol)
for each network layer supported.
73
PPP frame format

74