刘衍珩, 伊泽众, 王爱民, 李松江
吉林大学 计算机科学与技术学院，吉林 长春 130012
收稿日期: 2014-10-13
基金项目: 国家自然科学基金资助项目(61373123).
作者简介: 刘衍珩(1958-)，男，吉林长春人，吉林大学教授，博士生导师。

摘要: 针对BitTorrent网络中节点的“搭便车”行为会严重影响正常节点的下载进度以及整个网络性能的问题，提出了一种基于“以牙还牙”机制的经济模型.类比于现实社会的商品交易以及信用体系，在考虑了节点的上传下载行为的周期性表现以及文件块在节点中的动态分布状况后，设计了由节点财富值、文件块的定价以及节点透支额度组成的BitTorrent经济模型；并将该经济模型应用到“以牙还牙”机制中.在提出的经济模型中，节点间的资源传播作为一种交易，在未达到透支额度条件下节点按照文件块的定价进行交易，从而使得节点的财富值发生变化.仿真实验结果表明：在相似的资源传播速度下，该经济模型对free-rider节点的屏蔽效果要明显优于单纯的“以牙还牙”机制.
关键词：BitTorrent搭便车“以牙还牙”经济模型
Economic Model of BitTorrent Network Based on Tit-for-Tat
LIU Yan-heng, YI Ze-zhong, WANG Ai-min, LI Song-jiang
College of Computer Science and Technology, Jilin University, Changchun 130012, China
Corresponding author: WANG Ai-min, E-mail: yzzwolf@aliyun.com
Abstract: To solve the problem that the free-riding behavior of a node will seriously affect the download progress of the common node and the whole network performance in the BT network, a new economic model (TTEM) was proposed based on the tit-for-tat mechanism. According to the commodity trading and credit system in the social life, the economic model was presented that consisted of the node wealth, the file blocks pricing and the node overdraft. Finally, the TTEM was proposed by deploying the economic model on the tit-for-tat. Resources spread between nodes as a transaction in TTEM. Nodes were traded by the price of the file blocks, making the wealth of the node change, if the node’s wealth is greater than the overdraft. The simulation results show TTEM is able to reduce the impact which the free-rider nodes make on the BT network than the pure tit-for-tat mechanism under the similar propagation velocity of the file resources.
Key Words: BitTorrentfree-ridingtit-for-tateconomic model
区别于B/S，C/S网络模式的Peer-to-Peer(P2P)网络模式发展日趋成熟，尤其是近些年，越来越多的P2P应用进入网络世界，其中应用最广、影响最大的当属2003年Cohen提出的BitTorrent^[1].
BitTorrent协议作为架构于TCP/IP之上的一种P2P文件传输协议，其最大的特点是用户越多，下载完成所花费的时间越少.但是BitTorrent网络中普遍存在着多下载少上传，甚至只下载不上传的自私行为(该行为称为free-riding行为，具有该行为的节点称为free-rider节点^[2-7]).在BitTorrent网络中，如果不能有效地屏蔽free-rider节点，那么这些节点将占用大量的带宽，严重降低正常节点的下载质量.BitTorrent协议中的“tit-for-tat”机制实现了对节点下载行为的控制，能够限制free-rider节点的下载行为.“tit-for-tat”机制包括三部分：choke，unchoke和optimistic unchoke.
虽然“tit-for-tat”机制能够在一定程度上控制free-rider节点，但是“tit-for-tat”中leecher节点(指需要从邻居节点处下载文件块的节点)的optimistic unchoke策略以及seeder节点(指拥有所有文件块的节点)的节点选择策略使得free-rider节点仍有机会获益；在稳定的BitTorrent网络中，free-rider节点往往能够完成所需文件的下载^[8].文献[4]提出了一种适用于P2P网络的微支付经济模型，设计出一种基于虚拟货币的资源定价体系；该文用节点的虚拟货币量标志节点对网络的贡献度，以此判断节点的free-riding行为.文献[5]在对基于BitTorrent协议的DIME³分享网站研究之后，提出了DIME经济模型；在DIME模型中，文章提出种子年龄以及再销售的概念.以上两种控制策略虽然对free-rider节点有较好的屏蔽效果，但是其完全摒弃了“tit-for-tat”机制，实现较为复杂，在现有的BitTorrent客户端中应用较少.本文提出了基于“tit-for-tat”机制的BitTorrent网络经济模型，简称为TTEM.TTEM将经济学中基本的商品交易原理应用到“tit-for-tat”机制中，把文件资源看作一种商品，而节点就是商品的购买者和出售者；通过商品交易体系控制free-rider节点的下载行为.
1 BitTorrent经济模型将BitTorrent网络与市场经济类比，文件资源作为一种商品，而节点就是该商品的出售者或者消费者.
简单市场经济模型中商品的流动以及价格的变化完全由自由市场中商品的供求关系所引导.根据简单市场经济模型在BitTorrent网络中构建经济模型，将节点行为看作以文件资源为商品的个体间的交易行为.通过对节点财富值、文件块的定价以及节点透支额度的设计，完成BitTorrent经济模型的构建.
1.1 节点财富值节点财富值是一个节点所拥有的虚拟货币量，该值是节点的全局属性值.节点财富值是一个累积值，能够反映节点在整个生命周期中的行为.本文研究的是对free-rider节点的控制策略，因此不涉及节点对其财富值的篡改等带有欺骗性质的攻击性行为.
1.2 文件块的定价可以将文件块在节点中的分布情况看成文件块的供求信息，因此根据文件块在节点中的稀缺程度对其进行定价.由于交易双方的邻居节点不一定完全相同，这使得它们对同一文件块的稀有程度的定义有所不同，因此会致使它们对同一个文件块的定价有所不同.上传节点对文件块的定价称为上传价格，也就是下载节点所要支付的货币量；下载节点对文件块的定价称为下载价格，也就是上传节点能够获得的货币量.文件块A的价格可表示为

