Application

Transport
Network
Link
Physical

MAC is here!

Computer Networks

Medium Access Control

Dr. Satish Anamalamudi,

Department of CSE
SRM University-AP
 Overview
• In broadcast networks (Multi-access/random-access channels)
– The key issue is how to determine who gets to use the channel when there is
competition for it.
– MAC=Protocol to determine who goes next on channel.
– It’s important for LANs(Bus topology, WiFi), WANs are point-to-point.

• How to allocate a single broadcast channel among competing

users ??
• Can be done using :
– Static Channel Allocation.
• FDM and TDM.
– Dynamic Channel Allocation.
• ALOHA and Carrier Sense Protocols.
 Static Channel Allocation(FDMA)
• Let’s say N users exist:
• the available bandwidth is divided into N equal-sized portions.
• Each user is assigned to one portion(1/N).
• Since each user has a private frequency band
• there is no interference among users.
• Example : Wireless FM radio channels (Each station gets a portion of the
FM band and uses it most of the time to broadcast its signal.)

• Static channel allocation is efficient when :

• Number of users are less than available channels.
• Data transmission should have steady stream.

• Inefficient to divide into fixed number of chunks.

• May not all be used, or may need more.
• Doesn't handle bursty traffics of computer systems.
 Static Channel Allocation(TDMA)
• In a time slot only 1 user transmits (or receives).
• Several users share a single frequency channel.
• Transmission is non-continuous.
• Power consumption is lower than FDMA (e.g., the transmitter can be
turned off when idle)
• Synchronization is needed
 Dynamic channel allocation
Assumptions:
– Station Model: Assumes that each of N "stations" (packet generators, Terminal) independently produce frames. The station generates no new frame until that previous one is transmitted.

– Single Channel Assumption: There's only one channel; all stations are equivalent and can send and receive on that channel.

– Collision Assumption: If two frames overlap in any way time-wise, then that's a collision. Any collision is an error, and both frames must be retransmitted. Collisions are the only possible error.

– Continuous/ Slotted Time: Time is not in discrete chunks. Frame transmission can begin at any instant. Alternatively, in slotted, frame transmissions always begin at the start of a time slot. Any station can transmit in any slot (with a possible collision.)

– Carrier/No-Carrier Sense: Stations can tell a channel is busy before they try it. NOTE - this doesn't stop collisions.
 Multiple Access Protocols: ALOHA
ALOHA
– Developed in Hawaii in the 1970s.
 PURE ALOHA:
– Every station transmits whenever it wants to.
– Colliding frames are destroyed. The sender knows if its frame got destroyed using feedback property, and if so waits a random time and then retransmits.
– ANY overlap is a collision.
– Best efficiency if frames are same size.
– A contention system: Multiple users share a common channel that can lead to conflict.
Pure Aloha(2)
 Multiple Access Protocols: ALOHA
ALOHA : Performance
– collision probability increases:
– pkt sent at t0 collide with other pkts sent in [t0-1, t0+1]

– Very inefficient : Maximum achievable Throughput (18%)

P(success by given node) = P(node transmits) .

