Transcript 15-744: Computer Networking

15-744: Computer Networking
L-22 Wireless Broadcast
Overview
• 802.11
• Deployment patterns
• Reaction to interference
• Interference mitigation
• Mesh networks
• Architecture
• Measurements
• White space networks
2
Higher Frequency
Broadcast TV
Wi-Fi (ISM)
3
What are White Spaces?
Wireless Mic
TV
5447
70
0
170-216
90
0
0
MHz•50 TV Channels
-60
ISM (Wi-Fi)
240
0
250
0
518
0
530
0
“White spaces”
7000
MHz
•Each channel is 6 MHz wide
dbm
•FCC Regulations*
TV Stations in America
•Sense TV stations and Mics
-100
MHz
•Portable devices
on channels
- 51
Frequenc21700
470 MHz
y
White Spaces
are Unoccupied TV Channels
4
The Promise of White Spaces
TV
0 54- 174-21647
0
MHz90
Wireless Mic
ISM (Wi-Fi)
240
0
70
0
250
0
518
0
530
0
7000
MHz
Up to 3x of 802.11g
More
Spectrum
Longer
Range
at least 3 - 4x of Wi-Fi
5
White Spaces Spectrum Availability
0.8
Differences from ISM(Wi-Fi)
Urban
Fraction of Spectrum
Segments
0.7
0.6
Suburban
0.5
Rural
Fragmentation
Variable channel widths
0.4
0.3
0.2
1 20.13 4 5
0
1
1 2 3 4 5
2
3
4
5
6
# Contiguous Channels
>6
Each TV Channel is 6 MHz wide
Spectrum
 isUse
Fragmented
multiple channels for more bandwidth
6
White Spaces Spectrum Availability
Differences from ISM(Wi-Fi)
Fragmentation
Variable channel widths
Spatial Variation
Cannot assume same
channel free everywhere
1 2 3 4 5
1 2 3 4 5
TV
Tower
Location impacts spectrum availability
 Spectrum exhibits spatial variation
7
White Spaces Spectrum Availability
Differences from ISM(Wi-Fi)
Fragmentation
Variable channel widths
Spatial Variation
Cannot assume same
channel free everywhere
1 2 3 4 5
1 2 3 4 5
Temporal Variation
Same Channel will
not always be free
Any connection can be
disrupted any time
Incumbents appear/disappear over time
 Must reconfigure after disconnection
8
Channel Assignment in Wi-Fi
1
6
11
Fixed Width Channels
1
6
11
 Optimize which channel to use
9
Spectrum Assignment in WhiteFi
Spectrum Assignment
Problem
Maximize Throughput
Goal
Include
1 2 3 4 5
Assign
Spectrum at clients
1 2 3 4 5
Center Channel
&
Width
Fragmentation
 Optimize for both, center channel and width
Spatial Variation
 BS must use channel iff free at client
10
Accounting for Spatial Variation
1 2 3 4 5
1 2 3 4 5

1 2 3 4 5
1 2 3 4 5

1 2 3 4 5
1 2 3 4 5
=
1 2 3 4 5
11
Intuition
Intuition
Use widest possible channel
BS
But
Limited by most busy channel
1 2 3 4 5
 Carrier Sense Across All Channels
 All channels must be free
ρBS(2 and 3 are free) = ρBS(2 is free) x ρBS(3 is free)
Tradeoff between wider channel widths
and opportunity to transmit on each channel
12
Discovering a Base Station
1 2 3 4 5
1 2 3 4 5
Discovery Time = (B x W)
Fragmentation
 Try
