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
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.
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

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.

Utopian Simplex Protocol

We will consider a protocol that is simply because it does not worry about the possibility of
anything going wrong. Data is transmitted in one direction only. Both transmitting and
receiving network layers are always ready. Processing time can be ignored. Infinite buffer
space is available. This thoroughly unrealistic protocol, which we will nickname “Utopia”, is
simply to show the basic structure on which we will build. Its implementation is shown below.
Utopian simplex Protocol: There is one direction of data transmission only from sender to
receiver. Here we assume the communication channel to be error-free and the receiver will
infinitely quickly process the input. The sender pumps out the data onto the line as fast as it
can.

typedef enum {frame_arrival} event_type;

#include"protocol.h"

void sender1(void)
{
frame s; /* buffer for an outbound frame */
packet buffer; /* buffer for an outbound packet */
while(true)
{
from_network_layer(&buffer); /* go get something to send */
[Link]=buffer; /* copy it into s for transmission */
to_physical_layer(&s); /* send it on its way */
}
}

void receiver1(void)
{
frame r;
event_type event; /* filled in by wait, but not used here */
while(true)
{
wait_for_event(n event); /* only possibility is frame_arrival */
from_physical_layer(&r); /* go get the inbound frame */
to_network_layer(&[Link]); /* pass the data to the network layer */
}
}
This protocol has two different procedures, a sender and a receiver. MAX_SEQ is not needed
because no sequence numbers or acknowledgements are used. The only event type possible
is frame_arrival (i.e. the arrival of an undamaged frame). The sender pumps out the data in
an infinite while loop as fast as it can. The loop body consists of three actions and they are –
● Fetch a packet from the network layer,
● Construct an outbound frame using the variable s,
● Send the frame on its way.

Other fields have to do with error and flow control and there are no errors or flow control
restrictions here so only the info field is used here. The receiver is equally simple. The
procedure wait_for_event returns when the frame arrives and the event is set to
frame_arrival. The newly arrived frame from the hardware buffer is removed by the call
from_physical_layer and put in the variable r, so that receiver can get it. The data link layer
settles back to wait for the next frame when the data portion is passed on to the network
layer, suspending itself until the frame arrives. It does not handle either flow control or error
correction therefore it is unrealistic.
Properties of Utopian Simplex Protocol:
● The design of Utopian Simplex Protocol is based on 2 procedures i.e. Sender and
Receiver.
● Both Sender and Receiver run in the data link layer but the sender runs in the data link
layer of the source machine while Receiver runs in the data link layer of the destination
machine.
● It is designed for Unidirectional data transmission.
● Sender and receiver are always ready for data processing.
● Both of them have infinite buffer space available.
● The communication links never lose any data frames.
● It is considered as unrealistic as it does not handle flow control or error correction.

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 Stop and Wait ARQ offers error and flow control, but may cause big performance issues
as the sender always waits for acknowledgement even if it has the next packet ready to send.
Consider a situation where you have a high bandwidth connection and propagation delay is
also high (you are connected to some server in some other country through a high-speed
connection), you can’t use this full speed due to limitations of stop and wait.
Sliding Window protocol handles this efficiency issue by sending more than one packet at a
time with a larger sequence number. The idea is the same as pipelining in architecture.
Few Terminologies :

Transmission Delay (Tt) – Time to transmit the packet from host to the outgoing link. If B is
the Bandwidth of the link and D is the Data Size to transmit
Tt = D/B
Propagation Delay (Tp) – It is the time taken by the first bit transferred by the host onto the
outgoing link to reach the destination. It depends on the distance d and the wave propagation
speed s (depends on the characteristics of the medium).
Tp = d/s
Efficiency – It is defined as the ratio of total useful time to the total cycle time of a packet. For
stop and wait protocol,
Total cycle time = Tt(data) + Tp(data) +
Tt(acknowledgement) + Tp(acknowledgement)
= Tt(data) + Tp(data) + Tp(acknowledgement)
= Tt + 2*Tp

Since acknowledgements are very less in size, their transmission delay can be neglected.
Efficiency = Useful Time / Total Cycle Time
= Tt/(Tt + 2*Tp) (For Stop and Wait)
= 1/(1+2a) [ Using a = Tp/Tt ]

Effective Bandwidth(EB) or Throughput – Number of bits sent per second.

