Mathematical Adventures in Performance Analysis: From Storage Systems, Through Airplane Boarding, to Express Line Queues (Modeling and Simulation in Science, Engineering and Technology)

This book describes problems in the field of performance analysis, primarily the study of storage systems and the diverse mathematical techniques that are required for solving them. Topics covered include best practices for scheduling I/O requests to a disk drive, how this problem is related to airplane boarding, and how both problems can be modeled using space-time geometry. Also provided is an explanation of how Riemann's proof of the analytic continuation and functional equation of the Riemann zeta function can be used to analyze express line queues in a minimarket. Overall, the book displays the surprising relevance of abstract mathematics that is not usually associated with applied mathematics topics. Advanced undergraduate students or graduate students with an interest in the applications of mathematics will find this book to be a useful resource. It will also be of interest to professional mathematicians who want exposure to the surprising ways that theoretical mathematics may be applied to engineering problems. To encourage further study, each chapter ends with notes pointing to various related topics that the reader may want pursue. This mathematically rigorous work was noted in the news section of the journal Nature, and in popular media such as New Scientist, The Wall Street Journal, The Guardian, and USA Today. Preface 6 Contents 10 Chapter 1 A Classical Model for Storage System Activity 13 1.1 Modeling Disk Drives 14 1.1.1 Coordinates for Data Locations 14 1.1.2 Seek Time Functions 15 1.2 Modeling Access Patterns 16 1.2.1 The IRM 17 1.3 Estimating Seek Times in the IRM 19 1.4 Metric Spaces 22 1.5 The IRM Seek Estimate Is Pessimistic 24 1.6 Notes for Chap.1 31 Chapter 2 A Fractal Model for Storage System Activity 38 2.1 Definition of the Model 39 2.1.1 Marginal Spatial and Temporal Measures 41 2.2 Average Seek Distance Calculations 41 2.3 Cache Hit Ratios and Entropy 44 2.3.1 Basic Properties of Entropy 45 2.3.2 Static Cache Algorithms 47 2.4 Asymptotic Hit Ratio Computations 47 2.5 Incompatibility of q-ary and p-ary Bias Models 51 2.6 Notes for Chap.2 58 Chapter 3 Airplane Boarding, Disk Scheduling, and Lorentzian Geometry 61 3.1 The Disk Scheduling Problem 62 3.2 The ABZ Algorithm 63 3.2.1 Partially Ordered Sets 63 3.2.2 Partially Ordered Sets and the Disk Scheduling Problem 64 3.2.3 Efficient Computation of the ABZ Algorithm 67 3.2.4 Patience Sorting 68 3.2.5 Parallel Computation via Airplane Boarding 69 3.3 The General Airplane Boarding Process 70 3.4 Disk Scheduling and Airplane Boarding in a Probabilistic Setting 72 3.5 Lorentzian Geometry 75 3.5.1 Minkowski Space 75 3.5.1.1 Examples of Causal Partial Orders 77 3.5.1.2 Intervals 79 3.5.1.3 Causal Curves 80 3.5.1.4 Orthogonality and Volume 82 3.5.2 General (Lorentzian) Space-Time Manifolds 83 3.5.2.1 The Underlying Geometry of a Space-Time 83 3.5.2.2 Lorentzian Metrics 84 3.5.2.3 Vectors 86 3.5.2.4 Causal Curves in Lorentzian Geometry 87 3.5.2.5 Local Approximation by Minkowski Spaces 88 3.5.2.6 Lengths and Volumes 88 3.5.2.7 The Topology of the Space of Causal Curves 89 3.6 Discrete Space-Time 90 3.6.1 Poisson Sampling 91 3.6.2 Chains in Discrete Space-Time 93 3.7 Applications of Theorem 3.6.3 105 3.7.1 Applications to Disk Scheduling 105 3.7.2 General Relativity Theory 106 3.7.3 Estimating the Dimension of Causal Sets 107 3.7.3.1 Dimension Estimation Algorithm 107 3.7.4 Applications to Airplane Boarding Analysis 107 3.7.4.1 Computing the Maximal Curve 110 3.7.4.2 Existence of Solutions 112 3.7.4.3 Computing the Boarding Time of the Random Boarding Policy 112 3.7.4.4 Analysis of Back-to-Front Boarding Policies 114 3.7.4.5 Analysis of Other Boarding Policies 119 3.7.4.6 Unassigned Seating 124 3.7.4.7 Luggage and Overhead Bins 125 3.8 Disk Scheduling Under the Microscope 129 3.9 Notes for Chap.3 135 Chapter 4 Mirrored Configurations 140 4.1 Modeling a Mirrored Data Configuration Using Graphs 141 4.2 An Upper Bound on the Cycle Threshold 143 4.2.1 Branching Processes 143 4.2.2 An Upper Bound for the Cycle Threshold 145 4.3 Lubotzky–Phillips–Sarnak Graphs 147 4.3.1 Number Theoretic Preliminaries 148 4.3.2 Gaussian Integers and Hamiltonian Integers 149 4.3.3 Counting Gaussian and Hamiltonian Integers of a Given Norm 153 4.3.4 The LPS Construction 155 4.3.4.1 Construction of LPS Graphs via Hamiltonian Integers 155 4.3.4.2 A Description of Xp,q via Matrices 158 4.3.5 Construction of Families with Optimal Cycle Threshold via LPS Graphs 158 4.4 Constructions for General Degrees and Graph Sizes 163 4.5 Some Experimental Results 166 4.6 Notes for Chap.4 168 Chapter 5 On Queues and Numbers 171 5.1 Managing a Mini-Market 172 5.2 Basic Queueing Theory 179 5.3 Variants of the M/G/1 Queue 186 5.4 Duality Theory 192 5.5 Self-Dual Distributions in Queueing Theory 195 5.6 The Riemann Zeta Function 198 5.6.1 The Functional Equation of the Theta Function 199 5.6.2 Relating the Theta and Zeta Functions 200 5.7 Modular forms for SL2(Z) 202 5.7.1 Modular Forms for Congruence Subgroups 205 5.7.2 Mellin Transforms of Modular Forms 207 5.7.3 Diamond Operators 210 5.7.4 New Forms 211 5.7.5 Hecke Operators 212 5.7.6 Hecke Newforms and the Mini-Market Theorem 216 5.8 SITA Queues with Pareto Job-Size Distributions 219 5.9 Choosing Good Cutoffs 226 5.10 Analysis of the Large h Asymptotics of SITA Queues 227 5.11 Notes for Chap.5 231 Appendix A Some Basic Definitions and Facts 239 A.1 Point-Set Topology and Metric Topology 239 A.2 Measure Theory 244 A.3 Probability 247 A.4 Algebra 251 A.5 Linear Algebra 251 A.6 Harmonic Analysis and Transforms 252 A.7 Basic Definitions in Graph Theory 256 Appendix B Proofs of Theorems 259 B.1 Proofs of Results from Chap.2 259 B.2 Proofs of Results from Chap.3 262 B.3 Proofs of Results from Chap.4 279 References 284 Index 293 This monograph describes problems in the field of performance analysis, primarily the study of storage systems and the diverse mathematical techniques that are required for solving such problems. Topics covered include best practices for scheduling I/O requests to a disk drive, how this problem is related to airplane boarding, and how both problems can be modeled using space-time geometry. The author also explains how Riemann's proof of the analytic continuation and functional equation of the Riemann zeta function can be used to analyze express-line queues in a minimarket. Overall, the book reveals the surprising applicability of abstract mathematical ideas that are not usually associated with applied topics. Advanced undergraduate students or graduate students with an interest in the applications of mathematics will find this book a useful resource. It will also be of interest to professional mathematicians who want exposure to the surprising ways that theoretical mathematics may be applied to engineering problems. To encourage further study, each chapter ends with notes pointing to various related topics that the reader may want to pursue 2.4 Asymptotic Hit Ratio Computations2.5 Incompatibility of q-ary and p-ary Bias Models; 2.6 Notes for Chap. 2; Chapter3 Airplane Boarding, Disk Scheduling, and Lorentzian Geometry; 3.1 The Disk Scheduling Problem; 3.2 The ABZ Algorithm; 3.2.1 Partially Ordered Sets; 3.2.2 Partially Ordered Sets and the Disk Scheduling Problem; 3.2.3 Efficient Computation of the ABZ Algorithm; 3.2.4 Patience Sorting; 3.2.5 Parallel Computation via Airplane Boarding; 3.3 The General Airplane Boarding Process; 3.4 Disk Scheduling and Airplane Boarding in a Probabilistic Setting; 3.5 Lorentzian Geometry Front Matter....Pages i-xi A Classical Model for Storage System Activity....Pages 1-25 A Fractal Model for Storage System Activity....Pages 27-49 Airplane Boarding, Disk Scheduling, and Lorentzian Geometry....Pages 51-129 Mirrored Configurations....Pages 131-161 On Queues and Numbers....Pages 163-230 Back Matter....Pages 231-290