## 1.1 Purpose
This SRS describes the requirements and specifications of Libra, an Economy-Driven Cluster Scheduler. It explains the functional features of the scheduler, along with interface details, design constraints, and related considerations such as performance characteristics. The SRS is intended for users and owners of high-performance clusters, cluster management software, job schedulers, and grid resources.

## 1.2 Scope
The software product described in this document is the Libra Scheduler.

The Libra Scheduler will function as an add-on to the queuing, scheduling, and resource management module of the open-source Sun Grid Engine (SGE) cluster management system. It 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. The scheduler will manage sequential and embarrassingly parallel batch jobs to be run on a homogenous Linux cluster. It will not provide a mechanism for users to interact with each other or bargain on the use of resources.

The main objective of Libra is to provide Quality of Service (QoS) computational economy in cluster computing. This application aims to maximize user utility by optimizing resource utilization within user-imposed constraints, such as budget and deadline, thereby prioritizing user satisfaction.

[N/A]

### 1.3.1 Product perspective
The Libra Scheduler is an add-on component to the Sun Grid Engine (SGE) cluster management system, operating within a Linux-based cluster environment. Libra's primary role is to provide market-based, economy-driven scheduling for batch jobs, focusing on Quality of Service (QoS) based on user utility rather than system performance.

The overall system operates as follows:
*   SGE receives jobs submitted by users.
*   SGE delegates these jobs to Libra for scheduling and allocation to appropriate workstations or execution hosts.
*   Libra communicates its scheduling decisions regarding workstation allocation back to the SGE resource manager.
*   The SGE resource manager then dispatches the job to the chosen workstation.
*   Once a job is assigned to a workstation, Libra is responsible for implementing its scheduling policy on the jobs executing at those workstations.
*   No modifications to the Linux kernel are required for Libra's operation.

#### System interfaces
The Libra Scheduler interfaces directly with the Sun Grid Engine (SGE) cluster management system.
*   SGE is responsible for initial job submission and dispatching jobs to execution hosts based on Libra's decisions.
*   Libra receives job information from SGE and provides scheduling decisions (e.g., job acceptance/rejection, execution host, queue) back to SGE.
*   The SGE interface will require adaptation to support additional job submission parameters specific to Libra's QoS-driven approach (e.g., budget, deadline).
*   Outputs related to job deletion or changes (e.g., updated cluster information, revised scheduling decisions) are facilitated by SGE functionality, not independently produced by Libra.

#### User interfaces
The Libra Scheduler supports two primary user types: the cluster user and the cluster administrator.
*   **Cluster User Interface:** Users interact with the system via the Linux command prompt or through the interface provided by the Sun Grid Engine cluster management system. This 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 their submitted jobs.
    *   Cancel jobs they have submitted.
    *   Check their credit balance.
    *   Check their usage history.
*   **Cluster Administrator Interface:** Administrators interact with the system via the Linux command prompt or through the interface provided by the Sun Grid Engine cluster management system. In addition to all user commands, administrators can:
    *   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.
*   At present, only command-line or SGE-provided interfaces are supported. A Graphical User Interface (GUI) may be added in a later version.

#### Hardware interfaces
All hardware interfaces for Libra are inherited from the Sun Grid Engine (SGE) system, on top of which Libra operates. Libra will incorporate SGE's interfaces for managing and monitoring:
*   CPU usage
*   Memory usage
*   Swap file creation
*   Network communication

#### Software interfaces
The Libra Scheduler interfaces with the following software components:
*   **Sun Grid Engine (SGE)**
    *   **Name:** Sun Grid Engine
    *   **Version:** 5.3 (modified)
    *   **Source:** Sun Microsystems, Inc.
    *   **Purpose:** Libra directly interfaces with the modified SGE for job submission, resource allocation, and job execution management. SGE, in turn, interfaces with the underlying operating system and other necessary software components.
*   **Operating System**
    *   **Name:** Linux (implied)
    *   **Version:** [N/A]
    *   **Source:** Open source
    *   **Purpose:** SGE, and by extension Libra, operates on a Linux-based cluster. No modifications to the Linux kernel are required by Libra.
*   **Parallel Virtual Machine (PVM) libraries**
    *   **Name:** PVM (Parallel Virtual Machine)
    *   **Version:** [N/A]
    *   **Source:** University of Tennessee, Oak Ridge National Laboratory, and Emory University
    *   **Purpose:** Used by the cluster for the execution of embarrassingly parallel jobs.
