DIMACS/CCICADA Workshop on Stochastic Networks: Reliability, Resiliency, and Optimization

October 12 - 13, 2011
DIMACS Center, CoRE Building, Rutgers University

Endre Boros, RUTCOR, endre.boros at rutcor.rutgers.edu
Andras Prekopa, RUTCOR, prekopa at rutcor.rutgers.edu
Michael Tortorella, RUTCOR, mtortore at rutcor.rutgers.edu
Presented under the auspices of the DIMACS Special Focus on Algorithmic Foundations of the Internet, the DIMACS Special Focus on Cybersecurity and The Command, Control, and Interoperability Center for Advanced Data Analysis (CCICADA).


Yuliy Baryshnikov, University of Illinois

Title: Gordon-Loeb model of IT security investment and the (1/e)-rule

A simple and versatile model proposed in 2002 by Gordon and Loeb gives a way to estimate the levels of investment into IT security by an enterprise. Several deficiencies of the model have been identified since, endangering its main quantitative corollaries. In this talk I present a general axiomatic framework which allows one to deduce the main premises of the Gordon-Loeb model from first principles, and show that within this refined framework the most interesting corollary of the Gordon-Loeb model - (1/e) fraction of the expected loss as the upper bound on the IT security investment - is valid.

Tayfur Altiok, Department of Industrial and Systems Engineering, Rutgers University
Presenter: Amir Ghafoori, PhD student, Department of Industrial and Systems Engineering, Rutgers University

Title: Performance Analysis and Design of Tandem Queues with Blocking

Tandem systems are abundent in production systems and supply chains. Their exact analysis is quite difficult. A decomposition approximation is presented for systems with phase-type service times to analyze their performance. The approach builds upon the concepts of starvation and blocking. An optimization algorithm is constructed exploiting the decomposition approach to allocate buffer capacities or target inventory levels.

Melike Baykal-Gursoy, Rutgers University

Title: Queues in Random Environment and Some Probabilistic Programming Models for Incident Management

We will first present some queueing models with modulated arrival and service processes, and relate these models to the traffic flow interrupted by incidents. We will show that these models demonstrate the stochastic decomposition property, and derive the stationary distribution of the number in the system. These models are then utilized in estimating the travel times. In the second part of my presentation, we will discuss mathematical programming models with probabilistic constraints in order to address incident response and resource allocation problems for the planning of traffic incident management operations. We present a case study for the incident resource allocation problem to demonstrate the use of the proposed model in a real-world context.

Carol Davids, Illinois Institute of Technology

Title: TBA

Yi Mao, University of Tennessee

Title: Dynamical Analysis of Networks: How to Identify Important Nodes with Application to Protein Engineering

Over the course of evolution, protein structure has been optimized for its function. The relationship between protein structure and function has been one of the most intensively studied subjects in molecular biology. One issue of particular importance is how to identify functionally important components in a large heterogeneous and nonlinear system such as proteins. Here I use an elastic network model to represent proteins and explore the linkage between protein dynamics and function. An elastic network model is a mean-field and pairwise approximation of multi-body problems, and mathematically it yields a closed and compact analytic solution for protein dynamics (namely the fluctuation and covariance). There are several analysis tools that can be used to extract functionally important dynamical information from this model: normal modes analysis, clustering analysis, and perturbation approach. I will discuss them in addressing the major challenge in protein engineering: how to identify the sites that may change the overall behavior of the system.

Bill Massey, Princeton University

Title: Fair Scheduling for Dynamic Rate, Weighted Processor Sharing Queues

Consider a weighted processor sharing queue with non-homogeneous Poisson arrivals and general distributions for both sets of i.i.d. service and abandonment times. We want to determine a profit optimization policy over a fixed time interval with the additional constraint of fairness, where a predetermined percentage of serviced jobs is assigned to each customer class.

Using asymptotic methods, we can scale the stochastic model such that it converges to a limiting fluid model that is a deterministic, dynamical system. Using the methods of optimal control for such systems, we can then develop a profit optimal, class weighting schedule, for the original stochastic queueing system. The resulting policy is a dynamic rate analog to the c-mu rule.

This is joint work with Robert C. Hampshire of Carnegie Mellon University

Benedetto Piccoli, Rutgers University

Title: Heterogeneous models for nonlinear flows on networks

A wealth of models are available for network flows, both continuous and discrete. More recently, continuous pde models and mixed ones were proposed especially for vehicular traffic, data networks, and supply chains. We review some recent literature and describe some possible use of such models in applications.

András Prékopa and Merve Ünüvar, RUTCOR

