System and Method for Highly Scalable Video on Demand

• US 20030037331A1
• Filed: 08/30/2001
• Published: 02/20/2003
• Est. Priority Date: 08/30/2000
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Chinese University of Hong Kong
• Inventors: Lee, Jack Yiu-bun
• Granted Patent: US 7,107,606 B2
• Time in Patent Office: Days
• US Class Current: 725/32
• CPC Class Codes: H04N 21/2225 Local VOD servers
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568
• CPC Class Codes: H04N 21/2385 Channel allocation H04N21/266 takes precedence; Bandwidth allocation H04N21/24 takes precedence ; allocation of channels according to the instantaneous demands of the users in time-division multiplex systems H04J3/1682; admission control, resource allocation in open networks H04L12/5692; arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896; negotiating bandwidth in wireless networks H04W28/16
• CPC Class Codes: H04N 21/2396 characterized by admission policies admission control, resource allocation in open networks H04L12/5692; arrangements for network security using user profiles for access control H04L63/102; access security in wireless networks H04W12/08
• CPC Class Codes: H04N 21/26275 for distributing content or additional data in a staggered manner, e.g. repeating movies on different channels in a time-staggered manner in a near video on demand system
• CPC Class Codes: H04N 21/26616 for merging a unicast channel into a multicast channel, e.g. in a VOD application, when a client served by unicast channel catches up a multicast channel to save bandwidth data multicast over packet-switching network H04L12/18
• CPC Class Codes: H04N 21/4331 Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/6405 Multicasting data broadcast and multicast in packet switching networks H04L12/18
• CPC Class Codes: H04N 21/6587 Control parameters, e.g. trick play commands, viewpoint selection
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

Abstract of Disclosure

An embodiment of a system and method for providing video on demand provides pre-scheduled multicasts of videos as well as dynamically initiated transmissions of the front portion of videos. Users may first receive a dynamically initiated front portion of a video and then be merged into a pre-scheduled multicast. Preferably, the dynamically initiated transmission is also a multicast. Preferably, multiple admission controllers and a single server coordinate the dynamically initiated transmissions for any one video. Preferably, interactive controls are supported without requiring extra server-side resources. Preferably, latency is automatically equalized between users admitted via the pre-scheduled and the dynamically initiated transmissions. Preferably, a user receiving a video via a pre-scheduled multicast does not need to change channels to finish receiving the video transmitted. Preferably, a module can model and quickly estimate expected latency given system parameters such as number and allocation of channels and expected user arrival time(s).

Claims

1. A method for providing sequential data blocks having duration comprises:

providing repeated pre-scheduled multicasts of a data block;

dynamically initiating a transmission of the front portion of the data block in response to a user request to receive the data block; and

merging the user into a pre-scheduled multicast of the data block;

wherein the dynamically initiated transmission is a multicast.

2. The method according to claim 1, wherein each data block is a video comprising images viewed sequentially over time, whereby the video has a sequence and a duration, whereby the data block is a sequential data block having duration.

3. A method for providing videos to users, the method comprising:

multicasting a video according to a predetermined schedule, the multicasting hereinafter referred to as the first multicasting;

receiving an indication that a user desires to see the video;

if the first multicasting will not multicast the video timely for the user to receive and view the video with acceptably low waiting time, then dynamically initiating transmission of a portion of the video, the portion hereinafter referred to as the first portion of the video, wherein the user will receive at least some of the first portion of the video, and the user will receive another portion of the video, hereinafter referred to as the second portion of the video, via the first multicasting; and

if the first multicasting will multicast the video timely for the user to receive and view the video with acceptably low waiting time, then causing the user to receive the first multicasting without needing to receive the dynamically initiated transmission.

4. The method according to claim 3, wherein acceptably low waiting time is according to an adjustable threshold parameter, the method further comprising adjusting the threshold parameter dynamically for subsequent users who desire to see the video, to thereby reduce usage of transmission resources at a cost of increasing expected waiting time, by reducing likelihood of dynamically initiating transmission for the subsequent users, or to thereby reduce expected waiting time at a cost of increasing usage of transmission resources, by increasing likelihood of dynamically initiating transmission for the subsequent users

5. The method according to claim 3, wherein acceptably low waiting time is according to an adjustable threshold parameter, further comprising automatically adjusting the threshold parameter dynamically to attempt to equalize an expected average waiting time for users who receive the dynamically initiated transmission for the video with an expected average waiting time for users who do not receive the dynamically initiated transmission for the video.

6. The method according to claim 3, wherein acceptably low waiting time is according to an adjustable threshold parameter, and the threshold parameter may be adjusted along a continuum for graceful degradation of waiting-time performance as number of users increases.

7. The method according to claim 3, wherein the first multicasting is such that once the user begins receiving any portion of the video via the first multicasting, then the user does not need to change channel to receive substantially the entire remainder of the video.

8. The method according to claim 3, wherein the predetermined schedule is established more than about six hours before the first multicasting.

9. The method according to claim 3, wherein the predetermined schedule includes multiple fixed start times for the video, wherein multicastings according to the multiple fixed start times overlap in time.

