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

doi:10.1109/TC.2010.76

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 journal › Article › peer-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 language	English (US)
Article number	5445078
Pages (from-to)	995-999
Number of pages	5
Journal	IEEE Transactions on Computers
Volume	59
Issue number	7
DOIs	https://doi.org/10.1109/TC.2010.76
State	Published - 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

Access to Document

10.1109/TC.2010.76

Cite this

@article{c54baddb9f164313b89a7f377209947e,

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

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.",

keywords = "Fault-tolerance, Hypercube networks, Inherent stabilization, Node-disjoint paths, Stabilization",

author = "Ozgur Sinanoglu and Karaata, {Mehmet Hakan} and Bader Albdaiwi",

note = "Funding Information: This work was supported by Kuwait University, Research Grant No. [EO 02/09].",

year = "2010",

doi = "10.1109/TC.2010.76",

language = "English (US)",

volume = "59",

pages = "995--999",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "7",

}

TY - JOUR

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

AU - Sinanoglu, Ozgur

AU - Karaata, Mehmet Hakan

AU - Albdaiwi, Bader

N1 - Funding Information: This work was supported by Kuwait University, Research Grant No. [EO 02/09].

PY - 2010

Y1 - 2010

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

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

KW - Fault-tolerance

KW - Hypercube networks

KW - Inherent stabilization

KW - Node-disjoint paths

KW - Stabilization

UR - http://www.scopus.com/inward/record.url?scp=77952915954&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77952915954&partnerID=8YFLogxK

U2 - 10.1109/TC.2010.76

DO - 10.1109/TC.2010.76

M3 - Article

AN - SCOPUS:77952915954

SN - 0018-9340

VL - 59

SP - 995

EP - 999

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 7

M1 - 5445078

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this