基于网络层析成像的IP网络路由器级拓扑识别方法研究.doc

电子科技大学UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA硕士学位论文MASTER THESIS 论文题目基于网络层析成像的 IP网络路由器级拓扑识别方法研究 学科专业信息与通信工程 201121010805杨季学号作者姓名指导教师胡光岷教授 分类号密级注 1UDC学位论文基于网络层析成像的 IP网络路由器级拓扑识别方法研究（题名和副题名）杨季（作者姓名）指导教师胡光岷教授成都电子科技大学（姓名、职称、单位名称）申请学位级别硕士学科专业信息与通信工程提交论文日期 2014.5.17论文答辩日期 2014.5.30学位授予单位和日期电子科技大学 2014年 6 月 30 日答辩委员会主席评阅人注 1：注明国际十进分类法 UDC的类号。 RESEARCH ON IP NETWORK ROUTERLEVEL TOPOLOGY BASED ON NETWORKTOMOGRAPHYA Master Thesis Submitted toUniversity of Electronic Science and Technology of ChinaMajor: Information and Communication EngineeringAuthor:Ji YangAdvisor:Prof. Guangmin HuSchool :School of Communication & Information Engineering 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名：日期：年月日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）作者签名：导师签名：日期：年月日 摘要摘要随着网络技术的发展，网络成为了现代社会中最重要的基础设施之一，已经渗透到了人们生活的各个方面。网络路由器级拓扑表征了网络中路由器之间的连接关系，可为网络规划、优化、管理提供有用基础数据，也是构建可信、安全网络环境的前提。现有路由器级拓扑识别方法主要依靠 traceroute等测量工具收集原始数据，通过对数据进行分析构建路由器级拓扑。但在实际中，网络中很多节点出于安全等因素的考虑，不会响应 traceroute等测量工具发送的探测包，导致测量结果存在大量匿名理由器，故无法准确识别出路由器级拓扑。针对该问题，国际上有学者提出基于网络层析成像的拓扑估计方法，该方法通过在网络边缘节点之间发送探测包，然后利用统计学的方法推断出路由器级拓扑结构。该方法最大的优点是不需要内部节点协作，因此不受网络存在大量匿名路由器的限制。但是目前网络层析成像的方法只能识别出树状拓扑结构，而无法获得网状的路由器级拓扑结构。针对现有方法存在的缺陷，本文采用传统匿名路由器识别和网络层析成像相结合的研究思路，把网络层析成像估计所得的树状拓扑作为约束进行匿名路由器识别，进而构建较为完善的路由器级拓扑结构。本文主要贡献可以概括为以下两个方面：（1）提出基于图模式的匿名路由器聚类方法：匿名路由器聚类的目的是将在拓扑图上位置相近的匿名路由器聚集到一起，从而有利于设计合理的探测包发送方案，使发送的探测包能覆盖需要识别的匿名路由器。本文提出基于图模式的匿名路由器聚类方法，通过对测量得到原始数据的总结分析，归纳出了三种匿名路由器位置相近时，测量结果的图模式，根据起始节点、目的节点间的联系，确定匿名路由器的分布位置，对匿名路由器进行聚类。（2）提出基于网络层析成像的匿名路由器识别方法：网络层析成像利用这些已知路由器设计发包方法，并利用时间延迟的协方差构建树状拓扑。本文将树状拓扑作为约束条件，根据网络层析成像的特点提出匿名路由器识别准则，逐一分析树状拓扑中每条链路的匿名路由器分布情况。根据树状拓扑的约束和识别准则，得到每条路径的匿名路由器分布方程。通过迭代求解以上方程，就可以获得具体每条链路上匿名路由器的分布情况，进而识别出原始数据中的匿名路由器。本文使用理论数据和 iPlane、CAIDA提供的真实网络测量数据对提出方法进行实验验证，实验结果表明提出的匿名路由器聚类算法可以有效地对匿名路由器I 摘要进行聚类，提出的基于网络层析成像的匿名路由器识别方法能有效识别已经聚类的匿名路由器。因此，本文方法可以在存在匿名路由器的条件下，获得较为准确的路由器级拓扑结构。关键词：图模式，匿名路由器，网络层析成像，拓扑合并II ABSTRACTABSTRACTWith the rapid progress of network technology, network has been one of the mostimportant infrastructures and has infiltrated every aspect of our society. The networkrouter level topology can characterize connection between routers, and it can alsoprovide useful data for network programming, optimization, management, which are thefoundation of constructing credible and secure network.The existing router level topology recognition methods mainly rely on themeasuring tools, such as traceroute, to collect original data and then analysing the datato construct router level topology. Howvever, many network nodes wont give areponse to the measuring data packets emited by measuring tools for security reasons,which leads to lots of anonymous routers.So its impossible to accurately recognify therouter level topology. In order to solve this problem, some international scholarsproposed network tomography to estimate router level topology.This method emitsprobe packets among the network edge nodes, and then used statistical method to inferthe structure of router level topology. The biggest advantage of network tomography isthat it can infer router level topology without internal node collaboration, so it is notsubject to anonymous routers. But only tree topology can network tomography getinstead of the net topology.For defects of the existing methods, this paper combines the traditional anonymousrecognition methods with network tomography, which makes the tree topology asconstraint to recognify anonymous routers. By using this new method can we finallyconstruct a relative perfect network topology.The main contribution of this paperincluding:Firstly, proposing the anonymous router clustering method based on graphmodeling. The aim of anonymous router clustering is gathering the anonymous routerswhich have similar location.Anonymous routers clustering is helpful for designingreasonable probe packets transmission scheme and cover anonymous routers which arerequired to be identified. This paper proposes the clustering method based on graphmodeling. By analysing and summarizing the original measuring data, this paperconclude three kinds of anonymous routers clustering graph model. The three graphmodels are all according to the connections between known start nodes and endIII ABSTRACTnodes,so anonymous routers location can be determined and clustered.Secondly, proposing an anonymous routers recognition method based on networktomograph.Network tomography designed probe packets transmission scheme usingknown nodes, and use covariance of time delay to construct tree topology. So we makeuse of statical time delay covariance and construct tree topology. This tree topology isused as constrained codition, moreover according to the characteristics of networktomograph, this paper put forward anonymous routers recognition rules. According tothe tree topology and recognition rules, a equation can be obtained about anonymousrouters distribution at each link. By interatively solving the equation all answers aboutanonymous routers distribution can be obtained.This paper chooses real network measure data, which downloads from iPlane andCAIDA, to verify the clustering method and anonymous routers recognition methodbased on network tomograpg. And the result of experiment show that the clusteringmethod can cluster anonymous routers effectively and anonymous routers recognitionmethod can recognize anonymous routers effectively. Therefore, the methods proposedby this paper can get router level topology accurately in the presence of large numbersof anonymous routers.Keywords: graph model, anonymous router, network topography, topology mixtureIV 目录目录第一章绪论 . 11.1研究背景及研究意义 .11.2国内外研究现状 .21.2.1传统方法识别网络拓扑 .21.2.2网络层析成像法 .31.2.3匿名路由器识别 .41.3本文主要研究内容以及创新 .51.4文章具体章节安排 .6第二章匿名路由器模型概述 . 82.1匿名路由器产生的原因 .82.2匿名路由器对网络拓扑造成的影响 .92.2.1匿名路由器造成的虚假节点 .92.2.2匿名路由器造成的虚假链路 .102.3匿名路由器识别的传统方法以及问题 .112.3.1直接相连法 .112.3.2合并法 .112.3.3唯一存在法 .122.4基于图归纳的匿名路由器识别方法 .132.4.1图归纳法的基本定义 .132.4.2图归纳法的四种结构 .152.4.3图归纳法识别匿名路由器流程 .212.5小结 .22第三章基于图模式的匿名路由器聚类 . 243.1匿名路由器聚类的框架 .243.1.1数据预处理 .253.2目的节点相交图聚类 .263.2.1聚类思路 .263.2.2算法流程 .273.3起始节点相交聚类 .283.3.1聚类思路 .29V 目录3.3.2算法流程 .303.4起始节点邻接聚类 .313.4.1聚类思路 .313.4.2算法流程 .323.5匿名路由器聚类实验和分析 .333.6本章小结 .35第四章基于网络层析成像的匿名路由器识别 . 364.1基于网络层析成像的拓扑识别方法 .364.2基于约束的匿名路由器识别方法 .394.2.1聚类匿名路由器识别的约束条件 .404.2.2聚类匿名路由器的识别准则 .414.2.3聚类匿名路由器的合并 .434.3仿真分析 .454.3.1仿真平台和实验数据 .464.3.2实验结果 .474.4本章小结 .51第五章文章总结 . 535.1全文总结 .535.2工作展望 .54致谢 . 55参考文献 . 56攻硕期间取得的研究成果 . 58VI 图目录图目录图 2-1匿名路由器造成的虚假节点. 9图 2-2匿名路由器造成的虚假链路. 10图 2-3直接相连法处理前的拓扑.11图 2-4直接相连法处理后的拓扑.11图 2-5合并法处理前的拓扑. 12图 2-6合并法处理后的拓扑. 12图 2-7唯一存在法识别拓扑. 12图 2-8平行结构第一种形式. 15图 2-9平行结构第一种形式对应的冗余结构. 15图 2-10平行结构第二种形式. 16图 2-11平行结构第二种表现形式对应的冗余结构. 17图 2-12团结构. 17图 2-13团结构对应的冗余结构. 18图 2-14完全偶图结构. 19图 2-15完全偶图结构对应的冗余结构. 19图 2-16星型结构. 20图 2-17星型结构对应的冗余结构. 20图 2-18图归纳法识别匿名路由器的具体流程. 22图 3-1匿名路由器处理步骤. 24图 3-2数据预处理步骤. 25图 3-3目的节点相交聚类法思路. 27图 3-4目的节点相交法流程图. 28图 3-5起始节点相交聚类法思路. 29图 3-6起始节点相交聚类法流程. 30图 3-7起始节点邻接聚类. 31图 3-8起始节点邻接聚类法流程. 32图 4-1时间延迟协方差比较情况 1. 38图 4-2时间延迟协方差比较情况 2. 38图 4-3时间延迟协方差比较情况 3. 39图 4-4网络层析成像得到拓扑. 40图 4-5多个源节点树状拓扑. 41图 4-6共享准则第 1种情况示意图. 42图 4-7共享准则第 2种情况示意图. 42VII 图目录图 4-8独立准则示意图. 43图 4-9聚类匿名路由器拓扑. 44图 4-10 CAIDA数据对应的真实拓扑 . 46图 4-11网络测量数据直接绘制得到的拓扑. 47图 4-12以 6个节点为源节点分别得到的树状拓扑. 48图 4-13典型节点和链路. 49图 4-14最终识别出的网络拓扑. 51VIII 表目录表目录表 3-1理论数据匿名路由器聚类结果. 33表 3-2 iPlane数据匿名路由器聚类结果. 34表 3-3 CAIDA数据匿名路由器聚类结果 . 34IX 第一章绪论第一章绪论1.1研究背景及研究意义伴随信息技术的进一步发展，互联网在社会各个领域中扮演着越来越重要的角色。为了保证互联网的良好运行并且进一步提高其性能，科研人员必须详细地了解和掌握网络基本参数，比如网路拓扑等。通过研究网络拓扑，科研人员可以对网络进行实时分析、动态管理和有针对地研究高效网络协议。所谓网络拓扑，指的是网络实体间的连接关系，依据网络实体的相关定义能够把网络拓扑分为三层：overlay网络拓扑、链路层网络拓扑、网络层网络拓扑。在这三者中，对网络层网络拓扑的研究最多，在本文中如果没有专门说明，则提到的网络拓扑是指网络层网络拓扑。网络拓扑识别是了解网络性能的基础，就像开尔文爵士在演讲说的那样1：当我们可以明白表示我们谈论东西的时候，方能称得上对此有所了解；不然便只能认为是一片虚无。而为了明白地表示网络，网络拓扑识别十分必要。网络拓扑识别便是利用一定的方法和技术，对目标网络的逻辑拓扑进行推测和识别。经过若干年的努力，学术界提出了相应的方法和理论来解决网络拓扑识别。对网络层的实体分类，可以得到四个层次的网络拓扑：AS级(自治域)、IP接口级、POP（Point of Presence）级、路由器级。不同层次的网络拓扑，识别方法也不同。AS是 BGP路由协议的基本单元，同时也是 AS级拓扑的组成元素，故而通过被动侦听更新报文和 BGP路由表就能得到大量有用信息。IP接口级拓扑的节点是 IP地址，能够感知从网络上穿越的数据报文，因此识别时可以采用大规模主动发包的方法。相比之下，POP级拓扑和路由器级拓扑不能直接识别，只能通过间接的推理获得。对于 POP级拓扑，可以由 IP接口级映射为 POP级，然后结合地理信息就得到了 POP级拓扑；对于路由器级拓扑，也是在 IP接口级数据的基础上做别名解析，因为 IP路由器由众多的 IP接口构成，故在 IP接口级拓扑上首先识别属于同一台路由器的接口，然后再将其映射到路由器，就构成了路由器级拓扑。传统的网络拓扑判别法（例如DNS zone transfer、traceroute）需要假定所有的中间节点可协作，而后发包，并依据中间路由器回应的探测信息，猜测网络的拓扑结构，但这一般依赖于协议的允许和中间节点的协作才能完成。传统的方法最早是由Siamwalla等人2提出，包括了广播ping/ping的方法、基于DNS zonetransfer、基于traceroute的方法。除传统的网络拓扑识别方法而外，学术界还提出了另外一种方案来解决网络1 电子科技大学硕士学位论文拓扑识别问题，这就是网络拓扑识别的层析成像方法。层析成像法并不在意中间节点是否合作，这相对传统网络拓扑识别法而言，是一个很大的不同，层析成像法通过发送节点到节点的探测包，收集并分析得到的探测包的数字特征（比方时间延迟的方差、均值等），进而估计网络拓扑。识别目标网络拓扑结构意义重大。例如 1994年在科索沃战争中，在空袭打击之前得到的网络拓扑结构与空袭打击开始之后得到的网络拓扑结果对比，可以发现，打击之后的网络拓扑明显简单，这与空袭开始后的大范围停电导致的正常工作的节点减少是相吻合的，这从侧面也反映出空袭效果。然而在真正的网络环境中，部分路由器由于某些原因，返回错误的IP 地址信息或者不回应探测报文，这造成网络拓扑识别中出现一些无法识别的节点，这就是匿名路由器。匿名路由器产生很多虚假链路和虚假节点，对网络拓扑识别造成很大影响，故而引起了越来越多的关注。匿名路由器的识别也成为网络拓扑识别中一个必须解决的难题。1.2国内外研究现状研究网络拓扑识别，兴起于上世纪 90年代中期。目前包括清华、北大、中科院、东南大学、UCBerkeley、NLANR在内的众多国内外著名高等学府和研究所都在研究如何识别网络拓扑，其中位于加州大学圣迭戈分校超级计算机中心的互联网数据分析协作联盟：CAIDA3在这个领域具有相当的权威性。CAIDA成立于 1997年，自成立以来做出很多有影响力研究工作，因此在某种层面上，CAIDA是网络拓扑识别领域的风向标。在众多著名大学和研究所的共同努力下，网络拓扑识别的方法和理论都得到了极大的完善。网络拓扑识别算法可以分为两类：传统识别法和网络层析成像识别法。这两种识别方法都依赖发包获得的网络数据，而由于匿名路由器问题，在获取的网络测量数据中存在大量无法识别的信息，因此为了更好地识别网络拓扑，自上世纪 90年代中期以来，包括 CAIDA在内的一系列知名科学组织投入很大精力研究匿名路由器的识别问题。1.2.1传统方法识别网络拓扑传统的方法，当对网络拓扑进行识别时，要求得到网络协议的支持。传统的网络拓扑识别方法，具体来说首先向待测网络发送探测包，获得待测网络中的节点信息，再通过中间路由器返回的探测数据来推测目标网络的拓扑结构，最后把获取到的节点以及连接信息构成网络拓扑，上述过程需要协议的支持和中间节点的协作。2 第一章绪论传统网络拓扑识别方法经过发展，目前有广播 ping/ping、DNS的 zone transfer、traceroute等三种方法。以上方法可以分为两类，基于 ICMP协议的探测方法和基于 SNMP协议的探测方法4,5（1）广播 ping和 ping。主要用于确定网络中否存在有相应 IP地址的主机，ping采用的是收到和发送ICMP数据包，并且以异步形式进行上面两个过程。由于 ping通过单个存活主机的时间很短，约在 0.1秒以内，故而规模较小的（如几十或上百台主机）的网络，可以很快扫描完毕。广播 ping是向整个探测网络发送 ICMP数据包，由于网络负担会因此而变大，很多网络不支持该操作。（2）DNS的 Zone transfer该方法通常与广播 ping结合使用，以搜索探测网络内部的设备作为其算法起点。它的原理如下，IP网络中任意一个节点存在独一无二的地址，DNS中包含有网络地址和每个节点名字的映射表，因此可以依据此进行搜索。这种方法复杂度低并且十分方便，但由于不是绝对安全，某些安全级别较高的 DNS服务器不会执行这种操作。（3）traceroute由于 IP数据包首部有个 TTL字段，数据包在网络中每传递一次，TTL字段就会减 1，当某个路由器收到数据包，并且在做完自减操作后，TTL字段为 0，那么就丢弃数据，并且向源地址发送差错报文，这样