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

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

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

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

IP路由查找和报文分类模型研究

IP路由查找和报文分类作为路由器转发能力和提供高性能区分服务能力的关键因素,是当前路由器转发性能乃至整个网络性能的主要瓶颈。文章以IP路由查找和报文分类问题为研究对象,从空间几何的角度探究其本质,建立了相应数学模型MDCM,并以此为基础,讨论了各类搜索算法在IP路由查找和报文分类问题求解的优缺点,为研究和设计高性能的IP路由查找和报文分类算法提供重要指导。     

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

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

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

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

IP路由技术综述

因特网的高速增长给路由系统带来了巨大的压力。IP路由查找操作已经成为路由器转发性能乃至因特网整体性能的主要瓶颈之一。本文通过深入研究业界提出的关于IP路由的多种解决方案,提出了IP路由未来的发展方向。     

快速更新IPv4/IPv6双栈路由查找算法与实现

IPv4/IPv6双栈核心路由器需要一体化高效路由查找．但常用的单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列，这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性．提出并实现了一种独特的对前缀范围对分搜索的IPv4／IPv6双栈一体化多步TCAM流水查找方法．突出特点是转发表不需排序、查找速率高、表项更新快、查表连续性好．可满足IPv4／IPv6双协议栈核心路由器OC-768（40Gbps）端口、48B包的线速转发．     

多维IP包分类算法研究

IP包分类算法是应用在路由器数据平面的核心算法,其中一维的IP包分类算法就是路由地址查找算法,为路由器的基本转发功能提供支持,与此对应的多维的IP包分类算法是为支持第4层交换的路由器提供对IP数据报的分类,使路由器能对每一个特定的数据报作出预先定义好的处理,以便为了新的网络应用提供数据包过滤、防火墙、基于策略的路由、区分服务、QoS、流量计费等功能。本文介绍了两种典型的多维IP包分类算法在国内外研究现状及综述研究。     

LinuxIP路由查找算法研究

随着Internet技术的发展,尤其是网络带宽的不断扩展,在IP路由器中,当数据包达时,需要极快的路由查找速度,但现存的路由查找受其设计算法的限制,越来越难以满足这种需要,本文在分析了Linux下的路由查找机制的基础上,提出了一种改进的基于软件的高效率路由查找算法。     

高速路由器中基于树型结构路由查找算法的研究与实现

本文在比较各种基于树型结构查找算法的基础上提出了一种改进的路由查找算法，该算法具有查找速度快、所需存储空间小、更新速度快、硬件实现简单等特点，能够满足10Gbps核心路由器环境的要求。     

基于短前缀长度分割的高速二维分组分类算法

分组分类是路由器根据IP分组的多个域，从分类器数据库中匹配每个输入分组，确定分组转发规则的技术，分类器为实现因特网新业务提供了统一的方式，这些新业务包括：防火墙，网络地址翻译等，二维分组分类问题在未来的因特网体系结构中占有十分重要的地位，目前，人们已经提出了几种分组分类算法，但没有一种是理想的，提出基于短前缀长度分割的二维分组分类算法，它使用短前缀长度分割（SPLS）技术对分类器集合进行分割，使得分割后的小分类器子集合可以使用巳有快速IP路由查找方法进行查找，实现时以多叉树作为基本数据结构，实验显示它具有存储需求小，平均查询时间快，更新时间快，适合于大的分类器等特点，是一种较好的二维分组分类算法。     

Fast setup of end-to-end paths for bandwidth constrained applications in an IP/MPLS–ATM integrated environment

Transport networks are currently being moved towards a model of high performance Internet Protocol/Multiprotocol Label Switching (IP/MPLS) routers interconnected through intelligent core networks. Currently, Asynchronous Transfer Mode (ATM) technology has been widely deployed in several network backbones along with the Private Network-to-Network Interface (PNNI) protocols as the control plane. In order to cope with the increasing Internet traffic demands in the current context, fast setup of end-to-end paths with the required Quality of Service (QoS) is necessary.This paper analyzes the case of two IP/MPLS networks interconnected through an ATM core network, assuming MPLS as the mechanism to provide Traffic Engineering in the IP networks, and a PNNI-based control plane in the core network. This paper aims to define a mechanism needed to set up a fast end-to-end QoS Label Switched Path (LSP) between two Label Switched Routers (LSRs) belonging to different IP/MPLS domains. First, the fast end-to-end setup is achieved by modifying the network backbone control plane. Second, two different aggregation schemes are proposed to summarize the QoS network state information to be transported through the ATM core network. Therefore, both the efficient aggregation schemes and the fast mechanism allow source routing to set up a path faster than the existing methods and to reduce the blocking probability using a summary of the available resource information.     

