src/libswift_udp/ext/vod_picker.cpp

   1 /*
   2  *  vod_picker.cpp
   3  *  swift
   4  *
   5  *  Created by Riccardo Petrocco.
   6  *  Copyright 2009-2012 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9
  10 #include "swift.h"
  11 #include <cassert>
  12
  13 using namespace swift;
  14
  15 #define HIGHPRIORITYWINDOW 45000;       // initial high priority window in bin unit
  16 #define MIDPRIORITYWINDOW 4;            // proportion of the mid priority window compared to the high pri. one
  17
  18 /** Picks pieces in VoD fashion. The stream is divided in three priority
  19  *  sets based on the current playback position. In the high priority set
  20  *  bins are selected in order, while on the medium and low priority sets
  21  *  in a rarest fist fashion */
  22 class VodPiecePicker : public PiecePicker {
  23
  24     binmap_t        ack_hint_out_;
  25     tbqueue         hint_out_;
  26     FileTransfer*   transfer_;
  27     Availability*       avail_;
  28     uint64_t        twist_;
  29     bin_t           range_;
  30     int                         playback_pos_;          // playback position in KB
  31     int                         high_pri_window_;
  32
  33 public:
  34
  35     VodPiecePicker (FileTransfer* file_to_pick_from) : ack_hint_out_(),
  36            transfer_(file_to_pick_from), twist_(0), range_(bin_t::ALL)
  37     {
  38         avail_ = &(transfer_->availability());
  39         binmap_t::copy(ack_hint_out_, file().ack_out());
  40         playback_pos_ = -1;
  41         high_pri_window_ = HIGHPRIORITYWINDOW;
  42     }
  43
  44     virtual ~VodPiecePicker() {}
  45
  46     HashTree& file() {
  47         return transfer_->file();
  48     }
  49
  50     virtual void Randomize (uint64_t twist) {
  51         // Arno, 2012-03-21: After consulting with Riccardo, disable
  52         // twisting for VOD PP. Randomization of peers over the bitmap
  53         // is already guaranteed by the ack_hint_out_ (prevents double requesting)
  54         // and rarest first.
  55     }
  56
  57     virtual void LimitRange (bin_t range) {
  58         range_ = range;
  59     }
  60
  61
  62     bin_t getTopBin(bin_t bin, uint64_t start, uint64_t size)
  63     {
  64         while (bin.parent().base_length() <= size && bin.parent().base_left() >= bin_t(start))
  65                 {
  66                         bin.to_parent();
  67                 }
  68         return bin;
  69     }
  70
  71
  72     bin_t pickUrgent (binmap_t& offer, uint64_t max_width, uint64_t size) {
  73
  74         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))
  75         bin_t hint = bin_t::NONE;
  76         uint64_t examined = 0;
  77                 binmap_t binmap;
  78
  79         // report the first bin we find
  80         while (hint.is_none() && examined < size)
  81         {
  82                 curr = getTopBin(curr, (playback_pos_+1)<<1, size-examined);
  83                 if (!ack_hint_out_.is_filled(curr))
  84                 {
  85                         binmap.fill(offer);
  86                                 binmap_t::copy(binmap, ack_hint_out_, curr);
  87                                 hint = binmap_t::find_complement(binmap, offer, twist_);
  88                                 binmap.clear();
  89                 }
  90                 examined += curr.base_length();
  91                 curr = bin_t(0, curr.base_right().layer_offset()+1 );
  92         }
  93
  94         if (!hint.is_none())
  95                 while (hint.base_length()>max_width && !hint.is_base()) // Arno,2012-01-17: stop!
  96                 hint.to_left();
  97
  98         return hint;
  99     }
 100
 101
 102     bin_t pickRarest (binmap_t& offer, uint64_t max_width, uint64_t start, uint64_t size) {
 103
 104         //fprintf(stderr,"%s #1 Picker -> choosing from mid/low priority \n",tintstr());
 105         bin_t curr = bin_t(start<<1);
 106                 bin_t hint = bin_t::NONE;
 107                 uint64_t examined = 0;
 108                 //uint64_t size = end-start;
 109                 bin_t rarest_hint = bin_t::NONE;
 110                 // TODO remove..
 111                 binmap_t binmap;
 112
 113                 // TODO.. this is the dummy version... put some logic in deciding what to DL
 114                 while (examined < size)
 115                 {
 116                         curr = getTopBin(curr, start<<1, size-examined);
 117
 118                         if (!ack_hint_out_.is_filled(curr))
 119                         {
 120                                 // remove
 121                                 //binmap_t::copy(binmap, offer);
 122                                 //binmap.reset(curr);
 123
 124                                 binmap.fill(offer);
 125                                 binmap_t::copy(binmap, ack_hint_out_, curr);
 126                                 //hint = binmap_t::find_complement(ack_hint_out_, offer, curr, twist_);
 127                                 hint = binmap_t::find_complement(binmap, offer, twist_);
 128                                 binmap.clear();
 129
 130                                 if (!hint.is_none())
 131                                 {
 132                                         if (avail_->size())
 133                                         {
 134                                                 rarest_hint = avail_->get(rarest_hint) < avail_->get(hint) ? rarest_hint : hint;
 135                                         }
 136                                         else
 137                                         {
 138                                                 examined = size;
 139                                                 rarest_hint = hint;
 140                                         }
 141                                 }
 142                         }
 143
 144                         examined += curr.base_length();
 145                         curr = bin_t(0, curr.base_right().layer_offset()+1 );
 146
 147                 }
 148
 149                 if (!rarest_hint.is_none())
 150                 {
 151                         if (avail_->size())
 152                                 rarest_hint = avail_->getRarest(rarest_hint, max_width);
 153                         else
 154                                 while (rarest_hint.base_length()>max_width && !rarest_hint.is_base()) // Arno,2012-01-17: stop!
 155                                         rarest_hint.to_left();
 156                 }
 157
 158                 return rarest_hint;
 159     }
 160
 161
 162     virtual bin_t Pick (binmap_t& offer, uint64_t max_width, tint expires)
 163     {
 164         bin_t hint;
 165         bool retry;
 166         char tmp[32];
 167         char set = 'X'; // TODO remove set var, only used for debug
 168
 169         // TODO check... the seconds should depend on previous speed of the peer
 170         while (hint_out_.size() && hint_out_.front().time<NOW-TINT_SEC*3/2) { // FIXME sec
 171             binmap_t::copy(ack_hint_out_, file().ack_out(), hint_out_.front().bin);
 172             hint_out_.pop_front();
 173         }
 174
 175         // get the first piece to estimate the size, whoever sends it first
 176         if (!file().size()) {
 177
 178             return bin_t(0,0);
 179         }
 180
 181         do {
 182                 uint64_t max_size = file().size_in_chunks() - playback_pos_ - 1;
 183                 max_size = high_pri_window_ < max_size ? high_pri_window_ : max_size;
 184
 185                         // check the high priority window for data we r missing
 186                         hint = pickUrgent(offer, max_width, max_size);
 187
 188                         // check the mid priority window
 189                         uint64_t start = (1 + playback_pos_) + HIGHPRIORITYWINDOW;      // start in KB
 190                         if (hint.is_none() && start < file().size_in_chunks())
 191                         {
 192                                 int mid = MIDPRIORITYWINDOW;
 193                                 int size = mid * HIGHPRIORITYWINDOW;                                            // size of window in KB
 194                                 // check boundaries
 195                                 max_size = file().size_in_chunks() - start;
 196                                 max_size = size < max_size ? size : max_size;
 197
 198                                 hint = pickRarest(offer, max_width, start, max_size);
 199
 200                                 //check low priority
 201                                 start += max_size;
 202                                 if (hint.is_none() && start < file().size_in_chunks())
 203                                 {
 204                                         size = file().size_in_chunks() - start;
 205                                         hint = pickRarest(offer, max_width, start, size);
 206                                         set = 'L';
 207                                 }
 208                                 else
 209                                         set = 'M';
 210                         }
 211                         else
 212                                 set = 'H';
 213
 214                         // unhinted/late data
 215                         if (!file().ack_out().is_empty(hint)) {
 216                                 binmap_t::copy(ack_hint_out_, file().ack_out(), hint);
 217                                 retry = true;
 218                         }
 219                         else
 220                                 retry = false;
 221
 222         } while (retry);
 223
 224
 225         if (hint.is_none()) {
 226                 // TODO, control if we want: check for missing hints (before playback pos.)
 227                 hint = binmap_t::find_complement(ack_hint_out_, offer, twist_);
 228                 // TODO: end-game mode
 229                 if (hint.is_none())
 230                         return hint;
 231                 else
 232                                 while (hint.base_length()>max_width && !hint.is_base()) // Arno,2012-01-17: stop!
 233                                         hint.to_left();
 234
 235
 236         }
 237
 238         assert(ack_hint_out_.is_empty(hint));
 239         ack_hint_out_.set(hint);
 240         hint_out_.push_back(tintbin(NOW,hint));
 241
 242
 243         // TODO clean ... printing percentage of completeness for the priority sets
 244         //status();
 245
 246         //fprintf(stderr,"%s #1 Picker -> picked %s\t from %c set\t max width %lu \n",tintstr(), hint.str(tmp), set, max_width );
 247         //if (avail_->size())
 248         return hint;
 249     }
 250
 251
 252     void updatePlaybackPos(int size = 1)
 253     {
 254         assert(size>-1);
 255         if (size< file().size_in_chunks() - playback_pos_ - 2)
 256                 playback_pos_ += size;
 257     }
 258
 259
 260     void status()
 261         {
 262                 int t = 0;
 263                 int x = HIGHPRIORITYWINDOW;
 264                 int y = MIDPRIORITYWINDOW;
 265                 int i = playback_pos_ + 1;
 266                 int end_high = (x+playback_pos_)<<1;
 267                 int end_mid = ((x*y)+x+playback_pos_)<<1;
 268                 int total = 0;
 269
 270
 271                 while (i<=end_high)
 272                 {
 273                         if (!file().ack_out().is_empty(bin_t(i)))
 274                                 t++;
 275                         i++;
 276                 }
 277                 total = t;
 278                 t = t*100/((x<<1)-1);
 279                 fprintf(stderr, "low %u, ", t);
 280                 t = 0;
 281                 while (i<=end_mid)
 282                 {
 283                         if (!file().ack_out().is_empty(bin_t(i)))
 284                                 t++;
 285                         i++;
 286                 }
 287                 total += t;
 288                 t = t*100/((x*y)<<1);
 289                 fprintf(stderr, "mid %u, ", t);
 290                 t = 0;
 291                 while (i<=file().size_in_chunks()<<1)
 292                 {
 293                         if (!file().ack_out().is_empty(bin_t(i)))
 294                                 t++;
 295                         i++;
 296                 }
 297                 total += t;
 298                 t = t*100/((file().size_in_chunks()-(x*y+playback_pos_))<<1);
 299                 fprintf(stderr, "low %u  -> in total: %i\t pp: %i\n", t, total, playback_pos_);
 300         }
 301
 302 };