Computer Networks - Unit 3

MAC (Medium Access Control) Sub-layer

The MAC sub-layer is a part of the Data Link Layer in the OSI model. It is responsible
for controlling how devices access the shared communication medium (like a cable or
wireless channel).

It is also called as Media Access Control Sub-layer.

Key Functions:
1. Channel Access Control – Decides which device can use the medium at a given
time.
2. Frame Delimiting – Marks the beginning and end of data frames.
3. Error Checking – Adds CRC (Cyclic Redundancy Check) to detect transmission
errors.
4. Addressing – Uses MAC addresses to identify devices on a network.

Example:

In Wi-Fi or Ethernet, the MAC sub-layer ensures that only one device sends data at a
time to avoid collisions.

In short: The MAC sub-layer manages how data is placed on and taken from the network
medium, ensuring smooth and error-checked communication between devices.

MAC Addressing
A MAC (Media Access Control) address is a unique physical address assigned to every
device’s network interface card (NIC).

Key Points:
It is a 48-bit address (usually written as 12 hexadecimal digits, e.g.,
00:1A:2B:3C:4D:5E ).
Assigned by the manufacturer, and it is permanent (cannot be changed easily).
Used in local network communication (like in LANs) to identify devices.

Example:
When a router sends data to your laptop, it uses your laptop’s MAC address to make
sure the data goes to the right device.

In short:
A MAC address is a device’s unique hardware ID used to identify it on a local network.

Advantages:
1. Uniqueness – Every device has a unique MAC address, reducing address conflicts.
2. Hardware-based – No need for user configuration; it's built into the device.
3. Fast communication – Used in LANs for quick and direct device-to-device
communication.
4. Security filtering – Routers can use MAC filtering to allow/block specific
devices.

Disadvantages:
1. Fixed address – Hard to change if needed (not flexible like IP addresses).
 2. Privacy issues – MAC addresses can be tracked to monitor device activity.
3. Limited to LAN – Not useful for communication over the internet.
4. MAC spoofing – Hackers can change (spoof) their MAC address to bypass security.

Binary Exponential Back-off (BEB) Algorithm – Short and Simple

Explanation
Binary Exponential Back-off (BEB) is an algorithm used in networking to manage
collisions when multiple devices try to send data at the same time over a shared
medium.

Where it is used:
Used in CSMA/CD (Carrier Sense Multiple Access with Collision Detection), such
as in Ethernet networks.

How it works:
1. When a collision is detected, the device waits before retransmitting.
2. The wait time is randomly chosen between 0 and 2^k - 1 slots.
k is the number of collisions (increases with each collision, up to a
limit).
3. After waiting, the device tries to send again.
4. If another collision occurs, the back-off time doubles (exponential growth).

Example:
1st collision → wait between 0 to 1 slots
2nd collision → wait between 0 to 3 slots
3rd collision → wait between 0 to 7 slots, and so on.

Why it's useful:

It helps to reduce network congestion by spacing out retransmissions after
collisions.

Multiple Access Protocols (MAPs)

Definition:
Multiple Access Protocols are rules or methods that determine how multiple devices
share the same communication medium efficiently and fairly without interfering with
each other.

Types of Multiple Access Protocols

Type Key Idea Examples

Devices transmit at random, ALOHA, Slotted ALOHA,

Random Access
handle collisions CSMA, CSMA/CD, CSMA/CA

Devices take turns or are

Controlled Access Polling, Token Passing
scheduled

Channelization Divide the channel among users by

TDMA, FDMA, CDMA
Protocols time, frequency, or code

##### 1. Random
Access Protocols
 No central control
Devices transmit when ready
Handle collisions via retry
Best for light traffic

2. Controlled Access Protocols

Central controller or coordination
Devices transmit in order
Avoid collisions
Best for predictable traffic
3. Channelization Protocols
Divide bandwidth into logical channels
Each device gets its own slot/code
No collisions
Best for real-time or continuous traffic

Random Distributed Access Schemes / Protocols

Random Distributed Access Schemes are a category of Media Access Control (MAC)
protocols used in networks where multiple devices share a communication medium without
centralized coordination. These schemes allow devices to transmit data at random
times, and resolve conflicts (collisions) when more than one device transmits
simultaneously.

Where Are They Used?

