COMPUTER NETWORK

UNIT-2

DATA LINK LAYERS

DATA LINK LAYER DESIGN ISSUES:

The Data Link Layer in the OSI model is responsible for node-to-node data
transfer, detecting and possibly correcting errors that may occur in the Physical
layer, and managing flow control. It ensures that the data transferred across a
physical link between two devices is reliable and error-free. When designing the
Data Link Layer, several issues arise, which need to be addressed for efficient
communication. These design issues include:

1. Framing

 Problem: When transmitting data, it's crucial to differentiate where one

frame (unit of data) ends, and the next one begins.
 Solution: Frames are created by adding special markers (header and trailer)
to the data. Different methods, like byte stuffing or bit stuffing, are used to
ensure the receiver can recognize frame boundaries.

2. Error Control

 Problem: During transmission, bits may get corrupted due to noise,

interference, or other issues in the physical medium.
 Solution: Error detection and correction mechanisms are employed.
Common error detection methods include parity checks, checksum, and
Cyclic Redundancy Check (CRC). For error correction, methods like
SRM University/Dr.SK GUPTA Page 1
 COMPUTER NETWORK

Automatic Repeat reQuest (ARQ) are used, where corrupted frames are
retransmitted.

3. Flow Control

 Problem: If a sender transmits data too quickly, the receiver's buffer may
overflow, leading to data loss.
 Solution: Flow control protocols like Stop-and-Wait, Sliding Window, and
Acknowledgment (ACK) systems are employed. These allow the receiver
to manage the data rate by either halting the sender or using windowing
techniques to control the number of frames sent without receiving an
acknowledgment.

4. Access Control (for shared links)

 Problem: In a shared medium (like a bus topology or wireless networks),

multiple devices may want to transmit data simultaneously, leading to
collisions.
 Solution: Media Access Control (MAC) protocols like Carrier Sense
Multiple Access (CSMA), Token Passing, and Time Division Multiple
Access (TDMA) are used to coordinate access to the shared medium,
preventing or resolving collisions.

5. Link Management

 Problem: Ensuring the proper establishment, maintenance, and termination

of a connection between two devices.
 Solution: The layer must handle connection setup, frame sequencing, and
proper termination. This includes maintaining synchronization between
devices and recovering from errors like frame loss or duplication.

These issues collectively ensure that data can be reliably and efficiently transferred
across a link, handling potential disruptions, errors, and differences in data rate
between devices.

SRM University/Dr.SK GUPTA Page 2

 COMPUTER NETWORK

FRAMING:

Framing is one of the key design issues in the Data Link Layer, which deals with
how to group or organize bits into manageable units called frames. A frame is the
data packet that is transmitted over the network, and it includes not only the raw
data but also information needed to manage the communication, such as addresses
and error-detection codes.

Why Framing is Important

In a data communication system, the physical layer only deals with a stream of bits
without distinguishing where one piece of data starts or ends. Framing helps in:

 Boundary Identification: It helps the receiver recognize where a frame

starts and ends within the continuous stream of bits.
 Error Detection: Framing allows error detection at the frame level, so only
the specific corrupted frame is retransmitted, rather than the entire data
stream.
 Efficient Data Transmission: Breaking the data into smaller frames ensures
that the entire data is not lost if an error occurs; only the affected frame is
retransmitted.

Methods of Framing

Several techniques can be used to differentiate one frame from another:

1. Character Count (Length Field)

 In this method, the first few bytes of the frame specify the number of bytes
in the frame. The receiver reads this count and knows how many bytes to
expect in the frame.
 Advantages: Simple to implement.
 Disadvantages: If the length field is corrupted, it can result in the loss of
synchronization and frame errors.

2. Byte-Oriented Protocols (Byte Stuffing)

 Flag Bytes: The frame starts and ends with a special flag byte (for example,
the flag byte might be 01111110).

SRM University/Dr.SK GUPTA Page 3

 COMPUTER NETWORK

 Byte Stuffing: If the flag byte appears in the data, a special escape character
is added before it (stuffing), so the receiver does not mistakenly interpret it
as a frame boundary.
 Example Protocol: HDLC (High-level Data Link Control) uses this method.

3. Bit-Oriented Protocols (Bit Stuffing)

 Flag Bits: Similar to byte-oriented protocols, bit-oriented protocols use a

specific pattern (e.g., 01111110 for HDLC) to mark the start and end of a
frame.
 Bit Stuffing: To ensure that the flag pattern does not occur in the data,
whenever a sequence of 5 consecutive 1’s is found in the data, an additional
0 is inserted. This process is called bit stuffing.
 Advantage: More efficient than byte-oriented protocols because any type of
data (not limited to byte boundaries) can be transmitted.

4. Clock-Based Framing (Physical Layer Coding Violations)

 In some systems, clock-based framing techniques are used where specific

physical layer signaling violations or patterns (such as alternating voltage
levels) indicate frame boundaries.
 Advantage: Used in systems where the physical medium supports clock
signals, such as fiber optic or certain wired communication systems.
 Disadvantage: Limited in scope to specific media.

Example of Framing in Action

Let’s consider the HDLC (High-level Data Link Control) protocol:

1. HDLC frames start and end with a unique flag sequence (01111110).
2. Data is framed between these flags.
3. If the flag sequence appears in the actual data, bit stuffing is used to avoid
confusion.

SRM University/Dr.SK GUPTA Page 4

 COMPUTER NETWORK

ERROR DETECTION AND CORRECTION:

Error detection and correction are essential techniques in digital communications and data
storage to ensure data integrity. These methods identify and fix errors that can occur during
transmission or storage due to noise, interference, or other issues. Here’s an overview of both:

1. Error Detection

