基于分割多分枝Trie树的并行路由查找算法

为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题,提出了一种基于分割的多分枝 Trie树的并行路由查找算法。该算法将一棵多分枝 Trie 树根据处理器的核数分割成若干子树,每棵子树又构成一棵单独的多分枝Trie树,子树中取消了前缀查找,采取组成一个大中间节点的方式,在中间节点之间采用固定步长查询,中间节点内部采用二进制Trie树来表示。实验结果表明,该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点,同时适用于IPv4和 IPv6地址。     

采用变长多分支树实现最长前缀匹配查找

随着Internet的迅猛发展,网络带宽需求不断增加,客观上要求路由器能够每秒钟转发几百万到上千万个以上的分组,分组转发的重要一步就是查找路由表,因此采用何种查找算法从而实现快速的IP地址最长前缀查找LPM是实现高速分组转发的关键。所采用变长多分支树查找算法将比传统的查找算法明显提高路由查找速度。     

多分枝trie树路由查找算法研究

为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP 路由算法的基础上,提出一种基于多分枝trie树的改进路由查找算法.在多分枝trie树中取消前缀查找,组成一个大的中间结点.在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示.仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用.     

改进的TCAM路由更新方法与实现

基于TCAM的硬件路由查找算法能够在一个时钟周期内完成最长前缀匹配．实现快速路由查找和分组转发。但路由表表项的有序性使得更新过程比较复杂从而成为TCAM路由技术发展的瓶颈。根据不同长度前缀表项的分布特性及路由表稳态时的更新规律，优化了路由表的空间分配，并引入了缓冲池的思想．提出了一种改进的路由表更新方法，从而提高路由表更新效率。     

多分枝trie树路由查找算法研究

为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP路由算法的基础上．提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀查找,组成一个大的中间结点。在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示。仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用。     

快速路由查找算法的研究

首先给出了现有的路由查找算法以及这些算法的优缺点,在此基础上提出了基于二分查找Trie的路由查找算法.另外,文章给出了算法在IPv6T 实现方案.该算法具有查找、更新速度快的特点,由于算法简单,容易实现,因此具有较高的实用价值.     

高速IP路由查找中改善更新性能的方法

现有的高速IP路由查找算法更多地强调路由表的查找,却忽视了路由表的更新。而路由表的更新对整个路由查找算法的性能和实际应用有不可忽视的影响。分段式查找树(Multibittrie)查找算法作为常用的IP路由查找算法,具有算法简单、有效等特点,但是更新速率较慢。作者提出一种在分段式查找树中控制路由表更新时间的方法,此方法能够较大地改善分段式查找树的更新性能。文章对更新性能的改善作了论述。     

高性能安全路由器中快速路由查找算法的研究与实现

设计快速的路由查找算法是提高路由器整体性能的关键之一.文章在一种基于RAM快速路由查找算法的基础上,根据高性能安全路由器的设计要求,进一步融入Hash链式表以及Trie树查找算法的设计思想,提出了一种可配置的路由查找算法.通过动态配置算法中的评价函数系数,该算法可以适用于多种网络应用环境.     

TSB:一种多阶段IPv6路由表查找算法

充分分析IPv6地址结构、IPv6地址分配策略和IPv6骨干网路由表的特点后,将二叉树、段表和路由桶技术相结合,提出一种多阶段IPv6路由表查找算法.和已有算法相比,提出的算法查找速度快、占用内存少、扩展性好、支持增量更新.实验结果表明算法的软件参考实现在装有P4 2.4GHz CPU,512M DDR333 内存和Linux 操作系统的普通PC 机上的查找能力可以到达16MPPS(Million Packet per Second),这可以满足10Gbps 80 字节IPv6最小包的线速转发.对于当前IPv6骨干网BGP 路由表,算法的参考实现只占用几百K 字节的内存.     

基于非重叠前缀集合的并行路由查找系统

