Baton passing optimization scheme for load balancing/configuration planning in a video-on-demand computer system

• US 5,544,313 A
• Filed: 05/11/1994
• Issued: 08/06/1996
• Est. Priority Date: 05/11/1994
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Shachnai, Hadas, Wolf, Joel L., Yu, Philip S.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Chen, Duo
• Application Number:
  US08/241,087
• Time in Patent Office: 818 Days
• Field of Search: 395/650, 395/6, 395/600, 395/486, 395/275, 395/444, 380/20, 348/7, 364/401
• US Class Current: 725/92
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends
• 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 video on demand computer system includes a plurality of storage media each storing a plurality of videos. The storage media are disks attached to a computer system. The computer system plays the videos on demand by reading out the videos from the disks as data steams to play selected ones of the videos for users responsive to received user performance requests. The computer system is programmed to monitor the numbers of videos being performed for each of the disks. Based on the monitoring function performed by the computer system, the computer system performs a load balancing function by transferring the performance of a video in progress from one of the disks to another disk having a copy of the video in progress. The computer system periodically performs a reassignment function to transfer videos between the disks to optimize load balancing based on the user performance requests for each of the videos. There are two phases to the load balancing performed by the computer system; a static phase and a dynamic phase. In the static phase, videos are assigned to memory and disks, and in the dynamic phase there is provided a scheme for playing videos with minimal and balanced loads on the disks. The static phase supports the dynamic phase which insures optimal real-time operation of the system. Dynamic phase load balancing is accomplished by a process of baton passing.

Claims

1. A video on demand computer system, comprising:

a multimedia file server having memory for storing a limited number of videos;

a plurality of storage media connected to said multimedia file server, each of said storage media storing a plurality of videos; and

performance means, connected said multimedia file server, for performing selected ones of the videos for users responsive to received user performance request;

said multimedia file server including a central processing unit programmed to monitor numbers of videos being performed for each of the storage media and, based on the programmed monitoring operation, dynamically transferring the performance of a video in progress from one of the storage media to another storage media having a copy of the video in progress so as to balance the loads of the plurality of storage media wherein said central processing unit is further programmed to periodically perform a static reassignment of videos between said system memory and the storage media and between the storage media by transferring videos between memory and the storage media and between the storage media to optimize load balancing based on the user performance requests for each of the videos.

2. The computer system of claim 1 wherein said central processing unit performs load balancing between any pair of storage media through a sequence of load shifts across different storage media such that each shift causes the transfer of the performance of a video from one of the storage media (the source) to another storage media (the target) having a copy of the video being shifted and the source storage media becomes the target storage media for the next load shift.

3. The computer system of claim 2 wherein the load balancing performed by said central processor is by balancing loads across the storage media through balancing loads between pairs of overloaded and underloaded storage media.

4. The computer system of claim 2 wherein the static reassignment of videos by the central processor is performed by assigning videos to storage media to increase the availability of load shift sequences between any pair of storage media and shortening the length of a sequence.

5. The computer system of claim 1 further comprising configuration planning means to decide system memory and storage media requirement for a predetermined number of videos to minimize cost of the system.

6. A method of providing videos on demand in a multimedia computer system comprising the steps of:

assigning videos to system memory and a plurality of storage media according to forecasts of demands for videos, each of said storage media storing a plurality of videos, said assigning including determining a number of copies of each video to be stored in said storage media with only one copy of any video on a single storage media;

performing selected ones of the videos for users on demand in response to user performance request;

monitoring numbers of videos being performed for each of the storage media;

dynamically balancing the loads of said storage media by transferring the performance of a video in progress from one of the storage media to another storage media having a copy of the video in progress; and

periodically performing a static reassignment of videos between said system memory and the storage media and between the storage media by transferring videos between memory and the storage media and between the storage media to optimize load balancing based on the user performance requests for each of the videos.

7. The method of claim 6 wherein the step of dynamic load balancing is performed through a sequence of load shifts across different storage media such that each shift causes the transfer of the performance of a video from one of the storage media (the source) to another storage media (the target) having a copy of the video being shifted and the source storage media becomes the target storage media for the next load shift.

8. The method of claim 7 wherein the step of dynamic load balancing is further performed by balancing loads between pairs of overloaded and underloaded storage media.

9. The method of claim 7 wherein the step of performing a static reassignment is performed by assigning videos to storage media to increase the availability of load shift sequences between any pair of storage media and shortening the length of a sequence.