Understanding TCP Incast Throughput Collapse in Datacenter Networks

Thoughts

This paper explores the incast problem and evaluates proposed solutions.

The authors first reproduce the incast problem on several different clusters. They verify that the problem occurs repeatably in different environments. Next, they implement the solutions proposed in "Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication." They evaluate four possible modifications:

1. Decreasing minimum RTO
2. Randomizing minimum RTO
3. Setting a smaller multiplier for RTO exponential back-off
4. Using a randomized multiplier for RTO exponential back-off

The authors find that adjusting the RTO exponential back-off was unhelpful because there were only a small number of exponential back-offs during the transfer. Surprisingly, they found that randomizing the minimum RTO was also unhelpful. They attempt to explain this by stating that router queues are a fixed resource so even if the retransmissions are randomized, the packet loss is synchronized by the shared router queues. The only approach that was helpful was decreasing the minimum RTO. This works well for a limited number of senders.

Finally, the authors propose a model for throughput given the number of senders. The model works well for 200ms timers but fails to predict throughput at smaller timer values.

Thoughts

I like the idea of creating a model to explain the odd behavior of TCP during incast. However, some of the explanations in the paper were not completely convincing. For example, I am not convinced by the explanation of why randomizing the RTO does not help.

Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication

Summary

This paper describes the "TCP incast" problem and proposes several possible solutions.

Incast occurs when a program issues "barrier-synchronized requests" to multiple servers. For example, parallel reads in a distributed FS. The servers all respond at roughly the same time so a large volume of traffic is sent. This causes congestion and large packet loss. Next, TCP goes into retransmission and waits for the RTO of approximately 200ms. Due to this slow retransmission, the link gets very low utilization and the clients cannot progress.

This problem may repeat due to syntonization of the RTO timers, so multiple servers can attempt to retransmit at the same time again causing packet loss and slow retransmission. This issues is particularly acute in data centers because normal transmission latencies are very low, much less than the default RTO of 200ms.

To solve this problem the authors propose to reduce the RTO timer and make it fine grained. The reduced RTO value will increase throughput by waiting for less time after packet loss. However, the authors find that this does not completely solve the problem for large (>1024) sets of servers. The issue is that the timers become synchronized. To avoid this the authors propose randomizing the RTO value.

Thoughts

This paper provides an interesting look at an unexpected problem. I am surprised that the RTO value does not automatically adjust below 200ms based on round trip latency.

VL2: A Scalable and Flexible Data Center Network

Summary

This paper presents a layer 2 network design for large data centers with a focus on "agility." The paper identifies 3 problems in today's data center networks:

1. Insufficient capacity between servers
2. Lack of isolation between services
3. Poor support for VM migration

To solve these problems the authors propose building a virtual layer 2 network connecting all of the servers being used for a particular service. This network would be structured in a Clos topology and use OSPF routing algorithms to make use of multiple routes thus improving capacity. Isolation can be provided by adjusting the bandwidth available for each virtual network. Finally, VMs can be easily migrated because IP addresses are used only as names with no topological significance.

To route packets, VL2 introduces an additional location-specific IP (LA) much like the hierarchical MAC in PortLand. VL2 also uses a proxy to handle ARP requests that are looked up in a centralized directory service rather than broadcasted to all switches.

Thoughts

This paper includes an interesting analysis of data center network activity showing that it is fairly unpredictable and also split between lots of small flows and a few large ones.

The evaluation was also quite convincing. The authors built a real system and used it to evaluate the system when performing an all-to-all shuffle. They show that the system has 94% efficiency with high fairness.

PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric

Summary

This paper describes a network architecture for large data centers running virtual machines. The key requirements are:

1. Support for VM migration
2. No administrator configuration
3. Efficient communication along any physical path
4. No forwarding loops
5. Rapid failure detection

The key design feature of this paper is to use hierarchical MAC addresses and a centralized fabric manager with soft-state. The hierarchical MAC addresses correspond to physical topology and thus simplify routing. However, manual configuration can be avoided by using a Location Discovery Protocol.

