# 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. Libra is designed to provide a market-based economy-driven service for managing batch jobs on clusters, focusing on scheduling CPU time according to user utility rather than system performance considerations. The main objective of Libra is to offer Quality of Service (QoS) computational economy in cluster computing, specifically for users and owners of high-performance clusters, cluster management software, job schedulers, and grid resources.

## 1.2 Scope
The software product to be produced is the Libra Scheduler, an add-on to the Sun Grid Engine (SGE) cluster management system. The Libra Scheduler is designed to manage batch jobs on clusters by scheduling CPU time based on user utility rather than system performance considerations. Its primary function is to provide a market-based, economy-driven service that optimizes Quality of Service (QoS) in cluster computing.

The application of the Libra Scheduler is specifically for managing sequential and embarrassingly parallel batch jobs on a homogeneous Linux cluster. Although initially focused on CPU time scheduling, its functionality can be adapted to manage other resources and operate on heterogeneous clusters. The main objective of the Libra Scheduler is to implement a computational economy that prioritizes user constraints such as deadlines and budgets over traditional system-centric scheduling policies. This approach aims to maximize user satisfaction and utility.

The Libra Scheduler does not facilitate user interaction for resource bargaining, differentiating it from grid-computing environments like Nimrod/G. The project aligns with the broader goal of enhancing QoS in high-performance cluster environments, consistent with higher-level specifications of cluster management systems.

## 1.3 Product overview
[NULL]

### 1.3.1 Product perspective
Libra is an add-on to the Sun Grid Engine (SGE) cluster management system, which operates on a Linux-based cluster. It is designed to enhance the queuing, scheduling, and resource management capabilities of SGE by introducing a market-based economy-driven service for managing batch jobs on clusters. Libra's primary function is to schedule CPU time based on user utility rather than system performance considerations, thereby providing Quality of Service (QoS) in cluster computing.

#### System interfaces
Libra interfaces with the Sun Grid Engine, which is responsible for receiving job submissions and delegating them to Libra for scheduling. Libra communicates its scheduling decisions back to the resource manager, which then dispatches the jobs to the appropriate workstations. No modifications to the Linux kernel are required for this integration.

#### User interfaces
Libra provides interfaces for two types of users: cluster users and cluster administrators. Users can interact with the system through the Linux command prompt or the SGE interface to submit jobs, monitor job status, and manage job parameters. Administrators have additional capabilities to oversee cluster operations, modify scheduling policies, and manage job execution.

#### Hardware interfaces
Libra utilizes the hardware interfaces provided by the Sun Grid Engine, which include CPU usage, memory usage, swap file creation, and network communication. These interfaces ensure that Libra can effectively manage resources across the cluster.

#### Software interfaces
Libra interfaces directly with the modified Sun Grid Engine version 5.3. It also utilizes the PVM (Parallel Virtual Machine) and MPI (Message Passing Interface) libraries for executing embarrassingly parallel jobs. The operating system and other necessary software components are managed by SGE.

#### Communications interfaces
Libra leverages the communications architecture of the Sun Grid Engine, without introducing any unique communications interfaces beyond those provided by SGE.

#### Memory constraints
[N/A]

#### Operations
Libra supports dynamic resource allocation, allowing users to prioritize jobs based on budget and deadlines. It operates in both user-initiated and unattended modes, ensuring efficient job scheduling and execution. Backup and recovery operations are managed by the underlying SGE system.

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

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

### 1.3.2 Product functions
The Libra Scheduler is designed to enhance the Sun Grid Engine cluster management system by providing a market-based, economy-driven service for managing batch jobs on clusters. The major functions of the Libra Scheduler include:

- **Job Submission**: Users can submit jobs with specific parameters such as location of executables, input data sets, execution time, and whether the job is sequential or embarrassingly parallel. The scheduler will prioritize jobs based on user-defined criteria like budget and deadline.

- **Job Scheduling**: The scheduler allocates resources based on a bid-based proportional resource-sharing model, ensuring that jobs are scheduled according to user-centric priorities. It dynamically reallocates resources to accommodate urgent jobs, even if submitted later.

- **Resource Allocation**: Using the stride scheduling algorithm, the scheduler enforces resource allocations proportional to a user's budget and deadline, optimizing CPU utilization while maintaining Quality of Service (QoS).

- **Job Monitoring and Management**: Users and administrators can view job status, delete or change job parameters, and monitor resource usage. The system provides administrative security and job accounting to aid in scheduling policies.

- **Dynamic and Scalable Operations**: The scheduler is designed to be dynamic, allowing for changes in resource limits and execution order, and scalable, ensuring performance does not degrade with the addition of nodes and jobs.

