路由查找技术的分析及研究

从数据结构的角度分析各种路由查找技术的原理.并针对IPv6可聚类的全局单播地址,提出面向IPV6的路由查找算法.通过研究对比各种路由查找技术及其优化策略,为实际工作提供理论依据.     

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

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

用路由软件组建BGP4+协议一致性测试平台

IPV 6协议是下一代互联网协议.BGP 4 协议是支持IPV 6的多协议扩展的外部网关路由选择协议.简要介绍了BGP 4 协议和路由软件Zebra.对BGP 4 协议一致性测试平台的结构进行讨论,给出了一个用路由软件Zebra组建支持IPV 6的BGP 4 协议一致性测试平台的例子.     

基于IBFBP的IPv6路由查找算法

总结目前IPv6路由查找算法优缺点,提出了一种新的IPv6路由查找算法(IBFBP).该算法结合改进的布鲁姆过滤器(IBF)与BP神经网络,将IPv6不同长度网络ID作为IBF的输入,以关键字的特征标志创建标志库(LB)进行学习,提前判断是否发生误判.并且将位数组用counter计数数组来代替,支持可删除操作,进而进行BP神经网络学习过程.理论分析和实验结果表明:该算法比已有神经网络路由查找算法需要学习的条目数平均减少了1 500倍,还降低了误判率和搜索成本,提高了查找效率.     

从IPV4向IPV6过渡的隧道技术

本文研究探讨了从IPV4向IPV6过渡的过程中，用于解决IPV6小岛之间通信的各种隧道技术，并对它们的实现机制和路由开销做了比较。     

一种基于Trie的IPv6路由查找方案

在路由表中高效地查找匹配128位IPv6地址,成为了IPv6技术发展的一大制约因素。经大量研究表明,Trie数据结构是实现高速路由查找和报文转发的关键。本文结合IPv6的地址结构特点,设计出基于Trie数据结构的查找算法,提高了路由查找效率以及报文转发速度。     

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

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

Linux模拟IPV6双栈路由器实现方案

介绍了IPV6的网络路由器的原理和在Linux上的具体实现方法。讨论了在Linux下如何搭建IPV6网络试验平台,重点讨论如何将Linux工作站模拟成双栈路由器。然后介绍了静态路由和动态RIPng路由协议在Linux下的实现方法。     

低速无线个域网中的IPv6路由实现

分析了将IPv6与IEEE 802.15.4结合,在硬件平台上实现使用此协议的无线个域网(WPAN).该网络支持AODVjr路由算法,实现短程无线通信.重点论述了IPv6在IEEE 802.15.4上的AODVjr路由算法的实现.它实现了网络层路由表的建立、路由查找和选路等功能.     

设账查找：路由新算法

针对路由查找时间越来越长，影响到网络运营速度和可靠性以及网络未来的发展的这一问题，提出了路由查找新算法——设账查找法。该算法是在重新构建路由表的基础上，将每一个IP地址在路由表中采用分层设账的形式进行管理；查找时逐级查找账户，避免许多不必要的查找，缩短了查找时间，可将目前的查找速度提高10000倍以上。     

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

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

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

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

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

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

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

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

Hardware Routing Lookup with SDRAMT

The authors present a routing lookup architecture, SDIR(SDRAM based Direct Index Routing). With pipeline and interleaving access technique, SDIR can provide scalable lookup speed from 16.7 MPPS(megapacket per second) to 133 MPPS with SDRAM running at 133MHz frequency.     

A Wire-speed Routing Lookup Algorithm Based on TCAM

IntroductionInthepastfew years ,theresearchonroutinglookupalgorithmhasmadegreatprogress.Alotofalgorithms,whicharebasedonsoft,protocolandhardwarehaveap pearedinmanyliteratures.The purposeofthesealgo rithmsistosupportfastlookup .Recentlysomenewhard ware basedschemesuseTCAMtoimplementwire speedroutinglookup .TCAMisa parallellookupdevice .TheternarycapabilityallowsTCAMtostoreprefixesandde terminelongestprefixmatching .ThelookupperformanceofTCAM basedschemeisindependentofthesizeofroutetable…