Self-stabilizing routing protocols
Abstract
In systems made up of processors and links connecting the processors, the global state of the system is defined by the local variables of the individual processors. The set of global states can be defined as being either legal or illegal. A self-stabilizing system is one that forces a system from an illegal state to a global legal state without external interference, using a finite number of steps. This thesis will concentrate on application of self-stabilization to routing problems, in particular path identification, connectivity and methods involved in destinational routing. Traditional methods for creation of rooted paths to multiple destinations in a computer network involve the creation of spanning trees, and broadcasting information on the tree to be picked up by the individual nodes on the tree. The information for the creation of the tree are all sourced at the root, and the individual nodes update information from the centralized source. The self-stabilization model for networks allows the decision for a creation of a tree and message checking to occur automatically, locally, and more important, in contrast to traditional networks, asynchronously. The creation, "message" passing occur with a node and its immediate neighbor, and the tree, path is created based on this communicated data. In addition, the self-stabilization model eliminates the requisite initialization of traditional networks, i.e. given any arbitrary initial state the system (a given network) is guaranteed to stabilize to a legal global state, in the case of a broadcast network, a minimal spanning tree rooted at a source.