In this paper, we advocate edge caching in Cloud Radio Access Networks (C-RAN) to facilitate the ever-increasing mobile multimedia services. In our framework, central offices will cooperatively allocate cloud resources to cache popular contents and satisfy user requests for those contents, so as to minimize the system costs in terms of storage, VM reconfiguration, content access latency, and content migration. However, this joint resource allocation, content placement and request routing is nontrivial, since it needs to be continuously adjusted to accommodate system dynamics, such as user movement and content slashdot effect, while taking into account the time-correlated adjustment costs for VM reconfiguration and content migration. To this end, we build a comprehensive model to capture the key components of edge caching in C-RAN, and formulate a joint optimization problem, aiming at minimizing the system costs over time, and meanwhile satisfying the time-varying user requests and respecting various practical constraints (e.g., storage and bandwidth). Then, we propose a novel online approximation algorithm by resorting to the regularization, rounding and decomposition technique, which can be proved to have a parameterized competitive ratio with a polynomial running time. Extensive trace-driven simulations corroborate the efficiency, flexibility and lightweight of our proposed online algorithm, for instance it achieves an empirical competitive ratio around 2 – 4, gains over 30% improvement compared with many state-of-the-art algorithms in various system settings.

To better support emerging interactive mobile applications such as those VR-/AR-based, cloud computing is quickly evolving into a new computing paradigm called edge computing. Edge computing has the promise to bring cloud resources to the network edge to augment the capability of mobile devices in close proximity to the user. One big challenge in edge computing is the efficient allocation and adaptation of edge resources in the presence of high dynamics imposed by user mobility. This paper provides a formal study of this problem. By characterizing a variety of static and dynamic performance measures with a comprehensive cost model, we formulate the online edge resource allocation problem with a mixed nonlinear optimization problem. We propose MOERA, a mobility-agnostic online algorithm based on the "regularization" technique, which can be used to decompose the problem into separate subproblems with regularized objective functions and solve them using convex programming. Through rigorous analysis we are able to prove that MOERA can guarantee a parameterized competitive ratio, without requiring any a priori knowledge on input. We carry out extensive experiments with various real-world data and show that MOERA can achieve an empirical competitive ratio of less than 1.2, reduces the total cost by 4x compared to static approaches, and outperforms the online greedy one-shot solution by 70%. Moreover, we verify that even being future-agnostic, MOERA can achieve comparable performance to approaches with perfect partial future knowledge. We also discuss practical issues with respect to the implementation of our algorithm in real edge computing systems.

Deep neural networks (DNNs) have become a critical component for inference in modern mobile applications, but the efficient provisioning of DNNs is non-trivial. Existing mobile- and server-based approaches compromise either the inference accuracy or latency. Instead, a hybrid approach can reap the benefits of the two by splitting the DNN at an appropriate layer and running the two parts separately on the mobile and the server respectively. Nevertheless, the DNN throughput in the hybrid approach has not been carefully examined, which is particularly important for edge servers where limited compute resources are shared among multiple DNNs. This article presents HiTDL, a runtime framework for managing multiple DNNs provisioned following the hybrid approach at the edge. HiTDL's mission is to improve edge resource efficiency by optimizing the combined throughput of all co-located DNNs, while still guaranteeing their SLAs. To this end, HiTDL first builds comprehensive performance models for DNN inference latency and throughout with respect to multiple factors including resource availability, DNN partition plan, and cross-DNN interference. HiTDL then uses these models to generate a set of candidate partition plans with SLA guarantees for each DNN. Finally, HiTDL makes global throughput-optimal resource allocation decisions by selecting partition plans from the candidate set for each DNN via solving a fairness-aware multiple-choice knapsack problem. Experimental results based on a prototype implementation show that HiTDL improves the overall throughput of the edge by $4.3\times$ compared with the state-of-the-art.

The computing frontier is moving from centralized mega datacenters towards distributed cloudlets at the network edge. We argue that cloudlets are well-suited for handling power demand response to help the grid maintain stability due to more flexible workload management attributed to their distributed nature. However, they also require computing demand response to avoid overload and maintain reliability. To this end, we propose a novel online market mechanism, EdgeDR, to achieve cost efficiency in edge demand response programs. At a high level, we observe that the cloudlet operator can dynamically switch on/off entire cloudlets to compensate for the energy reduction required by the power grid or provide enough computing resources to the edge service. We formulate a long-term social cost minimization problem and decompose it into a series of one-round procurement auctions. In each auction instance, we propose to let the cloudlet tenants bid with cost functions of their two-dimension service quality degradation tolerance, and let the cloudlet operator choose the service quality, manage the workload, and schedule the cloudlet activation status. In addition, we present a dynamic payment mechanism for the operator to balance the tradeoff between short-term profit and long-term benefit in more practical scenarios. Via rigorous analysis, we exhibit that our bidding policy is individually rational and truthful; our workload management algorithm has near-optimal performance in each auction; and our overall online algorithm achieves a provable competitive ratio. We further confirm the performance of our mechanism through extensive trace-driven simulations.

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.

Deep neural networks (DNNs) have been widely adopted for various mobile inference tasks, yet their ever-increasing computational demands are hindering their deployment on resource-constrained mobile devices. Hybrid deep learning partitions a DNN into two parts and deploys them across the mobile device and a server, aiming to reduce inference latency or prolong battery life of mobile devices. However, such partitioning produces (non-uniform) DNN fragments which are hard to serve efficiently on the server. This article presents Graft—an efficient inference serving system for hybrid deep learning with latency service-level objective (SLO) guarantees. Our main insight is to mitigate the non-uniformity by a core concept called DNN re-alignment, allowing multiple heterogeneous DNN fragments to be restructured to share layers. To fully exploit the potential of DNN re-alignment, Graft employs fine-grained GPU resource sharing. Based on that, we propose efficient algorithms for merging, grouping, and re-aligning DNN fragments to maximize request batching opportunities, minimizing resource consumption while guaranteeing the inference latency SLO. We implement a Graft prototype and perform extensive experiments with five types of widely used DNNs and real-world network traces. Our results show that Graft improves resource efficiency by up to 70% compared with the state-of-the-art inference serving systems.