Structured Overlays: Maintenance and Dynamics

This chapter focuses on the methods by which the peers form a structured overlay and maintain its geometric and routing properties, a process referred to as overlay maintenance. The discussion is organized into different overlay categories: prefix routing, ring with logarithmic degree mesh, and constant degree graphs. In addition, a stochastic model of overlay maintenance under churn is presented. The chapter concludes with a discussion of hierarchical and federated overlay architectures. Overlay maintenance mechanisms require efficient methods to find stale routing table entries and replace them with new entries in a way that retains the desired routing behavior. Overlay maintenance algorithms have to be devised to include efficient features that are able to handle peer churn.