ARP requests are handled by the fabric manager which has a global view of IPs and MAC addresses. Migrating a VM just involves changing an entry in the fabric manager's table to assign an IP to a different machine.

They key difference between this approach and SEATTLE is the use of hierarchical addressing to simplify routing and using a fabric manager to provide fast and reliable ARP lookups.

Thoughts

It was not clear how well the LDP protocol works. The authors state that switch positions may be set manually or automatically, but the trade offs where not made clear.

I also would have liked to see a comparison between SEATTLE and PortLand in the evaluation.

Detailed Diagnosis in Enterprise Networks

Summary

This paper describes and automated system for determining potential causes of errors in machines and applications in a network. The authors propose building a dependency graph of which components may impact one another. This is done using templates such as "a machine depends on its processes and its configuration" and "an application process depends on its configurations, its NbrSet, its host machine and the configuration of the machine." Using these heuristics a graph of dependent components is built. When a problem is encountered the system searches for the potential cause. To do this the authors assume that correlation implies causation. They calculate the probability of the erroneous outcome given the state of each of its dependencies. This is done using historical data collected during normal operation. This probability determines the weight, w, of the corresponding edge in the dependency graph, implying that this edge has a potential impact of w. Finally, the potential causes are ranked based on the total weight of the path from the cause to the error combined with a measure of the abnormality of each component in that path. Components that are highly impacting more abnormal components will have a higher score.

Thoughts

This is a neat high-level way to diagnose problems, but I am surprised that it works as well as they claim. I am concerned that this approach may be limited to a small set of problems. Also, using correlation to imply causation will not work well in all cases even if the authors found it to be accurate for a set of problems. Specifically, this can be a problem when interactions become more complex and an unknown factor causes both correlated outcomes.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises

Summary

This paper describes a network architecture that combines the scalability of IP networks with the plug-and-play functionality of ethernet networks. The key idea is to extend ethernet routing to prevent broadcasts and optimize routing. Specifically, the paper proposes a DHT based lookup mechanism. When a node first joins the network it is discovered by the switch to which it is connected. This switch is responsible to adding the node's MAC to the directory. It does this by applying a consistent hash function to the MAC address and determining which switch is responsible for that hash value. The (MAC, location) pair is then stored by the designated switch. When a different host sends a packet, a lookup is preformed in the same manner and the packet is subsequently routed along the shortest path to the destination.

The key aspect of this algorithm is that the directory service eliminates the need for broadcasts, thus making the solution scalable. The network architecture also separates naming from locations, unlike TCP where nodes in a subnet must have a common prefix. This feature allows plug-and-play functionality where nodes do not have to be configured.

Thoughts

Overall, I like the idea; it would certainly be nice to have a large network with no configuration.

Part of the design requires caching directory entries, however, it is not clear how these caches would be invalidated when nodes disconnect from the system of failures occur. Also, I am concerned about the security of the system, it seems that nothing prevents nodes from spoofing MAC addresses or pretending to be switches.

Random Early Detection Gateways for Congestion Avoidance

Summary

This paper describes a method of notifying senders of upcoming congestion before it occurs. The method has the key benefits of being compatible with TCP and not requiring all gateways to use the same congestion control mechanism. This makes it a pragmatic choice, requiring fewer changes than "Congestion Control for High Bandwidth-Delay Product Networks."

The RED algorithm uses the average queue size to detect upcoming congestion. If the queue size is greater than a minimum threshold, packets form each connection may be marked with a congestion bit with some probability. This probability is proportional to he connection's share of the bandwidth at the gateway, thus the RED algorithm addresses both congestion and fairness.

Traditionally, TCP congestion control waits until the queue is full and then drops all packets. This has two negative consequences: dropped packets must be resent and all connections with dropped packets must slowly ramp up again. The RED algorithm addresses these issues by preemptively marking some connections as congested.

Overall, RED helps prevent congestion and keep delay low while being easy to implement on top of TCP.

Thoughts

