--- /dev/null
+.\" Auto generated Nroff by NroffEdit on April 12, 2010\r
+.pl 10.0i\r
+.po 0\r
+.ll 7.2i\r
+.lt 7.2i\r
+.nr LL 7.2i\r
+.nr LT 7.2i\r
+.ds LF Grishchenko and Bakker\r
+.ds RF FORMFEED[Page %]\r
+.ds LH Internet-Draft\r
+.ds RH December 19, 2011\r
+.ds CH swift\r
+.ds CF Expires June 21, 2012\r
+.hy 0\r
+.nh\r
+.ad l\r
+.in 0\r
+.nf\r
+.tl 'PPSP' 'A. Bakker'\r
+.tl 'Internet-Draft' 'TU Delft'\r
+.tl 'Intended status: Informational' \r
+.tl 'Expires: June 21, 2012' 'December 19, 2011'\r
+\r
+.fi\r
+.in 3\r
+.in 12\r
+.ti 8\r
+Peer-to-Peer Streaming Protocol (PPSP) \%<draft-ietf-ppsp-peer-protocol-00.txt>\r
+\r
+.ti 0\r
+Abstract\r
+\r
+.in 3\r
+The Generic Multiparty Protocol (swift) is a peer-to-peer based transport\r
+protocol for content dissemination. It can be used for streaming on-demand\r
+and live video content, as well as conventional downloading. In swift, the\r
+clients consuming the content participate in the dissemination by forwarding\r
+the content to other clients via a mesh-like structure. It is a generic\r
+protocol which can run directly on top of UDP, TCP, HTTP or as a RTP \r
+profile. Features of swift are short time-till-playback and extensibility. \r
+Hence, it can use different mechanisms to prevent freeriding, and work \r
+with different peer discovery schemes (centralized trackers or\r
+Distributed Hash Tables). Depending on the underlying transport\r
+protocol, swift can also use different congestion control algorithms, \r
+such as LEDBAT, and offer transparent NAT traversal. Finally, swift maintains \r
+only a small amount of state per peer and detects malicious modification of \r
+content. This documents describes swift and how it satisfies the requirements \r
+for the IETF Peer-to-Peer Streaming Protocol (PPSP) Working Group's peer \r
+protocol.\r
+\r
+\r
+.ti 0\r
+Status of this memo\r
+\r
+This Internet-Draft is submitted to IETF in full conformance with the\r
+provisions of BCP 78 and BCP 79.\r
+\r
+Internet-Drafts are working documents of the Internet Engineering Task Force\r
+(IETF), its areas, and its working groups. Note that other groups may also\r
+distribute working documents as Internet- Drafts.\r
+\r
+Internet-Drafts are draft documents valid for a maximum of six months and\r
+may be updated, replaced, or obsoleted by other documents at any time. It\r
+is inappropriate to use Internet-Drafts as reference material or to cite\r
+them other than as "work in progress."\r
+\r
+The list of current Internet-Drafts can be accessed at\r
+\%http://www.ietf.org/ietf/1id-abstracts.txt.\r
+\r
+The list of Internet-Draft Shadow Directories can be accessed at\r
+http://www.ietf.org/shadow.html.\r
+\r
+\r
+.nf\r
+Copyright (c) 2011 IETF Trust and the persons identified as the\r
+document authors. All rights reserved.\r
+\r
+This document is subject to BCP 78 and the IETF Trust's Legal\r
+Provisions Relating to IETF Documents\r
+\%(http://trustee.ietf.org/license-info) in effect on the date of\r
+publication of this document. Please review these documents\r
+carefully, as they describe your rights and restrictions with respect\r
+to this document. Code Components extracted from this document must\r
+include Simplified BSD License text as described in Section 4.e of\r
+the Trust Legal Provisions and are provided without warranty as\r
+described in the Simplified BSD License.\r
+\r
+.\" \# TD4 -- Set TOC depth by altering this value (TD5 = depth 5)\r
+.\" \# TOC -- Beginning of auto updated Table of Contents\r
+.in 0\r
+Table of Contents\r
+\r
+.nf\r
+ 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3\r
+ 1.1. Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . 3\r
+ 1.2. Conventions Used in This Document . . . . . . . . . . . . . 4\r
+ 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5\r
+ 2. Overall Operation . . . . . . . . . . . . . . . . . . . . . . . 6\r
+ 2.1. Joining a Swarm . . . . . . . . . . . . . . . . . . . . . . 6\r
+ 2.2. Exchanging Chunks . . . . . . . . . . . . . . . . . . . . . 6\r
+ 2.3. Leaving a Swarm . . . . . . . . . . . . . . . . . . . . . . 7\r
+ 3. Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . 7\r
+ 3.1. HANDSHAKE . . . . . . . . . . . . . . . . . . . . . . . . . 8\r
+ 3.3. HAVE . . . . . . . . . . . . . . . . . . . . . . . . . . . 8\r
+ 3.3.1. Bin Numbers . . . . . . . . . . . . . . . . . . . . . . 8\r
+ 3.3.2. HAVE Message . . . . . . . . . . . . . . . . . . . . . 9\r
+ 3.4. ACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9\r
+ 3.5. DATA and HASH . . . . . . . . . . . . . . . . . . . . . . . 10\r
+ 3.5.1. Merkle Hash Tree . . . . . . . . . . . . . . . . . . . 10\r
+ 3.5.2. Content Integrity Verification . . . . . . . . . . . . 11\r
+ 3.5.3. The Atomic Datagram Principle . . . . . . . . . . . . . 11\r
+ 3.5.4. DATA and HASH Messages . . . . . . . . . . . . . . . . 12\r
+ 3.6. HINT . . . . . . . . . . . . . . . . . . . . . . . . . . . 13\r
+ 3.7. Peer Address Exchange and NAT Hole Punching . . . . . . . . 13\r
+ 3.8. KEEPALIVE . . . . . . . . . . . . . . . . . . . . . . . . . 14\r
+ 3.9. VERSION . . . . . . . . . . . . . . . . . . . . . . . . . . 14\r
+ 3.10. Conveying Peer Capabilities . . . . . . . . . . . . . . . 14\r
+ 3.11. Directory Lists . . . . . . . . . . . . . . . . . . . . . 14\r
+ 4. Automatic Detection of Content Size . . . . . . . . . . . . . . 14\r
+ 4.1. Peak Hashes . . . . . . . . . . . . . . . . . . . . . . . . 15\r
+ 4.2. Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 16\r
+ 5. Live streaming . . . . . . . . . . . . . . . . . . . . . . . . 17\r
+ 6. Transport Protocols and Encapsulation . . . . . . . . . . . . . 17\r
+ 6.1. UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17\r
+ 6.1.1. Chunk Size . . . . . . . . . . . . . . . . . . . . . . 17\r
+ 6.1.2. Datagrams and Messages . . . . . . . . . . . . . . . . 18\r
+ 6.1.3. Channels . . . . . . . . . . . . . . . . . . . . . . . 18\r
+ 6.1.4. HANDSHAKE and VERSION . . . . . . . . . . . . . . . . . 19\r
+ 6.1.5. HAVE . . . . . . . . . . . . . . . . . . . . . . . . . 20\r
+ 6.1.6. ACK . . . . . . . . . . . . . . . . . . . . . . . . . . 20\r
+ 6.1.7. HASH . . . . . . . . . . . . . . . . . . . . . . . . . 20\r
+ 6.1.8. DATA . . . . . . . . . . . . . . . . . . . . . . . . . 20\r
+ 6.1.9. KEEPALIVE . . . . . . . . . . . . . . . . . . . . . . . 20\r
+ 6.1.10. Flow and Congestion Control . . . . . . . . . . . . . 21\r
+ 6.2. TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21\r
+ 6.3. RTP Profile for PPSP . . . . . . . . . . . . . . . . . . . 21\r
+ 6.3.1. Design . . . . . . . . . . . . . . . . . . . . . . . . 22\r
+ 6.3.2. PPSP Requirements . . . . . . . . . . . . . . . . . . . 24\r
+ 6.4. HTTP (as PPSP) . . . . . . . . . . . . . . . . . . . . . . 27\r
+ 6.4.1. Design . . . . . . . . . . . . . . . . . . . . . . . . 27\r
+ 6.4.2. PPSP Requirements . . . . . . . . . . . . . . . . . . . 29\r
+ 7. Security Considerations . . . . . . . . . . . . . . . . . . . . 32\r
+ 8. Extensibility . . . . . . . . . . . . . . . . . . . . . . . . . 32\r
+ 8.1. 32 bit vs 64 bit . . . . . . . . . . . . . . . . . . . . . 32\r
+ 8.2. IPv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . 32\r
+ 8.3. Congestion Control Algorithms . . . . . . . . . . . . . . . 32\r
+ 8.4. Piece Picking Algorithms . . . . . . . . . . . . . . . . . 33\r
+ 8.5. Reciprocity Algorithms . . . . . . . . . . . . . . . . . . 33\r
+ 8.6. Different crypto/hashing schemes . . . . . . . . . . . . . 33\r
+ 9. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . . 33\r
+ 9.1. Design Goals . . . . . . . . . . . . . . . . . . . . . . . 34\r
+ 9.2. Not TCP . . . . . . . . . . . . . . . . . . . . . . . . . 35\r
+ 9.3. Generic Acknowledgments . . . . . . . . . . . . . . . . . 36\r
+ Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . 37\r
+ References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37\r
+ Authors' addresses . . . . . . . . . . . . . . . . . . . . . . . . 39\r
+.fi\r
+.in 3\r
+\r
+.\" \# ETC -- End of auto updated Table of Contents\r
+\r
+\r
+\r
+.ti 0\r
+1. Introduction\r
+\r
+.ti 0\r
+1.1. Purpose\r
+\r
+This document describes the Generic Multiparty Protocol (swift), designed\r
+from the ground up for the task of disseminating the same content to a group\r
+of interested parties. Swift supports streaming on-demand and\r
+live video content, as well as conventional downloading, thus covering\r
+today's three major use cases for content distribution. To fulfil this task,\r
+clients consuming the content are put on equal footing with the servers\r
+initially providing the content to create a peer-to-peer system where\r
+everyone can provide data. Each peer connects to a random set of other peers\r
+resulting in a mesh-like structure. \r
+\r
+Swift uses a simple method of naming content based on self-certification. In\r
+particular, content in swift is identified by a single cryptographic hash\r
+that is the root hash in a Merkle hash tree calculated recursively from the\r
+content [ABMRKL]. This self-certifying hash tree allows every peer to\r
+directly detect when a malicious peer tries to distribute fake content. It\r
+also ensures only a small amount of information is needed to start a\r
+download (just the root hash and some peer addresses).\r
+\r
+Swift uses a novel method of addressing chunks of content called "bin\r
+numbers". Bin numbers allow the addressing of a binary interval of data\r
+using a single integer. This reduces the amount of state that needs to be\r
+recorded per peer and the space needed to denote intervals on the wire,\r
+making the protocol light-weight. In general, this numbering system allows \r
+swift to work with simpler data structures, e.g. to use arrays instead of \r
+binary trees, thus reducing complexity.\r
+\r
+Swift is a generic protocol which can run directly on top of UDP, TCP, HTTP, \r
+or as a layer below RTP, similar to SRTP [RFC3711]. As such, swift defines a \r
+common set of messages that make up the protocol, which can have different\r
+representations on the wire depending on the lower-level protocol used. When\r
+the lower-level transport is UDP, swift can also use different congestion \r
+control algorithms and facilitate NAT traversal. \r
+\r
+In addition, swift is extensible in the mechanisms it uses to promote client\r
+contribution and prevent freeriding, that is, how to deal with peers \r
+that only download content but never upload to others. Furthermore, \r
+it can work with different peer discovery schemes, \r
+such as centralized trackers or fast Distributed Hash Tables [JIM11]. \r
+\r
+This documents describes not only the swift protocol but also how it\r
+satisfies the requirements for the IETF Peer-to-Peer Streaming Protocol\r
+(PPSP) Working Group's peer protocol [PPSPCHART,I-D.ietf-ppsp-reqs].\r
+A reference implementation of swift over UDP is available [SWIFTIMPL].\r
+\r
+\r
+.ti 0\r
+1.2. Conventions Used in This Document\r
+\r
+The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",\r
+"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in\r
+this document are to be interpreted as described in [RFC2119].\r
+\r
+.ti 0\r
+1.3. Terminology\r
+\r
+.in 3\r
+message\r
+.br\r
+.in 8\r
+The basic unit of swift communication. A message will have different \r
+representations on the wire depending on the transport protocol used. Messages \r
+are typically multiplexed into a datagram for transmission.\r
+\r
+.in 3\r
+datagram\r
+.br\r
+.in 8\r
+A sequence of messages that is offered as a unit to the underlying transport \r
+protocol (UDP, etc.). The datagram is swift's Protocol Data Unit (PDU).\r
+\r
+.in 3\r
+content\r
+.br\r
+.in 8\r
+Either a live transmission, a pre-recorded multimedia asset, or a file.\r
+\r
+.in 3\r
+bin\r
+.br\r
+.in 8\r
+A number denoting a specific binary interval of the content (i.e., one \r
+or more consecutive chunks).\r
+\r
+.in 3\r
+chunk\r
+.br\r
+.in 8\r
+The basic unit in which the content is divided. E.g. a block of N \r
+kilobyte.\r
+\r
+.in 3\r
+hash\r
+.br\r
+.in 8\r
+The result of applying a cryptographic hash function, more specifically \r
+a modification detection code (MDC) [HAC01], such as SHA1 [FIPS180-2], \r
+to a piece of data. \r
+\r
+.in 3\r
+root hash\r
+.br\r
+.in 8\r
+The root in a Merkle hash tree calculated recursively from the content.\r
+\r
+.in 3\r
+swarm\r
+.br\r
+.in 8\r
+A group of peers participating in the distribution of the same content.\r
+\r
+.in 3\r
+swarm ID\r
+.br\r
+.in 8\r
+Unique identifier for a swarm of peers, in swift the root hash of the \r
+content (video-on-demand,download) or a public key (live streaming).\r
+\r
+.in 3\r
+tracker\r
+.br\r
+.in 8\r
+An entity that records the addresses of peers participating in a swarm,\r
+usually for a set of swarms, and makes this membership information \r
+available to other peers on request.\r
+\r
+.in 3\r
+choking\r
+.br\r
+.in 8\r
+When a peer A is choking peer B it means that A is currently not \r
+willing to accept requests for content from B.\r
+.in 3\r
+\r
+\r
+.ti 0\r
+2. Overall Operation\r
+\r
+The basic unit of communication in swift is the message. Multiple messages are\r
+multiplexed into a single datagram for transmission. A datagram (and hence the \r
+messages it contains) will have different representations on the wire depending \r
+on the transport protocol used (see Sec. 6).\r
+\r
+\r
+.ti 0\r
+2.1. Joining a Swarm\r
+\r
+Consider a peer A that wants to download a certain content asset.\r
+To commence a swift download, peer A must have the swarm ID of the content \r
+and a list of one or more tracker contact points (e.g. host+port). The list \r
+of trackers is optional in the presence of a decentralized tracking mechanism. \r
+The swarm ID consists of the swift root hash of the content (video-on-demand,\r
+downloading) or a public key (live streaming).\r
+\r
+Peer A now registers with the tracker following e.g. the PPSP tracker\r
+protocol [I-D.ietf.ppsp-reqs] and receives the IP address and port of peers\r
+already in the swarm, say B, C, and D. Peer A now sends a datagram\r
+containing a HANDSHAKE message to B, C, and D. This message serves as an\r
+end-to-end check that the peers are actually in the correct swarm, and\r
+contains the root hash of the swarm. Peer B and C respond with datagrams\r
+containing a HANDSHAKE message and one or more HAVE messages. A HAVE message\r
+conveys (part of) the chunk availability of a peer and thus contains a bin\r
+number that denotes what chunks of the content peer B, resp. C have. Peer D\r
+sends a datagram with just a HANDSHAKE and omits HAVE messages as a way of \r
+choking A.\r
+\r
+.ti 0\r
+2.2. Exchanging Chunks\r
+\r
+In response to B and C, A sends new datagrams to B and C containing HINT messages.\r
+A HINT or request message indicates the chunks that a peer wants to\r
+download, and contains a bin number. The HINT messages to B and C refer to\r
+disjunct sets of chunks. B and C respond with datagrams containing HASH,\r
+HAVE and DATA messages. The HASH messages contains all cryptographic hashes\r
+that peer A needs to verify the integrity of the content chunk sent in the\r
+DATA message, using the content's root hash as trusted anchor, see Sec. 3.5.\r
+Using these hashes peer A verifies that the chunks received from B and C are \r
+correct. It also updates the chunk availability of B and C using the information\r
+in the received HAVE messages. \r
+\r
+After processing, A sends a datagram containing HAVE messages for the chunks\r
+it just received to all its peers. In the datagram to B and C it includes an\r
+ACK message acknowledging the receipt of the chunks, and adds HINT messages\r
+for new chunks. ACK messages are not used when a reliable transport protocol\r
+is used. When e.g. C finds that A obtained a chunk (from B) that C did not\r
+yet have, C's next datagram includes a HINT for that chunk.\r
+\r
+Peer D does not send HAVE messages to A when it downloads chunks from other peers,\r
+until D decides to unchoke peer A. In the case, it sends a datagram with\r
+HAVE messages to inform A of its current availability. If B or C decide to\r
+choke A they stop sending HAVE and DATA messages and A should then rerequest\r
+from other peers. They may continue to send HINT messages, or periodic\r
+KEEPALIVE messages such that A keeps sending them HAVE messages.\r
+\r
+Once peer A has received all content (video-on-demand use case) it stops\r
+sending messages to all other peers that have all content (a.k.a. seeders).\r
+Peer A MAY also contact the tracker or another source again to obtain more \r
+peer addresses.\r
+\r
+\r
+.ti 0\r
+2.3. Leaving a Swarm\r
+\r
+Depending on the transport protocol used, peers should either use explicit \r
+leave messages or implicitly leave a swarm by stopping to respond\r
+to messages. Peers that learn about the departure should remove these peers \r
+from the current peer list. The implicit-leave mechanism works for both graceful and \r
+ungraceful leaves (i.e., peer crashes or disconnects). When leaving gracefully, a \r
+peer should deregister from the tracker following the (PPSP) tracker protocol.\r
+\r
+\r
+.ti 0\r
+3. Messages\r
+\r
+.fi\r
+In general, no error codes or responses are used in the protocol; absence \r
+of any response indicates an error. Invalid messages are discarded. \r
+\r
+For the sake of simplicity, one swarm of peers always deals with one content \r
+asset (e.g. file) only. Retrieval of large collections of files is done by \r
+retrieving a directory list file and then recursively retrieving files, which \r
+might also turn to be directory lists, as described in Sec. 3.11. \r
+\r
+.ti 0\r
+3.1. HANDSHAKE\r
+\r
+As an end-to-end check that the peers are actually in the correct swarm, the\r
+initiating peer and the addressed peer SHOULD send a HANDSHAKE message in\r
+the first datagrams they exchange. The only payload of the HANDSHAKE message\r
+is the root hash of the content. \r
+\r
+After the handshakes are exchanged, the initiator knows that the peer really\r
+responds. Hence, the second datagram the initiator sends MAY already contain\r
+some heavy payload. To minimize the number of initialization roundtrips, \r
+implementations MAY dispense with the HANDSHAKE message. To the same end,\r
+the first two datagrams exchanged MAY also contain some minor payload, e.g.\r
+HAVE messages to indicate the current progress of a peer or a HINT \r
+(see Sec. 3.6).\r
+\r
+\r
+.ti 0\r
+3.3. HAVE\r
+\r
+The HAVE message is used to convey which chunks a peers has available,\r
+expressed in a new content addressing scheme called "bin numbers".\r
+\r
+.ti 0\r
+3.3.1. Bin Numbers\r
+\r
+Swift employs a generic content addressing scheme based on binary intervals \r
+("bins" in short). The smallest interval is a chunk (e.g. a N kilobyte \r
+block), the top interval is the complete 2**63 range. A novel addition \r
+to the classical scheme are "bin numbers", a scheme of numbering binary \r
+intervals which lays them out into a vector nicely. Consider an chunk\r
+interval of width W. To derive the bin numbers of the complete interval and\r
+the subintervals, a minimal balanced binary tree is built that is at least W \r
+chunks wide at the base. The leaves from left-to-right correspond to \r
+the chunks 0..W in the interval, and have bin number I*2 where I is the \r
+index of the chunk (counting beyond W-1 to balance the tree). The higher \r
+level nodes P in the tree have bin number\r
+\r
+ binP = (binL + binR) / 2\r
+\r
+.br \r
+where binL is the bin of node P's left-hand child and binR is the bin of node\r
+P's right-hand child. Given that each node in the tree represents a\r
+subinterval of the original interval, each such subinterval now is\r
+addressable by a bin number, a single integer. The bin number tree of a\r
+interval of width W=8 looks like this:\r
+\r
+\r
+\r
+\r
+ 7\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ 3 11\r
+.br\r
+ / \\ / \\\r
+.br\r
+ / \\ / \\\r
+.br\r
+ / \\ / \\\r
+.br\r
+ 1 5 9 13 \r
+.br\r
+ / \\ / \\ / \\ / \\\r
+.br\r
+ 0 2 4 6 8 10 12 14\r
+.br \r
+\r
+.fi\r
+So bin 7 represents the complete interval, 3 represents the interval of\r
+chunk 0..3 and 1 represents the interval of chunks 0 and 1. The special\r
+numbers 0xFFFFFFFF (32-bit) or 0xFFFFFFFFFFFFFFFF (64-bit) stands for an\r
+empty interval, and 0x7FFF...FFF stands for "everything". \r
+\r
+\r
+.ti 0\r
+3.3.2. HAVE Message\r
+\r
+When a receiving peer has successfully checked the integrity of a chunk or\r
+interval of chunks it MUST send a HAVE message to all peers it wants to \r
+interact with. The latter allows the HAVE message to be used as a method of \r
+choking. The HAVE message MUST contain the bin number of the biggest\r
+complete interval of all chunks the receiver has received and checked so far\r
+that fully includes the interval of chunks just received. So the bin number\r
+MUST denote at least the interval received, but the receiver is supposed to \r
+aggregate and acknowledge bigger bins, when possible.\r
+\r
+As a result, every single chunk is acknowledged a logarithmic number of times.\r
+That provides some necessary redundancy of acknowledgments and sufficiently \r
+compensates for unreliable transport protocols.\r
+\r
+To record which chunks a peer has in the state that an implementation keeps\r
+for each peer, an implementation MAY use the "binmap" data structure, which\r
+is a hybrid of a bitmap and a binary tree, discussed in detail in [BINMAP].\r
+\r
+\r
+.ti 0\r
+3.4. ACK\r
+\r
+When swift is run over an unreliable transport protocol, an implementation MAY\r
+choose to use ACK messages to acknowledge received data. When a receiving \r
+peer has successfully checked the integrity of a chunk or interval of chunks\r
+C it MUST send a ACK message containing the bin number of its biggest, complete,\r
+interval covering C to the sending peer (see HAVE). To facilitate delay-based\r
+congestion control, an ACK message contains a timestamp.\r
+\r
+\r
+.ti 0\r
+3.5. DATA and HASH\r
+\r
+The DATA message is used to transfer chunks of content. The associated HASH message \r
+carries cryptographic hashes that are necessary for a receiver to check the\r
+the integrity of the chunk. Swift's content integrity protection is based on a \r
+Merkle hash tree and works as follows.\r
+\r
+.ti 0\r
+3.5.1. Merkle Hash Tree\r
+\r
+Swift uses a method of naming content based on self-certification. In particular, \r
+content in swift is identified by a single cryptographic hash that is the \r
+root hash in a Merkle hash tree calculated recursively from the content [ABMRKL]. \r
+This self-certifying hash tree allows every peer to directly detect when a malicious \r
+peer tries to distribute fake content. It also ensures only a small the amount \r
+of information is needed to start a download (the root hash and some peer \r
+addresses). For live streaming public keys and dynamic trees are used, see below.\r
+\r
+The Merkle hash tree of a content asset that is divided into N chunks\r
+is constructed as follows. Note the construction does not assume chunks\r
+of content to be fixed size. Given a cryptographic hash function, more specifically \r
+a modification detection code (MDC) [HAC01], such as SHA1, the hashes of all the \r
+chunks of the content are calculated. Next, a binary tree of sufficient height \r
+is created. Sufficient \r
+height means that the lowest level in the tree has enough nodes to hold all \r
+chunk hashes in the set, as before, see HAVE message. The figure below shows \r
+the tree for a content asset consisting of 7 chunks. As before with the\r
+content addressing scheme, the leaves of the tree correspond to a chunk and \r
+in this case are assigned the hash of that chunk, starting at the left-most leaf. \r
+As the base of the tree may be wider than the number of chunks, any remaining \r
+leaves in the tree are assigned a empty hash value of all zeros. Finally, the hash \r
+values of the higher levels in the tree are calculated, by concatenating the hash \r
+values of the two children (again left to right) and computing the hash of that \r
+aggregate. This process ends in a hash value for the root node, which is called\r
+the "root hash". Note the root hash only depends on the content and any modification\r
+of the content will result in a different root hash. \r
+\r
+\r
+\r
+\r
+ 7 = root hash\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ 3* 11\r
+.br\r
+ / \\ / \\\r
+.br\r
+ / \\ / \\\r
+.br\r
+ / \\ / \\\r
+.br\r
+ 1 5 9 13* = uncle hash\r
+.br\r
+ / \\ / \\ / \\ / \\\r
+.br\r
+ 0 2 4 6 8 10* 12 14\r
+.br\r
+ \r
+ C0 C1 C2 C3 C4 C5 C6 E\r
+.br\r
+ =chunk index ^^ = empty hash\r
+.br\r
+ \r
+\r
+.ti 0\r
+3.5.2. Content Integrity Verification\r
+\r
+.fi\r
+Assuming a peer receives the root hash of the content it wants to download\r
+from a trusted source, it can can check the integrity of any chunk of that \r
+content it receives as follows. It first calculates the hash of the chunk \r
+it received, for example chunk C4 in the previous figure. Along with this \r
+chunk it MUST receive the hashes required to check the integrity of that \r
+chunk. In principle, these are the hash of the chunk's sibling (C5) and \r
+that of its "uncles". A chunk's uncles are the sibling Y of its parent X, \r
+and the uncle of that Y, recursively until the root is reached. For chunk C4 \r
+its uncles are bins 13 and 3, marked with * in the figure. Using this information \r
+the peer recalculates the root hash of the tree, and compares it to the \r
+root hash it received from the trusted source. If they match the chunk of \r
+content has been positively verified to be the requested part of the content. \r
+Otherwise, the sending peer either sent the wrong content or the wrong \r
+sibling or uncle hashes. For simplicity, the set of sibling and uncles \r
+hashes is collectively referred to as the "uncle hashes". \r
+\r
+In the case of live streaming the tree of chunks grows dynamically and\r
+content is identified with a public key instead of a root hash, as the root \r
+hash is undefined or, more precisely, transient, as long as new data is \r
+generated by the live source. Live streaming is described in more detail\r
+below, but content verification works the same for both live and predefined\r
+content.\r
+\r
+.ti 0\r
+3.5.3. The Atomic Datagram Principle\r
+\r
+As explained above, a datagram consists of a sequence of messages. Ideally,\r
+every datagram sent must be independent of other datagrams, so each \r
+datagram SHOULD be processed separately and a loss of one datagram MUST NOT\r
+disrupt the flow. Thus, as a datagram carries zero or more messages,\r
+neither messages nor message interdependencies should span over multiple\r
+datagrams. \r
+\r
+This principle implies that as any chunk is verified using its uncle \r
+hashes the necessary hashes MUST be put into the same datagram as the \r
+chunk's data (Sec. 3.5.4). As a general rule, if some additional data is \r
+still missing to process a message within a datagram, the message SHOULD be \r
+dropped. \r
+\r
+The hashes necessary to verify a chunk are in principle its sibling's hash\r
+and all its uncle hashes, but the set of hashes to sent can be optimized. \r
+Before sending a packet of data to the receiver, the sender inspects the \r
+receiver's previous acknowledgments (HAVE or ACK) to derive which hashes the\r
+receiver already has for sure. Suppose, the receiver had acknowledged bin 1\r
+(first two chunks of the file), then it must already have uncle hashes 5,\r
+11 and so on. That is because those hashes are necessary to check packets of\r
+bin 1 against the root hash. Then, hashes 3, 7 and so on must be also known\r
+as they are calculated in the process of checking the uncle hash chain.\r
+Hence, to send bin 12 (i.e. the 7th chunk of content), the sender needs to\r
+include just the hashes for bins 14 and 9, which let the data be checked \r
+against hash 11 which is already known to the receiver. \r
+\r
+The sender MAY optimistically skip hashes which were sent out in previous,\r
+still unacknowledged datagrams. It is an optimization tradeoff between\r
+redundant hash transmission and possibility of collateral data loss in the\r
+case some necessary hashes were lost in the network so some delivered data\r
+cannot be verified and thus has to be dropped. In either case, the receiver\r
+builds the Merkle tree on-demand, incrementally, starting from the root\r
+hash, and uses it for data validation.\r
+\r
+In short, the sender MUST put into the datagram the missing hashes necessary \r
+for the receiver to verify the chunk.\r
+\r
+.ti 0\r
+3.5.4. DATA and HASH Messages\r
+\r
+Concretely, a peer that wants to send a chunk of content creates a datagram \r
+that MUST consist of one or more HASH messages and a DATA message. The datagram \r
+MUST contain a HASH message for each hash the receiver misses for integrity \r
+checking. A HASH message MUST contain the bin number and hash data for each \r
+of those hashes. The DATA message MUST contain the bin number of the chunk \r
+and chunk itself. A peer MAY send the required messages for multiple chunks \r
+in the same datagram. \r
+\r
+\r
+.ti 0\r
+3.6. HINT\r
+\r
+While bulk download protocols normally do explicit requests for certain ranges \r
+of data (i.e., use a pull model, for example, BitTorrent [BITTORRENT]), live \r
+streaming protocols quite often use a request-less push model to save round \r
+trips. Swift supports both models of operation. \r
+\r
+A peer MUST send a HINT message containing the bin of the chunk interval it \r
+wants to download. A peer receiving a HINT message MAY send out requested \r
+pieces. When it receives multiple HINTs (either in one datagram or in multiple), \r
+the peer SHOULD process the HINTs sequentially. When live streaming, \r
+it also may send some other chunks in case it runs out of requests or\r
+for some other reason. In that case the only purpose of HINT messages is \r
+to coordinate peers and to avoid unnecessary data retransmission, hence \r
+the name. \r
+\r
+\r
+\r
+.ti 0\r
+3.7. Peer Address Exchange and NAT Hole Punching\r
+\r
+Peer address exchange messages (or PEX messages for short) are common for \r
+many peer-to-peer protocols. By exchanging peer addresses in gossip fashion, \r
+peers relieve central coordinating entities (the trackers) from unnecessary \r
+work. swift optionally features two types of PEX messages: PEX_REQ and PEX_ADD.\r
+A peer that wants to retrieve some peer addresses MUST send a PEX_REQ message.\r
+The receiving peer MAY respond with a PEX_ADD message containing the addresses\r
+of several peers. The addresses MUST be of peers it has recently exchanged\r
+messages with to guarantee liveliness. \r
+\r
+.fi\r
+To unify peer exchange and NAT hole punching functionality, the\r
+sending pattern of PEX messages is restricted. As the swift handshake\r
+is able to do simple NAT hole punching [SNP] transparently, PEX\r
+messages must be emitted in the way to facilitate that. Namely,\r
+once peer A introduces peer B to peer C by sending a PEX_ADD message to\r
+C, it SHOULD also send a message to B introducing C. The messages\r
+SHOULD be within 2 seconds from each other, but MAY not be,\r
+simultaneous, instead leaving a gap of twice the "typical" RTT, i.e.\r
+\%300-600ms. The peers are supposed to initiate handshakes to each\r
+other thus forming a simple NAT hole punching pattern where the\r
+introducing peer effectively acts as a STUN server [RFC5389]. Still, peers\r
+MAY ignore PEX messages if uninterested in obtaining new peers or\r
+because of security considerations (rate limiting) or any other\r
+reason.\r
+\r
+The PEX messages can be used to construct a dedicated tracker peer.\r
+\r
+\r
+.ti 0\r
+3.8. KEEPALIVE\r
+\r
+A peer MUST send a datagram containing a KEEPALIVE message periodically\r
+to each peer it wants to interact with in the future but has no\r
+other messages to send them at present.\r
+\r
+\r
+.ti 0\r
+3.9. VERSION\r
+.fi\r
+Peers MUST convey which version of the swift protocol they support using a \r
+VERSION message. This message MUST be included in the initial (handshake) \r
+datagrams and MUST indicate which version of the swift protocol the sending \r
+peer supports. \r
+\r
+\r
+.ti 0\r
+3.10. Conveying Peer Capabilities\r
+.fi\r
+Peers may support just a subset of the swift messages. For example, peers \r
+running over TCP may not accept ACK messages, or peers used with a centralized \r
+tracking infrastructure may not accept PEX messages. For these reasons, peers \r
+SHOULD signal which subset of the swift messages they support by means of \r
+the MSGTYPE_RCVD message. This message SHOULD be included in the initial \r
+(handshake) datagrams and MUST indicate which swift protocol messages \r
+the sending peer supports. \r
+\r
+\r
+.ti 0\r
+3.11. Directory Lists\r
+\r
+Directory list files MUST start with magic bytes ".\\n..\\n". The rest of\r
+the file is a newline-separated list of hashes and file names for the\r
+content of the directory. An example:\r
+\r
+.nf\r
+\&.\r
+\&..\r
+1234567890ABCDEF1234567890ABCDEF12345678 readme.txt\r
+01234567890ABCDEF1234567890ABCDEF1234567 big_file.dat\r
+\r
+\r
+\r
+.ti 0\r
+4. Automatic Detection of Content Size\r
+\r
+.fi\r
+In swift, the root hash of a static content asset, such as a video file,\r
+along with some peer addresses is sufficient to start a download.\r
+In addition, swift can reliably and automatically derive the size\r
+of such content from information received from the network when fixed\r
+sized chunks are used. As a result, it is not necessary to include \r
+the size of the content asset as the metadata of the content,\r
+in addition to the root hash. Implementations of swift MAY use \r
+this automatic detection feature. \r
+\r
+.ti 0\r
+4.1. Peak Hashes\r
+\r
+The ability for a newcomer peer to detect the size of the content \r
+depends heavily on the concept of peak hashes. Peak hashes,\r
+in general, enable two cornerstone features of swift: reliable file \r
+size detection and download/live streaming unification (see Sec. 5). \r
+The concept of peak hashes depends on the concepts of filled and\r
+incomplete bins. Recall that when constructing the binary trees\r
+for content verification and addressing the base of the tree may\r
+have more leaves than the number of chunks in the content. In the\r
+Merkle hash tree these leaves were assigned empty all-zero \r
+hashes to be able to calculate the higher level hashes. A filled\r
+bin is now defined as a bin number that addresses an interval\r
+of leaves that consists only of hashes of content chunks, not\r
+empty hashes. Reversely, an incomplete (not filled) bin \r
+addresses an interval that contains also empty hashes,\r
+typically an interval that extends past the end of the file.\r
+In the following figure bins 7, 11, 13 and 14 are incomplete\r
+the rest is filled.\r
+\r
+Formally, a peak hash is a hash in the Merkle tree defined \r
+over a filled bin, whose sibling is defined over an incomplete bin. \r
+Practically, suppose a file is 7162 bytes long and a chunk \r
+is 1 kilobyte. That file fits into 7 chunks, the tail chunk being \r
+1018 bytes long. The Merkle tree for that file looks as follows. \r
+Following the definition the peak hashes of this file are in \r
+bins 3, 9 and 12, denoted with a *. E denotes an empty \r
+hash.\r
+\r
+ 7\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ / \\\r
+.br\r
+ 3* 11\r
+.br\r
+ / \\ / \\\r
+.br\r
+ / \\ / \\\r
+.br\r
+ / \\ / \\\r
+.br\r
+ 1 5 9* 13 \r
+.br\r
+ / \\ / \\ / \\ / \\\r
+.br\r
+ 0 2 4 6 8 10 12* 14\r
+.br\r
+\r
+ C0 C1 C2 C3 C4 C5 C6 E\r
+.br\r
+ = 1018 bytes\r
+.br\r
+\r
+Peak hashes can be explained by the binary representation of the \r
+number of chunks the file occupies. The binary representation for \r
+7 is 111. Every "1" in binary representation of the file's packet \r
+length corresponds to a peak hash. For this particular file there\r
+are indeed three peaks, bin numbers 3, 9, 12. The number of peak\r
+hashes for a file is therefore also at most logarithmic with its \r
+size.\r
+\r
+.fi\r
+A peer knowing which bins contain the peak hashes for the file \r
+can therefore calculate the number of chunks it consists of, and \r
+thus get an estimate of the file size (given all chunks but the last \r
+are fixed size). Which bins are the peaks can be securely communicated \r
+from one (untrusted) peer A to another B by letting A send the \r
+peak hashes and their bin numbers to B. It can be shown that \r
+the root hash that B obtained from a trusted source is sufficient \r
+to verify that these are indeed the right peak hashes, as follows. \r
+\r
+Lemma: Peak hashes can be checked against the root hash.\r
+\r
+Proof: (a) Any peak hash is always the left sibling. Otherwise, be\r
+it the right sibling, its left neighbor/sibling must also be\r
+defined over a filled bin, because of the way chunks are laid\r
+out in the leaves, contradiction. (b) For the rightmost \r
+peak hash, its right sibling is zero. (c) For any peak hash, \r
+its right sibling might be calculated using peak hashes to the \r
+left and zeros for empty bins. (d) Once the right sibling of \r
+the leftmost peak hash is calculated, its parent might be \r
+calculated. (e) Once that parent is calculated, we might \r
+trivially get to the root hash by concatenating the hash with \r
+zeros and hashing it repeatedly.\r
+\r
+.fi\r
+Informally, the Lemma might be expressed as follows: peak hashes cover all\r
+data, so the remaining hashes are either trivial (zeros) or might be\r
+calculated from peak hashes and zero hashes.\r
+\r
+Finally, once peer B has obtained the number of chunks in the content it\r
+can determine the exact file size as follows. Given that all chunks\r
+except the last are fixed size B just needs to know the size of the last\r
+chunk. Knowing the number of chunks B can calculate the bin number of the \r
+last chunk and download it. As always B verifies the integrity of this \r
+chunk against the trusted root hash. As there is only one chunk of data \r
+that leads to a successful verification the size of this chunk must \r
+be correct. B can then determine the exact file size as \r
+\r
+ (number of chunks -1) * fixed chunk size + size of last chunk\r
+\r
+\r
+.ti 0\r
+4.2. Procedure\r
+\r
+A swift implementation that wants to use automatic size detection MUST\r
+operate as follows. When a peer B sends a DATA message for the first time\r
+to a peer A, B MUST include all the peak hashes for the content in the\r
+same datagram, unless A has already signalled earlier in the exchange \r
+that it knows the peak hashes by having acknowledged any bin, even the empty \r
+one. The receiver A MUST check the peak hashes against the root hash\r
+to determine the approximate content size. To obtain the definite content size\r
+peer A MUST download the last chunk of the content from any peer that offers it.\r
+\r
+\r
+\r
+\r
+\r
+.ti 0\r
+5. Live streaming\r
+\r
+.fi\r
+In the case of live streaming a transfer is bootstrapped with a public key\r
+instead of a root hash, as the root hash is undefined or, more precisely,\r
+transient, as long as new data is being generated by the live source. \r
+Live/download unification is achieved by sending signed peak hashes on-demand, \r
+ahead of the actual data. As before, the sender might use acknowledgements \r
+to derive which content range the receiver has peak hashes for and to prepend \r
+the data hashes with the necessary (signed) peak hashes. \r
+Except for the fact that the set of peak hashes changes with time, \r
+other parts of the algorithm work as described in Sec. 3. \r
+\r
+As with static content assets in the previous section, in live streaming \r
+content length is not known on advance, but derived \%on-the-go from the peak \r
+hashes. Suppose, our 7 KB stream extended to another kilobyte. Thus, now hash 7 \r
+becomes the only peak hash, eating hashes 3, 9 and 12. So, the source sends \r
+out a SIGNED_HASH message to announce the fact.\r
+\r
+The number of cryptographic operations will be limited. For example,\r
+consider a 25 frame/second video transmitted over UDP. When each frame is \r
+transmitted in its own chunk, only 25 signature verification operations \r
+per second are required at the receiver for bitrates up to ~12.8 \r
+megabit/second. For higher bitrates multiple UDP packets per frame \r
+are needed and the number of verifications doubles.\r
+\r
+\r
+\r
+\r
+\r
+.ti 0\r
+6. Transport Protocols and Encapsulation\r
+\r
+.ti 0\r
+6.1. UDP\r
+\r
+.ti 0\r
+6.1.1. Chunk Size\r
+\r
+Currently, swift-over-UDP is the preferred deployment option. Effectively, UDP\r
+allows the use of IP with minimal overhead and it also allows userspace\r
+implementations. The default is to use chunks of 1 kilobyte such that a\r
+datagram fits in an Ethernet-sized IP packet. The bin numbering\r
+allows to use swift over Jumbo frames/datagrams. Both DATA and\r
+HAVE/ACK messages may use e.g. 8 kilobyte packets instead of the standard 1 \r
+KiB. The hashing scheme stays the same. Using swift with 512 or 256-byte \r
+packets is theoretically possible with 64-bit byte-precise bin numbers, but IP\r
+fragmentation might be a better method to achieve the same result.\r
+\r
+\r
+.ti 0\r
+6.1.2. Datagrams and Messages\r
+\r
+When using UDP, the abstract datagram described above corresponds directly\r
+to a UDP datagram. Each message within a datagram has a fixed length, which\r
+depends on the type of the message. The first byte of a message denotes its type.\r
+The currently defined types are:\r
+\r
+ HANDSHAKE = 0x00\r
+.br \r
+ DATA = 0x01\r
+.br\r
+ ACK = 0x02\r
+.br \r
+ HAVE = 0x03\r
+.br \r
+ HASH = 0x04\r
+.br \r
+ PEX_ADD = 0x05\r
+.br \r
+ PEX_REQ = 0x06\r
+.br \r
+ SIGNED_HASH = 0x07\r
+.br \r
+ HINT = 0x08\r
+.br \r
+ MSGTYPE_RCVD = 0x09\r
+.br \r
+ VERSION = 0x10\r
+.br \r
+\r
+\r
+Furthermore, integers are serialized in the network \%(big-endian) byte order. \r
+So consider the example of an ACK message (Sec 3.4). It has message type of 0x02\r
+and a payload of a bin number, a four-byte integer (say, 1); hence, its on the wire\r
+representation for UDP can be written in hex as: "02 00000001". This \%hex-like two \r
+character-per-byte notation is used to represent message formats in the rest of \r
+this section.\r
+\r
+.ti 0\r
+6.1.3. Channels \r
+\r
+As it is increasingly complex for peers to enable UDP communication\r
+between each other due to NATs and firewalls, swift-over-UDP uses\r
+a multiplexing scheme, called "channels", to allow multiple swarms to use the \r
+same UDP port. Channels loosely correspond to TCP connections and each channel\r
+belongs to a single swarm. When channels are used, each datagram starts with \r
+four bytes corresponding to the receiving channel number. \r
+\r
+ \r
+.ti 0\r
+6.1.4. HANDSHAKE and VERSION\r
+\r
+A channel is established with a handshake. To start a handshake, the initiating \r
+peer needs to know:\r
+\r
+.nf\r
+(1) the IP address of a peer\r
+(2) peer's UDP port and\r
+(3) the root hash of the content (see Sec. 3.5.1).\r
+.fi\r
+\r
+To do the handshake the initiating peer sends a datagram that MUST start \r
+with an all 0-zeros channel number followed by a VERSION message, then a \r
+HASH message whose payload is the root hash, and a HANDSHAKE message, whose \r
+only payload is a locally unused channel number. \r
+\r
+On the wire the datagram will look something like this:\r
+.nf\r
+ 00000000 10 01 \r
+ 04 7FFFFFFF 1234123412341234123412341234123412341234\r
+ 00 00000011\r
+.fi\r
+(to unknown channel, handshake from channel 0x11 speaking protocol version 0x01, \r
+initiating a transfer of a file with a root hash 123...1234)\r
+\r
+The receiving peer MUST respond with a datagram that starts with the\r
+channel number from the sender's HANDSHAKE message, followed by a \r
+VERSION message, then a HANDSHAKE message, whose only payload is a locally \r
+unused channel number, followed by any other messages it wants to send. \r
+\r
+Peer's response datagram on the wire:\r
+.nf\r
+ 00000011 10 01 \r
+ 00 00000022 03 00000003\r
+.fi\r
+(peer to the initiator: use channel number 0x22 for this transfer and \r
+proto version 0x01; I also have first 4 chunks of the file, see Sec. 4.3)\r
+\r
+.fi\r
+At this point, the initiator knows that the peer really responds; for that\r
+purpose channel ids MUST be random enough to prevent easy guessing. So, the\r
+third datagram of a handshake MAY already contain some heavy payload. To\r
+minimize the number of initialization roundtrips, the first two datagrams\r
+MAY also contain some minor payload, e.g. a couple of HAVE messages roughly\r
+indicating the current progress of a peer or a HINT (see Sec. 3.6).\r
+When receiving the third datagram, both peers have the proof they really talk \r
+to each other; three-way handshake is complete.\r
+\r
+A peer MAY explicit close a channel by sending a HANDSHAKE message that MUST\r
+contain an all 0-zeros channel number. \r
+\r
+On the wire:\r
+.nf \r
+ 00 00000000\r
+\r
+\r
+.ti 0\r
+6.1.5. HAVE\r
+\r
+A HAVE message (type 0x03) states that the sending peer has the \r
+complete specified bin and successfully checked its integrity:\r
+.nf\r
+ 03 00000003\r
+(got/checked first four kilobytes of a file/stream)\r
+\r
+\r
+\r
+.ti 0\r
+6.1.6. ACK\r
+\r
+An ACK message (type 0x02) acknowledges data that was received from\r
+its addressee; to facilitate delay-based congestion control, an\r
+ACK message contains a timestamp, in particular, a 64-bit microsecond\r
+time. \r
+.nf\r
+ 02 00000002 12345678\r
+(got the second kilobyte of the file from you; my microsecond\r
+timer was showing 0x12345678 at that moment)\r
+\r
+\r
+.ti 0\r
+6.1.7. HASH\r
+\r
+A HASH message (type 0x04) consists of a four-byte bin number and\r
+the cryptographic hash (e.g. a 20-byte SHA1 hash)\r
+.nf\r
+ 04 7FFFFFFF 1234123412341234123412341234123412341234\r
+\r
+\r
+.ti 0\r
+6.1.8. DATA\r
+\r
+.fi\r
+A DATA message (type 0x01) consists of a four-byte bin number and the \r
+actual chunk. In case a datagram contains a DATA message, a sender \r
+MUST always put the data message in the tail of the datagram. For \r
+example:\r
+.nf\r
+ 01 00000000 48656c6c6f20776f726c6421\r
+(This message accommodates an entire file: "Hello world!")\r
+\r
+\r
+.ti 0\r
+6.1.9. KEEPALIVE\r
+\r
+Keepalives do not have a message type on UDP. They are just simple \r
+datagrams consisting of a 4-byte channel id only.\r
+\r
+On the wire:\r
+.nf\r
+ 00000022\r
+\r
+.ti 0\r
+6.1.10. Flow and Congestion Control\r
+\r
+.fi\r
+Explicit flow control is not necessary in swift-over-UDP. In the case of\r
+video-on-demand the receiver will request data explicitly from peers and is \r
+therefore in control of how much data is coming towards it. In the case of\r
+live streaming, where a push-model may be used, the amount of data incoming\r
+is limited to the bitrate, which the receiver must be able to process otherwise\r
+it cannot play the stream. Should, for any reason, the receiver get saturated \r
+with data that situation is perfectly detected by the congestion control.\r
+Swift-over-UDP can support different congestion control algorithms, in particular,\r
+it supports the new IETF Low Extra Delay Background Transport (LEDBAT) congestion \r
+control algorithm that ensures that peer-to-peer traffic yields to regular \r
+best-effort traffic [LEDBAT]. \r
+\r
+\r
+.ti 0\r
+6.2. TCP\r
+\r
+.fi\r
+When run over TCP, swift becomes functionally equivalent to BitTorrent.\r
+Namely, most swift messages have corresponding BitTorrent messages and vice\r
+versa, except for BitTorrent's explicit interest declarations and\r
+choking/unchoking, which serve the classic implementation of the tit-for-tat\r
+algorithm [TIT4TAT]. However, TCP is not well suited for multiparty communication,\r
+as argued in Sec. 9.\r
+\r
+\r
+.ti 0\r
+6.3. RTP Profile for PPSP\r
+\r
+.fi\r
+In this section we sketch how swift can be integrated into RTP [RFC3550] to\r
+form the Peer-to-Peer Streaming Protocol (PPSP) [I-D.ietf-ppsp-reqs] running\r
+over UDP. The PPSP charter requires existing media transfer protocols be\r
+used [PPSPCHART]. Hence, the general idea is to define swift as a profile\r
+of RTP, in the same way as the Secure Real-time Transport Protocol (SRTP) \r
+[RFC3711]. SRTP, and therefore swift is considered ``a "bump in the stack"\r
+implementation which resides between the RTP application and the transport\r
+layer. [swift] intercepts RTP packets and then forwards an equivalent\r
+[swift] packet on the sending side, and intercepts [swift] packets and passes \r
+an equivalent RTP packet up the stack on the receiving side.'' [RFC3711].\r
+\r
+In particular, to encode a swift datagram in an RTP packet all the \r
+non-DATA messages of swift such as HINT and HAVE are postfixed to the RTP \r
+packet using the UDP encoding and the content of DATA messages is sent \r
+in the payload field. Implementations MAY omit the RTP header for packets\r
+without payload. This construction allows the streaming application to use \r
+of all RTP's current features, and with a modification to the Merkle tree \r
+hashing scheme (see below) meets swift's atomic datagram principle. The latter \r
+means that a receiving peer can autonomously verify the RTP packet as being \r
+correct content, thus preventing the spread of corrupt data (see \r
+requirement PPSP.SEC-REQ-4). \r
+\r
+The use of ACK messages for reliability is left as a choice of the\r
+application using PPSP.\r
+\r
+\r
+.ti 0\r
+6.3.1. Design\r
+\r
+6.3.1.1. Joining a Swarm\r
+\r
+To commence a PPSP download a peer A must have the swarm ID of the stream\r
+and a list of one or more tracker contact points (e.g. host+port). The list\r
+of trackers is optional in the presence of a decentralized tracking\r
+mechanism. The swarm ID consists of the swift root hash of the content,\r
+which is divided into chunks (see Discussion).\r
+\r
+Peer A now registers with the PPSP tracker following the tracker protocol\r
+[I-D.ietf.ppsp-reqs] and receives the IP address and RTP port of peers\r
+already in the swarm, say B, C, and D. Peer A now sends an RTP packet\r
+containing a HANDSHAKE without channel information to B, C, and D. This\r
+serves as an end-to-end check that the peers are actually in the correct\r
+swarm. Optionally A could include a HINT message in some RTP packets if it\r
+wants to start receiving content immediately. B and C respond with a\r
+HANDSHAKE and HAVE messages. D sends just a HANDSHAKE and omits HAVE\r
+messages as a way of choking A.\r
+\r
+\r
+6.3.1.2. Exchanging Chunks\r
+\r
+In response to B and C, A sends new RTP packets to B and C with HINTs for\r
+disjunct sets of chunks. B and C respond with the requested chunks in the\r
+payload and HAVE messages, updating their chunk availability. Upon receipt, \r
+A sends HAVE for the chunks received and new HINT messages to B and C. When \r
+e.g. C finds that A obtained a chunk (from B) that C did not yet have, C's \r
+response includes a HINT for that chunk.\r
+\r
+D does not send HAVE messages, instead if D decides to unchoke peer A, it\r
+sends an RTP packet with HAVE messages to inform A of its current\r
+availability. If B or C decide to choke A they stop sending HAVE and DATA\r
+messages and A should then rerequest from other peers. They may continue to\r
+send HINT messages, or exponentially slowing KEEPALIVE messages such that A\r
+keeps sending them HAVE messages.\r
+\r
+Once A has received all content (video-on-demand use case) it stops\r
+sending messages to all other peers that have all content (a.k.a. seeders).\r
+\r
+\r
+6.3.1.3. Leaving a Swarm\r
+\r
+Peers can implicitly leave a swarm by stopping to respond to messages.\r
+Sending peers should remove these peers from the current peer list. This\r
+mechanism works for both graceful and ungraceful leaves (i.e., peer crashes\r
+or disconnects). When leaving gracefully, a peer should deregister from the\r
+tracker following the PPSP tracker protocol.\r
+\r
+More explicit graceful leaves could be implemented using RTCP. In\r
+particular, a peer could send a RTCP BYE on the RTCP port that is derivable\r
+from a peer's RTP port for all peers in its current peer list. However, to\r
+prevent malicious peers from sending BYEs a form of peer authentication is\r
+required (e.g. using public keys as peer IDs [PERMIDS].)\r
+\r
+\r
+6.3.1.4. Discussion\r
+\r
+Using swift as an RTP profile requires a change to the content\r
+integrity protection scheme (see Sec. 3.5). The fields in the RTP \r
+header, such as the timestamp and PT fields, must be protected by the Merkle \r
+tree hashing scheme to prevent malicious alterations. Therefore, the Merkle\r
+tree is no longer constructed from pure content chunks, but from the complete \r
+RTP packet for a chunk as it would be transmitted (minus the non-DATA swift messages).\r
+In other words, the hash of the leaves in the tree is the hash over the\r
+Authenticated Portion of the RTP packet as defined by SRTP, illustrated\r
+in the following figure (extended from [RFC3711]). There is no need for the \r
+RTP packets to be fixed size, as the hashing scheme can deal with \r
+variable-sized leaves. \r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+.in 0\r
+ 0 1 2 3\r
+.br\r
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1\r
+.br\r
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<+\r
+.br\r
+ |V=2|P|X| CC |M| PT | sequence number | |\r
+.br\r
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |\r
+.br\r
+ | timestamp | |\r
+.br\r
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |\r
+.br\r
+ | synchronization source (SSRC) identifier | |\r
+.br\r
+ +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ |\r
+.br\r
+ | contributing source (CSRC) identifiers | |\r
+.br\r
+ | .... | |\r
+.br\r
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |\r
+.br\r
+ | RTP extension (OPTIONAL) | |\r
+.br\r
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |\r
+.br\r
+ | payload ... | |\r
+.br\r
+ | +-------------------------------+ |\r
+.br\r
+ | | RTP padding | RTP pad count | |\r
+.br\r
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+<+\r
+.br\r
+ ~ swift non-DATA messages (REQUIRED) ~ |\r
+.br\r
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |\r
+.br\r
+ | length of swift messages (REQUIRED) | |\r
+.br\r
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |\r
+.br\r
+ |\r
+.br\r
+ Authenticated Portion ---+\r
+.br\r
+\r
+ Figure: The format of an RTP-Swift packet. \r
+.in 3 \r
+ \r
+As a downside, with variable-sized payloads the automatic content size \r
+detection of Section 4 no longer works, so content length MUST be explicit in the \r
+metadata. In addition, storage on disk is more complex with out-of-order, \r
+variable-sized packets. On the upside, carrying RTP over swift allow \r
+decryption-less caching.\r
+ \r
+As with UDP, another matter is how much data is carried inside each packet.\r
+An important swift-specific factor here is the resulting number of hash \r
+calculations per second needed to verify chunks. Experiments should be \r
+conducted to ensure they are not excessive for, e.g., mobile hardware.\r
+\r
+At present, Peer IDs are not required in this design.\r
+\r
+\r
+.ti 0\r
+6.3.2. PPSP Requirements\r
+\r
+6.3.2.1. Basic Requirements\r
+\r
+- PPSP.REQ-1: The swift PEX message can also be used as the basis for a tracker protocol, to be discussed elsewhere.\r
+\r
+- PPSP.REQ-2: This draft preserves the properties of RTP.\r
+\r
+- PPSP.REQ-3: This draft does not place requirements on peer IDs, IP+port is sufficient. \r
+\r
+- PPSP.REQ-4: The content is identified by its root hash (video-on-demand) or a public key (live streaming).\r
+\r
+- PPSP.REQ-5: The content is partitioned by the streaming application.\r
+\r
+- PPSP.REQ-6: Each chunk is identified by a bin number (and its cryptographic hash.)\r
+\r
+- PPSP.REQ-7: The protocol is carried over UDP because RTP is.\r
+\r
+- PPSP.REQ-8: The protocol has been designed to allow meaningful data transfer between\r
+peers as soon as possible and to avoid unnecessary round-trips. It supports small and\r
+variable chunk sizes, and its content integrity protection enables wide scale caching.\r
+\r
+\r
+6.3.2.2. Peer Protocol Requirements\r
+\r
+- PPSP.PP.REQ-1: A GET_HAVE would have to be added to request which\r
+chunks are available from a peer, if the proposed push-based HAVE\r
+mechanism is not sufficient. \r
+\r
+- PPSP.PP.REQ-2: A set of HAVE messages satisfies this. \r
+\r
+- PPSP.PP.REQ-3: The PEX_REQ message satisfies this. Care should be taken with \r
+peer address exchange in general, as the use of such hearsay is a risk for the \r
+protocol as it may be exploited by malicious peers (as a DDoS attack mechanism).\r
+A secure tracking / peer sampling protocol like [PUPPETCAST] may be needed \r
+to make peer-address exchange safe.\r
+\r
+- PPSP.PP.REQ-4: HAVE messages convey current availability via a push model.\r
+\r
+- PPSP.PP.REQ-5: Bin numbering enables a compact representation of chunk availability.\r
+\r
+- PPSP.PP.REQ-6: A new PPSP specific Peer Report message would have to be\r
+added to RTCP. \r
+\r
+- PPSP.PP.REQ-7: Transmission and chunk requests are integrated in this\r
+protocol.\r
+\r
+\r
+6.3.2.3. Security Requirements\r
+\r
+- PPSP.SEC.REQ-1: An access control mechanism like Closed Swarms\r
+[CLOSED] would have to be added. \r
+\r
+- PPSP.SEC.REQ-2: As RTP is carried verbatim over swift, RTP encryption\r
+can be used. Note that just encrypting the RTP part will allow for \r
+caching servers that are part of the swarm but do not need access to the \r
+decryption keys. They just need access to the swift HASHES in the postfix to \r
+verify the packet's integrity.\r
+\r
+- PPSP.SEC.REQ-3: RTP encryption or IPsec [RFC4303] can be used, if the\r
+swift messages must also be encrypted. \r
+\r
+- PPSP.SEC.REQ-4: The Merkle tree hashing scheme prevents the indirect\r
+spread of corrupt content, as peers will only forward chunks to others if\r
+their integrity check out. Another protection mechanism is to not depend on\r
+hearsay (i.e., do not forward other peers' availability information), or to\r
+only use it when the information spread is self-certified by its subjects.\r
+\r
+Other attacks, such as a malicious peer claiming it has content but not\r
+replying, are still possible. Or wasting CPU and bandwidth at a receiving\r
+peer by sending packets where the DATA doesn't match the HASHes.\r
+\r
+\r
+- PPSP.SEC.REQ-5: The Merkle tree hashing scheme allows a receiving\r
+peer to detect a malicious or faulty sender, which it can subsequently\r
+ignore. Spreading this knowledge to other peers such that they know\r
+about this bad behavior is hearsay. \r
+\r
+\r
+- PPSP.SEC.REQ-6: A risk in peer-to-peer streaming systems is that malicious\r
+peers launch an Eclipse [ECLIPSE] attack on the initial injectors of the\r
+content (in particular in live streaming). The attack tries to let the\r
+injector upload to just malicious peers which then do not forward the\r
+content to others, thus stopping the distribution. An Eclipse attack could\r
+also be launched on an individual peer. Letting these injectors only use\r
+trusted trackers that provide true random samples of the population or using\r
+a secure peer sampling service [PUPPETCAST] can help negate such an attack. \r
+\r
+\r
+- PPSP.SEC.REQ-7: swift supports decentralized tracking via PEX or\r
+additional mechanisms such as DHTs [SECDHTS], but self-certification of\r
+addresses is needed. Self-certification means For example, that each peer \r
+has a public/private key pair [PERMIDS] and creates self-certified address \r
+changes that include the swarm ID and a timestamp, which are then exchanged\r
+among peers or stored in DHTs. See also discussion of PPSP.PP.REQ-3 \r
+above. Content distribution can continue as long as there are peers that \r
+have it available.\r
+\r
+- PPSP.SEC.REQ-8: The verification of data via hashes obtained from a\r
+trusted source is well-established in the BitTorrent protocol [BITTORRENT].\r
+The proposed Merkle tree scheme is a secure extension of this idea.\r
+Self-certification and not using hearsay are other lessons learned from\r
+existing distributed systems.\r
+\r
+- PPSP.SEC.REQ-9: Swift has built-in content integrity protection via\r
+self-certified naming of content, see SEC.REQ-5 and Sec. 3.5.1.\r
+\r
+\r
+.ti 0\r
+6.4. HTTP (as PPSP)\r
+\r
+In this section we sketch how swift can be carried over HTTP [RFC2616] to\r
+form the PPSP running over TCP. The general idea is to encode a swift\r
+datagram in HTTP GET and PUT requests and their replies by transmitting all\r
+the non-DATA messages such as HINTs and HAVEs as headers and send DATA\r
+messages in the body. This idea follows the atomic datagram principle for\r
+each request and reply. So a receiving peer can autonomously verify the\r
+message as carrying correct data, thus preventing the spread of corrupt data\r
+(see requirement PPSP.SEC-REQ-4). \r
+\r
+A problem with HTTP is that it is a client/server protocol. To overcome this\r
+problem, a peer A uses a PUT request instead of a GET request if the peer B\r
+has indicated in a reply that it wants to retrieve a chunk from A. In cases\r
+where peer A is no longer interested in receiving requests from B (described\r
+below) B may need to establish a new HTTP connection to A to quickly\r
+download a chunk, instead of waiting for a convenient time when A sends\r
+another request. As an alternative design, two HTTP connections could be\r
+used always., but this is inefficient.\r
+\r
+.ti 0\r
+6.4.1. Design\r
+\r
+6.4.1.1. Joining a Swarm\r
+\r
+To commence a PPSP download a peer A must have the swarm ID of the stream\r
+and a list of one or more tracker contact points, as above. The swarm ID as\r
+earlier also consists of the swift root hash of the content, divided in\r
+chunks by the streaming application (e.g. fixed-size chunks of 1 kilobyte\r
+for video-on-demand). \r
+\r
+Peer A now registers with the PPSP tracker following the tracker protocol\r
+[I-D.ietf-ppsp-reqs] and receives the IP address and HTTP port of peers\r
+already in the swarm, say B, C, and D. Peer A now establishes persistent\r
+HTTP connections with B, C, D and sends GET requests with the Request-URI\r
+set to /<encoded roothash>. Optionally A could include a HINT message in\r
+some requests if it wants to start receiving content immediately. A HINT is\r
+encoded as a Range header with a new "bins" unit [RFC2616,$14.35].\r
+\r
+B and C respond with a 200 OK reply with header-encoded HAVE messages. A\r
+HAVE message is encoded as an extended Accept-Ranges: header [RFC2616,$14.5] \r
+with the new bins unit and the possibility of listing the set of accepted bins. \r
+If no HINT/Range header was present in the request, the body of the reply is\r
+empty. D sends just a 200 OK reply and omits the HAVE/Accept-Ranges header\r
+as a way of choking A.\r
+\r
+6.4.1.2. Exchanging Chunks\r
+\r
+In response to B and C, A sends GET requests with Range headers, requesting\r
+disjunct sets of chunks. B and C respond with 206 Partial Content replies\r
+with the requested chunks in the body and Accept-Ranges headers, updating\r
+their chunk availability. The HASHES for the chunks are encoded in a new\r
+Content-Merkle header and the Content-Range is set to identify the chunk \r
+[RFC2616,$14.16]. A new "multipart-bin ranges" equivalent to the \r
+"multipart-bytes ranges" media type may be used to transmit multiple chunks \r
+in one reply.\r
+\r
+Upon receipt, A sends a new GET request with a HAVE/Accept-Ranges header for\r
+the chunks received and new HINT/Range headers to B and C. Now when e.g. C\r
+finds that A obtained a chunk (from B) that C did not yet have, C's response\r
+includes a HINT/Range for that chunk. In this case, A's next request to C is\r
+not a GET request, but a PUT request with the requested chunk sent in the\r
+body.\r
+\r
+Again, working around the fact that HTTP is a client/server protocol, peer A\r
+periodically sends HEAD requests to peer D (which was virtually choking A)\r
+that serve as keepalives and may contain HAVE/Accept-Ranges headers. If D\r
+decides to unchoke peer A, it includes an Accept-Ranges header in the "200 OK"\r
+reply to inform A of its current chunk availability. \r
+\r
+If B or C decide to choke A they start responding with 204 No Content\r
+replies without HAVE/Accept-Ranges headers and A should then re-request from\r
+other peers. However, if their replies contain HINT/Range headers A should\r
+keep on sending PUT requests with the desired data (another client/server\r
+workaround). If not, A should slowly send HEAD requests as keepalive and\r
+content availability update.\r
+\r
+Once A has received all content (video-on-demand use case) it closes the\r
+persistent connections to all other peers that have all content (a.k.a.\r
+seeders).\r
+\r
+\r
+6.4.1.3. Leaving a Swarm\r
+\r
+Peers can explicitly leave a swarm by closing the connection. This mechanism\r
+works for both graceful and ungraceful leaves (i.e., peer crashes or\r
+disconnects). When leaving gracefully, a peer should deregister from the\r
+tracker following the PPSP tracker protocol.\r
+\r
+\r
+6.4.1.4. Discussion\r
+\r
+As mentioned earlier, this design suffers from the fact that HTTP is a\r
+client/server protocol. A solution where a peer establishes two HTTP\r
+connections with every other peer may be more elegant, but inefficient. \r
+The mapping of swift messages to headers remains the same:\r
+\r
+ HINT = Range\r
+.br\r
+ HAVE = Accept-Ranges\r
+.br\r
+ HASH = Content-Merkle\r
+.br \r
+ PEX = e.g. extended Content-Location\r
+.br\r
+\r
+The Content-Merkle header should include some parameters to\r
+indicate the hash function and chunk size (e.g. SHA1 and 1K) used to\r
+build the Merkle tree.\r
+\r
+\r
+.ti 0\r
+6.4.2. PPSP Requirements\r
+\r
+6.4.2.1. Basic Requirements\r
+\r
+- PPSP.REQ-1: The HTTP-based BitTorrent tracker protocol [BITTORRENT] can be\r
+used as the basis for a tracker protocol, to be discussed elsewhere.\r
+\r
+- PPSP.REQ-2: This draft preserves the properties of HTTP, but \r
+extra mechanisms may be necessary to protect against faulty\r
+or malicious peers.\r
+\r
+- PPSP.REQ-3: This draft does not place requirements on peer IDs,\r
+IP+port is sufficient. \r
+\r
+- PPSP.REQ-4: The content is identified by its root hash (video-on-demand)\r
+or a public key (live streaming).\r
+\r
+- PPSP.REQ-5: The content is partitioned into chunks by the streaming application (see 6.4.1.1.)\r
+\r
+- PPSP.REQ-6: Each chunk is identified by a bin number (and its cryptographic hash.)\r
+\r
+- PPSP.REQ-7: The protocol is carried over TCP because HTTP is.\r
+\r
+\r
+6.4.2.2. Peer Protocol Requirements\r
+\r
+- PPSP.PP.REQ-1: A HEAD request can be used to find out which\r
+chunks are available from a peer, which returns the new Accept-Ranges header.\r
+\r
+- PPSP.PP.REQ-2: The new Accept-Ranges header satisfies this. \r
+\r
+- PPSP.PP.REQ-3: A GET with a request-URI requesting the peers of a resource\r
+(e.g. /<encoded roothash>/peers) would have to be added to request known\r
+peers from a peer, if the proposed push-based PEX/~Content-Location\r
+mechanism is not sufficient. Care should be taken with peer address exchange \r
+in general, as the use of such hearsay is a risk for the protocol as it may be \r
+exploited by malicious peers (as a DDoS attack mechanism). A secure \r
+tracking / peer sampling protocol like [PUPPETCAST] may be needed \r
+to make peer-address exchange safe.\r
+\r
+\r
+- PPSP.PP.REQ-4: HAVE/Accept-Ranges headers convey current availability.\r
+\r
+- PPSP.PP.REQ-5: Bin numbering enables a compact representation of chunk availability.\r
+\r
+- PPSP.PP.REQ-6: A new PPSP specific Peer-Report header would have to be\r
+added. \r
+\r
+- PPSP.PP.REQ-7: Transmission and chunk requests are integrated in this\r
+protocol.\r
+\r
+\r
+\r
+\r
+6.4.2.3. Security Requirements\r
+\r
+- PPSP.SEC.REQ-1: An access control mechanism like Closed Swarms\r
+[CLOSED] would have to be added. \r
+\r
+- PPSP.SEC.REQ-2: As swift is carried over HTTP, HTTPS encryption can be\r
+used instead. Alternatively, just the body could be encrypted. The latter\r
+allows for caching servers that are part of the swarm but do not need access\r
+to the decryption keys (they need access to the swift HASHES in the headers\r
+to verify the packet's integrity).\r
+\r
+- PPSP.SEC.REQ-3: HTTPS encryption or the content encryption facilities of\r
+HTTP can be used.\r
+\r
+- PPSP.SEC.REQ-4: The Merkle tree hashing scheme prevents the indirect\r
+spread of corrupt content, as peers will only forward content to others if\r
+its integrity checks out. Another protection mechanism is to not depend on\r
+hearsay (i.e., do not forward other peers' availability information), or to\r
+only use it when the information spread is self-certified by its subjects.\r
+\r
+Other attacks such as a malicious peer claiming it has content, but not\r
+replying are still possible. Or wasting CPU and bandwidth at a receiving\r
+peer by sending packets where the body doesn't match the HASH/Content-Merkle\r
+headers.\r
+\r
+\r
+- PPSP.SEC.REQ-5: The Merkle tree hashing scheme allows a receiving peer to\r
+detect a malicious or faulty sender, which it can subsequently close its\r
+connection to and ignore. Spreading this knowledge to other peers such that\r
+they know about this bad behavior is hearsay. \r
+\r
+\r
+- PPSP.SEC.REQ-6: A risk in peer-to-peer streaming systems is that malicious\r
+peers launch an Eclipse [ECLIPSE] attack on the initial injectors of the\r
+content (in particular in live streaming). The attack tries to let the\r
+injector upload to just malicious peers which then do not forward the\r
+content to others, thus stopping the distribution. An Eclipse attack could\r
+also be launched on an individual peer. Letting these injectors only use\r
+trusted trackers that provide true random samples of the population or using\r
+a secure peer sampling service [PUPPETCAST] can help negate such an attack. \r
+\r
+\r
+- PPSP.SEC.REQ-7: swift supports decentralized tracking via PEX or\r
+additional mechanisms such as DHTs [SECDHTS], but self-certification of\r
+addresses is needed. Self-certification means For example, that each peer \r
+has a public/private key pair [PERMIDS] and creates self-certified address \r
+changes that include the swarm ID and a timestamp, which are then exchanged\r
+among peers or stored in DHTs. See also discussion of PPSP.PP.REQ-3 \r
+above. Content distribution can continue as long as there are peers that \r
+have it available.\r
+\r
+- PPSP.SEC.REQ-8: The verification of data via hashes obtained from a\r
+trusted source is well-established in the BitTorrent protocol [BITTORRENT].\r
+The proposed Merkle tree scheme is a secure extension of this idea.\r
+Self-certification and not using hearsay are other lessons learned from\r
+existing distributed systems.\r
+\r
+- PPSP.SEC.REQ-9: Swift has built-in content integrity protection via\r
+self-certified naming of content, see SEC.REQ-5 and Sec. 3.5.1.\r
+\r
+\r
+.ti 0\r
+7. Security Considerations\r
+\r
+As any other network protocol, the swift faces a common set of security\r
+challenges. An implementation must consider the possibility of buffer\r
+overruns, DoS attacks and manipulation (i.e. reflection attacks). Any\r
+guarantee of privacy seems unlikely, as the user is exposing its IP address\r
+to the peers. A probable exception is the case of the user being hidden\r
+behind a public NAT or proxy.\r
+\r
+\r
+.ti 0\r
+8. Extensibility\r
+\r
+.ti 0\r
+8.1. 32 bit vs 64 bit\r
+\r
+.nf\r
+While in principle the protocol supports bigger (>1TB) files, all the\r
+mentioned counters are 32-bit. It is an optimization, as using\r
+\%64-bit numbers on-wire may cost ~2% practical overhead. The 64-bit\r
+version of every message has typeid of 64+t, e.g. typeid 68 for\r
+\%64-bit hash message:\r
+.nf\r
+ 44 000000000000000E 01234567890ABCDEF1234567890ABCDEF1234567\r
+\r
+.ti 0\r
+8.2. IPv6\r
+\r
+.fi\r
+IPv6 versions of PEX messages use the same 64+t shift as just mentioned.\r
+\r
+\r
+.ti 0\r
+8.3. Congestion Control Algorithms\r
+\r
+.fi\r
+Congestion control algorithm is left to the implementation and may even vary\r
+from peer to peer. Congestion control is entirely implemented by the sending\r
+peer, the receiver only provides clues, such as hints, acknowledgments and\r
+timestamps. In general, it is expected that servers would use TCP-like\r
+congestion control schemes such as classic AIMD or CUBIC [CUBIC]. End-user\r
+peers are expected to use weaker-than-TCP (least than best effort)\r
+congestion control, such as [LEDBAT] to minimize seeding counter-incentives.\r
+\r
+\r
+.ti 0\r
+8.4. Piece Picking Algorithms\r
+\r
+Piece picking entirely depends on the receiving peer. The sender peer is\r
+made aware of preferred pieces by the means of HINT messages. In some\r
+scenarios it may be beneficial to allow the sender to ignore those hints and\r
+send unrequested data.\r
+\r
+\r
+.ti 0\r
+8.5. Reciprocity Algorithms\r
+\r
+Reciprocity algorithms are the sole responsibility of the sender peer.\r
+Reciprocal intentions of the sender are not manifested by separate messages\r
+(as BitTorrent's CHOKE/UNCHOKE), as it does not guarantee anything anyway\r
+(the "snubbing" syndrome).\r
+\r
+\r
+.ti 0\r
+8.6. Different crypto/hashing schemes\r
+\r
+.fi\r
+Once a flavor of swift will need to use a different crypto scheme\r
+(e.g., SHA-256), a message should be allocated for that. As the root\r
+hash is supplied in the handshake message, the crypto scheme in use\r
+will be known from the very beginning. As the root hash is the\r
+content's identifier, different schemes of crypto cannot be mixed\r
+in the same swarm; different swarms may distribute the same content\r
+using different crypto.\r
+\r
+\r
+.ti 0\r
+9. Rationale\r
+\r
+Historically, the Internet was based on end-to-end unicast\r
+and, considering the failure of multicast, was addressed by\r
+different technologies, which ultimately boiled down to maintaining\r
+and coordinating distributed replicas. On one hand, downloading\r
+from a nearby well-provisioned replica is somewhat faster and/or\r
+cheaper; on the other hand, it requires to coordinate multiple\r
+parties (the data source, mirrors/CDN sites/peers, consumers). As\r
+the Internet progresses to richer and richer content, the overhead\r
+of peer/replica coordination becomes dwarfed by the mass of the\r
+download itself. Thus, the niche for multiparty transfers expands.\r
+Still, current, relevant technologies are tightly coupled to a\r
+single use case or even infrastructure of a particular corporation.\r
+The mission of our project is to create a generic content-centric\r
+multiparty transport protocol to allow seamless, effortless data\r
+dissemination on the Net.\r
+\r
+ TABLE 1. Use cases.\r
+\r
+.br\r
+ | mirror-based peer-assisted peer-to-peer\r
+.br\r
+------+----------------------------------------------------\r
+.br\r
+data | SunSITE CacheLogic VelociX BitTorrent\r
+.br\r
+VoD | YouTube Azureus(+seedboxes) SwarmPlayer\r
+.br\r
+live | Akamai Str. Octoshape, Joost PPlive\r
+.br\r
+\r
+.fi\r
+The protocol must be designed for maximum genericity, thus \r
+focusing on the very core of the mission, contain no magic\r
+ constants and no hardwired policies. Effectively, it is a \r
+set of messages allowing to securely retrieve data from\r
+whatever source available, in parallel. Ideally, the protocol must\r
+be able to run over IP as an independent transport protocol.\r
+Practically, it must run over UDP and TCP.\r
+\r
+\r
+.ti 0\r
+9.1. Design Goals\r
+\r
+.fi\r
+The technical focus of the swift protocol is to find the \r
+simplest solution involving the minimum set of primitives, still \r
+being sufficient to implement all the targeted usecases (see \r
+Table 1), suitable for use in general-purpose software and hardware\r
+(i.e. a web browser or a set-top box). The five design goals for \r
+the protocol are:\r
+\r
+.nf\r
+1. Embeddable kernel-ready protocol.\r
+2. Embrace real-time streaming, in- and out-of-order download.\r
+3. Have short warm-up times.\r
+4. Traverse NATs transparently.\r
+5. Be extensible, allow for multitude of implementation over\r
+ diverse mediums, allow for drop-in pluggability.\r
+\r
+The objectives are referenced as (1)-(5).\r
+\r
+.fi\r
+The goal of embedding (1) means that the protocol must be ready \r
+to function as a regular transport protocol inside a set-top box, \r
+mobile device, a browser and/or in the kernel space. Thus, the \r
+protocol must have light footprint, preferably less than TCP, \r
+in spite of the necessity to support numerous ongoing connections \r
+as well as to constantly probe the network for new possibilities. \r
+The practical overhead for TCP is estimated at 10KB per connection \r
+[HTTP1MLN]. We aim at <1KB per peer connected. Also, the amount of\r
+ code necessary to make a basic implementation must be limited to \r
+10KLoC of C. Otherwise, besides the resource considerations, \r
+maintaining and auditing the code might become prohibitively expensive.\r
+\r
+The support for all three basic usecases of real-time streaming,\r
+ \%in-order download and out-of-order download (2) is necessary \r
+for the manifested goal of THE multiparty transport protocol as no\r
+ single usecase dominates over the others.\r
+\r
+The objective of short warm-up times (3) is the matter of end-user\r
+ experience; the playback must start as soon as possible. Thus any \r
+unnecessary initialization roundtrips and warm-up cycles must be \r
+eliminated from the transport layer.\r
+\r
+.fi\r
+Transparent NAT traversal (4) is absolutely necessary as at least\r
+60% of today's users are hidden behind NATs. NATs severely affect\r
+connection patterns in P2P networks thus impacting performance \r
+and fairness [MOLNAT,LUCNAT].\r
+\r
+The protocol must define a common message set (5) to be used by \r
+implementations; it must not hardwire any magic constants, \r
+algorithms or schemes beyond that. For example, an implementation\r
+ is free to use its own congestion control, connection rotation \r
+or reciprocity algorithms. Still, the protocol must enable such \r
+algorithms by supplying sufficient information. For example, \r
+trackerless peer discovery needs peer exchange messages, \r
+scavenger congestion control may need timestamped acknowledgments,\r
+ etc.\r
+\r
+\r
+.ti 0\r
+9.2. Not TCP\r
+\r
+.fi\r
+To large extent, swift's design is defined by the cornerstone decision\r
+to get rid of TCP and not to reinvent any TCP-like transports on\r
+top of UDP or otherwise. The requirements (1), (4), (5) make TCP a\r
+bad choice due to its high per-connection footprint, complex and\r
+less reliable NAT traversal and fixed predefined congestion control\r
+algorithms. Besides that, an important consideration is that no\r
+block of TCP functionality turns out to be useful for the general\r
+case of swarming downloads. Namely,\r
+.nf\r
+ 1. in-order delivery is less useful as peer-to-peer protocols\r
+ often employ out-of-order delivery themselves and in either case\r
+ \%out-of-order data can still be stored;\r
+ 2. reliable delivery/retransmissions are not useful because\r
+ the same data might be requested from different sources; as\r
+ in-order delivery is not required, packet losses might be\r
+ patched up lazily, without stopping the flow of data;\r
+ 3. flow control is not necessary as the receiver is much less\r
+ likely to be saturated with the data and even if so, that\r
+ situation is perfectly detected by the congestion control;\r
+ 4. TCP congestion control is less useful as custom congestion\r
+ control is often needed [LEDBAT].\r
+In general, TCP is built and optimized for a different usecase than\r
+we have with swarming downloads. The abstraction of a "data pipe"\r
+orderly delivering some stream of bytes from one peer to another\r
+turned out to be irrelevant. In even more general terms, TCP\r
+supports the abstraction of pairwise _conversations_, while we need\r
+a content-centric protocol built around the abstraction of a cloud\r
+of participants disseminating the same _data_ in any way and order\r
+that is convenient to them.\r
+\r
+.fi\r
+Thus, the choice is to design a protocol that runs on top of \r
+unreliable datagrams. Instead of reimplementing TCP, we create a \r
+\%datagram-based protocol, completely dropping the sequential data \r
+stream abstraction. Removing unnecessary features of TCP makes \r
+it easier both to implement the protocol and to verify it; \r
+numerous TCP vulnerabilities were caused by complexity of the \r
+protocol's state machine. Still, we reserve the possibility \r
+to run swift on top of TCP or HTTP. \r
+\r
+Pursuing the maxim of making things as simple as possible but not \r
+simpler, we fit the protocol into the constraints of the transport\r
+layer by dropping all the transmission's technical metadata except \r
+for the content's root hash (compare that to metadata files used \r
+in BitTorrent). Elimination of technical metadata is achieved \r
+through the use of Merkle [MERKLE,ABMRKL] hash trees, exclusively\r
+single-file transfers and other techniques. As a result, a transfer\r
+is identified and bootstrapped by its root hash only.\r
+\r
+.fi\r
+To avoid the usual layering of positive/negative acknowledgment \r
+mechanisms we introduce a scale-invariant acknowledgment system\r
+ (see Sec 4.4). The system allows for aggregation and variable \r
+level of detail in requesting, announcing and acknowledging data,\r
+ serves \%in-order and out-of-order retrieval with equal ease.\r
+Besides the protocol's footprint, we also aim at lowering the \r
+size of a minimal useful interaction. Once a single datagram is \r
+received, it must be checked for data integrity, and then either \r
+dropped or accepted, consumed and relayed.\r
+\r
+\r
+\r
+.ti 0\r
+9.3. Generic Acknowledgments\r
+\r
+.nf\r
+Generic acknowledgments came out of the need to simplify the\r
+data addressing/requesting/acknowledging mechanics, which tends\r
+to become overly complex and multilayered with the conventional\r
+approach. Take the BitTorrent+TCP tandem for example:\r
+\r
+1. The basic data unit is a byte of content in a file.\r
+2. BitTorrent's highest-level unit is a "torrent", physically a\r
+byte range resulting from concatenation of content files.\r
+3. A torrent is divided into "pieces", typically about a thousand\r
+of them. Pieces are used to communicate progress to other\r
+peers. Pieces are also basic data integrity units, as the torrent's\r
+metadata includes a SHA1 hash for every piece.\r
+4. The actual data transfers are requested and made in 16KByte\r
+units, named "blocks" or chunks.\r
+5. Still, one layer lower, TCP also operates with bytes and byte\r
+offsets which are totally different from the torrent's bytes and\r
+offsets, as TCP considers cumulative byte offsets for all content\r
+sent by a connection, be it data, metadata or commands.\r
+6. Finally, another layer lower, IP transfers independent datagrams\r
+(typically around 1.5 kilobyte), which TCP then reassembles into\r
+continuous streams.\r
+\r
+Obviously, such addressing schemes need lots of mappings; from\r
+piece number and block to file(s) and offset(s) to TCP sequence\r
+numbers to the actual packets and the other way around. Lots of\r
+complexity is introduced by mismatch of bounds: packet bounds are\r
+different from file, block or hash/piece bounds. The picture is\r
+typical for a codebase which was historically layered.\r
+\r
+To simplify this aspect, we employ a generic content addressing\r
+scheme based on binary intervals, or "bins" for short.\r
+\r
+\r
+\r
+.ti 0\r
+Acknowledgements\r
+\r
+Arno Bakker and Victor Grishchenko are partially supported by the\r
+P2P-Next project (http://www.p2p-next.org/), a research project \r
+supported by the European Community under its 7th Framework Programme\r
+(grant agreement no. 216217). The views and conclusions contained \r
+herein are those of the authors and should not be interpreted as \r
+necessarily representing the official policies or endorsements, \r
+either expressed or implied, of the P2P-Next project or the European \r
+Commission.\r
+\r
+.fi\r
+The swift protocol was designed by Victor Grishchenko at Technische Universiteit Delft.\r
+The authors would like to thank the following people for their \r
+contributions to this draft: Mihai Capota, Raul Jiminez, Flutra Osmani, \r
+Riccardo Petrocco, Johan Pouwelse, and Raynor Vliegendhart.\r
+\r
+\r
+.ti 0\r
+References\r
+\r
+.nf\r
+.in 0\r
+[RFC2119] Key words for use in RFCs to Indicate Requirement Levels\r
+[HTTP1MLN] Richard Jones. "A Million-user Comet Application with\r
+ Mochiweb", Part 3. http://www.metabrew.com/article/\r
+ \%a-million-user-comet-application-with-mochiweb-part-3\r
+[MOLNAT] J.J.D. Mol, J.A. Pouwelse, D.H.J. Epema and H.J. Sips:\r
+ \%"Free-riding, Fairness, and Firewalls in P2P File-Sharing"\r
+ Proc. Eighth International Conference on Peer-to-Peer Computing \r
+ (P2P '08), Aachen, Germany, 8-11 Sept. 2008, pp. 301 - 310.\r
+[LUCNAT] L. D'Acunto and M. Meulpolder and R. Rahman and J.A. \r
+ Pouwelse and H.J. Sips. "Modeling and Analyzing the Effects\r
+ of Firewalls and NATs in P2P Swarming Systems". In Proc. of \r
+ IEEE IPDPS (HotP2P), Atlanta, USA, April 23, 2010.\r
+[BINMAP] V. Grishchenko, J. Pouwelse: "Binmaps: hybridizing bitmaps\r
+ and binary trees". Technical Report PDS-2011-005, Parallel and \r
+ Distributed Systems Group, Fac. of Electrical Engineering, \r
+ Mathematics, and Computer Science, Delft University of Technology, \r
+ The Netherlands, April 2009.\r
+[SNP] B. Ford, P. Srisuresh, D. Kegel: "Peer-to-Peer Communication\r
+ Across Network Address Translators",\r
+ http://www.brynosaurus.com/pub/net/p2pnat/\r
+[FIPS180-2]\r
+ Federal Information Processing Standards Publication 180-2:\r
+ "Secure Hash Standard" 2002 August 1.\r
+[MERKLE] Merkle, R. "Secrecy, Authentication, and Public Key Systems", \r
+ Ph.D. thesis, Dept. of Electrical Engineering, Stanford University, \r
+ CA, USA, 1979. pp 40-45.\r
+[ABMRKL] Arno Bakker: "Merkle hash torrent extension", BitTorrent \r
+ Enhancement Proposal 30, Mar 2009.\r
+ http://bittorrent.org/beps/bep_0030.html\r
+[CUBIC] Injong Rhee, and Lisong Xu: "CUBIC: A New TCP-Friendly\r
+ \%High-Speed TCP Variant", Proc. Third International Workshop\r
+ on Protocols for Fast Long-Distance Networks (PFLDnet), Lyon,\r
+ France, Feb 2005.\r
+[LEDBAT] S. Shalunov et al. "Low Extra Delay Background Transport \r
+ (LEDBAT)", IETF Internet-Draft draft-ietf-ledbat-congestion\r
+ (work in progress), Oct 2011.\r
+ \%http://datatracker.ietf.org/doc/draft-ietf-ledbat-congestion/ \r
+[TIT4TAT] Bram Cohen: "Incentives Build Robustness in BitTorrent", \r
+ Proc. 1st Workshop on Economics of Peer-to-Peer Systems, Berkeley, \r
+ CA, USA, Jun 2003.\r
+[BITTORRENT] B. Cohen, "The BitTorrent Protocol Specification",\r
+ February 2008, \%http://www.bittorrent.org/beps/bep_0003.html\r
+[RFC3550] Schulzrinne, H., Casner, S., Frederick, R., and V.\r
+ Jacobson, "RTP: A Transport Protocol for Real-Time\r
+ Applications", STD 64, RFC 3550, July 2003.\r
+[RFC3711] M. Baugher, D. McGrew, M. Naslund, E. Carrara, K. Norrman,\r
+ "The Secure Real-time Transport Protocol (SRTP), RFC 3711, March \r
+ 2004.\r
+[RFC5389] Rosenberg, J., Mahy, R., Matthews, P., and D. Wing,\r
+ "Session Traversal Utilities for NAT (STUN)", RFC 5389, October 2008.\r
+[RFC2616] R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, \r
+ P. Leach, T. Berners-Lee, "Hypertext Transfer Protocol -- HTTP/1.1",\r
+ RFC2616, June 1999.\r
+[I-D.ietf-ppsp-reqs] Zong, N., Zhang, Y., Pascual, V., Williams, C.,\r
+ and L. Xiao, "P2P Streaming Protocol (PPSP) Requirements", \r
+ draft-ietf-ppsp-reqs-05 (work in progress), October 2011.\r
+[PPSPCHART] M. Stiemerling et al. "Peer to Peer Streaming Protocol (ppsp)\r
+ Description of Working Group" \r
+ \%http://datatracker.ietf.org/wg/ppsp/charter/\r
+[PERMIDS] A. Bakker et al. "Next-Share Platform M8--Specification\r
+ Part", App. C. P2P-Next project deliverable D4.0.1 (revised), \r
+ June 2009.\r
+ \%http://www.p2p-next.org/download.php?id=E7750C654035D8C2E04D836243E6526E\r
+[PUPPETCAST] A. Bakker and M. van Steen. "PuppetCast: A Secure Peer\r
+ Sampling Protocol". Proceedings 4th Annual European Conference on\r
+ Computer Network Defense (EC2ND'08), pp. 3-10, Dublin, Ireland,\r
+ 11-12 December 2008.\r
+[CLOSED] N. Borch, K. Michell, I. Arntzen, and D. Gabrijelcic: "Access\r
+ control to BitTorrent swarms using closed swarms". In Proceedings\r
+ of the 2010 ACM workshop on Advanced video streaming techniques\r
+ for peer-to-peer networks and social networking (AVSTP2P '10).\r
+ ACM, New York, NY, USA, 25-30. \r
+ \%http://doi.acm.org/10.1145/1877891.1877898 \r
+[ECLIPSE] E. Sit and R. Morris, "Security Considerations for\r
+ Peer-to-Peer Distributed Hash Tables", IPTPS '01: Revised Papers\r
+ from the First International Workshop on Peer-to-Peer Systems, pp.\r
+ 261-269, Springer-Verlag, London, UK, 2002.\r
+[SECDHTS] G. Urdaneta, G. Pierre, M. van Steen, "A Survey of DHT\r
+ Security Techniques", ACM Computing Surveys, vol. 43(2), June 2011.\r
+[SWIFTIMPL] V. Grishchenko, et al. "Swift M40 reference implementation",\r
+ \%http://swarmplayer.p2p-next.org/download/Next-Share-M40.tar.bz2\r
+ (subdirectory Next-Share/TUD/swift-trial-r2242/), July 2011.\r
+[CCNWIKI] http://en.wikipedia.org/wiki/Content-centric_networking\r
+[HAC01] A.J. Menezes, P.C. van Oorschot and S.A. Vanstone. "Handbook of\r
+ Applied Cryptography", CRC Press, October 1996 (Fifth Printing, \r
+ August 2001). \r
+[JIM11] R. Jimenez, F. Osmani, and B. Knutsson. "Sub-Second Lookups on \r
+ a Large-Scale Kademlia-Based Overlay". 11th IEEE International \r
+ Conference on Peer-to-Peer Computing 2011, Kyoto, Japan, Aug. 2011 \r
+\r
+\r
+.ti 0\r
+Authors' addresses\r
+\r
+.in 3\r
+A. Bakker\r
+Technische Universiteit Delft \r
+Department EWI/ST/PDS\r
+Room HB 9.160\r
+Mekelweg 4\r
+2628CD Delft\r
+The Netherlands\r
+\r
+Email: arno@cs.vu.nl\r
+\r
+.ce 0\r
projects / swifty.git / blobdiff