doc/index.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 TRANSITIONAL//EN" "http://www.w3.org/TR/html4/loose.dtd">
   2 <html>
   3
   4 <head>
   5         <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   6         <title>swift: the multiparty transport protocol</title>
   7         <link rel="stylesheet" href="style.css" type="text/css">
   8         <script src="http://code.jquery.com/jquery-latest.js"></script>
   9         <script>
  10         $(document).ready(function(){
  11                 $("div.fold>h4, div.fold>h3, div.fold>h2").click(function () {
  12                         $("div.fold>p, div.fold>ul, div.fold>div").hide("fast");
  13                 $(this).siblings().each(
  14                                 function(){
  15                                         $(this).show("normal");
  16                                 }
  17                         );
  18                 });
  19         });
  20   </script>
  21 </head>
  22 <body>
  23
  24 <div>
  25         <img id=logo src="apusapus.png"/>
  26         <h1><i>swift:</i> the multiparty transport protocol</h1>
  27
  28         <div id='motto'>Turn the Net into a single data Cloud!</div>
  29
  30     <div id='abstract'>
  31     <b>Abstract</b>.
  32     &nbsp;<i>swift</i> is a multiparty transport protocol; its mission is to
  33     disseminate content among a swarm of peers. It is a sort of BitTorrent
  34     at the transport layer. <a href="http://bittorrent.org">BitTorrent</a> can't
  35     underlie a distributed filesystem or deliver Web pages; while
  36     <a href="http://github.com/gritzko/swift/raw/master/doc/swift-protocol.txt">swift</a> can.
  37     <a href="http://github.com/gritzko/swift">libswift</a>
  38     is 4000 lines of cross-platform C++ code
  39     licensed under LGPL; it runs on misc Unices, Mac OS X and Windows;
  40     it uses UDP with <a href="http://tools.ietf.org/wg/ledbat/">LEDBAT</a> congestion control.
  41     So far our speed record is mere 400Mbps, but we are working on that.
  42     The library is delivered as a part of <a href="http://p2p-next.org">P2P-Next</a>,
  43     funded by <a href="http://cordis.europa.eu/fp7/dc/index.cfm">EU FP7</a>.
  44     </div>
  45
  46         <div>   <h2>Ideas</h2>
  47                 <p>As <a href="http://en.wikipedia.org/wiki/Content-centric_networking">
  48                 wise people say</a>, the Internet was initially built for
  49                 remotely connecting scientists to expensive supercomputers (whose computing
  50                 power was comparable to modern cell phones). Thus, they supported the abstraction
  51                 of <i>conversation</i>. Currently, the Internet is mostly used for <i>disseminating</i>
  52                 content to the masses, which mismatch definitely creates some problems.</p>
  53
  54                 <p>The <i>swift</i> protocol is a content-centric multiparty transport
  55                 protocol. Basically, it answers one and only one question: <i>"Here is a
  56                 <a href="http://en.wikipedia.org/wiki/Hash_function">hash</a>!
  57                 Give me data for it!"</i> A bit oversimplifying, it might be understood as
  58                 <a href="http://en.wikipedia.org/wiki/BitTorrent">BitTorrent</a>
  59                 at the <a href="http://en.wikipedia.org/wiki/Transport_Layer">
  60                 transport layer</a>. Ultimately, it aims at the abstraction of the Internet
  61                 as a single big data <a href="http://en.wikipedia.org/wiki/Cloud_computing">
  62                 Cloud</a>. Such entities as storage, servers and connections are abstracted
  63                 away and are virtually invisible at the API layer. Given a hash,
  64         the data is received
  65                 from whatever source available and data integrity is checked
  66                 cryptographically with <a href="http://en.wikipedia.org/wiki/Hash_tree">
  67                 Merkle hash trees</a>.</p>
  68
  69                 <p>An old Unix adage says: "free memory is wasted memory". Once a
  70                 computer is powered on, there is no benefit in keeping some memory
  71                 unoccupied. We may extend this principle a bit further:
  72                 <ul>
  73                         <li>free bandwidth is wasted bandwidth;
  74                         <li>free storage is wasted storage.
  75                 </ul>
  76                 Unless your power budget is really tight, there is no sense in conserving
  77                 either. Thus, instead of putting emphasis on reciprocity and incentives
  78                 we focus on ligther-footprint code,
  79                 <a href="http://tools.ietf.org/wg/ledbat/">non-intrusive</a>
  80                 <a href="http://en.wikipedia.org/wiki/TCP_congestion_avoidance_algorithm">
  81                 congestion control</a> and automatic disk space management.
  82                 </p>
  83
  84                 <p>Currently, most parts of the protocol/library are implemented, pass
  85                 basic testing and successfully transfer data on real networks.
  86                 After more scrutinized testing, the protocol and the library are expected
  87                 to be real-life-ready in March'10.
  88                 </p>
  89         </div>
  90
  91         <div id='design'>       <h2>Design of the protocol</h2>
  92
  93                 <p>Most features of the protocol are defined by its function of
  94                 content-centric multiparty transport protocol. It entirely drops the TCP's
  95                 abstraction of sequential reliable data stream delivery as it is redundant in
  96                 our case. For example, out-of-order data could still be saved and the same
  97                 piece of data might be always received from another peer.
  98                 Being implemented over UDP, the protocol does its best to make
  99                 every datagram self-contained.
 100                 In general, cutting of unneeded functions and aggressive layer collapsing
 101                 greatly simplified the protocol, compared to e.g. the BitTorrent+TCP stack.</p>
 102
 103                 <div class='fold'>      <h3>Atomic datagrams, not data stream</h3>
 104                 <p>To achieve per-datagram flexibility of data flow and also to adapt to
 105                 the unreliable medium (UDP, and, ultimately, IP), the protocol was built
 106                 around the abstraction of atomic datagrams.
 107                 Ideally, once received, a datagram is either
 108                 immediately discarded or permanently accepted, ready to be forwarded to
 109                 other peers.
 110                 For the sake of flexibility, most of the protocol's messages
 111                 are optional. It also has no "standard" header. Instead, each datagram
 112                 is a concatenation of zero or more messages. No message ever spans two
 113                 datagrams. Except for the data pieces themselves, no message is
 114                 acknowledged, as thus, not guaranteed to be delivered.</p>
 115                 </div>
 116
 117                 <div class='fold'>      <h3>Scale-independent unit system</h3>
 118                 <p>To avoid a multilayered request/acknowledgement system, when every
 119                 next layer does basically the same, but for bigger chunks of data, as
 120                 it is the case with BitTorrent+TCP packet-block-piece-file-torrent
 121                 stacking, <i>swift</i> employs a scale-independent acknowledgement/
 122                 request system, where data is measured by aligned power-of-2 intervals
 123                 (so called bins). All acknowledgements and requests are done in terms
 124                 of bins.</p>
 125                 </div>
 126
 127                 <div class='fold'>      <h3>Datagram-level integrity checks</h3>
 128                 <p><i>swift</i> builds Merkle hash trees down to every single packet
 129                 (1 kilobyte of data). Once data is transmitted, all uncle hashes
 130                 necessary for verification are prepended to the same datagram.
 131                 As the receiver constantly remembers old hashes, the average number
 132                 of "new" hashes, which have to be transmitted is small,
 133                 normally around 1 per packet of data.</p>
 134                 </div>
 135
 136                 <div class='fold'>      <h3>NAT traversal by design</h3>
 137                 <p>The only method of peer discovery in <i>swift</i> is
 138                 <a href="http://en.wikipedia.org/wiki/Peer_exchange">PEX</a>:
 139                 a third peer initiates a connection between two of its contacted peers.
 140                 The protocol's handshake is engineered to perform simple NAT hole
 141                 punching transparently, in case that is needed.
 142                 </p>
 143                 </div>
 144
 145                 <div class='fold'>      <h3>Subsetting of the protocol</h3>
 146                 <p>Different kinds of peers might implement different subsets of messages;
 147                 a "tracker", for example, uses the same protocol as every peer, except
 148                 it only accepts the HANDSHAKE message and the HASH message (to let peers
 149                 explain what content they are interested in), while returning only
 150                 HANDSHAKE and PEX_ADD messages (to return the list of peers).
 151                 Different subsets of accepted/emitted messages may correspond to push/pull
 152                 peers, plain trackers, hash storing trackers, live streaming peers etc.
 153                 </p>
 154                 </div>
 155
 156                 <div class='fold'>      <h3>Push AND pull</h3>
 157                 <p>The protocol allows both for PUSH (sender decides what to send) and
 158                 PULL (receiver explicitly requests the data). PUSH is normally used as
 159                 a fallback if PULL fails; also, the sender may ignore requests and send
 160                 any data it finds convenient to send. Merkle hash trees allow this
 161                 flexibility without causing security implications.</p>
 162                 </div>
 163
 164                 <div class='fold'>      <h3>No transmission metadata</h3>
 165                 <p></p>
 166                 </div>
 167         </div>
 168
 169         <div>   <h2>Specifications and documentation</h2>
 170                 <p>
 171                 <ul>
 172                 <li><a href="http://github.com/gritzko/swift/raw/master/doc/swift-protocol.txt">
 173                         internet draft style technical description</a>
 174             <li><a href="">article</a>
 175                 </ul>
 176                 </p>
 177         </div>
 178
 179         <div>   <h2>The code</h2>
 180                 <ul>
 181                 <li><a href="http://97.107.136.211/files/p2tp.tar.gz">fairly recent tarball</a>
 182                 <li><a href="http://github.com/gritzko/swift"><i>swift</i> at github</a>
 183                 </ul>
 184         </div>
 185
 186         <div> <h2>Frequently asked questions</h2>
 187
 188         <div class="fold"> <h3>Well, why "swift"?</h3>
 189                 <p>That name served well to many other protocols; we hope it will serve well to ours.
 190                 You may count it as a meta-joke. The working name for the protocol was "VicTorrent".
 191                 We also insist on lowercase italic <i>"swift"</i> to keep the name formally  unique
 192                 (for some definition of unique).</p>
 193         </div>
 194
 195         <div> <h3>How is it different from... </h3>
 196
 197                 <div class='fold'><h4>...TCP?</h4>
 198                 <p>TCP emulates reliable in-order delivery ("data pipe") over
 199                 chaotic unreliable multi-hop networks. TCP has no idea what data it is dealing
 200                 with, as the data is passed from the userspace.
 201                 In our case, the data is fixed in advance and many peers participate in
 202                 distributing the same data. Orderness of delivery is of little importance and
 203                 unreliability is naturally compensated by redundance.
 204                 Thus, many functions of TCP turn out to be redundant.
 205                 The only function of TCP that is also critical for <i>swift</i> is the congestion
 206                 control, but... we need our own custom congestion control! Thus, we did not use
 207                 TCP.</p>
 208                 <p>That led both to hurdles and to some savings. As one example, every TCP
 209                 connection needs to maintain buffers for the data that has left the sender's userspace, but
 210                 did not yet arrive at the receiver's userspace. As we know that we are dealing
 211                 with the same fixed data, we don't need to maintain per-connection buffers.
 212                 </p>
 213                 </div>
 214
 215                 <div class='fold'><h4>...UDP?</h4>
 216                 <p>UDP, which is the thinniest wrapper around <a href="http://en.wikipedia.org/wiki/IPv4">
 217                 IP</a>, is our choiсe of underlying protocol. From the standpoint of ideology, a
 218                 transport protocol should be implemented over IP, but unfortunately that causes
 219                 some chicken-and-egg problems, like a need to get into the kernel to get deployments,
 220                 and a need to get deployments to be accepted into the kernel.
 221                 UDP is also quite nice in regard to NAT penetration.</p>
 222                 </div>
 223
 224                 <div class='fold'><h4>...BitTorrent?</h4>
 225                 <p>BitTorrent is an application-level protocol and quite a heavy one. We focused
 226                 on fitting our protocol into the restrictions of the transport layer, assuming
 227                 that the protocol might eventually be included into operating system kernels.
 228                 For example, we stripped the protocol of any transmission's metadata (the
 229                 .torrent file); leaving a file's root hash as the only parameter.</p>
 230                 </div>
 231
 232                 <div class='fold'><h4>...µTorrent's µTP?</h4>
 233                 <p>Historically, BitTorrent gained lots of adaptations to its underlying
 234                 transport. First and foremost, TCP is unable to prioritize traffic, so BitTorrent
 235                 needed to coerce users somehow to tolerate inconviniences of seeding. That caused
 236                 tit4tat and, to significant degree, rarest-first. Another example is the 4
 237                 upload slots limitation. (Well, apparently, some architectural decisions in
 238                 BitTorrent were dictated by oddities Windows 95, but... never mind.)
 239                 Eventually, BitTorrent developers came to the conclusion that not annoying
 240                 the user in the first place is probably a better stimulus. So they came up with
 241                 the <a href='http://www.ietf.org/dyn/wg/charter/ledbat-charter.html'>LEDBAT</a>
 242                 congestion control algorithm (Low Extra Delay Background Transport).
 243                 LEDBAT allows a peer to seed without interfering with the regular traffic
 244                 (in plain words, without slowing down the browser).
 245                 To integrate the novel congestion control algorithm into BitTorrent incrementally,
 246                 BitTorrent Inc had to develop TCP-alike transport named
 247                 <a href="http://en.wikipedia.org/wiki/Micro_Transport_Protocol">µTP</a>.
 248                 The <i>swift</i> project (then named VicTorrent) was started when we tried to understand
 249                 what happens if we'll strip BitTorrent of any Win95-specific, TCP-specific
 250                 or Python-specific workarounds. As it turns out, not much was left.
 251                 </p>
 252                 </div>
 253
 254                 <div class='fold'><h4>...Van Jacobson's CCN?</h4>
 255                 <p><a href="http://www.parc.com/about/people/88/van-jacobson.html">Van Jacobson's</a>
 256                 team in PARC is doing exploratory research on
 257                 <a href="http://en.wikipedia.org/wiki/Content-centric_networking">content-centric
 258                 networking</a>. While BitTorrent works at layer 5 (application), we go to layer 4 (transport),
 259                 PARC people are bold enough to go to layer 3 and to propose a complete replacement
 260                 for the entire TCP/IP world. That is certainly a compelling vision, but we focus
 261                 on near future (<10 years); while <a href="http://www.ccnx.org/">CCNx</a> is a
 262                 much more ambitious rework.</p>
 263                 </div>
 264
 265                 <div class='fold'><h4>...DCCP?</h4>
 266                 <p>This question arises quite frequently as DCCP is a congestion-controlled datagram
 267                 transport. The option of implementing <i>swift</i> over
 268                 <a href="http://en.wikipedia.org/wiki/DCCP">DCCP</a> was considered,
 269                 but the inconvinience of working with an esoteric transport was not compensated by the
 270                 added value of DCCP, which is limited to one mode of congestion control being readily
 271                 implemented.
 272                 Architectural restrictions imposed by DCCP were also found to be a major inconvenience.
 273                 Last but not least, currently only Linux supports DCCP at the kernel level.</p>
 274                 </div>
 275
 276                 <div class='fold'><h4>...SCTP?</h4>
 277                 <p><a href="http://en.wikipedia.org/wiki/SCTP">SCTP</a> is a protocol fixing some
 278                 shortcomings of TCP mostly in the context of telephony. As it was the case with
 279                 DCCP, contributions of SCTP were of little interest to us, while things we really
 280                 needed were missing from SCTP. Still, we must admit that we employ quite a similar
 281                 message-oriented model (as opposed to the TCP's stream-oriented). </p>
 282                 </div>
 283
 284         </div>
 285
 286         <div class='fold'>      <h2>Who we are</h2>
 287                 <p>
 288                 <ul>
 289                 <li> <a href="http://p2p-next.org/">P2P-Next Project</a>, EU 7th Framework Program
 290                 <li> <a href="http://ewi.tudelft.nl">Delft University of Technology</a> EWI PDS
 291                 <li> <a href="http://www.st.ewi.tudelft.nl/~pouwelse/">Dr. Johan Pouwelse</a>
 292                 <li> <a href="http://www.tribler.org/trac/wiki/VictorGrishchenko">
 293                 Dr. Victor Grishchenko</a>
 294                 </ul>
 295                 </p>
 296         </div>
 297
 298         <div class=fold>        <h2>Contacts&amp;feedback</h2>
 299                 <p><a href="mailto:victor.grishchenko@gmail.com">mail us</a></p>
 300                 <p>subscribe to a mailing list</p>
 301         </div>
 302
 303         </div>
 304
 305 </body>
 306 </html>