Application-Aware Traffic Scheduling for Workload Offloading in Mobile Clouds
This research explores the challenges of cloud computing for mobile devices, specifically focusing on energy consumption and wireless transmission costs. It proposes a solution to adaptively balance the energy/delay tradeoff by considering application characteristics and runtime dynamics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Application-Aware Traffic Scheduling for Workload Offloading in Mobile Clouds Liang Tong, Wei Gao University of Tennessee Knoxville IEEE INFOCOM 2016 1
CloudComputing for mobile devices Contradiction between limited battery and complex mobile applications Mobile Cloud Computing (MCC) Offloading local computations to remote execution via wireless communication 2 IEEE INFOCOM 2016
CloudComputing for mobile devices Wireless communication is expensive! A 3G/4G, WiFi B Application process Partitioning workloads at the method level B Local execution > wireless data transmission How to measure the cost? 3 IEEE INFOCOM 2016
Cost of wireless transmission Energy consumption during wireless transmission Energy model of the UMTS cellular radio interface High power state Up to 10 seconds A large portion of wireless energy consumption happens during tail times! IEEE INFOCOM 2016 4
Existing solution Deferral and bundling Before Time deferral Only one tail left After Time bundling Tail Transmission 1 Transmission 2 The tail time phenomenon can be alleviated No! Good enough? 5 IEEE INFOCOM 2016
Why? Ignorance of mobile app characteristics interdependency & causality? Before Time delay constraint? Run-time dynamics? After Time Tail Transmission 1 Transmission 2 Application performance could be seriously degraded! 6 IEEE INFOCOM 2016
Our solution Key idea: Adaptively balancing the energy/delay tradeoff Taking both causality and run-time dynamics of application method executions into account Solutions Optimal scheduling Offline scheduling Causality Heuristic scheduling Online scheduling Run-time dynamics 7 IEEE INFOCOM 2016
System model Multiple applications are running concurrently. For application i: Delay constraint: ?? Execution path: ?1 Offloading decisions: existing work ?,?2 ?, ,??? ?. Mi Mi Local Method executions 4 1 Time Mi 2Mi Mi Remote 5 3 Data Time transmissions Ti Ti Ti 3 1 2 Causality 8 IEEE INFOCOM 2016
Challenge How to eliminate transmission overlaps? Ti Ti Ti 3 1 2 Time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 cascaded delay deferral d1 d1 d1 transmission overlap Time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Additional delay to eliminate overlaps. But how long? 9 IEEE INFOCOM 2016
Offline transmission scheduling Problem formulation ?? max ???? Total number of bundling ?=1 s.t. ?? ??+1, ???? = 0, 0 ?? ??, ? ?? , ?? N transmission causality overlap elimination delay constraint ??. Exponential time for exhaustive Solution space: ?? search! How to find optimal solution with a low complexity? 10 IEEE INFOCOM 2016
Optimal transmission scheduling (OTS) Basic idea Solve problems by combining the solutions to subproblems subproblem 1 subproblem 2 subproblem 3 Dynamic Programming BUNDLE(?, ?): subproblem with j transmissions and delay constraint k Guarantee of optimal solution BUNDLE(??,??) has an optimal substructure What are the optimal solutions for subproblems? 11 IEEE INFOCOM 2016
Optimal transmission scheduling (OTS) Optimal solutions of subproblems dp[?][?](? ?): the maximum number of bundles for a subproblem of ?1,?2 ,?? when ?? is delayed for ? ?1 ?2 ??= 4 Time 1 2 3 4 5 6 7 8 9 10 11 12 13 Subproblem {?1,?2} Subproblem {?1} dp[1][m] (m k) dp[2][k] (k 4) dp[1][k] (k 4) Causality Delay constraint Time complexity: ?(????2) 12 IEEE INFOCOM 2016
Improvement of Computational Efficiency Problem: large computational overhead of OTS Time complexity of OTS: ? ????2 ?? could be very large Solution: 2-stage transmission scheduling Eliminating transmission overlaps heuristically Stage 1: Posterior overlap elimination Stage 2: Prior overlap avoidance 13 IEEE INFOCOM 2016
Improvement of Computational Efficiency Posterior overlap elimination Iteratively looking for the maximally allowed transmission delay within the application delay constraint Eliminating the transmission overlap due to such delay in a posterior manner ?(??2) 14 IEEE INFOCOM 2016
Improvement of Computational Efficiency Prior overlap avoidance Iteratively looking for the minimum transmission delay Ensure that all possible overlaps could be avoided in a prior manner ?(??2) 15 IEEE INFOCOM 2016
Online transmission scheduling Prediction of application execution path Formulating method transitions as an order-k semi- Markov model Semi-markov: arbitrary sojourn times between method transitions Order-k: precise prediction of method Invocation (k-step interdependency) Method execution times Incorporation of run-time dynamics Predicting the number of future method invocations Predicting the execution time of method to be invoked in the future 16 IEEE INFOCOM 2016
Online transmission scheduling Probabilistic transmission scheduling A probabilistic framework to adaptively schedule each transmission Probabilistically estimate the cumulative transmission delay Predicted number of future executionPredicted execution time Cumulative deferral Cumulative Execution time 17 IEEE INFOCOM 2016
Performance evaluations Comparisons Bundle transmission: performance requirements and delay constraint are not considered. Fast dormancy: the mobile device switches to IDLE quickly after data transmission RSG: run-time causality and dynamics are ignored. Evaluation metrics Application completion ratio Amount of energy saved Computational overhead The percentage of the energy consumption of application executions 18 IEEE INFOCOM 2016
Evaluation setup Evaluation against open-source Android apps Firefox, Chess-Walk, Barcode Scanner. Implementing the transmission scheduling approach into app codes Offloading operations Adopt MAUI for workload offloading decisions Adopt CloneCloud to maintain a clone VM at the cloud server for each app Experiments 100 times with different input data for statistical convergence 19 IEEE INFOCOM 2016
Effectiveness of offline scheduling The optimal scheduling (baseline < 2.0) and 2- stage scheduling (baseline 2.0) are used Baseline: completion time of local application executions 40% more energy saved Less than 4% overhead 25% more completion ratio 20 IEEE INFOCOM 2016
Effectiveness of online scheduling An order-3 semi-Markov model is used Online transmission algorithm performs better Higher overhead is incurred 25% more energy saved more than 50% overhead 20% more completion ratio 21 IEEE INFOCOM 2016
Summary Mobile Cloud Computing is critical to Augment mobile devices local capabilities Energy saving MCC offloading energy efficiency is determined by wireless transmission scheduling Insight: exploiting run-time causality and dynamics is the key Offline algorithm with causality being considered Online algorithm incorporating with run-time dynamics 22 IEEE INFOCOM 2016
Thank you! Questions? The paper and slides are also available at: http://web.eecs.utk.edu/~weigao/ IEEE INFOCOM 2016 23