快速的路由查找机制是高性能路由器设计的关键.最长匹配查找是路由查找的难点所在.本文提出一个并行路由查找系统.它使用一种路由表划分方法,可将路由表中的前缀划分为若干个集合,集合内前缀没有重叠.从而把路由表前缀的最长匹配查找转化为若干个集合内前缀的唯一匹配查找.基于这种方法,本文还提出一个通用的并行路由查找框架,框架适用于大多数路由查找算法.并行查找框架可简化查找算法的设计,提高查找算法的速度.使用二分查找算法,并行查找系统可以达到log₂(2N/B)的查找复杂度 (N为路由表前缀数目,B为大于4的整数).同时,并行查找系统对IPv6也具有很好的扩展性.     

BGP parallel computing model based on the iteration tree

Scalable architecture has become the main developing direction of core router in future Internet, and the major technical challenge faced by scalable router is the parallel computing technology in its control plane. This paper conducts an in-depth study of the parallel computing model of border gateway protocol (BGP) in scalable router. Based on hierarchical iteration tree, this paper gives a reasonable improvement of arborous BGP division scheme, which has the advantages of balanced task division and low communication cost. Detailed performance analysis is done and is compared with neighbor-based division scheme considering balance in the initial partition. At last, three implementations of the two schemes are compared and evaluated by using actual routing table data gained from Route Views. The conclusion is that, the developed division scheme based on iterative tree has a comprehensive advantage, which can provide workable models and methods to the expansion of control plane in the future scalable router system.     

High-speed IP routing with binary decision diagrams based hardware address lookup engine

With a rapid increase in the data transmission link rates and an immense continuous growth in the Internet traffic, the demand for routers that perform Internet protocol packet forwarding at high speed and throughput is ever increasing. The key issue in the router performance is the IP address lookup mechanism based on the longest prefix matching scheme. Earlier work on fast Internet protocol version 4 (IPv4) routing table lookup includes, software mechanisms based on tree traversal or binary search methods, and hardware schemes based on content addressable memory (CAM), memory lookups and the CPU caching. These schemes depend on the memory access technology which limits their performance. The paper presents a binary decision diagrams (BDDs) based optimized combinational logic for an efficient implementation of a fast address lookup scheme in reconfigurable hardware. The results show that the BDD hardware engine gives a throughput of up to 175.7 million lookups per second (Ml/s) for a large AADS routing table with 33 796 prefixes, a throughput of up to 168.6 Ml/s for an MAE-West routing table with 29 487 prefixes, and a throughput of up to 229.3 Ml/s for the Pacbell routing table with 6822 prefixes. Besides the performance of the scheme, routing table update and the scalability to Internet protocol version 6 (IPv6) issues are discussed.     

A router-assisted session tree configuration mechanism for reliablemulticast

A session tree based mechanism provides an efficient method to avoid well-known feedback implosion. However, it is not easy to configure an efficient session tree for IP multicast because it does not provide any explicit membership and routing topology information to the upper layer protocol. Incongruity between a session tree built on the transport layer and the corresponding routing tree on the network layer would incur large cost to handle control messages. This problem can be solved if a router that knows the information of routing topology can support the configuration of a session tree. Thus this letter proposed a router-assistant mechanism which minimizes the change of router functions and allows the routers to assist in providing a reliable multicast transport service     

Transmission-Efficient Routing in Wireless Networks Using Link-State Information

The efficiency with which the routing protocol of a multihop packet-radio network uses transmission bandwidth is critical to the ability of the network nodes to conserve energy. We present and verify the source-tree adaptive routing (STAR) protocol, which we show through simulation experiments to be far more efficient than both table-driven and on-demand routing protocols proposed for wireless networks in the recent past. A router in STAR communicates to its neighbors the parameters of its source routing tree, which consists of each link that the router needs to reach every destination. To conserve transmission bandwidth and energy, a router transmits changes to its source routing tree only when the router detects new destinations, the possibility of looping, or the possibility of node failures or network partitions. Simulation results show that STAR is an order of magnitude more efficient than any topology-broadcast protocol proposed to date and depending on the scenario is up to six times more efficient than the Dynamic Source Routing (DSR) protocol, which has been shown to be one of the best performing on-demand routing protocols.     

