Algorithms and architectures for high-performance IP lookup and packet classification engines

The Internet has become ubiquitous within the past few decades. The number of active users of the Internet has reached 2:5 billion and the number of Internet connected devices has reached 11 billion in year 2012. Considering this proliferation of Internet users and devices, forecasts show that the network traffic is expected to grow threefold between 2012 and 2017, which will result in a 1.4 Zettabytes of data exchange on the Internet in the year of 2017. ❧ These enormous amounts of traffic in the Internet demands high forwarding rates to satisfy the requirements of various time-critical applications. For example, multimedia applications such as video streaming, Voice over IP (VoIP) and gaming, require high bandwidth and low latency packet delivery. To meet such demands, network speeds have significantly increased since the inception of Internet; 10 Mbps to 100 Gbps rates within three decades. Such improvements in throughput are facilitated by the advancements in the underlying forwarding algorithms and the processing platforms used for networking. ❧ The goal of this research is to harness the processing capabilities and memory capacities of current state-of-the-art hardware and software platforms to devise wire-speed packet forwarding engines that are suitable for the future Internet. Even though the existing networking platforms possess the raw processing power and memory capacity, designing packet forwarding engines that meet the performance demands of future networks is not straightforward. It requires leveraging both algorithmic and architectural aspects of the solution and the platform, respectively, which forms the basis for our research. ❧ Specifically, four research problems are studied in this dissertation. They are as follows: ❧ • Scalable router virtualization with dynamic updates: With the advent of data centers and cloud computing, router virtualization is gaining popularity in the networking industry. Dedicated networking equipment on a per user (or virtual network) basis is expensive as well as not scalable. Router virtualization allows consolidation of multiple physical routers onto a single shared platform. In this research, scalable algorithms and architectures for large-scale router virtualization are developed. Update capabilities are integrated into the lookup architecture to enable non-blocking, incremental routing table updates. ❧• Performance modeling of virtual routers: Mapping multiple virtual routing tables onto a shared physical platform is challenging with stringent memory constraints, especially on hardware platforms. furthermore, it is important to know how many virtual networks can be supported on a given amount of hardware resources and what the performance would be. Hence, theoretical models for virtualized router performance are developed and a comprehensive performance evaluation of virtual routers is presented. ❧ • High performance IPv6 forwarding for backbone routers: The successor of the most prevalent logical addressing scheme in the Internet (IPv4) is IPv6. With this, several challenges arise from the packet forwarding engine’s standpoint: 1) increased routing table storage requirement, 2) increased lookup complexity 3) sustaining high performance. A versatile IPv6 lookup engine is developed that is suitable for both software and hardware platforms. The performance of the proposed approach evaluated on both software and hardware platforms show that the solution is suitable to be deployed in state-of-the-art 100 Gbps line-cards. ❧ • Ruleset-feature independent packet classification: Most packet classification solutions rely on various features of the classifier (or ruleset) to achieve low memory consumption and their reported performance. However, the unavailability such classifier features may cause such solutions to yield poor performance, rendering them to be suitable for only a subset of classifiers. A ruleset-feature independent packet classification engine that delivers deterministic performance for any classifier is proposed and evaluated. ❧ The aforementioned solutions are evaluated using state-of-the-art Field Programmable Gate Arrays (FPGAs). The IPv6 forwarding engine is implemented on both FPGA and general purpose multi-core processors to illustrate the versatility of the proposed solution. Performance evaluations demonstrate superior performance compared with existing solutions, with respect to throughput, memory consumption and power consumption. ❧ While the Internet backbone links are being upgraded to 100 Gbps rates, 400 Gbps and even 1 Tbps links are in the roadmap. Achieving such throughput rates while ensuring power and packet latency demands are met is a challenging task. This dissertation takes a step in this direction by proposing and developing novel lookup algorithms for packet forwarding engines that will meet and exceed the demands of the future Internet.

互联网在过去数十年间已无所不在。2012年，全球互联网活跃用户规模达25亿，联网设备数量突破110亿。鉴于互联网用户与联网设备的激增，业界预测2012至2017年间网络流量将增长至原来的三倍，2017年互联网数据交换总量将达到1.4泽字节（Zettabytes）。
如此海量的互联网流量要求极高的转发速率，以满足各类实时关键应用的需求。例如视频流、IP语音（Voice over IP, VoIP）、在线游戏等多媒体应用，均需高带宽、低延迟的数据包投递服务。为适配此类需求，自互联网诞生以来，网络传输速率已实现大幅提升：三十年间从10 Mbps演进至100 Gbps。吞吐量的此类进步，依托于底层转发算法与网络处理平台的技术迭代。
本研究的目标是依托当前最先进的硬件与软件平台的处理能力与内存容量，设计适配未来互联网的线速数据包转发引擎。尽管现有网络平台已具备原生处理能力与内存容量，但设计满足未来网络性能需求的数据包转发引擎并非易事。这需要分别从算法与架构层面，结合平台特性进行优化，这也构成本研究的核心立足点。
具体而言，本论文共研究四大科研问题，如下所示：
• 支持动态更新的可扩展路由器虚拟化：随着数据中心与云计算的兴起，路由器虚拟化在网络行业日益普及。为每个用户（或虚拟网络）配备专用网络设备不仅成本高昂，且缺乏可扩展性。路由器虚拟化技术可将多台物理路由器整合至单一共享平台。本研究针对大规模路由器虚拟化设计了可扩展的算法与架构，并在查找架构中集成更新能力，以实现无阻塞、增量式的路由表更新。
• 虚拟路由器性能建模：将多份虚拟路由表映射至共享物理平台，在严格的内存约束下极具挑战，尤其是在硬件平台场景中。此外，明确给定硬件资源可支持的虚拟网络数量与对应的性能表现至关重要。因此，本研究构建了虚拟化路由器的理论性能模型，并对虚拟路由器开展了全面的性能评估。
• 骨干路由器的高性能IPv6转发：作为互联网主流逻辑寻址方案（IPv4）的下一代标准，IPv6的普及给数据包转发引擎带来了多重挑战：1）路由表存储需求激增；2）查找复杂度提升；3）需维持高性能。本研究设计了适用于软件与硬件平台的通用IPv6查找引擎。通过在软件与硬件平台上的性能评估，证明所提方案可适配当前最先进的100 Gbps线路卡部署。
• 与规则集特征无关的数据包分类：绝大多数数据包分类解决方案依赖分类器（或规则集）的各类特征，以实现低内存消耗与优异的性能表现。但当无法获取此类分类器特征时，这类方案的性能会大幅下滑，仅能适用于有限的分类器场景。本研究提出并评估了一种与规则集特征无关的数据包分类引擎，可对任意分类器提供确定性性能保障。
上述所有解决方案均通过当前主流的现场可编程门阵列（Field Programmable Gate Arrays, FPGAs）进行验证。其中IPv6转发引擎同时在FPGA与通用多核处理器上实现，以展示所提方案的通用性。性能评估结果表明，相较于现有方案，本研究方案在吞吐量、内存占用与功耗方面均展现出更优的性能表现。
当前互联网骨干链路正升级至100 Gbps速率，400 Gbps乃至1 Tbps链路已纳入发展规划。在满足功耗与数据包延迟要求的前提下实现此类吞吐量，是一项极具挑战性的任务。本论文通过为数据包转发引擎设计新型查找算法，迈出了应对未来互联网需求的关键一步，相关方案可满足并超越未来网络的性能要求。