Common in wireless networks (e.g., Wi-Fi)
Also used in Ethernet (legacy) systems
Suitable for networks with variable and unpredictable traffic

Key Characteristics
Decentralized: No central controller determines who transmits when.
Collision-prone: Devices may transmit at the same time, causing collisions.
Collision resolution: Protocols include mechanisms to detect or avoid
collisions.
Major Random Access Schemes

Collision
Protocol Key Idea
Handling

Transmit whenever data is ready;

ALOHA After collision retransmit after random time if collision
occurs

After collision,
Divide time into slots; transmit at
Slotted ALOHA synchronized
beginning of slots
slots

CSMA (Carrier
Try to avoid
Sense Multiple Sense the channel before transmitting
collision
Access)

CSMA/CD (with
Detect collision Used in Ethernet; stop on collision and
Collision
while sending back off
Detection)

CSMA/CA (with
Avoid before Used in Wi-Fi; avoid collisions with
Collision
sending RTS/CTS signals
Avoidance)

Example: CSMA/CD (Ethernet)

1. Device senses if the channel is idle.
2. If idle, it transmits data.
3. If another device transmits at the same time, a collision occurs.
4. Devices detect the collision, stop, and wait a random time before trying again.

Example: CSMA/CA (Wi-Fi)

1. Device listens to channel.
2. If free, it sends a Request to Send (RTS).
3. Receiver replies with Clear to Send (CTS).
4. Sender transmits data.
5. This helps avoid collisions, especially in wireless where collision detection
is hard.

Advantages of Random Access Protocols

1. Simple to implement – Easy design with minimal rules.
2. Efficient under light traffic – Fewer collisions mean faster transmission.
3. No central control needed – Devices operate independently.
4. Cost-effective – No need for expensive coordination hardware.
5. Scalable – Supports many devices without major changes.

Disadvantages of Random Access Protocols

1. Collisions can occur – Multiple devices may transmit at the same time.
2. Wasted bandwidth – Collisions lead to retransmissions.
3. Unpredictable delays – No guarantee of when a device can send data.
4. Low efficiency under heavy load – Collisions increase significantly.
5. No prioritization – All devices have equal chance; no traffic class control.

Pure ALOHA
Pure ALOHA is one of the earliest Random Access Protocols designed for sharing a
communication channel without coordination. It was developed at the University of
Hawaii in the 1970s for wireless radio communication.

How Pure ALOHA Works

1. A device transmits data whenever it has data to send.
2. It does not check if the channel is free or busy.
3. After transmission, the device waits for an acknowledgment (ACK).
4. If ACK is received → transmission is successful.
5. If no ACK (collision occurred) → it waits a random time and retransmits.

Vulnerable Time
Collision can occur if any other device transmits within vulnerable time (2 ×
T), where T = time to send one frame.

This large "vulnerable period" causes high chances of collision.

Efficiency

$S=G e^(−2G)$

Where:

S = throughput (successful transmissions per slot)

G = average number of transmission attempts per slot

Maximum channel utilization: Only ~18.4%

Meaning: On average, only 18.4% of time is used for successful transmission.

Advantages
Very simple to implement
Good for low-traffic networks

Disadvantages
High collision rate
Poor efficiency (~18%)
Not suitable for high-traffic environments

Slotted ALOHA
Slotted ALOHA is an improvement over Pure ALOHA that reduces collisions and increases
efficiency by dividing time into slots.

How Slotted ALOHA Works

1. Time is divided into equal slots corresponding to one frame transmission time.
2. A device can only transmit at the beginning of a time slot.
3. If two devices transmit in the same slot, a collision occurs.
4. If only one device transmits in a slot, transmission is successful.
5. If collision occurs, the device waits a random number of slots before trying
again.

Vulnerable Time
 Vulnerable time = 1 frame time (vs. 2 in Pure ALOHA)
This cuts the chance of collision in half

Efficiency

$S=G e^(−G)$

Where:

S = throughput (successful transmissions per slot)

G = average number of transmission attempts per slot

Maximum channel utilization: Only ~18.4%

Meaning: On average, only 18.4% of time is used for successful transmission.

Advantages
1. Higher efficiency than Pure ALOHA (~36.8%)
2. Fewer collisions
3. Still decentralized

Disadvantages
1. Time synchronization is required (to align slots)
2. Idle slots waste bandwidth if no one transmits

Comparison Table

Feature Pure ALOHA Slotted ALOHA

Transmission Time Any time Only at slot start

Vulnerable Time 2 × frame time 1 × frame time

Max Efficiency ~18.4% ~36.8%

Synchronization Not needed Required

Carrier Sense Multiple Access (CSMA)

CSMA is a Random Access Protocol that helps reduce collisions in a shared
communication medium by making devices “listen” to the channel before transmitting.

It is used in Ethernet (CSMA/CD), Wi-Fi Networks (CSMA/CA) etc.

How CSMA Works

1. A device with data to send first listens to (senses) the channel.
2. If the channel is idle, it transmits the data.
3. If the channel is busy, it waits until the channel becomes idle.
4. Still, two devices may sense the channel as idle and transmit at the same time
→ collision.

“Carrier Sense” Concept

Devices can sense whether another device is currently transmitting by detecting
the carrier signal.
But it cannot always prevent collisions, especially due to propagation delay.
Types of CSMA

Type Behavior

1. 1- If channel is idle → transmit immediately. If busy → keep checking

persistent and transmit as soon as it’s free. (High collision chance)

2. Non- If channel is busy → wait a random time before sensing again.

persistent (Lower collision, longer delay)

3. p-
For slotted channels. If idle → transmit with probability p, else
persistent
wait for next slot. (Balance between delay and collisions)
(slotted)

Advantages
1. More efficient than ALOHA (fewer collisions)
2. Simple to implement
3. Good for moderate traffic

Disadvantages
1. Still has collisions
2. Cannot detect collision immediately (unless used with CSMA/CD)
3. Wasted time in sensing

CSMA/CD (Carrier Sense Multiple Access with Collision Detection)

CSMA/CD is a network protocol that improves CSMA by detecting collisions during
transmission and taking action to resolve them. It is used primarily in wired Ethernet
networks (especially older versions like 10Base-T).

How CSMA/CD Works – Step by Step

1. Carrier Sense (CS):

Device listens to the channel before sending data.

2. Multiple Access (MA):

Multiple devices can access the same medium.

3. Transmit Data:
If the channel is idle, the device starts transmitting.

4. Collision Detection (CD):

While transmitting, the device monitors the channel to detect if another
transmission is occurring.

5. Collision Handling:

If a collision is detected, the device:

Stops transmitting
Sends a jam signal to notify others
Waits a random time (using Binary Exponential Backoff)
Tries again later

Binary Exponential Backoff Algorithm

After a collision:
 Wait for a random time before retransmission.
The wait time increases exponentially after each collision.

Advantages
1. Reduces wasted bandwidth by detecting collisions quickly.
2. More efficient than ALOHA and plain CSMA in wired networks.
3. Simple and effective for small to medium traffic loads.

Disadvantages
1. Only works in wired networks (can't detect collisions in wireless).
2. Performance drops as traffic increases (many collisions).
3. Not used in modern Ethernet (switched networks don’t need it).

CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)

CSMA/CA is a collision avoidance protocol used mainly in wireless networks (e.g., Wi-
Fi) where collision detection is not possible. It tries to avoid collisions before
they happen.

Why Not CSMA/CD in Wireless?

In wireless, a device cannot listen while it transmits, so it cannot detect collisions
like in wired networks → that’s why CSMA/CA is used instead.

How CSMA/CA Works – Steps

1. Sense the channel:

If the channel is idle, wait for a small time (Interframe Space, IFS).
Then start a backoff timer.

2. Random Backoff:

If the channel remains idle, count down the backoff timer.

If the channel becomes busy, pause the timer until it's idle again.

3. Transmit the frame once the backoff timer reaches zero.

4. Optional (but common):

Use RTS/CTS (Request to Send / Clear to Send) mechanism to reserve the channel
before data is sent.

RTS/CTS Mechanism
Sender sends RTS → Receiver replies with CTS
All other devices wait until transmission finishes
Helps prevent hidden terminal problem

Advantages
1. Avoids collisions in wireless networks
2. Supports RTS/CTS to handle hidden terminals
3. More efficient in busy wireless environments

