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

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

高速地址CACHE——散列表的应用

路由交换机转发IP包时，需要查找路由表获得转发路径。网络上实现此功能比较费时，尤其在一个比较大的网络中进行路由交换时，路由查找表会相当庞大。为了解决这个问题，可采用高速地址缓存加快路由查找过程。其基本思路是第一次IP包的路由确定后，以后的包直接转发。在具体实现中需要有一个高速缓存来暂存路由信息，以便使后续的到达同一目的地的IP包快速通过路由交换机。本文采用散列算法对高速地址缓存的实现进行了具体的探讨。高速地址CACHE——散列表的应用@陈文革$西安交通大学计算机教学实验中心!710049 @程向前$西安交通大…     

IP路由缓存技术研究

针对目前用于IP路由查找的地址缓存技术和前缀缓存技术的局限性,分析了骨干网路由表前缀重叠特征,提出了一种基于阈值的IP路由缓存方法,该方法结合了地址缓存和前缀缓存技术,无需进行前缀扩展,克服了地址缓存技术缓存空间要求过大、前缀缓存技术无法缓存内部前缀节点的问题,在缓存空间、缓存命中率、缓存公平性以及路由增量更新方面具有优势;仿真实验表明对于路由条目超过260000的路由表,缓存空间大小为30000,选择阈值K=4时97%以上的节点可实现1:1缓存,其余节点采用地址缓存,缓存失效率小于0.02,可以用小的缓存空间实现高速线速转发.     

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

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

IPv4下路由查表及算法分析

查找路由表以给出下一跳地址是路由器中分组转发的核心步骤,因此快速的路由查表算法是实现高速分组转发的关键。该文分析了IPv4下路由查表问题及其难点,详细介绍了现有的各种查找算法并对它们进行了分析和比较,给出了在不同情况下应用适当查表算法的结论。     

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

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

自相似活跃子网前缀空间的路由查找

IP地址查询是路由器的基本工作,活跃IP和子网前缀地址空问是重尾分布且自相似的,而针对这种重尾分布的IP地址和前缀可以用于对路由查找进行统计优化．文章分析并验证了活跃IP地址空间的特点和子网前缀空间分形自相似特性,活跃IP的子网前缀在不同的聚类规模上的次序统计量服从Pareto分布,主干路由表项的次序统计量也近似服从Pareto分布．该文提出了一种基于活跃度排序的路由逐次查找算法——SOSL,对IP地址查询进行了优化,在该文的模拟实验中,活跃路由表的规模、刷新周期和活跃度判定下限间存在一些对数线性关系,使得作者可以以很小的活跃路由表来实现全部路由查找需求的99％;为SOSL实现中最关键的活跃路由表排序问题提出了一个基于计数器溢出的方案,复杂度为O（1）．对比发现该文的算法与TCAM结合能够提高TCAM的效率,高效地控制活跃路由表的规模,易于硬件实现．     

谁家的月亮最圆——第三层交换的不同解决方案

对于第三层交换,众多厂家都纷纷推出自己的方案。一般来讲,路由器厂家的策略是加入某些类似于交换机功能的快速处理;而交换机厂家则是在交换机中加入某些路由的功能。从产品或技术的定位来看,这些第三层交换技术又大致可以分为两种:面向LAN和面向WAN。 Ipsilon的IP Switching Ipsilon的技术称为IP Switching,它在ATM交换机上实现,利用ATM交换机高速的硬件转发性能。IP交换机由三部分构成:ATM交换机、IP switch controller以及一些特殊的管理协议,如IFMP和GSMP。 IP Switch Controller就是一个标准的IP路由器,可以运行路由协议,建立路由表,并进行第三层的信息转发。而且,它可以通过GSMP对ATM交换机进行控制。IFMP负责相邻IP交换机之     

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

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

核心路由器分布式路由控制的实现技术

针对骨干网上核心路由器的需求，提出了一种主从分布式高速多处理器交换体系结构。其主要思想是从模块不进行路由计算、不保存路由表，而保存全局的IP转发表；主模块运行路由协议负责维护路由表，计算并生成转发表，将该信息送往从模块。     

Learning the valid incoming direction of IP packets

Packet forwarding on the Internet is solely based on the destination address of packets, and it is easy to forge the source address of IP packets without affecting the delivery of the packets. To solve this problem, one can have routers check whether or not every packet comes from a correct direction based on its source address field. However, due to routing asymmetry in today’s Internet, a router cannot simply reverse its forwarding table to determine the correct incoming direction of a packet.In this paper, we present the source address validity enforcement protocol, SAVE, which allows routers to learn valid incoming directions for any given source address. SAVE is independent from—and can work with—any specific routing protocol. By only interfacing with the forwarding table at routers, SAVE allows routers to properly propagate valid source address information from source address spaces to all destinations, and allows each router en route to build and maintain an incoming tree to associate each source address prefix with a corresponding incoming interface. The incoming tree is further valuable in handling routing changes: although a routing change at one router could affect the incoming direction of source address spaces from many locations, only the router that sees the change needs to send out new updates. Finally, SAVE has a good performance with low overhead.     

一种基于马尔可夫模型的加速ICN路径收敛性的方法

在新型的内容中心网络(Information-Centric Networking, ICN)多宿主场景中,主机的标识和地址分离,允许数据包中携带多个地址。多目的地址的数据包在匹配路由表之后获得多个转发端口,在每跳具有路径选择的能力,可以根据网络的动态进行路径调整。然而,这种转发方法打破了根据路由表最短路径转发规则,数据包可能在网络中来回跳动而不能尽快收敛到目的地。本文提出一种基于马尔可夫模型的多地址裁剪方法,该模型能根据历史地址裁剪状态信息进行裁剪决策,从而提高路径的收敛性。实验结果表明该方法与基准方法相比,在保证传输速率几乎相同的同时,平均跳数减少约16%,在路径收敛性方面得到了改善。     

