Transcript Document

Routing in a (W)LAN
Routing in a (W)LAN is based on MAC addresses, never IP addresses. A
router (e.g. integrated with an access point) performs mapping between
these two address types:
IP network
(W)LAN
(W)LAN
device
00:90:4B:00:0C:72
Δίκτυα Υπολογιστών II
Router
124.2.10.57

00:90:4B:00:0C:72
Server
124.2.10.57
Δρ. Γεώργιος Δημητρακόπουλος
Address allocation
MAC addresses are associated with the hardware devices.
IP addresses can be allocated to (W)LAN devices either on a permanent
basis or dynamically from an address pool using the Dynamic Host
Configuration Protocol (DHCP).
The DHCP server may be a separate network element (or for example
integrated into a RADIUS server that offers a set of additional features), or
may be integrated with the address-mapping router and/or access point.
RADIUS = Remote Authentication Dial-In User Service
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Network Address Translation (NAT)
On the (W)LAN side of the network address translator (NAT device),
different (W)LAN users are identified using private (reusable, globally not
unique) IP addresses.
On the Internet side of the NAT device, only one (globally unique) IP
address is used. Users are identified by means of different TCP/UDP port
numbers.
In client - server type of communication, the application on the server is
usually behind a certain TCP/UDP port number (e.g. 80 for HTTP)
whereas clients can be allocated port numbers from a large address
range.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
NAT example
IP network
(W)LAN
User 1
NAT
device
IP address for all users in
(W)LAN:
Server
124.0.6.12
User 2
User 1 IP address
10.2.1.57
User 1 TCP port number
14781
User 2 IP address
10.2.1.58
User 2 TCP port number
14782
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Case study: ADSL WLAN router
1) The ADSL connection to the wide area network (WAN) is allocated a
globally unique IP address using DHCP.
2) We assume that the router has NAT functionality. Behind the router, in
the private LAN network, wireless and cabled LAN devices are allocated
private IP addresses, again using DHCP (this is a kind of "double DHCP"
scenario).
Although routing in the LAN is based on MAC addresses, the IP
applications running on the LAN devices still need their own "dummy" IP
addresses.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Contents
IEEE 802.11 MAC layer operation
• Basic CSMA/CA operation
• Network Allocation Vector (NAV)
• Backoff operation
• Wireless medium access example
Usage of RTS / CTS
Fragmentation
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Medium Access Control (MAC)
Medium access control: Different nodes must gain access to the shared
medium (for instance a wireless channel) in a controlled fashion
(otherwise there will be collisions).
Access methods:
FDMA
TDMA
CDMA
CSMA
Δίκτυα Υπολογιστών II
:
Assigning channels in frequency domain
LLC
Assigning time slots in time domain
MAC
Assigning code sequences in code domain
PHY
Assigning transmission opportunities in time
domain on a statistical basis
Δρ. Γεώργιος Δημητρακόπουλος
CSMA/CD vs. CSMA/CA (1)
CSMA/CD (Collision Detection) is the MAC method used in a wired LAN
(Ethernet). Wired LAN stations can (whereas wireless stations cannot)
detect collisions.
Basic CSMA/CD operation:
1)
2)
3)
4)
Δίκτυα Υπολογιστών II
CSMA/CD rule: Backoff
after collision
Wait for free medium
Transmit frame
If collision, stop transmission immediately
Retransmit after random time (backoff)
Δρ. Γεώργιος Δημητρακόπουλος
CSMA/CD vs. CSMA/CA (2)
CSMA/CA (Collision Avoidance) is the MAC method used in a wireless
LAN. Wireless stations cannot detect collisions (i.e. the whole packets will
be transmitted anyway).
Basic CSMA/CA operation:
1)
2)
3)
4)
5)
Δίκτυα Υπολογιστών II
CSMA/CA rule:
Backoff before
collision
Wait for free medium
Wait a random time (backoff)
Transmit frame
If collision, the stations do not notice it
Collision => erroneous frame => no ACK returned
Δρ. Γεώργιος Δημητρακόπουλος
AP
CSMA:
One packet at a time
Δίκτυα Υπολογιστών II
wired LAN
Basic wireless medium access
We shall next investigate
Infrastructure BSS only.
As far as medium access is
concerned, all stations and AP
have equal priority

