# 1 Introduction
[NULL]

## 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 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. Hence, the main objective of Libra is to provide Quality of Service (QoS) computational economy in cluster computing.

As part of this 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, but this is not within the current scope. 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
[NULL]

### 1.3.1 Product perspective
Libra forms part of a larger system comprising the Sun Grid Engine cluster management system that runs on a Linux-based cluster. SGE is responsible for receiving 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
The Libra Scheduler directly interfaces with the Sun Grid Engine (SGE) cluster management system. SGE is responsible for job submission, delegation, and dispatching jobs to chosen workstations based on Libra's decisions.

#### User interfaces
There will be two user types: the cluster user and the cluster administrator.
The minimal requirements are that both user types would be able to interact with the system through the Linux command prompt or through the interface provided by the Sun Grid Engine cluster management system. A Graphical User Interface (GUI) might be added once the basic functionality is implemented.

Cluster User Interface commands:
*   Submit jobs with 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 the user.
*   Check credit balance.
*   Check usage history.

Cluster Administrator Interface commands (in addition to user commands):
*   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 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 optimizing resource utilization within user-imposed constraints. User satisfaction is the primary concern, as opposed to maximizing CPU utilization.

The scheduler will allocate jobs based on user-submitted job parameters, including:
*   Location of the executable and input data sets
*   Where standard output is to be placed
*   System type
*   Maximum length of run (execution time)
*   Whether the job is sequential or embarrassingly parallel

The two job parameters most relevant to scheduling decisions are:
*   Budget allocated by the user to the process
*   Deadline

With support from the Sun Grid Engine, the Libra scheduler will embody the following features and functions:
*   Enforce resource allocations according to user-centric priorities.
*   Be dynamic, allowing for dynamic reallocation of resources based on user-centric priorities (e.g., emergency jobs with high bids). The scheduler should be able to change resource limits, priorities, privileges, and execution order of submitted jobs.
*   Be scalable, meaning its performance should not degrade with the addition of nodes and jobs to the cluster.
*   Be configurable, allowing for various scheduling policies that can be modified to incorporate QoS parameters.
*   Be separable from the cluster management system.
*   Provide administrative security.
*   Provide at least a basic level of job accounting to aid in scheduling policies.
*   Ideally provide a GUI for all components, such as for users to submit jobs and for administrators to oversee scheduling.

A market-based economic model (bid-based proportional resource-sharing model) will be developed for the Libra scheduler, responsible for pricing and allocating resources according to user constraints. The proportional stride-scheduling algorithm will be used to ensure actual resource allocation reflects the overall job share.

### 1.3.3 User characteristics
There are two classes of users for the Libra Scheduler:
*   **Cluster User:** Wishes to submit jobs for the cluster. Needs to know the exact nature of the submitted job (e.g., execution time, resources required) and must possess the technical know-how to use the interface for submitting jobs.
*   **Administrator:** Oversees scheduling and cluster usage. Must be an advanced cluster operator, fully qualified in using Linux, SGE, and the Libra Scheduler.

### 1.3.4 Limitations
*   **Project Constraints:** The current project is constrained by hardware resources for implementation and testing. The current test cluster consists of four Pentium-III workstations with 128 Mb RAM, running SGE on Linux. A larger number of dedicated workstations would be beneficial for better performance analysis. A simulating tool for testing may need to be specially designed if a generic one is not readily and freely available.
*   **Functional Limitations:** The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
*   **Licensing and Copyright:** Libra will be released under a GPL license and will be open-source. Sun Grid Engine (SGE) is a copyright trademark of Sun Microsystems, Inc. Libra Scheduler is a copyright trademark of Mr. Rajkumar Buyya, Monash University. MPI is a copyright of the University of Chicago and Mississippi State University. PVM is a copyright of the University of Tennessee, Oak Ridge National Laboratory, and Emory University.
*   **Parent Component:** The Libra scheduler will be a sub-component of SGE.
*   **Scheduling Constraints:** Exhaustive searches of the entire set of combinations of jobs will not be done. Heuristics will be developed for this scheduling problem.
*   **Deferred Requirements:** Detailed requirements for the economic front-end (exact costing and pricing policy) will be specified in a later version. The pricing mechanism will not affect the scheduling policies, as they assume a given cost and budget and schedule resources accordingly.
*   **Interface Limitations:** At present, only a command line Linux interface or the interface of the Sun Grid Engine cluster management system will be used as the user and administrator interface. A GUI might be added once the basic functionality is implemented.

