Peer-to-peer (P2P) applications in general, and unstructured applications in particular, have been very popular in the recent past. In this thesis, we identify common problems encountered in the course of developing different diverse peer-to-peer applications, and propose solutions to them. The broad problems we study are, namely, (i) load-balancing in heterogeneous unstructured P2P networks, where capacities to support load differ among the different members of the network, and application load is to be distributed in accordance with members' capacities to support it, and (ii) "extreme" nearest neighbor discovery in P2P networks, where the intent is to discover the latency-wise nearest peer in a P2P network, even when the nearest peer is in the same extended LAN or campus network. The goal of this thesis is to come up with a powerful set of basic mechanisms that the developers of many different P2P applications can reuse, rather than having to repeatedly reinvent the same solutions.

We examine two main causes of load in unstructured networks: the underlying random graph, and the process of random node selection, where random peers are periodically picked to handle application load. We extensively evaluate different approaches to do heterogeneous random graph construction and peer selection, and identify our Swaplinks algorithm as the best approach. Swaplinks builds robust graphs where node degrees are close to their desired degrees, provides a good base to perform random peer selection, and is virtually free of tuning knobs, making it very practical to deploy.

In our study of the extreme-nearest neighbor discovery problem, we identify and demonstrate a condition we call the clustering condition caused by the Internet last-hop architecture -- under the clustering condition, many different peers are located at about the same latency from one another, making it expensive for previous nearest-peer solutions to correctly find the nearest peer. We propose different solutions to overcome this problem, and show, using preliminary evaluations, that one of them is very attractive.