Unit 2:

Data Link Layer

Er. Vikas Goyal

A.P. (ECE department, PIET)
1
Data Link Layer
• Design Issues in Data link Layer
• Framing
• Error Detection and Correction
- Parity Check
- CRC
- Hamming Code
• Flow Control
- Sliding Window Protocols
• HDLC
• PPP

2
Data Link Layer
Design Issues :
The various services provided/Design Issues of Data link layer are :
1. Service Provided to the Network Layer
2. Framing
3. Error Detection and Correction
4. Flow Control

1. Service Provided to the Network Layer

• Data link layer provides three services to the network layer .
i) Un acknowledged Connectionless Service
ii) Acknowledged Connection less Service
iii) Acknowledged Connection Oriented Service

3
Data Link Layer
i ) Un acknowledged Connectionless Service
• Source sends independent frames to the destination with out any
acknowledgement .
• Not a reliable service .
• Used in the systems where error rate is low. Ex : LANS
ii ) Acknowledged Connectionless Service
• Source sends independent frames to the destination with an
acknowledgement .
• Reliable service .
• Used in Unreliable channels . Ex : Wireless Systems
iii ) Acknowledged Connection – Oriented Service
• Here source and destination establish a connection before any data is
transferred and send an acknowledgement to the source after receiving
each frame in order .
• Most reliable service and Used in more noisy channels. e.g. : Video
4
Data Link Layer
Framing :
• Grouping the bits together from the physical layer and constructing a
frame is called framing .
• The frames are created by the adding a header and trailer to the packet
which specify the source and destination addresses .
• Frames are used to perform the error detection and correction
operations .
• Framing is of two types :
1. Fixed size framing or static framing
- size of frame is fixed
- no need to specify the start of the frame .
2. Variable size framing or Dynamic
- Size of the frames changed .
- It is necessary to specify the start of each frame .
5
Data Link Layer
• Methods to Break the Bit Stream into Frames .
1. Character Count
2. Character Stuffing or Byte Stuffing
3. Bit Stuffing

Character Count
• Here a field in the header ,Specifies the number of characters in the
frame .
• Data link layer at the destination looks the character count and decide
the end of frame .
• The main draw back of this method is if any count is garbled by a
transmission error then the destination is unable to decide the frames .

6
Data Link Layer

Fig : Character Count a) With out Errors b) With Errors

7
Data Link Layer

Character Stuffing or Byte Stuffing

• In this method each frame starts with the ASCII character sequence
DLE STX and ends with DLE ETX .
• DLE STX and DLE ETX sequences are called frame boundaries .
• It is possible to occur DLESTX or DLEETX in the data ,which will
interfere the frame .
• To solve this problem the data link layer at ender side stuff an ASCII
DLE character just before each accidental DLE character in the data
.
• The Data link layer at receiving end removes this DLE before giving
the data to network layer .
• Disadvantage of this method is more overhead and each frame is
tied with 8 bit characters .

8
Data Link Layer

Fig : Character Stuffing

9
Data Link Layer
Bit Stuffing
• In this method each frame starts and ends with a special bit pattern like
01111110 called a flag byte .
• When the sender data link layer encounters a five consecutive ones in
the data it automatically stuffs a 0 bit into the out going bit stream .
• When the receiver sees five consecutive 1’s followed by a 0 bit it
automatically destuffs the 0 bit and send data to network layer

Fig: Bit Stuffing

10
Data Link Layer
Error Detection and Correction
• A reliable system must have the mechanism to detect and correct the
errors .
Types of Errors
• There are three types of Errors :
1. Single Bit
- one bit of a data unit is changed from 0 to 1 and 1 to 0.
Example :

11
Data Link Layer
2. Multiple Bit
- Two or more non consecutive bits in data unit have
changed from 1 to 0 or 0 to1 .
Example :

Fig : Multiple Bit Errors

