Transcript TCP for Mobile and Wireless Hosts

Some Issues in Ad Hoc Networks
Nitin Vaidya
University of Illinois at Urbana-Champaign
www.crhc.uiuc.edu/~nhv
Keynote talk presented at the International Workshop on
Theoretical Aspects of Wireless Ad Hoc, Sensor, and Peer-to-Peer Networks
Illinois Institute of Technology, Chicago, June 11, 2004
© 2004 Nitin Vaidya
1
Outline

Preliminaries

Advertising

Preaching
2
Ad Hoc Networks


Formed by wireless hosts which may be mobile
Without necessarily using a pre-existing
infrastructure
• Hybrid architectures using infrastructure likely in
many applications
3
Why Ad Hoc Networks ?

Potential ease of deployment

Decreased dependence on infrastructure
4
Many Potential Applications




Personal area networking
cell phone, laptop, ear phone, wrist watch
Military environments
soldiers, tanks, planes
Civilian environments
taxi cab network
meeting rooms
sports stadiums
boats, small aircraft
Emergency operations
search-and-rescue
policing and fire fighting
5
Challenges
(Opportunities)








Broadcast nature of the wireless medium
Limited wireless transmission range
– Hidden terminal problem
Packet losses due to transmission errors
Mobility-induced route changes
Mobility-induced packet losses
Battery constraints
Potentially frequent network partitions
Ease of snooping on wireless transmissions
(security hazard)
6
State of the Art

Lot of research activity on:
Routing
Medium access control
Quality of service
7
State of the Art

More recently …
Capacity of wireless networks << Information theory community
– Pure wireless networks
– Hybrid networks
– Delay-throughput trade-off
Graph-theoretic problems
–
–
–
–
<< Algorithms/theory community
Topology control
Dominating sets
Connectivity problems
Coverage problems in sensor networks
8
State of the Art


Many more (academic) problems … rich area
(Too) Many conferences
MobiHoc
SenSys
MASS
SECON
…
9
What’s Lacking?

Real applications still lacking (beyond military)
Hard to evaluate protocols in a vacuum

But there is hope … applications on the horizon
Community networks starting to use ad hoc routing
Vehicular networks
Sensor networks
10
What’s Lacking

Primitives to build distributed applications
Much work on distributed algorithms on fixed and
dynamic networks wherein dynamism comes from
“random” link failures
But little on ad hoc networks, where the dynamism comes
from node mobility and channel variations
Need to revisit distributed computing problems in the
new context
11
Outline

Preliminaries

Advertising

Preaching
12
Our Research Themes
Exploiting physical layer capabilities




Protocols for directional antennas
Rate adaptation
Power control & Power save mechanisms
Multi-channel mechanisms
13
Our Research Themes
Distributed algorithms for ad hoc networks




Address assignment
Mutual exclusion
Leader election
Token circulation
14
Our Research Themes
Misbehavior in Wireless Networks

Protocol design for misbehavior detection
15
Some of our past research …



Weak duplicate address detection
Misbehavior detection
Mutual exclusion
16
Weak Duplicate Address Detection
17
Address Assignment


Dynamic auto-configuration important for
autonomous operation of an ad hoc network
Goal:
Assign each node a unique address
OR
Assign each address to at most one node

Can be viewed as distributed mutual exclusion with
an address being a resource
18
Auto-Configuration in
Ad Hoc Networks


Worst case network delays may be unknown, or
highly variable, or unbounded
Partitions may occur, and merge
19
Duplicate Address Detection
in Ad Hoc Networks

Several proposals

One example [Perkins]:
Host picks an address randomly
Host performs route discovery for the chosen address
If a route reply is received, address duplication is
detected
20
Example:
Initially Partitioned Network
D’s packets for address a routed to A
21
Merged Network

Duplicate address detection (DAD) important to
avoid misrouting
22
Strong DAD


Detect duplicate addresses within t seconds
Not possible to guarantee strong DAD in presence
of unbounded delays
May occur due to partitions
Even when delays are bounded, bound may be difficult to
calculate
Unknown network size
•
23
DAD

Strong DAD impossible with unbounded delay

