Browse Prior Art Database

On the Representation of Markovian Systems by Network Models

IP.com Disclosure Number: IPCOM000128407D
Original Publication Date: 1969-Aug-01
Included in the Prior Art Database: 2005-Sep-15

Publishing Venue

Software Patent Institute

Related People

Wallace, Victor L.: AUTHOR [+3]

Abstract

Formal, unambiguous mathematical structures are developed for representing Markovian queueing networks and for systematically constructing a description of a continuous- parameter Markov chain model from a description of the network diagram. A formal queueing diagram notation is developed as a pictorial language. An approach to the problem of decomposition and recomposition of Markovian queueing networks is presented, and applied to realistic queueing networks.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 3% of the total text.

Page 1 of 41

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On the Representation of Markovian Systems by Network Models

THE UNIVERSITY OF MICHIGAN Technical Report 21 Victor L. Wallace

CONCOMP: Research in Conversational Use of Computers
F. H. Westervelt, Project Director ORA Project 07449

supported by: ADVANCED RESEARCH PROJECTS AGENCY DEPARTMENT OF DEFENSE WASHINGTON, D. C.

CONTRACT NO. DA-49-083 OSA-3050 ARPA ORDER NO. 716

administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR August 1969

Abstract

Formal, unambiguous mathematical structures are developed for representing Markovian queueing networks and for systematically constructing a description of a continuous- parameter Markov chain model from a description of the network diagram. A formal queueing diagram notation is developed as a pictorial language. An approach to the problem of decomposition and recomposition of Markovian queueing networks is presented, and applied to realistic queueing networks.

Table of Contents

Preface.....vii
List of Figures.....ix
List of Tables.....xi
1. Introduction.....1
2. A Syntax of the Pictorial Language.....5
3. Semantics of the Pictorial Language.....11
4. Defining a Network Model.....27
5. Element Representation.....29
6. The Network as a Markov Chain.....53
7. The Translation of Networks to Equilibrium Equations.....79
References.....112

University of Michigan Page 1 Aug 01, 1969

Page 2 of 41

On the Representation of Markovian Systems by Network Models

Preface

This report treats a general approach to the decomposition and recomposition of Markovian queueing networks. This theory was developed in 1967 as part of a project aiming at providing a computer program to produce transition intensity matrices from a description of the network in block-diagram form automatically by use of a digital computer.

The system which has finally been implemented1 under this project is based upon a gross simplification of the notions presented here, with an attendant reduction in the generality of the networks which may be so treated. Indeed, because of the considerable difficulties which a direct implementation of this theory in such a programming system entails, the simplified theory assumes a distinctly different form.

Nevertheless, this report should be of sufficient interest to its audience both as a progenitor of the notions finally implemented, and as a theoretical development on its own, capable of further theoretical development as part of the long neglected field of queueing networks.

V. L. Wallace

Ann Arbor

List of Figures

2.1 A network diagram.....6
3.1 A "holding server.".....14
3.2 Schematic of port variables.....23
5.1 The arrival element.....31
5.2 The exponential server.....32
5.3 The queue.....39
5.4 The random switch.....44
6.1 Illustrating the "propagation of an epoch.".....65
6.2 An epoch graph fragment corresponding to Fig. 6.1.....66
6.3 Graphs related to the epoch graph.....72
6.4 An epoch graph.....76
7.1 Illustratin...