UNIT - II

Data link layer: Design issues, framing, Error detection and correction. Elementary data link protocols:
simplex protocol, A simplex stop and wait protocol for an error-free channel, A simplex stop and wait
protocol for noisy channels.
Sliding Window protocols: A one-bit sliding window protocol, A protocol using Go-Back-N, A protocol
using Selective Repeat, Example data link protocols.

Design Issues in Data Link Layer

Data-link layer is the second layer after the physical layer. The data link layer is responsible for maintaining
the data link between two hosts or nodes.
Before going through the design issues in the data link layer. Some of its sub-layers and their functions are as
follows below.
The data link layer is divided into two sub-layers :
1. Logical Link Control Sublayer (LLC) –
Provides the logic for the data link, Thus it controls the synchronization, flow control, and error checking
functions of the data link layer. Functions are –
○ (i) Error Recovery.
○ (ii) It performs the flow control operations.
○ (iii) User addressing.

2. Media Access Control Sublayer (MAC) –

It is the second sub-layer of the data-link layer. It controls the flow and multiplexing for the transmission
medium. Transmission of data packets is controlled by this layer. This layer is responsible for sending the data
over the network interface card.
Functions are –
○ (i) To perform the control of access to media.
○ (ii) It performs the unique addressing to stations directly connected to LAN.
○ (iii) Detection of errors.

Design issues with data link layer are :

1. Services provided to the network layer –
The data link layer acts as a service interface to the network layer. The principal service is transferring data
from the network layer on the sending machine to the network layer on the destination machine. This transfer
also takes place via DLL (Data link-layer).
2. Frame synchronization –
The source machine sends data in the form of blocks called frames to the destination machine. The starting and
ending of each frame should be identified so that the frame can be recognized by the destination machine.
3. Flow control –
Flow control is done to prevent the flow of data frames at the receiver end. The source machine must not send
data frames at a rate faster than the capacity of the destination machine to accept them.
4. Error control –
Error control is done to prevent duplication of frames. The errors introduced during transmission from source to
destination machines must be detected and corrected at the destination machine.
Framing

Frames are the units of digital transmission, particularly in computer networks and telecommunications. Frames
are comparable to the packets of energy called photons in the case of light energy. Frame is continuously used in
the Time Division Multiplexing process.
Framing is a point-to-point connection between two computers or devices consisting of a wire in which data is
transmitted as a stream of bits. However, these bits must be framed into discernible blocks of information.
Framing is a function of the data link layer. It provides a way for a sender to transmit a set of bits that are
meaningful to the receiver. Ethernet, token ring, frame relay, and other data link layer technologies have their
own frame structures. Frames have headers that contain information such as error-checking codes.

At the data link layer, it extracts the message from the sender and provides it to the receiver by providing the
sender’s and receiver’s addresses. The advantage of using frames is that data is broken up into recoverable
chunks that can easily be checked for corruption.

Problems in Framing –
● Detecting start of the frame: When a frame is transmitted, every station must be able to detect it.
Station detects frames by looking out for a special sequence of bits that marks the beginning of the frame i.e.
SFD (Starting Frame Delimiter).
● How does the station detect a frame: Every station listens to a link for SFD pattern through a
sequential circuit. If SFD is detected, a sequential circuit alerts the station. Station checks the destination
address to accept or reject the frame.
● Detecting end of frame: When to stop reading the frame.

Types of framing – There are two types of framing:

1. Fixed size – The frame is of fixed size and there is no need to provide boundaries to the frame, the length of
the frame itself acts as a delimiter.
● Drawback: It suffers from internal fragmentation if the data size is less than the frame size
● Solution: Padding

2. Variable size – In this, there is a need to define the end of the frame as well as the beginning of the next
frame to distinguish. This can be done in two ways:
1) Length field – We can introduce a length field in the frame to indicate the length of the frame. Used in
Ethernet(802.3). The problem with this is that sometimes the length field might get corrupted.
2) End Delimiter (ED) – We can introduce an ED(pattern) to indicate the end of the frame. Used in Token
Ring. The problem with this is that ED can occur in the data. This can be solved by:

1. Character/Byte Stuffing: Used when frames consist of characters. If data contains ED then, a byte is stuffed
into data to differentiate it from ED. Let ED = “$” –> if data contains ‘$’ anywhere, it can be escaped using ‘\O’
character. –> if data contains ‘\O$’ then, use ‘\O\O\O$'($ is escaped using \O and \O is escaped using \O).