RED still uses a binary signal for congestion in the same way as traditional TCP congestion control. It is less precise than the algorithm presented in "Congestion Control for High Bandwidth-Delay Product Networks" which allows routers to explicitly control the sender's congestion window. However, RED seems much easier to implement since it can work with TCP and current routers. It would be interesting to see how these two algorithms compare in efficiency and fairness.

Congestion Control for High Bandwidth-Delay Product Networks

Summary

This paper presents a new protocol that explicitly tracks the degree of congestion in the network and reacts accordingly. The authors observe that regardless of queuing scheme, TCP becomes oscillatory and prone to instability when facing high delay-bandwith products. Moreover, with current high bandwidth links, TCP "might waste thousands of RTTs ramping up to full utilization following a burst of congestion." The proposed solution is to have routers inform senders about the degree of congestion at the bottleneck.

The protocol adds an additional congestion header containing the current cwnd and rtt values on all outgoing packets. Routers along the path can set a feedback parameter that instructs the sender to change the cwnd size. Each router in the path can override previous feedback with a stricter requirement thus the bottleneck link will dictate the changes. Finally, the receiver must forward this congestion header in the ACK.

The specific feedback values are computed in two steps. First, the "efficiency controller" computes the window size that would use all available link bandwidth. Next, the "fairness controller" allocates this window to individual flows to preserve fairness. This is done using the Additive Increase Multiplicative Decrease algorithm.

The authors evaluate this protocol through a theoretical stability analysis and a simulation based empirical analysis. The results show that XCP significantly out performs TCP in both high bandwidth and high delay environments.

Thoughts

This paper presents a very precise solution for the congestion problem, relying on explicit signals rather than implicit packet drops. This sounds like a great idea that should be put to use. It also solves the problem in wireless networks of determining if packets were dropped due to congestion or interference.

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

Summary

The key idea of this paper is to implement a fair queueing algorithm with low implementation complexity and resource requirements.

In core-stateless fair queueing the edge routers mark flows and compute per-flow estimates of arrival rates. Next, the core routers compute the fair-share rate based on the number of incoming flows. If a flow has a rate exceeding its fair-share, packets are dropped. This is efficient because there are a lot more edge router than core routers so the complex work of estimating rates and annotating flows is spread out.

Thoughts

This is a clever idea to spread out the work of fair queueing across lots of routers. The obvious limitation is that the edge routers must be trusted to give accurate estimates. It is also unclear if this approach is necessary given the available processing power in modern routers.

Analysis and Simulation of a Fair Queueing Algorithm

Summary

This paper presents an algorithm that emulates bit-by-bit round robin to ensure fairness for multiple flows in the case of congestion. The authors observe that the standard first-come-first-serve algorithms have a number of problems that make them "unfair." For example, a "fire hose" sender that ignores congestion signals (e.g. dropped packets) can get a disproportionate fraction of the bandwidth.

There two main design requirements the authors follow:

1. Fairness - ill-behaved senders get no more than their fair share of bandwidth
2. Delay control - ability to control delay independent of bandwidth

The authors propose a new fair queueing algorithm. They first decide to do allocation based on conversations, e.g. source-destination pairs. To ensure fairness the algorithm emulates bit-by-bit round robin of packets from each conversation. To implement this they send packets by earliest finishing time.

Thoughts

This paper presents a good idea for improving fairness in networks. I wonder why this technique is not currently widely used?

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

This paper presents an analytical analysis of congestion avoidance algorithms and proposes an "optimal" algorithm.

The paper assumes that network throughput typically follows the curve shown in the figure on the right. In other words, throughput increases quickly with load until a point when the system is nearly saturated (the knee) after which the increase in throughput is slow and soon afterwards the throughput falls dramatically (the cliff) due to packet loss. Using this model, the authors argue that the optimal algorithm will keep the system at "the knee" to avoid congestion rather than using a back-off algorithm to control congestion after it occurs.

