DATA LINK LAYER

OVERVIEW OF DLL

The data link layer transforms the physical layer, a raw transmission facility, to
a link responsible for node-to-node (hop-to-hop) communication. Specific
responsibilities of the data link layer include framing, addressing, flow control,
error control, and media access control.

2
DLL design issues
❶ Services Provided to the Network
Layer
⚫ The network layerwants to be able to send packets
to its neighbors without worrying about the details
of getting it there in one piece.
❷ Framing
⚫ Group the physical layer bit stream into units called frames.
Frames are nothing more than "packets" or "messages". By
convention, we use the term "frames" when discussing DLL.
❸ Error Control
⚫ Sender checksums the frame and transmits checksum
together with data. Receiver re-computes the checksum and
compares it with the received value.

❹ Flow Control
⚫ Prevent a fast sender from overwhelming a slower receiver.
 DATA LINK LAYER DESIGN ISSUES

□ Providing a well-defined service interface to the

network layer.
□ Dealing with transmission errors.
□ Regulating the flow of data so that slow receivers
are not swamped by fast senders
For this, the data link layer takes the packets it gets from the network layer and
encapsulates them into frames for transmission. Each frame contains a frame header, a
payload field for holding the packet, and a frame trailer

4
SERVICES PROVIDED TO
NETWORK LAYER
□ The function of the data link layer is to provide services to the
network layer. The principal service is transferring data from
the network layer on the source machine to the network
layer on the destination machine.

□ The data link layer can be designed to offer various services.

The actual services offered can vary from system to system.
Three reasonable possibilities that are commonly provided
are

1) Unacknowledged Connectionless service

2) Acknowledged Connectionless service 5

UNACKNOWLEDGED CONNECTIONLESS SERVICE

□ Unacknowledged connectionless service consists of having the

source machine send independent frames to the destination
machine without having the destination machine acknowledge
them
□ No logical connection is established beforehand or released
afterward. If a frame is lost due to noise on the line, no attempt is
made to detect the loss or recover from it in the data link layer
□ This class of service is appropriate when the error rate is very
low so that recovery is left to higher layers. It is also appropriate
6
for real- time traffic, such as voice, in which late data are
worse than bad data. Most LANs use unacknowledged
ACKNOWLEDGED CONNECTIONLESS SERVICE

□ When this service is offered, there are still no logical

connections used, but each frame sent is individually
acknowledged.

□ In this way, the sender knows whether a frame has arrived

correctly. If it has not arrived within a specified time
interval, it can be sent again. This service is useful over
unreliable channels, such as wireless systems.

□ Adding Ack in the DLL rather than in the Network Layer is

just an optimization and not a requirement. If individual
frames are acknowledged and retransmitted, entire packets
get through much faster. On reliable channels, such as fiber,
7
the overhead of a heavyweight data link protocol may be
unnecessary, but on wireless channels, with their inherent
FRAMING – CHARACTER
COUNT
 The first framing 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.

The trouble with this algorithm is that the count can

be garbled by a transmission error
Redundancy
 The central concept in detecting or
correcting errors is redundancy. To be
able to detect or correct errors, we need
to send some extra bits with our data.
These redundant bits are added by the
sender and removed by the receiver.
Their presence allows the receiver to
detect or correct corrupted bits.
Error Detection in Computer
Networks

 Error is a condition when the receiver’s information

does not match the sender’s. Digital signals suffer
from noise during transmission 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.
 Data (Implemented either at the Data link layer or
Transport Layer of the OSI Model) may get scrambled
by noise or get corrupted whenever a message is
transmitted. To prevent such errors, error-detection
codes are added as extra data to digital messages.
This helps in detecting any errors that may have
occurred during message transmission.
Types of Errors
 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.
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.
ERROR DETECTION VS ERROR
CORRECTION
 There are two types of attacks against errors:
 Error Detecting Codes: Include enough
redundancy bits to detect errors and use ACKs
and retransmissions to recover from the errors.
 Error Correcting Codes: Include enough
redundancy to detect and correct errors. The
use of error-correcting codes is often referred to
as forward error correction.
Error Detection Methods
 Simple Parity Check
 Two-Dimensional Parity Check
 Checksum
 Cyclic Redundancy Check (CRC)
Single Parity Check
 Single Parity checking is the simple mechanism and
inexpensive to detect the errors.
 In this technique, a redundant bit is also known as a
parity bit which is appended at the end of the data unit
so that the number of 1s becomes even. Therefore, the
total number of transmitted bits would be 9 bits.
 If the number of 1s bits is odd, then parity bit 1 is
