## 1.1 Purpose
This document describes the requirements and specifications 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, defined by parameters such as budget and deadline, rather than system performance considerations. The main objective of Libra is to provide Quality of Service (QoS) computational economy in 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.1 Product perspective
The Libra Scheduler is an add-on component for the Sun Grid Engine (SGE) cluster management system. It operates as part of this larger system, which runs on a Linux-based cluster. SGE is responsible for receiving jobs submitted by a user and delegating them to Libra for scheduling. Libra communicates its scheduling and allocation decisions back to the SGE resource manager, which then dispatches the job to the chosen workstation. Once a job is assigned, Libra is responsible for implementing the scheduling policy for the jobs executing on the workstations. No modifications to the Linux kernel are required.

#### System interfaces
The system interface is defined by the interaction between Libra and the Sun Grid Engine. SGE provides the primary interface for job submission and management, delegating scheduling decisions to Libra. Libra, in turn, provides scheduling information and host allocation decisions back to SGE's resource management module for execution.

#### User interfaces
There are two types of users, each with a corresponding interface provided through the Linux command prompt or the Sun Grid Engine interface.

*   **Cluster User Interface:** Allows a 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 submitted jobs.
    *   Cancel jobs submitted by them.
    *   Check their credit balance.
    *   Check their usage history.
*   **Cluster Administrator Interface:** Provides all the capabilities of the Cluster User Interface, plus the ability to:
    *   Check the status of each node of the cluster.
    *   Check the usage pattern history of the cluster.
    *   Check the status of all submitted jobs.
    *   Check the load on each node of the cluster.
    *   Alter the cost structure of the cluster.
    *   Alter the scheduling policy of the cluster.
    *   Cancel, suspend, and resume any job.

#### Hardware interfaces
Libra will utilize the hardware interfaces provided by the Sun Grid Engine, upon which it runs. These include interfaces for:

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

#### Software interfaces
*   **Sun Grid Engine (SGE):** Libra will directly interface with SGE, version 5.3. SGE, in turn, interfaces with the underlying Linux operating system.
*   **Parallel Execution Libraries:** For the execution of embarrassingly parallel jobs, the cluster will use the PVM (Parallel Virtual Machine) and MPI (Message Passing Interface) libraries.

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

#### Memory constraints
[N/A]

#### Operations
Normal operations are initiated by users and administrators through the command-line or SGE interfaces. These operations include submitting, monitoring, and managing jobs and the cluster itself. No specific requirements for periods of unattended operations, data processing support functions, or backup and recovery operations are specified.

#### Site adaptation requirements
The software can be adapted to a particular installation through configuration options available to the administrator. The administrator can alter the cost structure and the scheduling policy of the cluster.

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

### 1.3.2 Product functions
The main function of the Libra scheduler is to manage batch jobs on clusters by scheduling CPU time according to user utility (Quality of Service) rather than system performance considerations. It will use a market-based economic model where job scheduling is driven by user-specified parameters, primarily budget and deadline.

With support from the Sun Grid Engine (SGE), the Libra scheduler will provide the following functions:
*   Enforce resource allocations according to user-centric priorities.
*   Dynamically change resource limits, priorities, and the execution order of submitted jobs.
*   Provide scalable performance that does not degrade with the addition of more nodes and jobs.
*   Be configurable, allowing for various scheduling policies that can be modified to incorporate QoS parameters.
*   Operate as a separable module from the cluster management system.
*   Provide administrative security.
*   Provide a basic level of job accounting to aid in scheduling policies.
*   Provide a graphical user interface (GUI) 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 needs to know the exact nature of the submitted job, such as the execution time and resources required, and must possess the technical know-how to use the interface for submitting jobs.
*   **Cluster Administrator**: The user who oversees scheduling and cluster usage. This user must be an advanced cluster operator, fully qualified in using Linux, SGE, and the Libra Scheduler.

### 1.3.4 Limitations
*   **Hardware Limitations**: The system is designed to run on a homogenous Linux cluster. The initial implementation and testing will be performed on a small network of four Pentium-III workstations with 128 Mb RAM.
*   **Software and Interface Limitations**: The scheduler is an add-on for the Sun Grid Engine (SGE) cluster management system, version 5.3, and is dependent on its modules. All code will be written in standard C. The user interface is limited to the Linux command line or the SGE interface; a dedicated GUI is not planned for the initial version.
*   **Functional Limitations**: The scheduler will only manage sequential and embarrassingly parallel batch jobs. It will not support job migration for the purpose of decreasing resource fragmentation. There is no mechanism for users to interact or bargain with each other for resources. The exact costing and pricing policy will be specified in a later version.
*   **Algorithmic Limitations**: The scheduling algorithm will use heuristics and will not perform exhaustive searches of all job combinations.
*   **Regulatory and Licensing**: The project will be released as open-source software under a GPL license. No components will be purchased.
*   **Security**: The system will ensure the privacy of user job status. Alteration of scheduling criteria or resource allocation requires administrator authority.
*   **Quality Requirements**: The target maximum bug rate is 1 bug per KLOC.

