Congestion Control for High Bandwidth-Delay Product Networks

D. Katabi, M. Handley, C. Rohrs, "Congestion Control for High Bandwidth-Delay Product Networks," ACM SIGCOMM Conference, (August 2002).

Summary

This paper describes an alternative transport protocol to TCP called the eXplicit Control Protocol (XCP). One major problem with TCP is that as the delay-bandwidth product of links in a network increases, TCP becomes oscillatory and unstable, degrading performance, regardless of the congestion control or queueing scheme used at the routers. TCP can also be unfair to connections using high latency links. In addition, TCP unnecessarily delays the transfer of short flows, which are most of the flows in the Internet. Thus, this paper presents XCP as an alternative to TCP. Some of the main concepts underlying XCP are the decoupling of utilization from fairness control and the placement of state in the packets as opposed to the routers. The paper demonstrates that XCP is stable for any link capacity, feedback delay, or number of sources, and the parameters of XCP are constants independent of the environment. It achieves high utilization, small queues, and near zero drops in any environment. Other advantages of XCP are that allows for easy implementation of service differentiation schemes, it distinguishes error losses from congestion losses, it facilitates detection of misbehaving sources, and its performance is an incentive to deployment. Also, it is TCP-friendly.

The basic operation of XCP is as follows: An XCP sender maintains a congestion window (cwnd) and an estimate of round-trip time (RTT) just like in TCP. The XCP protocol defines a special congestion header carried in each packet used to communicate a flow’s state and feedback. This header contains a cwnd field set to the sender’s current cwnd, a RTT field set to the sender’s RTT estimate, and a feedback field, initially set to the sender’s demand and later reset by the router to provide feedback to the sender. The XCP router has an efficiency controller (EC) and a fairness controller (FC). These compute estimates of the average RTT of all flows over the link and make a single control decision every average RTT, which is the control interval. The EC computes the desired increase or decrease in the number of aggregate bytes to transmit in the next control interval. These bytes are allocated via the feedback field of the packet header. Exactly how they are divided up among the flows is decided by the FC, which uses an additive-increase multiplicative-decrease (AIMD) mechanism to converge to fairness – if an aggregate increase is desired, it allocates so that the increase in the throughput of all flows is the same, and if a decrease is desired, it allocates so that the decrease in throughput of a flow is proportional to its current throughput. In addition, the FC periodically shuffles allocation among 10% of the flows at a link in order to speed convergence to fairness.

This paper uses a fluid model to prove that XCP is stable independently of delay, capacity, and number of sources. It then provides a comparison of XCP to TCP Reno over Random Early Discard (RED), Random Early Marking (REM), Adaptive Virtual Queue (AVQ), and Core Stateless Fair Queueing (CSFQ) queueing policies. The queueing policy used with XCP almost never mattered because XCP almost never drops packets. These simulations show that XCP maintains near optimal utilization even in the face of capacity increase, feedback delay, increase in number of flows, and short web-like traffic, whereas TCP’s performance degrades. Also, XCP converges to fairness quickly and is not biased against long RTT flows like TCP, and is robust to high variance in the RTT distribution even though it uses average RTT. Moreover, XCP is able to dampen oscillations and respond quickly to sudden increases and decreases in traffic. Toward the end of the paper the authors describe how XCP can easily be used to provide differential service according to the shadow prices model and detect misbehaving sources. The also demonstrate that XCP is TCP-friendly.

Critique

I thought this paper was nice to read. It seems like their fluid model approach from control theory led to a very clean design and analysis of XCP. I tend to agree with their discussion about why the congestion signal shouldn’t be to drop packets and it needn’t even be binary. I also thought the extension to provide differential bandwidth allocation using the shadow prices model was good, especially as it seemed so straightforward to implement. I could see where that would be a commercially desirable feature of XCP.

