Unit 2

Unit-2
The Data Link Layer
Mr. Bhushan B. Shaharkar

([email protected])
Assistant Professor,
Information Technology
Walchand Institute of Technology, Solapur.

www.witsolapur.org)
Walchand Institute of Technology, Solapur 1

Data Link Layer
•Network layer services

•Framing
•Error control
•Flow control
2
Data Link Layer
• Algorithms for achieving:
– Reliable, +
– Efficient,
communication of a whole units – frames (as opposed to
bits – Physical Layer) between two machines.
• Two machines are connected by a communication
channel that acts conceptually like a wire (e.g.,
telephone line, coaxial cable, or wireless channel).
• Essential property of a channel that makes it “wire-like”

connection is that the bits are delivered in exactly the
same order in which they are sent.
Data Link Layer
• For ideal channel (no distortion, unlimited bandwidth and

no delay) the job of data link layer would be trivial.
• However, limited bandwidth, distortions and delay makes

this job very difficult.
Data Link Layer Design Issues
• Physical layer delivers bits of information to and from
data link layer. The functions of Data Link Layer are:
1. Providing a well-defined service interface to the network
layer.
2. Dealing with transmission errors.
3. Regulating the flow of data so that slow receivers are
not swamped by fast senders.
• Data Link layer
– Takes the packets from Physical layer, and
– Encapsulates them into frames
Data Link Layer Design Issues
• Each frame has a

– frame header – a field for holding the packet, and
– frame trailer.
• Frame Management is what Data Link Layer does.
• See figure in the next slide:

Packets and Frames
Relationship between packets and frames.
7
Services Provided to the Network Layer
• Principal Service Function of the data link layer is to
transfer the data from the network layer on the source
machine to the network layer on the destination machine.
– Process in the network layer that hands some bits to the
data link layer for transmission.
– Job of data link layer is to transmit the bits to the destination
machine so they can be handed over to the network layer
there (see figure in the next slide).
Network Layer Services
(a) Virtual communication. (b) Actual communication.

9
Possible Services Offered
● Unacknowledged connectionless service.
● Acknowledged connectionless service.
● Acknowledged connection-oriented service.
10
Unacknowledged Connectionless
Service
• It consists of having the source machine send independent frames to
the destination machine without having the destination machine
acknowledge them.
• Example: Ethernet, Voice over IP, etc. in all the communication channel
were real time operation is more important that quality of transmission.

Acknowledged Connectionless Service
• Each frame send by the Data Link layer is acknowledged and
the sender knows if a specific frame has been received or lost.
• Typically the protocol uses a specific time period that if has

passed without getting acknowledgment it will re-send the
frame.
• This service is useful for commutation when an unreliable

channel is being utilized (e.g., 802.11 WiFi).
• Network layer does not know frame size of the packets and
other restriction of the data link layer.
• Hence it becomes necessary for data link layer to have some
mechanism to optimize the transmission.
Acknowledged Connection Oriented
Service
• Source and Destination establish a connection first.
• Each frame sent is numbered
– Data link layer guarantees that each frame sent is indeed
received.
– It guarantees that each frame is received only once and that
all frames are received in the correct order.
• Examples:
– Satellite channel communication,
– Long-distance telephone communication, etc.
Acknowledged Connection Oriented
Service
• Three distinct phases:
1. Connection is established by having both side initialize
variables and counters needed to keep track of which
frames have been received and which ones have not.
2. One or more frames are transmitted.
3. Finally, the connection is released – freeing up the

variables, buffers, and other resources used to maintain
the connection.
15
Framing
• To provide service to the network layer the data link layer
must use the service provided to it by physical layer.
• Stream of data bits provided to data link layer is not
guaranteed to be without errors.
• Errors could be:
– Number of received bits does not match number of
transmitted bits (deletion or insertion)
– Bit Value
• It is up to data link layer to correct the errors if necessary.
Framing
• Transmission of the data link layer starts with breaking up
the bit stream
– into discrete frames
– Computation of a checksum for each frame, and
– Include the checksum into the frame before it is transmitted.
• Receiver computes its checksum error for a receiving
frame and if it is different from the checksum that is being
transmitted will have to deal with the error.
• Framing is more difficult than one could think!

