Computer Network

B.Tech, Computer Engineering

Delhi Technological University
Module 2_4: Medium Access Control Sublayers
Instructor: Divyashikha Sethia
Assistant Professor, Department of Software Engineering

1
• Network can be divided into two categories-

• i) Using pt to pt connections

• ii) Using broadcast channels

• LANs use broadcast channel.

• WANs are Pt to Pt except for satellite network.

2
 Medium Access Control
• The protocols used to determine who goes next on
a multiaccess channel belong to a sublayer of the
data link layer called the MAC (Medium Access
Control) sublayer.

3
 broadcast channels
• Key Issues:

- who gets to use the channels when there are

multiple nodes competing for it

- MAC sublayer of the data link layers determines

which node gets to access the broadcast channel.

- A network of computers broad or multi-access

medium requires protocol for effective sharing of
media, as only one node can send or transmit signal
at a time using broadcast node.

- where and how control to medium is given to a

node.
4
 Broadcast Channels
• Where control: is the control centralised or
decentralised distributed.

5
 Centralised control

Centralised Master node grants access for medium to other nodes.

Advantages:
•Greater control for priority, guarantied bandwidth
•Simpler logic at each node.
•Easy coordination.

Disadvantages:
- Vulnerable to failure of the master node.

6
Distributed approach in which nodes collectively perform a medium
access control function and dynamically decide which node gets the
medium access.

7
What manner the control is exercised?
MAC technique can be broadly be divided into four categories:-

MAC
|
_______________________________________________________________________
| | | |
Random Round Robin Reservation Channelization
| | | |
___________Pure Aloha _______ ________________ _________________
|_________ Slotted Aloha | | | | | | |
|_________CSMA Polling Token Passing Centralised Distributed FDMA TDMA CDMA
|_________CSMA/CD
|_________CSMA/CA

8
•Focus of random MAC.

•CSMA/CA is a wireless LAN protocol.

•Channelisation based MACs are used in cellular telephone network.

•Reservation based MACs are used in satellite.

9
 Contention Based Approach

•This is suitable where there are few nodes which have data for brief
periods of time suitable for bursty nature of traffic.

•Node which wants to transmit data contends for gaining control of the
medium.

10
 ALOHA
•Invented in 1970 for packet radio network connecting remote stations to
a central computer and various data terminals at campus at Howard
University.

• Users are allowed random access of central campus through common

radio frequency band f1 & the central campus broadcasts all received
signal at a different frequency band f2.

•Enables users to monitor pkt collisions.

11
 ALOHA Example

Central Server

f2 f2
f2

f1 f1
f1

B C
A

f1- random access f2 - broadcast

12
 Pure ALOHA

•This is pure Aloha- whenever node has a packet to send, it simply does
so.
•Frames will suffer collision and colliding frames will be destroyed.

•A user comes to know whether the packet sent has suffered collision, by
monitoring signal sent by control computer.
•After collision wait for random time and then retransmit

In pure ALOHA, frames are transmitted at completely arbitrary times.

13
Assumes all packets have fixed duration t. Packet will collide if there
is an overlap.
Vulnerable period is 2t.
14
 Calculating throughput for Pure ALOHA

•In probability theory, Poisson distribution expresses number of

events occurring in a fixed period of time if these events occur with a
known average rate & independently of the time since the last event.
If expected number of occurrence in this interval is G, then
probability that there are exactly k occurrences.

P[k] = Gk e-G / k!

15
 Calculating throughput for Pure ALOHA

•Frame Time denotes the amount of time needed to transmit the

standard fixed length frame ( Frame Time = Frame length / Bit Rate)

•Assume infinite users generate new frames according to Poisson

distribution at rate of mean N frames per frame time

•If N >1, users are generating frames at a higher rate than channel can
handle & frames will suffer collision. Hence 0<N<1

•Along with new frames these are retransmissions of frames that

previously suffered collisions.

•Probability of k transmissions attempts per frame time, old and new

16
combined is also considered Poisson with mean G per frame time.
 Calculating throughput for Pure ALOHA...

=> G >= N
- At low load N approximately 0, there are few collision hence few
retransmission => G appx N
-At high load there are many collisions
Probability for packet x to be successfully delivered =
Probability that there is no other packet during the period =
P(0) = Probability of 0 other frames in the period.
P[k] = Gk e-G / k! (K=0)
Throughput for the time period has G frames transmitted.
Throughput S = Offered Load = Average number of packets that can
successfully go throughout
= G Po.
Po = Probability that a frame does not suffer a collision. i.e Po is
probability of successful frames.
Pr [0] = Probability of 0 frames 17
0 -G
= G e / 0! = e -G
 Calculating throughput for Pure ALOHA...

