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