Bert Zwart (VU University Amsterdam), March 26, 2009
Joint work with Adam Wierman (Caltech)

For a GI/GI/1 queue it is well known that, in a large deviations setting, FIFO is optimal for light-tailed service times, and service disciplines such as PS (Processor Sharing) and SRPT (Shortest Remaining Processing Time) are optimal for heavy-tailed service times. It is also known that PS and SRPT do not perform well for light-tailed service times, while FIFO does not perform well for heavy-tailed service times. The natural question is whether it is possible to construct a single scheduling discipline that is competitive with FIFO for light-tailed service times and competitive with SRPT for heavy tailed service times.

The goal of this talk is to convince the audience that the answer to this question is no.

Seva Shneer (EURANDOM), March 24, 2009
Joint work with Vitali Wachtel (University of Munich).

Heavy-traffic analysis of the maximum of an asymptotically stable random walk.

For families of random walks $\{S_k^{(a)}\}$ with $\mathbf E S_k^{(a)} = -ka < 0$ we consider their maxima $M^{(a)} = \sup_{k \ge 0} S_k^{(a)}$. We investigate the asymptotic behaviour of $M^{(a)}$ as $a \to 0$ for asymptotically stable random walks. This problem appeared first in the 1960's in the analysis of a single-server queue when the traffic load tends to $1$ and since then is referred to as the heavy-traffic approximation problem. Kingman and Prokhorov suggested two different approaches which were later followed by many authors. We give two elementary proofs of the main result, using each of these approaches. It turns out that the main technical difficulties in both proofs are rather similar and may be resolved via a generalisation of the Kolmogorov inequality to the case of an infinite variance. Such a generalisation will also be discussed during the talk.

Rüdiger Schultz (Department of Mathematics, University of Duisburg-Essen), March 20, 2009

The two-stage, or recourse, model is a traditional object in stochastic programming. The aim is to optimize a nonanticipative first-stage decision within a two-stage problem under stochastic data uncertainty. When passing, in this context, from linear to mixed-integer linear models, some basic convexity properties are lost. Then structural and algorithmic analysis must be rethought almost from the beginning. In the talk we start out from risk neutral models which are extended towards risk aversion by incorporation of risk measures or stochastic dominance constraints. We analyze the arising structures and study model stability when perturbing the underlying probability distribution. For finite probability spaces, we derive equivalent block-structured mixed-integer linear programs. These models quickly exceed the capabilities of standard solvers which motivates the search for decomposition techniques. We conclude with a few such alternatives and demonstrate their computational impact on test instances inspired by power system optimization under uncertainty.

The whereabouts of customers in a queueing system interact. If more customers join the queue, one's waiting time may increase, to such a level that one may prefer not to join at all. But who decides who will join and who will not? Also, if too many packets are routed along one path, then an individual packet might be better assigned to some other path. But who will select this path, the individual himself or a central planner? Their objective may not be the same. For another decision problem, suppose acquiring the information which line or path is shorter comes with some cost. What should one do? On one hand, one has an incentive to pay for this information. On the other hand, this incentive decreases the larger the fraction becomes of those who acquire this information as the more informed customers will tend to make the two lines more even anyhow. The tutorial will deal with these and similar decision models.

Many decision problems in queues can be modeled as non-cooperative games. In such games players (or, in our case, customers, service providers or routers) have to take actions. While selecting their actions they are not fully informed on the actions taken, or to be taken, by others. In fact, in many situations, decision making is done simultaneously. Of course, each player likes to optimize his gains (utility), but one's optimal action is a function of what others are doing. Here the solution concept of Nash equilibrium is introduced and it replaces the concept of optimization which is used when a single decision maker is assumed. Specifically, Nash equilibrium is a set of strategies, one for each player (usually referred to as a strategy profile), so that assuming that all obey this recipe, each of the individuals does his best by following his share of this profile as well.

Most of the talk will be devoted to customers as decision makers who take actions as time progresses. Examples of that are to join or not to join the queue, which line to join, to pay or not to pay a premium in order to get higher priority, or to renege or not from the queue once waiting conditions deteriorate. We will also consider central planning. Here the assumption is that a regulator selects some parameters while trying to maximize the society’s revenues. Examples of that are selecting entry fees, designing set of priority premiums, or selecting service rates (ie, bandwidth allocation). The central planner analyze their revenues by considering the Nash equilibria in the game between customers resulting from any of their decisions. The talk is based on a 2003 book co-authored with Refael Hassin bearing the title To Queue or not to Queue: Equilibrium Behavior in Queueing Systems, and published by Kluwer's International Series. If time allows some recent results for M/G/1 queue will be dealt with as well.

Michel Mandjes (Korteweg-de Vries Institute for Mathematics, University of Amsterdam & CWI, Amsterdam & Eurandom, Eindhoven), February 19, 2009

Link dimensioning, i.e., selecting a (minimal) link capacity such that the users’ performance requirements are met, is a crucial component of network design. It requires insight into the interrelationship between the traffic offered (in terms of the mean offered load M, but also its fluctuation around the mean, i.e., ‘burstiness’), the envisioned performance level, and the capacity needed. We first derive, for different performance criteria, theoretical dimensioning formulae that estimate the required capacity C as a function of the input traffic and the performance target. For the special case of Gaussian input traffic these formulae reduce to C = M + a*V , where a directly relates to the performance requirement (as agreed upon in a service level agreement) and V reflects the burstiness (at the timescale of interest).We also observe that Gaussianity applies for virtually all realistic scenarios; notably, already for a relatively low aggregation level the Gaussianity assumption is justified. As estimating M is relatively straightforward, the remaining open issue concerns the estimation of V .We argue that, particularly if V corresponds to small time-scales, it may be inaccurate to estimate it directly from the traffic traces. Therefore, we propose an indirect method that samples the buffer content, estimates the buffer content distribution, and ‘inverts’ this to the variance. We validate the inversion through extensive numerical experiments (using a sizeable collection of traffic traces from various representative locations); the resulting estimate of V is then inserted in the dimensioning formula. These experiments show that both the inversion and the dimensioning formula are remarkably accurate.

Reuven Rubinstein( Faculty of Industrial Engineering and Technion, Israel Institute of Technology,Haifa , Israel),
March 9 & 11, 2009

We consider a Levy-driven tandem queue with an intermediate input assuming that its buffer content process obtained by a reflection mapping has the stationary distribution. For this queue, no closed form formula is known. We consider only light-tailed inputs, and derive exact asymptotics for the tail distribution of convex combination of two buffer contents. This includes the marginal stationary distributions of the buffer contents and their sum as special cases. These results generalize recent ones of Lieshout and Mandjes (2008) for the corresponding tandem queue without an intermediate input.

Yoni Nazarathy (The University of Haifa), January 8, 2009
Joint work with Gideon Weiss.

We analyze the variance curve of the output counting process of some queueing systems. Specifically we consider general loss-less single station queues, finite capacity queues, a push-pull queuing network and general re-entrant lines with infinite inputs. We show how to apply several methods to evaluate the asymptotic variance rate of outputs of these systems.

For loss-less stable single station queues we show that the variance rate of outputs equals that of the arrivals. For finite capacity queues we briefly survey a previously presented result and review the use of some matrix-analytic methods. For the push-pull queueing network we introduce a renewal-reward approach for obtaining the linear asymptote of the variance curve. We also discuss how the renewal-reward approach may be used for efficient simulation analysis of the variance rate of outputs resulting from regenerative systems.

We continue with a fluid scale and a diffusion scale analysis of the push-pull network and show how to obtain a more general result regarding the variance rate of outputs. This same method is applied to a general re-entrant line with an infinite supply of work. For this model we show that the variance rate of outputs only depends on the bottleneck machine and has a form of the variance rate of a related renewal process.

A routing policy for the X call-center model designed to respond to unexpected overloads

We consider a large-scale call-center model - a stochastic model with two customer classes and two associated service pools, with each pool primarily dedicated to the designated customer class, but with all agents cross-trained and allowed to serve the other class, even though they may do so inefficiently. Under normal loads, we want class-i customers to be served by type-i agents, but we automatically activate sharing (serving the other class) when there is an unexpected overload. We propose a Fixed-Queue-Ratio with Thresholds (FQR-T) control for available agents. We develop deterministic fluid approximations to describe the system performance when overloads occur, and show that this fluid approximations hold as heavy-traffic limits of the appropriately scaled model. The proof of convergence involves a heavy-traffic averaging principle.

Dmitriy Kim, Kazakh National University (visiting Heriot-Watt University), December 10, 2008

Ruin probability for a process with switching

Ruin probability is considered for a Markov process with one level of switching between two independent Levy processes one of which is spectrally negative and another is a compound Poisson process with drift. There is given a partition of the real line into two sets and, with each set, a probability distribution is associated. When a Markov process has a value in one of these sets, its next increment has the distribution associated with this set. Explicit representations were found for the ruin probability in terms of ladder heights. As a consequence, results were obtained for a risk process, where the premium rate and the claim size depend on whether current reserve is above or below a certain threshold

presentation

We study a collector's problem with K renewal arrival processes for the items of the different types, where the objective is to collect complete sets. In particular we derive the asymptotic distribution of the sequence of inter-arrival times between set completions. Joint work with Wolfgang Stadje.

We consider a (doubly) reflected Levy process without negative jumps where the Levy exponent is controlled by threshold levels based on the value of the process. We assume that the process can be in two stages, whereas in each stage there typically is a different service speed, drift parameter, or arrival rate. First, we consider a hysteretic control policy. Under such a policy, there is a retardation between switchings of the Levy exponent. Second, we consider a model where the exponent can only be observed (and also adapted) at Poisson instants. This may represent practical situations where information about the process is not continuously available. The aim of this talk is to determine the steady-state workload distributions and give intuition for the results.

In this talk we consider the solution to the classical control problem due to De Finetti (1957) and Gerber (1969) which concerns the optimal payment of dividends from an insurance risk process prior to ruin. The calculations we present go much further than existing literature in that our calculations are valid for a general spectrally negative Levy risk process as opposed to the classical Cramer-Lundberg process. Related is the problem where we impose the restriction that ruin be prevented by bail-out loans. Drawing on the fluctuation theory of spectrally negative Levy processes we give an explicit analytical description of the optimal strategy in the set of barrier strategies and the corresponding value function, for either of the problems. Subsequently we investigate when the dividend policy that is optimal amongst all admissible ones takes the form of a barrier strategy. We also calculate distributional properties of the net present value of dividends paid out in the optimal strategy as well as the moments of the de cit at ruin and the Laplace transform of the red period. The technique we use to derive these quantities appeals principally to excursion theory rather than integro-differential equations and makes a new link with the distribution of integrated exponential subordinators. Finally, we also consider the problem with fixed cost for taking out dividends.

We consider an $M/PH/1$ queue with workload-dependent balking. An arriving customer joins the queue and stays until served if and only if the system workload is no more than a fixed level at the time of his arrival. We begin by considering a fluid model where the buffer content changes at a rate determined by an external stochastic process with finite state space. We derive systems of first-order linear differential equations for the mean and LST (Laplace-Stieltjes Transform) of the busy period in this model and solve them explicitly. We obtain the mean and LST of the busy period in the $M/PH/1$ queue with workload-dependent balking as a special limiting case of this fluid model.

A general method is discussed to determine uncertainty intervals for performance measures of Markov chains given an uncertainty region for the parameters of the Markov chains. We investigate the effects of uncertainties in the transition probabilities on the limiting distributions, on the state probabilities after a number of steps, on mean sojourn times in transient states, and on absorption probabilities for absorbing states. We show that the uncertainty effects can be calculated by solving linear programming problems in the case of interval uncertainty for the transition probabilities, and by second order cone optimization in the case of ellipsoidal uncertainty. Many examples are given to illustrate the theory.

The talk is about some recent results by Frank Kelly, Steven Low and C. Papadimitriou together with some classical results by Braess and Wardrop. The talk will be mostly based on the paper: Frank Kelly, "The mathematics of traffic in networks". Chapter in "The Princeton Companion to Mathematics" (Editor Timothy Gowers; June Barrow-Green and Imre Leader, associate editors) Princeton University Press, 2008.

Consider a model of a congestion network where two batch service queues are available for general customers wanting to travel from a source to a destination. Viewing this model as a continuous time Markov process, we wish to find state dependent user equilibrium policies using a constructive proof and a computer iterative approach.

Ad hoc network routing protocols may fail to operate in the absence of an end-to-end connection from source to desti- nation. This deficiency can be resolved by so-called oppor- tunistic networking which exploits the mobility of the nodes by letting them operate as relays according to the store- carry-and-forward paradigm.

In this talk, I will show the delay analysis of a small opportunistic network by considering a tandem queueing system. An exact packet-level analysis by applying ideas from the polling literature will be presented.
Due to the state-space expansion, this analysis cannot efficiently be applied for all model parameter settings. For this reason, an analytical approximation will be constructed and its excellent performance will be shown. Finally, I will conclude the talk by illustrating some numerical results on the mean end-to-end delay and the delay optimization under power control.

We develop a conservation law for a multi-class $GI/GI/1$ queue operating under a general work-conserving scheduling discipline. For single-class single-server queues, conservation laws have been obtained for both non-anticipating and anticipating disciplines with general service time distributions. For multi-class single-server queues, conservation laws have been obtained for (i) non-anticipating disciplines with exponential service time distributions and (ii) non-preemptive non-anticipating disciplines with general service time distributions. The unifying conservation law we develop generalizes already existing conservation laws. In addition it covers popular non-anticipating multi-class time-sharing disciplines such as Discriminatory Processor Sharing (DPS) and Generalized Processor Sharing (GPS) with general service time distributions. As an application we show that the unifying conservation law can be used to compare the expected unconditional response time under two scheduling disciplines.