## 1.4 Definitions
*   **Bid-based Proportional Resource-Sharing Model:** An economic model that specifies one way of allocating resources between competing users based on their criteria, such as deadline and budget. The amount of resource allocated to users is proportional to the values of their bids.
*   **Cluster/Cluster Computing:** A cluster is an integrated collection of two or more connected computers that work as a single system image spanning all its nodes. Clustering is a strategy for processing applications by transparently spreading the processing of different jobs throughout the cluster.
*   **Computational Economy:** 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. User constraints such as deadline and budget are more important in determining the priority of a job than system policies like ordering jobs according to submission time.
*   **Embarrassingly Parallel Jobs:** 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.
*   **Grid Computing:** An infrastructure that couples resources such as computers, software, and devices across the Internet and presents them as a unified integrated single resource.
*   **Homogenous cluster:** A cluster in which the nodes or workstations have uniform characteristics such as the same memory size, hard disk space, and 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:** 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:** Jobs that must be run on a single node and cannot be split into separate jobs.
*   **Stride Scheduling:** 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, representing the interval between two successive schedulings of a job. Jobs with more tickets have shorter strides and are scheduled more frequently.

# 2 References
[N/A]

## 3.1 Functions

The system's functionality is partitioned into the following sub-functions.

### 3.1.1 Submit Job
This function allows an end-user or administrator to submit a job to the cluster through the Sun Grid Engine (SGE) interface.

*   **Inputs**: User information (name, authentication ID), job information, and cluster information (type, current load).
*   **Processing**: The system first checks if the cluster is open for submissions. It then performs a validity check to verify that the user is authorized to submit jobs.
*   **Outputs**: A boolean value indicating whether the cluster is accepting submissions and a boolean value indicating if the user was successfully verified.

### 3.1.2 View Job Status
This function allows a user or administrator to view details and execution progress of submitted jobs.

*   **Inputs**: User ID and password for authentication.
*   **Processing**: The system authenticates the user and then displays the available status information for jobs submitted by that user.
*   **Outputs**: A user view of available options and status information for submitted jobs.

### 3.1.3 Delete/Change Job
This function allows a user or administrator to cancel a submitted job or, under specific circumstances, change a non-critical job parameter such as the output directory. Critical scheduling parameters like deadline and budget are not normally changeable.

*   **Inputs**: User ID and password for authentication.
*   **Processing**: The system authenticates the user, removes the job from the queue or updates its parameters, and revises scheduling decisions for other pending jobs to account for the change in resource availability.
*   **Outputs**: Updated cluster information, including CPU load, node status, and potentially revised finishing times for other pending jobs.

### 3.1.4 Initialize Job
This function prepares a job for scheduling after it has been accepted by SGE.

*   **Inputs**: The job information submitted by the user and the job ID assigned by SGE.
*   **Processing**: The system retrieves and parses the submitted job parameters. These parameters are then set in variables that represent the job's state and are passed to the scheduling module.
*   **Outputs**: A structured set of the job's details, including Job ID, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, and Deadline.

### 3.1.5 Accept/Reject Job
This function determines if a submitted job can be satisfied given its budget and deadline constraints and the current state of the cluster.

*   **Inputs**: Job details (Job ID, type, execution time, budget, deadline) and current cluster information (CPU load, node status, remaining time of pending jobs).
*   **Processing**: Based on the job parameters and cluster load, the scheduler calculates a priority for the job. It then determines if the job can be completed by the specified deadline. This acts as a validity check on the feasibility of the user's request.
*   **Outputs**: A boolean value indicating whether the job has been accepted or rejected. If rejected, the system may provide a suggested alternative deadline or cost as a precondition for acceptance.

### 3.1.6 Calculate Scheduling Information
This function determines how a job will be scheduled based on its budget and deadline, using the Stride Scheduling algorithm. This is performed after a job is accepted.

*   **Inputs**: Job details, specifically the budget and deadline.
*   **Processing**: The system allocates "tickets" to a job based on its budget and deadline relative to all other jobs. It then calculates the job's stride and pass. The stride is inversely proportional to the number of tickets allocated to the job.
*   **Outputs**: The job's scheduling information: its allocated tickets, stride, and pass value.

### 3.1.7 Determine Execution Host
This function decides on which node and in which queue the job will be placed for execution.