Disadvantages
1. Overhead due to waiting times and RTS/CTS
2. Lower throughput than CSMA/CD
3. Complex implementation
Collision Free Protocols
Collision-Free Protocols are ways to manage how devices share a communication channel
(like Wi-Fi or Ethernet) so that data packets do not collide (overlap and get
corrupted).

In simpler terms:

Imagine several people trying to talk over a walkie-talkie. If they all talk at
once, no one is understood (collision).

A collision-free protocol makes sure only one person speaks at a time — using
rules to avoid two people speaking simultaneously.

Some common methods:

1. Time Division (TDMA)

Everyone gets their own time slot to talk.

2. Token Passing
A "token" is passed around; only the one holding the token can speak.

3. Polling
A central controller asks each person one by one if they want to speak.

Key idea:
These protocols prevent collisions, unlike others (like CSMA/CD) that detect and fix
them after they happen.

Advantages:

1. No Collisions
Data is transmitted without interference, ensuring reliability.

2. High Efficiency at High Load

Works very well when many devices want to communicate, since there are no
wasted transmissions.

3. Predictable Performance
Devices know when they can send data, which helps in systems needing guaranteed
timing (real-time systems).

4. Good for Deterministic Networks

Ideal where timing and order of messages are important (industrial networks,
critical systems).

Disadvantages:

1. Complex Coordination
Requires extra mechanisms (token passing, time slot management), adding
complexity.

2. Overhead
Time and bandwidth are spent managing tokens or time slots, reducing overall
capacity in light traffic.
 3. Less Flexible
Not as dynamic — adding/removing devices can be harder.

4. Idle Time
If a device has nothing to send in its turn, the slot may be wasted.

Basic Bit Map Protocol

Basic Bit Map Protocol is a simple collision-free protocol used to manage how devices
share a communication channel.

Simple Idea:

There are N devices on the network.

A bit map of N bits is used.

Each bit in the map corresponds to one device.

The bit map is broadcast by a central controller or managed collectively.

The protocol works in rounds:

1. Each device checks its bit in the bit map.

2. If a device wants to send data, it sets its bit to 1.
3. If not, it leaves it 0.
4. Devices then take turns sending data in the order of bits: device 1,
device 2, etc.
5. Only devices whose bit was set to 1 will transmit in that round.

Example:
4 devices → Bit map: 1010
Device 1 and Device 3 want to send.
Transmission order:
Device 1 sends.
Device 2 skips.
Device 3 sends.
Device 4 skips.

Advantages:
No Collisions → Only one device sends at a time.
Simple → Easy to implement.

Disadvantages:
Not Efficient at Low Traffic → Still cycles through the full map even if most
devices have nothing to send.
Overhead → Bit map exchange takes time.
Fixed Order → Devices must wait for their turn.

BRAP
BRAP stands for Binary Countdown Reservation Access Protocol. It is a collision-free
protocol used to let multiple devices decide who gets to transmit data — in a way that
prevents collisions.
Simple Idea:

Each device that wants to send data picks a unique binary number (priority
number).

All devices then broadcast their number bit by bit, starting from the most
significant bit.

At each step, if a device sees a higher-priority bit (1) while its own bit is
0, it drops out — meaning it loses this round.

Finally, only one device remains — the one with the highest binary number — and
it transmits.

The process repeats for the next transmission.

Example:

Let’s say we have 3 devices with these numbers:

Device Binary Number (Priority)

A 101

B 011

C 100

Step-by-step:

First bit: Devices A and C transmit 1 , B transmits 0 . → B drops out.

Second bit: A transmits 0 , C transmits 0 . → both stay.
Third bit: A transmits 1 , C transmits 0 . → C drops out.

Result: Device A wins and transmits.

Advantages:
Collision-free → Only one winner each round.
Prioritization → Higher-priority devices win.
Efficient at high load → No need to resend after collisions.

Disadvantages:
Priority Bias → Lower-priority devices may starve.
Overhead → The reservation process takes time.
Fixed Priorities → Hard to ensure fairness without changing numbers.

Binary Countdown Protocol

Binary Countdown Protocol is another name for Binary Countdown Reservation Protocol
(BRAP) — a collision-free protocol used in networks (like LANs) to decide which device
gets to send data.

Here’s a simple explanation:

