The Medium

Access Control
Sublayer

The Medium Access Control Sublayer

XP

❑ Network Links can be divided into:

1. Point-to-point connections
2. Broadcast channels
❑ We have discussed Point-to-Point
Connections.
❑ Broadcast Links and their Protocols will be
discussed next.

CS2008-Computer Networks
(Dr. V. K. Jain ) 1
 The Medium Access Control Sublayer
XP

❑ In any broadcast network, the key issue

is how to determine who gets to use the
channel when there is competition.
❑ Example: teleconferencing.

❑ Broadcast Channels are also known as

Multi-access channels or random access
channels.

The Medium Access Control Sublayer

XP

❑ The protocols used to determine who goes

next on a multi-access channel belong to
a sublayer of the data link layer called the
MAC (Medium Access Control) sublayer.
❑ Especially important in LAN’s and
particularly in wireless communication.
❑ WANs use point-to-point links with the
exception of satellite links.

CS2008-Computer Networks
(Dr. V. K. Jain ) 2
 XP
Channel Allocation Problem
• Static channel allocation
• Dynamic channel allocation.

XP
Static Channel Allocation
❑ Traditionally capacity of the channel is
split among multiple competing users
(e.g., TDM or FDM).
❑ Example: FM radio stations.

❑ However, when the number of senders is

large and varying or the traffic is bursty
FDM presents some problems.

CS2008-Computer Networks
(Dr. V. K. Jain ) 3
 XP
Static Channel Allocation
❑ If the spectrum is cut up into N regions and
❑ Fewer than N users are currently interested in
communicating, a large piece of valuable
spectrum will be wasted.
❑ More than N users want to communicate
some of them will be denied permission for
lack of bandwidth.
❑ Dividing the channel into constant number
of users of static sub channels is inherently
inefficient.

XP
Static Channel Allocation
❑ A static allocation is poor fit to most
computer systems, in which data traffic is
extremely bursty:
❑ Peak traffic to mean traffic ratios of 1000:1
are common.
❑ Consequently most of the channels will be
idle most of the time.

CS2008-Computer Networks
(Dr. V. K. Jain ) 4
 XP
Static Channel Allocation
❑ Example:
❑ Mean Time delay T seconds,
❑ Channel capacity C bps,

❑ Average arrival rate l frames/sec

❑ Frames average length of 1/m bits.

❑ With these parameters, the service rate of

the channel is μC frames/sec.
1
𝑇=
𝜇𝐶 − l

XP
Static Channel Allocation
❑ C = 100 Mbps,
❑ 1/m = 10,000 bits 1
❑ l = 5000 frames/sec
𝑇 =
𝜇𝐶 − l
❑ T = 200 msec

❑ This result holds only when there is no

contention in the channel.

10

CS2008-Computer Networks
(Dr. V. K. Jain ) 5
 XP
Static Channel Allocation
❑ Divide a single channel into N independent
channels:
❑ C/N = 100/N Mbps, 1
❑ 1/m = 10,000 bits 𝑇 =
𝑁 𝐶 l
𝜇 −
❑ l/N = 5000/N frames/sec 𝑁 𝑁
❑ TN = Nx200 msec
𝑁
= = NT
❑ For N=10 => TN = 2 msec.
𝜇𝐶 − l

11

XP
Assumptions for Dynamic Channel Allocation
❑ Before we get to the first of the many channel
allocation methods, it is worthwhile to carefully
formulate the allocation problem.
❑ Underlying all the work done in this area are the
following five key assumptions:
1. Independent traffic
2. Single channel
3. Observable Collisions
4. Continuous or slotted time
5. Carrier sense or no carrier sense

12

CS2008-Computer Networks
(Dr. V. K. Jain ) 6
 XP
Assumptions for Dynamic Channel Allocation

❑ Independent Traffic:
❑ The model consists of N independent
stations.
❑ The expected number of frames generated in
an interval of length Δ𝑡 is 𝜆Δ𝑡. 𝜆 – is arrival
rate of new frames.
❑ Once the frame has been generated, the
station is blocked and does nothing until the
frame has been successfully transmitted.

13

XP
Assumptions for Dynamic Channel Allocation

❑ Single Channel:
❑ The single channel is available for all
communication.
❑ All stations can transmit on it and all can
receive from it.
❑ The stations are assumed to be equally
capable though protocols may assign them
different roles (i.e., priorities)

14

CS2008-Computer Networks
(Dr. V. K. Jain ) 7
 XP
Assumptions for Dynamic Channel Allocation
❑ Observable Collisions:
❑ If two frames are transmitted simultaneously,
they overlap in time and the resulting signal is
garbled.
❑ This event is know as collision.

❑ All stations can detect that a collision has

occurred. A collided frame must be
retransmitted.
❑ No errors other than those generated by
collision occur.

15

XP
Assumptions for Dynamic Channel Allocation
❑ Continuous or Slotted Time:
❑ Time may be assumed continuous. In which
case frame transmission can begin at any
instant.
❑ Alternatively, time may be slotted or divided into
discrete intervals (called slots).
❑ Frame transmission must then begin at the start
of a slot.
❑ A slot may contain 0, 1 or more frames,
corresponding to an idle slot, a successful
transmission, or collision, respectively.

16

CS2008-Computer Networks
(Dr. V. K. Jain ) 8
 XP
