基于三态内容寻址存储器的路由表压缩和存储技术研究

针对高性能路由器中的路由存储和快速查找问题，提出了将冗余裁减算法和掩码扩展技术相结合的方法来压缩路由表。冗余裁减算法寻找路由表中的等价路由并删除冗余表项；掩码扩展技术则利用三态内容寻址存储器(TCAM)的非连续掩码的特点，对具有相同下一跳和相同前缀长度的路由项进行归并，并利用基于前缀扩展和逻辑最小化思想的增量更新算法，实现路由表动态更新过程中路由的重新归并。实验结果表明，本方法可以将路由表条目至少减少40％。     

路由表前缀结构分析

根据路由表中IP地址前缀之间的包含关系,提出了一种将地址前缀分类的方法,分析了各类地址前缀的增长规律．利用数据结构Trie来描述地址前缀,根据各地址前缀在Trie中的相对关系,将地址前缀划分为不同级别,分析了各级地址前缀的特征,并提出了路由表结构的概念．通过分析近几年路由表的结构探求路由表结构变化的特点和发展趋势．路由表中的地址前缀来源于用户的发布行为,通过分析发布行为对路由表结构的影响,寻找抑制路由表增长的方法．     

引入流量因素的路由表查找算法

分析了流量因素对路由表查找算法性能的影响,在CPU缓存技术的基础上提出引入流量分布因素的路由表查找算法,并对算法性能及适用性进行了讨论。     

抑制BGP路由表增长方法的研究

以增长趋势日益明显的BGP路由表为研究对象,针对在路由表中包含大量前缀长度大于地址分配策略所规定值的路由,基于模式匹配的路由过滤方法,建立了BGP路由前缀扩展列表的路由过滤数学模型,进一步讨论了AS级路由覆盖机制.仿真结果表明,该方法能够有效地滤除前缀长度不符合策略规定的路由,且能满足抑制路由表快速增长的要求.     

一种基于邻居路由表的Chord改进算法

利用空间换取时间的基本思想,提出一种基于邻居路由表的Chord改进算法NRToChord,该算法中每一个节点都维护一个具有更多节点信息的感知表,在路由过程中能够获取到与目标更加接近的下一跳节点,以提高路由效率,满足对路由时延有着更为苛刻要求的应用需要(如紧急通信,实时语音业务等).通过仿真实验证明:该算法在少量增加节点路由表容量的前提下,资源查找过程中的逻辑路由路径长度和物理路由时延都能缩短30%以上.     

快速的IP路由查找算法

下一代路由器的一个主要设计问题是IP查找机制。对于每一个接受的信息包,路由器在地址查找过程中需执行一次最长前缀匹配操作,以此决定下一个转发站点。目前,这一过程由软件完成并且已成为路由器性能的一个主要瓶颈。因此,我建议使用一种快速的IP查找机制,其中的转发表足够小可存储在SRAM（静态随机存储器）中,并且费用非常低。通过管道技术它也能用硬件来实现。通过使用我们建议的方法,一个大的、拥有45000路由前缀的路由表可以被压缩成大小大约为430千字节的转发表。在最坏的情况下,一次查询的存储器访问的次数是三次。当通过管道技术实现时,所建议的机制能达到每次存储器访问完成一次路由查询。对于目前10纳秒的静态随机存储器,这个机制提供大约每秒1亿次的路由查询。此外,查询速度可以通过存储器访问速度的加速线性提升。     

基于地址分配算法压缩路由表

提出一种基于概率的启发式算法对节点地址进行重新编号,该算法可以使得到达一些连续地址的下一跳尽可能的相同,进而再对这些连续地址进行压缩以达到简化路由表的目的.我们利用真实的网络拓扑进行仿真,实验结果表明在维持最短路径路由的前提下,仍然可以压缩到完整路由表的24%,利用这种方法可以极大的简化路由表,以提高网络仿真的规模.     

基于过滤机制的抑制BGP路由表增长的方法

经过对BGP路由表进行分析,发现在BGP路由表中包含大量前缀长度大于地址分配策略所规定值的路由·给出了一种减缓路由表增长的方法,该方法基于前缀长度对路由进行过滤·对前缀长度大于地址分配策略所规定值的路由,只允许其在指定的距离范围内被通告,一旦该路由穿越了指定数目的AS,它就将被过滤掉,不再被通告·通过修改BGP协议,为其增加一个新的属性来记录被过滤路由的最大通告距离,实现对路由过滤·通过模拟实验证明所给方法可行,对抑制路由表增长效果明显·     

一种路由表分布式存储转发架构及其查找算法

面向路由器FIS(Forwarding In Switch, FIS)处理机制,提出了一种基于路由表分布式存储的多级流水并行查找架构,采用多个低速的具有独立转发和交换功能的转发交换结点FSN(Forwarding and Switching Node)构成多级流水线,针对IPv6最长匹配前缀的查找需求,设计了一种基于前缀范围的二分查找算法PSB-BS(Prefix Scope Based Binary Search)：将IPv6转发表组织为分层结构,每一层对应不同长度范围的前缀信息,采用二分查找策略对子树层进行搜索,通过构建非对称二分查找树实现了转发表在FSN结点的分布式存储并能有效降低存储开销及IP查找复杂度.仿真结果表明,与目前Cisco商业路由器广泛采用的树位图算法相比,PSB-BS算法显著降低了存储及访存开销.     

Chord协议的最优路由表结构