This involves identifying errors in data transmission. Several methods are used:

 Parity Check: A parity bit is added to data. This bit ensures that the number of 1's is
either even (even parity) or odd (odd parity). It's a simple method but can detect only
single-bit errors.
 Checksum: A sum of the data's bits or bytes is calculated and sent along with the data.
The receiver re-calculates the sum and compares it to the received checksum. If they
differ, an error has occurred.
 Cyclic Redundancy Check (CRC): A more sophisticated method that treats data as a
polynomial and divides it by a known generator polynomial. The remainder (CRC value)
is sent along with the data. The receiver performs the same division and checks for errors.
 Hashing: Hash functions can be used to generate a fixed-length representation of data.
The receiver recalculates the hash to verify integrity.

2. Error Correction

Once an error is detected, error correction techniques try to recover the original data. Common
methods include:

 Hamming Code: Adds redundant bits to the data to both detect and correct errors. It’s
capable of correcting single-bit errors and detecting two-bit errors. The position of the
error can be determined by checking the parity bits.
 Reed-Solomon Code: A block-based error correction code used in many applications
like CDs, DVDs, and QR codes. It can correct multiple random symbol errors and is
widely used for its efficiency in correcting burst errors.
 Forward Error Correction (FEC): A technique where redundant data (extra
information) is added so that the receiver can correct errors without needing
retransmission. FEC codes are widely used in communication systems like satellite links.
 Convolutional Code: This is used for error correction in systems like deep space
communications. It encodes data by applying multiple convolutions, and decoding is
often done using the Viterbi algorithm.
 Automatic Repeat Request (ARQ): Instead of correcting the error, the receiver requests
the sender to retransmit the erroneous packet.

Key Differences:

 Detection vs. Correction: Detection only identifies that an error has occurred, while
correction identifies and fixes the error.

SRM University/Dr.SK GUPTA Page 5

 COMPUTER NETWORK

 Overhead: Error correction typically requires more redundant data than error detection
alone.

These methods ensure that communication systems like the Internet, storage systems, and
wireless networks can function reliably despite potential data errors.

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.

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.

SRM University/Dr.SK GUPTA Page 6

 COMPUTER NETWORK

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

SRM University/Dr.SK GUPTA Page 7

 COMPUTER NETWORK

BYTE AND BIT STUFFING:

Bit Stuffing and Byte Stuffing are two different techniques used in data
communication to handle control information embedded within the data stream,
especially in protocols that use flags to delimit data frames.

1. Bit Stuffing:

Purpose: Bit stuffing is used to ensure that the flag sequence (usually a series of
bits like 01111110 in HDLC) is not interpreted as part of the data.

How It Works:

 In a data transmission protocol that uses flags (like 01111110), the receiver
identifies the start and end of the data frame by this bit pattern.
 To ensure that this bit pattern does not accidentally appear in the data, a
process known as "bit stuffing" is used.
 If five consecutive 1s appear in the data, a 0 is automatically inserted
(stuffed) after them. This prevents the receiver from mistakenly interpreting
the data as a flag.

SRM University/Dr.SK GUPTA Page 8

 COMPUTER NETWORK

Example:

 Original data: 01111110 1011111110 01111110

 After bit stuffing: 01111110 10111111010 01111110

The receiver will remove the extra stuffed 0s when the data is received, restoring
the original bit sequence.

Applications:

 Bit stuffing is used in protocols like HDLC (High-Level Data Link Control)
and PPP (Point-to-Point Protocol).

2. Byte Stuffing:

Purpose: Byte stuffing is similar to bit stuffing but operates at the byte level. It is
used to distinguish between data and control information (such as frame
delimiters).

How It Works:

 Byte stuffing is often used in protocols that use special characters or bytes to
indicate the start and end of a frame, like in PPP or SLIP.
 If a special character (e.g., flag or escape character) appears in the data, an
escape character is inserted before it.
 This allows the receiver to differentiate between actual data and control
sequences.

Example:

 Suppose the flag byte is 0x7E, and the escape byte is 0x7D.
 Original data: Hello 0x7E World
 After byte stuffing: Hello 0x7D 0x5E World

Here, 0x7D 0x5E means that the original byte was 0x7E. The receiver can reverse
this when decoding.

SRM University/Dr.SK GUPTA Page 9

 COMPUTER NETWORK

Applications:

 Byte stuffing is commonly used in byte-oriented protocols like PPP (Point-

to-Point Protocol) and SLIP (Serial Line Internet Protocol).

Summary:

 Bit Stuffing works at the bit level, inserting bits to avoid misinterpretation
of control sequences.
 Byte Stuffing operates at the byte level, inserting escape sequences before
special control characters.

Both techniques are essential in ensuring that the data communication process
remains reliable, preventing the mix-up of control information with actual data.

SRM University/Dr.SK GUPTA Page 10

 COMPUTER NETWORK

CRC:

CRC (Cyclic Redundancy Check) is an error-detection algorithm widely used in

computer networks, data storage systems, and communication protocols.

It is designed to detect accidental changes or errors in data transmission or storage.

The main purpose of CRC is to identify errors that may occur during the
transmission of data over a communication channel or when storing data.

It works by calculating a checksum from the data being transmitted or stored, and
then comparing this checksum with the one calculated at the receiving end. If the
checksums do not match, it indicates that an error has occurred, and the data can be
discarded or retransmitted.

CRC is considered a powerful and efficient error-detection method as it can detect

a wide range of errors, including burst errors, single-bit errors, and multiple-bit
errors. It is commonly used in various network protocols, such as Ethernet, Wi-Fi,
and serial communication, to ensure the integrity of the transmitted data.

HAMMING CODES:

Hamming codes are a class of error-correcting codes that can detect and correct
single-bit errors. Developed by Richard Hamming in 1950, these codes are widely
used in digital communication systems, computer memory, and data transmission
systems where error correction is crucial.

Key Concepts of Hamming Codes

1. Error Detection and Correction:

o Hamming codes can detect and correct single-bit errors.
o They can also detect two-bit errors but cannot correct them.
2. Redundant Bits:
o In Hamming codes, redundant bits (also called parity bits) are added
to data to detect and correct errors. The number of redundant bits
depends on the length of the data.
o If you have m data bits, the number of redundant bits r is chosen so
that: 2r≥m+r+1This ensures that there are enough redundant bits to
cover both the data and the error correction.

SRM University/Dr.SK GUPTA Page 11

 COMPUTER NETWORK

3. Positioning of Redundant Bits:

o The redundant bits are placed at positions that are powers of 2 (1, 2, 4,
8, etc.) in the binary sequence. The positions of these bits help in
calculating the parity for error detection.
4. Hamming Code Structure:
o For a 4-bit message (e.g., 1011), you would need 3 redundant bits (r =
3). The data bits and redundant bits are placed in such a way that the
redundant bits are at positions that are powers of 2.

Bit Position 1 2 3 4 5 6 7
Type r1 r2 d1 r3 d2 d3 d4
Data - - 1 - 0 1 1

o Here, r1, r2, and r3 are the redundant bits, and d1, d2, d3, and d4 are
the data bits.

How Hamming Codes Work:

1. Step 1: Calculate Parity Bits: Each redundant bit (parity bit) covers several
data bits. The parity bits are calculated using even parity (i.e., the number of
1s in the covered bits should be even).
o r1 covers positions 1, 3, 5, and 7.
o r2 covers positions 2, 3, 6, and 7.
o r3 covers positions 4, 5, 6, and 7.

For example:

o r1 = parity(1, 3, 5, 7)
o r2 = parity(2, 3, 6, 7)
o r3 = parity(4, 5, 6, 7)
2. Step 2: Transmit the Data: Once the parity bits are calculated, they are
inserted into the appropriate positions, and the entire bit sequence is
transmitted.
3. Step 3: Detect and Correct Errors: At the receiver's end, the same parity
checks are performed:
o If no error is detected, the data is accepted as correct.
o If an error is detected, the position of the erroneous bit can be
identified by examining which parity checks fail. The position of the
erroneous bit is given by the binary number formed from the failed

SRM University/Dr.SK GUPTA Page 12

 COMPUTER NETWORK

parity check results. This allows the receiver to flip the erroneous bit
and correct the error.

Example of Hamming Code (7, 4):

Suppose we want to encode a 4-bit message 1011.

1. Place the data bits in positions 3, 5, 6, and 7, and leave positions 1, 2, and 4
for the parity bits.

Position 1 2 3 4 5 6 7
Data r1 r2 1 r3 0 1 1

2. Calculate the parity bits:

o r1 checks bits 1, 3, 5, 7 → r1 = parity(1, 1, 0, 1) = 1
o r2 checks bits 2, 3, 6, 7 → r2 = parity(1, 1, 1, 1) = 0
o r3 checks bits 4, 5, 6, 7 → r3 = parity(1, 0, 1, 1) = 0

So the encoded message becomes 1010011.

Error Detection and Correction Example:

Let’s assume an error occurs during transmission, and the receiver gets the data
1110011.

1. Recalculate the parity bits at the receiver:

o r1' = parity(1, 1, 0, 1) = 1 (correct)
o r2' = parity(1, 1, 1, 1) = 0 (correct)
o r3' = parity(1, 0, 1, 1) = 1 (incorrect)

The error is detected because r3 is incorrect. The position of the erroneous

bit can be determined by converting the incorrect parity check results into a
binary number: 011 (in binary), which corresponds to position 3. Therefore,
the bit at position 3 is flipped, correcting the error.

Advantages of Hamming Codes:

 Single-bit error correction: Hamming codes can correct single-bit errors,

which makes them suitable for many real-time communication systems.
 Efficient: Hamming codes are simple to implement in both hardware and
software.
SRM University/Dr.SK GUPTA Page 13
 COMPUTER NETWORK

Limitations:

 Limited error detection: Hamming codes can detect double-bit errors but
cannot correct them. They also cannot detect more than two errors.
 Inefficiency for large data: As the number of bits increases, more
redundant bits are needed, making Hamming codes less efficient for very
large data blocks.

Applications:

 Computer memory (ECC): Error correction in RAM and other memory

systems.
 Communication systems: Error detection and correction in network
protocols.
 Data storage: In systems like RAID for detecting and correcting errors in
stored data.

Hamming codes are one of the simplest and most fundamental methods of error
correction, making them widely used in both small and large-scale systems.

ELEMENTARY DATA LINK PROTOCOLS: SLIDING WINDOW

PROTOCOLS:

Elementary Data Link Protocols are simple protocols used in the Data Link Layer
of the OSI model to manage data transmission between directly connected devices.
These protocols are responsible for error detection, framing, and flow control to
ensure reliable and organized data transfer. Below are some of the most basic or
"elementary" data link protocols:

SRM University/Dr.SK GUPTA Page 14

 COMPUTER NETWORK

1. Unrestricted Simplex Protocol (Protocol 1)

 Type: Unrestricted and Simplex

 Description: In this protocol, communication is unidirectional (simplex),
meaning that data is only sent from one sender to one receiver, and no
feedback is expected from the receiver. There's no need for error detection
or correction.
 Features:
o No flow control.
o No error handling.
o Continuous transmission of data from the sender to the receiver.
o Used in ideal conditions where transmission errors are not expected.

Example:

 Suitable for one-way communication systems where the medium is noise-