Assumptions for Dynamic Channel Allocation
❑ Carrier Sense or No Carrier Sense:
❑ With the carrier sense assumption, stations
can tell if the channel is in use before trying to
use it.
❑ No station will attempt to use the channel while
it is sensed as busy.
❑ If there is no carrier sense, stations cannot
sense the channel before trying to use it.
❑ They will transmit then. Only later they can
determine whether the transmission was
successful.

17

XP
Multiple Access Protocols
❑ ALOHA
❑ Carrier Sense Multiple Access

❑ Collision-free protocols

❑ Limited-contention protocols

❑ Wireless LAN protocols

18

CS2008-Computer Networks
(Dr. V. K. Jain ) 9
 ALOHA XP

❑ 1970 Hawaii
❑ Norman Abramson and colleagues have
enabled wireless communication between
users in a remote island to the central
computer in Honolulu.
❑ Two versions of the protocol now called
ALOHA:
❑ Pure ALOHA and
❑ Slotted ALOHA

19

XP
Pure ALOHA
❑ Each user is free to transmit whenever they have
data to be sent.
❑ There will be collisions

❑ Senders need some way to fond out if this is

the case.
❑ In ALOHA after the station transmits its message
to the central computer, the computer
rebroadcasts the frame to all of the stations.
❑ Original sending station can listen for the
broadcast from the hub to see if its frame has
gone through.

20

CS2008-Computer Networks
(Dr. V. K. Jain ) 10
 XP
Pure ALOHA
❑ In other wired systems the sender might be
able to listen for collisions while transmitting.
❑ If the frame is destroyed, the sender just waits
a random amount of time and sends it again.
❑ Waiting time must be random or the sending
frames will collide over and over.
❑ Systems in which multiple users share a
common channel in a way that can lead to
conflicts are known as Contention Systems.

21

PURE ALOHA (1) XP

User

Collision
Collision Time

In pure ALOHA, frames are transmitted

at completely arbitrary times

22

CS2008-Computer Networks
(Dr. V. K. Jain ) 11
 Pure ALOHA XP

❑ What is the efficiency of an ALOHA channel?

❑ What fraction of all transmitted frames escape collisions
under these chaotic circumstances?
❑ Infinite collection of users typing at their terminals (stations).
❑ User states: WAITING or TYPING.
❑ When a line is finished, the user stops typing waiting for
response.
❑ The station then transmits a frame containing the line over the
shared channel to the central computer and checks the
channel to see if it was successful.
❑ If so the users sees the reply and goes back to typing
❑ If not, the user continuously to wait while the station
retransmits the frame over and over until it has been
successfully sent.

23

Pure ALOHA XP

❑ Frame Time – denotes the amount of time needed to

transmit the standard, fixed-length frame.
❑ Each new frame is assumed to be generated by Poisson
distribution with a mean of N frames per frame time.
❑ If N>1 the user community is generating frames at a
higher rate than the channel can handle, and nearly
every frame will suffer a collision.
❑ For reasonable throughput we expect 0 < N < 1.

24

CS2008-Computer Networks
(Dr. V. K. Jain ) 12
 Pure ALOHA XP

❑ In addition to the new frames, the stations also generate

retransmissions of frames that previously suffered
collisions.
❑ Assume that the new and the old frames combined are
well modeled by a Poisson distribution with mean G
frames per frame time. 𝐺 ≥ 𝑁.
❑ Low load: 𝑁 ≈ 0 there will be few collisions, hence
few retransmissions, 𝐺 ≈ 𝑁
❑ High load: there will be many collisions, 𝐺 > 𝑁.

25

XP
Pure ALOHA
❑ Under all loads the throughput S is just the offered
load, G, times the probability P0 of a transmission
succeeding:
𝑆 = 𝐺𝑃0

26

CS2008-Computer Networks
(Dr. V. K. Jain ) 13
 ALOHA (2) XP

Vulnerable period for the shaded frame.

27

Vulnerable time for pure ALOHA protocolXP

23 Dr Salman Ali
AlQahtani

28

CS2008-Computer Networks
(Dr. V. K. Jain ) 14
 Pure ALOHA XP

❑ The probability that k frames are generated during a

given frame time, in which G frames are expected, is
given by the Poison distribution:
𝐺 𝑘 𝑒 −𝐺
Pr[𝑘] =
𝑘!
−𝐺
❑ Probability of zero frames: 𝑒

❑ In an interval two frame times long, the mean

number of frames generated is 2G.
❑ Probability of no frames being initiated during the
entire vulnerable period is given by 𝑃0 = 𝑒 −2𝐺 .
❑ Using 𝑆 = 𝐺𝑃0

𝑆 = 𝐺𝑒 −2𝐺 .

29

Pure ALOHA XP

❑ The relation between the offered traffic and the

throughput is given in the next slide.
❑ The maximum throughput occurs at G=0.5
with S=1/2e which is about 0.184.
❑ The maximum utilization of the channel thus
is 18%.

30

CS2008-Computer Networks
(Dr. V. K. Jain ) 15
 ALOHA (3) XP

Throughput versus offered traffic for ALOHA systems.

31

Procedure for pure ALOHA protocol XP

21 Dr Salman Ali
AlQahtani

32

CS2008-Computer Networks
(Dr. V. K. Jain ) 16
 Pure ALOHA Example XP

Example 1 : A pure ALOHA network transmits 200-bit

frames on a shared channel of 200 kbps. What is the
requirement to make this frame collision-free?
Solution
Average frame transmission time Tfr is 200 bits/200
kbps or 1 ms.
The vulnerable time is 2×1 ms = 2 ms. This means no
station should send later than 1 ms before this
station starts transmission and no station should
start sending during the one 1-ms period that this
station is sending.

33

Pure ALOHA Example XP

25 Dr Salman Ali
AlQahtani
Example 2 : A pure ALOHA network transmits 200-bit frames
on a shared channel of 200 kbps. What is the throughput if
the system (all stations together) produces
a. 1000 frames per second. b. 500 frames per second c. 250
frames per second
Solution
The frame transmission time is 200/200 kbps or 1 ms.
a. If the system creates 1000 frames per second, this is 1
frame per millisecond. The load is 1. In this case S = G× e−2 G
or S = 0.135 (13.5 percent). This means that the throughput
is 1000 × 0.135 = 135 frames. Only 135 frames out of 1000
will probably survive.

34

CS2008-Computer Networks
(Dr. V. K. Jain ) 17
 Pure ALOHA Example XP
25 Dr Salman Ali
AlQahtani
Example 2: Solution
b. If the system creates 500 frames per second, this is 1/2 frame
per millisecond. The load is (1/2). In this case S = G× e−2 G or
S = 0.184 (18.4 percent). This means that the throughput is
500 × 0.184 = 92 frames and that only 92 frames out of 500
will probably survive. Note that this is the maximum
throughput case, percentagewise.

c. If the system creates 250 frames per second, this is 1/4 frame
per millisecond. The load is (1/4). In this case S = G× e−2 G or
S = 0.152 (15.2 percent). This means that the throughput is
250 × 0.152 = 38 frames and that only 38 frames out of 250
will probably survive.

35

Slotted ALOHA XP

❑ Roberts in 1972 doubled the capacity of

an ALOHA system.
❑ Divide time into discrete intervals called
slots.
❑ Each interval corresponds to one frame.

❑ Users will have to agree on slot boundaries.

❑ Synchronization is required:
❑ One special station emit a pip at the start of
each interval, like clock.

36

CS2008-Computer Networks
(Dr. V. K. Jain ) 18
 Slotted ALOHA XP

❑ A station is not permitted to send whenever

the user types a line.
❑ User waits for the beginning of the next slot.

❑ Continuous time ALOHA is turned into a

discrete time one.
❑ The probability of no other traffic during the
same slot as our test frame is then 𝑒 −𝐺 ,
which leads to:
𝑆 = 𝐺𝑒 −𝐺

37

Slotted ALOHA XP

Node 1
Packet Nodes 2 & 3
Packets
No Retransmission Retransmission
transmission

1 2 3 2 3
Time

Slot Collision

Collision mechanism in slotted ALOHA

38

CS2008-Computer Networks
(Dr. V. K. Jain ) 19
 Frames in a slotted ALOHA network XP
28 Dr Salman Ali
AlQahtani

39

XP
Vulnerable time for slotted ALOHA protocol
29 Dr Salman Ali
AlQahtani

40

CS2008-Computer Networks
(Dr. V. K. Jain ) 20
 Slotted ALOHA XP

❑ Slotted ALOHA
❑ peaks at the G = 1
❑ Throughput S = 1/e = 0.367 or 37%.

❑ The best case scenario:

❑ 37% of slots are empty
❑ 37% of successes, and

❑ 26% collisions.

41

Slotted ALOHA Example XP

Example 2 : A slotted ALOHA network transmits 200-bit frames

on a shared channel of 200 kbps. What is the throughput if
the system (all stations together) produces
a. 1000 frames per second. b. 500 frames per second c. 250
frames per second
Solution
The frame transmission time is 200/200 kbps or 1 ms.
a. If the system creates 1000 frames per second, this is 1
frame per millisecond. The load (G) is 1. In this case S =
G× e−G or S = 0.368 (36.8 percent).
This means that the throughput is 1000 × 0.368 = 368
frames. Only 368 frames out of 1000 will probably survive.

42

CS2008-Computer Networks
(Dr. V. K. Jain ) 21
 Slotted ALOHA Example XP
25 Dr Salman Ali
AlQahtani
Example 2: Solution
b. If the system creates 500 frames per second, this is 1/2 frame
per millisecond. The load is (1/2). In this case S = G× e−G or
S = 0. (18.4 percent). This means that the throughput is 500
× 0.184 = 92 frames and that only 92 frames out of 500 will
probably survive. Note that this is the maximum throughput
case, percentagewise.

c. If the system creates 250 frames per second, this is 1/4 frame
per millisecond. The load is (1/4). In this case S = G× e−G or
S = 0.195 (19.5 percent). This means that the throughput is
250 × 0.195 = 49 frames and that only 49 frames out of 250
will probably survive.

43

Pure ALOHA versus Sloted ALOHA XP

32 Dr Salman Ali
❑ ALOHA AlQahtani

❑ (p)ure-ALOHA : users transmit any time they desire.

❑ (s)lotted-ALOHA : users begin their transmission only at the beginning of a
slot

0.5
pure - ALOHA : S = Ge - 2 G
Vulnerable period
for slotted ALOHA slotted - ALOHA : S = Ge - G
0.4 0.368
Throughput
P P
S: Throughput

0.3
Slotted Aloha
Time 2P 0.184
0.2

Vulnerable period for pure Aloha

ALOHA 0.1

P= frame transmission time

00 2 4 6 8

G=gT

44

CS2008-Computer Networks
(Dr. V. K. Jain ) 22
 Carrier Sense Multiple Access Protocols XP
34 Dr Salman Ali
AlQahtani
❑ We have seen that maximum throughputs of
pure and slotted ALOHA protocols, are equal to
0.184 and 0.368, respectively.
❑ We need to find another way of improving
throughputs and supporting high-speed
communication networks.
❑ We could achieve better throughput if we can
prevent potential collision in a shared channel
by simply listening to the channel before
transmitting a packet.

45

Carrier Sense Multiple Access Protocols XP

❑ Protocols in which stations listen for a
carrier (i.e., transmission) and act
accordingly are called carrier sense
protocols.
❑ Several Versions of those protocols will be
discussed.
1. Persistent and Non-persistent CSMA
2. CSMA with Collision Detections

46

CS2008-Computer Networks
(Dr. V. K. Jain ) 23
 Carrier Sense Multiple Access(CSMA) Protocols
XP
34 Dr Salman Ali
❑ C SMA gives improved throughput comparedAlQahtani to Aloha
protocols
❑ C SMA protocols are based on the fact that each terminal on
the network is able to monitor the status of the channel before
transmitting information.
❑ Listens to the channel before transmitting a packet (avoid
avoidable collisions)
❑ I n CSMA, detection delay and propagation delay are
two important parameters.
❑ Detection delay is the time required for a terminal to sense whether or
not the channel is idle.
❑ Propagation delay is a relative measure of how fast it takes for a packet
to travel from a source station to a destination station.

47

Persistent and Non-persistent CSMA XP

❑ 1-Persistent Carrier Sense Multiple

Access (CSMA) protocol.
❑ When a station has data to be send it first
listens to the channel to see if anyone else is
transmitting at that moment.
❑ If the channel is idle the station sends the
data,
❑ Otherwise, the station just waits until it
becomes idle.

48

CS2008-Computer Networks
(Dr. V. K. Jain ) 24
 Persistent and Non-persistent CSMA XP

❑ 1-Persistent Carrier Sense Multiple Access

(CSMA) protocol.
❑ If a collision occurs, the station waits a random
amount of time and starts all over again.
❑ This protocol has problems with collisions:
➢ Two patiently waiting stations will start transmitting
at the same time when the channel becomes idle.
➢ Propagation delay can make even more subtle the
collision.

49

Persistent and Non-persistent CSMAXP

❑ 1-persistent refers to the probability of 1
of transmission when the channel found
to be idle.

50

CS2008-Computer Networks
(Dr. V. K. Jain ) 25
 Persistent and Non-persistent CSMAXP
❑ Non-persistent CSMA - In this protocol
the transmitting stations are less greedy.
❑ The transmitting station will send the packet if
the channel is found to be idle.
❑ However, if the channel is already in use the
station does not continuously sense it for
transmission. Instead it waits a random
amount of time and then repeats the
algorithm.

51

Collision Mechanism in Non-persistent CSMAXP

❑ Each MS can sense the transmission of all other

MSs, and the propagation delay is small as
compared with the transmission time.
❑ Following figure shows the collision process in
the Non-persistent CSMA protocol.
MS 1 Packet MS 5 sense
MS 2 Packet Delay for MS 5
MS 3 Packet

1 2 3 4 5 Time
Delay for MS 4 Collision

MS 4 senses

52

CS2008-Computer Networks
(Dr. V. K. Jain ) 26
 Persistent and Non-persistent CSMAXP
❑ P-persistent CSMA.
❑ The transmitting station will send the packet if
the channel is found to be idle with a
probability of p (q = 1-p; it defers that action
until the next slot).
❑ If the slot is still empty it does or not transmit
with the probability of p and q respectively.
❑ If the channel in use the station will treat this
as being a collision (waits random amount of
time)

53

Persistent and Non-persistent CSMAXP

Comparison of the channel utilization versus load for various

random access protocols.

54

CS2008-Computer Networks
(Dr. V. K. Jain ) 27
 CSMA/CD (CSMA with Collision Detection) XP

❑ Persistent and non-persistent CSMA protocols are

definitely an improvement over ALOHA because
they ensure that no station begins to transmit while
the channel is busy.
❑ However, if two stations sense the channel to be
idle and begin transmitting simultaneously, their
signals will still collide.
❑ Another improvement is for the stations to quickly
detect the collision and abruptly stop transmitting,
(rather than finishing them) since they are
irretrievably garbled anyway.
❑ This strategy saves time and bandwidth.

55

CSMA with Collision Detection XP

❑ Protocols that sense Collisions are known

as CSMA with Collision Detection
(CSMA/CD)
❑ This protocol is a basis of classical
Ethernet LAN.
❑ The transmitting station hardware must listen
to the channel while it is transmitting.
❑ If it is garbled up then it will know that
collision has occurred.

56

CS2008-Computer Networks
(Dr. V. K. Jain ) 28
 CSMA/CD (CSMA with Collision Detection) XP