Framing Methods
1.Byte count.
2.Flag bytes with byte stuffing.
3.Flag bits with bit stuffing.
4.Physical layer coding violations.
18
Byte Count Framing Method
• It uses a field in the header to specify the number of bytes
in the frame.
• Once the header information is being received it will be
used to determine end of the frame.
• See figure in the next slide:
• Trouble with this algorithm is that when the count is
incorrectly received the destination will get out of synch
with transmission.
– Destination may be able to detect that the frame is in error
but it does not have a means (in this algorithm) how to
correct it.
Framing (1)
A byte stream. (a) Without errors. (b) With one error.

20
Framing
C Program: C Program to implement byte count generator.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
void main()
{
char s[10] [10];
int x[50], i, n;
clrscr();
printf(“Enter the no. of frames that you want to send:\n”)
scanf(“%d” &n);
for (i=0; i<n; n++)
{
printf(“\n Enter the Frame no. %d\n”,i);
scanf(“%s”, &[i]);
}
for (i=0; i<n; i++)
{
x[i]=strlen(s[i]);
}
printf(“\n Generated Code is:\n\n ”);
}
getch();
} 21
Flag Bytes with Byte Stuffing Framing
Method
• This methods gets around the boundary detection of the frame
by having each appended by the frame start and frame end
special bytes.
• If they are the same (beginning and ending byte in the frame)
they are called flag byte.
• In the next slide figure this byte is shown as FLAG.
• If the actual data contains a byte that is identical to the FLAG
byte (e.g., picture, data stream, etc.) the convention that can be
used is to have escape character inserted just before the “FLAG”
character.
Framing (2)
• A frame delimited by flag bytes.

• Four examples of byte sequences before and after byte stuffing.
23
Flag Bits with Bit Stuffing Framing
Method
• This methods achieves the same thing as Byte Stuffing
method by using Bits (1) instead of Bytes (8 Bits).
• It was developed for High-level Data Link Control (HDLC)
protocol.
• Each frames begins and ends with a special bit pattern:
– 01111110 or 0x7E <- Flag Byte
– Whenever the sender’s data link layer encounters five
consecutive 1s in the data it automatically stuffs a 0 bit into the
outgoing bit stream.
– USB uses bit stuffing.
Framing (3)
Bit stuffing. (a) The original data. (b) The data as they appear on
the line. (c) The data as they are stored in the receiver’s memory after destuffing.
25
Framing
• Many data link protocols use a combination of presented

methods for safety.
• For example in Ethernet and 802.11 each frame begin with a

well-defined pattern called a preamble.
• Preamble is typically 72 bits long.
• It is then followed by a length field.

C Program to Implement bit stuffing and destuffing
#include<stdio.h> else
#include<stdlib.h> {
#define MAXSIZE 100 while(*p=='1' && count!=5)
int main() {
{
char *p,*q; count++;
char temp; *q=*p;
char in[MAXSIZE];
q++;
char stuff[MAXSIZE];
p++;
char destuff[MAXSIZE];
int count=0; }
printf("enter the input character string (0‘s & 1‘s if(count==5)
only):\n"); {
scanf("%s",in); *q='0';
p=in; q++;
q=stuff; }
while(*p!='\0')
{
if(*p=='0')
{
*q=*p;
q++;
p++;
}
C Program to Implement bit stuffing and destuffing
count=0; {
} count++;
} *q=*p;
*q='\0'; q++;
printf("\nthe stuffed character string is"); p++;
printf("\n%s",stuff); }
p=stuff; if(count==5)
q=destuff; {
while(*p!='\0') p++;
{ }
if(*p=='0') count=0;
{ }
*q=*p; }
q++; *q='\0';
p++; printf("\nthe destuffed
} character string is");
else printf("\n%s\n",destuff);
{ return 0;
while(*p=='1' && count!=5) }
Error Control
• After solving the marking of the frame with start and end the
data link layer has to handle eventual errors in transmission or
detection.
– Ensuring that all frames are delivered to the network layer at
the destination and in proper order.
• Unacknowledged connectionless service: it is OK for the

sender to output frames regardless of its reception.
• Reliable connection-oriented service: it is NOT OK.

Error Control
• Reliable connection-oriented service usually will provide a
sender with some feedback about what is happening at the
other end of the line.
– Receiver Sends Back Special Control Frames.

– If the Sender Receives positive Acknowledgment it will know
that the frame has arrived safely.
• Timer and Frame Sequence Number for the Sender is

Necessary to handle the case when there is no response
(positive or negative) from the Receiver .
Flow Control
• Important Design issue for the cases when the sender is
running on a fast powerful computer and receiver is running
on a slow low-end machine.
• Two approaches:
1. Feedback-based flow control
2. Rate-based flow control
Feedback-based Flow Control
• Receiver sends back information to the sender giving it

permission to send more data, or
• Telling sender how receiver is doing.
Rate-based Flow Control
• Built in mechanism that limits the rate at which sender may

transmit data, without the need for feedback from the receiver.
Error Detection and Correction
• Two basic strategies to deal with errors:

1. Include enough redundant information to
enable the receiver to deduce what the
transmitted data must have been.
Error correcting codes.
2. Include only enough redundancy to allow
the receiver to deduce that an error has
occurred (but not which error).
Error detecting codes.
• Error codes are examined in Link Layer because
this is the first place that we have run up against the
problem of reliability transmitting groups of bits.
– Codes are reused because reliability is an overall
concern.
– The error correcting code are also seen in the
physical layer for noise channels.
– Commonly they are used in link, network and
transport layer.
• Error codes have been developed after long

fundamental research conducted in mathematics.
• Many protocol standards get codes from the large

field in mathematics.
Error Detection & Correction Code (1)
1.Hamming codes.
2.Binary convolutional codes.
3.Reed-Solomon codes.
4.Low-Density Parity Check
codes.
37
Error Detection & Correction Code
• All the codes presented in previous slide add redundancy to
the information that is being sent.
• A frame consists of
– m data bits (message) and
– r redundant bits (check).
• Block code - the r check bits are computed solely as function
of the m data bits with which they are associated.
• Systemic code – the m data bits are send directly along with
the check bits.
• Linear code – the r check bits are computed as a linear

function of the m data bits.
• n – total length of a block (i.e., n = m + r)

• (n, m) – code
• n – bit codeword containing n bits.
• m/n – code rate (range ½ for noisy channel and
close to 1 for high-quality channel).
Example
•Transmitted: 10001001
•Received: 10110001
XOR operation gives number of bits that are different.
•XOR: 00111000
•Number of bit positions in which two codewords differ

is called Hamming Distance.
•It shows that two codes are d distance apart, and it
will require d errors to convert one into the other.
• All 2m possible data messages are legal, but due to
the way the check bits are computed, not all 2 n
possible code words are used.
• Only small fraction of 2m/2n or 1/2r are possible will be
legal codewords.
• The error-detecting and error-correcting codes of
the block code depend on this Hamming distance.
• To reliably detect d error, one would need a
distance d+1 code.
• To correct d error, one would need a distance 2d+1
code.
Example: Error correcting
• 4 valid codes:
– 0000000000
– 0000011111
– 1111100000
– 1111111111
•Minimal Distance of this code is 5 => can correct double errors
or it detect quadruple errors.
•0000000111 => single or double bit error. Hence the receiving
end must assume the original transmission was 0000011111.
•0000000000 => had triple error that was received as
0000000111 it would be detected in error.
• One cannot perform double errors and at the same time detect
quadruple errors.
• Error correction requires evaluation of each candidate

