Chapter 4

The Medium Access Control

Sublayer

11/17/2021 CS522 Tanenbaum 1

 The Channel Allocation Problem

• Static Channel Allocation in LANs and MANs

• Dynamic Channel Allocation in LANs and MANs

11/17/2021 CS522 Tanenbaum 2

Dynamic Channel Allocation in LANs and MANs

1. Station Model.

2. Single Channel Assumption.

3. Collision Assumption.

4. (a) Continuous Time.

(b) Slotted Time.

5. (a) Carrier Sense.

(b) No Carrier Sense.

11/17/2021 CS522 Tanenbaum 3

 Multiple Access Protocols

• ALOHA
• Carrier Sense Multiple Access Protocols
• Collision-Free Protocols
• Limited-Contention Protocols
• Wavelength Division Multiple Access Protocols
• Wireless LAN Protocols

11/17/2021 CS522 Tanenbaum 4

 Pure ALOHA

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

11/17/2021 CS522 Tanenbaum 5
 Pure ALOHA (2)

Vulnerable period for the shaded frame.

11/17/2021 CS522 Tanenbaum 6
 Pure ALOHA (3)
A station transmits a frame whenever it has data to send. When the frame collides with other
frame(s), retransmit it by waiting a random amount of time.
What is the throughput (or efficiency) of an ALOHA channel?
Let N (no. of stations using an ALOHA channel) = ∞ ,
assume infinite population, new arrival is a Poisson process,
λn = mean new frame arrival rate (frame/sec),
µ = channel capacity (frame/sec), T=1/ µ=frame time (sec/frame)
S = λn/µ= λn (frame/sec). 1/µ (sec/frame)
= mean new frames per frame time, S is traffic density or channel utilization,
λr = mean retransmitted frame rate.
The combined traffic of new and old (retransmission) traffic is still a Poisson
process with G= mean departure frames per frame time=(λn+λr)/µ=λT.
G is actual traffic density.
G can be controlled by adjusting retransmission time. Can S be controlled?
What is the system throughput? S or G?
Analysis:
• If S>1, almost every frame will collide.
• For reasonable throughput, 0<S<1. G > S.
• At low load, S ≈ 0 → G ≈ S.
• At high load, G>S.

11/17/2021 CS522 Tanenbaum 7

 Pure ALOHA (4)
• What is the relationship between G and S? S = GP0
P0 = the probability that a frame does not suffer a collision.
• How to find P0?
Note that the combined frame traffic is a Poisson process, therefore,
Pr[k] = the probability that k frames are generated during a frame time T
= (  T )  T
k
(λ=λn+λr, T=1/µ → λT=G substitute λT with G )
e
k!
(G ) k G
= e
k!
• But observe Figure 4-2, the vulnerable period of a frame is 2 frame time.
• Pr’[k] = (T’=2T, λT’=2G)
(2G ) k 2G 2 G
• P0 = Pr’[0] = . e S  GP 0  Ge
k!
• Observation:
S depends on incoming traffic.
G depends on S. For each S, there are two G values in Figure 4-3.

11/17/2021 CS522 Tanenbaum 8

What is the max. throughput of Pure
ALOHA?
How to control G to get maximum S? d ( f  g )  df  g  f  dg
dS d (Ge 2G )
  e 2G  (2)e  2G G  e 2G (1  2G )
dG dG
dS 1 1
Let 0 G  , Smax =  0.184
dG 2 2e
The best we can hope for the channel utilization is 18.4%.
Is 18.4% channel utilization for the ALOHA system too low?
For a terminal user sends 60 character/msg every 2 min.,
input rate is 0.5 char/sec = 5 bits/sec (assume 10 bit async.
transmission)
For 4800 bps channel and 10% utilization, it can support 96
interactive users.
For bursty, interactive traffic, pure ALOHA is sufficient and
simple.
11/17/2021 CS522 Tanenbaum 9
 Slotted ALOHA
Transmission time is divided into slots. Stations with data
to transmit will wait until the starting time of a slot. Time
of vulnerable period is reduced to 1 frame (slot) time.
(Require synchronization devices, e.g., a central station
broadcasts the clock signal to all stations for
synchronizing the slots.)
(G ) k G
Pr[k] = k! e
P0 = Pr[0] = e-G
S=GP0=Ge–G.
dS d (Ge G )
  e G  (1)e G G  e G (1  G )
