Queuing Theory for Emerging Classical and Quantum Systems
Workshop @ IFIP Performance 2023
November 17, 2023
Workshop @ IFIP Performance 2023
November 17, 2023
Queuing theory plays an important role in the design and performance evaluation of computer and communication systems. In recent years, it has been observed that several emerging systems demand analysis of new queuing models for understanding and improving their performance. For example, efficient design and operation of modern data centres require carefull consideration of the complex processing requirements of jobs as well as the connections among the servers. Quantum information systems, on the other hand, process information according to the laws of quantum mechanics. Designing efficient scheduling and resource management algorithms for quantum systems therefore requires incorporating the laws of quantum physics into queuing models.
The aim of this workshop will be to discuss queuing theoretic problems originating from both classical and quantum systems. We plan to bring together prominent researchers working on both areas to enable a discussion of potential applications of queuing theory for advances in the design, modeling and performance evaluation of emerging networked systems.
Mor Harchol-Balter (CMU)
Don Towsley (UMass)
9:00 am - 9:05 am: Welcome
9:05 am - 9:55 am: Keynote Talk 1
Speaker:
Mor Harchol Balter (Carnegie Mellon University)
Title:
Queueing Models for Today's Data Center Jobs
Abstract:
Most queueing models assume that a job runs on a single server. But this one-server-per-job model is not a good representation of today's compute jobs.
A typical data center job today occupies multiple cores concurrently, often thousands of cores. We refer to a job that concurrently occupies multiple cores as a multiserver job. Unfortunately, very little is known about response time in multiserver job queueing models. We present the first results on response time for multiserver job queueing models. In particular, we propose a new scheduling policy for multiserver jobs, called ServerFilling, and bound its response time.
We also consider today's parallel speedup jobs, that can run on any number of cores, but whose speed depends on the number of cores on which the job is run. Here it is even more complicated to understand how to best share a limited number of cores among a stream of jobs, each governed by a different speedup function. We discuss some recent optimality results in this nascent area.
Bio:
Mor Harchol-Balter is the Bruce J. Nelson Professor of Computer Science at Carnegie Mellon. She received her Ph.D. from U.C. Berkeley in 1996 under the direction of Manuel Blum. She joined CMU in 1999, and served as the Head of the PhD program from 2008-2011. She is the SIG Chair for ACM SIGMETRICS. She is a Fellow of both ACM and IEEE, a recipient of the McCandless Junior Chair, the NSF CAREER award, and several teaching awards, including the Herbert A. Simon Award and Spira Teaching Award. Mor's work focuses on designing new resource allocation policies, including load balancing policies, power management policies, and scheduling policies, for distributed systems. Mor is heavily involved in the SIGMETRICS / PERFORMANCE research community where she has received many paper awards (INFORMS George Nicholson Prize 22, SIGMETRICS 21, SIGMETRICS 19, PERFORMANCE 18, INFORMS APS 18, EUROSYS 16, MASCOTS 16, MICRO 10, SIGMETRICS 03, ITC 03, SIGMETRICS 96). She is the author of two popular textbooks, both published by Cambridge University Press: Performance Analysis and Design of Computer Systems , which bridges Operations Research and Computer Science, and Introduction to Probability for Computing . She is also a recipient of dozens of Industrial Faculty Awards including multiple awards from Google, Microsoft, IBM, EMC, Facebook, Intel, Yahoo!, and Seagate. Mor is best known for her enthusiastic keynote talks and her many PhD students, almost all of whom are professors at top academic institutions.
9:55 am - 10:35 am: Invited Talk 1
Speaker:
Debankur Mukherjee (Georgia Tech)
Title:
Mean-Field analysis for load balancing on spatial graphs
Abstract:
The analysis of large-scale, parallel-server load balancing systems has relied heavily on mean-field analysis. A pivotal assumption for this framework is that servers are exchangeable. However, modern datacenters have data locality constraints, such that tasks of a particular type can only be routed to a small subset of servers. An emerging line of research, therefore, considers load balancing algorithms on bipartite graphs where vertices represent task types and servers, respectively. In this talk, I will present a novel coupling-based approach to establish mean-field approximation for a large class of graphs which includes spatial graphs. The method extends the scope of mean-field analysis far beyond the classical full-flexibility setup.
Joint work with Daan Rutten.
Bio:
Debankur Mukherjee is the Leo and Louise Benatar Early Career Professor and Assistant Professor in the H. Milton Stewart School of Industrial and Systems Engineering at the Georgia Institute of Technology. Before joining Georgia Tech in 2019, he was a Prager assistant professor for a year in the Division of Applied Mathematics at Brown University. Debankur got his Ph.D. in Stochastic Operations Research from the Eindhoven University of Technology in the Netherlands. Debankur’s research spans the area of applied probability, at the interface of stochastic processes and computer science, with applications to performance analysis, online algorithms, and machine learning. His primary focus is to develop a foundational understanding of the challenges that arise in large-scale systems, such as data centers and cloud networks. His work was a finalist in the INFORMS JFIG paper competition in 2022 and INFORMS George Nicholson Student Paper Competition 2023 and received the Best Paper Award at ACM SIGMETRICS 2023 and the Best Student Paper Award at ACM SIGMETRICS 2018. His research has been funded by the NSF and he is currently serving on the editorial boards of Stochastic Systems, QUESTA, and Stochastic Models.
10:35 am - 11:15 am: Invited Talk 2
Speaker:
Javad Ghaderi (Columbia University)
Title:
Near-optimal packet scheduling with end-to-end deadline constraints in multihop networks
Abstract:
Scheduling packets with end-to-end deadline constraints in multihop networks is an important problem that has been notoriously difficult to tackle. Recently, there has been progress on this problem in the worst-case traffic setting with the objective of maximizing the weighted sum of packets delivered within their deadlines. The proposed algorithms were shown to achieve Ω(1/log(𝐿)) approximation if the minimum link capacity in the network is C= Ω(log(𝐿)), where 𝐿 is the maximum length of any packet's route in the network (which is bounded by the maximum deadline). However, such guarantees can be quite pessimistic due to the worst-case traffic assumption which may not accurately reflect real-world settings. In this work, we show that it is possible to design algorithms that attain a constant approximation by relaxing the worst-case traffic assumption. In fact, in stochastic traffic settings, such as i.i.d. packet arrivals, it is possible to design near-optimal, (1 − 𝜖)-approximation algorithms if C=Ω(log(L/ϵ)/ϵ^2). To the best of our knowledge, this is the first result that shows this problem can be solved near optimally under nontrivial assumptions on traffic and links' capacity. We further generalize our assumptions and provide extended simulations using real network traces that show that our algorithms indeed outperform the worst-case-based algorithms in practical settings. The techniques can be further combined with greedy or fractional graph coloring algorithms to provide constant, or near-optimal, approximation algorithms for multihop wireless networks with general interference graphs.
Bio:
Javad Ghaderi is an Associate Professor of Electrical Engineering at Columbia University. His research interests include algorithms, optimization, and stochastic processes with application to wireless networks and data centers. He received his B.Sc. from the University of Tehran, Iran, in 2006, M.Sc. from the University of Waterloo, Canada, in 2008, and Ph.D. from the University of Illinois at Urbana-Champaign in 2013. He spent a one-year Simons Postdoctoral Fellowship at the University of Texas at Austin before joining Columbia. He is a recipient of several awards, including Best Student Paper Finalist Award at ACC 2013, Best Paper Award at ACM CoNEXT 2016, NSF CAREER Award in 2017, Best Student Paper Award at IFIP Performance 2020, and Best Paper Award at IEEE INFOCOM 2020.
11:15 am - 11: 55 am: Invited Talk 3
Speaker:
Benny Van Houdt (University of Antwerp)
Title:
Two flavors of join-idle-queue load balancing
Abstract:
Join-Idle-Queue (JIQ) Load Balancing is an effective policy to achieve high performance in large systems with limited communication costs. Under JIQ servers that become idle add place token holding their id at a random dispatcher. Dispatchers select a random token for each incoming job and assign the job to the server id of the token. When a dispatcher runs of out tokens, it assigns any incoming job to a random server. In this talk we explain that JIQ comes in two flavors: with and without token withdrawals, depending on whether servers withdraw their token when receiving a job from another server. We explain why the original large scale system analysis mixes these two flavors and discuss asymptotically exact models for both.
Bio:
Benny Van Houdt is a professor at the department of Mathematics and Computer Science at the University of Antwerp where he also obtained his Phd in 2001. He has been a post-doctoral fellow of the FWO-Flanders from October 2001 until October 2007. He has been the Editor-in-Chief of the Performance Evaluation journal for 5 years (2018 - 2022), is a senior associate editor of ACM ToMPECS (since 2014) and is an editorial board member of Stochastic Models (since 2016). He has been a member of the editorial board of Operations Research Letters (2007-2017) and Performance Evaluation (2011-2017). He has been Technical Program Committee (TPC) co-chair of SMCtools 2006 (Pisa, Italy), MAM8 (Kerala, India), IFIP Performance 2014 (Torino, Italy) and QEST 2016 (Quebec City, Canada) and served on a number of TPCs including ACM Sigmetrics, IFIP Performance, IEEE MASCOTS, INFORMS APS, ITC, QEST, Valuetools, ASMTA, EPEW, etc. Benny is the (co)recipient of various awards including best paper awards at ACM Sigmetrics, IFIP Performance, ITC, QEST and Valuetools. He is an elected member and officer of the IFIP working group 7.3 on Computer System Modeling and has published papers in a variety of journals such as IEEE/ACM Trans. on Networking, IEEE Trans. on Information Theory, Communications, IEEE JSAC, IEEE/OSA JOCN, Performance Evaluation, QUESTA, Journal of Applied Probability, Adv. In Applied Probability, Operations Research Letters, INFORMS JOC, EJOR, Stochastic Models, Computer Networks, Naval Research Logistics, etc.
12:00 noon - 1:25 pm: Lunch Break
1:30 pm - 2:20 pm: Keynote Talk 2
Speaker:
Don Towsley (University of Massachusetts Amherst)
Title:
Queuing Models for Future Quantum Networks
Abstract:
Entanglement distribution in a quantum switch or end system is all about "matching" quantum states. As generating quantum states is highly probabilistic, this makes this a great candidate for simple Markovian models to which standard techniques widely used in the modeling of classical computing and communication systems can be applied. In this talk, I will present three case studies to illustrate this. The first consists of queuing models that for studying the aggregate capacity of a quantum network switch that serve pairs or sets of entangled qubits to end-nodes. The second case study focuses on the capacity region of a switch serving entanglement to pairs of users and a demonstration that a max-weight matching achieves this capacity. Quantum states are very fragile and highly sensitive to environmental noise. One of the biggest challenges in resource allocation in a quantum network is minimizing the impact of this noise. The third case study uses simple queuing models to capture the impact that different scheduling algorithms have on mitigating the impact of noisy memories on quantum teleportation.
Bio:
Don Towsley (Life Fellow, IEEE) received the B.A. degree in physics and the Ph.D. degree in computer science from the University of Texas 1971 and 1975. He is currently a Distinguished Professor with the College of Information and Computer Sciences, University of Massachusetts. He has held visiting positions at numerous universities and research labs, including the University of Paris VI, IBM Research, AT&T Research, Microsoft Research, and INRIA. His research interests include security, quantum communications, and networks and performance evaluation. He is a Corresponding Member of the Brazilian Academy of Sciences. He has received numerous IEEE and ACM awards, including the 2007 IEEE Koji Kobayashi Award, the 2007 ACM SIGMETRICS Achievement Award, and the 2008 ACM SIGCOMM Achievement Award. He has also received numerous best paper awards, including the IEEE Communications Society 1998 William Bennett Paper Award, the 2008 ACM SIGCOMM Test of Time Award, the 2018 ACM MOBICOM Test of Time Award, the 10+ Year 2010 DASFAA Best Paper Award, the 2012 ACM SIGMETRICS Test of Time Award, and five ACM SIGMETRICS best paper awards. He is the Co-Founder of ACM Transactions on Modeling and Performance Evaluation of Computing Systems and served as one of its first Co-Editor-in-Chiefs. He served as an Editor-in-Chief for the IEEE/ ACM Transactions on Networking and on numerous other editorial boards. He has served as the program co-chair for numerous conferences and on the program committees of many other. He is a Fellow of the ACM.
2:20 pm - 3:00 pm: Invited Talk 4
Speaker:
Stephen DiAdamo (Cisco)
Title:
The Impact of Quantum Memory Quality on Entanglement Assisted Communication
Abstract:
This presentation discusses entanglement-assisted communication, where quantum entanglement resources enable the transmission of classical information at an enhanced rate. We considered a scenario where entanglement is distributed ahead of time based on network traffic levels, and simulated a setting where idle nodes generate and store entanglement to later transmit messages at an accelerated rate. We analyzed this communication model using noise models for quantum memory in various scenarios, and extended our investigation to a quantum-enhanced distributed computing environment, where entanglement storage enhances data transmission rates for cooperative data processing. We proposed a protocol and demonstrated a distributed version of unsupervised clustering. Our results show that, for qubit channels, high rates of entanglement generation and modest storage requirements can surpass the classical limit with entanglement assistance. This presentation reviews these results.
Bio:
Stephen DiAdamo is a Research Scientist at Cisco Systems in the Cisco Quantum Lab group, focusing on quantum network design, protocols, and software. He has a bachelor’s of computer science from the University of Toronto, a master’s of mathematics, and a PhD of electrical engineering from the Technical University of Munich with a focus on quantum networks and simulation. He works in the Cisco Quantum Lab group and focuses primarily on designing architectures for quantum networks and developing applications for future quantum networks.
3:00 pm - 3:40 pm: Invited Talk 5
Speaker:
Eden Figueroa (Stony Brook University)
Title:
Building a long-distance quantum-capable internet testbed
Abstract:
Entanglement distribution in long-distance quantum internet networks must be stored and heralded in non-local quantum memories. These procedures are fundamental towards designing on-demand efficient distributed quantum protocols. In this talk, we will describe the fundamentals and first implementation of a layered
memory-assisted quantum network, designed to support quantum network services. We will also describe a quantum internet concept that integrates the abstract stack concepts of classical networking together with elementary quantum network services, allowing for its control and operation. Finally, we will present our implementation of a quantum-enabled internet network connecting quantum laboratories at Stony Brook University and Brookhaven National Laboratory, connected by 158 km of
inter-city field-deployed optical fibers.
Bio:
Prof. Eden Figueroa was awarded his BSc in Engineering Physics and his MSc in Optical Engineering at Monterrey Tech, Mexico in 2000 and 2002 respectively. From 2003 to 2008, he was a PhD student in the Quantum Technology Group of Prof. A. I. Lvovsky at the University of Konstanz in Germany and later at the Institute for Quantum Information Science at the University of Calgary, Canada. His PhD thesis entitled: “A quantum memory for squeezed light” was one of the first experimental implementations of quantum memory for quantized light fields. In 2009, he joined the Quantum Dynamics Group of Prof. G. Rempe at the Max-Planck-Institut für Quantenoptik in Garching, Germany where he worked in the implementation of quantum networks utilizing single-atoms trapped in high-finesse optical cavities. Starting in 2013, he has been the Group leader of the Quantum Information Technology group at Stony Brook University, where he has developed scalable room temperature quantum memories and entanglement sources, with the goal of developing the first working prototype of a quantum repeater network. Since Jan. 2019, Prof. Figueroa has also been a joint appointment with the Instrumentation Division at the Brookhaven National Laboratory. The collaboration between Stony Brook and BNL is developing the New York State Quantum Internet Testbed (NYSQIT), a first prototype of a quantum network distributing photonic entanglement over long distances across multiple nodes. Since August 2023, Prof. Figueroa has been the Director of the Center for Distributed Quantum Processing at Stony Brook and a Presidential Innovation Endowed Professor.
3:40 pm - 4:20 pm: Invited Talk 6
Speaker:
Sumeet Khatri (Freie Universität Berlin)
Title:
Optimal policies for quantum communication networks via Markov decision processes
Abstract:
The distribution of entanglement over long distances is a necessary component in the realization of quantum technologies such as quantum communication, quantum sensing, and distributed quantum computation. Long-distance entanglement distribution currently remains a challenge, however, due to limitations resulting from the fragility of quantum systems, such as photon losses, non-ideal measurements, and quantum memories with short coherence times. In this talk, I will present how Markov decision processes can be used to model and optimize protocols for linear chains of quantum repeaters, taking the current and near-future constraints of quantum devices into account. I will present optimal policies obtained both analytically as well using reinforcement learning, along with the practical guidance that such theoretical analyses have enabled. I will then discuss the prospect of extending these tools beyond linear chains of quantum repeaters to arbitrary quantum networks.
Bio:
Sumeet Khatri is a postdoctoral researcher in the group of Jens Eisert at the Freie Universität in Berlin. He works on topics in quantum information theory, including quantum communication, computing, metrology/sensing, and learning theory, with the goal of providing fundamental, theoretical guidance in order to help bring quantum technologies into real-world, widespread use. He completed his PhD in Physics in May 2021 at Louisiana State University. Prior to that, he earned his Bachelor's degree in Mathematical Physics and Master's degree in Physics at the University of Waterloo.
Registration fee:
- 100 USD for the workshop only
- 190 USD for students and 290 USD for faculty for the full conference
Registration fee is waived for invited speakers if they are only attending workshops