Transcript TCP for Mobile and Wireless Hosts

Can Theory Meet Practice:
The Case of Multi-Channel Wireless Networks
Nitin Vaidya
Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
Sept. 19. 2008
1
Multi-Channel Wireless Networks
Acknowledgements
Ph.D
M.S.

Jungmin So (2006)

Priya Ravichandran (2003)

Pradeep Kyasanur (2006)

Chandrakanth Chereddi (2006)

Vartika Bhandari (2008)

Rishi Bhardwaj (2007)

Thomas Shen (2008)

Vijay Raman
Post-docs

Wonyong Yoon

Cheolgi Kim
Funded in part by:
NSF, ARO, Motorola, Boeing
2
Preliminaries …
3
Wireless Networks

Wireless paradigms:
Single hop versus Multi-hop

Multi-hop networks:
Mesh networks, ad hoc networks, sensor networks
4
What Makes Wireless Networks
Interesting?
Significant path loss
- Signal deteriorates over space
+ Spatial re-use feasible
B
A
power

S
distance
5
5
What Makes Wireless Networks
Interesting?
Interference management non-trivial
B
A
power

I
C
D
S
distance
6
What Makes Wireless Networks
Interesting?
Many forms of diversity
• Time
• Route
• Antenna
• Path
• Channel
7
What Makes Wireless Networks
Interesting?
Time diversity
C
D
gain
Time
8
What Makes Wireless Networks
Interesting?
Route diversity
infrastructure
AP1
Access
point
AP2
B
F
A
X
C
D
E
Z
9
What Makes Wireless Networks
Interesting?
Antenna diversity
D
C
A
B
10
Sidelobes not shown
What Makes Wireless Networks
Interesting?
Path diversity
11
What Makes Wireless Networks
Interesting?
Channel diversity
High interference
Low gain
B
A
B
A
High gain
B
A
B
A
D
C
D
C
Low interference
12
Wireless Capacity

Wireless capacity limited

In dense environments, performance suffers

How to improve performance ?
13
Improving Wireless Capacity

Exploit physical resources, diversity

Exploiting diversity requires appropriate protocols
14
State of Multi-Hop Wireless
Very large volume of activity

Beautiful theory
Asymptotic Capacity
Throughput-optimal scheduling
Network utility optimization
Network coding
Cooperative relaying
15
State of Multi-Hop Wireless
Very large volume of activity

Practical protocols & deployments
Many wireless standards
And many more MAC & routing protocols
Many experimental deployments
Mesh devices
Sensor devices
Start-ups
16
State of Multi-Hop Wireless
Despite the volume of activity


Theoretical developments haven’t been translated
to practice
Theory often ignores realities of wireless
networks
Greater success in cellular environments
17
What is Lacking ?
Meaningful contact between


Practice
Networking


Theory
Comm
18
Picture from Wikipedia
This Talk
Utilizing multiple channels
in multi-hop wireless
19
Multi-Channel Environments
Available spectrum
Spectrum divided into channels
1
2
3
4
…
c
20
Multiple Channels
3 channels
8 channels 4 channels
26 MHz
100 MHz
200 MHz
150 MHz
915 MHz
2.45 GHz
5.25 GHz
5.8 GHz
IEEE 802.11 in ISM Band
21
Outline
capacity
D
Theory
to
Practice
Net-X
testbed
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
22
Interfaces & Channels

An interface can only use one channel at a time
Channel 1
W
cW
Channel c

Switching between channels may incur delay
23
Multiple Interfaces


Reducing hardware
cost allows for
multiple interfaces
m interfaces per node
1
m
24
Practical Scenario

m<c
A host can only be on
subset of channels
1
1
m
m
m+1
c
c–m unused channels
at each node
25
Multi-Channel Mesh

How to best utilize multiple channels
in a mesh network
with limited hardware ?
?
26
Need for New Protocols
m<c
c = 4 channels
m = 2 interfaces
1,2
1,2
A
B
D 1,2
Some channels not used
1,2
C
1,3
1,2
3,4
A
B
C
D
2,4
Network poorly connected
27
Multi-Channel Networks
Many Inter-Dependent Issues

How to choose a channel
for a transmission?
B
A


How to schedule
transmissions?
How to measure
“channel quality”
C
- gain, load

How to select routes ?
28
Outline
capacity
D
Theory
to
Practice
Net-X
testbed
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
29
Capacity Analysis


How does capacity improve with more channels ?
How many interfaces necessary to
efficiently utilize c channels ?
30
Network Model
31
Network Model
[Gupta-Kumar]

Random source-destination pairs among
randomly positioned n node in unit area,
with n  ∞
32
Capacity = ?


l = minimum flow throughput
Capacity = n l
33
Capacity
[Gupta-Kumar]

c=m
capacity
a
1
1
m=c
c=m
Capacity scales linearly with channels
IF # interfaces also scaled
34
Capacity

What if fewer interfaces ?
1
1
m
m
m+1
c
35
Mutlti-Channel Capacity
Order O(.)
Channels (c/m)
36
Capacity with n  ∞
Are these results relevant ?

Yield insights on design of
good routing and scheduling protocols
37
Outline
capacity
D
Theory
to
Practice
Net-X
testbed
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
38
Insights from Analysis (1)
Channel Usage


