Transcript ppt - Computer Science & Engineering

University of Nevada – Reno
Computer Science & Engineering Department
Fall 2015
CPE 400 / 600
Computer Communication Networks
Lecture 22
Prof. Shamik Sengupta
Office SEM 204
[email protected]
http://www.cse.unr.edu/~shamik/
Chapter 5
Link Layer
A note on the use of these ppt slides:
We’re making these slides freely available to all (faculty, students, readers).
They’re in PowerPoint form so you see the animations; and can add, modify,
and delete slides (including this one) and slide content to suit your needs.
They obviously represent a lot of work on our part. In return for use, we only
ask the following:
 If you use these slides (e.g., in a class) that you mention their source
(after all, we’d like people to use our book!)
 If you post any slides on a www site, that you note that they are adapted
from (or perhaps identical to) our slides, and note our copyright of this
material.
Computer
Networking: A Top
Down Approach
6th edition
Jim Kurose, Keith Ross
Addison-Wesley
March 2012
Thanks and enjoy! JFK/KWR
All material copyright 1996-2012
J.F Kurose and K.W. Ross, All Rights Reserved
Link Layer
5-2
The Data Link Layer
Our goals:

understand principles behind data link layer services:
 link layer addressing
 sharing a broadcast channel: multiple access
 reliable data transfer
 error detection, correction

Understanding various link layer technologies
 Ethernet (wired domain)
 Hubs, Switches, Bridges
 Differences with Routers
 Wi-Fi (wireless domain)
Link Layer: Introduction
Some terminology:


hosts and routers are nodes
communication channels that
connect adjacent nodes along
communication path are links
 wired links
 wireless links

layer-2 packet is a frame,
encapsulates datagram
data-link layer has responsibility of
transferring datagram from one node
to adjacent node over a link
Link Layer Services

framing, link access:
 encapsulate datagram into frame, adding header, trailer
 channel access if shared medium
 “MAC” addresses used in frame headers to identify source, dest
different from IP address!

reliable delivery between adjacent nodes
Q: why both link-level and end-end reliability?
Link Layer Services (more)

flow control:
 pacing between adjacent sending and receiving nodes

error detection:
 errors caused by signal attenuation, noise.
 receiver detects presence of errors:
signals sender for retransmission or drops frame

error correction:
 receiver identifies and corrects bit error(s) without resorting to
retransmission
Where is the link layer implemented?


in each and every host
link layer implemented in
“adaptor” (aka network
interface card NIC)
 Ethernet card, 802.11 card
 implements link, physical layer


attaches into host’s system
buses
combination of hardware,
software, firmware
host schematic
application
transport
network
link
cpu
memory
controller
link
physical
host
bus
(e.g., PCI)
physical
transmission
network adapter
card
MAC Addresses

There are two types of addresses:

32-bit IP address:
 network-layer address
 used to get datagram to destination IP subnet

MAC (or LAN or physical or Ethernet) address:
 function: get frame from one interface to another physically-connected
interface (same network)
 48 bit MAC address (for most LANs)
 burned in NIC ROM, also sometimes software settable
MAC Addresses

MAC (or LAN or physical or Ethernet) address:
 48 bit MAC address
MAC Addresses
Each adapter on LAN has unique MAC address
Locally administered
Broadcast address =
FF-FF-FF-FF-FF-FF
1A-2F-BB-76-09-AD
71-65-F7-2B-08-53
LAN
(wired or
wireless)
= adapter
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
Which ones are globally
unique and which ones are
locally administered?
ARP
Link Layer 5-11
ARP: Address Resolution Protocol
Question: how to determine
MAC address of B
knowing B’s IP address?


137.196.7.78
1A-2F-BB-76-09-AD
137.196.7.23

137.196.7.14
LAN
71-65-F7-2B-08-53
137.196.7.88
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
Each IP node (host, router)
on LAN has ARP table
ARP table: IP/MAC address
mappings for some LAN
nodes
< IP address; MAC address>

Timeout: time after which
address mapping will be
forgotten (Varies from
vendor to vendor, device to
device)
ARP: Address Resolution Protocol
Question: how to determine
MAC address of B
knowing B’s IP address?
137.196.7.78
1A-2F-BB-76-09-AD
137.196.7.23
137.196.7.14
LAN
71-65-F7-2B-08-53
137.196.7.88
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
 arp -a
 arp -s
 arp -d
ARP protocol: Same LAN (network)



