Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
BCA 6th Semester
Subject: BCA 6005 Computer Networks
Module IV: Data Link Layer
The data link layer converts the raw transmission facility provided by the physical layer to a reliable and
error-free link. It is the protocol layer in a program that handles the moving of data into and out of a
physical link in a network. Data bits are encoded, decoded and organized as frames in the data link layer,
before they are transported between two adjacent nodes on the same LAN or WAN. The data link layer
also determines how multiple devices share a common link for collision free transmission of frames. The
figure below describes the functionality of the data link layer at sender and receiver sides.
4.1 Design Issues :
1. Providing interface to the network layer services
2. Framing
3. Flow Control
4. Error Control
5. Synchronization
BCA6005 Computer Network, Module IV Page 1
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
6. Link Configuration Control
7. Medium Access Control
· Data link layer provides acknowledge connectionless service, unacknowledged connectionless
service and acknowledge connection oriented service to the network layer.
· Framing refers to translation of physical layer’s raw bits into larger aggregate (or) discrete units
called frames.
· Flow Control refers to the mechanisms that make sure that the sending station cannot overwhelm
the receiving station.
· Error control mechanisms can detect as well as correct errors. Various techniques are available
for detection and correction of error.
· Receiver must know when the data begins & when it ends and also receiver should be able to
distinguish between each bit in the frame of data which are achieved by means of
synchronization.
· Link Configuration Control involves :
A Link Topology: Physical arrangement of the connection between the devices.
B Link Duplexity: Simplex – only one device can transmit to other. (ie., one
direction transmit), Half duplex – Both device can transmit to each other, but not
simultaneously, Full duplex – Both device can transmit simultaneously.
· Medium access control deals with the techniques used at data link layer to resolve the multiple
access problems in multi shared link.
4.2 Error Detection Techniques :
When bits are transmitted over the computer network, they are subject to get corrupted due to
transmission impairments and network problems. The corrupted bits leads to false data being received by
the destination and are called errors. The error can be classified as single bit error and burst error.
Single bit error: In the received frame, only one bit has been corrupted, i.e. either changed from 0 to 1 or
from 1 to 0
Burst error: In the received frame, more than one bits are corrupted i.e. either changed from 0 to 1 or
from 1 to 0.
Data-link layer uses error control techniques to ensure that frames (bit streams of data) are transmitted
from the source to the destination with a certain extent of accuracy. Error control involves error detection
and error correction.
Error detection: Error detection involves checking whether any error has occurred or not in received
frame. The number of error bits and the type of error does not matter. There are a number of techniques
for detecting errors in frames such as:
1. Parity Check
2. Checksum
BCA6005 Computer Network, Module IV Page 2
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
3. Cyclic Redundancy Check (CRC).
Parity Check
The parity check is done by adding an extra bit, called parity bit to the data to make a number of 1s either
even in case of even parity or odd in case of odd parity.
While creating a frame, the sender counts the number of 1s in it and adds the parity bit in the following
way
· In case of even parity: If a number of 1s is even then the value of parity bit is 0. If the number of
1s is odd then the value of parity bit is 1. Example
1000011100000000000000000000000000000111100000000000000001001010100011 0
I-----------------------------------------------Frame contents---------------------------------------------I P-bit
· In case of odd parity: If a number of 1s is odd then the value of parity bit is 0. If a number of 1s
is even then the value of parity bit is 1. Example
1000011100000000000000000000000000000111100000000000000001001010100011 1
I-----------------------------------------------Frame contents---------------------------------------------I P-bit
On receiving a frame, the receiver counts the number of 1s in it. In case of even parity check, if the count
of 1s is even, the frame is accepted, otherwise, it is rejected. A similar rule is adopted for odd parity
check.
Advantages:
§ Detects any single bit error.
§ In fact, detects any error involving odd number of bits.
Disadvantages:
§ Not suitable for detecting burst errors.
Checksum
In this error detection scheme, the following steps are required
· Data is divided into fixed sized frames or segments.
· The sender adds the segments using 1’s complement arithmetic to get the sum. It then
complements the sum to get the checksum and sends it along with the data frames.
· The receiver adds the incoming segments along with the checksum using 1’s complement
arithmetic to get the sum and then complements it.
· If the result is zero, the received frames are accepted; otherwise, they are discarded.
BCA6005 Computer Network, Module IV Page 3
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
Cyclic Redundancy Check (CRC)
Cyclic Redundancy Check (CRC) involves binary division of the data bits being sent by a predetermined
divisor agreed upon by the communicating system. The divisor is generated using polynomials.
· Here, the sender performs binary division of the data segment by the divisor. It then appends the
remainder called CRC bits to the end of the data segment. This makes the resulting data unit
exactly divisible by the predetermined divisor.
· The receiver divides the incoming data unit by the predetermined divisor. If there is no
remainder, the data unit is assumed to be correct and is accepted. Otherwise, it is understood that
the data is corrupted and is therefore rejected.
This method involves the following steps:
Sender:
1. Message (M) to be transmitted is multiplied by 2 N where N is the number of bits required in
desired CRC Code.
2. Divide resultant message by a predetermined divisor P of N+1 bits, the MSB and LSB of P must
not be zero (0).
3. The remainder R (N-bit) so obtained is the CRC Code ( error detection code).
4. Add R to the result obtained in step-1 to make a frame T to be transmitted.
5. Send the frame T.
Receiver:
1. On receiving frame T receiver divides T by the same predetermined divisor P.
2. If remainder is zero (0) then the frame is accepted otherwise it is rejected.
Example: Compute the CRC code for the message (M): 1010001101 using divisor (P): 110101.
Solution: 1 1 0 1 0 1) 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 (
110101
_________
111011
110101
___________
111010
110101
____________
111110
110101
BCA6005 Computer Network, Module IV Page 4
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
__________
101100
110101
_________
110010
110101
_________
01110
R = 011100 (CRC code)
T = Transmitted Data
1010001101 0 1 1 1 0
4.3 Error Correction Techniques :
Error correction techniques find out the exact number of bits that have been corrupted and as well as their
locations. There are two principle ways to correct the detected error
· Backward Error Correction (Retransmission): If the receiver detects an error in the incoming
frame, it requests the sender to retransmit the frame. It is a relatively simple technique. But it can
be efficiently used only where retransmitting is not expensive as in fiber optics and the time for
retransmission is low relative to the requirements of the application.
· Forward Error Correction: If the receiver detects some error in the incoming frame, it executes
error-correcting code that generates the actual frame. This saves bandwidth required for
retransmission. It is inevitable in real-time systems. However, if there are too many errors, the
frames need to be retransmitted.
4.4 Flow Control :
Flow control technique allows two stations working at different speeds to communicate with each other. It
is a set of measures taken to regulate the amount of data that a sender sends so that a fast sender does not
overwhelm a slow receiver. The flow control restricts the number of frames the sender can send before it
waits for an acknowledgment from the receiver. There are two main flow control techniques used in the
data link layer:
BCA6005 Computer Network, Module IV Page 5
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
Stop and Wait flow control:
In this approach
· The sender sends a frame and waits for acknowledgment.
· Once the receiver receives the frame, it sends an acknowledgment frame back to the sender.
· On receiving the acknowledgment frame, the sender understands that the receiver is ready to
accept the next frame. So it sends the next frame
Disadvantages:
§ Only one frame is transmitted at time.
§ It is a slow process
§ It is inefficient approach.
Sliding Window flow control:
This approach allows the transmission of multiple frames before receiving an acknowledgment. It works
as follows:
· Both the sender and the receiver have finite sized buffers called windows. The sender and the
receiver agree upon the number of frames to be sent based upon the buffer size.
· The sender sends multiple frames in a sequence, without waiting for acknowledgment. When its
sending window is filled, it waits for acknowledgment. On receiving acknowledgment, it
advances the window and transmits the next frames, according to the number of
acknowledgments received.
Example
Suppose that we have sender window and receiver window each of size 4. So the sequence numbering of
both the windows will be 0,1,2,3,0,1,2 and so on. The following diagram shows the positions of the
windows after sending the frames and receiving acknowledgments.
BCA6005 Computer Network, Module IV Page 6
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
Sliding window protocols:
Sliding Window protocols are of two types
· Go – Back – N ARQ
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.
· Selective Repeat ARQ
This protocol also provides for sending multiple frames before receiving the acknowledgment for
the first frame. However, here only the erroneous or lost frames are retransmitted, while the good
frames are received and buffered.
BCA6005 Computer Network, Module IV Page 7
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
4.5 Common Data Link Layer Protocols:
4.6 High Level Data Link Protocol (HDLC):
· HDLC is based upon SDLC and provides both unreliable service and reliable service.
· It is a bit–oriented protocol that is applicable for both point–to–point and multipoint
communications
· Data is organized into frames. A frame is transmitted via the network to the destination that
verifies its successful arrival.
· It supports both half-duplex and full-duplex communication.
BCA6005 Computer Network, Module IV Page 8
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
Type of stations:
HDLC defines three types of stations.
· Primary Station: A primary station takes care of the data link management. The frames sent by
a primary station are called commands.
· Secondary Station: A secondary station operates under the control of a primary station. The
frames sent by the secondary station are called responses.
· Combined Station: A combined station can act as primary as well as secondary stations.
Therefore it can send both commands and responses.
Link Configuration:
HDLC uses two link configurations.
· Balanced Configuration
· Unbalanced Configuration
Data Transfer modes:
HDLC operates in three data transfer modes.
· Normal response mode (NRM) : It is a synchronous mode of communication. This mode is
suitable for point-ta-point as well as point-to-multipoint configurations.
· Asynchronous Response Mode (ARM): This mode is used for communication between primary
and secondary stations. As the name indicates it is an asynchronous mode o(communication.
· Asynchronous Balanced Mode (ABM): This mode is applicable to the point to point
communication between two combined stations. As both these stations are combined stations,
they are capable of link management functions.
Frame Structure:
The HDLC frame consists of Flag, Address, Control, Data, and CRC fields as shown below:
Flag (both opening and closing flags): 8 bits (01111110 or 7E hex).
Address: It is normally 8 or 16 bits in length. A leading 'zero' bit (MSB) indicates a unicast message; the
remaining bits provide the destination node address. A leading 'one' bit (MSB) location indicates
multicast message; the remaining bits provide the group address.
BCA6005 Computer Network, Module IV Page 9
Birla Institute of Technology Mesra Off-Campus Lalpur, Ranchi 834001
Control: The field is 8 bits, or 16 bits wide and indicates whether the frame is a Control or Data frame.
The field contains sequence number (HDLC frames are numbered to ensure delivery), poll (you need to
reply) and final (indicating that this is the last frame) bits.
Data (Payload): This is the information that is carried from node to node. This is a variable field.
Sometimes padded with extra bits to provide fixed length.
FCS (Frame Check Sequence) or CRC (Cyclic Redundancy Code): It is normally 16 bits wide. Frame
Check Sequence is used to verify the data integrity. If the FCS fails, the frame is discarded.
HDLC Frame Types:
The control field in HDLC is also used to indicate the frame type. There are three types of frames
supported by HDLC. These are:
I Frames: These are information frames, and contain user data
S Frames: These are supervisory frames, and contain commands and responses
U Frames: These are un-numbered frames, and typically contain commands and responses.
BCA6005 Computer Network, Module IV Page 10