Communication Network Analysis Notes
About this eBook
Preface This is the latest draft of notes I have used for the graduate course Communication Network Analysis, o ered by the Department of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. The notes describe many of the most popular analytical techniques for design and analysis of computer communication networks, with an emphasis on performance issues such as delay, blocking, and resource allocation. Topics that are not covered in the notes include the Internet protocols at least not explicitly , simulation techniques and simulation packages, and some of the mathematical proofs. These are covered in other books and courses. The topics of these notes form a basis for understanding the literature on performance issues in networks, including the Internet. Speci c topics include The basic and intermediate theory of queueing systems, along with stability criteria based on drift analysis and uid models The notion of e ective bandwidth, in which a constant bit rate equivalent is given for a bursty data stream in a given context An introduction to the calculus of deterministic constraints on tra c ows The use of penalty and barrier functions in optimization, and the natural extension to the use of utility functions and prices in the formulation of dynamic routing and congestion control problems Some topics related to performance analysis in wireless networks, including coverage of basic multiple access techniques, and transmission scheduling The basics of dynamic programming, introduced in the context of a simple queueing control problem The analysis of blocking and the reduced load xed point approximation for circuit switched networks. Students are assumed to have already had a course on computer communication networks, although the material in such a course is more to provide motivation for the material in these notes, than to provide understanding of the mathematics. In addition, since probability is used extensively, students in the class are assumed to have previously had two courses in probability. Some prior exposure to the theory of Lagrange multipliers for constrained optimization and nonlinear optimization algorithms is desirable, but not necessary. I m grateful to students and colleagues for suggestions and corrections, and am always eager for more. Bruce Hajek, December 2006 1
Countable State Markov Processes 1.1
Example of a Markov model
Consider a two-stage pipeline as pictured in Figure 1.1. Some assumptions about it will be made in order to model it as a simple discrete time Markov process, without any pretension of modeling a particular real life system. Each stage has a single bu er. Normalize time so that in one unit of time a packet can make a single transition. Call the time interval between k and k 1 the kth time slot, and assume that the pipeline evolves in the following way during a given slot. If at the beginning of the slot, there are no packets in stage one, then a new packet arrives to stage one with probability a, independently of the past history of the pipeline and of the outcome at state two. If at the beginning of the slot, there is a packet in stage one and no packet in stage two, then the packet is transfered to stage two with probability d1 .