Need to balance load on channels
Local channel assignment schemes helpful in some
large scale scenarios
 Local mechanisms with some hints from nearby
nodes
39
Insights from Analysis (2)


Static channel allocation
not optimal performance
in general
Must dynamically switch channels
Channel 1
B
A
2
C
D
40
Insights from Analysis (3)

Small number of switchable interfaces suffice

How to use a larger number of interfaces ?
41
Channel Management

Hybrid channel assignment: Static + Dynamic
Fixed (ch 1)
Fixed (ch 2)
Fixed (ch 3)
A
B
C
Switchable
2
1
Switchable
3
2
Switchable
42
Insights from Analysis (4)

Interface bottleneck can constrain performance
Interfaces as a resource
in addition to spectrum, time and space
43
Alleviating Interface Bottleneck

Routes must be distributed within a neighborhood
D
D
F
A
B
E
F
B
A
E
C
C
m=1
c=1,2
44
Insights from Analysis (5)

Channel switching delay potentially detrimental

But may be hidden with
careful scheduling – create idle time on
interfaces between
channel switches
additional interfaces
45
Insights from Analysis (6)

Optimal transmission range function of
number of channels
Intuition:
# of interfering nodes ≈ # of channels
46
Protocol Design: Timescale Separation
Upper layers

Routing: Longer timescales
(Optional) Multi-channel aware
route selection

Interface management:
Shorter timescales
Dynamic channel assignment
Interface switching
Transport
Network
802.11 Link
Physical
Layer
47
CBR – Random topology
(50 nodes, 50 flows, 500m x 500m area)
CBR flows
Normalized throughput
16
(m,c)
(2,2)
(2,5)
(5,5)
(2,12)
(12,12)
14
12
10
8
6
4
2
0
1
2
3
4
5
6
7
Topology number
8
9
10
48
Outline
capacity
D
Theory
to
Practice
Net-X
testbed
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
49
Net-X Testbed


Soekris 4521


Linux 2.4
Two 802.11a radios
per mesh node (m = 2)
Legacy clients with
1 radio
c = 5 channels
Net-X source
available
50
Phy-Aware Support

Additional mechanisms needed
to choose channels based on
destination
Ch. 2
B
A
Ch. 1
C
Next hop not equivalent to a wireless interface id


Phy-aware forwarding not supported traditionally
In general, need a “constraint” specification
for desired channel(s), antenna beamform,
power/rate, … to be used for the next hop
51
Phy-Aware Support

Multi-channel (phy-aware)
broadcast
Ch. 2
D

Channel switching from user space
has high latency: frequent switching
from user space undesirable
Ch. 3 A
B
Ch. 1
C
52
New Kernel Support

Interface management needs to be hidden from
“data path”
– Buffering packets for different channels
– Scheduling interface switching
Ch. 2
Ch. 1
Packet to B
buffer packet
Interface switches
to channel 1
Packet to C
Packet to C arrives
53
Asymmetry
Fixed (ch 1)
Fixed (ch 2)
Fixed (ch 3)
A
B
C
Switchable
2
1
Switchable
3
2
Switchable
54
Shortcomings
55
Shortcomings

Scheduling using legacy protocol (802.11),
ignorant of multi-channel nature of the system

Ignores interface heterogeneity

Does not explicitly handle channel heterogeneity
• All nodes assumed to switch to all available channel
• 802.11 / abg versus 802.11/bg
• Channel gains and external interference vary
56
capacity
D
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
Net-X
testbed
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
57
Modeling Interface Heterogeneity

Each radio can operate only on a subset of channels
58
Adjacent (c, f) Assignment
 Each node assigned a contiguous block of f channels
This model also subsumes
untuned radios [Petrovic et al]
as special cases
Example: f=2, c=8
59
Random (c, f) Assignment
 Each node is assigned a random f-subset of channels
More freedom in choices;
no adjacency constraint
Example: f=2, c=8
60
Impact of Constrained Channel Switching
Connectivity
(4, 5)
(2, 3)
A node cannot communicate
will all “in range” nodes
(5, 6)
(1, 2)
(1, 3)
(6, 7)
(7, 8)
(3, 6)
(2, 5)
Bottleneck Formation
Some channels may be
scarce in certain network
regions, leading to overload
on some channels/nodes
61
Channel Heterogeneity

Not all channels are made equal
 Distributed scheduling with heterogeneous
channels
62
Status
G
Channelbinding
Interface
-binding
IF
#1
Capacity + Scheduling
Protocol stack
IF
#2
Neighbor
Queues
Channel
Queues
IF
#m
Interface
Queues
63
capacity
D
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
Wrap-up
Net-X
testbed
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
64
Summary



Significant performance benefits using
many channels despite limited hardware
Insights from analysis useful in protocol design
Conversely, implementation experience helps
formulate new to theoretical problems
Important to complete the
loop from theory to practice
65
Research Opportunities


Significant effort in protocol design needed to
exploit available physical resources
Examples:
• MIMO (multi-antenna)
• Cooperative relaying
• Dense wireless infrastructure
66
Thanks!
www.crhc.uiuc.edu/wireless
67