*   **Message Passing Interface (MPI) libraries**
    *   **Name:** MPI (Message Passing Interface)
    *   **Version:** [N/A]
    *   **Source:** University of Chicago and Mississippi State University
    *   **Purpose:** Used by the cluster for the execution of embarrassingly parallel jobs.

#### Communications interfaces
Libra will utilize the existing communications architecture of the Sun Grid Engine itself. It will not introduce any unique communications interfaces beyond those provided by SGE.

#### Memory constraints
[N/A]

#### Operations
The Libra Scheduler supports various operational modes and functions:
*   **User-initiated operations:** Users can submit, monitor, cancel jobs, and query system status and personal account information through command-line or SGE interfaces.
*   **Administrator-initiated operations:** Administrators can perform all user operations, in addition to monitoring cluster health, managing system policies (cost, scheduling), and controlling any submitted job (cancel, suspend, resume).
*   **Automated processing:** Libra performs automated functions such as initializing jobs, accepting/rejecting jobs based on QoS parameters, calculating scheduling information (tickets, stride, pass), determining execution hosts and queues, dispatching jobs, updating cluster status, and executing jobs using the stride-scheduling algorithm.
*   **Data processing support functions:** Libra processes job parameters (budget, deadline, execution time) and cluster information (CPU load, node status, remaining job times, available memory) to make scheduling decisions.
*   **Backup and recovery operations:** [N/A]

#### Site adaptation requirements
The Libra Scheduler is designed to manage jobs on a homogenous Linux cluster. No specific site or mission-related features are defined for modification to adapt the software to a particular installation.

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

### 1.3.2 Product functions

The Libra Scheduler's primary function is to maximize user utility by providing Quality of Service (QoS) computational economy in cluster computing. It achieves this by scheduling CPU time based on user-defined parameters such as allocated budget and job deadline, rather than solely on system performance.

The major functions of the Libra Scheduler include:

*   **Job Allocation and Prioritization:** Allocating jobs to cluster resources based on user-centric priorities derived from budget and deadline, as well as other job specifications like executable location, system type, maximum execution time, and whether the job is sequential or embarrassingly parallel.
*   **Dynamic Resource Management:** Dynamically reallocating resources, changing job priorities, privileges, and execution order to accommodate urgent or high-value jobs, even if submitted later or during high system load.
*   **Scalable and Configurable Scheduling:** Maintaining performance as the cluster size and job count increase, and allowing for configurable scheduling policies that can incorporate various QoS parameters.
*   **Resource Accounting:** Providing a basic level of job accounting to track resource usage, which aids in scheduling decisions.
*   **Economic Model Implementation:** Utilizing a market-based, bid-based proportional resource-sharing model to determine resource pricing and allocation according to user constraints.
*   **Proportional Resource Enforcement:** Employing the stride-scheduling algorithm to ensure that actual resource allocation accurately reflects the calculated job share.
*   **System Integration:** Operating as a separable add-on to the Sun Grid Engine (SGE) cluster management system, leveraging its capabilities for job submission, dispatch, and cluster status management.
*   **Security:** Providing administrative security and control over scheduling criteria and resource allocation.

### 1.3.3 User characteristics
There are essentially two classes of users for the Libra Scheduler used with the Sun Grid Engine cluster management system:
*   **Cluster User**: This user wishes to submit jobs for the cluster. They need to know the exact nature of the submitted job, such as the execution time and required resources, and must possess the technical know-how to use the interface for submitting jobs.
*   **Cluster Administrator**: This user oversees scheduling and cluster usage. They must be an advanced cluster operator, fully qualified in using Linux, SGE, and the Libra Scheduler.

### 1.3.4 Limitations
The following items limit the supplier's options for the Libra Scheduler:

*   **Scope and Functionality**
    *   The scheduler will only manage sequential and embarrassingly parallel batch jobs.
    *   There will be no mechanism for users to interact with each other or bargain for resources.
    *   A basic module for job accounting and payment considerations will be provided, as these are not the primary focus of the scheduler.
    *   Detailed requirements for the economic front-end, including exact costing and pricing policies, will be specified in a later version.
    *   The scheduler will not support job migration for the purpose of decreasing resource fragmentation.
    *   Exhaustive searches of all job combinations will not be performed; heuristics will be developed for scheduling.

