Computer Networking Lecture Notes

2 October 2012 • Congestion & Flow Control

Outline

Transport behavior.
Flow control.
- Stop-and-wait
- Sliding window.
Congestion control.
- Prevention, detection, and mitigation.

Set Up

A wants to send a CD (700 Mb) or DVD (4.7 Gb) to B.

Easy peasy:

A does:

B does:

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

f = open("A big file")
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:

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

i = 0
while not eof()
  packet[i++] = read()

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.

Two Problems

Appropriate packet handling separates into two problems:
- The flow-control problem: treating the receiver kindly.
- The congestion-control problem: treating the network kindly.
Reliability is mixed in with both these problems.
- 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 expecting 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.

Observations

Throughput is proportional to window size/RTT.
The sender buffers unacknowledged packets for retransmission.
The receiver has a receive window of size n.
- The receive window buffers out-of-order packets.
What else can improve flow performance?

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.

Where's the Network?

Most networks can handle any connection from A to B.
- So what's the problem?
Most networks can't handle many connections from many As and Bs.
- A network is a shared resource.
Network congestion is a state of resource exhaustion in parts of the network.
- Congestion is a variable, dynamic condition.

Network Congestion

Network resources leading to congestion:
- Link bandwidth, into and out of network entities (routers).
- Intra-network buffering.
- Less important: intra-network CPU cycles.
As congestion grows, throughput falls, latency and delay increase.
- And variance on all grows.
- Until everything collapses.

A Congestion Portrait

congested behavior

Handling Congestion

Congestion can be dealt with in several ways:
- Prevention: congestion never occurs.
- Detection: end-points react to signals from networks and other entities.
- Mitigation: the network actively attempts to counter congestion.
Congestion handling is a combination of all three mechanisms.
- Which varies from network to network.

Congestion Prevention

Congestion prevention meters connections at the network edges.
- Connection requests are accepted based on available resources.
- This is known as admissions control (or policing).
Connection requests are tagged with quality of service (QoS) parameters.
- Principally mean and peak requirements.

Congestion Detection

Congestion detection flows from the networks out to the end-points.
Congestion indicators include
- Resource use high-water marks.
- Resource use variance.
Congestion signaling is explicit or implicit.
- Explicit indicators: congestion header bits.
- Implicit indicators: rate changes, lost packets.

Congestion Mitigation

Congestion mitigation attempts to configure networks to disperse congestion.
- Drop packets at resource-exhausted network points.
- Reroute connections away from congested areas.
Mitigation also sends signals to end-points.
- Hard to read, ambiguous signals.

Summary

Flow control manages sender transmission to benefit the receiver.
Flow control includes stop-and-wait and sliding window.
Congestion control manages sender transmission to benefit the network.
Congestion corresponds to network resource exhaustion.
Congestion control includes prevention, detection, and mitigation.

This page last modified on 2012 October 2.