Resource Discovery



Placement Strategies of Intermittently Available Environments

Yun Huang and Nalini Venkatasubramanian

Dept. of Information & Computer Science

University of California, Irvine

Irvine, CA 92697-3425, USA

{yunh, nalini}@ ics.uci.edu

Abstract

In this paper, we address the problem of data placement in a grid based multimedia environment, where the resource providers, i.e. servers, are intermittently available. The goal is to optimize the system performance by admitting maximum number of users into the system while ensuring user Quality of Service (QoS). Effective utilization of storage resources is key for providing continuous availability of data to end-users despite server downtimes. We define and formulate various placement strategies that determine the degree of replication necessary for video objects by using a cost-based optimization procedure based on a priori predictions of expected subscriber requests under various time-map scenarios and QoS demands. We also devise methods for dereplication of videos based on changes in popularity and server usage patterns. Our performance results indicate the benefits obtained the judicious use of dynamic placement strategies.

1. Introduction

Global grid infrastructures [FK98, A99] enable the use of idle computing and communication resources distributed in a wide-area environment; and upon a properly managed grid system infrastructure, multimedia applications that provide delivery of multimedia information are especially well suited, since much of information is read-only, coherence of multiple replicas is not an issue. However, systems on a computational grid are not continuously available.

We define “intermittently available” system as those in which servers and service providers may not be available all the time, e.g. grid-based systems might provide resources/services for only a few hours a day. Effective load management in an intermittently available multimedia environment requires:

• Resource discovery and scheduling mechanisms that will ensure the continuity of data to the user while servers are intermittently available.

• Data placement mechanisms to ensure that popularly requested information is replicated such that the data is always available.

We have addressed the first issue in [HV02]. In this paper, we focus on the second topic.

Generally, a placement policy for a multimedia (MM) system will address: (a) how many replicas needed for each MM object; (b) where to replicate, which servers the replicas should be created on; (c) when to make replicas. Given the network bandwidth constraints of each server, these decisions directly affect the system performance, i.e. the acceptability of concurrent requests for different MM objects. A bad placement policy will definitely deteriorate the system performance, in that it causes more replicas only to occupy the storage resources but not in service for requests; less replicas to be in service. So, the ideal placement policy is to provide the system the adaptability for the request pattern, that is, to own the capability of adjust the mapping of replicas on the servers according to the run-time request pattern. Previous work has addressed issues in data placement for servers that are continuous available [CGL99] [LD: no year]. But, in our system model, the servers are intermittently available, so it brings more complexities to the data placement problems, as besides the request pattern, the network bandwidth factors of the servers, we also need to take the time map of each server into account. In the remainder of this paper, without losing generality, we generalize the MM objects to video objects.

In this paper, we define and formulate 3 static placement strategies to initialize the mapping of replicas on servers, 2 dynamic placement strategies either to satisfy an individual incoming request, or to determine the degree of replication necessary for popular videos for overall system requests by using a cost-based optimization procedure based on a priori predictions of expected subscriber requests under various time-map scenarios. To optimize storage utilization, we also devise methods for dereplication of videos based on changes in their popularities and in server usage patterns.

The rest of this paper is organized as follows. We illustrate the system architecture in Section 2. Section 3 introduces the different placement strategies in such an intermittently available environment. Section 4 details the dynamic placement process, especially elaborate the algorithm of pseudo replication and pseudo dereplication. We evaluate the performance of the proposed approaches in Section 5 and conclude in Section 6 with future research directions.

2. System Architecture

The envisioned system consists of clients and multimedia servers distributed across a wide area network. The distributed servers provide resources to store the multimedia data that can be streamed or downloaded to clients at suitable QoS levels. The resources provided include high capacity storage devices (e.g. hard-disks), processor, buffer memory, and high-speed network interfaces for real-time multimedia retrieval and transmission. Servers may be intermittently available and the time map of servers containing available server times is predetermined. However, the availability of resources on servers can vary dynamically; furthermore, due to replication and dereplication of video objects, the stored data can change dynamically. To accommodate a large number of video objects, the environment includes tertiary storage[1].

Clients issue requests for multimedia information that may be replicated across servers. Client requests can vary significantly; hence requests are parameterized to specify the data resource requirements and service characteristics – i.e. earliest start time, latest finish time, service duration, and whether the service required is continuous or discontinuous etc. The key component of the infrastructure is a brokerage service. All incoming requests from clients are routed to the broker that determines whether or not to accept the request based on current system conditions and request characteristics. Specifically, the broker:

a) discovers the appropriate set of resources to handle an incoming request;

b) coordinates resource reservation and schedules these requests on the selected resources.

c) initiates replication and dereplication of multimedia objects to cater to changes in request pattern and load conditions.

