Understanding TCP Reliability and Pipelined Delivery

 
CS 352
Reliability: Pipelined Delivery
 
Lecture 12
Srinivas Narayana
 
1
Quick recap of concepts
Tp layer
 
Error detection
 
UDP
Connectionless
 
TCP
Connection-oriented
 
Sender
 
f(.)
 
Receiver
 
f(.)
 
Checksum
 
Checksum
 
Compare*
 
Detecting errors is insufficient.
Need to correct errors.
 
Also, data may simply be lost.
(checksum is also lost)
 
Need better mechanisms for
reliable data delivery!
 
TCP uses 3 simple ideas
 
Note: actual impl more nuanced
Review:
 
Sender sends a 
single
 packet, then
waits
 for an 
ACK
 to know the packet
was successfully received. Then the
sender transmits the next packet.
 
If ACK is not received until a timeout
(
RTO
), sender 
retransmits
 the packet
 
How to set the RTO?
Bad RTO: retransmit too early or too
late
Sender
Receiver
 
RTT
 
RTO
 
Retransmit
 
ACK delayed
ACK dropped
Pkt dropped
Pkt corrupted
How should the RTO be set?
 
A good RTO must 
predict
 the 
round-trip time
(RTT) between the sender and receiver
RTT: the time to send a single packet and receive
a (corresponding) single ACK at the sender
 
Intuition: If an ACK hasn’t returned, and our
(best estimate of) RTT has elapsed,  the
packet was likely dropped.
 
RTT can be measured directly at the sender.
No receiver or router help needed.
Sender
Receiver
ACK
RTO
Coping with packet 
duplication
Sender
Receiver
ACK
RTO
 
If ACKs delayed beyond the RTO,
sender may retransmit the 
same
 data
Receiver wouldn’t know that it just
received duplicate data from this
retransmitted packet
 
Add some identification to each
packet to help distinguish between
adjacent transmissions
This is known as the 
sequence number
 
Duplicate
packet
received!
(Receiver
doesn’t
know…)
Coping with packet loss: (3) Sequence #s
Sender
Receiver
ACK
RTO
 
A bad scenario: Suppose an ACK was
delayed beyond the RTO; sender
ended up retransmitting the packet.
 
At the receiver: 
sequence number
helps disambiguate a fresh
transmission from a retransmission
Sequence number same as earlier:
retransmission
Fresh sequence number: fresh data
 
0
 
0
Coping with packet loss: (3) Sequence #s
Sender
Receiver
RTO
 
A good scenario: packet successfully
received and ACK returned within
RTO
 
Sequence numbers of successively
transmitted packets are different
 
Receiver
knows
these are
not
duplicate,
because
sequence
numbers
are
different
 
SEQ 0
 
SEQ 1
 
ACK
RTO
Coping with packet loss: (3) Sequence #s
Sender
Receiver
RTO
A good scenario: packet successfully
received and ACK returned within
RTO
Sequence numbers of successively
transmitted packets are different
RTO
Receiver
knows
these are
not
duplicate,
because
sequence
numbers
are
different
ACK
 
ACK
 
ACK
SEQ 0
SEQ 1
Q: What is the seq# of third packet?
Sender
Receiver
ACK
RTO
 
Goal: Avoid ambiguity on which
packet was received/ACK’ed from
both the sender and receiver’s
perspective
One option: increment seq#: 2, 3, …
Alternative: since seq # 0 was
successfully ACK’ed earlier, it is OK to
reuse seq #0 for next transmission.
Seq #s reusable if older packets with
those seq #s known to be delivered
SEQ 0
SEQ 1
ACK
 
???
RTO
 
Stop-and-Wait Reliability
 
Sender sends a single packet, then
waits for an ACK to know the packet
was successfully received. Then the
sender transmits the next packet.
 
If ACK is not received until a timeout
(RTO), sender 
retransmits
 the packet
 
Disambiguate duplicate vs. fresh
packets using sequence numbers
that change on “adjacent” packets
Sender
Receiver
 
