UvA-DARE (Digital Academic Repository) A queueing-theoretic analysis of the threshold-based exhaustive data-backup scheduling policy

ARTICLES IN On the optimal use of a slow server in two-stage queueing systems Abstract. We analyse the threshold-based exhaustive data backup scheduling mechanism by means of a queueing-theoretic approach. Data packets that have not yet been backed up are modelled by customers waiting for service (back-up). We obtain the probability generating function of the system content (backlog size) at random slot boundaries in steady state.


INTRODUCTION
The last decade has witnessed a tremendous growth in data produced and stored. In a recent McKinsey report, it was stated that "by 2009, nearly all sectors in the US economy had at least an average of 200 terabytes of stored data (twice the size of US retailer Wal-Mart's data warehouse in 1999) per company with more than 1,000 employees" and that "the increasing volume and detail of information captured by enterprises, the rise of multimedia, social media, and the Internet of Things will fuel exponential growth in data for the foreseeable future" [1]. This creates various challenges, among which extracting valuable data from large data sets, i.e., data mining, security (authenticity, integrity), making backups to protect against data loss due to hardware failure, accidental deletion, theft, et cetera.
In order to alleviate the backup assignment of the huge amounts of data of various users, research has been carried out to reduce the amount of data to backup, e.g. by compression techniques. We refer to Tan et al. [2] and Vrable et al. [3] and the references therein. However, even with these data reduction techniques, the amount of data to be backed up and the number of users remain large. Hence, there is a need for efficient data backup scheduling policies, tackling the trade-off between not backing up too frequently to maintain sufficient capacity while keeping the age of data and backlog size sufficiently small to minimize the amount of data at risk of loss.
We analyse a basic data backup scheduling mechanism by means of a queueing-theoretic approach. The backup scheduling mechanism considered here is a threshold-based exhaustive policy, that is, a data backup is initiated as soon as the backlog size reaches or exceeds some threshold, and an ongoing backup is finished when the backlog size becomes zero, that is when all data is backed up including new data that has been created during the backup process. The corresponding queueing model is described and its analysis is briefly sketched in the subsequent sections.
To the best of our knowledge, there is a lack of formal mathematical models for backup scheduling. We are only aware of the paper of van de Ven et al. [4], where a discrete-time queueing model for a distributed backup scheduling protocol for corporate networks with homogeneous users (i.e., same data production and connectivity patterns) is

DATA BACKUP QUEUEING MODEL
The objective of developing a queueing model is to obtain a formula for the backlog size, that is the data that has not yet been backed up. The queueing model has the following features: • Time is slotted, that is, a discrete-time queueing model is considered.
• Data packets that have not been backed up are modelled to await backup (service) in a queue.
• During a slot a number of packets can arrive at the queue, that is, new packets are created; the number of arrivals during some slot k is denoted by A k and {A k ; k ≥ 0} is modelled as a sequence of independent and identically distributed (iid) random variables, with common probability mass function (pmf) a(n), n ≥ 0 and probability generating function (pgf) A(z). The mean number of arrivals during a random slot is denoted by λ. • When no backup is being carried out, a backup will be initiated at the first slot boundary where the backlog size, that is the system content, reaches or exceeds the threshold l. • The capacity of the backup server equals c, meaning that maximum c packets can be backed up in a slot.
• The server continues backing up until the backlog size becomes 0 again. Hence, at backup completion, the backlog size equals 0. • Arriving customers can immediately, that is in their slot of arrival, be taken into service if service is going on in that slot and capacity is available. This feature is in literature referred to as early arrivals.
In fact, the queueing model considered here is a discrete-time queueing model with batch service and N-policy (with N = l). In literature, the combination of batch service and N-policy has rarely been considered. To the best of our knowledge, only Arumuganathan and Jeyakumar [5], and Reddy et al. [6] incorporate both features, but in continuous time, which is not useful for our purpose.

ANALYSIS OF THE MODEL
Through a partial-generating function approach, we obtain the pgf U(z) of the system content, that is the data that has not yet been backed up, at random slot boundaries in steady state. The pgf U(z) is obtained as follows: 1} , • U k : system content at slot boundary k, • τ k = 0 if no backup is going on in slot k; τ k = 1 otherwise, • U 1 (z) := ∞ n=1 u 1 (n)z n . After some calculations, the following expression for U 1 (z) is obtained: Equation (1) contains c + l unknown constants u 0 (0), . . . , u 0 (l − 1), v 1 (1), . . . , v 1 (c), which can be determined once a set of c + l linearly independent equations in these unknowns are determined. First, c − 1 linearly independent equations are found by means of the standard approach of relying on Rouché's theorem and the analytic property of pgfs [7]:

200002-2
with z i the c − 1 zeroes of z c − A(z) different from 1 inside the closed complex unit disk {z ∈ C : |z| ≤ 1}. The other equations can be found through probabilistic reasoning, that is linking the state in a slot with feasible states in the previous slot, leading to and by applying the normalization condition on U(z):

CONCLUSIONS AND FUTURE WORK
A queueing system is developed and analysed to model a threshold-based exhaustive backup policy. This paper is one of the first to address the data backup challenge from a queueing-theoretic point of view. To the best of our knowledge, only van de Ven et al. also consider this point of view [4]. Whereas we study a threshold-based policy, van de Ven et al. examine a probabilistic backup policy, that is at each time slot the user decides with some probability whether to initiate a backup, regardless of the backlog size.
There are several directions for future research. The assumption of iid sequence {A k } may be relaxed, because in practice it is likely that the arrival process exhibits some cyclic pattern, as described by van de Ven et al. [4]. Our approach will then have to be slightly adapted by using partial or vector generating functions instead of probability generating functions, in order to keep track of the position within the cycle. Also, other backup policies could be studied and compared one to another. We have started analysing the threshold-based gated backup policy through a similar analysis technique, but we have obtained a functional equation which we have not yet been able to solve. Another possibility is to study a model that combines a threshold policy with a timer policy to ensure that the age of the data does not become excessive. This would result in some kind of discrete-time batch-service queueing model with NT policy.