I thought their argument that XCP could be used to facilitate policing agents that detect misbehaving sources was interesting but somewhat lacking. It might be nice to see this in action or to take a more detailed look XCP from a security angle and see if there are vulnerabilities that aren’t obvious from a first glance. This paper made me wonder why XCP isn’t supported in the Internet today. I’d be interested to see if anything ever came from this paper or if it was just a thought experiment.

Random Early Detection Gateways for Congestion Avoidance

S. Floyd, V. Jacobson, "Random Early Detection Gateways for Congestion Avoidance," IEEE/ACM Transactions on Networking, (August 1993).

One line summary: This paper presents an algorithm for congestion avoidance called Random Early Detection (RED) that drops packets probabilistically when the computed average queue length is between a minimum and maximum threshold in order to avoid congestion.

Summary

This paper presents an algorithm for congestion avoidance called Random Early Detection (RED). The authors argue that the most effective congestion detection can occur at gateways as opposed to the endpoints. In the current Internet, TCP only detects congestion when a packet has been dropped, meaning the queue at the gateway is full. Large queues at gateways are especially undesirable in networks with large delay-bandwidth product connections as it can significantly increase the average delay in the network. The authors also assume that it is useful to have queues at gateways in which traffic is multiplexed together with FIFO scheduling, and that per-connection gateway mechanisms such as those used in Fair Queueing should only be used when not having per-flow mechanisms is clearly inadequate. As RED does not use per-connection mechanisms, it is intended for networks where transport protocols are cooperative and respond to congestion indications, although it can be used to control congestion even when sources are not cooperative. In addition to the goals of keeping average queue size low and detecting congestion, RED places emphasis on avoiding global synchronization of TCP connections and avoiding bias against bursty traffic.

The RED algorithm works by first calculating the average queue size using a low-pass filter with an exponential weighted moving average. RED defines two thresholds, minimum and maximum. When the average queue size is below the minimum threshold, no packets are dropped. When it is above the maximum threshold, all packets are dropped. When it is between the two thresholds, each packet from the connections in the queue may be dropped with a probability that is a function of the average queue size, and this probability uniformly distributed and is proportional to that connection’s share of the bandwidth at the gateway. Later in the paper, the authors discuss setting the parameters for the algorithm. The weight in calculating the average should be selected to be not so low that it responds too slowly to changes in the actual queue size but not so high that the average fluctuates too wildly in response to bursty traffic. The minimum threshold shouldn’t be too low if traffic is fairly bursty. The maximum threshold depends on how high of an average queue length is tolerable. A rule of thumb is that the difference in the threshold values should be larger than the typical queue length increase in one RTT, in order to avoid global synchronization.

The authors state that RED meets the following goals: congestion avoidance, congestion detection at the same time scale as connections can respond to congestion, no global synchronization, simplicity, maximizing the throughput-to-delay ratio, no bias against bursty traffic (which the authors somewhat misleadingly term “fairness”), and appropriateness for a wide range of network environments. To show this they conduct a number of simulation experiments that compare RED with Drop Tail and Random Drop gateways. They also show how RED gateways can be used to identify connections using more than their fair share of bandwidth by noting which connections are having more of their packets dropped, as the probability of a connection having its packets dropped is assumed to be equal to that connection’s fraction of the link bandwidth through the gateway. Lastly, they provide an efficient implementation of the RED algorithm.

Critique

I didn’t really like this paper. I found it interesting that they argued for FIFO queueing, and I’m not sure I found their arguments as compelling after reading the other congestion avoidance papers we read. I also found their talk about their algorithm being “fair” rather misleading, since they don’t mean fair in the accepted sense. I think they gloss over the issue of true fairness as it was talked about in the Fair Queueing paper a little bit too much. Also, proper setting of the parameters of their algorithm seems to be important, but despite their rough guidelines it may not always be clear what the proper setting is. This seems like an undesirable property of their algorithm. It does seem like a step up from Drop Tail and a smaller step up from Random Drop, I will give them that. However, as I think we mentioned in class, I don’t think that this has led it to be widely implemented anyway. On more of a nit-picky note, I thought that a lot of their phrasing was awkward and their graphs were absolute crap (difficult to read, didn’t even have legends). I didn’t think the paper needed to be 20 pages long.

Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks

I. Stoica, S. Shenker, H. Zhang, "Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks," ACM SIGCOMM, (August 1998).

One line summary: This paper describes Core-Stateless Fair Queueing, a mechanism for implementing fair allocation in networks in such a way that minimizes the amount of state stored and the complexity of algorithms implemented in core network routers by relying on edge routers to perform flow rate estimation and labeling.

Summary

This paper presents a mechanism for fair allocation called Core-Stateless Fair Queueing (CSFQ). CSFQ identifies contiguous portions of the network as islands consisting of edge routers and core routers performing different functions to provide fair allocation in a simple and effective way. Edge routers compute per-flow estimates and label packets passing through them for use by core routers. Core routers keep no per-flow state and execute FIFO queueing and probabilistic dropping using the information in the packet labels put in place by the edge routers. The authors’ motivation for designing CSFQ begins with the assumptions that fair allocation is important to congestion control and that the complexity of existing mechanism hinders their adoption. The goal of CSFQ then is to achieve fair allocation while avoiding the need for core routers to maintain per-flow state or use complicated algorithms.

The authors use a fluid model to design and analyze CSFQ. Their fairness model is min-max fairness. Their algorithm uses the concept of max-min fairness to calculate the fair share of each flow. When the total arrival rate of all flows is less than the link capacity, no packets will be dropped. When arrival rate exceeds link capacity, those flows that are using more than their fair share will have packets dropped with a probability based on the amount they are using over their fair share. Two challenges in this algorithm are estimating flow rates and estimating the fair share. To estimate flow arrival rates, the algorithm uses an exponential averaging formula. Estimating fair share is more complicated. It is based on the prior estimate of fair share, the estimated total arrival rate, the estimated rate at which the algorithm accepts packets, and whether or not the link is congested. Edge routers estimate flow rates and use this to label packets. Note that these labels must be rewritten at a link that is congested because the estimated rate will no longer be accurate; the minimum of the estimated rate and the fair share rate instead. When experiencing congestion, core routers use the estimate of the flow rate and the estimate of the fair share to perform probabilistic dropping of flows’ packets based on how much beyond their fair share these flows are using. The authors briefly mention an extension that could be implemented to CSFQ that uses weights. They provide performance bounds for CSFQ and show that flows cannot use more than their fair share over the long run, so their algorithm does ensure fairness. They also demonstrate how their algorithm could be efficiently implemented in contemporary routers.

The authors compare CSFQ with four other algorithms. Two are baseline cases that do not ensure fairness: FIFO and RED. The other two represent alternative approaches to ensuring fairness: FRED and DRR. The authors note that CSFQ edge routers have complexity comparable to FRED while core routers have complexity comparable to RED. This is important because one of the main arguments of the authors is that CSFQ is simpler and thus more feasible to deploy. Their findings include that CSFQ provides reasonable fairness even in the face of ill-behaving source, works with different underlying flow control schemes, performs well over multiple congested links, reacts well to bursty traffic, performs reasonably when there is large link delay, and works well even when packets must be relabeled. In general, CSFQ provides fairness comparable to FRED but in a much more scalable manner. The authors also show how CSFQ can be extended to punish unfriendly or unresponsive sources.

Critique

In general, I liked this paper. I especially thought their experiments were nice and clean and revealed interesting aspects of the systems tested. However, as the authors admit, their experiments do not fully reveal how CSFQ would operate over more complex topologies, especially one containing large latencies. Large latency links seem to be a hazardous area for many a network protocol.

