PowerPoint Presentation
COMP30023 – Computer Systems
Copyright By PowCoder代写 加微信 powcoder
2022© University of Melbourne
TCP Congestion Control
• Socket Programming
– Socket Interface
– Sockets in C
• TCP flow control
2022© University of Melbourne
TCP Sliding Window – Segment
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
TCP Sliding Window – Segment
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
TCP Sliding Window – Segment
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
ACK:21, Window:50
TCP Sliding Window – Segment
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 31 41
ACK:21, Window:50
TCP Sliding Window – Segment
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 31 41 51
ACK:21, Window:50
ACK + 3 DupACKs = Fast Retransmission
• Flow+loss control had existed on single point-to-point links
for a long time
• TCP originally used the experience from the link layer
• Caused bad design decision.
Original flow + loss control
2022© University of Melbourne
• “Go-back-N” (3.4.3 of Kurose and Ross)
– When a packet is lost, go back to the point where it was
transmitted, and (re)transmit everything from that point onward
– Advantage: Receiver doesn’t need to store/reorder packets
• “Selective Repeat” (3.4.4 of Kurose and Ross)
– Only retransmit the lost packet
– Packets arrive out of order. Receiver must store out-of-order
packets to send them in-order to the application
• Selective repeat: more complex, only helps if loss is
– Link layer fixes errors. Errors will be rare – right?
Two types of flow control
2022© University of Melbourne
• In the late 1980s, the internet had “congestion collapse”
– It took tens of minutes to send a packet to the next building
• diagnosed and solved the problem
• Router buffers were overflowing, causing high loss
• Senders were doing go-back-N, so that every packet loss
caused N more packets to enter the system
• Solution: Selective repeat (“fast retransmit”)
– “Packet conservation” principle
Congestion collapse
2022© University of Melbourne
TCP Sliding Window – Segment
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 31 41 51
ACK:21, Window:50
ACK + 3 DupACKs = Fast Retransmission
TCP Sliding Window – Fast
retransmit
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 31 41 51
TCP Sliding Window – Fast
retransmit
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 31 41 51 61
ACK:21, Window:50
TCP Sliding Window – Fast
retransmit
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
ACK:71, Window:0
TCP Sliding Window
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
Potential for deadlock
• Sender won’t send any more data (window size is 0)
• Receiver won’t receive anything, so won’t send any ACKs to increase window size
TCP Sliding Window – Avoid
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
Data read by application
TCP Sliding Window – Window
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
WIndowUpdate, ACK:71, Window:50
Receiver can initiate an update by sending a WindowUpdate
TCP Sliding Window – Window
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
TCP Sliding Window – Persist
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
ACK:71, Window:0
On receipt of 0 size window, sender:
• Starts Persist Timer
• Persist Timer will periodically send
ZeroWindowProbe segments
Sender can monitor and initiate an update by sending a ZeroWindowProbe
TCP Sliding Window
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
Sender can initiate an update by sending a ZeroWindowProbe
ZeroWindowProbe
TCP Sliding Window
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
ZeroWindowProbeACK, ACK:71, Window:50
TCP Sliding Window
2022© University of Melbourne
1 11 21 31 41 51 61 71 81 91 101 111 121 131 141
1 11 21 31 41 51 61
232022© University of Melbourne
• When networks are overloaded, congestion occurs, potentially
affecting all layers
• Although lower layers (link and network) attempt to ameliorate
congestion, in reality TCP affects congestion most significantly
because TCP offers methods to transparently reduce the data
rate, and hence reduce congestion itself
– Real-time control protocol also helps by changing video compression
• Original TCP (before Jacobson)
– Initially, the receiver chooses a window based on its buffer size
– if the sender is constrained to this size, then congestion problems will
not occur due to buffer overflow at the receiver itself, but may still
occur due to congestion within the network
TCP Congestion Control
2022© University of Melbourne
• Jacobson introduce CWND, the congestion window, in the
same software update that introduce selective repeat.
• Additional window that is dynamically adjusted based on
network performance to aid efficient transfer
• The congestion window size is maintained by the sender,
unlike the sliding window that is controlled by the receiver
– Also only used at the sender.
– No changes to packet formats to send additional field
• Was a big consideration. Now a huge one.
Congestion Control Window
2022© University of Melbourne
• At first, CWND maximum segment size
– Sender transmits 1 segment
• For each segment acknowledged
– CWND += maximum segment size (MSS)
– Sender transmits 2 more segments
• Each full window of acknowledgements doubles the
congestion window – which grows until
– a timeout
– It reaches a threshold, SSthresh
Incremental congestion control
2022© University of Melbourne
Incremental congestion control
2022© University of Melbourne
TN 6th 6-44
• Slow-start algorithm
– Initial rate is slow
– Rate grows exponentially from there
• Eventually too many segments would be placed onto the network
causing congestion and timeouts
• Slow-start maintains a threshold: Slow Start Threshold ssthresh
• Slow start keeps increasing the size of the window until a timeout
occurs or the threshold is reached
• On segment loss: SSthresh CWND/2, start slow start again
• Once the SSthresh is reached, the growth is slowed to linear
– Achieved by CWND += MSS for each complete window of ACKs
– “additive increase”
• Can also react to known lost segments via fast retransmission
• Known as TCP Tahoe (1988) after BSD release name
Incremental congestion control
2022© University of Melbourne
Incremental congestion control –
an example
2022© University of Melbourne
TN 6th 6-46
• Further optimisations were made in TCP Reno (BSD Reno)
• Fast recovery when fast retransmit is triggered
– Starts from new ssthresh instead of original starting value,
effectively avoiding the slow start phase and going straight to
additive increase
Congestion control optimisation
2022© University of Melbourne
TN 6th 6-47
• SACK (Selective Acknowledgements) – provides greater
ability to track segments in-flight, by allowing up to 3 ranges
of bytes received to be specified
Further Optimisation
2022© University of Melbourne
TN 6th 6-48
• These packet-level rules affect many things we care about
– Fairness between flows
– Response to long round-trip times (RTTs)
– Response to random packet loss
• It is useful to have an algebraic expression relating these
quantities
Macroscopic model
2022© University of Melbourne
• W increases once per window
– Approximation: Each packet that arrives increases W by 1/W
• When a loss occurs (with probability p), W is halved
– With probability p, W W/2
• The average increase in window size is
• To be in equilibrium (balance), the average increase must be 0
– 𝑊𝑊 ≈ 2/𝑝𝑝
Window size
2022© University of Melbourne
• The window is sent ≤ once per round trip time (RTT), T
• Rate is 𝑊𝑊
1. For a given packet loss rate, longer RTTs get less rate
– “RTT unfairness”
2. If RTT is small, TCP forces the packet loss rate to be high
• This formula is very approximate
– Window only responds to one packet loss per RTT
– Packet losses are clustered
• However, it gives two important insights
Rate, fairness
2022© University of Melbourne
• For networks with very large windows (high speed, long
distance), TCP Reno needs unrealistically small packet loss, p
– New congestion control algorithms are need for bulk transfers
between data centres on different continents
• Within data centres, needs are different again
• IETF is won’t change, in case things break
• Just as the internet pioneers bypassed the ISO, companies
are implementing their own standards on their own
– DCTCP for data centres, Google’s BBR between data centres.
https://www.theregister.com/2021/10/27/systems_approach_tcp_control
And finally…
2022© University of Melbourne
https://www.theregister.com/2021/10/27/systems_approach_tcp_control
• The slides are based on slide prepared by
based on material developed previously by: ,
, , and .
• Some of the images included in the notes were supplied as
part of the teaching resources accompanying the text books
listed in lecture 1.
– (And also) Computer Networks, 6th Edition, Tanenbaum A., Wetherall. D.
https://ebookcentral.proquest.com/lib/unimelb/detail.action?docID=6481879
• Textbook Reference: 3.6, 3.7
Acknowledgement
2022© University of Melbourne
https://ebookcentral.proquest.com/lib/unimelb/detail.action?docID=6481879
TCP Congestion Control
TCP Sliding Window – Segment Loss
TCP Sliding Window – Segment Loss
TCP Sliding Window – Segment Loss
TCP Sliding Window – Segment Loss
TCP Sliding Window – Segment Loss
Original flow + loss control
Two types of flow control
Congestion collapse
TCP Sliding Window – Segment Loss
TCP Sliding Window – Fast retransmit
TCP Sliding Window – Fast retransmit
TCP Sliding Window – Fast retransmit
TCP Sliding Window
TCP Sliding Window – Avoid Deadlock
TCP Sliding Window – Window Update
TCP Sliding Window – Window Update
TCP Sliding Window – Persist Timer
TCP Sliding Window
TCP Sliding Window
TCP Sliding Window
Slide Number 23
TCP Congestion Control
Congestion Control Window
Incremental congestion control
Incremental congestion control
Incremental congestion control
Incremental congestion control – an example
Congestion control optimisation
Further Optimisation
Macroscopic model
Window size
Rate, fairness
And finally…
Acknowledgement
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com