Optimal movie distribution on video servers in an n-level interactive TV system

• US 5,916,303 A
• Filed: 05/21/1997
• Issued: 06/29/1999
• Est. Priority Date: 05/21/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Scott, Roderick Keith
• Primary Examiner(s): Faile, Andrew I.
• Assistant Examiner(s): Le, Uyen
• Application Number:
  US08/861,293
• Time in Patent Office: 769 Days
• Field of Search: 348/1, 348/3, 348/7, 348/12, 348/13, 455/2, 455/4.2, 455/5.1, 455/6.3, 395/200.47, 395/200.48, 395/200.49
• US Class Current: 709/217
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

Movies are distributed and stored within a movie on demand or near movie on demand system having a number of levels of interconnectivity between and including at least one headend and at least one hub serving a plurality of end users. Distribution is determined as a function of the storage cost of a movie at each level of the system, a connection cost of each level to an end user, and a selection probability of each of the movies. Distribution of the movies between the various servers in the cable system is performed in accordance with the calculated optimal distribution.

Claims

1. A method for distributing and storing movies within a movie on demand or near movie on demand system having i levels of interconnectivity between and including at least one head end and at least one hub serving a plurality of end-users, said method comprising the steps of:

inputting a storage cost of a movie at each level of said system;

inputting a connection cost of each level to an end-user;

inputting a selection probability of each of said movies;

determining an optimal distribution of said movies within said system as a function of said storage cost, said connection cost, and said selection probability; and

distributing said movies to various servers in said system in accordance with said determined optimal distribution, wherein said determining step further comprises the step of determining a minimal total storage and connection costs for each possible distribution of said movies in said system, wherein said step of determining said minimal total storage and connection costs for each possible distribution of said movies in said system comprises the step of calculating ##EQU23## wherein m_i is a number of said movies at each server on an ith level, wherein ##EQU24## wherein n is a number of levels numbered starting from 1 at a root and going to n, N_i is a number of nodes on level i, m_i is a number of movies stored at each node on the i^th level, l is an average length of a movie, r is an encoding rate, and d_i is a cost of storage for level i.

2. The method as recited in claim 1, further comprising the step of playing a selected one of said movies to said end-user in response to a request for said selected one of said movies by said end-user.

3. The method as recited in claim 1, wherein said inputting and determining steps are performed using one or more of said servers in said system.

4. The method as recited in claim 3, wherein each of said servers includes a data processing system comprising a processor and a memory.

5. A data processing system operable for distributing and storing movies within a movie on demand or near movie on demand system having i levels of interconnectivity between and including at least one head end and at least one hub serving a plurality of end-users, said system comprising:

circuitry for receiving a storage cost of a movie at each level of said system;

circuitry for receiving a connection cost of each level to an end-user;

circuitry for receiving a selection probability of each of said movies;

circuitry for determining an optimal distribution of said movies within said system as a function of said storage cost, said connection cost, and said selection probability; and

circuitry for distributing said movies to various servers in said system in accordance with said determined optimal distribution, wherein said determining circuitry further comprises circuitry for determining a minimal total storage and connection costs for each possible distribution of said movies in said system, wherein said circuitry for determining said minimal total storage and connection costs for each possible distribution of said movies in said system comprises circuitry for calculating ##EQU25## wherein m_i is a number of said movies at each server on an ith level, wherein ##EQU26## wherein n is a number of levels numbered starting from 1 at a root and going to n, N_i is a number of nodes on level i, m_i is a number of movies stored at each node on the i^th level, l is an average length of a movie, r is an encoding rate, and d_i is a cost of storage for level i.

6. The system as recited in claim 5, further comprising circuitry for playing a selected one of said movies to said end-user in response to a request for said selected one of said movies by said end-user.

7. The system as recited in claim 5, wherein said receiving and determining circuitry is located in one or more of said servers in said system.

8. A computer program product stored on a storage media and operable for distributing and storing movies within a movie on demand or near movie on demand system having i levels of interconnectivity between and including at least one head end and at least one hub serving a plurality of end-users, said computer program product comprising:

a plurality of binary values for receiving a storage cost of a movie at each level of said computer program product;

a plurality of binary values for receiving a connection cost of each level to an end-user;

a plurality of binary values for receiving a selection probability of each of said movies;