appended and if the number of 1s bits is even, then
parity bit 0 is appended at the end of the data unit.
 At the receiving end, the parity bit is calculated from
the received data bits and compared with the received
parity bit.
 This technique generates the total number of 1s even,
so it is known as even-parity checking.
Single Parity Check
Drawbacks Of Single Parity
Checking

 It can only detect single-bit errors which

are very rare.
 If two bits are interchanged, then it
cannot detect the errors.
LONGITUDINAL REDUNDANCY CHECK
(LRC)
 Longitudinal Redundancy Checks (LRC) seek to
overcome the weakness of simple, bit-oriented, one-
directional parity checking.
 LRC adds a new character (instead of a bit) called the
Block Check Character (BCC) to each block of data. Its
determined like parity, but counted longitudinally
through the message (also vertically)
 Its has better performance over VRC as it detects 98%
of the burst errors (>10errors) but less capable of
detecting single errors
 If two bits in one data units are damaged and two bits in
exactly the same positions in another data unit are also
damaged, the LRC checker will not detect an error.
TWO DIMENSIONAL PARITY
CHECK
 Upon receipt, each character is checked
according to its VRC parity value and then
the entire block of characters is verified
using the LRC block check character.
 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.
 The checksum detects all errors involving an odd
number of bits. It also detects most errors
involving even number of bits.
 Checksum – Operation at Sender’s Side
 Firstly, the data is divided into k segments each of m bits.
 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.
 The checksum segment is sent along with the data
segments.
 Checksum – Operation at Receiver’s Side
 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.
CHECKSUM EXAMPLE
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.
CRC Working
 We have given dataword of length n and divisor
of length k.
 Step 1: Append (k-1) zero’s to the original
message
 Step 2: Perform modulo 2 division
 Step 3: Remainder of division = CRC
 Step 4: Code word = Data with append k-1
zero’s + CRC
 Note:
 CRC must be k-1 bits
 Length of Code word = n+k-1 bits
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.
Advantages of Error Detection
 Increased Data Reliability: Error detection
ensures that the data transmitted over the network
is reliable, accurate, and free from errors. This
ensures that the recipient receives the same data
that was transmitted by the sender.
 Improved Network Performance: Error
detection mechanisms can help to identify and
isolate network issues that are causing errors. This
can help to improve the overall performance of the
network and reduce downtime.
 Enhanced Data Security: Error detection can also
help to ensure that the data transmitted over the
network is secure and has not been tampered with.
Disadvantages of Error
Detection

 Overhead: Error detection requires additional

resources and processing power, which can lead to
increased overhead on the network. This can result
in slower network performance and increased
latency.
 False Positives: Error detection mechanisms can
sometimes generate false positives, which can
result in unnecessary retransmission of data. This
can further increase the overhead on the network.
 Limited Error Correction: Error detection can
only identify errors but cannot correct them. This
means that the recipient must rely on the sender to
retransmit the data, which can lead to further
delays and increased network overhead.
 Block Coding
 Block coding is a technique used in computer networks to improve the
reliability and efficiency of data transmission. It involves dividing the data into
blocks or packets and adding extra bits, known as error-correction codes, to
each block. These codes can be used to detect and correct errors that may
occur during transmission.
 There are several different types of block codes, including linear block codes,
cyclic codes, and convolutional codes. Linear block codes are the most
commonly used, and they work by adding parity bits to the data blocks. Cyclic
codes are similar to linear block codes, but they use a different algorithm to
generate the error-correction codes. Convolutional codes are a type of error-
correcting code that uses a sliding window to encode the data.
Advantages of Block Coding
 Improved Reliability: Block coding can improve the reliability of digital

systems by adding redundant information to the data, which can be

used to detect and correct errors that may occur during transmission or

storage.

 Increased Data Accuracy: Block coding can help ensure the accuracy of

transmitted or stored data by detecting and correcting errors that may

occur.

 Greater Efficiency: Block coding can increase the efficiency of digital

systems by reducing the number of errors that occur during

transmission or storage, reducing the need for retransmission or

storage.
Disadvantages of Block Coding

 Increased Complexity: Block coding can increase

the complexity of digital systems, making them
more difficult to design, implement, and
maintain.
 Increased Overhead: Block coding can increase
the overhead of digital systems in terms of
processing time and memory usage, reducing
overall system performance.
 Increased Cost: Block coding can increase the
cost of digital systems, as it requires additional
hardware or software to implement the error
correction and detection mechanisms.
 ERROR CORRECTION
 Once detected, the errors must be corrected
 Two Techniques for error correction
