Method of allocating multiple users to a multiple user data distribution system

• US 5,913,026 A
• Filed: 04/24/1997
• Issued: 06/15/1999
• Est. Priority Date: 07/19/1994
• Status: Expired due to Term

• Current Assignee: Sarnoff Corporation (SRI International, Inc.)
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Chin, Danny, Kaba, James Timothy Christopher, Bleidt, Robert
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Perveen, Rehana
• Application Number:
  US08/847,591
• Time in Patent Office: 782 Days
• Field of Search: 395/200.31, 395/856, 395/821, 395/861, 395/865, 395/876
• US Class Current: 709/201
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G11B 2220/412 Distributed storage methods, i.e. the system may autonomously determine for a storage device that provides enough storage capacity for recording
• CPC Class Codes: H04N 21/226 Characteristics of the server or Internal components of the server
• CPC Class Codes: H04N 21/2318 using striping
• CPC Class Codes: H04N 21/2387 Stream processing in response to a playback request from an end-user, e.g. for trick-play
• CPC Class Codes: H04N 21/2396 characterized by admission policies admission control, resource allocation in open networks H04L12/5692; arrangements for network security using user profiles for access control H04L63/102; access security in wireless networks H04W12/08
• CPC Class Codes: H04N 21/6377 directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 21/658 Transmission by the client directed to the server
• CPC Class Codes: H04N 21/6587 Control parameters, e.g. trick play commands, viewpoint selection
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments

Abstract

A method for allocating multiple users to a multiple user data distribution system. More specifically, a data retrieval method for dynamically allocating multiple users to a plurality of parallel processors each connected to an information storage device in a multiple user distribution system. The method allocates each user to at least one processor. The allocated processor represents a slot within a service period. The service period comprises a plurality of slots such that within a given slot an allocated user accesses a subset of information storage devices to supply data to the user. The users are dynamically allocated to the slots in a service period such that the specific time at which each user is serviced and the subset of information storage devices that services them varies from service period to service period. However, each user is serviced during each service period. The allocation of the user within a service period is defined by the user'"'"'s present mode of operation and next mode of operation, i.e., the mode the user will use in the next service period. Additionally, the method provides error detection and correction for the data retrieved from the information storage devices. Furthermore, the method enables new data to be added to the information storage devices during each service period and permits a select number of information storage devices, such as disk drives, to be recalibrated without impacting the operation of the system.

Claims

1. In a multiple user data distribution system containing a parallel processing computer having a plurality of parallel processors each connected to a information storage device, wherein said multiple user data distribution system supplies data, in response to user commands, to a plurality of users, a method for dynamically allocating said plurality of users to said multiple user data distribution system comprising the steps of:

allocating each of the users within the plurality of users to at least one processor within said plurality of parallel processors such that said allocated processor represents a slot within a service period comprised of a plurality of slots;

accessing, for each of the users and in response to user commands and using said allocated processor, a specified discrete segment of data within an information storage device associated with the allocated processor;

supplying each of said users with said respective specified discrete segment of data;

reallocating each of said users to a different processor representing a different slot within a subsequent service period depending upon a present mode of operation selected by each of the users; and

repeating said accessing, storing and reallocating steps to produce a continuous stream of accessed discrete segments of data for said users.

2. The method of claim 1 wherein said accessing, supplying and reallocating steps define sequential service periods during which each user is supplied data.

3. The method of claim 2 wherein said reallocating step additionally reallocates each of said users on the basis of a selected mode of operation for each of the users for implementation in a subsequent service period.

4. The method of claim 2 wherein said reallocating step further comprises the steps of:

updating, in response to any changes of the mode of operation selected by any of the users, a global allocation table containing user modes of operation and information storage device address locations for the data segments to be accessed;

comparing the mode of operation used in the present service period with the mode of operation in the global allocation table;

prioritizing each of the users based upon results of the comparing step; and

reallocating the users to processors based upon the prioritization of the users.

5. The method of claim 4 wherein said prioritization is performed by determining, in response to the mode of operation selected by each user, a time and disk criticality for the discrete segment of data to be provided to each user.

6. The method of claim 2 wherein each of the users are allocated and reallocated to a subset of the plurality of processors and information storage devices such that data is accessed from said subset of the plurality of information storage devices, the accessed data from each information storage devices in the subset of information storage devices is concatenated to form a data element.

7. The method of claim 6 further comprising the steps of:

repetitively accessing said information storage devices within each subset to produce a series of data elements representing a block of data segments for each of the users; and

supplying the series of data elements to each of the users.

8. The method of claim 7 wherein said supplying step further comprises the steps of:

storing said series of data elements for each user in memory;

recalling said series of data elements from memory; and

reordering, as the data elements are recalled, the series of data elements into a predefined order.

9. The method of claim 8 further comprising the steps of:

multiplexing the series of data elements having a predefined order;

transmitting the multiplexed data to the users.

10. The method of claim 2 wherein said accessing step further comprises the steps of:

detecting errors in the data element accessed from each of the subsets of information storage devices;

correcting the detected errors.

11. The method of claim 7 wherein each of said data elements includes parity information and said correcting step further comprises the step of using the parity information to correct the detected errors.

12. The method of claim 11 wherein the parity information is stored in one of the information storage devices forming each of the subsets of information storage devices and said parity information is derived from data information contained in the other information storage devices in each of the subsets of information storage devices.

13. The method of claim 6 further comprising the steps of:

selecting one subset of information storage device for recalibration;

recalibrating said selected subset of information storage devices while the remaining processors access data elements within their associated information storage device.

14. The method of claim 6 further comprising the steps of:

providing a new stream of continuous discrete segments of data;

storing, during a service period, said new stream of continuous discrete segments of data within said information storage devices while, during the same service period, said processors supply data segments to the users.