（计算机系统结构专业论文）分布式sla监测系统后处理器的研究与实现.pdf

分布式s l a 监测系统后处理器的研究与实现 葛立青，龚俭东南大学 j ；f 户获取网络服务时，可通过s l a 合同来与网络服务提供商协商服务的q 。s 。验证s l a 合同 需要有一个s l a 管理和报告的工具。国家8 6 3 课题：基于抽样测量的分布式s l a 监测系统，就是 个研究该工具的课题，其目标是研制开发网络端至端s l a 监测、分析、报告所需的监测系统 p e r m e 。 本文的工作主要是围绕p e r m e 系统后处理器的设计实现以及设计实现过程中的难点问题展开 的。这些难点问题包括：时戳校准问题、抽样方法的设计问题、数据协同问题、s l a 流的设计问题、 两点s l a 测度的计算问题。 论文第二章讨论了时戳校准算法，从时钟间脉冲相位差的估计、时钟调整点的检测、时钟间偏 移鬣的估计三个方面详细探讨了该算法。第三章讨论了数据协同时硒个方面的问题：如何在p e r m e 系统间安全高效地传送数据；如何减少系统间待传送的数据量。系统间传送数据量的减少有赖丁部 署一个合理的抽样方法，本文依据用户对报文遵从延迟闽值情况的需求，从抽样点的部署、样本容 量的估计、抽样算法的选择等方面设计了种适合p e r m e 系统的抽样方法。第四章研究了s l a 流 的设计问题，将c l a f f 定义流的方法应用到了p e r m e 系统中来，在这一章还讨论了如何计算两点s l a 测度。 本论文在第五章详细介绍了屙处理器的设计与实现。在后处理器的设计中描述了后处理器的体 系结构、功能划分以及数据流图。在后处理器的实现中详细介绍了后处理器的四个子系统：原始数 据处理子系统、数据协同子系统、实时s l a 测度计算子系统、两点s l a 测度计算子系统以及这些 子系统的实现方法。 论文的最后设计了测试方案对后处理器的功能和性能进行了测试，初步证明了后处理器原型 系统的正确有效性。 关键字：q o s ，s l a ，时钟，抽样，流，测度 查堕奎兰婴主兰丝堡苎； a b s 仃a c t r e s e a r c ha n d i m p l e m e n t a t i o no fp o s t p r o c e s s o r i nd i s t r i b u t e ds l a g el i q i n g ，g o n gj i a n m e a s u r e m e n ts y s t e m s o u t h e a s tu n i v e r s i t y w h e ng e t t i n gs e r v i c e sf r o mn e t w o r k ，t h eu s e r sc a nn e g o t i a t ew i t ht h ep r o v i d e ra b o u t o o so ft h es e r v i c et h r o u g hs l ac o n t r a c t t ov a l i d a t et h es l ac o n t r a c t ，t o o l so fm a n a g i n g a n dr e p o r t i n gt h es l aa r en e e d e d an a t i o n a l8 6 3p r o j e c t ：d is t r i b u t e ds l am e a s u r e m e n ts y s t e m b a s e do ns a m p l i n gm e a s u r e m e n ti sp r o p o s e dt or e s e a r c ha n dd e v e l o pas y s t e mc a l l e dp e r m e f o re n d t o e n ds l am e a s u r e m e n t 、a n a l y s i s 、a n dr e p o r t 弛i st h e s i si sm a i n l yc o n c e r n e da b o u td e s i g na n di m p l e m e n t a t i o no ft h ep o s t - p r o c e s s o r i np e r m es y s t e ma n dt h ed i f f i c u l t i e si nt h ep r o c e s sw h i c hi n c l u d ec l o c kc a l i b r a t i n g 、d e s i g n o ft h es a m p l i n gm e t h o d 、c o o p e r a t i o no fd a t a 、d e s i g no fs l af l o w 、c o m p u t a t i o no fs l am e t r i c s t h es e o n dc h a p t e rd i s c u s s e st h ea l g o r i t h mo fc l o c kc a l i b r a t i n gi nd e p t hi nt h r e ea s p e c t s c l o c ks k e we s t i m a t i n g ，c l o c ka d j u s t m e n td e t e c t i n g 。a n dc l o c ko f f s e te s t i m a t i n g t h et h i r d c h a p t e ri sa b o u tt h et w op r o b l e m so fh o wt ot r a n f e rd a t as a f e l ya n de f f e c t i v e l yb e t w e e n p e r m es y s t e m sa n dh o wt od e c r e a s et h ea m o a n to fd a t at ob et r a n f e r e d s i n c ed e c r e a s eo f d a t ad e p e n d so nar e a s o n a b l em e t h o do fs a m p li n ga c c o r d i n gt ot h ed e m a n do fu s e r s ，as a m p li n g m e t h o di sd e s i g n e dt of i tt ot h ep e 删es y s t e m b yc o n s i d e r i n gt h r e ea s p e c t s ：d e p l o y m e n t o ft h es a m p l i n gp o i n t 、e s t i m a t eo fs a m p l es i z e 、c h o i c eo fs a m p l i n ga l g o r i t h m t h ef o u r t h c h a p t e rf o c u s e so nd e s i g no fs l af l o wa d a p t i n gt h ed e f i n i t i o nm e t h o do fc l a f ft ot h ep e p b i e s y s t e m a n dt h ec o m p u t a t i o no ft h es l am e t r i c sa r em e n t i o n e da sw e l l i nt h ef i f t hc h a p t e r ， ad e t a i l e di n t r o d u c t i o no ft h ed e s i g na n dr e a l i z a t i o no ft h es y s t e mi sg i v e n t h ep a p e ri se n d e dw i t had e s i g n e dt e s t i n gs c h e m e ，w h i c hi su s e dt ot e s tt h ef u n c t i o n a n dp e r f o r m a n c eo fp o s t p r o c e s s o r i ti st h ef i r s ts t e pt op r o v et h ec o r r e c t n e s sa n d e f f e c t i v i t yo ft h ep o s t p r o c e s s o r ， k e yw o r d s ：q o s ，s l a ，c l o c k ，s a m p l i n g ，f l o w ，m e t r i c s n 东南大学学位论文独创性声明 妒4 4 7 5 0 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：鱼兰查 日 东南大学学位论文1 吏用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：薹垒圭 导师签名：磊金日期：盘竺哆、了 一! 兰! ! 童 一 第一章引言 本章首先描述了s l a 的基本概念，说明了s l a 测量对s l a 管理的重要性。接着介绍了用于s l a 测量的些基本测量技术并阐述了s l a 测量现存的问题。最后讲述了本论文的项目背景以及研究的 目标和内容。 1 1s i a 的简要介绍 网络管理对网络的发展有很大的影响，已经成为现代信息网络中最重要的功能之。因此过去 i n t e r a c t 管理的理论研究和技术开发也多集中在网络管理。然而，上世纪九十年代中期以来随着 i n t e r n e t 的发展，大型公司、政府机关、科研单位、私营企业和一般消费者逐渐利用基于i n t e r n e c 的 服务作为进行商业活动的基本手段，服务管理和用户管理成为i n t e r n e t 管理的重点， n t e m e t 服务管 理的研究重点也从有效性管理转到可接受的服务质量( q u a i l 可o f s e r v i c e ，q o s ) 的管理。然而，现有 的网络管理方法大都不能提供有效的手段去支持响应时间和可用性等终端用户可以体验到的应用服 务性能参数，因此网络提供商无法实现对现有基础设施以及利用这些基础设施为终端朋户提供的服 务的有效性能的监控。而一个基于i n t e m e t 服务管理的服务级别管理和报告工具可以支持和满足这样 的管理需求。 在耳前的i n t e m e t 上，一个端系统用户使用的完整的服务总是由多个服务提供商提供的软硬件产 品组成，为了给用户提供端至端服务质量保证，就要求各服务提供商都能保证其相应部分的可_ i = f j 性 和性能。用户并不关心提供服务的各个组成部分，只关心q o s 。对q o s 的期望使用户同它们的服务 提供商协商q o s 级别，这通过s l a ( s e r v i c e l e v e la g r e e m e n t s ) 来实现。s l a 是服务提供商弄| j 媚户 之间为指定期望的q o s 级别签订的一个服务期望行为和q o s 参数的合同。s l a 合同中的指标反映 了j _ l j 户和网络供应商本身对网络性能的“最低要求”，并将这种水平以一种合法的书面的形式给出， 它的制定与实施将有助于整个数据业务服务水平的提高和对数据业务质量的规范化，对网络服务供 应商来讲，如果达不到要求就要受到经济上的惩罚；对于用户来讲，在多个提供商的前提卜，可以 自由选择具有高s l a 水平的网络服务供应商。 始近几年来，s l a 在国外用得十分普遍，从i p 骨干网、v p n 到互联网数据中心网络服务供 应商都推出了相应的s l a 。据不完全统计口i 在美国仅1 9 9 7 年一年内就有3 3 的网络服务供应商与 其商业用户签署了s l a 。所有i n t e r n e t 用户中有9 4 认为网络服务供应商提供的s l a 是必不可少的， 8 4 的用户表示愿意为得到网络服务供应商更加良好的服务而额外付费。国内这方面的起步较晚， 但很多网络服务供应商也已经意识到了这个问题。世纪互联网率先在国内引入了s l a 的概念。 s l a 是一种完全不同于传统厢络管理的全新的网络管理方法，它是建立在一种全新的网络管理 思想基础上的。目前s l a 还处于研究阶段，它的研究主要包括以下三方厩： 1 s l a 测度定义，目前还没有s l a 测度的公共标准； 2 ，s l a 测量，主要研究如何精确她测量服务提供商提供给用户的q o s ，s l a 测量是s l a 管理的基础： 3 s l a 的实时监控、分析并将最终的分析报告提供给用户。 对端至端性能进行监测的关键在于统一监测内容，即制定需要铡量的s l a 测度。使网络的性能 状态不仅纵向可比，而且具有横向的可比性，才能形成对网络使用状况的正确评价。但是由目前 的情况看来，这方面的研究还未形成统一的标准。i e t f 【j 1 的i p p m l 4 1 工作纽定义了一系列描述网络 性能的参量建议，如单向延迟铡度( r f c 2 6 7 9 ) ，单向分组丢失测度( r f c2 6 8 0 ) ，往返延迟测度( r f c 2 6 8 1 ) 等，明确了测量对象的参数、单位、定义和方法。并据此在h t t p ：w w w a d v a n c e d o r g c s g i p p m 建立了c u r r e n ts u r v e y o rn e t w o r km a p ，通过发送带有时戳的测试报文对美国3 s 个主节点问的单向 延迟和报文丢失率进行了测量这似乎是唯一的个根据己成形的定义对网络性能进行监测的网络 东南大学 受士学位论文 状况报告。参照国外同类工作的成果，建立统一的目标体系，s l a 测度定义是网络性能监测的首要 前提。 一黾s l a 合同被制定，网络服务供应商就必须按合同要求，分析报告相关s l a 的性能。而计 算这些性能的基本参数必须通过s l a 测量获得，因此。s l a 测量是s l a 分析报告的基础，而s l a 测量是基于网络测量技术的。下面将对几种主流同络溺量技术 5 j 进行简单介绍。 1 2 网络测量技术 早在1 9 9 5 年，当n s f 停止对整个n s f n e t 的资助以后，i n t e r n e t 出现多元发展的趋势，试图完 籀地跟踪和监控i n t e m e t 行为已经不可能了。n s f 投有馨下可以监测不同s p 之间的网络性能问题和 安全事件的框架结构，同时i s p 也没有重视收集或分析他们网络的数据。这样造成今天不但缺乏理 想的测量和分析网络行为工具，同时也缺乏用于分析网络行为变化的测度数据。 尽管网络测量没有得到足够的重视，但学术界对其研究一直没有问断。囡此现在有许多独立的 网络端至端测量方法和相应的工具，这些测量方法主要是在端主机发送主动探测分组进入网络，然 后记录分组返回的延迟。但是这种测量涉及到大量的难以独立建模的参数，同时测量结果的复杂性 使得收集的数据难以比较或标准化。有些研究组织正试图发展技术和体系结构来支持标准化铡撞、 性能评估、选择网络路由的可靠性等，但这些工作进行得很慢，还不能满足用户、研究者和i s p 的 需求， 网络测量可分为主动测量和被动测量两种方式，主动测量是通过主动产生流量直接测量网络的 属性，可以便用直接分析的方法。但是主动测量流量会对被测网络流量的性能产生负面的影响，因 此，主动测量系统开发需要仔细考虑对孵络实际传输流量的影响。被动测量完垒取决于被测网络中 目前已有的流量，它的最大优点是在测量期间不影响被铡嘲络的流量，但会引起测麓、分析、存储 等资源短缺的掏题 t 2 1 主动测量技术 主动意味藿测量过程中产生新的网络流量，主动流量可以引起网络部件的特殊响应( 如： t r a c e r o u t e ) ，也可以用于观测同络的性能( 如：t r e n o ) 。主动铡量给网络增加潜在的荷载负担，特别 是如果没有仔细设计使得该方法产生的流星最小，那么射幻的流量舍扰乱鼹络，髟赡分析翁果，例 如：如果为了测量在l p 网络中瓶颈链路的带宽，定期地向网络发送巨大的叩传输，由此产生的附 加流赞可能会引起h e i 女n b e r g 效应，并使测量的网络吞吐量低于实际的瓶颈链路的带宽。 其次，主动测量至少要多个网络部件以某种形式的参与。如：使用p i n g 估计主祝a 捌圭枕b 的r r ，需要主机b 响应i c i v l pe c h o 请求信息不同机器之间主动测量的合作方式有被动合作和 主动合作。如：响应i c v l p 请求，匿名f 1 甲服务器允许主机和服务器之间实现吞吐量测量，这种合 作称为被动台作。另一种合作方式是主动合作，需要具体的安捧，如果要铡量a 至b 之间单向延迟 的对称性，从b 到a 和从a 到b 都需要进行延迟测量，因而b 需要主动参与测量。 两络拓扑结构的变化需要使用主动测量技术，c a 王d a 扣j 开发的s k i r t e r r n 动态涮量丁具可砧予动态 发现希l 绘制全球i n t e m e t 拓扑l 。另外主动测量技术可以探测网络的具体问题，如发现许多i n t e r n e t 端至端的延迟分布具有重尾特征1 9 1 。 1 2 2 被动测量技术 被动测量需要在网络中的一点收集流量信息，如使用路由器或交换机收集数据或者使用一个独 立的设备被动地监溯通过被测量网络链路的流量。被动测量的优点是可以完全取消附加流黉和 h e i r , e n l r g 绶应，但有些测度被动铡重相当困难：如决定分翅所采用肋龉由，当然如果用户关心的 不是完整的网络路由，而是a s 之间的路由，郧么可以被动监测两个对等b g p 之间的流蹙，因为流 2 一一釜二童! ! 童 量包含全部的a s 之间的路由信息。被动技术的另一个重要的问题是与现在正在提出的要求确保隐 私和安全矛盾。 网络流量是由大小不一的分组构成的，收集到的数据可以进行各种流量分析，如：流量中各种 应用的成分、分组的大小分布、分组的相隔到达时间、性能和路径长度等。这些能帮助设计下一代 互联网设备和体系结构。网络运行者最感兴趣的是流量矩阵：有多少流量献一个厢络流句另一个网 络这个信息能有助于优化设计决定。不同的流量粒度矩阵有不同的用处，a s 粒度流量矩阵有助于 优化拓扑结构；企韭网或校园网的管理者为了解各部门之问流量交换的情况，可以建立系或 j 作组 粒度的流矩阵；国家粒度的流量矩阵有助于了解各国的网络开放策略和国际商业前景，例如f q 指出 美国是世界i n t e m g t 流量主要中转国，7 1 的其它国家之间的国际流量经过美国。 与荷载特性相关的一个重要特性是网络分组的大小。分组大小分布和到达时间的统计数据同设 计网络路由交换设备相关，因为交换一个分组的代价有每个分组和每个字二骨的成分，因此，有关于 典型 n t e r n e t 荷载的测度允许设计者优化路由器的硬件和软件体系结构。另一个重要的荷载分析是估 计流量中各种协议类型的比重。 被动测量还有许多其它的应用，如：识别、刻划和跟踪网页缓冲和代理的优化配置；网络体系 结构的安全性；拥塞控制算法的有效性：流量增长是由于用户数量的增加还是每个用户流量的增加： 流行协议和应用使用的变化：新的技术和协议( 如：组播和1 p v 6 ) 的渗透力和影响等等。上面这些 被动测量的应用是i n t e r n e t 流量行为研究的重要内容。 有时为了能够从被动收集的数据中提取某些参数可熊需要借助予主动测量。另外，被动测援是 不应该丢失分组的，否则分析的数据将不精确。但随着流量速率的增加。保证不丢失数据变得儿乎 不可能，因此抽样网络流量测量技术成为解决这一矛盾的非常有效的方法和技术。 1 2 3 抽样测量技术 网络被动测量流盈主要用于两络分析、规划和计费等但由于弼络带宽的高速发壤，同时计算 机测量、存储、分析资源的限制，难以直接测量全部的网络流量。一种解决方案是抽样测量部分流 量。从统计角度获得对流量总体行为的认识。 本论文的第三章将详细地描述抽样测量技术， 1 3p e r m e 系统 基于端至端s l a 浏4 度测量的重要性和目前测量平台的问题，c e r n e t 华东北网络中心承接了国 家8 酊计划课题：基于抽样测量的分布式服务级男f f 绮定( s l g ) 监襄f 系统“，其目标是研究高速p 网络环境中基于抽样测量的端至端s l a 监测系统的理论与技术，构造分布式网络端至端s l a 监测 集成体系结构，研制开发i n t e m e t 环境下的网络端至端s l a 监涮、分析、报告所需的监测系统一 p e r m e p e r m e 系统与以往的主动测量和被动测量的区别在于：以往的螭至端测蹙技术大多是采 用主动测量二 具或传统的p i n g 工具进行测量而被动测量一般是基于单个铡量点为核心，不同的被 动测量点之间不存在协同关系p e r m e 系统使埒描榉和堑算法。满足高速网络测量对性能的要求。 1 3 系统概述 p e r i e 系统主要包含二个关键部分：( 1 ) 高速i p 网络流量抽样测量系统：( 2 ) 端至端s l a 分析 报告系统。 ( 1 ) 高速i p 网络抽样测量系统 此系统具有面向高速i p 网络的流量抽样监听与分析设备，该设备运行于高速网络边界， 具有分缀俘获、时戳、过滤、抽样事件鉴别、产生分缨j d 、事件数据生成、捌量结果发送等 功能目标系统将具有遣应高速网络的吞吐量可根据抽样精度和网簟 流量调整抽样比率的能 ， 变塑查兰堡主兰垡堡塞 力。具有1 0 0 m b p s 快速以太网接口和1 0 0 0 ) 4 b p s 速率的光纤接口。 ( 2 ) 端至端s l a 分析报告系统 在高速流量的抽样技术、体系结构模型的研究、s l a 信息分析、报告技术、s l a 信息查询 技术等各项关键技术的支撑下，研制开发端至端s l a 分析报告系统，该系统基于通用计算机平 台，使用由各个高速i p 网络抽样测量系统所提供的原始抽样数据，并基于各个单项技术进行网 络端至端s l a 分析，监测网络s l a 的许可水平，根据s l a 所确定的服务标准发现网络中出现 的违约事件，提供网络可用性、基础设施鲁棒性及分析预计用户将来的需求和发展趋势等端至 端s l a 的分析报告。 在端至端s l a 分析报告系统中，支持8 个s l a 测度的测量它们分别是：吞吐量、响应 时间、失序数、重传数、昂小单向延迟、中值单向延迟、单向延迟抖动、丢包率。f 面是这些 测度的定义： 1 响应时间：测量点测量到请求报文的时间和测量点收到该请求报文应答的时间之间的筹。 2 吞吐量：在某个测量点测量到两个i p 之间传输的t c p 字节数，量纲为字节秒。 3 ，重传率：在测量时间范围内，i p i 和i p 2 之间，一个t c p 链接内，出现t c p 报头序号利前 面出现该链接内序号相同，则认为收到的报文是重传报文( 可以不用考虑反转的现象) ，当 然还包含收到相同的s y n 报文、a c k 报文和f i n 报文。总之，只要在一个t c p 链接内收到 相同的报文则认为是重传。测量时间粒度范围内，从i p i 到i p 2 的所有t c p 报文中，重传 的报文和总t c p 报文数之比为i p i 到i p 2 的重传率。 4 ，失序：在测量时间粒度内i p i 和i p 2 之间，一个t c p 链接内，收到所有i p l 的t c p 报文 中，后面报文的序号小于前面一个报文的序号( 需要考虑反转的问题) ，则认为失序值为i ， 小于2 个前面报文的认为失序值为2 ，以此类推。 5 最小单向延迟：在测量时间粒度内，两个i p 地址之间，所有抽样报文单向延迟的最小值。 6 中值单向延迟：在测量时间粒度内，两个l p 地址之间，所有抽样报文单向延迟的中间值。 7 单向延迟抖动：在测量时间粒度内，两个l p 地址之间，所有抽样报文单向延迟变化的均值。 g 丢包率：在测量时间粒度内，两个l p 地址之间，所有抽样报文中丢失的报文数和抽样报文 数的百分比 1 。3 2 系统总体结构 p e r m e 系统的总体结构可采用自顶向下的描述方式加以说明。分别是p e r m e 系统之间的分布 关系，p e r m e 系统内部的数据流图以及f e r m e 系统内部功能的分布结构 1 p e r m e 系统之间的分布关系 每一高速i p 网络的p e r m e 系统独立存在，成为自治系统，在全局上不存在中央处理系统和中央 控制系统。不同的高速i p 网络的p f j 瑚e 系统之间采用相互授权的方式为符合其政策的其它高速 i p 网络的p e r m e 系统提供所器要的协同信息但是端系统能够维护其和不同端系统之间的协作关系， 能够发现与其协作端系统是否正常工作的线索。因此p e p 啦e 系统的分布依赖于网络拓扑，其示意图 为图卜1 ： 第一章引言 图1 1 高速i p 网络的p e r m e 系统之间的分布关系图 图中的p e r m e 是高速i p 网络的网络s l a 监测系统目前的暂用名，该单词是p e r f o r m a n c e m e a s u r e m e n t 的缩写。 从圈1 一l 可知p e r m e 系统通常以中继子鄹方式存在，但是这些中继子网一般都处于网络的关键 节点上，例如各个地区的网络中心等等。每一p e r m e 系统可以选择和其它p e r m e 系统协作或不协作 并且可以定义所需要的协作关系。 2 p e r m e 系统内部的数据流图 图1 2 为系统内部详细的数据流图，是从测量器到s l a 分析报告系统的数据传输和分析流，而 没有包括反向的控制流。 、f1i 鼓据传辅f i敢韬读取l ，。、 阖l l i ，r 饥 调度i il s l a 组流 1i 流量统计l 管理 ( ) | 协同 j j 事实库i i 广 i ，、l 一 lh 耐 l测度计算 ) i 立廑一 配置库 l 三= j l， 3 i 结论库l l 查询 圈1 2p e r m e 系统内部的数据流图 5 i 东南大学硕士学位论文 2 p e r m e 系统内功能的分布结构 在p e r m e 系统内部主要有两种类型的系统存在，种是测量器，另一种是s l a 分析报告系统。 测量器负责获取具体数据，并且进行简单的过滤和抽样处理，其过滤、抽样需求和提供的数据内容 由服务系统决定。s l a 分析报告系统收集测量器提供的数据，以此进行相关的分析，并且根据需要 决定是否需要和其它p e p , m e 系统进行协同或进行特殊的响应动作。s l a 分析报告系统还能够提供用 户进行信息查询的能力以及管理员对各种具体功能进行管理的能力。 图卜3 是一个p e r m e 系统内部的主要功能结构图，该功能结构图是一个逻辑结构模型，在具体实 现时需要考虑性能问题，如果单一主机的分析处理系统不能够负担全部通信、分析、数据存储、查 询、管理等功能的性能要求。可以考虑使用分布的体系，但是在逻辑上仍是统一的。 p e r m e 系统中还有个重要的功能是操作控制功能，控制功能的控制能力在于各个功能模块的 配置文件，并且能够选择执行的功能，如哪些分析功能需要运行，也包括分析功能使用的知识库等 数据库。 s l a 分析报告系统在实现上可以划分为两个功能独立的实体由不同的小组实施开发二 作。我负 责的起后处理器的设计与实现因此后处理器实现时涉及到的问题是本论文主要研究的内容。下一 常就将重点介绍后处理器 1 4p e r m e 后处理器 圈1 - 3p e r m e 系统内部的功能结构圈 从上= 臂可知后处理器需能根据s l a 报告的要求，依据s l a 配置库中的知识，对本域的事实库 以及从其他域协同来的事实库中的事实进行关联与综合，实现端至端s l a 测度值的计算、统计。 另外此予系统从不同时间粒度对结论库进行摘要分析。最终将分析结果按照s l a 报告的要求分 f l i t 类的记入各个结论库中。下面将具体描述后处理器的需求以及实现时面临的问题。 1 4 1 后处理器的需求 后处理器是s l a 分析报告系统的一部分，它必须完成以下的要求。 1 )可以协同远端p e r m e 系统中的数据 6 2 ) 统计不同时间粒度的s l a 报告：实时、每小时、每臼、每月；并可由系统定时功能定时启 ? j _ 。i ? 。一 动。 3 ) 不同的应用具有不同的测度( 由s l a 配置库配置) ，用户可以根据应用的实际情况配置需 要测量的测度指标：并且系统只计算用户配置的这些测度 4 ) s l a 结论库中的内容可以提供给用户查询 5 ) 根据s l a 合同中对报文延迟规定的闽值，计算每个用户需要测量的s l a 延迟测度的遵从情 况。 综合这些需求可知：后处理器主要的任务是计算实时两点s l a 测度值，粗时间粒度统计s l a 测 度以及计算s l a 测度对用户规定的阈值的递从情况。为实现后处理器的这些功能，必须考虑如何解 决以下的一些技术难点。 1 ，4 2 后处理器实现难点 后处理器在设计实现时有三个主要的难点问题需要仔细研究 1 )对于测量报文单向延迟这样对时间极其敏感的s l a 测度而言，不同p e r m e 系统之间时间 的协同就显得十分重要。网络上不同主机之间时间的协同也直是学术界研究的热点。时 钟同步的难点在于利用g p s 进行时间同步价格较为昂贵，而n t p 是一种依赖网络本身的 时间同步机制，它的精确性部分依赖于n t p 协议两端之间通信所经过的1 n t e r n e t 路径 属性( 特别是时延) ，而单向时延恰恰是系统中需要测量的一个端至端s l a 测度。那么本 论文需要重点研究用什么算法来解决时钟问题? 2 )为了满足用户对端至端s l a 测度计算结果实时查询的需要，不同域之问数据的协同也需实 时发生。因为这些数据的传送都是经过互联网的，所以协同时必须研究如何合理选择数据 以使在互联网传送的数据量最小。 3 )后处理系统的设计和实现中除了多域间的协同以及两点s l a 铡度计算这些难点外，还需仔 细规划每个p e r m e 系统的数据库表和索引以及对数据库中某些表格( 其内的数据不断的 实时增加) 中数据的存放时间进行有效地管理。另外由于后处理中涉及到了很多的数据库 操作，因此为了提高系统的效率，某些程序就由存储过程来编写，那么确定哪些部分由存 储过程来实现哪些部分由c 语言来编写也是后处理设计的一个难点。 为解决后处理器实现时需要考虑的这三个难点。本论文从三个方面进行了研究。这三个方面的 具体内容在下一节中进行了详细描述。 1 5 论文的研究内容 本论文研究的主要内容是在p e r m e 的体系结构和全局控制方式下，完成后处理嚣的设计与实 现以及设计实现中涉及到的技术难点。具体研究内容分为以下几方面： ( 1 ) 时戳校准和数据协同 在端至端s l a 测度中，某些测度( 如：单向延迟、丢包率等) 需要数据发送方和接收方的测 量器都记录下同一报文的报头信息。当具体计算这些测度时，就需要将某一方测量器记录f 的报 头信息协同到另一方。鉴于p e r m e 系统之间是互相自治的本论文需详细研究每个p e r m e 系统 须从其他系统协同哪些数据以及何时和怎么协同这些数据，并且还需研究如何协同数据才能最小 程度的影响实际网络流量( 运用抽样技术) 。 多域之阃另外一个需要研究的内容是时钟，在测量单向延迟等s l a 测度时，域之间时钟的不 一致会导致严重的测量错误，因此如何进行多域之间时间的同步即将时戳校准到适合延迟计算的 程度一个研究的重点也是难点。 两点s l a 测度的计算与统计 在计算s l a 测度时，如果需要用到两个测量点的数据，则这些测度就被称之为两点s l a 测度， ， 东南大学顼士学位论文 在本课题中包括单向延迟、单向延迟抖动、和丢包率等。这些测度的计算和统计由后处理系统来 完成。在实际中，用户所关心的s l a 测度不是某单个报文的s l a 测度，雨是某段时间内s l a 测 度的统计值。因此本论文需研究如何定义流以在流的角度来计算两点s l a 测度值以及如何在流内 以一系列单个报文s l a 测度的统计值来表征流的s l a 测度。 ( 3 ) 后处理器的设计与实现 后处理器的主要功能是进行多域之间的数据协同，两点s l a 测度的生成以及s l a 测度的综台 和s l a 测度遵从性的计算等功能。后处理器设计与实现的研究包括该子系统的功能模块划分、模 块接口的定义以及相关数据结构的设计。 针对以上研究内容本论文剩余部分的组织结构如下： 第二章介绍了时钟问题的基本内容。并比较了几种经典的解决时钟问题的算法，然后根据 p e r m e 系统的实际特点提出了个改进的线性规划法来解决时钟问题 第三章讨论了p e p d v i e 系统闻进行数据协同时如何进行数据传送以及如何利用抽样技术减少待 传输的数据量。 第四章讨论了如何在p e p m e 系统中定义流以及如何计算两点s l a 测度- 笫五章描述了后处理器的模块和数据流的设计以及系统的实现细节 第六章简单地描述系统的测试环境、测试方案以及测试的结果和对测试结果的分析。 第七章是总结和展望。 8 第二章时戳校准算法 第二章时戳校准算法 在研究网络延迟测度时，网络延迟的计算将涉及到两个或多个主机时钟，显然，这些时钟的同 步将对测量的准确性产生决定性的影响。在两点的情况下，报文发送方和接收方在该报文发送和到 达的瞬间用时戳记录下相应的时刻。若两台主机的时钟是精确同步的，则两个时戳的差就是这个报 文经历的端到端网路延迟：若两台主机的时钟记录的时间有偏移但他们之间没有脉冲相位差，则两 个时戳的差就不仅仅包括端到端网络延迟也包括两个时钟的相对偏移量；若仅仅计算单向延迟就 不能将相对偏移量从测量的值中提取出来，除非知道真正的网络延迟，而这正是需要测量的量。如 果时钟之间存在相对脉冲相位羞，则不仅仅无法直接测量出网络延迟，而且随着时间的流逝，两个 时钟之间的偏移量也会逐渐的增加或减少( 这取决于报文发送方的时钟运行比接收方时钟运行的快 还是慢) 。+ f 图2 ，1 就是一个延迟随时问变化的例子。 0 8 0 7 懿： 蚓0 4 岸0 3 斟0 2 0 1 o 01 0 0 02 0 0 03 0 0 04 0 0 05 0 0 06 0 0 0 时间( 秒) 图2 一i1 0 0 分钟的延迟变化图 基于上面的分析在计算网络延迟时，必须首先排除时钟不同步带来的影响。解决时钟问题有 两种方案： 1 同步两个主机的物理时钟 当前属于这种方案的方法有网络时钟协议( n t p ) 1 1 2 1 , 全球定位系统( g p s ) ，和无线电信号， 每种解决方案都有优点和缺点。 n t p 在火规模网络中精度存在问题，连续的n t p 分组也许经历不同的队列延迟造成相对不精确 的时钟同步。g p s 为实现时问同步问题提供一个高精度的解决方案，g p s 信号能在全球任何一个地 方收到，且晟大分辨精度能达到l o o n s 。但是在从g p s 信号转为内核的时钟脉冲时会丢失精度，其 延迟范围可以控制在微秒范围之内，这种精度对于网络流量测量是足够了g p s 测量的缺点是g p s 接受器需要直接对准卫星同时，价格较为昂贵。另一种可能的方案是使用无线信号进行时钟同步， 提供的精度能达到微秒级。这种方案的缺点是不能保证任何地方都能正确接受无线信号，另外，空 气也能对信号产生干扰。 2 除去时钟不同步对待测数据时戳的影响，而不改变实际的物理时钟。 鉴于上一种方案的缺点，某些学者提出了不改变实际的物理时钟，仅除去时钟不同步对研究数 据时戳的影响的方法。p a x s o n l 9 9 7 年在论文【1 ”中提出来一种利用两个方向的单向延迟来准确校准时 戳的算法，并且说明了即使利用第一种方案同步了物理时钟，也仍然需要一种算法来校准时戳。 m o o n 也在q 中提出了一种利用一个方向的单向延迟来估计时钟之间脉冲相位差的线性回归算法。 但这些算法在具体应用时存在一些问题，譬如p a x s o n 方法在估计时钟调整时需要两个方向的单向延 9 东南大学硕士学位论文 本章将在前人工作的基础上，提出一种适合本系统的时戳校准算法，它的研究问题包括三个方 面： 1 时钟之间脉冲相位差的估计 2 时钟调整的检测 3 时钟之问偏穆量的估计 f 面将首先介绍一些背景知识，包括对钟术语、时钟函数的表示以及其他的一些基本概念，然 后用个简单的数学模型描述时钟之间脉冲相位差估计的问题和几种脉冲相位差估计的算法。在此 基础上提出了一个估计脉冲相位差和检测时钟调整的线性规划方法并说明了如何估计时钟之间的偏 移量。最后用实验的方法，验证了算法的正确性和适用性。 2 1 背景知识 2 1 1 时钟术语 除某些特定的点外，时钟c 可以表示为一个两阶可导的光滑函数： c ：r j 胄 此函数满足以下条件： 一阶可导：c ( ，) d c ( t ) d t ，二阶可导：c ”o ) = d 2 c ( , ) d t 2 在，gp c 胄，这里l 科是有限的。 虽然对于一个计算机上的实际时钟而言，它时间改变的最小单元是分辨率，并且总是大t - 0 ， 这样时钟函数似乎更应该被描述成一个阶梯函数，阶梯的高度就是时钟的分辨率，但如果认为实际 时钟报告的时间是一个连续函数在某个特定时刻的值，则上述模型可以成立。通过这种假定，就可 以回避实际时钟离散值的影响。 一个理想的时钟在任何时候都报告真实正确的时间，并且运行在一个固定的变化率上。若e 代 表理想的时钟；则它是一个确定的函数：e = ，并且只= 声 定义了时钟的时闻模型后，就可以方便的描述时钟的一些行为特征了，这里用”中定义的命名 系统来描述时钟特征。令c 。和c 代表两个不同时钟的时钟函数，则 分辨率( r e s o l h t l o r ) ： 一个时钟的分辨率指的是时钟时间改变的最小单元，分辨率给出了时钟误差较低的界限。( 注意： 时钟有细微的分辨宰但却有可能褶当不准确) 分辨翠的定义是相对于时钟报告的时间而不是真实的时间。 偏移量( o f f s e t ) ： 时钟报告的时间和真实时间的差；则时钟q 的偏移量为( e ( r ) 一f ) 。时钟c 。相对于时钟g 的 偏移量为e ( f ) 一e l ( t ) 频率( f r e q u e n c y ) ： 时钟变化的速率，时钟c 。在t 时刻的频率为c 。( f ) 。 脉冲相位差( s k e w ) ： 一个特定时钟的频率和理想时钟频率的差。在t 时刻时钟c 。相对于时钟g 的脉冲相位著为 ( c 。( ，) 一c 。( f ) ) 。 时钟漂移( d r i f t ) ： 时钟( 口的漂移董为c ”。o ) 在t 时刻时钟c o 相对于时钟g 的时钟漂移量为c ”。( ，) 一。( f ) 。 1 0 这里讨论的时钟不是理想时钟，而是现实中的时钟。以下将两个现实时钟的相对时钟偏移和相对脉 冲相位差简称为偏移量和脉冲相位差。 为了方便，下面将通过比较两个时钟频率之间的比例来代替相对脉冲相位差。则相应的定义为： 时钟比例( c l o c kr a t i o ) ： 一个时钟和真实时钟的频率之间的比例。则时钟c o 的时钟比例为c 。( f ) 门= c 。( ，) 。时钟c ， 相对丁时钟g 的时钟比例c 。( f ) c ( f ) 若时钟c 。和时钟g 有固定的频率，并且a 和占分别是时钟g 相对于时钟c 。的时钟比例和脉冲相伉 筹即d = c 。c 。，占= c 一c 。通过数学运算可知这两个变量之间的关系为 占= c 一c 。= a c 。一c 。= ( 口一1 ) c 。( 2 1 ) 2 。1 2 时钟区间的确定 本：霄介绍如何用特定时钟描述一个时钟区间。 令( f 。，t 2 ，c 口) 表示在t l 时刻和t 2 时刻( 根据真实时间) 之间根据时钟c 。来确定的时钟区间。 网为一个时钟为一个分段的连续函数。因此可以定义时间区间为： ( r l ，f 2 ，c o ) ；i c 。西 ( 2 2 ) = j j ，c 。d t + 2 c u d t + + c l 。d t 这里只n ( f l ，t 2 ) = 扫l ，p 2 ，p 。j 并且 ，i p t p 2 p 。 l ，j j l ( a 一】) i 随着i 线性增长，因此d ，逐渐增大。这就是为什么可从图2 - 1 中观察到延迟逐渐增大的趋 势。最后，从公式( 2 7 ) 。可以根据求出的a 和互来估计