No other frames are sent within one frame time.

Interval of 2 frames long i.e vulnerable period, mean number of
frames generated = 2G.
Probability that no other traffic is being controlled during the
vulnerable period to given by:
Po= e-2G (2 because it is probability for 2 frame period)
But S = GPo
S = G e-2G = Throughput in frames of offered load

18
 Slotted ALOHA

It is an Improvement over pure ALOHA. Channel is divided into slots

equal to time t and pkt transmission can only start at the beginning of a
slot.
i.e. the vulnerable period is reduced from 2t to t
Probability that no other traffic is being initiated during vulnerable
period is
Po = = G0 e-G / 0! = e-G
=> S = G P0 = G e-G
Slotted ALOHA peaks at G = 1 with throughput S = 1/e or about 0.368
twice that of pure ALOHA.

19
Best channel utilisation of 18% is obtained at 50% of the offered load.
Smaller offered load, channel capacity is underused.
Higher load, too many collisions reduce throughput.
20
 CSMA

-Poor efficiency of ALOHA is due to the fact that a node starts

transmitting w/o considering what other nodes are doing.

-If the propagation delay of the signal b/w 2 nodes is small compared to
the transmission time of a pkt, all other nodes will know quickly when a
node starts transmission.

- This is the observation made is Carries Sense Multiple Access

(CSMA)
* Node that wants to transmit data first listens to the medium to check
whether another transmission is in progress.
* Node starts sending only when the channel is free. 21
 CSMA…

Variations-

•1 Persistent CSMA:
-If the channel is free when sensed by a node, it transmits data.
-If channel is busy, nodes continues to monitor unit channel is idle
& then starts sending.

• Non-Persistent CSMA:
-If channel is free, node transmits.
-If busy, node waits for random amount of time & then monitors
again.

22
 CSMA..

• 3- P-Persistent
i) When station becomes ready to send it senses the channel
ii)If idle it transmits with prob p. and with prob q = 1-p defers it until
next slot. If that slot is also idle it either transmits or defers again with
prob p and q. Continues until frame has been transmitted or anther
station has begum transmitting.
iii)If channel is busy it waits for random time and starts again from i)
iv) If initially it senses channel busy then waits until next slot and starts
again i)

23
 CSMA/CD

Carrier sense multiple access with collision detection:

-Refinement over CSMA. In CSMA, when 2 pkts collide, channel
remains unutilized for entire duration of transmission time for both the
pkt.

-Wasted channel capacity can he large if the propagation time is small

compared to pkt transmission.

-This wastage of channel capacity can be reduced if nodes continue to

monitor channel during pkt transmission & immediately cease
transmission when collision is detected. It transmits jamming signal for
brief duration to ensure that all station know that collision occurred.

24
 CSMA/CD

-After this, node waits for random time & then retransmits, to ensure
that nodes involved in collision are not likely to have collision on
retransmission.

-To achieve stability binary exponential backoff is used. If there are

repeated collisions node attempts to retransmit each time at each
collision, value of random delay is doubled after 15 retries including
original try. Unlucky pkt is discarded.

25
Pure ALOHA gives max throughput of 100% & is suitable only for very
low offered load.
-Slotted ALOHA: S max = 0.36
-Non -persistent CSMA is better than persistent due to smaller
probability of collision for retransmitted pkt in non-persistent.
-Non -persistent CSMA/CD provides high throughput and can tolerate
heavy load.
26
CSMA/CD
Can be in one of three state contention, transmission or idle t0

Idle time implies no work.

t0 is the time frame finished transmission.

27
•If 2 stations starts transmit at t0, minimum time to detect collision is
time it takes the signal to propagate from one at to another.

•Time signal takes to propagate between 2 farthest station = t

Most distant station begins transmission at t - є instant before this signal
comes.

•The most distant station detects collision & stops instantly but the noise
burst generated from the collision gets back to the original station only
until 2t - є

28
Station can be sure that it has seized the channel until it has
transmitted for 2t w/o hearing a collisions

The contention interval is considered as SLOTTED ALOHA at slot 2t

wide.

Assume each slot contains 1 bit.

Once the channel is seized, station can transmit at any rate not just 1 bit
per 2t second.

29
 THANKS

References:
Tanenbaum chapter 4 (4.1, 4.2.1, 4.2.2)

30