The DOI matches its Crossref record.
Near-Optimal Worst-Case Throughput Routing for Two-Dimensional Mesh Networks
Abstract
Minimizing latency and maximizing throughput are important goals in the design of routing algorithms for interconnection networks. Ideally, we would like a routing algorithm to (a) route packets using the minimal number of hops to reduce latency and preserve communication locality, (b) deliver good worst-case and average-case throughput and (c) enable low-complexity (and hence, low latency) router implementation. In this paper, we focus on routing algorithms for an important class of interconnection networks: two dimensional (2D) mesh networks. Existing routing algorithms for mesh networks fail to satisfy one or more of design goals mentioned above. Variously, the routing algorithms suffer from poor worst case throughput (ROMM [13], DOR [23]), poor latency due to increased packet hops (VALIANT [31]) or increased latency due to hardware complexity (minimaladaptive [7, 30]). The major contribution of this paper is the design of an oblivious routing algorithm - O1TURN - with provable near-optimal worst-case throughput, good average-case throughput, low design complexity and minimal number of network hops for 2D-mesh networks, thus satisfying all the stated design goals. O1TURN offers optimal worst-case throughput when the network radix (k in a kxk network) is even. When the network radix is odd, O1TURN is within a 1/k2 factor of optimal worst-case throughput. O1TURN achieves superior or comparable average-case throughput with global traffic as well as local traffic. For example, O1TURN achieves 18.8%, 0.7% and 13.6% higher average-case throughput than DOR, ROMM and VALIANT routing, respectively when averaged over one million random traffic patterns on an 8x8 network. Finally, we demonstrate that O1TURN is well suited for a partitioned router implementation that is of similar delay complexity as a simple dimension-ordered router. Our implementation incurs a marginal increase in switch arbitration delay that is completely hidden in pipelined routers as it is not on the clock-critical path.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Opinion mining and sentiment analysis
Pang, B., & Lee, L. (2008) · Foundations and Trends® in Information Retrieval · doi:10.1561/1500000011 · Cited by 6,372
Outstanding Research Problems in NoC Design: System, Microarchitecture, and Circuit Perspectives
Marculescu, R., Ogras, U. Y., Peh, L.-S., Jerger, N. E., & Hoskote, Y. (2009) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2008.2010691 · Cited by 683
Express virtual channels: towards the ideal interconnection fabric
Kumar, A., Peh, L.-S., Kundu, P., & Jha, N. K. (2007) · Proceedings of the 34th annual international symposium on Computer architecture · doi:10.1145/1250662.1250681 · Cited by 335
Metadata
- Authors
- Seo, D., Ali, A., Lim, W.-T., Rafique, N., & Thottethodi, M.
- Venue
- ACM SIGARCH Computer Architecture News
- Published
- 2005-05
- Volume
- 33
- Issue
- 2
- Pages
- 432-443
- ISSN
- 0163-5964 (ISSN-L)
- OpenAlex
- W2162788247
- Cited by
- 173
- References
- 0
- FWCI
- 12.43
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Near-Optimal Worst-Case Throughput Routing for Two-Dimensional Mesh Networks. https://app.cochat.ai/papers/10.1145/1080695.1070006
- The paper
- Seo, D., Ali, A., Lim, W.-T., Rafique, N., & Thottethodi, M. (2005). Near-Optimal Worst-Case Throughput Routing for Two-Dimensional Mesh Networks. ACM SIGARCH Computer Architecture News. https://doi.org/10.1145/1080695.1070006
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.