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.