（通信与信息系统专业论文）internet中拓扑可视化和时延的研究及其在dnmai中的实现.pdf

摘要 随着互联网日益广泛的应用，对网络测量的研究变得越来越重要。论文设计和 实现了一种具有良好的可扩展性的分布式网络测量和分析基础架构d n m a i ，能够较 好地完成对网络性能的测量和分析。文中给出了d n m a i 的结构和各功能模块，以 及d n i a i 的具体实施方式和d n m a i 的优点。 论文在d n i a i 中实现了端到端时延的测量。在d n m a i 中，采用可变数据包长度 和数据包类型的测量方法以及采用从数据包的发送端和接收端同时发送数据包的 双向测量方式来对端到端时延进行测量。 论文还提出了一种基于斛寻路算法的新的拓扑可视化算法。通过分析研究和 实际测试，该可视化算法能够满足拓扑可视化的实时性要求，而且可对含环路的 网络进行分析，对于网络拓扑的可视化具有很强的普适性和高效性。 关键词：网络测量端到端时延a 算法拓扑可视化 a b s t r a c t a st h ea p p l i c a t i o n so fi n t e r n e tb e c o m em o r ea n dm o l ew i d e l y , t h er e s e a r c ho n m e a s u r e m e n to fn e t w o r kp e d 0 讽锄h a sb e e nm o r ea n dm o r ei m p o r t a n t t h i sp a p e r d e s i g n e da n di m p l e m e n t e dt h ed i s t r i b u t e dn e t w o r km e a s l i r e m e n ta n da n a l ) , s i s i n f r a s t r u c t u r e ，d n m a i ，a ni n f t a s t r u c t u r ew i t hg o o de x t e n s i b i l i t y d n m a ic a nm e a s u r e a n da n a l y z en e t w o r kp e r f o r m a n c ep r e f e r a b l y t h i sp a p e ri n t r o d u c e dd e t a i l e d l yt h e i n f r a s t r u c t u r eo f d n m a i ，i m p l e m e n to f d n m a ia n d a d v a n t a g eo f d n m a i t h i sp a p e ri m p l e m e n t e de n dt oe n dd e l a ym e a s u r e m e n ti nd n m a i i nt h ed e l a y m e a s u r e m e n t , t h ep a c k e ts i z ea n dt h ep a c k e tt y p eh a v ec h a n g e d ，t h ep a c k e tc a l lb es e n t f r o ms e n d e ra n dr e c e i v e rs i m u l t a n e o u s l y t h i sp a p e rg i v e san e t w o r kt o p o l o g yv i s u a l i z a t i o na l g o r i t h mb a s e do na + a l g o r i t h m t h r o u g ht h et o p o l o g yv i s u a l i z a t i o np r o g r a mh a sb e e nt e s t e di no p e r a t i o n a ln e t w o r k s ，i t i sr e a l i t yt h a tt h i sa l g o r i t h mc a nm e e tt h er e a l t i m er e q u i r e m e n to fn e t w o r kt o p o l o g y v i s u a l i z a t i o n , a n ds o l v et h ep r o b l e mo fl o o pc a u s e db ys i n g l et o p o l o g yv i s u a l i z a t i o n a l g o r i t h m ，t h e r e f o r e ，i t sp r e f e r a b l ys u i t a b l ef o rt h er e s e a r c ho nc o m p l i c a t e dn e t w o r k t o p o l o g y k e y w o r d ：n e t w o r km e a s u 职豇l c m e n dt oe n d d e l a ya + a l g o r i t h m t o p o l o g yv i s u a l i z a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 本人签名!盂基 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名!蠹悫 导师签名只期：0 钟。，工，弓， 第一章绪论 第一章绪论 1 1 课题的研究背景 网络测量是指遵照一定的方法和技术，利用软件或硬件工具来测试或验证表 征网络性能的指标的一系列活动的总和。网络测量是研究网络行为学( 互联网运 行规律的科学) 的重要方法，对于网络运营、设备研制和网络技术与协议的研发 都具有重要意义，对网络管理也具有重要的辅助作用。 现在的互联网规模越来越大，其性能的可知性越来越复杂，系统级的管理度 也越来越小i ”，而在实际网络运行中，互联网服务提供商需要通过网络性能测量 系统来监测网络性能和网络行为特征，_ 并根据测量数据配置和规划应用系统，使 之提供更高的服务质量：网络用户需要通过测量应用系统的网络性能，确定应用 系统是否提供了足够的网络服务质量，从而选择服务质量最佳的应用系统翻，所 以对网络性能测量的研究随着互联网日益广泛的应用而变得越来越重要。 一些网络测量工具在功能和结构上有所不足，如对于每一个测量需求，都要 部署一套测量工具，测量规模不易扩展。不能灵活配置，部署的测量工具只能测 量某种特定应用系统的网络性能，缺乏测量业务种类扩展能力等。随着网络系统 规模和业务种类的急剧增长，这种面向特定对象的性能评价手段在准确性和扩展 性上越来越不能满足要求 要解决这一问题，需要建立一个网络性能测量基础体系结构，为互联网性能 和运行特征的研究提供一个可扩展的测量平台。 有关网络测量技术，国内外己进行了大量的研究，提出了很多的测量体系结 构。国外具有代表性的是美国国家科学基金n s f ( t h en a t i o n a ls c i e n c ef o u n d a t i o n ) 和美国国防部高级研究项目署d a r p a ( t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t s a g e n c y ) 资助的国家i n t e m e t 测量基础框架n i m i ( n a t i o n a li n t e m e tm e a s u r e m e n t i n f r a s t r u c t u r e ) p j n i m i 项目开始由n s f 支持，现在由d a r p a 支持。该n i m i 测量系统建立在现有网络之上，它的体系结构类似于其他大型网络服务系统【4 j ， 如域名服务器d n s ( d o m a mn a m es e r v e r ) 网络时间协议n t p ( n e t w o r kt i m e p r o t o c 0 1 ) 和世界性的新闻组网络系统u s e n e t ，采用层次结构和分布式方式，使 之可以扩展到整今互联网。该n i m i 的测量技术主要采用主动测量技术，其评价 指标主要有性能类指标。它在互联网中部署大量探针机器，探针机器之间相互合 作交换测试流量从而监测互联网路径性能状况。目前探针机器采用的是p a x s o n 通讯公司研制的网络探针进程n p d ( n e t w o r kp r o b ed a e m o n ) ，现有部署的n p d 数 量3 7 个，测量路径达到1 0 0 0 条。该n i m i 测量系统与其它几个测量体系结构不 同的是，n i m i 致力于建立可扩展互联网网络性能测量设施的通用体系结构。而 2 i n t e r n e t 中拓扑可视化和时延的研究及其在d n m a i 中的实现 不是为特定的分析目标做一组特定的测量操作【卯，其探针是建立在n p d 基础上， 且由后台通信进程、任务调度、测量簇程序三部分组成，具有轻量级代码可移动， 动态性，自动配置能力，对敏感数据的测量保证其私有性的安全性等优良特性。 国内具有代表性的网络测量体系，是北京航空航天大学提出的可定制的网络 测量基础架构c n m i ( c u s t o m i z a b l en e t w o r km e a s u r e m e n ti n f r a s t r u c t u r e ) 1 6 】。c n m i 的重要组成部分是测量探针结点，包括执行环境和探针模块集合，其探针具有分 布性、实时性、指标的多样性和可扩展性，它基于j 2 s e ( j a v a2p l a t f o r m , s t a n d a r d e d i t i o n ) 技术来实现跨平台的测量探针，通过基于父子类的探针结构设计来实现 探针的启动和管理，并出此实现c n m i 的可扩屐机制。 上述测量体系结构主要存在以下不足： 1 由于没有提出模块设计者自定制用户参数输入方式和自定制数据结果可视 化形式的解决方案，因而不能定制测量指标，用户也不能添加自己想要而系统不 存在的指标，缺乏面向应用需求的测量与分析方案的定制系统。 2 ，结构的分析方法比较零散，没有系统化地加入到体系结构中，测量项目主 要限于时延、丢弃率、吞吐率等性能指标，没有考虑各种应用需求，如入侵检测， 脆弱性度量等。 3 大多数结构都没有考虑结构的扩展性，没有考虑如何拓展体系结构使其它 已有和将有的应用方便高效的加入到体系之中没有或较少考虑各测量和分析方 法之间数据的复用，数据利用率不高。 4 国内提出的c n m i 测量结构虽说考虑了探针的扩展性，但其探针必须基于 j 2 s e 进行设计，必须实现父类的方法，这样限制了模块的开发工具。也限制了模 块设计的灵活性，模块的系统集成与数据复用也很不方便。 本文通过在网络测量体系结构中引入x m l ，提出分布式网络测量与分析基础 架构( d i s t r i b u t e dn e t w o r km e a s u r e m e n ta n da n a l y s i si n f r a s t r u c t u r e ，d n m a i ) ，采 用与已有测量架构完全不同的设计架构，力求解决以上这些限制和不足 本论文题目属于国家自然科学基金重点项目“基于网络探测的i p 网络拓扑发 现和性能分析的研究”，为三所高校联合申请的项目该项目主要内容为：研究 i p 网络探测及性能分析技术，探讨基于网络探测的新技术和新应用，研究从大规 模数掘中解析网络特性和业务特性，研究网络和信息安全的理论及方法，研究探 测监控为一体的综合网管体系，为发展有自主知识产权的网络探测体系及网络新 方法奠定基础。我校负责i p 网络探测的体系结构、i p 网络探测的原理和方法、i p 网络流及安全性分析、i p 网络拓扑发现、无线i p 探测方法和技术的研究五部分 第一章绪论 1 2 论文的主要工作和内容安排 论文的主要工作以及为项目所作贡献主要有： 1 进一步完善所提出的分布式网络测量与分析基础架构( d n m a i ) ，完善各 个站点的功能和其程序模块，使整个d n m a i 系统更稳定、运行更顺畅。 2 在d n m a i 中实现了对端到端时延的测量。在d n m a i 中，采用可变数据报长 度和类型的测量方法以及采用从数据包的发送端和接收端同时发送数据包的双向 测量方式来对端到端时延进行测量。 3 提出了一种基于胁寻路算法的新的拓扑可视化算法通过分析研究和实 际测试，该可视化算法能够满足拓扑可视化的实时性要求，而且可对含环路的网 络进行分析，对于网络拓扑的可视化具有很强的普适性和高效性。 下面介绍论文的内容安排 第1 章介绍课题的背景技术、国内外研究现状，以及本课题的研究内容和目标。 第2 章介绍分布式网络测量和分析基础架构d i i m a i 和其性能优点。 第3 章介绍在d n i - i a i 中如何实现端到端时延的测量。 。 第4 章介绍所提出的一种基于胁寻路算法的拓扑可视化算法。并利用提出的拓 扑可视化方法对分布式拓扑发现的探测结果进行可视化。 第5 章总结全文 4 i n t e r n e t 中拓扑可视化和时延的研究及其在d n 姒i 中的实现 第二章分布式网络测量和分析基础架构d n m a i 2 1d n i a i 简介 针对上述测量体系结构的不足，d n m a i 被设计成一种能根据用户需求定制 测量与分析方案，即具有很强包容性的分布式网络测量体系结构及其实现方法， 以解决灵活适用场景和可扩展性的问题。 d n m a i ( d i s t r i b u t e dn e t w o r km e a s u r e m e n ta n da n a l y s i si n f r a s t r u c t u r e ) l “卅是 一种基于层次式管理的分布式结构。该结构从整体上将各站点及其配给的模块分 成主控站、监控站和探针三个大的层次。每个区域内部主控站与监控站以及下级 主控站之间组成树形的隶属层次结构，一个区域可以拥有多棵树。区域之间由各 树根组成一个类似对等网络进行协调工作的网络。每个监控站管理多个探针。 监控站负责响应主控站的配置与管理，探针的升级，启动，探针参数传入， 和所得测量数据的传送与交流。 探针则用于在所配置的参数下的测量，必要时向监控站查询其他站点探针的 位置并请求协调测量。 主控站了解整个d n m a i 的拓扑结构并能进行相应的测量配置，同时提供网 页服务向用户提供测量和分析接口，根据用户的选择和自身的配置以及策略文件 定制出测量和分析流水工序的策略，然后调度相应的多个监控站或其它主控站完 成探测，将结果存放到用户目录中供用户查看结果。主控站负责监控站的配置， 提供探针的发放和下载，根据用户计划进行定期测量；主控站还具有互相协商进 行大规模网络测量的功能。 用户登录根主控站来管理某个区域或整个网络的测量，网络的测量有其体 系结构。 d n m a i 的网络测量体系结构在主控站和监控站的各站点中，从程序实现上包 括：用户端模块、维护模块、调度模块、日程模块、执行模块、测量和分析模块， 首先启动各站点即所有主控站和监控站的维护模块，读取各自的站点配置文件。 主控站根据配置文件启动日程模块和调度模块，监控站则启动其调度模块，各模 块进入阻塞状态，等待命令的到达；当用户端模块被启动后，用户登录并定制所 需要的任务，发送到维护模块；维护模块将接收到的用户定制信息转发给调度模 块，调度模块根据用户的选择启动相应的执行模块：执行模块调用测量模块进行 探测，并在测量完数据后启动相应的分析模块，将分析模块的结果存为可扩展置 标语言x m l 文件，供用户使用。 第二章分布式网络测量和分析基础架构d n m a i 2 2 蹦m a i 中的功能模块 在洲a i 中，维护模块用于管理和分发各模块的消息并实现模块的更新。它 在站点的d n m a i 端口上进行侦听，所有消息的传输开始阶段都需要先经过维护模 块，因此维护模块的一个重要功能就是管理和分发各模块的消息。d n m a i 中调度 模块给启动的每一个模块都会分配一个“r u n t j m e i d ”编号，并维护一张“运行 时模块信息描述表”，d n j “a i 通过此编号来标识正在运行的每个模块，并根据此编 号来管理模块间的消息维护模块通过查看这张表来实现消息的分发维护模块 的另一个重要功能是实现模块的更新，d n 姒i 中的每一个模块都是可以升级的， 维护模块可以根据模块的版本号向上级站点请求下载最新版本的文件来进行更 新，由于每个站点都有维护模块，所以可以形成一级级的递级更新，最后所有 d n i a i 站点的文件都与主控站钧文件一样。该模块的工作流程( 如图2 1 ) 如下： 首先启动维护模块，读取站点配置文件后进行初始化，启动调度模块和日程 模块，然后创建侦听线程来侦听d n m a i 的端口，等待其它站点或其它模块的连接， 这时则进入主消息循环，如果收到退出消息则退出d n m a i 。当创建的侦听线程如 果接收到连接则创建一个消息处理线程处理该消息，原线程继续等待其它连接。 读取站点配置文件 初始化工作 启动调度模块 启动日程模块 接收到连接? 创建消息处理线程处理该连接 主消息循环 退出消息? 二二 二 退出d n m a 图2 。l 维护模块工作流程图 调度模块是d n i d a i 的核心，它负责管理用户的账号信息，接收客户端测量计 划，制定用户的任务计划，并根据计划启动执行模块。其间还需要根据用户的请 求调用各模块的x s l 文件进行转换，给用户端传回相应的h t m l 页面，以及调用其 它一些辅助模块进行辅助处理。在执行模块执行完毕后需要回收执行模块所占用 i n t e r n e t 中拓扑可视化和时延的研究及其在d n m a i 中的实现 的资源，同时启动任务计划中下一个满足要求的模块，并为之分配资源( 如消息 缓冲区等) 。如果是远程模块的请求，需要根据请求启动相应的模块，并在进程结 束时回收资源另外如果要启动的模块在站点上不存在，则需要通知维护模块进 行模块升级。以上动作失败时均需要给请求方返回出错信息。该模块的工作流程 ( 如图2 2 ) 如下： 首先，接收并解析命令行x m l 文档，从中得到所有的配置信息，然后等待并 解析发送到调度模块的x m l 消息，如果x m l 消息解析失败则返回，解析成功后使 用) ( m ls c h e m a s 文件对该x m l 消息进行语法验证，在用来进行语法验证的s c h e m a 文件中，我们定义传给调度模块的x 札消息根节点必须是 ，根节点下的第 一个子节点必须是 ，此子节点的内容表示消息发送者的模块类型，可 以是“w e ba p p l e t ”，“l o c a l m a i n t a i n ”，“l o c a le x e cm o d u l e ”， “r e m o t e e x e c m o d u l e ”或“s c h e d u l e m o d u l e ”；其分别表示为客户端模块，本 地站点的维护模块，本地站点的执行模块，非本地站点的执行模块，日程模块。 然后，根据第二个子节点的名字分别进行处理，如果接收的本地站点的维护 模块的x m l 消息中第二个子节点是( q u i t ，那么就退出调度模块。 调度模块开始 解析命令行x m l 文档 从参数得到所有配置信息 得到消息缓冲区 井解析发送到 的x m l 消息 检查节点 下第1 个子节点名字 ! 气! 划l 吐些型i $ c h e d u l e l - m o d u l e i 几而j 乏稠l 而i 荔碉i 丽露矗酾lii 蕊烈雨! 陌 点名字分蹦处理iiiii 点名字分别处理 几韵l 曛摄丁厂 2 个予节 ? 退出调度模块 n 图2 2 调度模块的工作流程图 日程模块负责读取日程任务文件( 该文件由调度模块生成) ，定时或到达预定 第二章分布式网络测量和分析基础架构d n 姒i 7 时刻后向调度模块发送消息来启动相应的探溯任务。该模块的工作流程( 如图 2 3 ) 如下： 首先，读取日程任务x 礼文档，从中得到日程任务的信息，当需要启动探测 任务时，就向调度模块发送消息来启动相应的探测模块进行探测； 然后，确定是否退出，即如果向调度模块发送消息失败则返回，如果收到本 地站点的维护模块的退出信息，那么就退出日程模块。 读取日程任务x m l 文档 从参数中得到日程任务信息 n 任务需要启动? 发送失败 向调度模块发送消息启动任务 收到本地站点维护模 块的退出信息? 退出日 圈2 3 日程模块工作流程图 执行模块主要任务是从命令行参数中解析x m l 文档，其中】( i f l 是e x t e n s i b l e m a r k u pl a n g u a g e 的英文缩写，意为可扩展置标语割 d 9 】从解析的文档中得到 测量模块或分析模块需要的参数，并按照参数的要求启动测量模块或分析模块来 完成对应的测量任务或分析任务最后还需要将结果转成适当的x m l 字符串，交 给调度模块进行处理，同时通知调度模块所规定的任务已经完成如果需要进行 的任务是一个分布式的任务则需要通知其它站点启动相应的执行模块来进行分布 式测量，对于对方站点上由此而被启动的执行模块来说则需要配合启动方来完成 分布式测量。如果任务较为复杂，需要在测量过程中与其他执行模块进行信息交 换，则应按照d n m a i 的约定方式进行通信执行模块的存在主要是为了各种测量 模块和分析模块能向调度模块提供统一的调用接口，向其它模块提供统一的通信 接口如果模块的功能较简单，可以和相应的测量模块或分析模块合并成一个模 块该模块的工作流程( 如图2 4 ) 如下： 首先，解析命令行x m l 文档，从中得到测量模块或分析模块需要的参数，如 果需要使用其它模块的结果作为输入参数，那么在该执行模块的 节点中 添加子节点，添加的子节点名称就是要使用文件的文件名； 然后，按照参数的要求启动测量模块或分析模块来完成对应的测量任务或分 析任务。任务完成后将结果x m l 文档交给调度模块进行处理，提交完后退出执行 8 i n t e r n e t 中拓扑可视化和时延的研究及其在d n l l i 中的实现 模块； 如果需要进行的任务是一个分布式的任务则首先与相应站点的维护模块建立 t c p 连接，然后通知其调度模块启动相应的执行模块来配合启动方完成分布式测 量，任务完成后将结果x m l 文档交给启动方的调度模块进行处理，提交完后退出 执行模块。 ( 启动执行模块) _ l 解析命令行x m l 文档j _ l 从文档中得到测量或分析模块需要的参数 女惺互联网中两台圭机问端到端的双向目诞，因为是台f # 式$ 蒯所以两自主机都必须安装 和m a i 探针即两端都必须是d i 的监 站 发髅；广一炭钠嗍间 i | 5 r 一移 蠲猷为厂一( 稀少于蚰韩) 每灯骺包懒广_ 铈 穗匿点1 阿丽蕊蓠环灏固 继点痴而两蔚丽丽习 燃到凹 图3 i 端到端时延测量模块的输入参数格式 3 2 2 编写生成参数输入界面的x s l 文件 在确定了执行模块的输入参数格式之后就可以编辑生成参数输入界面的x s l 文件了，它的目的就是允许用户选择和输入上面的几个参数，然后在用户提交任 务时生成上面x m l 形式的字符串。 由于要进行端到端时延测量的探测点必须运行端到端时延测量模块，所以探 测点必须是d n m a i 的监控站点，所以用户应该只能选择d n m a i 的站点作为探测点。 d n m a i 的站点信息放置在站点配置文件中，该文件会作为x s l 文件的输入文件传 进来，x s l 文件可以使用“d n m a i s t a t i o n s l o w _ s t a t i o n s s t a t i o n ”路径来得到 站点配置中的所有下级站点，而使用“d n m a i s t a t i o n s u p - s t a t i o n s s t a t i o n ” 路径则可以访问站点配置中配置的所有上级站点，这些节点的“i p ”属性是站点 的i p 地址，子节点 则表示对站点的描述。 x s l 的输入文件还有一个 测量互联网中两台生机阍端劐端的j 暖冉时廷，殴为墨台作式霖涮所以阿台主机都必易【霓睫有d n m a i 搽针，即两端郡必须是d n m a 豹益控站 ： 发包数： 起始包长为 色后，乜长增加 弛：点1 犀丽丽氡i 隔药酊习 溺量点2 阿溺而鬻蕊_ 莉戮丽习 发包袭型网 。，一 图3 7i ) l 岫l a i 中端到端时延测量的参数输入界面 蛐。? 尊伽。舻。譬 第三章在d , a i 中实现端到端的时延测量 图3 8 渊姒i 中的任务运行情况页面 _ t - ：i 潞? w # 。m l _ 敦据2 ：蹙述端：1 9 2 1 6 8 0 5 l 收麓：1 9 2 1 6 8 0 5 0 鑫毫王虽 对鹾田： 鬻= ：3 l s , m 枷”耳瞄讳，”一矗拜此时瑶曩一 图3 9d 】q m a j 中测试结柬后所得到结果查看页面 i n t e r n e t 中拓扑可视化和时延的研究及其在d n m a i 中的实现 第四章基于斛寻路算法的复杂网络拓扑可视化算法研究 及实现 本章将对d n m a i 进行改进在d n m a i 中实现分布式拓扑发现的可视化。 由于分布式拓扑发现是在单点拓扑发现的基础上进行分布探测而实现的，所以本 章提出了如何在单点拓扑发现的基础上实现分布式拓扑发现的可视化【3 9 4 0 i 。 拓扑可