RTT
 
RTO
 
SEQ 0
 
ACK
 
SEQ 1
 
Retransmit
 
In principle, these three ideas are sufficient
to implement reliable data delivery!
 
Making reliable data transfer
efficient
 
Efficiency problem
 with stop-and-wait
 
Sender sends 
one packet
, waits for an ACK
(or RTO) before transmitting next one
Unfortunately, too slow 
 
Suppose RTO = RTT = 100 milliseconds
Packet size (bytes in 1 packet) = 12,000 bits
Bandwidth of links from sender to receiver =
12 Mbit/s (1 M = 10
6
)
 
Rate of data transfer = data size / time
Sender
Receiver
RTT
 
120 Kilobit/s == 1% of bw!
RTO
Sending one packet per RTT makes the data
transfer rate limited by the 
time
 between the
endpoints, rather than the 
bandwidth
.
 
Ensure you got the (one)
box safely; make N trips
 
Ensure you get 
N 
boxes
safely; make 
just 1 trip!
 
Keep many packets in flight
Pipelined reliability
 
Data in flight:
 data that has been sent, but sender hasn’t yet
received ACKs from the receiver
Note: can refer to packets in flight or bytes in flight
New packets sent at the same time as older ones still in flight
New packets sent at the same time as ACKs are returning
More data moving in same time!
Improves 
throughput
Rate of data transfer
Pipelined reliability
 
Stop and wait: send 1 packet per RTT
 
Pipelined: send 
N
 packets per RTT
 
If there are N packets in flight, throughput
improves by 
N times 
compared to stop-and-
wait!
Sender
Receiver
RTT
RTO
 
Pipelining makes reliable data transfer efficient.
 
However, pipelining also makes it more complex.
 
Which packets were
successfully delivered?
 
Which packets should
the sender retransmit?
 
Which packets are
currently in flight?
 
Sliding Windows
 
Setup
 
Assume packets are labeled by sequence
numbers
Increasing from 0, …, N-1, then roll back to 0
Assume ACKs indicate the sequence
numbers of data that was received
Note: Didn’t need this for stop-and-wait
Convention: ACK#s carry the 
next
sequence 
number expected
Used in TCP.
Sender
Receiver
 
SEQ 0
 
ACK 1
 
SEQ 1
 
SEQ N-1
 
SEQ 0
 
 
ACK 2
Sliding window (sender side)
 
Window
: Sequence numbers of in-flight data
Window size
: The amount of in-flight data (unACKed)
 
Sender’s
point of
view:
 
Window size 
= 3
 
Last seq # known to
be received (ACK
recv’d at sender)
 
Last sequence
# sent
 
Transmissions later in time
Sliding window (sender side)
 
Suppose sequence number 2 is acknowledged by the receiver
Sender receives the ACK. Sender can transmit sequence # 5
The window “slides” forward
0
1
2
3
4
5
6
7
1
0
 
Window size 
= 3
 
Last seq # known to
be received (ACK
recv’d at sender)
 
Last sequence
# sent
Sender’s
point of
view:
Sliding window (sender side)
Suppose sequence number 2 is acknowledged by the receiver
Sender receives the ACK. Sender can transmit sequence # 5
The window “slides” forward
0
1
2
3
4
5
6
7
1
0
Window size 
= 3
Last seq # known to
be received (ACK
recv’d at sender)
Last sequence
# sent
Sender’s
point of
view:
Sliding window (
receiver side
)
 
Window of in-flight packets can look different between sender
and the receiver
Receiver only accepts sequence #s allowed by the current
receiver window
 
Window size 
= 3
 
Last seq # received
and ACK’ed by
receiver
 
Highest
sequence  #
accepted
 
Receiver’s
point of
view:
 
Receiver will not
accept this seq #.
Packet dropped
Summary of sliding windows
 
Sender and receiver can keep several packets of in-flight data
Book-keep the sequence numbers using the window
 
