A Comparision of Mechanisms for Improving TCP Performance over Wireless Links

This paper compares the performance of TCP over a wireless link using various schemes believed to improve TCP performance, primarily by dealing better with losses over the wireless link. The used a real wireless link between one TCP endpoint and a gateway and the gateway was connected over a wired link(s) (Ethernet or the wide-area US Internet) to the other TCP endpoint. Though the authors used a real wireless link, they simulated single-bit losses (by corrupting TCP checksums) according to an exponential distribution. (The authors also performed one simulation where introduced errors caused more than one packet to be lost, finding that selective acknowledgment helped more than usual.)

The authors compare several types of schemes for improving TCP performance: gateway solutions where the gateway resends missing segments and (in TCP-aware schemes) possibly suppresses spurious duplicate ACKs also; gateway solutions that split the TCP connection into two TCP connnections; and purely end-to-end solutions. The authors find that several proposed improvements do help with caveats:

• link-layer retransmission schemes help by themselves but work a lot better when they also suppress spurious duplicate acknowledgments, which lead to spurious retransmits and congestion window size reductions (TCP-aware link-layer schemes provided the most improvement of all the schemes tested in the paper);
  
• end-to-end selective acknowledgments make good use of much of the bandwidth of the link without gateway modifications, but do not perform as well as gateway modifications especially with a wide-area connection; and
  
• splitting the TCP stream at the gateway performs not as well as link-layer snooping because of limited buffer sizes at the gateway
  

Though the authors mentioned “very high interactive delays” as a motivating problem observed in TCP over wireless, they disappointingly did not attempt to measure it in this paper.

MACAW: A Media Access Protocol for Wireless LANs

This article proposes a media access protocol targetted at a particular contended wireless network. In the network environment considered by the authors, connectivity is symmetric (if A can receive from B, B can from A) and relatively short range with a sharp strength drop off. Thus, the primary efficiency concerns with implementing wireless in the authors environment are collisions at the receiver, including from signals out of range of the transmitter.

The hidden terminal problem makes carrier sense inappropriate. Instead, the authors explicit Request-to-Send and Clear-to-Send messages to manage the channel. Additionally the authors add an explicit acknowledgment (to guard against giving the false congestion signals to TCP-like protocols) and an explicit Data-Sending message (so other nodes within range of the transmitter can avoid interfering with its reception of the CTS and ACK).

Nodes control their use of the network based on these messages. A CTS or DS message reserves the channel for long enough to send the corresponding data and its acknowledgment. Based on past apparent collisions and their (apparent) locations, nodes backoff the rate at which they send RTSs, separately estimating congestion at their location and at the receiver.

The authors evaluated the MAC protocol with simulations of a variety of network topologies, verifying that reasonably fairness between data streams was provided by the MAC protocol and good link utilization was achieved (even in the presence of hidden terminals, unresponsive nodes, etc.) Most of the simulations used loss-insensitive flows and assumed the reception success was dependent entirely on distance from the receiver and competing transmitters.

It is very nice that the authors evaluated many network topologies and these clearly evaluations where the author's improvements produce huge differences. However, the paper seems to lack evaluation of more realistic scenarios. Even though the authors ACK scheme is motivated by transport protocol performance, almost none of the authors simulations consider performance of a TCP-like transport protocol or even how intermittent noise affects their link-layer protocol alone. The authors also do not consider any metric besides stream throughput, such as how much jitter and latency this MAC protocol introduces into the network.

Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication

This paper examines the consequences of one potential to the incast collapse (loss of useful throughput given several simultaneous TCP streams being received by a sink) problem: lowering or eliminating the minimum retransmission timeout. The intuition behind this change is that it will speed recovery from serious congestion events and that the very short and predictable round-trip times of datacenter networks do not require the current default's large margin of safety. They implemented this timeout reduction both in simulation and by modifying the Linux kernel TCP implementation (which required allowing timeouts to be triggered other than on the timer interrupt and internal timers to have better than 1ms granularity).

First, they evaluated this workload in an incast scenario; here, they had the sink pull 1MB data split evenly across a varying number of servers and measured the effective throughput (‘goodput’). Both simulation results and experiments showed a dramatic increase in useful throughput for small (approx. 1ms) minimum retransmission timeouts compared to values closer to the current default of 200ms. Based on RTT information from high-bandwidth (~10Gbps) datacenter networks and simulations, the authors further suggested that future networks will have substantially lower round-trip times, so minRTO should be eliminatined entirely. For such networks, the authors also reccommended adding random variation to the computed RTO to avoid accidental synchronization (from similar RTTs).

The authors also examined some possible negative impact drastically eliminating the minimum retransmission timeout would have. Two different sources of spurious retransmissions and delays are considered: from underestimates RTT due to a delay spike and from ACKs delayed for longer than the retransmission timeout. For both problems, the authors performed a comparision of Bit Torrrent throughputs observed with and without a very small minimum RTO. They found little difference in the per-flow throughput distribution with a low minimum retranmission timeout.

