2. Techniques

2. Techniques

In order to describe the alternative techniques, we assume a configuration consisting of K disk models: D0, D1,..., DK-1. There are qi disks belonging to disk model i: ,...,. A disk drive of model Di consists of mi zones. To illustrate, Figure 35.2 shows a configuration consisting of two disk models Do and D1 (K=2). There are two disks of each model (q0=q1=2), numbered ,,,. Disks of model 0 consist of 2 zones (m0=2) while those of model 1 consist of 3 zones (m1=3). Zone j of a disk (say ) is denoted as Zj(). Figure 35.2 shows a total of 10 zones for the 4 disk drives and their unique indexes. The kth physical track of a specific zone is indexed as PTk(Zj)).

click to expand
Figure 35.2: OLT1.

We use the set notation, { : }, to refer to a collection of tracks from different zones of several disk drives. This notation specifies a variable before the colon and the properties that each instance of the variable must satisfy after the colon. For example, to refer to the first track from all zones of the disk drives that belong to disk model 0, we write:

click to expand

With the configuration of Figure 35.2, this would expand to:

click to expand

2.1 IBM's Logical Track [25]

This section starts with a description of this technique for a single multi-zone disk drive. Subsequently, we introduce two variations of this technique, OLT1 and OLT2, for a heterogeneous collection of disk drives. While OLT1 constructs several logical disks from the physical disks, OLT2 provides the abstraction of only one logical disk. We describe each in turn.

With a single multi-zone disk drive, this technique constructs a logical track from each distinct zone provided by the disk drive. Conceptually, this approach provides equi-sized logical tracks with a single data transfer rate such that one can apply traditional continuous display techniques [2, 27, 3, 13, 21, 23]. With K different disk models, a naive approach would construct a logical track LTk by utilizing one track from each zone: LTk = {PTk(Zj()):i, j, p} where 0 j < mi and 0 i< K and 0 p < qi.

With this technique, the value of k is bounded by the zone with the fewest physical tracks, i.e., 0 k < Min[ NT(Zj()) ], where NT(Zj()) is the number of physical tracks in zone j of disk model Di. Large logical tracks result in a significant amount of memory per simultaneous display, rendering a continuous media server economically unavailable. In the next section, we describe two optimized versions of this technique that render its memory requirements reasonable.

2.2 Optimized Logical Track 1 (OLT1)

Assuming that a configuration consists of the same number of disks for each model, [5] OLT1 constructs logical disks by grouping one disk from each disk model (q logical disks). For each logical disk, it constructs a logical track consisting of one track from each physical zone of a disk drive. To illustrate, in Figure 35.2, we pair one disk from each model to form a logical disk drive. The two disks that constitute the first logical disk in Figure 35.2, i.e., disks and , consist of a different number of zones ( has 2 zones while has 3 zones). Thus, a logical track consists of 5 physical tracks, one from each zone.

Logical disks appear as a homogeneous collection of disk drives with the same bandwidth. There are a number of well known techniques that can guarantee hiccup-free display given such an abstraction, see [2, 27, 3, 13, 21, 23, 26]. Briefly, given a video clip X, these techniques partition X into equi-sized blocks that are striped across the available logical disks [3, 26, 27]: one block per logical disk in a round-robin manner. A block consists of either one or several logical tracks.

Let Ti denote the time to retrieve mi tracks from a single disk of model Di consisting of mi zones: Ti = mi (a revolution time + seek time). Then, the transfer rate of a logical track (RLT) is: RLT = (size of a logical track)/Max[Ti] for all i, 0 i < K.

In Figure 35.2, to retrieve a LT from the first logical disk, incurs 2 revolution times and 2 seeks to retrieve two physical tracks, while disk incurs 3 revolutions and 3 seeks to retrieve three physical tracks. Assuming a revolution time of 8.33 milliseconds (7200 rpm) and the average seek time of 10 milliseconds for both disk models, requires 36.66 milliseconds (T0 = 36.66) while requires 54.99 (T1 = 54.99) milliseconds to retrieve a LT. Thus, the transfer rate of the LT is determined by disk model D1. Assuming that a LT is 1 megabyte in size, its transfer rate is (size of a logical track)/Max[T0,TI] = 1 megabyte/54.99 milliseconds = 18.19 megabytes per second.

This example demonstrates that OLT1 wastes disk bandwidth by requiring one disk to wait for another to complete its physical track retrievals. In our example, this technique wastes 33.3 % of Do's bandwidth. In addition, this technique wastes disk space because the zone with the fewest physical tracks determines the total number of logical tracks. In particular, this technique eliminates the physical tracks of those zones that have more than NTmin tracks, NTmin=Min[NT(Zj()) ], i.e., it eliminates PTk( Zj() ) that have NTmin k < NT( Zj() ), for all i and j, 0 i<K and 0 j < mi.

2.3 Optimized Logical Track 2 (OLT2)

OLT2 extends OLT1 with the following additional assumption: each disk model has the same number of zones, i.e., mi is identical for all disk models, 0 i < K. Using this assumption, it constructs logical tracks by pairing physical tracks from zones that belong to different disk drives. This is advantageous for two reasons. First, it eliminates the seeks required per disk drive to retrieve the physical tracks. Second, assuming an identical revolution rate of all heterogeneous disks, it prevents one disk drive to wait for another.

The details of OLT2 are as follows. First, it reduces the number of zones of each disk to that of the disk with fewest zones: mmin = Min[mi] for all i, 0 i < K. Hence, we are considering only zones, Zj() for all i, j, and k (0 i < K, 0 j < mmin, and 0 k < q). For example, in Figure 35.3, the slowest zone of disks of and (Z2)are eliminated such that all disks utilize only two zones. This technique requires mmin disks of each disk model (totally mmin K disks). Next, it constructs LTs such that no two physical tracks (from two different zones) in a LT belong to one physical disk drive. A logical track LTk consists of a set of physical tracks:

(35.1) click to expand

click to expand
Figure 35.3: OLT2.

where . The total number of LTs is mmin NTmin, thus 0 k < mmin NTmin.

OLT2 may use several possible techniques to force all disks to have the same number of zones. For each disk with δZ zones more than mmin, it can either (a) merge two of its physically adjacent zones into one, repeatedly, until its number of logical zones is reduced to mmin, (b) eliminate its innermost δZ zones, or (c) a combination of (a) and (b). With (a), the number of simultaneous displays is reduced because the bandwidth of two merged zones is reduced to the bandwidth of the slower participating zone. With (b), OLT2 wastes disk space while increasing the average transfer rate of the disk drive, i.e., number of simultaneous displays. In [11], we describe a configuration planner that empowers a system administrator to strike a compromise between these two factors for one of the techniques described in this study (HetFIXB). The extensions of this planner in support of OLT2 is a part of our future research direction.

[5]This technique is applicable as long as the number of disks for each model is a multiple of the model with the fewest disk drives: if min(qi), 0 i < K, denotes the model with fewest disks, then qj is a multiple of min(qi).

Handbook of Video Databases. Design and Applications
Handbook of Video Databases: Design and Applications (Internet and Communications)
ISBN: 084937006X
EAN: 2147483647
Year: 2003
Pages: 393

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net