codeword which may be time consuming search.
• Through design this search time can be minimized.

Hamming Code
In Hamming code bits of codeward are numbered consecutively, starting with bit 1 at
the left end, bit 2 its immediate right and so on.
• Codeword: b1 b2 b3 b4 ….
• Check bits: The bits that
are powers of 2 (p1, p2, p4,
p8, p16, …).
• The rest of bits (m3, m5,
m6, m7, m9, …) are filled
with m data bits.
• Example shows some 7-bit
ASCII character encoded
as 11-bit codewords using
Hamming code.
Error Detection Codes (2)
Example of the Hamming code with m = 7 data bits and r = 4 check bits
is given below.
Example of an (11, 7) Hamming code

correcting a single-bit error.
45
Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, © Pearson Education-Prentice Hall, 2011
Convolutional Codes
• Not a block code
• There is no natural message size or encoding boundary as in
a block code.
• The output depends on the current and previous input bits.
Encoder has memory.
• The number of previous bits on which the output depends is
called the constraint length of the code.
• They are deployed as part of the
– GSM mobile phone system
– Satellite Communications, and
– 802.11 (see example in the previous slide).
Error Detection Codes (3)
The NASA binary convolutional code used in 802.11.
47
Convolutional Encoders
• Like any error-correcting code, a convolutional code works by
adding some structured redundant information to the user's data
and then correcting errors using this information.
• A convolutional encoder is a linear system.
• A binary convolutional encoder can be represented as a shift
register.
• The outputs of the encoder are modulo 2 sums of the values in
the certain register's cells.
• The input to the encoder is either the encoded sequence (for
non-recursive codes) or the encoded sequence added with the
values of some register's cells (for recursive codes).
• Convolutional codes can be systematic and non-systematic.
Systematic codes are those where an unencoded sequence is a
part of the output sequence.
• Systematic codes are almost always recursive, conversely, non-
recursive codes are almost always non-systematic.
Error-Detecting Codes (1)
Linear, systematic block codes

1.Parity.
2.Checksums.
3.Cyclic Redundancy Checks (CRCs).
49
Interleaving of parity bits to detect a burst error.
50
Example calculation of the CRC

51
Elementary Data Link Protocols
• Utopian Simplex Protocol

• Simplex Stop-and-Wait Protocol
• Error-Free Channel
• Simplex Stop-and-Wait Protocol
• Noisy Channel
52
Elementary Data Link Protocols
Implementation of the physical, data link, and network layers.
53
Elementary Data Link Protocols (3)
Some definitions needed in the protocols to follow. These definitions are located in the
file protocol.h.
54
Some definitions needed in the protocols to follow. These definitions are located in the
file protocol.h.
55
Some definitions needed in the protocols to follow. These definitions are located in the file
protocol.h.
56
Utopian Simplex Protocol (1)
A utopian simplex protocol.

57
Utopian Simplex Protocol (2)
A utopian simplex protocol.
58
Simplex Stop-and-Wait for an Error-Free Channel
• To build the receiver to powerful enough to process continuous frame.
• It must have buffering & processing abilities
• It requires dedicated hardware
• Receiver provide feedback to sender.
• After passing packet to its n/w layer, receiver send small dummy frame to
sender
• Protocols in which sender sends one frame & waits for acknowledge before
proceeding are called stop-and-wait protocol.
A simplex stop-and-wait protocol.

59

60
61
Simplex Stop-and-Wait Protocol for a Noisy Channel
• A NL on A gives packet 1 to its DLL. The packet is correctly received at B & passed
to NL on B. B send an ACK frame back to A.
• The ACK frame get lost completely.
• The DLL on A eventually times out.
• The duplicate frame also arrives intact at the DLL on B is accidentally passed to NL
there. If A is sending a file to B, part of the file will be duplicated.
62
PAwR Protocol
A positive acknowledgement with retransmission protocol.
63
PAwR Protocol
64
PAR with Retransmission Protocol

