Method and apparatus for selective buffering of pages to provide continuous media data to multiple users

• US 5,721,956 A
• Filed: 05/15/1995
• Issued: 02/24/1998
• Est. Priority Date: 05/15/1995
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Silberschatz, Abraham, Martin, Clifford Eric, Ozden, Banu, Rastogi, Rajeev
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US08/440,737
• Time in Patent Office: 1,016 Days
• Field of Search: 395/460, 395/461, 395/440, 395/416, 395/412, 395/872, 395/876, 395/878, 395/881
• US Class Current: 710/52
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends
• CPC Class Codes: H04N 7/24 Systems for the transmission of television signals using pulse code modulation H04N21/00 takes precedence

Abstract

Buffer space and disk bandwidth resources in a continuous media server are continuously re-allocated in order to optimize the number of continuous media requests which may be concurrently serviced at guaranteed transfer rates using on demand paging. Disk scheduling is provided to ensure that whenever an admitted request references a page of data, the page is available in a buffer for transfer to a client. Data for continuous media data files are stored on disk or held in the buffer to eliminate disk bandwidth limitations associated with concurrently servicing any number or combination of requests, provided buffer space is sufficient. Multiple requests for continuous media data files are selectively included in groups for servicing in order to provide that buffer and disk bandwidth requirements are maintained at a minimum and within available resource capabilities.

Claims

1. A method of retrieving portions of a continuous media data file from a disk to a buffer on demand, said continuous media data file comprising pages of data and being characterized by a transfer rate, the method comprising the steps of:

receiving a request for the continuous media data file;

pinning in the buffer a page currently referenced by the request; and

,

pinning in the buffer simultaneously the next page following the page currently referenced by the request, such that data are made available in the buffer for transfer at the transfer rate.

2. The method of claim 1, wherein the initial page of the continuous media data file is permanently stored in the buffer.

3. The method of claim 1, wherein the disk comprises a plurality of continuous media data files characterized by a plurality of transfer rates, respectively.

4. The method of claim 3, wherein the initial page of the continuous media data file is permanently stored in the buffer.

6. The method of claim 4, wherein the disk comprises a plurality of continuous media data files characterized by a plurality of transfer rates, respectively.

7. The method of claim 4, wherein the server includes a plurality of disks and the continuous media data file is stored over the plurality of disks.

8. The method of claim 7, wherein a page of the continuous media data file is striped over the plurality of disks.

9. The method of claim 7, wherein a plurality of continuous media data files are stored on the plurality of disks.

5. A method of retrieving data from a server, said server comprising a disk connected to a buffer by a transmission line, wherein the disk contains a continuous media data file, said continuous media data file comprising pages of data and being characterized by a transfer rate, the method comprising the steps of:

receiving a request for the continuous media data file;

determining whether the next page of the continuous media data file that the request will reference is pinned in the buffer;

paging the next page from the disk to the buffer if the next page is not pinned in the buffer; and

,

pinning the next page in the buffer simultaneously with the page currently referenced such that the next page is available for transfer when the request references the next page.

10. A method for servicing multiple requests for a continuous media data file at a server, wherein the server comprises a disk and buffer connected by a transmission line, said continuous media data file comprising pages of data and being characterized by a transfer rate, the method comprising the steps of:

receiving the requests for the continuous media data file;

pinning in the buffer pages currently referenced by the requests, respectively;

pinning in the buffer simultaneously the next pages following the currently referenced pages of the requests, respectively, such that data are made available in the buffer for transfer at the transfer rate and such that the pages of data in the buffer can be utilized for servicing more than one of the requests simultaneously;

determining whether a new request R_i arrived at the server after a previously received request R_i-1 at less than or equal to a first time interval, said first time interval being equal to twice the time required for a request to consume a page of the continuous media data file from the buffer, said request R_i-1 being included in a previous group, said previous group including requests, each of which arrived at the server at less than or equal to the first time interval after a preceding request included in the previous group;

constructing a new group with the new request R_i if R_i did not arrive after the request R_i-1 at a time less than or equal to the first time interval, the buffer contains sufficient space for the creation of the new group including the new request R_i and sufficient bandwidth is available on the transmission line for transferring pages of data to the buffer for servicing the new request R_i in the newly constructed group; and

,

joining R_i to the previous group if the new request R_i arrived after the request R_i-1 at a time less than or equal to the first time interval and the buffer contains sufficient space for servicing the new request R_i as part of the previous group.

11. The method of claim 10, further comprising the step of:

waiting until sufficient space in the buffer and disk bandwidth on the transmission line becomes available for constructing the new group with the new request R_i if R_i did not arrive after the request R_i-1 at a time less than or equal to the first time interval.

12. The method of claim 11, wherein at least one disk bandwidth unit on the transmission line must become available for servicing the new request in the newly constructed group.

13. The method of claim 10, wherein the number of pages of data for the continuous media data file is equal to at most twice the number of disk bandwidth units of the transmission line, such that any number of requests for the continuous media data file may be serviced provided that sufficient space exists in the buffer.

