# 1 Introduction
[NULL]

## 1.1 Purpose
The purpose of this Software Requirements Specification (SRS) is to describe the requirements and specifications of Libra, an Economy-Driven Cluster Scheduler. It details the functional features of the scheduler, along with interface details, design constraints, and performance characteristics. This document 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 designed to function as an add-on to the queuing, scheduling, and resource managing module of the open-source Sun Grid Engine (SGE) cluster management system. Its primary objective is to provide Quality of Service (QoS) computational economy in cluster computing by offering a market-based, economy-driven service for managing batch jobs. This involves scheduling CPU time based on user utility (e.g., budget and deadline) rather than solely on system performance considerations.

As part of this project, the Libra Scheduler will initially manage only sequential and embarrassingly parallel batch jobs on a homogenous Linux cluster. While its functionality can be adapted for other resources or heterogeneous clusters, this is outside the current scope. To provide QoS, there will be no mechanism for users to interact with each other or bargain for resource use.

The exact costing and pricing policy for the economic front-end will be specified in a later version of the project. The pricing mechanism will not affect the scheduling policies, as they assume a given cost and budget and schedule resources accordingly. Furthermore, at present, user and administrator interfaces will be limited to a command-line Linux interface or the existing Sun Grid Engine interface; a Graphical User Interface (GUI) may be added once basic functionality is implemented.

## 1.3 Product overview
[NULL]

### 1.3.1 Product perspective
Libra is an integral component of a larger system, the Sun Grid Engine (SGE) cluster management system, which operates on a Linux-based cluster. SGE is responsible for receiving user-submitted jobs and delegating them to Libra for scheduling and allocation to appropriate workstations or execution hosts. Libra communicates its workstation allocation decisions back to SGE's resource manager, which then dispatches the job to the chosen workstation. Once a job is assigned, Libra is responsible for implementing the defined scheduling policy on the jobs executing at the workstations. No modifications to the Linux kernel are required.

#### System interfaces

Libra interfaces directly with the modified Sun Grid Engine (SGE) cluster management system, version 5.3. SGE delegates jobs to Libra for scheduling and receives allocation decisions from Libra. SGE, in turn, interfaces with the underlying operating system and any other software components it requires.

#### User interfaces

There are two primary user types: the cluster user and the cluster administrator, each with corresponding interfaces. Initially, interaction will be through the Linux command prompt or the Sun Grid Engine (SGE) interface. A Graphical User Interface (GUI) may be added in the future.

*   **Cluster User Interface:** Allows users to:
    *   Submit jobs with associated deadline, cost, and execution time.
    *   Query the cluster for the current cost per unit time for submitting new jobs.
    *   Monitor the status of submitted jobs.
    *   Cancel jobs submitted by them.
    *   Check their credit balance.
    *   Check their usage history.
*   **Cluster Administrator Interface:** Provides all commands available to the cluster user, plus additional commands to:
    *   Check the status of each node in 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 utilized by Libra will be those provided by the Sun Grid Engine (SGE) on which it runs. This includes 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 (SGE) cluster management system, version 5.3. SGE, in turn, interfaces 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 the Sun Grid Engine (SGE) itself and will not introduce any unique communication interfaces beyond those provided by SGE.

#### Memory constraints

The current test environment consists of Pentium-III workstations with 128 MB RAM. Libra must operate within the memory constraints of the Sun Grid Engine (SGE) and the underlying Linux operating system on these nodes.

#### Operations

Users can submit jobs, view the status of their submitted jobs, and delete or change certain job parameters. Administrators have broader control, including monitoring all jobs and nodes, altering cost structures and scheduling policies, and managing any job. The system supports continuous job execution and dynamic resource reallocation based on economic principles.

#### 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 Quality of Service (QoS) constraints. Key functions include:

*   **Job Parameter Processing:** Receiving and processing job specifications submitted by the user, including location of executable and input data sets, standard output placement, system type, maximum execution time, job type (sequential or embarrassingly parallel), allocated budget, and deadline.
*   **QoS-Driven Scheduling:** Prioritizing jobs based on user-allocated budget and deadline, making user satisfaction the primary concern over maximizing raw CPU utilization.
*   **Dynamic Resource Allocation:** Enforcing resource allocations according to user-centric priorities and dynamically reallocating resources to accommodate urgent jobs. This includes the ability to change resource limits, priorities, privileges, and execution order of submitted jobs.
*   **Scalability:** Ensuring that performance does not degrade with the addition of nodes and jobs to the cluster.
*   **Configurability:** Allowing for various scheduling policies that can be modified to incorporate QoS parameters.
*   **Separability:** Operating as a separable component from the cluster management system.
*   **Administrative Security:** Providing mechanisms to ensure administrative security.
*   **Job Accounting:** Providing at least a basic level of job accounting to aid in scheduling policies.
*   **Economic Model Implementation:** Developing and implementing a market-based economic model (specifically, the bid-based proportional resource-sharing model) responsible for pricing and allocating resources according to user constraints. This model allocates computational time to jobs based on their priority, determined by deadline and budget considerations.
*   **Scheduling Algorithm:** Utilizing the proportional stride-scheduling algorithm to ensure that actual resource allocation accurately reflects the overall job share.

### 1.3.3 User characteristics
There are two primary classes of users for the Libra Scheduler:

*   **Cluster User:** Users who submit jobs to the cluster. They are expected to have technical knowledge to estimate job execution times and required resources, and possess the technical know-how to use the job submission interface.
*   **Cluster Administrator:** Administrators who oversee scheduling and cluster usage. They must be advanced cluster operators, fully qualified in using Linux, the Sun Grid Engine (SGE), and the Libra Scheduler.

### 1.3.4 Limitations
*   **Hardware Limitations:** The current test environment is limited to a network of four Pentium-III workstations, each with 128 MB RAM, running SGE on Linux. A larger number of dedicated workstations would be beneficial for more comprehensive performance analysis.
*   **Functional Scope Limitations:**
    *   The exact costing and pricing policy (economic front-end) will be specified in a later version.
    *   Initial user and administrator interfaces will be limited to command-line or the Sun Grid Engine (SGE) interface; a Graphical User Interface (GUI) is a potential future addition.
    *   The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
*   **Testing Limitations:** A dedicated simulation tool may need to be designed for testing purposes if a suitable generic and freely available one is not found.
*   **Procurement Limitations:** The entire Libra project is open source, and no components will be purchased.

## 1.4 Definitions
*   **Bid-based Proportional Resource-Sharing Model:** An economic model that specifies a method for allocating cluster resources between competing users based on their criteria, such as deadline and budget. In this model, the amount of resource allocated to users is proportional to the values of their bids (tokens or credits).
*   **Cluster/Cluster Computing:** Involves connecting two or more computers to leverage their combined computational power and resources. A cluster functions as an integrated collection of resources, providing a single system image across all its nodes, used for high-performance applications.
*   **Computational Economy:** Refers to the inclusion of user-specified Quality of Service (QoS) parameters with jobs, enabling resource management to be based on a user-centric approach (e.g., user constraints like deadline and budget) rather than a system-centric approach (e.g., submission time).
*   **Embarrassingly Parallel Jobs:** Parallel jobs comprised of independent parts that can be split up and performed on separate nodes as if they are sequential jobs, requiring minimal inter-job communication.
*   **Grid Computing:** An infrastructure that couples diverse resources (computers, software, devices) across the Internet and presents them as a unified, integrated single resource for processing jobs.
*   **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.
*   **Job accounting:** A method of quantifying the system resources used by a job.
*   **Process Migration:** The process of moving a job from one computer system to another without restarting the job from the beginning.
*   **QoS (Quality of Service):** Meeting what users actually want, thereby maximizing their utility.
*   **Sequential Jobs:** Jobs that must be run on a single node and cannot be split into separate jobs.
*   **Stride Scheduling:** A scheduling algorithm designed to enforce resource allocations proportional to a user’s priority or share. A pool of tickets represents resource rights, and a stride (inversely proportional to tickets) represents the interval between successive scheduling of a job. Jobs with more tickets are scheduled more frequently.

# 2 References
*   Buyya, R., Abramson, D., & Giddy, J. (2000). *Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid*. HPC ASIA’2000, China, IEEE CS Press, USA.
*   Buyya, R., Abramson, D., & Giddy, J. (2000). *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.
*   Buyya, R., Abramson, D., & Giddy, J. (2001). *An Economy Grid Architecture for Service-Oriented Grid Computing*. 10th IEEE International Heterogeneous Computing Workshop (HCW 2001), with IPDPS 2001, SF, California, USA.
*   Buyya, R., Stockinger, H., Giddy, J., & Abramson, D. *Economic Models for Management of Resources in Peer-to-Peer and Grid Computing*. Monash University.
*   Chun, B. N., & Culler, D. E. (1999). *Market-based proportional resource sharing for clusters*. Submitted for publication.

