TCP Congestion Control
The internet was suffering from congestion collapse-hosts would send their packets into the internet fast as the advertised window would allow, congestion would occur at some router(causing packets to be dropped), & the hosts would time to out & retransmits their packets, resulting in even more congestion.
The idea of TCP congestion control is for each source to determine how much capacity is available in the network, so it knows how many packets it can safely have in transit. Once a given source has this many packets in their transit, it uses the ar rival of an ACK as a signal that one of it s packets has the left the network, & that it is t herefore safe to insert a new packet into t he network without adding to the level of c ongestion. By using ACKs to pace the transmi ssion of packets, TCP is said to self-clockking.
Additive Increase/Multipulcative Decrease:
TCP maintains a new state variable for each connection, called Con gestion Window, which is used by the s ource to limit how much data it is allowed to have in transit at a given time .The congestion window is congestion control‟s counte rpart to flow control‟s advertised window. TCP is modified such that the maximum number of bytes of unacknowledged data allowed is now the minimum of the congestion window and the advertised window .TCP‟s effective window is revised as follows:
Max Window =MIN (Congestion Window, Advertised Window)
Effective Window =M ax Window – (Last Byte Sent- Last Byte Acked)
The problem, of course , is TCP comes to learn an appropriate va lue for Congestion Window . Unlike th e Advertised Window, which is sent by the re ceiving side of the connection, there is n o one to send a suitable Congestion Window based on the level of congestion it perceiv es to exist in the network. This involves decreasing the congestion goes up & increasin g the congestion window when the level of con gestion goes down. Taken together,, the mechanism is commonly called additive increase/multiplicative decrease (AIMD);
The additive increase mechanism just described is the right approach to use when the source is operating close to the available capacity of the network, but it takes too long to ramp up a connection when it is starting from scratch. TCP t herefore provides the second mechanism, ironically called slow chat that is used to incr ease the congestion window rapidly fro m the cold start. Slow start effectively increa ses the congestion window exponentially, rather than linearly.
The source starts out by setting Congestion Window to one packet. When the ACK for this packet arrives, TCCP adds 1 to Congestion Window and then se nds two packets. Upon their receiving the corresponding two ACKs, TCP increme nts the Congestion Window by 2-one f or each ACK –and next sends four packets. The end result is that TCP effectively dou bles the number of packets it has in transit every RTT.
There are actually two different situations in which slow start runs. The first is at the very beginning of a connection, at which time the source has no idea how many packets it is going to be able to have in transit at and given time. In this situation, slow start continues to double Congestion Window each RTT until there is and loss, at which time a timeout cause‟s multiplicative decrease to divide Congestion Window by 2.
The second situation in which slow start is a bit more subtle; it occurs when the connection goes dead while waiting for a timeout to occur.
Recall how TCP „s sliding window algorithm works – when the packet is lost, the source eventually reaches a point where it is sent as much data as the advertised window allows, and so it blocks while waiting for an ACK that will not arrive. Eventually, a timeout happens, but by this time there are no packets in transit; meaning that the source will receive no ACKs to “clock” the transmission of new packets. The source will instead receive a single commutative ACK that reopens the entire advertised window, but as explained above, the source then uses slow start to restart the flow of data rather than dumping a whole window‟s worth of data on the network all at once.
Fast Retransmit and Fast Recovery:
The idea of fast retransmit is straight forward. Every time a data packet arrives at the receiving side, the receiver responds with an acknowledgement, even if this sequence number has already been acknowledged. Thus, when a packet arrives out of order – that is, TCP cannot yet acknowledge the data the packet contains because earlier data has not yet arrived – TCP resends the same acknowledgement it sent the
last time. This second transmiss ion of the acknowledgement is called a duplicate ACK
.When the sending side sees a duplicate ACK , it knows that the other side mu st have received a packet out of order, which suggests that an earlier packet has might have been lost. Since it is also possib le that the earlier packet has only been delayed rather than lost , the sender waits un til it sees some number of duplicate ACKs and then retransmits the missing packet. In practice, TCP waits until it has seen three duplicate ACKs before retransmitting the packet.