Transcript TCP for Mobile and Wireless Hosts

Multi-Channel Wireless Networks:
Capacity, Protocols, and Experimentation
Nitin Vaidya
University of Illinois at Urbana-Champaign
www.crhc.uiuc.edu/wireless
Joint work with
Pradeep Kyasanur (Ph.D. candidate)
Chandrakanth Chereddi (M.S. candidate)
1
Multi-hop Wireless Networks


Two wireless paradigms:
Single hop versus Multi-hop
Multi-hop networks:
Mesh networks, ad hoc networks, sensor networks
2
Wireless Capacity

Wireless capacity limited

In dense environments, performance suffers

How to improve performance ?
3
Improving Wireless Capacity

Exploit physical resources

Exploit diversity/multiplicity of resources

Examples …
4
Exploit Infrastructure

Infrastructure provides a tunnel to forward
packets
infrastructure
BS1
BS2
B
C
A
D
E
Z
Ad hoc connectivity
X
5
Exploit Antennas

Steered/switched directional antennas
A
B
C
D
A
B
C
D
6
Improve Spatial Reuse
Power/Rate/Carrier-Sense Control
Transmit
Power
Rate
A
B
A B
C
Spatial
reuse
D
C
High
High
Low
Low
Low
High
D
7
Exploiting Diversity
Exploiting diversity
requires suitable protocols
8
This Talk
Utilizing multiple channels in wireless networks

Capacity bounds

Protocol design

Implementation issues
9
Multiple Channels

Typically, available frequency spectrum is split
into 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
250 MHz
500 MHz
1000 MHz
24.125 GHz
61.25 GHz
122.5 GHz
Large number of channels available
10
Channel Model

c channels available

Bandwidth per channel W
Channel 1
Channel 2
Channel c
11
Radio Interfaces

An interface can only use one channel at a time
Channel 1
Channel c

Switching between channels may incur delay
12
Interface Model


Reducing hardware cost allows for
multiple interfaces
m interfaces per node: Typical values of m small
1
m
13
Channel-Interface Scenarios

1
Scenario 1:
m=c
1
Common case today
One interface per channel
1
1
m
c=m
OR
With sufficient hardware
14
Channel-Interface Scenarios

Scenario 2:
m<c
A host can only be on
a subset of channels
1
1
m
m
c
This is the likely scenario
15
Need for New Protocols

A
When m < c , new protocols are needed
How to assign m interfaces to c channels?
When to switch an interface among channels?
How to select good routes?
1
1
B
1
1
D
All channels not used
C
1
A
1
B
C
2
D
Network poorly connected
16
Outline
Utilizing multiple channels in wireless networks

Capacity bounds

Protocol design

Implementation issues
17
Capacity Analysis


How does capacity improve if more channels are
added ?
How many interfaces needed to best use c
channels ?
Clearly, c interfaces sufficient
Not always possible to have c interfaces
18
Worst Case

Worst case capacity is m/c fraction of the
best-case
A
B
Channel data rate = W
c interfaces: cW throughput
m interfaces: mW throughput

What is the average capacity?
19
Capacity = ?
[Gupta-Kumar]

Random source-destination pairs among randomly
positioned n hosts in unit area, with n  ∞
20
Capacity = ?


l = minimum flow throughput
Capacity = n l
21
Capacity Constraints


Capacity constrained by available spectrum
bandwidth
Other factors further constrain
wireless network capacity …
22
Connectivity Constraint
[Gupta-Kumar]

Need routes between source-destination pairs
Places a lower bound on transmit range
A
D
Not connected
A
D
Connected
23
Interference Constraint
[Gupta-Kumar]

Interference among simultaneous transmissions
Limits spatial reuse
(1+)d
A
 is a
Guard
parameter
d
C
D
B
24
Capacity of Wireless Networks
[Gupta-Kumar]

Bit rate for each transmission = W

Capacity increases with n and c as
Capacity increases linearly with channels
25
Capacity of Wireless Networks
[Gupta-Kumar]

1
Result holds when m = c
1
1
1
W
m=c
c
W
W
26
Capacity Problem

What if fewer interfaces ?
How does the network capacity scale with channels?
1
1
m
m
c
Additional constraints on capacity become relevant
27
Interface Constraint

Throughput is limited by number of interfaces in a
neighborhood
Interfaces, a resource
•
k nodes in the “neighborhood”
 total throughput ≤ k * m * W
28
Destination Bottleneck Constraint

Per-flow throughput limited by
total number of flows at a host
f incoming
flows
If node throughput = T
D
Per-flow throughput = T / f
29
Mutlti-Channel Network Capacity
[MobiCom05]
Channels
(m=1)
30
Outline
Utilizing multiple channels in wireless networks

