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