UNIT-2

Data Link Layer: Channel Allocation Protocols

1. Random Access Techniques

Definition: Random access techniques allow devices to transmit data whenever they have
information to send, without prior coordination. This method is particularly useful in
environments where traffic is bursty and unpredictable.

A. ALOHA Protocol

 Pure ALOHA:
o Mechanism: Any device can transmit whenever it has data. If two devices
transmit simultaneously, a collision occurs.
o Collision Detection: After sending, the device waits for an acknowledgment.
If none is received, it assumes a collision has occurred.
o Retransmission: The device waits for a random time (using a backoff
algorithm) before attempting to retransmit.
o Efficiency: The maximum throughput is about 18.4% due to collisions.
 Slotted ALOHA:
o Mechanism: Time is divided into discrete slots. Devices can only begin
transmitting at the start of a time slot.
 o Collision Handling: Similar to pure ALOHA, but the chance of collisions is
halved.
o Efficiency: Maximum throughput increases to about 36.8%.

B. Carrier Sense Multiple Access (CSMA)

 Mechanism: Before transmitting, a device listens to the channel to check if it is free.

o CSMA/CD (Collision Detection): Used in wired networks (like Ethernet):
 If a device detects a collision while transmitting, it immediately stops
and sends a jam signal to inform other devices.
 Each device then waits for a random time before retrying.
 Efficiency can be high, but performance drops with many devices.
o CSMA/CA (Collision Avoidance): Used in wireless networks (like Wi-Fi):
 A device sends a Request to Send (RTS) to the receiver. If the receiver
is free, it sends back a Clear to Send (CTS).
 The device then transmits data, reducing the chance of collisions.
 This is crucial in wireless environments where collision detection is
difficult.

Advantages of Random Access Techniques

 Simplicity: Easy to implement without complex coordination mechanisms.

 Flexibility: Good for bursty traffic where devices need to send data at unpredictable
times.

Applications

 Wireless Networks: Such as Wi-Fi, where devices connect sporadically.

 Satellite Communication: Where devices may transmit data intermittently.

2. Controlled Access Techniques

Definition: Controlled access techniques regulate when devices can transmit over a shared
channel, reducing the chance of collisions and ensuring fair access among users.

A. Token Ring

 Mechanism: A token circulates around the network. A device can only transmit data
when it possesses the token.
o Token Passing: The token is a special data packet that grants permission to
send. If a device wants to transmit, it captures the token and sends its data.
o Efficiency: Since only one device transmits at a time, collisions are
eliminated.
B. Polling

 Mechanism: A central controller polls each device in a predetermined order.

o Permission to Transmit: The controller asks each device if it has data to
send. Only the polled device can transmit.
o Efficiency: Reduces the chance of collisions, but may introduce delays,
especially if many devices are waiting.

C. Time Division Multiple Access (TDMA)

 Mechanism: Time is divided into fixed slots, and each user is assigned specific time
slots for transmission.
o Slot Assignment: Users transmit only during their designated time slots,
ensuring no collisions.
o Efficiency: Maximizes bandwidth usage by ensuring all users get an
opportunity to transmit.

Advantages of Controlled Access Techniques

 Reduced Collisions: Coordinated access minimizes the likelihood of data collisions.

 Fairness: Each user has guaranteed access to the channel, which can improve
response times in busy networks.

Applications

 Token Ring Networks: Used in local area networks (LANs) for orderly data
transmission.
 TDMA in Mobile Networks: Employed in second-generation (2G) cellular systems.

3. Channelization Techniques

Definition: Channelization techniques divide the available bandwidth of a communication

channel into smaller, distinct channels to allow multiple users to communicate
simultaneously.

A. Frequency Division Multiple Access (FDMA)

 Mechanism: The total bandwidth is divided into frequency bands, each assigned to
