ADVANCED COMPUTER

NETWORKS

Dr. Irfana Memon

Department of CSE, QUEST

https://sites.google.com/a/quest.edu.pk/dr-irfana-memon/lecture-slides
Course Content
NO TOPIC
01 Introduction: Motivations of studying networking

02 Foundation (Problem: Building a network)

03 Models
04 Network Data Link Layer

05
06
07
08
09
10
11
12
Chapter 04
Data Link Network
Chapter 4: Outline

• Introduction: What is data link layer?

• Data Encoding
• Framing
• Error detection and Correction in data link layer
• Reliable delivery
What is data link layer?
• The primary service of the data
link layer is to support error-
free transmission.
• The physical layer sends the
information from the sender's
hub to the receiver's hub as raw
bits.
• The data link layer must identify
and correct any bug in the
communicated data.
• It takes packets from the
network layer and divides the
packets into frames which are
shared by the sender through
the physical layer, as
demonstrated in the diagram
below −
Functions of data link layer
The functions of the data link layer are explained below −

•Framings: It splits packets which are obtained from the network layer
into the controllable units known as frames.
•Physical Addressing: It inserts a header to the frame to represent the
physical address of the sender and receiver of the frame.
•Error Control: This is the leading service of the data link layer. It helps
the protocols to identify error frames and to provide the communication
of accurate frames.
•Flow Control: It supports a flow control structure to prevent a quick
transmitter from defeating a slow receiver by buffering more bits.
•Access Control: The data link layer protocol decides which device has
control over the connection at any provided time, when the other systems
are linked to a parallel connection.
Data Encoding
• Data Encoding is the process of using various
patterns of voltage or current levels to
represent 1s and 0s of the digital signals on the
transmission link.
• The common types of encoding are Unipolar, Polar,
Bipolar, and Manchester.
Data Encoding Techniques

The data encoding technique is divided into the following

types, depending upon the type of data conversion.
• Analog data to Analog signals
• Analog data to Digital signals
• Digital data to Analog signals
• Digital data to Digital signals
Analog data to Analog signal

• The modulation techniques such as Amplitude

Modulation, Frequency Modulation and Phase
Modulation of analog signals, fall under this category.
Analog data to Digital signals
• This process can be termed as digitization, which is
done by Pulse Code Modulation PCMPCM.
• Hence, it is nothing but digital modulation.
• As we have already discussed, sampling and
quantization are the important factors in this.
• Delta Modulation gives a better output than PCM.
Digital data to Analog signals

• The modulation techniques such as Amplitude Shift

Keying ASKASK, Frequency Shift Keying FSKFSK, Phase
Shift Keying PSKPSK, etc., fall under this category.
Digital data to Digital signals

• There are several ways to map digital data to digital

signals. Some of them are −
 Non Return to Zero (NRZ)
 NRZ - L NRZ–LEVEL
 NRZ - I NRZ–INVERTED
 Bi-phase Encoding
 Bi-phase Manchester
 Differential Manchester
NRZ
• NRZ Codes has 1 for High voltage level and 0 for Low
voltage level.
• The main behavior of NRZ codes is that the voltage level
remains constant during bit interval.
• The end or start of a bit will not be indicated and it will
maintain the same voltage state, if the value of the
previous bit and the value of the present bit are same.
• The following figure explains the concept of NRZ coding.
NRZ

If the above example is considered, as there is a long

sequence of constant voltage level and the clock
synchronization may be lost due to the absence of bit
interval, it becomes difficult for the receiver to differentiate
between 0 and 1.
There are two variations in NRZ namely −
 NRZ-L
 NRZ-I
NRZ-LEVEL

• There is a change in the polarity of the signal, only