Zbigniew Palmowski (Mathematical Institute University of Wroclaw), April 22, 2008

Cramér asymptotics for finite time first passage probabilities for general Lévy processes.

We derive the exact asymptotics of the finite time first passage probability over level x before time t if x and t tend to infinity with x/t constant, for a general Lévy process that admits exponential moments. The proof is based on a renewal argument and two-dimensional renewal theorems of Höglund (1990). This is a joint work with M. Pistorius.

Multivariate Risk Modelling Seminar, April 15, 2008
(Delft University - CWI - EURANDOM)

(12.30-14.00 Lunch in the Faculty Club TU/e - for invitees)
14.00-14.30: Fang Fang (TU Delft) - Fast pricing of various options under Levy processes
14.30-15.00: Xinzheng Huang (TU Delft) - Portfolio loss modelling
15.00-15.15: Break
15.15-15.45: Lech Grzelak (TU Delft) - Hybrid products
15.45-16.15: Viktoriya Masol (EURANDOM) - Pricing and hedging CDOs with Levy base correlation
16.15-16.30: Break
16.30-17.00: Henrik Jönsson - Pricing of constant maturity CDSs and other credit derivatives
17.00-17.30: Wim Schoutens (KU Leuven) - Credit CPPI and CPDO pricing

We address the problem of evaluating the asymptotic normalized average distributions of a class of combinatorial configurations in random, regular and irregular binary low-density parity-check (LDPC) code ensembles. Among the configurations considered are trapping and stopping sets. These sets represent subsets of variable nodes in the Tanner graph of a code that play an important role in determining the height and point of onset of the error-floor in its performance curve. The techniques used for deriving the spectra include large deviation theory and statistical methods for enumerating binary matrices with prescribed row and column sums.

The Asymptotic Variance Rate of the Output Process of Finite Capacity Queues

It is well known that the output process of many infinite capacity birth-death queues is a Poisson process. Thus for such queues the output rate equals the asymptotic variance rate (the asymptotic rate of increase of the variance function). The situation is quite different for finite capacity systems: Here it is known that in most cases the output process is not a renewal process but rather a more complex Markov Arrival Process (MAP).

In this case we develop a formula for the asymptotic variance rate of the form lambda* + R where lambda* is the output rate and R is an expression which may be easily evaluated. The proof relies on a relationship between a class of MAPs and Markov Modulated Poisson Process (MMPP) and uses results of W. Whitt with regards to the asymptotic variance rate of MMPPs that have a birth-death structure.

For the M/M/1/K queue, our formula evaluates to a closed form expression that shows a rather surprising phenomena: When the system is balanced (i.e. - the arrival and service rates are equal), R/lambda* is minimal. The situation is similar for the M/M/c/K queue and the Erlang loss system. Here also, balancing the system parameters results in a pronounced decrease in the asymptotic variance rate. We call this phenomenon, BRAVO (the acronym stands for Balancing Reduces Asymptotic Variance of Outputs) and end with some numerical results related to BRAVO that leave some open questions.

Brooke Shrader (University of Maryland, Electrical and Computer Engineering, USA ), April 8, 2008
Joint work with A. Ephremides at the University of Maryland.

In the recently developed concept of network coding, rather than replicating and retransmitting packets as they traverse the network, a node can encode groups of packets (e.g., by forming an XOR) before sending them on toward their destination. By employing the network coding approach, the maximum multicast throughput of a network can be achieved. We explore a bulk-service queueing model for network coding. We consider a random linear coding scheme that adapts to the amount of traffic at the source node and present results on the delay of this scheme.

Yahya Al-Harthi (King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia), February 14, 2008

Distributed Scheduling: A Look at Throughput and Stability in Random Access Networks

In wireless communications, the phenomena of fading lead to the development of many techniques to combat it. Recently, it has been shown that such phenomena can be exploited. In multiuser wireless systems, multiuser diversity can be exploited by scheduling users to transmit when their channel conditions are favorable. This kind of scheduling, called "opportunistic scheduling", leads to a sum throughput that increases with the number of users and, in certain cases, achieves capacity. However, the scheduling algorithm requires a global knowledge of every user’s channel gain, which may be difficult to obtain in some situations. Thus, a distributed scheduling algorithm would be very appealing even if it could only obtain a certain fraction of the capacity region of a centralized scheduling scheme.

In this work we consider distributed scheduling in wireless networks subject to simple collision constraints. We assume that nodes access the channel based a modified slotted Aloha protocol, where each node adapts its transmission probability based on a channel threshold that will also change to stabilize the queue. Initially, we will consider only the case of two users and derive the stability and throughput regions.

Biography: Dr. Yahya Al-Harthi is currently an Assistant Professor at King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia.

His research interests are generally in wireless communications and networking specifically in opportunistic scheduling algorithms, diversity techniques, random access protocols, radio resource management, and performance analysis and modeling of communications networks. [www.Harthi.net, email: yHarthi@kfupm.edu.sa]

Yoav Kerner (EURANDOM), February 5, 2008
Joint work with Moshe Haviv and Offer Kella (Hebrew university)

In most decision models dealing with unobservable stochastic congested environments, one looks for a (Nash) equilibrium behaviour among customers. This is a strategy that if adopted by all, then under the resulting steady-state conditions, the best response for an individual is to adopt this strategy too. The purpose of this paper is to look for a simple decision problem but where the assumption of steady-state conditions is removed. Specifically, we consider an M/M/N/N loss model in which one pays for trying to get service but is rewarded only if one finds an available server. The initial conditions at time zero are common-knowledge and each customer possesses his arrival time as his private information. The equilibrium profile tells each arrival if to try or not (randomization allowed) given his time of arrival. We show that all join up to some point of time. At this point, there is a quantum drop in the joining probability from one to some fraction. From then on their joining probability continuously converges to the equilibrium joining probability under the model which assumes steady-state.

A large variety of communication systems, including telephone and data networks, can be represented by so-called Whittle networks. The stationary distribution of these networks is insensitive, depending on the service requirements at each node through their mean only. These models are of considerable practical interest as they lead to engineering rules which are robust to the evolution of traffic characteristics. We consider the problem of optimal dynamic load balancing in stochastic networks, which is known to be a difficult optimization problem. By restricting the admissible set of solutions to the solutions preserving the structure of Whittle networks, we investigate the possibility of obtaining useful and robust approximations of the optimal performance.

Recent developments in the theory of scale functions for spectrally negative Levy processes

In the past 10 years, more and more studies which use the theory of spectrally negative L'evy processes have relied on the theory of scale functions. Such functions appear in virtually all identities concerning the fluctuations of the latter processes but historically very few concrete examples are known of these scale functions and an understanding of their general analytical properties is somewhat limited. I will talk about results from three recent parallel papers written concurrently in collaboration with Victor Rivero, Renming Song and Friedrich Hubalek which attempt to significantly improve on this situation.

Balakrishna Prabhu (EURANDOM), January 9, 2008
Joint work with Onno Boxma (TU/e and EURANDOM).

In the first part of the talk we focus on file-dissemination in a Peer-to-Peer network. In particular, we are interested in knowing how the file-dissemination time scales with the number of nodes in the network. Our main result shows that depending on the behavior of the nodes, two vastly different scaling laws can be obtained. This is joint work with Sindo Nunez-Queija (CWI and TNO). The second part of the talk focuses on the analysis of a queue with admission control and a variable-rate input source. Upon arrival, a packet is admitted with a probability that depends on the current queue length, and based on this decision the input source either increases or decreases its sending rate. This queueing model can be related to the interaction between congestion control algorithms and router buffers in the Internet.

In my talk I consider examples of microscopic and macroscopic dynamics in stochastic networks. I show how to use Markov chains, percolation and random graph colouring to rigorously solve challenging problems in information and communication systems. Among the problems addressed are insensitivity and transient behaviour in queues, connectivity, and interference of wireless LANs. The talk is intended for probabilists looking for applications of their knowledge as well as for ICT specialists seeking for new ideas. Part of this talk is based on papers written with Denis Denisov, Ken Duffy and Neil O'Connell.

In the first part of the talk, I will go over the basic results of Chapter 8 of Kyprianou's book. These are the computation of the Laplace transform of the exit time from an interval for a spectrally negative Levy process and for the process reflected in its past maximum or minimum.

In the second part, I will show an application of these computations in the study of diffusion in a spectrally negative environment.

Dmitriy Kim (Actuarial Mathematics and Statistics, Heriot-Watt University, Edinburgh), November 20

We study the so called oscillating random processes, or random processes with several levels of switching. There is given a partition of the real line into a finite number of sets and, with each set, there is associated a probability distribution. When a Markov chain takes a value in one of these sets, its next increment has the distribution associated with this set. The first half of the talk (joint with Vladimir Lotov) is devoted to the asymptotics of distribution of oscillating random walk with two levels of switching. In the second half we study ruin probability for process with one level of switching.

Fluid limits are a powerful analytical tool commonly used in stability analysis and control of queueing systems. However, it appears not yet to be well understood when a given queueing system has a unique fluid limit. This talk outlines some examples and conjectures towards a better understanding of this issue.

This seminar is based on Chapter 7 of Kyprianou’s book “Introductory Lectures on Fluctuations of Levy Processes with Applications”. This chapter is devoted to studying how the Wiener-Hopf factorization can be used to characterize the behaviour of any Levy process at first passage over a fixed level.

Stefan Thonhauser Johann Radon Institute for Computational and Applied Mathematics (RICAM), Linz, Austria),
October 11, 2007

In the classical Cramer-Lundberg risk model the problem of maximizing the expected cumulated discounted dividends is a widely discussed topic. In the most general case within this framework it is proved (Gerber 1969, Azcue and Muler 2005, Schmidli 2006) that the optimal dividend strategy is of the not very intuitive band strategy type. We discuss this maximization problem in a modified setting including a constant force of interest in the risk model. The value function can be identified in the set of viscosity solutions of the associated HJB equation and the optimal dividend strategy in this risk model with interest can be derived. (Joint work with Hansjoerg Albrecher, TU Graz)

Stelios Bekiros (Center for Nonlinear Dynamics in Economics and Finance, Department of Quantitative Economics, Faculty of Economics & Econometrics, University of Amsterdam), October 8, 2007

The implementation of quantitative finance models is a vital concern for all financial institutions and this trend has accelerated in recent years with regulatory processes such as Basel II. A synopsis of some practical modelling techniques of quantitative risk management for real-world problems is presented. These methodologies are drawn from diverse disciplines, such as geophysics, meteorology, engineering, econometrics, statistics etc. Some concepts discussed include multivariate extreme value theory (copulas), computational intelligence models, signal processing and filtering, nonlinear time series econometrics, nonlinear causality & dependence etc. Nevertheless, “quants” have to operate in an environment where additional non-quantitative skills are equally important! Communication is certainly the most important of all…

In this talk we will take a look at some continuity results for jump processes. What we refer to as a jump process is a generalization of what is known in the literature as a Generalized Semi-Markov process, and continuity results are known for these processes, assuming that events that trigger jumps are not allowed to occur simultaneously. We will first show how a sequence of jump processes can converge under the standard Skorohod J_1-metric to another jump process, which is analogous to the result of Whitt (Math of OR, 1980). We will then discuss how our method of proof also shows how similar results can be derived when you allow triggering events in the limiting process to occur simultaneously, but in this case a weaker topology on the path space must be considered. This is a joint (and part of an ongoing) work with R. F. Serfozo.

Peter den Iseger (Cardano, NL), June 19, 2007

New algorithms for Laplace Transform Inversion

The need for advanced numerical techniques in computational probability and finance is rapidly increasing. Many fast and efficient numerical transform inversion algorithms which can be employed to solve many of the problems arising in computational probability and finance have already been published in academic literature. However flexible, fast and precise, these algorithms also have many limitations: they cannot tackle important problems such as iterative algorithms (for instance recursion, widely employed for dynamic programming style problems), Levy process based modeling, or problems where the inverse transform as well as the transform itself needs to be computed (a good example is the waiting time distribution in a G\G\1 queue). These inversion algorithms perform the inversion in a number of points at a time. On the other hand, the numerical inversion method we are about to introduce is a piecewise inversion: we employ a Gaussian quadrature rule in order to compute the coefficients of the Legendre expansions of the desired function on all intervals [k,(k + 1). The two key differences, which enable the new numerical technique to tackle a much wider class of problems than its forebears, can be summarized as follows: 1)The original function f (obtained after the numerical inversion) can be evaluated in arbitrary points x_k (instead of only in points k, k = 0, 1,...).
2)The new method works both ways: if some numerical values of the original function f are given, then the algorithm generates its Laplace transform Lf (thus no closed-form analytical expression is needed!), and vice versa: given some numerical values of the Laplace transform, the original function f can be obtained in arbitrary points. These properties enable one to use the inversion algorithm iteratively, hence solving problems such as pricing guaranteed return rate products, fast convolution transforms, Ladder algorithms and the waiting time distribution in a G\G\1 queue. High dimensional versions of the algorithms are very efficient since they exploit a embedded Kronecker product structure and use efficient high dimensional versions of the fast Fourier transform. The precision and robustness of the algorithms is illustrated by a large number of numerical examples.

A.T.M. Aerts (TU/e, The Netherlands), June 18, 2007