10. The method according to claim 3, wherein the dynamically initiating transmission of the first portion of the video comprises dynamically initiating multicasting of the first portion of the video, the dynamically initiated multicasting hereinafter referred to as the second multicasting.

11. The method according to claim 3, wherein the first multicasting is over one of a set of channels pre-assigned for multicasting the video according to the predetermined schedule, the set of channels hereinafter referred to as the first set of channels.

12. The method according to claim 11, wherein a second set of channels is pre-assigned for dynamically initiated transmission for the video.

13. The method according to claim 12, wherein the number of channels in the second set of channels is allocated to be at least about the number of channels in the first set of channels.

14. The method according to claim 3, wherein the video includes a front-most portion of the video, and the first portion includes the front-most portion of the video.

15. The method according to claim 3, wherein the dynamically initiated transmission includes a patching multicast for continuing a front-most portion of the video that was stored at one of multiple prefix storage sites.

16. The method according to claim 3, wherein the first multicasting and the dynamically initiated transmission are both served from a same server.

17. The method according to claim 3, wherein the user receives and buffers the second portion of the video while receiving and viewing the at least some of the first portion of the video, and then views the buffered second portion of the video, time shifted, to thereby seamlessly view the at least some of the first portion of the video and the second portion of the video.

18. The method according to claim 17, wherein the user pauses and resumes viewing of the video at will without incurring additional resource expenditure by any server or network element involved in the first multicast or the dynamically initiated transmission.

19. The method according to claim 17, wherein the user views the video in slow motion at will without incurring additional resource expenditure by any server or network element involved in the first multicast or the dynamically initiated transmission.

20. The method according to claim 17, wherein the user can seek to an approximate new point in the video at will without incurring additional resource expenditure by any server or network element involved in the first multicast or the dynamically initiated transmission, and wherein the user can seek to a precise new point in the video at will but will require an additional dynamically initiated transmission from a server.

21. The method according to claim 3, wherein the receiving step comprises receiving at a server, from one of multiple controllers, the indication that a user desires to see the video, wherein the one controller itself received multiple requests for multiple users to receive the video, but the one controller sent fewer indications to the server than the multiple received requests.

22. The method according to claim 3, further comprising:

accepting proposed system parameters including number of channels, number of videos, allocation of channels, and a threshold parameter that is indicative of acceptably low waiting time;

accepting expected user arrival rates;

computing and outputting an approximate expected average wait time for the method based on the proposed system parameters and the expected user arrival rates, using numeric solutions to a performance model;

wherein sufficiency of proposed system parameters can be approximately determined.

23. A method for providing videos to users, the method comprising:

multicasting a video according to an earlier determined schedule, the multicasting hereinafter referred to as the first multicasting;

receiving at least one request that is indicative that a user desires to see the video; and

in response at least in part to the request, dynamically multicasting a portion of the video;

wherein at least one user receives the portion of the video, hereinafter referred to as the first portion of the video, from the dynamically multicasting;

the at least one user receives, from the first multicasting, at least a portion of the video, hereinafter referred to as the second portion of the video; and

the at least one user plays the first portion of the video followed by the second portion of the video.

24. The method according to claim 23, wherein the first multicasting is such that once a user begins receiving the first multicasting, then further communication for channel establishment is not required between the user and any network element that delivers the video to receive substantially the entire remainder of the video.

25. The method according to claim 23, wherein start time for any given multicast in the earlier determined schedule are not in response to any arrival of a user who will receive the given multicast, whereby even if no user is expected to watch the given multicast, the given multicast still takes place at its earlier determined start time.

26. The method according to claim 23, wherein multiple prefix servers are not used in conjunction with the dynamically multicasting.

27. The method according to claim 23, wherein the dynamically multicasting is a patching multicasting used in connection with multiple prefix servers.

28. The method according to claim 23, wherein the first multicasting and the dynamically multicasting are both served from a same server.

29. A method for providing videos to users, the method comprising:

(a) receiving a request from a user to receive a video at a controller;

(b) if an upcoming statically scheduled multicast of the video will begin within a threshold time parameter, then arranging for the user to receive the upcoming statically scheduled multicast of the video, thereby satisfying the request from the user and refraining from subsequent steps listed below;

(c) otherwise, if no new multicast for the video is currently being dynamically scheduled, then sending a request toward a server to begin dynamically scheduling a new multicast for the video, and continuing with subsequent steps listed below; and

(d) receiving a confirmation at the controller that the new multicast for the video has been dynamically scheduled, and, in response, arranging for the user to receive the upcoming dynamically scheduled new multicast for the video, wherein the new multicast for the video will include less than the entire video;

(e) wherein the user receives and buffers an in-progress pre-scheduled multicast of the video, the user receives and views the dynamically scheduled new multicast for the video, and the users begins to view content from the user'"'"'s buffer from the in-progress pre-scheduled multicast after the dynamically scheduled new multicast has caught up to the content from the user'"'"'s buffer.

30. The method of claim 29, further comprising:

(f) receiving a number of additional requests from additional users to receive the video at the controller in between execution of the steps (c) and (d); and