An Internet without the Internet protocol

The growth of the Internet has brought about many challenges for its critical infrastructure. The DNS infrastructure, which translates mnemonic host names into IP addresses understood by the routers, is frequently the target of cache poisoning attacks. Internet routers are also experiencing alarming growth in their routing table sizes, which may soon make it impossible for them to forward packets quickly enough to meet demand. Further, concerns about IPv4 address space exhaustion loom on the horizon despite the availability of IPv6. In this paper, we take a fresh look at Internet routing and propose a scheme that addresses all of these concerns cleanly. Our scheme forgoes IP addresses entirely and instead uses host names as identifiers in packets. The scalability of routing is ensured by encapsulating these packets in highly aggregated routing locators: we use autonomous system numbers (ASNs), which are already an integral part of inter-domain routing. We present data and experiments to show that a much simpler and scalable routing infrastructure can be designed for a future Internet by using fewer identifiers for its entities.     

Measurement and performance of a cognitive packet network

As the size of the Internet grows by orders of magnitude both in terms of users, number of IP addresses, and number of routers, and as the links we use (be they wired, optical or wireless) continuously evolve and provide varying reliability and quality of service, the IP based network architecture that we know so well will have to evolve and change. Both scalability and QoS have become key issues. We are currently conducting a research project that revisits the IP routing architecture issues and proposes new designs for routers. As part of this effort, this paper discusses a packet network architecture called a cognitive packet network (CPN), in which intelligent capabilities for routing and flow control are moved towards the packets, rather than being concentrated in the nodes. In this paper we outline the design of the CPN architecture, and discuss the quality-of-service based routing algorithm that we have designed and implemented. We then present our test-bed and report on extensive measurement experiments that we have conducted.     

一个快速的二维数据包分类算法

随着因特网的发展，主干路由器上的包输入成为网络性能的瓶颈。该文基于空间分解技术提出了一个数据包分类算法，它将数据包和过滤器的匹配用多维空间中的点的定位来实现，可用于快速的路由查找和数据包分类。     

支持域间分布式分组过滤的BGP扩展

可信任是下一代互联网的重要特征.目前,互联网的路由系统只按照分组的目的IP地址转发分组,携带虚假源IP地址的伪造分组也会被传输到目的地,这会在威胁接收方安全的同时,隐藏发送方的真实身份.可信任互联网的路由系统不仅需要能够正确地转发分组,而且能够验证分组来自正确的发送方.基于路由的域间分布式分组过滤是过滤伪造分组的有效方法.提出了BGP的路由选择通知功能扩展,为域间分组过滤提供过滤标准.在扩展的支持下,边界路由器能够鉴别进入本自治系统的分组的真实性,过滤掉伪造其他自治系统地址的分组.模拟结果表明,路由选择通知不会对BGP正常的路由功能产生负面影响,选择合理的路由选择时钟参数,可以在同时取得较小带宽开销和较快收敛速度的情况下,为域间分布式分组过滤提供支持.     

Fast IP routing lookups for high performance routers

The key to the success of the next generation IP networks to provide good services relies on the deployment of high performance routers to do fast IP routing lookups. In this paper, we propose a new algorithm for fast IP lookups using a so-called two-trie structure. The two-trie structure provides the advantages in that less memory space is required for representing a routing table than the standard trie while it still provides fast IP lookups. Based on the simulation result, the memory space can be saved around 27% over the standard trie while a lookup operation takes 1.6 memory accesses in the average case and 8 memory accesses in the worst case. Also, the structure is not based on any assumptions about the distribution of the prefix lengths in routing tables. Thus, increasing the lengths from 32 to 128 bit (from IPv4 to IPv6) does not affect the main structure.