How to achieve DAD ?
24
Design Principle
If you cannot solve a problem
Change the problem
25
Weak DAD: Requirement
Packets from a given host to a given address
should be routed to the same destination,
despite duplication of the address
26
Example:
Initially Partitioned Network
D’s packets for address a routed to A
27
Merged Network:
Acceptable Behavior
with Weak DAD
Packets from D
to address a
still routed to
host A
28
Merged Network:
Unacceptable behavior
Packets from D
to address a
routed to
host K instead
of A
29
Weak DAD: Implementation

Integrate duplicate address detection with route
maintenance
30
Weak DAD with Link State Routing


Each host has a unique (with high probability) key
May include MAC address, serial number, …
May be large in size
In all routing-related packets (link state updates)
IP addresses tagged by keys
 (IP, key) pair
31
Weak DAD with Link State Routing

Address duplication not always detected

Duplication detected before misrouting can occur

Weak DAD
 Reliable, but potentially delayed
32
Link State Routing (LSR): Example
33
Weak DAD with LSR
34
Weak DAD with LSR
X
Host X with key K_x joins
and choose IP_A
(address duplication)
35
Weak DAD with LSR
If host D receives a link state
update containing (IP_A, K_x),
host D detects duplication of
address IP_A
Two pairs with identical IP
address but distinct keys imply
duplication
36
Just-in-Time DAD

Duplication detected before routing tables could
be mis-configured
37
Moral of the Story


Traditionally, address assignment and routing are
independent algorithms
Duplicate address detection integrated with route
maintenance can provide stronger properties
38
Misbehavior Handling
Joint work with Pradeep Kyasanur
39
Problem Definition
Access Point

Wireless
channel
A
B

A
Nodes are required to
follow Medium Access
Control (MAC) rules
Nodes can benefit by
misbehaving
B
40
IEEE 802.11 overview


Distributed Coordination Function (DCF)
Widely used for channel access
DCF is a Carrier Sense Multiple Access/ Collision
Avoidance (CSMA/CA) protocol
41
CSMA/CA


Don’t transmit when channel is busy
Defer transmission for a random duration on idle
channel
42
Backoff Example

Choose backoff value B in range [0,CW]

Count down backoff by 1 every idle slot
CW is the Contention Window
B1=15
S1
B1=0
B1=20
Transmit
wait
wait
Transmit
CW=31
S2
B2=25
B2=10
B2=10
43
Possible Misbehavior

Backoff from biased distribution
Example: Always select a small backoff value
B1 = 1
B1 = 1
Misbehaving
node
Transmit
Transmit
Well-behaved
node
wait
wait
B2 = 20
B2 = 19
44
Potential Solutions

Prevent misbehavior

Detect misbehavior

Penalize misbehavior
45
Game Theoretic Solutions [MacKenzie]




Assumes there is some cost for transmitting
Nodes independently adjust access probability
Under some assumptions, network reaches a fair
equilibrium
Game theoretic solutions to the misbehavior
problem so far assume complete knowledge of the
channel (difficult to have in multi-hop networks)
Not yet clear whether partial information is adequate
46
Charging

Charge for transmitted packets

Transmitting more packets costs more

Disadvantages
Per-packet charging can still allow misbehavior that
decreases the user’s delay
Need to implement charging mechanism
47
Goals of proposed scheme

Detect misbehavior

Penalize misbehavior
48
Detecting Misbehavior



Observe each node
If a node does not wait long enough before
transmitting, then conclude that it is misbehaving
Penalize the misbehaving node
49
Issues


Idle duration is a function of backoff interval chosen
by a node
Observer does not know exact backoff value chosen
by a sender



Sender chooses random backoff
Hard to distinguish between maliciously chosen small values and a
legitimate random sequence
Wireless channel introduces uncertainties

Channel status seen by sender and receiver may be different
50
Potential Solution: Use long-term statistics



Observe backoffs chosen by a sender over multiple
packets
Backoff values not from expected distribution
 Misbehavior
Longer delay in detection, since the distribution of
non-deterministic backoff must be determined
51
A Simpler Approach