*   **Hardware and Environment**
    *   The current implementation and testing environment is limited to a network of four Pentium-III workstations with 128 MB RAM, running the Sun Grid Engine (SGE) on a Linux operating system.
    *   The scheduler will operate as a sub-component of the Sun Grid Engine cluster management system.
    *   No modifications to the Linux kernel are required.

*   **Interfaces**
    *   Initially, user and administrator interaction will be limited to a command-line Linux interface or the existing Sun Grid Engine interface; a Graphical User Interface (GUI) may be added in a later version.
    *   Libra will directly interface with the modified Sun Grid Engine cluster management system, version 5.3.
    *   Hardware and communication interfaces will be those provided by the Sun Grid Engine.

*   **Quality and Performance**
    *   A maximum bug rate of 1 bug per KLOC is targeted.
    *   All jobs are expected to be completed within a 10% error allowance, assuming accurate job statistics are submitted.
    *   The maximum response time for job submission will be 1 minute.
    *   The maximum cost charged to the user will not exceed the budget submitted by the user.

*   **Security**
    *   The scheduler must ensure the privacy of user job status.
    *   Full control over job execution must be maintained, preventing alteration of scheduling criteria or resource allocation without administrator authority.

*   **Development and Licensing**
    *   All coding will be done in standard C.
    *   All code will adhere to the Hungarian Naming Convention.
    *   The project will be open-source and released under the GNU General Purpose License (GPL); no components will be purchased.

## 1.4 Definitions
*   **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.
*   **QoS**: Quality of Service – meeting what users actually want, thus maximizing their utility.
*   **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.
*   **Linux**: An open source operating system, with extensive documentation and user support.
*   **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.
*   **Bid-based Proportional Resource-Sharing Model**: 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.
*   **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, 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.
*   **Process Migration**: The process of moving a job from one computer system to another without restarting the job from the beginning.
*   **Sequential Jobs**: Jobs that must be run on a single node, and cannot be split into separate jobs.
*   **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. This is opposed to real parallel jobs that comprise dependent threads that need to interact with each other during the course of execution.
*   **Job accounting**: A method of quantifying the system resources used by a job.
*   **GUI**: Graphical user interface.
*   **CPU**: Central processing unit of a computer.
*   **SGE**: Sun Grid Engine cluster management system.
*   **Open-source software**: Software for which the code is freely available for use and research.
*   **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.

# 2 References
## Compliance
[N/A]

## Guidance
1.  Title: "Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid"
    Authors: R. Buyya, D. Abramson, and J. Giddy
    Report Number: [N/A]
    Date: 2000
    Publishing Organization: IEEE CS Press, USA
    Source: HPC ASIA’2000, China proceedings

2.  Title: "An Economy Driven Resource Management Architecture for Global Computational Power Grids"
    Authors: R. Buyya, D. Abramson, J. Giddy
    Report Number: [N/A]
    Date: June 26-29, 2000
    Publishing Organization: The 2000 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2000)
    Source: PDPTA 2000, Las Vegas, USA proceedings

3.  Title: "An Economy Grid Architecture for Service-Oriented Grid Computing"
    Authors: R. Buyya, D. Abramson, and J. Giddy
    Report Number: [N/A]
    Date: April 2001
    Publishing Organization: 10th IEEE International Heterogeneous Computing Workshop (HCW 2001)
    Source: HCW 2001, with IPDPS 2001, SF, California, USA proceedings

4.  Title: "Economic Models for Management of Resources in Peer-to-Peer and Grid Computing"
    Authors: Rajkumar Buyya, Heinz Stockinger, Jonathan Giddy, and David Abramson
    Report Number: [N/A]
    Date: [N/A]
    Publishing Organization: Monash University
    Source: Monash University

5.  Title: "Market-based proportional resource sharing for clusters"
    Authors: B.N. Chun and D.E. Culler
    Report Number: [N/A]
    Date: September 1999
    Publishing Organization: [N/A] (Submitted for publication)
    Source: [N/A]

## 3.1 Functions

The Libra Scheduler provides an economy-driven approach to managing batch jobs on clusters, focusing on Quality of Service (QoS) based on user utility. The core functions involve accepting, scheduling, and executing jobs while interacting with the underlying Sun Grid Engine (SGE) cluster management system. The functional requirements are partitioned into the following sub-functions:

### 3.1.1 Submit Job

