System and method for highly scalable video on demand

• US 7,107,606 B2
• Filed: 08/30/2001
• Issued: 09/12/2006
• 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
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): Ustaris, Joseph G.
• Application Number:
  US09/944,058
• Publication Number:
  US 20030037331A1
• Time in Patent Office: 1,839 Days
• Field of Search: 725/87, 725/90, 725/94, 725/95, 725/96, 725/97, 725/101
• US Class Current: 725/87
• 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

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 each having a duration, comprising:

providing repeating 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 from a user so as to serve the user outside the pre-scheduled multicasts of the data block as a dynamically admitted user;

merging the dynamically admitted user into one of the pre-scheduled multicasts of the data block;

wherein the dynamically initiated transmission is a multicast transmission that is sent to and is shared by a plurality of dynamically admitted users for the data block who are admitted in time to catch the beginning of the dynamically initiated multicast transmission.

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. The method according to claim 1, wherein a length of the front portion of the data block is variable according to a greatest duration of the portion of the video that is needed by the dynamically admitted users.

4. 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;

in response to user requests from a plurality of users for the video outside the predetermined schedule for the first multicasting, dynamically initiating a multicast transmission of the video to at least a portion of the plurality of users whose requests are made in time to catch the beginning of the dynamically initiated multicast transmission;

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.

5. The method according to claim 4, 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.

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

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

8. The method according to claim 4, 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.

9. The method according to claim 4, 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.

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

11. The method according to claim 10, 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.

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

portion of the video.

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

14. The method according to claim 4, further comprising:

causing the second portion of the video to be received and buffered by the user while the user is receiving and viewing the at least some of the first portion of the video, and then causing the buffered second portion of the video, time shifted, to be transmitted to and viewed by the user to thereby provide seamless viewing of the at least some of the first portion of the video and the second portion of the video the user.

15. The method according to claim 14, further comprising:

using video buffering and an existing multicasting according to the predetermined schedule to provide pausing and resuming functions to a user without incurring additional resource expenditure by any server or network element involved in the first multicast or the dynamically initiated transmission.

16. The method according to claim 14, further comprising using video buffering and an existing multicasting according to the predetermined schedule to play the video in slow motion at a request of a user without incurring additional resource expenditure by any server or network element involved in the first multicast or the dynamically initiated transmission.

17. The method according to claim 14, further comprising using video buffering and an existing multicasting according to the predetermined schedule to allow a user to 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 initiating an additional dynamically initiated transmission to provide a user with a precise seek to a new point in the video.

18. The method according to claim 4, wherein a length of the first portion is variable according to a greatest duration of the portion of the video that is needed by the dynamically admitted users.

19. 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 to the user and at least one additional user requesting for the video outside the predetermined schedule for the first multicasting in time to catch the beginning of the dynamically initiated multicasting;

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 or the video.

20. The method according to claim 19, 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.

21. The method according to claim 19, 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.

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

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

24. The method according to claim 19, wherein a length of the first portion is variable according to a greatest duration of the portion of the video that is needed by the dynamically admitted users.

25. 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) producing a statically scheduled multicast of the video to serve each user who requests for the video within a threshold time parameter prior to the beginning of the statically scheduled multicast of the video;

(c) sending a request toward a server to begin dynamically scheduling a new multicast for the video in response to requests for the video from a plurality of users that are not within the threshold time parameter prior to the beginning of the statically scheduled multicast of the video; 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 users to share and to receive the upcoming dynamically scheduled new multicast for the video, wherein the new multicast for the video includes less than the entire video;

(e) causing the user whose request is not within the threshold time parameter to receive and buffer an in-progress pre-scheduled multicast of the video and to receive playback of the dynamically scheduled new multicast for the video; and

causing the buffered portion of the pre-scheduled multicast of the video to be played for the user after the dynamically scheduled new multicast has caught up to the buffered portion of the video.

26. The method of claim 25, 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;

(h) arranging for the additional users to receive the upcoming dynamically scheduled new multicast for the video; and

(i) 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.

27. 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;

means for multicasting the dynamically initiated transmission of the portion of the video to a plurality of users requesting for the video in time to catch the beginning of the dynamically initiated multicast; 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.

28. The system according to claim 27, 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.

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

30. The system according to claim 27, 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.

31. The system according to claim 27, wherein the system further comprises means for determining a length of the first portion is variable according to a greatest duration of the portion of the video that is needed by the dynamically admitted users.

32. 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;

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

means for sharing the dynamically multicast portion of the video among a plurality of users requesting for the video in time to catch the beginning of the dynamically multicast 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.

33. The system according to claim 32, 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.

34. The system according to claim 32, 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.

35. The system according to claim 32, wherein the system further comprises means for determining a length of the first portion is variable according to a greatest duration of the portion of the video that is needed by the dynamically admitted users.

36. 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;

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 includes less than the entire video; and

means for sharing the dynamically scheduled new multicast for the video among a plurality of users requesting for the video in time to catch the beginning of the dynamically scheduled new multicast for the 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.

37. The system of claim 36, 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.

38. 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, the controller operable to control the at least one server to serve a user via either the video multicast according to the fixed predetermined schedule or the dynamically initiated transmission;

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, and

wherein the controller and the at least one server are further operable to, in response to user requests from a plurality of users for the video outside the video multicast according to the fixed predetermined schedule, direct the dynamically initiated transmission as a multicast to the plurality of users when the requests are made in time to catch the beginning of the dynamically initiated transmission multicast.

39. A video-on-demand system, comprising:

at least one server operable multicast a video to a network connected to users according to a fixed multicast schedule to deliver the video;

at least one prefix cache server in the network to store an initial prefix portion of each of available videos in the network including the video; and

a controller operable to control the at least one server and the one prefix cache server in delivering the video to the users,

wherein the controller is operable to serve the initial prefix portion of the video from the at least one prefix cache server to a user who requests for the video outside the fixed multicast schedule and to dynamically initiate transmission of at least a portion of the video to serve, at the end of the serving of the initial prefix portion of the video, the user who requests for the video outside the fixed multicast schedule, and

wherein the controller is further operable to use a buffered multicast of the video to serve the user who requests for the video outside the fixed multicast schedule and to stop serving the user from the dynamically initiated transmission.

40. The system as in claim 39, wherein the controller and the at least one server are further operable to, in response to requests from a plurality of users for the video outside the video multicast according to the fixed multicast schedule, direct the dynamically initiated transmission as a multicast to the plurality of users when the requests are made in time to catch the beginning of the dynamically initiated transmission multicast.

41. 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,

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.

42. 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,

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.

43. 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,

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.

44. 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,

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.

45. 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,

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.

46. 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;

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,

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

accepting expected user arrival rates; and

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

wherein sufficiency of proposed system parameters can be approximately determined.

47. 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, and

wherein the dynamically multicasting is a patching multicasting used in connection with multiple prefix servers.

48. 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,

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 preassigned 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.