4.5 Article

Service Placement for Collaborative Edge Applications

Journal

IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 29, Issue 1, Pages 34-47

Publisher

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

Funding

  1. German Research Foundation (DFG)
  2. National Nature Science Foundation of China (NSFC) Joint Project [392046569, 61761136014]
  3. DFG Collaborative Research Center (CRC)-MAKI [1053]
  4. Ripple Faculty Fellowship
  5. U.S. Army Research Laboratory
  6. U.K., Ministry of Defense [W911NF-16-3-0001]
  7. National Science Foundation [1564348]
  8. Division Of Computer and Network Systems
  9. 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

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available