System for video server using coarse-grained disk striping method in which incoming requests are scheduled and rescheduled based on availability of bandwidth

• US 5,826,110 A
• Filed: 06/19/1995
• Issued: 10/20/1998
• Est. Priority Date: 06/19/1995
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rastogi, Rajeev, Ozden, Banu, Silberschatz, Abraham
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Kim, Ki S.
• Application Number:
  US08/492,315
• Time in Patent Office: 1,219 Days
• Field of Search: 395/115, 395/200.09, 395/650, 395/826, 395/494, 395/859, 395/865, 348/7, 455/5.1, 369/30, 364/514 A, 364/251.1, 364/253.2
• US Class Current: 710/45
• CPC Class Codes: G11B 27/002 Programmed access in sequence to a plurality of record carriers or indexed parts, e.g. tracks, thereof, e.g. for editing; transfer of record carriers from magazine G11B15/68, G11B17/10; G11B17/22
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A method for retrieving video data which has been striped across a plurality of disks using a coarse-grained striping technique. Specifically, and in accordance with an illustrative embodiment of the present invention, the method comprises scheduling the retrieval of a video in response to an incoming request and based on the availability of bandwidth on the disks, and then rescheduling the retrieval of that video to occur at an earlier time, the rescheduling based on a change (i.e., an increase) in the availability of bandwidth on the disks which results from the retrieval of another video being completed. The scheduling and rescheduling may, for example, comprise assigning a disk to the video, where the method further comprises incrementing the disk assigned to the video as each round occurs and beginning the retrieval of the given video when the disk assigned to it is the disk on which the data for the given video begins.

Claims

1. A method for servicing a plurality of incoming requests to retrieve a corresponding plurality of stored sequences of bits representing video information, each of the sequences of bits having been stored on a plurality of disks in accordance with a coarse-grained disk striping technique in which each of the stored sequences of bits is adapted to be retrieved in response to a corresponding request thereto and in a successive plurality of rounds including a first round, each of said rounds comprising the retrieval of a corresponding successive subsequence of said sequence of bits, each of said successive subsequences having been stored on exactly one of said disks, each of said disks having a bandwidth associated therewith, the method comprising the steps of:

scheduling the first round of the retrieval of one of said sequences of bits to occur at a first point in time, the scheduling performed in response to one of said incoming requests based on both the order in which said incoming requests are received and a measure of availability of said bandwidth associated with one or more of said disks; and

rescheduling the first round of said retrieval of said one of said sequences of bits to occur at a second point in time earlier than the first point in time, the rescheduling performed in response to a change in said measure of availability of said bandwidth associated with said one or more of said disks, said change in said measure of availability of said bandwidth resulting from a completion of the retrieval of another one of said sequences of bits.

2. The method of claim 1 wherein the plurality of disks has an ordering associated therewith, and wherein the step of scheduling and the step of rescheduling each comprises assigning one of said disks to said sequence of bits, the method further comprising the steps of:

incrementing the one of said disks assigned to said sequence of bits for each round of a retrieval of one or more other sequences of bits; and

beginning said retrieval of said sequence of bits when said sequence of bits has associated therewith the disk having the subsequence corresponding to the first round of the retrieval of said sequence of bits stored thereon, said step of beginning comprising performing the first round of said retrieval of said sequence of bits.

3. The method of claim I further comprising the step of retrieving the subsequence corresponding to the first round of the retrieval of said sequence of bits at said second point in time from one of said disks and the step of storing said subsequence in a buffer memory.

4. The method of claim 3 further comprising the step of transmitting said subsequence corresponding to the first round of the retrieval of said sequence of bits across a network to one or more requesters of said sequence of bits.

5. The method of claim 3 wherein the plurality of disks has an ordering associated therewith and wherein each of said successive subsequences of said sequence of bits has been stored on a correspondingly successive disk, the method further comprising the step of retrieving each of the subsequences corresponding to a round of the retrieval of said sequence of bits subsequent to said first round thereof and storing each of said subsequences in said buffer memory.

6. The method of claim 5 further comprising the step of transmitting each of said subsequences corresponding to a round of the retrieval of said sequence of bits across a network to one or more requesters of said sequence of bits.

7. A video server for servicing a plurality of incoming requests to retrieve a corresponding plurality of stored sequences of bits representing video information, the video server comprising:

a plurality of disks, each of said disks having a bandwidth associated therewith, each of said sequences of bits having been stored on the plurality of disks in accordance with a coarse-grained disk striping technique in which each of the stored sequences of bits is adapted to be retrieved in response to a corresponding request thereto and in a successive plurality of rounds including a first round, each of said rounds comprising the retrieval of a corresponding successive subsequence of said sequence of bits, each of said successive subsequences having been stored on exactly one of said disks;

means for scheduling the first round of the retrieval of one of said sequences of bits to occur at a first point in time, the means for scheduling responsive to one of said incoming requests, wherein said first point in time is based on both the order in which said incoming requests are received and a measure of availability of said bandwidth associated with one or more of said disks; and

means for rescheduling the first round of said retrieval of said one of said sequences of bits to occur at a second point in time earlier than the first point in time, the means for rescheduling responsive to a change in said measure of availability of said bandwidth associated with said one or more of said disks, said change in said measure of availability of said bandwidth resulting from a completion of the retrieval of another one of said sequences of bits.

8. The video server of claim 7 wherein the plurality of disks has an ordering associated therewith, and wherein the means for scheduling and the means for rescheduling each comprises means for assigning one of said disks to said sequence of bits, the video server further comprising:

means for incrementing the one of said disks assigned to said sequence of bits for each round of a retrieval of one or more other sequences of bits; and

means for beginning said retrieval of said sequence of bits when said sequence of bits has associated therewith the disk having the subsequence corresponding to the first round of the retrieval of said sequence of bits stored thereon, said means for beginning comprising means for performing the first round of said retrieval of said sequence of bits.

9. The video server of claim 7 further comprising means for retrieving the subsequence corresponding to the first round of the retrieval of said sequence of bits at said second point in time from one of said disks and means for storing said subsequence in a buffer memory.

10. The video server of claim 9 further comprising means for transmitting said subsequence corresponding to the first round of the retrieval of said sequence of bits across a network to one or more requesters of said sequence of bits.

11. The video server of claim 9 wherein the plurality of disks has an ordering associated therewith and wherein each of said successive subsequences of said sequence of bits has been stored on a correspondingly successive disk, the video server further comprising means for retrieving each of the subsequences corresponding to a round of the retrieval of said sequence of bits subsequent to said first round thereof and means for storing each of said subsequences in said buffer memory.

12. The video server of claim 11 further comprising means for transmitting each of said subsequences corresponding to a round of the retrieval of said sequence of bits across a network to one or more requesters of said sequence of bits.