# US 5,708,796 A · Method of retrieving continuous and non-continuous media data from a file system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 5,708,796 A - Document ID: US5708796A - Status: Granted - Kind: A - Application number: 08/341,827 - Filed: 1994-11-18 - Granted: 1998-01-13 - Earliest claimed: 1994-11-18 - Assignees: Lucent Technologies Inc. - Inventors: Banu Ozden; Rajeev Rastogi; Abraham Silberschatz - Web page: https://patentgrep.com/patent/US5708796A ## CPC - H04N 21/2326: {Scheduling disk or memory reading operations} - G06F 3/0613: {in relation to throughput} - G06F 3/0656: {Data buffering arrangements} - G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling} - G06F 3/0674: {Disk device} - 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) - H04N 7/17336: {Handling of requests in head-ends} - Y10S 707/99953: Recoverability - Y10S 707/99956: File allocation - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## 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.sub.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 ### Claim 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.sub.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. ### Claim 2 (depends on 1) 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.sub.i required to retrieve the particular media stream. ### Claim 3 (depends on 2) The method according to claim 2 wherein said determining step further comprises: rejecting said request if the sum of the retrieval times .SIGMA.C.sub.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. ### Claim 4 (depends on 1) 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.sub.i. ### Claim 5 (depends on 1) 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. ### Claim 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.sub.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. ### Claim 7 (depends on 6) 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. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 7) 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. ### Claim 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.sub.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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 12) The method according to claim 12 wherein said scanning step further comprises: scanning the disk from the second end to the first end. ### Claim 14 (depends on 11) 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. ### Claim 15 (depends on 11) 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 16) The method according to claim 16 further comprising: dynamically changing the number of tracks retrieved during any particular period. ### Claim 18 (depends on 15) 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. ### Claim 19 (depends on 15) 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. ### Claim 20 (depends on 19) 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. ### Claim 21 (depends on 20) 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. ### Claim 22 (depends on 21) 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. ### Claim 23 (depends on 22) 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. ### Claim 24 (depends on 21) 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. ### Claim 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.sub.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. ### Claim 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.sub.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. ### Claim 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.sub.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.