给出了Chord协议路由的形式化描述,将路由过程抽象成一个整数由一个数列受限的线性表示问题.利用Chord的双向边寻求路由表结构的优化,分析并提出了Chord协议的最优路由表结构.给出了基于最优路由表结构的路由算法,证明了3倍数Chord在满环情况下为最优路由表结构.     

三态内容寻址存储器与多核网络处理器结合的IP查找加速模型

提出了一种三态内容寻址存储器(TCAM)与多核网络处理器(NP)相结合的IP报文路由查表加速模型.将前缀长度大于24的表项存放在硬件TCAM中;将前缀长度小于等于24的转发表项组织成压缩的二叉树形式,依据该数据结构截取其中部分表项并存放在硬件中,将其他部分存放在NP的2级缓存中,并将该部分的内存地址索引存放在TCAM中以加速查找;在静态随机存储器中存放转发信息,以最大限度地减小NP报文查表所需访存时延.结果表明：所提出的报文处理模型的可扩展性强,当路由表规模扩大时,其存储资源开销几乎不增加;而利用NP的多线程特性,其报文转发的理论吞吐量可达100 Gb/s的级别,能够满足现有核心路由器的转发需求.     

一种基于超级节点的Chord区域搜索算法

 Chord协议是使用分布式散列表(DHT)技术最简单的环状拓扑结构的p2p模型,但是目前对Chord协议的改进,存在着增大路由表和节点状态信息维护开销过大的问题.提出了一种折衷的改进算法,将Chord环分成区域,每个区域选取一个超级节点.通过区域超级节点层次化定位方法,在不增大路由表和节点状态信息维护的情况下,提高了系统的定位效率.实验模拟结果表明节点路由表只需维护O(logk)其它节点信息(k为区域数量),就可大大降低平均查询路径长度.     

AES快速算法的扩展指令集实现

基于Daemen等提出的AES快速算法,给出了用可配置处理器NiosII扩展指令集实现硬件加速的两种方案——基于片内存储器存储快速算法查找表的方法、用硬件逻辑电路实现S盒并计算出快速算法查找表对应元素的方法,用对前向查找表的查表操作代替了AES算法计算密集的轮变换操作.首先,将快速算法的前向查找表存放在片上内存中,并用12条扩展指令分别完成密钥扩展、轮变换和末轮操作,末轮变换所需的S盒采取对前向查找表的掩模得到;然后,对该方案进行优化以消除片上内存的占用,即推导出S盒与前向查找表的逻辑关系,并采取有限元素求逆的方法用逻辑电路实现S盒,增强了系统安全性并降低了功耗;最后,对扩展指令集和协处理器等多种实现方案进行了测试及性能对比.结果表明,相比于经过结构优化的纯软件快速AES算法,文中提出的方案在仅增加223个LE的条件下,达到了2.47倍的加速比.     

Internet路由前缀宣告的特征挖掘与分析

基于大量的历史BGP路由表快照,对BGP路由宣告信息进行深度挖掘.提出了前缀宣告稳定性度量方法,验证了绝大多数路由宣告是稳定的,历史上发生的路由劫持事件都是瞬时的(不具备稳定性);设计了前缀宣告的相似性测度算法,对大量历史BGP路由宣告进行了分析,结果表明大多数大型AS宣告的路由前缀具有自相似性,即,同一个AS宣告的多个路由前缀有一定的连续性.基于以上两个特征,从历史路由信息中可进一步提取前缀宣告的可信集,构造BGP路由宣告的可信知识库,为后续的路由前缀劫持检测和路由安全监测提供依据.     

一种基于位置与身份标识分离协议的映射查询方法

互联网面临的主要挑战之一就是路由系统的可扩展性.针对如何减少核心路由表规模,如何减小路径查询长度,如何避免IP语义过载等是亟待解决的问题.基于位置与身份标识分离(locator/ID separation protocol,LISP)协议和Chord算法提出了一种新的映射方法LISP-Chord.LISP-Chord映射查询机制采用Chord算法,将端标识—路由位置(endpoint identifiers-to-routing locators,EID-to-RLOC)映射关系分布式的存储在映射服务器(MapServer)上进行资源查询.仿真结果表明,相比LISP-MAP,LISP-Chord协议具有更低的路由表复杂度,更低的节点加入退出开销以及更低的查询跳数.     

对等网络中分布式查找算法的分析比较

对等网络中的分布式查找算法可分为结构性和非结构性的,它们在查找机制、网络拓扑和查找效率等方面存在一些共性及区别.经过综合比较后发现,查找算法在不同指标上存在一定的权衡,如为了提高某一个指标(如时间复杂性),必然以牺牲另外的指标(如空间复杂性或网络负载)为代价.在将复杂查询加以改进后可以将文件查找算法应用到其他领域(如网格计算)中作为分布式查找的基础,为设计新的查找算法和扩展P2P查找算法的应用领域提供了重要参考.     

RR-Chord:一个基于Chord的低开销快速查询P2P系统

针对结构化P2P系统高异质性和节点频繁加入或离开带来的系统性能问题,基于Chord设计了一个RR-Chord系统.该系统所有节点被分为路由节点和非路由节点.路由节点具有更多的资源和路由信息,并可根据自身能力的强弱调整其路由表的大小,所有的路由节点形成路由环,所有的路由信息在路由环上路由以提高系统的查询效率.设计的新的加入算法,进一步减少了节点频繁加入与离开造成的维护开销.理论分析和实验结果表明.RR-Chord具有较好的路由性能和非常低的维护开销.