Thursday, February 3
	Ioannis Kontoyiannis, Purdue University
	How Well Can We Compress?
		The enormous growth of digital communications has made apparent the pressing need for efficient data compression. In this talk we will summarize what is known about the fundamental limits of how well data can be compressed (both in the lossless and lossy case). After recalling Shannon's classical information-theoretic answer to the data compression question, we will present recent results describing precisely how close one can come to optimality in practice. The main emphasis will be in avoiding and clarifying asymptotics as much as possible. The issues addressed include: How well can we compress with finite resources? The complexity/redundancy trade-off The price of universality/adaptivity Do all data sources qualitatively behave the same way? We will provide non-asymptotic results as well as limit theorems, refining Shannon's source coding theorems (in the same way, e.g., that the central limit theorem in probability refines the law of large numbers). Interpreting these results can provide intuition about what is possible in practice (at least in principle), and also offer new insights on how to design efficient compression algorithms.

	Thursday, February 10
	James R. Morrison, University of Illinois
	Linear Programming Performance Bounds for Queueing Networks
		For re--entrant lines operating under affine index policies, we develop linear programs to bound network performance. This is done by identification of polyhedral regions in which the average cost inequality has a fixed form when one proposes certain simple surrogates for the differential cost function. The stationary policies subsumed by affine index policies include buffer priority policies, FSMCT (fluctuation smoothing for the mean of the cycle time) policy, and others. In addition, more realistic model features may be incorporated by the approach. The preceeding will be developed for a fixed arrival rate to the network, and following this, we demonstrate how one may obtain functional bound linear programs which provide a functional form bounding the cost function of interest for all arrival rates.

	Thursday, February 17
	Shane Henderson, University of Michigan
	Efficient Simulation of Multiclass Queueing Networks
		Efficient Simulation of Multiclass Queueing Networks Joint work with Sean P. Meyn. Abstract Multiclass queueing networks are a very general class of models that have proven difficult to analyze when compared with other classes of networks such as Jackson networks. Linear programming approaches have been developed to attempt to bound the steady-state performance of a given multiclass queueing network. Such approaches implicitly or explicitly construct a Lyapunov function that simultaneously establishes that the network is stable, and gives bounds on its performance. The Lyapunov function so constructed may be used in a simulation of the network to reduce the variance of the simulation estimator. We describe the general theory behind this approach, provide some examples to show that the variance reduction can be dramatic, and discuss some related problems.

	Thursday, February 24
	Jenny Steichen, University of Illinois
	A heavy traffic limit theorem for the closed Lu-Kumar network
		A functional central limit theorem for a class of time-homogeneous continuous-time Markov processes is presented. This theorem is then applied to the closed Lu-Kumar network to get a heavy traffic limit theorem for the queue lengths in the network.

	Thursday, March 2
	Sanjay Shakkottai, University of Illinois
	An Introduction to Large Deviations in Communication Networks
		In this talk, we will review the basic ideas in large deviations and look at some of its applications in communication networks. In particular, we will consider applications to admission control in single class networks as studied in Botvich & Duffield and deVeciana & Walrand.

	Thursday, March 30
	Maury Bramson, University of Minnesota
	State Space Collapse and Heavy Traffic Limits
		The class of multiclass queueing networks for which heavy traffic limits have been rigorously derived is limited. State space plays an important role, and allows one to reduce the state at each station to a single work parameter. Under appropriate conditions, heavy traffic limits then follow from state space collapse through work of Williams. Disciplines under which state space collapse and the corresponding heavy traffic limits hold include FIFO networks of Kelly type, HLPPS networks, and certain static priority networks such as FBFS and LBFS.We will summarize relevant aspects of the above work. The main ideas behind the demonstration of state space collapse will be discussed.

	Thursday, April 6
	Ruth Williams, University of California, San Diego
	Dynamic Control of Stochastic Networks in Heavy Traffic
		Stochastic networks are used as models for complex manufacturing, telecommunications and computer systems. Some of these networks allow for flexible scheduling of jobs through dynamic (state-dependent) alternate routing and sequencing, hereafter collectively referred to as dynamic scheduling. Usually these models cannot be analyzed exactly, and it is a challenging problem to design dynamic scheduling policies for such networks that are simple to implement and yet are approximately optimal in an appropriate sense. As one approach to this problem, J. M. Harrison proposed Brownian control problems (BCPs) as formal heavy traffic approximations to dynamic scheduling problems for stochastic networks. Subsequently, various authors combined analysis of their optimal solutions to suggest original and attractive policies for certain specific stochastic network control problems. Despite these successes for specific problems, there is, as yet, no general rigorous approach to analyzing BCPs, inferring good policies from their solutions, and proving asymptotic optimality of such policies. This talk will survey developments in this direction to date.

	Friday, April 7 269 Everitt Lab 3-4 pm
	Ruth Williams, University of California, San Diego
	The measure-valued fluid limit for a processor sharing queue
		This talk concerns a single server queue with a processor sharing service discipline. This system is naturally modeled using a measure-valued process that keeps track of the residual service times of all customers currently in the system. The fluid limit for this model will be established as the unique solution of a nonlinear integral equation. The large time asymptotics of this fluid model will be described. This talk is based on joint work with Christian Gromoll and Amber Puha.

	Thursday, April 13
	Pierre Seri, CSL, UIUC
	Applying heavy traffic limits to the control of networks: the BIGSTEP approach
		This seminar considers the application of heavy traffic limits to control of highly loaded networks. Despite the extent of the literature on heavy traffic limits in different types of networks, little is known about the translation of these results into techniques that can be used to control practical networks. Indeed there is no general theory that relates the properties of the heavy traffic limits to that of the sequences of heavily loaded networks that yield these limits. However, developing such a theory is of importance if heavy traffic limits are to be applied to the analysis of heavily loaded networks. J. Harrison, with the BIGSTEP approach, presents a method to apply heavy traffic limits to controlling networks. The idea is to use properties of the optimal control of the {\em Brownian} limit to devise discrete-review policies for practical networks. The review points in these policies are widely spaced in time---thus justifying the name of the method. This seminar reviews the BIGSTEP approach and its application to examples of networks, and {\em investigates } the relationship between the control policy obtained through the BIGSTEP approach and that obtained through a similar technique applied to the fluid limit of the sequence of networks.

	Thursday, April 13
	Richard Dubrawski, CSL, UIUC
	Open Processing Networks: Canonical Representation of Workload
		The talk will cover J. Michael Harrison's 1999 paper, Brownian Models of Open Processing Networks: Canonical Representation of Workload. The paper develops definitions of workload, sysem load, and sensitivity for a general class network models. The talk will draw upon the recent talks by Maury Bramson, Ruth WIlliams and Pierre Francios regarding model reduction realized through the workload formulation denoted by W(t)=MZ(t). A canonical choice for the basis matrix M will be constructed.
	Thursday, May 4 Ravi Mazumdar, Purdue University The mathematics of large telecommunication networks The analysis and design of telecommunications networks is not an easy task even in the best of situatons. In the context of modern high-speed networks the problem is made even worse by the sheer diversity and rates of traffic (of the order of gigabits/s) and the vast amount of buffering and bandwidth. The problem is further complicated by the fact that networks need to be engineered to very stringent performance requirements such as cell or packet loss of the order of $10^{-9}$. This makes the utility of simulations questionable since simulating such systems to engineer loss involves a sample size which exceeds the cycle lengths of even the best random number generators. Moreover for design we need to understand how network performance depends on traffic and resource parameters. For this analytic insights are necessary and yet we cannot perform thousands of simulations when the results would be questionable. It would appear that the problems are insurmountable. However, we will see the "largeness" of such networks can actually be used to advantage. Using various specialized tools we can actually obtain "closed form" answers which are extremely accurate and obtain much insight on how traffic parameters affect performance. The use of these techniques will be demonstrated in the context of the design of admission control schemes.