# 1 Introduction

## 1.1 Purpose
This SRS describes the requirements and specifications of Libra, an Economy-Driven Cluster Scheduler. It explains the functional features of the scheduler, along with interface details, design constraints and related considerations such as performance characteristics. The SRS is intended for users and owners of high-performance clusters, cluster management software, job schedulers and grid resources.

## 1.2 Scope
The Libra Scheduler is intended to work as an add-on to the queuing, scheduling and resource managing module of the open source Sun Grid Engine (SGE) cluster management system. The software product is named Libra Scheduler.

The scheduler will offer market-based economy driven service for managing batch jobs on clusters by scheduling CPU time according to user utility rather than system performance considerations. The main objective of Libra is to provide Quality of Service (QoS) computational economy in cluster computing.

As part of the project, the Libra Scheduler will only manage sequential and embarrassingly parallel batch jobs to be run on a homogenous Linux cluster. Its functionality can be adapted to schedule resources other than CPU time, even on a heterogeneous cluster. To provide QoS to users, there will be no mechanism for users to interact with each other and bargain on the use of resources.

## 1.3 Product overview

### 1.3.1 Product perspective
Libra forms part of a larger system comprising the Sun Grid Engine (SGE) cluster management system that runs on a Linux-based cluster. SGE is responsible for receiving the jobs submitted by the user and delegating them to Libra for scheduling and placing on appropriate workstations or execution hosts. Libra communicates its decision regarding workstation allocation to the resource manager, which then dispatches the job to the chosen workstation. Once assignment to a workstation has occurred, Libra is responsible for implementing the scheduling policy on the jobs executing at the workstations. No modifications to the Linux kernel are required.

#### System interfaces
Libra interfaces with the Sun Grid Engine (SGE) cluster management system. SGE receives jobs and delegates them to Libra for scheduling. Libra communicates its scheduling decisions back to SGE's resource manager for dispatching.

#### User interfaces
There will be two user types, each with its own interface, accessible through the Linux command prompt or the SGE interface.

The cluster user interface will provide commands to:
*   submit jobs with the associated deadline, cost, and execution time,
*   query the cluster to establish the current cost per unit time for submitting new jobs,
*   monitor the status of submitted jobs,
*   cancel jobs submitted by him,
*   check his credit balance,
*   check his usage history.

The cluster administrator interface will provide all user commands, plus additional commands to:
*   check the status of each node of the cluster,
*   check the usage pattern history of the cluster,
*   check the status of all submitted jobs,
*   check the load on each node of the cluster,
*   alter the cost structure of the cluster,
*   alter the scheduling policy of the cluster,
*   cancel, suspend, and resume any job.

#### Hardware interfaces
All hardware interfaces of Libra will be those of the Sun Grid Engine on top of which it will be running. Hence, it will incorporate SGE’s interfaces for:
*   CPU usage,
*   Memory usage,
*   Swap file creation,
*   Network communication.

#### Software interfaces
Libra will directly interface with the modified Sun Grid Engine cluster management system, version 5.3. SGE in turn will be interfacing with the operating system and any other software components it requires. For the execution of embarrassingly parallel jobs, the PVM (Parallel Virtual Machine) and MPI (Message Passing Interface) libraries will be used by the cluster.

#### Communications interfaces
Libra will utilize the communications architecture of Sun Grid Engine itself, and will not have any unique communications interfaces above of SGE.

#### Memory constraints
[N/A]

#### Operations
[N/A]

#### Site adaptation requirements
[N/A]

#### Interfaces with services
[N/A]

### 1.3.2 Product functions
The main purpose of the Libra scheduler is to maximize user utility by scheduling jobs based on user-provided budget and deadline constraints, rather than maximizing system performance.

With support from the Sun Grid Engine, the Libra scheduler should embody the following features and functions:
*   Enforce resource allocations according to user-centric priorities (budget and deadline).
*   Be dynamic, allowing for the reallocation of resources based on new, high-priority jobs.
*   Be scalable, so that its performance does not degrade with the addition of nodes and jobs.
*   Be configurable, allowing for various scheduling policies.
*   Be separable from the cluster management system.
*   Provide administrative security.
*   Provide at least a basic level of job accounting.
*   Ideally provide a GUI for users and administrators (though this is not part of the initial scope).

### 1.3.3 User characteristics
There are two classes of users for the Libra Scheduler:
*   The user who wishes to submit jobs for the cluster. This user needs to know the exact nature of the submitted job, such as the execution time and resources required, and must possess the technical know-how to use the job submission interface.
*   The administrator who oversees scheduling and cluster usage. This user must be an advanced cluster operator, fully qualified in using Linux, SGE, and the Libra Scheduler.

### 1.3.4 Limitations
*   The scheduler will only manage sequential and embarrassingly parallel batch jobs.
*   The scheduler is designed for a homogenous Linux cluster.
*   The current hardware for implementation and testing is a network of four Pentium-III workstations.
*   Detailed requirements for the economic front-end (costing and pricing policy) will be specified in a later version.
*   Initially, only a command-line interface will be provided; a GUI might be added later.
*   The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
*   Libra will be released under a GPL license and will be open-source.

