Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-03-07
2004-02-10
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S158000, C710S039000, C725S087000, C725S097000
Reexamination Certificate
active
06691208
ABSTRACT:
The invention relates to methods of scheduling disk access requests in a video server, and, more particularly, to statistical scheduling methods that improve the effective disk bandwidth provided by video servers.
BACKGROUND OF THE DISCLOSURE
Video-on-demand systems allow subscribers (also referred to as users or clients) to request video programs from a video library at any time for immediate viewing in their homes. Subscribers submit requests to a video service provider via a communication channel (e.g., telephone lines or a back channel through the distribution network that carries the video to the subscriber's home), and the requested video program is routed to the subscriber's home via telephone or coaxial television lines. In order to provide such movie-on-demand services, video service providers use a video server to process subscriber requests, retrieve the requested programs from storage, and distribute the programs to the appropriate subscriber(s). One exemplary system for providing video-on-demand services is described in commonly assigned U.S. Pat. No. 6,253,375, issued Jun. 26, 2001, which is incorporated herein by reference.
In order for video servers to provide good performance, it is crucial to schedule video storage (disk) access requests such that disk bandwidth is maximized. Also, once a subscriber is watching a program, it is imperative to continuously deliver program content to the subscriber without interruption. In addition to distributing content to subscribers, disk bandwidth in a video server is typically also utilized for operations such as loading content, disk maintenance, and file system meta-data synchronizing. Disk bandwidth may also be reserved for reducing latency in data transfer to subscribers. The number of subscribers that can be properly served concurrently by a video server therefore depends on effective disk bandwidth, which in turn depends on how disk access requests are scheduled.
One of the problems facing current disk scheduling methods is the potential variation in time required to service disk accesses. For example, the internal transfer rate of a SEAGATE CHEETAH™ disk varies from 152 Megabits per second (Mbps) on inner tracks to 231 Mbps on outer tracks, and the seek time can vary from 0 milliseconds (ms) to 13 ms depending on how far apart the segments of data are from one another. Given these variations in seek and transfer times and the fact that the server may contain sixteen or more disk drives, it is difficult to determine the effective disk bandwidth of a video server. As a result, current disk scheduling methods allocate a fixed amount of time for every disk access request, regardless of whether the access finishes early. This results in a deterministic system in which the available disk bandwidth is known, but since the fixed amount of time must be large enough to accommodate a worst-case disk access, disk bandwidth is wasted.
Therefore, there is a need in the art for a method and apparatus for scheduling disk access requests in a video server without allocating worst-case access times, thus improving disk bandwidth utilization.
SUMMARY OF THE INVENTION
The disadvantages associated with the prior art are overcome by a method of the present invention, called Statistical Disk Scheduling (SDS), which exploits the fact that disk access times are on average significantly less than the worst case access time. The SDS finds use in improving video server functionality by increasing the bandwidth utilization of the storage medium in the following manner: worst case performance is used for priority operations (e.g., user read operations) but the bandwith created by better than worst case performance is used for non-priority operations such as loading content onto the disk drives and disk maintenance. As a result, bandwidth for loading content and disk maintenance, or file system meta-data synchronizing does not have to be specifically reserved, thus increasing the number of users that can be served simultaneously by the video server.
SDS maintains at least two queues and a queue selector. The first queue is an access request queue for access requests from a current user that is presently viewing a program and the second queue is for all other forms of access requests. The second queue may comprise multiple queues to provide a queuing hierarchy. The requests are ordered in each of the queues to optimize the bandwidth and ensure that the data to the current users is not interrupted such that a display anomaly occurs. The queue selector identifies the queue that will supply the next access request to a disk queue. The selected requests are sent to the disk queues for execution. The disk queues are generally located on the disk drives and are generally not accessible except to place a request in the queue for each disk drive. The requests are then executed on a first-in, first-out manner (FIFO). In effect, the invention defers disk use to the latest possible moment because once the request is in the disk queue it is more difficult to change. The inventive queue structure provides opportunities to alter the disk access requests and their execution order prior to sending the requests to the disk queue. If a disk queue is not used, i.e., the disk drive does not have an internal queue, then the access requests are sent one at a time from the SDS to the disk drive for execution.
More specifically, one embodiment of the SDS maintains three queues for each disk based on the type and priority of disk access requests, and a queue selector for managing queue selection. Selected requests are forwarded from the three queues to the disk such that bandwidth utilization is maximized, while giving highest priority to subscribers currently viewing a program so that their program streams are generally not interrupted. (Subscribers currently viewing a program are referred to as “steady-state” subscribers.) SDS dynamically monitors bandwidth utilization to determine when lower-priority requests can be scheduled without affecting on-time completion of the higher priority steady-state subscriber requests. In order to keep the disks busy and maximize disk bandwidth utilization, disk command queuing may be employed to ensure that the disk can begin seeking for the next access immediately after it finishes the data transfer for the current disk access.
In another embodiment of the invention, the queue selector uses a controlled admission algorithm that identifies a particular queue in which a new user (subscriber) will be assigned. The queue assignment process computes whether the user request can be serviced within a particular service period without causing other user requests to miss their data access deadlines. If the request can be performed in a timely manner, the user is assigned to the particular new user queue. However, if the request cannot be performed without detrimentally impacting other user requests within that service period, the request is reallocated to another entry point (i.e., a new user queue associated with another disk drive) into the disk array.
REFERENCES:
patent: 5220653 (1993-06-01), Miro
patent: 5561456 (1996-10-01), Yu
patent: 5581778 (1996-12-01), Chin et al.
patent: 5610841 (1997-03-01), Tanaka et al.
patent: 5644786 (1997-07-01), Gallagher et al.
patent: 5671377 (1997-09-01), Bleidt et al.
patent: 5687390 (1997-11-01), McMillian, Jr.
patent: 5721956 (1998-02-01), Martin et al.
patent: 5787482 (1998-07-01), Chen et al.
patent: 5802394 (1998-09-01), Baird et al.
patent: 5870629 (1999-02-01), Borden et al.
patent: 5926458 (1999-07-01), Yin
patent: 5926649 (1999-07-01), Ma et al.
patent: 5928327 (1999-07-01), Wang et al.
patent: 5991812 (1999-11-01), Srinivasan
patent: 6021464 (2000-02-01), Yao et al.
patent: 6023720 (2000-02-01), Aref et al.
patent: 6061504 (2000-05-01), Tzelnic et al.
patent: 6253375 (2001-06-01), Gordon et al.
patent: 6378036 (2002-04-01), Lerman et al.
patent: 6434631 (2002-08-01), Bruno et al.
Pan et al, “A Time-Scale Dependent Disk Scheduling Scheme for Multimedia on Demand Servers,” IEEE Procee
Chin Danny
Dandrea Robert G.
Fredrickson James
Lerman Jesse S.
Taylor Clement G.
Diva Systems Corp.
Gossage Glenn
Moser Patterson & Sheridan LLP
LandOfFree
Queuing architecture including a plurality of queues and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Queuing architecture including a plurality of queues and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queuing architecture including a plurality of queues and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3331139