dG dG
1
Let dS
 0  G 1 , Smax =  0.368
dG e
11/17/2021 CS522 Tanenbaum 10
PURE ALOHA vs. Slotted ALOHA

Throughput versus offered traffic for ALOHA systems.

11/17/2021 CS522 Tanenbaum 11
 Carrier Sense MA protocols
Protocols in which stations listen for a carrier (i.e. a transmission medium) and act
accordingly, e.g. MA protocols used by LANs.
1-Persistent CSMA
When a station has data to send, it listens to the channel.
If the channel is busy, it waits until channel idle.
When the channel is idle, it transmits a frame (with probability = 1).
Propagation delay effect:
At t0, station 1 detects idle and sends a frame.
At t0+τ−ε, station 2 detects idle and sends a frame.2
At t0+τ, station 2 detects collision.

11/17/2021 CS522 Tanenbaum 12

 Carrier Sense MA Protocols(2)
At t0+τ−ε+τ, station 1 detects collision.
In worst case, only about 2τ time later can station 1 detect the collision.
The longer the cable, the longer stations have to wait to be sure that there is
no collision.

Non-persistent CSMA
• If the channel is busy, it waits for random period then sense the channel
again.
• Better channel utilization but longer delays than 1-persistent CSMA.
p-persistent CSMA (applies to slotted channel)
• If the channel is idle, it transmits with prob = p (with 1-p, it defers until
next slot).
• If the next slot is idle again, do the same thing.

11/17/2021 CS522 Tanenbaum 13

Persistent and Nonpersistent CSMA

Comparison of the channel utilization versus load for various random access
protocols. Smaller p has better throughput but at what cost?
11/17/2021 CS522 Tanenbaum 14
 CSMA with Collision Detection

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

transmission, or idle.
11/17/2021 CS522 Tanenbaum 15
 The collision free protocols are of three
type and they are as follows −
•Bit map protocol
•Token passing
•Binary countdown

11/17/2021 CS522 Tanenbaum 16

 Collision-Free Protocols

The basic bit-map protocol.

11/17/2021 CS522 Tanenbaum 17
 The binary countdown protocol
Step 1 − A problem with the bit map protocol and token passing
is that overhead is 1 bit per station, so bitmap and token passing
will not suit the networks with thousands of stations.
Step 2 − A station wants to use the channel. It has to broadcast
its address as a binary bit string starting with a high order bit.
Step 3 − All addresses are assumed to be the same length.
Step 4 − The bits in each address position from different stations
are Boolean OR together by the channel when they are sent at
same time. WE will call this type of protocol binary countdown.
Step 5 − It implicitly assumes that the transmission delays are
negligible so that all stations instantaneously see the asserted
bits.
Step 6 − To avoid conflicts an arbitration rule must be applied,
whenever a station sees that the high order bit position that is 0
in address has been overwritten with 1 and it gives up.
Step 7 − After winning the bidding a station now transmits a
frame after which another bidding cycle starts.
Step 8 − It has the property that higher numbered stations have
higher priority than the lower numbered stations, either it may be
good or bad depending on context.
The binary countdown protocol, dashes indicate silence.

11/17/2021 CS522 Tanenbaum 18

 Collision-Free Protocols (2)

The binary countdown protocol. A dash indicates silence.

11/17/2021 CS522 Tanenbaum 19
 Limited-Contention Protocols

Acquisition probability for a symmetric contention channel.

11/17/2021 CS522 Tanenbaum 20
 Adaptive Tree Walk Protocol
In adaptive tree walk protocol, the stations or nodes are arranged in the form of a binary tree as
shown in the diagram. Here, the internal nodes (marked from 0 to 7) represent the groups while
the leaf nodes (marked A to H) are the stations contending for network access.

Under light loads, all the stations can

participate for contention each slot like
ALOHA. However, under heavy loads, only a
group can try for a given slot.

The tree for eight stations.

11/17/2021 CS522 Tanenbaum 21
Wavelength Division Multiple Access Protocols

Wavelength division multiple access.

11/17/2021 CS522 Tanenbaum 22
 Wireless LAN Protocols

