• Paper review: Adaptive Offloading for Pervasive Computing

    My friend Marcus recently suggested a good idea to keep track of papers that we read by writing a publicly available review about the work. So here's the first in a series of such posts.

    Title: Adaptive Offloading for Pervasive Computing

    Authors: Xiaohui Gu and Klara Nahrstedt (UIUC), Alan Messer, Ira Greenberg, and Dejan Milojicic (HP Labs)

    Motivation: Certain applications have high memory requirements, and thus cannot be easily run on resource constrained devices like mobile devices which are an essential component of pervasive computing environments. In lieu of such constraints, the authors propose a scheme wherein the deployment of such applications on mobile devices is made possible by "offloading" objects in the code (the paper assumes an object oriented language like Java or C#) onto a network-nearby device, hereafter referred to as the surrogate. This needs to be achieved by keeping the application completely oblivious to what's happening underneath. The problem: when to trigger an offload, and which objects to offload. Assumptions in the paper: Object oriented languages need to be used. High speed wireless link required. Summary: The core of the work involves describing each Java program as a graph of classes called the Application Execution Graph (AEG). Classes are chosen as the basic unit for representing an application because: 1) Classes map directly to interactions in the system, 2) classes allow more precise/fine-grained decision making for the offloading process (while this line isn't explained clearly, I believe it has to do with the next point) 3) The said interactions are easier to represent with classes than with several thousand Java objects. The graph of classes is to be partitioned into two chunks, one of which will remain on the device, and will be locally referenced, whereas the remaining chunk will be offloaded onto another device called the surrogate, usually a desktop or some non-resource-constrained device. Objects on the surrogate will be referenced using remote object invocations. This partitioning will be transparent to the application itself. This means that the Java application would be completely oblivious to the physical locations of the objects that it's dealing with, but the underlying VM will perform this partitioning, and will use local or remote invocations as would be the case. The VM used for the work was HP's Chai JVM. The AEG has weights for the nodes, and the edges. Weights are assigned to the nodes based on the access frequency of the class, the memory size of an instance of the class, the current location of the object, and whether the object _has_ to be on the device (device specific classes like a touchscreen reader for instance, which make no sense on the surrogate). The last property is called the IsNative property. The partitioning of the AEG is performed using a min cut algorithm, using the weights described above as a parameter for deciding the cut itself. Since determining the min-cut of a graph is an NP-Complete problem, the algorithm produces several possible min cut partitions, and maintains a set of such partitions. In run-time, one of these partitions is picked, depending on what is felt to be most optimal, given the particulars of the constraints in that scenario. All classes which have the IsNative property set to true, are bound to the device and will _not_ be offloaded to the surrogate. The architecture of the proposed solution is decomposed into a form wherein resource constraints are expressed using Fuzzy Logic. The fuzzy values like "low" and "high" depend on the application itself. Each application can have its own rules for the partitioning of the AEG. Depending on the rules and the current status of resource availability (like bandwidth and memory), we can pick the appropriate partition of the AEG that was generated in the step above. The partitioning is performed in a timely manner such that this computation needn't be performed when an offload has to be initiated, and we already have a partition available when we hit the resource limit. The solution was evaluated in a real setting (for a change!) and tools like Dia, Biomer and Java Notes was run. I won't be elaborating much on the evaluation itself, as it is clearly explained in the paper. I don't consider it very strong, as it does not explore cases where bandwidth was constrained, but it's still better than some other evaluations out there. Weaknesses in the work: Surrogates cannot be migrated on the fly, and this restricts how _far_ the mobile client can stray away from the surrogate. Furthermore, hacking the VM to achieve this may impact portability of the code, but this is much better than having to re-write applications.
  • NSoC student application deadline is nearby!

    The NS-3 Summer of Code programme has received a good deal of interest from students so far, and I'm pretty excited to see what the final set of applications will look like. Anyhow, hurry up students, the deadline for NSoC is on the 15th of April, 2011 at 19:00 UTC! Visit the NSoC wiki to find information regarding the applying process. Meanwhile, we recommend that you discuss your proposals as much as possible on the ns-developers mailing list and with your potential mentors before you apply to keep your proposal focused and polished.
  • Life is good

    Last week's Barcelona trip was the perfect weekend getaway from a hectic masters programme. After a not-so-enjoyable stint with changing hostels on Thursday, I met my colleagues from UPC, Barcelona for a nice round of drinks and tapas. I left for the Melia Barcelona early next day for WNS3 2011, and I was obviously excited about meeting the rest of the ns-3 developers for the first time. It's been more than a year of my involvement with the project, and so far it's been an amazing experience to work with the really awesome people that comprise of the ns-3 community. So meeting the faces behind the names from the mailing list was something I was looking forward to, and I did. A lot of hand shakes and introductions later, we got started with the programme. My talk went pretty well too. After the talks, we  had a pre-meeting for next day's ns-3 developers meeting in order to decide the agenda, the priorities, and the action items we planned to walk away with (note that beer is part of the schedule :) ). The day ended with an amazing dinner at a rather classy restaurant in the city. The developers meeting took place at the CTTC demo center on Saturday and lasted around 7 hours in total including lunch, during which we discussed and planned ahead as far as solving a number of issues was concerned. We also came to a consensus on organising an NS-3 Summer of Code programme, for which I'll be handling the reigns. All in all, it was an awesome experience to meet these guys, from whom I've been learning a lot over the past year. :) So in short, life is good. :)
  • GSoC 2011 results

    Unfortunately, ns-3 wasn't selected as a mentoring organisation for GSoC 2011. But don't worry, it doesn't end with that. We are keen on self organising a summer of code programme of our own, so that we can support some student projects and offer mentoring for the same over the summer. While we haven't decided on the exact plan yet, it is on our agenda for next week's ns-3 developers' meeting at Barcelona, co-located with Simutools 2011 and WNS3 2011. So stay tuned for updates from our end. If you have any ideas, suggestions or expectations from such a programme, feel free to get in touch with me and let me know what you think.
  • NS-3 Click Integration merged!

    As the title suggests, ns-3-click is finally in. So go ahead, clone ns-3-dev, and test all your Click graphs today! And as always, patches and improvements are welcome. :)