Edge Display Spanning Trees and Recovery in Data Communication Networks.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1983
Accession Number
ADA134378

Entities

People

  • James Anthony Roskind

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Communication Channels
  • Communication Networks
  • Computational Complexity
  • Computer Science
  • Computers
  • Databases
  • Digital Communications
  • Electrical Engineering
  • Engineering
  • Formal Languages
  • Literature
  • Massachusetts
  • Motivation
  • Network Topology
  • Packet Switching
  • Standards

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Agent-Based Social Robotics and Mobile-Assisted Learning in Virtual Environments.
  • Applied Combinatorial Optimization and Logic Circuit Design.