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

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