טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentVargaftik Shay
SubjectScheduling and Load Balancing in Emerging Networked Systems
DepartmentDepartment of Electrical Engineering
Supervisors Professor Ariel Orda
Professor Isaac Keslassy
Full Thesis textFull thesis text - English Version


Abstract

Nowadays, as computer networks continuously increase in size and speed, making an efficient use of compute and network resources becomes extremely challenging. At the heart of this challenge are scheduling and load balancing techniques that are expected to optimize resource usage and, in turn, minimize costs. The purpose of this thesis is to address these challenges.


Scheduling. We address the subject considering three platforms.


Dynamic networks. Backpressure algorithms constitute a well-known solution for routing, scheduling, and resource allocation in dynamic networks. However, they suffer from a number of major problems, which we successively address, as follows: (1) our first work (Chapter 4) focuses on solving the well-known starvation and last-packet problems; (2) our second work (Chapter 5) focuses on developing a dynamic Quality-of-Service (QoS) capability within the Backpressure framework.


Hybrid networks. Hybrid switching presents an appealing solution for scaling datacenter architectures. Unfortunately, it does not fit many traffic patterns produced by typical datacenter applications, and in particular, the skewed traffic patterns that involve one-to-many and many-to-one communications. Accordingly, in Chapter 6, we introduce composite-path switching by allowing composite circuit/packet paths between the two switches. We show how this enables the network to deal with skewed traffic patterns, and we offer a practical scheduling algorithm that can directly extend any hybrid-switching scheduling algorithm. 


Programmable switching. In Chapter 7 we introduce dRMT (disaggregated Reconfigurable Match-Action Table), a new architecture for programmable switches. dRMT overcomes two important restrictions of RMT by: (1) disaggregating the memory and compute resources of a programmable switch; (2) replacing RMT's pipeline stages with a cluster of processors that can execute match and action operations in any order. At the heart of dRMT is a new scheduling technique that can execute programs at line rate with fewer processors compared to RMT, and it avoids performance cliffs when there are not enough processors to run a program at line rate.


Load balancing. Today's heterogenous large-scale networks require scalable load-balancing techniques. Unfortunately, state-of-the-art load-balancing solutions for such networks are either unstable or provide poor performance. Accordingly, we look into scalable load balancing in a single as well as multiple dispatcher scenarios.


Persistent-Idle load distribution. In Chapter 8 we introduce the Persistent Idle (PI) load-distribution policy. In PI, the dispatcher forwards incoming jobs to an idle server, if such exists, or keeps sending all jobs onto the last server that was idle, otherwise. We prove that this counter-intuitive policy is stable and conduct simulations showing that PI achieves strong performance while incurring a negligible communication overhead.


Load balancing in large scale heterogeneous systems with multiple dispatchers. We next target a multi-dispatcher scenario. In Chapter 9 we introduce the Local-Shortest-Queue (LSQ) family of load balancing algorithms. Roughly speaking, in LSQ each dispatcher keeps a local view of the server queue lengths and routes jobs to the shortest among them. Communication is used only to update the local views. We show how simple and stable LSQ policies significantly outperform other low-communication policies using an equivalent communication budget.