IPv6 的快速路由查找算法研究

文章编号=1009 -2552 (2018)05 -0070 -05 DOI：10.13274/ki.hdzj.2018. 05. 017基于改进IPv6前缀的网络路由查找研究陈国良(暨南大学网络与教育技术中心，广州510632)摘要：随着IPv4地址的耗竭，IPv6的推广速度得到了非常大的提升。

具体的表现为，IPv6地 址分配量增多，骨干网路由器FIB(Forwarding Information T a b le转发信息表）中IPv6前缀数增加，骨干网IPv6流量大大增加。

路由查找算法的性能一直都是路由器性能的重要影响因素，针对 IPv4路由表进行优化的路由查找算法经过了非常久的研究，但是在IPv6的新环境下，以往的算 法往往性能不尽如人意。

因此，提出新的针对IPv6的路由查找算法非常必要。

文中针对IPv6的路由查找提出了一种分段查找与哈希查找相结合的算法，包括两种权衡策略，一种侧重减少查 找访存次数，一种侧重减少内存存储开销。

关键词：计算机网络；路由查找；IPv6中图分类号：TP393 文献标识码：AResearch on network routing lookup based on improved IPv6 prefixCHEN Guo-liang(Network and Educational Technology Center，Jinan University，Guangzhou 510632，China) Abstract：W ith the depletion of IPv4 address，the promotion speed of IPv6 is greatly improved.Specifically，the number of IPv6 address allocation increases，the number of IPv6 prefixes in the forwarding information table increases，and the IPv6 traffic of the backbone network increases greatly. The performance of the route lookup algorithm is always an important factor in the performance of the router.The routing algorithm for IPv4 routing table is studied for a long time.However，in the new environment of IPv6，the algorithms often do not perform w ell.Therefore,it is necessary to propose a new routing algorithm for IPv6. This paper proposes a combination of segment search and hash search for IPv6 route lookup，including two trade-off strategies，one that reduces the number of visits，and focuses on reducing memory storage costs.Key words：computer network；routing lookup;IPv6信息疼术2018年第5期0引百IPv6是为了解决IPv4地址空间有限的问题而 提出的协议，虽然由于历史原因，前期IPv6的推广 并不是非常顺利[1],在互联网中主要应用的还是IPv4协议,但随着IPv4地址的耗竭，IPv6成为了必 然的选择[2]。

基于改进IPv6前缀的网络路由查找研究陈国良【期刊名称】《信息技术》【年(卷),期】2018(42)5【摘要】随着IPv4地址的耗竭,IPv6的推广速度得到了非常大的提升.具体的表现为,IPv6地址分配量增多,骨干网路由器FIB(Forwarding Information Table转发信息表)中IPv6前缀数增加,骨干网IPv6流量大大增加.路由查找算法的性能一直都是路由器性能的重要影响因素,针对IPv4路由表进行优化的路由查找算法经过了非常久的研究,但是在IPv6的新环境下,以往的算法往往性能不尽如人意.因此,提出新的针对IPv6的路由查找算法非常必要.文中针对IPv6的路由查找提出了一种分段查找与哈希查找相结合的算法,包括两种权衡策略,一种侧重减少查找访存次数,一种侧重减少内存存储开销.%With the depletion of IPv4 address,the promotion speed of IPv6 is greatly improved.Specifically,the number of IPv6 address allocation increases,the number of IPv6 prefixes in the forwarding information table increases,and the IPv6 traffic of the backbone network increases greatly.The performance of the route lookup algorithm is always an important factor in the performance of the router.The routing algorithm for IPv4 routing table is studied for a long time.However,in the new environment of IPv6,the algorithms often do not perform well.Therefore,it is necessary to propose a new routing algorithm for IPv6.This paper proposes a combination of segment search and hash search for IPv6 routelookup,including two trade-off strategies,one that reduces the number of visits,and focuses on reducing memory storage costs.【总页数】6页(P70-74,78)【作者】陈国良【作者单位】暨南大学网络与教育技术中心,广州510632【正文语种】中文【中图分类】TP393【相关文献】1.基于前缀区间和前缀层次(PRPL)的IPv6路由查找算法 [J], 赵国锋;李振强;黄小红;马严2.基于有限前缀扩展和多Hash函数的动态IP路由查找算法 [J], 谭明锋;龚正虎;高蕾3.基于前缀区间集合的IPv6路由查找算法 [J], 崔宇;田志宏;张宏莉;方滨兴4.一种改进的IPV6最长前缀匹配路由查找算法 [J], 刘阳;高仲合5.基于前缀扩展的三级索引路由查找算法 [J], 唐丽梅;邢素霞;陈天华因版权原因，仅展示原文概要，查看原文内容请购买。

第22卷第10期 计算机应用与软件 Vol.22, No.102005年10月Computer Applications and SoftwareOct. 2005IPv6的快速路由查找算法研究王 燕(浙江警官职业学院 浙江 杭州 310018）摘 要 TCAM 被广泛用于执行快速路由查找，不管前缀的数量和长度，它能在极短时间内解决最佳前缀问题。

与基于软件解决方法相比较，TCAM 能提供持续吞吐量和简单系统体系，这对IPv6路由查找来说是很有吸引力的。

然而，它也有一些缺点，例如入口数量有限，价格昂贵和能源消耗。

因此，本文提出一种有效、能减少所需TCAM 的算法，该算法通过增加微DRAM 来消除98%的TCAM 入口。

实验证明，该算法效果良好，可以大大提高IPv6路由查找性能。

关键词IPv6 路由查找 TCAMRAPID ROUTING LOOKUP ALGORITHM RESEARCH ON IPv6Wang Yan(Department of Information Technology and Management, Zhejiang Police Vocation Academy, Hangzhou Zhejiang 310018, China)AbstractTernary content-addressable memory has been widely used to perform fast routing lookups. It is able to accomplish the best matching prefix problem in(1)O time without considering the number of prefixes and its lengths. As compared to the software-based solutions, the Ternary content-addressable memory can offersustained throughput and simple system architecture. It is attractive for IPv6 routing lookup. However, it also comes with several shortcomings, such as the limited number of entries, expansive cost and power consumption. Accordingly, an efficient algorithm is proposed in the paper to reduce the required size of Ternary content-addressable memory. The proposed scheme, which has a good effect, can eliminate 98 percentages of Ternary content-addressable memory entries by adding tiny DRAM. KeywordsIPv6 Routing Lookup TCAM1 引 言由于国际互联网和电子商务的飞速发展、网络接入需求呈指数级增长、国际互联网正面临着IPv4地址损耗问题，所以网络管理员必须越来越多地依赖NAT(网络地址转换)技术来配置网络。

第29卷第3期山东通信技术V oI．29N o．3 1竺!竺!星叁塾堡堡呈堡篁竺些竺竺!!竺!竺!呈!坠竺!竺壁垒!呈；!竺!I Pv6路由查找算法研究陈祥云(南京邮电大学计算机学院，南京210003)摘要：随着I nt em et的发展，路由信息不断增加，路由表急剧膨胀，路由查找问题已经成为影响网络通信速度的重要因素。

I Pv6的应用将使这一问题更加突出，而当前已有的针对I Pv4提出的算法很难满足I P v6快速路由查找的需要。

本文在详细分析I Pv6地址体系结构的基础上，对当前I Pv6主流的三种路由查找算法(TSB、B TL盯、D B H)进行了深入对比研究。

关键词：I P v6网络地址结构路由查找算法1引言随着I nt e m et规模的急剧膨胀．I nt er net上的主机数目正在成指数方式增长，应用业务的多元化导致网络流量的迅速增加。

电子商务等应用则对网络安全性提出了更高的要求。

l Pv6正是在人们对IPv4协议的地址空间、性能以及安全性等方面提出更高要求的情况下应运而生的。

为消除网络流量增加所带来的影响。

保证I nt em e t的服务质量，必须让数据包能够及时转发。

影响数据包转发速度的主要因素有三个：链路传输速度，路由器的数据处理能力和路由查找速度。

前两个因素目前已经有了较好的解决方案，而第三个因素则成为数据包转发速度的瓶颈。

当前已有的口路由查找算法大多是针对I P v4的，而其中的绝大多数并不适合于I Pv6。

因此，有必要进行针对I Pv6的高速路由查找算法的研究。

以提出适合I Pv6的高速路由查找算法。

2口v6地址体系结构2．1矾6地址表示I Pv6地址有128位．是l Pv4地址长度的4倍。

R FC l884规定的标准语法建议把I Pv6地址的128位(16个字节)写成8个16位的无符号整数，每个整数用4个十六进制位表示，这些数之间用冒号分开，例如：2001：2002：l f01：l：280：6702：f e4d：3eef o某些I Pv6地址中可能包含一长串的“0”。

IPv6网络中路由优化算法研究随着互联网的不断发展，IPv4地址的不足问题日益突出，IPv6作为IPv4的升级版逐渐得到广泛应用。

IPv6网络中的路由优化算法是保证网络性能的重要手段之一。

本文将介绍IPv6网络中路由的基本原理、路由优化算法的分类以及当前研究的热点与难点。

一、IPv6网络中的路由原理IPv6网络与IPv4网络类似，是由若干个网络组成的互联网络。

IPv6地址是由128位二进制数表示，相对于IPv4的32位地址具有更多的地址空间，可以支持更多的终端设备接入互联网。

IPv6网络的路由原理与IPv4基本相同，即在网络中搜索目标地址的最短路径。

IPv6路由协议主要有三种：RIPng、OSPFv3、BGP4+。

其中，RIPng是一种基于距离向量的路由协议，OSPFv3是一种基于链路状态的路由协议，BGP4+是一种面向自治系统（AS）的路由协议。

不同的路由协议有不同的路由表构建方式、更新策略和算法。

二、路由优化算法分类路由优化算法的分类可以根据其实现方式、性能指标和适用场景进行。

下面将介绍一些常见的路由优化算法分类。

1. 基于距离向量的路由算法基于距离向量的路由算法是一种轮询式的路由算法，每个节点都会周期性地向周围的邻居节点发送更新信息，以便更新路由表。

常见的基于距离向量的路由算法有RIPv2、RIPng等。

2. 基于链路状态的路由算法链路状态路由算法是一种基于节点之间传输链路状态信息的路由算法。

它通过节点之间的交换信息以了解网络的拓扑关系，并计算最短路径。

常见的基于链路状态的路由算法有OSPF、OSPFv3等。

3. 路径短时间算法路径短时间算法是一种考虑网络拓扑关系和数据包传输路径的路由算法。

它可以根据网络的实际拓扑和链路状况确定最短路径，并支持灵活的带宽、负载等路由策略。

常见的路径短时间算法有Dijkstra算法、A*算法等。

4. 混合型路由算法混合型路由算法是一种将基于距离向量和基于链路状态的路由算法相结合的路由算法。

基于IPv6的路由查找算法的研究与设计Internet的快速发展使链路上传输的数据速度达到了 400Gbps,导致路由器的吞吐量和查找最佳出口的工作量也大大增加。

路由器对每一个经过的数据报转发的快慢即路由转发速率是影响当前互联网数据吞吐量的关键,路由转发过程中的关键是路由表查找,因此设计一个合适的路由查找算法十分必要。

相比于IPv4,IPv6的地址长度更长,这意味着IPv6的路由表表项数会更多,基于前缀长度的IPv4查找算法不能直接扩展到IPv6的查找。

论文围绕基于IPv6的路由查找算法展开,分别给出了适用于目前路由表和将来大规模IPv6路由表的路由查找算法。

主要工作包括:1、对IPv6单播地址结构和当前骨干路由器路由表分布特点进行了解析,提出了一种B-树和Bloom Filter 相结合的IPv6路由查找算法(BTBF)。

BTBF首先利用2-3树查找前缀前16bits值,如果正确匹配2-3树节点,那么通过节点中的位数组对于Bloom Filter的映射,将下一步查找转发到Bloom Filter。

再计算Bloom Filter计数数组的二进制值通过Hash的方式映射到目的IP地址的存储位置从而获取下一跳。

实验结果表明,BTBF相比于其他树形类和Bloom Filter类算法有效减少了查找时间和存储空间占用,能在路由表项数变化较大的情况下维持稳定的查找性能。

2、基于二进制比特的Trie型数据结构面对大规模IPv6路由表时查找困难,因此引入了前缀区间的概念以适应大规模动态IPv6路由表查找,提出了一种段表与B-树相结合的IPv6路由查找算法。

以α位为分割点将路由前缀分隔为前缀Indexα(P)和后缀Suffixα(P),Indexα(P)保存在段表中,段表为一个顺序表,可以根据的不同分别存储在段表的不同位置,具体的存储形式为Set(i),i前缀Indexα(P)的值。

当段表查找阶段匹配成功后可以索引到B-树,然后在B-树中查找后缀Suffixα(P),并利用Cover(x)数组存储被节点区间包含的数据以解决B-树查找歧义问题。