(g) refraining from sending additional requests toward the server in response to the additional requests until, in the step (d), receiving the confirmation at the controller that the new multicast for the video has been dynamically scheduled, and then;

31. A system for providing videos to users, the system comprising:

means for multicasting a video according to a predetermined schedule, the multicasting hereinafter referred to as the first multicasting;

means for receiving an indication that a user desires to see the video;

means for, if the first multicasting will not multicast the video timely for the user to receive and view the video with acceptably low waiting time according to a threshold parameter, then dynamically initiating transmission of a portion of the video, the portion hereinafter referred to as the first portion of the video, wherein the user will receive at least some of the first portion of the video, and the user will receive another portion of the video, hereinafter referred to as the second portion of the video, via the first multicasting; and

means for, if the first multicasting will multicast the video timely for the user to receive and view the video with acceptably low waiting time according to the threshold parameter, then causing the user to receive the first multicasting without needing to receive the dynamically initiated transmission.

32. The system according to claim 31, wherein the means for multicasting is configured such that once the user begins receiving any portion of the video via the first multicasting, then the user does not need to change channel to receive substantially the entire remainder of the video.

33. The system according to claim 31, wherein the predetermined schedule includes multiple fixed start times for the video, wherein multicastings according to the multiple fixed start times overlap in time.

34. The system according to claim 31, wherein the dynamically initiating transmission of the first portion of the video comprises dynamically initiating multicasting of the first portion of the video, the dynamically initiated multicasting hereinafter referred to as the second multicasting.

35. The system according to claim 31, wherein:

the means for multicasting comprises a set of channels pre-assigned for multicasting the video according to the predetermined schedule;

the means for dynamically initiating transmission comprises a second set of channels pre-assigned for dynamically initiated transmission for the video; and

the number of channels in the second set of channels is allocated to be about the number of channels in the first set of channels.

36. A system for providing videos to users, the system comprising:

means for multicasting a video according to an earlier determined schedule, the multicasting hereinafter referred to as the first multicasting;

means for receiving at least one request that is indicative that a user desires to see the video; and

means for, in response at least in part to the request, dynamically multicasting a portion of the video;

wherein at least one user receives the portion of the video, hereinafter referred to as the first portion of the video, from the dynamically multicasting;

the at least one user receives, from the first multicasting, at least a portion of the video, hereinafter referred to as the second portion of the video; and

the at least one user plays the first portion of the video followed by the second portion of the video.

37. The system according to claim 36, wherein the first multicasting is such that once a user begins receiving the first multicasting, then further communication for channel establishment is not required between the user and any network element that delivers the video to receive substantially the entire remainder of the video.

38. The system according to claim 36, wherein start time for any given multicast in the earlier determined schedule are not in response to any arrival of a user who will receive the given multicast, whereby even if no user is expected to watch the given multicast, the given multicast still takes place at its earlier determined start time.

39. A system for providing videos to users, the system comprising:

means for receiving a request from a user to receive a video at a controller;

means for, if an upcoming statically scheduled multicast of the video will begin within a threshold time parameter, then arranging for the user to receive the upcoming statically scheduled multicast of the video, thereby satisfying the request from the user;

means for, otherwise, if no new multicast for the video is currently being dynamically scheduled, then sending a request toward a server to begin dynamically scheduling a new multicast for the video; and

means for receiving a confirmation at the controller that the new multicast for the video has been dynamically scheduled, and, in response, arranging for the user to receive the upcoming dynamically scheduled new multicast for the video, wherein the new multicast for the video will include less than the entire video;

wherein the user receives and buffers an in-progress pre-scheduled multicast of the video, the user receives and views the dynamically scheduled new multicast for the video, and the users begins to view content from the user'"'"'s buffer from the in-progress pre-scheduled multicast after the dynamically scheduled new multicast has caught up to the content from the user'"'"'s buffer.

40. The system of claim 39, further comprising:

means for receiving a number of additional requests from additional users to receive the video at the controller and refraining from sending additional requests toward the server in response to the additional requests until receiving the confirmation at the controller that the new multicast for the video has been dynamically scheduled; and

means for then arranging for the additional users to receive the upcoming dynamically scheduled new multicast for the video and sending a request toward the server to increase the amount of the video to include in the new multicast for the video, to thereby accommodate the additional users.

41. A system for providing video content, the system comprising:

at least one server, the at least one server configured to multicast a video via a network according to a fixed predetermined schedule and to dynamically initiate transmission of a portion of the video, hereinafter referred to as the first portion of the video, for at least one user, hereinafter referred to as the at least one dynamic user; and

a controller configured to receive requests from users to see a video and to indicate, to the at least one server, user interest to see the video, including interest by at least one of the at least one dynamic user;

wherein the at least one dynamic user receives at least part of the first portion of the video, and the at least one dynamic user also receives a portion of the video, hereinafter referred to as the second portion of the video, via the multicast according to the fixed predetermined schedule, and the first portion of the video includes video content not within the second portion of the video, and the at least one dynamic user is able to begin viewing the at least part of the first portion of the video and then to switch to viewing the second portion of the video.