Capacity bounds

Protocol design

Implementation issues
31
Protocol Design Goals

Utilize all the available channels

Without degrading network connectivity
32
Insights from Capacity Analysis (1)

Static channel allocation does not yield optimal
performance in general

Must dynamically switch channels

Need protocol mechanisms for channel switching
Channel 1
B
A
2
C
3
D
33
Insights from Capacity Analysis (2)

Optimal transmission range function of
density of nodes and
number of channels
Goal:
# of interfering nodes = # of channels
34
Insights from Capacity Analysis (3)

Routes must be distributed within a neighborhood

This is not necessary in single channel networks
D
D
F
A
B
E
C
Single Channel (m=c=1)
Optimal strategy
E
F
B
A
C
Multi-Channel (m<c)
Optimal strategy 35
Insights from Capacity Analysis (4)

Channel switching delay potentially detrimental,
but may be hidden with
careful scheduling, and/or
additional interfaces
36
Protocol Design Issue:
Which Layers to be Multi-Channel Aware?
Practical decision:

Above MAC layer

Allows use of unmodified 802.11
37
Separation of Responsibility

Interface management:
Shorter timescales
Dynamic channel assignment
to interfaces
Interface switching

Routing: Longer timescales
Multi-channel aware route
selection metrics
Upper layers
Transport
Network
802.11 Link
Physical
Layer
38
Interface Switching [Wcnc2005]



Interfaces may be switched or kept fixed
Classification:
 Static strategy: All interfaces of a node fixed
 Dynamic strategy: All interfaces of a node can switch
 Hybrid strategy: Some interfaces fixed, others switch
We use a hybrid strategy requiring at least two
interfaces per node
39
Static Strategy - Approach 1
[Draves2004Mobicom]
Assume two interfaces per node, 4 channels
1,2
1,2
1,2
A
B
C
All channels
not utilized

D
E
F
1,2
1,2
1,2
All nodes use common set of channels
Easiest extension when multiple channels available
40
Static Strategy - Approach 2
[Raniwala2005Infocom]
Assume two interfaces per node, 4 channels
1,2
1,2
2,3
A
B
C
Some routes
are longer

D
E
F
2,3
3,4
3,4
Different nodes may use different channels
41
Dynamic strategy
[So2004Mobihoc, Bahl2004Mobicom]

1-4
1-4
1-4
A
B
C
Coordination may be
needed before each
transmission
D
E
F
1-4
1-4
1-4
Interfaces can switch channels as needed
Transmissions can occur dynamically on any channel
42
Hybrid strategy
[Nasipuri1999Wcnc, Jain2001Ic3n]

One common channel used as “control” channel

Remaining channels used as “data” channels
1
1
B
A
2-4
C
2-4
Channel for data transmission negotiated on control
channel: control channel can become a bottleneck
43
Channel Assignment: Our Approach


2 interfaces much better than 1
Hybrid channel assignment: Static + Dynamic
Fixed (ch 1)
Fixed (ch 2)
Fixed (ch 3)
A
B
C
Switchable
2
1
Switchable
3
2
Switchable
44
Protocol Operation

Each node has 2 interfaces
1 fixed, 1 switchable
1
A
3
3
1
B
C
Timeline
1. A send to B
1
D
E
F
2
4
2
2. D send to A
Connectivity maintained + all channels used
45
Fixed channel selection

Goal: Different nodes in a neighborhood should use
different fixed channels
 Indirectly distributes load across channels
Protocol:
 On startup, choose random fixed channel

Every node periodically sends “Hello” pkt
Contains fixed channel of node
Contains fixed channel of 1-hop neighbors
46
Fixed channel selection



Pick channel with fewest nodes as fixed channel
Channel changed before sending next “Hello”
To prevent oscillations, change done probabilistically
Load-balances channel assignment in two-hop
neighborhood
Extensions possible:
Use load information
Balance over k-hops
47
Example
1
1
2
A
B
1) A sends Hello(1)
2) B sends Hello(2, A:1)
3) E sends Hello(4, A:1, B:2)
D
E
1
3
1
4
4) D sends Hello(3, A:1, B:2, E:4)
48
Supporting broadcast




Send a copy of packet over all channels
Strength: All neighbors receive broadcast, similar
to single channel network
Drawback: Cost of broadcast goes up
Extensions:
Use a dedicated broadcast channel (with a third
interface)
Send broadcast over subset of channels
49
Simulations

Qualnet 3.6 simulator

IEEE 802.11a channels (varied from 1 to 12)

Proposed protocols use two interfaces per node

