*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Scalable Network Scheduling in Software
Ahmed Saeed
Ph.D. student in Computer Science
School of Computer Science
College of Computing
Georgia Institute of Technology
Date: Monday, February 11th, 2019
Time: 11:30 am - 1:30 pm EST
Location: 322 Classroom, Cherry Emerson Building.
---
Committee:
Dr. Mostafa H. Ammar (Co-advisor), School of Computer Science, Georgia Institute of Technology
Dr. Ellen W. Zegura (Co-advisor), School of Computer Science, Georgia Institute of Technology
Dr. Ada Gavrilovska, School of Computer Science, Georgia Institute of Technology
Dr. Amin Vahdat, Google
Dr. Jun Xu, School of Computer Science, Georgia Institute of Technology
---
Abstract:
Network scheduling determines the relative ordering and priority of different flows or packets with respect to some ranking function that is mandated by a scheduling policy. It is the core component in many recent innovations to optimize network performance and utilization. The increasing scale of cloud applications is driving the need to scale network scheduling to millions of flows and to apply complex policies. This requires software network stacks to handle a large number of flows, ranked according to operator-defined policies, and going over different types of networks. This proposal describes three network scheduling systems that allow network operator to deploy scheduling policies efficiently in software, taking into account the diversity of the requirements of modern networks.
First, we develop a system that enforces packet shaping, the most basic scheduling policy efficiently at end hosts. The challenge of packet shaping at scale is optimizing the CPU and memory overhead of the rate limiting system. We present a framework that scales to tens of thousands of rate limiting policies and flows per server, built from the synthesis of three key ideas: i) a single queue shaper using time as the basis for releasing packets, ii) fine-grained, just-in-time freeing of resources in higher layers coupled to actual packet departures, and iii) one shaper per CPU core, with lock-free coordination.
Second, we develop a system that provides efficient and programmable packet schedulers in software. Unlike non-work-conserving shapers, programmable schedulers are challenging to implement efficiently. We overcome this challenge by exploiting underlying features of packet ranking; namely, packet ranks are integers and, at any point in time, fall within a limited range of values. To support programmability, we introduce novel programming abstractions to express scheduling policies that cannot be captured by current, state-of-the-art scheduler programming models.
Third, we propose a single congestion control approach that is designed to handle datacenter LAN traffic and WAN traffic simultaneously. This work is motivated by our observation that customization of congestion control algorithms causes the WAN traffic to negatively impact the performance of the LAN traffic. This customization is based on the differences between WAN and LAN characteristics. However, it overlooks that both types of traffic compete at the near-source bottlenecks where the two types of traffic overlap. We propose deploying two interacting congestion control loops: one handles near-source congestion leveraging local network feedback, while the other handles congestion on the rest of the path using conventional LAN and WAN congestion control schemes.