- **User and Administrator Interfaces**: The system provides interfaces for both users and administrators to interact with the cluster, submit jobs, monitor status, and manage scheduling policies.

These functions collectively aim to maximize user utility by aligning resource management with user-defined constraints, thereby providing a QoS computational economy in cluster computing.

### 1.3.3 User characteristics
The Libra Scheduler is designed for two primary user groups: cluster users and cluster administrators. 

- **Cluster Users**: These users are responsible for submitting jobs to the cluster. They must have a clear understanding of the job's nature, including execution time and required resources. Technical expertise is necessary to effectively use the interface for job submission.

- **Cluster Administrators**: Administrators oversee scheduling and cluster usage. They must be advanced cluster operators with comprehensive knowledge of Linux, the Sun Grid Engine (SGE), and the Libra Scheduler. Their role requires a high level of technical expertise to manage and configure the system effectively.

Both user groups are expected to have a strong technical background, with no specific accommodations mentioned for disabilities or varying educational levels.

### 1.3.4 Limitations
a) [N/A]

b) The current hardware limitation is the provision of a network of four Pentium-III workstations with 128 MB RAM for implementing and testing the high-performance cluster.

c) Libra will interface with the Sun Grid Engine cluster management system and utilize its interfaces for CPU usage, memory usage, swap file creation, and network communication.

d) [N/A]

e) [N/A]

f) [N/A]

g) All coding will be done in standard C.

h) [N/A]

i) The Libra scheduler will ensure the privacy of user job status and control over job execution, preventing unauthorized alteration of scheduling criteria or resource allocation.

j) [N/A]

k) The Libra scheduler will ensure security by maintaining privacy and control over job execution, requiring administrator authority for any alterations.

l) [N/A]

m) The workability of the Sun Grid Engine cluster management system modules, such as those dealing with process migration, is assumed to be compatible with the scheduling policies provided by the Libra Scheduler.

## 1.4 Definitions
- **Cluster/Cluster Computing**: Connecting two or more computers to leverage combined computational power and resources, providing a single system image across all nodes. Used for high-performance applications like AI, nuclear simulations, and scientific calculations.

- **QoS (Quality of Service)**: Meeting user requirements to maximize their utility.

- **Computational Economy**: Incorporating user-specified QoS parameters with jobs, focusing on user-centric resource management rather than system-centric, prioritizing user constraints like deadlines and budgets over system policies.

- **Grid Computing**: Infrastructure that integrates resources like computers, software, and devices across the Internet, presenting them as a unified resource for processing jobs.

- **Bid-based Proportional Resource-Sharing Model**: An economic model for allocating resources between users based on criteria like deadlines and budgets, where resource allocation is proportional to bid values.

- **Stride Scheduling**: A scheduling algorithm that allocates resources proportional to a user's priority or share, using a pool of tickets representing resource rights. Jobs with more tickets have shorter strides and are scheduled more frequently.

- **Process Migration**: Moving a job from one computer system to another without restarting it.

- **Sequential Jobs**: Jobs that must run on a single node and cannot be split into separate jobs.

- **Embarrassingly Parallel Jobs**: Parallel jobs that can be split into independent parts to run on separate nodes with minimal inter-job communication.

- **Job Accounting**: Quantifying system resources used by a job.

- **GUI (Graphical User Interface)**: A user interface that includes graphical elements.

- **CPU (Central Processing Unit)**: The primary component of a computer that performs most of the processing.

- **SGE (Sun Grid Engine)**: A cluster management system.

- **Open-source software**: Software with freely available code for use and research.

- **Homogenous cluster**: A cluster where nodes have uniform characteristics, such as memory size and operating system.

# 2 References
## Compliance
[N/A]

## Guidance

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.

These references can be obtained from the respective publishing organizations or academic libraries.

# 3 Requirements
[NULL]

## 3.1 Functions
The Libra Scheduler is designed to manage batch jobs on clusters by scheduling CPU time according to user utility. The following functions outline the fundamental actions required for accepting and processing inputs, as well as generating outputs:

### 3.1.1 Submit Job
- **Inputs**: User information, job information, and cluster information.
- **Processing**: Validates if the cluster is open for job submissions and verifies user credentials.
- **Outputs**: Boolean values indicating whether the cluster is accepting submissions and if the user is verified.

### 3.1.2 View Job Status
- **Inputs**: User ID and password.
- **Processing**: Displays available options and progress of job execution.
- **Outputs**: User view of job status and options.

### 3.1.3 Delete/Change Job
- **Inputs**: User ID and password.
- **Processing**: Removes or updates job parameters, revises scheduling decisions.
- **Outputs**: Updated cluster information and scheduling decisions.

