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

现代通信网络以高速运行，需要对数据传输的时序进行复杂的控制，以实现网络资源的有效共享。定时的控制由部署在核心网络组件以及用户系统中的数据分组调度功能来执行。本课题研究的是网络组件软件中数据包调度的设计和部署。这样的部署允许1)短的开发周期，使得能够跟踪技术状态，2)增强的操作灵活性，以及3)功能便携性，使得能够以最少的额外努力在多个位置部署调度功能。该项目将通过开发和评价计算结构和算法来解决调度功能软件部署方面的挑战，这些结构和算法能够实现有效的软件包调度，以及使用户能够根据自己的需要调整调度功能的机制。高级调度功能是成功的现代高速网络的核心，是当前和未来高级网络应用基础设施和数据中心网络的核心组件。数据包调度是优化网络性能和利用率的许多最新创新的核心组件。现代网络以两种特定方式依赖分组调度器：1)终端主机上的流量整形和分级带宽共享；2)硬件交换机中的调度。对于未来的网络，随着网络接口卡支持的CPU(中央处理器)容量和速率的增长，流量数量和支持的速率方面的规模预计将进一步增加。此外，网络运营商更喜欢开发周期更短的可编程网络组件。本项目的重点是在软件中设计和部署高效而灵活的分组调度。虽然网络功能的硬件实现总是比其相应的软件实现更快，但软件调度器具有几个优势，包括更短的开发周期以及在多个网络位置的多个平台上部署它们的能力。由于调度策略实现固有的计算复杂性，难以平衡效率与灵活性，以及需要仔细管理内存使用，因此软件分组调度具有挑战性。考虑到软件包调度的重要性并考虑到这些挑战，该项目旨在开发和评估高效和灵活的软件包调度器的方法。更具体地说，该项目试图：1)通过为调度器配备高效的数据结构、开发使调度器能够折衷精度以提高效率的数据结构、以及开发控制存储器使用的反压力机制来提高效率，以及2)通过实现调度策略和任意整形策略的映射来提高灵活性，而不牺牲效率，所述调度策略除了分组排名之外或代替分组排名，并且在出队操作时对分组或流进行重新排序。该项目还将为计算机网络课程开发可访问的教育内容，特别强调现代网络上的分组调度。最终，该项目的目标是推进软件调度器的最先进水平，使其在未来网络的不同地点实际使用是可行的。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.