Disadvantage – It is a very costly and obsolete method.

2. Bit Stuffing: Let ED = 01111 and if data = 01111

–> Sender stuffs a bit to break the pattern i.e. here appends a 0 in data = 011101.
–> Receiver receives the frame.
–> If data contains 011101, the receiver removes the 0 and reads the data.
Error detection and correction

Error A condition when the receiver’s information does not match with the sender’s information. During
transmission, digital signals suffer from noise that can introduce errors in the binary bits traveling from sender
to receiver. That means a 0 bit may change to 1 or a 1 bit may change to 0.

Error Detecting Codes (Implemented either at Data link layer or Transport Layer of OSI Model)
Whenever a message is transmitted, it may get scrambled by noise or data may get corrupted. To avoid this, we
use error-detecting codes which are additional data added to a given digital message to help us detect if any
error has occurred during transmission of the message.
Basic approach used for error detection is the use of redundancy bits, where additional bits are added to
facilitate detection of errors.
Some popular techniques for error detection are:
1. Simple Parity check
2. Two-dimensional Parity check
3. Checksum
4. Cyclic redundancy check

1. Simple Parity check

Blocks of data from the source are subjected to a check bit or parity bit generator form, where a parity of :
● 1 is added to the block if it contains odd number of 1’s, and
● 0 is added if it contains even number of 1’s
This scheme makes the total number of 1’s even, that is why it is called even parity checking.

2.
Two-dimensional Parity check

2. Two-dimensional Parity check

Parity check bits are calculated for each row, which is equivalent to a simple parity check bit. Parity check bits
are also calculated for all columns, then both are sent along with the data. At the receiving end these are
compared with the parity bits calculated on the received data

3. Checksum

● In the checksum error detection scheme, the data is divided into k segments each of m bits.
● In the sender’s end the segments are added using 1’s complement arithmetic to get the sum. The sum is
complemented to get the checksum.
● The checksum segment is sent along with the data segments.
● At the receiver’s end, all received segments are added using 1’s complement arithmetic to get the sum.
The sum is complemented.
● If the result is zero, the received data is accepted; otherwise discarded.

4. Cyclic redundancy check (CRC)

● Unlike the checksum scheme, which is based on addition, CRC is based on binary division.
● In CRC, a sequence of redundant bits, called cyclic redundancy check bits, are appended to the end of
the data unit so that the resulting data unit becomes exactly divisible by a second, predetermined binary number.
● At the destination, the incoming data unit is divided by the same number. If at this step there is no
remainder, the data unit is assumed to be correct and is therefore accepted.
● A remainder indicates that the data unit has been damaged in transit and therefore must be rejected.

Elementary data link protocols

Protocols in the data link layer are designed so that this layer can perform its basic functions: framing, error
control and flow control. Framing is the process of dividing bits - streams from the physical layer into data
frames whose size ranges from a few hundred to a few thousand bytes. Error control mechanisms deal with
transmission errors and retransmission of corrupted and lost frames. Flow control regulates speed of delivery
and so that a fast sender does not drown a slow receiver.

Types of Data Link Protocols

Data link protocols can be broadly divided into two categories, depending on whether the transmission channel
is noiseless or noisy.

Simplex Protocol

The Simplex protocol is a hypothetical protocol designed for unidirectional data transmission over an ideal
channel, i.e. a channel through which transmission can never go wrong. It has distinct procedures for sender and
receiver. The sender simply sends all its data available onto the channel as soon as they are available in its
buffer. The receiver is assumed to process all incoming data instantly. It is hypothetical since it does not handle
flow control or error control.

Stop – and – Wait Protocol

Stop – and – Wait protocol is for noiseless channels too. It provides unidirectional data transmission without
any error control facilities. However, it provides for flow control so that a fast sender does not drown a slow
receiver. The receiver has a finite buffer size with finite processing speed. The sender can send a frame only
when it has received indication from the receiver that it is available for further data processing.

Stop – and – Wait ARQ

Stop – and – wait Automatic Repeat Request (Stop – and – Wait ARQ) is a variation of the above protocol with
added error control mechanisms, appropriate for noisy channels. The sender keeps a copy of the sent frame. It
then waits for a finite time to receive a positive acknowledgement from the receiver. If the timer expires or a
negative acknowledgement is received, the frame is retransmitted. If a positive acknowledgement is received
then the next frame is sent.
Go – Back – N ARQ