when the incoming signal changes from 1 to 0 or
from 0 to 1.
• It is the same as NRZ, however, the first bit of the
input signal should have a change of polarity.
NRZ-INVERETED
• If a 1 occurs at the incoming signal, then there occurs a
transition at the beginning of the bit interval.
• For a 0 at the incoming signal, there is no transition at
the beginning of the bit interval.
• NRZ codes has a disadvantage that the synchronization
of the transmitter clock with the receiver clock gets
completely disturbed, when there is a string
of 1s and 0s.
• Hence, a separate clock line needs to be provided.
Bi-Phase Encoding
• The signal level is checked twice for every bit time,
both initially and in the middle.
• Hence, the clock rate is double the data transfer rate
and thus the modulation rate is also doubled.
• The clock is taken from the signal itself. The
bandwidth required for this coding is greater.
• There are two types of Bi-phase Encoding.
 Bi-phase Manchester
 Differential Manchester
Bi-phase Manchester

• In this type of coding, the transition is done at the

middle of the bit-interval.
• The transition for the resultant pulse is from High
to Low in the middle of the interval, for the input
bit 1.
• While the transition is from Low to High for the
input bit 0.
Differential Manchester

• In this type of coding, there always occurs a transition

in the middle of the bit interval.
• If there occurs a transition at the beginning of the bit
interval, then the input bit is 0.
• If no transition occurs at the beginning of the bit
interval, then the input bit is 1.
Summary of coding
• The following figure illustrates the waveforms of NRZ-L,
NRZ-I, Bi-phase Manchester and Differential
Manchester coding for different digital inputs.
FRAMING
FRAMING
• Data-link layer takes the packets from the Network Layer and
encapsulates them into frames.
• If the frame size becomes too large, then the packet may be
divided into small sized frames.
• Smaller sized frames makes flow control and error control more
efficient.
• Then, it sends each frame bit-by-bit on the hardware.
• At receiver’s end, data link layer picks up signals from hardware
and assembles them into frames.
Parts of a Frame
A frame has the following parts −
•Frame Header − It contains the source and the destination
addresses of the frame.
•Payload field − It contains the message to be delivered.
•Trailer − It contains the error detection and error correction
bits.
•Flag − It marks the beginning and end of the frame.
Types of Framing

Framing can be of two types, fixed sized framing and

variable sized framing.
• Fixed-sized Framing
• Variable – Sized Framing
Fixed-size framing

• Here the size of the frame is fixed and so the frame length
acts as delimiter of the frame.
• Consequently, it does not require additional boundary
bits to identify the start and end of the frame.

Example − ATM cells.

Variable-sized Framing
• Here, the size of each frame to be transmitted may be different. So
additional mechanisms are kept to mark the end of one frame and
the beginning of the next frame.
• It is used in local area networks.
• Two ways to define frame delimiters in variable sized framing are −
• Length Field − Here, a length field is used that determines the size
of the frame. It is used in Ethernet (IEEE 802.3).
• End Delimiter − Here, a pattern is used as a delimiter to determine
the size of frame. It is used in Token Rings. If the pattern occurs in
the message, then two approaches are used to avoid the situation −
• Byte – Stuffing − A byte is stuffed in the message to differentiate
from the delimiter. This is also called character-oriented framing.
• Bit – Stuffing − A pattern of bits of arbitrary length is stuffed in
the message to differentiate from the delimiter. This is also called
bit – oriented framing.
Error detection and Correction
in data link layer
Error detection and Correction
in data link layer

• Data-link layer uses error control techniques to

ensure that frames, i.e. bit streams of data, are
transmitted from the source to the destination with a
certain extent of accuracy.
Errors

• When bits are transmitted over the computer

network, they are subject to get corrupted due to
interference and network problems.
• The corrupted bits leads to spurious data being
received by the destination and are called errors.
Types of Errors
Errors can be of three types, namely single bit errors, multiple bit
errors, and burst errors.
•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.
Types of Errors
• Multiple bits error − In the received frame, more than one bits
are corrupted.

• Burst error − In the received frame, more than one consecutive

bits are corrupted.
Error Control
Error control can be done in two ways
•Error detection − Error detection involves checking whether
any error has occurred or not. The number of error bits and the
type of error does not matter.
•Error correction − Error correction involves ascertaining the
exact number of bits that has been corrupted and the location of
the corrupted bits.