Concept:
Many devices may want to transmit at the same time.
Each device is assigned a priority number (in binary form).
 Devices broadcast their number bit by bit, starting with the most significant
bit (MSB).
If a device sees a higher bit ( 1 ) while its own bit is 0 , it drops out (stops
competing).
At the end, the highest priority number wins and that device transmits.
After that, the process repeats.

Why it's called "Countdown":

Devices effectively count down in priority:

If your number can't win, you step back early, avoiding a collision.

Example:

Say we have 3 devices with these priority numbers:

Device Priority (binary)

A 101

B 011

C 100

Step-by-step:

First bit:
Devices A and C transmit 1 , B transmits 0 . → B drops out.

Second bit:
A transmits 0 , C transmits 0 . → Both stay.

Third bit:
A transmits 1 , C transmits 0 . → C drops out.

Result: Device A wins and transmits.

Advantages:
No Collisions → Only one winner per round.
Fast decision → Very efficient when many devices want to send.
Priority Control → Higher-priority devices can transmit first.

Disadvantages:
Unfair → Lower-priority devices may have to wait long (starvation).
Overhead → Extra bits must be transmitted for the countdown.
Priority must be managed → Needs a mechanism to assign priorities.

MLMA: Multi-Level Multi-Access Protocol

(Most likely what you mean by "MLMA" — sometimes called Multi-Level Multi-Access or
Multi-Level Multi-Access Limited Contention Protocol)

It is a type of Limited Contention Protocol used in networks to manage when devices

send data.

The Problem:
 In high traffic, random access protocols (like ALOHA, CSMA) suffer because too
many devices try to send → lots of collisions.

In low traffic, strictly collision-free protocols (like Token Passing) are

inefficient because devices waste time taking turns even when no one needs to
send.

Solution → Limited Contention Protocols:

Limited Contention Protocols try to get best of both worlds:

Use contention (random access) when few devices want to send.

Use controlled access (organized turns or scheduling) when many devices want to
send → avoiding collisions.

How MLMA Works (Simple Terms):

1. The protocol organizes devices into groups (levels).

2. At first, all devices are allowed to contend (try to send).

3. If too many collisions happen → the system starts to limit contention:

It selects a subset of devices (a level or group) to try next.

This process continues → groups get smaller → fewer devices competing →

collisions reduce.

4. Eventually, one device succeeds and transmits.

5. Then the protocol resets and starts again.

This is why it’s called Multi-Level — the contention is done in levels:

Level 1 → All devices

Level 2 → Half of them
Level 3 → Fewer, and so on.

Example (Very Simple):

8 devices want to send.
First, all 8 try → collision happens.
System splits: 4 devices at a time try.
If collision again → 2 devices at a time.
If collision again → 1 device at a time → winner transmits.
After success, system resets.

Advantages:
Adaptive → Works well in both high and low traffic.

Collision-free under high load → Controlled steps reduce collisions.

Efficient → No need for full scheduling like Token Ring.

Disadvantages:
 More complex than basic random access.

Overhead → Time spent splitting groups and managing levels.

If too many levels → latency increases.

Adaptive Tree Walk Protocol

Adaptive Tree Walk Protocol is another type of Limited Contention Protocol used to
resolve collisions in networks.

It is based on the idea of a binary tree structure, and it helps organize which
devices are allowed to transmit — especially when there are many competing devices.

Why It Is Needed:

In random-access networks (like ALOHA or CSMA), when many devices try to send
at once, lots of collisions happen → very inefficient.

Adaptive Tree Walk is designed to manage this situation:

It helps systematically decide who should send next.

It reduces the chance of further collisions.

Simple Idea:
1. Imagine devices are organized in a binary tree.

2. The root node represents all devices trying to transmit.

3. The process starts at the root:

If a collision happens, the system divides the set into two groups:
Left child → First half of devices
Right child → Second half of devices

4. It then explores one child at a time (one group at a time):

If a collision happens again → split that group further and repeat.

If no one wants to send → skip that branch.
If one device sends successfully → move to the next group.

5. The tree is explored adaptively — not strictly depth-first or breadth-first —

but based on the outcome (collision, success, idle).

Example:
Say 8 devices want to send:

[1-8]
/ \
[1-4] [5-8]
/ \ / \
[1-2] [3-4] [5-6] [7-8]

