一种新型二维路由器的设计与实现

一种新型二维路由器的设计与实现51015202530354045摘要：随着网络的不断发展,越来越多的新业务要求 I P 网络上的路由器不仅能提供信息传输,而且需要对 IP 报文进行细粒度的分类转发，例如流量工程，ACL 访问控制等。然而传统的 IP 路由方法已经无法满足这些要求，因此针对传输控制等问题我们设计了一种新型的二维路由器。二维路由是一种基于 IP 数据包中一对源地址和目的地址来选择下一跳地址进行数据包转发的路由方法。与传统路由协议相比，使用二维路由能够更加灵活的控制所有的数据包转发，满足 IP 网络中的流量控制等特殊传输要求。我们使用 FPGA 和 TCAM 实现了二维路由器，用硬件完成二维路由的查找转发过程，。经过实验验证，二维路由器能达到与传统路由器相同的转发性能，有些情况下二维路由还具有更好转发性能。关键词： 计算机系统结构；二维路由；报文转发；流量控制中图分类号：TP393.0A New Type Two Dimensional Router : Design andImplementationChen Qi1, Xu Mingwei2, Yang Shu2(1. Beijing University of Posts and Telecommunications Network Technology research InstituteBroadband Network Research Center,Beijing,100876;2. Tsinghua University Computer Network and Protocol Testing Laboratory,Beijing,100084)Abstract: With the continuous development of network, more and more new business require IPnetwork router can not only provide information transmission, but also classify IP packet withmore finer category then forward them, such as traffic engineering and Access Control List.However the traditional IP routing method cannot meet these requirements, therefore, aiming atproblems such as transmission control we have designed a new type of two-dimensional router.Two dimensional routing is a kind of based on IP packet of a source address, and the destinationaddress to choose the next jump address to forward the packet routing method. Compared with thetraditional routing protocol, the use of two dimensional routing can be more flexible control all ofthe data packet forwarding meets the IP network in flow control and other special transmissionrequirements. We use FPGA and TCAM realized the two-dimensional routers which completetwo-dimensional routing lookup forward process with hardware. Experimental results show thattwo dimensional routers can achieve the same forwarding performance with traditional router, andin some cases two-dimensional routing also has better forwarding performance.Key words: computer architecture; two-dimensional routing; IP packet routing; traffic engineering0 引言传统的互联网路由器是根据数据包目的地地址进行路由转发的。这种一维路由器的一般只利用目的地址对数据包进行分类。然而 , 越来越多互联网应有对路由器提出了更高的要求 ，例如策略路由、路由路径的安全性，流量工程、服务质量等。然而由于传统路由器架构的缺陷使得路由器提供更高级别的服务上很难有所创新和发展。在这篇文章中，我们开发了一种在硬件上实现二元组包分类的路由器。这种路由器是基于源 IP 地址和目的 IP 地址对数据包进行分类转发的。我们选择二元组分类方法是因为 1 ）-1-二元组包分类比较容易开始研究和设计；2 ）目的 IP 地址能够让路由器对数据包进行路由转发，而源 IP 地址能够让路由器对数据包进行明确分类（ IP 地址在公网内具有唯一性）。我们认为源 IP 地址和目的 IP 地址在路由协议中是具有较高优先级的（很大程度上能决定路由路径）。在这篇文章中，我们展示了我们的二维路由器能够达到与传统路由器相当的转发速50556065率。我们还进一步展示了二维路由器能够轻松支持更复杂的路由算法，例如策略路由和流量工程。在这篇文章中，我们设计了一种新型的转发表结构。我们结合 SRAM 和 TCAM 各自的优点实现了二维路由转发表。相比 TCAM ，SRAM 具有低成本和大容量等特点，因此我们使用 SRAM来存储下一跳信息，而用 TCAM 来完成源，目的地址的查找工作。网络前缀与下一跳地址不2降到了 O（2n）的规模。我们在商用路由器 Bit-Engine 12004 中实现了这种二维路由表。我们只需要重新设计了硬件 FPGA 逻辑,而不需要新的硬件。我们从 CERNET2 网络中抓取真正的网络拓扑、FIB 前缀和实际流量数据对二维路由器进行了全面的测试。结果表明,我们的二维路由器可以实现相同的线卡转发速度,而且我们只需要非常小规模的 TCAM 和 SRAM。文章结构如下：我们在第一章介绍了研究的背景和相关工作。第二章专门介绍二维路由器的存储设计。我们将详细介绍二维转发表的结构和相对应转发操作如何完成。我们进一步提出我们的TCAM和SRAM压缩方案。第三章介绍二维路由器如何根据路由表完成转发功能和路由表如何进行更新。在第四章中,我们介绍在实际情况下如何实现二维路由器，以及对路由器的改进。第五章我们用实际网络中的数据评估二维路由器性能。最后, 在第六章我们总结所做的研究和工作成果。1背景和相关工作首先我们先解释一下常见路由器是如何处理数据包的 . 当一个数据包到达一个路由器后 ，它将该路由器的所有数据通路，包括 ACL 控制访问列表，PBR 策略路由表，最后是 FIB 普70751些情况下 ACL 表和 PBR 表的分类规则可能相同，即它们在数据包中提取出所比较的关键字也许一样，一般由源地址，目的地址，源端口 目的端口和数据包类型五元组组成；FIB 表只是根据目的地址进行下一跳查找，因此关键字一般只有目的地址。ACL 表和 PBR 比 FIB表具有高一些的优先级，当这两种表命中时，该数据包将被上交或者丢弃，否则将会让该数据包通过 FIB 表查找进行普通转发操作。传统的路由器当中这些关键字比较由 TCAM 完成 ，每一条规则都都会存放在 TCAM 的一个地址中，SRAM 在相同地址中存放该规则的对应操作。显然，如果我们扩展 FIB 表中的比较关键字，那么 FIB 表本身就能够包含 ACL/PBR 表的功能。本文中，我们首先将源地址添加到 FIB 表中（我们认为源地址是除目的地址外最有价值的关键字）。-2-再是一一对应而变成了一对多的方式。通过这种分离我们将 TCAM 中要存储的表项从 O（n ）通转发表 。ACL 和 PBR 用于不同的数据包分类，而且大多数应用在边缘路由器上。在某ACL丢弃PBR丢弃FIB丢弃转发80上交上交上交图 1：数据包处理流程目的网络前缀*下一跳地址1.0.0.1源前缀 目的前缀下一跳地址1.0.0.10111*011*110*（a）FIB1.0.0.21.0.0.31.0.0.11.0.0.21.0.0.31.0.0.1(b)ACL-likeTCAMSRAM图 2：FIB 表结构和 ACL 表结构2859095100最直接的就是线性查找。后来衍生出以决策树，多元组搜索为基础的解决方案。决策树使用3地址前缀数量大大小于地址数量的特点。根据前缀长度将每一条转发规则用哈希的方法放进4类可以利用优化算法和存储结构来达到提高查找速度。但是由于查找效率较低和不能很好大速率流量，使得软件路由方法并不在网络中很普遍。5处理性能和能够储存的表的大小也会受到 TCAM 性能的限制。大多数的数据包分类方法都是使用类似 ACL 表的结构。这类查找方法在本质上都有一个缺点，那就是当前缀中的元素越多时，查找表会受到元组的乘法效应，使得表爆炸式增长。例如，在 ACL 表中，TCAM 存储的表项会有很多，而 SRAM 中仅存储一些下一跳地址。有研究提出更紧凑的结构来减少前缀的乘法效应。例如在 5 中，它首先查找一个一维目的前缀表, 并输出一个存储源前缀的子表地址 , 在那里再进行查找可以找到的对应的操作。如果子表中操作都是相同的，那么它可以合并不同的前缀规则。还有人提出扩展 SRAM 中存6这些都没有真正的解决乘法效应问题。这里我们将源地址添加进前缀匹配规则中，而且我们7表 1：二维转发表#123456目的前缀*011*110*源前缀*101*11*01*下一跳地址1.0.0.11.0.0.01.0.0.21.0.0.01.0.0.21.0.0.1-3-*0111*0111*011*011*110*110*在网络发展历史上数据包分类一直是一个很重要的研究课题 。基于软件的解决方案中，树结构来优化查找空间并利用一定规则进行查找达到更快速的匹配 ；多元组搜索则是利用不同的散列桶中，利用这种方法将一次搜索化为几个并行查找 。因此基于软件的数据包分基于 TCAM 查找的硬件路由器能够达到一个时钟周期就能够完成查找 ，但是路由器的储的内容，一个前缀可以对应多个操作。这样即使操作不同，仍能够合并一些前缀 。但是完全消除了这样带来的乘法效应 。78910110*110*110*101*111*101*100*11*1.0.0.21.0.0.01.0.0.21.0.0.22 二维转发表1052.1二维转发规则在传统的路由器 , 最长匹配原则被用来决定哪一个前缀将被匹配。这里我们将遵循这一原则定义二维路由的转发规则。用 d 和 s 分别表示目的地址和源地址，Pd(prefix d)和 Ps（prefixs）表示目的前缀和源前缀。A 表示转发的下一跳地址。一条二维转发表项由一个(Pd,Ps,a)三元组组成。110115定义 二维转发规则 当一个数据包到达路由器时，他的目的地址 d 首先按照最长匹配原则匹配目的前缀 Pd ，然后源地址 s 按照最长匹配原则匹配源前缀 Ps ，最后转发到所匹配的三元组中的下一跳地址。我们的这条规则还遵循以下几条原则：1) 避免冲突：当目的前缀与源前缀有相同的优先级时，那么使用最长匹配原则将可能出现冲突。因此二维表中目的前缀比源前缀高一个优先级。2) 兼容性：如果在匹配目的前缀后，无法找到与之匹配的源前缀，那么我们的转发规则倒退回 FIB 表转发规则，按照最长匹配的目的前缀的下一跳转发。2.2二维路由表的基本实现方法二维转发表的核心思想是 TCAM 与 SRAM 的分离 (见图三) 。首先目的前缀和源前缀存储在 TCAM 中，一张下一跳地址偏移表存储在 SRAM 中。而下一跳的信息由于比较长，因此我们120125在 SRAM 中存储的是一张映射表。图 3：实际二维转发表的结构实际我们在设计二维路由器的转发表时，在 TCAM 中存储源前缀表和目的前缀表，SRAM 中存储二维索引表和下一跳地址映射表。目的前缀表存储的是目的网络前缀和对应的索引 di(destination index),源前缀表存储的是源网络前缀和对应的索引 si(source index)。二维索引表以 di 为行地址，si 为列地址，存储内容为下一跳的映射值。映射表则是以映射值为地址，对应内容是下一跳地址和转发行为（上交，丢弃，转发）。因此对应一条二维转发-4-规则（Pd,Ps,a），由 Pd 和 Ps 中匹配得到的索引值得到 a 的映射值。然后再映射表中得到 a的准确信息。130135140我们以图三为例子，对于(110*,11*,1.0.0.3),这条规则：目的前缀 110*存储在目的前缀表中并且其索引值为 2 表示索引表中的第二行；源前缀 11*存储在源前缀表中并且索引值为 4 表示索引表中的第 4 列。在二维索引表中我们找到第 2 行第 4 列的元素所存储的映射值为 3.最后我们得到索引表中的第 3 个下一跳地址为 1.0.0.3。利用二维路由表结构，在 TCAM 存储的内容大小将是 O(n+m)bits，在 SRAM 中存储的内容大小是 O(n*m)bits。很显然利用二维路由表，我们将“乘积因子”转移到了 SRAM 中，而不是消除它，这样做是因为：1 TCAM 的存储能力远远小于 SRAM；2 TCAM 的价格远远大于 10100 倍 SRAM 的价格；3 TCAM 的功耗远远大于 SRAM 的功耗8。这样做并没有降低路由器的转发性能，影响转发性能的主要 TCAM 查找，相比原来的 3次 TCAM 查找我们减少为 2 次查找。并且 SRAM 中索引表和映射表的读取在流水线模式下只消耗 1 个时钟周期，我们在文章后面将详细解释这一过程。2.3二维路由表的正确性为了证明采用这种结构的转发正确性，我们就需要关注二维索引表。因为在图 3 中我们可以看到在二维索引表有时会有很多的空元素，如何处理这些空元素，将是保证转发正确性的关键。我们注意到在插入一条前缀后，二维索引表中就会多出一行或一列空元素。我们考145150虑 这 样 一 个 包 ， 它 的 目 的 地 址 是 1011 ， 源 地 址 是 1111. 根 据 表 1 中 的 转 发 规 则(101*,11*,1.0.0.2)会被匹配.不幸的在图 3 的这种结构中(101*,111*)对应着索引表的第 3 行第 1 列，但是这个地址的元素是个空值。为了解决这个问题，我们在目的前缀表中添加一个默认映射值，即目的前缀表变为(目的前缀,索引值，默认映射值)如表 2.当一个数据包在匹配了(Pd,Ps)一对前缀后发现在索引表中不存在对应的映射值，就采用目的前缀中的默认映射值。通过这样的方法我们有效的解决了二维索引表中空元素带来的转发不确定的问题。同时利用这个办法我们还能使二维转发表兼容传统的路由转发表，而不需要对传统路由表做改变。1551603 二维转发表操作1653.1我们主要介绍两种二维表的相关操作：二维路由表查询和路由表更新查找操作首先我们将解释在路由器中如何实现这种二维转发表的查找。我们利用流水线查找技术将-5-表 2 目的前缀表目的前缀索引值默认映射值*00011*11110*21101*3011*4210*53二维转发表分解成多个独立的步骤。我们将表明，利用这种流水线查找二维路由器能够达到与传统路由器相同的查找效率。170数据包目的前缀表查询源前缀表查询FIFO默认映射值目的索引源索引确定下一跳映射值查询二维索引表数据包处理查询下一跳映射表图 4：二维路由查找过程查找过程如图 4 所示。当一个数据包到达路由器时。路由器利用 TCAM 对该数据包的目的地址和源地址分别进行在目的前缀表和源前缀表中查找匹配。通过 TCAM 匹配得到一175组索引值和目的前缀的默认下一跳地址映射值。为了避免 SRAM 和 TCAM 时钟不同步引出的问题，这些信息将被缓存进一个 FIFO 中。利用一对索引值路由器从 SRAM 中读取出下一跳映射值，如果是空则使用默认映射值。最后在映射表中通过映射值得到下一跳信息和转发操作信息进行数据包转发。利用 TCAM 和 SRAM 的分离结构，这几个步骤都是在同步进行的，这样做大大减少了一个包所需要的查找周期。映射表查询下一跳映射值二维索引表表查询源目的前缀表查询180图 5： 转发流水线时空图由图 5 我们可以得到一次二维路由查询操作所花时间为 1 个 TCAM 查询周期和 3 个SRAM 读取周期。在采用流水线的情况下，数据包可以在仅花费一个时钟周期的情况下被连续的处理。而传统的路由器由于采用 ACL 结构使得 ACL 表，PBR 表和 FIB 表都存储在185TCAM 中，因此需要花费 3 个 TCAM 周期才能完成查询，就是说连续的数据包之间要间隔3 个周期才能够转发。因此我们能够得出结论，二维路由表能够达到与传统路由器相同的转发铝塑甚至更快。这我们在后面的测试中证明了这一点。3.2二维表更新路由表更新操作包括添加，删除和修改三种。二维路由表的更新操作与传统路由器最大190的不同就是一次更新不再是简单的单一数值修改，而可能是一行或是一列值的修改。我们考虑了以下几种操作：1)插入操作：目的前缀插入 insert(Pd,fc(Pd),2)源前缀插入 insert(Ps,fc(Ps)和转发规则插入 insert(Pd,Ps,a);2) 删除操作：目的前缀删除 delete(Pd,fc(Pd),2)源前缀删除 delete (Ps,fc(Ps)和转发规则删除 delete(Pd,Ps,a);3)更新操作：目的前缀更新update(Pd,fc(Pd),2)源前缀更新 update (Ps,fc(Ps)和转发规则更新update (Pd,Ps,a);我们用195Action(pd, fr(pd), Action(ps,fc(ps) and Action(pd, ps,a) 来表示这 3 种操作。Action(pd, fr(pd)发生在某一个目的前缀网络的可达性信息发生改变时，例如 BGP 路由-6-更新通告；这种操作一般只影响默认映射值或几个索引值因此，这种操作很容易完成。Action(ps,fc(ps)一般发生在策略路由更新或者 ACL 规则更新。这种操作必须更新二维索引表的一整列，而且没有有效方法能够改进这种操作。我们将在第五章具体讨论实现方法。200205210215220Action(Pd,Ps,a)意味着(Pd，Ps)这条规则发生改变。这种操作也可能引起二维索引表的一组数值发生改变，例如我们执行(101*,11*,1.0.0.1)这条更新,(101*,11*)和(101*,111*)都需要作出更改。二维表更新问题的核心就是如何找到一个新的二维索引表，使他相比原有的二维索引表的改变最少。在传统路由器中一般都采用树形结构来存储路由表，这样的好处是能够很清楚的看出一个更新对树中多少节点造成了影响。利用一些传统的路由优化算法，我们也能很快的计算出使前缀更新改变二维映射表最少的方法。关于算法的细节可以参考9。另外我们在硬件中使用多端口 SRAM 存储二维索引表和映射表，这样在更新时可以保证路由查找不被中断;而 TCAM 由于只有一个端口可以使用在更新时必须打断查找占用端口进行更新。因此对于大量的二维索引表的更新不会影响到路由器的转发性能。4 二维路由器的实现我们发现在实际中，只有很少的源前缀（例如一些著名的 web 服务提供商和数据中心中的网络前缀）有与默认路由不同的下一跳地址。因此给每一个目的前缀分配一行二维索引表是非常浪费的。为了进一步减少 SRAM 的空间我们把转发表分成 2 个部分，第一部分的目的前缀指向二维索引表中的一行，而第二部分目的前缀仅含有一个默认映射值。例如,在图 3, 目的地前缀 011* 不需要任何特定的源前缀 ,因此它是存储在第二部分。 在实现时，我们在目的前缀索引值上用一种特殊地址标记在逻辑上将索引表划分为 2 个部分。当某个前缀只有默认映射值，Action(Pd, fr(Pd)不在必须更新二维索引表。我们在一个商用路由器上实现了二维路由转发。该路由器支持 4 路光纤双工传输，最高速率为 1Gbps;路由器内部有一个 CPU 板卡用作路由器控制，两片 TCAM 芯片（IDT 75K62100），4 片 FPGA 芯片（Altera EP1S25-780）和多个 SRAM 芯片（IDT 71T75602），其中 FPGA 芯片用于各种芯片的控制使用完成二维路由转发流程。我们的实现全部基于原有硬件，没有添加其他新的芯片。我们从新设计了 FPGA 的功能代码，大约使用了 1500 行 VHDL 代码和少量的 C 语言代码。逻辑实现在图 6，图 7 为我们的硬件板卡实物。1 FPGA2 TCAM3 SRAM4 FIFO5光模块接口6 FPGA7 控制接口8 CPU板卡225图 6 内部 FPGA 设计图 7路由器板卡在数据平面，数据包到达路由器后，通过 TCAM 比较最长匹配出源前缀和目的前缀，通过与 TCAM 相连的 SRAM，FPGA 会得到一对索引值。然后 FPGA 利用这一对索引值读取存有二维索引表的 SRAM 得到对应的映射值。最后 FPGA 利用映射值读取存有映射表的SRAM 得到对应的下一跳信息。FPGA 将得到的下一跳信息和数据包一并传给下一个处理模-7-230235块。处理模块根据得到的信息将数据包进行上交，丢弃或者转发到 4 个端口中的一个。在控制平面，CPU 板卡用来处理协议的交互和读取上交的数据包内的路由信息来更新路由表。将对应的 TCAM 和 SRAM 的操作信息下发给 FPGA，FPGA 按 CPU 下发的操作来修改TCAM 和 SRAM 中的内容。5 性能评估和仿真测试我们通过收集 cernet2 网络中路由器的真正的数据来评估我们的二维路由器。由于页面限制,我们的详细模拟结果在9。5.1评估环境我们的评估环境有三个组件:1)一个 PC 主机作为控制平面,2)4 端口的光纤二维路由器和 3)流量产生器(IXIA 1600T)用来模拟网络的流量。流量产生器是通过光纤和路由器相连，PC 主240机通过串口连接到路由器。流量产生器以 4Gbps 的速度发送 64 字节数据包 (包括 18 个字节以太网头)。路由器接收流量并执行查找并将数据包转发回流量产生器。我们评估了存储占用 TCAM 和 SRAM 的大小以及查找和更新处理速度。5.2评估数据我们主要研究两种实际场景：策略路由和负载均衡。这两组数据就是从 CERNET2 实际245250255网络中收集得到。CERNET2 为超过 22 个主要城市中的大学和机构提供网络服务。在每个场景中我们主要评估 1)二维路由表所占 TCAM,SRAM 存储的大小 2)数据包查找转发速率 3)更新频率。我们从 CERNET2 路由表中收集到 6973 个网络前缀，我们主要收集了 3 所大学的策略路由表信息：清华大学（北京），华中科技大学（武汉）华南理工大学（广州）。我们将这3 组路由表信息放到二维路由器中进行测试（我们分别将策略路由简称为PR-BJ,PR-WH,PR-GZ）。我们还从武汉的节点路由器上在 3 个时间点收集了流量均衡的路由表信息，分别是6:00,14:00,22:00 (我们分别将这 3 个路由信息称为 LB-MO,LB-AF,LB-EV)。表 3 显示了每个路由表中的规则数目和更新操作数量(PB:策略路由，LB：流量均衡)。为了比较，我们把使用原始 ACL 表结构的路由器作为参考。表 3 路由表数据2605.35.3.1评估结果存储大小265在图 8 中 我们可以看到使用二维路由表结构的 TCAM 只有使用 ACL 表结构的 TCAM存储空间的 1/50.例如在 PR-WH 中二维路由表结构仅占用了 1MB 的 TCAM 而使用 ACL 表结构占用超过 72MB 的 TCAM。在流量均衡情况下 TCAM 存储空间相差很小，这是因为在策略路由时许多前缀都共享下一跳，我们使用二维路由能很好的将其合并，而在流量均衡时，-8-PB-BJPB-GZPR-WHLB-MOLB-AFLB-EVRules250366186306365674711873427410Updates/365674/475773这种二维转发规则较少，两种结构存储的网络前缀数量相当。270275在图 9 中我们可以看到，在使用策略路由时，二维路由表占用 SRAM 的空间大小只有ACL 表占用大小的 1/40.例如在 PR-WH，二维路由表占用 3MB 的 SRAM，而使用 ACL 结构的路由表占用了 125MB 的 SRAM。在使用流量均衡是，二维路由表占用的 SRAM 比 ACL结构的大一些。这是因为在策略路由中，虽然有很多前缀表项但是，二维索引表却很紧凑（空元素较少），并且通过下一跳映射我们又进一步减少了存储下一跳信息的 SRAM 空间；而在流量均衡时二维索引表却很稀疏，有大量的空元素使得 SRAM 存储空间较大。但是由于SRAM 的单位空间成本远远小于 TCAM 的成本，因此我们的二维路由表结构相比原来还是有很大优势的。280图 8 TCAM 存储空间图 9 SRAM 存储空间5.3.2查找速度在图 10 中，我们展示了在没有路由表更新时，路由器的查找转发数据包的速度。我们可以看到路由器的接收和发送速率均可以达到线卡转发速度的最大上限（在以太网中一个以太网帧包括 8 bytes 的序和 20 bytes 的头，因此其最大转发速率为 4*64/(20+64)=3.0476Gbps）。285注意，由于受到线卡转发速率的限制，我们的路由器只能达到线卡转发速率的上限，如果采用性能更好的线卡，我们的二维路由器还能达到更快的转发性能。图 10 转发速率-9-5.3.3更新操作290295300更新操作中 TCAM 的访问:我们评估了更新操作对 TCAM 的访问次数,因为对 TCAM 更新将中断查找。在图 11,我们展示了在策略路由和流量均衡中每 100 次更新对 TCAM 的访问次数。我们可以看到,使用 ACL 表结构 TCAM 访问次数比使用二维路由表结构的高 3 个数量级。例如,在策略路由中,每 100 次更新二维路由表仅有 2 3 次 TCAM 访问，而 ACL 表结构则导致数千次 TCAM 访问。这是因为二维路由表只有前缀信息在 TCAM，相关的下一跳信息存放在了 SRAM 中。更新操作中 SRAM 的访问:使用二维路由表在更新路由表时会有大量对 SRAM 的操作，尽管对 SRAM 的访问不会打断路由器的查找过程，但是受到总线读写资源限制，有可能使得更新不能及时完成。因此我们也评估了二维路由表在策略路由和流量均衡时对 SRAM 的读写次数。在图 12 中我们可以看到，使用二维路由表时每 100 次更新对 SRAM 的读写次数依然少于使用 ACL 表时的读写次数。这是因此使用二维路由表时每次更新只需要从写与原来不一样的索引表元素，而使用 ACL 表结构时，对 TCAM 中条目的频繁移动同样会引发对SRAM 的频繁读写操作。（注 FIST 表示二维路由表，ACL-LIKE 表示普通路由表结构）图 11 TCAM 访问次数图 12 SRAM 访问次数3055.3.4评估总结我们的评估显示二维路由表结构能够很好的容纳大量的前缀路由表。在各种场景应用中，二维路由表都有比原始路由表结构更好的表现。就现有的实验结果并不能充分说明二维路由表的潜力。我们的研究显示二维路由表能够轻松容纳超过 100 万条路由规则，并且每秒钟更新可以达到 5000 次。3103156 总结我们提出并实现了一种基于二维路由表结构的路由器。这种路由器可以实现基于目的网络前缀和源网络前缀的路由转发功能。我们通过一种对 TCAM 和 SRAM 的分离手段解决了由于网络前缀的增加而导致路由表爆炸增长的问题。我们利用 SRAM 的灵活性对二维路由表进行了压缩，同时开发了算法解决了 SRAM 的大量更新问题。我们不需要更新路由器任何硬件而在一种商用路由器上实现了二维路由转发，并且使用大量真实 CERNET2 网络数据验证我们的路由器具有良好的转发性能，并且能够支持各种网络服务例如策略路由和流量均衡。致谢历时将近两个月的时间终于将这篇论文写完，在论文的写作过程中遇到了无数的困难和- 10 -320325330335340障碍，都在同学和老师的帮助下度过了。尤其要强烈感谢我的论文指导老师徐老师，他对我进行了无私的指导和帮助，不厌其烦的帮助进行论文的修改和改进。感谢这篇论文所涉及到的各位学者。本文引用了数位学者的研究文献，如果没有各位学者的研究成果的帮助和启发，我将很难完成本篇论文的写作。感谢我的同学-杨术，在我写论文的过程中给予我了很多素材，还在论文的撰写和排版的过程中提供热情的帮助。由于我的学术水平有限，所写论文难免有不足之处，恳请各位老师和学友批评和指正。参考文献 (References)1