Windows 
slide forward
 as packets are ACKed (at receiver) and
ACKs are received (at sender)
 
Common case: Improve throughput by sending and ACKing more
packets in the same duration
Pipelining makes reliable data transfer efficient.
However, pipelining also makes it more complex.
Which packets were
successfully delivered?
Which packets should
the sender retransmit?
Which packets are
currently in flight?
 
Which packets to retransmit?
 
Pipelined Reliability
 
If there are N packets in flight, throughput
improves by N times relative to stop-and-wait.
Stop and wait: send 1 packet per RTT
Pipelined: send N packets per RTT
 
Q1: how should sender efficiently identify which
pkts were dropped and (hence) retransmitted?
 
Q2: how much data to keep in flight (i.e., what is
N?) to reduce drops/retransmits?
Sender
Receiver
RTT
RTO
How to identify dropped packets?
 
Suppose 4 packets sent, but 1 dropped. How
does sender know which one(s) dropped?
 
Recall: Receiver writes 
sequence numbers 
on
the ACK indicating successful reception
Key idea: Sender can infer which data was
received successfully using the ACK #s!
Hence, sender can know which data to retransmit
 
Q1: Should receivers ACK subsequent
packets upon detecting data loss?
Q2: If so, what sequence number should
receiver put on the ACK?
Sender
Receiver
RTT
RTO
 
Should this
ACK exist
???
 
ACK ??
Receiver strategies upon packet loss
Sender
Receiver
1
2
3
4
5
ACK pkts after a drop?
 
Go-back-N
 
Selective Repeat
What # on ACK?
 
Last seq# in order
Cumulative ACK
 
Seq# 
ranges
received so far
Selective ACK
 
No
 
Yes
 
TCP’s default
Sliding Window with Go Back N
 
When the receiver notices missing data:
 
It simply 
discards
 all data with greater sequence numbers
i.e.: the receiver will send no further ACKs
 
The sender will eventually time out (RTO) and retransmit all the
data in its sending window
 
Subtle: conceptually, 
separate timer per byte 
to infer RTO
Go back N
 
D
i
s
c
a
r
d
e
d
 
b
y
r
e
c
e
i
v
e
r
D
r
o
p
p
e
d
 
p
a
c
k
e
t
 
(
o
r
)
 
P
a
c
k
e
t
 
w
i
t
h
e
r
r
o
r
 
R
T
O
ACK 1
T
i
m
e
S
e
n
d
e
r
R
e
c
e
i
v
e
r
Maximum
window size = 8
Maximum
window size = 8
0
0
1
1
ACK 2
2
E
3
 
D
4
 
D
2
3
2
 
ACK 3
4
5
6
3
4
5
 
ACK 4
 
ACK 5
 
ACK 6
6
 
ACK 7
 
Go back N
 
Go Back N can recover from erroneous or missing packets.
 
But it is wasteful.
 
If there are errors, the sender will spend time and network
bandwidth retransmitting 
data the receiver has already seen.
 
Selective repeat with cumulative ACK
 
Idea: sender should only retransmit dropped/corrupted data.
The receiver 
stores 
all the correct frames that arrive following
the bad one.  (Note that the receiver requires 
memory to hold
data 
for each sequence number in the receiver window.)
When the receiver notices a skipped sequence number, it keeps
acknowledging the 
first in-order sequence number it wants to
receive. 
This is termed 
cumulative ACK.
When the sender times out waiting for an acknowledgement, it
just retransmits the first unacknowledged data
, not all its
successors.
Recall that RTO applies independently to each sequence #
Selective repeat with cumulative ACK
 
B
u
f
f
e
r
e
d
 
b
y
r
e
c
e
i
v
e
r
 
i
n
i
t
s
 
m
e
m
o
r
y
P
a
c
k
e
t
 
w
i
t
h
e
r
r
o
r
 
(
o
r
)
 
d
r
o
p
p
e
d
 
p
a
c
k
e
t
 
