| The idea of application-level routing has appeared in a wide variety of distributed systems. Examples include distributed publish-subscribe systems, Web caching, mobile applications, and network management. However, most of these designs have only explored application-level routing from the standpoint of their specific applications. To address the rapidly increasing demand of these systems, this thesis examines some general principles and mechanisms of large-scale application-level routing.;In this thesis, we first motivate our work in large-scale application-level routing with two case studies: a Web cache consistency architecture and its extension to a large-scale publish-subscribe system. Then, we discuss general design issues of application-level routing and focus on one specific problem: virtual topology design. Building on previous work, we propose a methodology for performance evaluation of virtual topologies in application-level routing. Using this methodology, we show that a simple "decentralized" heuristic results in performance comparable to that of algorithms requiring more global information. We have also studied the impact of physical topology properties on topology construction algorithms, and find that randomization of links in the virtual topology can greatly reduce sensitivity to physical topology with some performance degradation, especially for small virtual topologies. Ultimately, this study attempts to provide guidance for self-configuring protocols to build virtual topologies with desirable properties. |