a different user.
o Non-overlapping Channels: Each user transmits on a separate frequency,
minimizing interference.
o Efficiency: Suitable for continuous data streams like voice.
B. Time Division Multiple Access (TDMA)

 Mechanism: Similar to the controlled access method, TDMA divides time into slots
for users.
o Dynamic Slot Assignment: In some implementations, slots can be
dynamically assigned based on demand.
o Applications: Widely used in digital cellular networks, allowing multiple
calls on the same frequency.

C. Code Division Multiple Access (CDMA)

 Mechanism: Each user is assigned a unique code, allowing them to transmit

simultaneously over the same frequency band.
o Spread Spectrum: Users’ signals are spread over a wide frequency range,
which helps to minimize interference.
o Orthogonality: Properly designed codes allow for simultaneous
transmissions without crosstalk, enabling efficient use of bandwidth.

Advantages of Channelization Techniques

 Increased Capacity: Multiple users can share the same channel without
interference, maximizing bandwidth utilization.
 Flexibility: Allows for dynamic allocation of resources based on user demand.

Applications

 FDMA: Used in analog cellular systems and radio broadcasting.

 TDMA: Found in digital cellular networks, satellite communications, and wireless
systems.
 CDMA: Widely used in modern cellular systems, including 3G and some 4G
technologies.

Summary

 Random Access Techniques: Allow uncoordinated access to a shared channel,

relying on collision detection and avoidance methods (e.g., ALOHA, CSMA).
 Controlled Access Techniques: Coordinate access to prevent collisions and ensure
fair use (e.g., Token Ring, Polling, TDMA).
 Channelization Techniques: Divide bandwidth into smaller channels for
simultaneous use by multiple users (e.g., FDMA, TDMA, CDMA).

These techniques are crucial in the design and operation of communication networks,
ensuring efficient, reliable data transmission among users.
PROPAGATION DELAY is a key concept in networking and telecommunications,
referring to the time it takes for a signal to travel from the sender to the receiver across a
medium. This delay is influenced by several factors, including the distance between the two
points, the type of medium used for transmission (like fiber optic, copper cables, or air), and the
speed at which the signal travels.

Key Aspects of Propagation Delay

1. Formula

The propagation delay can be calculated using the formula:

Propagation Delay=DistancePropagation Speed\text{Propagation Delay} =

\frac{\text{Distance}}{\text{Propagation
Speed}}Propagation Delay=Propagation SpeedDistance

 Distance: The physical distance between the sender and receiver.

 Propagation Speed: The speed at which the signal travels through the medium. For
example:
o In fiber optics, signals travel at about two-thirds the speed of light (~200,000
km/s).
o In copper cables, the speed is slower, approximately 2/3 of the speed of light as
well.

2. Factors Affecting Propagation Delay

 Distance: Longer distances increase the propagation delay since the signal has to travel
further.
 Medium: Different transmission media have different propagation speeds. For instance,
light travels faster in a vacuum than in glass.
 Signal Type: The nature of the signal (analog or digital) can also influence the delay,
especially if the signal requires modulation.

3. Significance

 Network Performance: Propagation delay is crucial for understanding the overall

latency in a network. It contributes to the total round-trip time (RTT) in data
communications.
 Real-Time Applications: For applications like VoIP or online gaming, high propagation
delays can lead to noticeable lag, affecting user experience.
 Routing Protocols: Propagation delay can affect the choice of routing paths and the
performance of routing protocols in large networks.

4. Propagation Delay vs. Other Delays

Propagation delay is one component of total transmission delay, which also includes:
  Transmission Delay: The time taken to push all the packet's bits into the wire. It depends
on the packet size and the bandwidth of the channel.
 Queueing Delay: The time a packet spends in routing queues before being transmitted.
 Processing Delay: The time taken by routers to process the packet header and make
forwarding decisions.

Transmission Delay is the time it takes to push all the bits of a packet into the transmission
medium. It is a crucial component of overall network latency and is influenced primarily by the
size of the packet and the bandwidth of the communication channel.

