具有差异化服务的混合对等网络性能分析

张长振, 马占友,*, 刘 琳, 陈 利

(1. 燕山大学理学院, 河北 秦皇岛 066004; 2. 燕山大学里仁学院, 河北 秦皇岛 066004)

0 引 言

对等(peer-to-peer,P2P)网络在通信和资源共享中起着重要的作用。近年来,P2P网络由于其可扩展性和简单、经济高效的模型而变得越来越重要。具有分散文件存储的P2P文件共享系统已经出现,允许对等方共享资源并直接从彼此下载文件。然而,阻碍这些服务成功的一个主要问题是一种称为“搭便车”的行为,在这种行为中,对等方免费享用系统资源,而从不共享任何资源。这类用户的存在会影响服务的健康,因为它们会给其他节点和系统带来麻烦,如延误和资源浪费,降低P2P系统的有效性,加剧网络拥塞,导致系统的不稳定性,影响P2P系统满足其共享和协作的总体目的的能力[1]。Adar等[2]发现Gnutella中66%的对等点是从不分享资源的“搭便车”用户,47%的资源来自前1%的对等点,98%的资源来自前25%的对等点。

为了应对P2P网络中的“搭便车”行为,目前已经研究了许多方法,主要分为4类,分别是互惠策略(对等点优先提供资源给那些曾经提供过资源的对等点)、惩罚策略(对“搭便车”用户施加惩罚来减少“搭便车”行为)、激励策略(设计一种激励机制来鼓励用户共享资源)、信誉策略(这种策略依据对等点之前的信誉来提供资源服务)。每一种策略都有许多学者做了大量的工作。

(1) 互惠策略。Alotibi等[3]为了应对P2P网络中的“搭便车”问题,提出一个可扩展的方案,利用基于点的方法检测“搭便车”用户并限制他们的活动,通过提供下载优先权来奖励共享资源的用户。Ghaderzadeh等[4]提出了一种更智能的方法,其想法是对等点之间分享信息,对等点通过这些信息来选择最佳的对等点来进行资源共享。Zghaibeh[5]提出O-Torrent机制来应对“搭便车”行为。在此机制下,所有对等点只有共享资源才能下载使用系统的资源。

(2) 激励策略。Wu等[6]提出了一种基于博弈论的P2P文件共享激励机制,称为本地激励机制。根据网络中的交易数量和“搭便车”用户百分比,以下载带宽作为衡量标准进行评估。Singha和Singh[7]提出了一种新的激励机制,每个对等点根据自己的贡献获得相应的收益,以此来激励对等点共享资源。Awasthi和Singh[8]提出了一个基于贡献指数的激励策略。

(3) 惩罚策略。Yahaya[9]通过仿真研究了一种线性模型在P2P系统中缓解“搭便车”的有效性。Ojo等[10]利用博弈论提出了一种新的对等辅助流模型,提出了一个奖惩机制,对“搭便车”用户施加惩罚来鼓励资源共享。Manoharan和Ge[11]提出一个扣分策略来应对P2P网络中的“搭便车”行为。

(4) 信誉策略。Alhussain和Kurdi[12]提出了一种信誉管理系统,通过将每个对等方的信誉信息保存到一个链来完成。Marti和Garcia-Molina[13]介绍了信誉系统组件及其属性的分类,并讨论了用户行为和技术约束之间的冲突。Tseng和Chen[14]提出了一种P2P文件共享网络中的“搭便车”用户感知信誉系统,提供了一种简单的方法来减少恶意文件的传播和免费使用。Fan等[15]提出了一种新的信任模型,采用该技术计算信任评级特征向量和推荐矩阵,定义推荐声誉值来评估资源服务行为。Domingo-Ferrer等[16]论证了利用信誉提供激励来补偿负收益,从而使共同效用得以实现。Sanchez等[17]建立了完全分散的P2P共享管理网络和信誉管理协议,解决了影响资源共享的两个主要障碍,即缺乏对匹配机构的信任和隐私问题。

本文提出的差异化服务策略相当于一个惩罚策略。当对等点发出服务请求时,超级节点根据其存储的对等点的历史信誉值,区分“搭便车”用户和资源共享用户,对两类用户提供差异化服务,“搭便车”行为用户被分配给移动节点处理请求,其速率较低,而资源共享用户被分配给固定节点处理请求,其速率较高。目的是增大“搭便车”用户的平均等待时间,从而降低其个人平均收益,鼓励对等点资源共享。为了验证本文所提出的惩罚策略的有效性,本文将在数值实验中对两类对等点的个人平均收益进行对比分析。