Retransmission (aka Backward error
correction)
 Simplest, effective and most commonly used
technique – involves correction by
retransmission of data by the sender
 Popularly called Automatic Repeat Request
(ARQ)
Forward Error Correction (FEC)
Receiving device can correct the errors itself
 ERROR CORRECTION
 Messages (frames) consist of m data (message) bits and r
redundancy bits, yielding an n = (m+r)-bit codeword.
 Hamming Distance. Given any two codewords, we can
determine how many of the bits differ. Simply exclusive or
(XOR) the two words, and count the number of 1 bits in the
result.
 Significance? If two codewords are d bits apart, d errors are
required to convert one to the other.
 A code's Hamming Distance is defined as the minimum
Hamming Distance between any two of its legal
codewords (from all possible codewords).
 To detect d 1-bit errors requires having a Hamming
Distance of atleast d+1 bits.
 To correct d errors requires 2d+1 bits. Intuitively, after d
errors, the garbled messages is still closer to the original
message than any other legal codeword.
HAMMING DISTANCE
 In this method, extra parity bits are appended to the
message which are used by the receiver to correct the
single bit error and multiple bit error. Consider the
below example to understand this method in a better
way.
 Suppose the sender wants to transmit the message
whose bit representation is ‘1011001.’ In this message:
 Total number of bits(d) = 7
 Total of redundant bits(r) = 4 (This is because the
message has four 1’s in it)
 Thus, total bits(d+r) = 7 + 4 = 11
 Also, by convention, the redundant bits are always
placed in the places which are powers of 2.
 Therefore, we have R1, R2, R3, and R4 as redundant bits which will
be calculated according to the following rules:
 R1 includes all the positions whose binary representation has 1 in
their least significant bit. Thus, R1 covers positions 1, 3, 5, 7, 9, 11.
 R2 includes all the positions whose binary representation has 1 in
the second position from the least significant bit. Thus, R2 covers
positions 2,3,6,7,10,11.
 R3 includes all the positions whose binary representation has 1 in
the third position from the least significant bit. Hence, R3 covers
positions 4, 5, 6, 7.
 R4 includes all the positions whose binary representation has 1 in
the fourth position from the least significant bit due to which R4
covers positions 8,9,10,11.
 Now, we calculate the value of
R1, R2, R3 and R4 as follows:
 Since the total number of 1s in
all the bit positions
corresponding to R1 is an even
number. R1 = 0.
 Since the total number of 1s in
all the bit positions
corresponding to R2 is an odd
number, R2= 1.
 Since the total number of 1s in
all the bit positions
corresponding to R3 is an odd
number, R3= 1.
 Since the total number of 1s in
all the bit positions
corresponding to R4 is even, R4
= 0.
 Therefore, the message to be
transmitted becomes:
 This message is transmitted at the receiver’s end. Suppose, bit 6
becomes corrupted and changes to 0. Then, the message becomes
‘10101101110.’ So, at the receiver’s end, the number of 1’s in the
respective bit positions of R1, R2, R3, and R4 is rechecked to correct
the corrupted bit. This is done in the following steps: For all the parity
bits we will check the
 For R1: bits 1, 3, 5, 7, 9, and 11 are checked. We can see that the
number of 1’s in these bit positions is 4(even) so R1 = 0.
 For R2: bits 2,3,6,7,10,11 are checked. You can observe that the
number of 1’s in these bit positions is 5(odd) so we get a R2 = 1.
 For R3: bits 4, 5, 6, and 7 are checked. We see that the number of 1’s
in these bit positions is 3(odd). Hence, R3 = 1.
 For R8: bits 8,9,10,11 are observed. Here, the number of 1’s in these
bit positions is 2 and that’s even so we get R4 = 0.
 If we observe the Redundant bits, they give the binary number 0110
whose decimal representation is 6. Thus, bit 6 contains an error. To
correct the error the 6th bit is changed from 1 to 0 to correct the error.
FUNCTIONS AND REQUIREMENTS OF
THE DATA LINK PROTOCOLS
 The basic function of the layer is to transmit frames over a physical
communication link. Transmission may be half duplex or full duplex.
To ensure that frames are delivered free of errors to the destination
station (IMP) a number of requirements are placed on a data link
protocol. The protocol (control mechanism) should be capable of
performing:
 The identification of a frame (i.e. recognize the first and last bits of a
frame).
 The transmission of frames of any length up to a given maximum.
Any bit pattern is permitted in a frame.
 The detection of transmission errors.
 The retransmission of frames which were damaged by errors.
 The assurance that no frames were lost.
 In a multi drop configuration -> Some mechanism must be used for
