Ignore:
Timestamp:
Jun 21, 2007, 2:47:26 PM (15 years ago)
Author:
charles
Message:

adding experimental implementation of Tamilmani's `Swift' tit-for-tat algorithm for testing. To tweak or disable, change the values around line 50 of libtransmission/peer.c

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/peer.c

    r2149 r2177  
    2626#include "peertree.h"
    2727
     28/*****
     29******
     30*****/
     31
     32/**
     33*** The "SWIFT" system is described by Karthik Tamilmani,
     34*** Vinay Pai, and Alexander Mohr of Stony Brook University
     35*** in their paper "SWIFT: A System With Incentives For Trading"
     36*** http://citeseer.ist.psu.edu/tamilmani04swift.html
     37**/
     38
     39/**
     40 * Use SWIFT?
     41 */
     42static const int SWIFT_ENABLED = 1;
     43
     44/**
     45 * For every byte the peer uploads to us,
     46 * allow them to download this many bytes from us
     47 */
     48static const double SWIFT_REPAYMENT_RATIO = 1.1;
     49
     50/**
     51 * Allow new peers to download this many bytes from
     52 * us when getting started.  This can prevent gridlock
     53 * with other peers using tit-for-tat algorithms
     54 */
     55static const int SWIFT_INITIAL_CREDIT = 64 * 1024; /* 64 KiB */
     56
     57/**
     58 * We expend a fraction of our torrent's total upload speed
     59 * on on largesse by uniformly distributing free credit to
     60 * all of our peers.  This too helps prevent gridlock.
     61 */
     62static const double SWIFT_LARGESSE = 0.05; /* 5% of our UL */
     63
     64/**
     65 * How frequently to extend largesse-based credit
     66 */
     67static const int SWIFT_REFRESH_INTERVAL_SEC = 5;
     68
     69/*****
     70******
     71*****/
     72
    2873#define PERCENT_PEER_WANTED     25      /* Percent before we start relax peers min activeness */
    2974#define MIN_UPLOAD_IDLE         60000   /* In high peer situations we wait only 1 min
     
    4085                                            during high peer situations */
    4186#define MAX_REQUEST_COUNT       32
    42 #define OUR_REQUEST_COUNT       8 /* TODO: we should detect if we are on a
     87#define OUR_REQUEST_COUNT       12 /* TODO: we should detect if we are on a
    4388                                      high-speed network and adapt */
    4489#define PEX_PEER_CUTOFF         50 /* only try to add new peers from pex if
     
    151196
    152197    char              * client;
     198
     199    int64_t             credit;
    153200};
    154201
     
    191238    peer->port = port;
    192239    peer->from = from;
     240    peer->credit = SWIFT_INITIAL_CREDIT;
    193241    if( s >= 0 )
    194242    {
     
    220268    tr_bitfieldFree( peer->blamefield );
    221269    tr_bitfieldFree( peer->banfield );
    222     if( peer->buf )
    223     {
    224         free( peer->buf );
    225     }
    226     if( peer->outMessages )
    227     {
    228         free( peer->outMessages );
    229     }
     270    tr_free( peer->buf );
     271    tr_free( peer->outMessages );
    230272    if( peer->status > PEER_STATUS_IDLE )
    231273    {
     
    331373        if( NULL != tor )
    332374        {
    333             tr_rcTransferred( peer->download, ret );
    334             tr_rcTransferred( tor->download, ret );
    335             if ( !tor->customDownloadLimit )
    336             {
    337                 tr_rcTransferred( tor->handle->download, ret );
    338             }
    339            
    340375            if( tr_peerAmInterested( peer ) && !tr_peerIsChoking( peer ) )
    341376            {
     
    360395}
    361396
    362 uint64_t tr_peerDate( tr_peer_t * peer )
     397uint64_t tr_peerDate( const tr_peer_t * peer )
    363398{
    364399    return peer->date;
    365 }
    366 
    367 /***********************************************************************
    368  * tr_peerId
    369  ***********************************************************************
    370  *
    371  **********************************************************************/
    372 uint8_t * tr_peerId( tr_peer_t * peer )
    373 {
    374     return & peer->id[0];
    375400}
    376401
     
    390415 *
    391416 **********************************************************************/
    392 uint8_t * tr_peerHash( tr_peer_t * peer )
     417const uint8_t * tr_peerHash( const tr_peer_t * peer )
    393418{
    394419    return parseBufHash( peer );
     
    406431    uint8_t * p;
    407432    uint64_t date;
     433    const int isSeeding = tr_cpGetStatus( tor->completion ) != TR_CP_INCOMPLETE;
    408434
    409435    if( ( ret = checkPeer( peer ) ) )
     
    512538    while( ( p = blockPending( tor, peer, &size ) ) )
    513539    {
     540        if( SWIFT_ENABLED && !isSeeding && (peer->credit<0) )
     541        {
     542            break;
     543        }
     544
    514545        if( tor->customUploadLimit
    515546            ? !tr_rcCanTransfer( tor->upload )
     
    530561
    531562        blockSent( peer, ret );
    532         tr_rcTransferred( peer->upload, ret );
    533         tr_rcTransferred( tor->upload, ret );
    534         if ( !tor->customUploadLimit )
    535         {
    536             tr_rcTransferred( tor->handle->upload, ret );
    537         }
     563
     564        if( ret > 0 )
     565            tr_peerGotBlockFromUs( peer, ret );
    538566
    539567        tor->uploadedCur += ret;
     
    555583
    556584    /* Ask for a block whenever possible */
    557     if( tr_cpGetStatus( tor->completion ) == TR_CP_INCOMPLETE
     585    if( !isSeeding
    558586        && !peer->amInterested
    559587        && tor->peerCount > TR_MAX_PEER_COUNT - 2 )
     
    605633}
    606634
    607 /***********************************************************************
    608  * tr_peerIsConnected
    609  ***********************************************************************
    610  *
    611  **********************************************************************/
    612 int tr_peerIsConnected( tr_peer_t * peer )
     635int tr_peerIsConnected( const tr_peer_t * peer )
    613636{
    614637    return PEER_STATUS_CONNECTED == peer->status;
    615638}
    616639
    617 /***********************************************************************
    618  * tr_peerIsIncoming
    619  ***********************************************************************
    620  *
    621  **********************************************************************/
    622 int tr_peerIsFrom( tr_peer_t * peer )
     640int tr_peerIsFrom( const tr_peer_t * peer )
    623641{
    624642    return peer->from;
    625643}
    626644
    627 int tr_peerAmChoking( tr_peer_t * peer )
     645int tr_peerAmChoking( const tr_peer_t * peer )
    628646{
    629647    return peer->amChoking;
    630648}
    631 int tr_peerAmInterested( tr_peer_t * peer )
     649int tr_peerAmInterested( const tr_peer_t * peer )
    632650{
    633651    return peer->amInterested;
    634652}
    635 int tr_peerIsChoking( tr_peer_t * peer )
     653int tr_peerIsChoking( const tr_peer_t * peer )
    636654{
    637655    return peer->peerChoking;
    638656}
    639 int tr_peerIsInterested( tr_peer_t * peer )
     657int tr_peerIsInterested( const tr_peer_t * peer )
    640658{
    641659    return peer->peerInterested;
     
    647665 *
    648666 **********************************************************************/
    649 float tr_peerProgress( tr_peer_t * peer )
     667float tr_peerProgress( const tr_peer_t * peer )
    650668{
    651669    return peer->progress;
     
    657675 * Returns peer's listening port in host byte order
    658676 **********************************************************************/
    659 int tr_peerPort( tr_peer_t * peer )
     677int tr_peerPort( const tr_peer_t * peer )
    660678{
    661679    return ntohs( peer->port );
    662680}
    663681
    664 /***********************************************************************
    665  * tr_peerBitfield
    666  ***********************************************************************
    667  *
    668  **********************************************************************/
    669 tr_bitfield_t * tr_peerBitfield( tr_peer_t * peer )
    670 {
    671     return peer->bitfield;
    672 }
    673 
    674 float tr_peerDownloadRate( tr_peer_t * peer )
     682int tr_peerHasPiece( const tr_peer_t * peer, int pieceIndex )
     683{
     684    return tr_bitfieldHas( peer->bitfield, pieceIndex );
     685}
     686
     687float tr_peerDownloadRate( const tr_peer_t * peer )
    675688{
    676689    return tr_rcRate( peer->download );
    677690}
    678691
    679 float tr_peerUploadRate( tr_peer_t * peer )
     692float tr_peerUploadRate( const tr_peer_t * peer )
    680693{
    681694    return tr_rcRate( peer->upload );
     
    694707}
    695708
    696 uint64_t tr_peerLastChoke( tr_peer_t * peer )
     709uint64_t tr_peerLastChoke( const tr_peer_t * peer )
    697710{
    698711    return peer->lastChoke;
     
    704717}
    705718
    706 int tr_peerIsOptimistic( tr_peer_t * peer )
     719int tr_peerIsOptimistic( const tr_peer_t * peer )
    707720{
    708721    return peer->optimistic;
    709722}
    710723
    711 static inline int peerIsBad( tr_peer_t * peer )
    712 {
    713     return ( peer->badPcs > 4 + 2 * peer->goodPcs );
    714 }
    715 
    716 static inline int peerIsGood( tr_peer_t * peer )
    717 {
    718     return ( peer->goodPcs > 3 * peer->badPcs );
     724static int peerIsBad( const tr_peer_t * peer )
     725{
     726    return peer->badPcs > 4 + 2 * peer->goodPcs;
     727}
     728
     729static int peerIsGood( const tr_peer_t * peer )
     730{
     731    return peer->goodPcs > 3 * peer->badPcs;
    719732}
    720733
     
    796809    return count * 6;
    797810}
     811
     812/***
     813****
     814***/
     815
     816void
     817tr_peerSentBlockToUs ( tr_peer_t * peer, int byteCount )
     818{
     819    tr_torrent_t * tor = peer->tor;
     820
     821    tr_rcTransferred( peer->download, byteCount );
     822    tr_rcTransferred( tor->download, byteCount );
     823    if ( !tor->customUploadLimit )
     824        tr_rcTransferred( tor->handle->download, byteCount );
     825
     826    peer->credit += (int)(byteCount * SWIFT_REPAYMENT_RATIO);
     827}
     828
     829void
     830tr_peerGotBlockFromUs ( tr_peer_t * peer, int byteCount )
     831{
     832    tr_torrent_t * tor = peer->tor;
     833
     834    tr_rcTransferred( peer->upload, byteCount );
     835    tr_rcTransferred( tor->upload, byteCount );
     836    if ( !tor->customDownloadLimit )
     837        tr_rcTransferred( tor->handle->upload, byteCount );
     838
     839    peer->credit -= byteCount;
     840}
     841
     842static void
     843tr_torrentSwiftPulse ( tr_torrent_t * tor )
     844{
     845    int i;
     846    int deadbeatCount = 0;
     847    tr_peer_t ** deadbeats;
     848
     849    tr_lockLock( &tor->lock );
     850
     851    deadbeats = tr_calloc( tor->peerCount, sizeof(tr_peer_t*) );
     852    for( i=0; i<tor->peerCount; ++i ) {
     853        tr_peer_t * peer = tor->peers[ i ];
     854        if( tr_peerIsConnected( peer ) && ( peer->credit < 0 ) )
     855            deadbeats[deadbeatCount++] = peer;
     856    }
     857
     858    if( deadbeatCount )
     859    {
     860        const double ul_KiBsec = tr_rcRate( tor->upload );
     861        const double ul_KiB = ul_KiBsec * SWIFT_REFRESH_INTERVAL_SEC;
     862        const double ul_bytes = ul_KiB * 1024;
     863        const double freeCreditTotal = ul_bytes * SWIFT_LARGESSE;
     864        const int freeCreditPerPeer = (int)( freeCreditTotal / deadbeatCount );
     865        for( i=0; i<deadbeatCount; ++i )
     866            deadbeats[i]->credit = freeCreditPerPeer;
     867        tr_dbg( "torrent %s has %d deadbeats, "
     868                "who are each being granted %d bytes' credit "
     869                "for a total of %.1f KiB, "
     870                "%d%% of the torrent's ul speed %.1f\n",
     871            tor->info.name, deadbeatCount, freeCreditPerPeer,
     872            ul_KiBsec*SWIFT_LARGESSE, (int)(SWIFT_LARGESSE*100), ul_KiBsec );
     873    }
     874
     875    free( deadbeats );
     876
     877    tr_lockUnlock( &tor->lock );
     878}
     879void
     880tr_swiftPulse( tr_handle_t * h )
     881{
     882    static time_t lastPulseTime = 0;
     883    const time_t now = time (NULL);
     884    tr_torrent_t * tor;
     885
     886    if( lastPulseTime + SWIFT_REFRESH_INTERVAL_SEC > now )
     887        return;
     888    lastPulseTime = now;
     889
     890    for( tor=h->torrentList; tor; tor=tor->next )
     891        tr_torrentSwiftPulse( tor );
     892}
Note: See TracChangeset for help on using the changeset viewer.