Optimizing in the Dark: Learning an Optimal Solution through a Simple Request Interface

  • Qiao Xiang Yale University
  • Haitao Yu Tongji University
  • James Aspnes Yale University
  • Franck Le IBM T.J. Watson Research Center
  • Linghe Kong Shanghai Jiao Tong University
  • Y. Richard Yang Yale University

Abstract

Network resource reservation systems are being developed and deployed, driven by the demand and substantial benefits of providing performance predictability for modern distributed applications. However, existing systems suffer limitations: They either are inefficient in finding the optimal resource reservation, or cause private information (e.g., from the network infrastructure) to be exposed (e.g., to the user). In this paper, we design BoxOpt, a novel system that leverages efficient oracle construction techniques in optimization and learning theory to automatically, and swiftly learn the optimal resource reservations without exchanging any private information between the network and the user. We implement a prototype of BoxOpt and demonstrate its efficiency and efficacy via extensive experiments using real network topology and trace. Results show that (1) BoxOpt has a 100% correctness ratio, and (2) for 95% of requests, BoxOpt learns the optimal resource reservation within 13 seconds.

Published
2019-07-17
Section
AAAI Technical Track: Constraint Satisfaction and Optimization