舰船网络别名解析算法研究

孙明思，李 斌

（1.吉林农业科技学院电气与信息工程学院，吉林吉林 132101；2.哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨 150001）

0 引 言

近年来，无线通信技术、半导体技术、物联网技术和计算机网络技术的迅猛发展，船舶通信和网络系统能力得到了很大提升。但是，随着舰载数据中心[1]、舰载物联网和舰载通信技术的引入，舰载通信系统具有舰间通信、舰岸通信和舰空通信等三维立体通信能力。舰船具有跨域航行特点[2]，导致舰船与岸基网络通信时，无法及时有效地解析IP 地址。

传统的单调别名解析方法（Monotonic ID-based Alias Resolution，MIDAR）属于稳定拓扑解析，不存在由于舰船跨域或者跨国家行驶，导致被解析地址变更和延迟问题。所以，传统的MIDAR 无法提供稳定的跨域域名解析服务。舰船网络规模和行驶范围越来越大，网络构成越来越复杂。准确地描绘网络的拓扑结构有助于发现网络瓶颈，定位网络故障，为舰载数据中心和舰载信息系统提供稳定的网络服务，从而进一步保障舰船行驶安全。

目前MIDAR 算法[3]在已有的基于IP ID 别名解析算法的基础上，提高了IP 别名对的准确率，增加了探测的规模，在实际网络探测中取得了比较好的效果。本文在MIDAR 算法的基础上，通过大数据IP 地址分类和IP 别名解析对的“噪音”过滤来降低舰船跨域网络解析问题，通过响应时间消除潜在别名解析对提高解析准确率。

1 舰船网络IP 别名问题描述

路由器通常有多个接口，每个接口至少配置一个IP地址，路由级拓扑发现是将路由器的不同接口在网络中用一个节点表示的过程[4]。如果不能将路由器的不同接口合并，会出现一个路由器因为有多个接口存在而在网络中用多个节点表示的情况，生成的拓扑不能反映真实的网络连接情况[5]。与此同时，在对网络拓扑进行探测的过程中，难以用唯一的标识来表示一台路由器，这样就使正确描绘网络拓扑情况变得非常困难，对了解真实网络的拓扑结构带来挑战。

在图1 的舰船网络中，舰船A 的网络设备和舰船B的网络设备是探测源点。舰船A 通过卫星通信连接岸基卫星基站登录互联网，舰船B 通过近岸基站连接互联网。R 作为中间进行转发数据包的路由器，其中I1，I2和I3 是路由器R 的不同接口地址，C 是探测的目的节点，即远端数据中心。图2 展示了舰船网络的探测路径。通过IP 探测技术，船舶A 和B 分别经过两条单独的IP 路径访问云端数据中心。而在实际的舰船网络中，舰船A 和B 经过同一路由器的相同端口访问云端数据中心，这样就产生了IP 别名解析误差，需要这种符合实际的物理端口进行合并。

图1 舰船网络实际路由链路Fig.1 Real router link in the ship network

图2 舰船网络探测的IP 链路Fig.2 Probed IP link in the ship network

2 舰船网络别名解析算法

由于舰船经常大范围跨域移动，导致别名解析准确率低的问题，并且在别名解析过程中对网络流量产生很大影响。因此，本文以MIDAR 为基础，从IP 地址分类、别名对降维和潜在别名对消除等三个方面入手，减少别名解析规模，提高解析的效率和精度。本文使用Caida Ark 项目提供的IP 链路探测数据集，并根据该数据集模拟船舶大范围航行引起的大规模别名解析环境。

2.1 IP 地址集分类

根据IP 地址划分IP 物理位置，可以大大减少后续别名解析对的匹配过程，提高匹配效率和准确性。属于同一个路由器的IP 地址必然具有相同的地理位置，不同路由器的IP 地址可能具有不同的地理位置。因此，基于以上思想建立IP 地址相似性的树形聚类算法。

具体做法为：首先从收集到的IP 地址中过滤出所有私有IP 地址，即保留的和适用于局域网内的IP 地址；然后采用Geo IP 数据库查询IP 地理信息，IP 地理信息主要包括洲、国家、省/州、市和街道，以及相应的经纬度。依据地理信息建立树形结构，并根据查询结果将IP地址放入到对应的节点上。最后，统计每个地区路由器接口地址出现的次数。

在一个完整探测周期内探测到10 918 370 个不同的IP 地址，按照地理位置划分了75 606 个不同的国家和地区。这就将原问题的求解过程转换为75 606 个子问题的求解过程，降低问题的规模。出现路由器接口数量最多的地区是美国，大约有150 万个不同的IP 地址。如图3 所示为各地区IP 地址数量。

图3 各地区IP 地址数量Fig.3 Number of IP address in diverse areas

2.2 IP 别名解析对降维

首先收集了分布在世界30 个探测点的全球网络进行探测数据，探测空间是IPv4 前24 位所有的地址共生成10 129 123 条探测路径[6-7]。在完整探测周期内，共探测到132 371 209 个IP 地址，去掉重复出现的地址以后得到10 918 370 个各不相同的IP 地址。这种现象从侧面可以反映出探测过程中存在大量的探测冗余。统计各个IP 地址在探测过程中出现的次数，可以明显发现探测过程中只出现1 次的IP 地址占了绝大多数。通过分析在一个完整的探测周期内只出现一次的IP 地址很大可能是网络的边缘节点，但通过直观感觉网络中的边缘节点不可能占有那么大的比例。

