The Message Flow Model for Routing in Wormhole-Routed Networks

Xiaola Lin; Philip K. McKinley; Lionel M. Ni

doi:10.1109/71.395404

The Message Flow Model for Routing in Wormhole-Routed Networks

Xiaola Lin, Philip K. McKinley, Lionel M. Ni

Research output: Contribution to journal › Journal Article › peer-review

52 Citations (Scopus)

Abstract

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. This method may be used to develop deterministic, partially-adaptive, and fully-adaptive routing algorithms for wormhole-routed networks with arbitrary topologies. We first establish the necessary and sufficient condition for deadlock-free routing, based on the analysis of the message flow on each channel. We then use the model to develop new adaptive routing algorithms for 2D meshes.

Original language	English
Pages (from-to)	755-760
Number of pages	6
Journal	IEEE Transactions on Parallel and Distributed Systems
Volume	6
Issue number	7
DOIs	https://doi.org/10.1109/71.395404
Publication status	Published - Jul 1995
Externally published	Yes

Keywords

Channel dependency graph
adaptive routing
deadlockfree routing
mesh networks
message flow model
multicast communication
wormhole routing

Access to Document

10.1109/71.395404

Cite this

@article{7234800860a44d3d993467e1fcb1ebbb,

title = "The Message Flow Model for Routing in Wormhole-Routed Networks",

abstract = "In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. This method may be used to develop deterministic, partially-adaptive, and fully-adaptive routing algorithms for wormhole-routed networks with arbitrary topologies. We first establish the necessary and sufficient condition for deadlock-free routing, based on the analysis of the message flow on each channel. We then use the model to develop new adaptive routing algorithms for 2D meshes.",

keywords = "Channel dependency graph, adaptive routing, deadlockfree routing, mesh networks, message flow model, multicast communication, wormhole routing",

author = "Xiaola Lin and McKinley, \{Philip K.\} and Ni, \{Lionel M.\}",

year = "1995",

month = jul,

doi = "10.1109/71.395404",

language = "English",

volume = "6",

pages = "755--760",

journal = "IEEE Transactions on Parallel and Distributed Systems",

issn = "1045-9219",

publisher = "IEEE Computer Society",

number = "7",

}

TY - JOUR

T1 - The Message Flow Model for Routing in Wormhole-Routed Networks

AU - Lin, Xiaola

AU - McKinley, Philip K.

AU - Ni, Lionel M.

PY - 1995/7

Y1 - 1995/7

N2 - In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. This method may be used to develop deterministic, partially-adaptive, and fully-adaptive routing algorithms for wormhole-routed networks with arbitrary topologies. We first establish the necessary and sufficient condition for deadlock-free routing, based on the analysis of the message flow on each channel. We then use the model to develop new adaptive routing algorithms for 2D meshes.

AB - In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. This method may be used to develop deterministic, partially-adaptive, and fully-adaptive routing algorithms for wormhole-routed networks with arbitrary topologies. We first establish the necessary and sufficient condition for deadlock-free routing, based on the analysis of the message flow on each channel. We then use the model to develop new adaptive routing algorithms for 2D meshes.

KW - Channel dependency graph

KW - adaptive routing

KW - deadlockfree routing

KW - mesh networks

KW - message flow model

KW - multicast communication

KW - wormhole routing

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:A1995RK83200008

UR - https://openalex.org/W2127272160

UR - https://www.scopus.com/pages/publications/0029341372

U2 - 10.1109/71.395404

DO - 10.1109/71.395404

M3 - Journal Article

SN - 1045-9219

VL - 6

SP - 755

EP - 760

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 7

ER -

The Message Flow Model for Routing in Wormhole-Routed Networks

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this