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):

Report Date:

1983-10-01

Pagination or Media Count:

247.0

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 Oknkn 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.

Subject Categories:

  • Computer Hardware
  • Computer Systems
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE