# 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 a software product 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 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.

The application of the software is to 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.

#### User interfaces
There will be two user types, each with its own interface 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]

### 1.3.2 Product functions
The main purpose of the Libra scheduler is to maximize user utility by scheduling jobs based on user-specified budget and deadline constraints.

The scheduler will 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.

A market-based economic model (bid-based proportional resource-sharing) will be used for the pricing and allocation of resources. The proportional stride-scheduling algorithm will be used to ensure the actual resource allocation reflects the job's share.

### 1.3.3 User characteristics
There are two classes of users:
*   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 project is constrained by the provision of hardware resources. At present, a network of four Pentium-III workstations serves as the cluster.
*   A simulating tool needs to be used for testing, which may have to be specially designed.
*   The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
*   Exhaustive searches of the entire set of combinations of jobs will not be done; heuristics will be developed for scheduling.
*   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.

## 1.4 Definitions
*   **Cluster/Cluster Computing**: Connecting two or more computers together to take advantage of combined computational power and resources, working as an integrated collection of resources.
*   **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 (e.g., deadline, budget) rather than a system-centric approach (e.g., submission time).
*   **Linux**: An open source operating system.
*   **Grid Computing**: An infrastructure that couples resources across the Internet and presents them as a unified integrated single resource.
*   **Bid-based Proportional Resource-Sharing Model**: An economic model that allocates resources between competing users based on their bids. The amount of resource allocated is proportional to the values of their bids.
*   **Stride Scheduling**: A deterministic scheduling algorithm to enforce resource allocations proportional to a user’s priority or share (represented by tickets). A stride is inversely proportional to the number of tickets.
*   **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.
*   **Embarrassingly Parallel Jobs**: Parallel jobs comprised of independent parts that can be split up and performed on separate nodes with minimal inter-job communication.
*   **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 have uniform characteristics 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
*   **Submit Job**: Facilitated by the SGE interface, this feature allows a verified user to submit a job if the cluster is open for submissions. The SGE interface will be adapted to include additional parameters like budget and deadline.
*   **View Job Status**: Allows a user or administrator to view details about submitted jobs and their execution progress after authentication.
*   **Delete/Change Job**: Allows a user or administrator to cancel a job or, under specific circumstances, change non-critical job parameters (e.g., output directory). This action will trigger a revision of scheduling decisions.
*   **Initialize Job**: The Libra scheduler retrieves job details submitted by the user (Job ID, type, execution time, budget, deadline, etc.) and sets them in variables that represent the state of the cluster.
*   **Accept/Reject Job**: The scheduler determines if a job can be completed by its deadline given its budget, execution time, and the current cluster load. It outputs a boolean acceptance value and may suggest an alternative deadline or cost.
*   **Calculate Scheduling Information**: Once a job is accepted, Libra uses the Stride Scheduling Algorithm to allocate "tickets" based on the job's budget and deadline relative to other jobs. It calculates the job's stride and pass values for scheduling.
*   **Determine Execution Host**: Libra selects the least loaded host to ensure load balancing and then selects the appropriate queue on that host based on job type, budget, etc.
*   **Dispatch Job**: The scheduler inserts the job into the chosen queue on the determined execution host when it is time for the job to compete for resources.
*   **Update Cluster Status**: When a job is scheduled or completes, Libra updates the cluster status by reserving or releasing resources on the node and sending information about the load change to the central information store.
*   **Execute Job**: This ongoing process time-slices between all running jobs based on the stride-scheduling algorithm. It selects the job with the minimum "pass" value, allots it a quantum of execution time, and advances that job's pass by its stride.

## 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.
*   The entire Libra project is open source, and no component of it will be purchased.
*   Libra will be released under a GPL license.
*   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.

## 3.7 Software system attributes
*   **Reliability**: 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 and as required by the GNU General Purpose License.
*   **Portability**: [N/A]

## 3.8 Supporting information
The following supporting information is referenced in appendices of the original document:
*   Appendix A – Background Research
*   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.
*   **SGE**: Sun Grid Engine cluster management system.