P(no other node transmits in [t0-1,t0] .
P(no other node transmits in [t0,t0 +1]
 Slotted Aloha
• Time is divided into equal size slots (= packet trans. time)
• Node with new packet: transmit at beginning of next slot.
• If collision: retransmit packet in future slots with probability p, until
successful.

Success (S), Collision (C), Empty (E) slots

 Slotted ALOHA

Slotted ALOHA is twice as efficient as pure ALOHA

– Low load wastes slots, high loads causes collisions
– Efficiency up to 37% (almost twice to PURE ALOHA)

Comparison of the channel utilization versus load for various

random access protocols.
 Carrier Sense Multiple Access
Protocols
• CSMA protocol was developed to overcome :
• the problem in pure ALOHA and slotted ALOHA.
• i.e. to minimize the chances of collision.

• CSMA protocol is based on the principle of ‘carrier sense’. ("sense

before transmit" or "listen before talk).
• Carrier Sense – the ability of a network card to sense or detect
communication on the network.
• Multiple Access – states that in that network there are multiple stations
that could access the network at the same time.

• The chances of collision can be reduce to great extent if a station senses

the channel before trying to use it.

• Although CSMA can reduce the possibility of collision, but it cannot

eliminate it completely.
 Carrier Sense Multiple Access
Protocols
• There are three different types of CSMA protocols :-
(i) 1-Persistent CSMA
(ii) Non-Persistent CSMA
(iii)P-Persistent CSMA
1-Persistent CSMA
• When a station has data to send :
• it first listens(carrier sense) to the channel to see if anyone else
is transmitting at that moment.
• If the channel is idle:
• the stations sends its data(frame).
• If the channel is busy :
• the station just waits until the channel becomes idle.
• Later, the station start transmitting a frame.
• If a collision occurs :
• the station waits a random amount of time and starts all over
again.
• The protocol is called 1-persistent because the station transmits
with a probability of ‘1’ when it finds the channel idle.
CSMA collisions (Propagation delay)
 1-Persistent
• CSMA
Effect of propagation delay in CSMA :
• If a signal from station A has not reached to station B and
station B is ready to send, it will sense the channel to be idle and
send its frame.

• Collision can be there even when propagation delay is zero and

carrier sense is also there.
• If stations B and C become ready in the middle of A’s
transmission, B and C will wait until the end of A’s
transmission and then both will begin transmitted
simultaneously, resulting in a collision.

• If B and C were not so greedy, there would be fewer collisions.

 Non-Persistent
•
CSMA
when a station is ready to send a frame , it senses the channel :
• if busy : waits for random time rather than continuously sense it
for the purpose of seizing it.
• if idle : sends it.
• if collision : waits for random time and tries again.

• Less greedy than 1-persistent, hence better channel utilization but

longer delays.
• Reduced collision rate in comparison with 1-persistent CSMA.

Random Waiting
times

Wasted time
 Non-Persistent
CSMA
• Advantages of non-persistent CSMA:
• Less greedy than 1-persistent.
• It reduces the chances of collision because the stations wait a
random amount of time before transmitting.

• Disadvantages of non-persistent CSMA:

• Longer delays : This is due to the fact that the stations wait a
random amount of time before transmitting.
 P-Persistent
• Time is divided into slotsCSMA
where each Time unit (slot) is typically
equals to maximum propagation delay
• Station wishing to transmit listens to the medium:
• If medium idle,
• transmit the frame with probability (p), OR
• wait one time unit (slot) with probability (1 – p), then repeat 1.
• If medium is busy, continuously listen until idle and repeat step 1
• Performance :
• Reduces the possibility of collisions like 1-persistent.
• Reduces channel idle time like non-persistent
P-Persistent
CSMA
Persistent and Nonpersistent CSMA

Comparison of the channel utilization versus load for various random

access protocols.
 CSMA/CD
• CSMA with collision detection.
• Problem: when frames collide, medium is unusable
for duration of both (damaged) frames.
• For long frames (when compared to propagation
time), considerable waste.
• What if station listens while transmitting?
 Ethernet CSMA/CD
• Use any persistent CSMA for frame transmission.
• Transmit packet only if channel is sensed idle.
• During the packet transmission, the node’s computer hardware
monitors(listens) its own transmission to see if the packet has
experienced a collision.
• An additional XOR gate is implemented at the transmitter.
• If received signal XOR with transmitted signal is “0” then no
collision.
• If received signal XOR with transmitted signal is “1” then there is
a collision.
• Stop the ongoing frame transmission(when XOR=1).
• Collisions are detected within a few bit times.
• Transmission is then aborted, reducing the channel wastage
considerably.
• Sends a jamming signal to all of its neighbour stations.
CSMA/CD collision detection
Collision and abortion in CSMA/CD
CSMA/CD
 CSMA/CD Performance
• Wasted capacity is restricted to time to detect collision.
• Time to detect collision < 2*maximum propagation delay.

• Rule in CSMA/CD protocols: frames are long enough to allow

collision detection prior to end of transmission.
• Assumption : Transmission time is equal to maximum propagation time.

• What happens if the collision detection happens after transmission

time ?
• This case is true if collision happens close to the receiver.
• A jamming Signal will be broadcasted in the shared medium
• Nodes that receive the jamming signal will wait for backoff time.
 Collision Free Protocols

• Pure ALOHA, slotted ALOHA, CSMA and

CSMA/CD are contention based protocols
– try. If collide, retry.
– No guarantee of performance.
– What happens if the network load is high?
• Collision free protocols:
– pay constant overhead to achieve
performance guarantee
– Good when network load is high
 Collision Free
World
• Provides in order access to shared
medium so that every station has chance
to transfer (fair protocol)
• Eliminates collision completely.
• Three methods for controlled access:
– Reservation (Bitmap protocol)
– Polling
– Token Passing
 Reservation – Bit Map Protocol
• Two rounds of transmission cycle
• First Round (Contention Period)
• Consists of N slots each reserved for a particular station
• In this period, each station transmits
• 1 if it has a frame to transmit
• 0 if it has no frame to transmit
• At the completion of the first round everybody knows who wants to
transmit
• Second Round (Transmission Period)
• Stations transmit according to the order formed in the first round
• There will not be any collisions
 Bit Map - Reservation
Based
• When a station needs to send a data frame, it
makes a contention in its own 1-bit mini-slot.
• By listening to the contention interval, every
station knows which stations will transfer
frames, and in which order.
• The stations that made reservations can send
their data frames after the reservation frame.
 Token Ring

• Token pass.
• There is only one token in the network.
• The token is passed through every node in the network.
• Only the node that has the token can transfer data.
 Binary Countdown

The binary countdown protocol. A dash indicates silence.

 Contention vs. Collision-Free
• Contention better under low load. Why?
• Less collisions under low load.
• Collision-free better under high load. Why?
• Channel utilization is better at high load.
• How about combining their advantages -- limited
contention protocols.
• Behave like the ALOHA scheme under light load
• Behave like the bitmap scheme under heavy load.
 Limited contention protocols

– collision based protocols (ALOHA,CSMA/CD) are good when the

network load is low.
– collision free protocols (bit map, binary countdown) are good when
load is high.
– How about combining their advantages -- limited contention
protocols.
• Behave like the ALOHA scheme under light load
• Behave like the bitmap scheme under heavy load.
 Limited contention protocols:
– adaptive tree walk protocol
• trick: partition the group of station and limit the
contention for each slot.
– under light load, every one can try for each slot like aloha
– under heavy load, only a small group can try for each slot
– how do we do it
» treat stations as the leaf of a binary tree.
» first slot (after successful transmission), all stations (under
the root node) can try to get the slot.
» if no conflict, fine.
» if conflict, only nodes under a subtree get to try for the
next one. (depth first search)
Example: 0

1 2

3 4 5 6

A B C* D E* F* G H*

Slot 0: C*, E*, F*, H* (all nodes under node 0 can try), conflict
slot 1: C* (all nodes under node 1 can try), C sends
slot 2: E*, F*, H*(all nodes under node 2 can try), conflict
slot 3: E*, F* (all nodes under node 5 can try), conflict
slot 4: E* (all nodes under E can try), E sends
slot 5: F* (all nodes under F can try), F sends
slot 6: H* (all nodes under node 6 can try), H sends.
 Motivation for Wireless MAC
• Can we apply media access methods from fixed networks?
• Example CSMA/CD
– Carrier Sense Multiple Access with Collision Detection
– send as soon as the medium is free, listen into the medium if a collision
occurs (original method in IEEE 802.3)
• Problems in wireless networks
– Signal strength decreases proportional to the square of the distance
– Sender would apply CS and CD, but the collisions happen at the
receiver (Hidden terminals)
– it might be the case that a sender cannot “hear” the collision, i.e., CD
does not work
 Hidden and Exposed Terminals
• A wants to
transmit to B.
• C senses channel
– no idea A is
transmitting.
A B • C initiates
F transmission to F.
C
• Collision at B. – C
D and A are hidden
from each other.

• D could potentially transmit to E but does not –

senses A’s carrier. D is exposed to A. Loss in
 Hidden and exposed terminals
• Hidden terminals
– A sends to B, C cannot receive A
– C wants to send to B, C senses a “free” medium (CS fails)
– collision at B, A cannot receive the collision (CD fails)
– A is “hidden” for C

• Exposed terminals A B C
– B sends to A, C wants to send to another terminal (not A/B)
– C has to wait, CS signals a medium in use
– but A is outside the radio range of C, therefore waiting is not necessary
– C is “exposed” to B
 MACA - collision avoidance
• No carrier sense (CS)
• MACA (Multiple Access with Collision Avoidance) uses short signaling packets for collision avoidance
– RTS (request to send): a sender request the right to send from a receiver with a short RTS packet before it sends a data packet
– CTS (clear to send): the receiver grants the right to send as soon as it is ready to receive
• Signaling packets contain
– sender address
– receiver address
– packet size
• Variants of this method can be found in IEEE 802.11.
 MACA examples
• MACA avoids the problem of hidden terminals
– A and C want to
send to B
– A sends RTS first
– C waits after receiving
CTS from B

• MACA avoids the problem of exposed terminals?

– B wants to send to A, C
to another terminal
– now C does not have
to wait for it cannot
receive CTS from A

RTS

CTS CTS
A B C

RTS RTS

CTS
A B C
 Alternative Approach: MACAW
• No carrier sense, no collision detection
• Collision avoidance:
– Sender sends RTS
– Receiver sends CTS
– Sender sends DATA
– Receiver sends ACK
• Backoff mechanism:
– Exponential backoff with significant changes for improving fairness
and throughput
•
•
A sends out RTS and set a timer and waits for CTS
If A receives CTS before timer go to zero, OK! sends data packet
MACA
• Otherwise, A assumes there is a collision at B
• Double the backoff counter interval
• Randomly pick up a timer from [1,backoff counter]
• Send next RTS after timer go to zero
• B sends out CTS, then set a timer and waits for data packet
• If data packet arrives before timer go to zero, OK!
• Otherwise, B can do other things
• C overhears A’s RTS, set a timer which is long enough to allow A to receive CTS. After the timer goes to zero, C can do other things
• D overhears B’s CTS, set a timer which is long enough to allow B to receive data packet.
• E overhears A’s RTS and B’s CTS, set a timer which is long enough to allow B to receive data packet.
• RTS and CTS can also contain info to allow sender A to adjust power to reduce interference
 Interconnecting LANs
Q: Why not just one big LAN?
• Limited amount of supportable traffic: on single LAN, all stations must share bandwidth
• limited length: 802.3 (Ethernet) specifies maximum cable length
• large “collision domain” (can collide with many stations).

• Multiple LANs are connected through :

• HUB/Repeater :Connect two LANs at physical layer.
• Switch : Connect two LANs at the link layer(MAC address)
• Router : Connect two subnets at the network layer (IP address)
 Interconnection Devices

• There are many different devices for interconnecting

networks.
Ethernet Ethernet

Repeater Ethernet

Bridge
Router

Token- X.25
ring Network
Gateway
 Hubs/Repeaters
• Physical Layer devices: essentially repeaters operating at
bit levels: repeat received bits on one interface to all other
interfaces
• Hubs can be arranged in a hierarchy (or multi-tier design),
with backbone hub at its top

Collison Domain
 Hubs (more)
• Each connected LAN referred to as LAN segment
• Hubs do not isolate collision domains: node may collide
with any node residing at any segment in LAN
• Hub Advantages:
– simple, inexpensive device
– portions of the Multi-tier Hub LAN continue to operate if one hub
malfunctions
– extends maximum distance between node pairs (100m per Hub)

• Hub Limitations:
•single collision domain results in no increase in max throughput
multi-tier throughput same as single segment throughput
•cannot connect different Ethernet types (e.g., 10BaseT and
100baseT)
 Bridges
• Link Layer devices: operate on Ethernet frames, examining frame header and selectively forwarding frame based on its destination.
• Bridge isolates collision domains since it buffers frames.
• When frame is to be forwarded on segment, bridge uses CSMA/CD to access segment and transmit.

• Bridge advantages:
– Isolates collision domains resulting in higher total max throughput, and does not limit the number of nodes nor geographical coverage.
– Can connect different type Ethernet since it is a store and forward device

Collison
Domain-2
Collison Domain-1 Collison Domain-3
 Interconnection Without Backbone

• Not recommended for two reasons:

– - single point of failure at Computer Science hub
– - all traffic between EE and SE must path over CS segment

Switch
Hub
Switch ports
Twisted pair
 Bridge Learning: example
Suppose C sends frame to D and D replies back with
frame to C

C 1
 C sends frame to bridge
 bridge notes that C is on port 1 in the filtering table
 bridge has no info about D, so floods to all the LANs
 Nodes will compare the destination address of the
frame
 frame received by D
 Bridge Learning: example

C 1
D 2
 D generates reply to C, sends
 bridge sees frame from D
 bridge notes that D is on interface 2
 bridge knows C on interface 1, so selectively
forwards frame out via interface 1
 Bridge Operation
bridge procedure(in_MAC, in_port,out_MAC)
Set filtering table (in_MAC) to in_port /*learning*/
lookup in filtering table (out_MAC) receive out_port
if (out_port not valid) /* no entry found for destination */
then flood; /* forward on all but the interface on
which the frame arrived*/

if (in_port = out_port) /*destination is on LAN on which

frame was received */
then drop the frame

Otherwise (out_port is valid) /*entry found for destination */

then forward the frame on interface indicate
 Self-learning multi-switch S1
example Addres Port
s
Suppose C sends frame to I, I responds to C C 1
I 4

1 S4
S1 3 S4
1 1 S3
A 4 S2 2 Addres Port
F s
1 D I
B C C 1
E G H
I 3
S3
 Q: show switch tables and packet forwarding in Addres Port
s
S1, S2, S3, S4 C 1
S2 I 2
Addres Port
s
C 1
 The Danger of Loops
CC DD
a) <Src=AA, Dest=DD>
b) This continues to infinity
– How do we stop this?
c) Remove loops from the Hub
topology
Port 2 Port 2
– Without physically unplugging cables
AA 12 AA 12
d) 802.1 uses an algorithm to Port 1 Port 1
build and maintain a
spanning tree for routing Hub

