ACM SIGMETRICS / IFIP PERFORMANCE 2019
Phoenix, Arizona, USA
June 24-28, 2019
Reconfigurable Networks: Enablers, Algorithms, Complexity (ReNets)
Network traffic is growing explosively, and next-generation workloads, e.g., related to (distributed) machine learning and artificial intelligence, will further increase the amount of traffic headed for and between the world’s data centers. This quickly growing demand pushes today’s wide-area and datacenter networks towards their capacity limits. While over the years, several interesting new network architectures have been proposed to improve the efficiency and performance of such networks, especially in the context of data centers, these networks often have in common that their topology is fixed and cannot be reconfigured to the traffic demand they serve.
This tutorial discusses a different approach to operate networks: reconfigurable networks whose topology adjusts to the workload in an online manner. Reconfigurable networks are enabled by emerging optical technologies, allowing to quickly change the physical topology at runtime. This technology also introduces a vision of demand-aware networks which tap a new optimization opportunity: empirical and measurement studies show that traffic workloads feature spatial and temporal structure, which in principle could be exploited by reconfigurable networks. However, while the technology of such reconfigurable networks is evolving at a fast pace, these networks lack theoretical foundations: models, metrics, and algorithms - we have fallen behind the curve. The objective of this tutorial is to help bridge this gap, and introduce to the SIGMETRICS community a rich and potentially impactful research area, which touches many core topics of the conference. We first discuss technological enablers and report on motivating empirical studies. Our main focus in this tutorial then is on the new models and algorithmic challenges introduced by this field. In particular, we will review existing algorithms and complexity results, and highlight future research directions.
Ramakrishnan Durairajan is an Assistant Professor in the Department of Computer and Information Science at the University of Oregon, where he co-leads the Oregon Network Research Group (ONRG). Ram earned his Ph.D. and M.S. from the University of Wisconsin-Madison and his B.Tech. the College of Engineering, Guindy (CEG), Anna University. Ram's research has been recognized with NSF CRII award, UO faculty research award, best paper awards from ACM CoNEXT and ACM SIGCOMM GAIA and has been covered in the media (NYTimes, MIT Technology Review, Popular Science, Boston Globe, Gizmodo, Mashable, among others). In addition, his research on Internet topology has been named as "One of the 100 Greatest Innovations" and has won the "Best of What's New" (security category) from the Popular Science Magazine in 2017.
Klaus-T. Foerster is a Postdoctoral Researcher at the University of Vienna, working with Stefan Schmid. He was previously a PostDoc at Aalborg University, Denmark, and a Visiting Researcher at Microsoft Research, Redmond, USA, with Ratul Mahajan. He obtained his PhD degree (2016) from ETH Zurich, advised by Roger Wattenhofer. His research interests are in algorithms and complexity for networked and distributed systems.
Stefan Schmid is a Professor of Computer Science at the University of Vienna, where he is heading the Communication Technologies research group. He received his MSc (2004) and PhD (2008) from ETH Zurich, Switzerland. Subsequently, Stefan Schmid worked as postdoc at TU Munich and the University of Paderborn (2009). From 2009 to 2015, he was a senior research scientist at the Telekom Innovations Laboratories (T-Labs) in Berlin, Germany, and from 2015 to 2018, an Associate Professor at Aalborg University, Denmark. His research interests revolve around the fundamental algorithmic problems of networked and distributed systems.
The Power of SOAP Scheduling
Scheduling policies are at the heart of computer systems. The right scheduling policy can dramatically reduce response times, ensure fairness, provide class-based priority, etc., without requiring additional resources. While stochastic response time analysis of different scheduling policies has been the focus of thousands of theoretical papers, results are limited to analyzing a relatively small number of “simple” scheduling policies.
In this tutorial, we introduce the SOAP class of scheduling policies: Schedule Ordered by Age-based Priority. SOAP policies include almost all scheduling policies in the literature as well as infinitely many variants which have never been analyzed or even conceived. SOAP policies include the highly intractable SERPT policy (Shortest-Expected-Remaining-Processing-Time), as well as the famously complex Gittins Index policy. SOAP also includes a wide variety of “combination” policies, such as a policy that performs Shortest-Job-First on jobs with known size and Foreground-Background scheduling on jobs with unknown size, or a policy that is allowed to preempt jobs only when they hit certain ages.
The tutorial will teach attendees the following skills:
Mor Harchol-Balter is a Professor of Computer Science at CMU. She received her PhD from UC Berkeley in 1996. She joined CMU in 1999 and served as the Head of the PhD program from 2008-2011. Mor is a Fellow of the ACM and a Fellow of IEEE. She is a recipient of the McCandless Junior Chair, the NSF CAREER award, and several teaching awards, including the Herbert A. Simon Award and the Joel and Ruth Spira Award. She has received faculty awards from a dozen companies including Google, Microsoft, IBM, EMC, Facebook, Intel, Yahoo!, and Seagate. Mor’s work focuses on designing new resource allocation policies, including load balancing policies, power management policies, and scheduling policies. Mor is heavily involved in the SIGMETRICS research community, where she has received many best paper awards, and where she served as TPC Chair in 2007, as General Chair in 2013, and as the Keynote Speaker for 2016. She is also the author of a popular textbook, Performance Analysis and Design of Computer Systems, published by Cambridge University Press, which bridges Operations Research and Computer Science.
Ziv Scully is a graduate student in Computer Science at CMU advised by Mor Harchol-Balter and Guy Blelloch. He graduated from MIT in 2016 with a BS in Mathematics with Computer Science. He is the recipient of an NSF Graduate Fellowship and an ARCS Foundation scholarship. Ziv’s research focus is optimizing and analyzing computer systems and algorithms from a stochastic perspective, including job scheduling, load balancing, combinatorial optimization under uncertainty, and parallel algorithms. Two recent publications of his have been recognized with awards: “SOAP: One Clean Analysis of All Age-Based Scheduling Policies” was a finalist for the 2018 INFORMS APS Best Student Paper Prize, and “SRPT for Multiserver Systems” won the Best Student Paper Award at PERFORMANCE 2018.
Two-Sided Marketplaces: An Algorithmic Viewpoint
Markets facilitating economic transactions between two distinct sets of agents - buyers and sellers - have been around since time immemorial. However, they have been transformed in recent years by the rise of online platforms: for goods (Amazon, eBay), and increasingly, services: transportation (Lyft, Uber); electricity (the smart grid), physical/virtual work (Taskrabbit, Upwork); lodging (Airbnb); cloud-computing services (AWS, Azure, Google cloud marketplaces), etc. The core algorithmic challenge facing any two-sided marketplace platform is the same: it must decide which buyers and sellers should be matched, at what time, and under what terms of trade, to maximize some desired objective. Addressing these, though, is more challenging in online platforms, given the large scales and high volumes of data, complex constraints, and strategic interactions between agents leading to complex outcomes. Consequently, the design and operation of such marketplaces is a fast-emerging topic for researchers at SIGMETRICS, EC and related conferences.
The aim of this tutorial is to provide an introduction to the current algorithmic view - models, algorithms, and open problems - of online marketplaces. In particular, we will focus on the unique challenges of two-sided marketplaces: the requirement of budget balance, the need for two-sided participation constraints, the tension between segmentation and market thickness, etc. The tutorial will comprise of two parts - the first covering the mechanism design approach to two-sided markets (including the celebrated Myerson-Satterthwaite impossibility theorem, and recent progress on approximate optimal mechanisms via the CDW duality framework); the second focusing on the use of price-theoretic models to study more complex problems including the effect of information revelation, quality of service constraints, and competition.
Sid Banerjee is an assistant professor in the School of Operations Research and Information Engineering (ORIE), and graduate field member in Computer Science and the Center for Applied Mathematics, at Cornell University; he is also a technical consultant at Lyft. He received his PhD from the ECE Department at UT Austin, advised by Sanjay Shakkottai and Sujay Sanghavi, and was a postdoctoral researcher in the Social Algorithms Lab at Stanford, hosted by Ramesh Johari and Ashish Goel. His work is supported by an NSF CAREER award, as well as grants from the NSF and ARL.
Yang Cai is an assistant Professor of Computer Science and Economics at Yale University, and a member of the Cowles Foundation for Research in Economics. Prior to joining Yale, he was an Assistant Professor in the School of Computer Science at McGill University. He was a postdoc with Christos Papadimitriou at UC Berkeley, and received his Ph.D. at MIT in Computer Science under the supervision of Costis Daskalakis. He received a Sloan Fellowship in 2019.