empfehlenswert
Ein Grundlagenwerk zum Thema.
Warteschlangentheorie lang und schmutzig ;-)
Part I: Preliminaries Chapter 1 Queueing Systems 1.1 Systems of Flow 1.2. The Specifications and Measure of Queueing Systems Chapter 2 Some Important Random Processes 2.1 Notation and Structure for Basic Queueing Systems 2.2 Definition and Classification of Stochastic Processes 2.3 Discrete-Time Markov Chains 2.4 Continuous-Time Markov Chains 2.5 Birth-Death Processes Part II: Elementary Queueing Theory Chapter 3 Birth-Death Queueing Systems in Equilibrium 3.1 General Equilibrium Solution 3.2 M/M/1: The Classical Queueing System 3.3 Discouraged Arrival 3.4 M/M/u: Responsive Servers (Infinite Number of Servers) 3.5 M/M/m: The m-Server Case 3.6 M/M/1/k: Finite Storage 3.7 M/M/m/m: m-Server Loss System 3.8 M/M/1//M: Finite Customer Population - Single Server 3.9 M/M/u//M: Finite Customer Population - "Infinite" Number of Servers 3.10 M/M/m/K/M: Finite Population, m-Server Case, Finite Storage Chapter 4 Markovian Queues in Equilibrium 4.1 The Equlilibrium Equations 4.2 The Method of Stages - Erlangian Distribution E 4.3 The Queue M/E/1 4.4 The Queue E/M/1 4.5 Bulk Arrival Systems 4.6 Bulk Service Systems 4.7 Series-Parallel Stages: Generalizations 4.8 Networks of Markovian Queues Part III: Intermediate Queueing Theory Chapter 5 The Queue M/G/1 5.1 The M/G/1 System 5.2 The Paradox of Residual Life: A Bit of Renewal Theory 5.3 The Imbedded Markov Chain 5.4 The Transition Probalities 5.5 The Mean Queue Length 5.6 Distribution of Number in System 5.7 Distribution of Waiting Time 5.8 The Busy Period and Its Duration 5.9 The Number Served in a Busy Period 5.10 From Busy Periods to Waiting Times 5.11 Combinatorial Methods 5.12 The Takacs Integrodiffenrential Equation Chapter 6 The Queue G/M/m 6.1 Transition Probabilities for the Imbedded Markov Chain (G/M/m) 6.2 Conditional Distribution Queue Size 6.3 Conditional Distribution Waiting Time 6.4 The Queue G/M/1 6.5 The Queue G/M/m 6.6 The Queue G/M/2 Chapter 7 The Method of Collective Marks 7.1 The Marking of Customers 7.2 The Catastrophe Process Part IV: Advanced Material Chapter 8 The Queue G/G/1 8.1 Lindley's Integral Equation 8.2 Spectral Solution to Lindley's Integral Equation 8.3 Kingman's Algebra for Queues 8.4 The Idle Time and Duality Epilogü Appendix I: Transform Theory Refresher: z-Transform and Laplace Transform I.1 Why Transforms? I.2 The z-Transform I.3 The Laplace Transform I.4 Use of Transforms in the SOlution of Difference and Differential Equations Appendix II: Probability Refresher II.1 Rules of the Game II.2 Random Variables II.3 Expectations II.4 Transforms, Generating Functions, and Characteristic Functions II.5 Inequalities and Limit Theorems II.6 Stochastic Processes Glossary of Notation Summary of Important Rules Index
Kleinrock gelingt es auch "trockene" Theorie zu präsentieren.
Das Buch ist ein Rundumschlag zur Warteschlangentheorie und trotz des Alters (immerhin 1975 erschienen) aktuell. (Da soll nochmal einer sagen, die IT sei schnelllebig ;-). Für die praktische Relevanz gibt es einen zweiten Teil (den ich aber nicht kenne).
Wenn einem die empirischen Untersuchungen zu Serverauslastungen, zu langen Verweilzeiten (das System ist zu langsam) oder plötzlich auftretenden Systemzusammenbrüchen nicht mehr reichen, findet hier das erforderliche theoretische Rüstzeug, für eine detailiertere Analyse; z.B. für eine kleine Simulation.
Interessant sind auch die Herleitung des Hippie Paradoxons und die Aussage, dass das Antwortverhalten eines Servers extrem stark von der Varianz der Verweilzeit (Queue- und Servicetime) abhängt.
Das Hippie Paradoxon besagt, dass ein Hippie tatsächlich im Mittel n Minuten warten muss, wenn die mittlere Wartezeit zwischen zwei Autos, die einen trampenden Hippie mitnehmen, ebenfalls n Minuten beträgt. Naiverweise würde man die mittlere Wartezeit bei n/2 Minuten vermuten. Der Beweis findet sich im Kapitel 5.2 auf den Seiten 169-173.
Auf das Buch wurde ich aufmerksam durch einen Usenet Artikel von Rob Pike.
Leonard Kleinrock
1975, John Wiley & Sond, ISBN 0-471-49110-1, 417 Seiten
Amazon: http://www.amazon.de/exec/obidos/ASIN/0471491101
Unbedingt ansehen: http://rfc.sunsite.dk/rfc/rfc1121.html
Gefunden in Dr Dobbs Journal:
Happy Birthday Packet Switching, or Laboring on Labor Day
In the U.S., September 1 is Labor Day this year (2008), a national holiday that serves as an excuse for the boss to officially take the day off, even though I'm hard at it. But the Labor Day holiday is noteworthy for something else, too. It was Labor Day weekend 39 years ago that the Internet was launched. Well, sort of.
More specifically, on Labor Day weekend, September 2, 1969, UCLA became the first node of what was known as the ARPANET when a team of engineers led by University of California, Los Angeles computer scientist Leonard Kleinrock established the first network connection between two computers. The first network switch, known as an Interface Message Processor (IMP), arrived at UCLA on Labor Day weekend, 1969, and Kleinrock's team had to connect the first host computer to the IMP. By the end of the day, bits began moving between the UCLA computer and the IMP. By the next day, they had messages moving between machines.
A month later, a second node was added at the Stanford Research Institute, the first host-to-host message was launched from UCLA, and by December four sites were connected: UCLA; the Stanford Research Institute; the University of California, Santa Barbara; and the University of Utah. UCLA was in charge of conducting a series of tests to debug the network. Under Kleinrock's supervision, UCLA served for many years as the ARPANET Network Measurement Center.
Recognizing Kleinrock's contributions, the National Science Foundation this month selected him to receive the prestigious National Medal of Science. Established by Congress in 1959, the medal is the nation's highest scientific honor. Kleinrock is receiving the award for "fundamental contributions to the mathematical theory of modern data networks, for the functional specification of packet switching which is the foundation of Internet Technology, for mentoring generations of students and for leading the commercialization of technologies that have transformed the world," the National Science Foundation's citation reads.
Kleinrock wrote the first paper and published the first book on the subject, and directed the transmission of the first message to pass over the Internet. He was also responsible for setting up and running the Network Measurement Center, which tested the limits of the early Internet to evaluate its performance and behavior and improve its operation.
Congratulations to Dr. Kleinrock for a job well done. -- Jonathan Erickson
Queueing, Warteschlangen, Theorie, Markovketten
31-Dec-2002