Performance Analysis of Complex Networks and Systems

This rigorous, self-contained book describes mathematical and, in particular, stochastic and graph theoretic methods to assess the performance of complex networks and systems. It comprises three parts: the first is a review of probability theory; Part II covers the classical theory of stochastic processes (Poisson, Markov and queueing theory), which are considered to be the basic building blocks for performance evaluation studies; Part III focuses on the rapidly expanding new field of network science. This part deals with the recently obtained insight that many very different large complex networks - such as the Internet, World Wide Web, metabolic and human brain networks, utility infrastructures, social networks - evolve and behave according to general common scaling laws. This understanding is useful when assessing the end-to-end quality of Internet services and when designing robust and secure networks. Containing problems and solved solutions, the book is ideal for graduate students taking courses in performance analysis.1. Introduction; Part I. Probability Theory: 2. Random variables; 3. Basic distributions; 4. Correlation; 5. Inequalities; 6. Limit laws; Part II. Stochastic Processes: 7. The Poisson process; 8. Renewal theory; 9. Discrete-time Markov chains; 10. Continuous-time Markov chains; 11. Applications of Markov chains; 12. Branching processes; 13. General queueing theory; 14. Queueing models; Part III. Network Science: 15. General characteristics of graphs; 16. The shortest path problem; 17. Epidemics in networks; 18. The efficiency of multicast; 19. The hopcount and weight to an anycast group; Appendix A. A summary of matrix theory; Appendix B. Solutions to problems.