❑ In CSMA, if two terminals begin sending packet at the same

time, each will transmit its complete packet (although collision
is taking place).
❑ Wasting medium for an entire packet time.
❑ CSMA/CD
Step 1: If the medium is idle, transmit
Step 2: If the medium is busy, continue to listen until the
channel is idle then transmit
Step 3: If a collision is detected during transmission, cease
transmitting
Step 4: Wait a random amount of time and repeats the same
algorithm

57

CSMA with Collision Detection XP

CSMA/CD can be in one of three states: contention,

transmission, or idle.

58

CS2008-Computer Networks
(Dr. V. K. Jain ) 29
 CSMA/CD (CSMA with Collision Detection) XP

❑ Suppose that two stations both begin transmitting at

exactly time t0.
❑ How long will it take them to realize that they have
collided?
❑ The minimum time to detect the collision is just the time it
takes the signal to propagate from one station to the other.
❑ Based on this information, you might think that a station
that has not heard a collision for a time equal to the full
cable propagation time after starting its transmission can
be sure it has seized the cable.
❑ By ‘‘seized,’’ we mean that all other stations know it is
transmitting and will not interfere.
❑ This conclusion is wrong.

59

CSMA/CD (Cont’d) XP

T0 A begins transmission
A B

T0+- B begins transmission

A B

T0+ B detects collision

A B

T0+2 - A detects collision just

before end of transmission
A B
Time
( is the propagation time)

60

CS2008-Computer Networks
(Dr. V. K. Jain ) 30
 CSMA/CD (CSMA with Collision Detection) XP

❑ In the worst case a station cannot be sure that it has

seized the channel until it has transmitted for 2 without
hearing a collision.
❑ With this understanding, we can think of CSMA/CD
contention as a slotted ALOHA system with a slot width of
2.
❑ The difference for CSMA/CD compared to slotted ALOHA
is that slots in which only one station transmits (i.e., in
which the channel is seized) are followed by the rest of a
frame.
❑ This difference will greatly improve performance if the
frame time is much longer than the propagation time.

61

XP
Collision-Free Protocols
❑ In CSMA/CD collisions do not occur once
the station has unambiguously captured
the channel, but they still occur during the
contention period.
❑ These collisions adversely affect the
system performance (e.g., bandwidth-
delay product is large – long cable that
has a large propagation delay  and
frames are short).

62

CS2008-Computer Networks
(Dr. V. K. Jain ) 31
 Collision-Free Protocols XP

❑ Collisions reduce the bandwidth

❑ This make the time to send a frame
variable.
❑ Bad fit for real-time traffic:
❑ VoIP
❑ Video,

❑ Teleconferencing, etc.

63

Collision-Free Protocols XP

❑ In the protocols to be described, we

assume that there are exactly N stations
❑ Each programmed with a unique
address: 0-(N-1).
❑ We also assume Propagation delay is
negligible.
❑ Question: Which station gets the channel
(e.g., the right to transmit) after a
successful transmission.

64

CS2008-Computer Networks
(Dr. V. K. Jain ) 32
 Basic Bit-Map Protocol XP

CSMA/CD can be in one of three states: contention,

transmission, or idle.

65

Basic Bit-Map Protocol XP

❑ Each contention period consists of exactly N slots.

❑ If station 0 has a frame to send, it transmits a 1 bit during
the slot 0.
❑ No other station is allowed transmit during this slot.
❑ Regardless what station 0 does, station 1 gets to
opportunity to transmit a 1 bit during slot 1, but only if it
has a frame queued.
❑ In general, station j may announce that it has a frame to
send by inserting a 1 bit into slot j.
❑ After all N slots have passed by, each station has
complete knowledge of which stations wish to transmit.
At which point they begin transmitting frames in
numerical order.

66

CS2008-Computer Networks
(Dr. V. K. Jain ) 33
 Collision-Free Protocols (1) XP

The basic bit-map protocol.

67

XP
Bit-Map Protocol
❑ Protocols that broadcast their intention before that
actually transmission are called reservation protocols.
❑ Low-load conditions:
❑ Average wait conditions for low-numbered stations:
➢ N/2 slots for current scan to finish, and
➢ N slots for the following scan to run to completion before it
may begin transmitting.
➢ 1.5N slots wait time.
❑ Average wait conditions for high-numbered stations:
➢ 0.5N slots wait time.
❑ Mean of all stations is N times.

68

CS2008-Computer Networks
(Dr. V. K. Jain ) 34
 Bit-Map Protocol XP

❑ Efficiency:
❑ Overhead bits N 𝑑
❑ Data bits d 𝑑+𝑁
❑ High-load
❑ N bit contention period is prorated over N frames,
yielding an overhead of only 1 bit per frame:
❑ Efficiency: 𝑑
𝑑+1
❑ Mean delay for a frame:
❑ Sum of the time it queues inside the station +

❑ (N-1) × d + N once it gets to the head of its internal

queue.

69

XP
Token Passing
❑ The essence of the bit-map protocol is that it lets every
station transmit a frame in turn in a predefined order.
❑ Another way to accomplish the same thing is to pass a
small message called token form one station to the next
in the same predefined order.
❑ The token represents permission to send.
❑ If a station has a frame queued for transmission when it
receives the token, it can send that frame before it passes
the token to the next station.
❑ If it has no queued frame, it simply passes the token.
❑ In a token ring protocol, the topology of the network is
used to define the order in which stations send.

70

CS2008-Computer Networks
(Dr. V. K. Jain ) 35
 Collision-Free Protocols (2) XP

❑ The stations are connected one to the next in a single ring.

❑ Each station is receiving the token in from one direction and
transmitting it out in the other direction.
❑ Frames are also transmitted in the direction of the token. .

Token
Station

Direction of
transmission

Token ring.

71

XP
Token Passing
❑ To stop the frame circulating indefinitely (like the
token), one has to pay attention to remove the frame
from the ring.
❑ Typically it will be removed by the receiving station
and/or sending station.
❑ We do not need a physical ring to implement token
passing.
❑ The channel connecting the stations might instead be a
single long bus.
❑ Token Ring or Token Bus protocols work the same
way.

72

CS2008-Computer Networks
(Dr. V. K. Jain ) 36
 XP
Token Passing
❑ The performance of token passing is similar to that of
the bit-map protocol, though the contention slots and
frames of one cycle are now intermingled.
❑ After sending a frame, each station must wait for all N
stations (including itself) to send the token to their
neighbors and the other N − 1 stations to send a frame,
if they have one.
❑ A subtle difference is that, since all positions in the
cycle are equivalent, there is no bias for low- or high-
numbered stations.

73

Binary Countdown XP

❑ A problem with the basic bit-map and token passing protocols is

the overhead of 1 bit per station.
❑ Large overhead for the network with large number of stations.

❑ A better solution is to use binary station addresses with a

channel that combines transmissions.
❑ A station wanting to use the channel now broadcasts its address
as a binary bit string, starting with the high-order bit. The
addresses are assumed to be the same length.
❑ The bits in each address position from different stations are.
❑ BOOLEAN OR-ed together by the channel when they are send at the same
time.
❑ Binary Countdown protocol
❑ It implicitly assumes that the transmission delays are negligible
so that all stations see asserted bits essentially instantaneously.

74

CS2008-Computer Networks
(Dr. V. K. Jain ) 37
 XP
Binary Countdown
❑ Arbitration rule: As soon as a station sees that a high-
ordered bit position that is 0 in its address has been
overwritten with 1 it gives up.
❑ Example:
❑ If stations 0010, 0100, 1001, and 1010 are all trying
to get the channel, in the first bit time the stations
transmit 0, 0, 1, and 1, respectively.
❑ They are OR-ed together to get 1.

❑ Stations 0010 and 0100 see the 1 and know that

higher-numbered stations is competing for the
channel and they give up for the current round.
❑ Stations 1001 and 1010 continue.

75

XP
Binary Countdown
❑ The next bit is 0 so both stations continue.
❑ The next bit is 1 so the station 1001 gives up and
station 1010 wins the bidding.
❑ This gives it a right to transmit the frame, after
which a new cycle starts.

76

CS2008-Computer Networks
(Dr. V. K. Jain ) 38
 Binary Countdown XP

The binary countdown protocol. A dash indicates silence.

77

Limited-Contention Protocols XP

❑ So far we have considered two basic strategies

for channel acquisition in a broadcast network:
❑ Contention (e.g., CSMA), and
❑ Collision free protocols.
❑ Each strategy can be rated as to how well it does
with respect to the two important performance
measures:
❑ Delay at low-loads, and
❑ Channel efficiency at high-loads.

78

CS2008-Computer Networks
(Dr. V. K. Jain ) 39
 XP
Limited-Contention Protocols
❑ Contention (Pure or Slotted ALOHA) protocols
are preferred under
❑ The low load conditions:
➢ Low delay and
➢ practically collision free.
❑ But, the high load conditions:
➢ High Delay due to High number of collisions or contentions

79

Limited-Contention Protocols XP

❑ Reverse is true for collision-free protocols

❑ The low load conditions:
➢ High delay and
❑ The high load conditions:
➢ Relatively low Delay due to which, Channel efficiency improves (fixed
overheads).
❑ Obviously, it would be nice if we could combine the best
properties of the contention and collision-free protocols,
arriving at a new protocol that used contention at low load
to provide low delay, but uses a collision-free technique at
high load to provide good channel efficiency.
❑ Such protocols, which we will call Limited-Contention
Protocols.

80

CS2008-Computer Networks
(Dr. V. K. Jain ) 40
 Limited-Contention Protocols XP

❑ Up to now, the only contention protocols we have studied

have been symmetric i.e., each station attempts to
acquire the channel with some probability, p, with all
stations using the same p.
❑ k – stations are contending for channel access.
❑ Each station has p – probability of transmission during
each slot.
❑ Probability that some station acquires a channel is its
probability p multiplied with all the remaining (k-1)
stations deferring with probability of (1-p):
𝑘𝑝 1 − 𝑝 𝑘−1

81

Limited-Contention Protocols XP

❑ Probability that any station acquires a channel is its

