Transcript ppt

15-744: Computer Networking
L-18 Mobile Transport and
Applications
Mobile Issues
• Transport
• Applications
• Assigned reading
• [FGBA95] Adapting to Network and Client
Variability via On-Demand Dynamic Distillation
• [BPSK97] A Comparison of Mechanism for
Improving TCP Performance over Wireless
Links
© Srinivasan Seshan, 2001
L -18; 3-19-01
2
Wireless Challenges
• Force us to rethink many assumptions
• Need to share airwaves rather than wire
• Don’t know what hosts are involved
• Host may not be using same link technology
• Mobility
• Other characteristics of wireless
• Noisy  lots of losses
• Slow
• Interaction of multiple transmitters at receiver
• Collisions, capture, interference
• Multipath interference
© Srinivasan Seshan, 2001
L -18; 3-19-01
3
Overview
• TCP Over Noisy Links
• Adapting Applications to Slow Links
© Srinivasan Seshan, 2001
L -18; 3-19-01
4
TCP Problems Over Noisy Links
• Wireless links are inherently error-prone
• Fades, interference, attenuation
• Errors often happen in bursts
• TCP cannot distinguish between corruption
and congestion
• TCP unnecessarily reduces window, resulting
in low throughput and high latency
• Burst losses often result in timeouts
• Sender retransmission is the only option
• Inefficient use of bandwidth
© Srinivasan Seshan, 2001
L -18; 3-19-01
5
Constraints & Requirements
• Incremental deployment
• Solution should not require modifications to
fixed hosts
• If possible, avoid modifying mobile hosts
• Probably more data to mobile than from
mobile
• Attempt to solve this first
© Srinivasan Seshan, 2001
L -18; 3-19-01
6
Challenge #1: Wireless Bit-Errors
Router
Computer 1
Computer 2
Loss  Congestion
3
2
22
1
0
Loss  Congestion
Burst losses lead to coarse-grained timeouts
Wireless
Result: Low throughput
© Srinivasan Seshan, 2001
L -18; 3-19-01
7
Performance Degradation
Sequence number (bytes)
2.0E+06
Best possible
TCP with no errors
(1.30 Mbps)
1.5E+06
TCP Reno
(280 Kbps)
1.0E+06
5.0E+05
0.0E+00
0
10
20
30
40
50
60
Time (s)
2 MB wide-area TCP transfer over 2 Mbps Lucent WaveLAN
© Srinivasan Seshan, 2001
L -18; 3-19-01
Proposed Solutions
• End-to-end protocols
• Selective ACKs, Explicit loss notification
• Split-connection protocols
• Separate connections for wired path and
wireless hop
• Reliable link-layer protocols
• Error-correcting codes
• Local retransmission
© Srinivasan Seshan, 2001
L -18; 3-19-01
9
Approach Styles (End-to-End)
• Improve TCP implementations
• Not incrementally deployable
• Improve loss recovery (SACK, NewReno)
• Help it identify congestion (ELN, ECN)
• ACKs include flag indicating wireless loss
• Trick TCP into doing right thing  E.g. send extra dupacks
• What is SMART?
• DUPACK includes sequence of data packet that triggered it
Wired link
© Srinivasan Seshan, 2001
Wireless link
L -18; 3-19-01
10
Approach Styles (Split Connection)
• Split connections
• Wireless connection need not be TCP
• Hard state at base station
• Complicates mobility
• Vulnerable to failures
• Violates end-to-end semantics
Wired link
© Srinivasan Seshan, 2001
Wireless link
L -18; 3-19-01
11
Congestion Window (bytes)
Split-Connection Congestion Window
60000
Wired connection
Wireless connection
50000
40000
30000
20000
10000
0
0
20
40
60
80
100
120
Time (sec)
• Wired connection does not shrink congestion window
• But wireless connection times out often, causing sender to
stall
© Srinivasan Seshan, 2001
L -18; 3-19-01
Approach Styles (Link Layer)
• More aggressive local rexmit than TCP
• Bandwidth not wasted on wired links
• Adverse interactions with transport layer
• Timer interactions
• Interactions with fast retransmissions
• Large end-to-end round-trip time variation
• FEC does not work well with burst losses
Wired link
Wireless link
ARQ/FEC
© Srinivasan Seshan, 2001
L -18; 3-19-01
13
Hybrid Approach: Snoop Protocol
• Shield TCP sender from wireless vagaries
• Eliminate adverse interactions between protocol layers
• Congestion control only when congestion occurs
• The End-to-End Argument [SRC84]
• Preserve TCP/IP service model: end-to-end semantics
• Is connection splitting fundamentally important?
• Eliminate non-TCP protocol messages
• Is link-layer messaging fundamentally important?
Fixed to mobile: transport-aware link protocol
Mobile to fixed: link-aware transport protocol
© Srinivasan Seshan, 2001
L -18; 3-19-01
14
Snoop Overview
• Modify base station
• to cache un-acked TCP packets
• … and perform local retransmissions
• Key ideas
• No transport level code in base station
• When node moves to different base station,
state eventually recreated there
© Srinivasan Seshan, 2001
L -18; 3-19-01
15
Snoop Protocol: CH to MH
4 3 2 1
Snoop Agent
6 5
Correspondent
Host
1
Base Station
• Snoop agent: active interposition agent
• Snoops on TCP segments and ACKs
• Detects losses by duplicate ACKs and timers
• Suppresses duplicate ACKs from FH sender
© Srinivasan Seshan, 2001
L -18; 3-19-01
Mobile Host
Snoop Protocol: CH to MH
Snoop Agent
65 3 2
4 1
Correspondent
Host
Base Station
• Transfer of file from CH to MH
• Current window = 6 packets
© Srinivasan Seshan, 2001
L -18; 3-19-01
Mobile Host
Snoop Protocol: CH to MH
65
Snoop Agent
4
3
Correspondent
Host
2
1
Base Station
• Transfer begins
© Srinivasan Seshan, 2001
L -18; 3-19-01
Mobile Host
Snoop Protocol: CH to MH
4 3 2 1
6 5
Correspondent
Host
Snoop Agent
1
Base Station
Mobile Host
• Snoop agent caches segments that pass by
© Srinivasan Seshan, 2001
L -18; 3-19-01
Snoop Protocol: CH to MH
4 3 2 1
6 5
Correspondent
Host
3 2 1
Base Station
Mobile Host
1
• Packet 1 is Lost
© Srinivasan Seshan, 2001
Snoop Agent
L -18; 3-19-01
Lost Packets
Snoop Protocol: CH to MH
5 4 3 2 1
6
Snoop Agent
4 3
2
ack 0
Correspondent
Host
Base Station
1
• Packet 1 is Lost
• Duplicate ACKs generated
© Srinivasan Seshan, 2001
Mobile Host
L -18; 3-19-01
Lost Packets
Snoop Protocol: CH to MH
6
5 4 3 2 1
Snoop Agent
6
5
1
4
3
2
ack 0
Correspondent
Host
Base Station
ack 0
Mobile Host
1
Lost Packets
• Packet 1 is Lost
• Duplicate ACKs generated
• Packet 1 retransmitted from cache at higher priority
© Srinivasan Seshan, 2001
L -18; 3-19-01
Snoop Protocol: CH to MH
6
5 4 3 2 1
Snoop Agent
6
5
1
4
3
2
ack 4
Correspondent
Host
Base Station
ack 0
X
• Duplicate ACKs suppressed
© Srinivasan Seshan, 2001
L -18; 3-19-01
Mobile Host
Snoop Protocol: CH to MH
6
5
Snoop Agent
6
5 1
4
3
2
ack 5
Correspondent
Host
Base Station
ack 4
• Clean cache on new ACK
© Srinivasan Seshan, 2001
L -18; 3-19-01
Mobile Host
Snoop Protocol: CH to MH
6
ack 4
Correspondent
Host
6 51
4
3
2
ack 6
Base Station
ack 5
• Clean cache on new ACK
© Srinivasan Seshan, 2001
Snoop Agent
L -18; 3-19-01
Mobile Host
Snoop Protocol: CH to MH
Snoop Agent
9
8
Correspondent
Host ack 5
7
Base Station
ack 6
• Active soft state agent at base station
• Transport-aware reliable link protocol
• Preserves end-to-end semantics
© Srinivasan Seshan, 2001
L -18; 3-19-01
6 51
4
3
2
Mobile Host
Snoop Data Processing
Packet arrives
New pkt?
No
Sender retransmission
Yes
In-sequence?
1. Forward pkt
2. Reset local rexmit
counter
No
1. Mark as cong. loss
2. Forward pkt
Congestion loss
Yes
1. Cache packet
2. Forward to
mobile
Common case
© Srinivasan Seshan, 2001
L -18; 3-19-01
27
Snoop ACK Processing
Ack arrives (from mobile host)
New ack?
Yes
No
Discard
No
Spurious ack
Discard
Common case
Dup ack?
Yes
No
> threshold
Yes
Later dup acks
for lost packet
© Srinivasan Seshan, 2001
1. Free buffers
2. Update
RTT estimate
3. Propagate
ack to sender
Retransmit
lost packet
Next pkt lost
L -18; 3-19-01
28
Snoop Performance Improvement
Best
possible
TCP
(1.30
Mbps)
Sequence number (bytes)
2.0E+06
1.5E+06
Snoop
(1.11
Mbps)
TCP Reno
(280 Kbps)
1.0E+06
5.0E+05
0.0E+00
0
10
20
30
40
50
60
Time (s)
2 MB wide-area TCP transfer over 2 Mbps Lucent WaveLAN
© Srinivasan Seshan, 2001
L -18; 3-19-01
Congestion Window (bytes)
Benefits of TCP-Awareness
Snoop
60000
50000
40000
30000
20000
10000
0
LL (no duplicate ack suppression)
0
10
20
30
40
50
60
70
80
Time (sec)
• 30-35% improvement for Snoop: LL congestion window is small (but
no coarse timeouts occur)
• Connection bandwidth-delay product = 25 KB
• Suppressing duplicate acknowledgments and TCP-awareness leads
to better utilization of link bandwidth and performance
© Srinivasan Seshan, 2001
L -18; 3-19-01
Performance: FH to MH
1.6
1.4
Throughput (Mbps)
Snoop+SACK
1.2
Snoop
1
SPLIT-SACK
Typical error rates
TCP SACK
0.8
SPLIT
0.6
TCP Reno
0.4
• Snoop+SACK
and Snoop
perform best
• Connection
splitting not
essential
• TCP SACK
performance
disappointing
0.2
0
0
500
1000
1500
2000
2500
1/Bit-error Rate (1 error every x Kbits)
2 MB local-area TCP transfer over 2 Mbps Lucent WaveLAN
© Srinivasan Seshan, 2001
L -18; 3-19-01
31
Other Issues
• What about mobility?
• What about mobile-to-fixed communication?
© Srinivasan Seshan, 2001
L -18; 3-19-01
32
Handling Mobility
5
Router
4
Correspondent
Host
Send packets to multiple
base stations
3
1
2
Base Station
2
1
Base Station
1
Mobile Host
© Srinivasan Seshan, 2001
L -18; 3-19-01
33
Handling Mobility
6
Router
5
Resend missed packets from
Snoop cache on handoff
Correspondent
Host
4
1
2
3
Base Station
3
1 2
Base Station
1
Mobile Host
© Srinivasan Seshan, 2001
L -18; 3-19-01
34
Snoop Protocol: MH to CH
65
43
2
Mobile Host
0
1
Base Station
• Caching and retransmission will not work
• Losses occur before packet reaches BS
• Congestion losses should not be hidden
• Solution: Explicit Loss Notifications (ELN)
• In-band message to TCP sender
© Srinivasan Seshan, 2001
L -18; 3-19-01
Correspondent Host
Snoop Protocol: MH to CH
65
4321
0
Mobile Host
Base Station
• MH begins transfer to CH
© Srinivasan Seshan, 2001
L -18; 3-19-01
Correspondent Host
Snoop Protocol: MH to CH
65
43
2
Mobile Host
0
1
Base Station
• Packet 1 lost on wireless link
© Srinivasan Seshan, 2001
L -18; 3-19-01
Correspondent Host
Snoop Protocol: MH to CH
65
4
Mobile Host
1
0
1
3
2
ack 0
Base Station
Receiver
Lost Packets
• Add 1 to list of holes after checking for congestion
© Srinivasan Seshan, 2001
L -18; 3-19-01
Snoop Protocol: MH to CH
3 2 0
1
6 5 4
Mobile Host
1
ack 0
ack 0
Base Station
Lost Packets
• Duplicate ACKs sent
© Srinivasan Seshan, 2001
L -18; 3-19-01
Correspondent Host
Snoop Protocol: MH to CH
5 4 320
1
6
Mobile Host
1
ack 0
ack 0
ELN
ack 0
Base Station
Lost Packets
• ELN information added to duplicate ACKs
© Srinivasan Seshan, 2001
L -18; 3-19-01
Correspondent Host
Snoop Protocol: MH to CH
ack 0
ELN
56 4 320
1
1
Mobile Host
1
ack 0
ELN
ack 0
Base Station
Correspondent Host
Lost Packets
• ELN information on duplicate ACKs
• Retransmit on Packet 1 on dup ACK + ELN
• No congestion control now
© Srinivasan Seshan, 2001
L -18; 3-19-01
Snoop Protocol: MH to CH
5614 320
Mobile Host
ack 6
Base Station
Receiver
• Clean holes on new ACK
• Link-aware transport decouples congestion control from loss
recovery
• Technique generalizes nicely to wireless transit links
© Srinivasan Seshan, 2001
L -18; 3-19-01
Overview
• TCP Over Noisy Links
• Adapting Applications to Slow Links
© Srinivasan Seshan, 2001
L -18; 3-19-01
43
Adapting Applications
• Applications make key assumptions
• Hardware variation
• E.g. how big is screen?
• Software variation
• E.g. is there a postscript decoder?
• Network variation
• E.g. how fast is the network?
• Reason why we are discussing in this class 
• Basic idea – distillation
• Transcode object to meet needs of mobile host
© Srinivasan Seshan, 2001
L -18; 3-19-01
44
Transcoding Example
• Generate reduced
quality variant of Web
page at proxy
• Must predict how much
size reduction will result
from transcoding
• How long to transcode?
• Send appropriate
reduced-size variant
• Target response time?
© Srinivasan Seshan, 2001
L -18; 3-19-01
45
Source Adaptation
• Can also just have source
provide different versions
• Common solution today
• No waiting for transcoding
• Full version not sent across
network
• Can’t handle fine grain adaptation
© Srinivasan Seshan, 2001
L -18; 3-19-01
46
Next Lecture: Active Networks
• Active networks
• Active services
• Assigned reading
• [W99] Active network vision and reality: lessons
from a capsule-based system
• [AMK98] An Active Service Framework and its
Application to Real Time Multimedia
Transcoding
© Srinivasan Seshan, 2001
L -18; 3-19-01
47