# 1 Introduction
[NULL]

## 1.1 Purpose
This document specifies the requirements for Libra, an Economy-Driven Cluster Scheduler. The purpose of the Libra scheduler is to offer a market-based, economy-driven service for managing batch jobs on clusters. It schedules CPU time according to user utility, such as budget and deadline, rather than system performance considerations. The main objective is to maximize user utility and provide Quality of Service (QoS) in a computational economy for cluster computing.

## 1.2 Scope
The software product to be produced is the Libra Scheduler.

The Libra Scheduler will 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 a market-based, economy-driven service for managing batch jobs on clusters by scheduling CPU time according to user utility rather than system performance considerations. 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.

The main objective of Libra is to provide Quality of Service (QoS) computational economy in cluster computing. To provide QoS to users, there will be no mechanism for users to interact with each other and bargain on the use of resources according to their considerations. The scheduler's functionality can be adapted in the future to schedule resources other than CPU time, even on a heterogeneous cluster.

## 1.3 Product overview
[NULL]

### 1.3.1 Product perspective
The Libra Scheduler is an add-on component for the Sun Grid Engine (SGE) cluster management system. It is not a standalone product. Libra integrates with SGE's queuing, scheduling, and resource managing module to provide an economy-driven service for managing batch jobs.

The larger system operates on a Linux-based cluster. SGE is responsible for receiving jobs submitted by a user and delegating them to Libra for scheduling. Libra determines the optimal workstation allocation based on its economic model and communicates this decision back to the SGE resource manager. The SGE resource manager then dispatches the job to the chosen workstation. Once a job is running, Libra is responsible for implementing the scheduling policy on the executing jobs.

#### System interfaces
Libra interfaces with the Sun Grid Engine (SGE) cluster management system. SGE delegates scheduling decisions for batch jobs to Libra. Libra, in turn, provides SGE with workstation allocation decisions and scheduling policies for executing jobs.

#### User interfaces
There are two types of users, each with a distinct interface, accessible via the Linux command prompt or the SGE interface.

*   **Cluster User Interface:** The user interface must allow a cluster user to perform the following actions:
    *   Submit jobs with associated parameters such as deadline, cost, and execution time.
    *   Query the cluster to establish the current cost per unit of time for new jobs.
    *   Monitor the status of their submitted jobs.
    *   Cancel jobs they have submitted.
    *   Check their credit balance.
    *   Check their usage history.
*   **Cluster Administrator Interface:** The administrator interface must provide all the functionality of the cluster user interface, plus the ability to perform the following actions:
    *   Check the status and load of each node in the cluster.
    *   Check the usage pattern history of the cluster.
    *   Check the status of all submitted jobs.
    *   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 are managed through the Sun Grid Engine. Libra will utilize SGE's interfaces for:

*   CPU usage
*   Memory usage
*   Swap file creation
*   Network communication

#### Software interfaces
*   **Sun Grid Engine (SGE):** Libra will directly interface with a modified version of Sun Grid Engine, version 5.3. SGE is the parent component and provides the primary software interface.
*   **Operating System:** The system will run on a Linux-based cluster. No modifications to the Linux kernel are required.
*   **Parallel Processing Libraries:** The cluster will use the PVM (Parallel Virtual Machine) and MPI (Message Passing Interface) libraries for the execution of embarrassingly parallel jobs.

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

#### Memory constraints
[N/A]

#### Operations
The system supports user-initiated operations for job submission, monitoring, and management. The administrator can perform additional operations related to cluster and job management. There are no specified requirements for periods of unattended operations, data processing support functions, or backup and recovery operations.

#### Site adaptation requirements
The system must be configurable by the cluster administrator. The administrator shall have the ability to modify features to adapt the software to a particular installation, including:

*   Altering the cost structure of the cluster.
*   Altering the scheduling policy of the cluster.

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

### 1.3.2 Product functions
The primary function of the Libra scheduler is to provide a Quality of Service (QoS) computational economy in cluster computing. It manages batch jobs by scheduling CPU time according to user-specified utility parameters, such as budget and deadline, rather than traditional system performance considerations.