probability p multiplied with all the remaining (k-1)
stations deferring with probability of (1-p):
𝑘𝑝 1 − 𝑝 𝑘−1
❑ To find the optimal value of p, we differentiate with
respect to p, set the result to zero, and solve for p.
❑ Doing so, we find that the best value of p is 1/k.
Substituting p = 1/k, we get
𝑘−1 𝑘−1
❑ 𝑃𝑟 [𝑠𝑢𝑐𝑐𝑒𝑠𝑠 𝑤𝑖𝑡ℎ 𝑜𝑝𝑡𝑖𝑚𝑎𝑙 𝑝] = 𝑘
❑ This probability is displayed in the next slide.

82

CS2008-Computer Networks
(Dr. V. K. Jain ) 41
 Limited-Contention Protocols XP

Acquisition probability for a symmetric contention channel.

83

XP
Limited-Contention Protocols
❑ From the figure in previous slide it is fairly obvious that
probability that some stations will acquire the channel
can be increased only by decreasing the amount of
competition.
❑ The limited contention protocols do just that by:
1. Dividing the stations into (not necessarily disjoint) groups.
2. Only the members of group 0 are permitted to compete
for slot 0.
3. If one of them succeeds, it acquires the channel and
transmits its frame.
4. If there is a collision the members of the group 1 contend
for slot 1. etc.

84

CS2008-Computer Networks
(Dr. V. K. Jain ) 42
 Limited-Contention Protocols XP

❑ By making an appropriate division of stations into groups

the amount of contention for each slot can be reduced,
thus operating each slot near the left of the figure
presented in previous slide.
❑ The trick is how to assign stations to slots? Before Looking
at the general case, let us consider some special case:
❑ At one extreme, suppose each group has utmost one
member. Such assignment guarantees that there will never
be collisions because at most one station is contending for
any given slots (binary countdown protocol)
❑ The next case is to assign two stations per group. The
probability that both will try to transmit during a slot is p,2
which for a small p is negligible.

85

XP
Limited-Contention Protocols
❑ If more stations are assigned to the same slot, the
probability of a collision grows, but the length of the
bit-map needed to give everyone a chance shrinks.
❑ The limiting case is a single group containing all
stations (i.e., slotted ALOHA).
❑ We need a way to assign station slots dynamically:
➢ Many stations per slot when the load is low, and
➢ Few (or just one) station per slot when the load is high.

86

CS2008-Computer Networks
(Dr. V. K. Jain ) 43
 The Adaptive Tree Walk Protocol XP
❑ One particularly simple way of performing the
necessary assignment is to use the algorithm devised
by the U.S. Army for testing soldiers for syphilis during
World War II (Dorfman, 1943) :
❑ Blood samples from N soldiers

❑ A portion of each sample was poured into a single

test tube.
❑ This mixed sample was testing:
➢ If none of antibodies were found all the soldiers in the group
were declared healthy.
➢ Binary search was performed to pick which soldier was
infected.

87

The Adaptive Tree Walk Protocol XP

The tree for eight stations

88

CS2008-Computer Networks
(Dr. V. K. Jain ) 44
 The Adaptive Tree Walk Protocol XP
❑ In the first contention slot following the successful
transmission, slot 0, all stations were permitted to try to
acquire the channel.
❑ If there is a collision then during slot 1 only those
stations falling under node 2 in the tree (previous slide)
may compete.
❑ If one of them acquires the channel the slot following
the frame (i.e., slot 2 ) is reserved for those stations
under node 3.
❑ If on the other hand two or more stations under node 2
want to transmit, there will be a collision during slot 1, in
which case it is node 4’s turn during slot 2.

89

The Adaptive Tree Walk Protocol XP

❑ Depth first search of the tree to locate all ready stations
if the collision occurs during slot 0.
❑ Each bit slot is associated with some particular node in
the tree.
❑ If collision occurs the search continues recursively with
the node’s left and right children.
❑ If a bit slot is idle or if only one station transmits in it.
The searching of its node can stop because all ready
stations have been located.

90

CS2008-Computer Networks
(Dr. V. K. Jain ) 45
 The Adaptive Tree Walk Protocol XP
❑ When a load on the system is high it is
not worth to dedicate slot 0 to node 1.
❑ Similarly one would argue that nodes 2
and 3 should be skipped.
❑ In general the question is at what level in
the tree should we began the search?
❑ Heavier load the farther down the tree the
search should begin.

91

The Adaptive Tree Walk Protocol XP

❑ We will assume that each station has a
pretty good idea of the number of ready
stations q, (from monitoring traffic).
❑ Numbering the levels:
❑ Level 0: Node 1
❑ Level 1: Nodes 2, 3

❑ Level 2: Nodes 4,5,6 and 7. etc.

92

CS2008-Computer Networks
(Dr. V. K. Jain ) 46
 The Adaptive Tree Walk Protocol XP
❑ If the q ready stations are uniformly
distributed.
❑ Expected number of the stations below a
specific node at level i is just 2-iq
❑ Optimal number of contending station per
slot should be 1 and hence 2-iq = 1.
❑ Solving this equation, we find:
𝑖 = 𝑙𝑜𝑔2 𝑞

93

The Adaptive Tree Walk Protocol XP

The tree for eight stations

94

CS2008-Computer Networks
(Dr. V. K. Jain ) 47
 The Adaptive Tree Walk Protocol XP
