tijflSMfiffiipnl] IllHi ■Hi m H ma Mm IIP 111 mmm LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 510.84 no."77 — Tandem Queues with Feedback.... l6 2.U.1 Multiple Channels in Series and in Parallel l6 2.4.2 Cyclic Queues with Feedback 18 2 . k. 3 A Two Stage System ■ 19 2.k.k Two Stages and Feedback and Blocking 21 2 . 5 Final Remarks 23 3. THE MODEL OF A SPECIALIZED INFORMATION RETRIEVAL SYSTEM 2k 3.1 Basic Definitions 2k 3.2 The Model 26 3.2.1 The Tandems of System 29 3.2 . 1. 1 Probability of a Nonempty Stage 30 3.2.1.2 Probability of a Processor being Busy 33 V 3.2.2 The Source of System 3.1 3^ 3.3 Applications of the Model 37 3. h A Double Feedback System kO k. A NUMERICAL SOLUTION OF THE EQUATIONS OF THE MODEL kl k. 1 The Model when Blocking is Allowed kl k.2 A System with Two Waiting Jobs Allowed for Each Processor ^-1 k.3 The Equations of System k.l k3 k.k A General Solution for the Equations of System U.l k$ k. 5 The Source for a System of Tandems with Blocking 50 LIST OF REFERENCES 51 1. INTRODUCTION In this paper we study several queueing models of an information retrieval system described by Stellhorn [1]. This system utilizes an inverted file organization. An index file contains an entry for each of the terms selected as descriptors for the documents in the data file. Each entry in the index file points to an inverted list of pointers in the postings file. The latter points, in turn, to all documents in the data file that contains the corresponding index term. A query to such a system is in the form of a Boolean expression of index terms. The system replies to a query by accessing the list corresponding to the index terms, merging them and finally, selecting from the merging list those documents which satisfy the Boolean expression. Several probabilistic models for such a system have been analyzed in [h]. These models assume that the disk and processor are lumped into a servicing unit. We model this system here as one composed of two servicing units, i.e., a disk and a merger. (We shall refer to these units as servers 1 and 2 respectively, or as processors, in the broadest sense. ) These two units are cascaded such that a job is processed first by the disk and then by the merger, and queues are allowed to form for each of the servers. Furthermore, some of the jobs departing from the second server are fed back to the queue for the first server. Figure 1.1 shows a schematic description of the model. 5^ -P H H •rl