Key Aspects of Transmission Delay

1. Formula

Transmission delay can be calculated using the formula:

Transmission Delay=Packet SizeBandwidth\text{Transmission Delay} = \frac{\text{Packet

Size}}{\text{Bandwidth}}Transmission Delay=BandwidthPacket Size

 Packet Size: The size of the packet being transmitted, usually measured in bits (e.g., a
packet size of 1,500 bytes would be 12,000 bits).
 Bandwidth: The capacity of the communication channel, typically measured in bits per
second (bps).

2. Example Calculation

For instance, if you have a packet size of 1,500 bytes (12,000 bits) and a bandwidth of 1 Mbps
(1,000,000 bps), the transmission delay would be:

Transmission Delay=12,000 bits1,000,000 bps=0.012 seconds=12 milliseconds\text{Transmissio

n Delay} = \frac{12,000 \text{ bits}}{1,000,000 \text{ bps}} = 0.012 \text{ seconds} = 12 \text{
milliseconds}Transmission Delay=1,000,000 bps12,000 bits=0.012 seconds=12 milliseconds

3. Factors Affecting Transmission Delay

 Packet Size: Larger packets take longer to transmit. For example, a 10,000-bit packet
will take longer to send than a 1,500-bit packet.
 Bandwidth: Higher bandwidth allows for faster transmission of data. For instance, a 10
Mbps connection will transmit data faster than a 1 Mbps connection.
 Protocol Overhead: Additional bits for headers and trailers (used for error checking,
addressing, etc.) can slightly increase the effective packet size.

4. Significance

 Network Performance: Transmission delay is a critical component of the overall latency

in a network, affecting how quickly data is transmitted and received.
  Impact on Applications: Applications that require real-time communication (like video
conferencing or online gaming) are sensitive to transmission delays, as they can impact
user experience.
 Routing and Switching: In routers and switches, the transmission delay is a factor in
determining how quickly data can be forwarded through the network.

Transmission Delay vs. Other Delays

Transmission delay is one part of the total delay experienced in a network, which also includes:

 Propagation Delay: The time it takes for the signal to travel from the sender to the
receiver.
 Queueing Delay: The time packets spend waiting in queues at routers or switches before
they can be transmitted.
 Processing Delay: The time taken by routers to process the packet header and make
forwarding decisions.

ALOHA is a pioneering random access protocol used for managing access to a shared
communication medium. Developed at the University of Hawaii for wireless packet networks, it
allows multiple users to transmit data over the same channel without prior coordination. ALOHA
can be categorized into two main types: Pure ALOHA and Slotted ALOHA.

1) Pure ALOHA is one of the earliest random access protocols designed for
communication over a shared medium. It allows multiple devices to transmit data without
coordination, making it particularly suitable for environments where data transmission is
sporadic and unpredictable.

2)
Key Features of Pure ALOHA

1. Mechanism of Operation

 Transmission: Any device can transmit data whenever it has data to send. There are no
restrictions on when a device can start transmitting.
 Collision Handling: If two devices transmit simultaneously, a collision occurs, resulting
in both transmissions being lost.
 Retransmission: After detecting a collision (usually through the absence of an
acknowledgment), each device waits for a random time before attempting to retransmit.
This random backoff helps reduce the chance of repeated collisions.

2. Throughput and Efficiency

 Maximum Throughput: The theoretical maximum throughput of Pure ALOHA is about

18.4%. This means that, on average, only 18.4% of the time can be utilized for successful
transmissions. The rest is consumed by collisions and retransmissions.
 Throughput Formula: The throughput SSS can be expressed as:

S=G×e−2GS = G \times e^{-2G}S=G×e−2G

where GGG is the average number of frames generated by the system in a given time
interval.

3. Advantages

 Simplicity: The protocol is easy to implement and requires minimal coordination

between devices. There’s no need for complex algorithms or scheduling.
 Flexibility: It works well in environments where data is sent sporadically, making it
