Georgia Institute of Technology
Online and offline algorithms for circuit switch scheduling
Abstract
dc:description.abstractMotivated 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 δ 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.
Degree
thesis:*- Level thesis:degree_level
- Masters
- Department dc:contributor.department
- Computer Science
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2020
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Yazdanbod, Sina
- Advisor dc:contributor.advisor
-
- Singh, Mohit
- Committee members dc:contributor.committeemember
-
- Xu, Jun (Jim)
- Maguluri, Siva T.
Subjects
dc:subject × 4Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/63589