Edge Display Spanning Trees and Recovery in Data Communication Networks.

摘要

In this thesis we discuss a variety of ways in which information about topological changes (failures and restorations of links of a network) can be disseminated to the nodes of a packet switching network. We demonstrate how the use of precomputed (before the failures) structures can aid in providing swift and communications efficient methods of achieving the necessary notifications. One major result of this thesis is a new and computationally efficient method for finding such spanning trees (O(knkn) time to find k edge-disjoint spanning trees in a network with n nodes). The second major result that we provide is a way in which precomputed edge disjoint trees can be used by a distributed algorithm to effectively synchronize the nodes so that they use the same topology as a basis for routing.