Method of retrieving continuous and non-continuous media data from a file system

• US 5,708,796 A
• Filed: 11/18/1994
• Issued: 01/13/1998
• Est. Priority Date: 11/18/1994
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rastogi, Rajeev, Ozden, Banu, Silberschatz, Abraham
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lewis, Cheryl R.
• Application Number:
  US08/341,827
• Time in Patent Office: 1,152 Days
• Field of Search: 395/600, 395/425, 395/494, 395/495, 395/621
• US Class Current: 711/167
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: H04N 21/2326 Scheduling disk or memory reading operations
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A method of scheduling the retrieval of both continuous and non-continuous data retrieves continuous data streams at a predetermined rate. At least one server receives one or more requests for the retrieval of a stream of media data by at least one terminal. Each requested media stream is characterized by a playback rate r_i. A common retrieval time period is established for each requested media stream. The common retrieval time period is a function of the playback rate. The retrieval of the requested media stream is scheduled in the order in which each request is received by the server.

Claims

1. A method of scheduling the retrieval of data from recorded media contained within a file system capable of supporting storage and retrieval of both continuous and non-continuous media data, the file system comprising at least one server, the method comprising:

receiving a plurality of requests for retrieval of a stream of media data transmitted by at least one of a plurality of terminals, each requested media stream being characterized by a playback rate r_i ;

establishing a common retrieval time period for each requested media stream, said common retrieval period being a function of the playback rate; and

scheduling the retrieval time period for each requested media stream, said common retrieval period being a function of the playback rate; and

scheduling the retrieval of the requested media streams in the order in which request has been received by the server.

2. The method according to claim 1 wherein said receiving step further comprises:

determining whether a received request for retrieving a particular media stream is to be accepted by said file system, said acceptance being a function of the retrieval time C_i required to retrieve the particular media stream.

3. The method according to claim 2 wherein said determining step further comprises:

rejecting said request if the sum of the retrieval times Σ

C_i of all the data retrieval requests currently pending is greater than the common time period, the sum of the retrieval times including the retrieval time required to retrieve the particular media stream.

4. The method according to claim 1 wherein said step of establishing a common time period further comprises the step of determining a unit of retrieval for each request, said unit of retrieval being a function of the common time period and the playback rate r_i.

5. The method according to claim 1 wherein said step of establishing a common time period further comprises the steps of:

determining those requests which have been received within a given time interval;

grouping said requests received within the given interval into a set; and

establishing a common retrieval period for the requests in the set.

6. A method of scheduling the retrieval of data from disks contained within a file system capable of supporting storage and retrieval of both continuous and non-continuous media data, the file system comprising at least one server, having media data stored on a disk storage system having at least one disk, the method comprising:

receiving one or more requests for retrieval of a stream of media data transmitted by at least one of a plurality of terminals, each requested media stream being characterized by a playback rate r_i ;

establishing the requests received within a given time interval in an order for data retrieval based on the location of a track on the disk on which the data is stored;

scanning the disk from a first end to a second end;

retrieving the data associated with each request in the established order as the disk is scanned;

maintaining a buffer for storing the data, said buffer having a capacity for storing the equivalent of at least two data units; and

determining the amount of slack resulting from the retrieval of a particular data request.

7. The method according to claim 6 wherein the amount of slack is determined by calculating the difference between the number of data bits which should have been read to avoid slack and the amount of data read in response to the request.

8. The method according to claim 7 further comprising the step of:

adjusting the time at which the reading of data for a subsequent data request commences, said commencing time being dependent on the amount of slack from the previous request.

9. The method according to claim 8 wherein said commencing time is before the end of the period for the previous request if there is slack associated with the previous request.

10. The method according to claim 7 further comprising the step of:

adjusting the amount of data read for a particular request, said adjustment being dependent on the amount of data read for a previous request.

11. A method of scheduling the retrieval of data from recorded media contained within a file system capable of supporting storage and retrieval of both continuous and non-continuous media data, the file system comprising at least one server having media data stored on a disk storage system having at least one disk, the method comprising:

receiving a plurality of requests for retrieval of a stream of media data transmitted by at least one of a plurality of terminals, each requested media stream being characterized by a playback rate r_i ;

