An inherently stabilizing algorithm for node-to-node routing over all shortest node-disjoint paths in hypercube networks

Ozgur Sinanoglu, Mehmet Hakan Karaata, Bader Albdaiwi

Research output: Contribution to journalArticlepeer-review

Abstract

The node-disjoint paths problem deals with finding node-disjoint paths from a source node s to target node t, where t ≠ s. Two paths from s to t are said to be node-disjoint iff they do not have any common vertices except for their endpoints. Distributed solutions to the node-disjoint paths problem have numerous applications such as secure message transmission, reliable routing, and network survivability. In this paper, we present a simple distributed algorithm that is both stabilizing and inherently stabilizing under a realistic model that describes system interfaces and implementation issues in detail to route messages over all shortest node-disjoint paths from one process to another in an n-dimensional hypercube network.

Original languageEnglish (US)
Article number5445078
Pages (from-to)995-999
Number of pages5
JournalIEEE Transactions on Computers
Volume59
Issue number7
DOIs
StatePublished - 2010

Keywords

  • Fault-tolerance
  • Hypercube networks
  • Inherent stabilization
  • Node-disjoint paths
  • Stabilization

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'An inherently stabilizing algorithm for node-to-node routing over all shortest node-disjoint paths in hypercube networks'. Together they form a unique fingerprint.

Cite this