Design automation and queueing networks: An interactive system for the evaluation of computer queueing models

ABSTRACT

Design automation techniques have been successfully used in wiring board layouts, circuit design analysis, and other areas. Simulation techniques have been used by system analysts to evaluate complex computer systems. In the early stages of a computer system design a designer will find an interactive package, which gives him real-time solutions for queueing models of complex computer systems, extremely useful. In the first few passes at a design, detailed simulation studies are too expensive and too slow. A conversational package which evaluates arbitrary configurations and gives approximate results is preferable to a slow, expensive, though accurate simulation. This paper is concerned with the real-time analysis of complex queueing network models which have been extensively used in computer systems analysis. In this paper we present the theory, algorithms and some programs for a system which departs radically from previous attempts at computer design aids for queueing network analysis in two ways: firstly the design automation system proposed here will give both algebraic and numerical answers to queries put forward by the analyst. For instance, the analyst may want to find out an algebraic expression for the throughput of a network as a function of several parameters. Or the analyst may want the output in the form of a graph of throughput as a function of a parameter. The system discussed in this paper will satisfy both types of requests. Secondly, the system allows the analyst to evaluate arbitrary networks constructed from a set of specified “building blocks.” The “building blocks” are quite general—they include queues with devices (servers), branches, joins, and so on. The analyst is allowed to use as many building blocks as he pleases, and he can interconnect these building blocks in any pattern he chooses. Thus the system is moderately flexible and allows the analyst greater freedom in choosing the models best suited for his system.

REFERENCES

• 1: F. Baskett and F. P. Gomez. Processor sharing in a central server queueing model of multiprogramming with applications, Proc. Of the Sixth Annual Princeton Conference on Information Sciences and Systems, Princeton University, Princeton, N.J. (March 1972).
• 2: F. Baskett. Mathematical models of multiprogrammed computer systems, TSN-17, Computation Center Report, The University of Texas at Austin (January 1971).
• 3: K. M. Chandy. The analysis and solutions for general queueing networks, Proc. of the Sixth Annual Princeton Conference on Information Sciences and Systems, Princeton University, Princeton, N.J. (March 1972).
• 4: Peter J. Denning , Stuart C. Schwartz, Properties of the working-set model, Communications of the ACM, v.15 n.3, p.191-198, March 1972 [doi>10.1145/361268.361281]
• 5: K. B. Irani , V. L. Wallace, On Network Linguistics and the Conversational Design of Queueing Networks, Journal of the ACM (JACM), v.18 n.4, p.616-629, Oct. 1971 [doi>10.1145/321662.321677]
• 6: J. R. Jackson. Jobshop-like queueing systems Man. Sci. Vol. 10, (1963), pp. 131-142.
• 7: Jeffrey Buzen, Analysis of system bottlenecks using a queueing network model, Proceedings of the SIGOPS workshop on System performance evaluation, p.82-103, January 1971 [doi>10.1145/800024.808355]
• 8: J. Buzen, Queueing network models of multiprogramming. Ph.D. Dissertation, Division of Engineering and Applied Physics, Harvard University, Cambridge, Mass. (June 1971).
• 9: W. J. Gordon and G. P. Newell. Closed queueing systems with exponential servers. Operations Research, Vol. 15, No. 2, (April 1967), pp. 254-265.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Design, Theory