To display an object X of media type Mi (say CD-quality audio) with bandwidth requirement RC(Mi) (1.34 Mbps), Mitra conceptualizes X as consisting of r blocks: X0, X1, ..., Xr-1. Assuming a block size of B(Mi), the display time of a block, termed a time period [GKS95], equals (B(Mi))/(RC(Mi)). Assuming that the system is idle, when a PM references object X, the Scheduler performs two tasks. First, it issues a read request for X0 to the DM. It also provides the network address of the PM, requesting the DM to forward X0 directly to the PM. Second, after a pre-specified delay, it sends a control message to the PM to initiate the display of X0. This delay is due to the implementation of both GSS [YCK93] (detailed below) and FIXB [GKSZ96] (described in the Discussion Section). Once the PM receives a block, it waits for a control message from the Scheduler before initiating the display. The Scheduler requests the DM to transmit the next block of X (i.e., X1) in the next time period to the PM. This enables the PM to provide for a smooth transition between the two blocks to provide for a hiccup-free display. With the current design, a PM requires enough memory to cache at least two blocks of data.
Given a database that consists of different
media types (say
=2, MPEG-2 and CD-quality audio),
the block size of each media type is determined such that the
display time of a block (i.e., the duration of a time period
at the Scheduler) is fixed for all media types.
This is done as follows.
First, one media type Mi (say CD-quality audio) with
bandwidth requirement RC(Mi) (1.34 Mbps)
defines the base block size B(Mi) (say 512 KByte).
The block size of other media types is a function of their
bandwidth, RC(Mi), and B(Mi).
For each media type Mj, its block size is:
B(Mj) = (RC(Mj))/(RC(Mi)) ×B(Mi)In our example, the block size for MPEG-2 (4 Mbps) objects would be 1521.74 KByte.
In an implementation of a file system, the physical characteristics of a magnetic disk determines the granularity for the size of a block. With almost all disk manufacturers, the granularity is limited to (1)/(2)KByte(2). Mitra rounds up the block size of each object of a media type to the nearest (1)/(2)KByte. Thus, in our example, the block size for MPEG-2 object would be 1522 KByte. However, Mitra does not adjust the duration of a time period to reflect this rounding up. This forces the system to produce more data on behalf of a display as compared to the amount that the display consumes per time period. The amount of accumulated data is dependent on both the number of blocks that constitute a clip and what fraction of each block is not displayed per time period. The amount of accumulated data is expected to be insignificant. For example, with a two hour MPEG-2 video object, a display would have accumulated 622.7 KByte of data at the end of the display. The PM-driven Section describes a scheduling paradigm that prevents the Scheduler from producing data should the amount of cached data become significant.)
Mitra supports the display of N objects by multiplexing the disk bandwidth among N block retrievals. Its admission control policy ensures that the service time of these N block retrievals does not exceed the duration of a time period. The service time of the disk to retrieve a block of media type i is a function of B(Mi), the disk transfer rate, rotational latency, and seek time. Mitra opens each disk in RAW mode [Hew91]. We used the SCSI commands to interrogate the physical characteristics of each disk to determine its track sizes, seek characteristics, number of zones, and transfer rate of each zone. (To gather this information, one requires neither specialized hardware nor the use of the assembly programming language, see [GSZ95] for a detailed description of these techniques.) The Scheduler reads this information from a configuration file during its startup.
The Scheduler maintains the duration of a time period using a global variable and supports a linked list of requests that are currently active. In addition to other information, an element of this list records the service time of the disk to retrieve a block of the file referenced by this display. Mitra minimizes the impact of seeks incurred when retrieving blocks of different objects by implementing the GSS algorithm. With GSS, a time period might be partitioned into g groups. In its simplest form, GSS is configured with one group (g=1). With g=1, a PM begins to consume the block that was retrieved on its behalf during time period l at the beginning of time period l+1. This enables the disk scheduling algorithm to minimize the impact of seeks by retrieving the blocks referenced during a time period using a scan policy. Mitra implements this by synchronizing the display of the first block of an object (X0) at the PM with the end of the time period that retrieved X0. Once the display of X0 is synchronized, the display of the other blocks are automatically synchronized due to a fixed duration for each time period. The synchronization of X0 is achieved as follows. A PM does not initiate the display of X0 until it receives a control message from the Scheduler. The Scheduler generates this message at the beginning of the time period that retrieved X1.
With g>1, Mitra partitions a time period into g equi-sized intervals. The Scheduler assigns a display to a single group and the display remains with this group until its display is complete. The retrieval of blocks assigned to a single group employs the elevator scheduling algorithm. This is implemented as follows. Assuming that group Gi retrieves a block of X per time period, the display of X0 is synchronized with the beginning of group Gi+1.