Transcript CMPE 293: Wireless and Mobile Networking

CMPE 257: Wireless and
Mobile Networking
Spring 2002
Week 7
CMPE 257 Spring 2002
1
Announcements



Grades up to report 3 are out.
Midterm next class.
Reading assignment 4 due May 17.
CMPE 257 Spring 2002
2
Today

Transport layer (cont’d).



TCP over satellite.
TCP over MANETs.
Reliable multicast.
CMPE 257 Spring 2002
3
Transport Layer: Outline
 TCP/IP basics.
 Impact of transmission errors on TCP
performance.
 Approaches to improve TCP performance.




Classification.
Discussion of selected approaches.
TCP over satellite.
Issues in MANETs.
CMPE 257 Spring 2002
4
TCP Over Satellite
CMPE 257 Spring 2002
5
Satellite Links


High bandwidth-delay product.
Higher error rates than terrestrial links.
CMPE 257 Spring 2002
6
Improving TCP over Satellite


Extension of sequence number space with
timestamp option.
Larger congestion window (window scale
option)



Maximum window size up to 2^30 (instead of
2^16) bytes.
Acknowledge every packet (do not delay
acks).
Selective acks

Allow multiple packet recovery per RTT and avoid
slow-start.
CMPE 257 Spring 2002
7
Some Proposals


Space Communications Protocol StandardTransport Protocol (SCPS-TP) [Durst96].
During link outage, TCP sender freezes itself,
and resumes when link is restored




Outage assumed to occur in both directions
simultaneously
Ground station can detect outage of incoming link
(for instance, by low signal levels).
Sender does not unnecessarily timeout or
retransmit until it is informed that link has
recovered.
Sack to recover losses quickly.
CMPE 257 Spring 2002
8
Some Proposals (Cont’d)



Satellite Transport Protocol (STP)
[Henderson98]
Uses split connection approach.
Protocol on satellite channel different from
TCP.



Sacks when receiver detects losses.
Transmitter periodically requests receiver to ack
received data.
Reduces reverse channel bandwidth usage when
losses are rare.
CMPE 257 Spring 2002
9
Some Proposals (Cont’d)

TCP Spoofing





Early ACKing.
A la Snoop TCP.
Ground station acks packets
Should take responsibility for delivering
packets.
Early acks from ground station result in
faster congestion window growth.
CMPE 257 Spring 2002
10
TCP in Mobile Ad Hoc
Networks
CMPE 257 Spring 2002
11
Issues

Route changes due to mobility.



Wireless transmission errors.


Problem compounded due to multiple hops.
Out-of-order packet delivery.


Route change frequency.
Route establishment delay.
Frequent route changes may cause OOO delivery.
MAC.

MAC protocol can impact TCP performance.
CMPE 257 Spring 2002
12
Throughput over Multi-Hop
Wireless Paths [Gerla99]

When contention-based MAC protocol is
used, connections over multiple hops
are at a disadvantage compared to
shorter connections.


They have to contend for wireless access
at each hop.
Delay or drop probability increases with
number of hops.
CMPE 257 Spring 2002
13
Analysis of TCP Performance
over MANETs [Holland99]



Impact of mobility.
Simulation study.
Performance metric: throughput.

Baseline: ideal (expected) throughput.


Upper bound.
Static network.
CMPE 257 Spring 2002
14
Ideal Throughput


f(i) = fraction of time for which shortest
path length between sender and
destination is I.
T(i) = throughput when path length is I
(no mobility).

Ideal throughput = S f(i) * T(i)
CMPE 257 Spring 2002
15
Throughput versus Hops
1600
1400
1200
1000
800
600
400
200
0
TCP
Throughtput
(Kbps)
1 2 3 4 5 6 7 8 9 1
Number of hops
TCP throughput over 2 Mbps 802.11 MAC,
fixed, linear MANET.
CMPE 257 Spring 2002
16
Throughput versus speed
Throughput decreases with speed…
Ideal
Average
Throughput
Over
50 runs
Actual
Speed (m/s)
CMPE 257 Spring 2002
17
Throughput versus Speed
But not always… 30 m/s
20 m/s
Actual
throughput
Mobility pattern #
CMPE 257 Spring 2002
18
Impact of Mobility
TCP Throughput
2 m/s
10 m/s
Ideal throughput (Kbps)
CMPE 257 Spring 2002
19
Impact of Mobility
20 m/s
30 m/s
Ideal throughput
CMPE 257 Spring 2002
20
Why Throughput Degrades
mobility causes
link breakage,
resulting in route
failure
Route is
repaired
TCP sender
starts sending packets again
No throughput
No throughput
despite route repair
TCP data and acks
en route discarded
CMPE 257 Spring 2002
21
Why Throughput Degrades?
mobility causes
link breakage,
resulting in route
failure
TCP sender
times out.
Backs off timer.
Route is
repaired
TCP sender
resumes
sending
No throughput
No throughput
despite route repair
Larger route repair delays
especially harmful
TCP data and acks
en route discarded
CMPE 257 Spring 2002
22
Why Throughput Improves?
Low Speed Scenario
C
B
D
C
D
B
A
C
B
D
A
A
1.5 second route failure
Route from A to D is broken for ~1.5 second.
When TCP sender times after 1 second, route still broken.
TCP times out after another 2 seconds, and only then resumes.
CMPE 257 Spring 2002
23
Why Throughput Improves?
Higher Speed Scenario
C
B
D
C
D
B
A
C
D
B
A
A
0.75 second route failure
Route from A to D is broken for ~ 0.75 second.
When TCP sender times after 1 second, route is repaired.
CMPE 257 Spring 2002
24
Why Throughput Improves?
General Principle



