  Oblivious routing has a long history in both the theory and practice of
networking. In this work we initiate the formal study of oblivious routing in
the context of reconfigurable networks, a new architecture that has recently
come to the fore in datacenter networking. These networks allow a rapidly
changing bounded-degree pattern of interconnections between nodes, but the
network topology and the selection of routing paths must both be oblivious to
the traffic demand matrix. Our focus is on the trade-off between maximizing
throughput and minimizing latency in these networks. For every constant
throughput rate, we characterize (up to a constant factor) the minimum latency
achievable by an oblivious reconfigurable network design that satisfies the
given throughput guarantee. The trade-off between these two objectives turns
out to be surprisingly subtle: the curve depicting it has an unexpected
scalloped shape reflecting the fact that load-balancing becomes more difficult
when the average length of routing paths is not an integer because equalizing
all the path lengths is not possible. The proof of our lower bound uses LP
duality to verify that Valiant load balancing is the most efficient oblivious
routing scheme when used in combination with an optimally-designed
reconfigurable network topology. The proof of our upper bound uses an algebraic
construction in which the network nodes are identified with vectors over a
finite field, the network topology is described by either the elementary basis
or a sequence of Vandermonde matrices, and routing paths are constructed by
selecting columns of these matrices to yield the appropriate mixture of path
lengths within the shortest possible time interval.