Efficient Management and Packets Forwarding for Multimedia Flows

Well known requirements for handling multimedia flows in routers are resource reservation and fast packets forwarding. The former takes into account the quite stable and long lasting bandwidth occupation, whereas the latter takes into account the large number of packets routed along the same path. Many techniques have been proposed and standardized to face these requirements, but their application is often complex, expensive and sometimes limited by the need of agreements between network managers of the many networks and Autonomous Systems. This paper introduces IMFM (Integrated Multimedia Flows Management), an innovative, scalable, and extremely lightweight technique to provide routers deterministic and dynamic resource reservation and a fast forwarding table lookup. It is based on a distributed linked data structure that allows direct (searchless) access to entries in the routers’ tables, extending the resource reservation algorithm REBOOK. Unlike conventional virtual circuits, IMFM does not require any interaction with (nor change in) the underlying routing protocols and autonomously recovers from errors, faults and route changes. If information stored in its data structure becomes obsolete, packet handling is reverted to best-effort, lookup-driven forwarding, so that packets are never dropped nor misrouted. IMFM can be gradually deployed, providing a framework for congestion avoidance solutions and increasing the forwarding speed in IMFM-aware router even along partially IMFM-unaware paths. IMFM has been fully implemented. Experiments have been designed to demonstrate its feasibility and the measured performance is reported and compared with existing techniques.     

XOR-Based Schemes for Fast Parallel IP Lookups

An IP router must forward packets at gigabit speed in order to guarantee a good quality of service. Two important factors make this task a challenging problem: (i) for each packet, the longest matching prefix in the forwarding table must be quickly computed; (ii) the routing tables contain several thousands of entries and their size grows significantly every year. Because of this, parallel routers have been developed which use several processors to forward packets. In this work we present a novel algorithmic technique which, for the first time, exploits the parallelism of the router also to reduce the size of the routing table. Our method is scalable and requires only minimal additional hardware. Indeed, we prove that any IP routing table T can be split into two subtables T₁ and T₂ such that: (a) |T₁| can be any positive integer k ≤ |T| and |T₂| ≤ |T| - k + 1; (b) the two routing tables can be used separately by two processors so that the IP lookup on T is obtained by simply XOR-ing the IP lookup on the two tables. Our method is independent of the data structure used to implement the lookup search and it allows for a better use of the processors L2 cache. For real routers routing tables, we also show how to achieve simultaneously: (a) |T₁| is roughly 7% of the original table T; (b) the lookup on table T₂ does not require the bestmatching prefix computation.     

面向非全互连3D NoC的自适应单播路由算法

针对在非全互连三维片上网络（3D NoC）架构中的硅通孔（TSV）表只存储TSV地址信息,导致网络拥塞的问题,提出了记录表结构。该表不仅可以存储距离路由器最近的4个TSV地址,也可存储相应路由器输入缓存的占用和故障信息。在此基础上,又提出最短传输路径的自适应单播路由算法。首先,计算当前节点与目的节点的坐标确定数据包的传输方式;其次,检测传输路径是否故障,同时获取端口缓存占用信息;最后,确定最佳的传输端口,传输数据包到邻近路由器。两种网络规模下的实验结果表明,与Elevator-First算法相比,所提算法在平均延时和吞吐率性能指标上有明显的优势,且在网络故障率为50%时,Random和Shuffle流量模型下的丢包率分别为25.5%和29.5%。     

紧凑路由研究

传统的最短路径路由策略通常需要在每个节点上维护到所有其他节点的路由信息,路由表大小随着网络规模的增加而快速增长,因此可扩展性不好.紧凑路由能够有效降低路由表的增长速度,允许通过路径的小幅拉伸来大幅缩减节点的路由表,从而在路径长度和路由表规模之间获得比最短路径路由更好的平衡.针对通用网络或特定拓扑类型的网络提出了许多紧凑...     

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.     

基于SDN与NDN的卫星网络多约束路由算法

针对NDN卫星网络内容传输时延高、丢包率高且请求命中率低的问题,提出了一种基于SDN与NDN的卫星网络多约束路由算法,并命名为SNMcRA。基于SDN的集中控制与全局视图,通过建立多约束路由模型,将链路多约束信息与蚁群算法相结合以求解满足时延、带宽、丢包率多约束的代价最小路径,由节点在包转发的过程中动态完成转发表FIB和待定请求表PIT的构建。实验结果表明,该算法与DSP算法相比时延降低了35%,带宽利用率提升了29%,丢包率降低了17%,并且在请求命中率方面也具有显著优势。     

多网关无线Mesh网络干扰与负载感知路由度量

提出一种应用于多网关无线Mesh网络中的路由度量。首先建立多网关网络模型,获取网络拓扑信息并依此为网络节点分配不同的权值;然后通过网络拓扑信息及无线链路的衰落特性,推导网络中链路信号与干扰噪声比SINR的分布特性,进而计算链路的中断概率和中断速率;最后获取Mesh路由器节点缓存包数量,并计算网关节点容量占比,针对客户端业务和Internet业务设计具有保序性的ILR(Interfere and Load aware Routing)路由度量,网络依据路由度量为客户端业务和Internet业务选路。ILR路由度量考虑了网络干扰因素和负载分布信息,能够有效降低网络干扰,达到网络负载均衡、提高网络吞吐量的目的。