Skip to main content

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