0). 2 . 2 The Systems where P =0 — Simple Queues in Tandem The basic system considered here is one in which there is no feedback from the second server to the first queue. Two interarrival distributions have been considered--Markovian and arbitrary. 2.2.1 The M/M/l System This system is the one most widely treated in the literature (for example: [6], [7], [8]). Most of the results were obtained for systems in which: (a) Waiting is allowed before both stages. (b) No blocking is allowed between stages (i.e., queues are arbitrarily large). (c) The system is heavily loaded (i.e., the first queue is infinite). A very interesting property of these systems is that, in the steady state, departures from the system are also Poisson with the same parameter X as that of the input [8,9]. This result is summarized in Burke's Theorem: The steady state output of a queue with c channels in parallel, whose input is Poisson with parameter \ and the servers in the channels have the same exponential-service-time distribution with parameter u is itself Poisson distributed with parameter \. Reich [10] showed that if the arrivals and departures of a single channel queue are Poisson distributed, then the service time is exponential or a step function at zero. Let l(t) be the probability distribution function of the interarrival time and S, (t) and Sp(t) be the probability distribution functions of servers 1 and 2, respectively. In this case, I(t) = 1 - e" Xt , t>0 (2.2.1.1) and The greek letters A. and u will be used throughout this paper to denote interarrival rates and service rates, respectively. S 1 (t) = 1 - e'^1* (2.2.1.2) S 2 (t) = 1 - e"^" 1 (2.2.1.3) The following results are known [8] : 1. Probability of having n, jobs in the first phase, ru jobs in the second phase is P(n x ,n 2 ) == Pl x p 2 "(l- Pl )(l-p 2 ) (2.2.1.4) n 1 n 2 where p. denotes the traffic intensity of the i phase and are given by p, = — ; Po - — (2.2.1.5) 2. Expected number of jobs in the system is P-, P ? E(n) = tpi- + t^- (2.2.1.6) 1-p 1-P 2 ' 3. Expected number of jobs being served in the system is E g (n) = P-l + P 2 (2.2.1.7) k. Expected number of jobs waiting in the system is E (n) - E(n) - E (n) w s 2 2 P l P 2 7 5. Let f . (| ) be the probability density function of the waiting time for a job going from the (i-l) phase to the i phase. In this case, f, (0 = Ml-P, ) e (2.2.1.9) The probability density function of the waiting time for the overall system is f s (0 = f x (0 ® f 2 (l) (2.2.1.10) where f (t) ® f 2 (t) £ I f ( T ) f 2 (t-x) dT (2.2.1.11) J 6. Probability that n jobs are waiting in the system P (n) = ft 1 ) p n (l-p) 2 = (n+1) p n (l-p) 2 known only when (a, = m~. 7. Expected waiting time E(w) = J [|Ml-P x ) e + |A.(l-p 2 ) e ] d| Mi- Pl ) Mi-p 2 ) (2.2.1.12) (2.2.1.13) 8 2.2.2 The G/m/1 System Let A.(t) denote the probability density function of the interarrival time. For the first queue the arrivals are distributed as A(t), We consider the case where the mean time between arrivals is l/\. Service times of both servers are distributed exponentially with mean l/i-i. The utilization factor is defined as P = £ (2.2.2.1) The following results are known [7] : 1. The probability that k jobs remain in the first phase at time t is \ = lim P n-*co ( V k) ;2.2.2.2) A where q = number of jobs found in the system immediately prior to the arrival of C (job n). We then have n r^ = (1-a) a% k = 0,1,2, (2.2.2.3) where a is the (unique) root of a = A (|a-ua) (2.2.2.U) (The * operator denotes the Laplace transform. That is, (2.2.2. h) is equivalent to the integral equation a = P e- ( ^ ua)t dA(t) -'O (2.2.2.5) ). 2. Let w(£) be the probability density function of the waiting time. In this case w(0 =1-0 e-^ 1 " )^; | > o (2.2.2.6) 3. The expected waiting time is then k. The probability that the server is busy is, therefore 00 00 P(busy) = Z a = 2 (l-a) a k - a (2.2.2.8) k=l k=l Assuming that the system is heavily loaded and in the steady state, we have that the output rate from the system is given by \ = an (2.2.2.9) The fact that the output distribution is geometric, forallinput distribution is of extreme interest. Now we can look at the second phase of the tandem as an M/M/l system. Then, for a two phase G/M/l tandem we have a G/M/l-M/M/l configuration. Hence we have the following results: 1. Probability of having k jobs in the first queue, k p jobs in the second queue is given by k k P(k x ,k 2 ) = (l-a) a 1 (l- p ) p 2 (2.2.2.10) 10 where f 00 -(n,-n,a)t ff = / e dA(t) (2.2.2.11) and P=- = — (2.2.2.12) 2. Let the probability density function of the waiting time be w(£). I"t is given by w(|) = f(|) © g(|) (2.2.2.13) and -n,(l-(r)s f(|) = 1 - ae x (2.2.2.114) ;U) = \(l-p) e * (2.2.2.15) 3. The expected waiting time is given by 1 u-u-M 2.3 The System s where P _ = 1 — Cyclic Queueing Systems f In these systems, a job arrives at the first phase is served by both servers and always returns to the first phase, i.e., the system is closed. A schematic of such a system is shown in Figure 2.1. 11 CO H -p w CO o •H H O >> o H CVJ* Q) 12 2.3.1 A Cyclic System with Restricted Queue Lengths Gordon and Newell [11] analyzed. closed, cyclic systems and for the cases considered, they proved that these systems are stochastically equivalent to open systems in which the number of jobs is a random variable. They assumed u servers in tandem and, furthermore, they allowed only a maximum of M jobs waiting before each stage. The probability density function of the service times is assumed exponential for all cases, with parameters p.,, u p , ..., u. for i servers. We summarize some of their results in the following. An open system of tandem queues with exponential servers and restricted queue lengths is a special case of a cyclic system [11]. th Assuming the number of jobs in the i queue may not exceed M. , we have that the steady state distribution of the number of jobs is given by the solution of the difference equation M { z ^e.Cn.) 6 1+1 (n 1+1 )} pCvv-'V = 1=1 M * ^ S.(n.) E. +1 (n. +1 ) P(n 1 ,...,n. + l,n. +1 -l,...,n M ) (2.3.1.1) i=l where u. is defined as above. P(n 1 ,...,n M ) is the probability of having n , n , ..., n^ customers in the 1 ,2 , ..., n stage respectively, and n. = € i (n i } n. f l ' 13 n. = m. 5 i (n i ) = ( (2.3.1.3) 1 n. 4 M. l ' l Equation (2.3.1.1) can be solved in some special cases. In particular, for a two- stage tandem n-k^ P^n) = (^) P 1 (k 1 ) (2.3.1A) Here, P-,(n) denotes the equilibrium probability distribution, since for this case n +n = N, and P(n , n ) is redundant. Also k x = max(0,N-M 2 ) (2.3.1. 5) 1^ - min(N,M ) (2.3.1.6) Since n -,+Up = N, we have P x (n x ) = P 2 (n 2 ), in equilibrium, (2 3 17) when M-, = Mp. In the steady state P 1 (n) = (^/(i 1 ) n {[l-(^/M 1 )]/[l-(n 2 /u 1 ) N+1 ] ) (2.3.1.8) which is geometric as N-+00 and Kp/V, > 1. The mean flow rate of jobs through the system is given by F = ^{[i-^/uj/'VlM^/^)*]} (2.3.1.9) 11+ where R = 1 + (kg-l^) (2.3.1.10) 2.3.2 A Diffusion Approximation of a Cyclic System Rather than utilizing a standard birth-death analysis, diffusion processes with two reflecting barriers have been used to approximate the behavior of the system shown schematically in Figure 2.2 [12]. The steady state distribution of the number of jobs in the system is then given by F(n) = (l-Be 2 ^ n / a2 )/(l-Be 2 ^/ a2 ) (2.3.2.1) 2 where p. is the drift and a is an infinitesimal variance associated with the diffusion process. B is given by B = E(s)/(E(s)-e 2 ^ a ) (2.3.2.2) for N=l; when N=2, B is given by 2 2 B = E(s)/{E[max(S,D)](l-e^/ ff ) + E(s) e k ^° } (2.3.2.3) where D and S are the parameters of the random variables D(t) and A(t) respectively. Let N (t) denote the number of jobs present at the server 1 at time t, including those queued in addition to the one being currently serviced. Then, if N (0) = 0, c N c (t) = A(t) - D(t) 15 CM >> K OJ 1 «— •P K •H W 43 w 1 4 ^ H (Ti r-\ •H -P « Cl Ph «- d o H ca M 16 where A(t) represents the number of arrivals at server 1 in (0, t), and D(t) is the number of departures from server 1 in (0, t). As t becomes large A(t) and D(t) are approximately distributed with means t/E(D) and t/E(S) respectively. E(x) denotes the expected service time of a server with parameter x. Further references in diffusion approximation may be found in [13,1^15]. 2.k The Systems where P > — Tandem Queues with Feedback The feedback condition (P > 0) makes the analysis more complex than in the two cases considered before. It is a striking fact that, while the literature has developed extensively around single-stage queueing systems with open loop and with (possibly) multi-stages closed loop systems, systems with feedback have been neglected. When only one server is assumed, interarrival times are exponential, and the service time is fixed, the results are (in the discrete case) those of the round-robin scheduling discipline (as may be seen in [6]). However, assuming only one server and arbitrary service times and interarrival times, leads to an analysis like Liu's [h]. R. R. Jackson [16], Finch [17], Franta [18] and Reiser and Konheim [19] have considered the problem from different approaches as will be seen. 2.I4-. 1 Multiple Channels in Series and in Parallel R. R. Jackson analyzed a system with the following characteristics: 1. Each phase m contains r servers. m 2. Arrival of jobs from outside the system to stage 1 is Poisson at mean rate K. 17 3. Service times are all exponentially distributed with mean H . No jockeying is allowed. h. Once a job is served by server m it goes (instantaneously) to phase k with probability 6 . Following a birth-death analysis, we have m P(n , ...,n m ) = P(0,...,0) n b(n k ) (2.1*. 1.1) i=l K where o. is defined as — *■ < 1 and — (r kPk ) , r^ <_ r n> "K'K' K k ■ \> (2.)+. 1.2) m oo m H 2 b(n.) =* n A., j=l,...,fc (2.1+.1.3) i=l j=o 3 j=i J and m P(0, ...,0) = n l/A. (2.U.1.U) 3-1 ° Clearly, our two- stage, single feedback tandem system is but a very restricted case of the above system, and Jackson's equations would very nicely fit in the model if it were not for the (basic) assumption of exponentially distributed interarrival and service times. Furthermore, this set of equations only deals with the number in the system. Other parameters of interest (such as waiting time and busy period) are not dealt with. 18 2.4.2 Cyclic Queues with Feedback Finch treated the problem in a more restricted context, allowing feedback only from the last server. For this terminal feedback system, again assuming negative exponential distributions with parameters \ and |i we have n l "2 and P( ni ,n 2 ,...,n m ) = (X 1 ) J -(X 2 ) *... (X m ) m P(0,...,0) (2.4.2.1) X = \(1-P+P +...+P )/[u (1-P)] 3 = l,...,m (2.4.2.2) J J J m P = 2 p. (2.4.2.3) where P. is the probability that a job is fed back. J It should be noted that N (the number in the equations) is assumed fixed. Then, this system of equations has a unique solution. When N = °° and each X. < 1 we get the familiar J m n. P(n-.,...,n ) = n (X.) J (l-X.) (2.4.2.4) 1 m . , t i 3 0=1 which is, of course m n. P(n ,n ,...,n ) = IIp J (l-p) (2.4.2.5) 3=1 J d Let P.(n) be the probability of n customers at the j phase. Then P (n) = P*(l-p.) (2.4.2.6) u J J 19 Hence, the average number of customers in the j phase is l 2 n P (n) = p.(l-p.) (2.4.2.7) n=l J J J and average number of customers waiting in the j phase is L (n-1) P.(n) . p^(l-p.) (2.4.2.8) n=l J J J It is interesting to note that, under exponential assumptions and a heavily loaded system, these results are equivalent to an open- loop tandem. 2.4.3 A Two Stage System Franta [18] considered a system which has a double queue at the first stage, where the customers being fed back enter the queue closest to the server, whereas those that are newly arriving join the outmost queue, as shown in Figure 2.3. This system is characterized, in the author's notation, as 1/M//1/M//0 < N < N„, i.e., l-Markovian/l-Markovian and the number in the system is variable but the number of jobs, N, in the system is < N (again, in the author's notation). The expected flow time is E(F) = N/[n 1 P 1 (l-p)] (2.4.3.1) The nature of the analysis is such that any results are very limited, as becomes apparent by noting that equation (2.4.3.1) is the only one of any relevance for our purposes. Although the restriction N < N n is interesting since in any practical system N cannot be kept as large as 20 CM >■ CM 1 r-H A> >. -p w CO O VI VI o CO CVJ* 21 desired. On the other hand, precisely because of this restriction the scope of the solution is so limited. 2.h.k Two Stages and Feedback and Blocking When blocking at the second server is considered, the following results were obtained [19] from the model shown in Figure 2. k. The generating function of the probability of having M-j jobs, P M-j( Z )' is given by 0-1 P., .(Z) = A.(Z) P.,(Z) + I A. (Z) P A ., . , (2.k.k.l) K. — U where M is the maximum capacity of the queue before the second server and A Q ^ 1 (2.k.k.2) A l =| ta(Z)^] {2.k.k.3) A -| [a(Z)A -b(Z)A ] (2.k.k.k) with a(Z) = \(1-Z) + a + p (2.k.h.5) and OC and p are the service time parameters, b(Z) = p(0Z+l-0) (2.1+.1+.6) f 9 - probability of being fed back. 22 CD CD CO. £ VI •1-3 Q » « k « 5 1 ^ +3 03 >> CO CVJ 0) 23 To solve (2.k.k. l) M additional equations are needed, and these are obtained from M-l P (Z) - C" * P 0k \( Z)} / D n (Z) (2.U.U.7) k=0 where D (Z) = ([a(Z)-p] A - b(Z) A }/(l-Z) (2.J+.if.8) 2.5 Final Remarks The purpose of the preceding sections has been to present the work that has been developed for probabilistic models of queueing systems within the context of computer applications related to our particular problem. This survey does not pretend, by any means, to be exhaustive. Further works may be consulted [20,21,22,23] which point to related and parallel areas of interest. It should be apparent, at this point, that whenever stringent conditions are imposed on the models, only very limited results are available, The open (P =0) tandem systems prove to be more informative than the cyclic (P =l) and the general (P.p> 0) ones. At any rate, the exponential assumptions in the general tandem systems prove to be definitely unacceptable for our information retrieval system model. These system models would only hold under the assumption of a fixed number of quanta to be required from a job. Therefore, the expressions obtained, in general, may only be considered as bounds on the system performance. 2k 3. THE MODEL OF A SPECIALIZED INFORMATION RETRIEVAL SYSTEM 3. 1 Basic Definitions The model introduced here can be described schematically by Figure 3.1. It differs from the models described in Chapter 2 in that the service times of servers depend on the number of times a job has fed back to the system [k]. We will refer to this model of two tandem queues (including the processors) as "System 1.1." For this system let -u. .t b..(t) = \i e 1J (3.1.1) be the probability density function of the service time. The first subscript denotes the processor, and the second subscript denotes the number of quanta received plus one [for example: b (t) is the p.d.f. for the .jobs being in its second quantum in the first processor]. We will assume that all of b. . (t ) are known. Let cp(m) = Pr (a job needs more than m quanta). A quantum is the unit by which we measure the number of times a job has passed "through" system 1.1. If, for example, we say that a job has "received" 2 quanta, we mean that this job has been serviced twice by the processors in the tandem. 25 PM A PM i H ;; =L W a H ^k> < 1 -p w H El •H 26 As shown in [h], cp(m) may be expressed as a function of the parameters of the information retrieval system being modeled by system 1.1. We will assume that these parameters [and thus cp(m)] are known. Let v. > o 1 — be the probability that a job randomly chosen in the system is about to th receive its i quantum of service. Since the results we are going to apply were derived assuming an infinite reservoir of jobs demanding service at the first processor, we shall assume that the system is heavily loaded, clearly approximating the required condition. Finally, let a(t) = \ ±n e" in (3.1.2) be the probability density function of the interarrival time and f(t) = \ f e (3.1.3) be the p.d.f. of the feedback time, so that f(t) = f[a(t),b ltj (t),b 2j (t)] (3.1.10 3.2 The Model System 1.1 may not be properly described by means of the models of Chapter 2 [h, 5,6, 7, 9, 17, 18, 19]. We shall, therefore, model system 1.1, in turn, with a model that may be schematically described by Figure 3.2. We shall refer to this model as "system 3.1- " All the parameters (as described in section 3.1) apply to system 3.1. However, it should be noted that the 27 m -p w !>> CO CM I M 28 two probability density functions of the "sources" that fed system 3.1 [i.e., a(t) and f(t)] were lumped here to a single "source" S, i.e., we will assume that we have an infinite reservoir of jobs, and that these jobs are being generated by S in such a way that the number and interarrival characteristics of these jobs simulate the number and interarrival characteristics of the jobs that would have otherwise joined the first queue of system 1.1. In system 3.1> all of b. . (t) are explicitly dealt with. It is clear that there is a finite, nonzero probability that a job needs (k+1.) quanta, given that it has already received k quanta. This is true for any k, so that, in system 3.1, N -* °°. In the expressions to be derived we shall consistently assume that N -*■ °°. However, it is of practical interest to consider that there exists a finite k, such that the probability that a job needs (k+l) quanta approaches its limit at zero. Given that there are N tandems (in system 3.1) which coexist in time, we must impose some additional conditions to make it equivalent to system 1.1. Thus, we shall assume that the tandems of system 3.1 behave as follows: When an arrival is generated by S, it joins one and only one of the N tandems; specifically, it joins the first queue. This jobs is "tagged" in such a way that it will not be serviced (even if the queue it joined is empty) unless all the other jobs in the first queues of system 3.1 (and were tagged before) are serviced. When this job leaves the first processor, it undergoes a similar treatment for the second queue of the tandem. It should be clear that, on the average, a job entering system 3.1 will behave similarly to a job entering system 1.1. 29 We do still have to determine, however, which one of the tandems of system 3.1 does a job entering the system join. As stated in the preceding section, there is a probability v. that a job is about to receive its i quantum. Clearly, a job should join the i tandem (with service time distributions b, . (t) and b~. (t)) with probability v. to make system 3.1 behave like system 1.1, so we shall assume this. At this point, we have already determined the conditions under which system 3.1 will behave in a similar way to system 1.1. The usefulness of this approach is not yet apparent. However, let us point out that in system 3.1 we have an array of tandems without feedback. These may be analyzed with the tools of simple queueing theory (see Chapter 2). The methods mentioned above, however, assume a "uniform" flow through the system, i.e., the restrictions we imposed on our tandems disallow us to utilize these tools. So, we shall now, in turn, model the tandems of system 3.1 to circumvent this restriction. 3.2.1 The Tandems of System 3.1 Let -H. .t S. . = u. . e 1J 10 ij i = 1,2, ...N (3.2.1.1) d = 1,2 be the probability density function of the service time for the j server of the i tandem. Let us denote by x. . the probability that the j -*- J processor of the i tandem is busy and by y. . the probability that the id 30 j ' stage of the i tandem is not empty. (Here we denote the ensemble queue-processor 'by "stage.") Then X i0 =y id [(l - X kJ )(1 - X k + l,j ) --- (l - X Mj )] ' (3 - 2a - £) k f i and k = 1,2, . . . ,N i = 1,2,... ,N for system 3.1 as described in section 3.2. This equation may be written as: N \j - '» £ ^'V 0.8.1.3) j^i i = 1,2, ...,N k = 1,2 The system of equations in the last expression has 2N unknowns and only N equations. As may be seen, however, y. . denotes the probability of ■i J having at least one job in the j stage of the i tandem. This probability may be found by using a birth-death analysis, as follows. 3.2.1.1 Probability of a Nonempty Stage The following analysis will be formulated for only one processor (say processor l) for the i tandem queue. A similar treatment may be applied to any one of the two processors (from assumptions made in section 2.2.1) and to any one of the tandems. Let z(t) be the number of jobs in the stage at time t. The transitions z(t) -* z(t') for t T > t > 0, for an interval At such that t' = t + At are characterized (assuming the system to be nonempty) by: 31 Pr[z(t+At) = z(t)+l] = Pr(l arrival, no departures) = X V. At + O(At) (3.2.1.1.1) Pr[z(t+At) = z(t)] = Pr(no arrivals, no departures) = 1 - (\ V i +u il x il ) At + O(At) (3.2.1.1.2) Pr[z(t+At) = z(t)-l] = Pr(no arrivals, 1 departure) = x il H il At + O(At) (3.2.1.1.3) where \ is the parameter of the interarrival p.d.f. as generated by S. Letting P n (t) = P r [z(t) = a], t - 0, a = 0,1,...,H (3.2.1.1.4) we have P n (t+At) = P n (t)[l-(\v i +n il x il )At+0(At)] + P n _ 1 (t)[A.v i At+0(At)] + P n+1 (t)[ Xil u i;L At+0(At)] (3.2.1.1.5) Neglecting terms of 0(At), and dividing by At: P n (t+At) - P (t) lim -r = u... x... P ,,(t) - (A.V.+M. ,x. n ) P (t) A , _ At ll ll n+l v ' v i "il il' n^ J + \ v. P , (t) (3.2.1.1.6) i n-1 Thus, P A<*> ■ «U X il W*> " ^ V i +|1 il X il> P n<*> + X V i Vlt*' (3-2.1.1-7) 32 When z(t) = 0, we have P Q (t+At) - (1-A.v^t) P Q (t) + [i ±1 x ±1 At P 1 (t) (3.2.1.1.8) from which we obtain P'(t)- ^x^P^t) -Xv. P ( t ) (3.2.1.1.9) For the steady state lim P'(t) = and from (3.2.1.1.7) and t-*«> (3.2.1.1.9), we have H._ x. n P , - (\v.+H. n x. ,) P + \ v. P , = 0, n>l (3.2.1.1.10) ll ll n+1 l il il n i n-1 — ^il X il P l = x V i p o (3.2.1.1.11) Defining p \ v ± = and solving for (3.2.1. 1.10- 11), we have ll [1.-. x. n & v ~ " il il P n = P il P 0' n = °> 1 ' 2 >'" (3.2.1.1.12) Since p. , < 1 and Z P = 1, we get K il - n ' n=0 P = 1 ' Pil (3.2.1.1.13) so that, finally °n= ^- p il) p il a-°,l,2,... (3.2.1.1.1*0 which is the probability of having n jobs in the first stage of the i tandem. From (3.2.1.1.1^), the probability of having more than jobs is y±i =1 - F o = 1 - ^- p ii) = p il (3.2.1.1.15) 33 3.2.1.2 Probability of a Processor being Busy Equation (3.2.1.1.15) shows that, in the steady state, the probability of having at least one job in the first stage (of the i tandem) of system 3.1 is equal to the utilization factor of the i processor st (l stage). A similar treatment may be applied to the second stage (i tandem). Then, substituting in equation (3.2. 1.3 ), we have a system of N equations with N unknowns and all of the x. . may be determined: N x =p n (l-X..) 1-'1,...,S (3.2.1.2.1) #i k = 1,2 The last expression enables us to calculate the probability that processor j, in the i tandem is busy servicing a given job. Let us now assume that system 3.1 is going to be observed over a period of time sufficiently long so that the central limit theorem may be applied. For such a case, an average service rate u. . may be considered for the j processor in the i ■A-tJ tandem. It is given by U. . = x. . u. . i = 1,...,N (3.2.1.2.2) 3 = 1,2 On the average, a system where the service time rates are u. . will behave like we have determined system 3.1 should behave. On the other hand, because of the said modifications, we may look at this system (with (i. . ) as one in which the "tagging" mechanism mentioned in section 3.2 need not be applied. With this restriction removed, we may now apply the results of Chapter 2 to simple tandem queues. 34 At this point, we have a modified version of the original system 3.1, as it was shown in Figure 3.2. The "new" system 3.1 is shown in Figure 3.3. Since the systems of Figures 3.2 and 3.3 are functionally analogous, we shall assume that, from now on, when talking about system 3.1 we will refer to the modified version of Figure 3.3. It has been shown that, assuming the proper behavior of the source (S), system 3.1 will behave as system 1.1. Furthermore, the tools of queueing theory may now be applied to system 3.1. In order to completely specify system 3.1 as analogous to system 1.1, we still have to express the behavior of S as a function of the parameters of system 1.1. 3.2.2 The Source of System 3.1 Let a t (t) = \e" Xt (3.2.2.1) be the probability density function of the interarrival time of the jobs arriving to system 3.1> as generated by the source. X is defined as X = X. i = 1 ■> 111 i = 1,2, ...,N (3.2.2.2) X = v ± X f i > 1 J for the i tandem. This is so because tandem 1 will account only for new arrivals, while the remaining N-l tandems will receive v. parts of the feedback. As before we shall assume that the central limit theorem holds, and we will rely, further on, on this assumption. For convenience, let us call cp. = cp(i). From system 3.1 and our previous assumptions we can see that, from Burke's Theorem x f = ^in *! + * f v 2 % + ... + * f v w Vl (3.2.2.3) 35 % 1=1 CM OJ ZL H H i^ i=F CO -p w >> -d •H O a 0) EH CO •H and 36 N-l (3.2.2.4) so that N-l \„ - \„ £ v. cp. = \. CD. f f . _p i i m Y i Va *.„ = N-l Z v cp i=2 x K. in 1 - (3.2.2.5) Equation (3.2.2.5) gives X as a function of the primitive parameter (of system l.l) >^ n . The source S now is seen to behave according to the following equation: r a, (t) = \e -\t X = \. m i = 1 (3.2.2.6) \ v i cp 1 N-l 1-2 0=2 K i = 1,2, ...,N in 3 3 This equation may be expressed as a function of cp(m), exclusively, by making use of the fact that v . =