This function allows end-users or administrators to submit jobs to the cluster. It is primarily facilitated by the Sun Grid Engine (SGE) interface, which may be adapted to include additional Libra-specific submission parameters, or through a command-line interface.

*   **Inputs:**
    *   User Information: User name and authentication ID.
    *   Job Information: Details about the job to be submitted, including specifications for `Initialize Job`.
    *   Cluster Information: Cluster type, scheduling mechanism details, current load status, submission directions, and criteria.
*   **Processing:**
    *   The cluster determines if it is currently open for job submissions.
    *   The system validates the user attempting to submit the job.
    *   This decision is distinct from the `Accept/Reject Job` feature, which evaluates job parameters like budget and deadline.
*   **Outputs:**
    *   Boolean value indicating whether the cluster is accepting submissions.
    *   Boolean value indicating whether the user has been verified.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.2 View Job Status

This function enables users or administrators to view details about submitted jobs and monitor their execution progress.

*   **Inputs:**
    *   User ID and Password: Required to ensure only authorized users can view job status.
*   **Processing:**
    *   Displays available options regarding the submitted job.
    *   Provides information about the progress of job execution.
    *   Processes selected options if choices are provided to the user to view different aspects of job information.
*   **Outputs:**
    *   A user-specific view of available options and information about jobs submitted by that user.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.3 Delete/Change Job

This function allows users or administrators to cancel a job or, under specific circumstances, modify certain job parameters. Critical parameters like deadline and cost are generally not changeable, but modifications such as output directory or a delayed deadline may be permitted.

*   **Inputs:**
    *   User ID and Password: Required to ensure only authorized users can delete or change the job.
*   **Processing:**
    *   Removes the specified job from the queue.
    *   Updates the cluster status to reflect the job's removal.
    *   Revises scheduling decisions for pending jobs and the submission of new jobs.
*   **Outputs:**
    *   Updated cluster information, including CPU load, node status, queue length, quanta allocated to pending jobs, and revised expected finishing deadlines of pending jobs. These outputs are facilitated by the Sun Grid Engine and not independently produced by Libra.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.4 Initialize Job

This is a core functional requirement that prepares the scheduler for eventually scheduling and executing a job. Libra performs this function once a job has been accepted by SGE, using information from the scheduler.

*   **Inputs:**
    *   Information submitted by the user about the job.
    *   The job ID assigned by SGE.
*   **Processing:**
    *   Retrieves the detailed information of the job.
    *   Sets these details into variables that represent the state of the cluster and its queues.
    *   Passes the parsed parameters to the scheduling module for further evaluation (e.g., acceptance or rejection).
*   **Outputs:**
    *   A set of variables representing the exact job details: Job Id, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.5 Accept/Reject Job

This function is responsible for determining whether a user's job can be satisfied given its budget and deadline constraints.

*   **Inputs:**
    *   Job details: Job Id, Job type, Standalone Execution time, Location of executable and input data sets, System Type, Budget, Deadline.
    *   Cluster information: Current CPU load, node status, and remaining execution time of pending jobs.
*   **Processing:**
    *   Based on the job parameters, the scheduler calculates a priority for the job, reflecting the share of CPU time it deserves according to the specified criteria.
    *   The scheduler determines if the job can be completed by its requisite deadline, considering its execution time and the execution status of other pending jobs across various nodes.
*   **Outputs:**
    *   A boolean value indicating whether the job has been accepted or rejected.
    *   A suggested deadline or cost, which may be offered to the user as a precondition for job acceptance.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.6 Calculate Scheduling Information

This function decides how a job will be scheduled based on its budget and deadline. It utilizes the Stride Scheduling Algorithm to enforce resource allocations (CPU cycles) proportional to a user’s budget and deadline. This is performed by Libra once a job has been deemed accommodable.

*   **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 and deadline, as well as the budgets and deadlines of all other jobs on the potential execution host.
    *   Calculates the job's "stride" (inversely proportional to tickets, representing the interval between successive scheduling) and initializes its "pass" value (initially equal to its stride).
*   **Outputs:**
    *   Scheduling information for the job: its allocated tickets, stride, and pass values.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.7 Determine Execution Host