TCP timeout interval somewhat independent
of speed.
Network state at higher speed, when timeout
occurs, may be more favorable than at lower
speed.
Network state:



Link/route status.
Route caches.
Congestion.
CMPE 257 Spring 2002
25
How to Improve Throughput



Network feedback.
Inform TCP of route failure explicitly.
Let TCP know when route is repaired.



Probing.
Explicit notification.
Reduces repeated TCP timeouts and
backoff.
CMPE 257 Spring 2002
26
Performance Improvement
With feedback
Actual throughput
Without network
feedback
Ideal throughput
2 m/s speed
CMPE 257 Spring 2002
27
Performance Improvement
With feedback
Actual throughput
Without network
feedback
Ideal throughput
30 m/s speed
CMPE 257 Spring 2002
28
throughput as a fraction of
ideal
Performance with Explicit
Notification
1
0.8
Base TCP
0.6
With
explicit
notification
0.4
0.2
0
2
10
20
30
mean speed (m/s)
CMPE 257 Spring 2002
29
Issues: Network Feedback

Network knows best (why packets are lost).
+ Network feedback beneficial.
- Need to modify transport & network layer to
receive/send feedback

Need mechanisms for information exchange
between layers.
CMPE 257 Spring 2002
30
Impact of Caching



Route caching has been suggested as a
mechanism to reduce route discovery
overhead (e.g., DSR).
Each node may cache one or more routes to
given destination.
When route from S to D detected as broken,
node S may:


Use another cached route from local cache, or
Obtain a new route using cached route at another
node.
CMPE 257 Spring 2002
31
To Cache or Not to Cache
Average speed (m/s)
CMPE 257 Spring 2002
32
Why Performance Degrades
With Caching


When a route is broken, route discovery
returns cached route from local cache
or from nearby node.
Cached routes may also be broken.
timeout due
to route failure
timeout, cached timeout, second cached
route is broken
route also broken
CMPE 257 Spring 2002
33
To Cache or Not to Cache




Caching can result in faster route
“repair”.
But, faster does not necessarily mean
correct.
If incorrect repairs occur often enough,
caching performs poorly.
Need mechanisms for determining
when cached routes are stale.
CMPE 257 Spring 2002
34
Caching and TCP Performance


Caching can reduce overhead of route
discovery even if cache accuracy is not
very high.
But if cache accuracy is not high
enough, gains in routing overhead may
be offset by loss of TCP performance
due to multiple timeouts.
CMPE 257 Spring 2002
35
Window Size After Route
Repair


When route breaks: may be too optimistic or
may be too conservative.
Better be conservative than overly optimistic



Reset window to small value after route repair.
TCP needs to be aware of route repair (Route
Failure and Route Re-establishment Notifications).
Impact low on paths with small delay-bw product.
CMPE 257 Spring 2002
36
RTO After Route Repair


If new route longer, RTO may be too small,
leading to timeouts.
New RTO = function of old RTO, old route
length, and new route length.


Example: new RTO = old RTO * new route length
/ old route length
Not evaluated yet.
CMPE 257 Spring 2002
37
Impact of MAC - Delay
Variability





Shared wireless medium (and contention
MACs) causes RTT to be highly variable.
On slow wireless networks, delay is larger.
Large and variable RTTs result in larger RTO.
On packet loss, timeout takes much longer to
occur.
Idle source (waiting for timeout to occur)
lowers TCP throughput.
CMPE 257 Spring 2002
38
Impact of MAC - Delay
Variability [Balakrishnan97]
Basic idea: minimize ack transmissions.




