Journal
IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 29, Issue 1, Pages 34-47Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2020.3025985
Keywords
Collaboration; Synchronization; Edge computing; Optimized production technology; Cloud computing; Quality of service; Edge computing; service placement; performance optimization; approximation
Categories
Funding
- 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
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available