对于不同类别服务台的排队系统和休假排队系统的研究,Madan等[18]研究了单重异步Bernoulli休假策略下的M/M/2排队模型,探讨了两种休假方式,得到了模型的稳态方程组。Kumar和Madheswari[19]研究的多重休假下的异步M/M/2排队模型,利用矩阵几何解的方法得到了队长的稳态分布,分析了系统的忙期以及等待时间等指标。王玲等[20]研究了两个不同服务台的M/(Ek,M)/2可修排队系统,通过数值算例分析了服务率,到达率对系统平均队长的影响。金顺福等[21]基于固定节点的延迟修复策略,研究了混合P2P网络中固定节点延迟修复策略的性能分析,利用矩阵几何解方法,进行系统模型的稳态分析。Yu等[22]利用带有多重工作休假、启动器、反馈和N-策略的可修M/M/2排队模型研究了具有阈值激活过程和干扰信号的无线通信网络,并提出降低系统能耗的策略。Ayyappan等[23]研究了单个带有准入控制和伯努利休假的服务台服务两类顾客的问题。Ugochukwu和Onyebuchi[24]研究了中途退出,服务器故障,服务器休假对批量到达排队系统的各种状态的影响。Fan等[25]将休假排队模型应用于区块链系统,研究了区块生成过程中的一些性能指标。Tamrakar和Banerjee[26]研究了单个服务器、无限缓冲区、具有单个和多个休假的批量服务泊松队列,并通过进行数值实验验证了分析结果。Angelika和Abdelhak[27]研究了带有等待和K-变休假的单服务器马尔可夫伯努利反馈排队系统。Niranjan[28]研究了带有休假和状态依赖故障服务台的批量到达和批量服务排队系统。与以上工作不同,本文对服务台数量进行一般化,即将两类服务台的数量拓展到c和d个,以应对“搭便车”行为为目的,建立了M/M/c+d混合P2P网络排队模型。

本文将排队论的方法应用于混合P2P网络,根据用户的历史交易行为和信誉记录,将请求节点划分为两类,对疑似有“搭便车”行为的请求节点提供较低服务率的服务,对资源共享的请求节点提供高服务率的服务,以减少“搭便车”用户的个人平均收益,来应对“搭便车”问题,鼓励用户共享资源。建立了带有负顾客和同步多重工作休假的M/M/c+d排队模型,对混合P2P网络进行建模分析,利用矩阵几何解的方法求解排队系统的稳态分布,构建平均移动节点数量,请求节点个人平均收益等性能指标。使用Matlab 2018a进行数值实验,比较两类请求节点的个人平均收益,验证模型有效性,进行系统收益分析。

1 混合P2P网络与建模

1.1 混合P2P网络

本文所考虑的混合P2P网络由不同的对等簇组成,每个对等簇相当于一个对等点,簇与簇之间通过纯P2P模式相连接,如图1所示,图中的箭头方向表示簇之间发出的请求。每个簇包含一个超级节点,多个固定节点和移动节点。每个固定节点或者移动节点都是一个对等点,它既可以作为请求节点通过所在的簇向其他节点发出服务请求,也可以作为服务节点接收其他节点的服务请求。

图1 纯P2P模式Fig.1 Pure P2P mode

3类节点的具体作用如下:

(1) 超级节点:处理搜索请求,通过分析请求节点的历史数据和信誉情况,将其划分为两类,一类是接受完服务愿意作为服务节点向其他用户提供服务的节点(Ⅰ类请求节点);另一类是接受完服务不愿意作为服务节点而直接离开系统,即有“搭便车”行为倾向的节点(Ⅱ类请求节点)。将有“搭便车”行为倾向的请求节点分配给移动节点服务,将信誉良好的请求节点分配给固定节点服务。超级节点必须拥有足够的内存来存放请求节点的历史数据以及簇内固定节点和移动节点的信息目录,而且负责维护整个簇内的网络结构。

(2) 固定节点:为Ⅰ类请求节点提供高服务率的服务,位于Ⅰ区,数量为c,Ⅰ区带有一个可容纳无限请求的缓冲区。固定节点主要通过固定网络接入,优点是设备性能和网络带宽良好,稳定性高,有较高的服务率;缺点是需要不定时的休假来维持较高的服务率。