Modelling and simulation of the CMS Tier0 input buffering process

The CMS experiment at CERN will produce large amounts of data in short time periods. Because the data buffers at the experiment are not large enough, this data needs to be transferred to other storages. The CMS Tier0 will be an enormous job processing and storage facility at the CERN site. One part of this Tier0, called the Tier0 input buffer, has the task to readout the experiment data buffers and to supply these data to other tasks that need to be carried out with it (such as storing). It has to make sure that no data is lost. The buffer will be implemented with commodity disk servers and the question is how many servers minimally are needed? In this talk we describe the modelling and simulation of the buffering process to compare different scenarios for a set of disk servers that can accomplish the Tier0 input buffer tasks. To increase the performance per disk server, write and read actions on the same disk server are separated. To find the optimal moments for a disk server to change from accepting and writing items to supplying items to other tasks, the combination of various parameters, such as the usage of a particular queuing discipline (like FIFO, LIFO, LPTF and SPTF) and the state of the disk server has been studied. The simulations have been performed with the Yasper simulation tool. This tool uses Petri Net models as its input. The purpose of the seminar is to generate and discuss ideas with the audiance.

In this reading seminar we present Chapter 6 of the book by Andreas Kyprianou. This chapter gives an account of the theory of excursions of a Lévy process from its maximum and the Wiener-Hopf factorisation that follows as a consequence from it.

We consider a life insurance company selling life insurances. New policies are sold at random points in time, and each policy stays active for a random amount of time, during which it pays continuously premiums at constant rate. After the policy expires, the insurance company pays a claim. The aim is to compute the infinite-horizon ruin probability. We establish the remarkable result that, if the lifetime of policies is exponential, then the ruin probability is identical to the one of the standard compound Poisson model where the fund increases at constant rate and claims occur according to a Poisson process. This implies that the ruin probability does not dependent on the initial number of active policies, nor on the arrival process of new policies.

Ananth Krishnamurthy (Rensselaer Polytechnic Institute, Troy, NY), June 11, 2007

Recent progress and Trends in Stochastic Models for Manufacturing Systems with Product Variety

This presentation focuses on some recent developments in stochastic models for manufacturing systems with product variety. The talk will briefly cover three topics.
The first part of the talk focuses on fabrication/assembly systems with kitting operations. The kitting operation is modeled as a fork/join station with multiple inputs having general characteristics.
Approximation techniques are used to analyze this station in isolation.
These approximations are subsequently used in a decomposition based approach to analyze fabrication/assembly systems where component fabrication occurs in a fabrication line with multiple stations. The second part of the talk focuses on manufacturing systems operating under pull control policies such as kanban and CONWIP. The system is modeled as a closed queuing network with fork/join stations. Exact analysis of these networks is hard under general settings, and therefore new approximations methods based on decomposition techniques are developed based on renewal approximations of underlying traffic processes. Using new approximations for mean waiting times at a station, iterative algorithms are developed to estimate performance measures. The third part of the talk focuses on a new class of specialized queuing network models based on the dynamics of Autonomous Vehicle Based Storage and Retrieval Systems (AVS/R systems). In traditional crane-based Storage/Retrieval systems, aisle captive cranes move unit loads simultaneously in the horizontal and vertical dimensions while interfacing with end-of-aisle accumulation systems, (usually conveyors).
AVS/R systems utilize sequential vehicle movement in two horizontal dimensions along a guide rail, (rectilinear travel), that allows vehicles to access any location on the same vertical level within the storage rack. Vertical movement is performed by lifts installed along the rack periphery. Queuing models are proposed to predict the impact of storage rack configuration and operational policies including S/R device dwell point rules, lift seizure and S/R device blocking protocols, storage policy, load batching, buffering and transaction dispatching rules on performance measures such as transaction cycle times, lift and vehicle utilizations.

Biography: Ananth Krishnamurthy is an Assistant Professor in the Department of Decision Sciences and Engineering Systems at Rensselaer Polytechnic Institute, Troy, NY. He obtained his PhD in Industrial Engineering from the University of Wisconsin-Madison in 2002. He also has a Masters degree in Manufacturing Systems Engineering from University of Wisconsin-Madison, and a Bachelors degree in Mechanical Engineering from the Indian Institute of Technology, India. His research targets the development and state-of-the-art application of performance modeling techniques in the design and analysis of manufacturing systems.
His research focuses on topics design and application of production and assembly systems, material handling and warehouse systems for manufacturing environments operating in a high product variety, custom production environment. He special interest lie in theories and principles related to lead time reduction and quick response manufacturing. His research is supported by federal agencies as well as industry.

Bert Zwart (The H. Milton Stewart School of Industrial and Systems Engineering at the Georgia Institute of Technology, Atlanta, USA), June 7, 2007

An extension of the square root law of TCP

Using probabilistic scaling methods, we extend the square root law of TCP to congestion avoidance schemes which may not be of the AIMD (Additive Increase Multiplicative Decrease) type. Our results offer insight in the relationship between throughput and loss rate, and the time scale on which losses take place. Similar results are shown to hold in scenarios where dependencies between losses occur.

From a mathematical perspective, we consider an appropriately scaled sequence of Markov processes each modeling the evolution of a single TCP connection. We show that this sequence converges to a limiting Piecewise Deterministic Markov Process, of which we analyze some properties, like the invariant distribution.
We also show that the invariant distributions of the sequence of Markov processes converges to the invariant distribution of the limiting Markov process.

This is joint work with Krishanu Maulik. A preprint can be found on his webpage: http://www.isical.ac.in/~krishanu/techrep/tcp.pdf

Bernd Heidergott (Faculty of Economics and Business Administration , Vrije Universiteit Amsterdam), June 1, 8, 22, 2007

This series of lectures is concerned with max-plus algebra from a queueing point of view.

