Efficient Location-Aware Node And Object Discovery In Large-Scale Networks

The performance of many distributed systems is highly sensitive to the latency of finding objects in response to user requests. Efficient discovery of nodes and objects in the network that satisfy application-specific requirements is therefore a critical building block for many distributed systems. In this thesis, I introduce a space-based approach to solving node and object discovery problems. This approach represents the relationship between nodes and objects as distances in an abstract space, maps optimization objectives and constraints of the problem to regions in the space, and combines these regions to identify the solution to the discovery problem. Using the space-based approach, I address three common problems involving node and object discovery. First, I tackle the problem of efficiently discovering nodes with specific network latency characteristics, such as finding the closest server node to a target. This problem is commonly encountered in content distribution networks, online games, and other network services that demand low latency. I describe a system, called Meridian, that uses overlay routing in a small-world inspired network to solve such problems efficiently and accurately. Second, I address the decentralized approximate search problem, where the objective is to efficiently scan an online database for the set of objects that are most similar to given search terms. I describe the Cubit system, which provides a fully decentralized and efficient approximate search primitive for peer-to-peer systems. Finally, I solve the problem of accurately determining the physical location of Internet hosts and describe the Octant system, which uses a novel geometric technique to determine a target node's location from constraints extracted from network measurements. I characterize the performance and accuracy of these systems with data and evaluations drawn from deployments on PlanetLab and end-user systems. The results show that these space-based systems are accurate, efficient and scalable