Efficient Distributed Location Management For Mobile Computing Systems

Dr. Ravi Prakash
Computer Science Department
University of Rochester

Friday, February 28, 1997
11 a.m. - 12 noon
Fuller Labs 320

Location management is a fundamental problem in mobile computing systems. Existing industry standards employ centralized location management schemes. Centralized schemes lack scalability. Currently, research effort is focused in two different directions: (a) enhancing the centralized schemes, (b) devising entirely new distributed schemes.

This presentation will focus on a new distributed dynamic location management strategy for mobile systems. Its salient features are fast location update and query, load balancing among location servers, and scalability. The strategy employs dynamic hashing techniques and quorums to manage location update and query operations. Location information of a mobile host is replicated at a subset of location servers. The set of location servers associated with a mobile host changes with time, depending on the location of mobile hosts and load on the servers. This dynamism prevents situations of heavy load (location update and query messages) on some location servers when the mobile hosts are not uniformly distributed in space, or when some mobile hosts have their location updated or queried more often than others. New location servers can be added to the system as the number of mobile hosts and/or location update and query rates increase. Also, if the load diminishes, the number of location servers in the system can be reduced. Dynamic hashing and quorum systems are used to expand and shrink the number of location servers transparently. Unlike several existing schemes that progressively expand their region of search and may require multiple rounds of messages to locate a mobile host, the proposed scheme requires a single round of message multicasting for location update and query operations. The size of the multicast set is proportional to the square root of the number of location servers and each message has a small size. All multicast messages are restricted to the high bandwidth wired part of the mobile network. Hence, communication overhead and latency are low. The storage overheads imposed on the location servers are nominal.

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT