Service Placement for Collaborative Edge Applications

Lin Wang*, Lei Jiao, Ting He, Jun Li, Henri Bal

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


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.

Original languageEnglish
Article number9212591
Pages (from-to)34-47
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number1
Early online date5 Oct 2020
Publication statusPublished - Feb 2021

Bibliographical note

Funding Information:
Manuscript received March 6, 2020; revised July 23, 2020; accepted August 31, 2020; approved by IEEE/ACM TRANSACTIONS ON NETWORK-ING Editor C. Joo. Date of publication October 5, 2020; date of current version February 17, 2021. This work was supported in part by the German Research Foundation (DFG) and the National Nature Science Foundation of China (NSFC) Joint Project under Grant 392046569 (DFG) and Grant 61761136014 (NSFC), and in part by the DFG Collaborative Research Center (CRC)–MAKI under Grant 1053. The work of Lei Jiao was supported by the Ripple Faculty Fellowship. The work of Ting He was supported in part by the U.S. Army Research Laboratory and in part by the U.K., Ministry of Defense under Grant W911NF-16-3-0001. The work of Jun Li was supported by the National Science Foundation under Grant 1564348. A preliminary version of this article appeared at IEEE INFOCOM 2018. (Corresponding author: Lin Wang.) Lin Wang is with the Department of Computer Science, VU Amsterdam, 1081 HV Amsterdam, The Netherlands, and also with the Department of Computer Science, TU Darmstadt, 64289 Darmstadt, Germany (e-mail:

Publisher Copyright:
© 1993-2012 IEEE.

Copyright 2021 Elsevier B.V., All rights reserved.


  • approximation
  • Edge computing
  • performance optimization
  • service placement


Dive into the research topics of 'Service Placement for Collaborative Edge Applications'. Together they form a unique fingerprint.

Cite this