NeTS: Small: Eiffel: Efficient and Flexible Software Packet Scheduling

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Modern communication networks operate at high speeds that require sophisticated control of the timing of data transmissions to enable efficient sharing of network resources. The control of timing is performed by data packet scheduling functions deployed in core network components as well as user systems. This project considers the design and deployment of packet scheduling in network component software. Such deployment allows for 1) short development cycles, enabling the tracking of the state of the art, 2) enhanced flexibility of operation, and 3) function portability enabling the scheduling function to be deployed at multiple locations with minimal additional effort. The project will address the challenges of the software deployment of scheduling functions by developing and evaluating computation structures and algorithms that enable efficient software packet scheduling as well as mechanisms that allow users to tailor the scheduling functions to their needs. Advanced scheduling functions are central to successful modern high-speed networks, the core component of current and future advanced network applications infrastructure and data center networks. Packet scheduling is the core component of many recent innovations in optimizing network performance and utilization. The modern networks rely on packet schedulers in two specific ways: 1) traffic shaping and hierarchical bandwidth sharing at end-hosts, and 2) scheduling in hardware switches. For future networks, the scale in terms of number of flows and supported rates is expected to increase further with the growth of CPU (central processing unit) capacity and rates supported by network interface cards. Furthermore, network operators prefer programmable network components which have shorter development cycles. The focus of this project is on the design and deployment of efficient and flexible packet scheduling in software. While hardware implementation of network functionality will always be faster than its corresponding software implementation, software schedulers have several advantages including a shorter development cycle and the ability to deploy them on multiple platforms in multiple network locations. Software packet scheduling is challenging because of the inherent computational complexity of scheduling policy implementations, the difficulty of balancing efficiency with flexibility, and the need to carefully manage memory usage. Motivated by the importance of software packet scheduling and with these challenges in mind, the project aims to develop and evaluate approaches for efficient and flexible software packet schedulers. More specifically, the project seeks to: 1) Improve efficiency by equipping schedulers with efficient data structures, developing data structures that enable the scheduler to trade off accuracy for increased efficiency, and developing backpressure mechanisms that control memory usage, and 2) Improve flexibility without sacrificing efficiency by enabling the mapping of scheduling policies that require per-flow ranking in addition to or instead of packet ranking, and a re-ordering of packets or flows upon dequeue operation, and arbitrary shaping policies. The project will also develop accessible educational content for computer networking classes with specific emphasis on packet scheduling on modern networks. Ultimately, the project's goal is to advance the state of the art in software schedulers, making them feasible for practical use in diverse locations in future networks. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.