This function selects the specific node and queue where a job will be placed for execution. The decision is based on the job’s 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: Current CPU Load, Node Status, Remaining Time of Pending Jobs, Available Memory.
*   **Processing:**
    *   Libra first evaluates the load on each available host, sorting them in ascending order to identify the least loaded host, thereby ensuring load balancing.
    *   It then selects the appropriate queue on the chosen host, considering factors such as whether the job is sequential or embarrassingly parallel, its budget, and other relevant criteria.
*   **Outputs:**
    *   The chosen execution host and the specific queue on that host.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.8 Dispatch Job

This function takes the scheduled job and inserts it into the designated queue on the chosen execution host. It determines the optimal time to send the job for execution, potentially allowing other jobs to complete or be scheduled earlier if their deadlines are more urgent.

*   **Inputs:**
    *   The chosen execution host and the queue on which to place the job for execution.
*   **Processing:**
    *   The scheduler sends the job to the appropriate queue, where it then joins the competition for resources.
*   **Outputs:**
    *   The scheduled job, now placed in its appropriate host and queue.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.9 Update Cluster Status

This function updates the cluster's status whenever a job is scheduled for execution on a host or when a job completes and is removed from the cluster.

*   **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 necessary amount of resources for the job on the selected node.
    *   It updates the execution host's queue status.
    *   Sends information about the additional load on the queue and node to the central information store on the master host.
*   **Outputs:**
    *   There is no direct output; this function primarily performs an internal update and acts as a trigger.
*   **Responses to Abnormal Situations:** [N/A]

### 3.1.10 Execute Job

This function continuously runs as long as there are jobs in the queues. It is responsible for time-slicing between all currently executing jobs, with scheduling decisions made based on the stride-scheduling algorithm.

*   **Inputs:**
    *   Scheduled Job: Job details, including the queue and node where it is scheduled to run.
    *   Scheduling Information: The job’s tickets, stride, and pass values.
*   **Processing:**
    *   It examines all jobs across the cluster and selects the one with the minimum pass value.
    *   Allots a quantum of CPU time to the selected job.
    *   Advances the pass value of that job by its stride.
    *   In the event of a tie in pass values, jobs are ordered using a First-In, First-Out (FIFO) policy.
    *   This loop repeats until no jobs remain to be run on a queue.
*   **Outputs:**
    *   Updated Cluster Information: CPU Load, Node Status, Remaining Time of Pending Jobs, Available Memory.
*   **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 as such.
*   Assuming submitted statistics for jobs are accurate, the Libra scheduler will ensure that all jobs are completed with a 10% error allowance.
*   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
The primary usability objective of the Libra Scheduler is to provide Quality of Service (QoS) by meeting user expectations and maximizing user utility and satisfaction. This is achieved by prioritizing user-specified job parameters such as budget and deadline over system-centric performance considerations.

Specific usability requirements include:

*   **User Satisfaction and Effectiveness:**
    *   The system shall ensure that all jobs are completed within a 10% error allowance of the specified deadline, assuming accurate job statistics are provided.
    *   The system shall ensure that the maximum cost charged to the user does not exceed the budget submitted by the user.
    *   Users shall be able to submit jobs with associated deadline, cost, and execution time.
    *   Users shall be able to query the cluster for the current cost per unit time for submitting new jobs.
    *   Users shall be able to monitor the status of their submitted jobs.
    *   Users shall be able to cancel their submitted jobs.
    *   Users shall be able to check their credit balance and usage history.
    *   Administrators shall be able to check the status of each cluster node, usage patterns, and all submitted jobs.
    *   Administrators shall be able to check the load on each cluster node.
    *   Administrators shall be able to alter the cost structure and scheduling policy of the cluster.
    *   Administrators shall be able to cancel, suspend, and resume any job.

*   **Efficiency:**
    *   The maximum response time for the submission of a job shall be 1 minute.

*   **User Interface:**
    *   The system shall provide a command-line interface through Linux for both cluster users and administrators.
    *   The system shall leverage and adapt the interface provided by the Sun Grid Engine cluster management system for user and administrator interaction.
    *   Ideally, a Graphical User Interface (GUI) shall be provided for all components, including job submission for users and oversight for administrators, in future iterations.

*   **Documentation and Help:**
    *   Online user documentation shall be provided in the form of man pages accessible through Linux.

*   **Security and Control (Avoidance of Harm):**
    *   The Libra scheduler shall ensure the privacy of user job status.
    *   The Libra scheduler shall ensure full control over job execution, preventing alteration of scheduling criteria or actual resource allocation without administrator authority.

## 3.5 Logical database requirements