Remove the non-determinism
52
A Simpler Approach


Receiver provides backoff values to sender
Modification does not significantly change 802.11
behavior
53
Modifications to 802.11
B
Sender
S
Receiver
R
•
R provides backoff B to S
•
S uses B for backoff for next packet
54
Detecting deviations
Backoff
Sender S
Receiver R
Bobsr

Receiver counts number of idle slots Bobsr
Condition for detecting deviations: Bobsr <  B
≤1
55
Misbehavior Detection


The detection would always detect misbehavior IF
all nodes observe identical channel status at all
times
But all nodes do not see same channel status
Hidden terminals
Fading

In general, cannot diagnose misbehavior with 100%
accuracy
56
Penalizing Misbehavior
Actual backoff < B
Sender
S
Receiver
R
Bobsr
When misbehavior is suspected,
larger backoff intervals are assigned
 penalty mechanism
57
Penalty Scheme


Misbehaving sender has two options
Ignore assigned penalty  Easier to detect
Follow assigned penalty  No throughput gain
With penalty, sender has to misbehave more for same
throughput gain
58
Diagnosing Misbehavior


If misbehavior suspected for “long enough” duration,
conclude that the misbehavior is intentional
Higher layers / administrator can be informed of
misbehavior
59
Multiple Observers


Currently, single observer is used (receiver)
Data from multiple observers can be combined to
improve diagnosis
•S sends a packet to R
A
S
B
R
•A, B also monitor S
•Information from A, B, R
may be combined
60
Moral of the Story



MAC layer misbehavior can severely affect throughput
of well-behaved nodes
Improving predictability improves ability to detect
misbehavior
Open issues:
Using multiple observers
Integrating diagnosis with higher layers
61
Distributed Mutual Exclusion
Joint work with Jennifer Welch and
Jennifer Walter
62
Why Design New Algorithms for MANETs?
Approach 1: implement
existing distributed
primitives on top of existing
ad hoc routing protocols.
User Application
Distributed
Primitive
Routing
Protocol
Ad-Hoc Network
Approach 2: modify
distributed primitives to be
aware of information from
lower layers
User Application
Distrib. Routing
Primitive Protocol
Ad-Hoc Network
63
Distributed Mutual Exclusion



Token-based: Only the node possessing the token
may enter critical section
Nodes must have a way of sending requests to the
token holder
One solution:
Mutual exclusion for fixed topology
+
Routing on ad hoc networks
64
Link Reversal Algorithm [Gafni81]
(Routing Protocol)
A
B
F
C
E
G
D
65
Link Reversal Algorithm [Gafni81]
A
B
F
Links are bi-directional
But algorithm imposes
logical directions on them
C
E
D
G
Maintain a directed acyclic
graph (DAG) for each
destination, with the destination
being the only sink
This DAG is for destination
node D
66
Link Reversal Algorithm
A
B
F
C
E
G
Link (G,D) broke
D
Any node, other than the destination, that has no outgoing links
reverses all its incoming links.
67
Node G has no outgoing links
Link Reversal Algorithm
A
B
F
C
E
G
Represents a
link that was
reversed recently
D
Now nodes E and F have no outgoing links
68
Link Reversal Algorithm
A
B
F
C
E
G
Represents a
link that was
reversed recently
D
Now nodes B and G have no outgoing links
69
Link Reversal Algorithm
A
B
F
C
E
G
Represents a
link that was
reversed recently
D
Now nodes A and F have no outgoing links
70
Link Reversal Algorithm
A
B
F
C
E
G
Represents a
link that was
reversed recently
D
Now all nodes (other than destination D) have an outgoing link
71
Link Reversal Algorithm
A
B
F
C
E
G
D
DAG has been restored with only the destination as a sink
72
Link Reversal Algorithm

Goal: Maintain DAG pointing to the “destination”
despite topology changes
73
Mutual Exclusion in Static Networks
[Raymond89]


Static topology
Spanning tree with edges directed toward the
token holder
A
B
D
C
E
F
74
A
B
D
C
E
F
A
B
D
C
E
F
75
Raymond’s Algorithm on Ad Hoc Networks