Go – Back – N ARQ provides for sending multiple frames before receiving the acknowledgement for the first
frame. It uses the concept of sliding window, and so is also called sliding window protocol. The frames are
sequentially numbered and a finite number of frames are sent. If the acknowledgement of a frame is not
received within the time period, all frames starting from that frame are retransmitted.

Selective Repeat ARQ

This protocol also provides for sending multiple frames before receiving the acknowledgement for the first
frame. However, here only the erroneous or lost frames are retransmitted, while the good frames are received
and buffered.

A Simplex Stop-and-Wait Protocol for an Error-Free Channel

Stop – and – Wait protocol is data link layer protocol for transmission of frames over noiseless channels. It
provides unidirectional data transmission with flow control facilities but without error control facilities.
This protocol takes into account the fact that the receiver has a finite processing speed. If data frames arrive at
the receiver’s end at a rate which is greater than its rate of processing, frames are dropped out. In order to avoid
this, the receiver sends an acknowledgement for each frame upon its arrival. The sender sends the next frame
only when it has received a positive acknowledgement from the receiver that it is available for further data
processing.
Design
● Sender Site: The data link layer in the sender site waits for the network layer for a data packet. It then
checks whether it can send the frame. If it receives a positive notification from the physical layer, it makes
frames out of the data and sends it. It then waits for an acknowledgement before sending the next frame.
● Receiver Site: The data link layer in the receiver site waits for a frame to arrive. When it arrives, the
receiver processes it and delivers it to the network layer. It then sends an acknowledgement back to the sender.
Sender Site Algorithm of Simplex Stop – and – Wait Protocol for Noiseless Channel