A wireless LAN. (a) A transmitting. (b) B transmitting.

11/17/2021 CS522 Tanenbaum 23

 Wireless LAN Protocols (2)

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

(b) B responding with a CTS to A.
11/17/2021 CS522 Tanenbaum 24
 Ethernet
• Ethernet Cabling
• Manchester Encoding
• The Ethernet MAC Sublayer Protocol
• The Binary Exponential Backoff Algorithm
• Ethernet Performance
• Switched Ethernet
• Fast Ethernet
• Gigabit Ethernet
• IEEE 802.2: Logical Link Control
• Retrospective on Ethernet
11/17/2021 CS522 Tanenbaum 25
 Ethernet Cabling

The most common kinds of Ethernet cabling.

11/17/2021 CS522 Tanenbaum 26
 Ethernet Cabling (2)

Three kinds of Ethernet cabling.

11/17/2021 (a) 10Base5, (b) 10Base2,
CS522 Tanenbaum (c) 10Base-T. 27
 Ethernet Cabling (3)

Cable topologies. (a) Linear, (b) Spine, (c) Tree, (d) Segmented.
11/17/2021 CS522 Tanenbaum 28
 Ethernet Cabling (4)

(a) Binary encoding, (b) Manchester encoding,

11/17/2021 (c) Differential Manchester encoding.
CS522 Tanenbaum 29
Ethernet MAC Sublayer Protocol

Frame formats. (a) DIX Ethernet, (b) IEEE 802.3.

11/17/2021 CS522 Tanenbaum 30
Ethernet MAC Sublayer Protocol (2)

Collision detection can take as long as 2 .

11/17/2021 CS522 Tanenbaum 31
 Ethernet Performance

Efficiency of Ethernet at 10 Mbps with 512-bit slot times.

11/17/2021 CS522 Tanenbaum 32
 Switched Ethernet

A simple example of switched Ethernet.

11/17/2021 CS522 Tanenbaum 33
 Fast Ethernet

The original fast Ethernet cabling.

11/17/2021 CS522 Tanenbaum 34
 Gigabit Ethernet

(a) A two-station Ethernet. (b) A multistation Ethernet.

11/17/2021 CS522 Tanenbaum 35
 Gigabit Ethernet (2)

Gigabit Ethernet cabling.

11/17/2021 CS522 Tanenbaum 36
IEEE 802.2: Logical Link Control

(a) Position of LLC. (b) Protocol formats.

11/17/2021 CS522 Tanenbaum 37
 Wireless LANs

• The 802.11 Protocol Stack

• The 802.11 Physical Layer
• The 802.11 MAC Sublayer Protocol
• The 802.11 Frame Structure
• Services

11/17/2021 CS522 Tanenbaum 38

 The 802.11 Protocol Stack

Part of the 802.11 protocol stack.

11/17/2021 CS522 Tanenbaum 39
The 802.11 MAC Sublayer Protocol

(a) The hidden station problem.

11/17/2021 (b) The exposed station problem.
CS522 Tanenbaum 40
The 802.11 MAC Sublayer Protocol (2)

The use of virtual channel sensing using CSMA/CA.

11/17/2021 CS522 Tanenbaum 41
The 802.11 MAC Sublayer Protocol (3)

A fragment burst.
11/17/2021 CS522 Tanenbaum 42
The 802.11 MAC Sublayer Protocol (4)

Interframe spacing in 802.11.

11/17/2021 CS522 Tanenbaum 43
 The 802.11 Frame Structure

The 802.11 data frame.

11/17/2021 CS522 Tanenbaum 44
 802.11 Services

Distribution Services

• Association
• Disassociation
• Reassociation
• Distribution
• Integration
11/17/2021 CS522 Tanenbaum 45
 802.11 Services

Intracell Services
• Authentication
• Deauthentication
• Privacy
• Data Delivery

11/17/2021 CS522 Tanenbaum 46

 Broadband Wireless

• Comparison of 802.11 and 802.16

• The 802.16 Protocol Stack
• The 802.16 Physical Layer
• The 802.16 MAC Sublayer Protocol
• The 802.16 Frame Structure

11/17/2021 CS522 Tanenbaum 47

 The 802.16 Protocol Stack

