Transcript TCP flow control and congestion control

CSEE W4140
Networking Laboratory
Lecture 7: TCP flow control and
congestion control
Jong Yul Kim
03.22.2010
Short review of TCP from last time
 Characteristics of the IP network
 Delivers packets from host to host
 May lose packets (discarded by routers)
 Doesn’t care about packet order
 TCP is a




reliable,
in-order,
byte-stream service
(delivers data from application to application)
Short review of TCP from last time
 TCP is a reliable, in-order, byte-stream
service
 The beauty of TCP is that it works without
explicit support from the network
 Each end of the connection cooperate to make
sure packets are delivered reliably and in order
 Techniques used by TCP




Sequence numbers
Acknowledgements (and numbers)
Retransmissions
Timer
Today’s lecture
 TCP Flow Control
 Throttling the rate of sender so that the
receiver’s buffer does not overflow
 TCP Congestion Control
 Throttling the rate of sender in the face
of network congestion
TCP Flow Control (Receive Window)
 When a connection is established, the
receiver allocates a receive buffer.
 Incoming packets are stored in the buffer
so that the application can read data from
the buffer.
TCP Flow Control (Receiver
behavior)
 The receiver lets
the sender know:
IP header TCP header
20 bytes
TCP data
20 bytes
0
15 16
Source Port Number
31
Destination Port Number
Sequence number (32 bits)
Acknowledgement number (32 bits)
header
length
0
Flags
TCP checksum
window size
urgent pointer
Options (if any)
DATA
20 bytes
 how much space is
left in the buffer
= RcvWindow
 by placing that
value in the window
size field
 in every segment
that it sends to the
sender
TCP Flow Control (Sender behavior)
 Sender can fill up the spare room in the
receiver’s buffer by sending more data
 Sender maintains the size of data that has
already been sent but unacknowledged =
bytes_unACKed
 Makes sure that
 bytes_unACKed ≤ RcvWindow
Network Congestion
 Why does congestion occur?
 Too many senders sending at high rate
 Routers dropping packets due to overflowing
buffers
 What are the symptoms?




Packet loss
Packet queuing delay
More retransmission  more packet loss
Link bandwidth wasted on retransmissions
TCP Congestion Control
 Remember: TCP has no support from
the network about congestions
 Need to use end-to-end congestion
control
 TCP relies on perceived network
congestion and throttles the sending
rate accordingly
How does TCP know there is
congestion in the network?
 Answer:
packet loss
 Timeout
 Three duplicate
ACKs shown in
diagram on right
How does TCP limit sending rate?
 Using a variable called congestion
window = CongWin
 Size of unacknowledged data must be
less than CongWin
bytes_unACKed ≤ CongWin
 Sending rate is roughly
CongWin/RTT bytes/sec
We can throttle the sending rate by controlling CongWin
TCP Congestion Control Algorithm
 Is an algorithm that controls CongWin
 Simply stated:
 Packet loss (=congestion)  decrease CongWin
 All is well  increase CongWin
 Three main parts
 Additive-Increase, Multiplicative Decrease
 Slow Start
 Reaction to timeout events
Additive Increase, Multiplicative Decrease
(AIMD)
 Additive Increase
 Increase CongWin by 1 MSS every RTT
while there is no packet loss
 Multiplicative Decrease
 Decrease CongWin by half when packet
is lost
Additive Increase, Multiplicative Decrease
(AIMD)
Congestion Avoidance phase
Slow Start (SS)
 When connection is established
 CongWin is set to 1 MSS
 Increase CongWin by 1 MSS every ACK
 Different from Additive Increase
(+1 MSS every RTT)
 Until a loss occurs
 Result is an exponentially fast growth in
sending rate
Slow Start (SS)
Example of
Slow Start/Congestion Avoidance
cwnd = 1
Assume that
ssthresh = 8
cwnd = 2
cwnd = 4
14
cwnd = 8
10
ssthresh
8
6
4
cwnd = 9
2
6
t=
4
t=
2
t=
0
0
t=
Cwnd (in segments)
12
Roundtrip times
cwnd = 10
Reaction to Timeouts
 We already discussed that TCP perceives
congestion through packet loss
 Packet is considered lost when:
 Timeout occurs
 Three duplicate ACKs are received
 But timeouts and three duplicate ACKs are
different.
 What do they tell about the severity of
congestion?
Reaction to Timeouts
 Let’s do something different for
timeout.
 Reset CongWin to 1 MSS
 Begin again from Slow Start
 Slow start (exponential increase) until
when?
 New variable called Threshold
 Threshold is set to ½ CongWin
 After Threshold, do AIMD instead of SS
Lab 5 part 2 in the lab manual
R2
R1
10.0.3.0/24
PC1
PC2
10.0.2.0/24
10.0.1.0/24
Serial WAN connection
10.0.4.0/24
R3
R4
10.0.5.0/24
Lab 5 part 2 – our version
PC2
PC1
R2
R1
10.0.1.0/24
10.0.3.0/24
10.0.2.0/24
10.0.5.0/24
 Use Table 5.3 and Table 5.4 to configure PC1, PC2,
Router1, and Router2.
 Do parts 5(B), 6(A), 6(C), and 8.
 For part 8, configure PC1 and PC2 so that all packets
travel along PC1 – R1 – R2 – PC2 path.
Main Points of Lab 5 Parts 5~8
 More about TCP
 Interactive applications over TCP
 Data transfer applications over TCP
 Congestion Control
Prelab and lab reports
 Prelab 6 is due this Friday.
 Lab report 5.1 is due this week before
your labs.
 Lab report 5.2 + BGP lab is due next
week before your labs.