The authors evaluate algorithms on efficiency, fairness, distributedness and convergence. Efficiency refers to how close to the load is to the knee with the assumption that the knee is the optimal operating point. Fairness means that users bottle-necked on the same resource should have an equal share of it. Distributedness means that there is no central control with full system knowledge. Finally, convergence refers to the rate of reaching equilibrium (the knee) and the size of oscillations about the equilibrium point.

Using these criteria the authors determine the key traits of an optimal algorithm. Specifically, one should increase transmission rate additively but decrease it multiplicatively when congestion occurs.

I am not fully convinced that the throughput vs load curve is always of the shape that the authors assume. That being said the mathematical analysis of congestion is very valuable and suggests that currently used policies are probably quite good.

Congestion Avoidance and Control

Summary

This paper describes the key algorithms used to control data transmission and limit congestion in the Internet. The following algorithms are described in detail:

1. Slow-start
2. Round-trip timing
3. Exponential back-off
4. Window sizing

When transmitting data it is key to send at the rate of the slowest link in the path. This is necessary to avoid losses due to congestion. The rate of the slowest link can be approximated by the spacing (delay) between the returning ACKs, thus ACKs can be used to trigger sending the next packet. The problem is how to start this system, before data is sent there are no acknowledgments. This paper proposes the slow-start algorithm which creates a congestion window that is increased by one for each ACK received. The result is an exponential growth in the number of packets transmitted, until data is lost.

The next improvement concerns round-trip timing. It is important to have an accurate estimate of the round-trip time because the sender must know when to assume a packet has been lost, in other words, how long to wait for an acknowledgment before re-transmitting. The proposed improvement takes into account the fact that round-trip time variance increases with load. This avoids "the network equivalent of pouring gasoline on a fire" by preventing spurious retransmissions during times of heavy network load.

Finally, the paper describes how to avoid congestion. Specifically, it suggests that packet loss is a good indicator of congestion, since it is often caused by overflowing buffers in the path. So when packet loss is encountered the end points should exponentially decrease the rate of sending data. Specifically, the congestion window size is cut in half whenever a timeout occurs.

Thoughts

This paper very clearly explains the causes of network congestion and proposes simple and very well described techniques for dealing with it. Overall, I really enjoyed reading this paper.

I am concerned about the use of packet loss as a signal of congestion. Especially in wireless networks this seems like a bad idea. If a packet is lost due to wireless "noise" it is unclear that sending slower will have any benefit, in fact it may even make sense to send duplicate data faster to improve the chances of it reaching then receiver.

Understanding BGP Misconfiguration

This paper analyzes the prevalence of BGP misconfigurations and their causes. Specifically the authors focus on two types of misconfigruations:

1. Origin Misconfiguration. These occur when routes are injected accidentally into the BGP tables. Specifically this includes hijacking addresses and propagating private prefixes.

2. Export Misconfiguration. These occur when a route is exported in violation of policy.

The authors use a BGP listener (RouteViews) to view updates for 19 ASes. They identify origin misconfigurations by looking for updates that are short lived, lasting less than 1 day. To verify this classification they email the network administrators. For export misconfigurations the authors inferred relationships between ASes using "Gao's algorithm" and tested for violations to standard policies.

The findings showed that "at least 72% of new routes seen by a router during the day are a result of misconfiguration." However, these misconfigurations only lead to disruptions in connectivity 13% of the time. 80% of these incidents are corrected within less than an hour.

Interdomain Internet Routing

Summary

This paper describes the mechanism, policy and economics of Internet routing. The Internet uses topological addressing, so each route corresponds to some address prefix (e.g. 18.31.*). The key mechanisms and policies involve deciding how to route to addresses outside of one's network.

There are two types of agreements between ISPs: transit and peering. In transit agreements an ISP (or individual) will pay for access to a set of routes. In contrast, peering agreements are reciprocal, allowing traffic to from two networks to be exchanged freely. ISPs typically have peers, transit providers and transit customers.