14. The method of claim 10, wherein the size of the pages of data for the continuous media data file is a fixed quantity, the method further comprising the step of:

selecting a duration for pinning pages in the buffer such that sufficient disk bandwidth units on the transmission line are always available for concurrently servicing any number of requests for the continuous media data file provided that sufficient space in the buffer exists.

15. The method of claim 10, wherein the server includes a plurality of disks and the continuous media data file is stored over the plurality of disks.

16. The method of claim 15, wherein a page of the continuous media data file is striped over the plurality of disks.

17. The method of claim 10, wherein a plurality of continuous media data files are stored on the plurality of disks.

18. A method of retrieving data from a server, said server comprising a disk connected to a buffer by a transmission line, wherein the disk contains a continuous media data file, said continuous media data file comprising pages of data and being characterized by a transfer rate, the method comprising the steps of:

receiving requests for the continuous media data file;

pinning in the buffer pages currently referenced by the requests, respectively;

pinning in the buffer simultaneously the next pages following the currently referenced pages of the requests, respectively, such that data are made available in the buffer for transfer at the transfer rate and such that the pages of data in the buffer can be utilized for servicing more than one of the requests simultaneously;

placing the requests in groups for servicing according to time of arrival of the requests at the server;

selecting a pinning duration for pages pinned by the earliest request in an active group such that the earliest request in an active group pins the pages in the buffer for all other requests in the active group; and

,

continuously re-allocating the use of space in the buffer and units of disk bandwidth on the transmission line for servicing the requests such that the number of disk accesses for a page of the continuous media data file is maintained in steady state at most equal to one less than the total number of disk bandwidth units on the transmission line.

19. The method of claim 18, further comprising the step of:

adjusting the number of requests in groups according to the total number of requests being serviced, such that the steady state disk bandwidth condition is maintained and such that the total number of requests concurrently being serviced can exceed the total number of disk bandwidth units for the transmission line.

20. The method of claim 19, wherein the adjusting step further comprises the step of:

increasing the number of requests in an existing group.

21. The method of claim 19, wherein the adjusting step further comprises the step of:

decreasing the number of requests in an existing group.

22. The method of claim 19, wherein the adjusting step further comprises the step of joining a newly received request to a latest existing group, said joining step further comprising the steps of:

incrementing pinning durations for pages currently pinned in the buffer for the latest group; and

,

pinning in the buffer pages referenced by the newly received request until the join operation is completed.

23. The method of claim 19, wherein the adjusting step further comprises the step of combining a first group to a second group to form a new group, wherein the second group follows the first group consecutively in time and the earliest request in the second group arrived after the latest request in the first group at a time interval greater than a first time interval, said first time interval being equal to twice the time required for a request to consume a page of the continuous media data file from the buffer, said combining step further comprising the steps of:

incrementing pinning durations for pages currently pinned in the buffer for servicing the first group; and

,

pinning in the buffer pages referenced by the earliest request in the second group based on the difference in arrival times at the server between the earliest request and the latest request of the second group.

24. The method of claim 23, further comprising the step of:

pinning in the buffer pages referenced by the earliest request of the first group based on the difference in arrival times between the earliest request of the first group and the latest request of the second group, if the first group is an active group.

25. The method of claim 19, wherein the adjusting step further comprises the step of partitioning a group to form a partitioned group, wherein the group initially includes a first request which arrived at the server before a second request at a time interval greater than a first time interval, said first time interval being equal to twice the time required for a request to consume a page of the continuous media data file from the buffer, said partitioning step further comprising the step of:

selecting requests from the group for inclusion in the partitioned group such that the first request is in the partitioned group and the second request remains in the group and such that less space in the buffer is required for servicing the requests included in the group before partitioning occurred.

26. The method of claim 19, further comprising the step of:

receiving a newly arrived request for the continuous media data file;

joining the newly arrived request to a latest existing group if space in the buffer is sufficient.

27. The method of claim 26, wherein the joining step further comprises the steps of:

incrementing pinning durations for pages currently pinned in the buffer for a latest group; and

,

pinning in the buffer pages referenced by the newly received request until the join operation is completed.

28. The method of claim 19, further comprising the step of:

receiving a newly arrived request for the continuous media data file; and

,

reducing the number of active groups to ensure that at least one disk bandwidth unit is available in the steady state.

29. The method of claim 28, wherein the step of reducing the number of active groups further comprises the step of joining the newly arrived request to a latest existing group.

30. The method of claim 28, wherein the step of reducing the number of active groups further comprises the step of combining two consecutive groups.

31. The method of claim 28, further comprising the step of:

pinning in the buffer the initial pages referenced by the newly admitted request until a join or combine operation which is in progress completes or until an earliest existing group becomes passive.

32. The method of claim 19, further comprising the steps of:

receiving a newly arrived request for the continuous media data file; and

,

computing the space available in the buffer for servicing the new request after a join or combine operation is performed.

33. The method of claim 19, further comprising the step of:

computing the space available in the buffer for servicing the new request after the earliest request of an active group accesses the page before the last page of the continuous media data file for the first time.