12
Data Link Layer
3. Burst Errors
• Two or more consecutive bits in the data unit have changed from 1 to 0
and 0 to 1 .

Fig : Burst Errors

13
Data Link Layer
Error Detection
1. Redundancy
• To detect the errors we use a mechanism called redundancy.
• It involves the transmission of each data unit twice.
• Same data unit is not received twice in succession a transmission error
occurred .
• The disadvantage of this system is slow and if an error occurred at the
same position of both data units .
• To avoid the disadvantage of this method a shorter group of bits added
to the end of each data unit ,this technique is called redundancy
• Data unit is passed through a generating unit and it adds an appropriate
redundancy check bits .
• This data unit send to the receiver and receiver puts the entire stream
into a checking function .
• If there is no error data is accepted other wise rejected .
14
Data Link Layer

Fig : Redundancy
2. Exact –Count Encoding :
• The Number of 1’s in the data unit are same .
• In the destination side it count the number of 1’s received same or not
to determine the transmission error .
15
Data Link Layer
Error Correction
• Error correction can be handled in two ways :
1. When the error is discovered ,the receiver asks the sender to retransmit the
same data unit .
2. Receiver can use an error correcting codes to Detect and Correct the errors.
• There are different types of Error Detecting and correcting Techniques :
1. Parity Checker
2. Hamming Code
3. Cyclic Redundancy Check
1. Parity Checker
• It is the simplest technique for detecting and correcting errors.
• The MSB of an 8-bits word is used as the parity bit and the remaining 7 bits
are used as data or message bits.

16
Data Link Layer
• The parity of 8-bits transmitted word can be either even parity or odd
parity.
• Even parity : Even parity means the number of 1's in the given word
including the parity bit should be even (2,4,6,....).
• Odd parity : Odd parity means the number of 1's in the given word
including the parity bit should be odd (1,3,5,....).

17
Data Link Layer
Example :

Drawbacks
• It does not detect all types of errors .
• Not suitable for multiple bit errors .

18
Data Link Layer
2. Hamming Code
• Hamming code can be applied to data units of any length .
• Hamming code is used to detect and correct single bit errors .
• The distance between two words of the same size is called Hamming
distance.
Example :
• 1. The Hamming distance d(000, 011) is 2 because 000 +011 is 011
(two 1’s).
• 2. The Hamming distance d(10101, 11110) is 3 because 10101 +11110
is 01011 (three 1’s).

• To calculate the number of redundancy bits (r) required to correct a

given number of data bits (m ) it should satisfy a condition :

2r>=m+r+1 19
Data Link Layer

Number of Data Bits Number of Total Bits

(m) Redundancy Bits (r) (m+r)
1 2 3
2 3 5
3 3 6
4 3 7
5 4 9
6 4 10
7 4 11

Table : Relation Between Data and Redundancy Bits

20
Data Link Layer
• The redundancy bits in the original data are placed in powers of 2 like 1
,2,4,8,16 etc .

Fig : Position of Redundancy bits in hamming code

• r1 is selected so as to establish even parity in bit positions : 1,3,5,7,9,11 .

• r2 is selected so as to establish even parity in bit positions : 2,3,6,7,10,11 .
• r3 is selected so as to establish even parity in bit positions : 4,5,6,7.
• r4 is selected so as to establish even parity in bit positions : 8,9,10,11

21
Data Link Layer
• If any combination the number of 1’s even number ,assign the
corresponding r value as 0 else 1 .
• Like this after knowing the values of r1,r2,r4 and r8 the error bit
location can be identified by r’s position ( r8 r4 r2 r1).
• All values of r’s zero indicates no error has occurred .
Example 1: Consider the message 1001101 is transmitted through the
channel ,obtain the redundancy bits and transmitting unit needed.
Assume bit number 8 has been changed .how to locate it.
Example 2: Consider the message 1010111 is transmitted through the
channel ,obtain the redundancy bits and transmitting unit needed.
Assume bit number 3 has been changed .how to locate it.
Example 3: Consider the message 1101100 is transmitted through the
channel ,obtain the redundancy bits and transmitting unit needed.
Assume bit number 5 has been changed .how to locate it.

