3 * the main header file for libswift, normally you should only read this one
5 * Created by Victor Grishchenko on 3/6/09.
6 * Copyright 2009 Delft University of Technology. All rights reserved.
15 HANDSHAKE 00, channelid
16 Communicates the channel id of the sender. The
17 initial handshake packet also has the root hash
20 DATA 01, bin_32, buffer
24 ACKTS 08, bin_32, timestamp_32
25 Confirms successfull delivery of data. Used for
26 congestion control, as well.
29 Practical value of "hints" is to avoid overlap, mostly.
30 Hints might be lost in the network or ignored.
31 Peer might send out data without a hint.
32 Hint which was not responded (by DATA) in some RTTs
33 is considered to be ignored.
34 As peers cant pick randomly kilobyte here and there,
35 they send out "long hints" for non-base bins.
37 HASH 04, bin_32, sha1hash
38 SHA1 hash tree hashes for data verification. The
39 connection to a fresh peer starts with bootstrapping
40 him with peak hashes. Later, before sending out
41 any data, a peer sends the necessary uncle hashes.
43 PEX+/PEX- 05/06, ipv4 addr, port
44 Peer exchange messages; reports all connected and
45 disconected peers. Might has special meaning (as
46 in the case with swarm supervisors).
53 #include "compat/stdint.h"
68 #define NOW Datagram::now
70 /** tintbin is basically a pair<tint,bin64_t> plus some nice operators.
71 Most frequently used in different queues (acknowledgements, requests,
76 tintbin(const tintbin& b) : time(b.time), bin(b.bin) {}
77 tintbin() : time(TINT_NEVER), bin(bin64_t::NONE) {}
78 tintbin(tint time_, bin64_t bin_) : time(time_), bin(bin_) {}
79 tintbin(bin64_t bin_) : time(NOW), bin(bin_) {}
80 bool operator < (const tintbin& b) const
81 { return time > b.time; }
82 bool operator == (const tintbin& b) const
83 { return time==b.time && bin==b.bin; }
84 bool operator != (const tintbin& b) const
85 { return !(*this==b); }
88 typedef std::deque<tintbin> tbqueue;
89 typedef std::deque<bin64_t> binqueue;
90 typedef Address Address;
92 /** A heap (priority queue) for timestamped bin numbers (tintbins). */
96 int size () const { return data_.size(); }
97 bool is_empty () const { return data_.empty(); }
99 tintbin ret = data_.front();
100 std::pop_heap(data_.begin(),data_.end());
104 void push(const tintbin& tb) {
106 push_heap(data_.begin(),data_.end());
108 const tintbin& peek() const {
109 return data_.front();
113 /** swift protocol message types; these are used on the wire. */
123 SWIFT_SIGNED_HASH = 7,
124 SWIFT_MSGTYPE_SENT = 8,
125 SWIFT_MSGTYPE_RCVD = 9,
126 SWIFT_MESSAGE_COUNT = 10
130 class CongestionController;
134 /** A class representing single file transfer. */
139 /** A constructor. Open/submit/retrieve a file.
140 * @param file_name the name of the file
141 * @param root_hash the root hash of the file; zero hash if the file
142 is newly submitted */
143 FileTransfer(const char *file_name, const Sha1Hash& root_hash=Sha1Hash::ZERO);
145 /** Close everything. */
149 /** While we need to feed ACKs to every peer, we try (1) avoid
150 unnecessary duplication and (2) keep minimum state. Thus,
151 we use a rotating queue of bin completion events. */
152 //bin64_t RevealAck (uint64_t& offset);
153 /** Rotating queue read for channels of this transmission. */
154 int RevealChannel (int& i);
156 /** Find transfer by the root hash. */
157 static FileTransfer* Find (const Sha1Hash& hash);
158 /** Find transfer by the file descriptor. */
159 static FileTransfer* file (int fd) {
160 return fd<files.size() ? files[fd] : NULL;
163 /** The binmap for data already retrieved and checked. */
164 binmap_t& ack_out () { return file_.ack_out(); }
165 /** Piece picking strategy used by this transfer. */
166 PiecePicker& picker () { return *picker_; }
167 /** The number of channels working for this transfer. */
168 int channel_count () const { return hs_in_.size(); }
169 /** Hash tree checked file; all the hashes and data are kept here. */
170 HashTree& file() { return file_; }
171 /** File descriptor for the data file. */
172 int fd () const { return file_.file_descriptor(); }
173 /** Root SHA1 hash of the transfer (and the data file). */
174 const Sha1Hash& root_hash () const { return file_.root_hash(); }
178 static std::vector<FileTransfer*> files;
182 /** Piece picker strategy. */
183 PiecePicker* picker_;
185 /** Channels working for this transfer. */
188 std::deque<Address> pex_in_;
190 /** Messages we are accepting. */
196 void OnDataIn (bin64_t pos);
197 void OnPexIn (const Address& addr);
199 friend class Channel;
200 friend uint64_t Size (int fdes);
201 friend bool IsComplete (int fdes);
202 friend uint64_t Complete (int fdes);
203 friend uint64_t SeqComplete (int fdes);
204 friend int Open (const char* filename, const Sha1Hash& hash) ;
205 friend void Close (int fd) ;
209 /** PiecePicker implements some strategy of choosing (picking) what
210 to request next, given the possible range of choices:
211 data acknowledged by the peer minus data already retrieved.
212 May pick sequentially, do rarest first or in some other way. */
215 virtual void Randomize (uint64_t twist) = 0;
216 /** The piece picking method itself.
217 * @param offered the daata acknowledged by the peer
218 * @param max_width maximum number of packets to ask for
219 * @param expires (not used currently) when to consider request expired
220 * @return the bin number to request */
221 virtual bin64_t Pick (binmap_t& offered, uint64_t max_width, tint expires) = 0;
227 virtual void AddPeer (const Address& addr, const Sha1Hash& root) = 0;
228 virtual Address GetPeer (const Sha1Hash& for_root) = 0;
234 DataStorer (const Sha1Hash& id, size_t size);
235 virtual size_t ReadData (bin64_t pos,uint8_t** buf) = 0;
236 virtual size_t WriteData (bin64_t pos, uint8_t* buf, size_t len) = 0;
240 /** swift channel's "control block"; channels loosely correspond to TCP
241 connections or FTP sessions; one channel is created for one file
242 being transferred between two peers. As we don't need buffers and
243 lots of other TCP stuff, sizeof(Channel+members) must be below 1K.
244 Normally, API users do not deal with this class. */
247 Channel (FileTransfer* file, int socket=-1, Address peer=Address());
259 static const char* SEND_CONTROL_MODES[];
262 RecvDatagram (int socket);
263 static void Loop (tint till);
265 void Recv (Datagram& dgram);
269 void OnAck (Datagram& dgram);
270 void OnTs (Datagram& dgram);
271 bin64_t OnData (Datagram& dgram);
272 void OnHint (Datagram& dgram);
273 void OnHash (Datagram& dgram);
274 void OnPex (Datagram& dgram);
275 void OnHandshake (Datagram& dgram);
276 void AddHandshake (Datagram& dgram);
277 bin64_t AddData (Datagram& dgram);
278 void AddAck (Datagram& dgram);
279 void AddTs (Datagram& dgram);
280 void AddHint (Datagram& dgram);
281 void AddUncleHashes (Datagram& dgram, bin64_t pos);
282 void AddPeakHashes (Datagram& dgram);
283 void AddPex (Datagram& dgram);
285 void BackOffOnLosses (float ratio=0.5);
286 tint SwitchSendControl (int control_mode);
287 tint NextSendTime ();
288 tint KeepAliveNextSendTime ();
289 tint PingPongNextSendTime ();
290 tint CwndRateNextSendTime ();
291 tint SlowStartNextSendTime ();
292 tint AimdNextSendTime ();
293 tint LedbatNextSendTime ();
295 static int MAX_REORDERING;
298 static tint MAX_SEND_INTERVAL;
299 static tint LEDBAT_TARGET;
300 static float LEDBAT_GAIN;
301 static tint LEDBAT_DELAY_BIN;
302 static bool SELF_CONN_OK;
304 const std::string id_string () const;
305 /** A channel is "established" if had already sent and received packets. */
306 bool is_established () { return peer_channel_id_ && own_id_mentioned_; }
307 FileTransfer& transfer() { return *transfer_; }
308 HashTree& file () { return transfer_->file(); }
309 const Address& peer() const { return peer_; }
310 tint ack_timeout () {
311 return rtt_avg_ + std::max(dev_avg_,MIN_DEV)*4;
313 uint32_t id () const { return id_; }
315 static int DecodeID(int scrambled);
316 static int EncodeID(int unscrambled);
317 static Channel* channel(int i) {
318 return i<channels.size()?channels[i]:NULL;
320 static void CloseTransfer (FileTransfer* trans);
321 static SOCKET default_socket() { return sockets[0]; }
324 /** Channel id: index in the channel array. */
326 /** Socket address of the peer. */
328 /** The UDP socket fd. */
330 /** Descriptor of the file in question. */
331 FileTransfer* transfer_;
332 /** Peer channel id; zero if we are trying to open a channel. */
333 uint32_t peer_channel_id_;
334 bool own_id_mentioned_;
335 /** Peer's progress, based on acknowledgements. */
337 /** Last data received; needs to be acked immediately. */
339 bin64_t data_in_dbl_;
340 /** The history of data sent and still unacknowledged. */
342 bin64_t data_out_cap_;
343 /** Index in the history array. */
345 /** Transmit schedule: in most cases filled with the peer's hints */
347 /** Hints sent (to detect and reschedule ignored hints). */
349 uint64_t hint_out_size_;
350 /** Types of messages the peer accepts. */
353 //tint last_send_time, last_recv_time;
356 /** Smoothed averages for RTT, RTT deviation and data interarrival periods. */
357 tint rtt_avg_, dev_avg_, dip_avg_;
358 tint last_send_time_;
359 tint last_recv_time_;
360 tint last_data_out_time_;
361 tint last_data_in_time_;
362 tint last_loss_time_;
363 tint next_send_time_;
364 tint peer_send_time_;
365 /** Congestion window; TODO: int, bytes. */
367 /** Data sending interval. */
369 /** The congestion control strategy. */
371 /** Datagrams (not data) sent since last recv. */
372 int sent_since_recv_;
373 /** Recent acknowlegements for data previously sent. */
374 int ack_rcvd_recent_;
375 /** Recent non-acknowlegements (losses) of data previously sent. */
376 int ack_not_rcvd_recent_;
377 /** LEDBAT one-way delay machinery */
378 tint owd_min_bins_[4];
380 tint owd_min_bin_start_;
381 tint owd_current_[4];
387 int PeerBPS() const {
388 return TINT_SEC / dip_avg_ * 1024;
390 /** Get a request for one packet from the queue of peer's requests. */
391 bin64_t DequeueHint();
392 void CleanDataOut (bin64_t acks_pos=bin64_t::NONE);
393 void CleanStaleHintOut();
394 void CleanHintOut(bin64_t pos);
397 static PeerSelector* peer_selector;
399 static SOCKET sockets[8];
400 static int socket_count;
401 static tint last_tick;
402 static tbheap send_queue;
404 static Address tracker;
405 static std::vector<Channel*> channels;
407 friend int Listen (Address addr);
408 friend void Shutdown (int sock_des);
409 friend void AddPeer (Address address, const Sha1Hash& root);
410 friend void SetTracker(const Address& tracker);
411 friend int Open (const char*, const Sha1Hash&) ; // FIXME
417 /*************** The top-level API ****************/
418 /** Start listening a port. Returns socket descriptor. */
419 int Listen (Address addr);
420 /** Run send/receive loop for the specified amount of time. */
421 void Loop (tint till);
422 /** Stop listening to a port. */
423 void Shutdown (int sock_des=-1);
425 /** Open a file, start a transmission; fill it with content for a given root hash;
426 in case the hash is omitted, the file is a fresh submit. */
427 int Open (const char* filename, const Sha1Hash& hash=Sha1Hash::ZERO) ;
428 /** Get the root hash for the transmission. */
429 const Sha1Hash& RootMerkleHash (int file) ;
430 /** Close a file and a transmission. */
431 void Close (int fd) ;
432 /** Add a possible peer which participares in a given transmission. In the case
433 root hash is zero, the peer might be talked to regarding any transmission
434 (likely, a tracker, cache or an archive). */
435 void AddPeer (Address address, const Sha1Hash& root=Sha1Hash::ZERO);
437 void SetTracker(const Address& tracker);
439 /** Returns size of the file in bytes, 0 if unknown. Might be rounded up to a kilobyte
440 before the transmission is complete. */
441 uint64_t Size (int fdes);
442 /** Returns the amount of retrieved and verified data, in bytes.
443 A 100% complete transmission has Size()==Complete(). */
444 uint64_t Complete (int fdes);
445 bool IsComplete (int fdes);
446 /** Returns the number of bytes that are complete sequentially, starting from the
447 beginning, till the first not-yet-retrieved packet. */
448 uint64_t SeqComplete (int fdes);
451 //uint32_t Width (const tbinvec& v);
454 /** Must be called by any client using the library */
455 void LibraryInit(void);