Back to search

Georgia Institute of Technology

Online and offline algorithms for circuit switch scheduling

Abstract

dc:description.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 δ 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 × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/63589

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Yazdanbod, Sina. Online and offline algorithms for circuit switch scheduling. Masters thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/63589