Reduce frequency of send-receive turnaround and
contention between acks and data.
Piggybacking link layer acks with data.
Sending fewer TCP acks - ack every d-th
packet (d may be chosen dynamically).
Ack filtering - older acks in the queue, if new
ack arrives.
CMPE 257 Spring 2002
39
TCP Over Different Routing
Protocols [Dyer2001]

Impact of routing algorithm on TCP
performance.


On-demand versus proactive.


Metrics: connect time, throughput and overhead.
Proactive routing protocol outperforms reactive
ones. Why?
Sender-based heuristic to improve TCP’s
performance.
CMPE 257 Spring 2002
40
Fixed-RTO


TCP does not exponentially backoff the RTO.
Uses sender-based heuristic to distinguish
between congestion and “route failure”
losses.




Route failure assumed if 2 consecutive timeouts.
Unack’d packet retransmitted.
No RTO backoff in the second (and +) timeout.
RTO remains fixed until retransmission is ack’d.
CMPE 257 Spring 2002
41
Out-of-Order Packet Delivery



Route changes may result in out-of-order
(OOO) delivery.
Significantly OOO delivery confuses TCP,
triggering fast retransmit or…
Potential solutions:


Avoid OOO delivery by ordering packets before
delivering to IP layer
Turn off fast retransmit.

Can result in poor performance in presence of congestion
CMPE 257 Spring 2002
42
TCP DOOR [Wang2002]

Detect and respond to out-of-order
(OOO) packets.


Differentiate between OOO and congestion
losses.
OOO delivery caused by:


Retransmissions.
Route changes.
CMPE 257 Spring 2002
43
Detecting OOO



Sender detects OOO ACKs.
Receiver detects OOO data packets.
How would you classify their scheme?
CMPE 257 Spring 2002
44
OOO ACKs

Sequence number of packet being
ACKed: monotonically increasing.



Why? ACKs are not re-transmitted.
When would this not work?
For DUPACKs, add 1-byte to count
DUPACKs.



ADSN: ACK duplication sequence number.
TCP header option.
Each DUPACK carries different ADSN.
CMPE 257 Spring 2002
45
OOO Data Packets


At receiver.
Why comparing sequence numbers doesn’t
work?



Use extra sequence number: incremented with
every data packet, including retransmissions.



Retransmissions: higher sequence #’s can arrive
earlier.
Out-of-sequence event.
2-byte TCP packet sequence number (TPSN) as
TCP option.
Or timestamp.
Sender needs to
be notified.
CMPE 257 Spring 2002
46
OOO Response


At sender.
2 types of response:


Temporary disable congestion control for
fixed time interval T1.
If in congestion avoidance mode in the last
T2 time interval, go back to prior state.
CMPE 257 Spring 2002
47
Evaluation

Simulation environment:


ns-2 + CMU extensions.
Mobility: random way-point.


Workload: single TCP between fixed S and
R with and without congestion.


Comments?
Comments?
What other info will be useful in analysis?
CMPE 257 Spring 2002
48
Results


Significant goodput improvement
(~50%) when 2 response mechanisms
used.
Sender versus receiver detection.



Seem to perform the same.
Correlation between OOO ACKs and data.
Response mechanisms.

Both in place show better performance.
CMPE 257 Spring 2002
49
DSR Caching


With DSR caching enabled, lower
performance improvements.
Claim TCP performance was better than
when caching was off.

Why?
CMPE 257 Spring 2002
50
Reliable Mutlicast in MANETs
CMPE 257 Spring 2002
51
Motivation

Group communication services as
important application class for key
MANET scenarios: special operations,
exploration, etc.


E.g., teleconferencing and data
dissemination.
Multicast: efficient way of delivering
many-to-many data.
CMPE 257 Spring 2002
52
Challenges


Achieve reliability in the presence of constant
mobility, route changes, transmission errors
over multi-hop wireless routes.
MANETs are very sensitive to load and
congestion.



Contention-based MACs.
Hidden terminal problems.
Not much has been done…
CMPE 257 Spring 2002
53
Reliable Broadcast
[Pagani1997]


Special case: all nodes are receivers.
Reliable broadcast: all nodes deliver
same set of messages to application.


“Exactly-once” semantics.
Assumes underlying clustering
algorithm.
CMPE 257 Spring 2002
54
Primitives

rbcast (msg, group-id)


Caller blocks until message received by
clusterhead.
deliver(msg)

Notification of mssage reception by all
other nides.
CMPE 257 Spring 2002
55
Entities
Gateway
Cluterhead
CMPE 257 Spring 2002
56
Protocol





Sender sends message to its clusterhead.
Clusterhead broadcasts message within
cluster and waits for ACKs.
Nodes reply with ACK.
Gateways forward message to directly
connected clusters (through clusterheads).
Gateway delays its ACK until it gets ACK from
corresponding clusterheads.
CMPE 257 Spring 2002
57
Protocol (Cont’d)




