NeTS:Small: Making Online Network Functions Fast and Compact

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

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.