The Libra Scheduler, while not explicitly defining a relational database, requires a persistent data store to manage various types of information critical for its operation. This includes user-centric job parameters, cluster status, and scheduling decisions.

a) types of information used by various functions;

*   **User Data:**
    *   User ID, authentication ID, password.
    *   Credit balance.
    *   Usage history.
*   **Job Data:**
    *   Job ID.
    *   Job type (sequential or embarrassingly parallel).
    *   Standalone execution time.
    *   Location of executable and input data sets.
    *   System type.
    *   Budget allocated by the user.
    *   Deadline required by the user.
    *   Current job status (e.g., pending, executing, completed, cancelled).
    *   Scheduling information: tickets, stride, pass.
    *   Assigned execution host and queue.
*   **Cluster Data:**
    *   Cluster type.
    *   Scheduling mechanism details.
    *   Current load status (CPU load, node status, remaining time of pending jobs, available memory).
    *   Submission directions and criteria.
    *   Usage pattern history of the cluster.
    *   Cost structure of the cluster.
    *   Scheduling policy of the cluster.
*   **Pricing Data:**
    *   Current cost per unit time for submitting new jobs.

b) frequency of use;

*   **High Frequency:** Job Data (status, scheduling information, execution host, queue) and Cluster Data (load, node status, pending jobs, available memory) are frequently accessed and updated during job submission, scheduling, execution, and status monitoring.
*   **Moderate Frequency:** User Data (credit balance, usage history) is accessed upon user request.
*   **Low Frequency:** Administrator-specific Cluster Data (cost structure, scheduling policy) is accessed and altered by administrators.

c) accessing capabilities;

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

d) data entities and their relationships;

*   **Entities:**
    *   User
    *   Job
    *   Cluster Node
    *   Queue
    *   Scheduling Policy
    *   Cost Structure
*   **Relationships (Implicit):**
    *   A User submits multiple Jobs (one-to-many).
    *   A Job is associated with specific Scheduling Information (tickets, stride, pass).
    *   A Job is assigned to one Cluster Node and one Queue for execution.
    *   A Cluster Node can host multiple Jobs.
    *   A Queue can contain multiple Jobs.
    *   The system maintains a global Scheduling Policy and Cost Structure, which can be altered by an Administrator.
    *   Job Accounting data (usage history, credit balance) is associated with a User.

e) integrity constraints;

*   **Job Completion:** All accepted jobs are expected to be completed within their specified deadline, with a 10% error allowance, assuming accurate submitted statistics.
*   **Budget Adherence:** The maximum cost charged to a user for a job will not exceed the budget allocated by the user.
*   **User Authentication:** Only authenticated users are permitted to view or modify their own job details.
*   **Administrator Authority:** Alteration of scheduling criteria or actual resource allocation is restricted to administrators.

f) security;

*   **Data Privacy:** The system must ensure the privacy of user job status.
*   **Access Control:** User ID and password authentication will be enforced for accessing user-specific information and job status.
*   **Authorization:** Full control over job execution and the ability to alter scheduling criteria or resource allocation will be restricted to administrators.

g) data retention requirements.

*   A basic level of job accounting and usage history will be maintained to aid in scheduling policies and allow users to check their usage. Specific data retention periods are not defined in this version of the SRS.

## 3.6 Design constraints
*   **Parent Component: Sun Grid Engine**
    The Libra scheduler will be a sub-component of SGE.
*   **Software Language**
    All coding will be done in standard C.
*   **Scheduling Constraints**
    Exhaustive searches of the entire set of combinations of jobs will not be done. Heuristics will be developed for this scheduling problem.

## 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 system outage, the cluster will be down while the Linux operating system boots up, which will take less than five minutes.

### c) Security
*   The system will provide administrative security.
*   The Libra scheduler will ensure the privacy of user job status.
*   The Libra scheduler will ensure full control over job execution, preventing alteration of scheduling criteria or actual resource allocation without administrator authority.

### d) Maintainability
*   All code will adhere to the Hungarian Naming Convention.
*   All code will be written as required by the GNU General Purpose License.
*   The Libra scheduler will be a sub-component of the Sun Grid Engine.

### e) Portability
*   All coding will be done in standard C.
*   No modifications to the Linux kernel are required.
*   The scheduler is designed to run on a homogenous Linux cluster, but its functionality can be adapted to schedule resources other than CPU time, even on a heterogeneous cluster.
*   User and administrator interaction will primarily be through the Linux command prompt or the Sun Grid Engine cluster management system interface.

