|
|
|
|
Schedule.
We consider how to choose the reproduction rates in a one-dimensional contact process on a finite set to maximize the growth rate of the extinction time with the population size. The constraints are an upper bound on the average reproduction rate, and that the rate profile must be piecewise constant. We show that the optimum growth rate is achieved by a rate profile with at most two rates, and we characterize the solution in terms of a ``spatial correlation length" of the supercritical process. The proofs make use of a planar-graph duality in the graphical representation, due to Durrett and Schonmann.
The problem formulation was motivated by the following caricature of a surveillance problem using a linear wireless ``smart dust" network. We drop an array of N radio-equipped sensing capable smart dust motes in a line. The motes can acquire a common state of interest directly from the environment, but subsequently are unable to reobtain it, perhaps because of security concerns, or because the environment has once again become uninteresting. Individual motes may forget the state, perhaps due to memory constraints while they are performing other tasks. We assume however, that a mote can talk to its neighbouring motes asynchronously, enabling them to reacquire the lost state. Such inter-mote communication has a cost. Our problem then becomes one of maximizing the time for which the common state can be maintained by the smart dust array given a fixed bound on the cost one is willing to pay for inter-mote communication. Such time may be of interest because the smart dust array may have been designed to subsequently be interrogated by satellite or by air to recover the state.
Joint work with Aaron B. Wagner
It is well-known that scheduling policies which bias towards short jobs, such as SRPT (Shortest-Remaining-Processing-Time) result in low mean response times, as compared with fair scheduling policies such as PS (Processor-Sharing). What is less clear is what the performance impact on the long jobs will be.
In this talk we evaluate scheduling policies from the perspective of a new metric: the slowdown experienced by the long jobs. We analyze the SRPT policy in depth, and also use our metric to create a taxonomy of all scheduling policies.
In addition to analysis, we also present empirical results from our Apache web servers which are instrumented with alternative scheduling policies.
Joint work with Karl Sigman and Adam Wierman.
Fluid models are the deterministic analogs of queueing networks. Work over the last decade by various authors has shown that, for certain disciplines, convergence of the solutions of their fluid model equations implies the existence of heavy traffic limits and the stability of the corresponding queueing networks.
The convergence of such fluid model solutions is typically shown by the use of a Lyapunov function, and in various cases, by employing an appropriate entropy function. These techniques has been used by the speaker for FIFO networks and for HLPPS (head-of-the-line proportional processor sharing) networks. Work in progress applies related entropy and Lyapunov functions to processor sharing networks. LIFO networks will also be briefly discussed.
We devise a family of scheduing policies for stochastic processing networks that have been proposed by Harrison (2000). These networks are general, and they can model parallel server systems, input-queued switches, queueing networks with flexible servers, and networks with alternative routing. The devised policies, tentatively called maximum-pressure policies, are dynamic in that only local and downstream neighboring buffer levels are used.
We prove that a maximum-pressure policy is throughput optimal as long as each processing activitiy consumes jobs from one buffer. As a consequence, we characterize the stability region of the policy by a certain linear program (LP). This LP is different from the static LP advanced in Harrison (2000) and later used by Bramson and Williams (2002). We provide an example showing that the latter LP does not capture the stability region of a stochatic processing network when multiple servers are needed to process an activity.
Joint work with Wuqin Lin.
The topic of discussion will be a measure valued process that describes the dynamics of a GI/GI/1 processor sharing queue. At each fixed time, the process encodes the residual service times of jobs in the system as a random measure. From this measure valued process,one can recover standard performance processes, such as queue length and workload, by integrating against an appropriate function. This measure valued description plays an important role in the proof of a heavy traffic limit theorem for the GI/GI/1 processor sharing queue, which provides a diffusion approximation of the queue length process as a corollary. The measure valued description is also useful for analyzing performancemeasures associated with individual jobs, such as sojourn times or more general timing requirements.
The Internet is a federation of thousands of autonomous systems. Understanding and modeling the interaction of the autonomous systems is a key to improved prediction and control of the Internet. Revenues less expenses for each of the autonomous systems, be they nonprofit or for profit, is a key factor determining the value the Internet. We explore several possible definitions of network equilibrium based on capacity and prices, with an eye towards exploring the effect of market pressures on the fairness of allocation of network resources.
Joint work with Ganesh Gopal.
Massoulie and Roberts have introduced and studied a flow level model of Internet congestion control, that represents the randomly varying number of flows present in a network where bandwidth is dynamically shared between elastic document transfers.
In this talk the formalism of balanced fluid models and Brownian networks will be used to explore the behaviour of the flow level model in heavy traffic. Particular interest attaches to the phenomenon of entrainment, whereby congestion at some resources may prevent other resources from working at their full capacity.
Joint work with Ruth Williams.
How much information can wireless networks carry?
How should they be operated?
We present a network information theory which addresses these issues.
We show that when the medium has absorption, multi-hop transport is optimal, and the transport capacity grows like O(n). However, when there is absolutely no absorption, and the path loss attenuation is very little, then the transport capacity can grow like O(n^\theta) for \theta > 1, and a strategy of coherent multi-stage relaying with interference cancellation can be optimal.
Along the way, we show when the total power used by all the nodes bounds the transport capacity and also obtain a feasible rate for a Gaussian multiple-relay channel.
Joint work with Liang-Liang Xie.
It is well known that the performance of a network deteriorates when customers are allowed to choose routes in their self-interest, with the most famous result in this vein being the so-called Braess paradox. In this work we study self-interested routing in the context of stochastic networks, taking into account the discrete stochastic dynamics of such networks. We consider a two station network with renewal arrival processes and deterministic service times. A system manager chooses the scheduling rule at each station. The goal of the system manager is to minimize the expected number of customers in the system. Individual customers selfishly choose their route through the network so as to minimize their individual expected delay. We study the behavior of this system in Nash equilibrium, where each customer makes a choice the penalizes unilateral deviation. That is, if all customers except one made the choice suggested by the Nash equilibrium, the deviating customer would incur a greater expected delay than if she chose according to the Nash prescription.
We address two issues in this work. The first issue is to quantify the maximum performance degradation due to self-interested routing. We show that the system can be unstable (i.e. the number of customers in the system grows without bound) in Nash equilibrium when the system manager naively chooses the scheduling rule. Incidentally, we establish that the join-the-shortest-queue routing discipline can be unstable. The second issue is to design a scheduling rule that negates the performance degradation due to self-interested routing. That is, the scheduling rule induces a Nash equilibrium in which the system performance is as good as that in a system where the system manager is allowed to decide the routes of the customers. We propose one such scheduling rule, which has an intuitive structure, and quantify its performance.
Joint work with Ali Parlakturk
The value of a Markov control problem with long run average costs can be obtained as the solution of an infinite dimensional linear programming problem. This approach will be taken to study the convergence of the value for controlled processing networks in the heavy traffic limit. In particular, the relationship of the definition of "heavy traffic" developed by Harrison, Williams and Bramson and conditions needed for the good behavior of the sequence of linear programs will be considered. Controls in the models include both scheduling and initial assignment of work.
We add time to a Petri net in the following manner. The n-th firing of transition a has a duration a(n) and we assume that (a(n)) is a sequence of i.i.d. random variables. Places with choice are dealt with by introducing a routing: let b be such a place, then the n-th token entering the place is routed to transition b(b) and the sequence (b(n)) is i.i.d. The goal is to study the dynamic of such stochastic Petri nets. In this talk, we focus on the existence and computation of asymptotic throughputs for the transitions. In some cases, it is possible to model the dynamic evolution as x_{n+1}=T_n(x_n), where (T_n) is an i.i.d. sequence of max-plus linear maps, or of topical maps. Since there exist ergodic theorems for the iterates of such maps, we get as a corollary the existence of the throughputs. In other cases, the so-called monotone-separable framework of Baccelli-Foss, can be used to prove the existence of throughputs. These two approaches enable to cover the cases of open and closed event graphs, Jackson networks and Free Choice Petri nets. We survey these results and we insist on the case of live and bounded Free Choice nets, where getting the result requires to prove a structural property of independent interest: the existence and uniqueness of the `blocking marking'.
Joint work with B. Gaujal and S. Haar.
This talk is concerned with gossip-based information dissemination, according to which each participant of a group propagates information by ``gossiping'' to a few randomly selected group members. In a first part of the talk we show how the classical results of Erdos and Renyi on the connectivity of random graphs apply to characterise the performance of such systems. We also discuss the robustness of the Erdos-Renyi results when the underlying assumptions are relaxed. In a second part, we describe distributed mechanisms that enable new members joining the group to be provided with a list of random members of the right size given performance objectives. These mechanisms can be seen as probabilistic rules for the growth of a random graph.
This paper concerns policy synthesis in large queuing networks. The
results provide answers to the following questions:
(i) It is well-known that an understanding of variability is
important in the determination of safety stocks to prevent unwanted
idleness. Is this the only use of high-order statistical information in
policy synthesis?
(ii) Will a translation of an optimal policy for the deterministic
fluid model (in which there is no variability) lead to an allocation which
is approximately optimal for the stochastic network? If so, what is the
`regret'?
(iii) What are the highest sources of sensitivity in network control?
A sensitivity analysis of an associated deterministic optimal control problem provides an exact dichotomy in (ii). If an optimal policy for the deterministic fluid model is `maximally non-idling', then variability plays a small role in control design.
If this condition does not hold, then the `gap' between the fluid and stochastic optimal policies is exactly proportional to system variability. However, sensitivity of steady state performance with respect to perturbations in the policy vanishes with increasing variability.
Jonit work with
Mike Chen
A discrete version of Pitman's theorem states that, if X is
a simple random walk with positive drift, and M(n) is its
maximum up to time n, then the process 2M-X is Markov
and has the same law as that of X conditioned to stay
positive. I will show how the classical output theorem
for the stable, stationary M/M/1 queue, namely that the
departure process is Poisson, can be used to prove this
and, moreover, obtain a multi-dimensional generalisation.
This carries over to the Brownian motion setting, and in
this context there is a direct connection with eigenvalues
of random matrices. (This joint work with Marc Yor.)
I will then explain how all this is related to the RSK
correspondence between "words" and pairs of tableau.
Making this connection yields an alternative proof
of the above representation theorem and reveals more
of the mathematical structure of the processes involved.
It also leads to a new formula for the RSK algorithm,
which has a queueing interpretation, so that queueing
theoretic ideas can be used to analyse the algorithm
and its properties; going in the other direction, it yields
a formula, in terms of Schur polynomials, for the transient
distribution of any number of M/M/1 queues in series.
In this talk we consider the effect of physical scaling on
network performance. By the "physical scaling" of a network
we mean the reduction of its link speeds and buffer sizes by
a factor p and applying a proportion p of the original traffic
to this scaled version.
Our main finding is this: Physical scaling induces a performance
scaling, in that queueing delays, drop probabilities, and the
distribution of the number of concurrent connections are left
virtually unchanged. We verify this through analysis and simulations.
We discuss the implications of this for (i) the recently proposed
deterministic, differential equations-based models of networks
supporting long-lived flows, (ii) the M/GI type models of network
flows, and (iii) the scaleable prediction of network performance.
Joint work with: Rong Pan, Costas Psounis, Mayank Sharma and Damon Wischik
The governing laws of evolution of real-world
queueing systems vary with time.
While time-homogeneous models may serve as
reasonable approximations for slowly varying
systems, they fail to capture many
important time-dependent phenomena such as
rush hour, periodicity and sudden network
failures.
Mandelbaum and Massey (1993) obtained diffusion
approximations of the M_t/M_t/1 queue and
observed that the approximations could be interpreted
as derivatives of the one-dimensional reflection map.
In this talk directional derivatives of multi-dimensional
reflection maps will be characterized and used
to obtain diffusion approximations of
a large class of non-stationary queueing networks.
The subtleties that arise in the multi-dimensional setting,
the peculiarities of the diffusion approximation
and the influence of network structure will be illustrated
via examples. Applications of the theory to study
time-dependent phenomena will also be discussed.
This is part of joint work with Avi Mandelbaum, Bill Massey
and Ward Whitt.
We consider a single link model of a telecommunications service provider that serves both wholesale and retail customers. Retail customers are 'ordinary' phone users, who have a fixed price and arrival rate. Wholesale customers contract in advance for a fixed quantity of bandwidth over a longer term (e.g. six months). The arrival rate of wholesale customers depends on the posted price according to a known demand function. We consider the problem of dynamically choosing the wholesale price over an interval [0,T] leading up to the beginning of a wholesale contract interval. The objective is to maximize the total expected revenue from both wholesale and retail customers (only bandwidth that has not been sold to wholesale customers is available for retail customers).
When the bandwidth on the link is large, which is typically true in practice, an asymptotic approach can be used to obtain good (asymptotically optimal) dynamic pricing policies. Fluid level (strong law of large numbers) results yield an 'open loop' policy that charges a constant price for wholesale bandwidth throughout the interval [0,T]. Under reasonable conditions this fluid optimal price leads to a 'critically loaded' system: to leading order, the bandwidth left over for the retail system is exactly enough to meet the retail demand. Under critical loading a diffusion (central limit theorem) correction to the fluid can be obtained. The solution of the resulting diffusion control problem provides a simple, explicit, closed-loop (feedback) control for the original dynamic pricing problem.
Consider a closed queueing network with N servers (nodes, queues) and M customers. These customers are in the queues and are served according to the FIFO discipline at each node. The service times at each queue form i.i.d.
sequence with the (fixed) distribution function F(x). The class of networks under consideration is specified by the following natural routing rule: after being served by the server the customer becomes the last one in the quue to either of nodes n = 1, ..., N with equal probability P(n) = 1/N.
We study the thermodynamical limit for a mean field model describing how this 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. It was proved earlier [F. Karpelevich, A. Rybko, ITP 2000] that the quotient process on the space of orbits of G-action converges in thermodynamical limit (when the number of servers and the number of customers tends to infinity) to the limit deterministic dynamical system. The main new result of joint work with S. Slosman is the theorem about the global convergence of this infinite dimensional dynamical system to its unique stable point. The stable point corresponds to the invariant measure of M/Gl/1 queue. This statement easily implies "Poissonian Hypothesis" for this class of networks.
We will illustrate the use of simple
delay differential equation models for designing congestion controllers
and active queue management schemes in the Internet.
In the first part of the talk, we will present an
application of these models by designing an active queue management
algorithm called the Adaptive Virtual Queue that leads to low-loss operation
while achieving high utilization at the links.
In the second part of the talk, we will show that the
deterministic models are appropriate even for networks
with stochastic disturbances.
Joint work with Srisankar Kunniyur, Supratim Deb and Sanjay Shakkottai.
Generalized switch is a model of a queueuing system
where servers are flexible, interdependent, and have randomly
varying service capabilities. It includes as
special cases the model of multiuser data scheduling over a wireless medium,
the input-queued cross-bar switch model, and a discrete time version
of a parallel server queueing system. Finite number N of input flows
are served in discrete time by a switch. Switch state m follows a finite
discrete time Markov chain. In each state m, the switch can choose a
scheduling decision k from a finite set K(m); each scheduling decision
has the associated vector of service rates at which queues are served.
We consider heavy traffic regime and study
the MaxWeight discipline which always chooses a decision
maximizing the sum of queue service rates weighted by their queue lengths.
It is shown that (under some non-degeneracy conditions),
MaxWeight causes system to "self-organize": queue lengths are kept in
certain proportions ("state space collapse") which are exactly those
allowing MaxWeight to minimize the system workload among all
disciplines. MaxWeight does this without "knowing" the flow input rates
or switch state statistics. The main message of this result is that
optimal controls of complex systems of flexible interdependent servers
is possible with simple parsimonious scheduling rules.
We consider adhoc wireless networks without basestation and wireline
infrastructure but nodes can act as relays for other nodes. The capacity
of such networks is limited by the mutual interference of concurrent
wireless transmissions. Gupta and Kumar have recently analyzed this
capacity in an analytical model of fixed ad-hoc networks, where nodes
are randomly located on a disk but are immobile. Their main result shows
that as the number of nodes n per unit area increases, the throughput
per node goes to zero like 1/sqrt{n}. In contrast, we show that when
the nodes are mobile, tha average long-term throughput per node can be
kept constant even when the number of nodes increases. The
performance improvement is obtained through the exploitation of the
time-variation of the users' channels due to mobility. While the
original result was shown for the case when each node has a stationary
ergodic mobility process with a uniform stationary distribution on the
disk, the same result continues to hold even when each node is
restricted to move on a different one-dimensional path within the
two-dimensional
space.
Joint work with M. Grossglauser and S. Diggavi.
We consider uncapacitated serial inventory systems with Markov-modulated
demand, and Markov-modulated, stochastic, but non-overtaking leadtimes.
We employ a novel approach, based on a
decomposition into a collection of single-item
single-customer problems that are essentially decoupled.
We show that this technique results in a very simple derivation of
existing results (optimality of state-dependent echelon basestock
policies), efficient computational algorithms, and several new
results.
Joint work with Alp Muharremoglu.
Today's Internet is composed of many interconnected autonomous networks
that operate independently according to their individual set of policies.
However, providing end-to-end quality of service (QoS) requires a joint
effort by all the networks. One approach used in practice is built
upon service level agreements (SLA). When using this approach, one network
offers others forwarding services with certain guarantees on QoS.
The concatenation of these SLAs then ensures end-to-end QoS for the end
users.
In this talk, we use voice over IP to illustrate how measurement-based
admission control and SLAs can be designed to provide
end-to-end QoS in a dynamic, fully decentralized way. We then present a
game-theoretic model for the scheme to demonstrate its feasibility and some
of its interesting properties. We also show how this model can be
generalized into a framework for other types of services.
Joint work with Linhai He
J. M. Harrison (2000) has described a framework
for using formal diffusion approximations, called Brownian networks,
to address problems of performance analysis and control
in heavily loaded stochastic processing networks (SPNs). Harrison's
SPN model setup is very general, including as special cases,
multiclass queueing networks, networks with alternate routing capabilities,
and networks with simultaneous resource possession.
In utilizing this framework, one frequently needs to justify approximation
of an SPN operating under a given policy by a Brownian network operating
under an analog of that policy.
For multiclass queueing networks with certain service disciplines,
asymptotic behavior of balanced fluid models has been used by
various authors to
establish a property called state space collapse, which
validates the use of the Brownian
approximation for such networks.
For more general SPNs, investigation of the behavior of balanced fluid models
and of a related notion of state space collapse
are in the early stages of development.
In this talk, these aspects will be illustrated with examples.
In particular,
a model involving simultaneous resource possession will be discussed.
Under suitable assumptions, this model is equivalent in distribution
to an internet flow model where the notion of simultaneous
resource possession corresponds to entrainment of resources.
Based on joint work with Maury Bramson and Frank Kelly.
Neil O'Connell
Balaji Prabhakar
Kavita Ramanan
Marty Reiman
Alexander Rybko
R. Srikant
A.L.Stolyar
David Tse
John N. Tsitsiklis
Jean Walrand
Ruth Williams