As the role of the Internet has been steadily gaining in importance, overlays are increasingly being used to provide new services and to deploy older ones. Some of the services for which overlays have been proposed include multicast, quality of service (QoS), search, and resilient networks. The use of overlays, in turn, has led to more interest in improving their performance. The performance of an overlay network depends significantly on how the network is structured, i.e., the placement of the nodes in the underlying network topology, the links between the overlay nodes and the access links of these nodes. This thesis focuses on algorithms for improving the performance of