Changeset 2177


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

Location:
trunk/libtransmission
Files:
5 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}
  • trunk/libtransmission/peer.h

    r2004 r2177  
    3030typedef struct tr_peer_s tr_peer_t;
    3131
    32 tr_peer_t * tr_peerInit          ( struct in_addr, in_port_t, int sock, int );
    33 void        tr_peerDestroy       ( tr_peer_t * );
    34 const char *tr_peerClient        ( tr_peer_t * );
    35 void        tr_peerSetPrivate    ( tr_peer_t *, int );
    36 void        tr_peerSetTorrent    ( tr_peer_t *, tr_torrent_t * );
    37 int         tr_peerRead          ( tr_peer_t * );
    38 uint64_t    tr_peerDate          ( tr_peer_t * );
    39 uint8_t *   tr_peerId            ( tr_peer_t * );
    40 uint8_t *   tr_peerHash          ( tr_peer_t * );
    41 int         tr_peerPulse         ( tr_peer_t * );
    42 int         tr_peerIsConnected   ( tr_peer_t * );
    43 int         tr_peerIsFrom        ( tr_peer_t * );
    44 int         tr_peerAmChoking     ( tr_peer_t * );
    45 int         tr_peerAmInterested  ( tr_peer_t * );
    46 int         tr_peerIsChoking     ( tr_peer_t * );
    47 int         tr_peerIsInterested  ( tr_peer_t * );
    48 float       tr_peerProgress      ( tr_peer_t * );
    49 int         tr_peerPort          ( tr_peer_t * );
    50 tr_bitfield_t * tr_peerBitfield  ( tr_peer_t * );
    51 float       tr_peerDownloadRate  ( tr_peer_t * );
    52 float       tr_peerUploadRate    ( tr_peer_t * );
    53 void        tr_peerChoke         ( tr_peer_t * );
    54 void        tr_peerUnchoke       ( tr_peer_t * );
    55 uint64_t    tr_peerLastChoke     ( tr_peer_t * );
    56 void        tr_peerSetOptimistic ( tr_peer_t *, int );
    57 int         tr_peerIsOptimistic  ( tr_peer_t * );
    58 void        tr_peerBlame         ( tr_peer_t *, int piece, int success );
    59 struct in_addr * tr_peerAddress  ( tr_peer_t * );
    60 int         tr_peerGetConnectable( const tr_torrent_t *, uint8_t ** );
     32tr_peer_t * tr_peerInit            ( struct in_addr, in_port_t, int sock, int );
     33void        tr_peerDestroy         ( tr_peer_t * );
     34const char *tr_peerClient          ( tr_peer_t * );
     35void        tr_peerSetPrivate      ( tr_peer_t *, int );
     36void        tr_peerSetTorrent      ( tr_peer_t *, tr_torrent_t * );
     37void        tr_peerSentBlockToUs   ( tr_peer_t *, int byteCount );
     38void        tr_peerGotBlockFromUs  ( tr_peer_t *, int byteCount );
     39int         tr_peerRead            ( tr_peer_t * );
     40uint64_t    tr_peerDate            ( const tr_peer_t * );
     41const uint8_t *   tr_peerHash            ( const tr_peer_t * );
     42int         tr_peerPulse           ( tr_peer_t * );
     43int         tr_peerIsConnected     ( const tr_peer_t * );
     44int         tr_peerIsFrom          ( const tr_peer_t * );
     45int         tr_peerAmChoking       ( const tr_peer_t * );
     46int         tr_peerAmInterested    ( const tr_peer_t * );
     47int         tr_peerIsChoking       ( const tr_peer_t * );
     48int         tr_peerIsInterested    ( const tr_peer_t * );
     49float       tr_peerProgress        ( const tr_peer_t * );
     50int         tr_peerPort            ( const tr_peer_t * );
     51int         tr_peerHasPiece        ( const tr_peer_t *, int pieceIndex );
     52float       tr_peerDownloadRate    ( const tr_peer_t * );
     53float       tr_peerUploadRate      ( const tr_peer_t * );
     54void        tr_peerChoke           ( tr_peer_t * );
     55void        tr_peerUnchoke         ( tr_peer_t * );
     56uint64_t    tr_peerLastChoke       ( const tr_peer_t * );
     57void        tr_peerSetOptimistic   ( tr_peer_t *, int );
     58int         tr_peerIsOptimistic    ( const tr_peer_t * );
     59void        tr_peerBlame           ( tr_peer_t *, int piece, int success );
     60struct in_addr * tr_peerAddress    ( tr_peer_t * );
     61int         tr_peerGetConnectable  ( const tr_torrent_t *, uint8_t ** );
     62
     63void        tr_swiftPulse          ( tr_handle_t * );
    6164
    6265#endif
  • trunk/libtransmission/peerparse.h

    r2149 r2177  
    345345    }
    346346    tr_cpBlockAdd( tor->completion, block );
     347    tr_peerSentBlockToUs( peer, len-8 );
    347348    broadcastCancel( tor, index, begin, len - 8 );
    348349
     
    586587}
    587588
    588 static uint8_t * parseBufHash( tr_peer_t * peer )
     589static const uint8_t * parseBufHash( const tr_peer_t * peer )
    589590{
    590591    if( 48 > peer->pos )
  • trunk/libtransmission/shared.c

    r1725 r2177  
    294294        }
    295295
     296        tr_swiftPulse ( s->h );
     297
    296298        /* Wait up to 20 ms */
    297299        date2 = tr_date();
     
    383385{
    384386    tr_handle_t * h = s->h;
    385     tr_torrent_t * tor;
    386     uint8_t * hash;
    387387    int ii;
    388     uint64_t now = tr_date();
     388    const uint64_t now = tr_date();
    389389
    390390    for( ii = 0; ii < s->peerCount; )
    391391    {
    392         hash = tr_peerHash( s->peers[ii] );
     392        const uint8_t * hash = tr_peerHash( s->peers[ii] );
    393393
    394394        if( !hash && now > tr_peerDate( s->peers[ii] ) + 10000 )
     
    400400        if( hash )
    401401        {
     402            tr_torrent_t * tor;
     403
    402404            for( tor = h->torrentList; tor; tor = tor->next )
    403405            {
  • trunk/libtransmission/torrent.c

    r2159 r2177  
    607607        for( j = 0; j < tor->peerCount; j++ )
    608608        {
    609             if( tr_peerBitfield( tor->peers[j] ) &&
    610                 tr_bitfieldHas( tr_peerBitfield( tor->peers[j] ), piece ) )
     609            if( tr_peerHasPiece( tor->peers[j], piece ) )
    611610            {
    612611                (tab[i])++;
Note: See TracChangeset for help on using the changeset viewer.