Module 3

Data Link Layer

CSC503.3 - Analyze algorithms for error detection, error
correction, multiple access control and identify IP Addressing.

Compiled By Mrs. Soniya Khatu

Data Link Layer
3.1 DLL Design Issues (Services, Framing, Error Control, Flow
Control), Error Detection and Correction(Hamming Code, CRC,
Checksum) , Elementary Data Link protocols , Stop and Wait,
Sliding Window(Go Back N, Selective Repeat)

3.2 Medium Access Control sublayer

Channel Allocation problem, Multiple access Protocol( Aloha,
Carrier Sense Multiple Access (CSMA/CD)

Compiled By Mrs. Soniya Khatu

Data Link Layer
• The communication channel that connects the adjacent nodes is known as
links, and to move the datagram from source to the destination, the datagram
must be moved across an individual link.
• The main responsibility of the Data Link Layer is to transfer the datagram
across an individual link.
• The Data link layer protocol defines the format of the packet exchanged
across the nodes as well as the actions such as Error detection,
retransmission, flow control, and random access.
• The Data Link Layer protocols are Ethernet, token ring, FDDI and PPP.
• An important characteristic of a Data Link Layer is that datagram can be
handled by different link layer protocols on different links in a path.
• For example, the datagram is handled by Ethernet on the first link, PPP on
the second link.
Compiled By Mrs. Soniya Khatu
DLL Design Issues

Compiled By Mrs. Soniya Khatu

Data Link Layer
➢Providing services to the network layer:

1) Unacknowledged connectionless service - Appropriate for low error rate

and real-time traffic. Ex: Ethernet

2) Acknowledged connectionless service- Useful in unreliable channels, WiFi.

Ack/Timer/Resend

3) Acknowledged connection-oriented service- Guarantee frames are received

exactly once and in the right order. Appropriate over long, unreliable links
such as a satellite channel or a long-distance telephone circuit.

Compiled By Mrs. Soniya Khatu

Data Link Layer
➢Framing & Link access:

• Data Link Layer protocols encapsulate each network frame within a

Link layer frame before the transmission across the link.
• A frame consists of a data field in which network layer datagram is
inserted and a number of data fields.
• It specifies the structure of the frame as well as a channel access
protocol by which frame is to be transmitted over the link.

Compiled By Mrs. Soniya Khatu

Data Link Layer
➢Reliable delivery:

• Data Link Layer provides a reliable delivery service, i.e., transmits the
network layer datagram without any error.
• A reliable delivery service is accomplished with transmissions and
acknowledgements.
• A data link layer mainly provides the reliable delivery service over the
links as they have higher error rates and they can be corrected locally,
link at which an error occurs rather than forcing to retransmit the data.

Compiled By Mrs. Soniya Khatu

Data Link Layer
➢Flow control:

• A receiving node can receive the frames at a faster rate than it can
process the frame.
• Without flow control, the receiver's buffer can overflow, and frames
can get lost.
• To overcome this problem, the data link layer uses the flow control to
prevent the sending node on one side of the link from overwhelming
the receiving node on another side of the link.

Compiled By Mrs. Soniya Khatu

Data Link Layer
➢Error detection:

• Errors can be introduced by signal attenuation and noise.

• Data Link Layer protocol provides a mechanism to detect one or more
errors.
• This is achieved by adding error detection bits in the frame and then
receiving node can perform an error check.

Compiled By Mrs. Soniya Khatu

Data Link Layer

➢Error correction:

• Error correction is similar to the Error detection, except that receiving

node not only detect the errors but also determine where the errors
have occurred in the frame.

Compiled By Mrs. Soniya Khatu

Data Link Layer
➢Half-Duplex & Full-Duplex:

• In a Full-Duplex mode, both the nodes can transmit the data at the
same time.
• In a Half-Duplex mode, only one node can transmit the data at the
same time.

Compiled By Mrs. Soniya Khatu

Framing
• Framing is the function of a data
link layer that provides a way for a
sender to transmit a set of bits that
are meaningful to the receiver.

• The Frame contains the following

−

1. Frame Header
2. Payload field for holding packet
3. Frame Trailer

Compiled By Mrs. Soniya Khatu

Framing

• To provide service to the network layer, the data link layer must use
the service provided to it by the physical layer.
• What the physical layer does is accept a raw bit stream and attempt to
deliver it to the destination.
• This bit stream is not guaranteed to be error free.
• The number of bits received may be less than, equal to, or more than
the number of bits transmitted, and they may have different values.

Compiled By Mrs. Soniya Khatu

Framing
• It is up to the data link layer to detect and, if necessary, correct errors.
• The usual approach is for the data link layer to break the bit stream up
into discrete frames and compute the checksum for each frame
(framing).
• When a frame arrives at the destination, the checksum is recomputed.
• If the newly computed checksum is different from the one contained in
the frame, the data link layer knows that an error has occurred and
takes steps to deal with it (e.g., discarding the bad frame and possibly
also sending back an error report).

Compiled By Mrs. Soniya Khatu

Framing
➢Four framing methods:

1. Character count.

2. Flag bytes with byte stuffing.

3. Starting and ending flags, with bit stuffing.

4. Physical layer coding violations.

Compiled By Mrs. Soniya Khatu

Framing – 1. Character \ Byte Count
• 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.
• 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
doesnot have a means (in this algorithm) how to correct it.

Compiled By Mrs. Soniya Khatu

Framing – Character \ Byte Count
• This method uses a field in the header to specify the number of
characters in the frame.

• When the data link layer at the destination sees the character count, it
knows how many characters follow and hence where the end of the
frame is.

• This technique is shown in Fig. for four frames of sizes 5, 5, 8, and 8

characters, respectively.

Compiled By Mrs. Soniya Khatu

Framing – Character \ Byte Count

Compiled By Mrs. Soniya Khatu

Framing – Character \ Byte Count
• The trouble with this algorithm is that the count can be garbled by a
transmission error.
• For example, if the character count of 5 in the second frame of Fig.
becomes a 7, the destination will get out of synchronization and will be
unable to locate the start of the next frame.
• Even if the checksum is incorrect so the destination knows that the frame
is bad, it still has no way of telling where the next frame starts.
• Sending a frame back to the source asking for a retransmission does not
help either, since the destination does not know how many characters to
skip over to get to the start of the retransmission.
• For this reason, the character count method is rarely used anymore.
Compiled By Mrs. Soniya Khatu
Framing – 2. Flag bytes with byte stuffing
• This method gets around the problem of resynchronization after an error by
having each frame start and end with special bytes.

• In the past, the starting and ending bytes were different, but in recent years
most protocols have used the same byte, called a flag byte, as both the
starting and ending delimiter, as shown in Fig. as FLAG.

• In this way, if the receiver ever loses synchronization, it can just search for
the flag byte to find the end of the current frame.

• Two consecutive flag bytes indicate the end of one frame and start of the
next one.
Compiled By Mrs. Soniya Khatu
Framing – 2. Flag bytes with byte stuffing
• 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.
Compiled By Mrs. Soniya Khatu
Framing – 2. Flag bytes with byte stuffing
• 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.

