UUSee: Operational On-Demand Streaming with Network Coding
With the application of random network coding in P2P content distribution and live streaming systems that adopt the random gossiping philosophy in random mesh topologies, one may wonder if it can be similarly applied to P2P on-demand streaming systems, also called video-on-demand (VoD) systems. With high-performance implementations of random network coding in commodity hardware from dedicated servers to mobile devices, one may also wonder if network coding can be deployed in large-scale operational P2P streaming systems.
A P2P on-demand streaming system is conceptually more challenging to design and implement, in that it requires not only smooth sequential playback, but also the shortest possible “restarting” latency, after an interactive random seek request is received from the user to relocate the playback point. In previous work, similar to live streaming systems, the on-demand media stream is divided into generations, which implies that the initial buffering delay is at least the length of one generation in terms of playback time at the streaming bit rate. In both a simulation and a small prototype, it shows that the throughput achieved with random network coding is higher, compared to a block selection algorithm that downloads globally rarest blocks in the generation first.
Similar to the scenario of bulk content distribution systems, once again, it was not clear whether benefits of random network coding in simulations and small prototypes can easily be carried over to real-world on-demand streaming systems operating at a large scale. Overall, in both content distribution and streaming systems, despite the foundation established by extensive research in the literature, random network coding has not been reported to be deployed in real-world operational systems at a large scale or in a production setting. What are the lingering challenges that prevent such a deployment?
Our work, published as a full paper in IEEE INFOCOM 2010, have applied random network coding in an operational on-demand streaming system called UUSee, and have presented the first successful attempt that applies the theory of random network coding in large-scale real-world systems. The design objectives were similar to those of live streaming systems, in that random seek latencies and server bandwidth costs should be minimized, while a consistent and smooth playback quality should be maintained. We now introduce the practical challenges and their corresponding design choices, learned from the experiences in such an operational system.
Practical Challenges
In real-world systems, any benefits are accompanied with costs or drawbacks. One seemingly naive question when network coding is to be used in the UUSee on-demand streaming system is how the size of a block should be determined. A coded block is the basic transmission unit used to serve a portion of a generation in the stream. Block-level granularity accommodates slower serving peers so that they can serve at least one block in a reasonable amount of time. It is intuitively preferable to use a smaller block size, such as 1 KB, such that each block directly corresponds to a User Datagram Protocol (UDP) packet in practice.
This seems to be a good choice if there were no overhead imposed by coding coefficients. Yet with random linear coding on GF(256), each coefficient occupies a byte, and such overhead depends on the number of blocks in a generation. It appears that in order to reduce the overhead due to coding coefficients, one should consider using a smaller number of blocks in each generation.
However, we cannot afford to use too few blocks in a generation, since a smaller number of blocks will lead to a different type of communication overhead, after a generation is completely received and decoded on the receiving peer. Illustrated in the figure above, “braking” acknowledgment packets need to be sent back to each of the serving peers, respectively, to stop them from sending more coded blocks. Due to the latency for these braking acknowledgments to be received by serving peers, additional redundant blocks may be received by the receiving peer after the generation is complete, and will need to be discarded. Apparently, as the number of blocks in a generation becomes smaller, the overhead caused by these redundant blocks will become more pronounced due to frequent “braking”.
In addition, the need for exchanging buffer availability information between neighboring peers calls for a larger number of blocks in a generation, since a larger generation size reduces the number of bits required to represent buffer availability in an on-demand video stream. The good news is that, with highly optimized implementations of network coding on commodity CPUs, the UUSee system can afford to use a larger number of blocks if it needs to.
Design Choices
The primary design goal is to amplify conceptual and theoretical benefits of network coding to the maximum extent possible, and to mitigate its drawbacks in practical use. The following design choices have been made in the UUSee on-demand streaming system with network coding.
Overhead. Applying the lesser of two evils principle, the overhead caused by redundant blocks — received after the generation is completely downloaded by a receiving peer — is a more important concern. To mitigate such overhead, a larger number of blocks, 300 to 500, is used in a generation, with a smaller block size. In the UUSee system, 1 KB is used as the size of a block, corresponding to a single UDP packet. With such a design choice, if coding coefficients are embedded into coded blocks so that they are self-contained, up to 50% overhead is incurred due to the small size of each block, and the large number of blocks in a generation.
Instead of embedding coding coefficients in the coded blocks, UUSee chooses to embed the PRNG seed that is used to produce the sequence of random coefficients with a known pseudo-random number generator (PRNG). This effectively reduces the overhead to only 4 bytes, regardless of the number of blocks, m, in a generation. The only side effect is that peers are no longer able to serve coded blocks to others before completely receiving a generation. However, unlike live streaming, on-demand streaming systems do not have any requirements on the playback lag between live events and their corresponding times of playback. As a result, such a side effect is a non-issue in on-demand streaming.
The push protocol for coordinating multiple serving peers. Since random linear network coding is used to make such coordination simple, coded blocks from all serving peers are equally useful. Upon the explicit request from a downstream peer p for blocks in a particular generation, a serving peer starts to push freshly generated coded blocks consecutively to p as UDP packets (with flow control), until the “braking” acknowledgment packet arrives. The downstream peer p may send explicit requests to more than one serving peer, and simply sends one acknowledgment packet (as the “stop” signal) to each serving peer after it has successfully decoded the generation progressively using Gauss-Jordan elimination.
Practical Experiences with Network Coding
In our INFOCOM 2010 paper, we have designed and implemented the first operational on-demand streaming system with random network coding, and have observed an excellent level of real-world streaming performance, based on measurement studies using 200 GB worth of operational traces. It has become evident that the design objectives in on-demand streaming systems have been achieved: multiple serving peers are able to coordinate their actions serving a peer, leading to minimized buffering delays and bandwidth costs on servers. The playback quality has been satisfactory for normal-quality videos. For high-quality videos, the use of network coding has mitigated negative effects when the server bandwidth supply becomes tight in meeting the demand for bandwidth.