A wants to send datagram to B,
and B’s MAC address not in
A’s ARP table.
A broadcasts ARP query
packet, containing B's IP
address
 dest MAC address = FF-FFFF-FF-FF-FF
 all machines on LAN
receive ARP query
B receives ARP packet, replies
to A with its (B's) MAC
address
 frame sent to A’s MAC
address (unicast)


A caches (saves) IP-to-MAC
address pair in its ARP table
until information becomes old
(times out)
 soft state: information that
times out (goes away)
unless refreshed
ARP is “plug-and-play”:
 nodes create their ARP
tables without intervention
from net administrator
Addressing: routing to another LAN
Proxy-ARP: walkthrough: send datagram from A to B via R
assume A knows B’s IP address
88-B2-2F-54-1A-0F
74-29-9C-E8-FF-55
A
111.111.111.111
E6-E9-00-17-BB-4B
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
111.111.111.112
R
222.222.222.221
222.222.222.222
B
49-BD-D2-C7-56-2A
CC-49-DE-D0-AB-7D

two ARP tables in router R, one for each IP network
(LAN)
Addressing: routing to another LAN
A creates IP datagram with IP source A, destination B
A creates link-layer frame with R's MAC address as dest,
frame contains A-to-B IP datagram


MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
A
R
111.111.111.111
74-29-9C-E8-FF-55
B
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer 5-16
Addressing: routing to another LAN
frame sent from A to R
frame received at R, datagram removed, passed up to IP


MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
A
IP
Eth
Phy
R
111.111.111.111
74-29-9C-E8-FF-55
B
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer 5-17
Addressing: routing to another LAN


R forwards datagram with IP source A, destination B
R creates link-layer frame with B's MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
A
R
111.111.111.111
74-29-9C-E8-FF-55
IP
Eth
Phy
B
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer 5-18
Addressing: routing to another LAN


R forwards datagram with IP source A, destination B
R creates link-layer frame with B's MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
A
R
111.111.111.111
74-29-9C-E8-FF-55
IP
Eth
Phy
B
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer 5-19
Addressing: routing to another LAN


R forwards datagram with IP source A, destination B
R creates link-layer frame with B's MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
A
R
111.111.111.111
74-29-9C-E8-FF-55
B
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112
CC-49-DE-D0-AB-7D
111.111.111.110
E6-E9-00-17-BB-4B
222.222.222.221
88-B2-2F-54-1A-0F
Link Layer 5-20
Understanding the competition
for medium (channel) access
Protocols for Medium Access Control (MAC)
Multiple Access Links and Protocols
Two types of “links”:

broadcast (shared wire or medium)
 Ethernet
 802.11 wireless LAN

humans at a
cocktail party
(shared air, acoustical)
point-to-point
 point-to-point link between switches/Bridges and hosts
shared wire (e.g.,
cabled Ethernet)
shared RF
(e.g., 802.11 WiFi)
shared RF
(satellite)
Multiple Access protocols


single shared broadcast channel
two or more simultaneous transmissions by nodes:
interference
 collision if node receives two or more signals at the same time
multiple access protocol
 distributed algorithm that determines how nodes share
channel, i.e., determine when node can transmit
 communication about channel sharing must use channel itself!
 no out-of-band channel for coordination
Ideal Multiple Access Protocol
What are the multiple access protocols?
Channel Partitioning MAC protocols: TDMA
TDMA: time division multiple access




access to channel in "rounds"
each station gets fixed length slot (length = pkt trans time)
in each round
unused slots go idle
example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle
6-slot
frame
1
3
4
1
3
4
Channel Partitioning MAC protocols: FDMA
FDMA: frequency division multiple access



channel spectrum divided into frequency bands
each station assigned fixed frequency band
unused transmission time in frequency bands go idle
example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6
idle
FDM cable
frequency bands

“Taking Turns” MAC protocols
Polling:
 master node “invites”
slave nodes to transmit
in turn
 typically used with
“dumb” slave devices
 concerns:
1.
2.
3.
polling overhead
latency
single point of failure
(master)
data
poll
master
data
slaves
“Taking Turns” MAC protocols
Token ring:
 control token passed
from one node to next
sequentially.
 token message
 concerns:



token overhead
latency
single point of failure
(token)
T
(nothing
to send)
T
data
Concerns with Ideal protocols





Conservative
Too much overhead wasted
Not flexible, dynamic
If one user has nothing to send that “slot” is
wasted
Internet is all about dynamic…why not make
MAC protocol dynamic in nature?
MAC: Random Access Protocols

When node has packet to send
 transmit at full channel data rate R.
 no a priori coordination among nodes


two or more transmitting nodes ➜ “collision”,
random access MAC protocol specifies:
 how to detect collisions
 how to recover from collisions (e.g., via delayed retransmissions)

Examples of random access MAC protocols:
 Ethernet (IEEE 802.3)
 Wi-Fi (IEEE 802.11)

Based on the principle of reducing collisions!
CSMA (Carrier Sense Multiple Access)
CSMA: listen before transmit:
If channel sensed idle: transmit entire frame
 If channel sensed busy, defer transmission

human analogy: don’t interrupt others!
CSMA/CD (Collision Detection)

CSMA/CD: carrier sensing, collision detection
collisions detected within short time
colliding transmissions aborted, reducing channel wastage

collision detection:
easy in wired LANs: measure signal strengths, compare
transmitted, received signals
difficult in wireless LANs: received signal strength
overwhelmed by local transmission strength

human analogy: the polite conversationalist
Ethernet
Ethernet
“dominant” wired LAN technology:
 cheap $20 for NIC
 first widely used LAN technology
 simpler, cheaper
 kept up with speed race: 10 Mbps – 10 Gbps
Metcalfe’s Ethernet
sketch
Ethernet: physical topology

bus: popular through mid 90s
 all nodes in same collision domain
• can collide with each other

star: prevails today
 active switch in center
 each “spoke” runs a (separate) Ethernet protocol
• nodes do not collide with each other
switch
star
bus: coaxial cable
Link Layer 5-35
Ethernet frame structure
sending adapter encapsulates IP datagram (or other
network layer protocol packet) in Ethernet frame
type
dest.
source
preamble address address
data
(payload)
CRC
preamble:
 7 bytes with pattern 10101010 followed by one
byte with pattern 10101011
Link Layer 5-36
Ethernet frame structure (more)

addresses: 6 byte source, destination MAC addresses
 if adapter receives frame with matching destination address,
or with broadcast address (e.g. ARP packet), it passes data
in frame to network layer protocol
 otherwise, adapter discards frame

type: indicates higher layer protocol
IPV4, IPV6, ARP etc.

CRC: cyclic redundancy check at receiver
 error detected: frame is dropped
type
dest.
source
preamble address address
data
(payload)
CRC
Link Layer 5-37
University of Nevada – Reno
Computer Science & Engineering Department
Fall 2015
CPE 400 / 600
Computer Communication Networks
Lecture 23
Prof. Shamik Sengupta
Office SEM 204
[email protected]
http://www.cse.unr.edu/~shamik/
Ethernet: Unreliable, connectionless


connectionless: No handshaking between sending and
receiving NICs
unreliable: receiving NIC doesn’t send acks or nacks to
sending NIC
 stream of datagrams passed to network layer can have gaps (missing
datagrams)
 gaps will be filled if app is using TCP
 otherwise, app will see gaps

Ethernet’s MAC protocol: unslotted CSMA/CD
Ethernet CSMA/CD algorithm
1. NIC receives datagram from network 4. If NIC detects another transmission
layer, creates frame
while transmitting, aborts, send a
jam signal and prepare for
retransmission
2. If NIC senses channel idle, starts
frame transmission.
5. After collision, NIC enters
If NIC senses channel busy, waits
exponential backoff: after mth
until channel idle, then transmits
collision, NIC chooses K at random
from {0,1,2,…,2m-1}. NIC waits K
3. If NIC transmits entire frame without
slot times, returns to Step 2
detecting another transmission, NIC
(1 slot = 512 bit times)
is done with frame !
Ethernet’s CSMA/CD (more)
Jam Signal: make sure all other
transmitters are aware of
collision; 48 bits
Bit time: .1 microsec for 10 Mbps
Exponential Backoff:
Goal: adapt retransmission attempts
to estimated current load
 heavy load: random wait will
be longer
first collision: choose K from {0,1};
delay is K· 512 bit transmission times
after second collision: choose K
from {0,1,2,3}…
after
ten collisions, choose K from
{0,1,2,3,4,…,1023}
Overview of physical devices in the LAN



Hubs
Switches
Bridges
Hubs
… physical-layer (“dumb”) repeaters:
 bits coming in one link go out all other links at same
rate
 all nodes connected to hub can collide with one
another
 no frame buffering
 no CSMA/CD at hub: host NICs detect collisions
twisted pair
hub
Switch



link-layer device:
smarter than hubs, take active role
 store, forward Ethernet frames
 examine incoming frame’s MAC address, selectively
forward frame to one-or-more outgoing links when
frame is to be forwarded on segment, uses
CSMA/CD to access segment
transparent
 hosts are unaware of presence of switches

plug-and-play, self-learning
 switches typically do not need to be configured
Switch: allows multiple simultaneous
transmissions
A



hosts have dedicated,
direct connection to switch
switches buffer packets
Ethernet protocol used on
each incoming link, but no
collisions



C’
B
1 2
6
5
4
C
each link is its own collision domain
Full duplex
switching: A-to-A’ and Bto-B’ simultaneously,
without collisions
 not possible with “dumb” hub
3
B’
A’
switch with six interfaces
(1,2,3,4,5,6)
Switch Table



Q: how does switch know that
A’ reachable via interface 4,
B’ reachable via interface 5?
A
C’
B
A: each switch maintains a
switch table
1 2
6
5
4
C
each entry in the table holds:
 MAC address of host
 interface to reach host
 time stamp
3
B’
A’
Switch: self-learning


Q: how are entries created,
maintained in switch table?
A A A’
C’
B
switch learns which hosts can be
reached through which
interfaces
1 2
6
 when frame received, switch
“learns” location of sender:
incoming LAN segment
 records sender/location pair in
switch table
5
3
4
C
B’
MAC addr interface
A
Source: A
Dest: A’
1
A’
TTL
60
Switch table
(initially empty)
Self-learning, forwarding:
example

frame destination
unknown: flood
Source: A
Dest: A’
A A A’
C’
B
A6A’
5
 destination A location
known:
selective send
1 2
4
C
A’ A
B’
MAC addr interface
A
A’
1
4
3
A’
TTL
60
60
Switch table
(initially empty)
Interconnecting switches

switches can be connected together
S4
S1
S3
S2
A
B
C
F
D
E
I
G
H
 Q: sending from A to G - how does S1 know to
forward frame destined to G via S4 and S3?
 A: self learning! (works exactly the same as in
single-switch case!)
Institutional network
mail server
to external
network
router
web server
Link Layer 5-50
Switches vs. routers
datagram
both are store-and-forward:
frame
 routers: network-layer devices
application
transport
network
link
physical
 examine network-layer headers
 switches: link-layer devices
frame
link
physical
switch
 examine link-layer headers
both have forwarding tables:
 routers: compute tables using
routing algorithms, IP addresses
 switches: learn forwarding table
using flooding, learning, MAC
addresses
network datagram
link
frame
physical
application
transport
network
link
physical
Link Layer 5-51
Introduction to Bridges
 Many times it is necessary to connect a local area network to
another local area network
 The LANs might be of different types
 E.g., Ethernet LAN, token ring LAN etc.
 Switches are not sufficient then!
 Local area network to local area network connections are often
performed with a bridge
A bridge interconnecting two dissimilar LANs
Bridges
 A bridge can be used to connect two different LANs, such as a
CSMA/CD LAN and a token ring LAN
 A bridge can also be used to connect two similar LANs, such as
two CSMA/CD LANs
 Just like switch functionality
Bridges (2)
 Just like switch, a bridge does not need programming
but observes all traffic and builds routing tables
from this observation
 This observation is called backward learning.
 Each bridge has two connections (ports) and there is
a routing table associated with each port.
 A bridge observes each frame that arrives at a port,
extracts the source address from the frame, and places
that address in the port’s routing table.
Bridges (3)
More importantly,
 A bridge can also convert one frame format to another
 The bridge removes the headers and trailers from one
frame format and inserts (encapsulates) the headers and
trailers for the second frame format
Data Communications and Computer Networks
Chapter 8
Encapsulation
University of Nevada – Reno
Computer Science & Engineering Department
Fall 2015
CPE 400 / 600
Computer Communication Networks
Lecture 24
Prof. Shamik Sengupta
Office SEM 204
[email protected]
http://www.cse.unr.edu/~shamik/
VLANS
Link Layer 5-59
VLANs: motivation
consider:


Computer
Science
Electrical
Engineering
Computer
Engineering
CS user moves office to EE, but
wants connect to CS switch?
single broadcast domain:
 all layer-2 broadcast traffic
must cross entire LAN
 ARP, DHCP, unknown
location of destination MAC
address
 security/privacy, efficiency
issues
Link Layer 5-60
VLANs
port-based VLAN: switch ports grouped
(by switch management software)
so that single physical switch
Virtual Local
Area Network
switch(es) supporting
VLAN capabilities can
be configured to define
multiple virtual LANS
over a single physical
LAN infrastructure
1
7
9
15
2
8
10
16
…
…
Electrical Engineering
(VLAN ports 1-8)
Computer Science
(VLAN ports 9-15)
… operates as multiple virtual switches
1
7
9
15
2
8
10
16
…
Electrical Engineering
(VLAN ports 1-8)
…
Computer Science
(VLAN ports 9-16)
Link Layer 5-61
Port-based VLAN

traffic isolation: frames to/from ports
1-8 can only reach ports 1-8
router
 can also define VLAN based on MAC addresses
of endpoints, rather than switch port

dynamic membership: ports
can be dynamically assigned
among VLANs
1
7
9
15
2
8
10
16
…
Electrical Engineering
(VLAN ports 1-8)

…
Computer Science
(VLAN ports 9-15)
forwarding between VLANS: done via routing
(just as with separate switches)
 in practice vendors sell combined switches plus routers
Link Layer 5-62
VLAN-aware switches

Commercial 8-port VLAN-aware switches ($30-$60)
Link Layer 5-63
VLANS spanning multiple switches
1
7
9
15
1
3
5
7
2
8
10
16
2
4
6
8
…
Electrical Engineering
(VLAN ports 1-8)

…
Computer Science
(VLAN ports 9-15)
Ports 2,3,5 belong to EE VLAN
Ports 4,6,7,8 belong to CS VLAN
trunk port: carries frames between VLANS defined
over multiple physical switches
 frames forwarded within VLAN between switches can’t be
ordinary 802.1 frames (must carry VLAN ID info)
 802.1q protocol adds/removed additional header fields for
frames forwarded between trunk ports
Link Layer 5-64
802.1Q VLAN frame format
type
preamble
dest.
address
source
address
data (payload)
CRC
802.1 frame
type
preamble
dest.
address
source
address
data (payload)
2-byte Tag Protocol Identifier
(value: 0x8100)
CRC
802.1Q frame
Recomputed
CRC
Tag Control Information (3 bit priority field like IP TOS,
1 bit drop eligible indicator, 12 bit VLAN ID field)
Link Layer 5-65
Link layer in wireless
Link Layer 5-66
link access in wireless
domain



# wireless (mobile) phone subscribers now
exceeds # wired phone subscribers!
computer networks: laptops, palmtops,
PDAs, Smart Phones promise anytime
wireless Internet access!
It has really been a wireless revolution
decade…with more to come
 Wireless is no longer a luxury but a necessity
WLAN Market: WiFi
Worldwide WLAN Infrastructure
Shipments (Source: Gartner)
Forecast Sales of Wi-Fi Equipment
(Source: InfoTech Trends)
5
7
4
Millions of Units
6
$-bil
3
2
5
4
3
2
1
1
2001
2002
2003
2004
2005
20
01
20
02
20
03
20
04
20
05
20
06
20
07
0
0
WLAN growing exponentially
Source: Pyramid Research
Source: AirTight Networks
IEEE 802.11 Wireless LAN

802.11b

802.11g

 2.4 GHz unlicensed spectrum
 up to 11 Mbps

 2.4 GHz range
 up to 54 Mbps
802.11a
 5 GHz range
 up to 54 Mbps
802.11n: multiple antennae
 2.4 / 5 GHz range
 up to 200 Mbps
What else?
 802.11 ac – builds on 802.n – provides 80-160MHz channels
 802.11ad – 60GHz mmwave spectrum
 802.11af – Super Wi-Fi

 all use CSMA/CA for multiple access
 all have infrastructure and ad-hoc network versions
802.11 LAN architecture
 wireless host communicates
Internet
AP
hub, switch
or router
BSS 1
AP
BSS 2
with base station
 base station = access
point (AP)
 Basic Service Set (BSS)
(aka “cell”) in
infrastructure mode
contains:
 wireless hosts
 access point (AP): base
station
 ad hoc mode: hosts only
Basic Service Set (BSS)
BSS
Extended Service Set (ESS)
BSS’s with wired Distribution System (DS)
BSS
BSS
802.11: Channels, association


802.11b: 2.4GHz-2.485GHz spectrum divided into
13 channels at different frequencies
 AP admin chooses frequency for AP
 interference possible: channel can be same as
that chosen by neighboring AP!
host: must associate with an AP
 scans channels, listening for beacon frames
containing AP’s name (SSID) and MAC address
 selects AP to associate with
 will typically run DHCP to get IP address in
AP’s subnet
IEEE 802.11: multiple access problem

802.11: CSMA - sense before transmitting
 don’t collide with ongoing transmission by other node


Certain differences from Ethernet LAN in wired
domain
802.11: no collision detection!
 difficult to receive (sense collisions) when transmitting due
to weak received signals (fading)
• Signal strength falls off rapidly with distance
• Signal strength may weaken due to obstacles
• Medium “air” shared among many users (not just WiFi users)
 can’t detect all collisions in any case: hidden terminal
problem
“Open” Wireless Medium


Wireless interference
S1
R1
S2
R1
Hidden terminal
S1

R1
S2
Goal: CSMA/C(ollision)A(voidance)
How does the medium access work in
WLAN?
Contention
Based
Distributed Coordination Function (DCF)

Contention
Free
Point Coordination Function (PCF)
Access methods
 DCF CSMA/CA (mandatory)
• collision avoidance via exponential backoff
• Minimum distance (IFS) between consecutive packets
• ACK packet for acknowledgements (not for broadcasts)
 DCF with RTS/CTS (optional)
• Distributed Foundation Wireless MAC
• avoids hidden terminal problem
 PCF (optional)
• access point polls terminals according to a list
802.11 – MAC

DIFS = SIFS + (2 * Slot time)
Priorities
 defined through different inter frame spaces
 SIFS (Short Inter Frame Spacing)
• highest priority, for ACK, CTS, polling
response
 PIFS (PCF IFS)
• medium priority, for time-bounded service
using PCF
 DIFS (DCF, Distributed Coordination Function IFS)
• lowest priority, for asynchronous data service,
competing stations
DIFS
DIFS
medium busy
PIFS
SIFS
access if
medium is free  DIFS
contention
next frame
t

WLAN access scheme
details
Sending unicast packets
 station has to wait for DIFS before sending data
 receivers acknowledge at once (after waiting for SIFS) if the
packet was received correctly
 automatic retransmission of data packets in case of transmission
errors
DIFS
sender
data
SIFS
receiver
ACK
DIFS
other
stations
waiting time
data
t
contention
Contention for channel

When the other stations find the channel idle, they would
like to transmit their own packets
 Contention for channel

If all the waiting stations attempt at once, this will surely
result in collision
 Some CA scheme is necessary
 Backoff intervals can be used to reduce collision probability
DIFS
sender
data
SIFS
receiver
ACK
DIFS
other
stations
waiting time
data
t
contention
Backoff Interval

When transmitting a packet, choose a backoff interval in the range
[0,cw]
 cw is contention window

Count down the backoff interval when medium is idle
 Count-down is suspended if medium becomes busy

When backoff interval reaches 0, transmit packet
B1 = 25
B1 = 5
wait
data
data
B2 = 20
Assume cw = 31
wait
B2 = 15
B2 = 10
B1 and B2 are backoff intervals
at nodes 1 and 2
Backoff Interval

The time spent counting down backoff intervals is a part of
MAC overhead
 Choosing a large cw leads to large backoff intervals and can
result in larger overhead
 Choosing a small cw leads to a larger number of collisions (when
two nodes count down to 0 simultaneously)

Since the number of nodes attempting to transmit
simultaneously may change with time, some mechanism to
manage contention is needed
 IEEE 802.11 DCF: contention window cw is chosen dynamically
depending on collision occurrence
 Follows Binary exponential backoff algorithm
Binary Exponential Backoff (BEB) in DCF

Even before the first collision, nodes follow BEB

Initial backoff interval (before 1st collision)
 [0,7]

If still packets collide, double the collision interval
 [0,15], [0,31] and so on…
Avoiding collisions (more)
idea: allow sender to “reserve” channel rather than random



access of data frames: avoid collisions of long data frames
sender first transmits small request-to-send (RTS) packets
to BS using CSMA
 RTSs may still collide with each other (but they’re
short)
BS broadcasts clear-to-send CTS in response to RTS
CTS heard by all nodes
 sender transmits data frame
 other stations defer transmissions
avoid data frame collisions completely
using small reservation packets!
Collision Avoidance: RTS-CTS exchange
A
AP
B
reservation collision
DATA (A)
time
defer
Numerical Problems Practice
Wi-Fi
Hidden Node Problem
Wi-Fi with RTS/CTS