Compiled By Mrs. Soniya Khatu
Framing – 2. Flag bytes with byte stuffing

• A frame delimited by flag bytes.

• Four examples of byte sequences
Compiled Bybefore and after byte stuffing
Mrs. Soniya Khatu
Compiled By Mrs. Soniya Khatu
Framing – 2. Flag bytes with byte stuffing
➢ Use reserved characters to indicate the start and end of a frame. For
instance, use the two-character sequence DLE STX (Data-Link
Escape, Start of TeXt) to signal the beginning of a frame, and the
sequence DLE ETX (End of TeXt) to flag the frame's end.

➢ The second framing method, Starting and ending character stuffing,

gets around the problem of resynchronization after an error by having
each frame start with the ASCII character sequence DLE STX and
end with the sequence DLE ETX.

Compiled By Mrs. Soniya Khatu

Framing – 2. Flag bytes with byte stuffing
• Problem: What happens if the two-character sequence DLE ETX
happens to appear in the frame itself?
• Solution:

• Use character stuffing; within the frame, replace every occurrence of DLE with
the two-character sequence DLE DLE. The receiver reverses the processes,
replacing every occurrence of DLE DLE with a single DLE.

• Example:
• If the frame contained ``A B DLE D E DLE'', the characters transmitted over the
channel would be ``DLE STX A B DLE DLE D E DLE DLE DLE ETX''.

Compiled By Mrs. Soniya Khatu

Framing - Flag bytes with byte stuffing

Compiled By Mrs. Soniya Khatu

Framing - Flag bytes with byte stuffing

• A frame delimited by flag bytes.

• Four examples of byte sequences
Compiled Bybefore and after byte stuffing
Mrs. Soniya Khatu
Framing – 2. Flag bytes with byte stuffing

Compiled By Mrs. Soniya Khatu

Framing – 2. Flag bytes with byte stuffing

Disadvantage:

Character is the smallest unit that can be operated on; not all
architectures are byte oriented.

Compiled By Mrs. Soniya Khatu

 Framing – 3. Starting and ending flags, with bit
stuffing
• This technique allows data frames to contain an arbitrary number of
bits and allows character codes with an arbitrary number of bits per
character.

• It works like this. Each frame begins and ends with a special bit
pattern, 01111110 (in fact, a 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.

Compiled By Mrs. Soniya Khatu

Framing – 3. Starting and ending flags, with bit
stuffing

• This bit stuffing is analogous to byte stuffing, in which an escape byte

is stuffed into the outgoing character stream before a flag byte in the
data.

• When the receiver sees five consecutive incoming 1 bits, followed by

a 0 bit, it automatically destuffs (i.e., deletes) the 0 bit

Compiled By Mrs. Soniya Khatu

Framing – 3. Starting and ending flags, with bit
stuffing

Bit stuffing
(a) The original data.
(b) The data as they appear on the line.
(c) The data as they are stored in receiver’s memory after destuffing.
Compiled By Mrs. Soniya Khatu
Framing – 3. Starting and ending flags, with bit
stuffing

Compiled By Mrs. Soniya Khatu

Framing – 4. Physical layer coding violations
• This method of framing is only applicable to networks in which the
encoding on the physical medium contains some redundancy.

• For example, some LANs encode 1 bit of data by using 2 physical bits.
Normally, a 1 bit is a high-low pair and a 0 bit is a low-high pair.

• The scheme means that every data bit has a transition in the middle,
making it easy for the receiver to locate the bit boundaries.

• The combinations high-high and low-low are not used for data but are
used for delimiting frames in some protocols.
Compiled By Mrs. Soniya Khatu
Framing – 4. Physical layer coding violations

Compiled By Mrs. Soniya Khatu

Framing – 4. Physical layer coding violations
• As a final note on framing, many data link protocols use combination
of a character count with one of the other methods for extra safety.

• When a frame arrives, the count field is used to locate the end of the
frame.

• Only if the appropriate delimiter is present at that position and the

checksum is correct is the frame accepted as valid.

• Otherwise, the input stream is scanned for the next delimiter.

Compiled By Mrs. Soniya Khatu
Error Control

Compiled By Mrs. Soniya Khatu

Error Control

• 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 travelling from sender to receiver.

• That means a 0 bit may change to 1 or a 1 bit may change to 0.

Compiled By Mrs. Soniya Khatu

Error Control
• When data-frame is transmitted, there is a probability that data-frame may
be lost in the transit, or it is received corrupted.

• In both cases, the receiver does not receive the correct data-frame and
sender does not know anything about any loss.

• In such case, both sender and receiver are equipped with some protocols
which helps them to detect transit errors such as loss of data-frame.

• Hence, either the sender retransmits the data-frame or the receiver may
request to resend the previous data-frame.
Compiled By Mrs. Soniya Khatu
Error Control
• Error control in data link layer is the process of detecting and
correcting data frames that have been corrupted or lost during
transmission.
• In case of lost or corrupted frames, the receiver does not receive the
correct data-frame and sender is ignorant about the loss.
• Data link layer follows a technique to detect transit errors and take
necessary actions, which is retransmission of frames whenever error is
detected or frame is lost.
• The process is called Automatic Repeat Request (ARQ).

Compiled By Mrs. Soniya Khatu

 Error Control - Phases in Error Control
The error control mechanism in data link layer involves the following phases −

• Detection of Error −
Transmission error, if any, is detected by either the sender or the receiver.

• Acknowledgment − acknowledgment may be positive or negative.

• Positive ACK −
On receiving a correct frame, the receiver sends a positive acknowledge.

• Negative ACK −
On receiving a damaged frame or a duplicate frame, the receiver sends a negative
acknowledgment back to the sender.

Compiled By Mrs. Soniya Khatu

 Error Control - Phases in Error Control

• Retransmission −

• The sender maintains a clock and sets a timeout period.

• If an acknowledgment of a data-frame previously transmitted does not

arrive before the timeout, or a negative acknowledgment is received, the
sender retransmits the frame.

Compiled By Mrs. Soniya Khatu

Error Control
• Types of Errors
1. Single-Bit Error
• A single-bit error refers to a type of data transmission error that occurs when
one bit (i.e., a single binary digit) of a transmitted data unit is altered during
transmission, resulting in an incorrect or corrupted data unit.

Compiled By Mrs. Soniya Khatu

Error Control
2. Multiple-Bit Error
• A multiple-bit error is an error type that arises when more than one bit
in a data transmission is affected. Although multiple-bit errors are
relatively rare when compared to single-bit errors, they can still occur,
particularly in high-noise or high-interference digital environments.

Compiled By Mrs. Soniya Khatu

Error Control
3. Burst Error
• When several consecutive bits are flipped mistakenly in digital
transmission, it creates a burst error. This error causes a sequence of
consecutive incorrect values.

Compiled By Mrs. Soniya Khatu

Error Control
• Error Detection Methods
To detect errors, a common technique is to introduce redundancy bits
that provide additional information.

Various techniques for error detection include:

1) Simple Parity Check