1 37 Equations (3.2.2.6) and (3.2.2.7) indicate that system 3.1 may be looked at as a system of N tandems, where each of these has an associated "source" which generates arrivals according to these equations. The final modified version of system 3.1 is shown in Figure 3.^-. System 3.1* in its final version, is simply an ensemble of N two-stage tandem queues related to each other by equations (3.2.2.7) and (3.2.1.2.2). In the steady state, and for a sufficiently large number of observations, this system behaves as system 1.1. It is now a simple task to apply queueing theory concepts and formulae to obtain certain results of interest. 3.3 Applications of the Model The expected number of jobs in the i tandem is given by: E(n) =_^- + T ^2_ (3b3#i) 1 1_ Pil 1_p i2 where p. . = — — ; \ and |i. . defined as before. For the system, the expected number of jobs is given by: N p ii Pi? E(n) = Z (_i^ + _iL_) (3.3.2) 1-1 1_p il 1 "Pi2 by: The expected waiting time for a job joining the i tandem is given \(l-p ) \(l-p, p ) E(w). = % + i% (3.3.3) 38 "t' % H 1^ /< i H h OJ 1^ 13- H 1^ H ~W T3 8- a •H •r-D <; > H H rn C\l Fr I W II S 'o OJ > 1 H •ra 9- rt •H ■ra ^ > tH H OJ Q- 1 W || !3 -o S > 1 H H CO o d o •H W *H > H 0) on •H P4 39 The total waiting time of a job is given by: N E(w) = 2 i=l A.(l- Pil ) ^.(1-P i2 ) G ±1 +f (^ i2 -M 2 . (3.3.*0 The probability of having n, jobs in the first stage, n jobs in the second stage is given by: n i2 \2 P(V n 2 } i = P il~ P i2 ( 1 -P i l)( 1 -P i2 ) (3.3.5) N P( n;L ,n 2 ) = Z P( ni ,n 2 ). i=l (3.3.6) by: 4*Vi The average number of jobs being served in the i tandem is given E (n). = p + p si ll i2 (3.3.7) while the total number of jobs being served is given by: N E s (n) = ± E =1 P il + P i2 (3.3.8) The expected number of jobs waiting in the i tandem is given by: E (n). w 1 2 2 P il + _±2_ X - P il 1-P (3.3.9) i2 and the expected value of the total number of jobs waiting in the i tandem is given by: N E (n) = 2 E (n). w i=l w 1 3.h A Double Feedback System Hurley and Lawrie [2] describe a system in which a list, after being processed by the merger-coordinator, is stored back in main memory, i.e., there is feedback from the second server to itself. The resulting arrangement is shown in Figure 3. 5* In this case, there are two different feedback probabilities, P and Fro, that a job needs to be fed back to the first and second queues of the tandem, respectively. For this case, we may treat the second queue-second server as in sections 3.2 to obtain a system of N tandems in parallel without feedback. Then, use the same technique to the whole system of Figure 3.5 and get an W -tandem system. P f2 ^ ' > < P fl _ i t T i-p i-p new arrivals X f2 r f 1 Figure 3.5 A Double Feedback System kl k. A NUMERICAL SOLUTION OF THE EQUATIONS OF THE MODEL k.l The Model when Blocking is Allowed In all the models considered thus far (excepting those discussed in sections (2.3.1) and (2.k.k) it was assumed that the queue for the second stage of the tandem is unlimited. Furthermore, except for the case when the system is closed, it was assumed, that the number of jobs in the queue for the first processor can also be infinite. In this chapter we will consider the most general case, when both queues have finite lengths. A solution for the steady state as well as for the transient response will be presented. k.2 A System with Two Waiting Jobs Allowed for Each Processor As an example to illustrate our approach to the case when blocking is considered, we consider the system shown schematically in Figure k.l. *1 ^2 . in > V \ > / 1 queue 1 T queue 2 Figure k.l System k.l We refer to this system as system k.l. System k.l corresponds to a single one of the tandems of system 3.1. The procedure to be applied to system k.l may be generalized (as shown in the last chapter) to the ensemble of N tandems in parallel. Arrivals to queue 1 are Poisson distributed with an average arrival rate \. and service times of the jobs at both servers are exponentially distributed with parameters u., and m. for processors 1 and 2 respectively. When a new arrival finds 3 jobs in the first stage (one being served, two in the queue), it is lost to the system. After a job is served by processor 1, it joins the second queue, unless there are 2 jobs already queueing there. When this situation arises, the system is said to be blocked. There are three instances in which blocking can occur: when there are one, two or three jobs in the first stage and there are two jobs in the second queue . In this system it is no longer true that \. = ^• ou +« If fact, if \q-, is the average output rate of the first stage, and \-p is the average output rate of the second stage, we have in 01 in ' 01 P 1 < 1 p ± > 1 (^.2.1) where P-i = 1 ^i in and X 01 " ^02 X 01 ^ \£ P 2 < 1 P 2 > 1 (fc.2.2) ^3 where 2 m 1+.3 The Equations of System k.l System k.l has one state per configuration. That is, one for each combination of the number of jobs in stage 1 and jobs in stage 2, plus the blocking states mentioned above. For example, the state where there are no jobs in stage 1 and no jobs in stage 2 is a possible configuration of the system. We call this state, state 00. Let the probability that the system is in state 00 at time t be P__(t). In general, the system is in state ij when there are i jobs in stage 1 and j jobs in stage 2. The probability that the system is in state ij at time t is equal to P. . (t). P nn (t) is determined by the input and output parameters and the distribution of the input and output probabilities. In this case P Q0 (t+At) = P 0Q (t)(l-\At) + P 01 (t)(l-\At)(n 2 At) (^.3.1) From the equation we can write P Q0 (t+At) = P Q0 (t) - A-P 00 (t)At + P Q1 (t)u 2 At - A.u 2 P 01 (t)(At) 2 Since (At) ~ 0, we can then write P 00 (t + At) - P (t) At " " WooW - ^ 2 P 01 (t) and 2 kk p oo (t+ t} - p oo (t) At^O At " " *Ob<*> + ^01^ P^ (t) = - A.P 00 (t) + ^ 2 P 01 (t) (4.3.2) which is the differential equation for the probability that the system is in state 00. The system may exist in 19 different states (including state 00), that is: 00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33> A3, B3, C3- The last three states are the blocking states as mentioned before. The behavior of system k.l may now be uniquely specified by a system of simultaneous differential equations in P. .(t), one equation per state. For simplicity, we shall drop the functional notation and denote, for example, p 00 (t ) b y p oo and P 00 (t + At) by P ; o . We will not write explicitly the At factors. With this shorthand, the equation of (4.3.2) may be derived as follows P 00 = P 00 (l -^ + V 1 "^ ^2 and P '00 - - * P 00 + M 2 P 01 ( 4 - 3 - 3 > ^5 In an analogous way, we can write, then P 01 = P 02 (l -^ ^2 + P 10 (1 " A ' ) ^1 + PqI^ 1 "^^ 1 "^ 5 P il " " <**%> P 01 + ^2 P C2 + ^ P 10 ^3-W P 02 = p 02 (i-M(i-^ 2 ) + P 03 (1 " X) ^2 + ^l^ 1 "^) ^(H-fc) P^ = - (X + ^) P Q2 + n 1 P u> +^ P 03 (U.3.5) Pq 3 = P Q3 (l-\)(l-n 2 ) + P^Cl-A.) M x (l-H 2 ) p 03 = ■ (A,+M 2 } P 03 + **1 P 12 (^.3.6) p io = p oo x + ^o^-^i 1 -^) + p 11 (i-^)(i-h 1 ) n 2 P io - - (n 1+ x) P 1Q + x P 0Q + m 2 p i;l (lf.3.7) P ll = P 01 (1 ' M 2 ) X + P 11 ( 1 -^)( 1 -^ 2 )( 1 -^ 1 ) + P 12 (l-^)(1-H 1 ) U 2 + P 2Q H-^l-*.) p ii = - <**VV p n + * p oi + ^2 p i2 + ^i p 2o (i| - 3 - 8) P 12 = P 02 A '( 1 -^2 ) + P 12 ( 1 - A -)(l"^ 1 (l-M 2 ) + P 13 (l-A.)(l-^ 1 ) ^ + P 21 ( 1 " A -) ^(1-^) + P A3 ( 1 "^) ^ PJ2 = - (A.+n 1+ u 2 ) P^ + \ P^ + ^ 2 (P 13 +P A3 ) + H-L P 21 (^-3.9) P 13 = P i 3 ( 1 - X )( 1 "' 1 i)( 1 -^2^ + ^t 1 "^ ^l^ 1 "^^ + P 03 ^t 1 -^ P 13 = " (^i-V^) P 13 + M l P 22 + X P 03 (^-3.10) P 20 = P 20 (1_X)(1 "^1 ) + p 21 ( 1 -^)( 1 -^ 1 ) ^ 2 + p 10 Ml-^) P 20 " " (A ^l) P 20 + ^2 P 21 + X P 10 ^• 3 ' 11 ^ ke P 21 = Pg^ 1 "^ 1- ^ 1 "^ + P ll Ml-^Kl-^) + P 22 (l-^)(l-H 1 ) H 2 + P 30 H P 21 = " ( X+|a i + ^2^ P 21 + ^ P ll + U 2 P 22 + ^1 P 30 (4.3.12) P 22 = P 12 A -( 1 -^ 1 )( 1 -^ 2 ) + P 22 (l-^.)(1-H 1 )(l-H 2 ) + P 23 (l-X)(l-n 1 ) n 2 + p ^(l-^) + p B3 (i-\) n 2 P 22 = " <* + >VV P 22 + X P 12 + li 2 (P 2 3 +P B3 ) + ^1 P 31 (4.3.13) P 23 = P l3 Ml-n^U-^) + P 23 (l-^)(i-n 1 )(l-n 2 ) + P 32 n 1 (i-n 2 ) D 23 = {\+v ± +v 2 ) P 23 + \ P 13 + ^ p 32 (4.3.14) P 30 = P 20 X ( 1_ ^i) + P 31 (l-^ 1 )(l-^ 2 ) + P 30 (l-M 1 ) P' - - 1] p + \ P +uP 30 K l 30 20 ^2 31 (4.3.15) P 31 = P 21 A '( 1 -^ 1 )( 1 -^ 2 ) + P 32 (l-^ 1 ) ^ 2 + P 31 (l-H 1 )(l-H 2 ) 31 = - (u +u ) P +A.P + u P 31 ^1 *2 J 31 21 K 2 32 (4.3.16) P 32 = P 22 A -( 1 -^ 1 )(l-^ l 2 ) + P 33( 1- ^l) ^2 + P 32 (l-^ 1 )(l-^ 2 ) + P c3 ^ 2 P 32 = " K + ^ P 3 2 + X P 22 + ^2^ P 33 +P C3 ) P 33 = P 23 ^l-^Kl-i-^) + P 33 (l-^ 1 )(l-^ 2 ) (4.3.17) 33 - (^ x +n 2 ) P 33 + \ P, 33 23 (4.3.18) U7 P A3 " P 13 (1 - X) W 1 (1 - ,J 2 ) + Pa3 (1 - X)(1 - M 2 ) P A 3 " " <**V P A3 + "l P 13 (M - 19) P B3 = ^S^ 1 ^) ^l^"^) + P B3 (l-^)(l-Mg) + P A3 >-(l-H 2 ) P B3 = " ^V P B3 + M l P 23 + X P A3 (U - 3 - 20) P C3 = P 33 (1 " li 2 ) "l + W^ 5 + P B3 Ml V P 03 " - ^2 P C3 + M l P 33 + X P B3 (U - 3>21) These equations are a good indication of why systems are usually looked at in the steady state. For a system with n jobs (including service) allowed in the first stage and n p jobs (including service) allowed in the second stage, there are (n 1 +l)(n 2 +l) + n 1 possible states. If n = n p , then 2 number of states = n + 3n + 1 (U.3.22) with a corresponding equation for state. As an example, a system where k-0 jobs are allowed to queue per stage, we need 1721 equations. A closed solution for a system of such magnitude is clearly impractical. For t -+ », however, P' -» and, for system k. 1 we have n l n 2 1*0 - * P 00 + "2 P 01 " ° ■> (\+n 2 ) p 01 + n 2 Po2 + ^p 10 - o - ^2 } P 02 + V P Q3 + ^1 P 11 = ° " (^%) P 3 + ^1 P 12 = ° " C^l) P 10 + X P 00 + ^2 P ll = " (^l+V P ll + ^ P 01 + ^1 P 20 + ^2 P 12 = (X + H 1+ H 2 ) P^ + \ P^ + ^ P 2] _ + ^^ P 13 +P A3 ) = ° ( ^1 +M 2 } P l 3 + X P 03 + M l J P™ = o - (^l) P 20 + X P 10 + ^2 P 21 ^ } (^.3.23) - (^1+^) P 21 + X P ll + ^1 P 30 + ^2 P 22 = ° - (**V^) P 22 + X P ]2 + ^1 P 3 1 + ^2 (P 2 3 +P B3 ) = ° - (\4-n 1+ (j. 2 ) p + \ p + n x p = o - ^ p 3 o + * P 20 + ^2 P 3 1 = ° - (n-^) P 31 + *• P 21 + M 2 P. 2 = 32 (n 1+ n 2 ) p 32 + xp 22 + ^(p 33+ p c3 ) - ( V^2 } p 33 + X P 23 = = - ^2 ) P A3 + ^1 ' P_ = - <^V P B3 + ^1 P 23 + XP A3 = 23 A3 - ^2 P C3 + "l P 33 + X P B3 = ° h9 Which is a simple system of first degree simultaneous equations solvable by a number of numerical methods. k.k A General Solution for the Equations of System k.l An approximate solution to equations (k.3) was obtained by applying elementary numerical methods. Such a solution shows the behavior of the system during its transient period as well as the steady state response. Obviously, the solution for a sufficiently long period of time is the same as the solution to the system of equations of (U.3.23)> regardless of the initial state of the system. This solution was obtained by applying a Runge-Kutta-Fehlberg algorithm to the system of differential equations of (U.3.21) and then approximating the obtained data by a least squares polynomial of the fourth degree. The orthogonal polynomials were chosen to be Chebyshev, thus approaching a minimax property. The closed solution to the differential equations was found over an interval sufficiently long so that the system will reach a steady state condition. A numerical example may be found in the file UIUCDCS-F- 76-887 along with the graphs for the solution of the differential equations of the system. With these solutions, there are three parameters of the system which may be investigated. The mean number of jobs in the system is given by C 3 E(n) =2 £ n. . P. . (^.l) i-0 j=0 1J 1J {j=3|i=A,B,C) 50 where the states of the system are denoted by the subscripts of P, and n. . is the number of jobs in state ij. P. . is defined as before. The mean number of active processors is given by C 3 E(P) = Z Z n * . P. . i=o j=o 1J 10 U=3|i=A,B,C) (k.k.2) where n. 1 . is the number of active processors in state i j . For example n 1, n' = 2, etc. P. . is defined as before. A3 -' "13 ij The fraction of lost arrivals is equal to the probability that the first stage is full, thus F = P +P +P +P +P r 30 31 32 33 C3 (^.3) k.5 The Source for a System of Tandems with Blocking In order to apply the results obtained (when blocking is considered) to a model like system 3.1 it is necessary to acknowledge the fact that Burke's theorem does no longer apply. The sources of system 3.1 do not follow equation (3.2.2.7) any longer, but the distribution functions are given by a, (t) = \ e -At f K = \ in X - \ Q , i-1 cp i _ 1 i=l 1=2, 3,..., N (^.5.1) where X is defined as the average output rate of the second stage of the i tandem of a system like system 3.1. After considering equation (^.5.1) we can model a feedback system where only two jobs are allowed to queue before each processor with a model like system 3.1. 51 LIST OF REFERENCES [1] Stellhorn, William H., "A Specialized Computer for Information Retrieval," Ph.D. Thesis and Report No. 637, Department of Computer Science, University of Illinois, Urbana, Illinois, October, 197*+. [2] Hurley, B. J. and D. H. Lawrie, "A Study of Machine Architectures for Specialized Information Retrieval Computers, " to be published, Department of Computer Science, University of Illinois, Urbana, Illinois, [3] Hollaar, L. A., "A List Merging Processor for Inverted File Information Retrieval Systems, " Ph.D. Thesis and Report No. 762, Department of Computer Science, University of Illinois, Urbana, Illinois, October, 1975. [k] Liu, Jane W. S. and J. M. Milner, "Probabilistic Models of Inverted File Document Retrieval System, " International Symposium on Computer Performance Modeling, Measurement and Evaluation, Cambridge, Massachusetts, March, 1976. [5] Siski, R., "Pollaczek Method in Queueing Theory," Developpment recent s de la theorie des files d'attente et de ses applications , pp. 33-61, American Elsevier Publishing Company, Inc., September 27-0ctober 1, 1965. [6] Coffman, E. and P. Denning, Operating Systems Theory , Chapter k, Prentice Hall, 1973. [7] Kleinrock, L., Queueing Systems , Vol. I, Wiley, 1975. [8] Saaty, T., Elements of Queueing Theory, McGraw-Hill, I96I. [9] Burke, J., "The Output of a Queueing System," Op. Research, Vol. k, pp. 699-70*+, 1956. [10] Reich, R., "Waiting Times when Queues are in Tandem," Ann. Math. Stat. , Vol. 28, No. 3, P. 768, 1957. [11] Gordon, W. and G. Newell, "Cyclic Queueing Systems with Restricted Length Queues, " Op. Research , Vol. 15, pp. 266-277, 1967. [12] Gaver, D. and G. Sheldler, "Processor Utilization in Mult i -programming Systems via Diffusion Approximations, " Op. Research , Vol. 21, PP. 569-576, 1973. 52 [13] Cox, D., "Retrieval Theory, Methuen Monograph, " Methuen, London, I962. [Ik] Feller, W., An Introduction to Probability Theory and its Applications, Vol. I, 2nd Ed., Wiley, 1957. [15] Halachmi, B. and W. R. Franta, "A Closed, Cyclic, Two-stage Multi- programmed System Model and its Diffusion Approximation Solution, " University of Minnesota, 1975. [16] Jackson, R. R., "Queueing Systems with Phase Type Service," Op. Research Quart. , Vol. 5, PP. 109-120, 195U. [17] Finch, P. D., "Cyclic Queues with Feedback," J. Roy. Stat. Soc , Ser. B, Vol. 1, pp. 182-186, 1958. [18] Franta, W. R., "The Mathematical Analysis of the Computer Systems Modeled as a Two-stage Cyclic Queue," Technical Report 7^+-23> University of Minnesota, November, 197^. [19] Reiser, M. and A. G. Konheim, "The Analysis of Storage Constraints by a Queueing Network Model with Blocking, " Extended Abstract, IBM Research Report, to appear. [20] Lewis, P. A. W. and G. S. Sheldler, "A Cyclic Queue Model of System Overhead in Multiprogrammed Computer Systems, " IBM Research Report, J. of the ACM , Vol. 18, No. 2, pp. 199-220, April, 1971. [21] Jackson, J., "Networks of Waiting Lines," Op. Research , Vol. 5, No. k, pp. 518-521, August, 1975. [22] Baskett, F. , K Chandy, R. Muntz and F. Palacios, "Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, " J. of the ACM , Vol. 22, No. 2, April 1975- [23] Romani, J., "Un Modelo de la Teoria de Colas con Numero Variable de Canales, " Trabajos de Estadistica , Vol. 8, 1957. [21*] Feller, W., Ibid., pp. 278-317. [25] Ruiz-Pala, E., C. Avila-Beloso and W. Hines, Waiting Line Models , Reinhold, I966. [26] Kuo, S. S., Numerical Methods and Computers , Addison Wesley, 1955. [27] Shampine, L. and R. Allen, Numerical Computing and Introduction , Saunders, 1973. BIBLIOGRAPHIC DATA SHEET 1. Report No. , _ UnJCDCS-R-76-781 2. 3. Recipient's Accession No. 4. Title and Subtitle A Probabilistic Model for a Specialized Information 5. Report Date April, 1976 Retrieval System 6. 7. Author(s) Angel Fernando Kuri Morales 8- Performing Organization Rept. No. K Performing Organization Name and Address Department of Computer Science University of Illinois Urbana, Illinois 10. Project/Task/Work Unit No. 11. Contract /Grant No. 12. Sponsoring Organization Name and Address Department of Computer Science University of Illinois Urbana, Illinois 13. Type of Report & Period Covered 14. 15. Supplementary Notes 16. Abstracts A model for a specialized information retrieval system is discussed. A survey of the probabilistic models for queuing systems is performed with emphasis on queues in tandem. Several of these models are found to apply to the system discussed, but only for restricted conditions. A probabilistic model for the system discussed is developed, assuming unlimited queue lengths. A set of simultaneous differential equations describing a particular case, with finite queue lengths, is developed. The general procedure of solution is outlined. A numerical solution for the particular case is found, and the solutions are plotted. 17. Key Words and Document Analysis. 17o. Descriptors information retrieval processor queue tandem Markovian numerical 7b. Identifiers /Open-Ended Terms 17c. COSATI Field/Group 18. Availability Statement 19. Security Class (This Report) UNCLASSIFIED 21. No. of Pages 20. Security Class (This Page UNCLASSIFIED 22. Price 'ORM N TIS-35 (10-70) USCOMM-DC 40329-P7! fc* - *W 2$ %»