free or when acknowledgment is not required, like some radio or TV
broadcasts.
SRM University/Dr.SK GUPTA Page 15
 COMPUTER NETWORK

2. Stop-and-Wait Protocol (Protocol 2)

 Type: Stop-and-Wait and Simplex

 Description: In this protocol, the sender transmits a frame and then stops
and waits for an acknowledgment from the receiver before sending the next
frame. This helps in ensuring that each frame is correctly received before
moving on to the next one.
 Features:
o Flow control: The sender waits for acknowledgment before sending
the next frame.
o No error detection or retransmission in case of errors.
o Simple and easy to implement, but inefficient in terms of throughput.

Example:

 Used in systems where error-free communication is assumed but flow

control is still needed. For example, early dial-up modems.

3. Stop-and-Wait with Error Detection (Protocol 3)

 Type: Stop-and-Wait and Simplex with Error Detection

 Description: This protocol is similar to the Stop-and-Wait Protocol but
introduces error detection (typically using checksums or CRC). If the
receiver detects an error in a frame, it discards the frame and does not send
an acknowledgment, prompting the sender to resend the frame after a
timeout.
 Features:
o Error detection using mechanisms like CRC (Cyclic Redundancy
Check).
o Retransmission in case of errors (due to timeouts).
o The sender stops and waits for either an acknowledgment (ACK) or
the timeout to resend the frame.

Example:

 Used in systems where communication errors might occur, such as in early

network protocols or unreliable transmission mediums.

4. Stop-and-Wait ARQ (Automatic Repeat Request)

 Type: Stop-and-Wait with Error Detection and Retransmission

SRM University/Dr.SK GUPTA Page 16

 COMPUTER NETWORK

 Description: This protocol is an extension of the Stop-and-Wait protocol

that adds error detection and automatic retransmission. When the receiver
detects an error, it sends a Negative Acknowledgment (NAK), prompting the
sender to retransmit the frame. If an acknowledgment (ACK) is received, the
sender sends the next frame.
 Features:
o Acknowledgments (ACK) and Negative Acknowledgments (NAK)
are used for flow control and error handling.
o The sender retransmits frames upon receiving NAK or after a timeout.
o Reliable but slow, as the sender waits for an acknowledgment after
each frame.

Example:

 Widely used in communication systems where reliable data transfer is

required, such as in satellite communication or wireless networks.

5. Go-Back-N ARQ

 Type: Sliding Window Protocol

 Description: This is a more advanced protocol compared to Stop-and-Wait.
Here, the sender can send multiple frames before needing an
acknowledgment (depending on the window size). If an error occurs
(detected by a NAK or timeout), the sender goes back to the last
acknowledged frame and retransmits all subsequent frames (hence the name
"Go-Back-N").
 Features:
o Sliding window mechanism for managing multiple frames.
o Improved efficiency over Stop-and-Wait because multiple frames are
sent before waiting for acknowledgment.
o In case of an error, frames are retransmitted from the point of failure
onward.

Example:

 Used in systems where error rates are low, and retransmitting all frames
upon error is still feasible. For example, in older versions of TCP and
wireless communication systems.

6. Selective Repeat ARQ

SRM University/Dr.SK GUPTA Page 17

 COMPUTER NETWORK

 Type: Sliding Window Protocol

 Description: This protocol allows the sender to send multiple frames
without waiting for acknowledgment, just like Go-Back-N, but with a key
improvement: only the frames that were received with errors are
retransmitted (instead of retransmitting all frames after the error, like in Go-
Back-N). This makes it more efficient.
 Features:
o Sliding window mechanism for both sender and receiver.
o Frames are individually acknowledged, allowing for selective
retransmission of erroneous frames.
o More efficient than Go-Back-N because only the frames with errors
are retransmitted.

Example:

 Commonly used in modern communication systems like the TCP/IP

protocol stack, where higher efficiency is needed.

7. Simplified Sliding Window Protocol

 Type: Sliding Window Protocol

 Description: The sliding window protocol improves efficiency by allowing
the sender to send several frames before waiting for an acknowledgment.
The "window" is the range of sequence numbers the sender is allowed to
send without waiting for an acknowledgment.
 Features:
o Flow control and error detection using a sliding window.
o Sender can transmit multiple frames before waiting for an
acknowledgment.
o The size of the window determines how many unacknowledged
frames can be in transit.

Example:

 Found in various modern protocols for network communication, such as

TCP, where efficiency and reliability are important.

Key Features of Elementary Data Link Protocols:

SRM University/Dr.SK GUPTA Page 18

 COMPUTER NETWORK

1. Flow Control: Ensures that the sender does not overwhelm the receiver with
too much data. Protocols like Stop-and-Wait ensure that each frame is
acknowledged before proceeding.
2. Error Detection and Correction:
o Error detection: Using techniques like checksums, CRC, or parity
bits to detect transmission errors.
o Error correction: ARQ (Automatic Repeat Request) techniques are
used to retransmit frames when errors are detected.
3. Acknowledgments: The receiver sends feedback (ACK for successful
receipt, NAK for errors) to the sender, prompting retransmission when
necessary.

MEDIA ACCESS CONTROL – RANDOM ACCESS:

ALOHA:

CSMA:

CSMA/CD:

Media Access Control (MAC) is a sublayer of the Data Link Layer in the OSI
model that controls how devices on a shared communication medium access and
transmit data. When multiple devices share the same transmission medium, a
method is needed to avoid collisions and ensure that the medium is used
efficiently. Random Access methods are a group of MAC techniques that allow
devices to transmit data whenever they are ready, with the risk of collisions, which
are resolved after they occur.

Key Concepts of Random Access:

 No Prior Coordination: Devices do not coordinate before transmitting; they

