Home
Speakers
Schedule
Location and Directions
Hotel Information
Mayank Sharma
IBM
Title: Message Passing Algorithms for Stochastic Loss Networks
Abstract: Stochastic loss networks have been widely used and studied as models for diverse computer and communication systems in which different types of resources are used to serve various classes of customers involving simultaneous resource possession and non-backlogging workloads. Examples include telephone networks, cellular systems, broadband telecommunication networks, distributed computing, data centers, and multi-item inventory systems. Loss networks have even been used recently for resource planning within the context of workforce management in the information technology (IT) services industry, where a collection of IT service products are offered each requiring a set of resources with certain capabilities.
One of the most important objectives in analyzing such loss networks is to determine performance measures of interest, most notably the stationary loss probability for each customer class. The classical Erlang formula, which has been thoroughly studied and widely applied in many fields of research, provides the probabilistic characterization of these loss probabilities. More specifically, given a stochastic network and a multiclass customer workload, the formula renders the stationary probability that a customer will be lost due to insufficient capacity for at least one resource type.
We propose a novel message passing algorithm for estimating the stationary loss probabilities in stochastic loss networks based on structural properties of the exact stationary distribution; and prove exponentially fast asymptotic convergence of our algorithm to the exact answer. Further, we use a variational characterization of the stationary distribution to provide an alternative proof of an important result due to Kelly.