diff options
author | tpearson <tpearson@283d02a7-25f6-0310-bc7c-ecb5cbfe19da> | 2010-01-20 02:37:40 +0000 |
---|---|---|
committer | tpearson <tpearson@283d02a7-25f6-0310-bc7c-ecb5cbfe19da> | 2010-01-20 02:37:40 +0000 |
commit | 9ad5c7b5e23b4940e7a3ea3ca3a6fb77e6a8fab0 (patch) | |
tree | d088b5210e77d9fa91d954d8550e00e372b47378 /estimation-scripts | |
download | ktorrent-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.rb | 100 | ||||
-rw-r--r-- | estimation-scripts/Estimators.rb | 90 | ||||
-rw-r--r-- | estimation-scripts/README | 40 | ||||
-rw-r--r-- | estimation-scripts/Sample.rb | 64 | ||||
-rw-r--r-- | estimation-scripts/demo.rb | 18 | ||||
-rw-r--r-- | estimation-scripts/enable-logging.diff | 224 | ||||
-rw-r--r-- | estimation-scripts/processlog.rb | 63 |
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 |