4.2. A Taxonomy of Deadline-driven Approaches

We can straightforwardly generalize double buffering to N buffering by using N buffers and prefetching N-1 blocks before initiating a display. The system can continue to request a block every time a memory buffer becomes empty. This reduces the probability of hiccup to p[ω > (N − 1)T_p] because the retrieval time of a block must now exceed (N-1) time periods in order for a display to incur a hiccup. Assuming a clip consists of n blocks which have display sequence from B₀ to B_n−1 and N buffers, at most N-1 blocks^[1] (from B₀ to B_N−2) can be prefetched and accumulated before starting display to provide a more tolerable variance in block retrieval time for the consecutive blocks (B_N−1 to B_n−1). This is because prefetching provides a time gap of (N – 1)T_P between the currently displayed block and the recently requested block. When the display of the first block B₀ is initiated and N-1 blocks are prefetched, a request for BN-₁ is issued. Then, unless its retrieval time is longer than (N − l)T_p, B_N−1 will be available when it is needed (after (N − 1)T_p). Therefore, hiccup probability of this approach can be defined as р[ω > (N − 1)T_P]. As demonstrated by Table 4.1, when the system load is 0.85, the hiccup probability decreases by a factor of 20 when N is increased from 2 to 3. With N buffering, there exist alternative ways of prefetching data and scheduling block retrievals. Figure 4.2 outlines a taxonomy of different techniques using a deadline -driven servicing policy where each block is tagged with a deadline and the disk services requests using an earliest-deadline-first (EDF) policy.

^[1] One buffer should be available to receive a block while one of N-1 blocks is being displayed.

This taxonomy differentiates between two stages of block retrieval on behalf of a display: (1) prefetching stage that requests the first N-1 blocks and (2) steady stage that requests the remaining blocks. The system may employ a different policy to tag blocks that constitute each stage. Furthermore, blocks can be issued either in a Bulk or Sequential manner. With Bulk, all requests are issued at the same time, while with Sequential, requests are issued one at a time whenever a buffer in client's memory becomes free. Note that Bulk is irrelevant during a steady stage because it is very expensive to prefetch the entire clip at the client. This explains why the Bulk branch is shown as a leaf node of steady in Figure 4.2. Similarly, Sequential is irrelevant during prefetching because N buffers are available and our objective is to minimize startup latency^[2]. The remaining leaves of the taxonomy are categorized based on how they assign deadline to each block: either Fixed or Variable. With Fixed, all block requests have identical deadlines while, with Variable, requests might have different deadlines.

^[2] If block requests are issued sequentially during the prefetching stage, the startup latency would increase as a linear function of N, see Figure 4.3.

During the steady stage (SS), a client issues a block request when a buffer in its memory becomes free. Typically, a memory buffer becomes free every time period because the display time of a block is one time period long. With SSF, a fixed deadline, (N − 1)T_p^[3], is assigned to all steady requests to maximize the tolerable variance of block retrieval time to prevent hiccups. However, with SSV, deadlines are determined by the number of blocks in the buffer. If the number of undisplayed blocks in the buffer is k when a block request is issued, then its deadline is set to k × T_p. SSV strives to maintain the maximum data in the buffer by making the buffer full as soon as possible, while SSF strives to prevent data starvation in the buffer. The results demonstrate that both techniques provide an almost identical performance.

^[3] We are using this notation for simplicity but the real deadline is t_issue + (N – 1)T_p, where t_issue is the time that this request is issued.

4.2.1. PB: Bulk Dispatching of Blocks During Prefetching Stage

While the prefetching with Sequential approach minimizes the hiccup probability, startup latency increases linearly as a function of the number of buffers, N. Thus, even though we can guarantee a desired hiccup probability, the increased startup latency may not fit to some applications; especially latency sensitive applications such as interactive applications. This linear increase is caused by the sequential request scheduling because it issues one request per time period. By changing the request scheduling, we can avoid this problem: when a clip is referenced, N − 1 requests for the first N − 1 blocks are concurrently issued as in Figure 4.4.a (bulk prefetching). This section describes alternative strategies for (a) when to initiate the display of A relative to the arrival of the N-1 blocks and (b) how to set the deadline for these bulk requests. Consider each in turn. A client may initiate display in two alternative ways: either 1) once all N-1 blocks have arrived, termed conservative display (CD), or 2) upon the arrival of block A_o, termed aggressive display (AD). In Section 4.3, we compare these two alternatives. The results demonstrate that AD is superior to CD.

The deadline assigned to the first N-1 blocks can be either fixed (termed Fixed, PBF) or variable (termed Variable, PBV). With PBV, block B_i is tagged with (i + 1)T_p as its deadline. Assuming that a client initiates display when all N-1 blocks have arrived (i.e., CD), the startup latency is determined by the longest retrieval time of the first N-1 requests, max(ω_o, ..., ω_N–2) where ω_i is the retrieval time of block B_i. PBF is more aggressive because it can set the deadline for all N-1 requests to T_p in order to minimize startup latency. These requests might compete with block requests issued by other clients that are in their steady stage, increasing the probability of hiccups. However, this increase is negligible because the number of clients that are in their prefetching stage is typically small.

Section 4.3 compares these four alternatives, namely, PBF-CD, PBF-AD, PBV-CD, PBV-AD. The results demonstrate that PBV-AD provides a performance almost identical to PBF-AD. These two techniques are superior to the other alternatives.

4.2.2. Two Approaches to Handle Hiccups

While our proposed techniques strive to minimize hiccups, they cannot eliminate them all together. Moreover, the policy used at the client to respond to a hiccup impacts the server. To elaborate, a client may respond in two alternative ways to a hiccup: either wait for the missing data indefinitely (termed Wait) or skip the missing data and continue the display with remaining blocks (termed Skip). In the first case, the display is resumed upon the arrival of the missing data. This means that the server must service all block requests, even those whose deadline has been violated. With Skip, the server may discard these block requests because a client no longer needs them, minimizing the server load.

With Skip, in addition to skipping content with hiccups, every time that a display incurs a hiccup, the probability of it incurring another hiccup increases exponentially. This is because the waiting tolerance of N buffering decreases to that of N-1 buffering since the number of buffers in the client's memory is reduced to N-2. One may extend Skip to delay the display of remaining blocks by one T_p in order to prevent this undesirable situation. (There is no advantage to making Skip delay for multiple time periods.)

As detailed in Section 4.3, Skip results in a lower hiccup probability when compared with Wait because it reduces the server load. In passing, it is important to note that a client should not issue block requests while waiting because its buffers may overflow.