Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

The primary algorithm used for congestion avoidance on implementing TCP in Berkeley is the additive increase / multiplicative decrease algorithm: additively increase a users load if there is no congestion then multiplicatively decrease load if there is timeout (this means there is congestion). The paper shows why the said algorithm is sufficient enough to control congestion in a computer network.

The analysis consists of many users (n users sharing a network), and 4 criteria to evaluate the algorithm namely efficiency, fairness, distributedness and convergence. The paper models the system in linear controls and it shows how the algorithm converges (distributedly/with or without trunctation) to efficiency and fairness. Furthermore, the paper explains that additive increase / multiplicative decrease offers the least the time of convergence to fairness.

I have three more questions in addition to the author's further questions. First, is the study of the algorithm scalable or still feasible on very large number of users? If the numbers of users suddenly increase exponentially, will the system work? Or even if it works, will the time of convergence (to fairness and efficiency) be still optimal? Second, in relation to the asynchronous operation, the connections in some networks such as mobile and wireless networks always come and go. Almost all have small time connections: a user connects, transfer small amount of data, then closes the connection immediately. Does this algorithm will solve the congestion problem? My last question is about outside interference. In wireless networks, there are many interference (eg. interference from other network) that influence the network. Do these interference affect the congestion?

Congestion Avoidance and Control

The paper is about congestion control and avoidance on TCP. There are three main topics, two are about congestion control and one for avoidance. I'll talk on the first two parts.

Slow-start is a technique used for congestion control (control only, not avoidance). Before without slow-start, the TCP connection suffers from congestion when packet bursts goes from high-bandwidth network to low-bandwidth network. Slow-start fixes this by adding a new state called cwnd. The state dictates the number of packets that will be send per burst. Every acknowledgment sent by the receiver increases cwnd by 1. Note that cwnd increases exponentially. When a congestion or packet loss occurs cwnd resets to 1. Slow-start is combined with many other algorithms to achieve congestion avoidance and control.

Sometimes, packet loss occurs by bad round-trip and retransmit timers which destroys equilibrium (packet isn’t put into the network until an old packet leaves). When congestion occurs, the connection thinks of it as a packet loss even if it is only a delay. It retransmits the packet, thus wastes bandwidth. Good implementation of round-trip timer addresses this by estimating the variation of round trip time (I understood the technical stuff after reading again and again). Another problem that is fixed but not covered in the paper is the spacing of retransmits if a packet has to be retransmitted twice or more.

I will discuss the algorithms used in dealing with avoidance of congestion on my next blog entry (actually, the algorithm is almost similar to slow-start. On any timeout, set cwnd to half the current window size. On each ack for new data, increase cwnd by 1/cwnd). There are other topics shown such as the gateway side of congestion control and detailed discussion of the algorithms for congestion control and avoidance. They are highly technical but very informative.

I read the paper 3 times. I really have no idea what was I reading the first time I read it. Theres too much jargon words (just like the previous papers) and only little information register into my puny brain. I was confident that this will be an easy read because I know what TCP does and how it works. I also had good experience on socket programming in two different languages. But I realize I really don't know how TCP is created and what are the underlying algorithms (in Berkeley sockets) which made TCP a success.

PS: I recall my professor talking about modifying the transport layer to optimize the connection in Eric Brewer's project. What part of these algorithms is modified? Do these algorithms are sufficient to solve the "very far connection" (yes, point-to-point connection about 200-300km apart) problem?