With support from the Sun Grid Engine, the Libra scheduler will provide the following major functions:
*   Enforce resource allocations according to user-centric priorities.
*   Dynamically adjust resource limits, priorities, and the execution order of submitted jobs.
*   Provide scalability so that its performance does not degrade as nodes and jobs are added to the cluster.
*   Be configurable to allow for various scheduling policies that can incorporate QoS parameters.
*   Function as a separable component from the cluster management system.
*   Provide administrative security.
*   Provide at least a basic level of job accounting to aid scheduling policies.
*   Provide an interface for users to submit jobs and for administrators to oversee scheduling.

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

*   **Cluster User**: The user who submits jobs to the cluster. This user is expected to understand the nature of the submitted job, including its execution time and required resources. They must possess the technical expertise to use the job submission interface.
*   **Cluster Administrator**: The user who oversees scheduling and cluster usage. This user must be an advanced cluster operator, fully qualified and experienced in using Linux, Sun Grid Engine (SGE), and the Libra Scheduler.

### 1.3.4 Limitations
*   **Platform and Architecture:** The Libra scheduler is designed to operate as an add-on to the Sun Grid Engine (SGE) cluster management system, version 5.3. It is intended to run on a homogenous Linux cluster, and no modifications to the Linux kernel are permitted. All development will be done in standard C.
*   **Job and Scheduling Scope:** The scheduler will only manage sequential and embarrassingly parallel batch jobs. It will not support job migration for the purpose of decreasing resource fragmentation. The scheduling algorithm will be based on heuristics and will not perform exhaustive searches.
*   **System Interfaces:** The scheduler is entirely dependent on SGE for hardware interfaces (CPU, memory), communication architecture, and job submission. For parallel jobs, it relies on the PVM and MPI libraries. The user and administrator interfaces will be limited to the Linux command line and the existing SGE interface; a dedicated GUI is not part of the initial scope.
*   **Functional Scope:** The system will provide only a basic module for job accounting and payment. Detailed costing and pricing policies are deferred to a later version. There will be no mechanism for users to interact with each other to bargain for resources.
*   **Security:** User capabilities are restricted to prevent alteration of scheduling criteria or resource allocation without administrator authority.
*   **Licensing:** The software will be released under a GPL open-source license.

## 1.4 Definitions
- **Bid-based Proportional Resource-Sharing Model**: This is an economic model that specifies one way of allocating (cluster) resources between competing users based on what their criteria is, such as deadline and budget. In this model, the amount of resource allocated to users is proportional to the values of their bids. Essentially, in a bid-based system, the users are allocated tokens or credits, which they can use for having access to resources. The value of each credit depends on the resource demand and cost at the time of usage. We can modify this approach for our cluster, by evaluating this credit/priority according to the deadline and price constraints of users, and considering the system load and resources use as well. This priority is then used by a scheduling policy to allocate resource proportionally to the competing jobs.
- **Cluster/Cluster Computing**: Clustering involves connecting two or more computers together to take advantage of combined computational power and resources. Hence, a cluster works as an integrated collection of resources that can provide a single system image spanning all its nodes. Clustering is a popular strategy for processing applications because it transparently spreads the processing of different jobs throughout the cluster, and are used for high-performance applications such as AI expert systems, nuclear simulations, and scientific calculations.
- **Computational Economy**: Computational economy refers to 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. This essentially means that user constraints such as deadline and budget are more important in determining the priority of a job by the scheduler, than system policies like ordering jobs according to the basis of submission time. Currently, there is no holistic scheduling mechanism in cluster computing to enable differing QoS levels for different clients.
- **Embarrassingly Parallel Jobs**: These are 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. This is opposed to real parallel jobs that comprise dependent threads that need to interact with each other during the course of execution.
- **Grid Computing**: A grid is an infrastructure that couples resources such as computers (PCs, workstations, clusters and so on), software (for special purpose applications) and devices (printers, scanners) across the Internet and presents them as a unified integrated single resource that can be widely used. Grid computing refers to using a grid for processing jobs and processes.
- **Homogenous cluster**: A cluster in which the nodes or workstations have uniform characteristics such as the same memory size and hard disk space. They run the same operating system.
- **Job accounting**: It is a method of quantifying the system resources used by a job.
- **Linux**: Linux is an open source operating system, with extensive documentation and user support.
- **Open-source software**: Software for which the code is freely available for use and research.
- **Process Migration**: It is 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, thus maximizing their utility.
- **Sequential Jobs**: These are jobs that must be run on a single node, and cannot be split into separate jobs.
- **Stride Scheduling**: This is a scheduling algorithm to enforce resource allocations proportional to a user’s priority or share. A pool of tickets represents resource rights to a shared resource. A stride is inversely proportional to the number of tickets allocated to a job, hence representing the interval (in terms of CPU time) between two successive scheduling of a job. Jobs with more tickets have shorter strides and hence are scheduled more frequently and obtain a greater fraction of the resource. The algorithm is deterministic and quite accurately schedules jobs in exact proportions based on their ticket allocations.

