（计算机应用技术专业论文）基于文件共享的p2p网络建模及仿真.pdf

兰州大学研究生学位论文 摘要 网络建设的根本目的在于应用。为了保证网络的正常运行和服务质量，对网络的有 效管理越来越重要。 网络性能管理的实质是对网络进行性能分析、评价。通过收集和处理有关性能数据， 建立网络运行模型，模拟网络行为。p 2 p 网络作为分布式网络应用的一种全新范例正日 益普及和推广。p 2 p 网络技术起源于文件共享，网络中有大量的p 2 p 文件交换业务，给 网络流量和性能造成巨大影响。因此，基于文件共享的p 2 p 网络性能分析与研究具有较 高的实用价值。 本论文首先对网络性能分析的方法、指标和基本理论进行了论述。研究了p 2 p 网络 文件共享的模式结构和关键技术，对p 2 p 网络的通用模型进行分析和讨论，总结出影响 p 2 p 网络性能的关键因素。以p 2 p 文件共享软件b t 的工作模式为基础，建立了p 2 p 网 络的性能分析模型，并得到有关网络性能随特定参数变化的规律，通过实验测得到相关 性能指标，验证了模型的正确性。最后对p 2 p 网络模型进行模拟仿真，进一步分析了 p 2 p 网络的性能特征，证明所建模型用于网络性能的分析是可行的。 关键词：性能管理、性能参数、p 2 p 网络、建模、网络仿真 兰州大学研究生学位论文 _ - _ _ ，_ _ - - ， _ _ - ，_ - _ - - - _ _ - - _ - - _ _ _ a b s t r a c t s i n c en e t w o r ki sa p p l i c a t i o nd r i v e nt e c h n o l o g y , i t sm a n a g e m e n t i sa l le s s e n t i a lp a r t i nn e t w o r kf i e l da n da l s oh a v ea t t r a c t e dm u c ha t t e n t i o ni nc o m p u t e rt e c h n o l o g y a sw ea l lk n o wt h a tp e r f o r m a n c ea n a l y s i sa n de v a l u a t i o ni sav e r yi m p o r t a n tp a r t a m o n gp e r f o r m a n c em a n a g e m e n t ，l a t e l y , p 2 pn e t w o r k h a se m e r g e da san e w p a r a d i g mf o r b u i l d i n gd i s t r i b u t e dn e t w o r ka p p l i c a t i o n s s h a r i n gt h ef i l e sp r o d u c e t h ep 2 p t e c h n o l o g y a n d t h e r eo r ea l s om a n yf i l es h a r i n gs y s t e m so nn e t w o r kb a s ep 2 p a p p l i c a t i o n s ，w h i c hi n f l u e n c e t h et r a f f i ca n dn e t w o r kp e r f o r m a n c eh e a v i l y t h e r e f o r e ，s t u d y i n ga n da n a l y s i st h ef i l es h a r i n g s y s t e mo f p 2 p n e t w o r kp e r f o r m a n c eh a sg r e a ta p p l i c a t i o nv a l u e i nt h i st h e s i s ，w ei n t r o d u c e dt h em e t h o d so f p e r f o r m a n c ea n a l y s i s ，p e r f o r m a n c ea n a l y s i s p a r a m e t e r sa n d a l s oi t sb a s i ct h e o r i e s ；a f t e rs t u d y i n go nt h es t r u c t u r ea n dk e y t e c h n o l o g yo f p 2 pf i l e ss h a r i n gs y s t e ma n da n a l y s i si np 2 p g e n e r a ln e t w o r k m o d e l w e p o i n t e do u tt h ek e y f a c t o rw h i c hi n f l u e n c e dt h ep 2 pn e t w o r kp e r f o r m a n c e ；as i m p l em a t h e m a t i c a lm o d e lw a s d e s i g n e db a s e do nb t a sau s e f u lt o o lt oe x p l o r ea n di l l u s t r a t ef u n d a m e n t a lp e r f o r m a n c eo f p 2 pf i l es h a r i n gs y s t e m s ；f r o ma n a l y s i st h a tm o d e lw e g e ts o m ev a l u a b l ec o n c l u s i o n ，w h i c h a r ep r o v e dt r u et h r o u g ho u r e x p e r i m e n to n r e a ld a t a i nl a s ts e c t i o n ，w e p r e s e n t t h es i m u l a t i o n o fp 2 pf i l es h a r i n gs y s t e m ，f r o mw h i c hm o r ec h a r a c t e r so fp 2 pn e t w o r kr 妞 f o r m a n c ea r e c o n c l u d e da n dv a l i d a t e dt h a tt h em o d e lc a nb eu s e dt op e r f o r m a n c e a n a l y s i s k e y w o r d s ：p e r f o r m a n c em a n a g e m e n t ，p e r f o r m a n c ep a r a m e t e r , p 2 pn e t w o r k ，m o d e l i n g ， n e t w o r ks i m u l a t i o n i i 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导卜- 独立进 行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、 数据、观点等，均已明确注明出处。除文中已经注明引用的内容外，不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究 成果做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：日飙z , 4 - , 邓 关于学位论文使用授权的声明 爿二人在导师指导下所完成的论文及相关的职务作。铺，知识产权归、 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和也予版， 允许论文被查阅和借阅；小人授权兰州i 大学可以将术学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术沦文或成果时，第一署名单位仍然为兰州大学。 保密沧文在解密后应遵守此觌定。 删省繇他蝴虢触：遮必 兰州大学研究生学位论文 第一章绪论 1 1 计算机网络应用的发展现状 随着计算机网络在全球范围的不断推广应用，网络越来越成为世人所关注的热 点之一。当前计算机网络的发展特点是：网络规模不断扩大，复杂性不断增加，网 络的异构性越来越高。同时，伴随着各种网络应用的日渐扩展，网络上不断涌现各 种网络软件为用户提供各种服务。为了保证网络的正常运行和服务质量，对网络的 有效管理越来越重要。 网络管理是“未来网络结构”的关键技术之一，与高速路由交换、虚拟网络 并称为网络发展的三大支撑技术。网络管理的发展正处于从工程经验积累向理论性 科学转变的过渡阶段。通过长期的探索和实践，这一领域已经在网络管理系统的组 成、工程化的网络管理技术、网络管理的基本概念等方面取得了足够的经验和认识。 但在新的网络环境和需求下，如何转变传统的管理模式，以适应网络管理的综合化 和智能化特征。网络建设的根本目的在于应用，研究开发人员需要重新关注当今不 断涌现的各种新的网络应用，根据这些应用的特点并结合其它领域的关键技术来实 现对网络的有效管理。 1 2 网络性能管理及其优化 i s o 定义了网络管理的五大功能嘲，包括性能管理、配置管理、故障管理、计 费管理和安全管理。 随着网络规模的不断扩大，网络业务类型不断增多，使得网络性能管理交得更 加复杂。传统的网络性能监测是通过获取不同时期网络性能变化的报告，为管理者 提供经验资料，作为管理者调整与重新规划的根据。但对于网络可用性而言，更有 意义的是对当前网络性能异常变化的及时发现，以及对未来发展趋势的准确预测。 如何根据网络情况，确定并收集反映网络性能的数据。利用合理的分析模型，通过 对网络历史流量进行模拟以及对当前流量变化进行预测，帮助管理人员对网络进行 长久的规划，并按照业务类型对网络进行合理的安排调整，显得尤为重要。 兰州大学研究生学位论文 认识影响网络性能的因素及其相互关系，探讨其性能分析与评价方法，建立评 价模型，目的是优化网络配置，提高网络的性能。 1 3p 2 p 网络概述 p 2 p 即p e e rt op e e r ，称为对等网络或点对点技术。p 2 p 是一种网络模型，在 这种网络中所有的节点是对等的( 称为对等点) ，各节点具有相同的责任与能力并 协同完成任务。p 2 p 技术是目前计算机网络技术领域研究的一个热点。 p 2 p 网络并非一种全新的技术，从某种意义来说，p 2 p 可以说是一种向传统互 联网技术的回归，体现了互联网的本质，因为互联网最初的设计目标就是让网络上 的计算机互相之间可以直接通信而不需要中介。 简单地说，p 2 p 技术是对等点之间通过直接互连共享信息资源、处理器资源、 存储资源甚至高速缓存资源等，无需依赖集中式服务器或资源就可实现。其网络通 信方式如图1 1 所示。在对等网络中，每个节点的地位都是相同的，具备客户端和 服务器双重特性，可以同时作为服务使用者和服务提供者，因此p 2 p 网络的节点具 有很高的自治性和随意性。 图1 1p 2 p 网络模型 目前网络结构的主流是c s 模式，它要求设置拥有强大处理能力和高带宽的高 性能计算机做服务器，配合高档的服务器软件，将大量的数据集中存放在上面，并 安装了多样化的服务软件，服务器在集中处理数据的同时可以为网上其它计算机服 务，提供处理能力和其它应用。过于的集中会对网络的使用造成“瓶颈”。而p 2 p 技术的特征之一就是弱化了服务器的作用，甚至取消服务器，任意两台个人计算机 互为服务器，同时又是客户机，即具有对等性。 兰州大学研究生学位论文 1 。4 论文的研究工作 迄今为止，在网络应用领域仍存在许多有待研究和解决的问题。伴随着各种新 技术的不断涌现，也对网络的管理提出新的挑战。其中网络性能分析与评价是网络 性能管理技术领域一个非常重要的分支，网络性能分析与评价己经成为人们认识网 络、了解网络、更好的使用网络的重要手段。越来越多的网络应用，让人们急需完 善网络分析评价系统和开发出各种性能测量工具，但是目前计算机网络领域的现状 是网络测量分析领域的发展远远落后于计算机网络自身的发展。有专家认为，建设 下一代高速网络所要做的第一项工作，就是分析和收集有关性能数据、建立网络运 行模型、模拟网络行为。例如在网络应用和网络性能管理中，网络流量带宽是一种 重要而宝贵的资源，网络流量的测量和模型化对于分析网络性能，指导网络流量管 理，开发高效的网络应用等方面都十分重要。 本论文首先对网络性能分析的方法、指标和基本理论进行了论述。针对目前网 络上日益普及和推广的p 2 p 网络应用，尤其是大量的p 2 p 文件交换业务，研究了p 2 p 网络文件共享的模式结构和关键技术，对p 2 p 网络的通用模型进行分析和讨论，总 结出影响p 2 p 网络性能的关键因素。以p 2 p 文件共享软件b i t t o r r e n t 的工作模式 为基础，建立了p 2 p 网络的性能分析模型，并得到有关网络性能醢特定参数变化的 规律，通过实验测得到相关性能指标，验证了性能分析模型的正确性。最后对p 2 p 网络模型进行模拟仿真，证明所建模型用于网络性能的分析是可行的。 1 5 论文的结构 论文总体分为六章，第二章介绍网络性能分析、评价的方法和基本理论工具。 第三章介绍p 2 p 网络的结构模式和应用。第四章是对基于文件共享的p 2 p 网络性能 建模及相关参数分析，通过对实验数据的处理分析验证了模型的正确性。第五章是 对p 2 p 网络模型的模拟仿真。第六章是对全文的总结和进一步研究工作的展望。 兰州大学研究生学位论文 第二章网络性能分析、评价及其理论工具 网络的性能分析与评价是网络运行的前提，网络性能分析与评价的目的主要有 三个：选择、改进和设计。具体而言，是指在众多的系统方案中选择一个最适合需 要的，即在一定的价格范围内选择性能最好的系统，达到最好的性能价格比；对已 有系统的性能缺陷和瓶颈进行改造和提高其运行效率；对未来设计的系统进行性能 预测，在性能成本方面实现最佳设计或匹配。 网络性能一般包括以下两大方面。1 ：一方面是它的可靠性( 可利用性) ，即系统 能正常工作的时间，其指标可以是能够持续工作的时间长度，如平均无故障时间， 也可以是在一段时间内，能正常工作时间所占总时间的百分比。另一方面是它的处 理能力或效率，这又可以分为三类指标：一类指标是各种吞吐率，如系统在单位时 间内能正常作业的个数；另一类指标是各种响应时间，即从系统得到输入到给出输 出之间的时间；再一类指标就是各种利用率，即在给定时间范围内，网络各个部件 被使用的时间与整个时间之比。 网络性能分析、评价的主要任务就是研究系统配置、系统负载、性能指标之间 的相互关系得到有价值的结论。 2 1 网络性能分析、评价的一般方法 对网络性能进行分析、评价的方法很多。简单地可以分为定性与定量两种“1 。 所谓定性分析指的是技术人员根据自己的经验对一个己有或待建的网络进行大致 的性能估计，判断网络配置能否满足用户的需要。这种方法显然是不准确的，常常 要在安装或使用过程中动态地做出一些调整，以满足用户的需求。定量分析就是运 用数学工具或测量方法找出反映网络性能的指标间的数值关系以及某个或某些指 标变化时对网络性能的影响。与定性分析相比，定量分析更精确地反映了网络性能 的实际情况，为研究人员设计和规划网络提供了更准确、详细的依据，使决策更科 学。 下面简单介绍有关定量分析的常用方法。 4 兰州大学研究生学位论文 2 1 1 实际测量法 通过一定的测量设备或一定的测量程序可以直接从网络中测得各项性能指标 或相关的度量值，然后经过一些简单的运算求出相应网络参数。这是最直接也是最 基本的方法，其它方法在一定程度上要依赖于它。这种方法只能适用于已经存在并 运行的系统，目前流行的大多数网络测试软件及设备均属于这种情况。 最常见的网络测量方法有两类：主动测量和被动测量。这两种方法的作用和特 点不同，可以相互作为补充。 主动测量 主动测量是在选定的测量点上利用测量工具有目的地主动产生测量流量，注入 网络，并根据测量数据流的传送情况来分析网络的性能。主动测量的优点是对测量 过程的可控性比较高，灵活、机动，易于进行端到端的性能测量；缺点是注入的测 量流量会改变网络本身的运行情况，使得测量的结果与实际情况存在一定的偏差， 而且测量流量还会增加网络负担。主动测量在性能参数的测量中应用十分广泛，目 前大多数测量系统都涉及到主动测量。 被动测量 被动测量是指在链路或设备( 如路由器，交换机等) 上利用测量设备对网络进行 监测，而不需要产生多余流量的测量方法。被动测量的优点在于它不产生多余流量， 不会增加网络负担；其缺点在于被动测量基本上是綦于对单个设备的监测，很难对 网络端到端的性能进行分析，并且可能实时采集的数据量过大，另外还存在用户数 据泄漏等安全性和隐私阿题。被动测量非常适合用来进行流量测量。 2 1 2 模型方法 首先对评价的计算机网络建立一个适当的模型，然后求出模型的性能指标，以 便对系统进行性能评价。模型中一般包括许多参数，这些参数的确定往往依赖于对 实际系统的测量结果或对系统参数的估计。 模型方法又可以分为数学分析方法和计算机模拟方法两种。数学分析法主要运 用数学公式反映网络性能指标间的关系。只要得到了每一个性能的量度与其它量度 及影响因素之间的数学表达式，那么整个网络的性能就可以准确地把握了。采用数 学分析法，需要为网络建立适当的数学模型，把一个实际的网络抽象成一个理论上 兰州大学研究生学位论文 的相对简单但又能反映真实网络情况的模型。建立模型的过程中必须做一些合理的 假定，否则是很困难的，而且即便建立了模型，其求解也是非常复杂的，甚至得不 到明确的解。数学分析法主要运用概率论、随机过程论和排队论等数学工具，尤其 是排队论，因为一个网络系统可以等价为一个排队系统。 计算机模拟法，在很多情况下，网络性能太复杂，其它方法难以处理，这时模 拟是唯一可行的分析网络的方法。应用前面的分析方法求解，有时要做出许多假设， 因而产生的误差有时难以接受。虽然，模拟过程可能浪费时间，但它能获取比排队 更精确的分析模型。当然模拟法最终是通过计算机程序实现的，然后通过对所得到 的结果来分析网络的性能。 随着计算机技术的发展，系统的庞大和复杂使得网络性能评价问题变得越来越 困难并日益引起人们的重视。寻找有效的数学理论工具、建立直观的模型描述和有 效的模型分析方法以及使用高效的模拟仿真软件进行辅助决策，是网络系统性能评 价迫切需要解决的问题。 2 2 网络的性能参数 对网络性能进行度量和描述的工具就是网络性能参数。i e t f 和i t u t 都各自定 义了一套性能参数，并且还在不断的补充和修订之中。 连接性 连接性也称可用性、连通性或者可达性，严格说应该是网络的基本能力或属性， 不能称为性能，但i t u - t 建议可以用一些方法进行定量的测量。目前还提出了连通 率的概念，可以根据连通率的分布状况建立相关模型。 延迟 延迟的定义是；i p 包穿越一个或多个网段所经历的时间。延迟由固定延迟和 可变延迟两部分组成。固定延迟基本不变，由传播延迟和传输延迟构成；可变延迟 由中间路由器处理延迟和排队等待延迟两部分构成。 丢包率 丢包率的定义是：丢失的i p 包与所有的i p 包的比值。许多因素会导致数据 包在网络上传输时被丢弃，例如数据包的大小以及数据发送时链路的拥塞状况等。 6 兰州大学研究生学位论文 为了评估网络的丢包率，一般采用直接发送测量包来进行测量。对丢包率进行 准确的评估与预测则需要一定的数学模型。目前评估网络丢包率的模型主要有贝努 利模型、马尔可夫模型和隐马尔可夫模型等等。 带宽 带宽一般分为瓶颈带宽和可用带宽。瓶颈带宽是指当一条路径( 通路) 中没有 其它背景流量时，网络能够提供的最大的吞吐量。可用带宽是指在网络路径( 通路) 存在背景流量的情况下，能够提供给某个业务的最大吞吐量。因为背景流量的出现 与否及其占用的带宽都是随机的，所以可用带宽的测量比较困难。 瓶颈带宽反映了路径的静态特征，而可用带宽真正反映了在某一段时间内链路 的实际通信能力，所以可用带宽的测量具有更重要的意义。 流量参数 i t u t 提出两种流量参数作为参考：一种是以一段时间间隔内在测量点上观测 到的所有传输成功的i p 包数量除以时间间隔，即包吞吐量：另一种是基于字节吞 吐量：用传输成功的i p 包中总字节数除以时间间隔。 网络业务量的高突发性以及网络的异构性，使得网络呈现复杂的非线性，建立 流量模型越发变得重要。早期的网络流量模型，是经典流量模型，借鉴了p s t n 的 流量模型，用泊松模型描述数据网络的流量，以及后来的分组火车模型，m a r k o v 模 型等等。随着网络流量自相似性的发现，基于自相似模型的流量建模研究也取得了 不少进展和得到了广泛的应用，如分形布朗运动模型和分形高斯噪声模型以及小波 理论分析等等。 2 3 网络性能分析建模中常用的基本理论 概率论是研究网络性能、对模型进行分析的最基本的数学工具。因为概率论的 研究对象是大量随机现象的统计与分布规律，而网络中的信息不论其产生还是到达 的时间都是随机的，数据包的长度也符合一定的概率分布。随机过程论对研究网络 性能亦有很大的帮助。但最适合的数学工具是排队论理论，因为网络中的信息流和 排队论中的顾客流非常类似。 兰州大学研究生学位论文 2 3 1 概率论与随机过程 1 指数分布 指数分布的概率密度函数为： f ( x ) = 九p “九 0 ，x o 概率分布函数为： f ( x ) = 卜8 一“ 指数分布具有无记忆性( 或马尔可夫无后效性) 。 2 泊松分布 泊松分布的概率密度函数为： p x - k ) 2 眚e ， o ，妊0 ，1 ，2 ， 泊松分布的参数 是单位时间内随机事件的平均发生率。服从泊松分布的随机 变量，其数学期望与方差相等，同为参数 即： e ( x ) = v ( x ) = 在实际系统模型中，一般都假定任务( 或顾客) 的到来是服从泊松分布。用泊 松分布描述到达速率的方法如下： p ( 在时间间隔t 有k 个任务剿= 譬e 在时间间隔t 内任务到达的期望值= 入t 平均到达速率( 任务数秒) = 泊松分布适合于描述单位时间内随机事件发生的次数。泊松分布是最熏要的离 散型概率分布之一。泊松分布作为表述随机现象的一种形式，在计算机网络和计算 机系统的性能评价中扮演了重要的角色 3 泊松过程( p o i s s o np r o c e s s ) 泊松过程是一种累计随机事件发生次数的最基本的独立增量过程。例如排队服 务系统到达的随时间变化的总顾客数就构成一个泊松过程。泊松过程是描写随机事 件累计发生次数的基本数学模型之一。直观上，只要随机事件在不相交时间区间是 独立发生的，而且在充分小的区间上最多只发生一次，它们的累计次数就是一个泊 兰州大学研究生学位论文 一 松过程。 设随机过程 x ( o ，t 【o ，一) ) 的无限状态空间是e = 0 ，l ，2 ，) 若满足下列 条件： ( 1 ) x ( t ) 是平稳独立增量过程 ( 2 ) 对任意a ，t o ，每一增量x ( a + t ) 一x ( a ) 非负，且服从参数为 t 的泊松分 布，即有 p ( x ( a “) 一x ( a ) ) - k ) = 警一，k _ o i l ，2 ， 其中 0 ，则称x ( t ) 是具有参数 的泊松过程。 4 马尔可夫过程( m a r k o vp r o c e s s ) 自然界中有一类事物的变化过程仅与事物的近期状态有关，而与事物的过去状 态无关，这种特性称为无后效性。具有这种特性的随机过程称为马尔可夫过程。最 简单的马尔可夫过程是马尔可夫链，即时间和状态均为离散的马尔可夫过程，用数 学语言来描述为： 设随机序列 x ( n ) ，n = o ，i ，2 ， 的离散状态空间为e 。若对任意m 个非负整数 n 1 ，n 2 ，n 。( 0 s n l n 2 n 。) 和任意自然数k ，以及任意i l ，i 2 ，i 。，j e 满足： p x ( n 。+ k ) = j l x ( n t ) = b ，x ( n 2 ) = i 2 ，- x ( n 。) = i 。 = p x ( n 。+ k ) = jj x ( n 。) = i 。) ( 2 1 ) 则称 x ( n ) ，n = o ，1 ，2 ) 为马尔可夫链。 在( 2 1 ) 式中，如果r l 。表示现在时刻，n l ，1 1 2 ，n _ 1 表示过去时刻，r l 。+ k 表示将来时刻，上式表明过程在将来n 。+ k 时刻处于状态j 仅依赖于现在n 。时刻的 状态i 。，而与过去m _ 1 个时刻n 。，n ：，n 。所处的状态无关。( 2 1 ) 式给出了无后 效性的表达式。 马尔可夫过程分析是一种动态随机数学模型，它是建立在系统状态和状态转移 的概念上的。所谓系统，就是我们所研究的事物。所谓状态，是表示系统的最小 组变量。当确定了一组变量的值时，也就确定了系统某一时刻的行为，并说系统处 于某一状态。当系统由一种状态变为另一状态时，称之为状态转移，常用转移概率 和转移矩阵来描述。 兰州大学研究生学位论文 当k = 1 时，战( 1 ) 称为一步转移概率，记为巩。此时 巩= 巩( 1 ) p fx ( n + 1 ) 2 j i x ( n ) = i ) p i j = 1 ，i = l ，2 豫刭 o 兰州大学研究生学位论文 2 3 2 排队论 排队论对于计算机网络通信的定量分析起着关键的作用。排队论以概率论、随 机过程为基础，对排队系统进行抽象的数学描述，给出描写排队系统的数学表达式， 从而为分析排队系统的行为、改善其性能提供有力的数学工具。 排队论是以概率论和随机过程论为基础，专门研究排队系统的行为特性的一个 数学分支。研究排队系统的行为特性，一般从以下几个方面入手： 一、顾客来源：分为有限和无限两种。若顾客来源有限但数量相当大，可近似 为无限顾客来源。 二、顾客到达模式：排队系统的服务能力不仅取决于自身，还与顾客到达的模式 有关。在排队系统中最常见的顾客到达模式是指数分布： a ( t ) = p ( 到达间隔f ) = 1 一p ，入为平均到达速率。 三、服务时间分布：在很多排队系统中，选择服务时间服从指数分布，因为服从 指数分布的随机变量具有马尔科夫性质( 无后效性质) ，即如果一个服务员正在为一 个顾客服务i e i ) i 疑务时间服从指数分布，那么为完成这个服务还要花的时间的期望值 与己进行的服务时间无关。 四、最大顾客容量：容量为0 的系统称为丢失系统，即当所有服务员都忙时来 了顾客，则顾客便会离开系统。一般系统的容量介于0 与无限之间，若用k 表示， 则k 为系统中最多可容纳的顾客数。 五、排队纪律：又称服务规则，即选择下一个顾客进行服务的原则。常见的有 先来先服务( f c f s ) 、后来先服务( l c f s ) 、随机次序服务、优先级服务等。 排队模型常用肯达尔表示法简记为：a b c k m z 。a 为到时间分布，b 为服务 时间分布，c 为服务员数，k 为系统容量，n l 为顾客来源，z 为排队纪律。一般常取 前三项。 常用的排队模型： 1 m m 1 模型 m m 1 模型表示顾客以泊松到达模式进入系统，服务时间服从指数分布，系统 中的服务员数为l 。 根据泊松到达模式，在时问t 内，有一个顾客进入系统的概为：e m m ：m + o 。 兰州大学研究生学位论文 说明顾客到达速率和系统中的顾客数无关，即：厶= 旯。同样，服务速率和系统中 的顾客数也无关：。= 1 。系统中没有顾客的概率p o = l p ，其中p = 兰 1 为服务 员利用率。系统中有n 个顾客的概率为：p 。= ( 1 一p ) p 。系统中的顾客数服从几何 分布，均值为) _ ，方差为上。顾客在系统中的平均耗费时间为卫， 1 一p(1一p)p(1一p) 顾客在队列中的平均等待时间为= 兰_ ，平均队列长度为? l ，服务员中的顾客 , u o p )1 一p 平均数为p 。 当服务员数为n 时，模型记为m m n 。 2 m g 1 模型 m g 1 模型表示顾客以泊松到达模式进入系统，具有一般的服务时间分布，系 统中只有一个服务员。此模型的排队特性如下所示： 平均等待帆t 。= 嬲 平均删媳l w _ 勰 随机变量s 为每个顾客的服务时间，p 为利用率。 l i t t l e 定律 l i t t l e 定律是排队论中应用最广的定律之一，适用于各种排队系统。其数学表 达式为： 面：五亍 这里n 为系统中的平均顾客数， 为顾客平均到达速率，i 为顾客在系统中的 平均等待时间。上式适用于不同的顾客到达模式、服务时间分布、服务员个数和服 务规则。 2 3 3 排队网络模型 一个排队网络是一个有向图g = ( v ，e ) ，由一组节点v = 1 ，2 ，m 和一组弧 e v 。v 组成，如图2 1 所示。每个节点代表一个服务站，表示实际系统中的资 兰州大学研究生学位论文 一 源。服务站包括一个队列和一个或多个服务员。例如节点可以是通信系统中的某些 网络节点( 交换机或路由器) 。这些节点可能地理上分布得很分散，但可以假设节 点间的传输时间为零。e 是弧的集合，它定义了网络拓扑，表示顾客流的可能通路。 开 图2 1 一个简单的排队模型 排队网络模型可以分为三种类型： ( 1 ) 开环网络。至少要有一个来自外部的输入弧和一个出去的输出弧。图2 1 显 示了一个具有四个节点和两个外部弧( 一个输入弧一个输出弧) 的排队网络。如果 所有的外部弧都是输入弧，那么网络会在有限的时间内趋于饱和，即没有平衡状态。 令一方面，如果所有的外部弧都是输出弧，那么排队网络将最终清空， ( 2 ) 闭环网络。在此类型中没有外部弧，网络中的颜客数目为常数，所有的顾客 永远循环流动。在2 1 的图中，节点1 和节点2 的外部弧去掉，则该网络为一个闭 环网络。 ( 3 ) 混合网络。这类排队网络对于某些类型的顾客是闭环的而对其它类型的顾客 是丌环的，则称为混合网络。如果图2 1 中有一类顾客在节点l 和节点2 之间循环 流动，而还有一类顾客流经所有的节点，则此时该网络为一个具有两类顾客的混合 网络。 兰州大学研究生学位论文 第三章p 2 p 网络的结构模式和应用研究 p 2 p 网络不像c s 结构那样需要依赖于一个中心服务器来提供服务，p 2 p 网络 是一个高度互联的结构，它通过间歇的联机来互相发现。p 2 p 网络中的服务都是基 于所有的端点( p e e r ) 共同实现的。p 2 p 可以通过使用各种不同的通信渠道获得有效 的带宽资源，这就避免了在传统的c s 模式中必须使用专门的路由器，p 2 p 使得经 由各种不同的路由器进行通信成为可能。这些路由器可以是p 2 p 网络中赋予路由功 能的端点，从而减轻了网络拥塞。 3 1 p 2 p 技术的优势 ( 1 ) 负载均衡。p 2 p 网络环境下可以根据策略灵活地部署信息。负载均衡模块可 以监控各种信息的流量和请求率，然后重新部署这些信息以减轻单个节点的负载。 ( 2 ) 信息资源丰富。任何p 2 p 网络用户能够扫描活动节点并搜索需要的信息， 然后直接从这个节点上下载信息。用户可以在他们的机器上把信息共享出来，这样， 请求率高的文件能够很快地在网络中扩散开来。 ( 3 ) 冗余和容错。p 2 p 网络的多个节点问的信息复制导致高度冗余，其直接结果 是提高了信息的可用性，使之为更多的用户提供服务。另外，冗余使得网络不会产 生“单点失效”问题，所以分散式的p 2 p 网络提高了网络的容错和安全。 ( 4 ) 基于内容的寻址。在w e b 上，u r l 地址并不能直接反映出它们的内容。但在 p 2 p 网络中，存储特定信息的节点地址对于用户是透明的，用户向网络提交查询请 求时，请求信息中便包括需要查询的信息，p 2 p 软件把请求转换成存放这些信息的 节点地址。信息标志符等价于一组存储有该信息的节点地址，所以把信息按照内容 分类后再分布在网络上，这更易于信息资源的查找。 3 2 p 2 p 网络的主要结构模式 p 2 p 技术起源于文件共享。在p 2 p 的发展过程中，文件交换技术的演变最具代 表性。下面就以典型的p 2 p 文件交换网络为例来研究p 2 p 网络的主要结构模式，。 4 兰州大学研究生学位论文 3 2 1 集中目录式对等网络 在这种网络模型中，一群商性能的中央服务器保存着网络中所有活动对等端点 地址信息及其共享资源的目录信息。当需要查询某个文件时，对等端点会向一台中 央服务器发出文件查询请求。中央服务器进行相应的检索和查询后，返回符合查询 要求的对等端点地址信息列表。查询发起端点接收到应答后，会根据网络流量和延 迟等信息进行选择，与适合的端点直接建立连接，并开始文件传输。n a p s t e r 是最 为典型的集中目录式对等网络模型。其工作原理如图3 1 所示： 图3 1 集中目录式对等网络模型 这种形式具有中心化的特点，但是它不同于传统意义上的c s 模式。因为传 统的c s 模式采用的是种垄断的手段，所有资料都存放在服务器上，客户机只 能被动地从服务器上读取信息，并且客户机之间不具有交互能力；而集中式p 2 p 模 式则是所有资料文件都存放在提供该资料的客户机上，服务器上只保留索引信息， 服务器与对等端点以及对等端点之间都具有交互能力。 集中式p 2 p 可提供中心服务器目录检索、管理服务和标准的点到点通信，具有 高效的检索和低效的交换服务的特点。集中式p 2 p 对小型网络而言在管理和控制方 面占有一定的优势，但对大型网络并不适合。 3 2 2 分布式对等网络 在分布式对等网络模型中，对等端点通过与相邻对等端点之间的连接遍历整个 网络。该模型中为了查找某个文件，对等端点首先向与之相邻的所有活动对等点发 送一个查询请求包( q u e r y ) 。其它对等端点在接收到该查询请求包后，检奁本地是 兰州大学研究生学位论文 否有符合查询请求的文件内容，如果有，则按查询请求包的发送路径返回一个查询 响应包。无论本地是否存在符合查询请求的文件内容，其它对等端点都会将该查询 包通过广播方式继续在网络中传递，直至查询包中t t l ( t i m eo fl i f e ) 属性值递减 为0 时停止继续转发。工作原理如图3 2 所示： 圈3 2 分布式对等网络模型 在分布式p 2 p 中，对等端点通过与相邻端点之间的连接遍历整个网络体系。每 个端点在功能上都是相似的，并没有专门的服务器，而对等端点必须依靠它们所在 的分布网络来查找文件和定位其它端点。文件搜索排队响应时间长，造成大量网 络流量。用户之间的网络连接决定网络弹性和性能。没有中央控制点，不会因为 点故障导致全部瘫痪。 3 2 3 混合式对等网络 图3 3 混合式对等网络模型 混合式p 2 p 结合了集中式和分布式p 2 p 的优点，在设计思想和处理能力上都得 到了进 步的优化。它在分布式模式的基础卜- ，将用户节点按能力进行分类，使某 6 兰州大学研究生学位论文 些节点担任特殊的任务。这些节点共分为3 种： ( 1 ) 用户节点：普通节点，它不具有任何特殊的功能。 ( 2 ) 搜索节点：处理搜索请求，从它们的“孩子”节点中搜索文件列表，这些 节点须据有较高的网络连接速度。 ( 3 ) 索引节点：连接速度快、内存充足的节点可以作为索引节点。索引节点用 于保存可以利用的搜索节点信息，并搜集和维护网络的状态和结构信息。 目前第三代p 2 p 的软件体系结构中，一般都采用混合式p 2 p 。这种模式的关键 之一是引入了索引节点，索引节点不会直接连接到相关的资料上，它就像搜索引擎 一样，只是搜索和所需资料相关的地址，至于用户至d 底连接下载了什么内容则和它 无关；关键之二是引入搜索节点，搜索节点管理着所属用户的文件列表。用户节点 通过索引节点获得搜索节点信息，之后用户节点就与获得的搜索节点相连，每一次 查询都通过该搜索节点进行。当用户发出搜索请求后，如果和用户节点直接相连的 搜索节点查询结果达到用户设定值就停止。如果不足，就向相邻的搜索节点发出请 求，如果查询结果还不够，就继续向外快速发散，直到所有的搜索节点都被搜索到 为止。改进了搜索排队响应时间，每次排队产生流量低于分布式。 3 3p 2 p 网络的应用 p 2 p 引导网络运行模式从集中式向分布式偏移，也就是说网络应用的核心从中 央服务器向9 回络边缘的终端设备扩散：服务器到服务器、服务器到p c 机、p c 机到 p c 机，p c 机到e a p 手机所有网络节点上的设备都可以建立p 2 p 对话。伴随着 下一代互联网的发展，p 2 p 给互联网带来了无限的发展空间，至少有上百种应用能 被开发出来“”，但从目前的现状看，p 2 p 的应用可以概括如下： 1 对等计算 采用p 2 p 技术的对等计算，是把网络中的众多计算机暂时不用的计算能力连结 起来，使用积累的能力执行超级计算机的任务，使它们发挥出只有超级计算机才具 有的巨大功能，如天气预报、动画制作、基因组的研究等。有了对等计算之后，就 不再需要昂贵的超级计算机了。从本质而言，对等计算就是网络上c p u 资源的共享。 兰州大学研究生学位论文 2 协同工作 ? 2 p 技术使得互联网上任意两台计算机都可建立实时的联系。建立了一个安全、 共享的虚拟空间，人们可以进行各种各样的活动，这些活动可以同时进行，也可以 交互进行。p 2 p 技术可以帮助企业和客户，以及合作伙伴之间建立起一种安全的网 上工作联系方式。通过p 2 p 可以建立一个安全的企业级协同工作平台( p 2 p 网络) ， 提供互动的供求信息，帮助用户进行经销渠道维护、售后服务等。目前已经有p 2 p 网络在电子商务中成功应用的方案。 3 即时通信 两个或多个用户可以用其进行快速、直接的交流，易于同非计算机终端设备进 行通信，而且它不依赖设备即可辨别用户。当前广泛使用的m s n ，i c q ，q q 等著名 的通讯软件正在改变传统的通信方式。 4 分布式存储 这类应用改变了数据单一集中存储的模式，利用数据存储软件，在网络上将文 件分散化存放，而不像现在存放于专用服务器。这样既减轻了服务器负担，又增加 了数据的可靠性和传输速度。 5 搜索引擎技术 数据搜索及查询软件。用于在p 2 p 网络中实现信息检索，必须动态地搜集当前 p 2 p 网络中各个节点的内容，并且要有效地向用户传递。p 2 p 技术使用户能够深度 搜索文档，而且这种搜索无需通过w e b 服务器，也可以不受信息文档格式和宿主设 备的限制，可达到传统目录式搜索引擎无可比拟的深度。g o o g l e 也宣称要采用p 2 p 技术来改进其搜索引擎。 6 文件交换和共享 文件共享是p 2 p 软件最实质的使用宗旨，在众多的p 2 p 软件中所提供的功能也 是多以此为主。这些软件提供了一个大范围文件共享的平台，用户通过它可以与其 它用户交换共享的音乐、视频、图片、软件、游戏等。 3 4p 2 p 网络与网格( g r i d ) 作为分布式运算的不同应用，p 2 p 网络和网格( g r i d ) 技术基本概念非常相似 其最终目的都是资源共享，但两者所采用的技术各不相同。 兰州大学研究生学位论文 g r i d 来自高性能计算，网络资源一般使用超级计算机，集群，专门设备，以及 大规模数据库等。其中安全和性能是g r i d 最为关键问题。为了保证技术的实施还 制定了组织级的协议用于资源共享，安全上基于p k i + x 5 0 9 证书，使用可编程中间 件用于高性能计算。 p 2 p 网络所使用的设备一般大多为个人计算机，数字内容等占软件资源的大多 数。在网络上主要实现资源的发散控制。在p 2 p 网络体系中，每个结点直接连接， 地位平等，彼此相互提供或要求服务。其物理能力可以不要求平等，但它们可以直 接平等地连接起来，以实体( 结点) 的形式加入以增加系统的资源。p 2 p 网络体系中 人人平等，权力分散，允许匿名接入，因而管理是个大问题。 通常可以认为把网络中计算机间主要是直接共享数据( 文件) 的应用叫p 2 p 网 络，而网上计算机间直接共享共用处理能力口qg r i d 运算。在s u n 的 t h ej x t a s o l u t i o nt op 2 p ) 中p 2 p 的定义是，“一种网络模型，其中随操作内容而定，任 何结点可作为服务提供者或客户来操作。”在s u n 的 g r i dc o m p u t i n g ：an e w t e c h n o l o g yf o rt h ea d v a n c e dw e b 中对网格的描述是，“一种分布式运算体系 结构，以便把计算和数据资源作为服务在i n t e r n e t 上提供，很像电在电力网格上 提供一样。”换言之，前者强调平等的资源共享共用，后者强调协同的计算。网格 运算是公用事业运算( u t i l i t yc o m p u t i n g ) 的重要支柱之一。 兰州大学研究生学位论文 一一 第四章基于文件共享的p 2 p 网络性能建模 4 1b t 软件及其应用框架 b i t t o r r e n t 简称“b t ”，是目前最热门的下载方