•For both error detection and error correction, the sender needs
to send some additional bits along with the data bits.
•The receiver performs necessary checks based upon the
additional redundant bits.
•If it finds that the data is free from errors, it removes the
redundant bits before passing the message to the upper layers.
Error Detection Techniques

There are three main techniques for detecting

errors in frames:
• Parity Check
• Checksum
• 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 parity bit
value is 0. If the number of 1s is odd then parity bit value is 1.
 In case of odd parity: If a number of 1s is odd then parity bit
value is 0. If a number of 1s is even then parity bit value is 1.
• 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.
• The parity check is suitable for single bit error detection only.
Checksum
• In this error detection scheme, the following procedure is
applied:
 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.
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 divisor.
• The receiver divides the incoming data unit by the 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.
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:
•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.
Error Correction Codes
The four main error correction codes are
• Hamming Codes
• Binary Convolution Code
• Reed – Solomon Code
• Low-Density Parity-Check Code
Hamming Codes
• Hamming code is a block code that is capable of
detecting up to two simultaneous bit errors and
correcting single-bit errors.
• It was developed by Richard Hamming for error
correction.
• In this coding method, the source encodes the message
by inserting redundant bits within the message.
• These redundant bits are extra bits that are generated
and inserted at specific positions in the message itself
to enable error detection and correction.
• When the destination receives this message, it
performs recalculations to detect errors and find the
bit position that has error.
Hamming Code: Procedure
The procedure for single error correction by Hamming
Code includes two parts, encoding at the sender’s end and
decoding at receiver’s end.
Encoding a message by Hamming Code
The procedure used by the sender to encode the message
encompasses the following steps −
Step 1 − Calculation of the number of redundant bits.
Step 2 − Positioning the redundant bits.
Step 3 − Calculating the values of each redundant bit.
Once the redundant bits are embedded within the
message, this is sent to the destination.
Hamming Code: Procedure
Step 1 − Calculation of the number of redundant bits.
•If the message contains m number of data bits, r number of
redundant bits are added to it so that is able to indicate at
least (m + r + 1) different states.
•Here, (m + r) indicates location of an error in each of bit
positions and one additional state indicates no error.
•Since, r bits can indicate 2r states, 2r must be at least equal
to (m + r + 1).
•Thus the following equation should hold −
2r ≥ + + 1
Example 1 − If the data is of 7 bits, i.e. m = 7, the minimum
value of r that will satisfy the above equation is 4, (24 ≥ 7 + 4 +
1). The total number of bits in the encoded message, (m + r) =
11. This is referred as (11,4) code.
Hamming Code: Procedure
Step 2 − Positioning the redundant bits.
•The r redundant bits placed at bit positions of powers
of 2, i.e. 1, 2, 4, 8, 16 etc.
•They are referred in the rest of this text as r1 (at
position 1), r2 (at position 2), r3 (at position 4), r4 (at
position 8) and so on.
Example 2 − If, m = 7 comes to 4, the positions of the
redundant bits are as follows −
Hamming Code: Procedure
Step 3 − Calculating the values of each redundant bit.
•The redundant bits are parity bits.
•A parity bit is an extra bit that makes the number of 1s
either even or odd.
•The two types of parity are −
•Even Parity − Here the total number of bits in the
message is made even.
•Odd Parity − Here the total number of bits in the
message is made odd.
•Each redundant bit, ri, is calculated as the parity,
generally even parity, based upon its bit position.
•It covers all bit positions whose binary representation
includes a 1 in the ith position except the position of ri.
Hamming Code: Procedure
Thus −
•r1 is the parity bit for all data bits in positions whose
binary representation includes a 1 in the least significant
position excluding 1 (3, 5, 7, 9, 11 and so on)
•r2 is the parity bit for all data bits in positions whose
binary representation includes a 1 in the position 2 from
right except 2 (3, 6, 7, 10, 11 and so on)
•r3 is the parity bit for all data bits in positions whose
binary representation includes a 1 in the position 3 from
right except 4 (5-7, 12-15, 20-23 and so on)
Hamming Code: Example
Example 3 − Suppose that the message 1100101
needs to be encoded using even parity Hamming code.
Here, m = 7 and r comes to 4. The values of redundant
bits will be as follows −

