Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

SB38

3 - Analysis of Processor Sharing Queues via Relative Entropy Amber L. Puha, California State University-San Marcos, Department of Mathematics, 333 S. Twin Oaks Valley Road, San Marcos, CA, 92096-0001, United States, Ruth J. Williams In this talk, we discuss a new approach to studying the asymptotic behavior of fluid model solutions (formal functional law of large numbers limits) for critically loaded processor sharing queues. For this, we introduce a notion of relative entropy associated with measure valued fluid model solutions. This approach is developed with idea that similar notions involving relative entropy may be helpful for understanding the asymptotic behavior of critical fluid model solutions for stochastic networks operating under protocols naturally described by measure- valued processes. 4 - Ergodicity Properties of Levy-driven SDEs Arising from Multiclass Many-server Queueing Networks Guodong Pang, Penn State University, 310 Leonhard Bldg., Industrial and Manufacturing Engineering, University Park, PA, 16802, United States We study the ergodic properties of multidimensional piecewise Ornstein- Uhlenbeck processes with jumps, arising in multiclass many-server queues with bursty arrivals and/or asymptotically negligible service interruptions in the Halfin- Whitt regime. The SDEs have a piecewise linear drift, and are driven by either (1) a Brownian motion and a pure-jump Levy process, or (2) an anisotropic Levy process with independent one-dimensional symmetric alpha-stable components, or (3) an anisotropic Levy process as in (2) and a pure-jump Levy process. We identify conditions on the parameters in the drift and the Levy measure which result in polynomial and/or exponential ergodicity. n SB38 North Bldg 225B Recent Developments in Load-balancing Algorithms Sponsored: Applied Probability Sponsored Session Chair: Anton Braverman, Northwestern University, Evanston, IL, 60208, United States 1 - Asymptotically Optimal Load Balancing Topologies Debankur Mukherjee, Eindhoven University of Technology, Heeghtakker 78A, Eindhoven, 5625SW, Netherlands, Sem Borst, Johan S. van Leeuwaarden We consider a system of N servers inter-connected by some graph topology GN. Tasks with unit-mean exponential service times arrive at the various servers as independent Poisson processes of rate ?. Each incoming task is assigned to whichever server has the smallest number of tasks among the one where it appears and its neighbors in GN. This model has been extensively investigated via mean-field techniques in the case GN is a clique. For arbitrary graph, mean-field techniques breakdown, complicating the analysis. In this talk we will investigate how much sparsity in the graph can be allowed maintaining the asymptotic behavior of a clique on a fluid and a diffusion scale. 2 - Stein’s Method for Mean-field Approximations Lei Ying, Arizona State University, Chandler, AZ, United States Mean-field analysis is an analytical method for understanding large-scale stochastic systems such as large-scale data centers and communication networks. Most existing mean-field models concerned the light-traffic regime where the load of the system is strictly less than one and is independent of the size of the system. To overcome this difficulty of traditional mean-field models, this paper views the equilibrium point of the mean-field model, called a mean-field solution, simply as an approximation of the stationary distribution of the finite-size system, and uses Stein’s method to quantifies the approximation errors. 3 - A Simple Steady-State Analysis of Load Balancing Algorithms in the Sub-Halfin-Whitt Regime Xin Liu, Arizona State University, Tempe, AZ, 85281, United States, Lei Ying This work studies a class of load balancing algorithms for many-server systems assuming finite buffer. We focus on the steady-state performance of load balancing algorithms in the heavy traffic regime (called sub-Halfin-Whitt regime). We establish a sufficient condition under which the probability that an incoming job is routed to an idle server is one asymptotically. The class of load balancing algorithms that satisfy the condition includes join-the-shortest-queue (JSQ), idle- one-first (I1F), join-the-idle-queue (JIQ), and power-of-d-choices (Pod) with certain d. The proof of the main result is based on the framework of Stein’s method. A key contribution is to use a simple generator approximation based on state space collapse.