EB = Data Size(D) / Total Cycle time(Tt + 2*Tp)
Multiplying and dividing by Bandwidth (B),
= (1/(1+2a)) * B [ Using a = Tp/Tt ]
= Efficiency * Bandwidth

Capacity of link – If a channel is Full Duplex, then bits can be transferred in both the
directions and without any collisions. Number of bits a channel/Link can hold at maximum is
its capacity.
Capacity = Bandwidth(B) * Propagation(Tp)

For Full Duplex channels,

Capacity = 2*Bandwidth(B) * Propagation(Tp)

Concept Of Pipelining

In Stop and Wait protocol, only 1 packet is transmitted onto the link and then the sender waits
for acknowledgement from the receiver. The problem in this setup is that efficiency is very
less as we are not filling the channel with more packets after the 1st packet has been put onto
the link. Within the total cycle time of Tt + 2*Tp units, we will now calculate the maximum
number of packets that sender can transmit on the link before getting an acknowledgement.
In Tt units ----> 1 packet is Transmitted.
In 1 unit ----> 1/Tt packet can be Transmitted.
In Tt + 2*Tp units -----> (Tt + 2*Tp)/Tt
packets can be Transmitted
------> 1 + 2a [Using a = Tp/Tt]

Maximum packets That can be Transmitted in total cycle time = 1+2*a

Let me explain now with the help of an example.
Consider Tt = 1ms, Tp = 1.5ms.
In the picture given below, after the sender has transmitted packet 0, it will immediately
transmit packets 1, 2, 3. Acknowledgement for 0 will arrive after 2*1.5 = 3ms. In Stop and
Wait, in time 1 + 2*1.5 = 4ms, we were transferring one packet only. Here we keep a window
of packets that we have transmitted but not yet acknowledged.

After we
have received the Ack for packet 0, window slides and the next packet can be assigned
sequence number 0. We reuse the sequence numbers which we have acknowledged so that
header size can be kept minimum as shown in the diagram given below.
Sliding Window Protocol is actually a theoretical concept in which we have only talked
about what should be the sender window size (1+2a) in order to increase the efficiency of
stop and wait arq. Now we will talk about the practical implementations in which we take care
of what should be the size of the receiver window. Practically it is implemented in two
protocols namely :

1. Go Back N (GBN)
2. Selective Repeat (SR)

In this article, we will explain you about the first protocol which is GBN in terms of three main
characteristic features and in the next part we will be discussing SR as well as comparison of
both these protocols

Go Back N (GBN) Protocol

The three main characteristic features of GBN are:

Sender Window Size (WS)

It is IN itself. If we say the protocol is GB10, then Ws = 10. N should be always greater than 1
in order to implement pipelining. For N = 1, it reduces to the Stop and Wait protocol.

Efficiency Of GBN = N/(1+2a)

where a = Tp/Tt
If B is the bandwidth of the channel, then
Effective Bandwidth or Throughput
= Efficiency * Bandwidth
 = (N/(1+2a)) * B

Receiver Window Size (WR)

WR is always 1 in GBN. Now what exactly happens in GBN, we will explain with the help of an
example. Consider the diagram given below. We have a sender window size of 4. Assume
that we have lots of sequence numbers just for the sake of explanation. Now the sender has
sent the packets 0, 1, 2 and 3. After acknowledging the packets 0 and 1, receiver is now
expecting packet 2 and sender window has also slided to further transmit the packets 4 and 5.
Now suppose the packet 2 is lost in the network, Receiver will discard all the packets which
the sender has transmitted after packet 2 as it is expecting sequence number 2. On the
sender side for every packet sent there is a time out timer which will expire for packet number
2. Now from the last transmitted packet 5 sender will go back to the packet number 2 in the
current window and transmit all the packets till packet number 5. That’s why it is called Go
Back N. Go back means sender has to go back N places from the last transmitted packet in
the unacknowledged window and not from the point where the packet is lost.