*   **Inputs**: Job details (type, execution time, budget, deadline) and cluster information (CPU load, node status, available memory).
*   **Processing**: To ensure load balancing, the system first identifies the host with the lightest load. It then selects the appropriate queue on that host based on the job's type (sequential or embarrassingly parallel) and budget.
*   **Outputs**: The identity of the chosen execution host and queue.

### 3.1.8 Dispatch Job
This function inserts the job into the queue on the previously determined execution host. The dispatcher decides when to perform this insertion, allowing jobs with more urgent deadlines to be scheduled earlier.

*   **Inputs**: The chosen execution host and queue.
*   **Processing**: The scheduler sends the job to the appropriate queue where it will compete for resources.
*   **Outputs**: The scheduled job placed in its designated host and queue.

### 3.1.9 Update Cluster Status
This function updates the cluster's status whenever a job is scheduled for execution or when a job finishes and is removed from the cluster.

*   **Inputs**: Job details and the chosen execution host and queue.
*   **Processing**: The system reserves the resources required by the job on the node. It then updates the execution host's queue status and sends information about the new load to the central information store on the master host.
*   **Outputs**: This function is a trigger that updates the system state and has no direct data output.

### 3.1.10 Execute Job
This function manages the time-slicing between all concurrently executing jobs based on the Stride Scheduling algorithm.

*   **Inputs**: The scheduled job in its queue and its associated scheduling information (tickets, stride, pass).
*   **Processing**: The system continuously repeats the following loop for jobs in a queue:
    1.  Select the job with the minimum pass value.
    2.  Allot a quantum of execution time to that job.
    3.  Advance the job's pass value by its stride.
*   **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 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.
*   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.
*   Under all circumstances, the maximum cost charged to the user will not exceed the maximum cost payable as submitted by the user.

## 3.3 Usability requirements
The system shall be usable by two classes of users: the cluster user and the cluster administrator. The cluster user is expected to have the technical knowledge to use a command-line interface. The administrator must be an advanced cluster operator, fully qualified in using Linux and the Sun Grid Engine (SGE).

The minimal user interface will be the Linux command prompt or the interface provided by the SGE cluster management system. A graphical user interface (GUI) is a desirable future enhancement but is not required for the initial version.

The system shall provide interfaces for the following user roles and actions:

*   **Cluster User Interface**
    *   Submit jobs with the associated deadline, cost, and execution time.
    *   Query the cluster to establish the current cost per unit time for submitting new jobs.
    *   Monitor the status of submitted jobs.
    *   Cancel jobs submitted by the user.
    *   Check the user's credit balance.
    *   Check the user's usage history.
*   **Cluster Administrator Interface**
    *   All actions available to the cluster user.
    *   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.

To ensure system integrity and prevent harm from misuse, the scheduler will ensure the privacy of user job status and prevent alteration of scheduling criteria or resource allocation without administrator authority.

Online user documentation shall be provided in the form of man pages accessible through the Linux command line. All documentation will be made in accordance with requirements for open-source software under the GNU General Purpose License.

## 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 a sub-component of the Sun Grid Engine (SGE) cluster management system, version 5.3.
*   All coding will be done in standard C.
*   The scheduling algorithm will be developed using heuristics; exhaustive searches of the entire set of combinations of jobs will not be done.
*   All code will be written as specified by the Hungarian Naming Convention.
*   The software will be released under a GNU General Purpose License (GPL).
*   The system must operate on a Linux-based cluster, and no modifications to the Linux kernel are permitted.
*   Regulatory Requirements: [N/A]

## 3.7 Software system attributes
### 3.7.1 Reliability
There will be a maximum of 1 bug/KLOC.

### 3.7.2 Availability
In case of a system outage, the cluster will be down while the Linux operating system boots up. This will take less than five minutes.

### 3.7.3 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.

### 3.7.4 Maintainability
*   The scheduler should be separable from the cluster management system.
*   All code will be written as specified by the Hungarian Naming Convention.
*   All code will be written as required by the GNU General Purpose License.

### 3.7.5 Portability
All coding will be done in standard C.

## 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.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.1 Assumptions and dependencies
*   The workability of the Sun Grid Engine cluster management system modules, such as those dealing with process migration, with the scheduling policies provided by the Libra Scheduler is assumed.
*   A basic module of job accounting and payment considerations will be provided, as they are not the focus of the scheduler.
*   Users are assumed to have a fair estimate of job execution times, so that the decision to accept or reject a job is facilitated.

## 5.2 Acronyms and abbreviations
*   **CPU**: Central processing unit of a computer.
*   **GUI**: Graphical user interface.
*   **QoS**: Quality of Service – meeting what users actually want, thus maximizing their utility.
*   **SGE**: Sun Grid Engine cluster management system.