Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
A Randomized Algorithm for Label Assignment in Dynamic Networks

Meg Walraed-Sullivan, Radhika Niranjan Mysore, Keith Marzullo, and Amin Vahdat

Abstract

A basic problem in distributed computing has to do with assigning unique labels — that is, names or addresses — to network elements. Some approaches to solving this problem include using static assignment (e.g., MAC addresses), or using a centralized authority (e.g., DHCP). In this paper, we present an approach that is suitable for dynamic environments: where the rules constraining the label choices depend on the network topology, which in turn can change. This problem arose in the context of automatic address assignment in large-scale data center networks, and so we consider issues such as the scalability of message load and convergence time. We give a new algorithm, called the Decider/Chooser Protocol, and show its use in the assignment of labels in data center networks. We evaluate the correctness of the Decider/Chooser Protocol through proofs and model checking, and explore its performance via mathematical analysis and simulation. Through this evaluation, we find that the Decider/Chooser Protocol is well-suited for label assignment in the data center environment.

Details

Publication typeTechReport
URLhttp://csetechrep.ucsd.edu/Dienst/UI/2.0/Describe/ncstrl.ucsd_cse/CS2013-0994
PublisherUniversity of California, San Diego
> Publications > A Randomized Algorithm for Label Assignment in Dynamic Networks