A Randomized Algorithm for Label Assignment in Dynamic Networks

Meg Walraed-Sullivan, Radhika Niranjan Mysore, Keith Marzullo and Amin Vahdat
CS2013-0994
February 14, 2013

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.


How to view this document


The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.


[ Search ]


NCSTRL
This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu