Multiple Granularity Online Control of Cloudlet Networks for Edge Computing
Multiple Granularity Online Control of Cloudlet Networks for Edge Computing
复制标题
DOI：
10.1109/sahcn.2018.8397141
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Lei Jiao;Lingjun Pu;L. Wang;Xiaojun Lin;Jun Yu Li
中科院分区：
文献类型：
--
作者：
Lei Jiao;Lingjun Pu;L. Wang;Xiaojun Lin;Jun Yu Li
在面对动态和不可预测的资源价格和用户请求，以及当今不成熟的云基础设施的低效率时，以最优成本运行分布式云是非常重要的。我们建议在多个粒度上控制cloudlet网络：细粒度控制cloudlet内部的服务器，粗粒度控制cloudlet本身。我们将此问题建模为一个混合整数非线性规划，并考虑切换代价随时间的变化。为了在线解决该问题，我们首先将其线性化，“正则化”并解耦为一系列一次性子问题，我们在每个相应的时隙求解，然后我们设计了一个迭代的，依赖的舍入框架，使用我们提出的随机两两舍入算法将分数控制决策转换为每个时隙的积分控制决策。通过严格的理论分析，我们从竞争比和乘法积分差两个方面证明了我们的方法对离线最优积分决策的性能保证。对真实世界数据的广泛评估证实了我们的方法优于单粒度服务器控制和最先进的算法。
Operating distributed cloudlets at optimal cost is nontrivial when facing not only the dynamic and unpredictable resource prices and user requests, but also the low efficiency of today's immature cloudlet infrastructures. We propose to control cloudlet networks at multiple granularities: fine-grained control of servers inside cloudlets and coarse-grained control of cloudlets themselves. We model this problem as a mixed-integer nonlinear program with the switching cost over time. To solve this problem online, we firstly linearize, "regularize", and decouple it into a series of one-shot subproblems that we solve at each corresponding time slot, and afterwards we design an iterative, dependent rounding framework using our proposed randomized pairwise rounding algorithm to convert the fractional control decisions into the integral ones at each time slot. Via rigorous theoretical analysis, we exhibit our approach's performance guarantee in terms of the competitive ratio and the multiplicative integrality gap towards the offline optimal integral decisions. Extensive evaluations with real-world data confirm the empirical superiority of our approach over the single granularity server control and the state-of-the-art algorithms.