# 3 Requirements
[NULL]

## 3.1 Functions
The Libra scheduler performs a series of functions to manage and execute jobs within the cluster, interacting with the Sun Grid Engine (SGE) and directly managing scheduling decisions.

*   **3.1.1 Submit Job (SGE-facilitated)**
    *   **Introduction:** This feature, facilitated by the SGE interface (or command-line), allows end-users or administrators to submit jobs. The SGE interface will be adapted to include additional submission parameters required by Libra.
    *   **Inputs:**
        *   User Information: Name, authentication ID.
        *   Job Information: Details about the job to be submitted, including parameters for Libra.
        *   Cluster Information: Cluster type, scheduling mechanism details, current load status, submission directions and criteria.
    *   **Processing:** The cluster determines if it is open for job submissions and if the user is valid. This is distinct from the job acceptance decision based on budget/deadline.
    *   **Outputs:**
        *   Boolean: Indicates if the cluster is accepting submissions.
        *   Boolean: Indicates if the user is verified.

*   **3.1.2 View Job Status (SGE-facilitated)**
    *   **Introduction:** This feature allows users or administrators to view details about submitted jobs and their execution progress.
    *   **Inputs:** User ID and Password (for authentication).
    *   **Processing:** Displays available options and progress information about submitted jobs. Processes selected options if choices are provided to view different aspects of job information.
    *   **Outputs:** User view of available options and status for jobs submitted by the user.

*   **3.1.3 Delete/Change Job (SGE-facilitated)**
    *   **Introduction:** 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:** Removes the job from the queue and updates cluster status. Revises scheduling decisions for pending jobs and new submissions.
    *   **Outputs:** Updated cluster information and scheduling decisions (CPU load, node status, queue length, quanta allocated to pending jobs, revised expected finishing deadline of pending jobs). These outputs are facilitated by SGE.

*   **3.1.4 Initialize Job (Libra Function)**
    *   **Introduction:** This is a core Libra function that prepares the scheduler for a job once it has been accepted by SGE, using information from the scheduler.
    *   **Inputs:** User-submitted job information and the job ID assigned by SGE.
    *   **Processing:** Retrieves job details and sets them into variables representing the cluster's state and queues. Parsed parameters are passed to the scheduling module for acceptance/rejection.
    *   **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 (Libra Function)**
    *   **Introduction:** This function determines if a job can be satisfied given its budget and deadline.
    *   **Inputs:**
        *   Job details: Job ID, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
        *   Cluster information: CPU load, node status, remaining time of pending jobs.
    *   **Processing:** Based on job parameters, the scheduler calculates a priority reflecting the CPU time share deserved. It determines if the job can finish by its deadline, considering its execution time and the status of other pending jobs.
    *   **Outputs:**
        *   Boolean: Specifies if the job is accepted or rejected.
        *   Suggested deadline or cost: Provided to the user as a precondition for job acceptance.

*   **3.1.6 Calculate Scheduling Information (Libra Function)**
    *   **Introduction:** This Libra feature decides how a job will be scheduled based on its budget and deadline, using the Stride Scheduling Algorithm. It is performed once a job has been accommodated.
    *   **Inputs:** Job details: Job ID, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
    *   **Processing:** Allocates tickets to a job based on its budget, deadline, and those of other jobs on the potential execution host. Calculates the job's stride (global stride constant divided by tickets) and initial pass (equal to stride).
    *   **Outputs:** Scheduling information: The job’s tickets, stride, and pass.

*   **3.1.7 Determine Execution Host (Libra Function)**
    *   **Introduction:** This feature selects the node and queue for job execution based on budget, execution time, and deadline.
    *   **Inputs:**
        *   Job details: Job ID, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
        *   Cluster Information: CPU Load, Node Status, Remaining Time of Pending Jobs, Available Memory.
    *   **Processing:** Libra sorts hosts by load in ascending order to ensure load balancing, then selects the appropriate queue based on job type (sequential/embarrassingly parallel), budget, and other criteria.
    *   **Outputs:** The chosen execution host and queue.

*   **3.1.8 Dispatch Job (Libra Function)**
    *   **Introduction:** This feature inserts the job into the chosen queue on the execution host. It is separate to allow for potential waiting periods before CPU time is allocated, enabling other urgent jobs to be scheduled first.
    *   **Inputs:** The chosen execution host and queue for job placement.
    *   **Processing:** The scheduler sends the job to the appropriate queue, where it joins the competition for resources.
    *   **Outputs:** The scheduled job in its appropriate host and queue.

*   **3.1.9 Update Cluster Status (Libra Function)**
    *   **Introduction:** This Libra feature updates the cluster status whenever a job is scheduled for execution or removed from the cluster upon completion.
    *   **Inputs:**
        *   Job details: Job ID, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
        *   Chosen execution host and queue.
    *   **Processing:** Libra reserves the required resources on the node, updates the execution host queue status, and sends this load information to the central information store on the master host.
    *   **Outputs:** [N/A] (This function performs an update and does not return results; it acts as a trigger).

*   **3.1.10 Execute Job (Libra Function)**
    *   **Introduction:** This feature continuously 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: Job details, queue, and node where the job is scheduled.
        *   Scheduling Information: The job’s tickets, stride, and pass.
    *   **Processing:** It identifies the job with the minimum pass value across the cluster, allocates it a quantum of CPU time, and then advances that job's pass by its stride. In case of a tie, FIFO ordering is used. This process repeats until no jobs remain 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 schedulable jobs is limited only by the capacity of the nodes to fulfill job deadlines; there is no inherent upper limit within the Libra scheduler itself.
*   **Deadline Sensitivity:** Assuming accurate submitted job statistics, 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
*   **Documentation:** All documentation will adhere to requirements for open-source software under the GNU General Purpose License. Additionally, online user documentation will be provided in the form of man pages accessible through Linux.

## 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 (SGE).
*   **Software Language:** All coding will be done in standard C.
*   **Scheduling Constraints:** Exhaustive searches of the entire set of job combinations will not be performed. Heuristics will be developed for the scheduling problem.
*   **Licensing:** Libra will be released under a GPL license and will be open-source.
*   **Purchased Components:** The entire Libra project is open source, and no components will be purchased.

## 3.7 Software system attributes
*   **Reliability:**
    *   **Maximum Bug Rate:** There will be a maximum of 1 bug per KLOC (thousand lines of code).
*   **Availability:**
    *   **Maximum Time To Repair:** In case of a 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.
    *   It will ensure full control over job execution, preventing alteration of scheduling criteria or actual resource allocation without administrator authority.
*   **Maintainability:**
    *   **Naming Convention:** All code will be written as specified by the Hungarian Naming Convention.
    *   **Coding Standards:** All code will adhere to the requirements of the GNU General Purpose License.
*   **Portability:** [N/A]

## 3.8 Supporting information
*   **Background Research:** Appendix A provides background research (dated 10th Nov, 2001) on Cluster Computing, Market-based Economic Models, Cluster Scheduling, and Cluster Management Software.
*   **Data Flow Diagrams:** Appendix B contains Data Flow Diagrams illustrating the scheduler's processes.
*   **Data Dictionary:** Appendix C provides a Data Dictionary to interpret and understand the Data Flow Diagrams.
*   **Legal and Copyright Notices:**
    *   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.

# 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 may affect the requirements specified in this SRS:

*   **SGE Module Workability:** It is assumed that the Sun Grid Engine (SGE) cluster management system modules, such as those dealing with process migration, will be workable with the scheduling policies provided by the Libra Scheduler.
*   **Job Accounting and Payment:** A basic module for job accounting and payment considerations will be provided by external means, as these are not the primary focus of the scheduler itself.
*   **User Job Estimates:** Users are assumed to have a fair estimate of job execution times, which facilitates the scheduler's decision to accept or reject a job.
*   **Deferred Requirements:** Detailed requirements for the economic front-end (costing and pricing policy) will be specified in a later version. The current user and administrator interfaces are command-line or SGE-based, with a GUI being a potential future addition. The decision on whether to design a custom simulation tool or use a generic one for testing is pending.

## 5.2 Acronyms and abbreviations
*   **CPU:** Central Processing Unit
*   **GPL:** GNU General Purpose License
*   **GUI:** Graphical User Interface
*   **KLOC:** Kilo Lines Of Code (thousand lines of code)
*   **Linux:** An open-source operating system
*   **MPI:** Message Passing Interface
*   **PVM:** Parallel Virtual Machine
*   **QoS:** Quality of Service
*   **SGE:** Sun Grid Engine cluster management system
*   **SRS:** Software Requirements Specification
