Computer system performance modeling in perspective : a tribute to the work of Professor Kenneth C. Sevcik

Title:

Series:

Advances in computer science and engineering ; 1

Publication Information:

London : Imperial College Press, 2006

ISBN:

9781860946615

Subject Term:

Computer systems -- Evaluation

Computer systems -- Reliability

Electronic digital computers -- Evaluation

Added Author:

Gelenbe, E., 1945-

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010124252	QA76.9.E94 C656 2006	Open Access Book	Book	Searching... Unknown

Computer system performance evaluation is a key discipline for the understanding of the behavior and limitations of large scale computer systems and networks. This volume provides an overview of the milestones and major developments of the field.The contributions to the book include many of the principal leaders from industry and academia with a truly international coverage, including several IEEE and ACM Fellows, two Fellows of the US National Academy of Engineering and a Fellow of the European Academy, and a former President of the Association of Computing Machinery.

Ed Lazowska and Satish Tripathi and John Zahorjan and Derek EagerJeffrey P. BuzenEd CoffmanPeter J. DenningErol Gelenhe and Zhi-Hong Mao and Van-Da LiVittoria De Nitto Persone and Giuseppe IazeollaSatish K. Tripathi and J. Jobin and Michalis FaloutsosGuoqiang Wang and Yongchang Ji and Dan C. Marinescu and Damla Turgut and Ladislau BoloniGreg Franks and Murray Woodside and Jerry RoliaPeter G. Harrison and William J. KnottenbeltYaakov Kogan and Gagan ChoudhuryTzvetelina Battestilli and Harry PerrosMark S. SquillanteHelen Karatza

Preface	p. V
Chapter 1 Ken Sevcik as an Advisor and Mentor	p. 1
Chapter 2 Shadow Servers and Priority Scheduling	p. 47
1 Introduction	p. 7
2 Single Class Models	p. 8
3 Multi-Class Models	p. 8
4 Importance of Priorities	p. 9
5 The Shadow Server Approximation	p. 10
6 Extensions	p. 12
7 Comments on Significance	p. 13
References	p. 14
Chapter 3 On the Chronology of Dynamic Allocation Index Policies: The Pioneering Work of K. C. Sevcik	p. 15
1 Introduction	p. 15
2 Sevcik's Smallest-Rank-First Index Policy	p. 16
3 Background and Chronology	p. 17
4 Examples	p. 18
5 Concluding Remarks	p. 19
References	p. 19
Chapter 4 Operational Analysis	p. 21
1 Introduction	p. 21
2 Dead Cows	p. 21
3 Dead Cows in Markovian Queueing Networks	p. 22
4 The Birth of Operational Analysis	p. 24
5 The Fundamental Assumptions of Operational Analysis	p. 25
6 Controversy	p. 28
7 Salute	p. 29
8 An Historical Footnote	p. 29
References (Published)	p. 29
References (Unpublished Technical Reports)	p. 30
Appendix Operational Analysis: A Fable	p. 31
Chapter 5 Function Approximation by Random Neural Networks with a Bounded Number of Layers	p. 35
1 Introduction	p. 35
2 The GNN and Its Extensions	p. 36
2.1 The BGNN model	p. 38
3 Approximation of Functions of One Variable by the GNN with a Bounded Number of Layers	p. 40
3.1 Technical premises	p. 41
3.2 BGNN approximation of continuous functions of one variable	p. 44
3.3 CGNN approximation of continuous functions of one variable	p. 46
4 Approximation of Continuous Functions of s Variables	p. 49
5 Conclusions	p. 53
References	p. 54
Appendix Proof of Technical Lemmas	p. 56
Chapter 6 The Achilles' Heel of Computer Performance Modeling and the Model Building Shield	p. 59
1 Introduction	p. 59
2 The Current Status of Model Building	p. 60
3 System Multilevel Description	p. 61
3.1 The system vertical description	p. 62
3.2 The system horizontal description	p. 63
3.3 The system software description	p. 64
4 The Multilevel Model Building Method	p. 68
4.1 The top-down bottom-up process	p. 68
5 Comparison with Existing Approaches	p. 71
6 Conclusions	p. 72
Acknowledgment	p. 72
References	p. 73
Chapter 7 Wireless Network Simulation: Towards a Systematic Approach	p. 75
1 Introduction	p. 76
2 Background and Model	p. 78
3 Description of Our Framework	p. 79
3.1 System parameters	p. 79
3.2 Performance metrics	p. 80
3.3 Our framework	p. 81
4 Experimental Results	p. 82
4.1 Parameters that affect steady state utilization	p. 82
4.2 The significance of steady state arrival rate	p. 86
4.3 Discussion and applications	p. 87
5 Homogeneity	p. 90
5.1 Related work	p. 91
5.2 Metrics for comparison	p. 92
6 Evaluation	p. 92
6.1 Cell shape (number of neighbors)	p. 92
6.2 User speed	p. 96
6.3 User bandwidth requirement	p. 97
7 Conclusion	p. 98
References	p. 99
Chapter 8 Location- and Power-Aware Protocols for Wireless Networks with Asymmetric Links	p. 101
1 Introduction and Motivation	p. 102
2 Related Work	p. 104
3 The Model of the System	p. 106
4 m-Limited Forwarding	p. 110
4.1 Simulation study	p. 112
5 Routing Protocol	p. 118
5.1 Neighbor discovery	p. 119
5.2 Location and power update	p. 120
5.3 Route discovery	p. 120
5.4 Route maintenance	p. 121
6 MAC Protocol	p. 121
6.1 Topological considerations	p. 121
6.2 A solution to the hidden node problem	p. 124
6.3 Node status	p. 126
6.4 Medium access model	p. 126
6.5 A simulation study	p. 128
7 Cross-Layer Architecture	p. 130
8 Work in Progress	p. 131
9 Summary	p. 132
Acknowledgments	p. 133
References	p. 133
Chapter 9 Multi-Threaded Servers with High Service Time Variation for Layered Queueing Networks	p. 137
1 Introduction	p. 137
2 Residence Time Expressions	p. 138
2.1 MVA waiting time expressions	p. 139
3 Accuracy and Computation-Time Comparisons	p. 141
4 Example Case Studies	p. 143
4.1 Systems management example	p. 143
4.2 Electronic bookstore example	p. 144
5 Conclusions	p. 148
Acknowledgments	p. 150
Appendix A Marginal Probabilities	p. 150
Appendix B de Souza e Silva and Muntz Approximation	p. 152
References	p. 152
Chapter 10 Quantiles of Sojourn Times	p. 155
1 Introduction	p. 156
2 Time Delays in the Single Server Queue	p. 158
2.1 Waiting time distribution in the M/G/1 queue	p. 158
2.2 Busy periods	p. 159
2.3 Waiting times in LCFS queues	p. 160
2.4 Waiting times with Processor-Sharing discipline	p. 162
3 MM CPP/GE/c G-Queues: Semi-Numerical Laplace Transform Inversion	p. 162
4 Time Delays in Networks of Queues	p. 166
4.1 Open networks	p. 167
4.2 Closed networks	p. 169
4.2.1 Cyclic networks	p. 173
4.2.2 Paths with service rates all equal	p. 174
5 Passage Times in Continuous Time Markov Chains	p. 174
5.1 First passage times in CTMCs	p. 174
5.2 Uniformization	p. 175
5.3 Hypergraph partitioning	p. 176
5.4 Parallel algorithm and tool implementation	p. 177
5.5 Numerical example	p. 179
6 Passage Times in Continuous Time Semi-Markov Processes	p. 182
6.1 First passage times in SMPs	p. 183
6.2 Iterative passage time algorithm	p. 185
6.3 Laplace transform inversion	p. 186
6.4 Implementation	p. 187
6.5 Numerical example	p. 187
7 Conclusion	p. 190
References	p. 191
Chapter 11 Asymptotic Solutions for Two Non-Stationary Problems in Internet Reliability	p. 195
1 Introduction	p. 195
2 Poisson Approximation for the Number of Failed Routers	p. 197
3 Asymptotics of Lost Bandwidth	p. 200
References	p. 204
Chapter 12 Burst Loss Probabilities in an OBS Network with Dynamic Simultaneous Link Possession	p. 205
1 Introduction	p. 205
2 Problem Description	p. 208
3 A Queueing Network Model for an OBS Path	p. 209
3.1 The arrival process	p. 211
4 The Decomposition Algorithm	p. 213
4.1 An example	p. 213
4.1.1 Analysis of sub-system 1	p. 213
4.1.2 Analysis of sub-system 2	p. 215
4.1.3 The iterative procedure	p. 216
4.2 The decomposition algorithm	p. 217
4.3 Calculation of the burst loss probability	p. 219
5 Numerical Results	p. 220
6 Conclusions	p. 223
References	p. 224
Chapter 13 Stochastic Analysis of Resource Allocation in Parallel Processing Systems	p. 227
1 Introduction	p. 227
2 Model of Parallel Processing Systems	p. 230
3 Analysis of Dynamic Spacesharing	p. 232
3.1 Irreducibility and stability criterion	p. 235
3.2 Special case: Exponential model parameters	p. 235
3.3 Performance measures	p. 237
4 Analysis of Memory Reference Behavior	p. 239
4.1 Program behavior models	p. 240
4.2 Intra-locality memory overhead	p. 244
4.3 Inter-locality memory overhead	p. 245
4.3.1 Calculation of N[subscript I]	p. 246
4.3.2 Calculation of C[subscript I]	p. 247
4.4 Total memory overhead	p. 250
5 Conclusions	p. 250
Acknowledgment	p. 251
References	p. 251
Chapter 14 Periodic Task Cluster Scheduling in Distributed Systems	p. 257
1 Introduction	p. 257
2 Model and Methodology	p. 260
2.1 System and workload models	p. 260
2.2 Scheduling strategies	p. 262
2.3 Performance metrics	p. 263
2.4 Model implementation and input parameters	p. 263
3 Simulation Results and Performance Analysis	p. 264
3.1 Normal distribution case	p. 264
3.2 Uniform distribution case	p. 271
4 Conclusions and Future Research	p. 273
References	p. 273

Available:*

On Order

Summary

Summary

Table of Contents