center
channel
and
widths
How
thedifferent
new
client
discover
BS and
Clients
must
use
same
channels
Can
wedoes
optimize
this
discovery
time?
channels used by the BS?
13
SIFT, by example
10
5 MHz
MHz
SIFT
Does not decode packets
Pattern match in time domain
Amplitude
ADC
Data
SIFT
ACK
SIFS
Time
14
Taking Advantage of Broadcast
• Opportunistic forwarding
• Network coding
• Assigned reading
• 802.11 with Multiple Antennas for Dummies
• XORs In The Air: Practical Wireless Network
Coding
• ExOR: Opportunistic Multi-Hop Routing for
Wireless Networks
15
Outline
• MIMO
• Opportunistic forwarding (ExOR)
• Network coding (COPE)
• Combining the two (MORE)
16
How Do We Increase
Throughput in Wireless?
• Wired world: pull more wires!
• Wireless world: use more antennas?
MIMO
Multiple In Multiple Out
N transmit
antennas
M receive
antennas
• N x M subchannels
• Fading on channels is largely independent
• Assuming antennas are separate ½ wavelength or more
• Combines ideas from spatial and time diversity, e.g. 1 x N and
Nx1
• Very effective if there is no direct line of sight
• Subchannels become more independent
Simple Channel Model
• No diversity:
T
R
i x pT
x
• Adding multi-path:
h
x
pR = o
T
i x pT
R
x
h(t)
x
pR = o
Transmit and Receive Diversity
Revisited
• Receive diversity:
T
R
i
x
• Transmit diversity:
H
x
T
i x PT
PR = o
R
x
H
= o
MIMO How Does it Work?
• Coordinate the processing at the transmitter
and receiver to overcome channel impairments
• Maximize throughput or minimize interference
T
I x PT
Precoding
from Nx1
R
x
H
Channel
Matrix
x
PR = O
Combining
from 1xN
• Generalization of earlier techniques
• Combines maximum ratio combining at transmitter
and receiver with sending of multiple data streams
A Math View
Direct-Mapped NxM MIMO
M
Effect of transmission
Decoding
N
M
R =H*C+N
O = PR * R
D
Results
MxN
DxM
M
C = I
N
N
O = PR * H * I + PR * N
• How do we pick PR ?  Need “Inverse” of H: H-1
• Equivalent of nulling the interfering possible (zero forcing)
• Only possible if the paths are completely independent
• Noise amplification is a concern if H is non-invertible – its
determinant will be small
• Minimum Mean Square Error detector balances two effects
Precoded NxM MIMO
M
Effect of transmission
Coding/decoding
N
M
R =H*C+N
O = PR * R
D
Results
MxN
DxM
M
C = PT * I
N
NxD
D
O = PR * H * PT * I + PR * N
• How do we pick PR and PT ?
MIMO Discussion
• Need channel matrix H: use training with
known signal
• MIMO is used in 802.11n in the 2.4 GHz band
• Can use two of the non-overlapping “WiFi
channels”
• Raises lots of compatibility issues
• Potential throughputs of 100 of Mbps
• Focus is on maximizing throughput between
two nodes
• Is this always the right goal?
Outline
• MIMO
• Opportunistic forwarding (ExOR)
• Network coding (COPE)
• Combining the two (MORE)
29
Initial Approach: Traditional Routing
packet
packet
A
packet
B
src
dst
C
• Identify a route, forward over links
• Abstract radio to look like a wired link
30
Radios Aren’t Wires
A
12
23456
3456
456
123
123456
1
B
src
dst
C
• Every packet is broadcast
• Reception is probabilistic
31
Exploiting Probabilistic Broadcast
packet
A
B
src
dst
packet
C
• Decide who forwards after reception
• Goal: only closest receiver should forward
• Challenge: agree efficiently and avoid duplicate transmissions
32
Why ExOR Might Increase Throughput
src
N1
N2
N3
N4
N5
dst
75%
50%
25%
•
•
•
•
Best traditional route over 50% hops: 3(1/0.5) = 6 tx
Throughput ≅ /# transmissions
ExOR exploits lucky long receptions: 4 transmissions
Assumes probability falls off gradually with distance
33
Why ExOR Might Increase Throughput
N1
N2
src
dst
N3
N4
• Traditional routing: 1/0.25 + 1 = 5 tx
• ExOR: 1/(1 – (1 – 0.25)4) + 1 = 2.5 transmissions
• Assumes independent losses
34
ExOR Batching
tx: ≅
1009
tx:
src
rx: 99
88
N1
tx: ≅ 8
rx: 85
57
N2 tx: 57 -23
≅ 24
N3
N4
rx: 40
0
tx: 0
rx: 22
0
dst
rx: 53
23
tx: 23
• Challenge: finding the closest node to have rx’d
• Send batches of packets for efficiency
• Node closest to the dst sends first
• Other nodes listen, send remaining packets in turn
• Repeat schedule until dst has whole batch
35
Reliable Summaries
tx: {2, 4, 10 ... 97, 98}
batch map: {1,2,6, ... 97, 98, 99}
N2
N4
src
dst
N1
N3
tx: {1, 6, 7 ... 91, 96, 99}
batch map: {1, 6, 7 ... 91, 96, 99}
• Repeat summaries in every data packet
• Cumulative: what all previous nodes rx’d
• This is a gossip mechanism for summaries
36
Outline
• MIMO
• Opportunistic forwarding (ExOR)
• Network coding (COPE)
• Combining the two (MORE)
40
Background
• Famous butterfly example:
• All links can send one message per unit of
time
• Coding increases overall throughput
41
Background
• Bob and Alice
Relay
Require 4 transmissions
42
Background
• Bob and Alice
Relay
XOR
XOR
XOR
Require 3 transmissions
43
Coding Gain
• Coding gain = 4/3
1
1+3
3
44
Throughput Improvement
• UDP throughput improvement ~ a factor 2 >
4/3 coding gain
1
1+3
3
45
Coding Gain: more examples
2
1
5
3
4
1+2+3+4+5
Without opportunistic listening, coding [+MAC] gain=2N/(1+N)  2.
With opportunistic listening, coding gain + MAC gain  ∞
46
COPE (Coding Opportunistically)
• Overhear neighbors’ transmissions
• Store these packets in a Packet Pool for a
short time
• Report the packet pool info. to neighbors
• Determine what packets to code based on
the info.
• Send encoded packets
47
Opportunistic Coding
P4 P1
C
P4 P3 P2 P1
B’s queue
Next hop
P1
A
P2
C
P3
C
P4
D
Coding
Is it good?
P1+P2
Bad (only C can
decode)
P1+P3
Better coding (Both A
and C can decode)
P1+P3+P4
Best coding (A, C, D
can decode)
B
A
P4 P3
D
P3 P1
Packet Coding Algorithm
• When to send?
• Option 1: delay packets till enough packets to code with
• Option 2: never delaying packets -- when there’s a
transmission opportunity, send packet right away
• Which packets to use for XOR?
• Prefer XOR-ing packets of similar lengths
• Never code together packets headed to the same next
hop
• Limit packet re-ordering
• XORing a packet as long as all its nexthops can
decode it with a high enough probability
49
Packet Decoding
• Where to decode?
• Decode at each intermediate hop
• How to decode?
• Upon receiving a packet encoded with n native
packets
• find n-1 native packets from its queue
• XOR these n-1 native packets with the received
packet to extract the new packet
50
Summary of Results
• Improve UDP throughput by a factor of 3-4
• Improve TCP by
• wo/ hidden terminal: up to 38% improvement
• w/ hidden terminal and high loss: little improvement
• Improvement is largest when uplink to
downlink has similar traffic
• Interesting follow-on work using analog coding
52
Reasons for Lower Improvement in TCP
• COPE introduces packet re-ordering
• Router queue is small  smaller coding
opportunity
• TCP congestion window does not sufficiently
open up due to wireless losses
• TCP doesn’t provide fair allocation across
different flows
53
Outline
• MIMO
• Opportunistic forwarding (ExOR)
• Network coding (COPE)
• Combining the two (MORE)
55
Use Opportunistic Routing
R1
R2
dst
src
50%
R3
R4
• Best single path  loss prob. 50%
Opportunistic
routing
promises
large
increase
in
• In opp. routing [ExOR’05], any router that hears the
packet can forward throughput
it  loss prob. 0.54 = 6%
56
But
• Overlap in received packets  Routers
forward duplicates
P1
R1
P2
P1
P2
P10
src
dst
R2
P1
P2
57
ExOR
• State-of-the-art opp. routing, ExOR imposes
a global scheduler:
• Requires full coordination; every node must
know who received what
• Only one node transmits at a time, others
listen
58
Global Scheduling
dst
src
• Global coordination is too hard
• One transmitter  You lost spatial reuse!
59
MORE (Sigcomm07)
• Opportunistic routing with no global
scheduler and no coordination
• Uses random network coding
• Experiments show that randomness
outperforms both current routing and ExOR
60
Go Random
Each router forwards random combinations of packets
P1
P2
R1
α P1+ ß P2
src
dst
P1
P2
R2
γ P1+ δ P2
Randomness prevents duplicates
No scheduler; No coordination
Simple and exploits spatial reuse
61
Random Coding Benefits Multicast
P1
P2
P3
P4
src
dst1
dst2
dst3
P1
P2
P3
P1
P1
P2
P3
P4
P2
P4
P3
P4
Without coding  source retransmits all 4 packets
62
Random Coding Benefits Multicast
Random combinations
P1
P2
P3
P4
8 P1+5 P2+ P3+3 P4
src
7 P1+3 P2+6 P3+ P4
dst1
dst2
dst3
P1
P2
P3
P1
P1
P2
P3
P4
P2
P4
P3
P4
Without coding  source retransmits all 4 packets
With random coding  2 packets are sufficient
63
Summary
• Wireless behavior is not all bad
• Next lecture: Security: DDoS and
Traceback
• Readings:
• Practical Network Support for IP Traceback
• Amplification Hell: Revisiting Network Protocols
for DDoS Abuse
67