suitable for various applications, including satellite communications and wireless
networks.

4. Disadvantages

 High Collision Rate: As the number of users increases, the likelihood of collisions also
increases, leading to inefficiencies and wasted bandwidth.
 Low Efficiency: With a maximum throughput of only 18.4%, Pure ALOHA is not
efficient for networks with high traffic.

5. Applications

 Wireless Communication: Used in early wireless networks and satellite communication

systems, where devices need to transmit data intermittently.
 Simple Networks: Suitable for small networks with limited traffic, where simplicity and
low overhead are more critical than efficiency.
Conclusion

Pure ALOHA is a foundational protocol in the history of networking, showcasing the concept of
random access in data transmission. While it has its limitations in efficiency and scalability, its
simplicity and ease of use have made it relevant in certain applications.

2)Slotted ALOHA is an enhancement of the original Pure ALOHA

protocol designed to improve efficiency in managing access to a shared communication
medium. By introducing time slots, Slotted ALOHA minimizes the chances of collisions
between simultaneous transmissions.

Key Features of Slotted ALOHA

1. Mechanism of Operation

 Time Division: Time is divided into discrete intervals called time slots. Each device can
only begin transmitting at the start of a time slot, which creates a more structured
environment for data transmission.
 Transmission: A device waits until the start of the next time slot to transmit data. This
coordination reduces the likelihood of collisions since devices are less likely to transmit
simultaneously.
  Collision Handling: If two devices transmit at the same time (within the same slot), a
collision occurs. Both transmissions are lost, and the devices must attempt to retransmit
after waiting for a random backoff time.
 Retransmission: After a collision, devices wait for a random time period before retrying,
helping to minimize repeated collisions.

2. Throughput and Efficiency

 Maximum Throughput: The theoretical maximum throughput of Slotted ALOHA is

about 36.8%. This means that approximately 36.8% of the time can be utilized for
successful transmissions.
 Throughput Formula: The throughput SSS can be expressed as:

S=G×e−GS = G \times e^{-G}S=G×e−G

where GGG is the average number of frames generated by the system in a given time
interval.

3. Advantages

 Reduced Collision Rate: By using time slots, Slotted ALOHA decreases the chances of
simultaneous transmissions, resulting in fewer collisions compared to Pure ALOHA.
 Higher Efficiency: The maximum throughput is significantly improved over Pure
ALOHA, making it more suitable for networks with moderate traffic.
 Simplicity: While more structured than Pure ALOHA, it still retains a level of simplicity
in implementation.

4. Disadvantages

 Time Synchronization: Devices must be synchronized to start transmitting at the

beginning of time slots. This synchronization can introduce complexity, particularly in
larger networks.
 Wasted Time Slots: If a device has no data to send at the start of a time slot, the slot is
wasted. This can occur in environments with low traffic.

5. Applications

 Wireless Networks: Slotted ALOHA is used in various wireless communication

systems, including satellite networks and some early cellular systems.
 Network Protocols: It serves as a foundation for more complex protocols and is often
studied in academic contexts as a basic model for understanding random access methods.
Comparison with Pure ALOHA

Feature Pure ALOHA Slotted ALOHA

Time Structure Continuous Divided into time slots
Collision Handling Anytime Only at the start of a slot
Max Throughput 18.4% 36.8%
Synchronization No Yes
Efficiency Lower Higher

Slotted ALOHA improves upon the original Pure ALOHA protocol by organizing time into
discrete slots, reducing the likelihood of collisions and enhancing throughput. While it introduces
the need for synchronization, its advantages make it suitable for various applications in wireless
communication. Understanding Slotted ALOHA is essential for grasping the evolution of more
sophisticated access control protocols that build on its principles.

Carrier Sense Multiple Access (CSMA) is a network protocol