## 1.4 Definitions
*   **Cluster/Cluster Computing:** Connecting two or more computers together to take advantage of combined computational power and resources. A cluster works as an integrated collection of resources that can provide a single system image spanning all its nodes.
*   **QoS (Quality of Service):** Meeting what users actually want, thus maximizing their utility.
*   **Computational Economy:** The inclusion of user-specified QoS parameters with jobs so that resource management is based on a user-centric approach rather than on a system-centric approach.
*   **Linux:** An open source operating system.
*   **Grid Computing:** An infrastructure that couples resources such as computers, software, and devices across the Internet and presents them as a unified integrated single resource.
*   **Bid-based Proportional Resource-Sharing Model:** An economic model that specifies one way of allocating resources between competing users based on their criteria, such as deadline and budget. The amount of resource allocated to users is proportional to the values of their bids.
*   **Stride Scheduling:** A scheduling algorithm to enforce resource allocations proportional to a user’s priority or share. A stride is inversely proportional to the number of tickets allocated to a job.
*   **Process Migration:** The process of moving a job from one computer system to another without restarting the job from the beginning.
*   **Sequential Jobs:** Jobs that must be run on a single node and cannot be split into separate jobs.
*   **Embarrassingly Parallel Jobs:** Parallel jobs that are comprised of independent parts that can be split up and performed on separate nodes as if they are sequential jobs, with minimal inter-job communication necessary.
*   **Job accounting:** A method of quantifying the system resources used by a job.
*   **Open-source software:** Software for which the code is freely available for use and research.
*   **Homogenous cluster:** A cluster in which the nodes or workstations have uniform characteristics such as the same memory size and hard disk space, and run the same operating system.

# 2 References
*   [1] R. Buyya, D. Abramson, and J. Giddy, Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid, HPC ASIA’2000, China, IEEE CS Press, USA, 2000.
*   [2] R. Buyya, D. Abramson, J. Giddy, An Economy Driven Resource Management Architecture for Global Computational Power Grids, The 2000 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2000), Las Vegas, USA, June 26-29, 2000.
*   [3] R. Buyya, D. Abramson, and J. Giddy , An Economy Grid Architecture for Service-Oriented Grid Computing, 10th IEEE International Heterogeneous Computing Workshop (HCW 2001), with IPDPS 2001, SF, California, USA, April 2001.
*   [4] Rajkumar Buyya, Heinz Stockinger‡, Jonathan Giddy, and David Abramson, Economic Models for Management of Resources in Peer -to-Peer and Grid Computing, Monash University.
*   [5] B.N. Chun and D.E. Culler, Market-based proportional resource sharing for clusters. Submitted for publication, September 1999.

# 3 Requirements

## 3.1 Functions
### 3.1.1 Submit Job
This function allows an end-user or administrator to submit a job via the SGE interface, which will be adapted to include additional QoS parameters (budget, deadline).
*   **Inputs:** User Information, Job Information, Cluster Information.
*   **Processing:** The system verifies if the cluster is open for submissions and if the user is valid.
*   **Outputs:** A boolean indicating if the cluster is accepting submissions; a boolean indicating if the user is verified.

### 3.1.2 View Job Status
This function allows a user or administrator to view details about submitted jobs and their execution progress.
*   **Inputs:** User ID and Password.
*   **Processing:** The system displays available options and information about the user's submitted jobs.
*   **Outputs:** A user view of available options and job status information.

### 3.1.3 Delete/Change Job
This function allows a user or administrator to cancel a job or, under specific circumstances, change a job parameter (e.g., output directory, delayed deadline).
*   **Inputs:** User ID and Password.
*   **Processing:** The system removes the job from the queue and updates the cluster status, revising scheduling decisions for other jobs.
*   **Outputs:** Updated cluster information (CPU load, node status, queue length, etc.).

### 3.1.4 Initialize Job
This function prepares the scheduler to handle a job once it has been accepted by SGE.
*   **Inputs:** Job information submitted by the user and the job ID assigned by SGE.
*   **Processing:** The scheduler retrieves and parses the job details and sets them in variables representing the cluster state.
*   **Outputs:** Set variables representing the job details: Job ID, Job type, Execution time, Location of executable, System Type, Budget, Deadline.

### 3.1.5 Accept/Reject Job
This function determines if a user's job can be satisfied given its budget and deadline.
*   **Inputs:** Job details, Cluster information (CPU load, node status, etc.).
*   **Processing:** The scheduler calculates a priority for the job based on its parameters and determines if it can be finished by the required deadline given the current cluster state.
*   **Outputs:** A boolean value specifying acceptance or rejection. If rejected, a suggested deadline or cost may be provided as a precondition for acceptance.