4 - Steady-state Analysis of the Join the Shortest Queue Model in the Halfin-Whitt Regime Anton Braverman, Northwestern University, Kellogg Global Hub, Room 4171, Evanston, IL, 60208, United States This talk will focus on the generator comparison framework. This framework also goes by the name of the Stein method framework or the drift-based fluid Lyapunov function approach, and has received significant attention over the past few years as a tool for proving rates of convergence to steady-state fluid and diffusion approximations. I focus on the Join the Shortest Queue (JSQ) model in the Halfin-Whitt regime. This is an example of a ‘clean’ application of the generator comparison framework, which lets one push the boundaries of what the framework can do. Two specific points include a novel ‘trick’ to deal with state space collapse, and an approach to prove exponential ergodicity for Markov processes. Large-scale Data Centers Sponsored: Applied Probability Sponsored Session Chair: Siva Theja Maguluri, ISyE Ba Tech,Atlanta, GA, 30339, United States 1 - Adaptive Matching for Expert Systems with Uncertain Task Types Virag Shah, Stanford University, Stanford, CA, United States, Lennart Gulikers, Laurent Massoulie, Milan Vojnovic Online two-sided matching markets such as Q&A forums (e.g. StackOverflow, Quora) and online labour platforms (e.g. Upwork) rely on the ability to propose adequate matches based on imperfect knowledge of the two parties to be matched. This prompts a question: Which matching algorithms can, in the presence of uncertainty, lead to efficient platform operation? To this end, we develop a model of a task-server matching system. We give a necessary and sufficient condition for an incoming stream of tasks to be manageable by the system. We identify an optimal policy and show that it outperforms a natural greedy policy. We confirm our theoretical findings with experiments based on logs of a StackOverflow forum. 2 - Small-scale Markets for Bilateral Resource Trading in the Sharing Economy Srinivas Shakkottai, Texas A&M University, Dept. of ECE, College Station, TX, United States, Bainan Xia, Vijay Subramanian We consider a small-scale market for agent-to-agent resource sharing, in which each agent could either be a server (seller) or a client (buyer). In every time period, a server has resources that any client could consume, and randomly gets matched with a client. During each transaction, the server gets money and the client gets resources. We model the system using a Mean Field Game approach and prove the existence of the Mean Field Equilibrium, which can achieve an almost 100% trade ratio. Finally, we carry out a simulation study motivated by an agent-to-agent computing market, and a case study on a proposed photovoltaic market, and show the designed market benefits both individuals and the system as a whole. 3 - Integrating Online Learning and Adaptive Control in Queueing Systems with Uncertain Payoffs Xiaojun Lin, Professor, Purdue University, 465 Northwestern Ave., EE Building, West Lafayette, IN, 47907, United States, Wei-Kang Hsu, Jiaming Xu, Mark R. Bell Consider a queueing system where un-labeled clients arrive according to a stochastic process and each client brings a random number of tasks. As tasks are assigned to servers, they produce client/server-dependent random payoffs. The goal of the system is to maximize the expected payoff per unit time subject to the servers’capacity constraints. However, both the statistics of the dynamic client population and the client-specific payoff vectors are unknown to the operator. We design task-assignment policies that carefully integrate adaptive control (of the queueing system) with online learning (of the clients’ payoff vectors) to achieve low regret in finite time. 4 - Risk-sensitive Optimal Control of Stochastic Networks Rahul Singh, Intel, Santa Clara, CA, United States We consider the problem of designing risk sensitive optimal control policies for scheduling in a stochastic network. A single server provides service to N queues. Processing incurs a cost of C units, while completion yields a reward of R units. The queues have a buffer capacity of B units, and are penalized L units if a job is lost due to buffer overflow. We show that the risk-sensitive optimal control policy for such a simple set-up is of threshold type. n SB39 North Bldg 226A

44