E2E Protocols

cmpe 257: wireless and
mobile networking
katia obraczka
computer engineering
ucsc baskin engineering
lecture 9
cmpe 257 winter 11
1student presentations
• feb 28:
• march 9:
– mobility
management: tyler
and niosha.
• march 2:
– dtns: philip and
rance.
• march 7:
– energy
management:
mohamed.
– security: jim.
• march 14:
– security: chris and
and seth.
– hybrid networks:
gregg and darien.
cmpe 257 winter 11
2schedule
• exam: feb 23.
• project presentations: march 17.
– time change: 5-8pm.
– approximately 15 minutes for each
presentation.
cmpe 257 winter 11
3today
• end-to-end protocols.
cmpe 257 winter 11
4e2e protocols
• reliable point-to-point.
• reliable multipoint.
cmpe 257 winter 11
5reliable point2point transport
layer: outline
• tcp/ip basics.
• impact of transmission errors on tcp
performance.
• approaches to improve tcp performance on
wireless networks.
– classification.
• tcp on cellular.
• tcp on manets.
cmpe 257 winter 11
6internet protocol (ip)
• best-effort service:
– packets may be delivered out-of-order.
– packets may be lost.
– packets may be duplicated.
cmpe 257 winter 11
7transmission control protocol
•
•
•
•
reliable ordered delivery.
implements flow and congestion control.
reliability through retransmissions.
end-to-end semantics:
– acks sent to tcp sender confirm delivery of data
by tcp receiver.
– ack for data sent only after it reached receiver.
cmpe 257 winter 11
8tcp basics
• cumulative acknowledgements.
– ack i acknowledges receipt of packets
through (i-1).
• tcp uses byte sequence numbers.
– for simplicity, usually refer to packet
sequence numbers.
cmpe 257 winter 11
9cumulative acks
• new ack generated only on receipt of
new in-sequence packet.
40
39
33
41
38
34
40
34
37
35
39
35
cmpe 257 winter 11
36
38
36
37
10delayed acks
• ack delayed until:
– another packet is received, or
– delayed ack timer expires (200 ms
typical)
• reduces ack traffic.
cmpe 257 winter 11
11delayed acks
new ack not produced
on receipt of packet 36,
but on receipt of 37
40
39
38
33
41
37
35
40
39
35
cmpe 257 winter 11
38
37
12duplicate acks
• a dupack is generated whenever an
out-of-order segment arrives at the
receiver.
cmpe 257 winter 11
13duplicate acks
40
39
38
37
34
42
41
36
40
36
(above example assumes delayed acks)
cmpe 257 winter 11
39
36
dupack
on receipt of 38
14duplicate acks
• duplicate acks are not delayed.
• duplicate acks may be generated
when:
– a packet is lost, or
– a packet is delivered out-of-order (ooo).
cmpe 257 winter 11
15out-of-order packets
40
39
37
38
34
41
40
36
39
37
36
36
dupack
on receipt of 37
cmpe 257 winter 11
16number of dupacks
40
39
new ack
41
37
42
new ack
34
40
new ack 34
38
39
36
37
new ack 36 dupack 36
41
new ack 36
40
39
dupack 36 new ack 38
cmpe 257 winter 11
17window-based control
• sliding window protocol.
• window size minimum of
– receiver’s advertised window – function of
available receiver buffer size.
– congestion window - determined by
sender based on feedback from the
network
cmpe 257 winter 11
18sliding window
sender’s window
1 2 3 4 5 6 7 8 9 10 11 12 13
acks received
not transmitted
ack 5
1 2 3 4 5 6 7 8 9 10 11 12 13
sender’s window
cmpe 257 winter 11
19self-clocking
• new data sent when old data is ack’d.
• helps maintain “equilibrium”.
• congestion window size bounds the
amount of data that can be sent per
round-trip time.
• throughput <= w / rtt.
cmpe 257 winter 11
20window size
• ideal size = delay * bandwidth
• what if window size < delay*bw ?
– inefficiency (wasted bandwidth).
• what if > delay*bw ?
– queuing at intermediate routers.
– potential for packet loss.
cmpe 257 winter 11
21tcp packet loss detection
• tcp assumes that packet loss indicates
congestion.
• packet loss detection:
– retransmission timeout (rto).
– duplicate acknowledgements.
cmpe 257 winter 11
22rto
• for very packet transmitted, tcp
sender starts timer.
• if acknowledgement for timed packet
not received before timer=rto, packet
assumed lost.
• rto dynamically calculated.
cmpe 257 winter 11
23rto calculation
• rto = mean + 4 mean deviation.
• large variations in the rtt increase the
deviation, leading to larger rto.
cmpe 257 winter 11
24exponential backoff
• double rto on each timeout
t1
t2 = 2 * t1
timeout interval doubled
packet
transmitted
time-out occurs
before ack received,
packet retransmitted
cmpe 257 winter 11
25duplicate acks
• timeouts can take too long.
• how to initiate retransmission sooner?
– use duplicate acks as loss indicator.
• dupacks may be generated due to:
– packet loss, or
– out-of-order packet delivery.
• tcp sender assumes packet loss if it
receives 3 consecutive dupacks.
cmpe 257 winter 11
26note on duplicate acks
12 8 11 10 9 7
3 dupacks are also generated if a packet
is delivered at least 3 places beyond its
in-sequence location
cmpe 257 winter 11
27tcp congestion control
•
•
•
•
•
slow start.
congestion avoidance.
fast retransmit.
fast recovery.
selective acknowledgements (sack).
cmpe 257 winter 11
28slow start
• initially, cwnd = 1 mss (max. segment size).
• increment cwnd by 1 mss on each new ack.
• slow start ends when cwnd reaches the slow-
start threshold.
• cwnd grows exponentially in slow start.
– factor of 1.5 per rtt if every other packet ack’d.
– factor of 2 per rtt if every packet ack’d.
– could be less if sender does not always have data
to send.
cmpe 257 winter 11
29congestion avoidance
• on each new ack, increase cwnd by 1/
cwnd packets.
• cwnd increases linearly with time
during congestion avoidance.
– 1/2 mss per rtt if every other packet
ack’d.
– 1 mss per rtt if every packet ack’d.
cmpe 257 winter 11
30window
(segments)
14
congestion
avoidance
12
10
slow start
threshold
8
6
4
slow start
2
0
0
1
2
3
4
5
6
7
8
time (round trips)
assumes acks are not delayed.
cmpe 257 winter 11
31congestion?
• on detecting a packet loss, tcp sender
assumes network congestion.
cmpe 257 winter 11
32timeout
• on a timeout, slow start is invoked.
– cwnd is reduced to the initial value of 1
mss.
• slow start threshold is set to half the
window size before packet loss, or:
ssthresh = maximum(min(cwnd,receiver’s
advertised window)/2,2 mss).
cmpe 257 winter 11
33timeout (cont’d...)
after timeout
cwnd = 20
20
15
10
ssthresh = 10
ssthresh = 8
5
6
0
window
(segments)
25
time (round trips)
cmpe 257 winter 11
34fast retransmit
• when sender receives multiple (>= 3)
duplicate acks, assumes packet lost
without waiting for timeout.
– retransmits packet.
• tcp tahoe: slow start, congestion
avoidance, fast retransmit.
cmpe 257 winter 11
35fast recovery
• avoids slow start after single packet loss.
• operates in conjunction with fast retransmit.
• after tcp sender receives 3 duplicate acks:
–
–
–
–
retransmits one packet.
reduces cwnd by half.
every subsequent duplicate ack clocks transmission.
new ack causes sender to exit fast recovery.
cmpe 257 winter 11
36fast recovery
• ssthresh =
min(cwnd, receiver’s advertised window)/2
(at least 2 mss)
• retransmit the missing segment (fast retransmit)
• cwnd = ssthresh + number of dupacks
• when a new ack comes: cwnd = ssthreh
– enter congestion avoidance.
congestion window cut in half.
cmpe 257 winter 11
37(segments)
9
8
7
6
5
4
3
2
1
0
after fast recovery
0
2
4
6
8
10
12
14
time (round trips)
after fast retransmit and fast recovery window size is
reduced in half.
cmpe 257 winter 11
38tcp reno
•
•
•
•
slow-start
congestion avoidance
fast retransmit
fast recovery
cmpe 257 winter 11
39other tcp variants
reno still suffers when multiple losses per rtt.
• tcp new-reno
– stay in fast recovery until all packet losses in window are
recovered.
– can recover 1 packet loss per rtt without
causing a timeout.
• selective acknowledgements (sack) provides
information about out-of-order packets received by
receiver.
– can recover multiple packet losses per rtt.
cmpe 257 winter 11
40impact of transmission errors
on tcp performance
cmpe 257 winter 11
41random errors
• if number of errors is small, they may be
corrected by an error correcting code.
• excessive bit errors result in packet
being discarded, possibly before it
reaches the transport layer.
cmpe 257 winter 11
42random errors may cause
fast retransmit
40
39
38
37
34
36
example assumes delayed ack - every other packet ack’d
cmpe 257 winter 11
43random errors may cause
fast retransmit
41
40
34
39
38
36
example assumes delayed ack - every other packet ack’d
cmpe 257 winter 11
44random errors may cause
fast retransmit
42
41
40
36
39
36
dupack
duplicate acks are not delayed
cmpe 257 winter 11
45random errors may cause
fast retransmit
43
42
41
36
40
36
36
duplicate acks
cmpe 257 winter 11
46random errors may cause
fast retransmit
44
43
42
36
41
36
36
3 duplicate acks trigger
fast retransmit at sender
cmpe 257 winter 11
47random errors may cause
fast retransmit
• fast retransmit results in:
– retransmission of lost packet.
– reduction in congestion window.
• reducing congestion window in
response to transmission errors is
unnecessary.
cmpe 257 winter 11
48observations
• sometimes congestion response may be appropriate in
response to random errors.
• example: errors may occur due to interference from other
users or noise.
– interference due to other users is an indication of
congestion, and thus it is appropriate to reduce congestion
window.
– if noise causes errors, it is not appropriate to reduce window.
• when a channel is in a bad state for a long duration, it
might be better to let tcp backoff, so that it does not
unnecessarily attempt retransmissions.
cmpe 257 winter 11
49burst errors and timeouts
• if wireless link remains unavailable for
extended duration, multiple packets in a
window’s worth of data may be lost.
– driving through a tunnel.
– passing a truck.
• timeout results in slow start.
– slow start reduces congestion window to 1 mss.
reducing throughput.
cmpe 257 winter 11
50impact of transmission errors
• tcp cannot distinguish between packet
losses due to congestion and
transmission errors.
• unnecessarily reduces congestion
window.
• throughput suffers.
cmpe 257 winter 11
51approaches to
improve performance of tcp
in
wireless networks
cmpe 257 winter 11
52classification
• based on who takes the action and
• what kind of action taken.
• e2e versus cross-layer approaches.
– e2e approaches: connection end points try
to distinguish between congestion and non-
congestion losses.
– cross-layer approaches: combination of
e2e and intermediate node participation.
cmpe 257 winter 11
53infrastructure-based wireless
• earlier efforts to improve tcp’s
performance focused on inrastructure-
based wireless environments.
cmpe 257 winter 11
54cross-layer approaches
• link layer error recovery.
• link layer retransmission.
– tcp-awareness.
– tcp-unawareness.
• split connection.
cmpe 257 winter 11
55link layer mechanisms:
error correction
• example: forward error correction (fec) can be
used to correct limited number of errors.
• correctable errors hidden from the tcp sender.
• fec incurs overhead even when errors do not occur
– adaptive fec schemes can reduce the overhead by
choosing appropriate fec dynamically.
cmpe 257 winter 11
56link layer mechanisms:
link level retransmissions
• link level retransmission schemes
retransmit a packet at the link layer, if
errors are detected.
• retransmission overhead incurred only
if errors occur.
cmpe 257 winter 11
57link layer mechanisms
may combine both fec and
retransmissions:
• use fec to correct small number of
errors.
• use link level retransmission when fec
capability is exceeded.
cmpe 257 winter 11
58link level retransmissions
tcp connection
link layer state
application application application
transport transport transport
network network link link link
physical physical physical
rxmt
network
wireless
cmpe 257 winter 11
59link level retransmissions
issues
• how many times to retransmit at the link
level before giving up?
– finite bound semi-reliable link layer
– no bound reliable link layer
• what triggers link level
retransmissions?
– link layer timeout mechanism
– link level acks (negative acks, dupacks,
...)
cmpe 257 winter 11
60link level retransmissions
issues
• how much time is required to trigger link layer
retransmission?
– small fraction of end-to-end tcp rtt.
– multiple of end-to-end tcp rtt.
• should link layer deliver packets as they
arrive, or deliver them in-order?
– link layer may need to buffer packets and reorder
if necessary so as to deliver packets in-order.
cmpe 257 winter 11
61link layer schemes:
summary
when is a reliable link layer beneficial to
tcp performance?
• if it provides almost in-order delivery.
and
• tcp retransmission timeout large
enough to tolerate additional delays due
to link level retransmits.
cmpe 257 winter 11
62cross-layer approaches
• link layer error recovery.
• link layer retransmission.
– tcp-awareness.
– tcp-unawareness.
• split connection.
cmpe 257 winter 11
63tcp-aware link layer
cmpe 257 winter 11
64snoop protocol
[balakrishnan95]
• retains local recovery of split
connection approach.
• link level retransmissions.
• differs from split connection schemes:
– end-to-end semantics retained
– soft state at base station.
cmpe 257 winter 11
65snoop protocol
per tcp-connection state
tcp connection
application application transport transport network network link link link
physical physical physical
fh
bs
application
transport
rxmt
wireless
cmpe 257 winter 11
network
mh
66snoop protocol
• buffers data packets at base station.
– data sent by fh not yet ack’d by mh.
– allow link layer retransmission.
• when dupacks received by bs from mh
(or local timeout), retransmit on wireless
link, if packet in buffer.
• prevents fast retransmit by tcp sender
at fh by suppressing dupacks at bs.
cmpe 257 winter 11
67snoop : example
35
36
tcp state
maintained at
link layer
37
38
40
39
38
fh
37
bs
34
mh
36
example assumes delayed ack - every other packet ack’d
cmpe 257 winter 11
68snoop : example
35
39
36
37
38
41
40
34
39
38
36
cmpe 257 winter 11
69snoop : example
37
40
38
39
42
41
40
36
39
36
dupack
duplicate acks are not delayed
cmpe 257 winter 11
70snoop : example
37 40
38 41
39
43
42
41
36
40
36
36
duplicate acks
cmpe 257 winter 11
71snoop : example
44
37 40
38 41
39 42
43
fh
37
41
bs
dupack triggers retransmission
of packet 37 from base station
bs needs to be tcp-aware to
be able to interpret tcp headers
discard
dupack
mh
36
36
36
cmpe 257 winter 11
72snoop : example
45
37 40
38 41
39 42
44
43
42
37
36
36
36
36
cmpe 257 winter 11
73snoop : example
46
37 40 43
38 41 44
39 42
45
43
42
36
tcp sender does not
fast retransmit
41
36 36
36
cmpe 257 winter 11
74snoop : example
47
37 40 43
38 41 44
39 42 45
46
44
43
41
tcp sender does not
fast retransmit
36 36
36 36
cmpe 257 winter 11
75snoop : example
42 45
43 46
44
48
47
45
fh
44
bs
41
mh
43
36 36
36 36
cmpe 257 winter 11
76performance
bits/sec
2000000
1600000
1200000
base tcp
snoop
800000
400000
0
1/error rate
(in bytes)
2 mbps wireless link
cmpe 257 winter 11
77snoop protocol: advantages
• snoop prevents fast retransmit from
sender despite transmission errors and
out-of-order delivery on the wireless link.
• if wireless link delay-bandwidth product
less than 4 packets: simple (tcp-
unaware) link level retransmission scheme
can suffice.
– since delay-bandwidth product is small,
retransmission scheme can deliver lost packet
without causing
mh to send 3 dupacks.
cmpe 257 winter 11
78snoop protocol: advantages
• higher throughput can be achieved.
• local recovery from wireless losses.
• fast retransmit not triggered at sender
despite out-of-order link layer delivery.
• end-to-end semantics retained.
• soft state at base station.
– loss of the soft state affects performance,
but not correctness.
cmpe 257 winter 11
79snoop
protocol:disadvantages
• link layer at base station needs to be
tcp-aware.
• not useful if tcp headers are encrypted
(ipsec).
• cannot be used if tcp data and tcp
acks traverse different paths.
cmpe 257 winter 11
80delayed dupacks approach
• tcp-unaware approximation of
tcp-aware link layer.
• attempts to imitate snoop without making bs
tcp-aware.
• snoop implements two features at bs:
– link layer retransmission.
– dupack handling: reduced interference between
tcp and link layer retransmissions (droping
dupacks).
cmpe 257 winter 11
81delayed dupacks
• implements same two features:
– at bs : link layer retransmission.
– at mh : reducing interference between tcp
and link layer retransmissions (by delaying
dupacks).
cmpe 257 winter 11
82delayed dupacks protocols
• tcp receiver delays dupacks (third and
subsequent) for interval d, when out-of-order
packets received.
• dupack delay intended to give link level
retransmit time to succeed.
• benefit: delayed dupacks can result in
recovery from a transmission loss without
triggering a response from the tcp sender.
• disadvantage: recovery from congestion
losses delayed.
cmpe 257 winter 11
83delayed dupacks protocols
• delayed dupacks released after interval
d, if missing packet not received.
• link layer maintains state to allow
retransmission.
cmpe 257 winter 11
84delayed dupacks: example
35
36
link layer state
37
38
40
39
38
37
34
36
example assumes delayed ack - every other packet ack’d
link layer acks are not shown
cmpe 257 winter 11
85delayed dupacks: example
36
37
38
39
41
40
39
38
bs
34
35
36
removed from bs link layer buffer on receipt of a
link layer ack (ll acks not shown in figure)
cmpe 257 winter 11
86delayed dupacks: example
37
40
38
39
42
41
40
36
39
36
dupack
duplicate acks are not delayed
cmpe 257 winter 11
87delayed dupacks: example
37 40
38 41
39
43
42
41
36
original ack
40
36
36
duplicate acks
cmpe 257 winter 11
88delayed dupacks: example
37
44
39 41
40 42
43
37
36
dupack
base station forwards dupacks
cmpe 257 winter 11
41
36
dupacks
36
delayed
dupack
89delayed dupacks: example
37 42
40 43
41
45
44
36
42
36
dupacks
37
36
36
cmpe 257 winter 11
delayed dupacks
90delayed dupacks : example
37 43
41 44
42
46
45
43
36
42
41
delayed dupacks are
discarded if lost
packet received before
delay d expires
tcp sender does not
fast retransmit
cmpe 257 winter 11
91delayed dupacks [vaidya99]
2000000
base tcp
1600000
1200000
800000 dupack delay
80ms + ll
retransmit
400000 only ll
retransmit
0
38
1/error rate
(in bytes)
2 mbps wireless duplex link with 20 ms delay
no congestion losses
cmpe 257 winter 11
20 ms
20 ms
10 mbps 2 mbps
92delayed dupacks [vaidya99]
160000
140000
120000
100000
80000
60000
40000
20000
0
base tcp
dupack delay
80ms + ll
retransmit
16
1/error rate
(in bytes)
5% packet loss due to congestion
cmpe 257 winter 11
only ll
retransmit
20 ms
20 ms
10 mbps 2 mbps
93delayed dupacks:
advantages
• link layer need not be tcp-aware.
• can be used even if tcp headers are
encrypted.
• works well for relatively small wireless
rtt (compared to end-to-end rtt).
– relatively small d sufficient in such cases.
cmpe 257 winter 11
94delayed dupacks:
disadvantages
• right value of dupack delay d
dependent on wireless link properties.
• mechanisms to determine d needed.
• delays dupacks for congestion losses
too, delaying congestion loss recovery.
cmpe 257 winter 11
95cross-layer approaches
• link layer error recovery.
• link layer retransmission.
– tcp-awareness.
– tcp-unawareness.
• split connection.
cmpe 257 winter 11
96split connection approach
cmpe 257 winter 11
97split connection approach
• end-to-end tcp connection is broken
into one connection on the wired part of
route and one over wireless part.
cmpe 257 winter 11
98split connection approach
• connection between wireless host mh
and fixed host fh goes through base
station bs.
• fh-mh = fh-bs + bs-mh
fh
fixed host
bs
base station
cmpe 257 winter 11
mh
mobile host
99split connection approach
• split connection results in independent
control for the two parts.
– congestion/error control protocols, packet
size, time-outs, may be different for each
part.
fh
fixed host
bs
base station
cmpe 257 winter 11
mh
mobile host
100split connection approach
per-tcp connection state
tcp connection
tcp connection
application application transport transport transport
network network network
link link link
physical physical physical
rxmt
cmpe 257 winter 11
wireless
application
101split connection approach :
classification
• hides transmission errors from sender
• primary responsibility at base station
• if specialized transport protocol used on
wireless, then wireless host also needs
modification
cmpe 257 winter 11
102split connection approach:
example
• indirect tcp [bakre94]
– fh - bs connection : standard tcp.
– bs - mh connection : standard tcp.
cmpe 257 winter 11
103split connection: advantages
• bs-mh connection can be optimized
independent of fh-bs connection.
– different congestion/error control.
• local recovery of errors.
– faster recovery due to relatively shorter rtt on
wireless link.
• good performance achievable using
appropriate bs-mh protocol.
– standard tcp on bs-mh performs poorly when
multiple packet losses per window.
– selective acks improve performance.
cmpe 257 winter 11
104split connection:
disadvantages
• end-to-end semantics violated.
– ack may be delivered to sender before
data delivered to receiver.
39
40
38
fh
37
bs
mh
36
40
cmpe 257 winter 11
105split connection:
disadvantages
• bs retains hard state.
– bs failure can result in loss of data.
• if bs fails, packets 39 and 40 will be lost.
• both ack’d to sender sender does not buffer.
39
40
38
fh
37
bs
40
cmpe 257 winter 11
mh
36
106split connection:
disadvantages
• bs retains hard state.
hand-off latency increases due to state
transfer
– data that has been ack’d to sender must
be moved to new base station.
cmpe 257 winter 11
107handoff
39
40
bs
fh
38
37
36
40
mh
39
40
mh
hand-off
new base station
cmpe 257 winter 11
108split connection:
disadvantages
• buffer space needed at bs for each tcp connection.
– bs buffers tend to get full, when wireless link slower (one
window worth of data on wired connection could be stored at
the base station for each split connection).
• extra copying of data at bs
– copying from fh-bs socket buffer to bs-mh socket buffer.
– increases end-to-end latency.
cmpe 257 winter 11
109split connection:
disadvantages
• may not be useful if data and acks
traverse different paths.
– example: data on a satellite wireless hop,
acks on a dial-up channel.
bs
data
fh
mh
ack
cmpe 257 winter 11
110e2e approaches
• strict e2e versus e2e with intermediate
node involvement.
• e2e with intermediate node
involvement:
– explicit notifications.
cmpe 257 winter 11
111explicit notification schemes
general philosophy
• approximate ideal tcp behavior.
– ideally, tcp sender should simply retransmit a
packet lost due to transmission errors without
taking any congestion control actions.
• a node determines whether packets are lost
due to errors and informs sender using an
“explicit notification”.
• sender, on receiving the notification, does not
reduce congestion window, but retransmits
lost packet.
cmpe 257 winter 11
112explicit notification schemes
• motivated by explicit congestion notification
(ecn) proposals [floyd94].
variations proposed in literature differ in:
• who sends explicit notification.
• how they decide to send explicit notification.
• what sender does on receiving notification.
cmpe 257 winter 11
113explicit loss notification
[balakrishnan98]
• mh is the tcp sender.
• wireless link first on path from sender to
receiver.
• base station keeps track of holes in packet
sequence.
• when a dupack is received from the receiver,
bs compares the dupack sequence number
with recorded holes.
– if there is a match, an eln bit is set in dupack.
cmpe 257 winter 11
dupack with eln set
114eln
• when sender receives dupack with eln
set, it retransmits packet, but does not
reduce congestion window.
mh
4
3
wireless
2
1
1
1
record
hole at 2
bs
cmpe 257 winter 11
4
3
1
fh
1 1
115explicit loss notification
[biaz99thesis]
• adapts eln proposed in [balakrishnan98] for
the case when mh is receiver.
• caches tcp sequence numbers at base
station, similar to snoop. but does not cache
data packets, unlike snoop.
• duplicate acks are tagged with eln bit before
being forwarded to sender if sequence
number for the lost packet is cached at bs.
• sender takes appropriate action on receiving
eln.
cmpe 257 winter 11
116eln [biaz99thesis]
sequence numbers
cached at base station
39
38
37
39
36
37
38
37
37
dupack with eln
cmpe 257 winter 11
117explicit bad state notification
[bakshi97]
• mh is tcp receiver.
• bs attempts to deliver packets to mh using link layer
retransmission scheme.
• if packet cannot be delivered using small number of
retransmissions, bs sends a explicit bad state
notification (ebsn) message to tcp sender.
• when tcp sender receives ebsn, it resets rto.
– timeout delayed when wireless channel in bad state.
cmpe 257 winter 11
118partial ack protocols
[cobb95][biaz97]
• send two types of acknowledgements.
• partial ack informs sender that a
packet was received by an intermediate
host (typically, base station).
• normal tcp cumulative ack needed by
sender for reliability purposes.
cmpe 257 winter 11
119partial ack protocols
• when packet for which partial ack is
received detected to be lost, sender
does not reduce its congestion window
– loss assumed to be due to wireless errors.
37
37
partial ack
cmpe 257 winter 11
36
cumulative ack
120variations
• base station may or may not locally
buffer and retransmit lost packets.
cmpe 257 winter 11
121strict e2e schemes
cmpe 257 winter 11
122receiver-based scheme
[biaz98asset]
• mh is tcp receiver.
• receiver uses heuristics to guess cause of
packet loss.
• when receiver believes that packet loss is
due to errors, it sends notification to sender.
• tcp sender, on receiving notification,
retransmits lost packet, without reducing
congestion window.
cmpe 257 winter 11
123heuristics
• receiver uses inter-arrival time between
consecutively received packets to guess
cause of packet loss.
• on determining a packet loss as being due to
errors, the receiver may:
– tag corresponding dupacks with an eln bit, or
– send an explicit notification to sender.
cmpe 257 winter 11
124receiver-based scheme
• packet loss due to congestion
12
fh
11
10
bs
mh
t
fh
bs
12
11
congestion loss
cmpe 257 winter 11
10
mh
125receiver-based scheme
• packet loss due to transmission error
12
fh
11
10
bs
mh
2 t
12
fh
bs
11
error loss
cmpe 257 winter 11
10
mh
126sender-based discrimination
scheme
cmpe 257 winter 11
127sender-based discrimination
[biaz98ic3n,biaz99techrep]
• sender can attempt to determine cause of a packet
loss
• if packet loss determined to be due to errors, do not
reduce congestion window
• sender can only use statistics based on round-trip
times, window sizes, and loss pattern.
– unless network provides more information (example: explicit
loss notification)
cmpe 257 winter 11
128heuristics for congestion
avoidance
• define condition c as a function of
congestion window size and observed
rtts.
• condition c evaluated for new rtt.
• if (c == true) reduce congestion
window.
cmpe 257 winter 11
129heuristics for congestion
avoidance: some proposals
• tcp vegas [brakmo94]
expected throughput et = w(i) / rttmin
actual throughput
at = w(i) / rtt(i)
condition c = ( et-at > beta)
cmpe 257 winter 11
130sender-based heuristics
• record latest value evaluated for condition c
• when a packet loss is detected:
– if last evaluation of c is true, assume packet
loss due to congestion.
– else assume packet loss due to transmission
errors.
• if packet loss determined to be due to errors,
do not reduce congestion window
cmpe 257 winter 11
131sender-based heuristics:
disadvantage
• does not work quite well enough!!
reason
• not much correlation between observed
short-term statistics, and onset of
congestion.
cmpe 257 winter 11
132sender-based heuristics:
advantages
• only sender needs to be modified
needs further investigation to develop
better heuristics
– investigate longer-term heuristics.
cmpe 257 winter 11
133reliable point2point transport
layer: outline
? tcp/ip basics.
? impact of transmission errors on tcp
performance.
? approaches to improve tcp performance on
wireless networks.
? classification.
? tcp on cellular.
? tcp on manets.
cmpe 257 winter 11
134