分布式路由器中的路由管理模型

高性能分布式路由器中 ,路由管理必须面对两个技术难点 :1)实现高性能的路由查找算法 ;2 )实现主从路由表同步。该文提出一种分布式的路由管理模型 ,给出了这两个技术难点的解决方案。模型实现了路径压缩 Trie树和TCAM硬件相配合的路由查找算法 ,采用了自主设计的过滤算法对路由信息进行过滤 ,并应用 Zebra协议兼容 IPv4和 IPv6路由协议。模型可支持 2 .5 Gb/s接口的分组转发以及 2 0 0 0条 /s的路由更新速度。目前该模型已在国家“八六三”重大攻关项目——“核心路由器”中得到实现     

基于二分查找和Trie的IPv6路由查找算法

分析基于前缀长度的二分路由查找算法和基于Trie的路由查找算法的优缺点,在此基础上提出一个改进的路由查找算法,并给出其在IPv6下的实现方案.由于基于前缀长度的二分路由查找算法扩展性好、查找速度快,而基于Trie的路由查找算法实现灵活、转发表动态更新快,这使得所提算法具备路由转发表动态更新快、查找速度快、对前缀长度扩展性好等优点.模拟实验表明该算法能够较好地满足IPv6的要求.     

一种基于CHT的可扩展非对称二分查找平衡算法

从讨论非对称二分查找树的平衡问题出发,给出了一种通用的平衡权函数构造方法,解决了Waldvogel等在算法优化过程中提出的启发式平衡权函数构造问题,优化了非对称二分查找树平衡算法,使得CHT(collection of hash tables)算法很容易扩展到128 bit的IPv6地址.实验表明,该算法与Waldvogel等在特殊情况下给出的推测结果基本符合,能很好地适应IP前缀分布的变化,具有很好的适应性和可扩展性.     

基于链表结构的频繁模式树构造

FP-Growth算法在关联规则挖掘中是最经典的算法,主要通过频繁模式树(FP树)避免生成候选频繁项目集.针对FP-Growth算法中耗费内存严重的问题,采用链表存储方式,给出了FP-Growth算法的实现方法,其中单个结点采用链表形式来产生,频繁模式树采用左孩子右兄弟的存储结构来组织.在此基础上利用索引表,实现了对频繁模式树中共同前缀结点的快速查找,提高了频繁模式树构造的效率,解决了FP树构造算法中数据存储的瓶颈问题.最后以天体光谱数据和城市土壤数据作为数据集分别对该算法进行测试,实验结果表明,该方法的构造效率要明显优于基于顺序结构的FP-Growth算法.     

Ipv6地址的转换及自动配置

在Ipv6面世之前,全球范围内的网络用户普遍使用的协议为IPv4,每个IPv4接口都具有一个32位的地址,这个地址在全球范围是唯一的,但随着Intemet的高速发展,逐渐暴露出了IPv4的不足,其地址空间已经快要枯竭,主要原因是由于采用了分块地址的分配方式,大量的IP地址被浪费了。而且路由表增长过快。Ipv4地址采用了两级层次结构．它的地址包括网络地址和主机地址两个部分．而路由器中只存储网络地址部分。换句话说,有多少个局域网络,就有多少个网络地址,这导致路由器越来越难以迅速有效地找到目的网络,路由算法非常复杂。而且路由器之间一般需要定期交换路由信息。路由表的过大也导致了网络开销压力增大。     

高效的分布式组密钥协商机制

为了解决现有的组密钥协商机制需要各组用户在本地维护完整的密钥树信息,从而严重制约安全组播系统可扩展性的问题,提出一种高效的分布式组密钥协商机制(EDKAS).在该机制中,每个组用户仅需维护一个五元组结构的密钥树分支,降低了用户的存储开销和通信开销.同时,该机制采用分布式树平衡算法,使得尽管每个组用户仅维护部分密钥树信息,仍可以很好地保持密钥树的平衡.实验结果表明: EDKAS可以有效地降低维护密钥树的存储开销和通信开销,可适用于较大规模的分布式安全组播系统.     

高性能安全路由器BW7000的设计与实现

高性能和安全是计算机网络研究的两个主要问题。路由器在保证转发性能的前提下提供网络安全保护已经成为当前的研究热点。文章介绍了在完成国家"八六三"计划重大课题"高性能安全路由器"的过程中解决的若干关键技术问题。高性能安全路由器BW7000基于自主设计的高性能路由器操作系统HEROS。为保证高性能的路由转发,设计实现了基于RAM的高性能路由查找算法;为支持服务质量控制和安全管理,设计实现了基于无冲突HashTrie树的分组分类算法和基于反馈的分布式分组调度算法;为保证网络安全,提出了基于分布式密钥管理的路由器安     

一种基于信息交换的层次型快速移动IPv6切换机制

