IPv4向IPv6过渡隧道路由查找算法研究

摘 要 Internet网络迈向IPv6网络是大势所趋，但IPv4网络规模庞大，部署了大量的网络应用，因此IPv6取代IPv4并不是一蹴而就的，其将长期共存并平滑过渡。IPv4向IPv6过渡技术主要有双协议栈技术、翻译技术和隧道技术，隧道技术又细分为配置隧道和自动隧道，从灵活性和方便性看，IPv6自动隧道技术是理想的IPv4向IPv6过渡的技术，该技术主要关注如何有效的建立IPv6自动隧道路由转发表。本文的主要工作是：提出了一种基于TCAM的IPv6-in-IPv4自动隧道层次化的路由查找算法，降低了算法空间复杂度。

关键词 IPv6；隧道；TCAM

中图分类号U45 文献标识码A 文章编号 1674-6708（2013）99-0224-02

0 引言

IPv4网络在新形势下面临诸多的挑战，包括IP地址数量不足，服务质量保障能力不足，安全性不足，对移动互联网支持不足等一系列问题。因此，在2006年ITEF会议中， 明确IPv6为下一代互联网协议 。但 IPv6取代IPv4并不是一蹴而就的，其将长期共存并平滑过渡。2011年12月23日，国务院召开常务会议，提出了平滑过渡策略：“2014年至2015年，开展大规模部署和商用，实现国际互联网协议第4版与第6版主流业务互通”。 路由查找是路由器的核心技术，研究IPv4向IPv6过渡的高性能隧道路由查找技术具有重要的现实意义。

1 IPv6过渡技术研究综述

IPv6过渡技术研究的主要内容就是：IPv6孤岛之间如何通讯，以及IPv6网络如何与IPv4网络互通。目前IPv6过渡技术主要有3种：双栈技术（Dual Stack），协议翻译技术（NAT-PT）和隧道技术（Tunnel）。

双栈技术是所有过渡技术的基础，主要用于IPv4网络和IPv6网络接壤的网络设备上配合其他过渡技术使用。

协议翻译技术破坏了网络的端到端特性，对应用扩展支持不好，对数据加密的场景支持不好，因此该技术已经被ITEF建议重新审查。

隧道技术用于IPv6网络孤岛和孤点穿越IPv4网络进行通讯，主要有：配置隧道，6to4自动隧道和ISATAP自动隧道。

2 现有隧道路由查找算法

链路带宽和接口速率的快速提升要求核心路由器每秒能够执行上亿次的路由查找性能，因此在高性能路由器领域，使用TCAM作为路由查找器件。IPv6自动隧道并没有相应的路由协议，因此在现有方法中，TCAM中的自动隧道路由转发表是通过监听数据流的方式获取：监听隧道数据流，从报文中取出的IPv4主机地址构造成隧道路由转发表， 示例如下：

上述的隧道路由表项建立方法是无状态的（即非通过协议学习到）且隧道路由寻址是扁平化的。这种方法的主要问题是：

1）通过监听数据流发现和创建路由转发表，大量的报文冲击CPU，导致CPU不堪重负；

2）该技术类似早期的路由查找Cache策略，只不过用TCAM来做Cache查找。自动隧道在通讯建立时自动建立，在通讯结束时自动撤销，其存在的时间短，导致TCAM频繁更新，影响转发性能，同时期数据流时间局部性不明，Cache策略加速效果不明显；

3）隧道路由转发是一种点到点的扁平结构，一个用户可能同时访问多个站点，那么就会为一个用户创建多条表项，TCAM容量本身就有限，这导致TCAM表非常容易溢出。互联网上的节点何止千万，其对TCAM表项的消耗是不可预期不可规划的。

3 层次化隧道路由查找算法

要解决现有方法问题要从两个方面入手：通过路由协议来获得隧道路由转发表，并采用层次化隧道路由寻址。IPv6自动隧道路由有特殊标识可以与普通IPv6路由转发表进行区分。自动隧道的IPv6地址中内嵌了IPv4主机地址，最终转发决策是通过用该地址进行IPv4路由表查找做出的，且IPv4路由转发表是通过路由协议学习到的，且具有层次性。基于上述2点分析，可将本机学习到的IPv4网络路由与IPv6自动隧道路由的特征值拼接，从而生成IPv6隧道网络路由转发表，使得隧道网络路由转发表继承IPv4网络路由的相对稳定性和层次性，从根本上解决隧道路由转发性容量和稳定性问题，方法定义如下：

1）6to4自动隧道：前缀=2002：IPv4网络前缀；前缀长度=16+IPv4网络地址前缀长度。2002是该类隧道的特征值；

2）ISATAP自动隧道：前缀=64bits前缀：0000：5EFE： IPv4网络前缀；前缀长度=96+IPv4网络地址前缀长度。0000：5EFE是该类隧道的特征值。

该方法将空间复杂度从不确定性降低到O（N * M），N=IPv4路由条目数， M=IPv6隧道前缀数。6to4自动隧道只有1个固定前缀2002/16， ISATAP前缀数量则是不确定的。由于隧道转发决策和IPv6前缀无关，因此ISATAP的IPv6前缀可以定义为任意64bits网络前缀，前缀数也可降低为逻辑上的1个，优化后如下：

ISATAP自动隧道优化：前缀=任意64bits网络前缀：0000：5EFE： IPv4网络地址前缀；前缀长度=96+IPv4网络地址前缀长度。

优化后M=2，算法空间复杂度就降低为O（2N）， 任意前缀可以在TCAM中用掩码掩掉，表达为X。采用上述方法后，隧道路由转发表示例如下：

TCAM-based IPv6路由转发表的主要采用CAO_OPT管理算法 。CAO_OPT算法要求网络前缀是连续的，而优化后的ISATAP隧道路由前缀不是连续的，因此需对现有管理算法进行改进。IPv6标准网络路由和层次化的6to4隧道路由前缀长度均 =96，因此先根据前缀长度分区，然后每个区间内采用CAO_OPT算法管理：

层次化的6to4隧道路由存放在“IPv6标准网络路由区”，位于TCAM的高地址段；层次化的ISATAP隧道存放在专门“ISATAP隧道网络路由区”，其位于TCAM的中地址段，IPv6主机路由则存放在TCAM的低地址段，从而满足LPM查找的需求。

4结论

普通路由转发表项来源于路由守护协议之间的通告，然而自动隧道并没有相应的路由协议，因此现有方法通过监听数据流的方式获取自动隧道路由转发表。因此其是一种不稳定的扁平化寻址，空间复杂度不可预期，因此本文对其进行了改进：IPv6隧道网络路由转发表是通过拼接IPv4网络路由与IPv6自动隧道路由的特征值得到的，其继承了IPv4网络路由的层次性，从而将IPv6自动隧道路由表项的空间复杂度从不可预期降低到了O（2N）。

参考文献

[1]毕军，王优，冷晓翔.IPv6过渡研究综述.电信科学，2008（10）：12-22.

[2]王晓峰，吴建平，崔勇.互联网IPv6过渡技术综述. 小型微型计算机系统，2006，27（3）： 385-395.

[3]郑凯. 高性能IP路由查找和分组分类技术的研究[博士学位论文]. 北京： 清华大学计算机科学与技术系， 2006.

[4]Shah D，Gupta P.Fast updating algorithms for TCAMS.IEEE MICRO，2001，1-2：36-47.