Week - 3

Data Link Layer (DLL)

o The DLL is responsible for the node to node delivery of the message.
o The main function of this layer is to make sure data transfer is error-free from one node to
another, over the physical layer.
o When a packet arrives in a network, it is the responsibility of DLL to transmit it to the Host
using its MAC address.
o Data Link Layer is divided into two sub layers : LLC and MAC
Logical Link Control (LLC)
o Logical Link Control (LLC) is a sub-layer that generally provides the logic for the data link as
it controls the synchronization, multiplexing, flow control, and even error-checking functions
of DLL
Media Access Control (MAC)
o The packet received from Network layer is further divided into frames depending on the
frame size of NIC(Network Interface Card). DLL also encapsulates Sender and Receiver’s
MAC address in the header.
o The Receiver’s MAC address is obtained by placing an ARP(Address Resolution Protocol)
request onto the wire asking “Who has that IP address?” and the destination host will reply
with its MAC address.
DLL Purpose:
o Group the physical layer bit stream into units called frames.
o Sender checksums the frame and sends checksum together with data. The checksum allows
the receiver to determine when a frame has been damaged in transit.
o Receiver re-computes the checksum and compares it with the received value.
o If they differ, an error has occurred and the frame is discarded.
o Perhaps return a positive or negative acknowledgment to the sender.
o A positive acknowledgment indicate the frame was received without errors, while a negative
acknowledgment indicates the opposite.
DLL Functions:
The functions of the data Link layer are :
o Framing: Framing is a function of the data link layer. It provides a way for a sender to
transmit a set of bits that are meaningful to the receiver. This can be accomplished by
attaching special bit patterns to the beginning and end of the frame.

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

o Physical addressing: After creating frames, Data link layer adds physical addresses (MAC
address) of sender and/or receiver in the header of each frame.
o Error control: Data link layer provides the mechanism of error control in which it detects
and retransmits damaged or lost frames.
o Flow Control: The data rate must be constant on both sides else the data may get corrupted
thus , flow control coordinates that amount of data that can be sent before receiving
acknowledgement.
o Access control: When a single communication channel is shared by multiple devices, MAC
sub-layer of data link layer helps to determine which device has control over the channel at a
given time.
Framing Construction:
o Process of wrapping data with certain info before sending it.
o The DLL needs to pack bits into frames, so that each frame is distinguishable from another.
o Framing is a point-to-point connection between two computers or devices consists of a wire
in which data is transmitted as a stream of bits.
o Framing is a function of the data link layer. It provides a way for a sender to transmit a set of
bits that are meaningful to the receiver.
o Flag: indication for start and end of the frame
o Header: source / destination address, and other control information
o Data from upper layer
o Trailer: Error detection / correction code

Framing Methods:
o The four framing methods that are widely used are:
o Character count
o Starting and ending characters, with character stuffing
o Starting and ending flags, with bit stuffing
Character count:
o This method uses a field in the header to specify the number of characters in the frame.

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

 o 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.
o Disadvantage: If the count is garbled by a transmission error, the destination will lose
synchronization and will be unable to locate the start of the next frame.
o So, this method is rarely used.

(A) Without errors (B) with error

Byte or Character Stuffing:
o In this method, each frame starts with and ends with the sequence bytes – flag byte.
o If the flag byte occurs in the frame, stuff an extra escape byte (ESC)
o This method overcomes the drawbacks of the character count method.
o If the destination ever loses synchronization, it only has to look for Flag characters.
o If however, binary data is being transmitted then there exists a possibility of the
characters Flag occurring in the data.
o Since this can interfere with the framing, a technique called character stuffing is used.
o The sender's data link layer inserts an ASCII ESC character just before the ESC character
in the data. The receiver's data link layer removes this ESC before this data is given to the
network layer.
Original Data After Stuffing
A – Flag – B A-ESC-Flag - B
A – ESC – B A- ESC-ESC-B
A – ESC – Flag – B A- ESC – ESC – ESC – Flag - B
A – ESC – ESC – B A – ESC-ESC-ESC-ESC-B

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

Process of adding extra byte whenever there is an flag or escape character in the data

Bit Stuffing:
o The third method allows data frames to contain an arbitrary number of bits and allows
character codes with an arbitrary number of bits per character.
o At the start and end of each frame is a flag byte consisting of the special bit pattern
01111110
o Whenever the sender's data link layer encounters five consecutive 1s in the data, it
automatically stuffs a zero bit into the outgoing bit stream.
o This technique is called bit stuffing.
o When the receiver sees five consecutive 1s in the incoming data stream, followed by a zero
bit, it automatically de-stuffs the 0 bit.
o The boundary between two frames can be determined by locating the flag pattern.
Process of adding extra bit to ensure flag sequence does not appear in the data

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

Basic Error Detection:
Error
o Data are transmitted in the network. The Network should ensure complete and accurate
delivery of data from the source node to destination node.
o The Data can be corrupted during transmission. Many factors can corrupt or alter the
data that leads to an error.
o Transmission error.
o For reliable communication, errors must be detected and corrected.
o Error detection and correction are implemented either at the data link layer or the
transport layer of the OSI model.
Types of Error
Several types of error may occur during transmission over the network:
1-bit error
o Only one bit is changed in the data during transmission from the source to the destination
node i.e., either 0 is changed to 1 or 1 is changed to 0
o This error will not appear generally in case of serial transmission. But it might appear in
case of parallel transmission.

