  To reduce cost, datacenter network operators are exploring blocking network
designs. An example of such a design is a "spine-free" form of a Fat-Tree, in
which pods directly connect to each other, rather than via spine blocks. To
maintain application-perceived performance in the face of dynamic workloads,
these new designs must be able to reconfigure routing and the inter-pod
topology. Gemini is a system designed to achieve these goals on commodity
hardware while reconfiguring the network infrequently, rendering these blocking
designs practical enough for deployment in the near future. The key to Gemini
is the joint optimization of topology and routing, using as input a robust
estimation of future traffic derived from multiple historical traffic matrices.
Gemini "hedges" against unpredicted bursts, by spreading these bursts across
multiple paths, to minimize packet loss in exchange for a small increase in
path lengths. It incorporates a robust decision algorithm to determine when to
reconfigure, and whether to use hedging. Data from tens of production fabrics
allows us to categorize these as either low-or high-volatility; these
categories seem stable. For the former, Gemini finds topologies and routing
with near-optimal performance and cost. For the latter, Gemini's use of
multi-traffic-matrix optimization and hedging avoids the need for frequent
topology reconfiguration, with only marginal increases in path length. As a
result, Gemini can support existing workloads on these production fabrics using
a spine-free topology that is half the cost of the existing topology on these
fabrics.