transmit when they have data to send.
 Collision Handling: When two or more devices transmit at the same time, a
collision occurs. Random Access protocols provide mechanisms to detect or
prevent collisions and manage retransmissions.
 Efficient for Burst Traffic: These protocols are particularly suitable for
networks with bursty traffic, where communication is sporadic.

SRM University/Dr.SK GUPTA Page 19

 COMPUTER NETWORK

Main Types of Random Access Protocols:

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

1. ALOHA Protocol

ALOHA is one of the simplest and earliest random access protocols, developed for
wireless communication systems like radio transmissions.

Types of ALOHA:

 Pure ALOHA:
o Description: Devices transmit data whenever they have data to send.
If a collision occurs (two devices transmit at the same time), the
sender waits for a random amount of time (backoff) and retransmits
the data.
o Collision Handling: Since devices transmit without listening to the
channel, collisions can occur frequently. Each station must detect
whether its transmission was successful, usually via an
acknowledgment from the receiver.
o Efficiency: The maximum channel utilization is about 18.4% due to
frequent collisions.

Process:

o Sender sends the packet.

o If no acknowledgment is received (due to collision), the sender waits
for a random backoff time and retransmits.
 Slotted ALOHA:
o Description: In Slotted ALOHA, time is divided into slots, and
devices can only transmit at the beginning of a time slot. This reduces
the chances of collisions because collisions can only occur if two
devices attempt to transmit in the same slot.
o Collision Handling: Collisions still happen, but they are less frequent
than in Pure ALOHA.
o Efficiency: The maximum channel utilization increases to 36.8% due
to the slotted structure.

SRM University/Dr.SK GUPTA Page 20

 COMPUTER NETWORK

Process:

o Time is divided into slots.

o Devices wait until the start of the next slot to transmit.
o If a collision occurs, the sender waits for a random backoff time
before retrying.

2. Carrier Sense Multiple Access (CSMA)

In CSMA, devices first listen to the medium to check if it is free (carrier sense)
before attempting to transmit data. This helps reduce the probability of collisions
compared to ALOHA.

Types of CSMA:

 1-persistent CSMA:
o Description: The device continuously listens to the channel. If the
channel is idle, it sends data immediately. If the channel is busy, it
waits until it becomes idle and then transmits.
o Problem: This increases the chances of collisions since multiple
devices may transmit immediately after the channel becomes free.
 Non-persistent CSMA:
o Description: The device checks the channel, and if it is busy, it waits
for a random period before checking again. This reduces the chances
of collisions but increases the delay.
o Collision Handling: This type reduces the likelihood of collisions but
can increase idle times if devices wait too long before checking the
channel again.
 p-persistent CSMA:
o Description: The device listens to the channel, and if it is free, it
transmits with probability p. If the channel is busy or the device does
not transmit, it waits for the next time slot and tries again with the
same probability.
o Collision Handling: Reduces collision risk while maintaining
efficient channel usage. The value of p is chosen to optimize
performance based on network conditions.

SRM University/Dr.SK GUPTA Page 21

 COMPUTER NETWORK

3. CSMA with Collision Detection (CSMA/CD)

CSMA/CD is used in wired networks (e.g., Ethernet) to detect collisions while

transmitting data. It improves on basic CSMA by incorporating mechanisms to
detect collisions and stop transmissions to avoid wasting bandwidth.

How CSMA/CD Works:

 Carrier Sensing: The device listens to the channel before transmitting.

 Collision Detection: While transmitting, the device monitors the channel to
detect collisions. If a collision is detected (e.g., an unexpected voltage
change on the wire), the device immediately stops transmitting.
 Backoff: After detecting a collision, the device waits for a random backoff
time and attempts retransmission.

Collision Detection Process:

1. Device listens to the channel.

2. If the channel is idle, it starts transmitting.
3. While transmitting, the device continues to monitor the channel.
4. If a collision is detected, the transmission is halted, and a jam signal is sent
to inform all other devices about the collision.
5. The device waits for a random backoff time before retrying the transmission.

Application:

 Used in Ethernet (IEEE 802.3) networks.

 Efficient for wired LANs where detecting collisions is relatively easy due to
the nature of the medium.

4. CSMA with Collision Avoidance (CSMA/CA)

CSMA/CA is primarily used in wireless networks (e.g., Wi-Fi) where detecting

collisions is more difficult than in wired networks. Instead of detecting collisions,
CSMA/CA tries to avoid them altogether by taking additional precautions.

How CSMA/CA Works:

 Carrier Sensing: The device listens to the channel. If it is idle, the device
waits for a random backoff period to avoid collisions with other devices that
may have been waiting for the channel.
SRM University/Dr.SK GUPTA Page 22
 COMPUTER NETWORK

 Collision Avoidance: The device may send a short control message (e.g.,
Request to Send or RTS) before transmitting the actual data to alert other
devices to hold off their transmissions.
 Acknowledgments: After successfully receiving the data, the receiver sends
an acknowledgment (ACK) to confirm the successful reception.

Collision Avoidance Process:

1. The device listens to the channel.

2. If the channel is idle, it waits for a random backoff time before attempting
transmission.
3. The device may send an RTS message to reserve the channel.
4. If the RTS is acknowledged by the receiver with a Clear to Send (CTS)
message, the device transmits its data.
5. After receiving the data, the receiver sends an acknowledgment (ACK).
6. If no acknowledgment is received, the sender retransmits the data after a
backoff period.

Application:

 Used in Wi-Fi (IEEE 802.11) and other wireless networks where collisions
are harder to detect due to signal interference and attenuation over long
distances.

Comparison of Random Access Methods:

Protocol Type Collision Handling Efficiency Application

High collision rate, Early radio

Pure Random
retransmit after random ~18% communication
ALOHA Access
time systems

Satellite
Slotted Time- Reduced collision rate,
~36% communication
ALOHA Slotted retransmit in slots
systems

Listen Reduced collision, but Medium Early Ethernet, bus

CSMA
before collisions can still networks

SRM University/Dr.SK GUPTA Page 23

 COMPUTER NETWORK

Protocol Type Collision Handling Efficiency Application

transmit happen

Listen, Collision detection, Ethernet (Wired

CSMA/CD High
detect, stop retransmit after backoff networks)

Avoid Avoids collisions, Wi-Fi, Wireless

CSMA/CA High
collisions acknowledgment used LANs

CONTROLLED ACCESS:

TOKEN PASSING:

POLLING

RESERVATION:

Controlled Access is a set of media access control methods in which devices in a

network coordinate with each other to avoid collisions by ensuring that only one
device transmits at a time. Unlike Random Access protocols (e.g., ALOHA or
CSMA), where devices transmit independently and resolve collisions afterward,
Controlled Access protocols ensure that devices take turns accessing the shared
medium, making them more efficient for heavily loaded networks.

Key Characteristics of Controlled Access:

1. No Collisions: Since only one device can access the medium at a time,
collisions are avoided entirely.
2. Coordination: Devices use a coordination mechanism to determine which
one has the right to transmit.
3. Suitable for High Traffic: These protocols are more efficient when the
network has high traffic or when the shared medium is in constant use.

Main Types of Controlled Access Protocols:

1. Reservation
2. Polling
3. Token Passing
SRM University/Dr.SK GUPTA Page 24
 COMPUTER NETWORK

1. Reservation Protocol

In the Reservation protocol, devices reserve the right to use the medium before
transmitting. This ensures that collisions are avoided by scheduling transmissions
ahead of time.

How Reservation Works:

 The time on the medium is divided into two parts:

o Reservation Period: During this period, devices indicate their
intention to transmit data.
o Transmission Period: In this period, devices that successfully
reserved the medium transmit their data.

Process:

1. Each device sends a small control message during the reservation period,
indicating it wants to transmit.
2. If the reservation is successful, the device gets a slot to transmit its data in
the transmission period.
3. If multiple devices request the same slot, collisions may occur in the
reservation phase, but not in the data transmission phase.
4. Unsuccessful devices can try to reserve a slot in the next reservation period.

Example:

 Used in satellite communication or cellular networks, where devices need

to reserve time slots to communicate over a shared medium.

2. Polling

Polling is a centralized control mechanism where a central controller or "master"

polls devices (called "slaves") to give them permission to transmit. The controller
asks each device in turn whether it has data to send, and only the polled device is
allowed to transmit.

How Polling Works:

 A central controller sends a polling signal to each device one by one.

 Each device responds to the poll:
o If it has data to send, it transmits the data when polled.

SRM University/Dr.SK GUPTA Page 25

 COMPUTER NETWORK

o If it doesn’t have data, it sends a negative response, and the controller

polls the next device.

Process:

1. The controller sends a poll request to Device A.

2. Device A either sends data or responds with a "no data" signal.
3. The controller polls Device B, and the process continues.
4. Once all devices have been polled, the process starts over.

Advantages:

 Centralized control: Ensures fairness, as each device gets an equal

opportunity to transmit.
 No collisions: Since only the polled device transmits, there are no collisions.

Disadvantages:

 Delay: Devices may experience delays as they wait to be polled, especially

in networks with many devices.
 Single Point of Failure: The central controller is critical, and if it fails,
communication halts.

Example:

 Used in legacy networks like mainframe computer systems and point-to-

point communication, where a central controller manages multiple
terminals.
 Bluetooth also uses polling in its master-slave architecture.

3. Token Passing

In the Token Passing protocol, a special control message called a "token" is

passed around the network. Only the device that holds the token is allowed to
transmit. After finishing its transmission, the device passes the token to the next
device in a predetermined order.

How Token Passing Works:

 A token circulates among the devices in the network.

SRM University/Dr.SK GUPTA Page 26

 COMPUTER NETWORK

 A device that has the token can transmit data. If it has no data to send, it
simply passes the token to the next device.
 The token continues circulating, ensuring that every device gets an
opportunity to transmit.

Process:

1. Device A holds the token.

2. If Device A has data, it transmits while holding the token.
3. Once finished, Device A passes the token to Device B.
4. Device B can now transmit if it has data, and the process continues.

Advantages:

 No Collisions: Since only the device with the token can transmit, collisions
are avoided.
 Efficient for Heavy Traffic: Token passing can handle high traffic loads
effectively.

Disadvantages:

 Token Loss: If the token is lost due to an error, the entire network can halt
until the token is recovered or regenerated.
 Delay: Devices must wait their turn to receive the token, which can
introduce delay, especially in large networks.

Example:

 Token Ring Networks (IEEE 802.5) were based on this principle. A logical
ring is formed, and a token circulates around the network.
 FDDI (Fiber Distributed Data Interface) also uses token passing in high-
speed fiber optic networks.

Comparison of Controlled Access Protocols:

Collisio
Coordina Example
n Centralized/Distr Advanta Disadvant
Protocol tion Applicatio
Avoida ibuted ges ages
Method n
nce

SRM University/Dr.SK GUPTA Page 27

 COMPUTER NETWORK

Collisio
Coordina Example
n Centralized/Distr Advanta Disadvant
Protocol tion Applicatio
Avoida ibuted ges ages
Method n
nce

Efficient Collisions
Satellite
Reserva Reservati use of can occur
Yes Distributed communic
tion on period the in
ation
medium reservation

Fair
Delay,
Central access, Mainframe
single
Polling controller Yes Centralized no systems,
point of
polls collision Bluetooth
failure
s

