流随机Petri网在P2P文件共享传输时间分布中的应用分析

理论计算机科学电子笔记128（2005）79-99www.elsevier.com/locate/entcs流随机Petri网在计算P2P文件共享传输时间分布中的应用R. Gaeta，M. Gribaudo，D. 马尼尼湾Sereno1，2Dipartimento diInformaticaUniversit`adiTorinoCorso Svizzera，185，1049都灵，意大利摘要本文提出了一种应用流体随机Petri网（FSPN）的形式主义的点对点（P2P）文件共享应用程序的传输时间分布的分析。资源的转移遵循成功的搜索;转移时间主要受网络特性、应用特性、资源特性和用户行为的支配。建议的分析建模技术考虑到所有这些方面，并提供一个估计在已经执行了对给定资源的搜索之后的传输时间分布的估计。一些数值结果证明了所提出的技术的灵活性和潜力。关键词：对等系统，文件共享应用，流体随机Petri网。1介绍文件共享应用程序在互联网上产生的流量越来越大。这些应用程序基于对等（P2P）范例，其中应用程序的组件可以在请求和提供服务时充当客户端和服务器。到目前为止，已经开发了几种P2P文件共享应用，例如，Napster、Gnutella、Freenet、Kazaa等。1这项工作得到了意大利研究部长（MIUR）在项目Perf（FIRB）范围内的部分支持2Email：{rossano，marcog，m ani ni，m att eo}@ di. 我是。它1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.01.01480R. Gaeta等人理论计算机科学电子笔记128（2005）79对等体充当服务器，接受并转发用于搜索资源（文件）的传入查询，提供对搜索查询的响应，并在客户端选择作为客户端的对等体在搜索资源和从服务器传输（下载）资源之间交替在成功搜索之后，P2P应用向客户端提供持有所请求资源的副本的对等体的列表;取决于特定的P2P应用，包括描述对等体的附加信息，诸如服务器与其互联网服务提供商（ISP）之间的带宽、正在使用该服务器的客户端的数量以及客户端可以用于其服务器选择策略的其他信息。搜索和转移阶段都可能是耗时的。搜索时间主要受特定P2P应用的信令、路由、搜索协议等体系结构特征的影响。相比之下，资源的传输时间主要由网络费用决定。特性（最后和第一英里带宽3、连接对等点的路径上的延迟）、应用程序特性（允许的并发下载和上传的最大数量）、资源特性（对等点作为所请求资源的流行度、要下载的资源的大小、下载期间所选对等体上的竞争负载的函数来保持所请求资源的副本）以及用户行为（当多个对等体保持所请求资源的副本在本文中，我们开发了一种分析建模技术，用于分析P2P文件共享系统，目的是提供与给定资源的传输阶段相关的服务质量（QoS）用户感知度量;特别是，我们提供了一种估计传输时间分布的方法。这种分析是通用的（因为它可能适用于不同的P2P文件共享架构），并且足够灵活，可以适用于其他P2P应用程序的分析，例如，流媒体内容分发、车辆交通信息管理。我们开发了一种基于流体随机Petri网（FSPN）[12，24]和组合分析的混合建模技术。联合使用不同的建模范式，使我们能够捕捉几个功能，主导资源转移时间，以及获得一个有效的模型解决方案。我们开发的模型的参数是从文献中提出的P2P应用程序本文的概要如下：在第二节中，我们简要总结了P2P系统分析模型的相关工作，包括描述我们利用测量工作来匹配我们开发的模型的参数。第3节总结了FSPN的特点3 连接对等点到ISP的通道的带宽。R. Gaeta等人理论计算机科学电子笔记128（2005）7981形式主义第4节讨论了控制资源传输时间的主要问题，这些问题是由我们的分析建模技术捕获的，在第5节中详细说明。第6节介绍了模型分析的初步结果，而第7节得出结论，并概述了当前工作的几个发展。2背景及相关作品P2P模式最近引起了科学和学术研究人员的关注，因为文件共享应用程序用户的数量呈爆炸性增长，这些用户产生了当今互联网流量的很大一部分。基于P2P的应用提出了具有挑战性的研究问题，这些问题涉及分散体系结构中的可靠性、可扩展性、资源组织、索引、尺寸、发现和协调。在文献中已经提出了几个基于测量的P2P应用程序的评估。[19]中的工作是P2P系统行为的第一个定量评估之一，它基于“爬虫”来提取Gnutella应用级网络的拓扑结构，并得出结论，尽管Gnutella不是一个纯粹的幂律网络，但它的配置具有幂律结构的优点和缺点，例如，对随机对等故障的恢复能力。在[22]中，对P2P传输及其对底层网络的影响进行了系统的表征;提出了一种用于对P2P传输进行大规模测量以从大型ISP中的多个路由器收集数据 的 新 方 法 。 分 析 了 三 种 流 行 的 P2P 系 统 ： FastTrack 、 Gnutella 和DirectConnect。结果显示，IP地址、IP地址和自治系统之间的流量分布存在在[21]中，一项基于测量的研究提供了参与两个流行的P2P文件共享系统（如Napster和Gnutella）的最终用户主机的精确特征。此特征考虑了这些主机之间的瓶颈带宽、整个互联网、向这些主机发送数据包的IP级延迟、主机连接和断开系统的频率、主机共享和下载的文件数量以及这些方面之间的相关性。这项研究的结果表明，有显着的异质性，在同行的带宽，可用性，传输速率和同行的行为。[10]中的工作提出了现代P2P多媒体文件共享Kazaa中基于跟踪的工作负载分析。结果表明，P2P文件共享工作负载由与经典Web应用程序截然不同的进程驱动。它还表明，有显着的地方，82R. Gaeta等人理论计算机科学电子笔记128（2005）79Kazaa的工作负载，因此有大量的机会进行缓存，以减少带宽消耗。基于模型的P2P应用性能评估目前还处于起步阶段，因为考虑P2P网络的分析模型还很少。在大多数情况下，分析是通过广泛的离散事件模拟。在[25]中开发了一个基于年龄相关分支过程的分析模型，其中通过考虑瞬态机制来分析P2P文件共享应用程序的服务容量，以表征此类系统处理突发传输的能力。在[7]中部署了一个数学模型来探索和说明P2P文件共享系统的基本性能问题。该模型应用于三种不同类型的体系结构（集中式索引，分布式索引与hashing定向查询），它用于分析有关性能的重要方面，如系统扩展，免费加载器，文件流行度和可用性。在[13]中，引入了一种基于随机图的模型来研究P2P社区（如Gnutella或Freenet）的演化;该模型用于分析基本属性，如网络中给定节点的可达性。[15]中提出了另一种模拟方法，其中开发了一种工具，可以在代表性的Internet拓扑结构上模拟P2P网络。在[11]中，开发了一个可扩展和可伸缩的P2P仿真环境框架，该框架可以构建在现有的分组级网络仿真器之上。在[14]中，作者对文件共享网络的请求-响应过程进行了建模，并获得了三个性能参数（延迟，抖动和丢失概率）的解析表达式，作为网络中资源索引数量和查询超时值的函数。在[3]中的工作是少数几个使用Webuid模型来分析基于P2P的应用程序的例子之一。提出并研究了一种用于Squirrel协作缓存系统性能分析的代理流模型。为了应对大量用户随机加入和离开缓存系统，各个节点的请求流被近似为一个缓存流。由此产生的随机流模型在数学上是易于处理的，并提供了一个简单和低复杂度的计算命中概率的过程。R. Gaeta等人理论计算机科学电子笔记128（2005）79833流体随机Petri网的形式化随机流模型是一类分析模型，最近引起了许多研究人员的注意，用于复杂通信系统的性能评估（例如，参见[16]）。流体变量可用于近似离散变量，以解决在分析基于离散状态的模型时通常发生的状态空间爆炸问题。在最简单的一阶流体模型中，流体流动速率是恒定的，并且一阶微分方程组被写入以表征模型[1]。在[6]中，这个简单的一阶模型被扩展到考虑依赖于流体的湍流速率在[23]中提出了基于幂展开方法的一阶常速率流体模型的有效瞬态分析方法流体随机Petri网（FSPN）在[24，12]中引入，主要目的是提供离散状态系统的可行近似，其中要考虑的对象（客户，数据包，任务，工件等）的数量往往变得太大，无法用随机Petri网（SPN）常见的离散状态方法来处理。该模型的基础是定义两个不相交的地点集合：携带非负整数数量的标记的离散地点和由实非负数表征的连续地点。连续的地方可以被物理解释为水库，相关的实数表示水库中的液位。这就是为该模型指定FSPN名称的原因。流体是由沿着特殊的流体弧的流体过渡和流动生成的。流率可以是离散位置中的令牌分布和连续位置中的令牌水平的函数。图1中描述了形式主义的所有原语的图形表示。FSPN可以通过多种方式解决。在[2，8]中，已经提出了FSPN形式主义的模拟解决方案。相反，分析解决方案通过在混合离散和连续状态空间上创建适当的连续时间马尔可夫链（CTMC）来计算FSPN模型的性能指标。在这种情况下，必须求解以获得基本随机过程的稳态或瞬态解的方程是偏微分方程。这种方程组的解不是一件容易的事，文献中已经提出了各种数值技术，如半离散化[244P2P网络我们提出了一种分析建模技术的传输时间分布的估计，即，该阶段在成功的搜索阶段之后开始84R. Gaeta等人理论计算机科学电子笔记128（2005）79离散位置定时跃迁离散弧令牌立即过渡抑制弧流动场所流体流体过渡弧流体Fig. 1. FSPN形式主义一般来说，对于资源转移阶段，所有P2P应用程序都提供持有所请求资源的副本的对等体的列表。 在下文中，我们将请求资源的对等体表示为客户端，将持有所请求资源的副本的对等体表示为服务器。对于每台服务器，P2P应用程序还提供额外的信息，例如服务器与其ISP之间的带宽，使用该服务器的客户端数量以及帮助客户端选择服务器下载资源的其他信息。在下文中，我们讨论影响转移阶段持续时间的参数• 网络特性：从服务器下载文件的速率取决于客户端和所选服务器之间的瓶颈带宽、可用带宽以及连接两个对等端的路径上的延迟。对等体和ISP之间的连接带宽对传输阶段有明显的影响。在[21]中，Napster和Gnutella P2P应用程序的基于测量的结果表明，在带宽、延迟和其他特性方面存在显著的异质性，这些特性在系统的对等体之间变化了几个数量级。表1报告了在[21]中给出的用户带宽的百分比。我们的调查与特定的P2P应用程序无关，但它们可以应用于不同的P2P文件共享系统。然而，我们使用Napster和Gnutella的结果来设置我们模型中的一些参数。[21]中给出的结果的这种使用可能被认为是不适当的扩展，但是针对Napster和Gnutella导出的瓶颈带宽结果非常相似，即使这两个P2P应用程序基于不同的架构。重要的是要指出，表1中报告的措施，我们作为我们实验的基础，是在2002年提出的，这些措施代表了一个合理的R. Gaeta等人理论计算机科学电子笔记128（2005）7985带宽%14.4kbps的百分之四28.8 Kbps百分之一33.6 Kbps百分之一56 Kbps百分之二十三64 Kbps百分之三128 Kbps百分之三DSL百分之十四电缆百分之四十四T1百分之五T3百分之二表1用户带宽的分布（来自[21]）最后一英里的连接。趋势是向高速带宽连接，然后本文中提出的结果应被视为一种最坏情况下的分析。• 应用特性：在客户端选择一个服务器（或在并行下载的情况下选择多个这些带宽波动主要是由于所选服务器上的负载变化，也取决于并发上传/下载的最大数量一般来说，P2P应用程序在下载资源的不同客户端之间实现共享带宽策略：在某些情况下，服务器在客户端之间平等地共享可用的下载带宽，在其他情况下，共享策略取决于一些参数，这些参数说明了客户端的参与程度。客户端下载所请求文件的速度还取决于文件可以从多个不同的服务器上以片段或“块”下载的可能性• 资源特性：要下载的资源的大小对传输时间的分布有明显的影响。P2P应用的基于测量的分析（例如参见[10，20]）表明，P2P和WWW传输之间的典型资源大小存在实质性差异。这些论文中提出的措施显示了三个突出的区域：小于10 MB的小型资源，通常是MP3文件，中等大小的资源，对应于中小型视频文件的10到100 MB，以及对应于大型视频文件的超过100 MB的大型资源流行度对传输速率的影响是非常明显的。如果客户端正在寻找一个非常流行的资源，那么这个资源的副本由具有高速连接带宽的服务器持有的概率高于搜索“稀有”资源的情况。另一方面，持有非常流行的资源的服务器86R. Gaeta等人理论计算机科学电子笔记128（2005）79过载（因为有许多客户端需要其资源）随着资源流行度而增加。• 用户行为：当多个服务器持有所请求资源的副本时，这个问题很重要选择可以基于具有最快连接的服务器、具有最低负载的服务器，或者可以是随机选择。5建模技术我们开发的建模技术旨在计算当客户端（我们表示为标记客户端）行为如下时下载文件所需的时间分布：在搜索给定资源（文件）之后，客户端选择服务器来传输资源，并且一旦下载终止就离开系统。建模技术没有明确考虑搜索阶段，并假设此搜索的结果是持有资源副本的对等体的数量。5.1建模假设和系统参数我们开发的建模技术考虑了第4节中描述的几个控制传输时间的系统参数：网络特征（最后和第一英里带宽），应用程序特征（允许并发下载和上传的最大数量），资源特征（持有所请求资源副本的对等体数量，作为其流行度的函数，要下载的资源大小）和用户行为（当多个对等体持有所请求资源副本时，此外，建模技术是在以下假设下开发的• 一个资源的流行度是拥有一个副本的对等点的数量，我们用N表示。我们假设所有N个服务器不仅持有资源的副本，而且可供下载，即，下载请求既不排队也不被拒绝。• 我们不考虑对等体的可用性问题，也就是说，我们假设服务器在资源下载时间的所有持续时间内都是可用的，并且只有当客户端完全下载资源时，会话才会结束。• 底层IP网络不拥塞，即，网络传输时间由对等体的第一英里和最后一英里特性支配。这个假设可以通过对模型R. Gaeta等人理论计算机科学电子笔记128（2005）7987我们开发了一种用于解决从客户端到服务器的传输时间的可变性的方法• 服务器的操作带宽等于其第一英里带宽，即，在资源上载期间，服务器不执行下载。另一方面，客户端在传输阶段期间将其所有带宽专用于资源的下载，即，在传输阶段，客户端不允许上载。• 资源的下载不是以从不同服务器并行下载较小块的方式组织的。• 服务器不区分客户端，即，它均等地共享其所分配的带宽。• 我们假设一些系统参数是对等带宽的函数特别是，我们假设服务器允许的并发上传的最大数量被定义为其带宽的函数。此外，到达对等体的上传的平均数量被假定为也是其带宽的函数。该假设基于[19，21]中公布的可用测量，该测量将该系统参数表征为对等带宽的函数。5.2定义和符号本节介绍我们使用的符号。我们对随机变量和函数都使用了random，值使用random，集合使用书法风格。特别是• B={ 14.4 Kbps， 28.8 Kbps， 33.6 Kbps， 56 Kbps， 64 Kbps， 128Kbps， DSL， Cable， T1， T3}表示将对等体连接到其ISP的所有可能的可用带宽的集合;• N表示给定资源的流行度，即，持有资源副本的对等体的数量;N的范围是正自然数的集合• SB是一个随机变量，表示被标记的客户端选择下载所请求资源的对等体的带宽;在第5.5节中，我们提出了一种计算其在N上的条件分布的技术;• CB表示标记的客户端带宽。SB和CB的范围是离散集合B;• S表示资源大小（单位：MB）;• K：B →IN表示服务器允许的最大并发下载次数• LT表示到达服务器的上传请求的平均数量，88R. Gaeta等人理论计算机科学电子笔记128（2005）79W：B →[0，1]表示带宽相关权重，L：B →IR表示作为对等带宽的函数的上传请求的平均数量L（b）=LT·W（b）。5.3FSPN模型我们在本节中描述的模型是指变量CB、SB和S的特定实例，我们分别用cb、sb和s表示。我们的方法的基础是开发一个FSPN模型，该模型表示为标记客户端的请求提供服务的服务器; FSPN模型从标记客户端启动的那一刻起捕获其活动的时间演变下载直到完成。它还表示其他客户端的并发下载干扰，其结果是在标记客户端的可用带宽中引入波动。服务器由图2中描述的FSPN模型表示。定时转换请求到达对请求的到达进行建模，并且其速率等于L（sb）。由位置选择、阶段1、阶段2、结束服务、立即转换选择1、选择2、终止服务和定时转换服务1、服务2组成的子网对两阶段超指数服务进行建模，并且对于每个有形（离散）状态m j，我们将位置阶段1和阶段2中的令牌之和表示为I j，其表示与标记的客户端服务交互的请求。 Place AVAILABLE表示服务器可以容纳的请求数。这个模型有一个覆盖所有离散空间的P-半连续流.这些地方的标记之和等于K（sb）−1。Fluid placeTRANSFERRED表示由标记的客户端传输的 流体转换传输对文件传输进行建模;其流速f是服务中的客户端数量的函数，即，（一）. SBf（Ij）=最小IΣ，cb对于每个有形（离散）状态m j。j+1min函数考虑到传输速率受到最低带宽的限制;以这种方式，实际的带宽速率取决于客户端带宽和服务器的可用带宽（这反过来又取决于使用服务器的对等端的瞬时数量）。请注意，在f的定义中，通过将系统中的客户端数量（等式（1）中的Ij+ 1）加1来考虑标记的客户端通过这种方式，我们只考虑第一英里和最后一英里的带宽，忽略了底层网络。选择这种特定的服务器活动建模源于提供下载会话时间分布统计数据的可用度量[10特别是，这项研究强调，会议时间R. Gaeta等人理论计算机科学电子笔记128（2005）7989表现出高度的可变性（由于资源大小的巨大异质性）;因此，无限服务器策略的超指数服务时间是解释这些现象的最简单选择。可用K（sb）-1L（sb）选择1联系我们1售后服务STAGE_1服务_1请求到达联系我们第二阶段服务终止服务12transfer TRANSFERREDf（Ij）= min（sb /（Ij +1），cb）图二、 用于计算传输时间分布的服务器的FSPN模型表示Ft（t|sb，cb，s，π 0）。由于我们假设转换请求到达的服务速率和位置可用的初始标记取决于服务器带宽sb，并且转换速率函数f（等式（1））取决于sb和客户端带宽cb两者，所以FSPN模型的瞬态解可以被认为是这两个输入参数的函数。使用[9，12]中描述的技术分析图2这些技术分别考虑模型的离散和连续部分。特别是底层马尔可夫链描述的离散组件的模型是从FSPN。由于构成模型的定时转换的转换速率是恒定的，因此该基础马尔可夫链可以由单个恒定矩阵Q表征。在对角矩阵R中考虑了微流体相互作用，对角矩阵R的元素表示每个离散状态下的实际微流体速率，即，在每个离散状态mj中计算的等式（1）中定义的函数f的值。请注意，在这个特定的例子中，潜在的随机过程是马尔可夫奖励模型，因为只有正的随机流率存在。对于这类模型，存在专门和有效的技术（例如参见[4，5，17，18]）。尽管如此，我们还是选择使用[12]由于其简单性，并且允许可能需要标准奖励模型中不包括的特征的可能的未来扩展取决于流速。特别是，我们正计划使用依赖于连续部分的缓存速率来表示占已下载资源百分比的策略。如果我们记为πj（τ，x），则有x个单位的流体的概率密度90R. Gaeta等人理论计算机科学电子笔记128（2005）79.在离散状态mj中的时间τ，即，在状态mj中，在时间τ已经下载资源的x个字节的概率，则根据[9]中给出的结果，我们可以写为：（二）τ π（τ，x）τ+τ π（τ，x）阿克斯R=πQ，其中π（τ，x）是其分量对应于πj（τ，x）的向量。文件传输时间取决于传输开始时服务器上竞争对等体的数量。为了考虑这一影响，我们修改了模型：我们将图2所示的FSPN的初始标记设置为模型参数，表示为π0。参数π0是FSPN的状态空间上的概率分布（对应于标记mj的向量π0的分量表示为π0（mj））。由于对于任何状态mj，f（Ij）>0，并且由于该位置是无界的，我们不需要任何边界条件，而初始条件是：π（0，x）=δ（x）π0，其中δ（x）是狄拉克δ。当考虑完整的服务器模型时，矩阵Q和R以及向量π0取决于模型参数。特别地，矩阵Q和初始概率向量π0仅取决于所选择的服务器带宽sb，而矩阵R取决于服务器和客户端带宽两者。通过这些假设，我们可以将方程（2）的解表示为对于参数sb、cb和π0的给定组合的π（τ，x，sb，cb，π0）。在小于t秒内下载了s个字节的概率等于在时间τ=t下载了至少s个字节的概率，计算如下：（3）F t（t|sb，cb，s，π0）=.不好意思.π<$（τ，x，sb，cb，π0）dx..S、τ=t当reπ<$（τ，x，sb，cb，π0）=π（τ，x，sb，cb，π0）1时，that是s，π<$（τ，x，sb，cb，π0）是与离散态无关的量子态能级的概率密度，1是a一个向量，其分量数等于模型的离散状态数。5.4消除对初始负载概率F t（t|sb，cb，s，π0）取决于服务器模型的初始状态（即，π0）时，标记的客户端开始其下载。这种依赖性是至关重要的，因为初始状态可以对整个下载时间分布产生重大影响，特别是在考虑短文件时。为R. Gaeta等人理论计算机科学电子笔记128（2005）7991例如，考虑使用DSL连接从DSL服务器下载112 KByte JPEG图像所需的时间。图3表示当标记的客户端开始文件传输时，服务器上不同数量的竞争请求的传输时间分布（表3中总结了使用的模型参数）。在长文件的情况下，初始载荷的影响不太明显，因为离散模型达到稳态。 很容易注意到，当没有其他对等端干扰文件传输时，平均下载时间比有4个其他对等端访问服务器时短5倍以上。不同服务器初始状态的影响10.80.60.40.200 5 10 15 20 25时间（秒）图三.当标记的客户端开始文件传输时，传输时间的分布是竞争客户端数量的函数。为了获得当标记的客户端开始下载时去除对初始状态的依赖的传输时间的分布，我们必须正确地表征带宽为sb的服务器的概率向量π0。对于π0的计算，我们考虑图2中的FSPN，其中不包含带标记的客户端，此时我们不区分带标记的客户端和其他客户端。客户.我们计算该模型的稳态分布，并使用它来确定π0。We表示图2的FSPN的改进版本的静态方向矢量，假定服务器的带宽等于sb。在考虑完整模型时，只有在至少有一个可用令牌的情况下，才能接受标记的客户端。我们使用这个假设通过归一化π 0来计算π0 ，排除服务器拒绝标记的客户端请求的情况（即，忽略状态mj，使得I j= K（sb））。以这种方式，概率向量π0的初始载荷= 4初始载荷= 3初始载荷= 2初始载荷= 1初始载荷= 0F t（t| sb，cb，s，0）92R. Gaeta等人理论计算机科学电子笔记128（2005）79对应于状态mj（表示为π0（mj））可以计算为ππ（mj）（四）π0（m j）=π。（mh）mh：Ih1，和>：1ifn=1，P（SB = sb|N = n-1）= 0如果n = 1，XP（SB

下载后可阅读完整内容，剩余1页未读，立即下载