[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Theory of queuing networks and its applications to the analysis of information-computing systems

  • Published:
Journal of Soviet Mathematics Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

The present survey reflects the main results obtained through 1982 in the theory of queuing networks and some of its applications to the analysis of the productivity of information-computing systems. Special attention is devoted to as complete a description as possible of models of networks for which there exist closed expressions for the stationary distributions. The characteristic properties of such networks are studied, and effective computing algorithms are given for computing the characteristics. A number of approximate methods are presented which are used in analytic modeling of real information-computing systems — networks of data transmission and networks of computers and their components.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Literature cited

  1. O. I. Aven, N. I. Gurin, and Ya. A. Kogan, Quality Estimation and Optimization of Computing Systems [in Russian], Nauka, Moscow (1982).

    Google Scholar 

  2. A. Albert, Regression, Pseudoinversion, and Recurrent Estimation [Russian translation], Nauka, Moscow (1977).

    Google Scholar 

  3. A. A. Amosov, “A model of a distributed system of teleprocessing,” Avtomat. Vychisl. Tekh., No. 4, 22–25 (1981).

    Google Scholar 

  4. G. P. Basharin, “On analytic and numerical methods of investigating commutation systems,” in: Systems of Distribution of Information [in Russian], Nauka, Moscow (1972), pp. 17–32.

    Google Scholar 

  5. G. P. Basharin, L. B. Boguslavskii, and K. E. Samuilov, “On methods of computing capacity of networks of computer communication,” Itogi Nauki i Tekhniki, VINITI, Elektrosvyaz',13, 32–106 (1983).

    Google Scholar 

  6. G. P. Basharin, L. B. Boguslavskii, and V. I. Shteinberg, “Analysis of conflicts in general memory of multiprocessor systems,” Avtomat. Vychisl. Tekh., No. 6, 27–32 (1980).

    Google Scholar 

  7. G. P. Basharin, V. A. Kokotushkin, and V. A. Naumov, “On a method of equivalent replacements for computing fragments of networks of communication for a central computer. I,” Izv. Akad. Nauk SSSR, Tekh. Kibern., No. 6, 92–99 (1979).

    Google Scholar 

  8. G. P. Basharin, V. A. Kokotushkin, and V. A. Naumov, “On a method of equivalent replacements for computing fragments of a network of communication for a central computer. II,” Izv. Akad. Nauk SSSR, Tekh. Kibern., No. 1, 55–61 (1980).

    Google Scholar 

  9. G. P. Basharin, V. A. Kokotushkin, and V. A. Naumov, “The method of equivalent replacements in the theory of teletraffic,” Itogi Nauki i Tekhniki, VINITI, Elektrosvyaz',11, 82–122 (1980).

    Google Scholar 

  10. G. P. Basharin and K. E. Samuilov, “On the optimal structure of buffer memory in networks of data transmission with commutation of packets,” Preprint, Nauch. Sov. Kompleks. Probl. Kibern. Akad. Nauk SSSR, Moscow (1982).

    Google Scholar 

  11. G. P. Basharin and A. L. Tolmachev, “Some results of queuing theory,” Methods of Developing a Theory of Teletraffic [in Russian], Moscow (1979), pp. 52–65.

  12. V. G. Belyakov and Yu. I. Mitrofanov, “On the investigation of closed queuing networks of large size,” Avtom. Telemekh., No. 7, 61–69 (1981).

    Google Scholar 

  13. V. N. Buslenko, Automation of Imitation Modeling of Complex Systems [in Russian], Nauka, Moscow (1977).

    Google Scholar 

  14. Computing Networks. Terminology (Plan), Preprint, Nauch. Sov. po Kompleks. Probl. Kibernet. AN SSSR, Moscow (1981).

    Google Scholar 

  15. R. L. Dobrushin and V. V. Prelov, “The asymptotic approach to the investigation of networks of commutation of communications of linear structure with a large number of nodes,” Probl. Peredachi Inf.,15, No. 1, 61–73 (1979).

    Google Scholar 

  16. R. L. Dobrushin and Yu. M. Sukhov, “Asymptotic investigation of starlike networks of commutation of communications with a large number of radial rays,” Probl. Peredachi Inf.,12, No. 1, 70–94 (1976).

    Google Scholar 

  17. V. A. Zhozhikashvili, R. V. Bilik, V. M. Vishnevskii, and V. G. Vinarskii, “A method of computing buffer memory of a commutation node of communications,” Avtomatika Vychisl. Tekh., No. 5, 67–74 (1977).

    Google Scholar 

  18. V. A. Ivnitskii, “On the condition of independence of the stationary probabilities of states of an open network of single-server systems with losses from the form of the distributions of servicing times,” Izv. Akad. Nauk SSSR, Tekh. Kibern., No. 4, 136–140 (1981).

    Google Scholar 

  19. V. A. Ivnitskii, “On a condition of invariance of the stationary probabilities for queuing networks,” Teor. Veroyatn. Primen.,27, No. 1, 188–192 (1982).

    Google Scholar 

  20. V. N. Kaminskii, “Asymptotic properties of closed network models of computing systems,” in: Vychisl. Sistemy i Kompleksy, Leningrad (1980), pp. 7–12.

  21. V. N. Kaminskii, “Optimization of closed stochastic networks with exponential servicing,” Izv. Akad. Nauk SSSR, Tekh. Kibern., No. 6, 68–76 (1980).

    Google Scholar 

  22. B. A. Kats, “On servicing messages of random length,” in: Teoriya Massovogo Obsluzh., Tr. III Vses. Shkoly-Soveshch. po Teorii Massovogo Obsluzh., Vol. 2, Moscow State Univ. (1976), pp. 157–168.

  23. M. Ya. Kel'bert, “On the existence of limit distributions in some networks of commutation of communications,” in: Multicomponent Random Systems [in Russian], Moscow (1978), pp. 223–241.

  24. M. Ya. Kel'bert, A. Ya. Kreinin, and S. A. Troitskii, “On a class of queuing systems,” Problem. Peredachi Inf.,15, No. 1, 105–107 (1979).

    Google Scholar 

  25. M. Ya. Kel'bert and Yu. M. Sukhov, “On a class of starlike communication networks with packet commutation,” Probl. Peredachi Inf.,15, No. 4, 53–72 (1979).

    Google Scholar 

  26. J. Kemeni and J. Snell, Finite Markov Chains [Russian translation], Nauka, Moscow (1970).

    Google Scholar 

  27. D. König, V. V. Rykov, and F. Schmidt, “Stationary queuing systems with dependences,” Itogi Nauki i Tekhniki, VINITI, Teor. Veroyatn. Mat. Statistika. Teor. Kibernetika,18, 95–186 (1981).

    Google Scholar 

  28. M. Yu. Kitaev, “Queuing systems with Poisson outgoing flow,” Avtomat. Telemekh., No. 11, 40–45 (1980).

    Google Scholar 

  29. L. Kleinrock, Communication Networks. Stochastic Flows and Delays of Communications [Russian translation], Nauka, Moscow (1970).

    Google Scholar 

  30. L. Kleinrock, Computing Systems with Queues [Russian translation], Mir, Moscow (1979).

    Google Scholar 

  31. I. N. Kovalenko, “Queuing theory,” Itogi Nauki i Tekhniki, VINITI, Teor. Veroyatnostei. Mat. Statistika. Teor. Kibernetika (1971), pp. 5–109.

  32. A. Kofman and R. Kryuon, Queuing. Theory and Application [Russian translation], Mir, Moscow (1965).

    Google Scholar 

  33. N. Kristofides, Graph Theory. An Algorithmic Approach [Russian translation], Mir, Moscow (1978).

    Google Scholar 

  34. V. K. Kruglikov, “Application of the diffusion approximation to the investigation of a stochastic network at the level of two moments of the distributions,” in: Vychisl. Sistemy i Kompleksy, Leningrad (1980), pp. 41–47.

  35. S. A. Maiorov, G. I. Novikov, T. I. Aliev, E. I. Makharev, and B. D. Timchenko, Foundations of the Theory of Computing Systems [in Russian], S. A. Maiorov (ed.), Vysshaya Shkola, Moscow (1978).

    Google Scholar 

  36. V. S. Manusevich and N. P. Buslenko, “Imitation modeling of queuing networks,” Methods of Developing a Theory of Teletraffic [in Russian], Nauka, Moscow (1979), pp. 8–18.

    Google Scholar 

  37. Yu. I. Mitrofanov, V. G. Belyakov, and V. Kh. Kurbangulov, “Methods and programming possibilities for analytic modeling of network systems,” Preprint, Nauch. Sov. po Kompleks. Probl. Kibernet. Akad. Nauk SSSR, Moscow (1982).

    Google Scholar 

  38. V. A. Naumov, “On independent operation of subsystems of a complex system,” in: Teoriya Massovogo Obsluzh. Tr. III Vses. Shkoly-Soveshch. po Teorii Massovogo Obsluzh., Vol. 2, Moscow State Univ. (1976), pp. 169–177.

  39. G. I. Novikov and B. D. Timchenko, “Identification of systems of information processing on the basis of stochastic network models,” Vortragsreihe “Theorie und Anwendungen der Informationsverarbeitung,” 27 Int. Wiss. Kolloq. Techn. Hochschule. Ilmenau (1982), pp. 141–144.

  40. P. A. Petrov and A. V. Nikolov, “An analytic model for estimating productivity of multiprocessor computing systems,” Avtomat. Vychisl. Tekh., No. 4, 63–65 (1982).

    Google Scholar 

  41. M. Reiser, “Estimation of the characteristics of systems of data transmission,” TIIER,70, No. 2, 28–59 (1982).

    Google Scholar 

  42. A. N. Rybko, “Stationary distributions of Markov processes homogeneous in time which model communication networks with commutation of messages,” Probl. Peredachi Inf.,17, No. 1, 71–89 (1981).

    Google Scholar 

  43. A. N. Rybko, “Conditions for the existence of a stationary regime for two types of communication networks with commutation of messages,” Probl. Peredachi Inf.,18, No. 1, 94–103 (1982).

    Google Scholar 

  44. V. V. Rykov, “Controllable queuing systems,” Itogi Nauki i Tekhniki, VINITI, Teor. Veroyatnostei. Mat. Statistika. Teor. Kibernetika,12, 43–154 (1975).

    Google Scholar 

  45. S. I. Samoilenko, A. A. Davydov, V. V. Zolotarev, and E. I. Tret'yakova, Computing Networks (Adaptivity, Noise Stability, Reliability) [in Russian], Nauka, Moscow (1981).

    Google Scholar 

  46. V. N. Sachkov, Introduction to Combinatorial Methods of Discrete Mathematics [in Russian], Nauka, Moscow (1982).

    Google Scholar 

  47. D. S. Sil'vestrov, “Averages of attainment times for semi-Markov processes and queuing networks,” Elektron. Informationsverarb. Kybern.,16, No. 8–9, 399–415 (1980).

    Google Scholar 

  48. Yu. M. Sokol, “On an analytic model of conflicts in general memory of multiprocessor systems,” Avtomat. Vychisl. Tekh., No. 4, 66–68 (1982).

    Google Scholar 

  49. A. L. Tolmachev, “Some characteristics of closed exponential networks,” in: Teoriya Teletrafika i Informats. Seti [in Russian], Nauka, Moscow (1977), pp. 3–6.

    Google Scholar 

  50. A. L. Tolmachev, “On dependence on the past of a random walk of messages over a queuing network,” Second School on Automated Queuing Systems [in Russian], Frunze (1980), Texts of reports, Moscow (1980), pp. 24–25.

  51. Proceedings of the Institute of Electronic and Radioelectronic Engineers, TIIER,66, No. 11 (1966).

  52. D. Ferrari, Estimating Productivity of Computing Systems [Russian translation], Mir, Moscow (1981).

    Google Scholar 

  53. M. Schwartz, Computer Networks. Analysis and Planning [Russian translation], Radio i Svyaz', Moscow (1981).

    Google Scholar 

  54. M. A. Shpens, Systems of Distributing Information. Methods of Computation (Handbook), [in Russian], Svyaz', Moscow (1979).

    Google Scholar 

  55. A. Elldin and G. Lind, Foundations of the Theory of Teletraffic [Russian translation], Mir, Moscow (1972).

    Google Scholar 

  56. E. A. Yakubaitis, Architecture of Computing Networks [in Russian], Statistika, Moscow (1980).

    Google Scholar 

  57. S. F. Yashkov, “On the ergodicity of systems with a variable rate of servicing,” Izv. Akad. Nauk SSSR, Tekh. Kibern., No. 3, 83–90 (1981).

    Google Scholar 

  58. T. Altiok, “Approximate analysis of exponential tandem queues with blocking,” Eur. J. Oper. Res.,11, No. 4, 390–398 (1982).

    Article  Google Scholar 

  59. S. Balsamo and G. Iazeolla, “An extension of Norton's theorem for queuing networks,” IEEE Trans. Software Eng.,8, No. 4, 298–305 (1982).

    Google Scholar 

  60. A. D. Barbour, “Networks of queues and method of stages,” Adv. Appl. Probab.,8, No. 3, 584–591 (1976).

    Google Scholar 

  61. A. D. Barbour, “Generalized semi-Markov schemes and open queuing networks,” J. Appl. Probab.,19, No. 2, 469–474 (1982).

    Google Scholar 

  62. A. D. Barbour and R. Schassberger, “Insensitive average residence times in generalized semi-Markov processes,” Adv. Appl. Probab.,13, No. 4, 720–735 (1981).

    Google Scholar 

  63. Y. Bard, “Some extensions to multiclass queuing network analysis,” Perform. Comput. Syst. Amsterdam e.a. (1979), pp. 51–62.

  64. Y. Bard, “A model of shared DASD and multipathing,” Commun. ACM,23, No. 10, 564–572 (1980).

    Article  Google Scholar 

  65. Y. Bard, “Simple approach to system modeling,” Perform. Eval.,1, No. 2, 225–248 (1981).

    Google Scholar 

  66. Y. Bard, “Modeling I/O systems with dynamic path selection and general transmission networks,” Perform. Eval. Rev.,11, No. 4, 118–129 (1982).

    Google Scholar 

  67. Y. Bard and C. H. Sauer, “IBM contributions to computer performance modeling,” IBM J. Res. Develop.,25, No. 5, 562–570 (1981).

    Google Scholar 

  68. F. Baskett, K. M. Chandy, R. R. Muntz, and F. G. Palacios, “Open, closed, and mixed networks of queues with different classes of customers,” J. Assoc. Comput. Mach.,22, No. 2, 248–260 (1975).

    Google Scholar 

  69. F. J. Beutler and B. Melamed, “Decomposition and customer streams of feedback networks of queues in equilibrium,” Oper. Res,26, No. 6, 1059–1072 (1978).

    Google Scholar 

  70. K. Bharath-Kumar, “Discrete-time queuing systems and their networks,” IEEE Trans. Commun.,28, No. 2, 260–263 (1980).

    Article  Google Scholar 

  71. O. J. Boxma and A. G. Konheim, “Approximate analysis of exponential queuing systems with blocking,” Acta Inf.,15, No. 1, 19–66 (1981).

    Article  Google Scholar 

  72. A. Brandwajn, “Further results on equivalence and decomposition in queuing network models,” Perform. Eval. Rev.,9, No. 2, 93–104 (1980).

    Google Scholar 

  73. T. C. Brown and P. K. Pollett, “Some distributional approximations in Markovian queuing networks,” Adv. Appl. Probl.,14, No. 3, 654–671 (1982).

    Google Scholar 

  74. S. C. Bruell and G. Balbo, Computational Algorithms for Closed Queuing Networks, North-Holland (1980).

  75. P. J. Burke, “The output of a queuing system,” Oper. Res.,4, No. 6, 699–704 (1956).

    Google Scholar 

  76. P. J. Burke, “The dependence of sojourn times in tandem M/M/s queues,” Oper. Res.,17, No. 4, 754–755 (1969).

    Google Scholar 

  77. D. Y. Burman, “Insensitivity in queuing systems,” Adv. Appl. Probab.,13, No. 4, 846–859 (1981).

    Google Scholar 

  78. W. Bux, “Modeling and analysis of store-and-forward data switching centers with finite buffer memory and acknowledgment signalling,” Proc. 8th ITC, Melbourne (1976), pp. 524.1–524.6.

  79. J. P. Buzen, “Computational algorithms of closed queuing networks with exponential servers,” Commun. ACM,16, No. 9, 527–531 (1973).

    Article  Google Scholar 

  80. K. M. Chandy, U. Herzog, and L. Woo, “Parametric analysis of queuing networks,” IBM J. Res. Develop.,19, No. 1, 36–42 (1975).

    Google Scholar 

  81. K. M. Chandy, U. Herzog, and L. Woo, “Approximate analysis of general queuing networks,” IBM J. Res. Develop.,19, No. 1, 43–49 (1975).

    Google Scholar 

  82. K. M. Chandy, J. H. Howard, Jr., and D. F. Towsley, “Product form and local balance in queuing networks,” J. Assoc. Comput. Mach.,24, No. 2, 250–263 (1977).

    Google Scholar 

  83. K. M. Chandy and D. Neuse, “Linearizer: a heuristic algorithm for queuing network models of computing systems,” Commun. ACM,25, No. 2, 126–134 (1982).

    Article  Google Scholar 

  84. K. M. Chandy and C. H. Sauer, “Computational algorithms for product form queuing networks,” Commun. ACM,23, No. 10, 573–583 (1980).

    Article  Google Scholar 

  85. A. Chang and S. S. Lavenberg, “Work rates in closed queuing networks with general independent servers,” Oper. Res.,22, No. 4, 838–847 (1974).

    Google Scholar 

  86. A. Chatterjee, N. D. Georganas, and P. K. Verma, “Analysis of packet switched network with end-to-end congestion control and random routing,” IEEE Trans. Commun.,25, No. 12, 1485–1489 (1977).

    Article  Google Scholar 

  87. W. W. Chin and W. M. Chow, “A performance model of MVS,” IBM Systems J.,17, No. 4, 444–462 (1978).

    Google Scholar 

  88. J. W. Cohen, “The multiple phase service network with generalized processor sharing,” Acta Inf.,12, No. 3, 245–284 (1979).

    Google Scholar 

  89. Commuting Surveys,10, No. 3 (1978).

  90. P. J. Courtois, Decomposability, Queuing and Computer System Applications, Academic Press, New York (1977).

    Google Scholar 

  91. T. Czachorski, “Siec stanowisk obslugi jako matematyczny model zlozonego systemu komputerowego,” Podst. Sterow.,6, No. 3, 257–275 (1976).

    Google Scholar 

  92. H. Daduna, “Passage times for overtake-free paths in Gordon-Newell networks,” Adv. Appl. Probab.,14, No. 3, 672–686 (1982).

    Google Scholar 

  93. P. J. Denning and J. P. Buzen, “The operational analysis of queuing network models,” Comput. Surv.,10, No. 3, 225–261 (1978).

    Article  Google Scholar 

  94. D. L. Eager and K. C. Sevcik, “Performance bound hierarchies for queuing networks,” Perform. Eval. Rev.,11, No. 4, 213–214 (1982).

    Google Scholar 

  95. F. G. Foster and H. G. Perros, “Hierarchical queue networks with partially shared servicing,” J. Oper. Res. Soc.,30, 157–166 (1979).

    Google Scholar 

  96. F. G. Foster and H. G. Perros, “Queue networks with blocking: exact and approximate results,” Operating Syst.: Theory and Practice, Amsterdam e.a. (1979), pp. 167–179.

  97. F. G. Foster and H. G. Perros, “On the blocking process in queue networks,” Eur. J. Oper. Res.,5, No. 4, 276–283 (1980).

    Article  Google Scholar 

  98. P. Franken, D. Konig, U. Arndt, and V. Schmidt, Queues and Point Processes, Akademie-Verlag, Berlin (1981).

    Google Scholar 

  99. D. P. Gaver and G. S. Shedler, “Processor utilization in multiprogramming systems via diffusion approximations,” Oper. Res.,21, No. 2, 569–576 (1973).

    Google Scholar 

  100. D. P. Gaver and G. S. Shedler, “Approximate models for processor utilization in multiprogrammed computer systems,” SLAM J. Comput.,2, No. 3, 183–192 (1973).

    Article  Google Scholar 

  101. E. Gelenbe, “On approximate computer system models,” Comput. Archit. Networks, Amsterdam-Oxford (1974), pp. 187–206.

  102. E. Gelenbe, “Probabilistic models of computer systems. Part II: Diffusion approximations, waiting times and batch arrivals,” Acta Inf.,12, No. 4, 285–303 (1979).

    Article  Google Scholar 

  103. E. Gelenbe and I. Mitrani, Analysis and Synthesis of Computer Systems, Academic Press, London (1980).

    Google Scholar 

  104. E. Gelenbe and R. R. Muntz, “Probabilistic models of computer systems. Part I (exact results),” Acta Inf.,7, No. 1, 35–60 (1976).

    Article  Google Scholar 

  105. E. Gelenbe and G. Pujolle, “The behavior of a single queue in a general queuing network,” Acta Inf.,7, No. 2, 123–136 (1976).

    Article  Google Scholar 

  106. B. W. Gnedenko and D. König (eds.), Handbuch der Bedienungstheorie, Band 1, Akad.-Verlag, Berlin (1982).

    Google Scholar 

  107. B. W. Gnedenko and D. König, Handbuch der Bedienungstheorie, Band 2, Akad.-Verlag, Berlin (1983).

    Google Scholar 

  108. G. H. Gonnet and D. E. Morgan, “Analysis of closed queuing networks with periodic servers,” IEEE Trans. Software Eng.,5, No. 6, 653–659 (1979).

    Google Scholar 

  109. K. D. Gordon and L. W. Dowdy, “The impact of certain parameter estimation errors in queuing network models,” Perform. Eval. Rev.,9, No. 2, 3–9 (1980).

    Google Scholar 

  110. W. J. Gordon and G. F. Newell, “Closed queuing systems with exponential servers,” Oper. Res.,15, No. 2, 254–265 (1967).

    Google Scholar 

  111. B. Halachmi and W. R. Franta, “A diffusion approximation to the multiserver queue,” Manag. Sci.,24, No. 5, 522–529 (1978).

    Google Scholar 

  112. J. M. Harrison and A. J. Lemoine, “A note on networks of infinite-server queues,” J. Appl. Probab.,18, No. 2, 561–567 (1981).

    Google Scholar 

  113. P. G. Harrison, “Transient behavior of queuing networks,” J. Appl. Probab.,18, No. 2, 482–490 (1981).

    Google Scholar 

  114. W. E. Helm and R. Schassberger, “Insensitive generalized semi-Markov schemes with point process input,” Math. Oper. Res.,7, No. 1, 129–138 (1982).

    Google Scholar 

  115. J. C. Hershey, E. N. Weiss, and M. A. Cohen, “A stochastic service network model with application to hospital facilities,” Oper. Res.,29, No. 1, 1–22 (1981).

    Google Scholar 

  116. A. Hordijk and R. Schassberger, “Weak convergence for generalized semi-Markov processes,” Stochast. Process. Appl.,12, No. 3, 271–291 (1982).

    Article  Google Scholar 

  117. D. L. Iglehart and G. S. Shendler, “Regenerative simulation of response times in networks of queues with multiple job types,” Acta Inf.,12, No. 2, 159–175 (1979).

    Google Scholar 

  118. D. L. Iglehart and G. S. Shendler, “Simulation of response times in network queues,” Lect. Notes Control Inf. Sci.,26, Springer-Verlag, New York (1980).

    Google Scholar 

  119. D. L. Iglehart and G. S. Shendler, “Regenerative simulation of response times in networks of queues: statistical efficiency,” Acta Inf.,15, No. 4, 347–363 (1981).

    Google Scholar 

  120. M. Irland, “Buffer management in a packet switch,” IEEE Trans. Comput.,C26, No. 3, 328–337 (1978).

    Google Scholar 

  121. J. R. Jackson, “Networks of waiting lines,” Oper. Res.,5, No. 4, 518–521 (1957).

    Google Scholar 

  122. J. R. Jackson, “Jobshoplike queuing systems,” Manag. Sci.,10, No. 1,. 131–142 (1963).

    Google Scholar 

  123. R. R. P. Jackson, “Queuing systems with phase type service,” Oper. Res. Q.,5, No. 4, 109–120 (1954).

    Google Scholar 

  124. P. A. Jacobson and E. D. Lazowska, “Analyzing queuing networks with simultaneous resource possession,” Commun. ACM,25, No. 2, 142–151 (1982).

    Article  Google Scholar 

  125. U. Jansen and D. König, “Insensitivity and steady-state probabilities in product form queuing networks,” Elektron. Inf. Kybern.,16, No. 8–9, 385–397 (1980).

    Google Scholar 

  126. F. Kamoun and L. Kleinrock, “Analysis of shared finite storage in a computer network node environment under general traffic conditions,” IEEE Trans. Comput.,C28, No. 7, 992–1003 (1980).

    Google Scholar 

  127. F. P. Kelly, “Networks of queues with customers of different types,” J. Appl. Probab.,12, No. 3, 542–554 (1975).

    Google Scholar 

  128. F. P. Kelly, “Networks of queues,” Adv. Appl. Probab.,8, No. 2, 416–432 (1976).

    Google Scholar 

  129. F. P. Kelly, Reversibility and Stochastic Networks, Wiley, New York (1979).

    Google Scholar 

  130. M. G. Kienzle and K. C. Sevcik, “Survey of analytic queuing network models of computer systems,” Perform. Eval. Rev.,8, No. 3, 113–129 (1979).

    Google Scholar 

  131. H. Kobayashi, “Application of the diffusion approximation to queuing networks. I. Equilibrium queue distributions,” J. Assoc. Comput. Mach.,21, No. 2, 316–328 (1974).

    Google Scholar 

  132. H. Kobayashi, “Application of the diffusion approximation to queuing networks. II. Nonequilibrium distributions and applications to computer modeling,” J. Assoc. Comput. Mach.,21, No. 3, 459–469 (1974).

    Google Scholar 

  133. H. Kobayashi, Modeling and Analysis. An Introduction to System Performance Evaluation Methodology, Addison-Wesley, Reading (1978).

    Google Scholar 

  134. H. Kobayashi, “A computational algorithm for queue distribution via the Polya theory of enumeration,” Perform. Comput. Syst., Amsterdam e. a. (1979), pp. 79–88.

  135. H. Kobayashi and A. G. Konheim, “Queuing models for computer communications system analysis,” IEEE Trans. Commun.,25, No. 1, 2–29 (1977).

    Article  Google Scholar 

  136. A. G. Konheim and M. Reiser, “A queuing model with finite waiting room and blocking,” J. Assoc. Comput. Mach.,23, No. 2, 328–341 (1976).

    Google Scholar 

  137. D. König and U. Jansen, “Eine Invarianzeigenschaft zufälliger Bedienungsprozesse mit positiven Geschwindigkeiten,” Math. Nachr.,70, 321–364 (1975).

    Google Scholar 

  138. P. S. Kritzinger, S. van Wyk, and A. E. Krzesinski, “A generalization of Norton's theorem for multiclass queuing networks,” Perform. Eval.,2, No. 2, 98–107 (1982).

    Article  Google Scholar 

  139. P. J. Kuehn, “Approximate analysis of general queuing networks by decompositions,” IEEE Trans. Commun.,27, No. 1, 113–126 (1979).

    Article  Google Scholar 

  140. J. Labetoulle and G. Pujolle, “Isolation method in a network of queues,” IEEE Trans. Software Eng.,6, No. 4, 373–381 (1980).

    Google Scholar 

  141. J. Labetoulle, G. Pujolle, and C. Soula, “Stationary distributions of flows in Jackson networks,” Math. Oper. Res.,6, No. 4, 373–381 (1980).

    Google Scholar 

  142. S. S. Lam, “Queuing networks with population size constraints,” IBM J. Res. Develop.,21, No. 4, 370–378 (1977).

    Google Scholar 

  143. S. S. Lam, “An extension of Moore's result for closed queuing networks,” IBM J. Res. Develop.,21, No. 4, 384–387 (1977).

    Google Scholar 

  144. S. S. Lam, “Dynamic scaling and growth behavior of queuing network normalization constants,” J. Assoc. Comput. Mach.,29, No. 2, 492–513 (1982).

    Google Scholar 

  145. S. S. Lam and J. W. Wong, “Queuing network models of packet switching networks. Part 2: Networks with population size constraints,” Perform. Eval.,2, No. 3, 161–180 (1982).

    Article  Google Scholar 

  146. S. S. Lavenberg, “Queuing analysis of a multiprogrammed computer system having a multilevel storage hierarchy,” SIAM J. Comput.,2, No. 4, 232–252 (1973).

    Article  Google Scholar 

  147. S. S. Lavenberg and M. Reiser, “Stationary state probabilities at arrival instants for closed queuing networks with multiple type of customers,” J. Appl. Probab.,17, No. 4, 1048–1061 (1980).

    Google Scholar 

  148. E. D. Lasowska and J. Zahorjan, “Multiple class memory constrained queuing networks,” Perform. Eval. Rev.,11, No. 4, 130–140 (1982).

    Google Scholar 

  149. A. J. Lemoine, “Networks of queues. A survey of equilibrium analysis,” Manag. Sci.,24, No. 4, 464–481 (1977).

    Google Scholar 

  150. A. J. Lemoine, “Networks of queues. A survey of weak convergence results,” Manag. Sci.,24, No. 11, 1175–1193 (1978).

    Google Scholar 

  151. A. J. Lemoine, “On total sojourn time in networks of queues,” Manag. Sci.,25, No. 10, 1034–1035 (1979).

    Google Scholar 

  152. L. Lipsky, “A study of time sharing systems considered as queuing networks of exponential servers,” Comput. J.,23, No. 4, 290–297 (1980).

    Article  Google Scholar 

  153. R. A. Marie, “An approximate analytical method for general queuing networks,” IEEE Trans. Software Eng.,5, No. 5, 530–538 (1979).

    Google Scholar 

  154. R. A. Marie, “Calculation of equilibrium probabilities for λ(n)/Ck/1/N queues,” Perform. Eval. Rev.,9, No. 2, 117–125 (1980).

    Google Scholar 

  155. R. A. Marie, P. M. Snyder, and W. J. Stewart, “Extensions and computational aspects of an iterative method,” Perform. Eval. Rev.,11, No. 4, 186–194 (1982).

    Google Scholar 

  156. K. Matthes, “Zur Theorie der Bedienungsprozesse,” Trans. 3rd Prague Conf. Inform. Theory, Statist. Decision Functions, Random Process, Prague (1962), Prague (1964), pp. 513–528.

  157. B. Melamed, “On Poisson traffic processes in discrete-state Markovian systems with applications to queuing theory,” Adv. Appl. Probab.,11, No. 1, 218–229 (1979).

    Google Scholar 

  158. B. Melamed, “Characterizations of Poisson traffic streams in Jackson queuing networks,” Adv. Appl. Probab.,11, No. 2, 422–438 (1979).

    Google Scholar 

  159. B. Melamed, “On the reversibility of queuing networks,” Stochast. Process. Appl.,13, No. 2, 227–234 (1982).

    Article  Google Scholar 

  160. B. Melamed, “On Markov jump processes imbedded at jump epochs and their queuingtheoretic applications,” Math. Oper. Res.,7, No. 1, 111–128 (1982).

    Google Scholar 

  161. B. Melamed, “Sojourn times in queuing networks,” Math. Oper. Res.,7, No. 2, 223–244 (1982).

    Google Scholar 

  162. I. Mitrani, “A critical note on a result of Lemoine,” Manag. Sci., 25, No. 10, 1026–1027 (1979).

    Google Scholar 

  163. F. R. Moore, “Computational model of a closed queuing network with exponential servers,” IBM J. Res. Develop.,16, No. 6, 567–572 (1972).

    Google Scholar 

  164. J. A. Morrison, “A combinatorial lemma and its application to concentrating trees of discrete-time queues,” Bell System Techn. J.,57, No. 5, 1645–1652 (1978).

    Google Scholar 

  165. R. R. Muntz, “Poisson departure process and queuing networks,” Proc. 7th Ann. Princeton Conf. on Information Sciences and Systems, Princeton, New Jersey, March (1973), pp. 435–550.

  166. D. Neuse and K. M. Chandy, “HAM: The heuristic aggregation method for solving general closed queuing network models of computer systems,” Perform. Eval. Rev.,11, No. 4, 195–212 (1982).

    Google Scholar 

  167. A. S. Noetzel, “A generalized queuing discipline for product form network solutions,” J. Assoc. Comput. Mach.,26, No. 4, 779–793 (1979).

    Google Scholar 

  168. H. G. Perros, “A two-level open queue network with blocking and feedback,” RAIRO. Rech. Oper.,15, No. 1, 27–38 (1981).

    Google Scholar 

  169. H. G. Perros, “A symmetrical exponential open queue network with blocking and feedback,” IEEE Trans. Software Eng.,7, No. 4, 395–402 (1981).

    Google Scholar 

  170. B. Pittel, “Closed exponential networks of queues with saturation, the Jackson-type stationary distribution and its asymptotic analysis,” Math. Oper. Res.,4, No. 4, 357–378 (1979).

    Google Scholar 

  171. M. Reiser, “Numerical methods in separable queuing networks,” TIMS Studies Management Sci.,7, 113–142 (1977).

    Google Scholar 

  172. M. Reiser, “Mean value analysis of queuing networks. A new look at an old problem,” 4th Int. Symp. Modell. and Perform. Eval. Comput. Syst., Vienna, 1979, Conf. Prepr., Vol. 1, pp. 63–77.

  173. M. Reiser, “Mean-value analysis and convolution method for queue-dependent servers in closed queuing networks,” Perform. Eval.,1, No. 1, 7–18 (1981).

    Article  Google Scholar 

  174. M. Reiser and H. Kobayashi, “Accuracy of the diffusion approximation for some queuing systems,” IBM J. Res. Develop.,18, No. 2, 110–124 (1974).

    Google Scholar 

  175. M. Reiser and H. Kobayashi, “Queuing networks with multiple closed chains: theory and computational algorithms,” IBM J. Res. Develop.,19., No. 3, 283–294 (1975).

    Google Scholar 

  176. M. Reiser and H. Kobayashi, “Horner's rule for the evaluations of general closed queuing networks,” Commun. ACM,18, No. 10, 592–593 (1975).

    Article  Google Scholar 

  177. M. Reiser and S. S. Lavenberg, “Mean value analysis of closed multichain queuing networks,” J. Assoc. Comput. Mach.,27, No. 2, 313–322 (1980).

    Google Scholar 

  178. M. Reiser and S. S. Lavenberg, “Corrigendum to [177]“,” J. Assoc. Comput. Mach.,28, No. 3, 629 (1980).

    Google Scholar 

  179. C. L. Samelson and W. G. Bulgren, “A note on product-form solution for queuing networks with Poisson arrivals and general service-time distributions with finite means,” J. Assoc. Comput. Mach.,29, No. 3, 830–840 (1982).

    Google Scholar 

  180. C. H. Sauer, “Approximate solution of queuing networks with simultaneous resource possession,” IBM J. Res. Develop.,25, No. 6, 894–903 (1981).

    Google Scholar 

  181. C. H. Sauer and K. M. Chandy, “Approximate solution of queuing models,” Computer,13, No. 4, 25–31 (1980).

    Google Scholar 

  182. C. H. Sauer and K. M. Chandy, Computer System Performance Modeling: A Primer, Prentice-Hall, Englewood Cliffs, New Jersey (1981).

    Google Scholar 

  183. C. H. Sauer and E. A. MacNair, “Queuing networks software for systems modeling,” Software Pract. Exper.,9, No. 5, 107–128 (1979).

    Google Scholar 

  184. C. H. Sauer, E. A. MacNair, and S. Salza, “A language for extended queuing network models,” IBM J. Res. Develop.,24, No. 6, 747–755 (1980).

    Google Scholar 

  185. R. Schassberger, “Insensitivity of steady-state distributions of generalized semi-Markov processes with speeds,” Adv. Appl. Probab.,20, No. 4, 836–851 (1978).

    Google Scholar 

  186. R. Schassberger, “The insensitivity of stationary probabilities in networks of queues,” Adv. Appl. Probab.,10, No. 4, 906–912 (1978).

    Google Scholar 

  187. R. Schassberger, “Mathematische Probleme aus der Theorie verzweigter Bedienungs-systeme,” Ber. Math.-Statist. Sek. Forschungszent. Graz., No. 121–132, 125/1–125/30 (1980).

    Google Scholar 

  188. K. C. Sevcik and I. Mitrani, “The distribution of queuing network states at input and output instants,” J. Assoc. Comput. Mach.,28, No. 2, 358–371 (1981).

    Google Scholar 

  189. G. S. Shedler and D. R. Slutz, “Irreducibility in closed multiclass networks of queues with priorities. Passage times of a marked job,” Perform. Eval.,1, No. 3, 334–343 (1981).

    Google Scholar 

  190. G. S. Shedler and J. Southard, “Regenerative simulation of networks of queues with general service times, Passage through subnetworks,” IBM J. Res. Develop.,26, No. 5, 625–633 (1982).

    Google Scholar 

  191. B. Simon and R. D. Foley, “Some results on sojourn times in acyclic Jackson networks,” Manag. Sci.,25, No. 10, 1027–1034 (1979).

    Google Scholar 

  192. J. R. Spirn, “Queuing networks with random selection for service,” IEEE Trans. Software Eng.,5, No. 3, 287–289 (1979).

    Google Scholar 

  193. W. J. Stewart, “A comparison of numerical techniques in Markov modeling,” Commun. ACM,21, No. 2, 144–152 (1978).

    Article  Google Scholar 

  194. W. J. Stewart, “A direct numerical method for queuing networks,” Perform. Comput. Syst. Amsterdam e. a. (1979), pp. 89–102.

  195. W. J. Stewart and G. A. Zeisler, “On the existence of composite flow equivalent markovian servers,” Perform. Eval. Rev.,9, No. 2, 105–166 (1980).

    Google Scholar 

  196. D. Towsley, “Queuing network models with state-dependent routing,” J. Assoc. Comput. Mach.,27, No. 2, 323–337 (1980).

    Google Scholar 

  197. K. S. Trivedi and R. A. Wagner, “A decision model for closed queuing networks,” IEEE Trans. Software Eng.,5, No. 4, 328–332 (1979).

    Google Scholar 

  198. S. Tucci and E. A. MacNair, “Implementation of mean-value analysis for open, closed, and mixed queuing networks,” Comput. Perform.,3, No. 4, 233–239 (1982).

    Google Scholar 

  199. H. Vantilborgh, “Exact aggregation in exponential queuing networks,” J. Assoc. Comput. Mach.,25, No. 4, 620–629 (1978).

    Google Scholar 

  200. H. Vantilborgh, R. L. Garner, and E. D. Lazowska, “Near-complete decomposability of queuing networks with clusters of strongly interacting servers,” Perform. Eval. Rev.,9, No. 2, 81–92 (1980).

    Google Scholar 

  201. J. Walrand, “Filtering formulas and the ·/M/1 queue in a quasireversible network,” Stochastics,6, No. 1, 1–22 (1981).

    Google Scholar 

  202. J. Walrand, “On the equivalence of flows in networks of queues,” J. Appl. Probab.,19, No. 1, 195–203 (1982).

    Google Scholar 

  203. J. Walrand, “Poisson flows in single class open networks of quasireversible queues,” Stochast. Process. Appl.,13, No. 3, 293–303 (1982).

    Article  Google Scholar 

  204. J. Walrand and P. Varaiya, “Flows in queuing networks: a martingale approach,” Math. Oper. Res.,6, No. 3, 387–404 (1981).

    Google Scholar 

  205. J. Walrand and P. Varaiya, “Sojourn times and the overtaking condition in Jacksonian networks,” Adv. Appl. Probab.,12, No. 4, 1000–1018 (1980).

    Google Scholar 

  206. J. Walrand and P. Varaiya, “Interconnections of Markov chains and quasireversible queuing networks,” Stochast. Process. Appl.,10, No. 2, 209–219 (1980).

    Article  Google Scholar 

  207. A. C. Williams and R. A. Brandiwad, “A generating function approach to queuing network analysis of multiprogrammed computers,” Networks,6, No. 1, 1–22 (1976).

    MathSciNet  Google Scholar 

  208. J. W. Wong and S. S. Lam, “Queuing network models of packet switching networks. Part 1: Open networks,” Perform. Eval.,2, No. 1, 9–21 (1982).

    Article  Google Scholar 

  209. J. Zahorjan, K. C. Sevcik, D. L. Eager, and B. Galler, “Balanced job bound analysis of queuing networks,” Commun. ACM,25, No. 2, 134–141 (1982).

    Article  Google Scholar 

Download references

Authors
  1. G. P. Basharin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. L. Tolmachev
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Translated from Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 21, pp. 3–119, 1983.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Basharin, G.P., Tolmachev, A.L. Theory of queuing networks and its applications to the analysis of information-computing systems. J Math Sci 29, 951–1050 (1985). https://doi.org/10.1007/BF02104830

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02104830

Keywords

Search

Navigation