(1)

式中：price_A是文件块A的价格；β,γ是价格调整因子；cover_rate_A为文件覆盖率，当其为0时说明没有节点声明拥有文件块A，所以，文件块A不会被任何节点请求.
cover_rate_A的请求模型为

(2)

式中：size为邻居节点的数量；hava(i,A)表示节点i是否拥有文件块A，如果有，则hava(i,A)=1，否则，hava(i,A)=0.
根据文件块的稀有程度进行定价，既保证了与BitTorrent协议最少优先下载策略的一致性，又反映出商品价格随着供求情况变化的普遍经济学原理.式(1)采用反函数的方式，在保证最低复杂度前提下将文件块价格与其稀有度建立关联，还能够体现出供不应求时“物以稀为贵”、供大于求时物价降低的规律；两个价格调整因子β，γ可以控制文件块的价格在一个可接收的范围内变化.文件块的数量越大，每个文件块越是需要得到更快地传播.
1.3 节点透支额度节点透支额度(OVERDRAFT)由节点在一定时间周期内的上传下载量决定，对周期内上传量大的节点赋予较大的透支额度，保证该节点能够尽早下载到自己所需要的文件块(尤其是稀有文件块)，从而有利于稀有文件块的传播.根据节点周期性的上传下载行为给出了节点透支额度的计算公式：

(3)

