基于网络处理器IXP1200的路由查找功能的微码实现

介绍了网络处理器基本特点,以及如何基于Intel IXP1200网络处理器采用微码实现路由表的路由查找功能.路由查找功能采用Intel提供的TRIE表结构,实现32位IP地址最长前缀匹配算法.     

Trie树路由查找算法在网络处理器中的实现

Trie树数据结构的实现方法灵活,所需存储器空间小,是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s线速度网络处理器中微引擎的设计要求,提出一种基于最优平衡、多层存储的Trie树路由查找算法。建立一种平衡的压缩树结构,将该树中相邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度,以空间换取时间,从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现Trie路由查找算法,实验结果表明,单个微引擎的查找速度为4.4 Mb/s,能达到节省存储空间、提高查找效率的效果。     

基于RAM和TCAM存储结构的高速路由查找算法

由于因特网速度的不断提高,网络流量的不断增加和路由表规模的不断扩大,IP路由查找已经成为制约核心路由器性能的主要瓶颈。文章分析了两种常用的基于硬件存储器的路由查找算法,并结合它们各自优点,提出了一种基于RAM和TCAM存储结构的路由查找算法,该算法克服了上述两种算法的不足,具有查找速率高、更新时间快、存储代价低、易于实现等特点,是一种理想的适合于高速核心路由器环境的查找机制。     

众核网络处理器下高速包转发系统设计与实现

互联网的快速发展要求网络设备能够支持每秒几百万以上分组的转发能力,实现这一功能的关键是路由表的组织结构、快速的路由查找算法和高性能的硬件平台支持。设计并实现基于众核网络处理器的高速IP包转发系统,使用Tile-Gx36众核网络处理器作为硬件平台,采用基于Hash的前缀长度和多分支Trie树的路由查找算法,借鉴基于Hash的前缀长度路由表查找算法在存储和检索上的优势,并结合基于多分支Trie树路由表查找算法的查询效率,将路由表存储于L2层缓存中,进一步提高了路由表的访问速度和查询命中率。实验结果表明,对于不同大小负载的数据包系统均能满足40 Gbps的转发速度。     

支持压缩和多下一跳查找的路由查找方案

TCAM(ternary content addressable memory)是目前流行的一种高速路由查找技术.TCAM具有查找速度快、操作简单的优点,但同时它也具有3个明显的缺点:成本高、功耗大和路由更新复杂.路由器为了实现负载平衡以及策略路由,在路由表中保存着相当数量的具有多个下一跳的路由表项.基于TCAM技术,提出一种支持多下一跳的高速路由查找方案.方案通过两级索引表实现了多下一跳路由的存储和快速访问.为了提高TCAM的更新效率,方案还提出了一个N子空间TCAM更新算法.该算法对目前实际网络中的路由表,可达到近似O(1)的更新复杂度.为了减少TCAM的成本和功耗,方案中还使用了有效的路由压缩技术.压缩技术基于Trie树结构,实现简单.应用压缩技术,对于实际网络中的路由表,可减少20%的路由.该查找方案可以很容易地应用到未来的IPv6网络中.     

基于动态混合查找的WSN自适应路由算法

针对无线传感器网络(WSN)需动态调整路由请求域的问题,提出一种基于动态混合查找的WSN自适应路由算法。该算法依据路由查找的返回状态,以圆柱形路由请求域的半径作为调整参数,利用折半查找和指数查找相结合的方法对路由请求域进行动态自适应调整。仿真结果表明,该算法在数据包投递率、路由开销和数据包平均时延上的性能均优于AODVjr路由算法。     

基于网络处理器的路由交换方案

网络处理器是新一代网络设备的核心器件,基于网络处理器的路由器交换机开发是一个热点.由于ASIC和通用CPU各自的局限无法满足日益增长的网络流量和业务的需求,从而出现了网络处理器,网络处理器一般是由通用处理器作为控制CPU,多个转发引擎并行处理分组以隐藏访问I/O设备的延时,并通过协处理器来加速路由查找、CRC计算等功能.通过分析网络处理器的体系结构并依据当前网络处理器发展的实际情况提出了几种基于网络处理器设计的路由交换系统方案,并分析了各种方案的特点及应用场合.     

