Optimizing in the Dark: Learning Optimal Network Resource Reservation Through a Simple Request Interface
Optimizing in the Dark: Learning Optimal Network Resource Reservation Through a Simple Request Interface
复制标题
DOI：
10.1109/tnet.2020.3045595
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Qiao Xiang;Haitao Yu;J. Aspnes;Franck Le;C. Guok;L. Kong;Y. Yang
中科院分区：
文献类型：
--
作者：
Qiao Xiang;Haitao Yu;J. Aspnes;Franck Le;C. Guok;L. Kong;Y. Yang
在为现代分布式应用提供性能可预测性的需求和实质性好处的推动下，网络资源预留系统正在被开发和部署。然而，现有系统存在局限性：它们要么在寻找最佳资源预留方面效率低下，要么导致(例如，来自网络基础设施的)私有信息暴露(例如，向用户)。在本文中，我们设计了一个新颖的系统BoxOpt，它利用优化和学习理论中的高效Oracle构建技术，在网络和用户之间不交换任何私人信息的情况下，自动、快速地学习最优的资源预留。在BoxOpt中，我们首先将大多数预订系统中采用的简单预订接口建模为资源成员关系预言。其次，我们开发了一种高效的算法，通过对资源成员关系预言器的线性调用来构造资源分离预言器。第三，提出了一种通过迭代调用资源分离预言机来构造资源优化预言机的通用框架，并在该通用框架下开发了三种新颖高效的算法，其中最好的算法是通过对资源分离预言机的线性调用来计算最优资源预留。因此，BoxOpt可以通过对资源成员资格预言进行$O(n^{2})$调用来发现最优的资源预留。我们实现了一个BoxOpt的原型，并通过使用真实的网络拓扑和一个大型运行的联邦网络的7天跟踪的广泛实验来证明其效率和有效性。结果表明：(1)BoxOpt与最先进的优化求解器相比具有100%的正确率；(2)对于90%的请求，BoxOpt在10秒内学习到最优资源预留。
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. In BoxOpt, we first model the simple reservation interface adopted in most reservation systems as a resource membership oracle. Second, we develop an efficient algorithm that constructs a resource separation oracle by a linear number of calls on resource membership oracle. Third, we develop a generic framework to construct a resource optimization oracle by iteratively calling the resource separation oracle, and then develop three novel, efficient algorithms under this generic framework, the best of which computes the optimal resource reservation by a linear number of calls on resource separation oracle. As such, BoxOpt can discover the optimal resource reservation with $O(n^{2})$ calls on the resource membership oracle. We implement a prototype of BoxOpt with and demonstrate its efficiency and efficacy via extensive experiments using real network topology and a 7-day trace from a large operational federation network. Results show that (1) BoxOpt has a 100% correctness ratio by comparing with a state-of-the-art optimization solver, and (2) for 90% of requests, BoxOpt learns the optimal resource reservation within 10 seconds.