ISBN 978-3-8439-3455-8

978-3-8439-3455-8, Reihe Informatik

Michael Stein
Local Algorithms for Distributed Topology Adaptation

221 Seiten, Dissertation Technische Universität Darmstadt (2017), Softcover, A4

Zusammenfassung / Abstract

In communication networks, the connectivity between nodes is conceptualized as network topologies. Topologies constitute a crucial aspect of network design, maintenance, and optimization. Topology adaptations modify topologies at runtime to optimize the network w.r.t. given goals, e.g., energy conservation or load balancing. Topology adaptations shall be scalable and efficient; a concern that is commonly pursued by designing distributed algorithms (without centralized control) that are ‘local’ in the sense that each node acts based on limited knowledge about the network. Although locality is a major concern even beyond the field of topology adaptation, the distinguishing characteristics and graduations of local algorithms have been explored insufficiently in practice. The consensus among designers of distributed algorithms mainly restricts to the statement that local algorithms have a bounded view of the topology. This dissertation contributes to the systematic understanding of locality in the field of topology adaptation. Among other things, the dissertation presents a classification of locality, novel local algorithms for topology adaptation, and a systematic approach for locality control of existing topology adaptations.