Hence, the message sent will be 11000101100.

Hamming Code: Decoding
Decoding a message in Hamming Code
Once the receiver gets an incoming message, it performs
recalculations to detect errors and correct them. The
steps for recalculation are −
Step 1 − Calculation of the number of redundant bits.
Step 2 − Positioning the redundant bits.
Step 3 − Parity checking.
Step 4 − Error detection and correction
Hamming Code: Decoding
Step 1) Calculation of the number of redundant bits
Using the same formula as in encoding, the number of
redundant bits are ascertained.
2r ≥ + + 1
where m is the number of data bits and r is the number of
redundant bits.

Step 2) Positioning the redundant bits

The r redundant bits placed at bit positions of powers of 2,
i.e. 1, 2, 4, 8, 16 etc.
Hamming Code: Decoding
Step 3) Parity checking
• Parity bits are calculated based upon the data bits and
the redundant bits using the same rule as during
generation of c1, c2, c3, c4 etc.
• Thus
c1 = parity(1, 3, 5, 7, 9, 11 and so on)
c2 = parity(2, 3, 6, 7, 10, 11 and so on)
c3 = parity(4-7, 12-15, 20-23 and so on)
Hamming Code: Decoding

Step 4) Error detection and correction

• The decimal equivalent of the parity bits binary values
is calculated.
• If it is 0, there is no error. Otherwise, the decimal value
gives the bit position which has error.
• For example, if c1c2c3c4 = 1001, it implies that the data
bit at position 9, decimal equivalent of 1001, has error.
• The bit is flipped (converted from 0 to 1 or vice versa)
to get the correct message.
Hamming Code: Decoding
(Example)
Example 4 − Suppose that an incoming message 11110101101 is received.
Step 1 − At first the number of redundant bits are calculated using the formula 2r ≥ m + r +
1. Here, m + r + 1 = 11 + 1 = 12. The minimum value of r such that 2r ≥ 12 is 4.
Step 2 − The redundant bits are positioned as below −

Step 3 − Even parity checking is done −

c1 = even_parity(1, 3, 5, 7, 9, 11) = 0
c2 = even_parity(2, 3, 6, 7, 10, 11) = 0
c3 = even_parity (4, 5, 6, 7) = 0
c4 = even_parity (8, 9, 10, 11) = 0
Step 4 - Since the value of the check bits c1c2c3c4 = 0000 = 0, there are no errors in this
message.
Hamming Code for double error
detection
The Hamming code can be modified to correct a single
error and detect double errors by adding a parity bit as the
MSB, which is the XOR of all other bits.
Example 5 − If we consider the codeword, 11000101100,
sent as in example 3, after adding P =
XOR(1,1,0,0,0,1,0,1,1,0,0) = 0, the new codeword to be sent
will be 011000101100.
Flow Control
Flow Control
• Flow control is a technique that 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.
• In data link layer, flow control restricts the number of
frames the sender can send before it waits for an
acknowledgment from the receiver.
Approaches of Flow control
Flow control can be broadly classi ied into two categories −

Feedback based Flow Control

• In these protocols, the sender sends frames after it
has received acknowledgments from the user.
• This is used in the data link layer.
Approaches of Flow control
Flow control can be broadly classi ied into two categories −

Rate based Flow Control

• These protocols have built in mechanisms to restrict
the rate of transmission of data without requiring
acknowledgment from the receiver.
• This is used in the network layer and the transport
layer.
Flow control Techniques in data
link layer
• Data link layer uses feedback based flow control
mechanisms.
• There are two main techniques −
Stop and Wait

This protocol involves the following transitions −

•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 sender the next frame in queue.
Sliding Window
• This protocol improves the efficiency of stop and wait
protocol by allowing multiple frames to be transmitted
before receiving an acknowledgment.
• The working principle of this protocol can be described as
follows −
• Both the sender and the receiver has finite sized buffers
called windows. The sender and the receiver agrees 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.
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.
Wish You Good Luck

60