If same message received over multiple
paths: clusterhead selects one; piggybacks
the sender id in the message and broadcasts.
Non-selected gateway receives the broadcast
and records it’s the leaf for that message.
Prevents loops, allows multi-path, reduces
duplicates.
Reverse path is recorded: ACKs flow back.
CMPE 257 Spring 2002
58
Failures and Mobility


Timeouts and retransmissions.
Recovery by clusterheads & gateways.
CMPE 257 Spring 2002
59
Summary

2 phases:






Diffusion: message diffused from source to
destinations.
Gathering: source collects ACKs.
On-demand forwarding tree rooted at source.
If “virtual” links break, flooding is used.
Clusterheads buffer messages until ACK
comes back.
Reliability guaranteed as long as “liveness”
property holds.

Topology is stable enough.
CMPE 257 Spring 2002
60
Issues

Larger networks?



What happens when clusterheads and
gateways fail/move?


High delays.
Target smaller groups (10->100???).
Satisfying “liveness” is tricky.
Heavy duty protocol.


State at nodes.
ACKs for reliability.
CMPE 257 Spring 2002
61
Anonymous Gossip
[Chandra2001]

Approach:



Use of underlying “best-effort” multicast
routing mechanism.
Repair losses through gossip-based
propagation.
Gossip propagation is well-known!

Examples?
CMPE 257 Spring 2002
62
Gossip Round



Node A randomly chooses node B.
A and B exchange information on
messages they have and don’t have.
A and B exchange missing messages.
CMPE 257 Spring 2002
63
Anonymity


No need for membership information.
gossip-message and gossip-reply .



Node selects random neighbor and sends
gossip-message.
If node is not group member, selects
neighbor and forwards; if member, decides
to accept or forward.
If accepts, unicasts gossip-reply back.
CMPE 257 Spring 2002
64
Locality

Choosing closer-by or farther members.



Why is this an issue?
Choose near members with higher
probability.
Need to keep extra state: nearest-member.


Extra overhead to maintain this information.
Dependence on the underlying routing
protocol!
CMPE 257 Spring 2002
65
Cached Gossip


Gossip with known members.
member-cache keeps information on
known members.



Updated when messages are received
(data, gossip-reply, RREQ, etc.).
Node uses AG with probability panon;
otherwise cached gossip.
Why cached gossip?
CMPE 257 Spring 2002
66
Performance Evaluation





Simulations using GloMoSim.
M-AODV.
Single source.
Random way-point.
Parameters: range, number of nodes,
and maximum node speed.
CMPE 257 Spring 2002
67
Results




Improves packet delivery ratio.
Overhead?
Delay?
Comparison with flooding?
CMPE 257 Spring 2002
68
CALM [Tang2002]



Like AG, e2e approach.
Initial study comparing SRM to UDP
showed SRM performs badly in
MANETs.
Why?


SRM is heavy duty.
No congestion control!
CMPE 257 Spring 2002
69
Impact of Congestion Control
on Reliability?

CALM uses “rate-based” CC.




Data is sent at application rate.
If congestion, sender clocks sending rate
based on receivers experiencing
congestion.
Congested receivers kept in receiverlist.
Feedback is unicast to the source.

Generated after N consecutive packets are
missing.
CMPE 257 Spring 2002
70
CALM’s State Machine
Send packet,
Send packet, Receiver List not empty
Receiver List empty (addressed to a receiver in list)
Recv ACK, remove
receiver from Receiver List
WF_ACK
TX
* ACK, remove
receiver from Receiver List
* ACK, remove
receiver from Receiver List
Timeout, keep receiver in Receiver List
Has packet to send
IDLE
No packets to send
No packets to send
* ACK, remove
receiver from Receiver List
CMPE 257 Spring 2002
71
Evaluation




Simulations using QualNet.
Comparison between CALM, SRM, and
(multicast) UDP.
ODMRP.
Metrics: packet delivery, overhead,
delay, goodput.
CMPE 257 Spring 2002
72
Results


CALM outperforms SRM.
UDP performs surprisingly well, except
under high traffic loads.



Proves need for congestion control.
SRM’s main problem is extra load
caused by its control packets.
Congestion control helps but still need
relaibility.
CMPE 257 Spring 2002
73
Ongoing Work


RALM: reliability+congestion control.
Make control mechanisms scalable.





Select smaller set of receivers (maybe 1).
Use rate-based CC instead of stop-and-go.
Interaction with MAC layer.
Comparison with AG and use different
routing protocols.
….
CMPE 257 Spring 2002
74