summaryrefslogtreecommitdiffstats
path: root/estimation-scripts
diff options
context:
space:
mode:
authortpearson <tpearson@283d02a7-25f6-0310-bc7c-ecb5cbfe19da>2010-01-20 02:37:40 +0000
committertpearson <tpearson@283d02a7-25f6-0310-bc7c-ecb5cbfe19da>2010-01-20 02:37:40 +0000
commit9ad5c7b5e23b4940e7a3ea3ca3a6fb77e6a8fab0 (patch)
treed088b5210e77d9fa91d954d8550e00e372b47378 /estimation-scripts
downloadktorrent-9ad5c7b5e23b4940e7a3ea3ca3a6fb77e6a8fab0.tar.gz
ktorrent-9ad5c7b5e23b4940e7a3ea3ca3a6fb77e6a8fab0.zip
Updated to final KDE3 ktorrent release (2.2.6)
git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/applications/ktorrent@1077377 283d02a7-25f6-0310-bc7c-ecb5cbfe19da
Diffstat (limited to 'estimation-scripts')
-rw-r--r--estimation-scripts/EstimationResults.rb100
-rw-r--r--estimation-scripts/Estimators.rb90
-rw-r--r--estimation-scripts/README40
-rw-r--r--estimation-scripts/Sample.rb64
-rw-r--r--estimation-scripts/demo.rb18
-rw-r--r--estimation-scripts/enable-logging.diff224
-rw-r--r--estimation-scripts/processlog.rb63
7 files changed, 599 insertions, 0 deletions
diff --git a/estimation-scripts/EstimationResults.rb b/estimation-scripts/EstimationResults.rb
new file mode 100644
index 0000000..01eedcc
--- /dev/null
+++ b/estimation-scripts/EstimationResults.rb
@@ -0,0 +1,100 @@
+require 'Estimators'
+require 'Sample'
+
+class EstimationResults
+
+ attr_reader :estimator
+
+ def initialize(estimator, samples)
+ @samples = samples
+ @totalTime = samples.keys.max
+ @totalSize = @samples[@totalTime].bytesDownloaded + @samples[@totalTime].bytesLeft
+ @estimator = estimator
+
+ @maxError = nil
+ @estimations = nil
+ @absoluteErrors = nil
+ @relativeErrors = nil
+ @rootMeanSquareErrorRelative = nil
+ end
+
+ def getRootMeanSquareErrorRelative
+ if @rootMeanSquareErrorRelative == nil
+ relativeErrors = getRelativeErrors
+ @rootMeanSquareErrorRelative = 0.0
+ relativeErrors.each_value do |x|
+ @rootMeanSquareErrorRelative += x**2
+ end
+ @rootMeanSquareErrorRelative = Math.sqrt( @rootMeanSquareErrorRelative / relativeErrors.size )
+ end
+ return @rootMeanSquareErrorRelative
+ end
+
+ # returns the root mean square error for a specific interval of the download
+ # left and right must be floats between 0.0 (no bytes downloaded, start of download) and 1.0 (download complete), right must be greater than left
+
+ def getRootMeanSquareErrorRelative(left, right)
+ relativeErrors = getRelativeErrors
+ rmser = 0.0
+
+ n = 0
+ @samples.keys.each do |x|
+ percentage = @samples[x].bytesDownloaded.to_f / @totalSize
+ if percentage >= left and percentage <= right
+ rmser += relativeErrors[x]**2
+ n += 1
+ end
+ end
+
+ rmser = Math.sqrt( rmser / n )
+
+ return rmser
+ end
+
+ def getRelativeErrors
+ if @relativeErrors == nil
+ @relativeErrors = Hash.new
+ absoluteErrors = getAbsoluteErrors
+ absoluteErrors.keys.sort.each do |time|
+ timeLeft = @totalTime - time;
+ @relativeErrors[time] = absoluteErrors[time].abs.to_f / timeLeft
+ @relativeErrors[time] = @maxError if @maxError != nil and @relativeErrors[time] > @maxError
+ end
+ end
+ return @relativeErrors
+ end
+
+ def setMaxError(maxError)
+ if maxError != @maxError
+ @maxError = maxError
+ @relativeErrors = nil
+ @rootMeanSquareErrorRelative = nil
+ end
+ end
+
+ def getAbsoluteErrors
+ if @absoluteErrors == nil
+ @absoluteErrors = Hash.new
+ estimations = getEstimations
+ estimations.keys.sort.each do |time|
+ @absoluteErrors[time] = @estimations[time] - (@totalTime - time)
+ end
+ end
+
+ return @absoluteErrors
+ end
+
+ def getEstimations
+
+ if @estimations == nil
+ @estimations = Hash.new
+ @samples.values.sort.each do |sample|
+ @estimator.process(sample)
+ @estimations[sample.time] = @estimator.estimate
+ end
+ end
+
+ return @estimations
+ end
+end
+
diff --git a/estimation-scripts/Estimators.rb b/estimation-scripts/Estimators.rb
new file mode 100644
index 0000000..1ef0c6e
--- /dev/null
+++ b/estimation-scripts/Estimators.rb
@@ -0,0 +1,90 @@
+require 'Sample'
+
+# abstract base class of all estimators
+
+class Estimator
+
+ # processes a sample
+ def process(sample)
+ end
+
+ # returns an estimate (ETA as float)
+ # note that you must process at least one sample before this will return meaningful output
+ def estimate
+ end
+
+ # returns the name of the estimator
+ def name
+ end
+end
+
+# estimator that uses the current speed
+class CSAEstimator < Estimator
+ def process(sample)
+ @sample = sample.clone
+ end
+
+ def estimate
+ return @sample.bytesLeft.to_f / @sample.speed
+ end
+
+ def name
+ 'CurrentSpeedEstimator'
+ end
+end
+
+# estimator that uses the global average speed of the whole torrent download for estimation
+
+class GASAEstimator < Estimator
+ def process(sample)
+ @first = sample.clone if @first == nil
+ @last = sample.clone
+ @avgSpeed = Sample.averageSpeed(@first, @last)
+ end
+
+ def estimate
+ return @last.bytesLeft.to_f / @avgSpeed
+ end
+
+ def name
+ 'AverageSpeedEstimator'
+ end
+end
+
+# estimator that uses the average over the last n seconds
+
+class WINXEstimator < Estimator
+
+ attr_reader :windowSize
+
+ def process(sample)
+ # remove all samples that are older than the window size. Note: samples are sorted.
+ @list.pop until @list.length <= 1 or (sample.time - @list.last.time) <= @windowSize
+
+ # prepend array with newest sample
+ @list.unshift(sample.clone)
+ end
+
+ def estimate
+
+ if @list.length > 1
+ first = @list.first
+ last = @list.last
+ return first.bytesLeft.to_f / Sample.averageSpeed(last, first)
+ elsif @list.length == 1
+ sample = @list.first
+ return sample.bytesLeft.to_f / sample.speed
+ elsif @list.length == 0
+ return 0
+ end
+ end
+
+ def name
+ "MovingAverageEstimator_#{@windowSize}s"
+ end
+
+ def initialize(windowSizeInSeconds)
+ @list = Array.new
+ @windowSize = windowSizeInSeconds
+ end
+end
diff --git a/estimation-scripts/README b/estimation-scripts/README
new file mode 100644
index 0000000..00ba46f
--- /dev/null
+++ b/estimation-scripts/README
@@ -0,0 +1,40 @@
+Introduction
+============
+
+This directory contains patches and scripts for my experiments regarding download time estimation
+algorithms, using KTorrent for gathering data ;-)
+
+Files
+=====
+
+enable-logging.diff - Patch to apply to enable logging download stats once per second to $KDEHOME/share/apps/ktorrent/log (by Ivan). Apply it if you want to help collecting test cases.
+
+processlog.rb - extracts logs for single torrents from $KDEHOME/share/apps/ktorrent/log and stores them in $FILENAME-torrent.log
+
+Sample.rb - class representing a sample, does the parsing (given a line from adjustTimestmaps output)
+
+Estimators.rb - Some basic estimators, for estimation based on current speed, average speed and moving average speed.
+
+EstimationResults.rb - Calculates and holds the estimation results of an estimator, including statistics such as relative error for each estimation, root mean square error and the like
+
+What to do
+==========
+
+1) Apply the patch: In torrent/ dir, apply it via
+
+ cat enable-logging.diff | patch -p0
+
+2) Run ktorrent and download torrents. When completed, run processlog.rb:
+
+ ruby processlog.rb $KDEHOME/share/apps/ktorrent/log
+
+Extracted logs end up in $TORRENTFILENAME-torrent.log. ATTENTION: existing files are overwritten!
+
+4) Now, analyze the -adjusted file with a ruby script, using Sample.rb, Estimators.rb, and EstimationResults.rb... ;-)
+I will upload something useful as soon as finished.
+
+
+Frank Osterfeld, <frank.osterfeld at kdemail.net>
+
+
+
diff --git a/estimation-scripts/Sample.rb b/estimation-scripts/Sample.rb
new file mode 100644
index 0000000..b0c38c2
--- /dev/null
+++ b/estimation-scripts/Sample.rb
@@ -0,0 +1,64 @@
+
+class Sample
+
+ attr_reader :time, :speed, :bytesDownloaded, :bytesLeft, :peersTotal
+
+ def Sample.averageSpeed(sample1, sample2)
+ if sample2.time - sample1.time > 0
+ return (sample1.bytesLeft - sample2.bytesLeft).to_f / (sample2.time - sample1.time).to_f
+ else
+ return sample1.speed
+ end
+ end
+
+ def <=>(other)
+ @time <=> other.time
+ end
+
+ # parses a single sample from a line. Format is
+ #
+ # \<tt>timestamp,speed,bytesDownloaded,bytesLeft,peersTotal</tt>
+ #
+ # where
+ # - timestamp is in seconds since epoch (Integer)
+ # - speed is bytes/seconds as Integer
+ # - bytesDownloaded, bytesLeft are bytes as Integer
+ # - peersTotal is the number of available peers (both seeders and leecher, both
+ # connected and not connected to us)
+
+ def Sample.parse(line)
+
+ splitted = line.split(",")
+
+ # TODO: do better error checking
+ return nil if splitted.length != 5
+
+ time = splitted[0].to_i
+ speed = splitted[1].to_i
+ bytesDownloaded = splitted[2].to_i
+ bytesLeft = splitted[3].to_i
+ peersTotal = splitted[4].to_i
+ return Sample.new(time, speed, bytesDownloaded, bytesLeft, peersTotal)
+ end
+
+ # parses samples from a text file, with one sample per line
+ def Sample.parseFromFile(filename)
+ samples = Hash.new
+
+ input = File.open(filename)
+ input.each_line do |line|
+ s = Sample.parse(line)
+ samples[s.time] = s unless s == nil
+ end
+ input.close
+ return samples
+ end
+
+ def initialize(time, speed, bytesDownloaded, bytesLeft, peersTotal)
+ @time = time
+ @speed = speed
+ @bytesDownloaded = bytesDownloaded
+ @bytesLeft = bytesLeft
+ @peersTotal = peersTotal
+ end
+end
diff --git a/estimation-scripts/demo.rb b/estimation-scripts/demo.rb
new file mode 100644
index 0000000..9cf235b
--- /dev/null
+++ b/estimation-scripts/demo.rb
@@ -0,0 +1,18 @@
+require 'Sample'
+require 'Estimators'
+require 'EstimationResults'
+
+samples = Sample.parseFromFile(ARGV[0])
+
+est = WINXEstimator.new(ARGV[1].to_i)
+
+results = EstimationResults.new(est, samples)
+results.setMaxError(10.0)
+
+relErrors = results.getRelativeErrors
+
+relErrors.keys.sort.each do |x|
+ puts "#{x} #{relErrors[x]}"
+end
+
+#puts "RMSE: #{results.getRootMeanSquareErrorRelative}"
diff --git a/estimation-scripts/enable-logging.diff b/estimation-scripts/enable-logging.diff
new file mode 100644
index 0000000..57dc703
--- /dev/null
+++ b/estimation-scripts/enable-logging.diff
@@ -0,0 +1,224 @@
+Index: estimation-scripts/enable-logging.diff
+===================================================================
+--- estimation-scripts/enable-logging.diff (revision 472081)
++++ estimation-scripts/enable-logging.diff (working copy)
+@@ -1,106 +0,0 @@
+-Index: apps/ktorrent/ktorrentviewitem.cpp
+-===================================================================
+---- apps/ktorrent/ktorrentviewitem.cpp (revision 469614)
+-+++ apps/ktorrent/ktorrentviewitem.cpp (working copy)
+-@@ -25,6 +25,7 @@
+- #include <math.h>
+- #include "ktorrentviewitem.h"
+- #include "functions.h"
+-+#include <util/log.h>
+-
+- using namespace bt;
+-
+-@@ -77,6 +78,9 @@
+- KTorrentViewItem::KTorrentViewItem(QListView* parent,bt::TorrentControl* tc)
+- : KListViewItem(parent),tc(tc)
+- {
+-+ toLog = true;
+-+ counter = 1;
+-+ started = false;
+- update();
+- }
+-
+-@@ -86,6 +90,7 @@
+-
+- void KTorrentViewItem::update()
+- {
+-+ bool tmpLog = true;
+- /*
+- addColumn(i18n("File"));
+- addColumn(i18n("Status"));
+-@@ -114,8 +119,43 @@
+- setText(6,KBytesPerSecToString(tc->getUploadRate() / 1024.0));
+-
+- KLocale* loc = KGlobal::locale();
+-+
+-+
+-+ if(counter==1)
+-+ {
+-+ if (tc->isRunning())
+-+ {
+-+ if(!started)
+-+ {
+-+ Out() << "{" << tc->getTorrentName() << "}," << QDateTime::currentDateTime().toTime_t() << "," << tc->getDownloadRate() << "," << tc->getBytesDownloaded() << "," << tc->getBytesLeft() << "," << tc->getNumPeers() << ",ACTIVATED" << endl;
+-+ tmpLog = false;
+-+ started = true;
+-+ toLog = true;
+-+ }
+-+ }
+-+
+-+ if(!tc->isRunning())
+-+ {
+-+ if(started)
+-+ {
+-+ Out() << "{" << tc->getTorrentName() << "}," << QDateTime::currentDateTime().toTime_t() << "," << tc->getDownloadRate() << "," << tc->getBytesDownloaded() << "," << tc->getBytesLeft() << "," << tc->getNumPeers() << ",DEACTIVATED" <<endl;
+-+ tmpLog = false;
+-+ started = false;
+-+ }
+-+ toLog = false;
+-+ }
+-+ }
+-+
+-+ if(counter!=1) tmpLog=false;
+-+ counter *= -1;
+-+
+-+
+- if (tc->getBytesLeft() == 0)
+- {
+-+ if(toLog && tmpLog)
+-+ Out() << "{" << tc->getTorrentName() << "}," << QDateTime::currentDateTime().toTime_t() << "," << tc->getDownloadRate() << "," << tc->getBytesDownloaded() << "," << 0 << "," << tc->getNumPeers() << ",FINISHED" << endl;
+-+ toLog = false;
+-+
+- setText(7,i18n("finished"));
+- }
+- else
+-@@ -124,9 +164,16 @@
+- if( bytes_downloaded < 1 ) //if we just started download use old algorithm
+- {
+- if (tc->getDownloadRate() == 0)
+-+ {
+-+ if(toLog && tmpLog)
+-+ Out() << "{" << tc->getTorrentName() << "}," << QDateTime::currentDateTime().toTime_t() << "," << 0 << "," << tc->getBytesDownloaded() << "," << tc->getBytesLeft() << "," << tc->getNumPeers() << ",RUNNING" << endl;
+- setText(7,i18n("infinity"));
+-+ }
+- else
+- {
+-+ if(toLog && tmpLog)
+-+ Out() << "{" << tc->getTorrentName() << "}," << QDateTime::currentDateTime().toTime_t() << "," << tc->getDownloadRate() << "," << tc->getBytesDownloaded() << "," << tc->getBytesLeft() << "," << tc->getNumPeers() << ",RUNNING" << endl;
+-+
+- Uint32 secs = (int)floor( (float)tc->getBytesLeft() / (float)tc->getDownloadRate() );
+- QTime t;
+- t = t.addSecs(secs);
+-Index: apps/ktorrent/ktorrentviewitem.h
+-===================================================================
+---- apps/ktorrent/ktorrentviewitem.h (revision 469614)
+-+++ apps/ktorrent/ktorrentviewitem.h (working copy)
+-@@ -41,6 +41,10 @@
+- void update();
+-
+- private:
+-+ bool toLog;
+-+ int counter;
+-+ bool started;
+-+ uint start_timestamp;
+- int compare(QListViewItem * i,int col,bool ascending) const;
+- void paintCell(QPainter* p,const QColorGroup & cg,int column,int width,int align);
+-
+Index: apps/ktorrent/ktorrentviewitem.cpp
+===================================================================
+--- apps/ktorrent/ktorrentviewitem.cpp (revision 472081)
++++ apps/ktorrent/ktorrentviewitem.cpp (working copy)
+@@ -25,7 +25,10 @@
+ #include <math.h>
+ #include "ktorrentviewitem.h"
+ #include "functions.h"
++#include <util/log.h>
++#include <torrent/globals.h>
+
++
+ using namespace bt;
+ using namespace kt;
+
+@@ -78,6 +81,9 @@
+ KTorrentViewItem::KTorrentViewItem(QListView* parent,TorrentInterface* tc)
+ : KListViewItem(parent),tc(tc)
+ {
++ toLog = true;
++ counter = 1;
++ started = false;
+ update();
+ }
+
+@@ -87,6 +93,7 @@
+
+ void KTorrentViewItem::update()
+ {
++ bool tmpLog = true;
+ /*
+ addColumn(i18n("File"));
+ addColumn(i18n("Status"));
+@@ -114,8 +121,46 @@
+ setText(6,KBytesPerSecToString(s.upload_rate / 1024.0));
+
+ KLocale* loc = KGlobal::locale();
++
++
++
++ if(counter==1)
++ {
++ if (s.running)
++ {
++ if(!started)
++ {
++ Out() << "{" << s.torrent_name << "}," << QDateTime::currentDateTime().toTime_t() << "," << s.download_rate << "," << s.bytes_downloaded << "," << s.bytes_left << "," << s.num_peers << ",ACTIVATED" << endl;
++ tmpLog = false;
++ started = true;
++ toLog = true;
++ }
++ }
++
++ if(!s.running)
++ {
++ if(started)
++ {
++ Out() << "{" << s.torrent_name << "}," << QDateTime::currentDateTime().toTime_t() << "," << s.download_rate << "," << s.bytes_downloaded << "," << s.bytes_left << "," << s.num_peers << ",DEACTIVATED" <<endl;
++ tmpLog = false;
++ started = false;
++ }
++ toLog = false;
++ }
++ }
++
++ if(counter!=1) tmpLog=false;
++ counter *= -1;
++
++
++
+ if (s.bytes_left == 0)
+ {
++ if(toLog && tmpLog)
++ Out() << "{" << s.torrent_name << "}," << QDateTime::currentDateTime().toTime_t() << "," << s.download_rate << "," << s.bytes_downloaded << "," << 0 << "," << s.num_peers << ",FINISHED" << endl;
++ toLog = false;
++
++
+ setText(7,i18n("finished"));
+ }
+ else
+@@ -124,9 +169,17 @@
+ if( bytes_downloaded < 1 ) //if we just started download use old algorithm
+ {
+ if (s.download_rate == 0)
++ {
++ if(toLog && tmpLog)
++ Out() << "{" << s.torrent_name << "}," << QDateTime::currentDateTime().toTime_t() << "," << 0 << "," << s.bytes_downloaded << "," << s.bytes_left << "," << s.num_peers << ",RUNNING" << endl;
++
+ setText(7,i18n("infinity"));
++ }
+ else
+ {
++ if(toLog && tmpLog)
++ Out() << "{" << s.torrent_name << "}," << QDateTime::currentDateTime().toTime_t() << "," << s.download_rate << "," << s.bytes_downloaded << "," << s.bytes_left << "," << s.num_peers << ",RUNNING" << endl;
++
+ Uint32 secs = (int)floor( (float)s.bytes_left / (float)s.download_rate);
+ setText(7,DurationToString(secs));
+ }
+Index: apps/ktorrent/ktorrentviewitem.h
+===================================================================
+--- apps/ktorrent/ktorrentviewitem.h (revision 472081)
++++ apps/ktorrent/ktorrentviewitem.h (working copy)
+@@ -41,6 +41,10 @@
+ void update();
+
+ private:
++ bool toLog;
++ int counter;
++ bool started;
++ uint start_timestamp;
+ int compare(QListViewItem * i,int col,bool ascending) const;
+ void paintCell(QPainter* p,const QColorGroup & cg,int column,int width,int align);
+
diff --git a/estimation-scripts/processlog.rb b/estimation-scripts/processlog.rb
new file mode 100644
index 0000000..c750ba5
--- /dev/null
+++ b/estimation-scripts/processlog.rb
@@ -0,0 +1,63 @@
+IDX_TIME = 0
+IDX_STATE = 5
+
+def adjustTimestamps(perFile)
+ startTime = 0
+ offset = 0
+ lastDeactivation = -1
+ lastSample = nil
+
+ perFile.each_key do |file|
+ perFile[file].each do |line|
+
+ time = line[0].to_i
+
+ startTime = time if startTime == 0
+
+ time = time - startTime - offset
+
+ line[IDX_TIME] = time.to_s
+
+ if line[IDX_STATE] == 'RUNNING'
+ lastSample = line
+ elsif line[IDX_STATE] == 'ACTIVATED'
+ offset = time - lastDeactivation unless lastDeactivation == -1
+ perFile[file].delete(line)
+ elsif line[IDX_STATE] == 'DEACTIVATED'
+ lastDeactivation = time
+ perFile[file].delete(line)
+ elsif line[IDX_STATE] == 'FINISHED'
+ # print last sample: time speed=0 downloaded left=0 peersTotal
+ # puts "#{line[0].to_i},0,#{lastSample[2].to_i + lastSample[3].to_i},0,#{lastSample[4].to_i}"
+ perFile[file].delete(line)
+ end
+ end
+ end
+end
+
+perFile = Hash.new
+
+inputFile = File.new(ARGV[0])
+
+inputFile.each do |line|
+
+ splitted = line.strip.split(",")
+ if splitted.length == 7
+ key = splitted[0]
+ perFile[key] = Array.new if perFile[key] == nil
+ perFile[key].push(splitted[1..6])
+ end
+
+end
+
+inputFile.close
+
+adjustTimestamps(perFile)
+
+perFile.each_key do |file|
+ outfile = File.new("torrent-#{file}.log", "w")
+ perFile[file].each do |line|
+ outfile.puts line[0..4].join(",")
+ end
+ outfile.close
+end