THE UNIVERSITY OF MICHIGAN Technical Report 21 On the Representation of Markovian Systems by Network Models 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. iii

Table of Contents Page Preface vii List of Figures ix List of Tables xi 1. Introduction1 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 v

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 implemented [6, 7] 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 vii

List of Figures Page 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 Illustrating two cases for consolidation. 80 7. 2 Illustrating the "consolidated" networks for Fig. 7. 1. 82 7.3 Schematic of port variables. 85 7. 4 Relationships of port variables in connected elements. 85 7. 5 Illustrating epoch-splitting. 87 7.6 Illustrating epochs and their influence. 89 7. 7 Illustrating epochs and their influence. 92 7. 8 Illustrating externally determined epochs and their 98 influence. 7. 9 Queue-and-server consolidation. 101 ix

List of Tables Page I Semantics of State Variables, Parameters, and Auto-Epochs 17 II Semantics of Input and Output Port Variables 21 III Semantics of Contents Sensing and Value Collecting Ports 22 IV Element Definitions 50 xi

1. INTRODUCTION The Markovian systems of the title are, by definition, systems whose behavior is modeled by a continuous — parameter Markov chain with stationary transition probabilities. A network model, on the other hand, is a model consisting of distinct elements, interconnected through well defined interfaces. Such a model is often represented compactly in the form of a network diagram, consisting of separate elementary symbols and lines between them. The three representations-network diagram, network model, and Markov chain-can be used as three alternative descriptions of the same object, the Markovian system. That is, they can be used as alternative descriptions provided that the network diagram and the network model are formally and unambiguously defined. If they are, then it should also be possible to translate a description in any one of these forms into an equivalent description in any other. It is the purpose of this report to develop formal and unambiguous mathematical structures for both the network diagrams and the network models, and to show how a diagram can be translated into an equivalent Markov chain through intermediate use of these structures. The network model structure will be defined in a form specifically tailored to make this translation convenient. It will represent an algebraic description of the meaning behind the symbols used in the network diagram. The network diagram structure will be defined so that the diagrams will most flexibly and unambiguously approximate the crude, ambiguous (but natural) diagrammatic 1

2 forms used by systems analysts and theorists as visual aids. In this way, the diagrams will offer maximum facility to these people as a means of communication. This work represents a first stage in development of the theoretical machinery required for a graphic man-computer system for Markovian systems analysis. The areas of potential application of this system are potentially many, and include computer systems, communications switching systems, traffic control systems, assembly lines, and reliability studies, (The class of Markovian systems includes all those ordinarily called Markovian queueing systems.) While analysis of a Markov chain can proceed by analytical, numerical, or simulational means, this man-computer system will utilize a numerical analysis procedure based on that of the Recursive Queue Anal2 yzer in order to achieve a good compromise between response time and generality. This is an algorit.hm whxih requires only that the matrix of transition intensities of the Markov charm, "the coefficient matrix of the Kolmogorov differential equat.ion) be know.wno Thu hs thas matrix, together with information identifying states, wl, be considered the basic form, descriptive of the Markov chaino This report has three princlipyal parts. Sections 2 and 3 pose a legitimate picture language format for Markov network diagrams, and abstract a framework for the transfer of meaning from the network diagrams to the algebraic network modelo Sections 4 through 6 develop the algebraic model and treat its relationship to the Markov chaino Because the algebraic model

3 is relatively complicated and abstract, its development is carried through a series of trial models showing, by counterexample, why each new complication is a necessary improvement. Section 7 treats an operation called consolidation and the procedure for translation from the primitive network model to the transition intensity matrix describing the Markov chain.

2. A SYNTAX OF THE PICTORIAL LANGUAGE 2.1 PICTORIAL LANGUAGES Formal representations of Markovian systems in diagram form are actually expressions in a graphical language. More precisely, it is two3 dimensional pictorial language, to use W. R. Sutherland's term. It is a means of conveying precise meaning through pictorial symbols and syntax. Because the representations are descriptive of a problem to be solved rather than of the means of solution, such a language is also called a problemoriented pictorial Janguage.i: The C hief utility of pictorial languages arises from their compactness and from the high degree of instant recognition possible compared with textual languages. 2. 1. 1 An Example Consider, for example, the diagram of Figure 2. lo With suitable definitions, the symbols and syntax of this diagram could have the following meaning: Poisson arrivals of tasks, having mean rate of occurrence X, are accepted into a queue, with up to a maximum of np tasks present in the queue at any one time. A server removes tasks from the queue and processes them for independent, exponentially distributed intervals of time having mean 1/1,. Whenever the two other queues have less than a total of n5 tasks present at the time of a completion, the completed task is randomly assigned to the upper queue (with probability p) or the lower queue (with probability 1-p). Otherwise the service is restarted and the server held for 5

I F X n5 Figure 2. 1 A network diagram.

7 another exponentially distributed interval of time. Tasks assigned to the upper queue are removed from the queue and processed, one at a time, by a server which is held for an independent exponentially distributed period of time having mean 1//2. Upon completion of this holding, the task exits from the system and a new task is immediately drawn from the upper queue, if the queue is not empty. Tasks assigned to the lower queue go to any of n4 servers whenever one of them is vacant. These servers are each held for independent exponentially distributed intervals with mean 1/g3. Every completion produces an exit of a task from the system, and a new task is immediately drawn from the lower queue into the vacated server, if the queue is not empty. 2. 1. 2 The Need for a New Language That, briefly, is the meaning which can be assigned to the diagram of Figure 2. 1, In some senses, that description is incomplete because of the difficulty of systematically conveying all possible conditions and actions in English prose (i. e,, textually). It will be seen later than any questions arising from the ambiguities of the description can be answered when the symbols are adequately defined. The main issue here is that the diagram is clearly a means of description which is superior to proseo It is compact and easy to visualize. At present, no generally accepted pictorial language for the purpose of describing Markovian systems exists. As used by queueing theorists and analysts, diagrams are used as discussion aids rather than as complete

8 symbolic representations. It is not uncommon, for example, for textbooks to use the same diagram for two different systems-the difference being drawn out in the discussion. Thus, these diagrams are usually ambiguous and can't be formally used as prototypes for a picture language. The block4 diagram representations used by some simulator programs are unambiguous, but lack both the conciseness and the flexibility desired. They also are more general than necessary, since they can usually be used to describe many nonMarkovian systems. It is necessary, therefore, to define a pictorial language here which can be used for the purpose. However, rather than define a particular language, a class of languages which differ from one another only in their vocabulary will be defined. In other words, it will not be assumed that fixed set of symbols will be used. Rather, only the means of defining the symbols, and the form of the basic construction of expressions will be prescribed. In this way a "living language" is constructed. Of more practical significance, conciseness is preserved over wide ranges of application when special purpose symbols and syntactic constructions can be invented by a user as needed. This will obviate much of the awkwardness found in the simulation languages, and permit the abbreviation of frequently used constructions, 2. 2 A PROPOSED SYNTAX A network diagram (which is an expression in the picture language) will be characterized by a set of distinct symbols with lines between them.

9 Each symbol has a characteristic shape and a number of special connection points physically located on it. Each connecting point is the end-point of at most one connecting line, and has a specific orientation on the symbol, which identifies it. (Points in Figure 2. 1 which appear to have more than one connecting line are actually small symbols with more than one connecting point. ) Each connecting line has a type (dotted, solid, etc. ) and joins exactly two connecting points. The connecting points also have types, which determine what connections can legally be made. There are four types in use in Figure 2. 1: 1) task transfer-input; 2) task transfer-output; 3) contents sensing; and 4) value collecting. Others are possible, and this is one of the syntactic variables of the languageo In the language of Figure 2.o 1 connections are only permitted between a point of type (!) and a point of type (2), or between a point of type (3) and a point of type (4). The former connection is shown solid, the latter dotted. For simplicity, only this connection syntax will be used in this report, Finally, each symbol has a set of locations for parameters. The orientation of the parameter identifies it and its range (integer, real, etc. )o The parameter may be supplied as any algebraic expression of appropriate range,

10 It will be evident in the next section that the connection syntax is irrelevant to the algebraic model or its translator. It provides only a protection against unintended constructions. An algebraic meaning for the connecting line will always exist, regardless of the point-types involved, but it may represent nonsense if the connection syntax is invalid.

