Topology and Routing in Overlay Networks by

In this age of information, new models of information exchange methodologies based on overlay networks are gaining popular attention. Overlay networks provide a logical interconnection topology over an existing physical network. Overlay networks offer bene-fits such as ease of implementation, flexibility, adaptability, and incremental deployability. Due to the wide range of applications and advantages, formal study of overlay networks is required to understand the various research challenges in this context. In this thesis, we study two classes of overlay networks namely peer-to-peer networks and wireless ad hoc networks. Our focus will be along two central issues in overlay net-works: how to arrive at efficient topologies and how to provide efficient routing strategies. Peer-to-peer networks have gained a lot of research attention in recent years for various reasons. Despite many advances however, fundamental questions such as how to design deterministic constructions, and how to organize peers of non-uniform bandwidth have remained open. In this thesis, we answer these questions by providing a deterministic overlay topology, Pagoda, that can be used for efficient routing, data management an