（计算机应用技术专业论文）网格环境下网络带宽实时监控与预报算法研究.pdf

摘要 在使用计算网格共享地理上分布的丰富的异构资源求解大规模问题过程中，使用 的资源( 包括网络带宽) 动态变化，计算网格获取实时、准确的动态性能信息( 包括 网格资源性能信息和网格应用程序性能信息) ，对于负载管理系统从动态变化的资源池 中选择合适的资源是非常重要的。目前针对网络带宽测量的工具较多，但多数为按需 测量且测量多为单一测量，使用的方法也较简单，系统开销或对网络带宽的影响较大， 没有考虑具体应用的实际情况，没有考虑不同通信协议在传输上的差异，也没有考虑 在不同通信协议层上的性能差异，因而造成了测量结果的准确性低、适应性差，为准 确判断和预测网络带宽状况增加了难度。对手预报方法，可以应用于网络带宽预测的 模型较多，但普遍存在适用性不强的问题，不能很好地解决预测准确性与预测实时性 和预测产生的系统额外开销的矛盾，对在网格环境下能适应不同应用类型，准确反映 网络变化的预测模型选择或建立，还没有确立通用的模型或行之有效的方法。 本课题的研究针对网络带宽的准确测量、测量数据的正确分析、准确反映变化情 况的预报模型选择问题提出针对网络带宽的实时监测和预报方法基于等比包序列 的实时有效带宽测量算法，该算法可以使用较少的网络流量和c p u 运算时间得到较准 确的测量结果，对于网格环境下带宽的快速准确测量具有一定意义；在带宽准确测量 的基础上，采用了种改进的预报算法，n w s 改进算法动态指数平滑算法，获取 网格计算节点和网格a g e n t 节点间网络的可用带宽和预期的变化情况，在动态网格环 境下为调度决策系统提供有关网络性能的调度依据，使得网格资源的利用更加合理， 保证网络数据传输的实时性，改进应用程序的执行性能。经过大量的实验数据分析， 该带宽测量和预报算法能够很好的适应网格环境下的实时性要求，具有一定的实用价 值。 关键词：网格带宽测量预报信息服务 a b s t r a c t i nt h ep r o c e s so fu s i n gc o m p u t a t i o n a lg r i da n ds u f f i c i e n ts h a r e di s o m e r o u s r e s o u r c e st h a ta r ed i s t r i b u t e dg e o g r a p h i c a l l yt os o l v em a s s i v ep r o b l e m s ，t h e r e s o u r c e s ( i n c l u d i n gg r i db a n d w i d t h ) i n v o l v e ds h o u l db ed y n a m i ca n dt h e c o m p u t a t i o n a lg r i ds h o u l db e a b l et og e tt h er e a l - t i m ea n de x a c td y n a m i c c a p a b i t i 够i n f o r m a t i o n ( i n c l u d i n gt h eg r i di n f o r m a t i o no fr e s o u r c e sc a p a b i l i t y a n da p p l i c a t i o nc a p a b i l i t y ) i no r d e rt h a tt h el o a dm a n a g i n gs y s t e mc a ns e l e c t s u i t a b l er e s o u r c e sf r o md y n a m i cr e s o u r c ep 0 0 1 t h em e a s u r i n gt o o l st h a ta r e u s e df o rg r i db a n d w i d t ha r en u m e r o u s h o w e v e r , m o s to ft h e ma r es i m p l e ， s i n g l e f u n c t i o n a l a n dm e a s u r e d a c c o r d i n g t o n e e d b e s i d e s ，t h es y s t e m s p e n d i n gi sl a r g ea n dt h ei n f l u e n c ef o rn e t w o r kb a n d w i d t hi ss e v e r ew i t h o u t c o n s i d e r i n g t h er e a l a p p l i c a t i o n ，t h e d i f f e r e n c ei n t r a n s m i t t i n g v a r i o u s c o m m u n i c a t i o np r o t o c o l s ，a n dt h ed i f f e r e n c eo ft h ec a p a b i l i t yb e t w e e nl a y e r so f c o m m u n i c d t i o np r o t o c o l s a sar e s u l t ，t h em e a s u r i n gr e s u l t sa r ei n a c c u r a t ea n d i n f l e x i b l es ot h a tj u d g i n ga n dp r e d i c t i n gn e t w o r kb a n d w i d t hb e c o m e sm o r e d i f f i c u l t t h em e t h o d st h a tc a l lb eu s e di np r e d i c t i n gn e t w o r kb a n d w i d t ha r eo f g r e a ta m o u n t ，b u tm o s to ft h e ma r eo fl o wa p p l i c a b i l i t ys ot h a tn o n eo ft h e m c a na d j u s tt h ev e r a c i t ya n dt h er e a l - t i m eo fp r e d i c t i o na n de x t r as p e n d i n go ft h e s y s t e mc a u s e db yp r e d i c t i o n t h e r ei sn os u c hau n i v e r s a lm o d e lo ra ne f f i c i e n t m e t h o dt h a tc a nr e f l e c tt h ec h a n g e so fn e t w o r ke x a c t l ya n dc a r lb eu s e da l l r o u n di ng r i d t h i ss t u d yp r o p o s e dam e t h o do fr e a lt i m em e t e r a g ea n dp r e d i c t i o no f n e t w o r kb a n d w i d t hc o n s i d e r i n gt h em e a s u r eo f n e t w o r kb a n d w i d t h ，t h ea n a l y s i s o fm e a s u r i n gd a t aa n dt h es e l e c t i o no fp r e d i c t i n gm o d e l st h a tr e f l e c tc h a n g e s t h em e t h o dp r o p o s e di sar e a lt i m em e a s u r i n gw a yo fb a n d w i d t ht h a ta r eb a s e d o nt h eq u e u eo fg e o m e t r i cp r o p o r t i o np a c k a g e b u d g e t a r ye s t i m a t ei sam e t h o d t h a tc a ng e te x a c tr e s u l tb yu s i n gl e s sn e t w o r kr u n o f fa n dc a l c u l a t i n gt i m eo f c p u i ti so fg r e a ti m p o r t a n c ef o rm e a s u r i n gt h eb a n d w i d t hq u i c k l ya n de x a c t l y u n d e rg r i d m e a s u r i n gt h eb a n d w i d t hc o r r e c t l y , t h es t u d ya d o p t e dt h ed y n a m i c e x p o n e n t i a ls m o o t h i n ga l g o r i t h m ，a na d v a n c e dp r e d i c t i n gm e t h o do fn w s ，t o c a l c u l a t et h eu s e a b l eb a n d w i d t ho fn e t w o r kb e t w e e nt h en o d eo f g r i da n dg r i d a g e n tn o d e s ，a n dt og e tt ok n o wt h ee x p e c t e dc h a n g e s t h em e t h o dc a na l s o p r o v i d e t h ei n f o r m a t i o nc o n c e r n i n gt h e c a p a b i l i t yo ft h en e t w o r k t ot h e a t t e m p e r a t i o nd e c i s i o n - m a k i n gs y s t e mu n d e rd y n a m i cg r i de n v i r o n m e n t i nt h a t c a s e ，t h eg r i dr e s o u r c e sc a l lb eu s e dm o r er a t i o n a l ，a n dt h er e a lt i m e t r a n s m i s s i o no ft h en e t w o r kd a t ac a nb e g u a r a n t e e d t h e r e f o r e ，t h e a d m i n i s t r a t i v ec a p a b i l i t yo fa p p l i c a t i o ni si m p r o v e d a n a l y z i n gt h es u b s t a n t i v e d a t a ，t h es t u d yp o i n t e do u tt h em e t h o dp r o p o s e dc a np r o v i d ear e a lt i m e m e a s u r ea n dp r e d i c t i o no f t h eb a n d w i d t hu n d e rg r i de n v i r o n m e n t 。 k e y w o r d s ： g r i d ；b a n d w i d t hm e a s u r e ；p r e d i c t i o n ；i n f o r m a t i o ns e r v i c e 长春- e 业人学硕十学位论文 原创性说明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 日 目 ，算-、 u存年 列盯 孙 签者 作 ： 敝 醐 长春t 业大学硕士学位论文 第一章绪论 1 1 课题研究的背景和意义 课题的题目是“网格环境下网络带宽实时监控与预报算法研究”，它是国家自然科 学基金项目( 基金编号；6 0 4 7 3 0 9 9 ) “网格应用程序执行性能的实时监控和预报”的子 课题。 在使用计算网格共享地理上分布的丰富的异构资源求解大规模问题过程中，使用 的资源( 包括网络带宽) 动态变化，计算网格获取实时、准确的动态性能信息( 包括 网格资源性能信息和网格应用程序性能信息) ，对于负载管理系统从动态变化的资源池 中选择合适的资源是非常重要的。目前针对网络带宽测量的工具较多，但多数为按需 测量且测量多为单一测量，使用的方法也较简单，系统开销或对网络带宽的影响较大， 没有考虑具体应用的实际情况，没有考虑不同通信协议在传输上的差异，也没有考虑 在不同通信协议层上的性能差异，因而造成了测量结果的准确性低、适应性差，为准 确判断和预测网络带宽状况增加了难度。对于预报方法，可以应用于网络带宽预测的 模型较多，但普遍存在适用性不强的问题，不能很好地解决预测准确性与预测实时性 和预测产生的系统额外开销的矛盾，对在网格环境下能适应不同应用类型，准确反映 网络变化的预测模型选择或建立，还没有确立通用的模型或行之有效的方法。 1 2 课题研究的主要内容 本课题的研究将集中在： 1 针对网络带宽的准确测量、测量数据的正确分析、准确反映变化情况的预报模 型选择问题提出针对网络带宽的实时监测和预报方法； 2 获取网格计算节点和网格a g e n t 节点间网络的可用带宽和预期的变化情况，在 动态网格环境下为调度决策系统提供有关网络性能的调度依据，使得网格资源的利用 更加合理，保证网络数据传输的实时性，改进应用程序的执行性能。 本课题主要研究以下内容： 1 网络带宽的实时监控； 2 监测数据的准确分析； 3 网络带宽预报模型的选择或建立。 1 3 国内外研究现状 在网格环境下网络可用带宽是负载管理系统从动态变化的资源池中选择合适的资 源的重要参数之一。目前在该领域的研究主要集中在低开销的监控方法、准确的数据 分析和预测模型建立方面。监控是进一步管理网格应用的基础。计算网格需要实时准 长春工业大学硕上学位论文 确的动态性能信息，在高性能分布式计算系统中，自动化监控和管理分布式计算的各 个组件是十分重要的。许多监控系统的一个公共特点是预报的使用，预报可以是显式 或者隐式。显式方法尝试直接预测任务执行时的性能；隐式方法简单地假设在每个可 能的主机上任务的性能是可以排序的，根据主机上与任务无关的指标进行排序，然后 从排序中选择一个主机。 国外在该领域有一些已经应用的工具，代表性的有： 1 网络气候服务n w s 1 1 是一个分布式系统，它能够周期性地监控和动态广播不同 网络和计算资源的性能，支持面向资源的性能在线预报。它控制一组分布式性能传感 器( c p u 监控、网络监控等) ，从传感器收集信息并使用多个模型( 基于平均值、中值 和自动回归方法) 产生预报，预报在给定的时间内资源的使用情况。 2 p i n g e r 【2 】是一个部署在7 2 个国家超过6 0 0 台主机上的分布式监控系统，它 使用p i n g 工具在两台受管理的主机间进行周期性测量，目标是使在计算项目中易于发 现可协作的伙伴或帮助设计与理解网络。 3 f a s t l 3 1 是一个动态预测网络服务器性能的工具，允许客户应用针对完成时间、 内存需求和通信连接等需要获得一个准确的预测值，f a s t 使用了一些现成的底层网络 和主机监控工具，结合自定义的计算模型，应用于元计算1 4 】环境。 4 a c e 【5 j 主要致力于处理互联网络的运行时间多变性问题，在集群和网格环境下 大型分布式资源可以提供高效力，但同时也引入了提供和维持适当性能的复杂性，使 用a c e 保证了时间敏感应用的通信性能。 国内在这方面的研究以方法研究居多，包括； 1 分布式实时系统中的预测调度算法【6 】提出了多任务分配调度的预测算法p a a ( p r e d i c t i n ga l l o c a t i o na l g o r i t h m ) ，根据周期性任务执行时间或子任务数量的统计特性， 实现任务参量的合理预测和多任务的动态调度，以提高系统的实时性能，在任务完成 时间、负载均衡度、系统响应时间及任务夭折率等多方面均有显著改善。 2 分布式系统中主机负载预测的一种普适性方法【7 1 ，从分析主机负载的特性入手， 依据负载动态变化的规律，提出了一种具有普遍适用性的主机负载预测方法线性时间 序列模型法，并按该方法建立了h l p s 饵o s tl o a dp r e d i c t i o ns y s t e m ) 模型，提出了h l p s 的实现策略。 1 4 研究方法和指导思想 在带宽测量和预报算法已经存在一些工具，但都存在网络带宽占用较大和c p u 耗 用较高的问题，因此本文的研究方法还是基于现有的工具和理论，针对它们的不同特 点选用一种较实用的技术，然后结合网格环境的特点提出一种改进算法以适应网格环 境下的带宽测量和预报要求，并对改进算法进行评测。 2 长春工业大学硕士学位论文 1 5 开发环境和相关技术简介 1 5 1l i n u x 操作系统简介 l i n u x 是一套免费使用和自由传播的类u n i x 操作系统，这个系统是由全世界各地 的成千上万的程序员设计和实现的。自从1 9 9 0 年诞生到现在，由于l i n u x 具有开放源 代码，完全免费，安全，稳定等诸多优势已经在各个信息技术行业开始了大面积采用。 l i n u x 以高效性和灵活性著称。它能够在p c 计算机上实现全部的u n i x 特性，具有多 任务、多用户的能力，在服务器操作系统市场上的占有率增长强劲，根据2 0 0 3 年的统 计l i n u x 在服务器操作系统市场上的占有率已经超过3 0 ，已经有超过1 0 0 0 万的企业 用户在使用l i n u x 作为服务器平台，同时还有不计其数的个人用户。众多国际大型i t 商业公司包括i b m 、h p 、s u n 、o r a c l e 等已经开始把注意力转向l i n u x 并投巨资开 发l i n u x 操作系统相关产品，众多厂商开始发布自己的l i n u x 版本。 l i n u x 具有以下主要特征 8 1 ： 1 全面的多任务和真正的3 2 位操作系统。l i n u x 和其他u n i x 系统一样是真正的 多任务系统，它允许多个用户同时在一个系统上运行多道程序。l i n u x 还是真正的3 2 位操作系统，它工作在i n t e l8 0 3 8 6 和后来的i n t e l 处理器的保护模式下。 2 xw i n d o w 系统。xw i n d o w 是u n i x 平台上的事实工业标准。x f r e e 8 6 则是l i n u x 平台上的xw i n d o w 系统，xw i n d o w 系统是功能强大的图形界面，支持多种应用程序。 3 支持t c p i p 协议。在l i n u x 系统中，通过e t h e r n e t 可以连接到i n t e m e t 或当地 的局域网。使用s l i p ( s e r i a ll i n ei n t e m e tp r o t o c 0 1 ) 或p p p ( p o i mt op o i n tp r o t o c 0 1 ) ， 通过电话线和调制解调器也可连到i n t e m e t 上。 4 虚拟内存和共享库。l i n u x 可以利用你的硬盘的一部分作为虚拟内存，从而扩 展你的可用内存数量。l i n u x 不使用分段，也没有虚拟内存的限制。l i n u x 同时利用共 享库技术，允许那些使用标准子过程的程序在运行时共享子过程，从而节约了大量的 系统空间。 5 l i n u x 内核中的代码均为自由代码。l i n u x 上的大部分程序是自由软件。这些软 件是在自由软件基金会的g n u 计划下开发的。尽管如此，来自世界各地的黑客、程序 员，甚至商业公司也加入了l i n u x 软件开发的行列。 6 l i n u x 支持商业版u n i x 的全部功能。事实上，l i n u x 系统上的一些功能是u n i x 系统所不具备的。 7 g n u 软件的支持。l i n u x 支持大部分g n u 计划下的自由软件，包括g n uc 和g c c 编译器、g a w k 、g r o f f 和其他软件。 8 l i n u x 符合i e e ep o s i x 1 标准。l i n u x 特别注重可移植性，这样也支持u n i x 的其他一些标准。 9 l i n u x 比其他u n i x 系统更为便宜。如果通过i n t e m e t 下载l i n u x ，则不用花 长春1 = 业大学硕士学位论文 分钱。如果购买l i n u x 发布，也很便宜。 1 0 l i n u x 支持多种硬件平台。从低端的i n t e l3 8 6 直到高端的超级并行计算机系统， 都可以运行l i n u x 系统。 1 1 l i n u x 系统网络功能强大。不仅仅因为l i n u x 系统内核中紧密地集成了网络功 能和有大量的网络应用程序，更因为l i n u x 系统在超强网络需求下表现出的令人惊奇 的健壮性。 1 5 2 网格技术 “网格”是一个新出现的概念，代表了一种先进的技术和基础设施，是继i n t e r n e t 之后又一次重大的科技进步 9 1 。网格就是一个集成的计算与资源环境，或者说是一个计 算资源、池【1 0 l 。网格能够充分吸纳各种计算资源，并将它们转化成一种随处可得的、可 靠的、标准的同时还是经济的计算能力。除了各种类型的计算机，这里的计算资源还 包括网络通信能力、数据资料、仪器设备、甚至是人等各种相关的资源。 根据应用领域与求解问题的特点，人们提出了多种名称的网格，比如以数据密集 型问题的处理为核心的数据网格【l l 】，以解决科学问题为核心的科学网格【1 2 1 ，以全球地 球系统模型问题求解为主要目的的地球系统网格【1 3 】等等。此外还有地震网格【1 4 1 、军事 网格【1 5 i 、n a s a ( n a t i o n a l a e r o n a u t i c s a n ds p a c e a d m i n i s t r a t i o n ) 的i p g 【哺j 等行业网格。 对于网格提供的计算能力，有四个基本的要求，它们分别是可靠性要求、标准化 要求、易访问性要求和价格低廉的要求i lo 】。网格的核心就是突破了以往强加在计算资 源之上的种种限制，使人们可以以一种全新的更自由、更方便的方式使用计算资源， 解决更复杂的问题。 网格可以有非常广泛的应用领域，一旦建立起了网格，就可以开展许多以前无法 进行的工作和研究。在科学计算领域，网格可以在如下几个方面得到应用【10 】： 1 分布式超级计算。这和以前的高性能计算的作用十分类似，不同的是以前的高 性能计算大多是既重视的，主要靠一个地方的高性能计算机完成计算任务。目前遇到 的许多科学与工程计算问题是无法在任何一台超级计算机上解决的，因此需要更多的 超级计算机一起来完成，网格可以把分布式的超级计算机集中起来，协同解决复杂的 大规模问题。 2 高吞吐率计算。高吞吐率计算和高性能( 超级) 计算的侧重点是不同的，高性 能计算关心的是每秒能够完成的计算量，度量的时间单位很小。而对于高吞吐率计算， 它关心的是几个月、一年甚至是几年完成的计算量，度量的时间单位比较大。对于这 样的问题，可以利用c p u 周期窃取的技术，将大量空闲计算机的计算资源集中起来， 提供给对时间不太敏感的问题，作为计算资源的一种重要来源。 3 数据密集型计算。对于数据密集型问题，数据采集地点、数据处理地点、数据 分析与结果存放地点、可视化设备的地点等往往不在同一个地方，数据密集型问题的 4 长春丁业大学硕上学位论文 求解往往同时会产生很大的通信和计算需求，需要网格能力才可以解决。许多高能物 理实验，数字化天空扫描，气象预测等都是数据密集型问题。 在社会经济生活领域，网格可以在如下领域得到应用： 1 基于广泛信息共享的人与人交互。原来的人与人的交互受到地理位置、交互能 力、共享对象等等许多条件的限制。它可以让地理上分散的人员在_ 个虚拟的共享空 间中进行交互，共同讨论问题，可以产生面对面的效果，无疑会是十分理想的，会对 大家的工作方式产生很大的影响。 2 更广泛的资源贸易。计算能力闲置的机器可以共享出来，通过网格让更多的人 来租用；需要计算能力的人可以不必购买更大的计算机，只要根据自己计算任务的需 求，向网格购买计算能力就可以满足要求。除了计算资源。包括贵重仪器、程序、数 据、信息、文化产品等等各种资源都可以在贸易的基础上广泛共享。 网格作为一种新出现的重要的基础性设施，和其它的系统相比，具有分布性、自 相似性、动态多样性( 不可预测性) 、以及管理的多重性等多个方面特点。 1 分布与共享。分布性是网格的一个最主要的特点，网格的分布性首先是指网格 的资源是分布的，分布的网格一般涉及的资源类型复杂，规模较大，跨越的地理范围 较广。基于网格的计算是分布式计算，在网格分布式环境下，需要解决资源与任务的 分配和调度问题，安全传输和通信问题，实时性保障问题，人与系统以及人与人之间 的交互问题等等。网格资源虽然是分布的，但是它们却是可以充分共享的，网格上的 任何资源都可以提供给网格上的任何使用者。共享是网格的目的，没有共享便没有网 格，解决分布资源的共享问题是网格的核心内容。 2 自相似性。自相似性在许多自然和社会现象中大量存在，一些复杂系统大都具 有这种特征，网格就是这样。网格的局部和整体之间存在着一定的相似性，局部往往 在许多地方具有全局的某些特征，而全局的特征在局部也有一定的体现。网格的自相 似性在网格的建造和研究过程中有重要的意义。 3 动态性与多样性。网格的动态性包括动态增加和动态减少两个方面的含义，原 来拥有的资源或者功能，在下一时刻可能就会出现故障或者不可用；而原来没有的资 源，可能随着时间的推移会不断地加入进来。网格资源的动态变化特点要求网格管理 必须充分考虑并解决好这一问题，对于网格资源的动态减少或者资源出现故障的情况， 要求网格能够及时采取措施，实现任务的自动迁移，做到对高层用户透明或者尽可能 减少用户的损失。网格资源是异构和多样的，在网格环境中可以有不同体系结构的计 算机系统和类别不同的资源，因此网格系统必须能够解决这些不同结构、不同类别资 源之间的通信和互操作问题。网格的异构性或者说资源多样性的存在，为网格软件的 设计提出了更大的挑战。 4 自治性与管理的多重性。网格上的资源，首先是属于某一个组织或者个人的， 因此网格资源的拥有者对该资源具有最高级别的管理权限，网格应该允许资源拥有者 长释工业大学硕士学位论文 对他的资源有自主的管理能力，这就是网格的自治性：网格资源也必须接受网格的统 一管理，否则不同的资源就无法建立相互之间的联系，无法实现共享和互操作，无法 作为一个整体为更多的用户提供方便的服务，因此网格的管理具有多重性，一方面它 允许网格资源的拥有者对网格资源具有自主性的管理，另一方面又要求网格资源必须 接受网格的统一管理。 1 5 3 g l o b u s 项目 g l o b u s 项目由t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ( d a r p a ) ，u s d e p a r t m e n to f e n e r g y ，t h en 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 ) ，t h en a t i o n a la e r o n a u t i c s a n ds p a c e a d m i n i s t r a t i o n ( n a s a ) 等机构共同资助，项目的承担单位是a r g o n n e n a t i o n a l l a b o r a t o r y sm a t h e m a t i c sa n dc o m p u t e rs c i e n c ed i v i s i o n 以及t h eu n i v e r s i t yo fs o u t h e r n c a l i f o m i a si n f o r m a t i o ns c i e n c e si n s t i m m ，项目开始于1 9 9 6 年i l ”。 o l o b u s 项目是目前国际上最有影响的与网格计算相关的项目之一，其最初的目的 是希望把美国境内的各个高性能计算中心通过高性能网络连接起来，方便美国的大学 和研究机构使用，提高高性能计算机的使用效率。当时在美国建立了一个实验环境 - - i w a y ，它把位于美国1 7 个不同地点的6 0 多个组织的超级计算机和资源通过高性 能网络联系起来，进行大规模科学模拟、协同工程、并行计算等科学研究【1 8 l 【1 9 】f 2 0 l ，这 实际上是g l o b u s 项目的前身。 g l o b u s 项目把在商业计算领域中w e bs e r v i c e 技术融合在一起1 2 ”，希望不仅仅局限 于科学计算领域，而且能够对各种商业应用进行广泛的、基础性的网格环境支持，实 现更方便的信息共享和互操作，从而对商业模式、人的工作方式和生活方式产生深远 的影响。g l o b u s 对信息安全、资源管理、信息服务、数据管理以及应用开发环境等网 格计算的关键理论和技术进行了广泛的研究，开发出能在多种平台上运行的网格计算 工具包软件( g l o b u s t o o l k i t ) ，能够用来帮助规划和组建大型的网格试验和应用平台， 开发适合大型网格系统运行的大型应用程序。 为了有效地支持网格计算环境【2 2 1 ，g l o b u s 工具包针对g l o b u s 项目中提出的各种协 议【2 3 】，提供了一系列的服务( s e r v i c e ) 、软件库、编程接口( a p i ) 和使用例子1 2 4 1 。g l o b u s 工具包的实现主要有四方面的内容： 1 网格安全，这是网格计算环境正常运行的保证，g l o b u s 主要是结合目前成熟的 分布式安全技术，并进行一定的扩展，以适合网格计算环境的特点。 2 网格信息获取与分布，在网格计算环境中如何发布资源信息，如何查询、检索 资源信息是有效使用各种资源的前提条件。 3 网格资源管理，由于网格环境中的资源主要分布在广域网环境中，采用目前常 用的局域网资源管理技术不能有效地对其进行管理，为此g l o b u s 在局域网资源管理之 上实现了更高层次的资源管理技术，在信息服务的支持下，可有效地支持广域范围内 6 长春t 业大学硕士学位论文 的资源管理。 。 4 网格远程数据传输，实现广域网环境下的高速、可靠的数据传输和实现对应用 程序基本透明的远程文件i o 访问是g l o b u s 考虑的重要内容。 针对上述四个方面的内容，g l o b u s 项目实现的主要组成部分如图1 1 所示： 图1 - 1g l o b u s 工具包在网格计算逻辑结构中组成部分 1 网格安全基础设施例ds e c u r i t yi n f r a s t r u c t u r e ( g s i ) ：g s i 负责在广域网络 下的安全认证和加密通信，提供单点登录功能、远地身份鉴别功能、数据传输加密功 能等，提供了基于g s i 协议的g e n e r i cs e c u r i t ys e r v i c e s a p i ( g s s a p i ) 接口，是保证 网格计算环境安全性的核心部分。 2 g l o b u s 资源分配管理_ g l o b u sr e s o u r c ea 1 l o c a t i o nm a n a g e r ( g r a m ) ：g r a m 负责远程应用的资源请求处理、远程任务调度处理、远程任务管理等工作，负责对 r e s o u r c es p e c i f i c a t i o nl a n g u a g e ( r s l ) 信息的解析和处理工作，是网格计算环境中的 任务执行中心。 3 元计算目录服务m e t a c o m p u t i n gd i r e c t o r ys e r v i c e ( m d s ) ：m d s 主要完成 对网格计算环境中信息的发现、注册、查询、修改等工作，提供对网格计算环境的一 个真实、实时的动态反映。主要基于l i g h t w e i g h td i r e c t o r y a c c e s sp r o t o c o l ( l d a p ) 协 议，其处理的信息主要是网格计算环境中的各种资源( 包括数据资源、计算资源等) 、 服务和其它主题的描述，m d s 是网格计算环境中的信息服务中心。 4 全局二级存储服务g 1 0 b a la c c e s st os e c o n d a r ys t o r a g e ( g a s s ) ：g a s s 简 化了在g l o b u s 环境中应用程序对远程文件i o 的操作，使得使用u n i x 和标准c 语言 1 0 库的应用程序基本不用改动就可在o l o b u s 环境中执行，g a s s 是一个支持网格计算 环境远程i d 访问的中间件。 5 网格f t p 服务g r j d f t p ：g r i d f t p 是一个高性能、安全、可靠的数据传输 7 长存工业大学硕士学位论文 协议，并针对高带宽的广域网络环境进行了优化，具有支持第三方传输、断点续传、 并行传输、与g s i 结合的安全认证、缓存等特性，是网格计算环境中的数据传输工具。 6 g l o b u s 副本管理g l u b u sr e p l i c am a n a g e m e n t ：副本管理是一大类科学应用 程序中需要考虑的重要问题，由于存在对大型远程文件的访问，g l o b u sr e p l i c ac a t a l o g 通过把部分相关数据智能地放置在离科学应用程序最近的位置，使得科学应用程序可 快速地对数据进行访问。 1 6 本文结构 本章主要阐述了论文的主要研究内容、目的和现实意义，并介绍了带宽测量和预 报算法的研究现状及其分类，网格计算的背景和开发环境。第二章详细说明网络有效 带宽实时测量算法的基本原理与实现。第三章介绍多种预报模型并选用了一种n w s 的 改进预报模型动态指数平滑算法。第四章讲述了如何在网格环境下实现测量与预 报结果的通信。第五章分析实验数据并进行性能分析。第六章对本文的研究进行总结 并提出不足。 8 长春工业大学硕士学位论文 第二章网络有效带宽实时测量算法的基本原理与实现 2 1 基本概念 测量网络路径上端到端的有效带宽对于网络路由决策、负载均衡管理、传输性能 监控和q o s 管理等都具有重要意义。路径的有效带宽与该路径上的背景流量密切相关， 由于背景流量具有瞬时性，因此对有效带宽的实时精确测量是相当困难的。 根据测量方式的不同，对网络带宽测量般分为主动测量和被动测量1 2 ”，主动测 量通过主动向网络主机或服务器发送承载报文，获取与测量目标相关的性能参数计算 得出网络带宽；被动测量通过在网络特定位置安放的探针。记录和汇总某链路上的流 量信息分析得出网络带宽。主动测量增加了网络的数据负载且测量的附加流量有可能 影响测量结果。被动测量可以消除附加流量的影响和h e i s i n g b e r g 效应【2 6 】，但其无法确 保隐私和安全且难以获得对网络的端到端行为的理解。 带宽测量技术使用的算法主要有数据包对( p a c k e tp a i r ) 算法 2 7 - 3 1 】，p a t h c h a r 算法 3 2 - 3 4 及其衍生算法和分组串算法t 35 1 。数据包对算法通过同时发出两个背靠背的数据包， 使它们在链路瓶颈处排队，利用通过瓶颈后产生的时间间隔计算路径带宽。数据包对 算法原理简单，实现容易，但在处理网络噪音、丢包和多重路由尚缺乏有效机制。基 于数据包对算法的工具有b p r o b e ，c p o b e 2 8 1 和h e t i m e r 3 ”。p a t h c h a r 算法是一种单包测 量方法，通过向每条链路发送大小不同的包，确定其线性关系，再计算每个线性关系 的斜率，最终计算出每条链路的带宽值。p a t h c h a r 算法需要发送大量测量数据包，对网 络正常运行有影响，无法自适应路由变化，且中间结点必须支持i c m p 协议。基于 p a t h c h a r 算法的工具有p a t h c h a r 3 2 1 ，c l i n k l 3 3 1 和p c h a r 3 4 1 。分组串算法通过不断向路径上 发送大量的时间间隔越来越短的数据包，检测i m 的变化情况，r t t 变化的转折点即 为网络的可用带宽。分组串算法在测量期间严重影响网络正常运行且难以有效快速地 检测出r t t 变化的转折点。 基于数据包对算法由于其原理和实现比较简单，对网络影响小，在研究了数据包 对算法的优缺点后，针对其在高网络噪音下测量失真的情况，提出了改进算法等 比包序列算法，通过在源端向数据包内加入时间戳的方式，在目的端计算网络的有效 带宽。 2 1 1 端到端路径 数据包由源端到目的端可能经过一系列的存储转发节点和数据传输链路，由这些 节点和链路所构成的一条逻辑线路被称为端到端路径。如图2 1 所示，设路径r 由n 条 链路组成，分别为1 i ( i = 1 n ) ，带宽分别为b i 。n o 为源端节点，n 。为目的端节点。 9 长奋工业人学硕l 学位论文 圈2 - 1端到端路径模型 2 1 2 瓶颈带宽与有效带宽 在端到端路径中没有其它任何背景流量存在时，路经所能够提供的最大带宽b 可 以表示为： b = m i n b i ( 1 ) f i 。o - , n 即瓶颈带宽由路径上最窄链路的物理带宽决定，表征了该路经所能提供的端到端 的最大数据吞吐量。设链路l i 上的背景流量为h ，则链路l i 的有效带宽为u i = b i - p i ， 同理可知，端到端路径的有效带宽u 可以表示为： u = m i nu l = m i n ( e 一只)( 2 ) l 一2 一2 2 2 数据包对模型 数据包对模型的基本思想是从源端发送一对大小为s 的数据包，其时间间隔为t o ， 若数据包在路径上传输的过程中路径的背景流量未对探测包对产生影响，如图2 - 2 所 示。设数据包对到达链路i i 时的时间间隔为a t a i ，离开l i 时的时间间隔为t i ，则： 妒器卜，詈 即当数据包到达目的端时起时间间隔a t n 为： 一a t o , m 。a ，x 蔚一卜磊m i 扫nb ，卜( ，蔷 ( 4 ) 所以，只要t 0 足够小，就可以计算出路径的瓶颈带宽。 a k l 图2 - 2数据包对模型 l o 长春工业大学硕士学位论文 2 3 等比包序列算法描述 2 3 1 算法基本思想 使用等比包序列算法，从源端向目的端发送一系列大小均为s 南数据包( 如图2 - 3 所示) ，且每相邻的一对数据包的时间间隔满足如下等式： i a t s i ，s2 2 f o ( 5 ) 【a t 趾一，= k a t 趾：，趴，( f = 3 ，4 ，玎；七为常数) 其中毽- l ，岛为s i - i 与s i 数据包之间发送时的时润间隔，我们假设，在路径中存 在背景流量的情况下，随着包序列时间间隔的增大，序列中被插入干扰流量的可能性 也增大，当在链路b i 处，存在背景流量p i ，使得u i - b i p i 获得整条链路的最小值，此 时背景流量对包序列时间间隔的影响将保持到目的端。在目的端对包序列的到达时间 间隔进行统计，时间间隔大于或等于头几个数据包间时间间隔而又不符合( 5 ) 式变化 规律的数据包对，即为受背景流量影响的数据包对，使用这些数据包利用等式 血，= 硒s= 瓦s 即可求出路径中的有效带宽。 口e - 1 咽e 搬 i i f 丑一1 4 = 尼2 f 却，= 如 图2 3等比包序列模型 2 3 2 路径中不存在背景流量的情况 分析路径中不存在背景流量时使用等比包序列算法的情况。只要a t o 足够小，包序 列就会在瓶巅链路处排队，设当数据包s i 到达瓶颈链路时队列长度为q ，珞j _ 】，墨足 a 够大，满足等式出札i ，毋g 告，即在s i 之前所有的数据包都需要排队，而s i 之后所有 的数据包都不需要排队，则在包序列到达目的端时，s i 之前相邻数据包对