More Like this

1. LinkShare: Device-Centric Control for Concurrent and Continuous Mobile-Cloud Interactions

   https://doi.org/10.1145/3318216.3363303  

   Hu, Bo; Hu, Wenjun (November 2019, Symposium on Edge Computing)

   Mobile applications have become increasingly sophisticated. Emerging cognitive assistance applications can involve multiple computationally intensive modules working continuously and concurrently, further straining the already limited resources on these mobile devices. While computation offloading to the edge or the cloud is still the de facto solution, existing approaches are limited by intra-application operations only or edge-/cloud-centric scheduling. Instead, we argue that operating system level coordination is needed on the mobile side to adequately support the prospects of multi-application offloading. Specifically, both the local mobile system resource and the network bandwidth to reach the cloud need to be allocated intelligently among concurrent offloading jobs. In this paper, we build a system-level scheduler service, LinkShare, that wraps over the operating system scheduler to coordinate among multiple offloading requests. We further study the scheduling requirements and suitable metrics, and find that the most intuitive approaches of minimizing the end-to- end processing time or earliest-deadline first scheduling do not work well. Instead, LinkShare adopts earliest-deadline first with limited sharing (EDF-LS), that balances real-time requirements and fairness. Extensive evaluation of an Android implementation of LinkShare shows that adding this additional scheduler is essential, and that EDF-LS reduces the deadline miss events by up to 30% compared to the baseline. 

   more » « less
2. Distributed Threshold-based Offloading for Heterogeneous Mobile Edge Computing

   Qin, Xudong; Xie, Qiaomin; Li, Bin (July 2023, 2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS))

   In this paper, we consider a large-scale heterogeneous mobile edge computing system, where each device’s mean computing task arrival rate, mean service rate, mean energy consumption, and mean offloading latency are drawn from different bounded continuous probability distributions to reflect the diverse compute-intensive applications, mobile devices with different computing capabilities and battery efficiencies, and different types of wireless access networks (e.g., 4G/5G cellular networks, WiFi). We consider a class of distributed threshold-based randomized offloading policies and develop a threshold update algorithm based on its computational load, average offloading latency, average energy consumption, and edge server processing time, depending on the server utilization. We show that there always exists a unique Mean-Field Nash Equilibrium (MFNE) in the large-system limit when the task processing times of mobile devices follow an exponential distribution. This is achieved by carefully partitioning the space of mean arrival rates to account for the discrete structure of each device’s optimal threshold. Moreover, we show that our proposed threshold update algorithm converges to the MFNE. Finally, we perform simulations to corroborate our theoretical results and demonstrate that our proposed algorithm still performs well in more general setups based on the collected real-world data and outperforms the well-known probabilistic offloading policy. 

   more » « less
3. A Truthful Mechanism for Interval Scheduling

   https://doi.org/10.1007/978-3-319-99660-8_10  

   Garg, Jugal; McGlaughlin, Peter (September 2018, Lecture notes in computer science)

   Motivated by cloud computing, we study a market-based approach for job scheduling on multiple machines where users have hard deadlines and prefer earlier completion times. In our model, completing a job provides a benefit equal to its present value, i.e., the value discounted to the time when the job finishes. Users submit job requirements to the cloud provider who non-preemptively schedules jobs to maximize the social welfare, i.e., the sum of present values of completed jobs. Using a simple and fast greedy algorithm, we obtain a 1+s/(s−1) approximation to the optimal schedule, where s>1 is the minimum ratio of a job’s deadline to processing time. Building on our approximation algorithm, we construct a pricing rule to incentivize users to truthfully report all job requirements. 

   more » « less
4. Optimal Offloading for Dynamic Compute-Intensive Applications in Wireless Networks

   https://doi.org/10.1109/GLOBECOM38437.2019.9013327  

   Li, Bin (December 2019, 2019 IEEE Global Communications Conference (GLOBECOM))

   With the rapid growth of wireless compute-intensive services (such as image recognition, real-time language translation, or other artificial intelligence applications), efficient wireless algorithm design should not only address when and which users should transmit at each time instance (referred to as wireless scheduling) but also determine where the computation should be executed (referred to as offloading decision) with the goal of minimizing both computing latency and energy consumption. Despite the presence of a variety of earlier works on the efficient offloading design in wireless networks, to the best of our knowledge, there does not exist a work on the realistic user- level dynamic model, where each incoming user demands a heavy computation and leaves the system once its computing request is completed. To this end, we formulate a problem of an optimal offloading design in the presence of dynamic compute-intensive applications in wireless networks. Then, we show that there exists a fundamental logarithmic energy- workload tradeoff for any feasible offloading algorithm, and develop an optimal threshold-based offloading algorithm that achieves this fundamental logarithmic bound. 

   more » « less
5. Optimal Offloading for Dynamic Compute-Intensive Applications in Wireless Networks

   Li, Bin (December 2019, IEEE Conference on Global Communications Conference (GLOBECOM))

   With the rapid growth of wireless compute-intensive services (such as image recognition, real-time language translation, or other artificial intelligence applications), efficient wireless algorithm design should not only address when and which users should transmit at each time instance (referred to as wireless scheduling) but also determine where the computation should be executed (referred to as offloading decision) with the goal of minimizing both computing latency and energy consumption. Despite the presence of a variety of earlier works on the efficient offloading design in wireless networks, to the best of our knowledge, there does not exist a work on the realistic user-level dynamic model, where each incoming user demands a heavy computation and leaves the system once its computing request is completed. To this end, we formulate a problem of an optimal offloading design in the presence of dynamic compute-intensive applications in wireless networks. Then, we show that there exists a fundamental logarithmic energy-workload tradeoff for any feasible offloading algorithm, and develop an optimal threshold-based offloading algorithm that achieves this fundamental logarithmic bound. 

   more » « less