End-end congestion control: window-based congestion control
Sending transport entity maintains congestion window over sequence number space
- can send a packet if packet seq. # in window
- distinct from flow control window
on timeout
- loss assumed
- decrease congestion window size
- increase timeout value (in case packet was delayed)
ACK received: increase window size
- Everything is OK, so allow even larger window
End-end congestion control: TCP
uses window-based congestion control
two variables used
- cwnd
: congestion window size
- ssthresh
: threshold for slowing down rate of increase
TCP slow start + congestion avoidance:
- TCP window size = min(flow control window size, congestion control window size)
initialize: cwnd=1
ssthresh=16
loop: if (ACK received and cwnd <= ssthresh)
cwnd = cwnd+1
else if (ACK received and cwnd > ssthresh)
cwnd = cwnd + 1/ssthresh
else if packet timeout
ssthresh = cwnd/2 /* new thresh half current win */
cwnd = 1 /* new window size back to 1 */
forever
Network-indicated congestion control
Window-based control strictly end-end
- Network layer not involved, but congestion occurs in network layer!
One network-indicated approach: network "marks" packets passing through congested node
- Receiver sees congestion indication mark and tells sender to slow down
- Congestion-experienced flag in ISO CLNP, CWI (change window indicator in IBM SNA virtual route pacing
Second network-indicated approach: upon detecting congestion, congested router sends explicit message back to traffic sources to slow them down
- Text: choke packets
- Source quench in ICMP (Internet control message protocol)
- VR-RWI bit in SNA VR pacing
Network indicated congestion control: difficulties
Receiver-initiated control may have long feedback time in high-speed networks
- Sender may have 1000’s sent (but unACKed) packets before congestion indicator receiver
Both approaches require coupling of network and transport layer
- OK for homogeneous networks
- Difficult in internetworked environment, with different network layers
Rate-Based congestion control
- Congestion control particularly hard in high-speed networks
- e.g.,: 1 Gbit.sec ling, 225byte packet takes 1 microsec to transmit
- thousands of packets "in the wire" propagating cross country
- when congestion occurs, too late to react
- avoid congestion by regulating flow of packets into network
- smoother flows will avoid bursts of packets from different senders arriving at same node and causing congestion
- smooth out packet bursts at network edge on per session basis before they enter network.
Rate Based congestion control: leaky bucket
Goal: regulate rate at which sender can inject packets into network
- A packet must match up with (and remove ) a token before entering network
- Tokens added to bucket at rate r: controls long term rate of packet entry into network
- At most b tokens accumulate in bucket. Bucket size b control "burstiness" of arrivals
- Maximum number of packets entering network in t time units is b+rt
- XTP uses rate and burst parameters analagous to r,b
Congestion control by Buffer Preallocation
- Lack of buffering in network is fundamental cause of congestion
- Avoid congestion by allocating buffers to an end-end connection
- If insufficient buffers for a new connection, block it (as in circuit switching)
- Buffers dedicated to connection, link still shared
- Protects behaving connections from misbehaving one
Data link layer involved in transport layer congestion control
Congestion Control in ATM ABR Service
ATM ABR (available Bit Rate) service:
- allows sender to send at rate up to a peak cell rate (PCR)
- guarantees a rate of at least minimum cell rate (MCR) when needed
- sender rate may fluctuate between 0 and MCR, depending on sender need, network congestion
Congestion Control in ABR service:
- Combines aspects of rate-based and network-indicated congestion control
ATM ABR Congestion Control: EFCI
EFCI: explicit forward congestion indication
- Based on negative feedback ("bad things are happening") to sender
- Congested node (queue length > threshold) marks EFCI bit in sender-to-receiver cell
- Receiver sees EFCI set and notifies sender
- Sender decreases cell rate:
- ACR: allowed cell rate
- ACR = max(ACR *multiplicative decrease, MCR)
- Sender increases cell rate if no negative feedback in an update interval:
- ACR = min(ACR+ additive_increase, PCR)
ATM ABR Congestion Control: explicit rates
Sender declares every Nth cell as "RM" cell
- RM: resource management
- Records its PCR, allowed_call_rate in RM cell
- ER field in RM cell: used by switches to set source rate
Switch on sender-to-receiver path: if congested
- Determine new rate for that source (consider PCR, ACR)
- set ER field to indicate new rate only if new rate less than current ER value
Connection Management: connection paradigms
Connection-oriented
- Explicitly setup/tear down connections
- Setup up session context
- Initial sequence number, flow control window size
- Exchange data within context of connection
- e.g., TCP, ISOI TP4
Connectionless service
- Pure datagram
- One-time unreliable send
- e.g., UDP (RFC 768), ISP CLTP (ISO 8072)
- transaction oriented
- single request from sender, single reply from receiver
- VMTP protocol
Connection Management: fundamental issues
Source of problems:
- Network can delay, reorder lose packets
- Timeout/retransmit introduces duplicates of data, ACKs, connect, close packets
On packet arrival: is it real or is it memorex?
- New connection request/release from "real live client" or an old one
- Transport protocols must create/maintain/destroy enough "state" information to answer the memorex question
- Explicit connection establishment/teardown with connection-oriented service
Two basic approaches for setting up a connection
- Two way handshake with wristwatch
- Three way handshake
<