(3) 移动节点:为Ⅱ类请求节点提供低服务率的服务,位于Ⅱ区,数量为d,Ⅱ区无缓冲区。移动节点要通过无线网络接入,优点是移动性和灵活性好,几乎不需要休假;缺点是网络稳定性较低,带宽有限,所以服务率较低。

现实中,我们不能使得每一个簇内的超级节点都存储所有用户的历史信息,因为这要求极大的内存,大大增加了系统成本。我们的策略是,由于每一个用户都是优先向相邻的簇发出请求,而且P2P系统中的信息资源具有较大的重复性,所以簇内的超级节点只需要以自己所在的簇为中心,存储邻近一个范围内的用户的历史信息和信誉记录。当用户的请求在邻近的簇内得不到满足时,继续经过邻近的簇向另一个簇发出请求,由于另一个簇内的超级节点可能没有存储这个用户的历史信息,这要求两个簇之间的超级节点共享用户历史信息和信誉情况,这样,超级节点就不需要极大的内存,又能存储所有P2P网络中用户的信息。

图2描述了混合对等网络中每个簇的运行机制,图中的箭头方向表示请求节点的流动方向。

图2 混合P2P网络中每个簇的运行机制Fig.2 Operating mechanism of each cluster in a hybrid P2P network

1.2 模型描述

将每一个P2P网络的簇抽象为一个具有两类服务台的排队系统,把固定节点和移动节点分别抽象为两类不同服务率的服务台,将信誉不同的两类请求节点分别抽象为两类顾客。固定节点数量为c,有无限等待空间,服务时间S1服从参数为μ1的指数分布;移动节点数量为d,无等待空间,服务时间S2服从参数为μ2的指数分布(μ1>μ2>0)。Ⅰ类请求节点和Ⅱ类请求节点的到达间隔T1,T2分别服从参数λ1,λ2的指数分布(λ1,λ2>0)。

(2) 当Ⅰ区固定节点空闲时,固定节点立即进入长度为V的工作休假,休假长度V服从参数为θ的指数分布。当工作休假结束时,若Ⅰ区仍无节点请求服务,则固定节点继续下一个工作休假时间;当工作休期结束时,若Ⅰ区有节点请求服务,则固定节点结束工作休假期,开始正规忙期;若工作休假尚未结束,Ⅰ区已有节点请求服务,则固定节点以较低的速率μ2为Ⅰ类节点提供服务。

(3) 在工作休假期,若Ⅰ区没有空闲的固定节点,但Ⅱ区有空闲的移动节点,则新到的Ⅰ类请求节点直接进入Ⅱ区接受服务;若Ⅰ区有空闲固定节点,则新到的Ⅰ类请求节点在Ⅰ区接受服务。

(4) 系统引入负顾客,相当于干扰节点,可以将一次请求任务结束。当负顾客到达系统时,将一对一地抵消处于正常服务期的Ⅰ区任意一个请求节点,若Ⅰ区无处于正常服务期的请求节点,到达的负顾客自动消失。负顾客只起抵消作用,不接受服务,负顾客到达服从参数ε的指数分布。

假设排队系统的服务规则是先到先服务,到达间隔、服务时间、休假时间等均相互独立。本文主要利用带有负顾客和同步多重工作休假策略的M/M/c+d排队模型分析研究对等网络中的“搭便车”问题。

2 模型分析与性能指标

2.1 模型分析

假设L1(t)表示t时z刻系统中Ⅰ区的请求节点数,L2(t)表示t时刻系统中Ⅱ区的请求节点数,J(t)表示t时刻Ⅰ区固定节点所处的状态。

(1)

根据模型的描述可知,三维马尔可夫过程{(L1(t),L2(t),J(t)),t≥0}是一个拟生灭过程(quasi-birth-and-death process, QBD),有状态空间Ω={(0,j,0)|0≤j≤d}∪{(i,j,k)|i≥1,0≤j≤d,k=0,1}。

将状态按字典序进行排列,系统的状态转移率矩阵有如下分块形式:

(2)

其中,A00,A01,A10,Aii(1≤i≤c-1),A1,Ai,i-1(2≤i≤c),Acc,Ac,c+1分别代表水平间的状态转移率,为了简便表示矩阵,定义如下符号:

Q矩阵的各个子块矩阵具体如下:

(3)

(4)

(5)

当1≤i≤c-1时,

(6)

(7)

当2≤i≤c时,

(8)

(9)

(10)