The 802.16 Protocol Stack.

11/17/2021 CS522 Tanenbaum 48
 The 802.16 Physical Layer

The 802.16 transmission environment.

11/17/2021 CS522 Tanenbaum 49
 The 802.16 Physical Layer (2)

Frames and time slots for time division duplexing.

11/17/2021 CS522 Tanenbaum 50
The 802.16 MAC Sublayer Protocol

Service Classes
• Constant bit rate service
• Real-time variable bit rate service
• Non-real-time variable bit rate service
• Best efforts service

11/17/2021 CS522 Tanenbaum 51

 The 802.16 Frame Structure

(a) A generic frame. (b) A bandwidth request frame.

11/17/2021 CS522 Tanenbaum 52
 Bluetooth

• Bluetooth Architecture
• Bluetooth Applications
• The Bluetooth Protocol Stack
• The Bluetooth Radio Layer
• The Bluetooth Baseband Layer
• The Bluetooth L2CAP Layer
• The Bluetooth Frame Structure

11/17/2021 CS522 Tanenbaum 53

 Bluetooth Architecture

Two piconets can be connected to form a scatternet.

11/17/2021 CS522 Tanenbaum 54
 Bluetooth Applications

The Bluetooth profiles.

11/17/2021 CS522 Tanenbaum 55
 The Bluetooth Protocol Stack

The 802.15 version of the Bluetooth protocol architecture.

11/17/2021 CS522 Tanenbaum 56
 The Bluetooth Frame Structure

A typical Bluetooth data frame.

11/17/2021 CS522 Tanenbaum 57
 Data Link Layer Switching

• Bridges from 802.x to 802.y

• Local Internetworking
• Spanning Tree Bridges
• Remote Bridges
• Repeaters, Hubs, Bridges, Switches, Routers, Gateways
• Virtual LANs

11/17/2021 CS522 Tanenbaum 58

 Data Link Layer Switching

Multiple LANs connected by a backbone to handle a total load higher

11/17/2021 than the capacity of a single LAN.
CS522 Tanenbaum 59
 Bridges from 802.x to 802.y

Operation of a LAN bridge from 802.11 to 802.3.

11/17/2021 CS522 Tanenbaum 60
 Bridges from 802.x to 802.y (2)

The IEEE 802 frame formats. The drawing is not to scale.

11/17/2021 CS522 Tanenbaum 61
 Local Internetworking

A configuration with four LANs and two bridges.

11/17/2021 CS522 Tanenbaum 62
 Spanning Tree Bridges

Two parallel transparent bridges.

11/17/2021 CS522 Tanenbaum 63
 Spanning Tree Bridges (2)

(a) Interconnected LANs. (b) A spanning tree covering the

LANs. The dotted lines are not part of the spanning tree.
11/17/2021 CS522 Tanenbaum 64
 Remote Bridges

Remote bridges can be used to interconnect distant LANs.

11/17/2021 CS522 Tanenbaum 65
 Repeaters, Hubs, Bridges, Switches,
Routers and Gateways

(a) Which device is in which layer.

(b) Frames, packets, and headers.
11/17/2021 CS522 Tanenbaum 66
 Repeaters, Hubs, Bridges, Switches,
Routers and Gateways (2)

(a) A hub. (b) A bridge. (c) a switch.

11/17/2021 CS522 Tanenbaum 67
 Virtual LANs

A building with centralized wiring using hubs and a switch.

11/17/2021 CS522 Tanenbaum 68
 Virtual LANs (2)

(a) Four physical LANs organized into two VLANs, gray and white,
by two bridges. (b) The same 15 machines organized into two
VLANs
11/17/2021
by switches. CS522 Tanenbaum 69
 The IEEE 802.1Q Standard

Transition from legacy Ethernet to VLAN-aware Ethernet. The shaded

11/17/2021 symbols are VLAN aware.
CS522 The empty ones are not. 70
Tanenbaum
 The IEEE 802.1Q Standard (2)

The 802.3 (legacy) and 802.1Q Ethernet frame formats.

11/17/2021 CS522 Tanenbaum 71
 Summary

11/17/2021
Channel allocation methodsCS522
andTanenbaum 72
systems for a common channel.