并行网络模拟中远程路由策略的研究

首先对并行网络模拟所采用的远程路由策略进行了分析研究,之后提出了基于优化边界的远程路由策略.该策略用边界路由器ID取代目的IP地址作为路由转发方式,有效地提高了路由查询速度.同时,通过树区域收缩、后连节点去重和边界路由器去重3种方法降低了内存的占用量.基于PDNS的实验结果表明,相对于基于边界路由器的远程路由策略,该方法降低了85％的内存使用量,并减少了75％的模拟时间.     

一种基于分时的LEO卫星网络无环路由算法

在分析传统卫星网络路由算法的基础上，提出一种基于分时的LEO卫星网络无环路由算法(DTRA)。针对卫星在各时间片之间进行路由表切换时可能出现的路由环问题，算法采用平滑路由表切换策略消除由于切换前后网络状态信息不一致而产生环路的可能性，保证分组在任何时刻都能够沿无环最短时延路径被转发。同时，DTRA也能够通过使用无环备份路径处理可能出现的链路拥塞、节点失败等突发情况。通过复杂性分析可知，算法只需较小的星上存储开销和星上处理开销，而无需星问通信开销。仿真实验结果也表明算法能够提供数据最优传送，具有较好的端到端时延性能。     

七号信令中SCCP面向连接业务实现的关键问题

信令连接控制部分(SCCP)面向连接业务的最主要特点是在传递数据之前的连接建立阶段就完成了路由选择,因而如何解决路由控制和多用户识别问题是实现该业务的关键。通过对协议的深入分析及实际应用的考虑,设计出路由控制流程和多用户连接段表,从而很好地解决了上述问题,并由测试结果对SCCP面向连接业务进行了性能评估。     

Avoiding instability during graceful shutdown of multiple OSPF routers

Many recent router architectures decouple the routing engine from the forwarding engine, allowing packet forwarding to continue even when the routing process is not active. This opens up the possibility of using the forwarding capability of a router even when its routing process is brought down for software upgrade or maintenance, thus avoiding the route flaps that normally occur when the routing process goes down. Unfortunately, current routing protocols, such as BGP, OSPF and IS-IS do not support such operation. In an earlier paper, we described an enhancement to OSPF, called the IBB (I'll Be Back) capability, that enables a router to continue forwarding packets while its routing process is inactive. When the OSPF process in an IBB-capable router is inactive, it cannot adapt its forwarding table to reflect changes in network topology. This can lead to routing loops and/or black holes. In this paper, we focus on the loop problem and provide a detailed analysis of how and when loops are formed and propose solutions to prevent them. We develop two necessary conditions for the formation of routing loops in the general case when multiple routers are inactive. These conditions can easily be checked by the neighbors of the inactive routers. Simulations on several network topologies showed that checking the two conditions together signaled a loop in most cases only when a loop actually existed.     

基于拓扑感知的水下传感网络路由

由于水下传感网络的高时延、低带宽和高能耗等特性,建立路由协议仍存在挑战。为此,提出基于拓扑感知的水下传感网络路由(TAR)。TAR路由先通过交互Beacon包,使每个节点获取网络拓扑信息,并建立邻居信息表。再依据节点剩余能量和链路的可靠性,择优选择下一跳转发节点,进而提高路由的稳定性,平衡节点间能耗。仿真结果表明,提出的TAR路由增强了路由稳定性,并减少了节点的能耗。     

VLSI总体布线算法研究与实现

总体布线是布图设计中一个极为重要的设计环节。本文提出了基于可分离最小生成树(SMST)的优化L形直角斯坦(Steiner)树(L_RST)和优化Z_RST的算法。该算法实现上绕开计算重合度问题，以新的角度计算代价。利用基于tile的结构，实现了伪管脚(pseudo pin)的分配，适用于现代多层布线需求。最后文章研究了同时考虑串扰和时延的综合性能驱动的总体布线算法改进。