A Tutorial on Queuing and Trunking with Applications to Communications

The motivation for developing this synthesis lecture was to provide a tutorial on queuing and trunking, with extensions to networks of queues, suitable for supplementing courses in communications, stochastic processes, and networking. An essential component of this lecture is MATLAB-based demonstrations and exercises, which can be easily modified to enable the student to observe and evaluate the impact of changing parameters, arrival and departure statistics, queuing disciplines, the number of servers, and other important aspects of the underlying system model. Much of the work in this lecture is based on Poisson statistics, since Poisson models are useful due to the fact that Poisson models are analytically tractable and provide a useful approximation for many applications. We recognize that the validity of Poisson statistics is questionable for a number of networking applications and therefore we briefly discuss self-similar models and the Hurst parameter, long-term dependent models, the Pareto distribution, and other related topics. Appropriate references are given for continued study on these topics. The initial chapters of this book consider individual queues in isolation. The systems studied consist of an arrival process, a single queue with a particular queuing discipline, and one or more servers. While this allows us to study the basic concepts of queuing and trunking, modern data networks consist of many queues that interact in complex ways. While many of these interactions defy analysis, the final chapter introduces a model of a network of queues in which, after being served in one queue, customers may join another queue. The key result for this model is known as Jackson's Theorem. Finally, we state the BCMP Theorem, which can be viewed as a further extension of Jackson's Theorem and present Kleinrock's formula, which can be viewed as the network versionof Little's Theorem. Table of Contents: Introduction / Poisson, Erlang, and Pareto Distributions / A Brief Introduction to Queueing Theory / Blocking and Delay / Networks of Queues

William H. Tranter is the Bradley Professor of Communications, Virginia Polytechnic Institute and State University. He received the Ph.D. degree in Electrical Engineering from the University of Alabama in 1970. He then joined the faculty of the University of Missouri-Rolla. Professor Tranter served as Assistant (1980-84) and Associate (1984-85) Dean of Engineering for Graduate Affairs and Research. In 1985 he was appointed Schlumberger Professor of Electrical Engineering and he continued to serve in that position until his early retirement from the University of Missouri in 1997. In 1997 he joined the Electrical and Computer Engineering faculty of Virginia Tech as the Bradley Professor of Communications. In 1995, Professor Tranter served as an Erskine Fellow at Canterbury University (Christchurch, New Zealand) where he conducted research and developed a course on Computer-Aided Design and Analysis of Communications Systems. Professor Tranter's current area of interest is computer-aided design and performance evaluation of communication systems and simulation techniques with applications to wireless cellular systems. His research efforts have been supported by the NSF, ONR, DARPA, Schlumberger Foundation, NASA, McDonnell-Douglas, Boeing, GE Aerospace, LG Corporation, Raytheon and Batelle Memorial Laboratories. He also has interest in developing computer-based design and analysis tools for research and educational use and was supported by NSF to develop a three-course sequence in wireless communications complete with simulation-based demonstrations and laboratories utilizing MATLAB. Professor Tranter has been very active in professional activities. He served as chair of a number of technical committees within the IEEE Communications Society. From 1988 to 1998 he served as Editor-in-Chief of the IEEE Journal on Selected Areas in Communications. From 1997-1999 he served the Communications Society as Director of Journals and in 1999 was elected to the Board of Governors. Professor Tranter also served on the IEEE Awards Board and as chair of the Alexander Graham Bell Award Committee. In 2001 Professor Tranter was elected Vice-President, Technical Activities of the IEEE Communications Society. Professor Tranter received an IEEE Centennial Medal in 1984, a Millennium Medal in 2000, the Donald McLellan Meritorious Service Award from the IEEE Communications Society in 2000, and the Publications Exemplary Service Award in 2001. He was elected a Fellow of the IEEE in 1985. Most recently, Professor Tranter served a three-year term at the National Science Foundation as Program Director for the areas of communications, networking, information theory, and coding.Allen B. Mackenzie is an Associate Professor in the Bradley Department of Electrical and Computer Engineering, Virginia Polytechnic Institute and State University. He received his bachelor's degree in Electrical Engineering and Mathematics from Vanderbilt University in 1999. In 2003 he earned his Ph.D. in electrical engineering at Cornell University and joined the faculty of the Bradley Department of Electrical and Computer Engineering at Virginia Tech, where he is now an associate professor. During the 2012-2013 academic year, he is an E.T.S. Walton Visiting Professor at Trinity College Dublin. Prof. MacKenzie's research focuses on wireless communications systems and networks. Hiscurrent research interests include cognitive radio and cognitive network algorithms, architectures, and protocols and the analysis of such systems and networks using game theory. His past and current research sponsors include the National Science Foundation, the Defense Advanced Research Projects Agency, the National Institute of Justice, and the U.S. Army. Prof. MacKenzie is an associate editor of the IEEE Transactions on Communications and the IEEE Transactions on Mobile Computing. He also serves on the technical program committee of several international conferences in the areas of communications and networking, and is a regular reviewer for journals in these areas. Prof. MacKenzie is a senior member of the IEEE and a member of the ASEE and the ACM. In 2006, he received the Dean's Award for Outstanding New Assistant Professor in the College of Engineering at Virginia Tech. He is the author of more than 50 refereed conference and journal papers and the co-author of the book Game Theory for Wireless Engineers.