that helps manage how multiple devices share a communication channel. It is commonly
used in wired and wireless networks to reduce the chances of collisions when multiple
devices attempt to transmit data simultaneously. CSMA includes several variations, with
the most notable being CSMA/CD (Collision Detection) and CSMA/CA (Collision
Avoidance).
Key Features of CSMA

1. Basic Mechanism

 Carrier Sensing: Before transmitting, a device listens to the channel (the "carrier") to
determine if it is free. If the channel is clear, the device proceeds to transmit.
 Transmission: If the channel is busy (i.e., another device is transmitting), the device
waits until the channel is free before sending its data.
 Collision Handling: If two devices transmit simultaneously despite sensing the channel,
a collision occurs. How collisions are handled depends on the CSMA variant.

1) Carrier Sense Multiple Access with Collision Detection (CSMA/CD) is a network

protocol used primarily in wired Ethernet networks. It allows multiple devices to share a
single communication channel while minimizing collisions, ensuring efficient data
transmission.
Key Features of CSMA/CD

1. Basic Mechanism

 Carrier Sensing: Before transmitting, a device listens to the network (the "carrier") to
check if the channel is free.
 o If the channel is busy (another device is transmitting), the device waits until it is
clear.
o If the channel is clear, the device can proceed to transmit its data.

2. Collision Detection

 Listening While Transmitting: Unlike protocols that only listen before sending,
CSMA/CD devices continue to monitor the channel while they transmit.
o This allows them to detect collisions immediately if another device attempts to
transmit at the same time.

3. Collision Handling

 Collision Occurs: If a collision is detected during transmission:

o Immediate Stop: The transmitting devices immediately stop sending their data.
o Jam Signal: They transmit a jam signal to notify all other devices on the network
that a collision has occurred. This helps to ensure that all devices are aware of the
collision and refrain from transmitting.
 Backoff Algorithm: After sending the jam signal:
o Each device waits for a random amount of time before attempting to retransmit.
o The wait time is typically calculated using an exponential backoff algorithm. This
means that after each collision, the wait time increases exponentially, reducing the
chances of repeated collisions.

4. Efficiency and Throughput

 Throughput: The maximum theoretical throughput of CSMA/CD is about 50% in

practical scenarios, although it can vary based on network traffic and conditions. The
more devices trying to communicate simultaneously, the more collisions occur, reducing
overall efficiency.
 Efficiency Factors:
o Number of Devices: As the number of devices on the network increases, the
likelihood of collisions increases, which can reduce throughput.
o Traffic Load: High traffic can lead to more collisions, while low traffic can result
in more efficient use of the channel.

5. Advantages of CSMA/CD

 Collision Detection: By detecting collisions in real-time, CSMA/CD can quickly clear

the channel for retransmission, minimizing wasted bandwidth.
 Fairness: All devices have an equal opportunity to transmit since they listen before
sending.
 Simplicity: The protocol is relatively simple to implement, especially for wired
networks.

6. Disadvantages of CSMA/CD
  Collision Overhead: In high-traffic environments, the overhead of handling collisions
can significantly impact performance.
 Limited to Wired Networks: CSMA/CD is primarily effective in wired networks where
collision detection is feasible. In wireless networks, detecting collisions is much more
challenging due to the nature of radio transmission.
 Latency: Increased wait times after collisions can introduce delays in transmission,
particularly under heavy network load.

7. Applications of CSMA/CD

 Ethernet Networks: CSMA/CD was widely used in traditional Ethernet networks,

particularly those using coaxial cables and early twisted-pair technologies.
 Legacy Systems: Although modern Ethernet standards (like switched Ethernet) have
largely replaced CSMA/CD with full-duplex communication (which eliminates
collisions), understanding CSMA/CD remains important for historical context and legacy
systems.

CSMA/CD is a fundamental protocol in the evolution of networking, providing a means for

multiple devices to share a common communication channel efficiently. While it has been
largely supplanted by full-duplex systems in modern networks, its principles remain relevant for
understanding network access methods and collision management.

2) Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) is a network

protocol primarily used in wireless communication, particularly in Wi-Fi networks.
Unlike CSMA/CD, which detects collisions after they occur, CSMA/CA takes proactive
measures to avoid collisions before they happen.
Key Features of CSMA/CA

1. Basic Mechanism

 Carrier Sensing: Just like in CSMA/CD, devices listen to the channel before
transmitting. If the channel is busy (another device is transmitting), they wait until it is
free.
 Collision Avoidance: To reduce the likelihood of collisions:
o Devices use a mechanism called Request to Send (RTS) and Clear to Send
(CTS).

2. RTS/CTS Mechanism

 Request to Send (RTS): Before transmitting data, a device sends an RTS frame to the
intended receiver, indicating its intention to send data and the duration of the
transmission.
  Clear to Send (CTS): If the receiver is free and can accommodate the incoming data, it
responds with a CTS frame. This signal informs both the sender and other devices in the
network to refrain from transmitting for the specified duration, thereby reserving the
channel.
 Data Transmission: After receiving the CTS, the sender transmits the actual data. Other
devices wait until the transmission is complete.

3. Acknowledgment (ACK)

 After the data is successfully received, the receiver sends an ACK frame back to the
sender to confirm successful reception.
 If the sender does not receive an ACK (indicating that the transmission might have
failed), it will initiate a retransmission after a random backoff period.

4. Efficiency and Throughput

 Throughput: CSMA/CA can achieve higher throughput than CSMA/CD in wireless

environments, especially when the network traffic is low to moderate.
 Efficiency Factors:
o Number of Devices: In a wireless environment, CSMA/CA can significantly
reduce collisions compared to protocols without collision avoidance.
o Traffic Patterns: The RTS/CTS mechanism helps maintain efficiency even with
varying traffic loads, but can introduce overhead for very small data packets.

5. Advantages of CSMA/CA

 Collision Prevention: By reserving the channel before transmission, CSMA/CA

effectively reduces the likelihood of collisions, making it more suitable for wireless
environments where collision detection is difficult.
 Fairness: All devices get a fair chance to transmit data, as the RTS/CTS mechanism
allows for orderly access to the channel.
 Adaptability: CSMA/CA can adapt to varying network loads, ensuring efficient use of
the channel.

6. Disadvantages of CSMA/CA

 Overhead: The RTS/CTS exchange introduces additional overhead, which can be

inefficient for small data packets. For small transmissions, the time spent sending RTS
and CTS frames may exceed the time spent transmitting the actual data.
 Hidden Node Problem: Devices that are out of range of each other but within range of
the receiver can cause collisions, as they cannot sense each other’s transmissions.
 Exposed Node Problem: A device that is prevented from sending because it senses a
transmission may not actually interfere with the communication, leading to
underutilization of the channel.

7. Applications of CSMA/CA
  Wi-Fi Networks: CSMA/CA is the fundamental protocol used in IEEE 802.11 (Wi-Fi)
networks, facilitating wireless communication in homes, offices, and public places.
 Wireless Sensor Networks: It is also applicable in various wireless sensor networks
where devices need to communicate without collisions.

8. Comparison with Other Protocols

Feature CSMA/CA CSMA/CD ALOHA

Collision Detects and recovers from
Avoids collisions No collision detection
Handling collisions
Medium Type Wireless (Wi-Fi) Wired (Ethernet) Any
18.4% (Pure), 36.8%
Efficiency Higher in wireless About 50% (in practice)
(Slotted)
RTS/CTS
Mechanism Listen while transmitting Anytime transmission
handshake

CSMA/CA is a critical protocol for managing access in wireless networks, providing a robust
method for collision avoidance that is particularly effective in environments where multiple
devices are contending for the same communication medium. Its mechanisms help maintain
efficient and fair data transmission, making it an essential component of modern wireless
communication technologies.