The BGP protocol is the mechanism used to advertise routes allowing routers to build routing tables. To maximize profits, ISPs want to advertise routes to all customers, but not routes through peers (since no money is made from transmitting peer traffic) or routes through transit providers (since these cost money). Similarly, when importing routes ISPs prefer routes directly to customers (these earn money), followed by routes through peers (there are free), and finally routes through transit providers (these cost money). All of these policies are implemented automatically in the routers through prioritizing and filtering.

Unfortunately, the BGP protocol is not secure because it does not verify advertised routes. This allows malicious users and misconfiguration to cause traffic to be erroneously routed. For example, YouTube traffic was mistakenly routed to a "blackhole" in Pakistan.

Thoughts

At first glance, I am very surprised that this complex system with so many conflicting interests manages to (mostly) route traffic from anywhere to anywhere.

I am also curious about traffic ratios in peering arrangements. There seems to be an implicit assumption that the sender should pay for the traffic when both parties are interested in the connection.

Finally, as pointed out in the paper, the lack of security is alarming. Does one have to be an ISP to broadcast BGP advertisements or could any (small) customer potentially broadcast erroneous routes?

The Design Philosophy of the DARPA Internet Protocols

Summary

This paper describes the design goals and origin of current Internet protocols. The DARPA Internet originated as a way to interconnect separate networks, specifically packet radio and the ARPANET. Many of the original design decisions were pragmatic with the goal of leveraging as much existing technology as possible. For example, packet switching was used because it was already in use in existing networks. Gateways were the key new element that allowed multiple, separately administered, networks to communicate.

Next, the paper lists secondary design goals in order of priority:

1. Survivability
2. Multiple communication types
3. Variety of networks
4. Distributed management
5. Cost effective
6. Easy host attachment
7. Accountable resources
   

The top goals, namely survivability and support of multiple types of communication, heavily influenced the design and are still visible today. Survivability was key in a military setting to allow data to flow even if some links were cut. Similarly, multiple communication types were important because different applications had different requirements. For example, telephony requires low-latency but can tolerate loss while file transfer can tolerate delay but needs high throughput. These considerations led to the creation of both TCP and IP. TCP provided reliable communication while IP was a basic "datagram" protocol that could be built upon.

Thoughts

It is very interesting to see how the Internet evolved and how key decisions made over twenty years ago have a huge effect on how the Internet works today. While clearly many requirements have changed, for example, we now don't trust all nodes / networks, I am actually surprised how forward-looking the original design was. I was particularity impressed, that the original design anticipated the differing requirements of many types of communication and that the overall design was scalable.

End-to-End Arguments in System Design

Summary

This paper argues that providing extra functionality or strong guarantees in the communication system is redundant because applications must still re-implement this functionality at higher levels.

The authors provide a motivating example of a simple file transfer application. The application may fail for a number of reasons including disk errors, crashes, and errors in delivery. The argument is that because of this large set of errors, the application must implement a check for accurate delivery whether or not the communication system does a similar check at a lower level, thus, the low-level check is redundant.

A similar argument are made for secure data transmission. The network is not the only place where data may be leaked, thus encryption must be done at a higher level to protect against all leaks at once. Similarly, suppressing duplicate packets is unnecessary because the application may itself erroneously issue duplicate requests as part of failure/retry procedures.

Thoughts

This paper gets at the key question of how to design abstractions. On one hand, the application has the big picture knowledge of what is happening and what the goals are. In the extreme, this could be used to justify putting all functionality into the application, as in fact it has in the OS world in papers such as Exokernel. On the other hand, the whole point of an abstraction is to separate concerns thus making each piece easier to develop and maintain. This is why modern systems provide basic functionality, such as memory management or scheduling in operating systems, even when it may be more efficient to implement at a higher level.

This paper seems to argue for the "end-point" or application implementing all functionality extreme, however, a careful balance is needed. The paper alludes to this in the performance section when they admit that some reliability at the low-level is necessary to obtain acceptable performance (i.e. don't retransmit a whole file for one lost packet).

Overall, I agree with most of the examples in this paper, however, I believe that a careful balance must be struck between low and high levels to maintain ease-of-use and performance not just eliminating redundancy.