AA BB
 Loops and Routing

N S6
P

S5 O
K
L M S1
S2 S4
A S3
F I
B C D
E G H

There should be only one path exist from the Source to Destination to avoid the
loops at the data link layer.
 Spanning Tree Definition

a) A subset of edges in a graph that:

– Span all nodes
– Do not create any cycles
b) This structure is a tree 5

1 2 3 4 6 2

5 3
4 1

6 7 7
5
7

802.1 Spanning Tree Approach

• Elect a bridge to be the root of the tree
• Every bridge finds shortest path to the root
• Union of these paths becomes the spanning tree

• Bridges exchange Configuration Bridge Protocol Data Units (BPDUs) to build the tree
– Used to elect the root bridge
– Calculate shortest paths
– Locate the next hop closest to the root, and its port
– Select ports to be included in the spanning trees
5
8

Definitions
• Bridge ID (BID) = <Random Number>
• Root ID: bridge with the lowest BID in the tree.
• Path Cost: cost (in hops) from a transmitting bridge to the root
• Each port on a bridge has a unique Port ID.
• Root Port: port that forwards to the root on each bridge
• Designated Bridge: the bridge on a LAN that provides the minimal cost path to the root
– The designated bridge on each LAN is unique
5
9

Determining the Root

• Initially, all hosts assume they are the root.

• Bridges broadcast BPDUs:
Designated Bridge ID Root path cost Root ID

• Based on received BPDUs, each switch chooses:

– A new root (smallest known Root ID)
– A new root port (what interface goes towards the root)
– A new designated bridge (who is the next hop to root)
6
0

Comparing BPDUs
BPDU1 BPDU2
B1:R1/Cost1 B2:R2/Cost2

if R1 < R2: use BPDU1

else if R1 == R2 and Cost1 < Cost2: use BPDU1
else if R1 == R2 and Cost1 == Cost 2 and B1 < B2: use
BPDU1
else: use BPDU2
6
1

Spanning Tree Construction

0: 0/0 12:
12:12/0
0/1 3: 0/2
3/0

27: 27/0
27: 0/1 41: 41/0
41: 3/1
0/2

9: 3/2
0/3
9/0 68: 3/2
9/1
68: 68/0
0/3