IPv4网络与IPv6互联网的无状态通信机制
IPv4/IPv6过渡；无状态翻译；哈希函数；可扩展性；可溯源性
中图分类号： TP393.071
文献标志码：A
Abstract：
In the IPv4/IPv6 transition process， since some legacy IPv4 networks still need to communicate with the IPv6 Internet， the stateless communication mechanism between an IPv4 network and the IPv6 Internet， which complements the current IPv4/IPv6 translation framework， was proposed. First， the communication procedures in two related scenarios were demonstrated. The two scenarios include IPv6 Internet clients accessing IPv4 servers and IPv4 clients accessing IPv6 Internet servers. The oneway IPv6IPv4 address mapping function is the key component of the mechanism. Therefore， the requirements and three quantitative criteria of the oneway mapping function were discussed. Afterwards， multiple Hash functions as the candidates of the oneway mapping function were compared and analyzed with the real user data of large IPv6 websites and real IPv6 server addresses. The simulation results show that the FarmCity Hash function is suitable to be deployed in the above two scenarios because it has short average processing time， low collision rate and low reverse query complexity. It also verifies the validity of the stateless communication mechanism. Compared with current stateful communication mechanisms， the stateless mechanism has better scalability and traceability. Moreover， the capacity for bidirectional communication facilitates a smooth migration path towards the IPv6 Internet.
英文关键词Key words：
IPv4/IPv6 transition； stateless translation； Hash function； scalability； traceability
0引言
由于全球IPv4地址的耗尽，由IPv4向IPv6的过渡势在必行，但IPv6从设计之初便与IPv4并不兼容。在众多的IPv4/IPv6过渡技术中，无状态IPv4/IPv6翻译技术[1-3]使得新建的IPv6网络能与现有的IPv4互联网双向互联互通，因此能够有效地促进IPv4到IPv6的过渡进程。同时，由于在无状态翻译场景中，IPv4和IPv6地址之间的映射基于固定算法[2]，因此互联网服务提供商（Internet Service Provider， ISP）可以对IPv4用户和IPv6用户进行统一管理，包括流量管理、用户过滤、有效溯源等操作[4]。
在IPv4到IPv6的过渡过程中，仍有一些IPv4网络尚需要时间过渡到IPv6，但仍需要和IPv6互联网互联互通。比如一些信息资源提供商（Information Content Provider， ICP）需要被IPv6互联网的用户访问，或者一些IPv4的接入网希望能访问到IPv6互联网上的资源。现有的技术并不能很好地解决这个问题。NATPT（Network Address TranslationProtocol Translation）[5]能解决纯IPv4节点和纯IPv6节点相互通信的问题，但由于其不可扩展性和复杂性已经被国际互联网工程任务组（Internet Engineering Task Force， IETF）废弃[6]。NAT64有状态翻译技术[7-8]能解决IPv6互联网访问IPv4网络的问题，但是需要边缘设备为每个会话动态分配一个IPv4地址和端口，并保存和跟踪相应的会话状态。当有大量的用户访问时，翻译网关需要对大量会话粒度的状态作更新和同步，并需要作详细的日志记录。这些复杂的操作会影响到该翻译网关的性能，容易形成单点故障并降低网络应用的用户体验。同时，由于IPv4网络中的服务器记录的IPv4源地址都是动态生成的，在服务端想要区分用户或对用户作溯源就变得非常困难。而NAT64技术不能解决IPv4网络访问IPv6互联网的问题。 5）后续报文直接查表，无需使用上述单向映射函数。
如步骤2）和4）所示，使用端口移位的方式处理冲突，即将发生冲突的若干IPv6地址存储在一个链表中（链接法），并更改其源端口保证不同会话映射后的五元组依旧不同。这就要求单向映射函数能达到好的反向查询性能，即反向查询某IPv4地址的期望时间复杂度最小。
对ICP中的IPv4服务器来说，如果单向映射函数的冲突足够少，其日志记录的每个IPv4用户地址都可以通过静态映射表找到源IPv6地址，因而实现了较好的溯源性和安全性。同时静态的映射也方便网络管理员作用户过滤、流量管理等操作。静态映射表可以存储在和翻译器有高速链路的带外数据库或内存中。
1.2.2场景二：IPv4网络访问IPv6互联网
此场景可用于ICP的IPv4服务器访问IPv6互联网，或者尚未升级到IPv4的接入网络访问IPv6互联网，或其他类似的应用情况。如图2（b）所示，IPv4网络用户访问IPv6互联网服务器的步骤如下所示：
1）IPv4用户请求目标服务器的IPv6地址。
2）DNS查询服务器的AAAA记录，使用单向函数映射为IPv4地址（映射3）并返回给IPv4用户。映射完成后，在静态映射表中记录映射关系，如有冲突作二次映射并记录，也可根据用户经常访问的网站事先制作为静态彩虹表。
3）IPv4用户发送IPv4报文。
4）无状态翻译器翻译IPv4报文并发送至IPv6服务器。源IPv4地址被无状态映射到IPv6地址（映射1），目标IPv4地址通过查询静态映射表映射为相应IPv6地址。
5）IPv6服务器返回IPv6报文。
6）无状态翻译器翻译IPv6报文并发送回IPv4用户。目标IPv6地址被无状态映射回IPv4地址（映射1），源IPv6地址通过查询静态映射表映射为IPv4地址。
7）后续报文直接查表，无需使用上述单向映射函数。
场景二与场景一的不同之处在于DNS作单向映射函数时，仅能查询地址，不能对端口进行修改。但是，只要用户访问的IPv6目标地址在已知范围内，因此总可以设计完美哈希函数为这些目标地址事先建立好映射关系表，并存储在和翻译器与DNS均有高速链路的数据库或内存中。
综上，本文设计了IPv4网络和IPv6互联网之间的双向无状态通信机制，通过引入IPv6地址到IPv4地址的单向哈希函数，使得解决方案具有良好的可溯源性和网络运维性。与现有的无状态IPv4/IPv6翻译机制相结合，对处于IPv6过渡期的大型ICP来说，无论服务器是IPv4还是IPv6，都能无状态地为IPv4互联网和IPv6互联网提供服务。
该机制的关键是设计一个好的IPv6IPv4地址单向映射函数，下面将对该函数的设计需求和评价标准作简单介绍，并针对需求设计合适的映射函数。
2IPv6IPv4地址单向映射函数设计
2.1设计需求
IPv6IPv4单向映射函数将128位的任意IPv6地址映射到IPv4地址空间的某个子集S中，如图1（b）中影线阴影部分所示。在上述两个场景中，由于IPv4网络通常还要与IPv4互联网通信，因此S应不包含服务器所在的IPv4子网以及所有公网IPv4地址。如果服务器未使用私有IPv4地址，则S可包括私有的地址块和互联网数字分配机构（Internet Assigned Numbers Authority， IANA）保留的地址块[12]（这些地址不会进入全球路由表）。针对不同的应用场景，S应调整至|S|达到最大。一般情况下，10.0.0.0/24私有地址块和IANA预留的IPv4地址块足够提供226大小的值域范围。
不失一般性，本文仅考虑S仅包含一个IPv4子网的情况。事实上，如果S包括多个IPv4子网，可以建立一个虚拟的子网S1，其大小为|S|，且与S之间建立简单的一一映射的关系。这样将IPv6地址空间映射到S1就等价于映射到S。
在场景一中，一些服务器需要在映射时对用户的源IPv6地址保持前缀，即有特定长度公共前缀的IPv6地址能映射到同一个IPv4子网中，以便更精细的用户管理。假设单向映射函数为f，IPv6地址空间为G6，希望将公共前缀长度至少为l6的IPv6地址映射到一个前缀长度至少为l4的IPv4子网中去，则该需求可表示为：
A16，A26∈G6， A16∨A26≥l6 f（A16）∨f（A26）≥l4
2.2单向映射函数选择与设计
目前研究较为成熟的哈希算法可直接用作本文中的单向映射函数。常用的哈希函数包括MD5、SHA1、SHA256、SHA512、SHA384、SHA224（加密哈希函数[13]）、RS、PJW、ELF、DJB、BP、FNV[14]、CityHash[15]、FarmHash[16]（非加密哈希函数）等。其中：非加密哈希函数通常用于字符串压缩，只要指定源字符串的字节数为16，便可用于IPv6地址的映射；而加密哈希函数（MD5或SHA家族）通常将512比特（64字节）或1024比特（128字节）视为一个区块进行计算，在映射IPv6地址时，处理时间可能会相对较长。
根据值域|S|的大小不同，需要对上述哈希函数的输出作截位处理。只要哈希函数的输出分布足够均匀，从任何位置截位都可以得到均匀分布。
在场景一中，为满足保持前缀的映射需求，本文使用分段哈希函数。假设值域|S|是一个前缀长度为l的子网，IPv6地址A6通过分段哈希函数映射为A4，则有：
f1（A6[1，l6]）=A4[l+1，l+l4]
f2（A6[l6+1，128]）=A4[l+l4+1，32]
如第3章所示，选择不同的l6和l4会影响到哈希函数的性能。因此服务器应谨慎选择以上参数，以便在保持前缀和冲突率两者之间取得合适的折中方案。 在场景二中，如果目标IPv6服务器数量较少，可直接使用上述哈希函数制作静态映射表。当上述哈希函数的冲突率较高时，只要IPv6服务器数量小于IPv4子网大小，可以通过设计完美哈希函数[17]提供冲突率为零的静态映射。
2.3评价标准
评价IPv6IPv4地址单向映射函数的指标包括处理时间和冲突频率。在具体的应用场景中，管理员应选择处理时间短且冲突频率低的单向映射函数。对于场景一的单向映射函数，评价指标还包括反向查询复杂度。为提高映射操作的效率，管理员也应选择反向查询复杂度较低的单向映射函数。
处理时间表示单向映射函数处理一个IPv6地址平均所用时间。处理时间的绝对值与运算平台相关，在同一平台下，处理时间越短的单向函数越好。
冲突频率表示对于一组特定的IPv6地址集，单向映射函数生成的IPv4地址的重复频率。冲突频率越小的单向函数越好。假设IPv6地址集有N个IPv6地址，值域S包括M个IPv4地址，其中N>M。Ni表示映射到第i个IPv4地址的IPv6地址个数，若Ni>1则冲突个数为Ni-1。冲突频率可表示为：
p=1N∑Mi=1（Ni-ε（Ni-1））=1-1N∑Mi=1ε（Ni-1）
其中ε（x）为阶跃函数：
ε（x）=
1，x≥00，x<0
显然，要使冲突频率最小，需使Ni>0的IPv4地址数量最多，即N个IPv6地址映射到不同的N个IPv4地址。
场景一中的反向查询复杂度表示将一组IPv6地址映射至IPv4地址集合S0后，由S0中的IPv4地址反查IPv6地址的期望时间复杂度。期望时间复杂度越低的单向函数越好。由于相同IPv4地址通过端口移位处理冲突，因此反查某个IPv4地址时，需要遍历其对应的所有IPv6地址，直到匹配到某个移位后端口为止。假设每个IPv6地址出现的概率均为N-1，则第i个IPv4地址需要查询的期望次数为：
E（Ti）=1Ni（Ni+∑Nij=2j）=N2i+3Ni-22Ni，Ni≥2
1，Ni=1
0，Ni=0
总体的期望查询次数为：
E（T）=1N∑Mi=1NiE（Ti）=12N∑Mi=1（N2i+3Ni-2）ε（Ni-1）=12N∑Mi=1N2i-1N∑Mi=1ε（Ni-1）+32=12N∑Mi=1N2i-（1-p）+32=12N∑Mi=1Ni-NM2+N2M+p+12=M2Nσ2+p+N+M2M
因此，期望查询次数与Ni的方差σ2及冲突频率p成线性正相关。由于两者都在一一映射时达到最小值，代入可得总体期望查询次数最小值为1。在冲突频率相同的基础上，σ2越大，期望查询次数越多，因此该指标也反映出映射函数的平衡性。
3实验验证
本文采集了中国教育与科研计算机网站点2014年的访问日志数据，提取出1个月、3个月、6个月、9个月和12个月的独立IPv6地址集合，集合大小分别为14万、48万、125万、182万和270万。在此数据基础上，分析比较了在IPv6互联网访问IPv4网络场景（场景一）中，2.2节提到的常用哈希函数的性能。针对场景二，本文采集了目前流行的19万个IPv6网站，共解析出4.8万个可访问的IPv6服务器地址，并分析了不同哈希函数的效果。
五个数据集合的实际大小分别是：142424，486408，1252455，1822369，2708955
服务器地址实际数量是48666
3.1处理时间比较
本文的实验环境为Inter Core i7 2.7GHz CPU，4GB 1333MHz内存和MAC OS Yosemite 64位操作系统。针对上述IPv6地址集合，计算各哈希函数映射一个IPv6地址的平均处理时间，如图3所示。
可以看出，加密函数的处理时间通常比非加密函数处理时间要长一些。在加密函数中，处理时间较短的有MD5和SHA1，而本文列举的非加密哈希函数处理时间均在2～2.2μs，较加密哈希函数有明显的优势。
3.2冲突频率比较
首先设置哈希函数的值域是整个32位IPv4地址空间，比较各种哈希函数的冲突频率p与IPv6集合大小N之间的关系，如图4（a）所示；接下来固定N为125万（6个月IPv6地址数量），修改输出值域的大小M，比较各种哈希函数的冲突频率p与M之间的关系，如图4（b）所示。
可以看到，当M不变时，冲突频率随着N的增长而变大；当N不变时，冲突频率随着M的增长而变小。该结果与泊松装填模型[18]相吻合，即冲突概率与装载因子（N/M）成反相关关系。相比其他哈希函数，BP、ELF、PJW和DJB四个哈希函数的冲突概率明显大很多。在值域为32位IPv4地址空间条件下，输入48万个IPv6地址集合时，绝大部分哈希函数的冲突频率均小于万分之一；当输入125万个IPv6地址时，绝大部分哈希函数的冲突频率均小于万分之二。在值域为26位IPv4地址空间条件下（10.0.0.0/24和IANA预留的IPv4地址块足够提供226大小的值域），输入125万个IPv6地址时，绝大部分哈希函数的冲突概率小于百分之一。也就是说，在IPv4到IPv6过渡初期，一个IPv6独立用户数量在125万以下的IPv4网络均可使用本文所述机制为IPv6互联网提供无状态访问服务，且冲突概率非常小。当IPv6用户逐渐增多时（达到几百万或几千万的量级），哈希函数的冲突率会逐渐增加，这时管理员可每隔一段时间（如一个月）更新一次静态映射表，根据实验结果，冲突率仍可以降到万分之一以下。当IPv6用户继续增加时，管理员应考虑尽快将服务器升级到纯IPv6，使用1.1节所述机制为IPv4/IPv6互联网提供服务。 3.3反向查询复杂度比较
本文还比较了各种哈希函数的反向查询复杂度与各IPv6地址集合大小之间的关系，如图5所示。可以看出，对同一个哈希函数，反向查询复杂度和IPv6地址集合大小成正相关关系。除BP、ELF、PJW（与ELF的数据相同）和DJB四种函数外，其他哈希函数均可以实现较小的反向查询复杂度。因此，本文所述机制可以实现较快的反查性能。
3.4设计冲突率低的分段哈希函数
针对场景一中保持前缀的需求，对分段哈希函数进行仿真实验，值域为32位IPv4地址空间。对不同的l6和l4取值，使用性能较好的FarmHash函数分别对IPv6地址的两段进行映射。在N为125万（6个月IPv6地址数量）条件下，不同l6和l4取值对冲突频率的影响如图6所示。
可以看出，当l6等于48位时，l4大于5位就会使冲突频率迅速增长，说明IPv6用户地址在前48位的分布均匀性要比后80位差很多。这是由于目前IPv6前缀数量很少，仅用少数几个比特来表示便可以，而后80位尤其是后64位通常包含了用户的MAC地址信息或者随机生成的标识信息，信息量巨大，因此需要占用很多比特来表示。当l6大于96位后，l4也应增加到20位才能保持较低的冲突率。因此，管理员应考虑到IPv6地址的分布特征，合理选择l4和l6，以便在保持单向映射的无状态特性的同时更好地对用户进行管理。
3.5场景二的冲突频率
本文采集了目前流行的19万个IPv6网站，共解析出48万个可访问的IPv6服务器地址，使用上述各哈希函数对这些IPv6地址进行单向映射，比较其各自的冲突频率。实验表明，当值域为32位IPv4地址空间时，除BP、ELF、PJW和DJB外的哈希函数至多发生一次冲突；而当值域空间为226时，如表1所示，除BP、ELF、PJW和DJB外的哈希函数的冲突数均不超过25个，其中FarmHash函数仅发生8次冲突，冲突率仅0016%。实验表明，本文所述无状态机制也可很好地适用于场景二。
综合本章所述，FarmHash哈希函数可用于IPv6互联网与IPv4网络相互通信的两种场景中，具有处理时间短、冲突频率低、反向映射复杂度小等优点，验证了本文所述无状态机制的可行性。本文并未列举出所有的哈希算法，但其他可很好满足三项指标的哈希算法亦可应用于本文所述场景中。
4结语
本文提出了IPv4网络与IPv6互联网双向无状态通信机制，是对已有无状态IPv4/IPv6翻译技术的有效补充，形成了统一的无状态IPv4/IPv6翻译框架。该机制的关键在于设计一个好的单向映射函数，因此本文提出了处理时间、冲突频率和反向查询复杂度三个定量的评价标准，并用实际数据对不同的哈希函数进行了分析和比较。实验表明，FarmHash哈希函数能同时满足处理时间短、冲突频率低、反向映射复杂度小等要求，从而验证了该机制的可行性。与现有的有状态通信机制相比，该机制具有良好的可溯源性和网络运维性，可以很好地满足过渡过程中的需求，提供了一个平滑的IPv4/IPv6过渡路线。当IPv6用户大规模增加时，该IPv4网络应直接升
级为IPv6，使用1.1节所述无状态机制为IPv4/IPv6互联网提供服务。
