Abstract
Emerging parallel real-time and multimedia applications broaden the range of performance requirements imposed on the interconnection network. This communication typically consists of a mixture of different traffic classes, where guaranteed packets require bounds on latency or throughput while good average performance suffices for the best-effort traffic. This paper investigates how multicomputer routers can capitalize on low-latency routing and switching techniques for best-effort traffic while still supporting guaranteed communication. Through simulation experiments, we show that certain architectural features are best-suited to particular performance requirements. Based on these results, the paper proposes and evaluates a router architecture that tailors low-level routing, switching, and flow-control policies to the unique needs of best-effort and guaranteed traffic. Careful selection of these policies, coupled with fine-grain arbitration between the classes, allows the guaranteed and best-effort packets to share network bandwidth without sacrificing the performance of either class.
The work reported in this paper was supported in part by the National Science Foundation under Grant MIP-9203895 and an Office of Naval Research graduate fellowship. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Cohen, G. G. Finn, R. Felderman, and A. DeSchon, “The use of message-based multicomputer components to construct gigabit networks,” Computer Communication Review, vol. 23, no. 3, pp. 32–44, July 1993.
R. Cypher, A. Ho, S. Konstantinidou, and P. Messina, “Architectural requirements of parallel scientific applications with explicit communication,” in Proc. Int'l Symposium on Computer Architecture, pp. 2–13, May 1993.
D. Ferrari, “Client requirements for real-time communication services,” IEEE Communications Magazine, pp. 65–72, November 1990.
P. Kermani and L. Kleinrock, “Virtual cut-through: A new computer communication switching technique,” Computer Networks, vol. 3, no. 4, pp. 267–286, September 1979.
W. J. Dally and C. L. Seitz, “The torus routing chip,” Journal of Distributed Computing, vol. 1, no. 3, pp. 187–196, 1986.
J. J. Bae and T. Suda, “Survey of traffic control schemes and protocols in ATM networks,” Proceedings of the IEEE, vol. 79, no. 2, pp. 170–189, February 1991.
C. M. Aras, J. F. Kurose, D. S. Reeves, and H. Schulzrinne, “Real-time communication in packet-switched networks,” Proceedings of the IEEE, vol. 82, no. 1, pp. 122–139, January 1994.
W. J. Dally and P. Song, “Design of a self-timed VLSI multicomputer communication controller,” in IEEE Int'l Conf. on Computer Design: VLSI in Computers, pp. 230–234, 1987.
W. J. Dally, J. A. S. Fiske, J. S. Keen, R. A. Lethin, M. D. Noakes, P. R. Nuth, R. E. Davison, and G. A. Fyler, “The Message-Driven Processor: A multicomputer processing node with efficient mechanisms,” IEEE Micro, pp. 23–39, April 1992.
C. Peterson, J. Sutton, and P. Wiley, “iWarp: A 100-MOPS LIW microprocessor for multicomputers,” IEEE Micro, pp. 26–29,81–87, June 1991.
D. Talia, “Message-routing systems for transputer-based multicomputers,” IEEE Micro, pp. 62–72, June 1993.
M. G. Norman and P. Thanisch, “Models of machines and computation for mapping in multicomputers,” ACM Computing Surveys, vol. 25, no. 3, pp. 263–302, September 1993.
W. Dally, “Virtual-channel flow control,” IEEE Trans. Parallel and Distributed Systems, vol. 3, no. 2, pp. 194–205, March 1992.
J. Dolter, S. Daniel, A. Mehra, J. Rexford, W. Feng, and K. G. Shin, “SPIDER: Flexible and efficient communication support for point-to-point distributed systems,” Technical Report CSE-TR-180-93, University of Michigan, October 1993. To appear in Proc. Int. Conf. on Distributed Computing Systems, June 1994.
J. H. Kim and A. A. Chien, “Evaluation of wormhole routed networks under hybrid traffic loads,” in Proc. Hawaii Int'l Conf. on System Sciences, pp. 276–285, January 1993.
J. Dolter, A Programmable Routing Controller Supporting Multi-mode Routing and Switching in Distributed Real-Time Systems, PhD thesis, University of Michigan, September 1993.
W. Feng, J. Rexford, A. Mehra, S. Daniel, J. Dolter, and K. Shin, “Architectural support for managing communication in point-to-point distributed systems,” Technical Report CSE-TR-197-94, University of Michigan, March 1994.
J. Rexford, J. Dolter, and K. G. Shin, “Hardware support for controlled interaction of guaranteed and best-effort communication,” in Proc. Workshop on Parallel and Distributed Real-Time Systems, April 1994.
X. Zhang, “System effects of interprocessor communication latency in multicomputers,” IEEE Micro, pp. 12–15,52–55, April 1991.
W. J. Dally and C. L. Seitz, “Deadlock-free message routing in multiprocessor interconnection networks,” IEEE Trans. Computers, vol. C-36, no. 5, pp. 547–553, May 1987.
J. Ngai and C. Seitz, “A framework for adaptive routing in multicomputer networks,” in Symposium on Parallel Algorithms and Architectures, pp. 1–9, June 1989.
W. Dally and H. Aoki, “Deadlock-free adaptive routing in multicomputer networks using virtual channels,” IEEE Trans. Parallel and Distributed Systems, vol. 4, no. 4, pp. 466–475, April 1993.
R. Jain, The Art of Computer Systems Performance Analysis, John Wiley & Sons, Inc., 1991.
B. Tsai and K. G. Shin, “Sequencing of concurrent communication traffic in a mesh multicomputer with virtual channels,” to appear in Proc. Int'l Conf. on Parallel Processing, August 1994.
J.-P. Li and M. W. Mutka, “Priority based real-time communication for large scale wormhole networks,” in Proc. International Parallel Processing Symposium, pp. 433–438, April 1994.
J.-P. Li and M. W. Mutka, “Real-time virtual channel flow control,” in Phoenix Conference on Computers and Communication, April 1994.
A. A. Chien, “A cost and speed model for k-ary n-cube wormhole routers,” in Proc. Hot Interconnects, August 1993.
D. D. Kandlur, K. G. Shin, and D. Ferrari, “Real-time communication in multihop networks,” in Proc. Int. Conf. on Distributed Computer Systems, pp. 300–307, May 1991.
H. J. Chao and N. Uzun, “A VLSI sequencer chip for ATM traffic shaper and queue manager,” IEEE Journal of Solid-State Circuits, vol. 27, no. 11, pp. 1634–1643, November 1992.
K. Toda, K. Nishida, E. Takahashi, N. Michell, and Y. Yamaguchi, “Implementation of a priority forwarding router chip for real-time interconnection networks,” in Proc. Workshop on Parallel and Distributed Real-Time Systems, April 1994.
S. Konstantinidou, “Segment router: A novel router design for parallel computers,” to appear in Proc. Symposium on Parallel Algorithms and Architectures, June 1994.
M. W. Mutka, “Using rate monotonic scheduling technology for real-time communications in a wormhole network,” in Proc. Workshop on Parallel and Distributed Real-Time Systems, April 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rexford, J., Shin, K.G. (1994). Support for multiple classes of traffic in multicomputer routers. In: Bolding, K., Snyder, L. (eds) Parallel Computer Routing and Communication. PCRCW 1994. Lecture Notes in Computer Science, vol 853. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58429-3_32
Download citation
DOI: https://doi.org/10.1007/3-540-58429-3_32
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58429-2
Online ISBN: 978-3-540-48787-6
eBook Packages: Springer Book Archive