a plurality of binary values for determining an optimal distribution of said movies within said system as a function of said storage cost, said connection cost, and said selection probability; and

a plurality of binary values for distributing said movies to various servers in said system in accordance with said determined optimal distribution, wherein said determining circuitry further comprises a plurality of binary values for determining a minimal total storage and connection costs for each possible distribution of said movies in said system, wherein said plurality of binary values for determining said minimal total storage and connection costs for each possible distribution of said movies in said system comprises a plurality of binary values for calculating ##EQU27## wherein m_i is a number of said movies at each server on an ith level, wherein ##EQU28## wherein n is a number of levels numbered starting from 1 at a root and going to n, N_i is a number of nodes on level i, m_i is a number of movies stored at each node on the i^th level, l is an average length of a movie, r is an encoding rate, and d_i is a cost of storage for level i.

9. The computer program product as recited in claim 8, further comprising a plurality of binary values for playing a selected one of said movies to said end-user in response to a request for said selected one of said movies by said end-user.

10. A system comprising:

at least one head end server;

at least one hub server operable for serving a plurality of end-users;

i levels of interconnected computer servers between and including said at least one head end server and said at least one hub server, wherein said at least one head end server is at level 1, and wherein said hub server is at level i, wherein i is greater than or equal to 2;

circuitry for storing a plurality of movies;

circuitry for receiving a storage cost of a particular one of said plurality of movies at each of said i levels of said system;

circuitry for receiving a connection cost of each of said i levels to an end-user;

circuitry for receiving a selection probability of each of said plurality of movies;

circuitry for determining an optimal distribution of said plurality of movies within said i levels of interconnected servers as a function of said storage cost, said connection cost, and said selection probability; and

circuitry for distributing said plurality of movies to various servers in said i levels of interconnected servers in accordance with said determined optimal distribution, wherein said determining circuitry further comprises circuitry for determining a minimal total storage and connection costs for each possible distribution of said plurality of movies in said i levels of interconnected servers, wherein said circuitry for determining said minimal total storage and connection costs for each possible distribution of said plurality of movies in said i levels of interconnected servers comprises circuitry for calculating ##EQU29## wherein m_i is a number of s aid movies at each server on an ith level, wherein ##EQU30## wherein n is a number of levels numbered starting from 1 at a root and going to n, N_i is a number of nodes on level i, m_i is a number of movies stored at each node on the i^th level, l is an average length of a movie, r is an encoding rate, and d_i is a cost of storage for level i.

11. The system as recited in claim 10, further comprising circuitry for playing a selected one of said plurality of movies to an end-user in response to a request for said selected one of said plurality of movies by said end-user.

12. A method for distributing and storing movies within a movie on demand or near movie on demand system having i levels of interconnectivity between and including at least one head end and at least one hub serving a plurality of end-users, said method comprising the steps of:

inputting a storage cost of a movie at each level of said system;

inputting a connection cost of each level to an end-user;

inputting a selection probability of each of said movies;

inputting an average length of each said movie;

determining an optimal distribution of said movies within said system as a function of said storage cost, said connection cost, said selection probability, and said average length;

distributing said movies to various servers in said system in accordance with said determined optimal distribution; and

inputting an encoding rate, wherein said determining step also factors in said encoding rate, wherein storage cost equals ##EQU31## wherein n is a number of levels numbered starting from 1 at a root and going to n, an end-user level, wherein N_i is a number of nodes of level i, and m_i is a number of movies stored at each node on the i^th level, wherein an average length of a movie is l, r is the encoding rate, and d_i is a cost of storage for level i.

13. A method for distributing and storing movies within a movie on demand or near movie on demand system having i levels of interconnectivity between and including at least one head end and at least one hub serving a plurality of end-users, said method comprising the steps of:

inputting a storage cost of a movie at each level of said system;

inputting a connection cost of each level to an end-user;

inputting a selection probability of each of said movies;

inputting an average length of each said movie;

determining an optimal distribution of said movies within said system as a function of said storage cost, said connection cost, said selection probability, and said average length; and

distributing said movies to various servers in said system in accordance with said determined optimal distribution, wherein the connection costs equals ##EQU32## where N_n is a number of nodes in a user level and c_n is a number of active connections per node, wherein a probability of selecting a movie stored on an i^th level is P_i with a cost of that connection being s_i.