### 3.1.6 Calculate Scheduling Information
This function decides how a job will be scheduled based on its budget and deadline, using the Stride Scheduling Algorithm.
*   **Inputs:** Job details.
*   **Processing:** The scheduler allocates "tickets" to a job based on its budget and deadline relative to other jobs. It then calculates the job's stride and pass values.
*   **Outputs:** Scheduling information for the job: tickets, stride, and pass.

### 3.1.7 Determine Execution Host
This function decides on which node and in which queue a job will be placed for execution.
*   **Inputs:** Job details, Cluster Information (CPU Load, Node Status, etc.).
*   **Processing:** Libra identifies the least loaded host to ensure load balancing and then selects the appropriate queue based on job type, budget, etc.
*   **Outputs:** The chosen execution host and queue for the job.

### 3.1.8 Dispatch Job
This function inserts the job into the queue on the chosen execution host. The dispatcher decides when to actually send the job for execution.
*   **Inputs:** The chosen execution host and queue.
*   **Processing:** The scheduler sends the job to the appropriate queue where it will compete for resources.
*   **Outputs:** The scheduled job placed in its appropriate host and queue.

### 3.1.9 Update Cluster Status
This function updates the cluster status whenever a job is scheduled for execution or when a job finishes and is removed.
*   **Inputs:** Job details, Chosen execution host and queue.
*   **Processing:** Libra reserves the required resources on the node and updates the execution host's queue status, sending this information to the central information store.
*   **Outputs:** None. This is a trigger action.

### 3.1.10 Execute Job
This function manages the time-slicing between all currently executing jobs based on the stride-scheduling algorithm.
*   **Inputs:** Scheduled job details, Scheduling information (tickets, stride, pass).
*   **Processing:** The scheduler repeatedly selects the job with the minimum pass value, allots it a quantum of execution time, and advances that job's pass by its stride.
*   **Outputs:** Updated Cluster Information (CPU Load, Node Status, etc.).

## 3.2 Performance requirements
*   **Response time:** The maximum response time for the submission of a job will be 1 minute.
*   **Capacity:** The maximum number of jobs schedulable is limited only by the capacity of the nodes to fulfill the jobs’ deadlines; there is no upper limit inherent in the Libra scheduler.
*   **Deadline sensitivity:** Assuming submitted statistics for jobs are accurate, the Libra scheduler will ensure that all jobs are completed with a 10% error allowance.
*   **Cost sensitivity:** Under all circumstances, the maximum cost payable as submitted by the user will be the maximum cost charged to the user.

## 3.3 Usability requirements
All documentation will be made in accordance with requirements pertaining to open source software under the GNU General Purpose License. Additionally, on-line user documentation will be in the form of man pages accessible through Linux.

## 3.5 Logical database requirements
[N/A]

## 3.6 Design constraints
*   The Libra scheduler will be a sub-component of the Sun Grid Engine (SGE).
*   All coding will be done in standard C.
*   Exhaustive searches of the entire set of combinations of jobs will not be done. Heuristics will be developed for this scheduling problem.
*   The system will be developed and tested on a network of four Pentium-III workstations with 128 Mb RAM, running Linux.
*   The user and administrator interface will initially be a command line interface or the interface of the Sun Grid Engine.

## 3.7 Software system attributes
### Reliability
*   The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
*   There will be a maximum of 1 bug/KLOC.

### Availability
*   In case of system outage, the cluster will be down while the Linux operating system boots up. This will take less than five minutes.

### Security
*   The Libra scheduler will ensure the privacy of user job status and ensure full control over job execution, so that alteration of scheduling criteria or actual resource allocation is not possible without administrator authority.

### Maintainability
*   All code will be written as specified by the Hungarian Naming Convention.
*   All code will be written as required by the GNU General Purpose License.

### Portability
*   The software will be written in standard C.
*   The software is designed to run on a homogenous Linux cluster.

## 3.8 Supporting information
The following supporting information is referenced in appendices of the original document:
*   Appendix A: Background Research on Cluster Computing, Market-based Economic Models, Cluster Scheduling, and Cluster Management Software.
*   Appendix B: Data Flow Diagrams.
*   Appendix C: Data Dictionary.

# 4 Verification

## 4.1 Functions
[N/A]

## 4.2 Performance requirements
[N/A]

## 4.3 Usability requirements
[N/A]

## 4.5 Logical database requirements
[N/A]

## 4.6 Design constraints
[N/A]

## 4.7 Software system attributes
[N/A]

# 5 Appendices

## 5.1 Assumptions and dependencies
*   The workability of the Sun Grid Engine cluster management system modules such as those dealing with process migration with the scheduling policies provided by the Libra Scheduler is assumed.
*   A basic module of job accounting and payment considerations will be provided, as they are not the focus of the scheduler.
*   Users are assumed to have a fair estimate of job execution times, so that the decision to accept or reject a job is facilitated.

## 5.2 Acronyms and abbreviations
*   **CPU:** Central processing unit of a computer.
*   **GUI:** Graphical user interface.
*   **QoS:** Quality of Service.
*   **SGE:** Sun Grid Engine cluster management system.