Interface switching delay is 1 ms
50
UDP – Chain topology
Throughput (Mbps)
35
DSR - 1
MCR - 2
MCR - 5
MCR - 12
30
25
20
15
10
5
0
1
2
3
7
6
5
4
Chain length (in hops)
8
Chain Length (in hops)
9
10
51
FTP – Chain topology
Throughput (Mbps)
30
DSR - 1
MCR - 2
MCR - 5
MCR - 12
25
20
15
10
5
0
1
2
3
4
5
6
7
Chain length (in hops)
8
Chain Length (in hops)
9
10
52
Routing Approach


Existing routing protocols can be operated over
interface management protocol
May not select good routes
Does not consider cost of switching interfaces
Our solution
Develop a new channel-aware metric
Metric can be incorporated into any on-demand routing
protocol
53
Selecting Channel Diverse Routes

Most routing protocols use shortest-hop metric
Not sufficient in most multi-channel networks
1
3
3
4
B
A
4
C
A needs route to C
Route A-B-C better
4
4
D
E
F
2
4
2
Prefer channel diverse routes
54
Impact of Switching Cost

Interface switching cost has to be considered
A node may be on multiple routes, requiring switching
1
3
4
A
B
C
3
D needs route to F
D
2
Route A-B-C in use
2
E
4
4
F
2
Route D-E-F better
2
Select routes that do not require frequent switching
55
MCR: New Routing Metric

Measure switching cost for a channel

Measure total link cost of a hop:
ETT cost [Draves2004Mobicom] + Switching cost

Combine individual link costs into path cost
56
Routing Protocol



Incorporate metric in on-demand source-routed
protocol (similar to DSR)
RREQ messages modified to include link costs
Destination can compute best path
Using cost information in RREQ
57
Throughput in Random Networks
Normalized throughput
(50 nodes, 500m x 500m area)
DSR - 1
MCR - 2
MCR - 5
MCR - 12
14
12
10
8
6
4
2
0
1
2
3
4
5
6
7
Topology
Number
Topology
Number
8
9
10
58
Normalized throughput
Throughput with Varying Load
20
DSR - 1
MCR - 2
MCR - 5
MCR - 12
15
10
5
0
2
4
6
8
10
Number of Flows
Number of flows
12
14
59
Outline
Utilizing multiple channels in wireless networks

Capacity bounds

Protocol design

Implementation issues
60
Testbed



Protocols have been
implemented in a 15 node
testbed
Each node has 2 wireless
radios
Ethernet used for
controlling nodes
Soekris 4501
61
Lack of multi-channel support

Existing assumptions break with multiple channels

Routing table has only interface information
Ch. 2
B
A
Ch. 1 C
62
Lack of multi-channel support


Switching channels requires explicit invocation from
user-space
Frequent switching not permitted
Multi-channel broadcast not supported
Ch. 2
D
B
Ch. 3 A
Ch. 1
C
63
Testbed


Kernel support for multi-channel, multi-radio
implementation
Implementation of interface management and
routing protocols
64
Abstracting details

Interface management needs to be hidden from
“data path”
Allow existing applications to work unmodified
Allow variable number of channels and interfaces
Ch. 2
Ch. 1
Packet to B
buffer packet
Interface switches channel
Packet to C
Packet to C arrives
65
Implementation details
User
Applications
IP Stack
Hello Protocol
Routing Protocol
On-demand
routing support
Interface and Channel
Abstraction Layer
Interface
 Abstraction layer
simplifies the use of
multiple interfaces
 User-space daemon
implements routing and
“Hello” protocol
 Netfilter-based module
implements support for
on-demand routing
Interface
66
Channel abstraction layer
Address Mapping
Inte Tablel
Unicast
192.168.0.2
ath0
1
192.168.0.3
ath1
2
192.168.0.4
ath1
3
Add Packet
to
Queue
Channel Mapping
Interface
Broadcast
Table
1
ath0
2
ath1
3
ath1
1
2
3
Schedule
packet transmissions
67
Testbed measurements



We use Netgear cards based on atheros chipset
Madwifi driver has been modified to reduce
switching delay
Measured switching delay is approx. 5 milliseconds
68
Aggregate throughput (Mbps)
25
20
A
B
D
C
Throughput
4 flows: A->B, B->C, C->D, D->A
8 flows: In addition A->D, B->A, C->B, D->C
4 flows
8 flows
Channel data rate is 6 Mbps
15
10
5
0
2
Number of channels
4
69
Conclusion



Capacity results hint at significant
performance benefits using
many channels with few interfaces
Need suitable protocols to exploit the channels
Project status:
Protocols developed, but will continue being improved in scope
and performance
Testbed being grown in size
Performance measurements pending
70
Thanks!
www.crhc.uiuc.edu/wireless
71