2) Two-Dimensional Parity Check
3) Checksum
4) Cyclic Redundancy Check (CRC)
Compiled By Mrs. Soniya Khatu
Error Control – 1. Simple Parity Check
• Simple-bit parity is a simple error detection method that involves
adding an extra bit to a data transmission.

• It works as:
• 1 is added to the block if it contains an odd number of 1’s, and 0 is
added if it contains an even number of 1’s

• This scheme makes the total number of 1’s even, that is why it is
called even parity checking.

Compiled By Mrs. Soniya Khatu

Error Control – 1. Simple Parity Check

Compiled By Mrs. Soniya Khatu

Error Control – 1. Simple Parity Check
• Advantages of Simple Parity Check
1. Simple parity check can detect all single bit error.
2. Simple parity check can detect an odd number of errors.
3. Implementation: Simple Parity Check is easy to implement in both
hardware and software.
4. Minimal Extra Data: Only one additional bit (the parity bit) is added
per data unit (e.g., per byte).
5. Fast Error Detection: The process of calculating and checking the
parity bit is quick, which allows for rapid error detection without
significant delay in data processing or communication.
6. Single-Bit Error Detection: It can effectively detect single-bit errors
within a data unit, providing a basic level of error detection for
relatively low-error environments.
Compiled By Mrs. Soniya Khatu
Error Control – 1. Simple Parity Check
• Disadvantages of Simple Parity Check
1. Single Parity check is not able to detect even no. of bit error.

For example, the Data to be transmitted is 101010.

Codeword transmitted to the receiver is 1010101 (we have used even parity).
Let’s assume that during transmission, two of the bits of code word flipped to
1111101.
On receiving the code word, the receiver finds the no. of ones to be even and
hence no error, which is a wrong assumption.

Compiled By Mrs. Soniya Khatu

Error Control –2. Two-Dimensional Parity
Check
• Two-dimensional 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.

Compiled By Mrs. Soniya Khatu

Error Control – 2. Two-Dimensional Parity
Check

Compiled By Mrs. Soniya Khatu

Error Control –2. Two-Dimensional Parity
Check
• Advantages of Two-Dimensional Parity Check

1. Two-Dimensional Parity Check can detect and correct all single bit
error.

2. Two-Dimensional Parity Check can detect two or three bit error that
occur any where in the matrix.

Compiled By Mrs. Soniya Khatu

Error Control –2. Two-Dimensional Parity
Check
• Disadvantages of Two-Dimensional Parity Check

1. Two-Dimensional Parity Check can not correct two or three bit error.
It can only detect two or three bit error.

2. If we have a error in the parity bit then this scheme will not work.

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum
• Checksum error detection is a method used to identify errors in
transmitted data.

• The process involves dividing the data into equally sized segments and
using a 1’s complement to calculate the sum of these segments.

• The calculated sum is then sent along with the data to the receiver.

• At the receiver’s end, the same process is repeated and if all zeroes are
obtained in the sum, it means that the data is correct.
Compiled By Mrs. Soniya Khatu
Error Control- 3. Checksum
• Checksum – Operation at Sender’s Side

1. Firstly, the data is divided into k segments each of m bits.

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

3. The checksum segment is sent along with the data segments.

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum
• Checksum – Operation at Receiver’s Side

1. At the receiver’s end, all received segments are added using 1’s
complement arithmetic to get the sum. The sum is complemented.

2. If the result is zero, the received data is accepted; otherwise

discarded.

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum

Compiled By Mrs. Soniya Khatu

Error Control- 3.
Checksum

Compiled By Mrs. Soniya Khatu

Error Control- 3.
Checksum

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum
•

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum

Consider the data unit to be transmitted is-

10011001111000100010010010000100

Consider 8-bit checksum is used.

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum
• An IoT temperature sensor sends a data packet every minute to a
central monitoring server. Each packet contains three 4-bit values. To
detect any transmission errors due to interference, the system uses a 4-
bit checksum. Data Stream 010110011100.

Problem:
1. Compute the checksum at the sender side.
2. Add checksum and send the full message.
3. At the receiver, check if the message 0101 1001 1100 0010 has any
errors.

Compiled By Mrs. Soniya Khatu

Error Control- 3. Checksum
• A university’s student management system sends student ID data over
a network. Each ID is split into 8-bit segments and validated using
checksum. Student ID Binary Segments:
01001011 01100010 11010100
Problem:
1. Generate the checksum for the above ID packet.
2. Simulate the receiver getting this packet correctly. Show
verification.
3. If Segment 1 is received as 01011011, show how the system detects
the error.
Compiled By Mrs. Soniya Khatu
Error Control- 3. Checksum
• More Examples

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
CRC is a redundancy error technique used to determine the error.

Following are the steps used in CRC for error detection:

•In CRC technique, a string of n 0s is appended to the data unit, and this n
number is less than the number of bits in a predetermined number, known as
division which is n+1 bits.

•Secondly, the newly extended data is divided by a divisor using a process is

known as binary division. The remainder generated from this division is
known as CRC remainder.
Compiled By Mrs. Soniya Khatu
Error Control- CRC (Cyclic Redundancy Code)
•Thirdly, the CRC remainder replaces the appended 0s at the end of the
original data. This newly generated unit is sent to the receiver.

•The receiver receives the data followed by the CRC remainder.

The receiver will treat this whole unit as a single unit, and it is divided by
the same divisor that was used to find the CRC remainder.

If the resultant of this division is zero which means that it has no error, and
the data is accepted.
If the resultant of this division is not zero which means that the data consists
of an error. Therefore, the data is discarded.
Compiled By Mrs. Soniya Khatu
Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
Suppose the original data is 11100 and divisor is 1001.

CRC Generator

• A CRC generator uses a modulo-2 division.

• Firstly, three zeroes are appended at the end of the data as the length of the divisor is 4
and we know that the length of the string 0s to be appended is always one less than the
length of the divisor.
• Now, the string becomes 11100000, and the resultant string is divided by the divisor
1001.
• The remainder generated from the binary division is known as CRC remainder.
• The generated value of the CRC remainder is 111.
• CRC remainder replaces the appended string of 0s at the end of the data unit, and the
final string would be 11100111 which is sent across the network.
Compiled By Mrs. Soniya Khatu
Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
CRC Checker

• The functionality of the CRC checker is like the CRC generator.

• When the string 11100111 is received at the receiving end, then CRC
checker performs the modulo-2 division.

• A string is divided by the same divisor, i.e., 1001.

• In this case, CRC checker generates the remainder of zero. Therefore, the
data is accepted.

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
Consider the CRC generator is x7 + x6 + x4 + x3 + x + 1.

The corresponding binary pattern is obtained as-

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy
Code)
• The Data bits to be transmitted – 101001101 and
given Divisor – 110101

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy
Code)
• The Data bits to be transmitted – 101001101 and
given Divisor – 110101
N= 6 N -1= 5

Append 5 zeros to the given data

