Delay-optimal scheduling for some Input-Queued Switches

Abstract

The complexity of computer systems, networks and applications, as well as the advancements in computer technology, continue to grow at a rapid pace. Mathematical analysis, modeling and optimization have been playing, and continue to play, an important role in research studies to investigate fundamental issues and tradeoffs at the core of performance problems in the design and implementation of complex computer systems, networks and applications. On June 14, 2016, the 18th Workshop on MAthematical performance Modeling and Analysis (MAMA 2016) was held in Antibes Juan-les-Pins, France, sponsored by ACM SIGMETRICS and IFIP WG 7.3, and held in conjunction with SIGMETRICS/Performance 2016. This workshop seeks to bring together researchers working on the mathematical, methodological and theoretical aspects of performance analysis, modeling and optimization. It is intended to provide a forum at SIGMETRICS/Performance conferences for talks on early research in the more mathematical areas of computer performance analysis. These talks tend to be based on very recent research results (including work in progress) or on new research results that will be otherwise submitted only to a journal (or recently have been submitted to a journal). Thus, part of the goal is to complement and supplement the SIGMETRICS/Performance Conference program with such talks without removing any theoretical contributions from the main technical program. Furthermore, we continue to experience the desired result of having abstracts from previous MAMA workshops appear as full papers in the main program of subsequent SIGMETRICS, Performance and related conferences. All submissions were reviewed by at least 4 members of the program committee, from which a total of 15 were selected for presentation at the MAMA 2016 workshop. This special issue of Performance Evaluation Review includes extended abstracts relating to these presentations (arranged in the order of their presentation), which cover a wide range of topics in the area of mathematical performance analysis, modeling and optimization. The study of Antunes et al. presents a method to detect switches between stationary intervals as part of a probing strategy to estimate time-dependent traffic intensity. Gast provides a mean-field approximation of a system of interacting objects and constructs a Lyapunov function for this model, with applications to caching. The study of Domingues et al. focuses on search and placement in tiered cache networks, proposing and investigating a simple and flexible cache network architecture. Cai et al. consider information spreading forensics, proposing a framework for estimating information spread rates and establishing properties of this framework. The study of Gelenbe introduces a model of mutually influencing individuals who hold one of two opinions about some matter and shows certain properties of this model. Doncel et al. consider the question of whether mean-field games are the limit of finite stochastic games, showing that this convergence does not hold in general. The study of Feinberg and Liang describes the structure of optimal policies for discounted periodic-review single-commodity total-cost stochastic inventory control problems with fixed ordering costs. Fricker et al. investigate the performance of a system under simple resource adaptation algorithms based on the downgrading of requests when certain conditions hold. The study of Lu et al. considers dynamic resource allocation of computing resources to multiple workload classes under uncertainty within the context of a mathematical finance framework. Sermpezis and Dimitropoulos seek to analytically examine the effects of routing centralization on the performance of inter-domain routing and the convergence time of BGP. The study of Gardner et al. proposes a model of redundancy, in which jobs send redundant copies to d servers chosen uniformly at random, and obtains expressions for mean response time in such systems. Mukherjee et al. construct a coupling to bound the difference in queue length processes between the join-the-shortest-queue and power-of-d load balancing schemes. The study of Juneja and Manjunath considers the problem of when to dynamically join the queue in a system that allows customers in the lounge to know the queue, lounge and server occupancy at all times. Stolyar investigates a service system with packing constraints and heterogeneous servers, establishing theoretical properties for two variants of the model in the large-scale asymptotic regime. The study of Lu et al. considers a generalization of the input-queued switch scheduling problem under a linear cost function of delay for each queue and derives optimal solutions and structural properties. I sincerely thank each of the speakers and co-authors for their presentation and participation at the MAMA 2016 workshop, as well as each of the other workshop attendees. I also sincerely thank my fellow program committee members: I. Adan, Y. Baryshnikov, S. Borst, G. Casale, C.S. Chang, E. Coffman, J. Dai, E. de Souza e Silva, A. Dieker, N. Duffield, D. Eager, E. Feinberg, D. Gamarnik, A. Ganesh, D. Gaver, R. Gibbens, L. Golubchik, P. Harrison, A. Jean-Marie, P. Key, G. Latouche, J. van Leeuwaarden, Z. Liu, Y. Lu, J. Lui, M. Mandjes, R. van der Mei, P. Momcilovic, P. Nain, D. Nicol, S. Núñez-Queija, A. Proutiere, A. Radovanovic, K. Ramanan, P. Robert, M. Sharma, E. Smirni, R. Srikant, S. Stolyar, P. Taylor, D. Towsley, B. Van Houdt, A. Wierman, C. Xia, D. Yao, A. Zeevi and B. Zwart. Without all the work and support from both of these groups of people, the MAMA 2016 workshop would not have been possible. I also thank ACM SIGMETRICS and IFIP WG 7.3 for all of their support, and Nidhi Hegde for all of her assistance and support with this special issue of PER.