22
Data Link Layer
CRC (Cyclic Redundancy Check)
• Most power full redundancy technique based on the binary division .
• It uses polynomial codes for generating check bits in the form of cyclic
redundancy check .
• CRC bits are appended at the end of each data unit so that the resulting
data unit becomes exactly divisible by a second, predetermined number
.
• At the receiver the incoming data unit is divided by the same number .
• If there is no reminder the data unit is intact and it is accepted .
• A reminder indicates that data unit has damaged .

23
Data Link Layer

Fig : CRC Generator

and
Checker
24
Data Link Layer

Fig : CRC Encoding and Decoding

25
Data Link Layer

Fig : Binary Division in CRC Generator

26
Data Link Layer

Fig : Binary Division in CRC Checker

27
Data Link Layer
Example 1: What is the frame transmitted if the message i(x) is x7 + x4 + x3+x
and generator polynomial g(x) is x3 + x2 +1 .

11111001

1101 10011010000 Message plus k

1101 zeros
k + 1 bit check 1001
sequence c, 1101
equivalent to a 1000
degree-k 1101 Result:
polynomial 1011
1101 Transmit message
1100
1101
followed by
1000
remainder:
Remainder 1101
m mod c 101 10011010101

28
Data Link Layer

C(x) = x3 + x2 + 1 = 1101 Generator

P(x) = x10 + x7 + x6 + x4 + x2 + 1 = 10011010101 Received Message

11111011

1101 10011010101 Received

1101 message, no
k + 1 bit check 1001 errors
sequence c, 1101
equivalent to a 1000
degree-k 1101 1. Result:
polynomial 1011
1101 CRC test is passed
1100
1101
1101
Remainder 1101
m mod c 0

29
Data Link Layer

Example 2: i(x) =10110111 g(x)=110011

Example 3: i(x)=1101011011 g(x) =x4+x+1
Example 4: i(x)=1010011010 g(x) =10101

30
Flow Control
• Flow control coordinates the amount of data that can be
sent before receiving acknowledgement
• It is one of the most important functions of data link layer.
• Flow control is a set of procedures that tells the sender how
much data it can transmit before it must wait for an
acknowledgement from the receiver.
• Receiver has a limited speed at which it can process
incoming data and a limited amount of memory in which
to store incoming data.
• Receiver must inform the sender before the limits are
reached and request that the transmitter to send fewer
frames or stop temporarily.
• Since the rate of processing is often slower than the rate of
transmission, receiver has a block of memory (buffer) for
storing incoming data until they are processed.
31
Error Control

• Error control includes both error detection and error

correction.
• It allows the receiver to inform the sender if a frame is
lost or damaged during transmission and coordinates
the retransmission of those frames by the sender.
• Error control in the data link layer is based on
automatic repeat request (ARQ). Whenever an error is
detected, specified frames are retransmitted.

32
Note

Flow control refers to a set of procedures

used to restrict the amount of data
that the sender can send before
waiting for acknowledgment.

Don’t overwhelm the receiver!

11.33
Note

Error control in the data link layer is

based on automatic repeat request,
which is the retransmission of data.

11.34
PROTOCOLS

Now let us see how the data link layer can combine
framing, flow control, and error control to achieve the
delivery of data from one node to another.

11.35
Taxonomy of protocols discussed in this chapter

11.36
NOISELESS CHANNELS

Let us first assume we have an ideal channel in which

no frames are lost, duplicated, or corrupted. We
introduce two protocols for this type of channel.

Topics discussed in this section:

Simplest Protocol
Stop-and-Wait Protocol

11.37
The design of the simplest protocol with no flow or error control

