TCP Congestion Control Basics

undefined
 
TCP
Congestion Control
 
14-740: Fundamentals of Computer Networks
Credit: Bill Nace, 14-740, Fall 2017
 
Last Lecture
 
Reliable Data Transfer Tools
Checksum
Receiver Feedback
Retransmission Timer
Sequence Number
Window / Pipelining
 
2
 
traceroute
 
Connection-oriented Transport: TCP
Segment Structure
Connection Management
Reliable Data Transfer
 
3
 
TCP Overview
 
Point-to-point
One sender, one receiver
Reliable
Segments delivered in-order without loss
In-order byte stream
No message / record boundaries
Pipelined
Sliding-window type control algorithm
 
4
 
TCP Overview
 
Full duplex data
bi-directional data flow in the same
connection
Connection-oriented
handshaking (exchange of control
messages) initializes sender & receiver
state before data exchange
 
5
undefined
 
Both sides have buffers
Lots of “Producer-Consumer”
coordination problems to overcome
 
Transmission Control
 
Flow Control
Sender will not overwhelm receiver
Congestion Control
Various algorithms employed to limit
sending of segments
Don’t want to overwhelm the network
 
7
 
traceroute
 
Connection-oriented Transport: TCP
Segment Structure
Connection Management
Reliable Data Transfer
 
8
 
Format
 
Port numbers
like UDP
16-bit, some are
"well-known"
not same as UDP
 
9
 
Format
 
Seq# and Ack#
counted by bytes of
data, not segments
Seq: number of the first
byte in this segment
Ack: number of the
NEXT expected byte
Acks are cumulative
 
10
Flag Field
Header Length (4
bits)
# words (32-bit)
Usually 5 (20 bytes)
Can be longer
with options
11
 
Flag Field
 
12
 
