（计算机应用技术专业论文）网络检测点选取和放置方法的研究.pdf

卜 i 己0 川。- 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：堡垒 导师签名： 刍垒曼竺望 日期： 摘要 量詈曼量曼曼皇皇量鼍皇曹量皇蟹喜量罾皇鲁置葛詈詈昌詈昌鼍皇皇皇皇皇i l l 喜罾鲁曼鲁詈皇量量量皇量皇量葛! 鼍曼詈詈詈曼鼍暑鼍皇量詈曼旨墨宣置暑量量曼! 曼曼皇皇 摘要 互联网正在以惊人的速度增长，掌握互联网的结构以及其他动态属性，对于 网络新协议的设计、网络新功能的实现、网络服务质量分析、网络攻击的检测等 研究具有非常重要的科学意义。互联网的分布式属性使得了解互联网的结构和属 性越来越困难。网络检测作为理解网络行为的最有效途径，是对网络行为进行特 征化、对各项指标进行量化，并充分理解和正确认识互联网的最基本手段。 在实际进行网络检测中，除了对网络检测理论、方法、技术和工具等方面开 展相关研究外，网络检测点作为实施各种网络检测方法、技术和工具的必备条件， 对其部署方法开展研究也尤为重要。有效地部署网络检测点已经成为进行网络检 测研究的热点之一。传统的网络检测点部署方法是在网络中添加硬件检测设备， 进行网络检测。这种添加硬件检测设备进行网络检测的方法，部署的网络检测点 难以动态移动和变化，随着网络的高速发展和越来越复杂多变，已经很难满足未 来网络检测的需要。 为了克服传统的添加硬件检测设备的不足，本文提出相关方法在网络中选取 和放置具有代表性的节点，并通过在这些网络节点上安装网络检测软件，形成网 络检测点，进行网络检测。可见解决网络检测点部署问题的关键在于如何有效地 在网络中选取和放置具有代表性的网络节点。针对此问题，本文提出了网络延迟 检测点和网络流量检测点的选取和放置方法，同时对各种网络检测点选取方法的 统一化问题也进行了研究。主要研究成果和创新如下： ( 1 ) 将网络延迟检测点的选取问题转化为网络拓扑有权图聚类问题，结合 网络的层次结构特性，根据网络节点之间的网络延迟数值，提出使用系统聚类法 来解决网络拓扑有权图聚类问题。通过对系统聚类法基本思想的分析，提出递归 去除l 度异常节点算法，提高各种系统聚类算法的聚类效果。为了有效地在聚类 结果中选取具有代表性的中心节点，提出动态距离和最小算法。 ( 2 ) 为了评价各种系统聚类算法在解决网络延迟检测点选取和放置问题中 的聚类效果，总结了网络延迟检测点的选取原则：1 ) 依据节点之间的网络延迟 进行聚类，聚类结果的每个类内节点个数应该比较接近，类内节点间应该具有较 小的网络延迟；2 ) 在每个类中选取合适的中心节点部署网络检测软件，保证该 中心节点能代表类中其他节点，同时各个类中心节点之间网络延迟应该比较大， 以保证检测点具有较高的覆盖范围；3 ) 在相近的聚类效果前提下，受到经济及 可行性的制约，网络延迟检测点数量越少越好。根据网络延迟检测点的选取原则， 提出3 个聚类效果评价标准：1 ) 类内节点个数标准方差评价法；2 ) 类合并距离 评价法；3 ) 类中心间平均距离评价法。 ( 3 ) 将网络流量检测点选取问题抽象为求解无向图的弱顶点覆盖问题。在 关键词网络检测；检测点；选取；延迟；流量 a b s t f a c t a b s t r a c t t h ei n t e r n e ti sg r o w i n ga ta i la l a r m i n gr a t e m a s t e r i n gt h es t r u c t u r ea n do t h e r d y n a m i cp r o p e r t i e so ft h ei n t e m e th a sv e r yi m p o r t a n ts c i e n t i f i cs i g n i f i c a n c ef o rt h e n e wa g r e e m e n to fn e t w o r kd e s i g n s ，n e t w o r ki m p l e m e n t a t i o no fn e wf e a t u r e s ，n e t w o r k q u a l i t yo fs e r v i c ea n a l y s i s ，a n dn e t w o r ka t t a c kd e t e c t i o n t h ed i s t r i b u t e dp r o p e r t yo f t h ei n t e m e tm a k e su n d e r s t a n d i n gt h es t r u c t u r ea n dp r o p e r t i e so ft h ei n t e m e ti sv e r y d i f f i c u l t n e t w o r km e a s u r e m e n ti st h em o s te f f e c t i v ew a yf o ru n d e r s t a n d i n gt h e n e t w o r kb e h a v i o r , a n di st h em o s tb a s i cm e a n st oc h a r a c t e r i z et h en e t w o r kb e h a v i o r , t oq u a n t i f yt h ev a r i o u si n d i c a t o r sa n df u l l yu n d e r s t a n da n dc o r r e c tu n d e r s t a n d i n go f t h ei n t e m e t i na d d i t i o nt or e s e a r c h i n gn e t w o r km e a s u r e m e n tt h e o r y , m e t h o d s ，t e c h n i q u e sa n d t o o l si n p r a c t i c a l n e t w o r km e a s u r e m e n t ，n e t w o r km e a s u r e m e n t - n o d ei st h e i m p l e m e n t a t i o no ft h ev a r i o u sn e t w o r km e a s u r e m e n tm e t h o d s ，t e c h n i q u e sa n dt o o l s n e c e s s a r yc o n d i t i o n s ，a n dc o n d u c t i n gr e s e a r c ho fi t sd e p l o y m e n tm e t h o di sa l s o p a r t i c u l a r l yi m p o r t a n t t h ee f f e c t i v ed e p l o y m e n to fn e t w o r km e a s u r e m e n t n o d e sh a s b e c o m eo n eh o to ft h en e t w o r km e a s u r e m e n t t h et r a d i t i o n a ld e p l o y m e n tm e t h o do f n e t w o r km e a s u r e m e n t - n o d ei st oa d dh a r d w a r ed e t e c t i o ne q u i p m e n ti nt h en e t w o r kf o r t h en e t w o r kd e t e c t i o n i nt h i sa d d e dh a r d w a r ed e t e c t i o ne q u i p m e n tm e t h o df o r n e t w o r km e a s u r e m e n t ，t h ed e p l o y m e n to fn e t w o r kd e t e c t i o ne q u i p m e n ti sd i f f i c u l tt o m o v ea n dc h a n g ed y n a m i c a l l yw i t ht h er a p i dd e v e l o p m e n ta n di n c r e a s i n g l yc o m p l e x o ft h en e t w o r k ，a n dh a sb e e nd i f f i c u l tt om e e tf u t u r en e e d so ft h en e t w o r k m e a s u r e l e n t i no r d e rt oo v e r c o m et h et r a d i t i o n a ll a c k st oa d dh a r d w a r ed e t e c t i o ne q u i p m e n t ，t h i s d i s s e r t a t i o np r e s e n t sr e l a t e dm e t h o d sf o rs e l e c t i o na n dp l a c e m e n to ft h er e p r e s e n t a t i v e n o d e si nt h en e t w o r k ，a n dw i t hi n s t a l l i n gt h en e t w o r kd e t e c t i o ns o f t w a r eo nt h e s e n e t w o r kn o d e sf o r mt h en e t w o r km e a s u r e m e n t - n o d e st o c o m p l e t et h e n e t w o r k d e t e c t i o n h o wt oe f f e c t i v es e l e c t i o na n dp l a c e m e n to ft h er e p r e s e n t a t i v en o d e si st h e k e yp r o b l e mo fn e t w o r km e a s u r e m e n t - n o d ed e p l o y m e n t i nt h i s d i s s e r t a t i o n ，w e p r o p o s e dt h e s e l e c t i o na n dp l a c e m e n tm e t h o d so fn e t w o r kd e l a ya n dt r a f f i c m e a s u r e m e n t n o d ea r ep r o p o s e d ，a n dt h eu n i f i c a t i o nm e t h o df o r t h ed i f f e r e n tn e t w o r k m e a s u r e m e n t n o d ed e p l o y m e n ti sa l s os t u d i e d t h em a i nr e s e a r c ha n di n n o v a t i o na r e a sf o l l o w s ： ( 1 ) t h ep r o b l e mo ft h es e l e c t i o nn e t w o r kd e l a ym e a s u r e m e n t n o d ei st u r n e dt ot h a t o ft h en e t w o r kt o p o l o g yc l u s t e r i n g c o m b i n i n gp r o p e r t i e so ft h en e t w o r kh i e r a r c h y , w ea p p l yt h eh i e r a r c h i c a l c l u s t e r i n ga l g o r i t h m s t os o l v et h en e t w o r kt o p o l o g y c l u s t e r i n gp r o b l e mw i t ht h en e t w o r kd e l a yd a t a b a s e do na n a l y s i so ft h eh i e r a r c h i c a l c l u s t e r i n g ，w ep r e s e n ta na l g o r i t h mo fr e c u r s i v e l ye l i m i n a t i n go n eo u t - d e g r e e e x c e p t i o n a ln o d e s ，a n dt h ep r o p o s e da l g o r i t h mi m p r o v e st h ee f f i c i e n c y o ft h e h i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m s f o re f f e c t i v e l ys e l e c t i n gt h er e p r e s e n t a t i v ec e n t r a l n o d e ，ad y n a m i c a ll e a s td i s t a n c es u m m a t i o na l g o r i t h mi sp r o p o s e d i i i t h es i n g l ep r o p e r t ys u c ha sn e t w o r kd e l a y , t r a f f i ce t c ，a n dt h e ns e l e c ta n dd e p l o yt h e n e t w o r km e a s u r e m e n t n o d e t h r o u g ht h er e s e a r c ho ft h ev a r i o u ss e l e c t i o na l g o r i t h m s ， w ep r o p o s ead y n a m i cm e a s u r e m e n t n o d e ss e l e c t i o na l g o r i t h mb a s e do nd e g r e ea n d h o p ( d m s ) t h es i m u l a t i o nr e s u l t ss h o wt h a td m sa l g o r i t h mc a ns e l e c tt h ed i f f e r e n t n e t w o r kp r o p e r t i e sm e a s u r e m e n t n o d ew i t hs e tt h ed i f f e r e n tp a r a m e t e r s a n dh a v ea b e t t e rs c a l a b i l i t ya n dp r a c t i c a l i t y k e y w o r d sn e t w o r k m e a s u r e m e n t ；m e a s u r e m e n t - n o d e ；s e l e c t i o n ；d e l a y ；t r a f f i c i v 口录 目录 摘要i a b s t r a c t i i i 第1 章绪论一1 一 1 1 研究背景- 1 1 1 1 网络检测标准- 1 - 1 1 2 网络检测研究进展一2 - 1 1 3 网络检测中检测点作用一5 - 1 2 国内外研究现状- 6 一 1 2 1 网络延迟检测点研究一7 1 2 2 网络流量检测点研究一8 1 3 研究内容及意义一9 一 1 4 创新性工作- l o - 1 5 课题来源- 1 2 1 6 本文结构- 1 2 一 第2 章网络检测概述一15 2 1 网络检测简介- 1 5 2 1 1 网络检测定义- 1 5 - 2 1 2 网络检测要素一1 6 2 1 3 网络检测分类一1 6 2 2 网络延迟检测- 1 8 2 2 1 网络延迟一1 8 - 2 2 2 网络延迟检测方法学- 2 1 - 2 3 网络流量检测一2 2 2 3 1 网络流量检测方法- 2 2 - 2 3 2 网络流量检测技术- 2 3 2 4 网络拓扑检测一2 5 - 2 4 1 常见网络拓扑结构- 2 5 - 2 4 2 网络拓扑检测方法一2 7 2 5 网络拓扑建模一3 0 一 2 5 1 网络拓扑建模研究历程- 3 0 一 2 5 2 网络拓扑建模分类一31 2 5 3 网络拓扑建模工具和拓扑生成器一3 2 2 6 本章小结一3 3 一 第3 章网络检测点选取和放置总体方法研究一3 5 3 1 网络检测体系结构一3 5 3 1 1 集中式单点检测体系结构一3 5 - 3 1 2 分布式多点检测体系结构- 3 5 3 2 基于分布式检测体系结构的检测点选取和放置方法研究- 3 6 3 2 1 网络延迟检测点选取和放置问题一3 6 - 3 2 2 网络流量检测点选取一3 8 3 2 3 各种网络检测点统一化部署3 8 - v 北京t 业人学t 学博f j 学位论文 3 2 4 网络检测点选取和放置方法的评价标准一3 8 3 3 本章小结3 9 第4 章网络延迟检测点选取和放置方法研究一4 1 4 1 问题分析4 1 4 2 系统聚类法4 2 4 2 1 最短距离法4 2 4 2 2 最长距离法4 3 4 2 3 中间距离法4 4 4 2 4 类平均法4 4 4 2 5 重心法4 6 4 2 6 离差平方和法一4 6 4 3 递归去除1 度异常节点算法一4 8 4 4 动态距离和最小算法4 9 4 5 聚类算法的评价标准4 9 4 5 1 类内节点个数标准方差评价法一4 9 4 5 2 类合并距离评价法5 0 一 4 5 3 类中心间平均距离评价法5 0 4 6 仿真实验一5 1 - 4 6 1 实验设置一51 4 6 2 实验结果与分析51 - 4 7 本章小结一5 6 一 第5 章已知拓扑结构选取网络流量检测点一5 7 5 1 问题分析5 7 5 2 相关定义一5 7 5 3 基于邻接矩阵的检测点选取算法5 9 5 3 1 算法思路5 9 5 3 2 算法描述一6 0 5 3 3 算法举例说明6 0 一 5 3 4 仿真实验6 2 5 4 改进基于邻接矩阵的检测点选取算法6 3 5 4 1 算法思路一6 3 5 4 2 算法描述6 3 5 4 3 算法举例说明6 4 5 4 4 仿真实验一6 6 5 5 本章小结6 7 第6 章未知拓扑结构选取网络流量检测点一6 9 6 1 问题分析6 9 6 2 相关定义6 9 6 3 基于三元组信息的检测点选取算法7 0 6 3 1 算法描述一7 0 6 3 2 算法举例说明7l - 6 4 仿真实验及分析7 3 6 5 本章小结7 3 第7 章各种网络检测点选取方法的统一化研究一7 5 一 v i 同录 7 1 引言一7 5 7 2 动态网络检测点选取算法一7 5 7 3 用于网络流量检测点选取一7 6 7 3 1 相关知识一7 6 7 3 2 算法举例说明一7 6 7 3 3 仿真实验一7 8 7 4 用于网络延迟检测点选取一7 9 7 4 1 相关知识一7 9 - 7 4 2 仿真实验一7 9 7 5 本章小结- 8 0 一 结论一8 1 一 主要研究成果81 未来展望一8 2 一 参考文献一8 5 一 攻读博士学位期间所取得的研究成果一9 1 一 致谢一9 3 一 v i i v i i i 构和属性越来越困难，网络检测是对网络行为进行特征化、对各项指标进行量化， 并充分理解和正确认识互联网的最基本手段，是理解网络行为的最有效途径1 1 。 1 1 1 网络检测标准 互联网工程任务组( i n t e r n e te n g i n e e r i n gt a s kf o r c e ，i e t f ) 【2 】作为网络检测 与分析的研究和相关标准的制定组织，有很多与检测领域相关的工作组，主要有 i p p mw g 、i p f i xw g 、r t f mw g 、r m o nw g 、p s a m pw g 等。这些工作组 主要是针对网络检测指标体系以及部分网络检测方法的标准化等方面进行了大 量的工作。 i p p m i 作组主要致力于指定各种网络检测度量指标体系，为网络数据传输 服务的质量、性能、可靠性的检测提供依据。该工作组研究的重点主要包括连通 性( c o n n e c t i v i t y ) 、单向延迟和丢包率( o n e w a yd e l a ya n dl o s s ) 、双向延迟和 丢包率( r o u n d t r i pd e l a ya n dl o s s ) 、延迟抖动( d e l a yv a r i a t i o n ) 、丢失模式( l o s s p a t t e r n s ) 等。 口流信息导出( i pf l o wi n f o r m a t i o ne x p o r t ，i p f i x ) 工作组【3 l 主要致力于口流 信息导出方面的研究工作，比较贴近于实际的网络检测领域。 实时数据流检测( r e a l t i m et r a f f i cf l o wm e a s u r e m e n t ，r t f m ) 工作组1 4 】是针 对网络被动检测领域进行相关的研究，主要对报文的头部进行检测和分析。 远程网络监控( r e m o t en e t w o r km o n i t o r i n g m ，r m o n ) 工作组【5 】的目标是定 义一个用来进行远程网络监控的管理对象集合，这个管理计划能够提供对远程网 络的多个层次上的流量监控功能，同时满足故障、配置、性能管理的需求。这个 框架与简单网络管理协议( s n m p ) 的框架和标准相兼容。 分组抽样( p a c k e ts a m p l i n g ，p s a m p ) 工作组【6 】的主要工作是定义一种能够 通过分析统计或者是其他方法来对数据分组进行抽样的标准集，这种标准必须能 够满足普遍适用性和功能的兼容性，使得基于该标准的检测能够满足对足够广泛 的适用。 北京- r q k 人学t 学博l j 学位论丈 1 1 2 网络检测研究进展 很多国际组织、研究机构、大学和知名i t 企业都在从事与网络检测与分析相 关的研究工作，如n l a n r t 7 1 、c a i d a t 引、i e p m 9 1 、s u r v e y o r i l 0 1 、i p m ar 1 1 1 、i t e w g t l 2 】 等，其中n l a n r 、c a i d a 为专门致力于网络检测和分析研究的机构。 应用网络研究国家实验室( n a t i o n a ll a b o r a t o r yf o ra p p l i e dn e t w o r kr e s e a r c h ， n l a n r ) 是由美国国家科学基金会( n s f ) 资助的网络应用研究机构。目前 n l a n r 中直接与网络检测相关的研究包括被动检测分析项目( p a s s i v e m e a s u r e m e n ta n a l y s i s ，p m a ) 【l 驯和主动检测项目( a c t i v em e a s u r e m e n tp r o j e c t ， a m p ) 1 1 4 1 等。p m a 项目的目标是深入探究互联网运行、行为的细节，已经开发 为达到这些目标而需要的检测工具。其基本做法是通过被动采集通过关键网络链 路的数据分组头信息，通过这些信息可以研究相关网络的工作负载特性以及其他 一些网络性能特性。目前采集这些分组头信息的采集点分布在美国境内的2 0 多个 地方，在p m a 项目的支持下，研究人员开展了很多有意义的研究工作【l5 。1 。7 1 。a m p 项目是一个由许多单位共同参与的联合研究项目，是以主动的方式检测参与该项 目的单位之间的链路性能，包括它们之间的分组转发所经过的路径、双向延迟 r t t 、丢包率以及在有请求情况下的吞吐率等信息。目f j 在全球范围内美国、欧 洲、亚太地区的教育科研网络中部署了1 5 0 多个a m p 检测器，并对这些a m p 检测 器开展两两之间的性能检测。a m p 项目长期采集的网络检测数据，有助于网络 工程师、设计人员以及研究人员对改进网络的设计、进一步规划和优化网络的容 量，取得了很多最新的研究成果 1 8 - 2 0 。图1 1 为a m p 检测器在美国本土的部署图。 图1 1a m p 检测器在美国本七的部署图( 星号代表部署了a m p 检测器的地方) f i g u r e i - l t h ed e p l o y m e n to fa m pm e s hi nu s a ( s t a r s r e p r e s e n ts i t e si nt h ea m pm e s h ) 一2 一 第1 翠绪论 互联网数据分析合作组织( t h ec o o p e r a t i v ea s s o c i a t i o n f o r i n t e m e td a t aa n a l y s i s ，c a i d a ) 是有k cc l a f f y 和t r a c i em o n k 博士于1 9 9 7 仓t j 建的， 是专门对互联网流量进行分析和研究的国家组织，其成员主要来自商业、政府和 研究机构。c a i d a 开展并参与了很多世界性的网络检测计划，并开发了很多检 测工具 2 1 】，对互联网流量进程采集、统计和分析，以期达到全球网络基础设施 的合理利用，优化网络拓扑结构，提高网络的使用性能。c a i d a 一直积极参与 和支持许多和网络科学与工程相关的研究活动 2 2 3 5 】。作为c a i d a 具有代表性 的网络检测工具，s k i t t e r 3 6 禾l j 用i c m p 的t t l 特性，检测从一个源到数千个目的 地的分组转发路径，从而构建整个互联网的拓扑互连关系，同时帮助网络运行人 员分析端到端的路由、延迟、丢包等信息。c a i d a 已经在世界范围内部署了很 多分布式的s k i t t e r 检测点，检测来自美国、欧洲和亚洲的2 3 0 0 0 多个目的主机， 通过收集检测点的数据来获得整个互联网的属性信息。图1 2 为i p 路径的s k i t t e r 检测样本的可视化图。 图1 - 2i p 路径的s k i t t e r 检测样本的可视化图 f i g u r e1 - 2 i pp a t h so fs k i t t e rv i s u a l i z a t i o n 斯坦福线性加速器中心( s t a n f o r dl i n e ra c c e l e r a t o rc e n t e r ，s l a c ) 是由美国 能源部资助的高能物理实验室。它的主要人员是设计、建设和运行业内先进的电 子加速器和相关的实验装备。由于s l a c 从事的工作涉及到大量的科学计算，需 要与美国国内及世界各国相关的研究机构之间进行数据的共享和协作，对这些研 究机构之间的高性能网络链路和通信非常敏感，所以s l a c 于1 9 9 5 年成了了一个 北京t 业，：掌t 学博l + 学位论文 专门对互联网端到端性能监视小组( i n t e r n e te n d t o e n dp e r f c i f i n a n c em o n i t o r i n g ， 正p m ) 从事网络连通性和端到端性能的监视，以及相关检测工具的开发工作。 i e p m 成立以来，在端到端性能检测和监视方面进行了大量的工作，也取得了丰 富的研究成果3 7 4 2 1 。p i n g e r ( p i n ge n d t o e n dr e p o r t i n g ) 【4 3 1 项目是i e p m 所涉及 到的主要项目之一，主要是利用p i n g 命令来检测网络的性能，其检测的主要肿1 2 - 1 ：厶匕i j e , 指标包括网络延迟、丢包率、延迟抖动、t c p 吞吐率等。到目前为止，p i n g e r 项 目是目前世界上覆盖范围最广的端到端网络性能监视项目之一，已经在全球1 4 个国家部署了3 5 个检测主机，被检测的节点超过了3 6 0 0 个。图1 3 为p i n g e r 项目 的全球检测系统部署图。 图1 3p i n g e r 项目的全球检测系统图 f i g u r e1 - 3 t h eg l o b a lm o n i t o r i n gm a po fp i n g e rp r o j e c t s u r v e y o r 是由先进网络与服务公司( a n v a n c e dn e t w o r k s e r v i c ei n c a n s ) 于1 9 9 5 年开始实施的一个网络检测项目。该项目希望通过在全球众多高等教育和 研究机构中部署网络检测设备( 网络探针等) ，从而建立网络检测体系【l0 1 。 s u r v e y o r 项目的目标是建立一个网络检测的基础设施并开发相关的技术，使其能 够帮助网络用户和网络服务提供商，理解互联网的端到端链路的网络性能和可靠 性。s u r v e y o r 项目开始实施以来，已经在全世界6 0 多个科研和教育机构中部署 并检测了超过1 5 0 0 条路径。图l 4 和图1 5 分别为s u n ，e y o r 项目检测点的全球部署 图和美国本土部署图。 籀1 章绪论 = 广二，旷一苌 图l _ 4s u r v e y o r 项目检测点的全球部署图 f i g u r e1 - 4s u r v e y o rp r o j e c tm e a s u r e m e n t - n o d ed e p l o y m e n to fw o r l d 图l 一5s u r v e y o r 项目检测点的全球部署图和美国本土部署图 f i g u r e1 - 5s u r v e y o rp r o j e c tm e a s u r e m e n t - n o d ed e p l o y m e n to fu s a 通过上述国际组织、研究机构、大学和知名盯企业对网络的多年研究，已经 分别拥有了一些网络性能统计信息的样本库，供研究者们评估和使用以及进行数 据挖掘。国内如清华大学1 4 4 , 4 5 1 、哈尔滨工业大学删等机构也进行了相关的研究。 1 1 3 网络检测中检测点作用 上述提到的n l a n r 组织的a m p 项目在全球范围内美国、欧洲、和亚太地区 的教育科研网络中部署和建立了1 5 0 多个检测器，而p m a 项目也部署t 2 0 多个 1 2 国内外研究现状 在网络节点部署网络检测工具可以检测和收集流量等信息。例如，在c i s c o 的路由器上安装n e t f l o w l 4 7 1 可以收集指定节点对之间的流量数据和包信息。部署 了n e t f l o w 等检测工具的路由器会产生大量的数据报文，对网络和系统性能产生 较大影响。链路检测设备只能检测到本链路的流量情况，而部署在网络节点的检 测设备形成检测点，可以检测到与网络节点相连的每条链路的情况，并可根据收 集的网络信息来减少网络检测点的数量。在进行网络检测时，通常要访问路由器 一6 一 第1 币绪论 等网络设备中的数据信息，如果逐一访问每个网络设备，会对网络造成很大的开 销。研究表明，在局域网的一台c i s c 0 4 0 0 0 系列路由器上，进行g e t n e x t 查询，在 轮询期间路由器的吞吐率会下降1 5 2 0 。在获得完整网络信息的前提下，如何 选取网络检测点的数量及位置使得检测信息的传送给网络造成的额外负载最少 是一个非常值得考虑的问题。为了更加有效地部署网络检测点，完成各种网络属 性检测工作，近些年来国外研究者对网络检测点部署方法开展了一些有意义的尝 试。 在网络检测点部署问题研究初期，f r a n c i s 和j a m i n 首先提出一种基于网络节 点问距离关系的i n t e m e t 网络结构模型，称为i d m 印s 【4 8 1 。i d m a p s 是美国国家科学 基金会n s f 资助的一个大型研究项目，其研究目的是提供一种大规模网络距离 估计服务，项目需要确定检测工具t r a c e r s 部署的数量和位置，文献 4 9 1 研究了两 个问题：第1 个问题是给定检测站与目标节点的最大距离，求在满足最大距离约 束下的覆盖全网所需检测站的数量：第2 个问题是给定检测站的数量，确定检测 站的分布，使检测站与目标节点之间的最大距离最小。有两类解决方法来解决这 两个问题：第1 个问题解决方法是基于k 层优良分隔树( k h i e r a r c h i c a l l y w 甜s e p a r a t e dt r e e s ，k h s t ) 算法【5 0 】；第2 个问题可映射到k 中心问题( k c e n t e r p r o b l e m ) 1 5 1 1 。i d m a p s 项目中使用k - h s t 和k c e n t e r 方法在这个网络结构模型中 部署检测点。随着网络检测的不断深入，各种网络性能检测点的部署问题，越来 越受到网络研究和检测人员的兴趣，目前在网络延迟检测点和流量检测点部署问 题上也取得了一些研究进展。 1 2 1 网络延迟检测点研究 对于网络大规模异常事件的检测，如网络蠕虫病毒等，其检测效果直接取决 于网络检测点的部署，特别是针对网络延迟而部署的检测点。网络检测点的数量 越多，对网络异常检测及其传播控制就越有效。理想状态下如果能够在每个骨干 路由器进行检测，对网络异常事件的检测最有效果，显然相应的部署花费是无法 接受的。但是如果网络检测点部署的太少，则检测范围就会局限在部署网络检测 点的网络中，很难了解网络的整体情况，不能达到对大规模异常事件的有效检测 及控制。 在研究分布式入侵检测系统中延迟检测点的部署问题时，p o r r a s 等p 列提出将 检测点放置在网络出口路由器上；c o o k e 等【5 3 】提出基于网段来放置检测点的方 法；f r a n c i s 矛l l j a m i n 掣5 4 】提出基于层次化入侵检测系统放置框架，主要的原则是将 检测点放置在大部分网络数据流经的地方。这些延迟检测点的部署方法主要还是 基于以往网络检测经验，以人为的形式进行选取和放置，具有一定的局限性，很 难适应未来网络迅速发展的要求。 北京t 业人学t 学博i j 学位论文 目前国内对这方面也进行了相关的研究，段海新等 5 5 1 根据入侵检测系统中网 络检测经验，提出了两种网络延迟检测点放置策略：1 ) 在网络边界上安装检测 软件来发现异常：2 ) 在骨干网络的路由器、交换机等网络设备上安装检测软件。 何慧等【5 6 】对入侵检测系统中延迟检测点的部署问题进行