Lost Message (Frame)

o The sender has sent the frame but that is not received properly, this is known as loss of
frame during transmission.
o To deal with this type of error, a retransmission of the sent frame is required by the
sender.

Burst error
o 2 or more bits of data are altered during transmission from the source to the destination
node.
o It is not necessary that error will appear in consecutive bits.
o Size of burst error is from the first corrupted bit to the last corrupted bit.
o An n-bit burst error is a string of bits inverted during transmission.
o This error will hardly occur in case of parallel transmission.

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

 o It is difficult to deal with all corrupted bits at one instance.

Error Detection:
 The main goal of a network is accurate, error-free data delivery to the receiver.
 Data may get corrupted due to noise or other transmission issues.
 Error detection is required to identify errors before correction.
 A simple method is sending data twice and comparing it at the receiver, but this causes
high overhead and increased transmission time.
 Hence, redundancy is used by adding extra (redundant) bits to each data frame.
 These redundant bits help the receiver detect or correct errors.
 After verification, redundant bits are discarded.
 Errors can be handled by retransmission or by using error-correcting codes.
 Thus, sending extra bits with data is essential for error detection and correction.

Redundancy check methods commonly used in data transmission are:

o Checksum
o CRC
o Parity check
Checksum:
o The checksum generator divides the given input data into equal segments of k bits(8 or
16)

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

 o Checksum = check + sum
o Sender side  Checksum creation, Receiver side  Checksum validation
Operation at Sender side:
o Break the original message into ‘K’ number of blocks with ‘N’ bits in each block
o Sum all the ‘K’ data blocks
o Add the carry to the sum, if any
o Do 1’s complement to the sum is known as Checksum
o This result is known as the checksum and it is appended with the data stream.
o This appended data stream is transmitted across the network on the transmission media.
Operation at Receiver side:
o Collect all the data blocks including the checksum
o Sum all the data blocks and checksum
o If the result is all 1’s then accept, otherwise data can be discarded.
Example 1:
o Sender’s data 0000001001010000
00000010
01010000
Sum 01010010
o Checksum (Compliment) 10101101
o Data with appended checksum: 00000010 01010000 10101101
o Receiver’s accept the data as : 00000010 01010000 10101101
At receiver’s end : 00000010
01010000
10101101
sum 11111111
o As data sum is all 1’s it indicates that the data received at the receiver’s end is error free
so, it will be accepted by the receiver.
Example 2:
Sender data: 10011001 11100010 00100100 10000100
Receiver Data: 10011001 11100010 00110100 10000100
Check the data using checksum method to find at receivers end error free delivered or not.

Cyclic Redundancy Check (CRC):

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

Cyclic Redundancy Check (CRC) is an error detection technique used in computer networks to
detect accidental changes to raw data during transmission.
It is based on polynomial division using modulo-2 arithmetic.
 CRC is more powerful and reliable than parity check and checksum methods.
 Unlike checksum scheme, which is based on addition, CRC is based on binary division.
 In modulo 2 arithmetic there are no carriers for addition and borrows for subtraction.
 Bit strings as representative of polynomials with coefficients of 0 and 1 only.
 The sender divides the data by a generator polynomial and appends the remainder (CRC
bits) to the frame.
 The receiver divides the received frame by the same generator polynomial.
 If the remainder is zero, the data is error-free; otherwise, an error is detected.
Example:
Bit sequence: 1 0 0 1 0 1
Polynomial representation:

That is:

Modulo-2 Arithmetic
CRC uses modulo-2 arithmetic, which has the following properties:
 No carry in addition and No borrow in subtraction
 Addition and subtraction are performed using XOR operation
Operation Result
0⊕0 0
0⊕1 1
1⊕0 1
1⊕1 0

CRC Works
1. At the Sender
1. Choose a generator polynomial (G)
Example: 1011
2. Append (length of G − 1) zeros to the data.

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

 3. Perform modulo-2 division (XOR, no carry).
4. The remainder is the CRC.
5. Append the CRC to the original data and transmit.
2. At the Receiver
1. Divide the received data (data + CRC) by the same generator polynomial.
2. If the remainder is 0, data is error-free.
3. If the remainder is non-zero, error is detected.
Division in CRC Encoder

Division in CRC Decoder for two cases

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

Example:
Explain the Cyclic Redundancy Check (CRC) error detection technique and, for the data bit

sequence 1011101 with generator polynomial (binary 10101), show

how CRC bits are generated using modulo-2 division and write the final transmitted frame,
frame also
explaining how the receiver detects errors.

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT

Here, we got remainder as 0, the frame is accepted at receiver side.

If we modify any bit in the transmitted data from sender to receiver, dividing with generator
with data (data + CRC) we will not get 0 as rremainder.
emainder. So the frame is to be rejected at receiver
side.

Faculty: B. Thilak Reddy, HoD, Dept of IT, RGUKT