This post is an extract of the article “Automated Selection of Offloadable Tasks for Mobile Computation Offloading in Edge Computing”, presented at Conference on Network and Service Management (CNSM), 2017, Tokyo (Japan).

Please check also the post ULOOF (User Level Online Offloading Framework) for automated optimizations of Android application for initial insights of the Uloof project.

In computation offloading, one of the main related technical challenges is how to automatically partition an application code into offloadable and non-offloadable parts, for arbitrary applications by learning application code architecture. Performing this partitioning manually requires significant human effort: portions of Android applications (tasks) may be unsuitable for offloading due to several non-trivial motivations, such as frequent interaction with mobile users, difficulties in replicating device-specific resource instances at cloud/edge nodes, impossibility to serialize used resources, only to mention a few. Moreover, this required human effort slows down the acceptance of mobile offloading techniques in industrial scenarios for obvious cost motivations.

Within the ULOOf project, a general-purpose task selection algorithm has been developed and is able to detect offloadable parts of tasks from the entire mobile application code without prior knowledge of the analyzed application. In particular, the autonomous selection algorithm is applied on the original Android APK file and starts by scanning the whole application structure, applying incremental checks on each single class/method and dependency constraints between classes/methods.

Check phases

The classes and methods code is analyzed by Soot tool, a framework for analyzing and transforming Android applications.

On each methods, several iterative analysis are performed (e.g. OS dependencies, input/output dependencies, internal dependencies, etc.) and, in addition, dependency check to discard the methods having at least one dependency with a method marked as non-offloadable. This task can be very time-consuming, with a complexity of Θ(n^2*log n), where n is the total number of methods, which makes it not usable for a typical application with more than 100.000 methods.

Thus, a directed graph has been designed, where each node is a method and each edge is a method call, and starting from the root of the graph every non-offloadable methods found allows to cut the whole branch of the graph where the node is the local root. In this way, the complexity is Θ(n), where n is the number of non-offloadable methods that is much less than the total number of methods.

The methods suitable to be executed on the remote server will be instrumented and will generate a modified APK file which will be installed on the user mobile device. The instrumentation is performed with Soot which translate the method code into the Jimple pseudo/code an intermediate representation of Java code designed to be easier to manage than Java bytecode.

The method instrumentation allow to insert the code into the method body in order to receive the status of the current status of the application and be able to execute the method on the server when the required.

The whole process is included into the ULOOF framework, whose complete code is accessible at ULOOf on GitHub, where it is possible to retrieve more practical information and a step by step explanation about how to getting started with ULOOF.