i.e 10100110100000
Compiled By Mrs. Soniya Khatu
Error Control- CRC (Cyclic Redundancy
Code)
• Data bits to be transmitted –
101001101
• Divsor - 110101

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy
Code)
• A bit stream 1010000 is transmitted using the standard CRC method.
The generator polynomial is X3+1.
• What is the actual bit string transmitted?

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
A bit stream 1101011011 is transmitted using the standard CRC method. The
generator polynomial is x4+x+1.
What is the actual bit string transmitted is correct or not?

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
A bit stream 1101011011 is transmitted using the standard CRC method. The
generator polynomial is x4+x+1. What is the actual bit string transmitted?

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
A bit stream 10011101 is transmitted using the standard CRC method. The generator
polynomial is x3+1.

1. What is the actual bit string transmitted?

2. Suppose the third bit from the left is inverted during transmission. How will
receiver detect this error?

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
A bit stream 10011101 is
transmitted using the standard
CRC method. The generator
polynomial is x3+1.

1. What is the actual bit string

transmitted?

2. Suppose the third bit from

the left is inverted during
transmission. How will the
receiver detect this error?
Compiled By Mrs. Soniya Khatu
Error Control- CRC (Cyclic Redundancy Code)
A bit stream 10011101 is transmitted using the standard CRC method. The
generator polynomial is x3+1.

1. What is the actual bit string transmitted?

2. Suppose the third bit from the left is inverted during transmission. How
will the receiver detect this error?

The code word to be transmitted is obtained by replacing the last 3 zeroes

of 10011101000 with the CRC.
Thus, the code word transmitted to the receiver = 10011101100.

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)
A bit stream 10011101 is transmitted
using the standard CRC method. The
generator polynomial is x3+1.

1. What is the actual bit string

transmitted?
2. Suppose the third bit from the left
is inverted during transmission.
How will the receiver detect this
error?

Compiled By Mrs. Soniya Khatu

Error Control- CRC (Cyclic Redundancy Code)

Compiled By Mrs. Soniya Khatu

Error Control- Error Correction
• Error Correction codes are used to detect and correct the errors when data is
transmitted from the sender to the receiver.
• Error Correction can be handled in two ways:
• Backward error correction: Once the error is discovered, the receiver requests
the sender to retransmit the entire data unit.
• Forward error correction: In this case, the receiver uses the error-correcting
code which automatically corrects the errors.
• A single additional bit can detect the error , but cannot correct it.
• For correcting the errors, one has to know the exact position of the error.
• For example: If we want to calculate a single-bit error, the error correction code
will determine which one of seven bits is in error. To achieve this, we have to add
some additional redundant bits.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code

Compiled By Mrs. Soniya Khatu

What is Hamming Code?
➢ Invented by Richard Hamming (1950).
➢ Linear error-correcting code for single-bit error correction and
double-bit error detection.
➢ Used in digital communication, computer memory (ECC RAM), and
data storage.

Key Features
➢ Corrects 1-bit errors, detects 2-bit errors.
➢ Uses parity bits at positions 2i−1 (1, 2, 4, 8, ...).
➢ For m parity bits: supports up to 2m − m − 1 data bits.
Compiled By Mrs. Soniya Khatu
Error Correction – Hamming Code
• Parity bits: The bit that is appended to the original data of binary bits
so that the total number of 1s is even or odd.

• Even parity: To check for even parity, if the total number of 1s is

even, then the value of the parity bit is 0. If the total number of 1s
occurrences is odd, then the value of the parity bit is 1.

• Odd Parity: To check for odd parity, if the total number of 1s is even,
then the value of the parity bit is 1. If the total number of 1s is odd,
then the value of the parity bit is 0.
Compiled By Mrs. Soniya Khatu
Error Correction – Hamming Code
• Suppose r is the number of redundant bits and d is the total number of the
data bits.
• The number of redundant bits r can be calculated by using the formula:
2r > =d+r+1
• The value of r is calculated by using the above formula. For example, if the
value of d is 4, then the possible smallest value that satisfies the above
relation would be 3.

• To determine the position of the bit which is in error, a technique developed

by R.W Hamming is Hamming code which can be applied to any length of
the data unit and uses the relationship between data units and redundant
units.
Compiled By Mrs. Soniya Khatu
Error Correction – Hamming Code
• Algorithm of Hamming code:

1. An information of 'd' bits are added to the redundant bits 'r' to form
d+r.
2. The location of each of the (d+r) digits is assigned a decimal value.
3. The 'r' bits are placed in the positions 1,2,.....2k-1.
4. At the receiving end, the parity bits are recalculated.
5. The decimal value of the parity bits determines the position of an
error.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
Steps

• Determine number of parity bits (m):

For k data bits, 2m − m − 1 ≥ k.
• Place data bits in non-power-of-2 positions
(e.g., 3, 5, 6, 7 for (7,4) code).
• Calculate parity bits using even parity:
• Parity bit at 2i−1 checks positions where the i-th bit is 1 in their
binary representation.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
• Advantages:
• Simple and efficient for single-bit error correction.
• No retransmission needed for single errors.
• Widely used in ECC memory and communication systems.

• Limitations:
• Corrects only single-bit errors.
• Detects (but cannot correct) double-bit errors.
• Inefficient for large data (requires more parity bits).
• Not suitable for burst errors without modifications.
Compiled By Mrs. Soniya Khatu
Error Correction – Hamming Code
• Hamming code is a powerful yet simple method for error detection and
correction.
• Ideal for single-bit errors in digital systems.
• Understanding its encoding and decoding processes is key to
implementing error correction.
• Variants like extended Hamming enhance its capabilities.
• Questions? Explore implementations in Python, C++, or hardware!
• Not suitable for burst errors without modifications.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
• Relationship b/w Error position & binary number.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
Example: Encoding (7,4) Hamming Code
Data bits: 1011 (D7=1, D6=0, D5=1, D3=1)

Positions: P1 (1), P2 (2), D1 (3), P3 (4), D2 (5), D3 (6), D4 (7).

Calculate Parity:

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
Example: Decoding (No Error)

Received codeword: 0110011

Check P1 (1,3,5,7): Bits 0,1,0,1 → 2 ones (even) → P1=0.

Check P2 (2,3,6,7): Bits 1,1,1,1 → 4 ones (even) → P2=0.
Check P3 (4,5,6,7): Bits 0,0,1,1 → 2 ones (even) → P3=0.

Syndrome: 000 (decimal 0) → No error.

Data bits (3,5,6,7): 1011.

Compiled By Mrs. Soniya Khatu
Error Correction – Hamming Code
Example 3: Decoding (Single-Bit Error)

Received codeword: 0111011 (Error at position 4: 0 → 1)