# 2 References
[N/A]

# 3 Requirements
[NULL]

## 3.1 Functions
This section describes the functions of the Libra scheduler.

### 3.1.1 Submit Job
This function allows an end-user or administrator to submit a job through the Sun Grid Engine (SGE) interface. The SGE interface will be adapted to accept additional job parameters required by Libra. The system performs validity checks to determine if the cluster is currently accepting submissions and if the user is authorized.

*   Inputs:
    *   User Information: User name and authentication ID.
    *   Job Information: Details of the job to be submitted.
    *   Cluster Information: Cluster type, scheduling mechanism, current load, and submission criteria.
*   Outputs:
    *   A boolean value indicating whether the cluster is accepting submissions.
    *   A boolean value indicating whether the user is verified.

### 3.1.2 View Job Status
This function allows a user or administrator to view details about submitted jobs and monitor their execution progress. Access is authenticated to ensure users can only view their own jobs.

*   Inputs:
    *   User ID and Password.
*   Outputs:
    *   A user-specific view of submitted jobs and their current status.

### 3.1.3 Delete/Change Job
This function allows a user or administrator to cancel a submitted job or, under specific circumstances, change a job parameter. Critical parameters like deadline and budget are not normally changeable. Upon job deletion, the system revises its scheduling decisions for all other pending jobs.

*   Inputs:
    *   User ID and Password.
*   Outputs:
    *   Updated cluster information, including CPU load, node status, queue length, and revised finishing times for pending jobs.

### 3.1.4 Initialize Job
This function prepares a job for scheduling after it has been submitted via SGE. It retrieves the job details submitted by the user and sets them in variables that represent the state of the job within the scheduler.

*   Inputs:
    *   User-submitted job information and the Job ID assigned by SGE.
*   Outputs:
    *   Parsed job details: Job ID, job type, standalone execution time, location of executable and input data, system type, budget, and deadline.

### 3.1.5 Accept/Reject Job
This function determines whether the scheduler can satisfy the user's requirements based on the job's budget, deadline, and execution time. The scheduler assesses the current cluster load and the status of pending jobs to decide if the new job can be completed by its deadline.

*   Inputs:
    *   Job details: Job ID, type, execution time, budget, deadline.
    *   Cluster information: CPU load, node status, remaining execution time of pending jobs.
*   Outputs:
    *   A boolean value indicating whether the job is accepted or rejected.
    *   If rejected, a suggested alternative deadline or cost may be provided to the user.

### 3.1.6 Calculate Scheduling Information
This function determines the job's scheduling priority once it has been accepted. It uses the Stride Scheduling algorithm to allocate resources proportionally based on the job's budget and deadline relative to all other jobs. It calculates the tickets, stride, and pass for the job.

*   Inputs:
    *   Job details: Job ID, type, execution time, budget, deadline.
*   Outputs:
    *   Scheduling information: The job’s tickets, stride, and pass values.

### 3.1.7 Determine Execution Host
This function selects the most appropriate node (execution host) and queue for the job. To ensure load balancing, it sorts hosts by their current load and chooses the least loaded one. The queue is selected based on job type (sequential or embarrassingly parallel) and budget.

