2.2. Overview of SM Techniques

A basic approach to support continuous display in a single disk SM server is to divide an SM object into equi-sized blocks. Each block is a unit of retrieval and is stored contiguously. For example, a SM object X is divided into n equi-sized blocks: X₀, X₁, X₂, …, X_n–1. The size of blocks, the display time of a block, and the time to read a block from a disk drive can be calculated as a function of display bandwidth requirement of an object, the number of maximum simultaneous displays that a disk drive can support, and the physical disk characteristics such as the data transfer rate. Upon the request for the SM object X, the system stages the first block of X, i.e., X_o, from the disk into main memory and initiates its display. Prior to the completion of the display of X_o, the system stages the next block X₁ from the disk into main memory to provide for a smooth transition and a hiccup-free display. This process is repeated until all blocks of X are displayed. This process introduces the concept of a time period (T_p), which denotes the time to display a block. For example, the display time of one 0.5 MByte block of a SM object encoded with 4 Mb/s is one second (T_p = 1 sec).

In general, the display time of a block is longer than its retrieval time from a disk drive. Thus, the bandwidth of a disk drive can be multiplexed among multiple simultaneous displays accessing the same disk drive. For example, with the 4 Mb/s of display bandwidth requirement of MPEG-2 encoded objects, a disk drive with the 80 Mb/s of data transfer rate can support up to 20 simultaneous displays. This is the ideal case when there is no overhead in disk operation. However, in reality, a magnetic disk drive is a mechanical device and incurs a delay when required to retrieve data. This delay consists of: 1) seek time to reposition the disk head from the current track to the target track, and 2) rotational latency to wait until the data block arrives under the disk head. These are wasteful operations that prevent a disk drive from transferring data. Both their number of occurrence and duration of each occurrence must be reduced in order to maximize the number of simultaneous displays supported by a disk drive. Thus, the performance of SM servers significantly depends on the physical characteristics of magnetic disk drives such as data transfer rate, seek times, and rotational latency. For example, it is obvious that we can increase the throughput of a server using disk drives having a higher data transfer rate.

Another important physical characteristic of a magnetic disk drive is its zones: a disk consists of several zones with each providing a different storage capacity and transfer rate. Zone-bit recording (ZBR) is an approach utilized by disk manufactures to increase the storage capacity of magnetic disks, as described in Section 2.1.1. This technique groups adjacent disk cylinders into zones [139], [121]. Tracks are longer towards the outer portions of a disk platter as compared to the inner portions, hence, more data may be recorded in the outer tracks when the maximum linear density, i.e., bits per inch, is applied to all tracks. A zone is a contiguous collection of disk cylinders whose tracks have the same storage capacity, i.e., the number of sectors per track is constant in the same zone. Hence, outer tracks have more sectors per track than inner zones. Different disk models have a different number of zones. For example, a disk may consist of 7 zones while another one may consist of 9 zones.

Different zones provide a different transfer rate because: 1) the storage capacity of the tracks for each zone is different, and 2) the disk platters rotate at a fixed number of revolutions per second. Assuming a constant recording density in tracks, typical disks provide the maximum data transfer rates from the outermost zones and the minimum ones from the innermost zones. One can observe a significant difference in data transfer rates between the minimum and maximum (more than 50%).

This chapter introduces two important components of a SM server design: scheduling of the disk bandwidth and placement of data blocks. Traditionally, SM servers employ the scheduling of the available disk bandwidth to guarantee a continuous display and to maximize the throughput by minimizing the wasteful work of disk drives. Among various possible disk scheduling algorithms such as first-come-first-serve, shortest-seek-first, SCAN, elevator [44], and earliest-deadline-first (EDF) [168], [104], two scheduling approaches are widely utilized: deadline-driven and cycle-based. A technique for real-time scheduling of I/O tasks is a deadline-driven approach and it can be applied for the scheduling of SM data retrievals [138]. With this approach, a request for a block is tagged with a deadline that ensures a continuous display. Disks are scheduled to service requests with EDF. A limitation of this approach is that seek times may not be optimized because the sequence of block retrievals are determined by deadlines.

A cycle-based scheduling technique [70], [126], [170] is an approach exploiting the periodic nature of SM display. A time period is partitioned into a number of time slots (N) such that the duration of a slot is long enough to retrieve a block from a disk. The number of slots denotes the number of simultaneous displays supported by the system. During a given time period (or a cycle), the system retrieves up to N blocks, only one block for each display. Block requests for the next cycle are not issued until the current cycle ends. During the next cycle, the system retrieves the next blocks for displays in a cyclic manner. For example, assuming that the system can support up to three block retrievals during a time period, suppose that the system retrieves X_i, Y_j, and Z_k for a given time period. During the next time period, it retrieves X_i+1, Y_j+1, and Z_k+1.

Another way to reduce the worst seek time is to control the location of data blocks. Based on the observation of the typical sequential access pattern of continuous data blocks, one can place adjacent data blocks in the way that minimize the seek time between two retrievals.

A number of studies have investigated techniques to support a hiccup-free display of SM using magnetic disk drives with a single zone [9], [12], [13], [26], [59], [135], [136], [138], [175], [183], [70]. These studies assume a fixed data transfer rate for a disk drive. If a system designer elects to use one of these techniques with multi-zone disks, the system is forced to use the minimum data transfer rate of the zones for the entire disk in order to guarantee a continuous display of video objects. This approach results in a significant reduction of data transfer rate by wasting the transfer rates of outer zones. A couple of studies strive to cure this limitation by modelling a multi-zone disk drive as a logical single-zone disk. Track Pairing (TP) [15] provides logical tracks with an identical storage capacity by pairing two physical tracks (see Section 2.5.1). Logical Track (LT) [85] constructs a logical track by combining one physical track from each zone (see Section 2.5.2). Then, one can construct a SM server based on logical single-zone disks using one of traditional continuous display techniques. We introduce two alternative techniques, FIXB and VARB, that harness the average transfer rate of zones while ensuring a continuous display.