基于半监督聚类的局部网络拓扑测量任务选取方法

张晔 张宇

Abstract： This paper proposes a selection scheme of measurement task based on semi-supervised clustering， aiming at improving the discovery efficiency on IP addresses in local network that connected to external network. Three main approaches are conducted. Firstly， a small part of measurement tasks is selected to perform measurements as marker samples， and calculate centroids of all the known classes. Then， clustering is implemented using the distances from unlabeled samples to centroids. At last， measurement tasks are generated from the unlabeled samples that are far from all the centroids， by iterating this way until no any new class can be found. The parameters of the semi-supervised clustering are determined by the control variable. The measurement efficiency of the tasks is analyzed via the obtained number of IP addresses in local network that connected to external network. Furthermore， the aggregation ability of overall algorithm can be evaluated using clustering external indicator.

引言

網络拓扑测量是发现网络结构的一种重要方式，拓扑测量中以traceroute作为最常见的技术手段。Pansiot等人[1]最早运用traceroute来发现路由器级别的网络拓扑结构。20世纪末，南加州大学（university of southern California）开启了SCAN项目[2]，并发现了十五万的网络节点。CAIDA（Center for Applied Internet Data Analysis）的Ark平台从2007年开始一直在全球执行分布式拓扑测量。近年来，网络测量相关研究更加深入，Reza等人于2015年总结了之前十几年内研发的网络测量技术，对拓扑的粒度进行了细化，分为接口级别、路由器级别、POP级别和AS级别。同时，又专题讨论了每个级别的相关测量技术，再对其中的问题和限制做出了分析[3]；Holterbach等人[4]在2015年通过基于RIPE Atlas的开放测量平台的实验，发现多用户并发测量会影响测量精确度的问题，提出了设计测量平台亟需注意的各类因素；Augustin等人[5]则综合了多方的拓扑测量数据有效分析了IXP之间的连接关系。

互联网由大量的局部网络（AS自治域，国家）组成，分析局部网络如何与外部网络进行连接是了解网络拓扑结构的关键步骤。局部网络对外连接方式受商业关系、地理位置等因素影响，无法从运营商、IXP处直接获得大量局部网络对外连接信息，于是从traceroute测量结果中分析拓扑数据是获取相关信息的一种主要方式。在已有的网络测量工作中，主要通过对局部网络执行长时间、大规模的测量，最后从测量结果中获取局部网络对外连接IP地址。分析历史测量数据发现，大量的traceroute路径经过相同的局部网络对外连接IP地址，于是推测此现象和traceroute的测量点、目的节点相关。本文将以此为出发点，利用traceroute中测量点和目的节点的属性对测量任务进行半监督聚类[6-8]，旨在利用少量的已知测量数据预测traceroute的测量结果，选择最具测量意义的测量任务以减少不必要的测量，发现大量局部网络对外连接IP地址。最后，利用本算法选择多个局部网络的拓扑测量任务，研究得知只是选择3.5%的局部网络测量任务集就可以发现90%以上的局部网络对外连接IP地址，并利用聚类方法的评价标准[9]对算法进行评价，结果表明算法有良好的类别聚合能力，在实际测量工作有着很好的应用前景。

1局部网络的拓扑测量方法

1.1局部网络的测量任务集生成

Traceroute任务由测量点和目的节点组成。为了获取良好的局部网络的拓扑数据，就需要寻获数目众多、且呈发散式分布的一系列测量点。可以利用第三方网站（如traceroute.org）和搜索引擎（用Google搜索关键字Looking Glass）等方法来收集全世界的Looking Glass服务器，这些服务器以Web接口的方式提供免费traceroute测量服务，目前已收集稳定的1 000个服务器可执行traceroute测量，并且还设计了高并发测量系统调用测量点接口，所有接口可并发执行测量任务。为了更好地分析测量点属性来调度测量点，利用抓包工具获取测量点的源IP地址，分析源IP地址即会发现这些traceroute服务器分布在56个不同的国家和地区，满足分布广泛的需求。

测量局部网络时，从局部网络外的每个接口（部分接口有多个测量点）中轮流选择一个测量点加入测量点集；目的IP地址集需满足在局部网络中具有代表性且目的IP地址之间拓扑间隔较远的要求，先利用地理定位数据库（ip2Location）获取局部网络的IP地址段，按照设计的目的IP地址集规模对IP地址段进行切分，所有的IP地址段将切分成相同的规模，从每个IP地址段中随机选择一个活跃的IP地址（用ping测试是否连通）加入目的IP地址集。测量点集和目的IP地址集作笛卡尔乘积记为测量任务集，具体如图1所示，因此测量任务集中的每个任务元素为一次traceroute。