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.

Description:
TECHNICAL FIELD 
     The present invention relates in general to cable TV systems, and in particular, to video on demand and near video on demand systems. 
     BACKGROUND INFORMATION 
     One of the important offerings of an interactive cable TV (&#34;ITV&#34;) system is providing customers with the opportunity for ordering movies for viewing on their cable-attached televisions. There are two methods of delivering these movies. One is called Video on Demand (&#34;VOD&#34;), where the customer selects a title from a number of movies using a menu on the TV screen, and the movie is presented for immediate viewing. In a variation of the VOD case, a few movies are offered at specific times. This is called Near Video on Demand (&#34;NVOD&#34;). In both cases, the movies must be stored by the cable companies in such a way that customers have access to them. Today, a likely way of providing movies for customer viewing is to digitize them and store them on a form of computer called a video server. 
     Given the hierarchical nature of a cable system, there are numerous locations that could be used for storing movies. FIG. 1 illustrates the structure of a typical cable TV system. Neighborhoods (cells) are serviced by hubs and the hubs are connected to a headend. Headends could be interconnected and connected upstream to more centralized asset providers (not shown) containing video servers. 
     FIG. 2 illustrates a generalized system with n levels of interconnectivity. Movies for customer access could be stored in the hubs, the point closest to the customer. This theoretically would have the lowest connectivity costs, but movies of interest would have to be replicated at each hub. Connectivity costs include: 
     Network equipment 
     Switches 
     Gateways 
     Concentrators 
     Routers 
     Bridges 
     Adapters 
     etc. 
     Costs associated with the physical connection 
     Wire 
     Fiber optics 
     Repeaters 
     Transformers 
     Receivers 
     Satellite dishes 
     etc. 
     Bandwidth and network usage 
     Tariffs 
     Access charges 
     Management overhead 
     etc. 
     An option would be to store movies at the next highest group of nodes in the distribution tree. Connectivity costs would probably be more than for hub connectivity, but the movies would be replicated fewer times. This pattern continues as one moves up the cable system hierarchy towards the headend--higher connectivity costs and lower storage costs. 
     A cable company operator needs to determine the best way to distribute movie storage to minimize the overall system costs. Assuming connectivity costs are only incurred during movie viewing and connectivity costs rise as the distance from server to user increases, it is practical to assume that the most popular movies should be placed nearest to the customer at the hub. Less popular movies should be stored at higher nodes in the system. The problem becomes one of trading connectivity costs for storage costs, and then determining at what point the minimum overall cost occurs. The prior art has examined this problem by proposing complex models based on network traffic, viewer patterns, and other parameters. This invention proposes a more simple model based on movie popularity, storage costs, and connectivity costs. 
     SUMMARY OF THE INVENTION 
     The foregoing need is addressed by the present invention which provides a system and method for determining an optimal distribution of a plurality of movies within N levels of interconnected servers as a function of storage cost, connection cost, and selection probability of the movies. 
     More specifically, in a system having at least one headend server, and at least one hub server, and N levels of interconnected computer servers between and including the at least one headend server and at least one hub server, the system stores a plurality of movies, receives a storage cost for each one of the plurality movies at each of the levels of the system, receives a connection cost of the each of the levels to an end user, and receives a selection probability of each of the movies. The system then determines the optimal distribution throughout the N levels of interconnected servers as a function of the storage cost, connection cost and selection probability. Movies are then distributed in accordance with the calculated distribution. 
     The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which: 
     FIG. 1 illustrates a typical cable TV topology; 
     FIG. 2 illustrates an N-level cable TV system; 
     FIG. 3 illustrates a 2-level distributed video server system; 
     FIG. 4 illustrates a 3-level distributed video server system; 
     FIG. 5 illustrates a configuration of a server in accordance with the present invention; and 
     FIG. 6 illustrates a flow diagram of an embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION 
     In the following description, numerous specific details are set forth to provide a thorough understanding of the present invention. However, it will be obvious to those skilled in the art that the present invention may be practiced without such specific details. In other instances, well-known circuits have been shown in block diagram form in order not to obscure the present invention in unnecessary detail. For the most part, details concerning timing considerations and the like have been omitted inasmuch as such details are not necessary to obtain a complete understanding of the present invention and are within the skills of persons of ordinary skill in the relevant art. 
     A representative hardware environment for practicing the present invention is depicted in FIG. 5, which illustrates a typical hardware configuration of server 513 in accordance with the subject invention having central processing unit (CPU) 510, such as a conventional microprocessor, and a number of other units interconnected via system bus 512. Server 513 includes random access memory (RAM) 514, read only memory (ROM) 516, and input/output (I/O) adapter 518 for connecting peripheral devices such as disk units 520 and tape drives 540 to bus 512, user interface adapter 522 for connecting keyboard 524, mouse 526, speaker 528, microphone 532, and/or other user interface devices such as a touch screen device (not shown) to bus 512, communication adapter 534 for connecting server 513 to a network of such video servers in the system illustrated in FIG. 2, and display adapter 536 for connecting bus 512 to display device 538. CPU 510 may include other circuitry not shown herein, which will include circuitry commonly found within a microprocessor, e.g., execution unit, bus interface unit, arithmetic logic unit, etc. CPU 510 may also reside on a single integrated circuit. 
     Server 513 may be located at any one or all of the nodes within the N-level cable TV system illustrated in FIG. 2. Each of servers 513 operates to distribute movies in accordance with the present invention, and specifically in accordance with the process illustrated in FIG. 6, which is further described below. Movies may be digitized and stored within any of the memory and storage means within any one or all of servers 513 in accordance with the distribution calculated in accordance with the present invention. As an example, any one particular movie may be stored within disk drive 520 or tape drive 540 on any particular server 513, and then delivered to an end user in response to a request for the movie from the end user through the communications adapter 534. 
     Referring next to FIG. 6, there is illustrated a flow diagram of a process for implementing the present invention. The illustrated process may be embodied in software and/or hardware within each of servers 513. The process begins at step 601, where M movies are stored within the cable TV system using well-known means. As noted above, the movies may be digitized and then stored within any one or a plurality of servers 513. Thereafter, in step 602, the cost of storage of a movie at level i is inputted into the system. Such an input may be performed using any one of the input means coupled to a server 513. Likewise, the cost of a connection from a level i to an end user is inputted into the system in step 603. Additionally, in step 604, the probability of a given movie being selected by an end user is inputted into the system. 
     Thereafter, in step 605, the optimal distribution of the M movies is determined in accordance with the algorithm further described below. The optimal distribution is determined as a function of the storage cost, connection cost, and selection probabilities inputted in steps 602-604. 
     Next, in step 606, each of the M movies is transferred and distributed throughout the cable TV system network in accordance with the distribution determined in step 605. The movies are stored at each of the servers 513. In step 607, a selected movie is played to an end user in response to a request from the end user for that particular movie. 
     The remainder of the discussion will pertain to an implementation of step 605. 
     The system cost C of implementing video servers in the interactive TV system represented by the illustration in FIG. 2 is composed of two components, C d  the cost of the disk storage, and C s  the cost of the connection stream from that storage to the end user. Hence 
     
         C=C.sub.d +C.sub.s                                         (1) 
    
     Assuming the ITV system is implemented in a multi-level hierarchy with the potential of having servers at every level, the total cost for the storage becomes ##EQU1## where n is the number of levels numbered starting from 1 at the root and going to n, the end-user level. N i  is the number of nodes on level i, and m i  is the number of movies stored at each node on the i th  level. The average length (duration) of a movie is l, r is the encoding rate, and d i  is the cost of the storage for level i. Assuming that movies are not replicated across levels, M, the total number of unique movies stored in the system is ##EQU2## 
     The total cost of the video connections from servers to an end-user is ##EQU3## where N n  is the number of nodes in the user level and c n  is the number of active connections per node. The probability of selecting a movie stored on the i th  level is P i  with the cost of that connection being s i . And, ##EQU4## 
     Therefore from equation (1), the total system cost is ##EQU5## 
     To find the optimum number of movies to store at each level to minimize the system cost, one needs to find ##EQU6## and solve for each m i . This yields a system of nonlinear equations subject to a constraint, the equations being the first derivatives of the cost function with respect to the number of movies at each level. The constraint is that the number of all unique movies on the n levels sums to M as in equation (3). 
     Consider the exemplary 2-level cable system illustrated in FIG. 3. For this example, n=2, equation (5) becomes 
     
         C=lr(N.sub.1 m.sub.1 d.sub.1 +N.sub.2 m.sub.2 d.sub.2)+N.sub.2 c.sub.2 (P.sub.1 s.sub.1 +P.sub.2 s.sub.2)                        (7) 
    
     One challenge of using this model is determining the selection probability of a given movie. An approach is to assume that movie selection follows Zipf&#39;s law (please refer to Chen, Y. S. and Chong, P., &#34;Mathematical Modeling of Empirical Laws in Computer Applications: A Case Study,&#34; Computer Mathematics Applications, October 1992 and Chervenak, A. L., &#34;Tertiary Storage: An Evaluation of New Applications,&#34; PhD thesis, Univ. of California, Berkley, December 1994 for a further discussion of Zipf&#39;s law) that is; given M movies of interest, ordered by popularity, the probability of the i th  movie being requested is ##EQU7## where ##EQU8## Assuming Zipfs law applies to this example, ##EQU9## and 
     
         P.sub.2 =1-P.sub.1                                         (11) 
    
     Now, simultaneously solve equation (6) for m 1 , the movies at the headend, and m 2 , the movies replicated in the hubs, ##EQU10## This yields ##EQU11## for M, the total number of movies. 
     Consider an exemplary three-level server system composed of a central depository, cable headends, and neighborhood hubs as illustrated in FIG. 4. Using the cost equation (5), the cost of such a system is 
     
         lr(N.sub.1 m.sub.1 d.sub.1 +N.sub.2 m.sub.2 d.sub.2 +N.sub.3 m.sub.3 d.sub.3)+N.sub.3 c.sub.3 (P.sub.1 s.sub.1 +P.sub.2 s.sub.2 +P.sub.3 s.sub.3)                                                  (15) 
    
     Applying Zipf&#39;s law and making the suggested approximations: ##EQU12## Note that the approximations become more accurate as the m i  become large. 
     The problem becomes one of solving the system of nonlinear simultaneous equations ##EQU13## subject to the constraint M=m 1  +m 2  +m 3 . 
     Lagrange&#39;s Method (please refer to Taylor, Angus E. and Mann, W. Robert, &#34;Advanced Calculus,&#34; Second Edition, John Wiley and Sons, 1972) can be used to find the extremal values of a cost function, F(x 1 , x 2 , . . . , x n ) subject to a constraint G(x 1 , x 2 , . . . , x n ). 
     First, form the function 
     
         u=F(x.sub.1, x.sub.2, . . . , x.sub.n)+λG(x.sub.1, x.sub.2, . . . , x.sub.n)                                                  (20) 
    
     where λ is Lagrange&#39;s multiplier, an unknown constant. Next, form a system of n+1 equations composed of ##EQU14## where K is the value of the constraint equation. The solutions (x 1 , x 2 , . . . , x n , λ) provide (x 1 , x 2 , . . . , x n ) a minimal point of F(x 1 , x 2 , . . . , x n ). 
     The equations rendered by Lagrange&#39;s method are often too complex to be solved explicitly so solutions must be obtained numerically. One such approach is Newton&#39;s Iterative Method (please refer to Shoup, Terry E., &#34;Numerical Methods for the Personal Computer,&#34; Prentice-Hall, Inc., 1983). 
     Given a set of equations of the form: 
     
         ƒ.sub.1 (x.sub.1, x.sub.2, . . . , x.sub.n)=0 
    
     
         ƒ.sub.2 (x.sub.1, x.sub.2, . . . , x.sub.n)=0 
    
     
         ƒ.sub.n (x.sub.1, x.sub.2, . . . , x.sub.n)=0     (22) 
    
     a solution, (x 1 , x 2 , . . . , x n ) is to be found. 
     First, an initial guess for (x 1 , x 2 , . . . , x n ) is made, then that guess is used to solve for the delta matrix in ##EQU15## 
     The solutions are used to update the initial guess, 
     
         x.sub.1 =x.sub.1 Δx.sub.1 
    
     
         x.sub.2 =x.sub.2 +Δx.sub.2 
    
     
         x.sub.n =x.sub.n +Δx.sub.n                           (24) 
    
     The process is repeated until (x 1 , x 2 , . . . , x n ) converges, i.e., all |Δx i  | become smaller than a desired ε. 
     A modification technique called damped Newton (please refer to Conte, Samuel D. and de Boor, Carl, &#34;Elementary Numerical Analysis: An Algorithmic Approach,&#34; McGraw-Hill, 1980) is often used to avoid instabilities in the convergence process. Instead of adding the full value of the correcting Δx i  &#39;s provided by an iteration of the Newton technique, a fraction of the Δx i  &#39;s are added ##EQU16## j is chosen so that the residual error δ is minimized. The residual error is found by ##EQU17## 
     The F part of equation (20) is the cost of the three-level system (15). The constraint part of equation (20) becomes the sum of the movies at the three levels 
     
         G=m.sub.1 +m.sub.2 +m.sub.3 =M                             (27) 
    
     Then, forming u from equation (20): ##EQU18## Now, solve ##EQU19## for m 1 , m 2 , m 3 , and λ. 
     This is done by using Newton&#39;s method, iteratively computing ##EQU20## using ##EQU21## until all Δm i  and Δλ&lt;ε. 
     As with any numerical process, using Newton&#39;s method involves a certain number of practical considerations. For example, a crucial element of getting successful convergence inside the range of allowable solutions is choosing a good set of starting values for the iterative process. An excellent method for finding starting values has been found. Scan through various values of m i , summing to M, and then calculate the cost of that server distribution. Use the one that produces the lowest cost to seed the iterative process. This can be an iterative process, i.e., continually decrease the granularity of the scan routine until successful starting values are selected. 
     The following is a pseudo code segment for the scan procedure. (It should be noted that for systems with small n and small M, it may be easier to extend this initial guessing procedure to checking all possible distributions explicitly, i.e. increment=1, and not even try to solve the equations numerically.) ##EQU22## Attempt to solve using Newton&#39;s Method if no convergence, then decrease increment until convergence 
     Occasionally during Newton&#39;s Method, values for some of the m i  &#39;s will oscillate around zero and increase in value while the other values converge. It was found that such oscillation is an indication that the proper value of m i  is zero. 
     Another situation can occur in which the starting values contain zero or negative values for all but one of the m i  &#39;s. It was found that in this case, setting these values to zero and setting the other value to M provided the optimal distribution. 
     Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.