Centre for Mathematical
Sciences
Wilberforce Road, Cambridge, CB3 0WB
Tel: (01223) 337958
Fax: (01223) 337956
Email: secretary@statslab.cam.ac.uk
All interested are welcome
We consider broadcasting a stream of data in an unstructured network. Broadcasting has been studied extensively for edge-capacitated networks. Since 1970, the only known optimal schemes have relied on centralized packing of edge-disjoint spanning trees [Edmonds, Lovasz, Gabow]. We prove that a simple decentralised algorithm gets arbitrarily close to the optimal broadcast rate, providing a new proof of Edmonds' theorem. I shall also discuss a new formulation of the problem, where capacities are at nodes. We study the delay that users must wait in order to playback the stream with a small number of skipped packets, and discuss the suitability of our algorithms for live video streaming. This is joint work with Laurent Massoulie, Christos Gkantsidis and Pablo Rodriguez.
A network with k servers and k Poisson input flows is considered. The dynamic routing is introduced where each queue can be served by two servers (a 'circular' system). It is shown that the large deviation of the waiting time in one of the queues is caused, most likely, by an overload of n queues, where n= 1,...,k is determined by the average load across the network and by the distribution of the service time of a task.
The talk will focus on two aspects of stochastic networks analysis:1. The product form representation for steady state probabilities for a network with a protocol of multipoint connection.
2.Monotonicity properties of the optimal policy minimising the sojourn time in a network with multi-server nodes.
Optimization of communication networks has recently witnessed an impressive growth of research activities. In addition to viewing networks as objects to be optimized, some of these works also view networks as optimizers themselves. In addition to "Design by Optimization", some recent results also demonstrate the principle of "Design for Optimizability". Indeed, more than a tool to solve for optimal resource allocation, optimization theory provides to networking applications all of the following: a modeling language for design, a reverse-engineering methodology for analysis, a theoretical foundation for architectural decisions, a quantitative basis for fairness and robustness, and even an indicator of flaws in engineering assumptions. Many of these new uses of optimization actually do not involve solving any problem optimally.
Reflecting upon the history of optimization-based solutions to congestion, collision, and interference in the last 15 years, this talk discusses the reach and limitation of network optimization. Then, drawing from recent results on open problems in stochastic utility maximization and Internet routing, this talk surveys the emerging trends that give many new meanings to the phrase Optimization of Networks and by Networks.
Semimartingale Reflecting Brownian Motions (SRBMs) living in the closures of domains with piecewise smooth boundaries are of interest in applied probability because of their role as heavy traffic approximations for stochastic networks. Modern applications such as bandwidth sharing and packet switches can yield stochastic network models and SRBM approximations that are more general than those associated with conventional multiclass queueing networks. In justifying the approximation of a stochastic network by an SRBM, a crucial step is the use of a perturbation result or invariance principle. In essence this implies that a process satisfying the definition of an SRBM, except for small random perturbations in the defining conditions, is close in distribution to an SRBM. Here we describe sufficient conditions for an invariance principle to hold for SRBMs in piecewise smooth domains. A crucial ingredient in the proof of this result is an oscillation inequality for solutions of a perturbed Skorokhod problem.Some applications of our results and open problems will be discussed.
This talk is based on a joint work with S Shlosman and A Vladimirov. We will consider a network of simple servers processing customers of various types. If we introduce some natural connection between servers, then they may stay synchronized after an arbitrary long time. This fact violates the Poisson Hypothesis, a property which is usually associated with large networks. Such a phenomenon is possible when the mean number of customers at every server is high enough; otherwise the network becomes de-syncronized, no matter what kind interaction between servers is considered. Thus, the mean number of customers plays here the same role as the temperature in Statistical Mechanics. We give a specific simple example of the above-type behavior, but we believe that the phenomenon we describe is fairly general.
Please see also Past Seminars.
Last updated 19-June-2007
Valid HTML (4.01 Transitional)