An adaptive approach to indexing pervasive data

ABSTRACT

In a pervasive computing world data will be scattered among millions of devices and finding the right data will be a fundamental problem. Several proposed service discovery architectures can assist applications searching for data within local boundaries but there is currently no support for global access to data. We introduce an application-level protocol VIA* for building self-organizing, distributed, hierarchical data indices that adapt to dynamic query workloads. These indices efficiently route queries to relevant devices and reduce the overall workload of the system. Adapting to the query workload, VIA* uses a “query impedance” metric to approximate the optimal hierarchy for processing the expected query workload. Distributed, “logical” nodes in the interior of the hierarchy collect information about query impedance and forward this information to “data carrying” leaf nodes that react to improve the topology of the hierarchy. We present some findings from our workload testbed that demonstrate the performance and scalability characteristics of our approach and outline our research agenda

REFERENCES

• 1: William Adjie-Winoto , Elliot Schwartz , Hari Balakrishnan , Jeremy Lilley, The design and implementation of an intentional naming system, ACM SIGOPS Operating Systems Review, v.33 n.5, p.186-201, Dec. 1999
• 2: P. Castro and R. Muntz. Managing Context for Smart Spaces. IEEE Personal Communications, October, 2000.
• 3: Chatschik Bisdikian, Paul Castro, Ben Greenstein, Parviz Kermani, Richard Muntz, Maria Papadopouli. Sharing Appplication Data Across Service Discovery Domains. submitted for publication. January, 2001. (available at http://mmsl.cs.ucla.edu/~castrop/via-submitted.pdf)
• 4: Steven E. Czerwinski , Ben Y. Zhao , Todd D. Hodes , Anthony D. Joseph , Randy H. Katz, An architecture for a secure service discovery service, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.24-35, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313462]
• 5: JINI(tm) Connection Technology. http://www.sun.com/jini.
• 6: Jonathan Rosenberg, Erik Gutman, Ryan Moats, and Henning Schulzrinne. WASRV Architectural Principles. Internet Draft. Internet Engineering Task Force, Feb 1998. Work in progress.
• 7: The Open Source Gateway Initiative. http://www.ogsi.org.
• 8: The Salutation consortium. http://www.salutation.org.
• 9: Universal plug and play. http://www.upnp.org.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Performance, Theory

Keywords:
Pervasive computing, adaptive index, data dissemination