11.38
Figure 11.7 Flow diagram for Example 11.1

11.39
Figure 11.8 Design of Stop-and-Wait Protocol

11.40
Figure 11.9 Flow diagram for Example 11.2

11.41
 NOISY CHANNELS

Although the Stop-and-Wait Protocol gives us an idea of

how to add flow control to its predecessor, noiseless
channels are nonexistent. We discuss three protocols in
this section that use error control.

Topics discussed in this section:

• Stop-and-Wait Automatic Repeat Request (ARQ)
• Go-Back-N Automatic Repeat Request
• Selective Repeat Automatic Repeat Request

11.42
 • Sender keeps a copy of the last frame
Stop-and-Wait (One until it receives an acknowledgement.
bit Sliding window • For identification, both data frames and
acknowledgements (ACK) frames are
Protocol) numbered alternatively 0 and 1.
• Sender has a control variable (S) that
holds the number of the recently sent
frame. (0 or 1)
• Receiver has a control variable (R) that
holds the number of the next frame
expected (0 or 1).
• Sender starts a timer when it sends a
frame. If an ACK is not received within a
allocated time period, the sender
assumes that the frame was lost or
damaged and resends it
• Receiver send only positive ACK if the
frame is intact.
• ACK number always defines the number
of the next expected frame
43
Stop-and-Wait ARQ, lost ACK frame

• When a receiver receives a

damaged frame, it discards it
and keeps its value of R.
• After the timer at the sender
expires, another copy of frame
1 is sent.

44
Stop-and-Wait, lost ACK frame

• If the sender receives a

damaged ACK, it discards it.
• When the timer of the
sender expires, the sender
retransmits frame 1.
• Receiver has already
received frame 1 and
expecting to receive frame 0
(R=0). Therefore it discards
the second copy of frame 1.

45
Stop-and-Wait, delayed ACK frame
• The ACK can be delayed at
the receiver or due to
some problem
• It is received after the
timer for frame 0 has
expired.
• Sender retransmitted a
copy of frame 0. However,
R=1 means receiver
expects to see frame 1.
Receiver discards the
duplicate frame 0.
• Sender receives 2 ACKs, it
discards the second ACK.

46
Piggybacking
• A method to
combine a data
frame with ACK.
• Station A and B both
have data to send.
• Instead of sending
separately, station A
sends a data frame
that includes an ACK.
• Station B does the
same thing.
• Piggybacking saves
bandwidth.

47
Disadvantage of Stop-and-Wait
• In stop-and-wait, at any point in time, there is only one frame that is
sent and waiting to be acknowledged. This is not a good use of
transmission medium.
• To improve efficiency, multiple frames should be in transition while
waiting for ACK. That is called Sliding Window Protocols.
• Several frames can be sent at once the channel capacity can be used
efficiently .
• The receiver acknowledges only some of the frames , using a single ACK
to confirm the receipt of multiple data frames .

• There are three different types of Sliding window protocols .

1. One bit Sliding window Protocol
2. Go – Back – n Automatic Repeat – Request (ARQ)
3. Selective Repeat – Automatic Repeat Request (ARQ)

48
Go-Back-N ARQ

• We can send up to W frames before worrying about ACKs.

• We keep a copy of these frames until the ACKs arrive.
• This procedure requires additional features to be added to Stop-and-
Wait ARQ.

49
Sequence Numbers

• Frames from a sender are numbered sequentially.

• We need to set a limit since we need to include the sequence
number of each frame in the header.
• If the header of the frame allows m bits for sequence number, the
sequence numbers range from 0 to 2 m – 1. for m = 3, sequence
numbers are: 1, 2, 3, 4, 5, 6, 7.
• We can repeat the sequence number.
• Sequence numbers are:
0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, …

50
 Sender Sliding Window