No
collision
s,
Token Token Token loss
Yes Distributed efficient
Passing circulates can disrupt
for
heavy
loads

CHANNELIZATION:

TDMA:

FDMA:
SRM University/Dr.SK GUPTA Page 28
 COMPUTER NETWORK

CDMA:

Channelization is a technique used in multiple access protocols to allow multiple

users to share a common communication medium (like a wireless frequency
spectrum or a wired network) by dividing the available bandwidth into separate,
non-overlapping channels. Each user or device is allocated a specific channel,
reducing interference and allowing simultaneous communication without
collisions.

Channelization techniques are widely used in both wired and wireless networks,
including cellular networks, satellite communications, and cable systems. These
techniques fall under controlled access methods, as they ensure that users don't
interfere with each other's transmissions.

Key Channelization Techniques:

1. Frequency Division Multiple Access (FDMA)

2. Time Division Multiple Access (TDMA)
3. Code Division Multiple Access (CDMA)

1. Frequency Division Multiple Access (FDMA)

FDMA is a channelization technique where the available bandwidth is divided into

multiple frequency bands or channels, and each user is assigned a unique
frequency band for communication.

How FDMA Works:

 The entire frequency spectrum is divided into smaller, non-overlapping

frequency bands.
 Each user is assigned a different frequency band, which they can use for the
duration of the communication.
 Users can transmit and receive data simultaneously, but only within their
assigned frequency range.

Key Features:

 Continuous Transmission: Each user can continuously transmit data

without interruption, as long as they stay within their assigned frequency
band.

SRM University/Dr.SK GUPTA Page 29

 COMPUTER NETWORK

 No Collisions: Since each user has a dedicated frequency band, there are no
collisions between users.
 Guard Bands: To prevent interference between adjacent frequency bands,
guard bands (unused frequencies) are inserted between channels.

Advantages:

 Simple to implement.
 Suitable for analog communication systems.
 No need for complex synchronization between users.

Disadvantages:

 Inefficient use of bandwidth: Guard bands waste part of the available

spectrum.
 Limited flexibility: Once a frequency band is assigned, it cannot be easily
reused.

Example:

 Traditional analog cellular networks and FM radio broadcasting use

FDMA to assign separate frequencies to different users or stations.

2. Time Division Multiple Access (TDMA)

TDMA divides the communication medium into time slots, and each user is
allocated a specific time slot during which they can transmit data. Multiple users
share the same frequency band but take turns transmitting in their assigned time
slots.

How TDMA Works:

 The entire available bandwidth is used by all users, but each user is assigned
a specific time slot.
 Users take turns transmitting their data in a synchronized manner.
 Between time slots, the medium remains idle for each user until their next
time slot.

SRM University/Dr.SK GUPTA Page 30

 COMPUTER NETWORK

Key Features:

 Time-Slot Allocation: Each user is assigned a time slot, and only one user
can transmit during a specific slot.
 Synchronization: The system requires tight synchronization to ensure that
users transmit only in their assigned time slots.
 Time Guard Intervals: To avoid overlap between time slots, guard
intervals may be used to separate them.

Advantages:

 More efficient use of bandwidth compared to FDMA, as multiple users can

share the same frequency.
 No interference between users as long as time slots are managed correctly.
 Flexible and scalable for digital communication systems.

Disadvantages:

 Requires strict synchronization between users.

 Idle periods when users are waiting for their time slot can reduce efficiency.

Example:

 GSM (Global System for Mobile Communications), used in 2G mobile

networks, is a common example of TDMA.
 Digital broadcasting systems also often employ TDMA.

3. Code Division Multiple Access (CDMA)

CDMA is a more complex channelization technique where all users share the same
frequency band and time period, but each user is assigned a unique code. These
codes are used to encode and decode data, allowing multiple users to transmit
simultaneously without interfering with each other.

How CDMA Works:

 Each user's data is spread across the entire frequency band using a unique
spreading code.
 The receiver uses the same spreading code to decode the signal and retrieve
the original data.

SRM University/Dr.SK GUPTA Page 31

 COMPUTER NETWORK

 Since each user's data is encoded differently, the signals can overlap, but
they remain distinguishable by their codes.

Key Features:

 Spread Spectrum: CDMA uses a technique called spread spectrum to

spread each user's signal across a wide frequency band.
 Orthogonal Codes: The spreading codes are orthogonal (i.e., they don't
interfere with each other), ensuring that signals remain distinct even when
overlapping.
 Simultaneous Access: Multiple users can transmit at the same time and on
the same frequency without causing interference.

Advantages:

 Highly efficient use of the available bandwidth.

 No strict time synchronization is required, unlike TDMA.
 Can support more users than FDMA and TDMA, as signals are spread over
the entire spectrum.
 Resistant to interference and eavesdropping due to the use of unique codes.

Disadvantages:

 Complex to implement and manage, requiring sophisticated signal

processing.
 Users must have the correct code to decode the transmitted data, which adds
complexity to the network design.

Example:

 3G mobile networks (e.g., CDMA2000 and WCDMA) use CDMA to allow

multiple users to share the same frequency band.
 GPS (Global Positioning System) also uses CDMA to allow multiple
satellites to transmit signals on the same frequency band.

Comparison of Channelization Techniques:

SRM University/Dr.SK GUPTA Page 32

 COMPUTER NETWORK

Frequency Division Time Division Code Division

Technique Multiple Access Multiple Access Multiple Access
(FDMA) (TDMA) (CDMA)

All users share the

Medium Divides spectrum Divides spectrum
same spectrum with
Sharing into frequency bands into time slots
unique codes

No collisions No collisions
Collision No collisions
(dedicated (dedicated time
Avoidance (distinct codes)
frequencies) slots)

