Fuzzycast: Achieving Scalable and Efficient Video-on-Demand Over Multicast

Server bandwidth has been identified as a major bottleneck in large Video-on-Demand (VoD) systems. Using multicast delivery to serve popular content helps increase scalability by making efficient use of server bandwidth. In addition, recent research has focused on proactive schemes in which the server periodically multicasts popular content without explicit requests from clients. Proactive schemes are attractive because they consume bounded server bandwidth irrespective of client arrival rate.

In this project, we created Fuzzycast, a scalable periodic multicast scheme that uses simple techniques to provide VoD at reasonable client startup times at optimum server bandwidth. Our starting point is a theoretically optimum scheme for providing scalable VoD using multicast. We go on to consider a series of issues that are of both theoretical and real-world importance. They include support for variable-bitrate (VBR) media and scheduling transmissions over multiple multicast groups, and optimum adaptation to variable viewing populations. We supplement these results by describing their use in the construction of a prototype VoD system, where the single mechanism used shows practical optimality under a wide range of factors.

Contributions

The main idea behind Fuzzycast is to transmit each frame at a rate 1/(w+f), where w is the initial waiting time and f is the current frame number. We use a simple and effective heuristic to smoothen the resulting spiky stream. The heuristic's effectiveness is further increased by the observation that most VoD servers do not just serve a single movie, but many of them instead. This results in a server performance practically indistinguishable from the theoretical optimum through very simple schemes.

This allows any client to join at any time and start watching the movie almost immediately, even though the server is only required to transmit at a small, constant, multiple of a single movie playout rate.

In our publications below, we also discuss how to achieve optimum network and client bandwidth. This is based on an generic optimization problem we call Scottie's dilemma. We further discuss how to optimally reduce server bandwidth when the movie is temporarily in low demand.

Further, we introduce a new buffer management scheme that significantly reduces hard disk accesses, thereby improving client performance or allowing for cheaper implementation, important criteria for consumer devices.

Results

The success of VoD systems depends on the provider's ability to offer a cost-effective service that is also attractive to end-users. Scalability and efficiency are critical for the former part, while functionality, ease of use, and quick response to user commands are needed to satisfy the latter aspect.

Proactive VoD protocols are attractive from the scalability point of view, because they use server bandwidth efficiently to serve media even under heavy demand. However, current proactive schemes have significant drawbacks in terms of practical implementation and deployment. Fuzzycast, by taking a pragmatic frame-oriented approach, uses near-optimum server bandwidth while remaining relatively simple to implement and maintain.

Although transmitting variable bitrate (VBR) media is a significant issue in the real world, most existing periodic multicast schemes do not handle VBR media very well. We proposed a simple extension to Fuzzycast, namely Fragmented Fuzzycast, and demonstrated that it was able to deliver VBR content over constant-rate channels with minimal performance loss or complexity overhead.

Next, periodic multicast schemes place extra load on the network owing to redundant multicasts. We show how the problem of transmitting content over multiple multicast groups results in a fundamental resource tradeoff; by solving the general case, we obtain an optimum solution to our problem. We find that using even a few multicast groups results in significant reduction in overhead for both client and network. We note that the result obtained here is quite general and applicable to diverse situations, including networks that follow scaling properties that are very different from the Chuang-Sirbu law, in a straightforward manner.

Most importantly, we have shown that a simple and inexpensive heuristic scheduling can be used to outperform all known practical schemes, including many more complex schemes.

Using the optimum solution described here in other similar scenarios is an area of research we intend to pursue further. In addition, our current work involves extending these results to add support for more ``user-friendly'' options like interactive VCR-like functions.

Typical Operation

To demonstrate Fuzzycast, we ran the following scenario: The server started transmitting data at an arbitrary time. Our VoD client is started under Windows (image to the right; click to zoom) and the user begins browsing the program guide (left-hand part of window). At 12:05:26, the user selects Face/Off, whereupon the client immediately joins the appropriate multicast group and starts receiving and buffering data. In the meantime, the user has just gotten herself a snack and perfectly arranged the cushions on her sofa for a perfect movie-going experience. 32 seconds after the later, after the initial delay, enough data has been received such that playout can begin.

At 12:11:45, a second client (left, this time on a Linux machine) joins the same multicast group. Some 33 seconds later, it also has acquired enough data to begin streaming. Both client snapshots were taken about 1.5 minutes later, at 12:13:14.

Thanks to the scheduling mechanism used, the total transmit rate is only about 5 times that of a single movie, independent of the number of receivers and their join times. As can be seen by the snapshots that were taken at the same time, although both clients joined at separate times, each starts to play out the movie from the beginning shortly after the user chose the movie. Therefore, the different clients are also at different stages through the movie (this can be seen by looking at the time into the movie, which is displayed in small font directly below the actual movie (click on any of the images to see them in full detail).

On the right hand side of the client screens, several graphs are plotted. From top to bottom: Current client buffer usage, current receive bandwidth, and the transmission rate to the media renderer. From the client buffer size, you can see that the late-joiner (the Linux machine) is still early in the movie (before the client buffer peak at 37%), while the Windows machine is already beyond that.

Meanwhile, we have a look at the server (image to the left): Its network as well as the disk bandwidth have been steady since start. Even after a second client starts up, the bandwidths do not increase (image to the right).

(The choice of about 30 seconds for the initial delay as well as the availability of only a single movie, which is even just a trailer, would, and easily could, of course be adapted in a real deployment.)

Topology Data

We conducted many simulations, both on real as well as artificial topologies. These topologies and corresponding manipulation and conversion programs are also available.

Software

Requirements: Java Media Framework (JMF).

Publications

Participants

• Wei Deng
• Ramaprabhu Janakiraman
• Marcel Waldvogel
• Lihao Xu

Links

• Projects and Articles:
  SWORD: Scalable Wide-area On-demand Reliable Digital Streaming,
  IMoD: Interactive Media-on-Demand (Uni Mannheim),
  Berkeley Internet Broadcasting System,
  North Dakota Video-on-Demand (1994),
  Alexandros Eleftheriadis,
  Henning Schulzrinne,
  Pricing Considerations,
  Video-on-Demand Overview (Jari Peltoniemi, 1995),
  Internetworking Multimedia (Jon Crowcroft, Mark Handley, Ian Wakeman, 1998),
  
• Related work overview:
  CiteSeer,
• Press:
  Video on Demand (Chip Online special, October 2002),
  Want Video on Demand? Press Pause by Brad King (Wired News, September 11, 2002),
  Universal-Filme per Video on Demand (Heise Newsticker, October 8, 2002),
• Commercial offerings:
  Arcor, CinemaNow, HanseNet, Intertainer, Launch.com, Movielink, SightSound, USA Video,
• Software:
  Vodka,