Check P1 (1,3,5,7): Bits 0,1,0,1 → 2 ones (even) → P1=0.
Check P2 (2,3,6,7): Bits 1,1,1,1 → 4 ones (even) → P2=0.
Check P3 (4,5,6,7): Bits 1,0,1,1 → 3 ones (odd) → P3=1.
Syndrome: 100 (decimal 4) → Error at position 4.
Correct: Flip bit 4 (1 → 0) → 0110011.
Data: 1011.
Compiled By Mrs. Soniya Khatu
Error Correction – Hamming Code
Q1. A 7- bit hamming code word received by a receiver is 1011011.
Assuming the even parity state the received is correct or wrong. If wrong
locate the bit having error.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
Q1. A 7- bit hamming code word received by a receiver is 1011011.
Assuming the even parity state the received is correct or wrong. If wrong
locate the bit having error.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
Q2. Find the Hamming code for binary bit 1 0 0 0. Consider even parity
bits

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
Q3. Hamming code as 1 0 0 1 0 1 1. Now let us find the error position
when the code received is 1 0 0 1 111

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
• Q4. You have a 4-bit data word "1001" that needs to be transmitted
using a 7-bit Hamming code.
1.Determine the positions of the parity bits.
2.Calculate the values of the parity bits.
3.Construct the final 7-bit Hamming code.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
• Q5. A 7-bit Hamming code "1101010" is received by the receiver.
1.Identify whether there is an error in the received bit string.
2.If an error is detected, determine its position.
3.Correct the error and provide the corrected bit string.

Compiled By Mrs. Soniya Khatu

Error Correction – Hamming Code
• Q6. You receive a 7-bit Hamming code "1001101".
1.Check for any errors in the received code.
2.If an error is found, correct it.
3.Extract the original 4-bit data after correction.

Compiled By Mrs. Soniya Khatu

 Module 3
Data Link Layer
CSC503.3 - Analyze algorithms for error detection, error
correction, multiple access control and identify IP Addressing.

Compiled By Mrs. Soniya Khatu

Flow Control

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols

Compiled By Mrs. Soniya Khatu

 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 bit - streams from physical layer into
data frames whose size ranges from a few hundred to a few thousand
bytes.

• Error control mechanisms deals 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.
Compiled By Mrs. Soniya Khatu
 Elementary Data Link protocols
• 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.
• Protocols in Noiseless and Noisy Channel
• The study of protocols is divided into two categories:

1. Those that can be applied to channels with no noise or errors and those
that can be applied to channels with noise or errors.

2. Although the first group of protocols cannot be applied in real-world

situations, they provide a foundation for protocols for noisy channels.
Compiled By Mrs. Soniya Khatu
Elementary Data Link protocols

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
• Simplex Protocol
➢The Simplex protocol is 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 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.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
• Simplex Protocol

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
Stop – and – Wait Protocol
Stop – and – Wait protocol is for noiseless
channel 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.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
Stop – and – Wait Protocol

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
STOP-AND-WAIT ARQ Protocol

The Stop and Wait protocol is a

protocol used for reliable data
transmission over a noisy channel.

In this protocol, the sender only sends

one frame at a time and waits for an
acknowledgment (ACK) from the
receiver before sending the next
frame.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
STOP-AND-WAIT ARQ Protocol

This helps to ensure that the receiver

receives the data correctly and
eliminates the need for retransmission
in the case of errors caused by the
noisy channel.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
STOP-AND-WAIT ARQ Protocol

The sender continuously monitors

the channel for errors, and if an
error is detected, it waits for the next
ACK before resending the frame.
This protocol adds error control to
the basic unidirectional
communication of data frames and
ACK frames in the opposite
direction.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
STOP-AND-WAIT
ARQ Protocol

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
STOP-AND-WAIT ARQ Protocol

Flow Diagram
• A data flow diagram in the Stop-and-Wait protocol in a noisy channel can be
used to describe the flow of data between the sender and the receiver. This
diagram generally includes the following components:

➢Sender: The sender sends data frames one at a time and waits for a response
(ACK or NACK) from the receiver before sending the next data frame.

➢Receiver: The receiver receives the data frames and processes them. If the
frame is received correctly, the receiver sends an ACK signal to the sender. If
the frame is not received correctly, the receiver sends a NACK signal to the
sender.
Compiled By Mrs. Soniya Khatu
 Elementary Data Link protocols
STOP-AND-WAIT ARQ Protocol
Flow Diagram

➢Noisy Channel: The noisy channel is the medium through which the data
frames are transmitted from the sender to the receiver. The channel can add
noise to the data frames, resulting in errors and corruption of the data.

➢Error Detection: The receiver uses error detection techniques such as

checksums to detect errors in the received data frames.

➢Error Correction: If an error is detected, the receiver sends a NACK signal to

the sender, requesting a retransmission of the frame.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
STOP-AND-WAIT ARQ Protocol

In this protocol, the sender only sends one data frame at a time and waits
for a response from the receiver before sending the next frame.
This ensures that the receiver has enough time to process each frame before
receiving the next one.
The Stop-and-Wait protocol is reliable, but has low throughput compared
to other protocols.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
STOP-AND-WAIT ARQ Protocol

• In this protocol, the sender only sends one data frame at a time and waits
for a response from the receiver before sending the next frame.

• This ensures that the receiver has enough time to process each frame
before receiving the next one.

• The Stop-and-Wait protocol is reliable, but has low throughput compared

to other protocols.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols:
Sliding window

The sliding window protocol is the flow control protocol for noisy
channels that allows the sender to send multiple frames even before
acknowledgments are received.

It is called a Sliding window because the sender slides its window upon
receiving the acknowledgments for the sent frames.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols:
Working:

• The sender and receiver have a “window” of frames. A window is a

space that consists of multiple bytes.
• The size of the window on the receiver side is always 1.
• Each frame is sequentially numbered from 0 to n - 1, where n is the
window size at the sender side.
• The sender sends as many frames as would fit in a window.
• After receiving the desired number of frames, the receiver sends an
acknowledgment.
• The acknowledgment (ACK) includes the number of the next expected
frame.
Compiled By Mrs. Soniya Khatu
Elementary Data Link protocols:
Working:

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols:
• Sliding window protocol has
two types:

1.Go-Back-N Automatic
Repeat Request

2.Selective Repeat Automatic

Repeat Request

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
• Go – Back – N ARQ provides for sending multiple frames before receiving the
acknowledgment 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 acknowledgment of a frame is not received within the time-period, all
frames starting from that frame are retransmitted.
• The Go-Back-N Automatic Repeat Request (ARQ) protocol is a type of error-
control protocol used in data communication to ensure reliable delivery of data
over a noisy channel.
• In a noisy channel, the probability of errors in the received packets is high, and
hence, there is a need for a mechanism to detect and correct these errors.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

The Go-Back-N ARQ protocol is a type of sliding window protocol where

the sender transmits a window of packets to the receiver, and the receiver
sends back an acknowledgment (ACK) to the sender indicating successful
receipt of the packets.

In case the sender does not receive an ACK within a specified timeout
period, it retransmits the entire window of packets.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N
ARQ
Protocol –

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols:
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 again.

The size of the sender window is N in this protocol

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols:
Go-Back-N ARQ
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.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols:
The example of Go-Back-N ARQ is shown below in the figure.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
• To improve the efficiency of transmission (filling the pipe), multiple
frames must be in transition while waiting for acknowledgment.

