summaryrefslogtreecommitdiffstats
path: root/libktorrent/torrent/advancedchokealgorithm.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'libktorrent/torrent/advancedchokealgorithm.cpp')
-rw-r--r--libktorrent/torrent/advancedchokealgorithm.cpp259
1 files changed, 259 insertions, 0 deletions
diff --git a/libktorrent/torrent/advancedchokealgorithm.cpp b/libktorrent/torrent/advancedchokealgorithm.cpp
new file mode 100644
index 0000000..7ca0578
--- /dev/null
+++ b/libktorrent/torrent/advancedchokealgorithm.cpp
@@ -0,0 +1,259 @@
+/***************************************************************************
+ * Copyright (C) 2005 by Joris Guisson *
+ * joris.guisson@gmail.com *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU General Public License as published by *
+ * the Free Software Foundation; either version 2 of the License, or *
+ * (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU General Public License *
+ * along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *
+ ***************************************************************************/
+#include <stdlib.h>
+#include <util/functions.h>
+#include <interfaces/torrentinterface.h>
+#include "chunkmanager.h"
+#include "peer.h"
+#include "peermanager.h"
+#include "packetwriter.h"
+#include "advancedchokealgorithm.h"
+
+using namespace kt;
+
+namespace bt
+{
+
+
+ const Uint32 OPT_SEL_INTERVAL = 30*1000; // we switch optimistic peer each 30 seconds
+ const double NEWBIE_BONUS = 1.0;
+ const double SNUB_PENALTY = 10.0;
+ const double ONE_MB = 1024*1024;
+
+
+ AdvancedChokeAlgorithm::AdvancedChokeAlgorithm()
+ : ChokeAlgorithm()
+ {
+ last_opt_sel_time = 0;
+ }
+
+
+ AdvancedChokeAlgorithm::~AdvancedChokeAlgorithm()
+ {}
+
+ bool AdvancedChokeAlgorithm::calcACAScore(Peer* p,ChunkManager & cman,const kt::TorrentStats & stats)
+ {
+ const PeerInterface::Stats & s = p->getStats();
+ if (p->isSeeder())
+ {
+ /*
+ double bd = 0;
+ if (stats.trk_bytes_downloaded > 0)
+ bd = s.bytes_downloaded / stats.trk_bytes_downloaded;
+ double ds = 0;
+ if (stats.download_rate > 0)
+ ds = s.download_rate/ stats.download_rate;
+ p->setACAScore(5*bd + 5*ds);
+ */
+ p->setACAScore(0.0);
+ return false;
+ }
+
+ bool should_be_interested = false;
+ bool should_we_be_interested = false;
+ // before we start calculating first check if we have piece that the peer doesn't have
+ const BitSet & ours = cman.getBitSet();
+ const BitSet & theirs = p->getBitSet();
+ for (Uint32 i = 0;i < ours.getNumBits();i++)
+ {
+ if (ours.get(i) && !theirs.get(i))
+ {
+ should_be_interested = true;
+ break;
+ }
+ }
+
+ if (!should_be_interested || !p->isInterested())
+ {
+ // not interseted so it doesn't make sense to unchoke it
+ p->setACAScore(-50.0);
+ return false;
+ }
+
+
+
+ double nb = 0.0; // newbie bonus
+ double cp = 0.0; // choke penalty
+ double sp = 0.0; // snubbing penalty
+ double lb = s.local ? 10.0 : 0.0; // local peers get a bonus of 10
+ double bd = s.bytes_downloaded; // bytes downloaded
+ double tbd = stats.trk_bytes_downloaded; // total bytes downloaded
+ double ds = s.download_rate; // current download rate
+ double tds = stats.download_rate; // total download speed
+
+ // if the peer has less than 1 MB or 0.5 % of the torrent it is a newbie
+ if (p->percentAvailable() < 0.5 && stats.total_bytes * p->percentAvailable() < 1024*1024)
+ {
+ nb = NEWBIE_BONUS;
+ }
+
+ if (p->isChoked())
+ {
+ cp = NEWBIE_BONUS; // cp cancels out newbie bonus
+ }
+
+ // if the evil bit is on (!choked, snubbed and requests have timed out)
+ if (s.evil)
+ {
+ sp = SNUB_PENALTY;
+ }
+
+ // NB + K * (BD/TBD) - CP - SP + L * (DS / TDS)
+ double K = 5.0;
+ double L = 5.0;
+ double aca = lb + nb + (tbd > 0 ? K * (bd/tbd) : 0.0) + (tds > 0 ? L* (ds / tds) : 0.0) - cp - sp;
+
+ p->setACAScore(aca);
+ return true;
+ }
+
+ static int ACACmp(Peer* a,Peer* b)
+ {
+ if (a->getStats().aca_score < b->getStats().aca_score)
+ return 1;
+ else if (a->getStats().aca_score > b->getStats().aca_score)
+ return -1;
+ else
+ return 0;
+ }
+
+
+ void AdvancedChokeAlgorithm::doChokingLeechingState(PeerManager & pman,ChunkManager & cman,const kt::TorrentStats & stats)
+ {
+ PeerPtrList ppl;
+ Uint32 np = pman.getNumConnectedPeers();
+ // add all non seeders
+ for (Uint32 i = 0;i < np;i++)
+ {
+ Peer* p = pman.getPeer(i);
+ if (p)
+ {
+ if (calcACAScore(p,cman,stats))
+ ppl.append(p);
+ else
+ // choke seeders they do not want to download from us anyway
+ p->choke();
+ }
+ }
+
+ // sort list by ACA score
+ ppl.setCompareFunc(ACACmp);
+ ppl.sort();
+
+ doUnchoking(ppl,updateOptimisticPeer(pman,ppl));
+ }
+
+ void AdvancedChokeAlgorithm::doUnchoking(PeerPtrList & ppl,Peer* poup)
+ {
+ // Get the number of upload slots
+ Uint32 num_slots = Choker::getNumUploadSlots();
+ // Do the choking and unchoking
+ Uint32 num_unchoked = 0;
+ for (Uint32 i = 0;i < ppl.count();i++)
+ {
+ Peer* p = ppl.at(i);
+ if (!poup && num_unchoked < num_slots)
+ {
+ p->getPacketWriter().sendUnchoke();
+ num_unchoked++;
+ }
+ else if (num_unchoked < num_slots -1 || p == poup)
+ {
+ p->getPacketWriter().sendUnchoke();
+ if (p != poup)
+ num_unchoked++;
+ }
+ else
+ {
+ p->choke();
+ }
+ }
+ }
+
+ static int UpRateCmp(Peer* a,Peer* b)
+ {
+ if (a->getStats().upload_rate < b->getStats().upload_rate)
+ return -1;
+ else if (a->getStats().upload_rate > b->getStats().upload_rate)
+ return 1;
+ else
+ return 0;
+ }
+
+ void AdvancedChokeAlgorithm::doChokingSeedingState(PeerManager & pman,ChunkManager & cman,const kt::TorrentStats & stats)
+ {
+ PeerPtrList ppl;
+ Uint32 np = pman.getNumConnectedPeers();
+ // add all non seeders
+ for (Uint32 i = 0;i < np;i++)
+ {
+ Peer* p = pman.getPeer(i);
+ if (p)
+ {
+ // update the ACA score in the process
+ if (calcACAScore(p,cman,stats))
+ ppl.append(p);
+ else
+ // choke seeders they do not want to download from us anyway
+ p->choke();
+ }
+ }
+
+ ppl.setCompareFunc(UpRateCmp);
+ ppl.sort();
+
+ doUnchoking(ppl,updateOptimisticPeer(pman,ppl));
+ }
+
+ static Uint32 FindPlannedOptimisticUnchokedPeer(PeerManager& pman,const PeerPtrList & ppl)
+ {
+ Uint32 num_peers = pman.getNumConnectedPeers();
+ if (num_peers == 0)
+ return UNDEFINED_ID;
+
+ // find a random peer that is choked and interested
+ Uint32 start = rand() % num_peers;
+ Uint32 i = (start + 1) % num_peers;
+ while (i != start)
+ {
+ Peer* p = pman.getPeer(i);
+ if (p && p->isChoked() && p->isInterested() && !p->isSeeder() && ppl.contains(p))
+ return p->getID();
+ i = (i + 1) % num_peers;
+ }
+
+ // we do not expect to have 4 billion peers
+ return UNDEFINED_ID;
+ }
+
+ Peer* AdvancedChokeAlgorithm::updateOptimisticPeer(PeerManager & pman,const PeerPtrList & ppl)
+ {
+ // get the planned optimistic unchoked peer and change it if necessary
+ Peer* poup = pman.findPeer(opt_unchoked_peer_id);
+ TimeStamp now = GetCurrentTime();
+ if (now - last_opt_sel_time > OPT_SEL_INTERVAL || !poup)
+ {
+ opt_unchoked_peer_id = FindPlannedOptimisticUnchokedPeer(pman,ppl);
+ last_opt_sel_time = now;
+ poup = pman.findPeer(opt_unchoked_peer_id);
+ }
+ return poup;
+ }
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-04 21:09:57 +0000