基于CPU缓存的高性能IP路由表查找
Tzi-cker Chiueh Prashant Pradhan
计算机科学系 纽约州立大学石溪分校
摘要：线高速IP（互联网协议）路由器需要非常快的路由表来查找新接收的IP数据包。 路由表查找操作非常耗时，因为在查找过程中，只用了IP地址的一部分，而且网络地址的长度是可变的。本文介绍了一种名为Suez的用于群集的并行IP路由器的路由表查找算法。该算法的创新方面在于它能够使用CPU缓存的硬件来实现路由表的更新并且直接仔细地将IP地址映射到虚拟地址表中。通过运行一个详细的仿真模型 ， 它采用的是从一个主要跟踪网络路由器收集的CPU内存层次结构对性能影响的数据包，我们证明了该算法的整体性能达到了一个每秒87.0万查找量的500MHz的阿尔法处理器，这种处理器有16K的一级缓存和1 - 2MB的二级缓存。这一结果比以前用软件实现的路由查找速度要快了1到2个数量级。本文还报告了建议在计划内的各种结构参数的性能影响和其存储成本，这是在一个装有Linux系统并拥有Pentium -Ⅱ处理器的计算机实施测量的。
一、导言
每个逻辑IP路由表项包括以下内容：网络掩码、目的网络地址和一个输出端口标识符。给定一个IP数据包的目的主机地址，一个IP路由表项的网络掩码字段，用来提取目标网络地址，然后将得出目的网络地址字段。如果它们匹配，该路由表将被认为是潜在的候选人。通过这种方式从逻辑上的目标主机地址进行比较每个路由表项。最后，路由表中最长的网络地址栏输入候选人获胜，而数据包是经由本项中指定相应的下一跳路由器输出端口。如果没有路由表项匹配传入的IP数据包的目的主机地址，数据包被转发到一个默认路由器中。每个路由表项的网络掩码都会摘录IP地址中的一个不同的最有效位数字作为网络地址。因此，IP路由表中查找表基本上是在寻找路由的最长前缀匹配一个给定的目标IP地址。相反的顺序扫描，现有的IP路由软件，例如在Unix中BSD的，建立一个索引树，加快路由表项的查找过程，避免来访无关。但是，即使有指标，基于软件的路由表查找操作仍不能运行线速度。例如，对于1000位的数据包和一个1 Gb /秒的链接，线速路由表查找意味着每个输入端口每秒100万的查找量。本文介绍了一项名为Suez的基于高性能软件的IP路由器项目的IP路由表查找算法。由于目标硬件平台是一个generalpurpose的CPU，该算法是专为高效率的纯软件设计的。在此算法的关键是，观察路由表查找目的地搜索IP地址的映射到输出端口，和现代微处理器CPU缓存的目的是促进一个类似的过程。因此，通过把内存地址为虚拟IP地址，就可以利用CPU的缓存作为它的一个硬件支持，以加快路由表查找。在理想的情况下，如果每个路由表中查找对应一个虚拟地址查找，只需要一个缓存访问。因此做一个路由表查找，只需要一个周期。然而，在实践中，需要更复杂的机械扭曲查表缓存来作为CPU缓存路由，因为IP地址的“标签”长度是可变的，而现有的CPU缓存硬件只支持固定长度的标签。而在Suiz路由查找算法中，会仔细地连接虚拟地址和IP地址，以确保路由查找速度是一个接近完成的速度出于是取决于什么处理器。本文剩余内容如下。第2节回顾以前的工作，IP路由表查找和缓存。第3节中详细介绍了Suiz算法的路由表查找算法的缓存和架构是利用CPU的缓存。第4节介绍的方法查找算法用于表评估建议的路由性能。第5节介绍了测量和仿真结果和性能的详细分析。第6节介绍了样品的系统架构和运作的执行情况。第7节结束这项工作与本论文的主要结果的摘要，以及正在进行的工作简要概述。
二、相关工作
现在最流行的搜索最长前缀字符串匹配数据问题是一位接着一位的Patricia trie。一项称为降低基数树类似的技术， 已经实施在了Berkeley Unix的4.3版本中。通过比较了VLSI实现成本和性能问题的内容寻址存储器（CAM）的基础和特里的解决方案，路由表查找。麦考利和弗朗西斯[4]提出了基于二元和三元的分层网络地址粘附分子的快速的路由可变长度查表解决方案。诺克斯和Panchanathan [5]描述了一种基于路由表算法的多处理器查找的解决方案，它是基于寻找一个基数的数组实现线性流水线。最近，瓦尔•德福格尔开发了一项利用特定的查找长度的二进制搜索哈希表，使得每一个哈希表是一个完美的或半完美哈希函数关于集的前缀。德格马克开发了一个紧凑的路由表中的代表性，以确保整个代表性，适合于典型的二级缓存。他们估计每个查询可指示内完成100使用8内存引用。相比以往的计划，Suiz的路由表的组织是非常简单的，查询操作从而更为有效。不同于基于树搜索算法，Suiz的路由表查找算法不需要回溯支持最长前缀匹配。最近，Varghese分析所提交的控制扩大规模较小的长度前缀设置为一个独特的前缀长度在搜索中的数据结构的选择一般技术数量减少和扩大这些路由前缀长度。通过动态规划来选择较小设置，利用搜索数据结构的大小作为目标函数。地址在另一个工作路由表查找，执行金额在硬件使用大型廉价的DRAM 1 2级单位查找表和管线的通道。与此相反，Suiz中的路由查找算法在完全依靠标准处理器内存和缓存的硬件及软件实施，它是一个基于PC机开发的地址和页面管理硬件商品/软件设计。以前报道的作品都没有详细说明，包括CPU的延迟测量缓存的影响。另一种方法来加快路由表查找缓存的查询结果。 Feldmeie研究了路由表缓存的管理政策，并表明该路由表查找时间降低了65％。 陈先生调查的有效性和环境效益的多媒体查询缓存表中的路由。Estrin和Mitzel计算出来的路由器的存储状态和查找信息的要求维持，并表明该地区的存在，通过执行缓存查找tracedriven模拟的一个LRU路由表，对于不同粒度的谈话。在现在的中，没有一个以前的作品利用了CPU缓存，在苏伊士中也是这样。 此外，我们相信Suiz的路由表查找方案是第一个在一个单一的的算法中集成了缓存和路由表查找算法。同时，我们的工作包括详细的仿真和网络路由器执行测量，主要针对该算法在路由表从收集和实时交通痕迹。
三、路由表查找算法
Suiz项目的一项主要设计目标是要表明，通用型CPU可以作为一个强大的平台得到高性能IP路由。因此，苏伊士的路由表查找算法充分利用了大量的高速缓存层次结构。该算法是基于两个数据结构，目的地主机地址缓存（HAC），及一个目标网络地址路由表（NART）。两者都旨在利用CPU缓存效率。该算法首先查找了HAC，来检查给定的IP地址是否是在HAC缓存，因为已经被看到了。如果是这样，查找成功，相应的输出端口是用于路由相关的数据包。如果不是，该算法进一步协商NART来完成查找。
A、主机地址缓存
通常情况下，多个数据包在一个网络连接的有效时间内传输，并且网络的线路连接采用相对稳定。因此，目标IP地址流被一个本地的路由器样本看到。也就是说，大多数查找路由表是直接从HAC查找。
因此，对于整体路由表查找的性能来说，减少HAC击中访问时间是非常重要的。与用一个软件数据结构相比，例如一个哈希表，Suiz的HAC需要大量的时间停留在1级（L1）高速缓存中，并能够利用高速缓存的硬件的功能直接查找。作为第一步，32位的IP地址可以被看作是32位虚拟内存地址，简单的看作为L1高速缓存。如果他们在L1高速缓存命中，那么整个查找就会在一个CPU周期完成，否则进行一个NART查找是必需的。然而，这种方法存在几个缺点。首先，相对于典型的计划执行内存引用流来说，在目标主机地址流中，缺少空间局部性。结果是，地址空间消耗（访问模式）将变得稀疏，这可能导致一个非常大的页面表和过度TLB失效率和（或）网页故障率。第二，除非有特殊措施，无法保证HAC所有时间都是一级缓存。特别是不协调的虚拟到物理地址的映射可能会导致不必要的冲突缓存而未命中，由于在HAC和其他数据结构的接口被用于查找算法中。第三，现代L1缓存缓存块大小对于HAC过大。也就是说，在网络数据包中，由于缺乏空间局部性流作为参考，单个缓存块往往利用不足，导致大多数时间没有或只有一个HAC在缓存块中。因此，整体缓存效率比它是一个固定大小缓存还低。