establishing a common retrieval time period for each requested media stream, said common retrieval period being a function of the playback rate; and

establishing the requests received within the time interval in an order for data retrieval based on the location of a track on the disk on which the data is stored.

12. The method according to claim 11 further comprising:

scanning the disk from a first end to a second end; and

retrieving the data associated with each request in the established order as the disk is scanned.

13. The method according to claim 12 wherein said scanning step further comprises:

scanning the disk from the second end to the first end.

14. The method according to claim 11 further comprising:

determining which request is to be retrieved after a previous common period has ended by identifying the request which is the shortest distance from the disk location at which the last request was retrieved in the previous common period.

15. The method according to claim 11 wherein said establishing step further comprises:

determining the corresponding disk track at which each requested media stream is stored; and

scheduling the retrieval of the requested media streams such that the amount by which the disk must be rotated so that a disk head associated with the system is able to locate a position on the disk track at which a particular media stream is stored is reduced.

16. The method according to claim 15 wherein said retrieval of data in response to a request is performed by retrieving an integral number of disk tracks.

17. The method according to claim 16 further comprising:

dynamically changing the number of tracks retrieved during any particular period.

18. The method according to claim 15 wherein said scheduling step further comprises:

initiating the retrieval of data in response to a particular request when the disk head arrives at the disk track on which the data stream associated with the request is stored regardless of whether that portion of the disk track contains the beginning of the stream.

19. The method according to claim 15 further comprising the steps of:

maintaining a buffer for storing the data; and

buffering a track of data prior to an initial reading of data.

20. The method according to claim 19 further comprising the step of:

determining the amount of slack resulting from the retrieval of a particular data request.

21. The method according to claim 20 wherein the amount of slack is determined by calculating the difference between the number of data bits which should have been read to avoid slack and the amount of data read in response to the request.

22. The method according to claim 21 further comprising the step of:

adjusting the time at which the reading of data for a subsequent data request commences, said commencing time being dependent on the amount of slack from the previous request.

23. The method according to claim 22 wherein said commencing time is before the end of the period for the previous request if there is slack associated with the previous request.

24. The method according to claim 21 further comprising the step of:

adjusting the amount of data read for a particular request, said adjustment being dependent on the amount of data read for a previous request.

25. A method of scheduling the retrieval of data from recorded media contained within a file system capable of supporting storage and retrieval of both continuous and non-continuous media data, the file system comprising at least one server having media data stored on a disk storage system, the method comprising:

receiving a plurality of requests for retrieval of a stream of media data transmitted by at least one of a plurality of terminals, each requested media stream being characterized by a playback rate r_i ;

establishing a common retrieval time period for each requested media stream, said common retrieval period being a function of the playback rate;

scheduling the retrieval of the requested media streams by determining the corresponding disk track at which each requested media stream is stored; and

scheduling the order of retrieval of the requested media streams such that the amount by which a disk must be rotated so that a disk head associated with the disk storage system is able to locate a disk track at which a particular media stream is stored is reduced.

26. A method of scheduling the retrieval of data from recorded media contained within a file system capable of supporting storage and retrieval of both continuous and non-continuous media data, the file system comprising at least one server, the method comprising:

receiving a plurality of requests for retrieval of a stream of media data transmitted by at least one of a plurality of terminals, each requested media stream being characterized by a playback rate r_i ;

establishing a common retrieval time period for the plurality of requested media streams, said common retrieval period being a function of the playback rate; and

conforming the period of each request to the common retrieval time period by modifying each request'"'"'s unit of retrieval.

27. A method of scheduling the retrieval of data from recorded media contained within a file system capable of supporting storage and retrieval of both continuous and non-continuous media data, the method comprising:

receiving a plurality of requests for retrieval of a stream of media data transmitted by at least one of the plurality of terminals, each requested media stream being characterized by a playback rate r_i ;

treating each request as a sequence of instances;

establishing a common retrieval time period for the plurality of requested media streams, said common retrieval period being a function of the playback rate; and

delaying queuing of each request as necessary to insure that the instances of all requests arrive at the same time.