X-Git-Url: http://p2p-next.cs.pub.ro/gitweb/?a=blobdiff_plain;f=src%2Flibswift_udp%2Fext%2Fvod_picker.cpp;fp=src%2Flibswift_udp%2Fext%2Fvod_picker.cpp;h=690b4dcd9bb75d7d822e2e542027d67b2879f2b8;hb=46f3ca346fe499ba3e8f595fc5c2aa2b3e3c4d5f;hp=0000000000000000000000000000000000000000;hpb=d8da6fc1273a2acee935a15761b77a73424faef5;p=swifty.git

diff --git a/src/libswift_udp/ext/vod_picker.cpp b/src/libswift_udp/ext/vod_picker.cpp
new file mode 100644
index 0000000..690b4dc
--- /dev/null
+++ b/src/libswift_udp/ext/vod_picker.cpp
@@ -0,0 +1,302 @@
+/*
+ *  vod_picker.cpp
+ *  swift
+ *
+ *  Created by Riccardo Petrocco.
+ *  Copyright 2009-2012 Delft University of Technology. All rights reserved.
+ *
+ */
+
+#include "swift.h"
+#include <cassert>
+
+using namespace swift;
+
+#define HIGHPRIORITYWINDOW 45000;	// initial high priority window in bin unit
+#define MIDPRIORITYWINDOW 4; 		// proportion of the mid priority window compared to the high pri. one
+
+/** Picks pieces in VoD fashion. The stream is divided in three priority
+ *  sets based on the current playback position. In the high priority set
+ *  bins are selected in order, while on the medium and low priority sets
+ *  in a rarest fist fashion */
+class VodPiecePicker : public PiecePicker {
+
+    binmap_t        ack_hint_out_;
+    tbqueue         hint_out_;
+    FileTransfer*   transfer_;
+    Availability* 	avail_;
+    uint64_t        twist_;
+    bin_t           range_;
+    int				playback_pos_;		// playback position in KB
+    int				high_pri_window_;
+
+public:
+
+    VodPiecePicker (FileTransfer* file_to_pick_from) : ack_hint_out_(),
+           transfer_(file_to_pick_from), twist_(0), range_(bin_t::ALL)
+    {
+    	avail_ = &(transfer_->availability());
+        binmap_t::copy(ack_hint_out_, file().ack_out());
+        playback_pos_ = -1;
+        high_pri_window_ = HIGHPRIORITYWINDOW;
+    }
+
+    virtual ~VodPiecePicker() {}
+
+    HashTree& file() {
+        return transfer_->file();
+    }
+
+    virtual void Randomize (uint64_t twist) {
+    	// Arno, 2012-03-21: After consulting with Riccardo, disable
+    	// twisting for VOD PP. Randomization of peers over the bitmap
+    	// is already guaranteed by the ack_hint_out_ (prevents double requesting)
+    	// and rarest first.
+    }
+
+    virtual void LimitRange (bin_t range) {
+        range_ = range;
+    }
+
+
+    bin_t getTopBin(bin_t bin, uint64_t start, uint64_t size)
+    {
+    	while (bin.parent().base_length() <= size && bin.parent().base_left() >= bin_t(start))
+		{
+			bin.to_parent();
+		}
+    	return bin;
+    }
+
+
+    bin_t pickUrgent (binmap_t& offer, uint64_t max_width, uint64_t size) {
+
+    	bin_t curr = bin_t((playback_pos_+1)<<1); // the base bin will be indexed by the double of the value (bin(4) == bin(0,2))
+    	bin_t hint = bin_t::NONE;
+    	uint64_t examined = 0;
+		binmap_t binmap;
+
+    	// report the first bin we find
+    	while (hint.is_none() && examined < size)
+    	{
+    		curr = getTopBin(curr, (playback_pos_+1)<<1, size-examined);
+    		if (!ack_hint_out_.is_filled(curr))
+    		{
+    			binmap.fill(offer);
+				binmap_t::copy(binmap, ack_hint_out_, curr);
+				hint = binmap_t::find_complement(binmap, offer, twist_);
+				binmap.clear();
+    		}
+    		examined += curr.base_length();
+    		curr = bin_t(0, curr.base_right().layer_offset()+1 );
+    	}
+
+    	if (!hint.is_none())
+    		while (hint.base_length()>max_width && !hint.is_base()) // Arno,2012-01-17: stop!
+    	        hint.to_left();
+
+    	return hint;
+    }
+
+
+    bin_t pickRarest (binmap_t& offer, uint64_t max_width, uint64_t start, uint64_t size) {
+
+    	//fprintf(stderr,"%s #1 Picker -> choosing from mid/low priority \n",tintstr());
+    	bin_t curr = bin_t(start<<1);
+		bin_t hint = bin_t::NONE;
+		uint64_t examined = 0;
+		//uint64_t size = end-start;
+		bin_t rarest_hint = bin_t::NONE;
+		// TODO remove..
+		binmap_t binmap;
+
+		// TODO.. this is the dummy version... put some logic in deciding what to DL
+		while (examined < size)
+		{
+			curr = getTopBin(curr, start<<1, size-examined);
+
+			if (!ack_hint_out_.is_filled(curr))
+			{
+				// remove
+				//binmap_t::copy(binmap, offer);
+				//binmap.reset(curr);
+
+				binmap.fill(offer);
+				binmap_t::copy(binmap, ack_hint_out_, curr);
+				//hint = binmap_t::find_complement(ack_hint_out_, offer, curr, twist_);
+				hint = binmap_t::find_complement(binmap, offer, twist_);
+				binmap.clear();
+
+				if (!hint.is_none())
+				{
+					if (avail_->size())
+					{
+						rarest_hint = avail_->get(rarest_hint) < avail_->get(hint) ? rarest_hint : hint;
+					}
+					else
+					{
+						examined = size;
+						rarest_hint = hint;
+					}
+				}
+			}
+
+			examined += curr.base_length();
+			curr = bin_t(0, curr.base_right().layer_offset()+1 );
+
+		}
+
+		if (!rarest_hint.is_none())
+		{
+			if (avail_->size())
+				rarest_hint = avail_->getRarest(rarest_hint, max_width);
+			else
+				while (rarest_hint.base_length()>max_width && !rarest_hint.is_base()) // Arno,2012-01-17: stop!
+					rarest_hint.to_left();
+		}
+
+		return rarest_hint;
+    }
+
+
+    virtual bin_t Pick (binmap_t& offer, uint64_t max_width, tint expires)
+    {
+    	bin_t hint;
+    	bool retry;
+        char tmp[32];
+        char set = 'X';	// TODO remove set var, only used for debug
+
+    	// TODO check... the seconds should depend on previous speed of the peer
+        while (hint_out_.size() && hint_out_.front().time<NOW-TINT_SEC*3/2) { // FIXME sec
+            binmap_t::copy(ack_hint_out_, file().ack_out(), hint_out_.front().bin);
+            hint_out_.pop_front();
+        }
+
+        // get the first piece to estimate the size, whoever sends it first
+        if (!file().size()) {
+
+            return bin_t(0,0);
+        }
+
+        do {
+        	uint64_t max_size = file().size_in_chunks() - playback_pos_ - 1;
+        	max_size = high_pri_window_ < max_size ? high_pri_window_ : max_size;
+
+			// check the high priority window for data we r missing
+			hint = pickUrgent(offer, max_width, max_size);
+
+			// check the mid priority window
+			uint64_t start = (1 + playback_pos_) + HIGHPRIORITYWINDOW;	// start in KB
+			if (hint.is_none() && start < file().size_in_chunks())
+			{
+				int mid = MIDPRIORITYWINDOW;
+				int size = mid * HIGHPRIORITYWINDOW;						// size of window in KB
+				// check boundaries
+				max_size = file().size_in_chunks() - start;
+				max_size = size < max_size ? size : max_size;
+
+				hint = pickRarest(offer, max_width, start, max_size);
+
+				//check low priority
+				start += max_size;
+				if (hint.is_none() && start < file().size_in_chunks())
+				{
+					size = file().size_in_chunks() - start;
+					hint = pickRarest(offer, max_width, start, size);
+					set = 'L';
+				}
+				else
+					set = 'M';
+			}
+			else
+				set = 'H';
+
+			// unhinted/late data
+			if (!file().ack_out().is_empty(hint)) {
+				binmap_t::copy(ack_hint_out_, file().ack_out(), hint);
+				retry = true;
+			}
+			else
+				retry = false;
+
+        } while (retry);
+
+
+        if (hint.is_none()) {
+        	// TODO, control if we want: check for missing hints (before playback pos.)
+        	hint = binmap_t::find_complement(ack_hint_out_, offer, twist_);
+        	// TODO: end-game mode
+        	if (hint.is_none())
+        		return hint;
+        	else
+				while (hint.base_length()>max_width && !hint.is_base()) // Arno,2012-01-17: stop!
+					hint.to_left();
+
+
+        }
+
+        assert(ack_hint_out_.is_empty(hint));
+        ack_hint_out_.set(hint);
+        hint_out_.push_back(tintbin(NOW,hint));
+
+
+        // TODO clean ... printing percentage of completeness for the priority sets
+        //status();
+
+        //fprintf(stderr,"%s #1 Picker -> picked %s\t from %c set\t max width %lu \n",tintstr(), hint.str(tmp), set, max_width );
+        //if (avail_->size())
+        return hint;
+    }
+
+
+    void updatePlaybackPos(int size = 1)
+    {
+    	assert(size>-1);
+    	if (size< file().size_in_chunks() - playback_pos_ - 2)
+    		playback_pos_ += size;
+    }
+
+
+    void status()
+	{
+		int t = 0;
+		int x = HIGHPRIORITYWINDOW;
+		int y = MIDPRIORITYWINDOW;
+		int i = playback_pos_ + 1;
+		int end_high = (x+playback_pos_)<<1;
+		int end_mid = ((x*y)+x+playback_pos_)<<1;
+		int total = 0;
+
+
+		while (i<=end_high)
+		{
+			if (!file().ack_out().is_empty(bin_t(i)))
+				t++;
+			i++;
+		}
+		total = t;
+		t = t*100/((x<<1)-1);
+		fprintf(stderr, "low %u, ", t);
+		t = 0;
+		while (i<=end_mid)
+		{
+			if (!file().ack_out().is_empty(bin_t(i)))
+				t++;
+			i++;
+		}
+		total += t;
+		t = t*100/((x*y)<<1);
+		fprintf(stderr, "mid %u, ", t);
+		t = 0;
+		while (i<=file().size_in_chunks()<<1)
+		{
+			if (!file().ack_out().is_empty(bin_t(i)))
+				t++;
+			i++;
+		}
+		total += t;
+		t = t*100/((file().size_in_chunks()-(x*y+playback_pos_))<<1);
+		fprintf(stderr, "low %u  -> in total: %i\t pp: %i\n", t, total, playback_pos_);
+	}
+
+};