The YouTube serving infrastructure is complicated, with many interacting components, including load balancing, hierarchial storage, multiple client types and many format conversions. However, the YouTube content delivery uses the same server application, called ustreamer independent of client type, video format or geographical location.
The just-in-time algorithm in YouTube comprises of two phases namely the startup phase and a throttling phase.
It builds up the playback buffer in the client, to minimize the likelyhood of player pauses due to rebuffering(buffer-under-run) events.
ustreamer sends the first 30-40 seconds of video as fast as possible into the TCP socket
In this phase, ustreamer uses a token bucket algorithm to compute the schedule for delivering the rest of the video.
Tokens are added to the bucket at 125% of the video encoding rate and they are removed as soon as the video is delivered.
A delay timer for a data block (64KB) is computed to expire as soon as the bucket has sufficient tokens.
If for some reason, the video delivery is running behind, then the calculated delay will be zero and the data is written to TCP socket as soon as possible.
The extra 25% added to data rate as described above reduces the number of rebuffering events.
NOTE: A video is delivered over a single TCP connection.
Problem in JIT delivery algorithm
The bursts of data separated by idle periods, disrupts TCP’s self clocking.
For most applications, TCP data transmissions are triggered by the ACK returning from the receiver
With YouTube, TCP typically has no data to send when the ACKs arrive, and then when ustreamer writes the data to the socket, it is sent immediately because TCP has unused cwnd(congestion window)
YouTube solves this problem by setting an upper bound on cwnd of target_rate x RTT, where target_rate is the target streaming rate of the video in throttling phase.
Linux already provides this feature as a per-route option called cwnd clamp. YouTube team wrote a small kernel patch to make it available as a per-socket option.
Challenges ———- The solution described above encounters two practical challenges:
Network congestions causing re-buffering.
Small cwnd causing inefficient transfers.
Trickle addresses both these challenges and provides an algorithm to overcome them. Algorithm is decribed below. You can take a look at the animated demo here
Algorithm of Trickle in throttling phase
Trickle has effectively reduced the retransmissions by up to 50% in high bandwidth networks. It also reduces the average RTT by up to 28%.