The algorithm can be implemented on top of
routing protocol
– Routing algorithms provides abstraction of a fully
connected network


Maintain a spanning tree using logical links in the
“fully connected” network
“Adjacent” nodes in the spanning tree may be far
from each other  Potentially poor performance
76
Mutual Exclusion in Ad Hoc Networks

Gafni  Variable topology, fixed sink

Raymond  Fixed topology, moving sink

Proposed algorithm:
Mutual exclusion in ad hoc networks
 Variable topology, moving sink
77
Moral of the Story



Existing algorithms not always appropriate
Algorithms for dynamic networks can be applied to
ad hoc networks, but performance may be poor
Taking into consideration lower layer information
can help
78
On to the preaching …
79
Abstractions



Of necessity, algorithm designers work with
abstractions
Physical layer is messy
Abstractions hide “unnecessary” physical layer
details
80
Abstractions

But some details are important.
Many common mistakes.

I am guilty too … but hopefully learning from the
mistakes
81
Transmission “Range”

Transmission range R
R
82
Transmission “Range”




Given the thermal noise, beyond a certain distance
reliable communication infeasible at a desired rate
Converse often assumed true: Within transmission
range, reliable communication is assumed always
feasible
This assumption is not accurate
• Reliability depends on SINR
Assumption may perhaps be OK for order
statistics, but the constants matter in practice
83
Interference “Range”



Interference “range” assumed to be the distance
over which a transmission “collides” with another
transmission
Assumed that if a host transmits, no other
transmission within interference range will
succeed
Not accurate: Reliability depends on SINR
84
Interference “Range”
Whether A’s interference
results in unreliable
reception at D
depends on SINR at D
Interference
“range”
DATA
A
B
C
D
E
F
85
Graceful Degradation


Transmission “range” (or reliability) depends on
SINR and bit rate
Even if transmission at a higher rate fails, low
rate transmission may be feasible
Modulation schemes provide
a trade-off between
throughput and “range”
Throughput
Distance
86
Energy Consumption

Common assumption:
Energy required to transmit on a hop


=
k dθ
k and θ typically assumed to be constants
Proofs relying on constant k, θ may break when
they are not constants
87
Energy Consumption


When k,θ = constant, links AC and BD cannot
BOTH be on energy efficient routes (considering
only transmit energy)
With constant k,θ, energy efficient routes do not
need to intersect [Narayanaswamy02]
C
B
A
D
88
Energy Consumption



Consider routes AC and BD
With fixed k and fixed θ > 2, energy optimal
routes are A-B-C and B-C-D (direct links A-C and
B-D are not optimal)
Energy-efficient routes do not intersect
4
B
5
5
3
A
C
4
3
D
89
Energy Consumption



Let k be much smaller on diagonal links
(alternatively, θ ≈ 2 on diagonal links, and 3 on
other links)
Diagonal links cheaper than other routes
Energy efficient routes must intersect
4
B
C
5
5
3
A
4
3
D
90
Geographic Location



Many algorithms rely on knowledge of physical
location
Location estimates in practice contain some error
The error can affect correctness of geographic
routing [Saeda04]
91
Summary

Physical layer characteristics matter

Can affect algorithm performance and correctness
92
End of preaching …
93
Interesting Open Problems


Protocols that achieve “capacity”
Distributed algorithms for ad hoc networks
Shared memory
Message ordering
Group communication
…

Complexity as a function of mobility

Applications for ad hoc networks
94
Thanks!
http://www.crhc.uiuc.edu/wireless/
95
Thanks!
http://www.crhc.uiuc.edu/wireless/
96
Handling other misbehavior


Receiver may misbehave by assigning large or small
backoff values
Sender can detect receiver assigning small backoff
values
Backoff assigned by receiver has to follow well-known
distribution
Sender uses larger of assigned backoff and expected backoff
97
Handling other misbehavior


Detecting receiver assigning large backoff values not
handled
Equivalent to receiver not responding at all
Need higher layer mechanisms
Collusion between sender and receiver
Harder to detect
Requires an observer that can monitor both sender and
receiver
98