34. The method of claim 19, wherein the server includes a plurality of disks and the continuous media data file is stored over the plurality of disks.

35. The method of claim 19, wherein a plurality of continuous media data files are stored on the plurality of disks.

36. A system for providing continuous media services comprising:

a disk containing a continuous media data file, said continuous media data file comprising pages of data and being characterized by a transfer rate;

a buffer connected by a transmission line to said disk for storing pages of data;

a processor connected to the disk and the buffer, wherein said processor performs the operations of

receiving a request for the continuous media data file; and

,

retrieving portions of the continuous media data file for on demand servicing of the request, wherein a page currently referenced by the request and the next page following the currently referenced page are simultaneously pinned in the buffer to provide that data are made available in the buffer for transfer at the transfer rate.

37. The system of claim 36, wherein the initial page of the continuous media data file is permanently stored in the buffer.

38. The system of claim 36, wherein the disk comprises a plurality of continuous media data files characterized by a plurality of transfer rates, respectively.

39. The system of claim 36, further comprising:

a plurality of disks, said continuous media data file being stored over the plurality of disks.

40. The system of claim 39, wherein a page of the continuous media data file is striped over the plurality of disks.

41. The system of claim 39, wherein a plurality of continuous media data files are stored on the plurality of disks.

42. A system for providing continuous media services comprising:

a disk containing a continuous media data file, said continuous media data file comprising pages of data and being characterized by a transfer rate;

a buffer connected by a transmission line to said disk for storing pages of data;

a processor connected to the disk and the buffer, wherein the processor performs the operations of;

receiving a request for the continuous media data file;

pinning in the buffer a page currently referenced and the next page following the currently referenced page of the request such that data are made available in the buffer for transfer at the transfer rate and such that the pages of data in the buffer can be utilized for servicing more than one of the requests simultaneously;

determining whether a new request R_i arrived at the server after a previously received request R_i-1 at less than or equal to a first time interval, said first time interval being equal to twice the time required for a request to consume a page of the continuous media data file from the buffer, said request R_i-1 being included in a previous group, said previous group including requests, each of which arrived at the server at less than or equal to the first time interval after a preceding request in the previous group arrived at the server;

constructing a new group with the new request R_i if R_i did not arrive after the request R_i-1 at a time less than or equal to the first time interval, the buffer contains sufficient space for the creation of the new group including the new request R_i and sufficient bandwidth is available on the transmission line for transferring pages of data to the buffer for servicing the new request R_i in the newly constructed group; and

,

joining R_i to the previous group if the new request R_i arrived after the request R_i-1 at a time less than or equal to the first time interval and the buffer contains sufficient space for servicing the new request R_i as part of the previous group.

43. The system of claim 42, wherein the processor further performs the operation of:

waiting until sufficient space in the buffer and disk bandwidth on the transmission line becomes available for constructing the new group with the new request R_i if R_i did not arrive after the request R_i-1 at a time less than or equal to the first time interval.

44. The system of claim 42, wherein the number of pages of data for the continuous media data file is equal to at most twice the number of disk bandwidth units of the transmission line, such that any number of requests for the continuous media data file may be serviced provided that sufficient space exists in the buffer.

45. The system of claim 42, wherein the size of the pages of data for the continuous media data file stored on the disk is a fixed quantity, and wherein the processor further performs the operation of:

selecting a duration for pinning pages in the buffer such that sufficient disk bandwidth units on the transmission line are always available for concurrently servicing any number of requests for the continuous media data file provided that sufficient space in the buffer exists.

46. A system for providing continuous media service comprising:

a disk containing a continuous media data file, said continuous media data file comprising pages of data and being characterized by a transfer rate;

a buffer connected by a transmission line to said disk for storing pages of data;

a processor connected to the disk and the buffer, wherein the processor performs the operations of;

receiving requests for the continuous media data file;

retrieving portions of the continuous media data file for on demand servicing of the request, wherein a page currently referenced by the request and the next page following the currently referenced page are simultaneously pinned in the buffer to provide that data are made available in the buffer for transfer at the transfer rate;

placing the requests in groups for servicing according to time of arrival of the requests at the server;

selecting a pinning duration for pages pinned by the earliest request in an active group such that the earliest request in an active group pins the pages in the buffer for all other requests in the active group; and

,

continuously re-allocating the use of space in the buffer and units of disk bandwidth on the transmission line for servicing the requests such that the number of disk accesses for a page of the continuous media data file is maintained in steady state at most equal to one less than the total number of disk bandwidth units on the transmission line.

47. The system of claim 46, wherein the processor further performs the operations of:

adjusting the number of requests in groups according to the total number of requests being serviced, such that the steady state disk bandwidth condition is maintained and such that the total number of requests concurrently being serviced can exceed the total number of disk bandwidth units for the transmission line.

48. The system of claim 46, wherein the processor performs the operation of increasing the number of requests in an existing group.

49. The system of claim 46, wherein the processor performs the operation of decreasing the number of requests in an existing group.