期刊
出版社
IEEE
DOI: 10.1109/IPDPS47924.2020.00038
关键词
-
资金
- National Key RAMP
- D Program of China [2018YFB1800801]
- National Postdoctoral Program for Innovative Talents of China [BX20190202]
- China NSF [61702525, 61931011, 61872178, 61972252, 61972254, 61672348, 61672353]
- Joint Scientific Research Foundation of the State Education Ministry [6141A02033702]
- Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing [2018A09]
- Natural Science Foundation of Jiangsu Province [BK20181251]
- Alibaba Group through Alibaba Innovation Research Program
In this work, we study the problem of Robust Server Placement (RSP) for edge computing, i.e., in the presence of uncertain edge server failures, how to determine a server placement strategy to maximize the expected overall workload that can be served by edge servers. We mathematically formulate the RSP problem in the form of robust max-min optimization, derived from two consequentially equivalent transformations of the problem that does not consider robustness and followed by a robust conversion. RSP is challenging to solve, because the explicit expression of the objective function in RSP is hard to obtain, and RSP is a robust max-min problem with a matroid constraint and a knapsack constraint, which is still an unexplored problem in the literature. To address the above challenges, we first investigate the special properties of the problem, and reveal that the objective function is monotone submodular. We then prove that the involved constraints form a p-independence system constraint, where p is a constant value related to the ratio of the coefficients in the knapsack constraint. Finally, we propose an algorithm that achieves a provable constant approximation ratio in polynomial time. Both synthetic and trace-driven simulation results show that, given any maximum number of server failures, our proposed algorithm outperforms three state-of-the-art algorithms and approaches the optimal solution, which applies exhaustive exponential searches.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据