Publication:

ROMM Routing on Mesh and Torus Networks

Thumbnail Image

Open/View Files

tr-08-95.pdf (325.11 KB)

Date

1995

Authors

Published Version

Published Version

Journal Title

Journal ISSN

Volume Title

Publisher

The Harvard community has made this article openly available. Please share how this access benefits you.

Research Projects

Organizational Units

Journal Issue

Citation

Nesson, Ted and S. Lennart Johnsson. 1995. ROMM Routing on Mesh and Torus Networks. Harvard Computer Science Group Technical Report TR-08-95.

Abstract

ROMM is a class of Randomized, Oblivious, Multi-phase, Minimal routing algorithms. ROMM routing offers a potential for improved performance compared to both fully randomized algorithms and deterministic oblivious algorithms, under both light and heavy loads. ROMM routing also offers close to best case performance for many common routing problems. In previous work, these claims were supported by extensive simulations on binary cube networks [30, 31]. Here we present analytical and empirical results for ROMM routing on wormhole routed mesh and torus networks. Our simulations show that ROMM algorithms can perform several representative routing tasks 1.5 to 3 times faster than fully randomized algorithms, for medium{sized networks. Furthermore, ROMM algorithms are always competitive with deterministic, oblivious routing, and in some cases, up to 2 times faster.

Description

Other Available Sources

Research Data

Keywords

Terms of Use

This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service

URI

http://nrs.harvard.edu/urn-3:HUL.InstRepos:24829605

Collections

FAS Scholarly Articles

Endorsement

Review

Supplemented By

Related Stories