• In other words, we need to let more than one frame be outstanding to

keep the channel busy while the sender is waiting for acknowledgment.

• The first is called Go-Back-N Automatic Repeat. In this protocol several

frames can be send before receiving acknowledgments; we keep a copy of
these frames until the acknowledgments arrive.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
In the Go-Back-N Protocol, the sequence numbers are modulo 2 m , where
m is the size of the sequence number field in bits.

The sequence numbers range from 0 to 2 power m - 1.

For example, if m is 4, the only sequence numbers are 0 through 15

inclusive.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

• The sender window at any time divides the possible sequence numbers into
four regions.

• The first region, from the far left to the left wall of the window, defines the
sequence numbers belonging to frames that are already acknowledged.
•
• The sender does not worry about these frames and keeps no copies of them.

• The second region, coloured in Figure (a), defines the range of sequence
numbers belonging to the frames that are sent and have an unknown status.
Compiled By Mrs. Soniya Khatu
 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

• The sender needs to wait to find out if these frames have been received or
were lost. We call these outstanding frames.

• The third range, white in the figure, defines the range of sequence numbers
for frames that can be sent; however, the corresponding data packets have
not yet been received from the network layer.

• Finally, the fourth region defines sequence numbers that cannot be used until
the window slides.
Compiled By Mrs. Soniya Khatu
 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

• The send window is an abstract concept defining an imaginary

box of size 2 m − 1 with three variables: Sf, Sn, and Ssize.
• The variable Sf defines the sequence number of the first (oldest) outstanding frame.
• The variable Sn holds the sequence number that will be assigned to the next frame
to be sent.
• Finally, the variable Ssize defines the size of the window.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

• Figure (b) shows how a send window can slide one or more slots to the right when an
acknowledgment arrives from the other end.
• The acknowledgments in this protocol are cumulative, meaning that more than one frame
can be acknowledged by an ACK frame.
• In Figure, frames 0, I, and 2 are acknowledged, so the window has slide to the right three
slots.
• Note that the value of Sf is 3 because frame 3 is now the first outstanding frame.
• The send window can slide one or more slots when a valid acknowledgment arrives.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
Receiver window:
variable Rn (receive window, next frame expected).
The sequence numbers to the left of the window belong to the frames already received and
acknowledged; the sequence numbers to the right of this window define the frames that
cannot be received.

Any received frame with a sequence number in these two regions is discarded.

Only a frame with a sequence number matching the value of Rn is accepted and
acknowledged.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
Receiver window:
The receive window also slides, but only one slot at a time.

When a correct frame is received (and a frame is received only one at a time), the window
slides. (see below figure for receiving window).

The receive window is an abstract concept defining an imaginary box of size 1 with one
single variable Rn.

The window slides when a correct frame has arrived; sliding occurs one slot at a time.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

Fig: Receiver window (before sliding (a), AfterCompiled

slidingBy Mrs. Soniya Khatu
(b))
Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
Acknowledgment:
The receiver sends a positive acknowledgment if a frame has arrived safe and sound and
in order.
If a frame is damaged or is received out of order, the receiver is silent and will discard all
subsequent frames until it receives the one it is expecting.
The silence of the receiver causes the timer of the unacknowledged frame at the sender
side to expire.
This, in turn, causes the sender to go back and resend all frames, beginning with the one
with the expired timer.
The receiver does not have to acknowledge each frame received. It can send one
cumulative acknowledgment for several frames.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
• Resending a Frame:

• When the timer expires, the sender resends all outstanding frames.

• For example, suppose the sender has already sent frame 6, but the timer for frame 3
expires.

• This means that frame 3 has not been acknowledged; the sender goes back and sends
frames 3,4,5, and 6 again.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
• Resending a Frame:

• That is why the protocol is called Go-Back-N ARQ.

• Below figure is an example (if ack lost) of a case where the forward channel is reliable,
but the reverse is not. No data frames are lost, but some ACKs are delayed and one is
lost.

• The example also shows how cumulative acknowledgments can help if

acknowledgments are delayed or lost

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
Below figure is an example (if frame lost)

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
Sender Side:

• The sender transmits a window of packets to the receiver, starting with

sequence number i and ending with sequence number i + N - 1, where N is
the window size.

• The sender sets a timer for each packet in the window.

• The sender waits for an acknowledgment (ACK) from the receiver.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
Receiver Side:
• The receiver receives the packets and checks for errors.

• If a packet is received correctly, the receiver sends an ACK back to the

sender with the sequence number of the next expected packet.

• If a packet is received with errors, the receiver discards the packet and
sends a negative acknowledgment (NAK) to the sender with the sequence
number of the next expected packet.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
Sender Side (in case of no ACK received):

• If the sender does not receive an ACK before the timer for a packet expires,
the sender retransmits the entire window of packets starting with the packet
whose timer expired.

• The sender resets the timer for each packet in the window.

• The sender waits for an ACK from the receiver.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –
Sender Side (in case of NAK received):

• If the sender receives a NAK from the receiver, the sender retransmits only
the packets that were not correctly received by the receiver.

• The sender resets the timer for each packet that was retransmitted.

• The sender waits for an ACK from the receiver.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
GO-BACK-N ARQ Protocol –

The above steps are repeated until all packets have been successfully
received by the receiver.

The Go-Back-N ARQ protocol provides a reliable mechanism for

transmitting data over a noisy channel while minimizing the number of
retransmissions required.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

• In Go-Back-N ARQ, the receiver keeps track of only one variable, and
there is no need to buffer out-of- order frames; they are simply discarded.
• However, this protocol is very inefficient for a noisy link.
• For noisy links, there is a mechanism that does not resend N frames when
just one frame is damaged; only the damaged frame is resent.
• This mechanism is called Selective Repeat ARQ.
• It is more efficient for noisy links, but the processing at the receiver is more
complex.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

• The Selective Repeat ARQ protocol is a type of error-control protocol used

in data communication to ensure reliable delivery of data over a noisy
channel.

• Unlike the Go-Back-N ARQ protocol which retransmits the entire window
of packets, the Selective Repeat ARQ protocol retransmits only the packets
that were not correctly received.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

• In the Selective Repeat ARQ protocol, the sender transmits a window of

packets to the receiver, and the receiver sends back an acknowledgment
(ACK) to the sender indicating successful receipt of the packets.

• If the receiver detects an error in a packet, it sends a negative

acknowledgment (NAK) to the sender requesting retransmission of that
packet.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

• In the Selective Repeat ARQ protocol, the sender maintains a timer for each
packet in the window.

• If the sender does not receive an ACK for a packet before its timer expires,
the sender retransmits only that packet.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

• At the receiver side, if a packet is received correctly, the receiver sends

back an ACK with the sequence number of the next expected packet.

• However, if a packet is received with errors, the receiver discards the

packet and sends back a NAK with the sequence number of the packet that
needs to be retransmitted.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