*   Inputs:
    *   Job details: Job ID, type, execution time, budget, deadline.
    *   Cluster Information: CPU load, node status, remaining time of pending jobs, available memory.
*   Outputs:
    *   The chosen execution host and queue for the job.

### 3.1.8 Dispatch Job
This function places the job into the queue on the execution host previously determined. The dispatcher decides when to send the job for execution, allowing more urgent jobs to be scheduled first.

*   Inputs:
    *   The chosen execution host and queue.
*   Outputs:
    *   The job is placed in the appropriate host and queue, ready for execution.

### 3.1.9 Update Cluster Status
This function updates the overall cluster status whenever a job is scheduled for execution or when a job finishes and is removed. It reserves the necessary resources on the node and updates the central information store on the master host with the new load information.

*   Inputs:
    *   Job details.
    *   The chosen execution host and queue.
*   Outputs:
    *   This function has no direct output as it is a trigger that updates the system's internal state.

### 3.1.10 Execute Job
This function manages the time-slicing between all jobs currently running in the queues. Using the stride-scheduling algorithm, it repeatedly selects the job with the minimum "pass" value, allocates it a quantum of CPU time, and advances that job's pass by its stride.

*   Inputs:
    *   The scheduled job's details.
    *   The job's scheduling information (tickets, stride, and pass).
*   Outputs:
    *   Updated cluster information, including CPU load, node status, and the remaining execution time of pending jobs.

### 3.1.11 Responses to Abnormal Situations
[N/A]

## 3.2 Performance requirements
The maximum response time for the submission of a job will be 1 minute.

The maximum number of jobs that can be scheduled is limited only by the capacity of the nodes to fulfill the jobs’ deadlines; there is no upper limit inherent in the Libra scheduler.

Assuming submitted statistics for jobs are accurate, the Libra scheduler will ensure that all jobs are completed within a 10% error allowance of their deadline.

The scheduler's performance should not degrade with the addition of nodes and jobs to the cluster.

## 3.3 Usability requirements
The system shall be designed for two classes of users: the cluster user who submits jobs and the cluster administrator who oversees the system. Users are expected to have the technical knowledge to use a command-line interface. The administrator must be an advanced cluster operator qualified in using Linux and SGE.

Initially, interaction with the system will be through the Linux command prompt or the native Sun Grid Engine interface. A graphical user interface (GUI) for job submission and administration is a desirable future feature.

The cluster user interface shall allow the user to perform the following actions:
*   Submit jobs with an 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 their submitted jobs.
*   Cancel jobs they have submitted.
*   Check their credit balance.
*   Check their usage history.

The cluster administrator interface shall provide all the capabilities of the cluster user, as well as allow the administrator 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.

Online user documentation shall be provided in the form of man pages accessible through the Linux operating system.

## 3.5 Logical database requirements
The system requires a central information store on the master host to manage and persist data related to users, jobs, and the cluster state.

*   **Types of information used by various functions**
    *   User Information: User name, authentication ID, and credit balance.
    *   Job Information: Job ID, job type (sequential or embarrassingly parallel), standalone execution time, location of executable and input data, system type, budget, deadline, current status, tickets, stride, and pass.
    *   Cluster State Information: Status of each node, CPU load on each node, queue status, and available memory.
    *   Historical Information: A history of jobs submitted by each user and the overall cluster usage patterns.

*   **Frequency of use**
    *   Job and cluster state information is accessed and updated frequently whenever a job is submitted, scheduled, dispatched, executed, or completed.
    *   User credit balance is updated upon job completion.
    *   Historical data is accessed less frequently for administrative checks and user queries.

*   **Accessing capabilities**
    *   Cluster users must be able to query the status of their own submitted jobs, check their credit balance, and view their usage history.
    *   The cluster administrator must be able to check the status of all submitted jobs, check the status and load of each cluster node, and check the usage pattern history of the entire cluster.

