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
      Computer Systems
      Non-radio Communications

Distribution Statement : APPROVED FOR PUBLIC RELEASE