ACK: Segment acknowledges receipt of
another segment (i.e. ack seq# is good)
Setup and teardown signals
SYN: Synchronize seq#
FIN: No more data from sender
RST: Reset connection
Rarely used
PSH: Push the data to app-layer immediately
URG: Urgent data, indicated by Urgent Data Pointer
 
Format
 
Receive window
#bytes receiver is
willing to accept
For flow-control
 
13
 
Format
 
Checksum
Same as UDP
Urgent data pointer
Offset in data field
Options
Time stamps
Window scaling factors
Negotiating MSS
 
14
 
Format
 
Application Data
Size limited by MSS
MSS=Maximum Segment Size
Despite name, MSS is most
app data that can be carried
MTU (Max Trans Unit) of lower
level generally drives MSS
App data + TCP header + IP
overhead must fit in MTU
MSS is often 1460, 536 or
512 bytes
 
15
undefined
Question
 
Huge file of L bytes, MSS of 1200 bytes,
TCP sequence number field of 4 bytes
What is the maximum value of L such that
TCP sequence numbers are not reused?
16
undefined
Question
 
Huge file of L bytes, MSS of 1200 bytes,
TCP sequence number field of 4 bytes
What is the maximum value of L such that
TCP sequence numbers are not reused?
Kind of a trick question…
TCP sequence number is based on number
of bytes, not segments 
 MSS is irrelevant
Sequence number field is 32-bits, but all
sequence number arithmetic is modulo 2
32
so a theoretical file of L = ∞ bytes is possible
17
 
traceroute
 
Connection-oriented Transport: TCP
Segment Structure
Connection Management
Reliable Data Transfer
 
18
 
TCP Connection Management
 
Why connection establishment?
TCP sender, receiver setup state before
exchanging data segments
Initialize TCP variables:
seq#s
buffers, flow control info (
RcvWindow
)
Why connection teardown?
Free up state
 
19
undefined
 
Three-way Handshake
 
Step 1: client sends TCP SYN
segment to server
specifies initial seq#
holds no data
Step 2: server responds with
SYNACK segment
server allocates buffers
specifies initial seq#
Step 3: Client replies with ACK
may contain data
undefined
Question
 
TCP specification requires each side of a
connection to select an initial starting
sequence number at random
1
. Why?
21
1
Not exactly, but it's complicated.  Let's pretend it is random.
undefined
Question
 
TCP specification requires each side of a
connection to select an initial starting
sequence number at random
1
. Why?
Let’s say TCP does not exchange initial
sequence numbers, and just use 0 as the
starting point. What can happen?
An earlier incarnation of the same
connection can interfere with a later one
22
1
Not exactly, but it's complicated.  Let's pretend it is random.
 
Go Away, Dude
 
If a host receives a TCP SYN segment to
a closed port, it responds with a RST
segment
UDP sends a special ICMP packet in this
situation
 
23
undefined
 
Closing a Connection
 
Step 1: Client sends TCP FIN
segment to server
Step 2: Server receives FIN,
responds with ACK
Closes connection
Sends FIN
Recall: Connection is bi-
directional, needs to be shut
down from each side
undefined
 
Closing a Connection
 
Step 3: client receives FIN,
replies with ACK
Client enters “timed wait”
Will respond to FIN with ACK
240 seconds
(2x max time a segment
can exist in internet)
Step 4: server receives ACK,
closes connection
undefined
 
Question
 
Why does client enter “timed
wait” state before “closed,”
even after receiving FIN from
server?
undefined
 
Answer
 
What happens if ACK from the
client is lost, and the client
does not wait?
Client may open the same
connection again (same pair of
port #s)
Receives FIN from earlier
incarnation of connection
Immediately initiate closing of
the later incarnation
 
traceroute
 
Connection-oriented Transport: TCP
Segment Structure
Connection Management
Reliable Data Transfer
 
28
undefined
 
TCP RDT
 
TCP creates RDT
service on top of IP’s
unreliable service
Pipelined segments
Cumulative acks
Retransmission timer
Retransmissions are
triggered by:
timeout events
duplicate acks
Initially, we consider
simplified TCP sender:
ignore duplicate acks
ignore flow control,
congestion control
assume RTT is
estimated somehow
undefined
 
TCP Seq# and ACKs
 
Sequence numbers:
byte stream “number” of first
byte in segment’s data
ACKs:
seq # of next byte expected
from other side
cumulative ACK
acknowledges bytes up to the
first missing byte in the
stream
piggybacked
with data, if possible
undefined
 
TCP Sender Events
 
Data received from app:
Create segment
seq# is byte-stream number
of first data byte in segment
Send, if allowed by
congestion & flow-control
start timer if not already
running (think of timer as for
oldest unacked segment)
expiration interval:
TimeOutInterval
Timeout:
retransmit segment that
caused timeout
restart timer
 ACK received:
If acknowledges previously
unACKed segments
update what is known to
be ACKed
start timer if there are
outstanding segments
undefined
 
What does server do when it
gets the retransmitted
segment?
Retransmission Scenarios
Lost ACK
undefined
 
What does server do when it
gets the retransmitted
segment?
Discard it!  Expected seq# is
100.  Since 92 < 100 it knows
this is duplicate data
Retransmission Scenarios
Lost ACK
undefined
 
Will client retransmit 2nd
segment (Seq=100)?
Retransmission Scenarios
Premature Timeout
undefined
 
Will client retransmit 2nd
segment (Seq=100)?
No!  ACK=120 arrives before
the timeout
Retransmission Scenarios
Premature Timeout
undefined
Retransmission Scenarios
Cumulative ACK
 
Host hasn’t received ACK for
first segment, so why doesn’t it
retransmit?
undefined
 
Host hasn’t received ACK for
first segment, so why doesn’t it
retransmit?
ACK=120 is cumulative, which
means everything up to byte
120 has been received
(including 92)
Retransmission Scenarios
Lost ACK
 
ACK Generation
 
38
undefined
 
Fast Retransmit
 
Time-out period often
relatively long:
Long delay before
resending lost segment
Detect lost segments via
duplicate ACKs
Sender often sends
many segments back-
to-back
If segment is lost, there
will likely be many
duplicate ACKs
If sender receives 3
duplicate ACKs, it
supposes that segment
after ACKed data was
lost:
Fast retransmit: 
resend
segment before timer
expires
undefined
 
Scenario
 
Sender doesn’t have to wait for
a timeout to notice probable
loss of seq=100 segment
Sort of a NACK
 
Fast Retransmission
undefined
 
Why 3?
 
Why 3 duplicate ACKs? Why
not do fast retransmit after the
first duplicate ACK for a
segment is received?
If n+1 and n+2 (or n+3) are just
reordered, then waiting for 2
duplicate ACKs will not
retrigger retransmission
Voodoo constant
undefined
 
Lesson Objectives
 
Now, you should be able to:
describe the requirements and features
of TCP
describe the segment format of TCP
calculate MSS from the relationship of
MTU, Network and Transport header
sizes
 
42
undefined
 
You should be able to:
describe the operations behind establishing
and tearing-down a TCP connection
describe the operation of sender and
receiver in reliably transferring data across
the TCP connection. This description should
include events occurring at the sender
(including fast retransmission optimizations)
and receiver, as well as scenarios whereby
error conditions are overcome
undefined
 
14-740: Fundamentals of Computer Networks
 
Flow and Congestion
Control (Hosts)
 
traceroute
 
Flow Control
Principles of Congestion Control
TCP Congestion Control
 
45
 
Flow Control
 
In RDT lecture, we discovered windows for
managing pipelined transfer
But, didn't discuss windows (much) in
TCP lecture
TCP has 2 windows
Flow Control Window
Congestion Control Window
Sender limited by smallest window
 
46
Flow Control !
Flow Control !
=
=
 Congestion Control
 Congestion Control
undefined
 
Both sides have buffers
Lots of “Producer-Consumer”
coordination problems to overcome
 
Flow Control
 
Receive side of TCP connection has a
receive buffer of size 
RcvBuffer
Application process may be slow at
reading from the buffer
 
48
 
Flow Control (2)
 
Flow Control: Sender won’t overflow the
receiver’s buffer by transmitting too much,
too fast
Speed-matching service: matching the
send rate to the receiving app’s drain rate
 
49
 
Mechanism
 
Spare room in buffer
= RcvWindow
= RcvBuffer - [LastByteRcvd - LastByteRead]
 
50
Yes, this assumes receiver
Yes, this assumes receiver
discards out-of-order
discards out-of-order
segments.  Easy enough to
segments.  Easy enough to
program around
program around
simplification
simplification
 
Mechanism (2)
 
51
 
Receiver advertises spare room by including
value of 
RcvWindow
 in ACK segment
Gives sender permission to send this much
Sender limits unACKed data to 
RcvWindow
bytes
 
traceroute
 
Flow Control
Principles of Congestion Control
TCP Congestion Control
 
52
 
Router View
 
Router buffer absorbs temporary bursts
when input rate > output rate
When buffer is full, router cannot accept
more packets and must drop them
 
53
 
Costs of Congestion
 
 
54
 
Costs of Congestion
 
Packets can experience large queuing delays
Even if not dropped (adv topic: Bufferbloat)
Packets can be dropped due to buffer overflow
Sender must perform retransmission of lost
segments
Retransmission might not be necessary but was
triggered by premature timeout
Wasted network resources
 
55
 
Congestion
 
Too many sources sending too much data too
fast for 
network
 to handle
Different than flow control!
As network load increases, some router has
many packets queued in its buffer, resulting in:
Long delays – as packets wait for processing
Lost packets – as buffer space overflows,
cannot handle any more incoming packets!
 
56
 
Congestion Collapse
 
Commonly happened in late 1980s!
End-hosts would send their packets into the Internet
as fast as the receiver advertised window would
allow
Congestion would happen at some router, causing
packets to be dropped
End-hosts would retransmit their packets
Network would become more and more congested
Vicious cycle: retransmission of old packets, not
new ones!
 
57
 
Congestion Control
 
Goal: large throughput and small delay
To increase throughput, send more
packets
More packets increases queue length at
routers -- delay increases
Large throughput != small delay
 
58
undefined
 
Congestion Control (2)
 
Apply some control theory
Region 1: Low throughput
Region 2: High delay
Throughput increases slowly
Delay increases quickly
Region 3: Collapse
Throughput 
 0, Delay 
At what load would we like to
operate?
 
59
undefined
Congestion Control (2)
Apply some control theory
Region 1: Low throughput
Region 2: High delay
Throughput increases slowly
Delay increases quickly
Region 3: Collapse
Throughput 
 0, Delay 
At what load would we like to
operate?
60
 
How do we control?
 
Need feedback mechanism!
Detect when network approaches knee
point, so countermeasures can be taken
Slow down sending rate
“Conservation of Packets” Law
When network running in steady state at
peak efficiency, don’t put a packet into
the network until one leaves
 
61
undefined
 
Feedback Approaches
 
Network-assisted
congestion control
(detection):
routers provide
feedback to sender, or
Set single bit in header
as it goes by, or ...
TCP/IP ECN, ATM,
SNA, DECnet
tell explicit send rate
End-end control:
no explicit feedback
from network
congestion inferred from
end-system observed
loss, delay
approach taken by TCP
 
Feedback Mechanism
 
Network Assisted: Signals from routers
End-to-end: Messages from receiver
 
63
 
traceroute
 
Principles of Congestion Control
TCP Congestion Control
 
64
 
TCP CC: Overview
 
End-to-End CC: sender limits transmission
based on perceived congestion
Uses 
CongWin
 variable -- how much data
allowed in-flight at any time
LastByteSent-LastByteAcked ≤ CongWin
Roughly, rate = 
CongWin
 / RTT
 
65
 
Congestion Detection
 
How does sender perceive congestion?
timeout
3 duplicate ACKs
TCP sender reduces rate (
CongWin
)
after loss event
 
66
 
TCP CC: Components
 
Slow start
 – Getting to equilibrium
Additive-increase, multiplicative-decrease
(AIMD)
 – Adapting to path (avoiding
congestion)
RTT estimation – Conservation at
equilibrium
Reaction to timeout events
 
67
 
TCP CC (2)
 
TCP is 
self-clocking
Uses ACK to trigger (or clock) its
increase in congestion window size
A number of algorithmic varieties:
TCP Tahoe
TCP Reno (most widely used)
TCP Vegas, TCP SACK, etc
 
68
 
Getting Started
 
Uncontrolled rush to send segments is UGLY
 
69
 
Some segments
got sent 5 times!
“Nothing in this
trace resembles
desirable
behavior”
 
Slow Start
 
Getting to Equilibrium
When connection begins, 
CongWin
 = 1 MSS
Available bandwidth may be >> MSS/RTT
desire a quick ramp-up to respectable rate
Therefore, at start, increase rate exponentially
fast ...
until first loss event ...
or 
CongWin
 > 
ssthresh
 (a pre-set threshold)
 
70
undefined
 
Slow Start
 
When connection begins,
increase rate exponentially:
double 
CongWin
 every RTT
done by increasing 
CongWin
by 1MSS for every ACK
received
Summary: initial rate is slow
but ramps up exponentially fast
 
Behavior of Slow Start
 
With Slow Start, no bandwidth wasted on
retransmission
 
72
 
Control at Equilibrium
 
Slow start’s exponential increase will eventually
saturate the network
What happens to keep it in control?
Additive Increase, Multiplicative Decrease
(AIMD) algorithm
Backoff quickly when loss occurs
Continue probing for usable bandwidth
This phase is also called 
congestion avoidance
 
73
 
Additive Increase:
 Increase 
CongWin
 by
1 MSS every RTT until loss is detected
Multiplicative Decrease:
 cut 
CongWin
 in
half after a loss event
 
AIMD Mechanics
 
74
 
Sawtooth
behavior: Probing
for bandwidth
undefined
 
Refinements
 
Under TCP Tahoe, 
CongWin
 set to 1 after
a loss, then slow start to 
ssthresh
, which
is set to half of 
CongWin
’s value at loss
Under TCP Reno, 
CongWin
 is set to
ssthresh
 and then linear increase
Fast Recovery
TCP Tahoe
After both loss events
CongWin set to 1 MSS
Enters Slow Start
TCP Reno
After 3 dup ACKs:
Cancel Slow Start
CongWin is cut in half
window grows linearly
But after timeout event:
CongWin set to 1 MSS
window grows exponentially
to a threshold, then grows linearly
undefined
 
CongWin size plot
 
77
undefined
CongWin size plot
78
undefined
 
CongWin size plot
undefined
CongWin size plot
undefined
 
CongWin size plot
undefined
CongWin size plot
undefined
 
CongWin size plot
undefined
CongWin size plot
undefined
 
CongWin size plot
undefined
CongWin size plot
 
RTT and Timeout
 
How should the timeout value be set?
Must be longer than RTT (which varies)
Too short: premature timeout
unnecessary retransmissions
Too long: slow reaction to segment loss
Strategy: Measure actual RTTs for
baseline
 
87
 
Estimating RTT
 
Grab some samples: 
SampleRTT
Measured time from segment
transmission to ACK receipt
ignore retransmissions
Sampled values vary, so “smooth”
average several recent measurements
 
88
undefined
 
Why ignore retransmissions?
 
TCP does not measure
SampleRTT for retransmitted
segments.  Why not?
undefined
Why ignore retransmissions?
TCP does not measure
SampleRTT for retransmitted
segments.  Why not?
 
Smoothing the Samples
 
To smooth samples, use exponential
weighted moving average (EWMA)
EstimatedRTT <= (1-α)*EstimatedRTT + α*SampleRTT
Influence of past samples decreases
exponentially fast
Typical value for 
α
 is 0.125
 
91
 
Setting the Timeout
 
Timeout should be EstimatedRTT + “safety margin”
Large variation in EstimatedRTT 
 larger margin
Use EWMA of deviation in SampleRTT from
EstimatedRTT
DevRTT <= (1-β)*DevRTT + β*| SampleRTT-EstimatedRTT |
β
 typically set to 0.25
Then set timeout interval
TimeoutInterval = EstimatedRTT + 4 * DevRTT
 
92
 
Why worry about Variance?
 
Why not just estimate RTT (use EWMA), then multiply by
a constant “safety margin?”
Older version of TCP did just that:
TimeoutInterval = EstimatedRTT*2
Not adaptive enough -- Need a larger safety margin
when network load is higher, smaller for lower loads
Otherwise, timeout interval is too short – what happens?
Retransmit segments that are not lost
Adds more segments to an already congested network!
 
93
 
TCP CC Summary
 
When 
CongWin
 is below 
Threshold
, window
grows exponentially (
slow-start
 phase)
When 
CongWin
 is above 
Threshold
, window
grows linearly (
congestion-avoidance
 phase)
When a 
triple duplicate ACK
 occurs, 
Threshold
set to 
CongWin/2
 and 
CongWin
 set to
Threshold
.  Window grows linearly
When 
timeout
 occurs, 
Threshold
 set to
CongWin/2
 and 
CongWin
 is set to 1 MSS. Enters
slow-start phase
 
94
 
Lesson Objectives
 
Now, you should be able to:
describe the mission, operation and
mechanisms for flow control in TCP
list causes, costs and consequences of
network congestion
describe the operations of, as well as
advantages and disadvantages of,
different feedback mechanisms
 
95
undefined
 
You should be able to:
describe the overall congestion control
mechanisms used in TCP, including
the congwin variable, self-clocking
nature, and interaction of various
phases
describe the slow start component of
TCP congestion control; including
starting conditions, reactions to ACKs
and ending conditions
undefined
 
You should also be able to:
describe the congestion avoidance
component of TCP congestion control;
including starting conditions, ending
conditions, reactions to loss, reactions
to ACKs and differences between
Reno and Tahoe versions
describe how TCP sets timeout values
calculate EstimatedRTT, DevRTT and
TimeoutInterval
Slide Note
Embed
Share

This content covers the basics of congestion control in TCP, including aspects such as reliable data transfer tools, checksum usage, and receiver feedback. It's based on material from the book "Computer Networking: A Top Down Approach, 6th edition" by J.F. Kurose and K.W. Ross, and a lecture by Bill Nace in the course 14-740: Fundamentals of Computer Networks. Understanding these concepts is crucial for optimizing network performance and ensuring efficient data transmission.


Uploaded on Sep 12, 2024 | 2 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. TCP Congestion Control 14-740: Fundamentals of Computer Networks Credit: Bill Nace, 14-740, Fall 2017 Material from Computer Networking: A Top Down Approach, 6thedition. J.F. Kurose and K.W. Ross

  2. Last Lecture Reliable Data Transfer Tools Checksum Receiver Feedback Retransmission Timer Sequence Number Window / Pipelining 14-740: Fall 2017 2

  3. traceroute Connection-oriented Transport: TCP Segment Structure Connection Management Reliable Data Transfer 14-740: Fall 2017 3

  4. TCP Overview Point-to-point One sender, one receiver Reliable Segments delivered in-order without loss In-order byte stream No message / record boundaries Pipelined Sliding-window type control algorithm 14-740: Fall 2017 4

  5. TCP Overview Full duplex data bi-directional data flow in the same connection Connection-oriented handshaking (exchange of control messages) initializes sender & receiver state before data exchange 14-740: Fall 2017 5

  6. Both sides have buffers Lots of Producer-Consumer coordination problems to overcome

  7. Transmission Control Flow Control Sender will not overwhelm receiver Congestion Control Various algorithms employed to limit sending of segments Don t want to overwhelm the network 14-740: Fall 2017 7

  8. traceroute Connection-oriented Transport: TCP Segment Structure Connection Management Reliable Data Transfer 14-740: Fall 2017 8

  9. Format Port numbers like UDP 16-bit, some are "well-known" not same as UDP 14-740: Fall 2017 9

  10. Format Seq# and Ack# counted by bytes of data, not segments Seq: number of the first byte in this segment Ack: number of the NEXT expected byte Acks are cumulative 14-740: Fall 2017 10

  11. Flag Field Header Length (4 bits) # words (32-bit) Usually 5 (20 bytes) Can be longer with options 14-740: Fall 2017 11

  12. Flag Field ACK: Segment acknowledges receipt of another segment (i.e. ack seq# is good) Setup and teardown signals SYN: Synchronize seq# FIN: No more data from sender RST: Reset connection Rarely used PSH: Push the data to app-layer immediately URG: Urgent data, indicated by Urgent Data Pointer 14-740: Fall 2017 12

  13. Format Receive window #bytes receiver is willing to accept For flow-control 14-740: Fall 2017 13

  14. Format Checksum Same as UDP Urgent data pointer Offset in data field Options Time stamps Window scaling factors Negotiating MSS 14-740: Fall 2017 14

  15. Format Application Data Size limited by MSS MSS=Maximum Segment Size Despite name, MSS is most app data that can be carried MTU (Max Trans Unit) of lower level generally drives MSS App data + TCP header + IP overhead must fit in MTU MSS is often 1460, 536 or 512 bytes 14-740: Fall 2017 15

  16. Question Huge file of L bytes, MSS of 1200 bytes, TCP sequence number field of 4 bytes What is the maximum value of L such that TCP sequence numbers are not reused? Kind of a trick question TCP sequence number is based on number of bytes, not segments MSS is irrelevant Sequence number field is 32-bits, but all sequence number arithmetic is modulo 232 so a theoretical file of L = bytes is possible 14-740: Fall 2017 17

  17. traceroute Connection-oriented Transport: TCP Segment Structure Connection Management Reliable Data Transfer 14-740: Fall 2017 18

  18. TCP Connection Management Why connection establishment? TCP sender, receiver setup state before exchanging data segments Initialize TCP variables: seq#s buffers, flow control info (RcvWindow) Why connection teardown? Free up state 14-740: Fall 2017 19

  19. Three-way Handshake Step 1: client sends TCP SYN segment to server specifies initial seq# holds no data Step 2: server responds with SYNACK segment server allocates buffers specifies initial seq# Step 3: Client replies with ACK may contain data

  20. Question TCP specification requires each side of a connection to select an initial starting sequence number at random1. Why? Let s say TCP does not exchange initial sequence numbers, and just use 0 as the starting point. What can happen? An earlier incarnation of the same connection can interfere with a later one 1Not exactly, but it's complicated. Let's pretend it is random. 14-740: Fall 2017 22

  21. Go Away, Dude If a host receives a TCP SYN segment to a closed port, it responds with a RST segment UDP sends a special ICMP packet in this situation 14-740: Fall 2017 23

  22. Closing a Connection Step 1: Client sends TCP FIN segment to server Step 2: Server receives FIN, responds with ACK Closes connection Sends FIN Recall: Connection is bi- directional, needs to be shut down from each side

  23. Closing a Connection Step 3: client receives FIN, replies with ACK Client enters timed wait Will respond to FIN with ACK 240 seconds (2x max time a segment can exist in internet) Step 4: server receives ACK, closes connection

  24. Question Why does client enter timed wait state before closed, even after receiving FIN from server?

  25. Answer What happens if ACK from the client is lost, and the client does not wait? Client may open the same connection again (same pair of port #s) Receives FIN from earlier incarnation of connection Immediately initiate closing of the later incarnation

  26. traceroute Connection-oriented Transport: TCP Segment Structure Connection Management Reliable Data Transfer 14-740: Fall 2017 28

  27. TCP RDT TCP creates RDT service on top of IP s unreliable service Pipelined segments Cumulative acks Retransmission timer Retransmissions are triggered by: timeout events duplicate acks Initially, we consider simplified TCP sender: ignore duplicate acks ignore flow control, congestion control assume RTT is estimated somehow

  28. TCP Seq# and ACKs Sequence numbers: byte stream number of first byte in segment s data ACKs: seq # of next byte expected from other side cumulative ACK acknowledges bytes up to the first missing byte in the stream piggybacked with data, if possible

  29. TCP Sender Events Data received from app: Create segment seq# is byte-stream number of first data byte in segment Send, if allowed by congestion & flow-control start timer if not already running (think of timer as for oldest unacked segment) expiration interval: TimeOutInterval Timeout: retransmit segment that caused timeout restart timer ACK received: If acknowledges previously unACKed segments update what is known to be ACKed start timer if there are outstanding segments

  30. ACK Generation Event at receiver Receiver Action Arrival of in-order segment with expected seq#. All data up to seq# already ACKed Delayed ACK. Wait up to 500ms for next segment. If no next segment, send ACK Arrival of in-order segment with expected seq#. One other segment has ACK pending Immediately send single cumulative ACK for both in- order segments Arrival of out-of-order segment higher than expected seq#. Gap detected Immediately send duplicate ACK, indicating seq# of next expected byte Immediately send ACK, provided that segment starts at lower end of gap Arrival of segment that partially or completely fills gap 14-740: Fall 2017 38

  31. Fast Retransmit Time-out period often relatively long: Long delay before resending lost segment Detect lost segments via duplicate ACKs Sender often sends many segments back- to-back If segment is lost, there will likely be many duplicate ACKs If sender receives 3 duplicate ACKs, it supposes that segment after ACKed data was lost: Fast retransmit: resend segment before timer expires

  32. Scenario Fast Retransmission Sender doesn t have to wait for a timeout to notice probable loss of seq=100 segment Sort of a NACK

  33. Why 3? Why 3 duplicate ACKs? Why not do fast retransmit after the first duplicate ACK for a segment is received? If n+1 and n+2 (or n+3) are just reordered, then waiting for 2 duplicate ACKs will not retrigger retransmission Voodoo constant

  34. Lesson Objectives Now, you should be able to: describe the requirements and features of TCP describe the segment format of TCP calculate MSS from the relationship of MTU, Network and Transport header sizes 14-740: Fall 2017 42

  35. You should be able to: describe the operations behind establishing and tearing-down a TCP connection describe the operation of sender and receiver in reliably transferring data across the TCP connection. This description should include events occurring at the sender (including fast retransmission optimizations) and receiver, as well as scenarios whereby error conditions are overcome

  36. Flow and Congestion Control (Hosts) 14-740: Fundamentals of Computer Networks Material from Computer Networking: A Top Down Approach, 6thedition. J.F. Kurose and K.W. Ross

  37. traceroute Flow Control Principles of Congestion Control TCP Congestion Control 14-740: Fall 2017 45

  38. Flow Control In RDT lecture, we discovered windows for managing pipelined transfer But, didn't discuss windows (much) in TCP lecture TCP has 2 windows Flow Control Window Congestion Control Window Sender limited by smallest window Flow Control != Congestion Control 14-740: Fall 2017 46

  39. Both sides have buffers Lots of Producer-Consumer coordination problems to overcome

  40. Flow Control Receive side of TCP connection has a receive buffer of size RcvBuffer Application process may be slow at reading from the buffer 14-740: Fall 2017 48

  41. Flow Control (2) Flow Control: Sender won t overflow the receiver s buffer by transmitting too much, too fast Speed-matching service: matching the send rate to the receiving app s drain rate 14-740: Fall 2017 49

  42. Mechanism Spare room in buffer = RcvWindow Yes, this assumes receiver discards out-of-order segments. Easy enough to program around simplification = RcvBuffer - [LastByteRcvd - LastByteRead] 14-740: Fall 2017 50

  43. Mechanism (2) Receiver advertises spare room by including value of RcvWindow in ACK segment Gives sender permission to send this much Sender limits unACKed data to RcvWindow bytes 14-740: Fall 2017 51

  44. traceroute Flow Control Principles of Congestion Control TCP Congestion Control 14-740: Fall 2017 52

  45. Router View Router buffer absorbs temporary bursts when input rate > output rate When buffer is full, router cannot accept more packets and must drop them 14-740: Fall 2017 53

  46. Costs of Congestion 14-740: Fall 2017 54

  47. Costs of Congestion Packets can experience large queuing delays Even if not dropped (adv topic: Bufferbloat) Packets can be dropped due to buffer overflow Sender must perform retransmission of lost segments Retransmission might not be necessary but was triggered by premature timeout Wasted network resources 14-740: Fall 2017 55

  48. Congestion Too many sources sending too much data too fast for network to handle Different than flow control! As network load increases, some router has many packets queued in its buffer, resulting in: Long delays as packets wait for processing Lost packets as buffer space overflows, cannot handle any more incoming packets! 14-740: Fall 2017 56

  49. Congestion Control Goal: large throughput and small delay To increase throughput, send more packets More packets increases queue length at routers -- delay increases Large throughput != small delay 14-740: Fall 2017 58

  50. Congestion Control (2) Apply some control theory Region 1: Low throughput Region 2: High delay Throughput increases slowly Delay increases quickly Region 3: Collapse Throughput 0, Delay At what load would we like to operate? 14-740: Fall 2017 60

Related


More Related Content

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