❑ Numerous improvements to the basic algorithm have
been discovered by Bertsekas and Gallager (1992).
❑ For example, consider the case of stations G and H
being the only ones wanting to transmit.
❑ At node 1 a collision will occur, so 2 will be tried and
discovered idle.
❑ It is pointless to probe node 3 since it is guaranteed to
have a collision (we know that two or more stations
under 1 are ready and none of them are under 2, so
they must all be under 3).
❑ The probe of 3 can be skipped and 6 tried next. When
this probe also turns up nothing, 7 can be skipped and
node G tried next.

95

XP
Wireless LAN Protocols
❑ A system of laptop computers that
communicate by radio – wireless LAN.
❑ It also has somewhat different properties
than a wired LAN.
❑ Leads to different MAC protocols.

96

CS2008-Computer Networks
(Dr. V. K. Jain ) 48
 XP
Wireless LAN Protocols
❑ Common configuration of wireless
LAN:
❑ Office Building with Access Points (APs)
❑ APs Strategically placed

❑ APs are wired together (copper or fiber)

❑ APs provide connectivity

97

Wireless LAN Protocols XP

❑ Transmission power of APs and laptops is

adjusted to have a range of tens of meters,
nearby rooms become like a single cell and
the entire building becomes like the cellular
telephony system.
❑ But, each cell has only one channel.

❑ This channel is shared by all the stations in

the cell, including APs.
❑ Bandwidth provided – up to 600 Mbps.

98

CS2008-Computer Networks
(Dr. V. K. Jain ) 49
 Wireless LAN Protocols XP

❑ Wireless system can not normally detect

a collision while it is occurring.
❑ The received signal is weak (millions
times fainter than the signal that is being
transmitted)
❑ Difficulty in finding collision.

❑ Instead ACK are used to discover

collisions and other errors after the fact.

99

XP
Wireless LAN Protocols
❑ Additional, and even more important,
difference between wireless LAN and
wired LAN:
❑ Wireless LAN: A station may not be able to
transmit or receive frames to or from all other
stations due to limited radio range.
❑ Wired LAN: Once the one station sends a
frame, all other stations receive it.

100

CS2008-Computer Networks
(Dr. V. K. Jain ) 50
 Wireless LAN Protocols XP

❑ Simplifying assumptions:
❑ Each radio transmitter has some fixed range.
❑ Its range is represented by an ideal circular
coverage region
❑ within that region station can sense and
receive the station’s transmission.

101

Wireless LAN Protocols XP

❑ Naïve approach:
❑ Use CSMA:
➢Just listen for other transmissions.
➢If none is doing it then transmit.
❑ Problem:
➢What matters for reception is interference at the
receiver and not at the sender.

❑ Consider the figure in next slide:

102

CS2008-Computer Networks
(Dr. V. K. Jain ) 51
 Wireless LAN Protocols (1) XP

A wireless LAN. (a) A and C are hidden terminals

when transmitting to B.
❑ The problem of a station not being able to detect a potential
competitor for the medium because the competitor is too far
away is called the hidden terminal problem.

103

Wireless LAN Protocols (2) XP

A wireless LAN. (b) B and C are exposed terminals when transmitting to

A and D.
❑ The problem of a station to falsely conclude that it may not send and
deferred the transmission is called the exposed terminals problem.

104

CS2008-Computer Networks
(Dr. V. K. Jain ) 52
 Wireless LAN Protocols XP

❑ Before starting the transmission a station must know

whether there is radio activity around the receiver.
❑ CSMA merely tells it whether there is activity near the
transmitter by sensing the carrier.
❑ With wired communication all signals propagate to
all stations so this distinction does not exist.
❑ However only one transmission can take place at
one time.

105

Wireless LAN Protocols XP

❑ In a system based on short-range radio waves multiple

transmissions can occur simultaneously:
❑ If they all have different destinations, and

❑ These destinations are out of range of one another.

❑ Multiple Access with Collision Avoidance (MACA) -

Early protocol that tackles these problems for wireless
LAN’s.
❑ The basic idea behind it is for the sender to stimulate
the receiver into outputting a short frame
❑ Nearby stations can detect this transmission and
avoid transmitting for the duration of the upcoming
(larger) data frame.

106

CS2008-Computer Networks
(Dr. V. K. Jain ) 53
 Wireless LAN Protocols XP

❑ MACA is illustrated in the next slide.

❑ A sends a frame to B – A initiates the request by
sending an Request To Send (RTS) to station B.
➢ Short frame (30 bytes) that contains the length of data frame
that will eventually follow.
❑ B replies with a Clear To Send (CTS) frame.
➢ This frame contains the data length (copied from RTS).
❑ After reception of the CTS frame the station A begins
transmission.

108

Wireless LAN Protocols (3) XP

The MACA protocol. (a) A sending an RTS to B. (b) B

responding with a CTS to A.

109

CS2008-Computer Networks
(Dr. V. K. Jain ) 54
 Wireless LAN Protocols XP

❑ Any station hearing the RTS is clearly close to

A and must remain silent long enough for the
CTS to be transmitted back to A without
conflict.
❑ Any stations hearing CTS are clearly close to B
and must remain silent during the upcoming
data transmission, whole length it can tell by
examining the CTS frame.
❑ Still collisions are possible.

110

RTS/CTS handshake… XP

111

CS2008-Computer Networks
(Dr. V. K. Jain ) 55
 RTS/CTS failure… XP

112

RTS/CTS failure…2 XP

113

CS2008-Computer Networks
(Dr. V. K. Jain ) 56