transmission in downlink (from the
AP) and uplink (from a station) is
similar.
Δρ. Γεώργιος Δημητρακόπουλος
DCF (CSMA/CA) vs. PCF
Designed for contention-free services (delay-sensitive real-time
services such as voice transmission), but has not been implemented
(yet)
Point Coordination
Function (PCF)
Used for contention
services (and basis for
PCF)
MAC
extent
Distributed Coordination Function (DCF) based
on CSMA/CA
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (1)
Cyclic Redundancy
Check (CRC) is used for
error detection
Transmitted
frame (A=>B)
ACK
(B=>A)
DIFS
SIFS
If the received frame is
erroneous, no ACK will
be sent
When a frame is received without bit errors, the receiving station (B)
sends an Acknowledgement (ACK) frame back to the transmitting
station (A).
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (2)
Earliest allowed
transmission time of
next frame
Transmitted
frame (A=>B)
ACK
(B=>A)
Next frame
(from any station)
DIFS
SIFS
DIFS
During the transmission sequence (Frame + SIFS + ACK) the
medium (radio channel) is reserved. The next frame can be
transmitted at earliest after the next DIFS period.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (3)
Transmitted
frame (A=>B)
ACK
(B=>A)
Next frame
DIFS
SIFS
DIFS
There are two mechanisms for reserving the channel:
Physical carrier sensing and Virtual carrier sensing using the socalled Network Allocation Vector (NAV).
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (4)
Information about the
length of the frame is in
the PHY header
Transmitted
frame (A=>B)
ACK
(B=>A)
Next frame
DIFS
SIFS
DIFS
Physical carrier sensing means that the physical layer (PHY) informs
the MAC layer when a frame has been detected. Access priorities
are achieved through interframe spacing.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (5)
The two most important interframe spacing times are SIFS and
DIFS:
SIFS (Short Interframe Space) = 10 ms (16 ms)
DIFS (DCF Interframe Space) = 50 ms (34 ms)
802.11b
802.11g
When two stations try to access the medium at the same time, the
one that has to wait for the time SIFS wins over the one that has to
wait for the time DIFS. In other words, SIFS has higher priority over
DIFS.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (6)
Transmission is not
allowed as long as NAV is
non-zero
Transmitted
frame
ACK
NAV value is
given here
DIFS
NAV
SIFS
Next frame
DIFS
Virtual carrier sensing means that a NAV value is set in all stations
that were able to receive a transmitted frame and were able to read
the NAV value in this frame.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (7)
Transmitted
frame
Long transaction
ACK
ACK
NAV
DIFS
SIFS
DIFS
Virtual carrier sensing using NAV is important in situations where
the channel should be reserved for a ”longer time” (RTS/CTS
usage, fragmentation, etc.).
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
NAV value is carried in MAC header
MPDU (MAC Protocol Data Unit)
Addr 1
Addr 2
Addr 3
Addr 4
(optional)
MAC payload
FCS
Duration field: 15 bits contain the NAV value in number of
microseconds. The last (sixteenth) bit is zero.
All stations must monitor the headers of all frames they receive
and store the NAV value in a counter. The counter decrements
in steps of one microsecond. When the counter reaches zero,
the channel is available again.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (8)
Channel was idle at
least DIFS seconds
Transmitted
frame (A=>B)
ACK
(B=>A)
Next frame
(from any station)
DIFS
SIFS
t > DIFS
When a station wants to send a frame and the channel has been
idle for a time > DIFS (counted from the moment the station first
probed the channel) => can send immediately.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (9)
Channel was busy
when station wanted to
send frame
Transmitted
frame (A=>B)
ACK
(B=>A)
Backoff
DIFS
SIFS
Next
frame
DIFS
When a station wants to send a frame and the channel is busy =>
the station must wait a backoff time before it is allowed to transmit
the frame. Reason? Next two slides…
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
No backoff => collision is certain
Suppose that several stations (B and C in the figure) are waiting to
access the wireless medium.
When the channel becomes idle, these stations start sending their
packets at the same time => collision!
Station A
ACK
Station B
Collision!
Station C
DIFS
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Backoff => collision probability is reduced
Contending stations generate random backoff values bn. Backoff counters
count downwards, starting from bn. When a counter reaches zero, the
station is allowed to send its frame. All other counters stop counting until
the channel becomes idle again.
Station A
ACK
Backoff
Remaining
backoff time
Station B
bn is large
Station C
DIFS
Δίκτυα Υπολογιστών II
bn is small
Δρ. Γεώργιος Δημητρακόπουλος
Contention window (CW) for 802.11b
If transmission of a frame was unsuccessful and the frame is allowed to
be retransmitted, before each retransmission the Contention Window
(CW) from which bn is chosen is increased.
802.11b
CW
Initial attempt
DIFS
1st retransm.
DIFS
…
CW = 25-1 = 31 slots (slot =
20 ms)
…
CW = 26-1 = 63 slots
:
5th (and further)
retransmissions
Δίκτυα Υπολογιστών II
DIFS
…
CW = 210-1 =
1023 slots
Δρ. Γεώργιος Δημητρακόπουλος
Contention window (CW) for 802.11g
In the case of 802.11g operation, the initial CW length is 15 slots. The slot
duration is 9 ms. The backoff operation of 802.11g is substantially faster
than that of 802.11b.
802.11g
CW
Initial attempt
DIFS
1st retransm.
DIFS
…
CW = 24-1 = 15 slots (slot =
9 ms)
…
CW = 25-1 = 31 slots
:
6th (and further)
retransmissions
Δίκτυα Υπολογιστών II
DIFS
…
CW = 210-1 =
1023 slots
Δρ. Γεώργιος Δημητρακόπουλος
Selection of random backoff
From the number CW (= 15 / 31 … 1023 slots) the random backoff bn (in
terms of slots) is chosen in such a way that bn is uniformly distributed
between 0 … CW.
Since it is unlikely that several stations will choose the same value of bn,
collisions are rare.
The next slides show wireless medium access in action. The example
involves four stations: A, B, C and D. ”Sending a packet” means
”Data+SIFS+ACK” sequence. Note how the backoff time may be split into
several parts.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (1)
Station A
ACK
Defer
Station B
Backoff
1
Station C
Contention
Window
Defer
2
1) While station A is
sending a packet, stations
B and C also wish to send
packets, but have to wait
(defer + backoff)
2) Station C is ”winner”
(backoff time expires first)
and starts sending packet
Station D
DIFS
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (2)
3) Station D also
wishes to send a
packet
Station A
Station B
4
Station C
ACK
3
Defer
Station D
DIFS
Δίκτυα Υπολογιστών II
4) However,
station B is
”winner” and
starts sending
packet
DIFS
Δρ. Γεώργιος Δημητρακόπουλος
Wireless medium access (3)
5) Station D starts
sending packet.
Now there is no
competition.
Station A
Station B
ACK
Station C
5
Station D
DIFS
Δίκτυα Υπολογιστών II
DIFS
Δρ. Γεώργιος Δημητρακόπουλος
No shortcuts for any station…
Transmitted
frame (A=>B)
Backoff
ACK
(B=>A)
DIFS
SIFS
Next
frame
(A=>B)
DIFS
When a station wants to send more than one frame, it has to use
the backoff mechanism like any other station (of course it can
”capture” the channel by sending a long frame, for instance using
fragmentation).
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
ACK frame structure
Frame type = control
MPDU
Frame subtype = ACK
NAV
0 0 1 0 1 0 1 1
FCS
No MAC
payload
Address of station from which frame was
sent that is now acknowledged
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Usage of RTS & CTS
The RTS/CTS (Request/Clear To Send) scheme is used as a
countermeasure against the “hidden node” problem:
Hidden node problem:
WS 1
WS 1 and WS 2 can ”hear” the AP
but not each other
=>
If WS 1 sends a packet, WS 2 does not notice this
(and vice versa) => collision!
Δίκτυα Υπολογιστών II
AP
WS 2
Δρ. Γεώργιος Δημητρακόπουλος
Reservation of medium using NAV
The RTS/CTS scheme makes use of “SIFS-only” and the NAV (Network
Allocation Vector) to reserve the medium:
SIFS
WS 1
RTS
Data frame
CTS
AP
SIFS
NAV in RTS
NAV in CTS
Δίκτυα Υπολογιστών II
DIFS
ACK
SIFS
NAV = CTS + Data + ACK + 3xSIFS
NAV = Data + ACK + 3xSIFS
Δρ. Γεώργιος Δημητρακόπουλος
Danger of collision only during RTS
WS 2 does not hear the RTS frame (and associated NAV), but can hear
the CTS frame (and associated NAV).
WS 1
RTS
AP
Data frame
CTS
ACK
Danger of collision
NAV in RTS
NAV in CTS
Δίκτυα Υπολογιστών II
NAV = CTS + Data + ACK + 3xSIFS
NAV = Data + ACK + 3xSIFS
Δρ. Γεώργιος Δημητρακόπουλος
Advantage of RTS & CTS (1)
Usage of RTS/CTS offers an advantage if the data frame is very long
compared to the RTS frame:
WS 1
AP
RTS
Data frame
CTS
(RTS/CTS used)
ACK
Short interval: collision not likely
WS 1
AP
Data frame
(RTS/CTS not used)
ACK
Long interval: collision likely
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Advantage of RTS & CTS (2)
A long “collision danger” interval (previous slide) should be avoided for
the following reasons:
Larger probability of collision
Greater waste of capacity if a collision occurs and the frame has to
be retransmitted.
A threshold parameter (dot11RTSThreshold) can be set in the wireless
station. Frames shorter than this value will be transmitted without using
RTS/CTS.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος
Fragmentation
Fragmentation makes use of the RTS/CTS scheme and the NAV
mechanism:
SIFS
WS 1
RTS
AP
SIFS
Frag 0
CTS
DIFS
Frag 1
ACK 0
SIFS
ACK 1
SIFS
SIFS
RTS
NAV in WS
NAV in AP
Δίκτυα Υπολογιστών II
Frag 0
CTS
ACK 0
Δρ. Γεώργιος Δημητρακόπουλος
Sequence control field
MPDU (MAC Protocol Data Unit)
Addr 1
Addr 2
Fragment number (for
identifying fragments)
Δίκτυα Υπολογιστών II
Addr 3
Addr 4
(optional)
MAC payload
FCS
Frame sequence number (for
identifying frames)
Δρ. Γεώργιος Δημητρακόπουλος
Advantage of fragmentation
Transmitting long data frames should be avoided for the following
reasons:
Larger probability that the frame is erroneous
Greater waste of capacity if a frame error occurs and the whole
frame has to be retransmitted.
A threshold parameter (dot11FragmentationThreshold) can be set in the
wireless station. Frames longer than this value will be transmitted using
fragmentation.
Δίκτυα Υπολογιστών II
Δρ. Γεώργιος Δημητρακόπουλος