| As modern computer networks continue to grow in their scale and size with a fast pace, how to provide efficient and scalable lookup services, such as mobile node location lookup in mobile ad-hoc networks (MANET) or object lookup in peer-to-peer (P2P) file sharing, becomes a great research challenge. An important vantage point to attack this hard problem is to exploit the locality property of communication patterns in such large networks. For example, in a large MANET, a node is much more likely to communicate with nearby nodes. In this thesis, we develop data structures and algorithms to exploit such locality properties in the two aforementioned types of lookup services. The basic idea of our approach is to build a hierarchical level of areas based on the real or virtual geographical space of the network, and to confine the communications within a certain level of area whenever possible. We present a novel rendezvous mechanism called the Geographically-Scoped Hashing (GSH), which is used to coordinate the publish and query operations of lookup service in a distributed and locality-aware manner. The complete design of two schemes, HIGH-GRADE for location lookup in MANET and Leopard for object lookup in P2P networks, are presented. Through detailed analysis and simulation, we demonstrate many advantages of the two schemes. HIGH-GRADE is shown to have superior scalability property than other related schemes in terms of both communication and storage cost, especially given a localized data traffic pattern that conforms to the power-law property. Leopard achieves a constant routing stretch, always locates a nearby copy when many copies of an object exist, and mitigates "flash crowds" for popular objects with near-optimal load balance. We also present a prototype implementation of these lookup services, named Leopard Over Mesh (LOM). Our experience in developing LOM proves that the GSH-based solutions are of reasonable complexity and can be flexibly integrated with the commodity platforms such as a wireless mesh network based on Linux or Microsoft Windows. |