For delayed ACKs, the authors compared throughput in an 16-node fan-in situation with and without delayed ACKs. They found that enabling delayed ACKs (with a delayed ACK timer larger than the round-trip time) caused a substantially lower throughput with large fan-in.

The solution proposed in this paper is relatively easy to deploy, simple, and seems to work with few negative consequences. The authors suggest that the spurious timeout avoidance the minRTO was set for is no longer necessary now that recovery from spurious timeouts does not cause entry into slow-start. But do the delay spikes that motivated the original minRTO setting still exist? (Is better recovery from misestimation enough?)

Understanding TCP Incast Throughput Collapse in Datacenter Networks

This paper is another examination of solutions to and the cause of the incast problem. They analyze the incast phonemon with and without the changes proposed in the CMU paper (much lower minRTO/disabling delayed ACKs). Unlike the CMU paper, the evaluation here primarily uses a constant data per source scenario rather than a constant data per sink scenario. They find that this fixed-source-size workload yields more complex goodput behavior than the other scenario. And in contrast the CMU findings, the authors find that delayed ACKs, in fact, do help against incast for large numbers of senders because they induce increased variance in the RTT estimate and TCP window size.

The authors produced a simple numerical model of the throughput collapse behavior assuming that it is determined by the number of retransmission timeout events and the interpacket wait time. From this model and refinements, the authors produce an explanation for the throughput collapse behavior: first, throughput collapses as the number of retransmission timeouts increases with the number of senders, then the width of period in which retransmission timeouts are triggered (per congestion event) increases, so recovery senders become desynchronized, but eventually the width of that distribution becomes so wide that senders about to experience a timeout interfere with senders just recovering from a timeout.

It is disappointing that the qualitative observations which would seem to explain the throughput collapse are not incorporated into the model, nor is an good empirical way to test for their presence beyond fitting a more complicated model attempted or suggested.

VL2

This paper is remarkable similar to PortLand. Therefore, I will focus first on the differences:

• Topology — the supported topologies are folded Clos networks. Similar to fat trees, these provide many paths between racks and, as in PortLand, the authors propose routing flows randomly over the paths. Both of the papers examine three-stage topologies, both of which would support approximately the same number of end-hosts based on the number of ports each switch had; though the fat tree topology examined would use considerably more switches. To achieve similar performance VL2 assumes that switch-to-switch bandwidths are substantially higher than end-host-to-switch bandwidths. The fat tree topology is also considerably more regular, so where PortLand relies on location-specifying MAC addresses and explicit failure notifications the VL2 scheme runs a link state protocol between switches (but not to export end-host addresses) while .
• Layer choice — VL2 uses location-specifying IP addresses; providing a mapping from location-agnostic (relocatable) IP addresses to location-specific ones analagous to PortLand's AMAC to PMAC mapping. Unlike PortLand, using IP addresses combines two mappings (AMAC to PMAC and PMAC to IP) that PortLand maintained into one mapping that VL2 contains (AA to LA). The disadvantage, of course, is that servers need extra support to know this mapping (doing IP in IP encapsulation) rather than it being backwards-compatible as using the ARP cache is.
  
• The directory servers — in this paper, they are only responsible for the AA to LA mappings (no failure matrix), and replication/distribution of the directory servers is actually implemented. Also, the directory servers are queried by end-hosts rather than by switches;
  
• Autoconfiguration story — None seems apparent in this paper.
  
• Hardware required — The system in this paper runs on commodity switching ASICs, relying mostly on existing switch features rather than custom switching software.
  

The authors use some traces (presumably from MS data centers) and show that flow size varies a lot, traffic patterns are not very predictable, and small failures are frequent. They use these traces to motivate their choice of random load balancing rather than assuming a smarter scheme exists. For their prototype evaluation they measure utilization and fairness under an all-to-all TCP scenario on their 75-node testbed (apparently with near-commodity hardware) and measure interference between two services (with and without large numbers of TCP flows (‘mice’) in one service).

Probably the best feature of this paper is the authors extensive reuse of existing protocol implementations (OSPF, ECMP, etc.) This means that their fabric is probably more readily deployable and more hardware-agnostic than PortLand. It is also a disadvantage: they are not taking advantage of the relatively predictable topology they demand for routing, and many more pieces of hardware (each end-host) needs to be reconfigured than under the PortLand scheme which is truly invisible to the end-hosts.

PortLand

This paper describes a layer-2 switch fabric targeted at datacenters. Scalability and the obvious simple correctness goals apply (loop-free forwarding, fault-tolerance) as well as ease of configuration and allowing IP addresses to move around in the datacenter.
To make this task simpler (that is, with less per-switch state) the authors fix the datacenter's topology as a fat tree and designate a centralized ‘fabric manager’ (which must be replicated for fault tolerance, of course) which coordinates between switches.

As with SEATTLE, the switches in this scheme handle all ARP requests themselves in addition to managing routing.
Switch state is kept small by distributing ‘pseudo MAC’ addresses which encodes the position of the destination node in the topology; a host's actual MAC address is never distributed to other nodes. The fabric manager controls the IP to PMAC mapping, allowing switches to respond to ARP requests and generate gratuitous ARPs if a PMAC becomes invalid.

Forwarding is kept loop-free by assuming a rooted fat tree and by following the rule that a packet changes from going up toward the root to down toward a node exactly once. For load balancing, switches can choose freely between upstream ports (the authors suggest switching on flows to keep each flow single-path); for fault-tolerance, the fabric manager distributes failure information to affected switches who then update their routing tables accordingly.

Probably the most clever scheme here is switch autoconfiguration. Bottom level switches discover that they are connected to enough non-switches, and the level number of higher-level switches propagates up the fat-tree. Position number assignment is done in a greedy fashion, synchronized by a higher level switch.
Combined with failed link detection, this should make (re)configuration automatic except for the pesky issue of the fabric manager and communication with it.

The authors tested their system on a 16-host prototype, evaluating its response to failures, IP migration, and the overhead it imposed on the fabric manager. Failures resulted in approximately 100 milliseconds of disconnectivity (which was, of course, made worse by TCP timeouts), and for the VM migration scenario, the TCP flow stalls fails for periods of approx 200-600 ms. For the fabric manager, they evaluated the overhead of between 25 and 100 ARP misses/sec/host, asssumed scaling, and extrapolated the CPU and network bandwidth uses of the fabric manager, and found that the fabric manager would require a lot of CPU resources (70 cores for the 100 ARP/sec case with ~30k hosts).

These numbers are disappointing though the authors point out that these miss rates seem unrealistic and that the fabric manager could probably be distributed to a cluster. Since presumably the authors are pretty confident that ARP miss rates are considerably lower in a real data center, it is disappointing that they didn't try to measure or intelligently estimate the rate at which they would be expected to occur. The linear extrapolation is also disappointing — couldn't the authors have really run their fabric manager on a synthetic trace with these miss rates and host count and measured the CPU usage?

Detailed Diagnosis in Enterprise Networks

This paper describes a system (called NetMedic) for identifying the likely location of the root cause of faults from component state/performance traces. Machine-local information (such CPU and memory utilization) in addition to network information (such as traffic rates and response times) are collected and assigned to “components” which, in the paper's evaluation, correspond to entities such as machines, user processes, or the collective networking infrastructure.

Since the system does not assume any domain knowledge about the measurements it receives, faults are detected based on measurements deviating from their usual values. Diagnosis uses historical correlations to determine whether an anomalous measurement bis likely influencing/influenced by another. To determine which components' measurements to compare, domain knowledge is used: ‘template’ mark the dependencies each component type has to other components (e.g. between a machine and all of its processes or between processes communicating over IP). Given this directed dependency graph and the likelihood of measurements influencing each other, the ‘best’ cause is determined based on the best geometric means of influence scores on paths from the alleged cause to components, weighted by the destination components' abnormality, combined with this geometric mean for the component being diagnosed.

The authors include an evaluation where they analyze whether their system can diagnose injected faults causes correctly. They compare their approach to a simpler approach and a hand-tuned aporoach. Both share the dependency graph and root cause ranking method. The simpler method only measures whether components are ‘abnormal’ and computes influencing ranks based solely on whether both components are abnormal; the hand-tuned method only measures influence between variables hand-marked as related. The authors find that their system gave the correct cause as the first ranked cause for almost all the injected faults, and did so substantially better than the simple approach, which was successful about half of the time. The hand-tuned approach did not a substantial improvement, showing that the authors had not lost much but avoiding domain-specific knowledge in that part.

One troubling aspect of this work is formulas that seem to be chosen mostly arbitrarily (e.g. using geometric mean and sqrt(c->e value * global weighted value) for cause ranking; the choice of 0.1 and 0.8 has a ‘default’ edge weight; etc.) Of course, the authors had to make some choice here, but from the results we cannot tell how sensitive correct diagnosis is to these choices — is there technique actually general enough that they mostly don't matter? (The authors did do a sensitivity analysis for one of these parameters — the length of history used for diagnosis.)

There's also the big step away from fully domain-agnostic diagnosis in requiring templates. These templates are fortunately applicable to many kinds of applications, which is why, based on their motivation, they felt it okay to use them but not such similar input about the measurements they are taking. But these templates do not look entirely trivially to make: the ones they show have many subtle dependencies, such as on machine firewalls and other traffic. Are they actually easy to infer, and given that the authors have gone to great effort to develop a method for ignoring irrelevant correlations, how useful are they?