Method and apparatus for prioritizing video frame retrieval in a shared disk cluster

[0002] 1. Technical Field

[0003] The present invention relates in general, to video servers and in particular to shared disk clusters of video servers within a video on demand (VOD) system. More particularly, the present invention relates to video frame retrieval from shared disk clusters in a VOD system. Still more particularly, the present invention relates to out of order video frame retrieval requests from multiple video servers.

[0004] 2. Description of the Related Art

[0005] A VOD system typically includes ac storage server, a controller, a communications network and customer stations. Multiple videos are stored in digital form on a storage server and transmitted, or played out, to an end user—at the user's station—upon request. An end user would select an available movie (stored on the storage server) and the controller would transmit the selected movie over the communications network to the customer's station.

[0006] In order to cost-effectively meet customer demand, video storage servers are usually required to provide multiple current streams of multimedia data (i.e., videos) at the same time. During normal playout, data blocks containing ordered frames of the multimedia stream are retrieved from a storage system and transmitted to the receiving station (that of the end user). The receiving station decodes the incoming multimedia stream and plays it out. The receiving station is usually connected to the VOD service via a network and either cable or satellite. Within the VOD service the movies may be stored on hard disk drives, usually shared disk storage. Many shared disk storage systems are very large and provide data block feeds for multiple servers.

[0007] During normal playout, media (video) segments are retrieved (I/O request) by a video server, buffered in memory and then transmitted at a fixed rate to the receiving station. In shared-disk clusters of video servers, disk contention can result in poor video quality when disk requests are prioritized without reference to first video frame deadlines. While a single video server can control the order of issue of I/O requests, requests out of deadline order may be received by disks shared by multiple servers. This increases the probability that video frames will be dropped and the image quality of the video suffers.

[0008] Current shared disk subsystems nominally select the order that I/O (input/output) requests are satisfied by examining a queue of requests and ordering them in a scheme that will produce the minimum amount of disk drive read head movement. This is often referred to as an “elevator” algorithm where the disk drive head takes the next read closest to the current position of the drive head.

[0009] With the advent of real time data delivery, elevator algorithms are found to be counter productive to video timing requirements. For instance, requests that must be satisfied immediately may be ordered by the algorithm in a lower priority slot in lieu of requests whose disk address happens to be closer to the current disk head position.

[0010] Real time data delivery software often must compensate for elevator algorithms by either requesting one I/O at a time or turning off the elevator algorithm and making requests in priority order. For a multi-node system where multiple machines are requesting data from a single pool of disks, contention for transmit order may cause large variances in retrieval times from buffers of frames from shared disks, resulting in the transmitted video being perceived by the user as poor quality reception.

[0011] Therefore, it would be desirable to provide a method and apparatus that would improve the prioritizing of video data requests and reduce dropped video frames, which are seen by the viewer as poor quality television images.

[0012] It is therefore one object of the present invention to provide a method and apparatus for transmitting video data frames with no visible delay between data frames.

[0013] It is another object of the present invention to provide a method and apparatus for determining accurate times for prioritizing data frame disk reads associated with multiple video streams originating from a plurality of video servers.

[0014] It is yet another object of the present invention to provide a method and apparatus for which provides higher disk read rates with fewer missed frame deadlines, and requiring less memory buffering.

[0015] The foregoing objects are achieved as is now described. A first frame deadline is calculated and attached to an I/O request for prioritizing and retrieving video data frames from a shared disk cluster. Disk adapters queue video data frame requests according to the deadline incorporated in the frame requests. Data frames are transmitted to a requesting end user utilizing the attached deadline time to schedule the frames according to a time priority. Alternatively, a “slack” time until deadline is computed and utilized to determine the order in which the first frame and subsequent frames of the requested video data may be retrieved from disk to be present in the video server's memory in order to avoid a visible delay in sending that frame to the end user.

[0016] The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.

[0017] The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0018] FIG. 1 depicts a high-level block diagram of a video on demand system in which a preferred embodiment of the present invention may be implemented;

[0019] FIG. 2 is a high-level flow diagram of a method in accordance with a preferred embodiment of the present invention;

[0020] FIG. 3 depicts a high-level flow diagram of a modification of the method in accordance with a preferred embodiment of the present invention; and

[0021] FIG. 4 is a high-level block diagram of the process of scheduling frame packets in accordance with a preferred embodiment of the present invention.

