Transcript ppt
TCP: flow and congestion control Flow Control Flow Control is a technique for speed-matching of transmitter and receiver. Flow control ensures that a transmitting station does not overflow buffer of receiving station with data We will discuss two protocols for flow control: Stop-and-Wait Sliding Window (used by TCP) For the time being, we assume that we have a perfect channel (no errors) Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher Stop-and-Wait Flow Control Simplest form of flow control In Stop-and-Wait flow control, the receiver indicates its readiness to receive next data frame Operations: 1. Sender: Transmit a single frame 2. Receiver: Transmit acknowledgment (ACK) 3. Goto 1. Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher Analysis of Stop-and-Wait Last bit received tack~0 propagation delay tprop Frame Frame transmission delay tframe Start Transmit End Transmit Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher ACK End of Transmit of ACK Receiver Efficiency = ? ACK Sender Last bit of ACK received Analysis of Stop-and-Wait Last bit received tack~0 propagation delay tprop Frame Frame transmission delay tframe Start Transmit End Transmit Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher ACK End of Transmit of ACK Receiver Efficiency = t frame 2 t prop t frame ACK Sender Last bit of ACK received Sliding Window Flow Control Notion of window-based flow control: Sender can only transmits those bytes that are within its sliding window Every time an acknowledgement (ACK N) is received, window slides to N (and its size is notified by receiver). Copyright ©: Caccamo Sliding Window Flow Control How is “flow control” achieved? At any instant, the sender is permitted to send bytes with sequence numbers within sliding “advertised window” Receiver controls size of sliding window (by means of window field in TCP header) ACK N, window W: receiver acknowledges all bytes up to (but not including) sequence number N and sets new window size W starting point of sender window slides to position N (in data stream) with size W Copyright ©: Caccamo Flow Control example Sender W=360 SND_next=1 W=260 SND_next=141 W=80 SND_next=321 SND_next=401, W=0 Sender stops transmission! Receiver TCP Congestion Control Congestion control was introduced in the Internet roughly eight years after TCP/IP was introduced. In the early years Internet was suffering severe congestion problems: Host would send packets as fast as it could still honoring advertised receiver window If congestion would occur at some router, packets would get dropped At timeout, host would retransmit those packets again creating even more congestion Copyright ©: Caccamo TCP Congestion Control Congestion control (at the sender side) tries to estimate available capacity in the network to prevent link congestion To implement congestion control, TCP introduces two new state variables for each connection Congestion window (cwnd): default 1 segment Slow start threshold size ssthresh: default 65535 bytes Copyright ©: Caccamo TCP Congestion Control By introducing congestion window, the max number of unacknowledged bytes in transit on the network is: min( cwnd , advertised _ window) Copyright ©: Caccamo TCP Congestion Control Quiz: How does the sender decide whether the network is congested or not? Copyright ©: Caccamo TCP Congestion Control Quiz: How does the sender decide whether the network is congested or not? We assume that a packet loss (hence, resulting in an ack timeout) is caused by dropping (due to congestion) somewhere in the network It is assumed that probability of a transmission error is very low TCP interprets timeouts as sign of congestion and it slows down transmission rate by reducing cwnd Copyright ©: Caccamo TCP slow start Congestion window cannot fall below the size of a single segment (packet), called maximum segment size or MSS At start of a new connection the congestion window is initialized to one segment Each time an ACK is received, the congestion window is increased by one segment Copyright ©: Caccamo TCP slow start Example: sender transmits one segment, after ACK is received cwnd is incremented from one to two, and two segments are sent. If both segments are acknowledged, the congestion window is increased to four (exponential growth) Exponential increase (not really “slow”), quickly increases window size up to network capacity Copyright ©: Caccamo TCP Congestion Control When congestion is detected by timeout ssthresh = ½ cwnd cwnd is set to one segment and connection restarts using slow start until ssthresh is reached (exponential increase) If cwnd ssthresh, TCP is in slow start. After the threshold, TCP switches to linear growth Copyright ©: Caccamo Exponential vs linear growth During exponential growth (slow start), contention window is doubled each RTT (round-trip time) until there is a loss During linear growth (additive increase) contention window is increased by at most one segment each round-trip time (regardless how many ACKs are received within RTT) assume each ack acknowledges reception of MSS bytes each time an ack is received a new increment is computed increment=MSS x (MSS/cwnd); cwnd = cwnd + increment Copyright ©: Caccamo Fast retransmit and recovery When congestion is detected by duplicate ACKs, it means that some but not all segments are received (moderate congestion) segments are out-of-order receiver acks each new packet. If packets are out-of-order, last ack is resent since new data cannot be acknowledged yet If 3 duplicate ACKs are received, assume that one segment has been lost and retransmit it immediately (fast retransmit) instead of waiting for timeout don’t reduce the flow drastically by using slow start: cwnd = ½ cwnd (fast recovery with linear growth) Copyright ©: Caccamo TCP Additive Increase/ Multiplicative Decrease After ssthresh is reached, TCP switches to linear growth to exploit unused network bandwidth (additive increase) Each time an ack is received a new increment is computed Increment=MSS x (MSS/cwnd); cwnd = cwnd + increment If congestion is detected by duplicate acks, cwnd = ½ cwnd (fast recovery with linear growth) Plotting cwnd as function of time, you obtain a sawtooth behavior timeout fast KB Copyright ©: Caccamo recovery time