## 1.4 Definitions
*   **Bid-based Proportional Resource-Sharing Model:** An economic model for allocating cluster resources between competing users based on criteria such as deadline and budget. Resources are allocated proportionally to user bids (tokens/credits), whose value depends on resource demand and cost.
*   **Cluster/Cluster Computing:** Connecting two or more computers to combine computational power and resources, working as an integrated collection to provide a single system image. Used for high-performance applications.
*   **Computational Economy:** Inclusion of user-specified QoS parameters with jobs for user-centric resource management, where user constraints (deadline, budget) are prioritized over system policies.
*   **CPU:** Central processing unit of a computer.
*   **Embarrassingly Parallel Jobs:** Parallel jobs comprised of independent parts that can be split and performed on separate nodes with minimal inter-job communication.
*   **Grid Computing:** An infrastructure coupling resources (computers, software, devices) across the Internet, presenting them as a unified, integrated single resource.
*   **GUI:** Graphical user interface.
*   **Homogenous cluster:** A cluster in which nodes have uniform characteristics (e.g., same memory, hard disk space, operating system).
*   **Job accounting:** A method of quantifying the system resources used by a job.
*   **Linux:** An open-source operating system.
*   **Open-source software:** Software for which the code is freely available for use and research.
*   **Process Migration:** Moving a job from one computer system to another without restarting it.
*   **QoS (Quality of Service):** Meeting what users actually want, thus maximizing their utility.
*   **SGE:** Sun Grid Engine cluster management system.
*   **Sequential Jobs:** Jobs that must be run on a single node and cannot be split.
*   **Stride Scheduling:** A scheduling algorithm to enforce resource allocations proportional to a user’s priority or share, using a pool of tickets and strides inversely proportional to tickets.

# 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
[NULL]

## 3.1 Functions
The functional requirements for the Libra scheduler are organized by the processes and features encapsulated within it.

### 3.1.1 Submit Job
This feature is facilitated by the SGE interface (potentially adapted for additional parameters) or a command-line interface.
*   **Inputs:** User Information (name, authentication ID), Job Information (details for pending jobs, cluster capacity), Cluster Information (type, scheduling mechanism, current load, submission criteria).
*   **Processing:** The cluster determines if it is open for submissions and if the user is valid. This is distinct from accepting/rejecting a specific job based on its parameters.
*   **Outputs:** Boolean indicating if submission is accepted, Boolean indicating user verification status.

### 3.1.2 View Job Status
This feature allows users or administrators to view details and progress of submitted jobs.
*   **Inputs:** User ID and Password for authentication.
*   **Processing:** Show available options and job execution progress. Process selected options to view different aspects of job information.
*   **Outputs:** User view of available options and job status.

### 3.1.3 Delete/Change Job
This feature allows users or administrators to cancel a job or, under specific circumstances, change certain job parameters (e.g., output directory, delayed deadline). Critical parameters like deadline and cost are not normally changeable.
*   **Inputs:** User ID and Password for authentication.
*   **Processing:** Remove job from the queue and update cluster status. Revise scheduling decisions for pending jobs and new submissions.
*   **Outputs:** Updated cluster information and scheduling decisions (CPU load, node status, queue length, quanta allocated, revised expected finishing deadline). These outputs are facilitated by SGE.

### 3.1.4 Initialize Job
This function prepares the scheduler for a job once it has been accepted by SGE.
*   **Inputs:** User-submitted job information and the job ID assigned by SGE.
*   **Processing:** Retrieve job details and set them in variables representing cluster and queue states. Parsed parameters are passed to the scheduling module.
*   **Outputs:** Set variables representing job information: Job ID, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.

### 3.1.5 Accept/Reject Job
This function determines if a job can be satisfied given its budget and deadline.
*   **Inputs:** Job details (Job ID, type, execution time, location, system type, budget, deadline), Cluster information (CPU load, node status, remaining time of pending jobs).
*   **Processing:** Calculate job priority based on budget and deadline. Determine if the job can finish by its deadline, considering its execution time and other pending jobs.
*   **Outputs:** Boolean indicating job acceptance or rejection. A suggested deadline or cost may be given as a precondition for acceptance.

### 3.1.6 Calculate Scheduling Information
This feature decides how a job will be scheduled based on its budget and deadline, using the Stride Scheduling Algorithm.
*   **Inputs:** Job details (Job ID, type, execution time, location, system type, budget, deadline).
*   **Processing:** Allocate tickets to the job based on its budget and deadline, and those of other jobs on the execution host. Calculate the job's stride (global stride constant / tickets) and initial pass (equal to stride).
*   **Outputs:** Scheduling information: job’s tickets, stride, and pass.