[0022] With reference now to the figures, and in particular with reference to FIG. 1, a high-level block diagram of a video on demand system in which a preferred embodiment of the present invention may be implemented, is depicted. As depicted, video on demand system 100 includes end user stations 102, communication network 104 which may be a two-way cable television network, a telephone network, another wide-area network or local area network. Connected to communications network 104 is video server 106. Video server 106 includes memory buffer 108, Computer processing Unit (CPU) 110, disk adapter 112, disk controller 114, and shared disk cluster 116. Multiple disk drives (not shown) within disk cluster 116 store video data for multiple videos. Disk controller 114 controls reading and writing of data to the disk drives in disk cluster 116. Video data which is read from disk drives within disk cluster 116 is output from storage server 106 to communication network 104. The video data is then received by end user stations 102.

[0023] Depending on the size of a VOD system there may be multiple video servers and the objective of a VOD system is to provide each end user with the video data requested by that end user. Video data is retrieved, on request, by disk controllers 114 from disk cluster 116. The data is then sent to disk adapter 112 within Video Server 1 or 2. The data stream is smoothed out, using buffer memory 108 and subsequently transmitted in a continuous stream by CPU 1 or 2110 to user station 102 via communications network 104.

[0024] As indicated above, the video server is connected to a set of shared disks and streams multiple video channels to viewers by reading video data blocks from disk drives within shared disk cluster drive. Multiple viewers may be connected at any time and multiple video channels may be transmitted from the same server at the same time.

[0025] Transmitting video data blocks to end user stations is time critical. An end user sends a request for a video stream (movie) and the movie may be stored on multiple disks with video data blocks out of order. Large volume or intermediate storage of video data, in line with and prior to server buffer memory, is typically accomplished with Redundant Array of Inexpensive Disk (RAID) disk drive systems. The video server orders data blocks, that make up the movie, for transmission from each disk within the disk array to the end user. It is critical that data blocks from multiple disks, representing multiple video streams are sent on time to multiple users so that the end of one data block is seamlessly followed by the next data block in order to present a continuous movie.

[0026] Referring now to FIG. 2, a high-level flow diagram of a method for prioritizing video frame retrieval in a shared disk cluster in accordance with a preferred embodiment of the present invention, is illustrated. The method, or process, should be considered in concert with FIG. 1. FIG. 1 block diagram also shows the scheme which each CPU, disk adapter and disk controller combination employs to jointly prioritize disk requests to minimize missed frame deadlines. The process for providing prioritization begins with step 200, which depicts an end user connecting to a video server and making a request for a movie (video stream). The process continues to step 202, which illustrates the video server prefilling the memory buffer with data frames of the movie request. The process then proceeds to step 204, which depicts the video server sending the next frame to the requesting station. Next, the process passes to step 206 which illustrates the CPU of each connected server computing “wall clock” time (real time) deadline, which is the time the next disk block containing the next frame or set of sequential frames must be resident in the memory buffer.

[0027] The process then proceeds to step 208, which depicts the CPU computing “slack time.” Slack time is saved to each disk read request command packet (see FIG. 4) and is equal to deadline time less the current time at which the command packet is sent to the disk adapter. The process next passes to step 210, which depicts the disk read request being issued to the disk adapter. The process continues to step 212, which illustrates read commands being queued in the disk adapter. While in the disk adapter queue, slack time of each read command is regularly decremented so that the waiting time of the read command in queue is reflected. The process then passes to step 214, which depicts a disk controller requesting another command and the disk adapter sending a read command having the least slack time remaining.

[0028] The process continues to step 216, which illustrates a disk controller retrieving a data block associated with the read command. The process proceeds to step 218, which depicts disk controllers queuing read commands for the disk storage system from all CPU adapters in least slack time order. As described in step 212, slack time is regularly decremented by the time the command remains in queue in the disk controller to reflect the waiting time in the queue. Read requests from CPU 1 and CPU 2 (see FIG. 1) are then sequenced by least slack time. Next the process passes to step 218, which illustrates the disk drive completing the current read command and the disk controller issuing another read command, having the next least slack time, to the disk arm. The process then proceeds to step 220, which depicts completed read commands sending the data to the disk adapter in least slack time order.

[0029] The process continues to step 222, which illustrates data being received by the buffer in least slack time order. The process then passes to step 224, which depicts video frames sent by CPUs in the video server from the buffer to a user station.

[0030] Even though the process depicts transmitting data from a single server to a single station, there may be multiple video streams through the same server to multiple stations. The frames are entered into the buffer in slack time order instead of first come, first serve or nearest track order (elevator order). This procedure allows the server to provide data streams with fewer missed frame deadlines and therefore fewer dropped frames thus, providing a more consistent viewing. Also, since there is less variance in disk read response times, higher disk I/O rates result and less memory buffering is required; reducing cost. Less memory buffering also provides that first frame startup time is shorter for the viewer.

