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

Presentation Outline

Research Background and Motivation

Centralized Solutions

Adaptive Algorithm

Non-adaptive Algorithm

Distributed Solution

Conclusions and Future Work

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

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.

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

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)

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))

Distributed Algorithm, cont.

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

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


	Yang Wang and Thomas Kunz
	University of Alberta Carleton University
	http://kunz-pc.sce.carleton.ca/
	tkunz@sce.carleton.ca


	Research Background and Motivation
	Centralized Solutions
		Adaptive Algorithm
		Non-adaptive Algorithm
	Distributed Solution
	Conclusions and Future Work


	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


	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.


	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


	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)


	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))


	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


	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