.ti 3\r
The swift is a generic multiparty (swarming) transport protocol.\r
\r
-.nf\r
+.fi\r
.in 3\r
-The TCP, today's dominating transport protocol, is connection/\r
-\%conversation-oriented. But traffic-wise, the currently dominating\r
-usecase is content dissemination. There is a multitude of\r
-incompatible approaches to resolve that discrepancy above/below the\r
-transport layer: peer-to-peer, CDN, caches, mirrors, multicast, etc.\r
-The swift aims at creating a single unified content-centric transport\r
-protocol serving as a lingua-franca of content distribution.\r
-To implement that ultimate data cloud model, the protocol has to\r
-unify use cases of data download, video-on-demand and live streaming.\r
-It must work in the settings of client-server, peer-to-peer, CDN or\r
-\%peer-assisted networks, effectively blending those architectures.\r
+The TCP, today's dominating transport protocol, is connection/ conversation-oriented. But traffic-wise, the currently dominating usecase is content dissemination. There is a multitude of incompatible approaches to resolve that discrepancy above/below the transport layer: peer-to-peer, CDN, caches, mirrors, multicast, etc.\r
+The swift aims at creating a single unified content-centric transport protocol serving as a lingua-franca of content distribution.\r
+To implement that ultimate data cloud model, the protocol has to unify use cases of data download, video-on-demand and live streaming. It must work in the settings of client-server, peer-to-peer, CDN or \%peer-assisted networks, effectively blending those architectures.\r
\r
\r
.ti 0\r
4. swift subsystems and design choices\r
4.1. The atomic datagram principle\r
4.2. Handshake and multiplexing\r
- 4.3. Data integrity and on-demand Merkle hashes\r
- 4.4. Generic acknowledgments\r
+ 4.3. Generic acknowledgments\r
+ 4.4. Data integrity and on-demand Merkle hashes\r
4.5. Peer exchange and NAT hole punching\r
- 4.6. Congestion control\r
- 4.7. Hints and piece picking\r
+ 4.6. Data requests (HINTs)\r
+ 4.7. Subsetting of the protocol\r
+ 4.8. Directory lists\r
5. Enveloping\r
5.1. IP\r
5.2. UDP\r
5.3. TCP\r
6. Security Considerations\r
-7. Pending issues\r
-8. Normative References\r
+7. Extensibility\r
+References\r
Author's address\r
\r
\r
data | SunSITE CacheLogic VelociX BitTorrent\r
VoD | YouTube Azureus(+seedboxes) SwarmPlayer\r
live | Akamai Str. Octoshape, Joost PPlive\r
- TABLE 1. Usecases.\r
+ TABLE 1. Usecases.\r
\r
.fi\r
The protocol must be designed for maximum genericity, thus focusing on the very core of the mission, contain no magic constants and no hardwired policies. Effectively, it is a set of messages allowing to securely retrieve data from whatever source available, in parallel. The protocol must be able to run over IP as an independent transport protocol. For compatibility reasons, it must also run over UDP and TCP.\r
.ti 0\r
3. Design goals\r
\r
-.nf\r
-The technical focus of the swift protocol is to find the simplest\r
-solution involving the minimum set of primitives, still being\r
-sufficient to implement all the targeted usecases (see Table 1),\r
-suitable for use in general-purpose software and hardware (i.e. a\r
-web browser or a set-top box).\r
-The five design goals for the protocol are:\r
+.fi\r
+The technical focus of the swift protocol is to find the simplest solution involving the minimum set of primitives, still being sufficient to implement all the targeted usecases (see Table 1), suitable for use in general-purpose software and hardware (i.e. a web browser or a set-top box). The five design goals for 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. Pluggability/extensibility.\r
+5. Be extensible, allow for multitude of implementation over\r
+ diverse mediums, allow for drop-in pluggability.\r
\r
Later in the draft, the objectives are referenced as (1)-(5).\r
\r
-device, a browser or even in the kernel space. Thus, the protocol\r
-must have light footprint, preferably less than TCP, in spite\r
-the necessity to support numerous ongoing connections as well as to\r
-constantly probe the network for new possibilities. The practical\r
-overhead for TCP is estimated at 10KB per connection [HTTP1MLN]. We\r
-aim at <1KB per peer connected. Also, the amount of code necessary\r
-to make a basic implementation must be limited to 10KLoC of C.\r
-Otherwise, besides the resource considerations, maintaining and\r
-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 for\r
-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\r
-any unnecessary initialization roundtrips and warm-up cycles must be\r
-eliminated from the transport layer.\r
+.fi\r
+The goal of embedding (1) means that the protocol must be ready to function as a regular transport protocol inside a set-top box, mobile device, a browser and/or in the kernel space. Thus, the protocol must have light footprint, preferably less than TCP, in spite the necessity to support numerous ongoing connections as well as to constantly probe the network for new possibilities. The practical overhead for TCP is estimated at 10KB per connection [HTTP1MLN]. We aim at <1KB per peer connected. Also, the amount of code necessary to make a basic implementation must be limited to 10KLoC of C. Otherwise, besides the resource considerations, maintaining and auditing the code might become prohibitively expensive.\r
+\r
+The support for all three basic usecases of real-time streaming, \%in-order download and out-of-order download (2) is necessary for the manifested goal of THE multiparty transport protocol as no single usecase dominates over the others.\r
+\r
+The objective of short warm-up times (3) is the matter of end-user experience; the playback must start as soon as possible. Thus any unnecessary initialization roundtrips and warm-up cycles must be eliminated from the transport layer.\r
\r
.fi\r
Transparent NAT traversal (4) is absolutely necessary as at least 60% of today's users are hidden behind NATs. NATs severely affect connection patterns in P2P networks thus impacting performance and fairness [MOLNAT,LUCNAT].\r
.ti 0\r
4. swift subsystems and design choices\r
\r
-.nf\r
+.fi\r
To large extent, swift 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
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
- in-order delivery is not necessary, packet losses might be\r
+ 2. reliable delivery/retransmissions are less 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
+ situation is perfectly detected by the congestion control;\r
4. TCP congestion control is less useful as custom congestion\r
- control is often needed.\r
+ control is often needed [LEDBAT].\r
In general, TCP is built and optimized for a different usecase than\r
we have with swarmed downloads. The abstraction of a "data pipe"\r
orderly delivering some stream of bytes from one peer to another\r
that is convenient to them.\r
\r
.fi\r
-Thus, the choice is to design the protocol that runs on top of unreliable datagrams. Instead of reimplementing TCP we create a \%datagram-based protocol, completely dropping the sequential data stream abstraction. Ripping off unnecessary features of TCP makes it easier both to implement the protocol, and to check/verify it; e.g. numerous TCP vulnerabilities were caused by complexity of the protocol's state machine. Still, we reserve the possibility to run swift on top of TCP or HTTP. The draft itself assumes swift-over-UDP implementation; the necessary adjustments to run the protocol over IP or TCP a listed in Sec. 5.\r
+Thus, the choice is to design a protocol that runs on top of unreliable datagrams. Instead of reimplementing TCP, we create a \%datagram-based protocol, completely dropping the sequential data stream abstraction. Removing unnecessary features of TCP makes it easier both to implement the protocol and to verify it; numerous TCP vulnerabilities were caused by complexity of the protocol's state machine. Still, we reserve the possibility to run swift on top of TCP or HTTP. The draft itself assumes swift-over-UDP implementation; the necessary adjustments to run the protocol over IP or TCP are listed in Sec. 5.\r
\r
Pursuing the maxim of making things as simple as possible but not simpler, we fit the protocol into the constraints of the transport layer by dropping all the transmission's technical metadata except for the content's root hash (compare that to metadata files used in BitTorrent). Elimination of technical metadata is achieved through the use of Merkle [MERKLE,ABMRKL] hash trees, exclusively single-file transfers and other techniques. As a result, a transfer is identified and bootstrapped by its root hash only.\r
\r
-.nf\r
-To avoid the usual layering of positive/negative acknowledgment\r
-mechanisms we introduce a scale-invariant acknowledgment system (see\r
-Sec 4.4). The system allows for aggregation and variable level of\r
-detail in requesting, announcing and acknowledging data, serves\r
-\%in-order and out-of-order retrieval with equal ease.\r
-Besides the protocol's footprint, we also aim at lowering the size of\r
-a minimal useful interaction. Once a single datagram is received,\r
-it must be checked for data integrity, and then either dropped or\r
-accepted, consumed and relayed.\r
+.fi\r
+To avoid the usual layering of positive/negative acknowledgment mechanisms we introduce a scale-invariant acknowledgment system (see Sec 4.4). The system allows for aggregation and variable level of detail in requesting, announcing and acknowledging data, serves \%in-order and out-of-order retrieval with equal ease.\r
+Besides the protocol's footprint, we also aim at lowering the size of a minimal useful interaction. Once a single datagram is received, it must be checked for data integrity, and then either dropped or accepted, consumed and relayed.\r
\r
.ti 0\r
4.1. The atomic datagram principle\r
\r
.fi\r
-loss of one datagram MUST NOT disrupt the flow. Thus, a datagram carries zero or more messages, and neither messages nor message interdependencies should span over multiple datagrams. In particular, any data piece is verified using uncle hash chains; all hashes necessary for verifying data integrity are put into the same datagram as the data (Sec. 4.3). As a general rule, if some additional data is still missing to process a message within a datagram, the message SHOULD be dropped.\r
+Ideally, every datagram sent must be independent of other datagrams, so each datagram SHOULD be processed separately and a loss of one datagram MUST NOT disrupt the flow. Thus, a datagram carries zero or more messages, and neither messages nor message interdependencies should span over multiple datagrams. In particular, any data piece is verified using uncle hash chains; all hashes necessary for verifying data integrity are put into the same datagram as the data (Sec. 4.3). As a general rule, if some additional data is still missing to process a message within a datagram, the message SHOULD be dropped.\r
\r
+.fi\r
+Each datagram starts with four bytes corresponding to the receiving channel number (Sec. 4.2). The rest of a datagram is a concatenation of messages. Each message within a datagram has fixed length, depending on the type of the message. The first byte of a message denotes its type. Integers are serialized in the network \%(big-endian) byte order. Variable-length messages, free-form text or JSON/bencoded objects are not allowed.\r
+Consider an example of an acknowledgment message (Sec 4.4). It has message type of 2 and a payload of a four-byte integer (say, 1); it might be written in hex as: "02 00000001". Later in the document, a \%hex-like two char per byte notation is used to represent message formats.\r
+\r
+In case a datagram has a piece of data, a sender MUST always put the data message (type id 1) in the tail of a datagram. Such a message consists of type id, bin number (see Sec. 4.3) and the actual data. Normally there is 1 kilobyte of data, except the case when file size is not a multiple of 1024 bytes, so the tail packet is somewhat shorter. Example:\r
.nf\r
-Each datagram starts with four bytes corresponding to the receiving\r
-channel number (Sec. 4.2). The rest of a datagram is a\r
-concatenation of messages. Each message within a datagram has fixed\r
-length, depending on the type of the message. The first byte of a\r
-message denotes its type. Integers are serialized in the network\r
-\%(big-endian) byte order. Variable-length messages, free-form text\r
-or JSON/bencoded objects are not allowed.\r
-Consider an example of an acknowledgment message (Sec 4.4). It has\r
-message type of 2 and a payload of a four-byte integer (say, 1); it\r
-might be written in hex as: "02 00000001". Later in the document, a\r
-\%hex-like two char per byte notation is used to represent message\r
-formats.\r
-\r
-In case a datagram has a piece of data, a sender MUST always put\r
-the data message (type id 1) in the tail of a datagram. Such a\r
-message consists of type id, bin number (see Sec. 4.3) and the\r
-actual data. Normally there is 1 kilobyte of data, except the case\r
-when file size is not a multiple of 1024 bytes, so the tail packet\r
-is somewhat shorter. Example:\r
01 00000000 48656c6c6f20776f726c6421\r
(This message accommodates an entire file: "Hello world!")\r
\r
.ti 0\r
4.2. Handshake and multiplexing\r
\r
-For the sake of simplicity, one transfer always deals with one file\r
-only. Retrieval of large collections of files is done by retrieving\r
-a directory list file and then recursively retrieving files, which\r
-might also turn to be directory lists (see Sec. 4.9). To distinguish\r
-different transfers between the same pair of peers, the protocol\r
-introduces an additional layer of multiplexing, the channels.\r
-"Channels" loosely correspond to TCP connections; "content" of a\r
-single "channel" is a single file. A channel is established with a\r
-handshake. To start a handshake, the initiating peer needs to know\r
+.fi\r
+For the sake of simplicity, one transfer always deals with one file only. Retrieval of large collections of files is done by retrieving a directory list file and then recursively retrieving files, which might also turn to be directory lists (see Sec. 4.9). To distinguish different transfers between the same pair of peers, the protocol introduces an additional layer of multiplexing, the channels. "Channels" loosely correspond to TCP connections; "content" of a single "channel" is a single file. A channel is established with a handshake. To start a handshake, the initiating peer needs to know:\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. 4.5).\r
-The handshake is made by a HANDSHAKE message, whose only payload is\r
-a channel number. HANDSHAKE message type is 0. The initiating\r
-Initiator sends an initiating datagram to a peer:\r
+.fi\r
+The handshake is made by a HANDSHAKE message, whose only payload is a channel number. HANDSHAKE message type is 0. The initiating handshake must be followed by the transfer's root hash.\r
+\r
+The initiator sends first datagram to its peer:\r
+.nf\r
00000000 04 7FFFFFFF 1234123412341234123412341234123412341234\r
00 00000011\r
(to unknown channel, handshake from channel 0x11, initiating a\r
(peer to the initiator: use channel number 0x22 for this transfer;\r
I also have first 4 kilobytes of the file, see Sec. 4.3)\r
\r
-At this point, the initiator knows that the peer really responds;\r
-for that purpose channel ids MUST be random enough to prevent easy\r
-guessing. So, the third datagram of a handshake MAY already contain\r
-some heavy payload. To minimize the number of initialization\r
-roundtrips, the first two datagrams MAY also contain some minor\r
-payload, e.g. a couple of HAVE messages roughly indicating the\r
-current progress of a peer or a HINT (see Sec. 4.7).\r
+.fi\r
+At this point, the initiator knows that the peer really responds; for that purpose channel ids MUST be random enough to prevent easy guessing. So, the third datagram of a handshake MAY already contain some heavy payload. To minimize the number of initialization roundtrips, the first two datagrams MAY also contain some minor payload, e.g. a couple of HAVE messages roughly indicating the current progress of a peer or a HINT (see Sec. 4.7).\r
+.nf\r
00000022\r
(this is a simple zero-payload keepalive datagram consisting of\r
a 4-byte channel id only. At this point both peers have the\r
\r
1. The basic data unit is of course a byte of content in a file.\r
2. BitTorrent's highest-level unit is a "torrent", physically a\r
-2. A torrent is divided into "pieces", typically about a thousand\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 own progress to other\r
peers. Pieces are also basic data integrity units, as the torrent's\r
metadata includes SHA1 hash for every piece.\r
-3. The actual data transfers are requested and made in 16KByte\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
+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 a kilobyte), which TCP then reassembles into\r
To simplify this aspect, we employ a generic content addressing\r
scheme based on binary intervals (shortcutted "bins"). The base\r
interval is 1KB "packet", the top interval is the complete 2**63\r
-range. Till Sec. 4.4.1 any file is considered to be 2**k bytes long.\r
+range. Till Sec. 4.4.1, any file is considered to be 2**k bytes long.\r
The binary tree of intervals is simple, well-understood, correlates\r
well with machine representation of integers and the structure of\r
Merkle hashes (Sec. 4.4). A novel addition to the classical scheme\r
lays them out into a vector nicely. Bin numbering is done in the\r
order of interval's "center", ascending, namely:\r
\r
-.in 4\r
7\r
3 11\r
1 5 9 13\r
0 2 4 6 8 10 12 14\r
\r
-.in 3\r
-The number 0xFFFFFFFF (32-bit) or 0xFFFFFFFFFFFFFFFF (64-bit)\r
-stands for an empty interval; 0x7FFF...FFF stands for "everything".\r
-In general, this numbering system allows to work with\r
-simpler data structures, e.g. to use arrays instead of binary trees\r
-in many cases. As a minor convenience, it also allows to use one\r
-integer instead of two to denote an interval. By requiring every\r
-message to use bin numbers, we enforce genericity.\r
-\r
-Back to the acknowledgment message. A HAVE message (type 3) states\r
-that the sending peer obtained the specified bin and successfully\r
-checked its integrity:\r
+.fi\r
+The number 0xFFFFFFFF (32-bit) or 0xFFFFFFFFFFFFFFFF (64-bit) stands for an empty interval; 0x7FFF...FFF stands for "everything". In general, this numbering system allows to work with simpler data structures, e.g. to use arrays instead of binary trees in many cases. As a minor convenience, it also allows to use one integer instead of two to denote an interval. By requiring that every message uses bin numbers, we enforce genericity.\r
+\r
+Back to the acknowledgment message. A HAVE message (type 3) states that the sending peer obtained the specified bin and successfully checked its integrity:\r
+.nf\r
+02 00000003\r
(got/checked first four kilobytes of a file/stream)\r
\r
The data is acknowledged in terms of bins; as a result, every\r
.ti 0\r
4.4. Data integrity and on-demand Merkle hashes\r
\r
-The integrity checking scheme is unified for two usecases of\r
-download and streaming. Also, it works down to the level of a\r
-single datagram by employing Merkle hash trees [MERKLE]. Peers\r
-receive chains of uncle hashes just in time to check the incoming\r
-data. As metadata is restricted to just a single root hash,\r
-newcomer peers derive the size of a file from hashes. That\r
-functionalities heavily depend on the concept of peak hashes,\r
-discussed in Sec. 4.4.1. Any specifics related to the cases of file\r
-download and streaming is discussed in Sec. 4.4.2, 4.4.3\r
-respectively.\r
+.fi\r
+The integrity checking scheme is unified for two usecases of download and streaming. Also, it works down to the level of a single datagram by employing Merkle hash trees [MERKLE]. Peers receive chains of uncle hashes just in time to check the incoming data. As metadata is restricted to just a single root hash, newcomer peers derive the size of a file from hashes. That functionality heavily depends on the concept of peak hashes, discussed in Sec. 4.4.1. Any specifics related to the cases of file download and streaming is discussed in Sec. 4.4.2 and 4.4.3, respectively.\r
\r
Here, we discuss the common part of the workflow. As a general\r
rule, the sender SHOULD prepend data with hashes which are\r
uncle hash chain. Hence, to send bin 12 (i.e. the 7th kilobyte of\r
data), the sender needs to prepend hashes for bins 14 and 9, which\r
let the data be checked against hash 11 which is already known to\r
+the receiver.\r
+The sender MUST put into the datagram the chain of uncle hashes\r
+necessary for verification of the packet, always before the data\r
message itself, i.e.:\r
\r
+.nf\r
04 00000009 F01234567890ABCDEF1234567890ABCDEF123456\r
04 0000000E 01234567890ABCDEF1234567890ABCDEF1234567\r
(uncle hashes for the packet 12)\r
01 0000000C DA1ADA1ADA1A...\r
(packet 12 itself)\r
\r
-The sender MAY optimistically skip hashes which were sent out in\r
-previous (still unacknowledged) datagrams. It is an optimization\r
-tradeoff between redundant hash transmission and possibility of\r
-collateral data loss in the case some necessary hashes were lost in\r
-the network so some delivered data cannot be verified and thus\r
-has to be dropped.\r
-In either way, the receiver builds the Merkle tree on-demand,\r
-incrementally, starting from the root hash, and uses it for data\r
-validation.\r
+.fi\r
+The sender MAY optimistically skip hashes which were sent out in previous (still unacknowledged) datagrams.\r
+It is an optimization tradeoff between redundant hash transmission and possibility of collateral data loss in the case some necessary hashes were lost in the network so some delivered data cannot be verified and thus has to be dropped.\r
+In either case, the receiver builds the Merkle tree on-demand, incrementally, starting from the root hash, and uses it for data validation.\r
\r
\r
.ti 0\r
4.4.1. Peak hashes\r
\r
+.fi\r
The concept of peak hashes enables two cornerstone features of swift:\r
download/streaming unification and file size proving. Formally,\r
peak hashes are hashes defined over filled bins, whose parent\r
hashes are defined over incomplete (not filled) bins. Filled bin is\r
a bin which does not extend past the end of the file, or, more\r
-precisely, contains no empty packets. Practically, we use peak\r
-hashes to cover the data range with logarithmic number of hashes,\r
+precisely, contains no empty packets. Practically, we use peaks\r
+to cover the data range with logarithmic number of hashes,\r
so each hash is defined over a "round" aligned 2^k interval.\r
As an example, suppose a file is 7162 bytes long. That fits into\r
7 packets, the tail packet being 1018 bytes long. The binary\r
every "1" in binary representation of the file's packet length\r
corresponds to a peak hash. Namely, for this particular file we'll\r
have three peaks, bin numbers 3, 9, 12.\r
-Thus, once a newcomer joins a swarm, the first peer sending him\r
-data prepends it with peak hashes; the newcomer checks them against\r
+Thus, once a newcomer joins a swarm, the first peer who sends him\r
+data prepends it with peak hashes. The newcomer checks them against\r
the root hash (see Sec 4.4.2).\r
\r
+.nf\r
04 00000003 1234567890ABCDEF1234567890ABCDEF12345678\r
04 00000009 234567890ABCDEF1234567890ABCDEF123456789\r
04 0000000C 34567890ABCDEF1234567890ABCDEF1234567890\r
\r
the entire data range (2**63 bytes). Every hash in the tree is\r
defined in the usual way, as a SHA1 hash of a concatenation of two\r
-\%lower-level SHA1 hashes, corresponding to left and right data\r
+\%lower-level SHA1 hashes, which correspond to left and right data\r
\%half-ranges respectively. For example,\r
hash_1 = SHA1 (hash_0+hash_2)\r
where + stands for concatenation and hash_i stands for Merkle hash\r
of the bin number i. Obviously, that does not hold for the\r
-\%base-layer hashes, which are normal SHA1 hashes over 1KB data\r
+\%base-layer hashes. Those are normal SHA1 hashes over 1KB data\r
ranges ("packets"), except probably for the tail packet, which\r
might have less than 1KB of data. The normal recursive formula does\r
not apply to empty bins, i.e. bins that have no data absolutely;\r
.ti 0\r
4.4.3. Hash trees for streams\r
\r
-.nf\r
+.fi\r
In the case of live streaming a transfer is bootstrapped with a\r
public key instead of a root hash, as the root hash is undefined\r
or, more precisely, transient, as long as new data keeps coming.\r
-Stream/download unification is achieved by sending signed peak\r
+Streaming/download unification is achieved by sending signed peak\r
hashes on-demand, ahead of the actual data. Similarly to the\r
+previous case, the sender mightuse acknowledgements to derive which\r
+data range the receiver has peak hashes for and to prepend the data\r
hashes with the necessary (signed) peak hashes.\r
Except for the fact that the set of peak hashes changes with the\r
-time, other parts of the algorithm work as described in 4.4.2 As we\r
+time, other parts of the algorithm work as described in 4.4.2. As we\r
see, in both cases data length is not known on advance, but derived\r
\%on-the-go from the peak hashes. Suppose, our 7KB stream extended to\r
another kilobyte. Thus, now hash 7 becomes the only peak hash,\r
-eating hashes 3, 9 and 12, so the source sends out a signed peak hash\r
+eating hashes 3, 9 and 12. So, the source sends out a signed peak hash\r
message (type 7) to announce the fact:\r
\r
+.nf\r
07 00000007 1234567890ABCDEF1234567890ABCDEF12345678 SOME-SIGN-HERE\r
\r
\r
.ti 0\r
4.5. Peer exchange and NAT hole punching\r
\r
-Peer exchange messages are common for many peer-to-peer protocols.\r
-By exchanging peer IP addresses in gossip fashion, the central\r
-coordinating entities (trackers) might be relieved of unnecessary\r
-work. Following the example of BitTorrent, swift features two types\r
-of PEX messages: "peer connected" (type 5) and "peer disconnected"\r
-(type 6). Peers are represented as IPv4 address-port pairs:\r
+Peer exchange messages are common for many peer-to-peer protocols. By exchanging peer IP addresses in gossip fashion, peers relieve central coordinating entities (the trackers) from unnecessary work. Following the example of BitTorrent, swift features two types of PEX messages: "peer connected" (type 5) and "peer disconnected" (type 6). Peers are represented as IPv4 address-port pairs:\r
+.nf\r
05 7F000000 1F40\r
(connected to 127.0.0.1:8000)\r
\r
+.fi\r
To unify peer exchange and NAT hole punching functionality, the\r
sending pattern of PEX messages is restricted. As swift handshake\r
is able to do simple NAT hole punching [SNP] transparently, PEX\r
\r
\r
.ti 0\r
-4.6. Congestion control\r
+4.6. Data requests (HINTs)\r
\r
.fi\r
-swift employs pluggable congestion control. In general, it is expected that servers would use TCP-like congestion control schemes such as classic AIMD or CUBIC [CUBIC]. End-user peers are expected to use weaker-than-TCP (least than best effort) congestion control, such as [LEDBAT] to minimize seeding counter-incentives.\r
-\r
-\r
-.nf\r
While bulk download protocols normally do explicit requests for\r
certain ranges of data (e.g. BitTorrent's REQUEST message), live\r
streaming protocols quite often do without to save round trips.\r
also may send some other data in case it runs out of requests or\r
on some other reason. To emphasize that, request messages are named\r
HINTs; their only purpose is to coordinate peers and to avoid\r
-unnecessary data retransmission. A peer is supposed to process\r
+unnecessary data retransmission. A peer SHOULD to process\r
HINTs sequentially. HINT message type is 8.\r
+.nf\r
08 00000009\r
(a peer requests fifth and sixth packets)\r
\r
\r
.ti 0\r
-4.8. Subsetting of the protocol\r
+4.7. Subsetting of the protocol\r
\r
+.fi\r
As the same protocol is supposed to serve diverse usecases,\r
different peers may support different subsets of messages. The\r
supported subset SHOULD be signaled in the handshake packets.\r
\r
\r
.ti 0\r
-4.9. Directory lists\r
+4.8. Directory lists\r
\r
.fi\r
Directory list files MUST start with magic bytes ".\n..\n\n". The rest of the file is a newline-separated list of hashes and file names for the content of the directory. An example:\r
\r
.nf\r
-.\r
-..\r
+\&.\r
+\&..\r
1234567890ABCDEF1234567890ABCDEF12345678 readme.txt\r
01234567890ABCDEF1234567890ABCDEF1234567 big_file.dat\r
\r
5.1. IP\r
\r
.fi\r
-albeit it has downsides: first NAT/firewall compatibility problems, and second the necessity of in-kernel implementation on both ends.\r
+The most theoretically correct way is to run swift on top of IP, as another transport protocol like TCP or UDP. Albeit, that option has significant downsides. First, that is inevitable NAT/firewall compatibility problems. Second, that necessitates in-kernel implementation for all peers.\r
\r
\r
.ti 0\r
5.2. UDP\r
\r
.nf\r
-Currently, swift-over-UDP is the default deployment option.\r
-Effectively, UDP allows to use IP with minimal overhead, it also\r
-allows userspace implementations.\r
-Besides the classic 1KB packet scenario, the bin numbering allows\r
-to use swift over Jumbo frames/datagrams. Both data and\r
-acknowledgments may use e.g. 8KB packets instead of "standard"\r
-1KB. Hashing scheme stays the same.\r
-Using swift with 512 or 256-byte packets is theoretically possible\r
-with 64-bit byte-precise bin numbers, but IP fragmentation might be\r
-a better method to achieve the same result.\r
+Currently, swift-over-UDP is the default deployment option. Effectively, UDP allows to use IP with minimal overhead, it also allows userspace implementations.\r
+Besides the classic 1KB packet scenario, the bin numbering allows to use swift over Jumbo frames/datagrams. Both data and acknowledgments may use e.g. 8KB packets instead of "standard" 1KB. Hashing scheme stays the same.\r
+Using swift with 512 or 256-byte packets is theoretically possible with 64-bit byte-precise bin numbers, but IP fragmentation might be a better method to achieve the same result.\r
\r
\r
.ti 0\r
\r
.fi\r
Congestion control algorithm is left to the implementation and may even vary from peer to peer. Congestion control is entirely implemented by the sending peer, the receiver only provides clues, such as hints, acknowledgments and timestamps.\r
+In general, it is expected that servers would use TCP-like congestion control schemes such as classic AIMD or CUBIC [CUBIC]. End-user peers are expected to use weaker-than-TCP (least than best effort) congestion control, such as [LEDBAT] to minimize seeding counter-incentives.\r
\r
\r
.ti 0\r
.ti 0\r
7.6. Different crypto/hashing schemes\r
\r
-.nf\r
+.fi\r
Once a flavour 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
.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
\r
.in 3\r
Victor Grishchenko\r
-TU Delft\r
+TU Delft, EWI PDS\r
+Mekelweg 4, HB 9.240\r
+2628CD Delft\r
+The Netherlands\r
\r
Email: victor.grishchenko@gmail.com\r
\r
incompatible approaches to resolve that discrepancy above/below the\r
transport layer: peer-to-peer, CDN, caches, mirrors, multicast, etc.\r
The swift aims at creating a single unified content-centric transport\r
- protocol serving as a lingua-franca of content distribution.\r
- To implement that ultimate data cloud model, the protocol has to\r
- unify use cases of data download, video-on-demand and live streaming.\r
- It must work in the settings of client-server, peer-to-peer, CDN or\r
+ protocol serving as a lingua-franca of content distribution. To\r
+ implement that ultimate data cloud model, the protocol has to unify\r
+ use cases of data download, video-on-demand and live streaming. It\r
+ must work in the settings of client-server, peer-to-peer, CDN or\r
peer-assisted networks, effectively blending those architectures.\r
\r
\r
4. swift subsystems and design choices\r
4.1. The atomic datagram principle\r
4.2. Handshake and multiplexing\r
- 4.3. Data integrity and on-demand Merkle hashes\r
- 4.4. Generic acknowledgments\r
+ 4.3. Generic acknowledgments\r
+ 4.4. Data integrity and on-demand Merkle hashes\r
4.5. Peer exchange and NAT hole punching\r
- 4.6. Congestion control\r
- 4.7. Hints and piece picking\r
+ 4.6. Data requests (HINTs)\r
+ 4.7. Subsetting of the protocol\r
+ 4.8. Directory lists\r
5. Enveloping\r
5.1. IP\r
5.2. UDP\r
5.3. TCP\r
6. Security Considerations\r
- 7. Pending issues\r
- 8. Normative References\r
+ 7. Extensibility\r
+ References\r
Author's address\r
\r
\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
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\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
data | SunSITE CacheLogic VelociX BitTorrent\r
VoD | YouTube Azureus(+seedboxes) SwarmPlayer\r
live | Akamai Str. Octoshape, Joost PPlive\r
- TABLE 1. Usecases.\r
+ TABLE 1. Usecases.\r
\r
The protocol must be designed for maximum genericity, thus focusing\r
on the very core of the mission, contain no magic constants and no\r
The technical focus of the swift protocol is to find the simplest\r
solution involving the minimum set of primitives, still being\r
sufficient to implement all the targeted usecases (see Table 1),\r
- suitable for use in general-purpose software and hardware (i.e. a\r
- web browser or a set-top box).\r
- The five design goals for the protocol are:\r
+ suitable for use in general-purpose software and hardware (i.e. a web\r
+ browser or a set-top box). The five design goals for the protocol\r
+ are:\r
\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. Pluggability/extensibility.\r
+ 5. Be extensible, allow for multitude of implementation over\r
+ diverse mediums, allow for drop-in pluggability.\r
\r
Later in the draft, the objectives are referenced as (1)-(5).\r
\r
- device, a browser or even in the kernel space. Thus, the protocol\r
- must have light footprint, preferably less than TCP, in spite\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
- the necessity to support numerous ongoing connections as well as to\r
+ The goal of embedding (1) means that the protocol must be ready to\r
+ function as a regular transport protocol inside a set-top box, mobile\r
+ device, a browser and/or in the kernel space. Thus, the protocol must\r
+ have light footprint, preferably less than TCP, in spite the\r
+ necessity to support numerous ongoing connections as well as to\r
constantly probe the network for new possibilities. The practical\r
overhead for TCP is estimated at 10KB per connection [HTTP1MLN]. We\r
- aim at <1KB per peer connected. Also, the amount of code necessary\r
- to make a basic implementation must be limited to 10KLoC of C.\r
+ aim at <1KB per peer connected. Also, the amount of code necessary to\r
+ make a basic implementation must be limited to 10KLoC of C.\r
Otherwise, besides the resource considerations, maintaining and\r
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 for\r
- the manifested goal of THE multiparty transport protocol as no\r
- single usecase dominates over the others.\r
+ in-order download and out-of-order download (2) is necessary for the\r
+ manifested goal of THE multiparty transport protocol as no single\r
+ 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\r
- any unnecessary initialization roundtrips and warm-up cycles must be\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
Transparent NAT traversal (4) is absolutely necessary as at least 60%\r
4. swift subsystems and design choices\r
\r
To large extent, swift 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
+ to get rid of TCP and not to reinvent any TCP-like transports on top\r
+ of UDP or otherwise. The requirements (1), (4), (5) make TCP a bad\r
+ choice due to its high per-connection footprint, complex and less\r
+ reliable NAT traversal and fixed predefined congestion control\r
+ algorithms. Besides that, an important consideration is that no block\r
+ of TCP functionality turns out to be useful for the general case of\r
+ swarming downloads. Namely,\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
- in-order delivery is not necessary, packet losses might be\r
- patched up lazily, without stopping the flow of data;\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\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 less 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
+ situation is perfectly detected by the congestion control;\r
4. TCP congestion control is less useful as custom congestion\r
- control is often needed.\r
+ control is often needed [LEDBAT].\r
In general, TCP is built and optimized for a different usecase than\r
we have with swarmed downloads. The abstraction of a "data pipe"\r
orderly delivering some stream of bytes from one peer to another\r
of participants disseminating the same _data_ in any way and order\r
that is convenient to them.\r
\r
- Thus, the choice is to design the protocol that runs on top of\r
- unreliable datagrams. Instead of reimplementing TCP we create a\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. Ripping off unnecessary features of TCP makes it\r
- easier both to implement the protocol, and to check/verify it; e.g.\r
- numerous TCP vulnerabilities were caused by complexity of the\r
- protocol's state machine. Still, we reserve the possibility to run\r
- swift on top of TCP or HTTP. The draft itself assumes swift-over-UDP\r
- implementation; the necessary adjustments to run the protocol over IP\r
- or TCP a listed in Sec. 5.\r
+ stream abstraction. Removing unnecessary features of TCP makes it\r
+ easier both to implement the protocol and to verify it; numerous TCP\r
+ vulnerabilities were caused by complexity of the protocol's state\r
+ machine. Still, we reserve the possibility to run swift on top of TCP\r
+ or HTTP. The draft itself assumes swift-over-UDP implementation; the\r
+ necessary adjustments to run the protocol over IP or TCP are listed\r
+ in Sec. 5.\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
mechanisms we introduce a scale-invariant acknowledgment system (see\r
Sec 4.4). The system allows for aggregation and variable level of\r
detail in requesting, announcing and acknowledging data, serves\r
- in-order and out-of-order retrieval with equal ease.\r
- Besides the protocol's footprint, we also aim at lowering the size of\r
- a minimal useful interaction. Once a single datagram is received,\r
- it must be checked for data integrity, and then either dropped or\r
- accepted, consumed and relayed.\r
-\r
-4.1. The atomic datagram principle\r
-\r
- loss of one datagram MUST NOT disrupt the flow. Thus, a datagram\r
- carries zero or more messages, and neither messages nor message\r
+ in-order and out-of-order retrieval with equal ease. Besides the\r
+ protocol's footprint, we also aim at lowering the size of a minimal\r
+ useful interaction. Once a single datagram is received, it must be\r
+ checked for data integrity, and then either dropped or accepted,\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
- interdependencies should span over multiple datagrams. In particular,\r
- any data piece is verified using uncle hash chains; all hashes\r
- necessary for verifying data integrity are put into the same datagram\r
- as the data (Sec. 4.3). As a general rule, if some additional data is\r
- still missing to process a message within a datagram, the message\r
- SHOULD be dropped.\r
+ consumed and relayed.\r
+\r
+4.1. The atomic datagram principle\r
+\r
+ Ideally, every datagram sent must be independent of other datagrams,\r
+ so each datagram SHOULD be processed separately and a loss of one\r
+ datagram MUST NOT disrupt the flow. Thus, a datagram carries zero or\r
+ more messages, and neither messages nor message interdependencies\r
+ should span over multiple datagrams. In particular, any data piece is\r
+ verified using uncle hash chains; all hashes necessary for verifying\r
+ data integrity are put into the same datagram as the data (Sec. 4.3).\r
+ As a general rule, if some additional data is still missing to\r
+ process a message within a datagram, the message SHOULD be dropped.\r
\r
Each datagram starts with four bytes corresponding to the receiving\r
- channel number (Sec. 4.2). The rest of a datagram is a\r
- concatenation of messages. Each message within a datagram has fixed\r
- length, depending on the type of the message. The first byte of a\r
- message denotes its type. Integers are serialized in the network\r
- (big-endian) byte order. Variable-length messages, free-form text\r
- or JSON/bencoded objects are not allowed.\r
- Consider an example of an acknowledgment message (Sec 4.4). It has\r
- message type of 2 and a payload of a four-byte integer (say, 1); it\r
- might be written in hex as: "02 00000001". Later in the document, a\r
- hex-like two char per byte notation is used to represent message\r
- formats.\r
-\r
- In case a datagram has a piece of data, a sender MUST always put\r
- the data message (type id 1) in the tail of a datagram. Such a\r
- message consists of type id, bin number (see Sec. 4.3) and the\r
- actual data. Normally there is 1 kilobyte of data, except the case\r
- when file size is not a multiple of 1024 bytes, so the tail packet\r
- is somewhat shorter. Example:\r
+ channel number (Sec. 4.2). The rest of a datagram is a concatenation\r
+ of messages. Each message within a datagram has fixed length,\r
+ depending on the type of the message. The first byte of a message\r
+ denotes its type. Integers are serialized in the network (big-endian)\r
+ byte order. Variable-length messages, free-form text or JSON/bencoded\r
+ objects are not allowed. Consider an example of an acknowledgment\r
+ message (Sec 4.4). It has message type of 2 and a payload of a four-\r
+ byte integer (say, 1); it might be written in hex as: "02 00000001".\r
+ Later in the document, a hex-like two char per byte notation is used\r
+ to represent message formats.\r
+\r
+ In case a datagram has a piece of data, a sender MUST always put the\r
+ data message (type id 1) in the tail of a datagram. Such a message\r
+ consists of type id, bin number (see Sec. 4.3) and the actual data.\r
+ Normally there is 1 kilobyte of data, except the case when file size\r
+ is not a multiple of 1024 bytes, so the tail packet is somewhat\r
+ shorter. Example:\r
01 00000000 48656c6c6f20776f726c6421\r
(This message accommodates an entire file: "Hello world!")\r
\r
4.2. Handshake and multiplexing\r
\r
For the sake of simplicity, one transfer always deals with one file\r
- only. Retrieval of large collections of files is done by retrieving\r
- a directory list file and then recursively retrieving files, which\r
+ only. Retrieval of large collections of files is done by retrieving a\r
+ directory list file and then recursively retrieving files, which\r
might also turn to be directory lists (see Sec. 4.9). To distinguish\r
different transfers between the same pair of peers, the protocol\r
introduces an additional layer of multiplexing, the channels.\r
"Channels" loosely correspond to TCP connections; "content" of a\r
single "channel" is a single file. A channel is established with a\r
- handshake. To start a handshake, the initiating peer needs to know\r
+ handshake. To start a handshake, the initiating peer needs to know:\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. 4.5).\r
- The handshake is made by a HANDSHAKE message, whose only payload is\r
- a channel number. HANDSHAKE message type is 0. The initiating\r
- Initiator sends an initiating datagram to a peer:\r
- 00000000 04 7FFFFFFF 1234123412341234123412341234123412341234\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
+ (2) peer's UDP port and\r
+ (3) the root hash of the content (see Sec. 4.5).\r
+ The handshake is made by a HANDSHAKE message, whose only payload is a\r
+ channel number. HANDSHAKE message type is 0. The initiating handshake\r
+ must be followed by the transfer's root hash.\r
+\r
+ The initiator sends first datagram to its peer:\r
+ 00000000 04 7FFFFFFF 1234123412341234123412341234123412341234\r
00 00000011\r
(to unknown channel, handshake from channel 0x11, initiating a\r
transfer of a file with a root hash 123...1234)\r
(peer to the initiator: use channel number 0x22 for this transfer;\r
I also have first 4 kilobytes of the file, see Sec. 4.3)\r
\r
- At this point, the initiator knows that the peer really responds;\r
- for that purpose channel ids MUST be random enough to prevent easy\r
+ At this point, the initiator knows that the peer really responds; for\r
+ that purpose channel ids MUST be random enough to prevent easy\r
guessing. So, the third datagram of a handshake MAY already contain\r
some heavy payload. To minimize the number of initialization\r
roundtrips, the first two datagrams MAY also contain some minor\r
\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 BitTorrent+TCP tandem for example:\r
-\r
- 1. The basic data unit is of course a byte of content in a file.\r
- 2. BitTorrent's highest-level unit is a "torrent", physically a\r
- 2. A torrent is divided into "pieces", typically about a thousand\r
- of them. Pieces are used to communicate own progress to other\r
- peers. Pieces are also basic data integrity units, as the torrent's\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
+ to become overly complex and multilayered with the conventional\r
+ approach. Take BitTorrent+TCP tandem for example:\r
+\r
+ 1. The basic data unit is of course 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 own progress to other\r
+ peers. Pieces are also basic data integrity units, as the torrent's\r
metadata includes SHA1 hash for every piece.\r
- 3. The actual data transfers are requested and made in 16KByte\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
+ 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 a kilobyte), which TCP then reassembles into\r
To simplify this aspect, we employ a generic content addressing\r
scheme based on binary intervals (shortcutted "bins"). The base\r
interval is 1KB "packet", the top interval is the complete 2**63\r
- range. Till Sec. 4.4.1 any file is considered to be 2**k bytes long.\r
+ range. Till Sec. 4.4.1, any file is considered to be 2**k bytes long.\r
The binary tree of intervals is simple, well-understood, correlates\r
well with machine representation of integers and the structure of\r
Merkle hashes (Sec. 4.4). A novel addition to the classical scheme\r
lays them out into a vector nicely. Bin numbering is done in the\r
order of interval's "center", ascending, namely:\r
\r
- 7\r
- 3 11\r
- 1 5 9 13\r
- 0 2 4 6 8 10 12 14\r
-\r
- The number 0xFFFFFFFF (32-bit) or 0xFFFFFFFFFFFFFFFF (64-bit)\r
- stands for an empty interval; 0x7FFF...FFF stands for "everything".\r
- In general, this numbering system allows to work with\r
- simpler data structures, e.g. to use arrays instead of binary trees\r
- in many cases. As a minor convenience, it also allows to use one\r
- integer instead of two to denote an interval. By requiring every\r
- message to use bin numbers, we enforce genericity.\r
-\r
- Back to the acknowledgment message. A HAVE message (type 3) states\r
- that the sending peer obtained the specified bin and successfully\r
- checked its integrity:\r
- (got/checked first four kilobytes of a file/stream)\r
+ 7\r
+ 3 11\r
+ 1 5 9 13\r
+ 0 2 4 6 8 10 12 14\r
\r
- The data is acknowledged in terms of bins; as a result, every\r
+ The number 0xFFFFFFFF (32-bit) or 0xFFFFFFFFFFFFFFFF (64-bit) stands\r
+ for an empty interval; 0x7FFF...FFF stands for "everything". In\r
+ general, this numbering system allows to work with simpler data\r
+ structures, e.g. to use arrays instead of binary trees in many cases.\r
+ As a minor convenience, it also allows to use one integer instead of\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
+ two to denote an interval. By requiring that every message uses bin\r
+ numbers, we enforce genericity.\r
+\r
+ Back to the acknowledgment message. A HAVE message (type 3) states\r
+ that the sending peer obtained the specified bin and successfully\r
+ checked its integrity:\r
+ 02 00000003\r
+ (got/checked first four kilobytes of a file/stream)\r
+\r
+ The data is acknowledged in terms of bins; as a result, every\r
single packet is acknowledged logarithmic number of times. That\r
provides some necessary redundancy of acknowledgments and\r
sufficiently compensates unreliability of datagrams. Compare that\r
\r
4.4. Data integrity and on-demand Merkle hashes\r
\r
- The integrity checking scheme is unified for two usecases of\r
- download and streaming. Also, it works down to the level of a\r
- single datagram by employing Merkle hash trees [MERKLE]. Peers\r
- receive chains of uncle hashes just in time to check the incoming\r
- data. As metadata is restricted to just a single root hash,\r
- newcomer peers derive the size of a file from hashes. That\r
- functionalities heavily depend on the concept of peak hashes,\r
- discussed in Sec. 4.4.1. Any specifics related to the cases of file\r
- download and streaming is discussed in Sec. 4.4.2, 4.4.3\r
- respectively.\r
-\r
- Here, we discuss the common part of the workflow. As a general\r
- rule, the sender SHOULD prepend data with hashes which are\r
- necessary for verifying that data, no more, no less. While some\r
- optimistic optimizations are definitely possible, the receiver\r
- SHOULD drop data if it is impossible to verify it. Before sending a\r
- packet of data to the receiver, the sender inspects the receiver's\r
- previous acknowledgments to derive which hashes the receiver\r
- already has for sure.\r
- Suppose, the receiver had acknowledged bin 1 (first two kilobytes\r
- of the file), then it must already have uncle hashes 5, 11 and so\r
- 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\r
- also known as they are calculated in the process of checking the\r
- uncle hash chain. Hence, to send bin 12 (i.e. the 7th kilobyte of\r
- data), the sender needs to prepend hashes for bins 14 and 9, which\r
- let the data be checked against hash 11 which is already known to\r
- message itself, i.e.:\r
-\r
- 04 00000009 F01234567890ABCDEF1234567890ABCDEF123456\r
+ The integrity checking scheme is unified for two usecases of download\r
+ and streaming. Also, it works down to the level of a single datagram\r
+ by employing Merkle hash trees [MERKLE]. Peers receive chains of\r
+ uncle hashes just in time to check the incoming data. As metadata is\r
+ restricted to just a single root hash, newcomer peers derive the size\r
+ of a file from hashes. That functionality heavily depends on the\r
+ concept of peak hashes, discussed in Sec. 4.4.1. Any specifics\r
+ related to the cases of file download and streaming is discussed in\r
+ Sec. 4.4.2 and 4.4.3, respectively.\r
+\r
+ Here, we discuss the common part of the workflow. As a general rule,\r
+ the sender SHOULD prepend data with hashes which are necessary for\r
+ verifying that data, no more, no less. While some optimistic\r
+ optimizations are definitely possible, the receiver SHOULD drop data\r
+ if it is impossible to verify it. Before sending a packet of data to\r
+ the receiver, the sender inspects the receiver's previous\r
+ acknowledgments to derive which hashes the receiver already has for\r
+ sure. Suppose, the receiver had acknowledged bin 1 (first two\r
+ kilobytes of the file), then it must already have uncle hashes 5, 11\r
+ and so on. That is because those hashes are necessary to check\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
+ packets of bin 1 against the root hash. Then, hashes 3, 7 and so on\r
+ must be also known as they are calculated in the process of checking\r
+ the uncle hash chain. Hence, to send bin 12 (i.e. the 7th kilobyte of\r
+ data), the sender needs to prepend hashes for bins 14 and 9, which\r
+ let the data be checked against hash 11 which is already known to the\r
+ receiver. The sender MUST put into the datagram the chain of uncle\r
+ hashes necessary for verification of the packet, always before the\r
+ data message itself, i.e.:\r
+\r
+ 04 00000009 F01234567890ABCDEF1234567890ABCDEF123456\r
04 0000000E 01234567890ABCDEF1234567890ABCDEF1234567\r
(uncle hashes for the packet 12)\r
01 0000000C DA1ADA1ADA1A...\r
previous (still unacknowledged) datagrams. It is an optimization\r
tradeoff between redundant hash transmission and possibility of\r
collateral data loss in the case some necessary hashes were lost in\r
- the network so some delivered data cannot be verified and thus\r
- has to be dropped.\r
- In either way, the receiver builds the Merkle tree on-demand,\r
- incrementally, starting from the root hash, and uses it for data\r
- validation.\r
+ the network so some delivered data cannot be verified and thus has to\r
+ be dropped. In either case, the receiver builds the Merkle tree on-\r
+ demand, incrementally, starting from the root hash, and uses it for\r
+ data validation.\r
\r
\r
4.4.1. Peak hashes\r
\r
The concept of peak hashes enables two cornerstone features of swift:\r
- download/streaming unification and file size proving. Formally,\r
- peak hashes are hashes defined over filled bins, whose parent\r
- hashes are defined over incomplete (not filled) bins. Filled bin is\r
- a bin which does not extend past the end of the file, or, more\r
- precisely, contains no empty packets. Practically, we use peak\r
- hashes to cover the data range with logarithmic number of hashes,\r
- so each hash is defined over a "round" aligned 2^k interval.\r
- As an example, suppose a file is 7162 bytes long. That fits into\r
- 7 packets, the tail packet being 1018 bytes long. The binary\r
- representation for 7 is 111. Here we might note that in general,\r
- every "1" in binary representation of the file's packet length\r
- corresponds to a peak hash. Namely, for this particular file we'll\r
- have three peaks, bin numbers 3, 9, 12.\r
- Thus, once a newcomer joins a swarm, the first peer sending him\r
- data prepends it with peak hashes; the newcomer checks them against\r
- the root hash (see Sec 4.4.2).\r
+ download/streaming unification and file size proving. Formally, peak\r
+ hashes are hashes defined over filled bins, whose parent hashes are\r
+ defined over incomplete (not filled) bins. Filled bin is a bin which\r
+ does not extend past the end of the file, or, more precisely,\r
+ contains no empty packets. Practically, we use peaks to cover the\r
+ data range with logarithmic number of hashes, so each hash is defined\r
+ over a "round" aligned 2^k interval. As an example, suppose a file is\r
+ 7162 bytes long. That fits into 7 packets, the tail packet being 1018\r
+ bytes long. The binary representation for 7 is 111. Here we might\r
+ note that in general, every "1" in binary representation of the\r
+ file's packet length corresponds to a peak hash. Namely, for this\r
+ particular file we'll have three peaks, bin numbers 3, 9, 12. Thus,\r
+ once a newcomer joins a swarm, the first peer who sends him data\r
+ prepends it with peak hashes. The newcomer checks them against the\r
+ root hash (see Sec 4.4.2).\r
\r
04 00000003 1234567890ABCDEF1234567890ABCDEF12345678\r
04 00000009 234567890ABCDEF1234567890ABCDEF123456789\r
04 0000000C 34567890ABCDEF1234567890ABCDEF1234567890\r
(this sequence of peak hashes proves that a file is 7KB long)\r
-\r
-\r
-4.4.2. Hash trees for files\r
-\r
- the entire data range (2**63 bytes). Every hash in the tree is\r
- defined in the usual way, as a SHA1 hash of a concatenation of two\r
- lower-level SHA1 hashes, corresponding to left and right data\r
- half-ranges respectively. For example,\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
+4.4.2. Hash trees for files\r
+\r
+ the entire data range (2**63 bytes). Every hash in the tree is\r
+ defined in the usual way, as a SHA1 hash of a concatenation of two\r
+ lower-level SHA1 hashes, which correspond to left and right data\r
+ half-ranges respectively. For example,\r
hash_1 = SHA1 (hash_0+hash_2)\r
where + stands for concatenation and hash_i stands for Merkle hash\r
of the bin number i. Obviously, that does not hold for the\r
- base-layer hashes, which are normal SHA1 hashes over 1KB data\r
+ base-layer hashes. Those are normal SHA1 hashes over 1KB data\r
ranges ("packets"), except probably for the tail packet, which\r
might have less than 1KB of data. The normal recursive formula does\r
not apply to empty bins, i.e. bins that have no data absolutely;\r
4.4.3. Hash trees for streams\r
\r
In the case of live streaming a transfer is bootstrapped with a\r
- public key instead of a root hash, as the root hash is undefined\r
- or, more precisely, transient, as long as new data keeps coming.\r
- Stream/download unification is achieved by sending signed peak\r
- hashes on-demand, ahead of the actual data. Similarly to the\r
- hashes with the necessary (signed) peak hashes.\r
- Except for the fact that the set of peak hashes changes with the\r
- time, other parts of the algorithm work as described in 4.4.2 As we\r
- see, in both cases data length is not known on advance, but derived\r
+ public key instead of a root hash, as the root hash is undefined or,\r
+ more precisely, transient, as long as new data keeps coming.\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
- on-the-go from the peak hashes. Suppose, our 7KB stream extended to\r
- another kilobyte. Thus, now hash 7 becomes the only peak hash,\r
- eating hashes 3, 9 and 12, so the source sends out a signed peak hash\r
- message (type 7) to announce the fact:\r
+ Streaming/download unification is achieved by sending signed peak\r
+ hashes on-demand, ahead of the actual data. Similarly to the previous\r
+ case, the sender mightuse acknowledgements to derive which data range\r
+ the receiver has peak hashes for and to prepend the data hashes with\r
+ the necessary (signed) peak hashes. Except for the fact that the set\r
+ of peak hashes changes with the time, other parts of the algorithm\r
+ work as described in 4.4.2. As we see, in both cases data length is\r
+ not known on advance, but derived on-the-go from the peak hashes.\r
+ Suppose, our 7KB stream extended to another kilobyte. Thus, now hash\r
+ 7 becomes the only peak hash, eating hashes 3, 9 and 12. So, the\r
+ source sends out a signed peak hash message (type 7) to announce the\r
+ fact:\r
\r
07 00000007 1234567890ABCDEF1234567890ABCDEF12345678 SOME-SIGN-HERE\r
\r
\r
4.5. Peer exchange and NAT hole punching\r
\r
- Peer exchange messages are common for many peer-to-peer protocols.\r
- By exchanging peer IP addresses in gossip fashion, the central\r
- coordinating entities (trackers) might be relieved of unnecessary\r
- work. Following the example of BitTorrent, swift features two types\r
- of PEX messages: "peer connected" (type 5) and "peer disconnected"\r
- (type 6). Peers are represented as IPv4 address-port pairs:\r
+ Peer exchange messages are common for many peer-to-peer protocols. By exchanging peer IP addresses in gossip fashion, peers relieve central coordinating entities (the trackers) from unnecessary work. Following the example of BitTorrent, swift features two types of PEX messages: "peer connected" (type 5) and "peer disconnected" (type 6). Peers are represented as IPv4 address-port pairs:\r
05 7F000000 1F40\r
(connected to 127.0.0.1:8000)\r
\r
To unify peer exchange and NAT hole punching functionality, the\r
- sending pattern of PEX messages is restricted. As 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 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 and better not be\r
- simultaneous, 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. 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
-\r
-4.6. Congestion control\r
-\r
- swift employs pluggable congestion control. In general, it is\r
- expected that servers would use TCP-like congestion control schemes\r
- such as classic AIMD or CUBIC [CUBIC]. End-user peers are expected to\r
- use weaker-than-TCP (least than best effort) congestion control, such\r
- as [LEDBAT] to minimize seeding counter-incentives.\r
-\r
+ sending pattern of PEX messages is restricted. As swift handshake is\r
+ able to do simple NAT hole punching [SNP] transparently, PEX messages\r
+ must be emitted in the way to facilitate that. Namely, once peer A\r
+ introduces peer B to peer C by sending a PEX message to C, it SHOULD\r
+ also send a message to B introducing C. The messages SHOULD be within\r
+ 2 seconds from each other, but MAY and better not be simultaneous,\r
+ leaving a gap of twice the "typical" RTT, i.e. 300-600ms. The peers\r
+ are supposed to initiate handshakes to each other thus forming a\r
+ simple NAT hole punching pattern where the introducing peer\r
+ effectively acts as a STUN server. Still, peers MAY ignore PEX\r
+ messages if uninterested in obtaining new peers or because of\r
+ security considerations (rate limiting) or any other reason.\r
+\r
+\r
+4.6. Data requests (HINTs)\r
\r
While bulk download protocols normally do explicit requests for\r
certain ranges of data (e.g. BitTorrent's REQUEST message), live\r
streaming protocols quite often do without to save round trips.\r
Explicit requests are often needed for security purposes; consider\r
+ that BitTorrent can only verify hashes of complete pieces that might\r
+ consist of multiple blocks requested from many peers. As swift has no\r
+ such implications, it is supposed to work both ways. Namely, a peer\r
+ SHOULD send out requested pieces, while it also may send some other\r
+ data in case it runs out of requests or on some other reason. To\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
- that BitTorrent can only verify hashes of complete pieces that\r
- might consist of multiple blocks requested from many peers.\r
- As swift has no such implications, it is supposed to work both\r
- ways. Namely, a peer SHOULD send out requested pieces, while it\r
- also may send some other data in case it runs out of requests or\r
- on some other reason. To emphasize that, request messages are named\r
- HINTs; their only purpose is to coordinate peers and to avoid\r
- unnecessary data retransmission. A peer is supposed to process\r
- HINTs sequentially. HINT message type is 8.\r
+ emphasize that, request messages are named HINTs; their only purpose\r
+ is to coordinate peers and to avoid unnecessary data retransmission.\r
+ A peer SHOULD to process HINTs sequentially. HINT message type is 8.\r
08 00000009\r
(a peer requests fifth and sixth packets)\r
\r
\r
-4.8. Subsetting of the protocol\r
+4.7. Subsetting of the protocol\r
\r
- As the same protocol is supposed to serve diverse usecases,\r
- different peers may support different subsets of messages. The\r
- supported subset SHOULD be signaled in the handshake packets.\r
- The SWIFT_MSGTYPE_RCVD message (type 9) serves exactly this\r
- purpose. It contains a 32-bit big-endian number with bits set\r
- to 1 at offsets corresponding to supported message type ids.\r
- E.g. for a tracker peer which receives only handshakes and\r
- (root) hashes, sends out handshakes and PEX_ADD messages, that\r
- message will look like:\r
- 09 00000011\r
- Peers running over TCP may not accept ACK messages, etc etc.\r
+ As the same protocol is supposed to serve diverse usecases, different\r
+ peers may support different subsets of messages. The supported subset\r
+ SHOULD be signaled in the handshake packets. The SWIFT_MSGTYPE_RCVD\r
+ message (type 9) serves exactly this purpose. It contains a 32-bit\r
+ big-endian number with bits set to 1 at offsets corresponding to\r
+ supported message type ids. E.g. for a tracker peer which receives\r
+ only handshakes and (root) hashes, sends out handshakes and PEX_ADD\r
+ messages, that message will look like: 09 00000011 Peers running over\r
+ TCP may not accept ACK messages, etc etc.\r
\r
\r
-4.9. Directory lists\r
+4.8. Directory lists\r
\r
Directory list files MUST start with magic bytes ".\n..\n\n". The\r
rest of the file is a newline-separated list of hashes and file names\r
for the content of the directory. An example:\r
\r
+ .\r
+ ..\r
1234567890ABCDEF1234567890ABCDEF12345678 readme.txt\r
01234567890ABCDEF1234567890ABCDEF1234567 big_file.dat\r
\r
\r
5.1. IP\r
\r
- albeit it has downsides: first NAT/firewall compatibility problems,\r
- and second the necessity of in-kernel implementation on both ends.\r
+ The most theoretically correct way is to run swift on top of IP, as\r
+ another transport protocol like TCP or UDP. Albeit, that option has\r
+ significant downsides. First, that is inevitable NAT/firewall\r
+ compatibility problems. Second, that necessitates in-kernel\r
+ implementation for all peers.\r
\r
\r
5.2. UDP\r
\r
+ Currently, swift-over-UDP is the default deployment option. Effectively, UDP allows to use IP with minimal overhead, it also allows userspace implementations.\r
+ Besides the classic 1KB packet scenario, the bin numbering allows to use swift over Jumbo frames/datagrams. Both data and acknowledgments may use e.g. 8KB packets instead of "standard" 1KB. Hashing scheme stays the same.\r
+ Using swift with 512 or 256-byte packets is theoretically possible with 64-bit byte-precise bin numbers, but IP fragmentation might be a better method to achieve the same result.\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\r
- Currently, swift-over-UDP is the default deployment option.\r
- Effectively, UDP allows to use IP with minimal overhead, it also\r
- allows userspace implementations.\r
- Besides the classic 1KB packet scenario, the bin numbering allows\r
- to use swift over Jumbo frames/datagrams. Both data and\r
- acknowledgments may use e.g. 8KB packets instead of "standard"\r
- 1KB. Hashing scheme stays the same.\r
- Using swift with 512 or 256-byte packets is theoretically possible\r
- with 64-bit byte-precise bin numbers, but IP fragmentation might be\r
- a better method to achieve the same result.\r
-\r
-\r
5.3. TCP\r
\r
If ran over TCP, the swift becomes functionally equivalent to\r
\r
\r
\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
+\r
\r
\r
\r
Congestion control algorithm is left to the implementation and may\r
even vary from peer to peer. Congestion control is entirely\r
implemented by the sending peer, the receiver only provides clues,\r
- such as hints, acknowledgments and timestamps.\r
+ such as hints, acknowledgments and timestamps. In general, it is\r
+ expected that servers would use TCP-like congestion control schemes\r
+ such as classic AIMD or CUBIC [CUBIC]. End-user peers are expected to\r
+ use weaker-than-TCP (least than best effort) congestion control, such\r
+ as [LEDBAT] to minimize seeding counter-incentives.\r
\r
\r
7.4. Piece picking algorithms\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
+ content's identifier, different schemes of crypto cannot be mixed in\r
+ the same swarm; different swarms may distribute the same content\r
using different crypto.\r
\r
\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
-[LUCNAT] submitted\r
\r
\r
\r
Internet-Draft swift April 2010\r
\r
\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
+[LUCNAT] submitted\r
[BINMAP] V. Grishchenko, J. Pouwelse: "Binmaps: hybridizing bitmaps\r
and binary trees" http://bouillon.math.usu.ru/articles/\r
binmaps-alenex.pdf\r
Author's address\r
\r
Victor Grishchenko\r
- TU Delft\r
+ TU Delft, EWI PDS\r
+ Mekelweg 4, HB 9.240\r
+ 2628CD Delft\r
+ The Netherlands\r
\r
Email: victor.grishchenko@gmail.com\r
\r
\r
\r
\r
-\r
-\r
-\r
-\r
-\r
-\r
-\r
\r
\r
\r
projects / swift-upb.git / commitdiff