Advanced Reservation Techniques For Resource Allocation Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract- grid computing enables the provision of distributively owned resources to the various requesting applications by extending its different service to various applications. The most important thing to be considered here is the resource management and scheduling, satisfying all the quality of service constraints (qos). The qos issues that the task which has been submitted must be dispatched by the grid in a timely fashion. Since grid is a highly dynamic system it is a requisite to perform advance reservation of resources that are required by the various tasks. In this paper we survey a few of the advance reservation algorithms proposed and implemented. The results of the implementation of algorithms are studied from the simulation graphs.

Keywords- concurrent execution, resource reservation, co-reservation, Resource Scheduling, meta-request,


Grid computing has came forth as the next generation parallel and distributed computing that combines the dispersed heterogeneous resources for solving a range of large scale concurrent application. Initially immediate allocation of resources were done but it suffered few drawbacks. Generally we see that in most of the Grid systems the requests for the resources are placed in a queue, when there is unavailability of resources. Thus the availability of resources is very uncertain. Applications have to contend for the resources while dealing with the middleware complexities and resources have to distribute their capacity among competing applications. This becomes a major difficulty, therefore it is essential to support Advance reservation of resources in Grid system.

Advance reservation (AR) is considered as a process which requests resources that are needed by a particular task for a specific interval of time in future. The resources can not only specifically be CPU resources but also memory, disk space, storage and network bandwidth. AR resolves the resource contention and allows concurrent access of resources by the users for the execution of application successively. This also ensures the availability of resources at the needed time for the users or application.

There are various proposed existing algorithms to optimize the performance of the Grid system. The algorithm which supports co- reservation is also considered in this paper. Co- reservation permits the users to request for multiple resources concurrently at the same time. Nevertheless it does not permit different users to 'space-share' the resources during the same time intervals.

Few of the available tools for the scheduling simulations are namely Bricks [4], SimGrid [5], and OptorSim [6]. But these tools do not support advance reservation technique. Thus GridSim [7] is used to support this Advance reservation mechanism.

GridSim [7] is basically a Java-based simulation package that provides characterstics for application composition, information services for resource allocation which also has the capacity to model heterogeneous computational resources of variable performance.


States of advance reservation

The various states in the advance reservation process may be defined as follows:

Requested: Is the beginning state of reservation when a request has been made for reservation is first made.

Rejected: The reservation has not been achieved successfully due to full slots and the existing one expires.

Accepted: The reservation request has been achieved successfully.

Committed: The user confirms the resource before expiry time and is honoured by the resource

Change requested: Before the starting of the execution the user may want to change the requirements for the reservation. Once this is successful the it is committed for the new requirements else the old values are considered.

Active: Reservation now starts its task and the resource executes the reservation.

Cancelled: If the user is no longer in need of the reservation it is cancels the request.

Completed: This marks the reach of end time of the reservation.

Terminated: The user may terminate a reservation before its end time has reached.

Scheduling Systems for Advance reservation

GridSim primarily focuses on the simulating Grids A scheduler with resource always aims at reserving the CPUsGridSim utilizes the FCFS approach ARSimpleSpaceShared object for the reservation based system. The scheduler has a reservation list which contains all the accepted reservation in a sorted manner. The scheduler finds the empty slots based on the start time. It stores the index of all the reservation and calculates.

Simulation results

This experiment simulates the scenario showing how far the GridSim has ability to handle the AR functionalities and examines the effect of AR from the point of users and resources.

Advance reservation analysis

The metric applied in the analysis are namely Mean waiting time and Mean Offset time from the request reservation time. Mean waiting time is defined as the mean time that the job is required to wait prior to acquiring of the resources.

Fig. 1 is an example of the results that were produced which shows the Mean waiting time. Fig. 2 shows that the offset becomes higher when there are more number of reservations.

The analysis done in [2] concludes that the Mean Waiting time of the queued jobs raises as the percentage of reservation of resources raises. And the mean offset time also raises with the increase in the percentage of reservation but less than the jobs without the reservation.

The reservation job can classified as two types namely Restartable and Non-restartable jobs. Restartable jobs are jobs that can be suspended if it exceeds the amount of allocated time and can resume its execution when it finds that the CPU is free. On the other hand Non-Restartable jobs cannot be suspended instead they execute until they complete the execution or occasionally may be pre-empted by a scheduler and return the jobs with the current status to the user with or without finishing the jobs. The graphs have been drawn for both Restartable jobs as well as the non-Restartable jobs so that it would be feasible to compare the results.

The resource utilization does not change for the restartable jobs but decreases for the non-restartable jobs. The number of Jobs that are rejected becomes higher when the rate of reservation increases.

The [2] concludes that the Advance reservation allows concurrent access for the applications to be executed in parallel using the GridSim tool. The design and implementation in GridSim was also studied.

Time (min)

Jobs using AR

Fig. 1 Mean waiting time

% of jobs using AR



Fig. 2 Mean Offset Time