begin
canSend = True; //Allow the first frame to be sent
while (true) //check repeatedly
do
Wait_For_Event(); //wait for availability of packet
if ( Event(Request_For_Transfer) AND canSend) then
Get_Data_From_Network_Layer();
Make_Frame();
Send_Frame_To_Physical_Layer();
canSend = False;
else if ( Event(Acknowledgement_Arrival)) then
Receive_ACK();
canSend = True;
end if
end while
end
Receiver Site Algorithm of Simplex Stop – and – Wait Protocol for Noiseless Channel
begin
while (true) //check repeatedly
do
Wait_For_Event(); //wait for arrival of frame
if ( Event(Frame_Arrival) then
Receive_Frame_From_Physical_Layer();
Extract_Data();
Deliver_Data_To_Network_Layer();
Send_ACK();
end if
end while
end
Flow Diagram
The following flow diagram depicts communication via simplex stop – and – wait protocol for noiseless
channel:

A Simplex Stop-and-Wait Protocol for a Noisy Channel

Simplex Stop – and – Wait protocol for noisy channels is data link layer protocol for data communications with
error control and flow control mechanisms. It is popularly known as Stop – and –Wait Automatic Repeat
Request (Stop – and –Wait ARQ) protocol. It adds error control facilities to Stop – and – Wait protocol.
This protocol takes into account the facts that the receiver has a finite processing speed and that frames may get
corrupted while transmission. If data frames arrive at the receiver’s end at a rate which is greater than its rate of
processing, frames can be dropped out. Also, frames may get corrupted or entirely lost when they are
transmitted via network channels. So, the receiver sends an acknowledgment for each valid frame that it
receives. The sender sends the next frame only when it has received a positive acknowledgment from the
receiver that it is available for further data processing. Otherwise, it waits for a certain amount of time and then
resends the frame.
Design

● Sender Site − At the sender site, a field is added to the frame to hold a sequence number. If data is
available, the data link layer makes a frame with the certain sequence number and sends it. The sender then
waits for the arrival of acknowledgement for a certain amount of time. If it receives a positive acknowledgment
for the frame with that sequence number within the stipulated time, it sends the frame with the next sequence
number. Otherwise, it resembles the same frame.
● Receiver Site − The receiver also keeps a sequence number of the frames expected for arrival. When a
frame arrives, the receiver processes it and checks whether it is valid or not. If it is valid and its sequence
number matches the sequence number of the expected frame, it extracts the data and delivers it to the network
layer. It then sends an acknowledgement for that frame back to the sender along with its sequence number.
Sender Site Algorithm of Simplex Stop – and – Wait Protocol for Noisy Channel

begin
SeqNo = 0; // Initialize sequence number of outbound frame
canSend = True; //Allow the first frame to be sent
while (true) //check repeatedly
do
Wait_For_Event(); //wait for availability of packet
if ( Event(Request_For_Transfer) AND canSend) then
Get_Data_From_Network_Layer();
frame = Make_Frame(SeqNo);
Store_Copy_Frame([Link]);
Send_Frame_To_Physical_Layer([Link]);
Start_Timer([Link]);
SeqNo = SeqNo + 1;
canSend = False;
else if ( Event(Acknowledgement_Arrival)) then
Receive_ACK();
if ( ACK_No = SeqNo ) then
Stop_Timer ([Link]);
canSend = True;
end if
else if ( Event( Timer > Max_time)) then
Resend_Frame_To_Physical_Layer([Link]-1);
Start_Timer([Link]-1);
end if
end while
end
Receiver Site Algorithm of Simplex Stop – and – Wait Protocol for Noisy Channel
begin
RSeqNo = 0; // Initialise sequence number of expected frame
while (true) //check repeatedly
do
Wait_For_Event(); //wait for arrival of frame
if ( Event(Frame_Arrival) then
Receive_Frame_From_Physical_Layer();
if ( Corrupted ( [Link] )
doNothing();
else if ( [Link] = RSeqNo ) then
Extract_Data();
Deliver_Data_To_Network_Layer();
RSeqNo = RSeqNo + 1;
end if
Send_ACK(ACKframe[RSeqNo]);
end if
end while
end

Flow Diagram

The following flow diagram depicts communication via simplex stop – and – wait ARQ protocol for noisy
channel −
Sliding Window Protocol

The sliding window is a technique for sending multiple frames at a time. It controls the data packets between
the two devices where reliable and gradual delivery of data frames is needed. It is also used in TCP
(Transmission Control Protocol).

In this technique, each frame has sent from the sequence number. The sequence numbers are used to find the
missing data in the receiver end. The purpose of the sliding window technique is to avoid duplicate data, so it
uses the sequence number.

Types of Sliding Window Protocol

Sliding window protocol has two types:

1. Go-Back-N ARQ

2. Selective Repeat ARQ

Go-Back-N ARQ

Go-Back-N ARQ protocol is also known as Go-Back-N Automatic Repeat Request. It is a data link layer
protocol that uses a sliding window method. In this, if any frame is corrupted or lost, all subsequent frames have
to be sent [Link] size of the sender window is N in this protocol. For example, Go-Back-8, the size of the
sender window, will be 8. The receiver window size is always 1.

If the receiver receives a corrupted frame, it cancels it. The receiver does not accept a corrupted frame. When
the timer expires, the sender sends the correct frame again. The design of the Go-Back-N ARQ protocol is
shown below.
The example of Go-Back-N ARQ is shown below in the figure.

Selective Repeat ARQ

Selective Repeat ARQ is also known as the Selective Repeat Automatic Repeat Request. It is a data link layer
protocol that uses a sliding window method. The Go-back-N ARQ protocol works well if it has fewer errors.
But if there is a lot of error in the frame, lots of bandwidth loss in sending the frames again. So, we use the
Selective Repeat ARQ protocol. In this protocol, the size of the sender window is always equal to the size of the
receiver window. The size of the sliding window is always greater than 1.

If the receiver receives a corrupt frame, it does not directly discard it. It sends a negative acknowledgment to the
sender. The sender sends that frame again as soon as on the receiving negative acknowledgment. There is no
waiting for any time-out to send that frame. The design of the Selective Repeat ARQ protocol is shown below.

The example of the Selective Repeat ARQ protocol is shown below in the figure.
Difference between the Go-Back-N ARQ and Selective Repeat ARQ?

Go-Back-N ARQ Selective Repeat ARQ

If a frame is corrupted or lost in it,all subsequent In this, only the frame is sent again, which is
frames have to be sent again. corrupted or lost.

If it has a high error rate,it wastes a lot of bandwidth There is a loss of low bandwidth.

It is less complex. It is more complex because it has to do sorting

and searching as well. And it also requires more
storage.

It does not require sorting. In this, sorting is done to get the frames in the
correct order.

It does not require searching. The search operation is performed in it.

It is used more. It is used less because it is more complex.

A One-Bit Sliding Window Protocol

Sliding window protocols are data link layer protocols for reliable and sequential delivery of data frames. The
sliding window is also used in the Transmission Control Protocol. In these protocols, the sender has a buffer
called the sending window and the receiver has a buffer called the receiving window.

In one – bit sliding window protocol, the size of the window is 1. So the sender transmits a frame, waits for its
acknowledgment, then transmits the next frame. Thus it uses the concept of stop and waits for the protocol. This
protocol provides for full – duplex communications. Hence, the acknowledgment is attached along with the next
data frame to be sent by piggybacking.

Working Principle

The data frames to be transmitted additionally have an acknowledgment field, ack field that is of a few bits
length. The ack field contains the sequence number of the last frame received without error. If this sequence
number matches with the sequence number of the frame to be sent, then it is inferred that there is no error and
the frame is transmitted. Otherwise, it is inferred that there is an error in the frame and the previous frame is
retransmitted.

Since this is a bi-directional protocol, the same algorithm applies to both the communicating parties.
The algorithm of One – bit Sliding Window Protocol
begin
frame s, r; //s and r denotes frames to be sent and received
SeqNo = 0; // Initialise sequence number of outbound frame
RSeqNo = 0; // Initialise sequence number of expected frame
while (true) //check repeatedly
do
Wait_For_Event(); //wait for availability of packet
if ( Event(Request_For_Transfer) AND canSend) then
Get_Data_From_Network_Layer();
s = Make_Frame(SeqNo);
Store_Copy_Frame(s);
Start_Timer(s);
SeqNo = SeqNo + 1;
end if;
Wait_For_Event(); //wait for arrival of frame
if ( Event(Frame_Arrival) then
r = Receive_Frame_From_Physical_Layer();
if ( [Link] = RSeqNo ) then
Extract_Data(r);
Deliver_Data_To_Network_Layer(r);
Stop_Timer(r);
RSeqNo = RSeqNo + 1;
end if
end if
[Link] = [Link];
Send_Frame_To_Physical_Layer(s);
Start_Timer(s);
SeqNo = SeqNo + 1;
end while
end

Illustrative Example

The following diagram depicts a scenario with sequence numbers 0, 1, 2, 3, 0, 1, 2 and so on. It depicts the
sliding windows in the sending and the receiving stations during frame transmission.
A Protocol Using Go-Back-N

Go-Back-N protocol, also called Go-Back-N Automatic Repeat reQuest, is a data link layer protocol that uses a
sliding window method for reliable and sequential delivery of data frames. It is a case of sliding window
protocol having to send a window size of N and receiving window size of 1.

Working Principle

Go – Back – N ARQ provides for sending multiple frames before receiving the acknowledgment for the first
frame. The frames are sequentially numbered and a finite number of frames. The maximum number of frames
that can be sent depends upon the size of the sending window. If the acknowledgment of a frame is not received
within an agreed upon time period, all frames starting from that frame are retransmitted.

The size of the sending window determines the sequence number of the outbound frames. If the sequence
number of the frames is an n-bit field, then the range of sequence numbers that can be assigned is 0 to 2n−1.
Consequently, the size of the sending window is 2n−1. Thus in order to accommodate a sending window size of
2n−1, a n-bit sequence number is chosen.

The sequence numbers are numbered as modulo-n. For example, if the sending window size is 4, then the
sequence numbers will be 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, and so on. The number of bits in the sequence number is 2 to
generate the binary sequence 00, 01, 10, 11.

The size of the receiving window is 1.

Sender Site Algorithm of Go-Back-N Protocol

begin

frame s; //s denotes frame to be sent

frame t; //t is temporary frame

S_window = power(2,m) – 1; //Assign maximum window size

SeqFirst = 0; // Sequence number of first frame in window

SeqN = 0; // Sequence number of Nth frame window

while (true) //check repeatedly

do

Wait_For_Event(); //wait for availability of packet

if ( Event(Request_For_Transfer)) then

//check if window is full

if (SeqN–SeqFirst >= S_window) then

doNothing();

end if;
 Get_Data_From_Network_Layer();

s = Make_Frame();

[Link] = SeqN;

Store_Copy_Frame(s);

Send_Frame(s);

Start_Timer(s);

SeqN = SeqN + 1;

end if;

if ( Event(Frame_Arrival) then

r = Receive_Acknowledgement();

if ( AckNo > SeqFirst && AckNo < SeqN ) then

while ( SeqFirst <= AckNo )

Remove_copy_frame([Link](SeqFirst));

SeqFirst = SeqFirst + 1;

end while

Stop_Timer(s);

end if

end if

// Resend all frames if acknowledgement havn’t been received

if ( Event(Time_Out)) then

TempSeq = SeqFirst;

while ( TempSeq < SeqN )

t = Retrieve_Copy_Frame([Link](SeqFirst));

Send_Frame(t);

Start_Timer(t);

TempSeq = TempSeq + 1;

end while
 end if

end

Receiver Site Algorithm of Go-Back-N Protocol

Begin

frame f;

RSeqNo = 0; // Initialise sequence number of expected frame

while (true) //check repeatedly

do

Wait_For_Event(); //wait for arrival of frame

if ( Event(Frame_Arrival) then

Receive_Frame_From_Physical_Layer();

if ( Corrupted ( [Link] )

doNothing();

else if ( [Link] = RSeqNo ) then

Extract_Data();

Deliver_Data_To_Network_Layer();

RSeqNo = RSeqNo + 1;

Send_ACK(RSeqNo);

end if

end if

end while

end

A Protocol Using Selective Repeat

Selective repeat protocol, also called Selective Repeat ARQ (Automatic Repeat reQuest), is a data link layer
protocol that uses a sliding window method for reliable delivery of data frames. Here, only the erroneous or lost
frames are retransmitted, while the good frames are received and buffered.

It uses two windows of equal size: a sending window that stores the frames to be sent and a receiving window
that stores the frames received by the receiver. The size is half the maximum sequence number of the frame. For
example, if the sequence number is from 0 – 15, the window size will be 8.
Working Principle

Selective Repeat protocol provides for sending multiple frames depending upon the availability of frames in the
sending window, even if it does not receive acknowledgement for any frame in the interim. The maximum
number of frames that can be sent depends upon the size of the sending window.

The receiver records the sequence number of the earliest incorrect or un-received frame. It then fills the
receiving window with the subsequent frames that it has received. It sends the sequence number of the missing
frame along with every acknowledgement frame.

The sender continues to send frames that are in its sending window. Once it has sent all the frames in the
window, it retransmits the frame whose sequence number is given by the acknowledgements. It then continues
sending the other frames.

Sender Site Algorithm of Selective Repeat Protocol

begin

frame s; //s denotes frame to be sent

frame t; //t is temporary frame

S_window = power(2,m-1); //Assign maximum window size

SeqFirst = 0; // Sequence number of first frame in window

SeqN = 0; // Sequence number of Nth frame window

while (true) //check repeatedly

do

Wait_For_Event(); //wait for availability of packet

if ( Event(Request_For_Transfer)) then

//check if window is full

if (SeqN–SeqFirst >= S_window) then

doNothing();

end if;

Get_Data_From_Network_Layer();

s = Make_Frame();

[Link] = SeqN;

Store_Copy_Frame(s);

Send_Frame(s);
 Start_Timer(s);

SeqN = SeqN + 1;

end if;

if ( Event(Frame_Arrival) then

r = Receive_Acknowledgement();

//Resend frame whose sequence number is with ACK

if ( [Link] = NAK) then

if ( NAK_No > SeqFirst && NAK_No < SeqN ) then

Retransmit( [Link](NAK_No));

Start_Timer(s);

end if

//Remove frames from sending window with positive ACK

else if ( [Link] = ACK ) then

Remove_Frame([Link](SeqFirst));

Stop_Timer(s);

SeqFirst = SeqFirst + 1;

end if

end if

// Resend frame if acknowledgement haven’t been received

if ( Event(Time_Out)) then

Start_Timer(s);

Retransmit_Frame(s);

end if

end

Receiver Site Algorithm of Selective Repeat Protocol

Begin

frame f;
RSeqNo = 0; // Initialise sequence number of expected frame

NAKsent = false;

ACK = false;

For each slot in receive_window

Mark(slot)=false;

while (true) //check repeatedly

do

Wait_For_Event(); //wait for arrival of frame

if ( Event(Frame_Arrival) then

Receive_Frame_From_Physical_Layer();

if ( Corrupted ( [Link] ) AND NAKsent = false) then

SendNAK([Link]);

NAKsent = true;

end if

if ( [Link] != RSeqNo AND NAKsent = false ) then

SendNAK([Link]);

NAKsent = true;

if ( [Link] is in receive_window ) then

if ( Mark(RSeqNo) = false ) then

Store_frame([Link]);

Mark(RSeqNo) = true;

end if

end if

else

while ( Mark(RSeqNo))

Extract_Data(RSeqNo);

Deliver_Data_To_Network_Layer();
 RSeqNo = RSeqNo + 1;

Send_ACK(RSeqNo);

end while

end if

end if

end while

end

Examples of Data Link Layer Protocols

Data Link Layer protocols are generally responsible to simply ensure and confirm that the bits and bytes that are
received are identical to the bits and bytes being transferred. It is basically a set of specifications that are used
for implementation of a data link layer just above the physical layer of the Open System Interconnections (OSI)
Model.
Some Common Data Link Protocols :
There are various data link protocols that are required for Wide Area Network (WAN) and modem connections.
Logical Link Control (LLC) is a data link protocol of Local Area Network (LAN). Some of data link protocols
are given below :

1. Synchronous Data Link Protocol (SDLC) –

SDLC is basically a communication protocol for computers. It usually supports multipoint links even error
recovery or error correction also. It is usually used to carry SNA (Systems Network Architecture) traffic and is
the present precursor to HDLC. It was also designed and developed by IBM in 1975. It is also used to connect
all of the remote devices to mainframe computers at central locations may be in point-to-point (one-to-one) or
point-to-multipoint (one-to-many) connections. It is also used to make sure that the data units should arrive
correctly and with the right flow from one network point to the next network point.

2. High-Level Data Link Protocol (HDLC) –

HDLC is basically a protocol that is now assumed to be an umbrella under which many Wide Area protocols sit.
It is also adopted as a part of the X.25 network. It was originally created and developed by ISO in 1979. This
protocol is generally based on SDLC. It also provides best-effort unreliable service and also reliable service.
HDLC is a bit-oriented protocol that is applicable for point-to-point and multipoint communications.

3. Serial Line Interface Protocol (SLIP) –

SLIP is generally an older protocol that is just used to add a framing byte at the end of an IP packet. It is
basically a data link control facility that is required for transferring IP packets usually among Internet Service
Providers (ISP) and a home user over a dial-up link. It is an encapsulation of the TCP/IP especially designed to
work with over serial ports and several router connections simply for communication. It has some limitations
like it does not provide mechanisms such as error correction or error detection.

4. Point to Point Protocol (PPP) –

PPP is a protocol that is basically used to provide the same functionality as SLIP. It is the most robust protocol
that is used to transport other types of packets also along with IP Packets. It can also be required for dial-up and
leased router-router lines. It basically provides a framing method to describe frames. It is a character-oriented
protocol that is also used for error detection. It is also used to provides two protocols i.e. NCP and LCP. LCP is
used for bringing lines up, negotiation of options, bringing them down whereas NCP is used for negotiating
network-layer protocols. It is required for the same serial interfaces as that of HDLC.

5. Link Control Protocol (LCP) –

It was originally developed and created by IEEE 802.2. It is also used to provide HDLC style services on LAN
(Local Area Network). LCP is basically a PPP protocol that is used for establishing, configuring, testing,
maintenance, and ending or terminating links for transmission of data frames.

6. Link Access Procedure (LAP) –

LAP protocols are basically data link layer protocols that are required for framing and transferring data across
point-to-point links. It also includes some reliability service features. There are basically three types of LAP i.e.
LAPB (Link Access Procedure Balanced), LAPD (Link Access Procedure D-Channel), and LAPF (Link Access
Procedure Frame-Mode Bearer Services). It actually originated from IBM SDLC, which is being submitted by
IBM to the ISP simply for standardization.

7. Network Control Protocol (NCP) –

NCP was also an older protocol that was implemented by ARPANET. It basically allows users to have access to
use computers and some of the devices at remote locations and also to transfer files among two or more
computers. It is generally a set of protocols that is forming a part of PPP. NCP is always available for each and
every higher-layer protocol that is supported by PPP. NCP was replaced by TCP/IP in the 1980s.