1	A Dynamic Assignment Problem in a Mobile System with Limited Bandwidth Yang Wang and Thomas Kunz University of Alberta Carleton University http://kunz-pc.sce.carleton.ca/ tkunz@sce.carleton.ca
2	Presentation Outline Research Background and Motivation Centralized Solutions Adaptive Algorithm Non-adaptive Algorithm Distributed Solution Conclusions and Future Work
3	Mobile Computing Challenges
4	Adaptive Mobile Applications: System Overview
5	Proposed Architecture
6	Research Challenges Overall question: how to “best” split the client application between client device and proxy (i.e., the assignment problem) Not all objects are migratable (user interface, etc.) Runtime migration interferes with execution, so limit maximum amount of data to be migrated (i.e., object code and state) Stone’s network flow solution for 2-processor case not applicable Does not consider mobile environment constraints Requires object location to be chosen freely Paper shows that assignment problem is NP-complete by reducing it to the 0/1 Knapsack problem
7	Adaptive Algorithm Initially all objects are on client side. Each object is assigned a value D that characterizes how well it is suited to be migrated (benefits from being assigned to a faster CPU, linkages – method invocations – with other objects) Threshold value t determines which objects should be migrated (all objects for which D > t), initially the average of all D Adaptive Algorithm: after making migration decision, adapt threshold to reflect object migration (essentially by excluding migrated object.
8	Adaptive Algorithm, cont. Time complexity: O(ne) Example: Nodes have computational cost and size, edges have communication costs Proxy Processor 100 times faster than client device Wireless link capacity: 16 Initial node: 1 (highest D) Result: migrate 1, 2, 4, 5 for a benefit of 605
9	Non-adaptive Algorithm Adaptive Algorithm: essentially breadth-first search, nodes re-visited multiple times with different thresholds Non-adaptive algorithm: recursive, assumes that threshold is set once, n times faster than Adaptive Algorithm (i.e., O(e)) Applied to same example: migrate nodes 1, 2, 6, 3, for a benefit of 518 (i.e., less optimal)
10	Distributed Algorithm Both Adaptive and Non-adaptive Algorithms are centralized. If migration can extend to multiple proxies, centralized solution not ideal Distributed version: implement decision algorithm in proxy objects (i.e., the stubs that provide location transparency when invoking methods) and run in a coordinated but distributed fashion Basic idea: pass token in a tree structure, based on well-known algorithm, node/proxy object with token uses information to make migration decision Message complexity: O(n²log(n))
11	Distributed Algorithm, cont.
12	Conclusions Dynamically assign application objects to mobile device and proxy server, subject to: Computational demand of objects Object size (code and state) Inter-object relationships Optimal solution NP-hard Proposed three heuristics Centralized algorithms Distributed algorithm Algorithms proven to terminate, with known time or message complexities
13	Future Work Implement these algorithms in our mobile code toolkits for PalmPilot and Windows CE/Pocket PC devices Explore link between capacity limitation and wireless link capacity (i.e., the nature of the intrusion) If mobile environment changes, do we need to re-run algorithms from scratch or can we incrementally figure out new assignments