（计算机系统结构专业论文）大规模高速网络数据分析系统的设计与实现.pdf

摘要 摘要 大规模高速网络数据分析系统( i p t a s ) 的设计与实现 高亚东丁伟 东南大学计算机科学与工程学院 随着计算机网络技术的快速发展，用户数量和应用的种类、规模以近乎指数规律增长。 在这种急剧膨胀的驱使下，网络规模不断扩大，网络流量不断增长。网络结构和网络行为越 来越复杂网络运行也越来越容易出现技术性问题。目前，研究人员主要通过网络测量，获 取网络中各类应用的流量差异，以及影响网络性能和服务质量的因素，从中探寻这一庞大非 线性复杂系统所表现的未知行为，进而为技术和管理策略的改进提供参考。被动测量由于对 网络运行无干扰，测量数据能最真实地反映网络行为，所以被广泛应用于网络测量工作。但 是，对于主干速率在1 g b p s 以上的大规模高速网络，海量数据的采集、整理、分析处理等都 是被动测量需要解决的难题 本论文的研究内容和相关工作，着重于大规模高速网络被动测量这一背景下，与测量和 网络行为分析密切相关的海量数据采集后的归并整理和分析处理这两大难点。论文将详细探 讨多链路高速主干信道报文数据的归并整理策略研究和实现一个适应大规模高速网络海量 数据处理需求的i p t r a c e 数据分析系统i p t r a c e a n a l y s i ss y s t e m ( i p t a s ) ，并利用i p t a s 对采集自c e k n e t 江苏省网边界信道的t r a c e 进行分析 论文首先研究在c e r n e t 江苏省网边界信道上采集的并行报文数据的归并整理策略。 论文介绍了2 0 0 5 年1 1 月1 0 日利用w a t c h e r l 】系统采集的数据特征，并针对数据中的存在 问题，详细分析了产生原因。为了将数据整理成可在研究中使用的t r a c e ，论文设计了时戳 乱序报文的排序算法和并行报文数据的多路归并算法在此基础上设计了两个数据整理工 具，并利用它们在计算机集群系统上完成了致据的排序和归并。论文还研究了w a t c h e r l 1 系统内采集器之间的时钟相对漂移对t r a c e 中报文时戳的影响。 然后，论文设计和实现i p t r a c e 数据分析系统( i p l r a s ) 论文分析了系统的需求提出 i p t a s 应该具有支持良好扩展性的体系结构，以支持在使用系统的过程中只经过简易步骤就 可以扩展系统的数据分析功能。论文根据系统7 个方面的需求概要设计了i p t a s 应该具有 的功能对i p t a s 中的关键问题进行了详细研究并给出具体的解决方案。在解决了关键 问题之后，论文依据功能设计和关键问题研究中设计的体系结构、模型与过程，实现了 i p t a s ，得到一个基于网络的、支持多用户的i p t r a c e 数据分析系统 最后，论文对i p t a s 进行测试。测试表明，符合规范的数据分析算法能够经过简易的 过程成功扩展到系统框架之下。并成功进行数据分析，相关功能达到了预期目标论文利用 i p t a s 分析一个t r a c e ，并根据分析结果总结了c e r n e t 报文在时间和空间上的一些分布特 性。 【关键词】i p t r a c e , 报文，报头，归并整理策略，数据分析算法 东南大学硕士学位论文 a b s t r a c t t h ed e s i g na n d m p l e m e n t a t i o no f d a t a a n a l y s i ss y s t e mf u rl a r g e - s c a l en e t w o r k g a oy a d o n g , d i n gw e i s c h o o lo f c o m p u t e rs c i e n c ea n de n g i n e e r i n g , s o u t h e a s tu n i v e r s i t y w i t lt h er a p i dd e v e l o p m e n to f n e t w o r kt e c h n o l o g y , t h ea m o u n to fu s e r $ a n dt h et y p e so f a p p l i c a t i o n s ，h a sb e e ng r o w i n ga l m o s te x p o n e n t i a l l y d r i v e nb ys u c ha ne x p a n s i o n , n e t w o r ks c a l e a n dl r d f n cg r o w s ，n e t w o r ks t r u c t u r ea n db e h a v i o rb e c o m e sm o r ec o m p l i c a t e d , a n dt h e r ea r c i n c r e a s i n gt e c h n i c a lp r o b l e m si nt h er u n n i n go ft h en e t w o r k c u r r e n t l y , t h er e s e a r c h e r ss t u d yt h e b - a l t i cd i f f e r e n c eo fv a r i o u sa p p l i c a t i o n s , a n da n a l y z et h ei m p a c t so nn e t w o r kp e r f o r m a n c ea n d q u a l i t yo fs e r v i c e , m a i n l yt h r o u g hn e t w o r km e a s u r i n g , t oe x p l o r et h eu n k n o w nb e h a v i o r s p e r f o r m e db yt h i sh u g ec o m p l e xn o n l i n e a rs y s i e m d u et ot h eo p e r a t i o no ft h en e t w o r kw i t h o u t i n t e r f e r e n c e ，p a s s i v em e a s u r e m e n tc a ng e tt h em e a s u r e m e n td a t aw h i c hm o s tt r u l yr e f l e c tn e t w o r k b e h a v i o r , s oi ti sw i d e l yu s e di nt h en e t w o r km e a s u r e m e n t h o w e v o r , i nt h eh i g h - s p e e dn e t w o r k , m a s s i v ed a t ac o l l e c t i o n , c o i l a t i o n , a n da n a l y s i s , a r et h ed i 茄c u l tp r o b l e m s , w h i c hn e e dt ob e r e s o l v e db yp a s s i v em e a s u f e m e n t u n d e rt h eb a c k g r o u n do f p a s s i v em e u r e m e n tf o rl a r g e - s c a l eh i g h - s p e e dn e t v o r k , t h i sp a p e r f o c u s e do ot h e c o l l a t i o na n da n a l y s i so ft h em a s s i v ed a t a , w h i c hw a sc l o s e l yr e l a t e dt ot h e m e a s u r e m e n ta n db e h a v i o ra n a l y s i s i tw o u l dd e a lw i t ht h es t r a t e g yo fd a t ac o l l a t i o n , a n dt h e d e s i g na n di m p l e m e n t a t i o no ft h ei pt r a c ea n a l y s i ss y s t e m ( i p t a s ) a n di tw o u l da n a l y z ea t r a c ev i ai p t a s f i r s t , i ts t u d i e dt h es t r a t e g yo fp r o c e s s i n gt h ep a r a l l e lp a c k e td a t ac o l l e c t e df r o mj i e n g s u p r o v i n c eb o r d e r c h a n n e lo f c e r n e t i td i s c u s s e d t h e f e a t u r e s o f t h ed a t ac a p t u r e db y w a c t h o r l 1 s y s t e m , a n da n a l y z e dt h er e a s o n so ft h ep r o b l e m se 菇s t e di nt h ed a t a i td e s i g n e dt w oa l g o r i t h m s w i t h0 ( n ) t i m ec o m p l e x i t y , a n du s e dt h e mt os o r tt h ed i s o r d e rp a c k e t sa n dm e r g et h ep a r a l l e ld a t a i nah i g hp e r f o r m a n c ec o m p u t e rc l u s t e r i ta l s od i s c u s s e dt h ec l o c ke r r o rc a u s e db yc l o c ks k e w a m o n gt h es e v e r a lc o l l e c t o rm a c h i n e s t h e n , i td e s i g n e da , u ti m p l e m e n t e di p t a s i ta n a l y z e dt h er e q u i r e m e n t so fi p t a s ，a n dp u t f o r w a r dt h a ti p t a ss h o u l dh a v ea na r c h n c c t u r ew h i c hs u p p o r t e ds c a l a b i l i t y , i no r d e rt oe x p a n dt h e a n a l y s i sf u n c t i o n so fi p t a so n l yt h r o u g has i m p l ea p p r o a c h a c c o r d i n gt ot h es e v e ns p e c i f i c r e q u i r e m e n t s ，i td e s i g n e dr e l a t e df u n c t i o n sa n dp r o c e d u r e s ，a n dc o n d u c t e dad e t a i l e ds t o d ya n d g a v es p e c i f i cs o l u t i o n st ot h ek e yp r o b l e m s i na c e n r d a n e ew i t ht h e s es t r u c t u r e s , m o d e l sa n d p r o c e d u r e s , i td e s i g n e dt h ec o n t r o ls t r u c t u r e so f i p t a s ，a n dc o m p l e t e dt h ei m p l e m e n t a t i o n f i n a l l y , t h ep a p e rt e s t e di p t a s ，a n dd i ds o m ea n a l y s i sw o r ko i lat r a c ec o l l e c t e df i o m j i a n g s up r o v i n c eb o r d e rc h a n n e lo f c e r n e t , u s i n gi p t a s k e yw o r d s i pt r a c e ，p a c k e t ，p a c k e th e a d e r , s t r a t e g yo fp r o c e s s i n gd a t a , d a t aa n a l y s i s a l g o r i t h m 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或 证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意 研究生签名： 南至，聋日期：至! ! z ：! 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查 阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：l 为善，敦导师签名：研究生签名：l 白善，孔导师签名：日期：趔! z ：生 第l 章绪论 1 1 引言 第1 章绪论 2 0 世纪6 0 年代末，在美国国防部远景规划局( d a r p a ) 的资助下，科技人员开始进行 计算机之间的互连研究，并利用研究的成果组建了a r p a n e t ，它标志着计算机网络的诞生。 此后的十多年里，网络在结构和协议方面，得到了深入研究。1 9 8 0 年，当a r p a n e t 上的 机器转为使用新的t c p f l p 协议时，i n t e r a c t 正式诞生。2 0 多年来，互联网得到了长足发展， 尤其是1 9 9 0 年以后，其发展日新月异，甚至可以用爆炸来形容。如今，互联网己经渗透到 社会的各个方面，在各个领域起着重要作用。网络带宽不断增加，性能不断提高，用户数量 和网络应用的种类、规模甚至以近乎指数规律增长。由于互联网从构建之初就缺乏统一规划， 加之尚未建立类似传统电话网中应用的数学规划模型，网络在应用和用户人群急剧膨胀的驱 使下，不断扩大规模，各种网络服务层出不穷网络流量不断增长，网络行为越来越复杂， 网络运行也越来越容易出现技术性问题 正如我们需要用辩证的现点看待任何事物，网络对社会发展、人们的生活产生了正反两 方面的深远影响。在互联网构建之初。人们不会意识到它将给人们的生活带来如此大的便利， 也不会联想到它的背后隐藏着如此多的形形色色的问题。近年来，研究人员越来越重视网络 急剧扩张对其在可扩展、安全、服务质量和创新性应用等方面产生的影响。于是开始重点研 究网络运行的客观规律，以期从中发现各种问题的根源以及解决方法然而，到目前为止对 网络运行客观规律的研究还缺乏系统的概念和方法，研究人员只能通过对网络进行测量，探 讨这一庞大非线性复杂系统所表现的未知行为在网络测量的基础上系统分析网络行为， 获取网络中各种类型应用的流量差异，以及影响网络性能和服务质量的因素，有助于更好地 了解各种网络应用和服务的实际工作状况，为技术和管理策略的改进提供参考从而有利于 提升网络性能，更好地为用户提供服务。 网络测量可追溯到a r p a n e t 建立时，它伴随着网络技术的发展，相关理论和技术研究也 取得了很大成就。目前，互联网的标准化组织i e t f 下属的i p p m 、i p f i x 、p s a m p 等工作 纽都在进行有关网络测量的标准制定工作。其中1 p p m 工作组负责组织制定有关互联网数据 传输质量、性能和可靠性的指标川；i p f i x 工作组主要研究i p 设备输出数据流信息的相关标 准 2 1 ；p s a m p 工作组则主要研究通过统计学和其它方法进行报文采样的相关标准化工作 3 1 这些标准的制定使网络测量的理论和方法更加系统化，能够更好地对开展网络测量提供指 导。网络测量也产生了多种分类标准，其中使用最广泛的是按测量方式分为主动测量和被动 测量，二者主要区别在于测量过程中是否向被测网络注入测试流量1 4 j j 。其中，被动测量通 过流量镜像获取技术，监听特定信道上的流量井进行分析。较主动测量而言，它的优点在于 不会产生额外的测试流量，对网络运行没有干扰，能最真实地观测到网络的行为。但是，对 于主干速率在1 g b p s 以上的大规模高速网络，海量数据的采集、整理、分析处理等都是被动 测量需要解决的难题。 在大规模高速网络被动测量这一宏观背景下，本论文的研究内容和相关工作，着重于网 络测量数据的整理和分析系统的研究。论文将详细探讨多链路主干信道的海量报文数据的归 并整理策略，设计和实现一个大规模高速网络环境下的i pt r a c e 数据分析系统i pt r a c e a n a l y s i ss y s t e m ( i p l r a s ) 。最后以从中国教育网( c e r n e t ) 下属的一个省网边界信道上 采集的t r a c e 为对象，在归并整理的基础上，利用i p t a s 完成对该t r a c e 的一些分析工作。 需要特别说明的是，文中提到的t r a c e 都是指从真实网络采集的i p t r a c e 。 东南大学硕士学位论文 1 2 论文研究背景 1 2 1 测量数据管理 网络测量数据是计算机网络技术研究的基本要素之一，但随着测量的持续开展，测量数 据的规模迅速增长，对应的统计分析工具( 软件) 和分析结果的数量、规模也随之增长，研 究工作开始遭遇如何有效管理测量数据的难题。一方面存放在存储介质中的测量数据，会 因为可能发生的硬件损坏或更新，以及数据迁移，而存在管理困难。另一方面对每一个测 量数据集合进行有效跟踪则是更加复杂的问题在测量数据集的使用过程中，对于发现的 每个问题和每个有价值的分析结果，应如何保存和表述1 6 j 。国际上一些测量机构针对测量数 据的管理问题进行了相关研究，主要侧重于测量数据的跟踪、反馈和提高可用性。相关工作 主要有： l可扩展网络测量知识库( s i m r ) ：m a r ka l l m a n 等人在一篇名为。as c a l a b l es y s t e m f o r s h a r i n g i n t e m e t m e a s u r e m e n t s ”的论文中，描述了一种用于管理网络测量数据和相关元 数据的可扩展互联网测量知识库。相关元数据包括用户信息，测量工具、数据采集平台和部 署位置、数据特征，实验内容、与其它数据集合的关系等。建立该知识库系统的目的是协助 研究人员收集大量种类繁多的测量数据促进研究团体内部的数据共享，并允许研究人员利 用共享的分析工具和测量数据验证他人的研究成果。从本质来说，可扩展网络测量知识库是 一种提供集中式共享存储空间的管理信息系统。 2 i s t - m o m e 数据库：m o m e i s 项目也做了很多类似工作。该项目建立i s t - m o v e 数 据库，目的是为欧盟的信息社会计划在i p 网络监控和测量方面提供协同i s t - m o v e 数据库 通过统一接口提供符合公共标准格式的数据，包括报文、流、路由信息、q o s 数据等。某些 数据还附有分析结果包括平均流量、报文大小、到达速率、到达间隔时间等，并且以直方 图等图形方式显示了部分分析结果1 9 j 。此外，它也提供一些网络监控和测量工具与s i m r 相比，i s t - m o m e 数据库更注重共享数据的格式标准化 3 c a i d a 网络测量数据目录( 1 m d c ) ：c a i d a 1 在测量数据管理方面进行了更深入的 研究他们在2 0 0 1 年向美国国家科学基金会提出建立一个注册和注释测量数据的公共系统， 该系统能够与c a i d a 的测量数据以及其它网络测量数据良好协作目的是为研究人员提供 测量数据分布和相关研究工作的检索服务n j 。2 0 0 2 年c a i d a 正式开始建立i m d c ( i n t e m e t m e a s u r e m e n td a t a c a t a l o g ) i m d c 在设计过程中借鉴了s i m r 和i s t - m o m e 数据库，井将与 i s t - m o m e 数据库和其它网络测量知识库的综合和交互，作为其将来工作的重点之一与 s i m r 和i s t - m o m e 数据库相比i m d c 不提供测量数据的集中共享也不将测量数据转化为 特定的标准格式，而是试图对分布在整个互联网范围内的测量数据进行有效跟踪，并着重于 对测量数据的描述 上述3 种系统不管是提供集中式数据共享还是分布式数据编录，它们在本质上都是关于 测量数据的管理信息系统，没有提供数据管理和共享之外的其它功能 1 2 2 海量数据处理 随着网络流量不断增长，网络测量尤其是全流量被动测量必须面对海量数据。对海量数 据的处理是一项艰巨复杂的任务，原因有以下3 方面： 1 数据量庞大：在全流量被动测量中，数据量已达到t b 级，数据的存储和管理已经 有较大难度，对其处理则更加困难。 2 软硬件要求高：海量数据的处理过程，需占用大量系统资源。一般情况下，如果处 理的数据量达到r b 级，要考虑使用小型机或者运算能力相当的高性能计算设施，如高性能 2 第1 章绪论 计算机集群系统。这些硬件设施需要较高投入， 些专用系统资源管理软件，合理分配系统资源， 一般科研机构不具备条件。此外，还需要一 优化数据处理过程，提高数据处理效率。 3 需要优秀的数据处理方法和技巧：要求建立良好的数据处理模型，降低算法的时间 复杂度，编写正确的程序代码，在细节上减少系统开销对程序效率的影响。在软硬件条件相 差不大的情况下，方法和技巧是决定数据处理效率的最主要因素。 目前在海量数据处理中，应用较多的技术有数据库、数据仓库、数据挖掘、数据抽样、 并行处理技术等。这些技术在网络测量数据的处理中，也得到了不同程度的应用。网络测量 领域的一些机构和个人将其设计的数据处理算法和工具以开放源码的方式公开发布，研究 人员可以免费获取并应用于研究工作之中。但这些开源工具一般不具备通用性，在测量数据 处理过程中可以借鉴其思想，针对待处理海量数据的特点，设计相应的算法和工具。此外， 一些企业，如f l u t e 公司，也推出了用于网络测量的软件产品，可在功能上予以参考。 1 2 3 原始t r a c e 的来源和特征 本文研究主要涉及的t r a c e 来源于c e r n e t 江苏省网( 即j s e r n l 玎) 边界路由器和 c e r n e t 主干路由器之间的高速信道它通过一个被动网络报文采集系统w a t e h e r l 1 以分 光方式获得。w a t h e r l 1 由c e r n e t 华东( 北) 地区网络中心设计，它能对组成c e r n e t 江苏省网边界信道的3 对共6 根光纤，进行报文实时采集而且，如果继续增加光纤以扩展 信道只要安装相应的光纤分光器，增加部署采集器和存储器，即可扩展系统。系统的结构 如图1 1 所示： 图1 - 1w a t c h e r l 1 体系结构图 教据库 上述结构中，对应每一条双向物理链路，在其两根光纤上分别安装光纤分光器，井设置 两台服务器分别充当采集器和存储器。采集器直接从光纤接口上捕获全部流量，并截取每个 i p 报文的头部，打上时戳，然后将报头通过千兆链路批量发往存储器，由存储器写入存储 介质。w a t h e r l 1 的所有采集器利用n t p ( n e t w o r kt i m ep r o t o c 0 1 ) 与一台专用的时钟服务 器定时同步( 同步间隔：6 4 秒) ，而这台时钟服务器通过g p s ( g l o b a lp o s i t i o ns y s t e m ) 与 东南大学硕士学位论文 标准时间进行同步。 w a t e h e r l i 系统采集的数据存在两方面缺陷：一是由于被采集信道采用多链路结构，从 3 对光纤采集的数据并行分布在3 台存储器上，不是完整的t r a c e ；二是w a t h e r l 1 系统中每 台采集器负责采集一对光纤，两个方向的报文在打上时戳后混合通过高速信道发往后台存储 器的过程中，会发生时戳乱序。因此，必须对每份并行数据内部的报文排序，然后进行流量 归并，使数据成为时戳有序的规范致的报文流，才能作为t r a c e 用于研究工作。 1 3 论文研究目标和主要内容 1 3 1 论文研究目标 论文研究的主要目标是设计和实现一个适应大规模高速网络海量数据处理需求的i p t r a c e 数据分析系统，为网络行为学研究提供数据分析工具。结合相关工作，论文研究可细 分为以下两方面具体目标： 1 针对2 0 0 5 年1 1 月l o 日在c e r n e t 江苏省网边界采集的报文数据分析其中存在 的问题和原因，提出解决问题的思路，并完成数据归并，使之成为一个可以使用的t r a c e 2 设计并实现一个面向高速网络i pt r a c e 的数据分析系统，其结构具有可扩展性。它 提供良好的管理功能，支持数据分析功能扩展，能够完成各种基本的数据分析工作，并为更 高级和个性化的数据分析工作提供基础性支持 1 3 2 论文研究内容 围绕上述研究目标，本论文研究内容在以下几方面展开： 1 数据整理策略：结合信道特点和数据采集系统的结构，说明2 0 0 5 年1 1 月1 0 日在 c e r n e t 江苏省网边界采集的报文数据的特征。找出其中存在问题的原因针对每一个问 题，提出解决方案，并实施数据整理，使其成为能在研究中使用的完整t r a c 2 数据分析系统的体系结构设计：系统的体系结构应该具有良好的可扩展性，以便在 开发完成后能根据研究工作的需要不断导入新的数据分析算法，从而实现功能扩展。同时 系统的体系结构应该使系统具有较好的工作效率。因此，要在整体上综合考虑系统可扩展性 和系统效率。 3 数据格式的描述：数据分析系统中涉及众多数据结构，为方便管理，并统一规范， 可利用一种标准的描述语言对数据格式进行直观描述，并且易于被应用程序理解。因此，要 研究数据的描述方式。 4 数据分析算法：根据已有的和可以预见的数据分析需求，研究数据分析系统将要支 持的数据分析功能涉及的代表性分析算法 5 数据分析系统的实现：基于实现环境探讨系统的具体实现方案，并通过对系统的 测试验证系统结构模型和系统功能。 6 对c e r n e tt r a c e 的分析：以论文研究第1 项内容整理所得的t r a c e 为分析对象， 利用数据分析系统，通过对t r a c e 的分析，总结c e r n e t 报文在时间和空间上的分布特性。 该部分具体的数据分析工作，也是对数据分析系统的进一步测试。 4 第1 章绪论 1 4 论文课题来源 论文研究依托于中国教育和科研计算机网( c e r n e t ) 华东( 北) 地区网络中心承担的国 家重点基础研究发展规划( 9 7 3 ) 课题“网络动态行为和传输控制理论”( 课题编号： 2 0 0 3 c b 3 1 4 8 0 4 ) 。该课题是国家重点基础研究项目。新一代互联网体系结构理论研究”的重 要组成部分。课题围绕“网络动态行为及其可控性”这一科学问题，对该问题的研究将解决 未知的网络行为与确定的传输控制目标之间的矛盾。下文中如提及“9 7 3 课题”。均指该课 题。 目前，该9 7 3 课题组已经开展的研究工作主要有流行为研究，流测度研究、流分类技术、 应用层协议识别、流识别算法研究、报文和流的抽样算法研究、t c p 连接完整性研究，以及 数据净化等。这些研究都需要使用从网络上采集的i pt r a c e ，进行各种实验。实验中存在 很多相同或者类似的工作，因此针对9 7 3 课题组涉及的数据分析处理中的通用需求，设计一 个具有可扩展性的i pt r a c e 数据分析系统，用于在以后的研究工作中不断集成各种可以复 用的数据分析算法，具有现实意义 本论文课题正基于此，论文研究工作中设计和实现的数据分析系统，将为9 7 3 网络行为 学课题提供一个基础性的保障设施。 1 5 本论文的组织结构 论文全文分为7 章。其中第l 章是绪论，介绍论文的研究背景、研究目标、研究内容和 课题来源论文第2 章研究数据归并整理策略井进行实际的数据整理，这是论文研究工作 的第一部分论文从第3 章开始进入论文研究的主体部分，在这一章中进行i p l a s 需求分 析和功能设计论文第4 章研究i p t a s 中的关键问题，并给出解决方案。论文第5 章完成 i p t a s 的实现论文第6 章测试i p t a s ，并利用i p t a s 对c e r n e t 报文在时间和空间上的 分布特性进行一些尝试性的分析工作论文最后进行总结，并展望未来工作 东南大学硕士学位论文 第2 章数据归并整理策略 w a t c h e r l 1 系统采集的数据并行分布在多台存储器上，特定用户之间的通信报文由于路 由器的负载均衡而随机分布在多份数据之中，而且每份数据都存在报文时戳乱序的缺陷。因 此必须将数据归并整理成完整的t r a c e ，才能在研究中使用。本章将分析2 0 0 5 年1 1 月l o 日 采集的原始数据的特征，并针对时戳乱序和数据分布的实际情况设计报文的排序算法和归 并算法以两个算法为核心设计数据整理工具，并利用东南大学计算机学院的高性能计算机 集群，对原始数据进行归并整理。 2 1 数据特征说明 2 1 1 数据格式 2 0 0 5 年1 1 月1 0 日w a t c h e r l 1 系统采集了全天2 4 小时流经江苏省网边界的所有i p 报 文，并截取和保存报文头部的6 0 字节。当i p 报文长度不足6 0 字节时采集器用零补齐 同时，采集器根据处理报文时的系统时间，为报文添加一个8 字节的时戳最终写入存储器 的报头记录格式如图2 1 所示： 醅字节 图2 - 1 报头记录格式 8 字节 印字节 其中前8 字节的时戳结构为： d 扪j c tt i m e v a l ( 1 0 n gt v _ s e c ； 。s e c o n d s + l o n gt v _ u s e c ； 1 m i c r o s e c o n d s f ) ； 该结构的两个成员变量用于存储相对于纪元( e p o c h l ) 的时间差值。其中t v c 表示秒 数，t ? u s e c 表示微秒数。该结构对时间的表示精度可达微秒级，但采集器为每个报文添加 的时戳精度是毫秒级，因此t vu s e c 的几个低位比特对报文时戳精度没有实际意义。考虑到 后续研究中经常要区分报文进出扛苏省网的具体方向，所以有必要为每个报文添加方向标 记。采集器利用t vu s 最低4 位标记报文的方向和流经的光纤号，其中前3 个比特存储光 纤号，最后一个比特是方向标记：0 为入，l 为出。 g n u l i n u x 和p o s i x 系统上纪元为1 9 7 0 - 0 1 - 0 10 0 ：0 0 ：0 0u t c 6 第2 章数据归并整理策略 时戳之后的6 0 字节中，最前面是网络层报头即i p 报头，其长度通常是2 0 字节如 果有i p 选项，则会更长。i p 报头的实际长度由i h l ( 1 p h e a d e r l e n g t h ) 域川指明。紧接着 i p 报头，6 0 字节中剩余的空间是i p 报文负载区的前端部分。如果i p 报头的p r o t o c o l 域指明 的协议类型是一种传输层协议，那么i p 负载区的最前端是传输层报头。其中，u d p 报头长 度为8 字节”“，t c p 报头实际长度则由其d a t ao f f s e t 域指明通常为2 0 字节。截取的 6 0 字节报头覆盖网络层报头和传输层报头，而多截取的字节，其中包括一些应用层信息， 是为进行更高层研究预留的数据支持。 2 1 2 数据分布 对象数据总量约为2 4 3 t b ( 按1 t b = 1 0 2 4 g b 换算，依此类推) 。由于w a t c h e d 1 系统中 设置了3 套采集储存子系统，采集的报头数据分布在3 台存储器上，每台存储器中的数据只 是整个采集时段全部流量的3 个并行部分之一信道两端的路由器采用负载均衡策略分流流 量，3 台存储器上的数据量大致相当。 在存储器内部报头数据存储在一系列固定大小的二进制文件中每个文件的大小为 2 0 0 m b 其中存储了约3 0 8 4 万个报头，时戳跨越数秒。文件以其中存储的第一个报头记录 的时戳作为文件名。在文件名上体现数据的前后关系，保证在后续处理中程序能够根据文件 名自动确定数据的先后顺序 2 1 3 时戳乱序及原因 观察一台存储器上的数据，发现报文时戳在总体上呈现递增趋势，这和w a t h e r l 1 系统 实时采集实时添加时戳的设计思想吻合。但在一个较小时间粒度内观察，发现连续存储在二 进制文件中的报头记录在时戳上存在逆向波动某个报头记录的时戳比它前一个报头记录的 时戳，在时间轴上更接近e p o c h ，这不符合实际而且可以判定这一现象是在从报文被捕获 直到报头被写入存储器这一过程中，由某个环节的问题造成的。后续研究中，经常要以当前 处理的报文的时戳作为参考时间，重现当日某一时刻的流量时戳乱序必然会影响测量和分 析精度，甚至带来严重问题。 仔细分析，发现原因在于采集器的实现机制。每台采集器负责采集一条双向物理链路的 两条光纤，将两个方向的报头混合在一起发送给存储器。图2 - 2 显示了采集器的内部结构。 采集器 图2 - 2 采集器内部结构简图 7 东南大学硕士学位论文 从两根光纤通过分光器获取的流量镜像被传送到采集器的两个光纤接口采集器将打上 时戳后的报头暂存在两个报头缓冲区中。虽然统计显示进出江苏省网的报文数量大体平衡， 但在较小的时间粒度内，流量在两个方向上并不对称，甚至差异较大。正是由于这种小时间 粒度内流量的不对称性，采集器的两个光纤接口接收数据的速率存在快慢差别于是造成填 写两个报头缓冲区的速率差异。而以太传输模块为了及时腾出报头缓冲区空间以容纳后续报 头，它总是尽快将两个缓冲区中的报头取出，封装成以太帧发往存储器。时戳乱序就发生在 交叉地从两个报头缓冲区读取报头并封装以太帧这一环节。 如果采集器对从两个报头缓冲区中取出的报头进行时戳检查并按先后顺序拼装以太 帧。似乎可以解决这一问题，但事实不尽如此。因为在双向流量差异较大的情况下，一个方 向的报头缓冲区会被迅速填满而施加的双向时戳检查机制，会阻碍以太传输模块迅速将填 写速率快的缓冲区腾空，缓冲区一旦填满就不能容纳而只能丢弃后续报头，造成高丢包率 要从根本上解决时戳乱序问题，需要采集器采用更加优化的实现机制和部署方案 2 2 数据整理工作的时间复杂性 数据整理包括两项工作：一是根据时戳对3 份并行数据分别排序；二是进行流量归并， 将3 份并行数据归并成完整的t r a c e 。设报文总数为h ，则3 份并行数据的平均规模是n 3 。 对一份数据排序的平均时间开销五“3 包括：输入开销露”、排序开销7 = 、输出开销 7 = 其中输入、输出开销是读写磁盘的m o 开销，它们与磁盘寻道时间、数据在磁盘上 的分布等多种不确定因素有关无法用与数据规模n 3 相关的函数表示，对开销大小也只能 定性分析捧序开销是c p u 运算开销，c p u 单次运算所需时间可根据其工作频率确定，而 运算次数与将采用的捧序算法有关，可表示成关于数据规模n 3 的函数厂加3 ) ，所以排序 开销可通过定量计算得出设c p u 单次运算所需时间为c ，对一份数据排序的平均时间开 销可表示成式2 1 ： 正= 磁”+ t ：3 + c f ( n 3 ) ( 2 1 ) 3 份数据总排序时间开销可表示成式2 2 ： 五“= 3 ( 巧”+ 瓦：3 ) + 3 c x “n 3 ) ( 2 2 ) 同理，流量归并的时间开销可表示成式2 3 ： 巧= 3 x 瑶”+ 咒+ c 。g ( n ) ( 2 3 ) 其中，g ( ) 表示对总规模为7 7 的数据进行归并所需的运算次数。 根据式2 2 和式2 3 ，在进行数据整理时，应该在两方面降低时间开销：一是设计高效 的数据整理算法，尽量降低算法的时间复杂度；二是采用优化的磁盘读写策略，降低i 0 开 销。 2 3 数据整理算法和工具 2 3 1p a c k e t s o r t 算法 实验观察表明。数据中相邻报头记录的时戳差异不超过2 秒，在算法中维持长度为4 秒的时间窗口，对落在时间窗口内的报头进行排序，即可处理报文时戳乱序问题。由于排序 的依据是时戳，可使用散列方法设计报文排序算法p a c k e ts o r t 。 在算法中，维护变量c u r r e n t _ s e c 用于记录根据报文时戳定义的时间( 相对于e p o c h 的秒数) ，这是对数据采集时的时间值重现。开设含有8 1 0 6 单元的环形表，每个单元包含 g 第2 章数据归并整理策略 一个l i n k 指针和一个l a s t 指针。其中一半用作当前的散列表。与4 秒时间窗e l 相对应，每一 个表项对应一微秒。随着算法的执行，散列表在环形表中不断向前移动。散列函数内部使用 线性映射方法时戳减去c u r r e n t _ s e c 所得差值即为散列地址。具有相同时戳的报头根据散 列函数给出的散列地址，在对应表项的l i n k 指针后串接成单向链表。为了使算法的时间复杂 度控制在线性时问内，l a s t 指针总是指向单向链表的最后一个结点，新报头直接根据这个指 针插入到链表尾部。图2 - 3 显示了p a c k e ts o r t 算法中使用的散列表结构。t a i li n d e x 和 h e a d _ i n d e x 是两个主指针，分别指向4 秒钟时间窗e l 的第一个微秒和晟后一个微秒分别对 应的表项，它们在散列表中的位置，每次移动都以1 0 。的倍数沿环形表向前推进。 1 w li n d c xh e a r lj n d e x 图2 - 3 散列表结构 p a c k e t _ s o r t 算法的概要流程如图2 - 4 所示： 9 东南大学硕士学位论文 上述算法将时戳的i x , u c 成员变量的所有比特都纳入散列值计算，但实际上时戳只达 到毫秒级精度，而且t vl i s c c 的最低4 位被用来保存光纤编号和方向信息。这样做并投有引 起新的误差，因为算法将保证报头在实际采集精度( 毫秒级) 上有序。带来的唯一影响是时 截除t vu s e c 的最低4 位外其它比特全部相同的若干报头，会根据晟低4 位的取值组合聚类， 其中具有相同光纤号和方向信息的报头将在排序过程中被连续写入磁盘。因为没有引起新的 误差，所以这种影响至少不是负面的。 2 3 2 报文排序器 以p a c k e ts o r t 算法为核心设计一个报文排序器。由于p a c k e ts o r t 算法的时间复杂度已 被控制在线性时间内，所以在实现排序器时，主要考虑降低读写磁盘的i ，o 开销对排序效率 的影响。为提高效率，程序采用多线程结构：将从磁盘读入报头的功能独立为一个报头输入 线程；将向磁盘写入有序报头的功能独立为一个报头输出线程；对报头捧序的过程则在一个 独立的报头排序线程中实现。此外，通过批量读写的方式减少磁盘i o 次数。 报文排序器的结构如图2 - 5 所示。报头输入线程和报头排序线程之间通过报头缓冲区进 行数据交换。p a c k e ts o r t 算法中。将r r a ni n d e x , t a i li n d e x + n * 1o o ) 范围内的报头从散列结 构中取出”这一步骤不在报头j | 序线程中真正实现，只是简单予以标记具体工作则由报 头输出线程完成。报头排序线程和报头输出线程直接使用散列结构进行数据交换，减少了一 处数据交换缓冲区，因而节省了一次数据拷贝的开销，这在客观上也使效率有所提高。 报头输出线程采用的存储策略和w a t c h e d 1 小的二进制文件中每个文件的大小为2 0 0 m b ， 件名，在文件名上体现数据