Advance Computer Networks (Lecture 02)

2. Advanced Medium Access Control Protocols

 2.1 Traditional CSMA/CD
 2.2 The 802.11 MAC Protocol for Wireless LANs


What is a LAN?

Let collisions take place, detect them, repeat the transmission.

When the station finds the medium idle it transmits immediately. When it finds the medium busy it waits for the end of the other transmission and then starts its own transmission immediately (transmission probability = 1).

When the station finds the medium idle it transmits immediately. When the station finds the medium busy it stops sensing, waits a random exponential back off time and then starts a new transmission attempt.

to communicate directly with each other, without connection to a wired network.The stations do not have a “forwar-ding” functionality. The IBSS only permits one-hop communication 

(1-hop ad-hoc mode).
(1-hop ad-hoc mode). (1-hop ad-hoc mode). (1-hop ad-hoc mode).

 In wireless communication new problems arise because the physical layer operates differently from cable-based physical layers. For example, unlike in an Ethernet segment, not every station can hear every other station directly. In particular: from “A hears B” and “B hears C” we cannot always conclude that “A hears C”! A cannot sense if C is sending, and vice versa.

The Problem of the “Hidden Terminal”

A and C both want to send to B.

A senses the medium and notices that it is free. A begins to send.

At the same time, C senses the medium and sees that it is free (the signal of A does not reach C). C also begins to send.

The signals collide in B, B receives none of the two messages correctly.

Neither A nor C can determine the collision since they do not hear each other.

  •  Another reason why CSMA/CD will not work is that wireless cards cannot send and receive at the same time.

 We conclude: CSMA/CD will not work in wireless networks! IEEE 802.11 MAC (1)

DFWMAC: Distributed Foundation Wireless Medium Access Control 

 Three variants are standardized:

DFWMAC-DCF CSMA/CA (mandatory in all WLANs)

Distributed Coordination Function – Carrier Sensing Multiple Access with Collision Avoidance 

“listen before talk

Reduction of collisions whenbusyby a random backoff timer

Acknowledgment of receipt through an ACK (in unicast mode only)

The problem of thehidden terminal” is not solved!

DFWMAC-DCF with RTS/CTS (optional)

Basic function like DFWMAC-DCF CSMA/CA

In addition, avoidance of the hidden terminal problem by a Request-to-Send / Clear-to-Send mechanism (RTS/CTS). IEEE 802.11 MAC (2)
DFWMAC-PCF (optional)

PCF = Point Coordination Function 

collision-free, centralized access control procedure for services with time guarantees 

Basic idea: the access point polls the stations in a round-robin fashion Priorities by Three Waiting Periods (1)
SIFS (Short Inter-Frame Spacing)

Highest priority, for ACK, CTS, answer to polling


Intermediate priority, for time-guaranteed services by the PCF (Point Coordination Function). The access point waits the PIFS time before using the medium for control purposes (in particular for polling). 


Lowest priority, for asynchronous (best effort) data services
  Priorities by Three Waiting Periods (2)


“Listen-before-talk”: stations ready to send sense the medium (carrier sensing).

If the medium is free for the duration of an appropriate Inter-Frame Spacing (IFS), the station sends immediately. 

If the medium is busy, the station waits a DIFS and then waits for an additional random back-off time in order to reduce the probability of a collision.

Note: Collisions are still possible, although not very probable. Acknowledgements (Uni cast Case)

 Problem: Collision detection to recognize a successful transmission on the sender side (like in the Ethernet) does not work! Therefore explicit acknowledgments are needed. If the sender does not receive an acknowledgment, a re transmission takes place in the MAC layer! 


 Optional. Only available for unicast transmission. Usually not advisable for short packets. Basically a method by which the receiver informs all stations in his radio range to shut up for an upcoming transmission. Solves the hidden terminal problem.

 Extension of the access procedure by a Network Allocation Vector NAV for the reservation of future slots for the same pair of transmitter and receiver.

 RTS = Request To Send, CTS = Clear To Send. 

IEEE 802.11 - Frame Structure

Control Frame, Management Frame, Data Frame

important for detecting duplicate packets after lost ACKs

Receiver, transmitter (physical), BSS identifier, transmitter (logical)

 What happens when a station moves and the radio link gets weak or is lost? 


Scanning of the environment (listen for beacons of APs or send a probe into the medium and wait for an answer). 

 Reassociation Request

Contains information about the past AP and asks for a new association.

 Reassociation Response

Success: i.e., an AP answers, the station is physically connected again 

Failure: continue to scan 

 AP accepts Re association Request

Registration of the new station with the distribution system 

The old AP is informed by the distribution system to release the connection to this stationPHY: Why 2.4 GHz? Unlicensed ISM band (Industrial, Scientific, Medical)
 Advantage: usage free of charge, no permission required 

 Problem: non-exclusive use (e.g., garage door openers and microwave ovens work at 2.4 GHz) = > a very noisy frequency band
 Solution: use spread-spectrum technology. Mandatory in the US.

 Frequency ranges and wavelengths:

Frequency Hopping Spread Spectrum (1)

 Several channels from the entire frequency band are used in parallel. Senders and receivers rapidly jump between the channels in an agreed sequence. In this way, narrow-band noise has less effect. 

Frequency Hopping Spread Spectrum (2)

Frequencies in the 2.4 GHz Band

Frequencies in the 5 GHz Band

Example of a Bridge between Three LANs

Spanning Trees

 In order to make the interconnection of LANs more reliable, there are often several interconnection points (bridges) between them. In order to avoid the cycling of frames in such a network, the bridges must agree on a spanning tree for the graph. This is done with a spanning tree protocol (not discussed in detail here).

 A LAN (Local Area Network) is a network for the transmission of data between independent peer stations.
 It is usually under the legal control of a single user (single enterprise) and is usually limited to the user‘s premises.
  Characteristics of a Local Area Network

High transmission speed (10 - 1000 MBit/s)
Easy, inexpensive connection of stations
No need to take Telecom rules and regulations into account
Different types of devices can be connected easily:
personal computers
mobile phones
department servers/file servers/mail servers
printers and other peripheral devices.
Interconnection to Wide-Area Networks (WANs) is possible via routers (layer 3).

  LANs in the ISO Reference Model

Medium Access Control

broadcast medium
independent stations
   => send collisions will occur
 Solution: Medium Access Control
 Two allocation principles:
collision detection
collision avoidance
Use a circulating token to control the access to the medium.
2.1 Traditional CSMA/CD (Ethernet)
   CSMA/CD = Carrier Sensing with Multiple Access and Collision Detection
   Topology: Bus 

Bi-directional data flow
Bus interruption => network failure

CSMA/CD Basic Assumptions and Principles

All stations can hear each other on the medium.
 Carrier Sensing, Multiple Access (CSMA)
 (also called "listen before talk")
 A station that wants to send senses the medium:
If the medium is occupied, sending is postponed.
If the medium is free, sending begins immediately.

 CSMA/CD Retry Strategies (1)

 What will a station do exactly when it wants to transmit?

1-persistent CSMA
non-persistent CSMA
 Non-persistent CSMA leads to a better channel utilization when the chan-nel is busy, but also to longer delays for retry messages.
Random Exponential Backoff Time

 A random exponential backoff time is defined as follows:

 A station picks a value k from a list of exponential ones (k = 0,1,2,4,8,…,2m-1) at random where m = min(n,10) and n is the number of unsuccessful attempts, and waits k*512 bit times.
 The reason for this is that a station does not know how many stations it is competing with; it should wait longer if it has tried unsuccessfully several times already.


 If two or more stations begin to send at the same time, a collision occurs.
 Note: There is an increased danger of collisions when another transmission is ending: All stations who’s wish to send arose during the other transmission are “synchronized” to the end of this other transmission.
 Therefore, stations involved in a collision will wait a random time interval be-fore re-trying to send.

CSMA/CD: Protocol (1)

CSMA/CD: Protocol (2)

CSMA/CD – Frame Format

Preamble = 7 Bytes, 7 x ‘10101010’….alternating 0,1…Provide synchronization
SFD = Starting Frame Delimiter (1 Byte, contains ‘10101011’)…beginning of frame
DA = Destination Address (6 Bytes)…physical address of destination
SA = Source Address (6 Bytes)….physical address of source
Info = n bytes of data
FCS = Frame Check Sequence (32-bit CRC)….error correction code
Physical Mediums Used by Ethernet

Hubs and LAN Switching

 In the early Ethernet years the Ethernet cables were actually installed in a physical bus topology.
 The bus topology turned out to be impractical for locating faults, connecting new stations, etc.
 Today Ethernet hubs with a star-shaped wiring are common, in particular in cable conducts in offices (“categorycable“, „categorycable“).
 Note that the medium access control protocol in a hub is still CSMA/CD! However, collisions now take place in the hub rather than on the coaxial cable.

Ethernet LAN with a Hub and Two Coaxial Cables

LAN Switching

qThroughput in an Ethernet LAN can be further increased by LAN switching.
q The hub is replaced by a frame-switching node (switch) which forwards the individual frames between the star-topology cables. The format of the Ethernet frames remains the same, thus the end systems (stations) do not  notice the difference.
qWhen doing LAN switching, the hub is replaced by a frame switch. It eva-luates the MAC destination address and forwards the frame on the appro-priate link.

2.2  802.11 MAC for Wireless LANs

 Design goals
A wireless local area network with an 802 MAC layer
Should fit under the same LLC layer (802.2, Logical Link Control). Thus it should be compatible with all higher layers, in particular IP.
Support for stationary wireless stations and mobile wireless stations
Can operate with an infrastructure (access points) or without an infra-structure (in ad-hoc mode).
IEEE 802.11 - System Architecture (1)
 Independent Basic Service Set (IBSS)
 Set of mobile stations that are able

IEEE 802.11 - System Architecture (2)


 IEEE 802.11 defines access point, distribution system, portal and distribution services.

IEEE 802.11 - System Architecture (3)

 Infrastructure Basic Service Set
 Communication is always between a mobile station and an access point.
 Extended communication possibilities, but frames between mobile stations are sent over the air twice.

IEEE 802.11 - System Architecture (4)

 Extended Service Set
 Set of Infrastructure BSSs that are connected by a distribution system.

Why are New MAC Algorithms Needed?

CSMA/CD does not work

IFS = Inter-Frame Spacing

Frame Types
Sequence numbers (Sequence Control)
Four Addresses

Roaming (better: Hand-over or Hand-off)

5 GHz (802.11a/h/j/n/ac)
Dynamic frequency selection (DFS) and transmit power control (TPC) capabilities on 
5.250–5.350 GHz and 5.470–5.725 GHz. In addition the fre-quency range 5.150 - 
5.350 GHz is only allowed for indoor use, leaving only 5.470 - 5.725 GHz for outdoor 
and indoor use.

LAN Bridges

A brigde connects two or more LANs that may use different MACs (e.g., an Ethernet 
LAN with a Wireless LAN). It can be considered as a layer-2 gateway.
A bridge operates on layer 2 exclusively (on MAC frames). Protocols of the higher 
layers are not taken into consideration. In particular, a LAN bridge is quite different 
from an IP router.


Popular posts from this blog

Algorithm and Data structure (Lecture # 4)

Algorithms and data structures(Lecture # 01)