Moderate efficiency High efficiency (all

Lower efficiency
Efficiency (idle time between users transmit
due to guard bands
slots) simultaneously)

Strict time Minimal

No synchronization
Synchronization synchronization synchronization
needed
required needed

Analog cellular 3G networks, GPS,

GSM (2G), digital
Example networks, radio modern cellular
broadcasting
broadcasting systems

ETHERNET STANDARD:

Ethernet is a family of networking technologies and standards used for local area
networks (LANs) and metropolitan area networks (MANs). Developed in the
1970s by Xerox and later standardized by the IEEE 802.3 working group, Ethernet
has evolved over the years, with multiple standards addressing different speeds,
media types, and topologies. Ethernet supports data link layer protocols and uses
both wired and optical fiber as transmission media.

SRM University/Dr.SK GUPTA Page 33

 COMPUTER NETWORK

Key Features of Ethernet:

 Frame-based Data Transmission: Ethernet networks transmit data in units

called frames.
 MAC Addressing: Devices are identified using Media Access Control
(MAC) addresses, which are unique to each device on the network.
 Collision Detection and Avoidance: Ethernet originally used CSMA/CD
(Carrier Sense Multiple Access with Collision Detection) to manage
access to the shared medium, although this is no longer relevant in modern
full-duplex Ethernet.
 Scalability: Ethernet can scale from small local networks to large enterprise
systems.

Ethernet Standards and Speeds:

Maximum
Standard Speed Medium Notes
Distance
10 Twisted-pair Early Ethernet standard,
10BASE-T 100 meters
Mbps copper now largely obsolete.
100 Twisted-pair Also known as Fast
100BASE-TX 100 meters
Mbps copper Ethernet.
Twisted-pair Commonly known as
1000BASE-T 1 Gbps 100 meters
copper Gigabit Ethernet.
10 Twisted-pair 55 to 100 10 Gigabit Ethernet over
10GBASE-T
Gbps copper meters twisted-pair copper.
40 Twisted-pair High-speed Ethernet for
40GBASE-T 30 meters
Gbps copper data centers.
High-speed Ethernet used
100 Twisted-pair
100GBASE-T 30 meters primarily in enterprise
Gbps copper
systems.
1000BASE- Multimode
1 Gbps 550 meters Gigabit Ethernet over fiber.
SX fiber
1000BASE- Single-mode 5-10 Long-distance Ethernet over
1 Gbps
LX fiber kilometers fiber.
10 Multimode 10 Gigabit Ethernet over
10GBASE-SR 400 meters
Gbps fiber fiber for shorter distances.
10GBASE- 10 Single-mode 10 kilometers 10 Gigabit Ethernet for

SRM University/Dr.SK GUPTA Page 34

 COMPUTER NETWORK

Maximum
Standard Speed Medium Notes
Distance
LR Gbps fiber long-distance fiber
networks.
40GBASE- 40 Multimode 100-150 40 Gigabit Ethernet over
SR4 Gbps fiber meters fiber, often in data centers.
100 Gigabit Ethernet for
100GBASE- 100 Multimode
100 meters high-speed data center
SR10 Gbps fiber
networks.

Evolution of Ethernet Standards:

1. 10 Mbps Ethernet (10BASE-T):

o The original Ethernet standard defined data rates of 10 Mbps and
used coaxial cables or twisted-pair cables.
o It relied on CSMA/CD for collision detection, which is unnecessary
in modern switched Ethernet networks.
2. Fast Ethernet (100BASE-T):
o Fast Ethernet increased the speed to 100 Mbps and continued to use
twisted-pair cables.
o This standard is backward compatible with 10BASE-T, allowing older
and newer Ethernet equipment to coexist.
3. Gigabit Ethernet (1000BASE-T):
o Gigabit Ethernet supports 1 Gbps data rates and uses twisted-pair or
fiber optic cables.
o Widely used in home, office, and enterprise networks today.
4. 10 Gigabit Ethernet (10GBASE-T):
o 10 Gbps Ethernet has become common in data centers and high-
performance computing environments.
o It supports both twisted-pair copper (10GBASE-T) and fiber optic
media (10GBASE-SR, 10GBASE-LR).
5. 40G and 100G Ethernet:
o 40G Ethernet and 100G Ethernet (e.g., 40GBASE-T, 100GBASE-
SR10) are primarily used in large-scale data centers, server farms, and
high-bandwidth environments.
o These standards use both copper and fiber optic media, with a focus
on maximizing throughput and minimizing latency.

SRM University/Dr.SK GUPTA Page 35

 COMPUTER NETWORK

Ethernet Frame Format:

Ethernet transmits data using frames, which consist of several fields:

1. Preamble: A 7-byte field that synchronizes the receiver's clock with the
incoming data.
2. Start Frame Delimiter (SFD): A 1-byte field indicating the start of the
frame.
3. Destination MAC Address: A 6-byte field containing the MAC address of
the destination device.
4. Source MAC Address: A 6-byte field containing the MAC address of the
source device.
5. EtherType/Length: A 2-byte field indicating the type of the payload (e.g.,
IPv4, ARP) or the length of the payload.
6. Payload: The actual data being transmitted (46–1500 bytes).
7. Frame Check Sequence (FCS): A 4-byte field used for error detection
(CRC).

Full Duplex and Switched Ethernet:

 Full Duplex: Modern Ethernet supports full duplex, meaning devices can
send and receive data simultaneously, eliminating collisions and increasing
throughput.
 Switched Ethernet: In modern networks, Ethernet switches manage data
transmission between devices. Each device is connected to a switch port, and
the switch manages packet forwarding, eliminating the need for CSMA/CD.

SRM University/Dr.SK GUPTA Page 36