A router architecture for real-time point-to-point networks

ABSTRACT

Parallel machines have the potential to satisfy the large computational demands of emerging real-time applications. These applications require a predictable communication network, where time-constrained traffic requires bounds on latency or throughput while good average performance suffices for best-effort packets. This paper presents a router architecture that tailors low-level routing, switching, arbitration and flow-control policies to the conflicting demands of each traffic class. The router implements deadline-based scheduling, with packet switching and table-driven multicast routing, to bound end-to-end delay 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 shares packet buffers and link-scheduling logic between the multiple output ports. Verilog simulations demonstrate that the design meets the performance goals of both traffic classes in a single-chip solution.

REFERENCES

• 1: L. R. Welch and K. Toda, "Architectural support for real-time systems: Issues and trade-offs," in Proc. International Workshop on Real-Time Computing Systems and Applications, December 1994.
• 2: M. W. Mutka, "Using rate monotonic scheduling technology for real-time communications in a wormhole network,ss in 1-'roc. Workshop on 1-'arallel and Dsstmbuted Real- Time Systems, April 1994.
• 3: Jong-Pyng Li , Matt W. Mutka, Priority Based Real-Time Communication for Large Scale Wormhole Networks, Proceedings of the 8th International Symposium on Parallel Processing, p.433-438, April 01, 1994
• 4: A. Saha, A simulator for real-time parallel processing architectures, Proceedings of the 28th Annual Simulation Symposium, p.74, April 25-28, 1995
• 5: K. Toda, K. Nishida, E. Takahashi, N. Michell, and Y. Yamaguchi, "Design and implementation of a priority forwarding router chip for real-time interconnection networks," International Journal of Mini and Microcomputers, vol. 17, no. 1, pp. 42-51, 1995.
• 6: R. Games , A. Kanevsky , P. Krupp , L. Monk, Real-time communications scheduling for massively parallel processors, Proceedings of the Real-Time Technology and Applications Symposium, p.76, May 15-17, 1995
• 7: Reza S. Raji, Smart networks for control, IEEE Spectrum, v.31 n.6, p.49-55, June 1994 [doi>10.1109/6.284793]
• 8: C. M. Aras, J. F. Kurose, D. S. Reeves, and H. Schulzrinne, "Real-time communication in packetswitched networks," Proceedings of the IEEE, vol. 82, pp. 122-139, January 1994.
• 9: D. D. Kandlur , K. G. Shin , D. Ferrari, Real-Time Communication in Multihop Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.10, p.1044-1056, October 1994 [doi>10.1109/71.313121]
• 10: H. Zhang, "Providing end-to-end performance guarantees using non-work-conserving disciplines," Computer Communications, vol. 18, pp. 769-781, October 1995.
• 11: Y. Ofek and M. Yung, "The integrated MetaNet architecture: A switch-based multimedia LAN for parallel computing and real-time traffic," in Proc. 1EEE 1NFO- COM, pp. 802-811, 1994.
• 12: W. J. Dally and C. L. Seitz, "The torus routing chip," Journal of Distributed Computing, vol. 1, no. 3, pp. 187- 196, 1986.
• 13: R. L. Cruz, "A calculus for network delay, part I: Network elements in isolation," IEEE Trans. Information Theory, vol. 37, pp. 114-131, January 1991.
• 14: Q. Zheng and K. G. Shin, "On the ability of establishing real-time channels in point-to-point packet-switched networks," IEEE Trans. Communications, pp. 1096- 1105, February/March/April 1994.
• 15: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 16: Jennifer Rexford , Kang G. Shin, Support for Multiple Classes of Traffic in Multicomputer Routers, Proceedings of the First International Workshop on Parallel Computer Routing and Communication, p.116-130, May 16-18, 1994
• 17: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 18: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 19: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
• 20: K. Aoyama and A. Chien, "Cost of adaptivity and virtual lanes in a wormhole router," Journal of VLSI Design, vol. 2, no. 4, pp. 315-333, 1995.
• 21: F. A. Tobagi, "Fast packet switch architectures for broadband integrated services digital networks," Proceedings of the IEEE, vol. 78, pp. 133-167, January 1990.
• 22: Q. Zheng, K. G. Shin, and C. Chen, "Real-time communication in ATM," in Proc. Annual Conference on Local Computer Networks, pp. 156-164, October 1994.
• 23: D. Picker and It. D. Fellman, "Scaling and performance of a priority packet queue for real-time applications," in Proc. Real-Time Systems Symposium, pp. 56-62, December 1994.
• 24: H. J. Chao, "A novel architecture for queue management in the ATM network," IEEE Journal on Selected Areas in Communications, vol. 9, pp. 1110-1118, September 1991.
• 25: P. E. Boyer, F. M. Guillemin, M. J. Servel, and J.-P. Coudreuse, "Spacing cells protects and enhances utilization of ATM network links," IEEE Network Magazine, pp. 38-49, September 1992.
• 26: E. Wallmeier and T. Worster, "The Spacing Policer, an algorithm for efficient peak bit rate control in ATM networks," in Proc. International Switching Symposium, pp. 22-26, October 1992.
• 27: J. Liebeherr , D. E. Wrege, A versatile packet multiplexer for quality-of-service networks, Proceedings of the Fourth IEEE International Symposium on High Performance Distributed Computing - HPDC '95, p.148, August 02-04, 1995
• 28: J. Rexford, A. Greenberg, and F. Bonomi, "Haxdwareefficient fair queueing architectures for high-speed networks," in Proc. IEEE INFOCOM, March 1996.
• 29: P. Kermani and L. Kleinrock, "Virtual cut-through: A new computer communication switching technique," Computer Networks, vol. 3, pp. 267-286, September 1979.
• 30: J. Rexford , J. Dolter , Wu-Chang Feng , K. G. Shin, PP-MEss-SIM: a simulator for evaluating multicomputer interconnection networks, Proceedings of the 28th Annual Simulation Symposium, p.84, April 25-28, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  J. Computer Applications

General Terms:
Design, Management, Verification