TCP was conceived to ensure reliable node-to-node communication in moderate-bandwidth, moderate-latency, WANs. As it is now a mature Internet standard, it is the default connection-oriented protocol in networks built from commodity components, including Internet data centers. Data centers, however, rely on high-bandwidth, low-latency networks for communication. Moreover, their communication patterns, especially those generated by distributed applications such as MapReduce, often take the form of synchronous multi-node to node bursts. Under the right conditions, the network switch buffer overflow losses induced by these bursts confuse TCP's feedback mechanisms to the point that TCP throughput collapses. This collapse, termed TCP Incast, results in gross underutilization of link capacities, significantly degrading application performance.
Conventional approaches to mitigating Incast have focused on single-path solutions, for instance, adjusting TCP's receive windows and timers, modifying the protocol itself, or adopting explicit congestion notifications. This thesis explores complementary multi-path approaches to avoiding Incast's onset. The principal idea is to use the regularity and high connectivity of typical data center networks, such as the increasingly popular fat-tree topology, to better distribute multi-node to node bursts across the available paths, thereby avoiding the switch buffer overflows that induce TCP Incast.
The thesis's main contributions are: (1) development of new oblivious, multi-path, routing schemes for fat-tree networks, (2) derivation of relations between the schemes and Incast's onset, and (3) investigation of a novel "front-back" approach to minimizing the packet reordering introduced by multipath routing. Formal analyses are focused on relating schemes' worst-case loading of certain network resources - expressed as oblivious performance ratios (OPRs) - to Incast's onset. Potential benefits are assessed through ns-3 simulations on fat-trees under a variety of communication patterns. Results indicate that over a variety of experimental conditions, the proposed schemes reduce the incidence of TCP Incast compared to standard routing schemes.