Several kinds of information are required to ensure effective resource provisioning – this includes server resource availabilities, server time maps, replica maps, network conditions etc. This information is held in a directory service (DS) that is accessed and updated suitably by the broker. Using state information in the DS, the broker determines a candidate sever or a set of servers that can satisfy the request. Once a solution for the incoming request (i.e. scheduled servers and times) has been determined, the broker will update the directory service to reflect the allocated schedule. The goal is to improve the overall system performance, in order to facilitate more requests. If the broker determines that more than one server must provide the desired service, it transforms the single user request to multiple requests that will execute on the different servers. The service provided may be continuous or discontinuous; and can be finished without or with some delay. In the typical mode of operation, the servers guarantee the provision of appropriate quality of service to each request, once resources have been reserved.

3. Placement Strategies

Given the time map and server resource configurations, an effective placement strategy will determine the optimal mapping of replicas to servers, so that the overall system performance is improved and accepted requests will be guaranteed QoS. Specifically, a placement policy for a multimedia (MM) system will address: (a) how many replicas needed for each MM object; (b) where to replicate, which servers the replicas should be created on; (c) when to make replicas. Placement decisions can be made statically in advance or dynamically changed at runtime based on request arrival patterns. We propose a family of static and dynamic placement policies (as in Fig 2) that can be used in intermittently available environments. Compared with the on-demand placement strategy, which tries to satisfy an incoming request, the time-aware predictive placements are to improve the overall request acceptance based on a prediction of the requests for a following period of time. Especially, we specify the Time-aware Predictive Placement (TAPP) algorithm that uses a cost-based optimization procedure based on a priori predictions of expected subscriber requests. In this paper, we will try to define and formalize the dynamic placement strategies, and evaluate the system performance.

1. Static placement strategies

Our objective is to improve the overall system utilization and number of the concurrent users, another words, we focus on the policies that minimize the overall number of rejections, while keeping the load balance among the servers. There are two main ways to deal with how many replicas needed for each video data. One is based on the request popularity of each video; the other is to decide evenly or randomly without caring about the popularity. To settle down the problem of which data replica is stored on which server, we propose deterministic and non-deterministic (random) placement policies to initialize the servers.

We propose deterministic and non-deterministic placement policies to determine which replica is created on which server.

• SP1: Cluster-based static placement – Ordinarily, an equal placement strategy attempts to create an equal number of replicas for each video object. The cluster-based placement enhances the rudimentary placement to accept the intermittently availability of servers. Cluster the servers into groups so that the total available service time of each group covers the entire day. Each video object is associated with exactly one group, so that every server in the group has a replica of this video object.

• SP2: Popularity-enhanced deterministic placement – Classify the video objects into two groups of very-popular and less-popular. A replica of very-popular video object is placed on every server, assuming resource availability. Less-popular video objects are evenly placed in the remaining storage space. The even placement policy attempts to create an equal number of replicas for less-popular video objects.

• SP3: Popularity-based random placement – Choose the number of replicas for a video object based on its popularity, and randomly distributed these replicas among the feasible servers, that have available disk storage.

In the remainder of this paper, we will use SP1, SP2 and SP3 to identify the three static placement strategies.

2. Dynamic placement strategies

The dynamic placement strategies we propose consider the available disk storage, the current load on the servers, and the changing request patterns for access to video objects. We model the incoming request R from the client as:

R: < VID R , ST R , ET R , Type R, QoS R >

Where VID R corresponds to the requested video ID; ST R is the request start time; ET R is the end time by which the request should be finished; Type R represents the type of the request including (a) immediacy of the response (b) whether the request must be continuous or can be discontinuous and (c) whether the request must be executed on a simple server or may be executed on multiple servers. QoS R represents the QoS parameters of the request, i.e. the resources required by the request and the duration for which these resources are needed. We model the resources needed by a request using 4 parameters: the required disk bandwidth (R DBW), required memory resource (R MEM), required CPU (R CPU ) , and the required network transfer bandwidth (RNBW); Dv represents the duration for which these resources are required

In order to deal with the capacity of each server over time in a unified way, we define a Load Factor (R, S, t) for a request r on server s at time t, as:

Thus, the Load Factor of a server s at time t, LF(R, S, t), is determined by the bottleneck resource at time t. We use the average load-factor over all time units (between ST R and ET R) during which the server is available. For example, if the granularity of the time units in a day is 24 (24 hours/day), and ST R is 5am and ET R is 10am, then we consider

LF (s) = Average (LF5, LF6, LF7, LF8, LF9, LF10).

Dynamic placement strategies can classified based on whether they are initiated on-demand to satisfy an individual request, or initiated in advance based on predicted request arrivals. The on-demand strategy is myopic since it is focused on a single request; while the predicative strategy attempts to provide better overall performance for a large number of requests.

On-demand Placement

The on-demand placement strategy is a request-driven that can be used when the broker can not find the available servers to schedule the coming request. This policy is to find a server (or a set of servers) whose disk(s) has (have) no replica for the requested video, but has available network bandwidth and will be able to provide service for the requested period, also has (have) or will be able to have enough storage for making a new requested replica. So, there will be two main steps of this strategy:

First, check for sufficient available network bandwidth resources for service request. At this step, when selecting the server(s) for new replica, we ignore the multiple servers’ cases for on-demand placement due to the added complexity and overhead of scheduling multiple replications (and future dereplications) for satisfying a single request. The on-demand placement policy studied in this paper selects a single candidate server that has sufficient resource that can provide continuous service for the request time period. If there are many candidate servers, the policy will choose the one which is least loaded, that is, i.e. has the minimum Load Factor of the server. (this is also to solve the ties, so put together with “ways to solve the ties of dereplicated replicas”?)

Second, check for sufficient storage resources to create a replica. If the server chosen for new replica of the requested video has enough disk space available to create the replica of the required video, then a replica is created and the request is scheduled on this server. However, if the server’s storage is fully occupied by other video replicas, then dereplication of one or more video replicas that are not in use or has not been reserved for future use is necessary so as to free the storage space for the new replica. At this point, either there are some replicas that can be dereplicated, then do replication and schedule the request on this server; or there may be no enough replicas to be dereplicated and free space, then it has to give up this server, and continue to check next server(s) that may be able to satisfy the requests in order of increasing load factor, until there is no one server can be applicable and this request is rejected.

There are many ways to solve the ties of dereplicated replicas, such as: randomly pick one of them; or choose the one that have been accessed the least number of times before. It seems that the first one is not good in that it may dereplicate the most popular video replicas on this server. So, we use the second approach, but the system has to keep track of the accesses to all replicas on each server.

(In detailed algorithm [Appendix], if returnServer is not null, then schedule the request on the returnServer; otherwise, reject the request.)

With low startup latencies, large amounts of server bandwidth and tertiary bandwidth are required to create replicas, hence the on-demand policy may not always be feasible.

Predictive Placement Strategies

Since reallocation of video objects to data servers is a lengthy and expensive process, such reallocation should be performed in advance, to satisfy expected future subscriber requests. Hence a time-aware predictive placement policy is used by the broker to determine when, where, and how many replicas of each video object should be placed in a video server so as to maximize the number of requested serviced by it. Furthermore, the TAPP takes into account the line??? Of server availability while making placement decision.

This strategy can be implemented by two approaches:

• Bandwidth – biased: without considering the servers’ storage, choose servers for new replicas only based on the current load and service time availability.

• Storage – biased: starts considering the available disk storage of the servers besides the current load; if there is no enough disk storage, then choose some of the servers that have replicas of less-popular videos, and try to make new replicas for popular videos.

The implementation algorithms will be elaborated in the next section.

4. The Time-aware Placement Algorithm

In this section, we present a generalized time-aware predictive placement algorithm (TAPP). In fact, before running the TAPP algorithm (illustrated in Fig 4) at the beginning of every period of time, during the previous time period, the system has to record the total rejections of each video and total number of requests for each video, based on which, TAPP can execute the following 4 main steps: popularity Estimation, Candidate server selection, Pseudo Replication, and Pseudo Dereplication.

Popularity Estimation

In this step is to decide which video objects need more replicas based on the rejection-popularity (RP) factor. If “total rejections of video i within last period of time” is # rejection (i), “total rejections for whole videos within last period of time” is # rejections, and “total requests of video i within last period of time” is requests (i), then the RP(i) is defined as:

[pic]

Then, the larger the RP of a video, the more problematic it is, which implies that it is necessary to add replicas of this video object.

By studying the request model, we assume if [pic], then video i will be added in the list of popular videos with decreasing order of the RP. If [pic], then video j will be inserted in the list of less-popular videos in the first phase by the sequence of increasing order of the value of RP.

Candidate server selection

In this step, storage – biased approach will choose all the servers that have storage resource available as candidate servers. On the other hand, bandwidth – biased approach is to choose all the servers that still have network bandwidth available and available service time, but without caring if they have extra disk storage. According to the load factor to determine if it’s heavily loaded. But, how many to choose? Or how to delete the invalid servers.

Pseudo Replication: given the set of servers of disk_available_servers (in Fig 3) and popular videos got from the step of Popularity Estimation, use the pseudo allocation algorithm to get a set of combinations as (server j, video i), so as to create one replica i on j.

In order to derive a mapping of video objects to data servers, the broker constructs a placement cost matrix that represents the relative costs of servicing subscriber requests from each of the data servers. Columns in the placement matrix represent data servers and rows represent video objects as Table 1. Each entry in the matrix, [pic]represents the maximum revenue that can accrue from allocating Vi to S j.

If video i is in server j, then the entry of i row and j column is set as null, so that this combination will never be in consideration of this replication matrix.

1/ LF(Ri, Sj) represents the average number of requests of Ri that data server Sj can provide for each time unit in one placement period. Ni is the number of rejections in the last period; As this is for an intermittently available system, tj is used to represent the value of total service time for server j. so that (1/LF(Ri,Sj) * tj represents the average total number of requests for video i that a sever j can accept.

After calculating the entries in the matrix of each row and column, first to choose the maximum value of each column and set the values in the last row accordingly, then to choose the maximum value of the last row, so that a set of replication combination with one video and one server, (server j, video i) is selected. Then, shrink the matrix by deleting either a column (if Ni >= 1/LF(Ri,Sj)*tj) and decreasing the value of Ni by 1/LF(Ri,Sj)*tj; or a row (if Ni ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download