[0031] Referring to FIG. 3, a method for prioritizing video frames utilizing earliest frame deadline, in accordance with a preferred embodiment of the present invention, is depicted. The process begins with step 300, which depicts the CPUs in the video servers synchronizing real time clocks within one millisecond (ms) utilizing a known method such as Network Time Service. The process then proceeds to step 302, which illustrates a video server prefilling the memory buffer with data frames of a movie request from a user station. The process then proceeds to step 304, which depicts the video server sending the next frame to the requesting station. Next, the process passes to step 306 which illustrates the CPU of each connected server computing “wall clock” time (real time) deadline, which is the time the next disk block must be resident in the memory buffer. The process then continues to step 308, which depicts the CPU saving block deadline time, less one millisecond synchronizing error, in a disk read request packet. Next the process passes to step 310, which illustrates the disk adapter queuing read commands in “earliest deadline, transmitted first” order. Using real-time to schedule data packets eliminates the need to account for time in queue.

[0032] The process then proceeds to step 312, which depicts read commands being queued in earliest deadline order. Next the process continues to step 314, which illustrates the disk controller completing a command and requesting another command. A read command with the earliest deadline time is then sent to the disk controller. The process passes to step 316, which depicts disk controller queuing read commands from ALL CPU disk adapters. The commands are queued in “earliest deadline, transmitted first” order. When a disk drive regulated by the disk controller completes a current read command, the process proceeds to step 318, which depicts the disk controller issuing the next read command, with earliest deadline to the disk drive arm.

[0033] The process then passes to step 320, which illustrates completed read commands sending data to the disk adapter in earliest deadline time order. The process continues to step 322, which depicts data being received by the buffer in earliest deadline time order. The process then passes to step 324, which illustrates video frames sent by CPUs in the video server from the buffer to a user station via a communications network.

[0034] Though the process depicts transmitting data from a single server to a single station, there may be multiple video streams through the same server to multiple stations. The frames are entered into the buffer in earliest deadline time order instead of first come first serve or nearest track order (elevator order). This allows the server to provide data streams with fewer missed frame deadlines, and therefore fewer dropped frames, thus providing more consistent viewing. Also, since there is less variance in disk read response times, higher disk I/O rates result and less memory buffering is required, thus reducing cost. Less memory buffering also indicates first frame startup time is shorter for the viewer.

[0035] Referring now to FIG. 4, a high-level block diagram of the process of ordering frame packets in accordance with a preferred embodiment of the present invention, is illustrated. Disk.command packet 400 comprises a disk adapter routing packet 410 containing a disk controller command packet 420. Both packets are prepared by a disk driver software portion of a typical CPU resident operating system. The disk adapter routing packet 410 is modified to include slack time (add or modify a 2 byte field) or deadline time stamp (provide an 8 byte field in adapter packet for a time stamp). The slack time or deadline time stamp which is read and updated by disk adapter microcode is modified to send commands to shared disk controllers 114 in least slack time order.

[0036] As disk adapter routing packet 410 arrives at the addressed disk controller 114, modified microcode in disk controller 114 updates the slack time as previously described, and issues commands to disk head (not shown) in least slack time order. Earliest deadline time processing is as described above, except that earliest deadline time need not be updated.

[0037] After command packet 420 retrieves the data requested, disk controller 114 sends routing packet 410, containing command packet 420, back to disk adapter 112 which then routes the packets retrieved to memory buffer 108. Video data packet streams for different stations (users) are depicted in FIG. 4 with data frame packets 404 intended for Station A 102 and data frame packets 402 intended for Station B 102. As shown, a data frame packet 404 for user A contains the data frame for station A and a deadline time 403 of 12 milliseconds. A data frame packet 402 for user B contains the data frame for station 102 B, and deadline time 401 of 14 milliseconds. The data frame packet shown between packets 402 and 404 has a deadline time set between 12 and 14 milliseconds.

[0038] Scheduling time critical video data packets according to time allows for efficient transmittal of data frames having no visible delay between frames. Higher disk read rates are accomplished with fewer missed frame deadlines. Utilizing either slack time or deadline time, worst case disk response times are reduced for retrieving disk reads associated with multiple video streams originating from a plurality of video'servers.

[0039] It is important to note that while the present invention has been described in the context of a fully functional device, those skilled in the art will appreciate that the mechanism of the present invention and/or aspects thereof are capable of being distributed in the form of a computer usable medium of instructions in a variety of forms, and that the present invention applies equally regardless of the particular type of signal and switching bearing media used to actually carry out the distribution. Examples of computer usable media include: nonvolatile, hard-coded type media such as read only memories (ROMs) or erasable, electrically programmable read only memories (EEPROMs), recordable type media such as floppy disks, hard disk drives and CD-ROMs, and transmission type media such as digital and analog communication links.

[0040] While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention.