Monday, May 6, 2013

Fig. 1. BitTorrent Live (source: http://live.bittorrent.com/)
During the last decade, we have seen several interesting peer-to-peer (P2P) file sharing mechanisms such as Napster, Gnutella, eDonkey-series, and the most successful (also, still beloved by tons of users) BitTorrent.

The concept, protocol, and the mechanism of the BitTorrent were solely invented by the American computer programmer, Bram Cohen, and he founded also the company called BitTorrent Inc..

Most of us know that BitTorrent became a commodity one in the file sharing in around 2006, but the concept was made around 2001, and it took certain amount of time to get more people's engagement in BitTorrent.  Similarly, the concept and vision of the "live, real-time video streaming over P2P" called BitTorrent Live was announced by Bram Cohen in September 16, 2009.  The most interesting one is, he had already found that people need such a way to broadcast individuals' live contents (e.g., UGCs) who don't have any dedicated infrastructures for broadcasting.

After 3.5 years from his announcement, he just (early 2013) announced the public beta test for his new BitTorrent Live, and the right time, his patent describing the concept of BitTorrent's internal protocol was unveiled on USPTO (March 2013).  Accidentally, I got a chance to look at the details of all the inside of the BitTorrent Live's internal protocol, so I felt that I should do some analysis of the inside of the BitTorrent Live.  This is the reason why I'm unveiling the BitTorrent Live.

[** Note that, all the details were based on his presentation materials, and the recent patent (no. US2013/0066969 on USPTO), but if there is a serious conflict, please let me know.  Also, if you find something wrong, please also let me know to correct. **]


In this post, I will describe the internal protocol of BitTorrent Live using the following order.  

  • Main objective of BitTorrent Live 
    • I will describe the main goal of this protocol here. 
  • Time-based batch packet processing  
    • This is to bound the packet transmission delay, and to avoid overhead of managing smaller packets. 
  • Two-level peer group (a.k.a. "club")-based overlay network topology 
    • This is to decongest the network packet request to the source (a.k.a., "broadcaster"), and to utilize the peers' network bandwidth. 
  • Congestion control avoidance mechanism 
    • This is all about using UDP-based communication (in other words, "connectionless"), not using TCP congestion control mechanism. 
  • Prioritized data transmission scheduling 
    • This is a key component to efficiently provide and balance the streaming latency and coverage of streaming among peers. 
  • Data reconstruction and playback on the end-user machine 
    • This is to play the live streaming video contents received by multiple peers. 




Section 1:
Main objective of BitTorrent Live 


Here, I would like to start with the quote on the BitTorrent Live website
"BitTorrent Live is a powerful new web-based live streaming technology. Designed to eliminate barriers to broadcast, Live is an entirely new protocol, designed to deliver high quality video to large audiences - with significant reduction in infrastructure cost and network delays."
The basic objective is to provide a "Live" streaming to tons of subscribers (millions of end-users) within a few-seconds of delay, as live TV broadcasting does.  If you're familiar with BitTorrent, you would be able to guess what is the key challenging factor; yes, it's on the term, "Live".  If we don't have such a constraint, then we can just record the video streaming and share it with users on another time using existing BitTorrent protocol.  But, the constraint called "Live" (a.k.a., "real-time") makes it a little bit complicated.  This is the starting point, of understanding the existing problem, on the P2P-based communication mechanism.  

[** Note that, there have been several interesting publications related to live-streaming over P2P networks.  But this post is dedicated to unveil the BitTorrent Live protocol, so I will not touch the similar previous works. **]




Section 2: 
Time-based batch packet processing 


The most important task on the live video streaming is, keeping the "timeliness" of transmitting new data packets created by the source node (a.k.a., "broadcaster").  To be able to provide the "timeliness" in an efficient manner, we need to solve a tradeoff between the overhead of managing packets, and the latency of packet transmission.  If we have too coarse-grained, long-time batch packet processing (e.g., 5 seconds of batch processing), we will have too much communication latency between peers, so it may spoil the "timeliness" property.  On the other hand, if we take a finer term batch processing (e.g., 0.01 seconds), we will have too much packet transmission overhead due to the large portion of packet headers and management cost. 

Thanks to Bram Cohen's intuition, BitTorrent Live uses a "0.25 seconds" as a unit for the batch packet processing.  This means that it will take at least "0.25 seconds" x "number of transmission" streaming latency from the source node to the end-users' media player.  But as you can imagine, even though we have 10 times of transmission among peers, it will take just 2.5 seconds delay due to the batch processing.  This is a quite reasonable "magic number" for the batch processing. 

Also, Fig. 2 shows how the sub-packets form the batch packet, and how the checksum (hash) is calculated among the sub-packets.  This is a useful (efficient) way to reduce the time to make a checksum for each peer.  (Could you imagine some other better ways?) 

Fig. 2. Batch packet processing and its hierarchical hashing mechanism




Section 3:
Two-level peer group-based overlay network topology 


Since BitTorrent Live towards a decentralized communication, it is necessary to form a dynamic network topology using existing peers.  Bram Cohen used an existing, but compelling concept of both overlay and hierarchical networks using the peers.  In BitTorrent Live, clusters (in other word, groups) are called as "Clubs". Note that, each club is not only a notion of virtual group of peers, but also a way to distribute (decentralize) streaming packets to multiple set of groups of peers. 

Figure 3 shows the hierarchical overlay network topology used in BitTorrent Live, and you can see multiple clubs.  There is another "magic number: 6" for the number of clubs.  Each peer involves to at least two clubs, and each club works both as first-level (tier-1) screamer club (in Fig. 3, in-club), and a second-level (tier-2) distributor club (in Fig. 3, out-of-club).  

Fig. 3. Two-level Overlay P2P Network in BitTorrent Live

[** Because I'm not really familiar with the P2P concepts, so I asked Bram about why do we call the tier-1 club peers as a screamers, and he mentioned that this is a common technical term.  If some readers can give any point of reason, please let me have. **]

In BitTorrent Live, as I depicted as directional arrow in Fig. 3, all the communication is directional (using UDP protocol).  First of all, the source node transmits each packet to appropriate club peers (at least two peers for redundancy and real-time response), where the club is selected by the "Mod 6" operation of the packet's sequence number.  For example, if there is a "17th packet", then the "club 5" (17 Mod 6 = 5) will be selected as a screamer (tier-1) club, and the source node will transmit the "17th packet" to some peers in the "club 5".  Then, each peer transmits at least two in-club peers, and another two out-of-club peers.  There is less unveiled information on how to manage list of neighboring peers, but I guess that there will be some mechanism similar to "finger tables" used in the previous P2P protocols.  

Anyhow, by composing such a two-level hierarchy, we can several benefits as follows; 1) the source node can offload its duty to distribute the packets, 2) the end-user peers can receive packets from multiple intermediate sources (peers in the same club, and out-of-clubs), and 3) its fault-tolerance, and reliability even though some peers have transmission delays.  

[** Also, I asked to Bram Cohen to know how he made a decision on the magic number "6", and he answered that he made various network simulations by his own simulation code.  Thanks to his effort, BitTorrent Live got the magic number "6", and it still keeps its simplicity of distributing packets and groups of peers in the same notion. **] 



Section 4: 
Congestion control avoidance mechanism 


As I already mentioned earlier in this post, communication among peers are uni-directional, based on UDP.  This means that there is no TCP-like congestion control mechanism.  Bram Cohen mentioned that TCP's connection-oriented mechanism is not suitable for P2P's nature (dynamic topology, communicate with tons of peers on demand), and TCP's congestion control doesn't seem to be great than just using simple congestion control avoidance using UDP.  Figure 4 shows the impact of congestion control on the bandwidth utilization, and he justified that there are actually less differences between two of them.  

Fig. 4. Comparison of Network Bandwidth Utilization between UDP (simple congestion avoidance) and TCP 

[** Note that it is still arguable, and we could do better design for the congestion controlling mechanism.  We can leave this portion to our tons of scientists working overnight everyday. :-) **]




Section 5: 
Prioritized data transmission scheduling 


One of key challenging part when using P2P communication is to make peers cooperative each other.  On the BitTorrent Live's packet data transmission between peers in different clubs (please refer to Fig. 3), each peer should be able to balance both the duty to broadcast its own club packets (communicate with in-club peers), and help others to distribute packets from the other clubs (communicate with out-of-club peers).  To do this, Bram Cohen developed a two-level round-robin scheduling mechanism with the following extra policies. (also, please see the Fig. 5)

  • Send in-club data packets first. 
    • Because the in-club data packets should be sent as soon as possible. 
  • Do FCFS (first-come-first-serve). 
    • No other reason not to do in this way. 
  • Take round-robin scheduling (among multiple peers). 
    • To minimize the worst-case latency due to queueing delay on each peer. 
  • Send at least 1 out-of-club data packets out of 10 data transmission. 
    • To be cooperative with other peers. 


Fig. 5. Two-level Prioritized Packet Transmission Queues

Note that, something in Fig. 5 might be wrong, since I don't fully understand whether if the in-club data  are the data to be sent to in-club peers, or just in-club packets.  So, please take this into account when you're unclear to get it.





Section 6: 
Data reconstruction and playback on the end-user machine 


Finally, the end-user peers can play the live streaming video as soon as they received certain amount of consecutive data packets.  Aforementioned, each packet has 0.25 seconds, so it might be better to have a few more packets in a row to start playback.

Figure 6 shows an example of reconstructing video streaming data on one of the end-user peers.  As we can see in this figure, the packets are divided into "6" clubs, and some of the packets may not arrive in-time due to the delay of the multi-hop network communications.  Since Bram is so much a big fan of the number "6", he selected the same number, "6", as the number of consecutive packets to allow playback on the end-user peers.  Actually, taking the same number is quite reasonable, because if an end-user is a new comer to the P2P network, and starting to receive some packets, then it might be true to wait to receive packets in-time for all "6" clubs.  So, in this example, 28th packet will be the starting point to play, since there are no other sufficient amount of consecutive packets before 28th.


Fig. 6. An Example: Received Packets and the Place to Start Playing
(where numbers from 0 to 44 are the sequence numbers of the packets)

In addition, there is another big pitfall to start playing as soon as possible on the end-user peers; waiting time for the forthcoming key frame in the video codec.  Usually, all the video codecs are not very keen to put key frames frequently, since it spoils the compression performance significantly.  The average waiting time to get the first key frame would be roughly "8" seconds on most video codecs where they put one key frame per 16 seconds.  This is the same reason why the digital cable TVs are very slow when zapping channels.




Performance: 
Scalability 


Finally, here is a simple graph related to the scalability of BitTorrent Live; especially focusing on the source node's bandwidth requirement (see Fig. 7).

Fig. 7. Comparison of BitTorrent Live and many legacy live broadcasting
(in terms of the bandwidth requirement on the source node)

Even though we haven't tested the BitTorrent Live with massive amount of users (> 100M users), it is still very useful platform for the usual live broadcasting purpose among people, since it does not ask any server-side infrastructures, no need to pay for individuals (** here I believe that Bram is a nice guy so that he will not ask individuals to pay some money. :-D).

That's it.  Now it's your turn to use the BitTorrent Live!  Hope all of you are happy with live video broadcasting!

- written by ANTICONFIDENTIAL, at SF, in May 6, 2013

0 comments:

Post a Comment