Changeset 3864

Timestamp:

Nov 18, 2007, 1:00:49 AM (15 years ago)

Author:

charles

Message:

reintroduce the "SWIFT" algorithm

Location:

trunk

Files:

• gtk/torrent-inspector.c (modified) (2 diffs)
• libtransmission/clients.c (modified) (1 diff)
• libtransmission/peer-mgr-private.h (modified) (2 diffs)
• libtransmission/peer-mgr.c (modified) (10 diffs)
• libtransmission/peer-msgs.c (modified) (4 diffs)
• libtransmission/ratecontrol.c (modified) (2 diffs)
• libtransmission/transmission.h (modified) (1 diff)

trunk/gtk/torrent-inspector.c

@@ -37 +37 @@
 #include "util.h"
 
-#define UPDATE_INTERVAL_MSEC 1500
+#define UPDATE_INTERVAL_MSEC 2000
 
 /****
@@ -362 +362 @@
         case TR_PEER_STATUS_PEER_IS_CHOKED:       text = _( "Peer is Choked" ); break;
         case TR_PEER_STATUS_CLIENT_IS_CHOKED:     text = _( "Choked" ); break;
-        case TR_PEER_STATUS_CLIENT_IS_INTERESTED: text = _( "Choked and Interested" ); break;
+        case TR_PEER_STATUS_CLIENT_IS_INTERESTED: text = _( "Choked & Interested" ); break;
         case TR_PEER_STATUS_READY:                text = _( "Ready" ); break;
         case TR_PEER_STATUS_REQUEST_SENT:         text = _( "Request Sent" ); break;
         case TR_PEER_STATUS_ACTIVE           :    text = _( "Active" ); break;
+        case TR_PEER_STATUS_ACTIVE_AND_CHOKED:    text = _( "Active & Choked" ); break;
         default:                                  text = "BUG"; break;
     }

trunk/libtransmission/clients.c

@@ -409 +409 @@
             isprint( id[6] ) && isprint( id[7] ) )
         {
-            tr_asprintf( &ret, "unknown client (%c%c%c%c%c%c%c%c)",
+            tr_asprintf( &ret, "%c%c%c%c%c%c%c%c",
                   id[0], id[1], id[2], id[3], id[4], id[5], id[6], id[7] );
         }
         else
         {
-            tr_asprintf( &ret, "unknown client (0x%02x%02x%02x%02x%02x%02x%02x%02x)",
+            tr_asprintf( &ret, "0x%02x%02x%02x%02x%02x%02x%02x%02x",
                   id[0], id[1], id[2], id[3], id[4], id[5], id[6], id[7] );
         }

trunk/libtransmission/peer-mgr-private.h

@@ -28 +28 @@
     ENCRYPTION_PREFERENCE_NO
 };
+
+/**
+*** The "SWIFT" system is described by Karthik Tamilmani,
+*** Vinay Pai, and Alexander Mohr of Stony Brook University
+*** in their paper "SWIFT: A System With Incentives For Trading"
+*** http://citeseer.ist.psu.edu/tamilmani04swift.html
+***
+*** More SWIFT constants are defined in peer-mgr.c
+**/
+
+/**
+ * Use SWIFT?
+ */
+static const int SWIFT_ENABLED = 1;
+
+/**
+ * For every byte the peer uploads to us,
+ * allow them to download this many bytes from us
+ */
+static const double SWIFT_REPAYMENT_RATIO = 1.33;
+
 
 typedef struct tr_peer
@@ -67 +88 @@
     double rateToClient;
     double rateToPeer;
+
+    int64_t credit;
 }
 tr_peer;

trunk/libtransmission/peer-mgr.c

@@ -40 +40 @@
 #include "utils.h"
 
+/**
+*** The "SWIFT" system is described by Karthik Tamilmani,
+*** Vinay Pai, and Alexander Mohr of Stony Brook University
+*** in their paper "SWIFT: A System With Incentives For Trading"
+*** http://citeseer.ist.psu.edu/tamilmani04swift.html
+***
+*** More SWIFT constants are defined in peer-mgr-private.h
+**/
+
+/**
+ * Allow new peers to download this many bytes from
+ * us when getting started.  This can prevent gridlock
+ * with other peers using tit-for-tat algorithms
+ */
+static const int SWIFT_INITIAL_CREDIT = 64 * 1024; /* 64 KiB */
+
+/**
+ * We expend a fraction of our torrent's total upload speed
+ * on largesse by uniformly distributing free credit to
+ * all of our peers.  This too helps prevent gridlock.
+ */
+static const double SWIFT_LARGESSE = 0.10; /* 10% of our UL */
+
+/**
+ * How frequently to extend largesse-based credit
+ */
+static const int SWIFT_PERIOD_MSEC = 5000;
+
+
 enum
 {
@@ -115 +144 @@
     tr_timer * rechokeTimer;
     tr_timer * refillTimer;
+    tr_timer * swiftTimer;
     tr_torrent * tor;
     tr_bitfield * requested;
@@ -315 +345 @@
     tr_peer * p;
     p = tr_new0( tr_peer, 1 );
+    p->credit = SWIFT_INITIAL_CREDIT;
     p->rcToClient = tr_rcInit( );
     p->rcToPeer = tr_rcInit( );
@@ -398 +429 @@
     tr_timerFree( &t->rechokeTimer );
     tr_timerFree( &t->refillTimer );
+    tr_timerFree( &t->swiftTimer );
 
     tr_bitfieldFree( t->requested );
@@ -1168 +1200 @@
 static int reconnectPulse( void * vtorrent );
 static int rechokePulse( void * vtorrent );
+static int swiftPulse( void * vtorrent );
 
 void
@@ -1182 +1215 @@
     assert( ( t->isRunning != 0 ) == ( t->reconnectTimer != NULL ) );
     assert( ( t->isRunning != 0 ) == ( t->rechokeTimer != NULL ) );
+    assert( ( t->isRunning != 0 ) == ( t->swiftTimer != NULL ) );
 
     if( !t->isRunning )
@@ -1195 +1229 @@
                                        RECHOKE_PERIOD_MSEC );
 
+        t->swiftTimer = tr_timerNew( t->manager->handle,
+                                     swiftPulse, t,
+                                     SWIFT_PERIOD_MSEC );
+
         reconnectPulse( t );
 
         rechokePulse( t );
+
+        swiftPulse( t );
     }
 
@@ -1211 +1251 @@
     tr_timerFree( &t->rechokeTimer );
     tr_timerFree( &t->reconnectTimer );
+    tr_timerFree( &t->swiftTimer );
 
     /* disconnect the peers. */
@@ -1478 +1519 @@
 {
     /* FIXME: tweak this? */
-    return ( 1 * peer->rateToPeer )
-         + ( 1 * peer->rateToClient );
+    return /* 1 * peer->rateToPeer )
+         +*/ ( 1 * peer->rateToClient );
 }
 
@@ -1531 +1572 @@
     torrentLock( t );
     rechoke( t );
+    torrentUnlock( t );
+    return TRUE;
+}
+
+/***
+****
+***/
+
+static int
+swiftPulse( void * vtorrent )
+{
+    Torrent * t = vtorrent;
+    torrentLock( t );
+
+    if( !tr_torrentIsSeed( t->tor ) )
+    {
+        int i;
+        int peerCount = 0;
+        int deadbeatCount = 0;
+        tr_peer ** peers = getConnectedPeers( t, &peerCount );
+        tr_peer ** deadbeats = tr_new( tr_peer*, peerCount );
+
+        for( i=0; i<peerCount; ++i ) {
+            tr_peer * peer = peers[i];
+            if( peer->credit < 0 )
+                deadbeats[deadbeatCount++] =  peer;
+        }
+
+        if( deadbeatCount )
+        {
+            const double ul_KiBsec = tr_rcRate( t->tor->upload );
+            const double ul_KiB = ul_KiBsec * (SWIFT_PERIOD_MSEC/1000.0);
+            const double ul_bytes = ul_KiB * 1024;
+            const double freeCreditTotal = ul_bytes * SWIFT_LARGESSE;
+            const int freeCreditPerPeer = (int)( freeCreditTotal / deadbeatCount );
+            for( i=0; i<deadbeatCount; ++i )
+                deadbeats[i]->credit = freeCreditPerPeer;
+            tordbg( t, "%d deadbeats, "
+                       "who are each being granted %d bytes' credit "
+                       "for a total of %.1f KiB, "
+                       "%d%% of the torrent's ul speed %.1f\n",
+                deadbeatCount, freeCreditPerPeer,
+                ul_KiBsec*SWIFT_LARGESSE, (int)(SWIFT_LARGESSE*100), ul_KiBsec );
+        }
+
+        tr_free( deadbeats );
+        tr_free( peers );
+    }
+
     torrentUnlock( t );
     return TRUE;

trunk/libtransmission/peer-msgs.c

@@ -1035 +1035 @@
     tor->downloadedCur += byteCount;
     msgs->info->pieceDataActivityDate = time( NULL );
+    msgs->info->credit += (int)(byteCount * SWIFT_REPAYMENT_RATIO);
     tr_rcTransferred( msgs->info->rcToClient, byteCount );
     tr_rcTransferred( tor->download, byteCount );
@@ -1256 +1257 @@
     tor->uploadedCur += byteCount;
     msgs->info->pieceDataActivityDate = time( NULL );
+    msgs->info->credit -= byteCount;
     tr_rcTransferred( msgs->info->rcToPeer, byteCount );
     tr_rcTransferred( tor->upload, byteCount );
@@ -1441 +1443 @@
 {
     /* don't let our outbuffer get too large */
-    return tr_peerIoWriteBytesWaiting( msgs->io ) < 4096;
+    if( tr_peerIoWriteBytesWaiting( msgs->io ) > 4096 )
+        return FALSE;
+
+    /* SWIFT */
+    if( SWIFT_ENABLED && !tr_torrentIsSeed( msgs->torrent )
+                      && ( msgs->info->credit < 0 ) )
+        return FALSE;
+
+    return TRUE;
 }
 
@@ -1493 +1503 @@
 
     else if( ( time(NULL) - peer->pieceDataActivityDate ) < 3 )
-        peer->status = TR_PEER_STATUS_ACTIVE;
-
-    else if( peer->clientIsChoked )
-        peer->status = TR_PEER_STATUS_CLIENT_IS_CHOKED;
+        peer->status = peer->clientIsChoked
+                       ? TR_PEER_STATUS_ACTIVE_AND_CHOKED
+                       : TR_PEER_STATUS_ACTIVE;
 
     else if( peer->peerIsChoked )
         peer->status = TR_PEER_STATUS_PEER_IS_CHOKED;
 
+    else if( peer->clientIsChoked )
+        peer->status = peer->clientIsInterested 
+                       ? TR_PEER_STATUS_CLIENT_IS_INTERESTED
+                       : TR_PEER_STATUS_CLIENT_IS_CHOKED;
+
     else if( msgs->clientAskedFor != NULL )
         peer->status = TR_PEER_STATUS_REQUEST_SENT;
-
-    else if( peer->clientIsInterested )
-        peer->status = TR_PEER_STATUS_CLIENT_IS_INTERESTED;
 
     else

trunk/libtransmission/ratecontrol.c

@@ -30 +30 @@
 #include "utils.h"
 
-#define GRANULARITY_MSEC 100
+#define GRANULARITY_MSEC 250
 #define SHORT_INTERVAL_MSEC 3000
 #define LONG_INTERVAL_MSEC 6000
@@ -109 +109 @@
         max = r->limit;
         kb = max>cur ? max-cur : 0;
-        bytes = (size_t)(kb * 1024u);
+        bytes = (size_t)(kb * 1024);
 
         tr_lockUnlock( (tr_lock*)r->lock );

trunk/libtransmission/transmission.h

@@ -692 +692 @@
     TR_PEER_STATUS_READY,
     TR_PEER_STATUS_REQUEST_SENT,
-    TR_PEER_STATUS_ACTIVE
+    TR_PEER_STATUS_ACTIVE,
+    TR_PEER_STATUS_ACTIVE_AND_CHOKED
 }
 tr_peer_status;