Universal Wormhole Routing

Ronald I. Greenberg; Hyeong-Cheol Oh

doi:10.1109/SPDP.1993.395550

Universal Wormhole Routing

Ronald I. Greenberg, Hyeong-Cheol Oh

Department of Computer Science

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

Abstract

We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log 3 A) slowdown, when all worms have the same length. Variable-length worms are also considered. We run some simulations on the fat-tree which show that not only does wormhole routing tend to perform better than the more heavily studied store-and-forward routing, but that performance superior to our provable bound is attainable in practice

Original language	American English
Journal	Computer Science: Faculty Publications and Other Works
DOIs	https://doi.org/10.1109/SPDP.1993.395550
State	Published - Dec 1 1993

Keywords

wormhole routing
packet routing
randomized routing
greedy routing
area-universal networks
fat-tree interconnection network

Disciplines

Computer Sciences
Theory and Algorithms

Access to Document

10.1109/SPDP.1993.395550License: Unspecified

Universal Wormhole RoutingFinal published version, 182 KBLicense: Unspecified

Cite this

@article{eabf1ec9b6024ed48366c5070bdceac0,

title = "Universal Wormhole Routing",

abstract = " We examine the wormhole routing problem in terms of the {"}congestion{"} c and {"}dilation{"} d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log 3 A) slowdown, when all worms have the same length. Variable-length worms are also considered. We run some simulations on the fat-tree which show that not only does wormhole routing tend to perform better than the more heavily studied store-and-forward routing, but that performance superior to our provable bound is attainable in practice",

keywords = "wormhole routing, packet routing, randomized routing, greedy routing, area-universal networks, fat-tree interconnection network",

author = "Greenberg, {Ronald I.} and Hyeong-Cheol Oh",

year = "1993",

month = dec,

day = "1",

doi = "10.1109/SPDP.1993.395550",

language = "American English",

journal = "Computer Science: Faculty Publications and Other Works",

}

TY - JOUR

T1 - Universal Wormhole Routing

AU - Greenberg, Ronald I.

AU - Oh, Hyeong-Cheol

PY - 1993/12/1

Y1 - 1993/12/1

N2 - We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log 3 A) slowdown, when all worms have the same length. Variable-length worms are also considered. We run some simulations on the fat-tree which show that not only does wormhole routing tend to perform better than the more heavily studied store-and-forward routing, but that performance superior to our provable bound is attainable in practice

AB - We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log 3 A) slowdown, when all worms have the same length. Variable-length worms are also considered. We run some simulations on the fat-tree which show that not only does wormhole routing tend to perform better than the more heavily studied store-and-forward routing, but that performance superior to our provable bound is attainable in practice

KW - wormhole routing

KW - packet routing

KW - randomized routing

KW - greedy routing

KW - area-universal networks

KW - fat-tree interconnection network

UR - https://ecommons.luc.edu/cs_facpubs/113

U2 - 10.1109/SPDP.1993.395550

DO - 10.1109/SPDP.1993.395550

M3 - Article

JO - Computer Science: Faculty Publications and Other Works

JF - Computer Science: Faculty Publications and Other Works

ER -

Universal Wormhole Routing

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this