Rotating combined queueing (RCQ): bandwidth and latency guarantees in low-cost, high-performance networks

ABSTRACT

Network service guarantees not only provide significant performance benefits to distributed computing systems (more balanced resource utilization, fast fault recovery, and fair network access), but they are also essential for many new applications requiring real-time communications with continuous data types (audio/video). Most existing algorithms which provide network service guarantees are too complicated to be feasible in high-speed, low-cost switches for multicomputer networks. The simpler algorithms proposed provide only limited service guarantees or waste significant network resources.We present a novel, cost-effective queueing and scheduling algorithm, called Rotating Combined Queueing (RCQ), which can efficient]y support a range of service guarantees including deterministic delay bounds and bandwidth guarantees in multicomputer networks. By allowing bursty traffic to utilize unused network resources efficiently, RCQ also can provide competitive performance to best-effort data communications. Such cost-effective service guarantees not only provide substantial benefits to the overall system performance, but can also further expand the domain of multicomputer applications to encompass distributed multimedia applications requiring isochronous communications.

REFERENCES

• 1: Ron Buck, nCUBE Corporation: The Oracle Media Server for nCube Massively Parallel Systems, Proceedings of the 8th International Symposium on Parallel Processing, p.670-673, April 01, 1994
• 2: Timothy Callahan , Seth Copen Goldstein, NIFDY: a low overhead, high throughput network interface, Proceedings of the 22nd annual international symposium on Computer architecture, p.230-241, June 22-24, 1995, S. Margherita Ligure, Italy
• 3: H. Chao. A novel architecture for queue management in the ATM network. IEEE Journal on Selected Areas in Commu. nications, 9(7):1110-8, September 1991.
• 4: Cisco Systems, Inc. Advanced Queueing Techniques in the Oiseo iO~q~ 1995. Cisco Systems Wl~_ite Paper available from http ://cio. cisco, com/varp/public/732/gult I/Index. html.
• 5: Gray Research, Inc. Gray T3D System Architecture Overview, March 1993.
• 6: 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]
• 7: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 8: Fore Systems, Inc. ForeThought Bandwidth Management, 1995. Fore Systems Wllite Paper available from ht tp : //vtrg. ~o re. c om/h~ml/produ ctm/vhi'a ep/whir ep. htntl.
• 9: Didier Le Gall, MPEG: a video compression standard for multimedia applications, Communications of the ACM, v.34 n.4, p.46-58, April 1991 [doi>10.1145/103085.103090]
• 10: S. J. Golestani. Congestion-free communication in highspeed packet networks. IEEE Transactions on Communications, 39(12):1802-1812, December 1991.
• 11: Robert W. Horst, TNet: A Reliable System Area Network, IEEE Micro, v.15 n.1, p.37-45, February 1995 [doi>10.1109/40.342016]
• 12: J. Hyman, A. Lazar, and G. PacificJ. Real-time scheduling with quality of service constraints. IEEE Journal on Selected Areas in Communications, 9(7):1052-1063, September 1991.
• 13: Intel Corporation. Paragon XP/S Product Overview, 1991.
• 14: Divyesh Jadav , Alok Choudhary, Designing and Implementing High-Performance Media-on-Demand Servers, IEEE Parallel & Distributed Technology: Systems & Technology, v.3 n.2, p.29-39, June 1995 [doi>10.1109/88.393231]
• 15: 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]
• 16: Vijay Karamcheti , Andrew A. Chien, Software overhead in messaging layers: where does the time go?, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.51-60, October 05-07, 1994, San Jose, California, United States
• 17: M Karol, M. HIuchyj, and S. Morgan. Input versus output queueing on a space-division packet switch. IEEE Transactions on Communications, COM-35(12):1347-1356, December 1987.
• 18: P. Kermani and L. Kleinrock. Virtual cut-through: A new computer connnunlcations switching technique. Computer N~tworks, 3(4):267-86, 1979.
• 19: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 20: Mitsubishi Electronic Devices Group. Data Book for the Mitsubishi M6007x and M6008x Series Gate Array Families, March 1993.
• 21: Y. Ofek and M. Yung. The integrated MetaNet architecture: A switch-based multimedia LAN for parallel computing and real-time traffic. In Proceedings of IEEE INFOCOM, pages 802-811, 1994.
• 22: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks—the single node case, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 2), p.915-924, May 1992, Florence, Italy
• 23: D. Reininger and D. Raychaudhuri. Statistical multiplexing of VBR MPEG compressed video on ATM networks. In Proceedings of IEEE INFOGOM, pages 919-926, 1993.
• 24: Hui Zhang , Srinivasan Keshav, Comparison of rate-based service disciplines, Proceedings of the conference on Communications architecture & protocols, p.113-121, September 03-06, 1991, Zurich, Switzerland
• 25: L. Zhang, Virtual clock: a new traffic control algorithm for packet switching networks, Proceedings of the ACM symposium on Communications architectures & protocols, p.19-29, September 26-28, 1990, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Neural nets

General Terms:
Algorithms, Design, Management