Title: Single Commodity Stochastic Network Design under Probabilistic Constraints with Discrete Random Variables

Single commodity networks are considered, where demands at the nodes are random. The problem is to find minimum cost optimal capacities at the nodes and arcs subject to the constraints that all demands should be met on a prescribed probability level (reliability constraint) and some constraints on the capacities should be satisfied. The reliability constraint is formulated in terms of Gale-Hoffman feasibility inequalities but their number is reduced by elimination technique. The concept of a p-efficient point is used in a smart way to convert and then relax the problem into LP, Two solution techniques are presented depending on if all p-efficient points are known or are simultaneously generated with the solution of LP. The joint distribution of the demands is used to obtain the p-efficient points for all non-eliminated stochastic inequalities and the solution of a knapsack problem is used to generate each new p-efficient point. The model can be applied to interconnected power systems, flood control networks, design of shelter and road capacities in evacuation, parking lot capacities, financial networks, etc. Numerical examples are presented.

András Prékopa and Olga Myndyuk, RUTCOR

Title: Single Commodity Stochastic Network Design under Probabilistic Constraint with Continuously Distributed Random Variables

Single commodity networks are considered where demands are continuously distributed random variables. The problem is to find minimum cost optimal arc and node capacities subject to the constraint that all demands are met with large probability. The reliability constraint is formulated in the terms of Gale-Hoffman feasibility inequalities, the number of which is reduced by Prékopa-Boros elimination based on topology of the network. One of the key methods in the solution algorithm is a smart representation of the p-quantile or multivariate Value at Risk of the random vector involved, where as the boundary of the c.d.f. of the demand vector already provides us with the boundary of the entire random vector. The other one is the application of a hybrid algorithm that provides us alternating inner and outer approximations of the set of feasible solutions with the lower and upper bounds at each iteration. An illustrative example will be presented.

Jose Ramirez-Marquez, Stevens

Title: Stochastic Consideration in Systems Resilience Engineering

This talk will describe recent advances in Resilience Engineering. It will start by describing the concept of resilience from a systems perspective and then describe some of the metrics that have been used and mis-used to quantify resilience. The talk will then move on to describe mathematically system resilience as a stochastic time dependent variable. The relationships among resilience, reliability, and availability will also be identified along with quantitative methods that can be used to quantify network resilience. Finally, the talk will describe relevant optimization models when considering Resilience.

Marty Reiman, Bell Laboratories

Title: A Stochastic Programming Based Approach to Assemble-to-Order Inventory Systems

The assemble-to-order system is a classical model in inventory theory, where multiple components are used to produce multiple products. All components are obtained from an uncapacitated supplier after a deterministic (component dependent) lead time, while demand for the products is random. The optimal control for this system (where the goal is to minimize the long run average inventory + backlog cost) is not known except for very special cases. In this talk I will describe an approach to solving this problem using a particular multi-stage stochastic linear program with complete recourse, which we have shown provides a lower bound on achievable cost in the inventory system. I will also describe how to translate the solution of this stochastic program into a control policy for the inventory system in some special cases. Finally, I will provide a set of sufficient conditions under which a control policy achieves the lower bound (and is hence optimal), and show some examples where this occurs.

(Based on joint work with Mustafa Dogru and Qiong Wang)

Aleksandr Stolyar, Bell Labs, D. Gamarnik, MIT E. Yudovina, Cambridge

Title: Stationary distribution of large-scale queueing systems in Halfin-Whitt regime: Exponential bounds

We consider systems consisting of one or several server pools, each containing large number of identical servers, and multiple classes of input flows; such models appear e.g. in cloud computing or customer contact centers.The Halfin-Whitt asymptotic regime is when system capacity exceeds its load by O(sqrt{r}), where r is the system size (total number of servers). The diffusion-scaled process measures O(sqrt{r}) deviations of state from the optimal operating point. Establishing tightness of stationary distributions of diffusion-scaled processes, as r increases to infinity, is a challenging problem. We prove tightness -- moreover, uniformly bounded exponential moments -- in two special cases of interest.

Michael Tortorella, RUTCOR

Title: Performance Analysis on a Shoestring

Product-form queueing network models mostly require Poisson arrivals and/or exponential service times. Many realistic networks lack these properties, but performance analysis of such networks is still needed. This talk explores what you can do if all you know is that routing in the network is Markovian, with no restrictions on arrival processes or service times. Naturally, many performance analyses are not available in this case, but some useful results can still be obtained. We also explore the approximation of address-based routing by Markovian routing.

Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on October 10, 2011.