### 3.1.4 Initialize Job
- **Inputs**: Job details and job ID from SGE.
- **Processing**: Retrieves job details and sets cluster state variables.
- **Outputs**: Set variables representing job information.

### 3.1.5 Accept/Reject Job
- **Inputs**: Job details and cluster information.
- **Processing**: Determines job priority and feasibility based on budget and deadline.
- **Outputs**: Boolean value for job acceptance and suggested conditions for acceptance.

### 3.1.6 Calculate Scheduling Information
- **Inputs**: Job details.
- **Processing**: Allocates tickets, calculates stride and pass using the Stride Scheduling Algorithm.
- **Outputs**: Scheduling information including tickets, stride, and pass.

### 3.1.7 Determine Execution Host
- **Inputs**: Job details and cluster information.
- **Processing**: Selects the least loaded host and appropriate queue.
- **Outputs**: Chosen execution host and queue.

### 3.1.8 Dispatch Job
- **Inputs**: Chosen execution host and queue.
- **Processing**: Sends job to the appropriate queue for execution.
- **Outputs**: Scheduled job in its designated host and queue.

### 3.1.9 Update Cluster Status
- **Inputs**: Job details and chosen execution host and queue.
- **Processing**: Reserves resources, updates queue status, and informs the central information store.
- **Outputs**: [N/A]

### 3.1.10 Execute Job
- **Inputs**: Scheduled job details and scheduling information.
- **Processing**: Allocates CPU time based on the minimum pass value, updates pass using stride.
- **Outputs**: Updated cluster information including CPU load and node status.

### Error Handling and Recovery
- **Responses to Abnormal Situations**: [N/A]
- **Effect of Parameters**: Job parameters such as budget and deadline directly influence scheduling decisions and resource allocation.
- **Relationship of Outputs to Inputs**: Outputs are directly related to inputs through the scheduling algorithms and job parameters, ensuring that user constraints are prioritized in scheduling decisions.

The functions are designed to ensure that user satisfaction is prioritized by optimizing resource utilization within user-imposed constraints, while maintaining system performance and scalability.

## 3.2 Performance requirements
The performance requirements for the Libra Scheduler are as follows:

- **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.

[N/A]

## 3.3 Usability requirements
The Libra Scheduler aims to provide a user-friendly experience for both cluster users and administrators. Usability requirements focus on ensuring that users can effectively and efficiently interact with the system, achieving their goals with satisfaction and minimal risk of error.

- **Effectiveness**: Users should be able to submit jobs, monitor their status, and manage job parameters with ease. The system should provide clear feedback on job submissions and status updates to ensure users understand the current state of their tasks.

- **Efficiency**: The interface should allow users to perform tasks quickly, minimizing the time required to submit jobs and retrieve job status information. The system should respond to user actions, such as job submissions and queries, within a maximum of one minute.

- **Satisfaction**: The system should be intuitive and easy to navigate, reducing the learning curve for new users. A command-line interface will be available initially, with the potential for a graphical user interface (GUI) to enhance user satisfaction in future iterations.

- **Avoidance of Harm**: The system will ensure the privacy of user job status and prevent unauthorized alterations to job execution and scheduling criteria. Only authorized administrators will have the ability to modify critical parameters, ensuring the integrity of the scheduling process.

These usability requirements are designed to ensure that the Libra Scheduler meets the needs of its users while maintaining a high level of satisfaction and security. [N/A]

## 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), which imposes certain design constraints. All coding for the Libra scheduler will be done in standard C, adhering to the GNU General Purpose License. The scheduling constraints dictate that exhaustive searches of the entire set of combinations of jobs will not be performed; instead, heuristics will be developed to address the scheduling problem.

## 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 per KLOC (thousand lines of code).

### Availability
- 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, so that alteration of scheduling criteria or actual resource allocation is not possible without administrator authority.

### Maintainability
- [N/A]

### Portability
- All coding will be done in standard C.
- The entire Libra project is open source, and hence no component of it will be purchased.
- Libra will be released under a GPL license and will be open-source.
- All documentation will be made in accordance with requirements pertaining to open source software under the GNU General Purpose License.
- On-line user documentation will be in the form of man pages accessible through Linux.
- The Libra scheduler will be a sub-component of the Sun Grid Engine (SGE).
- Libra will directly interface with the modified Sun Grid Engine cluster management system, version 5.3.
- For the execution of embarrassingly parallel jobs, the PVM (Parallel Virtual Machine) and MPI (Message Passing Interface) libraries will be used by the cluster.
- Libra will utilize the communications architecture of Sun Grid Engine itself, and will not have any unique communications interfaces above that of SGE.
- All hardware interfaces of Libra will be those of the Sun Grid Engine on top of which it will be running.