## 3.8 Supporting information
The Libra Scheduler addresses the current lack of a holistic scheduling mechanism in cluster computing that enables differing Quality of Service (QoS) levels for different clients. Its main objective is to provide market-based, economy-driven service for managing batch jobs on clusters by scheduling CPU time according to user utility (e.g., budget and deadline) rather than solely system performance considerations.

The following information items are provided to clarify the scope and future development:

*   Detailed requirements for the economic front-end, including the exact costing and pricing policy for charging users, will be specified in a later version of this document. The pricing mechanism will not affect the scheduling policies, as they assume a given cost and budget, and schedule resources accordingly.
*   At present, user and administrator interfaces will be limited to a command-line Linux interface or the interface provided by the Sun Grid Engine cluster management system. A Graphical User Interface (GUI) might be added once the basic functionality is implemented.
*   It remains to be decided whether a custom software tool for simulation and testing purposes will be designed or if a generic, freely available tool will be used.

## 4.1 Functions
[N/A]

## 4.2 Performance requirements
Verification of the performance requirements will involve the following approaches and methods:

*   **Response Time Verification**:
    *   **Method**: Conduct load testing by submitting jobs under varying system loads, including low, medium, and high CPU utilization and different queue lengths. The time elapsed from the initiation of a job submission to the system's confirmation of job acceptance will be measured.
    *   **Criteria**: The measured response time for job submission shall not exceed 1 minute.

*   **Capacity Verification**:
    *   **Method**: Perform stress testing by progressively increasing the number of concurrent jobs submitted to the cluster. Monitor the scheduler's behavior and the cluster's resource utilization (CPU, memory, network) until jobs begin to consistently miss their deadlines due to node saturation.
    *   **Criteria**: The scheduler shall continue to process and attempt to schedule jobs without internal failure or imposing an artificial upper limit before the underlying cluster nodes reach their capacity to fulfill job deadlines. This may require a simulation tool or a larger testbed for comprehensive analysis.

*   **Deadline Sensitivity Verification**:
    *   **Method**: Execute test suites comprising jobs with diverse, predefined deadlines and accurately estimated execution times. The actual completion time of each job will be monitored and compared against its specified deadline.
    *   **Criteria**: All jobs shall be completed within a 10% error allowance of their specified deadlines, assuming the submitted job statistics are accurate.

*   **Cost Sensitivity Verification**:
    *   **Method**: Submit jobs with explicitly defined maximum budgets. Upon job completion, the actual cost charged for each job will be retrieved from the job accounting system.
    *   **Criteria**: The charged cost for any job shall not exceed the user-specified maximum budget under any circumstances.

## 4.3 Usability requirements
[N/A]

## 4.5 Logical database requirements
[N/A]

## 4.6 Design constraints
The verification of design constraints will involve the following approaches:

*   **Parent Component: Sun Grid Engine**
    Verification will involve integration testing to confirm that the Libra scheduler functions correctly as a sub-component of the Sun Grid Engine (SGE) version 5.3. This includes validating the communication and data exchange through the defined software interfaces with SGE.

*   **Software Language**
    Verification will be performed through code reviews and static analysis tools to ensure that all coding adheres to the standard C language specification.

*   **Scheduling Constraints**
    Verification will involve reviewing the design and implementation of the scheduling algorithms to confirm that they utilize heuristics and do not perform exhaustive searches of job combinations. Performance testing under various load conditions will also be conducted to ensure the efficiency expected from a heuristic-based approach.

## 4.7 Software system attributes
[N/A]

## 5.1 Assumptions and dependencies
A number of factors that may affect the requirements specified in this 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
*   **Cluster/Cluster Computing:** Connecting two or more computers together to take advantage of combined computational power and resources, working as an integrated collection of resources that can provide a single system image spanning all its nodes.
*   **CPU:** Central processing unit of a computer.
*   **Computational Economy:** The inclusion of user-specified Quality of Service (QoS) parameters with jobs so that resource management is based on a user-centric approach rather than on a system-centric approach.
*   **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, 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.
*   **GUI:** Graphical user interface.
*   **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.
*   **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.
*   **SGE:** Sun Grid Engine cluster management system.
*   **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, where a stride is inversely proportional to the number of tickets allocated to a job.