R
T
O
ACK 1
T
i
m
e
S
e
n
d
e
r
R
e
c
e
i
v
e
r
Maximum
window size = 8
Maximum
window size = 8
0
0
1
1
ACK 2
2
E
3
4
2
5
2
 
ACK 5
6
5
 
ACK 6
6
 
ACK 7
3
4
 
ACK 2
 
ACK 2
Selective repeat with 
selective ACK
 
B
u
f
f
e
r
e
d
 
b
y
r
e
c
e
i
v
e
r
 
i
n
i
t
s
 
m
e
m
o
r
y
F
r
a
m
e
 
w
i
t
h
e
r
r
o
r
 
R
T
O
ACK 1
T
i
m
e
S
e
n
d
e
r
R
e
c
e
i
v
e
r
Maximum
window size = 8
Maximum
window size = 8
0
0
1
1
ACK 2
2
E
3
4
2
5
2
 
ACK 5
6
5
 
ACK 6
6
 
ACK 7
3
4
 
ACK 2
SACK 0--1, 3
 
ACK 2
SACK 0,--1, 3--4
TCP: Cumulative & Selective ACKs
 
Sender retransmits the seq #s it thinks aren’t
received successfully yet
Pros & cons: selective vs. cumulative ACKs
Precision of info available to sender
Redundancy of retransmissions
Packet header space
Complexity (and bugs) in transport software
On modern Linux, TCP uses selective ACKs
by default
Sender
Receiver
1
2
3
4
2
3
4
5
5
Slide Note
Embed
Share

This lecture delves into the concepts of TCP reliability and pipelined data delivery, emphasizing the need for mechanisms to ensure data integrity and accuracy. It covers error detection, handling delayed and dropped packets, setting retransmission timeouts (RTO), coping with packet duplication and loss using sequence numbers, and more. The content provides insights on improving the reliability of data transmission over networks.


Uploaded on Jul 29, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. CS 352 Reliability: Pipelined Delivery Lecture 12 http://www.cs.rutgers.edu/~sn624/352-F22 Srinivas Narayana 1

  2. Quick recap of concepts TCP Connection-oriented UDP Connectionless Detecting errors is insufficient. Need to correct errors. Error detection Also, data may simply be lost. (checksum is also lost) Sender Receiver Need better mechanisms for reliable data delivery! f(.) f(.) Checksum Checksum TCP uses 3 simple ideas Compare* Note: actual impl more nuanced

  3. Review: Sender sends a single packet, then waits for an ACK to know the packet was successfully received. Then the sender transmits the next packet. Receiver Sender RTT ACK delayed ACK dropped Pkt dropped Pkt corrupted If ACK is not received until a timeout (RTO), sender retransmits the packet How to set the RTO? Bad RTO: retransmit too early or too late RTO Retransmit

  4. How should the RTO be set? Receiver Sender A good RTO must predict the round-trip time (RTT) between the sender and receiver RTT: the time to send a single packet and receive a (corresponding) single ACK at the sender RTO Intuition: If an ACK hasn t returned, and our (best estimate of) RTT has elapsed, the packet was likely dropped. ACK RTT can be measured directly at the sender. No receiver or router help needed.

  5. Coping with packet duplication Receiver Sender If ACKs delayed beyond the RTO, sender may retransmit the same data Receiver wouldn t know that it just received duplicate data from this retransmitted packet RTO Duplicate packet received! (Receiver doesn t know ) Add some identification to each packet to help distinguish between adjacent transmissions This is known as the sequence number ACK

  6. Coping with packet loss: (3) Sequence #s Receiver Sender A bad scenario: Suppose an ACK was delayed beyond the RTO; sender ended up retransmitting the packet. 0 RTO At the receiver: sequence number helps disambiguate a fresh transmission from a retransmission Sequence number same as earlier: retransmission Fresh sequence number: fresh data 0 ACK

  7. Coping with packet loss: (3) Sequence #s Receiver Sender A good scenario: packet successfully received and ACK returned within RTO SEQ 0 Receiver knows these are not duplicate, because sequence numbers are different RTO ACK Sequence numbers of successively transmitted packets are different SEQ 1 RTO

  8. Coping with packet loss: (3) Sequence #s Receiver Sender A good scenario: packet successfully received and ACK returned within RTO SEQ 0 Receiver knows these are not duplicate, because sequence numbers are different RTO ACK ACK Sequence numbers of successively transmitted packets are different SEQ 1 RTO ACK

  9. Q: What is the seq# of third packet? Receiver Sender Goal: Avoid ambiguity on which packet was received/ACK ed from both the sender and receiver s perspective One option: increment seq#: 2, 3, Alternative: since seq # 0 was successfully ACK ed earlier, it is OK to reuse seq #0 for next transmission. Seq #s reusable if older packets with those seq #s known to be delivered SEQ 0 RTO ACK SEQ 1 RTO ACK ???

  10. Stop-and-Wait Reliability Sender sends a single packet, then waits for an ACK to know the packet was successfully received. Then the sender transmits the next packet. Receiver Sender SEQ 0 RTT ACK If ACK is not received until a timeout (RTO), sender retransmits the packet SEQ 1 Disambiguate duplicate vs. fresh packets using sequence numbers that change on adjacent packets RTO Retransmit

  11. In principle, these three ideas are sufficient to implement reliable data delivery!

  12. Making reliable data transfer efficient

  13. Efficiency problem with stop-and-wait Receiver Sender Sender sends one packet, waits for an ACK (or RTO) before transmitting next one Unfortunately, too slow RTT Suppose RTO = RTT = 100 milliseconds Packet size (bytes in 1 packet) = 12,000 bits Bandwidth of links from sender to receiver = 12 Mbit/s (1 M = 106) RTO Rate of data transfer = data size / time 120 Kilobit/s == 1% of bw!

  14. Sending one packet per RTT makes the data transfer rate limited by the time between the endpoints, rather than the bandwidth. Ensure you got the (one) box safely; make N trips Ensure you get N boxes safely; make just 1 trip! Keep many packets in flight

  15. Pipelined reliability Data in flight: data that has been sent, but sender hasn t yet received ACKs from the receiver Note: can refer to packets in flight or bytes in flight New packets sent at the same time as older ones still in flight New packets sent at the same time as ACKs are returning More data moving in same time! Improves throughput Rate of data transfer

  16. Pipelined reliability Receiver Sender Stop and wait: send 1 packet per RTT Pipelined: send N packets per RTT RTT If there are N packets in flight, throughput improves by N times compared to stop-and- wait! RTO

  17. Pipelining makes reliable data transfer efficient. However, pipelining also makes it more complex. Which packets are currently in flight? Which packets were successfully delivered? Which packets should the sender retransmit?

  18. Sliding Windows

  19. Setup Receiver Sender Assume packets are labeled by sequence numbers Increasing from 0, , N-1, then roll back to 0 Assume ACKs indicate the sequence numbers of data that was received Note: Didn t need this for stop-and-wait Convention: ACK#s carry the next sequence number expected Used in TCP.

  20. Sliding window (sender side) Window: Sequence numbers of in-flight data Window size: The amount of in-flight data (unACKed) Sequence numbers restart from 0 beyond a point (finite space on header) Window size = 3 Sender s point of view: 0 1 0 3 1 4 2 5 7 6 0 7 1 6 2 Last seq # known to be received (ACK recv d at sender) Last sequence # sent 3 5 4 Transmissions later in time

  21. Sliding window (sender side) Suppose sequence number 2 is acknowledged by the receiver Sender receives the ACK. Sender can transmit sequence # 5 The window slides forward Window size = 3 Sender s point of view: 0 1 0 3 1 4 2 5 7 6 0 7 1 6 2 Last seq # known to be received (ACK recv d at sender) Last sequence # sent 3 5 4

  22. Sliding window (sender side) Suppose sequence number 2 is acknowledged by the receiver Sender receives the ACK. Sender can transmit sequence # 5 The window slides forward Window size = 3 Sender s point of view: 0 1 0 3 1 4 2 5 7 6 0 7 1 6 2 Last seq # known to be received (ACK recv d at sender) Last sequence # sent 3 5 4

  23. Sliding window (receiver side) Window of in-flight packets can look different between sender and the receiver Receiver only accepts sequence #s allowed by the current receiver window Window size = 3 Receiver will not accept this seq #. Packet dropped Receiver s point of view: 1 0 3 1 4 2 5 7 6 0 Last seq # received and ACK ed by receiver Highest sequence # accepted

  24. Summary of sliding windows Sender and receiver can keep several packets of in-flight data Book-keep the sequence numbers using the window Windows slide forward as packets are ACKed (at receiver) and ACKs are received (at sender) Common case: Improve throughput by sending and ACKing more packets in the same duration

  25. Pipelining makes reliable data transfer efficient. However, pipelining also makes it more complex. Which packets are currently in flight? Which packets were successfully delivered? Which packets should the sender retransmit?

  26. Which packets to retransmit?

  27. How to identify dropped packets? Suppose 4 packets sent, but 1 dropped. How does sender know which one(s) dropped? Receiver Sender Recall: Receiver writes sequence numbers on the ACK indicating successful reception Key idea: Sender can infer which data was received successfully using the ACK #s! Hence, sender can know which data to retransmit RTT Should this ACK exist ??? Q1: Should receivers ACK subsequent packets upon detecting data loss? Q2: If so, what sequence number should receiver put on the ACK? RTO

  28. Receiver strategies upon packet loss Receiver Sender ACK pkts after a drop? 1 2 No Yes 3 4 Go-back-N Selective Repeat What # on ACK? 5 Seq# ranges received so far Selective ACK TCP s default Last seq# in order Cumulative ACK

  29. Sliding Window with Go Back N When the receiver notices missing data: It simply discards all data with greater sequence numbers i.e.: the receiver will send no further ACKs The sender will eventually time out (RTO) and retransmit all the data in its sending window Subtle: conceptually, separate timer per byte to infer RTO

  30. Go back N RTO Sender Maximum window size = 8 0 1 2 3 4 2 3 4 5 6 Receiver Maximum window size = 8 0 1 2 3 4 5 6 E D D Discarded by receiver Dropped packet (or) Packet with error Time

  31. Go back N Go Back N can recover from erroneous or missing packets. But it is wasteful. If there are errors, the sender will spend time and network bandwidth retransmitting data the receiver has already seen.

  32. Selective repeat with cumulative ACK Idea: sender should only retransmit dropped/corrupted data. The receiver stores all the correct frames that arrive following the bad one. (Note that the receiver requires memory to hold data for each sequence number in the receiver window.) When the receiver notices a skipped sequence number, it keeps acknowledging the first in-order sequence number it wants to receive. This is termed cumulative ACK. When the sender times out waiting for an acknowledgement, it just retransmits the first unacknowledged data, not all its successors. Recall that RTO applies independently to each sequence #

  33. Selective repeat with cumulative ACK RTO Sender Maximum window size = 8 0 1 2 3 4 2 5 6 Receiver Maximum window size = 8 0 1 3 4 2 5 6 E Buffered by receiver in its memory Packet with error (or) dropped packet Time

  34. Selective repeat with selective ACK RTO Sender Maximum window size = 8 0 1 2 3 4 2 5 6 Receiver Maximum window size = 8 0 1 3 4 2 5 6 E Buffered by receiver in its memory Frame with error Time

  35. TCP: Cumulative & Selective ACKs Receiver Sender Sender retransmits the seq #s it thinks aren t received successfully yet Pros & cons: selective vs. cumulative ACKs Precision of info available to sender Redundancy of retransmissions Packet header space Complexity (and bugs) in transport software On modern Linux, TCP uses selective ACKs by default 1 2 3 4 2 3 4 5 5

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#