• Unlike Go-Back-N ARQ, in Selective Repeat ARQ, the receiver buffer is

maintained for all packets that are not in sequence.

• When a packet with a sequence number different from the expected

sequence number arrives at the receiver, it is buffered, and the receiver
sends an ACK for the last in-order packet it has received.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

• If a packet with a sequence number that the receiver has already buffered
arrives, it is discarded, and the receiver sends an ACK for the last in-order
packet it has received.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT
ARQ Protocol -

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols:
• 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.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols:
• Selective Repeat ARQ

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

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol -
Sender Side:

• The sender transmits a window of packets to the receiver, starting with

sequence number i and ending with sequence number i + N - 1, where N is
the window size.
• The sender sets a timer for each packet in the window.
• The sender waits for an acknowledgment (ACK) from the receiver.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –
Sender Window:
• In the selective repeat, the sender sends several frames specified by a
window size even without the need to wait for individual acknowledgement
from the receiver as in Go-Back-N ARQ.

• In selective repeat protocol, the retransmitted frame is received out of

sequence.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –
Sender Side (in case of no ACK received):

• If the sender does not receive an ACK before the timer for a packet expires,
the sender retransmits only that packet.

• The sender resets the timer for the retransmitted packet.

• The sender waits for an ACK from the receiver.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –
Sender Side (in case of NAK received):

• If the sender receives a NAK from the receiver, the sender retransmits only
the packets that were not correctly received.

• The sender resets the timer for each packet that was retransmitted.

• The sender waits for an ACK from the receiver.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –
Receiver Side:
• The receiver receives the packets and checks for errors.

• If a packet is received correctly and is in order, the receiver sends an ACK

back to the sender with the sequence number of the next expected packet.

• If a packet is received with errors or is out of order, the receiver discards

the packet and sends a negative acknowledgment (NAK) to the sender with
the sequence number of the packet that needs to be retransmitted.

• The receiver buffers out-of-order packets and sends an ACK for the last in-
order packet it has received.
Compiled By Mrs. Soniya Khatu
Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –
• Receiver window:
• The receiver window in Selective Repeat is totally different from the one in Go Back-N.
First, the size of the receive window is the same as the size of the send window (2m-1).

• The Selective Repeat Protocol allows as many frames as the size of the receiver window
to arrive out of order and be kept until there is a set of in order frames to be delivered to
the network layer.

• Because the sizes of the send window and receive window are the same, all the frames
in the send frame can arrive out of order and be stored until they can be delivered.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –
• Receiver window:

• However the receiver never delivers packets out of order to the network layer. Above
Figure shows the receive window.

• Those slots inside the window that are coloured define frames that have arrived out of
order and are waiting for their neighbours to arrive before delivery to the network layer.

• In Selective Repeat ARQ, the size of the sender and receiver window must be at most
one-half of 2m.

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

Compiled By Mrs. Soniya Khatu

Elementary Data Link protocols
SELECTIVE REPEAT ARQ Protocol –

Piggybacking:
A technique called piggybacking is used to improve the efficiency of the
bidirectional protocols.
When a frame is carrying data from A to B, it can also carry control
information about arrived (or lost) frames from B; when a frame is carrying
data from B to A, it can also carry control information about the arrived (or
lost) frames from A.

Compiled By Mrs. Soniya Khatu

 Elementary Data Link protocols:
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 In this, only the frame is sent again, which is
subsequent frames have to be sent again. corrupted or lost.
If it has a high error rate,it wastes a lot of There is a loss of low bandwidth.
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.
Compiled By Mrs. Soniya Khatu
Medium Access Control sublayer

➢ Channel Allocation problem

➢ Multiple access Protocol

➢Aloha
➢ Carrier Sense Multiple Access (CSMA/CD)

Compiled By Mrs. Soniya Khatu

THE CHANNEL ALLOCATION PROBLEM
In broadcast networks, a single channel is shared by several stations.
This channel can be allocated to only one transmitting user at a time.
There are two different methods of channel allocations:
1. Static Channel Allocation- a single channel is divided among various
users either on the basis of frequency (FDM) or on the basis of time
(TDM). In FDM, fixed frequency is assigned to each user, whereas, in
TDM, fixed time slot is assigned to each user.
2. Dynamic Channel Allocation- no user is assigned a fixed frequency or
fixed time slot. All users are dynamically assigned frequency or time slot,
depending upon the requirements of the user.

Compiled By Mrs. Soniya Khatu

Medium Access Control Sublayer:
To coordinate the access to the channel, multiple access protocols are
required.
All these protocols belong to the MAC sub layer.
Data Link layer is divided into two sub layers:

1. Logical Link Control (LLC)- is responsible for error control & flow
control.
2. Medium Access Control (MAC)- MAC is responsible for multiple
access resolutions.

Compiled By Mrs. Soniya Khatu

MULTIPLE ACCESS PROTOCOLS:

• Many protocols have been defined to handle the access to shared links.
• These protocols are organized in three different groups:
● Random Access Protocols
● Controlled Access Protocols
● Channelization Protocols

Compiled By Mrs. Soniya Khatu

Random Access Protocols:
• There is no rule that decides which station should send next.

• If two stations transmit at the same time, there is collision and the frames are lost.

• The various random access methods are:

1. ALOHA
2. CSMA (Carrier Sense Multiple Access)
3. CSMA/CD (Carrier Sense Multiple Access with Collision Detection)
4. CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)

Compiled By Mrs. Soniya Khatu

ALOHA
• ALOHA was developed at University of Hawaii in early 1970s by Norman
Abramson.
• It was used for ground based radio broadcasting.
• In this method, stations share a common channel.
• When two stations transmit simultaneously, collision occurs and frames are
lost.
• There are two different versions of ALOHA:
1. Pure ALOHA
2. Slotted ALOHA

Compiled By Mrs. Soniya Khatu

Compiled By Mrs. Soniya Khatu
Pure ALOHA
• In pure ALOHA, stations transmit frames whenever they have data to
send. When two stations transmit simultaneously, there is collision and
frames are lost.

• In pure ALOHA, whenever any station transmits a frame, it expects

an acknowledgement from the receiver.

• If acknowledgement is not received within specified time, the station

assumes that the frame has been lost.
•

Compiled By Mrs. Soniya Khatu

Pure ALOHA
• If the frame is lost, station waits for a random amount of time and sends
it again.

• This waiting time must be random; otherwise, same frames will collide
again and again.

• Whenever two frames try to occupy the channel at the same time, there
will be collision, and both the frames will be lost.

• If the first bit of a new frame overlaps with the last bit of a frame almost
finished, both frames will be lost, and both will have to be retransmitted.
Compiled By Mrs. Soniya Khatu
Pure ALOHA

Compiled By Mrs. Soniya Khatu

 Pure ALOHA
● In pure ALOHA, the stations transmit frames whenever they have data to send. When
two or more stations transmit simultaneously, there is collision and the frames are
destroyed.

● In pure ALOHA, whenever any station transmits a frame, it expects

acknowledgement from the receiver.

