Nikolai Samteladze
Summary:
We use delta encoding algorithms to reduce the size of Android app updates. We implement delta encoding for Android using the bsdiff and bspatch tools. Server software and an Android app have been developed. Currently, we are able to achieve 50% reduction in size for Android updates. If widely deployed, this has the potential to significantly reduce data traffic in cellular networks.

Update Mechanism:
We propose to use delta encoded patches to update Android applications. The new application update mechanism can be described as follows:
  1. Compute a patch on the server.
  2. Download the patch to the smart phone.
  3. Obtain a new version of the installed app by applying the downloaded patch on the smart phone.
  4. Install the new version of application and then delete the old version and the patch used.

Statistics Collection:
We are currently conducting a study to understand how applications are updated in Android. The results of this research will allow us to precisely estimate saving in traffic and money that can be achieved by using the proposed application update mechanism. We created an Android application that collects the required statistics which will be further used in out research. The following statistics is collected:
  1. Application's name, version, size and time of the last update for each of the installed applications.
  2. Wi-Fi and Mobile networks connectivity statistics. That means whether the device is connected to any of Wi-Fi or Mobile (3G/4G) networks.

Papers and Presentations:
Preliminary results were summarized in this paper that will be presented at the LCN 2012 conference.

Google Smart Updates Technology:
At Google I/O 2012 in July 2012 Google announced (video available here) Smart Updates technology for Google Play Store. It started to work in the mid August as was reported by Android Police. They use the same approach as we proposed in our application update mechanism. Delta difference between two application's version is computed as sent to the end device where it is deployed (installed application is patched).

According to our measurements, average patch size (delta difference size) for popular applications is 34%. This correlates with the information announced at Google I/O 2012 (Google announced approximately 33% patch size for the most popular applications).

Software:
To implement the proposed approach we created both server software to compute delta patches and a smart phone application to deploy the received patches and update the installed applications. To compute delta difference on the server we used BSDiff tool created by Colin Percival. To patch the installed application on Android device we ported BSPatch tool's (also created by Colin Percival) code to Android. Also we created several tools to collect the required statistics from the end devices and automate some research tasks.