聚合组播路由并行查找算法

目前,组播主干网的核心路由器速率已经达到2.5Gbps～10Gbps,这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.为获取高性能组播路由查找算法,利用位图压缩技术,结合组播路由转发表的特点,设计出一种聚合组播路由并行查找算法,最后在IXP2800网络处理器模拟环境下对算法性能进行测试,达到了OC-192的线速转发性能.该算法适用于各种多线程结构处理器,具有较高的参考价值.     

路由查找算法研究综述

随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps～10Gbps.这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀匹配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了各种查找算法,并对它们进行了详细的分析和比较,最后指出了进一步的研究方向.     

基于TCAM的二级路由查找

功率消耗大是三态内容寻址存储器(TCAM)的主要缺点之一。根据TCAM的可配置特性，提出了基于TCAM的二级路由查找，大大降低了TCAM的功耗。给出了基于比特选择的二级路由查找方案并对其进行了性能分析。最后介绍了二级路由查找下的路由更新算法。     

高速地址Cache-散列表的应用

路由交换机对IP进行转发时，一般需要查找路由表获得转发路径。但在网络层上实现此功能是一个耗费时间的过程，特别是在一个比较大网络中进行路由交换时，其路由表会相当庞大，路由查找就成了交换机的一个瓶颈。为了解决这个问题，可采用高速地址缓存来加快路由查找过程。其基本思路是第一次IP包的路由确定后，以后的包直接转发，在具体实现中，需要有一个高速地址缓存为暂存路由信息，以便使后续的到达同一目的地的IP包块通过路由交换机。文章对高速地址缓存的实现进行了探讨。     

Reconfigurable memory architecture for scalable IP forwarding engines

In this paper, a reconfigurable memory architecture and lookup technique for IP packet forwarding engines is presented. This is achieved by partitioning the forwarding table into smaller partial lookup tables for each output port and allowing a forwarding engine to process them in parallel. This effectively reduces the complexity of finding the ‘longest prefix match’ problem to the ‘first prefix match’ problem. Our method is a flexible technique that significantly elevates the scalability of the next generation network processors and other packet processing devices. Such scalability facilitates migration to IPv6 and benefits network equipments especially in terms of growing routing table size, traffic, frequency of route updates and bandwidth requirement.     

高速地址Cache--散列表的应用

路由交换机由IP包进行转发时，需要查找路由表获得转发路径。但在网络层上实现此功能是一个耗费时间的过程，特别是在一个比较大的网络中进行路由交换时，其路由表会相当庞大，路由查找就成了交换机的一个瓶颈。为了解决这个问题，可采用高速地址缓存来加快路由查找过程。其基本思路是第一次IP包的路由确定后，以后的包直接转发。在具体实现中，需要有一个高速地址缓存路由信息，以便使后续的到达同一目的地的IP包块快速通过路交换机。对高速地址缓存的实现进行了探讨。     

Routing table partitioning for speedy packet lookups in scalable routers

Most of the high-performance routers available commercially these days equip each of their line cards (LCs) with a forwarding engine (FE) to perform table lookups locally. This work introduces and evaluates a technique for speedy packet lookups, called SPAL, in such routers. The BGP routing table under SPAL is fragmented into subsets which constitute forwarding tables for different FEs so that the number of table entries in each FE drops as the router grows. This reduction in the forwarding table size drastically lowers the amount of SRAM (e.g., L3 data cache) required in each LC to hold the trie constructed according to the prefix matching algorithm. SPAL calls for caching the lookup result of a given IP address at its home LC (denoted by LC/sub ho/, using the LR-cache), such that the result can satisfy the lookup requests for the same address from not only LC/sub ho/, but also other LCs quickly. Our trace-driven simulation reveals that SPAL leads to improved mean lookup performance by a factor of at least 2.5 (or 4.3) for a router with three (or 16) LCs, if the LR-cache contains 4K blocks. SPAL achieves this significant improvement, while greatly lowering the SRAM (i.e., the L3 data cache plus the LR-cache combined) requirement in each LC and possibly shortening the worst-case lookup time (thanks to fewer memory accesses during longest-prefix matching search) when compared with a current router without partitioning the routing table. It promises good scalability (with respect to routing table growth) and exhibits a small mean lookup time per packet. With its ability to speed up packet lookup performance while lowering overall SRAM substantially, SPAL is ideally applicable to the new generation of scalable high-performance routers.     

