Method of striping a data stream onto subsets of storage devices in a multiple user data distribution system

• US 5,920,702 A
• Filed: 04/24/1997
• Issued: 07/06/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, Bleidt, Robert, Kaba, James Timothy Christopher
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Perveen, Rehana
• Application Number:
  US08/847,590
• Time in Patent Office: 803 Days
• Field of Search: 395/441, 395/439, 395/182.04, 395/438, 395/200.61, 395/200.76, 395/886, 395/850, 348/7, 711/4, 711/100, 711/114
• US Class Current: 709/231
• 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 multiple user data storage, retrieval and distribution system containing a parallel processing computer system that forms a digital information server. The server contains a plurality of parallel processors each connected to a information storage device. The user data is stored in a distributed manner amongst the information storage devices. The distribution system dynamically allocates the users to the system based upon the user'"'"'s requested operating mode. As such, during successive user service periods, all the users are supplied their requested data. The system also provides error detection and correction for the data requested by the users. Furthermore, additional data can be added to the information storage devices during each service period and select information storage devices can be recalibrated without affecting system operation. Even though the system allocates users dynamically such that the data is retrieved from the information storage devices in an arbitrary order, the system contains an output timing sequencer that generates output data in a predefined order no matter the order in which the data is retrieved from the information storage devices. The disclosed apparatus and method find applicability in video servers, medical imaging, special effects and animation and location based entertainment systems among other applications.

Claims

1. In a multiple user data distribution system containing a parallel processor computer having a plurality of parallel processors each connected to an 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 striping data into said multiple user data distribution system comprising the steps of:

providing a continuous stream of data that is subdivided into discrete segments;

dividing said plurality of information storage devices into a plurality of subsets of information storage devices;

selecting a sequential number of discrete segments of said data stream for each of said subsets of information storage devices;

storing said selected number of discrete segments of data in each of said subsets of information storage devices; and

repeating said discrete segment selecting and storing steps until said discrete segments form, within each subset of information storage devices, a plurality of blocks of contiguous data having a predetermined size such that said discrete segments comprising each of said data blocks have a striped pattern.

2. The method of claim 1 wherein said storing step further comprises the step of simultaneously storing said selected number of discrete segments of data in each of said subsets of information storage device.

3. The method of claim 1 wherein said continuous stream of data is a digitized video program.

4. The method of claim 1 wherein the blocks of contiguous data stored within each subset of information storage devices are sequentially stored such that said data blocks form a striped pattern of contiguous blocks of contiguous data within the plurality of subsets of information storage devices.

5. The method of claim 1 wherein each of said subsets of information storage devices contain five information storage devices and each information storage device stores 16,000 contiguous words of data to produce a predetermined size block of contiguous data containing 80,000 contiguous words of data.

6. The method of claim 1 further 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 if the users and in response to user commands and using said allocated processor, a specified discrete segment of data within a information storage device associated with the allocated processor;

supplying each of said users with a 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.

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

8. The method of claim 6 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.

9. The method of claim 8 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.

10. The method of claim 9 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.

11. The method of claim 6 wherein each of the users are allocated and reallocated to said 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.

12. The method of claim 11 further comprising the steps of:

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

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

13. The method of claim 12 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.

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

multiplexing the series of data elements having a predefined order;

transmitting the multiplexed data to the users.

15. The method of claim 11 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.

16. The method of claim 15 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.

17. The method of claim 16 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.

18. The method of claim 11 further comprising the steps of:

selecting one subset of information storage devices for recalibration;

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

19. The method of claim 11 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.