英语原文共 11 页
加速网络分析的算法和数据结构
强调
bull;一种新的队列算法，减少硬件队列中的数据包下降。
bull;新增无锁双峰生产者-消费者队列，消除多线程争用。
bull;动态分流流量的算法，同时最大化信息熵。
bull;无锁哈希表，假阴性低，消除内存争用开销。
bull;多分辨率优先队列，将优先队列的复杂性降低到O(1)。
摘要
随着计算机生成的数据以指数形式持续增长，暴露了新的瓶颈，这要求我们重新思考传统的软件和硬件架构。本文提出了五种优化网络流量分析过程的算法和数据结构(长队列模拟、无锁双向队列、早期去尾、LFN表和多分辨率优先队列)。我们在运行Bro网络分析器的高性能网络设备R-Scope上集成了这些优化，并且目前的基准显示，在10 Gbps的流量下，性能提升了5倍。
1、介绍
对路由器、防火墙或网络分析器等网络组件的系统范围优化非常复杂，因为它涉及至少数百种不同算法和数据结构的正确编配，这些算法和数据结构以微妙的方式相互关联。在这些高度动态的系统中，瓶颈迅速从一个组件转移到另一个组件，形成一个微瓶颈网络。这使得理解应该进一步优化哪些元素以获得额外的性能单元变得具有挑战性。此外，这些移动的微瓶颈以独特的方式相互连接，从而优化其中一个往往会导致性能的全面下降。这是由于内部系统的非线性所导致的，如在分层内存架构中发现的非线性。例如，虽然优化从线路到应用程序的数据包传输是至关重要的，但是在限制条件下，向应用程序推送过多的包是有害的，因为最终被丢弃的包将通过抖动处理器的本地缓存造成净负面影响，增加总体缓存遗漏率，从而降低整个系统的性能。因此，性能优化的过程应该是一个一丝不苟的过程，它要求采取细小而安全的步骤，避免追求短期收益的陷阱，正是这种陷阱可能导致新的、更大的瓶颈。
在本文中，我们提出了5个这样的安全步骤，它们有助于优化R-Scope的性能，一个能以其核心运行网络分析器Bro的高性能设备。这些步骤中的每一步都引入了一种新的算法或数据结构，旨在加速系统的整体性能，每一个都解决了不同的移动微瓶颈。当我们使用Bro来演示这些优化的有效性时，发现这些优化是通用的，因此我们认为这些技术可以普遍应用于加速网络分析的问题，或者在某种程度上，可以用于优化其他更活跃的网络组件，如防火墙或路由器。
本文的结构如下所示。第二部分将详细描述这五种HPC算法，给出它们如何运行的详细描述，以及用独立的基准测试来说明它们如何通过解除特定瓶颈来帮助提高性能。第三部分提供了一个系统范围的基准测试来测量所有算法一起工作的性能。第四部分则是对论文的归纳总结。
2、算法和数据库
2.1 数据包转发的长队列模拟
高性能网络接口卡(NICs)通过使用诸如接收侧缩放(RSS)、零拷贝、包合并或内核旁路等技术，帮助加快将包从线路移动到应用程序的过程。这些卡通过以硬件失去一定程度的灵活性和可编程性为代价来实现更高的性能。例如，在（高性能计算网卡）HPC NIC 中发现的一个常见的刚性元素是芯片中嵌入的内存量，它限制了在传输应用程序时用于临时保存数据包的环的大小。所以，应用程序无法足够快地处理的高流量临时突发，流量可能会从这些硬件环中溢出而导致数据包丢失。
传统的处理源自有限大小环(LSR)的数据包丢包的方法，是指定一个或多个调度程序线程(DT)将包从环中移出，并将它们放入一个或多个连接到驻留在主机上的应用程序线程(AT)的软件队列中。因为主机没有NIC的嵌入式内存限制，所以软件队列的大小实际上是无限的。因此，只要调度程序线程能够足够快地将数据包从有限大小的环(LSR)移动到无限大小的队列(USQ)，就可以消除由于突发流量而导致的数据包丢失。这个解决方法如图1所示。
虽然这个解决方案听起来不错，但在高性能计算环境中，调度程序线程还引入了以下细微但重要的性能损失:
- 数据包读取缓存损失。如果调度程序线程(DT)需要读取数据包（例如，如果它需要计算数据包的IP元组的哈希值来决定数据包应该转发到哪个目标队列）然后需要将这个数据包加载到本地缓存中。由于应用程序线程(AT)也需要读取数据包以进行自己的处理，所以调度程序模型需要将一个数据包加载到缓存中两次(一次在DT的本地缓存上，另一次在AT的本地缓存上)。这对性能有负面影响，因为缓存丢失(需要访问内存来获取数据)通常比缓存命中慢10倍。作为一般原则，一个好的设计应该针对每个包的整个生命周期中的单个缓存负载。
- 描述符读取缓存损失。即使DT不需要读取数据包（例如，一些实现可以从硬件提供的数据包环境信息中提取数据包IP元组的散列）DT仍然需要将包描述符加载到其本地缓存中。(数据包描述符是所有网卡驱动程序的一个小型软件数据结构部分，包含指向数据包缓冲区的指针和其他控制元数据，如数据包长度或其IP元组的散列等等。)在这种情况下，在一个数据包的生命周期中，它的描述符需要加载两次，一次在DT的本地缓存，另一次在AT的本地缓存。就像前面说的一样，一个好的设计应该为每个数据包描述符指定单个缓存负载。
- 内存和计算开销。这种方法带来的另一个开销是运行程序调度线程本身所需的额外内存和计算资源。
为了避免上述性能损失，我们建议使用长队列模拟(LQE)，这是一种简单但有效的技术，它消除了调度程序线程引入的开销，还可能减少数据包丢失。
LQE背后的主要概念是通过折叠执行操作让DT线程进入AT线程来模拟调度程序线程解决方案的行为。首先考虑由调度程序模型实现的DT和AT线程的伪代码：
AtLqeThread()过程的关键特征是，它确保来自LSR环的所有数据包在处理下一个数据包之前都被移动到USQ队列中，从而有效地为该环提供最高优先级。这种方法通过一个执行DT和AT过程的线程来模拟调度程序模型的行为。因此，数据包和包描述符都只加载到一次缓存(在AT的本地缓存中)，并且没有额外的内存和计算开销来维护调度程序线程。演示LQE模型如图2所示。
在更正式的情况下，我们将长队列模拟模型的性能属性描述如下引理:
引理1：(长队列模拟性能)让lambda;和lambda;max分别作为平均和最大数据包到达率测量光敏电阻环。假设为了简单起见且不失普遍性，处理一个包的时间为常数，让micro;dt和micro;lqe的各自作为DT模型和LQE模型的数据包处理速率,micro;dt和micro;lqe对应于一个除以所花费的时间执行AtThread()的第6行和AtLqeThread()的第5行。如果Slsr是LSR环中可以容纳的最大数据包数，则下面说法是正确的：
(1) micro;lqe gt; micro;dt .
(2) If slsr /lambda;max ge; 1/micro;lqe，LQE模型的性能优于DT模型。
(3) If slsr /lambda;max lt; 1/micro;lqe and lambda; ge; micro;lqe，LQE模型的性能优于DT模型。
(4) If slsr /lambda;max lt; 1/micro;lqe and lambda; lt; micro;lqe，DT模型的性能优于LQE模型。
证明：因为LQE模型不用承受由额外的缓存未命中或之前描述的计算和内存开销而带来的DT性能损失，不难发现micro;lqe gt;micro;dt。
对(2)来说也成立，注意程序AtLqeThread()和DtThread()的计算成本，除了处理数据包的成本之外都是一样的(假设从环和队列中放入和获取数据包的成本与处理数据包的成本相比，可以忽略不计)。因为在LQE模型中，处理一个数据包所花费的时间是1 /micro;lqe，当应用程序线程处理数据包时，可以插入到环中的数据包的最大数量是lambda;max /micro;lqe。因为slsrge;lambda;max /micro;lqe，没有数据包丢失，所以长队模拟和调度程序模型运送一个数据包丢失的概率等于零。从(1)可以了解micro;lqe gt;micro;dt，因此可以得出这样的结论：LQE模型使用更少的内存和计算资源，却可以提供了提供与DT模型相同的丢包概率，这就是它之所以成为卓越的设计的原因。
如果slsr lt;lambda;max /micro;lqe且lambda;ge;micro;lqe,然后从队列理论我们知道这将导致一个永久不稳定的状态，其中USQ队列将无限长，对于这两种模型，系统都不会有一个平稳分布。因此， DT模型和LQE模型的数据包将分别以lambda;minus;micro;dt、lambda;minus;micro;lqe的速率丢失。从(1)中micro;lqe gt;micro;dt，使得LQE模型成为比DT模型更好的设计。
最后,如果slsr lt;lambda;max /micro;lqe且lambda;lt;micro;lqe，那么再次运用队列理论我们发现，系统将稳定处理导致的队列大小临时增加的流量暴增，应用程序线程只能在LSR环能够适应暴增的情况下才能处理队列大小。在LQE模型中，当slsr lt;lambda;max /micro;lqe时，最大突发流量将溢出LSR环，在爆发期间内导致包丢失速率达lambda;maxminus;micro;lqe。然而，在DT模型中，由于专用的DT线程可以将数据包从LSR环移动到USQ队列，此过程不会丢包，所以可以消除这种数据包丢失的情况。因此，DT模型的性能更好。
图3用决策树总结了引理1的结果，这个决策树可用于确定何时使用DT或LQE模型。
我们举例说明引理1的实际应用来决定使用一个真正高性能计算应用程序的正确设计。假设我们的系统使用网卡Solarflare Flareon Ultra SFN7122F，这个网卡提供的硬件环可以容纳104个缓冲区，每个缓冲区包含65,536字节的数据包。假设一个体系结构中有20个应用程序线程，那么总缓冲区大小slsr = 136,314,880字节。表1给出了最长时间的应用程序线程，从1 Gbps到10 Gbps间的不同突发率(lambda;max)中，在不丢失任何在LSR环中数据包的情况下，以(slsr /lambda;max)的速率处理数据包。
表2和图4给出了应用程序线程运行Bro网络分析器所产生数据包的处理时间分布。这些测量书是使用一个流量数据集来执行的，该数据集是由我们在纽约的公司网络的真实数据包跟踪和使用Ixia流量生成器综合生成的。最终成为人工合成的流量(用于HTTP/HTTPS等应用程序)和机器生成的连接(用于SNMP等服务)的数据集。表3总结了流量数据集的主要统计数据。
根据这个样本，Bro可以在小于100ms的时间内处理所有的数据包(绝大多数数据包可以在小于1ms的时间内处理)，也就是1/micro;lqe lt; 0.1 s。自从SF卡网速在10 Gbps时用的时间为slsr /lambda;max = 0.11 s，因为slsr /lambda;max ge;1/micro;lqe，所以我们可以得出结论，当使用Solarflare HPC NIC高性能计算网卡时，长队列模拟模型是Bro网络分析器的正确设计。
最后一个要设计的参数是软件队列的大小(USQ)。实际上，这个队列可以是任意大小的(它的硬件限制由主机中的内存决定)，但实验证明存在一个最优大小值。这在图5中可以证明，我们使用表3中速率为10gbp的流量集为LQE提供实现。结果表明，当队列中的缓冲区数量等于1500时，数据包的丢包量是最小的。由于我们的实现基于Solarflare NIC，每个缓冲区有65,536字节，这就对应于一个98.3 MB的最优队列大小。
为了理解这个最优队列大小值的存在性，考虑两个极端情况。首先假设队列的大小非常小，显然这不是最优的，因为队列将无法容纳数据包突增。相反，假设队列的大小是无限大的。在这种情况下，队列可以存储非常大的数据包突发事件，但是在限制条件下，这样做将对本地缓存产生负面影响，因为并不是队列中存储的所有数据包描述符都适合本地缓存。也就是说，当我们试图吸收任意数量的数据包时，由于缓存抖动的增加，系统的生产率会下降。值得注意的是，这个最优值主要取决于静态系统参数，如(硬件)本地缓存的大小或(软件)数据包描述符的大小。因此，该值在不同类型的输入流量中应该相当稳定。但是，如果硬件架构发生变化(例如，缓存大小的增加通常意味着最优队列大小的增加)或者如果数据包描述符数据结构发生变化，那么这种优化将有所不同。
2.2 选择性捕获数据包的无锁双向队列
现在，我们将注意力转向设计高性能数据包路径中的另一个问题。除了由应用程序线程处理数据包之外，假设我们需要将接收到的数据包存储到磁盘中。因为在高速情况下，这可能是一项艰巨的任务(例如，10 Gbps的流量需要每秒处理多达2000万个数据包)，这将限制我们的规格为只捕获有限批数据包。我们将使用选择性数据包捕获(SPC)这个名称来表示以高速度执行捕获这种类型的数据包的功能。我们要实现的SPC引擎的工作原理如下:
- 应用程序线程完成对数据包的处理后，将数据包存储在第二个环中。如果环已满，则删除最旧的包，为新包腾出空间。
- 应用程序线程在任何时候都有能力触发数据包捕获操作。例如，应用程序可以决定是否处理一个正在进行网络安全攻击的数据包，并触发捕获操作，以便将一批数据包保存在硬盘中，以便对可疑数据包进行更详细的离线分析。
- 在触发包捕获操作时，SPC线程(ST)唤醒，将给定数量的数据包从环传输到硬盘，然后返回休眠状态。
SPC工作流如图6所示，是对第2.1节中LQE模型的描述。
由应用程序线程(AT)组成的子系统LSR2环和SPC线程(ST)定义了一个传统的消费者-生产者问题，但有一个警告：消费者并不总是活跃的。这意味着这个环需要两种不同的操作模式，一种是当用户休眠时不从环上取包，另一种是用户主动从环上取包。我们的目标是设计一个支持这两种操作模式的高性能队列，且不使用会对数据路径的性能产生负面影响的锁。我们将这种数据结构称为无锁双向队列(
资料编号：[5091]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
