NeTS:Small: Making Online Network Functions Fast and Compact

现代路由器的线速正在从OC-768（40 Gb/s）提高到100 Gb/s，甚至每秒太比特。为了跟上这样的高吞吐量，在线网络功能的流量测量，数据包调度，访问控制和服务质量将不得不使用片上SRAM实现。然而，将这些网络功能安装在快速但小的片上存储器中是当今的主要技术挑战。许多在线功能严重依赖于几个基本的构建块，称为在线原语，用于数据处理和存储。三个基本的在线原语是特别重要的：（1）用于测量每个流中不同元素的数量的扩展估计器，（2）用于测量每个流的大小的大小估计器，以及（3）用于对大型数据集进行成员检查的高性能Bloom过滤器。它们在服务提供、容量规划、计费、路由表查找、流量测量、防火墙设计和入侵检测等方面有许多应用。一个关键的技术挑战是如何使在线原语既快速又紧凑。由于速度快，要求它们在处理每个数据包时只进行一次内存访问或在最坏情况下更新一个计数器。由于结构紧凑，要求它们使用最少的SRAM内存，并能够处理大量不可预测的流。本项目致力于满足上述要求的新方法，称为虚拟位向量和虚拟计数向量，在线数据存储和检索。该项目包括四个研究部分：（1）一个内存访问紧凑的扩展估计，（2）一个计数器更新紧凑的大小估计，（3）一个内存访问快速布隆过滤器，（4）架构感知的在线原始designs.Broader影响：拟议的研究将推进我们的知识，设计大规模在线操作在一个非常紧张的片上存储空间。该项目开发的新设计方法有望提高现代路由器和防火墙的性能。此外，由于这些基本的在线原语中包含的基本数据结构广泛适用于计算机科学，因此其性能的改进可能会对其他研究领域产生广泛的影响。研究成果将通过会议和期刊出版物传播。将编制新的教材，将该项目的在线网络功能和研究成果纳入研究生课程。

The line speed of modern routers is reaching beyond OC-768 (40Gb/s) to 100Gb/s or even terabits per second. In order to keep up with such high throughput, online network functions for traffic measurement, packet scheduling, access control, and quality of service will have to be implemented using on-chip SRAM. However, fitting these network functions in fast but small on-chip memory represents a major technical challenge today. Many online functions rely heavily on several fundamental building blocks called online primitives for data processing and storage. Three fundamental online primitives are of particular importance: (1) spread estimators for measuring the number of distinct elements in each flow, (2) size estimators for measuring the size of each flow, and (3) high-performance Bloom filters for membership check against large data sets. They have numerous applications in service provision, capacity planning, billing, routing-table lookup, traffic measurement, firewall design, and intrusion detection. A key technical challenge is how to make online primitives both fast and compact. Being fast, the requirement is that they should make only one memory access or update one counter in the worst case when processing each packet. Being compact, the requirement is that they should use a minimum amount of SRAM memory and be able to handle a large, unpredictable number of flows. This project strives to fulfill the above requirements with new methodologies, called virtual bit vectors and virtual counting vectors, for online data storage and retrieval. The project consists of four research components: (1) one-memory-access compact spread estimators, (2) one-counter-update compact size estimators, (3) one-memory-access fast Bloom filters, and (4) architecture-aware online primitive designs.Broader Impact: The proposed research will advance our knowledge for designing large-scale online operations in a very tight on-chip memory space. New design approaches developed by this project are expected to improve the performance of modern routers and firewalls. In addition, because the basic data structures embodied in these fundamental online primitives are widely applicable in Computer Science, improvement in their performance can potentially have broad impact in other research areas. Research outcome will be disseminated through conference and journal publications. New educational materials will be developed to incorporate online network functions and research results from this project into graduate courses.