Skip to main content

Worst-case traffic for oblivious routing functions

Publication ,  Journal Article
Towles, B; Dally, WJ
Published in: IEEE Computer Architecture Letters
January 1, 2002

This paper presents an algorithm to find a worst-case traffic pattern for any oblivious routing algorithm on an arbitrary interconnection network topology. The linearity of channel loading offered by oblivious routing algorithms enables the problem to be mapped to a bipartite maximum-weight matching, which can be solved in polynomial time for routing functions with a polynomial number of paths. Finding exact worst-case performance was previously intractable, and we demonstrate an example case where traditional characterization techniques overestimate the throughput of a particular routing algorithm by 47%. © 2002, IEEE. All rights reserved.

Duke Scholars

Published In

IEEE Computer Architecture Letters

DOI

ISSN

1556-6056

Publication Date

January 1, 2002

Volume

1

Issue

1

Start / End Page

4

Related Subject Headings

  • Computer Hardware & Architecture
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Towles, B., & Dally, W. J. (2002). Worst-case traffic for oblivious routing functions. IEEE Computer Architecture Letters, 1(1), 4. https://doi.org/10.1109/L-CA.2002.12
Towles, B., and W. J. Dally. “Worst-case traffic for oblivious routing functions.” IEEE Computer Architecture Letters 1, no. 1 (January 1, 2002): 4. https://doi.org/10.1109/L-CA.2002.12.
Towles B, Dally WJ. Worst-case traffic for oblivious routing functions. IEEE Computer Architecture Letters. 2002 Jan 1;1(1):4.
Towles, B., and W. J. Dally. “Worst-case traffic for oblivious routing functions.” IEEE Computer Architecture Letters, vol. 1, no. 1, Jan. 2002, p. 4. Scopus, doi:10.1109/L-CA.2002.12.
Towles B, Dally WJ. Worst-case traffic for oblivious routing functions. IEEE Computer Architecture Letters. 2002 Jan 1;1(1):4.

Published In

IEEE Computer Architecture Letters

DOI

ISSN

1556-6056

Publication Date

January 1, 2002

Volume

1

Issue

1

Start / End Page

4

Related Subject Headings

  • Computer Hardware & Architecture