Accession Number : ADA134378
Title : Edge Display Spanning Trees and Recovery in Data Communication Networks.
Descriptive Note : Doctoral thesis,
Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS
Personal Author(s) : Roskind,James Anthony
PDF Url : ADA134378
Report Date : Oct 1983
Pagination or Media Count : 247
Abstract : 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.
Descriptors : *Communications networks, *Computer aided instruction, Failure(Electronics), Data transmission systems, Packets, Nodes, Decision making, Data links, Data processing terminals, Topology, Algorithms, Edges, Data displays, Theses
Subject Categories : Computer Hardware
Distribution Statement : APPROVED FOR PUBLIC RELEASE