Computer Networking Lecture Notes

2014 September 29 • Transport Congestion & Flow Control

Outline

Transport behavior.
Flow control.
- Stop-and-wait to sliding window.
- TCP flow control.
- Rate-based flow control.
Congestion control.
- Prevention, detection, and mitigation.

Set Up

A wants to send a DVD (4.7 Gb) to B.

Easy peasy:

A does:

B does:

f = open("big.dvd")
c = connect("to B")
c.write(f.read())
c.close()
f.close()

f = open("big.dvd")
c = connect("from A")
f.write(c.read())
c.close()
f.close()

What does the rest of the system do?

Transport Behavior

a transport connection

How About This?

Sender does:

Receiver does:

packets = from-session()for i = 0 to n - 1
  write(packet[i])

i = 0
while not eof()
  packets[i++] = read()
to-session(packets)

This is the packet firehose.
Problem solved?

Objectives

The transport layer should handle packets so that
- The service it implements has the expected characteristics (reliability).
- The receiving end can handle data efficiently and effectively.
- The generated traffic doesn’t abuse the network.
Mission accomplished?

The Packet Fire Hose

Blasting packets from the sender at full host speed fails on all counts.
- Packet transport is unreliable.
- The receiver can get swamped with data.
- The network (a shared resource) probably can’t handle too much blasting behavior.
  - And if it can, the results are likely to be ugly.
Let’s rethink.

Problems

Appropriate packet handling separates into three problems:
1. The flow-control problem: treating the receiver kindly.
2. The congestion-control problem: treating the network kindly.
3. Reliability in the presence of best-effort service (IP service).
All three problems are mixed together.

Flow Control

The flow-control problem: manage the packet stream so that
- The receiver gets data as fast as possible, but no faster.
- The network handles packets with as little loss as possible.
- Both are run just this side of their upper limits.
Reliability is folded into packet handling too.

Stop-And-Wait Flow Control

stop-and-wait flow control

At the other extreme, send a packet and wait for an acknowledgment.

This is called stop-and-wait flow control.

Stop-and-Wait Reliability

stop-and-wait retransmissions

The sender times out on acks and retransmits.

RTO: round-trip time-out.

Time-Out Values

Time-out values combine mean round-trip time and variation (quasi-variance):
RTT_i = αRTT_{i - 1} + (1 - α)T_i
VAR_i = βVAR_{i - 1} + (1 - β)(RTT_i - T_i)
RTO_i = RTT_i + 4VAR_i
T_i = measured pkt-ack time
α = 0.75
β = 7/8

Stop-and-Wait Performance

How well does stop-and-wait perform?
If the network or the receiver are overwhelmed, then there’s no hope.
Round-trip time (rtt) bounds performance.
- Effective bandwidth = packet size/rtt
- Packet sizes are small relative to network bandwidth.
- Round-trip times are large.
How can performance be improved?

Improving Performance

Send two packets without acknowledgment.
- And expect two acks in return.
This effectively doubles the segment size from one to two packets.
- But the rtt increases too.
Better: allow two outstanding acks.
- Send out a packet immediately after receiving an ack.
Are the network and receiver stressed?

Turning the Crank

If doubling segment size improves performance, how about tripling it?
- How about making it n times bigger?
Increase n until either the network or the receiver gasps.
- n is a knob for tuning performance.
- It’s negotiated by sender and receiver at connection set-up.
  - And can be adjusted during transmission.

Sliding-Window Flow Control

The result is known as sliding-window flow control.
n is the flow-control window size.

TCP Sliding Window

TCP sliding windows

Segment Loss

segment loss, timeouts and retransmissions

The sender times out on acks and retransmits.

RTO: round-trip time-out.

Segment Duplication

segment loss, timeouts and retransmissions

Receiver buffering handles segment duplication.

RTO: round-trip time-out.

Segment Reording

segment loss, timeouts and retransmissions

Receiver buffering handles segment reordering.

Acknowledgments

Acknowledgments are important, but are expensive.
Acknowledgments can be:
- Negative (NACKs): unreceived packets.
- Cumulative: All packets up to the acknowledged packet received.
- Selective (SACKs): packets received independent of order.
Under varying circumstances, different acks provide better performance.

Ack Performance

In general
- Cumulative provides worst performance.
  - Received out-of-order packets are retransmitted.
- Selective acks provide better performance.
  - Immediate acks avoid unnecessary retransmissions.
- Negative acks provide best performance.
  - Only send acks when needed.

Rate-Based Flow Control

A receiver R can accept an average of k Mbits/sec.
- The receive buffer is neither too full or too empty.
Suppose a sender S can transmit an average of k Mbits/sec to R.
- No further flow control between S and R is needed.
This is the basis for rate-based flow control.
- Similar to media stream transmission.

Congestion Control

Most networks provide congestion control.
- Either at the network’s edge, or in the routers or both.
However, different networks use different congestion-control mechanisms.
- And trying to play nice with in-transit networks is hard.
Transport congestion control reacts network congestion control.
- Back off or push as needed.

TCP Congestion Control

TCP provides congestion control as a service.
- Performance mostly, and efficiency.
TCP makes minimal assumptions about the underlying networks.
- Starting with the lost packet assumption.
- However, handling TCP well is a goal for most networks.
- And TCP favors some network behaviors over others.

A Congestion Portrait

congested behavior

End-to-End Congestion Control

The sender detects congestion.
- Either by dropped packets or explicitly notification.
The sender throttles sending fewer packets into the connection.
- For the good of the networks.
The sender also tries to push back with more packets.
- For the good of the endpoints.

The Congestion Window

In TCP flow control the sender’s window is constrained by the receiver’s buffer size.
last acked - last sent ≤ receiver buffer size
In congestion control, the sender’s window is also constrained by the congestion window.
last acked - last sent ≤ min(receiver buffer size, congestion window)
Congestion control occurs by manipulating the congestion window size.

Start-Up Window Size

Setting congestion window = receiver buffer size is a hostile act.
- A large influx of packets all at once.
Start the congestion window at one packet, and increase by one for every expected acked received.
- This is an exponential increase.
- But known as slow start.

Slow-Start Example

slow-start example

The congestion window size equals the number of unacked packets.

Thresholding

Exponential growth is unsustainable.
- It quickly causes congestion.
TCP avoids congestion with a thresholding value.
The congestion window size grows by one when it’s larger than the thresholding value.
- This is an additive increase.
The onset of thresholding marks the end of slow start.

Thresholding Example

slow-start thresholding

Throttling

The sender interprets an ack time-out as evidence for network congestion.
Time to throttle:
- The threshold is reset to half the congestion window size.
- The congestion window size is reset to 1.
- Slow start begins again.

Throttling Example

Summary

Flow control protects slow receivers from fast senders.
- Flow control is an end-to-end property.
Congestion control protects slow networks from fast senders.
- Congestion control isn't an end-to-end property (and there's the rub).
TCP folds congestion control into flow control.
- UDP and IP have no control.

References

Congestion avoidance and control by Van Jacobson in Symposium Proceedings on Communications Architectures and Protocols, 1988.

This page last modified on 2014 September 30.