• At the sending site, to
hold the outstanding
frames until they are
acknowledged, we use
the concept of a window.
• The size of the window is
at most 2m -1 where m is
the number of bits for
the sequence number.
• Size of the window can
be variable, e.g. TCP.
• The window slides to
include new unsent
frames when the correct
ACKs are received 51
Receiver Sliding Window

• Size of the window at the

receiving site is always 1 in
this protocol.
• Receiver is always looking for
a specific frame to arrive in a
specific order.
• Any frame arriving out of
order is discarded and needs
to be resent.
• Receiver window slides as
shown in fig. Receiver is
waiting for frame 0 in part a
& frame 1 in part b.

52
 Control Variables
• Sender has 3 variables: S, SF, and SL
• S holds the sequence number of recently sent frame
• SF holds the sequence number of the first frame
• SL holds the sequence number of the last frame
• Receiver only has the one variable, R, that holds the sequence
number of the frame it expects to receive. If the seq. no. is the
same as the value of R, the frame is accepted, otherwise rejected.

53
 Acknowledgement
• Receiver sends positive ACK if a frame arrived safe and in order.
• If the frames are damaged/out of order, receiver is silent and
discard all subsequent frames until it receives the one it is
expecting.
• The silence of the receiver causes the timer of the unacknowledged
frame to expire.
• Then the sender resends all frames, beginning with the one with
the expired timer.
• For example, suppose the sender has sent frame 6, but the timer
for frame 3 expires (i.e. frame 3 has not been acknowledged), then
the sender goes back and sends frames 3, 4, 5, 6 again. Thus it is
called Go-Back-N-ARQ

54
Go-Back-N ARQ, normal operation
• The sender keeps track of the outstanding frames and
updates the variables and windows as the ACKs arrive.

55
Go-Back-N ARQ, lost frame
• Frame 2 is lost
• When the
receiver receives
frame 3, it
discards frame 3
as it is expecting
frame 2
(according to
window).
• After the timer
for frame 2
expires at the
sender site, the
sender sends
frame 2 and 3.
(go back to 2)56
Go-Back-N ARQ, damaged/lost/delayed ACK

• If an ACK is damaged/lost, we can have two situations:

• If the next ACK arrives before the expiration of any timer,
there is no need for retransmission of frames because
ACKs are cumulative in this protocol.
• If ACK1, ACK2, and ACk3 are lost, ACK4 covers them if it
arrives before the timer expires.
• If ACK4 arrives after time-out, the last frame and all the
frames after that are resent.
• Receiver never resends an ACK.
• A delayed ACK also triggers the resending of frames

57
Go-Back-N ARQ

58
Selective Repeat ARQ, sender and receiver windows
• Go-Back-N ARQ simplifies the process at the receiver site. Receiver only keeps
track of only one variable, and there is no need to buffer out-of-order frames,
they are simply discarded.
• However, Go-Back-N ARQ protocol is inefficient for noisy link. It bandwidth
inefficient and slows down the transmission.
• In Selective Repeat ARQ, only the damaged frame is resent. More bandwidth
efficient but more complex processing at receiver.
• It defines a negative ACK (NAK) to report the sequence number of a damaged
frame before the timer expires.

59
Selective Repeat ARQ, lost frame • Frames 0 and 1 are
accepted when received
because they are in the
range specified by the
receiver window. Same
for frame 3.
• Receiver sends a NAK2
to show that frame 2
has not been received
and then sender
resends only frame 2
and it is accepted as it is
in the range of the
window.

60
Selective Repeat ARQ, sender window size
• Size of the sender and receiver windows must be at most one-half of 2 m. If m =
2, window size should be 2 m /2 = 2. Fig compares a window size of 2 with a
window size of 3. Window size is 3 and all ACKs are lost, sender sends duplicate
of frame 0, window of the receiver expect to receive frame 0 (part of the
window), so accepts frame 0, as the 1st frame of the next cycle – an error.

61
Selective Repeat ARQ

62