We consider model based estimates for set-up time. The general setting we are interested in is the following: given a disk and a sequence of read/write requests to certain locations, we would like to know the total time of transitions (set-up time) when these requests are served in an orderly fashion. The problem becomes nontrivial when we have, as is typically the case, only the counts of requests to each location rather then the whole input, and we can only hope to estimate the required time. Models that estimate set-up time have been suggested and heavily used as far back as the sixties. However, not much theory exists to enable a qualitative understanding of such models. To this end we introduce several properties such as (i) super-additivity which means that the set-up time estimate decreases as the input data is refined (ii) monotonicity which means that more activity produces more set-up time, (iii) Dominance which means that one model always produces higher estimates than a second model and (iv) approximation guarantees for the estimate with respect to the worst possible time, by which we can study different models. We provide criteria for super-additivity and monotonicity to hold for popular models such as the Partial Markov model (PMM). The criteria show that the estimate produced by these models will be monotone for any reasonable system. We also show that the independent reference model (IRM) based estimate functions as a worst case estimate in the sense that the estimate is guaranteed to be at least half of the actual set-up time. We also show that it dominates the PMM based estimates. Using our criteria we prove that PMM based estimates are always super additive when applied to the special metrics that correspond to seek times of disk drives. To establish our theoretical results we use the theory of finite metric spaces, and en route show a result of independent interest in that theory, which is a strengthening of a theorem of J.B. Kelly [J.B. Kelly, Hypermetric spaces and metric transforms, in: O. Shisha (Ed.), Inequalities III, 1972, pp. 149-158] about the properties of metrics that are formed by concave functions on the line.
展开▼
机译：我们考虑建立时间的基于模型的估计。我们感兴趣的常规设置如下：给定磁盘和对某些位置的一系列读/写请求，我们希望知道按顺序提供这些请求时的转换总时间（设置时间）时尚。当我们通常只有每个位置的请求计数而不是整个输入的计数时，问题就变得不那么重要了，我们只能希望估计所需的时间。已经提出了估计建立时间的模型，并且早在60年代就已大量使用。但是，没有太多理论可以对这种模型进行定性的理解。为此，我们引入了几个属性，例如（i）超可加性，这意味着随着输入数据的细化，建立时间的估计值会减少（ii）单调性，这意味着更多的活动会产生更多的建立时间，（iii）支配地位，这意味着一个模型总是比第二个模型产生更高的估计，并且（iv）就最坏的可能时间而言，该估计具有近似保证，由此我们可以研究不同的模型。我们为超可加性和单调性提供了适用于流行模型（例如部分马尔可夫模型（PMM））的标准。该标准表明，对于任何合理的系统，这些模型产生的估计都是单调的。我们还表明，基于独立参考模型（IRM）的估计在保证保证至少为实际设置时间一半的意义上起着最坏情况的估计的作用。我们还表明，它主导了基于PMM的估计。使用我们的标准，我们证明了将基于PMM的估计应用于与磁盘驱动器查找时间相对应的特殊指标时，始终具有超加性。为了建立我们的理论结果，我们使用有限度量空间理论，并且在途中显示出对该理论具有独立兴趣的结果，这是对J.B. Kelly [J.B. Kelly，《超度量空间和度量变换》，见：O。Shisha（Ed。），《不等式III》，1972年，第149-158页]，介绍了在线上凹函数形成的度量的属性。
展开▼
