Interactive video distribution systems – User-requested video program system – Video-on-demand
Reexamination Certificate
2000-03-17
2004-02-10
Miller, John (Department: 2614)
Interactive video distribution systems
User-requested video program system
Video-on-demand
C725S095000, C725S097000, C370S351000, C370S400000, C709S232000
Reexamination Certificate
active
06691312
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to multicasting video.
BACKGROUND OF THE INVENTION
Development of a high-speed internetworking infrastructure (e.g., the Internet) and digital video technology has led to the emergence of several networked multimedia applications that include streaming video as a media component. Such applications include streaming video broadcasts, distance learning, corporate telecasts, narrowcasts, etc. Digital video traffic typically exhibits high bandwidth requirements and significant burstiness at multiple time scales, owing to the encoding schemes and content variation between and within video scenes. For example, MPEG (Motion Pictures Experts Group) encodes a video in different size frames. Additionally, the information needed to encode each frame can vary, for example, based on how much video information changes from image to image. When combined with other media such as audio, text, HTML (HyperText Markup Language), and images, multi-media transmissions can become even burstier. The high bandwidth requirements coupled with the bursty variable-rate nature of these streams complicates the design of efficient storage, retrieval, and transport mechanisms for such media.
A technique known as workahead smoothing can yield significant reductions in peak rate and rate variability of video transmissions from a server to a single client (i.e. unicast). In smoothing, by transmitting frames early, the sender, or a smoothing node, can coordinate access with the client and can send large video frames at a slower rate without disrupting continuous playback at the client. The frames transmitted ahead of time are temporally stored in buffers present in the server and the client. A characteristic of the smoothed transmission schedule is that the smoothing benefit is a non-decreasing function of buffer sizes present.
SUMMARY OF THE INVENTION
For many applications, streaming video transmission occurs from a server simultaneously to a large number of heterogeneous clients that have different resource capacities (e.g. buffer sizes) and that are scattered geographically over a heterogeneous internetwork that has different resource capacities in different segments. Described herein are techniques that can reduce the bandwidth overhead for such simulcast services.
In general, in one aspect, the invention features a method of multicasting video to multiple client nodes via intermediate nodes. The method includes accessing video information descriptive of the video to be multicast, accessing information describing a distribution tree of nodes from a source of the video to the multiple clients nodes via one or more internetwork nodes, accessing rate constraints of nodes in the distribution tree, accessing buffer allocations of the nodes in the distribution tree, and determining one or more smoothed transmission schedules for each node in the distribution tree based on the accessed video information, the accessed information describing the distribution tree, the accessed rate constraints of nodes in the distribution tree, and the accessed buffer allocations of the nodes, the one or more transmission schedules describing the transmission of video data to one or more children nodes.
Embodiments may include one or more of the following features. Accessing buffer allocations can include determining buffer allocations based on the accessed video information, the accessed information descriptive of a distribution tree, and the accessed rate constraints. Accessing rate constraints may include receiving rate constraints. The determining may include determining an upper constraint for each node, determining a lower constraint for each node, and determining a smoothing schedule based on the determined upper and lower constraints. The determining of a smoothed schedule may use majorization. The method may further include distributing the determined transmission schedules to nodes in the distribution tree. The determined transmission schedules may include schedules that cause at least one node to differentially cache data for distribution to the at least one node's children.
In general, in another aspect, the invention features a computer program product, disposed on a computer readable medium, for multicasting video to multiple client nodes via intermediate nodes. The program includes instructions for causing a processor to access video information descriptive of the video to be multicast, access information describing a distribution tree of nodes from a source of the video to the multiple clients nodes via one or more internetwork nodes, access rate constraints of nodes in the distribution tree, access buffer allocations of the nodes in the distribution tree, and determine one or more smoothed transmission schedules for each node in the distribution tree based on the accessed video information, the accessed information describing the distribution tree, the accessed rate constraints of nodes in the internetwork, the accessed buffer allocations of nodes in the internetwork, and the one or more transmission schedules describing the transmission of video data to one or more children nodes.
Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of the present invention, suitable methods and materials are described below. All publications, patent applications, patents, and other references mentioned herein are incorporated by reference in their entirety. In case of conflict, the present specification, including definitions, will control.
In addition, the materials, methods, and examples are illustrative only and not intended to be limiting.
REFERENCES:
patent: 5940391 (1999-08-01), Malkin et al.
patent: 6320865 (2001-11-01), Agrawala et al.
patent: 6377972 (2002-04-01), Guo et al.
Almeroth et al., “The Use of Multicast Delivery to Provide a Scalable and Interactive Video-on-Demand Service,” IEEE Journal of Selected Areas in Communication, vol. 14, No. 6, p. 1110-1122 (1996).
Deering et al., “Multicast Routing in Datagram Internetworks and Extended LANs”, ACM Transactions on Computer Systems, vol. 8, No. 2, p. 85-110 (1990).
Feng et al., “A Comparison of Bandwidth Smoothing Techniques for the Transmission of Prerecorded Compressed Video,” Proc. IEEE Infocom '97 Conf. Comp. Comm., vol. 1, p. 58-66 (1997).
Garrett et al., “Analysis, Modeling and Generation of Self-Similar VBR Video Traffic,” ACM, p. 269-280, (Sep. 1994).
Lakshman et al. “Variable Bit-Rate (VBR) Video Tradeoffs and Potentials,” proc. IEEE, vol. 86, p. 952-973 (May 1998).
Rao et al., “Fast Techniques for the Optimal Smoothing of Stored Video,” Multimedia Systems, vol. 7, p. 222-233 (1999).
Rexford et al., “Online Smoothing of Live, Variable-Bit-Rate Video,” Proceedings of Workshop on Network and Operating System Support . . . , IEEE, p. 235-243 (1997).
Rexford et al., “Smoothing Variable-Bit-Rate Video in an Internetwork,” IEEE/ACM Transations on Networking, vol. 7, No. 2, p. 202-215 (Apr. 1999).
Salehi et al., “Supporting Stored Video: Reducing Rate Variability and End-to-End Resource Requirements Through Optimal Smoothing,” IEEE/ACM Transactions on Networking, vol. 6, No. 4, p. 397-410 (1998).
Sen et al. “Optimal Multicast Smoothing of Streaming Video over an Internetwork,” Proceedings IEEE Infocom '99 Conf. On Comp. Comm., vol. 2, p. 455-463 (1999).
Dey Jayanta Kumar
Sen Subhabrata
Towsley Don
Zhang Zhi-Li
Fish & Richardson P.C.
Ma Johnny
Miller John
University of Massachusetts
LandOfFree
Multicasting video does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multicasting video, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicasting video will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3315652