BT算法汇总Word文件下载.docx
- 文档编号:4531728
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:19
- 大小:573.59KB
BT算法汇总Word文件下载.docx
《BT算法汇总Word文件下载.docx》由会员分享,可在线阅读,更多相关《BT算法汇总Word文件下载.docx(19页珍藏版)》请在冰点文库上搜索。
2、Arrays.fill(availability,0)
3、对于下载任务中的所有连接进行相同操作
for(inti=_peer_transports.size-1;
i>
=0;
i--)
1)将与client的第i个连接付给pc
2)得到该pc对应的peer拥有piece的可用性布尔变量数组piecesAvailable
3)如果此数组piecesAvailable不为空:
遍历任务中所有pieces,若在pc中可用,则将对应piece的可用性加1
4、加入本机拥有piece的可用性
5、将availability复制到_availability:
System.arraycopy(availability,0,_availability,0,availability.length)
备注:
类System中的成员方法arraycopy:
publicstaticvoidarraycopy(Objectsrc,intsrc-position,Objectdst,intdst-position,intlength)
2得到最小可用性:
line1641:
publicfloatgetMinAvailability(){
inttotal=0;
intnbPieces;
//piece数目
intallMin;
synchronized(_availability){//可用性整形数组:
privateint[]_availability;
nbPieces=_availability.length;
//得到piece数目
if(nbPieces==0)
return0;
allMin=_availability[0];
for(inti=0;
i<
nbPieces;
i++){
if(_availability[i]<
allMin)
allMin=_availability[i];
}
if(_availability[i]>
total++;
returnallMin+(total/(float)nbPieces);
得到所有piece中出现的最小频率值
1、定义变量:
privateint[]_availability;
可用性数组
inttotal=0;
intallMin;
一个保存出现频率最小的piece的频率值
intnbPieces;
记录piece数目
2、将可用性数组_availability的长度作为piece数nbPieces
3、如果没有可用piece,即nbPieces=0,函数返回0
4、将第一个可用性数组中piece的可用性赋给allMin
5、遍历所有piece,将每个piece的可用性与allMin比较,最后得出所有piece中出现频率的最小值
6、遍历所有piece,将每个piece的可用性与allMin比较,记录可用性大于allMin的piece个数total
7、函数最后返回实型数:
allMin+(total/(float)nbPieces)
DownloadManagerStatsImpl.java:
Line319:
publicfloatgetAvailability()
{
PEPeerManagerpm=download_manager.getPeerManager();
if(pm==null){
return(-1);
return(pm.getMinAvailability());
PEPeerControlImpl.java:
Line1635:
publicintgetAvailability(intpieceNumber){
synchronized(_availability){
return_availability[pieceNumber];
Line1663:
publicint[]getAvailability(){
return_availability;
区别:
getAvailable()?
?
3得到稀有piece:
Line1044:
privatevoidgetRarestPieces(PEPeerTransportpc,intrangePercent)
按照指定范围得到指定节点拥有的稀有piece
1、得到某个pc对应的peer拥有piece的可用性布尔数组pieceAvailable
2、Arrays.fill(_piecesRarest,false)
3、设标记piece最小可用性等级的变量pieceMinAvailability(指网络中每个piece的可下载个数),赋初值为-1
4、扫描任务重所有的piece,确定出pieceMinavailability
5、pieceMinAvailability=((100+rangePercent)*pieceMinAvailability)/100
6、如果10<
pieceMinAvailability<
999,则pieceMinAvailability=999。
即确保网络中的种子足够多,下载哪个piece都行
7、遍历任务重所有pieces,如果第i个piece没有已下载完,没有正在下载中,而且该piece可用时:
若其最小可用性小于最小可用性等级(_availability[i]<
=pieceMinAvailability),
则:
置此piece为稀有(_piecesRarest[i]=true)
4得到可以下载的piece:
Line923:
findPieceToDownload(PEPeerTransportpc)
检查一个给定peer,它的哪个block可以被下载
算法:
1、确立一个稀有piece列表
2、如果piece中的block已经被请求而且没有下载完,继续下载
3、如果一个piece所有block下载完,则通过最小可用性“随机”选择一个新的piece
4、如果找不到新的piece,意味所有piece已经下载完,返回false
1、调用getRarestPieces(pc,90),得到一个稀有piece列表;
2、如果布尔数组_piecesRarest为空,即没有稀有piece,返回false
3、设整形变量稀有piece数nbPieceRarest为0
4、遍历稀有piece数组,得到稀有piece数
5、如果没有piece可以下载,即稀有piece数为0,返回false
6、设piece数pieceNumber、block数blockNumber、最近完成下载数lastCompleted的初值均为-1
7、对于所有piece,进行相同操作:
如果第i个piece不为空,没有正在下载,而且是稀有piece,则:
1)得到并标记piece中一个block,将它的索引号付给整形变量tempBlock
2)如果此tempBlock不为-1,则:
A、如果第i个piece已经下载数目大于最近一次piece的下载数,则:
a、若先前的piece序号不为-1,则取消对其block的请求
b、将现在的piece序号付给pieceNumber
c、tempBlock付给blockNumber
B、如果第i个piece已经下载数目不大于上一次piece的下载数,则:
取消对此piece的第tempBlock块的请求
3)如果此tempBlock为-1,则此piece没有可以下载的block,置_piecesRarest[i]
为假,nbPiecesRarest减1
8、如果pieceNumber、blockNumber均不为-1,则请求下载此piece的blockNumber块,返回true
9、如果没有稀有piece,返回false
//如果此piece中没有可以下载的block,“随机”选择另一个piece
10、调用getRarestPieces(pc,20)
11、调用磁盘管理器函数getPiecenumberToDownload(boolean[]_piecesRarest),将得到的piece序号付给pieceNumber
注:
DiskManagerImpl.java:
Line2113:
publicintgetPiecenumberToDownload(boolean[]_piecesRarest)
12、如果pieceNumber为-1,返回false
13、建立类型为PEPieceImpl对象piece,赋初值null
14、得到最后一个piece付给piece
15、增加一个piece:
pieceAdded(piece)
16、对于_pieces数组的第pieceNumber个元素赋值为piece
17、得到并标记此piece中的block为请求状态,把序号付给blockNumber
18、请求pc连接中第pieceNumber个piece的第blockNumber个block进行下载
最佳无阻塞算法:
Chocking的原因有很多。
当同一时刻通过多个连接发送数据时,TCP拥塞控制的效果很差。
这样,Choking就允许Peers使用一种tit-for-tat-ish算法来确保他们获得一个稳定的下载速率。
下面介绍的Choking算法是目前BT客户端中所广泛采用的。
很重要的一点是,所有新的算法既能用在包含他们全部的网络上,也能用在只包含此算法的网络上。
好的Choking算法应该满足如下准则:
1.为了获得好的TCP性能,它应限制同时上传的数量;
2.应避免阻塞和非阻塞状态的频繁切换(Fibrillation);
3.应该酬谢让自己下载的Peer,为它提供上载;
4.当发现更好的连接(相对于当前的连接)的时候,试图启用他们,称作OptimisticUnchoking。
目前使用的Choking算法中避免Fibrillation(抖动)的唯一策略是:
每10秒更新被阻塞的Peers。
酬谢(Reciprocation)和限制上传的数目通过解除(对自己感兴趣的且拥有最好的上载速率的)4个Peers的阻塞来管理。
这样可以获得最大的下载速率。
而这四个Peers因对己感兴趣而成为下载者。
拥有更好的上载速率(相对于下载者而言)但对自己不感兴趣的Peer被阻塞,但一旦当它对自己感兴趣,则阻塞上载速率最慢的下载者,使其取而代之成为新的下载者。
如果一个Client拥有完整的资源文件,则它将根据上载速率而不是下载速率来决定阻塞哪些Peer。
对于OptimisticUnchoked,在任意时刻都会有一个不被阻塞的Peer而不管它的上载速率如何(如果它对自己感兴趣,则成为4个下载者中的一员),至于哪一个Peer被OptimisticUnchoked,会每30秒更新一次。
最新连接的Peer成为OptimisticUnchoked的可能性是其他Peers的3倍,这将给他们一个很好的机会去完成一个Piece的上载。
1预备最佳无阻塞节点:
Line1210:
privatevoidprepareBestUnChokedPeers(intnumUpRates)
预备最佳无阻塞节点
传递参数:
上传节点数目
1)如果没有节点,返回
2)建立长整形数组upRates,大小为numUpRates
3)建立最佳上传者列表bestUploaders
4)对于所有client-peer连接,进行同样下述操作:
对类型为PEPeerTransport对象pc赋初值:
null;
将第i个连接付给pc;
如果client对peer感兴趣而且peer被client阻塞:
将pc.getStats().getReception()付给长整形变量upRate
调用:
testAndSortBest(upRate,upRates,pc,bestUploaders,0):
如果最佳无阻塞列表为空或者没有连接,返回;
如果最佳无阻塞列表中包括此连接,返回;
5)遍历最优上传者列表,向每个最优列表中的pc发送unChoke消息
2得到最佳无阻塞节点:
Line1239:
privateListgetBestUnChokedPeers(intnbUnchoke)
得到最佳无阻塞peers
问题:
长整形数组upRates,长整形数upRate的意义;
Line1256:
if(upRate>
256)testAndSortBest(upRate,upRates,pc,bestUploaders,0);
Line1277:
_manager.getStats().getUploaded()/(_manager.getStats().getDownloaded()+16000))<
10)
3完成最佳无阻塞:
Line1322:
privatevoidperformOptimisticUnChoke()
完成最佳无阻塞
1、设计数器index=0;
2、对于所有client-peer连接进行循环:
将第i个连接付给类型为PEPeerTransport对象pc;
如果pc与类型为PEPeerTransport对象currentOptimisticUnchoke相等,则index加1
3、如果index大于所有连接数,置index为0;
4、设currentOptimisticUnchoke为空;
5、
防冷落算法:
偶然情况下,BT的peer端可能会被它下载的所有的peers端阻塞。
这种情况下,此peer端的下载速率就很低,直到优化unchock算法找到更好的peers端。
为了消除这个问题,当超过一分钟一个peer没有从特定的peer得到一个piece那么BT就认为它被那个peer冷落。
并不上传给它直到优化unchoke(这是对于上述的优化unchocke算法的一个例外),这就常常会使多于一个peers同时进入优化unchoke状态。
从而使下载速率快速恢复。
Line760:
privatevoidcheckRequests()
取消超时请求,标记peer为冷落状态;
防冷落算法
对于cliect与所有peers进行相同操作:
1、得到第i个连接,付给类型为PEPeerTransport的对象pc
2、如果此pc状态为正在传输,则:
建立request超时列表;
如果列表不为空而且长度大于0,则:
结束算法:
当下载将要结束时,将会趋向最后的几个piece-sections下载减慢,为了加速下载,客户端向所有peers发送请求下载其没有的piece。
为了保证传输过多的冗余数据而到是性能下降,客户端一旦收到piece-sections,向所有的其他peers发送cancel消息。
至于什么时候启动ENDGAME算法。
规范没有给出推荐值。
EndGameModeChunk.java中:
声明了公共类EndGameModeChunk,chunk是实现类的对象:
EndGameModeChunkchunk=(EndGameModeChunk)endGameModeChunks.get(random);
//随机得到一个进入结束算法的对象chunk
//Thelistofchunksneedingtobedownloaded
privateListendGameModeChunks;
intnbChunks=endGameModeChunks.size();
超级种子算法:
超级种子概念不是老版本BT协议的一部分。
S5.5中的超级种子的概念是为帮助那些自身带宽有限(对支持大的Torrent来说)的发起者而设计的一种新的做种算法,它能使发起者减少需要上传的数据量以便spawnnewseedsinthetorrent。
当一个做种的Client进入了超级种子模式,它的行为将不同于普通的做种者,而是扮成一个不拥有任何数据的普通Client。
当其他的Client和它建立连接之后,它将通知这些Clients自己收到了一个从未被发送过的Piece(所有Piece都被发送过的情况是很罕见的),这就使得Clients只试图下载这一个Piece(而没有其他想法)。
当Clients下载完这个Piece后,超级种子不再通知他们下载其他的Pieces直到它看到刚刚传送的那一个Piece已经被至少一个其他的Client提供下载。
因此在那之前,Clients都不会访问超级种子的其他Pieces,这样就节省了超级种子的带宽。
这种方法将提高做种的效率,既让Peers去下载最稀有的数据(降低了传送的多余数据量),又限制了传送给Peers的对Swarm没有任何贡献的数据量。
这种算法未出现之前,一个种子在其他Client成为种子之前,可能需要上传150%~200%于Torrent的数据量。
而现在,一个运行在超级种子模式下的Client(对一个大的Torrent做种),只需要上传105%于Torrent的数据量。
这相当于一个普通种子做种效率的150%~200%。
但是,在通常情况下不建议使用超级种子模式。
虽然它有助于稀有数据的分发(因为它对Client的下载选择做出了限制,同时也限制了Clients下载已经部分得到的数据),所以超级种子模式只适用于那些最初做种的Server。
SuperSeedPeer.java:
publicclassSuperSeedPeerimplementsComparable{
publicPEPeerpeer;
publicSuperSeedPeer(PEPeerpeer){
this.peer=peer;
}
publicintcompareTo(Objectobj){
SuperSeedPeerotherPeer=(SuperSeedPeer)obj;
returnthis.peer.getUploadHint()-otherPeer.peer.getUploadHint();
}
SuperSeedPiece.java
1、声明一组变量:
piece索引号:
privateintpieceNumber;
privateintlevel;
//开始进入超级种子模式时,level=0
//当superseed有peer没有的piece时,level=1
//当一个peer收到superseed的piece时,level=2
第一次分配时间:
privatelongtimeFirstDistributed;
第一个接收者:
privatePEPeerfirstReceiver;
到达另一个peer的时间:
privateinttimeToReachAnotherPeer;
2、构造函数:
publicSuperSeedPiece(PEPeerControlmanager,intpieceNumber)
3、同步代码块:
publicsynchronizedvoidpeerHasPiece(PEPeerpeer)
功能:
根据不同的level得到firstReceiver
4、获得level数值:
publicintgetLevel()
5、同步代码块:
向peer显示已经有的piece
publicsynchronizedvoidpieceRevealedToPeer()
6、返回piece序号:
publicintgetPieceNumber()
7、剩余peer
publicvoidpeerLeft()
8、publicvoidupdateTime()
遗留问题:
1、privateintlevel;
//level的含义
2、publicsynchronizedvoidpeerHasPiece(PEPeerpeer);
//不知道此函数是否理解正确
3、publicvoidsetUploadHint(inttimeToSpread);
//此函数的含义
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- BT 算法 汇总