Start with [1-8]. Collision → split.

Try [1-4]. Collision → split.
 Try [1-2]. Device 2 sends successfully.
Now move to [3-4], and so on.

Adaptive Behavior:
If the system sees an empty group (no device wants to send), it skips it →
saves time.
The search path is adaptive based on which groups cause collisions or
successes.

Advantages:
Collision reduction → fewer wasted transmissions.
Adaptive → responds to current network load.
Efficient in high traffic → works better than pure random access when many
devices want to send.

Disadvantages:
Overhead → managing the tree and splitting groups takes time.
Latency → under light traffic, simpler protocols (like CSMA) are faster.

Performance Measuring Metrics

Here’s a simple explanation of common Performance Measuring Metrics for Medium Access
Control (MAC) protocols or network protocols, like the ones we’ve discussed (Tree
Walk, MLMA, CSMA, etc.):

1. Throughput
Definition: How much useful data is successfully transmitted over the network
per unit of time.

Goal: Higher throughput is better — means the channel is used efficiently.

Example: If the network can carry 1000 packets/second, and we are achieving 800
packets/second → 80% throughput.

2. Delay (or Latency)

Definition: Time taken from when a packet is ready to be sent to when it is

actually delivered.

Includes:

Queuing delay (waiting for turn),

Transmission delay,

Propagation delay.

Goal: Lower delay is better — means data reaches faster.

3. Channel Utilization

Definition: Fraction of time the channel is actually carrying useful data (vs.
being idle or in collision).

Goal: Higher utilization means the channel is being used well.

4. Collision Rate

Definition: How often collisions occur during transmission attempts.

Goal: Lower collision rate is better — fewer wasted attempts.

5. Fairness

Definition: How fairly the available bandwidth or access is distributed among

devices.

Goal: All devices should get reasonable chances to transmit.

Example: If one device always wins (as in BRAP), fairness is poor.

6. Efficiency

Definition: Ratio of useful data sent to total time spent (including overhead,
collisions, etc.).

Goal: Higher efficiency means fewer resources wasted.

What is IEEE 802?

A set of network standards developed by the IEEE (Institute of Electrical and
Electronics Engineers).

Focuses mainly on LAN (Local Area Network) and MAN (Metropolitan Area Network)
technologies.

Works mostly on Layer 1 (Physical Layer) and Layer 2 (Data Link Layer) of the
OSI model.

Purpose → Define how devices on a local or metropolitan network communicate.

Structure:
IEEE 802 is the overall series. Under it, there are many variants, each covering a
specific type of network.

Main IEEE 802 Variants:

IEEE
Name / Purpose Example Use
802.x

LAN/MAN management, bridging (Switches),

802.1 Managing networks
Spanning Tree

Logical Link Control (LLC) — part of Data

802.2 Works with all 802 variants
Link Layer

Office LAN with Ethernet

802.3 Ethernet (Wired LAN)
cables

802.4 Token Bus (Rare, now mostly obsolete) Industrial networks

802.5 Token Ring (Mostly obsolete) Old IBM networks

 Metropolitan networks
802.6 MAN — Distributed Queue Dual Bus (DQDB)
(legacy)

802.7 Broadband LAN (No longer active) Older broadband LANs

802.8 Fiber Optic LANs (No longer active) Older fiber networks

Mixed-use networks
802.9 Integrated Services LAN (Data + Voice)
(Obsolete)

802.10 Network security (Obsolete) Securing LANs

802.11 Wireless LAN (Wi-Fi) Home/office Wi-Fi

802.12 Demand Priority LAN (100BaseVG) Now obsolete

Wireless Personal Area Network (WPAN) —

802.15 Bluetooth, ZigBee
Bluetooth

Wireless broadband
802.16 Broadband Wireless MAN (WiMAX)
(citywide)

Carrier networks, optical

802.17 Resilient Packet Ring (RPR)
networks

Coordination of radio
802.18 Radio Regulatory TAG
standards

802.19 Coexistence of Wireless Networks Avoiding interference

Mobile data networks

802.20 Mobile Broadband Wireless Access (MBWA)
(early)

Smooth handoff between Wi-

802.21 Media Independent Handover
Fi and cellular

Wireless Regional Area Network (WRAN) —

802.22 Rural broadband
using TV White Spaces