接下来对这些数据进行统计发现，出现1 次的IP 地址共有10 266 454 个，占探测到的IP 地址数量的94%。由于探测过程中可能引入“噪声”，所以在探测周期内出现1 次的IP 地址有两种可能：

1）来自路由器接口地址，该接口在探测周期内只被探测到一次；

2）非路由器接口地址，只有一种可能就是该地址来自探测的目标地址集合。

首先将只出现一次的IP 地址加入一个集合S1中，从收集到的原始探测数据中找出所有的目的地址，将这些目标地址加入到集合S2中，然后从集合S1中去掉S1和S2的交集。通过计算得出10 266 454 个（S1）出现1 次的IP 地址中有307 428 个IP 地址来自路由器接口地址，有9 959 026 个IP 地址是来自探测的目标地址集合S2。这些来自探测目标地址集合的IP 地址一部分是未分配的IP 地址，一部分是分配给主机的IP 地址。所以需要将这9 959 026 个IP 地址从探测到的IP 地址集合中去除，这样就将探测到的IP 地址空间从千万级降低到百万级别，大大降低问题的规模，为后续阶段的处理提供方便。

2.3 潜在IP 别名对的消除

用MIDAR 算法对所属同一个IP 地址集合进行别名解析，将IP 地址集合用具有相似IP ID 的增长率的IP 地址进一步划分成更小的集合。得到的IP 地址集合是潜在的IP 别名对，对这些潜在别名对用以下基于响应时间的别名解析算法进行处理，得到最终处理的IP 别名对，达到IP 别名解析的目的。

判断两个候选别名IP ID 值的顺序是否一致，也就是说，所产生的值的递增顺序应该与使用共享计数器一致。因为IP ID 值的范围是0～65 535，定义符号X＜Y表示序列空间的小于关系。使用下列步骤来判断地址A和B是否是别名。首先，发送一个探测数据包给A，等待1 ms，然后发送探测数据包给B。假设响应数据包的IP ID 值分别为A1和B1。检查A1和B1顺序是否一致，并且彼此靠近，即A1-10＜B1＜A1+200。如果在这个范围，等待400 ms，发送探测数据包给B，等待1 ms，然后发送探测数据包给A。随后检查B2和A2的IP ID 的值是否在B2-10＜A2＜B2+200 的区间，并满足A1＜A2和B1＜B2的条件。如果这些条件都能得到满足，则判断A和B是别名，否则判断A和B不是别名。

由于无法知道收集到的IP ID 生成的确切时间，因此在比较值的时候使用了一个误差范围。间隔1 ms 发送探测数据包，由于网络中存在负载平衡等其他因素，会导致数据包在网络中出现路由不一致的现象。但是这并不影响对两个IP 别名对的判断。

3 实验验证与分析

使用两组真实的数据集对算法进行验证。R&E是由研究和教育网络提供的一个已知网络拓扑（CAnet，CENIC，GEANT，I-Light，Internet2 和NLR），Tier1 是一个由一级ISP 提供的已知网络拓扑。首先采用随机选取不同物理地址的方式模拟舰船大范围跨域航行，并在该条件下验证算法是否能与已知网络拓扑的别名情况达成一致。

本文采用2017 年3 月份的数据进行实验对比，用TCP 的探测方式对Tier1 和R&E 数据集分别做探测，分别用时30.1 s 和13.1 s。请注意，该测试没有针对整个MIDAR 系统，特别是没有测试多个测量方法、多个阶段或自适应探测间距。本文算法和MIDAR 的运行结果如表1 所示。表1 中，TP 为判断正确的正确率，FP 为判断错误的正确率，PPV 为精确率，即计算为正确的数据中计算正确的数量，PPV 由TP（/TP+FP）计算而得。

表1 实验结果对比Table 1 Experimental results of different methods

如表1所示，Tier1和R&E 数据集的待测试别名对数量分别为62 817和2 307。Tier1是R&E 数据量的27倍，说明Tier1 解析范围更大。对比较大的数据集Tier1，本文算法在别名解析的精确率上好于MIDAR 算法，得到的错误别名对也少于MIDAR 算法。相比MIDAR 算法，本文提出的算法精度提高了17%。在Tier1 数据集上，本文提出的算法与传统的MIDAR 算法正确判断的正确率相当，解析错误判断的正确率优于传统MIDAR。从而，本文提出算法精确率优于传统MIDAR。但是对于R&E 规模较小，无法体现大规模解析环境，这两个算法没有明显区别，别名解析的正确率和错误的别名对数量都相差不大。因此可以得出结论，本文算法在别名解析的精度方面提高显著。

4 结 论

舰船网络的稳定对舰船安全行驶具有重要作用。舰船跨域行驶对传统固定IP 别名解析方法提出了挑战。特别是在跨区域、跨国家的行驶过程中容易产生错误解析别名对数量呈非线性增长的情况。本文通过改进MIDAR 算法，通过IP 地理和主机划分两种策略，在解析前缩减解析规模，并且将问题划分为若干个互不相关的子问题进行别名解析，在准确性和效率等方面都取得了良好的效果。在后期通过响应时间对解析出的潜在别名对进行验证，相较传统MIDAR 方法，本文方法提高了17%的准确率。因此，本文提出的方法实现了舰船跨域行驶中的舰船网络别名解析功能，并具有较高的准确率，为舰船网络的安全稳定提供了一个有效的解决思路。