Worst-case traffic for oblivious routing functions
Publication
, Conference
Towles, B; Dally, WJ
Published in: Annual ACM Symposium on Parallel Algorithms and Architectures
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 most practical routing functions. 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%.
Duke Scholars
Published In
Annual ACM Symposium on Parallel Algorithms and Architectures
DOI
Publication Date
January 1, 2002
Start / End Page
1 / 8
Citation
APA
Chicago
ICMJE
MLA
NLM
Towles, B., & Dally, W. J. (2002). Worst-case traffic for oblivious routing functions. In Annual ACM Symposium on Parallel Algorithms and Architectures (pp. 1–8). https://doi.org/10.1145/564871.564872
Towles, B., and W. J. Dally. “Worst-case traffic for oblivious routing functions.” In Annual ACM Symposium on Parallel Algorithms and Architectures, 1–8, 2002. https://doi.org/10.1145/564871.564872.
Towles B, Dally WJ. Worst-case traffic for oblivious routing functions. In: Annual ACM Symposium on Parallel Algorithms and Architectures. 2002. p. 1–8.
Towles, B., and W. J. Dally. “Worst-case traffic for oblivious routing functions.” Annual ACM Symposium on Parallel Algorithms and Architectures, 2002, pp. 1–8. Scopus, doi:10.1145/564871.564872.
Towles B, Dally WJ. Worst-case traffic for oblivious routing functions. Annual ACM Symposium on Parallel Algorithms and Architectures. 2002. p. 1–8.
Published In
Annual ACM Symposium on Parallel Algorithms and Architectures
DOI
Publication Date
January 1, 2002
Start / End Page
1 / 8