Lecture 1 provides an introduction to max-plus algebra. The basic algebraic concepts are introduced and properties of max-plus algebra are discussed. The so called `heap of pieces' model is introduced and key issues in studying max-plus models are discussed.

Lecture 2 is devoted to queueing networks. Several examples will be discussed. An emphasis will be on modeling of waiting times (read: vector valued Lindely recursions). In the second part of the lecture, subadditive ergodic theory for max-plus models will be discussed.

In Lecture 3 we give a self contained proof of the celebrated result that any open max-plus linear queueing network with traffic intensity less than one admits stationary waiting times.

Lecture 4 will illustrate the link between graph theoretical concepts and ergodic theory of queueing systems. As will be explained in the lecture, max-plus techniques allow to identify sub-networks and to analyze the way in which these sub-networks determine the speed of the networks.

Evsey Morozov (Institute of Applied Mathematical Research and Petrozavodsk University, Russia), May 7, 2007

Stability analysis of a multiserver system with a dependence between workload, input and service time

Including various dependencies in a queueing model to reflect real-life effects, makes it more realistic. Our study concerns a general multiserver queue allowing dependence of the service time of an arriving customer and next interarrival period on both the current waiting time and the server assigned to the arriving customer. There are essentially no assumptions on the (conditional) distributions describing the model. We combine the Markov property of the workload process (to describe dependencies in the framework of Lindley-type recursion) with the regenerative property of that process to study stability using a characterization of the limit behaviour of the renewal process of regenerations. For this system, we establish sufficient stability conditions which are close to being necessary.

Wiener-Hopf techniques for the analysis of the time-dependent behavior of queues

The time-dependent behavior of queuing systems is considered to be a difficult problem. In contrast to the steady of the steady-state behavior, papers on the time-dependent behavior are very rare. But in many practical situations, for example in communication networks, the steady-state is not reached so that we have to investigate the time-dependent behavior in order to determine any control procedure.

We consider two conventional queuing systems and two fluid flow models. We are interested in time-dependent distributions of (actual/virtual) waiting time, number of customers, queue length (for conventional queuing systems) and the time-dependent distribution of buffer content (for fluid flows). To obtain the time-dependent distribution of interests, we derive a system of transformed Wiener-Hopf integral equations, which is solved by Wiener-Hopf factorization and subsequent decomposition. This factorization and decomposition will give us explicit expressions for the transforms of the time-dependent distributions. A numerical inversion is then applied to obtain the distributions. Some examples of results will be given at the end of talk.

In this seminar we consider Chapter 3 of Kyprianou’s book and discuss some more distributional and path-related properties of general Lévy processes, namely, the Strong Markov property, duality, moments, and exponential change of measure. The Lévy processes are now assumed to be defined on a filtered probability spaces.

Over the last years, ruin-related quantities of the collective risk process have been studied for various generalizations of the classical Cramer-Lundberg model. In this talk, some recent developments with respect to considering dividend payments to shareholders will be considered. Furthermore, it will be shown in what way tax payments can affect the probability of ruin for the insurance portfolio. For both extensions, some optimality issues will be discussed.

The book is devoted to studies of quasi-stationary phenomena in nonlinearly perturbed stochastic systems. The core of this phenomenon is that one can observe something that resembles a stationary behaviour of the system before its lifetime goes to the end. Examples of stochastic systems, in which quasi-stationary phenomena can be observed, are various queuing systems and reliability models, in which the lifetime is usually considered to be the time in which some kind of a fatal failure occurs in the system.

Population dynamics or epidemic models supply another class of examples of such stochastic systems. In population dynamics models, the lifetimes are usually the extinction times for the corresponding populations.

In epidemic models, the role of the lifetime is played by the time of extinction of the epidemic in the population. A ruin for risk processes can be also considered as an example of such phenomenon. An important characteristic feature of these models is a non-linear character of perturbation that essentially complicates the asymptotic analysis of quasi-stationary phenomena. The methods developed in the book are based on the exponential asymptotic expansions for nonlinearly perturbed renewal equations. Mixed ergodic and large deviation theorems are given for nonlinearly perturbed regenerative processes, semi-Markov processes, and Markov chains.

Applications to nonlinearly perturbed population dynamics and epidemic models, queuing systems and risk processes are considered. The book contains an extended bibliography of works in the area.

In this talk I will consider Levy processes reflected at zero. I will show how the classical Pollaczek-Khinchine formula can be extended from compound-Poisson input to Levy input. A useful lemma in this derivation concerns the transform of a reflected Levy process after an exponential time, for a given initial condition. For the special case of M/G/1 input a more direct approach can be followed.

The same lemma enables us to get a handle on Markov-modulated reflected Levy processes. I'll show what the structure of the workload transform looks like. Time permitting. I'll end with some thoughts on the special case of Markov modulated fluid.

Hansjoerg Albrecher (Graz Universität of Technology, Austria), January 31, 2007

Ruin theory in the presence of dividend and tax payments

Erlang's fixed-point approximation (EFPA) has been used for more than forty years to estimate blocking probabilities in large loss networks. For overflow loss networks (e.g. least-loaded routing in telephony networks), the accuracy of EFPA can often be remarkably poor. This is because the assumption inherent to EFPA that arrivals to each server group are independent and random is usually violated to a greater extent if overflow is permitted. In this talk, I highlight some of the work over the last forty years that has been used to enhance the accuracy of EFPA. I then demonstrate that EFPA with all the latest bells and whistles (e.g. higher moment matching, sub-network decomposition) may still perform poorly for some of the most simple types of overflow loss networks. The main purpose of my talk is to discuss a new approximation that I show offers higher accuracy than EFPA for several cases. The new approximation is simple: Given a system for which an estimate of blocking probability is sought, we first construct a second system to act as a surrogate for the original system. Estimating blocking probability in the second system with EFPA provides a better estimate for blocking probability in the original system than if we were to use the conventional approach of directly using EFPA in the original system. The second system is constructed simply by imposing preemptive priorities in the original system. I discuss the rationale underpinning the new approximation and argue that its success is due to its ability to utilise congestion information imbedded in overflow traffic, whereas the conventional EFPA approach fails to utilise such information.

Topic of today's seminar is the introductory chapter "Levy Processes and Applications" of Kyprianou's book. In particular, the relation between Levy processes and infinite divisible distributions is discussed. Furthermore, several examples of Levy processes are given, like gamma processes, inverse Gaussian processes and stable processes.
Finally, a number of applied probability models related to Levy processes will be introduced: the Cramer Lundberg risk process, the M/G/1 queue, optimal stopping problems and continuous-state branching processes. These applied probability models will be treated in detail in later chapters of the book.

Budhi Arta Surya (Universiteit Utrecht), January 18, 2007
Joint work with Andreas Kyprianou

We revisit the previous work of Leland [J Finance 49:1213–1252, 1994], Leland and Toft [J Finance 51:987–1019, 1996] and Hilberink and Rogers [Finance Stoch 6:237–263, 2002] on optimal capital structure and show that the issue of determining an optimal endogenous bankruptcy level can be dealt with analytically and numerically when the underlying source of randomness is replaced by that of a general spectrally negative Lévy process. By working with the latter class of processes we bring to light a new phenomenon, namely that, depending on the nature of the small jumps, the optimal bankruptcy level may be determined by a principle of continuous fit as opposed to the usual smooth fit. Moreover, we are able to prove the optimality of the bankruptcy level according to the appropriate choice of fit.

I will be discussing several ongoing research projects that I started this past year. I will begin by presenting the first analysis of the Join-the-Shortest-Queue task assignment policy for Web server farms. Web server farms involve Processor-Sharing servers. This work introduces a new technique: Single-Queue-Approximation (SQA), and uses the technique to prove some interesting insensitivity properties for Web server farms. This work is joint with Varun Gupta, Karl Sigman, and Ward Whitt. Next, I will turn to the problem of analyzing limited resource sharing systems. An example of a limited resource sharing system is the Processor-Sharing queue with a multi-programming limit, where jobs beyond this limit wait in an external FCFS queue. I will present preliminary results on the first approximate analysis of such systems. This work is joint with Jim Dai, Varun Gupta, and Bert Zwart.

BIO: Mor Harchol-Balter is an Associate Professor of Computer Science at Carnegie Mellon University. She received her doctorate from the Computer Science department at the University of California at Berkeley under the direction of Manuel Blum. She is a recipient of the McCandless Chair, the NSF CAREER award, the NSF Postdoctoral Fellowship in the Mathematical Sciences, multiple best paper awards, and several teaching awards, including the Herbert A. Simon Award for Teaching Excellence. She currently serves as Treasurer of the SIGMETRICS board, and as Program Chair for ACM SIGMETRICS 2007 and for QEST 2007.
Professor Harchol-Balter is heavily involved in the ACM SIGMETRICS research community. Her work focuses on designing new scheduling/resource allocation policies for various distributed computer systems including Web servers, distributed supercomputing servers, networks of workstations, and database systems. Her work involves inventing new queueing analysis, as well as systems implementation, and emphasizes integrating measured workload distributions into the problem solution.

Stability of some random multiple-access protocols with spatial interactions.

We adopt the classical ALOHA scheme to the case when the users in a multiple-access system have local interactions given by some neighbourhood relations. We prove that the fluid limits of the system's workload satisfy a certain differential equation and, via an analysis of this differential equation, obtain conditions sufficient for the system to be stable. We also discuss the behaviour of the fluid limits. This is a joint work with Charles Bordenave and Serguei Foss

Johan van Leeuwaarden (Technical University of Eindhoven), November 28, 2006
Joint work with A.J.E.M. Janssen (Philips Research) and B. Zwart (Georgia Tech)

We consider the M/D/s queue and keep track of the number of customers waiting in the queue (without those in service) at the end of consecutive intervals of lengths equal to the constant service time. Customers arrive according to a Poisson process and can be served by either one of the s servers. In the Halfin-Whitt regime, the normalized queue length distribution converges to that of the maximum of the Gaussian random walk with negative drift.

The limiting procedure applied in the Halfin-Whitt regime is based on the central limit theorem, and the limit is easily established. This is not, however, really satisfactory, since it does not tell us how fast the convergence takes place. The limiting result alone essentially gives no real information on any of the finite-sized queueing models. More satisfactory would be to have asymptotic estimates or even inequalities from which we could judge just how close the scaled queueing model is to its heavy-traffic limit. Also, the way in which the convergence takes place would be valuable information.

We view the M/D/s queue in Halfin-Whitt regime through the prism of the Gaussian random walk, for which we derive Gaussian-type expressions for characteristics of the M/D/s queue (probability of an empty queue, mean and variance of the queue length). We build upon work of Chang & Peres (1997) and Jelenkovic, Mandelbaum & Momcilovic (2004).

In the first part of this talk I will consider Asymptotic Bounds for a Geometric Sum with Subexponential Summands. The asymptotic form of the tail distribution of a geometric sum is easy to obtain, but the relative accuracy of the asymptotic form is, in general, very poor for practical applications. Work by Kalashnikov and Tsitsiashvili provided bounds for this relative accuracy. We present their results in a more probabilistic light, and provide a specific example which shows how to improve on the tightness of their result.

In the second part I will consider some results on the Sums of Long-Tailed Random Variables that have a Conditional Independence Structure. There is a general basket of results that apply to sums of subexponential independent random variables. This has been extended to the class S*, to local subexponential distributions and to long-tails and to heavy-tails. We wish to extend this further to allow dependence of the random variables in such a way that the main results of the theory are preserved. We choose the random variables to be independent conditional on some sigma-algebra, and try to construct sufficient conditions to ensure that properties concerning conditional convolutions, finite and light-tailed sums of conditionally dependent random variables, and results concerning the supremum of a random walk with dependent summands are all preserved. This is work in progress jointly with Professor Serguei Foss.

November 21, 2006, Introductory mini-course "Levy processes in finance" by Wim Schoutens (Katholieke Universiteit Leuven), November 21, 2006

Production systems are the base for building and improving the economic strength of a country. Modern production systems are organized as supply chain networks. Supply chain are complex systems: lead-time delays, production capacity and raw materials constraints, failure and market demand uncertainty, and feedback flow of information and materials make the task of the supply chain manager a challenge. The purpose of this work is to support the decision process and to exploit the information carried by the real-world data (market demand, production failures, ...). Our approach is composed by four main block. The first one aims to model the dynamics and the source of uncertainty of the supply chain, using difference equations and markov modulated model. The second block use large-deviations techniques to relate steady-state performance of the supply chain with key design parameters. The third block introduce model predictive control and robust optimization to achieve sub-optimal and robust performance at the low-level control. The last block distribute the control system through the supply chain using approximate dynamic programming and actor-critic techniques enhancing cooperation between all the facilities of the supply chain. Keywords: Supply Chain Modeling, Model Predictive Control, Large Deviations, Actor-Critic, Robust Optimization, Multi-Agent Consensus.

Using the generator of a Markov process to obtain information about various properties of the process is not a new idea. However, it seems to be helpful to recall the methods and to show that in some cases the generator approach is neither cumbersome nor technical. The appropriate class of stochastic processes to demonstrate this is formed by the class of Piecewise Deterministic Markov Processes (PDMP) which covers a wide range of processes appearing in applied probability. We give an introduction to these processes, how to determine the generator and how to use it, focusing on some examples from queueing theory. Finally we mention some general martingales for a two dimensional PDMP including some already well known martingales as particular cases.

Till Daniel, Frank, (Institute for Theoretical Physics, University of Münster, Germany), October 23, 2006

In many disciplines such as physics, engineering sciences and life sciences random walks have been successfully described as Markov diffusion processes using the well-established theory of Fokker-Planck equations. However, Markov diffusion processes cannot account for mean field forces and memory effects that play important roles in many-body systems and systems exhibiting time-delayed feedback loops. In the lecture it will be shown how mean field forces and memory effects can be taken into account by generalizing the theory of Fokker-Planck equations. To this end, random walks will be described by means of nonlinear Fokker-Planck equations and delay Fokker-Planck equations.
Bifurcations such as order-disorder transitions, delay-induced (Hopf) bifurcations, and re-entrant bifurcations will be addressed. Transient solutions and second-order statistics will be discussed. Fundamental concepts will be illustrated by examples and benchmark models.

It is well-known that many fundamental relationships in queueing theory can be derived with the use of Palm measures induced by stationary systems. In this talk, we will discuss how many of these relationships carry over to the non-stationary setting. We will show that the stochastic intensity of a point process is still linked to the family of Palm measures in the non-stationary setting, which generalizes the results of Papangelou and Bremaud. This result is used to generate necessary and sufficient conditions for a transient version of the "ASTA" property to hold. We'll also show how Palm theory can be used to derive equations that relate queue lengths and waiting times, that are similar to the transient Little laws discussed in Bertsimas and Mourtzinou. Other results will be discussed as time permits.

Nicolae Popescu (University of Bucharest), October 9, 2006

Probability Models in Finance

"My master thesis has two chapters. The first chapter is about models in discrete time. We prove two main theorems about financial markets. The first theorem deals with viability of a financial market while the second one gives conditions for a viable market to be complete. The second chapter, using tools from stochastic calculus, we determine the solution of the equation that describes the prices in the Black-Scholes continuous-time model.

Dirk P. Kroese (University of Queensland, Australia), October 2, 2006
Joint work with Reuven Y. Rubinstein.

Solving Difficult Optimisation and Counting Problems via the Cross-Entropy Method

In talk we show how the Cross-Entropy method can be used to solve difficult combinatorial optimisation and counting problems. Examples of the former are the maxcut, travelling salesman problem and satisfiability problem; examples of the latter are problems such as counting the total number of Hamiltonian cycles, colourings and spanning trees in a graph, determining the permanent of a matrix, and computing the number of self-avoiding random walks of a certain length. For such #P-complete problems, very few generic deterministic or randomised methods are available. We demonstrate that CE method provides an important advancement in these type of problems.

The growing trend in computer systems towards using scheduling policies that prioritize jobs with small service requirements has resulted in a new focus on the fairness of such policies. In particular, researchers have been interested in whether biasing towards small job sizes results in large jobs being treated "unfairly." However, unfairness is an amorphous concept and thus difficult to define and study. In this talk, I will present some recent attempts to define and study the concept of fairness in single server queueing settings. Rather than providing the unique, correct definition of fairness for queues, my goal in this talk is to illustrate, compare, and contrast, the range of fairness measures that have been suggested and to summarize what interesting open questions remain for each.

Group Testing Models With Incomplete Identication and their Applications in Medical and Industrial Problems

In this talk we review an ongoing research project on group testing models by Wolfgang Stadje, Frank Van Der Duyn Schouten and Shaul K. Bar-Lev and others. This project has already yielded six papers:
1. "Hypergeometric group testing with incomplete information" (2003). 2. Optimal roup testing models with processing times and incomplete identication(2004); 3. Multinomial group testing models with incomplete identication. (2005); 4. Group testing procedures with incomplete identication and unreliable results"(2006); 5. "Applications of bulk queues to group testing models with incomplete identication" (submitted); 6. "Aging and window period in group testing models" (in preparation).
More specially, we study several group testing models. The objective is to choose an optimal group size for pooled screening of a contaminated population so as to collect a prespecied number of good items from it with minimum testing expenditures. The tested groups that are found contaminated are either discarded or are used as new sampling population in later stages of the procedures. Since testing may be time-consuming, we also consider deadlines to be met for the testing process. We derive algorithms and exact results for the underlying distributions of the appropriate stopping times, enabling us to nd optimal procedures. We shall briefly review various aspects of group testing procedures such as multinomial group testing; unreliable results (false-positive and false-negative), window periods and expiration dates. The talk will not be of mathematical nature but rather a brief "state of art" on the subject.

Lerzan Ormeci (Koç Üniversitesi, Istanbul, Turkey), August 30, 2006
Joint work with Fikri Karaesmen and Eren Cil, both from Koc University

Effects of System Parameters on the Optimal Policy Structure in a Class of Queueing Control Problems

We consider a class of queueing control problems involving commonly used control mechanisms such as admission control, pricing, and service rate control. Such controls are frequently employed in modeling service systems, telecommunications, and also in inventory systems modeled as make-to-stock queues. It is by now well established that in a number of such important problems, the optimal policy is structured and is described by a few parameters. From a design point of view, it is useful to understand how the optimal policy changes when the system parameters such as arrival or service rates, or the number of servers vary. We present a general framework to investigate the policy implications of the system parameters by using event-based dynamic programming. In this framework, the value function of the control problem is first represented by a number of common operators, and the effect of system parameters on the optimal policy is analyzed for each individual operator. We first illustrate the framework through a dynamic pricing control problem, and then present the analysis for a set of frequently used operators. Whenever a queueing control problem can be modeled by these operators, the effects of system parameters on the optimal policy follows trivially from this analysis. This enables us to easily retrieve and generalize some of the existing results in the literature.

We consider real-valued piecewise deterministic Markov processes and try to analyze them via their extended infinitesimal generator. Using appropriate martingales the expectation, further moments, the Laplace transform and stationarity conditions can be found. Some special cases and further extensions are presented.

On The joint distribution of the queue length and the residual service time in the Mn/G/1 queue

We consider an M/G/1 queue which the number of customers in the system is observed by customers upon their arrivals. Based of the number of customers in the system, an arriving customer decides whether joining the queue or not, while a mixture between these two option is allowed. We assume homogeneous customers who join the system with probability which depends in the number of customers in the system. For any set of such probabilities, we develop a closed recursive formula for the conditional distribution of the waiting time, given the number of customer in the system. These conditional distribution are the solution of a set of linear differential equation. We also provide a simple recursive formula for the Laplace-Stiltijs Transform for the above mentioned conditional distribution. We conclude by presenting a cost/reward model and describing the equations which their solution is the Nash equilibrium probabilities

Nikolay Likhanov (Institute for information transmission problems, Moscow), June 13, 2006

We consider the system of N separated queues with constant service bit rate. As an input traffic we consider the packets of bits which arrived to the system according to the Poisson point process. When packet arrived to the system it can takes randomly K queues (K<N) and will goes for service to the queue with minimal workload. We assume that sizes of the packets are independent random variables distributed by power low. Large buffer asymptotic expressions for overflow probability are derived.

Importance sampling (which is a variance reduction technique for stochastic simulation) has become a standard tool in estimating probabilities of rare-events. Recently, in work by Chen, Diaconis, Holmes and Liu (2005), this technique was also applied to approximate counting problems (the number of binary contingency tables). Although empirical evidence suggests that importance sampling may be a suitable technique for approximate counting, the theoretical support to substantiate this evidence is very limited.

We shall discuss a new technique, based on Lyapunov bounds for Markov chains, that can be used to analyze the computational complexity of state-dependent importance sampling algorithms (for rare-events and counting). As an application, we analyze the computational complexity of Chen et al (2005)'s counting algorithm in the context of large and sparse binary contingency tables. We will also illustrate this technique in the context of rare-event simulation. In particular, we shall present an algorithm (joint work with Peter Glynn) that can be proved to be efficient (in a suitable sense) for estimating the tail of the maximum of a general random walk -- which has important implications in queueing and insurance. This is the first algorithm that is known to be probably efficient for the maximum of random walks with general heavy-tailed distributions (we only require subexponentiality of the right tail and the corresponding integrated tail).

We study exact asymptotics for the distribution of the first time a Levy process or a random walk starting from a positive level becomes negative. We apply these results to find asymptotics for the distribution of the busy period in an M/G/1 queue. This is a joint work with D. Denisov.

Yiqiang Q. Zhao (Professor and Director School of Mathematics and Statistics Carleton University, USA), April 11, 2006

Geometric Decay in a Generalized Join Shortest Queue Model Matrix-Analytic Method for a Non-Positive Recurrent Case

Several methods have been proposed in analyzing tail asymptotics for two-dimensional models, among which the matrix-analytic method looks relatively easier to use. However, it has bee only applied to positive recurrent cases. In this talk, I will demonstrate by using a generalized join shortest queue model how the matrix-analytic method can be also used to study geometric tail asymptotics in the joint stationary distribution in the case of non-positive recurrence. This talk is based on my joint work with Hui Li and Masakiyo Miyazawa.

Andrei Sleptchenko (Erasmus University Rotterdam), March 21, 2006
Joint work with M. Eric Johnson, Dartmouth College

We consider a network of devices that are subject to traditional failures that can lead to a system failure if not repaired. However, the devices are also subject to a sort of suspected failures that might not influence the system performance directly but still have to taken into account. We develop an LP based optimization model to assign repair priorities depending on system states and we show that, the optimal repair policy follows a unique threshold indicator (either work on the real failures or the suspected ones). We examine the behavior of the optimal policy under different settings.

Moshe Haviv (Hebrew University of Jerusalem), February 21, 2006
Joint with Tim Roughgarden, Stanford University

We consider a single multi-server memoryless service station. Servers have heterogeneous service rates. Arrivals are routed to one of the servers. The routing decisions are not based on the queue lengths. There are two criteria for routing selection. The first is the (Nash) equilibrium, under which each customer minimizes his own mean waiting time, given the behavior of the others. The second is social optimization, where the routing is designed to minimize the average mean waiting time across all arrivals. The ratio between the social costs in both cases is called the price of anarchy (PoA). We show that the PoA is bounded from above by the number of servers utilized under the socially optimal behaviour. In particular, it is bounded by the number of available servers. Moreover, this bound is tight.

The scale-problem in rain-rate time series has motivated a number of studies about the relationships between intensity, duration and frequency since the beginning of XX century. It has been observed that some empirical curves are traditionally modelled for rare events using power laws that are compatible with multifractal scalings. Certainly, it is true that most of these studies are based rather on empirical evidence than on statistical theory, but the mathematical theory to deal with this type of statistical problems is of recent development and not trivial. We discuss about mathematical relationships between IDF curves and random multiplicative cascades, and their relevance for statistics of extremes.

Limiting Performance of Ad Hoc Networks with Topology-Transparent Scheduling Schemes

In this work we investigate the limiting properties, in terms of capacity and delay, of an ad hoc network employing a topology-transparent scheduling scheme. In particular, we focus on Time-Spread Multiple Access (TSMA) protocols, which are able to offer a deterministic upper bound on the access delay. The analysis is based on some asymptotic (focusing) properties of geometric random graphs. The analytical framework is applied to both static and mobile networks. The obtained results are compared with the results present in the literature for the case of an optimum (centralized) scheduling scheme.

From technology to nature and back: BIONETS, BIONETICS and beyond

The recent advances achieved in the last decades in many technological fields (e.g., computing and communications) has led to a huge improvement in our understanding of natural phenomena. Genome sequencing is probably the most amazing example of what technology can do when applied to nature. The reverse approach (from nature to technology) has not, in general, received considerable attention. This can be done by the fact that, historically, technology has been put in place by humans to control, in a well predefined way, the "chaos" of nature and turn it into a purposeful system. Nowadays, we are reaching a stage in which technological systems (e.g., OSs in computing and the Internet in communication) show a level of complexity similar to that of biological organisms. We present the BIONETS project as an example of the application of bio-inspired paradigms to the engineering of autonomic networks, its multi-disciplinary evolution into BIONETICS and some futuristic research lines in the area.

We consider a reflected Levy process with no negative jumps which is required to be above a positive constant multiple of the age process (time since the last event) of some Poisson process. Applying some Martingale theory we compute the Laplace-Stieltjes transform of its stationary distribution which has a product form. In particular it is distributed like the infinite sum of independent random variables, one of which is the stationary distribution of the Levy process reflected at the origin.

Locality of Reference and the Use of Sojourn Time Variance for Measuring Queue Unfairness

The variance of job sojourn time (or waiexists. In this work we demonstrate that this quantity has a disadvantage as an unfairness metric, since it is not local tting time) is used, either explicitly or implicitly, as an indication of unfairness perhaps for as long as queueing theory o the busy period in which it is measured. It therefore may account for job discrepancies which are not relevant to unfairness of scheduling. We show that RAQFM, a recently proposed job fairness metric, does possess such a locality property. We further show that within a large class of unfairness metrics RAQFM is unique in possessing this property. We also show that RAQFM has other desired properties which make it a good candidate for a queue fairness measure.

We describe two data network models where descriptor variables can have very heavy tails. The first is the infinite source Poisson (or M/G/$\infty$ input) model where we assume sessions are initiated at Poisson times and session lengths have an infinite mean heavy tail distribution. We comment on growth rates, self-similar approximations and buffer content. For the 2nd model, we study sessions initiated at renewal times and both the session lengths and inter-renewal times may have heavy tails. We study the activity rate process; that is, the number of active sessions at a given time t as well as cumulative input.

Network data traffic reveals strong correlations in its statistical structure. This feature can be nicely captured by ON-OFF and M/G/∞ processes that, in case of heavy-tailed distributions for the activity times, turn to be long range dependent. We discuss the limiting processes that appear as output of a single queueing system fed by such processes as the intensity rate grows to infinity. Finally we extend this result to a fluid queueing network by looking at the condition under which the limiting processes are linear combinations of fractional Brownian motions or Lévy motions.

Analysis of a Simple Markovian Re-Entrant Line with Infinite Supply of Work under the LBFS Policy

We consider a two machine 3 step re-entrant line, with an infinite supply of work. The service discipline is last buffer first served. Processing times are independent exponentially distributed. We analyze this system, obtaining steady state behavior and sample path properties.

Validity of Steady-state Heavy Traffic Approximations in Generalized Jackson Network
Joint work with Assaf Zeevi (Columbia University)

(Generalized) Jackson network is one of the oldest queueing network models. The closed form type solution to this model is not achievable in general, modulo some specific Markovian type cases. As a result, the researchers focused on asymptotic approaches, and here the diffusion approximation plays a very prominent role. In particular, a classical theorem by Reiman asserts that a sequence of normalized queue length processes converges weakly to an associated Reflected Brownian Motion (RBM), as the network approaches the heavy traffic regime. However, the result corresponds only to the transient behavior, and it was not known whether the stationary distribution of the RBM provides a valid approximation of the underlying GJN in steady-state. We resolve this open problem, thus validating a so-called ``interchange-of-limits'' for this class of networks. The result has several useful implications. In particular, in some cases, the asymptotic steady state distribution of queue lengths and waiting times can be computed in closed form.

Stochastic networks with unreliable components
The talk presents joint work with Cornelia Sauer (Hamburg University)

We reconsider the classical Jackson and BCMP networks and remove the requirement that the servers in the network are always able to work when customers are present. We describe degradable network models where breakdowns of servers occur and their repair has to be performed. Breakdowns and repairs occur in different ways: Concurrently in groups or single nodes, the intensities of their occurrence may be state dependent.

We apply different rules to handle the customers' routing connected with nodes in repair status. These rules originate from communication and or production theory where they are used to resolve blocking situations.

The up and down times of the stations may be nonexponental and additionally influenced by the global state of the network. This allows to consider versatile working period and repair time distributions.

Our main result is a product form theorem for the joint steady state distribution of the combined queue length and reliability status of the network.

In recent studies it has been shown that the throughput of a TCP connection is strongly related to the random variable $Z = \int_0^\infty \exp{-X(t)} dt$, with $X(t)$ a compound Poisson process. In the financial mathematics literature, such random variables are called perpetuities, and also appear in the pricing of Asian options. Another applications is the limiting distribution of the pick time in a carousel system under the nearest item heuristic (see the thesis of Nelly Litvak)

This talk focuses on the TCP application, and also presents new results on the distribution of $Z$. In particular, we give an expression for the Mellin transform of $Z$, and the tail asymptotics of $Z$.

References: F. Guillemin, Ph. Robert, B. Zwart. AIMD algorithms and exponential functionals. Annals of Applied Probability 14 (2004), no. 1, 90--117. K. Maulik, B. Zwart. Tail asymptotics for exponential functionals of Levy processes. Eurandom report 2004-036.

Armand M. Makowski (University of Maryland), February 23, 2005
Joint work with Sarut Vanichpun.

Locality of reference in streams of requests: Modeling temporal correlations via stochastic orderings

The performance of demand-driven caching depends on the locality of reference exhibited by the stream of requests made to the cache. In spite of numerous efforts, no consensus has been reached on how to formally compare streams of requests on the basis of their locality of reference. We take on this issue by introducing the notion of TC ordering for comparing strength of temporal correlations in streams of requests. This notion is based on the supermodular ordering, a concept of positive dependence which has been successfully used for comparing dependence structures in sequences of rvs. We explore how the TC ordering captures the strength of temporal correlations in several Web request models, namely, the higher-order Markov Chain model (HOMM), the partial Markov Chain model (PMM) and the LRU Stack Model.

Armand M. Makowski (University of Maryland), February 22, 2005
Joint work with Sarut Vanichpun.

The output of a cache under the independent reference model -- Where did the locality of reference go?

We consider a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). We characterize the popularity pmf of the stream of misses from the cache, the so-called output of the cache, for a large class of cache replacement policies, including standard on-demand replacement algorithms such as the policy A_0 and the random policy, as well as the LRU policy. We measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution. Using the notion of majorization to capture the degree of skewness, we show that for the policy A_0 and the random policy, the output always has less locality of reference than the input. However, we show by counterexamples that this is not always the case under the LRU policy when the input is selected according to a Zipf-like pmf. In that case, conjectures are offered (and supported by simulations) as to when LRU caching indeed reduces locality of reference.

Wireless scheduling plays an important role in the design of next generation wireless networks as it determines the QoS provisioning over the wireless link. Compared to its wired counterpart, the design of wireless schedulers is a harder and more challenging problem due to the unique characteristics of the wireless channel. While recent work focused on the design of wireless schedulers to meet specific performance objectives, our research aims to characterize the QoS performance of a generic wireless scheduler in a downlink centralized scheduling scenario, assuming a Markov-based wireless channel. We present our approach to achieve the above objective, and demonstrate the trade-off amongst QoS metrics, wireless scheduler and receiver design in various scheduling scenarios using numerical results.

In this talk we present the study of the limit processes for the internal flows of a network of fluid queues. The analysis starts form the study of the limit for the output flow of a single fluid queue having as input either an M/G/? process or the superposition of ON-OFF processes. The limit is carried out by increasing the input arrival rate to infinity by retaining constant the traffic intensity. The analysis is then extended to networks and the conditions for the convergence to linear combination of FBM or Lévy motions are derived.

A large number of applied probabilists often get nervous when the famous names of Wiener and Hopf are used in a single sentence. The Wiener-Hopf factorization is sometimes even viewed as a mathematical curiosity of little practical value. This talk aims to give evidence to the contrary. I will use the concept of a censored Markov Chain to obtain a simple derivation of the Wiener-Hopf factorization in the lattice case. Then I explain how the results look in more general form. Particular aspects I would like to treat are
- Spitzers identity from probability
- The Plemelj-Sokhotsi formula from analysis; the "Pollaczek method"
- Kingman's algebraic point of view
- Multidimensional factorizations
- The connection with the matrix analytic method

Christian Gromoll (Stanford University), December 15, 2004
Joint work with Ruth Williams.

Fluid limit of a network with fair bandwidth sharing and general document size distributions

Roberts and Massoulie (1998) have introduced a model of Internet congestion control that represents the randomly varying number of flows in a network where bandwidth is dynamically shared among flows. Flows correspond to continuous transfers of individual documents through the network. Thus, the model assumes a "separation of time scales'' between flow level dynamics and packet level dynamics in the network; the time scale of document arrivals and departures (flow level) is much longer than the time scale on which rate control schemes such as TCP converge to equilibrium (packet level).

This work proposes a fluid model, or formal functional law of large numbers approximation, for the flow level model operating under a weighted alpha fair bandwidth sharing policy, introduced by Mo and Walrand (2000). This policy offers a generalization of the processor sharing discipline from a single resource to a network with several shared resources. In contrast to earlier work of Kelly and Williams (2003), the present fluid model allows general, rather than exponentially distributed, interarrival times and document sizes. To describe the evolution of the system, measure valued processes are used to keep track of the residual sizes of all documents in the system at any given time. Under mild conditions, the appropriately rescaled measure valued processes corresponding to a sequence of flow level models (with fixed network structure) are tight, and each weak limit point of the sequence is almost surely a fluid model solution.

Scalable TCP is a proposal to improve the performance of TCP over high speed networks. In contrast to the Additive Increase Multiplicative Decrease (AIMD) algorithm used in the standard versions of TCP, Scalable TCP uses a Multiplicative Increase Multiplicative Decrease (MIMD) congestion control algorithm. In the first part of this talk, we present a mathematical analysis of the MIMD congestion control algorithm in the presence of random losses. Our approach is based on relating the window size process to that of the workload process in a standard G/G/1 queue thus providing the throughput of the algorithm and the higher moments of the window size process. In the second part of this talk, we study fairness among sessions sharing a common bottleneck link. We first study how two MIMD sessions share the capacity in the presence of general combinations of synchronous and asynchronous losses. We show that, with rate dependent losses, the capacity is fairly shared whereas rate independent losses provide high unfairness. Finally, we look at inter-protocol fairness: how the capacity is shared among sessions some of which use the AIMD algorithm whereas others use the MIMD algorithm in the presence of synchronous losses.

Control of service rate in a network of queues is a well studied problem in the literature of queueing and communication theory. A wireless multiaccess is a communication system where many transmitters communicate with a single receiver over a shared channel. Thus a wireless multiaccess is equivalent to a network of parallel queues with one server whose capacity is shared among queues. In this talk, we present service rate (transmission rate) control algorithms designed to achieve certain performance objectives specific to the wireless multiaccess scenario. The main difference between the service rate control of a ``standard'' queueing network and the queueing network arising from a multiaccess is that the service rate available is time varying due to fading environment, the service cost is exponential in the service rate and the costs are non-additive.

Asymptotics for the tail distribution of the maximum of a Markov-modulated random walk with heavy-tailed increments.

We extend ([S1]) results of [FZ] in two important particular cases: when a reference distribution is either long-tailed with dominated variation or strongly concave. Our results are based on new estimates for the tail distributions of sums of random variables with distributions satisfying one of properties mentioned above. We also obtain ([S2]) local analogues of the latter estimates. [FZ] S. Foss, S. Zachary. "Asymptotics for the maximum of a modulated random walk with heavy-tailed increments". Analytic Methods in Applied Probability (in memory of Fridrich Karpelevich), Amer. Math. Soc. Transl., 207, No. 2, 37-52 (2002). [S1] V. Shneer. "Estimates for the distributions of sums of subexponential random variables", to appear in Siberian Mathematical Journal. [S2] V. Shneer. "Estimates for local probabilities of sums of independent random variables with heavy-tailed distributions", in progress.

José Niño-Mora (Department of Statistics, Universidad Carlos III de Madrid), November 16, 2004

We address the problem of designing a dynamic server scheduling policy for a Markovian multiclass queue with finite buffers, incurring linear holding costs and/or loss costs. Our goal is to design well-grounded and tractable scheduling policies which are close to optimal for discounted or average cost criteria. For each of several problem variations, we propose a new index policy, which dynamically prescribes to allocate servers to classes with larger index values. The approach and results follow from deployment of the general framework of marginal productivity indices and partial conservation laws for restless bandits, which we have introduced in a recent series of papers.

Consider a random walk with i.i.d. increments and assume that these increments are heavy-tailed. The exact asymptotics for the tail distribution of the supremum and for tha tail distribution of the maximum on the random time interval are known when is negative and finite. We revisit these theorems and give complementary results in the case .

We hope to discuss both relaxation times ("time to reach equilibrium") and queues with time-varying arrival rates, using material from, a.o., the following papers:

A two-priority fluid model: joint steady state distribution of the buffer content processes

We consider a single-node fluid-flow model with two classes of fluid that are served according to a strict priority service discipline under which the higher priority traffic always takes precedence over the lower priority traffic. The service rate is assumed to be constant and the input flows are generated by an irreducible finite state Continuous Time Markov Chain. We obtain exact analytic results for the steady-state joint buffer content of the two priority classes.

Our approach is based on an embedded analysis of the system which allows to gain insight of its structure by preserving the probability nature of the problem to a higher degree than an earlier spectral decomposition method (Bong Dae Choi and Ki Bong Choi, Telecommunication Sys, 79-95). This two-priority-model provides the necessary tools for obtaining the steady-state distribution of the lowest class of fluid in a system with K > 2 priorities by reducing it to a two-priority system with the higher priority class defined as the aggregate of the first K-1 priority classes of fluid. Another observation to make is that the two-priority fluid model is equivalent to the tandem fluid model.

In this talk we show the exact asymptotics of the busy period in a GI/G/1 queue. This asymptotics is applied to define the workload process conditioned to stay positive. Therefore in the first part of the talk it is reviewed a general theory of Markov processes never exiting a subspace A of the state space E or in another words, Markov processes conditioned to stay in the subspace A. It is shown how the knowledge of the exact asymptotics of the tail distribution of the exit time helps to identify the suitable exponential martingale, which in turn, serves for the change of measure. Under the new probability measure the process is the sought for never exiting one the subspace A. A detailed analysis is given for the workload in the M/G/1 FCFS queue conditioned to stay positive. We also find the exact asymptotics for the busy period in the GI/G/1 FCFS queue. Of course one must first markovize the workload process by the attaching the second component of the remaining arrival time process. We also study the quasi-stationary distribution of the workload processrticular, we give sufficient conditions for its existence.

A review of Perishable Inventory Systems (PIS) with Random Input and Random Output is introduced. The status of this ongoing research is as follows. Some works have already been published in the past, some have been submitted for publication last year, some are in process or under investigation and finally, some are still considered as open problems. The general approach is based on a certain analogy between the age of the oldest item in the PIS and the Attained Waiting Time process of a single server queue.

In this paper the integrated traffic control and traffic assignment problem is studied for a situation with two road authorities. The road authorities try to optimize their own objectives and the same is done by the road users. This leads to a tri-level optimization problem. Game theory gives a suitable framework to analyze the problem and to find solutions for different situations, e.g. no cooperation, cooperation between the two authorities and a system optimum where all actors cooperate to maximize the weighted benefits for all actors. In this paper two approaches are used: an analytical one and an approach based on a simulation and assignment framework. Both approaches are described and used to study a simple example, for which the results are given and discussed. The results show that that separate or integrated anticipatory control gives the better results than iterative adaptation of the optimization. If one road authority takes the lead and anticipates the reactions of both the road users and the other road authority a sub-optimum is reached. The model calculation gives evidence that cooperation of road administrators improves the utilization of the infrastructure and that a global optimization does not necessarily give a worse situation for one road administrator.

The performance of wireless data systems has been extensively studied in the context of a single base station. In the present paper we investigate the flow-level performance in networks with multiple base stations. We specifically examine the complex, dynamic interaction introduced by the strong impact of interference from neighboring base stations. We derive two types of lower and upper bounds for the number of active flows, transfer delays and flow throughputs in the various cells. While the first type of bounds are rather rough and simple to compute, the second type of bounds are sharper, but harder to calculate. In order to obtain closed-form estimates for the latter bounds, we introduce two limit regimes, termed fluid and quasi-stationary regime, where the system dynamics evolve on a very fast and a very slow time scale, respectively. Importantly, the performance in both limit regimes is insensitive, thus yielding simple, explicit estimates that render the detailed statistical characteristics of the system largely irrelevant. Numerical experiments show that the upper bounds evaluated in the quasi-stationary regime provide conservative and extremely tight approximations.

We consider the problem of designing dynamic server assignment policies that maximize the throughput of queueing networks with flexible servers. Flexibility here means that each server may be capable of performing service at several different classes in the network. The first half of the talk will be concerned with a tandem queueing system with finite buffers operating under manufacturing blocking. Under certain homogeneity conditions on the service rates, we show any non-idling policy yields maximum throughput. In the more general case, under exponential assumptions, we identify the optimal policy in a two class, two server system and find that it is of a particularly simple form. The second half of the talk examines the infinite buffer case with more general network structure. We assume that the interarrival times and the service times are independent and identically distributed, and that routing is probabilistic. We also allow for server switching times, which we assume to be independent and identically distributed. We deduce the value of a tight upper bound on the achievable throughput by equating the throughput of the queueing network model with that of a limiting deterministic fluid model. (Joint work with Sigrun Andradottir and Hayriye Ayhan at Georgia Tech.)

In this talk we study a two-station network with Poisson arrivals, exponential service times and Markovian routing. The total service capacity in the network is shared among the stations according to fixed proportions, except when one of the stations is empty. In that case the total service capacity in the network is given to the non-empty station. The problem of finding the generating function of the joint stationary queue length distribution can be reduced to a Riemann-Hilbert boundary value problem. We also discuss issues that arise when we want to use the solution of this boundary value problem to obtain performance measures like mean queue length and fraction of time that a station is empty. Joint work with Johan van Leeuwaarden.

We study a system which consists of a dispatcher and several identical servers in parallel, where the dispatcher must make a routing decision immediately on a customer's arrival. Customer service times follow a general distribution with finite first and second moments, with the actual service time of a customer known to the dispatcher on arrival. If the distribution is discrete, we propose a policy consisting of multi-layered round-robin routing at the dispatcher and shortest remaining processing time scheduling at the servers. This policy is shown to have a heavy traffic limit that is identical to one in which there is a single queue and optimal scheduling. We then proceed to discuss implementation issues, in particular what one should do if the service time distribution is continuous. Several simulation results are presented that suggest that the proposed policy is desirable if service time variability is high. We conclude with a brief discussion of related open problems.

In commonly used approaches for the discrete-time bulk service queue, the stationary queue length distribution follows from the roots inside or outside the unit circle of a characteristic equation. These roots can be considered to be located on a queue-specific curve. By adopting a special parametrization of this curve, the relevant roots occur as equidistant samples of a periodic function whose Fourier coefficients can be determined analytically. Then, using Fourier sampling, we derive analytic and root-free expressions for the mean and variance of the stationary queue length, as for the whole stationary queue length distribution. The resulting expressions are reminiscent of Spitzer's identity for the moment generating function of the steady-state waiting time for a G/G/1 queue. We also present analytic representations of the roots themselves in the form of sample values of periodic functions with analytically given Fourier series coefficients, making the conventional approaches more transparent and explicit. The resulting computational scheme is easy to implement and numerically stable.

Motivated by heavy-traffic limit theorems, we study a single-server queue with Gaussian input. In the talk, we are interested in the asymptotics of the steady-state probability of a high buffer content. This fits into the following framework: Let Y be a centered Gaussian process with stationary increments, possibly with long range dependent characteristics. Moreover, let mu be a 'drift' function that tends to infinity. Under certain conditions on Y and mu, we obtain the asymptotics of the probability P(sup Y_t - mu(t) > u), u to infinity, where the supremum is taken over the positive halfline. While a large deviation analysis only yields logarithmic asymptotics, completely different techniques are required to obtain exact asymptotics.

In this talk we consider a system with two carousels operated by one picker. The items to be picked are randomly located on the carousels and the pick times follow a phase-type distribution. The picker alternates between the two carousels, picking one item at a time. Important performance characteristics are the waiting time of the picker and the throughput of the two carousels. The waiting time of the picker satisfies an equation very similar to Lindley's equation for the waiting time in the PH/U/1 queue. Although the latter equation has no simple solution, it appears that the one for the waiting time of the picker can be solved explicitly. Furthermore, it is well known that the mean waiting time in the PH/U/1 queue strongly depends on the coefficient of variation of the inter-arrival time. Numerical results show that, for the carousel system, the mean waiting time and throughput are not very sensitive to the coefficient of variation of the pick-time.

Heavy traffic analysis of a closed queueing system with Gated Random Order of Service

Boxma et al. (2003) have proposed a closed queueing system with the gated random order as an appropriate delay model for blocked contention trees when used in closed populations, as e.g. in cable networks. Also, they gave a heuristic argument to obtain an approximation to the second moment of the delay for heavy traffic (or overload) conditions. In the talk, asymptotic techniques will be used to formalise these approximations. In particular, results will be stated about the fluid limit for such a system. Moreover, issues concerning the diffusion refinements of this fluid limit will be discussed.

The first Laurent series coefficients for singularly perturbed stochastic matrices

There are a few procedures for computing the Laurent series expansions for the mean passage time matrix and for the deviation matrix of a singularly perturbed Markov chain. We suggest here a method for computing the first terms in these expansions in a way which highlights the system dynamics in various time scales. We consider the general case when the unperturbed Markov chain has some transient states as well as at least two ergodic classes. We conclude with the application of the singularly perturbed Markov chains to the PageRank algorithm of Google.

Consider a class of irreducible Markov processes with semi-infinite set of states $(n_1,n_2,\mathbf{s})$, where $n_1$ and $n_2$ ranges from $0$ to $\infty$ (two-dimension). Vector $\mathbf{s}$ is an element of a finite set $\mathbf{S}$. For any state $(n_1,n_2,\mathbf{s})$ and $n_1>0$ the only possible transitions are to states with $n_1-1 \le n'_1 \le n_1+1$ and $n_2 \le n'_2 \le n_2+1$, i.e. in upper hemisphere. Such process can describe a big range of queueing models with priorities and two priority classes. Due to the special structure of this process it is possible to consider it as a QBD process and to apply existing methods in order to express the probabilities of the state with $n_1>0$ via boundary probabilities $n_1=0$. In this presentation two possible methods for finding steady state probabilities will be presented, based on matrix-geometric approach and based on generating function approach.

Graphical models are used to model multivariate dependencies, and have an intuitive representation using graphs. They can be used for causal modeling and are recently being applied in artificial intelligence systems. This talk will introduce some of the basic concepts of graphical models. No specific prior knowledge is required.

Perturbation analysis for denumerable Markov chains with applications to queueing models

We study the parametric perturbation of the stationary distribution of Markov chains with denumerable state spaces. In the case of singular perturbations, the transition probabilities of a Markov chain, with several ergodic classes, are perturbed such that (rare) transitions between the different ergodic classes of the unperturbed chain are allowed. We relax commonly made assumptions in related literature in order to apply the results to queueing models. Assuming nu-geometric ergodicity, we are able to explicitly express the steady state distribution of the perturbed Markov chain as a Taylor series in the perturbation parameter. We specialize our results for quasi birth and death processes and provide queueing examples.

Sunday morning. Mr. Short arrives at the supermarket waitingline carrying only a bag of bagels. Ahead of him he finds Mrs. Long holding an overly loaded cart. Would it be fair to serve Long ahead of Short? "How much fair" would it be to push Short ahead of Long? Recent studies have shown that fairness is a very important issue for human beings in queues, perhaps as important as the waiting itself. Nonetheless, Queueing Theory that has been developed for several decades, has hardly dealt with this issue. The objective of this work is to start studying this subject and propose measures that can be used to evaluate level of fairness in queueing systems. In particular we aim at a measure that can addressthe Short/Long tradeoff. This problem is challenging, especially due to the constantly changing "set of players" in the queue. Once such measure is developed and agreed upon and a scale ofreference is developed, practitioners can use it to evaluate the fairness level of their systems and its corresponding quality. We will discuss two measures; the first is based on order-of-service principles while the second is based on resource allocation principles. The latter seems to better account for the tradeoffs between seniority and job-size (as demonstrated in the Short/Long case). We will analyze the measure and present its major properties. Joint work with Benjamin Avi-Itzhak and David Raz

Traditional definitions of capacity of CDMA networks are either related to the number of calls they can handle (pole capacity) or to the arrival rate that guarantees that the rejection rate (or outage) is below a given fraction (Erlang capacity). We extend the latter definition to other quality of service (QoS). We consider best-effort (BE) traffic sharing the network resources with real-time (RT) applications. BE applications can adapt their instantaneous transmission rate to the available one and thus need not be subject to admission control or outages. Their meaningful QoS is the average delay. The delay aware capacity is defined as the arrival rate of BE calls that the system can handle such that their expected delay is bounded by a given constant. We compute both the blocking probability of the RT traffic having an adaptive Grade of Service (GoS) as well as the expected delay of the BE traffic for an uplink multicell WCDMA system. This yields the Erlang capacity for former and the delay capacity for the latter.

We consider a random walk $S_n=\sum_{i=1}^n\xi_i$ with a heavy-tailed distribution of increments. When the mean is finite and negative, then the asymptotics of $M=sup S_n$ is given by the well-known Veraverbeke theorem. We study these asymptotics when $\mathbf |\xi_1|=\infty$. In particular, we state results in the case of regularly-varying tails. Also, we give asymptotics for $M_\tau=\max_{0\le i\le \tau} S_i$, where $\tau$ is a stopping time.

The performance of networks and their ability to offer Quality of Service (QoS) depend on accurately capturing the parametric dependence of the QoS measures such as the delay or loss distributions. The stringent QoS requirements imply that the estimations are associated with the tails of the buffer occupancy distribution which naturally leads to a study of the asymptotics. There are basically two approaches 1) The large buffer asymptotics, and 2) The many sources asymptotics. Both cases for a single node have been investigated quite thoroughly. However, there has been limited success at identifying the asymptotics for network models. In this talk, I will present results on the buffer overflow and packet loss asymptotics for a network and their implications for admission control. The network considered is accessed by mutually independent classes of traffic and is assumed to be loop-free with respect to source-destination pairs. Large buffer asymptotics was obtained for long range dependent inputs. A network with small buffers was also analyzed for general arrivals under the many sources asymptotics.

In this paper we investigate a single server retrial queue with a finite number of heterogeneous sources of calls. It is assumed when a given source is idle it will generate a primary call after an exponentially distributed time. If the server is free at the time of the request's arrival then the call starts to be served. The service time is also exponentially distributed. During the service time the source cannot generate a new primary call. After service the source moves into free state and can generate a new call again. If the server is busy at the time of the arrival of a primary call, then the source starts generating so called repeated calls with exponentially distributed times until it finds the server free. As before, after service the source becomes free and can generate a new primary call again. We assume that the primary calls, repeated attempts and service times are mutually independent. This queueing system and its variants could be used to model magnetic disk memory systems, local area networks with CSMA/CD protocols and collision avoidance local area networks. The novelty of this model is the heterogeneity of the calls, which means that each call is characterized by its own arrival, repeated and service rates. The aim of the paper is to give the usual steady-state performance measures of the system. To do so, an efficient software tool, MOSEL ( Modeling, Specification and Evaluation Language ) developed at the University of Erlangen, Germany, is used to formulate and solve the problem. Several sample numerical results illustrate the power of the tool showing the effect of different parameters on the system measures.

In the standard formulation of the occupancy problem one considers the distribution of r balls in n cells, with each ball assigned independently to a given cell with probability 1/n. Although closed form expressions can be given for the distribution of various interesting quantities these expressions are often of limited practical use. Approximations provide an attractive alternative, and in this talk, we consider a large deviation approximation as r and n tend to infinity. We consider a dynamical model, where the balls are placed in the cells sequentially and "time" corresponds to the number of balls that have already been thrown. A sketch of the large deviation analysis of this "process level" problem is presented, and the rate function for the terminal problem is then obtained via the contraction principle. The solution to the corresponding variational problem that characterizes this rate function is also presented. The solution is fairly complete and explicit: the minimizing trajectories and minimal costs are identified up to two constants which are the unique solutions to an elementary fixed point problem. Some examples and extensions are discussed, including results obtained from importance sampling which allow estimation of probabilities rather than exponents via the change of measure afforded by the solution to the calculus of variations problem.

We present a unified treatment of sigular perturbations in finite Markov chains. The treatment is based on the analysis of series expansions of various important entities such as the perturbed stationary distribution matrix, the deviation matrix and the mean passage times matrix. Some combinatorial issues will be looked at too.

Sid Resnick, (School of Operations Research and Industrial Engineering, Ithaca, USA), January 22, 2003

Limits of on/off hierarchical product models for data transmission

A hierarchical product model seeks to model network traffic as a product of independent on/off processes. Previous studies have assumed a Markovian structure for component processes amounting to assuming that exponential distributions govern on and off periods but this is not in good agreement with traffic measurements. However, if the number of factor processes grows and input rates are stabilized by allowing the on period distribution to change suitably, a limiting on/of process can be obtained which has exponentially distributed on periods and whose off periods are equal in distribution to the busy period of an M/G/infinity queue. We give a fairly complete study of the possible limits of the product process as the number of factors grow and offer various characterizations of the approximating processes. We also study the dependence structure of the approximations.

We study sensitivity analysis for performance characteristics of stochastic processes. We will address the finite/transient problem and the infinite/stationary problem. Specifically, we introduce a concept of measure valued differentiation, called $ \cal D $--derivative, where $ \cal D $ is an appropriately defined class of performance functions $g$, such that the derivative of the integral of $g$ with respect to the measure under consideration exists. $ \cal D $--differentiation generalises the concept of weak differentiation, and our approach (1) works uniformly on a predefined class of performance functions, (2) allows for a product rule of differentiation, that is, analysing the derivative of a measure immediately yields results for finite products of the measure. Measure valued differentiation can be applied to conditional measures, such as Markov kernels as well, and then clearly identifies the trade--off between the generality of performance classes that can be analysed and the generality of the classes of measures.
We will discuss how one can go from finite horizon results to infinite horizon results. We will conclude with some remarks on estimation.

We consider a tandem queueing model consisting of two stations. Special feature of the model is that the total service capacity of the stations together is constant. When both stations are nonempty, a given proportion of this capacity is allocated to the first station and the remaining part to the second station. However, if one of the stations becomes empty, the total capacity of the two stations together is allocated to the other station. The model is motivated by a situation encountered in multi-access communication in cable TV networks. Before users are actually allowed to transmit data over a communication channel, they first have to obtain a kind of grant in order to avoid collisions. The total capacity of the communication channel is divided over the two different stages: allocation of the grants on one hand and transmission of actual data on the other hand. We study the two-dimensional Markov process representing the numbers of jobs in the two stations. A functional equation for the generating function of the stationary distribution of this Markov process is derived and the solution of the functional equation is obtained. In the analysis we use the theory of Riemann-Hilbert boundary value problems.

Restless bandits: PCL-indexability conditions and applications to control of queueing systems

Restless bandits (RBs) are Markov decision chains having two actions (active/passive) available in each state. Besides their intrinsic interest, they arise as building blocks in a rich variety of complex resource allocation models, including the restless bandit problem (RBP). This involves the sequential selection of stochastic projects, modeled as RBs, where passive projects can keep evolving. Unlike the classical multiarmed bandit problem (where passive projects are frozen), which is solved optimally by the Gittins index rule, the RBP is computationally intractable. Whittle (1988) proposed an appealing index policy for the RBP, based on the optimal solution of individual RBs. The Whittle index, however, is not defined for all RBs, which prompted research efforts to identify simple indexability conditions. We recently proposed the first such indexability conditions, based on the satisfaction of Partial Conservation Laws (PCL). The talk will review the PCL-indexability conditions, as well as more recent work, dealing with (1) the intuitive interpretation of PCL-indexability in physical and economic terms; and (2) applications for the derivation of new index policies in queueing systems control.

We formulate the problem of the optimal scheduling and control of a manufacturing system, for a finite horizon under on-line policies.This problem incorporates some of the features of discrete deterministic scheduling problems, as well as of control of discrete stochastic multiclass queueing networks, and it is intractable. It can however be approximated by a deterministic, continuous, linear control problem. This suggests a 3 step procedure: (i) The optimal solution of the fluid problem provides a lower bound on the objective of the original problem (ii) The fluid problem can be solved in practice, e.g. as a separated continuous linear program (iii) The fluid solution can be used to obtain a heuristic scheculing and control policy for the original system, with a probabilistic performance guarantee. We discuss various aspects of this approach.

Thermodynamical Limit for Symmetric Closed Qeueuing Networks

We study the thermodynamical limit for a mean field model describing how a closed symmetric queueing network operates. The Markov process under consideration is invariant under the action of a certain symmetry group G in the phase space. We prove that the quotient process on the space of orbits of G -action converges to the limit deterministic dynamical system. From the properties of this dynamical system the Propagation of Chaos property follows.

Bandwidth sharing in a large star-shaped network: mean-field heuristics and operator-based analysis

We consider a symmetrical star-shaped network, in which bandwidth is shared among active connections, according to some sharing policy. We introduce the so-called "min" policy as a conservative approximation to the classical "max-min policy". Starting from a chaos propagation hypothesis, plausible when the system is large enough, one can write equilibrium equations for the load on an arbitrary link of the network. Numerical and analytical study of the equations allow to state several qualitative conclusions about the impact of various parameters (e.g. link intensity factor and route lengths) on mean document transfer time. Also we present an approach based on functional analysis of nonlinear integral operators, to get a quantitative characterization of the behaviour of the network under heavy traffic conditions.

Heinz Weisshaupt (Department of Statistics and Decision Support Systems, Vienna University),
December 19, 2000

A measure valued Approach to Convex Set-Valued Dynamics, applicable to constraint stochastic optimization

We introduce a new concept of differentiable set-valued dynamics and show the existence of solution curves. To do this we introduce simple set-valued functions which are completely determined by a convex set and a function on the boundary of this set, and show the differentiability of these functions from the right at t=0. Then we approximate local solutions of our dynamical system by set-valued functions consisting of a finite number of simple functions. The dynamics are described by functions on the boundaries of convex bodies. (This is analogous to the description of single valued dynamics by vector fields.) It can be shown that in some special cases applicable to set-valued constraint stochastic optimization, the local solutions can be glued together to provide global ones. A constraint stochastic optimization problem is investigated.

We discuss two important approaches, fluid and regenerative, which are widely used in stability analysis of queueing networks.

First part is a survey of recent works devoted to fluid approximation in stability analysis of multiclass networks. We derive flow balance equations and corresponding fluid limit model. Relation between stability of the fluid model and stability of the original queueing network is also considered. Then we discuss stability of Jackson-type network and some related topics (e.g. network instability, convergence of moments). A few numerical examples illustrate instability under conventional traffic assumption.

In the second part, which is mainly based on works of author we outline main steps of the regenerative approach to stability analysis of Jackson-type and multiclass networks. We touch assumptions of weak regeneration of the network processes, renewal technique in proof of stability and simulation of weakly regenerative processes.

A brief survey of multiaccess communication is presented. The talk focuses on collision resolution algorithms. ALOHA and splitting tree algorithms are discussed, and the delay analysis of a splitting tree algorithm (dueto Mathys and Flajolet) is outlined. Note: this is not a talk about my own research. Background material: Ch. 4 of the book Data Networks of Bertsekas and Gallager.

We examine a replacement system with discrete-time Markovian deterioration and finite state space $\{0,...,N\}$. State 0 stands for a new system, and the higher the state the worse the system; a system in state $N$ is considered to be in a {\it bad state}. We impose the condition that the fraction of replacements in state $N$ should not be larger than some fixed number. We prove that a generalized control limit policy maximizes the expected time between two successive replacements and we explain explicitly how to derive this optimal policy.
Some numerical examples are given.

The term "sensitivity analysis'' refers to the estimation of the impact of changes in expected performance of a Discrete Event System (DES) upon changes of some of the input parameters. In some cases it can be expressed as a gradient. Sensitivity estimation can be divided in three categories: the pathwise analysis (covering the so-called perturbation analysis--or PA methods), the weak differentiation methodology, and perturbation methods, which include finite differences, harmonic analysis and simultaneous perturbations. We propose a methodological study and explain how different estimation techniques can be ``recovered''. We will emphasize the first two approaches and (time permitting) introduce the third. Selected examples will serve as the basis for the construction of the corresponding sensitivity estimators.

An informal meeting in which the martingale method is discussed.
On our request he will give a brief outline of the method that is presented in his paper with W. Whitt (Useful martingales for stochastic storage processes with Levy input, J. Appl. Probab. 29 (1992) 396-403), and answer our questions.

With the aim of studying a multi-station feedforward fluid network with Markov modulated input and output rates we first study a two dimensional parallel network having the property that the second station cannot be empty unless the first station is. A method for computing the steady state characteristics of such a process is given and it is shown that this can be used to determine the steady state characteristics of two dimensional tandem fluid networks and more general networks. Finally a multi-station feedforward network is considered. Under appropriate conditions, it is explained how to determine the joint steady state Laplace-Stieltjes transform (LST) and it turns out that in order to compute conditional means and the covariance structure (given the state of the underlying Markov chain) all that is needed is the methods developed for the two dimensional parallel model together with some trivial linear algebra.

We consider M/G/1-type and G/M/1-type queueing systems with 'disasters', occurring at certain random times and causing an instantaneous removal of the entire residual workload from the system. After such a clearing, the system is assumed to be ready to start working again immediately.
We consider clearings at deterministic equidistant times, at random times and at crossings of some pre-specified level, and derive the stationary distribution of the workload process for these clearing times and some of their combinations.

Only a few works in the literature study polling systems with failing nodes. None, however, has treated the associated repair process or the combined effect of breakdowns and repairs on system's performance and quality of service. We'll consider three service mechanisms: Gated, Exhaustive and Globally-Gated. For each regime we study several variations, differing from each other by (i) whether the arrival process to a queue being repaired continues or stops during the repair process, and (ii) whether the failure is observed immediately when it occurs or only at the end of a service (e.g. transmission) duration. For each of the above models we'll provide analyses regarding the system state at polling instants (law of motion, probability generating functions, first and second order moments) and derive expressions for several performance measures such as (distribution and mean of) number of customer various models and express all results in a unified generalized form.

Tail behaviour of stationary wainting time in two-server queue: heavy-tailed case (Joint work with Sergei Foss)

Our talk is devoted to the asymptotic behaviour of the distribution tail of the stationary waiting time W in the GI/GI/2 queue. Given that the service times have subexponential distributions, we discuss the lower and upper bounds for P{W>x}. It turns out that these bounds heavily depend on the value of the traffic load.

The last two decades have witnessed the advent of sophisticated methods for sensitivity analysis and optimisation of stochastic systems. In the first part of the talk, we give an overview of these new methods, such as perturbation analysis, the score function (importance sampling) and the weak derivative. The second part of the talk is devoted to the application of the weak derivative to option pricing of an American call option.

Denoting f_{\alpha,\beta}(F) the image of a natural exponential family (NEF) on R by the affine transformation f_{\alpha,\beta} and by F_{\lambda} its {\lambda}-th convolution power, we describe all the NEF for which f_{\alpha,\beta}(F) = F_{\lambda} for a given (\alpha,\beta,\lambda). We get a discrete version of NEF with a power or exponential variance function. We apply this result to determine all reproducible NEF as defined by Bar-Lev and Enis (Ann. Statist. 1986, Reproducibility and natural exponential families with power variance functions).

A stochastic cash management system is studied in which the cash flow is modeled by the superposition of a Brownian motion with drift and a compound Poisson process with positive and negative jumps for "big" deposits and withdrawals, respectively. We derive explicit formulas for the disruptions of the bankruptcy time, the time until bankruptcy or the reaching of a prespecified level, the maximum cash amount in the system, and for the expected discounted revenue generated by the system.

A sequence of random numbers is learned in strict succession. Immediately after each observation we must either select or reject the observed number. The numbers selected must increase. The goal is to select a possibly long increasing subsequence.
If the total number of observations is a fixed integer $n$, there is a simple algorithm which yields, on the average, approximately $\sqrt{2n}$ selections (Samuels/Steele), as is well known. We consider the more general situation when the number of observations is a random variable $N$ with known distribution. The problem of maximizing the average length of selected subsequence is solved asymptotically, as $N$ becomes in a sense large.
We also discuss a multivariate version of the problem (joint results with Yu. Baryshnikov) as well as the related problem with sum constraints.

We suggest two approaches for pricing in congested systems. One is based on externalities, i.e. one pays for the added waiting time one imposed on others. The other is based on applying the Aumann-Shapley price mechanism to the time of waiting functions. Examples are given for the M/G/1 queueing system under various entrance disciplines.

We consider a loss system with $c$ parallel identical servers, no waiting room and two classes of customers. We prove the existence of thresholds in determining the admission rules. We, also, establish sufficient conditions for the existence of a high priority class, which we call the ``preferred'' class: the optimal policy saves some of the resources by keeping idle servers even in the presence of non-preferred customers with the intent of providing a better service level for future customers of the preferred class. Under more restrictive conditions, it is shown that the preferred class is determined by a ``modified'' $c\mu$ rule. We consider the system under single and batch arrivals which occur according to a Poisson or a Markov arrival process as well as with fixed rewards and rejection costs and random rewards.

For the evaluation of queueing systems it is common practice to define some (embedded) Markov chain, which represents the queueing behaviour. Usually, these Markov chains are random walks on a (multi-dimensional) grid. Several approaches are available for constructing the equilibrium distributions of these random walks, however, none of these approaches is generally successful. The presentation will focus on a direct approach based on linear combinations of product-form solutions. It will be indicated when this approach works and what results are obtained.
The presentation summarises joint work of the last 10 years with Ivo Adan, Geert-Jan van Houtum, Jeremy Visschers and Henk Zijm.

A compensation approach for two-dimensional random walks with geometric jumps

Several queueing problems lead to Markov chains with jumps of unbounded length, particularly with geometric behaviour in one or more directions. In the talk the equilibrium behaviour is analysed for two-dimensional nearest neighbour random walks, which may make geometric jumps in one direction. It is shown that, under some rather severe restrictions on the jump rates in the interiour of the random walk, the solution to the equilibrium equations is an infinite sum of product forms. This solution can be constructed using a compensation method. During the presentation some specific problems, that occur when analysing these models, and the solution to these problems are discussed.

Martin boundary is found for transient homogeneous random walks on $Z^2$ with different jumps in a finite number of states and for random walks on $ Z\times Z_+$ and on $ Z_+^2$ with piecewise linear homogeneities. Analytic approach is used. An elliptic curve defined by the generating function of jumps is considered. In most cases Martin boundary and the minimal Martin boundary are related to some subset of real points of this curve and are homeomorphic to a segment. In other cases, the minimal Martin boundary consists of one or two points, while the Martin boundary is much larger.
Joint work with V.Malyshev (INRIA, France)

The problem of finding the tail behaviour of the waiting time distribution in multi-server queues is addressed under the assumption that the service time distribution is heavy-tailed. After having reviewed some general results (lower and upper bounds), some results for a special multi-server queue (which is analytically tractable) are presented.
This research (joint work with Onno Boxma and Qing Deng) is still ongoing, so the talk will be rather informal.

Analysis of series of idenical queues has numerous applications and leads to various interesting mathematical questions. In this talk I will tell about some of them and also about the connections this model has with other topics such as percolation, combinatorics, random matrices etc. As an application a conjecture by Glynn and Whitt is proved.

Three stopping problems for queues with applications to statistical control processes

We consider three problems for dual versions of statistical control processes. In the first problem each of the dual processes fluctuates between two linear boundaries, in the second problem above the lower boundary and in the third below the upper boundary.
In the primal version the process is a compound Poisson process with positive general jumps and in the dual version it is a compound renewal process with exponential jumps. The duality is based on time reversal theory. A relevant functional for the first problem is the probability of hitting the lower boundary before upcrossing the upper boundary. For both the second and third problems relevant functionals are the maximal distance from the boundary during the lifetime of the process. Explicit expressions for these functionals are introduced by exploiting queueing theory.

Gleb Koshevoy (Moscow, currently at the University of Cologne), September 22, 1999

The market of information goods as with computer software already occupies a significant and increasing share of the world market. Such a situation presents mathematical economists with a problem on modelling this market; that is, specifying a space for information goods and a space for prices, aims and constraints of agent, establishing conditions of existence for balanced states in the market and possibily efficiency properties of such states. There is a crucial difference between information goods and ordinary goods. Ordinary goods are added according to the usual sum, while sum of information goods is indempotent operation.
As a market good, an information good is not scarce in the economic sense: once obtained the same good can be used by everybody who buys it even though the original owner has not lost it. Another characteristic feature of information goods is the insignificant cost of reproduction.
We consider a competitive equilibrium model like the Arrow-Debreu model, and study the existence and optimality of equilibria. The crucial requirements that provide the existence of an equilibrium are that consumers' preferences and producers' cost functions are submodular functions.

S. Kerov, (Steklov Institute, St. Petersburg branch, currently Gottingen), September 29, 1999

The problem of finding the longest increasing subsequence in a random permutation (known also as Ulam problem) surfaced around in the networking community many times (in the context of online bin packing, or, more prominently, in the context of long series of queues). Remarkably, the most successful approach to study this and many other related problem stems from the asymptotic representation theory of symmetric groups, that is of large Young diagrams.

Georg Pflug, (University of Vienna and IIASA, Laxenburg, Austria), October 11, 1999

We consider a stochastic optimization problem such as a one- or multiperiod portfolio optimization problem under constraints and study the dependence of the solution on the assumed probability model.
The notion of epi-convergence and epi-distance is introduced and applied to the problem. The sensitivity w.r.t. the probability model is relevant in particular if we approximate the theoretical model by the empirical model, i.e. the model based on statistical observations.
We give some results on convergence and asymptotics of solutions of stochastic programs. There is an obvious connection to asymptotic statistics for M-estimates.

We review some typical problems: Multiperiod (tree structured) problems and problems with nonlinear risk measures (such as value-at-risk) as objectives. Again questions of sensitivity and asymptotics are considered. Variational analysis is used to link optimal value considerations with solution set considerations.

Load-balanced networks became popular in recent research, both theoretical and applied. Here, a task selects a sample of servers and joins a server from the sample with a shorter queue. As samples may intersect, this creates an intricate dependence between the queues at different nodes. There is a variety of questions to ask about the behaviour of this kind of networks: the capacity domain, the form of the equilibrium distribution, asymptotical results. The talk will focus on Jackson-type load-balanced networks where the arrival flows are Poisson, and the tasks select samples independently.

We study (a somewhat simplified version of) the Tetris game (two dimensional geometric objects, called pieces, falling down on a surface for ming heaps). However, simple as it may seem, our version of the Tetris game contains, in a nutshell, many interesting problems in the area of stability of stochastic processes.
In our talk, we will formalise the Tetris game within an exotic algebraic framework, called (max,+) semiring, and we show that Tetris ``linearises'' in this semiring. We will then study the asymptotic growth rate of the heap of pieces generated by the Tetris game. Guided by our little sample system, we will discuss the existing limit theory for stochastic sequences, such as the Perron--Frobenius theory, Markov chain analysis and Borovkov's renovating event theorem. Finally, we discuss some recent results on Taylor series expansions for the asymptotic growth rate.

Recent advances on the achievable regions approach to the optimal control of stochastic networks

The achievable region method address optimal control problems on stochastic systems by reducing them to deterministic mathematical programming problems. To do so it seeks to formulate the region of achievable performance spanned by the performance vector of interest under all admissible policies by means of tractable convex constraints. Deterministic optimization of a performance objective over this region, or relaxations thereof, gives information on the optimal system performance, and may give insight for designing (nearly) optimal policies. The talk will focus on recent advances of this approach developed by speaker and coworkers, on three types of stochastic scheduling models: 1) bandit problems (both classical and restless); 2) multiclass queueing networks and 3) parallel scheduling.

T. J. J. (Dee) Denteneer, (Philips Research, Eindhoven), November 24, 1999

Access networks (e.g. cable networks) are currently being standardized (e.g. DOCSIS, IEEE, DAVIC/DVB) and are the focus of extensive commercial activity.
Characteristic for such networks is a sequential procedure for data transfer from a station at the customer premises to a central node, which consists of two stages. First, a contention stage is carried out, in which a station requests a number of data slots (in contention with other stations). Second, a data transfer stage is carried out, in which the data is transferred in reserved data slots.
In the talk we will describe these networks in some detail and address a number of the performance issues: - Optimisation: such a network has a large number of degrees of freedom that affect performance. These are currently being set via simulation. However, simulation is very slow. - Analysis: The sequential procedure defines a double queueing system for which no analytical treatment is known even in case of Poisson traffic. - Traffic modeling: The performance of access networks is sensitive to both long-range dependencies and short-range dependencies in the traffic carried over the network. This requires new traffic models that accurately reflect both types of dependencies.

We analyse the tail behaviour of stationary response times in the class of open stochastic networks admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i_0 is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j>= i_0 asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i_0. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general open (max,+)-linear systems associated with M-dependent driving matrices having one (or more) dominant diagonal entry in the subexponential class.

Large Deviation Probabilities For Random Walks. Part I. Regularly varying distribution tails

We establish first order approximations and asymptotic expansions for probabilities of crossing arbitrary curvilinear boundaries in the large deviations range by random walks with regularly varying distribution tails. In particular, we study the large deviations probabilities for the sums and maxima of partial sums of independent and identically distributed random variables.