（计算机科学与技术专业论文）非授权局域网拓扑探测算法的研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 随着计算机网络技术的迅速发展，网络本身的安全性问题日益突出。局域网拓扑探测 作为网络安全研究的一项重要内容，目前已经很难适应复杂网络环境的需要，存在很多问 题亟待解决。其中，网络层拓扑探测和物理拓扑探测算法的研究尤为重要。本文围绕网络 层拓扑探测和物理拓扑探测算法的研究与实现，所做的工作主要集中在以下几点： 1 针对基于i c m p 协议的网络层拓扑探测算法存在的问题，研究并提出了启发式子网猜 测、启发式地址猜测和启发式路由器别名探测技术，优化了t r a c e r o u t e 算法。在此 基础上，提出基于i c m p 的启发式网络层拓扑探测算法，并对算法进行了复杂性分析 和性能测试。分析和测试结果表明，该算法采用的启发策略可以有效降低算法的网络 开销，提高网络层拓扑探测的准确性和完整性，对于不同规模的局域网具有较强的适 应性： 2 在深入分析三种典型的物理拓扑推断理论和算法的基础上，提出直接相连和通过哑设 备直接相连两种交换机互连关系的判定规则，进一步降低交换机地址转发表完全性对 拓扑推断的影响，提高了拓扑推断的准确性，并根据该规则设计和实现了基于f d b 的 物理拓扑探测算法，较好解决了哑设备和v l a n 对拓扑推断的影响。算法的主要特点 是在交换机地址转发表不完整的情况下，能够有效实现正确的拓扑推断。测试表明， 算法在正确性和效率方面均有较大的提高； 3 针对现有拓扑图显示工具存在的问题，研究和实现了大规模异构局域网中拓扑图自动 生成算法，解决了拓扑图规模较大时存在的重叠、交叉和布局不合理等问题，具有较 好的容错显示能力； 4 ，以网络层和物理拓扑探测算法为核心，结合s n m p 协议和多种探测方法，实现了探测 策略可配置的局域网拓扑探测原型系统n e t w o r k p r o b e 。测试表明，n e t w o r k p r o b e 在准 确性、完整性和探测效率等方面能够满足大规模异构局域网拓扑探测的要求。 本文的研究成果已经在某预研项目中得到应用，为项目顺利通过中期检查打下了坚实 基础，为有效解决非授权目标网络拓扑探测受限等问题提供了有效的手段a 关键词：拓扑探测，s n m p 协议，启发式算法，物理拓扑，拓扑推断，哑设备 里堕型堂塾查奎兰型壅生堕堂堡笙兰 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g y ，n e t w o r ks e c u r i t yp r o b l e m s b e c o m em o r ea n dm o r ep r o m i n e n t c u r r e n t l y , a sa l li m p o r t a n tr e s e a r c ha s p e c ti nn e t w o r k s e c u r i t y ，i n t r a a sn e t w o r kt o p o l o g yp r o b et e c h n o l o g yc a r lh a r d l ym e e tt h en e e d so fc o m p l e x n e t w o r kc i r c u m s t a n c e s ，a n dm a n yp r o b l e m sn e e dt ob es o l v e d t os o l v et h e s ep r o b l e m s ，t h e r e s e a r c ho fi n t r a a sn e t w o r kt o p o l o g yp r o b ea l g o r i t h n a si sv e r yi m p o r t a n t i nt h i sp a p e r ，t h e n e t w o r kl a y e ra n dp h y s i c a lt o p o l o g yp r o b ea l g o r i t h m sa r ep u tf o r w a r da n dr e a l i z e d ，a n dt h em a i n w o r kc o n c e n t r a t e so na s p e c t sa sf o l l o w s ： 1 i no r d e rt os o l v et h es h o r t c o m i n g si nn e t w o r kt o p o l o g yp r o b ea l g o r i t h m su s i n gi c m p ，t h e h e u r i s t i cs u b n e th y p o t h e s i st e c h n i q u e ，h e u r i s t i ci pa d d r e s sh y p o t h e s i st e c h n i q u ea n d h e u r i s t i cr o u t e ra l i a sp r o b et e c h n i q u ea r es t u d i e da n dp u tf o r w a r d ，a n dt h et r a c e r o u t e p r o g r a m m ei so p t i m i z e d b a s e do nt h e s e ，a ni c m pb a s e da l g o r i t h mo fh e u r i s t i ci n t r a a s n e t w o r kt o p o l o g yp r o b ei sp u tf o r w a r da n dr e a l i z e d t h e n ，t h ec o m p l e x i t yo f t h ea l g o r i t h mi s a n a l y z e d t h ea n a l y s i sr e s u l t ss h o wt h a tt h eh e u r i s t i ct e c h n i q u e so ft h ea l g o r i t h mc a nr e d u c e t h ec o s to fn e t w o r kc o m m u n i c a t i o ne f f e c t i v e l y , a n dt h ea l g o r i t h mh a sd e s i r a b l ea d a p t a b i l i t y i nd i f i e r e n ts i z e di n t r a - a sn e t w o r k 2 w i t ht h es t u d yo ft h r e et y p i c a lt h e o r i e sa n da l g o r i t h m so fp h y s i c a in e t w o r kt o p o l o g yi n f e r ， t w or u l e so fi n f e r r i n gt h ed i r e c tc o n n e c t i o na n dd u m pd e v i c e sb a s e dc o n n e c t i o na r ep u t f o r w a r d t h er u l e sr e d u c et h er e q u i r e m e n to ff o r w a r d i n gd a t a b a s e si n t e g r a l i t yo fs w i t c h e s a n di m p r o v et h ec o r r e c t n e s so f p h y s i c a li n f e rr e s u l te f f e c t i v e l y b a s e do nt h er u l e s ，t h ef d b b a s e da l g o r i t h mo fi n t r a a sn e t w o r kp h y s i c a lt o p o l o g yp r o b ei sd e s i g n e da n do p t i m i z e d a n i m p o r t a n tc h a r a c t e r i s t i co ft h ea l g o r i t h mi st h a ti tc a ni n f e rt h en e t w o r kp h y s i c a lt o p o l o g y c o r r e c t l yo nt h el a c ko ft h ei n t e g r a l i t yo ff o r w a r d i n gd a t a b a s eo fs w i t c h e s t h et e s tr e s u l t s h o w st h a tt h ea l g o r i t h mh a ss a t i s f i e da d v a n t a g ei ne f f i c i e n c yw h i c hc a nm e e tt h ed e m a n do f l a r g e 。s c a l ei n t r a - a sn e t w o r kp h y s i c a lt o p o l o g yp r o b e 3 i no r d e rt os o l v et h ep r o b l e m si nc u r r e n tt o p o l o g ym a pg e n e r a t i o nt o o l s ，at o p o l o g ym a p g e n e r a t i o na l g o r i t h mo fl a r g e - s c a l ei n t r a - a sn e t w o r ki sd e s i g n e da n di m p l e m e n t e d t h e a l g o r i t h mc a ne l i m i n a t et h eo v e r l a p ，i n t e r l a c ea n du n r e a s o n a b l el a y o u ta m o n ge l e m e n t si n n e t w o r kt o p o l o g ym a p ，a n di th a sa b i l i t yt or e c t i f yt h et o p o l o g ym a pw h e ns o m et o p o l o g y i n f o r m a t i o ni sn o ta c c u r a t e 4 w i t ht h ec o m b i n a t i o no ft h eh e u r i s t i ct o p o l o g yp r o b ea l g o r i t h m ，p h y s i c a lt o p o l o g yp r o b e a l g o r i t h m ，s n m pb a s e da l g o r i t h ma n do t h e rt o p o l o g yp r o b et e c h n i q u e s ，a ni n t r a - a s n e t w o r kt o p o l o g yp r o b ep r o t o t y p en a m e dn e t w o r k p r o b ei sd e s i g n e da n di m p l e m e n t e d 国防科学技术大学研究生院学位论文 w h i c hc a ns u p p o r tf l e x i b l ec o n f i g u r a t i o no f p r o b ep o l i c i e sa c c o r d i n gt ot h ea c t u a ln e t w o r k c i r c u m s t a n c e s t h et e s tr e s u l t ss h o wt h a tn e t w o r k p r o b eh a s g o o dp e r f o r m a n c e i n c o r r e c t n e s s ，c o m p l e t e n e s sa n de f f i c i e n c ya n dh a ss a t i s f i e da d a p t a b i l i t yi nh e t e r o g e n e o u s n e t w o r k p a r to f p r o d u c t i o n si nt h i sp a p e rh a sb e e na p p l i e di n t oan a t i o n a lr e s e a r c hp l a na n dl a i dt h e f o u n d a t i o nf o rt h es u c c e s s f u te x a m i n a t i o no ft h ep r o j e c t a d d i t i o n a l l y ，i tp r o v i d e sa ne f f e c t i v e w a yo f p r o b i n gt h ea i m e dn e t w o r kw i t h o u ta u t h o r i z a t i o ni na i m e dn e t w o r k k e y w o r d s ：t o p o l o g yp r o b e ，s n m p ，h e u r i s t i ca l g o r i t h m , p h y s i c a lt o p o l o g y ，t o p o l o g y i n f e r d u m bd e v i c e i i i 国防科学技术大学研究生院学位论文 图目录 图2 1 拓扑探测算法使用的相关协议 图2 2i p 封装的i c m p 报文 图2 3i c m p 报文的一般格式 图2 4i c m p 地址掩码请求与应答报文 图2 5i c m p 时间戳请求与应答报文。 图2 6i c m p 端口不可达差错报文 图2 7i p 首部中记录路由选项的般格式 图2 8s n m p 工作机制j 图2 ，9m i b 库树形结构。，。 图2 1 0s n m p 的报文格式 图3 1 根据i p 地址集猜测子网地址示例 图3 2i p 源站路由选项的通用格式 图3 3i p 源站路由选项示例，。， 图3 4 路由器源站路由示例l 图3 5 路由器源站路由示例2 一 图3 6 路由器源站路由示例3 ， 图3 7 路出器别名探测思想示意图1 ， 图3 8 路由器别名探测思想示意图2 图4 1 以太数据包格式 图4 2 构造生成树时发送报文格式 图4 3 物理拓扑示意图 图4 4 物理拓扑推断流程示意图， 图4 5 交换机简单连接判断示例 图5 1n e t w o r k p r o b e 系统结构示意图 图5 2 拓扑探测数据关系图 图5 3 单个二元组的坐标确定方法 图5 4 相邻二元组的坐标确定方法1 图5 5 相邻二元组的坐标确定方法2 。， 图5 6 相邻二元组的坐标确定方法3 ， 图5 7 相邻二元组的坐标确定方法4 图5 8 根节点坐标确定示意图 图5 9 网络县拓扑图，。， 图5 1 0 子网1 9 2 1 6 8 1 0 的交换机拓扑图 0 ，0 0 0 0 u u坨墙坞坞加趵扒射拢盯勰孔驼弘钙钉盯弛弛弱昭弱銎的 国防科学技术大学研究生院学位论文 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 韭拯抠旦垫圈堑i i = 拯型簋洼盟珏塞生塞狸 学位论文作者签名： 曼薹塑日期：渺中年i y 月晌 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目t 一韭援拯旦垫圈拯盐握型差洼鳗堡銮生塞熟 学位论文作者签名：曼堕塑 作者指导教师签名：堇瑟圆聋 日期：训节年7 月彬日 日期：? 。v 年，歹月2 f 日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题研究背景 随着计算机网络技术的发展，网络规模不断扩大，网络中节点的类型和节点之间的互 连技术多种多样，这使得网络的拓扑结构日益复杂，而且处于不断的变化之中。在这种情 况下，传统的局域网拓扑探测技术已经很难适应异构网络管理的需要。同时，作为非授权 目标局域网探测的关键技术，传统的拓扑探测技术也无法满足局域网发展的需要。 在局域网中，传统的网络层拓扑探测技术紧密依赖s n m p 协议口j ，而s n m p 协议本身 就存在着技术上的缺陷，导致传统的网络层拓扑探测技术存在较大的局限性，主要表现在 以下两点： 1 安全性差2 1 1 3 1 。传统拓扑探测算法是基于s n v i p 协议来实现的，在s n m p v l t 3 】中，通过 明文密钥来进行身份验证。在s n m p v 2 t 3 】中，身份验证使用加密技术，但协议的复杂 性增加，没有得到推广，它的修改版本s n m p v 2 c ”继续使用基于明文密钥的身份验证 方式： 2 兼容性差。s n m p 协议是基于m i b 3 1 数据库实现的。不同厂商为了方便用户管理，在 m m 库中添加了各自的私有设备管理协议，而私有协议之间差异性大，并没有形成统 一的标准。 这就导致当前紧密依赖于s n m p 的网络层拓扑探测技术，很难保证拓扑探测的正确性 和完整性。同时，在非授权目标网络拓扑探测中，基于s n m p 的网络层拓扑探测技术更是面 临严峻挑战。主要原因如下： 1 网络中对s n m p 的应用不规范。统计数据表明，在整个网络环境中，只有大约8 的主机、 9 0 的路由器正确地配置了s n m p 协议并且可以被拓扑探测算法所使用【2 。 2 关键节点的s n m p 访问受限。由于s n i v l p 协议存在安全隐患，为了提高局域网的安全 性，网络管理者禁止对某些关键节点的s n m p 访问，这些安全管理策略都使得基于 s n m p 的非授权拓扑探测很难奏效。 因此，突破目标网络对非授权网络层拓扑探测的限制已经成为拓扑探测研究领域的重 要课题之一。为了解决浚问题，本文研究不依赖于s n m p 协议的网络层拓扑探测技术，提高 拓扑探测对复杂网络环境的适应性。 另一方面，随着计算机性能的提高以及通信量的剧增，传统局域网已经愈来愈超出了 自身的负荷。为了提高了局域网的性能，交换式局域网技术应运而生。由于交换式局域网 升级不需要改变网络中其它硬件，具有很高的可扩充能力，并且能够在高速与低速网络间 转换，实现不同网络的协同，已经成为局域网升级时首选的方案。目前，以交换机互连和 集群技术为支撑的交换式局域网已经成为当前局域网设计方案的主流，物理( 数据链路层) 第1 页 国防科学技术大学研究生院学位论文 的拓扑结构已经成为局域网拓扑结构的骨干。 在交换式局域网中，物理拓扑结构探测技术越来越成为拓扑探测需要解决的核心问 题，主要有以下原因： 1 网络层的拓扑结构探测对物理设备是透明的，已经不能准确刻画交换式网络的拓扑属 性： 2 利用物理拓扑信息，可以优化网络配置，减缓网络拥塞。提高服务质量； 3 只有掌握物理拓扑结构，才能详细了解网络运行状态，便于进行流量控制、故障检测 等工作； 4 v l a n 4 技术的应用，使局域网的配置更灵活，安全性更高。但在v l a n 中，对物理拓 扑的研究就尤为重要。 同时，在局域网非授权拓扑探测中，掌握了目标网络的物理拓扑，能够准确定位网络 中脆弱节点物理位置和具体的路由信息，从而提高攻击的有效性与准确性。 对物理拓扑探测技术的研究已经成为当前局域网拓扑探测的热点和难点。现有的一些 算法依赖s n m p 协议，但标准s n m p 包含的数据完整性很差，亟需更有效的物理拓扑探测技 术，以保证拓扑推断的正确性。 本文来源于“十五”预研项目，主要采用s n m p 和i c m p 探测技术结合的技术路线， 重点解决网络拓扑探测技术在非授权复杂网络环境中的适应能力，提高拓扑探测的完全 性、准确性和效率。本文在研究网络层和物理拓扑探测算法的基础上，实现了局域网拓扑 探测原型系统n e t w o r k p r o b e ，更准确，更清晰的呈现局域网的多层拓扑结构。 1 2 局域网拓扑探测技术研究现状 目前，基于s n m p 协议的网络层拓扑探测技术已经比较成熟，但不依赖于s n m p 的网络 层拓扑探测技术还需要深入研究：同时，在物理拓扑探测中，由于数据链路层设备( 网桥、 交换机) 对于t c p i p 协议透明，很难通过i c m p 协议识别网络中的数据链路层设备，并且通 信通常只发生在相邻的设备之间，难以获取设备之间互连的有效信息，这使得物理拓扑探 测技术主要依赖s n m p 。 对于网络层拓扑而言，国内外商用的企业级网络系统管理平台中基本都实现了基于 s n m p 协议的网络层拓扑探测功能，其中具有代表性的有h po p e n v i e w 、毋mt i v o l i 、c i s c o c d pr 5 1 等。其它商用网络层拓扑结构探测工具有： 1 o p t i m a ls u r v e y o r 。它的关键技术是s n m p + n o v e l l 网络查询机制： 2 d a r t m o u t hi n t e r m a p p e r 。它的关键技术是s n m p + a p p l e t a l k 广播。 研究领域中，局域网中网络层拓扑结构探测代表性技术有： 1 o c t o p u s 、a r g u s 提出了通过综合运用s n m p 、i c m p 等技术进行自治系统内部网络层拓 扑结构探测的算法【6 t ： 第2 页 国防科学技术大学研究生院学位论文 2 s i a m w a l l ae ta l ，提出了异类网络q h l a y e r - 3 ( 网络层) 拓扑结构推断算法，该算法使用 i c m p 协议【”。 在物理拓扑探测技术方面，国外学者提出的代表性研究方法主要有： 1 l o r a n n e t w o r k s y s t e m s 提出了异构网络物理拓扑结构探测技术 8 1 。它的基本思想是观 察网络节点上不同端口的数据传输模式，运用概率分析的方式对不同节点中具有相似 数据传输模式的端口进行互联。这种技术只能以概率推测节点之间的互连，准确率还 有待进一步提高； 2 y u r ib r i t b a r t 提出了基于标准s n m pm i b 信息的异构网络物理拓扑探测算法【9 l 。提出节 点间直接相连的判断规则，递归地推断所有节点间的互连关系。它是研究物理拓扑推 断的重要理论基础； 3 b r u c el o w e c a m p 进一步放松了对地址转发表完全性的要求【1 0 】。提出节点间简单相连判 断规则，从判断节点间的直接相连转为判断简单相连，有效提高了物理拓扑推断在大 型局域网中的效率。 综上所述，当前的局域网拓扑探测技术研究已经取得了很大的技术性突破，但仍然很 难满足要求，面临的主要问题是获取的信息量小，对不活跃节点的探测能力较弱，拓扑推 断能力不强，准确性和完整性不高，而且，在物理拓扑探测中，对v l a n 的识别仍是目前的 研究难点。 1 3 本文主要研究内容 根据项目要求，结合目前实际，本文主要研究内容有： 针对基于i c m p 协议的网络层拓扑探测算法存在的问题，研究并提出了启发式子网猜 测、启发式p 地址猜测和启发式路由器别名探测技术，优化了t r a c e r o u t e 算法；在此 基础上，提出基于i c m p 的启发式网络层拓扑探测算法，并对算法复杂性进行了分析 和性能测试； 在深入分析现有物理拓扑推断理论和算法的基础上，提出直接相连和通过哑设备直接 相连两种交换机互连关系的判定规则，进一步降低交换机地址转发表完全性对拓扑推 断的影响，提高了拓扑推断的准确性。并根据该规则设计和实现了局域网物理拓扑探 测算法，较好解决了哑设备和v l a n 对拓扑推断的影响： 针对现有拓扑图显示工具存在的问题，研究和实现了大规模异构局域网中拓扑图自动 生成算法，解决了拓扑图规模较大时存在的重叠、交叉和布局不合理等问题，具有较 好的容错显示能力； 以网络层和物理拓扑探测算法为核心，结合s n m p 协议和多种探测方法，实现了探测 策略可配置的局域网拓扑探测原型系统n e t w o r k p r o b e ，并对n e t w o r k p r o b e 原型系统作 了性能测试分析。 第3 页 国防科学技术大学研究生院学位论文 全文共分六章，各章的组织结构如下： 第一章为绪论部分，主要介绍了课题研究的背景、局域网拓扑探测技术研究现状和本 文主要研究内容； 第二章介绍了局域网拓扑探测的相关概念和主要支撑技术： 第三章对典型网络层拓扑探测算法进行了分析，针对算法存在的问题，研究并提出启 发式网络层拓扑探测技术，在此基础上提出和实现了启发式网络层拓扑探测算法，并 对算法作了测试分析； 第四章首先介绍了交换机原理、生成树协议和s n m p 协议在物理拓扑探测中的应用， 然后重点分析了三种典型的物理拓扑推断算法，提出了新的物理拓扑推断规则在此 基础上提出和实现了物理拓扑推断算法，并对算法作了性能优化： 第五章实现了局域网拓扑探测原型系统n e t w o r k p m b e ，并对系统做了性能测试和分析： 第六章为结束语，总结了本文的工作并对进一步的研究工作进行了展望。 1 4 本文的研究成果 本文的研究成果主要是： 设计并实现了一个局域网环境下的网络拓扑探测系统原型该研究成果已经在某预研 项目中得到应用，为项目顺利通过中期检查打下了坚实基础。为有效解决非授权目标 网络拓扑探测受限和脆弱节点探测等问题提供了有效的手段。 以第一作者在小型微型计算机系统发表论文一篇( 已录用) ，以第一作者在计 算机工程与科学发表论文一篇( 见本文附录a ) 。 第4 页 国防科学技术大学研究生院学位论文 第二章局域网拓扑探测概述 2 1 1 网络拓扑探测的定义 2 1 网络拓扑探测的概念 网络拓扑探测【1 1 】【1 2 】是依靠计算机软件和程序自动确定网络中各元素相互之间的动 态关系，其中网络元素是指网络中的路由器( 底层网关) 、交换机、网关( 高层网关) ，还 有子网、网桥、h u b 、主机。网络拓扑直接呈现网络的物理连接和逻辑连接，这些物理连 接按拓扑类型可分为总线型、星型、环型、树型、星环型、混合型等。球子网大都采取简 单的拓扑结构，而口主干网则是一种不规则的网状树。 在分析网络拓扑结构时，常把网络中的路由器、子网、主机、交换机等设备抽象成为 一个点，把连接这些设备的信道抽象成两点之间的边，这样网络拓扑就抽象成一个图。图 是网络拓扑的数学模型，那么切研究图论的方法都可以用来研究网络拓扑结构。图论中 的深度优先遍历和广度优先遍历在网络拓扑探测中广为应用，即从图的任意一点出发，沿 着某条边，可以访问图中的所有节点，而且是每一个节点至少被访问一次，这就是图的遍 历。本文中所研究的拓扑探测算法都是基于图或树的遍历算法。 i p 网络中有主干网、局域网、子网等，其使用的互连设备不同。例如主干网通常由边 界路由器连接不同的自治系统( a s ) 组成。而局域网多是由路由器一路由器连接或路由器一 子网连接。而子网一般是不同结构的l a n 网，子网内多是主机。所以，针对不同规模的 网络，所需拓扑信息的详略，探测速度的快慢，探测开销的大小，而设计不同的探测算法。 一般有主拓扑探测算法、局域网拓扑探测算法和子网拓扑探测算法等。 2 1 2 不同层次的网络拓扑探测 从协议层次的角度来看，d 网络有网络接口层( o s i 的链路层、物理层) 、网络层、 传输层和应用层。通常网络层是拓扑探测的首选位置，几乎所有的网络都支持口协议，而 基于s n m p 协议的探测算法可实现性较强，所以传统的探测算法都是在单一管理域中的网 络层探测逻辑网络的拓扑结构。但在大型异构i p 网络中，此技术仅能发现小部分拓扑信息， 所以有必要深入到网络接口层和v l a n 中进行探测。为了提供更大的带宽，交换机越来越 多地分布到口网络中，形成了以交换机为骨干的交换式p 网络，而交换机的拓扑互连对 网络层是不可见的，所以为了真正掌握网络拓扑，物理拓扑探测技术研究是必不可少的。 第5 页 国防科学技术大学研究生院学位论文 2 i 3 网络拓扑探测的技术支撑 由于碑网络协议【1 2 【1 3 【1 4 1 丰富，拓扑探测算法可以利用协议特性来获取相关信息组成 拓扑视图。目前主要的拓扑探测算法所涉及到的有关协议如图2 ，1 所示。 应用层 传输层 网络层 链路层 图2 1 拓扑探测算法使用的相关协议 其中晟常用的探测工具有p i n g 、t r a c e r o u t e 、d n s 和基于这些工具和协议的组合算法。 这些算法利用协议性质获取设备中存放在数据库、链表和变量中的拓扑信息来构成拓扑 图。这些协议分别适合于不同规模、不同层次、不同方式下的探测算法，以求达到其性能 和开销的最佳比值。 另一方面，拓扑探测又主动探测和被动监测两种。主动式一般由网管主机或运行探测 程序的主机向需要探测的目标网络发送探测报文，然后获取相关拓扑信息。它的优点是快 捷，缺点是增加网络额外流量；被动监测技术是在所需探测网络内安置探测器或探测源， 由它监视当前网络运行情况，得到信息后发送给探测主机，以形成拓扑视图。该技术优点 是不增加额外流量开销，缺点是速度相对较慢，而且安装探测器对大型网络来说很难现实。 一个好的探测算法应该是主动探测和被动监测技术结合起来。本文就是采用i c m p 主 动探测和s n m p 拓扑信息结合的策略实现多层次网络拓扑探测的。 2 1 4 探测算法的目标和性能评价 网络拓扑探测算法追求高效率、高速度、高完整性和高准确率四个目标。即尽可能小 的网络开销、尽可能快的探测速度、尽可能完整的拓扑信息、尽可能准确地拓扑信息。针 对这四个目标，衡量网络拓扑探测算法也有四个评价参数： 1 速度：指拓扑探测算法运行的时间，通常以分钟计算： 2 丌销：开销指网络通信开销。如发送s n m p 报文的次数、发送p i n g 包的次数和 t r a c e r o u t e 跟踪所经历的路由器跳数决定； 3 完整性：是用发现网络中主机、路由器、交换机、子网数的百分比表示； 第6 页 国防科学技术大学研究生院学位论文 4 准确度：发现的拓扑元素是否准确无误，也是用百分比表示。 2 2 1i c m p 协议 2 211i c m p 协议概述 2 2 网络拓扑探测的基本技术 i c m p 协议【1 4 1 ”1 可以被认为是i p 层的一个组成部分，它传递差错报文以及其它需要注 意的信息，i c m p 报文通常被口层或更高层协议( t c p 或u d p ) 使用。当网络通信发生异 常时，一些i c m p 报文把差错报文返回给用户进程。i c m p 报文是在m 数据报内部被传输 的，如图2 2 所示。i c m p 协议的正式规范参见r f c 7 9 2 p o s t e r l l 9 8 1 b 【l 5 1 。 卜一i p 数据报+ l 旺亟丑二夏画口 2 0 卓节 图2 ，2i p 封装的i c m p 报文 i c m p 报文的格式如图2 3 所示，所有报文的前4 个字节都是一样的，但是剩下的其它 字节互不相同。i c m p 协议的类型字段可以有1 5 个不同的值，分别描述特定类型的i c m p 报文，某些i c m p 报文还使用代码字段的值进一步描述不同的条件。本节主要介绍i c m p 协议中几种重要的报文类型。 2 2 1 2 主要i c m p 报文类型 图2 3i c m p 报文的一般格式 本节主要介绍i c m p 地址掩码请求与应答、时间戳请求与应答、端口不可达差错三种 i c m p 报文。 i c m p 地址掩码请求与应答报文 i c m p 地址掩码请求与应答用于无盘系统在引导过程中获取自己的子网掩码，系统广 第7 页 国防科学技术大学研究生院学位论文 播它的i c m p 请求报文，它的报文格式如图2 4 所示。 类型( 1 7 或l g ) l 代码( o )l校验和 标志符序列号 3 2 位子网掩码 图2 4i c m p 地址掩码请求与应答报文 t 2 字节 - l i c m p 地址掩码请求与应答报文中的标志符和序列号字段由发送端任意选择设定，这 些值在应答中将被返回。这样，发送端就可以把应答与请求进行匹配。 i c m p 时间戳请求与应答报文 i c m p 时间戳请求与应答报文允许系统向另一个系统查询当前的时间，来协调统一的 时间。这种i c m p 报文的好处是它提供了毫秒级的分辨率，而利用其它方法从别的主 机获取的时间只能提供秒级的分辨率。i c m p 时间戳请求与应答报文格式如图2 5 所 示。 图2 5i c m p 时间戳请求与应答报文 该报文工作流程如下：首先由请求端填写发起时间戳，然后发送报文：应答系统收到 请求报文时填写接收时闽戳，在发送应答时填写发送时间戳。大多数情况下应答系统 的接收时间戳和发送时间戳都设成相同的值。在实际应用中，主要用来计算报文的往 返时间( r t t ) ，它的值是接收到应答时的时间减去发送请求的时间值。 i c m p 端口不可达差错报文 i c m p 端口不可达报文是i c m p 目的不可达报文的一种。对于u d p 协议而言，如果收 到一份u d p 数据报而目的端口与某个正在使用的进程不相符，那么u d p 返回一个 i c m p 不可达报文，可以用t f t p 强制生成一个端口不可达报文。端口不可达报文的 一般格式如图2 6 所示。 第8 页 国防科学技术大学研究生院学位论文 0 781 51 63 1 类型( 3 ) 代码( 0 - 15 )校验和 来用( 必须为0 ) i p 首部( 包括选项) + 原始i p 数据报中数据的前8 字节 2 2 13p i n g 程序 图2 6i c m p 端口不可达差错报文 t 8 字节 上 p i n g 程序【1 4 1 是对两个t c p i p 系统连通性进行测试的基本工具，它只利用i c m p 回显 请求和回显应答报文。p i n g 程序的原理是任何支持t c p i p 的设备在收到一个回显请求报 文的时候，都会返回一个回显应答报文，请求报文和应答报文的格式相同。应答报文可以 简单的从请求报文中导出，方法是将诤报文中的源地址和目的地址交换，将类型“e c h o ” 换成“e c h o r e p l a y ”，将请求报文里收到的数据作为应答报文中的数据，然后重新计算 出新的d 值以及校验和，便得到了正确的回显应答报文。若发送方能够收到正确的应答报 文，则报告目的主机运行正常，并计算出发送请求与接收应答报文之间的时间差作为一次 交互通信所花费的时间。 大多数p i n g 程序都提供了一个一r 选项，其功能是记录路由的功能。它使得p i n g 程 序在发送出去的碑数据包中设置的口r r 选项。这样每个处理该数据包的路由器都把它的 i p 地址放入选项字段中，当数据包到达目的端时，d 地址清单应该复制到i c m p 回显应答 中，这样返回途中所经过的路由器地址也被加入到清单中。当p i n g 程序收到回显应答时， 它就得到了这份诤地址清单，清单中记录p 地址为路由器转发报文的出口的口地址。 i p 数据包中的r r 选项的一般格式如图2 7 所示。 u 。jj 。 c 。a e 1 e n p t r 1 pa d d r # li pa d d r # 2 i pa d d r # 3i pa d d r # 9 1114 字节 4 字节4 字节 。 4 字节 图2 7i p 首部中记录路由选项的一般格式 t r a c e r o u t e “：【”i 检测并记录到达某个指定网络目标的路径。它使用i c m p 报文和i p 首 第9 页 国防科学技术大学研究生院学位论文 部的t t l 字段，并试图从沿路由到达目标的每个主机处获得一个i c m p 的t i m e 。 e x c e e d e d 消息。随着试图连接目标的一个不可达端口，将导致沿路每个路由器在丢弃 u d p 数据报时都返回一个i c m p 超时报文。其工作过程描述如下： 1 发送4 0 字节的u d p 报文( t t l = 1 ) 至探测目标点； 2 第一个接收该报文的路由器丢弃该报文，发送i c m p 超时报文至源节点； 3 源节点接收i c m p 超时报文，并记下超时报文的发源地，将它作为通向探测目标点的 第一站路由器： 4 再次发送4 0 字节的u d p 报文( t t l = 2 ) 至探测目标点； 5 第二个接收该报文的路由器丢弃该报文，发送i c m p 超时报文至源节点； 6 源节点接收该超时报文。并记下超时报文的发源地，将它作为通向探测目标点的第二 站路由器： 7 t t l 每次加1 ，重复上述步骤，直至目标点有回应，或者未成功到达目标点但已经过 了最大跳数。如果报文到达目标点，则会有i c m p 超时报文发送至源节点( 因为报文 的目的端口对于t c p i p 系统来说正常情况下是不使用的) 。源节点根据i c m p 超时报 文来判别与目标点的连接是否成功。 2 2 2s n m p 协议 在数据链路层设备中，由于交换机从其功能上可以作为多端口的透明网桥，而且在标 准s n i v l pb r i d g em i b 1 7 1 中，已经存储了网桥转发和过滤数据帧的信息，因此，通过b r i d g e m m 中网桥的信息推断设备互连关系是物理拓扑探测算法的关键。本节主要介绍s n m p 协 议。 2 2 2 1s n m p 协议模型 简单网络管理协议1 1 1 ( s n m p ) 模型由4 部分组成：管理节点( m a n a g e m e n tn o d e ) 、 管理站( m a n a g e m e n ts t a t i o n ) 、管理信息库( m i b ：m a n a g e m e n ti n f o r m a t i o nb a s e ) 和简单 网络管理协议( m a n a g e m e n tp r o t o c 0 1 ) 。s n m p 极为详细地规定了设备应