3. SEMANTICS OF THE PICTORIAL LANGUAGE Having established a syntax, which defines the form which Markovian network diagrams may legally take, the meaning which the diagram conveys must be described. This meaning can be awkwardly conveyed in English, as the description of Figure 2. 1 testifies. However, our purpose is to describe this meaning in a formal algebraic form, to enable systematic transfer of this meaning to the description of a Markov chain. In this sense, set and function concepts are used as a meta-language with which to define the picture language expressions. The English descriptions will be used to gain insight into the forms which the algebraic descriptions must take. 3.1 AN ASSUMPTION —MEANING INDEPENDENT OF CONTEXT One important property of the language which must be assumed is that each symbol have a definable meaning independent of its position (or context) in a network diagram. It will be seen in this section that each of the symbols used in Figure 2. 1, as well as many others which can be invented, can be so described in English. Since this is the case, our plan to seek to do so also in formal algebraic terms appears reasonable. In order to distinguish between language elements and the things they represent, it will be noticed that separate terms are used. Thus diagrams represent networks, whereas symbols represent elements, connecting lines represent connections, and connection points represent ports. (The phrase "The meaning of a language element" is synonymous to the phrase "a 11

12 description of the thing repr-esented by the language element.') 3.1.1 An Example To give an example of a verbal, context-independent definitiorn of a symbol, ccnsider the following definition of a queue. The queue has an input port, an outtput p'rt, and a contents sensing port. (For simplicity, the operation of the contents-sensing port will not be treated here. ) It has a parameter, represented here by the symbol N, which indicates the maximum number of waiting tasks which can be allowed in the queue. Let the num.ber of waiting tasks be represented here by s. This queue is affected whenreve:r tasks are offered by the element connected at its input. If yl tasks are offered at the i.pit, arnd x, tasks are acceptable to the element cornnected at the output, then s~y3. tasks w iil be offered at the output. The number of tasks actually seint to the oultpt wrll be the smaller of s+y1 and x2. The number of waitirmg tasks is changed to N f s+y X2 > N; to zero if s+Y i-x, < 0; and to s+y- X, u.hewLseo Thei nimber of tasks acceptable to the qh -, at.ts input, ias -a+Xqo, T.h naB.mber actually taken at the input is the smnallr of,-s+x2 and y.' The queue is also affected wihenever tasks are requested by the element connected at its oupt. pcrt. If y2 tasks are requested at the oetlpult and x tasks are available from the element connected at the input, then y2+-N-s tasks will be requested by the queue from the element connected at its input. The number of tasks actually taken at the input will be the smaller of y2+N-s and x.sr The number of waiting tasks is changed to N ff

13 s+xl-y2 > N; to zero if s+xl-y2 < 0; and to s+xl-y2 otherwise. The number of tasks sent to the output is s+x1 if s+x1-y2 < 0; and Y2 if s+xl-y2 > 0. 3.2 A FRAMEWORK FOR SEMANTIC DESCRIPTION OF SYMBOLS The verbal definition of the queue is very wordy and somewhat repetitious. The verbal description of the meaning of Figure 2. 1 was also. The key to reducing this wordiness, or at least putting it in some perspective, lies in attempting to observe the entities which all elements have in;common. Then, by naming these entities, the cumbersome phrases which describe them can be replaced by something more technical. For example, the definition of the queue made frequent reference to "the element connected to (a port) " Such a reference is to be expected in the definition of perhaps every element which has a port, unless the elements related by the connection are truly independent of one another. Thus, the term associate will be used to refer to an element connected to the element under study. The term associate at (a port) can be used when specification of the port is necessary. 3. 2. 1 State Variables Less trivially, the phrase "the number of tasks waiting" describes the status of the element at any particular time. It is to be expected that there will be similar status variables for other elements, like "the number of tasks in service" for a multiple server element, or "the current phase of sece" for servers with Erlag distributed holding times. Such service" for servers with Erlang distributed holding times. Such

14 variables, when they are present in an element, will be referred to as state variables of the element, or sometimes as state components (for reasons that will be clear in the next section). There may be more than one such variable for a single element, for combinations of element should also be legal elements of a system. To illustrate, Figure 3. 1 demonstrates a possible equivalence, in diagram form, between a "holding server" and a queue and server connected together. The state variables might well be jointly the "number waiting" and the "number in service." Pi P2 PI PFigure 3. 1 A "holding server." The range of values which the state variable of an element can assume is a set which is distinctive of the element. We call this set S the state set of the element. It is also a property of the element, like the set P of ports of the element. That is, an element e consists of a set P, a set S, and other things. The members of S are either integers or integer vectors, depending on whether there is one, or more than one, state variable to the element. Table I lists a set of useful symbols for a pictorial language for Markovian networks, along with their names, the semantics associated with

15 their state variables, their state sets, and some other properties which will be described in subsections 3. 2. 2 and 3. 2. 3. A verbal description of the meaning of some of these symbols will be given in section 3. 3 and in section 5. 3. 2. 2 Parameters The symbol N stood for "the maximum number of waiting tasks which can be allowed in the queue" in the definition of the queue. This was an example of a parameter. Parameters have many significances in elements. Generally, they represent variables upon which the behavior of the element depends, but which do not change with the status of the element. As far as this treatment is concerned, the parameters are constants. Other uses of parameters are as mean values of probability distributions, probabilities of branches, etc. Table I supplies the meanings of parameters, and the sets from which their values must be taken, for some symbols. Because they are constants, parameters will be ignored in the remainder of this report. Any property of an element can be treated, in general, as a function of the parameters of the element without difficulty. 3.2.3 Epochs Sometimes, when a symbol is being defined it is necessary to refer to points in time when something occurs (according to a probabilistic rule). Such a time is called an epoch.

16 To illustrate, the definition of a server having exponentially distributed holding times of mean 1/g will contain a statement to the effect "a service completion occurs with probability intensity,i whenever a task is present, " and other statements to the effect "whenever a service completion occurs..." The times of "service completions" are epochs. If epochs are points in time at which something occurs, then epoch classes are sets of those points selected by some semantic identification, If the probabilistic rule determining whether or not a particular time t is a member of an epoch class is purely determined within an element, then that epoch class will be termed an autogenous (self-generated) epoch class of the element, and its members are autogenous epochs. The semantics of autogenous epoch classes for the sample group of symbols are listed in a column of Table I. They are all characterized by the fact that they can be thought to occur spontaneously within the element, and are not "triggered" from actions (or epochs) of the associates. Such triggering epoch classes, which will be called exogenous epoch classes, will be discussed in the section 3. 2. 4. Epochs and epoch classes will be defined more abstractly, in stochastic terms, in Section 6. 3. 2. 4 Port Variables A rereading of the definition of the queue will recall a whole group of special phrases which refer to the influence of the associates of the queue. These phrases, like "the number of tasks acceptable to. o o " the number of tasks available from..," "the number of tasks requested by. o."

1 7 TABLE I SEMANTICS OF STATE VARIABLES, PARAMETERS, AND AUTO-EPOCHS Symbol Name of Symbol Parameter State Variables Sti -------------------------------------—. —----------------- /^"7\_~^ r\~~~"The maximum, allowed number of._..., f Queue " m ao n b o "The number of waiting tasks. 10, waiting tasks. T (integer): N Exponential "The mean rate of service for "The nambier of tasks in - | | Server the occupied server. T (real):y service. i? "The mean rate of service per _J Eriang phase." (real): y TuO "The phasel of current task. f ~~... Server "The number of phases." (integer): N "The mean rate of service per Multiple task."1 (real): y "The number of tasks ro, 99 N ^ Server "The number of servers." in service." Y (integer): N ite Set Auto-Epochs ~ 11.., NJ None l} "Service Completions" 1,..., NI"Phase completions" 1,.., NI "Service Completions" Poisson Arrival Element "The mean rate of arrival. " (real): y None {0} "Arrivals" _ —-w Exit None None f0} None -^Merge-one~one{0} - O Merge None None f Ol --— ~~ ~~~~~~~~~~~~~~~~~~~~ ~~ ~~ ~~ ~~ ~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ None ttl Ove rf low None None {0} None Balking Queue "The mean rate of balk per waiting task. " (real): y "The maximum allowed number of waiting tasks. " (integer): N "The number of waiting tasks. " fo0,1,..., NT "Balks" Pfy> Random "The a priori probability of rNn t^. ~Distributor upward selection. " (real):p nlJ Random "The a priori probability of r^ None f Collector upward selection. " (real):p Blocker "The number of sensed tasks to None rf produce blocking. " (integer):N None None None -I -N — - - Contents Adder None None {0 None Random Switch "The a priori probability of an upward setting. " (real): p None f0} None

18 or "the number of tasks offered by" represent variables sufficiently generalized that they continue to have meaning independently of the nature of the associate. Indeed, it will be seen shortly that they will have a technical meaning whenever the connection to the associate is syntactically allowable. These phrases are used to describe what is "seen" through a connection either when looking from the queue toward the associate or from the associate toward the queue. The first two, "the number of tasks acceptable to..." and "the number of tasks available from... ", appear to play a role similar to that of the state variable when "... " is replaced by "the associate. " Like state variables, they describe an observed condition of the element; but in this case the condition is external to the element. Such a variable will be called an exocondition (short for exogenous condition: a condition having external origin) at the designated port. An exocondition of an element e is determined by the nature of the associate (call it e') of e, as a function of properties or conditions observed in the associate. This function, as yet not identified, is a property of e'. Its value, for example, is "the number of tasks acceptable to e'. " To e it is external, to e' it is internal. We will call this function an endocondition (for endogenous condition: a condition proceeding from within) function of e', and its values will be called endoconditions. Clearly, if e' is to have exoconditions, then conversely e must also have an endocondition function. The fact that there is a single variable "seen through the port" which, in combination with those "seen through" the other ports, is all that needs

19 to be known about the status of the rest of the network, is a very interesting one. It is a property of networks which seems natural, but which is, in fact, an assumption to be made about queueing networks. This assumption will be made here. It implies that all influences between elements are explicitly shown by the connections between them, and that influences from remote elements are achieved only through influences by them of the closer elements. Networks having this property will be called explicit. It appears that explicitness of a network is a necessary condition for the existence of a context-independent definition of elements, Earlier we referred to epoch classes whose probabilistic rule of occurrence was external to the element under study. An example of this is the time-point represented by the phrase "whenever tasks are offered by (the associate)" in the definition of a queue. Such an epoch class is associated with a port and is called an exogenous epoch class (or exo-epoch class) at the porto Obviously, the associate must define this epoch, which it does by an endogenous epoch class. In English descriptions, one sees "whenever (epoch) and if (condition) then tasks will be offered. " Variables representing "the number of tasks offered by (the associate), " indicate an identifier of the specific interpretation -atached-to -the action resulting from the epoch and will be called exocontrols for the elemento The exocontrol of the element is determined by an endocontrol for the associate, which is a value of an endocontrol function. The "controls" always classify what is to happen when the corresponding epoch occurs.

20 It should be clearly noted that the two alternate phraseologies for each of our types of variables are distinctly associated with input and output ports (io e., the "syntactic type" of the port), respectively. This is made clear in Table II, which tabulates the semantics. It is also clear from Table II that the endocondition of an input port of an element has the same meaning as the exocondition of an output port of its associate, and vice versa; and that this similarly holds true for-controls and -epochs. This indicates that when inputs are connected to outputs, the corresponding variables always have the same meaning, and that the eight variables (four for each port) in the connection reduce to just four distinctions. In the syntactic description of section 2. 2, two additional types of connection points were described, known as contents sensing and value collecting points. These connection point types were used in Figure 2. 1 as part of the mechanism for describing blocking. They conceivably have other uses as wello Since contents sensing ports can only be connected to value collecting ports, the semantics of their port variables are interrelated in the same manner as the input and output ports: endoconditions of an element meaning the same thing as the exoconditions of its associate, etc. The semantics of these two port types are summarized in Table IIIo The controls were omitted because only one action can result from the exo-epoch. Thus the endocontrol and exocontrol have no role and cand be considered to be always zero. Similarly the cases indicated by a blank in Table III have no role to play in the sample vocabulary of the pictorial language, and are zero, Of course,

21 TABLE II SEMANTICS OF INPUT AND OUTPUT PORT VARIABLES Te r Port Type TerK and \ Input Port Output Port Symbol "The number of tasks accep- "The number of tasks ndocondon table to (the element)." available from (the element) " "The number of tasks a- "The number of tasks Exocondition x vailable from (the asso- acceptable to (the ciate)." associate)." ddontrol w "The number of tasks re- "The number of tasks quested by (the element. " offered by (the element). " "The number of tasks of- "The number of tasks Exocontrol y Exoconrol fered by (the associate). " requested by (the associate)." "When tasks are re- "When tasks are ofEndo-epoch quested by (the element)." fered by (the element}." Exo-epoch "When tasks are offered "When tasks are reExo-epochby (the associate)." quested by (the associate). "

22 TABLE III SEMANTICS OF CONTENTS SENSING AND VALUE COLLECTING PORTS Port Type Term\ and Contents Sensing Port Value Collecting Symbol Port Endoond n "The number of tasks repreEndocondition v sented by (the element)." "The number of tasks Exocondition x represented by (the associate)." "When the number of tasks Endo-epoch represented by (the element) changes." "When the number ^~ ~~~Exo ~- ~epoch,of tasks represented by (the associate) changes."

23 an extension of the pictorial vocabulary to other symbols might display a necessity for these variables to play a9 role. The exocondition, endocondition, exocontrol, and endocontrol at a port will be known as port variables. If we designate them by x, v, y, and w respectively, their roles are suggested schematically by the arrows in Figure 3. 2, where their port is represented as a short horizontal line, and the element as a box. This representation will be a handy aid in later discussion. y [ _ w Figure 3. 2. Schematic of port variables In general, there will be no mathematical need to associate meanings like "number of tasks... " with these variables in order to define what we mean by the word "element." We assume only that one always connects ports together whose variables have mutually compatible meanings. Nevertheless, in illustrating an element-writing out its detailed characteristicsthe semantics are helpful to the person who writes them out. Also, in determining whether a certain connection should be allowed (i. e., in syntax checking of the picture language), the consistency of these semantics is allimportant. But in combining elements, forming new ones, and in writing out their formal mathematical descriptions the semantics are irrelevant.

24 Even the question of whether a port is an input or output port can be ignored. The ability to write algebraic descriptions of elements and to combine them is the objective of this report, so that these semantic descriptions of the variables will assume a low importance. They will be used only to illustrate, and sometimes to clarify. 3o 2. 5 Events The verbal definition of the queue was expressed in two paragraphs. The first paragraph described the action which resulted from an exogenous epoch at the input port, while the second paragraph described the action which resulted from an exogenous epoch at the output port. The totality of action in an element known to occur when an exogenous epoch occurs will be called an exogenous event. Similarly, the action in an element known to occur when an autogenous epoch occurs will be called arn autogenous evento 3o 3 A DESCRIPTION OF SOME USEFUL ELEMENT TYPES It will be useful now to define, verbally, several more of the element types partially described in Table Lo This will clarify some of the fine points of behavior which might be confusing when these elements are used as illustrations of the algebraic network model. 3. 3. 1 The Exponential Server A service completion occurs with probability intensity Mx (the parameter; see Table I) whenever the number of tasks in service is

25 unity. When this occurs (an autogenous epoch), and the number of tasks acceptable to the associate at the output is zero, the task simply resumes service and no further action results from this epoch until it completes again. If the number of tasks acceptable to the output associate is nonzero, one task is offered to it. If, in this case, a task is available from the input associate one task is requested and the state remains unchanged (it was at unity). If a task is not available, the state is set to zero. Whenever tasks are offered at the input and the state is unity, the number of tasks acceptable to the server is zero and no further action results, If the state is zero, one task is acceptable to the server, and the state is increased to unity. When tasks are requested by the output associate, no tasks are available from the server, and no action results. The state remains unchanged, 3. 3, 2 The Poisson Arrival Element An arrival occurs with probability intensity X. When this occurs, one task is offered by the arrival element at the only port (which is an output). The state is always the same. When tasks are requested by the associate, no tasks are available from the element, and no action results, 3. 3. 3 The Random Distributor When tasks are offered by the input associate, they are offered

26 at the outputs in a proportion determined as follows: A two-dimensional random walk experiment is conducted, with the probability of moving upward being p, and the probability of moving to the right being (1-p). Whenever the vertical coordinate reaches the number of tasks acceptable to the upper output associate, or the horizontal coordinate reaches the number of tasks acceptable to the lower output associate, or the sum of both coordinates reaches the number of tasks offered by the input associate, the experiment stops. The coordinates indicate the number of tasks to be offered to the output associates. If the process is resumed until one of the first two conditions are met, then the sum of the coordinates indicates the number of tasks acceptable to the element at the input. A similar strategy determines the result of a request for tasks by one of the output associates. 3. 3. 4 The Exit When tasks are offered at the input port, the number of tasks acceptable by the element is infinite. No change in state occurs.

4. DEFINING A NETWORK MODEL Since diagrams represent networks and symbols represent elements, and a diagram contains a collection of symbols, it is reasonable to suppose a network contains a set of elements. The discussion of semantics in the previous section has shown (or, at least, postulated) that it is meaningful to refer to elements in the abstract, without concern for their context. For this reason, one can indeed speak of a set & of elements. Furthermore, if we denote by 6' the union of the ports of all the elements of $, then a connection can be thought to consist of a pair of distinct elements of (. The connection syntax in the pictorial language provided that each connection point would have at most one connecting line. Thus, the set C of connections can be termed a function mapping (P onto L6. Moreover, since "P1 is connected to P2" implies also that "P2 is connected to pl, " the connection function C is obviously its own inverse. We shall therefore postulate that a Markovian network N consists of a set ( of elements, and a self-inverse function C, called a connection function. Or, N (,C). (4.1) Naturally, the task now is to find a suitable definition for an element e in (. It will be seen in the next section that an element consists of a set of states, a set of ports, a set of autogenous events, and a set of exogenous events. The form which these latter two sets must take for the meaning conveyed to be sufficiently general will also be described. 27

28 Section 6 will show that the meaning conveyed is the correct one by firmly relating this model to the Kolmogorov equations of the underlying Markov chain.

5. ELEMENT REPRESENTATION In this section we heuristically construct a suitable algebraic definition for an element. By successive examination of examples of elements, and of what we mean verbally by them, we will build up our model into a fairly complicated mathematical object. This constructive approach is taken in order to concretely explain the need for each feature of the model which is included. The true justification of the model as a consistent mathematical object will be treated in Section 6 where the definition will be related to the underlying Markov chain, and in Section 7 where the "connection" operation is defined. Thus, as far as mathematical development is concerned all but the last subsection of this section could be omitted, It is offered to improve credibility of the model, and to support the necessity of its complexity. It also illustrates many of the definitions in more practical terms. Throughout this discussion, the semantics of Tables I and II will be used for the port-variables and the epoch classes. 5.1 STATES AND PORTS Associated with an element e of a queueing network are two sets: a set of "states" S and a set of ports P. The set of states is the set of possible values of the state variables of the element. Thus each member of the set of states defines a possible condition of the element defined. Each port identifies a possible source of influence upon the element by 29

30 another element. A port p of the network is in the port set P of exactly one element e Ec o Recall that a port was described as a point to which exactly one "connection" can be madeo The next order of business is to substitute a more precise definition for the relatively vague definition given for autogenous, endogenous, and exogenous events. 50 2 AUTOGENOUS EVENTS An autogenous event for an element e has been defined in Section 3. 2 as the action of an element which occurs when an autogenous epoch is known to have occurred. Let A be the set of autogenous epoch classes for elemernte, which may be empty. Then for each XE A e there is an autogenous event (, and for the element e there is a set of these e { {: XE Ae} (5.1) e which is empty if A is empty, The purpose of the autogenous event is to describe the kind of information given in the verbal description of the action in the server when a service completion occurs or in a Poisson arrival element when an arrival occurso This includes a description of the endogenous epoch classes generated, the endocontrols and endoconditions which play a role, the change in the local state which occurs, and the probability law which governs the epocho These will in some way be dependent upon the identity of the epoch, the current local state, and the current exoconditions

31 and exocontrols. All this will become more evident with examples. Consider first the element which presents the autogenous event in its purest form, the element used to describe a Poisson arrival process having mean rate of arrival y. 5. 2. 1 The Poisson Arrival Element This element was used in Figure 3.1 at the far left of the diagram, and was verbally described in Section 3. 3. The graphic symbol used to describe it in network diagrams is shown in Figure 5. 1. It has a single port (which is an output port) and a single local state; so that we might write S = {0} (5.2) P = {p} Figure 5. 1 Furthermore, there is a single class X of autogenous epochs, corresponding to the times when an "arrival" occurs. These epochs occur in any time interval of duration At with a probability yAt, when At is sufficiently small. (This is a property of the Poisson process. ) Thus one says that epochs in X occur with a probability intensity y. Each epoch produces the effect of generating an endogenous epoch class

32 (indicating an "offering of tasks") at the port p, with an endocontrol (indicating "the number of tasks offered") which is unity. There is, obviously, no change in local state possible. We can note this description symbolically by saying that the autogenous event s is a quadruple X = (p1, O,y) (2.3) indicating that the epoch causes an endogenous event at port p, with an endocontrol 1, a final state 0, and it occurs with probability intensity y. The picture presented here, however, is too simple. A more realistic idea of the form that an autogenous event should take can be seen by examining the exponential server. (For now, we are only concerned with its autogenous events.) 5. 2. 2 The Autogenous Events of the Exponential Server It is evident from the symbol for this element (Figure 2. 2) that this element has two ports, one input and one output. Let the state 0 represent the idle state, and 1 the busy state. Thus e S = {0,1} (5.4) P = FIP'P 2 Figure 5. 2

33 The only autogenous epochs are the "task completions,)" which have a probability intensity y when the state is 1 and probability intensity 0 when the state is 0. This illustrates that it is necessary to regard the probability intensity of an event as a function of state. Further, each task completion can generate endogenous epochs at both ports p1 and P2, since it may cause either an offering of a task at its output, a request for a task at its input, or both. The endocontrol at these ports and the state resulting when this epoch occurs will, in general, depend upon the exoconditions observed at that time. If "the number of tasks acceptable to" the associate at P2 is at least one, then it is known that the completed task can be sent, and therefore that a task can be requested from the associate at P1. In other words if the exocondition x2 is positive (x2 > 0), then the endocontrol wl ("the number of tasks requested") is unity. Otherwise it is zero. However, regardless of "the number of tasks acceptable to" the associate at port p2, a task can be "offered" through p2. That is, w2 = 1. Clearly, the endocontrols (w1, w2) must be treated as functions of the exoconditions (x1, x2)o A little consideration of the above discussion should bring the conclusion that the resulting state must also depend upon the:exocqndtioals (xl1 x2) Analogously to Eq. (5. 3), the above discussion could be described symbolically by saying that the autogenous event ( of this element is a quadruple = ({ P1P2}, 3, gP, 9) (5. 5)

34 where 3 is a vector valued function of (x1, x2) whose values are the values of the double (w1, w2) = (1l(x1, x2), 32(Xl, x2)) 0 when x2 0 I 2 i1(X1'X2) (5. 6) 1 when x2 > 0 2(Xl X2) = 1 where g is also a function of (x1, x2). Owhen x Oand x > 0 g(x9 x2) = (5 7) 1 otherwise and where i is a function of state s e S: 0 when s = 0 AN(s) - (5. 8) y when s 1lo This quadruple indicates that the autogenous epoch causes endogenous epochs at p1 and p2, with endocondition given by 01 and /3, a target state given by g, and that it occurs with probability intensity given by g. 5o 20 3 A General Definition The similarity between Eqs. (5. 3) and (5. 5) was, of course, intentionalo Their mathematical form is identical if, in (5. 3), we replace p by {p}, 1 by the unity function, 0 by the zero function, and y by a constant function (all of appropriate domain). The two examples are sufficient

35 to motivate the general (abstract) definition of an autogenous event given below. It should be noted, however, that neither example had more than one autogenous event, even though such a situation is possible. Thus, in addition to the sets S and P, a set of autogenous events must take a place in the definition of an element. The definition below also takes cognizance of some other possibilities in the forms of the functions which were not demonstrated in the examples. For example, it is quite certainly true that endocontrols can take on values greater than unity. How else would such things as bulk arrival or service be described? The philosophy followed is to keep whatever usable generality appears inherent in the examples and notation. In general, every autogenous event ( can be defined in a quite natural way as a function of s e S, whose values consist of quadruples s (Q sg s, s) (5.9) where the components are defined as follows: 1. The endogenous epoch set QX is a set of ports, Q C P at which endogenous events are identified. 2. Let I = X I xI x. I oox, where {PlP, p2, n Q, and pl P2 Pn where I = {, 1 2,... } for all p E P. Then the endocontrol function 3 p s is a function on ~ to 4, for each s E S. If we write this function out as

36 (w, w,,w ) sx (x,x x ) (5.10) P1 P2 P then w represents the endocontrol at port p, and x represents the exocondition at port p, for all p e Q o 3o The target state function g is a function on J to S, for each s s E S. It represents the target state as a function of the original state and the exoconditions at the ports in Q o In other words gs(x, x,... x ) S P i P2n is the value of the target state when the element is originally in state s and sees exoconditions x, o, x at ports Pl o pn respectivelyo 4o The probability intensity i s is a non-negative real number. It represents the probability intensity of the occurrence of the epoch generating the autogenous event X, as a function of the original state. It remains to be shown, in Section 6, that this definition is unambiguous. It also remains to be shown that it is sufficiently general to suit all pcterntial needs within specified assumptionso The latter, unfortunately, appears to be only provable by experience. Nevertheless, the question of gererality will also be explored in Section 60 5 3 EXOGENOUS EVENTS An exogenous event for an element e is that object which identifies the effects upon e observed when an exogenous epoch occurs at one of its portso A more detailed and precise definition for exogenous events is now sought. The epochs which determine such events are defined by autogenous

37 events in other elements in a network. They are observed in the element e only by the occurrence of an endogenous epoch class in an associate of e. The appearance of an exogenous event at a port of e obligates e to define an endocondition at that port which serves as an exocondition to the adjacent element. It also requires the specification of the observed effect of the epoch upon e. The effect may be either the generation of endogenous epoch classes at other ports, or a change in state, or both. A further examination of the exponential server element will help clarify these representational needs. 5. 3. 1 The Exogenous Events of the Exponential Server We observe that an exogenous epoch for this element is the "offering of tasks" into port pl. The first necessity is to define the endocondition v1, the "number of tasks which can be accepted by e, " as it is observed at one of these epochs: v1 a1(s) = 1-s, all s E S (511) where S = {0, 1} as before. This indicates that a task can be accepted only if the server is idle. We further observe that no endogenous epoch classes are generated by this epoch, and that the state will increase from O to 1 whenever the exocontrol y1 ("the number of tasks offered by the associate") at port p1 is not zero. This description can be symbolically noted by saying that this exogenous event i is a triple

38 ({P1}, 1 gi) (5. 12) signifying that the epoch class is determined from port pl, that the endocondition at p1 is given by the function a1 (Eq. (2. 11)), and that the target state after the epoch occurs will be given by the function gl 0 y 0 and s g1(s, Y ) = (5.13) Y1 Y > Oor s 1. We can also observe that a second exogenous epoch class for this element is the "requesting of a task" by the associate at port P2. However, since a server can only transmit tasks at its output during "job completion" epochs, the consequences of the request are simple to describe- an endocondition of 0 is always shown and there are no endogenous epoch classes or changes in state. This exogenous event 2 could be described by the trip.le %2 ({P29 0~9 g 2) (5.14) where g2(s) - s using the same notation as for Eqo (5. 12). The description used in Eqs. (5. 12) and (5. 14) does not take account of the possibility that an exogenous epoch class may generate an endogenous epoch class at a port other than the one defining the epoch. This possibility gives rise to more complexity in the description of an

39 exogenous event, and is well illustrated in the attempt to describe the behavior of the "queue" element. 5. 3. 2 The Queue This element, whose symbol appears in Figure 5. 3 must accept inputs of groups of tasks and hold them until they are requested (in groups) from other elements. It has two ports, an input (P1) and an output (p2). Its state is described by the "number of waiting tasks present, " and is bounded by a constant, N. The queue is entirely controlled from outside, having no autogenous epoch classes and thus no autogenous events. Thus, P = {PP2} S = {0,1,2,...,N} (2.15) Figure 5. 3 The exogenous epoch at port p1 is the "offering of tasks by the associate. " If an element connected at P2 "can accept" any of these tasks, they will be passed on. Thus, the exogenous epoch at p1 causes an endogenous event to be generated at p2. The endocondition v1 ("the number of tasks acceptable") at p1, and the target state g1 ("the number of waiting tasks"), will depend upon the value of the exocondition x2 ("the number of

40 tasks acceptable") at p2 and the exocontrol y1 ("the number of tasks offered") at p1. In fact, then, we can write 1 al(s, 2) = N-s+x2 (5.16) signifying that the number of tasks acceptable at p1 is the capacity of the queue, less the number already present, plus the number which can be passed on through p2. We can also write gl(s, x2, yl) min (N, max(0, s+Yl-x2)) (5. 17) signifying that the number in queue after the epoch occurs is the number present before the epoch, plus the number offered by the associate at the input, less the number acceptable by the associate at the output (but at least zero and at most N). The endocontrol w2 ("the number of tasks offered") associated with the endogenous epoch class at P2 can be written W2 -= 2(S9y1)'s Y1 (5.18) signifying that the number offered to the output associate, is the number in queue plus the number offered by the input associate. This exogenous event is considerably more complicated than the first (i. e., Eq. (5.12)), but it can be described by the quintuple = (f{p},{,pa}a1, g1 (50.19) (1 19P1}s { 2} gl) (5P 19) signifying that the epoch is determined from port p1, that this epoch generates an endogenous epoch class at p2, with an endocontrol given by the value of the function y2' that the endocondition at p1 is given by the value

41 of the function a, and that the state immediately after this epoch is given by the value of the function gl. The triple used in the previous example can be expanded to a special case of this more general form. The second exogenous event of the queue describes the effect of an epoch determined at port p2, representing "a request for tasks by the associate at P2." The endocondition v2, endocontrol w1, and target state g2 for this event are analogously determined by the equations v2 = a2(s,x1) = s+x1 (5 20) g2(s, x1, Y2) - min(N max(O, s -Y2 +x1)) (5.21) w1 = 1(s, Y2) = N-s+Y2 (5.22) using an obvious notational convention for the subscripts. This event 2 is. described by the quintuple 2 = ({P2}' {P1} a 2 1' g2) (5. 23) 5. 3. 3 A General Form (Deterministic) In the examples, there has been at most a single port identifying the source of an exogenous epoch. If we assume that this will always be the case, then the set of exogenous events are in one-to-one correspondence with the set of ports. This suggests that a more efficient format for the description of exogenous events would be as a quadruple which is a function defined on the set of ports P, rather than as the quintuples uised in Eqs. (5. 19) and (5. 23).

42 If we adopt this convention, then there is a single exogenous event function ~ defined on P. Attempting to provide enough generality in the folm which this function takes (general in the same sense as our previous definition of the autogenous event function), this exogenous event function would have to take the form of a quadruple ps - =(QP, ap 3Ps gPs) p E P s e S (5. 24) whose components are defined as follows: 1o The endogenous epoch set QP is a set of ports, QP C P at which endogenous events are generated by Ps 2. Define an integer space 4P by jP I xI x. oxI where Pl P2 Pn {P1l oo p, } n QP, and where I = {0, 1 2, o } for all q E P as before. Then the endocondition function is a function on to I for each s P p e P, s e So If we write this function out as v pa,. Xp ~ x ) (5. 25) p S ls PI P2 Pn then v represents the endocondition at port p, and x, q e QP represents the exocondition at port q. 3. The endoconrtrol function is a functionon on JxI to P for each p E Po Writing the function out as (wp w2...,w ) = (x P',., x, yp) (5. 26) P1 P2 n P2 n then wq, q e QP, represents the endocontrol at port q when the element is in state s and "excited" by an exogenous event at port p, y represents the P

43 exocontrol at port p, and x, y e QP, represents the exocondition at port y. 4. The target state function gP is a function on PxI to S, for s p each s e S. Thus gP (x, x, o.., x, y ) is the value of the target state s P P2 nP p when: (a) the element is in state s, (b) an exogenous event arrives at port p, and (c) the element sees the exoconditions x, x,..., x at ports P1',,pn' respectively (where {P1,, pn} = QP as before), and y is the exocontrol at port po This rather formidable object P is, as we have seen, a natural result of attempting to find a description which fits the exogenous events of the foregoing examples in some abstraction. It is evidently complex because our intuitive concept of an exogenous event is surprisingly complex. Worse yet, as will be seen in the next section, even this is not quite general enougho 5. 3. 4 Random Effects-The Random Switch If a state and exogenous epoch is given, then the endoconditions returned, the endogenous epoch classes generated, the endocontrols, and the target state may not all be deterministic. Rather, these variables can be random variables not totally determined by the particular exogenous epoch class which otherwise identifies them. This requires a further generalization of the mathematical model for an exogenous event. A very simple example of this problem can be found in the random switch symbolized in Figure 5. 4. The operation of this switch is as follows:

44 Figure 5. 4. The random switch. Fach time a task or tasks are offered at its input, or requested from an output, the switch is set. With probability r it is set between the input and the upper output, and with probability 1-r it is set between the input and the lower output. After the switch is set the tasks flow, to the extent possible, from the input to the selected output. This element has three ports, a single state, and no autogenous events: P = {Po P p1P2} S = {0} (5.27) An exogenous epoch determined at port p0 (the input) has two possible effects. With probability r it produces an endogenous epoch class at pi, returns an endocondition which is equal to the exocondition at pi, sends an endocontrol equal to the exocontrol at po, and remains at state 0. In the notation of Eq. (5. 24) P0 PO PO PO P0 (s) = (Q a ~SI3 5,g \) (5. 28) where

45 P0 Q = {P} PO V = a s(X1) = PO w = 1 s xYo) =Yo = g s(X1Y0) = 0. (5 29) With probability 1-r, on the other hand, the roles of p1 and P2 are reversed so the exoevent is AP AoP A Po APo APo C = (Q,a ~S sg s) (5. 30) where APO Q = {P2} A /AP0 A AP0 AP0 g (X2YO) (5. 3 ) A handy notation would treat the exo-event set Z for the element as a set valued function on P whose value consists jigf.exo-events. over.. an index set which is distinctive for each port. Thus Z (p) = {U:-e E}, pe P (5.32) P0 Then the "exoevent" s corresponding to Eq. (5. 28) would be coupled with the probability r, and written

46 a1 a1 a1 1 1- O = (Q,a s'3,g Sr) (5.33) APo where SP contains al. The "exoevent" t (s) becomes U2 a2 U2 02 U2 = (Q,a s',g s, (-r)) (5 34) and we can write Sp {a, a2}. The exo-events for the other ports are similarly derived, as a3 (s) = ({p0},a t1' i, 0,r) (5.35) a4 e (s) = (0, O, O O (-r)) (5. 36) where Z = {3', a4}, 0 represents the zero function, and where Pi a 1(x) = X09 and 3'1l(x0, Y) = y1l For port P2 the roles of p1 and P2 above are interchangedo 5. 3. 5 A General Form (Stochastic) As implied by the foregoing example, the exogenous events of an element can be described by a set Z (p) = {0a: U Sp }, p e P with each event C being a function on S of the form a(~ = (Qa a a a a ), s E S 37 s =(Qsa si sg, S) S (5 37) where Q, a s,' s, and ga are defined exactly as they were in Section 3 3 xcpt that p is ow dfid as th port p such that 5. 3. 3, except that p is now defined as the port p such that a ~,. The p

47 symbol r s represents a function whose range is in the interval [0, 1]. Its domain may be quite complex and will be treated in full after some additional theory is presented in Section 6. A set-valued function Z, mapping a set of ports onto a set of exogenous events, will be called an exo-event set. 5.4 FULL DEFINITION OF AN ELEMENT With the description of the state set S, the port set P, auto-event set 2, and the exo-event set Z for an element e, we appear to have described all of the technical meaning represented by the element. We now turn this around and define the element e as the collection of four such sets as defined. In other words, we let e = (S,P,,Z) (5 38) This completes our definition of element and network, except for the tricky considerations regarding Tia in the definition of the exoevent, which s will be clarified later. To summarize, (1) S is a set of objects called states (2) P is a set of objects called ports (3) 2 is a set of objects called autogenous events (4) Z is a set valued function on P to sets of exogenous events (5) An autogenous event 5 is a quadruple, a function on S, =s = (Q' S'gS9 S)' s S

48 where (a) Q is a set of ports, called an endo-epoch set. (b) s, for all s e S, a function of as many integer variables as there are ports in Q (representing the endoconditions at these ports). Its range has an equal number of (integer) components (representing the endocontrols at the ports). (c) gs, for all s E S, is a function of as many integer variables as there are ports in Q (also representing the endoconditions), into the set So It represents the target state of the evento (d) Is, for all s e S, is a positive real number (representing the probability intensity occurrence of the event). (6) An exogenous event C is a quintuple, a function on S 5s (Q SS S where (a) Q is a set of ports, called an endo-epocho (b) a, for all s E S, is a function of as many integer variables as there are ports in Q (representing exoconditions at these ports), into the set of nonnegative integers (representing the endocondition at the port p for which Es Z (p))o (c) 1s3 for all s e S, is a function of as many integer variables as there are ports in Q, plus one (representing the endoconditions and an exocontrol at p defined above ) Its range

49 has as many (integer) components as there are ports in Q (representing the endocontrols at these ports). (d) gs, for all s e S, is a function of the same variables as As (above) into S. It represents the target state of the event. (e) T, for all s e S, is a function of the same variables as 3s (above), as we shall see, and is onto the interval [0, 1]. It represents a probability. Table III formally lists the defining sets and functions for some of the more common elements. It should be, for the most part, self-explanatory, except for a few notational conventions. The parameter symbols (y, r, N) from Table I are used without further explanation. The subscript "1" on a port is always for an input port, while a "2'? is for an output porto More than one port of a type are distinguished by primes. The exoconditions and exocontrols use the main symbols x and y as usual, with the subscripts and primes borrowed from their respective ports. Endocontrols, as vectors, are ordered in the same sequence as the elements of the corresponding endoevent set. An asterisk (*) is used where a function is degenerate, having null range and domain, as when an endocontrol vector has no components. For a set of numbers A, and any variable a, the symbol I (A) represents the function which has unity value whenever a is in A, and is An alternate notation is to use the symbol 0 to denote the function having null range and null domain.

50 TABLE IV ELEMENT DEFINITIONS1 For notation, see text.

51 zero otherwise. That is, I. (A) is the indicator function of the set A. The symbol J+ is used to represent the set of positive integers {1, 2,... }, so that I a(J+) has unity value whenever a is an integer greater than zero, and is zero otherwise. For any variables a, b, c, the symbol [a]c signifies the integer part of a not exceeding c or lying below b. In other words [a]c = min{b, max{c, int(a)}}. (5. 39)

6. THE NETWORK AS A MARKOV CHAIN The pictorial language describes not only Markovian systems, but also Markov chains. At this point the network model will be related to the Markov chains, and will thereby be given a more rigorous foundation. So far, the chief justification for our constructs has been that they seem to parrot what one does in ordinary verbal description. This is, of course, not an adequate basis for constructing a network model. In this section, new probabilistic definitions will be given for many of the concepts more loosely used in the foregoing development of the model. These new definitions, and the mathematical system they evolve, represent still another "translation;" this being the last one, Because they are more precise, these definitions are also somewhat more general. Nevertheless, the same terms and symbols will be used for the new as for the old. To have created a whole new symbology would have been still more confusing. One major difference in the viewpoint of this section from the previous one is that the network is viewed as a whole, and then gradually broken down into its component parts, rather than the reverse. This is a consequence of the fact that Markov chains are not naturally broken up into thi thngs like elements andconnections, and so our development must proceed from the well known theory toward a more conventional view of Markov chains. Thus, the starting point is the entire network. 53

54 6 1 THE KOLMOGOROV AND EQUILIBRIUM EQUATIONS The only concern of this report is with continuous-time, finite Markov chains with stationary transition probabilities. This model consists of a one parameter family of random variables {Zt, t > 0} having the property that, for any real t1, t2 t3 such that 0 < t1 < t2 2' 3 0 - 1 < t3, and for any z1, z2, z3 in the range of Zt, pr{Zt z3iZt 3 z22 t-3 31Z 2}, (6ol) 3 2 1 3 2 the latter being a function of z2, z3, and (t3-t2). The range of the random variable Zt is called the state set, will be denoted by / and will always be finite here. It is a well-known (cfo theorem II, 18. 3 and corollary IIo 19o 2 of Ref. 1) property of finite-state continuous-time Markov chains with stationary transition probabilities that the process is completely determined by the transition intensities, defined as i A d pr{Zt = jZO i}tO (6. 2) uij:'dt' o0 t:: 0 for all i, j e r o The transient state probabilities for this process Pi.(t) where by definition Pij(t): pr{zt = j I zo n i), are found from the Kolmogorov differential equations d df Pij(t) - kkjikt) (6. 3) The equilibrium state probabilities, yi, ic, are found from a solution

55 of the system of algebraic equations L Uvi.r = 0 (6.4) ie for all j e Eo It is these latter equations, known as the equilibrium 2 equations, which the Recursive Queue Analyzer or similar algorithms are capable of efficiently solving. If the state set z consists of a sequence consecutive integers (1, 2,..., ns), then Eq. (6. 4) takes the familiar matrix form of a homogeneous set of equations T U 0. (6.5) However, the state can, in general, be regarded as an abstract object and s an abstract set. 6.2 A VECTOR VALUED MARKOV CHAIN For networks as treated here, the state will be described by a vector consisting of a number of components (the state-variables of all the elements). Thus, if Zt(l) is a queue length in the network, and Zt(2) is the number of servers of a particular multiple server which are occupied, and Zt(3) is some other queue length, etc., then t = (() Zt(2). t("), t > 0 (6.6) is a vector-valued Markov chain, which will be denoted by Z. Letting Sk be the set of possible values of Zt(k), then c C SlxS2x... xSn is the state set for Z. The "a C" symbol is used instead of the "=I" symbol

56 because certain combinations of the components may not be possible or (k) necessary. The components Z k), treated as random processes, will be called process compcnents, while Zt, the vector, will be called simply the process. Each process component is a continuous parameter, discrete state random process, but in general only the process as a whole has the Markovian property. The components Ztk) correspond to the variables we called state variables in the earlier sections, and are therefore iderntified with the elements Each component will be associated with exactly one element, although an element may be associated with more than one component. In general, samples of these components are defined only as elements Pf their respective sets Sk, and need not be assumed to be integers. (The example has been given that a state component may designate the current pattern of naths established through an element representing a switching network, these patterns having no direct correspondence to nrumbers.) Nevertheless, each component state set Sk must be finLte, so it will always be possible to put the states in correspondencee to integers. 60 3 EPOCHS The role played by epochs is a vital one to the treatment of Markov chains as networks.

57 6. 3.1 A Definition Each nonzero value of uij for ifj signifies that at any time when Zt is in state i (i. e., when Zt has value i) there is a chance that Zt may jump to state j. This chance is measured by the probability pr{Zt+At = jlt = i} = uijAt (6.7) for At sufficiently small and i/jo (The value of uij for i=j is given by 1 - pr{Zt+ ilZt =i -u -At (6 8) t+At t- 1 for At sufficiently small. Since E u = 0 all i e, (6.9) j J we will not be concerned with u..- it is readily found when all other u.. are known.) The value in time at which this jump occurs is an epoch of the process. Thus uijAt represents the probability, given that Zt is in state i at time t, that an epoch which takes i to j occurs in the interval Et, t+At]. This object represents an abstraction of the concept of epoch described in section 3. Let the sample space for the Markov chain Zt be the set 12. Then, for each w e 2 there is a set T(w) of epochs marking the times of all jumps in Zt(w). Thus T is a set-valued random variable. When one refers to the object "completions of service in server 3" or "arrivals at the input to queue 1, " as was done in section 3, one is referring to a subset of Tr(w) for each w e Sl. An

58 individual "completion of service" refers to a member of this subset, which is also a member of r(w), and hence is also an epoch. 6. 3 2 Epoch Classes Let an arbitrary subset of r(w) be represented as v(ow) for all Se 2o Then v is a set valued random variable which is called an epoch class. This, also, represents an abstraction of the concept of epoch class described in section 3. Phrases like "completions of service. o o" identify epoch classes, in this more precise sense. Epoch classes are not necessarily disjoint subsets of To For example, a "service completion of server 3 when switch 1 is in its left position" identifies an epoch class, but so do a "service completion of server 3" and "any occurrence when switch 1 is in its left positiono " The first is, in fact, the intersection of the second and third. 6. 30 3 Partitions of the Epoch Set Suppose, however, that the set r of epochs of {Zt} is partitioned by a set N {il, v2, o., m} of (disjoint) epoch classes, where m U k(W) =.() (6010) k:1 and vk (w) nvk (w) (6.11) 1 2

59 for all k andk2 in12, andforllwE S2. Such a partitioning allows Eqs. (6. 3) and (6. 4) to be rewritten in a very useful form. Let y be a function representing the probability intensity of occurrence of an arbitrary epoch class v, given only that the process is in state i. Thus A 0pr{i (n [^0; At]^4 i.=-} g(, i) = lim -- (6.12) At- 0 for all epoch classes v and all i e g. Recall that, because of the stationarity of {Zt, we are free to observe these probability intensities merely at t 0 O. To avoid the unsightly expression "v n [0, At] =," we shall henceforth (where v is any epoch class) use the more graphic phrase "v occurs in At" to mean the same thing. Thus A pr{ occurs in At Z =zi} (y, i) = lim 0- At, (6 12a) At-0 for all epoch classes v and all i ~ J. Furthermore, let h be a function representing the probability that the epoch, having just occurred, results in a transition to j. That is, h(v,i,j) lim pr{ZA t jv occurs in At and ZO i}, (6.13) At-0 for all i and j in j. We note, from Eq. (6. 2), that

60 uij A d pr{Zt= jZoO Also, pr{ZAt j and voccurs in At Zo=i} (v,, i)h(v, i, j) u lim at (6 14) At-0 A and, pr{Zt j and T occurs in At| Z = i} E (v, i)h(v,i,j) - lim At (6 15) ve ln GAt-0 A since 71t is a finite partitioning of To We observe that for i/j it is impossible for Z t to be equal to j when Z =i if some epoch did not occur in the interval [0, At]o Consequently pr{ZAt j and occurs AtI Z i} p = r jlZ i} (6016) for all At > 0 and all i/j. From this it is readily concluded that ( v i)h(vg i, j) - u (6 17) for all ij e, iijo What this means is that, for an arbitrary finite partitioning of T, if the probability intensity o of each epoch class in the partitioning is known, and if the conditional transition probability (given the epoch class) h is also known, the transition intensities uij are readily determined. The next step is to relate the element properties rigorously to a partitioning of, and known functions yo and h.

61 6.3. 4 The Autogenous Epoch Classes The "autogenous epoch classes" of the network, first described in section 3, are seen to constitute a partitioning of r. That is, if each autogenous epoch class for each element is represented by an epoch class X E A, then A is a finite set of disjoint subsets of r whose union is To While this is taken axiomatically, it is reasonable to suggest that because an autogenous epoch class represents occurrences which arise spontaneously, (1) every epoch must somewhere have a "spontaneous source, " and (2) no epoch can have more than one "spontaneous source. " The consistency between viewing autogenous epoch classes as members of a partitioning A, and viewing them as representing times whose identity is spontaneously determined within an element becomes more acceptable when it is observed that each of the autogenous epoch classes described in Table I has a probability intensity of occurrence which is well known a priori. In other words, if X is an autogenous epoch class of e, p(X, i) is determined immediately when the definition of the element is given. From Eq. (6 17), ui. is determined by u. = p(X, i)h(X, i, j) (6.18) Xe A where h(X, i, j) = lim pr{Zt = jIX occurs in At and Z At 0

62 This function can be broken down further through the use of the exogenous epoch classes (and subclasses), and the epoch-trees, which will be described below. 6. 3. 5 Exogenous Epoch Classes Each port defines an epoch class representing, under the conventions of Table II (section 3. 2. 4), either "the times when tasks are offered by (the associate)" or "the times when tasks are requested by (the associate). " These were called exogenous epoch classeso Let Pp denote the exogenous epoch class at port po (It should be noted that every epoch in an exogenous epoch class must also be in an autogenous epoch class. That is, a "task" may not be "offered" unless action was initiated elsewhere in the network ) It has been observed (section 5. 3. 4) that an exogenous epoch may not always produce the same effect as another exogenous epoch in the same class Inr different words, the exogenous epoch class p can be further partitioned to represent distinctions in the action which results from its occurrence. Thus, a finer epoch class for the random switch is'"times when tasks are offered by the associate at the input port of a random switch and the switch is set to its upward position, " and "times when..o downward position " If p is the exogen- p ous epoch class at that (input) port, then these two epoch classes represent partitioning subsets of pp.

63 In general an exogenous epoch class p at a port p will be partitioned into a set L of epoch classes. That is P U o pp (6.20) ae _ P and a1 n a2 = d for all al and 2 in Z. 1 2 p 6. 3.6 Endogenous Epoch classes To see how more detailed epoch classes are defined for a network, let X be an autogenous epoch class of an element e. This epoch class is known to "generate" endogenous epoch classes at a number of the ports of e, which are designated by the endo-event set QXo If Q = tPl' P2, ~~, Pkj} then these endogenous epoch classes are synonymous to exogenous epoch classes at the ports connected to p1, p2,..., Pki. e., at ports Pa = C(p1)' Pb = C(P2)' *, Pz = C(pk) (The significance of this "generating" of exogenous epoch classes pp P Pa Pb.., Xp is that X is contained in each of these classes.) These pz epoch classes are partitioned into the sets of epoch classes p a > pa b 0oo, p, Y Consequently there are a number of new epoch classes z generated by v(X, a' orb o o, z) = X n a% n b n o n (6.21)

64 for each o L X c~b S, o.., Z e. In short, there are as Pa b z pz many separately distinguishable epoch classes as there are combinations of the partitioning subsets of the exogenous epoch classes. Furthermore, each of these epoch classes generate endogenous epoch classes at other ports of the elements of which they are a part. These a b az. are the elements of the endogenous epoch sets Q a Q,.., Q in their respective exogenous events. Intersections of the partitioning subsets continue until no further endogenous epoch classes are generatedo 6. 4 Epoch Trees and Tree Structured Networks This process of tracing out the endogenous epoch classes can be made clearer with the aid of Figure 6. 1. What is shown are boxes representing the elements, solid lines representing connections, dots representing epoch classes (located at the ports that give rise to them, in the case of exogenous epoch classes), and dotted arrows showing the ports in the endo-event sets of the epochs at their tails. The epoch classes 19 29 ao3' a4 are members of the partitiorings 9, L. p, L respectively. Thus, the diagram represents a P 9 Pd ^a b c pd'smallest" epoch class of the network. Others would result from other combinations, but since the Qa sets would be different, the "shape" of the diagram would be different for eacho Each such epoch class will be called primitive, and to each there will correspond an epoch graph such as Figure 6. 2.

e2 e5 Pd el PI Pa P4 CM <U) e6 Pe PC Figure 6. 1 Illustrating the "propagation of an epoch. "

66 A1~~~- _~4 A.' x74 Figure 6. 2 An epoch graph fragment corresponding to figure 6. 1. 00 -

67 It will be assumed that no graph linking the epoch classes in this manner closes. Hence the epoch graphs are trees, and the networks meeting this restriction will be called tree-structured. This restriction can be relaxed at the expense of further complication of the models. However, such a gel sralization is beyond our present scope. A tree-structured network can have a closed diagram. The epoch graph for each primitive epoch class may be open, even though the graph for all of the primitive epoch classes superimposed is closed. 6.6 THE PROBABILITY INTENSITY OF A PRIMITIVE EPOCH CLASS The set of all primitive epoch classes is itself a partitioning of the epoch set -. Thus, if we let v now represent (generically) a primitive epoch class, and let"Z now represent the set of all primitive epoch classes, then from Eq. (6. 17) uij = v i)h(v i j), (6.17) where pr{v occurs in Atl Z = i} (v, i) lim -t (6.12a) At-0 represents the (conditional) probability intensity of the occurrence of v, and where h(v, i, j) lim pr{Zt = j v occurs in At and Z = i}. (6.13) At -0 IfEq. (6. 17) is to be used constructively,, ( i) must be determined for all ve 1 and all i E e, and it must specifically be determined

68 in terms of probabilities and properties of individual elements in the networko The event "v occurs in At" is equivalent to an event reading t" X, a 29... o9 ao all occur in At, " where Xl 9 02 o o o 9m are the epochs of the tree describing v. Consequently, cp can be treated like a joint probability, and broken up by use of a conditional chain of the type pr{v occurs in At Z oi} = pr{X occurs in At Z =i}pr{a1 occurs in AtIX occurs in At, Z -i}.00. o. pr{am occurs in AtI Cm,0ml' ~ 9 a1 all occur in At; Z =i} (6. 22) Let the ordering a1, a2,.., am used in Eqo (6. 22) be any ordering such that every epoch class (X, al, o o., m) is conditioned only by epoch classes which they do not lead to in the epoch graph. For example, Figure 60 1 has just such an ordering for al, a2 %, ao (Since the epoch graph is a tree, such an ordering always existso ) Let (Zt)k represent the projection of Zt on the components of Zt for the element possessing port pk' and let ik represent the projection of i upon the corresponding state variables of the element possessing port Pk, k= 1, o o mo Finally, let Pk represent the exogenous epoch class at port pk, and let *k be the immediate predecessor of a on the epoch grapho Then we postulate the following property for the network ~ pr{rk occurs in A kl o k o o a1, X all occur in At; Zo-i} pr{Uk occurs in At, a'k occurs in At, Z (k)i} pr{ok occurs in At Pk occurs in At, Z (k)ik} (60 23)

69 for k=2,.., m, and pr{a1 occurs in Atix occurs in At; Zo=i} = pr{ao occurs in At I p occurs in At, Z o()=i (6. 24) (hpting that the predecessor of al must be X). Crudely, what this means is that: (1) If we know the exogenous epoch class Pk, of which ak is a part, then a knowledge of the epoch classes which generated the exogenous epoch class Pk is not useful in determining the probability of ak. (2) If we know the state of the element of which ak is a part, then a knowledge of the state of the rest of the network is similarly useless. In a similar vein, we also postulate that pr{X occurs in At I Zo=i} = pr{x occurs in AtI Z (0)-=} (60 25) where Zt(0) is the projection of Zt on the process components of Zt associated with the element defining X, and io is the projection of i upon the corresponding state variables. The conditions of these postulates were met by every element proposed in Table I, and are a direct consequence of the so-called "explicitness" of the network. Without this condition, the action of an element would depend upon the character of other elements in the network. It is interesting to note that this property is very similar to the Markovian property, with the (partially ordered) epoch classes of the epoch tree playing the role of the (totally ordered)*,time axis.

70 The probabilities of Eq. (6. 23) and (6. 24) are functions only of ak and ik9 since Pk can be directly found from ak. Thus, let /ak, ik) represent this probability for all ak in the epoch graph. Also let ((X, i ) represent the probability defined by Eq. (6. 25). Then Eq. (60 22) becomes pv, i ) - ((X, io <=l; ii), ~. C4om1 im) (6o26) O m and each term is associated with a single element of the network. 6 6 THE CONDITIONAL TRANSITION PROBABILITY In order to use Eq. (6. 17) for the evaluation of the transition intensities uij, a formulation for determining h(v i, j) - lim pr{Zt = A j occurs in At, Z Oi} (6, 13) At-0 for all i, j E a and all primitive epoch classes vw %, must be foundo This process is assisted by the creation of a new stochastic process, for which the original Markov chain, {Zt}, is a projection. Let {Zt, t > 0} be this new chain, having components z ( ) (n) (1) (f) Z oo o (, Z x,,.z xt, where Q is the number of ports in the network. The component X(k) corresponds to the endocondition at the port pok k1, I o o o, and is a random variable associated with each porto There are several additional graphs which it is useful to define,

71 each having the same form as an epoch-graph but with different labeling. If we relabel the nodes of Figure 6. 2 with the ports to which the endogenous epochs belong (i. e., the port p such that a Sp P for each node a in the epoch graph) we obtain what will be called the remote-port graph. If we relabel the nodes p of the remote-port graph by the ports to which p is connected, the result is what will be called the near-port graph. (The justification of the terminology s should be clear from inspection of Figure 6. 1.) Relabeling the nodes with the endocondition at the remote-ports gives an endocondition graph, and the endocontrols at the near-ports gives an endocontrol graph. Finally, labeling the nodes with sets of process components gives a state component graph. The significance attached to each of these graphs, which are illustrated in Figure 6.0 3 for the example of Figures 60 1 and 60 2, will be explained shortly. The endocontrol w. at port p. is a variable which identifies a set of epoch classes {w~ w E {0, 1, 2 o o o}} which is another partitioning of the exo1 epoch p,, where p'i is the (remote) port connected to the (near) port pi. There is a special series of properties of networks which were evident in the examples of Section 5. These have to do with the necessity for information about the state, events, or conditions of elements remote from a particular element. It was clear that one could take a fairly myopic view of each element while defining it.

72 (a) Remote-port o Graph 0< (b) Near-port Graph o 0< (c) Endocondition O Graph o (d) Endocontrol Graph 0< (e) State Component {Z(l Graph o< Figure 6. 3 Graphs related to the epoch graph.

73 This shows up as postulated properties for some of the conditional probabilities analogous to those found for epoch classes. The postulated properties are itemized below for a fixed v e 7' and a fixed current state Z0: Postulate 1 Postulate 2 Postulate 3 Postulate 4 The network is tree-structured. The endoconditions not in the endocondition graph A are independent of all other components of Zt. The dependence of each endocondition in the endocondition graph upon endoconditions which are not its predecessors in the graph is totally determined by its immediate successors and its state componentso Tius, from Figure 6. 3 pr{x(a) - x Ix(b) = xb X(d) -x Xd (f) X(g) x X(h) = h, Z=z v occurs in At} - pr{x(a)=x IX(b) Xb X(d) -xd Z (3) occurs in At}. (6. 27) This property is similar to the Markovian property with a partially-ordered set playing the role of the time -axis. The dependence of each endocontrol upon endocontrols which are not its successors in the endocontrol graph is similarly totally determined by its immediate predecessor, the state components,

74 Postulate 5 Postulate 6 and the corresponding endoconditionso Io e., for Figure 60 3 pr{O occurs in Atl 1 0,0, occur in At, w2 w w w3 A Z0=z, voccurs in At} pr{wn t occurs in occurs in At 2 w1 (2) X(f) = 0 z2', voccurs in At} (60 28) Each state component appears at most once in the state component graph. The target state component-Z( t, i=19 2ooo, n, is determined by the corresponding initial state components, endocondition, and endocontrols oo (i) pr{zAt = z 0,I O 0 o o all occur in At, ZAt 3 V/ 1 "'2 A A /\(i) Z =Z Z z all ii3} 0Z' At 1 pr{zzt) 2 31 0 occurs in At, (3) X (b) x Xd) x } (6 29) z 0 = Z32 x XbX di (6. 29) By appropriately chaining all these conditional probabilities, A joint probabilities on ZAt and (w, 0 o0,w) (conditional on Z0. z0) can be foundo An appropriate marginal distribution provides h from Eq. (6 13), as requiredo The conditional transition probability function h is thus one long product of many, many conditional probabilities, each of which, by postulate, was found to depend upon properties observable at a single element or its ports. A collection of all those

75 for the element possessing the autogenous epoch class represents as a product, the true value of the intensity function s used in section 5. The examples were all simple enough so that this complexity did not show itself. (Most of the conditional probabilities were unity ) Some inconsistencies would surely show up if many of the stranger elements had been described. This is best illustrated by a simple exampleo Consider the epoch graph of Figure 6. 4. We must represent the probability that (X, a2, a4, a6) a!l occur in At, that X6) a6(s6)s that X(2) =a 2(s2 a6(s6)), that X(4) a 4(s) that 0() ) ) all occur in At, that,4 49 w1 w3 w5' Z = g a 2(s2, a(s)), a(s4)) that Z(t g2 ( l a6(s6)) (3)that Z 4 6 (1)s that Z g3 (s3 w3), and that Z( ) g46(s w4); given Z s ='At = g493 3 3(A't given Z~== 91' Z(2) S Z(4) = S and Z(4) = where w = a( S X a2 w3 3= (s1 a 2(S, a 6(s6)), a 4(s4)), and w 5 = j5 (S29 w1, a6(S6)). This probability is the product of the following conditional probabilities, because of the postulates [el] (1) pr{xoccurs in AtlZo() s=1 [e2] (2) pr{o2 occurs in Atlp2 occurs in At, Zoi2) S2 [e3] (3) pr{a4 occurs in Atlp4 occurs in At, Z (3)= S3} [e] (4) pr{a6 occurs in AtiP6 occurs in At, Z (4) s4} [e4] (5) pr{X6 ) = 6(S6)1 a6 occurs in At, Z4) = s4} [e2] (6) pr{X(2) = a 2(s2' 6(S6))l a2 occurs in At, X(6) = a6(s6), z(2) S2 O = S2}

e2 W5 P6 x(6) WI P2 032~~~~~0 P5 AJ/ X~~~~K N~* Pi w3'P [ e3 P4_ P3 D - x(4) Figure 6. 4 An epocn grapi.

77 [e3] (7) pr{X(4 = 4(4)a4 occurs in At, Z = s 3} (e]()p(1~) (3) (1): X [el] (8) pr() and (3) both occur in At, Z(1 g 1 (..) 1 w3 Ix occurs in At, X(2) = a2(.. ), X (4)= a4(s4), Z (1 )= s1 [e2] (9) pr{0w(5 occurs tin, Z 2_ 5 i (1) a2 and (1) both occur in At, 1 X(6)= ay6(s6) Z(2) 2 pr{Z(3) a U4 (3) [e3] (10) p AtZ = g3 (s3 w3) a4 occurs in At, Z0 = s} [e4] (11) pr(Z4t g4(s4w4) 1a6 occurs in At, Z4)= s4} The left-most margin indicates which element totally determines the given probabilityo From this we see that the intensity function is used in section 5 represents all those terms associated with the element having the autogenous evento Thus, reverting to the previous, more general, notation S: lim pr{X occurs in AtI Z (0) = S} sAt-0 x pr{wO all occur in At, Z ( g s(x) occurs in At, XQ}/t (6 |X occurs in At, XQ = x./At (6. 30) where w is a shorthand for w w. ~ o, where P1, P2,.. are in wQ 1w Q; and Where xQ is shorthand for xl, x2,... the exoconditions at the ports in Q.

78 We also see that the prdbability function 7r represents all those terms associated with the element having ak for an exogenous epoch at port Pk. Thus skf lim pr{ak occurs in AtlPp occurs in At, Z (k) - } s pt-0 o k pr{X(k) d k(xQ) ak occurs in At, XQ) XQ Zo sk} k pr{Ow all occur in At, (ZAt)k gsk (xQ Yk) Iak and w both occur in At, XQ Zx (k)= s} (6 31) Pk It should be carefully noted that neither Ps nor 7r represent s s meaningful conditional probability intensities or probabilities, because the conditions are not "chained. " However, they do represent a product of legitimate conditional probabilities, and the product of all such probabilities for the primitive epoch class v (as shown in an epoch graph) is very meaningful. It is a large joint probability whose sums are over appropriate variables results in the determination of yo(v, i)h(v, i, j)o

7, THE TRANSLATION OF NETWORKS TO EQUILIBRIUM EQUATIONS The objective of this report has been to provide the capabilities needed to specify a Markovian system in pictorial language form, and then to systematically translate the specification (we called it a diagram) into a straightforward description of the equilibrium equations for the Markov chain which models it. It was agreed that the matrix of transition intensities (uij) would suffice, provided its index set was suitably identified with the states of the system. The problem has, up to now, been almost entirely representational. However, with the background provided, we can finally take an operational view, and develop the procedure. An operatiorvcalled consolidation will be central to the procedure for translation, and the major part of this section will be devoted to its description~ Finally, its use for the task of translation will be presentedo 7.1 CONSOLIDATION OF NETWORKS The operation of network consolidation consists of forming a new network which is-equivalent to the old, but for which one connection (and its meaning) has been absorbed into the elements. There are two cases, illustrated in Figure 7. o1 Either the connection to be * We will say the two networks, N and N, are equivalent if they describe the same Markov chain (in the same state space). 79

I I -— 1 I I I I I r — -a I I — 1 I I I I I I- _,__ I~l I I I I —I r -, m I I -— L I. 1 L..-.. 6 I I I L.. I J I I t -.- - 00 C) I r -— n I I I I I I LI. F;gure 7. 1 Itlustrat:ng two cases for consolidation.

81 absorbed joins ports of two different elements, or it joins two ports of the same element. Symbolically, if the new network is N and the old is N, and if one of the ports involved is pi, the consolie - dation operation C can be written N =,(N, Pl) (7.1) The other port (p2) involved is obviously found from the connection function C P2 = C(p) (7.2) As a result of the absorption of the connection, new elements must be formed. In the first case, the elements el and e2 will be "consolidated" into a single element e having two less ports than the two elements had together. In the second case el will be replaced by a new element e which has two less ports than e1. All elements except these remain unchanged, as well as all connections other than the one between pi ana p2 Figure 7. 2 illustrates the consolidated networks. Symbolically, if we let N = (, C) then = (6 -{eI, e2}) U eo (7.3) A (We adopt the convention of defining e2 = el for case 2. ) Every connection other than the one being absorbed remains the same, so that the new connection function is simply a restriction of C to the set (P - -{p1 P2}1. (7.4)

r —--- L. ___J I I r-, —I I I I I I I I II Il L _- i I I J I _ I L___J r~ m —I I I F — I I I I I I I I L. _. _ _ J Figure 7. 2 Illustrating the "consolidated" networks for figure 7.1 b)

83 I.e., C(p) = C(p) for allpe f - {p, p2}. (7.5) Thus, the principal operation in network consolidation is the operation which determines the element e. This operation is called element consolidation. In case 1 we write that e = C'(el, e2, Pl, P2), and in case 2 we write that e = e "(el, p1, p2), where the operations (' and t" represent the element consolidation. To define these operations it is clearly necessary, and sufficient, to define a port set P, a state set S, an auto-event set a, and an exo-event set Z such that e = (P, S, -, Z) and the network N defines the same Markov chain as N. Only case 1 will be considered here. Case 2 follows trivially from this procedure for tree-structured networks. The port set P is the easiest to derive. Since every port which was a port of either e1 or e2 must be a port of e, with the exception of p1 and p2, P is obviously P = (P1 u P2) - {p1 P2}, (7.6) where P1 and P2 are the port sets of e1 and e2 respectively. This permits every connection other than the one being absorbed to remain unchanged. More will be said about the state set S later. However, it is clear that if the "condition" of the new element is to be described, the values of the state variables of both elements must be known. Therefore

84 S is at most the set S1 x S2 of pairs, or C S1 ix S2 (7.7) This is sufficient knowledge of S to proceed with the descriptions of and Z 7.2 CONSOLIDATED AUTOGENOUS EVENTS While the consolidation of the auto-events is a highly detailed operation, in principle it is quite straightforward. Each port of an element identifies, under appropriate circumstances, an endocondition function and an endocontrol function. In Section 3 we had used the schematic reproduced in Figure 7. 3 to illustrate this state of affairs, where v represents an endocondition, and w represents an endocontrol. Under other circumstances, we have said that the behavior of the element is frequently dependent upon exoconditions and exocontrols, which are schematically shown as x and y in Figure 7o 3. The endocontrols and the endoconditions were determined, as required, by the-encdocontrol and endocondition functions which defined the element. The exocontrols and exoconditions were treated as variables Unless otherwise stated, the Cartesian product operator will be taken in an associative form so that (AxB)xC = AxBxCo Thus, if S1 SaXSb and 2 SdxSc, then (a, b, c, d) SlxS2 if (a, b) e S1 and (c, d)e S2. Strictly, one otherwise means ((a, b), (c, d))e S xS2 under these circumstances.

85 4-)> Figure 7. 3 Schematic of port variables. upon which these functions depended, and were to be determined by the network external to the element —in particular, by the endocontrol and endocondition of the associate at the port. This situation is indicated schematically in Figure 7. 4. Evidently a simple substitution, representing x2 instead by the function defining v1, Y2 by the function defining w1, x1 by the function defining v2, and y1 by the function defining w2. The variables x1, x2, Y1, Y2 would then cease to exist, and everything which depended upon them would depend instead upon the variables upon which v1, v2, w1, w2 depended. Furthermore, the functions defining v1, v2, w1 and w2 could now be absorbed by defining new functions which were compositions of the e2 Figure 7. 4 Relationships of port variables in connected elements.

86 functions defining v1, v2, w1 and w2 with the functions which originally depended upon x1, x2, y1 and y2. Thus all variables or functions identified with the two ports would disappear from view. The application of this simple principle is practically all that is needed to consolidate the elements, and, in particular, the autoevents. However, considerable detail ensues from the detailed structure of the element and the auto-event definitions, and the ways in which the endocondition and endocontrol functions are buried in this structure. The auto-event sets of elements e1 and e2 are the sets -1 = {X: Xc A1} S2:X E A 2 (7.8) respectively, while that of e is { X e } ) (7. 9) where A1 and A2 are disjoint, and A is a new set of epoch classes associated with the consolidated element. Clearly, since the underlying Markov chain for the network must not change under this operation, each epoch in A1 and A2 must have a counterpart in the epoch set Ao Put in other words, each auto-event of the elements e1 and e2 represent "actions" of the consolidated elemento At first blush, one might expect that the epochs in A would correspond one-for-one to the epochs in the union of A1 and A2. This is, however, not the case.

87 As it happens some of these epochs may split into several new ones, so that A is not necessarily the union of A1 and A2. To see why this is so, consider an epoch class X.1 A1 which produces an endogenous epoch class of e1 at port p1. Since this is an exogenous epoch class at P2 (because of the connection between p1 and P2), we must look to the exogenous events of e2 to fully explore what happens. Here 2(P) = {' cre Zp}, pe P2, (7.10) and if Z contains more than one member, there will be several 2 consequences within e2 resulting from the same auto-epoch in e1. To be more concrete, suppose e1 is a server and e2 is a random switch (see Figure 7. 5). Then, when a service completion occurs in e1, P4 "O \JI Figure 7. 5 Illustrating epoch-splitting. either an endo-event occurs at port p3 or it occurs at p4. For the consolidated element, there would be two auto-epoch classes: one which offered a task out port p3 and one which offered a task out port

88 p4' This illustration also shows that, in general, the exo-events at ports p1 and P2 will also be involved in the operation of deriving the consolidated auto-events. Recall that every auto-event X of an element e is defined by s = (Q s' g, Is' X E A, s e S and every exo-event ~, (k(P) ~ (Q~ 9,a,s gs, a S), e p P, s S s s sss p e e and that Q represents the set of ports having endo-epoch classes generated by the epoch class X. The role of the endo-epoch sets Q and Qa is more clearly seen with the aid of the epoch-graphs of Figure 7 6, which illustrates two possible situations, In case (a) element el possesses an auto-event whose endo-epoch set contains the ports pil pa and Pb while e2 possesses an exo-event at port p2 ron — taining pc and Pd' In other words Q { P1l Pa, pb} and Q - {pc Pd}o Clearly, the consolidated auto-event corresponding to this is one which has an endo-event set consisting of Pa, Pb' Pc, and pd On the other hand, in case (b) the endo-epoch set for X in e1 does not contain P', so that the exo-event at port p2 will not be excited. The consolidated auto-event must have an endo-epoch set consisting of only Pa and pb. In this latter case, the consolidated auto-event must, in some sense, be simply an extension of the auto-event of el, since no exo-events at p2 are involved.

~*aouoIJUT joU^ putu sDpodO9 mUT-ejrIsT.hI 9'L ajnqT1 (q) Dd -~s- r... II / - -. I Nl /llllm _,.. iy~lCIZd (D) / I \ Pd.... za > 1 "I'l Zd Id i i 6 _i _ 68

90 From these examples, we can distinguish the following two useful subsets of the epoch set Ai~ (1) Those epochs X for which p1 E QX Call the set of these Al1o A 1 {X:X A1p1' Q (7.11) (2) Those epochs X for which p1 Q. Call the set of these A 1 A" = {tX EX A1, P Q } (7.12) Notice that A'1 and A'l together form a partition of A.1 A similar partition {A'2, A"2} can be found for A2~ Case (1) Let s S(' /3 sg s9 s) (7.13) for all sXS and Xc Ao For case (1), above, each of the auto-events of eL in A' does not involve any of the exo-events of e2. Consequently, the consolidated element e will have one auto-event for each X v A', and these events will have precisely the same influence on the ports of e as did et. Therefore, let A1 be contained in A, and write QX QX (7.14) for all X e A'1 C A. Further, recall that if QX - {p, p b',. Pz} then f3 is a function on I xI x...xI to I xI x.. oxI, representing S1 Pa P P P a Pb Pz the endo-controls at the ports of Q, as functions of the exoconditions at the same portso These are all unchaged by the consolidation so that

91 we write X(s s ) s (7.15) (-x s^) xS for all s1 e S1, (s1, s2) e S SxS2, and X e A' C A. Still further, gs g s is the target state function, which is a function of the exoconditions at the ports of Q, to the set S C S x S2. The second state variable will be uninfluenced by the event so that g (S, S2) s1 (g, S (7 16) for all s1 e S1,.o, etc. Finally, the probability intensity of the epoch is also unchanged, so we write f (s1, S2) S1 (7017) for all sl e S1.., etc. This defines the auto-events for all X e A 1~ An interchange of the roles of el and e2 will define the auto-events X for all X A'1. Case (2) For case (2), things are a little more complicated. Besides the situation illustrated in Figure 7. 6, one can encounter the situation (the "random exo-event") illustrated schematically in Figure 7. 7. In this case Sp (see Eq. ( 7 10)) consists of two elements a and ob, and as a result the epoch X is split into two epochs in the consolidated element (with a probability intensity which is that of X split between the two new

92 el e2 Pb Pi Pa f_ Pd N N' \ o ________Pa P Pc (a) el e2 Pb P P2 2'b Pd / Pa Pc (b) Figure 7. 7 Illustrating epochs and their influence.

93 epochs). One of these has endo-event set {Pa' Pb' Pd} and the other has endo-event set {pa Pb, Pc} In general each epoch class in A" a b c I1 will result in as many epoch classes in 1 as there are elements in. We can thus name these new epochs by the double (X, a) e A x Z P2 1 p2 and let A A A" x S. Similarly, each epoch in A" will result in -- 1 P2 2 epochs corresponding to the elements of A" x S. Furthermore, 2 p1 there can be no epochs of e other than those mentioned so that we say A A'1 U2 A'2 x p)) u(A x Z ). (7.18) We now define the \ for X E (A'" x s ) Observing Figure 1 P2 7. 7, the endo-epoch set is easily defined as Q(X, ) X QX - P{p} (7.19) for all X E A"1, and a e Zp. Then, for the example illustrated, _(X, ff) Q - pa Pb' P d (X, a%) Q {Pa9 Pb P C}- (7~ 20) The consolidated endo-control function a must be a func(sl' s2) tion on XJ' ) to J(' a), where I(' a) = I xxI..XI x xl Xo xI, Pa Pz a P z XPa' PzUQ-p {pa ** PZ, -,...,p1} {t ~~, ) =P QO, andIp = {0, 1, 2,...} for all p e P. Let us define the components of Js' ) by (Sl, s2) X 0 } Y 2Do ~ P * 1 0 / )a (7 21) (S1's2) P= Pz Pa Pz

94 the components of i by s2 31 (Pp (,**.*..,, p 3 ), (7. 22) a! Pa the components of i by S2 fi~ == (3,...,3,,j3 ), (7.23) s2 Pa Pz 23 and the endocondition function at port P2 by a, for all X e A" and P2 P2 1 all a e E. Then the first group of components of /(, a) is found P2 a (s1' s2) from b by replacing x by a (x,,...,,) as follows p(x,..., X, xp,..Xp, ) = 3p (Xpa,...,x,a (Xp, 0,..Xp, )) p Pz paz P P za Z P2 Pa PZ (7.24) for all p {pa 0..., pz} and all (sI s 2) e S, X E A"1, and J Z P a z 1(X p a The second group of components of (S, s ) is found from s by replacing the exocontrol y2 by Sp (x,.., x, aP (xp,.o., I)) so that p(x,..., X,,...,X ) = P (x,., 3 (xP... aZ ( a a7.25) x,a (x,...,x, ))) (7.25) PZ P2 P a p z for all p E {p',...,Xp' } and all (si, e SXe A" and a S. Pa z 2 E p

95 The formation of the target state function g(X' ) proceeds sim-(X, a) s(Sl' S2 ilarly. Let the components of g(s' s) be defined by s(X, o) 1 92) (7.26) g(s1, s2)= (gl'g2) for all X A" 1 and all a e S Then P2 - X a gl(xxXp,,...,xxp,...,xp) = gs (xp,...,x Pa (xp,..., Pa Pz a b 1 aPz P2 a x, )) (7.27) z and g2(xp P.,,x,,x )gU 2(x,a..),,xg Pa Xp, )-s2Xp,, O e oXpa ))) P a Pz for all (s1,' 2) S9 et.o The probability intensity of the epoch (X, a) is found by multiplying the probability intensity function /j of the autogenous event X by the s1 conditional probability function 77T of Ca given that the epoch (in this 2 case X) occurs. Thus -x AS o) - i1, S7 e. o 28) ~~s!~~~~ P2 - 5 1-X The remaining elements of — those for X e A" x Z -are s 2 p found by repeating the procedure with the roles of p1 and p2 reversed.

7.3 CONSOLIDATED EXOGENOUS EVENTS The exo-event sets of elements e1 and e2 are the sets z1(p) = E S} pe P1 (7.29) 2(p) = { a Sp} pE P (7.30) respectively, while that of e is (p) = {( Ea Ep} pE P. (7.31) p Since the event sets Z1 and Z2 represent the consequences of epochs determined externally to their respective elements but identified with a port, they must continue to be described in Z. We have already seen how the exo-events corresponding to Z and Z are accounted forpi P2 they are absorbed into auto-eventso On the other hand, if an exo-event produces an endo-epoch class on p1 it is clear that A, a e, must influence the exo-event in much the same manner as for auto-events. In fact, the consolidation of exo-events follows that of auto-events almost exactly. Figure 7. 8 illustrates some typical situations for epochs observed at a particular port, say pao In case (a), the epoch aLi c Z generates an endo-event at pl, which in turn excites the external epoch a2 e Z. However, as seen in case (b), it is possible that an P2 external epoch a1 can fail to involve a2. It is also possible that more than one external epoch can be randomly excited by a1 as suggested by (a) and (c). 97

98 e2 Pa es- - N. Nl. N %. 0^ —"N PI P2 Pb Pd (a) -2 - / v Pc e2 Po \\ k/ N Pl P2 2 \ I / PC el Pa I (T (b) PI P2 Pb Pd (C) e2 3 F,...,N PC Figure 7. 8 Illustrating externally determined epochs and their influence.

99 We recall that every exo-event of an element e is of the form sa = (Q s a,3,g s' ), a e Sp, pE P, se S, (7. 32) s s s s s p e e and that Q represents the ports excited when the external epoch a is excited (at port p). We again distinguish two useful subsets of every Z for every p e (P1 - {P}): (1) Those exo-epochs a for which p1 i Qa. Call these Zp SP = {a:ae, P Qa}. (7 33) (2) Those exo-epochs a for which p1 e Qa. Call these S' p "p = {a:ae Zp, p1 QE }. (7.34) A similar partitioning for p E P2 can be found by replacing P1 by P2, Pi by P2, and S1 by S2 in the above Case (1) Let - U(Y -U -U -r -a s (Q a, s, s, s7Ts) (7 35) for all s e S and a e S, p e P. Let Z' be contained in p, and let Qa Qa (7.36) a0. = a~ ~~(7.37) a(Sl'S2) Sa 7 (S s 52) f s (7. 38) -a s (g (7 39) g(s1, S2) 1 s2

100 and 1 (s1 s2) = S1 (7.40) for all (s1, s) S, a E 7P, P e P1 - {P } Then as are the exoevents of e corresponding to the a: S, p P1 - {P1} The a for e Z7ps p e P2 - {P2} can be found analogously. Case (2) In this case, there will be an exo-event of e for each element E" x E p P - {P}; and analogously for each element of Z' x S P P2 P p I, p e P2 - {P2}. Consequently, we let S (p x S for p ^ 1P C'p U (C'lp X C~~ P P 2P P {p } and Z-' U(L' x ) for p P2 - {. 2} he ^ 1. P PI P Pj 2 A exo-even, set Z(p) ~- e S pP P= PI UP 2- {PlP 2}, (7.41) will be a complete set of txo-events for e. The r for or Z p x S p ( P1 - {pl}, are defined very analP P2 ogously to the way the X were defined. For example, the endo-epoch set Q( is given by (ro1o, _) 1 or Q QI- (Q 1P }L) Q (7. 4) The basic sequence for the formation of the endocondition functions, endocontrol functions, target state functions, and conditional probabilities for this and the "reversed roles" case will not be detailed here. It is notationally tedious, and will add little to understanding which the

101 previous cases have not already provided. 7.4 AN EXAMPLE OF CONSOLIDATION Element consolidation ('(el. e2' p1, P2) will be performed to illustrate the technique. In this case e1 will be a queue, and e2 a server. The output of the former is connected to the input of the latter, and it is this connection which is to be absorbed (see Figure 7. 9). Po PI P2 P3 Figure 7. 9 Queue-and-server consolidation. From Table III we take the following data, with a slight change in notation. (Every equation in this section is assumed to be valid for all s e S, s e S1, s2 e S2). The Queue (1) Ports: P1 = {P' P.} (2) States: S1 = 0,1,...,N} (3) Auto-event set:,1 = 0 (4) Exo-event set: Z (P0) = a~1 )} 1 {o11} s1 l(Pl)

102 (5) Exoevents: alO (a):s1 Qs1 a1 0 Q a10 = (o, 10 0 aO 0 a10 11 1 = {pl} a10 a1 (1) = N-sl +1 a1o s1 (Xl'Y = slYO gs (X YO) = [Sl+yO-Xl]o S1 al (b) s11 11 Q all all al all all 1 a 1 1 Sa 1 1 = (Q { where = {Po} a11 1 (Xo) = N-Sl+X0 all 1 (X0 Y1) = N-Sl+Yl allxo ) = gs (Xo Y) I Sl-y+Xo]N s 1 1..l -' 0

103 111 S1 = 1 The Server (1) Ports: P2 = {P2P3} (2) States: S2 = {0,1} (3) Auto-event set: 2 = {s } (4) Exo-event set: Z 2(P) = {22} 2 Z2(P3) { 23 2 (5) Auto-events: x s2 (Q,,g', M ), where S2 S2 s2 Q = {P2 P3} X A s(x2 x3) = (Ix (J+), ) ((x2, x3), 32 x3)) gs (x2' 3) = I(J+)I ({0}) 2 2 3 X s2 y I ({o}) 2 (6) Exo-events (22 (a)?22 S2 a22 a22 a22 a22 a22 =(Q'a's'gsg' ), where 2 2 S2 2 Q22

104 o22 s2 = 1 -2 o2 2 a2 gs (y2) 2 = 1-I ({0})II ({0}) Y2 s2 (b) (23 a22 IT 1 Q23 023 323 (Q?,a2,2 22 S2 ~23 gg 52 a23 7T ), where s2 a23 s2 2 23 s 2 = 0 23 S2 a23 g (Y3) 2o = 2 23 s7 s 2 The Consolidation (1) Ports: The port set is P1 u P2 - pl - P2,' hence p = {P' P3} (7 43) (2) States: The state set S is contained in S1 x S2 S C {0,o,oo.,N} x {0,1} hence (7.44)

105 (3) Auto-events: Let d, s e S, be the consolidated auto-event resulting from the autoevent ( of the server. Let S2 = -x x -x -X 5s = AP, S). (7. 45) Then, since Q = {2, p3}, the epoch X gives rise to an exoevent s at p1 (which is connected to p2), and by Eq. (7. 19) (with roles of p1 and p2 reversed). Q = Q u Q - {P2} = {P' P3} (7.46) To obtain the endocontrol function 3 S(X0, x3) which has two components which will be called /3 (xO, x3) and / 3(x 0 x3), we adall al X join s (from s ) and 3 (from ) leaving s^s3) = 3) ( 3)) ( s (O Y1) 3(x2, x3)) = (n-s+yl 1) Then we replace y1 by the endocontrol 32(from x ) to get 22 -x (7o 4+) s (x0,x3) =(N-sl+I (J),1) (7.47) 3 Since this does not involve x2, the exocondition at port 2, no further substitutions are necessary, and Xs is described for all s = (s1, s2)e S. S'X To obtain the target state g s(x0, X3) which has two components (g 1(x, x3), g 2(x, x3)) we adjoin ggs (O, y1) and gs (x2,x3), pro2 2 duc ing x W x I011 x g s(X,3) ( 1 3) = 2(x0, x3)) = (gs (x y1) g (2, 3)) = ([sl-y1+K], I (J ({0})) (7.48) O x 2 1 3(

106 by 11 Replacing yj by h 2(x2, x3) and x2 by a S (xO), and noting that n-s1+x0(J ) = I (J+)I (J ) because of the non-negativity of N-s 0 ns- xs and x0, we obtain gs(xO' x3) ([S-x N-s1- Ix3((J+)+ I (JI ) X({})) -X which is the final form for g. -X X al Finally, to obtain/ S, we take the product of z s and 7L to ~~~s ~~sg~2 s1 get M s = yIs ({0}) (7.50) (4) Auto-event set: = { } (7.51) (5) Exo-event set: Z(po) = {( 0} s a3 Z(P3) = {s }(7.52) (6) Exo-events: (a) Let the exo-event at port 0 of the consolidated network be rs (Q acS fis'gs s T) (7 53) alO Then, since Qs = {1}, an exo-epoch class at port 0 produces, in 1 turn, an endo-epoch class at port 1 and an exo-event at port 2. Thus al 0 22 and ~ are involved in this exo-event. We have s1 s2 a0 U 10 a22 a Q1 U QU Q -{p1} = 0. (7.54) -0 For the endocondition function a at port 0 we have s

107 -_0 a10 as - = (x N-sl+x = (7.55) s22 Replacing x1 by a, which is 1-s2, we get finally 2 -a0 as = N+1 - (s1+s (7. 56) s -0 -a0 Because Q is empty, the endocontrol function s3 specifies the endos control at no ports, and hence is a null function 0 (has null range and domain). This would also be found through systematic procedure since a22 a -= d. also. Thus s2 2 s 0 e (7. 57) -0 The target state gs (Y0) has two components, and we let _U 0 0 -0 gs (Yo) =(gl (Yo)' g2 (Yo)) These are found through the substitutions -aO -a 0 -aa0 l 22 gs (y0) (gl (YO) g2 (YO)) (gs (XlY Y)g2 (Y 2)) ([s+yo -x, 1-Iy ({0})I ({0}))o (7.58) -i v i-v 0 Y2 $ 2 U10 22 Then replacing Y2 by 01 (x1, y0) and xl by a, we get 1 2 gs (Y0) = ([Y0+(Sl+S2)-]1N gNy) =( ([yO(s8+s2)-1]' 1s0 -Is+y0({0})Is2({0})) = ([y0+(+s 2)-1]0, 1-Is ({0})I ({0})Is ({0})). (7. 59) 1S Y0

108 -0 a10 22 Finally, T,22 or S S1 S2 a 0 = 1 (7.60) (b) Let the exo-event at port 3 of the consolidated network be a ( 3 _a3 (a 3 0a3 Ps = (Q a's'is,gs's ) (7.61) -~23 Then, since Q s = 0, an exo-event at port 3 produces no endo-events 2 r023 at any other ports, and only _ is involved in this event (i. e. this s3 is a case (1) consolidation; see Eqs. 7.36 through 7. 41). Consequently a3 Q3 = 0 (7.62) a3 a23 a: = a 0 (7.63) s s2 /3 = j0 (7.64) a-3 a23 gs (Y3) gs (Y3) - s2 (7 65) -a3 23 Trs = 7s =1 (7.66) This completes the consolidation. A careful examination of each of the properties of this element reveals that its description is exactly the description that would be expected. This definition is the representation of a new element, which could be added to our list of primitive elements (Table I).

109 7. 5 CONSOLIDATED STATE SET The set S has not been defined, except to say that it is contained in the Cartesian product of SL and S2, S1 x S2o The various functions representing target states, endoconditions, and endocontrols were said to be functions on this set. As a matter of fact, however, they have all been well defined over the larger state S1 x S2. Nevertheless, S1 x S2 is generally much larger than necessary, since there are many states in it which the process would never return to once leaving. In fact, a great many states are left as soon as any epoch occurs within their element, A state s is said to be essential if a return is possible from every state to which s leads (see Ref. 1)o Since the equilibrium probability of an inessential state is zero, little is lost in omitting it from the model. However, unrecognized inessential states can waste memory in a computation. Moreover, in typical RQA-1 models, the ratio of inessential to essential states when a Cartesian product space is used is often ten to one, and could be considerably greater. A foolproof scheme to eliminate all inessential states with reasonable computation is very desirable, but difficult to produce. However, techniques which are very effective, but not perfect, can be devised. Mostly they involve deriving constraint equations from the target state functions. This problem will be treated in a later work.

110 7 6 REDUCTION OF A NETWORK TO A TRANSITION INTENSITY MATRIX With the establishment of a well-defined consolidation operator, the problem of deriving the transition intensity matrix from a given finite network has been solved. For, by successively applying the consolidation operator to each connection in the network, one can ultimately reduce it to an equivalent network which has no ports and only a single elemento If it has no ports, then this element also has no exogenous events, and the autogenous events are extremely simple. There are no endocontrols, endoconditions, or endo-events. We observe that N*' ({e*}, 0) is the limit network, where,0 represents the null (connection) function. The element e* must have the form e* (S9 I, 9 A ) (7 67) where _ X {: A} (7. 68) and - (pg, s)~ (7.69) 5 Notice that;a is simply the probability intensity of a primitive epoch s and that g is simply a transition function g S -So (7. 70) Thus S can be looked upon as a collection of matrix elements, so that if

1ll X Xx. we map S onto a set of integers, and let j = g i, then gi is a probability intensity that a jump will occur from state i to state j. This is clearly just another form for the transition intensity matrix. 7.7 NOTES We have succeeded in obtaining what amounts to a definition of a queueing network. That this is a useful definition, one which adequately models real-world queueing systems, can be argued from experience and the rather intuitive way the model has been built up from the "kinds of things we want to talk about." This report has attempted to be formal in its notation and definitions, but not in its arguments. To have attempted to pose formal arguments at this point in the development would have significantly delayed publication (perhaps indefinitely), and thus delayed the progress that inevitably comes from the interchange of ideas with others. Nevertheless, it is believed that an axiomatic structure, and an orderly theory can eventually be built around the arguments and results presented here. It is further believed that the notions developed can be readily extended to networks which are not treestructured, and to networks which must be modeled by semi-Markov processes rather than Markov chains.

112 References [1] Chung, K. L., Markov Chains with Stationary Transition Probabilities, Springer Verlag, Hamburg, 1960. [2] Wallace, V. L. and R. S. Rosenberg, "RAQ-1, The Recursive Queue Analyzer,' Systems Engineering Laboratory Technical Report no. 2, Electrical Engineering Department, University of Michigan, February 1966. [3] Sutherland, W. R., "The On-Line Graphical Simplification of Computer Procedures, " Ph. D. thesis, Electrical Engineering Department, Massachusetts Institute of Technology, January 1966. [4] Gordon, G., "A General Purpose Systems Simulation Program," Proc. Eastern Joint Computer Conference, Washington, D.C., December 1961. [5] Morse, P. M., Queues Inventories and Maintenance, John Wiley and Sons, New York, 1958. [6] Irani, K. B. and V. L. Wallace, "A System for the Solution of Simple Stochastic Networks, " Technical Report 31, Systems Engineering Laboratory, Department of Electrical Engineering, Uni versity of Michigan, Ann Arbor, 1969 also Technical Report no. 14, Concomp Project, Computing Center, University of Michigan, Ann Arbor, 1969. [7] Randall, L. So, I. S. Uppal, G. Ao McClain, and J. Fo Blinn, "An Implementation of the Queue Analyzer System (QAS) on the IBM 360/67, " Technical Report 43, Systems Engineering Laboratory, Department of Electrical Engineering, University of Michigan, Ann Arbor, 1969; also Technical Report 22, Concomp Project, Computing Center, University of Michigan, Ann Arbor, 1969.

-113 UNCLASSIFIED j I! 1 I J i I f I i I T I I Security Classification DOCUMENT COINTR L DATA - R &:' {Securitv claas:firation of ttle, bod y C ora:: r..iorr:.;. assie.-.; rector ips. c, 1. ORIGINATING ACTIVITY (Corporate author, 2-.:'.:RT' SECUR.TY CLASSIFICATION CONCOMP PROJECT,ROUP 2 b. GR OUP UNIVERSITY OF MICHIGAN 3. REPORT TITLE ON THE REPRESENTATION OF MARKOVIAN SYSTEMS BY NETWORK MODELS 4. DESCRIPTIVE NOT.ES!Type of report end inc..sive dates) Technical Report 21 5. AUTHOR(S) (First name, middle initial, last name) VICTOR L. WALLACE 6. REPORT DATE J7-. TOAL-. 0. OF PAGES bo. NO. OF REFS August 1969 112 7 8a. CONTRACT OR FGRANT NO. Sa. ORIGINATOR'S REPORT NUMBER(S) DA-49-083 OSA-3050 | Concomp Technical Report 21 b. PROJECT NO. i9b. OTHER REPORT NO(S) (Any other numbers that may be assigned c. this report) SEL TR 42 10. DISTRIBUTION STATEMENT Qualified requesters may obtain copies of this report from DDC. _..,,,,,,, 1 i1. SU':sEMN.' in RY N`3EiS.2. SPONSORING MILITARY ACTIVITY Advanced Research Projects Agency ______________________________________________________________ I I I t i I 13. 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 decomposition and recomposition of Markovian queueing networks is presented, and applied to realistic queueing networks. DD 1 NV 651473 UNCLASSIFIED Security Classification

UNCLASSI ification.- Security Classification -114 l 14. LINK A LINK B LINK C KEY WORDS I... IIRROL E |WT ROLE WT ROLE WT pictorial language Markovian queueing networks networks mathematical modeling -1 I I I I I UNCLASSIFIED Security Classification