Shared memory multiprocessor architectures for software IP routers

We propose new shared memory multiprocessor architectures and evaluate their performance for future Internet protocol (IP) routers based on symmetric multiprocessor (SMP) and cache coherent nonuniform memory access (CC-NUMA) paradigms. We also propose a benchmark application suite, RouterBench, which consists of four categories of applications representing key functions on the time-critical path of packet processing in routers. An execution driven simulation environment is created to evaluate SMP and CC-NUMA router architectures using this RouterBench. The execution driven simulation can produce accurate cycle-level execution time prediction and reveal the impact of various architectural parameters on the performance of routers. We port the FUNET trace and its routing table for use in our experiments. We find that the CC-NUMA architecture provides an excellent scalability for design of high-performance IP routers. Results also show that the CC-NUMA architecture can sustain good lookup performance, even at a high frequency of route updates.     

UCLA网络加速器路由表快速查找改进模型

论文针对网络服务的应用,研究了UCLA设计的网络加速器模型,发现UCLA网络加速器设计在某些情况下得到较多不合理的下一跳出口地址,减低了加速器的性能。通过增加运算符改进加速器的运算,减少了所查找的路由表的出口数目,能更准确地定位下一跳的位置,提高了加速器的效率。     

IP Routing table compaction and sampling schemes to enhance TCAM cache performance

Routing table lookup is an important operation in packet forwarding. This operation has a significant influence on the overall performance of the network processors. Routing tables are usually stored in main memory which has a large access time. Consequently, small fast cache memories are used to improve access time. In this paper, we propose a novel routing table compaction scheme to reduce the number of entries in the routing table. The proposed scheme has three versions. This scheme takes advantage of ternary content addressable memory (TCAM) features. Two or more routing entries are compacted into one using don’t care elements in TCAM. A small compacted routing table helps to increase cache hit rate; this in turn provides fast address lookups. We have evaluated this compaction scheme through extensive simulations involving IPv4 and IPv6 routing tables and routing traces. The original routing tables have been compacted over 60% of their original sizes. The average cache hit rate has improved by up to 15% over the original tables. We have also analyzed port errors caused by caching, and developed a new sampling technique to alleviate this problem. The simulations show that sampling is an effective scheme in port error-control without degrading cache performance.     

一种基于哈希表和Trie树的快速IP路由查找算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。算法综合考虑了IP地址的分布特点,兼顾了查找速度、存储空间利用、硬件实现,以及向IPv6过渡等几个因素。具有算法简单、查找速度较快、存储空间利用率较高、易于扩展和便于硬件实现等特点。     

基于LSOT的高速IP路由查找算法

由于因特网速度不断提高、网络流量不断增加、路由表规模不断扩大，IP路由查找已经成为制约路由器性能的重要原因，因而受到广泛重视。目前人们已经提出几种算法用于解决IP路由查找问题，但均不能完全满足核心路由器的要求。该文提出一种基于LSOT的IP路由查找方法，它使用可变大小段表和偏移量表，能适应SRAM和FPGA芯片内存储器容量的变化，具有查找速度高、更新时间快、存储代价低、易于实现等特点，使用FPGA设计能满足10Gbps端口速率核心路由器环境的要求，使用ASIC设计能满足40Gbps端口速率核心路由器环境的要求。     

基于前驱查找的快速IP路由查找和更新方案

路由器的转发速率通常受限于选择路由的速度，因此路由查找和更新的方法在路由器设计中至关重要。文章提出了一种可硬件实现的快速IP路由查找和更新方法，将IP前缀匹配等价为地址范围搜索，采用B-树结构存储路由表。这种方案对存储要求较低，仅由小容量的片上SRAM和片外DRAM构成。实验表明，该方案在简单硬件支持下就能够达到OC-48的转发要求。