Analysis and Synthesis of Computer Systems presents a broad overview of methods that are used to evaluate the performance of computer systems and networks, manufacturing systems, and interconnected services systems. Aside from a highly readable style that rigorously addresses all subjects, this second edition includes new chapters on numerical methods for queueing models and on G-networks, the latter being a new area of queuing theory that one of the authors has pioneered. This book will have a broad appeal to students, practitioners and researchers in several different areas, including practicing computer engineers as well as computer science and engineering students. Read more...
1. Basic tools of probabilistic modelling. 1.1. General background. 1.2. Markov processes. The exponential distribution. 1.3. Poisson arrival streams. Important properties. 1.4. Steady-state. Balance diagrams. The "Birth and Death" process. 1.5. The M/M/1, M/M/c and related queueing systems. 1.6. Little's result. Applications. The M/G/1 system. 1. 7. Operational identities. 1.8. Priority queueing --
2. The queue with server of walking type and its applications to computer system modelling. 2.1. Introduction. 2.2. The queue with server of walking type with Poisson arrivals, and the M/G/1 queue. 2.3. Evaluation of secondary memory device performance. 2.4. Analysis of multiplexed data communication systems --
3. Queueing network models. 3.1. General remarks. 3.2. Feedforward networks and product-form solution. 3.3. Jackson networks. 3.4. Other scheduling strategies and service time distributions. 3.5. The BCMP theorem. 3.6. The computation of performance measures --
4. Queueing networks with multiple classes of positive and negative customers and product form solution. 4.1. Introduction. 4.2. The model. 4.3. Main results. 4.4. Existence of the solution to the traffic equations. 4.5. Conclusion --
5. Markov-modulated queues. 5.1. A multiserver queue with breakdowns and repairs. 5.2. Manufacturing blocking. 5.3. Phase-type distributions. 5.4. Checkpointing and recovery in the presence of faults. 5.5. Spectral expansion solution. 5.6. Balance equations. 5.7. Batch arrivals and/or departures. 5.8. A simple approximation. 5.9. The heavy traffic limit. 5.10. Applications and comparisons. 5.11. Remarks --
6. Diffusion approximation methods for general queueing networks. 6.1. Introduction. 6.2. Diffusion approximation for a single queue. 6.3. Diffusion approximations for general networks of queues with one customer class. 6.4. Approximate behaviour of a single queue in a network with multiple customer classes. 6.5. Conclusion --
7. Approximate decomposition and iterative techniques for closed model solution. 7.1. Introduction. 7.2. Subsystem isolation. 7.3. Decomposition as an approximate solution method. 7.4. An electric circuit analogy for queueing network solution --
8. Synthesis problems in single-resource systems : characterisation and control of achievable performance. 8.1. Problem formulation. 8.2. Conservation laws and inequalities. 8.3. Characterisation theorems. 8.4. The realisation of pre-specified performance vectors. Complete families of scheduling strategies. 8.5. Optimal scheduling strategies --
9. Control of performance in multiple-resource systems. 9.1. Some problems arising in multiprogrammed computer systems. 9.2. The modelling of system resources and program behaviour. 9.3. Control of the degree of multiprogramming. 9.4. The page fault rate control policy (RCP). 9.5. Control of performance by selective memory allocation. 9.6. Towards a characterisation of achievable performance in terminal systems --
10. A queue with server of walking type. 10.1. Introduction. 10.2. Properties of the waiting time process. 10.3. Application to a paging drum model.
Author(s): Erol Gelenbe, Isi Mitrani
Series: Advances in Computer Science and Engineering: Texts, Vol. 04
Edition: 2nd
Publisher: Imperial College Press
Year: 2010
Language: English
Pages: 324
City: London, UK
Contents......Page 8
Preface to the Second Edition......Page 6
1.1. General background......Page 12
1.2. Markov processes. The exponential distribution......Page 14
1.3. Poisson arrival streams. Important properties......Page 20
1.4. Steady-state. Balance diagrams. The “Birth and Death” process......Page 24
1.5. The M/M/1, M/M/c and related queueing systems......Page 31
1.6. Little’s result. Applications. The M/G/1 system......Page 39
1.7. Operational identities......Page 45
1.8. Priority queueing......Page 48
References......Page 53
2.1. Introduction......Page 54
2.2. The queue with server of walking type with Poisson arrivals, and the M/G/1 queue......Page 55
2.2.1. The embedded Markov chain......Page 56
2.2.2. The stationary queue length process......Page 60
2.3.1. Application to a paging drum model......Page 69
2.3.2. Solid-state secondary memory devices......Page 74
2.4. Analysis of multiplexed data communication systems......Page 79
2.4.2. Approximate analysis of buffer queue length......Page 81
References......Page 82
3.1. General remarks......Page 84
3.2. Feedforward networks and product-form solution......Page 87
3.3. Jackson networks......Page 91
3.4. Other scheduling strategies and service time distributions......Page 101
3.4.1. The egalitarian processor-sharing strategy......Page 102
3.4.2. The pre-emptive-resume LCFS strategy......Page 103
3.4.3. The server-per-job strategy......Page 104
3.5. The BCMP theorem......Page 109
3.6. The computation of performance measures......Page 117
References......Page 125
4.1. Introduction......Page 128
4.2. The model......Page 130
4.3. Main results......Page 132
4.4. Existence of the solution to the traffic equations......Page 143
References......Page 145
5. Markov-Modulated Queues......Page 148
5.1. A multiserver queue with breakdowns and repairs......Page 150
5.2. Manufacturing blocking......Page 152
5.3. Phase-type distributions......Page 153
5.4. Checkpointing and recovery in the presence of faults......Page 154
5.5. Spectral expansion solution......Page 155
5.6. Balance equations......Page 157
5.7. Batch arrivals and/or departures......Page 162
5.8. A simple approximation......Page 164
5.9. The heavy traffic limit......Page 166
5.10. Applications and comparisons......Page 169
5.11. Remarks......Page 174
References......Page 175
6.1. Introduction......Page 176
6.2. Diffusion approximation for a single queue......Page 177
6.2.1. Queues and the numerical discretisation of the diffusion equation......Page 178
6.2.2. An approach based on the central limit theorem......Page 180
6.2.3. The instantaneous return process [10, 11]......Page 182
6.2.4. Application to the GI/G/1 queue: stationary solution......Page 187
6.2.5. Application to a closed two-server system with general service time distributions......Page 189
6.2.6. The discretisation problem......Page 192
6.3. Diffusion approximations for general networks of queues with one customer class......Page 196
Example 6.1......Page 202
6.3.1. Application to packet-switching computer-communication networks......Page 204
Example 6.2......Page 208
6.3.2. The approach of Kobayashi and Reiser to the approximation of queueing networks......Page 210
6.4.1. Computation of the approximate interarrival statistics for each queue......Page 212
6.4.2. Diffusion approximation to the queue length process......Page 215
6.5. Conclusion......Page 217
References......Page 218
7.2. Subsystem isolation......Page 222
7.2.1. Aggregate/subsystem decomposition for a closed Jackson network......Page 223
7.2.2. Solution with one single aggregate/subsystem decomposition......Page 224
7.3. Decomposition as an approximate solution method......Page 226
7.3.1. Approximate stationary solution of the system Q......Page 229
7.4. An electric circuit analogy for queueing network solution......Page 235
References......Page 240
8.1. Problem formulation......Page 242
8.2. Conservation laws and inequalities......Page 244
8.3. Characterisation theorems......Page 253
8.4. The realisation of pre-specified performance vectors. Complete families of scheduling strategies......Page 260
8.4.1. Generalised processor-sharing strategies......Page 265
8.5. Optimal scheduling strategies......Page 270
References......Page 279
9.1. Some problems arising in multiprogrammed computer systems......Page 280
9.2. The modelling of system resources and program behaviour......Page 282
9.3. Control of the degree of multiprogramming......Page 285
9.3.1. The knee criterion......Page 286
9.3.2. The L = S criterion......Page 288
9.3.3. The 50% criterion......Page 290
9.4. The page fault rate control policy (RCP) .......Page 292
9.5. Control of performance by selective memory allocation......Page 298
9.6. Towards a characterisation of achievable performance in terminal systems......Page 303
References......Page 305
10.1.1. The mathematical model......Page 308
10.1.2. Relation to previous work......Page 309
10.2. Properties of the waiting time process......Page 310
References......Page 318
Index......Page 320
