System for retrieving data in a video server

• US 6,415,328 B1
• Filed: 05/21/1998
• Issued: 07/02/2002
• Est. Priority Date: 05/26/1997
• Status: Expired due to Term

• Current Assignee: Gula Consulting Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Korst, Johannes H. M.
• Primary Examiner(s): WILEY, DAVID ARMAND
• Application Number:
  US09/083,693
• Time in Patent Office: 1,503 Days
• Field of Search: 348/7, 395/200.47, 395/200.48, 395/200.49, 395/200.09, 395/672, 395/826, 395/650, 709/217, 709/218, 709/219, 709/105, 709/230-237, 711/114, 711/157, 711/167-169
• US Class Current: 709/232
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: H04N 21/2326 Scheduling disk or memory reading operations

Abstract

In an audio/video server blocks of data are read from a storage medium by a reader and supplied to users in the form of data streams. The storage medium includes a plurality of storage units. The blocks are stored in at least two different and randomly selected storage units. A scheduler controls reading of blocks from the storage medium. For each block to be read, the scheduler selects one storage unit from the storage units in which the block is stored such that the playback load on the storage units is balanced. The scheduler issues a read request to the reader for reading the block from the selected storage unit.

Claims

1. A video server, comprising:

means for storing a predetermined selection of blocks multiple times in the storage medium by storing individual blocks of the selection in their entirety in a set of at least two different and substantially randomly selected storage units of the medium;

scheduler means for selecting from a corresponding set of all storage units in which the block is stored, one storage unit from which the block is to be read so as to balance the load on the plurality of storage units; and

for assigning a corresponding read request to the selected storage unit and

reader means for, in response to a block read request, reading the corresponding block from the assigned storage unit for supplying a corresponding data stream to a user.

2. A system as claimed in claim 1, wherein the scheduler means is for, in response to a request for fetching a block for a data stream, selecting from the corresponding set the storage unit which at that moment has a lowest load resulting from already assigned block read requests.

3. A system as claimed in claim 1, wherein the scheduler means is for balancing the load on the plurality of storage units by cyclically:

determining a group of blocks to be read within a next cycle;

performing the selecting and assigning for all blocks of the group such that the load on the plurality of storage units resulting from the assigned block read requests is balanced; and

causing the reader means to read the corresponding blocks from the assigned storage units.

4. A system as claimed in claim 3, wherein the scheduler means is for performing the selecting and assigning by processing the blocks of the group in sequence and for each block:

selecting from the corresponding set the storage unit which at that moment has a lowest load resulting from block read requests which have already been assigned for blocks of the group; and

assigning the corresponding block read request to the selected storage unit.

5. A system as claimed in claim 3, wherein the scheduler means is for selecting, for each of the blocks of the group, a preliminary storage unit and assign the corresponding block read request to the preliminary selected storage unit, and for iteratively re-selecting a storage unit and re-assigning the corresponding block read request until a predetermined condition is met, by processing the blocks of the group in sequence and for each block:

selecting from the corresponding set the storage unit which at that moment has a lowest load resulting from block read requests which have already been assigned for blocks of the group; and

assigning the corresponding block read request to the selected storage unit.

6. A system as claimed in claim 5, wherein the condition is that a maximum load on at least one of the storage units is the same as a maximum load on at least one of the storage units at the end of a previous iteration.

7. A system as claimed in claim 3, wherein the scheduler means is for selecting, for each of the blocks of the group, a preliminary storage unit and assigning the corresponding block read request to the preliminary selected storage unit, and, for re-selecting for blocks of the group, a storage unit and re-assigning the corresponding block read request by:

determining whether a maximum load resulting from the preliminary assignment of block read requests can be lowered by k units, by;

solving a maximum flow problem by calculating a maximum flow from a source to a drain through a network of nodes n_i, wherein for each storage unit s_i, a corresponding node n_i is defined;

the source is connected to each node n_i via a corresponding arc with a capacity of max(k+l_i−

l_max,

     0), where l_i corresponds to a load on storage unit s_i resulting from the block read requests which have been preliminary assigned to s_i and l_max=max{l_i};

each node n_i is connected to n_j (n_i≠

n_j) via a corresponding arc with a capacity corresponding to the number of blocks which are stored in both s_i and s_j and for which the corresponding block read request has been assigned to s_i; and

each node n_i is connected to the drain via a corresponding arc with a capacity of max(l_max−

l_i−

k,

     0); and

deciding that the maximum load can be lowered by k units if a calculated maximum flow through the network is such that the flow from the source to each node n_i equals max(k+l_i−

l_max,

     0); and

if the maximum load can be lowered by k units, re-assigning a number of block read requests from s_i to s_j (s_i≠

s_j) that equals the resulting calculated flow from n_i to n_j.

8. A system as claimed in claim 3, wherein the scheduler means is for selecting, for each of the blocks of the group, a preliminary storage unit and assigning the corresponding block read request to the preliminary selected storage unit, and, for blocks of the group, for re-selecting a storage unit and re-assigning the corresponding block read request by:

iteratively;

selecting a storage unit si with a load on s_i being equal to a maximum load l_max on the plurality of storage units, where the loads result from currently assigned block read requests;

determining whether a path exists from s_i to a storage unit s_j with a load less than l^max−

1, where the path is formed by a sequence of storage units s_p1, s_p2, . . . , s_p1, with s_i=s_p1 and s_j=s_p1 and wherein for each pair s_pk, s_p(k+1) a block read request can be reassigned from s_pk to s_p(k+1), with k ranging from 1 to 1-1; and

if a path exists;

reassigning a block read request from s_pk to s_p(k+1) for k ranging from 1 to 1-1;

until no path exists.

9. A system as claimed in claim 1, wherein the blocks relate to a plurality of titles, each title comprising a sequence of data blocks and being associated with a predetermined multiplication factor;

the multiplication factor of a title relating to a ratio of the number of blocks stored in the storage medium for the title and the number of blocks of the title.

10. A system as claimed in claim 8, wherein the multiplication factor of a title determines how many times individual blocks of the title are stored in the storage medium and/or which percentage of blocks of the title are stored multiple times in the storage medium.