preventing conflicts caused by simultaneous transmission by many
stations.
 The detection of failure or abnormal situations for control and
ELEMENTARY DATA LINK
PROTOCOLS

 The protocols are normally

implemented in software by using
one of the common programming
languages.
 • An Unrestricted Simplex Protocol
 • A Simplex Stop-and-Wait Protocol
 • A Simplex Protocol for a Noisy Channel
 AN UNRESTRICTED SIMPLEX
PROTOCOL

 In order to appreciate the step by step

development of efficient and complex
protocols we will begin with a simple but
unrealistic protocol. In this protocol: Data are
transmitted in one direction only
 The transmitting (Tx) and receiving (Rx) hosts
are always ready
 Processing time can be ignored
 Infinite buffer space is available
 No errors occur; i.e. no damaged frames and
no lost frames (perfect channel)
 A SIMPLEX STOP-AND-WAIT
PROTOCOL
 In this protocol we assume that Data are
transmitted in one direction only. No errors occur
(perfect channel)
 The receiver can only process the received
information at a finite rate. These assumptions
imply that the transmitter cannot send frames at a
rate faster than the receiver can process them.
 The problem here is how to prevent the sender from
flooding the receiver.
 A general solution to this problem is to have the
receiver provide some sort of feedback to the
sender. The process could be as follows: The
receiver send an acknowledge frame back to the
sender telling the sender that the last received
STOP & WAIT PROTOCOL
 The sender sends one frame and
waits for feedback from the
receiver. When the ACK arrives, the
sender sends the next frame.
A SIMPLEX PROTOCOL FOR A
NOISY CHANNEL
 In this protocol the unreal "error free" assumption in protocol 2 is
dropped. Frames may be either damaged or lost completely. We
assume that transmission errors in the frame are detected by the
hardware checksum. One suggestion is that the sender would
send a frame, the receiver would send an ACK frame only if the
frame is received correctly. If the frame is in error the receiver
simply ignores it; the transmitter would time out and would
retransmit it.
 One fatal flaw with the above scheme is that if the ACK frame is
lost or damaged, duplicate frames are accepted at the receiver
without the receiver knowing it.
 Imagine a situation where the receiver has just sent an ACK
frame back to the sender saying that it correctly received
and already passed a frame to its host. However, the ACK
frame gets lost completely, the sender times out and
retransmits the frame. There is no way for the receiver to
tell whether this frame is a retransmitted frame or a new
frame, so the receiver accepts this duplicate happily and
transfers it to the host. The protocol thus fails in this
aspect.
 To overcome this problem it is required that the receiver be
able to distinguish a frame that it is seeing for the first time
from a retransmission. One way to achieve this is to have the
sender put a sequence number in the header of each frame it
sends. The receiver then can check the sequence number of
each arriving frame to see if it is a new frame or a duplicate
to be discarded.
 The receiver needs to distinguish only 2 possibilities: a new
frame or a duplicate; a 1-bit sequence number is
sufficient. At any instant the receiver expects a particular
sequence number. Any wrong sequence numbered frame
arriving at the receiver is rejected as a duplicate. A correctly
numbered frame arriving at the receiver is accepted, passed
to the host, and the expected sequence number is
incremented by 1.
SLIDING WINDOW
PROTOCOLS
DATA FRAME
TRANSMISSION
 Unidirectional assumption protocols
 Not general in previous elementary

 Full-duplex - approach 1

 Two separate communication channels(physical

 circuits)

 Forward channel for data

 Reverse channel for acknowledgement

 Problems: 1. reverse channel bandwidth

wasted
2. cost
 DATA FRAME
TRANSMISSION
 Full-duplex - approach 2
 Same circuit for both
directions
 Data and acknowledgement
are intermixed
 How do we tell
acknowledgement from
data? "kind" field telling
data or acknowledgement
 Can it be improved?
 Approach 3
 Attaching
acknowledgement to
outgoing data frames
PIGGYBACKING
 Temporarily delaying transmission of outgoing
acknowledgement so that they can be hooked onto the next
outgoing data frame
 Advantage: higher channel bandwidth utilization
 Complication:
 How long to wait for a packet to piggyback?
 If longer than sender timeout period then sender retransmits
 ⇒ Purpose of acknowledgement is lost
 Solution for timing complexion
 If a new packet arrives quickly
 ⇒ Piggybacking
 If no new packet arrives after a receiver ack timeout
 ⇒ Sending a separate acknowledgement frame