One concern is whether CSFQ would in fact be easier to adopt and administer than other fair queueing algorithms. That was one of their main motivations for proposing the architecture, but the fact that it has to be adopted on an “island-by-island” basis as opposed to a router-by-router basis seems potentially awkward. As the authors freely admit in the beginning of their paper, their underlying assumptions are open to debate. In particular, it was (and still is?) arguable whether other fair allocation mechanisms are too complex to implement and deploy in contemporary routers. While this may indeed turn out to be false, I think I recall discussing in class the fact that fair allocation mechanisms weren’t really implemented in most routers today. I may be misremembering this, but if not, then we can’t really say if the authors’ goal of providing a simple and feasibly deployable fair allocation mechanism has been met, since it hasn’t really been tested in practice.

Analysis and Simulation of a Fair Queueing Algorithm

A. Demers, S. Keshav, S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm," Internetworking: Research and Experience, 1 (1990), pp. 3-26.

One line summary: This paper proposes a fair queueing algorithm for congestion control at gateways and provides analysis and simulation results for this algorithm.

Summary

This paper proposes a fair queueing algorithm for congestion control at gateways. As the authors point out, there are two points at which congestion control can be implemented. The first is at the source and the second is at the gateways. At the source, flow control algorithms, while not directly designed to control congestion, do affect overall network traffic. At the gateways, congestion control can be implemented through routing algorithms, such as adaptive routing, and through queueing algorithms, which affect congestion indirectly. This paper focuses on the latter.

The authors note that queueing algorithms can be thought of as allocating bandwidth, promptness, and buffer space. The most commonly used queueing algorithm, first-come-first-served (FCFS) does not address each of these things separately. The authors argue that it is important to consider how flow control algorithms interact with queueing algorithms to affect network congestion. With this in mind, a major shortcoming of FCFS is that it does not provide good congestion control in the presence of ill-behaved sources in the network i.e. sources that do not provide good flow control and thus flood the network with packets. Such ill-behaving sources can unfairly capture high portions of the outgoing bandwidth of gateways implementing FCFS. In response to this, the authors propose a fair queueing (FQ) algorithm.

The authors’ requirements of their algorithm are: it must be able to allocate bandwidth and buffer space fairly; it must be able to control promptness/delay somewhat independently of bandwidth and buffer space; and it should provide service that does not depend discontinuously on a packet’s time of arrival. To define fair, the authors use the max-min fairness criteria, which state that an allocation is fair if (1) no user receives more than it requests, (2) no other allocation satisfying the first condition has a higher minimum allocation, and (3) the second condition remains recursively true as the minimal user is removed and the total resource amount reduced accordingly. The authors define a user as a source-destination pair, or a conversation. They then define their algorithm, which is based on a packetized version of a bit-by-bit round-robin scheme. Essentially, they first allocate a queue to each conversation. Then they consider the packets at the head of the queue, and estimate what they call the ‘finish time’ for these packets, which is the time at which the packet would finish being serviced. Finally, the algorithm selects the packet with the lowest finish time for transmission. The authors build upon this algorithm by introducing an additional factor that they call the bid. In this improved version of the algorithm, the packets are selected for transmission based on their bid, which is calculated in such a way as to provide less delay to users using less than their fair share of bandwidth. When the gateway’s buffers begin to fill, it must choose packets to drop. The way the authors’ algorithm selects a packet to drop is by choosing the last packet from the user currently using the most buffer space.

The authors then analyze their algorithm with respect to two types of sources: FTP-like sources and telnet-like sources. They do a bunch of annoying math and conclude that their algorithm is indeed able to provide lower delay to lower throughput sources. They then consider their algorithm with respect to flow control algorithms. They consider three types, (1) generic flow control algorithms using a timeout mechanism and a sliding window of set size, (2) second generation flow control algorithms using dynamic window sizes, fast retransmits, improved timeout calculation, and congestion signals, and (3) third generation flow control algorithms, which are similar to the second except that congestion signals are sent selectively. They select one flow control algorithm from each category and use them each with their FQ algorithm and with the FCFS algorithm to compare the two via simulation. They provide a lot of results but the main lesson from these is that FQ gateways cannot control congestion by themselves but can help protect from ill-behaved sources. Their FQ algorithm isn’t perfect and its performance depends a lot on the flow control algorithm used and the specific network dynamics, but it still provides much better fairness than FCFS.

Critique

There are a few things I didn’t like about this paper. I found all their mathematical analysis a bit much. It was annoying to read, especially the preemptive versus nonpreemtive bit, which didn’t factor in much anywhere else in the paper. I think it would have been better if the authors included all the mathematical details in an appendix and used the space instead to state their main point and conclusion of all that analysis, which as far as I can tell, they did in just one sentence out of 3-5 pages. The unused space then could have been used to provide some psuedocode or examples of their algorithm in action. These things would have made their paper much more appealing.

The authors also point out that there are objections to their algorithm, which might be interesting to discuss. The first objection is that some source-destination pairs, such as mail servers, need more than their fair share of bandwidth. The second is that their algorithm is too complicated to implement on routers in a such a way that it could run fast enough to match the speed of the links. It wouldn’t be very useful or compelling if their algorithm slowed the routers down.

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

D-M Chiu, R. Jain, "Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks," Computer Networks and ISDN Systems, 17 (1989), pp 1-14.

One line summary: In this paper the authors algebraically analyze a subset of algorithms for congestion avoidance with respect to a number of criteria, including efficiency, fairness, distributedness, and convergence; they are able to conclude that the optimal algorithm uses additive increase and multiplicative decrease.

Summary

In this paper, the authors analyze decentralized algorithms for congestion avoidance based on binary feedback signals, focusing on what they call increase/decrease algorithms. They focus on an abstract system in which there is one bottleneck resource used by n users. They assume that the binary feedback signal indicates whether this resource is overloaded or underloaded, and that the signal is sent by setting a bit in the packet header. They also assume that the feedback and control loop is synchronous across all users. The authors focus on linear control functions. In this context then, increase/decrease algorithms are merely those in which one signal indicates that the resource is underloaded and the load should be increased, and the other signal means the opposite. Examples of such algorithms include multiplicative increase/additive decrease and additive increase/multiplicative decrease.

The criteria by which the authors select controls are efficiency, fairness, distributedness, and convergence. Efficiency is measure by how close the total load on a resource is to the point where any further load would cause a decrease in response time and throughput, i.e. the point of maximum utilization and throughput and lowest response time. Fairness is measured by a function that the authors define which attempts to measure how equal the allocation of the resource is across all users. Distributedness means that the users only have limited knowledge of the system, in particular, whether the resource is overloaded or underloaded. Lastly, convergence is a measure of both responsiveness, or how fast the system takes to reach equilibrium, and of smoothness, or how large the oscillations around the equilibrium are. They choose to examine distributed linear control functions that converge to efficient and fair states.

In order to analyze the set of possible control functions, the authors represent system state transitions in an n-dimensional vector space (representing the load for each of n users) across discrete time slots. The ith user’s load at time t is x_i(t) and the load at the next time interval, x_i(t+1), is a function of the control scheme used with the load at time t and the system feedback. For example, it could be that x_i(t+1) = a + b*x_i(t) if the binary signal is indicates the resource is underloaded. In this function, a is additive and b is multiplicative. With this representation, they are able to deduce algebraically a number of propositions. The first is essentially that the decrease policy should be multiplicative and the increase policy should have an additive component and can optionally have a multiplicative component with coefficient no less than one. The second proposition is that both the increase and the decrease can have both additive and multiplicative components provide that a special step is taken in the case when certain convergence restrictions would be violated. The third and most conclusive proposition is that for feasibility and optimal convergence, the increase should be additive and the decrease should be multiplicative.

