Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-02-28
2002-12-17
Nguyen, Than (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S111000, C711S154000, C711S158000, C711S167000
Reexamination Certificate
active
06496899
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computer data storage and server systems, and more particularly to digital video/audio storage and playback systems supporting multiple continuous media streams.
2. Description of the Relevant Art
Multimedia or video server systems are used in a variety of applications for the storage and playback of video, audio or other multimedia data streams. For example, multimedia servers may be used for broadcast, cable or satellite solutions to distribute multimedia information to clients or consumers. Professional broadcasters and associated service providers, such as networks and affiliates or cable providers, may employ digital video servers to support high bandwidth multimedia broadcast applications including multi-channel program playout, ad insertion, and digital content management. Other applications for multimedia server systems may include computer-based training in which multimedia training materials or lectures may be stored on the server system accessed by students over a network or the internet.
Video archiving, browsing and retrieval is another multimedia server application. Various movies may be stored by the server and distributed to users upon request. Video-on-demand or video delivery systems may enable a plurality of users or viewers to selectively watch movies or other audio/video sequences which are stored on one or more video servers or media servers. The video servers may be connected through data transfer channels, such as a broadcast cable system, satellite broadcast system or the internet, to the plurality of users or subscribers. The video servers may store a plurality of movies or other audio/video sequences, and each user can select one or more movies from the video servers for viewing. Each user may include a television or other viewing device, as well as associated decoding logic, for selecting and viewing desired movies. When a user selects a movie, the selected movie may be transferred on one of the data transfer channels to the viewing device of the respective user. Multimedia servers are also found in webcasting applications in which entertainment may be multicast on the internet to different subscribers. Multimedia servers are found in numerous other applications as well.
To meet the demands of many different applications and users, it is desirable for a multimedia server system to provide flexibility and extensibility. Two important requirements for a multimedia server system are storage space and file system bandwidth. Multimedia data, such as full-motion digital video, requires a large amount of storage and data transfer bandwidth. Thus, multimedia systems use various types of video compression algorithms to reduce the amount of necessary storage and data transfer bandwidth. In general, different video compression methods exist for still graphic images and for full-motion video. Video compression methods for still graphic images or single video frames may be intraframe compression methods, and compression methods for motion video may be interframe compression methods.
Examples of video data compression for still graphic images are RLE (Run-Length Encoding) and JPEG (Joint Photographic Experts Group) compression. Although JPEG compression was originally designed for the compression of still images rather than video, JPEG compression is used in some motion video applications. Most video compression algorithms are designed to compress full motion video. Examples of video compression techniques are MPEG (Moving Pictures Experts Group), MPEG-2, DVI (Digital Video Interactive) and Indeo, among others.
Even with the use of compression techniques, multimedia applications may still require extremely large amounts of storage. For example, two hours of video encoded at 1 Mb per second may require roughly one gigabyte (1 GB) of storage. A system supporting numerous different content may require up to several terabytes (TB) of storage. The server system must also be able to provide enough bandwidth for the various users to access selected multimedia content without overloading the storage system. For example, to support 100 simultaneous subscribers viewing multimedia content encoded at 1 Mb per second, a server may need to support a bandwidth in excess of 100 Mb per second when allowing for overhead. If enough bandwidth is not available, then some requests may have to be denied, or the play quality may suffer (video may run too slowly or may appear “jerky”). To meet such storage and bandwidth needs, a multimedia server may utilize one or more RAID (Redundant Array of Inexpensive Drives) storage systems. In a RAID system, for a given multimedia file, blocks of multimedia data may be stored across multiple hard disk units. The blocks may be read out or transferred to the communication network and transmitted or broadcast to the user or users. At the receiving end the blocks may be decoded for user viewing on a display device.
The disks of each hard disk unit may also be considered as being divided into zones. Since they are physically larger, tracks in zones at the outer disk contain more sectors than tracks in zones near the rotational axis of the disk. Therefore, assuming the disks rotate with a constant velocity, the data bandwidth available from the outer most zones is greater than the data bandwidth available from the innermost zones. Even with modem hard disk drives, there can be a 2-1 variation between worst case and average case disk transfer bandwidth due to sectors/track variations between outer and inner zones.
Many multimedia applications require continuous media streams in which data streams must be delivered at a specified and possibly time-varying data rates and with a specified uniformity of that delivery rate. In some cases, the uniformity of the delivery rate may be adversely affected by the algorithm used to satisfy disk access requests. The use of a “first-come, first-served” disk access algorithm may not always be the most efficient way to satisfy disk requests, as motion of the read-write head (used to access information from the disk) may be less than optimal. Some optimization of head motion may be realized through the use of algorithms that re-order the disk requests. In such re-ordering algorithms, disk requests may be satisfied in an order different from the order in which they were made. One such re-ordering algorithm is known as an “elevator” algorithm. In one typical elevator algorithm, the head of the disk storage system sweeps from the outer disk to the inner disk, satisfying and queued disk request along the way, and then reversing direction. While this algorithm may allow for more efficient motion of the read-write head, highly non-uniform access times may still be present, as newly arriving requests may be satisfied prior to previously queued requests. A large number of newly arriving requests may cause long delays in satisfying previously queued requests.
Non-uniform disk access times may be detrimental to many applications, particularly multimedia applications. For example, video playback from a disk storage system may appear erratic when disk access times are non-uniform. Audio playback may be affected in a similar manner. As such, the quality of a multimedia presentation accessed from a disk storage system with non-uniform access times may suffer.
SUMMARY OF THE INVENTION
The problems outlined above may in large part be solved by a system and method of bounded disk request reordering in accordance with the present invention. In one embodiment, disk access requests may be performed during traversals of a disk head across a disk. Each traversal may have a specified direction of motion. A plurality of disk accesses may be performed during a disk head traversal. In some cases, disk accesses may be performed in an order different from the order in which the original disk access requests were received. The overall number of disk access requests for a given disk head traversal may be limited to a maximum number N. By limiting the number of disk reques
Kivlin B. Noäl
Nguyen Than
Sun Microsystems Inc.
LandOfFree
Disk scheduling system with bounded request reordering does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Disk scheduling system with bounded request reordering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Disk scheduling system with bounded request reordering will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2986659