TCP Congestion Control Tricks and Concept

TCP Congestion Control

The goal of TCP Congestion Control

  • The goal of TCP Congestion Control is to determine the available network capacity and prevent network overload.
    Depends on other connections that share the resources.
  • Typically, in discussions, First in First Out queues are assumed; however, congestion control mechanisms work with other queuing techniques (fair queuing) as well.

Why TCP Congestion Control?

  • Congestion is bad for the overall performance of the network.
    Excessive delays can be caused.
    Retransmissions may result due to dropped packets
    Waste of capacity and resources.
    In some cases (UDP) packet losses are not recovered from.
    Note: Main reason for lost packets on the Internet is due to congestion — errors are rare.

The Congestion Window

  • In order to deal with congestion, a new state variable called “CongestionWindow” is maintained by the source.
    Limits the amount of data that it has in transit at a given time.
    MaxWindow = Min(Advertised Window, CongestionWindow)
    EffectiveWindow = MaxWindow – (LastByteSent -LastByteAcked).
    TCP sends no faster than what the slowest component — the network or the destination host –can accommodate.

Managing the Congestion Window

  • Decrease window when TCP perceives high congestion.
  • Increase window when TCP knows that there is not much congestion.
  • How? Since increased congestion is more catastrophic, reduce it more aggressively.
  • The increase is additive, the decrease is multiplicative — called the Additive Increase/Multiplicative Decrease (AIMD) behaviour of TCP.

AIMD details(TCP Congestion Control)

AIMD detail

  • Each time congestion occurs – the congestion window is halved.
    Example, if the current window is 16 segments and a time-out occurs (implies packet loss), reduce the window to 8.
    Finally, the window may be reduced to 1 segment.
  • The window is not allowed to fall below 1 segment (MSS).
  • For each congestion window worth of packets that have been sent out successfully (an ACK is received), increase the congestion window by the size of a (one) segment.

More AIMD details(TCP Congestion Control)

More AIMD Detail

  • Remember that TCP is byte oriented.
    does not wait for an entire window worth of ACKs to add one segment worth to congestion window.
  • Reality: TCP source increments congestion window by a little for each ACK that arrives.
    Increment = MSS * (MSS/Congestion Window)
    This is for each segment of MSS acked.
    Congestion Window + = Increment.
  • Thus, TCP demonstrates a sawtooth behaviour!

TCP Slow Start(TCP Congestion Control)

TCP Slow Start

  • Additive Increase is good when the source is operating at near close to the capacity of the network.
    Too long to ramp up when it starts from scratch.
  • Slow start –> increase congestion window rapidly at cold start.
    Slow start allows for exponential growth in the beginning.
    E.g. Initially CW =1, if ACK received, CW = 2.
    If 2 ACKs are now received, CW = 4. If 4 ACKs are now received, CW =8 and so on.
  • Note that upon experiencing packet loss, multiplicative decrease takes over.

Why Call it Slow Start?

  • The original version of TCP suggested that the sender transmit as much as the Advertised Window permitted.
  • Routers may not be able to cope with this “burst” of transmissions.
  • The slow start is slower than the above version — ensures that a transmission burst does not happen at once.

A second scenario

  • Let us say TCP has sent Advertised Window worth of packets.
  • No ACKs are received and TCP times-out and continues to block the application.
  • Ultimately an ACK is received which specifies that all sent packets are received (remember ACKs are cumulative).
  • Now, instead of dumping Advertised Window worth of packets (again a burst), TCP resorts to Slow start.

Where does AIMD come in now?(TCP Congestion Control)

  • The slow start is used to increase the rate to a “target window size” prior to AIMD taking over.
  • What is this target window size? — Unclear
  • In addition, we now have to do bookkeeping for two windows — the congestion window and the “target congestion window” where Slow start ends and AIMD begins.

The Congestion Threshold(TCP Congestion Control)

  • Initially, no target window — when a packet loss occurs, divide the current CW by 2 (due to multiplicative decrease) — this now becomes the target window.
  • Define this to be the “Congestion Threshold”.
  • Reduce actual CW to 1.
  • Use Slow Start to ramp up to the Congestion Threshold (or simply threshold). Once this is reached use AIMD.

Summary: TCP Tahoe

TCP Tahoe

  • Thus:
    When CW is below the threshold, CW grows exponentially
    When it is above the threshold, CW grows linearly.
    Upon time-out, set “new” threshold to half of current CW and the CW is reset to 1.
  • This version of TCP is called “TCP Tahoe”.

Fast Retransmit

Fast Retransmit

  • Coarsely grained TCP time-outs sometimes lead to long periods wherein a connection goes dead waiting for a timer to expire.
  • Fast Retransmit — a heuristic that sometimes “triggers” the retransmission of a packet faster than permissible by the regular time-out.
  • Every time a data packet arrives at a receiver, the receiver ACKs even though the particular sequence number has been ACKed.
  • Thus, when a packet is received in out of order, resend the ACK sent last time — a duplicate ACK!

Duplicate ACKs

Duplicate ACKs

  • When a duplicate ACK is seen by the sender, it infers that the other side must have received a packet out of order.
    Delays on different paths could be different — thus, the missing packets may be delivered.
    So wait for “some” number of duplicate ACKs before resending data.
    This number is usually 3.

Fast Recovery (TCP Congestion Control)

  • When the fast retransmit mechanism signals congestion, the sender, instead of returning to Slow Start uses a pure AIMD.
    Simply reduces the congestion window by half and resumes additive increase.
  • Thus, recovery is faster — this is called Fast Recovery.

TCP Reno (TCP Congestion Control)

  • The version of TCP wherein fast retransmit and fast recovery are added in addition to previous congestion control mechanisms is called TCP Reno.
    Has other features — header compression (if ACKs are being received regularly, omit some fields of TCP header).
    Delayed ACKs — ACK only every other segment.

Why TCP Congestion Avoidance?

  • TCP increases the load to determine when congestion occurs and then backs off.
  • Losses are the events that determine congestion.
  • But costly — can we predict the onset of congestion? Prevent loss?

DECbit (TCP Congestion Control)

  • Split the responsibility of congestion control between end hosts and routers.
  • Router monitors congestion and explicitly notifies end-host when congestion is about to occur
    Set a binary congestion bit called DECbit.
  • The notification reaches the destination which copies the bit in the ACK that it sends the source.
  • In response, the source adjusts transmit rate.

When is congestion perceived?

congestion perceived

  • The criterion for congestion is that the average queue length must be greater than or equal to 1.
  • This average is computed over a time-interval that spans the previous busy + idle + current busy periods.

The source response

  • The source watches as to what fraction of the received messages have the DECbit set.
  • If this number > 50 % then, congestion window = 0.875 the previous window.
  • Else, if it is < 50 %, congestion window + = 1.

Random Early Drop (RED)

  • Very similar to DECbit.
  • Each router monitors its queue length and if the queue length is longer than a certain value, drop packets (implicit notification) to indicate congestion.
    DECbit is an explicit form of notification.
  • Note that packets are dropped much earlier than usual — before buffer resources are exhausted completely — so drops are fewer
    Bursty drops are also reduced.

Details of RED

  • The principle is to drop the packet with some “drop probability” when the queue length exceeds a certain “drop level”.
  • Instead of a sample queue length, average queue length (more accurately captures the notion of congestion) is considered.
    AvgLen = (1-weight)*AvgLen + weight * SampleLen

More RED Details

  • With RED, two thresholds are maintained — the MinThreshold and MaxThreshold.
  • If AvgLen <= MinThreshold queue packet
  • If AvgLen >= MaxThreshold drop arriving packet.
  • If MinThreshold <= AvgLen <= MaxThreshold, then, calculate a drop probability P (as we will see) and drop the arriving packet with the probability P.

The Drop probability

The Drop probability

  • We define a new quantity called MaxP
  • This is the maximum value that P can take.
  • The linear increase between MinThresh and MaxThresh.
  • In reality, it is more complex — depends on how long has it been from the last drop.
  • We define:
    TempP = {MaxP * (AvgLen-MinThresh)} /(MaxThresh-MinThresh)
    and then, P = Temp/(1-count X TempP)
  • Here, count keeps track of the number of “newly” arriving packets that have been queued.

More about the drop probability

  • With an increase in count, notice that P increases.
  • This means that if a lot of new packets have been received after a drop, it is time to drop again!
  • Thus, this leads to “widely spaced” drops (a larger packet accumulation before consecutive drops) rather than closely spaced drops.
  • If sources are sending more data, more likely that their packets get dropped.
  • Rest of RED — self-study.

A Visit to Vegas(TCP Congestion Control)

  • Having routers participate in congestion control requires changes to core routers -difficult.
  • It is better to do this end-to-end.
  • However, we want to still have source-based control — now, it would be source-based congestion avoidance.
  • We need a TCP that watches out for signs of congestion –TCP Vegas.

Noting RTT variations

  • How much does the RTT increase with each packet sent?
    Note that with each additional packet, we are adding load.
  • One way — compute for every two round-trip delays (with an increase in a segment) to see if observed RTT > avg of min and maximum RTT.
  • If yes, reduce congestion window.

A second possibility(TCP Congestion Control)

  • Every RTT increases congestion window by a packet (or segment).
  • Compute throughput as the number of outstanding bytes divided by RTT.
  • Also, keep the value of the throughput that was achieved when only one packet was in transit (at the beginning of the connection).
  • If the difference between current throughput and this above-tagged throughput is less than 1/2 decrease congestion window by 1.

TCP Vegas

  • Somewhat in line with what we saw in the previous examples.
  • Source tries to match the available bandwidth exactly.
  • TCP source maintains what is known as BaseRTT — the RTT when the flow is not congested — typically the minimum of all RTTs observed.
  • It uses this value to determine if or not congestion is being experienced.

Expected and Actual Rates

  • The source computes an Expected Rate — Expected Rate = CongestionWindow/BaseRTT
  • Actual Rate is also computed — the number of bytes transmitted during the RTT of a tagged packet.
  • Diff = Expected Rate – Actual Rate.
  • Note that the Diff is always greater than or equal to zero (BaseRTT is the lowest !).

Vegas Rules

  • Define two thresholds α and β.
  • If Diff <, α TCP vegas increases congestion window linearly during next RTT.
  • If Diff >β, it decreases the congestion window linearly.
  • If α < Diff <β, TCP Vegas leaves the congestion window as is.

Vegas Behavior

Vegas Behavior

  • Green Line — Expected throughput
  • Black Line — Actual throughput
  • Shaded area — region between α and β thresholds
Posts you may Like


Please enter your comment!
Please enter your name here