针对现有移动IPv6切换延迟大、分组丢失率高问题,提出一种基于信息交换的层次型快速移动IPv6切换(IFHMIPv6)机制.设计一种信息交换机制,使移动节点可预知领域内各接入路由器之间的邻居关系及相应的第2层和第3层信息;结合分层切换和快速切换,在分层移动IPv6上调整快速移动IPv6的信令流程,简化切换准备阶段操作;通过设置隧道定时器,保留在原路由器中建立的隧道.研究结果表明:IFHMIPv6在减少无线接入网络发现延迟和候选路由器发现延迟的基础上,进一步减少了总体切换延迟和分组丢失率,降低移动节点乒乓运动引入的信令开销;IFHMIPv6的切换延迟和分组丢失率比FMIPv6和HMIPv6的低.     

可编程虚拟化路由器的转发表查找技术综述

可编程虚拟化路由器是未来互联网的核心网络设备,即在一个物理路由器平台上并行实现多个相互独立的虚拟路由器.综述了可编程虚拟化路由器的转发表(forwarding table,FIB)查找技术.分析了FIB查找技术的性能与可伸缩性挑战,即查找吞吐量、存储空间和增量更新问题.讨论了多FIB融合的IP查找算法和基于NDN(named data networking)命名的非IP查找算法的研究进展.指出了OpenFlow的多域FIB查找和基于硬件的NDN线速转发是未来研究亟需解决的重点问题.     

数据流重组中Hash-Splay查找算法

针对高速网络取证目前所面临的问题,围绕提高网络数据流重组效率,在数据流重组算法中分析比较了几种典型的查找算法,并将Hash表和Splay树组合成Hash-Splay查找算法.该算法首先建立Hash表,然后将所有的TCP连接结点分配到各个表项,每个表项用Splay树将该表项的所有连接结点组织起来.查找时,根据连接标识通过Hash函数计算出Hash地址,再对该Hash地址对应的Splay树进行查找,找到后按照Splay树的操作规则进行查找、插入和删除等操作.由于根据连接标识找到对应Splay树的时间开销很小,可以忽略不计,因此Hash-Splay算法的复杂度可以看作是每棵Splay树操作的平均复杂度,算法同时具有Hash表和Splay树的优点,查找效率比Hash表和Splay树的都高.     

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

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

An efficient distributed algorithm for game tree search

This paper presents a distributed game tree search algorithm called DDS^*. Based on communication overhead, storage requirement, speed up, and other factors, the performance of algorithm DDS^* is analysed, and the number of nodes searched with SSS^* as well as a-b algorithm. The simulation test shows that DDS^* is an efficient and practical search algorithm.     

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

互联网面临的主要挑战之一就是路由系统的可扩展性.针对如何减少核心路由表规模,如何减小路径查询长度,如何避免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协议具有更低的路由表复杂度,更低的节点加入退出开销以及更低的查询跳数.     

基于前缀共享树的频繁情节挖掘算法

经典的频繁情节挖掘算法NONEPI及其改进算法NONEPI+存在时空复杂度高、"重复计算"等问题,基于最小且非重叠发生的支持度定义,提出一个基于前缀共享树的频繁情节挖掘算法PST_NONEPI,该算法采用深度优先搜索策略,将发现的频繁情节压缩到前缀共享树中,通过动态维护前缀共享树来发现所有的频繁情节。该算法只需扫描事件序列一次,大大提高了频繁情节挖掘的效率。实验证明,PST_NONEPI算法能有效地挖掘频繁情节。     

一种IP数据包快速分类算法

为了提高查找效率,在无冲突哈希查找算法和Grid of Tries算法的基础上提出了一种基于无冲突哈希和多比特Trie树(NHMT)的IP分类算法.该算法的核心有3部分:哈希函数的构造,主要是采用基于目的端口和协议两域构造哈希函数,使得在最坏情况下完全避免了空间爆炸问题;在Grid of Tries算法的基础上,对Grid of Tries算法改造成修剪的Trie树和多比特Trie树,以减少空间复杂度;在无冲突哈希查找算法的基础上扩展一层用于存放源端口号(或范围),扩展后一般要提高算法的时间复杂度,要通过引入多比特Trie树的方法进行解决.对于空间复杂度方面与无冲突哈希查找算法比较,一般情况下不增加空间复杂度.通过仿真,当对10 000条规则进行包分类时,该算法的分类速度可以达到1 Mbit/s,所消耗的最大内存为8.2 MB.     

基于子团规模的社团划分算法与地理位置

针对以往社团划分算法中存在的子团规模过大的问题,在CNM算法的基础上重新定义子团规模,提出了CLCNM社团划分算法.社团划分结果表明,改进后的算法在子团数量和模块度方面要优于CNM算法.在此基础上,研究社团划分与地理位置间的关系,提出地址前缀相似度的概念,子团地址前缀相似度越大,说明社团划分后的地理效应越明显.CLCNM社团划分结果表明:IPv6网络子团具有明显的地理效应,即子团中节点分布在相邻的地理位置.这一结论可对网络拓扑的再部署提供借鉴性意见.     

哈希在FCFS SAVI算法中的应用研究

FCFS SAVI是一种基于IPv6无状态地址自动配置协议的真实源地址验证方案,查找算法在该方案中起着关键作用.提出将哈希查找应用到FCFS SAVI方案中,详细分析哈希查找在FCFS SAVI方案中的性能,并进行了实验测试.