At the end of the paper, the authors describe what nonlinear control functions in congestion avoidance algorithms might look like, but reason that because such control is too sensitive to various system parameters, the robustness of the control is decreased. On this note, they go on to enumerate a few practical considerations in choosing an algorithm for congestion avoidance. The first is that it should be independent of hardware and software parameters as much as possible in order to reduce the complexity of the configuration task and make configuration errors less possible. The second consideration is that the resources and allocations must be measured in integers, so this should be taken into account when choosing an algorithm. The last practical consideration they mention is ease of implementation. Given all these considerations in addition to the result of their earlier analysis, they conclude that an algorithm that uses a linear control function with additive increase and multiplicative decrease is optimal.

Critique

I didn’t like everything about this paper. I thought that it was a bit too abstract, and I think in general it is no trivial matter to translate abstract results into real working solutions. However, given that there appear to be so many different algorithms for congestion avoidance, of which they only examine a subset, their analysis does provide some solid guidance in choosing among these, especially if you accept that the conclusions they draw from their analysis of their simplified system still completely hold in the much more complex environment of real systems. Since real TCP uses additive increase/multiplicative decrease, it seems that this could be a safe bet.

I’d be curious to see if algorithms with control functions other than additive increase/multiplicative decrease have been tested in practice. The authors mention that this paper is just one in a series of papers in which they examine a range of mechanisms for congestion avoidance, so an interesting exercise might be to take some of the algorithms they look at in their other papers and actually test them against additive increase/multiplicative decrease, and also maybe examine some algorithms that use nonlinear control functions.

One thing I did really like about this paper is their use of graphs. Whereas some of the algebra was at times a bit tedious or difficult to follow, I thought the graphs helped them provide a nice, clear, and more intuitive explanation for how the control functions worked and how they converged to fairness and efficiency. Although these graphs were further simplified on top of their simplifying assumptions, in that they represented the case with only two users, they were still pretty much key in helping me to understand some of their conclusions.

Congestion Avoidance and Control

V. Jacobson, M. Karels, "Congestion Avoidance and Control," ACM SIGCOMM Conference, (August 1988).

One line summary: This paper describes several important algorithms for congestion control in TCP, including slow-start, exponential backoff, multiplicative decrease additive increase, and RTT variance estimation; the paper also provides results that demonstrate that implementations of TCP using the algorithms described in the paper are better than older implementations.

Summary

The authors note that due to an explosive increase in size, computer networks have increasingly experienced congestion problems. Seven algorithms added to TCP are meant to help deal with this: round-trip time (RTT) variance estimation, exponential backoff, slow start, aggressive receiver ACK policy, dynamic window sizing, Karn’s algorithm, and fast retransmit. The authors describe the first five of these algorithms. According to the authors, these algorithms stem from the observation that a TCP connection should obey a “conservation of packets” principle, which basically states that for a connection in equilibrium, the sender should not place a new packet into the connection until an old packet leaves. There are three instances in which this principle will not be upheld: when the connection doesn’t initially reach equilibrium, when after equilibrium is reached, a new packet is sent before an old packet leaves, and when resource limitations along the connection path make equilibrium unattainable. The authors address each of these in turn.

The first failure occurs when a connection is being started or restarted. The authors note that a TCP connection is a self-clocking system, which help makes it stable, however, this also means that in order to get packets flowing there must be ACKS to clock them out, but to get ACKS there must be packets flowing. The authors thus describe the slow-start algorithm as a method for “starting the clock” and gradually increasing the number of packets flowing. The slow-start algorithm is as follows: For each connection, store a variable called the congestion window that will be used to determine the number of packets to send. When starting or restarting, set the congestion window to 1 packet. Every time a packet is acknowledged, increase the congestion window by 1. To select how many packets to send at a time, choose the minimum of the congestion window and the receiver’s advertised window. The result of this algorithm is that if no packets are lost or delayed, the congestion window doubles every RTT, and never will the sender send packets at a rate faster than twice the maximum send rate on the connection path. The authors find that this algorithm greatly decreases the number of retransmits and increases effective bandwidth.