### 3.1.7 Determine Execution Host
This feature decides on which node and queue the job will be placed for execution, based on job budget, execution time, and deadline.
*   **Inputs:** Job details (Job ID, type, execution time, location, system type, budget, deadline), Cluster Information (CPU Load, Node Status, Remaining Time of Pending Jobs, Available Memory).
*   **Processing:** Sort hosts by load in ascending order to choose the least loaded host (load balancing). Select the appropriate queue based on job type (sequential/embarrassingly parallel), budget, etc.
*   **Outputs:** The chosen execution host and queue.

### 3.1.8 Dispatch Job
This feature inserts the job into the chosen queue on the execution host. The dispatcher decides when to send the job for execution, allowing for potential delays.
*   **Inputs:** The chosen execution host and queue.
*   **Processing:** Send the job to the appropriate queue to join the competition for resources.
*   **Outputs:** The scheduled job in its appropriate host and queue.

### 3.1.9 Update Cluster Status
This feature updates the cluster status whenever a job is scheduled or removed from the cluster.
*   **Inputs:** Job details (Job ID, type, execution time, location, system type, budget, deadline), Chosen execution host and queue.
*   **Processing:** Reserve required resources on the node. Update the execution host queue status and send this information about the additional load to the central information store on the master host.
*   **Outputs:** [N/A] (This feature performs an update and does not send results back; it's a trigger).

### 3.1.10 Execute Job
This feature runs as long as there are jobs in the queues, deciding how to time-slice between currently executing jobs based on the stride-scheduling algorithm.
*   **Inputs:** Scheduled Job (details, queue, node), Scheduling Information (job’s tickets, stride, pass).
*   **Processing:** Select the job with the minimum pass value from all jobs on the cluster and allot it a quantum. Advance that job's pass by its stride. In case of a tie, FIFO ordering is used. This loop repeats until no jobs are left in a queue.
*   **Outputs:** Updated Cluster Information (CPU Load, Node Status, Remaining Time of Pending Jobs, Available Memory).

## 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 as such.
*   **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
[N/A]

## 3.5 Logical database requirements
[N/A]

## 3.6 Design constraints
*   **Parent Component:** The Libra scheduler will be a sub-component of the Sun Grid Engine.
*   **Software Language:** All coding will be done in standard C.
*   **Scheduling Constraints:** Exhaustive searches of the entire set of combinations of jobs will not be done. Heuristics will be developed for this scheduling problem.
*   **Naming Convention:** All code will be written as specified by the Hungarian Naming Convention.
*   **Coding Standards:** All code will be written as required by the GNU General Purpose License.
*   **Purchased Components:** The entire Libra project is open source, and hence no component of it will be purchased.

## 3.7 Software system attributes
*   **Reliability:**
    *   Maximum bug rate: There will be a maximum of 1 bug/KLOC.
*   **Availability:**
    *   Maximum Time To Repair: In case of system outage, the cluster will be down while the Linux operating system boots up, which will take less than five minutes.
*   **Security:**
    *   The Libra scheduler will ensure the privacy of user job status.
    *   The Libra scheduler will ensure full control over job execution.
    *   Alteration of scheduling criteria or actual resource allocation is not possible without administrator authority.
*   **Maintainability:** [N/A]
*   **Portability:** [N/A]

## 3.8 Supporting information
*   Online user documentation will be in the form of man pages accessible through Linux, in accordance with requirements pertaining to open source software under the GNU General Purpose License.
*   The SRS is supported by:
    *   Appendix A – Background Research (dated 10th Nov, 2001) on: Cluster Computing, Market-based Economic Models, Cluster Scheduling, Cluster Management Software.
    *   Appendix B – Data Flow Diagrams.
    *   Appendix C – Data Dictionary.

# 4 Verification
[NULL]

## 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
[NULL]

## 5.1 Assumptions and dependencies
A number of factors that may affect the requirements specified in the SRS include:
*   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
*   **GPL:** GNU General Purpose License
*   **GUI:** Graphical User Interface
*   **KLOC:** Kilo Lines Of Code
*   **MPI:** Message Passing Interface
*   **PVM:** Parallel Virtual Machine
*   **QoS:** Quality of Service
*   **SGE:** Sun Grid Engine
*   **SRS:** Software Requirements Specification
