期刊
IEEE-ACM TRANSACTIONS ON NETWORKING
卷 29, 期 1, 页码 34-47出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2020.3025985
关键词
Collaboration; Synchronization; Edge computing; Optimized production technology; Cloud computing; Quality of service; Edge computing; service placement; performance optimization; approximation
类别
资金
- German Research Foundation (DFG)
- National Nature Science Foundation of China (NSFC) Joint Project [392046569, 61761136014]
- DFG Collaborative Research Center (CRC)-MAKI [1053]
- Ripple Faculty Fellowship
- U.S. Army Research Laboratory
- U.K., Ministry of Defense [W911NF-16-3-0001]
- National Science Foundation [1564348]
- Division Of Computer and Network Systems
- Direct For Computer & Info Scie & Enginr [1564348] Funding Source: National Science Foundation
This paper proposes an iterative algorithm ITEM and an online algorithm OPTS for deploying collaborative edge applications to achieve the best overall system performance, with a parameterized constant approximation ratio and stable performance; experiments show that ITEM performs close to the optimum and converges fast, while OPTS reduces full updates by more than 67% of the time.
Edge computing is emerging as a promising computing paradigm for supporting next-generation applications that rely on low-latency network connections in the Internet-of-Things (IoT) era. Many edge applications, such as multi-player augmented reality (AR) gaming and federated machine learning, require that distributed clients work collaboratively for a common goal through message exchanges. Given an edge network, it is an open problem how to deploy such collaborative edge applications to achieve the best overall system performance. This paper presents a formal study of this problem. We first provide a mix of cost models to capture the system. Based on a thorough formulation, we propose an iterative algorithm dubbed ITEM, where in each iteration, we construct a graph to encode all the costs and convert the cost optimization problem into a graph cut problem. By obtaining the minimum s - t cut via existing max-flow algorithms, we address the original problem via solving a series of graph cuts. We rigorously prove that ITEM has a parameterized constant approximation ratio. Inspired by the optimal stopping theory, we further design an online algorithm called OPTS, based on optimally alternating between partial and full placement updates. Our evaluations with real-world data traces demonstrate that ITEM performs close to the optimum (within 5%) and converges fast. OPTS achieves a bounded performance as expected while reducing full updates by more than 67% of the time.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据