其中,A0,0是d+1维的方阵,A1,0是(2d+2)×(d+1)维的矩阵,A0,1是(d+1)×(2d+2)维的矩阵,其余的子块矩阵均是2d+2维的方阵。

当马尔可夫过程{(L1(t),L2(t),J(t)),t≥0}正常返时,稳态分布有如下形式:

QBD{(L1(t),L2(t),J(t)),t≥0} 正常返的充分必要条件是矩阵方程:

R2Ac,c-1+RAc,c+Ac,c+1=0

(11)

有最小非负解R,且谱半径SP(R)<1,随机阵

(12)

有左零向量。当QBD正常返时,稳态分布为

(13)

其中,e1和e2分别是d+1维和2d+2维且所有元素均为1的列向量。

上述结论的证明过程运用了矩阵几何解方法,具体证明过程可参见文献[29-31]。

算法 1 迭代算法步骤 1 对系统参数定义初始值η(η=10-10),c,d,ε,θ,λ1,λ2,μ1,μ2,设置率阵R=0步骤 2 输入 Ac,c-1,Ac,c,Ac,c+1步骤 3 定义 Rn=RR=-(R2Ac,c-1+Ac,c+1)A-1c,cRn+1=R步骤 4 如果 Rn+1-Rn∞>η 返回步骤3否则 进入步骤5步骤 5 R=Rn+1

2.2 性能指标

(1) Ⅰ区请求节点平均队长为

(14)

(2) Ⅱ区请求节点平均队长为

(15)

利用排队理论中的Little公式[32-33]可得

(3) Ⅰ区和Ⅱ区请求节点平均逗留时间为

(16)

(4) Ⅱ类请求节点到达后消失的概率为

(17)

(5) Ⅰ区无空闲,Ⅰ类请求节点到达后等待的概率为

(18)

3 数值实验

通过迭代算法得到R2Ac,c-1+RAc,c+Ac,c+1=0的最小非负解R,然后利用稳态分布方程组求解,可以得到πi,j,k的数值结果,进而可以得到混合P2P系统的各项性能指标。在实际生活中,性能指标会随参数的变化而变化。利用Matlab 2018a给出数值例子来刻画性能指标随系统参数的变化趋势。

3.1 系统性能分析

图3反映了当μ1=5,μ2=1,c=6,θ=1,p=0.6,ε=1时,Ⅰ区请求节点的平均等待时间E(W1)随工作休假参数θ和固定节点数量d变化的趋势。当d固定时,随着θ的逐渐增大,E(W1)逐渐减小;当θ固定时,随着d的逐渐增大,E(W1)逐渐减小。这是因为θ越大,Ⅰ区服务台工作休假的时间越短,正常工作时间越长,因此请求节点等待的时间越短;d越大,可供Ⅰ类请求节点选择的服务台数量越大,等待时间就越短。

图3 E(W1)与d和θ的关系Fig.3 Relationship of E(W1) with d and θ

图4反映了当μ1=5,μ2=1,c=6,d=6,θ=1,p=0.6,ε=1时,Ⅱ区请求节点的平均队长随两类请求节点到达率变化的趋势。当Ⅰ类请求节点和Ⅱ类请求节点的到达率增大时,Ⅱ区请求节点的平均队长逐渐增大。这是因为当Ⅰ区无空闲固定节点时,Ⅰ类请求节点会以概率1-p进入Ⅱ区接受服务,所以Ⅰ类请求节点和Ⅱ类请求节点的到达率增大都会使得Ⅱ区请求节点的平均队长增大。

图4 E(L2)与λ1和λ2的关系Fig.4 Relation ship of E(L2) with λ1 and λ2

当c=6,d=5,λ1=6,λ2=3,μ1=10,μ2=5,θ=4,p=0.6时,观察负顾客的到达率变化对系统性能指标的影响。从表1可以看出随着ε的不断增大,E(W1),E(L1),E(W2),E(L2)分别不断减小,但Pd没有明显的变化。这是因为负顾客的到达会抵消一个Ⅰ类请求节点,而Ⅰ类请求节点会以一定概率进入Ⅱ区接受服务,所以E(W1)等4个指标都会随负顾客到达率的增大而减小。而负顾客只抵消正常工作状态的固定节点,不抵消移动节点,所以Pd随ε改变,没有明显变化。

表1 ε对系统性能指标的影响

3.2 模型有效性验证

本文为应对P2P网络中的“搭便车”行为,提出一个惩罚策略,对“搭便车”行为用户和资源共享用户提供不同服务率的服务,本节对此惩罚策略进行有效性验证。

