Grad Seminar: Wanyi Chen, Eric Friedlander
Dynamic Decision Making In A Queueing System With Secondary Service
Motivated by operational practices in emergency departments, we consider a queueing model where each job is one of two types. Type 1 jobs need only a primary service given by a single server. Type 2 jobs need an additional secondary service. Secondary service is conducted by infinitely many servers. Primary servers cannot serve a new job until secondary service of a job is over. Jobs incur waiting costs and there is an option of starting primary and secondary services together with an extra cost. The decision is whether or not to use that option for each job given the probability that the job is type 1. We show the optimal policy is of threshold-type and numerically test the performance of heuristic methods.
Diffusion Approximations for Load Balancing Mechanisms in
Cloud Storage Systems
Analysis of large-scale communication networks (e.g. ad hoc wireless networks, cloud computing systems, server networks etc.) is of great practical interest. The massive size of such networks frequently makes direct analysis intractable. Asymptotic approximations using hydrodynamic and diffusion scaling limits provide useful methods for approaching such problems. In this talk, we explore an application of these approximation techniques to a model for load balancing in a large, cloud-based, storage system. In these types of systems, files are often coded across several servers to improve reliability and retrieval speed. We consider a network of n servers storing a set of files using the Maximum Distance Separable (MDS) code where file requests are routed using the Batch Sampling routing scheme (cf. Li, Ramamoorthy, Srikant (2016)). Specifically, each file is stored in equally sized pieces across L servers such that any k pieces can reconstruct the original file. When a request for a file is received, the dispatcher routes the job into the k-shortest queues among the L for which the corresponding servers contain the file being requested. We establish a law of large numbers and a central limit theorem as the system becomes large (i.e. n → ∞). Since the queues have infinite buffers, the state descriptors are infinite dimensional. In particular, the diffusion limit is described in terms of a Hilbert space valued stochastic differential equation driven by a cylindrical Brownian motion. The well studied Power-of-d routing scheme, also known as the supermarket model, is a special case of the model considered here. This is joint work with Amarjit Budhiraja