Invariance Properties Of Queueing Networks And Their Application To Computer/Communications Systems

Abstract

During the past decade there has been a quantitative leap in the development of queueing theory as it relates to the design, control, and operation of computer communications systems. Much of the research centres on the so-called “product form solution” of the network state probabilities. This, in turn, has led to the discovery, in many specific cases, that the state probabilities are invariant with respect to the form of the service time distribution. No systematic investigation of this invariance has appeared in tJie computer/communications literature as of this date. Our main objectives in this paper, therefore, are to describe and define the class of queueing models which has this invariance property and to demonstrate that almost all such models have a common basis. The theoretical foundation for the classification of invariance (developed by Kovalenko (19, 20) and, independently, by Konig (17)) has not received much recognition. In this paper, Kovalenko’s main theorem is stated, the required conditions for invariance are explained, and examples of solutions which can be derived quite easily from the theorem are given. The connection between the invariance property and the product form of the state probabilities is demonstrated. Finally, two extensions of Kovalenko’s theorem are presented; one by Guseinov (10) and one by the authors.

Résumé

Durant la dernière décennie, des développements appréciables ont eu lieu dans la modélisation, le controle et la mise en fonction de systèmes informatisés de communication en théorie des files d’attente. Les efforts de recherche ont surtout été concentres sur la solution en “forme de produit” du réseau probabiliste des états du systéme. Ces efforts ont permis de découvrir que, pour plusieurs cas particuliers, les probabilités des états ne varient pas avec la forme de la distribution du temps de service. A ce jour, aucune investigation systématique de cette invariance n’est apparue dans la littérature informatique/communication. Notre but principal dans cet article est done de décrire et de définir l’ensemble des modèles de files d’attente qui ont cette propriété d’invariance et de démontrer que la plupart de ces modèles ont une base commune. La base théorique de cette propriété d’invariance (qui fut développée par Kovalenko et, de façon independante, par König) n’a pas reçu tellement de reconnaissance. Dans cet article, le téorême principal de Kovalenko est présente, les conditions requises pour l’invariance sont expliquées, et quelques exemples de solutions, faciles à obtenir à partir du théortême, sont donnès. Nous démontrons aussi l’existence d’un lien entre la propriété d’invariance et la “forme de produit” des probabilités des états. Finalement, deux extensions du théorême de Kovalenko sont présentées; l’une par Guseinov et l’autre par les auteurs.

Additional information

Notes on contributors

Isaac Dukhovny

ISAAC M. DUKHOVNY was born in Zhitomir, ussR, on 10 July 1939. He received the MS (mathematics) degree from Moscow State University and PHD in mathematics from Moscow Lumumba University in 1965 and 1970, respectively. From February 1970 to 1973 he was a junior scientific researcher at the Tetetraffic Department, Institute for Information Transmission Probtems, Moscow. From 1973 untit 1979, he was a senior scientific researcher at the Computer Centers Network Department of ttie Institute of Central Statistical Boards of the ussR, Moscow. Since September 1979 he has been a senior systems programmer of the Data Networtc Systems Department, Bantc of America, San Francisco. His principat research interests are in the fietd of probabitity theory, queueing theory, mathematicat statistics, and teletraffic. He is a co-author of the book Priority queueing models for computer-communications systems (Moscow “Nauka,” 1976).

Ernest Koenigsberg

ERNEST KOENIGSBERG is a New Yorker by birth and a San Franciscan by adoption. He received the BA (physics) degree from New York University in 1948 and the PHD (theoretical physics) degree from Iowa State University in 1953. He has been active in Operations Research since 1955, serving as the head of OR groups at EMI Research and Development Ltd., Midwest Research Institute and Touche, Ross, and as senior vice president and technical director of Matson Research Corp. and Manatytics Inc. He has been teaching Operations Research since 1962 at the University of California, Berkeley, where he is now a senior member of the facutty of the School of Business. Dr Koenigsberg is an associate editor of INFOR.