式中:W₀表示节点的初始财富值；μ是透支额度的调整因子；up_ij为节点i在前一choke周期内为邻居节点j上传的文件块数量；down_ji为节点i在前一choke周期内从邻居节点j下载的文件块数量；不为0.
由节点财富值、文件块的定价和节点透支额度组成的BitTorrent经济模型，能够降低不积极上传的节点(包括free-rider节点)获得稀有文件块的概率，从而加快稀有文件块的传播速度.
2 TTEM将BitTorrent经济模型融合到“tit-for-tat”机制中，通过改变choke/unchoke/optimistic unchoke策略达到更好地抑制free-rider节点的效果.
2.1 更新邻居节点财富值节点在一个choke周期之后会向邻居节点发送自己的财富值信息，邻居节点收到该信息之后会更新邻居列表中的相关信息.如果节点没有发送财富信息，邻居节点会向该节点发送“试探”信息，节点收到该信息后向邻居节点发送自己的财富值等信息；如果邻居节点发送的“试探”信息未得到响应，则在邻居列表中移除该节点.
2.2 交易过程根据文献[9]中FairTrade模型对节点间交易行为的描述并结合“tit-for-tat”机制，将TTEM中节点的交易描述如下(以节点i向邻居节点j请求文件块Block_A为例)：
步骤1 节点j在下载完Block_A后，根据其邻居节点的文件块信息，计算Block_A的稀有度，并完成对Block_A的上传定价，然后将HAVE信息以及Block_A的上传价格发送给节点i.
步骤2 节点i收到由节点j发送来的HAVE信息以及Block_A的上传价格后，根据Block_A在其邻居节点中的稀有度完成对Block_A的下载定价，向节点j发送INTEREST信息和下载定价信息，并等待节点j向自己发送UNCHOKE信息.
步骤3 节点i收到节点j的UNCHOKE信息后向其发送REQUEST信息.
步骤4 节点j收到节点i的请求后，根据Block_A的上传定价减少节点i的虚拟货币量，然后将Block_A发送给节点i；节点i收到Block_A后，根据下载定价增加节点j的虚拟货币量.
2.3 节点选择对于leecher(或者seeder)节点i，在执行optimistic unchoke策略时要将邻居节点j的财富值作为一种选择因子，在遍历邻居节点的同时将财富值大于其OVERDRAFT_j的节点加入待选列表中.当遍历结束后，节点i在待选列表中随机选择一个邻居节点，将该邻居节点标记为unchoke状态，并向其发送unchoke通知.
对于seeder节点i，在执行choke/unchoke策略时，不仅要考虑邻居节点j的下载带宽，还要将邻居节点j当前拥有的虚拟货币量作为是否choke/unchoke节点j的一种影响因子.如果邻居节点j的虚拟货币量低于其当前可透支额度OVERDRAFT_j，则无论该邻居节点的下载带宽有多大，节点i都要对该邻居节点执行choke方法.当有多个邻居节点的虚拟货币量未达到透支额度时，节点i按照原“tit-for-tat”中的choke算法对其邻居节点进行choke/unchoke.如果邻居节点的财富值都低于其当前可透支额度，那么seeder节点i就按照邻居节点财富值递减的顺序unchoke邻居节点.
财富值作为节点的全局属性信息，以其为标准对邻居节点作出选择，执行choke/unchoke/optimistic unchoke策略，改变了“tit-for-tat”机制中只关注邻居节点对自己的帮助而忽视了对整个网络的贡献的缺陷，有助于发现上传能力更强、对整个网络贡献更大的节点，从而保证文件块的传播速度.由于无攻击性的free-rider节点“只下载不上传”，因此其财富值在某一时刻一定会低于透支额度，从而得不到unchoke机会，也就不能从其他节点那里获得下载带宽.因此，改进后的“tit-for-tat”机制能够明显减少free-rider节点被optimistic unchoke的机会.
3 仿真实验3.1 实验方案仿真实验是在实现了BitTorrent协议的PeerSim^[10]平台上进行的.将TTEM加入到该平台中，实现了对TTEM的仿真模拟.
仿真实验参数设置如表 1所示.
表 1(Table 1)

表 1 实验参数参考值Table 1 Default value of the experiment parameters 参数 值 节点数量 1 000 Tracker数量 1 节点带宽/(kB·s-1) 200 节点邻居数量 20 节点Swarm值 40 种子节点数量 40 free-rider覆盖率 0，20%，40%，60%，80% 文件大小/MB 100 文件块大小/kB 256

表 1 实验参数参考值 Table 1 Default value of the experiment parameters

检测TTEM模型的性能，主要从正常节点平均用时和free-rider节点下载平均用时两方面与“tit-for-tat”机制进行比较.
正常节点下载平均用时：正常节点下载平均用时表示BitTorrent网络中文件资源的传播速度；通过对比该指标可以得出不同控制策略对文件资源的传播速度的影响程度，从而得出其对正常节点的控制作用.正常节点的下载平均用时越大，控制策略的性能越差.
free-rider节点下载平均用时：free-rider节点下载平均用时能够表现出free-rider节点在BitTorrent网络中受益情况；通过对比该指标可以得出不同的控制策略对free-rider节点的控制作用.free-rider节点下载平均用时越大，控制策略对free-rider节点的控制越好.
公式中的调整因子参考值如表 2所示.
表 2(Table 2)

表 2 调整因子参考值Table 2 Default value of the coefficients β γ μ W0 0.2 1 0.02 400

表 2 调整因子参考值 Table 2 Default value of the coefficients

3.2 实验结果由图 1可知，对于不同的free-rider节点覆盖率，TTEM模型下的正常节点下载平均用时均小于“tit-for-tat”机制.随着free-rider节点覆盖率的提高，“tit-for-tat”机制下正常节点的下载平均用时从1 156 s增加到3 927 s，使得正常节点多花费了200%的时间才能把所需的文件资源下载完成.而TTEM模型中，正常节点的下载平均用时只从1 128 s增加到1 430 s；在free-rider覆盖率达到80%的时候，正常节点仅多花费了约27%的时间就将所需的文件资源下载完成.
图 1(Fig. 1)

图 1 不同free-rider节点覆盖率下正常节点的下载平均Fig.1 Mean time of common peers downloaded completely with different free-rider peer coverage

以上数据说明，相比于“tit-for-tat”机制，TTEM模型在不同free-rider覆盖率下都能够保证文件资源在正常节点间保持着良好的传播速度.
图 2中，随着free-rider节点覆盖率的增加，“tit-for-tat”机制下free-rider节点的下载平均用时从1 600 s增加到4 000 s，增加了1.5倍；而在TTEM模型下，平均用时从2 000 s增加到5 500 s，增加了1.75倍.在同一free-rider节点覆盖率下，TTEM模型的下载平均用时均大于“tit-for-tat”机制，并且free-rider节点覆盖率越大，其差别越大，从相差300 s增加到相差1 500 s.
图 2(Fig. 2)

图 2 不同free-rider节点覆盖率下free-rider节点的下载平均用时Fig.2 Mean time of free-rider peers downloaded completely with different free-rider peer coverage

以上数据表明，相比于“tit-for-tat”机制，TTEM模型能有效地控制free-rider节点，并且free-rider节点的覆盖率越大，其控制效果越明显.
以40%的free-rider节点覆盖率为例，分析TTEM模型下正常节点和free-rider节点的下载进度.
图 3中，600 s之后正常节点下载完成率大致呈线性上升，到2 000 s时正常节点下载完成率达到80%，3 000 s时正常节点全部完成下载；而在2 000 s之前，free-rider节点仅下载完成了不到10%，2 000 s之后，free-rider节点才得到充足的资源进行下载.
图 3(Fig. 3)

图 3 节点下载完成率Fig.3 Percent of peers downloaded completely

TTEM模型中，下载前期(2 000 s之前)由于文件块的稀有度高、定价高，free-rider节点如果下载这些文件块，其透支的虚拟货币将很快达到透支额度的限制；正常节点由于能够主动上传资源从而得到收益，抵消下载花费.因此，正常节点能够得到充足的下载带宽，而free-rider节点的下载带宽受到有效限制.下载中后期(2 000 s以后)，正常节点的下载完成率在80%以上，因此free-rider节点的邻居节点中的种子节点覆盖率较高，从而free-rider节点能够获得更多的下载带宽，完成文件资源的下载.
通过分析图 1，图 2和图 3可以得出相比于“tit-for-tat”机制，TTEM模型在保证满足正常节点的下载需求的同时，能够有效地控制free-rider节点的free-riding行为.
4 结论本文提出了基于“tit-for-tat”的BitTorrent网络经济模型(TTEM)，将节点下载、上传文件块的行为看作一种以文件块为商品的交易行为，并通过对节点财富值、“商品”的定价以及“消费者”透支额度限定的设计，实现了对free-rider节点更加有效的屏蔽.原始BitTorrent协议以及TTEM进行的仿真模拟实验结果表明，在文件资源传播速度相似的前提下，TTEM比原始的“tit-for-tat”机制能更好地控制free-rider节点，使得BitTorrent网络的整体性能有明显的提高.
参考文献

[1]	Cohen B.Incentives build robustness in BitTorrent[C]//Workshop on Economics of Peer-to-Peer Systems.Berkeley,2003:68-72.(0)
[2]	Manoharan S, Ge T. A demerit point strategy to reduce free-riding in BitTorrent[J].Computer Communications, 2013, 36(8): 875–880.(0)
[3]	Locher T,Moor P,Schmid S,et al.Free riding in BitTorrent is cheap[C]//Fifth Workshop on Hot Topics in Networks (HotNets).Irvine,2006:85-90.(0)
[4]	Wang Q J,Yu J,Yu M,et al.Economic model based on micro-payment in P2P systems[C]// 1st International Conference on Information Science and Engineering (ICISE).Nanjing,2009:204-206.(0)
[5]	Kash I A,Lai J K,Zhang H,et al.Economics of BitTorrent communities[C]//Proceedings of the 21st International Conference on World Wide Web. Lyon:ACM,2012:221-230.(0)
[6]	Bhakuni A,Sharma P,Kaushal R.Free-rider detection and punishment in BitTorrent based P2P networks[C]//IEEE International Advance Computing Conference (IACC).New Delhi,2014:155-159.(0)
[7]	Shin K,Reeves D S,Rhee I.Treat-before-trick:free-riding prevention for BitTorrent-like peer-to-peer networks[C]//IEEE International Symposium on Parallel & Distributed Processing.Rome,2009:1-12.(0)
[8]	Bharambe A R,Herley C,Padmanabhan V N.Analyzing and improving bittorrent performance[R].Barcelona:Microsoft Research,2006:1-12.(0)
[9]	Saito K,Morino E,Murai J.Fair trading of information:a proposal for the economics of peer-to-peer systems[C]//The First International Conference on Availability,Reliability and Security.Vienna,2006:764-771.(0)
[10]	Jelasity M,Montresor A,Jesi G P.Peersim peer-to-peer simulator[EB/OL].(2005-11-11) [2014-06-15]. http://peersim.sourceforge.net/.(0)