Acknowledgements
There are 2 kinds of acknowledgements namely:
● Cumulative Ack: One acknowledgement is used for many packets. The main
advantage is less traffic. A disadvantage is less reliability as if one ack is the loss that would
mean that all the packets sent are lost.
● Independent Ack: If every packet is going to get acknowledgement independently.
Reliability is high here but a disadvantage is that traffic is also high since for every packet we
are receiving independent ack.
GBN uses Cumulative Acknowledgement. At the receiver side, it starts an
acknowledgement timer whenever the receiver receives any packet which is fixed and when it
expires, it is going to send a cumulative Ack for the number of packets received in that
interval of timer. If the receiver has received N packets, then the Acknowledgement number
will be N+1. Important point is that the Acknowledgement timer will not start after the expiry of
the first timer but after the receiver has received a packet.
Time out timer at the sender side should be greater than the Acknowledgement timer.
Relationship Between Window Sizes and Sequence Numbers
We already know that sequence numbers required should always be equal to the size of
window in any sliding window protocol.
Minimum sequence numbers required in GBN = N + 1
Bits Required in GBN = ceil(log2 (N + 1))

The extra 1 is required in order to

avoid the problem of duplicate packets
as described below.
Example: Consider an example of GB4.
● Sender window size is 4 therefore we require a minimum of 4 sequence numbers to
label each packet in the window.
● Now suppose the receiver has received all the packets(0, 1, 2 and 3 sent by sender)
and hence is now waiting for packet number 0 again (We can not use 4 here as we have only
4 sequence numbers available since N = 4).
● Now suppose the cumulative back for the above 4 packets is lost in the network.
● On the sender side, there will be a timeout for packet 0 and hence all the 4 packets will
be transmitted again.
● Problem now is that the receiver is waiting for a new set of packets which should have
started from 0 but now it will receive the duplicate copies of the previously accepted packets.
● In order to avoid this, we need one extra sequence number.
● Now the receiver could easily reject all the duplicate packets which were starting from 0
because now it will be waiting for packet number 4 (We have added an extra sequence
number now).

This is explained with the help of the illustrations below.

Trying with Sequence numbers 4.

Now Try with one extra Sequence Number.

Now it is clear as to why we need an extra 1 bit in the GBN protocol.
Why Selective Repeat Protocol? The go-back-n protocol works well if errors are less, but if
the line is poor it wastes a lot of bandwidth on retransmitted frames. An alternative strategy,
the selective repeat protocol, is to allow the receiver to accept and buffer the frames following
a damaged or lost one. Selective Repeat attempts to retransmit only those packets that are
actually lost (due to errors) :
● Receiver must be able to accept packets out of order.
● Since the receiver must release packets to higher layers in order, the receiver must be
able to buffer some packets.

Retransmission requests :
● Implicit – The receiver acknowledges every good packet, packets that are not ACKed
before a time-out are assumed lost or in [Link] that this approach must be used to be
sure that every packet is eventually received.
● Explicit – An explicit NAK (selective reject) can request retransmission of just one
packet. This approach can expedite the retransmission but is not strictly needed.
● One or both approaches are used in practice.

Selective Repeat Protocol (SRP) : This protocol(SRP) is mostly identical to GBN protocol,
except that buffers are used and the receiver, and the sender, each maintains a window of
size. SRP works better when the link is very unreliable. Because in this case, retransmission
tends to happen more frequently, selectively retransmitting frames is more efficient than
retransmitting all of them. SRP also requires a full-duplex link. backward acknowledgements
are also in progress.
● Sender’s Windows ( Ws) = Receiver’s Windows ( Wr).
● Window size should be less than or equal to half the sequence number in SR protocol.
This is to avoid packets being recognized incorrectly. If the size of the window is greater than
half the sequence number space, then if an ACK is lost, the sender may send new packets
that the receiver believes are retransmissions.
● Senders can transmit new packets as long as their number is with W of all unACKed
packets.
● Sender retransmits un-ACKed packets after a timeout – Or upon a NAK if NAK is
employed.
● Receiver ACKs all correct packets.
● Receiver stores correct packets until they can be delivered in order to the higher layer.
● In Selective Repeat ARQ, the size of the sender and receiver window must be at most
one-half of 2^m.

Figure – the sender only retransmits frames, for which a NACK is receivedEfficiency of
Selective Repeat Protocol (SRP) is same as GO-Back-N’s efficiency :
Efficiency = N/(1+2a)
Where a = Propagation delay / Transmission delay
Buffers = N + N
Sequence number = N(sender side) + N ( Receiver Side)
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 :

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.

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.