● If acknowledgement is not received within specified time, the station assumes that the
frame (or acknowledgement) has been destroyed.

Compiled By Mrs. Soniya Khatu

 Pure ALOHA

● If the frame is destroyed because of collision the station waits for a random amount of
time and sends it again.

● This waiting time must be random otherwise the same frames will collide again and
again.

● Therefore pure ALOHA dictates that when the time-out period passes, each station
must wait for a random amount of time before resending its frame. This randomness
will help avoid more collisions.

Compiled By Mrs. Soniya Khatu

 Pure ALOHA
• Vulnerable time:
• Let us find the length of time, the vulnerable time, in which there is a possibility of
collision.
• We assume that the stations send fixed length frames with each frame taking Tfr S to
send. Below
• Figure shows the vulnerable time for station A

Compiled By Mrs. Soniya Khatu

 Pure ALOHA
➢Station A sends a frame at time t.
➢Now imagine station B has already sent a frame between t - Tfr and t.
➢This leads to a collision between the frames from station A and station B.
➢The end of B's frame collides with the beginning of A's frame.
➢On the other hand, suppose that station C sends a frame between t and t + Tfr .
➢Here, there is a collision between frames from station A and station C.
➢The beginning of C's frame collides with the end of A's frame Looking at Figure, we
see that the vulnerable time, during which a collision may occur in pure ALOHA, is 2
times the frame transmission time.

➢Pure ALOHA vulnerable time = 2 x Tfr.

Compiled By Mrs. Soniya Khatu

Fig: FlowCompiled
chart of pure
By Mrs. ALOHA
Soniya Khatu
Pure ALOHA
Problem:
A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps.
What is the requirement to make this frame collision-free?
Solution:
Average frame transmission time Tfr is 200 bits/200 kbps or 1 ms. The vulnerable
time is 2 x 1 ms =2 ms. This means no station should send later than 1 ms before
this station starts transmission and no station should start sending during the one I-
ms period that this station is sending.
The throughput for pure ALOHA is S = G × e −2G . The maximum throughput
Smax = 0.184 when G= (1/2).

Compiled By Mrs. Soniya Khatu

Slotted ALOHA
• Slotted ALOHA was invented to improve the efficiency of pure ALOHA.

• In slotted ALOHA, time of the channel is divided into intervals called slots.

• The station can send a frame only at the beginning of the slot and only one frame
is sent in each slot.

• If any station is not able to place the frame onto the channel at the beginning of the
slot, it has to wait until the next time slot.

• There is still a possibility of collision if two stations try to send at the beginning of
the same time slot.

Compiled By Mrs. Soniya Khatu

Slotted ALOHA
• Pure ALOHA has a vulnerable time of 2 x Tfr .
• This is so because there is no rule that defines when the station can send.
• A station may send soon after another station has started or soon before another
station has finished.
• Slotted ALOHA was invented to improve the efficiency of pure ALOHA.
• In slotted ALOHA we divide the time into slots of Tfr s and force the station to
send only at the beginning of the time slot.
• Figure below shows an example of frame collisions in slotted ALOHA.

Compiled By Mrs. Soniya Khatu

Slotted ALOHA

Compiled By Mrs. Soniya Khatu

Slotted ALOHA
• Because a station is allowed to send only at the beginning of the synchronized
time slot, if a station misses this moment, it must wait until the beginning of the
next time slot.

• This means that the station which started at the beginning of this slot has already
finished sending its frame.

• Of course, there is still the possibility of collision if two stations try to send at the
beginning of the same time slot.

• However, the vulnerable time is now reduced to one-half, equal to Tfr.

Compiled By Mrs. Soniya Khatu

Carrier Sense Multiple Access (CSMA)
• CSMA stands for Carrier Sense Multiple Access. Carrier Sense means, stations
has an additional property with them, that they can sense the channel (carrier) and
tell if the channel is in use or not.

• What we want, that at the start of the slot, stations should sense the channel first,
and then act accordingly.

• CSMA was developed to overcome the problems of ALOHA i.e. to minimize the
chances of collision.

• The chances of collision reduces to a great extent if a station checks the channel
before trying to use it.

Compiled By Mrs. Soniya Khatu

Carrier Sense Multiple Access (CSMA)
There are three different types of CSMA protocols:

1. 1-Persistent CSMA
2. Non-Persistent CSMA
3. P-Persistent CSMA

Compiled By Mrs. Soniya Khatu

Carrier Sense Multiple Access (CSMA)
• 1-Persistent CSMA:
• In this method, station that wants to transmit data, continuously
senses the channel to check whether the channel is idle or busy.

• If the channel is busy, station waits until it becomes idle.

• When the station detects an idle channel, it immediately transmits the

frame.

• This method has the highest chance of collision because two or more
stations may find channel to be idle at the same time and transmit their
frames.

Compiled By Mrs. Soniya Khatu

Carrier Sense Multiple Access (CSMA)
• Non-Persistent CSMA:

• A station that has a frame to send senses the channel.

• If the channel is idle, it sends immediately.
• If the channel is busy, it waits a random amount of time and then
senses the channel again.
• It reduces the chance of collision because the stations wait for a
random amount of time.
• It is unlikely that two or more stations will wait for the same amount
of time and will retransmit at the same time.

Compiled By Mrs. Soniya Khatu

Carrier Sense Multiple Access (CSMA)
• P-Persistent CSMA:
• In this method, the channel has time slots such that the time slot
duration is equal to or greater than the maximum propagation delay
time.
• When a station is ready to send, it senses the channel.

• If the channel is busy, the station waits until the next slot.

• If the channel is idle, it transmits the frame. It reduces the chance of

collision and improves the efficiency of the network.

Compiled By Mrs. Soniya Khatu

Carrier Sense Multiple Access (CSMA)

Compiled By Mrs. Soniya Khatu

CSMA with Collision Detection (CSMA/CD):
• In this protocol, the station senses the channel before transmitting the
frame.
• If the channel is busy, the station waits.
• Additional feature in CSMA/CD is that the stations can detect
collisions.
• The stations abort their transmission as soon as they detect a collision.
• This feature is not present in CSMA. The stations continue to transmit
even though they find that a collision has occurred.
• .

Compiled By Mrs. Soniya Khatu

CSMA with Collision Detection (CSMA/CD)
• In CSMA/CD, the station that sends its data on the channel, continues to
sense the channel even after data transmission.
• If collision is detected, the station aborts its transmission and waits for a
random amount of time & sends its data again.
• As soon as a collision is detected, the transmitting stations release a jam
signal.
• Jam signal alerts other stations.
• Stations are not supposed to transmit immediately after the collision has
occurred.

Compiled By Mrs. Soniya Khatu

 CSMA with Collision Detection (CSMA/CD)

Compiled By Mrs. Soniya Khatu

CSMA with Collision Detection (CSMA/CD)
• CSMA/CD can be in one of three states: contention, transmission, or
idle.

Compiled By Mrs. Soniya Khatu

Compiled By Mrs. Soniya Khatu