## 3.8 Supporting information
[N/A]

# 4 Verification
[NULL]

## 4.1 Functions
The verification of the Libra Scheduler's functions will involve several approaches to ensure the software meets its specified requirements. The following methods will be employed:

- **Validity Checks on Inputs**: Verification will include testing the input parameters such as user information, job details, and cluster information to ensure they are correctly validated before processing. This will involve unit tests and integration tests to confirm that invalid inputs are appropriately handled and do not cause system failures.

- **Exact Sequence of Operations**: The sequence of operations for each function, such as job submission, scheduling, and execution, will be verified through detailed test cases that simulate real-world scenarios. This will ensure that the operations occur in the correct order and produce the expected outcomes.

- **Responses to Abnormal Situations**: The system's response to abnormal situations will be tested, including:
  - **Overflow**: Stress testing will be conducted to ensure the system can handle maximum input loads without crashing.
  - **Communication Facilities**: Tests will verify that communication between the scheduler and the Sun Grid Engine is reliable and that any communication failures are gracefully handled.
  - **Hardware Faults and Failures**: Simulations of hardware failures will be performed to ensure the system can recover or fail safely without data loss.
  - **Error Handling and Recovery**: The error handling mechanisms will be tested to ensure that errors are logged, and recovery procedures are initiated as specified.

- **Effect of Parameters**: The impact of different job parameters, such as budget and deadline, on scheduling decisions will be verified through test cases that vary these parameters and observe the resulting scheduling behavior.

- **Relationship of Outputs to Inputs**: The relationship between inputs and outputs will be verified by:
  - **Input/Output Sequences**: Ensuring that the sequence of inputs leads to the correct sequence of outputs, as specified in the requirements.
  - **Formulas for Input to Output Conversion**: Testing the algorithms and formulas used for converting inputs to outputs, such as the stride scheduling algorithm, to ensure they produce the correct results.

These verification methods will be applied to each functional requirement, ensuring that the Libra Scheduler operates as intended and meets all specified requirements.

## 4.2 Performance requirements
The verification of performance requirements for the Libra Scheduler will focus on ensuring that the system meets the specified response times, capacity, deadline sensitivity, and cost sensitivity. The following methods will be employed:

- **Response Time Verification**: The system will be tested to ensure that the maximum response time for job submission does not exceed 1 minute. This will be measured by submitting jobs under various conditions and recording the time taken for the system to acknowledge the submission.

- **Capacity Verification**: Although there is no inherent upper limit to the number of jobs the Libra Scheduler can handle, tests will be conducted to ensure that the system can manage the maximum number of jobs that the nodes can handle without missing deadlines. This will involve stress testing the system with a high volume of job submissions.

- **Deadline Sensitivity Verification**: The system will be evaluated to ensure that all jobs are completed within a 10% error allowance of their specified deadlines. This will be verified by submitting jobs with known execution times and deadlines and checking the completion times.

- **Cost Sensitivity Verification**: The system will be tested to confirm that the maximum cost charged to the user does not exceed the maximum cost submitted by the user. This will involve submitting jobs with various budget constraints and verifying the cost calculations.

These verification methods will ensure that the Libra Scheduler meets its performance requirements under both normal and peak workload conditions.

## 4.3 Usability requirements
[N/A]

## 4.5 Logical database requirements
[N/A]

## 4.6 Design constraints
Verification of design constraints will involve ensuring that the Libra scheduler adheres to the specified constraints imposed by the Sun Grid Engine (SGE) and the project requirements. The following approaches will be used:

- **Parent Component Verification**: Confirm that the Libra scheduler functions as a sub-component of the Sun Grid Engine without requiring modifications to the SGE or the Linux kernel.

- **Software Language Compliance**: Verify that all coding is done in standard C, as specified.

- **Scheduling Constraints**: Ensure that the scheduling algorithms do not perform exhaustive searches of all job combinations. Instead, verify that heuristics are developed and implemented for efficient scheduling.

These verification activities will be conducted through code reviews, testing, and validation against the project specifications and external standards.

## 4.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 per thousand lines of code (KLOC).

### Availability
- 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 and ensure full control over job execution, so that alteration of scheduling criteria or actual resource allocation is not possible without administrator authority.

### Maintainability
- [N/A]

### Portability
- All coding will be done in standard C, which is a proven portable language.
- [N/A] for other portability attributes.

# 5 Appendices
[NULL]

## 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
- **GUI**: Graphical User Interface
- **QoS**: Quality of Service
- **SGE**: Sun Grid Engine
- **PVM**: Parallel Virtual Machine
- **MPI**: Message Passing Interface
