Reconfiguration of spanning trees in networks in the presence of node failures

K. Ravindran, G. Singh, P. Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Connectivity among a set of user entities in a network can be provided by a network level abstraction of acyclic graph (or spanning tree). The paper discusses the reconfiguration of a graph in the presence of failure of network nodes. A reconfiguration manifests as a graph fragmentation problem, whereby two or more disjoint subgraphs attempt to connect with one another to form a composite graph. Fragment interconnection requires contention resolution between fragments to avoid cycles. This paper presents two classes of contention resolution algorithms applicable for environments with potentially large number of fragments. They are based on pre-established ranking among fragments and random arbitration among fragments. The algorithms have been evaluated by simulation and compared. The algorithms are useful in supporting data multicasting across workstations and distributed computations involving data on different machines.

Original languageEnglish (US)
Title of host publication1993 IEEE 13th International Conference on Distributed Computing Systems
PublisherIEEE Computer Society
Pages219-226
Number of pages8
ISBN (Print)0818637706
StatePublished - Jan 1 1993
Externally publishedYes
Event1993 IEEE 13th International Conference on Distributed Computing Systems - Pittsburgh, PA, USA
Duration: May 25 1993May 28 1993

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Other

Other1993 IEEE 13th International Conference on Distributed Computing Systems
CityPittsburgh, PA, USA
Period5/25/935/28/93

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Reconfiguration of spanning trees in networks in the presence of node failures'. Together they form a unique fingerprint.

  • Cite this

    Ravindran, K., Singh, G., & Gupta, P. (1993). Reconfiguration of spanning trees in networks in the presence of node failures. In 1993 IEEE 13th International Conference on Distributed Computing Systems (pp. 219-226). (Proceedings - International Conference on Distributed Computing Systems). IEEE Computer Society.