Robust resource provisioning in time-varying edge networks

Ruozhou Yu, Guoliang Xue, Yinxin Wan, Jian Tang, Dejun Yang, Yusheng Ji

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Edge computing is one of the revolutionary technologies that enable high-performance and low-latency modern applications, such as smart cities, connected vehicles, etc. Yet its adoption has been limited by factors including high cost of edge resources, heterogeneous and fluctuating demands, and lack of reliability. In this paper, we study resource provisioning in edge computing, taking into account these different factors. First, based on observations from real demand traces, we propose a time-varying stochastic model to capture the time-dependent and uncertain demand and network dynamics in an edge network. We then apply a novel robustness model that accounts for both expected and worst-case performance of a service. Based on these models, we formulate edge provisioning as a multi-stage stochastic optimization problem. The problem is NP-hard even in the deterministic case. Leveraging the multi-stage structure, we apply nested Benders decomposition to solve the problem. We also describe several efficiency enhancement techniques, including a novel technique for quickly solving the large number of decomposed subproblems. Finally, we present results from real dataset-based simulations, which demonstrate the advantages of the proposed models, algorithm and techniques.

Original languageEnglish (US)
Title of host publicationMobiHoc 2020 - Proceedings of the 2020 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
PublisherAssociation for Computing Machinery
Pages21-30
Number of pages10
ISBN (Electronic)9781450380157
DOIs
StatePublished - Oct 11 2020
Event21st ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2020 - Virtual, Online, United States
Duration: Oct 11 2020Oct 14 2020

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

Conference

Conference21st ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2020
Country/TerritoryUnited States
CityVirtual, Online
Period10/11/2010/14/20

Keywords

  • edge computing
  • multi-stage stochastic optimization
  • resource allocation
  • robustness
  • time-varying

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'Robust resource provisioning in time-varying edge networks'. Together they form a unique fingerprint.

Cite this