65
Sliding Window Protocols
A sliding window of size 1, with a 3-bit sequence number.

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

(c) After the first frame has been received. (d) After the first
acknowledgement has been received. 67
One-Bit Sliding Window Protocol (1)
68
69
70
Two scenarios for protocol 4. (a) Normal case. (b) Abnormal

case. The notation is (seq, ack, packet number). An asterisk indicates where a
network layer accepts a packet
71
Protocol Using Go-Back-N (1)
Pipelining and error recovery. Effect of an error when

(a) receiver’s window size is 1
72
Pipelining and error recovery. Effect of an error when

(b) receiver’s window size is large.
73
A sliding window protocol using go-back-n.
74
75
76
77
78

79

80
Simulation of multiple timers in software. (a) The queued

timeouts (b) The situation after the first timeout has expired.
81
Protocol Using Selective Repeat (1)
A sliding window protocol using selective repeat.
82
83
84
85
86
87
...

88
...

89

90
a) Initial situation with a window of size7

b) After 7 frames sent and received but not acknowledged.
c) Initial situation with a window size of 4.
d) After 4 frames sent and received but not acknowledged.
91
End

Unit 2

Uploaded by

Copyright:

Available Formats

Unit 2

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 2

Uploaded by

Copyright:

Available Formats

Unit-2

The Data Link Layer

Mr. Bhushan B. Shaharkar

Walchand Institute of Technology, Solapur.

Walchand Institute of Technology, Solapur 1

•Network layer services

• Essential property of a channel that makes it “wire-like”

• For ideal channel (no distortion, unlimited bandwidth and

• However, limited bandwidth, distortions and delay makes

• Each frame has a

• See figure in the next slide:

Relationship between packets and frames.

(a) Virtual communication. (b) Actual communication.

● Unacknowledged connectionless service.

● Acknowledged connectionless service.

● Acknowledged connection-oriented service.

the destination machine without having the destination machine

were real time operation is more important that quality of transmission.

• Typically the protocol uses a specific time period that if has

• This service is useful for commutation when an unreliable

3. Finally, the connection is released – freeing up the

• Framing is more difficult than one could think!

A byte stream. (a) Without errors. (b) With one error.

• A frame delimited by flag bytes.

• Many data link protocols use a combination of presented

• For example in Ethernet and 802.11 each frame begin with a

• Preamble is typically 72 bits long.

• It is then followed by a length field.

• Unacknowledged connectionless service: it is OK for the

• Reliable connection-oriented service: it is NOT OK.

– Receiver Sends Back Special Control Frames.

• Timer and Frame Sequence Number for the Sender is

• Receiver sends back information to the sender giving it

• Built in mechanism that limits the rate at which sender may

• Two basic strategies to deal with errors:

• Error codes have been developed after long

• Many protocol standards get codes from the large

• Linear code – the r check bits are computed as a linear

• n – total length of a block (i.e., n = m + r)

•Number of bit positions in which two codewords differ

• Error correction requires evaluation of each candidate

• Through design this search time can be minimized.

Example of an (11, 7) Hamming code

The NASA binary convolutional code used in 802.11.

Linear, systematic block codes

Interleaving of parity bits to detect a burst error.

Example calculation of the CRC

• Utopian Simplex Protocol

Implementation of the physical, data link, and network layers.

A utopian simplex protocol.

A utopian simplex protocol.

• To build the receiver to powerful enough to process continuous frame.

• It must have buffering & processing abilities

• It requires dedicated hardware

• Receiver provide feedback to sender.

proceeding are called stop-and-wait protocol.

A simplex stop-and-wait protocol.

A simplex stop-and-wait protocol.