假设一个请求节点完成一次服务请求之后获得的个人回报为M,请求节点在系统内单位平均逗留时间的时间成本为F,则请求节点完成一次服务请求所获得的个人平均收益有如下表达式:

U1=M-F·E(W1)

(19)

U2=M-F·E(W2)

(20)

其中,U1表示Ⅰ类请求节点的个人平均收益函数,U2表示Ⅱ类请求节点个人平均收益函数。当c=d=7,λ1=λ2=2,ε=3,p=1,μ1=2,μ2=0.5,M=20,F=15,即,两类请求节点的到达率相等,但固定节点和移动节点的服务率不同时,观察随工作休假参数θ变化,两类请求节点的个人平均收益U1,U2的大小。由图5可以看到,随着工作休假参数的增大,两类请求节点的个人平均收益均逐渐增大。这是因为如果工作休假参数增大,平均休假时间减小,服务节点处于工作状态的概率增大,因此请求节点的平均逗留时间减小,通过收益函数的表达式可知,请求节点的个人平均收益与平均逗留时间负相关。因此,两类请求节点的个人平均收益增大。

图5 U1,U2与θ的关系Fig.5 Relationship of U1,U2 with θ

另外,Ⅰ类请求节点的平均收益函数曲线始终在Ⅱ类请求节点的平均收益函数的上方,即,无论哪个参数水平,Ⅰ类请求节点的平均收益始终大于Ⅱ类请求节点的平均收益。为了看到准确的收益对比,表2给出了两类请求节点个人平均收益的数值比较。表2显示,无论在哪一个工作休假参数水平下,Ⅰ类请求节点的个人平均收益相比于Ⅱ类请求节点的个人平均收益,至少高出20%。因此,本文所建立的应对“搭便车”行为的模型可以有效降低“搭便车”用户的平均收益,惩罚作用明显。

表2 U1,U2的具体值

4 系统收益分析

本节讨论P2P系统的收益问题。假设L表示P2P系统服务完一个节点后获得的平均收益,C表示单位时间内P2P系统服务一个节点的平均成本,Cp表示每个节点在正规忙期内的损失,Cd表示一个Ⅱ类请求节点消失后带来的潜在损失,则P2P系统的收益函数可以表示为

(21)

其中,

为了保证该P2P系统盈利,需要满足

即

图6反映了当λ2=2,μ1=10,μ2=5,c=6,d=5,p=0.6,ε=3,L=22,C=5,Cp=14.1,Cd=5时,系统收益随λ1和θ变化的趋势。当θ固定时,随λ1逐渐增大,收益U逐渐减小,最终小于零;当λ1固定时,收益U随θ的增大而变大。这是因为λ1增大,但若服务台服务率相对较小,有一部分请求节点到达后离开,造成的潜在损失加大;而当θ增大时,系统的休假时间减小,正常工作时间增大,给系统带来的收益增大。所以,为了提高系统收益,一方面需要使服务率相对于到达率较大,从而降低请求节点离开的概率,另一方面需要降低系统的休假时间。

图6 U与λ1和θ的关系Fig.6 Relationship of U with λ1 and θ

为了保证系统收益大于零,需找到使得系统收益大于零的点。由Matlab 2018a可以得到,当λ1<19,θ=5;λ1<20,θ=6;λ1<20,θ=7;λ1<21,θ=9时,P2P系统收益大于零。

5 结 论

P2P网络中的“搭便车”行为严重影响了系统的效率和稳定性。本文提出一个惩罚策略来应对“搭便车”行为,即根据对等点的历史信誉值,将其分为两类,对其提供差异化服务,减少“搭便车”用户的个人收益。利用M/M/c+d排队模型,对此混合P2P网络进行排队建模,使用矩阵几何解方法求解排队模型的稳态分布,通过数值实验验证了模型的有效性。实验结果显示,无论在哪一个工作休假参数水平下,Ⅰ类请求节点的个人平均收益相比于Ⅱ类请求节点的个人平均收益,至少高出20%。最后通过构造系统收益函数,研究了混合P2P系统的收益,得到保证混合P2P系统收益的参数阈值。本文将排队建模方法应用于P2P网络,分析P2P网络中的实际问题,为以后的研究提供了思路。

对于P2P中的“搭便车”现象,需要提出更加合理有效的“搭便车”行为划分方法,结合排队理论,构造更加有创新性的P2P网络系统。针对此问题，我们将在以后的工作中继续研究。