（计算机科学与技术专业论文）基于双抽样的测量流长度分布的算法研究.pdf

中文摘要 摘要 网络流量测量和分析对于网络管理、网络规划和网络安全应用等都有非常重 要的作用。近年来随着网络带宽的高速发展，信息量快速增加，要测量网络中的全 部数据流量变得越来越困难。如何快速准确地测量网络流量成为一个研究热点。 为了解决网络测量所面临的问题，人们提出了抽样测量技术，即抽样测量部 分流量，然后从统计学角度估计原始流信息。抽样测量技术分为基于流的抽样和 基于报文的抽样。基于流的抽样估计精度高，但是资源消耗量大；基于报文的抽 样可扩展性好，但是估计精度低。 本文在分析基于流的抽样技术和基于报文的抽样技术的基础上，提出了双抽 样方法。双抽样方法的抽样流需要经过两次抽样才能获得。首先进行流抽样得到 一组抽样流，然后进行报文抽样，得到最终的抽样流。以网上采集的t r a c e s 进行 抽样试验，经对比分析表明与单纯的报文抽样和流抽样相比，双抽样方法在系统 资源消耗方面有很大优势，减少了抽样过程中所要维护的信息量。 为了解流量及所需资源情况，知道未抽样流的长度和数量是有意义的，本论 文研究了如何由抽样报文流统计数据推断出所对应的未抽样流的统计数据的算 法。抽样会造成信息的损失。首先，分析了双抽样方法中信息损失情况，第一步 的流抽样导致了原始流数量的减少；第二阶段的报文抽样在第一阶段抽样流的基 础上既有流数量的减少，也有流长度信息的损失。针对流抽样的估计，根据流被 抽空的概率大小将流分为长流和短流，对于长流用比例法估计；对于短流用e m 算法估计，得到了由第一阶段流抽样所得抽样流的流长分布。针对报文抽样的估 计，用比例法在前一阶段估计得到的抽样流基础上，得到了原始流的流长分布情 况。实验结果表明，由双抽样方法得到的抽样流能够有效地估计出原始流的分布。 关键词：流抽样；报文抽样；双抽样；流长度；酬算法 英文摘要 a b s tr a c t n e t w o r kt r a f f i cm o n i t o r i n ga n da n a l y s i si sc r u c i a lf o rm a n yn e t w o r ka p p l i c a t i o n s ， s u c ha sn e t w o r km a n a g e m e n t s ，n e t w o r kp l a n n i n g ，a n dn e t w o r ks e c u r i t ya p p l i c a t i o n s w i t ht h er a p i dg r o w t ho fl i n ks p e e di nr e c e n ty e a r , i ti sv e r yd i f f i c u l tt om e a s u r ea l lo f t h ei n f o r m a t i o nw h e nf a c i n gl a r g en u m b e ro ff l o ws o u r c e s h o wt o a c c u r a t e l ya n d e f f i c i e n t l ym o n i t o rt h el a r g ev o l u m eo fn e t w o r kf l o w sb e c o m e s ar e s e a r c hh o t - s p o t i no r d e rt os o l v et h ep r o b l e m si nt h en e t w o r km e a s u r e m e n t ，t h e s a m p l i n g m e a s u r e m e n ti sp r o p o s e d ，i e s a m p l i n gm e a s u r e m e n ti su s e dt oe s t i m a t et h eo r i g i n a l f l o wi n f o r m a t i o nf r o mt h es t a t i s t i c a lp o i n to fv i e w s a m p l i n gm e a s u r e m e n tt e c h n o l o g y i sc l a s s i f i e di n t of l o w - b a s e ds a m p l i n ga n dp a c k e t - b a s e ds a m p l i n g t h ef l o w b a s e d s a m p l i n gh a v eh i g ha c c u r a c y , b u tt h er e s o u r c e sc o n s u m e di si nl a r g eq u a n t i t i e s ；t h e p a c k e t - b a s e ds a m p l i n gi ss c a l a b i l i t ya n de x p a n s i v e l y , b u ti t se s t i m a t i n ga c c u r a c yi sl o w i no r d e rt oo v e r c o m ea f o r e m e n t i o n e ds h o r t c o m i n g so fp a c k e ts a m p l i n ga n df l o w s a m p l i n g ，w ep r o p o s eas a m p l i n gs t r a t e g yc a l l e dd o u b l es a m p l i n gw h i c hc o n s i s t so f f l o ws a m p l i n ga n dp a c k e ts a m p l i n g t w os a m p l i n gr u l e sa r ei n c l u d e di nt h ea b o v ew o r k ： f l o ws a m p l i n g ，w h e r ee n t i r ef l o w so fp a c k e t sa r er e t a i n e do rd i s c a r d e da to n c e ，a n d p a c k e ts a m p l i n g ，w h i c ha c t sd i r e c t l yo ni n d i v i d u a lp a c k e t sa n di si g n o r a n to ff l o w s u s i n gr e a ln e t w o r kt r a f f i ct r a c e s ，w es h o wt h a tt h ep r o p o s e dd o u b l es a m p l i n gt e c h n i q u e i n d e e dd e c r e a s e st h eu s a g eo ft h es y s t e ms o u r c e sa n dl e s s e nt h ei n f o r m a t i o n k n o w i n gt h en u m b e ra n dl e n g t h o ft h e u n s a m p l e df l o w sr e m a i n s u s e f u l c h a r a c t e r i z i n gt r a f f i ca n dr e s o u r c e sr e q u i r e dt oa c c o m m o d a t ei t sd e m a n d s t h i sp a p e r i n v e s t i g a t e st h em e t h o d st h a tu s ef l o ws t a t i s t i c sf o r m sf r o ms a m p l e dp a c k e ts t r e a mt o i n f e rt h el e n g t h so ff l o w sa n dt h e i rf r e q u e n c i e si nt h eu n s a m p l e ds t r e a m s o m em e t h o d s f o re s t i m a t i o no fo r i g i n a lf l o wl e n g t hd i s t r i b u t i o nf r o ms a m p l i n gf l o ws t a t i s t i c sa r e d i s c u s s e dt oo b t a i nt h ed i s t r i b u t i o nf e a t u r eo fu n s a m p l e df l o w s s a m p l i n ge n t a i l sa n i n h e r e n tl o s so fi n f o r m a t i o n f i r s to fa l l ，w ea n a l y s et h ei n f o r m a t i o nl o s si nd o u b l e s a m p l i n gm e t h o d i nt h ep a c k e ts a m p l i n gp r o c e s s ，t h ei n f o r m a t i o nl o s s i st h et o t a l n u m b e r so ff l o w sd e c r e a s e da n dt h en u m b e ro fp a c k e t so ff l o w sl e s s e n e db yt h ep a c k e t s a m p l i n g i nt h ef l o ws a m p l i n gp r o c e s s ，t h ei n f o r m a t i o nl o s si so n l yt h et o t a ln u m b e r s o ff l o w sd e c r e a s e db yf l o ws a m p l i n g t h en e t w o r kf l o wi sd i v i d e di n t ol o n gf l o w sa n d s h o r to n e s ，a c c o r d i n gt ot h ep r o b a b i l i t yo ff l o wu n s a m p l e d i ne s t i m a t i o no fp a c k e t 英文摘要 s a m p l i n g ，t h es c a l i n gm e t h o di su s e di ne s t i m a t i n gt h ed i s t r i b u t i o no fl o n gf l o w , a n dt h e e x p e c t a t i o nm a x i m i z a t i o n ( e m ) a l g o r i t h mi su s e di ne s t i m a t i n gt h ed i s t r i b u t i o no fs h o r t f l o w i ne s t i m a t i o no ff l o ws a m p l i n g ，w ea l s ou s et h ee ma l g o r i t h mt oe s t i m a t et h e d i s t r i b u t i o no fo r i g i n a lf l o wo nt h ek n o w no fd i s t r i b u t i o n so fs a m p l i n gf l o ww h i c hi s e s t i m a t e db e f o r e t h ee x p e r i m e n tr e s u l t sd e m o n s t r a t et h a tt h ei n f e r r e dd i s t r i b u t i o n sa r e e f f i c a c i o u s k e yw o r d s ：f l o ws a m p l i n g ；p a c k e ts a m p l i n g ；d o u b l es a m p l i n g ：f l o wl e n g t h ； e m a l g o r i t h m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：基王塑抽搓笪测量逋量廑坌查的篡这婴窥：。除论文中已经 注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表 或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签锈问伊7 年7 月争日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密( 请在以上方框内打“”) 论文作者签名彦朗 导师签名：缈导师签名：名沙陟、厂 日期： 一月￥日 ff 基于双抽样的测量流长度分布的算法研究 第1 章绪论 2 0 世纪以计算机为代表的信息产业的出现，标志着人类社会进入了信息时代。 计算机网络的研究和发展，特别是互联网在全球的推广与应用，对世界科技、经济和 社会都产生了重大的影响。就计算机网络本身而言，它是计算机技术与通信技术相 结合的产物，它的出现和发展促进了计算机应用和通信方式发生革命性的变化【。 互联网是上亿台计算机互联而成的全球性网络，随着更多的网络服务的提供及 用户的不断增加，网络主干流量的增长越来越迅速，网络行为也变得越来越复杂。虽 然相关的组网与管理技术在不断地完善，但是人们对它在局部和整体范围内所体现 出的行为特征依然没有一个正确和完整的认识。 掌握i n t e r n e t 的行为是网络规划、网络管理、网络安全、新网络协议和网络应 用设计等诸多研究工作的重要前提，因此近年来对大规模互联网络行为的研究已经 成为本领域被关注的热点目标。而网络测量是分析、掌握网络行为的基础，是一种通 过收集数据或报文踪迹，以定量地分析不同的网络应用在网络中活动规律的技术。通 过测量分析可以掌握网络行为的基本特征，有助于寻找网络行为变化的规律，构造 并验证网络行为的数学模型。所以，针对网络行为的测量与分析方法展开系统性的 研究将对i n t e r n e t 行为学方面的研究取得理论突破具有重要的意义。 1 1in t e r n e t 的发展 i n t e m e t 是全球最大的、开放的、由众多网络互联而成的计算机网络。i n t e m e t 的发展已经经历了三个阶段，逐渐走向成熟。从1 9 6 9 年i n t e r n e t 的前身a r p a n e t 的诞生到1 9 8 3 年，这是研究试验阶段，主要是进行网络技术的研究和试验。从1 9 8 3 年到1 9 9 4 年是i n t e r n e t 的实用阶段，在美国和一部分发达国家的大学和研究部门中 得到j 一泛应用，它是作为用于教学、科研和通信的学术网络。从1 9 9 4 年以后，丌 始进入i n t e r n e t 商业化阶段，除了原有的学术网络应用外，政府部门、商业企业以 及个人广泛使用i n t e m e t ，而且全世界绝大部分国家都纷纷接入i n t e m e t ，这种迅猛 第1 章绪论 发展的进程表明i n t e m e t 正日益成熟。 至今，全世界没有人能够知道i n t e m e t 的确切规模。i n t e r n e t 正以当初人们始料 不及的惊人速度向前发展，今天的i n t e m e t 已经从各个方面逐渐改变人们的工作和 生活方式。 i n t e m e t 的重大意义并不在于它的规模，而在于它提供了一种全新的全球性的 信息基础设施。当今世界正向知识经济时代迈进，信息产业已经发展成为世界发达 国家的新的支柱产业，成为推动世界经济高速发展的新的源动力，并且广泛渗透到 各个领域，特别是近几年来国际互联网络及其应用的发展，从根本上改变了人们的 思想观念和生活方式，推动了各行各业的发展，并且成为知识经济时代的一个重要 标志之一。i n t e m e t 已经构成全球信息高速公路的雏形和未来信息社会的蓝图。纵 观i n t e m e t 的发展史，可以看出i n t e m e t 的发展趋势主要表现在如下几个方面： ( 1 ) 运营产业化 以i n t e r n e t 运营为产业的企业迅速崛起，从1 9 9 5 年5 月开始，多年资助i n t e m e t 研究开发的美国科学基金会( n s f ) 退出i n t e r n e t ，把n f s n e t 的经营权转交给美国 3 家最大的私营电信公司( 即s p r i n t 、m c i 和a n s ) ，这是i n t e r n e t 发展史上的重大 转折。 ( 2 ) 应用商业化 随着i n t e m e t 对商业应用的开放，它已成为一种十分出色的电子化商业媒介。 众多公司、企业不仅把i n t e r n e t 作为市场销售和客户支持的重要手段，而且把它作 为传真、快递及其他通信手段的廉价替代品，借以形成与全球客户保持联系和降低 日常的运营成本。如：电子邮件、口电话、网络传真、v p n 和电子商务等等的日 渐受到人们的重视。 ( 3 ) 互联全球化 i n t e m e t 虽然已有三十多年的发展史，但是早期主要限于美国国内的科研机构、 政府机构和它的盟国范围内使用。现在情况出现了变化，随着各国纷纷提出适合本 基于双抽样的测量流长度分布的算法研究 国国情的信息高速公路计划，已迅速形成了世界性的信息高速公路建设热潮，各个 国家都在以最快的速度接入i n t e r n e t 。 ( 4 ) 互联宽带化 随着网络基础的改善、用户接入方面新技术的采用、接入方式的多样化和运营 商服务能力的提高，接入网速度慢形成的瓶颈问题将得到进一步改善，上网速度将 会更快，带宽瓶颈约束将会消除，互联必然会宽带化，从而促进更多的应用在网上 实现，并能满足用户多方面的网络需求。 ( 5 ) 多业务综合平台化、智能化 随着信息技术的发展，互联网将成为图像、语音和数据“三网合一”的多媒体业 务综合平台，并与电子商务、电子政务、电子公务、电子医务、电子教学等交叉融 合。十n - 十年内，互联网将超过报刊、广播和电视的影响力，逐渐形成“第四媒 体”。 综上所述，随着电信、电视、计算机“三网融合”趋势的加强，未来的互联网将 是一个真正的多网合一、多业务综合和智能化的平台，未来的互联网是移动+ i p + 广播多媒体的网络世界，它能融合现今所有的通信业务，并能推动新业务的迅猛发 展，给整个信息技术产业带来一场重大的革命。 i n t e r n e t 具有以下特点： 第一，t c p i p 技术将多种不同的网络技术和管理域统一为一个整体，是i n t e r n e t 快速发展的主要原因，然而t c p i p 技术只是将各种多样性统一起来。 第二，i n t e m e t 规模庞大。2 0 0 9 年1 月的估计有6 2 5 ，2 2 6 ，4 5 6 台联网主机。i n t e m e t 的规模庞大会产生两个方面的问题：首先，网络异质性的规模会很庞大，表现出特 殊行为的少数计算机在i n t e r n e t 中可能也会有数千台，因此就要考虑这些计算机的 行为。其次，会产生比例问题，有些网络协议和机制在小规模网络中能很好地工作， 但是当网络规模增大数倍以后就不能正常运行了，大规模网络意味着一些罕见的事 情会经常出现在网络的某处。另外由于网络规模庞大，依靠人工干预以维护网络的 第1 章绪论 正常运行相当困难。 第三，i n t e m e t 增长速度快。 1 2 网络测量技术的发展 近年来互联网得到快速发展，新应用不断出现，很多研究机构都致力于开发对 互联网实施监测和测量技术的研究。网络测量和分析作为监控、理解和认识网络行 为进而优化和重新规划网络结构以及改善网络服务质量的重要手段，受到了越来越 多的网络研究人员和运行人员的重视，因而网络测量技术，特别是对网络性能测量 技术的研究，已经成为当前计算机网络领域重要的研究热点之一。 目前网络测量根据网络行为研究方向大体分为拓扑测量、流量性能测量和端到 端性能测量。为了测量需要相应的测量工具，简单的测量工具远远不能满足i n t e m e t 行为测量的需要，一些国际组织开发了各种专门用于i n t e m e t 网络测量的工具，并 建立各种网络测量体系结构。 网络测量技术始于上世纪7 0 年代初，发展于8 0 年代，9 0 年代已渐成体系，在网 络测量的方法、工具及流量的测量模型等方面取得了很大的发展。 美国在1 9 9 2 年开始着手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 ti n f r a s t r u c t u r e ) 1 1 。n i m i 是一个完整的网络测量基础框 架，并且是第一个执行大规模端到端i n t e r a c t 行为测量的软件。它是b e r k e l e y 大学 v e m 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 i m i 的目标是要 建立一个全球化的、分布式的、大规模的i n t e n l e t 测量体系。与其他许多网络测量体 系相比较，n i m i 具有可伸缩性和可部署性特点，强调构造一个网络测量的系统框架， 而不仅仅是为了某种特殊的分析目的执行特定的测量。 1 9 9 5 年，美国自然科学基金会( n a t i o n a ls c i e n c ef o u n d a t i o n ，n s f ) 开始着手对 互联网进行系统的测量。1 9 9 6 年初，在n s f 支持下美国成立了网络应用研究国家实 验室n i a n r 【3 ( t h en a t i o n a ll a b o r a t o r yf o r a p p l i e dn e t w o r kr e s e a r c h ) ，网络性能测量 是其主要研究方向之一。n l a n r 网络测量研究项目主要由被动测量分析p m a 和主 动测量分析a m p 两个研究项目组成。n l a n r 建立了网络分析基础设施n a j ，它致力 基于双抽样的测量流长度分布的算法研究 于通过对互联网的性能测量和流量测量，从而理解互联网系统级的服务模型。 1 9 9 7 年，互联网数据分析合作组织( c o o p e r a t i v ea s s o c i a t i o nf o r i n t e m e td a t a a n a l y s i sc a i d a ) 1 4 】在美国加州大学圣地亚哥分校超级计算中心成立，对网络测量的 相关理论和方法展开系统研究。i e t f 网络协议性能指标工作组( i p p m w g ) 为互联网 的测量做了许多工作，i e t f 拥有众多的r f c ( r e q u e s t f o rc o m m e n t s ) 矛t l 实验草案，制 定了一些性能指标定义的标准，用于互联网数据传输服务的质量、性能和可靠性的 测量。这些指标向网络操作者、网络终端用户和独立的测试组提供无偏差的性能测 量。而且，i p p mw g 推动有效指标测量工具和过程的共享，提供一个论坛，共享实 施和应用这些指标的信息，但是实际的实施和应用并不在工作组范围之内。i p p m w g 已经完成的工作包括近期制定的r f c 和一些协议草案，其框架主要是关于信息 分类的。 除美国外，其他国家也开展了对i n t e r n e t 的大规模测量和研究，例如加拿大的 t r i u m f 网络监视，主要目的是对国家i n t e m e t 路径上的包丢失隋况和路由特征进行 测量，以及新西兰的w a n d ( w a i k a t oa p p l i e dn e t w o r kd y n a m i c s ) q b 被动测量子项目 w i t s ( w a i k a t oi n t e r n e tt r a f f i cs t o r a g e ) ，其主要目的是创建用于统计分析和创建模拟 模型的i n t e m e t 流量模型。欧洲在1 9 9 5 年也开展了对i n t e r a c t 的测量，其中p p n c g ( 粒 子物理网络协作组) 是在这方面做得比较成功的一个组织。 我国网络的发展起步比较晚，上世纪9 0 年代初才接入i n t e r n e t ，大规模的快速发 展开始于9 0 年代末，国内的一些大学和研究所相继开展了网络测量系统以及方法的 研究工作，与国外的差距正在逐步缩小。国防科学技术大学、西南交通大学等高校 在基于i c m p 协议的p 拓扑探测方面的技术比较成熟；哈尔滨工业大学计算机科学与 工程系实现了一个大规模网络拓扑测量的原型系统，能够针对大规模网络进行路由 i p 拓扑结构的自动发现，并且进行可视化显示；中国科学院计算技术研究所信息网 络室开发出的大规模i n t e m e t 网络测量与分析系统n i p m a s ，该系统能对跨地域的大 型网络进行在线监测，并根据用户需求灵活添加业务测量工具，实现对网络主要性 能状态的监测，并且分别针对网络业务运行正常、亚健康状态( 即网络设备正常但业 务运行不正常) 和用户业务完全不能进行( 即网络设备或链路不正常) 状态进行具体性 能监测或故障定位。另外，n i p m a s 还实现了g i s 显示、动态播放和w e b 发布等功能； 第1 章绪论 在n i p m a s 的基础上，中科院计算所还开发出支持i p v 6 的大型网络测量系统f o x ， 在国内外都处于领先地位。 网络的测量方法主要有主动测量和被动测量，两种测量方法各有优缺点，分别 用于不同的场合。主动测量是通过主动产生流量直接测量网络属性，可以使用直接 分析方法。但是主动测量流量会对被测网络流量的性能产生负面影响。因此，主动 测量系统开发需仔细考虑对网络实际传输流量的影响。被动测量完全取决于被测网 络目前已有的流量，其最大优点是在测量期间不影响被测网络的流量，但会引起测 量、分析、存储等资源短缺的问趔5 , 6 , 7 , 8 1 。 1 2 1 主动测量技术 主动测量技术是由a m p ( a c t i v em e a s u r e m e n tp r o j e c t ) 组织提出的数据分析方法 【9 ，1 0 】。主动意味着测量过程中产生新的网络流量，可以引起网络部件的特殊响应( 如： t r c e r o u t e ) ，也可以用于观测网络的性能( 如：t r e n o ) 。这种测量方法实际上是映射 i n t e m e t 系统，在主动测量方式中，通过向网络发送数据、观察结果和发送数据所需 时间来研究网络行为。主动测量本身产生新的业务测量流量，利用这些业务量测量 反映网络提供给其他用户的服务参数。这些测量流量可能会引起网络的特殊响应， 或网络为流量提供某种性能。因此主动测量给网络增加潜在的荷载负担，特别是如 果没有仔细设计而使得该方法产生的流量最小，那么附加的流量会干扰网络，影响 分析结果。例如：如果为了测量在m 网络中瓶颈链路的带宽，定期向网络发送巨大 的t c p 传输，产生的附加流量可能会引起h e i s e n b e r g 效应( 即额外的流量可能会干扰 网络，并使结果分析产生误差) ，并使得测量的网络吞吐量低于实际瓶颈链路的带宽。 在主动测量过程中，测量流量可通过详细定义在一定的控制条件下产生。主动 测量是基于i m 的测量，而不是对单程延迟的测量。因为r 1 陌测量更易于实现，而 且不会依赖外部设备去同步两台监视器的时间。另外，有的测量方法是使用全球定 位系统( g p s ) 接收器来同步主机的时间。但这些系统过于昂贵并且难于安装，而且 获得的额外信息也有限，因此并不普及。具体来说，l m 测量是通过类似p i n g 的程 序，每隔一定时间段就要进行一次。该程序对每台被测主机发送i c m p 响应包，然后 等待i c m p 的回应包，记录每个站点的测量延迟。发现或诊断一个站点故障的一个最 基于双抽样的测量流长度分布的算法研究 好方法就是查看r t t 图标的起伏状况，这些起伏表明路由或配置上的变化所引起两 个站点间r t t 的改变情况。另外就是要查看丢包率。如果一个站点的丢包率过高， 那么它可能出现硬件损坏，这种分析是非常基本的。如果要对一个站点的性能有进 一步理解，就要通过比较它同其他站点的连通性来获得。 其次，主动测量至少要多个网络部件以某种形式的参与，例如：使用p i n g 估计 主机a n 主机b 的r t t ，需要主机b 响应i c m pe c h o 请求信息。不同机器之间主动测 量的合作方式有被动合作方式和主动合作方式，如：响应i c m p 请求、匿名f t p 服务 器允许主机和服务器之间实现吞吐量测量，这种合作称为被动合作方式。另一种合 作方式是主动合作方式，需要具体的安排，如果要测量a 至b 之间单向延迟的对称性， 从b 到a 和从a 到b 都需要进行延迟测量，因而b 需要主动参与测量。 网络拓扑结构的变化需要使用主动测量技术，c a i d a 4 】开发的s k i t t e r 动态测量工 具可用于动态发现和绘制全球e t 拓扑【l l 】。另外主动测量技术可以探测网络的具 体问题，如发现许多 n t e m e t 端至端的延迟分布具有重尾特征【1 2 1 。 主动测量是为了监测两指定端点之间的性能而向网络中注人流量的方法，跟踪 和可视化。i n t e m e t 拓扑结构是主动测量最主要的应用。同时主动测量还可以探测网 络的特定现象。 主动测量的优点【1 3 】如下： 1 使用方便，适合端到端的网络性能测量，对于需要关心的内容只需在本地 发送测试包观察网络的响应即可。 2 对用户而言是很安全的，因为该方法不涉及用户的网络信息。 主动测量也存在其缺点，主要包括： 1 主动测量增加了网络潜在负载，尤其是如果该测量未经仔细设计，产生的 流量达不到最小，可能会对网络造成较大影响。 2 主动测量必须向网络中注入附加流量，从而对网络的实际行为造成影响， 掩盖网络行为的本来面目，其测量结果也会造成一定的偏差。 3 主动测量会引起h e i s e n b e r g 效应，即额外的流量可能会干扰网络，并使结果 第1 章绪论 分析产生偏差。 1 2 2 被动测量技术 与主动测量相对应的是被动测量，被动测量需要在网络中的一点收集流量信息， 例如使用路由器或交换机收集数据或用一个独立的设备被动地监测通过被测量网络 链路的流量。被动测量可以完全消除附加流量和h e i s e n b e r g 效应，但有些时候被动 测量却非常困难：例如决定分组所采用的路由。当然如果用户关心的不是完整的网 络路由，而是a s 之间的路由，那么可以被动监测两个对等b g p 之间的流量，因为流 量包含全部的a s 之间的路由信息。被动测量技术的另一个重要问题是现在正在提出 的要求确保隐私和安全的矛盾【5 1 。 网络流量是由大小不一的分组构成的，收集到的数据可以进行各种流量分析， 例如：流量中各种应用的成分、分组的大小分布、分组的相隔到达时间、性能和路 径长度等，这些信息能帮助设计下一代互联网设备和体系结构。有时为了能够从被 动收集的数据中提取某些参数可能需要借助于主动测量。另外，被动测量应该有尽 可能低的丢失率，否则测量的数据将很难进行精确估计。网络运行者最感兴趣的是 流量矩阵：有多少流量从一个网络流向另一个网络，这一信息有助于优化设计决定。 不同的流量粒度矩阵有不同的用处，a s 粒度流量矩阵有助于优化拓扑结构；企业网 或校园网的管理者为了了解各部门之间流量交换情况，可建立系或工作组粒度的流 矩阵；国家粒度的流量矩阵有助于了解各国的网络开放策略和国际商业前景。 与荷载特性相关的一个重要特性是网络分组的大小。分组大小分布和到达时间 的统计数据与设计网络路由交换设备相关，因为交换一个分组的代价有每个分组和 每个字节的成分，因此，有关典型i n t e m e t 荷载的测度允许设计者优化路由器的硬件 和软件体系结构。另一个重要的荷载分析是估计流量中各种协议类型的比重。 被动测量还有许多其它应用，例如：识别、刻划和跟踪网页缓冲和代理的优化 配置；网络体系结构的安全性；拥塞控制算法的有效性；流量增长是因为用户数量 的增加还是每个用户流量的增加；新的技术和协议( 如：组播和i p v 6 ) 的渗透力和 影响等。这些被动测量的应用是i n t e r n e t 流量行为研究的重要内容。被动测量完全取 决于被测网络中目前已有的流量，它的最大优点是在测量期间不影响被测网络的流 量，但会引起测量、分析、存储等资源短缺的问题。 基于双抽样的测量流长度分布的算法研究 被动测量的优点如下： 1 被动测量不必主动发送测量包，在测量时不会增加网络流量，测量的是网 络真正流量，因此被动测量又被称为非侵扰式测量。 2 能够达到对观察点网络行为的详尽理解。 但是被动测量也有其本身所固有的缺点： 1 被动测量实现复杂度高，其准确度依赖于包捕获器的性能。 2 关于隐私和安全的问题：被动测量方式可能要查看网络上的所有数据包， 容易捕获网络中的敏感信息，给用户信息的保密和安全带来威胁。 3 只能获得网络局部数据，无法了解网络整体状况或对网络端到端行为的理 解。被动测量只能固定在网络的某一点收集数据，而不能根据网络的整体 情况来调整收集策略。 4 被动测量在网络排错时非常有价值，但是在仿真网络故障或隔离确切故障 位置时会受到限制。 5 被动测量的前提是协作，否则无法在测量点安装必要的软、硬件设备，测 量范围由此受限。 在对网络进行测量时，采用主动测量还是采用被动测量，是人们直探讨的问 题。当前性能测量趋向于采用主动与被动测量相结合的方法，如利用主动测量确定 网络的整体性能，而当网络发生异常时，则采用被动测量方法确定问题所在位置， 进行故障定位。 1 3 流的概念及流测量技术 1 3 1 流的概念 在i p 技术上，至少在三个领域用到“流”( f l o w ) n 概念【1 4 】：首先，在资源预 约类协议( 例如资源预留协议r s v p ) 中，“流 用来描述网络流量；第二，在交换技 术中，“流”被看作交换的一个单元；最后，“流”是网络测量与分析中的一个重要 概念。 第1 章绪论 作为网络测量与分析中的“流 ，包含以下要素： 1 方向性 首先，“流”可以定义为单向的或双向的。面向连接的t c p 流一般是双向的， 从a 到b 的流量会引起从b 到a 的流量，至少有确认流。现在网上多媒体应用一 般都是单向的，比如实时音频流或视频流通常采用u d p ，不需要对方确认。单向“流” 数据和双向“流”数据都很重要，单向“流”数据对路由问题、网络流量特征的分 析等都非常重要，而双向数据对于协议、应用的使用情况的分析更为重要。由单向 “流”数据得到双向“流 数据总是可能的，所以在网络测量中，一般把流定义为 单向的，也就是说从a 到b 的流和从b 到a 的流被看作两个流。 2 端点特性 定义一个“流”，最重要的是要说明流对应的端点( 流的起点和终点) 和协议使用 情况。对于i p v 4 ，定义一个流一般需要以下几个方面的信息：源地址、宿i p 地 址、源端口号、宿端口号、协议类型、开始时间、结束时间、超时时间等。 3 超时时间 对于网络测量和分析，“流”的概念还需要定义一个超时时间，使恰当的网络 通信量聚合进这个流内。在超时时间内，一直有此流的包通过，则认为这个流是“活 跃 的，如果在超时时间内没有数据包通过，则说明流终止。超时时间是可以自行 设置的，通常设置为6 4 秒。 p 网中的“流 概念可以定义为对一个呼叫或连接的人为逻辑对应【1 5 】。流是流 量的一部分，由起始时间和停止时间定界。与流相关的属性值( 源目的地址、分组 计数、字节计数等) 具有聚合性质，反映了在起始和停止范围发生的事件。由于研 究背景的不同，流有不同的定义。 定义1 ：流是指符合特定的流规范和条件约束的一系列数据包的集合。在本论 文中流是指具有相同的源i p 、宿m 、源端口、宿端口的按结束标识约束的t c p 或 u d p 报文集合( 不考虑协议) 。 定义2 ：抽样流是指在上述定义的流中以某种概率p 进行抽样而得到的报文 集合。在本论文中为叙述方便称定义l 中的流为原始流。 基于双抽样的测量流长度分布的算法研究 定义3 ： 流长度是指流中所包含报文的数量。例如对一个含有5 0 0 个报文的 流，则这个流的长度为5 0 0 。 1 3 2 流测量技术 报文( p a c k e t ) 是网络中最小的传输单元，最初网络行为研究主要集中在数据 报文层次上，但是由于这些研究相对平等地分析每个报文，从而导致对报文间关系 及其更高层次信息分析的缺失。针对流( f l o w ) 的网络行为研究在很多方面弥补了 局限于报文层次研究的不足，对网络“流”的特性进行测量和分析，可以掌握网络某 结点或链路上的诸如运输协议、应用协议、流量强度情况和用户行为特征等的流量 细节。而且采用流概念记录测量结果，通常能够大大节省存储空间。因此流测量成 为网络测量中的一个热点研究方向，特别是流分布的测量。而流测量的方法的主要 问题在于缺乏可测量性。 早在19 9 7 年对m c i 踪迹( 仃a c e ) 的测量显示了超过2 5 0 ，0 0 0 个流存在【8 】o 而现在的高 速网络1 分钟的流量就存在上百万个流。由于网络的高速与流数量的巨大，使得实时 在线的流测量变得非常困难。因此各种流测量技术、流测量算法成为研究热点，并 且取得一系列的研究成果。目前在流测量方法上主要使用了抽样和哈希技术，研究 的重点是流识别和流分布的算法【1 6 】。 1 4 本论文的主要研究内容 本论文的主要研究内容是，综合分析流抽样和报文抽样技术，针对这两种抽样 技术的优缺点，给出了一种新的抽样方法双抽样，即先进行流抽样，得到抽样流f ， 再在抽样流f 的基础上进行报文抽样，得到最终的抽样流g 。然后得出根据抽样流分 布估计原始流长度分布的算法。最后，通过实验验证本文提出的双抽样方法，分析 系统资源消耗，以及对原始流长度估计的精度情况。 1 5 论文的章节安排 根据论文的内容要求，本文的章节安排如下： 第l 章绪论。主要介绍本文的研究背景、主要内容和论文组织结构。 第2 章抽样测量技术。主要介绍报文抽样和流抽样的相关概念，并综述了目 前国内外对这两种抽样技术的研究进展，以及抽样测量技术的应用。 第l 章绪论 第3 章双抽样方法。对报文抽样和流抽样方法进行探讨，在此基础上提出了 双抽样方法，并给出双抽样的实现方法，通过实验表明双抽样方法比单纯的流抽样 和报文抽样大大地节约了系统资源。 第4 章原始流分布的估计。针对报文抽样的估计，根据流被抽空的概率大小 将流分为长流和短流，对于长流用比例法估计；对于短流用e m 算法估计，得到了 由第一阶段流抽样所得抽样流的流长分布。针对流抽样的估计，用比例法在前一阶 段估计得到的抽样流基础上，得到了原始流的流长分布。实验结果表明，由双抽样 方法得到的抽样流能够有效地估计出原始流的分布。 第5 章总结与展望。总结本文的创新点及主要工作，并对未来的工作进行展 塑。 基于双抽样的流长度分布的算法研究 第2 章抽样测量技术 2 。1 抽样测量技术的提出 虽然i n t e m e t 诞生才短短的十几年时间，但是由于各种不同应用的驱动，网络 已经深入到世界的各个角落，成为目前信息交流的最主要平台之一【1 7 j 。i n t e m e t 软件联盟的调查报告显示，1 9 8 1 年8 月联网主机仅有2 1 3 台，而到2 0 0 0 年1 月 互联网上联网主机的数目约为7 2 ，3 9 8 ，0 9 2 台，到了2 0 0 9 年的1 月这个数目就增加 到了6 2 5 ，2 2 6 ，4 5 6 台【l 引，图2 1 为摘录自i s c 主站的不同时段活动主机探测结果的 统计图，数据表明i n t e m e t 活动主机数随着年份的增加呈非线性增长，基本符合 摩尔定律。i n t e m e t 在国内的发展和普及也十分迅速，图2 2 是我国的i p v 4 地址 资源增长情况【i9 1 ，从中国互联网c n n i c 统计数据来看，我国的i p v 4 地址资源保 持快速增长。2 0 0 8 年达到1 8 1 2 7 3 3 4 4 个，存在逐年增长的趋势。 10 0 ，0 0 0 ，0 0 0 可 cc 叮晒 1 口 r n n可 c )口口c )口口c ) c e - c c c c c c - c,r- 妇 叮 叮酊叮叮叮。叮叮 111 )11