Browse Prior Art Database

APPROXIMATION ANALYSIS OF GENERAL QUEUEING NETWORKS

IP.com Disclosure Number: IPCOM000148482D
Original Publication Date: 1974-Jul-15
Included in the Prior Art Database: 2007-Mar-30

Publishing Venue

Software Patent Institute

Related People

Chandy, K.M.: AUTHOR [+4]

Abstract

IS OF GENERAL QUEUEING NETWORKS K. M. Chandy*, U. Herzog** and I,. Woo IBM Thomas J. Watson Research CenterYorktown Heights, New York 10598ABSTRACT: An approximate iterative technique for the analysis of complex queueing networks with general service times is presented. The technique is based on Norton's theorem for queueing networks which obey local balance. The technique determines approximations of the queue length and wait time distributiorls of each queue in the network. Com- parison of results obt.ained by the approximate method with simulated and exact results show that the approximate method has reasonable accuracy.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 28

IS OF GENERAL QUEUEING NETWORKS
K. M. Chandy*, U. Herzog** and I,. Woo

IBM Thomas J. Watson Research Center
Yorktown Heights, New York 10598
ABSTRACT: An approximate iterative technique for the
analysis of complex queueing networks with general service
times is presented. The technique is based on Norton's
theorem for queueing networks which obey local balance. The
technique determines approximations of the queue length and
wait time distributiorls of each queue in the network. Com-
parison of results obt.ained by the approximate method with
simulated and exact results show that the approximate method
has reasonable accuracy.

* On leave from the University of Texas at Austin.

** On leave from the University of Stuttgart, West Germany.

APPROXIMATE ANALY S

RC 4931

(1l21910)

July 15, 1974
Computer

Sciences

[This page contains 1 picture or other non-text object]

Page 2 of 28

LIMITED DISTRIBUTION NOTICE

This report has been submitted for publication elsewhere and has been issued as a Research Report for early disserni~ation of its contents. As a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.

Copies may be requested from:
ZBM Thomas J. Watson Research Center Post Office Box 218
Yorktown Heights, New York 10598

[This page contains 1 picture or other non-text object]

Page 3 of 28

1. Introduction
Queueing network models have been widely used in the analysis of computer
systems and teleprocessing networks [l] and 121. However, efficient compu-
tational techniques for analyzing complex networks are limited to problems
which satisfy local balance (31. Efficient methods for the analysis of
specific networks which do not satisfy local balance exist; see for instance

[4]. Approximating a general network by one which satisfies local balance
usually results in unacceptable error for computer systems analysis.

    Green and Tang [61 suggest that systems analysis techniques which
require modest computation time and give results accurate to around 10% or
20% are adequate for the configuration phase of teleprocessing network
design; subsequent phases may deal with more detailed, more accurate and
more expensive techniques. The present work is concerned with the configu-
ration phase.

    This paper presents an approximate, iterative method for determining
performance values for closed queueing networks with first-come-first-served
discipline and general service times. The method is a direct application
of Norton's theorem [7], and it gives exact solutions for networks which
satisfy local balance. The method may be extended to networks with other
disciplines and also to several classes of customers.

    In the next section (section 21, some concepts related to Norton's
theorem are developed. The algorithm is presented in section 3; the
algorithm is illustrated by means of an example in Appendix 1. In secti...