BitTorrent激励机制对性能的影响分析与改进

PAGE19PAGE2BitTorrent激励机制对性能的影响分析与改进**本课题得到国家自然科学基金（60803148）、国家自然科学基金（60973124）、教育部高校博士点科研基金（20102302110036）、中央高校基本科研业务费专项资金资助（HIT.NSRIF.2010.047）资助。李治军，1977年生，男，博士，副教授，主要研究领域为对等网络，传感器网络，普适计算，手机感知，操作系统。联系方式e-mail:lizhijun_os@，中国计算机学会会员李治军,姜守旭,李晓义（哈尔滨工业高校计算机科学与技术学院哈尔滨150001）摘要激励机制tit-for-tat和optimisticunchoking是使BitTorrent系统得以良好工作的一项核心机制.对于这一机制,文[7]的分析结果表明“节点公正度和文件下载时间之间存在trade-offs”,也即节点选择的激励策略会影响其文件下载时间,因此就有必要定量揭示激励机制对BitTorrent文件下载效率的影响.另一方面,博弈是分析BitTorrent时常用的方法,即节点会以自身利益的最大化为目标来对其激励策略的选择进行博弈.相比抽象的公正性(是目前BitTorrent博弈分析中最常使用的效用函数)而言,使文件下载时间最小化才是BitTorrent节点最想达到的优化目标,因此以文件下载时间为效用的博弈更符合实际,也更全面(本文的分析结果表明本文提出的博弈蕴含了以往的以公正性为效用的博弈).为了形式的建立和分析本文提出的博弈,本文首先用马尔可夫模型定量的分析了BitTorrent激励机制对系统产生的效果;然后在此基础上用fuild模型分析了激励机制下的文件传输结构,并用概率手段揭示了在这一传输结构下最小化文件下载时间的条件;接下来在综合上述分析结果的基础上得出达到系统纳什平衡时各类节点采纳的激励策略;最后本文将理论讨论结果实现为一个简称为AIPS的BitTorrent自适应激励协议.模拟实验结果表明本文提出的AIPS较现有的BitTorrent激励协议能明显的提高文件共享系统性能.关键词BitTorrent，激励机制，马尔可夫分析，fluid分析，纳什平衡，自适应激励中图法分类号：TP393.0TheAnalysisandImprovementoftheIncentiveMechanisminBitTorrentLiZhijun,JiangShouxu,LiXiaoyi（SchoolofComputerScienceandTechnologyinHarbinInstituteofTechnology,Harbin,150001）AbstractIncentivemechanisms,i.e.tit-for-tatandoptimisticunchoking,arekernelmechanismsforthefavorableoperationoftheBitTorrentsystems.Forsuchmechanisms,theanalysesin[7]showthatthereisatrade-offsbetweenthenodes’fairnessandthefiledownloadtime,thatis,theincentivestrategieschoosedbythenodeswillinfluencethefiledownloadtime.Therefore,itisabsolutelynecessarytodepictquantitativelytherelationshipbetweenthefiledownloadefficiencyandtheincentivemechanismsforBitTorrent.Ontheotherhand,theanalysesbasedonthegametheoryarefamiliarinBittorrentandthenodesinBittorrentwilladapttheirincentivemechanismtomaximizetheirutilities.However,incontrasttotheabstractfairnesswhichistheutilitycommonlyusedinnowadaysgamesinBitTorrent,thefiledownloadtimeismorepreferableutilityfortheusersinBitTorrent.Therefore,thegamewiththe“filedownloadtime”asitsutilityprovidedinthispaperismoreactualandmorecomprehensive(theresultsobtaindinthispapershowthatthegameprovidedinthispapercontainsthepreviousgamewiththefairnessasitsutility).Toformallyextablishandanalyzethegameprovidedinthispaper,firstly,theMarkovmodelisusedtoquantitativelydepicttheinfluenceofincentivemechanismonBitTorrent;secondly,thethefiletransferfeaturesarediscoveredbasedonthefuildmodel,andtheconditionstominimizethefiledownloadtimeareinferredfurtherbasedonthetransferfeatures;thirdly,thegameisprovidedanditsNashequilibriumisprovidedalso;finally,aself-adaptiveincentivemechanismcalledAIPSforBitTorrentisprobidedbycombiningalltherelatedresultsinferredfromthemodels.SimulationsshowthattheAIPScanimprovetheperformanceoftheBitTorrentremarkably.Keywords:BitTorrent;Incentivemechanism;Markovanalysis;Fluidanalysis;Nashequilibrium;Self-adaptiveincentive引言现有的P2P文件共享系统,如BitTorrent[1],eMule[2]等大都采纳类似的文件文件传输过程:(1)将文件被分成若干块(chunk);(2)peer节点从seed节点上下载部分文件块后就能给其他peer节点上传这些块;(3)peer节点从别的peer节点那里寻找所需的块下载,同时给别的peer节点上传其所需的块.采纳这样的传输过程以后,下载一个文件的peer节点就形成一个集合依据peer-to-peer的方式相互传输数据,所以这样的文件共享系统也常被称为fileswarming系统.由于在这样的fileswarming系统中,每个peer都能供应服务,所以系统的总服务能力随着下载节点个数的增加而增长,总服务能力除以节点所需带宽之和就是每个节点下载文件的平均速度,这个平均速度将直接决定节点的平均文件下载时间.由于总服务能力能随下载节点个数线性增长,所以文件的平均下载时间不会随下载节点个数的增加而变大,使得系统具有良好的可扩展性[3].而对于传统的C/S结构,系统的服务能力取决于服务器的能力,和下载节点个数无关,文件的下载时间会随着下载节点个数的增加而飞快变大,甚至最终会导致系统变得不行用.由此可见,peer-to-peer模式给大规模文件传输带来来巨大的好处.正是由于P2P模式给出文件传输带来的好处,这些P2P文件共享系统得到了广泛的使用,而且在这些系统中,BitTorrent更是获得了很大的成功.文献[4]的测量、统计结果表明:2004年P2P流量占整个Internet网络流量的40\%,而BitTorrent流量占据了这些P2P流量中的35%.2007年,德国互联网调研机构ipoque称:互联网总流量中的50-90%都来自P2P程序,而在这些P2P程序里,BitTorrent占据了P2P流量中的50-70%,2008年的统计结果表明,BitTorrent仍然占据P2P流量的第一位[5].随着BitTorrent在Internet中被普遍使用并产生着巨大的网络流量,在P2P学术领域消灭了BitTorrent的网络测量分析和理论建模分析,这些分析旨在揭示BitTorrent的系统性能及BitTorrent设计中影响系统性能的因素.对于P2P文件共享系统而言,系统的性能从用户角度集中体现在文件的下载时间上,从系统资源角度集中体现在文件传输产生的网络流量上.由于BitTorrent系统中的节点只下载该节点还没有的文件块,而系统中的其他数据传输(如交换文件块位图)引起的通信量相比文件块传输而言很小,所以可以认为BitTorrent中的网络流量为m|F|(m为下载节点个数,|F|为下载文件F的大小),这是文件共享所需的最小网络通信流量,所以在分析BitTorrent时不需分析引起的通信流量,只需分析文件的下载时间.激励机制是BitTorrent文件传输协议的重要组成部分,BitTorrent采纳的激励机制由tit-for-tat和optimisticunchoking两个策略组成,这两个策略都是用来掌握选择哪些节点进行数据上传的,其中tit-for-tat策略保证了节点选择那些给该节点供应最大下载带宽的nut(系统默认nut=4)个节点进行上传,从而保证了节点在供应大的上传带宽的同时也能获得大的下载带宽.显然tit-for-tat策略使供应上传成为得到下载的前提条件,所以freeriders在这种策略下得不到下载带宽,有效抑制了free-riding行为;另一个激励策略OptimisticUnchoking是节点随机选取nuo(系统默认nuo=1)个邻居节点供应上传,其目的是通过试探连接未连接过的节点,找出比现有连接上传带宽更高的节点,从而获得更大的下载带宽[6].激励机制对于提高文件共享系统的性能(即缩短文件的下载时间)起着重要的作用,在没有激励的情况下,BitTorrent中的很多用户就会变成只下载文件而拒绝上传的freeriders,此时系统的总服务能力就会显著降低(极限情况就退化成C/S结构),文件的下载时间将随着下载节点的增多而显著增加[6].但另一方面,激励机制也使能力低的节点(不具备供应大上传带宽的能力)获得少量的下载带宽,对于能力低的节点来说,文件的下载时间会很大,文[7]用深刻的数学分析表明“节点公正度和文件下载时间之间存在trade-offs”这一事实,这说明节点选择的激励策略会影响其文件下载时间,对于BitTorrent中的节点来说,相比抽象的公正性(贡献带宽接近于接收带宽)而言,使文件下载时间最小化才是节点最想达到的优化目标.因此节点必定会以文件下载时间为效用函数而展开博弈[8],而目前针对BitTorrent的激励讨论都以公正性为博弈的效用函数,本文认为以文件下载时间为效用的博弈才更符合实际.从BitTorrent诞生到现在,在对其文件传输和激励机制的理论分析方面产生了大量的讨论.如Clevenot等人在文[9]中将packet网络中的fulid模型[10]引入到P2P应用的性能分析中,文[9]用fulid模型对P2PWeb缓存系统Squirrel的性能(如命中率、延迟等)进行了理论分析,表明fulid模型具有有效分析象P2P这样的多数据源内容共享系统的能力.但Squirrel系统中没有激励机制,所以文[9]和分析带激励的BitTorrent之间还存在着很大的区分.Qiu等人在文[11]中用fuild模型对BitTorrent的文件传输性能(平均下载时间、可扩展性、共享效率等)进行了简略的理论分析,同时也分析了激励机制对BitTorrent性能的影响.针对BitTorrent中的激励机制,文[11]得出的结论是节点在选择上传带宽和下载带宽的博弈过程中存在Nash平衡点:具有相同上传带宽的节点会形成一个组相互传输数据.但文[11]并没有定量的分析形成组对文件传输的简略影响,这也是由于Nash平衡无法定量刻画组的简略结构而造成的.Clevenot-Perronnin等人在文[12]中提出了multiclassfluidmodel,并用该模型对异构P2P文件共享系统进行建模分析,该文给出的分析方法可以用于分析激励机制造成的异构BitTorrent系统,但文[12]给出的是一般性的分析方法和分析结果,在分析带激励机制的BitTorrent这一简略系统而言不完全适用.Massoulié等人用随机过程分析了一个couponreplication系统[13],该系统实际上是P2Pfileswarming系统的特殊情形:节点带着一个初始coupon(即文件块)进入系统;在系统中相互复制自己没有的coupon(即文件块交换);当收集到全部的coupon(即文件下载完成)后节点离开系统.本文分析的系统和文[13]的假设完全一样,但文[13]旨在分析BitTorrent中的altruist和rarestfirst策略对系统性能的影响,而本文集中分析BitTorrent激励机制对文件共享性能的影响.文[14]中的大部分讨论工作和文[13]类似(只是对文[13]的部分讨论给出了更紧的结果),另一方面,文[14]用随机模型分析了tit-for-tat激励机制,但文[14]只分析了此时的平均下载时间,而且是在先执行coordinatedmatching后再启动tit-for-tat的假设基础分析的,这样的分析结果既没有分析激励机制对文件传输影响的细节,又与实际BitTorrent的工作环境不符(在实际P2P环境中,没有中心节点的帮助很难完成coordinatedmatching).文[15]依据文件下载的完成情况对系统中的节点分布给出分析,发现这个分布呈现字母U的外形,即只下载到少量文件块的节点和快要下载到全部文件块的节点较处于其他下载阶段的节点要明显多,这也说明对于BitTorrent的整个文件下载过程,其中开头阶段和结束阶段的文件下载速度要明显缓慢.但文[15]在分析时假定全部节点的上传带宽全都(即分析的是同构系统),有趣的是,该文分析时认为处于不同下载阶段的节点之间的数据传输效率是不同的,即文[15]处理的是各节点获得的文件块数量不同这一异构特性,实际上该异构性表示的是文件共享系统在时间范畴上的异构性,而节点具有不同的上传带宽(精准的说是供应了多少上传带宽)体现了文件共享系统在空间上的异构性.本文的分析表明白tit-for-tat机制使空间异构性影响着文件共享性能,对此文[15]并没有给出分析,另外在本文的分析过程也考虑了时间异构性.除分析激励机制对BitTorrent文件传输性能的影响以外,还有一些讨论用来分析BitTorrent激励机制的激励效果,如Levin等人在文[16]中提出了一个基于拍卖的模型来分析BitTorrent激励机制,分析的结果表明该激励机制不是严格意义上的tit-for-tat,所以不是严格意义上的公正、易受到诸如Sybil等攻击,在基础上文[16]给出了一个成比例的上传带宽安排策略(Prop-share).较于该讨论,本文重点讨论激励机制对文件共享性能的影响,这样的分析在文[16]是没有的.由于文[16]提出的Prop-share是一种更为严格的tit-for-tat策略,所以Prop-share仍会导致节点按其上传带宽成组,因此本文给出的分析方法和分析结论对于Prop-share策略仍适用.本文的工作和Liao等人在文[17]给出的工作类似,文[17]和本文一样,分析的对象都是由高带宽和低带宽两类节点的异构BitTorrent系统,但文[17]的讨论较粗糙,如在文[17]的分析中(低带宽节点在系统中所占的比例)被设为定值,而由于高带宽节点和低带宽节点的文件下载时间存在差异,两类节点在系统中停留的时间不一样,所以凹凸带宽节点在系统中占的比率是不断变化的;再如文[17]分析的是异构系统在tit-for-tat等机制作用下的达到平稳状态后的文件平均下载时间,但该文却并没有明确的给出这一平稳状态.Legout等人在文[18]中就BitTorrent的peerselection策略给出了简略的实验分析(而且是该文首次给出了这样的结果),该文从实验测量角度得出了相像带宽节点的聚类现象,但由于文[18]不能就聚类现象给出形式化描述,所以无法做进一步深化分析,实际上,本文的讨论工作正是以此为动身点的.另外,通过改进激励机制来提高BitTorrent的性能也是本文讨论的内容之一,Li等人在文[19]中用fulid模型对BitTorrent中的free-riding进行了分析,结果表明seed的存在是使free-riders受益的直接缘由,所以该文针对seed给出了抑制free-riders的方法,由于本文分析时假设seed只用来给下载者供应第一个文件块,在后续的文件下载中不起作用,所以在本文的讨论中seed是不能让free-riders收益的,这表明文[19]给出的方法和本文给出的方法将在BitTorrent中一同发挥作用.Zhao等人在文[20]中给出了一个一般性的框架来分析和设计激励协议,该框架可以用来分析能动态调整的激励机制(即自适应激励),这表明自适应激励将成为BitTorrent激励协议改进讨论中的一项重要内容,但文[20]的分析是从系统鲁棒性动身,且分析的是两个一般性自适应激励协议,而本文直接从文件共享应用目标动身来提出可良好的适用于BitTorrent的自适应激励机制.Huang等人在文[21]中给出了一种称为dynamicquotaallocation的上传节点选择策略,该策略的基本思想是动态调整节点上传带宽安排中tit-for-tat和optimisticunchoking所占的比例(BitTorrent中这个比例固定为4:1),用来解决该文中提出的供应和需求之间的paradox问题.本文对激励机制的改进采纳了同样的思想,但本文的讨论建立在严格的理论模型基础上,并从系统性能的优化角度动身,远不限于只解决供求paradox的问题.Fan等人在文[7]中也给出了通过掌握tit-for-tat和optimisticunchoking之间的比例来实现文件平均下载时间和系统公正性之间的折中,但该讨论的基础假设是文件下载时间和系统公正性完全分离,而实际上不好的系统公正性就会导致大量的free-riders,自然会使文件下载时间增大.对实际BitTorrent系统来说最有意义的问题是从文件下载时间的最小化动身找到Pareto最优状态(对应一套节点选择和块选择的参数设置),在综合考虑这些实际BitTorrent系统普遍存在的因素(空间异构性、时间异构性、free-riders等)基础上找到这样的Pareto最优状态就是本文要解决的基本问题.总的来说,本文的主要贡献如下:(1)本文用马尔科夫过程分析了tit-for-tat作用下进行文件块相互传输的节点集合具有的特征,而且本文对这一特征给出了简略的数量刻画,这为BitTorrent激励机制的分析和改进奠定了理论基础.(2)本文用fulid模型分析了激励机制作用以后BitTorrent文件共享的系统性能,揭示了此时的文件下载系统结构,并用概率方法分析了该结构对节点间文件交换的简略影响.(3)本文提出了以最小化文件下载时间为效用函数的节点博弈模型,分析了该博弈的纳什平衡,给出了达到纳什平衡时各类节点实行的激励策略.(4)在理论分析基础上,本文提出了一种格外易于实现的自适应激励协议(self-AdaptiveIncentiveProtocolsforfileSwarming,简称为AIPS),并用模拟实验验证了AIPS对文件下载性能的影响.本文的组织结构为:第2节对BitTorrent的激励机制,即由tit-for-tat和optimisticunchoking两个协议组成的节点选择策略进行了理论建模和分析;第3节对带激励的BitTorrent文件传输进行了fulid建模分析及概率分析,据此给出了以最小化文件下载时间为效用的节点博弈模型及其纳什平衡,本节的最后给出了一个可直接用于BitTorrent的自适应激励协议AIPS;第4节对AIPS进行模拟实验;第5节是本文的结论.BitTorrent激励机制的理论分析2.1BitTorrent激励机制模型定义1集合D(p,t)定义为时刻t向节点p供应下载的节点集合;集合U(p,t)定义为时刻t从节点p处下载数据(即节点p供应上传)的节点集合.对于节点p,p从D(p,t)中的节点下载数据,p给U(p,t)中的节点上传数据,如图1所示.因此本文将D(p,t)称为节点p的下载节点集,U(p,t)为节点p的上传节点集.图1节点p的下载节点集合D(p,t)和上传节点集合U(p,t)显然,D(p,t)将直接决定节点p的文件下载时间(由于文件下载时间等于文件大小除以下载速率),因此在分析BitTorrent的性能时首先需要分析D(p,t)的变化以及D(p,t)稳定时的状态.依据BitTorrent的节点选择策略tit-for-tat和optimisticunchoking(BitTorrent就用这两个协议来实现激励),节点p将按如下原则产生U(p,t+1)从t时刻的下载节点集D(p,t)中选择nut=4个供应下载带宽最大的节点,然后随机选择nuo=1节点,从而形成包含m=nut+nuo=5个节点的集合U(p,t+1),此季节点p会将其上传带宽等分为m份,向集合U(p,t+1)中的每个节点安排一份上传带宽.同样的原理,U(p,t+1)中的节点在t+1时刻获得节点p的下载带宽后会依据同样的原则调整t+2时刻的给p的上传带宽,也即会影响到D(p,t+2),所以就有D(p,t)将影响U(p,t+1),而U(p,t+1)又会影响D(p,t+2)等等,该依靠关系可表示为图2.显然上述过程存在随机性,所以此处使用马尔可夫过程对该依靠关系进行数学分析.图2U(p,t)和D(p,t)之间的依靠关系由上述分析过程可以看出,节点的上传带宽将直接影响U(p,t)和D(p,t)的变化,也即P2P文件共享系统的空间异构性(本文处理的对象就是异构P2P文件共享系统)将直接影响系统平稳时的U(p,t)和D(p,t).所以本文在分析时将依据上传带宽对节点进行分类,不失一般性的前提下可将节点分为两类:上传带宽高的节点Ph和上传带宽低的节点Pl,并假设Ph中节点的上传带宽都为uh,Pl中节点的上传带宽都为ul,令Nh=|Ph|,Nl=|Pl|,N=Nh+Nl.由于节点选择策略的自适应通常都体现为nut和nuo之间的比值[7,21],为了分析和设计的便利,本文假设nuo恒等于1,nut=m,用m值来自适应的调整节点选择策略(这样的设置显然会导致nut:nuo1,即激励占据更大的比重,P2P系统的开放性导致这样设置的合理性,所以BitTorrent采纳了4:1.且本文后面的分析得出的Pareto有效条件满意m2,所以此处的假设从理论和实际角度都是合理的).此季节点在执行optimisticunchoking来随机选择nuo=1节点时,找到1个高上传带宽节点的概率为=Nh/N,找到1个低上传带宽节点的概率为1-=Nl/N.2.2高带宽节点的上传节点集令节点h是高带宽节点,设t时刻的U(h,t)={n1,…,nm},其中{n1,n2…,nm-1}(依据假设nut=m-1是节点p应用tit-for-tat规章从D(h,t-1)中选择的节点,而nm是节点poptimisticunchoking到(即随机选择)的节点.U(h,t)中的节点依据其上传带宽也可以分为两类:高上传带宽节点和低上传带宽节点.用nh和nl分别表示U(h,t)中高带宽节点和低带宽节点个数,其中nh,nl是非负整数且nh+nl=m.定义2定义Up(nh,nl,t)为节点p在t时刻的上传状态,其中nh和nl分别表示U(h,t)中高上传带宽节点的个数和低上传带宽节点的个数.由BitTorrent的tit-for-tat和optimisticunchoking的工作过程可知,节点p在选择哪些节点上传文件只与节点p前一时刻的下载节点集D(p,t)和有关,而与简略时刻无关.因此在分析Up(nh,nl,t)等同于分析在上传状态集合Up(nh,nl|nh+nl=m)上形成的马尔可夫链,可以将状态枚举为{Up(0,m),Up(1,m-1),…,Up(m,0)},其中Up(1,m-1)表示节点p的上传节点集合由1个高上传带宽节点和m-1个低上传带宽节点组成.本文将该马尔可夫链记为{Up(t):t=0,1,2,…},其概率转移矩阵记为Pu(p).定理1对于高带宽节点h,其概率转移矩阵Pu(h)为:(0,(0,m)(1,m-1)(2,m-2)…(m-1,1)(m,0)(0,m)(1-)22(1-)2…00(1,m-1)0(1-)22(1-)…00(2,m-2)00(1-)2…00…(m-1,1)000…1-(m,0)000…1-Pu(h)=(1)证明:以Pu(h)[(2,m-2),(2,m-2)]为例,即当节点h时刻t的上传节点集U(h,t)中高、低上传带宽节点的个数分别为2与m-2时,U(h,t+2)中高、低上传带宽节点个数仍为2与m-2的概率.大事“U(h,t+2)中高、低上传带宽节点个数分别为2与m-2”可分为如下三种情况:(1)节点h从D(h,t+1)中依据tit-for-tat协议选择2个高上传带宽节点和m-3个低上传带宽节点(该大事用T2表示),再用optimisticunchoking协议随机选择到1个低上传带宽节点(该大事用O0表示,显然Pr(O0)=1-;(2)节点h从D(h,t+1)中依据tit-for-tat协议选择1个高上传带宽节点和m-2个低上传带宽节点(该大事用T1表示),再用optimisticunchoking协议随机选择1个高上传带宽节点(该大事用O1表示,显然Pr(O1)=).并且由于tit-for-tat和optimisticunchoking的节点选择是独立的,所以:Pu(h)[(2,m-2),(2,m-2)]=Pr(T2)Pr(O0)+Pr(T1)Pr(O1)由于U(h,t)中高、低上传带宽节点个数分别为2与m-2,依据tit-for-tat协议U(h,t)中的节点都会选择向高带宽节点(节点h是高带宽节点)上传,因此U(h,t)D(h,t+1),因此D(h,t+1)中至少有2个高上传带宽节点.用大事D2和D3+分别表示D(p,t+1)中有2个高上传带宽节点的大事和有3个及3个以上高上传带宽节点的大事,消灭D3+是由于有高上传带宽节点optimisticunchoking到了节点h.节点h被某个高上传带宽节点h'optimisticunchoking到的概率为1/N,大事D2等价于Nh个高上传带宽节点都没有optimisticunchoking到节点h的概率,由于节点选择策略是独立的,所以Pr(D2)=(1-1/N)Nh=1-+o()1-;又由于D(p,t+1)只消灭上述这两种情况,所以Pr(D3+=.Pr(T2|D3+)表示U(h,t+2)从D(h,t+1)中选择2个高上传带宽节点,而此时D(p,t+1)中有3个以上的高上传带宽节点,当m-13时,依据tit-for-tat协议,Pr(T2|D3+)=0,同理可知Pr(T2|D2)=1.因此:Pr(T2)=Pr(T2|D3+)Pr(D3+)+Pr(T2|D2)Pr(D2)=0+1(1-)同理,当m-12时,由于D(h,t+1)中的高上传带宽节点个数至少为2,依据tit-for-tat协议有Pr(T1)=0.所以,当m4时Pu(h)[(2,m-2),(2,m-2)]=(1-)2.上面给出的是m4时的情况分析,现分析m=2和m=3时的概率转移:当m=2时,节点h用tit-for-tat协议从D(h,t+1)中只选出1个节点,U(h,t)D(h,t+1)使得这个节点肯定是高上传带宽的节点,所以Pr(T2)=0,Pr(T1)=1,所以Pu(h)[(2,m-2),(2,m-2)]=.当m=3时,节点h会用tit-for-tat协议从D(h,t+1)中选出2个节点,U(h,t)D(h,t+1)使得这2个节点肯定都是高上传带宽的节点,所以Pr(T2)=1,Pr(T1)=0,有Pu(h)[(2,m-2),(2,m-2)]=1-..(1-)22(1-)201-0(1-)22(1-)201-01-Pu,2(h)=(1-(1-)22(1-)200(1-)22(1-)2001-001-Pu,3(h)=找到这些矩阵的共同规律即得出式(1).证毕.对于BitTorrent(对应m=5)中的高上传带宽节点h,其马尔可夫链{Uh(t):t=0,1,2,…}上的状态转移图就为:图3BitTorrent中高上传带宽节点h的{Uh(t):t=0,1,2,…}的状态转移2.3高带宽节点Uh(t):t=0,1,2,…的极限分布定理2令Pu(h)=limnPun(h),有:(0,(0,m)(1,m-1)(2,m-2)…(m-1,1)(m,0)(0,m)000…1-(1,m-1)000…1-(2,m-2)000…1-…(m-1,1)000…1-(m,0)000…1-Pu(h)=(2)证明:令Puk(h)[ij]=Pr(Uh(l+k)=j|Uh(l)=i),Pu(h)[ij]=limkPuk(h)[ij].令fk(i,j)为从时刻0从状态i动身在时刻k首次到达状态j的概率.以m=5(即BitTorrent)为例来分析,为了描述的便利,将状态Uh(0,5),Uh(1,4),Uh(2,3),Uh(3,2)记为0,1,2,3,将状态Uh(4,1),Uh(5,0)记为4,5,将Puk(h)[ij].简记为Pijk.依据图3显然有,状态0,1,2,3为格外返态,状态4,5为常返态,因此Pij=0|i{0,1,2,3,4,5};j{0,1,2,3}.接下来需要计算Pij|i{0,1,2,3,4,5};j{4,5}.P442=x=05P4xPx4=00+00+02+02(1-)+(1-)(1-)+(1-)=1-,经过归纳可以得出P44k=1-,即有P44=1-.同样的方法可计算得出P45=1-,P54=和P55=.现在求P14.由于limkP14k=limkt=1kf14tP44k-t=limkt=1Kf14tP44k-t+limkt=K+1kf14tP44k-t固定K后limkt=1Kf14tP44k-t+limkt=K+1kf14tP44k-t=t=1Kf14tP44+limkt=K+1kf14tP44k-t再令K有limKt=1Kf14tP44=t=1f14tP44以及limKlimkt=K+1kf14tP44k-t=0.显然,t=1f14t为从状态1动身到达状态4(此处该这一大事记为A)的概率,定义B1为从状态1动身且在到达状态5之前先到达状态4的大事;而B2为从状态1动身且在到达状态4之前先到达状态5大事.由状态迁移图3可知,从状态1动身最终必定到达状态{4,5},所以Pr(B1B2)=1,而显然有B1和B2不行能同时发生,即Pr(B1B2)=0.因此可用全概率公式得出:t=1f14t=Pr(A)=Pr(A|B1)Pr(B1)+Pr(A|B2)Pr(B2),而其中Pr(A|B1)=1;Pr(A|B2)=t=1f54t=(1-)+(1-)+(1-)2+…=(1-)/(1-)=1.因此就有t=1f14t=Pr(B1)+Pr(B2)=1,也就有P14=P44=1-.同样的方法可以求得Pu,5(h)中的其它项.同理对于其他的m取值,也可以用同样的方法求得Pu,m(h)[ij],得到式(2).证毕.2.4高上传带宽节点的聚簇定理3高上传带宽节点h的马尔可夫链{Uh(t):t=0,1,2,…}的极限分布u(h)=(0,…,1-,),并且与初始分布无关.证明:设系统中高上传带宽节点h的初始上传状态的分布为,则其极限分布u(h)=Pu(h):0…1-0…1-…………0…1-0…1-u(h)==(0,…,1-,)(3)即有u(h)=(0,…,1-,),证毕.定理3的结果表明,随着tit-for-tat和optimisticunchoking对上传节点的逐步选择,具有高上传带宽的节点最终将选择给同样具有高上传带宽的节点进行数据上传.定量的说,一个高上传带宽节点平均会将其(1-)(m-1)/m+m/m=(m-1+)/m的上传带宽安排给高带宽节点.2.5低上传带宽节点的聚簇对于BitTorrent文件共享系统整体而言,任何时刻节点p给节点p供应了上传带宽upq,则在同一时刻节点q从节点p那里收到的下载带宽dqp=upq.所以对于文件共享系统而言,节点的总上传带宽等于节点的总下载带宽.应用这个等式可以分析低上传带宽节点的聚簇.图4高、低上传带宽节点集合在文件共享系统中的传输关系包含高、低上传带宽两类节点的文件共享系统可以表示为图4,其中的Uhl表示高上传带宽节点集合给低上传带宽节点集合传输的总带宽,依据定理3可以求出Uhl和Uhh:Uhh=(m-1+)uhNh/m(4)Uhl=(1-)uhNh/m(5)对于Ull和Ulh显然有Ull+Ulh=ulNl,要求得Ulh和Ull需要建立上传带宽和下载带宽间的关系.定理3表明系统平稳后高上传带宽节点h的上传节点集U(h)的结构为:m-1个高上传带宽节点{n1,n2,…,nm-1}和1个节点nm(nmPh的概率为,nmPl的概率为1-).依据图2可知,平稳后的D(h)将依靠于这个U(h)结构,由于节点h是高上传带宽节点,所以接收节点h的上传带宽的节点也会给节点h上传(tit-for-tat),即U(h)D(h).除了U(h)中的节点给h供应下载带宽以外,其他N-m-1个节点也可能给节点h供应下载带宽,当且仅当这些节点optimisticunchoking到节点h,其中每个节点optimisticunchoking到节点h的概率为1/N.此时集合D(h)就可枚举出来:{n1,n2,…,nm-1,nm,nm+1,…,nN-1},其中{n1,n2,…,nm-1,nm}的含义和U(h)一样,系统中其他的N-m-1个节点形成{nm+1,…,nN-1}.由于系统平稳后节点ni|{i=1,…,m-1都是高上传带宽节点,所以计算Ulh时和这个m-1节点没有关系.对于节点nm,该节点以概率为是高上传带宽节点,所以该节点对Ulh的贡献可近似为(1-)ul/m(之所以说近似是由于当时可能有多个高带宽节点向低带宽节点nm上传,但显然这样的概率较一个高带宽节点接受多个高带宽节点上传的概率要低得多).对于剩下的节点ni|{i=m+1,…,N-1,这些节点对Ulh的贡献为i=m+1,…,N-1(1-)/Nul/m,这是由于剩下N-m-1个节点都以1/N的概率给节点h供应上传,且该节点是低带宽节点的概率为1-,假定m<<N时有:Ulh=2(1-)ulNh/m(6)Ull=ulNl-2(1-)ulNh/m(7)从图3可以清楚地看出:高、低上传带宽节点集合之间的数据传输相比集合内部的传输要少很多,节点依据其带宽表现出了明显的聚类现象,而且这种聚类会随着m的增大而加剧.式(4)-式(7)定量的说明白激励协议对BitTorrent文件传输的影响,目前还没有讨论对这一影响给出定量分析结果,而该定量分析结果,即式(4)-(7)是本文讨论的基础.带激励BitTorrent文件传输的性能分析与改进3.1BitTorrent文件传输模型在对BitTorrent的文件传输性能进行理论分析之前,需对其文件传输过程模型化.BitTorrent文件传输过程的核心是:文件被分成若干块,下载一个文件的节点集合相互传输所需的文件块.一个大小为|F|的文件F被分割为文件块集合F={c1,c2,…,ck},通常P2P文件共享系统中的文件块大小固定.BitTorrent中的文件块大小通常设定为256KB,而|F|通常为数百MB,所以BitTorrent中节点下载一个文件通常需要下载数千个文件块(即k值通常为数千).当一个节点p想下载文件F时,p首先要访问tracker服务器,tracker会给p返回若干拥有F的节点(seed节点),p从这些节点下载到文件F的若干块后,p和其他下载节点之间开头相互交换文件块,进入fileswarming时期.由于节点p从seed那里下载的文件块只有几块,远小于k的值,所以影响文件传输性能的关键是下载同一文件的节点集合(可用F表示该集合)内各节点间的文件块交换,分析时可忽视tracker和seed对传输性能的影响.因此要下载F的节点p进入F时,假定p初始化有一个文件块ci,且ci从{c1,c2,…,ck}中随机选取.定义3对于任意pF,节点p的文件下载时间tF(p)就是指通过F中节点间的文件块交换使p下载完成F={c1,c2,…,ck}的时间.定义4从P2P文件共享系统角度,其文件传输性能集中体现为系统的平均文件下载时间TF:TF=pFtF(p)/|F|(8)此时F就成为一个随时间变化的动态系统,记F(t)为t时刻的F.系统F(t)按如下方式变化:(1)一个新下载者p以参数为的泊松过程在t1时刻进入系统F;(2)一个节点在t2时刻下载完文件F后立刻离开F,显然t2-t1=tF(p).因此本文分析的TF就是系统平稳后节点在动态系统F(t)中停留的平均时间.显然,影响节点p在系统F(t)的停留时间的关键因素是F(t)|t[t1,t2]集合中各节点间的文件块交换过程.对于BitTorrent系统,这个文件块交换过程与t无关,固定为:(1)节点p向和其连接的节点集合N(p)发送文件块位图(该位图用来表示节点拥有文件的哪些文件块),同时也从这些节点那里接收文件块位图,对于BitTorrent通常有|N(p)|=40;(2)p依据特定的块选择原则(如BitTorrent采纳的rarestfirst原则)从这些位图中找到自己没有的文件块Cr;(3)p向拥有文件块Cr的某个节点pr发出下载申请;(4)pr依据节点选择策略(在BitTorrent中就是tit-for-tat加上optimisticunchoking的激励机制)决定是否给p发送数据块Cr.很多讨论结果,如文[9-14]等已经对无激励影响下的系统F(t)进行了深化的分析,本文将集中分析在BitTorrent激励机制影响下的F(t)及文件块交换.3.2BitTorrent激励下的F(t)BitTorrent激励机制对F(t)影响的根本表现是:激励机制会将F(t)依据节点上传带宽被“分割”成若干个部分,高上传带宽节点更多的和高上传带宽节点进行文件传输;低上传带宽节点更多的低上传带宽节点进行文件传输.因此BitTorrent激励机制下的F(t)变成由多类节点组成的简洁结构(图4刻画了两类节点下该结构的细节).此时分析TF变成分析各类节点的平均文件下载时间,进一步变成各类节点在系统F(t)中的停留时间,依据Little定理L=W[22],节点在系统中的停留时间将和系统的规模有直接联系.所以此处将集中分析F(t)中各类节点集合的规模在文件传输过程中的变化,这一节点规模的变化讨论大都以文[11]给出的fluid模型为基础.但文[11]讨论的是同构系统,即全部节点属于同一类型.文[12]扩展了fluid模型使其可以适用于异构系统的分析,本文也采纳该扩展模型来对BitTorrent激励对F(t)的影响进行分析.不失一般性,和前面一样本文仍假定系统F(t)中只包含高上传带宽节点和低上传带宽节点两类,并令t时刻F(t)中高上传带宽节点的个数为h(t),低上传带宽节点的个数为l(t),有h(t)+l(t)=|F(t)|.由于一个新的下载者会以参数为的泊松过程进入F(t).所以h(t)会以参数为h的泊松过程加1,而l(t)会以参数为l的泊松过程加1,其中h+l=.本文假定任何节点在下载完F后立刻离开系统,且不在下载中途离开.seed节点只对文件交换初始化起作用,所以这个fluid系统中不包含seed节点,完全由leecher节点组成.令高、低上传带宽节点的下载带宽分别为ch和cl.同文[11],定义高、低上传带宽节点的文件共享效率为h和l,可建立微分方程:dh(t)/dt=h-min(chh(t),hUhh+lUlh)dl(t)/dt=l-min(cll(t),lUll+hUhl)其中Uij|{i,j}{h,l}就是式(4)-(7)给出的结果,只是其中的Nh和Nl在这里相应的变成h(t)和l(t),而=h(t)/(h(t)+l(t)).h2(t)l2(t)h(t)l(t)h(t)l(t)h2(t)l2(t)h(t)l(t)h(t)l(t)-hh-hh-hl/m0-(m-1)hh/m-ll/mhhhl/m-ll-(m-2)ll/m-hh/mllh(t)l(t)(h(t)+l(t))=(9)3.3BitTorrent激励对文件块交换的影响由于F(t)被分割成很多个节点类,BitTorrent系统内的文件块交换就变成为节点类内部的文件块交换.由于相互感爱好是文件块交换的前提,而随着交换节点集合规模的缩小(F(t)的分割显然会导致规模的缩小),节点找到供应感爱好文件块的节点(此处将这样节点成为有效下载节点)的机会就会削减,有些下载周期(实际上是choking周期)会因找不到有效下载节点而浪费,导致文件下载时间增长.例如,在完全为类内交换的极端情况下(在图4中表现为没有类间的边),且该类中全部节点拥有文件块的并集仍是文件F的真子集时,该类中全部节点的文件下载时间将变成无穷大.Unchoking机制的提出就是为了解决该问题,图4中节点类之间的边就是执行unchoking后才有的结果,而且随着m的削减,unchoking掌握的上传带宽配额就会增加(见式(5)和(7)),各节点类之间的边就会增多,找到有效下载节点的概率会增加.在进行掌握之前需对上述影响进行定量分析,这肯定量特征就体现在式(9)中的上,而的大小就是概率值:Pr{节点p在时刻t能向其连接节点供应感爱好文件块},式(9)中的h和l分别对应于此概率值中p为高带宽节点和p为低带宽节点.因此:=1-qN(p)Pr(C(p)C(q))=1-Pr(C(p)C(q))|N(p)|其中N(p)是节点p的连向的邻居节点,C(p)是节点p已经下载获得的文件块集合,上式的推导中假定各节点的文件下载是独立的(由于BitTorrent中各节点独立下载,所以该假设成立).文[11]给出的分析结果是上式中的值格外接近1,表明在BitTorrent中的rarestfirst块选择策略下,找到有效下载节点的概率很高,浪费的下载周期很少.但文[11]在分析时实际上假定了节点能交换全部文件块的事实,也即网络上的文件块集合没有被分割的事实.这种分割表现的最为极端的情形是一个断开且不能和其他子网恢复连通的子网上只有部分文件块,此时最终会导致这个子网内的“节点集合无文件块可传”情况,此时势必造成文件下载时间的增大.而图4所描述的网络“断开”(实际上不是完全断开,而是连通度变小了)对文件下载的影响是:当一个节点聚簇中的文件块交换完成时,别的簇会向该簇引入新的文件块,如果引入的文件块数量太少就会导致进入该簇的数据量不能满意簇内带宽的全部使用,浪费下载带宽,增加文件下载时间.在本文假定的两带宽系统中,高带宽节点会消灭这一现象(由于高带宽节点簇能很快将簇中的文件交换完,且低带宽节点簇向高带宽节点簇供应新文件块的速度很可能低于高带宽节点簇的下载能力).显然,对于实际的BitTorrent文件共享系统而言,上述网络“断开”对文件传输的影响才是需要本文分析和解决的问题,而在BitTorrent掩盖网络上,真的网络断开可以很容易做到恢复连通(如随机选择一个节点optimisticunchoking即可).依据上文的分析,消灭如图4描述的网络``断开''以及高带宽节点簇将簇内文件块交换完成以后,要使这一``断开''不影响到文件的下载速度,就要求低带宽节点簇向高带宽节点簇引入的新数据量大于高带宽节点簇的总下载能力,即:YS|Ph|S/uluh|Ph|Yuh/ul(10)其中Y是低带宽给高带宽节点引入的新文件块数量,S是每个文件块的大小,YS|Ph|表示低带宽节点簇向高带宽节点簇引入的可新下载的数据量(和|Ph|相乘是由于Ph中的每个节点都需要下载这Y个新数据块,所以此处新的含义表示Ph中任何节点都没有下载到的文件块);S/ul是一个文件块被低带宽节点上传给高带宽节点的时间,由于这Y个文件块被多个低带宽节点并行的上传给多个高带宽节点,所以该时间也是大小为YS|Ph|的新数据量进入高带宽节点簇所需要的时间,这个时间乘以uh和|Ph|是这段时间高带宽节点簇所能下载的总数据量,即其总下载能力(此处用uh而不是dh来计算下载能力是由于高带宽节点的下载依靠其他高带宽节点的上传,而上传是能力的瓶颈).显然式(10)中的Y值与高、低带宽节点簇之间的连接数量,与节点簇已经下载到的文件块数量,与文件块在节点上的分布等因素有关.此处令C(p)表示节点p已经下载到的文件块集合;在系统只包含两类节点的假设下,位于高、低带宽节点簇之间的连接实际上就形成从Pc到P的割(此处的P就是Ph),将这个割记为L[Pc,P].此时,割L中的边会将C(Pc)中的块上传到C(P)中,而多少个“新块”(不在C(P)中的块)被加入C(P)中是此处分析的关键,显然该新块数量应该是一个随机变量,可分析其期望值,而这个期望值就是式(10)中的Y.图5给出割L,“新块”,C(P),C(Pc),c(p)等概念之间的关系:图5C(P),C(Pc),割L等集合之间的关系在图5中,对于割L中的连接l=(p',p),如果p'将一个“新块”上传到p处,就认为l将一个“新块”引入到C(P).因此L共引入到C(P)中的新块数就是全部lL引入的“新块”的并集大小,可定义示性随机变量Xl:1ImportNewChunkbylXl=0Others在不考虑L中各Xl之间的相互影响(显然这些随机变量是不独立的)时,节点p'将一个新块上传到p处的概率值不小于(|C(p')-C(P)|)/(|C(p')-C(p)|)(之所以不能求出该概率的精确值是由于rarestfirst块选择策略中块的选择不只和本地文件块集合有关).另一方面,由于l引入C(P)的新块可能被l'再次引入,为完成L共引入新块个数的计算,假定各l引入新块的过程是按序进行的,而由于L中的各个连接是完全对称的,此处就规定这个连接挨次为1,2,…,l,…,并将上面定义Xl=1的含义修改为在1,2,…,l-1完成加入后,l又引入一个“新块”(此时的C(P)已经包含了连接1,2,…,l-1加入的新块).因此上面的概率下界分析实际上就是:Pr(Xl=1|Yl-1=0)(|C(p')-C(P)|)/(|C(p')-C(p)|),其中Yl-1=X1+X2+…+Xl-1,在Yl-1的定义下,相应的也就有Pr(Xl=1|Yl-1=i)(|C(p')-C(P)|-i|C(p')|/|C(PcL)|)/(|C(p')-C(p)|),其中|C(p')|/|C(PcL)|表示已经被连接1,2,…,l-1引入C(P)的每个新块落入C(p')中的概率,由于采纳了rarestfirst块选择策略,所以可以认为每个节点下载到的文件块是在F中均匀选取的[11],即可认为每个块等概率的在C(p')中,也就会等概率的属于C(p')C(p'')(均匀分布的并仍然是均匀分布),所以每个块将等概率的属于C(PcL),由于被连接1,2,…,l-1引入的每个块必定在C(PcL)中,所以该块b落入C(p')中的概率就为Pr(bC(p')|bC(PcL))=Pr(bC(p'),bC(PcL))/Pr(bC(PcL))=Pr(bC(p'))/Pr(bC(PcL)=|C(p')|/|C(PcL)|.在上述定义基础上,求L共引入到C(P)中的新块个数的期望值(即式(11)中的Y)就相当于求E[Y|L|],此时有下面的推导:E[Xl|Yl-1=i](|C(p')-C(P)|-i|C(p')|/|C(PcL)|)/(|C(p')-C(p)|)E[E[Xl|Yl-1]]=E[Xl]E[Xl]i=0l-1(|C(p')-C(P)|-i|C(p')|/|C(PcL)|)/(|C(p')-C(p)|)Pr(Yl-1=i)E[Xl]i=0l-1(|C(p')-C(P)|)/(|C(p')-C(p)|)Pr(Yl-1=i)–i=0l-1i|C(p')|/(|C(PcL)||C(p')-C(p)|)Pr(Yl-1=i)E[Xl](|C(p')-C(P)|)/(|C(p')-C(p)|)-|C(p')|/(|C(PcL)||C(p')-C(p)|)E[Yl-1]又由于E[Yl]=E[Xl]+E[Yl-1]E[Yl]-E[Yl-1]c1-c2E[Yl-1]其中c1=(|C(p')-C(P)|)/(|C(p')-C(p)|),c2=|C(p')|/(|C(PcL)||C(p')-C(p)|)E[Yl](1-c2)E[Yl-1]+c1E[Yl](1-c2)l-1E[Yl-1]+c1(1-(1-c2)l-1)/c2又由于E[Y1]=E[X1]=Pr(X1=1)(|C(p')-C(P)|)/(|C(p')-C(p)|)=c1E[Yl]c1(1-(1-c2)l)/c2其中E[E[Xl|Yl-1]]=E[Xl]是条件数学期望的直接结果,而c1,c2中的p,p'虽然在图5中随连接l而变化,但在上述分析中显然将其当成是和l无关的值,实际上这是由于E[Yl]-E[Yl-1]c1-c2E[Yl-1]E[Yl]-E[Yl-1]E[c1]–E[c2]E[Yl-1].因此上式中的c1,c2应该是E[c1],E[c2].综合上述分析就有在满意下面的条件时,高、低带宽节点的聚合及分离就不会对文件下载产生大的影响.c1(1-(1-c2)l)/c2uh/ul(11)在求c1,c2的数学期望时,由于只有高带宽节点已交换完簇内文件块之后才需要从低带宽节点引入新的文件块,也即在图5中当C(p)=C(P)时才消灭对带宽节点数据传输的影响,在这样的条件下显然有:c1=1.此时如果对式(11)中等号左边的式子针对c2求偏导可以发现其随c2单调递减:(1)当c2=o(1/|L|)时,式(11)变为:|L|uh/ul(12)c2=o(1/|L|)意味着|C(p')-C(P)|至少大于1,通常只有|C(P)|较小时,该条件才能满意,显然没有任何高带宽节点已下载到大部分文件块是此类情况的必要条件.同时还要求|C(PcL)|接近于|C(p')|的|L|倍,这表明L对应到的低带宽节点下载到的文件块集合基本没有交集,由于BitTorrent的各节点optimisticunchoking选取到的节点是随机且独立的,所以当各个|C(p')|很小时,交集很小的条件才能得到满意.但rarestfirst的存在使得通过|L|找到的低带宽节点下载的文件块集合大小的期望为k/2.此时只有|L|2时才能满意交集很小的条件,否则c2就变成一个常数.(2)当c2是一个属于(1/|L|,uh/ul)的常数时,式(11)变为:|L|log1-c21-c2uh/ul(13)式(13)表明,随着c2无限接近于uh/ul时,|L|将趋于无穷大.(3)而当c2uh/ul时,式(12)的条件无法得到满意.有趣的是,即使此时高贷款节点从高带宽节点簇中脱离,将其全部上传连接都设置为optimisticunchoking也不能避开下载效率的降低,由于此时无论|L|如何设置都不能满意式(12)的条件.条件c2uh/ul意味着|C(p')-C(P)|很小(由于p'是随机选取的,意味着C(p)很大),显然此时消灭了BitTorrent中常见的最后块现象[14,15],由于该现象已经不属于本文的讨论范围,所以本文只处理上述条件1和条件2(分别对应式(12)和(13))所给出的情形.3.4BitTorrent文件块交换中的节点博弈与纳什平衡BitTorrent中节点的下载文件过程是一个典型的博弈过程:不同类型的节点通过不断调整其策略来达到收益的最大化.在BitTorrent文件共享中,节点的收益应该是文件的下载时间(当然是下载时间的最小化).实际上,用博弈的观点分析BitTorrent中的tit-for-tat激励机制已经在文[11]等讨论中消灭过,但文[11]中的收益定义为接收带宽和贡献带宽之间的差异,因此文[11]给出的博弈只是单纯的分析了节点付出和回报之间的关系,而相比这种关系而言,BitTorrent中的节点往往更关心文件的下载时间,即使付出适当的多余回报.实际上,在考虑文件下载时间的同时已经将以往BitTorrent博弈中的付出和回报关系考虑在内了,这是由于如果回报没能和付出匹配,文件下载时间就会增长,此时的节点必定会实行相应的策略来获得和付出匹配的回报.因此,将文件下载时间作为效用函数的博弈是对以往BitTorrent博弈的一种更符合文件共享特征的深化.本文将给出并分析这个以下载时间为效用函数的BitTorrent文件块交换博弈.不失一般性,此处仍分析只要两类节点(高带宽节点和低带宽节点)的BitTorrent系统.定理4在节点理性的假设下,对于P2P文件交换系统中的高带宽节点h而言,当h实行的上传节点选择策略为:当|C(h)|<YP时,h在其上传节点选择中选取optimisticunchoking的概率p(即上文中的1/m)满意下面的条件:/((1-1/m)(uh-ul))log1-1/(k-|C(h)|)1-/(k-|C(h)|)(14)时;而当|C(h)|>YP时,节点选择的上传节点都是低带宽节点时,节点h达到Nash平衡.其中YP是一个临界值:YP=k-(15)k是节点h交换文件F={c1,c2,…,ck}的块数,令=uh/ul.证明:依据式(13)的分析,显然c2=1/是C(h)等于临界值YP的条件.对于c2,由于p'的随机选取以及rarestfirst机制,所以可以的认为|C(p')|/|C(PcL)|1/2,而求|C(p')-C(p)|的均值时,任意文件块ciF满意ciC(p')ciC(p)的概率为Pr(ciC(p'))Pr(ciC(p))=(k-|C(p)|)/2k,依据期望的加和,|C(p')-C(p)|的均值为(k-|C(p)|)/2.联立上述结果以后就有条件C(p)=k-,即有式(15).由上面的分析结果可知,c21/(k-|C(h)|),将该值代入式(13)有|L|log1-1/(k-|C(h)|)1-/(k-|C(h)|).依据图4和式(6)的结果有|L|=Ulh/(ul/m).但是不能直接将式(6)中的值Ulh代入计算,这是由于在新的博弈(以文件下载时间为收益函数)下,低带宽节点会实行不同于以往的节点选择策略.依据上面的分析结果,高带宽节点之所以unchoking到低带宽节点的缘由是由于高带宽节点集合内部的新文件块不能满意文件块交换速率,盼望从低带宽节点那里引入更多的新文件块.因此,低带宽节点能获得高带宽节点上传带宽的缘由是高带宽节点想从低带宽节点那里获得新文件块,而不是由于低带宽节点unchoking到了高带宽节点,因此Nash平衡时低带宽选择的策略是不去unchoking高带宽节点,由于unchoking到一个高带宽节点后高带宽节点choking回的带宽为0,要比unchoking到一个低带宽节点获得的收益小.实际上如果从收益最大化角度动身,低带宽节点对高带宽节点的unchoking也可以选择choking回一个0带宽,这会导致高带宽节点更多的unchoking(由于高带宽没有达到unchoking的目的,即引入新文件块),但是高带宽节点可以将自己的带宽降低到低带宽(通过设置适当的网络协议参数,这样的掌握应该很容易实现),此时低带宽节点就无法区分出高带宽节点.因此此时低带宽实行的策略就会限制自己获得高下载带宽的机会,从博弈的角度,低带宽节点对高带宽节点的unchoking予以choking回报将使其收益更大.因此以文件下载时间为收益的BitTorrentNash平衡实际上是一种综合考虑带宽和文件块的一种平衡,区分于以往文献给出的只考虑带宽的平衡,而其中的高带宽节点的带宽和低带宽节点的新文件块之间的互换和平衡是两类平衡最显著的差别.依据低带宽节点在博弈中选择的策略,式(6)应改为Ulh=(1-)ulNh/m,将其带入后可得条件h(t)(1-)log1-1/(k-|C(h)|)1-/(k-|C(h)|).再综合式(9)的结果(其中Ulh等数值要按上面的描述修改,而由于此处分析的是节点文件下载满负荷的情况,所以可假定l=h=1,系统稳定时就有条件(14)(简略证明见附录1).证毕.对于式(14),除m和|C(h)|以外都是已知的量,对于实际的BitTorrent系统而言,这些量都可以通过网络测量而获得,属于BitTorrent系统的一些先验统计数值.图6给出了式(14)等号右边随|C(h)|及系统参数的变化情况(其中参数k设为1000,这是依据文件块大小通常设为256KB,一个数百MB的文件通常有1000块左右),由图6可以看出,为充分利用高带宽节点的带宽资源,高带宽节点集应该从低带宽节点集那里获得的(即用unchoking低带宽节点换取的)连接数量在|C(h)|<YP时随|C(h)|的变化很小,基本可以认为是一个常数,且从图6可以看出这个常数格外接近(实际上从分析角度,这个事实就是“当1/(k-|C(h)|)很小时,(1-1/(k-|C(h)|))1-/(k-|C(h)|)”的一个直接结果).图6式(14)等号右边和参数|C(h)|及间的关系综合上面的分析,式(14)可以近似为:1/m1-/((-1)ul)(16)将式(16)中的和ul依据附录1中的等式(20)进行无量纲处理,并结合h(t)=m/((m-1)uh),l(t)=((m-1-m))/((m-1)ul)以及N=h(t)+l(t),就能依据式(16)得出下面的条件:Nm(-1)(1+/-)m-(-1)/(17)表1求出几类典型场景下m的取值(其中假设=0.2).表1几类典型场景下的m取值N(Swarm中的节点规模)m取值5N>84任意5N<84m100/(84-N)580m2510N>369任意10N<369m450/(369-N)10300m6.5100N>39699任意100N<39699m49500/(39699-N)10010000m1.671001000m1.28从表1的数值可以看出:(1)对于肯定的,如果N足够大,m可以任意取值,实际上此时很大的N使得h(t)也足够大到无需