Online and offline algorithms for circuit switch scheduling

Abstract

Motivated by the use of high-speed circuit switches in large scale data centers, we consider the problem of {\em circuit switch scheduling}. In this problem, we are given demands between pairs of servers and the goal is to schedule at every time step a matching between the servers while maximizing the total satisfied demand over time. The crux of this scheduling problem is that once one shift from one matching to a different one a fixed delay $\delta$ is incurred during which no data can be transmitted. For the offline version of the problem, we present an almost (1- 1/e) approximation ratio. Since the natural linear programming relaxation for the problem has an unbounded integrality gap, we adopt a hybrid approach that combines the combinatorial greedy with randomized rounding of a different suitable linear program. For the online version of the problem, we present a (bi-criteria) ((e-1)/(2e-1)-epsilon)-competitive ratio (for any constant epsilon >0 ) that exceeds time by an additive factor of O(delta/epsilon). We note that no uni-criteria online algorithm is possible. Surprisingly, we obtain the result by reducing the online version to the offline one.