The [3] introduces an algorithm for Scheduling advance reservation of resources. The [9] implements an Advance Reservation Server (ARS) which works along with the Dynamic Soft Real Time (DSRT) [10]. The immediate reservations are posed as advance reservation along with the current time as the start time for a specific duration of time. The [3] compares its proposed algorithm with the Resource Broker algorithm which is proposed in [11] incorporates along with the ARS presented in [9].

The [3] demonstrate an algorithm Reservation Scheduling with priority and Benefit function (RSPB) [3] which schedules relatively with regard to the priorities of different reservation requests. In RSPB [3] each reservation request has a related benefit function which evaluates the 'profit' for the client. This RSPB [3] is able to be implemented on the top of the CPU Scheduler.

The [3] defines a centralised resource reservation scheduler where all the reservations are carried out by the centralised unit. When the requests arrive arbitrarily in the Poisson manner the scheduler needs to make decision subsequently after the arrival of a request or a batch of requests instead the scheduler must not wait till all the request arrives.

The [3] makes certain assumptions that once the request is granted reservation a declaration is signed between the application and the system and the scheduler may not analyse the request once more except when QoS constraints are violated.

Dynamically arriving requests are collected for a particular interval of time interval to form a meta-request. The [3] also defines Pseudo code for dynamic reservation scheduler and for priority and benefit function based scheduling algorithm for indivisible reservations.

Simulation results

The simulation results of RSPB [3] and the RB (Resource Broker) [11] were carried out and graphs were depicted in [3].

And the results of both the algorithms (RSPB and RB) were compared. The event simulator was written with the help of PARSEC language [12]. The results of both the algorithms were projected to the same graph to compare the variations among them. The five different graphs are drawn which displays the number of rejections versus request, number of rejection versus machines, number of rejection versus requested duration, average reserved CPU versus requested CPU and sum of rejected priorities versus rejections respectively. It has been studied from the first three graph that the number of rejections for RSPB is substantially lower than that of RB.

Fig. 3 is a sample graph which shows the variation of the number of rejections with respect to the number of requests. In the same manner all the graphs are drawn. The five different graphs are drawn which displays the number of rejections versus request, number of rejection versus machines, number of rejection versus requested duration, average reserved CPU versus requested CPU and sum of rejected priorities versus Thus the observation states that various algorithms should be employed depending upon the policy of optimization.

No. of rejections

Number of request

Fig. 3 Number of rejections vs. request


Co- reservation of resources allows access to multiple resources at the same time. [1] defines three different algorithms for scheduling co-reservations on heterogeneous resources. All these algorithms operate on pseudo-online mode. This approach may also be extended to the other resource such as storage and networks. The previous approach of scheduling is extended to reserving multiple resources. The [1] presents three algorithms namely Co- reservation scheduler with priority and benefit function (Co- RSPB) which takes into account the relative priorities of the request where it has a benefit function assorted to it which measures the 'profit' accumulated by the client by obtaining the resource at the requested level. The Co- reservation scheduler with best fit Scheme (Co-RSBF), The Co- reservation scheduler with best fit and refining (Co-RSBFR).

As we saw in the earlier case once the meta- request is collected by the scheduler, it is scheduled by a chosen heuristic. If any resource set can satisfy the request then the request is called as floating request else fixed. Co-RSPB schedules the floating request. The meta request which consists of set of requests are sorted according to their priority and regarded in the non-ascending order by priority. The requests are found to have sub-request since it is a co- reservation request.

The Co- reservation scheduler with best fit Scheme (Co-RSBF) [1] algorithm allows the requests to be sorted by the sum of requirements of the sub-request.

The Co- reservation scheduler with best fit and refining (Co-RSBFR) [1] algorithm applies the Co-RSBF and raises the benefit to the resource by admitting the reservation request.

Simulation results

The simulations were carried out for all the three different algorithms. The results shows that Co-RSBF performs worse based on the system benefit measure since the scheduling may done without considering the priorities of the requests and so has failed to increase the system benefit. It has also been examined that the Co-RSBFR performs poor than the other two approaches on both the metrics. The refinement process is found to raise the number of rejection and bring down the system benefit. The numbers of rejections are relatively higher than the other two approaches which is because it tries to refine the reservation by rendering more benefit for requests that have already been reserved.

Fig. 4 shows a sample simulation outcome of the analysis done to examine the performance of all the algorithms as how the number of rejection varies with respect to the increase in the number of request.

No. Of Rejection

Number of requests

Figure 4. Variation of the number of rejections with number of requests


This paper is a survey of the papers which focus on algorithms for scheduling advance reservation of resources. The Quality of service constraints are applied to these algorithms. The various algorithms for scheduling the advance reservation requests were examined and studied. The simulation was also performed and the graphs show the observation of the studies though simulation that has been performed. It can be concluded from this paper that the various algorithms may be employed based on the policy or objective of optimization required by the system. Since the requirement of each system widely varies we cannot reason out that only a particular algorithm is feasible. All the algorithms are beneficial and important in some way.