The authors next explain that the second failure must be due to a sender’s faulty retransmit timer. This timer should estimate the RTT, which increases when load increases, in order to determine when a packet should be retransmitted, but one mistake in doing this is not estimating the variance in the RTT. The authors present an easy-to-calculate method for estimating the variance in their appendix. Another mistake is not choosing the correct backoff after a packet is retransmitted. The authors argue that only exponential backoff schemes have any hope of working in the general case. The authors demonstrate that a timer that estimates RTT using their method more accurately approximates RTT than the method previously used in TCP.

Lastly, the authors point out that if the timers are doing a good job of estimating RTT, then a timeout probably indicates a lost packet instead of a broken timer. Lost packets are typically a sign that the network is congested, causing connections to encounter resource limits, which is the third failure case. Connection endpoints must have a way of responding to congestion such that they decrease the amount they send when the network is congested and increase the amount they send when it is possible to do so, in order to achieve the proper utilization of network resources while avoiding congestion. To this end, the authors introduce a multiplicative decrease additive increase algorithm. The reason the decrease happens much faster than the increase is because it is easy for the network to become congested and much harder for it to become uncongested. The algorithm works as follows: On a timeout, the congestion window is set to half of the current congestion window size (multiplicative decrease). For each packet acknowledgement received thereafter, increase the congestion window (cwnd) by 1/cwnd (additive increase). Then when choosing the number of packets to send, choose the minimum of the congestion window and the receiver’s advertised window. The authors note that this does not include slow-start because they are two entirely different algorithms, but they should be implemented together, which is done usually by having separate slow-start and congestion avoidance phases. The authors show that their congestion avoidance approach results in fewer retransmits and higher bandwidth utilization.

Critique

The algorithms the authors propose in this paper later made it into newer implementations of TCP, so in that sense, they were very successful. Their results demonstrate that their algorithms were generally an improvement over previous implementations. However, as the authors point out, there are still improvements to be made. For instance, none of their solutions ensure fair sharing of network bandwidth, so they propose this as an area of future work. (Then again, according to Kurose and Ross, the multiplicative decrease additive increase algorithm was later shown to converge to provide equal sharing of bandwidth by Chui in 1989, a year after this paper was published, so perhaps it was the case that this work did not need to be done after all.)

Also, in certain situations, TCP’s exponential backoff and congestion avoidance can cause serious performance problems. Regular TCP can be improved for high-performance networks and there are apparently some extensions to TCP for this. Investigation reveals that some of the later changes to TCP’s congestion avoidance algorithms were suggested in order to allow it to more appropriately handle networks with LFNs and high-latency links. Lastly, some of the assumptions that the authors make about the network aren’t necessarily always valid. For instance, the authors state that packets are lost due to either network congestion or packet damage, but that the latter occurs so infrequently that it is safe to assume that a timeout is almost always a sign of network congestion. However, in wireless networks, this assumption does not generally hold, so TCP’s congestion avoidance can in this case result in link underutilization. Thus, a modified mechanism that takes this into account would be appropriate for TCP in wireless networks.

I thought this paper was good, and obviously the algorithms described in the paper are important, as they are now an integral part of TCP. Congestion control is a very important service, without which the Internet could not function well, if at all. I was somewhat confused as to how much of the algorithms suggested were original contributions, since some of the footnotes seem to indicate very similar algorithms had first been suggested elsewhere. I found that the authors’ tendency to reference a handful of papers I hadn’t read without really explaining briefly what was in those papers inhibited my understanding. And just as a matter of personal taste, I did not like it that so much information was crammed into the footnotes and appendices; to me this made the paper less readable, although aside from this it was well-written.

[EDIT: From my comment about fairness as examined by Chui it's probably clear that I read this paper before I read the other one. ;-) ]