*   **Data entities and their relationships**
    *   A User entity contains user-specific data such as authentication ID and credit balance. Each user can have multiple jobs.
    *   A Job entity contains all parameters submitted with a job, such as execution time, budget, deadline, and its current execution status. Each job is associated with one user.
    *   A Node entity represents an execution host and stores its current state, including load and queue status. Each node can execute multiple jobs.

*   **Integrity constraints**
    *   The maximum cost charged to a user for a job will not exceed the budget submitted by the user for that job.

*   **Security**
    *   The system must ensure the privacy of user job status, allowing users to view only their own job information.
    *   Alteration of scheduling criteria or resource allocation data must be restricted to the cluster administrator.

*   **Data retention requirements**
    *   The system must retain a history of completed jobs to support user and administrator queries regarding usage history. The specific retention period is not defined.

## 3.6 Design constraints
*   The Libra scheduler will be implemented as a sub-component of the Sun Grid Engine (SGE) cluster management system.
*   The system will operate on a homogenous Linux cluster, and no modifications to the Linux kernel are permitted.
*   All software will be developed in the standard C programming language.
*   The source code must adhere to the Hungarian Naming Convention.
*   The scheduler will only manage sequential and embarrassingly parallel batch jobs.
*   The scheduling algorithm will be based on heuristics and will not perform exhaustive searches of job combinations.
*   The project will be entirely open source, with no purchased components.
*   The Libra scheduler will be released under the GNU General Purpose License (GPL).

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

### b) Availability
*   In case of a system outage, the maximum time to repair will be less than five minutes, which is the time required for the Linux operating system to boot.

### c) Security
*   The system shall verify that a user is valid before accepting job submissions.
*   Users must provide a User ID and Password to view job status or to delete/change a job.
*   The scheduler will ensure the privacy of user job status.
*   The scheduler will ensure full control over job execution, so that alteration of scheduling criteria or actual resource allocation is not possible without administrator authority.

### d) Maintainability
*   The Libra scheduler shall be separable from the cluster management system.
*   The scheduler shall be configurable, allowing for various scheduling policies to be modified.
*   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.

### e) Portability
*   All coding will be done in standard C.
*   The software is designed to run on a Linux operating system.
*   No modifications to the Linux kernel are required.

## 3.8 Supporting information
The problem to be solved by the software is the lack of a user-centric, economy-driven scheduling mechanism in cluster computing. The Libra scheduler will provide a market-based service that schedules resources based on user-specified Quality of Service (QoS) parameters, such as budget and deadline, to maximize user utility rather than system performance.

The following supporting information is provided in the appendices:
*   Sample input/output formats are described in the Data Flow Diagrams (Appendix B) and the Data Dictionary (Appendix C).
*   Cost analysis studies: [N/A]
*   User surveys: [N/A]
*   Background information on Cluster Computing, Market-based Economic Models, Cluster Scheduling, and Cluster Management Software is provided in Appendix A.

Special packaging instructions for the code and media: [N/A]

The information provided in the appendices is for context and background only and is not to be considered part of the formal requirements.

# 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
Verification of the design constraints will be performed through inspection, analysis, and testing.

*   **Parent Component (Sun Grid Engine):** The correct integration of the Libra scheduler as a sub-component of the Sun Grid Engine (SGE) will be verified during integration testing. Test cases will demonstrate that Libra properly interfaces with SGE, receiving jobs and returning scheduling decisions to the SGE resource manager.
*   **Software Language (Standard C):** Adherence to the standard C programming language will be verified through static code analysis and manual code reviews. The build process will be configured to use a standard C compiler with strict compliance flags enabled.
*   **Scheduling Constraints (Heuristics):** The use of a heuristic-based scheduling algorithm will be verified by code inspection and review of the algorithm's design documentation. Performance tests will be conducted to ensure scheduling decisions are made within acceptable time frames under various loads, which would be infeasible for an exhaustive search algorithm.

## 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 of a computer.
*   **GUI**: Graphical user interface.
*   **QoS**: Quality of Service – meeting what users actually want, thus maximizing their utility.
*   **SGE**: Sun Grid Engine cluster management system.
