A router architecture for real-time communication in multicomputer networks

Jennifer Rexford, John Hall, Kang G. Shin

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


Parallel machines have the potential to satisfy the large computational demands of real-time applications. These applications require a predictable communication network, where time-constrained traffic requires bounds on throughput and latency, while good average performance suffices for best-effort packets. This paper presents a new router architecture that tailors low-level routing, switching, arbitration, flow-control, and deadlock-avoidance policies to the conflicting demands of each traffic class. The router implements bandwidth regulation and deadline-based scheduling, with packet switching and table-driven multicast routing, to bound end-to-end delay and buffer requirements for time-constrained traffic while allowing best-effort traffic to capitalize on the low-latency routing and switching schemes common in modern parallel machines. To limit the cost of servicing time-constrained traffic, the router includes a novel packet scheduler that shares link-scheduling logic across the multiple output ports, while masking the effects of clock rollover on the represention of packet eligibility times and deadlines. Using the Verilog hardware description language and the Epoch silicon compiler, we demonstrate that the router design meets the performance goals of both traffic classes in a single-chip solution. Verilog simulation experiments on a detailed timing model of the chip show how the implementation and performance properties of the packet scheduler scale over a range of architectural parameters.

Original languageEnglish (US)
Pages (from-to)1088-1101
Number of pages14
JournalIEEE Transactions on Computers
Issue number10
StatePublished - 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • Link scheduling
  • Multicomputer router
  • Packet switching
  • Real-time communication
  • Wormhole switching


Dive into the research topics of 'A router architecture for real-time communication in multicomputer networks'. Together they form a unique fingerprint.

Cite this