Systems and methods for providing video-on-demand services for broadcasting systems

• US 6,557,030 B1
• Filed: 05/31/2000
• Issued: 04/29/2003
• Est. Priority Date: 05/31/2000
• Status: Expired due to Fees

• Current Assignee: PrediWave Corp.
• Original Assignee: PrediWave Corp.
• Inventors: Hoang, Khoi
• Primary Examiner(s): Luu, Le Hien
• Assistant Examiner(s): WILLETT, STEPHAN F
• Application Number:
  US09/584,832
• Time in Patent Office: 1,063 Days
• Field of Search: 709/203, 709/219, 709/231, 709/232, 709/234, 707/102, 707/104.1, 725/95, 725/97, 725/145
• US Class Current: 709/217
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 65/613 for the control of the source by the destination control signals issued by the client directed to the server or network components specially adapted for selective content distribution H04N21/637
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• 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/262 Content or additional data distribution scheduling, e.g. sending additional data at off-peak times, updating software modules, calculating the carousel transmission frequency, delaying a video stream transmission, generating play-lists scheduling strategies for dispatcher in multiprogramming arrangements G06F9/4881; arrangements for scheduling broadcast services or broadcast-related services H04H60/06; flow control in packet networks H04L47/10; establishing a time schedule or organising the servicing of application requests H04L67/62
• CPC Class Codes: H04N 21/26216 involving the channel capacity, e.g. network bandwidth admission control, resource allocation in open networks H04L12/5692; flow control in packet networks H04L47/10; establishing a schedule or organising the servicing of application requests taking into account QoS H04L67/61
• CPC Class Codes: H04N 21/26233 involving content or additional data duration or size, e.g. length of a movie, size of an executable file
• CPC Class Codes: H04N 21/26241 involving the time of distribution, e.g. the best time of the day for inserting an advertisement or airing a children program
• 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/4181 for conditional access
• CPC Class Codes: H04N 21/4331 Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 21/472 End-user interface for requesting content, additional data or services; End-user interface for interacting with content, e.g. for content reservation or setting reminders, for requesting event notification, for manipulating displayed content end-user interfaces for retrieving video data from a database G06F16/739; network services for supporting unicast streaming H04L65/612
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/482 End-user interface for program selection broadcast systems using EPGs H04H60/72
• CPC Class Codes: H04N 21/84 Generation or processing of descriptive data, e.g. content descriptors systems specially adapted for using meta-information in broadcast systems H04H60/73
• CPC Class Codes: H04N 21/845 Structuring of content, e.g. decomposing content into time segments
• CPC Class Codes: H04N 7/17318 : Direct or substantially direct transmission and handling of requests
• CPC Class Codes: Y10S 707/99945 : Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 : Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method for sending data to a client to provide data-on-demand services comprises the steps of: receiving a data file, specifying a time interval, parsing the data file into a plurality of data blocks based on the time interval such that each data block is displayable during a time interval, determining a required number of time slots to send the data file, allocating to each time slot at least a first of the plurality of data blocks and optionally one or more additional data blocks, such that starting from any of the time slots, (i) the data file can be displayed by accessing the first of the plurality of data blocks; (ii) at a consecutive time slot, a next data block sequential to a prior displayed data block is available for displaying; and (iii) repeating step (ii) until all of the plurality of data blocks for the data file has been displayed, and sending the plurality of data blocks based on the allocating step.

Claims

1. A method for generating a scheduling matrix for a data file, said scheduling matrix provides a send order for sending data blocks of a data file, such that said data blocks are available in sequential order to a client receiving said data blocks, said method of comprising the steps of:

(a) receiving a number [x], wherein said number [x] is a number into which said data file is divided;

(b) setting a first variable [j] to zero;

(c) setting a second variable [i] to zero;

(d) clearing all entries in a reference array;

(e) writing into said reference array at least one data block stored in matrix positions of a column [(i+j) modulo x, j] of said scheduling matrix, if said reference array does not contain said at least one data block;

(f) writing a data block [i] into said reference array and a matrix position [(i+j) modulo x, j] of said scheduling matrix, if said reference array does not contain said data block [i];

(g) incrementing said second variable [i] by one and repeating step (e) through step (g) until said second variable [i] is equal to said number [x]; and

(h) incrementing said first variable [j] by one and repeating said step (c) through step (h) until said first variable [j] is equal to said number [x].

2. The method of claim 1, further comprising the steps of:

(i) repeating said steps (a) to (h) to generate a set of scheduling matrices for a set of data files; and

applying a convolution method to generate a delivery matrix based on said set of scheduling matrices for sending said set of data files.

3. A method of calculating a delivery matrix, said delivery-matrix provides a send order for sending data blocks of a set of data files, said method comprising the steps of:

(a) calculating a scheduling matrix for each corresponding data file in a set of data files to form a set of scheduling matrices, wherein;

said scheduling matrix sends out said data blocks using a pattern based on a number [x] into which said each corresponding data file is divided; and

said pattern allows for said data blocks in said each corresponding data file to be accessible in a sequential order at a random time;

(b) generating an identification array containing an identification for each of said set of data files; and

(c) combining said set of scheduling matrices and said identification array to generate a delivery matrix for said set of data files.

4. The method of claim 3, wherein said combining includes the step of using a convolution method.

5. A computer implemented on-demand data broadcast method comprising the act of preparing a delivery matrix defining a data transmission sequence suitable for broadcast, to a plurality of clients, on-demand data in a non client specific manner, wherein transmission of said on-demand data files requires an amount of transmission bandwidth that is independent of the number of said plurality of clients.

6. A computer implemented method as recited in claim 5, wherein the act of generating a delivery matrix comprises the act of:

preparing a first scheduling matrix suitable for transmission of a first data file, said first data file being represented by a first plurality of data blocks, said first scheduling matrix providing a first sequence for transmitting said first plurality of data blocks sequentially within time slots in a manner such that any client receiving transmission of said first data file according to said first scheduling matrix may begin accessing said first data file within one time slot.

7. A computer implemented method as recited in claim 6, wherein the act of preparing a delivery matrix further includes the acts of:

preparing a second scheduling matrix suitable for transmission of a second data file, said second data file being represented by a second plurality of data blocks, said second scheduling matrix providing a second sequence for transmitting said second plurality of data blocks sequentially within time slots in a manner such that any client receiving transmission of said second data file according to said second scheduling matrix may begin accessing said second data file within one time slot; and

generating said delivery matrix through a combination of said first and second scheduling matrices.

8. A computer implemented universal data broadcast method as recited in claim 5 further comprising the act of preparing an electronic program guide (EPG) suitable for broadcast to said plurality of clients.

9. A computer implemented method as recited in claim 5, wherein said on-demand data includes video data.

10. A computer implemented method as recited in claim 5, wherein said on-demand data includes game data.